摘要

閱讀這篇文章，希望你首先已經(jīng)對(duì)Leveldb有了一定的了解，并預(yù)先知曉下列概念：

• LSM技術(shù)
• 跳表
• WAL技術(shù)
• Log Compaction

本文不是一篇專注于源代碼解析的文章，也不是一篇Leveldb的介紹文。我們更希望探討的是對(duì)于一般的單機(jī)數(shù)據(jù)存儲(chǔ)引擎存在哪些問題，Leveldb作為一個(gè)經(jīng)典實(shí)現(xiàn)，是采用什么策略并如何解決這些問題的。
Leveldb的解決方案是出于什么考慮，如何高效實(shí)現(xiàn)的，做出了哪些權(quán)衡以及如何組織代碼和工程。你可以先從以下幾篇文章對(duì)Leveldb有一個(gè)基本了解。

Leveldb的實(shí)現(xiàn)原理

LevelDB之LSM-Tree

LevelDB設(shè)計(jì)與實(shí)現(xiàn)

Leveldb的基本架構(gòu)

數(shù)據(jù)模型和需求

首先提出幾個(gè)問題：

• Leveldb在用戶視圖中的基本單元是什么？
• Leveldb一條記錄在內(nèi)存中的形式是什么，記錄以怎樣的方式被組織？
• Leveldb的記錄在文件中的存儲(chǔ)格式是什么，多條記錄在單文件中是如何被管理的，多文件又是如何被管理的？
• Leveldb向用戶做出了怎樣的保證，在什么樣的場(chǎng)景下提供了優(yōu)化？

首先，Leveldb所處理的每條記錄都是一條鍵值對(duì)，由于它基于sequence number提供快照讀，準(zhǔn)確來說應(yīng)該是鍵，序列號(hào)，值三元組，由于用戶一般關(guān)心最新的數(shù)據(jù)，可以簡(jiǎn)化為鍵值對(duì)。

Leveldb對(duì)持久化的保證是基于操作日志的，一條寫操作只有落盤到操作日志中之后（暫時(shí)先這么理解，實(shí)際上這里有所出入，后面在優(yōu)化部分會(huì)講到）才會(huì)在內(nèi)存中生效，才能被讀取到。這就保證了對(duì)于已經(jīng)能見到的操作，必定可以從操作日志中恢復(fù)。
它對(duì)一致性的保障可以認(rèn)為是順序一致性（這里的一致性不是數(shù)據(jù)庫理論的一致性，不強(qiáng)調(diào)從安全狀態(tài)到另一個(gè)安全狀態(tài)，而是指從各個(gè)視圖看事件發(fā)生的順序是一致的，由于使用了write batch 競(jìng)爭(zhēng)鎖，實(shí)際上寫入是串行化的，但同時(shí)并發(fā)的寫操作的順序取決于線程搶占鎖的順序）。
在這里我們可以稍微脫離leveldb的實(shí)現(xiàn)討論一下一致性，能不能實(shí)現(xiàn)線性一致性呢？如果我們不支持追加操作的情形下，寫是冪等的，如果確保版本號(hào)是按照操作開始時(shí)間嚴(yán)格遞增分配的，即使并發(fā)讀寫也是可以的，這樣做還有一個(gè)問題，就是如何支持快照讀，那就必須保留每一個(gè)寫記錄，但它們是亂序的，進(jìn)行查找將是困難的，我們可以通過設(shè)置同步點(diǎn)，兩個(gè)同步點(diǎn)之間的是寫緩沖，快照讀只有在寫緩沖中需要遍歷查找，在寫緩沖被刷入之前重排序記錄，刷入的時(shí)機(jī)是任意小于當(dāng)前同步點(diǎn)版本號(hào)的寫操作執(zhí)行完畢。上述所描述的只可能適合于對(duì)熱點(diǎn)key的大量并發(fā)寫。上面所討論的接近編程語言的內(nèi)存模型，可以參考JMM內(nèi)存模型或者C++內(nèi)存模型。

Leveldb對(duì)寫操作的要求是持久化到操作日志中，其所應(yīng)對(duì)的數(shù)據(jù)量也超出了內(nèi)存范圍，或者說其存儲(chǔ)內(nèi)容的存儲(chǔ)主體還是在磁盤上，只不過基于最近寫的數(shù)據(jù)往往會(huì)被大量訪問的假設(shè)在內(nèi)存中存儲(chǔ)了較新的數(shù)據(jù)。leveldb的核心做法就是保存了多個(gè)版本的數(shù)據(jù)以讓寫入操作不需要在磁盤中查找鍵的位置，將隨機(jī)寫改為順序?qū)?#xff0c;將這一部分代價(jià)某種程度上轉(zhuǎn)嫁給讀時(shí)在0層SSTable上的查找。那么它的讀性能受到影響了嗎？個(gè)人認(rèn)為它的讀性能稍顯不足主要是受制于LSM的檢索方式而非由于多版本共存的問題，當(dāng)然寫的便利也是基于這樣的組織方式。

上面這幾段主要是個(gè)人的一些想法，可能有些混亂，剩余的幾個(gè)問題將在下面的部分再詳細(xì)解答。

工程上的層次結(jié)構(gòu)

leveldb的實(shí)現(xiàn)大致上可以分成以下幾層結(jié)構(gòu)：

• 向用戶提供的DB類接口及其實(shí)現(xiàn)，主要是DB、DbImpl、iter等
• 中間概念層的memtable、table、version以及其輔助類，比如對(duì)應(yīng)的iter、builder、VersionEdit等
• 更底層的偏向?qū)嶋H的讀寫輔助類，比如block、BlockBuilder、WritableFile及其實(shí)現(xiàn)等
• 最后是它定義的一些輔助類和實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)比如它用來表示數(shù)據(jù)的最小單元Slice、操作狀態(tài)類Status、memtable中用到的SkipList等

可能的性能瓶頸

首先讓我們考慮設(shè)計(jì)一款類似于Leveldb的存儲(chǔ)產(chǎn)品，那么面臨的主要問題主要是以下幾項(xiàng)：

• 寫入磁盤時(shí)的延遲
• 并發(fā)寫加鎖造成的競(jìng)爭(zhēng)
• 讀操作時(shí)如何通過索引降低查找延遲
• 如何更好地利用cache優(yōu)化查詢效率，增加命中
• 快速地從快照或者日志中恢復(fù)
• 后臺(tái)工作如何保持服務(wù)可用

Leveldb的內(nèi)存管理

