作为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 | inline const char* GetVarint32Ptr(const char* p, const char* limit, |
Slice
Slice定义在include/leveldb/slice.h里面,可以理解为对const char*
的View。
Memtable类
Memtable类定义在memtable.h/cc里面。接口如下
size_t ApproximateMemoryUsage()
估计大小,在被修改的时候也可以调用。Iterator* NewIterator()
void Add(SequenceNumber seq, ValueType type, const Slice& key, const Slice& value)
负责插入记录。- type
普通插入type
为kTypeValue。
删除操作实际上是插入type
为kTypeDeletion
的记录。 - key
- type
bool Get(const LookupKey& key, std::string* value, Status* s)
如果存在key对应的记录,返回true,并且将值存在*value
上。
如果存在key被删除的记录,返回true,并且在*status
存入NotFound()
。
否则返回false。
这里LookupKey
的设计较为复杂,稍后讲解。void Ref()
void Unref()
Memtable还有下面一些成员:
KeyComparator comparator_
封装了个InternalKeyComparator
,这一块后面介绍1
2
3
4
5struct KeyComparator {
const InternalKeyComparator comparator;
explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) {}
int operator()(const char* a, const char* b) const;
};int refs_
Arena arena_
Table table_
实际上是个跳表。1
typedef SkipList<const char*, KeyComparator> Table;
Key
Memtable在跳表中索引的Key中存放三个数据:
User Key
用户实际传入的key。Sequence Number
1
typedef uint64_t SequenceNumber;
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。
start_
指向klength,klength表示userkey长度。注意,这里userkey也可以存放InternalKey,所以LookupKey
可以表示一个Memtable Key。1
2
3
4klength varint32 <-- start_
userkey char[klength] <-- kstart_
tag uint64
<-- end_kstart_
end_
1 | class LookupKey { |
总结一下,一个Key中的信息包括:
- klength
- User Key
- Tag
- Sequence Number
- Value Type
其中:
- Memtable Key
1+2+3 - Internal Key
2+3 - User Key
2
比较
我们合成了一个包含三个部分的Internal Key,如果仅仅是这样,直接比较也许还是可行的,毕竟User Key、Seq、Value Type啥的都是有层级的。但是,这些东西是用VarInt存储的,这就不好直接bitwise比较了。
Comparator
接口定义在include/leveldb/comparator.h里面。包含下面一些成员
int Compare(const Slice& a, const Slice& b) const
比较函数void FindShortestSeparator(std::string* start, const Slice& limit)
目的是节约空间。如果*start
这个字符串小于limit
字符串,那么就修改*start
,变成大小在*start
和limit
之间,但是长度最短的字符串。
其方法基于公共前缀,如果*start
是helloWorld
,limit
是helloZookeeper
,那么旧改*start
为helloX
,也就是后面的World
不要了。
【Q】这个功能会用到哪里呢?我觉得在插入是用不上的,因为会涉及修改Key的值。void FindShortSuccessor(std::string* key)
data
在开头存了对应字符串的长度。所以GetLengthPrefixedSlice
会先读取长度到len
里面,这个时候p
前进指向了实际的字符串,然后创建一个Slice。
1 | static Slice GetLengthPrefixedSlice(const char* data) { |
MemTable::KeyComparator
就是获取对应的字符串,然后调用InternalKeyComparator
比较。
1 | int MemTable::KeyComparator::operator()(const char* aptr, |
比较的顺序是:
- User Key升序
- Sequence Number降序
这样,会倾向于找新的 - ValueType降序
但考虑到Sequence Number,大概率用不到。1
2
3
4
5
6
7
8
9
10
11
12
13int 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
需要计算下面几部分:
- K的长度,用VarInt存
这里internal_key_size
为啥要加上8呢?这是因为Sequence Number和Type分别占用了7个byte和1个byte。所以从User Key生成Internal Key的时候要加上这两部分。
这就是Memtable Key,相对于Internal Key多存储的一块数据。 - K本身
也就是Internal Key。 - V的长度
- V本身
1
2
3
4
5
6
7
8
9
10
11
12
13
14void 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 | ... |
查找
首先,从LookupKey中取得memtable_key
,这个是包含了4个部分的。接着获得跳表的迭代器iter
,定位到第一个大于等于memkey
的位置。
我们得到key_ptr
指向Internal Key,key_length
为Internal Key的长度。
1 | bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) { |
接着我们比较Value Type,它在tag的最后一个字节。注意tag的组装方式是(seq << 8) | type
1 | if (comparator_.comparator.user_comparator()->Compare( |
Reference
- https://izualzhy.cn/memtable-leveldb
- https://github.com/yingshin/leveldb_more_annotation/blob/master/db/memtable.h
- https://zhuanlan.zhihu.com/p/79362747
- 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