c# - 如何创建一个Lockfree集合集合

Question

我需要创建一个集合集合。该集合由多个线程调用以添加项和查找项。添加后，项目将不会被删除。目前，在添加元素时我需要锁定整个集合。有没有办法让它无锁。或者我可以使用更好的数据结构或模式吗？这是我的代码的简化版本:

readonly ConcurrentDictionary<string, ConcurrentDictionary<int, int>> dict = new ConcurrentDictionary<string, ConcurrentDictionary<int, int>>();

void AddUpdateItem(string s, int k, int v)
{
    ConcurrentDictionary<int, int> subDict;
    if (dict.TryGetValue(s, out subDict))
    {
        subDict[k] = v;
    }
    else
    {
        lock (dict)
        {
            if (dict.TryGetValue(s, out subDict))
            {
                subDict[k] = v;
            }
            else
            {
                subDict = new ConcurrentDictionary<int, int>();
                subDict[k] = v;
                dict[s] = subDict;
            }
        }
    }
}

Answer 1

您可以通过使用不变性使散列表无锁，但如果存在争用，它可能效率不高。基本上，您需要一个可以原子交换的字典内容类。您构建当前内容的副本，进行一次更改，然后使用比较和交换原语将其与现有版本交换。如果比较和交换失败，请重新开始复制​​步骤。

您也许能够仅以原子方式交换单个哈希桶，这将使争用变得不那么常见，并且重试成本更低。 (ConcurrentDictionary 确实已经使用了这种优化，以减少锁争用)但是增加桶的数量仍然需要上述方法。

看看 Eric Lippert 的博客，他在其中介绍了不可变数据结构。他有a nice example of a binary tree ，它应该向您展示制作无锁哈希表所需的技术。