BigTable > Log-structure merge-tree (LSM tree) > LSM原理解读 | 20 minutes to warmup

 LSM原理解读  本文来源：码农网 本文链接：https://www.codercto.com/a/49359.html 

内容简介：06年，Google发表了BigTable论文，从此推开了大数据时代的大门。为什么又提及BigTable，是因为这篇论文中使用了LSM这种数据结构。LSM: Log Structured-Merge Tree(日志结构合并树)，是一种先于BigTable出现的文件组织方式，最早可以追溯到1996年 Patrick O'Neil等人的论文。在BigTable出现之后开始被重视被广泛应用，比较有名的产品就是Hbase、Cassandra、Leveldb等。

06年，Google发表了BigTable论文，从此推开了大数据时代的大门。

为什么又提及BigTable，是因为这篇论文中使用了LSM这种数据结构。

LSM: Log Structured-Merge Tree(日志结构合并树)，是一种先于BigTable出现的文件组织方式，最早可以追溯到1996年 Patrick O'Neil等人的论文。在BigTable出现之后开始被重视被广泛应用，比较有名的产品就是Hbase、Cassandra、Leveldb等。

• 用一句话先简单概括其原理

把一颗大树拆分成N棵小树，数据先写入内存中，随着小树越来越大，内存的小树会flush到磁盘中。 磁盘中的树定期做合并操作，合并成一棵大树，以优化读性能。

• 先用个简单的结构看一下

 最简单的LSM tree是两层树状结构C0,C1。 C0比较小，驻留在内存，当C0超过一定的大小， 一些连续的片段会从C0移动到磁盘中的C1中，这是一次merge的过程。在实际的应用中， 一般会分为更多的层级(level)， 而层级C0都会驻留在内存中。

背景

LSM被设计来提供比传统的B+树或者ISAM(Indexed Sequential Access Method)更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个目标。之所以说这是一个好方法，是因为对于存储来讲问题的本质还是磁盘随机操作慢，顺序读写快。顺序读写磁盘快于随机读写主存，而且快至少三个数量级。

如果对写操作的吞吐量敏感,一个好的办法是简单的将数据添加到文件。这个策略经常被使用在日志或者堆文件，因为他们是完全顺序的，所以可以提供非常好的写操作性能。

同时他们也有一些缺点，从日志文件中读一些数据将会比写操作需要更多的时间，需要倒序扫描，直接找到所需的内容。

这说明日志仅仅适用于一些简单的场景：1. 数据是被整体访问，像大部分 数据库 的WAL(write-ahead log) 2. 知道明确的offset，比如在Kafka。

与此同时我们也有多种方法来支持复杂的读场景，比如二分查找、哈希、B+数等。这些方式虽提升了读的性能，却丢失了日志文件很好的写性能。

不管怎样，随机的操作要尽量减少。所以LSM就出现了，保持了日志文件写性能，以及微小的读操作性能损失。本质上就是让所有的操作顺序化。

算法

LSM将之前使用一个大的查找结构，变换为将写操作顺序的保存到一些相似的有序文件(Sorted Strings Table,简称sstable)中。所以每个文件包 含短时间内的一些改动。因为文件是有序的，所以之后查找也会很快。文件是不可修改的，他们永远不会被更新，新的更新操作只会写到新的文件中。通过周期性的合并这些文件来减少文件个数。 此时可以回到上面看图 。

更具体的看，当一些更新操作到达时，他们会被写到内存缓存（也就是memtable）中，memtable使用树结构来保持key的有序，在大部分的实现中，memtable会通过写WAL的方式备份到磁盘，用来恢复数据，防止数据丢失。当memtable数据达到一定规模时会被刷新到磁盘上的一个新文件，重要的是系统只做了顺序磁盘读写，因为没有文件被编辑，新的内容或者修改只用简单的生成新的文件。

因为比较旧的文件不会被更新，重复的纪录只会通过创建新的纪录来覆盖，这也就产生了一些冗余的数据。所以系统会周期的执行合并操作（compaction)。 合并操作选择一些文件，并把他们合并到一起，移除重复的更新或者删除纪录，同时也会删除上述的冗余。更重要的是，通过减少文件个数的增长，保证读操作的性能。因为sstable文件都是有序结构的，所以合并操作也是非常高效的。

