http://qing.weibo.com/1765738567/693f0847330008ii.html¹

http://qing.weibo.com/1765738567/693f0847330008x6.html²

講到了LSM 樹和COLA樹，LSM已經(jīng)被許多主流NoSQL系統(tǒng)采用,，如BigTable,，Cassandra，而COLA則知道的人不多,。文章分析比較的很清晰,。

以下原文

-----------------------------------------------------------------------------------------------------------------------------------

首先來回答一個問題：為什么在磁盤中要使用b+樹來進(jìn)行文件存儲呢？

原因還是因?yàn)闃涞母叨鹊偷镁壒?，磁盤本身是一個順序讀寫快,，隨機(jī)讀寫慢的系統(tǒng)，那么如果想高效的從磁盤中找到數(shù)據(jù),，勢必需要滿足一個最重要的條件：減少尋道次數(shù),。

我們以平衡樹為例進(jìn)行對比，就會發(fā)現(xiàn)問題所在了：

先上個圖

這是個平衡樹,，可以看到基本上一個元素下只有兩個子葉節(jié)點(diǎn)

抽象的來看,，樹想要達(dá)成有效查找，勢必需要維持如下一種結(jié)構(gòu)：

樹的子葉節(jié)點(diǎn)中,，左子樹一定小于等于當(dāng)前節(jié)點(diǎn),，而當(dāng)前節(jié)點(diǎn)的右子樹則一定大于當(dāng)前節(jié)點(diǎn)。只有這樣,，才能夠維持全局有序,，才能夠進(jìn)行查詢。

這 也就決定了只有取得某一個子葉節(jié)點(diǎn)后,，才能夠根據(jù)這個節(jié)點(diǎn)知道他的子樹的具體的值情況,。這點(diǎn)非常之重要，因?yàn)槎嫫胶鈽?，只有兩個子葉節(jié)點(diǎn),，所以如果想找 到某個數(shù)據(jù)，他必須重復(fù)更多次“拿到一個節(jié)點(diǎn)的兩個子節(jié)點(diǎn),，判斷大小,，再從其中一個子節(jié)點(diǎn)取出他的兩個子節(jié)點(diǎn)，判斷大小,?！边@一過程。

這個過程重復(fù)的次數(shù),，就是樹的高度,。那么既然每個子樹只有兩個節(jié)點(diǎn)，那么N個數(shù)據(jù)的樹的高度也就很容易可以算出了。

平衡二叉樹這種結(jié)構(gòu)的好處是,，沒有空間浪費(fèi),，不會存在空余的空間，但壞處是需要取出多個節(jié)點(diǎn),，且無法預(yù)測下一個節(jié)點(diǎn)的位置,。這種取出的操作，在內(nèi)存內(nèi)進(jìn)行的時候,，速度很快，但如果到磁盤,，那么就意味著大量隨機(jī)尋道,。基本磁盤就被查死了,。

而b樹,，因?yàn)槠錁?gòu)建過程中引入了有序數(shù)組，從而有效的降低了樹的高度,，一次取出一個連續(xù)的數(shù)組,，這個操作在磁盤上比取出與數(shù)組相同數(shù)量的離散數(shù)據(jù)，要便宜的多,。因此磁盤上基本都是b樹結(jié)構(gòu),。

不過，b樹結(jié)構(gòu)也不是完美的,，與二叉樹相比,，他會耗費(fèi)更多的空間。在最惡劣的情況下,，要有幾乎是元數(shù)據(jù)兩倍的格子才能裝得下整個數(shù)據(jù)集（當(dāng)樹的所有節(jié)點(diǎn)都進(jìn)行了分裂后）,。

以上，我們就對二叉樹和b樹進(jìn)行了簡要的分析,，當(dāng)然里面還有非常多的知識我這里沒有提到,，我希望我的這個系列能夠成為讓大家入門的材料，如果感興趣可以知道從哪里著手即可,。如果您通過我的文章發(fā)現(xiàn)對這些原來枯燥的數(shù)據(jù)結(jié)構(gòu)有了興趣,，那么我的目標(biāo)就達(dá)到了: )

在這章中，我們還將對b數(shù)的問題進(jìn)行一下剖析,，然后給出幾個解決的方向

