点击查看第一章
点击查看第三章
第2章

基础数据结构与算法

著名的计算机科学家N.Wirth说过：程序=算法+数据结构。对于HBase这样的一个分布式数据库来说，它的代码规模已经非常庞大，如果加上测试代码以及序列化工具（Protobuf/Thrift）生成的代码，HBase项目（2.0分支）代码行数已经突破150万。但是，即使这样庞大的项目也是由一个个算法和数据结构组成。
本章将会介绍HBase用到的一些核心算法和数据结构。这里，我们假设读者已经具备了“数据结构”课程相关的基础知识，例如链表、栈、队列、平衡二叉树、堆等。
HBase的一个列簇（Column Family）本质上就是一棵LSM树（Log-Structured Merge-Tree）。LSM树分为内存部分和磁盘部分。内存部分是一个维护有序数据集合的数据结构。一般来讲，内存数据结构可以选择平衡二叉树、红黑树、跳跃表（SkipList）等维护有序集的数据结构，这里由于考虑并发性能，HBase选择了表现更优秀的跳跃表。磁盘部分是由一个个独立的文件组成，每一个文件又是由一个个数据块组成。对于数据存储在磁盘上的数据库系统来说，磁盘寻道以及数据读取都是非常耗时的操作（简称IO耗时）。因此，为了避免不必要的IO耗时，可以在磁盘中存储一些额外的二进制数据，这些数据用来判断对于给定的key是否有可能存储在这个数据块中，这个数据结构称为布隆过滤器（Bloom Filter）。
本章将介绍HBase的核心数据结构，主要包括跳跃表、LSM树和布隆过滤器。同时，为了使读者加深印象，我们设计了一个轻量级KV存储引擎MiniBase，并提供了一些相关的编程练习。

2.1　跳跃表

跳跃表（SkipList）是一种能高效实现插入、删除、查找的内存数据结构，这些操作的期望复杂度都是O(logN)。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。正因为这些优点，跳跃表广泛使用于KV数据库中，诸如Redis、LevelDB、HBase都把跳跃表作为一种维护有序数据集合的基础数据结构。
众所周知，链表这种数据结构的查询复杂度为O(N)，这里N是链表中元素的个数。在已经找到要删除元素的情况下，再执行链表的删除操作其实非常高效，只需把待删除元素前一个元素的next指针指向待删除元素的后一个元素即可，复杂度为O(1)，如图2-1所示。

图2-1　链表删除元素操作

但问题是，链表的查询复杂度太高，因为链表在查询的时候，需要逐个元素地查找。如果链表在查找的时候，能够避免依次查找元素，那么查找复杂度将降低。而跳跃表就是利用这一思想，在链表之上额外存储了一些节点的索引信息，达到避免依次查找元素的目的，从而将查询复杂度优化为O(logN)。将查询复杂度优化之后，自然也优化了插入和删除的复杂度。
1.定义
如图2-2所示，跳跃表的定义如下：

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

图2-2　跳跃表定义

2.查找
在跳跃表中查找一个指定元素的流程比较简单。如图2-3所示，以左上角元素（设为currentNode）作为起点：

• 如果发现currentNode后继节点的值小于等于待查询值，则沿着这条链表向后查询，否则，切换到当前节点的下一层链表。
• 继续查询，直到找到待查询值为止（或者currentNode为空节点）为止。
  

图2-3　在跳跃表中查找元素5的流程

