LSM-Tree（Log Structured Merge Tree）是数据库畛域内较高效的key-value存储构造，被广泛应用于工业界数据库系统，如经典的单机kv数据库LevelDB、RocksDB，以及被诸多分布式NewSQL作为底层存储引擎。

本期将由腾讯云数据库高级工程师韩硕来为大家分享基于LSM-Tree存储的数据库性能改良，重点介绍近年来学术界对LSM-Tree的性能改良工作，并探讨这些改良措施在工业界数据库产品中的利用状况以及落地的可能性。以下是分享实录：

1. LSM-Tree根本构造

LSM-Tree全称为“Log Structured Merge Tree”，是一种基于磁盘存储的数据结构。1996年Patrick O’Neil等人在信息系统期刊上发表了一篇题名为“Log Structured Merge Tree”的论文，首次提出LSM-Tree构造。相比于传统的B+树，LSM-Tree具备更好的写性能，能够将离散的随机写申请转换成批量的程序写操作，无论是在RAM、HDD还是在SSD中，LSM-Tree的写性能都更加优良。

作为高效的key-value存储构造，LSM-Tree已被广泛应用到工业界数据库系统中，如经典的单机kv数据库LevelDB、RocksDB，以及被诸多分布式NewSQL作为底层存储引擎，近日公布的TDSQL新敏态引擎存储模块也使用了LSM-Tree构造。LSM-Tree构造有较多长处：写性能弱小、空间利用率高、较高的可调参个性、并发管制简略、有齐备的修复计划等。

LSM-Tree的实质是基于out-place update即不在原地更新。下图展现了in-place update即原地更新与out-place update即不在原地更新的区别。

在in-place update中，数据更新操作是将数据的新值间接笼罩旧值，但会带来随机读写问题。在out-place update中，数据更新操作则是将新值按工夫程序追加到文件开端，通常会带有版本号用于标记新值或旧值，个别为程序写，因而写性能更好，但毛病是会产生冗余数据，在读性能和空间利用率上也无奈与in-place update相比。

以后支流的LSM-Tree根本构造如下图，分为内存和磁盘两局部。内存采纳MemTable数据结构，能够通过B+树或跳表实现。MemTable用于承受最新的数据更新操作，保护外部数据in-tree逻辑上的有序。磁盘中的局部数据存储物理有序。数据依照层进行堆放，档次越往下，数据写入的工夫就越早。每层外部按是否有序可划分为一个或多个sorted run。一个sorted run外部的数据必然有序（通常指物理上有序）。sorted run数据可进一步划分为不同的SSTable。当MemTable中的数据写满时，其会向L0进行落盘操作即Flush操作。如果LSM-Tree的某一层也达到容量阈值，就会向下合并，将同样的key的过期版本革除，即compaction操作。

RocksDB是基于LSM-Tree的存储引擎，其根本构造如下图。它与LSM-Tree根本构造在主体上保持一致，不同点在于RocksDB的内存中减少了Immutable MemTable局部，这是用于Flush操作的写缓存机制。当MemTable中的数据写满时，会先暂存到Immutable MemTable中，再通过后盾的异步线程将Immutable MemTable缓缓落盘到磁盘中的SST根本件。RocksDB中还减少了WAL日志，用于crash时的数据恢复。

LSM-Tree反对的查问可分为点查与范畴查问两大类，对应的执行形式如下：
● 点查：先查MemTable，再从SST中的Level0、Level1…...一层层向下探查，找到数据就返回。因为下层数据必然比上层数据的版本新，因而返回的都是最新数据。
● 范畴查问：每一层都会找到一个匹配数据项的范畴，再将该范畴进行多路归并，归并过程中同一key只会保留最新版本。

LSM-Tree性能的掂量次要思考三类因素：空间放大、读放大和写放大。

第一类因素是空间放大。在LSM-Tree中所有写操作都是程序追加写，数据的更新操作则是通过创立一个新的空间来存储新值，即out-place update。与此同时，因为旧值不会立刻被删除，因而会占用局部空间。实际上这部分冗余数据占用空间的大小要远大于无效数据自身，这种景象被称为“空间放大”。LSM-Tree会利用compaction操作来清理旧数据从而升高空间放大。

