Go語言并發安全的Map探索及研究

關鍵詞： Golang 并發安全 sync.Map 分片加鎖實現 實驗設計 技術選型

在我國，云計算產業發展迅速，市場從最初的10億發展到目前的1 000 億規模。根據云架構的特點，定義最佳路徑以最大化云的使用和價值，已經成為業界的迫切要求，于是，“云原生”概念應運而生。在云原生領域，大多數項目都是用Go 語言實現的，包括知名的容器運行時代表Docker、事實上的容器編排標準Kubernetes等。目前，一些大型IT 公司也在使用Go 語言對部分業務進行重組。Go 語言可以說是云原生的第一個開發語言。

與其他語言一樣，在高并發場景下，進程和線程（協程）可能會出現臟數據讀取、臟寫入、資源爭用導致死鎖等問題。為了避免出現這些問題，就有了并發安全。Go 語言的Map 是開發過程中常用的內置數據結構，它可以很方便地在特定的鍵值結構上執行CRUD操作。然而，在官方的設計中，它并不是一種可以在并發場景下進行并發讀寫的線程安全類型，因此需要考慮對其進行一些線程安全的改造。

1 Map 設計與并發不安全性

1.1 標準庫中Map 的設計

Go 語言中的Map 可以存儲非單一數據類型的元素，它是一種“無序”的鍵值對（key/value）的集合。在底層數據結構上，Map是一種哈希表[1（] hash table）的特定實現。Go 語言的Map 主要包括數據存放和數據定位這兩個部分。

Map 的核心數據結構位于runtime/map.go，如圖1所示，主要包括hmap、mapextra 和bmap 這3 個結構體。

hmap 表示一個Map，mapextra 表示溢出桶，而bmap 表示每一個具體的桶。

無論是在Map 中存儲一個鍵值還是查找一個鍵值，首先都得先找到所在的位置。定位鍵（以下以 key代替）的一般流程如圖2 所示。

大致步驟具體如下。

（1）判斷hmap 是否為nil，或者h.count 值是否為0，如果h 為nil 則表示未初始化，則可能panic，如果h.count=0，則表示該Map 為空，則直接返回一個零值。

（2）判斷是否處于并發讀寫狀態，如果是則產生panic。

（3）對做hash，得到一個值，將其記作HASH_VALUE。不同類型的key，所用的hash算法是不一樣的，具體可以參考algarray。

（4）根據B 值（如圖中的B 是5），則桶的長度是32，并取HASH_VALUE 低5 位的掩碼值m ：= bucket‐Mask（h.B），這個值就是桶編號，00100 對應的十進制是4，計算當前bucket 的地址b： = （*bmap） （add（h. buckets，（hashamp;m）*uintptr（t.bucketsize））），定位到4 號桶。

（5）根據h.oldbuckets 是否為nil，判斷是否處于擴容中。如果不是nil，則表示當前Map 正處于擴容狀態。將m 減少一半mgt;gt;=1，重新計算當前key 在oldbuckets中的位置。如果oldbuckets 沒有全部遷移到新bucket，則在oldbuckets中查找。

（6）然后使用HASH_VALUE的高8位，以10010001為例，它對應的10進制數是145。

（7）在4 號桶中尋找tophash 值為145 的key，找到了0 號槽位，這樣整個查找過程就結束了。這一步的tophash 的設計很巧妙。通過對鍵進行hash 運算后，得到的最后低B 位可以鎖定到哪一個桶，但是每個桶中還有8 個元素，并且還有可能有溢出桶。因為做hash運算太耗時，所以為了提高性能，在每個桶中查找鍵時，不會做傳入的鍵==hash（桶中的鍵）這種操作。而是利用空間換時間，在Map 賦值階段，就提前將計算好鍵的hash 值并將高8 位存入tophash 中。這樣在查找時，就直接和tophash 里的值進行比較，可以提高性能。

（8）如果在桶中沒找到，并且溢出桶的指針不為空，還要繼續去溢出桶中查找，直到找到。如果所有的鍵槽位都找遍了，包括所有的溢出桶，就會返回Map 對應的類型的零值。

（9）如果是存儲操作，當兩個不同的鍵落在同一個桶中，此時就發生了哈希沖突。解決沖突的手段是使用鏈表，在對應的那個桶中，從前往后找到第一個空位插入。這樣，在查找某個鍵時，先找到對應的桶，再去遍歷桶中的鍵。

1.2 并發不安全性

但是，標準庫中的Map 不是并發安全的[2]。從圖3的代碼示例中可以看到，原生Map 在并發場景下，即使鍵不一樣，但只要存在同時讀寫，線程就是不安全的，進行并發讀寫時會發生運行時錯誤。

