導讀：LevelDB是Google開源的持久化KV資料庫，在其高效能的背後，將資料拆分成多層進行儲存。本文作者深入分析了LevelDB儲存模組的設計和原始碼實現，快速瞭解LevelDB高效能背後的原理。

作者 codedump codedump.info 博主，多年從事網際網路伺服器後臺開發工作。可訪問作者部落格閱讀 codedump 更多文章。

 

本文基於leveldb 1.9.0程式碼。

整體架構

 

如上圖，leveldb的資料儲存在記憶體以及磁碟上，其中：

• memtable：儲存在記憶體中的資料，使用skiplist實現。
• immutable memtable：與memtable一樣，只不過這個memtable不能再進行修改，會將其中的資料落盤到level 0的sstable中。
• 多層sstable：leveldb使用多個層次來儲存sstable檔案，這些檔案分佈在磁碟上，這些檔案都是根據鍵值有序排列的，其中0級的sstable的鍵值可能會重疊，而level 1及以上的sstable檔案不會重疊。

 

在上面這個儲存層次中，越靠上的資料越新，即同一個鍵值如果同時存在於memtable和immutable memtable中，則以memtable中的為準。

 

另外，圖中還使用箭頭來表示了合併資料的走向，即：

 

 

以下將針對這幾部分展開討論。

Log檔案

寫入資料的時候，最開始會寫入到log檔案中，由於是順序寫入檔案，所以寫入速度很快，可以馬上傳回。

 

來看Log檔案的結構：

• 一個Log檔案由多個Block組成，每個Block大小為32KB。
• 一個Block內部又有多個Record組成，Record分為四種型別：
  • Full：一個Record佔滿了整個Block儲存空間。
  • First：一個Block的第一個Record。
  • Last：一個Block的最後一個Record。
  • Middle：其餘的都是Middle型別的Record。
• Record的結構如下：
  • 32位長度的CRC Checksum：儲存這個Record的資料校驗值，用於檢測Record合法性。
  • 16位長度的Length：儲存資料部分長度。
  • 8位長度的Type：儲存Record型別，就是上面說的四種型別。
  • Header部分
  • 資料部分

memtable

memtable用於儲存在記憶體中還未落盤到sstable中的資料，這部分使用跳錶（skiplist）做為底層的資料結構，這裡先簡單描述一下跳錶的工作原理。

 

如果資料存放在一個普通的有序連結串列中，那麼查詢資料的時間複雜度就是O(n)。跳錶的設計思想在於：連結串列中的每個元素，都有多個層次，查詢某一個元素時，遍歷該連結串列的時候，根據層次來跳過（skip）中間某些明顯不滿足需求的元素，以達到加快查詢速度的目的，如下圖所示：

 

 

在以上這個跳錶中，查詢元素6的流程，大體如下：

• 構建一個每個連結串列元素最多有5個元素的跳錶。
• 由於6大於連結串列的第一個元素1，因此如果存在必然在1之後的元素中，因此進入元素1的指標陣列中，從上往下查詢元素4：
  • 第一層：指向的指標為Nil空指標，不滿足需求，繼續往下查詢；
  • 第二層：指向的指標儲存的資料為4，小於待查詢的元素4，因此如果元素6存在也必然在4之後，因此指標跳轉到元素4所在的位置，繼續從上往下開始查詢。
• 到了元素4所在的指標陣列，開始從上往下繼續查詢：
  • 第一層：指向的指標儲存的資料為6，查詢完畢。

 

從上面的分析過程中可以看到：

• 跳錶是一種以犧牲更多的儲存空間換取查詢速度，即“空間換時間”的資料結構。
• 跳錶的每一層也都是一個有序連結串列。
• 如果一個元素出現在第i層的連結串列中，那麼也必然會在第i層以下的連結串列中出現。
• 連結串列的每個節點中，垂直方向的陣列儲存的資料都是一樣的，水平方向的指標指向連結串列的下一個元素。
• 最底層的連結串列包含所有元素，也就是說，在最底層資料結構退化為一個普通的有序連結串列。
  

