haizdl
作者haizdl2020-10-15 11:13
技术经理, 大连

DB 存储引擎:LSM-Tree 存储引擎详细分解

字数 6018阅读 4868评论 0赞 3

【摘要】:LSM树,即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构,它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的,只是具体的实现不同。传统关系型数据库使用B-Tree或一些变体作为存储结构,能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷,那就是逻辑上相离很近但物理却可能相隔很远,这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多,为了提升IO性能,我们需要一种能将随机操作变为顺序操作的机制,于是便有了LSM树。LSM树能让我们进行顺序写磁盘,从而大幅提升写操作,作为代价的是牺牲了一些读性能。本文基于LSM存储引擎的数据特点、架构、关键算法等进行讨论分解并展示详实的LSM树存储引擎视图,以便更好掌握相关数据库技术。

【关键字】:存储引擎;LSM-Tree;顺序读写

1. 存储引擎简介

接触数据库比较深的人可能对存储引擎并不陌生,但是大多数数据库管理员可能对存储引擎并不熟悉,因为我们大多数关系型数据库的学习者并不需要关心存储引擎的选择和应用,因为我们熟知的 Oracle 、 SQL Server 等数据库基本只有一种存储引擎,没有给大家选择和设计的机会。但是如果我们接触 MySQL 以及其他一些 NOSQL 数据库比较多的人可能对存储引擎就会深有感受。

那么存储引擎是什么?它主要解决什么问题呢?

首先,我们认为存储引擎就是如何为了解决存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。用户可以根据应用的需求选择更适合自己应用场景的存储引擎来提高数据库的性能和数据的访问效率。常见的存储引擎有哈希存储引擎、 B 树存储引擎、 LSM 树存储引擎等三种。不同的存储引擎对数据的结构、数据的存储方式、数据的读取方式等都有不同的要求和特点。今天我们要跟大家分享的是 LSM-Tree (Log-Structured Merge-Tree) 存储引擎,大多 NoSQL 数据库核心思想都是基于 LSM 来做的,只是具体的实现不同。例如 LevelDB 、 RocksDB 、 Hbase 、 Cassandra 等。 LSM 树通过尽可能减少写磁盘次数,实际落地存储的数据按 key 划分,形成有序的不同文件;结合其 “ 先内存更新后合并落盘 ” 的机制,尽量达到顺序写磁盘,尽可能减少随机写;对于读则需合并磁盘已有历史数据和当前未落盘的驻于内存的更新。 LSM 树存储支持有序增删改查,写速度大幅提高,但随机读取数据时效率低。

2. LSM-Tree 存储引擎设计原理

2.1 LSM-Tree 合并思想

LSM 树由两个或以上的存储结构组成,比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中,称为 C0 tree ,具体可以是任何方便健值查找的数据结构,比如红黑树、 map 之类,甚至可以是跳表。另外一个存储结构常驻在硬盘中,称为 C1 tree ,具体结构类似 B 树。 C1 所有节点都是 100% 满的,节点的大小为磁盘块大小。


图 2.1.1 LSM-Tree 存储结构 1


图 2.1.2 LSM-Tree 存储结构 2

如上图所示,数据库采用了基于 LSM Tree 结构作为数据库的存储引擎,数据被分为基线数据( SSTable )和增量数据( MemTable )两部分,基线数据被保存在磁盘中,当需要读取的时候会被加载到数据库的缓存中,当数据被不断插入(或者修改时)在内存中缓存增量数据,当增量数据达到一定阀值时,就把增量数据刷新到磁盘上,当磁盘上的增量数据达到一定阀值时再把磁盘上的增量数据和基线数据进行合并。这个本身是 LSM 的核心设计思想,非常朴素,就是将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,从而大幅度提升性能。关于树的节点数据结构,不同数据库在基于 LSM-Tree 思想实现具体存储引擎的时候,可以根据自己的特点去定义。

2.2 LSM-Tree WAL

谈及 LSM ( Log Structured Merge Tree )树存储引擎,从字面意思上,其实我们基本能看到两层意思,第一个是 Merge ,就是我们上一节说到的合并思想;另外一个就是 Log ,就是我们接下来要说的 WAL 文件,从下面展示的基于 LSM 存储引擎的写的流程当中,我们可以看到 WAL 就是数据库的一个日志文件。

图 2.2.1 LSM-Tree 写数据流程图
当插入一条数据时,数据先顺序写入磁盘保存的 WAL 文件中,之后插入到内存中的 Memtable 当中, Memtable 实际上保存的数据结构就是我们所述的内存当中的小树。这样就保证了数据的持久化,即使因为故障宕机,虽然内存里面的数据已经丢失,但是依然可以通过日志信息恢复当初内存里面的数据信息,并且都是顺序写,速度非常快。当 memtable 写入文件 SSTable 后,这个 log 文件的内容就不再需要了。而新的 memtable 会有新的 log 文件对应。