上面的代碼在運行期拋出了“fatal error： concurrentmap read and map write”異常，表示在讀寫過程中出現了同時讀寫的問題。為什么會出現這個問題呢？在Map 底層源代碼，如圖4 中所示的3 段代碼是針對讀和寫的函數，它們都有一段檢查是否并發的代碼。如果有并發，在會拋出panic。這個就是標準庫Map 不支持并發的根本原因。

Go 語言官方文檔對“Map 不能安全地并發使用[3]”這個問題專門做了說明：Map 不能安全地并發使用：同時讀寫Map 時的行為是未知的。如果需要并發讀寫Map，則必須通過某種同步機制來協調訪問。

同時，Go又對Map實現了一些特殊檢查，即使不使用go run -race 工具鏈對相關代碼進行沖突檢測，在并發不安全地修改Map時，該檢查會在運行時自動報告。

2 Map 的改進及優化

上面的示例代碼從表面上看，操作是不同的鍵，看起來是讀寫這兩個協程在各自操作不同的元素，而Map也沒有擴容的問題，但是在運行時卻檢測到Map有并發訪問，所以會發生panic，解決方法有如下幾種。

（1）使用sync.Mutex 或者sync.RWMutex 實現并發互斥邏輯[4-5]。利用sync.RWMutex 實現并發互斥邏輯。造成沖突的根本原因是Map 并發是不安全的。避免Map 并發讀寫產生panic 的方法之一就是加鎖，考慮到讀寫性能，可以使用讀寫鎖sync.RWMutex 自己實現并發互斥邏輯。

（2）使用sync.Map。使用1.9版本引入的sync.Map，它是官方實現的線程安全的Map，通過空間換時間，來達到并發安全的目的。

（3）通過分片加鎖實現更高效并發Map。雖然使用讀寫鎖可以提供線程安全的Map，但是在有大量并發讀寫的情況下，鎖的競爭會非常激烈。在這種情況下，需要盡量減小鎖的粒度和減少鎖的持有時間。減小鎖的粒度常用的方法就是分片（Sharding），將一把鎖分成幾把鎖，每個鎖控制一個分片。

2.1 MutexMap

在并發場景下，使用互斥鎖可以讓同一時刻只有一個協程對Map 進行讀寫操作。因此，使用Go 語言封裝的特性，使用一個結構體對sync.Mutex 和Map 進行封裝。這樣，這個新的結構化對象就可以確保在并發環境中只有一個協作程序可以進行讀寫操作，從而消除并發讀寫問題的影響。代碼示例如圖5 所示。

2.2 RWMutexMap

Mutex Map 的實現可以提供線程安全映射，但由于互斥鎖的功能，如果并發讀寫數較多，則鎖的競爭非常激烈。特別是在并發讀取較多的場景中，互斥鎖會嚴重影響讀取性能。可以參考RWMutex 對Mutex 的優化方式，使用讀寫鎖定代替Mutex 進行優化。

2.3 sync.Map

除了使用鎖定來控制讀取和寫入外，Go 1.9 版本的標準庫還包含與線程安全相關的數據結構sync.Map。sync.Map 對RWMutexMap 進行了一些優化，具體敘述如下。

（1）空間換時間。使用兩個冗余數據結構（只讀字段read、可寫字段dirty）減少鎖定功能對性能的影響。

（2）讀寫分離[6]。與讀（更新）相關的操作將通過未加鎖的read 盡可能多地執行，與寫（新）相關的操作將通過dirty 加鎖執行。對只讀字段（read）的操作不需要加鎖。優先從read 中讀取、更新、刪除。

（3）動態調整。所有新記錄的key 都只存在于dirty 中。如果多次讀取dirty 中的key，dirty 將升級為不需要鎖定的read，避免總是從dirty 中加鎖讀取。

（4）多重檢查。鎖定后，必須再次檢查read 字段，以確保在操作dirty 字段之前實際上不存在。

（5）延遲刪除。刪除鍵值只是打標記，只有在將dirty 提升到read 時，才會清理刪除的數據。新增keyvalue時，標記成enpunged；dirty 上升成read 時，標記刪除的key 被批量移出Map。這樣一來，在dirty 成為read之前，這些key 都會命中read，而read 不需要加鎖，無論是讀還是更新，性能都很高。

