Go map 讀寫性能優化 - 分片 map

基本在所有的編程語言中，都有 map 這種數據結構，Go 語言也不例外。我們知道 Go 是一門對併發支持得比較好的語言，但是 map 並不支持併發讀寫。比如，下面這種寫法是錯誤的：

var m = make(map[int]int)
var wg sync.WaitGroup
wg.Add(2)
// 啓動兩個協程序同時寫入 map
go func() {
    for i := 0; i < 100; i++ {
        m[i] = i
    }
    wg.Done()
}()
go func() {
    for i := 0; i < 100; i++ {
        m[i] = i
    }
    wg.Done()
}()
wg.Wait()

這樣寫會報錯：

fatal error: concurrent map writes

爲什麼 Go map 不支持併發讀寫

這跟 map 的實現有關，根本原因是：map 的底層是支持自動擴容的，在添加元素的時候，如果發現容量不夠，就會自動擴容。如果允許擴容和訪問操作同時發生，那麼訪問到的數據就不一定就是我們之前存放進去的了，所以 Go 從設計上就禁止了這種操作。也就是 fail fast 的原則。

至於具體爲什麼，我們可以看看 map 在擴容時做了什麼操作：

上圖來源於我之前寫的一篇文章：go map 設計與實現

Go 中 map 的擴容是一個漸進的過程，在我們訪問 map 的時候，會對 map 底層實際存儲數據的桶進行遷移。

如果支持併發讀寫，就有可能會導致底層定位到的桶是擴容前的，但是實際上數據已經遷移到了新的桶中，這樣就會導致訪問到的並不是我們想要的數據。

Go map 設計上的考慮

在 Go 官網的博客上有專門針對 Go 不支持併發讀寫的說明，大概意思是：

經過長時間討論，Go 團隊認爲，多數情況下，我們並不需要從多個 goroutine 來對 map 進行安全訪問，map 可能是已經實現了同步的某些較大數據結構或計算的一部分。因此，如果底層再去實現 map 的互斥操作， 就會減慢大多數程序的速度，而只能增加少數程序的安全性。

也就是說，他們認爲大多數情況下，map 通常是我們自定義數據結構的一部分，而對這個自定義數據結構的訪問時，我們一般已經有了鎖去保證併發讀寫安全了，所以沒有必要再在底層的 map 上加鎖，從而可以保證大多數程序的速度。

但是從語言層面上來說，我們依然可以自行通過互斥鎖來實現 map 的的互斥訪問。僅當對 map 在進行更新的時候，map 的讀纔是不安全的，但是 map 是支持併發讀的。

如何解決這個問題 - 互斥鎖

關於這一點，同樣可以在 Go 官方博客中找到相關的說明，在 Go map 併發這一節也給了對應的 demo。具體來說就是將一般鎖跟 map 關聯起來，要讀寫 map 的時候，得先獲取這個鎖才能訪問，這樣就避免了對 map 的併發讀寫了。這是最典型的一種解決方案，也是最簡單的。

下面的結構體定義了一個匿名結構體 counter，這個結構體中包含了一個 sync.RWMutex 互斥鎖和一個 map：

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

讀的時候，我們可以使用 RLock 獲取讀鎖，然後訪問 m 這個 map：

counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)

RLock 是讀鎖，多個 goroutine 可以同時獲取讀鎖，讀鎖釋放之前，其他 goroutine 無法獲取寫鎖。

寫的時候，我們可以使用 Lock 獲取寫鎖：

counter.Lock()
counter.m["some_key"]++
counter.Unlock()

Lock 是寫鎖，只有一個 goroutine 可以獲取寫鎖，並且寫鎖釋放之前，其他 goroutine 無法獲取讀鎖，也無法獲取寫鎖。

另一種解決方法 - sync.Map

除了使用互斥鎖，我們也可以使用 Go 語言自帶的 sync.Map 來解決這個問題：

var m sync.Map
var wg sync.WaitGroup
wg.Add(2)
go func() {
    for i := 0; i < 100; i++ {
        m.Store(i, i)
    }
    wg.Done()
}()
go func() {
    for i := 0; i < 100; i++ {
        m.Store(i, i)
    }
    wg.Done()
}()
wg.Wait()

雖然 sync.Map 可以實現併發的讀寫，但是底層上依然會有較多的競態條件，所以性能上並不是最好的，本質上還是操作一個 map， 只是通過一些原子操作 + 自旋鎖來實現併發安全的讀寫。

而且 sync.Map 設計出來的時候是爲了應對一些特定的場景的，具體來說有以下兩個場景：

  1. 當給定 key 的條目只寫入一次但讀取多次時，如在只會增長的緩存中。（讀多寫少）

  2. 當多個 goroutine 讀取、寫入和覆蓋不相交的鍵集的條目。（不同 goroutine 操作不同的 key）

