LevelDB阅读笔记-Memtable
LevelDB中的MemTable
在LevelDB中,MemTable是一个内存数据结构,它被用于暂存写操作,并在合适的时候转换为immutable的memtable,最后转为SSTable文件写入磁盘。MemTable实际上只是一个提供了读写操作的接口,它负责将外界的key-value数据封装,实际的数据存储和查询都是由内部的SkipList
索引来完成的,因此我们将着重分析SkipList的源码。
MemTable
MemTable
类包含了以下数据成员和接口:
class MemTable {
Iterator* NewIterator();
void Add(SequenceNumber seq, ValueType type, const Slice& key,
const Slice& value);
bool Get(const LookupKey& key, std::string* value, Status* s);
private:
struct KeyComparator {
const InternalKeyComparator comparator;
explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) {}
int operator()(const char* a, const char* b) const;
};
typedef SkipList<const char*, KeyComparator> Table;
KeyComparator comparator_;
int refs_;
Arena arena_;
Table table_;
};
MemTable
作为一个内存索引结构,提供了Add()
方法用于插入或删除指定的键值对,Get()
方法用于对指定的key进行点查询,NewIterator
方法提供了获得迭代器的手段,方便用于范围查询。KeyComparator
是一个MemTable
内部的Comparator
, 在后面会看到,MemTable
会将要求插入的key和value按照InternalKey
的方式进行序列化,序列化得到的字节数组是key和value的组合,因此需要一个comparator
来提供对该字节数组的比较功能。SkipList
实现了一个模板跳表类,它是MemTable的核心结构。Arena
是该MemTable的内存分配器,从而避免了多次进行new等调用。reference counter
被用于维护整个MemTable
的生命周期,只有在refs_
大于0时该MemTable才可以被使用,当等于0时,该memtable会被调用delete
释放内存。但MemTable
的析构函数是private
的,这意味着外界无法临时创建一个栈上的MemTable
对象,也无法显式地delete一个动态分配的MemTable
对象。
方法实现
MemTable::Add
Add方法将传入的Key, SequenceNumber, ValueType, Value
等信息序列化为一个字符数组,然后直接调用SkipList
的Insert接口进行插入。重点在于序列化的过程,代码的注释中有明确的说明:
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()]
}
传入的参数先被拼接为一个InternalKey
, 然后将该InternalKey
的长度按照VarInt32编码写入数组头部,然后依次是internal_key, ValueSize和Valuesize。此处不再赘述代码。了解了MemTable内部存储一个key-value pair的格式之后,我们可以简单描述一下KeyComparator
的比较函数的实现:
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);
}
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);
}
KeyComparator
从一个按照上述方式序列化的字符数组中通过GetLengthPrefixedSlice()
调用获得其中的InternalKey
部分,然后直接调用内部保存的InternalKeyComparator
的比较函数进行比较。
GetLenghtPrefixedSlice()
的名字直截了当地说明了该函数的作用,对于以varied int表示长度,随后紧接着key的内容的表示方式,该函数返回一个Slice对象用于引用其内容。而MemTable中经过序列化后的key-value pair正好符合这种模式。
MemTable::Get
MemTable
通过Get
来获得一个指定key对应的value的值,根据注释中的叙述,当在MemTable中找到该key或者该key被删除时,返回true,否则返回false。因此,True实际上说明了该key的最新版本在MemTable中;返回False实际上是提醒调用者该key不在MemTable中,可能需要到SSTable中去找。
Get
调用分为两步,首先调用SkipList
的迭代器的Seek
找到该key的大概位置,然后比较迭代器指向的key是否与User key相同。最后根据类型进行返回。这里比较是否相同时没有使用InternalKeyComparator
比较,而是直接使用InternalKeyComparator
内部的User Key Comparator进行比较。
bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
// Find target key in skiplist
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);
// Check if matches user key
if (comparator_.comparator.user_comparator()->Compare(
Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
// Return based on ValueType
}
}
return false;
}
Iterator
MemTable::Iterator
继承自Iterator
抽象基类,用于负责遍历MemTable
中的元素。一个Iterator
对象提供了多个操作接口用于访问或修改该Iterator对应的元素。为了方便理解,可以将此处的Iterator
接口与STL中的容器迭代器操作接口对比,例如:Iterator::SeekToFirst
对应于std::vector<>::begin()
, Iterator::Next()
对应于std::vector::Iterator::operator++
等等。
由于LevelDB是一个KV存储系统,因此迭代器需要提供key-value的获取接口。Iterator
基类规定了Iterator::key()
和Iterator::value()
接口用于获取迭代器关联元素的key和value,且返回值为Slice
。但LevelDB内部有多种key,因此不同数据结构的迭代器返回的key的类型也不尽相同。例如,MemTable::Iterator
的key的调用返回的是一个InternalKey
, 而SkipList::Iterator
的key调用返回的则是一个以key_length
作为前缀的key的字符序列。
下面简单描述一下MemTableIterator
的实现:
class MemTableIterator : public Iterator {
public:
explicit MemTableIterator(MemTable::Table* table) : iter_(table) {}
MemTableIterator(const MemTableIterator&) = delete;
MemTableIterator& operator=(const MemTableIterator&) = delete;
~MemTableIterator() override = default;
bool Valid() const override { return iter_.Valid(); }
void Seek(const Slice& k) override { iter_.Seek(EncodeKey(&tmp_, k)); }
void SeekToFirst() override { iter_.SeekToFirst(); }
void SeekToLast() override { iter_.SeekToLast(); }
void Next() override { iter_.Next(); }
void Prev() override { iter_.Prev(); }
Slice key() const override { return GetLengthPrefixedSlice(iter_.key()); }
Slice value() const override {
Slice key_slice = GetLengthPrefixedSlice(iter_.key());
return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());
}
private:
MemTable::Table::Iterator iter_;
std::string tmp_; // For passing to EncodeKey
};
MemTableIterator
的迭代功能实际上是通过SkipList
的迭代功能实现的,每当调用SeekToFirst
,Next
等接口时,MemTableIterator
会实际上调用iter_
的对应接口。而对于key(), value(),seek()
等接口,MemTableIterator
需要在SkipList::Iterator
返回的PrefixLengthKey格式与InternalKey
格式之间进行转换。
例如,MemTableIterator
通过EncodeKey
接口将一个InternalKey
转换为PrefixLength格式,并放置在tmp_
中;通过GetLengthPrefixSlice
函数将一个SkipList::Iterator
返回的PrefixLength格式转换为InternalKey
格式。
SkipList
SkipList是一种有序的内存索引结构,它相比红黑树等树形的有序索引实现起来更加简单。在LevelDB中,SkipList作为一个通用的基础组件,被放置在util
文件夹而不是db
文件夹中。SkipList的接口定义如下:
template <typename Key, class Comparator>
class SkipList {
private:
struct Node;
public:
explicit SkipList(Comparator cmp, Arena* arena);
// Insert key into the list.
// REQUIRES: nothing that compares equal to key is currently in the list.
void Insert(const Key& key);
// Returns true iff an entry that compares equal to key is in the list.
bool Contains(const Key& key) const;
class Iterator;
}
SkipList是一个模板类,其中Key
用于指明该有序索引存储的键的类型;Comparator
用于指明该有序索引进行序的比较时使用的方式。SkipList提供了两个公共接口用于使用:
Insert
用于插入一个KeyContains
用于检查指定的key是否存在。- 此外,
SkipList
在内部定义了Iterator
类用于进行范围或者点查询。
Insert过程
SkipList在Insert时会首先找到该key对应的节点应该在的位置,由于LevelDB中的Skiplist每个节点是单向链接的,因此也就需要找到该key应该插入位置的前驱节点。这是通过FindGreaterOrEqual
来实现的,该函数会返回在每一层上新插入节点的前驱节点:
Node* prev[kMaxHeight];
Node* x = FindGreaterOrEqual(key, prev);
// Our data structure does not allow duplicate insertion
assert(x == nullptr || !Equal(key, x->key));
SkipList的算法要求为每个节点随机指定一个高度,如果该高度高于当前SkipList的最高高度,还需要用head
节点来填充prev
数组超出当前最大高度的部分:
int height = RandomHeight();
if (height > GetMaxHeight()) {
for (int i = GetMaxHeight(); i < height; i++) {
prev[i] = head_;
}
max_height_.store(height, std::memory_order_relaxed);
}
到这一步做完,新插入node的所有前驱节点都被正确找到了,只需要按照链表的方式将其链入即可:
x = NewNode(key, height);
for (int i = 0; i < height; i++) {
// NoBarrier_SetNext() suffices since we will add a barrier when
// we publish a pointer to "x" in prev[i].
x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
prev[i]->SetNext(i, x);
}
这里链入的方式是从最底层到最高层链入,目的是为了防止并发情况下的错误。如果先将NewNode从高层链入,假设此时有一个并发的search操作到来,当该search操作到达这个node之后,它可能会顺着该node向下移动,但此时NewNode下层的next指针还没有设置完,从而导致错误。
此处x = NewNode(key, height)
分配了一个高度为height
, 包含键为key
的节点,这里仅仅只是简单将key赋值给Node内部,因为SkipList假设模板参数Key
是可拷贝的。当我们在MemTable
中对其实例化时,对应的Key
为const char*
, key的内容所占用的空间需要在调用SkipList::insert
之前分配。
FindGreaterOrEqual
该函数是实现SkipList
所有操作的核心,包括Insert中找到应该插入的prev
位置,在Contain
函数中找到目标key所在的位置等等。该函数的原型如下:
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
Node** prev) const;
对于输入的key,该函数返回当前SkipList中满足node key >= key
的第一个节点,并且将每一层中,满足node key < key
的最大的节点放入prev数组中。该函数从最高层开始,不断试探下一个节点的key是否小于目标key,如果是,则向前移动;如果不是,则说明当前的节点满足:node->key < key <= node->next->key
,因此将node加入到prev数组中。
Node* x = head_;
int level = GetMaxHeight() - 1;
while (true) {
Node* next = x->Next(level);
if (KeyIsAfterNode(key, next)) {
// Keep searching in this list
x = next;
} else {
if (prev != nullptr) prev[level] = x;
if (level == 0) {
return next;
} else {
// Switch to next list
level--;
}
}
}
除了FindGreaterOrEqual
之外,SkipList
还提供了FindLessThan
, FindLast
等函数,但它们的大体实现细节都与FindGreaterThanOrEqual
无异,此处不再赘述。
SkipList搜索过程
SkipList
内部定义了Iterator
类,但该类并不直接继承leveldb的Iterator
类,因为SkipList
作为一个utility, 并不属于db定义的一部分。也正是因为这个原因,SkipList::Iterator
是定义在SkipList
内部的,而且它不会支持一些Iterator
抽象接口定义的操作,例如value()
等。
SkipList的Iterator包含了两个成员,一是该迭代器索引元素所在的跳表,二是其对应元素的节点:
template<typename Key, class Comparator>
class SkipList {
...
class Iterator {
SkipList* list_;
Node* node_;
};
}
Iterator
通过调用list_
的相关成员函数来修改保存的node_
节点,从而实现指向不同元素的功能。以Seek()
实现为例,该迭代器接口修改迭代器使其指向第一个比目标key大或相等的节点,其本质只是调用了SkipList
的FindGreaterOrEqual
函数:
template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
node_ = list_->FindGreaterOrEqual(target, nullptr);
}
其他迭代器接口也是类似的实现。值得注意的是,由于这里Iterator
是SkipList
的嵌套类,因此它有权访问SkipList
类的所有成员,包括私有成员。但是SkipList
无权访问嵌套类Iterator
的私有成员。
小结
本节我们简单介绍了MemTable
以及SkipList
的实现原理,MemTable
作为一个内存缓冲区,其索引是可以替换的,只是在LevelDB中采用了SkipList,所以这两部分分开构建。MemTable
负责接受外界Insert, Delete, Get
请求并将其序列化为SkipList
可接受的数据格式;SkipList
负责有序索引的实现逻辑。
一些有用的启发包括:使用迭代器实现Get
操作,从而减少重复逻辑的书写。