concurrent-map 和 sync.Map，我該選擇哪個？

官方的map並不是執行緒安全的，如果我們在多執行緒中並行對一個map進行讀寫操作，是會引發panic的。解決方案除了使用鎖來對map進行保護外，還有兩種方式：

一，開源專案 concurrent-map 提供了可以用來做並行安全的map

二，Go1.9之後，標準庫提供了一個sync.Map

這兩種並行安全的map，我們應該怎麼選擇呢？

在concurrent-map我看到這麼一段話：

標準庫中的sync.Map是專為append-only場景設計的。因此，如果您想將Map用於一個類似記憶體資料庫，那麼使用我們的版本可能會受益。你可以在golang repo上讀到更多，這裡 and 這裡譯註:sync.Map在讀多寫少效能比較好，否則並行效能很差

concurrent-map為什麼會有這種表述呢？這篇文章就來庖丁解牛下。

concurrent-map

concurrent-map是Golang中一個流行的並行安全的雜湊表庫，它允許多個goroutine同時對雜湊表進行讀寫操作，而不需要使用顯式的鎖或同步原語。

該庫的核心原理是使用分片鎖，將雜湊表分成多個小的雜湊表片段，併為每個片段分配一個獨立的鎖。當多個goroutine嘗試同時讀寫同一個片段時，只有該片段上的鎖會被鎖住，而其他片段的鎖則不受影響，從而避免了整個雜湊表被鎖住的情況。

當進行寫操作時，只需要鎖住要寫入的片段的鎖，以確保原子性操作。當進行讀操作時，則不需要鎖住片段的鎖，只需要對該片段上的讀取操作進行同步即可。

此外，concurrent-map庫還使用了一些優化策略，如快取雜湊值和桶的地址，以減少計算和查詢時間，從而提高並行讀寫效能。

總之，concurrent-map庫的原理是基於分片鎖和其他優化策略來實現高效的並行安全雜湊表。

我們先看它的使用方式：

	// 建立一個新的 map.
	m := cmap.New[string]()

	// 設定變數m一個鍵為「foo」值為「bar」鍵值對
	m.Set("foo", "bar")

	// 從m中獲取指定鍵值.
	bar, ok := m.Get("foo")

	// 刪除鍵為「foo」的項
	m.Remove("foo")

它的New方法建立了一個ConcurrentMap結構

type ConcurrentMap[K comparable, V any] struct {
	shards   []*ConcurrentMapShared[K, V]
	sharding func(key K) uint32
}

我們看ConcurrentMap結構中的shards，是用來代表map分片之後的這些儲存分片ConcurrentMapShared。

而sharing這個匿名函數代表的是分配的hash函數。

而儲存分片是一個基礎的，帶有互斥鎖的map

type ConcurrentMapShared[K comparable, V any] struct {
   items        map[K]V
   sync.RWMutex 
}

所以看到這裡我們其實心裡明白了個七七八八了，再看下它的New/Set/Get的流程如下：

flowchart LR cmap.New --> 建立一個ConcurrentMap --> 初始化ConcurrentMapShared cmap.Set --> 根據需要設定的key查詢對應的ConcurrentMapShared --> 加鎖寫分片中的map cmap.Get --> 根據需要查詢的key找出對應分片ConcurrentMapShared --> 加讀鎖讀取分片中的map

是的，基本原理就是如上圖所示。concurrent-map就是將一個大map拆分成若干個小map，然後用若干個小mutex 對這些小map進行保護。這樣，通過降低鎖的粒度提升並行程度。畢竟嘛，一個諸葛亮不如十個臭皮匠。

sync.Map

sync.Map是Golang標準庫中提供的一個並行安全的雜湊表，它與常規的map相比，可以在多個goroutine並行存取時，保證資料的安全性和一致性。

理解sync.Map，最關鍵就是理解Map結構。

type Map struct {
	mu Mutex //互斥鎖，用於鎖定dirty map

	//優先讀map,支援原子操作，註釋中有readOnly不是說read是唯讀，而是它的結構體。read實際上有寫的操作
	read atomic.Value // readOnly

	// dirty是一個當前最新的map，允許讀寫
	dirty map[any]*entry

	// 主要記錄read讀取不到資料加鎖讀取read map以及dirty map的次數，當misses等於dirty的長度時，會將dirty複製到read
	misses int
}

這裡的sync.Map的邏輯還是比較複雜的。我們再看它的Store函數和Load函數。

func (m *Map) Store(key, value any) 
func (m *Map) Load(key any) (value any, ok bool)

我們先把Store的程式碼流程圖畫出來

flowchart TD Store-->判斷read中是否有key{判斷read中是否有key} 判斷read中是否有key{判斷read中是否有key}--有key-->在read中tryStore-->CompareAndSwapPointer-->原子替換read中對應指標判斷read中是否有key{判斷read中是否有key}--沒有key-->加鎖-->判斷key的位置判斷key的位置--在read中存在-->dirty中存入這對keyvalue-->read中原子替換指標-->解鎖判斷key的位置--在read中不存在\n在dirty中存在-->dirty中原子替換指標-->解鎖判斷key的位置--在read中不存在\n在dirty中不存在-->read中所有元素複製到dirty一份-->read中增加這個keyvalue-->dirty中增加這個keyvalue-->解鎖

