This action will force synchronization from balloonwj/CppGuide, which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
本系列《leveldb源码分析》共有22篇文章,这是第三篇。
Memtable是leveldb很重要的一块,leveldb的核心之一。我们肯定关注KV数据在Memtable中是如何组织的,秘密在Skip list中。
在Leveldb中,所有内存中的KV数据都存储在Memtable中,物理disk则存储在SSTable中。在系统运行过程中,如果Memtable中的数据占用内存到达指定值(Options.write_buffer_size),则Leveldb就自动将Memtable转换为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字符串的起始地址。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。