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用于插入一个Key
• Contains用于检查指定的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操作，从而减少重复逻辑的书写。