基于LSM的存储技术的前世今生

1. 概述

Log-Structured Merge-trees (LSM树)被广泛应用在现代NoSQL系统存储层中，比如：BigTable、Dynamo、HBase、Cassandra、LevelDB、RocksDB和AsterixDB等等。不同于传统的索引结构（比如B+树）更新时直接在所在位置进行修改，LSM树则先将数据直接写入到内存，然后通过合并线程将内存数据刷新到磁盘。这种设计有很多好处，包括：超高的写性能、不错的空间利用率、可优化性、简单的并发控制和恢复机制等。

2. LSM树的历史

通常情况下，数据库存储引擎处理更新采用两种方法：原地更新（in-place updates）和异地更新（out-of-place updates）。原地更新结构（比如B+树）是直接将新的数据覆盖到原有的位置，这样虽然会带来好的查询性能，但是这样做导致随机IO，会极大降低写性能，并且多次更新和删除会严重导致磁盘页面碎片化问题，从而降低了空间利用率。

相反，异地更新结构（比如LSM树）则是将更新数据存储在新的位置，而不是覆盖原有的旧数据。这样做利用了操作系统的顺序IO，从而提高了写性能，并且由于旧数据的存在，使得数据恢复变得很简单了。但是这样做牺牲了读性能，因为必须要读取所有位置的记录才能得到正确的数据。于是就需要一个将离散数据重新组织的方法将读和写性能达到一个平衡。

LSM-tree的结构最早在1996年提出，他设计了一个合并的过程，能达到非常高的写性能的同时，将读性能和空间利用率达到一个合理的范围。初始设计参考如下：

LSM树包括一系列Component（即上图中的C）组成，其中每一个Component为一个B+树，第一个Component保存在内存，其余则为磁盘，容量依次增大，当前一个Component满了的时候，将被合并到下一个。在原始的论文中说，Component个数固定的情况下，当相邻容量比：

相同的时候，写性能达到最优，这一原则也在后续的LSM优化实践中被采用。

3. 现代LSM树       

3.1. 基本结构

现代LSM树简化了原始LSM的结构，多个Component合并到一个新文件，而并不会修改原来旧的Component。并且一个Component并不局限于B+树，还可以为跳跃表（skip-list）或是一个有序字符串表（SSTables）。一个SSTable包括一个数据块的链表和一个索引块 ，其中数据块存储了按照索引键顺序的数据，索引块存储了各数据块的范围，示例如下：

随着增删改的进行，Component的个数也会逐渐增多，LSM查询需要检查更多的Component，这样会导致查询性能的下降。为了解决这个问题，磁盘上的Component需要不断合并来降低Component的个数。目前实践上有两种策略来进行这种合并。分级合并策略（leveling merge policy）：每一个level有一个Component，但是level L的容量是level L-1的T倍，因此上一级将要合并多次才能将下一级填满，然后启动下一级的合并。这种合并策略优化了读性能，因为合并后Component个数变得更少。合并示意图如下：

还有一种称之为层级合并策略（tiering merge policy），每一个level又分成T个Component。这样对于写操作，因为它降低了合并的频率。合并示意图如下：

3.2. 优化技术

当前有两个广泛使用的优化方案：布隆过滤器和分区技术。可以将布隆过滤器部署在LSM磁盘Component之上，当做一个独立的过滤器使用，对于点查询，先通过布隆过滤器判断是否存在，由于布隆过滤器的判非特性，当不满足布隆过滤器，也就没有必要读取该Component了。对于当Component是B+树的情况，也可以将布隆过滤器部署在叶子上来达到降低IO的目的。

