面試題：

• 為什么map不能并發(fā)讀寫？
• map 并發(fā)讀寫會(huì)panic嗎？
• 為什么sync.Map 沒有l(wèi)en方法？
• map + lock 和 sync.Map 差別在哪里？

map

結(jié)構(gòu)圖

image.png

image.png

sync .Map

源碼分析

package sync

import (
    "sync/atomic"
    "unsafe"
)

/*
大概思想：
readMap 相當(dāng)于 是 dirtyMap的緩存
每次增加新的key都是加鎖然后存到dirtyMap，
每次讀取數(shù)據(jù)的時(shí)候每次都是去無(wú)鎖讀readMap，如果readMap沒有讀到，miss+1，
miss達(dá)到一個(gè)數(shù)字后，就把dirtyMap設(shè)置為readMap，
接下來(lái)存新的數(shù)據(jù)的時(shí)候，又會(huì)遍歷readMap把當(dāng)前有效的數(shù)據(jù)，存到dirtyMap，然后把新的數(shù)據(jù)存到dirtyMap，如此往復(fù)
*/

type Map struct {
    // 鎖（對(duì)dirtyMap操作的時(shí)候會(huì)使用）
    mu Mutex
    // read是個(gè)原子變量，在read里面的值是能夠并發(fā)修改的 ，其實(shí)read相當(dāng)于是dirtyMap的緩存
    read atomic.Value // readOnly
    // 加鎖進(jìn)行操作，和read構(gòu)成冗余，misses達(dá)到len(dirty)后升級(jí)為read
    dirty map[interface{}]*entry
    // 查詢沒有命中read的次數(shù)
    misses int
}

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    m       map[interface{}]*entry
    amended bool // 是否有新數(shù)據(jù)寫入dirty
}

// 來(lái)代替被刪除的占位符
var expunged = unsafe.Pointer(new(interface{}))

// entry： 用于保存value的interface指針,通過(guò)atomic進(jìn)行原子操作
type entry struct {
    // p points to the interface{} value stored for the entry.
    //
    // 這里注釋感覺有問題，如果p == nil 的話 不能說(shuō)明m.dirty == nil
    // If p == nil, the entry has been deleted and m.dirty == nil.
    //
    // 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.
    // 這就是interface{}的指針，能夠被原子操作
    // dirtyMap 和 readMap 的值都指向一個(gè)指針，這樣修改了什么，另一個(gè)也會(huì)跟著變
    p unsafe.Pointer // *interface{}
}

func newEntry(i interface{}) *entry {
    return &entry{p: unsafe.Pointer(&i)}
}

// 從map里面獲得數(shù)據(jù)
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 先把read 轉(zhuǎn)成map
    read, _ := m.read.Load().(readOnly)
    // 先判斷 read 該key是否存在
    e, ok := read.m[key]
    // 如果不存在 且 amended 為true(表示dirtyMap里面有readMap不存在的值)就加鎖,去dirtyMap看看值存不存在
    if !ok && read.amended {
        // 加鎖
        m.mu.Lock()
        // 加鎖成功后，還要判斷一下 read 數(shù)據(jù) ，因?yàn)榭赡茉诩渔i過(guò)程中，dirty 已經(jīng)升級(jí)成read了
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            //  嘗試從dirtyMap里面獲得數(shù)據(jù)
            e, ok = m.dirty[key]
            // 增加未命中次數(shù)，達(dá)到一個(gè)數(shù)字就把 dirty 升級(jí) 為read
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    // 把指針轉(zhuǎn)化為interface的值返回
    return e.load()
}

func (e *entry) load() (value interface{}, ok bool) {
    p := atomic.LoadPointer(&e.p)
    if p == nil || p == expunged {
        return nil, false
    }
    return *(*interface{})(p), true
}

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
    // 把read轉(zhuǎn)化為map
    read, _ := m.read.Load().(readOnly)
    // 如果read里面已經(jīng)存在該key 直接嘗試設(shè)置值 , 這步并不需要加鎖 ，這就很nice
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    // 如果readMap 并沒有找到該key，或者說(shuō)該readMap的值不存在或者被刪除的占位符標(biāo)記了，就需要加鎖操作 dirtyMap了
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    //  double checking，防止在加鎖的時(shí)候 dirty Map 升級(jí)為readMap
    if e, ok := read.m[key]; ok {
        // key在read中被標(biāo)記為expunge刪除的話，相當(dāng)于dirtyMap沒有這個(gè)key的指針 （而且 dirty 肯定不為空只有dirtyMap被同步了才會(huì)有expunged狀態(tài)，
        // 需要插入dirty，并且修改該指針的值
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        // 使用原子操作存儲(chǔ)值
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok { // 看看key值是否已經(jīng)在dirty里面了
        e.storeLocked(&value)
    } else {
        // amended 若為false，則表示dirty未被初始化過(guò)
        if !read.amended {
            // 初始化dirty，將read中未被刪除的有效的數(shù)據(jù)全都復(fù)制到dirty中，read中指向nil的數(shù)據(jù)會(huì)被標(biāo)記為expunged（并且不被同步到dirtyMap）
            m.dirtyLocked()
            // 將amended改為true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // 將值存入dirty
        // 只有dirtyMap 存入了readMap不存在的值，amended才會(huì)為true
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.

// 因?yàn)榇鏀?shù)據(jù)的時(shí)候，必須確保 dirtyMap 也要存入，  如果 p 為 expunged ，說(shuō)明dirtMap 沒有該key的指針，所以不能直接存，所以返回false
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
        }
    }
}