什么應(yīng)該在內(nèi)存中

在內(nèi)存中存放的數(shù)據(jù)主要包含當(dāng)前數(shù)據(jù)庫的元信息、memtable、ImmutableMemtable，前者顯然是必要的，后兩者存放的都是最新更新的數(shù)據(jù)。那么為什么需要有ImmutableMemtable呢。這是為了在持久化到磁盤上的同時(shí)保持對(duì)外服務(wù)可用，如果沒有這樣一個(gè)機(jī)制，那么我們要么需要持久化兩次，并在第一次持久化的中途記錄增量日志，第二次應(yīng)用上去，這是CMS垃圾回收器的做法，但是顯然十分復(fù)雜；還有一種選擇是我們預(yù)留一定的空間，直接將要持久化的memtable拷貝一份，這樣做顯然會(huì)浪費(fèi)大量可用內(nèi)存，對(duì)于一個(gè)數(shù)據(jù)庫來說，這是災(zāi)難性的。

那么元信息具體應(yīng)該包含哪些信息呢？

• 當(dāng)前的操作日志句柄
• 版本管理器、當(dāng)前的版本信息（對(duì)應(yīng)compaction）和對(duì)應(yīng)的持久化文件標(biāo)示
• 當(dāng)前的全部db配置信息比如comparator及其對(duì)應(yīng)的memtable指針
• 當(dāng)前的狀態(tài)信息以決定是否需要持久化memtable和合并sstable
• sstable文件集合的信息

上面列出了一些比較重要的元信息，可能還有遺漏

memtable詳解

memtable的結(jié)構(gòu)

memtable的鍵包含三個(gè)部分：

• Slice user ley
• sequence number
• value type

鍵的比較器首先按照遞增順序比較user key，然后安裝遞減順序比較sequence number，這兩個(gè)足以唯一確定一條記錄了。把user key放到前面的原因是，這樣對(duì)同一個(gè)user key的操作就可以按照sequence number順序連續(xù)存放了，不同的user key是互不相干的，因此把它們的操作放在一起也沒有什么意義。用戶所傳入的是LookupKey，它也是由User Key和Sequence Number組合而成的，其格式為：

| Size (int32變長)| User key (string) | sequence number (7 bytes) | value type (1 byte) |

這里的Size是user key長度+8，也就是整個(gè)字符串長度了。value type是kValueTypeForSeek，它等于kTypeValue。由于LookupKey的size是變長存儲(chǔ)的，因此它使用kstart_記錄了user key string的起始地址，否則將不能正確的獲取size和user key。

memtable本身存儲(chǔ)同一鍵的多個(gè)版本的數(shù)據(jù)，這一點(diǎn)從剛剛指出的鍵的格式也可以看出。這里為什么不直接在寫的時(shí)候直接將原有值替換并使用用戶鍵作為查找鍵呢？畢竟在memtable中add和update都需要先進(jìn)行查找。個(gè)人認(rèn)為除了需要支持快照讀也沒有別的解釋了，雖然這樣做會(huì)使得較老的記錄沒有被compact而較新的記錄已經(jīng)compact了的奇怪現(xiàn)象發(fā)生，但并不影響數(shù)據(jù)庫的讀寫，在性能上也沒有損害。那么快照讀為何是必要的呢？這個(gè)問題我目前也沒有很好的回答，讀者可以自行思考。

memtable的追加

memtable的追加操作主要是將鍵值對(duì)進(jìn)行編碼操作并最后委托給跳表處理，代碼很簡(jiǎn)單，就放上來吧。

// KV entry字符串有下面4部分連接而成 // key_size : varint32 of internal_key.size() // key bytes : char[internal_key.size()] // value_size : varint32 of value.size() // value bytes : char[value.size()] size_t key_size = key.size(); size_t val_size = value.size(); size_t internal_key_size = key_size + 8; const size_t encoded_len = VarintLength(internal_key_size) + internal_key_size + VarintLength(val_size) + val_size; char* buf = arena_.Allocate(encoded_len); char* p = EncodeVarint32(buf, internal_key_size); memcpy(p, key.data(), key_size); p += key_size; EncodeFixed64(p, (s << 8) | type); p += 8; p = EncodeVarint32(p, val_size); memcpy(p, value.data(), val_size); assert((p + val_size) - buf == encoded_len); table_.Insert(buf);

有關(guān)跳表可以參考下列文章：

Skip List（跳躍表）原理詳解與實(shí)現(xiàn)

memtable的查找

根據(jù)傳入的LookupKey得到在memtable中存儲(chǔ)的key，然后調(diào)用Skip list::Iterator的Seek函數(shù)查找。Seek直接調(diào)用Skip list的FindGreaterOrEqual(key)接口，返回大于等于key的Iterator。然后取出user key判斷時(shí)候和傳入的user key相同，如果相同則取出value，如果記錄的Value Type為kTypeDeletion，返回Status::NotFound(Slice())。本質(zhì)上依然委托跳表處理。

內(nèi)存分配和釋放

Leveldb自己實(shí)現(xiàn)了基于引用計(jì)數(shù)的垃圾回收和一個(gè)簡(jiǎn)單的內(nèi)存池Arena，其實(shí)現(xiàn)預(yù)先分配大內(nèi)存塊，劃分為不同對(duì)齊的內(nèi)存空間，其機(jī)制乏善可陳，在這里就不多言，放張圖吧。

Arena主要提供了兩個(gè)申請(qǐng)函數(shù)：其中一個(gè)直接分配內(nèi)存，另一個(gè)可以申請(qǐng)對(duì)齊的內(nèi)存空間。Arena沒有直接調(diào)用delete/free函數(shù)，而是由Arena的析構(gòu)函數(shù)統(tǒng)一釋放所有的內(nèi)存。應(yīng)該說這是和leveldb特定的應(yīng)用場(chǎng)景相關(guān)的，比如一個(gè)memtable使用一個(gè)Arena，當(dāng)memtable被釋放時(shí)，由Arena統(tǒng)一釋放其內(nèi)存。

另外就是對(duì)于許多類比如memtable、table、cahe等leveldb都加上了引用計(jì)數(shù)，其實(shí)現(xiàn)也非常簡(jiǎn)單，就是在對(duì)象中加入數(shù)據(jù)域refs，這也非常好理解。比如在迭代的過程中，已經(jīng)進(jìn)入下一個(gè)block中了，上一個(gè)block理應(yīng)可以釋放了，但它有可能被傳遞出去提供某些查詢服務(wù)使用，在其計(jì)數(shù)不為0時(shí)不允許釋放，同理對(duì)于immutable_memtable，當(dāng)它持久化完畢時(shí)，如果還在為用戶提供讀服務(wù)，也不能釋放。不得不說Leveldb的工程層次很清楚，幾乎沒有循環(huán)引用的問題。

