本文基于leveldb 1.9.0代碼。

整體架構(gòu)

 

如上圖，leveldb的數(shù)據(jù)存儲在內(nèi)存以及磁盤上，其中：

• memtable：存儲在內(nèi)存中的數(shù)據(jù)，使用skiplist實(shí)現(xiàn)。
• immutable memtable：與memtable一樣，只不過這個(gè)memtable不能再進(jìn)行修改，會將其中的數(shù)據(jù)落盤到level 0的sstable中。
• 多層sstable：leveldb使用多個(gè)層次來存儲sstable文件，這些文件分布在磁盤上，這些文件都是根據(jù)鍵值有序排列的，其中0級的sstable的鍵值可能會重疊，而level 1及以上的sstable文件不會重疊。

在上面這個(gè)存儲層次中，越靠上的數(shù)據(jù)越新，即同一個(gè)鍵值如果同時(shí)存在于memtable和immutable memtable中，則以memtable中的為準(zhǔn)。

另外，圖中還使用箭頭來表示了合并數(shù)據(jù)的走向，即：

 

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

Log文件

寫入數(shù)據(jù)的時(shí)候，最開始會寫入到log文件中，由于是順序?qū)懭胛募?，所以寫入速度很快，可以馬上返回。

來看Log文件的結(jié)構(gòu)：

• 一個(gè)Log文件由多個(gè)Block組成，每個(gè)Block大小為32KB。
• 一個(gè)Block內(nèi)部又有多個(gè)Record組成，Record分為四種類型：

Full：一個(gè)Record占滿了整個(gè)Block存儲空間。

First：一個(gè)Block的***個(gè)Record。

Last：一個(gè)Block的***一個(gè)Record。

Middle：其余的都是Middle類型的Record。

• Record的結(jié)構(gòu)如下：

32位長度的CRC Checksum：存儲這個(gè)Record的數(shù)據(jù)校驗(yàn)值，用于檢測Record合法性。

16位長度的Length：存儲數(shù)據(jù)部分長度。

8位長度的Type：存儲Record類型，就是上面說的四種類型。

Header部分

數(shù)據(jù)部分

 

memtable

memtable用于存儲在內(nèi)存中還未落盤到sstable中的數(shù)據(jù)，這部分使用跳表(skiplist)做為底層的數(shù)據(jù)結(jié)構(gòu)，這里先簡單描述一下跳表的工作原理。

如果數(shù)據(jù)存放在一個(gè)普通的有序鏈表中，那么查找數(shù)據(jù)的時(shí)間復(fù)雜度就是O(n)。跳表的設(shè)計(jì)思想在于：鏈表中的每個(gè)元素，都有多個(gè)層次，查找某一個(gè)元素時(shí)，遍歷該鏈表的時(shí)候，根據(jù)層次來跳過(skip)中間某些明顯不滿足需求的元素，以達(dá)到加快查找速度的目的，如下圖所示：

 

在以上這個(gè)跳表中，查找元素6的流程，大體如下：

• 構(gòu)建一個(gè)每個(gè)鏈表元素最多有5個(gè)元素的跳表。
• 由于6大于鏈表的***個(gè)元素1，因此如果存在必然在1之后的元素中，因此進(jìn)入元素1的指針數(shù)組中，從上往下查找元素4：

***層：指向的指針為Nil空指針，不滿足需求，繼續(xù)往下查找;

第二層：指向的指針保存的數(shù)據(jù)為4，小于待查找的元素4，因此如果元素6存在也必然在4之后，因此指針跳轉(zhuǎn)到元素4所在的位置，繼續(xù)從上往下開始查找。

• 到了元素4所在的指針數(shù)組，開始從上往下繼續(xù)查找：

***層：指向的指針保存的數(shù)據(jù)為6，查找完畢。

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

