圖解 sync-Map

前面的兩篇文章《2 萬字圖解 map》，《從應用層面細說 map》從原理層面和應用層面分別介紹了內建 map 是如何實現的、如何使用，以及使用過程中需要注意的地方。本篇文章將介紹 sync.Map 的使用和實現分析，通過圖解的方式分析 p 的狀態，爲什麼有 expunged 狀態的存在。建議結合前兩篇文章一起閱讀，能夠更深入的理解 map。

sync.Map 是什麼

Go 內建的 map 類型不是線程安全的，sync.Map 是 Go1.9 中新增加的一個線程安全的 map. sync.Map 的添加、查詢和刪除元素操作的時間複雜度與內建的 map 是一樣的，都是常數級別的。與內建 map 不同的是 ，sync.Map 的零值是一個有效的值，它是一個空的 map。需要注意的是，sync.Map 並不是用來替換內建的 map 類型，它只能被應用在一些特殊的場景中。

爲什麼有 sync.Map

內建的 map 不是線程安全的，雖然內建的 map+Mutex 或 map+RWMutex 可以保證線程安全，但在下面的兩個場景中，使用 sync.Map 會比使用 map+RWMutex 性能要好很多。

怎麼使用 sync.Map

sync.Mapa 支持基本的添加元素、查詢元素、遍歷、刪除元素四種操作，此外還支持 LoadOrStore 操作。Load 方法獲取一個鍵值對的 value, 如果 key 不存在，返回的 value 是 nil，如果 key 存在，返回的 value 是一個 interface 類型，需要斷言成真正的類型。sycn.Map 遍歷使用 Range 方法，需要傳入一個函數，函數的入參和出參已經確定了, 是 func(k,v interface) bool。k 和 v 是遍歷到的 key 和 value, 在函數內部實現自己的業務邏輯。

package main

import (
 "fmt"
 "sync"
)

func main() {
 // m零值是有效的，可以直接使用
 var m sync.Map

 // 添加元素到sync.Map
 m.Store("name", "mingyong")
 m.Store("age", 20)

 // 訪問sync.Map中元素
 v, ok := m.Load("name")
 fmt.Println(v, ok)

 // 遍歷sync.Map
 m.Range(func(k, v interface{}) bool {
  fmt.Println(k, v)
  return true
 })

 // 刪除sync.Map中的元素
 m.Delete("name")
}

sync.Map 實現分析

