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。
      删除操作实际上是插入typekTypeDeletion的记录。
    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里面。
ParseInternalKeyInternalKey转成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,变成大小在*startlimit之间,但是长度最短的字符串
    其方法基于公共前缀,如果*starthelloWorldlimithelloZookeeper,那么旧改*starthelloX,也就是后面的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对keyvalue,都用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