Go sync map 的內部實現

目錄

1. 引言 a. 簡單介紹併發性及其在此上下文中的應用

2. sync.RWMutex 和 map 一起使用的問題

3. 介紹 sync.Map a. 在哪些場景使用 sync.Map?

4. sync.Map 實現細節 a. 加載、存儲和刪除如何在高層次上工作？b. 存儲被刪除和只是 nil 之間的區別 c. Store(key, value interface) d. Load(key interface{}) (value interface{}, ok bool) e. LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) f. LoadAndDelete(key interface{}) (value interface{}, loaded bool) g. Delete()(value interface{}, ok bool) h. Range(f func(key, value interface{}) bool)_

5. sync.Map 和 RWMutex 保護的 map 之間的性能對比。快速優化指南

6. 極致的優化是什麼樣的？

引言

這篇文章簡單介紹瞭如何使用 sync.Map，同時解釋 sync.Map 的工作原理。

在應用代碼中，大多數操作都是依賴 hash map。因此，如果 hash map 的讀寫很慢，它們最終會成爲性能的主要瓶頸。在引入 sync.Map 之前，標準庫只需要依賴於不是線程安全的內置 map。當多個 goroutines 調用它時，必須依賴 sync.RWMutex 來同步訪問。但是這麼做，並不能很好地利用多核 CPU 的性能，所以在 go1.9 引入 sync.Map 來解決多核 CPU 操作 map 的性能問題。當程序運行在 64 核的機器上，sync.RWMutex 的性能下降會比較明顯。

使用sync.RWMutex,sync.RWMutex 中readerCount的值隨着每次調用讀鎖而增加，這會導致緩存的競爭。最終導致處理器其他內核的性能下降。這是因爲每增加一個核心，更新每個核心緩存的開銷就會增加。sync.Map 文檔

snyc.Map 類型針對兩個常見案例進行優化

(1) 當給定鍵的 entry 只寫入一次但讀取多次時，就像只會增長的緩存中一樣

(2) 當多個 goroutine 讀取、寫入和重寫 keys 。在這兩種情況下，與使用單獨的 Mutex 或 RWMutex 配對的 map 相比，使用 sync.Map 可以顯着減少鎖爭用。

帶有讀寫鎖的 map 在第一個 case 中，在頻繁地調用 atomic.AddInt32(&rw.readerCount, 1) and atomic.AddInt32(&rw.readerWait, -1) 下性能顯著下降。寫入的開銷無法避免，但我們必須期望讀取速度非常快，特別是它作爲一個緩存，應該有助於在快速管道中處理數據。

簡單介紹併發性及其在此上下文中的應用

現代應用程序必須在短時間內處理大量歷史數據。爲此，他們重度依賴高速的多核處理器。

這些系統處理的實時輸入通常具有不可預測的到達時間。這正是操作系統級線程和 goroutines 真正閃耀的地方。這些依賴鎖和信號量的組合來讓它們在等待輸入時 "休眠"。這會釋放虛擬線程使用的 CPU 資源，直到它收到喚醒它的中斷。等待中斷的線程或 goroutine 類似於等待在輸入到達時調用的回調——中斷信號在解鎖它正在等待的互斥鎖時（或當信號量變爲零時）產生。

在理想情況下，我們希望應用程序處理數據的能力隨着計算機核心數增加而增強。即使程序一開始的設計是多個 goroutines 處理多個任務，也並不一定能夠很好地擴展算力。

某些代碼塊可能需要鎖或 atomic 指令進行同步，將這部分 (譯者注: 臨界區) 變成強制同步執行的代碼塊。比如每個 goroutine 都可以訪問的中央緩存。這些會導致鎖爭用，從而阻止應用程序通過增加內核來提高性能。甚至更糟的是，這些可能會導致性能下降。atomic 指令也會帶來開銷，但它比鎖引起的開銷小得多。

硬件級原子指令對於內存的訪問並不總是保證讀取最新值。原因是，每個處理器內核都維護一個可能失效的本地緩存。爲了避免這個問題，原子寫操作通常跟在指令之後強制每個緩存更新。最重要的是，爲了提升（在硬件和軟件級別）的性能，它還必須防止 內存重新排序 (就是我們常說的指令重排，cpu 的一種優化手段)。

map 結構被廣泛使用，以至於幾乎每個應用程序都在其代碼中依賴它。並且要在併發應用程序中使用它，讀取和寫入它必須與 Go 中的 _sync.RWMutex_ 同步。這樣做會導致對 atomic.AddInt32(...)的過度使用，從而導致頻繁的緩存爭用，強制刷新緩存和內存 (指令) 排序。這會降低性能(譯者注: 這裏說的緩存是 CPU 中的緩存)。

sync.Map使用 atomic 指令和鎖的組合，但確保讀取操作的路徑儘可能短，大多數情況下，每次調用 Load(...) 只需一個原子加載操作案件。atomic 存儲指令通常是強制更新（每個內核的）緩存的指令，而 atomic 加載可能只需要強制執行內存排序並確保其原子性。只有 atomic.AddInt32(...) 最糟糕，因爲它與對同一變量的其他原子更新的爭用將導致它忙於等待，直到依賴於比較和交換 (譯者注: 這裏便是 CAS 指令，在彙編中一個指令完成兩個操作) 指令的更新成功。

sync.RWMutex 和 map 一起使用的問題

使用 sync.RWMutex 來同步訪問 map 的一個例子: https://github.com/golang/go/blob/912f0750472dd4f674b69ca1616bfaf377af1805/src/sync/map_reference_test.go#L25

爲方便起見，將上面的代碼鏡像到這裏:

源代碼 1

