Golang中sync.Map的實現(xiàn)原理是什么

這篇文章給大家介紹 Golang中sync.Map的實現(xiàn)原理是什么，內(nèi)容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

簡介

Go 的內(nèi)建 map 是不支持并發(fā)寫操作的，原因是 map 寫操作不是并發(fā)安全的，當你嘗試多個 Goroutine 操作同一個 map，會產(chǎn)生報錯：fatal error: concurrent map writes。

因此官方另外引入了 sync.Map 來滿足并發(fā)編程中的應用。

sync.Map 的實現(xiàn)原理可概括為：

• 通過 read 和 dirty 兩個字段將讀寫分離，讀的數(shù)據(jù)存在只讀字段 read 上，將最新寫入的數(shù)據(jù)則存在 dirty 字段上

• 讀取時會先查詢 read，不存在再查詢 dirty，寫入時則只寫入 dirty

• 讀取 read 并不需要加鎖，而讀或?qū)?dirty 都需要加鎖

• 另外有 misses 字段來統(tǒng)計 read 被穿透的次數(shù)（被穿透指需要讀 dirty 的情況），超過一定次數(shù)則將 dirty 數(shù)據(jù)同步到 read 上

• 對于刪除數(shù)據(jù)則直接通過標記來延遲刪除

數(shù)據(jù)結構

Map 的數(shù)據(jù)結構如下：

type Map struct {
    // 加鎖作用，保護 dirty 字段
    mu Mutex
    // 只讀的數(shù)據(jù)，實際數(shù)據(jù)類型為 readOnly
    read atomic.Value
    // 最新寫入的數(shù)據(jù)
    dirty map[interface{}]*entry
    // 計數(shù)器，每次需要讀 dirty 則 +1
    misses int
}

其中 readOnly 的數(shù)據(jù)結構為：

type readOnly struct {
    // 內(nèi)建 map
    m  map[interface{}]*entry
    // 表示 dirty 里存在 read 里沒有的 key，通過該字段決定是否加鎖讀 dirty
    amended bool
}

entry 數(shù)據(jù)結構則用于存儲值的指針：

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

屬性 p 有三種狀態(tài)：

• p == nil: 鍵值已經(jīng)被刪除，且 m.dirty == nil

• p == expunged: 鍵值已經(jīng)被刪除，但 m.dirty!=nil 且 m.dirty 不存在該鍵值（expunged 實際是空接口指針）

• 除以上情況，則鍵值對存在，存在于 m.read.m 中，如果 m.dirty!=nil 則也存在于 m.dirty

Map 常用的有以下方法：

• Load：讀取指定 key 返回 value

• Store： 存儲（增或改）key-value

• Delete： 刪除指定 key

源碼解析

Load

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先嘗試從 read 中讀取 readOnly 對象
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]

    // 如果不存在則嘗試從 dirty 中獲取
    if !ok && read.amended {
        m.mu.Lock()
        // 由于上面 read 獲取沒有加鎖，為了安全再檢查一次
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]

        // 確實不存在則從 dirty 獲取
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // 調(diào)用 miss 的邏輯
            m.missLocked()
        }
        m.mu.Unlock()
    }

    if !ok {
        return nil, false
    }
    // 從 entry.p 讀取值
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    // 當 miss 積累過多，會將 dirty 存入 read，然后 將 amended = false，且 m.dirty = nil
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

Store

func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    // 如果 read 里存在，則嘗試存到 entry 里
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    // 如果上一步?jīng)]執(zhí)行成功，則要分情況處理
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    // 和 Load 一樣，重新從 read 獲取一次
    if e, ok := read.m[key]; ok {
        // 情況 1：read 里存在
        if e.unexpungeLocked() {
            // 如果 p == expunged，則需要先將 entry 賦值給 dirty（因為 expunged 數(shù)據(jù)不會留在 dirty）
            m.dirty[key] = e
        }
        // 用值更新 entry
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        // 情況 2：read 里不存在，但 dirty 里存在，則用值更新 entry
        e.storeLocked(&value)
    } else {
        // 情況 3：read 和 dirty 里都不存在
        if !read.amended {
            // 如果 amended == false，則調(diào)用 dirtyLocked 將 read 拷貝到 dirty（除了被標記刪除的數(shù)據(jù)）
            m.dirtyLocked()
            // 然后將 amended 改為 true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // 將新的鍵值存入 dirty
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

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
        }
    }
}

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))
}

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 {
        // 判斷 entry 是否被刪除，否則就存到 dirty 中
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        // 如果有 p == nil（即鍵值對被 delete），則會在這個時機被置為 expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

Delete

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

// LoadAndDelete 作用等同于 Delete，并且會返回值與是否存在
func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
    // 獲取邏輯和 Load 類似，read 不存在則查詢 dirty
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !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()
    }
    // 查詢到 entry 后執(zhí)行刪除
    if ok {
        // 將 entry.p 標記為 nil，數(shù)據(jù)并沒有實際刪除
        // 真正刪除數(shù)據(jù)并被被置為 expunged，是在 Store 的 tryExpungeLocked 中
        return e.delete()
    }
    return nil, false
}

總結

可見，通過這種讀寫分離的設計，解決了并發(fā)情況的寫入安全，又使讀取速度在大部分情況可以接近內(nèi)建 map，非常適合讀多寫少的情況。

sync.Map 還有一些其他方法：

• Range：遍歷所有鍵值對，參數(shù)是回調(diào)函數(shù)

• LoadOrStore：讀取數(shù)據(jù)，若不存在則保存再讀取

關于 Golang中sync.Map的實現(xiàn)原理是什么就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。