Log-Structured Merge-Tree (LSM-Tree)

1、简介

LSM Tree 主要是针对文件存储系统的写入/删除速度的瓶颈问题而提出的结构，在HBase、Cassandra、LevelDB中被应用。文件存储系统除了考虑I/O效率之外，还需要考虑到存储成本的问题。在存储系统相关的论文中[1]提到，用户上传的照片很少被改动，对于那些修改的数据并不是更新到原始的位置，而是在新的位置存放这个数据新的版本。所以把那些旧的数据存放在write-once的存储介质上是节省成本的一种方法。而在另外一篇关于分布式缓存的论文中也提到了无论对数据的请求的分布如何，缓存系统缓存最频繁访问的 O ( n l o g n ) O(nlog n) O(nlogn)个对象就可以使得 n n n个存储节点负载均衡[2]。所以将一小部分数据放在内存，而大部分的数据放在磁盘中可以比较好的平衡存储系统效率与存储成本。LSM Tree中的 C 0 C_0 C0​树存放在内存中，而 C 1 ∼ C k C_1 \sim C_k C1​∼Ck​则存放在磁盘上。并且将对树中数据的修改延迟批量化处理，从而避免大量的随机的修改操作带来的性能上的下降。在LSM Tree 中，对于那些最不频繁访问的数据则不断的从 C 0 C_0 C0​移动到 C 1 C_1 C1​直到 C k C_k Ck​。 C i C_i Ci​有大小的限制，当 C i C_i Ci​的数据溢出后，数据归并到 C i + 1 C_{i+1} Ci+1​中，以此类推。

2、五分钟规则(Five Minute Rule)

这一理论最早由Jim Gray 和 Gianfranco Putzolu在1985年提出。该规则描述了什么数据应该放在内存或者是磁盘上。该规则的描述是，对于随机访问频率不少于每五分钟一次的页面应该被缓存。此外还有另外一个一分钟规则为缓存那些访问频率不少于每一分钟一次的页面。当然，这里的五分钟与一分钟是基于当时的内存与磁盘的开销的。随着目前内存成本的降低以及SSD等新的存储设备的出现，规则里面的具体时间会发生变化。

3、包含两个树结构的LSM-Tree (Two Component LSM-Tree)

LSM-Tree可以包含两个或者是更多的树结构，下面是包含两个树结构的LSM-Tree的示意图。

其中较小的 C 0 C_0 C0​树完全驻留在内存中，而较大的 C 1 C_1 C1​树保存在磁盘上。当然 C 1 C_1 C1​不是完全保存在磁盘上的， C 1 C_1 C1​中经常访问的节点是保存在内存中的。由于 C 0 C_0 C0​树是在内存中的，因此不一定非要使用类似于B树的结构，使用平衡二叉树也是可以的。而 C 1 C_1 C1​由于是放在磁盘上的，因此需要选择合适的结构并进行一些优化。

对于日志系统，当一条日志被写入后，该条日志记录的索引项被插入到 C 0 C_0 C0​树中，之后它会被迁移到 C 1 C_1 C1​树中。迁移操作是发生在当 C 0 C_0 C0​的大小超过了阈值，之后会进行一个滚动合并(rolling merge)的过程。该过程会将 C 0 C_0 C0​中连续的索引项从 C 0 C_0 C0​中删除并合并到 C 1 C_1 C1​中。对于该索引项的查找，都要首先查看 C 0 C_0 C0​树，之后再查看 C 1 C_1 C1​树。

C 1 C_1 C1​树相比于B树，对连续的I/O操作进行了优化。在 C 1 C_1 C1​树的每一层中，邻近的节点在磁盘上的位置也是相邻的。多页面I/O(Multi-page block I/O)用于提供在滚动合并过程以及检索过程中的优化(减少了查找与旋转的延迟)。滚动合并包含多个合并的步骤。使用多页面I/O读取 C 1 C_1 C1​树最底层索引项，每个合并操作首先从已读取的索引项块中读取一个磁盘页面的索引项，之后和 C 0 C_0 C0​中读取的最底层的索引项合并，生成的新节点作为 C 1 C_1 C1​树的叶子节点。这种将 C 0 C_0 C0​中的多个叶子节点的索引项合并到 C 1 C_1 C1​树中，相比于B树对于每个索引项都需要一次读取一次写入要更加高效。

