关于golang:golangsyncMap原理

本文次要论述：Load、Store、Delete，更加具体的论述能够参考源码形容（倡议先大体浏览一下 Map 源码）。

空间换工夫。通过冗余的两个数据结构 (read、dirty), 实现加锁对性能的影响。
应用只读数据 (read)，防止读写抵触。
动静调整，miss 次数多了之后，将 dirty 数据晋升为 read。
double-checking。
提早删除。删除一个键值只是打标记（会将 key 对应 value 的 pointer 置为 nil，但 read 中依然有这个 key:key;value:nil 的键值对），只有在晋升 dirty 的时候才清理删除的数据。
优先从 read 读取、更新、删除，因为对 read 的读取不须要锁。
尽管 read 和 dirty 有冗余数据，但这些数据是通过指针指向同一个数据，所以只管 Map 的 value 会很大，然而冗余的空间占用还是无限的。

// Map is a concurrent map with amortized-constant-time loads, stores, and deletes.
// It is safe for multiple goroutines to call a Map's methods concurrently.
//
// It is optimized for use in concurrent loops with keys that are
// stable over time, and either few steady-state stores, or stores
// localized to one goroutine per key.
//
// For use cases that do not share these attributes, it will likely have
// comparable or worse performance and worse type safety than an ordinary
// map paired with a read-write mutex.
//
// The zero Map is valid and empty.
//
// A Map must not be copied after first use.

// 该 Map 是线程平安的，读取，插入，删除也都放弃着常数级的工夫复杂度。// 多个 goroutines 协程同时调用 Map 办法也是线程平安的。该 Map 的零值是无效的，// 并且零值是一个空的 Map。线程平安的 Map 在第一次应用之后，不容许被拷贝。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.
    
     // 一个只读的数据结构，因为只读，所以不会有读写抵触。// 所以从这个数据中读取总是平安的。// 实际上，理论也会更新这个数据的 entries, 如果 entry 是未删除的 (unexpunged), 并不需要加锁。如果 entry 曾经被删除了，须要加锁，以便更新 dirty 数据。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 蕴含的 entries, 它蕴含最新的 entries(包含 read 中未删除的数据, 虽有冗余，然而晋升 dirty 字段为 read 的时候十分快，不必一个一个的复制，而是间接将这个数据结构作为 read 字段的一部分), 有些数据还可能没有挪动到 read 字段中。// 对于 dirty 的操作须要加锁，因为对它的操作可能会有读写竞争。// 当 dirty 为空的时候，比方初始化或者刚晋升完，下一次的写操作会复制 read 字段中未删除的数据到这个数据中。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.
    // 当从 Map 中读取 entry 的时候，如果 read 中不蕴含这个 entry, 会尝试从 dirty 中读取，这个时候会将 misses 加一，// 当 misses 累积到 dirty 的长度的时候，就会将 dirty 晋升为 read, 防止从 dirty 中 miss 太屡次。因为操作 dirty 须要加锁。misses int
}

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {m       map[interface{}]*entry
    // true if the dirty map contains some key not in m.
    // 如果 Map.dirty 有些数据不在中的时候，这个值为 true
    amended bool 
}

// An entry is a slot in the map corresponding to a particular key.
type entry struct {// p points to the interface{} value stored for the entry.
    //
    // 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.

    // p 有三种值：//nil: entry 已被删除了，并且 m.dirty 为 nil
    //expunged: entry 已被删除了，并且 m.dirty 不为 nil，而且这个 entry 不存在于 m.dirty 中
    // 其它：entry 是一个失常的值
    p unsafe.Pointer // *interface{}}

// A Value provides an atomic load and store of a consistently typed value.
// Values can be created as part of other data structures.
// The zero value for a Value returns nil from Load.
// Once Store has been called, a Value must not be copied.
//
// A Value must not be copied after first use.
type Value struct {
    noCopy noCopy

    v interface{}}

下图来自：http://www.jianshu.com/p/43e66dab535b

依据指定的 key, 查找对应的值 value, 如果不存在，通过 ok 反映

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果没找到，并且 m.dirty 中有新数据，须要从 m.dirty 查找，这个时候须要加锁
    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.)
        //double check, 防止加锁的时候 m.dirty 晋升为 m.read, 这个时候 m.read 可能被替换了。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()}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {return}
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

更新或者新增一个 entry

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {read, _ := m.read.Load().(readOnly)
    // 从 read map 中读取 key 胜利并且取出的 entry 尝试存储 value 胜利，间接返回
    if e, ok := read.m[key]; ok && e.tryStore(&value) {return}

    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {if e.unexpungeLocked() {// 确保未被标记成删除，即 e 指向的是非 nil 的
            // The entry was previously expunged, which implies that there is a
            // non-nil dirty map and this entry is not in it.
            //m.dirty 中不存在这个键，所以退出 m.dirty
            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.
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: 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.
func (e *entry) tryStore(i *interface{}) bool {p := atomic.LoadPointer(&e.p)
    if p == expunged {return false}
    for {if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {return true}
        p = atomic.LoadPointer(&e.p)
        if p == expunged {return false}
    }
}


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

func (e *entry) tryExpungeLocked() (isExpunged bool) {p := atomic.LoadPointer(&e.p)
    for p == nil {
         // 将曾经删除标记为 nil 的数据标记为 expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {return true}
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

// 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.

// unexpungeLocked 函数确保了 entry 没有被标记成已被革除。// 如果 entry 先前被革除过了，那么在 mutex 解锁之前，它肯定要被退出到 dirty map 中

// 如果 entry 的 unexpungeLocked 返回为 true，那么就阐明 entry 
// 之前被标记成了 expunged，并通过 CAS 操作胜利把它置为 nil。func (e *entry) unexpungeLocked() (wasExpunged bool) {return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

删除一个键值

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {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 {delete(m.dirty, key)
        }
        m.mu.Unlock()}
    if ok {e.delete()
    }
}

func (e *entry) delete() (hadValue bool) {
    for {p := atomic.LoadPointer(&e.p)
        // 已标记为删除
        if p == nil || p == expunged {return false}
        // 原子操作，e.p 标记为 nil
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {return true}
    }
}

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
}

在 Map Load 办法中调用 e.load() 时，load 办法会辨认该值是否已被删除

本文 map 构造形容局部参考：https://studygolang.com/articles/10511

关于golang:golangsyncMap原理

一、sync Map 包整体构造

导言：

二、根底数据结构

1、Map

2、readOnly

3、entry

4、Value

三、Load

四、Store

五、Delete

六、疑难

1、曾经删除的 key, 再次 Load 的时候，会怎么样？