下面將從數據結構定義，到基本的添加元素 (Store 方法）、查詢元素 (Load 方法）、遍歷元素 (Range 方法）和刪除元素 (Delete 方法）操作，結合源碼來分析 sync.Map 的實現，以及通過圖解的方式分析爲什麼有 expunged 狀態的出現。「注意，下面分析的代碼是 Go 1.14 darwin-amd64 版本」

數據結構定義

sync.Map 的結構圖如下圖所示，可以結合下面的結構體定義一起看，就很容易理解了。

先來看下 sync.Map 的結構定義，它的定義如下，可以看到它只有 4 個字段。其中 mu 鎖字段用戶保護 dirty，因爲 dirty 是一個內建的 map, 是非線程安全的，read 也是一個 map, 對 read 的讀取不需要加鎖處理。misses 是一個計數器，記錄在從 read 中讀取數據的時候，沒有命中的次數，一旦 misses 值和 dirty 長度相同之後，會把 dirty 內容提升爲 read.

type Map struct {
 mu Mutex
    
 // 把read看成一個安全的只讀的map.atomic.Value是一個interface類型的結構體，裏面實際裝的是
 // 一個map,對atomic.Value中的元素更新是通過原子操作進行的，
 read atomic.Value // readOnly

 // dirty需要使用上面的mu加鎖才能訪問裏面的元素，dirty中包含所有在read字段中但未被expunged(刪除)
 // 的元素以及新加的元素
 dirty map[interface{}]*entry

 // misses是一個計數器，記錄在從read中讀取數據的時候，沒有命中的次數，一旦misses值和dirty長度
 // 一樣之後，會把dirty內容提升爲read
 misses int
}

Map 中的 read 字段是 atomic.Value 類型，它裏面實際存儲的結構爲 readOnly,readOnly 結構如下，以原子方式存儲在 read 中

// readOnly是存在Map結構中read字段中的內容，它以原子方式存儲
type readOnly struct {
 m map[interface{}]*entry
 // amended爲true表示dirty中包含read中沒有的數據，爲false表示dirty中的數據在read都
 // 存在
 amended bool // true if the dirty map contains some key not in m.
}

expunged 用來標識 map 中的 key 是已經刪掉的指針，在 sync.Map 刪除一個 key 時，並不是立即將其從 map 中刪除，而是將 key 對應的 value 標記爲 nil 或者 expunged，在以後的處理過程中才有機會真正刪除

// expunged用來標識map中的key是已經刪掉的指針，在sync.Map刪除一個key時，並不是立即將其從
// map中刪除，而是將key對應的value標記爲nil或者expunged，在以後的處理過程中才有機會真正刪除
var expunged = unsafe.Pointer(new(interface{}))

entry 是 dirty 這個 map value 對應的類型，它代表一個值，entry 是對 * interface{} 做了一個結構體的包裝。如果 dirty 字段非 nil，map 的 read 字段和 dirty 字段會包含相同的非 expunged 的數據項，所以如果通過 read 字段更改了這個項的值，從 dirty 字段中也會讀取到這個項的新值，因爲它們指向的是同一個地址。

type entry struct {
 p unsafe.Pointer // *interface{}
}

Store 方法

Store 方法用來保存或更新一個鍵值對。它既可以是新增元素，也可以是更新元素。如果更新的元素在 read 中已存在，在下面的兩種情況下會直接更新, 不會用到鎖:

在下面的兩種情況下更新會用到鎖：

// Store保存或更新一個鍵值對
func (m *Map) Store(key, value interface{}) {
 // 檢查key是否在read中存在
 read, _ := m.read.Load().(readOnly)
 // 如果key在read中，有3種情況:
 // 1.p=nil,表示key已刪除，並且dirty中不存在數據
 // 2.p=expunged,表示key已刪除，dirty中存在數據且該key不在dirty中
 // 3.p=&entry，表示key存在，指向一個真實的value
 // 對情況1和情況3，直接將value的值存在p中，對情況2不存value，繼續走後面的邏輯
 if e, ok := read.m[key]; ok && e.tryStore(&value) {
  return
 }

 m.mu.Lock()
 // 加鎖後，繼續檢查read中是否有key存在
 read, _ = m.read.Load().(readOnly)
 // key在read中，繼續檢查key是否已經被刪除
 if e, ok := read.m[key]; ok {
  if e.unexpungeLocked() {
   // 如果key已被刪除，並且處於expunged狀態，說明此key存在read但不在dirty中
   // 並且此時dirty非空，需要將此key加入到dirty中，並且更新e.p的值指向value
   m.dirty[key] = e
  }
  e.storeLocked(&value)
 } else if e, ok := m.dirty[key]; ok {
  // key不在read中但在dirty中，直接更新dirty中e.p的值，指向value
  e.storeLocked(&value)
 } else {
  // 走到這裏說明key既不在read中也不在dirty中，肯定是一個新的key.
  // 並且dirty中所有的key都在read中
  if !read.amended {
   // 如果dirty爲nil,需要創建dirty對象，並且標記read的amended爲true，
   // 說明有元素存在於dirty中但不在read中
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
  }
  // new一個新entry，將新值加入到dirty對象中
  m.dirty[key] = newEntry(value)
 }
 m.mu.Unlock()
}

// tryStore嘗試將value的值存在e.p中
func (e *entry) tryStore(i *interface{}) bool {
 for {
  p := atomic.LoadPointer(&e.p)
  // 如果p爲expunged，不能直接存儲，因爲此時的read中所有處於非expunged狀態的key都
  // 在dirty中，將key加回到read的時候，也需要將其加入到dirty中，此處不處理這種情況
  // 直接返回
  if p == expunged {
   return false
  }
  // p爲nil或指向&entry對象，設置e.p爲i的值，即將e.p指向存入的value
  if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
   return true
  }
 }
}

// unexpungeLocked將e.p從expunged修改爲nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
 return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// storeLocked原子操作，將i存儲到e.p中，此處的i不能是expunged值
func (e *entry) storeLocked(i *interface{}) {
 atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

func (m *Map) dirtyLocked() {
 // 如果dirty字段已經存在，就不需要在創建了
 if m.dirty != nil {
  return
 }
 // 獲取read字段
 read, _ := m.read.Load().(readOnly)
 m.dirty = make(map[interface{}]*entry, len(read.m))
 // 遍歷read字段，將裏面不是punged狀態的鍵值對複製到dirty中
 for k, e := range read.m {
  if !e.tryExpungeLocked() {
   m.dirty[k] = e
  }
 }
}

Load 方法

Load 方法返回一個 key 對應的 value 值。優先從 read 中開始查詢，因爲訪問 read 不需要加鎖。如果很幸運，可以從 read 中讀取到了 key 對應的 value，就不用加鎖，這種情況下性能是最好的。但是，如果請求的 key 不在 read 中，並且 dirty 中存在有元素不在 read 中，需要進一步查詢 dirty，對 dirty 操作需要加鎖。所以，讀取不在 read 中的 key 會因爲加鎖而導致性能下降。Load 操作過程中可能存將 dirty 提升爲 read 操作，在查詢 dirty 的時候，會執行 missLocked 操作，該操作會增加 misses 值，如果 misses 值等於 dirty 長度，就會將 dirty 提升爲 read，並將 dirty 置爲空。

// Load方法返回key對應的value，第二bool型參數表示key是否在map中存在
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
 read, _ := m.read.Load().(readOnly)
 // 優先從無鎖map read中讀取
 e, ok := read.m[key]
 // 如果無鎖map中不存在並且dirty中有元素不在read中，進一步從dirty中讀取
 if !ok && read.amended {
  m.mu.Lock()
  // 雙重檢查，進一步查看read中是已有key存在
  read, _ = m.read.Load().(readOnly)
  // 如果key已存在，直接返回對應的value
  e, ok = read.m[key]
  // key還是不存在，並且dirty中有數據，不得不檢查dirty中是否有
  if !ok && read.amended {
   // 從dirty中獲取數據
   e, ok = m.dirty[key]
   // 不管key在不在dirty中，命中記錄數misses都會加1，當misses大於等於
   // dirty中數據元素的個數時，dirty中的數據會被提升到read中，提升之後
   // dirty將會被清空，命中記錄數misses清零
   m.missLocked()
  }
  m.mu.Unlock()
 }
 // key在read和dirty中都不存在，返回nil和false
 if !ok {
  return nil, false
 }
 // 返回value值，e可能來自read也可能來自dirty，所以value可能是從read獲得的，也可能是從
 // dirty獲得的
 return e.load()
}

func (m *Map) missLocked() {
 // misses計數+1
 m.misses++
 // 如果沒有達到臨界值(dirty的長度)，直接返回
 if m.misses < len(m.dirty) {
  return
 }
 // 將dirty字段的內容提升爲read
 m.read.Store(readOnly{m: m.dirty})
 // 清空dirty,dirty爲map類型，清空方法是直接賦值nil，讓GC清理掉裏面的內容
 m.dirty = nil
 // misses計數重置爲0
 m.misses = 0
}

func (e *entry) load() (value interface{}, ok bool) {
 // 原子操作，獲取e.p中值
 p := atomic.LoadPointer(&e.p)
 // p爲nil或expunged狀態都表示key被刪除了，所以直接返回nil,false
 if p == nil || p == expunged {
  return nil, false
 }
 // 返回value的值
 return *(*interface{})(p), true
}

Range 方法

Range 方法對 sync.Map 進行遍歷，需要傳入一個 func(key, value interface{}) bool 類型的函數 f, 對遍歷到的每個鍵值對調用 f 進行處理。如果函數 f 返回 false, 對 sync.Map 的迭代將會停止。

// Range 方法對sync.Map進行遍歷操作，需要傳入一個func(key, value interface{}) bool類型的
// 函數f，會對遍歷到的鍵值對調用f進行處理，如果函數f返回false,對sync.Map的迭代將停止。
// Range 方法在遍歷的時候會對sync.Map的元素至多訪問一次，如果在執行Range操作的時候，有其他協程併發
// 的添加或刪除元素，可能會導致有些元素未被遍歷到。
// Range 方法是一個O(N)時間複雜度的操作，對於存在元素在dirty不在read的情況，進行了一個優化，將dirty
// 提升爲read了，所以下次在進行Range的時候，直接對read進行遍歷，不用加鎖。
func (m *Map) Range(f func(key, value interface{}) bool) {
 
 // 如果所有的元素都在read中，直接對read進行遍歷
 read, _ := m.read.Load().(readOnly)
 // 確認是否有元素存在dirty中而不在read中
 if read.amended {
  m.mu.Lock()
  read, _ = m.read.Load().(readOnly)
  if read.amended {
   // 有元素在dirty中，對dirty進行遍歷
   read = readOnly{m: m.dirty}
   // 進行一個優化，將dirty提升爲read
   m.read.Store(read)
   // 將dirty提升爲read之後，dirty置爲nil
   m.dirty = nil
   // 計數器清理0
   m.misses = 0
  }
  m.mu.Unlock()
 }
    // 對遍歷到的每個元素，調用傳入的函數f進行處理
 for k, e := range read.m {
  v, ok := e.load()
  if !ok {
   continue
  }
  if !f(k, v) {
   break
  }
 }
}

Delete 方法

Delete 方法刪除一個元素，同樣還是優先檢查 key 是否在 read 中，如果在 read 中，就不需要檢查 dirty 了。爲啥呢？key 在 read 中分爲兩種情況，一種是此 key 只在 read 中，不在 dirty 中，很好反正不在 dirty 中，直接將 read 中元素刪掉就行了，注意此處的刪除並不是真正刪除，而是標記爲一個刪除的狀態，方便後面又有操作加入此 key 時，直接修改 read 中 e.p 的值。另一種是此 key 也存在 dirty 中，此時 dirty 中 key 對應的 e 和 read 中該 key 對應的 e 是同一個，爲什麼是同一個後面在介紹 e.p 的狀態時有詳細說明，這裏只需明白它們是同一個 e，這種情況將 e.p 設置爲 nil，其實也是將 dirty 中 e.p 也設置爲了 nil. 如果 key 在 read 中不存在，恰好當前存在元素在 dirty 中而不在 read 中，則需要進一步確認 key 是否在 dirty 中，這種情況需要加鎖，如果 key 在 dirty 中，直接調用 delete 將 dirty 中的 key 刪除。重複調用 Delete 操作刪除同一個 key 也是可以的，只有第一次會標記刪除，後面調用不做處理，因爲此 key 對應的 value 已標記爲刪除狀態了。

// Delete刪除一個key
func (m *Map) Delete(key interface{}) {
 // 先檢查key是否在read中
 read, _ := m.read.Load().(readOnly)
 e, ok := read.m[key]
 // 如果key不在read中，並且此時dirty中存在數據不在read中，繼續檢查dirty
 if !ok && read.amended {
  m.mu.Lock()
  // 加鎖再進行一次檢查
  read, _ = m.read.Load().(readOnly)
  e, ok = read.m[key]
  if !ok && read.amended {
   // 直接從dirty中刪除key,此時read中是不存在的，dirty中刪掉之後，兩邊都是
   // 不存在了
   delete(m.dirty, key)
  }
  m.mu.Unlock()
 }
 // 滿足ok爲true，read中肯定是有該key的， dirty有兩種情況:
 // 1是dirty中沒有該key， 2是dirty中也有該key
 // 對於情況1，因爲dirty中不存，直接將read中e.p設置爲nil,標記爲刪除狀態
 // 對於情況2，dirty中key對應的e和read中該key對應的e是同一個，所以直接將
 // read中的e.p設置爲nil,其實也是將dirty中e.p也設置爲nil了
 if ok {
  e.delete()
 }
}

func (e *entry) delete() (hadValue bool) {
 for {
  p := atomic.LoadPointer(&e.p)
  // p爲nil和expunged都表示之前已刪除過了，直接返回false表示未進行實際的刪除
  if p == nil || p == expunged {
   return false
  }
  // 將e.p置爲nil, key並未從read中刪除，如果key存在於dirty中，key也是未從dirty
  // 中刪除的
  if atomic.CompareAndSwapPointer(&e.p, p, nil) {
   return true
  }
 }
}

LoadOrStore

LoadOrStore 方法可以看做 Load 操作和 Store 操作的組合，如果 key 已經在 sync.Map 中，返回當前 key 對應的 value, 否則將存儲傳入的 value 值。

// LoadOrStore 可以看做Load操作和Store操作的組合，如果key已存在m中（無論是在read中還是dirty中），
// 就是隻要key沒有被刪除，就返回當前的key對應的value值，否則將存儲傳入的value值，
// 第二返回參數是一個bool值，表示最後執行的是load操作還是store操作
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
 // 還是優先檢查read，避免加鎖
 read, _ := m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
  // 嘗試load和store操作，如果ok爲true，表示load成功
  actual, loaded, ok := e.tryLoadOrStore(value)
  if ok {
   return actual, loaded
  }
 }

 m.mu.Lock()
 // 雙重檢查
 read, _ = m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
  // e.p爲expunged狀態，表示m.dirty非空且dirty不存在該key
  // 需要將key-value加到dirty中，這裏dirty和read實際上key
  // 指向的是同一個e，更新e值，dirty和read中都存有該key-value了
  if e.unexpungeLocked() {
   m.dirty[key] = e
  }
  actual, loaded, _ = e.tryLoadOrStore(value)
 } else if e, ok := m.dirty[key]; ok {
  // key在dirty中不在read中，
  actual, loaded, _ = e.tryLoadOrStore(value)
  m.missLocked()
 } else {
  if !read.amended {
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
  }
  m.dirty[key] = newEntry(value)
  actual, loaded = value, false
 }
 m.mu.Unlock()

 return actual, loaded
}