Leveldb的磁盤存儲(chǔ)

需要存儲(chǔ)的內(nèi)容

對(duì)于一個(gè)db，大致需要存儲(chǔ)下列文件

• db的操作日志
• 存儲(chǔ)實(shí)際數(shù)據(jù)的SSTable文件
• DB的元信息Manifest文件
• 記錄當(dāng)前正在使用的Manifest文件，它的內(nèi)容就是當(dāng)前的manifest文件名
• 系統(tǒng)的運(yùn)行日志，記錄系統(tǒng)的運(yùn)行信息或者錯(cuò)誤日志。
• 臨時(shí)數(shù)據(jù)庫文件，repair時(shí)臨時(shí)生成的。

SSTable詳解

SSTable文件組織

單個(gè)SSTable文件的組織如下圖所示：

大致分為幾個(gè)部分：

• 數(shù)據(jù)塊 Data Block，直接存儲(chǔ)有序鍵值對(duì)
• Meta Block，存儲(chǔ)Filter相關(guān)信息
• Meta Index Block，對(duì)Meta Block的索引，它只有一條記錄，key是meta index的名字（也就是Filter的名字），value為指向meta index的位置。
• Index Block，是對(duì)Data Block的索引，對(duì)于其中的每個(gè)記錄，其key >=Data Block最后一條記錄的key，同時(shí)<其后Data Block的第一條記錄的key；value是指向data index的位置信息
• Footer，指向各個(gè)分區(qū)的位置和大小，示意圖如下：

所有類型的block格式是一致的，主要包含下面幾部分：

其中type指的是采用哪種壓縮方式，當(dāng)前主要是snappy壓縮，接下來主要講講block data部分的組織：

snappy是前綴壓縮的，為了兼顧查找效率，在構(gòu)建Block時(shí)，每隔幾個(gè)key就直接存儲(chǔ)一個(gè)重啟點(diǎn)key。Block在結(jié)尾記錄所有重啟點(diǎn)的偏移，可以二分查找指定的key。Value直接存儲(chǔ)在key的后面，無壓縮。

普通的kv對(duì)存儲(chǔ)結(jié)構(gòu)如下：

• 共享前綴長度
• 非共享鍵部分的長度
• 前綴之后的字符串
• 值

總體的Block Data如下：

總體來看Block可分為k/v存儲(chǔ)區(qū)和后面的重啟點(diǎn)存儲(chǔ)區(qū)兩部分，后面主要是重啟點(diǎn)的位置和個(gè)數(shù)。Block的大小是根據(jù)參數(shù)固定的，當(dāng)不能存放下一條記錄時(shí)多余的空間將會(huì)閑置。

SSTable邏輯表達(dá)

SSTable在代碼上主要有負(fù)責(zé)讀相關(guān)的Table、Block和對(duì)應(yīng)的Iterator實(shí)現(xiàn)；在寫上主要是BlockBuilder和TableBuilder。可以看出來這也是個(gè)典型的二層委托結(jié)構(gòu)了，上面的層次將操作委托給下面層次的類執(zhí)行，自己管控住progress的信息，控制當(dāng)前的下層實(shí)體。這里我們主要關(guān)心Table和Block中應(yīng)該存放哪些信息以支持它們的操作。

先講講簡(jiǎn)單的Block，毫無疑問除了數(shù)據(jù)（char*+size）本身以外就是重啟點(diǎn)了，重啟點(diǎn)可是查詢的利器啊，直接的思路是解析重啟點(diǎn)部分成一個(gè)vector等，實(shí)際上Leveldb不是這樣做的，只是保留了一個(gè)指向重啟點(diǎn)部分的指針，至于為什么我們?cè)诓樵円还?jié)里再詳談。

再說說Table，

SSTable的寫入

首先，我們考慮在內(nèi)存中構(gòu)建一個(gè)連續(xù)的內(nèi)存區(qū)域代表一個(gè)block的內(nèi)容，它又可以分為兩部分：1. 數(shù)據(jù)的寫入 2. 數(shù)據(jù)寫入完畢后附加信息的添加。 先考慮追加一條記錄，我們需要知道哪些東西？

• 當(dāng)前block提供給數(shù)據(jù)的剩余空間以確定是否需要換block
• 當(dāng)前的重啟點(diǎn)以確定共享前綴
• 當(dāng)前重啟點(diǎn)已有的key數(shù)量以確定是否將本次寫入作為新的重啟點(diǎn)
• 確保key的有序性，所以必須知道上次添加的key

在確定這些需要的信息后，追加的過程就是查找和維護(hù)這些信息以及單純的memcpy了。

第二步，讓我們考慮在數(shù)據(jù)寫入完畢之后需要為block添加其他信息的過程：

• 我們需要記錄所有的重啟點(diǎn)和重啟點(diǎn)位置，我們不得不在追加的時(shí)候來維護(hù)它們，看來得回去改上面的代碼了
• 我們得從配置元數(shù)據(jù)中得到壓縮類型
• 最后我們得記錄CRC

現(xiàn)在，我們可以把這么一段char[]的數(shù)據(jù)轉(zhuǎn)換成Slice表達(dá)的block了。接下來，讓我們考慮如何批量的把數(shù)據(jù)寫入單個(gè)SSTable文件中。這同樣分為三個(gè)步驟：1. 追加數(shù)據(jù) 2. 附加信息 3. Flush到文件。 我們依次考慮。

追加數(shù)據(jù)需要做哪些：

• 知道當(dāng)前block及當(dāng)前block能否再添加一條數(shù)據(jù)
• 維護(hù)有序性，需要上一次的key和新加key比較
• 如果生成新的block，為了維護(hù)索引，需要為將被替換的block生成索引記錄，所以必須維護(hù)一個(gè)index Block
• 維護(hù)過濾器信息（這一部分將在布隆過濾再詳細(xì)解釋，可以暫時(shí)忽略）
• 為了決定是否需要刷到文件中去，需要知道已寫的block數(shù)

實(shí)際上向文件寫入是以Block為單位的，當(dāng)我們完成一個(gè)Block時(shí)，在將它寫入文件時(shí)需要做什么呢？