• 跳表是一種以犧牲更多的存儲空間換取查找速度，即“空間換時(shí)間”的數(shù)據(jù)結(jié)構(gòu)。
• 跳表的每一層也都是一個(gè)有序鏈表。
• 如果一個(gè)元素出現(xiàn)在第i層的鏈表中，那么也必然會在第i層以下的鏈表中出現(xiàn)。
• 鏈表的每個(gè)節(jié)點(diǎn)中，垂直方向的數(shù)組存儲的數(shù)據(jù)都是一樣的，水平方向的指針指向鏈表的下一個(gè)元素。
• ***層的鏈表包含所有元素，也就是說，在***層數(shù)據(jù)結(jié)構(gòu)退化為一個(gè)普通的有序鏈表。

sstable文件

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

首先來看sstable文件的整體結(jié)構(gòu)，如下圖：

 

sstable文件中分為以下幾個(gè)組成部分：

• data block：存儲數(shù)據(jù)的block，由于一個(gè)block大小固定，因此每個(gè)sstable文件中有多個(gè)data block。
• filter block以及metaindex block：這兩個(gè)block不一定存在于sstable，取決于Options中的filter_policy參數(shù)值，后面就不對這兩部分進(jìn)行講解。
• index block：存儲的是索引數(shù)據(jù)，即可以根據(jù)index block中的數(shù)據(jù)快速定位到數(shù)據(jù)處于哪個(gè)data block的哪個(gè)位置。
• footer：腳注數(shù)據(jù)，每個(gè)footer數(shù)據(jù)信息大小固定，存儲一個(gè)sstable文件的元信息(meta data)。

可以看到，上面這幾部分?jǐn)?shù)據(jù)，從文件的組織來看自上而下，先有了數(shù)據(jù)再有索引數(shù)據(jù)，***才是文件自身的元信息。原因在于：索引數(shù)據(jù)是針對數(shù)據(jù)的索引信息，在數(shù)據(jù)沒有寫完畢之前，索引信息還會發(fā)生改變，所以索引數(shù)據(jù)要等數(shù)據(jù)寫完;而元信息就是針對索引數(shù)據(jù)的索引，同樣要依賴于索引信息寫完畢才可以。

block

上面幾部分?jǐn)?shù)據(jù)中，除去footer之外，內(nèi)部都是以block的形式來組織數(shù)據(jù)，接著看block的結(jié)構(gòu)，如下圖：

 

從上面看出，實(shí)際上存儲數(shù)據(jù)的block大同小異：最開始的一部分存儲數(shù)據(jù)，然后存儲類型，***一部分存儲這個(gè)block的校驗(yàn)碼以做合法性校驗(yàn)。

以上只是對block大體結(jié)構(gòu)的分析，在數(shù)據(jù)部分，每一條數(shù)據(jù)記錄leveldb使用前綴壓縮(prefix-compressed)方式來存儲。這種算法的原理是：針對一組數(shù)據(jù)，取出一個(gè)公共的前綴，而在該組中的其它字符串只保存非公共的字符串做為key即可，由于sstable保存KV數(shù)據(jù)是嚴(yán)格按照key的順序來排序的，所以這樣能節(jié)省出保存key數(shù)據(jù)的空間來。

如下圖所示：一個(gè)block內(nèi)部劃分了多個(gè)記錄組(record group)，每個(gè)記錄組內(nèi)部又由多條記錄(record)組成。在同一個(gè)記錄組內(nèi)部，以本組的***條數(shù)據(jù)的鍵值做為公共前綴，后續(xù)的記錄數(shù)據(jù)鍵值部分只存放與公共前綴非共享部分的數(shù)據(jù)即可。

 

以記錄的三個(gè)數(shù)據(jù)

 

說明如下：

 

 

 

因?yàn)橐粋€(gè)block內(nèi)部有多個(gè)記錄組，因此還需要另外的數(shù)據(jù)來記錄不同記錄組的位置，這部分?jǐn)?shù)據(jù)被稱為“重啟點(diǎn)(restart point)”，重啟點(diǎn)首先會以數(shù)組的形式保存下來，直到該block數(shù)據(jù)需要落盤的情況下才會寫到block結(jié)尾處。

有了以上的準(zhǔn)備，就可以來具體看添加數(shù)據(jù)的代碼了，向一個(gè)block中添加數(shù)據(jù)的偽代碼如下。

 

