揭祕 Go sync-Map 設計與實現

什麼是 sync.Map

我們都知道在 Go 語言中，普通的 Map 是非併發安全，併發讀寫時會 panic，sync.Map 則是官方庫提供的一種特殊的併發安全的映射類型，能保較高的性能的同時，還能保證併發安全。sync.Map 有以下幾個特點：

sync.Map 特點

併發安全： sync.Map 無需額外的鎖機制即可在多個 goroutine 中安全地進行讀寫操作。這對於高併發的應用場景非常重要，可以避免數據競爭和不一致的問題。

package main

import (
    "fmt"
    "sync"
)

func main() {
    // 創建一個 sync.Map
    var m sync.Map

    // 模擬多個 goroutine 同時讀寫
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            if id % 2 == 0 {
                 // 寫入,無需加鎖
                m.Store(id, fmt.Sprintf("value for %d", id))
            } else {
                // 讀取,無需加鎖
                value, ok := m.Load(id)
                if ok {
                    fmt.Printf("Goroutine %d read: %v\n", id, value)
                }
            }
        }(i)
    }

    wg.Wait()
}

讀寫分離: 內部採用了讀寫分離的設計，將頻繁訪問的元素存儲在一個只讀的部分，而將較少訪問的元素和新添加的元素存儲在一個可寫的部分。這種設計可以減少讀取操作時的鎖競爭，提高性能。

type Map struct {
    // ...
    
    // 負責讀，無需加鎖
    read atomic.Pointer[readOnly]

    // 負責寫，需要加鎖
    dirty map[any]*entry
    
    // ...
}

自動調整： 隨着時間的推移，sync.Map 會自動將可寫部分中頻繁訪問的元素提升到只讀部分，以進一步優化讀取性能。同時，當可寫部分的大小超過一定閾值時，會進行清理和合並操作。

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
       return
    }
    m.read.Store(&readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

功能豐富： sync.Map 提供了豐富的接口，包括存儲、讀取、刪除、遍歷等操作，方便開發者在不同的場景下使用。

type mapInterface interface {
    Load(any) (any, bool) // 讀取
    Store(key, value any) // 存儲
    LoadOrStore(key, value any) (actual any, loaded bool) // 讀取並存儲
    LoadAndDelete(key any) (value any, loaded bool) // 讀取並刪除
    Delete(any) // 刪除
    Swap(key, value any) (previous any, loaded bool) // 交換
    CompareAndSwap(key, old, new any) (swapped bool) // 比較並交換
    CompareAndDelete(key, old any) (deleted bool) // 比較並刪除
    Range(func(key, value any) (shouldContinue bool)) // 遍歷
}

應用示例

對 Map 有併發讀寫的需求的都可以考慮使用 sync.Map，我們在實際開發中通常使用 sync.Map 作爲緩存或者是動態配置，緩存和動態配置的特點都是讀多寫少，存在併發讀寫的場景，下面以緩存作爲示例：

package main

import (
    "fmt"
    "sync"
    "time"
)

func main() {
    cache := sync.Map{}

    // 模擬寫入緩存
    cache.Store("data_key", "initial value")

    // 讀取緩存
    value, ok := cache.Load("data_key")
    if ok {
        fmt.Println("Value from cache:", value)
    }

    // 模擬數據更新
    go func() {
        time.Sleep(2 * time.Second)
        cache.Store("data_key", "updated value")
    }()

    // 持續讀取緩存
    for {
        value, ok = cache.Load("data_key")
        if ok {
            fmt.Println("Current value:", value)
        }
        time.Sleep(1 * time.Second)
    }
}

sync.Map 的性能優勢

測試的代碼有點多，不關注測試代碼邏輯的可以跳過代碼直接閱讀 《性能小結》章節

原始的 Map 存在併發安全的問題，爲了避免併發安全我們通常使用：Map+Mutex、Map+Rwmutex、sync.Map 等方式去避免併發安全問題，其中 sync.Map 在大部分場景都具有性能優勢：

測試代碼封裝

const (
    baseKey = 128
)

type mapInterface interface {
    Load(any) (any, bool)
    Store(key, value any)
}

type MutexMap struct {
    mu    sync.Mutex
    dirty map[any]any
}

func (m *MutexMap) Load(key any) (value any, ok bool) {
    m.mu.Lock()
    value, ok = m.dirty[key]
    m.mu.Unlock()
    return
}

func (m *MutexMap) Store(key, value any) {
    m.mu.Lock()
    if m.dirty == nil {
       m.dirty = make(map[any]any)
    }
    m.dirty[key] = value
    m.mu.Unlock()
}

type RWMutexMap struct {
    mu    sync.RWMutex
    dirty map[any]any
}

func (m *RWMutexMap) Load(key any) (value any, ok bool) {
    m.mu.RLock()
    value, ok = m.dirty[key]
    m.mu.RUnlock()
    return
}

func (m *RWMutexMap) Store(key, value any) {
    m.mu.Lock()
    if m.dirty == nil {
       m.dirty = make(map[any]any)
    }
    m.dirty[key] = value
    m.mu.Unlock()
}

type SyncMap struct {
    dirty *sync.Map
}

func (m *SyncMap) Load(key any) (value any, ok bool) {
    value, ok = m.dirty.Load(key)
    return
}

func (m *SyncMap) Store(key, value any) {
    m.dirty.Store(key, value)
}

type bench struct {
    setup func(*testing.B, mapInterface)
    perG  func(b *testing.B, pb *testing.PB, i int, m mapInterface)
}

func benchMap(b *testing.B, bench bench) {
    for _, m := range [...]mapInterface{
       &MutexMap{dirty: make(map[any]any)},   // map+mutex
       &RWMutexMap{dirty: make(map[any]any)}, // map+rwmutex
       &SyncMap{dirty: &sync.Map{}},          // sync.Map
    } {
       b.Run(fmt.Sprintf("%T", m), func(b *testing.B) {
          if bench.setup != nil {
             bench.setup(b, m)
          }

          b.ResetTimer()

          var i int64
          b.RunParallel(func(pb *testing.PB) {
             id := int(atomic.AddInt64(&i, 1) - 1)
             bench.perG(b, pb, id*b.N, m)
          })
       })
    }
}

func benchRun(b *testing.B, reads, writes int) {
    benchMap(b, bench{
       setup: func(_ *testing.B, m mapInterface) {
          for i := 0; i < reads; i++ {
             m.Store(i, i)
          }
          // Prime the map to get it into a steady state.
          for i := 0; i < reads; i++ {
             m.Load(i)
          }
       },

       perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
          r := rand.New(rand.NewSource(time.Now().Unix()))
          for pb.Next() {
             j := r.Intn(reads + writes)

             if j < reads {
                m.Load(j)
             } else {
                m.Store(j, j)
             }
          }
       },
    })
}