第二类因素是读放大。在LSM-Tree、B+树等外存索引构造中，进行读操作时须要按从上到下的程序一层层去读取存储节点，如果想读一条数据，就会触发屡次操作，即一次读操作所读到的数据量实际上要远大于读指标数据自身，从而影响读性能，这种景象被称为“读放大”。
    
第三类因素是写放大。在LSM-Tree中，compaction操作会将多个SST文件重复读取，合并为新的SSTable文件后再次写入磁盘，因而导致一条kv数据的屡次重复写入操作，由此带来的IO性能损失即写放大。

LSM-Tree的初衷是想通过空间放大和读放大来换取写放大的升高，从而达到极致的写性能，但也须要做好三方面因素的衡量。EDBT 2016的一篇论文首先提出RUM猜测（R为read，U为update，M为memory usage，RUM为三者缩写）。该论文认为，三者之间存在衡量关系，无奈使得三个方面的性能都达到最优，因而必须在三者之间进行无效衡量。

以compaction操作为例，其目标是保证数据的部分有序和清理数据旧值，即一个sorted run外部的多个SST文件中的数据是有序的，从而升高读放大。对一个查问而言，在一个sorted run中至少只须要读取一个SST中的一个数据块。

如果齐全不做compaction操作，即始终程序写，LSM-Tree就会进化为log文件，这时写性能达到最佳。因为只须要程序写log即可，不须要做任何操作。但读性能将会处于最差状态，因为在没有任何索引、无奈保障有序性的状况下，每次想读到固定的数据项，就须要扫描所有的SST件。

如果compaction操作做到极致，实现所有数据全局有序，此时读性能最优。查问时只须要通过索引和二分法即可迅速找到要读的键值的地位，一次IO操作即可实现，但代价是须要频繁进行compaction操作来维持全局有序状态，从而造成重大的写放大，即写性能变差。

这就延长出两种compaction策略：

● Tiering compaction：较少做compaction操作，有序性较弱，每一层容许有多个sorted run。

● Leveling compaction：更频繁的compaction操作，尽可能加强有序性，限度每一层最多只有1个sorted run（L0层除外）。

2. Compaction优化策略与剖析

Leveling compaction策略中，每层只有一个sorted run，sorted run外部的数据放弃物理有序。具体实现上咱们以RocksDB为例。一个sorted run能够由多个key不重叠且有序的SSTable files组成。当第L层满时，L层会选取局部数据即局部SSTable，与L+1层有重叠的SSTable进行合并，该合并操作即compaction操作。

Tiering compaction策略中，每层能够有至少T个sorted run，sorted run外部有序但每层不齐全有序。当第L层满时，L层的T个sorted run会合并为L+1层的1个sorted run。因为每层容许有多个sorted run，因而SST文件间可能会存在数据范畴的重叠，compaction操作的频率会更低，写性能也会更强。

两种compaction策略各有优劣。Tiering compaction因为compation操作频率低，过期版本的数据未能失去及时革除，因而空间利用率低，由此带来的查问操作的代价比拟高。在极其状况log file即齐全不做compaction操作时，写入性能最优。Leveling compaction则会更频繁地做compaction操作，因而数据趋势更有序。极其状况sorted array即数据达到全局有序时，此时查问性能和空间利用率最优。

SIGMOD 2018的一篇论文对上述两种compaction策略进行了具体的实践剖析，剖析后果演绎为下表，其剖析后果与前述统一。实践剖析过程如下：

先从写入操作复杂度进行剖析。I/O以block为根本单位，一次I/O均匀读写B条kv，因而一条kv写一次磁盘的代价能够示意为1/B。在leveling compaction策略中，第i层向第i+1层最多合并T次，在第j层合并到第i层时，其可被后续的数据项重复进行t-j次合并。由此可得，每条KV在第i层即任意一层被均匀IO的读写次数为t/2次，即O(T)。从MemTable始终向下合并到最初一层即第L层，会失去均匀写磁盘数即“TL/B”。

以下图为例，每合并一次，第i层的增量不会超过1/T。第i层通道从空到满，其最多向下合并t次，因而每条kv在每层均匀被合并2/T次。

