前面寫(xiě)了兩篇文章介紹 LevelDB 的整體架構(gòu)和接口使用壶愤。這篇文章，我們從代碼的角度看看 LevelDB 的設(shè)計(jì)與實(shí)現(xiàn)函筋，先從讀操作開(kāi)始贝润。

LevelDB 的版本更新不是很頻繁，整體變化不大掂墓。本文的源代碼參考和索引的版本是 LevelDB v1.20谦纱。

LevelDB 的目錄結(jié)構(gòu)很簡(jiǎn)單，就不用介紹了君编，直接進(jìn)入正題吧跨嘉。

leveldb::DB

LevelDB 暴露給外部的操作接口都封裝在 leveldb::DB 這個(gè)抽象類(lèi)里，具體實(shí)現(xiàn)是 leveldb::DBImpl 吃嘿。使用時(shí)偿荷，leveldb::DB 用于引用一個(gè) LevelDB 實(shí)例。一個(gè) LevelDB 實(shí)例可以簡(jiǎn)單認(rèn)為是一個(gè)支持并發(fā)讀寫(xiě)和持久化的 map唠椭。

LevelDB 暴露給外部的操作接口都很簡(jiǎn)單跳纳，具體可以根據(jù)上面提供的索引鏈接看看代碼和注釋。

讀操作

leveldb::DB::Get 根據(jù) Key 獲取 Value贪嫂，先看看函數(shù)的原型：

virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0;

leveldb::ReadOptions 是讀操作的一些參數(shù)寺庄。verify_checksums 和 fill_cache 是兩個(gè)偏優(yōu)化的參數(shù)，重點(diǎn)是 snapshot 參數(shù)，表示本次讀操作要從哪個(gè) Snapshot 讀取斗塘。snapshot 默認(rèn)是 NULL赢织，此時(shí) LevelDB 會(huì)從當(dāng)前 Snapshot 讀取。

講到 Snapshot馍盟，我們順便來(lái)看看 leveldb::Snapshot 的實(shí)現(xiàn)于置。leveldb::Snapshot是個(gè)空殼，具體實(shí)現(xiàn)是在 leveldb::SnapshotImpl 贞岭，也相當(dāng)簡(jiǎn)單八毯，和 Snapshot 相關(guān)的變量只有一個(gè) number_ (SequenceNumber) —— 不難看出 LevelDB 是通過(guò)維護(hù)一個(gè) Sequence Number 來(lái)實(shí)現(xiàn)快照功能。

LevelDB 單個(gè) Key 的讀取操作的具體實(shí)現(xiàn)是 leveldb::DBImpl::Get 瞄桨。我們來(lái)看看讀操作的過(guò)程：

1. 獲取互斥鎖话速。
2. 獲取本次讀操作的 Sequence Number：如果 ReadOptions 參數(shù)的 snaphot 不為空，則使用這個(gè) snapshot 的 Sequence Number芯侥；否則泊交，默認(rèn)使用 LastSequence（LastSequence 會(huì)在每次寫(xiě)操作后更新）。
3. MemTable柱查， Immutable Memtable 和 Current Version 增加引用計(jì)數(shù)廓俭，避免在讀取過(guò)程中被后臺(tái)線程進(jìn)行 Compaction 時(shí)“垃圾回收”了。Version 主要用來(lái)維護(hù) SST 文件的版本信息唉工。
4. 釋放互斥鎖 研乒，下面 5 和 6 兩步是沒(méi)有持有鎖的，特別是第 6 步酵紫。
5. 構(gòu)造 LookupKey 。
6. 查找
   1. 從 MemTable 查找 错维。
   2. 從 Immutable Memtable 查找奖地。
   3. 從 SST 文件查找。
7. 獲取互斥鎖
8. 更新 SST 文件的統(tǒng)計(jì)信息赋焕，根據(jù)統(tǒng)計(jì)結(jié)果決定是否調(diào)度后臺(tái) Compaction参歹。
9. MemTable, Immutable Memtable 和 Current Version 減少引用計(jì)數(shù)。
10. 釋放鎖（由析構(gòu)函數(shù)完成）隆判，返回結(jié)果犬庇。

MemTable

上面分析讀流程的時(shí)候，可以發(fā)現(xiàn)第 6 步侨嘀，從 Memtable臭挽、Immutable Memtable 和 Current Version 指向的 SST 文件查找內(nèi)容是不需要持有鎖的。這樣做沒(méi)有并發(fā)讀寫(xiě)的問(wèn)題嗎咬腕？

簡(jiǎn)單分析一下：引用計(jì)數(shù)保證了相關(guān)文件和內(nèi)存數(shù)據(jù)結(jié)構(gòu)不會(huì)被回收欢峰，而 Immutable Memtable 和 SST 文件都是只讀的，沒(méi)有并發(fā)讀寫(xiě)問(wèn)題。所以纽帖，只要看 MemTable 是否支持并發(fā)讀寫(xiě)宠漩。

