共计 5406 个字符，预计需要花费 14 分钟才能阅读完成。
摘要：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+ 树，也是十分值得深刻学习的，当前有机会再对其进行深入分析～
点击关注，第一工夫理解华为云陈腐技术~