当一个读操作请求时，系统首先检查内存数据(memtable)，如果没有找到这个key，就会逆序的一个一个检查sstable文件，直到key 被找到。因为每个sstable都是有序的，所以查找比较高效(O(logN))，但是读操作会变的越来越慢随着sstable的个数增加，因为每一个 sstable都要被检查。

所以，读操作比其它本地更新的结构慢，幸运的是，有一些技巧可以提高性能。最基本的的方法就是页缓存（也就是leveldb的 TableCache，将sstable按照LRU缓存在内存中）在内存中，减少二分查找的消耗。

即使有每个文件的索引，随着文件个数增多，读操作仍然很慢。通过周期的合并文件，来保持文件的个数，因些读操作的性能在可接收的范围内。即便有了合 并操作，读操作仍然会访问大量的文件，大部分的实现通过布隆过滤器来避免大量的读文件操作, cassandra就采用了Bloom filter的方式。

思考

我们看到LSM有更好的写性能，同时LSM还有其它一些好处。sstable文件是不可修改的，这让对他们的锁操作非常简单。一般来说，唯一的竞争资源就是 memtable，相对来说需要相对复杂的锁机制来管理在不同的级别。

而如scylladb，通过异步IO，非阻塞线程，线程和线程之间通过消息通讯，没有内存的共享，没有互斥锁，也没有原子操作来大幅的提高了cpu的效率。

2016年，Lanyue Lu等人发布了WiscKey论文，这篇论文提出了一种新的设计 WiscKey: Separating Keys from Values in SSD-conscious Storage，专门为SSD所优化，将key和value分别存储以减少I/O放大。key存在LSM tree中， value存在WAL中，叫做value log。

通常情况下，key比较小，所以LSM tree比较小，当获取value值的时候，再从SSD存储中读取。

本文来源：码农网
本文链接：https://www.codercto.com/a/49359.html

LSM tree (log-structured merge-tree) > Memtable | Sparse index

作者：henryPKU
链接：https://www.zhihu.com/question/19887265/answer/1714901833
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LSM tree (log-structured merge-tree) 是一种对频繁写操作非常友好的数据结构，同时兼顾了查询效率。LSM tree 是许多 key-value 型或日志型数据库所依赖的核心数据结构，例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB 等。

LSM tree 之所以有效是基于以下事实：磁盘或内存的连续读写性能远高于随机读写性能，有时候这种差距可以达到三个数量级之高。这种现象不仅对传统的机械硬盘成立，对 SSD 硬盘也同样成立。如下图：

LSM tree 在工作过程中尽可能避免随机读写，充分发挥了磁盘连续读写的性能优势。

SSTable

LSM tree 持久化到硬盘上之后的结构称为 Sorted Strings Table (SSTable)。顾名思义，SSTable 保存了排序后的数据（实际上是按照 key 排序的 key-value 对）。每个 SSTable 可以包含多个存储数据的文件，称为 segment，每个 segment 内部都是有序的，但不同 segment 之间没有顺序关系。一个 segment 一旦生成便不再修改（immutable）。一个 SSTable 的示例如下：

可以看到，每个 segment 内部的数据都是按照 key 排序的。下面我们来介绍每个 segment 是如何生成的。

写入数据

LSM tree 的所有写操作均为连续写，因此效率非常高。但由于外部数据是无序到来的，如果无脑连续写入到 segment，显然是不能保证顺序的。对此，LSM tree 会在内存中构造一个有序数据结构（称为 memtable），例如红黑树。每条新到达的数据都插入到该红黑树中，从而始终保持数据有序。当写入的数据量达到一定阈值时，将触发红黑树的 flush 操作，把所有排好序的数据一次性写入到硬盘中（该过程为连续写），生成一个新的 segment。而之后红黑树便从零开始下一轮积攒数据的过程。

读取/查询数据

如何从 SSTable 中查询一条特定的数据呢？一个最简单直接的办法是扫描所有的 segment，直到找到所查询的 key 为止。通常应该从最新的 segment 扫描，依次到最老的 segment，这是因为越是最近的数据越可能被用户查询，把最近的数据优先扫描能够提高平均查询速度。

