本文介绍leveldb中内存库memtable的实现。
memtable是leveldb中的内存库， 写入的数据都会先写到memtable中，然后通过合库的方式落到磁盘。检索时也是先检索内存库memtable。
1 memtable的数据结构
class MemTable {
public:
// MemTables are reference counted.The initial reference count
// is zero and the caller must call Ref() at least once.
explicit MemTable(const InternalKeyComparator& comparator);
// Increase reference count.
void Ref() { ++refs_;
}// Drop reference count.Delete if no more references exist.
void Unref() {
--refs_;
assert(refs_ >= 0);
if (refs_ <= 0) {
delete this;
}
}typedef SkipList Table;
KeyComparator comparator_;
int refs_;
Arena arena_;
Table table_;
};
【【leveldb】memtable内存数据库的实现】如上，memtable 是由一个 跳表 SkipList实现。使用arena_ 进行内存管理；使用引用计数共享memtable减少内存copy。
2 数据写入
add的时候，将 原始key和value 转换为特定的格式之后，写入 skiplist 。同样的key在 skiplist会被覆盖掉，这个可以看下skiplist的具体实现，所以memtable中不存在相同的key。
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();
size_t internal_key_size = key_size + 8;
const size_t encoded_len =
VarintLength(internal_key_size) + internal_key_size +
VarintLength(val_size) + val_size;
char* buf = arena_.Allocate(encoded_len);
char* p = EncodeVarint32(buf, internal_key_size);
memcpy(p, key.data(), key_size);
p += key_size;
EncodeFixed64(p, (s << 8) | type);
p += 8;
p = EncodeVarint32(p, val_size);
memcpy(p, value.data(), val_size);
assert((p + val_size) - buf == encoded_len);
table_.Insert(buf);
}memtable中key和value的内存格式如下：
文章图片
其中 key_size + 8和 value_size 这些数值类型的存储，使用的是 变长存储，
具体方法是 将每个字节的最高位作为标志位，最高位=1，表示还需下一个字节；=0，则表示是最后一个字节，
这样，32位的数值最多需要5个字节存储，但是在大多情况下，小数值居多，所以这样一来也可以进行内存压缩，节约内存。这种varint形式的存储方式，应用在很多地方，protobuf中就用到了varint的方法来压缩数字类型的数据。
sequence_num + valuetype 加起来占用8个字节，高7个字节存储sequence_num， 低1个字节存储 valuetype。
valuetype代表了两种操作，一种kTypeValue 代表写入；一种 kTypeDeletion代表删除，删除的动作在合库的时候执行。
3 检索
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:
//klengthvarint32
//userkeychar[klength]
//taguint64
//vlengthvarint32
//valuechar[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;
const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
if (comparator_.comparator.user_comparator()->Compare(
Slice(key_ptr, key_length - 8),
key.user_key()) == 0) {
// Correct user key
const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
switch (static_cast(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;
} 检索时输入的key是一个lookupKey对象。lookupKey对象将用户原始key，转为memtable中key存储的方式，其中 memtable_key 包括了key_size + 8 、 key 、 sequence_num + valuetype; user_key 就是原始的key
以 memtable_key 从 skiplist中检索， 将检索到的数据中原始key 和 输入原始key进行比较，当查找到的是 删除 数据时，返回 空结果。
