c++ - 在磁盘上实现无锁数据结构

Question

对于那些在无锁数据结构和基于磁盘的数据结构方面具有深厚背景的人来说，我有一个有趣的挑战。

我正在寻找一种在 C++ 中构建数据结构以保存不同数量对象的方法。

限制是这样的:

1. 数据结构必须驻留在磁盘上。
2. 有一个线程写入数据结构，许多其他线程从中读取。
3. 每次读取都是原子的。 (假设我可以为此自动读取大小为 32/64KB 的 block ，并且所有对象的大小都小于该 block 。
4. 写入不应阻塞读取，因为可以假设我也可以以原子方式写入 32/64KB 的 block 。
5. 根本不能使用锁。

有什么建议吗？

我正在考虑使用类似 B-Tree 的东西，当需要拆分节点并写入新数据时，而不是将它们移动到文件末尾的新节点，然后只更新指向将要驻留的节点的指针在其他一些文件中(原始 block 将被标记为免费并添加到免费存储中)

但是，如果我的映射文件大于 32/64Kb，我就会遇到问题。假设我希望它只保存 100 万个对象指针，而不是 4 字节/指针，我得到 400 万字节，这大约是4 Megs...(甚至超过 10 亿个对象...)这意味着不能以原子方式编写映射文件。

因此，如果有人对如何实现上述内容有更好的建议 - 或者甚至是某个方向，我们将不胜感激。

据我所知，B-Tree 的所有开源/商业实现都使用某种锁，我无法使用。

谢谢， 最大。

Answer 1

仅仅假设读/写是原子的——主要是因为它们不是原子的，你不会走得太远，你最终会以一种会降低性能的方式来模拟它。

听起来你想研究MVCC ，这是设计无锁数据库时使用的非常标准的机制。基本概念是每次读取都会获得数据库的“快照”——通常以无锁方式实现，即保留旧页面并仅对新页面执行任何修改。一旦旧页面被读者使用完，它们最终会被标记为可重复使用。

虽然 MVCC 比 CPU/RAM 无锁结构复杂得多，但一旦您拥有它，许多相同的乐观无锁模式都适用于使用它。