c# - 通过基于类的当前实现直接枚举ConcurrentDictionary到正常的Dictionary,将它安全地复制吗?

标签 c# multithreading dictionary concurrentdictionary

TL; DR:单个ConcurrentDictionary枚举是否可能两次发射相同的 key ? ConcurrentDictionary类(.NET 5)的current implementation是否允许这种可能性?

我有一个由多个线程同时更改的ConcurrentDictionary<string, decimal>,我想定期将其复制到正常的Dictionary<string, decimal>,并将其传递给表示层以更新UI。有和没有快照语义,有两种复制方法:

var concurrent = new ConcurrentDictionary<string, decimal>();

var copy1 = new Dictionary<string, decimal>(concurrent.ToArray()); // Snapshot

var copy2 = new Dictionary<string, decimal>(concurrent); // On-the-go
我很确定第一种方法是安全的,因为 ToArray 方法返回ConcurrentDictionary的一致 View :

Returns a new array containing a snapshot of key and value pairs copied from the ConcurrentDictionary<TKey,TValue>.


但是我更喜欢使用第二种方法,因为它产生的争用较少。
我很担心获得ArgumentException: An item with the same key has already been added.的可能性。documentation似乎并没有排除这种可能性:

The enumerator returned from the dictionary ... does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.


这是让我担心的情况:
  • 线程A开始枚举ConcurrentDictionary,并且 key X由枚举器发出。然后,线程被操作系统暂时挂起。
  • 线程B删除 key X
  • 线程C使用键X添加一个新条目。
  • 线程A恢复枚举ConcurrentDictionary,枚举器观察到新添加的X条目并将其发出。
  • Dictionary类的构造函数尝试将键X插入两次到新构造的Dictionary中,并引发异常。

  • 我试图重现这种情况,但没有成功。但这并不是100%令人放心的,因为可能导致这种情况出现的条件可能微妙。也许我添加的值没有“正确的”哈希码,或者没有生成“正确的”哈希码冲突次数。我试图通过学习该类的source code来找到答案,但是不幸的是,这太复杂了,我无法理解。
    我的问题是:基于当前实现(.NET 5)的是否安全,可以通过直接枚举来创建ConcurrentDictionary的快速副本,还是我应该进行防御性编码并在每次复制时拍摄快照?

    澄清:我同意谁说使用API​​并考虑其未记录的实现细节是不明智的。但是,a,这就是这个问题的全部内容。出于好奇,这是一个颇有教育意义的问题。我保证,我不打算将获得的知识用于生产代码。 😃

    最佳答案

    Is it possible in practice for a single enumeration of a ConcurrentDictionary, to emit the same key twice?


    这取决于您如何定义“实践”。但是根据我的定义,是的,在实践中ConcurrentDictionary绝对有可能两次发出相同的 key 。就是说,您无法编写正确的代码来假设它不会。
    The documentation clearly states:

    The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.


    它没有提供其他有关行为的陈述,这意味着在调用GetEnumerator()时,键可能存在,例如由。第一个枚举元素,此后将其删除,然后以允许枚举器再次检索相同键的方式再次添加。
    这是我们在实践中唯一可以依靠的东西。
    那就是说,在学术上发言(即不在实践中)…

    Does the current implementation of the ConcurrentDictionary class (.NET 5) allow this possibility?


    在检查the implementation of GetEnumerator() 时,在我看来,当前的实现可以避免多次返回同一 key 的可能性。
    根据代码中的注释,内容为:
    // Provides a manually-implemented version of (approximately) this iterator:
    //     Node?[] buckets = _tables._buckets;
    //     for (int i = 0; i < buckets.Length; i++)
    //         for (Node? current = Volatile.Read(ref buckets[i]); current != null; current = current._next)
    //             yield return new KeyValuePair<TKey, TValue>(current._key, current._value);
    
    然后查看注释中提到的“手动实现的版本”……我们可以看到该实现只对buckets数组进行了迭代,然后在每个存储桶中对构成该存储桶的链接列表进行了迭代,就像注释中的示例代码建议。
    但是看看the code that adds a new element to a bucket,我们看到了:
    // The key was not found in the bucket. Insert the key-value pair.
    var resultNode = new Node(key, value, hashcode, bucket);
    Volatile.Write(ref bucket, resultNode);
    checked
    {
        tables._countPerLock[lockNo]++;
    }
    
    当然,该方法还有更多的功能,但这是症结所在。此代码将bucket列表的开头传递给新的节点构造函数,该构造函数又将新节点插入到列表的开头。然后,bucket变量ref变量将被新的节点引用覆盖。
    IE。新节点将成为列表的新头。
    因此,我们看到:
  • 首次调用_buckets时,枚举器从字典中捕获当前MoveNext()数组。
  • 这意味着即使字典必须重新分配其后备存储以增加存储桶数,枚举器也将继续迭代前一个数组。
  • 此外,如果重新分配了,则旧的链表不会被重用。 The code that reallocates the storage为整个集合创建所有新的链接列表:

  • // Copy all data into a new table, creating new nodes for all elements
    foreach (Node? bucket in tables._buckets)
    {
        Node? current = bucket;
        while (current != null)
        {
            Node? next = current._next;
            ref Node? newBucket = ref newTables.GetBucketAndLock(current._hashcode, out uint newLockNo);
    
            newBucket = new Node(current._key, current._value, current._hashcode, newBucket);
    
            checked
            {
                newCountPerLock[newLockNo]++;
            }
    
            current = next;
        }
    }
    
  • 这意味着最坏的情况是在不重新分配后备存储的情况下删除并重新添加了一个元素(因为这是使用当前正在迭代的同一链表的唯一方法),因此 key 在同一根中结束链表。
  • 但是我们知道,新节点总是会添加到列表的开头。枚举器没有任何回溯的方式,它可以让它看到列表顶部添加的新节点。它所能做的就是继续处理已经存在的列表的其余部分。

  • 我相信这意味着您不能两次获得相同的 key 。
    也就是说,我要指出:ConcurrentDictionary代码很复杂。我非常擅长阅读代码,并且认为上面的分析是正确的。但是我不能保证。哎呀,即使在通读代码的同时,我也对可能的事情和不可行的事情两次交换了看法,因为我没有考虑特殊的可能性。我可能仍然忽略了某些东西,例如一些极端情况链表枚举以某种方式返回到头部,或者_buckets数组以某种方式调整大小,而不是创建原始数组的全新副本(您不能在严格的C#代码中做到这一点,但是CLR具有各种它可能会以性能为目的而做出肮脏的 Action )。
    更重要的是,这些都不重要。底层实现可能由于任何原因而每天发生变化(例如,也许他们在代码中发现了一个错误,而该错误根本无法使用“迭代过程中没有重复键”版本进行修复)。鉴于您的原始问题是在将字典内容作为快照复制到另一个数据结构的上下文中提出的,并且ConcurrentDictionary类实际上确实具有ToArray()方法来提供该功能,因此没有理由编写任何可能绊倒的代码这些可能的极端情况之一。

    关于c# - 通过基于类的当前实现直接枚举ConcurrentDictionary到正常的Dictionary,将它安全地复制吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65417001/

    相关文章:

    c# - 使用 C# 中的方法关闭特定窗体

    java - 在本地分析独立 Java 应用程序的线程

    c++ - 并发队列内存消耗爆炸,然后程序崩溃

    c++ - c++11(atomic)的获取释放操作

    c# - Windows 服务中的并行任务

    c# - mailgun 到电子邮件地址替换为抄送电子邮件地址

    c# - 流利的断言 : string does not contain a definition for ShouldBeEquivalentTo

    javascript - for in 循环不打印所有元素 - Javascript

    python - 将列表列表中的特定索引值替换为相应的字典值

    java - 有没有办法使用 java 8 替换列表中的 Map 值?