// Taken from here: https://github.com/golang/go/blob/912f0750472dd4f674b69ca1616bfaf377af1805/src/sync/map_reference_test.go#L25
// RWMutexMap is an implementation of mapInterface using a sync.RWMutex.
type RWMutexMap struct {
 mu    sync.RWMutex
 dirty map[interface{}]interface{}
}

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

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

func (m *RWMutexMap) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
 m.mu.Lock()
 actual, loaded = m.dirty[key]
 if !loaded {
  actual = value
  if m.dirty == nil {
   m.dirty = make(map[interface{}]interface{})
  }
  m.dirty[key] = value
 }
 m.mu.Unlock()
 return actual, loaded
}

func (m *RWMutexMap) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
 m.mu.Lock()
 value, loaded = m.dirty[key]
 if !loaded {
  m.mu.Unlock()
  return nil, false
 }
 delete(m.dirty, key)
 m.mu.Unlock()
 return value, loaded
}

func (m *RWMutexMap) Delete(key interface{}) {
 m.mu.Lock()
 delete(m.dirty, key)
 m.mu.Unlock()
}

func (m *RWMutexMap) Range(f func(key, value interface{}) (shouldContinue bool)) {
 m.mu.RLock()
 keys := make([]interface{}, 0, len(m.dirty))
 for k := range m.dirty {
  keys = append(keys, k)
 }
 m.mu.RUnlock()

 for _, k := range keys {
  v, ok := m.Load(k)
  if !ok {
   continue
  }
  if !f(k, v) {
   break
  }
 }
}

當性能很重要時，我們可以通過減少並行獲取相同鎖的頻率（從而減少鎖爭用的頻率）或完全用 atomic 指令（如 atomic-load、atomic-store 和 atomic-compare）代替鎖來解決這個問題和交換。atomic 操作也不是靈丹妙藥，因爲依賴於 atomic 比較和交換的狀態更新在無限循環中運行，直到更新成功。當存在爭用時，更新通常不會發生，因此當有大量併發更新時，導致它們忙等待。

大多數應用程序通常使用兩者的組合。甚至有些應用程序也嘗試選擇更快的替代方案，例如減少對循環中旋轉的 atomic 比較和交換指令的調用次數。

[sync.RWMutex](https://github.com/golang/go/blob/912f0750472dd4f674b69ca1616bfaf377af1805/src/sync/rwmutex.go#L28) 使用信號量的組合以及兩個附加變量 readerCount和 readerWait 來記錄正在讀取和等待讀取的數量。

要理解在多核環境中我們需要使用 sync.Map，而不是使用由 sync.RWMutex 保護的內置 map，那麼，我們必須深入研究how [sync.RWMutex](https://sreramk.medium.com/go-sync-rwmutex-internals-and-usage-explained-9eb15865bba) 的內部工作。

sync.Map 有下面這些一看就懂的方法（取自 這裏）

源代碼 2

//Delete deletes the value for a key.
func (m *Map) Delete(key interface{})

//Load returns the value stored in the map for a key, or nil if no 
//value is present. The ok result indicates whether value was found 
//in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool)

//LoadAndDelete deletes the value for a key, returning the previous 
//value if any. The loaded result reports whether the key was 
//present.
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool)

//LoadOrStore returns the existing value for the key if present. 
//Otherwise, it stores and returns the given value. The loaded 
//result is true if the value was loaded, false if stored.
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)

//Range calls f sequentially for each key and value present in the 
//map. If f returns false, range stops the iteration.
//Range does not necessarily correspond to any consistent snapshot 
//of the Map's contents: no key will be visited more than once, but 
//if the value for any key is stored or deleted concurrently, Range 
//may reflect any mapping for that key from any point during the 
//Range call.
//Range may be O(N) with the number of elements in the map even if f 
//returns false after a constant number of calls.
func (m *Map) Range(f func(key, value interface{}) bool)

//Store sets the value for a key.
func (m *Map) Store(key, value interface{})

