LevelDB源碼分析之十四：TwoLevelIterator

一.原理

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

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

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

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

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

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

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

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

在雙層迭代器中，level1中的迭代器指向的是一個(gè)容器，level2中的迭代器才指向真正的元素。對(duì)應(yīng)到書店，level1指向書架（對(duì)圖書進(jìn)行分類），level2指向圖書。當(dāng)要查找某本書時(shí)，先要定位到書架，再在該書架中根據(jù)書的編號(hào)找到具體的書。

二.LevelDB中的實(shí)現(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，避免每次都要調(diào)用iterator->key()和iterator->valid()，因?yàn)樘摵瘮?shù)調(diào)的頻繁調(diào)用，有一定的性能消耗。至于為何有性能損耗，可參考：

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

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

2.迭代器的初始化

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

3.迭代器的各種操作

//?Index?Block的block_data字段中，每一條記錄的key都滿足：
//?大于上一個(gè)Data?Block的所有key，并且小于后面所有Data?Block的key
//?因?yàn)镾eek是查找key>=target的第一條記錄，所以當(dāng)index_iter_找到時(shí)，
//?該index_inter_對(duì)應(yīng)的data_iter_所管理的Data?Block中所有記錄的
//?key都小于target，需要在下一個(gè)Data?Block中seek，而下一個(gè)Data?Block
//?中的第一條記錄就滿足key>=target
void?TwoLevelIterator::Seek(const?Slice&?target)?{
??index_iter_.Seek(target);
??InitDataBlock();
??//?data_iter_.Seek(target)必然會(huì)找不到，此時(shí)data_iter_.Valid()為false
??//?然后調(diào)用SkipEmptyDataBlocksForward定位到下一個(gè)Data?Block，并定位到
??//?該Data?Block的第一條記錄，這條記錄剛好就是要查找的那條記錄
??if?(data_iter_.iter()?!=?NULL)?data_iter_.Seek(target);
??SkipEmptyDataBlocksForward();
}
//?因?yàn)閕ndex_block_options.block_restart_interval?=?1
//?所以這里是解析第一個(gè)Block?Data的第一條記錄
void?TwoLevelIterator::SeekToFirst()?{
??index_iter_.SeekToFirst();
??InitDataBlock();
??if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToFirst();
??SkipEmptyDataBlocksForward();
}
//?因?yàn)閕ndex_block_options.block_restart_interval?=?1
//?所以這里是解析最后一個(gè)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時(shí)調(diào)用了
??//???SetDataIterator(NULL)，此時(shí)直接返回，因?yàn)闆]數(shù)據(jù)可讀啦
??//?2.如果data_iter_.Valid()為false，說明當(dāng)前Data?Block的block_data字段讀完啦
??//???開始讀下一個(gè)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();
??}
}

注釋還是寫的比較詳細(xì)的，備忘足矣。block_function_是BlockFunction類型的函數(shù)指針，實(shí)參在Table類中，名為BlockReader。關(guān)于Table，詳見：LevelDB源碼分析之十三：table