首页 > 代码库 > leveldb源码分析--Memtable
leveldb源码分析--Memtable
本节讲述内存中LevelDB的数据结构Memtable,Memtable义如其名即为内存中的KV Table,即LSM-Tree中的C0 Tree。我们知道在LSM-Tree中刚插入的的KV数据都是存储在内存中,当内存中存储的数据超过一定量以后再写到磁盘中。而对于leveldb来说这个过程演变为内存中的数据都是插入到MemTable中,当MemTable中的数据超过一定量(Options.write_buffer_size)以后MemTable就转化为Immutable Memtable等待dump到磁盘中的SSTable中。Immutable Memtable从结构上讲和Memtable是完全一样的,区别仅仅在于其是只读的,不允许写入操作,而Memtable则是允许写入和读取的,而当MemTable转化为Immutable MemTable时会生成一个MemTable。
为了理解MemTable,我们首先看一下他包含了那些成员变量
typedef SkipList<const char*, KeyComparator> Table; KeyComparator comparator_; //比较器,用来判断Key的顺序,稍后介绍 int refs_; //引用计数,当引用为0时作一个自我销毁 Arena arena_; //简易的内存池 Table table_; //保存KV对的实际结构,其为一个SkipList
上文提到了当内存中的数据超过一定的量时,MemTable就会转化为Immutable Table,这个量的管理和判断就是通过Arena来实现的。它的工作十分简单,将申请到的内存块放入std::vector blocks_中,在Arena的生命周期结束后,统一释放掉所有申请到的内存,内部结构如图所示:
只是在处理时涉及到了一个小技巧,Arena会先预先分配一块4K大小的内存,如果后继有内存请求就从其中进行获取,如果剩下的空间不够请求就又两种处理方式:1. 申请大小 > 1K,那么直接申请一块新的对应的大小并存入vector中;2. 申请大小 <= 1K, 申请一块4K的内存,然后在其中分配相应大小的空间给请求者。
Arena主要提供了两个申请函数:其中一个直接分配内存,另一个可以申请对齐的内存空间。这种设计应该说这是和leveldb特定的应用场景相关的,比如一个memtable使用一个Arena,当memtable被释放时,由Arena统一释放其内存。而小内存预先分配的方式可以有效减少内存申请的系统调用的次数,降低对应的开销。理解了流程,我们还是看看代码吧:
char* alloc_ptr_; //当前预分配的4K的地址指针 size_t alloc_bytes_remaining_; //预分配内存尚未使用的大小 std::vector<char*> blocks_; //已经分配的内存地址指针集合 size_t blocks_memory_; //已经分配的内存大小
申请流程,只列出申请不不对齐的方法,申请对齐的内存只是加了一个内存对齐的过程,逻辑很简单
inline char* Arena::Allocate(size_t bytes) { if (bytes <= alloc_bytes_remaining_) { //剩余内存大于申请,直接从预分配的内存中取走相应大小 char* result = alloc_ptr_; alloc_ptr_ += bytes; alloc_bytes_remaining_ -= bytes; return result; } return AllocateFallback(bytes);}
char* Arena::AllocateFallback(size_t bytes) { //if > 1K 直接分配一块内存然后返回给申请者 if (bytes > kBlockSize / 4) { char* result = AllocateNewBlock(bytes); return result; } // 否则申请一块 4K 的内存然后取相应的大小返回给请求者. alloc_ptr_ = AllocateNewBlock(kBlockSize); alloc_bytes_remaining_ = kBlockSize; char* result = alloc_ptr_; alloc_ptr_ += bytes; alloc_bytes_remaining_ -= bytes; return result;}
这里Arena的使用原理就分析完成了,在其析构的时候会释放掉所有的内存。
至于SkipList leveldb也就是对齐有一个具体的实现,对齐详细的介绍和说明有一篇文章《SkipList 跳表》有详细的介绍。接下来的文章我们介绍一下MemTable的迭代器和Comparator。