简介

在之前的文章中我们知道RocksDB每一次写入，都是先写WAL，然后写Memtable,这次我们就来分析下MemTable的实现.

在RocksDB中，每个ColumnFamily都有自己的Memtable,互不影响．而在RocksDB中Memtable有多种实现(SkipList/HashSkipList/HashLinkList/Vector),具体的区别可以看这里,我们这次主要来分析默认的实现skiplist(只有skiplist是可以并发插入的).

实现

首先从创建Memtable开始，Memtable的创建(ColumnFamilyData::CreateNewMemtable)是在创建ColumnFamily(VersionSet::CreateColumnFamily)的时候创建的．这里就是创建memtable,然后设置到ColumnFamilyData的mem_域中．

  1. MemTable* ColumnFamilyData::ConstructNewMemtable(
  2.     const MutableCFOptions& mutable_cf_options, SequenceNumber earliest_seq) {
  3.   return new MemTable(internal_comparator_, ioptions_, mutable_cf_options,
  4.                       write_buffer_manager_, earliest_seq, id_);
  5. }
  6. void ColumnFamilyData::CreateNewMemtable(
  7.     const MutableCFOptions& mutable_cf_options, SequenceNumber earliest_seq) {
  8.   if (mem_ != nullptr) {
  9.     delete mem_->Unref();
  10.   }
  11.   SetMemtable(ConstructNewMemtable(mutable_cf_options, earliest_seq));
  12.   mem_->Ref();
  13. }

上面所提及的，RocksDB有多种MemTable的实现，那么它是如何来做的呢，RocksDB通过memtable_factory来根据用户的设置来创建不同的memtable.这里要注意的是核心的memtable实现是在MemTable这个类的table_域中.

  1. MemTable::MemTable:
  2.       table_(ioptions.memtable_factory->CreateMemTableRep(
  3.           comparator_, &arena_, ioptions.prefix_extractor, ioptions.info_log,
  4.           column_family_id)),
  7. class MemTableRepFactory {
  8.  public:
  9.   virtual ~MemTableRepFactory() {}
  11.   virtual MemTableRep* CreateMemTableRep(const MemTableRep::KeyComparator&,
  12.                                          Allocator*, const SliceTransform*,
  13.                                          Logger* logger) = 0;
  14.   virtual MemTableRep* CreateMemTableRep(
  15.       const MemTableRep::KeyComparator& key_cmp, Allocator* allocator,
  16.       const SliceTransform* slice_transform, Logger* logger,
  17.       uint32_t /* column_family_id */) {
  18.     return CreateMemTableRep(key_cmp, allocator, slice_transform, logger);
  19.   }
  20. ........................

然后最后会调用对应的实现的CreateMemTableRep方法，这里我们就来看SkipList的实现．

  1. MemTableRep* SkipListFactory::CreateMemTableRep(
  2.     const MemTableRep::KeyComparator& compare, Allocator* allocator,
  3.     const SliceTransform* transform, Logger* /*logger*/) {
  4.   return new SkipListRep(compare, allocator, transform, lookahead_);
  5. }

最终就是创建SkipListRep对象，在这个对象里面会创建SkipList(class InlineSkipList).

  1. class SkipListRep : public MemTableRep {
  2.   InlineSkipList<const MemTableRep::KeyComparator&> skip_list_;
  3. ...................................
  4. public:
  5.  explicit SkipListRep(const MemTableRep::KeyComparator& compare,
  6.                       Allocator* allocator, const SliceTransform* transform,
  7.                       const size_t lookahead)
  8.      : MemTableRep(allocator),
  9.        skip_list_(compare, allocator),
  10.        cmp_(compare),
  11.        transform_(transform),
  12.        lookahead_(lookahead) {}

这里SkipList就不分析实现了，如果对这个数据结构不了解的，可以去WIKI看一下．这里我们只需要知道最终所有的memtable数据都是保存在SkipList中就可以了.

在之前的分析中我们知道Memtable的插入是通过WriteBatch然后遍历ColumnFamily来插入的，而最终则是会调用MemTable::Add这个函数.

  1. bool MemTable::Add(SequenceNumber s, ValueType type,
  2.                    const Slice& key, /* user key */
  3.                    const Slice& value, bool allow_concurrent,
  4.                    MemTablePostProcessInfo* post_process_info) {
  5. bool res = table->InsertKeyConcurrently(handle);
  6.     if (UNLIKELY(!res)) {
  7.       return res;
  8.     }
  9. ..............................
  10.                    }

最终会调用InlineSkipList来对数据进行插入.

  1. template <class Comparator>
  2. bool InlineSkipList<Comparator>::InsertConcurrently(const char* key) {
  3.   Node* prev[kMaxPossibleHeight];
  4.   Node* next[kMaxPossibleHeight];
  5.   Splice splice;
  6.   splice.prev_ = prev;
  7.   splice.next_ = next;
  8.   return Insert<true>(key, &splice, false);
  9. }

看到这里或许会有疑问了，那就是skiplist里面只有key,而RocksDB是一个ＫＶ存储，那么这个KV是如何存储的呢，这里是这样的，RocksDB会将KV打包成一个key传递给SkipList, 对应的KEY的结构是这样的.

  1.   // Format of an entry is concatenation of:
  2.   //  key_size     : varint32 of internal_key.size()
  3.   //  key bytes    : char[internal_key.size()]
  4.   //  value_size   : varint32 of value.size()
  5.   //  value bytes  : char[value.size()]

而数据的格式化就在之前的MemTable::Add中实现的.

  1. uint32_t key_size = static_cast<uint32_t>(key.size());
  2.   uint32_t val_size = static_cast<uint32_t>(value.size());
  3.   uint32_t internal_key_size = key_size + 8;
  4.   const uint32_t encoded_len = VarintLength(internal_key_size) +
  5.                                internal_key_size + VarintLength(val_size) +
  6.                                val_size;
  7.   char* buf = nullptr;
  8.   std::unique_ptr<MemTableRep>& table =
  9.       type == kTypeRangeDeletion ? range_del_table_ : table_;
  10.   KeyHandle handle = table->Allocate(encoded_len, &buf);
  12.   char* p = EncodeVarint32(buf, internal_key_size);
  13.   memcpy(p, key.data(), key_size);
  14.   Slice key_slice(p, key_size);
  15.   p += key_size;
  16.   uint64_t packed = PackSequenceAndType(s, type);
  17.   EncodeFixed64(p, packed);
  18.   p += 8;
  19.   p = EncodeVarint32(p, val_size);
  20.   memcpy(p, value.data(), val_size);

而对于真正的KEY的解析是在SkipList的Comparator中实现的(compare_).下面的代码片段可以看到会解析出来真正的key,然后再进行查找以及插入.

  1. bool InlineSkipList<Comparator>::Insert(const char* key, Splice* splice,
  2.                                         bool allow_partial_splice_fix) {
  3.   Node* x = reinterpret_cast<Node*>(const_cast<char*>(key)) - 1;
  4.   const DecodedKey key_decoded = compare_.decode_key(key);
  5. ...............................
  6.                                         }