在Tiering compaction策略中，每条KV在第i层时只会被合并一次，因而从MemTable始终向下合并到最初一层即第L层，会失去均匀写磁盘数即L/B。

在第i-1层向第i层合并时，会在第i层产生一个新的sorted run，均匀每条kv在每层只会被合并一次。

再从空间放大率进行剖析。space-amplification定义为：过期版本的kv数与无效kv总数之比。在Leveling compaction策略中，最坏的状况为前L-1层的每条数据在最初一层即第L层中都各有一条未被革除的过期版本数据。每层容量为比值为T的等比数列，依据等比数列求和公式， 第L−1层的kv数量占总kv数的1/T，最初一层则占 (T−1)/T，因而空间放大为1/T，空间放大率较低。

在Tiering compaction策略中，容许每层最多有T个sorted run，最坏状况下最初一层的T个sorted run之间都是每个kv的不同版本，即一条kv在最初一层的每个sorted run都呈现一次，共T个不同版本，因而空间放大为O(T)。

Leveling compaction的空间放大系数为1/T，因而空间利用率较高。Tiering compaction在最坏状况下，最初一层的每个sorted run都是冗余数据，空间利用率较差。

再从查问角度进行剖析。点查应用Bloom filter进行过滤，将其分成两类：

● 读穿透，即查问数据不存在。

● 假如晓得每次产生假阳性的概率，如果断定后果为假阳性，则须要读一次磁盘。

在Leveling compaction策略中，每层只有一个sorted run，实现齐全有序，因而每层只须要查问一次Bloom过滤器。依据二项分布冀望公式，推导出的冀望读盘次数为L×e的-m/n次方。

在Tiering compaction策略中，每层最多有T个sorted run，最多可能查问T次Bloom filter，在前述构造根底上乘以T的系数，依据推导出的冀望读磁盘次数，其查问性能落后于Leveling compaction。

如果查问数据存在，因为产生假阳性的概率远小于1，因而大部分状况下，无论是Tiering compaction还是Leveling compaction，都只须要读一次盘。

再从范畴查问角度进行剖析。该论文将范畴查问分为短范畴查问和长范畴查问。短范畴查问指返回block数量的大小不超过最大层数范畴的两倍；反之则为长范畴查问。

通过统计公式发现，短范畴查问在归并前的各版本数据趋向于均匀分布在各层，因而Leveling compaction和Tiering compaction的查问复杂度别离为O(L)和O(T×L)。长范畴查问在归并前各版本数据大部分来自最初一层，因而上述两种策略的代价别离为返回block数的大小、返回block数的大小再乘以T，因而Leveling compaction比Tiering compaction的读性能更好。

通过上述实践剖析，能够失去如下论断：

● Tiering compaction的写放大低，compaction频率低，其缺点为空间放大高、查问效率低，更利于update频繁的workload；Leveling compaction的写放大高，compaction操作更频繁，但空间放大低，查问效率高。

● 只管Tiering compaction和Leveling compaction的空间放大不同，但导致空间放大的次要起因雷同，即受最上层的过期版本数据影响。

● 越往下的层，做一次compaction的I/O代价越高，但产生的频率也更低，不同层之间做compaction的冀望代价大致相同。

● 点查、空间放大、长范畴查问的性能瓶颈在LST-tree的最上层，而更新操作则更加平均地散布在每一层。因而，缩小非最初一层的compaction频率能够无效升高更新操作的代价，且对点查、空间放大、长范畴查问的性能影响较小。

3. 升高写放大

基于上述实践剖析，该论文提出混合compaction策略即Lazy Leveling。它将Leveling与Tiering进行联合，在最初一层应用Leveling策略，其余层应用Tiering策略，即最初一层只能存在惟一的sorted run，其余层容许存在多个sorted run，从而无效升高非最初一层做compaction的频率。

下表是采取Lazy Leveling策略后的性能汇总表，其中，绿色局部示意成果较好，红色局部示意较差，黄色局部代表适中。从下表能够看出，Lazy Leveling的更新操作（update）性能优于Leveling，靠近于Tiering。这是因为在前L-1层维持Tiering策略，做compaction的频率更低，写放大低。但Lazy Leveling的空间放大靠近于Leveling，远好于Tiering。这相当于联合了两种策略的劣势。

