如何创建集合的Lockfree集合

本文关键字：集合 Lockfree 创建 何创建 | 更新日期: 2023-09-27 18:11:26

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

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;
            }
        }
    }
}

如何创建集合的Lockfree集合

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

您可能能够自动交换单个哈希桶，这将使争用更少，并且重试更便宜。(ConcurrentDictionary已经使用了这个优化，以减少锁争用)但是增加桶的数量仍然需要上面概述的方法。

看看Eric Lippert的博客，他在其中介绍了不可变数据结构。他有一个很好的二叉树示例，它应该向您展示创建无锁哈希表所需的技术。

方法ConcurrentDictionary.GetOrAdd是线程安全的(尽管不是原子的)。它保证返回的对象对于所有线程都是相同的。您的代码可以重写为:

void AddUpdateItem(string s, int k, int v)
{
    var subDict = dict.GetOrAdd(s, _ => new ConcurrentDictionary<int, int>());
    subDict[k] = v;
}

您是否在代码中使用任务或线程?在任何情况下，ConcurrentDictionary都被设计为线程安全的。在添加或删除元素时不需要使用锁。链接来自MSDN如何:从ConcurrentDictionary中添加和删除项解释了如何使用它。

如果您推测创建子字典，有一个更简单的解决方案:

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;
    while ( true )
    {
        if ( dict.TryGetValue( s, out subDict ) )
        {
            subDict[ k ] = v;
            break;
        }
        // speculatively create new sub-dictionary
        subDict = new ConcurrentDictionary<int, int>();
        subDict[ k ] = v;
        // this can only succeed for one thread
        if ( dict.TryAdd( s, subDict ) ) break;
    }
}

在开始实现无锁集合之前，请先了解一下可以解决问题的ReadWriteLock。如果不是这样(例如，因为有大量的写争用)，就没有真正的放之四海而皆准的方法。

我过去使用的一种技术是使用一个专门用于管理集合的线程，并使用Interlocked.Exchange将新对象编组到该线程，并将不可变集合发送出去。使用这种方法，您的写入器线程被管理在一个单独的列表中，当创建或销毁写入器时，您需要锁定该列表，因此这仅在罕见事件时有效。

相关文章：