Sync.Map
原理
- 通過 read 和 dirty 兩個字段實現數據的讀寫分離，讀的數據存在只讀字段 read 上，將最新寫入的數據存在 dirty 字段上。
- 讀取時會先查詢 read，不存在再查詢 dirty，寫入時則只寫入 dirty。
- 讀取 read 并不需要加鎖，而讀或寫 dirty 則需要加鎖。
- misses 字段來統計 read 被穿透的次數（被穿透指需要讀 dirty 的情況），超過一定次數則將 dirty 數據更新到 read 中（觸發條件：misses=len(dirty)）。
優缺點
- 優點：通過讀寫分離，降低鎖時間來提高效率。
- 缺點：不適用于大量寫的場景，這樣會導致 read map 讀不到數據而進一步加鎖讀取，同時dirty map也會一直晉升為read map，整體性能較差，甚至沒有單純的 map+metux 高。
- 適用場景：讀多寫少的場景。
Sync.Map 數據結構
type Map struct {mu Mutexread atomic.Value // readOnly// 包含需要加鎖才能訪問的元素// 包括所有在read字段中但未被expunged（刪除）的元素以及新加的元素dirty map[any]*entry// 記錄從read中讀取miss的次數，一旦miss數和dirty長度一樣了，就會把dirty提升為read misses int
}// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {m map[any]*entryamended bool // true if the dirty map contains some key not in m.
}// expunged is an arbitrary pointer that marks entries which have been deleted
// from the dirty map.
var expunged = unsafe.Pointer(new(any))// An entry is a slot in the map corresponding to a particular key.
type entry struct {p unsafe.Pointer // *interface{}
}
Sync.Map 操作
Store
// Store sets the value for a key.
func (m *Map) Store(key, value any) {// 判斷 read 有沒有包含這個 key，有則 cas 更新read, _ := m.read.Load().(readOnly)if e, ok := read.m[key]; ok && e.tryStore(&value) {return}// read 沒有，需要加鎖訪問 dirtym.mu.Lock()read, _ = m.read.Load().(readOnly)// 雙重檢查，在查一下 read 里面有沒有（包含標記刪除的）if e, ok := read.m[key]; ok {// 之前被標記為刪除，重新加入 dirtyif 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)} else if e, ok := m.dirty[key]; ok {e.storeLocked(&value)} 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.// 創建一個新的 dirty，遍歷 read，將沒有標記刪除的加入m.dirtyLocked()m.read.Store(readOnly{m: read.m, amended: true})}m.dirty[key] = newEntry(value)}m.mu.Unlock()
}func (m *Map) dirtyLocked() {if m.dirty != nil {return}read, _ := m.read.Load().(readOnly)m.dirty = make(map[any]*entry, len(read.m))for k, e := range read.m {if !e.tryExpungeLocked() {m.dirty[k] = e}}
}
Store 是 新增/修改 操作：
- read 里面有，直接 cas 更新。
- read 沒有，加鎖。
- 再次檢查 read，有已經標記刪除的，重用，并更新 value。
- dirty 有，直接更新。
- dirty 沒有，新增一個。如果 dirty 為 nil，創建一個 dirty，遍歷 read 將元素加入 dirty。
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 any) (value any, ok bool) {// 先從 read 獲取read, _ := m.read.Load().(readOnly)e, ok := read.m[key]// dirty 中有包含 read 中沒有的元素if !ok && read.amended {// 加鎖，雙檢查 read，read 中沒有，從 dirty 中獲取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.// miss++m.missLocked()}m.mu.Unlock()}if !ok {return nil, false}return e.load()
}func (m *Map) missLocked() {m.misses++if m.misses < len(m.dirty) {return}// dirty 提升為 readm.read.Store(readOnly{m: m.dirty})// dirty 置為 nilm.dirty = nilm.misses = 0
}
Load 是 讀取 操作：
- 從 read 中獲取，有則直接返回。
- read 中沒有，加鎖
- 雙檢查 read， read 有，賦值。
- read 沒有，從 dirty 中獲取，不管 dirty 中有沒有，miss++
當miss == len(dirty)，dirty 提升為 read 字段，清空 dirty。
Delete
// Delete deletes the value for a key.
func (m *Map) Delete(key any) {m.LoadAndDelete(key)
}// 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 any) (value any, loaded bool) {// 從 read 中獲取read, _ := m.read.Load().(readOnly)e, ok := read.m[key]if !ok && read.amended {// 加鎖，雙重檢查 readm.mu.Lock()read, _ = m.read.Load().(readOnly)e, ok = read.m[key]if !ok && read.amended {// read 沒有，dirty 有，則直接刪除 dirty 的keye, 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 {// 延遲刪除：read 的 entry 標記為刪除，設置為 nilreturn e.delete()}return nil, false
}func (e *entry) delete() (value any, ok bool) {for {p := atomic.LoadPointer(&e.p)if p == nil || p == expunged {return nil, false}if atomic.CompareAndSwapPointer(&e.p, p, nil) {return *(*any)(p), true}}
}
Delete 是 刪除 操作：
- 從 read 中獲取，有則賦值。
- read 沒有，加鎖
- 雙重檢查 read，有則賦值。
- read 沒有，dirty 有，刪除 dirty 中的值，給 entry 賦值，miss++。
- 延遲刪除：read 的 entry 標記為刪除，設置為 nil。
