從B+樹到LSM樹，及LSM樹在HBase中的應用

前言

在有代表性的關系型數(shù)據(jù)庫如MySQL、SQL Server、Oracle中，數(shù)據(jù)存儲與索引的基本結(jié)構(gòu)就是我們耳熟能詳?shù)腂樹和B+樹。而在一些主流的NoSQL數(shù)據(jù)庫如HBase、Cassandra、LevelDB、RocksDB中，則是使用日志結(jié)構(gòu)合并樹（Log-structured Merge Tree，LSM Tree）來組織數(shù)據(jù)。本文先由B+樹來引出對LSM樹的介紹，然后說明HBase中是如何運用LSM樹的。

回顧B+樹

為什么在RDBMS中我們需要B+樹（或者廣義地說，索引）？一句話：減少尋道時間。在存儲系統(tǒng)中廣泛使用的HDD是磁性介質(zhì)+機械旋轉(zhuǎn)的，這就使得其順序訪問較快而隨機訪問較慢。使用B+樹組織數(shù)據(jù)可以較好地利用HDD的這種特點，其本質(zhì)是多路平衡查找樹。下圖是一棵高度為3的4路B+樹示例。

與普通B樹相比，B+樹的非葉子節(jié)點只有索引，所有數(shù)據(jù)都位于葉子節(jié)點，并且葉子節(jié)點上的數(shù)據(jù)會形成有序鏈表。B+樹的主要優(yōu)點如下：

• 結(jié)構(gòu)比較扁平，高度低（一般不超過4層），隨機尋道次數(shù)少；
• 數(shù)據(jù)存儲密度大，且都位于葉子節(jié)點，查詢穩(wěn)定，遍歷方便；
• 葉子節(jié)點形成有序鏈表，范圍查詢轉(zhuǎn)化為順序讀，效率高。相對而言B樹必須通過中序遍歷才能支持范圍查詢。

當然，B+樹也不是十全十美的，它的主要缺點有兩個：

• 如果寫入的數(shù)據(jù)比較離散，那么尋找寫入位置時，子節(jié)點有很大可能性不會在內(nèi)存中，最終會產(chǎn)生大量的隨機寫，性能下降。下圖來自TokuDB的PPT，說明了這一點。

• 如果B+樹已經(jīng)運行了很長時間，寫入了很多數(shù)據(jù)，隨著葉子節(jié)點分裂，其對應的塊會不再順序存儲，而變得分散。這時執(zhí)行范圍查詢也會變成隨機讀，效率降低了。

可見，B+樹在多讀少寫（相對而言）的情境下比較有優(yōu)勢，在多寫少讀的情境下就不是很有威力了。當然，我們可以用SSD來獲得成倍提升的讀寫速率，但成本同樣高昂，對海量存儲集群而言不太可行。日志結(jié)構(gòu)合并樹（LSM Tree）就是作為B+樹的替代方案產(chǎn)生的。

認識LSM樹

LSM樹實際上不是一棵樹，而是2個或者多個樹或類似樹的結(jié)構(gòu)（注意這點）的集合。下圖示出最簡單的有2個結(jié)構(gòu)的LSM樹。

（上圖中，少了一個字母D）

在LSM樹中，最低一級也是最小的C0樹位于內(nèi)存里，而更高級的C1、C2...樹都位于磁盤里。數(shù)據(jù)會先寫入內(nèi)存中的C0樹，當它的大小達到一定閾值之后，C0樹中的全部或部分數(shù)據(jù)就會刷入磁盤中的C1樹，如下圖所示。

由于內(nèi)存的讀寫速率都比外存要快非常多，因此數(shù)據(jù)寫入C0樹的效率很高。并且數(shù)據(jù)從內(nèi)存刷入磁盤時是預排序的，也就是說，LSM樹將原本的隨機寫操作轉(zhuǎn)化成了順序?qū)懖僮?，寫性能大幅提升。不過，它的tradeoff就是犧牲了一部分讀性能，因為讀取時需要將內(nèi)存中的數(shù)據(jù)和磁盤中的數(shù)據(jù)合并。總體上來講這種tradeoff還是值得的，因為：

• 可以先讀取內(nèi)存中C0樹的緩存數(shù)據(jù)。內(nèi)存的效率很高，并且根據(jù)局部性原理，最近寫入的數(shù)據(jù)命中率也高。
• 寫入數(shù)據(jù)未刷到磁盤時不會占用磁盤的I/O，不會與讀取競爭。讀取操作就能取得更長的磁盤時間，變相地彌補了讀性能差距。

在實際應用中，為了防止內(nèi)存因斷電等原因丟失數(shù)據(jù)，寫入內(nèi)存的數(shù)據(jù)同時會順序在磁盤上寫日志，類似于我們常見的預寫日志（WAL），這就是LSM這個詞中Log一詞的來歷。另外，如果有多級樹的話，低級的樹在達到大小閾值后也會在磁盤中進行合并，如下圖所示。

下面以HBase為例來簡要講解LSM樹是如何發(fā)揮其作用的。

HBase中的LSM樹

在之前的學習中，我們已經(jīng)了解HBase的讀寫流程與MemStore的作用。MemStore作為列族級別的寫入和讀取緩存，它就是HBase中LSM樹的C0層。并且它確實也沒有采用樹形結(jié)構(gòu)來存儲，而是采用了跳表——一種替代自平衡BST的結(jié)構(gòu)。MemStore Flush的過程，也就是LSM樹中C0層刷寫到C1層的過程，而LSM中的日志對應到HBase自然就是HLog了。

為了方便理解，再次祭出之前用過的HBase讀寫流程簡圖。

HFile就是LSM樹中的高層實現(xiàn)。從邏輯上來講，它是一棵滿的3層B+樹，從上到下的3層索引分別是Root index block、Intermediate index block和Leaf index block，對應到下面的Data block就是HFile的KeyValue結(jié)構(gòu)了。HFile V2索引結(jié)構(gòu)的圖示如下：

我們已經(jīng)知道，HFile過多會影響讀寫性能，因此高層LSM樹的合并即對應HFile的合并（Compaction）操作。合并操作又分別Minor和Major Compaction，由于Major Compaction涉及整個Region，對磁盤壓力很大，因此要盡量避免。

HBase為了提升LSM結(jié)構(gòu)下的隨機讀性能，還引入了布隆過濾器（建表語句中可以指定），對應HFile中的Bloom index block，其結(jié)構(gòu)圖如下所示。

通過布隆過濾器，HBase就能以少量的空間代價，換來在讀取數(shù)據(jù)時非常快速地確定是否存在某條數(shù)據(jù)，效率進一步提升。