使用双缓冲技术进行并发读写？

Question

我有一个比较简单的应用场景：

1. 我的程序将通过Websockets接收更新，并使用这些更新来更新其本地状态。这些更新非常小（通常是< 1-1000字节JSON，所以< 1ms进行反序列化），但非常频繁（高达〜1000/s）。
2. 同时，该程序将从本地状态读取/评估并输出其结果。
3. 这两个任务都应该并行运行，并将持续运行整个程序的时间，即永远不会停止。
4. 本地状态的大小相对较小，因此内存使用量不是一个大问题。

棘手的部分在于更新需要“原子”发生，这样它就不会从本地状态中读取例如仅写入了一半更新的本地状态。根据我目前的了解，状态不受原语限制，可能包含任意类，因此我无法通过像使用Interlocked原子操作这样简单的方法来解决它。我计划在自己的线程上运行每个任务，因此在这种情况下总共有两个线程。

为了实现这个目标，我想使用双缓冲技术，其中：

1. 它保留两份状态副本，以便可以在写入另一个副本时从一个副本中读取。
2. 线程可以通过使用锁来通信它们正在使用哪个副本。即，写入线程在写入时锁定副本；读取线程在完成当前副本后请求访问锁；写入线程看到读取线程正在使用它，因此会切换到其他副本。
3. 写入线程跟踪其对当前副本所做的状态更新，因此当它切换到另一个副本时，它可以“追赶上来”。

这就是想法的一般要点，但实际实现当然会有所不同。

我尝试查找是否存在常见解决方案，但并没有找到太多信息，所以让我想到了一些问题：

1. 这是可行的，还是我遗漏了什么？
2. 是否有更好的方法？
3. 这是常见的解决方案吗？如果是，通常称为什么？
4. （额外加分）是否有一些相关主题的好资源可供阅读？

基本上，我感觉自己已经遇到了瓶颈，无法找到更多资源和信息，以查看这种方法是否“好”。我计划在.NET C#中编写此代码，但我认为这些技术和解决方案可以转换为任何语言。欢迎提供任何见解。

- Buretto

---

本地状态是可变的还是不可变的？ - Theodor Zoulias

Answer 1

你实际上需要四个缓冲区/对象。两个缓冲区/对象归读取器所有，一个归写入者所有，一个在邮箱中。

读取器--每当他完成对较新对象的一组原子操作时，就使用交换操作将他的旧对象句柄（指针或索引无关紧要）与邮箱的对象交换。然后他查看新获得的对象，并比较序列号和他刚读取（仍在持有）的对象，以确定哪个是较新的。

写入者--将最新数据的完整副本写入他的对象，然后使用交换操作将他新写入的对象与邮箱中的对象交换。

正如你所看到的，写入者可以随时窃取邮箱对象，但永远不能窃取读取器正在使用的对象，因此读取操作保持原子性。读取器也可以随时窃取邮箱对象，但永远不能窃取写入者正在使用的对象，因此写入操作保持原子性。

只要互换函数生成正确的内存屏障（对于写线程中完成的交换操作为释放，对于读线程为获取），对象本身可以是任意复杂的。

- Ben Voigt

---

嗯，我还没有完全理解为什么阅读器需要使用两个对象/缓冲区，它不能只使用一个并与邮箱进行比较以查看是否有任何更新，然后交换吗？我感觉从技术上讲，我可以只使用总共两个缓冲区（使用我在帖子中概述的想法），但这可能会更加混乱和复杂。我真的很喜欢邮箱的想法，它似乎简单直观，由于内存不是我的问题，使用3-4个缓冲区并不是什么大问题。我一定会研究这个。谢谢。 - Buretto

@Bureto：“与邮箱比较”是一个问题。当对象在邮箱中时，您无法访问它，因为写入者可以随时交换邮箱并在您读取它时开始写入对象。在检查之前，您必须将对象从邮箱中交换出来。 - Ben Voigt

如果我理解有误，请纠正我，以下是我对其工作原理的理解：

1. 通过引用（当然）将邮箱对象读入临时占位符对象中进行交换。
2. 对于写入者，它可以通过完成交换并使用“Interlock.Exchange”来更新邮箱引用以获取新对象的序列号来完成其工作。
3. 对于读取器，它会检查占位符对象的序列号与其当前“主要”对象的序列号，并且如果占位符的序列号较高，则占位符将成为主要对象，并且...

- Buretto

@Bureto：避免锁是我的解决方案的一个特点，但你试图消除第四个对象会引入竞争条件（在C++中这是即时未定义行为，在C#中您仍然可以获得类型安全保证，但不能保证实际找到的值）。读者需要通过Interlocked.Exchange从邮箱中获取对象来声明该对象（序列号存储在该对象中）。仅仅创建另一个指向同一对象的“占位符”句柄（指针/索引/任何东西），该对象仍由邮箱拥有，这是不安全的。 - Ben Voigt

@Bureto：然而，除了你必须在对象在邮箱中时停止尝试读取之外，你对于在发布前在写入者中递增序列号并在读取者中检查以决定是否替换“主要对象”的理解是完全正确的。 - Ben Voigt

Answer 2

如果我理解正确，写操作本身是同步的。如果是这样的话，那么也许不需要保留两份副本，甚至不需要使用锁。

也许像这样做可以起到作用？

State state = populateInitialState();

...

// Reader thread
public State doRead() {
    return makeCopyOfState(state);
}

...

// Writer thread
public void updateState() {
    State newState = makeCopyOfState(state);

    // make changes in newState

    state = newState;
}

- obe

---

不幸的是，在我的情况下，更新可能会影响状态的大范围（即不仅仅是其中的一小部分），因此我必须最终复制任意大的状态 AFAICT。嗯...也许这暗示了我结构化状态的不良。我知道这个想法如何工作，如果使用Interlocked/原子交换函数，我一定会记住它。感谢你的洞察力。 - Buretto

Answer 3

看起来您正在使用输入-处理-输出模式的多线程流水线。当问题简单时，有时会合并输入和处理阶段（或处理和输出阶段）。

您添加了C#标签，因此使用类似BlockingCollection的东西可能是在输入和输出线程之间进行通信的有用方式。由于本地状态相对较小（您的话），因此从输入线程向输出线程发布包含本地状态副本的数据对象可能是一个简单的解决方案。这遵循共享无内容哲学，满足原子要求，因为当前状态的快照已排队。队列包含状态更改的积压，满足“追赶”功能。

通常情况下，当试图确定在两个或多个线程（或进程、服务、服务器等）之间进行何种通信以及如何进行通信时，消息模式和对话模式是有用的资源。

- Daniel Dearlove