《HBase原理与实战》读书笔记-基础数据结构与算法

HBase的列族本质上就是一棵LSM树（Log-Structured Merge-Tree）。

LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构（跳跃表）；磁盘部分由一个个独立文件组成（每个文件又是由一个个数据块组成）。

内存数据结构可以选择：平衡二叉树、红黑树、跳跃表等维护有序集的数据结构，由于考虑并发性能，HBase选择了表现更优秀的跳跃表。

数据存储在磁盘上的数据库系统，磁盘寻道和数据读取都很耗IO，为了避免不必要的IO耗时，可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否又可能存储在这个数据块中，这个数据结构称为布隆过滤器（BloomFilter）

一、跳跃表（SkipList）

跳跃表是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(logN)（N是元素的个数）。与红黑树、二叉树相比的优势在于：实现简单、并发场景下加锁粒度更小，从而可以实现更高的并发性。

跳跃表广泛使用于KV数据库中，例如Redis、HBase等都把跳跃表作为一种维护有序数据集合的基础数据结构。

1、跳跃表的定义

跳跃表.png

• 跳跃表由多条分层的链表组成（设为S0，S1，...），例如图中有4条链表。
• 每条链表都有两个元素：（正无穷大）和（负无穷大），分表表示链表的头部和尾部。
• 从上到小，上层链表元素集合是下层链表元素集合的子集，即S1是S0的子集，S2是S1的子集。
• 跳跃表的高度定义为水平链表的层数。

2、跳跃表的查找

跳跃表.png

如上图，以左上角元素（设为currentNode）作为起点：

• 如果currentNode后继节点的值 <= 待查询值，则沿着这条链表向后查询，否则切换到currentNode的下一层链表；
• 继续查询，直到找到待查询值为止，或者currentNode为空节点为止。

3、跳跃表的插入

• 先按上述流程找到待插入元素的前驱和后继，然后按随机算法生成一个高度值；

// p是一个(0,1)之间的常数，一般取p=1/4或1/2
public void randomHeight(double p){
  int height = 0;
  while(random.nexDouble() < p) height ++;
  return height +1
}

• 将带插入节点按照高度值生成一个垂直节点（该节点的层数正好等于高度值）。
• 插入到跳跃表的多条链表中去。假设height=randomHeight(p)，这里需要分情况讨论：
  （1）若height大于跳跃表的高度，则跳跃表的高度被提升为height，同时需要更新头部节点和尾部节点的指针指向。
  （2）若height小于等于跳跃表的高度，则需要更新待插入元素前驱和后继的指针指向。

4、跳跃表的删除

暂略

关于跳跃表的理解，可以参考：https://www.sohu.com/a/293236470_298038，这里不做笔记整理了

二、LSM树（Log-Structured Merge-Tree）

LSM树（日志结构合并树），本质上和B+树一样，是一种磁盘数据的索引结构，但是，LSM树的索引对写入请求更友好，因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长顺序写且不支持随机写。因为基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。

LSM树的索引一般由两部分组成：

• 内存部分：采用跳跃表（ConcurrentSkipListMap）来维护一个有序的KV（KeyValue）集合；
• 磁盘部分：由多个内部KV（KeyValue）有序的文件组成；

1、KV存储格式

LSM中存储的是多个KV组成的集合，每一个KV一般都会用一个字节数组来表示。
理解字节数组的设计：

字节数组.png

• keyLen：占4字节，存储KV结构中key所占用的字节长度；
• valueLen：占4字节，存储KV结构中value所占用的字节长度；
• rowkeyLen：占2字节，存储rowkey占用的字节长度；
• rowkeyBytes：占用rowkeyLen个字节，用来存储rowkey的二进制内容；
• familyLen：占1字节，用来存储family占用的字节长度；
• familyBytes：占familyLen字节，用来存储family的二进制内容；
• qualifierBytes：占qualifierLen个字节，用来存储qualifier的二进制内容。

并没有单点分配字节来存储qualifierLen，是因为可以通过keyLen和其他字段的长度，计算出qualifierLen：
qualifierLen = keyLen - 2B - rowkeyLen - 1B - familyLen - 8B - 1B

• timestamp：占8字节，表示timestamp对应的long值；
• type：占1字节，表示这个KV 操作的类型，比如：Put、Delete、DeleteColumn、DeleteFamily等;

type字段是一个关键字段，表明LSM树内存储的不只是数据，而是每次操作记录，这对应来LSM树（Log-Structured Merge-Tree）中Log的含义，即操作日志。

