c++ - 制作 C++ 哈希表的最佳策略，线程安全

Question

(我对实现的设计感兴趣，而不是一个可以完成所有工作的现成结构。)

假设我们有一个 HashTable 类(不是作为树实现的哈希映射而是哈希表)
并说有八个线程。
假设读写比约为 100:1 或更好的 1000:1。
情况 A)只有一个线程是写入者，而其他线程(包括写入者)可以从 HashTable 中读取(它们可能简单地遍历整个哈希表)
情况 B)所有线程都是相同的，并且都可以读/写。

有人可以建议最好的策略来使类线程安全并考虑以下因素
1. 最高优先级，最小锁争用
2. 最少锁数的第二优先级

到目前为止，我的理解是:
一个 BIG 读写锁(信号量)。
特殊化信号量，以便在情况 B 中可以有八个实例 writer-resource，其中每个 writer 资源锁定一行(或就此而言的范围)。
(所以我猜 1+8 互斥体)

请让我知道我的想法是否正确，以及我们如何改进此解决方案。

Answer 1

有了如此高的读/写比率，您应该考虑无锁解决方案，例如nbds .

编辑:

一般来说，无锁算法的工作原理如下:

安排您的数据结构，以便对于您打算支持的每个功能，您可以在一个原子操作中确定其结果是否有效(即，其他线程在读取后​​没有改变其输入)并委身于他们；除非您提交，否则不会更改其他线程可见的状态。这将涉及利用特定于平台的功能，例如 Win32 的原子比较和交换或 Cell 的缓存行保留操作码。

每个支持的函数变成一个循环，重复读取输入并尝试执行工作，直到提交成功。

在争用非常低的情况下，这是对锁定算法的性能优势，因为函数大部分都是第一次成功，而不会产生获取锁的开销。随着竞争的增加， yield 变得更加可疑。

通常可以原子操作的数据量很小 - 32 或 64 位很常见 - 因此对于涉及许多读取和写入的函数，结果算法变得复杂并且可能很难推理。出于这个原因，最好为您的问题寻找并采用成熟的、经过充分测试且易于理解的第三方无锁解决方案，而不是自行解决。

哈希表的实现细节将取决于哈希表设计的各个方面。我们是否希望能够扩大 table ？如果是这样，我们需要一种方法将大量数据从旧表安全地复制到新表中。我们期望哈希冲突吗？如果是这样，我们需要一些行走碰撞数据的方法。我们如何确保另一个线程不会删除返回它的查找和使用它的调用者之间的键/值对？也许是某种形式的引用计数？ - 但谁拥有引用？ - 或者只是在查找时复制值？ - 但是如果值很大怎么办？

无锁堆栈很好理解并且实现起来相对简单(从堆栈中删除一个项目，获取当前顶部，尝试用它的下一个指针替换它直到成功，返回它；添加一个项目，获取当前顶部并将其设置为项目的下一个指针，直到您成功将项目的指针写入作为新的顶部；在具有保留/条件写入语义的体系结构上，这就足够了，在仅支持 CAS 的体系结构上，您需要附加一个随机数或版本编号到原子操作的数据以避免 ABA problem )。它们是一种以原子锁自由方式跟踪键/数据的可用空间的方法，允许您将键/值对(实际存储在哈希表条目中的数据)减少到一个或两个指针/偏移量，一个小的足够的数量可以使用您的架构的原子指令进行操作。还有其他人。

然后读取变成了查找条目的情况，根据请求的键检查 kvp，做任何事情以确保返回值时该值仍然有效(获取拷贝/增加其引用计数)，检查条目是否'自从我们开始读取以来没有被修改，如果是，则返回值，撤消任何引用计数更改，如果不是，则重复读取。
写入取决于我们对冲突的处理方式；在微不足道的情况下，它们只是找到正确的空槽并写入新的 kvp 的情况。
以上已大大简化，不足以生成您自己的安全实现，尤其是在您不熟悉无锁/无等待技术的情况下。可能的并发症包括 ABA 问题、优先级反转、特定线程的饥饿；我没有解决散列冲突。

nbds 页面链接到 excellent presentation在允许增长/碰撞的现实世界方法上。其他存在，一个快速的谷歌发现很多论文。

无锁和无等待算法是令人着迷的研究领域。我鼓励读者谷歌一下。也就是说，幼稚的无锁实现在很多时候看起来很合理并且行为正确，而实际上却很不安全。虽然牢牢掌握原则很重要，但我强烈建议使用现有的、易于理解和经过验证的实现，而不是滚动自己的实现。