atomic-try-update

此库使您能够轻松地正确实现自己的无锁数据结构。除了基本原语之外，我们还提供了一些可以直接使用或作为您自己的应用特定算法基础的示例数据结构。

概述

atomic_try_update 的典型用途包括实现状态机、构建简单的资源分配器、使用“伪单调性”以确定性的方式初始化系统、在堆栈中累积状态以及使用 claim 模式允许并发代码排队并按顺序处理。

与大多数无锁库不同，我们使上述组合保持线性可序列化语义变得容易。例如，您实现一个无锁状态机，在两阶段提交协议中计算投票，然后将其与堆栈结合。生成的代码将每个响应的信息添加到堆栈中，然后恰好一次处理计票结果，而不需要使用互斥锁或精心安排的写入等额外同步。

当我们说“线性可序列化”时，我们是指使用 atomic_try_update 构建的算法的任何执行调度都等效于某种单线程调度，并且系统中的其他代码将就请求的执行顺序达成一致。这大致等同于数据库事务文献中的“严格可序列化”。atomic_try_update 提供的语义介于事务处理系统和 CPU 寄存器之间。我们选择“线性可序列化”这个术语，因为它在讨论寄存器语义时更常用，并且 atomic_try_update 通常限于双字（通常是 128 位）更新。

从性能角度来看，atomic_try_update 在可以拥有许多独立实例且每个实例争用较低的情况下表现最佳。例如，使用单个 atomic_try_update 实例来协调系统中所有读取操作很可能会创建并发瓶颈。为每个客户端连接使用一个可能就不会。这意味着您应该坚持使用其他更专业的算法，例如顶级事件队列和系统中其他高争用单例数据结构。

致谢

这个库提炼了多个人在多个十年中完成的算法工作。然而，我们未能找到关于这种无锁算法设计方法的任何书面文档。如果您了解这个领域的早期研究或系统，请与我们联系，以便我们可以更新本节。

这项工作之所以可能，是因为我们几代同事培训了他们的同事应用这些算法。谢谢。

Dagstuhl研讨班21442“确保数据库管理系统的可靠性和鲁棒性”的参与者为此库的预发布版本提供了有益的反馈。确定性样本代码灵感来源于CALM原则，类似的原始代码由Joe Hellerstein的研究小组独立发明。他们发明了“伪单调性”这个术语来描述产生确定性结果或因运行时错误而失败的并发算法。Mae Milano为我们提供了来自编程语言社区的相关近期工作的全面概述。