leveldb 源码分析 3¶
本系列《leveldb 源码分析》共有 22 篇文章,这是第三篇。
4. Memtable 之一¶
Memtable 是 leveldb 很重要的一块,leveldb 的核心之一。我们肯定 关注 KV 数据在 Memtable 中是如何组织的,秘密在 Skip list 中。
4.1 用途¶
在 Leveldb 中,所有内存中的 KV 数据都存储在 Memtable 中,物理 disk 则存储在 SSTable 中。在系统运行过程中,如果 Memtable 中的数据占用内存到达指定值 (Options.write_buffer_size),则 Leveldb 就自动将 Memtable 转换为 Immutable Memtable,并自动生成新的 Memtable,也就是 Copy-On-Write 机制 了。
Immutable Memtable 则被新的线程 Dump 到磁盘中,Dump 结束则该 Immutable Memtable 就可以释放了。因名知意,Immutable Memtable 是只读的。
所以可见,最新的数据都是存储在 Memtable 中的,Immutable Memtable 和物理 SSTable 则是某个时点的数据。
为了防止系统 down 机导致内存数据 Memtable 或者 Immutable Memtable 丢失,leveldb 自然也 依赖于 log 机制来保证可靠性 了。
Memtable 提供了写入 KV 记录,删除以及读取 KV 记录的接口,但是事实上Memtable 并不执行真正的删除操作,删除某个 Key 的 Value 在 Memtable 内是作为插入一条记录实施的,但是会打上一个 Key 的删除标记,真正的删除操作在后面的 Compaction 过程中,lazy delete。
4.2 核心是 Skip list¶
另外,Memtable 中的 KV 对是根据 Key 排序的,leveldb 在插入等操作时保证 key 的有序性。想想,前面看到的 Skip list 不正是合适的人选吗,因此 Memtable 的核心数据结构是一个 Skip list,Memtable 只是一个接口类。当然随之而来的一个问题就是 Skip list 是如何组织 KV 数据对的,在后面分析 Memtable 的插入、查询接口时我们将会看到答案。
4.3 接口说明¶
先来看看 Memtable 的接口:
void Ref() { ++refs_; }
void Unref();
Iterator* NewIterator();
void Add(SequenceNumber seq,
ValueType type,
const Slice& key,
const Slice& value);
bool Get(const LookupKey& key, std::string* value, Status* s);
首先 Memtable 是基于引用计数的机制,如果引用计数为 0,则在 Unref 中删除自己,Ref 和 Unref 就是干这个的。
- NewIterator 是返回一个迭代器,可以遍历访问 table 的内部数据,很好的设计思想,这种方式隐藏了 table 的内部实现。外部调用者必须保证使用 Iterator 访问 Memtable 的时候该 Memtable 是 live 的。
- Add 和 Get 是添加和获取记录的接口,没有 Delete,还记得前面说过,memtable 的 delete 实际上是插入一条 type 为 kTypeDeletion 的记录。
4.4 类图¶
先来看看 Memtable 相关的 整体类层次 吧,并不复杂,还是相当清晰的。见图 4.4-1。
4.5 Key 结构¶
Memtable 是一个 KV 存储结构,那么这个 key 肯定是个重点 了,在分析接口实现之前,有必要仔细分析一下 Memtable 对 key 的使用。
这里面有 5 个 key 的概念,可能会让人混淆,下面就来一个一个的分析。
4.5.1 InternalKey & ParsedInternalKey & User Key¶
InternalKey 是一个复合概念,是有几个部分组合成的一个 key,ParsedInternalKey 就是对 InternalKey 分拆后的结果,先来看看 ParsedInternalKey 的成员,这是一个 struct:
Slice user_key;
SequenceNumber sequence;
ValueType type;
也就是说 InternalKey 是由 User key + SequenceNumber + ValueType 组合而成的,顺便先分析下几个 Key 相关的函数,它们是了解 Internal Key 和 User Key 的关键。
首先是 InternalKey 和 ParsedInternalKey 相互转换的两个函数,如下。
bool ParseInternalKey (const Slice& internal_key,
ParsedInternalKey* result);
void AppendInternalKey (std::string* result,
const ParsedInternalKey& key);
函数实现很简单,就是字符串的拼接与把字符串按字节拆分,代码略过。根据实现,容易得到 InternalKey 的格式 为:
| User key (string) | sequence number (7 bytes) | value type (1 byte) |
由此还可知道 sequence number 大小是 7 bytes,sequence number 是所有基于 op log 系统的关键数据,它唯一指定了不同操作的时间顺序。
把 user key 放到前面的原因 是,这样对同一个 user key 的操作就可以按照 sequence number 顺序连续存放了,不同的 user key 是互不相干的,因此把它们的操作放在一起也没有什么意义。
另外用户可以为 user key 定制比较函数,系统默认是字母序的。
下面的两个函数是分别从 InternalKey 中拆分出 User Key 和 Value Type 的,非常直观,代码也附上吧。
inline Slice ExtractUserKey(const Slice& internal_key)
{
assert(internal_key.size() >= 8);
return Slice(internal_key.data(), internal_key.size() - 8);
}
inline ValueType ExtractValueType(const Slice& internal_key)
{
assert(internal_key.size() >= 8);
const size_t n = internal_key.size();
uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
unsigned char c = num & 0xff;
return static_cast<ValueType>(c);
}
4.5.2 LookupKey & Memtable Key¶
Memtable 的 查询接口传入的是 LookupKey,它也是由 User Key 和 Sequence Number 组合而成的,从其构造函数:
LookupKey(const Slice& user_key, SequenceNumber s)
中分析出 LookupKey 的格式为:
| Size (int32变长)| User key (string) | sequence number (7 bytes) | value type (1 byte) |
两点:
- 这里的 Size 是 user key 长度 +8,也就是整个字符串长度了;
- value type 是 kValueTypeForSeek,它等于 kTypeValue。
由于 LookupKey 的 size 是变长存储的,因此它使用 kstart_ 记录了 user key string 的起始地址,否则将不能正确的获取 size 和 user key;
LookupKey 导出了三个函数,可以分别从 LookupKey 得到 Internal Key,Memtable Key 和 User Key,如下:
// 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); }
其中 start_ 是 LookupKey 字符串的开始,end_ 是结束,kstart_ 是 start_+4,也就是 user key 字符串的起始地址。