LevelDB源码分析：TwoLevelIterator

一.原理

先看一个例子，我们为书店写一个管理图书的程序，书店里有许多书Book，每个书架（BookShelf)上有多本书。
类结构如下所示：

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

如何遍历书架上所有的书呢？一种实现方法是：

vector& GetBooks() const {
  return books_;
}

这样的实现暴漏了内部太多的细节，调用者根本就不需要知道Shelf存储Book的方式，仅仅需要遍历所有的数据即可。而且这样当我们换用另外一种数据结构存储Book时，客户端的代码就需要进行修改。但是如果使用Iterator模式则没有这个问题。

具体的我们需要遍历书店中所有的书，现在应该如何实现呢？
一种实现方式是，由BookStore负责保存中间状态，包括当前遍历到了哪个书架，遍历到了书架上的哪本书。

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

这种实现方法对外是干净的，但是对于BookStore的维护者来说却是不友好的，Iterator的中间状态不是BookStore的成员，逻辑上不应该由BookStore维护。而且当两个甚至多个用户同时遍历书店时BookStore得同时维护多个中间状态，极其容易出错。更好的一种实现方式是，把遍历Iterator相关的代码和状态封装成一个类，有两个层级Shelf 和 Book，这个类的名字我们叫做TwoLevelIteator。

在双层迭代器中，level1中的迭代器指向的是一个容器，level2中的迭代器才指向真正的元素。对应到书店，level1指向书架（对图书进行分类），level2指向图书。当要查找某本书时，先要定位到书架，再在该书架中根据书的编号找到具体的书。

二.LevelDB中的实现

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()，因为虚函数调的频繁调用，有一定的性能消耗。至于为何有性能损耗，可参考：

C++中虚函数(virtual function)到底有多慢

为什么 C++ 中使用虚函数时会影响效率？

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_已经创建了，什么都不用干，这可以防止InitDataBlock被多次调用
    } else {
      // 创建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)，此时直接返回，因为没数据可读啦
  // 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类型的函数指针，实参在Table类中，名为BlockReader。