2.3 LSM-Tree SSTable

SSTable ( Sorted String Table )是一种拥有持久化,有序且不可变的的键值存储结构,它的 key 和 value 都是任意的字节数组,并且了提供了按指定 key 查找和指定范围的 key 区间迭代遍历的功能。 SSTable 内部包含了一系列可配置大小的 Block 块,典型的大小是 64KB ,关于这些 Block 块的 index 存储在 SSTable 的尾部,用于帮助快速查找特定的 Block 。当一个 SSTable 被打开的时候, index 会被加载到内存,然后根据 key 在内存 index 里面进行一个二分查找,查到该 key 对应的磁盘的 offset 之后,然后去磁盘把响应的块数据读取出来。当然如果内存足够大的话,可以直接把 SSTable 直接映射到内存中,从而提供更快的查找。在 LSM-Tree 里, SSTable 有一份在内存里面,其他的多级在磁盘上。

图 2.3.1 LSM-Tree SSTable
SSTable 在后台是要经过不断地排序合并,文件随着层次的加深,其大小也逐步变大。同时它也是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。如图下图所示的情况, leve0 的 SSTable 达到数据量的阀值之后,会经过排序合并形成 Level1 的 SSTable , Level1 的 SSTable 达到阀值之后,会经过排序合并成为 Level2 的 SSTable 文件。

图 2.3.2 LSM-Tree SSTable’s merge
以上图中所示的文件合并过程是一个排序合并的过程,因此每一层都包含大量 SSTable 文件,但是键值值范围不重复,这样查询操作只需要查询这一层的一个 SSTable 文件即可。

3. LSM-Tree 存储引擎读写算法

3.1 LSM-Tree 数据写入过程

说到 LSM-Tree 存储引擎的写入,分为实时的写入以及滞后的刷盘以及合并两部分过程。实时的写入主要涉及到 WAL 日志以及 MemTable ,我们前面说过 WAL 是一个顺序日志文件,而 MemTable 是内存当中的 Skip-List 的数据结构,实时写入的时候:

首先,将数据顺序写入 WAL Log 文件,由于是顺序追加,没有检索的过程,会非常快。

然后,将数据写入 MemTable ,也涉及到在 Skip-List 当中追加链的操作,内存处理也非常快。

当内存 Memtable 当中的数据达到一定的规模触及阀值条件的时候,后台会启动排序及合并操作,将 MemTable 当中的数据排序并刷入磁盘形成 SSTable ,同时周期性的将 SSTable 文件再进行排序分组,形成更大的 SSTable 文件,并转入下一个 Level 存储。

3.2 LSM-Tree 数据修改过程

LSM-Tree 存储引擎的更新过程其实并不存在,它不会像 B 树存储引擎那样,先经过检索过程,然后再进行修改。它的更新操作是通过追加数据来间接实现,也就是说更新最终转换为追加一个新的数据。只是在读取的时候,会从 Level0 层的 SSTable 文件开始查找数据,数据在低层的 SSTable 文件中必然比高层的文件中要新,所以总能读取到最新的那条数据。也就是说此时在整个 LSM Tree 中可能会同时存在多个 key 值相同的数据,只有在之后合并 SSTable 文件的时候,才会将旧的值删除。

3.3 LSM-Tree 数据删除过程

LSM-Tree 存储引擎的对数据的删除过程与追加数据的过程基本一样,区别在于追加数据的时候,是有具体的数据值的,而删除的时候,追加的数据值是删除标记。同样在读取的时候,会从 Level0 层的 SSTable 文件开始查找数据,数据在低层的 SSTable 文件中必然比高层的文件中要新,所以如果有删除操作,那么一定会最先读到带删除标记的那条数据。后期合并 SSTable 文件的时候,才会把数据删除。

3.4 LSM-Tree 数据读取过程

对于 LSM-Tree 的读取操作,按照 Memtable 、 SSTable 的架构来讲,那么肯定是先扫描 MemTable 当中的元素,然后扫描 SSTable 文件当中的数据,然后找到相应数据。虽然我们讲过 SSTable 本身是有序的数据元素片段,而且对于读取概率较大的数据基本会在 Memtable 当中,但是这依然会造成巨大的扫描,读取效率会非常低下。