sstable檔案

大體結構

首先來看sstable檔案的整體結構，如下圖：

 

 

sstable檔案中分為以下幾個組成部分：

• data block：儲存資料的block，由於一個block大小固定，因此每個sstable檔案中有多個data block。
• filter block以及metaindex block：這兩個block不一定存在於sstable，取決於Options中的filter_policy引數值，後面就不對這兩部分進行講解。
• index block：儲存的是索引資料，即可以根據index block中的資料快速定位到資料處於哪個data block的哪個位置。
• footer：腳註資料，每個footer資料資訊大小固定，儲存一個sstable檔案的元資訊（meta data）。

 

可以看到，上面這幾部分資料，從檔案的組織來看自上而下，先有了資料再有索引資料，最後才是檔案自身的元資訊。原因在於：索引資料是針對資料的索引資訊，在資料沒有寫完畢之前，索引資訊還會發生改變，所以索引資料要等資料寫完；而元資訊就是針對索引資料的索引，同樣要依賴於索引資訊寫完畢才可以。

 

block

上面幾部分資料中，除去footer之外，內部都是以block的形式來組織資料，接著看block的結構，如下圖：

 

 

從上面看出，實際上儲存資料的block大同小異：最開始的一部分儲存資料，然後儲存型別，最後一部分儲存這個block的校驗碼以做合法性校驗。

 

以上只是對block大體結構的分析，在資料部分，每一條資料記錄leveldb使用字首壓縮（prefix-compressed）方式來儲存。這種演演算法的原理是：針對一組資料，取出一個公共的字首，而在該組中的其它字串只儲存非公共的字串做為key即可，由於sstable儲存KV資料是嚴格按照key的順序來排序的，所以這樣能節省出儲存key資料的空間來。

 

如下圖所示：一個block內部劃分了多個記錄組（record group），每個記錄組內部又由多條記錄（record）組成。在同一個記錄組內部，以本組的第一條資料的鍵值做為公共字首，後續的記錄資料鍵值部分只存放與公共字首非共享部分的資料即可。

 

 

以記錄的三個資料、、為例，假設這三個資料在同一個record group內，那麼對應的record記錄如下所示：

 

 

說明如下：

• ：由於這對資料是這一組記錄組的第一組資料，因此共享的字首部分長度為0，因為每一組都以第一條資料的key為共享字首，因此針對第一條資料本身，其共享字首長度就是0了。
• ：鍵值“ab”與本組公共字首（即本組的第一條資料鍵值“a”）有公共字首“a”，因此共享字首長度為1，非共享部分鍵值為剩下的“b”。
• ：鍵值“c”與本組公共字首“a”沒有重合部分，因此共享字首長度為0。

 

因為一個block內部有多個記錄組，因此還需要另外的資料來記錄不同記錄組的位置，這部分資料被稱為“重啟點（restart point）”，重啟點首先會以陣列的形式儲存下來，直到該block資料需要落盤的情況下才會寫到block結尾處。

 

有了以上的準備，就可以來具體看新增資料的程式碼了，向一個block中新增資料的偽程式碼如下。

 

 

有了前面的這些準備，再在前面block格式的基礎上展開，得到更加詳細的格式如下：

 

 

block詳細格式還是劃分為三大部分，其中：

• 資料部分
  • 多個記錄組組成的記錄資料。
  • 多個重啟點資料組成的重啟點陣列資料，每個元素記錄對應的記錄組在block中的偏移量，型別為fixed32型別。
• 壓縮型別，大小為1 Byte。
• CRC32校驗資料，大小為4 Byte。

   

 

footer

footer做為儲存sstable檔案原資訊部分的資料，格式相對簡單，如下圖：

Iterator的設計

迭代器的設計是leveldb中的一大亮點，leveldb設計了一個虛擬基類Iterator，其中定義了諸如遍歷、查詢之類的介面，而該基類有多種實現。原因在於：leveldb中存在多種資料結構和多種使用場景，如：

