LevelDB之Memtable实现

发表于 |

作为LevelDB源码分析系列的第一篇文章，介绍Memtable的实现，以及其中涉及到的数据结构和辅助函数。

Memtable是LevelDB的内存数据结构。当一个Memtable满之后，会被变成Immutable Memtable，并写入SSTable Level0。

基本概念

VarInt

LevelDB的VarInt机制，用一个char数组存放整数，主要目的不是支持大整数，而是压缩小整数的存储空间。例如小于128的unsigned int，只要一个字节就行，但如果数比较大，。
具体实现就是读char数组，如果最高位是1，那么就说明这个VarInt还没有结束，于是就接着读下一位。
GetVarint32Ptr的函数签名，传入的limit表示这个VarInt数组有多长。因为VarInt最多占用5个字节，所以一般传入都是p + 5。我们需要注意，合法的limit应当始终大于p。
一开始是一个优化分支，如果只有一个char，那么直接返回了，否则调用GetVarint32PtrFallback。
这个函数返回的前进后的p。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
inline const char* GetVarint32Ptr(const char* p, const char* limit,
                                  uint32_t* value) {
  if (p < limit) {
    uint32_t result = *(reinterpret_cast<const uint8_t*>(p));
    if ((result & 128) == 0) {
      *value = result;
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p, limit, value);
}

const char* GetVarint32PtrFallback(const char* p, const char* limit,
                                   uint32_t* value) {
  uint32_t result = 0;
  for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
    uint32_t byte = *(reinterpret_cast<const uint8_t*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return nullptr;
}

Slice

Slice定义在include/leveldb/slice.h里面，可以理解为对const char*的View。

Memtable类

Memtable类定义在memtable.h/cc里面。接口如下

  1. size_t ApproximateMemoryUsage()
    估计大小，在被修改的时候也可以调用。
  2. Iterator* NewIterator()
  3. void Add(SequenceNumber seq, ValueType type, const Slice& key, const Slice& value)
    负责插入记录。
    1. type
      普通插入type为kTypeValue。
      删除操作实际上是插入type为kTypeDeletion的记录。
    2. key
  4. bool Get(const LookupKey& key, std::string* value, Status* s)
    如果存在key对应的记录，返回true，并且将值存在*value上。
    如果存在key被删除的记录，返回true，并且在*status存入NotFound()。
    否则返回false。
    这里LookupKey的设计较为复杂，稍后讲解。
  5. void Ref()
  6. void Unref()

Memtable还有下面一些成员：

  1. KeyComparator comparator_
    封装了个InternalKeyComparator，这一块后面介绍

    1
    2
    3
    4
    5
    struct KeyComparator {
      const InternalKeyComparator comparator;
      explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) {}
      int operator()(const char* a, const char* b) const;
    };

  2. int refs_

  3. Arena arena_

  4. Table table_
    实际上是个跳表。

    1
    typedef SkipList<const char*, KeyComparator> Table;

Key

Memtable在跳表中索引的Key中存放三个数据：

  1. User Key
    用户实际传入的key。

  2. Sequence Number

    1
    typedef uint64_t SequenceNumber;

  3. Value Type
    表示是不是删除。
    对于C而言，enum的大小取决于里面定义的范围。对于C++，可以显式指定实际使用的类型。

    1
    enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 };

这些数据是按顺序编码的，这样方便比较。

InternalKey把这些打包到一个std::string里面。
ParseInternalKey把InternalKey转成ParsedInternalKey，后者可以直接读取上面三个字段。
AppendInternalKey可以从ParsedInternalKey构建InternalKey。

为了方便查找，还将User Key和Sequence Number合并，组成LookupKey。

  1. start_
    指向klength，klength表示userkey长度。注意，这里userkey也可以存放InternalKey，所以LookupKey可以表示一个Memtable Key。

    1
    2
    3
    4
    klength  varint32               <-- start_
    userkey  char[klength]          <-- kstart_
    tag      uint64
                                    <-- end_

  2. kstart_

  3. end_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LookupKey {
 public:
  // Initialize *this for looking up user_key at a snapshot with
  // the specified sequence number.
  LookupKey(const Slice& user_key, SequenceNumber sequence);

  LookupKey(const LookupKey&) = delete;
  LookupKey& operator=(const LookupKey&) = delete;

  ~LookupKey();

  // Return a key suitable for lookup in a MemTable.
  Slice memtable_key() const { return Slice(start_, end_ - start_); }

  // Return an internal key (suitable for passing to an internal iterator)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

  // Return the user key
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
};

