前言
LSM 树，即日志结构合并树（Log-Structured Merge-Tree）是Google BigTable 和 HBase 的基本存储算法，它是传统关系型数据库的 B+ 数的改进。算法的关注重心是 “如何在频繁的数据改动下保持系统读取速度的稳定性”，算法的核心在于尽量保证数据是顺序存储到磁盘上的，并且会有频繁地对数据进行整理，保证其顺序性。而顺序性就可以最大程度保证数据的读取性能稳定。
在有代表性的关系型数据库如MySQL、SQL Server、Oracle中，数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中，则是使用日志结构合并树（Log-structured Merge Tree，LSM Tree）来组织数据。
一、B树，B+树，LSM树
1.1 B树
B树，又叫做平衡多路查找树。一个m阶的b树的特性如下：
- 树中的每个节点，最多有m个子节点。
- 除了根节点之外，其他的每个节点至少有ceil(m/2)个子节点，ceil函数为取上限函数。
- 所有的叶子节点都在同一层，叶子节点bubaohan任何关键信息。
- 每个非叶子节点都包含有n个关键字信息：{n,a0,k1,a1,k2,……,kn,an}，
- n的取值范围，[ceil(m/2)-1]<=n<=(m-1)
- Ki(i=1...n)为关键字，且关键字的信息按照顺序排序
- Ai(i=0...n)为指向子节点的指针，且Ai指向的子树节点的关键字信息必须大于ki，并且小于k(i+1)
上图为一个3阶的b树，即m=3
- 每个节点最多有3个子节点
- 每个节点最少有ceil(m/2)=2个子节点
- 每个节点至少有1<=n<=2个关键字信息
对于一棵节点为N阶数为M的树，查找和插入需要的比较次数为logM-1N~logM/1
1.2 B+树
B+树是b树的一个变种，差别如下
- 所有的叶子节点中包含了全部的关键字信息，以及指向含有这些关键词信息记录的指针
- 叶子节点中的关键字信息是有序链接的
- 非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储数据的数据层
1.3 LSM树
LSM树（log-Structured Merge-Trees）原理是将一棵大树拆分成了多棵小树，每棵小树其实是一个有序的b+树。数据写入首先写入到内存中，随着小树越来越大，小树flush到磁盘中。磁盘中的小树数量到达一定量后，对这些小树做merge操作，合并成了一棵大的b+树。LSM树牺牲了部分读性能（因为需要遍历多棵小树）来提高了写性能。
二、核心思想
LSM树核心就是放弃部分读能力，换取写入的最大化能力。LSM 树会将所有的数据插入、修改、删除等操作保存在内存中，当此类操作达到一定得数据量后，再批量地写入磁盘当中。而在写磁盘时，会和以前的数据做合并。在合并过程中，并不会像 B+ 树一样，在原数据的位置上修改，而是直接插入新的数据， 从而避免了随机写。
HBase的一个列簇（Column Family）本质上就是一棵LSM树（Log-StructuredMerge-Tree）。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，这里由于考虑并发性能，HBase选择了表现更优秀的跳跃表。磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。
LSM树本质上和B+树一样，是一种磁盘数据的索引结构。但和B+树不同的是，LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写），因此基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。
LSM树的索引一般由两部分组成，一部分是内存部分，一部分是磁盘部分。内存部分一般采用跳跃表来维护一个有序的KeyValue集合。磁盘部分一般由多个内部KeyValue有序的文件组成。
2.1 KeyValue结构：
LSM树中存储的是多个keyValue组成的集合。每一个KeyValue由一个字节数组来表示。如下图所示
总体来说，字节数组主要分为以下几个字段。其中Rowkey、Family、Qualifier、Timestamp、Type这5个字段组成KeyValue中的key部分。
• keyLen：占用4字节，用来存储KeyValue结构中Key所占用的字节长度。
• valueLen：占用4字节，用来存储KeyValue结构中Value所占用的字节长度。
• rowkeyLen：占用2字节，用来存储rowkey占用的字节长度。
• rowkeyBytes：占用rowkeyLen个字节，用来存储rowkey的二进制内容。
• familyLen：占用1字节，用来存储Family占用的字节长度。
• familyBytes：占用familyLen字节，用来存储Family的二进制内容。
• qualif ierBytes：占用qualif ierLen个字节，用来存储Qualif ier的二进制内
注意：HBase并没有单独分配字节用来存储qualif ierLen，因为可以通过keyLen和其他字段的长度计算出qualif ierLen。代码如下：
• timestamp：占用8字节，表示timestamp对应的long值。
• type：占用1字节，表示这个KeyValue操作的类型，HBase内有Put、Delete、Delete Column、DeleteFamily，等等。注意，这是一个非常关键的字段，表明了LSM树内存储的不只是数据，而是每一次操作记录。
Value部分直接存储这个KeyValue中Value的二进制内容。所以，字节数组串主要是Key部分的设计。
在比较这些KeyValue的大小顺序时，HBase按照如下方式（伪代码）来确定大小关系：
注意：在HBase中，timestamp越大的KeyValue，排序越靠前。因为用户期望优先读取到那些版本号更新的数据。
上面以HBase为例，分析了HBase的KeyValue结构设计。通常来说，在LSM树的KeyValue中的Key部分，有3个字段必不可少：
- Key的二进制内容。
- 一个表示版本号的64位long值，在HBase中对应timestamp；这个版本号通常表示数据的写入先后顺序，版本号越大的数据，越优先被用户读取。甚至会设计一定的策略，将那些版本号较小的数据过期淘汰（HBase中有TTL策略）。
- type，表示这个KeyValue是Put操作，还是Delete操作，或者是其他写入操作。本质上，LSM树中存放的并非数据本身，而是操作记录。这对应了LSM树（Log-Structured Merge-Tree）中Log的含义，即操作日志。
2.2 MemStore实现部分
HBase中对LSM树的实现，是在内存中用一个ConcurrentSkipListMap保存数据，即MemStore。ConcurrentSkipListMap是利用跳跃表（SkipList）的数据结构实现的。
跳跃表是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(logN)。
跳跃表的优势在于
- 比红黑树或其他的二分查找树的实现简单很多 2.并发场景下加锁粒度更小，提高并发性能。因此诸Redis、LevelDB、HBase等KV数据库，都把跳跃表作为一种维护有序数据集合的核心数据结构。
跳跃表可以看作是一种特殊的有序链表。跳跃表是由多层有序链表组成。最底一层的链表保存了所有的数据，为了提高链表的查询效率，通过每向上的一层链表依次保存下一层链表的部分数据作为索引，采用空间换取时间等方式提高效率。相邻的两层链表中元素相同的节点之间存在引用关系，一般是上层节点中存在一个指向下层节点的引用。
跳跃表的目的在于提高了查询效率，同时也牺牲了一定的存储空间，在跳跃表中查找一个指定元素的流程比较简单。如上图所示，以左上角元素作为起点：如果发现当前节点的后继节点的值小于等于待查询值，则沿着这条链表向后查询，否则，切换到当前节点的下一层链表。继续查询，直到找到待查询值为止（或者当前节点为空节点）为止。
跳跃表的构建稍微复杂一点，首先，需要按照上述查找流程找到待插入元素的前驱和后继；然后，按照如下随机算法生成一个高度值：
// p是一个(0,1)之间的常数，一般取p=1/4或者1/2
public void randomHeight(doubule p) {
int height = 0;
while(random.newtDouble < p) {
height++;
}
return height + 1;
}
最后，将待插入节点按照randomHeight生成一个垂直节点的位置（这个节点的层数位置正好等于高度值），之后插入到跳跃表的多条链表中去。假设height=randomHeight§，这里需要分两种情况讨论：如果height大于跳跃表的高度，那么跳跃表的高度被提升为height，同时需要更新头部节点和尾部节点的指针指向。如果height小于等于跳跃表的高度，那么需要更新待插入元素前驱和后继的指针指向。
2.3 磁盘文件实现部分-用多路归并实现LSM树的文件合并
随着写入的增加，内存数据会不断地刷新到磁盘上。最终磁盘上的数据文件会越来越多。所以LSM树的实现实际上是将写入操作全部转化为了磁盘的顺序写入，提高了写入性能。但是，这种设计是以牺牲一定的读操作性能为代价的，因为读取的时候，需要归并多个文件来获取满足条件的KV，非常消耗磁盘IO，这样读性能会很差，所以hbase内部采用多路合并思想异步地进行compaction把多个小文件合并成一个大文件，以提高读数据性能。
多路归并思想
回顾一下多路归并的算法思路，假设现在有K个文件，其中第i个文件内部存储有Ni个正整数（这些整数在文件内按照从小到大的顺序存储），如何将K个有序文件合并成一个大的有序文件？
可以使用多路归并算法进行实现。对每个文件设计一个指针，取出K个指针中数值最小的一个，然后把最小的那个指针后移，接着继续找K个指针中数值最小的一个，继续后移指针……直到N个文件全部读完为止。如下图示例所示：
具体实现上，可以用一个最小堆来维护K个指针，每次从堆中取最小值，开销为logK，最多从堆中取sum(Ni)次元素。
为了优化读取操作的性能，hbase会进行两种类型的compact。
minor compact：即选中少数几个Hfile,将他们多路归并成一个文件。这种方式的有点是可以进行局部的Compact,通过少量的IO减少文件个数，提高读取操作的性能。适合较高频率的执行。但它的缺点是只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。
major compact：将所有的HFile一次性多路归并成一个文件。这种方式的好处是，合并之后只有一个文件，这样读取的性能肯定是最高的。但它的问题是合并所有的文件可能需要很长的时间并消耗大量的IO走远，因此major compact不宜使用太频繁，可以选择周期性的执行，或者在集群空闲时手动执行。
2.4 布隆过滤器（Bloom Filter）
布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。
HBase为了提升LSM结构下的随机读性能，还引入了布隆过滤器（建表语句中可以指定），对应HFile中的Bloom index block，其结构图如下所示。
由于布隆过滤器只需占用极小的空间，便可给出 “可能存在” 和 “肯定不存在”的存在性判断。因此可以提前过滤掉很多不必要的数据块，从而节省了大量的磁盘IO。hbase的get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省了大量磁盘IO。
如果在表中设置了Bloomfilter，那么HBase会在生成StoreFile时包含一份bloomfilter结构的数据，称其为MetaBlock；MetaBlock与DataBlock（真实的KeyValue数据）一起由LRUBlockCache维护。所以，开启bloomfilter会有一定的存储及内存cache开销。
hbase中布隆过滤器的3中类型：
- none：关闭布隆过滤器功能
- row：按照rowkey计算布隆过滤器的二进制串并存储。get查询时，必须带rowkey.
- rowcol：按照rowkey+family+qualifier这3个字段拼出byte[]来计算布隆过滤器值并存储。如果查询时，get可以指定到这3个字段，则肯定可以通过布隆过滤器提高性能。
任何类型的get（基于rowkey或row+col）Bloom Filter的优化都能生效，关键是get的类型要匹配Bloom Filter的类型。基于row的scan是没办法走Bloom Filter的，因为Bloom Filter是需要事先知道过滤项的，对于顺序scan是没有事先办法知道owkey的，而get是指明了rowkey所以可以用Bloom Filter。
在使用布隆过滤器时，需要注意两个问题：
1、什么时候应该使用布隆过滤器？根据上面的描述，布隆过滤器的主要作用，是帮助HBase跳过那些显然不包括所查找数据的底层文件。那么，当所查找的数据均匀分布在所有文件中（当用户定期更新所有行时，就可能导致这种情况），布隆过滤器的作用就微乎其微，反而浪费了存储空间。相反，如果我们查找的数据只包含在少部分的文件中，就应该果断使用布隆过滤器。
2、应该选择行级还是行加列级布隆过滤器？很显然，行加列级因为粒度更细，占用的存储空间也就越多。因此，如果用户总是读取整行的数据，行级布隆过滤器就够用了。在可以选择的情形下，尽可能使用行级布隆过滤器，因为它在额外的空间开销和利用过滤存储文件提升性能之间取得了更好的平衡。
通过布隆过滤器，HBase就能以少量的空间代价，换来在读取数据时非常快速地确定是否存在某条数据，效率进一步提升。
三、LSM 树的读写
LSM 树读写架构图
LSM树的结构是横跨内存和磁盘的，包含memtable、immutable memtable、SSTable等多个部分。
memtable
顾名思义，memtable是在内存中的数据结构，用以保存最近的一些更新操作，当写数据到memtable中时，会先通过WAL的方式备份到磁盘中，以防数据因为内存掉电而丢失。memtable可以使用跳跃表或者搜索树等数据结构来组织数据以保持数据的有序性。当memtable达到一定的数据量后，memtable会转化成为immutable memtable，同时会创建一个新的memtable来处理新的数据。immutable memtable
顾名思义，immutable memtable在内存中是不可修改的数据结构，它是将memtable转变为SSTable的一种中间状态。目的是为了在转存过程中不阻塞写操作。写操作可以由新的memtable处理，而不用因为锁住memtable而等待。SSTable
SSTable(Sorted String Table)即为有序键值对集合，是LSM树组在磁盘中的数据的结构。如果SSTable比较大的时候，还可以根据键的值建立一个索引来加速SSTable的查询。下图是一个简单的SSTable结构示意：
写入操作
写操作首先需要通过WAL将数据写入到磁盘Log中，防止数据丢失，然后数据会被写入到内存的memtable中，这样一次写操作即已经完成了，只需要1次磁盘IO，再加1次内存操作。相较于B+树的多次磁盘随机IO，大大提高了效率。随后这些在memtable中的数据会被批量的合并到磁盘中的SSTable当中，将随机写变为了顺序写。
删除操作
当有删除操作时，并不需要像B+树一样，在磁盘中的找到相应的数据后再删除，只需要在memtable中插入一条数据当作标志，如delKey:1933，当读操作读到memtable中的这个标志时，就会知道这个key已被删除。随后在日志合并中，这条被删除的数据会在合并的过程中一起被删除。
更新操作
更新操作和000删除操作类似，都是只操作memtable，写入一个标志，随后真正的更新操作被延迟在合并时一并完成。
查询操作
查询操作相较于B+树就会很慢了，读操作需要依次读取memtable、immutable memtable、SSTable0、SSTable1…。需要反序地遍历所有的集合，又因为写入顺序和合并顺序的缘故，序号小的集合中的数据一定会比序号大的集合中的数据新。所以在这个反序遍历的过程中一旦匹配到了要读取的数据，那么一定是最新的数据，只要返回该数据即可。但是如果一个数据的确不在所有的数据集合中，则会白白得遍历一遍。
读操作看上去比较笨拙，所幸可以通过布隆过滤器来加速读操作。当布隆过滤器显示相应的SSTable中没有要读取的数据时，就跳过该SSTable。
布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
还有上面提到的索引文件，也可以加速读操作。
合并操作
由前面的增删改查操作来看，合并操作是LSM树最重要的操作。
合并操作有两个主要的作用：
合并内存中的数据到磁盘中。
由于将内存数据合并到磁盘当中会产生大量的小的集合，并且更新和删除操作会产生大量的冗余数据，通过合并操作可以减少集合中的冗余数据并降低读操作时线性扫描的耗时。
参考：
https://blog.csdn.net/u011047968/article/details/125298135
https://www.cnblogs.com/swordfall/p/10567468.html
https://segmentfault.com/a/1190000023390528
https://blog.csdn.net/breakout_alex/article/details/111350371