我們看下，這裡面有幾個步驟是非常有細節的。

首先，第一次判斷read中是否有key的時候是沒有加鎖的，所以當第一次判斷結束後，一旦明確read中沒有key，要做後續的操作之前，先做一次加鎖操作，做完加鎖操作之後，又判斷了一次key是否在read中。這是為什麼呢？其實是由於在加鎖這個操作的前後，map還是有可能有變化的，人不可能兩次踏入同一個河流，map也不可能在加鎖前後兩次都不變，所以這裡必須進行二次判斷，這裡可以說是非常細節了。

其次，在判斷read或者dirty中已經有key的時候，Store做的操作不是複製一份value到目標結構，而是使用原子替換atomic.StorePointer 來將目標map中key對應的value指標替換為引數value。為什麼呢？ - 這是極致的效能優化寫法，原子替換能減少一次值拷貝操作，做一次指標賦值就能替換拷貝記憶體操作。從這裡我們也能理解為什麼這個並行map會放在atomic包中，因為它的實現大量依賴atomic的原子操作。

同樣，我們將Load的程式碼轉化為流程圖如下，

flowchart TD Load --> 判斷read中是否有key{判斷read中是否有key} 判斷read中是否有key{判斷read中是否有key}--有key-->直接返回對應的value 判斷read中是否有key{判斷read中是否有key}--沒有key-->加鎖-->再次判斷read中是否有key{再次判斷read中是否有key} 再次判斷read中是否有key{再次判斷read中是否有key} --有key-->直接返回對應的value 再次判斷read中是否有key{再次判斷read中是否有key} --沒有key-->返回dirty中是否有key-->標記map的miss值加一-->如果miss值大於dirty的個數-->將dirty中的map通過指標切換到read-->dirty置空-->標記map的miss值為0

從Load中我們大致能看出sync.Map的思路。

sync.Map內部使用兩個map，read和dirty。其實read的map的作用是擋在讀寫操作的第一個屏障。如果讀寫在這個read中能直接操作的話，我們就直接在read中讀寫，那麼就可以完全避免使用鎖，效能自然就提升了。

而dirty的作用就相當於是一個緩衝區，一旦要寫的key在read中找不到，我們就會先寫dirty中。這個好處是什麼？也是不去影響讀read的操作，不會出現並行讀寫一個資料結構的情況。

而什麼時候dirty的快取清空同步到read中呢？就是「當map的miss標記大於dirty的個數的時候」。

這裡我讀的時候也確實有這個疑問，為什麼是「當miss標記個數大於dirty個數」。而不是當miss標記個數大於某個值呢？我是這麼理解，miss是代表讀操作在read中失效的數量，而dirty個數代表寫操作在read中失效的數量。如果使用固定值來比對miss個數，那麼這個固定值是不好定的，比如一個有10個key的map和一個有10000個key的map如果都是一樣的固定值，那是明顯不合適的。所以就找了這麼個「浮動閾值」。

concurrent-map和sync.map的比較

我們再回到最開始的那一段話：

標準庫中的sync.Map是專為append-only場景設計的。因此，如果您想將Map用於一個類似記憶體資料庫，那麼使用我們的版本可能會受益。你可以在golang repo上讀到更多，這裡 and 這裡譯註:sync.Map在讀多寫少效能比較好，否則並行效能很差

通過以上的程式碼分析，我們看出sync.Map的這個機制，是一個想追求無鎖讀寫的結構，它最好的執行方式是讀永遠都命中read，寫只命中dirty，這用能不用任何鎖機制就能做到map讀寫。而它最差的執行狀態是read和dirty不斷做替換和清理動作，效能就無法達到預期。而什麼時候可能出現最差執行狀態呢？- 大量的寫操作和大量的讀操作。大量讀寫會導致「map的miss標記大於dirty的個數」。這個時候sync.Map中第一層屏障會失效，dirty就會頻繁變動。

而current-map就相當於是一個比較中等中規中矩的方案。它的每次讀寫都會用到鎖，只是這個鎖的粒度比較小。它的最優執行方式是我們的所有並行讀寫都是分散在不同的hash切片中。它的最差執行方式就是我們所有的並行讀寫都集中在一個hash切片。但是按照實際執行邏輯，這兩種極端情況都不會發生。

所以總結下來，concurrent-map 的這段話確實沒有騙我們：

sync.Map在讀多寫少效能比較好，而concurrent-map 在key的hash度高的情況下效能比較好。

在無法確定讀寫比的情況下，建議使用 concurrent-map。

最後說一句：世上本沒有煩惱，選擇多了，便有了幸福的煩惱。

參考

https://segmentfault.com/a/1190000015242373