在繼續嘗試瞭解 sync.Map 的原理之前，還要了解 爲什麼我們絕對需要這些方法 [LoadAndDelete (...)](https://sreramk.medium.com/go-why-does-sync-map-97342f12b3fa)和 [LoadOrStore(...)](https://sreramk.medium.com/go-why-does-sync-map-97342f12b3fa)。

sync.Map總是維護兩個 map 對象，一個用於讀取，一個用於寫入。讀映射是部分不可變的，而寫映射是完全可變的。

在任何時候，可讀 map 都不會更新，而可寫的 map 是可以更新，表示存儲的準確狀態（即使它沒有設置爲 nil）。每當從只讀 map 未命中鍵時，它就會從帶有 sync.Mutex 鎖的寫入映射中讀取。

刪除一個鍵的時候，鍵可以只存在於可寫 map 中，也可以存在於可寫 map 和可讀 map 中。如果它僅存在於可寫 map 中，則使用內置的 delete 操作將其完全刪除。但是如果它同時存在於可寫 map 和可讀 map 中，則它只設置爲nil（注意，將字段設置爲 nil 的更新操作同時反映在讀 map 和寫 map 中，因爲它們指向同一個 entry 對象；稍後會詳細介紹）。

每次訪問由 sync.Mutex 保護可寫的 map，也有原子指令的開銷。因此，這些開銷略大於由 sync.RWMutex 保護的內置 map。

因此，此實現的目標之一應該是減少讀取未命中的頻率。這是通過將可寫 map 提升爲下一個可讀的 map 來完成的（同時將指向可寫 map 的指針設置爲 nil），當讀取未命中數大於可寫 map 的長度時（此長度使用 len ）。然後丟棄過時的可讀 map。

在第一次嘗試向可寫的 map 添加鍵時，通過將新可讀 map 的內容複製到可寫的 map 來創建新 map 對象。數據搬移結束之後，可讀的 map 將存儲最準確的狀態。但是被搬移之後就變成了 "不可變"，不會再有新的 key 被添加進去。因此，向 sync.Map 添加額外的鍵會使可讀的 map 失效。

更新有兩種不同的方式。如果添加的鍵（使用sync.Map 的Store(...) 或LoadOrStore(...) 操作）已經存在於可讀的 map 中，則可讀的 map 中與鍵關聯的值是以原子方式更新（注意：以這種方式對 value 字段所做的更改也將立即反映在可寫映射上。本文稍後將解釋這是如何做到的）。如果鍵只存在於可寫的 map 中，或者鍵根本不存在，則更新僅在可寫區域中進行，並需要使用 “sync.Mutex” 鎖。

sync.Map 的使用場景

sync.Map 最初是爲了減少 Go 的標準庫包所產生的開銷，這些包一直使用由 sync.RWMutex 保護的 map。所以 Go 的作者們發現像 sync.Map 這樣的存儲不會增加太多的內存開銷（另一種內存密集型解決方案是爲每個使用的 goroutine 提供一個單獨的映射副本，但讓它們同步更新）而還提高程序在多核環境中的性能。因此，sync.Map 的初衷是爲了解決標準包中的問題，但還是公開了，希望大家覺得有用。

但是，文檔並沒有真正詳細說明 sync.Map 究竟在哪裏最有用。通過基準測試 和 [sync.Map](https://medium.com/@deckarep/the-new-kid-in-town-gos-sync-map-de24a6bf7c2c) 表明，僅當它在具有超過 4 個核的系統上運行時，使用 sync.Map 比使用由 sync.RWMutex 保護的 map 更加高效。sync.Map 最理想的用例是將其用作緩存，特別是頻繁訪問不相交的鍵；或從同一組鍵中廣泛讀取它。

新添加的鍵可能會留在可寫的 map 中，而最常訪問的鍵可能會留在可讀的 map 中。當添加、讀取和刪除一組有限的鍵時，假定每個操作都以相同的頻率發生時，sync.Map 將執行最少的操作。當你不讓寫 map 中的鍵被提升時，就會發生這種情況經常添加和刪除它們。在這種情況下，我們最好將 map 與 sync.RWMutex 或 sync.Mutex 一起使用（併發散列映射的確切選擇通常通過基準測試決定）。

每當一個鍵在 sync.Map 中被刪除，它只將其關聯的值字段標記爲[nil](https://github.com/golang/go/blob/21a04e33353316635b5f3351e807916f3bb1e844/src/sync/map.go#L297)，但直到第一次寫入後，key 才真正刪除 writable-map 作爲可讀 map。這會導致內存開銷。但是這種開銷只是暫時的，等到下一個提升週期，開銷就會下降。

sync.Map 實現細節

方便起見，這裏給出 [sync.map](https://github.com/golang/go/blob/21a04e33353316635b5f3351e807916f3bb1e844/src/sync/map.go#L12) 的結構。

源代碼 3

// Map is like a Go map[interface{}]interface{} but is safe for concurrent use
// by multiple goroutines without additional locking or coordination.
// Loads, stores, and deletes run in amortized constant time.
//
// The Map type is specialized. Most code should use a plain Go map instead,
// with separate locking or coordination, for better type safety and to make it
// easier to maintain other invariants along with the map content.
//
// The Map type is optimized for two common use cases: (1) when the entry for a given
// key is only ever written once but read many times, as in caches that only grow,
// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
// sets of keys. In these two cases, use of a Map may significantly reduce lock
// contention compared to a Go map paired with a separate Mutex or RWMutex.
//
// The zero Map is empty and ready for use. A Map must not be copied after first use.
type Map struct {
 mu Mutex

 // read contains the portion of the map's contents that are safe for
 // concurrent access (with or without mu held).
 //
 // The read field itself is always safe to load, but must only be stored with
 // mu held.
 //
 // Entries stored in read may be updated concurrently without mu, but updating
 // a previously-expunged entry requires that the entry be copied to the dirty
 // map and unexpunged with mu held.
 read atomic.Value // readOnly

 // dirty contains the portion of the map's contents that require mu to be
 // held. To ensure that the dirty map can be promoted to the read map quickly,
 // it also includes all of the non-expunged entries in the read map.
 //
 // Expunged entries are not stored in the dirty map. An expunged entry in the
 // clean map must be unexpunged and added to the dirty map before a new value
 // can be stored to it.
 //
 // If the dirty map is nil, the next write to the map will initialize it by
 // making a shallow copy of the clean map, omitting stale entries.
 dirty map[interface{}]*entry

 // misses counts the number of loads since the read map was last updated that
 // needed to lock mu to determine whether the key was present.
 //
 // Once enough misses have occurred to cover the cost of copying the dirty
 // map, the dirty map will be promoted to the read map (in the unamended
 // state) and the next store to the map will make a new dirty copy.
 misses int
}

正如我們所見，sync.Map 有一個 dirty map 存儲和一個用於存儲 “clean” 的 read map 的 atomic.Value 字段。所有對 dirty 的訪問總是由 mu 保護。在我們查看每個獨立的方法如何工作之前，我們必須對 sync.Map 的工作原理和設計思想有一個宏觀的瞭解。

The [鍵值對構成的 entry ](https://github.com/golang/go/blob/c1cc9f9c3d5ed789a080ef9f8dd9c11eca7e2026/src/sync/map.go#L73)結構對於sync.Map的功能至關重要

源代碼 4

type entry struct {
 // p points to the interface{} value stored for the entry.
 //
 // If p == nil, the entry has been deleted, and either m.dirty == nil or
 // m.dirty[key] is e.
 //
 // If p == expunged, the entry has been deleted, m.dirty != nil, and the entry
 // is missing from m.dirty.
 //
 // Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty
 // != nil, in m.dirty[key].
 //
 // An entry can be deleted by atomic replacement with nil: when m.dirty is
 // next created, it will atomically replace nil with expunged and leave
 // m.dirty[key] unset.
 //
 // An entry's associated value can be updated by atomic replacement, provided
 // p != expunged. If p == expunged, an entry's associated value can be updated
 // only after first setting m.dirty[key] = e so that lookups using the dirty
 // map find the entry.
 p unsafe.Pointer // *interface{}
}

entry 結構相當於 “容器” 或 “盒子”，保存和鍵相關聯的值。不是直接用 m[key] = value 存儲值，而是將 value 封裝在一個方便的 entry 類型容器中。然後將 entry 的地址存儲到與鍵關聯的 map 對象中。

在任何的時間節點中，都假定 entry 滿足以下三個屬性之一：

1. 它包含一個有效值：p != expunged && p != nil。expunged（意味着永久刪除）被定義爲 var expunged = unsafe.Pointer(new(interface{}))，這是一個只設置一次的任意全局值。它沒有任何價值。它只是爲了將 “刪除” 值與任意 entry 字段中的所有其他 nil 和非 nil 值區分開來。

2. 它包含 nil。

3. 它包含 expunged（我們很快就會詳細介紹 nil 狀態與 expunged 狀態有何不同）。

將指針包裹在一個像 entry 這樣的結構下是非常方便的。如果您正在更改 entry 的狀態，您可以期望它在每個其他具有指向 entry 對象的指針的位置立即更新。

所以，如果您在可讀的 map 和可寫的 map 之間共享 entry 的地址，更新可讀 map 的 entry也將反映可寫的 map 上的更改以及反之亦然（請注意，在源 3 和可寫映射中）源 5 映射被定義爲map[inerface{}]entry，其中鍵是一個interface{}，並且該 entry 存儲爲一個指針）。

源代碼 5：只讀結構體

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
 m       map[interface{}]*entry
 amended bool // true if the dirty map contains some key not in m.
}

sync.Map 結構的 read 字段是一個 atomic.Value 字段，它保存對 readOnly（源代碼 5）的引用。此結構包含另一個字段 amended，當 sync.Map 對象通過添加新鍵進行擴展並且自添加新鍵後尚未發生升級時，該字段爲真。在這種情況下，鍵進入可寫的 map，而可讀 map 中沒有它的記錄。amended 字段爲 true 時，表示這種特定狀態，其中 dirty映射包含的記錄，但是 read 不包含記錄。

加載、存儲和刪除如何在高層次上工作？

這些操作的讀取部分通常是廉價的（相對）。原因是從 atomic.Value 字段中檢索到 readOnly 對象的指針，並快速搜索與鍵關聯的值。如果該值存在，則返回。

如果它不存在，那麼它很可能是最近添加的。在這種情況下，需要檢查 dirty 字段（需要 mu 字段的保護）。如果鍵存在於 dirty 字段中，則將其作爲結果進行檢索。

在此實現中 (譯者注: dirty map)，讀操作會比較慢。隨着 readOnly 對象中的每次未命中，字段 misses 的值自動遞增。當 misses 計數大於 dirty 的大小時，通過創建一個新的 readOnly對象來包含它，它會被提升（直接移動它的指針）到 read 字段。發生這種情況時，會丟棄 read 字段的先前值。

所有涉及 dirty map 的操作都在互斥鎖 mu 保護的區域內執行。

當記錄被存儲到 sync.Map 中時，它會通過以下三種方式之一進行處理:

1、修改 (read.Load().(readOnly))[key]返回的 entry 實例，如果檢索成功。修改是通過將值添加到 entry 字段來完成的。

2. 修改 dirty[key] 返回的 entry 實例，如果檢索成功。修改是通過替換 entry 對象（存儲在 atomic.Value 類型的 read 對象內）中的值來完成的。如果第一步失敗，則執行此操作。

3. 如果 dirty 爲 nil（當read.amended爲 false 時就是這種情況），創建一個新的 map 並將只讀 map 中的所有內容複製到它。然後將記錄添加到 dirty（注意，隨着字段被複制，entry 對象的地址就是被複制的對象。因此，讀映射和寫映射中存在的每個鍵都指向準確的相同的 entry 對象。）

在刪除的情況下，如果鍵存在於 read 中的 readOnly 對象中，它的 entry 實例會自動更新爲 nil。這個操作不需要獲取 mu。但是在 dirty 字段中搜索鍵時需要獲取 mu。如果鍵不存在於 read 中，它會在 dirty 中查找，同時由 mu 保護。如果只在 dirty 中找到，則直接使用內置的 delete 函數刪除 entry 對象。

因此，當在 read 字段持有的 readOnly 實例中找到鍵時，讀取、寫入和刪除操作將是完全原子的。而其他需要通過 dirty 處理的情況將由 mu 保護。

對 entry 字段所做的任何修改都將反映在 read 和 dirty map 中的 readOnly 對象上。因爲，每當通過複製 readOnly 實例創建新的 map[interface{}]entry 對象時，只會複製 entry 對象的地址。

存儲 expunged 和簡單的 nil 之間的區別

始終認爲以下屬性成立：

1. entry 裏面有一個指針。在任何時間，它的指針都可以保存 expunged、nil 或指向接口的指針，該指針保存了用戶通過Store(...) 或 LoadOrStore(...)方法提供的有效值。

2. 如果 entry 保存的是 nil，則表示與鍵關聯的值已通過調用 Delete(...) 或 LoadAndDelete(...) 進行刪除，而它存在於 readOnly 對象中，並且 髒 map。

3. If entry holds expunged, it signifies that a non-nil dirty map exists which does not have the same key that associates the entry field.

4. 如果 entry 包含 expunged，則表示存在非 nil dirty 映射，該映射不具有關聯 entry 字段的相同鍵。

當misses > len(dirty)（misses 是sync.Map 結構中的一個字段）時，dirty map 被複制到 atomic.Value 類型的 read 字段中。這樣做的代碼是：m.read.Store(readOnly{m: m.dirty}) 其中，這裏的 Store 是一個原子存儲操作。

readOnly 對象中有兩個字段。一個用於 map，另一個用於 amended 變量，該變量表示升級後是否將新鍵添加到 sync.Map 對象。第一次嘗試在升級後插入鍵會導致 readOnly對象內的 map 被逐鍵複製到 dirty map 鍵。與存儲 nil 的 entry 對象相關聯的每個鍵都不會被複制到 dirty 映射中，而是將其 entry 對象更新爲包含expunged。

因此，expunged 的鍵僅存在於 乾淨 映射中，而不會將它們複製到新的 dirtymap。這是在假設不會再次添加被刪除一次的鍵的情況下完成的。

有兩個獨立的未導出方法，爲 sync.Map 定義的 missLocked() 和 dirtyLocked()。他們的責任如下:

1. 傳播 dirty 映射（同時將sync.Map中的dirty字段設置爲nil）

2. 將 readOnly 對象（其 amended 字段設置爲 false）中的鍵值對複製到新創建的 dirty map 對象（通過忽略與 entry 對象關聯的鍵）設置爲 nil 並使它們expunged；因爲它們沒有被複制到dirty map 中）。missLocked() 每次在讀取 readOnly對象時出現鍵未命中時都會被調用。除了 Range(…)之外，sync.Map 中定義的每個導出方法都可以觸發調用，因爲它們都首先嚐試檢索存儲的記錄並接受 key 作爲參數。missLocked() 僅在其大小小於未命中數時纔會提升 dirty 映射。

Store(key, value interface{}) 接口:

源代碼 6: Store 方法

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
 
 /// PART 1
 read, _ := m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok && e.tryStore(&value) {
  return
 }
 ///------------------------------------------------------------
 
 
 /// PART 2
 m.mu.Lock()
 read, _ = m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
  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
  }
  e.storeLocked(&value)
 ///--------------------------------------------------------------
 
 /// PART 3
 } else if e, ok := m.dirty[key]; ok {
  e.storeLocked(&value)
 /// -------------------------------------------------------------
  
  
 /// PART 4
 } else {
  if !read.amended {
   // We're adding the first new key to the dirty map.
   // Make sure it is allocated and mark the read-only map as incomplete.
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
  }
  m.dirty[key] = newEntry(value)
 }
 m.mu.Unlock()
 /// --------------------------------------------------------------
}

讓我們將上面的代碼分成四部分（上面標記了包含每個部分的區域）。第一部分嘗試從 read 中檢索值，這是一個包含 readOnly 對象的 sync.Value 字段。如果讀取成功，它會嘗試將值以原子方式存儲到 entry對象中。源代碼 7 顯示了它是如何完成的。

tryStore(…)操作中的 atomic 更新包含一個無限循環，該循環在值之前被 expunged 時終止。這是因爲，expunged 值表示在 dirty map 中沒有相同鍵字段的副本，而在 只讀 對象中有一個。因此，在這種情況下更新指針不會反映在 dirty map 上，它總是應該包含 sync.Map 的完全更新和準確狀態。除了最近剛剛推廣的情況。在這種情況下，dirty 字段將暫時保留 nil，直到第一次嘗試寫入它，因爲它被設置爲 nil。

源代碼 7 中的無限循環導致函數保持 “忙等待” 狀態，直到更新成功。原子比較和交換操作接受三個參數。要修改的指針、指針中可能包含的舊值和新值。如果舊值與指針中保存的原始值相同，則新值存儲在指針中。

在源代碼 7 中，指針首先從 entry 對象中自動加載，並檢查它是否被 expunged。如果是，那麼tryStore 會失敗，因爲expunged 表示entry 對象不存在於與其鍵關聯的 dirty map 中。因此，將值存儲到從 read 映射中檢索到的 entry 對象將不再有用（因爲修改不會反映在 dirty map 上）。

如果 e.p（存儲在 entry 對象中的指針）與之前的p值相同，則源代碼 7 第 11 行中的 atomic-compare-and-swap 指令負責添加新值在源代碼 7 的第 8 行讀取。如果在不同的 goroutine 中運行的方法在第 11 行執行之前原子地修改了 p 的底層值，比較和交換指針操作失敗導致循環繼續。如果 p 被修改爲包含 expunged，那麼循環會因爲第 8 行的條件分支而中斷。

這個無限循環將一直持續到在第 7 行到第 11 行的語句被執行時 e.p 沒有被不同的 goroutine 修改。這就是爲什麼當我們使用 atomic 指令而不是讓 goroutine 休眠直到需要再次運行的鎖時，CPU 上的爭用會更加嚴重。原子指令導致 “忙等待” 發生，直到沒有爭用。

源代碼 7：tryStore 方法

// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.
func (e *entry) tryStore(i *interface{}) bool {
 for {
  p := atomic.LoadPointer(&e.p)
  if p == expunged {
   return false
  }
  if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
   return true
  }
 }
}