其實(shí)toku DB的網(wǎng)站上有個非常不錯的對b樹問題的說明,，我在這里就再次侵權(quán)一下，將他們的圖作為說明b樹問題的圖譜吧,，因?yàn)檎娴姆浅Ｇ逦?/p>

http:///downloads/mysqluc-2010-fractal-trees.pdf³

B樹在插入的時候,，如果是最后一個node,那么速度非常快，因?yàn)槭琼樞驅(qū)憽?/p>

但如果有更新插入刪除等綜合寫入,，最后因?yàn)樾枰h(huán)利用磁盤塊,，所以會出現(xiàn)較多的隨機(jī)io.大量時間消耗在磁盤尋道時間上。

-----------------------------------------------------------------------------------------------------------------------------------

PS：B+樹就是在B樹基礎(chǔ)上加兩個規(guī)定  1.非葉子結(jié)點(diǎn)只存指針,，葉子結(jié)點(diǎn)存數(shù)據(jù)  2.所有葉子結(jié)點(diǎn)從左到右用雙鏈表串起來

-----------------------------------------------------------------------------------------------------------------------------------

如果是一個運(yùn)行時間很長的b樹,，那么幾乎所有的請求，都是隨機(jī)io,。因?yàn)榇疟P塊本身已經(jīng)不再連續(xù),，很難保證可以順序讀取。

以上就是b樹在磁盤結(jié)構(gòu)中最大的問題了,。

那么如何能夠解決這個問題呢,？

目前主流的思路有以下幾種

1.      放棄部分讀性能，使用更加面向順序?qū)懙臉涞慕Y(jié)構(gòu)來提升寫性能,。

這個類別里面,，從數(shù)據(jù)結(jié)構(gòu)來說，就我所知并比較流行的是兩類,，

一類是COLA（Cache-Oblivious Look ahead Array）（代表應(yīng)用自然是tokuDB）,。

一類是LSM tree(Log-structured merge Tree)或SSTABLE

(代表的數(shù)據(jù)集是cassandra,hbase,bdb java editon,levelDB etc.).

2.      使用ssd，讓尋道成為往事,。

我 們在這個系列里,，主要還是講LSM tree吧，因?yàn)檫@個東西幾乎要一桶漿糊了,。幾乎所有的nosql都在使用,，然后利用這個宣稱自己比mysql的innodb快多少多少倍。,。我對此表示 比較無語,。因?yàn)閚osql本身似乎應(yīng)該是以省去解析和事務(wù)鎖的方式來提升效能。怎么最后卻改了底層數(shù)據(jù)結(jié)構(gòu),，然后宣稱這是nosql比mysql快的原因 呢,？

畢竟Mysql又不是不能掛接LSM tree的引擎。,。,。

好吧，牢騷我不多說,，畢竟還是要感謝nosql運(yùn)動,，讓數(shù)據(jù)庫團(tuán)隊(duì)都重新審視了一下數(shù)據(jù)庫這個產(chǎn)品的本身。

那么下面,，我們就來介紹一下LSM Tree的核心思想吧,。

首先來分析一下為什么b+樹會慢。

那么,，LSM Tree采取了什么樣的方式來優(yōu)化這個問題呢？

簡單來說,，就是放棄磁盤讀性能來換取寫的順序性。

乍一看,，似乎會認(rèn)為讀應(yīng)該是大部分系統(tǒng)最應(yīng)該保證的特性,，所以用讀換寫似乎不是個好買賣。但別急,，聽我分析之,。

1.      內(nèi)存的速度遠(yuǎn)超磁盤，1000倍以上,。而讀取的性能提升,，主要還是依靠內(nèi)存命中率而非磁盤讀的次數(shù)

2.      寫入不占用磁盤的io，讀取就能獲取更長時間的磁盤io使用權(quán),，從而也可以提升讀取效率,。

因此，雖然SSTable降低了了讀的性能,，但如果數(shù)據(jù)的讀取命中率有保障的前提下,，因?yàn)樽x取能夠獲得更多的磁盤io機(jī)會，因此讀取性能基本沒有降低,，甚至還會有提升,。

而寫入的性能則會獲得較大幅度的提升，基本上是5~10倍左右,。