在上面的这个过程中，在合并的操作之前，缓存多个页面索引项的块称为emptying block，而合并操作之后新生成的节点首先被写入到一个称为filling block的缓冲区。当filling block填充满了之后，所缓冲 C 1 C_1 C1​的新的叶子节点被写入到磁盘上的空闲区域。下图是合并操作的示意图。

如上图所示，合并 C 1 C_1 C1​与 C 0 C_0 C0​中的节点是连续的，并且写入到新的位置，并且合并之前的块并没有被覆盖掉，这样可以用于故障恢复。并且，为了减少恢复重建过程所需要的时间，在合并过程中会定时地保存检查点(checkpoint)，将缓存的信息强制的写入到磁盘上。

4、LSM树索引查找

由于LSM包含多个树结构，并且根据各个树上数据的新旧程度，查找操作会首先从 C 0 C_0 C0​开始，之后是 C 1 C_1 C1​。因此，相比于B树结构会更耗时一些。由于 C 0 C_0 C0​是在内存中的，所以将那些最近一段时间内(比如 τ i \tau_i τi​ 秒内)插入的索引项保存下来可以减少查找到磁盘上的次数。通过对每个事务(transaction)的开始时间追踪，可以保证在最近的 τ 0 \tau_0 τ0​秒内开始的事务所产生的日志都可以通过 C 0 C_0 C0​树中的索引项查找到。

5、LSM树的删除、更新以及长延时的查询

与前面的插入操作一样，对于LSM树的删除操作也可以采用延迟与批量化的方式来进行优化。可以将对LSM树中索引项的删除延迟到滚动合并过程执行，并且在此期间，需要对查询操作进行筛选，确保不会查询到将要被删除的索引项节点。而对于更新操作，如果把它看做是删除-插入操作的组合，那么同样可以采用这种延迟的方式。此外，还有两种比较高效的索引修改的方式。其中一种是预测删除通过简单的预测假设来进行批量化的删除操作。比如假设超过20天的索引项会被删除，则 C K C_{K} CK​树中超过20天的索引项可以在滚动合并的过程中被批量的删除掉。另外一种是长延时查询，这种方式将查询项(find note entry)插入到 C 0 C_0 C0​树中，之后它会在 C i C_i Ci​与 C i + 1 C_{i+1} Ci+1​迁移的过程中做查询操作，直到当这个查询项被迁移到包含相关索引项的最大的 C i C_i Ci​时结束。

6、磁盘模型

LSM树相比于B树的一大优势在于极大地减少了I/O开销，这一优势有一部分是由于采用多页面的块结构(multi-page block)带来的。

原论文中对内存以及磁盘的代价进行了如下的符号定义：

• C O S T d COST_d COSTd​: 磁盘存储1MB数据的代价；
• C O S T m COST_m COSTm​: 内存存储1MB数据的代价；
• C O S T P COST_P COSTP​: 对于随机页面访问，磁盘提供每秒1个页面I/O速度的代价；
• C O S T π COST_\pi COSTπ​: multi-page block I/O 提供每秒1个页面I/O速度的代价

对于需要 S S S MB数据存储以及每秒 H H H 个随机页面的I/O，则总的代价为 C O S T D = max ⁡ ( S ⋅ C O S T d , H ⋅ C O S T P ) COST_D=\max(S\cdot COST_d, H\cdot COST_P) COSTD​=max(S⋅COSTd​,H⋅COSTP​)。为了使得随机I/O的速度更快，在内存中建立一个缓冲区，则增加这个缓冲区的代价为 C O S T B = S ⋅ C O S T m + S ⋅ C O S T d COST_B = S\cdot COST_{m}+S\cdot COST_d COSTB​=S⋅COSTm​+S⋅COSTd​。那么最终访问这些数据的最小代价为 C O S T T O T = min ⁡ ( max ⁡ ( S ⋅ C O S T d , H ⋅ C O S T P ) , S ⋅ C O S T m + S ⋅ C O S T d ) COST_{TOT}=\min(\max(S\cdot COST_d, H\cdot COST_P), S\cdot COST_m+ S\cdot COST_d) COSTTOT​=min(max(S⋅COSTd​,H⋅COSTP​),S⋅COSTm​+S⋅COSTd​)。在 C O S T T O T COST_{TOT} COSTTOT​的变化曲线上可以分为三段。当数据量 S S S比较小的时候， C O S T T O T COST_{TOT} COSTTOT​的值取决于磁盘的存储代价 S ⋅ C O S T d S\cdot COST_d S⋅COSTd​。随着 H / S H/S H/S的不断增加，即单位数据的访问频率越来越高， C O S T T O T COST_{TOT} COSTTOT​取决于磁盘I/O的代价 H ⋅ C O S T P H\cdot COST_P H⋅COSTP​。最终，在图中的第三个阶段，即前面提到的五分钟规则所确定的那个点——决定把数据放在磁盘上还是内存中，此时 C O S T T O T COST_{TOT} COSTTOT​取决于 S ⋅ C O S T m + S ⋅ C O S T d S\cdot COST_m+S\cdot COST_d S⋅COSTm​+S⋅COSTd​。

