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 原理与实际》一书