leveldb源代码分析系列:MemTable的实现

MemTable及其实现

这是一个第零层的主题,预计扩展如下第一层主题:

1.1 comparator介绍

1.2 skiplist实现介绍

1.3 数据压缩相关介绍

1.4 Put流程

1.5 Get流程

leveldb中的MemTable为内存中存储key_value的类,其通过skiplist实现这一功能。

MemTable含有的数据成员:

KeyComparator  comparator_;
int  refs_;
Arena  arena_;
Table  table_;

其中 KeyComparator 是类内部的一个struct,其封装了 InternalKeyComparator ,以及提供了operator()重载函数。其用来作为table_的比较函数。refs_是本对象的引用计数,可以调用Ref和Unref函数增加或减少其引用计数,当refs_归零时delete this。 Arena 是分配内存的类,用来为插入的数据分配内存。 Table 是这样一个typedef : typedef SkipList<const char*, KeyComparator> Table ,是一个跳跃列表,数据存储的地方。

MemTable::MemTable(const InternalKeyComparator&  comparator):comparator_(comparator),refs_(0),  table_(comparator_,  &arena_)  {}

在构造函数中,comparator_被传入的comparator构造,refs_初始化为0,table被传入comparator_和arena_。

MemTable 还有一个相关的类: MemTableIterator ,其提供了对存储数据的迭代器式访问操作。

MemTable 中最主要的两个函数: AddGet ,其间接实现了leveldb提供的三个接口: GetPutDelete 。leveldb中的Delete并不是真的在内存中删除此项,而是put一个标识为delete的特殊项。

在介绍函数 AddGet 函数之前,首先介绍下table_中存储数据的格式,其中包含了user_key和user_value以及sequence,leveldb将这几个项组合为一个entry。

entry: [ internal_key_size : user_key : sequence(7 byte) : type(1 byte) : user_value_size : value ]

其中user_key和user_value是保存的key-value键值对,其余的两个size类型的长度不定,leveldb内部会根据其大小进行压缩操作。 InternalKeyComparator 的比较逻辑是先按照uesr_key升序排列,相同user_key按照sequence降序排列,具体信息见1.1节,comparator的详细介绍。

Add 函数的作用是在table_中追加一项entry,encoded_len即为该entry的长度。

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;

然后调用 arena_.Allocate 获取内存,对size进行压缩并按照entry格式依次填入申请到的内存中,最后执行 table_.Insert 操作执行真正的添加操作。

Get函数的作用是根据key查询table_中某一项是否存在,如果存在则获取其value。其输入的第一个参数为 LookupKey 类型,leveldb中的注释显示这是一个用于 DBImpl::Get 的辅助类,他的作用是根据用户输入的user_key和sequence(这个可能是某个snapshot对应的sequence,其实leveldb中正是靠sequence来实现snapshot机制的)构建一个entry格式的internal_key,便于在table_中做真正的查找操作。Get函数中首先通过 Table::Iterator 迭代器找到可能是结果的entry,然后对其进行解码,并比较user_key是否相等,如果不相等则意味着table_中没有要查找的项,返回false。否则提取entry的type标志,如果标志是delete,则说明这一项在之前已经被删除,返回true,但是将status改为notfound。

Table的迭代器如何找到可能是结果的项,见1.2 skiplist介绍。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章