在這兩種情況下，可以獲得比用 Mutex + map 或 RWMutex + map 更好的性能，因爲很多的鎖操作都變成了原子操作。

具體細節可參考我此前的一篇文章：深入理解 go sync.Map - 基本原理

互斥鎖、sync.Map 還不是最優的解決方案

使用互斥鎖或者 sync.Map 的方式，雖然都可以解決 map 併發讀寫的問題，但是性能上都不是最優的。

因爲它們底層還是會有互斥鎖的競爭。這就意味着，在進行寫 map 操作時，可能會存在較多的鎖競爭，從而導致性能下降。

map 分片

如果我們有了解過 MongoDB，就會知道，MongoDB 中也有分片的概念，當數據量過大時， 單個 MongoDB 實例可能無法存儲所有的數據，或者單個實例無法處理過多的讀寫請求， 這時候就需要將數據分片存儲到多個 MongoDB 實例中，也就是按照一定的規則將數據存儲到不同的機器上， 然後讀寫數據的請求也會依據一定規則被路由到對應的機器上。

同樣的，如果我們的 map 併發請求過多，那麼我們也可以將 map 分片， 將不同的 key 存儲到不同的 map 中，這樣就可以避免 map 的併發讀寫了。

我們需要做的是：通過 key 來計算其 hash 值，然後根據 hash 值來決定將 key 存儲到哪個 map 中， 同時，我們每一個 map 都需要加上互斥鎖，這樣就可以保證每一個 map 的併發安全了。

具體如下圖：

說明：

  1. 圖中的 G0~2 表示 goroutine，lock0~2 表示不同的互斥鎖，map shard 0~2 表示多個 map 分片。

  2. goroutine 中會根據 key 計算出 hash 值，然後根據 hash 值來決定將 key 存儲到哪個 map 分片中，然後獲取這個分片對應的鎖，然後進行讀寫操作。

雖然上圖畫起來是 G1 不會訪問到 shard 0 或者 shard 2，但實際上是有可能的，上圖只是想說明：多個 goroutine 可以多個鎖來訪問多個 map 分片，而不用像之前那樣多個 goroutine 都來競爭同一把鎖了。也就減少了鎖的競爭和等待。

代碼實現

具體實現已經有一個開源的庫了：orcaman/concurrent-map， 可以在 github 上搜到。

下面是它的部分代碼：

var SHARD_COUNT = 32


// A "thread" safe map of type string:Anything.
// To avoid lock bottlenecks this map is dived to several (SHARD_COUNT) map shards.
type ConcurrentMap[K comparable, V any] struct {
 shards   []*ConcurrentMapShared[K, V]
 sharding func(key K) uint32
}

// A "thread" safe string to anything map.
type ConcurrentMapShared[K comparable, V any] struct {
 items        map[K]V
 sync.RWMutex // Read Write mutex, guards access to internal map.
}

// GetShard returns shard under given key
func (m ConcurrentMap[K, V]) GetShard(key K) *ConcurrentMapShared[K, V] {
 return m.shards[uint(m.sharding(key))%uint(SHARD_COUNT)]
}

說明：

  1. SHARD_COUNT 是分片數量，也就是底層會有多少個 map 分片。

  2. ConcurrentMap 表示一個支持併發讀寫的 map，它底層包含了多個 map 分片，以及有一個根據 key 計算分片的函數。

  3. ConcurrentMapShared 表示一個 map 分片，也就是上面提到的 map + RWMutex 組合。

  4. GetShard 根據 key 獲取對應的 map 分片。

單從代碼的角度，它封裝了更多的東西，性能相比單純的 map + RWMutex 自然會差一點， 但是從併發讀寫的角度來說，它比單純 map + RWutex 要好很多。因爲它將原本只支持一個協程寫的 map 轉換爲了支持多個協程寫操作的 map，一定程度上提高了併發

但是需要注意的是，我們需要頻繁寫同一個 key 的操作，上面這種分片的方式也不能帶來性能上的提升。分片的方式更適合那些 key 區分度高的、寫操作頻繁的場景。

總結

最後再簡單回顧一下本文所講內容：

  1. Go 的 map 設計上不支持併發讀寫，如果我們有併發讀寫操作會直接 panic。

  2. Go 的設計者們認爲，多數情況下，我們並不需要從多個 goroutine 來對 map 進行安全訪問，所以他們沒有在底層實現 map 的互斥操作。

  3. 有兩種方法可以解決 map 併發讀寫的問題：互斥鎖、sync.Map。但是 sync.Map 設計上是應對某些特定場景的，並不合適所有場景。

  4. 我們可以通過分片的方式來解決 map 併發讀寫的問題，這樣可以減少鎖的競爭，提高併發讀寫性能。目前已經有現成的開源庫可以使用了。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/4ZHyTtoyz8TT0ljvjIKd4Q

猜你喜歡