7、LSM树与B树的I/O代价对比

7.1、索引项插入代价

对于B树，假设新插入的索引项的位置可能在B树最底层的随机位置，则每次插入索引项都需要从根节点逐层向下确定位置，并且这种随机使得无法通过缓存来避免每次自顶向下的搜索过程。根据[4]中定义在B树中的随机的键值对查找，平均未在缓冲区中找到的页面的个数称为B树的有效深度(effective depth)，表示为 D e D_e De​。在B树的插入过程中，对B树底层的叶子节点对应的一个页面进行修改操作，之后会有一个脏页写回到磁盘的操作。这样B树的插入操作的代价为 C O S T B − i n s = C O S T P ⋅ ( D e + 1 ) COST_{B-ins}=COST_P\cdot (D_e+1) COSTB−ins​=COSTP​⋅(De​+1)。

对于LSM树，在前面提到相比于B树的一个优势在于批量化的操作。因此，下面定义一个参数 M M M 表示平均 C 0 C_0 C0​中多少个索引项插入到 C 1 C_1 C1​中的一个页面叶节点。因此， M M M取决于索引项的大小以及 C 0 C_0 C0​和 C 1 C_1 C1​树的叶节点大小的比例。下面定义决定 M M M的一些参数：

• S e S_e Se​: 索引项的大小；
• S p S_p Sp​: 页面的大小;
• S 0 S_0 S0​: C 0 C_0 C0​叶节点层级的节点大小;
• S 1 S_1 S1​: C 1 C_1 C1​叶节点层级的节点大小

所以，一个页面可以保存的索引项的个数为 S p / S e S_p/S_e Sp​/Se​， C 0 C_0 C0​中保存的索引项的比例为 S 0 / ( S 0 + S 1 ) S_0/(S_0+S_1) S0​/(S0​+S1​)，所以可以得到计算 M M M的公式为 M = ( S p / S e ) ⋅ ( S 0 / ( S 0 + S 1 ) ) M=(S_p/S_e)\cdot (S_0/(S_0+S_1)) M=(Sp​/Se​)⋅(S0​/(S0​+S1​))。因此LSM树一个索引项插入的代价为 C O S T L S M − i n s = 2 ⋅ C O S T π / M COST_{LSM-ins}=2\cdot COST_\pi / M COSTLSM−ins​=2⋅COSTπ​/M。

最终，LSM树与B树的插入代价的比例为 C O S T L S M − i n s / C O S T B − i n s = 2 / ( D e + 1 ) ⋅ ( C O S T π / C O S T P ) ⋅ ( 1 / M ) COST_{LSM-ins}/COST_{B-ins}=2/(D_e+1)\cdot (COST_\pi/COST_P)\cdot (1/M) COSTLSM−ins​/COSTB−ins​=2/(De​+1)⋅(COSTπ​/COSTP​)⋅(1/M)。其中 D e D_e De​在原论文的AccountId||Timestamp的例子中是约等于2的，而 ( C O S T π / C O S T P ) (COST_\pi/COST_P) (COSTπ​/COSTP​)值小于1，而M是至少等于1的，所以LSM树的插入代价要比B树的代价更小。

以上的比较同样需要考虑到比较极端的情况，比如根据前面 M M M的等式中，假如 S 1 S_1 S1​远大于 S 0 S_0 S0​或者索引项特别大，则M的值是有可能小于1的。这种情况下在合并过程中，可能需要将 C 1 C_1 C1​中的多个页面加载到内存并写回。

