LSM樹存儲引擎

2.2.3　LSM樹存儲引擎

LSM樹（Log Structured Merge Tree）的思想非常樸素，就是将對資料的修改增量保持在記憶體中，達到指定的大小限制後将這些修改操作批量寫入磁盤，讀取時需要合并磁盤中的曆史資料和記憶體中最近的修改操作。LSM樹的優勢在于有效地規避了磁盤随機寫入問題，但讀取時可能需要通路較多的磁盤檔案。本節介紹LevelDB中的LSM樹存儲引擎。

1．存儲結構

如圖2-8所示，LevelDB存儲引擎主要包括：記憶體中的MemTable和不可變MemTable（Immutable MemTable，也稱為Frozen MemTable，即當機MemTable）以及磁盤上的幾種主要檔案：目前（Current）檔案、清單（Manifest）檔案、記錄檔（Commit Log，也稱為送出日志）檔案以及SSTable檔案。當應用寫入一條記錄時，LevelDB會首先将修改操作寫入到記錄檔檔案，成功後再将修改操作應用到MemTable，這樣就完成了寫入操作。

當MemTable占用的記憶體達到一個上限值後，需要将記憶體的資料轉儲到外存檔案中。LevelDB會将原先的MemTable當機成為不可變MemTable，并生成一個新的MemTable。新到來的資料被記入新的記錄檔檔案和新生成的MemTable中。顧名思義，不可變 MemTable的内容是不可更改的，隻能讀取不能寫入或者删除。LevelDB背景線程會将不可變MemTable的資料排序後轉儲到磁盤，形成一個新的SSTable檔案，這個操作稱為Compaction。SSTable檔案是記憶體中的資料不斷進行Compaction操作後形成的，且SSTable的所有檔案是一種層級結構，第0層為Level 0，第1層為Level 1，以此類推。

SSTable中的檔案是按照記錄的主鍵排序的，每個檔案有最小的主鍵和最大的主鍵。LevelDB的清單檔案記錄了這些中繼資料，包括屬于哪個層級、檔案名稱、最小主鍵和最大主鍵。目前檔案記錄了目前使用的清單檔案名。在LevelDB的運作過程中，随着Compaction的進行，SSTable檔案會發生變化，新的檔案會産生，老的檔案被廢棄，此時往往會生成新的清單檔案來記載這種變化，而目前檔案則用來指出哪個清單檔案才是目前有效的。

直覺上，LevelDB每次查詢都需要從老到新讀取每個層級的SSTable檔案以及記憶體中的MemTable。LevelDB做了一個優化，由于LevelDB對外隻支援随機讀取單條記錄，查詢時LevelDB首先會去檢視記憶體中的MemTable，如果MemTable包含記錄的主鍵及其對應的值，則傳回記錄即可；如果MemTable沒有讀到該主鍵，則接下來到同樣處于記憶體中的不可變Memtable中去讀取；類似地，如果還是沒有讀到，隻能依次從新到老讀取磁盤中的SSTable檔案。

2．合并

LevelDB寫入操作很簡單，但是讀取操作比較複雜，需要在記憶體以及各個層級檔案中按照從新到老依次查找，代價很高。為了加快讀取速度，LevelDB内部會執行Compaction操作來對已有的記錄進行整理壓縮，進而删除一些不再有效的記錄，減少資料規模和檔案數量。

LevelDB的Compaction操作分為兩種：minor compaction和major compaction。Minor compaction是指當記憶體中的MemTable大小到了一定值時，将記憶體資料轉儲到SSTable檔案中。每個層級下有多個SSTable，當某個層級下的SSTable檔案數目超過一定設定值後，levelDB會從這個層級中選擇SSTable檔案，将其和高一層級的SSTable檔案合并，這就是major compaction。major compaction相當于執行一次多路歸并：按照主鍵順序依次疊代出所有SSTable檔案中的記錄，如果沒有儲存價值，則直接抛棄；否則，将其寫入到新生成的SSTable檔案中。