下面來看一下細(xì)節(jié)

其實(shí)從本質(zhì)來說,，k-v存儲要解決的問題就是這么一個：盡可能快得寫入，以及盡可能快的讀取,。

讓我從寫入最快的極端開始說起,，闡述一下k-v存儲的核心之一—樹這個組件吧。

我們假設(shè)要寫入一個1000個節(jié)點(diǎn)的key是隨機(jī)數(shù)的數(shù)據(jù)。

對磁盤來說,，最快的寫入方式一定是順序的將每一次寫入都直接寫入到磁盤中即可,。

但這樣帶來的問題是，我沒辦法查詢,，因?yàn)槊看尾樵円粋€值都需要遍歷整個數(shù)據(jù)才能找到,，這個讀性能就太悲劇了。,。

那么如果我想獲取磁盤讀性能最高,，應(yīng)該怎么做呢？把數(shù)據(jù)全部排序就行了,，b樹就是這樣的結(jié)構(gòu),。

那么，b樹的寫太爛了,，我需要提升寫,，可以放棄部分磁盤讀性能，怎么辦呢,？

簡單,，那就弄很多個小的有序結(jié)構(gòu)，比如每m個數(shù)據(jù),，在內(nèi)存里排序一次,，下面100個數(shù)據(jù)，再排序一次……這樣依次做下去,，我就可以獲得N/m個有序的小的有序結(jié)構(gòu),。

在查詢的時候，因?yàn)椴恢肋@個數(shù)據(jù)到底是在哪里,，所以就從最新的一個小的有序結(jié)構(gòu)里做二分查找,，找得到就返回，找不到就繼續(xù)找下一個小有序結(jié)構(gòu),，一直到找到為止,。

很容易可以看出，這樣的模式,，讀取的時間復(fù)雜度是(N/m)*log2N ,。讀取效率是會下降的。

這就是最本來意義上的LSM tree的思路,。

那么這樣做,，性能還是比較慢的，于是需要再做些事情來提升,，怎么做才好呢,？

于是引入了以下的幾個東西來改進(jìn)它

1.      Bloom filter : 就是個帶隨即概率的bitmap,可以快速的告訴你,，某一個小的有序結(jié)構(gòu)里有沒有指定的那個數(shù)據(jù)的。于是我就可以不用二分查找,，而只需簡單的計算幾次就能知道數(shù)據(jù)是否在某個小集合里啦,。效率得到了提升，但付出的是空間代價,。

2.      小樹合并為大樹： 也就是大家經(jīng)?？吹降腸ompact的過程，因?yàn)樾渌阅苡袉栴},，所以要有個進(jìn)程不斷地將小樹合并到大樹上,，這樣大部分的老數(shù)據(jù)查詢也可以直接使用log2N的方式找到，不需要再進(jìn)行(N/m)*log2n的查詢了,。

這就是LSMTree的核心思路和優(yōu)化方式,。

不過，LSMTree也有個隱含的條件,，就是他實(shí)現(xiàn)數(shù)據(jù)庫的insert語義時性能不會很高,，原因是，insert的含義是： 事務(wù)中,，先查找該插入的數(shù)據(jù),，如果存在，則拋出異常,，如果不存在則寫入,。這個“查找”的過程,，會拖慢整個寫入,。

這樣，我們就又介紹了一種k-v寫入的模型啦,。在下一次,，我們將再去看看另外一種使用了類似思路，但方法完全不同的b樹優(yōu)化方式 COLA樹系,。敬請期待 ~

-------------------------------

COLA樹

-------------------------------

終于來到了COLA樹系,，這套東西目前來看呢，確實(shí)不如LSM火,，不過作為可選方案,，也是個值得了解的嘗試，不過這塊因?yàn)橹挥幸唤MMIT的人搞了個東西出來,，所以其實(shí)真正的方案也語焉不詳?shù)摹?/span>

從性能來說,，tokuDB的寫入性能很高，但更新似乎不是很給力,，查詢較好,，占用較少的內(nèi)存,。

http://www./2009/04/28/detailed-review-of-tokutek-storage-engine/⁴

