leveldb源代码分析系列1: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介绍。

Image placeholder
LoveCode
未设置
  17人点赞

没有讨论,发表一下自己的看法吧

推荐文章
leveldb源代码分析系列1.1:memtable中comparator的实现

leveldb中memtable封装了一个skiplist用来存储真正的数据,跳跃列表的实现一定需要定义存储项的序关系,而在leveldb中这个序关系通过comparator相关类来实现。leveld

leveldb源代码分析系列1.2:skiplist实现

skiplist的实现介绍leveldb中的SkipList是一个模板类,其模板参数的类型分别是存储的Key类型和Comparator类型。虽然名字是Key类型,但其实存储了整个entry,只不过Co

TPC-C解析系列03_TPC-C基准测试之SQL优化

TPC-C是一个非常严苛的基准测试模型,考验的是一个完备的关系数据库系统全链路的能力。这也是为什么在TPC-C的榜单前列,出现的永远只是大家熟知的那几家在业界有着几十年积累、从关系数据库理论开始发展就

TPC-C解析系列05_TPC-C基准测试之存储优化

TPC-C规范要求被测数据库的性能(tpmC)与数据量成正比。TPC-C的基本数据单元是仓库(warehouse),每个仓库的数据量通常在70MB左右(与具体实现有关)。TPC-C规定每个仓库所获得的

Nebula 架构剖析系列(二)图数据库的查询引擎设计

摘要上文(存储篇)说到数据库重要的两部分为存储和计算,本篇内容为你解读图数据库Nebula在查询引擎QueryEngine方面的设计实践。在Nebula中,QueryEngine是用来处理Nebula

TPC-C解析系列01_TPC-C benchmark测试介绍

作者:阳振坤2019.10导语:自从蚂蚁金服自研数据库OceanBase获得TPC-C测试第一名后,引起了行业内外大量关注,我们衷心的感谢大家对OceanBase的支持与厚爱,也虚心听取外界的意见和建

TPC-C解析系列02_OceanBase如何做TPC-C测试

导语:蚂蚁金服自研数据库OceanBase登顶TPC-C引起业内广泛关注,为了更清楚的展示其中的技术细节,我们特意邀请OceanBase核心研发人员对本次测试进行技术解读,共包括五篇:1)TPC-C基

TPC-C解析系列04_TPC-C基准测试之数据库事务引擎的挑战

OceanBase这次TPC-C测试与榜单上Oracle和DB2等其他数据库在硬件使用上有非常大的不同,OceanBase的数据库服务器使用的是204+3台型号是ecs.i2.16xlarge阿里云E

使用BCC工具分析系统性能

系统管理员可以通过利用BCC(BPFCompilerCollection)库的工具来分析操作系统性能和获取操作系统信息。BCC介绍BCC工具全称BPFCompilerCollection(BCC),是

第 10 节:复合类型 1:数组

1:数组01数组定义和使用packagemain import"fmt" funcmain0101(){ //数组定义 //数组是一系列相同数据类型在内存中有序存储的数据集合 //var数组名[

weex和React Native的区别是什么?

weex简介:weex是阿里巴巴公司与2016年6月开源的一种用于构建移动跨平台的UI框架特点:Lightweight:轻量级,语法简单,易于使用Extendable:可扩展,丰富内置组件,可扩展的A

react native的优缺点是什么?

ReactNative使用Javascript语言,类似于HTML的JSX,以及CSS来开发移动应用,因此熟悉Web前端开发的技术人员只需很少的学习就可以进入移动应用开发领域。reactnative的

双11、TPC-C?OceanBase的征程在哪里?

蚂蚁金服自研的分布式关系数据库OceanBase登顶TPC-C一个月后,便迎来了2019年双11大考,团队相信“TPC-C只是双11的虚拟预演,双11才是一次真实场景的TPC-C。”OceanBase

红帽OpenShift得到IBM、AWS和Azure的支持,生态能力正不断扩大

继IBM在11月6日宣布,IBMCloudPaks容器云的底层技术通过红帽OpenShift来支持后;AWS也于11月7日表示,原生集成AWS服务的红帽OpenShift容器平台已可用于由光环新网技术

echarts和vue的区别是什么?

echarts:ECharts,缩写来自EnterpriseCharts,商业级数据图表,一个纯Javascript的图表库,可以流畅的运行在PC和移动设备上,兼容当前绝大部分浏览器(IE6/7/8/

bootstrap和vue的区别是什么?

Bootstrap是美国Twitter公司的设计师MarkOtto和JacobThornton合作基于HTML、CSS、JavaScript开发的简洁、直观、强悍的前端开发框架,使得Web开发更加快捷

app.vue的作用是什么?

app.vue的作用是什么?app.vue可以当做是网站首页,是一个vue项目的主组件,页面入口文件,所有页面都是在App.vue下进行切换的。是整个项目的关键,app.vue负责构建定义及页面组件归

jquery和vue的区别是什么?

jquery和vue的区别是什么?●jquery是直接操作DOM;使用选择器($)选取DOM对象,对其进行赋值、取值、事件绑定等操作;和原生的js区别只在于可以更方便的选取和操作DOM对象;数据和界面

React v16.9 中unsafe的生命周期函数

https://zh-hans.reactjs.org/b...Unsafe的生命周期 componentWillMount→UNSAFE_componentWillMount 没有用过,不描述

基础信息:MySQL 特性

MySQL数据库的优缺点: 关系型数据库管理系统(RDBMS):MySQL是一个典型的关系型数据库管理系统。 易用:MySQL很容易上手。只要你掌握一些简单的SQL知识,就可以构建SQL语句与My

2019年9月数据库流行度排行:MySQL 强劲增长完成深 V 反转

导读:DB-Engines的2019年9月数据库流行度排行榜已经发布,本月最耀眼的明星是MySQL,分值大幅增长25.39分,较年初已经上升了125分,增幅达10%,完成了一次深V反转。相较之下,Or

ThinkPHP6 核心分析(一):Http 类的实例化

从入口文件出发 当访问一个ThinkPHP搭建的站点,框架最先是从入口文件开始的,然后才是应用初始化、路由解析、控制器调用和响应输出等操作。入口文件主要代码如下: //引入自动加载器,实现类的自动加载

Requests源码分析

Requests源码分析最近python学习到了瓶颈了,这次准备从KennethReitz大神的requests入手分析源码,看大神的代码是一种学习的好方法,让我从中学到很多以前不知道的知识reque

源码分析 | 咋嘞?你的IDEA过期了吧!加个Jar包就破解了,为什么?

微信公众号:bugstack虫洞栈|博客:https://bugstack.cn沉淀、分享、成长,专注于原创专题案例,以最易学习编程的方式分享知识,让自己和他人都能有所收获。目前已完成的专题有;Net

Gradle Builds Everything —— Task 实例

上文讲述了Gradle中关于任务的基础概念,本文开始讲述下Task是如何定义的。为了方便,我们的语境分不开Gradle和AndroidGradlePlugin,因此此处不脱离Android环境来介绍G