深入HBase——数据结构与算法

引入

通过前面的文章，我们对HBase已经有了基本认识，下面我们从HBase最核心的算法和数据结构进一步深入HBase。

HBase的一个列簇（Column Family）本质上就是一棵LSM树（Log-Structured Merge-Tree）​。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，这里由于考虑并发性能，HBase选择了表现更优秀的跳跃表。磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。并且为了避免不必要的IO耗时，还可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（Bloom Filter）​。

下面我们就深入介绍一下提到的核心数据结构与算法：

• LSM树（Log-Structured Merge-Tree）​
• 跳跃表（SkipList）
• 布隆过滤器（Bloom Filter）​

LSM树（Log-Structured Merge-Tree）

LSM树本质上和B+树一样，是一种磁盘数据的索引结构。但和B+树不同的是，LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树的索引结构本质都会将其全部转化成磁盘的顺序写入，而HDFS擅长的正是顺序写（且HDFS不支持随机写）​，因此基于HDFS实现的HBase能极大提高写入操作的性能，但这种设计对读取操作是非常不利的，因为需要在读取的过程中，通过归并所有文件来读取所对应的KV，这是非常消耗IO资源的。因此，在HBase中设计了异步的compaction来降低文件个数，达到提高读取性能的目的。由于HDFS只支持文件的顺序写，不支持文件的随机写，而且HDFS擅长的场景是大文件存储而非小文件，所以上层HBase选择LSM树这种索引结构是最合适的。

原理

LSM树是一种用于存储和管理数据的数据结构，特别适用于写入密集型的工作负载。它的设计灵感来自于日志结构文件系统。LSM树的核心思想是将写操作集中到一个内存中的有序数据结构（如MemTable），待数据积累到一定数量后，将这些数据批量写入到磁盘上的有序文件中。这种设计能够显著提高写操作的性能，因为将随机写转换为顺序写，能够减少磁盘的寻道时间。

结构

LSM树的索引一般由两部分组成，一部分是内存部分，一部分是磁盘部分。内存部分一般采用跳跃表来维护一个有序的KeyValue集合。磁盘部分一般由多个内部KeyValue有序的文件组成。

KeyValue存储格式

在HBase为例，这个字节数组串设计如下图所示，字节数组主要分为以下几个字段：

其中Rowkey、Family、Qualifier、Timestamp、Type这5个字段组成KeyValue中的key部分。

• keyLen：占用4字节，用来存储KeyValue结构中Key所占用的字节长度。
• valueLen：占用4字节，用来存储KeyValue结构中Value所占用的字节长度。
• rowkeyLen：占用2字节，用来存储rowkey占用的字节长度。
• rowkeyBytes：占用rowkeyLen个字节，用来存储rowkey的二进制内容。
• familyLen：占用1字节，用来存储Family占用的字节长度。
• familyBytes：占用familyLen字节，用来存储Family的二进制内容。
• qualifierBytes：占用qualifierLen个字节，用来存储Qualifier的二进制内容。
  注意，HBase并没有单独分配字节用来存储qualifierLen，因为可以通过keyLen和其他字段的长度计算出qualifierLen。
  代码如下：

qualifierLen=keyLen -2B - rowkeyLen -1B - familyLen -8B -1B

• timestamp：占用8字节，表示timestamp对应的long值。
• type：占用1字节，表示这个KeyValue操作的类型，HBase内有Put、Delete、Delete Column、DeleteFamily，等等。注意，这是一个非常关键的字段，表明了LSM树内存储的不只是数据，而是每一次操作记录。

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

注意：

在HBase中，timestamp越大的KeyValue，排序越靠前。因为用户期望优先读取到那些版本号更新的数据。

通常来说，在LSM树的KeyValue中的Key部分，有3个字段必不可少：

• Key的二进制内容。
• 一个表示版本号的64位long值，在HBase中对应timestamp；这个版本号通常表示数据的写入先后顺序，版本号越大的数据，越优先被用户读取。甚至会设计一定的策略，将那些版本号较小的数据过期淘汰（HBase中有TTL策略）​。
• type，表示这个KeyValue是Put操作，还是Delete操作，或者是其他写入操作。本质上，LSM树中存放的并非数据本身，而是操作记录。这对应了LSM树（Log-Structured Merge-Tree）中Log的含义，即操作日志。

多路归并

