前言：為什么傳統(tǒng)數(shù)據(jù)庫使用B樹較多，而大數(shù)據(jù)存儲使用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等存儲引擎為什么選擇LSM樹呢？本文首先介紹什么是LSM樹；然后與B樹簡單對比，分析其優(yōu)勢和缺點；最后再看一下hbase和kudu對LSM的實現(xiàn)和優(yōu)化以及它們之間的對比。
LSM樹
上圖引用自BigTable論文，我們直接來看采用LSM樹的存儲引擎讀寫數(shù)據(jù)時的流程，就能比較直觀的理解LSM樹了。
插入/更新數(shù)據(jù):
當有記錄要插入時，按key在memtable中找到相應(yīng)位置，如果已存在此key值，那就直接更新。memtable是內(nèi)存中存數(shù)據(jù)的地方，這些數(shù)據(jù)按key值排序，為了快速查找，會有紅黑樹之類的數(shù)據(jù)結(jié)構(gòu)作為索引。當memtable大小到一定閾值，就把它連同索引一起存到一個文件，這個文件就是一個SSTable。這樣SSTable會越來越多。后臺compaction線程會按一定策略被觸發(fā)，去對SSTable文件進行合并。由于數(shù)據(jù)在每個SSTable中是排好序的，合并的過程就是歸并排序。
在把記錄按key排序?qū)懙絤emtable的同時，會寫到一個log文件中。這個log文件不用排序，它是為了容錯，當memtable數(shù)據(jù)丟失的時候可以由此重建。當memtable寫入文件后，這個log文件的內(nèi)容就不再需要了。而新的memtable會有新的log文件對應(yīng)。
讀數(shù)據(jù)：
首先在memtable中查找，沒找到的話，再按時間順序在SSTable文件中查找。當讀數(shù)據(jù)的時候，如果某個記錄不存在，需要讀取所有的SSTable才能確定。所以一般每個SSTable文件生成的時候會帶一個bloom filter，對這一點進行優(yōu)化。
LSM VS B樹
B樹被廣泛應(yīng)用于各種傳統(tǒng)數(shù)據(jù)庫。采用了B樹的存儲系統(tǒng)，所有數(shù)據(jù)都是排序的，并將這些數(shù)據(jù)分成一個個page。而B樹就是指向這些page的索引組成的m階樹。每次讀寫數(shù)據(jù)的過程就是順著B樹查找或更新各個page的過程。B樹相對于AVL、紅黑樹等的優(yōu)點在于可以減少文件讀寫次數(shù)。
對比LSM和B樹之前，我們先來考慮一下它們?yōu)槭裁磿O(shè)計成這樣。要設(shè)計一個系統(tǒng)，我們可以從最簡單的設(shè)計出發(fā)。對于存儲系統(tǒng)，最簡單的就是把記錄直接寫到記錄文件的末尾，這樣的做法寫效率是最高的。然而要查詢某一條記錄，需要遍歷整個文件，這是無法接受的。為了快速查詢，一個辦法是建立hash索引，但是hash索引有其自己的問題，比如數(shù)據(jù)量大的時候，索引在內(nèi)存中就放不下了。另一個辦法就是事先對數(shù)據(jù)進行排序。從排好序的文件中查找記錄有一箱的數(shù)據(jù)結(jié)構(gòu)可以用，平衡二叉樹、堆、紅黑樹等等，還有今天的主角B樹（啊，不，B樹只是被來出來陪襯的，今天的主角是LSM）。
這里的關(guān)鍵是“事先”是什么時候。首先會想到的思路是在寫入的時候。在計算機系統(tǒng)中真正foundmental的創(chuàng)新是很不容易的。大多數(shù)的優(yōu)化其實都是tradeoff，也就是犧牲一點A，得到一點B。在這里，一共兩種操作，寫入或者讀取，為了提高讀取效率，我們就要在寫入的時候多做一些事情。對于B樹，這多做的事情首先是找到正確的位置，其次還會有page的分裂等。
大多數(shù)時候，B樹的表現(xiàn)是很優(yōu)秀的，他也一直很努力的提高自己，不斷增加新技能，進化出了B+\B*樹等進化體。然而當系統(tǒng)同時服務(wù)的客戶越來越來多，對吞吐量的要求越來越高。B樹表示在大并發(fā)寫操作的時候，壓力有點大，因為要做的事情有點多。那怎么辦，為了讀取數(shù)據(jù)的時候輕松一點，這些事情不得不做啊。
當B樹不堪重負的時候，主角LSM樹登場了。他說，想要有高的寫吞吐，就給我減負，我可管不了那么多，我可是主角。作者也很無奈，想想也是，哪個主角沒幾個掛呢，給他開掛吧。本來都是寫入的時候要做的事，就少做一點吧，給你幾個后臺線程，剩下的事情用它們做吧。有了這幾個后臺線程幫忙，LSM樹處理大量寫入的能力一下就上來了。LSM由此直接拿下Hbase、Cassandra、kudu等大量地盤。老大哥B樹表示，他有掛，我很慌。
到這里就比較清楚了，B樹把所有的壓力都放到了寫操作的時候，從根節(jié)點索引到數(shù)據(jù)存儲的位置，可能需要多次讀文件；真正插入的時候，又可能會引起page的分裂，多次寫文件。而LSM樹在插入的時候，直接寫入內(nèi)存，只要利用紅黑樹保持內(nèi)存中的數(shù)據(jù)有序即可，所以可以提供更高的寫吞吐。不過，把compaction交給后臺線程來做，意味著有時間差，讀取的時候，通常不止一個SSTable，要么逐個掃描，要么先merge，所以會影響到讀效率。另外，當后臺線程做compaction的時候，占用了IO帶寬，這時也會影響到寫吞吐。所以B樹還不會被LSM取代。
Hbase VS kudu
Hbase 的存儲實現(xiàn)是LSM的典型應(yīng)用，適合大規(guī)模在線讀寫。然而，除了這種OLTP的訪問模式，正如我在大數(shù)據(jù)場景與挑戰(zhàn)中提到的，還有一種OLAP的數(shù)據(jù)訪問模式，Hbase其實是不合適的。對此，最常見的做法是定期把數(shù)據(jù)導(dǎo)出到專門針對OLAP場景的存儲系統(tǒng)。這個做法一點都不優(yōu)雅，因為一份同樣的數(shù)據(jù)同時存在兩個不同的地方，而且還會有一個不一致的時間窗口。Kudu就是為了解決這個問題而誕生的。我最早看到kudu就很有興趣，也很好奇，一個存儲系統(tǒng)能同時滿足OLTP和OLAP兩種場景，那是厲害的。不過現(xiàn)在kudu由于運維成本等其他問題還沒有被廣泛采用，挺可惜的。
扯遠了，我們來看為了更好的支持OLAP，kudu對LSM做了哪些優(yōu)化。OLAP經(jīng)常會做列選擇，所有的OLAP存儲引擎都是以列式存儲的。kudu也想到了這一點。kudu的memtable(在kudu中叫MemRowSet)還是同之前一樣，只是SSTable(在kudu中叫DiskRowSet)改成了列式存儲。對于列式存儲，讀取一個記錄需要分別讀每個字段，因此kudu精心設(shè)計了RowSet中的索引(針對并發(fā)訪問等改進過的B樹)，加速這個過程。
除了列式存儲，kudu保證一個key只可能出現(xiàn)在一個RowSet中，并記錄了每個RowSet中key的最大值和最小值，加速數(shù)據(jù)的范圍查找。這也意味著，對于數(shù)據(jù)更新，不能再像之前一樣直接插入memtable即可。需要找到對應(yīng)的RowSet去更新，為了保持寫吞吐，kudu并不直接更新RowSet，而是又新建一個DeltaStore，專門記錄數(shù)據(jù)的更新。所以，后臺除了RowSet的compaction線程，還要對DeltaStore進行merge和apply。從權(quán)衡的角度考慮，kudu其實是犧牲了一點寫效率，單記錄查詢效率，換取了批量查詢效率。
這樣看來，從B樹到LSM，到kudu對LSM的優(yōu)化，其實都是針對不同場景不同的訪問需求做出的各種權(quán)衡而已。了解了這些，我們在選擇這些技術(shù)的時候心里就有底了。另外，權(quán)衡并不是那么容易的事。怎么樣犧牲A去補償B，可能有不同的策略。研究現(xiàn)有系統(tǒng)的一些思想，有助于當我們自己面臨問題的時候，有更多思路。
作者：群演_
鏈接：http://m.itdecent.cn/p/d52edc9f33df
來源：簡書
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