value部分直接存储这个KV中value的二进制内容，所以字节数组串主要是key部分的设计。

2、多路归并

多路归并算法：
（1）假设有K路数据流，流内部是有序的，且流间同为升序或降序；
（2）首先读取每个流的第一个数，如果已经EOF，pass；
（3）将有效的k(k可能小于K)个数比较，选出最小的那路mink，输出，读取mink的下一个；
（4）直到所有K路都EOF。

其他的，参考网络资料：http://blog.itpub.net/31561269/viewspace-2564096/

3、LSM树的索引结构

一个LSM树的索引主要由两部分构成：

• 内存部分：采用跳跃表（ConcurrentSkipListMap）来维护一个有序的KV（KeyValue）集合，KV结构就是前面所说的字节数组；
• 磁盘部分：由多个内部KV（KeyValue）有序的文件组成；

LSM树索引结构.png

数据写入时直接写入MemStore中，随着不断写入，一旦内存占用超过一定阀值，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘上。

内部导出形成一个有序数据文件的过程称为flush。为避免flush影响写入性能，会把当前写入的MemStore设为Snapshot，不允许新的写入操作写入这个Snapshot的MemStore，另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放，这样就可以通过两个MemStore来实现稳定的写入性能。

在整个数据写入过程中，LSM树全部使用append操作（即，磁盘顺序写），没有任何随机写操作。
因此LSM树是一种写入友好的索引结构，将磁盘的写入带宽利用到极致。

随着写入增加，内存数据会不断刷新到磁盘上，最终磁盘上的数据文件越来越多。如果数据没有任何读取操作，磁盘上产生很多的数据文件对写入并无影响，而且这时写入速度是最快的，因为所有IO都是顺序IO。但是一旦有用户读请求，则需要将大量的磁盘文件进行多路归并，之后才能读取到所需的数据。因为需要将那些key相同的数据全局综合起来，最终选择出合适的版本返回给用户。

所以，磁盘文件数量越多，在读取时随机读取的次数也会越多，从而影响读取操作的性能。

为了优化读操作性能，设置了一定策略将选中的多个hfile进行多路归并，合并成一个文件（即，compact操作），文件的个数越少，则读取数据时需要随机操作的次数越少，读操作性能则越好。

按选中的文件个数，将compact操作分为两种类型：

• minor compact：选中少数几个hfile多路归并成一个文件。

好处：可以进行局部compact，适合较高频率的跑；
坏处：只合并局部数据，对于全局删除操作无法在合并过程中完全删除。

• major compact：将所有的hfile一次性多路归并成一个文件。

好处：合并后只有一个文件，这样读取的性能肯定最高；
坏处：合并所有文件需要很长时间且消耗大量IO带宽。因此major compact不宜太频繁，适合周期性跑。

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

LSM树的索引结构本质上是将写入操作全部转化为磁盘的顺序写入，极大提高写入操作的性能，但是这种设计对读操作非常不利，因为需要在读取过程中，通过归并所有文件来读取所对应的KV，非常消耗IO资源。
因此HBase中设计来异步的compaction来降低文件个数，达到提高读取性能的目的。
由于HDFS只支持文件的顺序写，不支持文件的随机写，而且HDFS擅长的场景是大文件存储而非小文件，所以上层HBase选择LSM树这种索引结构是最合适的。

三、布隆过滤器（BloomFilter）

布隆过滤器的理解，网络资源参考：https://www.jianshu.com/p/2104d11ee0a2

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

在HBase 1.x版本中，用户可以对某些列设置不同类型的布隆过滤器，共有3种类型：

• NONE：关闭布隆过滤器功能；
• ROW：按照rowkey来设计布隆过滤器的二进制串并存储。

Get查询的时候，必须带rowkey，所以用户可以建表时默认把布隆过滤器设置为ROW类型。

• ROWCOL：按照rowkey+family+qualifier这3个字段频出byte[]来计算布隆过滤器并存储。

Get查询的时候，若能指出rowkey、family、qualifier这3个字段，则肯定可以通过布隆过滤器提升性能；若缺少3个字段中任何一个，则无法通过布隆过滤器提升性能（因为计算布隆过滤器的key不确定）。

需要注意！一般意义上的Scan操作，HBase都无法使用布隆过滤器来提升扫描数据性能，因为布隆过滤器的key值不确定，所以无法计算出哈希值对比。但是在某些特定场景下，Scan操作可以借助布隆过滤器提升性能。