[跟吉姆一起讀LevelDB]11.Iterator與Compaction(1)

leveldb::Iterator *it = db->NewIterator(ReadOptions());nfor (it->SeekToFirst(); it->Valid(); it->Next()) {n cout << it->key().ToString() << ": " << it->value().ToString() << endl;n}n

其中leveldb::Iterator是一個虛父類, 相當於Java的interface. 這設計再合乎情理不過了! 不同Iterator的模式具有高度的一致性, 比如都要"Next()", "Valid()"... 又不能很容易在編譯期確定, 程序怎麼知道這是memtable/immemtable的Iterator還是SSTable的Iterator, 亦或SSTable的Block的Iterator呢? 諸位如果不想實現STL那樣完備複雜的Iterator, 可以參考下Google的介面要求, 見於iterator.h.

跟入NewIterator, http://db_impl.cc 1157-1167,

Iterator* DBImpl::NewIterator(const ReadOptions& options) {n SequenceNumber latest_snapshot;n uint32_t seed;n Iterator* iter = NewInternalIterator(options, &latest_snapshot, &seed);n return NewDBIterator(n this, user_comparator(), iter,n (options.snapshot != NULLn ? reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_n : latest_snapshot),n seed);n}n

NewInternalIterator會將所有KV Iterator(memtable, SSTable...)合併成單一Iterator. 這個抽象程度就很高了! 有點編譯原理中combinator的感覺. 跟入內部, db_impl.cc 1068-1097,

Iterator* DBImpl::NewInternalIterator(const ReadOptions& options,n SequenceNumber* latest_snapshot,n uint32_t* seed) {n IterState* cleanup = new IterState;n mutex_.Lock();n *latest_snapshot = versions_->LastSequence();nn // Collect together all needed child iteratorsn std::vector<Iterator*> list;n list.push_back(mem_->NewIterator());n mem_->Ref();n if (imm_ != NULL) {n list.push_back(imm_->NewIterator());n imm_->Ref();n }n versions_->current()->AddIterators(options, &list);n Iterator* internal_iter =n NewMergingIterator(&internal_comparator_, &list[0], list.size());n versions_->current()->Ref();nn cleanup->mu = &mutex_;n cleanup->mem = mem_;n cleanup->imm = imm_;n cleanup->version = versions_->current();n internal_iter->RegisterCleanup(CleanupIteratorState, cleanup, NULL);nn *seed = ++seed_;n mutex_.Unlock();n return internal_iter;n}n

首先照例, 即使純讀操作也要上鎖取得快照. mem_和imm_是兩個跳錶的Iterator, current()->AddIterators添加的是當前Version控制下所有SSTable的Iterator. 這麼些個Iterator都存在一個vector里, 通過NewMergingIterator合併, 並註冊回調(這裡僅用於釋放資源), 當Iterator被析構時觸發. 這些其實都挺無趣的, 就是Iterator的各種組合, 記得這是設計模式的正確姿勢就好了. 部分代碼也寫得有點亂, 各種void*傳參數.

接著, NewDBIterator負責將InternalIterator的KV轉化為用戶輸入資料庫時的, 比如"6Sherry"還原為"Sherry", "6"是為了加速字元串比對而額外添加的長度prefix. 此外, 如果同一KV有多個SequenceNumber, 要根據Options得到最正確的那一個.

DBIterator有一個compaction相關策略. 在iterate時會隨機採樣key. 其實很多時候與其用if判斷一個固定閾值, 不如就用隨機數算了. 一來簡單, 二來世界就是很混沌, 隨機採樣的結果會更平滑.

http://db_iter.cc 130-137,

inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {n Slice k = iter_->key();n ssize_t n = k.size() + iter_->value().size();n bytes_counter_ -= n;n while (bytes_counter_ < 0) {n bytes_counter_ += RandomPeriod(); // 隨機設計下一個閾值n db_->RecordReadSample(k); // RandomPeriod的平均值是預先設定的n }n

RecordReadSample最終會跳到http://version_set.cc 444-480,

bool Version::RecordReadSample(Slice internal_key) {n ParsedInternalKey ikey;n if (!ParseInternalKey(internal_key, &ikey)) {n return false;n }nn struct State {n GetStats stats; // Holds first matching filen int matches;nn static bool Match(void* arg, int level, FileMetaData* f) {n State* state = reinterpret_cast<State*>(arg);n state->matches++;n if (state->matches == 1) {n // Remember first match.n state->stats.seek_file = f;n state->stats.seek_file_level = level;n }n // We can stop iterating once we have a second match.n return state->matches < 2;n }n };nn State state;n state.matches = 0; // 當前key是否跨越了多個level?n ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match); // 我有特別的回調方法nn // Must have at least two matches since we want to merge acrossn // files. But what if we have a single file that contains manyn // overwrites and deletions? Should we have another mechanism forn // finding such files?n if (state.matches >= 2) { n // 1MB cost is about 1 seek (see comment in Builder::Apply).n return UpdateStats(state.stats); // allowed_seeks是否到0了?n }n return false;n}n

開始觸及LevelDB的核心競爭力了, compaction策略,

1. iteration時隨機抽樣出來的key如果跨越了2個及以上的level, 位於最上層level的那個SSTable的allowed_seeks計數器要減一, 歸零時觸發compaction.

431-442,

bool Version::UpdateStats(const GetStats& stats) {n FileMetaData* f = stats.seek_file;n if (f != NULL) {n f->allowed_seeks--;n if (f->allowed_seeks <= 0 && file_to_compact_ == NULL) {n file_to_compact_ = f;n file_to_compact_level_ = stats.seek_file_level;n return true;n }n }n return false;n}n

背後的邏輯如果明白LevelDB的設計思想就很容易明白. 一方面我們分level是希望越下層compaction越少, 整個level越大, 另一方面又不希望一個key穿越多個level, 這樣硬碟查詢次數就更多. 所以LevelDB的compaction有兩個標準, 一個是整個level的大小, 另一個就是SSTable被訪問(seek)的次數. 根據局部性原理, 熱點數據的周圍也是熱點數據. compaction的策略還有很多(待續), 大體上理解都不難, 只是工程師為了調校出這些參數應該花了不少精力吧. 各位大可借鑒下. 我現在能一下子記起來的有, 硬碟單次讀取的block 4KB大, 每65535個位元組就要分配4位元組的checksum etc..

推薦閱讀：