讀多寫少

func BenchmarkLoadMostlyRead(b *testing.B) {
    var reads, writes = baseKey << 3, baseKey
    
    benchRun(b, reads, writes)
}

>>> go test -bench=. -benchmem
goos: darwin
goarch: arm64
pkg: sync_map
cpu: Apple M3 Pro
BenchmarkLoadMostlyRead sync_map.MutexMap-12           11812083               102.1 ns/op             7 B/op          0 allocs/op
BenchmarkLoadMostlyRead sync_map.RWMutexMap-12         15006846                79.00 ns/op            7 B/op          0 allocs/op
BenchmarkLoadMostlyRead sync_map.SyncMap-12            50878357                22.54 ns/op            8 B/op          1 allocs/op
PASS
ok      sync_map        5.415s

讀少寫多

func BenchmarkLoadMostlyRead(b *testing.B) {
    var reads, writes = baseKey, baseKey << 3
    
    benchRun(b, reads, writes)
}

>>> go test -bench=. -benchmem
goos: darwin
goarch: arm64
pkg: sync_map
cpu: Apple M3 Pro
BenchmarkLoadMostlyWrite sync_map.MutexMap-12           8027871               141.2 ns/op            12 B/op          1 allocs/op
BenchmarkLoadMostlyWrite sync_map.RWMutexMap-12         7322696               163.1 ns/op            12 B/op          1 allocs/op
BenchmarkLoadMostlyWrite sync_map.SyncMap-12            7920776               151.8 ns/op            26 B/op          2 allocs/op
PASS
ok      sync_map        4.661s

讀寫均衡

