leveldb 源码分析 22¶
本系列《leveldb 源码分析》共有 22 篇文章，这是第二十二篇
14 DB 的查询与遍历之 2¶
14.4 DBIter¶
Leveldb 数据库的 MemTable 和 sstable 文件的存储格式都是(user key, seq, type) => uservalue。DBIter 把同一个 userkey 在 DB 中的多条记录合并为一条，综合考虑了 userkey 的序号、删除标记、和写覆盖等等因素。 从前面函数 NewIterator 的代码还能看到，DBIter 内部使用了 MergingIterator，在调用 MergingItertor 的系列 seek 函数后，DBIter 还要处理 key 的删除标记。否则，遍历时会把已删除的 key 列举出来。 DBIter 还定义了两个移动方向，默认是 kForward： 1） kForward，向前移动，代码保证此时 DBIter 的内部迭代器刚好定位在 this->key(),this->value() 这条记录上； 2） kReverse，向后移动，代码保证此时 DBIter 的内部迭代器刚好定位在所有 key=this->key() 的 entry 之前。 其成员变量 savedkey 和 saved value 保存的是 KReverse 方向移动时的 k/v 对，每次 seek 系调用之后，其值都会跟随 iter_ 而改变。 DBIter 的代码开始读来感觉有些绕，主要就是它要处理删除标记，而且其底层的 MergingIterator，对于同一个 key 会有多个不同 sequence 的 entry。导致其 Next/Prev 操作比较复杂，要考虑到上一次移动的影响，跳过删除标记和重复的 key。 DBIter 必须导出 Iterator 定义的几个接口，下面就拖出来挨个分析。
14.4.1 Get 系接口¶
首先是几个简单接口，获取 key、value 和 status 的：
//kForward直接取iter_->value()，否则取saved value
virtual Slice value() const {
assert(valid_);
return (direction_ == kForward) ? iter_->value() : saved_value_;
}
virtual Status status() const {
if (status_.ok())
returniter_->status();
return status_;
}
14.4.2 辅助函数¶
在分析 seek 系函数之前，先来理解两个重要的辅助函数：FindNextUserEntry 和 FindPrevUserEntry 的功能和逻辑。其功能就是循环跳过下一个/前一个 delete 的记录，直到遇到 kValueType 的记录。 先来看看，函数声明为： void DBIter::FindNextUserEntry(bool skipping, std::string* skip) 参数@skipping 表明是否要跳过 sequence 更小的 entry； 参数@skip 临时存储空间，保存 seek 时要跳过的 key； 在进入 FindNextUserEntry 时，iter_ 刚好定位在 this->key(), this->value() 这条记录上。下面来看函数实现：
virtual Slice key() const { //kForward直接取iter_->key()，否则取saved key
assert(valid_);
return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
}
// 循环直到找到合适的entry，direction必须是kForward
assert(iter_->Valid());
assert(direction_ == kForward);
do {
ParsedInternalKey ikey;
// 确保iter_->key()的sequence <= 遍历指定的sequence
if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
switch (ikey.type) {
case kTypeDeletion:
//对于该key，跳过后面遇到的所有entry，它们被这次删除覆盖了
//保存key到skip中，并设置skipping=true
SaveKey(ikey.user_key, skip);
skipping = true;
break;
case kTypeValue:
if (skipping &&
user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
// 这是一个被删除覆盖的entry，或者user key比指定的key小，跳过
}
else { // 找到，清空saved key并返回，iter_已定位到正确的entry
valid_ = true;
saved_key_.clear();
return;
}
break;
}
}
iter_->Next(); // 继续检查下一个entry
} while (iter_->Valid());
// 到这里表明已经找到最后了，没有符合的entry
saved_key_.clear();
valid_ = false;
FindNextUserKey 移动方向是 kForward，DBIter 在向 kForward 移动时，借用了 saved key 作为临时缓存。FindNextUserKey 确保定位到的 entry 的 sequence 不会大于指定的 sequence，并跳过被删除标记覆盖的旧记录。 接下来是 FindPrevUserKey，函数声明为：void DBIter::FindPrevUserEntry()，在进入 FindPrevUserEntry 时，iter_ 刚好位于 saved key 对应的所有记录之前。源代码如下：
assert(direction_ == kReverse); // 确保是kReverse方向
ValueType value_type =kTypeDeletion; //后面的循环至少执行一次Prev操作
if (iter_->Valid()) {
do { // 循环
// 确保iter_->key()的sequence <= 遍历指定的sequence
ParsedInternalKey ikey;
if (ParseKey(&ikey)&& ikey.sequence <= sequence_) {
if ((value_type !=kTypeDeletion) &&
user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
break; // 我们遇到了前一个key的一个未被删除的entry，跳出循环
// 此时Key()将返回saved_key，saved key非空；
}
//根据类型，如果是Deletion则清空saved key和saved value
//否则，把iter_的user key和value赋给saved key和saved value
value_type = ikey.type;
if (value_type ==kTypeDeletion) {
saved_key_.clear();
ClearSavedValue();
} else {
Slice raw_value =iter_->value();
if(saved_value_.capacity() > raw_value.size() + 1048576) {
std::string empty;
swap(empty,saved_value_);
}
SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
saved_value_.assign(raw_value.data(), raw_value.size());
}
}
iter_->Prev(); // 前一个
} while (iter_->Valid());
}
if (value_type == kTypeDeletion){ // 表明遍历结束了，将direction设置为kForward
valid_ = false;
saved_key_.clear();
ClearSavedValue();
direction_ = kForward;
} else {
valid_ = true;
}
函数 FindPrevUserKey 根据指定的 sequence，依次检查前一个 entry，直到遇到 user key 小于 saved key，并且类型不是 Delete 的 entry。如果 entry 的类型是 Delete，就清空 saved key 和 saved value，这样在依次遍历前一个 entry 的循环中，只要类型不是 Delete，就是要找的 entry。这就是 Prev 的语义。
14.4.3 Seek 系函数¶
了解了这两个重要的辅助函数，可以分析几个 Seek 接口了，它们需要借助于上面的这两个函数来跳过被 delete 的记录。
void DBIter::Seek(const Slice& target) {
direction_ = kForward; // 向前seek
// 清空saved value和saved key，并根据target设置saved key
ClearSavedValue();
saved_key_.clear();
AppendInternalKey( // kValueTypeForSeek(1) > kDeleteType(0)
&saved_key_,ParsedInternalKey(target, sequence_, kValueTypeForSeek));
iter_->Seek(saved_key_); // iter seek到saved key
//可以定位到合法的iter，还需要跳过Delete的entry
if (iter_->Valid()) FindNextUserEntry(false,&saved_key_);
else valid_ = false;
}
void DBIter::SeekToFirst() {
direction_ = kForward; // 向前seek
// 清空saved value，首先iter_->SeekToFirst，然后跳过Delete的entry
ClearSavedValue();
iter_->SeekToFirst();
if (iter_->Valid()) FindNextUserEntry(false,&saved_key_ /*临时存储*/);
else valid_ = false;
}
void DBIter::SeekToLast() { // 更简单
direction_ = kReverse;
ClearSavedValue();
iter_->SeekToLast();
FindPrevUserEntry();
}
14.4.4 Prev() 和 Next()¶
Next 和 Prev 接口，相对复杂一些。和底层的 merging iterator 不同，DBIter 的 Prev 和 Next 步进是 以 key 为单位的，而 mergingiterator 是以一个 record 为单位的。所以在调用 merging Iterator 做 Prev 和 Next 迭代时，必须循环直到 key 发生改变。 这次让我们以 Prev 为例，以 14.4-1 图解一下，还真是一图胜千言啊。 假设指定读取的 sequence 为 2，当前 iter 在 key4:2:1 上，direction 为 kForward。此时调用 Prev()，此图显示了 Prev 操作执行的 5 个步骤：
S1 首先因为 direction 为 kForward，先调整 iter 到 key3:1:1 上。此图也说明了调整的理由，key4:2:1 前面还有 key4:3:1。然后进入 FindPrevUserEntry 函数，执行 S2 到 S4。 S2 跳到 key3:2:0 上时，这是一个删除标记，清空 saved key（其中保存的是 key3:1:1）。 S3 循环继续，跳到 key2:1:1 上，此时 key2:1:1 > saved key，设置 saved key 为 key2:1:1，并继续循环。 S4 循环继续，跳到 key2:2:1 上，此时 key2:2:1 > saved key，设置 saved key 为 key2:2:1，并继续循环。 S5 跳到 Key1:1:1 上，因为 key1:1:1 < saved key，跳出循环。 最终状态 iter_ 位置在 key1:1:1 上，而 saved key 保存的则是 key2:2:1 上，这也就是 Prev 应该定位到的值。也就是说在 Prev 操作下，iter_ 的位置并不是真正的 key 位置。这就是前面 Get 系函数中，在 direction 为 kReverse 时，返回 saved key/value 的原因。 同理，在 Next 时，如果 direction 是 kReverse，根据上面的 Prev 可以发现，此时 iter 刚好是 saved key 的前一个 entry。执行iter->Next()就跳到了 saved key 的 dentry 范围的 sequence 最大的那个 entry。在前面的例子中，在 Prev 后执行 Next，那么 iter 首先跳转到 key2:3:1 上，然后再调用 FindNextUserEntry 循环，使 iter 定位在 key2:2:1 上。 下面首先来分析 Next 的实现。如果 direction 是 kReverse，表明上一次做的是 kReverse 跳转，这种情况下，iter_ 位于 key 是 this->key() 的所有 entry 之前，我们需要先把 iter_ 跳转到 this->key() 对应的 entries 范围内。
void DBIter::Next() {
assert(valid_);
if (direction_ == kReverse) { //需要预处理，并更改direction=kForward
direction_ = kForward;
// iter_刚好在this->key()的所有entry之前，所以先跳转到this->key()
// 的entries范围之内，然后再做常规的skip
if (!iter_->Valid()) iter_->SeekToFirst();
else iter_->Next();
if (!iter_->Valid()) {
valid_ = false;
saved_key_.clear();
return;
}
}
// 把saved_key_ 用作skip的临时存储空间
std::string* skip =&saved_key_;
SaveKey(ExtractUserKey(iter_->key()), skip);// 设置skip为iter_->key()的user key
FindNextUserEntry(true, skip);
}
接下来是 Prev()，其实和 Next() 逻辑相似，但方向相反。
如果 direction 是 kForward，表明上一次是做的是 kForward 跳转，这种情况下，iter_ 指向当前的 entry，我们需要调整 iter，使其指向到前一个 key，iter 的位置是这个 key 所有 record 序列的最后一个，也就是 sequence 最小的那个 record。
void DBIter::Prev() {
assert(valid_);
if (direction_ == kForward) { //需要预处理，并更改direction
// iter_指向当前的entry，向后扫描直到key发生改变，然后我们可以做
//常规的reverse扫描
assert(iter_->Valid()); // iter_必须合法，并把saved key设置为iter_->key()
SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
while (true) {
iter_->Prev();
if (!iter_->Valid()) { // 到头了，直接返回
valid_ = false;
saved_key_.clear();
ClearSavedValue();
return;
}
if (user_comparator_->Compare(ExtractUserKey(iter_->key()),
saved_key_) < 0) {
break; // key变化就跳出循环，此时iter_刚好位于saved key对应的所有entry之前
}
}
direction_ = kReverse;
}
FindPrevUserEntry();
}
接下来要分析的是插入和删除操作。
14.5 小结¶
查询操作并不复杂，只需要根据 seq 找到最新的记录即可。知道 leveldb 的遍历会比较复杂，不过也没想到会这么复杂。这主要是得益于 sstable 0 的重合性，以及 memtable 和 sstable 文件的重合性。
leveldb 源码分析全系列完。