二、HBase的核心数据结构 跳跃表、LSM树、布隆过滤器_hbase跳表

HBase的核心数据结构

HBase的一个列簇（Column Family）本质上是一棵LSM树（Log-Structured Merge-Tree）。

LSM树分为内存部分和磁盘部分。

内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，由于考虑并发性能，HBase选择了表现更优秀的跳跃表。

磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。对于数据存储在磁盘上的数据库系统来说，磁盘寻道以及数据读取都是非常耗时的操作（简称IO耗时）。为了避免不必要的IO耗时，可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（BloomFilter）。

跳跃表(SkipList)

跳跃表（SkipList）是一种能高效实现插入、删除、查找的内存数据结构，复杂度都是O（logN）。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。

LSM树

LSM树是一种磁盘数据的索引结构。LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写）。

一个LSM树的索引主要由两部分构成：内存部分和磁盘部分。内存部分是一个ConcurrentSkipListMap，Key是rowkey、column family、qualifier、type以及timestamp， Value是字节数组。

随着数据不断写入MemStore，一旦内存超过阈值会将数据flush到磁盘，生产HFile；多个小HFile文件会compact成一个大HFile。

compact操作分成两种类型。

• major compact，是将所有的hfile一次合并成一个文件。好处是，合并之后只有一个文件，读取的性能好；但它的问题是，合并所有的文件可能需要很长的时间并消耗大量的IO带宽，所以major compact不宜使用太频繁，适合周期性地跑。
• minor compact，即选中少数几个hfile 合并成一个文件。优点是，可以进行局部的compact，通过少量的IO减少文件数量，提升读取操作的性能，适合较高频率地跑；但它的缺点是，只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。

minor compact虽然能减少文件，但却无法彻底清除那些delete操作。而major compact能完全清理那些delete操作，保证数据的最小化。

布隆过滤器

布隆过滤器对任意给定元素w，给出的存在性结果为两种：

• w可能存在于集合A中。
• w肯定不在集合A中。

布隆过滤器由一个长度为N的01数组array组成。首先将数组array每个元素初始设为0。
对集合A中的每个元素w，做K次哈希，第i次哈希值对N取模得到一个 index(i)，即 index(i) = HASH_i(w) % N，将array数组中的array[index(i)]置为1。最终array变成一个某些元素为1的01数组。

布隆过滤器算法示例

A={x，y，z}，N=18，K=3。
初始化array = 000000000000000000
对元素x，HASH_0(x) % N=1，HASH_1(x) % N=5，HASH_2(x) % N=13。因此array=010001000000010000;
对元素y，HASH_0(y) % N=4，HASH_1(y) % N=11，HASH_2(y) % N=16。因此array=010011000001010010;
对元素z，HASH_0(z) % N=3，HASH_1(y) % N=5，HASH_2(y) % N=11。因此array=010111000001010010;
最终得到的布隆过滤器串为：010111000001010010。
1
2
3
4
5
6

对于元素w，K次哈希值分别为：
HASH_0(w) %N=4
HASH_1(w) %N=13
HASH_2(w) %N=15
可以发现，布隆过滤器串中的第15位为0，因此可以确认w肯定不在集合A中。因为若w在A中，则第15位必定为1。

如果有另外一个元素t，K次哈希值分别为：
HASH_0(t) %N=5
HASH_1(t) %N=11
HASH_2(t) %N=13
发现布隆过滤器串中的第5、11、13位都为1，但是却没法肯定t一定在集合A中。
1
2
3
4
5
6
7
8
9
10
11

HBase与布隆过滤器

由于布隆过滤器只需占用极小的空间，便可给出“可能存在”和“肯定不存在”的存在性判断，可以提前过滤掉很多不必要的数据块，从而节省了大量的磁盘IO。HBase的Get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省大量磁盘IO。