這里有一些性能上的指標(biāo)和分析性文字。確實(shí)看起來很心動,，不過這東西只適合磁盤結(jié)構(gòu),，到了SSD似乎就掛了。原因不詳,，因?yàn)闆]有實(shí)際的看過他們的代碼,，所以一切都是推測，如果有問題,，請告知我,。

先說原理，上ppt http:///presentations/bender-Scalperf-9-09.pdf⁵,， 簡單來說,，就是一幫MIT的小子們，分析了一下為什么磁盤寫性能這么慢,，讀的性能也這么慢,，然后一拍腦袋，說：“哎呀,，我知道了,，對于兩級的存儲（比如磁 盤對應(yīng)內(nèi)存，或內(nèi)存對于緩存,，有兩個屬性是會對整個查詢和寫入造成影響的,，一個是容量空間小但速度更快的存儲的size，另外一個則是一次傳輸?shù)? block的size.而我們要做的事情,，就是盡可能讓每次的操作傳輸盡可能少的數(shù)據(jù)塊,。

傳輸?shù)脑缴伲敲床樵兊男阅芫驮胶谩?/p>

進(jìn)而,，有人提出了更多種的解決方案,。

B-tree [Bayer, McCreight 72]

cache-oblivious B-tree [Bender, Demaine, Farach-Colton 00]

buffer tree [Arge 95]

buffered-repositorytree[Buchsbaum,Goldwasser,Venkatasubramanian,Westbrook 00]

Bε

 tree[Brodal, Fagerberg 03]

log-structured merge tree [O'Neil, Cheng, Gawlick, O'Neil 96]

string B-tree [Ferragina, Grossi 99]

這些結(jié)構(gòu)都是用于解決這樣一個問題，在磁盤上能夠創(chuàng)建動態(tài)的有序查詢結(jié)構(gòu),。

在 今天,，主要想介紹的就是COLA，所謂cache-oblivious 就是說,，他不需要知道具體的內(nèi)存大小和一個塊的大小,，或者說，無論內(nèi)存多大,，塊有多大,，都可以使用同一套邏輯進(jìn)行處理，這無疑是具有優(yōu)勢的,，因?yàn)閮?nèi)存大小 雖然可以知道,，但內(nèi)存是隨時可能被臨時的占用去做其他事情的,，這時候，CO就非常有用了,。

其他我就不多說了,，看一下細(xì)節(jié)吧~再說這個我自己都快繞進(jìn)去了。

眾所周知的,，磁盤需要的是順序?qū)懭?，下一個問題就是，怎么能夠保證數(shù)據(jù)的順序?qū)憽?/p>

我們假定有這樣一個空的數(shù)據(jù)集合

可以認(rèn)為樹的高度是log2N,。

每行要么就是空的,，要么就是滿的，每行數(shù)據(jù)都是排序后的數(shù)據(jù),。

如果再寫一個值的時候,，會寫在第一行，比如寫了3,。

再寫一個值11的時候,，因?yàn)榈谝恍幸呀?jīng)寫滿了，所以將3取出來,，和11做排序,，嘗試寫第二行。又因?yàn)榈诙幸矟M了,，所以將第二行的5和10也取出,，對3,11,5,10 進(jìn)行排序。寫入第四行

這就是COLA的寫入過程,。

可以很清楚的看出,，COLA的核心其實(shí)和LSM類似，每次“將數(shù)據(jù)從上一層取出,，與外部數(shù)據(jù)進(jìn)行歸并排序后寫入新的array”的這個操作,，對sas磁盤非常友好,。因此,，寫入性能就會有非常大的提升。

并且因?yàn)閿?shù)據(jù)結(jié)構(gòu)簡單,，沒有維持太多額外的指針,，所以相對的比較節(jié)省空間。

但這樣查詢會需要針對每個array都進(jìn)行一次二分查找,。

性能似乎還不是很高,，所以，他們想到了下面這種方式,，把它的命名為fractal tree,分形樹,。

用更簡單的方法來說的話呢,，就是在merge的時候，上層持有下層數(shù)據(jù)的一個額外的指針,。

來協(xié)助進(jìn)行二分查找,。

這樣，利用空間換時間,，他的查詢速度就又回到了log2N這個級別了,。

到此，又一個有序結(jié)構(gòu)被我囫圇吞棗了,。