func BenchmarkLoadMostlyRead(b *testing.B) {
    var reads, writes = baseKey << 2, baseKey << 2
    
    benchRun(b, reads, writes)
}

>>> go test -bench=. -benchmem
goos: darwin
goarch: arm64
pkg: sync_map
cpu: Apple M3 Pro
BenchmarkReadWriteBalanced sync_map.MutexMap-12                 8909396               120.4 ns/op            10 B/op          1 allocs/op
BenchmarkReadWriteBalanced sync_map.RWMutexMap-12              12947712                94.64 ns/op           10 B/op          1 allocs/op
BenchmarkReadWriteBalanced sync_map.SyncMap-12                 12849976                86.18 ns/op           18 B/op          1 allocs/op
PASS
ok      sync_map        4.397s

性能小結

這裏的寫指的是新增 key，並不是更新，如果是更新 sync.Map 的性能還能提升一倍以上，因爲 sync.Map 對 value 的更新原理是 Load + 原子操作。

a8lBJl

實現原理

基於 Go 1.23

數據結構

整體結構

type Map struct {
    // 互斥鎖，當對 dirty 進行讀寫時需要加鎖
    mu Mutex
    
    // 原子類型，底層指向 readOnly，是隻讀 map 的載體, 讀取時先讀只讀 map
    // 實際上更新和刪除也會在這個上操作，只有新增的 key 會在 dirty 裏操作
    read atomic.Pointer[readOnly]

    // 新增的 key 會先寫到這個裏面，等到一定時機 read 和 dirty 會相互同步
    dirty map[any]*entry

    // 因爲新增的 key 會先寫入 dirty 中，導致某些 key 在 read 中找不到，misses 記錄
    // 找不到的次數，達到一定數值後 dirty 就會向 read 中同步
    misses int
}

// read 字段真正指向的類型
type readOnly struct {
    // 底層的只讀 map，只讀不需要加鎖
    m       map[any]*entry 
    
    // 如果 dirty 中有 read 裏沒有 key 時 amended 爲 true
    amended bool
}

// map 的 value, 裏面的 p 是原子類型，對於 value 的讀取、更新、刪除 直接使用原子操作就可以不用加鎖
// 如果一個 key 在 read 和 dirty 裏面都存在，那麼read 和 dirty 底層複用同一個 entry
type entry struct {
    p atomic.Pointer[any]
}

sync.Map 的整體結構如下：

設計技巧

有一些設計技巧在這裏簡單介紹一下，下面進行源碼解析時也會詳細講解：

1. sync.Map 採用了讀寫分離的設計，大多數 key 在 read 中不用加鎖讀取，只有少數的 key 需要加鎖對 dirty 進行讀寫；

2. read 字段是原子類型而非直接聲明成 readOnly，是因爲 readOnly 裏面有兩個字段如果在不加鎖的情況分別對 m 和  amended 進行賦值時不能保證原子性，m 和 amended 的狀態可能是不一致的，把 m 和  amended 看成一個整體，然後使用原子操作對 read 賦值，這樣可以保證原子性。

m.read.Store(&readOnly{m: read.m, amended: true})

3. 相同的 key 在 read 和 dirty 中共用一個 entry ，這樣設計的目的是能保證 read 和 dirty 對應的 value 是相同的，避免數據不一致的問題，例如：更新了 read 中的 value 後就不需要再更新 dirty 中的 value。

4. entry 中的 p 也是原子類型，這樣設計的好處是，read 中 value 可以在不加鎖的情況進行讀取、更新、刪除，如果不是原子類型，那麼 read 中 value 只能進行讀取，更新和刪除需要加鎖。

// 讀取
p := e.p.Load()

// 更新
e.p.CompareAndSwap(p, i)

// 刪除，在 sync.Map 中刪除是特殊的更新，更新後的值爲 nil
e.p.CompareAndSwap(p, nil)

5. P 有三種狀態分別是：any、nil、expunged, 他們之間可以進行轉換，這樣設計的目的是刪除時可以不用加鎖先在 read 中刪除，如果 read 中沒有再加鎖在 dirty 中刪除：

• 正常情況 p 會指向一個 any 類型的值，在刪除時 p 會指向 nil，實際並沒有刪除；

• 當 read 向 dirty 向轉換時（dirty 爲 nil 並且需要向 dirty 寫入新值時），read 中被刪除的 p 會從 nil 轉換成 expunged，但是不會複製到 dirty 中；

