LevelDB源碼分析：TwoLevelIterator

一.原理

先看一個例子，我們?yōu)闀陮懸粋€管理圖書的程序，書店里有許多書Book，每個書架（BookShelf)上有多本書。
類結構如下所示：

class?Book?{
private:
?string?book_name_;
};
class?Shelf?{
?private:
??vectorbooks_;
};

如何遍歷書架上所有的書呢？一種實現(xiàn)方法是：

vector&?GetBooks()?const?{
??return?books_;
}

這樣的實現(xiàn)暴漏了內(nèi)部太多的細節(jié)，調用者根本就不需要知道Shelf存儲Book的方式，僅僅需要遍歷所有的數(shù)據(jù)即可。而且這樣當我們換用另外一種數(shù)據(jù)結構存儲Book時，客戶端的代碼就需要進行修改。但是如果使用Iterator模式則沒有這個問題。

具體的我們需要遍歷書店中所有的書，現(xiàn)在應該如何實現(xiàn)呢？
一種實現(xiàn)方式是，由BookStore負責保存中間狀態(tài)，包括當前遍歷到了哪個書架，遍歷到了書架上的哪本書。

class?BookStore?{
?Iterator*?NewIterator()?const;
?private:
??vectorshelf_;
??vector::iterator?shelf_iter_;
??vector::iterator?book_iter_;
};

這種實現(xiàn)方法對外是干凈的，但是對于BookStore的維護者來說卻是不友好的，Iterator的中間狀態(tài)不是BookStore的成員，邏輯上不應該由BookStore維護。而且當兩個甚至多個用戶同時遍歷書店時BookStore得同時維護多個中間狀態(tài)，極其容易出錯。更好的一種實現(xiàn)方式是，把遍歷Iterator相關的代碼和狀態(tài)封裝成一個類，有兩個層級Shelf 和 Book，這個類的名字我們叫做TwoLevelIteator。

在雙層迭代器中，level1中的迭代器指向的是一個容器，level2中的迭代器才指向真正的元素。對應到書店，level1指向書架（對圖書進行分類），level2指向圖書。當要查找某本書時，先要定位到書架，再在該書架中根據(jù)書的編號找到具體的書。

二.LevelDB中的實現(xiàn)

1.頭文件

class?TwoLevelIterator:?public?Iterator?{
?public:
??TwoLevelIterator(
????Iterator*?index_iter,
????BlockFunction?block_function,
????void*?arg,
????const?ReadOptions&?options);

??virtual?~TwoLevelIterator();

??virtual?void?Seek(const?Slice&?target);
??virtual?void?SeekToFirst();
??virtual?void?SeekToLast();
??virtual?void?Next();
??virtual?void?Prev();

??virtual?bool?Valid()?const?{
????return?data_iter_.Valid();
??}
??virtual?Slice?key()?const?{
????assert(Valid());
????return?data_iter_.key();
??}
??virtual?Slice?value()?const?{
????assert(Valid());
????return?data_iter_.value();
??}
??virtual?Status?status()?const?{
????//?It'd?be?nice?if?status()?returned?a?const?Status&?instead?of?a?Status
????if?(!index_iter_.status().ok())?{
??????return?index_iter_.status();
????}?else?if?(data_iter_.iter()?!=?NULL?&&?!data_iter_.status().ok())?{
??????return?data_iter_.status();
????}?else?{
??????return?status_;
????}
??}

?private:
??void?SaveError(const?Status&?s)?{
????if?(status_.ok()?&&?!s.ok())?status_?=?s;
??}
??void?SkipEmptyDataBlocksForward();
??void?SkipEmptyDataBlocksBackward();
??void?SetDataIterator(Iterator*?data_iter);
??void?InitDataBlock();

??BlockFunction?block_function_;//生成Data?Block中block_data字段的迭代器
??void*?arg_;
??const?ReadOptions?options_;
??Status?status_;
??IteratorWrapper?index_iter_;//第一層迭代器，Index?Block的block_data字段迭代器的代理
??IteratorWrapper?data_iter_;?//第二層迭代器，Data?Block的block_data字段迭代器的代理
??//?If?data_iter_?is?non-NULL,?then?"data_block_handle_"?holds?the
??//?"index_value"?passed?to?block_function_?to?create?the?data_iter_.
??std::string?data_block_handle_;//handle中間變量
};

這里需要注意的是，兩層迭代器都是IteratorWrapper類型而不是iter，主要是為了緩存key和valid，避免每次都要調用iterator->key()和iterator->valid()，因為虛函數(shù)調的頻繁調用，有一定的性能消耗。至于為何有性能損耗，可參考：

