歡迎光臨
每天分享高質量文章

經典開原始碼分析——Leveldb高效儲存實現

導讀: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記錄如下所示:

 

 

說明如下:

 

因為一個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

赞(0)

分享創造快樂