作為一名應(yīng)用系統(tǒng)開發(fā)人員，為什么要關(guān)注數(shù)據(jù)內(nèi)部的存儲(chǔ)和檢索呢?首先，你不太可能從頭開始實(shí)現(xiàn)一套自己的存儲(chǔ)引擎，往往需要從眾多現(xiàn)有的存儲(chǔ)引擎中選擇一個(gè)適合自己應(yīng)用的存儲(chǔ)引擎。因此，為了針對你特定的工作負(fù)載而對數(shù)據(jù)庫調(diào)優(yōu)時(shí)，最好對存儲(chǔ)引擎的底層機(jī)制有一個(gè)大概的了解。

[[283718]]

今天我們就先來了解下關(guān)系型數(shù)據(jù)庫MySQL和NoSQL存儲(chǔ)引擎HBase的底層存儲(chǔ)機(jī)制。對于一個(gè)數(shù)據(jù)庫的性能來說，其數(shù)據(jù)的組織方式至關(guān)重要。眾所周知，數(shù)據(jù)庫的數(shù)據(jù)大多存儲(chǔ)在磁盤上，而磁盤的訪問相對內(nèi)存的訪問來說是一項(xiàng)很耗時(shí)的操作，對比如下。因此，提高數(shù)據(jù)庫數(shù)據(jù)的查找速度的關(guān)鍵點(diǎn)之一便是盡量減少磁盤的訪問次數(shù)。

磁盤與內(nèi)存的訪問速度對比

為了加速數(shù)據(jù)庫數(shù)據(jù)的訪問，大多傳統(tǒng)的關(guān)系型數(shù)據(jù)庫都會(huì)使用特殊的數(shù)據(jù)結(jié)構(gòu)來幫助查找數(shù)據(jù)，這種數(shù)據(jù)結(jié)構(gòu)叫作索引( Index)。對于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫，考慮到經(jīng)常需要范圍查找某一批數(shù)據(jù)，因此其索引一般不使用 Hash算法，而使用樹( Tree)結(jié)構(gòu)。然而，樹結(jié)構(gòu)的種類很多，卻不一定都適合用于做數(shù)據(jù)庫索引。

二叉查找樹與平衡二叉樹

最常見的樹結(jié)構(gòu)是二叉查找樹( Binary Search Tree)，它就是一棵二叉有序樹：保證左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值，而右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。其優(yōu)點(diǎn)在于實(shí)現(xiàn)簡單，并且樹在平衡的狀態(tài)下查找效率能達(dá)到 O(log n);缺點(diǎn)是在極端非平衡情況下查找效率會(huì)退化到 O(n)，因此很難保證索引的效率。

二叉查找樹的查找效率

針對上述二叉查找樹的缺點(diǎn)，人們很自然就想到是否能用平衡二叉樹( Balanced Binary Tree)來解決這個(gè)問題。但是平衡二叉樹依然有個(gè)比較大的問題：它的樹高為 log n——對于索引樹來說，樹的高度越高，意味著查找所要花費(fèi)的訪問次數(shù)越多，查詢效率越低。

況且，主存從磁盤讀數(shù)據(jù)一般以頁為單位，因此每次訪問磁盤都會(huì)讀取多個(gè)扇區(qū)的數(shù)據(jù)(比如 4KB大小的數(shù)據(jù))，遠(yuǎn)大于單個(gè)二叉樹節(jié)點(diǎn)的值(字節(jié)級(jí)別)，這也是造成二叉樹相對索引樹效率低下的原因。正因如此，人們就想到了通過增加每個(gè)樹節(jié)點(diǎn)的度來提高訪問效率，而 B+樹(B+-tree)便受到了更多的關(guān)注。

B+樹

在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫里， B+樹( B+-tree)及其衍生樹是被用得比較多的索引樹。

B+樹

