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

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

int InternalKeyComparator::Compare(const  Slice&  akey, const Slice& bkey) const {
  // Order by:
  // increasing user key (according to user-supplied comparator)
  // decreasing sequence number
  // decreasing type (though sequence# should  be  enough to disambiguate)
  int r = user_comparator_->Compare(ExtractUserKey(akey),ExtractUserKey(bkey));
  if(r == 0) {
  const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
  const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
  if(anum > bnum) {
    r = -1;
  }
  else if (anum < bnum) {
    r = +1;
  }
  }
return  r;
}

Compare函数中首先使用user_comparator_比较user_key的大小,如果user_key不相等则直接使用user_key的比较结果返回,否则继续比较sequence的大小。
注意:akey.data() + akey.size() - 8经过解码后是sequence的七位和type的一位组合的8位数字,但由于sequence是不可能重复的,所以这里不需要继续解码,直接比较结果也是正确的。
当user_key相同时,sequence按照逆序排序。即相同user_key中序列号越大,在skiplist中位置越靠前。
在这里给出默认的user_comparator_初始化流程以及其比较机制。

InternalKeyComparator是继承于Comparator的派生类,leveldb中还有一个继承于Comparator的派生类:BytewiseComparatorImpl。剧透一下:BytewiseComparatorImpl就是默认的user_comparator_对象的类型。leveldb中默认使用BytewiseComparatorImpl比较user_key,使用InternalKeyComparator比较entry的internal_key部分。

在DB::Open函数中,impl被生成。

DBImpl* impl = new DBImpl(options,  dbname);

DBImpl对象中有一成员internal_comparator_,其类型为InternalKeyComparator。在DBImpl构造函数中,internal_comparator_成员通过传入的option中的成员初始化。默认情况下,Options的comparator成员初始化为BytewiseComparatorImpl对象,所以internal_comparator_对象中的user_comparator_成员被初始化BytewiseComparatorImpl类型。

Options::Options():  comparator(BytewiseComparator()),  env(Env::Default())  {}
const Comparator*  BytewiseComparator() {
 static NoDestructor<BytewiseComparatorImpl>  singleton;
 return  singleton.get();
}

来看看BytewiseComparatorImpl类中是如何比较user_key的:其调用Slice的compare方法,首先比较a和b的长度,长度小的一方属于小的一方。当长度相同时,通过memcmp函数进行比较。

virtual int Compare(const Slice& a, const Slice&  b) const {
  return a.compare(b);
}

inline int Slice::compare(const Slice& b)  const  {
  const size_t min_len = (size_ < b.size_) ?  size_ : b.size_;
  int r = memcmp(data_,  b.data_,  min_len);
  if (r == 0) {
    if (size_ < b.size_)
      r = -1;
    else if (size_ > b.size_)
      r = +1;
  }
  return  r;
}

DB::Open函数中接着使用impl->internal_comparator_对象初始化了impl对象中的mem_成员。

impl->mem_ = new MemTable(impl->internal_comparator_);

MemTable类型中封装了类型KeyComparator,其封装了InternalKeyComparator

struct KeyComparator {
  const InternalKeyComparator  comparator;
  explicit KeyComparator(const  InternalKeyComparator& c) : comparator(c) {}
  int operator()(const char*  a, const char* b) const;
};

之后的Get,Put等基本操作的分析过程中会继续看到这些成员和函数的使用。

本节最重要的结论:通过InternalKeyComparatorBytewiseComparatorImpl这两个类,skiplist的存储项排序按照user_key升序,相同user_key项按照sequence降序。

Image placeholder
LoveCode
未设置
  41人点赞

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

推荐文章
leveldb源代码分析系列1:MemTable的实现

MemTable及其实现这是一个第零层的主题,预计扩展如下第一层主题:1.1comparator介绍1.2skiplist实现介绍1.3数据压缩相关介绍1.4Put流程1.5Get流程leveldb中

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

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

