HBase的LSM树结构
2019-01-27
LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。
对于LSM树的详细介绍还可以参见以下几篇博客：
LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。
- 因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog
- MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。
- 数据首先被存储在日志文件，这些文件内的数据完全有序。当有日志文件被修改时，对应的更新会被先保存在内存中来加速查询；
- 当多次修改，使内存空间被逐渐被占满后，LSM树会把有序的“键-记录”对写到磁盘中，同时创建一个新的数据存储文件。此时，因为最近的修改都被持久化了，内存中保存的最近更新就可以被丢弃了；
- 所有节点都是满的并按页存储。修改数据文件的操作通过滚动合并完成；
- 多次数据刷写之后会创建许多数据存储文件，后台线程就会自动将小文件聚合成大文件，这样磁盘查找就会被限制在少数几个数据存储文件中。磁盘上的树结构也可以拆分成独立的小单元，这样更新就可以被分散到多个数据存储文件中；
- 查询： 先查找内存中的存储，然后再查找磁盘上的文件。这样在客户端看来数据存储文件的位置是透明的；
- 删除： 是一种特殊的更改，当删除标记被存储之后，查找会跳过这些删除过的键。当页被重写时，有删除标记的键会被丢弃。此外，后台运维过程可以处理预先设定的删除请求。这些请求由TTL（time-to-live）触发，例如，当TTL设为20天后，合并进程会检查这些预设的时间戳，同时在重写数据块时丢弃过期的记录。
LSM树存储引擎、B树存储引擎和哈希存储引擎的区别
- 哈希存储引擎：是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，其检索效率非常高，索引的检索可以一次定位，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，可以选择哈希表。代表数据库：redis、memcache等
- B+树存储引擎：是B+树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。
- LSM树（Log-Structured Merge Tree）存储引擎：核心思想的核心就是放弃部分读能力，换取写入的最大化能力。和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。通常LSM-tree适用于索引插入比检索更频繁的应用系统。代表数据库：nessDB、leveldb、hbase等