來源：https://juejin.im/post/5e756a156fb9a07cbf46d7fd
分佈式——吞吐量巨強、Hbase的承載者 LSMT
今天是分佈式系統的第九篇文章。
今天給大家分享的內容是LSM樹，它的英文是Log-structed Merge-tree。看著有些發怵，但其實它的原理不難，和B樹相比簡直算是小兒科了。
並且這也是一個非常經典的數據結構，並且在大數據系統當中有非常廣泛的應用。有許多耳熟能詳的經典系統，底層就是基於LSM樹實現的。因此，今天就和大家一起來深入學習一下它的原理。
背景知識
首先，我們先從背景知識開始。我們之前介紹B+樹的時候說過，B+樹和B樹最大的不同就是將所有的數據都放在了葉子節點。從而優化了我們批量插入以及批量查詢的效率，而優化的核心邏輯就是因為無論是什麼存儲介質，順序存儲的效率一定要比隨機存儲更高，並且高的還不是一點半點。這個已經算是老生常談了，如果我沒記錯的話，這已經是我第三次在文章當中提到這一點了。
我最近看到了一張圖，很好地闡述了隨機讀取和順序讀取兩者的效率差，我們來看下面這張圖。其中綠色的部分表示硬盤順序讀取的最大速度，而紅色表示隨機讀取時的速度。
我們看下縱座標就知道，這兩者差的不是一點半點，已經有數量級的差距了。而且還不止是一個數量級，至少相差了三個數量級，顯然這是非常恐怖的。另外，這個差距並不只是在傳統的機械硬盤上存在，即使是現在比較先進的SSD固態硬盤上，也一樣存在。也就是說這個差距是介質無關的。
直觀優化
既然隨機讀取和順序讀取的效率差了這麼多，不由得不讓人心動。如果能夠發明一個數據結構可以充分地利用上這一點，那麼我們的系統對數據的吞吐能力一定可以再上一個臺階。對於許多科技公司而言，尤其是大數據公司，因為數據量帶來的機器開銷的費用佔據了日常支出的大頭。如果能夠很好地解決這個問題，顯然可以節約大量的資源。
一個樸素的想法就是將所有的讀寫都設計成順序讀寫，比如日誌系統就是一個典型的例子。在我們記錄日誌的時候，總是添加在文件的末尾，而不會插入在文件的中間。由於我們總是添加在文件末尾，在磁盤上這是一個順序的讀寫。但我們把讀寫都設計成順序的，也就意味著我們當我們要查找的內容在文件中間的時候，我們
必須要讀入文件中的所有內容。這個思路應用最廣泛的地方有兩個，一個是數據庫的日誌當中。在我們用數據庫執行寫入或者修改操作的時候，數據庫會將所有的變更寫成log記錄下來。還有一處是消息系統的中間件，比如kafka。
但是在複雜的增刪查改的場景當中，尤其是涉及到批量讀寫的場景，簡單的文件順序讀寫就不能滿足需求了。當然我們可以引入哈希表或者是B+樹這些數據結構實現功能，但這些複雜的數據結構都避免不了比較慢的隨機讀寫操作，而我們希望隨機讀寫能儘量減少，正是基於這個原理，LSMT被髮明瞭出來。LSMT使用了一種獨特的機制犧牲了一些讀操作的性能，保證了寫操作的能力，它能夠讓所有的操作順序化，幾乎完全避免了隨機讀寫。
在我們介紹LSMT的原理之前，我們先來介紹一下它的子結構SSTable。
SSTable
第一次看到這個單詞的時候覺得一頭霧水是正常的，SSTable的全稱是
Sorted String Table，本質就是一個KV結構順序排列的文件。我們來看下下圖： 最基礎的SSTable就是上圖當中右側的部分，即key和value的鍵值對按照key值的大小排序，並存儲在文件當中。當我們需要查找某個key值對應的數據的時候，我們會將整個文件讀入進內存，進行查找。同樣，寫入也是如此，我們會將插入的操作在內存中進行，得到結果之後，直接覆蓋原本的文件，而不會在文件當中修改，因為這會牽扯到移動大量的數據。
如果文件中的數據量過大，我們需要另外建立一個索引文件，存儲不同的key值對應的offset，方便我們在讀取文件的時候快速查找到我們想要查找的文件。索引文件即上圖當中左邊部分。
需要注意，SSTable是不可修改的，我們只會用新的SSTable去覆蓋舊的，而不會再原本的基礎上修改。因為修改會涉及隨機讀寫，這是我們不希望的。
LSM的增刪改查
理解了SSTable之後，我們來看下基本的LSM實現原理。
其實最基本的LSM原理非常簡單，本質上就是在SSTable的基礎上增加了一個Memtable，Memtable顧名思義就是
存放在內存當中的表結構。當然也不一定是表結構，也可以是樹結構，這並不影響，總之是一個可以快速增刪改查的數據結構，比如紅黑樹、SkipList都行。其次我們還需要一個log文件，和數據庫當中的log一樣，記錄數據發生的變化。方便系統故障或者是數據丟失的時候進行找回，所以整體的架構如下：
查找
我們先來看查找的情況，當我們需要查找一個元素的時候，我們
會先查找Memtable。原因也很好理解，它就在內存當中，不需要額外讀取文件，如果Memtable當中沒有找到，我們再一個一個查找SSTable，由於SSTable當中的數據也是順序存儲的，所以我們可以使用二分查找，整個查找的速度也會非常快。但是有一點，由於SSTable的數量可能會很多，而且我們必須要順序查找，所以當SSTable數量很大的時候，也會影響查找的速度。為了解決這個問題，我們可以引入布隆過濾器進行優化。我們對每一個SSTable建立一個布隆過濾器，可以快速地判斷元素是否在某一個SSTable當中。布隆過濾器判斷元素不存在是一定準確的，而判斷存在可能會有一個很小的幾率失誤，但這個失誤率是可以控制的，我們可以設置合理的參數，使得失誤率足夠低。加上了布隆過濾器之後的查找操作是這樣的：
上圖的星星表示布隆過濾器，也就是說我們先通過布隆過濾器判斷元素是否存在之後，再進行查找。
布隆過濾器在之前的文章當中曾經和大家介紹過，有遺忘或者是新關注的同學可以點擊下方鏈接回顧一下。
大數據算法——布隆過濾器
增刪改
除了查找之外的其他操作都發生在Memtable當中，比如當我們要增加一個元素的時候，我們直接增加在Memtable，而不是寫入文件。這也保證了增加的速度可以做到非常快。
除此之外，修改和刪除也一樣，如果需要修改的元素剛好在Memtable當中，沒什麼好說的我們直接進行修改。那如果不在Memtable當中，如果我們要先查找到再去修改免不了需要進行磁盤讀寫，這會消耗大量資源。所以我們還是在Memtable當中進行操作，我們會插入這個元素，標記成修改或者是刪除。
所以我們可以把增刪改這三個操作都看成是添加，但是這就帶來了一個問題，這麼操作會導致很快Memtable當中就積累了大量數據，而我們的內存資源也是有限的，顯然不能無限拓張。為了解決這個問題，我們需要定期將Memtable當中的內容存儲到磁盤，存儲成一個SSTable。這也是SSTable的來源，SSTable當中的數據不是憑空出現的，而是LSM落盤產生的。
同樣，由於我們不斷地落盤同樣也會導致SSTable的數量增加，前面我們也已經分析過了，SSTable的數量增加會影響我們查找的效率，所以我們不能放任它無限增加。再加上我們還存儲了許多修改和刪除的信息，我們需要把這些信息落實。為了達成這點，我們需要定期將所有的SSTable合併，在合併的過程當中我們完成數據的刪除以及修改工作。換句話說，之前的刪除、修改操作只是被記錄了下來，直到合併的時候才真正執行。
整個歸併的過程並不難，類似於歸併排序當中的歸併操作，只是我們需要加上狀態的判斷。
總結
我們回顧一下LSMT的整個過程，雖然說是樹，但其實樹形結構並不明顯。但如果我們觀察一下查找元素時候的查詢順序，其實是從Memtable，然後沿著SSTable順序往下的 ，這點和樹形結構是一致的，可以看成一個比較”窄“的樹。如果還是覺得這個數據結構長得不那麼像一棵樹是正常的，我們不用糾結。另外，從原理上來看，簡直有些簡單粗暴地過頭，但是從實際結果來看，它的效果卻非常好，在Hbase、kudu當中有著廣泛應用。
我們對比一下它和B+樹，在B+樹當中，我們為了能夠快速讀取而使用了多路平衡樹，這樣可以迅速找到對應key的節點。我們只需要讀入節點當中的內容即可，但也正因為平衡樹的結構，導致了我們在寫入數據的時候會引起樹結構的變動，也就涉及到多次文件的隨機讀寫。當我們數據的吞吐量很大的時候，會帶來巨大的開銷。而LSMT則不然，我們讀取的時候效率比B+樹要低，但是對於大數據的寫入支持得更好。在大數據場景當中，許多對於數據的吞吐量有著很高的要求，比如消息系統、分佈式存儲等。這個時候B+樹就有些無能為力了，但是同樣，如果我們需要保證查找的效率，那LSMT也不太合適，因此兩者其實並沒有誰比誰更優，而是針對的場景不同。
閱讀更多 月漫灣 的文章
