關(guān)鍵詞： Golang 并發(fā)安全 sync.Map 分片加鎖實現(xiàn) 實驗設(shè)計 技術(shù)選型

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

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

1 Map 設(shè)計與并發(fā)不安全性

1.1 標(biāo)準(zhǔn)庫中Map 的設(shè)計

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

Map 的核心數(shù)據(jù)結(jié)構(gòu)位于runtime/map.go，如圖1所示，主要包括hmap、mapextra 和bmap 這3 個結(jié)構(gòu)體。

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

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

大致步驟具體如下。

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

（2）判斷是否處于并發(fā)讀寫狀態(tài)，如果是則產(chǎn)生panic。

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

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

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

（6）然后使用HASH_VALUE的高8位，以10010001為例，它對應(yīng)的10進(jìn)制數(shù)是145。

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

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

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

1.2 并發(fā)不安全性

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

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

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

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

2 Map 的改進(jìn)及優(yōu)化

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

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

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

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

2.1 MutexMap

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

2.2 RWMutexMap

Mutex Map 的實現(xiàn)可以提供線程安全映射，但由于互斥鎖的功能，如果并發(fā)讀寫數(shù)較多，則鎖的競爭非常激烈。特別是在并發(fā)讀取較多的場景中，互斥鎖會嚴(yán)重影響讀取性能?？梢詤⒖糝WMutex 對Mutex 的優(yōu)化方式，使用讀寫鎖定代替Mutex 進(jìn)行優(yōu)化。

2.3 sync.Map

除了使用鎖定來控制讀取和寫入外，Go 1.9 版本的標(biāo)準(zhǔn)庫還包含與線程安全相關(guān)的數(shù)據(jù)結(jié)構(gòu)sync.Map。sync.Map 對RWMutexMap 進(jìn)行了一些優(yōu)化，具體敘述如下。

（1）空間換時間。使用兩個冗余數(shù)據(jù)結(jié)構(gòu)（只讀字段read、可寫字段dirty）減少鎖定功能對性能的影響。

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

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

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

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

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

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

2.4 通過分片加鎖實現(xiàn)

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

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

筆者設(shè)計的ConCurrentMap 的數(shù)據(jù)結(jié)構(gòu)如圖6 所示（基于Go1.18 以上版本，使用了泛型的寫法）。

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

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

3 實驗設(shè)計與結(jié)果分析

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

（1）不同的讀寫比例，對這幾種Map進(jìn)行基準(zhǔn)測試，觀察其結(jié)果。（2）設(shè)置key 相同和不同的場景，對sync.Map和ConcurrentMap進(jìn)行基準(zhǔn)測試，觀察其結(jié)果。

3.1 實驗1 設(shè)計

不同的讀寫比例實驗設(shè)計：通過NumOfWriter 和NumOfReader 設(shè)置，啟動對應(yīng)數(shù)量的協(xié)程。關(guān)鍵代碼如圖8 所示。

3.1.1 實驗1 的測試結(jié)果

實驗測試結(jié)果如表1 所示。

3.1.2 結(jié)果分析

只讀場景：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 設(shè)計

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

3.2.1 實驗2 的測試結(jié)果

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

3.2.2 結(jié)果分析

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

4 結(jié)語

關(guān)于MutexMap、RWMutexMap、sync.Map 以及分片ConCurrentMap 的選擇問題，除了看上述的測試結(jié)果外，還需要根據(jù)應(yīng)用場合與實際情況來使用。

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

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