帶你讀《HBase原理與實踐》之二：基礎資料結構與算法

點選檢視第一章 點選檢視第三章

第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);

ret = Bytes.compare(a.qualif ierBytes, b.qualif ierBytes);

// 注意：timestamp越大，排序越靠前

ret = b.timestamp - a.timestamp;

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的資料。代碼如下所示：

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