另一种常见的方法是采用分区技术，即每一个Component又按照范围划分成多个不同范围的小的Component（每个称之为SSTable）。这样做有很多好处：首先，可以将大的Component的合并分割成多个小的合并，并且分区还可以优化顺序递增主键和非均匀更新的性能。目前主流的数据库比如LevelDB和RocksDB都是采用的这种分区技术，称之为分区合并策略（Partitioned Leveling Merge Policy）。由于level 0是存储在内存，所以没必要分区。当将一个SSTable从level L合并到SSTable从level L+1 时，只需要把与level L有交集的level L+1取出来，与level L合并生成新的level L+1上的SSTable即可，其他的不需要处理。下图显示了当需要将level 1的0-30合并到level 2时，只需要处理level 2的0-15和16-32两个SSTable即可。合并后，旧的SSTable直接交给回收系统进行垃圾回收。对于一次合并过程究竟选择哪一个SSTable，不同数据库系统采用不同的方案，LevelDB采用round-robin方式。

分区也能应用在层级合并策略上。但是有一个主要的问题是，由于每个level会有多个SSTable，这样必须要保证交叠的SSTable按照新旧的关系排序，才能保证正确性。通过SSTable在每一level的组织情况，可以分为水平分组和垂直分组模式。垂直分组保证了在水平方向key的范围不交叠。分区层级的垂直分组下的合并方法如下，组内范围交叠，组件范围不交叠，合并的时候分组合并到下一级与该组有交叠关系的所有组。可以看到0-31和0-30合并前属于一组，合并后分在了不同的组。还有分区层级的水平分组合并方法，在此不赘述了。

3.3. 并发控制和恢复机制

根据事物的隔离级别要求，当前的基于LSM的系统应用锁技术和多版本技术处理并发控制。由于LSM本身就存有多版本数据，只需要给LSM树增加一个元文件用来控制版本即可。为了防止正在用的Component被删除，给每个Component维护一个索引数，对该Component的操作都是先给该索引数+1，使用完后-1即可。由于写操作都是之间写入内存，系统需要引入日志系统来保证数据的一致性。为了简化恢复过程，目前的系统大多采用基于no-steal的内存管理策略，即未提交事物不落盘，只有redo日志，没有undo日志的策略。当crash发生后，有效的Component应该能够被恢复。对于非分区的LSM树可以通过对每一个磁盘的Component加一个起始和结束时间戳。恢复过程可以通过所有不相交的时间戳区间重建Component列表。当时间戳区间相交时，则只需要最长间隔Component即可，因为该Component是被最后合并的，其他的直接删除即可。对于分区LSM树，则这种时间戳就不够用了。对于LevelDB和RocksDB，实际上是维护了一个独立的元数据日志，记录的对SSTables的增加和删除过程，通过回访这个元数据日志，即可重建Component列表。

4. 结论 

LSM树结构的存储结构由于在超高的写性能，高空间利用率等的优势，在当今NoSQL数据库系统广泛应用。并且随着新硬件（比如SSD/NVM、多核、Direct IO等）的快速发展，适应相关需求的新的优化方法层出不穷，加快了LSM的快速发展。

5. 参考资料

1.https://en.wikipedia.org/wiki/Log-structured_merge-tree

2.https://www.researchgate.net/publication/329772189_LSM-based_Storage_Techniques_A_Survey

3.https://researcher.watson.ibm.com/researcher/files/us-wtan/DiffIndex-EDBT14-CR.pdf

4. http://distributeddatastore.blogspot.com/2013/08/cassandra-sstable-storage-format.html

腾讯数据库技术团队对内支持QQ空间、微信红包、腾讯广告、腾讯音乐、腾讯新闻等公司自研业务，对外在腾讯云上依托于CBS+CFS的底座，支持TencentDB相关产品，如CynosDB、CDB、CTSDB、MongoDB、CES等 。 腾讯数据库技术团队专注于持续优化数据库内核和架构能力，提升数据库性能和稳定性，为腾讯自研业务和腾讯云客户提供“省心、放心”的数据库服务。 此公众号旨在和广大数据库技术爱好者一起推广和分享数据库领域专业知识，希望对大家有所帮助。