日誌結構合併樹

01-26

這篇文章主要介紹我自己實現的日誌結構合併樹，它在Mushroom這個項目里，主要涉及實現過程中遇到的問題及解決方法，並且會分享一些關於日誌結構合併樹的思考，還會穿插一些LevelDB的介紹。

日誌結構合併樹（Log-Structured Merge Tree）被人們熟知應該是因為谷歌的高性能存儲引擎——LevelDB。

LSM Tree是為了優化資料庫寫性能而出現的，相較於傳統的B+樹，它減少了磁碟隨機讀取的需求，從而在一定程度上改善了資料庫的寫能力，當然在一定程度上犧牲了資料庫的讀能力。

不久之前一直覺得LSM Tree是有著神秘感的索引樹，後來閱讀了LSM Tree論文，覺得與其說LSM Tree是一種樹，不如說它是通過傳統索引組織有序文件或內存塊的一種方式。以兩部件LSM Tree為例，它要求一棵樹始終位於內存（小樹），另一棵樹位於磁碟（大樹），小樹可以是紅黑樹、跳躍表（參考LevelDB），甚至可以是B樹，而大樹則通常是B樹或其變種，所以LSM Tree中的索引是可以選擇的。

傳統的B+樹的缺陷就是在訪問節點時涉及到了大量的磁碟隨機讀寫，因為你無法保證節點常駐內存，尤其是當B+樹管理的索引量很大的時候。這導致資料庫讀寫性能急劇下降（對於這個現象深有體會，所以在寫Mushroom時候我把整棵索引樹都放在了內存）。

LSM樹採取的做法就是通過引入多部件索引來減少磁碟隨機讀寫的需求，如何減少呢？在大量插入情況下我們周期性地選取兩部分索引進行合併，並且把合併後的有序文件（或內存塊）添加到磁碟尾部（或成為新文件），修改節點信息以保證索引樹的正確和完整，並且周期性地回收失效索引。

為什麼減少了磁碟的隨機讀寫？因為合併時索引單向遍歷的方式增加了磁碟的順序讀寫，合併後的索引也是以順序的方式添加到磁碟尾部。

理論比較簡單，不過理論和實踐完全是兩碼事。當然如果把性能和並發考慮在內的話那就完全是另一個世界了。

因為之前實現了並發B link樹，所以就比較自然地就選擇了B link樹作為內存和磁碟索引。所以在Mushroom里LSM樹應該被叫做LSM B link樹。同時我也懶得採取「先實現單線程LSM樹，再擴展為多線程」這種方式，所以LSM B link樹的設計一開始就是在多線程背景下的。

接下來面臨的一個很大的問題就是如何設計合併策略了。一個很自然的想法就是我們希望進行合併的兩部分索引鍵值分布儘可能緊湊，這樣涉及到的磁碟頁面是在一個小的區間，可以避免大量磁碟的讀寫。我一開始設想的是拿B link樹的一部分用來合併，但這引發了一系列的問題。

如何在合併時保證樹結構的正確性？
如何保證合併索引的區間選取既不太大又不太小？
當某個線程檢測到達閾值開始合併後如何處理仍然在對樹進行操作的其它線程？

這些問題困擾了我很久。B link樹每層節點都有附加指針，所以即使在單線程下也很難解決問題1，所以後來採取了和LevelDB相同的做法，內存索引到達閾值後整個壓縮成sstable。這樣就比較容易地解決了1和2，同時通過等待樹上的線程結束和阻擋後續線程來保證壓縮時只有一個線程可以接觸到這棵樹，這也間接保證了性能不受影響。

Mushroom的磁碟索引和LevelDB是一樣的，以sstable（Sorted String Table）文件為節點，每個sstable節點由多個block組成。block在LevelDB里是文件壓縮的基本單位。為了簡便起見，我暫時沒有對block進行壓縮處理。

磁碟部分的索引合併相對來說會簡單一些，某一層到達閾值後合併，具體來說從這一層挑選一個文件和下一層有重疊鍵值的文件進行合併。所以整個合併策略和LevelDB是一致的。

合併策略介紹完畢。但是內存索引和磁碟索引合併這個臨界區會引起一個比較大的問題，那就是Level0（內存索引或者說直接轉換為sstable的磁碟索引）和Level1（磁碟索引）會出現鍵值的大量重疊，所以每次合併代價都是很昂貴的，這個問題似乎無解啊。

最後，LSM樹還有個優勢在於它減少了數據存儲空間的需求。

雖然程序只有3000行，但是優化那簡直是三天三夜都說不完，挑幾個比較有意思的說說。

Mushroom里組成內存索引和磁碟索引的基本單位分別是page和block，它們大量存在於程序中，那優化就是要儘可能地保證降低new和delete，所以分別引入page_manager和block_manager，凡是需要大量new和delete的都訂製一個管理器。其實page_manager還有有個有意思的地方是它使得前面講到的ptr域需要的位元組數從8降到了4，這是個非常關鍵的優化。

引入了圖形學渲染中的雙buffer策略，程序中可以同時存在兩棵B link內存樹，分別是mem_tree_和imm_tree_，mem_tree_賦值給imm_tree_然後轉換為sstable，這樣只需要將imm_tree_重置就又能轉變成mem_tree_，也避免了大量的new和delete。另外這裡需要額外的加鎖機制保證Get和Put能不受影響地執行。LevelDB中MemTable在引用計數為0後會釋放內存索引，所以MemTable中Arena這個結構里的block會被釋放掉。

除此以外還有一些可以實現的優化：

針對LSM樹的優化那就是結合測試數據調參數，獲取合適的部件數量和每個部件的大小，各部件之間的大小關係等等
對sstable中的block進行壓縮
最近發現B link樹還可以優化，使每個節點的利用率從1/2增加到2/3

顯然1是必須的。2、3沒什麼意思，而且3雖然提高了內存利用率但是會降低性能。

寫著寫著發現沒什麼挑戰性了，所以偷懶了沒做很多優化，感覺還是結合實踐理解LSM樹的思想比較重要，尤其是合併策略這個點比較關鍵，而且借這個機會對LevelDB的理解更加深刻了。

下一步的計劃是將Mushroom擴展為分散式索引。

代碼在Github上：UncP/Mushroom。我寫好了測試數據生成腳本和測試腳本

./run_mushroom.sh 1000000

這樣就可以跑1百萬索引測試（這個數據可以修改，1到1千萬都可以）。有問題歡迎開issue，趕緊去star！

PS:

是不是一直對LevelDB中「level 0的鍵值會重疊、而其它層不會」感到很疑惑，我的猜測是為了避免合併時鍵值太過稀疏，從而提高了性能。