上面一篇博文主要说了leveldb的理论原理,接下来将说明leveldb中如何去实现这些组件,主要是按照下面的思路进行的:首先分别分析LSM的各个组件,例如memtable,commit log,compaction实现,之后将这些功能串联起来分析一下leveldb的读写流程。这篇中主要是关于memtable的分析。
memtable常驻于内存,需要按照key进行排序,通常意义上的话,可以使用二叉查找树来实现,跟进一步可以使用红黑树保证树的平衡,但是leveldb中使用了另外的一种数据结构:跳表Skip List。
memtable声明在db/memtable.h中,定义如下:
这里面有几个注意点,首先Arena对象实现了一套leveldb的内存管理策略,将在下面的文章中进行分析,这里仅仅将其想象成一个内存分配器即可;另外就是Table类型(实际上就是SkipList类型)也将在下面的文章中进行分析。下面主要关注memtable初始化、插入key、查询key,由于LSM模型中memtable中没有数据的“实际”删除,这里并没有实现删除方法。
初始化函数定义如下:
就是简单的完成refs_和table_的初始化。插入的函数定义如下:
思路上相对比较简单,首先对用户传递进来的kv进行格式化,之后调用table_的Insert方法插入到数据库中,需要注意:1. 新出现了Slice类型,基本上和std::string类型向类似,代码比较简单,这里略过;2. 用户传递进来的kv最终被封装到了一个char数组中,格式为key_size, key_bytes, (sequence_number << 8)|type,value_size, value_bytes(其中并没有,这里仅仅是为了区分)。
查询的操作代码如下:
Get函数内首先通过Table查找key,如果找到该key,解析key的内容,如果是kTypeValue类型的,返回给客户端查找到的value,如果是kTypeDeletion类型的(参考
leveldb源代码分析:理论基础),返回给客户端表明没有找到。这里需要注意的是Get的参数中使用了LookupKey,该类型实际上就是在用户输入的key/value和leveldb内部使用key的起到桥梁的作用,定义如下:
至此基本上memtable的初始化、读取、插入的操作分析完了,未解决问题如下:
1. SkipList数据结构
2.Arena内存分配策略
分享到:
相关推荐
leveldb源码分析 比较全面讲解leveldb leveldb 是 Google 开源的持久化 KV 单机存储引擎,开源页面 http://code.google.com/p/leveldb/。 针对存储面对的普遍随机 IO 问题,leveldb 采用了 merge-dump 的方式,将...
leveldb 源码,源于google 官方github 源码,解压缩即可
levelDB源码分析记录1
leveldb源码分析
leveldb源码工程Windows版,使用vs2010编译通过。有问题可以参考根目录下的Windows文件(使用notepad打开)
免积分,最新的 leveldb-1.18 源码及leveldb实现解析
包含两个版本的levelDB,1.15.0和1.4.0
Leveldb是一个google实现的非常高效的kv数据库,资源为leveldb实现分析 pdf版本,内容清晰,简介,详实。
leveldb实现解析
详细且纯粹的leveldb源码注解
windows下可编译的leveldb源码,主要用boost库替代linux下移植代码。 修改源码部分: 1.db\c.cc文件中头文件unistd.h 2.port\port.h文件中注明使用的是windows系统 3.无法打开包括文件:“sys/mman.h”: No such ...
图解leveldb源码和中文注释
Windows下使用VS2012编译成功的leveldb源码工程文件,下载后直接点击.sln文件打开,更改配置后直接可用。生成的LevleDB.lib文件在Debug文件夹中。如果不想编译,也可以直接在自己工程中使用生成的LevleDB.lib库,亲...
leveldb是Jeff Dean 和 Sanjay Ghemawat 两位超级大神实现的高效 kv 数据库。本资料对leveldb源码进行了详细的注释,可以帮助初学者快速的阅读源码,了解设计的思想。
leveldb实现解析[归类].pdf
DB leveldb实现解析
LevelDB是Google开源的持久化Key-...)的方式,将逻辑场景的写请求转换成顺 序写Log和写Memtable操作,由后台进程将Memtable持久化成Sstable。对于读请求,随机IO 还是无法避免,但它设计了一系列策略来保证读的效率。