????golang 線程安全的 Map

作者水平有限,而并發博大精深. 如文章中有任何錯誤, 希望讀者不吝指出.謝謝!

章節目錄

Map 基本類型定義

Store

Load

Delete

Range

Map 基本類型定義##

Map

這里我們先看一下 Map 都涉及到那些類型.

type Map struct {// 互斥鎖. 用于互斥的讀寫 dirty.mu Mutex// 值得聲明的一點, read 和 dirty 中的 entry 是同一個.read atomic.Value // 該屬性的實際類型為 readOnly 類型.dirty map[interface{}]*entrymisses int }

readOnly

type readOnly struct {m map[interface{}]*entryamended bool // 表示 dirty 中是否包含一些不存在于 read 中的 key. }

entry

// 用來表示 Map 中的一個 Value 值. type entry struct {p unsafe.Pointer // *interface{} }

vars

// 當某個 entry 的值為 expunged, 表示該 entry 已經被標記為刪除狀態, 等待被刪除. var expunged = unsafe.Pointer(new(interface{}))

Map : Store()##

Store 流程:

先在 read 中查找相應的 key, 如果該 key 已存在且該 entry 沒有被標記為已刪除, 則更新該 entry 的值并返回.

然后在 dirty 中尋找該 key, 如果該 key 存在于 dirty 中, 則更新該 entry 并返回.

如果 read 和 dirty 中都不包含該 key:
a) 如果當前 read 中包含的 key 和 dirty 中包含的 key 相同且 dirty 不為空, 則將 read 中不為空的 entry 復制到 dirty 中. 并將
b) 將新的 key-value 存在 dirty 中.
這里對于 read 的操作是不需要加鎖的.而對 dirty 的操作是需要加鎖的.
對于 read 的操作不會涉及到添加新的 key, 只是讀取或者更新 entry 的值. 而 entry 是 atomic.Value 類型的, 通過相應的原子操作方法進行,因此不需要加鎖. 而對 dirty 的操作會涉及到往一個普通 map 中添加新的 key-value, 因此需要加鎖.

// 創建一個 entry func newEntry(i interface{}) *entry {return &entry{p: unsafe.Pointer(&i)} }// Map 中的 entry 有兩種合法的狀態 : expunged(被標記為刪除狀態), 正常狀態. // 如果 entry 被標記為刪除狀態, tryStore 返回 false // 否則, 會將 i 保存到 map 中, tryStore 返回 truefunc (e *entry) tryStore(i *interface{}) bool {p := atomic.LoadPointer(&e.p)if p == expunged {return false}for {// 使用 CAS 設置 entry 的值. 如果設置成功, 返回 trueif atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {return true}// 這里的理解有待進一步驗證.// 在剛剛進入方法 tryStore 時我們取出 entry 的值, 存儲于 p.// 但是有可能在從第一句代碼到使用 CAS 設置 entry 的值期間, // entry.p 被其他線程修改(刪除), 導致 CAS 操作失敗.p = atomic.LoadPointer(&e.p)if p == expunged {return false}} }// 判斷該 entry 的值是否已經被標記為刪除狀態. // 如果該 entry 的值為 expunged, 說明該 entry 的值已經被標記為刪除, 此時將該 entry 置為 nil. func (e *entry) unexpungeLocked() (wasExpunged bool) {return atomic.CompareAndSwapPointer(&e.p, expunged, nil) }func (e *entry) storeLocked(i *interface{}) {atomic.StorePointer(&e.p, unsafe.Pointer(i)) }// 判斷該 entry 的值是否已經被標記為刪除狀態 // 如果該 entry 的值為 nil, 則將該 entry 修改為 expunged. 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 }// 如果 dirty map為空，則把 read 中數據拷貝到 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 {// 將所有的 nil 的 entry 設置為 expunged// 拷貝不為 expunged 的 entryif !e.tryExpungeLocked() {m.dirty[k] = e}} }func (m *Map) Store(key, value interface{}) {read, _ := m.read.Load().(readOnly)// 如果 Map 中相應的 key 已經存在, 且沒有被標記為刪除狀態, // 將 value 寫入, 并返回.if e, ok := read.m[key]; ok && e.tryStore(&value) {return}// 如果 read 中沒有對應的 key, 此時則需要往 dirty 中寫入 key-value.// 注意, 對于 dirty 的操作需要加鎖.m.mu.Lock()// 在獲取鎖期間, 有可能 read 被其他線程修改, // 因此在此檢查 key 是否已經存在于 read 中.read, _ = m.read.Load().(readOnly)//在獲取鎖期間, read 中被存入 key 相關的 entry.if e, ok := read.m[key]; ok {// 如果 entry 被標記為刪除狀態, 刪除原對象, 并寫入新對象 e.if e.unexpungeLocked() { m.dirty[key] = e}// 如果 entry 未被標記為刪除狀態, 說明原先 entry 也是一個合法數據, // 則直接更新該 entry 的值.e.storeLocked(&value)} else if e, ok := m.dirty[key]; ok { // read 中不存在 key, 而 dirty 中存在該 key. // 直接更新該 key 所對應的 entrye.storeLocked(&value)} else { // read 和 dirty 中都不存在該 key.if !read.amended {m.dirtyLocked()m.read.Store(readOnly{m: read.m, amended: true}) // 將 amended 值為true, 標記 dirty 中存在 read 沒有的 key.}m.dirty[key] = newEntry(value)}m.mu.Unlock() }

