LSM樹存儲模型

LSM的結構

LSM的基本思想是將修改的數據保存在內存，達到一定數量後在將修改的數據批量寫入磁盤，在寫入的過程中與之前已經存在的數據做合並。同B樹存儲模型一樣，LSM存儲模型也支持增、刪、讀、改以及順序掃描操作。LSM模型利用批量寫入解決了隨機寫入的問題，雖然犧牲了部分讀的性能，但是大大提高了寫的性能。

MemTable

LSM本身由MemTable,Immutable MemTable,SSTable等多個部分組成，其中MemTable在內存，用於記錄最近修改的數據，一般用跳躍表來組織。當MemTable達到一定大小後，將其凍結起來變成Immutable MemTable，然後開辟一個新的MemTable用來記錄新的記錄。而Immutable MemTable則等待轉存到磁盤。

Immutable MemTable

所謂Immutable MemTable，即是隻能讀不能寫的內存表。內存部分已經有了MemTable，為什麼還要使用Immutable MemTable？個人認為其原因是為了不阻塞寫操作。因為轉存的過程中必然要保證內存表的記錄不變，否則如果新插入的記錄夾在兩條已經轉存到磁盤的記錄中間，處理上會很麻煩，轉存期間勢必要鎖住全表，這樣一來就會阻塞寫操作。所以不如將原有的MemTable變成隻讀Immutable MemTable,在開辟一個新的MemTable用於寫入，即簡單，又不影響寫操作。

SSTable

SSTable是本意是指有序的鍵值對集合( a set of sorted key-value pairs )。是一個簡單有用的集合，正如它的名字一樣，它存儲的就是一係列的鍵值對。當文件較大的時候，還可以為其建立一個鍵-值的位置的索引，指明每個鍵在SSTable文件中的偏移距離。這樣可以加速在SSTable中的查詢。(當然這一點是可選的，同時讓我想去了Bitcask模型中hint文件，通過記錄 鍵-值的位置 ,來加速索引構建)

使用MemTable和SSTable這兩個組件，可以構建一個最簡單的LSM存儲模型。這個模型與Bitcask模型相比，不存在啟動時間長的問題，但是這個模型的讀性能非常的差，因為一但在MemTable找不到相應的鍵，則需要在根據SSTable文件生成的時間，從最近到較早在SSTable中尋找，如果都不存在的話，則會遍曆完所有的SSTable文件。
如果SSTable文件個數很多或者沒有建立SSTable的文件內索引的話，讀性能則會大大下降。

除了在對SSTable內部建立索引外，還可以使用Bloom Fileter,提高Key不在SSTable的判定速度。同樣，定期合並舊的SSTable文件，在減少存儲的空間的同時，也能提高讀取的速度。下麵這幅圖很好的描述了在LSM的大部分結構和操作

LevelDB如何優化讀性能

Leveldb是一個輕量級的，快速的以存儲為目的的key-value存儲引擎。其使用的正是LSM存儲模型。我們可以看看LevelDB是如何來優化讀性能的。在LevelDB中，存在一種元信息文件MANIFEST，用於記錄leveldb的元信息，比如DB使用的Comparator名，以及各SSTable文件的管理信息：如Level層數、文件名、最小key和最大key等等。相比而言，元信息文件而SSTable文件的數目成正比，一般來說不會太多，是可以載入內存的，因此Level可以通過查詢元信息，從而判斷哪些文件中存在我們需要的Key對應的記錄，減少SSTable文件讀取次數。此外，LevelDB的合並操作Compaction是分層次進行的，每一層都有多個SSTable文件，每次合並後除了Level0和內存的MemTable，Immutable MemTable中會有重複的鍵值外，LevelN(N>=1)的各層內部的SSTable文件不會再有重複的鍵值。同時，如果在Level N 層讀到了數據，那麼就不需要再往後讀Level N+1,Level N+2等層的數據了.因為Level N層的數據總是比Level N+1等層的數據更“新鮮”。

實現一個簡單的LSM存儲模型

根據上麵講述的原理，實現了一個簡單的LSM模型(https://github.com/Winnerhust/Code-of-Book/blob/master/Large-Scale-Distributed-Storage-System/lsm_tree.py)。這個模型也內存表為一個跳躍表，SSTable就是簡單的有序鍵值對集合，沒有SSTable內部使用索引,沒有使用Bloom過濾器。其實能就是將我之前的Bitcask模型進行了簡單的改造：

• 將原來的哈希表換成了跳躍表；
• 原來讀取記錄完全依賴哈希表，現在如果在跳躍表中沒有的話，就去讀取文件SSTable文件中的數據，根據文件編號從大到小進行，編號越大，表示數據越新；
• 去掉了加載數據的功能(LSM不需要)；

簡單起見，沒有完成對範圍掃描的支持，不過內存表和SSTable都是有序的，因此這個也不是很難。

參考：
詳解SSTable結構和LSMTree索引

---

歡迎光臨我的網站----蝴蝶忽然的博客園----人既無名的專欄。
如果閱讀本文過程中有任何問題，請聯係作者，轉載請注明出處！