当扫描某个特定的 segment 时，由于该 segment 内部的数据是有序的，因此可以使用二分查找的方式，在 O(logn) 的时间内得到查询结果。但对于二分查找来说，要么一次性把数据全部读入内存，要么在每次二分时都消耗一次磁盘 IO，当 segment 非常大时（这种情况在大数据场景下司空见惯），这两种情况的代价都非常高。一个简单的优化策略是，在内存中维护一个稀疏索引（sparse index），其结构如下图：

稀疏索引 sparse index | 全量索引（dense index）| March 28, 2022 review 

稀疏索引是指将有序数据切分成（固定大小的）块，仅对各个块开头的一条数据做索引。与之相对的是全量索引（dense index），即对全部数据编制索引，其中的任意一条数据发生增删均需要更新索引。两者相比，全量索引的查询效率更高，达到了理论极限值 O(logn)，但写入和删除效率更低，因为每次数据增删时均需要因为更新索引而消耗一次 IO 操作。通常的关系型数据库，例如 MySQL 等，其内部采用 B tree 作为索引结构，这便是一种全量索引。

有了稀疏索引之后，可以先在索引表中使用二分查找快速定位某个 key 位于哪一小块数据中，然后仅从磁盘中读取这一块数据即可获得最终查询结果，此时加载的数据量仅仅是整个 segment 的一小部分，因此 IO 代价较小。以上图为例，假设我们要查询 dollar 所对应的 value。首先在稀疏索引表中进行二分查找，定位到 dollar 应该位于 dog 和 downgrade 之间，对应的 offset 为 17208~19504。之后去磁盘中读取该范围内的全部数据，然后再次进行二分查找即可找到结果，或确定结果不存在。

稀疏索引极大地提高了查询性能，然而有一种极端情况却会造成查询性能骤降：当要查询的结果在 SSTable 中不存在时，我们将不得不依次扫描完所有的 segment，这是最差的一种情况。有一种称为布隆过滤器（bloom filter）的数据结构天然适合解决该问题。布隆过滤器是一种空间效率极高的算法，能够快速地检测一条数据是否在数据集中存在。我们只需要在写入每条数据之前先在布隆过滤器中登记一下，在查询时即可断定某条数据是否缺失。

布隆过滤器的内部依赖于哈希算法，当检测某一条数据是否见过时，有一定概率出现假阳性（False Positive），但一定不会出现假阴性（False Negative）。也就是说，当布隆过滤器认为一条数据出现过，那么该条数据很可能出现过；但如果布隆过滤器认为一条数据没出现过，那么该条数据一定没出现过。这种特性刚好与此处的需求相契合，即检验某条数据是否缺失。

文件合并（Compaction）

随着数据的不断积累，SSTable 将会产生越来越多的 segment，导致查询时扫描文件的 IO 次数增多，效率降低，因此需要有一种机制来控制 segment 的数量。对此，LSM tree 会定期执行文件合并（compaction）操作，将多个 segment 合并成一个较大的 segment，随后将旧的 segment 清理掉。由于每个 segment 内部的数据都是有序的，合并过程类似于归并排序，效率很高，只需要O(n)的时间复杂度。

在上图的示例中，segment 1 和 2 中都存在 key 为 dog 的数据，这时应该以最新的 segment 为准，因此合并后的值取 84 而不是 52，这实现了类似于字典/HashMap 中“覆盖写”的语义。

删除数据

现在你已经了解了 LSM tree 读写数据的方式，那么如何删除数据呢？如果是在内存中，删除某块数据通常是将它的引用指向 NULL，那么这块内存就会被回收。但现在的情况是，数据已经存储在硬盘中，要从一个 segment 文件中间抹除一段数据必须要覆写其之后的所有内容，这个成本非常高。LSM tree 所采用的做法是设计一个特殊的标志位，称为 tombstone（墓碑），删除一条数据就是把它的 value 置为墓碑，如下图所示：