• 儲存記憶體中資料的memtable。
• 儲存落盤資料的sstable，而就前面分析而言，一個sstable中還有不同的block，需要根據index block來定位資料處於哪個data block。
• 進行合併的時候，每次最多合併兩個層次的檔案，在這個過程中需要對待合併的檔案集合進行遍歷。前面分析的DBImpl::DoCompactionWork函式，就是透過iterator來遍歷待合併檔案進行合併操作的。

 

逐個來看不同的iterator實現以及其使用場景。

迭代器大體分為兩類：

• 底層迭代器：處於最底層，直接訪問底層資料結構，而不依賴於其他迭代器的迭代器。
• 組合迭代器：組合各種迭代器（包括底層和組合迭代器）完成工作的迭代器。

 

底層迭代器

底層迭代器有以下三種：

• MemTableIterator：用於實現對memtable的迭代遍歷，由於memtable由skiplist實現，因此內部封裝了對skiplist的迭代訪問。
• Block::Iter：前面分析sstable的時候，講到一個sstable內部其實有多個block組成，這個迭代器就是按照block的結構進行迭代訪問的迭代器。
• Version::LevelFileNumIterator：每個level都由多個sstable檔案組成，說白了就是一個sstable型別的陣列。除了level 0之外，其餘level的sstable的鍵值之間沒有重疊關係，而LevelFileNumIterator就是用於迭代一組有序sstable檔案的迭代器。

 

 

組合迭代器

組合迭代器內部都包含至少一個迭代器，組合起來完成迭代工作，有如下幾類。

 

TwoLevelIterator

顧名思義，TwoLevelIterator表示兩層迭代器，建立TwoLevelIterator的函式原型為：

 

 

引數說明如下：

• Iterator* index_iter：索引迭代器，可以理解為第一層的迭代器。
• BlockFunction *block_function：這是一個函式指標，根據index_iter迭代器的傳回結果來再建立一個迭代器，即針對查詢索引傳回資料的迭代器。其函式引數有三個，其中前面兩個由下麵的arg以及options引數指定，而第三個引數slice就是index_iterator傳回的索引資料。
• void* arg：傳入BlockFunction函式的第一個引數。
• const ReadOptions& options：傳入BlockFunction函式的第二個引數。

綜合以上，TwoLevelIterator的工作流程如下：

 

 

TwoLevelIterator有如下兩類：

• Table::Iterator：實現對於單個sstable檔案的迭代。由於一個sstable檔案中有多個block，而又劃分為index block和data block，查詢資料時，先根據鍵值到index block中查詢到對應的data block，再進入data block中進行查詢，這個查詢過程實際就是一個兩層的查詢過程：先查索引資料，再查資料。因此Table::Iterator型別的TwoLevelIterator，組合了index block的Block::Iter，以及data block的Block::Iter。
• ConcatenatingIterator：組合了LevelFileNumIterator以及Table::Iterator，用於在某一層內的sstable檔案中查詢資料。因此它的第一層迭代器就是前面的LevelFileNumIterator，用於根據一個鍵值在一組有序的sstable檔案中定位到所在的檔案，而第二層的迭代器是Table::Iterator，用於在第一層迭代器LevelFileNumIterator中查詢到的sstable檔案中查詢鍵值。另外，既然ConcatenatingIterator處理的是有序sstable檔案，那麼level 0的sstable檔案就不會使用這種迭代器進行訪問，因為level 0檔案之間有重疊鍵值。

 

 

MergingIterator

用於合併流程的迭代器。在合併過程中，需要操作memtable、immutable memtable、level 0 sstable以及非level 0的sstable，該迭代器將這些儲存資料結構體的迭代器，統一進行歸併排序：

• memtable以及immutable memtable：使用前面提過的MemtableIterator迭代器。
• level 0 sstable：由於level 0的sstable檔案之間鍵值有重疊，所以使用的是level 0的sstable檔案各自的Table::Iterator。
• level 1層級及以上的sstable：使用前面介紹過的ConcatenatingIterator，即可以針對一組有序sstable檔案進行遍歷的iterator。

 