3.插入
跳跃表的插入算法要复杂一点。如图2-4所示。首先，需要按照上述查找流程找到待插入元素的前驱和后继；然后，按照如下随机算法生成一个高度值：
// p是一个(0,1)之间的常数，一般取p=1/4或者1/2
public void randomHeight(double p){

int height = 0 ;
while(random.nextDouble() < p) height ++ ;
return height + 1;

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

图2-4　在跳跃表中插入元素48的流程

4.删除
删除操作和插入操作有点类似，请读者思考如何实现删除操作。
5.复杂度分析
这里，我们一起来评估跳跃表的时间和空间复杂度。

查询时间复杂度关键取决于从最左上角到达最底层走过的横向步数和纵向步数之和。我们反过来考虑这个过程，也就是从最底层达到最左上角s走过的期望步数（包括横向步数）。对第k层第j列节点来说，它只可能从以下两种情况跳过来：

• 第k - 1层第j列节点往上走，跳到第k层第j列节点。根据randomHeight (p)函数定义，往上走的概率为p。
• 第k层第j + 1列节点往左走，跳到第k层第j列节点。这种情况，第k层第j + 1列节点已经是垂直节点的最高点，也就是说，这个节点已经不能往上走，只能往左走。根据randomHeight (p)函数定义，往左走的概率为(1 - p)。

设Ck为往上跳k层的期望步数（包括纵向步数和横向步数），那么有：


由插入/删除的实现可以看出，插入/删除的时间复杂度和查询时间复杂度相等，故性质5成立。
因此，跳跃表的查找、删除、插入的复杂度都是O(logN)。

2.2　LSM树

LSM树本质上和B+树一样，是一种磁盘数据的索引结构。但和B+树不同的是，LSM树的索引对写入请求更友好。因为无论是何种写入请求，LSM树都会将写入操作处理为一次顺序写，而HDFS擅长的正是顺序写（且HDFS不支持随机写），因此基于HDFS实现的HBase采用LSM树作为索引是一种很合适的选择。
LSM树的索引一般由两部分组成，一部分是内存部分，一部分是磁盘部分。内存部分一般采用跳跃表来维护一个有序的KeyValue集合。磁盘部分一般由多个内部KeyValue有序的文件组成。
1.KeyValue存储格式
一般来说，LSM中存储的是多个KeyValue组成的集合，每一个KeyValue一般都会用一个字节数组来表示。这里，首先需要来理解KeyValue这个字节数组的设计。
以HBase为例，这个字节数组串设计如图2-6所示。

图2-6　HBase rowkey组成
总体来说，字节数组主要分为以下几个字段。其中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：占用qualif ierLen个字节，用来存储Qualifier的二进制内容。注意，HBase并没有单独分配字节用来存储qualifierLen，因为可以通过keyLen和其他字段的长度计算出qualif ierLen。代码如下：
  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部分的设计。
在比较这些KeyValue的大小顺序时，HBase按照如下方式（伪代码）来确定大小关系：
int compare(KeyValue a, KeyValue b){
int ret = Bytes.compare(a.rowKeyBytes, b.rowKeyBytes);
if(ret != 0) return ret;
ret = Bytes.compare(a.familyBytes, b.familyBytes);
if(ret != 0) return ret;
ret = Bytes.compare(a.qualif ierBytes, b.qualif ierBytes);
if(ret != 0) return ret;
// 注意：timestamp越大，排序越靠前
ret = b.timestamp - a.timestamp;
if(ret != 0) return ret;
ret = a.type - b.type;
return ret;
}
注意，在HBase中，timestamp越大的KeyValue，排序越靠前。因为用户期望优先读取到那些版本号更新的数据。
上面以HBase为例，分析了HBase的KeyValue结构设计。通常来说，在LSM树的KeyValue中的Key部分，有3个字段必不可少：

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

先看一个简单的问题：现在有K个文件，其中第i个文件内部存储有Ni个正整数（这些整数在文件内按照从小到大的顺序存储），如何设计一个算法将K个有序文件合并成一个大的有序文件？在排序算法中，有一类排序算法叫做归并排序，里面就有大家熟知的两路归并实现。现在相当于K路归并，因此可以拓展一下，思路类似。对每个文件设计一个指针，取出K个指针中数值最小的一个，然后把最小的那个指针后移，接着继续找K个指针中数值最小的一个，继续后移指针……直到N个文件全部读完为止，如图2-7所示。

图2-7　多路归并算法

算法复杂度分析起来也较为容易，首先用一个最小堆来维护K个指针，每次从堆中取最小值，开销为logK，最多从堆中取 Ni次元素。因此最坏复杂度就是 Ni×logK。
核心实现如下：
public class KMergeSort {
public interface FileReader {

// true to indicate the f ile still has some data, false means EOF.
boolean hasNext() throws IOException;

// Read the next value from f ile, and move the f ile read offset.
int next() throws IOException;

}

public interface FileWriter {

void append(int value) throws IOException;

}

public void kMergeSort(f inal List 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()) {
    heap.add(new Pair<>(fr, fr.next()));
  }
}
while (!heap.isEmpty()) {
  Pair<FileReader, Integer> current = heap.poll();
  writer.append(current.getValue());
  FileReader currentReader = current.getKey();
  if (currentReader.hasNext()) {
    heap.add(new Pair<>(currentReader, currentReader.next()));
  }
}

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

图2-8　LSM树索引结构

LSM树索引结构如图2-8所示。内存部分导出形成一个有序数据文件的过程称为f lush。为了避免flush影响写入性能，会先把当前写入的MemStore设为Snapshot，不再容许新的写入操作写入这个Snapshot的MemStore。另开一个内存空间作为MemStore，让后面的数据写入。一旦Snapshot的MemStore写入完毕，对应内存空间就可以释放。这样，就可以通过两个MemStore来实现稳定的写入性能。
在整个数据写入过程中，LSM树全部都是使用append操作（磁盘顺序写）来实现数据写入的，没有使用任何seek+write（磁盘随机写）的方式来写入。无论HDD还是SSD，磁盘的顺序写操作性能和延迟都远好于磁盘随机写。因此LSM树是一种对写入极为友好的索引结构，它能将磁盘的写入带宽利用到极致。
随着写入的增加，内存数据会不断地刷新到磁盘上。最终磁盘上的数据文件会越来越多。如果数据没有任何的读取操作，磁盘上产生很多的数据文件对写入并无影响，而且这时写入速度是最快的，因为所有IO都是顺序IO。但是，一旦用户有读取请求，则需要将大量的磁盘文件进行多路归并，之后才能读取到所需的数据。因为需要将那些Key相同的数据全局综合起来，最终选择出合适的版本返回给用户，所以磁盘文件数量越多，在读取的时候随机读取的次数也会越多，从而影响读取操作的性能。
为了优化读取操作的性能，我们可以设置一定策略将选中的多个hfile进行多路归并，合并成一个文件。文件个数越少，则读取数据时需要seek操作的次数越少，读取性能则越好。
一般来说，按照选中的文件个数，我们将compact操作分成两种类型。一种是major compact，是将所有的hf ile一次性多路归并成一个文件。这种方式的好处是，合并之后只有一个文件，这样读取的性能肯定是最高的；但它的问题是，合并所有的文件可能需要很长的时间并消耗大量的IO带宽，所以major compact不宜使用太频繁，适合周期性地跑。
另外一种是minor compact，即选中少数几个hf ile，将它们多路归并成一个文件。这种方式的优点是，可以进行局部的compact，通过少量的IO减少文件个数，提升读取操作的性能，适合较高频率地跑；但它的缺点是，只合并了局部的数据，对于那些全局删除操作，无法在合并过程中完全删除。因此，minor compact虽然能减少文件，但却无法彻底清除那些delete操作。而major compact能完全清理那些delete操作，保证数据的最小化。
总结：LSM树的索引结构本质是将写入操作全部转化成磁盘的顺序写入，极大地提高了写入操作的性能。但是，这种设计对读取操作是非常不利的，因为需要在读取的过程中，通过归并所有文件来读取所对应的KV，这是非常消耗IO资源的。因此，在HBase中设计了异步的compaction来降低文件个数，达到提高读取性能的目的。由于HDFS只支持文件的顺序写，不支持文件的随机写，而且HDFS擅长的场景是大文件存储而非小文件，所以上层HBase选择LSM树这种索引结构是最合适的。

2.3　布隆过滤器

1.案例
如何高效判断元素w是否存在于集合A之中？首先想到的答案是，把集合A中的元素一个个放到哈希表中，然后在哈希表中查一下w即可。这样确实可以解决小数据量场景下元素存在性判定，但如果A中元素数量巨大，甚至数据量远远超过机器内存空间，该如何解决问题呢？
实现一个基于磁盘和内存的哈希索引当然可以解决这个问题。而另一种低成本的方式就是借助布隆过滤器（Bloom Filter）来实现。
布隆过滤器由一个长度为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数组。
下面举个例子，如图2-9所示，A = {x, y, z}，N = 18，K = 3。

图2-9　布隆过滤器算法示例

初始化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。
此时，对于元素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中。
因此，布隆过滤器串对任意给定元素w，给出的存在性结果为两种：

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

在论文中证明，当N取K*|A|/ln2时（其中|A|表示集合A元素个数），能保证最佳的误判率，所谓误判率也就是过滤器判定元素可能在集合中但实际不在集合中的占比。
举例来说，若集合有20个元素，K取3时，则设计一个N = 3×20/ln2 = 87二进制串来保存布隆过滤器比较合适。
2.算法实现
布隆过滤器的代码实现很短，如下所示：
public class BloomFilter {
private int k;
private int bitsPerKey;
private int bitLen;
private byte[] result;

public BloomFilter(int k, int bitsPerKey) {

this.k = k;
this.bitsPerKey = bitsPerKey;

}

public byte[] generate(byte[][] keys) {

assert keys != null;
bitLen = keys.length * bitsPerKey;
bitLen = ((bitLen + 7) / 8) << 3; // align the bitLen.
bitLen = bitLen < 64   64 : bitLen;
result = new byte[bitLen >> 3]; // each byte have 8 bit.
for (int i = 0; i < keys.length; i++) {
  assert keys[i] != null;
  int h = Bytes.hash(keys[i]);
  for (int t = 0; t < k; t++) {
    int idx = (h % bitLen + bitLen) % bitLen;
    result[idx / 8] |= (1 << (idx % 8));
    int delta = (h >> 17) | (h << 15);
    h += delta;
  }
}
return result;

}

public boolean contains(byte[] key) {

assert result != null;
int h = Bytes.hash(key);
for (int t = 0; t < k; t++) {  // Hash k times
  int idx = (h % bitLen + bitLen) % bitLen;
  if ((result[idx / 8] & (1 << (idx % 8))) == 0) {
    return false;
  }
  int delta = (h >> 17) | (h << 15);
  h += delta;
}
return true;

}
}
有两个地方说明一下：

• 在构造方法BloomFilter(int k, int bitsPerKey)中，k表示每个Key哈希的次数，bitsPerkey表示每个Key占用的二进制bit数，若有x个Key，则N=x*bitsPerKey。
• 在实现中，对Key做k次哈希时，算出第一次哈希值h之后，可借助h位运算来实现二次哈希，甚至三次哈希。这样性能会比较好。
  3.案例解答

有了布隆过滤器这样一个存在性判断之后，我们回到最开始提到的案例。把集合A的元素按照顺序分成若干个块，每块不超过64KB，每块内的多个元素都算出一个布隆过滤器串，多个块的布隆过滤器组成索引数据。为了判断元素w是否存在于集合A中，先对w计算每一个块的布隆过滤器串的存在性结果，若结果为肯定不存在，则继续判断w是否可能存在于下一个数据块中。若结果为可能存在，则读取对应的数据块，判断w是否在数据块中，若存在则表示w存在于集合A中；若不存在则继续判断w是否在下一个数据块中。
这样就解决了这个问题。读者可以思考一下：在64KB的数据块中，平均每个Key占用1000字节，且在做3次哈希的情况下，需要占用多少字节的空间来存储布隆过滤器的二进制？
4. HBase与布隆过滤器
正是由于布隆过滤器只需占用极小的空间，便可给出“可能存在”和“肯定不存在”的存在性判断，因此可以提前过滤掉很多不必要的数据块，从而节省了大量的磁盘IO。HBase的Get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省大量磁盘IO。
在HBase 1.x版本中，用户可以对某些列设置不同类型的布隆过滤器，共有3种类型。

• NONE：关闭布隆过滤器功能。
• ROW：按照rowkey来计算布隆过滤器的二进制串并存储。Get查询的时候，必须带- rowkey，所以用户可以在建表时默认把布隆过滤器设置为ROW类型。
• ROWCOL：按照rowkey+family+qualif ier这３个字段拼出byte[]来计算布隆过滤器值并存储。如果在查询的时候，Get能指定rowkey、family、qualif ier这３个字段，则肯定可以通过布隆过滤器提升性能。但是如果在查询的时候，Get中缺少rowkey、family、qualifier中任何一个字段，则无法通过布隆过滤器提升性能，因为计算布隆过滤器的Key不确定。

注意，一般意义上的Scan操作，HBase都没法使用布隆过滤器来提升扫描数据性能。原因很好理解，同样是因为布隆过滤器的Key值不确定，所以没法计算出哈希值对比。但是，在某些特定场景下，Scan操作同样可以借助布隆过滤器提升性能。
对于ROWCOL类型的布隆过滤器来说，如果在Scan操作中明确指定需要扫某些列，如下所示：
Scan scan = new Scan()
.addColumn(FAMILY0, QUALIFIER0)
.addColumn(FAMILY1, QUALIFIER1)
那么在Scan过程中，碰到KV数据从一行换到新的一行时，是没法走ROWCOL类型布隆过滤器的，因为新一行的key值不确定；但是，如果在同一行数据内切换列时，则能通过ROWCOL类型布隆过滤器进行优化，因为rowkey确定，同时column也已知，也就是说，布隆过滤器中的Key确定，所以可以通过ROWCOL优化性能，详见HBASE-4465。
另外，在HBASE-20636中，腾讯团队介绍了一种很神奇的设计。他们的游戏业务rowkey是这样设计的：
rowkey=#
也就是用userid和其他字段拼接生成rowkey。而且业务大部分的请求都按照某个指定用户的userid来扫描这个用户下的所有数据，即按照userid来做前缀扫描。基于这个请求特点，可以把rowkey中固定长度的前缀计算布隆过滤器，这样按照userid来前缀扫描时（前缀固定，所以计算布隆过滤器的Key值也就固定），同样可以借助布隆过滤器优化性能，HBASE-20636中提到有一倍以上的性能提升。另外，对于Get请求，同样可以借助这种前缀布隆过滤器提升性能。因此，这种设计对Get和基于前缀扫描的Scan都非常友好。
这个功能已经在HBase 2.x版本上实现，感兴趣的读者可以尝试。

2.4　设计KV存储引擎MiniBase

前面我们已经介绍了LSM树索引结构中最核心的数据结构和算法。在理解了这些基本知识后，我们可以自己动手设计一个嵌入式KV存储引擎。
本节实践性很强，我们将动手实现一个高吞吐低延迟的KV存储引擎。这个KV存储引擎非常轻量级，可以说是HBase的一个极简版本，所以，我们暂且称它为MiniBase，即HBase的迷你版本。
MiniBase作为嵌入式存储引擎，提供了一些非常简洁的接口，如下所示：
public interface MiniBase extends Closeable {

void put(byte[] key, byte[] value) throws IOException;

byte[] get(byte[] key) throws IOException;

void delete(byte[] key) throws IOException;

/**

• Fetch all the key values whose key located in the range [startKey, stopKey)
• @param startKey start key to scan (inclusive), if byte[0], means -oo
• @param stopKey to stop the scan. (exclusive), if byte[0], means +oo
• @return Iterator for fetching the key value one by one.
  */

Iter scan(byte[] startKey, byte[] stopKey) throws IOException;

interface Iter {

boolean hasNext() throws IOException;

KeyValue next() throws IOException;

}
}
MiniBase只容许使用byte[]作为Key和Value，事实上，其他类型的基本数据类型可以非常容易地转化成byte[]：例如，String s = "abc"，那么通过Bytes.toBytes(s)可以转化成byte[]，其他数据类型类似。下面对接口部分做简要介绍：

• put/get/delete这3个接口非常容易理解，即增加、读取、删除一个key。如碰到异常，则直接抛出IOException。
• scan接口需要传入扫描的数据范围[startKey, stopkey)。注意，如果startKey=byte[0]，则表示扫描（- ∞, stopKey）的所有数据，stopkey=byte[0]也是类似的含义。由于Scan操作可能返回内存无法存放的大量数据，因此，我们设计了一个迭代器用来读取数据。用户只需不断地执行next()，直到hasNext()返回false，即可从小到大依次读取存储引擎中的所有数据。

1.MiniBase核心设计
MiniBase的总体结构如图2-10所示。MiniBase是一个标准的LSM树索引结构，分内存部分和磁盘部分。

图2-10　MiniBase总体结构

内存部分为MemStore。客户端不断地写入数据，当MemStore的内存超过一定阈值时，MemStore会flush成一个磁盘文件。可以看到图2-10中的MemStore分成MutableMemstore和ImmutableMemstore两部分，MutableMemstore由一个ConcurrentSkipListMap组成，容许写入；ImmutableMemstore也是一个ConcurrentSkipListMap，但是不容许写入。这里设计两个小的MemStore，是为了防止在f lush的时候，MiniBase无法接收新的写入。假设只有一个MutableMemstore，那么一旦进入f lush过程，MutableMemstore就无法写入，而此时新的写入就无法进行。
磁盘部分为DiskStore，由多个DiskFile组成，每一个DiskFile就是一个磁盘文件。ImmutableMemstore执行完flush操作后，就会生成一个新的DiskFile，存放到DiskStore中。当然，为了有效控制DiskStore中的DiskFile个数，我们为MiniBase设计了Compaction策略。目前的Compaction策略非常简单—当DiskStore的DiskFile数量超过一个阈值时，就把所有的DiskFile进行Compact，最终合并成一个DiskFile。
下面考虑DiskFile的文件格式设计。在设计之前，需要注意几个比较核心的问题：

• DiskFile必须支持高效的写入和读取。由于MemStore的写入是顺序写入，如果flush速度太慢，则可能会阻塞后续的写入，影响写入吞吐，因此flush操作最好也设计成顺序写。LSM树结构的劣势就是读取性能会有所牺牲，如果在DiskFile上能实现高效的数据索引，则可以大幅提升读取性能，例如考虑布隆过滤器设计。
• 由于磁盘空间很大，而内存空间相对很小，所以DiskFile的数据必须分成众多小块，一次IO操作只读取一小部分的数据。通过读取多个数据块来完成一次区间的扫描。
  基于这些考虑，我们为MiniBase的DiskFile做了简单的设计，如图2-11所示。

图2-11　DiskFile存储格式

一个DiskFile由３种类型的数据块组成，分别是DataBlock、IndexBlock、MetaBlock。

• DataBlock ：主要用来存储有序的KeyValue集合—KeyValue-1，KeyValue-2，…，KeyValue-N，这些KeyValue的大小顺序与其存储顺序严格一致。另外，在MiniBase中，默认每一个Block约为64kB，当然用户也可以自己设置Block的大小。注意，一个DiskFile内可能有多个Block，具体的Block数量取决于文件内存储的总KV数据量。

• IndexBlock ：一个DiskFile内有且仅有一个IndexBlock。它主要存储多个DataBlock的索引数据，每个DataBlock的索引数据包含以下４个字段：

  • lastKV ：该DataBlock的最后一个KV，查找时，先查IndexBlock，根据lastKV定位到对应的DataBlock，然后直接读取这个DataBlock到内存即可。
  • offset ：该DataBlock在DiskFile中的偏移位置，查找时，用offset值去文件中Seek，并读取DataBlock的数据。
  • size：该DataBlock占用的字节长度。
  • bloomFilter：该DataBlock内所有KeyValue计算出的布隆过滤器字节数组。

• MetaBlock ：和IndexBlock一样，一个DiskFile中有且仅有一个MetaBlock；同时MetaBlock是定长的，因此可以直接通过定位diskf ile.f ilesize - len(MetaBlock)来读取MetaBlock，而无需任何索引。主要用来保存DiskFile级别的元数据信息：

  • fileSize ：该DiskFile的文件总长度，可以通过对比这个值和当前文件真实长度，判断文件是否损坏。
  • blockCount：该DiskFile拥有的Block数量。

• blockIndexOffset：该DiskFile内的IndexBlock的偏移位置，方便定位到IndexBlock。

  • blockIndexSize：IndexBlock的字节长度。
    假设用户需要读取指定DiskFile中key='abc'对应的value数据，那么可以按照如下流程进行IO读取：首先，由于DiskFile中MetaBlock的长度是定长的，所以很容易定位到MetaBlock的位置，并读取MetaBlock的二进制内容。MetaBlock中存储着blockIndexOffset字段，这个字段指向着IndexBlock存储的位置，因此可以定位到这个位置并读取blockIndexSize字节的二进制内容，这样就完成了IndexBlock的读取。由于IndexBlock中存储着每一个DataBlock对应的数据区间，通过二分查找可以很方便定位到key='abc'在哪个DataBlock中，再根据对应的DataBlock的offset和size，就能顺利完成DataBlock的IO读取。

在MemStore的数据导出成DiskFile时，按照DiskFile设计的存储格式，我们应该是可以保证顺序写入的。请读者自行思考DiskFile的生成流程，这里不再赘述。
2. KeyValue组成
在MiniBase中，只容许两种更新操作：Put操作，Delete操作。由于LSM树索引中存放的是操作记录，并不是真实数据，所以我们需要把KeyValue结构设计成操作记录的格式。
我们设计的KeyValue结构如下所示：
public enum Op {
Put((byte) 0),
Delete((byte) 1);

private byte code;

Op(byte code) {

this.code = code;

}
}

public class KeyValue{
private byte[] key;
private byte[] value;
private Op op;
private long sequenceId;
// ...other methods
}
这里，主要有（key, value, Op, sequenceId）这4个字段，Op有Put和Delete两种操作类型。重点需要理解SequenceId字段，我们会为每一次Put/Delete操作分配一个自增的唯一sequenceId，这样每一个操作都对应一个sequenceId。读取的时候，只能得到小于等于当前sequenceId的Put/Delete操作，这样保证了本次读取不会得到未来某个时间点的数据，实现了最简单的Read Committed的事务隔离级别。
由于KeyValue在MemStore和DiskFile中都是有序存放的，所以需要为KeyValue实现Comparable接口，如下所示：
public class KeyValue implements Comparable{
// ...
@Override
public int compareTo(KeyValue kv) {

if (kv == null) {
  throw new IllegalArgumentException("kv to compare shouldn't be null");
}
int ret = Bytes.compare(this.key, kv.key);
if (ret != 0) {
  return ret;
}
if (this.sequenceId != kv.sequenceId) {
  return this.sequenceId > kv.sequenceId   -1 : 1;
}
if (this.op != kv.op) {
  return this.op.getCode() > kv.op.getCode()   -1 : 1;
}
return 0;

}
}
其中，compareTo方法定义了KeyValue的比较顺序。Key小的KeyValue排在更前面，这是因为用户期望按照从小到大的顺序读取数据。注意在Key相同的情况下，sequenceId更大的KeyValue排在更前面，这是因为sequenceId越大，说明这个Put/Delete操作版本越新，它更可能是用户需要读取的数据。
（1）写入流程
无论是Put操作还是Delete操作，我们都需要一个自增的sequenceId，用于构建KeyValue结构。例如，Put操作的写入代码如下：
@Override
public void put(byte[] key, byte[] value) throws IOException {
this.memStore.add(KeyValue.createPut(key, value, sequenceId.incrementAndGet()));
}
写入到MemStore之后，需要考虑的是，数据量达到一个阈值之后，需要开始f lush。在f lush的时候，先将MutableMemstore切换成ImmutableMemstore，切换过程中必须保证没有写入操作。所以，我们用一个读写锁updateLock来控制写入操作和Flush操作的互斥。写入时，先拿到updateLock的读锁，写完之后释放，而在切换MemStore时拿到updateLock的写锁，切换完之后释放。
因此，MemStore写入代码大致如下：
public void add(KeyValue kv) throws IOException {
f lushIfNeeded(true);
updateLock.readLock().lock();
try {

KeyValue prevKeyValue;
if ((prevKeyValue = kvMap.put(kv, kv)) == null) {
  dataSize.addAndGet(kv.getSerializeSize());
} else {
  dataSize.addAndGet(kv.getSerializeSize() - prevKeyValue.getSerializeSize());
}

} f inally {

updateLock.readLock().unlock();

}
f lushIfNeeded(false);
}
注意，第一个f lushIfNeeded方法在发现MemStore满的时候，将抛出IOException，告诉用户MemStore已经满了，此刻重试即可。第二个f lushIfNeeded将提交MemStore的Flush任务，Flush线程收到请求后开始跑Flush任务。另外，在成功地把KV放入到ConcurrentSkipListMap之后，需要更新MemStore的dataSize。这里有两种情况：之前KV不存在，则直接累计kv.getSerializeSize即可；之前KV存在，则将二者差值累积到dataSize上。
dataSize为当前MemStore内存占用字节数，用于判断是否达到Flush阈值。它是一个AtomicLong变量，所以在写入高并发的情景下，该变量可能成为一个性能瓶颈，因为所有的并发写入都需要串行执行这个CAS操作。但就目前来说，对性能并不会产生太大的影响。
（2）读取流程
读取流程相对要复杂很多，从MiniBase结构图（图2-10）可以看出，有MutableMemstore
和ImmutableMemstore两个内存有序KV集合、多个DiskFile有序集合。在Scan的时候，需要把多个有序集合通过多路归并算法合并成一个有序集合，然后过滤掉不符合条件的版本，将正确的KV返回给用户。
对于多路归并算法，我们已经在2.2节中介绍，这里不再赘述。重点阐述如何过滤不符合条件的数据版本。
假设用户按照图2-12左侧所示，依次执行了7个操作（注意，每个操作的sequenceId都是自增的），那么多路归并之后的数据如图2-12右侧所示。

图2-12　多路归并后读取的KeyValue列表

对于同一个Key的不同版本，我们只关心最新的版本。假设用户读取时能看到的sequenceld≤101的数据，那么读取流程逻辑如下：

• 对于Key=A的版本，我们只关注（A,Delete,100）这个版本，该版本是删除操作，说明后面所有key=A的版本都不会被用户看到。
• 对于Key=B的版本，我们只关心（B,Put,101）这个版本，该版本是Put操作，说明该Key没有被删除，可以被用户看到。
• 对于Key=C的版本，我们只关心（C,Put,95）这个版本，该版本是Put操作，说明该Key没有被删除，可以被用户看到。

于是，对于全表扫描的scan操作，MiniBase将返回（B,Put,101）和（C,Put,95）这两个KeyValue给用户。
对应的代码实现，可以在MiniBase源码的MStore#ScanIter中看到，这里不再赘述。
3.思考与练习
设计存储引擎是本章最核心的部分，完整的项目代码，我们已经开源在GitHub(https://github.com/openinx/minibase)上。为了让读者更深入地理解MiniBase的实现原理，我们特意设计了一些练习，这样读者可以亲自参与MiniBase的设计和实现，学以致用。
问题1.
向MiniBase写入数据时，是直接写到MemStore中的。在MemStore刷新到磁盘之前，若进程由于异常原因退出，则用户成功写入MemStore的数据将丢失，无法恢复。一种常见的解决方案就是，在将数据写入MemStore之前，先写一份操作日志，这样即使进程退出，仍然可以通过操作日志来恢复MemStore的数据。请为MiniBase实现写WAL日志功能，保证其在进程崩溃之后依然可以从WAL日志中恢复MemStore的数据。
这里给出几个小提示：

• 随着用户的不断写入，WAL日志可能无限增长。这样进程重启后，恢复数据时可能需花费很长时间。因此，需要控制WAL日志的数据量，事实上一旦MemStore执行了f lush操作，那么之前的WAL日志都可以清理。
• 在高并发写入的情况下，会有多线程同时写入WAL日志。但由于必须保证WAL日志的完整性，需通过排他锁来控制每次写入WAL日志的操作，即多个并发写入将在写WAL日志这个步骤中严格串行，这样会极大地限制吞吐量。请思考该如何设计写WAL日志流程，以达到提升写入吞吐的目的。
  问题2.

MiniBase在Get/Scan实现中，涉及读取Block的地方，并没有使用LRU Cache，而是在每次读Block的时候直接去磁盘文件中读Block。请你为MiniBase设计一种LRU Cache，把经常访问的Block缓存在内存中，这样下次读取Block时，可以省去读取磁盘的开销，降低访问延迟。
实现一个LRU Cache并不难，网上也有很多资料和库。我们容许读者使用成熟的类库来完成练习。但有如下一些注意事项：

• 需要用参数控制LRU缓存的总大小，这样用户可以为不同的机器配置不同大小的LRU Cache。
• 请将Block的Cache命中率百分比在日志中打印出来，便于用户做进一步性能调优。
• 对比使用LRU Cache前后，MiniBase的Get/Scan吞吐分别提升多少。
  问题3.

DiskFile中的DataBlock存放着有序的多个KeyValue集合。但目前Get/Scan的实现非常简单，当需要做Block内Seek时，现在是直接依次检查各个KeyValue，这种实现相对低效。但由于KeyValue的有序性，我们也可以借助二分搜索来提升DataBlock的读取性能。请为DataBlock的Seek操作实现二分查找。
其实，当存放的KeyValue字节数很小时，Block内将存放众多KeyValue。这时二分查找比顺序查找高效很多。在实现该功能后，请对比测试KeyValue长度分别为10和1000时的性能。理论上，采用二分后，KeyValue长度为10的性能将远优于顺序读取。
问题4.
当前，在实现MiniBase的Get接口时，我们采用了一个很简单粗暴的实现方式，即通过Scan接口得到迭代器，然后将迭代器执行一次Next，就获取了Get的数据。代码如下所示：
@Override
public KeyValue get(byte[] key) throws IOException {
KeyValue result = null;
Iter it = scan(key, Bytes.EMPTY_BYTES);
if (it.hasNext()) {

KeyValue kv = it.next();
if (Bytes.compare(kv.getKey(), key) == 0) {
  result = kv;
}

}
return result;
}
事实上，由于Get操作的特殊性，我们可以通过布隆过滤器过滤掉大量无效的Block数据块。请重新设计Get操作的实现，通过布隆过滤器来优化Get操作的性能，并对比当前版本的Get性能，看看相差多少。
拓展阅读
［1］ Choose Concurrency-Friendly Data Structures: http://www.drdobbs.com/parallel/choose-concurrency-friendly-data-structu/208801371?pgno=1
［2］ Skip Lists: A Probabilistic Alternative to Balanced Trees: http://www.epaperpress.com/sortsearch/download/skiplist.pdf
［3］ Skip List源代码Java版本：https://github.com/openinx/algorithm-solution/blob/master/template/sort/SkipList.java
［4］ The Log-Structured Merge-Tree (LSM-Tree): https://www.cs.umb.edu/~poneil/lsmtree.pdf
［5］ Bloom Filter: https://en.wikipedia.org/wiki/Bloom_filter