concurrency - 何时使用破坏者模式以及何时使用工作窃取本地存储？

Question

以下是否正确？

disruptor pattern 如果必须以多种方式(io 操作或注释)处理每个条目，则具有更好的并行性能和可扩展性，因为可以使用多个消费者进行并行化而不会发生争用。

相反， work stealing (即在本地存储条目并从其他线程窃取条目)如果每个条目必须仅以单一方式处理，则具有更好的并行性能和可扩展性，因为在破坏者模式中将条目不连续地分布到多个线程上会导致争用。

(当涉及多个生产者(即 from boost )时，破坏者模式是否仍然比其他无锁多生产者多消费者队列(例如 CAS operations )快得多？)

我的情况详细 :

处理一个条目可能会产生几个新条目，它们最终也必须被处理。性能具有最高优先级，按 FIFO 顺序处理的条目具有第二优先级。

在当前实现中，每个线程使用本地 FIFO，在其中添加新条目。空闲线程从其他线程的本地 FIFO 中窃取工作。线程处理之间的依赖关系使用无锁解决， mechanically sympathetic哈希表(写入时的 CAS，具有存储桶粒度)。这会导致非常低的争用，但有时会破坏 FIFO 顺序。

使用干扰器模式将保证 FIFO 顺序。但是，将条目分发到线程上是否会导致比具有工作窃取功能的本地 FIFO(每个线程的吞吐量大致相同)更高的争用(例如，读取游标上的 CAS)？

我找到的引用文献

the standard technical paper on the disruptor 中的性能测试(第 5 + 6 章)不包括不相交的工作分配。

https://groups.google.com/forum/?fromgroups=#!topic/lmax-disruptor/tt3wQthBYd0是我在破坏者 + 工作窃取方面找到的唯一引用资料。它指出，如果有任何共享状态，每个线程的队列会显着变慢，但没有详细说明或解释原因。我怀疑这句话是否适用于我的情况:

使用无锁哈希表解决共享状态；

必须在消费者之间不连续地分发条目；

除工作窃取外，每个线程仅在其本地队列中读写。

Answer 1

更新 - 最大化性能的底线:您需要以惯用的语法编写破坏者和窃取工作，然后进行基准测试。

对我来说，我认为区别主要在于消息重点与任务重点之间的区别，因此也在于您想要思考问题的方式。尝试解决您的问题，如果它以任务为中心，那么 Disruptor 是一个不错的选择。如果问题是针对消息的，那么您可能更适合使用另一种技术，例如窃取工作。

使用 偷工减料当你的实现是 消息聚焦 .每个线程都可以选择一条消息并运行它直到完成。例如 HTTP 服务器 - 每个入站 http 请求都分配了一个线程。该线程专注于从头到尾处理请求 - 记录请求、检查安全控制、执行 vhost 查找、获取文件、发送响应和关闭连接

使用 破坏者当你的实现是 重点任务 .每个线程可以在处理的特定阶段工作。替代示例:对于任务焦点，处理将分为多个阶段，因此您将有一个执行日志记录的线程、一个用于安全控制的线程、一个用于 vhost 查找的线程等；每个线程专注于其任务并将请求传递给管道中的下一个线程。阶段可能是并行的，但整体结构是一个专注于特定任务的线程，并在线程之间传递消息。

当然，您可以更改您的实现以更好地适应每种方法。

在您的情况下，如果您想使用 Disruptor，我会以不同的方式构建问题。通常，您可以通过让单个线程拥有状态并通过该工作线程传递所有任务来消除共享状态 - 在 SEDA 中查找大量这样的图表。这可能有很多好处，但同样，这真的取决于您的实现。

更详细一些:

Disruptor - 当需要严格的阶段排序时非常有用，当所有任务的长度一致时额外的好处，例如:外部系统没有阻塞，每个任务的处理量非常相似。在这种情况下，您可以假设所有线程将在系统中均匀工作，因此会安排 N 个线程来处理每 N 条消息。我喜欢将 Disruptor 视为实现线程处理阶段的类似 SEDA 的系统的有效方法。您当然可以拥有一个应用程序，它具有单个阶段和多个并行单元在每个阶段执行相同的工作，但是在我看来这并不是真正的重点。这将完全避免共享状态的成本。

工作窃取 - 当任务具有不同的持续时间并且消息处理的顺序不重要时使用它，因为这允许空闲且已经消耗其消息的线程从另一个任务队列继续进行。这样，例如，如果您有 10 个线程，其中 1 个在 IO 上被阻塞，则其余线程仍将完成它们的处理。