【关于C#的Dictionary多线程情况下CPU 100%的问题】
C#的偶发性 CPU 100%的问题，定位到是Dictionary线性不安全导致死锁，改成了ConcurrentDictionary 就可以解决问题。
我也知道Dictionary是线性不安全，但我以为它只是在多线程里面会导致脏读的问题而已，并不知道会导致CPU 100%。那我就好奇，为什么Dictionary的ContainsKey方法，会导致CPU100%呢，这里再稍微挖一下。
我简述一下背景，虽然是C#语言，但Dictionary作为一个比较基础的数据类型，其他语言也会有类似的实现，只是名字不一样罢了，下面只涉及一些数据结构和程序实现逻辑，所以应该写过程序的都应该明白。。。
Dictionary是以一种KV(Key-Value)的数据类型，它是一个泛型的类型，Dictonary<TKey, TValue>，可以定义键和值的类型，类似java的HashMap。定义长这样。
image.png
我们回到主题，通过Dump看到CPU 100时代码时卡在了ContainsKey里面，那ContainsKey方法是怎么实现的呢：
image.png
是直接调用了FindEntry，我们继续看FindEntry。
image.png
我们发现FindEntry有一个for循环，代码卡在这个方法内、CPU又100%，那这个循环的嫌疑就非常大了，死循环造成的；那并发情况下会造成死循环吗，我们看到里面几个全局变量，特别是2个集合buckets、entries，循环判断条件是index>=0就继续，按就说我可以顺势猜测，在并发的情况下，有可能出现entry的next永远都大于等于0，所以造成了死循环。那我们再看看这两个集合buckets、entries是干什么的。
我翻了一遍代码之后，代码片段比较凌乱我就不全贴上来了，但确定了buckets和entries这2个集合的用意，我大致解释一下。
我们看一下这两个集合的定义。
image.png
buckets比较简单，int的集合，但entries又是一个Dictionary的内部类Entry，我们看看内部类Entry的数据结构。
image.png
好，材料基本上准备好了，其实这两个很明显就是为了存储Dictonary的字典元素，那具体有什么用的呢。那我们先看看，插入第一个kv值的时候，是怎么存的。我参考了Insert源代码的逻辑，代码有点长我就不贴上来了，有兴趣的同学去搜也能搜得到。
先把插入的KV值里面的Key，做以下计算：
image.png
1、通过GetHashCode，计算出Key的hashcode，int类型的。
2、然后hashcode跟buckets的长度，取余数，得到了一个int值，我称之为bucket_index。
这段算法对应的源代码如下：
image.png
源代码的里面有几个需要注意的地方：
1、源代码里面的index1，就是对应的是我上面定义的bucket_index。
2、另外是题外话，而为什么要 & int.MaxValue呢，这是为了保证num1得到的是一个正数的小技巧。
那我们继续往下，看下图。
image.png
重点看1、2、3步。
1、假设这个要插入的kv值是第一个的话，那第一步就会按着计数，操作的entry_index为0，先把值插入到entries[0]里面存起来。
2、其中，Entry除了存放Key和Value，根据定义还有一个Next，这个Next就是buckets[bucket_index]现在的值。我们从定义可知，buckets默认的值均为-1，所以第一个Next肯定为-1。
3、最后一步，把buckets[bucket_index]的值更新为目前操作的entry_index，在这个例子里面，就是把0放到buckets[bucket_index]。
这段逻辑对应的源代码，如下所示，红框是重点部分。
image.png
先不管为什么数据结构这么设计，我们看看接下来，如果bucket_index算到是其他index，那也是跟上面的逻辑类似，存进去的Entry.next都会为-1，因为buckets的初始化都是-1，但如果bucket_index 算到的值跟之前发生重合呢？
假如插入到第四个kv值，key根据算法算出来的bucket_index跟上面的例子类似的话，根据逻辑走向，如下图步骤4、5、6所示：
image.png
其实步骤逻辑跟上面都是一样的，结果就是
- buckets[bucket_index]从0，变成了3。
- entries[entry_index]的next就再也不是-1，而是旧的buckets[bucket_index]，是0。
基本上，buckets和entries的存储逻辑讲清楚了，那我们回头看看，FindEntry的逻辑是怎么根据Key搜索的。
image.png
1、先把Key按hashcode、取余的方式，先算一遍，得到目标的bucket_index。
2、根据buckets[bucket_index]，就得到了目标的entry_index，从而可以比对hashcode和key是否是要找的那个Key。
3、但这个Key是可能并非可能是找的值，为什么呢，你看上面插入逻辑的例子。2个不一样的Key可以算出同一个bucket_index，所以如果上一步判断并非是找出来的Key的话，就需要根据Next找下一个entry_index，然后再继续做步骤2的比对。
4、不断循环2、3，跳出循环有2个条件，找到了对应的Key，或者Next小于0的时候就跳出循环。为什么Next一定是有小于0，因为根据上面的逻辑，buckets初始化元素是-1，Next存的是bucket的值，所以第一个插入entry的Next肯定是-1，所以必定有等于-1的Next存在。
好的，到了这里，这个数据结构和程序逻辑都清楚了。我们再回头看，为什么并发造成的线程不安全会死循环，怎么才会出现entry的next永远都大于等于0。
我直接指出答案，这是Insert实现的一部分，上面截图里面也有的，但红框不同，如下图所示。
image.png
这个count是一个全局变量，又是什么呢，其实就是entry_index。上面代码的逻辑看得出，每insert一个，count就会+1计数，所以看得出entries是按自然数逐个增长填充的。
这里在多线程里面就会出现问题，this.count会出现脏读的可能，比如同时有2个Insert动作多线程执行的话，此时代码里面的count就是一样的，并不是按+1的规则。如果2次Insert的count是一样，也就是entry_index会一样，会出现什么问题呢，我们回到原来的插入逻辑。
假如并发2次取到count，也就是entry_index都是A；还有一个条件，2次Key计算的bucket_index都是同一个，那么逻辑如下图：
image.png
1、第一次Insert的时候，原来的bucket_index假如是X，X就会存到entries[A].Next = X。
2、然后buckets[bucket_index] = A，从X变成了A。
3、第二次Insert的时候，entry_index仍然是A，所以就会出现entries[A].Next = A。
到这里就出现entries[A].Next = A，出现这个逻辑的话，我们又回到FindEntry的代码。
image.png
注意循环的「末尾循环体」的部分，index=this.entries[index].next。
那如果entries[A].Next = A出现了，那这样index就永远是A，就造成了死循环。
最后总结一下，Dictionary.ContainsKey 方法的确在多线程有可能会造成死循环，条件是：
分析这里就结束了
- 并发的时候，2个Key算出来的bucket_index是一致。
- this.count 出现脏读。
当然，这是其中一种条件，有可能有其他。
所以根据这个结论，如果要重现死循环，多线程执行的方法里面，就不能只有ContainsKey，虽然cpu 100%是在ContainsKey，但数据错乱并不是ContainsKey造成的，多线程执行的方法还需要有Insert，才会有可能触发这个死循环。
分析这里就结束了，最后说一下这个Dictionary的实现方式，为什么要这样实现，其实说白了就是实现Dictionary的算法。
- 用key通过hashcode和取模，得到数组对应的索引位置，这个索引是buckets的索引，buckets存的是entry的递增索引。
- key的取模算法有可能会重复，所以entry对象增加了next，存放上一个重复的entry索引，从而同样key的取模索引的所有entry就组成了一个link的集合。
- 这个效率和存储方式是非常有效率的。
- 但由于上面也看到，entry和bucket是一个数组，数组就是有固定的length，但Dictionary是可以不需要输入length，这个因为Dictionary内部实现了自动扩容。扩容的时候会把现有的entry的next和bucket存放的值全部重新计算一遍。因此需要效率高的话，可以初始化Dictionary，先预计好他的Capacity，初始化的时候先设置好Capacity，减少触发它的自动扩容机制。
- 以下是stackoverflow对这个实现的分析，https://stackoverflow.com/questions/38242613/findentry-function-in-dictionary-cs
image.png
网友评论