由於以上每種型別的iterator，內部遍歷資料都是有序的，所以MergingIterator內部做的事情，就是將對這些iterator的遍歷結果進行“歸併”。MergingIterator內部有如下變數：

• const Comparator* comparator_：用於鍵值比較的函式operator。
• IteratorWrapper* children_：儲存傳入的iterator的陣列。
• int n_：children_陣列的大小。
• IteratorWrapper* current_：儲存當前查詢到的位置所在的iterator。
• Direction direction_：儲存查詢的方向，有向前和向後兩種查詢防線。

 

可以看到，current_以及direction_兩個成員是用於儲存當前查詢狀態的成員。

構建MergingIterator迭代器傳入的Comparator是InternalKeyComparator，其比較邏輯是：

• 首先比較鍵值是否相等，不相等則直接傳回比較結果。
• 如果鍵值相等，那麼從鍵值中decode出來sequence值，對比sequence值，對sequence值進行降序比較。由於這個值是單調遞增的，因此越新的資料sequence值越大。換言之，在儲存層次中（依次為memtable->immutable memtable->level 0 sstable->level n sstable）越靠上面的資料，在鍵值相同的情況下越小。

 

Seek(target)函式的偽程式碼：

 

 

而FindSmallest函式的實現，是遍歷children_找到最小的child儲存到current_指標中。前面分析InternalKeyComparator提到過，相同鍵值的資料，根據sequence值進行降序排列，即資料越新的資料其sequence值越大，在這個排序中查詢的結果就越在上面。因此，FindSmallest函式如果在memtable、level 0中都找到了相同鍵值，將優先選擇memtable中的資料。

 

MergingIterator迭代器的其它實現不再做解釋，簡單理解：針對一組iterator的查詢結果進行歸併排序。對於同樣一個鍵值，只取位置在儲存位置上最靠上面的資料。

 

這麼做的原因在於：一個鍵值的資料可能被寫入多次，而需要以最後一次寫入的資料為準，合併時將丟棄掉不在儲存最上面的資料。

 

以下麵的例子來說明MergingIterator迭代器的合併結果。

 

 

在上圖的左半邊，是合併前的資料分佈情況，依次為：

• memtable：鍵值1的刪除記錄，以及鍵值<2,test>。
• immutable memtable：鍵值<2,tesat2>以及<3,test>。
• level 0 sstable：鍵值<1,test>。
• level 1 sstable：鍵值<3,a>。

 

合併的結果如上圖的右邊所示：

• 鍵1：因為第一條鍵1的記錄是在memtable中的刪除記錄，所以鍵1將被刪除，即不會出現在合併結果中。
• 鍵2：最靠上面的關於鍵2的儲存記錄是<2,test>，這條記錄儲存在合併結果中，而immutable memtable的記錄<2,test2>將被丟棄，因為這條記錄不是最新的。
• 鍵3：使用了immutable memtable中的記錄<3,test>，丟棄了level 1 sstable中的<3,a>這條記錄。

核心流程

有了前面幾種核心資料結構的瞭解，下麵談leveldb中的幾個核心流程。

 

修改流程

修改資料，分為兩類：正常的寫入資料操作以及刪除資料操作。

 

先看正常的寫入資料操作：

• append一條記錄到log檔案中，雖然這是一次寫磁碟操作，但是由於是在檔案末尾做的順序寫操作，所以效率並不低。
• 向當前的memtable中寫入一條資料。這個動作看似簡單，但是如果在來不及合併的時候，可能會出現阻塞，在後面合併操作中再展開解釋。

 

完成以上兩步之後，就可以認為完成了更新資料的操作。實際上只有一次檔案末尾的順序寫操作，以及一次寫記憶體操作，如果不考慮會被合併操作阻塞的情況，實際上還是很快的。

 

再來看刪除資料操作。leveldb中，刪除一個資料，其實也是新增一條新的記錄，只不過記錄型別是刪除型別，程式碼中透過列舉變數定義了這兩種操作型別：

 

 