其餘部分 2、3 和 4（在 Source 6 中）都在一個由 mu 鎖保護的區域內運行。第 1 部分在 key 存在於 readOnly 對象中並且 tryStore 操作（如上所述）成功時返回。

但是第 1 部分失敗意味着 key 不存在於 readOnly 對象中，或者它已被刪除。繼續第 2 部分，讀取值再次重新加載到鎖定區域內。

可能會在調用從不同 goroutine 執行的 missLocked() 之後被替換，該 goroutine 也將在獲取 mu 後執行（_Note ，每個帶有後綴 Locked 的函數都應該在由 mu 保護的鎖定區域內執行）。但是因爲第 1 部分沒有獲取 mu，在源代碼 6 的第 6 行檢索到的值可能會過時。

在第 2 部分中，再次檢索了 entry 指針。現在，調用e.unexpungeLocked() 檢查存儲在 entry 中的值是否被 expunged：

1. 如果它是 nil 或其他任何東西，則表示在 dirty 映射中也必須存在相同的鍵。

2. 但如果它是 expunged，則表示該鍵不存在於 dirty 映射中，並且必須將其添加到其中。因此，由 read.m[key] 檢索到的 entry 對象的指針被存儲到與其適當的鍵相關聯的dirty 中。因爲使用了相同的指針，對底層 entry 對象的任何更改都會反映在 “乾淨” map 和 “dirty” map 中。對 unexpungeLocked() 的調用會執行語句 return atomic.CompareAndSwapPointer(&e.p, expunged, nil)（這是其定義中唯一的語句）。這確保了 e.p 僅在它被 expunged時更新。您不必在這裏忙着等待以允許更新發生。這是因爲 CompareAndSwapPointer(...)的 “舊指針” 參數是一個常量（expunged）並且它永遠不會改變。

