2.2 LSM树

LSM树本质上和B+树一样，是一种磁盘数据的索引结构。但和B+树不同的是，LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写），因此基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。

LSM树的索引一般由两部分组成，一部分是内存部分，一部分是磁盘部分。内存部分一般采用跳跃表来维护一个有序的KeyValue集合。磁盘部分一般由多个内部KeyValue有序的文件组成。

1.KeyValue存储格式

一般来说，LSM中存储的是多个KeyValue组成的集合，每一个KeyValue一般都会用一个字节数组来表示。这里，首先需要来理解KeyValue这个字节数组的设计。

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

总体来说，字节数组主要分为以下几个字段。其中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。代码如下：

        qualifierLen=keyLen -2B - rowkeyLen -1B - familyLen -8B -1B

• timestamp：占用8字节，表示timestamp对应的long值。

• type：占用1字节，表示这个KeyValue操作的类型，HBase内有Put、Delete、Delete Column、DeleteFamily，等等。注意，这是一个非常关键的字段，表明了LSM树内存储的不只是数据，而是每一次操作记录。

Value部分直接存储这个KeyValue中Value的二进制内容。所以，字节数组串主要是Key部分的设计。

在比较这些KeyValue的大小顺序时，HBase按照如下方式（伪代码）来确定大小关系：

        int compare(KeyValue a, KeyValue b){
          int ret=Bytes.compare(a.rowKeyBytes, b.rowKeyBytes);
          if(ret !=0) return ret;
          ret=Bytes.compare(a.familyBytes, b.familyBytes);
          if(ret !=0) return ret;
          ret=Bytes.compare(a.qualifierBytes, b.qualifierBytes);
          if(ret !=0) return ret;
          // 注意：timestamp越大，排序越靠前
          ret=b.timestamp - a.timestamp;
          if(ret !=0) return ret;
          ret=a.type - b.type;
          return ret;
        }

注意，在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个文件全部读完为止，如图2-7所示。

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

核心实现如下：

        public class KMergeSort {
          public interface FileReader {
            //true to indicate the file still has some data, false means EOF.
            boolean hasNext() throws IOException;
            //Read the next value from file, and move the file read offset.
            int next() throws IOException;
          }
          public interface FileWriter {
            void append(int value) throws IOException;
          }
          public void kMergeSort(final List<FileReader> readers, FileWriter writer)
            throws IOException {
            PriorityQueue<Pair<FileReader, Integer>> heap=
                new PriorityQueue<>((p1, p2) -> p1.getValue() - p2.getValue());
            for (FileReader fr : readers) {
              if (fr.hasNext()) {
                heap.add(new Pair<>(fr, fr.next()));
              }
            }
            while (!heap.isEmpty()) {
              Pair<FileReader, Integer> current=heap.poll();
              writer.append(current.getValue());
              FileReader currentReader=current.getKey();
              if (currentReader.hasNext()) {
                heap.add(new Pair<>(currentReader, currentReader.next()));
              }
            }
          }
        }

3. LSM树的索引结构

一个LSM树的索引主要由两部分构成：内存部分和磁盘部分。内存部分是一个ConcurrentSkipListMap，Key就是前面所说的Key部分，Value是一个字节数组。数据写入时，直接写入MemStore中。随着不断写入，一旦内存占用超过一定的阈值时，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘上。

LSM树索引结构如图2-8所示。内存部分导出形成一个有序数据文件的过程称为f lush。为了避免f lush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放。这样，就可以通过两个MemStore来实现稳定的写入性能。

随着写入的增加，内存数据会不断地刷新到磁盘上。最终磁盘上的数据文件会越来越多。如果数据没有任何的读取操作，磁盘上产生很多的数据文件对写入并无影响，而且这时写入速度是最快的，因为所有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树这种索引结构是最合适的。