// unexpungeLocked ensures that the entry is not marked as expunged.
//
// If the entry was previously expunged, it must be added to the dirty map
// before m.mu is unlocked.
func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// storeLocked unconditionally stores a value to the entry.
//
// The entry must be known not to be expunged.
func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

// 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) {
    // Avoid locking if it's a clean hit.
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        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 {
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        actual, loaded, _ = e.tryLoadOrStore(value)
    } else if e, ok := m.dirty[key]; ok {
        actual, loaded, _ = e.tryLoadOrStore(value)
        m.missLocked()
    } 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)
        actual, loaded = value, false
    }
    m.mu.Unlock()

    return actual, loaded
}

// tryLoadOrStore atomically loads or stores a value if the entry is not
// expunged.
//
// If the entry is expunged, tryLoadOrStore leaves the entry unchanged and
// returns with ok==false.
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
    p := atomic.LoadPointer(&e.p)
    if p == expunged {
        return nil, false, false
    }
    if p != nil {
        return *(*interface{})(p), true, true
    }

    // Copy the interface after the first load to make this method more amenable
    // to escape analysis: if we hit the "load" path or the entry is expunged, we
    // shouldn't bother heap-allocating.
    ic := i
    for {
        if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
            return i, false, true
        }
        p = atomic.LoadPointer(&e.p)
        if p == expunged {
            return nil, false, false
        }
        if p != nil {
            return *(*interface{})(p), true, true
        }
    }
}

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
    // 把read轉(zhuǎn)成結(jié)構(gòu)體
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    //不在read中，且dirty中有新數(shù)據(jù)
    if !ok && read.amended {
        m.mu.Lock()
        // 第二次嘗試讀，防止加鎖中發(fā)生了變化， 比如dirty map 升級(jí)為 read map了
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            // 如果read里面還是沒有，而且dirty還有別的數(shù)據(jù)，就對(duì)dirty進(jìn)行刪除一下（不管dirtyMap里面有沒有這個(gè)值，反正刪就完了）
            delete(m.dirty, key)
        }
        m.mu.Unlock()
    }
    if ok {
        // read中存在key，將這個(gè)key標(biāo)記為刪除狀態(tài)，但并不刪除數(shù)據(jù)
        e.delete()
    }
}

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

// 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) {
    // We need to be able to iterate over all of the keys that were already
    // present at the start of the call to Range.
    // If read.amended is false, then read.m satisfies that property without
    // requiring us to hold m.mu for a long time.
    read, _ := m.read.Load().(readOnly)
    if read.amended {
        // m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
        // (assuming the caller does not break out early), so a call to Range
        // amortizes an entire copy of the map: we can promote the dirty copy
        // immediately!
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        if read.amended {
            read = readOnly{m: m.dirty}
            m.read.Store(read)
            m.dirty = nil
            m.misses = 0
        }
        m.mu.Unlock()
    }

    for k, e := range read.m {
        v, ok := e.load()
        if !ok {
            continue
        }
        if !f(k, v) {
            break
        }
    }
}

// 如果沒有命中一定次數(shù)就把 dirtyMap 升級(jí)為readMap 然后把原來(lái)的 dirtyMap 設(shè)置為空
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    // 這里可以看到dirty剛升級(jí)到read，amended是false的 ,amended 只有在 dirtyMap 包含readMap不存在的key的時(shí)候才會(huì)為true
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

// 把readMap的有效的數(shù)據(jù)同步到dirtyMap中
func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }

    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    // 遍歷readMap的所有的值，然后把readMap中有效值賦值到dirtyMap。readMap值為nil的對(duì)象改成expunged，
    // 這相當(dāng)于是一個(gè)標(biāo)記，如果readMap中有值為expunged，就說(shuō)明，當(dāng)前dirtyMap 已經(jīng)被初始化了，并且dirtyMap不存在這個(gè)key
    for k, e := range read.m {
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

// 把nil的改為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
}

存儲(chǔ)過(guò)程圖解

image.png

結(jié)論：

map 之所以不能并發(fā)存儲(chǔ)，是因?yàn)樵诓l(fā)存新的key的時(shí)候，可能會(huì)hash到同一個(gè)槽上，導(dǎo)致 原來(lái) key1 : val1 ， 和 key2 : val2 變成 key2:val1 的這種非預(yù)期場(chǎng)景，而且在 map 增在bucket的時(shí)候可能造成bucket鏈表出錯(cuò)。
那么如果在 不增加新key的情況下，map 并發(fā)讀寫是否是安全的呢？ 答案是安全的，所以 sync.Map 就是利用了這個(gè)特性，減少了 map 加鎖的粒度。更大的提高了map的性能。