Wan*_*eck 14 database binary-tree functional-programming immutability data-structures
我正在研究实现一个简单的开源对象时态数据库的最佳数据结构,目前我非常喜欢使用持久性红黑树来实现它.
我使用持久数据结构的主要原因首先是最小化锁的使用,因此数据库可以尽可能并行.此外,实现ACID事务更容易,甚至能够抽象数据库以在某种集群上并行工作.这种方法的好处在于它几乎可以免费实现时态数据库.这是非常好的,特别适用于网络和数据分析(例如趋势).
所有这些都非常酷,但我对在磁盘上使用持久数据结构的整体性能有点怀疑.即使今天有一些非常快的磁盘可用,并且所有写入都可以异步完成,所以响应总是立竿见影,我不想在错误的前提下构建所有应用程序,只是意识到它并不是真的好这样做的方式.
这是我的思路: - 由于所有写入都是异步完成的,并且使用持久数据结构将不会使先前(当前有效)结构无效,因此写入时间实际上不是瓶颈.- 有一些关于此类结构的文献正是针对磁盘使用的.但在我看来,这些技术将增加更多的读取开销,以实现更快的写入.但我认为恰恰相反是可取的.这些技术中的许多确实最终会使用多版本树,但它们并不是严格不可变的,这对于证明持久开销非常重要. - 我知道在向数据库附加值时仍然需要进行某种锁定,而且如果不是要维护所有版本,我也知道应该有一个好的垃圾收集逻辑(否则文件大小肯定会大幅上升) .还可以考虑增量压缩系统. - 在所有搜索树结构中,我真的认为红黑是最接近我需要的,因为它们提供最少的旋转次数.
但是在此过程中存在一些可能的缺陷: - 异步写入 - 可能会影响需要实时数据的应用程序.但我不认为Web应用程序就是这种情况,大部分时间都是如此.此外,当需要实时数据时,可以设计另一种解决方案,例如需要以更实时的方式工作的特定数据的登记/结账系统. - 它们也可能导致一些提交冲突,但我没有想到它何时会发生的好例子.如果两个线程使用相同的数据,那么正常的RDBMS中也会发生冲突,对吧？ - 拥有像这样的不可变接口的开销将呈指数级增长,一切都注定要很快失败,所以这一切都是个坏主意.
有什么想法吗？
谢谢!
编辑:似乎存在对持久性数据结构的误解:http: //en.wikipedia.org/wiki/Persistent_data_structure
如果您发现写入时间遇到瓶颈，或者如果没有同步写入，持久性保证就毫无意义（嗯...），您应该执行大多数其他数据库所做的操作：实现预写日志（WAL）或重做-日志。
磁盘实际上非常擅长顺序写入，或者至少这是它们最擅长的。这是随机写入（例如树中的写入），速度非常慢。即使闪存驱动器在随机写入方面击败了磁盘，但在顺序写入方面仍然明显更好。实际上，即使大多数 RAM 也更擅长顺序写入，因为涉及的控制信号较少。
通过使用预写日志，您不必担心：