tryStore() 和 unexpungeLocked() 都可以更新 e.p，儘管它們不是由同一個互斥鎖相互保護的。因此，他們可能會嘗試從不同的 goroutines 同時更新 e.p。但這不會成爲競爭條件，因爲 unexpungeLocked() 應該僅在其指針（入口 entry 的 p 字段）設置爲 expunged 時修改入口 entry。

在不同的 goroutine 上運行的 unexpungeLocked() 可以在 Source 7 的第 7 行和第 11 行之間的任何地方執行它的 CompareAndSwapPointer(…) 語句。如果它在這些行之間執行，底層指針的值將在第 11 行的比較和交換操作將導致循環失敗並再次重複。因此，如果出現以下情況，則無法成功執行 Source 7 中第 7 行和第 11 行之間的區域：

1. 不同的 goroutine 執行相同的區域，試圖修改相同的底層指針，或者，

2. 如果 unexpungeLocked() 在同一時間範圍內同時執行。在第 2 部分中，值最終通過調用 storeLocked(...)存儲到 entry 對象中。現在轉到第 3 部分。第 2 部分中的條件在兩種可能性下失敗（注意，我們已經排除了鍵可能存在於 readOnly對象中的可能性）：

3. 鍵存在於 dirty map 中。

4. 鍵不在 dirty map 中。第 3 部分處理第一種情況。它只是將記錄存儲到 entry 對象中。現在第 4 部分處理以下兩種可能性：