• 檢查工作，確定block確實(shí)需要寫入
• 壓縮工作
• 通知工作，告知index Block和Filter Block的維護(hù)方
• 重置工作，將當(dāng)前block重置，準(zhǔn)備下一次追加

最后，當(dāng)數(shù)據(jù)全部添加完畢，該SSTable文件從此將不可變更，這一步需要執(zhí)行的是：

• 寫入最后一塊data block
• 寫入Meta Block
• 根據(jù)上文寫入時(shí)留存的位置信息構(gòu)建Meta Index Block
• 寫入Meta Index Block
• 將最后的data block位置信息寫入Index Block中，并將Index Block寫入文件
• 寫入Footer信息

SSTable的遍歷

SSTable的遍歷主要委托給一個(gè)two level iterator處理，我們只需要弄清楚它的Next操作就能明白其工作原理。所謂的two level，指的是索引一層，數(shù)據(jù)一層。在拿到一個(gè)SSTable文件的時(shí)候，我們先解析它的Index block部分，然后根據(jù)當(dāng)前的index初始化data block層的iterator。接下來我們主要關(guān)注Next的過程。

分為兩種情形：

當(dāng)前記錄不是當(dāng)前Data Block的最后一條，只需要data iter向前進(jìn)一步即可

當(dāng)前記錄是最后一條，這時(shí)就要先前進(jìn)一步index iter，得到data block的位置信息

讀取data block，此處先暫時(shí)省略table cache的優(yōu)化，簡(jiǎn)單起見都是從文件中讀

創(chuàng)建新的data iter

當(dāng)然，二級(jí)迭代器還做了許多的其他工作，比如允許你傳入block function，但這和我們討論的主線無關(guān)，這里就不過多陳述了。

SSTable的查詢

SSTable的查詢也委托給iter處理，其主要過程就是對(duì)key的定位，也是主要分為三部分：

• 定位到哪個(gè)block
• 遷移到該block上
• 定位到block中的哪一條

無論是index block還是data block，它們的iter實(shí)現(xiàn)是一致的，其查找都遵循以下過程：

• 通過重啟點(diǎn)進(jìn)行二分查找
• 跳到最大的不比目標(biāo)大的重啟點(diǎn)，遍歷查找，一直到一個(gè)不比目標(biāo)小的key出現(xiàn)

這里最絕妙的是兩點(diǎn)

• index block的設(shè)計(jì)和二級(jí)迭代器，一方面通過這種手段進(jìn)行快速定位，另一方面將遍歷和查找統(tǒng)一到一個(gè)框架下，不可謂不妙
• 重啟點(diǎn)的設(shè)計(jì)，避免解析數(shù)據(jù)內(nèi)容快速使用二分查找定位key的大致區(qū)域

我們都知道磁盤的讀寫是十分耗時(shí)的，索引的手段大量減少了磁盤讀的必要。當(dāng)然，還有許多加速的手段比如過濾器和緩存，我們將在最后一節(jié)詳細(xì)解釋。

元信息存儲(chǔ)與管理

這里我們主要關(guān)注db的元信息，也即Manifest文件。

元信息文件的格式

首先，Manifest中應(yīng)該包含哪些信息呢？

首先是使用的coparator名、log編號(hào)、前一個(gè)log編號(hào)、下一個(gè)文件編號(hào)、上一個(gè)序列號(hào)。這些都是日志、sstable文件使用到的重要信息，這些字段不一定必然存在。其次是compact點(diǎn)，可能有多個(gè)，寫入格式為{kCompactPointer, level, internal key}。其后是刪除文件，可能有多個(gè)，格式為{kDeletedFile, level, file number}。最后是新文件，可能有多個(gè)，格式為{kNewFile, level, file number, file size, min key, max key}。對(duì)于版本間變動(dòng)它是新加的文件集合，對(duì)于MANIFEST快照是該版本包含的所有sstable文件集合。下面給出一張Manifest示意結(jié)構(gòu)圖。

Leveldb在寫入每個(gè)字段之前，都會(huì)先寫入一個(gè)varint型數(shù)字來標(biāo)記后面的字段類型。在讀取時(shí)，先讀取此字段，根據(jù)類型解析后面的信息。

元信息的邏輯表達(dá)

在代碼中元信息這一部分主要是Version類和VersionSet類。LeveDB用 Version 表示一個(gè)版本的元信息，Version中主要包括一個(gè)FileMetaData指針的二維數(shù)組，分層記錄了所有的SST文件信息。 FileMetaData 數(shù)據(jù)結(jié)構(gòu)用來維護(hù)一個(gè)文件的元信息，包括文件大小，文件編號(hào)，最大最小值，引用計(jì)數(shù)等，其中引用計(jì)數(shù)記錄了被不同的Version引用的個(gè)數(shù)，保證被引用中的文件不會(huì)被刪除。除此之外，Version中還記錄了觸發(fā)Compaction相關(guān)的狀態(tài)信息，這些信息會(huì)在讀寫請(qǐng)求或Compaction過程中被更新。在CompactMemTable和BackgroundCompaction過程中會(huì)導(dǎo)致新文件的產(chǎn)生和舊文件的刪除。每當(dāng)這個(gè)時(shí)候都會(huì)有一個(gè)新的對(duì)應(yīng)的Version生成，并插入VersionSet鏈表頭部。

VersionSet是一個(gè)Version構(gòu)成的雙向鏈表，這些Version按時(shí)間順序先后產(chǎn)生，記錄了當(dāng)時(shí)的元信息，鏈表頭指向當(dāng)前最新的Version，同時(shí)維護(hù)了每個(gè)Version的引用計(jì)數(shù)，被引用中的Version不會(huì)被刪除，其對(duì)應(yīng)的SST文件也因此得以保留，通過這種方式，使得LevelDB可以在一個(gè)穩(wěn)定的快照視圖上訪問文件。VersionSet中除了Version的雙向鏈表外還會(huì)記錄一些如LogNumber，Sequence，下一個(gè)SST文件編號(hào)的狀態(tài)信息。

元信息的修改

這里我們主要探討二個(gè)問題：

• 如何描述一次修改，或者說一次修改應(yīng)該包括什么，怎樣才算是一次合法的修改？
• 如何應(yīng)用一次修改，使得系統(tǒng)切換到新的配置上

描述一次變更的是VersionEdit類，而最為直接的持久化和apply它的辦法就是

構(gòu)造VersionEdit并寫入Manifest文件

合并當(dāng)前Version和versionEdit得到新version加入versionSet

將當(dāng)前version指向新生成的version

