论文背景
键值存储被广泛应用于各个领域,目前大多数的键值存储系统(如RocksDB、LevelDB等)采用LSM-Tree作为底层存储结构。关于LSM-Tree的总体设计思想这里就不再多做赘述。这里主要探讨LSM-Tree的数据合并(通常也被称作Merge或Compaction)策略。Merge过程是目前LSM-Tree的一大性能瓶颈,其能在很大程度上影响LSM-Tree的读写性能。在当今所有LSM-Tree架构的设计中,Compaction主要有分为两种策略:Tiering和Leveling。下面将简要描述一下两种策略的设计和它们之间的优劣。
Tiering vs. Leveling
1. Tiering-Compaction
Tiering-Compaction(典型代表Cassandra)将会在某层的数据量达到阈值时合并该层的SortedRun(即一个排序单元,一个SortedRun的数据不存在重叠且有序排列)。在Tiering-Compaction的策略下,一层可能会存在多个SortedRun,即同层的数据之间可能存在重叠,因此Tiering同时还会带来读放大的问题。
2. Leveling-Compaction
与Tiering不同,Leveling-Compaction(典型代表RocksDB、LevelDB)可能会合并两层的SortedRun,该策略确保每层只有一个SortedRun,因此相比Tiering,Leveling的读放大问题相对比较小,但是同时也因为要确保每层的数据不存在重叠,Leveling会更加频繁地进行数据合并,所以Leveling会带来更加严重的写放大问题。
总结
总结以上两种Compaction策略,Tiering在更新密集型工作负载下有着更大的优势(写放大小),但是在点查、长短范围查询的负载下Leveling表现更佳优异(读放大更小),同时Tiering相比Leveling空间放大的问题更加严重。
层数设定
关于LSM-Tree的层数的设定,文章中给出了下面的公式
其中N表示总键值对的数量,B表示数据块(block)中所能包含的最大键值对数,P表示缓冲区中block的个数,T表示层之间的容量放大倍数,L表示根据计算得到LSM-Tree的合理层数。文中对于上面公式的解释是,Level0的容量大小表示为B*P
,从而可以推出Leveli的容量大小为B*P*T^i
个键值对,LSM-Tree的总数据量为N,那么最大层中大约将包含N*(T-1)/T
个键值对,那么可以得出B*P*T^L = N*(T-1)/T
,从而可以推导出上面的公式。并且还能推算出放大倍数T的范围为[2, N/(B*P)]
。
通常来说,当Leveling(Tiering)的T增加时,其查询的性能以及空间放大问题就会降低(增加),而更新操作的开销则会增加(降低)。
![](https://nekoneko.best/usr/uploads/2024/05/4264780066.png)
上图是作者对Tiering和Leveling空间放大率的分析。这里定义键值存储系统的空间放大率是存储的总键值对个数除以unique键值对(即不重叠数据的大小)再减去1。对于Leveling来说,最坏情况每次更新一个键值对时从第1层到第L层都存有一个key值与更新数据相同的数据,以此类推到第L层,就可能有1/T个垃圾数据对,因此总空间放大就是O(1/T);对于Tiering来说,最坏情况就是第1层到第L-1层的数据都与最后一层(第L层)存在重叠,换而言之就是最后一层中包含了系统整体key值范围的数据(不过都是垃圾数据),因此总空间放大最后一层数据量与就是O(T)。
Lazy Leveling Compaction
综上所述,Tiering和Leveling都有各自的优劣,分别适用于不同的工作负载。为了结合两种策略的优势,让系统能够适应各种工作负载,作者提出了一种Lazy Leveling的数据合并策略,该策略可以看作是Tiering和Leveling的结合体。Lazy Leveling的具体做法是在最大层采用Leveling策略合并数据(确保最大层只有一个SortedRun),而其他层使用Tiering。另外,为了加速点查,作者为不同层的布隆过滤器(Bloom Filter)分别使用了不同的内存分配(布隆过滤器的假阳率主要跟其位数组大小、哈希函数有关,通过提升位数组的大小能够有效降低假阳率)。
各负载复杂度对比
下图为Tiering、Leveling和Lazy Leveling在各负载下在最坏情况下的复杂度对比
可以看到Lazy Leveling在达到了与Leveling相同的空间放大、点查、长范围查找复杂度的同时降低系统更新的开销、以及稍逊色于Leveling的短范围查询性能。
Fluid LSM-Tree
Fluid LSM-tree是LSM-Tree的泛化,通过分别控制最大级别和所有其他级别的合并频率,允许在设计空间中流动。相对于Lazy Leveling,Fluid LSM-tree可以通过减少最大级别的合并来优化更新,或者通过在所有其他级别进行更多合并来优化短范围查找。
Fluid LSM-Tree提供了两个参数K和Z,Z表示最大层SortedRun个数,K则为其余层的最大SortedRun个数:
- K = 1, Z = 1时则为Leveling
- K = T - 1, Z = T - 1时则为Tiering
- K = T - 1, Z = 1时则为Lazy Leveling。
通过动态地调整Z和K,Fluid LSM-Tree可以在Lazy Leveling, Tiering和Leveling之间转换:增加Z可以降低最大层数据合并的频率,从而降低更新的开销;降低K可以增加其余层的合并频率,从而提升点查、短范围查询的性能。