5. dirty map 是 nil

6. dirty map 不是 nil如果 dirty map 是nil，則必須在添加新鍵之前通過從 readOnly對象複製 entry 來創建它。否則，直接添加鍵而不做任何更改。

dirty 映射爲nil 也表示自從它的 dirty map 被提升爲 “乾淨” map 以來，沒有新 entry 被添加到 sync.Map 對象中。因此，如果 dirty 是 nil，則源 5 中的字段 read.amended應該是 false。

在將 dirty map 提升爲乾淨 map 時（這發生在對結構 sync.Map 中定義的 missLocked()的調用時；它僅在Load(...)、LoadOrStore(...)時執行、LoadAndDelete(...) 或 Delete(...) 被調用）它只是被直接複製到 “乾淨” 的 map 中。發生這種情況時，用戶可以自由地同時刪除乾淨 map 中的鍵（這只是一個原子操作）並重新添加它們。但是在升級後第一次嘗試將新鍵添加到 map 中時，乾淨映射的內容被複制到髒映射中。但是當發生這種情況時，在其 entry 對象的指針字段中帶有 nil 的鍵被忽略，並且在 “乾淨” map 中，它們被原子地更改爲expunged。

在第 4 部分中，調用了 dirtyLocked() 來填充 dirty 映射。來源 [dirtyLocked()](https://github.com/golang/go/blob/aa4e0f528e1e018e2847decb549cfc5ac07ecf20/src/sync/map.go#L362)

源碼 8：dirtyLocked() — 通過複製可讀 map 的內容創建一個新 map 並將其存儲在 dirty 中

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

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

tryExpungeLocked() 定義如下：

源碼 9：tryExpungeLocked()——如果它是 nil，則用 expunged 更新 entry 的指針

func (e *entry) tryExpungeLocked() (isExpunged bool) {
 p := atomic.LoadPointer(&e.p)
 for p == nil {
  if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
   return true
  }
  p = atomic.LoadPointer(&e.p)
 }
 return p == expunged
}

像源代碼 7 中定義的 tryStore(...) 一樣，源代碼 8 也依賴於一個完全原子的操作來將 expunged 設置爲指針。正如我們在 Source 8 中看到的，新的 dirty map 的創建和最終更新僅在 dirty 爲 nil 時發生。源代碼 8 的第 9 行清楚地表明，只有當 tryExpungeLocked() 失敗時，纔會將鍵添加到 dirty map 中。

