LevelDB源码分析之八：memtable

阅读本文可参考：

LevelDB源码分析之一：coding

LevelDB源码分析之二：comparator

LevelDB源码分析之三：arena

LevelDB源码分析之四：AtomicPointer

LevelDb源码分析之五：skiplist（1）

LevelDb源码分析之六：skiplist（2）

LevelDB源码分析之七：Random

        在LevelDB中所有KV数据都是存储在Memtable，Immutable Memtable和SSTable中的，Immutable Memtable从结构上讲和Memtable是完全一样的，区别仅仅在于其是只读的，不允许写入操作，而Memtable则是允许写入和读取的。当Memtable写入的数据占用内存到达指定数量，则自动转换为Immutable Memtable，等待Dump到磁盘中，系统会自动生成新的Memtable供写操作写入新数据，理解了Memtable，那么Immutable Memtable自然不在话下。

        LevelDB的MemTable提供了将KV数据写入，删除以及读取KV记录的操作接口，但是事实上Memtable并不存在真正的删除操作，删除某个Key的Value在Memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作是延后的，会在以后的Compaction过程中去掉这个KV。 需要注意的是，LevelDB的Memtable中KV对是根据Key大小有序存储的，在系统插入新的KV时，LevelDB要把这个KV插到合适的位置上以保持这种Key有序性。其实，LevelDb的Memtable类只是一个接口类，真正的操作是通过背后的SkipList来做的，包括插入操作和读取操作等，所以Memtable的核心数据结构是一个SkipList。

        Memtable主要作用是对skiplist、arena、comparator进行组合和管理，接口函数屏蔽了底层操作，对使用者更加优雅。

一.构造函数

MemTable::MemTable(const InternalKeyComparator& cmp)
    : comparator_(cmp),
      refs_(0),
      table_(comparator_, &arena_) {
}

构造函数对私有成员变量进行了初始化，table_是SkipList类型，将&aerna_当做key传入，arena_是Arena类型。

二.内存估算函数

size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }

这里直接调用的是Arena类的MemoryUsage方法，该方法返回整个内存池使用内存的总大小（不精确）。

三.添加函数

void MemTable::Add(SequenceNumber s, ValueType type,
                   const Slice& key,
                   const Slice& value) {
  // Format of an entry is concatenation of:
  //  key_size     : varint32 of internal_key.size()
  //  key bytes    : char[internal_key.size()]
  //  value_size   : varint32 of value.size()
  //  value bytes  : char[value.size()]
  size_t key_size = key.size();
  size_t val_size = value.size();
  // 参考LevelDB源码分析之二：comparator中关于Internal Key的介绍，
  // 因为Internal Key由user_key、sequence和type三个字段组成，user_key
  // 也就是这里的key，sequence和type会打包成一个uint64_t类型的数据，
  // 所以这里的长度为key_size+8
  size_t internal_key_size = key_size + 8;
  // 参考LevelDB源码分析之一：coding，为了节约空间，数字都是编码存储的，
  // VarintLength方法求出的是编码后的长度。关于encoded_len的组成详见下图。
  const size_t encoded_len =
      VarintLength(internal_key_size) + internal_key_size +
      VarintLength(val_size) + val_size;
  // 分配内存
  char* buf = arena_.Allocate(encoded_len);
  // 编码internal_key_size，编码后存放到buf中，p指向internal_key_size的结尾
  char* p = EncodeVarint32(buf, internal_key_size);
  // 将key拷贝到buf中，占用key_size大小
  memcpy(p, key.data(), key_size);
  p += key_size;
  // 将sequence和type打包后存放到buf中，大小为8字节，EncodeFixed64只是进行了简单的拷贝（考虑的大端或小端）。
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  // 编码val_size，编码后存放到buf中，p指向val_size的结尾
  p = EncodeVarint32(p, val_size);
  // 将value拷贝到buf中，占用val_size大小
  memcpy(p, value.data(), val_size);
  // 判断存储完后所占内存的大小，是否与初始计算的大小相等
  assert((p + val_size) - buf == encoded_len);
  // 插入到SkipList中
  table_.Insert(buf);
}

一个完整的buf内容如下图所示。

四.获取函数

// 如果能找到key对应的value, 将该value存储到*value参数中，返回值为true。
// 如果这个key中的有删除标识,存放一个NotFound()错误到*status参数中，返回值为true。
// 否则返回值为false
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  // 得到memkey，memkey中实际上包含了klength|userkey|tag，也就是说它包含了internal_key_size
  // 和internal_key
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  // 找到SkipList中大于等于memkey的结点
  iter.Seek(memkey.data());
  // 如果找到了这个结点
  if (iter.Valid()) {
	// 一个结点的结构如下所示
    // entry format is:
    //    klength  varint32
    //    userkey  char[klength]
    //    tag      uint64
    //    vlength  varint32
    //    value    char[vlength]
    // Check that it belongs to same user key.  We do not check the
    // sequence number since the Seek() call above should have skipped
    // all entries with overly large sequence numbers.
    const char* entry = iter.key();
    uint32_t key_length;
	// 取出klength，并将key_ptr指到klength之后
	// 为什么加5？参考LevelDB源码分析之一：coding
    const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
	// 比较结点中的userkey和LookupKey中的userkey是否相等，如果相等，说明找到了这个结点。
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8),
            key.user_key()) == 0) {
      // 获取tag，tag等于(sequence<<8)|type
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
	  // 取出type并判断
      switch (static_cast(tag & 0xff)) {
        case kTypeValue: {
		  // 取出value的大小和内容
          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
          value->assign(v.data(), v.size());
          return true;
        }
        case kTypeDeletion:
          *s = Status::NotFound(Slice());
          return true;
      }
    }
  }
  return false;
}

}

获取函数的第一个参数是LookupKey类型，LookupKey是一个帮助类，通过它可以更方便的对Memtable进行操作。由于LookupKey的官方注释特别详细，这里就不分析了。