leveldb之二:MemTable

    #leveldb #memtable

    前面介绍了 skiplist ,skiplist 是 leveldb 里一个非常重要的数据结构,实现了高效的数据查找与插入(O(logn))。

    但是 skiplist 的最小元素是Node,存储单个元素。而 leveldb 是一个单机的 {key, value} 数据库,那么 kv 数据如何作为Node存储到 skiplist?如何比较数据来实现查找的功能?leveldb 的各个接口及参数,是如何生效到 skiplist的?

    这些问题,在MemTable中能够找到答案。

    1. MemTable 简述

    使用 leveldb 写入的数据,为了提供更快的查找性能,部分数据在内存中也会存储一份,这部分数据就使用MemTable存储。

    MemTable初始化时接收一个用于比较的对象,该对象可以比较 key 用于 skiplist 的排序。

    explicit MemTable(const InternalKeyComparator& comparator);
    

    与 leveldb 对外的接口类似,MemTable也提供了Add Get两个接口

    void Add(SequenceNumber seq, ValueType type,
            const Slice& key,
            const Slice& value);
    
    bool Get(const LookupKey& key, std::string* value, Status* s);
    

    其中key value即用户指定的值,seq是一个整数值,随着写入操作递增,因此seq越大,该操作越新。type表示操作类型:

    1. 写入
    2. 删除。

    Status是 leveldb 的一个辅助类,在返回值的表示上更加丰富。类本身比较简单,不过设计还是挺巧妙的,之后会写篇笔记介绍下。

    同时MemTable还通过迭代器的形式,暴露底层的 skiplist :

    Iterator* MemTable::NewIterator() {
      return new MemTableIterator(&table_);
    }
    

    因此MemTableIterator实现上也是操作 skiplist 的迭代器。

    table_就是底层的 skiplist ,负责管理数据。

      struct KeyComparator {
        const InternalKeyComparator comparator;
        explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { }
        int operator()(const char* a, const char* b) const;
      };
      friend class MemTableIterator;
      friend class MemTableBackwardIterator;
    
      typedef SkipList<const char*, KeyComparator> Table;
    
      KeyComparator comparator_;
      int refs_;
      Arena arena_;
      Table table_;
    

    存储类型为const char*,比较方式为KeyComparator

    接下来分别介绍下。

    2. 存储的数据格式

    用户调用 leveldb 接口指定的 key,到了MemTable增加了SequenceNumValueType,以及指定的 value,这些数据都会存储到 skiplist,具体格式如下:

    memtable key

    varint encode的操作在protobuf varint 里也介绍过,主要的特点是:

    1. 整数由定长改为变长存储
    2. 小整数仅占用1个字节,随着数值变大占用的字节数也变大,最多占用5个字节。

    具体原理可以参考上面的笔记。

    存储数据的整体思路跟 protobuf 序列化类似,还是|len(key) |key |len(value) |value |的格式,然后是encode sequence type这些技巧。

    sequencetype分别占用7bytes和1bytes,其中sequence是一个随着写入操作单调递增的值:

    typedef uint64_t SequenceNumber;
    

    type是一个枚举变量,表示写入/删除操作

    // Value types encoded as the last component of internal keys.
    // DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
    // data structures.
    enum ValueType {
      kTypeDeletion = 0x0,
      kTypeValue = 0x1
    };
    
    //用于查找
    static const ValueType kValueTypeForSeek = kTypeValue;
    

    如注释所说,type作为 internal key 的最后一个 component

    MemTable相关的有多种 key,本质上就是上图里三种:

    1. userkey: 用户传入的 key,即用户key.
    2. internal key: 增加了sequence type,用于支持同一 key 的多次操作,以及 snapshot,即内部key.
    3. memtable key: 增加了 varint32 encode 后的 internal key长度

    用于辅助的类有多个,例如LookupKey ParsedInternalKey InternalKey,其中跟MemTable用到了LookupKey

    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();
    
      // 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); }
    
     private:
      // We construct a char array of the form:
      //    klength  varint32               <-- start_
      //    userkey  char[klength]          <-- kstart_
      //    tag      uint64 //sequence && ValueType合称tag
      //                                    <-- end_
      // The array is a suitable MemTable key.
      // The suffix starting with "userkey" can be used as an InternalKey.
      const char* start_;
      const char* kstart_;
      const char* end_;
      //为了避免内存碎片 or 提高性能?
      char space_[200];      // Avoid allocation for short keys
        };
    

    对照前面的图 或者 注释,可以找到几个变量start_ kstart_ end_的位置。

    对比下构造函数看下代码更清楚些(shou me the code.🙂)

    static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
      assert(seq <= kMaxSequenceNumber);
      assert(t <= kValueTypeForSeek);
      return (seq << 8) | t;
    }
    
    LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
      size_t usize = user_key.size();
      //SequenceNumber + ValueType占8个字节,encode(internal_key_size)至多占5个字节,因此预估至多+13个字节
      size_t needed = usize + 13;  // A conservative estimate
      char* dst;
      if (needed <= sizeof(space_)) {
        dst = space_;
      } else {
        dst = new char[needed];
      }
      //start_指向最开始位置
      start_ = dst;
      //memtable的internal_key_size=usize+8,对应MemTable::Add实现。
      dst = EncodeVarint32(dst, usize + 8);
      //kstart_指向userkey开始位置
      kstart_ = dst;
      memcpy(dst, user_key.data(), usize);
      dst += usize;
      EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
      dst += 8;
      //end_指向(s << 8 | type)的下一个字节
      end_ = dst;
    }
    

    EncodeFixed64如果是小端,则直接内存 copy;如果是大端,则反向 copy,固定占用8bytes。

    3. 数据怎么比较

    整条数据写入 skiplist 后,使用 naive 的比较方式肯定行不通:

    1. 前面字节是 internal key经过 varint encode 后的长度,比较这个长度没有意义。
    2. 用户如果写入两次,例如先 add {“JeffDean”: “Google”},然后 add {“Jeff Dean”:”Bidu”},预期查找的结果肯定是后者。

    MemTable里,使用KeyComparator比较,作为Skiplist的第二个模板参数

      struct KeyComparator {
        const InternalKeyComparator comparator;
        explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { }
        int operator()(const char* a, const char* b) const;
      };
    

    operator()负责解析出 internal key,交给 comparator 比较:

    int MemTable::KeyComparator::operator()(const char* aptr, const char* bptr)
        const {
      // Internal keys are encoded as length-prefixed strings.
      // 分别获取internal_key并比较
      Slice a = GetLengthPrefixedSlice(aptr);
      Slice b = GetLengthPrefixedSlice(bptr);
      return comparator.Compare(a, b);
    }
    

    可以看到调用了InternalKeyComparator::Compare接口:

    class InternalKeyComparator : public Comparator {
     private:
      const Comparator* user_comparator_;
     public:
      explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }
      virtual const char* Name() const;
      //从slice里解析出userkey,与8字节的tag:(sequence << 8) | type
      //userkey按照字母序比较
      //如果userkey相同,则tag按大小逆序比较,即sequence越大越靠前
      virtual int Compare(const Slice& a, const Slice& b) const;
      ...
    };
    

    其中user_comparator_默认为BytewiseComparator,即按照字节大小排序。

    Compare具体的实现:

    int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
      // Order by:
      //    increasing user key (according to user-supplied comparator)
      //    decreasing sequence number
      //    decreasing type (though sequence# should be enough to disambiguate)
      //    首先比较userkey,即用户写入的key
      int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
      // 如果是同一个userkey,继续判断tag是否相等
      if (r == 0) {
        //sequence越大,排序结果越小
        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;
    }
    

    总结一下主要是两条:

    1. userkey 按照指定的排序方式,默认字节大小排序,akey-userkey < bkey-userkey 则返回-1.
    2. 如果 userkey 相等,那么解析出 sequence,按照 sequence 大小逆序排序,即 akey-sequence > bkey-sequence 则返回-1.sequence越大则代表数据越新,这样的好处是越新的数据越排在前面。

    注:DecodeFixed64解析出的实际上是sequence << 8 | type,因为 sequence 占高位,因此直接比较大小也能代表sequence

    4. Add/Get操作

    Add过程的代码就是组装memtable key,然后调用SkipList接口写入。

    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();
      //InternalKey长度 = UserKey长度 + 8bytes(存储SequenceNumber + ValueType)
      size_t internal_key_size = key_size + 8;
      //用户写入的key value在内部实现里增加了sequence type
      //而到了MemTable实际按照以下格式组成一段buffer
      //|encode(internal_key_size)  |key  |sequence  type  |encode(value_size)  |value  |
      //这里先计算大小,申请对应大小的buffer
      const size_t encoded_len =
          VarintLength(internal_key_size) + internal_key_size +
          VarintLength(val_size) + val_size;
      char* buf = arena_.Allocate(encoded_len);
      //append key_size
      char* p = EncodeVarint32(buf, internal_key_size);
      //append key bytes
      memcpy(p, key.data(), key_size);
      p += key_size;
      //append sequence_number && type
      //64bits = 8bytes,前7个bytes存储s,最后一个bytes存储type.
      //这里8bytes对应前面 internal_key_size = key_size + 8
      //也是Fixed64而不是Varint64的原因
      EncodeFixed64(p, (s << 8) | type);
      p += 8;
      //append value_size
      p = EncodeVarint32(p, val_size);
      //append value bytes
      memcpy(p, value.data(), val_size);
      assert(p + val_size == buf + encoded_len);
      //写入table_的buffer包含了key/value及附属信息
      table_.Insert(buf);
    }
    

    Get通过SkipList::Iterator::Seek接口获取第一个operator >=的 Node。传入的第一个参数是LookupKey包含了 userkey,同时指定了一个较大的SequenceNumber s(具体多么大我们后续分解),而根据InternalKeyComparator的定义,返回值有两种情况:

    1. 如果该 userkey 存在,返回小于 s 的最大 sequence number 的 Node.
    2. 如果 userkey 不存在,返回第一个 > userkey 的 Node.
    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;
        //解析出internal_key的长度存储到key_length
        //key_ptr指向internal_key
        const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
        //Seek返回的是第一个>=key的Node(>= <=> InternalKeyComparator::Compare)
        //因此先判断下userkey是否相等
        if (comparator_.comparator.user_comparator()->Compare(
                Slice(key_ptr, key_length - 8),
                key.user_key()) == 0) {
          // Correct user key
          // tag = (s << 8) | type
          const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
          //type存储在最后一个字节
          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;
    }
    

    5. 参考

    本文MemTable的注释都ci到了leveldb_more_annotation