首先，我們看看VersionEdit包含哪些內(nèi)容：

std::string comparator_;uint64_t log_number_;uint64_t prev_log_number_;uint64_t next_file_number_;SequenceNumber last_sequence_;bool has_comparator_;bool has_log_number_;bool has_prev_log_number_;bool has_next_file_number_;bool has_last_sequence_;std::vector< std::pair<int, InternalKey> > compact_pointers_;DeletedFileSet deleted_files_;std::vector< std::pair<int, FileMetaData> > new_files_;

對(duì)比上文Manifest的結(jié)構(gòu)，我們不難發(fā)現(xiàn)：Manifest文件記錄的是一組VersionEdit值，在Manifest中的一次增量內(nèi)容稱作一個(gè)Block。

Manifest Block := N * VersionEdit

可以看出恢復(fù)元信息的過程也變成了依次應(yīng)用VersionEdit的過程，這個(gè)過程中有大量的中間Version產(chǎn)生，但這些并不是我們所需要的。LevelDB引入VersionSet::Builder來避免這種中間變量，方法是先將所有的VersoinEdit內(nèi)容整理到VersionBuilder中，然后一次應(yīng)用產(chǎn)生最終的Version，這種實(shí)現(xiàn)上的優(yōu)化如下圖所示：

元信息的持久化

Compaction過程會(huì)造成文件的增加和刪除，這就需要生成新的Version，上面提到的Compaction對(duì)象包含本次Compaction所對(duì)應(yīng)的VersionEdit，Compaction結(jié)束后這個(gè)VersionEdit會(huì)被用來構(gòu)造新的VersionSet中的Version。同時(shí)為了數(shù)據(jù)安全，這個(gè)VersionEdit會(huì)被Append寫入到Manifest中。在庫重啟時(shí)，會(huì)首先嘗試從Manifest中恢復(fù)出當(dāng)前的元信息狀態(tài)，過程如下：

• 依次讀取Manifest文件中的每一個(gè)Block， 將從文件中讀出的Record反序列化為VersionEdit；
• 將每一個(gè)的VersionEdit Apply到VersionSet::Builder中，之后從VersionSet::Builder的信息中生成Version；
• 計(jì)算compaction_level_、compaction_score_；
• 將新生成的Version掛到VersionSet中，并初始化VersionSet的manifest_file_number_， next_file_number_，last_sequence_，log_number_，prev_log_number_ 信息；

操作日志存儲(chǔ)與管理

數(shù)據(jù)寫入Memtable之前，會(huì)首先順序?qū)懭隠og文件，以避免數(shù)據(jù)丟失。LevelDB實(shí)例啟動(dòng)時(shí)會(huì)從Log文件中恢復(fù)Memtable內(nèi)容。所以我們對(duì)Log的需求是：

• 磁盤存儲(chǔ)
• 大量的Append操作
• 沒有刪除單條數(shù)據(jù)的操作
• 遍歷的讀操作

LevelDB首先將每條寫入數(shù)據(jù)序列化為一個(gè)Record，單個(gè)Log文件中包含多個(gè)Record。同時(shí)，Log文件又劃分為固定大小的Block單位。對(duì)于一個(gè)log文件，LevelDB會(huì)把它切割成以32K為單位的物理Block（可以做Block Cache），并保證Block的開始位置一定是一個(gè)新的Record。這種安排使得發(fā)生數(shù)據(jù)錯(cuò)誤時(shí)，最多只需丟棄一個(gè)Block大小的內(nèi)容。顯而易見地，不同的Record可能共存于一個(gè)Block，同時(shí)，一個(gè)Record也可能橫跨幾個(gè)Block。

Block := Record * N Record := Header + Content Header := Checksum + Length + Type Type := Full or First or Midder or Last

Log文件劃分為固定長度的Block，每個(gè)Block中包含多個(gè)Record；Record的前56個(gè)字節(jié)為Record頭，包括32位checksum用做校驗(yàn)，16位存儲(chǔ)Record實(shí)際內(nèi)容數(shù)據(jù)的長度，8位的Type可以是Full、First、Middle或Last中的一種，表示該Record是否完整的在當(dāng)前的Block中，如果不是則通過Type指明其前后的Block中是否有當(dāng)前Record的前驅(qū)后繼。

Leveldb的交互流程

recovery過程

Db恢復(fù)的步驟：

首先從CURRENT讀取最后提交的MANIFEST

讀取MANIFEST內(nèi)容

清除過期文件

這里可以打開所有的sstable文件，但是更好的方案是lazy open

把log轉(zhuǎn)換為新的level 0sstable

將新寫操作導(dǎo)向到新的log文件，從恢復(fù)的序號(hào)開始

讀過程

讀的過程可以分為兩步：查找對(duì)應(yīng)key+讀取對(duì)應(yīng)值，主要問題在第一步。前面我們?cè)赟STable章節(jié)中已經(jīng)詳細(xì)解釋了對(duì)于單個(gè)SSTable文件如何快速定位key，在MemTable章節(jié)解釋了如何在內(nèi)存中快速定位key；我們先大致列出查找的流程：

在MemTable中查找，無法命中轉(zhuǎn)到2

在immutable_memtable中查找，查找不中轉(zhuǎn)到3

在第0層SSTable中查找，無法命中轉(zhuǎn)到4

在剩余SSTable中查找

那么我們接下來的問題是對(duì)于第0層以及接下來若干層，如何快速定位key到某個(gè)SSTable文件？

對(duì)于Level > 1的層級(jí)，由于每個(gè)SSTable沒有交疊，在version中又包含了每個(gè)SSTable的key range，你可以使用二分查找快速找到你處于哪兩個(gè)點(diǎn)之間，再判斷這兩個(gè)點(diǎn)是否屬于同一個(gè)SSTable，就可以快速知道是否在這一層存在以及存在于哪個(gè)SSTable。

對(duì)于0層的，看來只能遍歷了，所以我們需要控制0層文件的數(shù)目。

寫過程

完成插入操作包含兩個(gè)具體步驟：

KV記錄以順序的方式追加到log文件末尾，并調(diào)用Sync將數(shù)據(jù)真正寫入磁盤。盡管這涉及到一次磁盤IO，但是文件的順序追加寫入效率是很高的，所以并不會(huì)導(dǎo)致寫入速度的降低；

