磁盘上的持久化（纯函数式）红黑树性能问题

Question

磁盘上的持久化（纯函数式）红黑树性能问题

databasedata-structuresfunctional-programmingbinary-treeimmutability

15

我正在研究最适合实现一个简单的开源对象时间数据库的数据结构，并且目前我非常喜欢使用Persistent Red-Black树来实现。

我使用持久化数据结构的主要原因首先是为了尽量减少锁的使用，以便使数据库能够尽可能地并行。此外，这将更容易实现ACID事务，甚至可以抽象出数据库以在某种类型的集群上并行工作。这种方法的好处是可以几乎免费地实现时间数据库。而且这对于Web和数据分析(例如趋势)来说特别有用。

所有这些都很酷，但我有一点怀疑使用持久化数据结构在磁盘上的整体性能。即使今天有一些非常快速的硬盘可用，而且所有写操作都可以异步完成，因此响应总是立即的，我也不想建立在错误的前提下构建整个应用程序，只会意识到这并不是真正好的方法。

这是我的思路： - 由于所有写入操作都是异步执行的，并且使用持久化数据结构将使之前——当前有效的——结构无效，因此写入时间并不是真正的瓶颈。

有一些关于像这个这样的结构的文献，它们专门用于磁盘使用。但是我认为这些技术会增加更多的读取开销以实现更快的写入。但我认为恰恰相反是可取的。此外，许多这些技术确实最终会产生多版本树，但它们并不是严格不变的，这是证明持久开销的关键因素。

我知道在向数据库附加值时仍然需要某种形式的锁定，并且如果不维护所有版本，则应该有良好的垃圾收集逻辑（否则文件大小肯定会大幅上升）。还可以考虑增量压缩系统。

在所有搜索树结构中，我真的认为红黑树是最接近我所需的，因为它们提供了最少的旋转。

但是这条路上可能会有一些潜在的陷阱： - 异步写入可能会影响需要实时使用数据的应用程序。但我认为这通常不适用于Web应用程序。此外，当需要实时数据时，可以设计其他解决方案，例如需要以更实时方式处理的特定数据的签入/签出系统。 - 它们也可能导致一些提交冲突，尽管我无法想到何时会发生。另外，如果两个线程正在使用相同的数据，则普通RDBMS中也可能会发生提交冲突，对吗？ - 具有这样的不变接口的开销将呈指数增长，一切都注定要很快失败，所以这一切都是个坏主意。

任何想法吗？

谢谢！

编辑：似乎有人误解了什么是持久化数据结构： http://en.wikipedia.org/wiki/Persistent_data_structure

- Waneck

1

你能解释一下为什么“我使用持久化数据结构的主要原因首先是为了最小化锁的使用”吗？无论是否持久化，你仍然需要锁定... - Mitch Wheat

1

好的，你是对的。仍然需要使用锁，但将其最小化到绝对最少。例如，在我的情况下，我们只需要在“弱”引用上使用锁，如红黑树的头部。在将所有树的更改附加到文件后，我们只需锁定它以更改指向树头的指针（仅为整数）。没有可能让不知情的读者捕捉到处于不一致状态的树，并且锁应该非常快速地工作。此外，对于写入，仅在更改文件大小（追加数据）时才需要锁。 - Waneck

如果你不知道什么是持久化数据结构（http://en.wikipedia.org/wiki/Persistent_data_structure），为什么不先去查一下呢？Uncle Brad： - Waneck

1

你可能想要查看这个a functional, append-only database（一个功能完备、追加写入的数据库）。 - BlueRaja - Danny Pflughoeft

@Waneck，我写了这个，你可能会感兴趣。 - dan_waterworth

显示剩余2条评论

4个回答

1

我的想法是你有一个很棒的点子。现在去构建它吧。从你写的所有内容来看，听起来你正在遭受分析麻痹的严重情况。

- rtperson

嗨！我很高兴你这么想！我已经在编写代码了，但由于这是我第一次编写数据库管理系统，所以我想可能有些地方我走错了方向！谢谢！ - Waneck

1

我知道这个问题有点老了，但我一直在实现几乎相同的东西，我发现，由于查找次数太多，二叉树的性能非常糟糕。也许更好的想法是尽管会增加额外的空间开销，但尝试制作一个更广泛的持久化树。

- dan_waterworth

你是完全正确的。实际上，有一个很好的实现需要关注 - couchdb的不可变B树！但是现在我已经改变了这个项目的方向，并且放弃了纯函数数据结构在磁盘上的需求，因为它们在这种情况下并不是非常合适的选择。对于无锁结构，最好在内存映射文件上实现CAS操作。 - Waneck

@Waneck，是的，我看过couchdb的b-tree（尽管我没有深入研究实现）。您能否解释一下您关于无锁结构的第二条评论？我不确定我理解。 - dan_waterworth

请看链接 http://stackoverflow.com/questions/2846190/cross-platform-and-cross-process-atomic-int-writes-on-file！当我发现可以在内存映射文件上执行比较并交换操作时，对我来说，持久数据结构似乎不是数据库的很好的解决方案。仅追加意味着没有局部性，并且在所有情况下都会使用磁盘（从性能角度而言）不佳。 - Waneck

1

有兴趣和志同道合的人一起交流 :-) 我实际上已经实现了一个使用持久化数据结构作为数据模型的数据库。我想可以称之为一种持久性B2树。采用追加方式存储到磁盘并进行垃圾回收-不需要永久保存所有历史记录。可以设置有限的保留期限，以便让数据库忘记早期的历史记录。

请见http://bergdb.com/

- Frans Lundberg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andres Jaan Tack · Accepted Answer

如果您发现写入时间瓶颈，或者同步写入缺失导致耐久性保证无意义（嗯...），那么您应该像大多数其他数据库一样实现预写日志（WAL）或重做日志。

实际上，磁盘在顺序写入方面非常出色，或者至少这是它们擅长的。随机写入（例如树中的写入）非常缓慢。即使是闪存驱动器，在随机写入方面也要比磁盘好得多，但仍然比顺序写入要好得多。实际上，大多数RAM在顺序写入方面都更好，因为涉及的控制信号较少。

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

- 撕裂写入（在猫吃掉电源之前，您已经写了一半的树图像） - 信息丢失（您实际上没有将树持久化，但Joe认为您已经完成了） - 随机、同步磁盘I/O带来的巨大性能损失。