8、包含多个树的LSM

在包含多个树结构的LSM中， C 0 C_0 C0​仍然是完全保存在内存中的，而 C 1 … C K C_1\dots C_K C1​…CK​是保存在磁盘上的，但是那些经常访问的页面是缓存在内存中的。滚动合并过程发生在邻近的 C i C_i Ci​与 C i + 1 C_{i+1} Ci+1​之间。在前面关于以包含两个树结构的LSM的插入代价的计算中，得到了一个涉及到 C 0 C_0 C0​与 C 1 C_1 C1​大小的一个公式，而对于包含多个树结构的LSM中，每个结构的大小限制如何确定，原论文中给出了分析。

首先定义LSM树的大小 S ( C i ) S(C_i) S(Ci​)为最底层叶节点包含的索引项的大小， S = ∑ i S i S=\sum_{i}S_i S=∑i​Si​。并假设对树 C 0 C_0 C0​的插入频率为一个相对稳定的值 R R R，且新插入的索引项最终都能够存活到被滚动合并到 C K C_K CK​，且每个树结构的大小都接近于当前分析确定的最大限制。设变量 r i r_i ri​表示相邻的两个树结构的大小的比例， r i = S i / S i − 1 r_i=S_i/S_{i-1} ri​=Si​/Si−1​。并且相邻的两个树结构 C i − 1 C_{i-1} Ci−1​与 C i C_i Ci​之间的滚动合并所需的I/O频率可以表示为关于 C 0 C_0 C0​插入频率以及 r i r_i ri​的函数 R R R。因此最小化每秒钟I/O的页面的个数 H H H也是在最小化磁盘的I/O的开销。在固定总的大小 S S S的情况下并不是很好求解，因为这使得 r i r_i ri​之间有依赖关系。所以，如果固定 S k S_k Sk​的大小，则最优的方案为 r i r_i ri​都等于一个值 r r r，即 S i = r i ⋅ S 0 S_i=r^i\cdot S_0 Si​=ri⋅S0​。

对于包含 K + 1 K+1 K+1个树结构的LSM，固定最大的树 C K C_K CK​的大小。设插入到 C 0 C_0 C0​的频率 R R R，最小的树结构大小为 S 0 S_0 S0​，则总的页面I/O的频率 H H H在所有的 r i = S i / S i − 1 r_i=S_i/S_{i-1} ri​=Si​/Si−1​都等于一个共同的值 r r r的时候是最小的。因此最终全部树结构的大小 S = S 0 + r ⋅ S 0 + … r K ⋅ S 0 S=S_0+r\cdot S_0+\dots r^{K}\cdot S_0 S=S0​+r⋅S0​+…rK⋅S0​。并且，总的页面I/O的频率 H = ( 2 R / S p ) ⋅ ( K ⋅ ( 1 + r ) − 1 / 2 ) H=(2R/S_p)\cdot (K\cdot (1+r)-1/2) H=(2R/Sp​)⋅(K⋅(1+r)−1/2)。

证明：

