65.9K
CodeProject 正在变化。 阅读更多。
Home

RaptorDB - 键值存储 V2

Mehdi Gholam
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.96/5 (101投票s)

2012年1月19日

CPOL

15分钟阅读

viewsIcon

817975

downloadIcon

7146

更快的键/值存储 NoSQL 嵌入式数据库引擎，利用新的 MGIndex 数据结构，包含 MurMur2 哈希和 WAH 位图索引来处理重复项。(支持 MonoDroid)

raptordbkv2/raptorDB.png

引言

本文是我之前文章（https://codeproject.org.cn/Articles/190504/RaptorDB）的第二版。我不得不写一篇新文章，因为在这个版本中，我对原始版本进行了完全的重新设计和架构调整，因此它与前一篇文章不符。在这个版本中，我放弃了 b+树和哈希索引，转而使用我自己的 MGIndex 结构，该结构在所有方面都更优越，性能数据足以说明一切。

什么是 RaptorDB？

以下是用于描述 RaptorDB 的所有术语的简要概述：

  • 嵌入式：您可以像使用任何其他 DLL 一样在应用程序内部使用 RaptorDB，而无需安装服务或运行外部程序。
  • NoSQL：一场自发的运动，旨在用更相关、更适合特定应用的存储系统来取代关系型数据库。这些系统通常是为提高性能而设计的。
  • 持久化：所有更改都会存储在硬盘上，因此您永远不会在断电或崩溃时丢失数据。
  • 字典：一个键/值存储系统，类似于 .NET 中的实现。
  • MurMurHash：由 Austin Appleby 于 2008 年创建的非加密哈希函数（http://en.wikipedia.org/wiki/MurmurHash）。

特点

RaptorDB 具有以下特点：
  • 极高的性能（通常比 RaptorDB v1 的插入性能快 2 倍，读取性能快 4 倍）。
  • 极小的占用空间，约 50kb。
  • 无依赖。
  • 读写支持多线程。
  • 数据页与主树结构分离，因此如果需要，可以从内存中释放，并按需加载。
  • 在非干净关闭时自动恢复索引文件。
  • 字符串键采用 UTF8 编码，如果未另行指定，则限制为 60 字节（最多 255 个字符）。
  • 支持使用 RaptorDBString 类处理长字符串键。
  • 重复键存储为 WAH 位图索引，以实现最佳存储和访问速度。
  • 两种操作模式：立即刷新和延迟刷新（后者速度更快，但有非干净关闭时数据丢失的风险）。
  • 支持枚举索引。
  • 支持枚举存储文件。
  • 支持移除键。

为什么需要新的数据结构？

总有改进的空间，而对更快系统的持续需求迫使我们创造新的做事方式。MGindex 也不例外。目前，MGindex 在写入方面比 b+树快 **15 倍**，在读取方面快 **21 倍**，同时保留了 b+树结构对磁盘友好的主要特性。

B+树的问题

理论上，b+树的时间复杂度为 O(N log k N) 或 log k N，其中 k 是一个常数。对于 k 通常大于 200 的典型值，b+树应该优于任何二叉树，因为它需要的操作次数更少。然而，我发现以下问题阻碍了性能：

  • b+树中的页面通常实现为指向子节点的列表或数组，因此虽然查找和插入值是 O(log k) 操作，但实际过程需要移动数组或列表中的子节点，这非常耗时。
  • 分裂 b+树中的页面需要修复父节点和子节点，因此会有效地锁定树一段时间，这使得并行更新非常非常困难，并催生了大量研究文章。

好的索引结构的要求

那么，什么是一个好的索引结构？以下是我认为必不可少的功能：

  • 可分页的数据结构
    • 易于加载和保存到磁盘。
    • 在内存不足时释放内存。
    • 按需加载以优化内存使用。
  • 极快的插入和检索速度。
  • 支持多线程和并行使用。
  • 页面应相互链接，以便可以通过转到下一页轻松执行范围查询。

MGIndex

MGIndex 汲取了 b+树的最佳特性，并在改进它们的同时消除了其缺点。MGIndex 的设计也非常简单，如下面的图所示：
raptordbkv2/pagelist.png

