LevelDB是Google傳奇工程師Jeff Dean和Sanjay Ghemawat開源的KV存儲引擎探入，無論從設計還是代碼上都可以用精致優(yōu)雅來形容狡孔，非常值得細細品味。接下來就將用幾篇博客來由表及里的介紹LevelDB的設計和代碼細節(jié)蜂嗽。本文將從設計思路苗膝、整體結構、讀寫流程植旧、壓縮流程幾個方面來進行介紹辱揭，從而能夠對LevelDB有一個整體的感知离唐。
設計思路
LevelDB的數(shù)據(jù)是存儲在磁盤上的，采用LSM-Tree的結構實現(xiàn)问窃。LSM-Tree將磁盤的隨機寫轉化為順序寫亥鬓，從而大大提高了寫速度。為了做到這一點LSM-Tree的思路是將索引樹結構拆成一大一小兩顆樹域庇，較小的一個常駐內存嵌戈，較大的一個持久化到磁盤，他們共同維護一個有序的key空間听皿。寫入操作會首先操作內存中的樹熟呛，隨著內存中樹的不斷變大，會觸發(fā)與磁盤中樹的歸并操作尉姨，而歸并操作本身僅有順序寫庵朝。如下圖所示：
隨著數(shù)據(jù)的不斷寫入，磁盤中的樹會不斷膨脹啊送，為了避免每次參與歸并操作的數(shù)據(jù)量過大偿短，以及優(yōu)化讀操作的考慮，LevelDB將磁盤中的數(shù)據(jù)又拆分成多層馋没，每一層的數(shù)據(jù)達到一定容量后會觸發(fā)向下一層的歸并操作昔逗，每一層的數(shù)據(jù)量比其上一層成倍增長。這也就是LevelDB的名稱來源篷朵。
整體結構
具體到代碼實現(xiàn)上勾怒，LevelDB有幾個重要的角色，包括對應于上文提到的內存數(shù)據(jù)的Memtable声旺，分層數(shù)據(jù)存儲的SST文件笔链，版本控制的Manifest、Current文件腮猖，以及寫Memtable前的WAL鉴扫。這里簡單介紹各個組件的作用和在整個結構中的位置，更詳細的介紹將在之后的博客中進行澈缺。
- Memtable：內存數(shù)據(jù)結構坪创，跳表實現(xiàn)，新的數(shù)據(jù)會首先寫入這里姐赡；
- Log文件：寫Memtable前會先寫Log文件莱预，Log通過append的方式順序寫入。Log的存在使得機器宕機導致的內存數(shù)據(jù)丟失得以恢復项滑；
- Immutable Memtable：達到Memtable設置的容量上限后依沮，Memtable會變?yōu)镮mmutable為之后向SST文件的歸并做準備，顧名思義，Immutable Mumtable不再接受用戶寫入危喉，同時會有新的Memtable生成宋渔；
- SST文件：磁盤數(shù)據(jù)存儲文件。分為Level 0到Level N多層辜限，每一層包含多個SST文件傻谁；單個SST文件容量隨層次增加成倍增長；文件內數(shù)據(jù)有序列粪；其中Level0的SST文件由Immutable直接Dump產生，其他Level的SST文件由其上一層的文件和本層文件歸并產生谈飒；SST文件在歸并過程中順序寫生成岂座，生成后僅可能在之后的歸并中被刪除，而不會有任何的修改操作杭措。
- Manifest文件： Manifest文件中記錄SST文件在不同Level的分布费什，單個SST文件的最大最小key，以及其他一些LevelDB需要的元信息手素。
- Current文件: 從上面的介紹可以看出鸳址，LevelDB啟動時的首要任務就是找到當前的Manifest，而Manifest可能有多個泉懦。Current文件簡單的記錄了當前Manifest的文件名稿黍，從而讓這個過程變得非常簡單。
讀寫操作
作為KV數(shù)據(jù)存儲引擎崩哩，基本的讀寫操作是必不可少的巡球，通過對讀寫操作流程的了解，也能讓我們更直觀的窺探其內部實現(xiàn)邓嘹。
1酣栈，寫流程
LevelDB的寫操作包括設置key-value和刪除key兩種。需要指出的是這兩種情況在LevelDB的處理上是一致的汹押，刪除操作其實是向LevelDB插入一條標識為刪除的數(shù)據(jù)矿筝。下面就一起看看LevelDB插入值的過程。
LevelDB對外暴露的寫接口包括Put棚贾，Delete和Write窖维，其中Write需要WriteBatch作為參數(shù)，而Put和Delete首先就是將當前的操作封裝到一個WriteBatch對象鸟悴，并調用Write接口陈辱。這里的WriteBatch是一批寫操作的集合，其存在的意義在于提高寫入效率细诸，并提供Batch內所有寫入的原子性沛贪。
在Write函數(shù)中會首先用當前的WriteBatch封裝一個Writer，代表一個完整的寫入請求。LevelDB加鎖保證同一時刻只能有一個Writer工作利赋。其他Writer掛起等待水评，直到前一個Writer執(zhí)行完畢后喚醒。單個Writer執(zhí)行過程如下：
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已經(jīng)寫滿則嘗試切換到Immutable Memtable，生成新的Memtable供寫入塘偎，并觸發(fā)后臺的Immutable Memtable向Level0 SST文件的Dump疗涉。Immutable Memtable Dump不及時也會掛起當前寫操作。
- BuildBatchGroup中會嘗試將當前等待的所有其他Writer中的寫入合并到當前的WriteBatch中吟秩，以提高寫入效率咱扣。
- 之后將WriteBatch中內容寫入Binlog并循環(huán)寫入Memtable。
- 關注上述代碼的最后一行涵防，在所有的值寫入完成后才將Sequence真正更新闹伪，而LevelDB的讀請求又是基于Sequence的。這樣就保證了在WriteBatch寫入過程中壮池，不會被讀請求部分看到偏瓤，從而提供了原子性。
2椰憋，讀流程
首先厅克，生成內部查詢所用的Key，該Key是由用戶請求的UserKey拼接上Sequence生成的橙依。其中Sequence可以用戶提供或使用當前最新的Sequence已骇，LevelDB可以保證僅查詢在這個Sequence之前的寫入。
用生成的Key票编，依次嘗試從 Memtable褪储，Immtable以及SST文件中讀取，直到找到慧域。
從SST文件中查找需要依次嘗試在每一層中讀取鲤竹，得益于Manifest中記錄的每個文件的key區(qū)間，我們可以很方便的知道某個key是否在文件中昔榴。Level0的文件由于直接由Immutable Dump 產生辛藻，不可避免的會相互重疊，所以需要對每個文件依次查找互订。對于其他層次吱肌，由于歸并過程保證了其互相不重疊且有序，二分查找的方式提供了更好的查詢效率仰禽。
-
可以看出同一個Key出現(xiàn)在上層的操作會屏蔽下層的氮墨。也因此刪除Key時只需要在Memtable壓入一條標記為刪除的條目即可纺蛆。被其屏蔽的所有條目會在之后的歸并過程中清除。
?
壓縮操作
數(shù)據(jù)壓縮是LevelDB中重要的部分规揪，即上文提到的歸并桥氏。冷數(shù)據(jù)會隨著Compaction不斷的下移，同時過期的數(shù)據(jù)也會在合并過程中被刪除猛铅。LevelDB的壓縮操作由單獨的后臺線程負責字支。這里的Compaction包括兩個部分，Memtable向Level0 SST文件的Compaction奸忽，以及SST文件向下層的Compaction堕伪，對應于兩個比較重要的函數(shù)：
1，CompactMemTable
CompactMemTable會將Immutable中的數(shù)據(jù)整體Dump為Level 0的一個文件栗菜，這個過程會在Immutable Memtable存在時被Compaction后臺線程調度刃跛。過程比較簡單，首先會獲得一個Immutable的Iterator用來遍歷其中的所有內容苛萎，創(chuàng)建一個新的Level 0 SST文件，并將Iterator讀出的內容依次順序寫入該文件检号。之后更新元信息并刪除Immutable Memtable腌歉。
2，BackgroundCompaction
SST文件的Compaction可以由用戶通過接口手動發(fā)起齐苛，也可以自動觸發(fā)翘盖。LevelDB中觸發(fā)SST Compaction的因素包括Level 0 SST的個數(shù)，其他Level SST文件的總大小凹蜂，某個文件被訪問的次數(shù)馍驯。Compaction線程一次Compact的過程如下：
- 首先根據(jù)觸發(fā)Compaction的原因以及維護的相關信息找到本次要Compact的一個SST文件。對于Level0的文件比較特殊玛痊，由于Level0的SST文件由Memtable在不同時間Dump而成汰瘫，所以可能有Key重疊。因此除該文件外還需要獲得所有與之重疊的Level0文件擂煞。這時我們得到一個包含一個或多個文件的文件集合混弥，處于同一Level。
- SetupOtherInputs： 在Level+1層獲取所有與當前的文件集合有Key重合的文件对省。
- DoCompactionWork：對得到的包含相鄰兩層多個文件的文件集合蝗拿，進行歸并操作并將結果輸出到Level + 1層的一個新的SST文件，歸并的過程中刪除所有過期的數(shù)據(jù)蒿涎。
- 刪除之前的文件集合里的所有文件哀托。通過上述過程我們可以看到，這個新生成的文件在其所在Level不會跟任何文件有Key的重疊劳秋。
總結
通過對LevelDB設計思路仓手，整體結構以及其工作過程的介紹胖齐。相信已經(jīng)對LevelDB有一個整體的印象。接下來還將用幾篇博客俗或，更深入的介紹LevelDB的數(shù)據(jù)管理市怎，版本控制，迭代器辛慰，緩存等方面的設計和實現(xiàn)区匠。
參考
LSM-Tree示意圖來源于論文：The Log-Structured Merge-Tree
Source Code：https://github.com/google/leveldb