這樣看起來，leveldb刪除資料時，並不會真的去刪除一條資料，而是打上了一個標記，那麼問題就來了：如果寫入資料操作與刪除資料操作，只是型別不同，在查詢資料的時候又如何知道資料是否存在？看下麵的讀資料流程。

 

讀流程

向leveldb中查詢一個資料，也是從上而下，先查記憶體然後到磁碟上的sstable檔案查詢，如下圖所示：

 

 

• 先在記憶體中的memtable中查詢資料，查到則傳回；
• 否則在磁碟中的sstable檔案中查詢資料，從0級開始往下查詢，查到則傳回；

 

這樣自上而下的原因就在於leveldb的設計：越是在上層的資料越新，距離當前時間越短。

 

舉例而言，對於鍵值key而言，首先寫入kv對，然後再刪除鍵值key資料。第一次寫入的資料，可能因為合併的原因以及到了sstable檔案上，而再次刪除鍵值key的資料時，根據上面的解釋，其實也是寫入資料，只不過標記為刪除。於是，越後寫入的資料，越在上面這個層次的上面，這樣從上往下查詢時就能先查詢到後寫入的資料，此時看到了資料已經被標記為刪除，就可以認為資料不存在了。

 

那麼，前面寫入的資料實際上已經沒有用了，但是又佔用了空間，這部分資料就等待著後面的合併流程來合併資料最後刪除掉。

 

合併流程

核心資料結構

首先來看與合併相關的核心資料結構。

 

每一次合併過程以及將memtable中的資料落盤到sstable的過程，都涉及到sstable檔案的增刪，而這每一次操作，都對應到一個版本。

 

在leveldb中，使用Version類來儲存一個版本的元資訊，主要包括：

• std::vector

   files_[config::kNumLevels]：用於儲存所有級別sstable檔案的FileMetaData陣列，可以看到這個成員是一個陣列，而陣列的每個元素又是一個vector，這其中陣列部分使用level級別來進行索引，同級別的sstable資訊儲存在vector中。

• FileMetaData* file_to_compact_和int file_to_compact_level_：下一次進行合併時的檔案和級別。
• double compaction_score_和int compaction_level_：當前最大compact分數和對應的級別，在Finalize函式中進行計算，具體計算的規則會在下麵介紹。

 

可以看到，Version儲存的主要是兩類資料：當前sstable檔案的資訊，以及下一次合併時的資訊。

 

所有的級別，也就是Version類，使用雙向連結串列串聯起來，儲存到VersionSet中，而VersionSet中有一個current指標，用於指向當前的Version。

 

 

當進行合併時，首先需要挑選出需要進行合併的檔案，這個操作的入口函式是VersionSet::PickCompaction，該函式的傳回值是一個Compaction結構體，該結構體內部儲存合併相關的資訊，Compaction結構體中最重要的成員是VersionEdit類成員，這個成員用於儲存合併過程中有刪減的sstable檔案：

• DeletedFileSet deleted_files_：合併後待刪除的sstable檔案。
• std::vector< std::pair

   > new_files_：合併後新增的sstable檔案。

 

可以認為：version N + version N edit = version N + 1，即：第N版本的sstable資訊，在經過該版本合併的VersionEdit之後，形成了Version N+1版本。

 

另外還有一個VersionSet::Builder，用於儲存合併中間過程的資料，其本質是將所有VersoinEdit內容儲存到VersionSet::Builder中，最後一次產生新版本的Version。

 

 

合併條件及原理

leveldb會不斷產生新的sstable檔案，這時候需要對這些檔案進行合併，否則磁碟會一直增大，查詢速度也會下降。

 

這部分講解合併觸發的條件以及進行合併的原理。

leveldb大致在以下兩種條件下會觸發合併操作：

• 需要新生成memtable的情況下，此時必然會把原來的memtable切換為immutable memtable，後者又需要及時落盤成為新的sstable檔案，將immutable memtable資料落盤為sstable檔案的流程稱為”minor compaction“，因為有新的sstable檔案產生，所以需要合併檔案減少sstable檔案的數量。
• 查詢資料時，某些sstable總是查詢不到資料，此時可能是因為資料太過分散了，也需要將檔案合併。

 