C++中虛函數(shù)(virtual function)到底有多慢

為什么 C++ 中使用虛函數(shù)時會影響效率？

2.迭代器的初始化

void?TwoLevelIterator::InitDataBlock()?{
??if?(!index_iter_.Valid())?{
	//?當index_iter_無效時，讓data_iter_也無效
????SetDataIterator(NULL);
??}?else?{
????//?index_iter_是Index?Block中block_data字段迭代器的代理
????//?handle是對應的Data?Block的偏移和該Data?Block的block_data字段大小編碼后的結果
????Slice?handle?=?index_iter_.value();
????if?(data_iter_.iter()?!=?NULL?&&?handle.compare(data_block_handle_)?==?0)?{
????//?如果data_iter_已經(jīng)創(chuàng)建了，什么都不用干，這可以防止InitDataBlock被多次調用
????}?else?{
??????//?創(chuàng)建Data?Block中block_data字段的迭代器
??????Iterator*?iter?=?(*block_function_)(arg_,?options_,?handle);
??????//?將handle轉化為data_block_handle_
??????data_block_handle_.assign(handle.data(),?handle.size());
??????//?將iter傳給其代理data_inter_
??????SetDataIterator(iter);
????}
??}
}

3.迭代器的各種操作

//?Index?Block的block_data字段中，每一條記錄的key都滿足：
//?大于上一個Data?Block的所有key，并且小于后面所有Data?Block的key
//?因為Seek是查找key>=target的第一條記錄，所以當index_iter_找到時，
//?該index_inter_對應的data_iter_所管理的Data?Block中所有記錄的
//?key都小于target，需要在下一個Data?Block中seek，而下一個Data?Block
//?中的第一條記錄就滿足key>=target
void?TwoLevelIterator::Seek(const?Slice&?target)?{
??index_iter_.Seek(target);
??InitDataBlock();
??//?data_iter_.Seek(target)必然會找不到，此時data_iter_.Valid()為false
??//?然后調用SkipEmptyDataBlocksForward定位到下一個Data?Block，并定位到
??//?該Data?Block的第一條記錄，這條記錄剛好就是要查找的那條記錄
??if?(data_iter_.iter()?!=?NULL)?data_iter_.Seek(target);
??SkipEmptyDataBlocksForward();
}
//?因為index_block_options.block_restart_interval?=?1
//?所以這里是解析第一個Block?Data的第一條記錄
void?TwoLevelIterator::SeekToFirst()?{
??index_iter_.SeekToFirst();
??InitDataBlock();
??if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToFirst();
??SkipEmptyDataBlocksForward();
}
//?因為index_block_options.block_restart_interval?=?1
//?所以這里是解析最后一個Block?Data的最后一條記錄
void?TwoLevelIterator::SeekToLast()?{
??index_iter_.SeekToLast();
??InitDataBlock();
??if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToLast();
??SkipEmptyDataBlocksBackward();
}

void?TwoLevelIterator::Next()?{
??assert(Valid());
??data_iter_.Next();
??SkipEmptyDataBlocksForward();
}

void?TwoLevelIterator::Prev()?{
??assert(Valid());
??data_iter_.Prev();
??SkipEmptyDataBlocksBackward();
}


void?TwoLevelIterator::SkipEmptyDataBlocksForward()?{
??//?1.如果data_iter_.iter()為NULL，說明index_iter_.Valid()為為NULL時調用了
??//???SetDataIterator(NULL)，此時直接返回，因為沒數(shù)據(jù)可讀啦
??//?2.如果data_iter_.Valid()為false，說明當前Data?Block的block_data字段讀完啦
??//???開始讀下一個Data?Block的block_data字段（從block_data第一條記錄開始讀）
??while?(data_iter_.iter()?==?NULL?||?!data_iter_.Valid())?{
????//?Move?to?next?block
????if?(!index_iter_.Valid())?{
??????SetDataIterator(NULL);
??????return;
????}
????index_iter_.Next();
????InitDataBlock();
????if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToFirst();
??}
}

void?TwoLevelIterator::SkipEmptyDataBlocksBackward()?{
??while?(data_iter_.iter()?==?NULL?||?!data_iter_.Valid())?{
????//?Move?to?next?block
????if?(!index_iter_.Valid())?{
??????SetDataIterator(NULL);
??????return;
????}
????index_iter_.Prev();
????InitDataBlock();
????if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToLast();
??}
}

注釋還是寫的比較詳細的，備忘足矣。block_function_是BlockFunction類型的函數(shù)指針，實參在Table類中，名為BlockReader。