浅谈HBase LSM树存储系统

1.LSM树的起源

​在了解LSM树之前，我们需要了解哈希表和B+树。

​ 标签保存方式支持添加、删除、编辑和随机读取，但不支持顺序扫描。与之相对应的存储系统就是关键——value的存储系统。对于key-value的输入和查询，哈希表的复杂度是O(1)，明显比O(n)树操作要快。如果不需要顺利的过一遍数据，哈希表是最好的选择

​ B+树不仅支持单条记录的增删改查操作，还支持顺序扫描。 （B+ 树的叶子之间的点）。对应的存储系统是关系型数据库（Mysql等）。但删除和更新信息比较复杂。

​ LSM树（Log-Structured Merge Tree）存储引擎与B树存储引擎类似，也支持增、删、读、修改、顺序扫描操作。而批量存储技术则避免了磁盘随机写入的问题。当然，凡事都有其优点和缺点。与B+树相比，LSM树牺牲了部分阅读来大幅提高写作。

2。 LSM

​ LSM树的概念和理念非常简单：将对数据库的增量更改存储在内存中，当这些更改事件达到大小限制时将这些更改事件写入集成磁盘。不过，阅读起来有点困难。它需要结合磁盘上的历史数据和内存中最近的修改工作，因此写入性能大大提高。读取时，可能需要先检查内存是否命中，否则需要访问更多的磁盘文件。严格来说，用LSM树实现的HBase写性能比Mysql高一个数量级，读性能低一个数量级。

​LSM树的原理是将一棵大树分成N棵小树。它首先被写入内存。随着子树越来越大，内存中的子树会下到磁盘上，磁盘上的树就会干涸。可以不时进行分组活动，组合成一棵大树，提高阅读能力。

​ LSM在hbase中的实现过程对应如下：

​ 1.因为小树是先写入内存的，为了避免内存数据丢失，需要在磁盘上停留一段时间。同时写入内存，对应HBase MemStore和HLog

​ 2.当MemStore中的树达到一定大小时，需要加载到磁盘HRegion（通常是Hadoop DataNode）中，这样MemStore就变成了磁盘文件。 DataNode 上的 StoreFile。 HRegionServer 定期检查 DataNode。数据库进行合并操作以完全删除无效空间。现在将几棵小树组合成一棵大树以提高可读性。

3。 LSM原理

关于LSM Tree，对于最简单的两层LSM树，内存中的数据和磁盘上的数据结合在一起，如下图

​ lsm树，理论部分内存中的树可以与磁盘上的第一层树结合起来。直接对磁盘树进行更新操作可能会破坏物理块的连续性。然而，在实际应用中，LSM通常有很多层。当磁盘上的小树组合成大树时，可以调整顺序，使块不连续，提高可读性。

​ 在hbase实现中，经过一定时间后，将整个内存发送到磁盘来创建文件。这个文件的存储是一棵小B+树，因为hbase一般安装在HDFS上，而HDFS不支持对文件进行更新操作，所以hbase去掉了整个内存但不要把更新和磁盘上的小树混淆了。这个设计是有道理的。从内存到磁盘的小树会定期组合成一棵大树。基本上，hbase 使用 lsm 树概念。