LevelDB MemTable
简介
LevelDB 的 MemTable 使用跳表实现，MemTable 是内存中的结构，支持插入和查找操作，支持一写多读。当 Memtable 中的数据占用内存大小达到 write_buffer_size 则将被转换为 Immutable Memtable ，同时创建一个新的 Memtable ，Immutable Memtable 会在后台被 dump 成 SSTable 。
这里存在的问题是，Immutable MemTable 没有及时 dump 的话，会阻塞新的 Memtable 的创建，阻塞写请求。
用户接口与数据模型
class MemTable {
// Returns an estimate of the number of bytes of data in use by this
// data structure. It is safe to call when MemTable is being modified.
size_t ApproximateMemoryUsage();
// Return an iterator that yields the contents of the memtable.
//
// The caller must ensure that the underlying MemTable remains live
// while the returned iterator is live. The keys returned by this
// iterator are internal keys encoded by AppendInternalKey in the
// db/format.{h,cc} module.
Iterator* NewIterator();
// Add an entry into memtable that maps key to value at the
// specified sequence number and with the specified type.
// Typically value will be empty if type==kTypeDeletion.
void Add(SequenceNumber seq, ValueType type, const Slice& key,
const Slice& value);
// If memtable contains a value for key, store it in *value and return true.
// If memtable contains a deletion for key, store a NotFound() error
// in *status and return true.
// Else, return false.
bool Get(const LookupKey& key, std::string* value, Status* s);
};TODO: 迭代器的实现没有按快照隔离
键值编码
MemTable 的 key 称为 internalKey，由三部分组成：
用户定义的 key :
- 序列号
- leveldb 中，每一次写操作都有一个 sequence number，标志着写入操作的先后顺序。由于在 leveldb中，可能会有多条相同 key 的数据项同时存储在数据库中，因此需要有一个序列号来标识这些数据项的新旧情况。序列号最大的数据项为最新值
- 类型
- 标志本条数据项的类型，为更新还是删除
| uKey(n bytes) | sequence number(7 bytes) | type (1 byte) |
MemTable 将 Internalkey 和 Value 拼在一起作为 SkipList 的 Key ：
| klength | internal key | vlength | value |
|---|---|---|---|
| varint32 | klength bytes | varint32 | vlength bytes |
排序由 InternalKeyComparator 实现，按：
- uKey 升序
- Sequence Number 降序
- type 降序
内存分配
MemTable 通过 LevelDB Arena 进行内存分配和使用统计，只提供内存分配的接口，内存资源释放跟随 Arena 释放进行销毁，很适合 MemTable 只增不删的特点。