现在有K个文件，其中第i个文件内部存储有Ni个正整数（这些整数在文件内按照从小到大的顺序存储）​，如何设计一个算法将K个有序文件合并成一个大的有序文件？

在排序算法中，有一类排序算法叫做归并排序，里面就有大家熟知的两路归并实现。现在相当于K路归并，因此可以拓展一下，思路类似。对每个文件设计一个指针，取出K个指针中数值最小的一个，然后把最小的那个指针后移，接着继续找K个指针中数值最小的一个，继续后移指针……直到N个文件全部读完为止。

核心实现代码如下：

    /*** 该类实现了 k 路归并排序的功能，用于合并多个有序文件的内容。*/public class KMergeSort {/*** 文件读取器接口，定义了从文件中读取数据的方法。*/public interface FileReader {/*** 检查文件是否还有更多数据。* @return 如果文件还有数据，返回 true；否则返回 false 表示到达文件末尾。* @throws IOException 如果在读取文件时发生 I/O 错误。*///true to indicate the file still has some data, false means EOF.boolean hasNext() throws IOException;/*** 从文件中读取下一个值，并将文件读取偏移量向后移动。* @return 文件中的下一个整数值。* @throws IOException 如果在读取文件时发生 I/O 错误。*///Read the next value from file, and move the file read offset.int next() throws IOException;}/*** 文件写入器接口，定义了向文件中写入数据的方法。*/public interface FileWriter {/*** 向文件中追加一个整数值。* @param value 要追加的整数值。* @throws IOException 如果在写入文件时发生 I/O 错误。*/void append(int value) throws IOException;}/*** 实现 k 路归并排序，将多个有序文件的内容合并到一个文件中。* @param readers 一个包含多个 FileReader 的列表，每个 FileReader 对应一个有序文件。* @param writer 用于写入合并后数据的 FileWriter。* @throws IOException 如果在读取或写入文件时发生 I/O 错误。*/public void kMergeSort(final List<FileReader> readers, FileWriter writer)throws IOException {// 创建一个优先队列（最小堆），用于存储每个文件的当前最小值PriorityQueue<Pair<FileReader, Integer>> heap=new PriorityQueue<>((p1, p2) -> p1.getValue() - p2.getValue());// 初始化优先队列，将每个文件的第一个值加入队列for (FileReader fr : readers) {if (fr.hasNext()) {// 将文件读取器和其下一个值作为一个 Pair 加入堆中heap.add(new Pair<>(fr, fr.next()));}}// 不断从堆中取出最小值，并将其写入输出文件while (!heap.isEmpty()) {// 从堆中取出最小值对应的 PairPair<FileReader, Integer> current=heap.poll();// 将该值写入输出文件writer.append(current.getValue());// 获取当前文件读取器FileReader currentReader=current.getKey();// 如果当前文件还有更多数据，将下一个值加入堆中if (currentReader.hasNext()) {// 将当前文件读取器和其下一个值作为一个 Pair 加入堆中heap.add(new Pair<>(currentReader, currentReader.next()));}}}}

LSM树的索引结构

一个LSM树的索引主要由两部分构成：内存部分和磁盘部分。内存部分是一个ConcurrentSkipListMap，Key就是前面所说的Key部分，Value是一个字节数组。数据写入时，直接写入MemStore中。随着不断写入，一旦内存占用超过一定的阈值时，就把内存部分的数据导出，形成一个有序的数据文件，存储在磁盘上。 

内存部分导出形成一个有序数据文件的过程称为flush。为了避免flush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放。这样就可以通过两个MemStore来实现稳定的写入性能。（看过深入HDFS的小伙伴会发现，这个和SNN合并元数据的操作很类似）

注意：

在整个数据写入过程中，LSM树全部都是使用append操作（磁盘顺序写）来实现数据写入的，没有使用任何seek+write（磁盘随机写）的方式来写入。无论HDD还是SSD，磁盘的顺序写操作性能和延迟都远好于磁盘随机写。因此LSM树是一种对写入极为友好的索引结构，它能将磁盘的写入带宽利用到极致。

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

为了优化读取操作的性能，我们可以设置一定策略将选中的多个hfile进行多路归并，合并成一个文件。文件个数越少，则读取数据时需要seek操作的次数越少，读取性能则越好。一般来说，按照选中的文件个数，我们将compact操作分成两种类型。一种是major compact，是将所有的hfile一次性多路归并成一个文件。这种方式的好处是，合并之后只有一个文件，这样读取的性能肯定是最高的；但它的问题是，合并所有的文件可能需要很长的时间并消耗大量的IO带宽，所以major compact不宜使用太频繁，适合周期性地跑。

另外一种是minor compact，即选中少数几个hfile，将它们多路归并成一个文件。这种方式的优点是，可以进行局部的compact，通过少量的IO减少文件个数，提升读取操作的性能，适合较高频率地跑；但它的缺点是，只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。因此，minor compact虽然能减少文件，但却无法彻底清除那些delete操作。而major compact能完全清理那些delete操作，保证数据的最小化。

在HBase中的应用

写操作优化：通过将数据先写入到内存中的MemTable，HBase能够将随机写转换为顺序写，从而大大提高写操作的性能。这对于HBase这种需要处理大量写入请求的数据库来说非常重要。

读操作优化：虽然LSM树的设计主要是为了优化写操作，但通过将多个SSTable的索引信息加载到内存中，HBase也能够有效地处理读取请求。此外，SSTables的有序存储结构也使得范围查询变得非常高效。

数据一致性：在MemTable写入到SSTable之前，HBase会将数据写入WAL，以确保数据的持久性和一致性。如果在写入过程中发生故障，HBase可以通过WAL恢复未写入到SSTable的数据。

优点

高性能写入：LSM树能够将随机写转换为顺序写，从而显著提高写入性能。这对于写入密集型的工作负载非常重要。

有效利用存储空间：通过将多个小的SSTables合并为更大的SSTable，LSM树能够有效地减少存储空间的占用，并提高数据的存储效率。

易于实现压缩：由于SSTables是按主键排序的，因此可以很容易地对它们进行压缩，从而进一步提高存储效率。

缺点

读操作延迟：在读取数据时，HBase需要在多个SSTables之间进行查找和合并，这可能会导致一定的读取延迟。

合并开销：合并SSTables的过程需要消耗大量的系统资源，包括CPU、内存和磁盘I/O。如果合并操作过于频繁或规模过大，可能会对系统的性能产生一定的影响。

跳跃表（SkipList）

跳跃表是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(logN)。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。正因为这些优点，跳跃表广泛使用于KV数据库中，诸如Redis、LevelDB、HBase都把跳跃表作为一种维护有序数据集合的基础数据结构。

众所周知，链表这种数据结构的查询复杂度为O(N)，这里N是链表中元素的个数。在已经找到要删除元素的情况下，再执行链表的删除操作其实非常高效，只需把待删除元素前一个元素的next指针指向待删除元素的后一个元素即可，复杂度为O(1)。但问题是，链表的查询复杂度太高，因为链表在查询的时候，需要逐个元素地查找。如果链表在查找的时候，能够避免依次查找元素，那么查找复杂度将降低。而跳跃表就是利用这一思想，在链表之上额外存储了一些节点的索引信息，达到避免依次查找元素的目的，从而将查询复杂度优化为O(logN)。将查询复杂度优化之后，自然也优化了插入和删除的复杂度。

原理

跳跃表是一种有序数据结构，它通过在每个节点中维护多个指针，以支持快速的插入、删除和查找操作。跳跃表的灵感来自于链表，但它通过添加多层指针来减少查找时间。每个节点在跳跃表中可以有多个层次，每个层次的指针指向比当前节点更大的键。这样，在查找一个键时，可以从最高层开始，快速跳过不相关的节点，从而减少比较的次数。

结构

跳跃表的结构是由多个节点组成的，每个节点包含一个键和多个指向其他节点的指针。节点的层数是随机的，通常通过一个概率函数来确定。最高层的指针可以快速跳过大量的节点，而底层的指针则用于精细的查找。跳跃表的层次结构类似于一个金字塔，最顶层的层数最少，最底层的层数最多。

• 跳跃表由多条分层的链表组成（设为S0, S1, S2, ... , Sn）​；
• 每条链表中的元素都是有序的；
• 每条链表都有两个元素：+∞（正无穷大）和 -∞（负无穷大）​，分别表示链表的头部和尾部；
• 从上到下，上层链表元素集合是下层链表元素集合的子集，即S1是S0的子集，S2是S1的子集。

注意：跳跃表的高度为水平链表的层数。

代码示例

    /*** 跳跃表类，实现了跳跃表数据结构，支持插入、查找和删除操作。*/public class SkipList {private static final int MAX_LEVEL = 16; // 跳跃表的最大层级private int level; // 当前跳跃表的层级private Node head; // 跳跃表的头节点private Random random; // 用于生成随机数/*** 构造函数，初始化跳跃表。*/public SkipList() {head = new Node(MAX_LEVEL);level = 1;random = new Random();}/*** 跳跃表的节点类，包含键值和指向下一个节点的数组。*/private class Node {int key; // 节点的键值Node[] next; // 指向下一个节点的数组/*** 构造函数，初始化指向下一个节点的数组。* @param level 节点的层级*/Node(int level) {next = new Node[level]; // 初始化指针数组}/*** 构造函数，初始化节点的键值和指向下一个节点的数组。* @param key 节点的键值* @param level 节点的层级*/Node(int key, int level) {this.key = key;next = new Node[level];}}/*** 随机生成节点的层级。* @return 生成的节点层级*/private int randomLevel() {int lvl = 1;// 以 50% 的概率增加层级，直到达到最大层级while (random.nextInt(2) == 0 && lvl < MAX_LEVEL) {lvl++;}return lvl;}/*** 向跳跃表中插入一个键值。* @param key 要插入的键值*/public void insert(int key) {int lvl = randomLevel(); // 随机生成节点的层级// 更新数组用于记录每一层的前驱节点Node[] update = new Node[MAX_LEVEL];// 初始化更新数组，将每一层的前驱节点设为头节点for (int i = 0; i < MAX_LEVEL; i++) {update[i] = head;}Node current = head;// 从最高层开始，找到每一层的插入位置for (int i = level - 1; i >= 0; i--) {while (current.next[i] != null && current.next[i].key < key) {current = current.next[i];}update[i] = current;}// 如果当前层级大于跳跃表的层级，则更新跳跃表的层级if (lvl > level) {level = lvl;}Node newNode = new Node(key, lvl); // 创建新节点// 更新每一层的指针for (int i = 0; i < lvl; i++) {newNode.next[i] = update[i].next[i];update[i].next[i] = newNode;}}/*** 在跳跃表中查找一个键值。* @param key 要查找的键值* @return 如果找到返回 true，否则返回 false*/public Boolean search(int key) {Node current = head;// 从最高层开始，找到可能包含键值的节点for (int i = level - 1; i >= 0; i--) {while (current.next[i] != null && current.next[i].key < key) {current = current.next[i];}}// 检查是否找到键值if (current.next[0] != null && current.next[0].key == key) {return true;} else {return false;}}/*** 从跳跃表中删除一个键值。* @param key 要删除的键值*/public void delete(int key) {Node[] update = new Node[MAX_LEVEL];// 初始化更新数组，将每一层的前驱节点设为头节点for (int i = 0; i < MAX_LEVEL; i++) {update[i] = head;}Node current = head;// 从最高层开始，找到每一层的删除位置for (int i = level - 1; i >= 0; i--) {while (current.next[i] != null && current.next[i].key < key) {current = current.next[i];}update[i] = current;}current = current.next[0];// 如果找到要删除的节点if (current != null && current.key == key) {// 更新每一层的指针for (int i = 0; i < level; i++) {if (update[i].next[i] != current) {break;}update[i].next[i] = current.next[i];}// 如果删除后某一层为空，则降低跳跃表的层级while (level > 1 && head.next[level - 1] == null) {level--;}}}/*** 打印跳跃表的每一层。*/public void printList() {System.out.println("Skip List:");// 从最高层开始，打印每一层的节点for (int i = level - 1; i >= 0; i--) {Node current = head.next[i];System.out.print("Level " + i + ": ");while (current != null) {System.out.print(current.key + " ");current = current.next[i];}System.out.println();}}}

在HBase中的应用

MemStore：跳跃表是HBase的MemStore中的主要数据结构。MemStore是内存中的一个有序数据集，用于存储即将写入到磁盘的数据。跳跃表的高效插入和查找特性使得MemStore能够快速处理大量的写入请求，并在需要时将数据刷新到磁盘上。

Block Index：在HBase的存储引擎中，块索引（Block Index）也使用跳跃表来加速数据的定位。块索引保存了每个数据块的起始键和结束键，通过跳跃表的结构，可以快速确定一个键所在的数据块，从而减少磁盘的随机读取次数。

优点

快速的插入、删除和查找：跳跃表在平均情况下的插入、删除和查找操作的时间复杂度为O(log n)，这比传统的链表要快得多。

动态性：跳跃表能够在任何时间进行插入、删除和查找操作，而不需要进行任何预处理或重建操作。

易于实现：跳跃表的实现相对简单，不需要复杂的平衡操作，因此易于理解和实现。

缺点

空间开销：跳跃表需要为每个节点维护多个指针，这会增加空间的开销。在节点数较多的情况下，指针的维护可能会占用较大的内存空间。

性能波动：由于跳跃表的层数是随机生成的，因此在极端情况下，可能会出现层数过高的情况，导致性能下降。然而，这种情况的概率较低，可以通过调整随机概率函数来缓解。

布隆过滤器（Bloom Filter）

关于布隆过滤器，推荐先阅读这篇论文，里面详细介绍了布隆过滤器的原理、变体和在网络中的多种应用，以及使用时需要在空间效率和假阳性概率之间权衡。

原理

布隆过滤器是一种概率性的数据结构，用于判断一个元素是否可能存在于一个集合中。它通过使用多个哈希函数将元素映射到一个位数组中。当一个元素被添加到集合时，它会被多个哈希函数处理，每个哈希函数的结果会设置位数组中对应的位置为1。在查询时，同样使用这些哈希函数处理待查询的元素，如果位数组中所有对应的位置都为1，则认为该元素可能存在于集合中。否则，可以确定该元素一定不存在于集合中。

结构

布隆过滤器的核心是一个位数组和多个哈希函数。位数组的大小和哈希函数的数量会影响布隆过滤器的准确性和空间利用率。较大的位数组和较多的哈希函数可以降低误判率，但会增加空间的使用和计算的时间。

工作流程

1. 添加元素
   当一个元素被添加到布隆过滤器时，它会通过多个哈希函数生成多个整数，这些整数对应于位数组中的位置。然后，将这些位置的位设置为1。

2. 查询元素
   要判断一个元素是否存在于集合中，将其通过相同的哈希函数生成对应的位位置，并检查这些位置是否都为1。如果有任何一个位置为0，则可以确定该元素不存在于集合中。否则，认为该元素可能存在，但可能存在误判。

3. 误判率
   布隆过滤器的误判率是指错误地认为一个不存在的元素存在于集合中的概率。误判率可以通过调整位数组的大小和哈希函数的数量来控制。

在HBase中的应用

HFile：布隆过滤器被广泛应用于HBase的HFile中。HFile是HBase存储数据的基本单元，每个HFile包含多个数据块。在每个数据块中，布隆过滤器用于快速判断某个行键是否可能存在于该块中。当进行数据查询时，首先通过布隆过滤器快速筛选出可能包含目标行键的数据块，从而减少不必要的磁盘I/O操作。

Filter：HBase的过滤器（Filter）也可以利用布隆过滤器来加速数据的过滤过程。例如，在行键过滤器中，可以使用布隆过滤器来判断某个行键是否满足过滤条件，从而快速定位到目标数据。

优点

高效率：布隆过滤器的查询操作非常高效，时间复杂度为O(k)，其中k是哈希函数的数量。这使得它非常适合用于大数据场景中的快速查询。

节省空间：与传统的存储所有元素的方式相比，布隆过滤器所需的存储空间非常小。例如，存储一个包含数百万元素的集合可能只需要几千字节的空间。

并行性：布隆过滤器的查询和插入操作可以并行执行，因为它们不涉及任何共享资源的锁定。这使得它非常适用于大规模并行处理系统。

缺点

误判率：布隆过滤器存在一定的误判率，即错误地认为一个不存在的元素存在于集合中的概率。虽然可以通过调整参数来降低误判率，但无法完全消除。

无法删除元素：一旦一个元素被添加到布隆过滤器中，很难将其删除。因为多个元素可能共享同一个位数组中的位置，删除一个元素可能会导致误判率的增加。

参数调整复杂：布隆过滤器的性能和准确度高度依赖于位数组的大小和哈希函数的数量。选择合适的参数需要根据实际的数据量和查询需求进行仔细的测试和调整。