详解Hbase底层的数据结构——LSMT _Hbase

今天给大家分享的内容是LSM树，它的英文是Log-structed Merge-tree 。看着有些发怵，但其实它的原理不难，和B树相比简直算是小儿科了。

并且这也是一个非常经典的数据结构，并且在大数据系统当中有非常广泛的应用。有许多耳熟能详的经典系统，底层就是基于LSM树实现的。因此，今天就和大家一起来深入学习一下它的原理。

背景知识
首先，我们先从背景知识开始。我们之前介绍B+树的时候说过， B+树和B树最大的不同就是将所有的数据都放在了叶子节点。从而优化了我们批量插入以及批量查询的效率，而优化的核心逻辑就是因为无论是什么存储介质，顺序存储的效率一定要比随机存储更高，并且高的还不是一点半点。这个已经算是老生常谈了，如果我没记错的话，这已经是我第三次在文章当中提到这一点了。

我最近看到了一张图，很好地阐述了随机读取和顺序读取两者的效率差，我们来看下面这张图。其中绿色的部分表示硬盘顺序读取的最大速度，而红色表示随机读取时的速度。

文章插图

我们看下纵坐标就知道，这两者差的不是一点半点，已经有数量级的差距了。而且还不止是一个数量级，至少相差了三个数量级，显然这是非常恐怖的。另外，这个差距并不只是在传统的机械硬盘上存在，即使是现在比较先进的SSD固态硬盘上，也一样存在。也就是说这个差距是介质无关的。

直观优化
既然随机读取和顺序读取的效率差了这么多，不由得不让人心动。如果能够发明一个数据结构可以充分地利用上这一点，那么我们的系统对数据的吞吐能力一定可以再上一个台阶。对于许多科技公司而言，尤其是大数据公司，因为数据量带来的机器开销的费用占据了日常支出的大头。如果能够很好地解决这个问题，显然可以节约大量的资源。

一个朴素的想法就是将所有的读写都设计成顺序读写，比如日志系统就是一个典型的例子。在我们记录日志的时候，总是添加在文件的末尾，而不会插入在文件的中间。由于我们总是添加在文件末尾，在磁盘上这是一个顺序的读写。但我们把读写都设计成顺序的，也就意味着我们当我们要查找的内容在文件中间的时候，我们必须要读入文件中的所有内容。

这个思路应用最广泛的地方有两个，一个是数据库的日志当中。在我们用数据库执行写入或者修改操作的时候，数据库会将所有的变更写成log记录下来。还有一处是消息系统的中间件，比如kafka 。

但是在复杂的增删查改的场景当中，尤其是涉及到批量读写的场景，简单的文件顺序读写就不能满足需求了。当然我们可以引入哈希表或者是B+树这些数据结构实现功能，但这些复杂的数据结构都避免不了比较慢的随机读写操作，而我们希望随机读写能尽量减少，正是基于这个原理， LSMT被发明了出来。LSMT使用了一种独特的机制牺牲了一些读操作的性能，保证了写操作的能力，它能够让所有的操作顺序化，几乎完全避免了随机读写。

在我们介绍LSMT的原理之前，我们先来介绍一下它的子结构SSTable 。

SSTable
第一次看到这个单词的时候觉得一头雾水是正常的， SSTable的全称是Sorted String Table ，本质就是一个KV结构顺序排列的文件。我们来看下下图：

文章插图

最基础的SSTable就是上图当中右侧的部分，即key和value的键值对按照key值的大小排序，并存储在文件当中。当我们需要查找某个key值对应的数据的时候，我们会将整个文件读入进内存，进行查找。同样，写入也是如此，我们会将插入的操作在内存中进行，得到结果之后，直接覆盖原本的文件，而不会在文件当中修改，因为这会牵扯到移动大量的数据。