Boost.Asio 的同步和并发数据结构模式

Question

我正在寻找一些在 Boost.ASIO 中使用容器数据结构时要应用的指导原则。 Boost.ASIO 文档描述了如何使用 strand 对象来提供对共享资源的序列化访问，而无需显式线程同步。我正在寻找一种系统的方法来将 strand 同步应用于：

STL（或类似 STL）容器（例如，std::deque、std::unordered_map）；和
免等待容器，例如 boost::lockfree::spsc_queue or folly::ProducerConsumerQueue。

下面列出了我的问题。我应该提到我的主要问题是 1-3，但有理由我也准备接受 "These questions are moot/misguided" 作为答案；我在问题 4 中对此进行了详细说明。

要使任意 STL 容器适应安全同步使用，是否足以通过 strand 实例执行其所有操作？
为了适应同步、并发使用的无等待读写容器，通过两个不同的 strands 包装其操作是否足够，一个用于读取操作，一个用于写操作？ This question 暗示 "yes"，尽管在那个用例中作者描述了使用 strand 来协调来自多个线程的生产者，同时大概只从一个线程读取。
如果上面 1-2 的答案是肯定的，那么 strand 是否应该通过调用 boost::asio::post 来管理对数据结构的操作？

为了了解 3. 中的问题，这里是 chat client example:

中的一个片段

void write(const chat_message& msg)
{
  boost::asio::post(io_context_,
      [this, msg]()
      {
        bool write_in_progress = !write_msgs_.empty();
        write_msgs_.push_back(msg);
        if (!write_in_progress)
        {
          do_write();
        }
      });
}

这里，write_msgs_是一个聊天消息队列。我问是因为这是一种特殊情况，其中对 post 的调用可能会调用组合异步操作 (do_write)。如果我只想从队列中压入或弹出怎么办？举一个高度简化的例子：

template<typename T>
class MyDeque {
public:
     push_back(const T& t);
    /* ... */
private:
    std::deque<T> _deque;
    boost::asio::io_context::strand _strand
};

那么 MyDeque::push_back(const T& t) 应该直接调用

boost::asio::post(_strand, [&_deque]{ _deque.push_back(t); })

其他操作也一样吗？还是 boost::asio::dispatch 更合适？

最后，我知道有很多并发向量、哈希映射等的健壮实现（例如，Intel Thread Building Blocks Containers）。但似乎在受限的用例下（例如，仅维护活跃聊天参与者的列表、存储最近的消息等），完全并发的向量或哈希映射的力量可能有点矫枉过正。真的是这样吗？还是我只使用完全并发的数据结构会更好？

Answer 1

I am looking for a systematic way to apply strand synchronization to:

STL (or STL-like) containers (e.g., std::deque, std::unordered_map); and

您正在寻找不存在的东西。最接近的是活动对象，除非您对它们进行异步操作，否则您几乎不需要股。这几乎没有意义，因为对 STL 容器的任何操作都不应该具有足以保证异步的时间复杂度。另一方面，计算复杂性使得添加任何类型的同步都是非常次优的 -

而不是 fine-grained 锁定 [当您将 STL 数据结构作为 ActiveObjects 时，您会自动选择] 您总是会发现 coarse-grained 锁定具有更好的性能。

甚至在设计中，通过减少共享总是比通过 "optimizing synchronization" 获得更高的性能（这是矛盾的）。

wait-free containers such as boost::lockfree::spsc_queue or folly::ProducerConsumerQueue.

为什么还要同步对 wait-free 容器的访问。等待免费意味着没有同步。

子弹

To adapt an arbitrary STL container for safe synchronized use, is it sufficient to perform all its operations through a strand instance?

是的。只是那不是存在的东西。 Strands 包装异步任务（及其完成处理程序，它们只是来自执行者 POV 的任务）。

见上面的咆哮。
To adapt a wait-free read-write container for synchronized, concurrent use, is it sufficient to wrap its operations through two distinct strands, one for read operations and one for write operations?

如前所述，同步访问 lock-free 构造是愚蠢的。

This question hints at a "yes", although in that use case the author describes using a strand to coordinate producers from several threads, while presumably only reading from one thread.

那是 特别是 与 SPSC 队列相关的地方，即对执行 read/write 操作的线程施加额外的约束。

虽然这里的解决方案确实是创建具有对任一操作集的独占访问权限的逻辑执行线程，注意您正在限制任务，这与约束 data.
如果上面 1-2 的答案是肯定的，strand 是否应该通过调用 boost::asio::post 来管理对数据结构的操作？

所以，答案不是 "yes"。正如我在介绍中提到的，通过 post 发布所有操作的想法归结为实现活动对象模式。是的，你可以这样做，不，那不会很聪明。（我很确定如果你这样做，根据定义你可以忘记使用 lock-free 容器）
[....]
Then should MyDeque::push_back(const T& t) just call
```
boost::asio::post(_strand, [&_deque]{ _deque.push_back(t); })
```
是的，这就是 ActiveObject 模式。但是，请考虑如何实施 top()。考虑一下如果您有两个 MyDeque 实例（a 和 `b）并想将项目从一个实例移动到另一个实例，您会怎么做：
```
if (!a.empty()) {
    auto value = a.top();     // synchronizes on the strand to have the return value
    a.pop();                  // operation on the strand of a
    b.push(std::move(value)); // operation on the strand of b
}
```
由于队列 b 不在 a 链上，b.push() 实际上可以在 a.pop() 之前提交，这可能不是您所期望的。此外，非常明显的是，所有 fine-grained 同步步骤的效率远低于对一组数据结构进行所有操作的链。
[...] 但似乎 [...] 完全并发的向量或哈希映射的力量可能有点矫枉过正

完全并发的向量或哈希映射中没有 "force"。他们有成本（在处理器业务方面）和收益（在较低的延迟方面）。在你提到的情况下，延迟很少是问题（注册会话是一个罕见的事件，并且受实际 IO 速度支配），所以你最好使用最简单的东西（IMO 那将是 single-threaded 服务器对于那些数据结构）。让工作人员进行任何 non-trivial 操作 - 他们可以运行在线程池上。（例如，如果您决定实施 chess-playing chat-bot）

您希望链形成逻辑执行线程。您希望将 access 同步到您的数据结构，而不是您的数据结构本身。有时无锁数据结构是一个简单的选择，可以避免必须很好地设计事物，但不要指望它会神奇地表现得很好。

部分链接：

boost::asio and Active Object（Tanner Sansbury on ActiveObject with Asio）有很多想法与您的问题重叠
是我维护连接列表的例子

Boost.Asio 的同步和并发数据结构模式

Synchronized and concurrent data structure patterns with Boost.Asio

c++

concurrency

multithreading

boost-asio

子弹