前言：為什么傳統(tǒng)數(shù)據(jù)庫使用B樹較多，而大數(shù)據(jù)存儲(chǔ)使用LSM樹較多？kudu為什么比hbase更適合支持OLAP查詢？

上一篇場景和挑戰(zhàn) 提到數(shù)據(jù)系統(tǒng)最基本的需求就是數(shù)據(jù)存取，多數(shù)情況下數(shù)據(jù)是一條條記錄，每條記錄包含key和value。為了提高存取記錄的效率，我們知道傳統(tǒng)數(shù)據(jù)庫多使用B樹作為索引結(jié)構(gòu)。而在大數(shù)據(jù)場景下，hbase、kudu等存儲(chǔ)引擎為什么選擇LSM樹呢？本文首先介紹什么是LSM樹；然后與B樹簡單對比，分析其優(yōu)勢和缺點(diǎn)；最后再看一下hbase和kudu對LSM的實(shí)現(xiàn)和優(yōu)化以及它們之間的對比。

LSM樹

image.png

上圖引用自BigTable論文，我們直接來看采用LSM樹的存儲(chǔ)引擎讀寫數(shù)據(jù)時(shí)的流程，就能比較直觀的理解LSM樹了。
插入/更新數(shù)據(jù):
　　當(dāng)有記錄要插入時(shí)，按key在memtable中找到相應(yīng)位置，如果已存在此key值，那就直接更新。memtable是內(nèi)存中存數(shù)據(jù)的地方，這些數(shù)據(jù)按key值排序，為了快速查找，會(huì)有紅黑樹之類的數(shù)據(jù)結(jié)構(gòu)作為索引。當(dāng)memtable大小到一定閾值，就把它連同索引一起存到一個(gè)文件，這個(gè)文件就是一個(gè)SSTable。這樣SSTable會(huì)越來越多。后臺(tái)compaction線程會(huì)按一定策略被觸發(fā)，去對SSTable文件進(jìn)行合并。由于數(shù)據(jù)在每個(gè)SSTable中是排好序的，合并的過程就是歸并排序。
　　在把記錄按key排序?qū)懙絤emtable的同時(shí)，會(huì)寫到一個(gè)log文件中。這個(gè)log文件不用排序，它是為了容錯(cuò)，當(dāng)memtable數(shù)據(jù)丟失的時(shí)候可以由此重建。當(dāng)memtable寫入文件后，這個(gè)log文件的內(nèi)容就不再需要了。而新的memtable會(huì)有新的log文件對應(yīng)。
讀數(shù)據(jù)：
　　首先在memtable中查找，沒找到的話，再按時(shí)間順序在SSTable文件中查找。當(dāng)讀數(shù)據(jù)的時(shí)候，如果某個(gè)記錄不存在，需要讀取所有的SSTable才能確定。所以一般每個(gè)SSTable文件生成的時(shí)候會(huì)帶一個(gè)bloom filter，對這一點(diǎn)進(jìn)行優(yōu)化。

LSM VS B樹
　　B樹被廣泛應(yīng)用于各種傳統(tǒng)數(shù)據(jù)庫。采用了B樹的存儲(chǔ)系統(tǒng)，所有數(shù)據(jù)都是排序的，并將這些數(shù)據(jù)分成一個(gè)個(gè)page。而B樹就是指向這些page的索引組成的m階樹。每次讀寫數(shù)據(jù)的過程就是順著B樹查找或更新各個(gè)page的過程。B樹相對于AVL、紅黑樹等的優(yōu)點(diǎn)在于可以減少文件讀寫次數(shù)。
　　對比LSM和B樹之前，我們先來考慮一下它們?yōu)槭裁磿?huì)設(shè)計(jì)成這樣。要設(shè)計(jì)一個(gè)系統(tǒng)，我們可以從最簡單的設(shè)計(jì)出發(fā)。對于存儲(chǔ)系統(tǒng)，最簡單的就是把記錄直接寫到記錄文件的末尾，這樣的做法寫效率是最高的。然而要查詢某一條記錄，需要遍歷整個(gè)文件，這是無法接受的。為了快速查詢，一個(gè)辦法是建立hash索引，但是hash索引有其自己的問題，比如數(shù)據(jù)量大的時(shí)候，索引在內(nèi)存中就放不下了。另一個(gè)辦法就是事先對數(shù)據(jù)進(jìn)行排序。從排好序的文件中查找記錄有一箱的數(shù)據(jù)結(jié)構(gòu)可以用，平衡二叉樹、堆、紅黑樹等等，還有今天的主角B樹（啊，不，B樹只是被來出來陪襯的，今天的主角是LSM）。
　　這里的關(guān)鍵是“事先”是什么時(shí)候。首先會(huì)想到的思路是在寫入的時(shí)候。在計(jì)算機(jī)系統(tǒng)中真正foundmental的創(chuàng)新是很不容易的。大多數(shù)的優(yōu)化其實(shí)都是tradeoff，也就是犧牲一點(diǎn)A，得到一點(diǎn)B。在這里，一共兩種操作，寫入或者讀取，為了提高讀取效率，我們就要在寫入的時(shí)候多做一些事情。對于B樹，這多做的事情首先是找到正確的位置，其次還會(huì)有page的分裂等。
　　大多數(shù)時(shí)候，B樹的表現(xiàn)是很優(yōu)秀的，他也一直很努力的提高自己，不斷增加新技能，進(jìn)化出了B+\B*樹等進(jìn)化體。然而當(dāng)系統(tǒng)同時(shí)服務(wù)的客戶越來越來多，對吞吐量的要求越來越高。B樹表示在大并發(fā)寫操作的時(shí)候，壓力有點(diǎn)大，因?yàn)橐龅氖虑橛悬c(diǎn)多。那怎么辦，為了讀取數(shù)據(jù)的時(shí)候輕松一點(diǎn)，這些事情不得不做啊。
　　當(dāng)B樹不堪重負(fù)的時(shí)候，主角LSM樹登場了。他說，想要有高的寫吞吐，就給我減負(fù)，我可管不了那么多，我可是主角。作者也很無奈，想想也是，哪個(gè)主角沒幾個(gè)掛呢，給他開掛吧。本來都是寫入的時(shí)候要做的事，就少做一點(diǎn)吧，給你幾個(gè)后臺(tái)線程，剩下的事情用它們做吧。有了這幾個(gè)后臺(tái)線程幫忙，LSM樹處理大量寫入的能力一下就上來了。LSM由此直接拿下Hbase、Cassandra、kudu等大量地盤。老大哥B樹表示，他有掛，我很慌。
　　到這里就比較清楚了，B樹把所有的壓力都放到了寫操作的時(shí)候，從根節(jié)點(diǎn)索引到數(shù)據(jù)存儲(chǔ)的位置，可能需要多次讀文件；真正插入的時(shí)候，又可能會(huì)引起page的分裂，多次寫文件。而LSM樹在插入的時(shí)候，直接寫入內(nèi)存，只要利用紅黑樹保持內(nèi)存中的數(shù)據(jù)有序即可，所以可以提供更高的寫吞吐。不過，把compaction交給后臺(tái)線程來做，意味著有時(shí)間差，讀取的時(shí)候，通常不止一個(gè)SSTable，要么逐個(gè)掃描，要么先merge，所以會(huì)影響到讀效率。另外，當(dāng)后臺(tái)線程做compaction的時(shí)候，占用了IO帶寬，這時(shí)也會(huì)影響到寫吞吐。所以B樹還不會(huì)被LSM取代。

