开源中国

我们不支持 IE 10 及以下版本浏览器

It appears you’re using an unsupported browser

为了获得更好的浏览体验,我们强烈建议您使用较新版本的 Chrome、 Firefox、 Safari 等,或者升级到最新版本的IE浏览器。 如果您使用的是 IE 11 或以上版本,请关闭“兼容性视图”。
RaptorDB - Key/Value 存储系统 V2 - 技术翻译 - 开源中国社区

RaptorDB - Key/Value 存储系统 V2 【已翻译100%】

标签: RaptorDB
oschina 推荐于 4年前 (共 14 段, 翻译完成于 12-25) 评论 6
收藏  
40
推荐标签: RaptorDB 待读

引言

这篇博文是我前一篇博文的第二版本,前一篇博文可以在这儿(http://www.codeproject.com/Articles/190504/RaptorDB)找到,我必须写一篇新的博文,这是因为在这篇博文里,我对最初的设想完全进行重新设计和重新架构,所以它不再是前一篇博文的继续。在这一版本的博客文章里,我剔除了B+树和哈希索引,支持了我自己的MGIndex结构,MGIndex结构总的来说很优秀,后面的性能比较的数值可以说明一切。

RaptorDB是什么?

下面是用来描述RaptorDB的所有关键词的简要说明:

  • 嵌入式:你可以像使用任何其他的动态链接库哪样在应用中使用RaptorDB,而且不需要安装服务或者运行外部程序。

  • NoSQL:使用与应用更加密切相关的,特定的存储系统替代关系型数据库的草根运动正在进行中。设计这样的系统通常都是为了提高性能。

  • 持久性:任何更改都会存储在磁盘上,因此在电力突然中断或者崩溃的情况下,你从不会丢失任何数据

  • 字典:键值存储系统与.NET里的键值实现非常相似。

几点人
 翻译得不错哦!

特性

RaptorDB拥有以下特性:

  • 非常高的性能(具有代表性的是与RaptorDB v1相比,插入速度是原来的2倍,读取速度是原来的4倍)

  • foot print非常小,只有50kb。

  • 没有任何依赖。

  • 支持多线程读取和写入。

  • 数据分页从主树形结构中独立,这样可以在需要时从内存中释放掉,并在请求时被加载。

  • 非正常关机后索引文件自动恢复

  • string key使用UTF8编码,在未指定情况下限制长度是60字节(上限255个字符)

  • 通过使用theRaptorDBStringclass支持long string Key

  • 重复的key通过WAH位图索引存储,这样可以优化存储并且加快访问速度

  • 两种操作模式,直接写入和暂缓写入(后者更快一些,但代价是在非正常关机时有数据丢失的风险)

  • 支持枚举索引

  • 支持枚举存储文件

  • 可以移除key

为什么换了一种数据结构?

总是存在一些改进的空间,并且和以往一样我们需要更快的系统,这都迫使我们创建了一个新的方法来完成工作。MGindex也不例外。

当前MGindex以b+树的结构呈现其中的一个原因是它具有15倍的写入速度和21倍的读取速度,同时使那些负责对硬盘友好的主要特性也是b+树结构。

BoydWang
 翻译得不错哦!

B+树存在的问题

理论上来讲,B+树的复杂度是O(N logkN)或者说是以k为底对N求对数的复杂度,例如,现在对哪些k值大于200来说,B+树应该优于任何二叉树,这是因为它使用的操作最少。不过,我发现下面几个问题在阻碍着性能的提高:

  • B+树的页面通常都是由一系列或者一组子指针来表示的,所以查找并插入一个值是复杂度为O(logk)的操作,这样的过程实际上需要在一组或者一系列子指针间来回移动,这就耗费了一些时间。

  • 分割B+树的页面需要修正父节点,而且事实上,在这个期间子节点就锁定了这棵树,那么并行更新就会非常非常难于实现,因此就促使大量的研究论文在讨论并行更新。

好的索引结构的要求

怎样才算是一个好的索引结构,下面罗列了我认为一个好的索引结构应该具有的重要特性:

  • 能够实现页面数据结构:

    •   易于装载,并可保存到磁盘。

    •  在内存有限制的情况下保持有空闲内存。

    •  优化内存使用,实现按需装载。

  • 可以非常快速的插入和获取。

  • 支持多线程和并发处理。

  • 页面应该连接在一起,这样你可以很容易地进入下一页面,从而可实现一定范围内的查询。

几点人
 翻译得不错哦!

MGIndex

MGIndex采纳了B+树的最优秀的特性,同时对它们进行修正,剔除了阻碍提高性能的东西。另外,MGIndex的设计非常简单,如下图所示:

raptordbkv2/pagelist.png

就像你看到那样,这样的页面列表是一个由页面的主关键字以及与其关联的起始页面编号和所属的页面数组成的已排序字典。而页面则是由主关键字和记录编号对组成的字典。

这种格式确定是一个只对关键字进行半排序的列表,也就是说页面内部的数据没有进行排序,而页面之间进行排序。因此要对一个关键字进行查找仅仅比较页面列表里的主要关键字,找到所需页面,然后从页面字典里就可得到这个关键字。

MGIndex的复杂度是O(log M)+ O(1),这里M是N/所属的页面数[在Globals类里,所属页面数等于10000]。这就意味着你用log M的时间在页面列表里进行二叉树搜索,用O(1)的时间在页面内获取这个值。

RaptorDB启动的时候就装载了页面列表,而且从此以后就一直装载着,而页面则根据需要和使用率进行装载。

几点人
 翻译得不错哦!

页面分割

如果页面已经填满,而且已经达到了PageItemCount所指定的数目,那么MGIndex将对页面字典里的关键字进行排序,然后把数据分为两个页面(就像B+树分割那样),接着更新页面列表,添加新的页面,更改需要更改的主关键字。这么做可以保证页面都进行了排序处理。

令人意外的是,就像你在性能测试里所看到的那样,处理器结构在这儿起到了重要的作用,因为它与关键字的排序时间直接相关,Core iX处理器在这方面似乎表现更加优越。

MGIndex令人关注的其他作用

下面列出了MGIndex的一些令人关注的其他作用:

  • 由于页面数据与页面列表结构相互分离,所以锁定的实现就简单多了,而且在页面内部是各自锁定,不是锁定整个索引,也不像普通树那么操作。

  • 在页面填满的时候分割出另一个页面就非常简单,而且不像B+树那样需要对整个树进行遍历,来检查是否有节点溢出的问题。

  • 主页面列表的更新很少,因此主页面列表结构的锁定不会影响性能。

  • 上面的这些使得MGIndex成为并发更新的真正优秀的候选者。

几点人
 翻译得不错哦!

没有采用的方法或者说采用的方法以及使用回原来的方法!

最初我用AATree描述页面结构,AATree可以在这儿(http://demakov.com/snippets/aatree.html)找到其说明,这是因为它具有易于理解的非常良好、简单的结构。经过对其内部所采用的(红黑树结构的).net SortedDictionary进行测试和比较之后,发现它有些慢,所以就不再采用它(参见性能比较部分)。

我决定不使用SortedDictionary描述页面是因为它比普通的Dictionary要慢些,而且要对关键字进行存储,排序并不是必须的,可以通过其他方式实现对关键字的排序。你可以在你喜欢的任何时候在代码中切换为使用SortedDictionary。除了你可以删除页面分割里的排序以外,其余的全部代码都可以照原样使用。

我还对各种各样的排序程序进行了测试,比如双基准快速排序,timsort和插入排序。通过我的测试,我发现所有这些都比我内部采用的.net快速排序要慢。

几点人
 翻译得不错哦!

性能测试

这个版本的测试我整理了一个列表显示我曾经在上面做测试的机器和结果。

raptordbkv2/computers.png

你可以看到在新的Intel Core iX系列处理器上性能有了显著提高。

对比 B+树和MGIndex

为了衡量b+树,红/黑树和MGIndex,我整理了如下结果。

raptordbkv2/compare.png

时间是秒。

B+Tree : 源于RaptorDB v1的索引代码。

SortedDictionary:是.net的内部实现,据称是一个红/黑树。

BoydWang
 翻译得不错哦!

真正的大数据集!

为了把这个引擎放在真正的压力下,我用庞大的数据集合做了如下测试(时间单位是秒,内存单位是Gb):

raptordbkv2/bigdata.png

这些测试在一台拥有12Gb内存,10k Raid存储阵列,运行64位Windows 2008 Server R2的HP ML120G6上进行。出于比较的目的,我也在RaptorDb v1引擎上测试了2亿条数据。

我推迟了10亿条记录的get测试因为它需要一个巨大的内存数组来存储一会查询会用到的GuidKey,因此在表里标记为NT(not tested)。

有趣的是,读取性能是相对线性的。

BoydWang
 翻译得不错哦!

调整索引参数

为了获得RaptorDB的最佳性能,你可以对与硬件紧密相关的一些参数进行调整。

  • PageItemCount: 控制每个页面的大小

下面是一些我测试的结果:

raptordbkv2/nodes.png

我选择10000这个值,因为它在读写两方面都很好。欢迎你对你系统上的这个值进行修改,看看哪个数值更适合你。

几点人
 翻译得不错哦!

性能测试2.3版本

在版本2.3里,单个把内部类转换为结构的简单更改就获得了2倍多的性能提高和至少少使用30%的内存。这几乎可以保证让你在任何系统上都可以获得十几万的插入性能。

raptordbkv2/v23perf.png

上面的一些测试运行了三次,这是因为那时计算机正在运行其他东西(不是为了测试而冷启动机器),因此最初的结果不算。HP G4笔记本电脑的测试结果是在令人惊讶。

我还对上面所列的最后一个服务器重新进行了1亿插入测试,下面是测试结果:

raptordbkv2/100m.png

正如你在上面的测试中所看到了,(虽然计算机规格与先前进行测试的HP系统不相匹配,但是)插入时间快了4倍,令人不可思议的是内存使用仅仅是前面测试所使用内存的一半。

几点人
 翻译得不错哦!
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们
评论(6)
Ctrl/CMD+Enter

顶一个
嵌入式,这类似于sqlite的noSQL实现吗?
顶一个 只是代码运行时候 写入文件 报错 显示 :其他进程占用 。有好解决方法么?

引用来自“alvinReal”的评论

顶一个 只是代码运行时候 写入文件 报错 显示 :其他进程占用 。有好解决方法么?
测试出错版本 3.2.0 及 3.2.5 不知道其他人遇到没有
这个很差的,我测了,插入10万条数据竟然1秒多
读尤其慢,10万条数据检索一条竟然慢到2秒才出来。比最差的关系数据库差了3个级别
测的版本是2.70
顶部