B+樹的主要特點(diǎn)如下。每個(gè)樹節(jié)點(diǎn)只存放鍵值，不存放數(shù)值，而由葉子節(jié)點(diǎn)存放數(shù)值。這樣會(huì)使樹節(jié)點(diǎn)的度比較大，而樹的高度就比較低，從而有利于提高查詢效率。葉子節(jié)點(diǎn)存放數(shù)值，并按照值大小順序排序，且?guī)е赶蛳噜徆?jié)點(diǎn)的指針，以便高效地進(jìn)行區(qū)間數(shù)據(jù)查詢;并且所有葉子節(jié)點(diǎn)與根節(jié)點(diǎn)的距離相同，因此任何查詢的效率都很相似。與二叉樹不同， B+樹的數(shù)據(jù)更新操作不從根節(jié)點(diǎn)開始，而從葉子節(jié)點(diǎn)開始，并且在更新過程中樹能以比較小的代價(jià)實(shí)現(xiàn)自平衡。

正是由于 B+樹的上述優(yōu)點(diǎn)，它成了傳統(tǒng)關(guān)系型數(shù)據(jù)庫的寵兒。當(dāng)然，它也并非無懈可擊，它的主要缺點(diǎn)在于隨著數(shù)據(jù)插入的不斷發(fā)生，葉子節(jié)點(diǎn)會(huì)慢慢分裂——這可能會(huì)導(dǎo)致邏輯上原本連續(xù)的數(shù)據(jù)實(shí)際上存放在不同的物理磁盤塊位置上，在做范圍查詢的時(shí)候會(huì)導(dǎo)致較高的磁盤 IO，以致嚴(yán)重影響到性能。

日志結(jié)構(gòu)合并樹

眾所周知，數(shù)據(jù)庫的數(shù)據(jù)大多存儲(chǔ)在磁盤上，而無論是傳統(tǒng)的機(jī)械硬盤( HardDiskDrive, HDD)還是固態(tài)硬盤( Solid State Drive, SSD)，對磁盤數(shù)據(jù)的順序讀寫速度都遠(yuǎn)高于隨機(jī)讀寫。

磁盤順序與隨機(jī)訪問吞吐對比

然而，基于 B+樹的索引結(jié)構(gòu)是違背上述磁盤基本特點(diǎn)的——它會(huì)需要較多的磁盤隨機(jī)讀寫，于是， 1992年，名為日志結(jié)構(gòu)( Log-Structured)的新型索引結(jié)構(gòu)方法便應(yīng)運(yùn)而生。日志結(jié)構(gòu)方法的主要思想是將磁盤看作一個(gè)大的日志，每次都將新的數(shù)據(jù)及其索引結(jié)構(gòu)添加到日志的最末端，以實(shí)現(xiàn)對磁盤的順序操作，從而提高索引性能。不過，日志結(jié)構(gòu)方法也有明顯的缺點(diǎn)，隨機(jī)讀取數(shù)據(jù)時(shí)效率很低。

1996年，一篇名為 Thelog-structured merge-tree(LSM-tree)的論文創(chuàng)造性地提出了日志結(jié)構(gòu)合并樹( Log-Structured Merge-Tree)的概念，該方法既吸收了日志結(jié)構(gòu)方法的優(yōu)點(diǎn)，又通過將數(shù)據(jù)文件預(yù)排序克服了日志結(jié)構(gòu)方法隨機(jī)讀性能較差的問題。盡管當(dāng)時(shí) LSM-tree新穎且優(yōu)勢鮮明，但它真正聲名鵲起卻是在 10年之后的 2006年，那年谷歌的一篇使用了 LSM-tree技術(shù)的論文 Bigtable: A Distributed Storage System for Structured Data橫空出世，在分布式數(shù)據(jù)處理領(lǐng)域掀起了一陣旋風(fēng)，隨后兩個(gè)聲名赫赫的大數(shù)據(jù)開源組件( 2007年的 HBase與 2008年的 Cassandra，目前兩者同為 Apache頂級(jí)項(xiàng)目)直接在其思想基礎(chǔ)上破繭而出，徹底改變了大數(shù)據(jù)基礎(chǔ)組件的格局，同時(shí)也極大地推廣了 LSM-tree技術(shù)。