对于点查（point lookup），论文中别离剖析了查找不存在kv和kv在最初一层两种状况，并基于论文Monkey的思路对每层的bloom filter bit进行了优化，能够达到与Leveling+Monkey策略相匹配的点查性能。对于长范畴查问，Lazy Leveling能够做到与Leveling统一的性能，而短范畴查问则进化至靠近Tiering的程度。

论文对此进行总结：应用一种繁多compaction策略，不可能在上述所有操作中做到性能最优。Lazy Leveling实质上是Tiering与Leveling策略的折衷加调优，在侧重于更新操作、点查和长范畴查问的workload上性能较好；Leveling实用于查问为主的workload；Tiering则实用于更新操作为主的workload。

论文通过建设代价模型将Lazy Leveling进行推广，将其称为Fluid LSM-Tree。假如有两个参数，别离为Z和K。Z示意最初一层容许有最多Z个sorted run；其余层则容许有多个sorted run。K为限度参数，示意每层最多有K个sorted run。当每个sorted run的值达到t/k时会向下做compaction。通过这样的形式，将Lazy Leveling进行泛化推广，通过不同的workloads来调节参数Z和K。下表是将参数Z和K增加进去后的Fluid LSM-Tree的代价利用剖析后果。

但这在实际操作中会遇到问题，即如何依据workloads来选取参数Z和K。论文采取搜寻形式去找到针对某个workload代价模型最小的参数K和Z。在真正实现时，咱们对workload的认知绝对无限，想要找到最优的参数K和Z会较为艰难，且该模型总体比较复杂，实践性无限。

RocksDB在某种意义上也采取了混合compaction策略。RocksDB的L0层的SST之间，K容许相互重叠，即容许多个sorted run。这实际上是Tiering策略，因为其落盘的Flush的性能更优。在L1-Ln层中采取Leveling策略，可能更及时地清理过期数据，进步空间利用率。

RocksDB将每个sorted run切割为多个SST文件，每个SST文件都有大小阈值。其长处在于每次产生compaction时，只须要选取一个或者大量的SSTable与上层有KV重叠的SSTable进行合并，波及到合并的无效数据量处于可控范畴。

SOSP 2017中有一篇名为PebblesDB的论文，提出了compaction Guard概念。每层宰割为多个分片，分片间的宰割称之为compaction Guard，即一次compaction操作不会逾越该分界线，每个分界线外部SST之间容许重叠，可了解为Tiering compaction。这种做法最大的益处是能够保障数据项从第i层向第L+1层进行compaction时，写入只有一次。因为它将原生的LSM-Tree进行分隔，造成FLSM构造。其害处是读性能会变差。因为找到对应分片后，分片外部如果存在多个SST，咱们就不晓得数据的真正寄存地位，这时须要借助Bloom过滤器来对每个SST进行探查，且即便应用Bloom过滤器，其产生假阳性的冀望次数也会减少。

在RocksDB实际过程中，咱们发现它实际上提供了一个SST Partitioner的类，通过类能够在代码实现上保障分片，但与PebblesDB不同的是，其在分片外部放弃SST不重叠，依然采取Leveling策略。其益处是读性能不变。尽管写性能没有失去晋升，但更加适配于扩容场景，便于迁徙及迁徙后数据的物理删除操作。

以TDSQL新敏态引擎架构为例。每层的存储节点称为TDstore，一个TDstore实在的数据存储相当于保护一个LSM-Tree构造来存储KV数据，再将KV数据依照区间划分成不同Region。须要扩容时，咱们会减少若干个存储节点，再将原来节点上的局部Region迁徙过来。Region迁徙波及到Region数据的迁徙。如果采纳前述的宰割策略，将LSM-Tree的每一层基于Region边界进行宰割，将Region从绝对残缺的SST文件中捞取进去，并插入到新增的TDstore存储节点中。因为SST依据边界进行宰割，咱们能够绝对残缺地将Region外部的数据迁徙或删除，因而Region数据迁徙的性能会失去晋升。