jquery中children()和find()的区别是什么?

jquery中children()和find()的区别children(selector)方法是返回匹配元素集合中每个元素的所有子元素(仅儿子辈)。参数可选,添加参数表示通过选择器进行过滤,对元素进行

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

angular的注入器是什么?

在依赖注入和依赖查找的时候注入器和提供器就需要使用。接下来就简单介绍一下注入器和提供器。注入器Angular提供的类,一般不需调用,会自动通过组件的构造函数注入。1.当一个提供器提供在模块中时,他是对

深入了解Nodejs Buffer的使用

JavaScript起初为浏览器而设计,没有读取或操作二进制数据流的机制。Buffer类的引入,则让NodeJS拥有操作文件流或网络二进制流的能力。Buffer基本概念Buffer对象的内存分配不是在

Disruptor的简单介绍与应用

前言最近工作比较忙,在工作项目中,看了很多人都自己实现了一套数据任务处理机制,个人感觉有点乱,且也方便他人的后续维护,所以想到了一种数据处理模式,即生产者、缓冲队列、消费者的模式来统一大家的实现逻辑。

使用BCC工具分析系统性能

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

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

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

dreamweaver中CSS怎么设置

dreamweaver中CSS怎么设置1、打开软件后,我们可以直接按下快捷键【Ctrl+J】2、或者,我们点击菜单栏的修改命令按钮。3、然后,我们点击页面属性按钮。4、接下来我们就会看到页面属性这个窗

php中css不加载怎么解决?

php中css不加载怎么解决?解决方法:1、首先打开HTML文档;2、然后在head标签中找到引入css文件的link标签;3、最后在link标签的href属性的值前面,加上__STATIC__即可。

webpack中css的url报错?

webpack中css的url报错?css-loader://打包样式中背景图 { test:/\.(png|jpg)$/, loader:"url-loader?limit=8192&name=im

jQuery中click()方法如何使用?

jQuery中click()方法如何使用?作用:click()方法触发click事件,或规定当发生click事件时运行的函数。语法:$(selector).click() $(selector).cl

react-native中IOS的webview和js层通信 - UIWebview

前言在9012的最后一篇写到了在rn中安卓的webview的通信原理,而作为0202年的第一篇,继续讨论上年rn中webview通信剩下的部分。背景:对于webview,了解过的人都知道在ios端会存

echarts怎么引入到vue中?

准备工作:首先我们初始化一个vue项目,执行vueinitwebpackechart。接着我们进入初始化的项目下,安装echarts,npminstallecharts-S //或 cnpminsta

axios怎么引入到vue中?

Axios是一个基于promise的HTTP库,可以用在浏览器和node.js中。在vue项目之中使用axios是一个非常明智的选择,因为vue官方已经宣称不再维护vue-resource,并且推荐使

node中文什么意思?

起初,RyanDahl称他的项目为web.js,就是一个Web服务器,但是项目的发展超过了他最初单纯开发一个Web服务器的想法,变成了构建网络应用的一个基础框架,这样可以在它的基础上构建更多的东西,诸

vue中如何关闭eslint检测?

vue中如何关闭eslint检测?有了eslint的校验,可以来规范开发人员的代码,是挺好的。但是有些像缩进、空格、空白行之类的规范,在开发过程中一直报错,未免太过于苛刻了。所以,下面来介绍下怎么在v

ajax怎么在vue中使用?

ajax怎么在vue中使用?axios是一个基于Promise的HTTP请求客户端,用来发送请求,也是vue2.0官方推荐的,同时不再对vue-resource进行更新和维护本文为大家介绍vue使用a

vue中的diff算法详解

1.当数据发生变化时,vue是怎么更新节点的?要知道渲染真实DOM的开销是很大的,比如有时候我们修改了某个数据,如果直接渲染到真实dom上会引起整个dom树的重绘和重排,有没有可能我们只更新我们修改的