[跟吉姆一起讀LevelDB]2.LSM Tree與leveldb::DB::Open操作(1)

01-27

在看源代碼之前, 先了解設計結構是必須的, 這就繞不開著名的LSM Tree了. 我在閱讀了原作者論文和BigTable論文之後, 一開始最驚奇的是"偽代碼"呢? 沒有. 其實LSM Tree與其說是某種數據結構/演算法, 倒不如說是一種設計思路, 用日誌和批量寫入來替代索引更新, 達到通過犧牲隨機查詢速度換取更迅捷地寫入的效果. 動機是機械硬碟時代, seek操作是昂貴的, 因為需要馬達轉動磁碟. 固態硬碟時代, 情況極大地好轉了. 但仍然不可避免的是順序寫入同樣快過隨機的.

強烈建議閱讀LSM Tree相關文章, 太基本的我就不重複介紹了, 下面講點思考.

所有數據直接寫入memtable並打log, 當memtable足夠大的時候, 變為immemtable, 開始往硬碟挪, 成為SSTable. 這就是LSM Tree僅有的全部. 你可以用任何有道理的數據結構來表示memtable, immemtable和SSTable. Google選擇用跳錶實現memtable和immemtable, 用有序行組來實現SSTable.

一點也不驚喜吧~ 原論文1996年發表, 過了好多年才被Google工程師發掘. 問題太嚴重了. 首先, 搜索key最差時要發瘋一樣從memtable讀到immemtable, 再到所有SSTable. 其次, SSTable要怎麼有效merge(Google稱之為"major compaction")呢? 資料庫寫啊寫, 有10G了, 新來了一個immemtable要歸併, 一言不合重寫10個多G? 對此, 原論文描述了一種多組件版本, 降低了瞬時IO壓力, 但總IO卻更高了, 沒解決什麼大問題.

Google打了兩個增強補丁.

1. 添加BloomFilter, 這樣可以提升全庫掃描的速度, 肯定沒這個key的SSTable直接跳過.

2. leveled compaction, 把SSTable分成不同的等級. 除等級0以外, 其餘各等級的SSTable不會有重複的key.

這可以說是最重要最有用的改動(不然為啥叫LevelDB?). 想像一下, 如果永遠只有一個SSTable, 我要把新immemtable歸併進去, 就要重寫這個SSTable. 數據有多大, 這個SSTable也會有多大, 那還怎麼合併?

聰明的童鞋可以說那把SSTable分成若干份, 每份2MB. 但wrost case一樣悲劇. 比如, 當前這個immemtable恰好永遠有一個key與任意SSTable中至少一個key重複. Ops! 又回到了剛剛重寫全庫的case了.

Google的做法則讓每次compaction波及到的範圍是可預期的. 官方文檔摘抄: "The compaction picks a file from level L and all overlapping files from the next level L+1". 這就非常優雅了! 資料庫一個老大難題就是怎麼釋放被刪除記錄的空間? LevelDB這種不立即釋放只按等級延遲合併的方法是很高明的, 沒有任何隨機讀寫操作, 機制上又很簡單, 還不需要bookkeeping.

在第一部分的最後糾正下網上很多博文都有錯的點(源代碼證實). compaction不一定會清空所有deletion maker. 這個思考下就明白了. 如果下級還有相同key的數據, 就把deletion maker清了, 應該刪除的數據不是又莫名其妙恢復了么?

