HBase的一个列簇（Column Family）实质上就是一棵LSM树（Log-StructuredMerge-Tree）。LSM树分为内存局部和磁盘局部。内存局部是一个保护有序数据汇合的数据结构。一般来讲，内存数据结构能够抉择均衡二叉树、红黑树、跳跃表（SkipList）等保护有序集的数据结构，这里因为思考并发性能，HBase抉择了体现更优良的跳跃表。磁盘局部是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。

LSM树实质上和B+树一样，是一种磁盘数据的索引构造。但和B+树不同的是，LSM树的索引对写入申请更敌对。因为无论是何种写入申请，LSM树都会将写入操作解决为一次程序写，而HDFS善于的正是程序写（且HDFS不反对随机写），因而基于HDFS实现的HBase采纳LSM树作为索引是一种很适合的抉择。

LSM树的索引个别由两局部组成，一部分是内存局部，一部分是磁盘局部。内存局部个别采纳跳跃表来保护一个有序的KeyValue汇合。磁盘局部个别由多个外部KeyValue有序的文件组成。

1.KeyValue存储格局

一般来说，LSM中存储的是多个KeyValue组成的汇合，每一个KeyValue个别都会用一个字节数组来示意。这里，首先须要来了解KeyValue这个字节数组的设计。

以HBase为例，这个字节数组串设计如图所示。

总体来说，字节数组次要分为以下几个字段。其中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.多路归并

先看一个简略的问题：当初有K个文件，其中第i个文件外部存储有Ni个正整数（这些整数在文件内依照从小到大的顺序存储），如何设计一个算法将K个有序文件合并成一个大的有序文件？在排序算法中，有一类排序算法叫做归并排序，外面就有大家熟知的两路归并实现。当初相当于K路归并，因而能够拓展一下，思路相似。对每个文件设计一个指针，取出K个指针中数值最小的一个，而后把最小的那个指针后移，接着持续找K个指针中数值最小的一个，持续后移指针……直到N个文件全副读完为止，如图所示。

算法复杂度剖析起来也较为容易，首先用一个最小堆来保护K个指针，每次从堆中取最小值，开销为logK，最多从堆中取次元素。因而最坏复杂度就是

3. LSM树的索引构造

一个LSM树的索引次要由两局部形成：内存局部和磁盘局部。内存局部是一个ConcurrentSkipListMap，Key就是后面所说的Key局部，Value是一个字节数组。数据写入时，间接写入MemStore中。随着一直写入，一旦内存占用超过肯定的阈值时，就把内存局部的数据导出，造成一个有序的数据文件，存储在磁盘上。LSM树索引构造如图所示。内存局部导出造成一个有序数据文件的过程称为flush。为了防止f lush影响写入性能，会先把以后写入的MemStore设为Snapshot，不再答应新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让前面的数据写入。一旦Snapshot的MemStore写入结束，对应内存空间就能够开释。这样，就能够通过两个MemStore来实现稳固的写入性能。


LSM树索引构造

随着写入的减少，内存数据会一直地刷新到磁盘上。最终磁盘上的数据文件会越来越多。如果数据没有任何的读取操作，磁盘上产生很多的数据文件对写入并无影响，而且这时写入速度是最快的，因为所有IO都是程序IO。然而，一旦用户有读取申请，则须要将大量的磁盘文件进行多路归并，之后能力读取到所需的数据。因为须要将那些Key雷同的数据全局综合起来，最终抉择出适合的版本返回给用户，所以磁盘文件数量越多，在读取的时候随机读取的次数也会越多，从而影响读取操作的性能。

为了优化读取操作的性能，咱们能够设置肯定策略将选中的多个hf ile进行多路归并，合并成一个文件。文件个数越少，则读取数据时须要seek操作的次数越少，读取性能则越好。

一般来说，依照选中的文件个数，咱们将compact操作分成两种类型。一种是major compact，是将所有的hf ile一次性多路归并成一个文件。这种形式的益处是，合并之后只有一个文件，这样读取的性能必定是最高的；但它的问题是，合并所有的文件可能须要很长的工夫并耗费大量的IO带宽，所以major compact不宜应用太频繁，适宜周期性地跑。

另外一种是minor compact，即选中少数几个hf ile，将它们多路归并成一个文件。这种形式的长处是，能够进行部分的compact，通过大量的IO缩小文件个数，晋升读取操作的性能，适宜较高频率地跑；但它的毛病是，只合并了部分的数据，对于那些全局删除操作，无奈在合并过程中齐全删除。因而，minor compact尽管能缩小文件，但却无奈彻底清除那些delete操作。而major compact能齐全清理那些delete操作，保证数据的最小化。

总结：LSM树的索引构造实质是将写入操作全副转化成磁盘的程序写入，极大地提高了写入操作的性能。然而，这种设计对读取操作是十分不利的，因为须要在读取的过程中，通过归并所有文件来读取所对应的KV，这是十分耗费IO资源的。因而，在HBase中设计了异步的compaction来升高文件个数，达到进步读取性能的目标。因为HDFS只反对文件的程序写，不反对文件的随机写，而且HDFS善于的场景是大文件存储而非小文件，所以下层HBase抉择LSM树这种索引构造是最合适的。

文章基于《HBase原理与实际》一书