• 被刪除的 key 重新寫入時，nil 和 expunged 有不同的邏輯：

讀取操作

func (m *Map) Load(key any) (value any, ok bool) {
    // 通過原子操作獲取 read 
    read := m.loadReadOnly()
    e, ok := read.m[key]
    if !ok && read.amended {
       // 加鎖  
       m.mu.Lock()
      
       // 再次檢查 read 中是否存在
       read = m.loadReadOnly()
       e, ok = read.m[key]
       if !ok && read.amended {
          // 如果 read 中不存在，再檢查 dirty 中是否存在
          e, ok = m.dirty[key]
         
          m.missLocked()
       }
       m.mu.Unlock()
    }
    if !ok {
       return nil, false
    }
    return e.load()
}

1. 通過原子操作獲取 read ，檢查 key 在 read 中是否存在，如果不存在則需要加鎖然後在 dirty 中檢查；

2. 如果 read 中不存在，首先加鎖，然後再次檢查 key 在 read 中是否存在，如果不存在再檢查 dirty 裏面是否存在，同時還需要檢查是否需要使用 dirty 覆蓋 read；

3. 如果 read 和 dirty 中都不存在，返回 nil, false；

4. 如果存在則使用原子操作，返回 p 指向的值。

因爲新增的 key 會先寫入 dirty 中，導致某些 key 在 read 中找不到， sync.Map 的 misses 字段記錄了在 read 中找不到的次數，達到一定數值後 dirty 就會向 read 中同步，missLocked() 就是對應的同步邏輯， missLocked 需要在加鎖時使用：

