面試還原

技面第二輪面試題問到了LSM-Tree是如何實作加速隨機寫的，不是存盤研發方向的童鞋們一看這個題可能會一臉懵逼，可能會疑惑什么是LSM-Tree啊，以前只聽過紅黑樹、B+樹，那么，這個資料結構又有什么特點，為什么能它用來對隨機寫進行加速，
LSM-Tree常被用于一些目前流行的key-Valuex型存盤引擎，比如 Bigtable、Cassandra、HBase、RocksDB，它通過將大量的隨機寫轉換為順序寫來達到資料寫性能的提升，但是也帶來了讀取性能的下降，更適合寫多讀少的應用場景，

什么是LSM-Tree

LSM-Tree(Log Structured Merge Tree),它是一種分層、有序、面向磁盤的資料結構，主要利用了磁盤批量的順序寫性能遠勝于隨機寫的特性，對資料的操作均采用追加方式，不進行洗掉和更新，但是該設計在大大提升了寫性能的同時降低了讀性能，
在這里插入圖片描述

舉個例子，我們要插入一條資料到LSM-Tree，那么執行 “put key1 bar”,該操作首先被寫入磁盤的WAL日志中，該操作用于故障恢復，如果出現宕機就可以將記憶體中來不及寫入磁盤的資料進行恢復從而確保了資料寫入的可靠性，然后，將這個資料寫入到記憶體中的MemTable，這個時候并不會去判斷該key值是否已經存在，之后便可以回復用戶寫入成功，記憶體是有限的不可能不斷寫入，所以MemTable固定大小一般是32M，當MemTable寫滿之后，被轉換為Immutable MemTable(只讀MemTable)，然后創建一個空的MemTable繼續寫入資料，為什么使用Immutable MemTable呢？因為這樣可以避免MemTable中的記憶體序列化到磁盤阻塞寫操作，這個時候，有一個后臺執行緒會不停地將Immutable MemTable復制到磁盤中并釋放記憶體，每個Immutable MemTable對應于磁盤中的SSTable,SSTable,全稱是sorted string table，它擁有一種持久化、有序且不可變的鍵值存盤結構，它的key和value都是任意的位元組陣列，它內部包含一系列可配置大小的Block（默認大小一般是64k)，Block的索引存盤在尾部,當SSTable打開時，索引被加載到記憶體，然后根據key在匯入記憶體里面再進行二分查找，找到key對應的offset之后，然后去磁盤把相應的資料塊讀出來，這些SSTable檔案，雖然每個檔案中的key是有序的，但是檔案之間完全完全無序遭成還是無法查找，這里SSTable巧妙地采用了分層合并機制來解決亂序的問題，啥意思？
SSTable被分為很多了層，越往上層檔案越少，越往底層檔案越多，每一層的容量都有一個固定的上限值，一般來說，下一層的容量是上一層的10倍，當某一層寫滿了，就會觸發后臺執行緒往下一層合并，資料被合并到下一層之后，本層的SSTable檔案就可以洗掉掉了，合并程序其實也是個排序程序，除了Level 0以外，每一層內的檔案都是有序的，檔案內的KV也是有序的，這樣就便于查找了，
這個合并步驟叫做Major Compaction,這個階段會真正地清除掉被標記洗掉掉的資料以及多版本資料的合并，從而避免浪費空間，由于SSTable都是有序的，可以直接采用Merge Sort進行高效合并，
所以，利用WAL確保資料寫入的可靠性，只進行資料的追加不更新資料的特性，只要寫入WAL和MemTable便認為資料已經寫入成功，這樣充分利用順序寫入提升了資料寫入性能，同時又利用了分層合并機制提示了資料的查詢性能，

寫入操作

在這里插入圖片描述
寫入操作只需要在WAL檔案中順序寫入當前操作，寫入成功之后將該資料寫入MemTable中即可認為寫入成功，

讀取操作

采用分層查找的方法，首先在記憶體中的MemTable和Immutable MemTable中查找，之后到磁盤的SSTable的每層進行查找，找到后直接回傳，資料是根據這個路徑追加的，因此按照這個路徑就能查找到，這樣的查找方式有可能由于需要多次進行記憶體和檔案的查找才可以找到符合條件的key,但是這個分層結構越是被經常讀寫的熱資料越靠上，對這樣的key查找就很快，

讀取優化

實際使用中，通常可以對讀取操作進行下一步的優化，在記憶體中快取SSTable檔案的key,這樣可以采用布隆過濾器進行加速查找，比如LevelDB中有個manifest檔案，它記錄了SSTable檔案的一些關鍵資訊，比如Level層數，檔案名，最小key值，最大key值等，這個檔案通常不大，完全可以放入記憶體，從而幫助快速定位要查詢的SSTable檔案，

洗掉操作

洗掉資料時并不是立即洗掉，而是記錄下對這個key的操作操作做標記，只有當合并SSTable檔案時才會真正地洗掉，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/306424.html

標籤：java

上一篇：1.序言—為什么建立自己的博客?

下一篇：Java--這張執行緒瓜圖保熟，不進來看看？這瓜要是不熟它就Dead掉了