LevelDB源码解析(4) MemTable

简介

MemTable是LevelDB在内存中的缓存库。用户写入数据时，LevelDB会先把数据写入到MemTable中。如果MemTable写满了，就会新建一个MemTable进行写入。后台再异步把旧的MemTable压缩写到磁盘上。因为旧的MemTable不允许写入了，所以也被称为Immutable MemTmable。

MemTable的成员变量

KeyComparator comparator_;
int refs_;
Arena arena_;
Table table_;

comparator_：是一个比较器，用于比较key的大小，这个没啥好聊的。
refs_：当前MemTable对象被引用数，如果为0说明对象未被使用。
arena_：内存分配器，具体实现可以看LevelDB源码解析(1) Arena内存分配器
table_：是一个SkipList对象，具体实现可以看LevelDB源码解析(2) SkipList(跳跃表)

MemTable的对外接口

Add - 添加元素

void Add(SequenceNumber seq, ValueType type, const Slice& key,  const Slice& value);

总共有4个参数

seq：序列号，SequenceNumber其实就是uint64_t类型。每个插入的key-value都会有一个序列号。seq的值是单调递增的。
type：值类型，ValueType是一个枚举类型，只有0和1两个值。0表示删除，1表示插入。LevelDB事实上不存在传统的删除操作，所有删除操作都是通过添加一个ValueType为0的插入记录来实现的，所以一个key在库中可能有多条记录，以最后一条记录（即seq最大的）为准。
key：key-value的key，Slice类其实就是一个字符串，只是提供了一些操作函数，把它当做一个string理解就可以了。
value：key-value的value，和key类型一样也是Slice。

Add函数把要插入的key-value编码后插入MemTable内部的跳跃表table_中。代码如下：

void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key, const Slice& value)
{
  size_t key_size = key.size(); 
  size_t val_size = value.size();
  size_t internal_key_size = key_size + 8;
  const size_t encoded_len =
    VarintLength(internal_key_size) + internal_key_size + VarintLength(val_size) + val_size;
  char* buf = arena_.Allocate(encoded_len);

  //EncodeVarint32返回的指针指向size域后第一个字节。
  char* p = EncodeVarint32(buf, internal_key_size);
  std::memcpy(p, key.data(), key_size);
  p += key_size;

  EncodeFixed64(p, (s << 8) | type);
  p += 8;

  p = EncodeVarint32(p, val_size);
  std::memcpy(p, value.data(), val_size);
  assert(p + val_size == buf + encoded_len);

  table_.Insert(buf);
}

代码逻辑分为4步：

计算编码需要的空间大小encoded_len，encoded_len为key_size变长编码长度 + key长度 + 8 + value_size变长编码长度 + value长度。
从内存分配器arena_申请encoded_len字节的内存
把seq、type、key、value编码写入buf中
把buf插入跳跃表table_

编码格式如下：

长度	key_size变长编码长度+8	key长度	7个字节	1个字节	value_size变长编码长度	value长度
内容	internal_key_size	key	seq	type	value_size	value

变长编码我们在LevelDB源码解析(3) 变长编码一文讨论过，主要是为了节省size域占用的空间。

Get - 查找元素

bool Get(const LookupKey& key, std::string* value, Status* s);

总共有3个参数和一个返回值：

key：LookupKey类型，这是一个辅助类，用于对原始的key进行编码，用于查找。LevelDB内部存储的是编码后的key，这个辅助类是辅助转换的。
value：如果找到了key的元素，就把value的值设置为实际的value
s：这个用于保存查找状态。因为MemTable中删除元素是通过添加一条删除记录来实现的，如果在MemTable里面匹配到了key，但是是条删除记录，就把s设置为NotFound
返回值：只要在MemTable里匹配到了key，不管是插入记录还是删除记录，都返回true

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
  Slice memkey = key.MemTable_key();
  Table::Iterator iter(&table_);
  iter.Seek(memkey.data());
  if (iter.Valid()) {
    const char* entry = iter.key();
    uint32_t key_length;
    const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
      switch (static_cast<ValueType>(tag & 0xff)) {
        case kTypeValue: {
          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;
}

Get的代码逻辑分为4步：

从LookupKey中获取查找key，查找key的格式是：变长key_size域|key|seq|kTypeValue
从MemTable的SkipList中搜索key。因为SkipList中存储的时候实际上是把key和value编码后存在一起的，所以Seek的时候是在匹配前缀，而不是查找key值一样的记录。Seek返回的数据的key前缀可能等于查找key，也可能是大于查找key的。如果大于查找key，一定是SkipList中最小的大于查找key的数据。
解码找到的数据，分别把key、value、ValueType解析出来
比较原始key是否匹配，如果不匹配直接返回false，如果匹配，就判断ValueType，如果是插入记录，就把value置为实际的值，返回true。如果是删除记录，就把状态s设置为NotFound，返回ture。

ApproximateMemoryUsage - 内存占用情况

size_t ApproximateMemoryUsage();

这个的实现很简单，直接调用了Arena的MemoryUsage函数。

NewIterator - 创建迭代器

Iterator* NewIterator();

返回当前MemTable对象的迭代器。

Ref 与 Unref

void Ref();
void Unref();

Ref把当前MemTable的引用数refs_加1，Unref把引用数减1，如果减1后引用数为0，就释放当前MemTable。

源码版本

https://github.com/google/leveldb/releases/tag/1.22

简介