在磁盘性能上的持久性（纯功能性）红黑树

我正在研究实现简单的开源对象时态数据库的最佳数据结构，目前我非常喜欢使用持久性红黑树做它。在磁盘性能上的持久性（纯功能性）红黑树

我使用持久数据结构的主要原因首先是尽量减少锁的使用，因此数据库可以尽可能平行。另外，实现ACID事务更容易，甚至能够抽象出数据库在某种类的集群上并行工作。这种方法的伟大之处在于它可以实现几乎免费的时间数据库。这是相当不错的，特别适用于网络和数据分析（例如趋势）。

所有这些都非常酷，但我对在磁盘上使用永久数据结构的整体性能有点怀疑。尽管现在有一些速度非常快的磁盘，并且所有写入都可以异步完成，所以响应总是立竿见影，我不想在一个错误的前提下构建所有应用程序，只是意识到它并不是一件好事方法来做到这一点。由于所有写操作都是异步完成的，并且使用持久数据结构将不会使前一个 - 当前有效的结构无效，所以写时间并不是真正的瓶颈。 - 关于像this这样的结构，有一些文档正好用于磁盘使用。但在我看来，这些技术将增加更多的读取开销以实现更快的写入。但我认为恰恰相反是可取的。同样，这些技术中的许多技术确实最终得到了多版本树，但它们并不是完全不可改变的，这对证明持续开销非常重要。 - 我知道在将值附加到数据库时仍然需要某种锁定，并且我也知道如果不是所有版本都要维护，应该有一个好的垃圾收集逻辑（否则文件大小肯定会大大增加）。也可以考虑三角洲压缩系统。 - 在所有搜索树结构中，我真的认为红黑最接近我所需要的，因为它们提供最少的旋转次数。

但是有一些可能的缺陷： - 异步写入 - 可以影响实时需要数据的应用程序。但大多数时候，我认为网络应用程序并不是这种情况。另外，当需要实时数据时，可以设计出另一种解决方案，例如需要以更实时的方式工作的特定数据的签入/签出系统。 - 也可能导致一些承诺冲突，尽管我没有想到它可能发生的一个很好的例子。如果两个线程使用相同的数据，那么在正常的RDBMS中也会发生提交冲突，对吗？ - 像这样拥有一个不可变接口的开销将呈指数级增长，一切都注定很快就会失败，所以这一切都是一个坏主意。

有什么想法？

谢谢！

编辑：似乎是一个持久数据结构是什么样的误解： http://en.wikipedia.org/wiki/Persistent_data_structure

来源

2010-05-05 Waneck

你在杀我Smalls。 – 2010-05-05 02:10:25

你能解释为什么“我使用持久数据结构的主要原因首先是为了尽量减少锁的使用”???持续与否，你仍然需要锁... – 2010-05-05 04:12:42

嗯，你是对的。仍然需要使用锁，但将其最小化至最小。例如，就我的情况而言，我们需要锁定的唯一位置是“弱”引用，如红黑树的头部。将所有树更改附加到文件后，我们必须锁定它才能将指针（仅限于int）更改为树的头部。一个不知情的读者不可能在不一致的状态下捕捉该树，并且该锁应该工作得非常快。此外，为了写入，唯一需要锁定的时间是更改文件的大小（将数据附加到它） – Waneck 2010-05-05 12:21:33

如果您发现您的写入时间受到瓶颈，或者您的耐久性保证在没有同步写入的情况下毫无意义（嗯...），您应该执行大多数其他数据库所做的操作：实施Write-Ahead Log（WAL）或重做日志。

磁盘实际上非常适合连续编写，至少这是他们最擅长的。这是随机写入（如树中的那些），速度非常慢。即使闪存驱动器在随机写入时也不受磁盘影响，但在顺序写入时依然明显更好。实际上，即使大多数RAM在连续写入时也更好，因为涉及的控制信号较少。

通过使用预写日志，你不必担心：

断写（你写一半树木图像猫吃了你的电源之前）
损失的信息（你实际上并没有坚持这棵树，但乔认为你是这样做的）
来自随机同步磁盘I/O的巨大性能命中。

来源

2010-05-05 23:15:05

嘿！谢谢你的提示！这真的是必须的，因为使用过的内存很容易变满。但是在数据库完全暂时（记录所有更改的数据）的情况下，它实际上只能成为一个文件！从这个意义上说，垃圾收集是我认为最大的（但必要的）减速之一。 – Waneck 2010-05-06 13:00:17

你能否解释为什么使用WAL意味着你不必担心“随机，同步磁盘I/O带来的巨大性能”？ – 2011-01-21 09:08:05

预写日志很少随机读取/写入数据;它总是附加到传统硬盘上的速度很快。是的，系统中会出现其他随机写入，但对于基本上每次更新记录时使用的某些内容，效率都很重要。 – 2011-01-21 19:12:21

我的想法是，你有一个伟大的想法。现在去建立补货的事情。从你写的所有内容来看，这听起来像是你正在遭受analysis paralysis的严重病例。

来源

2010-05-05 16:48:22 rtperson

嘿！我真的很高兴你这样想！我已经编写了代码，但由于这是我第一次编写数据库管理系统，我以为也许我可能在某个地方走错了方向！谢谢！ – Waneck 2010-05-05 17:25:44

这方面的进展如何？ – clintm 2011-10-19 14:34:28

我知道这个问题有点老了，但我一直在实施几乎相同的事情，我发现的是，作为二叉树意味着性能是可怕的（由于数量寻求）。尽管额外的空间开销，尝试制作更广泛的持久树也许是一个更好的主意。

来源

2011-01-21 09:05:06

你完全正确。实际上有一个很好的实现 - couchdb的不可变的b-tree！但是现在我已经改变了这个项目的方向，并且我放弃了对磁盘上纯功能数据结构的需求，因为在这种情况下它们并不是非常紧密的结合。对于无锁结构，最好在内存映射文件上实现CAS操作。 – Waneck 2011-01-21 11:45:20

@Waneck，是的，我看到了couchdb的b-tree（虽然我还没有深入实施）。你介意解释你关于无锁结构的第二个评论吗？我不确定我明白。 – 2011-01-22 09:35:05

请参阅http://stackoverflow.com/questions/2846190/cross-platform-and-cross-process-atomic-int-writes-on-file！在我发现可以对内存映射文件执行比较和交换操作后，我认为持久数据结构对于数据库来说不是一个很好的解决方案。追加只意味着没有局部性，毕竟，磁盘（性能方面）的使用率很差。 – Waneck 2011-01-23 13:58:06

有趣的人likeminded :-)我实际上已经实现了一个使用持久数据结构作为其数据模型的数据库。一种持久的B2树，我想可以称之为它。只追加存储到磁盘和垃圾收集 - 并非所有的历史都需要永久保存。可以设置一个有限的保留期，以便数据库可以忘记早期历史。

请参阅http://bergdb.com/

来源

2013-08-23 01:48:40

在磁盘性能上的持久性（纯功能性）红黑树

回答

相关问题