Map 的方法: Load()##

Load 流程:

先在 read 中查找該 key, 如果找到直接返回.

否則返回在 dirty 中查找該 key 的結果(可能為空), 并增加 misses 的值. 當misses 的值大于 dirty 的長度時, 將 dirty 中數據轉儲于 read 中.(之所以轉存, 是因為訪問 read 不需要鎖).

// 增加 misses 計數. // 在 misses 大于 dirty 長度時, 將 dirty 復制到 read 中. 并清空 dirty, 重置 misses func (m *Map) missLocked() {m.misses++if m.misses < len(m.dirty) {return}m.read.Store(readOnly{m: m.dirty}) // 注意, 這里隱式的將 amended 置為 false.m.dirty = nilm.misses = 0 }// 該方法用來在 Map 中查找與 key 關聯的 value. 未找到, 返回 nil. // ok 返回值表示是否找到相關的 key. func (m *Map) Load(key interface{}) (value interface{}, ok bool) {// 查找 key 時, 總是先在 Map.read 字段中查找. 找到則返回該 value.read, _ := m.read.Load().(readOnly)e, ok := read.m[key]// 如果 read 中不存在該 key, 而 dirty 中存在該 keyif !ok && read.amended {m.mu.Lock()read, _ = m.read.Load().(readOnly)e, ok = read.m[key]if !ok && read.amended {e, ok = m.dirty[key]m.missLocked()}m.mu.Unlock()}if !ok {return nil, false}return e.load() }

Map 的方法: Delete()##

func (e *entry) delete() (hadValue bool) {for {p := atomic.LoadPointer(&e.p)// 如果該元素已經被標記為刪除狀態, 直接返回.if p == nil || p == expunged {return false}// 如果該元素為正常狀態, 則將該 entry 置為 nilif atomic.CompareAndSwapPointer(&e.p, p, nil) {return true}} }func (m *Map) Delete(key interface{}) {read, _ := m.read.Load().(readOnly)e, ok := read.m[key]// read 中不存在該 keyif !ok && read.amended {m.mu.Lock()read, _ = m.read.Load().(readOnly)e, ok = read.m[key]if !ok && read.amended {delete(m.dirty, key)}m.mu.Unlock()}// read 中存在該 keyif ok {e.delete()} }

Map 的方法: Range()##

func (m *Map) Range(f func(key, value interface{}) bool) {read, _ := m.read.Load().(readOnly)// 如果 Map 元素存儲于 dirty 中, 先將數據轉存到 read 中.if read.amended {m.mu.Lock()read, _ = m.read.Load().(readOnly)if read.amended {read = readOnly{m: m.dirty}m.read.Store(read)m.dirty = nilm.misses = 0}m.mu.Unlock()}for k, e := range read.m {v, ok := e.load()if !ok {continue}if !f(k, v) {break}} }

感謝 https://juejin.im/post/5b1b3d785188257d45297d0a 文章作者的分享.

總結

以上是生活随笔為你收集整理的sync.Map 源码学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。