本系列《leveldb源码分析》共有22篇文章,这是第三篇。
Memtable是leveldb很重要的一块,leveldb的核心之一。我们肯定关注KV数据在Memtable中是如何组织的,秘密在Skip list中。
在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。
另外,Memtable中的KV对是根据Key排序的,leveldb在插入等操作时保证key的有序性。想想,前面看到的Skip list不正是合适的人选吗,因此Memtable的核心数据结构是一个Skip list,Memtable只是一个接口类。当然随之而来的一个问题就是Skip list是如何组织KV数据对的,在后面分析Memtable的插入、查询接口时我们将会看到答案。
先来看看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就是干这个的。
先来看看Memtable相关的整体类层次吧,并不复杂,还是相当清晰的。见图4.4-1。
Memtable是一个KV存储结构,那么这个key肯定是个重点了,在分析接口实现之前,有必要仔细分析一下Memtable对key的使用。
这里面有5个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);
}
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) |
两点:
由于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字符串的起始地址。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。