func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
 p := atomic.LoadPointer(&e.p)
 // key已被刪除，需要進一步判斷處理，這裏先終止處理
 if p == expunged {
  return nil, false, false
 }
 // key存在，value值有效，直接返回之前的value值，即執行Load操作
 if p != nil {
  return *(*interface{})(p), true, true
 }

 // 走到這裏說明key也是已經被刪除，e.p爲nil,並且dirty是空的，所以直接將i存儲在e.p中即可，不用關心dirty
 ic := i
 for {
  // 原子更新e.p的值，更新前爲nil
  if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
   return i, false, true
  }
  // 進一步判斷e.p是不是被別的地方已經修改爲非nil了
  p = atomic.LoadPointer(&e.p)
  // 如果p爲expunged，說明key在其他地方已經被刪除了，需要進一步判斷處理，這裏先終止處理
  if p == expunged {
   return nil, false, false
  }
  // e.p已經被其他地方設置值了，這裏直接返回已設置的值
  if p != nil {
   return *(*interface{})(p), true, true
  }
 }
}

p 的三種狀態

再回頭看下 sync.Map 的數據結構，無論是 dirty 還是 read 中的 m 它們都是內建的 map, 並且這個 map 的 value 是 * entry 類型。entry 的定義如下

type entry struct {
 p unsafe.Pointer // *interface{}
}