有了前面的這些準(zhǔn)備，再在前面block格式的基礎(chǔ)上展開，得到更加詳細(xì)的格式如下：

 

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

• 數(shù)據(jù)部分

多個(gè)記錄組組成的記錄數(shù)據(jù)。

多個(gè)重啟點(diǎn)數(shù)據(jù)組成的重啟點(diǎn)數(shù)組數(shù)據(jù)，每個(gè)元素記錄對應(yīng)的記錄組在block中的偏移量，類型為fixed32類型。

• 壓縮類型，大小為1 Byte。
• CRC32校驗(yàn)數(shù)據(jù)，大小為4 Byte。

footer

footer做為存儲sstable文件原信息部分的數(shù)據(jù)，格式相對簡單，如下圖：

Iterator的設(shè)計(jì)

迭代器的設(shè)計(jì)是leveldb中的一大亮點(diǎn)，leveldb設(shè)計(jì)了一個(gè)虛擬基類Iterator，其中定義了諸如遍歷、查詢之類的接口，而該基類有多種實(shí)現(xiàn)。原因在于：leveldb中存在多種數(shù)據(jù)結(jié)構(gòu)和多種使用場景，如：

• 保存內(nèi)存中數(shù)據(jù)的memtable。
• 保存落盤數(shù)據(jù)的sstable，而就前面分析而言，一個(gè)sstable中還有不同的block，需要根據(jù)index block來定位數(shù)據(jù)處于哪個(gè)data block。
• 進(jìn)行合并的時(shí)候，每次最多合并兩個(gè)層次的文件，在這個(gè)過程中需要對待合并的文件集合進(jìn)行遍歷。前面分析的DBImpl::DoCompactionWork函數(shù)，就是通過iterator來遍歷待合并文件進(jìn)行合并操作的。

逐個(gè)來看不同的iterator實(shí)現(xiàn)以及其使用場景。

迭代器大體分為兩類：

• 底層迭代器：處于***層，直接訪問底層數(shù)據(jù)結(jié)構(gòu)，而不依賴于其他迭代器的迭代器。
• 組合迭代器：組合各種迭代器(包括底層和組合迭代器)完成工作的迭代器。

底層迭代器

底層迭代器有以下三種：

• MemTableIterator：用于實(shí)現(xiàn)對memtable的迭代遍歷，由于memtable由skiplist實(shí)現(xiàn)，因此內(nèi)部封裝了對skiplist的迭代訪問。
• Block::Iter：前面分析sstable的時(shí)候，講到一個(gè)sstable內(nèi)部其實(shí)有多個(gè)block組成，這個(gè)迭代器就是按照block的結(jié)構(gòu)進(jìn)行迭代訪問的迭代器。
• Version::LevelFileNumIterator：每個(gè)level都由多個(gè)sstable文件組成，說白了就是一個(gè)sstable類型的數(shù)組。除了level 0之外，其余l(xiāng)evel的sstable的鍵值之間沒有重疊關(guān)系，而LevelFileNumIterator就是用于迭代一組有序sstable文件的迭代器。

 

組合迭代器

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

TwoLevelIterator

顧名思義，TwoLevelIterator表示兩層迭代器，創(chuàng)建TwoLevelIterator的函數(shù)原型為：

 

參數(shù)說明如下：

• Iterator* index_iter：索引迭代器，可以理解為***層的迭代器。
• BlockFunction *block_function：這是一個(gè)函數(shù)指針，根據(jù)index_iter迭代器的返回結(jié)果來再創(chuàng)建一個(gè)迭代器，即針對查詢索引返回?cái)?shù)據(jù)的迭代器。其函數(shù)參數(shù)有三個(gè)，其中前面兩個(gè)由下面的arg以及options參數(shù)指定，而第三個(gè)參數(shù)slice就是index_iterator返回的索引數(shù)據(jù)。
• void* arg：傳入BlockFunction函數(shù)的***個(gè)參數(shù)。
• const ReadOptions& options：傳入BlockFunction函數(shù)的第二個(gè)參數(shù)。

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

 

TwoLevelIterator有如下兩類：