图 2.3.3 LSM-Tree Index
虽然 LSM-Tree 的设计思想并不是为了随机读的性能而设计,但是为了改善随机读的效率,那么在其数据结构的设计当中,其实是有考虑索引设计的。正如图 2.3.3 所示,在每一个 SSTable 文件的尾部是有记录数据位置的索引信息的。这些信息是可以被流失读入内存当中,然后形成一个稀疏索引,那么检索的时候如果从 MemTable 当中没有检索到数据,接下来需要访问 SSTable 的时候,是可以先通过这个稀疏索引定位到 SSTable 的具体位置,然后在准确读取数据,这样的话就会大大提高随机读取的效率。

4. LSM-Tree 存储引擎优略分析

4.1 LSM-Tree 的优势

我们通过对 B-Tree 存储引擎的学习,应该了解到 B-Tree 存储引擎的随机检索能力是非常强的,一方面它可以通过平衡树的算法,通过少数几次二分法思想的查找就可以在索引定位数据的位置;另外一方面它也不用担心像哈希存储引擎那样需要考虑冲突的解决办法,需要考虑哈希函数的健壮性问题。对于数据存取的模式来讲, B+Tree 则是将数据拆分为固定大小的 Block 或 Page, 一般是 4KB 大小,和磁盘一个扇区的大小对应, Page 是读写的最小单位,更适合固定大小的结构化数据结构的存取。总结以上两点, B-Tree 存储引擎应该在结构化的数据的随机读取方面是无可比拟的。

但是,在高吞吐写的场景下, B-Tree 就显得力不从心了。主要原因就是它的插入、更新、删除的这些操作都是建立在检索的前提之下的,虽然这种操作更适合事务型的业务场景,但是对于事务型不是非常强,但是吞吐量巨大的场景并不适合。这就是 LSM-Tree 诞生的根本原因, LSM-Tree 正是为了克服这个问题,通过将数据增删改全部转化为顺序写入从而显著提高写的性能。这个特点在分布式系统上更为看重,当然针对读取普通的 LSM-Tree 结构,在使用索引或者缓存优化后的也可以达到 O ( logN )的复杂度。因此对于持续写入数据量大,数据和时间相关,编码到 key 值中很容易使 key 值进行排序的这种场景是最适合 LSM-Tree 存储引擎的。这个时候大家可能会联想到哈希存储引擎,其实也容易区分:首先,哈希存储引擎的索引需要一次性全部 Load 到内存当中;其次,哈希存储引擎的 Key 是无法正常排序的;再次,不是所有的数据都可以用哈希函数套用的,也不是所有键值数据都能很好处理冲突问题。

4.2 LSM-Tree 的劣势

基于 LSM-Tree 分层存储能够做到写的高吞吐,带来的副作用是整个系统必须频繁的进行 compaction ,写入量越大, Compaction 的过程越频繁。而 compaction 是一个 compare & merge 的过程,非常消耗 CPU 和存储 IO ,在高吞吐的写入情形下,大量的 compaction 操作占用大量系统资源,必然带来整个系统性能断崖式下跌,对应用系统产生巨大影响,当然我们可以禁用自动 Major Compaction ,在每天系统低峰期定期触发合并,来避免这个问题。

另外 LSM-Tree 的更新、删除全部是通过增加新数据间接实现,那么 Key 值必然存在多版本,而且事务锁的机制与 B-Tree 相比而言会宽松很多,而且键值重复很多,这也就导致了它不适合事务要求非常强的结构化数据处理场景。

5. 总结展望

总结来看,我们通过对 LSM-Tree 存储引擎的合并思想、数据处理算法等的了解,基本了解了它诞生的缘由, LSM-Tree 存储引擎就是为了高吞吐量数据写入场景而设计。在了解了它的最大优点之后,各个数据库在利用它实现自己的读写算法的同时也会根据特殊场景、特殊配置等采取各种改进方式来发挥它的优势的同时避免劣势的放大,因此具体实现方式上有很多 LSM-Tree 的变种,本文就不做具体讨论,希望同业能基于此而深入研究并分享更多具体实现方面的分享。

【 参考文献】

[1] Patrick O'Neil1, Edward Cheng2 Dieter Gawlick3: The Log-Structured Merge-Tree (LSM-Tree)

[2] https://www.cnblogs.com/fxjwind/archive/2012/06/09/2543357.html

[3] https://cloud.tencent.com/developer/article/1441835

[4] http://www.codinglabs.org/html/theory-of-mysql-index.html

如果觉得我的文章对您有用,请点赞。您的支持将鼓励我继续创作!

3

添加新评论0 条评论

Ctrl+Enter 发表

作者其他文章

相关文章

相关问题

相关资料

X社区推广