假设 C i − 1 C_{i-1} Ci−1​在磁盘上，则 C i − 1 C_{i-1} Ci−1​与 C i C_i Ci​之间的滚动合并过程需要涉及到从 C i − 1 C_{i-1} Ci−1​以及 C i C_i Ci​的读取以及写入。对于 C i − 1 C_{i-1} Ci−1​的I/O频率为 R / S p R/S_p R/Sp​，而对于 C i C_i Ci​的I/O频率为 r i ⋅ R / S p r_i\cdot R/S_p ri​⋅R/Sp​。因此，一轮滚动合并操作需要的I/O为 2 ⋅ ( r i + 1 ) ⋅ R / S p 2\cdot (r_i+1)\cdot R/S_p 2⋅(ri​+1)⋅R/Sp​。那么对整个LSM的I/O 频率 H = ( R / S p ) ( ( 2 ⋅ r 1 + 2 ) + ( 2 ⋅ r 2 + 2 ) + ⋯ + ( 2 ⋅ r K − 1 + 2 ) + ( 2 ⋅ r K + 1 ) ) = ( 2 R / S p ) ( ∑ 1 K r i + K − 1 2 ) H=(R/S_p)((2\cdot r_1+2)+(2\cdot r_2+2)+\dots+(2\cdot r_{K-1}+2)+(2\cdot r_K+1))=(2R/S_p)(\sum_1^{K}r_i+K-\frac{1}{2}) H=(R/Sp​)((2⋅r1​+2)+(2⋅r2​+2)+⋯+(2⋅rK−1​+2)+(2⋅rK​+1))=(2R/Sp​)(∑1K​ri​+K−21​)。在约束条件 Π i = 1 K r i = ( S k / S 0 ) = C \Pi_{i=1}^{K} r_i=(S_k/S_0)=C Πi=1K​ri​=(Sk​/S0​)=C限制下，对于最小化目标式子中 ∑ i = 1 K r i \sum_{i=1}^{K} r_i ∑i=1K​ri​，将 r K r_K rK​替换为 C ⋅ Π i = 1 K − 1 r i − 1 C\cdot \Pi_{i=1}^{K-1} r_i^{-1} C⋅Πi=1K−1​ri−1​。对式子中的每个 r j , j = 1 , … , K − 1 r_j, j=1,\dots, K-1 rj​,j=1,…,K−1求偏导并令其等于0，得到 0 = 1 − 1 r j C ⋅ Π i = 1 K − 1 r i − 1 0=1-\frac{1}{r_j}C\cdot \Pi_{i=1}^{K-1}r_i^{-1} 0=1−rj​1​C⋅Πi=1K−1​ri−1​，可以得到使得上述目标最小化时，每个 r i r_i ri​都等于 C ⋅ Π i = 1 K − 1 r i − 1 C\cdot \Pi_{i=1}^{K-1}r_i^{-1} C⋅Πi=1K−1​ri−1​即 C 1 / K C^{1/K} C1/K。

上面的这些证明过程是在固定最大的树结构的大小 S K S_K SK​的前提下计算得到的。而对于给定LSM中所有树结构总大小的前提下，如何确定每个树结构的大小，原论文中只给出了一个 r i r_i ri​之间的递推公式，没有证明过程。这个递推公式可以使用拉格朗日乘子法得到。

证明：

首先，问题的目标是最小化 H H H，而最小化 H H H就是需要最小化 ∑ i = 1 K r i \sum_{i=1}^{K}r_i ∑i=1K​ri​。并且所有的树大小总和需要等于 S S S。因此问题的目标为：

min ⁡ ∑ i = 1 K r i s . t .    ∑ i = 0 K S i = S \min \sum_{i=1}^{K} r_i\\ s.t.\ \ \sum_{i=0}^{K}S_i=S min∑i=1K​ri​s.t.  ∑i=0K​Si​=S

设函数 F = ∑ i = 1 K r i + λ ( ∑ i = 0 K S i − S ) = r 1 + r + 2 + ⋯ + r K + λ ( ∑ i = 0 K S i − S ) = r 1 + r 2 + ⋯ + r K + λ ( S 0 + r 1 S 0 + r 1 r 2 S 0 + ⋯ + r 1 r 2 … r K S 0 − S ) F=\sum_{i=1}^{K}r_i+\lambda (\sum_{i=0}^{K}S_i-S)\\ =r_1+r+2+\dots + r_K+\lambda (\sum_{i=0}^{K}S_i - S)\\ =r_1+r_2+\dots + r_K+\lambda (S_0+r_1S_0+r_1r_2S_0+\dots+r_1r_2\dots r_KS_0-S) F=∑i=1K​ri​+λ(∑i=0K​Si​−S)=r1​+r+2+⋯+rK​+λ(∑i=0K​Si​−S)=r1​+r2​+⋯+rK​+λ(S0​+r1​S0​+r1​r2​S0​+⋯+r1​r2​…rK​S0​−S)。

对 r k r_k rk​以及 r k − 1 r_{k-1} rk−1​求偏导并令其等于0.

∂ F ∂ r K = 0 ⇒ 1 + λ Π i = 1 K − 1 r i S 0 = 0 \frac{\partial F}{\partial r_K}=0 \Rightarrow 1+\lambda \Pi_{i=1}^{K-1}r_i S_0=0 ∂rK​∂F​=0⇒1+λΠi=1K−1​ri​S0​=0;