总结一下，一个Key中的信息包括：

  1. klength
  2. User Key
  3. Tag
    1. Sequence Number
    2. Value Type

其中：

  1. Memtable Key
    1+2+3
  2. Internal Key
    2+3
  3. User Key
    2

比较

我们合成了一个包含三个部分的Internal Key，如果仅仅是这样，直接比较也许还是可行的，毕竟User Key、Seq、Value Type啥的都是有层级的。但是，这些东西是用VarInt存储的，这就不好直接bitwise比较了。

Comparator接口定义在include/leveldb/comparator.h里面。包含下面一些成员

  1. int Compare(const Slice& a, const Slice& b) const
    比较函数
  2. void FindShortestSeparator(std::string* start, const Slice& limit)
    目的是节约空间。如果*start这个字符串小于limit字符串，那么就修改*start，变成大小在*start和limit之间，但是长度最短的字符串。
    其方法基于公共前缀，如果*start是helloWorld，limit是helloZookeeper，那么旧改*start为helloX，也就是后面的World不要了。
    【Q】这个功能会用到哪里呢？我觉得在插入是用不上的，因为会涉及修改Key的值。
  3. void FindShortSuccessor(std::string* key)

data在开头存了对应字符串的长度。所以GetLengthPrefixedSlice会先读取长度到len里面，这个时候p前进指向了实际的字符串，然后创建一个Slice。

1
2
3
4
5
6
static Slice GetLengthPrefixedSlice(const char* data) {
  uint32_t len;
  const char* p = data;
  p = GetVarint32Ptr(p, p + 5, &len);  // +5: we assume "p" is not corrupted
  return Slice(p, len);
}

MemTable::KeyComparator就是获取对应的字符串，然后调用InternalKeyComparator比较。

1
2
3
4
5
6
7
int MemTable::KeyComparator::operator()(const char* aptr,
                                        const char* bptr) const {
  // Internal keys are encoded as length-prefixed strings.
  Slice a = GetLengthPrefixedSlice(aptr);
  Slice b = GetLengthPrefixedSlice(bptr);
  return comparator.Compare(a, b);
}

比较的顺序是:

  1. User Key升序
  2. Sequence Number降序
    这样，会倾向于找新的
  3. ValueType降序
    但考虑到Sequence Number，大概率用不到。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
      int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
      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;
    }

可以看到，在InternalKeyComparator里面，还会调用user_comparator_->Compare去比较User Key。它默认是BytewiseComparator类型的。

插入

现在我们有一个KV对key和value，都用Slice运载的。我们要把它放到跳表中。
有点类似于Spark将K和V连续放在两个slot上，LevelDB直接将K和V编码到一起存放。因此，我们可以看到总长度encoded_len需要计算下面几部分：

  1. K的长度，用VarInt存
    这里internal_key_size为啥要加上8呢？这是因为Sequence Number和Type分别占用了7个byte和1个byte。所以从User Key生成Internal Key的时候要加上这两部分。
    这就是Memtable Key，相对于Internal Key多存储的一块数据。
  2. K本身
    也就是Internal Key。
  3. V的长度
  4. V本身
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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();
      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;
    ...

下面，就是从Memtable里面的Arena中分配一块内存buf，然后把上面说的四个字段填进去，最后把buf添加到跳表table_里面。跳表插入只需要实现比较操作，这个之前已经定义过了。

1
2
3
4
5
6
7
8
9
10
11
12
...
  char* buf = arena_.Allocate(encoded_len);
  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);
}

查找

首先，从LookupKey中取得memtable_key，这个是包含了4个部分的。接着获得跳表的迭代器iter，定位到第一个大于等于memkey的位置。
我们得到key_ptr指向Internal Key，key_length为Internal Key的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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()) {
    // 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;
    const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);

接着我们比较Value Type，它在tag的最后一个字节。注意tag的组装方式是(seq << 8) | type

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
      // Correct user key
      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;
}

Reference

  1. https://izualzhy.cn/memtable-leveldb
  2. https://github.com/yingshin/leveldb_more_annotation/blob/master/db/memtable.h
  3. https://zhuanlan.zhihu.com/p/79362747
  4. https://github.com/balloonwj/CppGuide/blob/master/articles/leveldb%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/leveldb%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%904.md