在上一篇文章你真的了解字典嗎?一文中我介紹了Hash Function和字典的工作的基本原理.
有網友在文章底部評論,說我的Remove和Add方法沒有考慮線程安全問題.
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?redirectedfrom=MSDN&view=netframework-4.7.2
查閱相關資料後,發現字典.net中Dictionary本身時不支援線程安全的,如果要想使用支援線程安全的字典,那麼我們就要使用ConcurrentDictionary了.
在研究ConcurrentDictionary的源碼後,我覺得在ConcurrentDictionary的線程安全的解決思路很有意思,其對線程安全的處理對對我們項目中的其他高并發場景也有一定的參考價值,在這裡再次分享我的一些學習心得和體會,希望對大家有所幫助.
ConcurrentDictionary是Dictionary的線程安全版本,位于System.Collections.Concurrent的命名空間下,該命名空間下除了有ConcurrentDictionary,還有以下Class都是我們常用的那些類庫的線程安全版本.
BlockingCollection:為實作 IProducerConsumerCollection 的線程安全集合提供阻塞和限制功能。
ConcurrentBag:表示對象的線程安全的無序集合.
ConcurrentQueue:表示線程安全的先進先出 (FIFO) 集合。
如果讀過我上一篇文章你真的了解字典嗎?的小夥伴,對這個<code>ConcurrentDictionary</code>的工作原理應該也不難了解,它是簡簡單單地在讀寫方法加個<code>lock</code>嗎?
如下圖所示,在字典中,數組entries用來存儲資料,buckets作為橋梁,每次通過hash function擷取了key的哈希值後,對這個哈希值進行取餘,即<code>hashResult%bucketsLength=bucketIndex</code>,餘數作為buckets的index,而buckets的value就是這個key對應的entry所在entries中的索引,是以最終我們就可以通過這個索引在entries中拿到我們想要的資料,整個過程不需要對所有資料進行周遊,的時間複雜度為1.
ConcurrentDictionary的資料存儲類似,隻是buckets有個更多的職責,它除了有dictionary中的buckets的橋梁的作用外,負責了資料存儲.
key的哈希值與buckets的length取餘後<code>hashResult%bucketsLength=bucketIndex</code>,餘數作為buckets的索引就能找到我們要的資料所存儲的塊,當出現兩個key指向同一個塊時,即上圖中的John Smith和Sandra Dee他同時指向152怎麼辦呢?存儲節點Node具有Next屬性執行下個Node,上圖中,node 152的Next為154,即我們從152開始找Sandra Dee,發現不是我們想要的,再到154找,即可取到所需資料.
由于官方原版的源碼較為複雜,了解起來有所難度,我對官方源碼做了一些精簡,下文将圍繞這個精簡版的ConcurrentDictionary展開叙述.
https://github.com/liuzhenyulive/DictionaryMini
ConcurrentDictionary中的每個資料存儲在一個Node中,它除了存儲value資訊,還存儲key資訊,以及key對應的hashcode
而整個ConcurrentDictionary的資料存儲在這樣的一個Table中,其中m_buckets的Index負責映射key,m_locks是線程鎖,下文中會有詳細介紹,m_countPerLock存儲每個lock鎖負責的node數量.
ConcurrentDictionary會在構造函數中建立Table,這裡我對原有的構造函數進行了簡化,通過預設值進行建立,其中DefaultConcurrencyLevel預設并發級别為目前計算機處理器的線程數.
ConcurrentDictionary中較為基礎重點的方法分别位Add,Get,Remove,Grow Table方法,其他方法基本上是建立在這四個方法的基礎上進行的擴充.
向Table中添加元素有以下亮點值得我們關注.
開始操作前會聲明一個tables變量來存儲操作開始前的m_tables,在正式開始操作後(進入lock)的時候,會檢查tables在準備工作階段是否别的線程改變,如果改變了,則重新開始準備工作并從新開始.
通過GetBucketAndLockNo方法擷取bucket索引以及lock索引,其内部就是取餘操作.
對資料進行操作前會從m_locks取出第lockNo個對象最為lock,操作完成後釋放該lock.多個lock一定程度上減少了阻塞的可能性.
在對資料進行更新時,如果該Value的Type為允許原子性寫入的,則直接更新該Value,否則建立一個新的node進行覆寫.
該方法依據CLI規範進行編寫,簡單來說,32位的計算機,對32位元組以下的資料類型寫入時可以一次寫入的而不需要移動記憶體指針,64位計算機對64位以下的資料可一次性寫入,不需要移動記憶體指針.保證了寫入的安全.
詳見12.6.6 http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-335.pdf
從Table中擷取元素的的流程與前文介紹ConcurrentDictionary工作原理時一緻,但有以下亮點值得關注.
讀取bucket[i]在Volatile.Read()方法中進行,該方法會自動對讀取出來的資料加鎖,避免在讀取的過程中,資料被其他線程remove了.
Volatile讀取指定字段時，在讀取的記憶體中插入一個記憶體屏障，阻止處理器重新排序記憶體操作，如果在代碼中此方法之後出現讀取或寫入，則處理器無法在此方法之前移動它。
Remove方法實作其實也并不複雜,類似我們連結清單操作中移除某個Node.移除節點的同時,還要對前後節點進行連結,相信一塊小夥伴們肯定很好了解.
當table中任何一個m_countPerLock的數量超過了設定的門檻值後,會觸發此操作對Table進行擴容.
<code>lock[]</code>:在以往的線程安全上,我們對資料的保護往往是對資料的修改寫入等地方加上lock,這個lock經常上整個上下文中唯一的,這樣的設計下就可能會出現多個線程,寫入的根本不是一塊資料,卻要等待前一個線程寫入完成下一個線程才能繼續操作.在ConcurrentDictionary中,通過雜湊演算法,從數組<code>lock[]</code>中找出key的準确lock,如果不同的key,使用的不是同一個lock,那麼這多個線程的寫入時互不影響的.
寫入要考慮線程安全,讀取呢?不可否認,在大部分場景下,讀取不必去考慮線程安全,但是在我們這樣的鍊式讀取中,需要自上而下地查找,是不是有種可能在查找個過程中,鍊路被修改了呢?是以ConcurrentDictionary中使用Volatile.Read來讀取出資料,該方法從指定字段讀取對象引用,在需要它的系統上，插入一個記憶體屏障，阻止處理器重新排序記憶體操作，如果在代碼中此方法之後出現讀取或寫入，則處理器無法在此方法之前移動它。
在ConcurrentDictionary的更新方法中,對資料進行更新時,會判斷該資料是否可以原子寫入,如果時可以原子寫入的,那麼就直接更新資料,如果不是,那麼會建立一個新的node覆寫原有node,起初看到這裡時候,我百思不得其解,不知道這麼操作的目的,後面在jeo duffy的部落格中Thread-safety, torn reads, and the like中找到了答案,這樣操作時為了防止torn reads(撕裂讀取),什麼叫撕裂讀取呢?通俗地說,就是有的資料類型寫入時,要分多次寫入,寫一次,移動一次指針,那麼就有可能寫了一半,這個結果被另外一個線程讀取走了.比如說我把 <code>劉振宇</code>三個字改成<code>周傑倫</code>的過程中,我先把劉改成周了,正在我準備去把振改成傑的時候,另外一個線程過來讀取結果了,讀到的資料是<code>周振宇</code>,這顯然是不對的.是以對這種,更安全的做法是先把<code>周傑倫</code>三個字寫好在一張紙條上,然後直接替換掉<code>劉振宇</code>.更多資訊在CLI規範12.6.6有詳細介紹.
<code>checked</code>和<code>unckecked</code>關鍵字.非常量的運算(non-constant)運算在編譯階段和運作時下不會做溢出檢查,如下這樣的代碼時不會抛出異常的,算錯了也不會報錯。
但是我們知道,int的最大值是2147483647,如果我們将上面這樣的代碼嵌套在<code>checked</code>就會做溢出檢查了.
相反,對于常量,編譯時是會做溢出檢查的,下面這樣的代碼在編譯時就會報錯的,如果我們使用<code>unckeck</code>标簽進行标記,則在編譯階段不會做移除檢查.
那麼問題來了,我們當然知道checked很有用,那麼uncheck呢?如果我們隻是需要那麼一個數而已，至于溢出不溢出的關系不大，比如說生成一個對象的HashCode，比如說根據一個算法計算出一個相對随機數，這都是不需要準确結果的,ConcurrentDictionary中對于<code>m_keyRehashCount++</code>這個運算就使用了unchecked,就是因為m_keyRehashCount是用來生成哈希值的,我們并不關心它有沒有溢出.
<code>volatile</code>關鍵字,表示一個字段可能是由在同一時間執行多個線程進行修改。出于性能原因，編譯器\運作時系統甚至硬體可以重新排列對存儲器位置的讀取和寫入。聲明的字段volatile不受這些優化的限制。添加volatile修飾符可確定所有線程都能按照執行順序由任何其他線程執行的易失性寫入,易失性寫入是一件瘋狂的事情的事情:普通玩家慎用.
本部落格所涉及的代碼都儲存在github中,Take it easy to enjoy it!
https://github.com/liuzhenyulive/DictionaryMini/blob/master/DictionaryMini/DictionaryMini/ConcurrentDictionaryMini.cs