4. 升高读放大

升高读放大必须联合布隆过滤器。具体实现为：每层设置一个布隆过滤器，通过布隆过滤器进行过滤，缩小有效读磁盘block的次数。

下图为前述的论断表。当数据查问不存在即产生读穿透时，产生假阳性的概率为e的-m/n次方。只有产生假阳性，就必须去读数据块，进行一次读磁盘操作。在Leveling中，每层只有一个sorted run，查一次Bloom filter的概率为e的-m/n次方，依据冀望公式推导出的冀望读盘次数为L乘以e的-m/n次方。Tiering中则是T乘以L再乘以e的-m/n次方。假如点查时应用布隆过滤器进行过滤，每层都建设一个布隆过滤器即固定的bits团，读性能就可失去晋升。

2017年一篇名为Monkey的论文对布隆过滤器进行优化。在LSM-Tree不同层设置不同的布隆过滤器的bits，能够无效升高IO开销，从而缩小读穿透的冀望次数。其论断剖析如下：第i层设置（a+b）×（L-i）的bits。因为最初一层数据量最大，只用一个bit来hash到布隆过滤器中。相比于前述公式，这能够缩小一个L系数。因为Bloom filter要在内存中持有，而每层的bits不同，因而总体上升高了布隆过滤器的内存开销。其点查的读性能和整体Bloom filter的空间利用率都会失去晋升。

SIGMOD 2021一篇名为Cuckoo的论文，采纳布谷鸟过滤器代替布隆过滤器，从而优化读性能。布隆过滤器的优化形式为：LSM-Tree的每层甚至每个SST文件都会保护一个Bloom filter，查问时须要从MemTable L0到Ln一层层向下探查，每次探查时先走一遍相应的布隆过滤器。该论文提出代替计划，不须要每层都保护一个布隆过滤器，而是抉择保护一个全局的布谷鸟过滤器。先查全局的布谷鸟过滤器，如果反馈不存在则示意数据不存在，如果反馈存在，思考到可能产生假阳性，咱们再去查数据文件。

实现原理为：全局的布谷鸟过滤器里记录了Level ID。如果在布谷鸟过滤器中有mash，则不须要持续向下探查，能够间接找到其对应的Level ID，找到对应层、对应的sorted run去读磁盘，看数据是否存在。布谷鸟过滤器对接两局部：其hash map或签名，再加上地位ID即level ID。

布谷鸟过滤器。咱们通过两次哈希算出key所要插入的具体位置，所对应的两个桶称为b1和b2。b1间接拿key进行擦洗，b2不须要用key的原值，在算出签名指纹后再做哈希，因而每个key会有两个能够寄存的地位。

布谷鸟过滤器哈希的数据插入过程如下：假如要插入item X，通过第一个哈希计算出其地位是2，即b1等于2，第二个哈希算出其地位是6。咱们先将其放在第一个地位，如果能够放下则放下，如果放不下再看第二个地位即b2，如果b2没有被占则间接放下。如果b2也被占则进行relocate，将原来的对象剔除，新插入的值再放到第二个地位。被剔除的值会放到它的两个bucket中的另一个。如果另一个bucket也被占据，被占的元素会持续被踢走，直到所有元素都有一个新的空白地位寄存，则该过程完结。

Cuckoo论文中还须要记录其签名，用于确认key。如果签名抵触则会造成假阳性。除此之外，还须要记录其Level ID如下图中的1、4、5，Level ID的作用是记录该值位于哪个sorted run。通过Level ID能够在具体的sorted run里查问或更新。

5. 升高空间放大

RocksDB默认采纳Leveling compaction，但也提供相似Tiering compaction的选项。如果抉择Leveling compaction，它会提供dynamic level size adaptation机制。实践分析表明，在最初一层数据充斥时，Leveling compaction的空间放大率不高，等于1/T。但在实践中，最初一层的理论数据通常不会达到阈值。

