日志合并结构树(LSM)的原理与实现

对于日志合并结构树(Log-Structured Merge-Tree)的说明主要来自于Patrick O'Neil等人在论文《The Log-Structured Merge Tree》中的介绍。

翻译参考：

分布式系统 The Log-Structured Merge-Tree(译)

基本概念

LSM树并不是树结构，而是由两个或更多的类树组件组成的集合。

组成部分

LSM树一般至少由两个部分组成：

一个较小的位于内存的组件，就是上图中的C0 tree(or C0 component)
一个较大的位于磁盘的组件，就是上图中的C1 tree((or C1 component)

尽管C1树常驻磁盘，但它的常被访问的磁盘页会被保留在内存中(如下图)，所以也可以看做是常驻内存里的。

读写操作

历史记录表的数据每生成一行新记录流程如下：

首先向顺序日志文件中写一条用于恢复这次插入行为的日志记录(WAL,write ahead log)
该行数据的索引被插入到常驻内存的 C0 树中
会适时地将这些C0树上的数据迁移到磁盘上的C1树中
每个索引的搜索过程都是先C0后C1

所以实质上在两个组成部分外还有一个组成部分，就是行为日志。行为日志可以用来获取实际数据以及进行崩溃恢复。而LSM中的L(log)指的就是这个部分。

C1树结构

上述C0树写入是无IO开销的，但是C0位于内存，成本远高于磁盘，这就需要有一种高效的刷盘方式到C1。

为了实现这个目的，在当C0树因插入操作而达到接近某个上限的阈值大小时，就会启动一个滚动合并(rolling merge)过程，来将某些连续的记录段从C0树中删除，并merge到磁盘上的C1树中。

C1树具有一个类似于B-树的目录结构，但是它是为顺序性的磁盘访问优化过的，所有的节点都是100%满的，同时为了有效利用磁盘，做了以下优化:

在根节点之下的所有的单页节点都会被打包(pack)放到连续的多页块(multi-page block)上。对于滚动合并和较长的区间检索的情况将会使用多页块 I/O，而在匹配性的查找中会使用单页节点以最小化缓存需求。对于根节点之外的节点使用256Kbytes的多页块大小，根节点根据定义通常都只是单个的页面。

滚动合并

滚动合并行为是一系列的合并步骤：

先读取包含C1树的叶节点的多页块，这会使得C1中的一系列节点条目驻留到缓存
然后每次合并都会去读取已经被缓存的C1树的一个磁盘页大小的叶节点
将那些来自于叶节点的记录与从C0树中拿到的叶节点级的记录进行合并，这样就减少了C0的大小
合并完成后，会在C1树中创建了一个新的合并好的叶子节点

合并前被读取到缓存中叶节点多页块被称为清空块(emptying block)，新的叶节点被写入另一个不同的已缓存的多页块，被称为填充块(filling block)。当填充块被C1中新合并的节点填满后，该block会被写入到磁盘上的新空闲区域中，这样老的块就不会被覆盖，在发生crash时就可以进行恢复。

当合并步骤完成后，C1中的老的叶节点就会变为无效状态，之后会从C1目录结构中被删除。通常，每次都是C1中的最左边的叶节点记录参与merge，因为如果老的叶节点都是空的那么合并步骤也就不会产生新的节点。

为了减少恢复时的重构时间，merge过程需要进行周期性的checkpoints，强制将缓存信息写入磁盘。

LSM树组件创建流程

C0树结构

与C1树不同，C0树不一定要具有一个类B-树的结构，因为C0树永不会位于磁盘上，它的节点可以具有任意大小，没有必要让它与磁盘页面大小保持一致，因此我们就没有必要为了最小化树的深度而牺牲CPU的效率。这样，一个2-3树或者是AVL树就可以作为C0树使用的一个数据结构。

创建C1树

当C0首次增长到它的阈值大小时，最左边的一系列记录将会从C0中删除(这应是以批量处理的模式完成，而不是一次一条记录)，
然后被重新组织成C1中的一个100%满的叶子节点。
所有的叶节点会按照从左到右的顺序放到缓存中的一个multi-page block的初始页面中，直到该block填满为止
之后，该block会被写到磁盘中，成为C1树的磁盘上的叶级存储的第一部分
随着后续的叶节点的加入，C1树会创建出一个目录节点结构
C1树的上级目录节点被存放在独立的多页块缓存(multi-page block buffers)或者是单页面缓存中，无论存在哪里，都是为了更好地利用内存和磁盘；目录节点中的记录包含一些分隔点，通过这些分隔点可以将用户访问导引到单个的单页节点中。通过这种指向叶级节点的single-page索引节点可以提供高效的精确匹配访问，避免了多页块的读取，这样就最小化了缓存需求。这样在进行滚动合并或者按range检索时才会读写多页块，对于索引化的查询(精确匹配)访问则读写节点。
在一系列叶级节点blocks被写出时，那些由C1的目录节点组成的还未满的多页块可以保留在缓存中。在如下情况下，C1的目录节点会被强制写入磁盘：

由目录节点组成的某个多页块被填满了
根节点发生了分裂，增加了C1树的深度（成了一个大于2的深度）
执行Checkpoint
对于第一种情况，只有被填满的那个block会被写出到磁盘。对于后两个情况，所有的多页块缓存和目录节点buffers都会被flush到磁盘。

当C0树的最右边的叶节点记录首次被写出到C1树后，整个过程就又会从两个树的最左端开始，只是从现在开始，需要先把C1中的叶子级别的多页块读入到buffer，然后与C0树中的记录进行merge，产生出需要写入到磁盘的新的C1的叶节点多页块。

如图所示。J-1层结点包含连续的指向J层结点（node1，node2，...nodeK）的指针（P1，P2，...，PK）和分割指针的键（S1，S2，...，SK-1）。J层结点连续存放在多页块的K页中，如果J层的两个结点存放于同一个多页块中，那这两个结点的键值之间的所有结点也存放在多页块中。M是多页块分割的标记，表示直到下一个M标记或空结点之内的所有后续结点都存放在同一个多页块中。M中包含了多页块开始的硬盘页号和多页块中结点的数量。树根始终是以一个单页存储的。可以看出多页块可用于范围检索，而多页块中结点可用于精确的键值匹配的检索。

滚动合并

在滚动合并时，C0和C1都有一个指向相等键值的游标，往复地穿越在C0和C1的键值对上，不断地从C0中取出数据放入到磁盘上的C1中。从根结点到达这个位置的路径将C1上所有正在进行滚动合并的多页块分成两部分。一部分游标还未到达的结点，合并时读入清空块，另一部分是填充块，是游标已经走过的结点，即滚动合并的结果。这样的过程如下：

从C1中读入未合并的叶子结点，存储于内存的清空块中；
从C0中读取叶子结点，并与清空块中的叶子结点进行合并排序；
将合并排序的结果写入填充块中，并从C0中删除用于合并排序的旧叶子结点；
不断地重复步骤2和3，当填充块被合并排序的结果填满时，将填充块追加到硬盘的新位置，并从C1中删除用于合并排序的旧叶子结点，当清空块被全部读取完时，再从C1中读入未合并的叶子结点；
当C0和C1的所有叶子节点都被读入内存进行合并，并产生新的叶子结点之后，C0和C1的一次滚动合并就结束了。

由于C0存储在内存之中，所以C0可以保留最近插入或最常访问的那些数据，以提高访问速率并降低I/O操作的次数。C1的旧多页块可用于崩溃恢复，所以为了不覆盖旧多页块，滚动合并产生的新多页块将被写入硬盘的新空。一般来说，每次合并之后，会剩下一些不满的没有写入硬盘的填充块，没有填入填充块的叶子结点，这些结点会和它们的目录结点一样暂时缓存在内存中，等待下次滚动合并时，再写入相应的填充块或者填满并写入硬盘。

与C0和C1的滚动合并相比，硬盘内的相邻部件Ci-1和Ci之间的滚动合并多了一个清空块和填充块。这是因为Ci-1和Ci都存储在硬盘之中，合并时需要先将Ci-1和Ci的清空块和填充块存入内存，合并的过程与C0和C1的相同，但Ci-1不会将所有的条目都拿去合并，而是会保留一部分条目（例如新插入的那部分条目）到Ci-1的填充块。如下图所示：

当前正在进行滚动合并的结点被加锁（红圈圈住的点），写保护。蓝色的点表示游标，绿色的点表示游标未到达的结点，树上折线表示从树根到游标的路径。

索引

搜索

当一个需要立刻返回的精确匹配查询或是范围查询在LSM树的索引上执行时，会先在C0树执行搜索值，然后搜C1树。这暗含着少许额外的CPU开销(相对于B树来说)，因为分别去两棵树目录进行搜索。对于那些具有超过两个组件的LSM-tree来说，还会有IO上的开销。

如上图，考虑多个组件的LSM树，拥有C0, C1, C2 … Ck，这样一个递增的索引树结构。其中C0是驻留在内存的，而且他组件都在磁盘。这种情况下，每当Ci-1 条目达到阈值时，每个(Ci-1,Ci)之间的异步滚动合并过程会从较小的组件中移动条目到较大的组件。这个结论很重要，务必牢记。

LSM有一个规则，即为了保证LSM中所有条目都被检查到，就必须让每个精确匹配或范围查找要访问每个Ci组件的索引结构。然而，有一些可能的优化方式，可使得此搜索范围限制在组件的初始子集
如果记录的生成逻辑就能保证索引唯一性，比如时间戳，那么在较小的一个Ci组件内搜索到结果就可以直接停止搜索直接返回。
再比如，搜索条件中使用了最近的时间戳，我们可以限制搜索范围为那些还没有移动到最大组件的记录所处的序号小的组件上。当合并游标在（Ci，Ci + 1）对中循环徘徊时，我们通常有理由保留Ci中那些最近插入的条目（比如在最近τi秒内），而只允许那些较旧的条目移动到Ci+1中。
在最频繁的查询指向最近插入的值的这种场景中，许多搜索都可在C0树中就完成，这样就使得C0树完全发挥了了自己的内存缓存价值。这是十分重要的性能优化策略。举个例子，被用作短期事务UNDO日志索引，在中止事件中被访问，在创建这些索引后会有大比例是访问短期内的数据，所以我们可以预期大多数这样的索引会驻留在内存中。
通过跟踪每个事务的开始时间，我们可以保证在最后的τ0秒内启动事务的所有日志，例如，将在组件C0中找到，而无需搜索位于磁盘的其他LSM树组件。

删除

需要指出的是删除操作可以像插入操作那样享受到延迟和批量处理带来的好处。

当某个被索引的行被删除时，如果该记录在C0树中对应的位置上不存在，那么可以将一个删除标记记录(delete node entry)放到该位置，该标记记录也是通过相同的key值进行索引，同时指出将要被删除的记录的Row ID(RID)。

实际的删除可以在后面的rolling merge过程中碰到实际的那个索引entry时执行：也就是说delete node entry会在merge过程中移到更大的组件中，同时当碰到相关联的那个entry，就将其清除。与此同时，查询请求也必须在通过该删除标记时进行过滤，以避免返回一个已经被删除的记录。该过滤很容易进行，因为删除标记就是位于它所标识的那个entry所应在的位置上，同时在很多情况下，这种过滤还起到了减少判定记录是否被删除所需的开销。

更新

对于任何应用来说，那些会导致索引值发生变化的更新都是不平凡的，但是这样的更新却可以被LSM-tree一招化解，通过将该更新操作看做是一个删除操作+一个插入操作

并发

多组件原理

回顾下前面的内容，考虑K+1个组件的LSM树，拥有C0, C1, C2 … Ck，这样一个递增的索引树结构。其中C0是驻留在内存的，而且他组件都在磁盘。这种情况下，每当Ci-1 条目数量达到阈值时，每个(Ci-1,Ci)之间的异步滚动合并过程会从较小的组件中移动条目到较大的组件。每个驻留磁盘组件都是由磁盘页大小的节点按B树类型结构组成，此外根节点下的各层的节点都按照key的顺序排列并打包放置到多页块中。LSM树上层的目录信息可以指引单个页节点访问，还能指明哪些节点位于该多页块上，这样的好处是使得可以一次性执行对这样的块的读取或写入。

等值匹配时，一个基于此盘的Ci可被单独驻留在单页内存缓存中，也可被包含在多页块的缓存中。作为大范围搜索或是滚动合并的游标穿过块高频访问的结果，一个多页缓存会被缓存到内存。

LSM并发三大问题

无论如何，Ci组件的所有非锁定节点都可以随时进行访问目录查找，并且磁盘访问将执行旁路以查找内存中的任何节点，即使该节点是多页块一部分，参与滚动合并。总的来说，LSM树的并发访问必须解决以下三种物理冲突：

一个查找操作不应该访问一个基于磁盘组件的同时，另外一个进程正在滚动合并且正在修改该节点的内容。（读写不能并发）
当另外的进程正在更改C0某部分以执行滚动合并到C1的同时，在C0组件中查找或插入不应访问C0树的相同部分。（读和删除合并不能并发）
用来将数据从Ci-1移动到Ci的游标有时候需要穿越过用来将数据从Ci移动到Ci+1的游标，因为从Ci-1的数据导出速度总是至少与Ci数据导出数据相当，这就意味着Ci-1的游标运转速度更快。无论采用何种并发方法，都必须允许上述情况发生，也就是说导出数据到Ci的进程不会因数据从Ci导出的进程而阻塞。

基于磁盘组件合并时的并发

LSM树中用于并发控制访问基于磁盘的组件而导致冲突，所以加锁的单位是树的节点：

正在因滚动合并被修改的节点会被加上写锁
正在因搜索而读取的节点会被加上读锁
为了防止死锁，设计了目录锁相关方法

而C0树采用的锁实现方式具体依据是采用的数据结构。

例如，在 2-3树的情况下，我们可以用写锁锁住2-3树的目录节点一个子树，该节点包含要合并到C1节点时受影响范围内的所有条目;
同时，查找操作会用读锁锁定那些处于搜索路径上的2-3树的所有节点。

锁的释放：

读锁

一旦叶节点上的条目被扫描完了，就会释放

写锁

滚动游标使用的写锁会在合并到更大的组件后被释放

为了提高并发，前面章节提到过的C1树的empty block和filling block都会包含整数个C1树中的页大小的节点，并驻留在内存。在合并重组节点时，这些节点会被加上写锁，以阻止对这些记录的其他类型并发访问。

C0到C1之时的并发

前面讨论的都是基于磁盘的组件间merger时的并发情况，现在说说C0到C1的合并时的并发情况。与其他合并步骤相同，CPU应该专注于合并任务，所以其他访问会被排他的写锁拒绝，当然这个时间会尽可能短。那些会被合并的C0条目应该被提前计算、提前加写锁。除此之外，CPU时间还会由于C0组件以批量的形式删除条目节省时间，而不是每次单独删除而尝试再平衡；C0树可以在整个合并步骤完成后被完全的平衡。

LSM恢复

检查点

在新条目插入到C0后，当C0与C1进行滚动合并时，某些条目将从C0转移到更大的组件中。由于滚动合并发生在内存缓存的多页块中，所以只有当条目真正写入硬盘时，滚动合并的成果才会真正生效。然而滚动合并时可能就会发生系统故障，进而使得内存数据丢失。为了能有效地进行系统恢复，在LSM树的日常使用中，需要记录一些用以恢复数据的日志。然而与以往数据库中的日志不同的是，日志中只需要要记录数据插入的事务。简单地说，这些日志只包含了被插入数据的行的号码及插入的域和值。

LSM树在记日志时设置检查点（checkpoint）以恢复某一时刻的LSM-tree。当需要在时刻T0设置检查点时：

完成所有组件的当前正在进行的合并，这样结点上的锁就会被释放；
将所有新条目的插入操作以及滚动合并推迟至检查点设置完成之后；
将C0写入硬盘中的一个已知的位置；此后对C0的插入操作可以开始，但是合并操作还要继续等待；
将硬盘中的所有部件（C1~CK）在内存中缓存的结点写入硬盘；
向日志中写入一条特殊的检查点日志。
检查点日志的内容包括：

T0时刻最后一个插入的已索引的行的日志序列号（Log Sequence Number，LSN0）；
硬盘中的所有部件的根在硬盘中的地址；
各个部件的合并游标；
新多页块动态分配的当前信息。在以后的恢复中，硬盘存储的动态分配算法将使用此信息判别哪些多页块是可用的。

一旦检查点的信息设置完毕，就可以开始执行被推迟的新条目的插入操作了。由于后续合并操作中向硬盘写入多页块时，会将信息写入硬盘中的新位置，所以检查点的信息不会被消除。只有当后续检查点使得过期的多页块作废时，检查点的信息才会被废弃。

恢复

当系统崩溃后重启进行恢复时，需要进行如下操作：

在日志中定位一个检查点；
将之前写入硬盘的C0和其它部件在内存中缓存的多页块加载到内存中；
将日志中在LSN0之后的部分读入内存，执行其中索引条目的插入操作；
读取检查点日志中硬盘部件（C1~CK）的根的位置和合并游标，启动滚动合并，覆盖检查点之后的多页块；
当检查点之后的所有新索引条目都已插入至LSM-tree且被索引后，恢复即完成。

这一恢复措施的唯一的一个缺点就是恢复的时间可能会比较长，但通常这并不严重。因为内存中的数据可以很快地写入硬盘。当两个相邻的部件进行滚动合并时，新产生的结点将会写入到硬盘中的新位置。这样在将合并产生的结点写入硬盘时，上层结点中指向该结点的指针需要更新为结点的新位置。当正在进行滚动合并，却临时需要设置检查点时，加载进内存的多页块和目录结点都会写入到硬盘中新的位置。这样，在高层的目录结点中指向这些结点的指针同样需要立即更新为硬盘中的新地址。在恢复的过程中需要注意的是目录结点的更新。

更进一步，当使用检查点进行恢复时，滚动合并所需的所有的多页块都会从硬盘重新读回内存，由于所有的多页块的新位置较之设置检查点时的旧位置都发生了改变，这样所有目录结点的指针都需要更新。这听起来似乎是一大笔性能开销，但这些多页块其实都已加载到内存里了，所以没有I/O开销。若要使得恢复的时间不超过几分钟，那么可以每隔几分钟的I/O操作就设置一次检查点。

RokcsDB

LSM Tree-Based存储引擎的compaction策略

执行写操作时，先同时写memtable与预写日志WAL。memtable写满后会自动转换成不可变的（immutable）memtable，并flush到磁盘，形成L0级sstable文件。sstable即有序字符串表（sorted string table），其内部存储的数据是按key来排序的，后文将其简称为SST。
执行读操作时，会首先读取内存中的数据（根据局部性原理，刚写入的数据很有可能被马上读取），即active memtable→immutable memtable→block cache。如果内存无法命中，就会遍历L0层sstable来查找。如果仍未命中，就通过二分查找法在L1层及以上的sstable来定位对应的key。
随着sstable的不断写入，系统打开的文件就会越来越多，并且对于同一个key积累的数据改变（更新、删除）操作也就越多。由于sstable是不可变的，为了减少文件数并及时清理无效数据，就要进行compaction操作，将多个key区间有重合的sstable进行合并。

Rocksdb中文网:文件结构

磁盘上的文件被分成多层进行组织。我们叫他们Level-1, Level-2，等等，或者简单的L1,L2，等等。一个特殊的层，Level-0(L0)，会包含刚从内存memtable落盘的数据。
每一层（除了Level0）都是一个排序结果，因为每个SST文件中的key都是排好序的
所有非0层都有目标大小。压缩的目标是限制这些层的数据大小。大小目标通常是指数增加。
当L0的文件数量到达level0_file_num_compaction_trigger，压缩(compaction)就会被触发，L0的文件会被合并进L1。
如果结果仍旧超出下一层的目标大小，我们重复操作 —— 选一个文件然后把它合并到下一层

level_compaction_dynamic_level_bytes
如果level_compaction_dynamic_level_bytes为false，那么层目标这样决定： L1的目标是max_bytes_for_level_base，然后 Target_Size(Ln+1) = Target_Size(Ln) * max_bytes_for_level_multiplier * max_bytes_for_level_multiplier_additional[n]。max_bytes_for_level_multiplier_additional默认全为1。
level_compaction_dynamic_level_bytes为true:最后一层的目标大小(层数-1)总是层的实际大小。剩下的Target_Size(Ln-1) = Target_Size(Ln) / max_bytes_for_level_multiplier。如果哪一层的大小小于 max_bytes_for_level_base / max_bytes_for_level_multiplier，我们不会填充他。这些层会保持为空，所有L0的压缩会跳过这些层，直接到第一个符合大小的层。

TTL

如果没有人更新一个文件中key，那么这个文件将不会进入压缩流程，而这个文件就会存活很久。例如，在某些特定场景，key会被“软删除” —— 把数值设置为空而不是直接使用Delete删除。这个“已经删除”的key范围可能不会有任何新的写入了，这样，这个数据就会在LSM里面待很长时间，浪费空间。

一个动态ttl列族选项被用于解决这个问题。文件（或者说，数据）老于TTL的数据在没有其他后台任务的时候会被定时压缩。这会让数据进入常规的压缩流程，摆脱无用的老数据。对于所有不是最底层的，比ttl要新的数据，以及所有在最底层老于ttl的数据，这还有一个（好的）副作用。注意这会导致更多的写因为RocksDB会调度更多的压缩。

The Pathologies of Big Data