聊聊lLSM-TREE存储引擎

白鳝的洞穴 2021-07-06

1684

前阵子有个网友在公众号留言，想让老白聊聊LSM-TREE存储引擎。实际上前段时间老白写过一个关于LSM-TREE存储引擎的HTAP数据库的系列，不过那篇文章更主要是分析了近些年较为流行的几个HTAP分布式数据库的底层技术的优缺点，虽然对LSM-TREE做了一些描写，但是并不深入。今天我在此系列第一篇的基础上，对LSM-TREE存储引擎做一些更详细的分析。

近些年来LSM-TREE存储引擎十分热门，很多数据库都采用了LSM-TREE存储引擎，可能大多数搞数据库的都听说过，不过可能不一定会去认真深究LSM-TREE是怎么回事。实际上LSM-TREE是影响我们这个世界的谷歌三大论文中的BigTable中提出的，LSM-TREE是Log Structured Merge Tree的简称，维基百科的描述如下图。

维基百科对LSM-TREE的定义中提出，LSM-TREE是一种对于高性能写入十分有效的数据结构。在LSM-TREE的设计思路中，LSM-TREE基于谷歌的著名的五分钟理论，也就是说如果某个数据每5分钟至少被访问一次，那么这个数据最好存放在内存里。LSM-TREE存储引擎也是计算机系统近些年快速发展，CPU、内存的价格大幅度下降的结果。因为实现LSM-TREE存储引擎的关键是大内存和强大的CPU处理能力。

LSM-TREE的数据在C0阶段是存储在内存中的SSTABLE中的，这些SSTABLE按照一定大小的SEGMENT存储在内存中，当一个SEGMENTS写满后进入锁定状态，新数据将被写在新的SEMGENTS中，而锁定状态的SEGMENT经过MERGE后会被写入磁盘进行持久化。

大家可能也看出来了，这种SSTABLE写入的时候，如果是UPDATE操作，是不管某条数据是否存在的，只管把最新的数据写入SSTABLE，然后当一个SEGMENT写满后整体刷盘，这样的架构对于大并发的数据写入操作/UPDATE操作比传统的以HEAP/BTREE的模式要快得多。

LSM-TREE和数据库又是什么关系呢？我们借用互联网上的一张图来解释一下。

数据库一般包括sql引擎和存储引擎两部分。存储引擎可能把数据存放在持久化存储设备（比如硬盘）上，或者易失性的内存里（比如内存数据库）。在数据库发展的这些年里，存储引擎一直是B+TREE结构占主导地位。随着这些年分布式数据库的发展，谷歌论文BigTable中的LSM-TREE成为一种存储引擎的新宠。下面的图同样来自于互联网，列出了两大阵营中的主要数据库产品。传统的内存数据库实际上在存储结构上也采用了堆结构。内存数据库与普通的磁盘数据库之间的差异也是很大的，绝对不是把磁盘文件全部放入内存而已。因为内存数据库的数据访问基本上是基于memcpy的，而传统的磁盘库要使用disk/file io接口去访问数据文件。这里我们不重点讨论内存数据库引擎，普通的内存数据库引擎大部分是HEAP存储结构的特殊的存储引擎，而一些新的内存数据库也开始使用LSM-TREE存储结构了。

我们可以看到，大多数的传统数据库或者非分布式数据库都采用了B-TREE结构的存储，表的数据存储在堆结构的数据块中，索引使用B-TREE结构。而一些新型的分布式数据库都采用LSM TREE存储结构。

基于B-TREE结构的存储引擎具有较好的事务处理能力，但是对于大规模的数据写入性能与LSM-TREE相比有巨大的差距。因为LSM-TREE采用内存缓冲+大批量顺序写入的方式，对于高写入的场景具有极高的性能。特别是在更适合顺序访问的SSD盘。LSM-TREE还很适合于分层存储，其中可以利用具有不同性能/成本特性的不同类型的存储，例如RAM，SSD，HDD和远程文件存储（例如AWS S3）。

不过LSM TREE也存在自身的不足，在大吞吐量读的场景下，LSM-TREE需要消耗更多的IO，另外为了保证LSM-TREE的性能，需要进行比较和合并操作，这个操作相当消耗CPU和IO资源。

基于上述的原理，LSM-TREE是一种十分适合于大型写入场景的存储引擎，不过由于SSTABLE的MERGE的需要，会更加消耗CPU和IO资源。不过随着写在计算于IO能力的极大提升，这种存储引擎对于现代的计算机系统来说，算是十分适合的。

这种存储引擎中，如果仅仅是一些不做UPDATE的时序数据或者指标数据，那么其写入是十分高效的，如果数据存在大量的UPDATE操作，那么一条记录在数据库中可能存在多个副本。基于LSM-TREE存储引擎的数据库的MVCC也是基于这总多副本机制来实现的。因此，在做COMPARE AND MERGE的时候，不仅仅要考虑如何高效的进行合并，还要考虑MVCC多版本的有效性控制，因为数据库操作的UNDO和一致性读都是要依靠这个多副本机制来实现的。因此LSM-TREE要用于关系型数据库，需要有更为强大的多副本控制能力。

还有一点要注意的是，COMPARE AND MERGE操作是在后台进行的，数据库要实现既能够高效的合并，又不会影响应用访问相关数据，对算法有较高的要求。如果某个热数据并发访问十分频繁，此时正好在做MERGE处理，那么此时数据库的热块冲突会被极大的放大，严重时会对数据库应用的性能造成巨大的影响。而如果MERGE操作延后太多，又会导致UPDATE十分频繁的表的容量出现暴涨，从而影响全表扫描的性能。

基于存储引擎方面存在的一些缺点，基于LSM-TREE存储引擎的数据库，对于UPDATE十分频繁，同时访问热度又较高的情况，如何保障性能是一个难点。因此如果我们在测试一个基于lsm-tree存储引擎的数据库的时候，不要光是测试并发写入的性，这是所有LSM-TREE存储引擎的数据库都很强的地方。而是要多测试一些UPDATE十分频繁的表上面的一些复杂查询SQL的性能，特别是全表扫描等操作的性能。当然如果你的应用中不存在这样的场景，那么你就可以比较放心的使用基于LSM-TREE存储引擎的数据库了。

数据库

文章转载自白鳝的洞穴，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

聊聊lLSM-TREE存储引擎

评论