庖丁解LevelDB之整體感知

作者：王康 2017-12-20 08:58:14

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

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

LevelDB的數(shù)據(jù)是存儲(chǔ)在磁盤上的，采用LSM-Tree的結(jié)構(gòu)實(shí)現(xiàn)。LSM-Tree將磁盤的隨機(jī)寫轉(zhuǎn)化為順序?qū)懀瑥亩蟠筇岣吡藢懰俣取榱俗龅竭@一點(diǎn)LSM-Tree的思路是將索引樹結(jié)構(gòu)拆成一大一小兩顆樹，較小的一個(gè)常駐內(nèi)存，較大的一個(gè)持久化到磁盤，他們共同維護(hù)一個(gè)有序的key空間。寫入操作會(huì)首先操作內(nèi)存中的樹，隨著內(nèi)存中樹的不斷變大，會(huì)觸發(fā)與磁盤中樹的歸并操作，而歸并操作本身僅有順序?qū)憽Ｈ缦聢D所示：

LSM示意

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

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

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

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

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

讀寫操作

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

1，寫流程

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

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

在Write函數(shù)中會(huì)首先用當(dāng)前的WriteBatch封裝一個(gè)Writer，代表一個(gè)完整的寫入請求。LevelDB加鎖保證同一時(shí)刻只能有一個(gè)Writer工作。其他Writer掛起等待，直到前一個(gè)Writer執(zhí)行完畢后喚醒。單個(gè)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); 
   
  // 將當(dāng)前的WriteBatch內(nèi)容寫入Binlog以及Memtable 
  ...... 
 
  versions_->SetLastSequence(last_sequence); 
}

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

2，讀流程

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

壓縮操作

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

1，CompactMemTable

CompactMemTable會(huì)將Immutable中的數(shù)據(jù)整體Dump為Level 0的一個(gè)文件，這個(gè)過程會(huì)在Immutable Memtable存在時(shí)被Compaction后臺(tái)線程調(diào)度。過程比較簡單，首先會(huì)獲得一個(gè)Immutable的Iterator用來遍歷其中的所有內(nèi)容，創(chuàng)建一個(gè)新的Level 0 SST文件，并將Iterator讀出的內(nèi)容依次順序?qū)懭朐撐募Ｖ蟾略畔⒉h除Immutable Memtable。

2，BackgroundCompaction

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

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

總結(jié)

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

責(zé)任編輯：武曉燕來源： catkang博客