http://db_impl.cc 958-967行,

} else if (ikey.type == kTypeDeletion &&n ikey.sequence <= compact->smallest_snapshot &&n compact->compaction->IsBaseLevelForKey(ikey.user_key)) {n // For this user key:n // (1) there is no data in higher levelsn // (2) data in lower levels will have larger sequence numbersn // (3) data in layers that are being compacted here and haven // smaller sequence numbers will be dropped in the nextn // few iterations of this loop (by rule (A) above).n // Therefore this deletion marker is obsolete and can be dropped.n

------

理解了大體設計, 啃代碼的時間到了. 跟我一起看看leveldb::Status status = leveldb::DB::Open(options, "testdb", &db);會觸發什麼模塊吧.

為了使用debugger, 先要對VS Code進行設置, 在根目錄新建".vscode"目錄, 建立"tasks.json"和"launch.json"文件.

tasks.json內容,

{n "command": "make",n "isShellCommand": true,n "version": "0.1.0",n "args": [],n "showOutput": "always"n}n

launch.json內容,

{n "version": "0.2.0",n "configurations": [n {n "request": "launch",n "type": "cppdbg",n "MIMode": "lldb",n "args": [],n "cwd": "${workspaceRoot}",n "environment": [],n "externalConsole": false,n "name": "(lldb) Launch",n "preLaunchTask": "make",n "program": "${workspaceRoot}/main",n "stopAtEntry": falsen }n ]n}n

Makefile的OPT設置為-g2, 然後重編譯, 再按F5應該會有這樣的效果,

------

leveldb::DB::Open來自http://db_impl.cc 1490行,

Status DB::Open(const Options& options, const std::string& dbname,n DB** dbptr) { // static工廠函數n *dbptr = NULL;nn DBImpl* impl = new DBImpl(options, dbname);n

源代碼有幾點習慣挺好的, 值得學習.

提供給外部的介面一般都要做成工廠函數, 避免我覺得有點蠢萌的兩步構造.
literal type(int, float, void*...)不允許傳引用, int a=1; F(a) vs F(&a), 後者更清晰.
總是考慮下是不是要禁止複製, 是的話寫上private: A(const A&); void operator=(const A&);
單參構造函數加explicit.

接上, new然後跳到117行的構造函數,

DBImpl::DBImpl(const Options& raw_options, const std::string& dbname)n : env_(raw_options.env), // Env* constn internal_comparator_(raw_options.comparator), // const InternalKeyComparatorn internal_filter_policy_(raw_options.filter_policy), // const InternalFilterPolicyn options_(SanitizeOptions(dbname, &internal_comparator_, // const Optionsn &internal_filter_policy_, raw_options)),n owns_info_log_(options_.info_log != raw_options.info_log), // booln owns_cache_(options_.block_cache != raw_options.block_cache), // booln dbname_(dbname), // const std::stringn db_lock_(NULL), // FileLock*n shutting_down_(NULL), // port::AtomicPointern bg_cv_(&mutex_), // port::CondVarn mem_(NULL), // MemTable*n imm_(NULL), // MemTable*n logfile_(NULL), // WritableFile*n logfile_number_(0), // uint64_tn log_(NULL), // log::Writer*n seed_(0), // uint32_tn tmp_batch_(new WriteBatch), // WriteBatch*n bg_compaction_scheduled_(false), // booln manual_compaction_(NULL) { // ManualCompaction*n has_imm_.Release_Store(NULL);nn // Reserve ten files or so for other uses and give the rest to TableCache.n const int table_cache_size = options_.max_open_files - kNumNonTableCacheFiles;n table_cache_ = new TableCache(dbname_, &options_, table_cache_size);nn versions_ = new VersionSet(dbname_, &options_, table_cache_,n &internal_comparator_);n}n

Google C++ Style雖然禁止函數默認參數, 但允許你扔個Options.

解釋下成員變數的含義,

env_, 負責所有IO, 比如建立文件
internal_comparator_, 用來比較不同key的大小
internal_filter_policy_, 可自定義BloomFilter
options_, 將調用者傳入的options再用一個函數調整下, 可見Google程序員也不是盡善盡美的... 庫的作者要幫忙去除錯誤參數和優化...
db_lock_, 文件鎖
shutting_down_, 基於memory barrier的原子指針
bg_cv_, 多線程的條件
mem_ = memtable, imm = immemtable
tmp_batch_, 所有Put都是以batch寫入, 這裡建立個臨時的
manual_compaction_, 內部開發者調用時的魔法參數, 可以不用理會

我決定先搞懂memory barrier的原子指針再繼續分析, 就先到這了.