LevelDB源码4：Memtable

设计

MemTable是一个内存数据结构，简单说它就是一个SortedMap：

• MemTable是一个Map，提供了Get接口，也就是可以快速地根据键查找到值，也可以使用Put接口插入Kv。
• MemTable是Sorted，也就是里面存储的键都是有序的，可以按照键的顺序迭代Map，或者做范围查询。

有了MemTable提供的Get和Put，就有了一个简单的内存Kv数据库，可以实现Kv的查询，插入和范围查询。

Put，Delete，Update实际上都是一个Put。

Update：等价于新插一个同样的key（LevelDB中没有Update）。

Delete：将当前最新的key插入空，并且标志置为删除。

因为MemTable是内存数据结构，不需要磁盘IO，所以读写的速度非常快，所以就达到了场景需求：高效的写性能。然而这会有个问题，当数据库实例崩溃、宕机或者停机维护的时候，存储的数据就会丢失，这时候需要持久化数据。

class MemTable {
  typedef SkipList<const char*, KeyComparator> Table;
  KeyComparator comparator_;
  int refs_;
  Arena arena_;
  Table table_;
};

key

LookupKey = memtableKey = klength+internalKey
ParsedInternalKey = InternalKey = User key + Sequence + Type
其中ParsedInternalKey ，LookupKey是辅助类，相当于是概念上key的实现

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

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

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

ParsedInternalKey

struct ParsedInternalKey {
  Slice user_key;
  SequenceNumber sequence;
  ValueType type;
};

在Memtabl核心的数据结构跳表SkipList中，里面保存的每一个节点Node（table\_.Insert(buf)），就是一个key-value，其格式：
:::info
memtable key的形式：internal_key_size | internal_key（user_key，seq，type）| val_size|value

sstable key保存的形式：shared_length | non_shared | non_shared_key_contents | val_size|value
:::

InternalKey和ParsedInternalKey相互转换的两个函数：

ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
      : user_key(u), sequence(seq), type(t) {}

void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
  result->append(key.user_key.data(), key.user_key.size());
  PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
}

LookupKey

class LookupKey {
 private:
  // We construct a char array of the form:
  //    klength  varint32               <-- start_
  //    userkey  char[klength]          <-- kstart_
  //    tag      uint64
  //                                    <-- 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_;
  char space_[200];  // Avoid allocation for short keys
};

LookupKey格式：

比较器

默认字节大小排序。可以用户自定义。