不過，如sync 包文檔中所述，sync.Map 并非替換內置Map 的，而是僅應用于特定場景。在下面所列舉的兩個場景中，與使用讀寫鎖提供線程安全的Map 相比，使用sync.Map 的性能更好，具體如下：只會增長的緩存系統中，對鍵一寫多讀；多個協程操作的key 集合沒有交集（或者交集很少），即多個協程CRUD 操作不同的key-value。

兩種場景的使用條件都較為苛刻，所以官方建議先對自己的場景做性能測評[7-8]，如果實際上可以顯著提高性能，再去使用sync.Map。

2.4 通過分片加鎖實現

通過互斥鎖或者讀寫鎖實現的線程安全的Map，功能上滿足要求。但是，從高并發性角度來說，鎖是性能下降的根本原因。因此，并發編程的原則是最大限度地減少鎖定的使用。當不得不使用鎖時，可以減少鎖粒度和持有時間，從而降低鎖的影響。

使用互斥鎖或讀寫鎖定時，鎖定的對象是整個Map，如果協程對Map 中的key 進行修改操作，則其他協程將無法讀取和寫入其他key。分片的解決方法是將Map 分割成N 個塊，各塊之間的讀寫操作是在不相互干擾的情況下，對標準庫中的地Map 進行分片加鎖[9]，降低鎖粒度，更大限度地減少鎖定等待的時間（鎖沖突）。

筆者設計的ConCurrentMap 的數據結構如圖6 所示（基于Go1.18 以上版本，使用了泛型的寫法）。

ConcurrentMap 是一個切片，切片的每個元素都是攜帶了讀寫鎖的Map。關鍵方法GetShard 用于計算每一個key 應該分配到哪個分片上。

常用的讀寫方法都是先傳入key，調用GetShard（key） 計算出分片索引，然后找到對應的Map 塊，然后對這個塊進行加鎖，接著再執行讀寫操作，最后再釋放鎖。具體如圖7 所示。

3 實驗設計與結果分析

筆者設計兩組基準測試的實驗[10-11]，來衡量各種場景下每種Map 的性能。

（1）不同的讀寫比例，對這幾種Map進行基準測試，觀察其結果。（2）設置key 相同和不同的場景，對sync.Map和ConcurrentMap進行基準測試，觀察其結果。

3.1 實驗1 設計

不同的讀寫比例實驗設計：通過NumOfWriter 和NumOfReader 設置，啟動對應數量的協程。關鍵代碼如圖8 所示。

3.1.1 實驗1 的測試結果

實驗測試結果如表1 所示。

3.1.2 結果分析

只讀場景：sync. Mapgt;ConCurrentMapgt;rwmutexgt;gt;mutex。

讀寫場景（邊讀邊寫）：ConCurrentMapgt;gt;rwmutexgt;mutexgt;sync.Map。

讀寫場景（讀80% 寫20%）：ConCurrentMapgt;gt;rwmutex=sync.Mapgt;mutex。

讀寫場景（讀98% 寫2%）：ConCurrentMapgt;syncMapgt;gt;rwmutexgt;mutex。

只寫場景：ConCurrentMapgt;gt;mutexgt;rwmutexgt;sync.Map。

3.2 實驗2 設計

（1）根據sync.Map 的特性，選擇插入的key 為同一個key，關鍵代碼如圖9 所示。（2）插入不同的key，對ConCurrentMap 采取不同的分區（1、16、32、256），關鍵代碼如圖10 所示。

3.2.1 實驗2 的測試結果

（1）插入同一個key 值的結果具體見表2。（2）插入不同的key 不同分區的測試結果具體見表3。

3.2.2 結果分析

Sync.Map 在插入其他密鑰時性能似乎最差。如果ConCurrentMap中的分區數設置為1，則認為單個Map中添加了全局讀寫鎖定，速度比sync.Map 快。但是，sync.Map和分區為1的 ConCurrentMap在多次測試時差異較大，有時sync.Map 快，有時分區為1 的ConCurrentMap快，但都不會比分區為16以上的ConCurrentMap快。此外，分區數越大，速度越快，當分區數為256 時，執行速度開始減慢。

4 結語

關于MutexMap、RWMutexMap、sync.Map 以及分片ConCurrentMap 的選擇問題，除了看上述的測試結果外，還需要根據應用場合與實際情況來使用。

雖然sync.Map 返回的值都是interface{}類型具備通用性，但是在執行某些操作時卻必須不斷地去斷言，這樣可能會帶來性能問題。在這種情況下，如果性能要求不是特別高，則可以使用RWMutexMap 作為專用更換，從而消除斷言中的一些性能損失。

RWMutexMap 在并發量很大時，性能下降得非常快，所以如果存在高并發的場景可以選擇使用sync.Map。