leveldb::MemTable 底層的實(shí)現(xiàn)是 leveldb::SkipList 。在 leveldb::SKipList 有一段注釋說(shuō)明 懊直，簡(jiǎn)單地說(shuō)就是：

1. 寫(xiě)寫(xiě)沖突需要外部同步扒吁。
2. 讀寫(xiě)沖突不需要外部同步，只要保證 SkipList 不會(huì)被垃圾回收就好室囊。
3. 這里的 SkipList 只插入雕崩，不修改和刪除 。

因此波俄，從這段注釋可以看出晨逝，MemTable 支持一寫(xiě)多讀同時(shí)并發(fā)操作。后面有機(jī)會(huì)聊到 LevelDB 的寫(xiě)操作再來(lái)介紹一下 SkipList 的 Insert 操作如何實(shí)現(xiàn)讀寫(xiě)并發(fā)不需要鎖懦铺。

LookupKey

LevelDB 通過(guò) user_key 和 sequence 構(gòu)造 leveldb::LookupKey 捉貌，用于 LevelDB 內(nèi)部接口的查找。參考 LookupKey 的代碼和注釋 冬念，其格式為：

LookupKey.png

1. klength 的類(lèi)型是 varint32趁窃，是 leveldb 內(nèi)部編碼的可變長(zhǎng)度的 uint32_t，存儲(chǔ) userkey + tag 的長(zhǎng)度急前。表示一個(gè) varint32 最多需要 5 個(gè)字節(jié)醒陆。
2. userkey 就是一個(gè) userkey 的 char 數(shù)組。
3. tag 是使用 LittleEndian 編碼的 uint64裆针，其組成是 7 字節(jié)的 sequence 和 1 字節(jié)的 value_type刨摩。
4. 所以，一個(gè) LookupKey 的最大長(zhǎng)度為: 5 + userkey size + 8 = userkey size + 13世吨。

SST 文件的查找

LevelDB 中將 SST 文件的管理實(shí)現(xiàn)成 leveldb::Version 澡刹，同時(shí)實(shí)現(xiàn)了 leveldb::VersionSet 管理多個(gè) Version —— 因?yàn)?LevelDB 要支持 MVCC 所以可能同時(shí)存在多個(gè)版本。

查找的時(shí)候耘婚，獲取當(dāng)前版本 current , 調(diào)用 leveldb::Version::Get 在 SST 上進(jìn)行查找罢浇。

1. 從 level0 開(kāi)始一層一層查找 —— 小 level 的數(shù)據(jù)比大 level 新，所以如果先找到了的話可以直接返回沐祷。
2. 在要查找的 level 收集需要查找的文件嚷闭。level0 的 sst 文件比較特殊，是直接由 Immutable MemTable dump 得到的赖临，因此胞锰，每個(gè)文件的 key 范圍可能重疊。level0 可能需要查找多個(gè)文件兢榨，其它 level 的 文件的 key 不會(huì)重疊胜蛉，至多只需要讀一個(gè)文件挠进。
3. 對(duì)步驟 2 收集到的文件進(jìn)行查找。具體查找邏輯由 leveldb::TableCache::Get 實(shí)現(xiàn)誊册。這里面涉及一些 Cache 相關(guān)的實(shí)現(xiàn)领突，暫時(shí)略過(guò)。
4. 查找過(guò)程會(huì)記錄一些統(tǒng)計(jì)信息：如果不止讀取一個(gè) sst 文件案怯，則記錄最后讀取的是哪個(gè) level 的哪個(gè)文件君旦。

讀觸發(fā)的 Compaction

讀取結(jié)束后，如果不止讀取一個(gè) sst 文件嘲碱，則更新統(tǒng)計(jì)信息金砍，決定是否觸發(fā) Compaction。更新統(tǒng)計(jì)信息時(shí)麦锯，直接將記錄的文件的 leveldb::FileMetaData 的 allowed_seeks 減一恕稠，當(dāng) allowed_seeks <= ０時(shí)，表示讀取效率很低扶欣，需要執(zhí)行 Compaction鹅巍，減少這條路徑上的文件數(shù)量。

調(diào)用 MaybeScheduleCompaction 嘗試調(diào)度后臺(tái)線程的 Compaction料祠。

小結(jié)

這里只是簡(jiǎn)單介紹了 LevelDB 的讀操作的大概情況骆捧。實(shí)際上，LevelDB 的讀操作涉及很多東西髓绽，如：寫(xiě)操作相關(guān)的并發(fā)讀寫(xiě)敛苇、Sequence Number 等；Compaction 相關(guān)的 Version顺呕、VersionSet等枫攀；讀操作還有可能觸發(fā) Compaction；還有 Table Cache株茶、Block Cache 這些相關(guān)的東西沒(méi)提及来涨。

參考文檔

• LevelDB Source Code
• SSTable and Log Structured Storage: LevelDB