正如您所见，页面列表是一个已排序的字典，包含每个页面的第一个键以及关联的页码和页面项数。页面是键和记录号对的字典。
这种格式确保了半排序的键列表，即页面内的数据未排序，但页面之间是排序的。因此，查找一个键只需比较页面列表中的第一个键以找到所需的页面，然后从页面的字典中获取键。

MGIndex 的复杂度为 O(log M)+O(1)，其中 M = N / PageItemCount [PageItemCount = Globals 类中的 10000]。这意味着您可以在页面列表中进行 log M 次二分查找，并在页面内以 O(1) 的时间复杂度获取值。

RaptorDB 首先加载页面列表，然后就可以开始工作了，页面是根据使用情况按需加载的。

页面分裂

当页面已满并达到 PageItemCount 时，MGIndex 会对页面字典中的键进行排序，并将数据分成两个页面（类似于 b+树分裂），然后通过添加新页面并更改所需的第一个键来更新页面列表。这将确保页面按排序顺序进行。

有趣的是，处理器架构在这里起着重要作用，正如性能测试所示，它直接关系到排序键的时间，Core iX 处理器在这方面表现非常好。

MGIndex 的有趣副作用

以下是 MGIndex 的一些有趣副作用：
  • 由于数据页与页面列表结构是分离的，因此实现锁定很简单，并且仅限于页面内，而不是整个索引，这不像普通树那样。
  • 页面已满时分裂页面很简单，不需要像 b+树那样进行树遍历来检查节点溢出。
  • 主页面列表更新不频繁，因此锁定主页面列表结构不会影响性能。
  • 以上这些使得 MGIndex 成为并行更新的绝佳选择。

未走的路 / 走过的路又折返！

最初，我使用了 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+树：是 RaptorDB v1 的索引代码。
SortedDictionary：是内部 .net 实现，据说是红黑树。

非常大的数据集！

为了给引擎带来真正的压力，我在巨大的数据集上进行了以下测试（时间单位为秒，内存单位为 GB）：

raptordbkv2/bigdata.png
这些测试是在一台 HP ML120G6 系统上进行的，拥有 12GB 内存，10k RAID 硬盘驱动器，运行 Windows 2008 Server R2 64 位。为了与 RaptorDb v1 进行相对性能比较，我还包含了一个使用该引擎的 2000 万条记录的测试。

我推迟了对超过 1 亿条记录的 Get 测试，因为它需要大量的内存数组来存储 Guid 键以便稍后查找，这就是表中出现 NT（未测试）的原因。

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

索引参数调优

为了最大限度地利用 RaptorDB，您可以针对您的硬件调整一些特定参数。

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

raptordbkv2/nodes.png
我选择了 10000 这个数字，因为它在读写方面都表现良好，您可以自行在您的系统上进行调整，看看什么最适合您。

性能测试 v2.3

在 v2.3 中，将内部类转换为结构体这一简单的更改带来了 2 倍以上的巨大性能提升，并且内存使用量降低了至少 30%。几乎可以保证在任何系统上实现 **100k+ 的插入性能**。

raptordbkv2/v23perf.png

上面的一些测试运行了 3 次，因为当时计算机正在使用中（未冷启动进行测试），所以初始结果有误。HP G4 笔记本的表现令人惊讶。

我还对上面列表中的最后一个服务器上的 1 亿条记录测试重新进行了测试，结果如下：

raptordbkv2/100m.png

正如您在上面的测试中所见，插入时间快了 4 倍（尽管计算机规格与之前测试的 HP 系统不匹配），并且令人难以置信的是，内存使用量是之前测试的一半。

Using the Code

要创建或打开数据库，请使用以下代码：

// to create a db for guid keys without allowing duplicates
var guiddb = RaptorDB.RaptorDB<Guid>.Open("c:\\RaptorDbTest\\multithread", false);

// to create a db for string keys with a length of 100 characters (UTF8) allowing duplicates
var 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 的区别