如果寫入log文件成功，那么將這條KV記錄插入內(nèi)存中的Memtable中。前面介紹過，Memtable只是一層封裝，其內(nèi)部其實(shí)是一個(gè)Key有序的SkipList列表，插入一條新記錄的過程也很簡(jiǎn)單，即先查找合適的插入位置，然后修改相應(yīng)的鏈接指針將新記錄插入即可。

log文件內(nèi)是key無序的，而Memtable中是key有序的。對(duì)于刪除操作，基本方式與插入操作相同的，區(qū)別是，插入操作插入的是Key:Value 值，而刪除操作插入的是“Key:刪除標(biāo)記”，由后臺(tái)Compaction程序執(zhí)行真正的垃圾回收操作。

其中的具體步驟可以參閱操作日志管理和memtable詳解這兩部分。

Leveldb的Log Compaction

Log Compaction的經(jīng)典問題

在解釋Leveldb的log compaction過程之前我們先回顧幾個(gè)關(guān)于如何做compaction的重要問題：

• 為什么需要compaction？
• 何時(shí)需要做compaction
• 具體怎么做compaction
• 如何在compaction的同時(shí)保證服務(wù)可用
• compaction對(duì)性能的影響
• 如何在服務(wù)的延遲和單次compaction的收益做trade off

先回答第一個(gè)問題：，LevelDB之所以需要Compaction是有以下幾方面原因：

• 數(shù)據(jù)文件中的被刪除的KV記錄占用的存儲(chǔ)空間需要被回收；
• 將key存在重合的不同Level的SSTable進(jìn)行Compaction，可以減少磁盤上的文件數(shù)量，提高讀取效率

我們接下來將主要圍繞這些問題給出Leveldb的答案。

compaction的時(shí)機(jī)

• 定期后臺(tái)觸發(fā)compaction任務(wù)
• 正常的讀寫流程中判定系統(tǒng)達(dá)到了一個(gè)臨界狀態(tài)，此時(shí)必須要進(jìn)行Compaction

這里我們主要談?wù)劧?#xff0c;什么時(shí)候判斷，如何判斷到達(dá)了這個(gè)臨界狀態(tài)？

首先了解Leveldb的兩種Compaction：

• minor compaction：將內(nèi)存immune memtable的數(shù)據(jù)dump至磁盤上的sstable文件。
• major compaction：多個(gè)level眾多SSTable之間的合并。

何時(shí)判斷是否需要compaction

• 啟動(dòng)時(shí)，Db_impl.cc::Open()在完成所有的啟動(dòng)準(zhǔn)備工作以后，會(huì)發(fā)起一次Compaction任務(wù)。這時(shí)是由于還沒有開始提供服務(wù)，不會(huì)造成任何影響，還能夠提供之后所有的讀效率，一本萬利。
• 數(shù)據(jù)寫入過程中，使用函數(shù)MakeRoomForWrite確認(rèn)memtable有足夠空間寫入數(shù)據(jù)
• get 操作時(shí)，如果有超過一個(gè) sstable 文件進(jìn)行了 IO，會(huì)檢查做 IO 的最后一個(gè)文件是否達(dá)到了 compact 的條件（ allowed_seeks 用光），達(dá)到條件，則主動(dòng)觸發(fā) compact。

在MakeRoomForWrite函數(shù)中:

先判斷是否有后臺(tái)合并錯(cuò)誤，如果有，則啥都不做；如果沒有，則執(zhí)行2;

如果后臺(tái)沒錯(cuò)誤，則判斷mem_的大小是是否小于事先定義閾值：如果是，則啥都不做返回，繼續(xù)插入數(shù)據(jù)；如果大于事先定義的閾值，則需要進(jìn)行一次minor compaction;

如果imm_不為空，代表后臺(tái)有線程在執(zhí)行合并,在此等待;

如果0層文件個(gè)數(shù)太多，則也需要等待;

如果都不是以上情況，表示此時(shí)memtable空間不足且immu memtable不為空，需要將immune memtable的數(shù)據(jù)dump至磁盤sstable文件中。 這就是Minor Compaction了，調(diào)用MaybeScheduleCompaction()函數(shù)執(zhí)行此事。

說明下為什么會(huì)有第4點(diǎn)：因?yàn)槊窟M(jìn)行一次minor compaction，level 0層文件個(gè)數(shù)可能超過事先定義的值，所以會(huì)又進(jìn)行一次major compcation。而這次major compaction，imm_是空的，所以才會(huì)有第4條判斷。

如何判斷是否需要compaction

上文的MakeRoomForWrite主要針對(duì)Minor compaction，可以看出其判斷的依據(jù)主要就是有沒有足夠的空間執(zhí)行下一次寫入操作；這里我們將主要關(guān)注major compaction，也就是文件的合并，其執(zhí)行主要是在后臺(tái)的清理線程。

major compaction的觸發(fā)方式主要有三種：

• 某一level的文件數(shù)太多
• 某一文件的查找次數(shù)超過允許值
• 手動(dòng)觸發(fā)

既然要判斷這幾個(gè)條件，就要維護(hù)相關(guān)信息，我們看看Leveldb為它們維護(hù)了哪些信息。

首先，介紹下列事實(shí)

不同level之間，可能存在Key值相同的記錄，但是記錄的Seq不同。 最新的數(shù)據(jù)存放在較低的level中，其對(duì)應(yīng)的seq也一定比level+1中的記錄的seq要大。 因此當(dāng)出現(xiàn)相同Key值的記錄時(shí)，只需要記錄第一條記錄，后面的都可以丟棄。level 0中也可能存在Key值相同的數(shù)據(jù)，但其Seq也不同。數(shù)據(jù)越新，其對(duì)應(yīng)的Seq越大。 且level 0中的記錄是按照user_key遞增，seq遞減的方式存儲(chǔ)的，相同user_key對(duì)應(yīng)的記錄被聚集在一起按照Seq遞減的方式存放的。 在更高層的Compaction時(shí)，只需要處理第一條出現(xiàn)的user_key相同的記錄即可，后面的相同user_key的記錄都可以丟棄。刪除記錄的操作也會(huì)在此時(shí)完成，刪除數(shù)據(jù)的記錄會(huì)被直接丟棄，而不會(huì)被寫入到更高level的文件。

接下來，我們分別對(duì)幾種觸發(fā)方式詳細(xì)介紹其機(jī)制：

