從B+樹(shù)到LSM樹(shù),及LSM樹(shù)在HBase中的應(yīng)用
點(diǎn)擊上方藍(lán)色字體，選擇“設(shè)為星標(biāo)”
回復(fù)”資源“獲取更多資源
前言
在有代表性的關(guān)系型數(shù)據(jù)庫(kù)如MySQL、SQL Server、Oracle中，數(shù)據(jù)存儲(chǔ)與索引的基本結(jié)構(gòu)就是我們耳熟能詳?shù)腂樹(shù)和B+樹(shù)。而在一些主流的NoSQL數(shù)據(jù)庫(kù)如HBase、Cassandra、LevelDB、RocksDB中，則是使用日志結(jié)構(gòu)合并樹(shù)（Log-structured Merge Tree，LSM Tree）來(lái)組織數(shù)據(jù)。本文先由B+樹(shù)來(lái)引出對(duì)LSM樹(shù)的介紹，然后說(shuō)明HBase中是如何運(yùn)用LSM樹(shù)的。
回顧B+樹(shù)
為什么在RDBMS中我們需要B+樹(shù)（或者廣義地說(shuō)，索引）？一句話：減少尋道時(shí)間。在存儲(chǔ)系統(tǒng)中廣泛使用的HDD是磁性介質(zhì)+機(jī)械旋轉(zhuǎn)的，這就使得其順序訪問(wèn)較快而隨機(jī)訪問(wèn)較慢。使用B+樹(shù)組織數(shù)據(jù)可以較好地利用HDD的這種特點(diǎn)，其本質(zhì)是多路平衡查找樹(shù)。下圖是一棵高度為3的4路B+樹(shù)示例。
與普通B樹(shù)相比，B+樹(shù)的非葉子節(jié)點(diǎn)只有索引，所有數(shù)據(jù)都位于葉子節(jié)點(diǎn)，并且葉子節(jié)點(diǎn)上的數(shù)據(jù)會(huì)形成有序鏈表。B+樹(shù)的主要優(yōu)點(diǎn)如下：結(jié)構(gòu)比較扁平，高度低（一般不超過(guò)4層），隨機(jī)尋道次數(shù)少；
數(shù)據(jù)存儲(chǔ)密度大，且都位于葉子節(jié)點(diǎn)，查詢穩(wěn)定，遍歷方便；
葉子節(jié)點(diǎn)形成有序鏈表，范圍查詢轉(zhuǎn)化為順序讀，效率高。相對(duì)而言B樹(shù)必須通過(guò)中序遍歷才能支持范圍查詢。
如果寫(xiě)入的數(shù)據(jù)比較離散，那么尋找寫(xiě)入位置時(shí)，子節(jié)點(diǎn)有很大可能性不會(huì)在內(nèi)存中，最終會(huì)產(chǎn)生大量的隨機(jī)寫(xiě)，性能下降。下圖來(lái)自TokuDB的PPT，說(shuō)明了這一點(diǎn)。
如果B+樹(shù)已經(jīng)運(yùn)行了很長(zhǎng)時(shí)間，寫(xiě)入了很多數(shù)據(jù)，隨著葉子節(jié)點(diǎn)分裂，其對(duì)應(yīng)的塊會(huì)不再順序存儲(chǔ)，而變得分散。這時(shí)執(zhí)行范圍查詢也會(huì)變成隨機(jī)讀，效率降低了。
可見(jiàn)，B+樹(shù)在多讀少寫(xiě)（相對(duì)而言）的情境下比較有優(yōu)勢(shì)，在多寫(xiě)少讀的情境下就不是很有威力了。當(dāng)然，我們可以用SSD來(lái)獲得成倍提升的讀寫(xiě)速率，但成本同樣高昂，對(duì)海量存儲(chǔ)集群而言不太可行。日志結(jié)構(gòu)合并樹(shù)（LSM Tree）就是作為B+樹(shù)的替代方案產(chǎn)生的。認(rèn)識(shí)LSM樹(shù)LSM樹(shù)由Patrick O'Neil等人在論文《The Log-Structured Merge Tree》中提出，它實(shí)際上不是一棵樹(shù)，而是2個(gè)或者多個(gè)樹(shù)或類似樹(shù)的結(jié)構(gòu)（注意這點(diǎn)）的集合。下圖示出最簡(jiǎn)單的有2個(gè)結(jié)構(gòu)的LSM樹(shù)。
在LSM樹(shù)中，最低一級(jí)也是最小的C0樹(shù)位于內(nèi)存里，而更高級(jí)的C1、C2...樹(shù)都位于磁盤(pán)里。數(shù)據(jù)會(huì)先寫(xiě)入內(nèi)存中的C0樹(shù)，當(dāng)它的大小達(dá)到一定閾值之后，C0樹(shù)中的全部或部分?jǐn)?shù)據(jù)就會(huì)刷入磁盤(pán)中的C1樹(shù)，如下圖所示。
由于內(nèi)存的讀寫(xiě)速率都比外存要快非常多，因此數(shù)據(jù)寫(xiě)入C0樹(shù)的效率很高。并且數(shù)據(jù)從內(nèi)存刷入磁盤(pán)時(shí)是預(yù)排序的，也就是說(shuō)，LSM樹(shù)將原本的隨機(jī)寫(xiě)操作轉(zhuǎn)化成了順序?qū)懖僮鳎瑢?xiě)性能大幅提升。不過(guò)，它的tradeoff就是犧牲了一部分讀性能，因?yàn)樽x取時(shí)需要將內(nèi)存中的數(shù)據(jù)和磁盤(pán)中的數(shù)據(jù)合并?？傮w上來(lái)講這種tradeoff還是值得的，因?yàn)椋?/span>可以先讀取內(nèi)存中C0樹(shù)的緩存數(shù)據(jù)。內(nèi)存的效率很高，并且根據(jù)局部性原理，最近寫(xiě)入的數(shù)據(jù)命中率也高。
寫(xiě)入數(shù)據(jù)未刷到磁盤(pán)時(shí)不會(huì)占用磁盤(pán)的I/O，不會(huì)與讀取競(jìng)爭(zhēng)。讀取操作就能取得更長(zhǎng)的磁盤(pán)時(shí)間，變相地彌補(bǔ)了讀性能差距。
下面以HBase為例來(lái)簡(jiǎn)要講解LSM樹(shù)是如何發(fā)揮其作用的。HBase中的LSM樹(shù)我們已經(jīng)了解了HBase的讀寫(xiě)流程與MemStore的作用。MemStore作為列族級(jí)別的寫(xiě)入和讀取緩存，它就是HBase中LSM樹(shù)的C0層。并且它確實(shí)也沒(méi)有采用樹(shù)形結(jié)構(gòu)來(lái)存儲(chǔ)，而是采用了跳表——一種替代自平衡BST的結(jié)構(gòu)。MemStore Flush的過(guò)程，也就是LSM樹(shù)中C0層刷寫(xiě)到C1層的過(guò)程，而LSM中的日志對(duì)應(yīng)到HBase自然就是HLog了。
為了方便理解，再次祭出之前用過(guò)的HBase讀寫(xiě)流程簡(jiǎn)圖。
HFile就是LSM樹(shù)中的高層實(shí)現(xiàn)。從邏輯上來(lái)講，它是一棵滿的3層B+樹(shù)，從上到下的3層索引分別是Root index block、Intermediate index block和Leaf index block，對(duì)應(yīng)到下面的Data block就是HFile的KeyValue結(jié)構(gòu)了。HFile V2索引結(jié)構(gòu)的圖示如下：
我們已經(jīng)知道，HFile過(guò)多會(huì)影響讀寫(xiě)性能，因此高層LSM樹(shù)的合并即對(duì)應(yīng)HFile的合并（Compaction）操作。合并操作又分別Minor和Major Compaction，由于Major Compaction涉及整個(gè)Region，對(duì)磁盤(pán)壓力很大，因此要盡量避免。
HBase為了提升LSM結(jié)構(gòu)下的隨機(jī)讀性能，還引入了布隆過(guò)濾器（建表語(yǔ)句中可以指定），對(duì)應(yīng)HFile中的Bloom index block，其結(jié)構(gòu)圖如下所示。
通過(guò)布隆過(guò)濾器，HBase就能以少量的空間代價(jià)，換來(lái)在讀取數(shù)據(jù)時(shí)非?？焖俚卮_定是否存在某條數(shù)據(jù)，效率進(jìn)一步提升。歡迎點(diǎn)贊+收藏+轉(zhuǎn)發(fā)朋友圈素質(zhì)三連
文章不錯(cuò)？點(diǎn)個(gè)【在看】吧！??