func (m *Map) missLocked() {
    m.misses++
    
    // 開始同步的閾值 len(m.dirty)
    if m.misses < len(m.dirty) {
       return
    }
    
    // 使用原子操作更新 read 
    m.read.Store(&readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

寫入操作

func (m *Map) Store(key, value any) {
    _, _ = m.Swap(key, value)
}

func (m *Map) Swap(key, value any) (previous any, loaded bool) {
    // key 是否在 read 中存在
    read := m.loadReadOnly()
    if e, ok := read.m[key]; ok {
       // 如果存在則進行嘗試交換
       if v, ok := e.trySwap(&value); ok {
          if v == nil {
             return nil, false
          }
          return *v, true
       }
    }

    // 如果不存在則加鎖進行進一步的處理
    m.mu.Lock()
    
    // 再次檢查 read
    read = m.loadReadOnly()
    if e, ok := read.m[key]; ok {
       // 如果是 read 中存在且 p 的狀態是 expunged, 則需先把 expunged 轉換成 nil
       // 然後在 dirty 新增相應的 k-v
       if e.unexpungeLocked() {
          // The entry was previously expunged, which implies that there is a
          // non-nil dirty map and this entry is not in it.
          m.dirty[key] = e
       }
       
       // 將新的值與舊的值進行交換
       if v := e.swapLocked(&value); v != nil {
          loaded = true
          previous = *v
       }
    } else if e, ok := m.dirty[key]; ok {
       // 如果 read 中不存在且 dirty 中存在，則將新的值與舊的值進行交換
       if v := e.swapLocked(&value); v != nil {
          loaded = true
          previous = *v
       }
    } else {
       // 如果 read 和 dirty 中都不存在
       if !read.amended {
          // 如果 dirty 爲 nil 時需要初始化 dirty
          m.dirtyLocked()
          // 設置 amended 爲true，因爲新寫入 key 在 dirty 中，所以 amended 必然爲 true
          m.read.Store(&readOnly{m: read.m, amended: true})
       }
       
       // 在 dirty 中寫入新值
       m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
    return previous, loaded
}

Store 底層調用的是 Swap 方法，直接看 Swap 的具體實現：

1. key 是否在 read 中存在，且 p 狀態不是 expunged 則進行新舊值交換，交換成功則返回；

2. 如果上一步交換失敗或者 read 中不存在，需要加鎖，然後進行進一步判斷 read 和 dirty 是否存在；

3. 如果是 read 中存在且 p 的狀態是 expunged, 則需先把 expunged 轉換成 nil 然後在 dirty 新增相應的 k-v，然後再將新的值與舊的值進行交換；

4. 如果 read 中不存在且 dirty 中存在，直接將新的值與舊的值進行交換；

5. 如果 read 和 dirty 中都不存在，如果 dirty 爲 nil 時需要初始化 dirty 並且標記 amended 爲 true，然後在 dirty 中寫入新值。

寫入新值時如果 dirty 爲 nil 時需要重新初始化，初始化的過程是從 read 中找到未被刪除的 key 複製到 dirty 中，該過程需要加鎖完成。

func (m *Map) dirtyLocked() {
    if m.dirty != nil {
       return
    }

    read := m.loadReadOnly()
    m.dirty = make(map[any]*entry, len(read.m))
    for k, e := range read.m {
       if !e.tryExpungeLocked() {
          m.dirty[k] = e
       }
    }
}

調用完 dirtyLocked() 後效果：

刪除操作

func (m *Map) Delete(key any) {
    m.LoadAndDelete(key)
}

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    read := m.loadReadOnly()
    e, ok := read.m[key]
    if !ok && read.amended {
       m.mu.Lock()
       read = m.loadReadOnly()
       e, ok = read.m[key]
       if !ok && read.amended {
          e, ok = m.dirty[key]
          delete(m.dirty, key)
          // Regardless of whether the entry was present, record a miss: this key
          // will take the slow path until the dirty map is promoted to the read
          // map.
          m.missLocked()
       }
       m.mu.Unlock()
    }
    if ok {
       return e.delete()
    }
    return nil, false
}

func (e *entry) delete() (value any, ok bool) {
    for {
       p := e.p.Load()
       
       // nil 或者 expunged 說明已經被刪除了
       if p == nil || p == expunged {
          return nil, false
       }
       
       // 把 p 的值替換成 nil
       if e.p.CompareAndSwap(p, nil) {
          return *p, true
       }
    }
}

Delete 的底層是 LoadAndDelete ，LoadAndDelete 關鍵邏輯如下：

1. 先在 read 中查找對應的 key ，如果沒找到再到 dirty 裏面查找；

2. 在 dirty 裏查找前需要先加鎖，查找同時會判斷是否需要將 dirty 同步到 read 中（m.misses > len(m.dirty)）；

3. 經過上面的查找，如果查找到則調用 e.delete() 進行刪除，實際是將 p 替換成 nil；

遍歷操作

func (m *Map) Range(f func(key, value any) bool) {
    read := m.loadReadOnly()
    if read.amended {
       m.mu.Lock()
       read = m.loadReadOnly()
       if read.amended {
          read = readOnly{m: m.dirty}
          copyRead := read
          m.read.Store(©Read)
          m.dirty = nil
          m.misses = 0
       }
       m.mu.Unlock()
    }

    for k, e := range read.m {
       v, ok := e.load()
       if !ok {
          continue
       }
       if !f(k, v) {
          break
       }
    }
}

1. 如果 read 的數據並不完全（read.amended == true ）則使用 dirty 的內容覆蓋 read；

2. 遍歷 read，將 k-v 傳給回調函數，回調函數出錯則終止遍歷。

總結

主要流程

1. 添加 key：如果是第一次寫入 key 的話（假設其值爲 value），會先寫入 dirty map，在 dirty map 中的 value 是一個指向 entry 結構體的指針。entry 結構體中的 p 字段也是一個指針，它指向了 value 的內存地址。

2. 讀取 key：先從 read 中讀取（無鎖，原子操作），read 中找不到的時候再去 dirty 中查找（有鎖）。

3. 修改 key：如果 key 在 read map 中存在的話，會直接修改 key 對應的 value。如果 key 在 read map 中不存在的話，會去 dirty map 中查找（有鎖），如果在 dirty map 中也不存在的話則會在 dirty 新增一個 key 。

4. 刪除 key：如果 key 在 read map 中存在的話，會將 key 對應的 entry 指針設置爲 nil（實際上是打標記而已，並沒有刪除底層 map 的 key）。如果在 read 中找不到，並且 dirty 有部分 read 中不存在的 key 的話，會去 dirty map 中查找（有鎖），如果在 dirty map 中也不存在的話，則刪除失敗。

性能對比

在讀多寫少、讀寫均衡的場景，sync.Map 的性能都具有一定優勢：

1xigdx

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