• Table::Iterator：實(shí)現(xiàn)對于單個(gè)sstable文件的迭代。由于一個(gè)sstable文件中有多個(gè)block，而又劃分為index block和data block，查詢數(shù)據(jù)時(shí)，先根據(jù)鍵值到index block中查詢到對應(yīng)的data block，再進(jìn)入data block中進(jìn)行查詢，這個(gè)查詢過程實(shí)際就是一個(gè)兩層的查找過程：先查索引數(shù)據(jù)，再查數(shù)據(jù)。因此Table::Iterator類型的TwoLevelIterator，組合了index block的Block::Iter，以及data block的Block::Iter。
• ConcatenatingIterator：組合了LevelFileNumIterator以及Table::Iterator，用于在某一層內(nèi)的sstable文件中查詢數(shù)據(jù)。因此它的***層迭代器就是前面的LevelFileNumIterator，用于根據(jù)一個(gè)鍵值在一組有序的sstable文件中定位到所在的文件，而第二層的迭代器是Table::Iterator，用于在***層迭代器LevelFileNumIterator中查詢到的sstable文件中查詢鍵值。另外，既然ConcatenatingIterator處理的是有序sstable文件，那么level 0的sstable文件就不會使用這種迭代器進(jìn)行訪問，因?yàn)閘evel 0文件之間有重疊鍵值。

 

MergingIterator

用于合并流程的迭代器。在合并過程中，需要操作memtable、immutable memtable、level 0 sstable以及非level 0的sstable，該迭代器將這些存儲數(shù)據(jù)結(jié)構(gòu)體的迭代器，統(tǒng)一進(jìn)行歸并排序：

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

由于以上每種類型的iterator，內(nèi)部遍歷數(shù)據(jù)都是有序的，所以MergingIterator內(nèi)部做的事情，就是將對這些iterator的遍歷結(jié)果進(jìn)行“歸并”。MergingIterator內(nèi)部有如下變量：

• const Comparator* comparator_：用于鍵值比較的函數(shù)operator。
• IteratorWrapper* children_：存儲傳入的iterator的數(shù)組。
• int n_：children_數(shù)組的大小。
• IteratorWrapper* current_：保存當(dāng)前查詢到的位置所在的iterator。
• Direction direction_：保存查找的方向，有向前和向后兩種查詢防線。

可以看到，current_以及direction_兩個(gè)成員是用于保存當(dāng)前查找狀態(tài)的成員。

構(gòu)建MergingIterator迭代器傳入的Comparator是InternalKeyComparator，其比較邏輯是：

• 首先比較鍵值是否相等，不相等則直接返回比較結(jié)果。
• 如果鍵值相等，那么從鍵值中decode出來sequence值，對比sequence值，對sequence值進(jìn)行降序比較。由于這個(gè)值是單調(diào)遞增的，因此越新的數(shù)據(jù)sequence值越大。換言之，在存儲層次中(依次為memtable->immutable memtable->level 0 sstable->level n sstable)越靠上面的數(shù)據(jù)，在鍵值相同的情況下越小。

Seek(target)函數(shù)的偽代碼：

 

而FindSmallest函數(shù)的實(shí)現(xiàn)，是遍歷children_找到最小的child保存到current_指針中。前面分析InternalKeyComparator提到過，相同鍵值的數(shù)據(jù)，根據(jù)sequence值進(jìn)行降序排列，即數(shù)據(jù)越新的數(shù)據(jù)其sequence值越大，在這個(gè)排序中查找的結(jié)果就越在上面。因此，F(xiàn)indSmallest函數(shù)如果在memtable、level 0中都找到了相同鍵值，將優(yōu)先選擇memtable中的數(shù)據(jù)。

MergingIterator迭代器的其它實(shí)現(xiàn)不再做解釋，簡單理解：針對一組iterator的查詢結(jié)果進(jìn)行歸并排序。對于同樣一個(gè)鍵值，只取位置在存儲位置上最靠上面的數(shù)據(jù)。

這么做的原因在于：一個(gè)鍵值的數(shù)據(jù)可能被寫入多次，而需要以***一次寫入的數(shù)據(jù)為準(zhǔn)，合并時(shí)將丟棄掉不在存儲最上面的數(shù)據(jù)。

