LSM(Log Structured Merge Trees ) 筆記-有解無憂

一、大幅度制約存盤介質吞吐量的原因
二、傳統資料庫的實作機制
三、LSM Tree的歷史由來
四、提高寫吞吐量的思路
- 4.1 一種方式是資料來后，直接順序落盤
- 4.2 另一種方式，是保證落盤的資料是順序寫入的同時，還保證這些資料是有序的
五、 LSM Tree結構圖
- 5.1 寫入時，為什么要先寫一份log
- 5.2 什么是MemTable
- 5.3 什么是ImmutableMemTable
- 5.4 什么是SSTable
- 5.5 如何進行資料讀取
- 5.6 如何進行資料的洗掉和更新
- 5.7 SSTable的合并
- 5.8 最近讀取的SSTable IndexBlock快取
六、參考文獻

一、大幅度制約存盤介質吞吐量的原因

首先拋出結論，無論任何存盤介質（不管是機械硬碟還是SSD，抑或是記憶體）的順序訪問速度都遠遠高出隨機訪問的速度，
file

二、傳統資料庫的實作機制

傳統資料庫，比如Mysql使用的b+樹索引，對讀友好，但容易造成隨機寫，比如新插入一個值到資料庫，首先我們要讀取b+樹，判斷新插入的值放在樹的什么位置，其次在特定的位置寫入新值，并做一系列調整，分裂，使之滿足b+樹的特性，這不可避免的造成了磁盤的隨機訪問，大資料量的插入速度很慢，當然這也符合歷史發展趨勢，早起的IT行業，資料量和資料增長速度有限，只要擁有良好的查詢性能，即可滿足需求，

但隨著硬體性能的提升，業務形態的變化，現今的互聯網系統，往往面臨著資料的大量、高速產生，如何加快存盤速度，成了關鍵，于是LSM Tree應運而生，

三、LSM Tree的歷史由來

LSM Tree的最早概念，誕生于1996年google的“BigTable”論文，后世多種資料庫產品對LSM Tree的具體實作，都有一些小的差異，采用LSM Tree作為存盤結構的資料庫有，Google的LevelDB, Facebook的RockDB(RockDB來源于LevelDB), Cassandra,HBase等，

四、提高寫吞吐量的思路

既然順序寫比起隨機寫速度更快，那得想辦法將資料順序寫，

4.1 一種方式是資料來后，直接順序落盤

這擁有很高的寫速度，但是當我們想要查尋一個資料的時候，由于存盤下的資料本身是無序的（寫的值本身無法控制順序），無法使用任何演算法進行優化，只能挨個查詢，讀取速度是很慢的，

4.2 另一種方式，是保證落盤的資料是順序寫入的同時，還保證這些資料是有序的

而請求寫入的資料本身是無序且不可預測的，如何保證落盤的資料是有序的呢？這就需要利用記憶體訪問速度比硬碟快的原理，將寫入的請求，先在記憶體中快取起來，按一定的有序結構組織，達到一定量后，再寫入硬碟，從而使得硬碟順序寫入了有序的資料，提高資料的寫入速度同時，方便了后續基于有序資料的查找(有序的資料結構，可以通過二分查找等演算法進行進行快速查詢，具體查找演算法，得看是哪種有序結構)

五、 LSM Tree結構圖

LSM tree即利用了上述第二種方式，具體結構圖如下：
file

5.1 寫入時，為什么要先寫一份log

為了防止寫入的資料，在斷電時丟失，所以先順序寫一份log到硬碟，方便資料恢復，

5.2 什么是MemTable

寫入資料的記憶體快取，MemTable中存盤的是有序的資料，什么才是有序的資料結構？不同的實作可能不相同，LevelDB使用的是SkipList，Hbase使用的是B Tree，

5.3 什么是ImmutableMemTable

MemTable中的資料隨時在增加，當其增加到一定量后，將其變為不可變資料，ImmutableMemTable，新生成一份MemTable用于后續的資料寫入，ImmutableMemTable中的資料，將被寫入到硬碟中的SSTable.

5.4 什么是SSTable

SSTable 全稱Sorted String Table，實際上就是被寫入資料的有序存盤檔案，所以叫sorted.
file

SSTable檔案有DataBlock,IndexBlock,BitSet(不同的實作，有可能沒有)

DataBlock 一個SSTable包含多個資料塊，資料按KeyValue的形式有序組織，
IndexBlock 記錄每個資料塊中最大的那個Key的Offset
BitSet 使用Bloom Filter來將一個Key映射到BitSet中

資料的有序組織、IndexBlock、BitSet，這些資料結構，都是為了提高資料讀取時的速度，那資料是如何進行讀取的呢？

5.5 如何進行資料讀取

讀取的大概流程如下
file
由于SSTable是順序創建，所以最新的SSTable中包含了最新的值，再查找SSTable時，依次查找最新的SSTable，

每一個SSTable的查詢流程如下
file
布隆運算式的原理是以極小的資料容量，去存盤大量資料存在的可能性，所以如果通過BitSet的布隆運算式查詢該Key存在時，只是一個理論存在可能，接下來要通過IndexBlock真正進行查詢，而如果布隆運算式在BitSet中沒有找到，那就是真的沒有，可以快速跳過，進入下一個SSTable查找，布隆運算式的運用，能夠大大提高查找效率，

5.6 如何進行資料的洗掉和更新

為了保證資料的順序寫，所有SSTable都不會因為洗掉和更新而在原資料所在位置進行更改，在更新時，僅僅插入一個最新的值去寫到新的SSTable中，在洗掉時，依然是插入一個基于該Key的洗掉標記，寫入最新的SSTable中，由于查找某個Key是基于時間新鮮度，反向依次查找SSTable，所以讀取某個Key始終讀的是最新的值，

5.7 SSTable的合并

隨著榷訓月累，SSTable的檔案數會增多，導致查找時性能下降，同時由于資料的更新或洗掉，讓老的SSTable中資料的有效性降低，太多的過期資料占用SSTable，同樣會降低查詢效率，所以一般資料庫引擎，定期都會有一個SSTable的合并操作，移除過時資料，將多個小SSTable合并成大的SSTable，

5.8 最近讀取的SSTable IndexBlock快取

在大記憶體的條件下，部分資料庫還會將最近讀取的SSTable　索引，快取至記憶體，這進一步加速了查找的程序，

六、參考文獻

http://www.benstopford.com/2015/02/14/log-structured-merge-trees/
http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html
https://blog.csdn.net/u014774781/article/details/52105708
https://en.wikipedia.org/wiki/Log-structured_merge-tree
https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

歡迎關注我的個人公眾號"西北偏北UP"，記錄代碼人生，行業思考，科技評論

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

標籤：大數據

上一篇：抖音資料采集Frida進階：脫殼、自動化、高頻問題

下一篇：回顧MySQL基礎