Hbase VS kudu
　　Hbase 的存儲(chǔ)實(shí)現(xiàn)是LSM的典型應(yīng)用，適合大規(guī)模在線讀寫。然而，除了這種OLTP的訪問模式，正如我在大數(shù)據(jù)場景與挑戰(zhàn)中提到的，還有一種OLAP的數(shù)據(jù)訪問模式，Hbase其實(shí)是不合適的。對此，最常見的做法是定期把數(shù)據(jù)導(dǎo)出到專門針對OLAP場景的存儲(chǔ)系統(tǒng)。這個(gè)做法一點(diǎn)都不優(yōu)雅，因?yàn)橐环萃瑯拥臄?shù)據(jù)同時(shí)存在兩個(gè)不同的地方，而且還會(huì)有一個(gè)不一致的時(shí)間窗口。Kudu就是為了解決這個(gè)問題而誕生的。我最早看到kudu就很有興趣，也很好奇，一個(gè)存儲(chǔ)系統(tǒng)能同時(shí)滿足OLTP和OLAP兩種場景，那是厲害的。不過現(xiàn)在kudu由于運(yùn)維成本等其他問題還沒有被廣泛采用，挺可惜的。
　　扯遠(yuǎn)了，我們來看為了更好的支持OLAP，kudu對LSM做了哪些優(yōu)化。OLAP經(jīng)常會(huì)做列選擇，所有的OLAP存儲(chǔ)引擎都是以列式存儲(chǔ)的。kudu也想到了這一點(diǎn)。kudu的memtable(在kudu中叫MemRowSet)還是同之前一樣，只是SSTable(在kudu中叫DiskRowSet)改成了列式存儲(chǔ)。對于列式存儲(chǔ)，讀取一個(gè)記錄需要分別讀每個(gè)字段，因此kudu精心設(shè)計(jì)了RowSet中的索引(針對并發(fā)訪問等改進(jìn)過的B樹)，加速這個(gè)過程。
　　除了列式存儲(chǔ)，kudu保證一個(gè)key只可能出現(xiàn)在一個(gè)RowSet中，并記錄了每個(gè)RowSet中key的最大值和最小值，加速數(shù)據(jù)的范圍查找。這也意味著，對于數(shù)據(jù)更新，不能再像之前一樣直接插入memtable即可。需要找到對應(yīng)的RowSet去更新，為了保持寫吞吐，kudu并不直接更新RowSet，而是又新建一個(gè)DeltaStore，專門記錄數(shù)據(jù)的更新。所以，后臺(tái)除了RowSet的compaction線程，還要對DeltaStore進(jìn)行merge和apply。從權(quán)衡的角度考慮，kudu其實(shí)是犧牲了一點(diǎn)寫效率，單記錄查詢效率，換取了批量查詢效率。

這樣看來，從B樹到LSM，到kudu對LSM的優(yōu)化，其實(shí)都是針對不同場景不同的訪問需求做出的各種權(quán)衡而已。了解了這些，我們在選擇這些技術(shù)的時(shí)候心里就有底了。另外，權(quán)衡并不是那么容易的事。怎么樣犧牲A去補(bǔ)償B，可能有不同的策略。研究現(xiàn)有系統(tǒng)的一些思想，有助于當(dāng)我們自己面臨問題的時(shí)候，有更多思路。

作者：群演_
鏈接：http://www.itdecent.cn/p/d52edc9f33df
來源：簡書
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。