假如每层容量放大比例为T，每层容量是T系数的等比数列。依据等比数列进行求和，咱们发现最初一层的数据量占绝大多数，等于总大小的（T-1）/T，后面所有层只占总大小的1/T，此时冗余数据量为后面所有层数据量与最初一层数据量之比，等于1/（T-1）。假如放大比率为10，阈值为1G，L1到L4的阈值别离为10G、100G、1000G。如果L4为最初一层，通过计算可知冗余率为1.1。

理论状况下，最初一层的数据量个别不会达到阈值。在上述例子中的L4层，如果以动态阈值为参照，以后L4的数据并没有写很多，可能只有200G数据，其放大率会比拟差，后面存在大量冗余数据。

因而RocksDB提出了动静调整每层容量阈值的机制。以下图为例，当L0充斥时，其数据先不往L1写，而是先往L5进行合并，这时L1至L4为空。

当L5的理论数据量达到阈值10M时，compaction L0往着落的指标层切到L4，并让L4的阈值放弃最后的阈值即10M，再将L5的阈值乘以放大系数T，L4与L5之间的容量阈值仍放弃T倍的关系。假如L5的理论数据量达到11M，则L4的阈值为1.1M。

数据一直往L4写，L4再向L5进行compaction，L4会逐步达到阈值。

L4达到阈值后，以此类推，当L3达到10M后，开启L2作为L0的合并指标层。L3初始阈值为10M，这时L4扩充为100M，L5裁减为1000M。

在这种动静调整每层空间大小阈值的策略下，能够将数据冗余量始终保持在1/（T-1）。在T=10时，其空间放大率不会超过1.1，这是比拟现实的空间放大率。

升高空间放大还有其余的实际措施。目前RocksDB曾经实现key prefix encoding，能够让相邻的key共享一次，只存一次，从而节俭10%的空间开销。sequence ID garbage collection也是较好的优化措施。当一个key的sequence number小于最老的snapshot的sequence number，则它的sequence number能够改写为0，而不影响数据的正确性。sequence number压缩率的进步带来了空间利用率的进步。

加压缩也能够优化空间放大。目前RocksDB反对多种压缩办法。第三方压缩办法有LZ、Snappy等办法。咱们还能够以SST文件作为单元来设置不同的压缩算法，从而对KV数据进行压缩。升高空间耗费的同时会减少读开销，压缩过程中也会耗费肯定的CPU资源，读的过程中还要进行解压，这就要求咱们必须进行衡量。因而实际的优化策略通常为：L0至L2层不压缩，L3及以下应用较为轻量级的压缩算法，如Snappy、LZ，能够综合思考压缩带来的空间开销受害和读性能受害。最初一层采纳压缩率更大的压缩算法，一方面是因为数据较老，读到的概率较低，另一方面是因为越往下的层的容量阈值越大，存储的数据也越多，压缩率高能够节俭较大的空间开销。

RocksDB也在Bloom filter方面进行优化实际。Bloom filter自身会有相应的内存开销，在内存无限的状况下，能够缩小Bloom filter对内存的占用。办法之一是最初一层数据不再建设bloom filter。因为最初一层的数据量较大，Bloom filter自身占用的空间也比拟大，会耗费较多内存，且思考到最初一层的数据较老，被拜访的概率较小，因而在最初一层或最初几层不再建设Bloom filter，在节俭内存耗费的同时对读性能影响小。

还有其余的优化办法，比方compaction job 并发。在RocksDB中，compaction在后盾异步进行执行，执行过程中分为不同compaction job，如果两个compaction job之间的SST汇合相互不重叠，则这两个compaction job能够实现现场并发。L0层的SST文件通常相互重叠，RocksDB对此进行优化，提出subcompaction概念，将L0层有SST重叠的状况也做并发。IPDPS 2014的一篇论文还提出，compaction之间能够做流水线。

6. 结语

相比于传统的B+树，LSM-Tree构造具备更好的写性能，能够将离散的随机写申请转换成批量的程序写操作。其性能掂量次要思考三类因素：空间放大、读放大和写放大。LSM-Tree最后的设计理念是想通过空间放大和读放大来换取写放大的升高，从而达到极致的写性能，但也须要做好三方面因素的衡量，能够从升高写放大、升高读放大、升高空间放大三方面来对LSM-Tree构造进行优化，从而晋升数据库性能。