摘要：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+树，也是十分值得深刻学习的，当前有机会再对其进行深入分析～
点击关注，第一工夫理解华为云陈腐技术~