天天看點
傳回

LevelDB源碼分析之十四：TwoLevelIterator

一.原理

先看一個例子，我們為書店寫一個管理圖書的程式，書店裡有許多書Book，每個書架（BookShelf)上有多本書。

類結構如下所示：

class Book {
private:
 string book_name_;
};
class Shelf {
 private:
  vector<Book> books_;
};

如何周遊書架上所有的書呢？一種實作方法是：

vector<Book>& GetBooks() const {
  return books_;
}

這樣的實作暴漏了内部太多的細節，調用者根本就不需要知道Shelf存儲Book的方式，僅僅需要周遊所有的資料即可。而且這樣當我們換用另外一種資料結構存儲Book時，用戶端的代碼就需要進行修改。但是如果使用Iterator模式則沒有這個問題。

具體的我們需要周遊書店中所有的書，現在應該如何實作呢？

一種實作方式是，由BookStore負責儲存中間狀态，包括目前周遊到了哪個書架，周遊到了書架上的哪本書。

class BookStore {
 Iterator* NewIterator() const;
 private:
  vector<Shelf> shelf_;
  vector<Shelf>::iterator shelf_iter_;
  vector<Book>::iterator book_iter_;
};

這種實作方法對外是幹淨的，但是對于BookStore的維護者來說卻是不友好的，Iterator的中間狀态不是BookStore的成員，邏輯上不應該由BookStore維護。而且當兩個甚至多個使用者同時周遊書店時BookStore得同時維護多個中間狀态，極其容易出錯。更好的一種實作方式是，把周遊Iterator相關的代碼和狀态封裝成一個類，有兩個層級Shelf 和 Book，這個類的名字我們叫做TwoLevelIteator。

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

LevelDB源碼分析之十四：TwoLevelIterator

二.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。 關于Table，詳見： LevelDB源碼分析之十三：table

參考連結：https://www.cnblogs.com/KevinT/p/3823240.html

leveldb TwoLevelIterator table
上一篇: leveldb源碼學習之 DBImpl 類（背景壓縮 major compaction）
下一篇: Python練習題：實作三數之和

繼續閱讀