帮酷LOGO
  • 显示原文与译文双语对照的内容

raptordbkv2/raptorDB.png

简介

本文是我在( http://www.codeproject.com/Articles/190504/RaptorDB ) 上发现的版本 2,因为在本版本中我完全重新设计并重新设计了原文。 在本版本中,我已经经完成了b+tree和哈希索引,以适合自己的MGIndex 结构。

什么是 RaptorDB?

下面是用于描述 RaptorDB的所有术语的简要概述:

  • 可以使用 RaptorDB inside: 你可以像将任何其他DLL一样使用应用程序,不需要安装服务或者运行外部程序。
  • 收费 : grass移动以取代关系数据库与更相关的。专门的存储系统,并将它的应用到实际的应用中。 这些系统通常是为了性能而设计的。
  • 英镑持久化:任何更改都存储在硬盘上,因此你永远不会丢失电源中断或者崩溃的。
  • 字典: 一个关键/值存储系统,与. NET. 中的实现非常类似
  • MurMurHash: 一个非加密哈希函数,由 Austin Appleby在 2008 ( http://en.wikipedia.org/wiki/MurmurHash ) 中创建。

特性

RaptorDB 具有以下功能:
  • 非常快的性能( 通常 2x 个插入和 4x 个 RaptorDB的读取性能)
  • ~50kb. 上的小脚印非常小
  • 无相关性。
  • 多线程支持读写。
  • 数据页与主树结构分离,如果需要,可以以从内存中释放,并按需加载。
  • 非干净关闭的自动索引文件恢复。
  • 如果未指定( 最大为 255个字符),则字符串密钥被编码为to字节并且限制为 60字节。
  • 使用 RaptorDBString 类支持长字符串键。
  • 重复键存储为WAH位图索引,以获得最佳存储和访问速度。
  • 两种操作模式刷新立即和延迟的( 后者是以牺牲非干净关闭数据损失的风险为代价的更快的) 。
  • 枚举支持的索引。
  • 枚举支持的存储文件。
  • 支持删除键。

另一个数据结构?

总有一些改进的空间,并且需要更快的系统来强制我们创建新的方法。
MGindex
也不例外。 目前,MGIndex 在写和读的代价上超过了1 英镑,同时保持了b+tree结构的磁盘友好性。

b+tree的问题

从理论上说,b+tree是O 或者 log base,例如对于 above的典型值,例如b+tree应该胜过任何二进制树,因为它将使用更少的操作。 但是,我发现以下问题会影响性能:

  • 通常情况下会在b+tree或者 array 中实现页面,因此在查找和插入值的过程中,进程实际上必须移动子进程,这是进程的一部分,所以耗时。
  • 在b+tree中拆分页面必须修复父节点和子节点,因这里并行更新非常困难并且导致了大量研究文章。

一个好的索引结构的

那么什么是好的索引结构,这里是我认为的一个重要特性:

  • 页面能力数据结构:
    • 轻松加载并保存到磁盘。
    • 内存约束的空闲内存。
    • 按需加载以优化内存使用。
  • 非常快速的插入和检索。
  • Multi-thread-able和并行能使用。
  • 页面应该链接在一起,这样你就可以轻松地访问下一页。

MGIndex

MGIndex 采用b+tree的最佳特性,同时对它们进行改进,从而消除障碍。 MGIndex 在设计中也非常简单,如下图所示:
raptordbkv2/pagelist.png

你可以以看到页列表是每个页面的第一个键的排序字典,以及相关的页码和页面项目计数。 页面是键和记录编号对的字典。
这种格式确保了一个半排序的键列表,在页面中数据不是排序的,而是页面的排序 relative 。 所以查找一个键就比较页列表中的第一个键,找到页面所需的页码并从页面中获取键。

MGIndex 是O ( 日志M ) +O ( 1 ),正在进行n/pageitemcount [ PageItemCount = 10000 in the Globals class] 。 这意味着在日志M 时,在页面列表中进行二进制搜索,并在页面中获取 O(1) 时间的值。

RaptorDB 通过加载页面列表开始,并且很好地从那里进入并按需加载页面。

页拆分

在页面满了到达 PageItemCount的情况下

MGIndex 
将在页的字典中排序,并将数据分解为两页( 与b+tree拆分类似) 并通过添加新页面更新页面列表。 这将确保排序页面的顺序。

有趣的是,处理器架构在性能测试中可以以看到,因为它直接与排序关键点相关。

MGIndex的兴趣副作用

下面是 MGIndex的一些有趣的副作用
  • 因为数据页与页列表结构分离,实现锁定很容易,而不是整个索引,而是普通树。
  • 分割一个页面是简单的,并且不需要一个树遍历的节点 overflow 检查作为b+tree中的。
  • 主页列表更新很少,因此主页面列表结构的锁定不会影响性能。
  • above 使 MGIndex 成为并行更新的一个很好的候选者。

路没有走/路 and doubled !

最初我在这里使用了 AATree 来为页面结构找到( http://demakov.com/snippets/aatree.html ),因为它的结构非常好,易于理解。 经过测试和比较内部. NET SortedDictionary ( 这是一个红黑树结构),它是缓慢的,所以废弃的( 。查看性能比较) 。

我决定对页面使用 SortedDictionary,因为它比普通的Dictionary 慢,并且用于 key-value 存储的目的不需要。 如果希望在代码中使用 switch,你可以在任何时候对该代码进行处理,这对除你可以删除页面中的排序之外的其他代码没有任何区别。

我还尝试了多种排序例程,比如双 pivot 快速排序。timsort 。插入排序和发现它们都比我测试中的内部. NET 快速排序例程慢。

性能测试

在这个版本中我已经编译了一个我已经测试过的计算机列表,below 是结果。

raptordbkv2/computers.png
你可以看到,新的英特尔核心iX处理器获得了非常显著的性能提升。

比较B+tree和 MGIndex

为了衡量b+tree的relative 性能,红/黑树和 MGIndex 我已经编译了以下结果。

raptordbkv2/compare.png
时间以秒为单位。

B+TreeRaptorDB v1的索引代码
SortedDictionary
是内部. NET 实现被认为是红色/黑树。

非常大的数据集 !

为了让引擎处于压力之下,我在大型数据集( 时间以秒为单位,内存为 Gb ) 上做了以下测试:

raptordbkv2/bigdata.png
这些测试是在一个带有 12Gb 个Ram的HP ML120G6系统上完成的,10k 个raid磁盘驱动器运行 Windows 2008服务器 R2 64位。 为了衡量 relative 性能到 RaptorDB v1,我已经在该引擎中包含了 20万个测试。

因为它需要内存中存储的键,所以我推迟测试get记录,因为在内存中存储了一个巨大的array,这就是为什么表中存在一个 NT ( 未测试) 。

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

索引参数优化

为了充分利用 RaptorDB,你可以调整一些特定于你的硬件的参数。

  • PageItemCount: 控制每个页面的大小。
以下是我的一些结果:

raptordbkv2/nodes.png
我选择了 10000个数字作为读写的好案例,欢迎你在你自己的系统上修改它。

性能测试 v2.3

在v2.3中,将内部类转换为结构的单个简单更改使 2 x+的性能大大提高,至少 30%低内存使用。 你几乎可以保证在任何系统上获得 100k+插入性能

raptordbkv2/v23perf.png

一些测试 above 被运行 3次,因为计算机在( 不是为了测试而启动的) 上使用,所以初始结果是关闭的。 惠普的G4笔记本电脑真是惊人。

我还在 above 列表中的最后一个服务器上运行了 100测试,结果如下:

raptordbkv2/100m.png

就像你在 above 测试中看到的,插入时间是 4x ( 虽然计算机的规格不是 MATCH 系统之前测试过的),令人难以置信的内存使用量是前一次测试的一半。

使用代码

若要创建或者打开数据库,请使用以下代码:

// to create a db for guid keys without allowing duplicatesvar guiddb = RaptorDB.RaptorDB<Guid>.Open("c:RaptorDbTestmultithread", false);// to create a db for string keys with a length of 100 characters (UTF8) allowing duplicatesvar strdb = RaptorDB.RaptorDB<string>.Open("c:intdb", 100, true); 

要插入和检索数据,请使用以下代码:

Guid g = Guid.NewGuid();
guiddb.Set(g, "somevalue");string outstr="";if(guiddb.Get(g, out outstr)) 
{
 // success outstr should be"somevalue"}

UnitTests项目包含用于不同用例的工作示例代码,以便你可以参考它以获得更多示例。

与v1的差异

以下是v2中与 RaptorDB的v1相对应的列表:

  • 日志文件已经被删除,因为 MGIndex 足够快用于进程索引,所以不再需要。
  • 线程已经被计时器替换。
  • 索引将在 background 中保存到磁盘,而不会阻止引擎进程。
  • 已经经简化了混乱的泛型代码,并且已经经删除了 RDBDataType,你可以以使用正常的int 。long 。string和Guid数据类型。
  • 已经添加 RemoveKey

除了现有的代码应该编译为与新引擎相同。

使用RaptorDBString和 RaptorDBGuid

RaptorDBString 用于长字符串键( 大于 255个字符),它对于文件路径 等等 非常有用,你可以以按以下方式使用它:

// long string keys without case sensitivityvar rap = new RaptorDBString(@"c:raptordbtestlongstringkey", false);// murmur hashed guid keysvar db = new RaptorDBGuid("c:RaptorDbTesthashedguid"); 

如果你有大量需要存储的项目,那么 RaptorDBGuid 是一个特殊引擎,它将对输入进行 MurMur2 散列处理,以降低内存使用率。 你可以按以下方式使用它:

// murmur hashed guid keysvar db = new RaptorDBGuid("c:RaptorDbTesthashedguid"); 

全局参数

以下参数位于 Global.cs 文件中,你可以更改引擎内部工作的控制。

参数
默认值
描述
<code>BitmapOffsetSwitchOverCount
10
switch 过点存储为与记录编号列表相对的WAH位图
<code>PageItemCount
10,000
页中的项的数目
<code>SaveTimerSeconds
60
后台保存索引计时器秒( 比如 每隔 60秒将索引保存到磁盘)
<code>DefaultStringKeySize
60
默认字符串密钥大小( 以字节为单位存储)
<code>FlushStorageFileImmetiatley
false
立即刷新到存储文件
<code>FreeBitmapMemoryOnSave
false
保存时压缩和自由位图索引内存

RaptorDB接口

Set(T, byte[])设置键和字节 array 值,返回 void
Set(T, string)设置键和字符串值,返回 void
Get(T, out string)获取键并将它的放入字符串输出参数中,如果找到键,则返回 true
Get(T, out byte[])获取键并将它的放入字节 array 输出参数中,如果找到键,则返回 true
<code>RemoveKey(T)
这将删除索引中的键
EnumerateStorageFile()
将主存储文件的所有内容作为
IEnumerable<
 KeyValuePair<T, byte[]>>
Enumerate(fromkey)
从给定的键枚举索引。
GetDuplicates(T)返回主存储文件记录编号的列表,作为指定键的IEnumerable<int>
FetchRecord(int)byte[]的形式从主存储文件中返回值,用于
GetDuplicates
Enumerate
Count(includeDuplicates)返回数据库索引中的项数,如果指定,还计算重复项
SaveIndex()允许立即保存到索引磁盘( 引擎将自动保存在计时器的background 中)
Shutdown()这将关闭所有文件并停止引擎。

非干净关机

在非干净关闭时,RaptorDB 将自动重新生成最后一个索引项到存储文件中最后插入项的索引。 特性还允许你删除mgidx文件,并让 RaptorDB 从头开始重新生成索引。

删除密钥

RaptorDB 中删除键已经添加了以下警告:

  • 数据 从存储文件中删除。
  • 一个特殊的删除记录被添加到跟踪删除的存储文件中,这也有助于在需要。
  • 数据 从索引中删除。

单元测试

raptordbkv2/unittests.png

源代码( 所有测试的输出文件夹都是 C:RaptorDbTest ) 中包含以下单元测试:

  • 这个测试将生成 100个重复的1000个重复项,并获取每一个。
  • 这个测试将生成 100,001个 Guid,并从预定的Guid 枚举索引并显示结果计数。
  • 测试将从插入开始处创建 2个线程,插入 1,000.000项和第三个线程读取 2,000,000项,以及第三个线程的延迟。
  • 这里测试将插入 1,000,000项和读取 1,000个项。
  • One_Million_Set_Shutdown_Get: 这里测试将在读取前执行 above 但关闭并重新启动。
  • :这个测试将创建 100,000个字符串键并从索引中读取。
  • 这个测试将使用 RaptorDBGuid 类 MurMur MurMur hash hash writting writting writting writting 。
  • Ten_Million_Set_Get: 与 1百万个测试相同,但有 10个项目。
  • Twenty_Million_Optimized_GUID: 与 10百万个测试相同,但有 20个项目。
  • Twenty_Million_Set_Get: 与 1百万个测试相同,但有 20个项目。
  • StringKeyTest: 最大 255长度的普通字符串键的测试。
  • RemoveKeyTest: 在关闭期间,删除键的测试工作正常。

文件格式

文件格式:*.mgdat

值存储在磁盘上的以下结构中:
raptordbkv2/docs_file.png

文件格式:*.mgbmp

位图索引以下列格式存储在磁盘上:
raptordbkv2/mgbmp.png
位图行长度可变,如果新数据适合磁盘上的记录大小,则将重用,如果没有其他记录将被创建。 为此,可能需要定期索引压缩来删除以前更新留下的未使用记录。

文件格式:*.mgidx

MGIndex索引按如下格式保存:
raptordbkv2/mgidx.png

文件格式:*.mgbmr,*.mgrec

Rec文件是写入磁盘的一系列 long 值,没有特殊格式。 这些值将记录编号映射到位图中的偏移量索引文件和文档存储文件。

历史

  • 初始版本 v2.0: 19th 2012年01月
  • 更新 v2.1: 26th 2012年01月
    • 锁定safedictionary迭代器集,感谢 igalk474
    • 字符串 default(T) ->""而不是 null,感谢的Ole Thrane 来查找它
    • mgindex字符串firstKey空修复
    • 添加了普通字符串键的测试
    • 修正了与v1文章的链接
  • 更新 v2.2: 8th 2012年02月
    • Bug 修复 removeKey,感谢英镑的
    • 在safedictionary中删除了联合国需要的初始化,感谢 Paulo Zemek
  • 更新 v2.3: 1st 2012年03月
    • 将内部类更改为结构( 2x+速度,30%个内存)
    • 添加了密钥库类和代码重构
    • 在文章中添加了v2.3个性能
  • 更新 v2.4: 7th 2012年03月
    • Bug 修复删除密钥集 isDirty> Martin
    • 页 <> 是一个重新定义它的状态的类
    • 添加了 RemoveKeyTest 单元测试
    • 从 StorageFile.CreateRowHeader 中删除MemoryStream以加快速度
    • 当前记录编号也在位图的位图索引中设置
  • 更新 v2.5: 28th 2012年05月
    • 添加了用于访问页列表的并发的SafeSortedList
    • 将性能插入v2.3速度( 删除多余的重复写入)
  • 更新 v2.6: 20th 2012年12月
    • 从RaptorDB发送回代码存储区
    • 添加了更多数据类型( uint,short,double,float,datetime 。)
    • 将锁添加到 indexfile
    • 更新的记录器
    • 更新了带有锁的安全字典
    • 为单声道/monodroid支持改为 Path.DirectorySeparatorChar
    • WAHbitarray中的Bug 固定边缘
    • 更新的存储文件
  • 更新 v2.7.0: 6th 2013年10月
    • Bug 修复 WAHBitArray
    • 索引文件在共享模式下打开以支持联机复制备份
    • 脏页在保存时对读性能进行排序
  • 更新 v2.7.5: 11th 2013年10月
    • Bug 修复将页面列表保存到磁盘上计数> 50个项目



Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语