tryExpungeLocked() 確保 entry對象中的指針字段設置爲 expunged，如果它最初是 nil（參見源代碼 9 的第 4 行）。如果在比較和交換操作之前修改了指針，則交換失敗並且循環退出。這個循環一直持續到 p 不是 nil。這可能會在執行比較和交換之前從 nil 改變；例如，它可以被一個 goroutine 替換，該 goroutine 執行對 sync.Map 結構中的 Store(...) 方法的調用。

在調用 dirtyLocked() 之後，讀取的 map 被標記爲 “已修改”。這表示 read 字段中的 map 已經失效。

Load(key interface{}) (value interface{}, ok bool):

注意：如果您還沒有閱讀Store(...) 部分，我建議您閱讀。我在那裏使用的推理路線也適用於這裏以及下面解釋的所有其他方法。因此我不會在這裏重新解釋它們。

源代碼 10：Load

// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
 read, _ := m.read.Load().(readOnly)
 e, ok := read.m[key]
 if !ok && read.amended {
  m.mu.Lock()
  // Avoid reporting a spurious miss if m.dirty got promoted while we were
  // blocked on m.mu. (If further loads of the same key will not miss, it's
  // not worth copying the dirty map for this key.)
  read, _ = m.read.Load().(readOnly)
  e, ok = read.m[key]
  if !ok && read.amended {
   e, ok = 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 nil, false
 }
 return e.load()
}

1. 以原子方式檢索 readOnly 對象。

2. 檢查鍵及其 entry 是否存在於其中

3. 如果成功，返回結果。此時，沒有使用鎖。

4. 如果失敗，並且 read.amended 爲真（表示 dirty 字段不是 nil），則從可寫的 map（即 dirty 映射）中讀取該值。

5. 第 4 步在一個由 mu 保護的鎖定區域內運行。源代碼 10 中的第 5、6 和 7 行在第 12、13 和 14 行中再次重複；但這是在鎖定區域內完成的。這樣做是因爲，在此期間，與該鍵關聯的不同 goroutine 可能添加了一個新的 entry 對象。但是所有的寫操作都與鎖同步。因此，這裏不會有任何競爭條件。

6. 如果通過可讀的 map 檢索失敗，則從可寫的 map 中檢索。

LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)

LoadOrStore(…) 的源代碼點擊這裏.

在大多數情況下，LoadOrStore(...) 與 Load(...) 類似，除了它使用 e.tryLoadOrStore(value)代替e.tryLoad() 並且還調用了 missLocked( ...) 如果鍵在可讀的 map 中不存在。

tryLoadOrStore(...) 的實現類似於使用比較和交換指令的任何原子更新策略。只有當 entry 對象持有除 expunged（包括 nil）以外的任何指針時，此方法纔會成功。

LoadAndDelete(key interface{}) (value interface{}, loaded bool):

跟隨的策略 與上面提到的策略並不是很獨特。第一次讀取嘗試使用 readOnly 對象。如果成功，e.delete() 被調用，它以原子方式將 entry 對象的指針設置爲 nil。如果失敗，則從鎖定區域內的 dirty map 中檢索 entry 對象。如果 dirty 映射有鍵，就會調用 e.delete()。The key is not removed at this point. It is just set to nil. 此時未移除鍵。它只是設置爲 nil。

Delete()(value interface{}, ok bool):

內部調用 LoadAndDelete(…)

Range(f func(key, value interface{}) bool)

1. 首先嚐試從 readOnly 對象中檢索密鑰

2. 如果成功，則立即使用返回的對象計算範圍循環（從 源碼) 中的第 341 行到 349 行）。

3. 如果失敗，則在 line 325 處檢查, 查看 sync.Map 對象是否通過在最近的 dirty map 升級後使用附加鍵對其進行擴展來 “修改”。

4. 如果在 line 325 處檢查成功，則立即提升dirtymap。這樣做是因爲，假設訪問了所有鍵，範圍操作最有可能是 O(N)。因此，在提升 dirty 映射並將 dirty 設置爲 nil 之後，我們可以期待接下來的存儲操作（引入新鍵的 Store(...) 或 LoadOrStore(...)）遵循創建新的 dirty map 的緩慢路徑，這是一個 O(N) 操作。但是調用 Range(...) 本身就是一個 O(N) 操作，在 O(N) 操作創建一個新的 dirty map 之前確保 O(N) 操作（創建一個新的dirty map）只跟在另一個 O(N) 操作之後。因此我們可以將它們攤銷爲一個 O(N) 操作

5. 在步驟 4 之後，執行範圍操作。

sync.Map 和 RWMutex 保護的 map 之間的性能對比。快速優化指南

這篇文章（go 中的新成員 -- sync.Map by Ralph Caraveo III) 詳細說明了當我們僅使用幾個核心處理器時，簡單的 sync.RWMutex保護 map 如何比 sync.Map 性能更好。文章中的基準測試表明，超過 4 個內核，sync.Map 的性能似乎明顯高於由 sync.RWMutex保護的 map。

因此，有必要構建一個原型，稍後可以對其進行基準測試，以測試其實現的每個變體的相對性能。這可以幫助我們選擇最適合每種情況的變體。這與深度神經網絡的工作方式有相似之處。在 DNN 中，我們有一個損失函數，我們試圖將其值最小化。這種情況下的損失函數表達了神經網絡模型的目標。

同樣，應用程序必須將它們的測試用例和基準一起視爲表達整個項目目標的 “損失函數”。如果你衡量績效，及時你可以改進它。因爲，你無法調整你沒有衡量的東西。

當您優化的內容沒有提高應用程序的整體性能，或者性能的變化太小可以忽略不計時，過早的優化確實會成爲一個問題。

讓我們看一個例子：

