HBase与LSM树

一、LSM树的原理

讲LSM树之前，需要提下三种基本的存储引擎，这样才能清楚LSM树的由来：

1. 哈希存储引擎
   是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统，如Redis。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表效率是很高的。
2. B树存储引擎
   是B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。
3. LSM树（Log-Structured Merge Tree）存储引擎
   和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。

通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

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

以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：

1. 因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog
2. MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

二、HBase 的 LSM 实现

１、WAL 预写日志支持

类似与 binlog 的作用，在写入 MemTable 之前，往 WAL 写入日志，避免宕机出现的数据丢失的情况发生。因此 HBase 算是一个不错的可靠性存储。

这里有个很有趣的地方，某些测试环境下，机械硬盘的顺序写性能会高于对内存的随机写。因此 WAL 的写入性能是非常可观的，我们不必对此过于介怀。

２、Minor vs Major Compaction

(1) Minor Compaction： 根据配置策略，自动检查小文件，合并到大文件，从而减少碎片文件，然而并不会立马删除掉旧 HFile 文件；

(2) Major Compaction： 每个 CF 中，不管有多少个 HFiles 文件，最终都是将 HFiles 合并到一个大的 HFile 中，并且把所有的旧 HFile 文件删除，即CF 与 HFile 最终变成一一对应的关系。

3、BlockCache

除了 MemStore（也就是 MemTable） 以外，HBase 还提供了另一种缓存结构，BlockCache。

BlockCache 本质上是将热数据放到内存里维护起来，避免 Disk I/O，当然即使 BlockCache 找不到数据还是可以去 MemStore 中找的，只有两边都不存在数据的时候，才会读内存里的 HFile 索引寻址到硬盘，进行一次 I/O 操作。

4、HFile 的数据结构

参考：http://hbasefly.com/2016/03/25/hbase-hfile/

5、Bloom Filter

HFile 文件中包含了一个 Bloom Block，这个是用来做布隆过滤的。Bloom Block 的数据是在启动的时候就已经加载到内存里，除了 Block Cache 和 MemStore 以外，这个也对 HBase 随机读性能的优化起着至关重要的作用。

生成 HFile 的时候，会将 key 经过三次 hash 最终落到 Bloom Block 位数组的某三位上，并将其由0更改成1，以此标记该 key 的确存在这个 HFile 文件之中，查询的时候不需要将文件打开并检索，避免了一次 I/O 操作。然而随着 HFile 的膨胀，Bloom Block会越来越大。

HFile 包含x 和 y 两个数据的情况