LevelDB源码分析之memtable

前言

LevelDB是一个google实现的非常高效的kv数据库。
LevelDB采用了LSM tree实现了高效的写操作和不错的读性能。LSM tree即The Log-Structured Merge-Tree，它充分考虑了磁盘随机读写速度慢的问题，尽可能保证了键值对插入过程中磁盘只进行顺序写入，而不用执行寻道、移动磁头等昂贵操作。LSM tree主要由两部分数据结构组成，其一是驻留内存的memtable，其二是保存到磁盘上的sstable。LSM tree的介绍，可参见introduction to LSM.

• LevelDB在内存中维护memtable记录最近的写操作（kTypeValue）和删除操作（kTypeDeletion）；
• 当内存中的memtable达到一定大小后，会将其保存为硬盘上的sstable.

本文分析LevelDB的memtable实现。

memtable

memtable维护最近发生在LevelDB的写操作。其底层采用的是一种具有O(logn)查找和插入时间复杂度的数据结构：Skip List，以下简单介绍其概念。

Skip List有多个层，其最底层是一个排好序的链表。

Skip list的查找

• 如上图所示，假设要查找9，查找时，从顶层开始，找到第一个恰小于9的结点，这里为1；
• 因为结点1后没有更多结点，向下走一层，重复上述过程，到达结点6；
• 继续往下走一层，然后往前找，到达9，即找到目标结点。

Skip list的插入

Skip list的插入过程与查找类似，但在查找插入位置的过程中，需要记录经过的结点“路径”，当找到插入位置后，垂直走至底层，将新结点插入。然后逐层回溯“结点路径”，第i+1层的结点以某一固定概率p延伸到上层。

平均情况下，每个结点出现在1/(1-p)个层中。

memtable实现

MemTable类提供的API

  // 自增引用计数。
  void Ref() {
     ++refs_; }

  // Drop reference count. Delete if no more references exist.
  void Unref() {
    
    --refs_;
    assert(refs_ >= 0);
    if (refs_ <= 0) {
    
      delete this;
    }
  }

  // 返回此memtable大约占用的内存空间大小。
  size_t ApproximateMemoryUsage();

  // memtable的迭代器。
  // 调用者需要保证在迭代器存活时memtable也存活。
  // 此迭代器返回的是编码后的内部键（internal key）。
  Iterator* NewIterator();

  // 往memtable中添加一个键值对，指定序列号SequenceNumber和类型。
  // 类型为kTypeValue表明是插入键值对，类型为kTypeDeletion表明是删除键值对。
  void Add(SequenceNumber seq, ValueType type, const Slice& key,
           const Slice& value);

  // 根据键从memtable获取值，值将被存到value变量中，并返回true。
  // 如果memtable包含一个key的删除标记，存一个NotFound()到变量s中并返回true。
  // 其它情况返回false。
  bool Get(const LookupKey& key, std::string* value, Status* s);

MemTable的成员变量如下：

  typedef SkipList<const char*, KeyComparator> Table;
  
  // 键的比较器
  KeyComparator comparator_;
  // 引用计数器
  int refs_;
  // 内存分配器
  Arena arena_;
  // 底层的 skip list
  Table table_;

Add

Add将一个entry插入到memtable中。

一个entry的内存布局如下：

此处key类型为Internal Key。LevelDB包含三种key：

• Lookup Key
• Internal Key
• User Key

User Key是读写数据库直接用到的key，一般用一个Slice表示，如：

db->Put(leveldb::WriteOptions(), "hello", "LevelDB");	// 此处"hello"即User Key.

Internal Key则是在User Key的基础上扩充了两个字段。Lookup Key又在Internal Key的首部添加了一个字段。它们三者的关系如下图所示：

Add代码实现如下：

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()]
  // tag : uint64((sequence << 8) | type)
  // value_size : varint32 of value.size()
  // value bytes : char[value.size()]
  size_t key_size = key.size();
  size_t val_size = value.size();

  size_t internal_key_size = key_size + 8;	// Internal Key 占用内存大小为 User Key + 8 bytes，详见上图
  const size_t encoded_len = VarintLength(internal_key_size) +
                             internal_key_size + VarintLength(val_size) +
                             val_size;
  // 给entry分配空间。
  char* buf = arena_.Allocate(encoded_len);
  // 将key_size写到此entry中。
  char* p = EncodeVarint32(buf, internal_key_size);
  // 将key写到此entry中。
  std::memcpy(p, key.data(), key_size);
  p += key_size;
  // 将tag写到此entry中，tag包含序列号的低56位和操作类型（插入/删除，八位）。
  EncodeFixed64(p, (s << 8) | type);
  p += 8;
  // 将val_size写到此entry中。
  p = EncodeVarint32(p, val_size);
  // 将value写到此entry中。
  std::memcpy(p, value.data(), val_size);
  assert(p + val_size == buf + encoded_len);
  // entry构建完成，将它插入到skip list中。
  table_.Insert(buf);
}

Add实际上根据entry的内存布局将各字段放到分配的buf内存空间中，然后调用其skip list成员变量的方法table_.Insert(buf)将构造的entry插入到skip list中。

Get

Get根据键LookupKey在memtable中查找entry。

Get代码如下：

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
    
  Slice memkey = key.memtable_key();
  // 声明了一个skip list上的迭代器。
  Table::Iterator iter(&table_);
  iter.Seek(memkey.data());
  if (iter.Valid()) {
    
    // entry format is:
    // klength varint32
    // userkey char[klength]
    // tag uint64
    // vlength varint32
    // value char[vlength]
    // 检查它属于同一个user key。
    // 不检查序列号，因为Seek()已经跳过了序列号过大的entry。
    
    // 迭代下一个键。
    const char* entry = iter.key();
    // 从entry中读出key_length。
    uint32_t key_length;
    // GetVarint32Ptr从entry读出key_length，并返回读取后指针的位置，即key的地址。
    const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
    // 对entry中的user key和lookup key中的user key进行比较。
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
    
      // 找到了正确的user key.
      // 取出紧跟user key后的tag，即序列号和值类型。
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
      // 取出tag低8位的值，即value type.
      switch (static_cast<ValueType>(tag & 0xff)) {
    
        case kTypeValue: {
    
          // key_ptr + key_length即值长度字段的位置，GetLengthPrefixedSlice从entry里面取出了值v。
          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
          // 将值v赋给value后返回true.
          value->assign(v.data(), v.size());
          return true;
        }
        case kTypeDeletion:
          // 键已经被删除，返回not found.
          *s = Status::NotFound(Slice());
          return true;
      }
    }
  }
  return false;
}

将memtable写到sstable

当一个memtable超出一定的大小（默认4MB）时，会创建一个新的memtable和日志文件，并将以后的更新定向到此新的memtable和日志文件。
在后台进行以下工作：

1. 将先前的memtable内容写到sstable；
2. 丢弃旧的memtable；
3. 删除旧的日志文件和memtable；
4. 将新的sstable添加到level-0.

其调用链如下：

Put() -> Write() -> MakeRoomForWrite() -> MaybeScheduleCompaction() -> 
env_->Schedule(&DBImpl::BGWork, this)异步开始BGWork() -> BackgroundCall() -> 
BackgroundCompaction() -> CompactMemTable()

参考资料

introduction to LSM
LevelDB Documentation
Skip List Wikipedia