庖丁解LevelDB之整體感知
LevelDB是Google傳奇工程師Jeff Dean和Sanjay Ghemawat開源的KV存儲引擎，無論從設計還是代碼上都可以用精致優雅來形容，非常值得細細品味。本文將從設計思路、整體結構、讀寫流程、壓縮流程幾個方面來進行介紹，從而能夠對LevelDB有一個整體的感知。
設計思路
LevelDB的數據是存儲在磁盤上的，采用LSM-Tree的結構實現。LSM-Tree將磁盤的隨機寫轉化為順序寫，從而大大提高了寫速度。為了做到這一點LSM-Tree的思路是將索引樹結構拆成一大一小兩顆樹，較小的一個常駐內存，較大的一個持久化到磁盤，他們共同維護一個有序的key空間。寫入操作會首先操作內存中的樹，隨著內存中樹的不斷變大，會觸發與磁盤中樹的歸并操作，而歸并操作本身僅有順序寫。如下圖所示：
LSM示意
隨著數據的不斷寫入，磁盤中的樹會不斷膨脹，為了避免每次參與歸并操作的數據量過大，以及優化讀操作的考慮，LevelDB將磁盤中的數據又拆分成多層，每一層的數據達到一定容量后會觸發向下一層的歸并操作，每一層的數據量比其上一層成倍增長。這也就是LevelDB的名稱來源。
整體結構
具體到代碼實現上，LevelDB有幾個重要的角色，包括對應于上文提到的內存數據的Memtable，分層數據存儲的SST文件，版本控制的Manifest、Current文件，以及寫Memtable前的WAL。這里簡單介紹各個組件的作用和在整個結構中的位置。
- Memtable：內存數據結構，跳表實現，新的數據會首先寫入這里；
- Log文件：寫Memtable前會先寫Log文件，Log通過append的方式順序寫入。Log的存在使得機器宕機導致的內存數據丟失得以恢復；
- Immutable Memtable：達到Memtable設置的容量上限后，Memtable會變為Immutable為之后向SST文件的歸并做準備，顧名思義，Immutable Mumtable不再接受用戶寫入，同時會有新的Memtable生成；
- SST文件：磁盤數據存儲文件。分為Level 0到Level N多層，每一層包含多個SST文件；單個SST文件容量隨層次增加成倍增長；文件內數據有序；其中Level0的SST文件由Immutable直接Dump產生，其他Level的SST文件由其上一層的文件和本層文件歸并產生；SST文件在歸并過程中順序寫生成，生成后僅可能在之后的歸并中被刪除，而不會有任何的修改操作。
- Manifest文件： Manifest文件中記錄SST文件在不同Level的分布，單個SST文件的***最小key，以及其他一些LevelDB需要的元信息。
- Current文件: 從上面的介紹可以看出，LevelDB啟動時的首要任務就是找到當前的Manifest，而Manifest可能有多個。Current文件簡單的記錄了當前Manifest的文件名，從而讓這個過程變得非常簡單。
LevelDB 結構
讀寫操作
作為KV數據存儲引擎，基本的讀寫操作是必不可少的，通過對讀寫操作流程的了解，也能讓我們更直觀的窺探其內部實現。
1，寫流程
LevelDB的寫操作包括設置key-value和刪除key兩種。需要指出的是這兩種情況在LevelDB的處理上是一致的，刪除操作其實是向LevelDB插入一條標識為刪除的數據。下面就一起看看LevelDB插入值的過程。
LevelDB對外暴露的寫接口包括Put，Delete和Write，其中Write需要WriteBatch作為參數，而Put和Delete首先就是將當前的操作封裝到一個WriteBatch對象，并調用Write接口。這里的WriteBatch是一批寫操作的集合，其存在的意義在于提高寫入效率，并提供Batch內所有寫入的原子性。
在Write函數中會首先用當前的WriteBatch封裝一個Writer，代表一個完整的寫入請求。LevelDB加鎖保證同一時刻只能有一個Writer工作。其他Writer掛起等待，直到前一個Writer執行完畢后喚醒。單個Writer執行過程如下：
- Status status = MakeRoomForWrite(my_batch == NULL);
- uint64_t last_sequence = versions_->LastSequence();
- Writer* last_writer = &w;
- if (status.ok() && my_batch != NULL) {
- WriteBatch* updates = BuildBatchGroup(&last_writer);
- WriteBatchInternal::SetSequence(updates, last_sequence + 1);
- last_sequence += WriteBatchInternal::Count(updates);
- // 將當前的WriteBatch內容寫入Binlog以及Memtable
- ......
- versions_->SetLastSequence(last_sequence);
- }
- 在MakeRoomForWrite中為當前的寫入準備Memtable空間：Level0層有過多的文件時，會延緩或掛起當前寫操作；Memtable已經寫滿則嘗試切換到Immutable Memtable，生成新的Memtable供寫入，并觸發后臺的Immutable Memtable向Level0 SST文件的Dump。Immutable Memtable Dump不及時也會掛起當前寫操作。
- BuildBatchGroup中會嘗試將當前等待的所有其他Writer中的寫入合并到當前的WriteBatch中，以提高寫入效率。
- 之后將WriteBatch中內容寫入Binlog并循環寫入Memtable。
- 關注上述代碼的***一行，在所有的值寫入完成后才將Sequence真正更新，而LevelDB的讀請求又是基于Sequence的。這樣就保證了在WriteBatch寫入過程中，不會被讀請求部分看到，從而提供了原子性。
2，讀流程
- 首先，生成內部查詢所用的Key，該Key是由用戶請求的UserKey拼接上Sequence生成的。其中Sequence可以用戶提供或使用當前***的Sequence，LevelDB可以保證僅查詢在這個Sequence之前的寫入。
- 用生成的Key，依次嘗試從 Memtable，Immtable以及SST文件中讀取，直到找到。
- 從SST文件中查找需要依次嘗試在每一層中讀取，得益于Manifest中記錄的每個文件的key區間，我們可以很方便的知道某個key是否在文件中。Level0的文件由于直接由Immutable Dump 產生，不可避免的會相互重疊，所以需要對每個文件依次查找。對于其他層次，由于歸并過程保證了其互相不重疊且有序，二分查找的方式提供了更好的查詢效率。
- 可以看出同一個Key出現在上層的操作會屏蔽下層的。也因此刪除Key時只需要在Memtable壓入一條標記為刪除的條目即可。被其屏蔽的所有條目會在之后的歸并過程中清除。
壓縮操作
數據壓縮是LevelDB中重要的部分，即上文提到的歸并。冷數據會隨著Compaction不斷的下移，同時過期的數據也會在合并過程中被刪除。LevelDB的壓縮操作由單獨的后臺線程負責。這里的Compaction包括兩個部分，Memtable向Level0 SST文件的Compaction，以及SST文件向下層的Compaction，對應于兩個比較重要的函數：
1，CompactMemTable
CompactMemTable會將Immutable中的數據整體Dump為Level 0的一個文件，這個過程會在Immutable Memtable存在時被Compaction后臺線程調度。過程比較簡單，首先會獲得一個Immutable的Iterator用來遍歷其中的所有內容，創建一個新的Level 0 SST文件，并將Iterator讀出的內容依次順序寫入該文件。之后更新元信息并刪除Immutable Memtable。
2，BackgroundCompaction
SST文件的Compaction可以由用戶通過接口手動發起，也可以自動觸發。LevelDB中觸發SST Compaction的因素包括Level 0 SST的個數，其他Level SST文件的總大小，某個文件被訪問的次數。Compaction線程一次Compact的過程如下：
- 首先根據觸發Compaction的原因以及維護的相關信息找到本次要Compact的一個SST文件。對于Level0的文件比較特殊，由于Level0的SST文件由Memtable在不同時間Dump而成，所以可能有Key重疊。因此除該文件外還需要獲得所有與之重疊的Level0文件。這時我們得到一個包含一個或多個文件的文件集合，處于同一Level。
- SetupOtherInputs： 在Level+1層獲取所有與當前的文件集合有Key重合的文件。
- DoCompactionWork：對得到的包含相鄰兩層多個文件的文件集合，進行歸并操作并將結果輸出到Level + 1層的一個新的SST文件，歸并的過程中刪除所有過期的數據。
- 刪除之前的文件集合里的所有文件。通過上述過程我們可以看到，這個新生成的文件在其所在Level不會跟任何文件有Key的重疊。
總結
通過對LevelDB設計思路，整體結構以及其工作過程的介紹。相信已經對LevelDB有一個整體的印象。接下來還將用幾篇博客，更深入的介紹LevelDB的數據管理，版本控制，迭代器，緩存等方面的設計和實現。