以上兩種情況，對應到leveldb程式碼中就是以下幾個地方：

• 呼叫DB::Open檔案開啟資料庫檔案時，由於之前可能已經存在了一些檔案，這時會做檢查，滿足條件的情況下會進行合併操作。
• 呼叫DB::Write函式寫入資料時，呼叫MakeRoomForWrite函式分配空間，此時如果需要新分配一個memtable，也會觸發合併操作。
• 呼叫DB::Get函式查詢資料時，某些檔案查詢的次數超過了閾值，此時也會進行合併操作。

 

另外還需要提一下合併的兩種型別：

• minor compaction：將記憶體的資料落地到磁碟上的遷移過程，對應於leveldb就是將immutable memtable資料落盤為sstable檔案的流程。
• major compaction：sstable之間的檔案進行合併的流程。

 

選擇進行合併的檔案

函式VersionSet::PickCompaction用於構建出一次合併對應的Compaction結構體。來看這個函式主要的流程。

 

在挑選哪些檔案需要合併時，依賴於兩個原則：

• 首先考慮每一層檔案的數量：這個數量的計數，對應到Version的compaction_score_中，在每次VersionSet::Finalize函式中，都會首先進行預計算這個值，那個級別的分數高，下一次就優先選擇該層次來做合併。對於不同的層次，計算的規則也不同：
  • level 0：0級檔案的數量除以kL0_CompactionTrigger來計算分數。
  • 非0級：該層次的所有檔案大小/MaxBytesForLevel(level)來計算分數。
• 如果上面的計算中，compaction_score_為0，那麼就需要具體針對一個檔案來進行合併。leveldb中，在FileMetaData結構體裡有一個成員allowed_seeks，表示在該檔案中查詢某個鍵值時最多允許的定位次數，當這個值為0時，意味這個檔案多次查詢都沒有查詢到資料，因此這個檔案就需要進行合併了。

 

檔案的allowed_seeks在VersionSet::Builder::Apply函式中進行計算：

 

 

如果是第一種情況，即compaction_score_ >= 1的情況來選擇合併檔案，還涉及到一個合併點的問題（compact point），即leveldb會儲存上一次進行合併的鍵值，這一次會從這個鍵值以後開始尋找需要進行合併的檔案。

 

而如果合併層次是0級，因為0級檔案中的鍵值有重疊的情況，因此還需要遍歷0級檔案中鍵值範圍與這次合併檔案由重疊的一起加入進來。

 

在這之後，呼叫VersionSet::SetupOtherInputs函式，用於獲取同級別以及更上一層也就是level + 1級別中滿足合併範圍條件的檔案，這就構成了待合併的檔案集合。

 

 

如上圖所示：

• 此時選擇進行合併的檔案，其鍵值是[1,2,4,5]。
• 由於該檔案在level 0級別，sstable檔案的鍵值有重疊，同時還在在其上面一層選擇同樣鍵值範圍有重疊的sstable檔案，選擇的結果就是綠色的sstable檔案，這些將做為這次合併進行歸併排序的檔案。

 

合併流程

以上呼叫VersionSet::PickCompaction函式選擇完畢了待合併的檔案及層次之後，就來到DBImpl::DoCompactionWork函式中進行實際的合併工作。

 

該函式的原理不算複雜，就是遍歷檔案集合進行合併：

 

 

合併操作對讀寫流程的影響

leveldb將使用者的讀寫操作，與合併工作放在不同的執行緒中處理。當使用者需要寫入資料進行分配空間時，會首先呼叫DBImpl::MakeRoomForWrite函式進行空間的分配，該函式有可能因為合併流程被阻塞，有以下幾種可能性：

 

參考資料

• 資料分析與處理之二（Leveldb 實現原理）：https://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html
• Leveldb之Iterator總結：http://kernelmaker.github.io/Leveldb_Iterator