• 容量觸發(fā)Compaction：每個(gè)Version在其生成的時(shí)候會(huì)初始化兩個(gè)值compaction_level_、compaction_score_，記錄了當(dāng)前Version最需要進(jìn)行Compaction的Level，以及其需要進(jìn)行Compaction的緊迫程度，score大于1被認(rèn)為是需要馬上執(zhí)行的。我們知道每次文件信息的改變都會(huì)生成新的Version，所以每個(gè)Version對(duì)應(yīng)的這兩個(gè)值初始化后不會(huì)再改變。level0層compaction_score_與文件數(shù)相關(guān)，其他level的則與當(dāng)前層的文件總大小相關(guān)。這種區(qū)分的必要性也是顯而易見的：每次Get操作都需要從level0層的每個(gè)文件中嘗試查找，因此控制level0的文件數(shù)是很有必要的。同時(shí)Version中會(huì)記錄每層上次Compaction結(jié)束后的最大Key值compact_pointer_，下一次觸發(fā)自動(dòng)Compaction會(huì)從這個(gè)Key開始。容量觸發(fā)的優(yōu)先級(jí)高于下面將要提到的Seek觸發(fā)。
• Seek觸發(fā)Compaction：Version中會(huì)記錄file_to_compact_和file_to_compact_level_，這兩個(gè)值會(huì)在Get操作每次嘗試從文件中查找時(shí)更新。LevelDB認(rèn)為每次查找同樣會(huì)消耗IO，這個(gè)消耗在達(dá)到一定數(shù)量可以抵消一次Compaction操作消耗的IO，所以對(duì)Seek較多的文件應(yīng)該主動(dòng)觸發(fā)一次Compaction。但在引入布隆過濾器后，這種查找消耗的IO就會(huì)變得微不足道了，因此由Seek觸發(fā)的Compaction其實(shí)也就變得沒有必要了。
• 手動(dòng)Compaction：LevelDB提供了外部接口CompactRange，用戶可以指定觸發(fā)某個(gè)Key Range的Compaction，LevelDB默認(rèn)手動(dòng)Compaction的優(yōu)先級(jí)高于兩種自動(dòng)觸發(fā)。

這幾個(gè)觸發(fā)條件并非無的放矢，單個(gè)文件過大的容量會(huì)吸引大量的查詢并且這些查詢的速度由于其容量均會(huì)減慢，考慮極端情況，只有一個(gè)SSTable，那么查詢最快也得經(jīng)歷其所有重啟點(diǎn)的二分查找。容量越大，能夠裝入內(nèi)存的table就更少，需要發(fā)生文件讀的可能性就越大。對(duì)每一層次來說，上面的理由依然成立，一層的容量過大，要么是文件數(shù)很多，要么是單個(gè)文件的容量過大，后者已經(jīng)分析過了，前者會(huì)導(dǎo)致二分變慢，而且新數(shù)據(jù)和老數(shù)據(jù)沒有區(qū)分度，不能對(duì)于這一假設(shè)（新的數(shù)據(jù)往往被更頻繁地訪問）做優(yōu)化，而且對(duì)于同一key，其記錄數(shù)變多，重啟點(diǎn)能覆蓋的key變少，即使單個(gè)文件內(nèi)的查找也變得低效。

某個(gè)文件頻繁地被查找，可能出于幾種情形：1. 它包含了太多的熱點(diǎn)key最新的記錄，也就是說它的查找大部分命中了。2. 它的key range 和一些長期木有更新而又被經(jīng)常訪問的key重合了，這種就是出現(xiàn)大量未命中的查找。個(gè)人認(rèn)為compaction主要改善的是后者，這也是為什么布隆過濾器使得seek compaction無足輕重，因?yàn)榕袛嘁粋€(gè)SSTable是否含有對(duì)應(yīng)key所需要的IO資源變少了，但如果你命中了，該讀的還是得讀，布隆并不能改善啥，所以個(gè)人認(rèn)為主要為了改善第二點(diǎn)。

上面兩段就是Leveldb對(duì)于compaction的IO消耗與單次comapct收益權(quán)衡之后給出的答案。

compaction的過程

minor compaction

首先，我們來講講minor compaction，它的目的是把immutable_memtable寫入0層的SSTable文件中。我們已經(jīng)只讀如何遍歷一個(gè)memtable了，也知道如何通過逐條添加構(gòu)建一個(gè)SSTable了，更清楚了SSTable如何持久化到文件中。對(duì)上述步驟不明白的，請(qǐng)參閱上文memtable和sstable章節(jié)，所以minor compaction的過程不是理所當(dāng)然的嗎？

這里，主要還是強(qiáng)調(diào)兩點(diǎn)：

• 寫入過程發(fā)生在immutable_memtable上，所以絲毫不影響寫服務(wù)，memtable依然可用
• 寫入文件過程完畢后，在交換memtable和immutable_memtabled之后，immutable_memtable正在服務(wù)的讀操作不會(huì)受到影響，這是得益于引用計(jì)數(shù)，直到服務(wù)完畢才會(huì)刪除原來的immutable_memtable

接下來，我們主要解析major compaction。

選取參與compaction的SSTable

除level0外，每個(gè)level內(nèi)的SSTable之間不會(huì)有key的重疊：也就是說，某一個(gè)key只會(huì)出現(xiàn)在該level（level > 0）內(nèi)的某個(gè)SSTable中。但是某個(gè)key可能出現(xiàn)在多個(gè)不同level的SSTable中。因此，大部分情形下，Compaction應(yīng)該是發(fā)生在不同的level之間的SSTable之間。

對(duì)level K的某個(gè)SSTable S1，Level K+1中能夠與它進(jìn)行Compaction的SSTable必須滿足條件：與S1存在key范圍的重合。

如上圖所示，對(duì)于SSTable X，其key范圍為hello ~ world，在level K+1中，SSTable M的key范圍為 mine ~ yours，與SSTable X存在key范圍的重合，同時(shí)SSTable N也是這樣。因此，對(duì)于 SSTable X，其Compaction的對(duì)象是Level K+1的SSTable M和SSTable N。

最后，考慮特殊情形——level0 的狀況。Level 0的SSTable之間也會(huì)存在key范圍的重合，因此進(jìn)行Compaction的時(shí)候，不僅需要在level 1尋找可Compaction的SSTable，同時(shí)也要在level 0尋找，如下圖示：

major compaction的過程

先從觸發(fā)點(diǎn)開始考慮，我們就先從簡(jiǎn)單的情況——也就是compact單個(gè)文件開始講起。先假設(shè)我們需要compact Level K層的某個(gè)文件，首先我們要做的就是首先找到參與compaction的所有文件，然后遍歷這些文件中的所有記錄，選取里面有效且最新的記錄寫入到新的SSTable文件。最后用新生成的SSTable文件替換掉原來的Level K + 1層的文件。