∂ F ∂ r K − 1 = 0 ⇒ 1 + λ [ Π i = 1 K − 2 r i ( 1 + r K ) ] S 0 = 0 \frac{\partial F}{\partial r_{K-1}}=0 \Rightarrow 1+\lambda\left[\Pi_{i=1}^{K-2}r_i(1+r_K)\right]S_0=0 ∂rK−1​∂F​=0⇒1+λ[Πi=1K−2​ri​(1+rK​)]S0​=0

所以 Π i = 1 K − 1 r i = Π i = 1 K − 2 r i ( 1 + r K ) ⇒ r K − 1 = 1 + r K \Pi_{i=1}^{K-1}r_i =\Pi_{i=1}^{K-2}r_i(1+r_K)\Rightarrow r_{K-1}=1+r_K Πi=1K−1​ri​=Πi=1K−2​ri​(1+rK​)⇒rK−1​=1+rK​。

其他的递推公式以此类推。

证毕。

9、最小化总代价

在前面的过程中，对于包含两个树结构的LSM来说，总的代价是关于内存以及磁盘存储以及访问代价的一个公式， C O S T T O T = C O S T m ⋅ S 0 + max ⁡ [ C O S T d ⋅ S 1 , C O S T π ⋅ H ] COST_{TOT} = COST_m\cdot S_0+\max [COST_d\cdot S_1, COST_\pi \cdot H] COSTTOT​=COSTm​⋅S0​+max[COSTd​⋅S1​,COSTπ​⋅H]。并结合前面一节中关于访问磁盘频率 H H H的等式 H = ( 2 R / S p ) ⋅ ( K ⋅ ( 1 + r ) − 1 / 2 ) H=(2R/S_p)\cdot (K\cdot (1+r)-1/2) H=(2R/Sp​)⋅(K⋅(1+r)−1/2)，并定义以下变量：

• s = ( C O S T m ⋅ S 0 ) / ( C O S T d ⋅ S 1 ) s=(COST_m\cdot S_0)/(COST_d\cdot S_1) s=(COSTm​⋅S0​)/(COSTd​⋅S1​)
• t = 2 ⋅ ( ( R / S p ) / S 1 ) ⋅ ( C O S T π / C O S T d ) ( C O S T m / C O S T d ) t=2\cdot((R/S_p)/S_1)\cdot (COST_\pi/COST_d)(COST_m/COST_d) t=2⋅((R/Sp​)/S1​)⋅(COSTπ​/COSTd​)(COSTm​/COSTd​)
• C = C O S T T O T / ( C O S T d ⋅ S 1 ) C=COST_{TOT}/(COST_d\cdot S_1) C=COSTTOT​/(COSTd​⋅S1​)

然后使用上面这些符号替换 H H H公式中的变量，并假设 S 0 / S 1 S_0/S_1 S0​/S1​比较小，可以得到一个近似的等式 C ≈ s + max ⁡ ( 1 , t / s ) C\approx s+\max(1,t/s) C≈s+max(1,t/s)。式子中的变量 t t t是对于多页面块(multi-page block)I/O速率需求的衡量值，变量 s s sLSM需要多少的内存。对于 t < = 1 t<=1 t<=1时，即对于数据的访问频率不是很高的情况下，可以尽可能的将数据放到磁盘上来减少内存的使用开销；而对于 t > 1 t>1 t>1的情况，最小化 C C C的 s s s与 t t t的关系为 s = t 1 / 2 s=t^{1/2} s=t1/2，即 C O S T m i n = 2 [ ( C O S T m ⋅ S 1 ) ( 2 ⋅ C O S T π ⋅ R / S p ) ] 1 / 2 COST_{min} = 2\left[(COST_m\cdot S_1)(2\cdot COST_\pi \cdot R/S_p)\right]^{1/2} COSTmin​=2[(COSTm​⋅S1​)(2⋅COSTπ​⋅R/Sp​)]1/2。

10、LSM树的并行

对于LSM中保存在磁盘上的树结构中的一个节点，可以在进行完全匹配查找时将节点缓存在一个单个页面大小的内存缓冲区中，或者缓存在一个包含多个页面的块中。对于LSM树的并行操作需要避免以下三种冲突：

