leveldb读取流程

leveldb查找操作主函数：

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  Status s;
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  if (options.snapshot != NULL) {
    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
  } else {
    snapshot = versions_->LastSequence();
  }

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != NULL) imm->Ref();
  current->Ref();

  bool have_stat_update = false;
  Version::GetStats stats;

  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    // First look in the memtable, then in the immutable memtable (if any).
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // Done
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {
      // Done
    } else {
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    mutex_.Lock();
  }

  if (have_stat_update && current->UpdateStats(stats)) {
    MaybeScheduleCompaction();
  }
  mem->Unref();
  if (imm != NULL) imm->Unref();
  current->Unref();
  return s;
}

Get函数主体流程很简单，先从memtable中查找，再从Immutable中查找，最后从磁盘Table中查找。但是查找过程中可以考虑几个问题：
多版本控制
    查找时指定某个快照版本时如何找到数据
    先后插入了数据 "wcc":28, "wcc":29, "wcc":30, 此时查找过程如何
    先插入了数据 "wcc":28 然后删除了数据 "wcc":28, 此时查找过程如何
并发控制
    读数据的时候 其他的写线程会造成哪些影响

对于memtable(底层数据结构是skiplist)，插入的数据格式为：

key.png

而skiplist插入查找元素时使用的比较函数是:

// aaa:101  aab:101      -->  aaa:101, aab:101   //user key小的会排在前面
// aaa:101  aaa:102      -->  aaa:102, aaa:101   //user key相同, sequence大的会排在前面(教新的操作)
int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
  // Order by:
  //    increasing user key (according to user-supplied comparator)
  //    decreasing sequence number
  //    decreasing type (though sequence# should be enough to disambiguate)
  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
  //userkey相同时,比较 (sequence num << 8 | value_type) 
  //实际上sequence num已经能完全区分了
  if (r == 0) {
    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
    if (anum > bnum) {
      r = -1;
    } else if (anum < bnum) {
      r = +1;
    }
  }
  return r;
}

因此：
 当需要从指定快照版本查找数据时，ReadOptions::snapshot 应该设置成指定版本。查找key时会把 key,快照版本号组合起来进行查找。
 当数据被修改(多次插入)，如果没指定版本号，会根据当前最新版本号，找到最后一次插入的数据值。
  当数据插入后被删除，因为删除操作的sequence number更大，因此查找时优先返回，然后根据valueType是kTypeDeletion 告知调用者key对应的数据不存在。

对于磁盘中的Table, compact数据时会保证，如果key的sequence number比最小的snapshot 大的话, delete的数据也不会被drop掉.