這樣我們就面臨一個(gè)生死攸關(guān)的問題了：當(dāng)處理一條記錄的時(shí)候，如何判斷要不要將它寫入新文件中呢？答案是當(dāng)有比它更新的同一key的記錄就拋棄它，那么如何找到這個(gè)更新的記錄呢？

最簡(jiǎn)單的做法：由于Level k 比Level k+1新，Level k+1又不會(huì)出現(xiàn)key 重合，我們很自然地可以得到一個(gè)從新到舊的遍歷順序，只要去新寫入的SSTable中查詢即可。但這樣每次寫入都需要一次查詢，依然太慢了。我們能不能先按key序遍歷，在同一key內(nèi)部再按seq遞減序遍歷，這樣只要保留每個(gè)key區(qū)間的第一個(gè)。Leveldb就是這么做的，但是如何實(shí)現(xiàn)呢？

Leveldb使用了一個(gè)merging iterator，它統(tǒng)籌控制每個(gè)SSTable的iterator，并在它們中選取一個(gè)前進(jìn)，然后跳過所有同一key的記錄。這樣處理一條記錄所需的查找代價(jià)從查詢新SSTable文件的所有內(nèi)容變成了詢問幾個(gè)SSTable對(duì)應(yīng)iter的當(dāng)前游標(biāo)，不可謂不妙啊，令人驚嘆的做法！下圖是一個(gè)簡(jiǎn)單的流程示意：

關(guān)于iterator的詳細(xì)參考可以閱讀下列文章：

庖丁解LevelDB之Iterator

下一步，我們把它擴(kuò)展到一層文件的compaction：對(duì)于大多數(shù)層，由于文件之間的key range沒有交疊，所以你完全可以迭代進(jìn)行上面的操作，分別對(duì)每一個(gè)文件合并。實(shí)際上major compaction是按key range來的，它每次會(huì)compact一個(gè)level中的一個(gè)范圍內(nèi)的SSTable，然后將這個(gè)key范圍更新，下次就compact下一范圍，控制每一層參與一次compact的SSTable數(shù)量。

接下來，我們考慮Level 0 的情形，由于我們必須保證0層的總比1層新，假設(shè)0層本來有兩個(gè)同一key的記錄，較新的那個(gè)被合并到1層之后，查詢時(shí)在0層能查到較老的那個(gè)，bug出現(xiàn)了！所以我們不得不找出本層所有和當(dāng)前所要合并的文件有重疊的文件加入合并集合來解決。

然后，我們來講講刪除的情形。Leveldb中的刪除是一個(gè)特殊記錄，它不會(huì)導(dǎo)致數(shù)據(jù)立即被刪除，而是查詢到刪除記錄后將會(huì)忽略更老的記錄。真正的刪除過程是發(fā)生在Compaction中的，這里我們又得問一個(gè)問題了：那么刪除記錄需要寫入到上一層嗎？需要的，否則在上上層的記錄就有可能被查到，只有最上層的刪除記錄會(huì)真正被刪除，所以刪除是逐步逐層地進(jìn)行的，一層一層刪去過去的記錄。

我們考慮major compaction對(duì)服務(wù)可用性和性能的影響：在生成新SSTable期間，舊的SSTable依然可用。由于SSTable本就是不可寫的，所以對(duì)寫服務(wù)不會(huì)造成任何不可用，對(duì)于讀服務(wù)，依然可以在老的SSTable上進(jìn)行。新的SSTable寫到的是一個(gè)臨時(shí)文件，當(dāng)寫入完畢后會(huì)進(jìn)行重命名操作，但是注意對(duì)于舊文件，必須查詢它在內(nèi)存中有沒有對(duì)應(yīng)的table以及該table的引用計(jì)數(shù)。只有當(dāng)沒有讀服務(wù)在該文件上，才能刪除該文件。所以，綜上compaction對(duì)服務(wù)可用性沒有什么影響。

最后，我們還需要生成一次compact點(diǎn)，進(jìn)行一次version edit并寫入Manifest文件，最終使當(dāng)前version更新到新版本。這個(gè)過程在元信息管理中已經(jīng)講述過了，就不再贅述了。

Leveldb的工程優(yōu)化

write batch

Leveldb采用write batch來優(yōu)化并發(fā)寫，對(duì)每一個(gè)寫操作，先通過傳入的鍵值對(duì)構(gòu)造一個(gè)WriteBatch對(duì)象，這玩意里面其實(shí)就是一個(gè)字符串，多個(gè)并發(fā)寫的write batch最后會(huì)被合并成一個(gè)。這一段的代碼確實(shí)精妙，請(qǐng)參閱下列文章。

leveldb - 并發(fā)寫入處理

table cache

對(duì)于Leveldb這種主要基于磁盤存儲(chǔ)的引擎，cache優(yōu)化是非常自然的想法。levelDb中引入了兩個(gè)不同的Cache:Table Cache和Block Cache。其中Block Cache是配置可選的。cache主要還是作用在讀過程中，詳細(xì)情況大家請(qǐng)參閱下列文章：

LevelDB教程9：levelDB中的Cache

源代碼實(shí)現(xiàn)解析：

leveldb源碼分析之Cache

如何作用在讀操作流程中的：

Leveldb源碼分析--11

布隆過濾器

先了解布隆過濾器的原理和概念：

Bloom Filter概念和原理

對(duì)實(shí)現(xiàn)感興趣的盆友，可以繼續(xù)看這篇文章

leveldb源碼學(xué)習(xí)--BloomFilter布隆過濾器

增加過濾器就需要在寫入SSTable的時(shí)候向過濾器添加自己寫入的鍵，這一點(diǎn)可以回頭看SSTable寫入過程。過濾器的作用在Compaction一章中也說了，主要為了改善當(dāng)發(fā)現(xiàn)目標(biāo)key在某個(gè)SSTable的key range內(nèi)，但事實(shí)上未命中時(shí)，減少IO消耗，所以大家也知道解析過濾器部分應(yīng)該用在哪兒了吧。

參考文章

• The Log-Structured Merge-Tree
• Leveldb源代碼
• 庖丁解LevelDB系列
• LevelDB專題系列
• Leveldb源碼解讀系列
• Leveldb之Put實(shí)現(xiàn)
• 那巖 《Leveldb實(shí)現(xiàn)解析》

總結(jié)

以上是生活随笔為你收集整理的Leveldb二三事的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。