面对 key 数量多和区间查询低效问题：Hash 索引趴窝，LSM 树申请出场
摘要：Hash 索引有两个明显的限制：（1）当 key 的数量很多时，维护 Hash 索引会给内存带来很大的压力；（2）区间查询很低效。如何对这两个限制进行优化呢？这就轮到本文介绍的主角，LSM 树，出场了。
我们通过 append-only log 的数据结构，实现了一个具备高写入性能的 key-value 数据库。append-only log 之所以有很高的写入性能，主要得益于磁盘的顺序写入。这可能违反了我们对磁盘的认知，因为在我们的印象中，写磁盘总是很慢。其实不然，准确地说应该是随机写磁盘很慢，因为在写之前可能会进行多次寻址。如果只是顺序写磁盘，性能是非常的高，如下的一个 ACM 报告中显示，顺序写磁盘甚至比随机写内存的性能还要高！
举个例子，Kafka 是一个高性能的消息队列，它的厉害之处就在于极致地利用磁盘的顺序写入性能，如果生产者和消费者的速率相当，消息甚至可以在操作系统的 Page Cache 层面就完成了传递。所以，以后别再认为写磁盘很慢了！
append-only log 大幅提升了数据写入性能，但是随之而来的是，非常低的数据读取性能。针对这一点，我们采用 Hash 索引进行了优化，优化的效果也非常的显著。然而，Hash 索引有两个明显的限制：（1）当 key 的数量很多时，维护 Hash 索引会给内存带来很大的压力；（2）区间查询很低效。
如何对这两个限制进行优化呢？
这就轮到本文介绍的主角，LSM 树，出场了。
LSM 树（Log-Structured Merge Tree）并不是一种数据结构，准确来说是一种存储模型，由 MemTable、Immutable MemTable、SSTable 等部分组成。它也是利用了 append-only log 的优势，大幅提升了写入性能。同时，因为 key 的存储有序性，所以具备了不错的读取性能，也克服了上文所述 Hash 索引的两个限制。下面，本文将一步步分析 LSM 树是如何做到这一点的。
SSTable
在最简单的数据库例子中，因为数据是无序存储的，所以在读取某个 key 的值时，就需要遍历整个数据文件，算法复杂度是 O(n)。为了提升读性能，我们不得不在内存中维护所有 key 的 Hash 索引。
假如存储数据时，对记录按照 key 进行排序的会怎样？
对于 key 有序存储这种情况，即使不用 Hash 索引，也能得到很好的查询效率，因为我们可以使用二分查找法（Binary Search）来快速找到 key 所在的位置，算法复杂度是 O(logn)。LSM 树正是采用 key 有序这种方式来组织数据存储的，并称之为 SSTable。
SSTable（Sorted String Table）是 LSM 树最基础的一个存储结构，存储在磁盘中，并且数据按照 key 进行排序的。数据保持 key 有序的好处是可以在 O(logn)的时间下，快速找到一个 key 值，相比于纯粹的 append-only log 有了很大的提升。但是，如果所有的数据都存储在一个 SSTable 上，数据量一大，查询效率也会下降。因此，LSM 树通常会将数据分散存储在多个 SSTable 中，并且记录每个 SSTable 的最大 key 和最小 key，这样就能快速定位到一个 key 存储在哪个 SSTable 上了。
SSTable 数据查找示例
这里只是介绍了一种比较简单的 SSTable 实现方式，实际上，各种 LSM 树存储引擎对 SSTable 的实现都有所差异，比如 LevelDB 就将 SSTable 划分成两大块，数据存储区存储 key:value 数据，数据管理区存储索引等数据。
那么怎样才能保证 SSTable 的有序性呢？
类似的在磁盘中维护数据有序的存储结构最常见的当属 B/B+树了，如果对 SSTable 也采用类似的存储结构，那么带来的第一个问题就是每次写入都会伴随着磁盘的随机写，从而影响了数据的写入性能，这明显就违反了 LSM 树的初衷。为了同时兼顾 SSTable 的有序性以及写入性能，LSM 树采用了 MemTable 这一组件。
MemTable
相比于磁盘上维护一个有序的数据结构，在内存上实现数据有序要简单得多，而且具备较高的读写性能，常见的有序数据结构有红黑树、AVL 树、跳表等，不管你插入的顺序如何，读出来的数据总是有序的。MemTable 正是 LSM 维护在内存中的一个有序的数据结构，接下来我们看下 LSM 是如何利用 Memtable 做到同时兼顾 SSTable 的有序行和写入性能的：
1、当写入请求过来时，先将 record 写入到 Memtable 中，这样就能保证 record 在内存中有序了，而且具备较高的写入性能。
2、当 Memtable 的大小达到一定的阈值后（通常是几个 Mb 的大小），将 MemTable 转成 Immutable MemTable（一个只读不写的 MemTable），并创建新的 MemTable 接收写请求。
和《从Hash索引到LSM树（一）》中的 segment file 机制类似，一个时刻只有 current segment file 接收写请求，其他的只读不写。
3、通过后台任务，定时将 Immutable MemTable 的数据刷到 SSTable 中，因为 Immutable MemTable 本身的有序性，所以就能保证 SSTable 中的数据是有序的，而且数据写入 SSTable 文件时完全是顺序写入，做到了有序性和写入性能的兼顾。
4、当读请求过来时，查找的顺序是 MemTable->Immutable MemTable->SSTable，找到则返回，否则一步步执行下去。
Memtable 同时兼顾有序和写性能
Memtable 底层通常采用跳表来实现（LevelDB、HBase 都采用了这一实现方法），相比较 AVL 和红黑树，跳表在插入数据的时候可以避免频繁的树节点调整操作，所以写入效率很高，而且实现起来也更简单些。
LsmKvDb
使用 LSM 树作为存储引擎的数据库，通常对 SSTable 进行分层管理，方便查询以及后续的 Compact 操作。本文也将采用对 SSTable 进行分层的架构实现 LsmKvDb。
LsmKvDb 存储架构
首先对 Level 进行抽象，每个 Level 都由多个 SSTable 组成：
LsmKvDb 的实现代码如下，写数据时写入 MemTable，当达到阈值后转 Immutable MemTable。Immutable MemTable 与 MemTable 具有相同的数据结构，唯一不同的是前者只读不写，后者既读也写。
Compaction
在文章《从Hash索引到LSM树（一）》已经对 Compaction 机制已经有了讲解，其目的是清除掉已经被覆写或删除了的纪录，避免数据存储文件无休止的增长下去。对于 LSM 树而言，该机制同样适用，随着数据的不断添加、更新和删除，一些 SSTable 之间必然存在着重叠的 key 或被删除的 key。通过 Compaction，可以将多个 SSTable 合并成一个，从而节省了磁盘空间。
在上篇文章中，对 segment file 的 compact 操作主要依赖于 Hash 索引。因为是索引覆盖全部的 key，所以可以很容易通过新的 segment file 的 Hash 索引来判断该 key 是否已经被处理过。但对于 SSTable 而言，并没有覆盖全部 key 的 Hash 索引，那么如何进行 compact 才高效呢？
得益于 SSTable 的有序性，我们可以应用归并排序算法来进行 compact 操作！
LSM 树的 Compaction 通常有三种类型，分别是 minor compact、major compact 和 full compact。
Minor Compact
minor compact 指的是将 Immutable MemTable 中的数据直接转存到 Level0 中的 SSTable。
minor compact
因为是直接将各个 Immutable MemTable 的数据转储成 SSTable，并没有做合并的操作，因此在 Level0 中，各个 SSTable 之间的 key 可能存在重叠的现象。
Major Compact
major compact 指的是将 Level n 中的 SSTable 合并到 Level n+1 中。
Level0 -> Level1
的合并步骤如下：
1、选中 Level0 中的最老的 SSTable sst0，然后在 Level0 中找到与sst0 的 key 存在重叠的所有 SSTable sst0...n。
2、在 Level1 中，选取所有与 sst0...n存在 key 重叠的 SSTable sst'0...m。
3、对sst0...n和sst'0...m采用多路归并排序算法进行合并，得到新的sst‘’0...k，并存储在 Level1 中。
4、删除sst0...n和sst'0...m。
major compact Level0 -> Level1
不同于 Level0，Level1 和 Level2 中各个 SSTable 之间并不存在 key 重叠的现象，因此 Level1 -> Level2 的合并会稍微简单些。
Level1 -> Level2
的合并步骤如下：
1、选中 Level1 中的最老的 SSTable sst0。
2、在 Level2 中，选取所有与 sst0存在 key 重叠的 SSTable sst'0...m。
3、对sst0和sst'0...m采用多路归并排序算法进行合并，得到新的sst''0...k，并存储在 Level2 中。
4、删除sst0和sst'0...m。
major compact Level1 -> Level2
Full Compact
full compact 指的是对 Level0、Level1、Level2 中所有的 SSTable 进行 compact 操作，同样也是采用多路归并排序算法。
full compact
通常 full compact 耗时较多，所以一般都会选择在流量较少的时刻进行。
优化 LSM 树
为 SSTable 引入 block
到目前为止，对于在一个 SSTable 中查找一个 key，我们首先会根据 min key 和 max key 判断该 key 是否属于该 SSTable 所属的范围，如果属于，则对 SSTable 采用二分查找法进行搜索。二分查找之所以在 LsmKvDb 中行得通，是因为这是一个简单的 SSTable 实现 —— 数据按string存储和n分隔。在实际的运用中，为了尽可能地利用磁盘空间，SSTable 中数据通常都是以字节码的形式存储，也不会以n分隔每条 record，这种情况下采用二分查找的实现就比较复杂了，而且效率也会太高。
一个常见的优化方法是，在 SSTable 中对 record 按照一定的 size 组织成多个 block，并以 block 为单位进行压缩。为了能够快速找到某个 key 所属的 block，需要在内存中维护每个 block 的起始 key 对应在 SSTable 中的 offset（一个稀疏的 Hash 索引）。
按 block 存储的 SSTable
在查找 key 的步骤如下：
1、根据索引定位到 key 所属的 block。
2、将该 block 加载到内存中，并解压。
3、对内存中的数据采用二分查找。
在设计 block 的大小时，应该利用磁盘的空间局部性原理，使得系统能够只花费一次磁盘 I/O 就能将整个 block 加载到内存中。
为 SSTable 引入 Bloom Filter
其实当目标 key 属于某个 SSTable 的 key 范围时，该 key 也不一定会存在于该 SSTable 中。但是到目前为止，只要目标 key 在某个 SSTable 的范围内，LsmKvDb 都会进行查找操作。随着系统中的 SSTable 数目的增多，查询效率必然会随之下降。
一个常见的优化方法时，为 SSTable 引入布隆过滤器 Bloom Filter。
Bloom Filter 是保存在内存中的一种数据结构，可以用来告诉你 “某样东西一定不存在或者可能存在”。它由一个超长的二进制位数组和一系列的 Hash 函数组成。二进制位数组初始全部为 0，当有元素加入集合时，这个元素会被一系列 Hash 函数计算映射出一系列的值，所有的值在位数组的偏移量处置为 1。如果需要判断某个元素是否存在于集合当中，只需判断该元素被 Hash 后的值在数组中的值，如果存在为 0 的，则该元素一定不存在；如果全为 1，则可能存在，这种情况可能有误判。
Bloom Filter
通过 Bloom Filter，我们可以很快就能判断目标 key 是否不存在于 SSTable 中，从而提升了读性能。
Google 的 Guava 库就提供了一个 BloomFilter 的实现，并且可以按需来设置误判率。
总结
本文承接上《从Hash索引到LSM树（一）》，主要介绍了 LSM 树的基本原理，并且在原来 append-only log 的基础上实现了一个简单的基于 LSM 树的 key-value 数据库 LsmKvDb。LSM 树主要由 MemTable、Immutable MemTable、SSTable 组成，其中 MemTable 和 Immutable MemTable 在内存中维护，而 SSTable 则存储在磁盘中。SSTable 的有序性使得 LSM 树在无需 Hash 索引的情况下具有不错的读取性能，而且支持区间查询；而 Memable 则使得 LSM 树具备很高的写入性能。
本系列文章，我们从一个最简单的 key-value 数据库起步，一步步通过 Hash 索引、LSM 树、布隆过滤器等技术手段对其进行了优化，从中也深入分析了各个技术点的实现原理。但数据库的索引技术远不止这些，比如最常用到的 B/B+树，也是非常值得深入学习的，以后有机会再对其进行深入分析～
版权声明: 本文为 InfoQ 作者【华为云开发者社区】的原创文章。
原文链接:【http://xie.infoq.cn/article/2b83232f313daf7668f807adc】。文章转载请联系作者。
提供全面深入的云计算技术干货 2020.07.14 加入
华为云开发者社区，提供全面深入的云计算前景分析、丰富的技术干货、程序样例，分享华为云前沿资讯动态，方便开发者快速成长与发展，欢迎提问、互动，多方位了解云计算！ 传送门：https://bbs.huaweicloud.com/
评论