可以看到, entry 是對 unsafe.Pointer 做了一層包裝，這裏標題中說的 p 就是 entry 中的 p. p 有三種狀態，分別是 nil, expunged, 正常狀態（指向一個有效的 value 地址）

爲什麼搞這麼複雜，只有 nil 和正常狀態兩種狀態可以嗎？可以的，之所以搞這麼複雜，是爲了儘可能榨乾性能，提升程序的性能。下面通過圖解的方式分析 p 中的 expunged，看完之後你就很清楚的明白 expunged 是幹啥的，爲什麼有 expunged 狀態。將 read 和 dirty 理解爲兩個集合，key 是在 read 還是 dirty 中，理解爲 key 是在集合 read 和還是在集合 dirty 中。這裏重點是梳理清楚 p 的狀態，所以圖中只畫了 key，不關心 value 細節。每個集合中的一個小方塊代表一個 key。不同顏色的小方塊代表的含義不同，具體含義如下：

對於一個新的 sync.Map, 開始向裏面添加兩個元素，key 分別爲 a 和 b. 得到集合狀態如下圖所示，此時 read 是空的，dirty 中有兩個元素。

然後進行兩次查詢元素操作，因爲 read 爲空，兩次查詢都是從 dirty 中獲取到的，misses 未命中計數達到 dirty 的長度，會將 dirty 提升爲 read, 並將舊 dirty 清空，所以得到如下集合狀態，read 集合中有兩個元素，dirty 集合是空的。

