LevelDB是Google傳奇工程師Jeff Dean和Sanjay Ghemawat開(kāi)源的KV存儲(chǔ)引擎，無(wú)論從設(shè)計(jì)還是代碼上都可以用精致優(yōu)雅來(lái)形容，非常值得細(xì)細(xì)品味。本文將從設(shè)計(jì)思路、整體結(jié)構(gòu)、讀寫(xiě)流程、壓縮流程幾個(gè)方面來(lái)進(jìn)行介紹，從而能夠?qū)evelDB有一個(gè)整體的感知。

設(shè)計(jì)思路

LevelDB的數(shù)據(jù)是存儲(chǔ)在磁盤(pán)上的，采用LSM-Tree的結(jié)構(gòu)實(shí)現(xiàn)。LSM-Tree將磁盤(pán)的隨機(jī)寫(xiě)轉(zhuǎn)化為順序?qū)?，從而大大提高了?xiě)速度。為了做到這一點(diǎn)LSM-Tree的思路是將索引樹(shù)結(jié)構(gòu)拆成一大一小兩顆樹(shù)，較小的一個(gè)常駐內(nèi)存，較大的一個(gè)持久化到磁盤(pán)，他們共同維護(hù)一個(gè)有序的key空間。寫(xiě)入操作會(huì)首先操作內(nèi)存中的樹(shù)，隨著內(nèi)存中樹(shù)的不斷變大，會(huì)觸發(fā)與磁盤(pán)中樹(shù)的歸并操作，而歸并操作本身僅有順序?qū)?。如下圖所示：

LSM示意

隨著數(shù)據(jù)的不斷寫(xiě)入，磁盤(pán)中的樹(shù)會(huì)不斷膨脹，為了避免每次參與歸并操作的數(shù)據(jù)量過(guò)大，以及優(yōu)化讀操作的考慮，LevelDB將磁盤(pán)中的數(shù)據(jù)又拆分成多層，每一層的數(shù)據(jù)達(dá)到一定容量后會(huì)觸發(fā)向下一層的歸并操作，每一層的數(shù)據(jù)量比其上一層成倍增長(zhǎng)。這也就是LevelDB的名稱來(lái)源。

整體結(jié)構(gòu)

具體到代碼實(shí)現(xiàn)上，LevelDB有幾個(gè)重要的角色，包括對(duì)應(yīng)于上文提到的內(nèi)存數(shù)據(jù)的Memtable，分層數(shù)據(jù)存儲(chǔ)的SST文件，版本控制的Manifest、Current文件，以及寫(xiě)Memtable前的WAL。這里簡(jiǎn)單介紹各個(gè)組件的作用和在整個(gè)結(jié)構(gòu)中的位置。

• Memtable：內(nèi)存數(shù)據(jù)結(jié)構(gòu)，跳表實(shí)現(xiàn)，新的數(shù)據(jù)會(huì)首先寫(xiě)入這里；
• Log文件：寫(xiě)Memtable前會(huì)先寫(xiě)Log文件，Log通過(guò)append的方式順序?qū)懭?。Log的存在使得機(jī)器宕機(jī)導(dǎo)致的內(nèi)存數(shù)據(jù)丟失得以恢復(fù)；
• Immutable Memtable：達(dá)到Memtable設(shè)置的容量上限后，Memtable會(huì)變?yōu)镮mmutable為之后向SST文件的歸并做準(zhǔn)備，顧名思義，Immutable Mumtable不再接受用戶寫(xiě)入，同時(shí)會(huì)有新的Memtable生成；
• SST文件：磁盤(pán)數(shù)據(jù)存儲(chǔ)文件。分為L(zhǎng)evel 0到Level N多層，每一層包含多個(gè)SST文件；單個(gè)SST文件容量隨層次增加成倍增長(zhǎng)；文件內(nèi)數(shù)據(jù)有序；其中Level0的SST文件由Immutable直接Dump產(chǎn)生，其他Level的SST文件由其上一層的文件和本層文件歸并產(chǎn)生；SST文件在歸并過(guò)程中順序?qū)懮?，生成后僅可能在之后的歸并中被刪除，而不會(huì)有任何的修改操作。
• Manifest文件： Manifest文件中記錄SST文件在不同Level的分布，單個(gè)SST文件的***最小key，以及其他一些LevelDB需要的元信息。
• Current文件: 從上面的介紹可以看出，LevelDB啟動(dòng)時(shí)的首要任務(wù)就是找到當(dāng)前的Manifest，而Manifest可能有多個(gè)。Current文件簡(jiǎn)單的記錄了當(dāng)前Manifest的文件名，從而讓這個(gè)過(guò)程變得非常簡(jiǎn)單。