这个例子展示了删除 segment 2 中的 dog 之后的效果。注意，此时 segment 1 中仍然保留着 dog 的旧数据，如果我们查询 dog，那么应该返回空，而不是 52。因此，删除操作的本质是覆盖写，而不是清除一条数据，这一点初看起来不太符合常识。墓碑会在 compact 操作中被清理掉，于是置为墓碑的数据在新的 segment 中将不复存在。

LSM tree 与 B tree 的对比

主流的关系型数据库均以 B/B+ tree 作为其构建索引的数据结构，这是因为 B tree 提供了理论上最高的查询效率 - O(logn)。但对查询性能的追求也造成了 B tree 的相应缺点，即每次插入或删除一条数据时，均需要更新索引，从而造成一次磁盘 IO。这种特性决定了 B tree 只适用于频繁读、较少写的场景。如果在频繁写的场景下，将造成大量的磁盘 IO，从而导致性能骤降。这种应用场景在传统的关系型数据库中比较常见。

而 LSM tree 则避免了频繁写场景下的磁盘 IO 开销，尽管其查询效率无法达到理想的 ，但依然非常快，可以接受。所以从本质上来说，LSM tree 相当于牺牲了一部分查询性能，换取了可观的写入性能。这对于 key-value 型或日志型数据库是非常重要的。

总结

LSM tree 存储引擎的工作原理包含以下几个要点：

1. 写数据时，首先将数据缓存到内存中的一个有序树结构中（称为 memtable）。同时触发相关结构的更新，例如布隆过滤器、稀疏索引。
2. 当 memtable 积累到足够大时，会一次性写入磁盘中，生成一个内部有序的 segment 文件。该过程为连续写，因此效率极高。
3. 进行查询时，首先检查布隆过滤器。如果布隆过滤器报告数据不存在，则直接返回不存在。否则，按照从新到老的顺序依次查询每个 segment。
4. 在查询每个 segment 时，首先使用二分搜索检索对应的稀疏索引，找到数据所在的 offset 范围。然后读取磁盘上该范围内的数据，再次进行二分查找并获得结果。
5. 对于大量的 segment 文件，定期在后台执行 compaction 操作，将多个文件合并为更大的文件，以保证查询效率不衰减。

参考：

• Understanding LSM Trees: What Powers Write-Heavy Databases. Braden Groom
• Log Structured Merge Trees. Ben Stopford
• The Pathologies of Big Data. ACM

 Actionable Items

It takes time to make the article to be readable. I also learn a lot about memtable and SSTable. The example is very helpful for me to understand how BigTable is designed to use LSM similar design. 

Follow up 

March 28, 2022

Google those keywords:

1. LSM tree 存储引擎的工作原理
2. 将数据缓存到内存中的一个有序树结构中（称为 memtable）
3. 当 memtable 积累到足够大时，会一次性写入磁盘中，生成一个内部有序的 segment 文件。
4. 布隆过滤器、稀疏索引, bloom filter, sparse index 
5. Segment - 
6. Binary search - sparse index - offset range - read disk date - binary search and find result
7. 对于大量的 segment 文件，定期在后台执行 compaction 操作，将多个文件合并为更大的文件，以保证查询效率不衰减。
8.  key-value 型或日志型数据库所依赖的核心数据结构
9. LSM tree (log-structured merge-tree) 
10. BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB
11. 稀疏索引 sparse index | 全量索引（dense index）| March 28, 2022 review 
12. Segment compaction | tombstone | How to delete the key? 
13. LSM tree 的所有写操作均为连续写，因此效率非常高。但由于外部数据是无序到来的，如果无脑连续写入到 segment，显然是不能保证顺序的。对此，LSM tree 会在内存中构造一个有序数据结构（称为 memtable），例如红黑树。每条新到达的数据都插入到该红黑树中，从而始终保持数据有序。当写入的数据量达到一定阈值时，将触发红黑树的 flush 操作，把所有排好序的数据一次性写入到硬盘中（该过程为连续写），生成一个新的 segment。而之后红黑树便从零开始下一轮积攒数据的过程。
14. LSM tree -> segment -> memtable - using red black tree -> Write once for a block into hard disk/ SSDisk
15. Write -> a lot of write -> no order -> memtable -> SStable -> segment -> GFS data structure -> BigTable data structure