以下面的例子來說明MergingIterator迭代器的合并結(jié)果。

 

在上圖的左半邊，是合并前的數(shù)據(jù)分布情況，依次為：

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

合并的結(jié)果如上圖的右邊所示：

• 鍵1：因?yàn)?**條鍵1的記錄是在memtable中的刪除記錄，所以鍵1將被刪除，即不會出現(xiàn)在合并結(jié)果中。
• 鍵2：最靠上面的關(guān)于鍵2的存儲記錄是<2,test>，這條記錄保存在合并結(jié)果中，而immutable memtable的記錄<2,test2>將被丟棄，因?yàn)檫@條記錄不是***的。
• 鍵3：使用了immutable memtable中的記錄<3,test>，丟棄了level 1 sstable中的<3,a>這條記錄。

核心流程

有了前面幾種核心數(shù)據(jù)結(jié)構(gòu)的了解，下面談leveldb中的幾個(gè)核心流程。

修改流程

修改數(shù)據(jù)，分為兩類：正常的寫入數(shù)據(jù)操作以及刪除數(shù)據(jù)操作。

先看正常的寫入數(shù)據(jù)操作：

• append一條記錄到log文件中，雖然這是一次寫磁盤操作，但是由于是在文件末尾做的順序?qū)懖僮?，所以效率并不低?/li>
• 向當(dāng)前的memtable中寫入一條數(shù)據(jù)。這個(gè)動作看似簡單，但是如果在來不及合并的時(shí)候，可能會出現(xiàn)阻塞，在后面合并操作中再展開解釋。

完成以上兩步之后，就可以認(rèn)為完成了更新數(shù)據(jù)的操作。實(shí)際上只有一次文件末尾的順序?qū)懖僮鳎约耙淮螌憙?nèi)存操作，如果不考慮會被合并操作阻塞的情況，實(shí)際上還是很快的。

再來看刪除數(shù)據(jù)操作。leveldb中，刪除一個(gè)數(shù)據(jù)，其實(shí)也是添加一條新的記錄，只不過記錄類型是刪除類型，代碼中通過枚舉變量定義了這兩種操作類型：

 

這樣看起來，leveldb刪除數(shù)據(jù)時(shí)，并不會真的去刪除一條數(shù)據(jù)，而是打上了一個(gè)標(biāo)記，那么問題就來了：如果寫入數(shù)據(jù)操作與刪除數(shù)據(jù)操作，只是類型不同，在查詢數(shù)據(jù)的時(shí)候又如何知道數(shù)據(jù)是否存在?看下面的讀數(shù)據(jù)流程。

讀流程

向leveldb中查詢一個(gè)數(shù)據(jù)，也是從上而下，先查內(nèi)存然后到磁盤上的sstable文件查詢，如下圖所示：

 

• 先在內(nèi)存中的memtable中查詢數(shù)據(jù)，查到則返回;
• 否則在磁盤中的sstable文件中查詢數(shù)據(jù)，從0級開始往下查詢，查到則返回;

這樣自上而下的原因就在于leveldb的設(shè)計(jì)：越是在上層的數(shù)據(jù)越新，距離當(dāng)前時(shí)間越短。

舉例而言，對于鍵值key而言，首先寫入kv對

那么，前面寫入的數(shù)據(jù)實(shí)際上已經(jīng)沒有用了，但是又占用了空間，這部分?jǐn)?shù)據(jù)就等待著后面的合并流程來合并數(shù)據(jù)***刪除掉。

合并流程

核心數(shù)據(jù)結(jié)構(gòu)

首先來看與合并相關(guān)的核心數(shù)據(jù)結(jié)構(gòu)。

每一次合并過程以及將memtable中的數(shù)據(jù)落盤到sstable的過程，都涉及到sstable文件的增刪，而這每一次操作，都對應(yīng)到一個(gè)版本。

在leveldb中，使用Version類來存儲一個(gè)版本的元信息，主要包括：