以下是 RaptorDB v2 与 v1 之间的一些区别：

  • 已移除日志文件，不再需要，因为 MGIndex 已足够快，无需进程内索引。
  • 线程已替换为计时器。
  • 索引将在后台保存到磁盘，不会阻塞引擎进程。
  • 混乱的泛型代码已简化，不再需要 RDBDataType，您可以使用普通的 int、long、string 和 Guid 数据类型。
  • 已添加 RemoveKey。

除此之外，现有代码在新引擎下应可直接编译。

使用 RaptorDBString 和 RaptorDBGuid

RaptorDBString 用于长字符串键（大于 255 个字符），对于文件路径等非常有用。您可以使用它：

// long string keys without case sensitivity
var rap = new RaptorDBString(@"c:\raptordbtest\longstringkey", false);

// murmur hashed guid keys
var db = new RaptorDBGuid("c:\\RaptorDbTest\\hashedguid");

RaptorDBGuid 是一个特殊的引擎，它将对输入的 Guid 进行 MurMur2 哈希处理，以降低内存使用量（4 字节，而不是 16 字节），这对于存储大量项非常有用。您可以使用它：

// murmur hashed guid keys
var db = new RaptorDBGuid("c:\\RaptorDbTest\\hashedguid");

全局参数

以下参数位于 Global.cs 文件中，您可以更改它们来控制引擎的内部工作。

参数
 默认值
 描述
BitmapOffsetSwitchOverCount
 		10
 切换点，在此点之后，重复项将存储为 WAH 位图，而不是记录号列表。
PageItemCount
 		10,000
 一个页面内的项目数量。
SaveTimerSeconds
 		60
 后台保存索引的计时器秒数（例如，每 60 秒将索引保存到磁盘）。
DefaultStringKeySize
 		60
 默认字符串键大小（以字节为单位，存储为 UTF8）。
FlushStorageFileImmetiatley
 		false
 立即刷新到存储文件。
FreeBitmapMemoryOnSave
 		false
 保存时压缩并释放位图索引内存。

RaptorDB 接口

Set(T, byte[]) 设置键和字节数组值，返回 void。
Set(T, string) 设置键和字符串值，返回 void。
Get(T, out string) 获取键并将其放入字符串输出参数，如果找到键则返回 true。
Get(T, out byte[]) 获取键并将其放入字节数组输出参数，如果找到键则返回 true。
RemoveKey(T)
 这将从索引中移除键。
EnumerateStorageFile() 返回主存储文件中的所有内容，类型为 IEnumerable< KeyValuePair<T, byte[]> >。
Enumerate(fromkey)
 从给定的键开始枚举索引。
GetDuplicates(T) 返回主存储文件记录号的列表，类型为 IEnumerable<int>，表示重复键。
FetchRecord(int) 从主存储文件中返回字节数组类型的 byte[] 值，与 GetDuplicates 和 Enumerate 一起使用。
Count(includeDuplicates) 返回数据库索引中的项目数，如果指定，则计算重复项。
SaveIndex() 允许将索引立即保存到磁盘（引擎会自动在后台按时钟周期保存）。
Shutdown() 这将关闭所有文件并停止引擎。

非干净关闭

在非干净关闭的情况下，RaptorDB 将自动从最后一个索引项重建索引，直到存储文件中的最后一个插入项。此功能还允许您删除 mgidx 文件，并让 RaptorDB 从头开始重建索引。

移除键

在 RaptorDB 的 v2 版本中，已添加移除键的功能，但有以下注意事项：

  • 数据 不会 从存储文件中删除。
  • 一个特殊的删除记录将被添加到存储文件中，用于跟踪删除，并在需要重建索引时提供帮助。
  • 数据 会 从索引中移除。

单元测试

raptordbkv2/unittests.png