LevelDB 結(jié)構(gòu)

讀寫(xiě)操作

作為KV數(shù)據(jù)存儲(chǔ)引擎，基本的讀寫(xiě)操作是必不可少的，通過(guò)對(duì)讀寫(xiě)操作流程的了解，也能讓我們更直觀的窺探其內(nèi)部實(shí)現(xiàn)。

1，寫(xiě)流程

LevelDB的寫(xiě)操作包括設(shè)置key-value和刪除key兩種。需要指出的是這兩種情況在LevelDB的處理上是一致的，刪除操作其實(shí)是向LevelDB插入一條標(biāo)識(shí)為刪除的數(shù)據(jù)。下面就一起看看LevelDB插入值的過(guò)程。

LevelDB對(duì)外暴露的寫(xiě)接口包括Put，Delete和Write，其中Write需要WriteBatch作為參數(shù)，而Put和Delete首先就是將當(dāng)前的操作封裝到一個(gè)WriteBatch對(duì)象，并調(diào)用Write接口。這里的WriteBatch是一批寫(xiě)操作的集合，其存在的意義在于提高寫(xiě)入效率，并提供Batch內(nèi)所有寫(xiě)入的原子性。

在Write函數(shù)中會(huì)首先用當(dāng)前的WriteBatch封裝一個(gè)Writer，代表一個(gè)完整的寫(xiě)入請(qǐng)求。LevelDB加鎖保證同一時(shí)刻只能有一個(gè)Writer工作。其他Writer掛起等待，直到前一個(gè)Writer執(zhí)行完畢后喚醒。單個(gè)Writer執(zhí)行過(guò)程如下：

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); 
   
  // 將當(dāng)前的WriteBatch內(nèi)容寫(xiě)入Binlog以及Memtable 
  ...... 
 
  versions_->SetLastSequence(last_sequence); 
} 

• 在MakeRoomForWrite中為當(dāng)前的寫(xiě)入準(zhǔn)備Memtable空間：Level0層有過(guò)多的文件時(shí)，會(huì)延緩或掛起當(dāng)前寫(xiě)操作；Memtable已經(jīng)寫(xiě)滿則嘗試切換到Immutable Memtable，生成新的Memtable供寫(xiě)入，并觸發(fā)后臺(tái)的Immutable Memtable向Level0 SST文件的Dump。Immutable Memtable Dump不及時(shí)也會(huì)掛起當(dāng)前寫(xiě)操作。
• BuildBatchGroup中會(huì)嘗試將當(dāng)前等待的所有其他Writer中的寫(xiě)入合并到當(dāng)前的WriteBatch中，以提高寫(xiě)入效率。
• 之后將WriteBatch中內(nèi)容寫(xiě)入Binlog并循環(huán)寫(xiě)入Memtable。
• 關(guān)注上述代碼的***一行，在所有的值寫(xiě)入完成后才將Sequence真正更新，而LevelDB的讀請(qǐng)求又是基于Sequence的。這樣就保證了在WriteBatch寫(xiě)入過(guò)程中，不會(huì)被讀請(qǐng)求部分看到，從而提供了原子性。

2，讀流程