• std::vector
• files_[config::kNumLevels]：用于存儲所有級別sstable文件的FileMetaData數(shù)組，可以看到這個(gè)成員是一個(gè)數(shù)組，而數(shù)組的每個(gè)元素又是一個(gè)vector，這其中數(shù)組部分使用level級別來進(jìn)行索引，同級別的sstable信息存儲在vector中。
• FileMetaData* file_to_compact_和int file_to_compact_level_：下一次進(jìn)行合并時(shí)的文件和級別。

double compaction_score_和int compaction_level_：當(dāng)前***compact分?jǐn)?shù)和對應(yīng)的級別，在Finalize函數(shù)中進(jìn)行計(jì)算，具體計(jì)算的規(guī)則會在下面介紹。

可以看到，Version保存的主要是兩類數(shù)據(jù)：當(dāng)前sstable文件的信息，以及下一次合并時(shí)的信息。

所有的級別，也就是Version類，使用雙向鏈表串聯(lián)起來，保存到VersionSet中，而VersionSet中有一個(gè)current指針，用于指向當(dāng)前的Version。

 

當(dāng)進(jìn)行合并時(shí)，首先需要挑選出需要進(jìn)行合并的文件，這個(gè)操作的入口函數(shù)是VersionSet::PickCompaction，該函數(shù)的返回值是一個(gè)Compaction結(jié)構(gòu)體，該結(jié)構(gòu)體內(nèi)部保存合并相關(guān)的信息，Compaction結(jié)構(gòu)體中最重要的成員是VersionEdit類成員，這個(gè)成員用于保存合并過程中有刪減的sstable文件：

• DeletedFileSet deleted_files_：合并后待刪除的sstable文件。
• std::vector< std::pair

> new_files_：合并后新增的sstable文件。

可以認(rèn)為：version N + version N edit = version N + 1，即：第N版本的sstable信息，在經(jīng)過該版本合并的VersionEdit之后，形成了Version N+1版本。

另外還有一個(gè)VersionSet::Builder，用于保存合并中間過程的數(shù)據(jù)，其本質(zhì)是將所有VersoinEdit內(nèi)容存儲到VersionSet::Builder中，***一次產(chǎn)生新版本的Version。

 

合并條件及原理

leveldb會不斷產(chǎn)生新的sstable文件，這時(shí)候需要對這些文件進(jìn)行合并，否則磁盤會一直增大，查詢速度也會下降。

這部分講解合并觸發(fā)的條件以及進(jìn)行合并的原理。

leveldb大致在以下兩種條件下會觸發(fā)合并操作：

• 需要新生成memtable的情況下，此時(shí)必然會把原來的memtable切換為immutable memtable，后者又需要及時(shí)落盤成為新的sstable文件，將immutable memtable數(shù)據(jù)落盤為sstable文件的流程稱為”minor compaction“，因?yàn)橛行碌膕stable文件產(chǎn)生，所以需要合并文件減少sstable文件的數(shù)量。
• 查詢數(shù)據(jù)時(shí)，某些sstable總是查找不到數(shù)據(jù)，此時(shí)可能是因?yàn)閿?shù)據(jù)太過分散了，也需要將文件合并。

以上兩種情況，對應(yīng)到leveldb代碼中就是以下幾個(gè)地方：

• 調(diào)用DB::Open文件打開數(shù)據(jù)庫文件時(shí)，由于之前可能已經(jīng)存在了一些文件，這時(shí)會做檢查，滿足條件的情況下會進(jìn)行合并操作。
• 調(diào)用DB::Write函數(shù)寫入數(shù)據(jù)時(shí)，調(diào)用MakeRoomForWrite函數(shù)分配空間，此時(shí)如果需要新分配一個(gè)memtable，也會觸發(fā)合并操作。
• 調(diào)用DB::Get函數(shù)查詢數(shù)據(jù)時(shí)，某些文件查詢的次數(shù)超過了閾值，此時(shí)也會進(jìn)行合并操作。

另外還需要提一下合并的兩種類型：

• minor compaction：將內(nèi)存的數(shù)據(jù)落地到磁盤上的遷移過程，對應(yīng)于leveldb就是將immutable memtable數(shù)據(jù)落盤為sstable文件的流程。
• major compaction：sstable之間的文件進(jìn)行合并的流程。