假設您有一個應用程序，它應該通過 API 調用接收配置文件信息以及特定的元數據，將其轉換爲不同的格式並將它們發送到不同的微服務。假設您編寫了一個過程來過濾正在讀取的數據中的特定模式 - 假設您收到客戶資料數據，並且您的應用程序應該過濾超過 8 年的資料並將其 ID 發送到不同的消息隊列，同時還存儲緩存中的配置文件。

你應該使用sync.Map 還是使用 sync.RWMutex 保護的 map？

假設在應用程序收到的每 100 個配置文件數據中，其中一個是 8 年前的。那麼你真的應該考慮使用哪種類型的 map 嗎？這些選擇中的任何一個在這裏都沒有區別，因爲您的選擇通常不會損害系統的整體性能。也許是因爲這個緩存不是最慢的一步。

當我們以一個團隊的方式工作時，讓不同的人處理不同的任務很常見。因此，讓人們通過使用本地化基準測試使他們的代碼部分運行得更快，您不會從中受益。基準測試必須反映應用程序的總體目標。

如果它不是真正的瓶頸，那麼任何用於提高部分代碼庫性能的工作都將被浪費掉。但是當您編寫一個大多數功能都向用戶公開的庫時，情況就有些不同了。在應用程序級別（包括公開的 API）編寫基準測試有助於設定團隊希望實現的目標。

如果閱讀這篇文章給你的印象是 Go 作者過早地優化，我不得不說，那不是真的。Go 是一種通用語言，我相信即使是它的作者也無法完全預測它的所有用例。但是他們總是有可能找出最常見的用例併爲此進行優化。他們的首要任務應該是調整對其生態系統影響最大的部分。爲此，他們絕對需要來自所有用戶的非常嚴格的反饋循環。他們的主要重點應該是解決痛點。

極致的優化是什麼樣的？由於我之前提到的原因，實際上並不需要將應用程序中的性能提高到某一點。也就是說，如果您確實希望出於某種原因使您的應用程序超快，那麼請繼續閱讀！

SQL 數據庫系統竭盡全力使事情運行得更快。他們通過爲同一任務實施多個 “策略” 來做到這一點。當您查詢未編入索引的記錄時，您將觀察到最壞情況的性能。當查詢引擎回退到使用暴力搜索時，就會發生這種情況。

但是如果您建立了索引，查詢引擎就有機會選擇更好的算法（僅引用索引）來提高查詢執行時間。“查詢計劃” 階段負責確定要使用的正確策略。如果您構建了多個索引，那麼您實際上是在爲查詢引擎提供太多可供選擇的選項和策略。在這種情況下，它甚至可能依靠執行統計來選擇最佳策略以供內部使用。

同樣，如果您想要一個 super fast 併發 map，以下內容可能會有所幫助：

源代碼 11：超高效同步 map

import (
  "sync"
)

// RWMutexMap is an implementation of mapInterface using a sync.RWMutex.
type RWMutexMap struct {
 mu    sync.RWMutex
 dirty map[interface{}]interface{}
}

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

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

func (m *RWMutexMap) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
 m.mu.Lock()
 actual, loaded = m.dirty[key]
 if !loaded {
  actual = value
  if m.dirty == nil {
   m.dirty = make(map[interface{}]interface{})
  }
  m.dirty[key] = value
 }
 m.mu.Unlock()
 return actual, loaded
}

func (m *RWMutexMap) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
 m.mu.Lock()
 value, loaded = m.dirty[key]
 if !loaded {
  m.mu.Unlock()
  return nil, false
 }
 delete(m.dirty, key)
 m.mu.Unlock()
 return value, loaded
}

func (m *RWMutexMap) Delete(key interface{}) {
 m.mu.Lock()
 delete(m.dirty, key)
 m.mu.Unlock()
}

func (m *RWMutexMap) Range(f func(key, value interface{}) (shouldContinue bool)) {
 m.mu.RLock()
 keys := make([]interface{}, 0, len(m.dirty))
 for k := range m.dirty {
  keys = append(keys, k)
 }
 m.mu.RUnlock()

 for _, k := range keys {
  v, ok := m.Load(k)
  if !ok {
   continue
  }
  if !f(k, v) {
   break
  }
 }
}

// MapInterface is the interface Map implements.
type MapInterface interface {
 Load(interface{}) (interface{}, bool)
 Store(key, value interface{})
 LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)
 LoadAndDelete(key interface{}) (value interface{}, loaded bool)
 Delete(interface{})
 Range(func(key, value interface{}) (shouldContinue bool))
}

func NewSuperEfficientSyncMap(numOfCores int) MapInterface {
  if numOfCores == 0 {
    numOfCores = GOMAXPROCS(0)
  }
  
  // Or this could include more complex logic with multiple 
  // strategies.
  
  if numOfCores > 4 {
    return sync.Map{}
  }
  
  return RWMutexMap{}
}

策略模式幾乎可以在任何地方使用，讓應用程序的不同部分可以對其性能進行巨大的控制。您還可以編寫模塊來記下統計信息併爲您的應用程序設計正確的策略，更像是查詢計劃器的工作方式。

這樣，您的應用程序將爲每個環境使用一組不同的策略！如果您的客戶關心性能並且您支持廣泛的平臺，這將非常有用。或者，如果您正在構建一種語言，它將最有用。

也就是說，如果您清楚團隊的目標，總是可以避免過早優化。如果沒有嚴格的目標，您就無法真正知道什麼是 “優化”。

• 原文地址：https://github.blog/2021-07-22-github-supply-chain-security-features-go-community/

• 原文作者：William Bartholomew

• 本文永久鏈接：https://github.com/gocn/translator/blob/master/2021/w28_GitHub_brings_supply_chain_security_features_to_the_Go_community.md

• 譯者：朱亞光

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