• 首先，生成內(nèi)部查詢所用的Key，該Key是由用戶請(qǐng)求的UserKey拼接上Sequence生成的。其中Sequence可以用戶提供或使用當(dāng)前***的Sequence，LevelDB可以保證僅查詢?cè)谶@個(gè)Sequence之前的寫(xiě)入。
• 用生成的Key，依次嘗試從 Memtable，Immtable以及SST文件中讀取，直到找到。
• 從SST文件中查找需要依次嘗試在每一層中讀取，得益于Manifest中記錄的每個(gè)文件的key區(qū)間，我們可以很方便的知道某個(gè)key是否在文件中。Level0的文件由于直接由Immutable Dump 產(chǎn)生，不可避免的會(huì)相互重疊，所以需要對(duì)每個(gè)文件依次查找。對(duì)于其他層次，由于歸并過(guò)程保證了其互相不重疊且有序，二分查找的方式提供了更好的查詢效率。
• 可以看出同一個(gè)Key出現(xiàn)在上層的操作會(huì)屏蔽下層的。也因此刪除Key時(shí)只需要在Memtable壓入一條標(biāo)記為刪除的條目即可。被其屏蔽的所有條目會(huì)在之后的歸并過(guò)程中清除。

壓縮操作

數(shù)據(jù)壓縮是LevelDB中重要的部分，即上文提到的歸并。冷數(shù)據(jù)會(huì)隨著Compaction不斷的下移，同時(shí)過(guò)期的數(shù)據(jù)也會(huì)在合并過(guò)程中被刪除。LevelDB的壓縮操作由單獨(dú)的后臺(tái)線程負(fù)責(zé)。這里的Compaction包括兩個(gè)部分，Memtable向Level0 SST文件的Compaction，以及SST文件向下層的Compaction，對(duì)應(yīng)于兩個(gè)比較重要的函數(shù)：

1，CompactMemTable

CompactMemTable會(huì)將Immutable中的數(shù)據(jù)整體Dump為L(zhǎng)evel 0的一個(gè)文件，這個(gè)過(guò)程會(huì)在Immutable Memtable存在時(shí)被Compaction后臺(tái)線程調(diào)度。過(guò)程比較簡(jiǎn)單，首先會(huì)獲得一個(gè)Immutable的Iterator用來(lái)遍歷其中的所有內(nèi)容，創(chuàng)建一個(gè)新的Level 0 SST文件，并將Iterator讀出的內(nèi)容依次順序?qū)懭朐撐募?。之后更新元信息并刪除Immutable Memtable。

2，BackgroundCompaction

SST文件的Compaction可以由用戶通過(guò)接口手動(dòng)發(fā)起，也可以自動(dòng)觸發(fā)。LevelDB中觸發(fā)SST Compaction的因素包括Level 0 SST的個(gè)數(shù)，其他Level SST文件的總大小，某個(gè)文件被訪問(wèn)的次數(shù)。Compaction線程一次Compact的過(guò)程如下：

• 首先根據(jù)觸發(fā)Compaction的原因以及維護(hù)的相關(guān)信息找到本次要Compact的一個(gè)SST文件。對(duì)于Level0的文件比較特殊，由于Level0的SST文件由Memtable在不同時(shí)間Dump而成，所以可能有Key重疊。因此除該文件外還需要獲得所有與之重疊的Level0文件。這時(shí)我們得到一個(gè)包含一個(gè)或多個(gè)文件的文件集合，處于同一Level。
• SetupOtherInputs： 在Level+1層獲取所有與當(dāng)前的文件集合有Key重合的文件。
• DoCompactionWork：對(duì)得到的包含相鄰兩層多個(gè)文件的文件集合，進(jìn)行歸并操作并將結(jié)果輸出到Level + 1層的一個(gè)新的SST文件，歸并的過(guò)程中刪除所有過(guò)期的數(shù)據(jù)。
• 刪除之前的文件集合里的所有文件。通過(guò)上述過(guò)程我們可以看到，這個(gè)新生成的文件在其所在Level不會(huì)跟任何文件有Key的重疊。

總結(jié)

通過(guò)對(duì)LevelDB設(shè)計(jì)思路，整體結(jié)構(gòu)以及其工作過(guò)程的介紹。相信已經(jīng)對(duì)LevelDB有一個(gè)整體的印象。接下來(lái)還將用幾篇博客，更深入的介紹LevelDB的數(shù)據(jù)管理，版本控制，迭代器，緩存等方面的設(shè)計(jì)和實(shí)現(xiàn)。