技术15期：浅谈Hbase中的数据结构和算法
前言
本文主要介绍HBase中非常重要的三种数据机构与算法，以便于读者了解HBase的设计思想，因此去熟悉其相关特性，可以更好地去使用HBase。这三种数据结构与算法分别是跳跃表、LSM树和布隆过滤器。
01 跳跃表
跳跃表是一种能够高效插入、删除、查找的内存数据结构，与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，并且在并发场景中加锁粒度更小，从而可以实现更高的并发。正因为这些优点，跳跃表广泛使用于KV数据库中，诸如Redis、LevelDB和HBase。
图1 跳跃表定义
如图1所示，跳跃表由多条分层的链表组成（设为S0，S1，S2，S3），例如图中有4条链表。其中，每条链表中的元素都是有序的，每条链表都有两个必要的元素，（正无穷大）和（负无穷大），分别代表链表的头部和尾部。上层链表元素集合是下层链表元素集合的子集，即S1是S0的子集，跳跃表的高度定义为水平链表的层数。
跳跃表在查找时，以图1左上角的元素为起点（设为currentNode），如果发现currentNode后续节点的值小于待查询值，则沿着这条链表向后查询，否则，切换到当前节点的下一层链表，然后继续查询，直到找到待查询值（或者currentNode为空节点）为止。
跳跃表的插入算法要复杂一些，首先按照上述查找流程找到待插入元素的前驱和后驱，然后随机生成一个高度值，代码实现如下。
最后，根据高度值生成一个垂直节点，插入到跳跃表的多条链表中去。当randomHeight(p)大于跳跃表的高度时，那么跳跃表的高度被提升为randomHeight(p)，同时需要更新头部节点和尾部节点的指针指向。如果跳跃表randomHeight(p)小于等于跳跃表的高度，那么需更新待插入元素的前驱和后续的指针指向。例如，要插入的值是40，获得的高度值是4，各层链表需插入的数据如图1所示。当跳跃表需要删除节点时，需要把节点及其所跨越的层数删除。
02 LSM树
LSM树（日志结构合并树）本质上和B+树一样，也是一种磁盘数据的索引结构。与B+树不同的是，LSM树对写入更友好，同时牺牲了一部分的读取性能。无论何种请求，LSM树都会将写入操作处理为一次的顺序写，HDFS擅长的正是顺序写，十分符合基于HDFS实现的HBase。
一个LSM树由两部分组成，内存部分和磁盘部分。内存部分是一个跳跃表，数据写入时，直接写入内存中，随着写入数据量不断增加，一旦占用的内存超过一定的阈值时，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘中。
图2 LSM树索引结构
如图2所示，内存部分导出形成一个有序的数据文件的过程称为flush。在HBase中，为了避免flush影响数据写入的性能，会首先把当前写入的MemStore设为Snapshot，不再允许新的写入操作写入这个Snapshot的MemStore，另外开辟一个内存空间作为MemStore，让后面的数据写入这个新的MemStore。一旦Snapshot的MemStore写入完毕，对应的内存空间就可以释放，这样就可以保证数据的写入性能。
当用户读取数据时，则需要将大量的磁盘文件进行多路合并。因为在读取数据的时候，需要将那些key相同的数据全局综合起来，最终选择出合适的版本返回给用户，所以磁盘的文件数量越多，在读取的时候随机读取的次数也会越多，从而会造成读取性能较差。为了优化读取操作的性能，HBase采取一定的策略对hfile进行多路合并，合并成一个文件，读取数据时随机读取的操作次数越少，读取性能越好。
LSM树的索引结构本质是将一棵大树拆成N棵小树，它首先将数据写入内存中，随着写入的数据量越来越大，内存中的小树会flush到磁盘当中，磁盘中的树定期做merge操作，合并成一棵大树，以优化读取性能。因此，写入操作全部转换成磁盘的顺序写入，极大地提高了写入操作的性能。
03 布隆过滤器
判断一个元素是否存在于一个集合中，首先想到的是把集合中的元素一个个放到哈希表中。这样确实可以解决小数据量场景下元素存在性的判定，但如果集合数据量巨大，甚至远远超过了机器内存的空间，该如何来解决问题？其中，一种低成本的方式是借助布隆过滤器来实现。
图3 布隆过滤器示例
举个例子，如图3所示，A={x,y,z}，N=18，K=3
初始化array= [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
对元素x，HASH_0(x)%N=1，HASH_1(x)%N=5，HASH_2(x)%N=13，因此array= [0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0]
对元素y，HASH_0(x)%N=4，HASH_1(x)%N=11，HASH_2(x)%N=16，因此array= [0,1,0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,0]
对元素z，HASH_0(x)%N=3，HASH_1(x)%N=5，HASH_2(x)%N=11，因此array= [0,1,0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0]
最终得到的布隆过滤器串为：[0,1,0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0]
此时，如果对于元素w，K次的哈希值分别为4，13，15。由于15布隆过滤器串中第15位为0，因此可以确认w肯定不在集合A中。因为若w在A集合中，则第15位必定为1。
如果有另一个元素t，其K次哈希值分别为5，11，13。由于布隆过滤器串中第5、11、13位均为1，但是没法肯定t一定在集合A中。因此，布隆过滤器串对任意给定元素w，给出的存在性结果分为两种：
w可能存在于集合A中
w肯定不在集合A中
总 结
参考文献：《HBase原理与实践》
想学习更多技术内容
别忘了关注普适极客