然後執行刪除（key 爲 a）元素操作，將 a 對應的 e.p 設置爲 nil，標記爲刪除狀態，並不是直接 delete 掉。此時 dirty 中沒有元素，read.amended 爲 false, 所以無需對 dirty 做任何處理。得到的集合狀態如下圖所示。

在上圖的狀態的基礎上，向裏面添加新元素 c，因爲 c 在 read 和 dirty 中都不存在，需要將其添加到 dirty 中（注意，添加新元素都是添加在 dirty 中）。在添加 c 到 dirty 之前，需要將 read 中非刪除的元素（key 爲 b) 拷貝一份到 dirty 中，並將 read 中刪除的元素即 e.p=nil 修改爲 e.p=expunged 狀態。得到的集合狀態如下圖所示。

好了，現在可以分析爲什麼有 e.p=expunged 這個狀態了，對比上面兩張圖，可以看到他們的差別是一個 dirty 是空的，另一個 dirty 是非空的。現在向裏面重新添加回元素 a 的時候，對於 key 爲 a 對應的 e.p=nil 狀態，直接在 read 中添加，這個過程是不需要進行加鎖的。但是對於 key 爲 a 對應的 e.p=expunged 狀態，需要在 read 和 dirty 中都添加，這個過程是需要進行加鎖的。經過上面的分析，我們也就明白了，爲什麼要搞一個 expunged 狀態，是爲了 dirty 爲空的時候，直接對 read 進行操作不用加鎖，提升程序性能。

總結

理解 sync.Map 就是要搞清楚 read 和 dirty 中元素的分佈情況，什麼情況下元素在 read 中什麼情況下元素在 dirty 中，記住一句話，「只要 dirty 不是 nil,dirty 中擁有所有的元素，這個時候最全的數據以 dirty 爲準, 只要 dirty 爲 nil, 所有的元素都在 read 中，這個時候最全的數據以 read 爲準」。下面對 sync.Map 一些要點進行一個總結。

Go sync.Map 看一看 [1] 深入理解 Go-sync.Map 原理剖析 [2]

Reference

[1]

Go sync.Map 看一看: https://segmentfault.com/a/1190000018657984

[2]

深入理解 Go-sync.Map 原理剖析: https://segmentfault.com/a/1190000020325763

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

猜你喜歡