HBase 篇（八）：LSM Tree

Google的BigTable论文提到了一个很重要的东西：它所使用的文件组织方式（LSM-Tree），这个东东出自1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》。

对HBase有一定了解的同学对这个LSM一定不陌生。我们先来回忆下HBase的读写

写流程

1. 向zookeeper发起请求，从ROOT表中获得META所在的region，再根据table，namespace，rowkey，去meta表中找到目标数据对应的region信息以及regionserver

2. 把数据分别写到HLog和MemStore上一份，若MemStore中的数据有丢失，则可在HLog上恢复

3. 当memstore数据达到阈值（默认是64M），将数据刷到硬盘，将内存中的数据删除同时删除Hlog中的历史数据。

4. 当多个StoreFile文件达到一定的大小后，会触发Compact合并操作，合并为一个StoreFile，这里同时进行版本的合并和数据删除。

5. 当Compact后，逐步形成越来越大的StoreFIle后，会触发Split操作，把当前的StoreFile分成两个，这里相当于把一个大的region分割成两个region

6. 当hregionser宕机后，将hregionserver上的hlog拆分，然后分配给不同的hregionserver加载，修改.META.

读流程

1. 首先用MemStoreScanner搜索MemStore里是否有所查的rowKey（这一步在内存中，很快），

2. 同时也会用Bloom Block通过一定算法过滤掉大部分一定不包含所查rowKey的HFile，

3. 上面提到在RegionServer启动的时候就会把Trailer，和Load-on-open-section里的block先后加载到内存，所以接下来会查Trailer，因为它记录了每个HFile的偏移量，可以快速排除掉剩下的部分HFile。

4. 经过上面两步，剩下的就是很少一部分的HFile了，就需要根据Index Block索引数据（这部分的Block已经在内存）快速查找rowkey所在的block的位置；

5. 找到block的位置后，检查这个block是否在blockCache中，在则直接去取，如果不在的话把这个block加载到blockCache进行缓存，

6. 最后扫描这些读到内存中的Block（可能有多个，因为有多版本），找到对应rowKey返回需要的版本。

熟悉了HBase的读写流程后（尤其是写流程），了解lsm tree就会变得容易很多了。Log-Structured Merge-Tree中文翻译是日志结构合并树。那我们就从日志结构与合并树这两个方面来讲。

日志结构

我们知道磁盘随机读写性能是比顺序读写慢至少3个数量级的，日志的特点是 它是顺序追加写 的，可以保证非常好的写操作性能，但是从 日志文件中读一些数据将会比写操作需要更多的时间 ，需要倒序扫描，直接找到所需的内容。

因此日志适用的场景非常有限：

1. 数据是被整体访问，像大部分数据库的WAL(write-ahead log)、HDFS

2. 记录了文件明确的偏移量，比如Kafka

为了为更复杂的读场景（比如按key或者range）提供高效的性能，人们发明了几种方式：

二分查找: 将文件数据有序保存，使用二分查找来完成特定key的查找。

哈希：用哈希将数据分割为不同的bucket

B+树：使用B+树 或者 ISAM 等方法，可以减少外部文件的读取

外部文件： 将数据保存为日志，并创建一个hash或者查找树映射相应的文件。

所有的方法都可以有效的提高了读操作的性能（最少提供了O(log(n)) )，但是，却丢失了日志文件超好的写性能。上面这些方法，都 强加了总体的结构信息在数据上，数据被按照特定的方式放置，所以可以很快的找到特定的数据 ，但是却对写操作不友善，让写操作性能下降。更糟糕的是，当我们需要更新hash或者B+树的结构时，需要同时更新文件系统中特定的部分，这就是上面说的比较慢的随机读写操作。这种随机的操作要尽量减少。

此时，LSM 被发明了， LSM 使用一种不同于上述四种的方法，保持了日志文件写性能，以及微小的读操作性能损失。本质上就是 通过把随机写的数据写到内存，然后定期flush到磁盘，对于磁盘来说，让所有的操作顺序化，而不是随机读写。

合并树

LSM树原理把一棵大树拆分成N棵小树， 它首先写入内存中即是小树，随着小树越来越大，会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能 。

lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。

hbase在实现中，是把整个内存在一定阈值后，flush到disk中，形成一个file，这个file的存储也就是一个小的B+树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，所以hbase这么整体内存flush，而不是和磁盘中的小树merge update，这个设计也就能讲通了。内存flush到磁盘上的小树，定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。