c++ - 是否可以在 C++ 中实现无锁映射

Question

我们正在开发基于 C/S 的网络应用程序，我们发现添加到 std::map 的锁太多，导致服务器性能变差。

我想知道是否可以实现无锁地图，如果可以，如何实现？那里有开源代码吗？

编辑：实际上我们使用 std::map 来存储套接字信息，我们根据套接字文件描述进行了封装，以包含一些其他必要的信息，例如 ip 地址、端口、套接字类型、tcp 或 udp 等。

总而言之，我们有一张全球地图说

map<int fileDescriptor, socketInfor*> SocketsMap,

那么每个用于发送数据的线程都需要访问 SocketsMap，并且在从 SocketsMap 读取或写入 SocketsMap 之前必须添加互斥锁，这样会因为 SocketsMap 中添加的锁而大大降低整个应用程序的并发度。

为了避免并发级别的问题，我们有两种解决方案： 1. 分别存储每个 socketInfor* 2. 使用某种无锁映射。

我想找一些无锁的地图，因为这个解决方案所需的代码更改比解决方案1要少得多。

score 20 · Accepted Answer

实际上有一种方法，虽然我自己没有实现它，但有一篇关于无锁地图的论文使用著名 C++ 专家 Andrei Alexandrescu 的危险指针。

score 5 · Accepted Answer

是的，我已经使用“拆分有序列表”概念在 C++ 中实现了无锁无序映射( docs )。它是一个自动扩展容器，支持 64 位 CAS 上的数百万个元素，没有 ABA 问题。在性能方面，它是一头野兽（参见第 5 页）。它已经过数百万随机操作的广泛测试。

score 2 · Accepted Answer

HashMap 会适合吗？看看Intel Threading Building Blocks，他们有一个有趣的并发映射。我不确定它是无锁的，但希望您对良好的多线程性能感兴趣，而不是特别对无锁感兴趣。你也可以检查CityHash lib

编辑：

实际上 TBB 的哈希映射不是无锁的

score 2 · Accepted Answer

2

如果你使用 C++11，你可以看看facebook/folly的 AtomicHashMap

于 2014-12-24T08:45:20.160 回答

score 1 · Accepted Answer

如果两个操作同时处理映射并且一个正在更改映射结构的机会相对较小，则此方法特别有效 - 并且您不希望每次都锁定开销。

但是，有时会发生碰撞，您将不得不以某种方式导致它（通常通过回滚到最后一个稳定状态并重试操作）。

如果您的硬件支持足够好的原子操作 - 这可以通过比较和交换 (CAS)轻松完成- 您可以单独更改参考（并且无论何时更改地图，您都在使用地图的副本，而不是原始地图，并仅在您提交时将其设置为主要）。

score 1 · Accepted Answer

我很惊讶没有人提到它，但是 Click Cliff 已经在 Java 中实现了一个无需等待的哈希映射，我相信它可以移植到 C++，

6 回答 6