LSM-tree最大的特點(diǎn)是同時(shí)使用了兩部分類樹的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，并同時(shí)提供查詢。其中一部分?jǐn)?shù)據(jù)結(jié)構(gòu)( C0樹)存在于內(nèi)存緩存(通常叫作 memtable)中，負(fù)責(zé)接受新的數(shù)據(jù)插入更新以及讀請求，并直接在內(nèi)存中對數(shù)據(jù)進(jìn)行排序;另一部分?jǐn)?shù)據(jù)結(jié)構(gòu)( C1樹)存在于硬盤上 (這部分通常叫作 sstable)，它們是由存在于內(nèi)存緩存中的 C0樹沖寫到磁盤而成的，主要負(fù)責(zé)提供讀操作，特點(diǎn)是有序且不可被更改。

LSM-tree的 C0與 C1部分

LSM-tree的另一大特點(diǎn)是除了使用兩部分類樹的數(shù)據(jù)結(jié)構(gòu)外，還會(huì)使用日志文件(通常叫作 commit log)來為數(shù)據(jù)恢復(fù)做保障。這三類數(shù)據(jù)結(jié)構(gòu)的協(xié)作順序一般是：所有的新插入與更新操作都首先被記錄到 commit log中——該操作叫作 WAL(Write Ahead Log)，然后再寫到 memtable，最后當(dāng)達(dá)到一定條件時(shí)數(shù)據(jù)會(huì)從 memtable沖寫到 sstable，并拋棄相關(guān)的 log數(shù)據(jù); memtable與 sstable可同時(shí)供查詢;當(dāng) memtable出問題時(shí)，可從 commit log與 sstable中將 memtable的數(shù)據(jù)恢復(fù)。

我們可以參考 HBase的架構(gòu)來體會(huì)其架構(gòu)中基于 LSM-tree的部分特點(diǎn)。按照 WAL的原則，數(shù)據(jù)首先會(huì)寫到 HBase的 HLog(相當(dāng)于 commit log)里，然后再寫到 MemStore(相當(dāng)于 memtable)里，最后會(huì)沖寫到磁盤 StoreFile(相當(dāng)于 sstable)中。這樣 HBase的 HRegionServer就通過 LSM-tree實(shí)現(xiàn)了數(shù)據(jù)文件的生成。HBase LSM-tree架構(gòu)示意圖如下圖。

HBase LSM-tree架構(gòu)示意圖

LSM-tree的這種結(jié)構(gòu)非常有利于數(shù)據(jù)的快速寫入(理論上可以接近磁盤順序?qū)懰俣?，但是不利于讀——因?yàn)槔碚撋献x的時(shí)候可能需要同時(shí)從 memtable和所有硬盤上的 sstable中查詢數(shù)據(jù)，這樣顯然會(huì)對性能造成較大的影響。為了解決這個(gè)問題， LSM-tree采取了以下主要的相關(guān)措施。

定期將硬盤上小的 sstable合并(通常叫作 Merge或 Compaction操作)成大的 sstable，以減少 sstable的數(shù)量。而且，平時(shí)的數(shù)據(jù)更新刪除操作并不會(huì)更新原有的數(shù)據(jù)文件，只會(huì)將更新刪除操作加到當(dāng)前的數(shù)據(jù)文件末端，只有在 sstable合并的時(shí)候才會(huì)真正將重復(fù)的操作或更新去重、合并。

對每個(gè) sstable使用布隆過濾器( Bloom Filter)，以加速對數(shù)據(jù)在該 sstable的存在性進(jìn)行判定，從而減少數(shù)據(jù)的總查詢時(shí)間。

總結(jié)

LSM樹和B+樹的差異主要在于讀性能和寫性能進(jìn)行權(quán)衡，在犧牲的同時(shí)尋找其余補(bǔ)救方案。

B+樹存儲(chǔ)引擎，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描(B+樹的葉子節(jié)點(diǎn)之間的指針)，對應(yīng)的存儲(chǔ)系統(tǒng)就是關(guān)系數(shù)據(jù)庫。但隨著寫入操作增多，為了維護(hù)B+樹結(jié)構(gòu)，節(jié)點(diǎn)分裂，讀磁盤的隨機(jī)讀寫概率會(huì)變大，性能會(huì)逐漸減弱。LSM樹(Log-Structured MergeTree)存儲(chǔ)引擎和B+樹存儲(chǔ)引擎一樣，同樣支持增、刪、讀、改、順序掃描操作。而且通過批量存儲(chǔ)技術(shù)規(guī)避磁盤隨機(jī)寫入問題。當(dāng)然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。