• 一个对实际存储在磁盘上的节点的查询操作不应该与另外一个涉及到该节点的滚动合并操作并行执行；
• 针对 C 0 C_0 C0​树的查找或者是插入操作不应该与另外一个将 C 0 C_0 C0​中的节点滚动合并到 C 1 C_1 C1​的操作并行执行；
• 由于LSM中 C i C_i Ci​的大小是逐渐增大的，因此编号较小的 C i − 1 C_{i-1} Ci−1​的滚动合并到 C i C_{i} Ci​比从 C i C_{i} Ci​到 C i + 1 C_{i+1} Ci+1​的频率更高。因此，需要保证在这种情况下，相邻的滚动合并操作在有数据重叠的情况下，一方不会被另一方阻塞。

在LSM中，以节点作为加锁的单元。对处于滚动合并操作过程中的节点加写模式锁，而在查询过程中被读取的节点加读模式锁。

假设在某两个驻留在磁盘上的LSM树结构之间进行滚动合并操作，将 C i − 1 C_{i-1} Ci−1​中超出大小限制的索引项节点合并到 C i C_i Ci​中。在 C i − 1 C_{i-1} Ci−1​的叶子层中有一个游标指向 C i − 1 C_{i-1} Ci−1​中处于最底层中下一个被合并到 C i C_i Ci​的索引项，同时也指向从该叶子节点位置一直向上到 C i − 1 C_{i-1} Ci−1​根节点每一层对应的位置。对于 C i C_i Ci​也有同样的指针指向接下来将要进行合并操作的位置。在滚动合并过程中， C i C_i Ci​中将要插入的新节点会首先放到一个多页面块(multi-page block)缓冲区中，并且按照从左到右的顺序放置。对于 C i C_i Ci​中指向的节点会在内存中被分成两个多页面块缓冲区，其中"emptying block"中是合并游标尚未到达的区域，而"filling block"中是已经进行合并操作的位置。在某些情况下，可能并不想将 C i − 1 C_{i-1} Ci−1​中所有的索引项全部合并到 C i C_i Ci​中，对于 C i − 1 C_{i-1} Ci−1​同样按照当前游标的位置，将缓冲区划分为"emptying block"——游标尚未到达的地方以及"filling block"——目前为止已经合并的地方。在滚动合并的过程中，将会对以上四个block全部加上写锁。当 C i C_i Ci​的"emptying block"用尽的时候释放锁。

11、LSM树的恢复机制

在滚动合并的过程中，操作中涉及到的数据会被暂时放在内存缓冲的多页面块(multi-page blocks)中。因此，当系统发生故障时，滚动合并操作的结果会丢失。LSM使用检查点(checkpoint)的方法，在 T 0 T_0 T0​时刻，假如需要一个checkpoint，那么在完成所有的合并步骤之后把锁释放掉，之后延迟所有新的索引项的插入操作直到检查点建立完毕。在建立检查点时需要进行如下的操作：

• 将 C 0 C_0 C0​写入到磁盘指定的位置，在写入完成后，对于LSM新插入索引项的操作可以继续进行，而对于合并操作则需要继续延迟；
• 对于保存在磁盘上的 C i C_i Ci​缓存在内存的数据刷新到磁盘上；

对于创建的检查点文件包含如下的信息：

• 日志***;
• LSM中所有树结构的根节点的在磁盘上的地址;
• 所有树结构中合并游标的位置;
• 内存中多页面块的动态分配情况

在以上关于使用检查点作为恢复机制的过程中，有一个细节需要注意。在滚动合并的过程中，每当多页面块或者是树结构中非底层节点从磁盘加载到内存中时，需要立即指定新的磁盘位置，防止在清空操作之前开始创建检查点而创建检查点需要将剩余的数据写入到磁盘上。同样，对于新创建的节点也需要先指定一个磁盘上的位置。

12、LSM的一些变体

原论文中给出了一些基于基本LSM的一些变体方法。比如LSM树中的节点可以直接存放数据而不是存放一个索引项指向实际数据的地址，而且这样记录可以根据键值存放在一起。这种做法的一个坏处是导致插入数据的I/O速率 R R R、滚动合并操作过程中游标移动以及总的I/O速率 H H H都会变大或变快。另外一种变体是把 C i C_i Ci​中最近一段时间产生的索引项保留下来而不是合并到 C i + 1 C_{i+1} Ci+1​中。

参考

[1] Finding a needle in Haystack: Facebook’s photo storage

[2] DistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed Caching

[3] The Log-Structured Merge-Tree (LSM-Tree)

[4] The SB-tree: An index-sequential structure for high-performance sequential access