選擇進(jìn)行合并的文件

函數(shù)VersionSet::PickCompaction用于構(gòu)建出一次合并對應(yīng)的Compaction結(jié)構(gòu)體。來看這個(gè)函數(shù)主要的流程。

在挑選哪些文件需要合并時(shí)，依賴于兩個(gè)原則：

• 首先考慮每一層文件的數(shù)量：這個(gè)數(shù)量的計(jì)數(shù)，對應(yīng)到Version的compaction_score_中，在每次VersionSet::Finalize函數(shù)中，都會首先進(jìn)行預(yù)計(jì)算這個(gè)值，那個(gè)級別的分?jǐn)?shù)高，下一次就優(yōu)先選擇該層次來做合并。對于不同的層次，計(jì)算的規(guī)則也不同：

level 0：0級文件的數(shù)量除以kL0_CompactionTrigger來計(jì)算分?jǐn)?shù)。

非0級：該層次的所有文件大小/MaxBytesForLevel(level)來計(jì)算分?jǐn)?shù)。

• 如果上面的計(jì)算中，compaction_score_為0，那么就需要具體針對一個(gè)文件來進(jìn)行合并。leveldb中，在FileMetaData結(jié)構(gòu)體里有一個(gè)成員allowed_seeks，表示在該文件中查詢某個(gè)鍵值時(shí)最多允許的定位次數(shù)，當(dāng)這個(gè)值為0時(shí)，意味這個(gè)文件多次查詢都沒有查詢到數(shù)據(jù)，因此這個(gè)文件就需要進(jìn)行合并了。

文件的allowed_seeks在VersionSet::Builder::Apply函數(shù)中進(jìn)行計(jì)算：

 

如果是***種情況，即compaction_score_ >= 1的情況來選擇合并文件，還涉及到一個(gè)合并點(diǎn)的問題(compact point)，即leveldb會保存上一次進(jìn)行合并的鍵值，這一次會從這個(gè)鍵值以后開始尋找需要進(jìn)行合并的文件。

而如果合并層次是0級，因?yàn)?級文件中的鍵值有重疊的情況，因此還需要遍歷0級文件中鍵值范圍與這次合并文件由重疊的一起加入進(jìn)來。

在這之后，調(diào)用VersionSet::SetupOtherInputs函數(shù)，用于獲取同級別以及更上一層也就是level + 1級別中滿足合并范圍條件的文件，這就構(gòu)成了待合并的文件集合。

 

如上圖所示：

• 此時(shí)選擇進(jìn)行合并的文件，其鍵值是[1,2,4,5]。
• 由于該文件在level 0級別，sstable文件的鍵值有重疊，同時(shí)還在在其上面一層選擇同樣鍵值范圍有重疊的sstable文件，選擇的結(jié)果就是綠色的sstable文件，這些將做為這次合并進(jìn)行歸并排序的文件。

合并流程

以上調(diào)用VersionSet::PickCompaction函數(shù)選擇完畢了待合并的文件及層次之后，就來到DBImpl::DoCompactionWork函數(shù)中進(jìn)行實(shí)際的合并工作。

該函數(shù)的原理不算復(fù)雜，就是遍歷文件集合進(jìn)行合并：

 

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

leveldb將用戶的讀寫操作，與合并工作放在不同的線程中處理。當(dāng)用戶需要寫入數(shù)據(jù)進(jìn)行分配空間時(shí)，會首先調(diào)用DBImpl::MakeRoomForWrite函數(shù)進(jìn)行空間的分配，該函數(shù)有可能因?yàn)楹喜⒘鞒瘫蛔枞?，有以下幾種可能性：

 

參考資料

數(shù)據(jù)分析與處理之二(Leveldb 實(shí)現(xiàn)原理)：https://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html

Leveldb之Iterator總結(jié)：http://kernelmaker.github.io/Leveldb_Iterator

本文轉(zhuǎn)載自微信公眾號「高可用架構(gòu)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系高可用架構(gòu)公眾號。