源代码中包含以下单元测试（所有测试的输出文件夹为 C:\RaptorDbTest）：

  • Duplicates_Set_and_Get：此测试将生成 1000 个 Guid 的 100 个重复项并获取每个重复项（测试 WAH 位图子系统）。
  • Enumerate：此测试将生成 100,001 个 Guid，并从预定的 Guid 开始枚举索引并显示结果计数（计数在每次运行时可能会有所不同）。
  • Multithread_test：此测试将创建 2 个线程插入 1,000,000 个项，第三个线程在插入开始后 5 秒延迟读取 2,000,000 个项。
  • One_Million_Set_Get：此测试将插入 1,000,000 个项并读取 1,000,000 个项。
  • One_Million_Set_Shutdown_Get：此测试将执行上述操作，但会先关闭再重新启动，然后再读取。
  • RaptorDBString_test：此测试将创建 100,000 个 1kb 的字符串键并从索引中读取它们。
  • Ten_Million_Optimized_GUID：此测试将使用 RaptorDBGuid 类，对 10,000,000 个 Guid 进行 MurMur 哈希处理，并读写它们。
  • Ten_Million_Set_Get：与 100 万项测试相同，但处理 1000 万项。
  • Twenty_Million_Optimized_GUID：与 1000 万项测试相同，但处理 2000 万项。
  • Twenty_Million_Set_Get：与 100 万项测试相同，但处理 2000 万项。
  • StringKeyTest：测试最大长度为 255 的普通字符串键。
  • RemoveKeyTest：测试移除键在关闭后是否正常工作。

文件格式

文件格式：*.mgdat

值在磁盘上按以下结构存储：
raptordbkv2/docs_file.png

文件格式：*.mgbmp

位图索引在磁盘上按以下格式存储：
raptordbkv2/mgbmp.png
位图行的长度是可变的，如果新数据适合磁盘上的记录大小，则会重用。如果不适合，则会创建新记录。因此，可能需要定期进行索引压缩以删除上次更新留下的未使用记录。

文件格式：*.mgidx

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

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

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

历史

  • 初始发布 v2.0：2012 年 1 月 19 日
  • 更新 v2.1：2012 年 1 月 26 日
    • 感谢 **igalk474** 修正了 safedictionary 迭代器的锁定问题。
    • string default(T) -> "" 而不是 null，感谢 **Ole Thrane** 发现此问题。
    • mgindex 字符串 firstkey null 修复。
    • 添加了普通字符串键的测试。
    • 修复了 v1 文章的链接。
  • 更新 v2.2：2012 年 2 月 8 日
    • 感谢 **syro_pro** 修复了 removekey 错误。
    • 感谢 **Paulo Zemek** 移除了 safedictionary 中不必要的初始化。
  • 更新 v2.3：2012 年 3 月 1 日
    • 将内部类更改为结构体（速度提高 2 倍以上，内存使用量降低 30%）。
    • 添加了 keystore 类和代码重构。
    • 为文章添加了 v2.3 性能部分。
  • 更新 v2.4：2012 年 3 月 7 日
    • 感谢 **Martin van der Geer** 修复了 remove key set 页面 isDirty 的错误。
    • Page<T> 再次成为一个类，以修复其状态的保持。
    • 添加了 RemoveKeyTest 单元测试。
    • 为了提高速度，从 StorageFile.CreateRowHeader 中移除了 MemoryStream。
    • 重复项的位图索引也设置了当前记录号。
  • 更新 v2.5：2012 年 5 月 28 日
    • 添加了 SafeSortedList 以实现页面列表的访问并发。
    • 插入性能恢复到 v2.3 的速度（移除了对重复项的额外写入）。
  • 更新 v2.6：2012 年 12 月 20 日
    • 将 RaptorDB 文档存储的代码回传。
    • 添加了更多数据类型（uint, short, double, float, datetime...）。
    • 为索引文件添加了锁。
    • 更新了日志记录器。
    • 更新了带锁的安全字典。
    • 改为使用 Path.DirectorySeparatorChar 以支持 Mono/MonoDroid。
    • 修复了 WAHbitarray 中的边缘情况错误。
    • 更新了存储文件。
  • 更新 v2.7.0：2013 年 10 月 6 日
    • WAHBitArray bug 修复
    • 索引文件以共享模式打开，以便进行在线备份。
    • 脏页在保存时排序，以提高读取性能。
  • 更新 v2.7.5：2013 年 10 月 11 日
    • 修复了将页面列表保存到磁盘时出现计数大于 5000 万项的错误。
© . All rights reserved.