golang中map的并发 syncmap详解

golang中map当前版本默认直接并发写会报concurrent map writes 错误

在golang中要实现并发读写的话有三种目前通用的方式：

    1. 使用读写锁sync.RWMutex,在读的时候使用读锁，使用的时候如下代码，效率较低：

 

<pre class="has"><code>var counter = struct{ sync.RWMutex //读写锁 m map[string]int }{m: make(map[string]int)} counter.RLock() // 读锁定 n := counter.m["some_key"] counter.RUnlock() unter.Lock()// 写锁定 counter.m["some_key"] counter.Unlock()</code></pre>

    2. 使用golang官方包的syncmap，效率比第一种方式要高。源码在原生包sync.Map，或者github:https://github.com/golang/sync/tree/master/syncmap

    3. 使用其他开源包的concurrentmap，或者自己实现，可以参考java的concurrentmap，使用shard将数据分块，每个锁只针对一个块。

    该文章主要讲syncmap的流程，并在源码中翻译原来注释加入一些中文注释帮助理解，<span style="color:#f33b45;">配合源码食用效果更佳。  </span>

<h1>总述：  </h1>

   

    syncmap是由两个map构成，一个只读readmap，一个写dirtymap。两个map的存储的value都是entry一个指向具体值的指针，如果一个key在read和dirty中同时存在那么修改的时候通过read来<span style="color:#f33b45;">原子修改</span>即可，如果value为nil或者expunged代表被删除。

    在代码里面通过原子操作 循环对比来实现lockfree。在操作read的时候使用的是lockfree的方式，操作dirty的时候需要加锁。

  <span style="color:#f33b45;">  在每次lockfree进入lock之后，由于之前判断情况时候并没有上锁，所以是可能已经改变的，需要再取值判断一次情况。</span>这种情况在整个源码从lockfree到lock时候大量出现。

    

   

<h3>    读取</h3>

    读的时候优先往read中lockfree读，read中读不到的话再往dirytymap 中lock查找，记录未命中次数，当达到一定次数之后将dirtymap中的数据全部复制到read中。

    读取情况如下如下：

<ol><li>如果read中存在，返回结果</li><li>read中没有，dirty没有生成，返回nil，记一次未命中数</li><li>read中没有，返回dirty的结果，记一次为命中数</li><li>未命中数==len(dirty)的话，把read=dirty，dirty=nil</li></ol>

read中没有的意思是指没有对应key，entry指向nil，entry指向expunged

<h3>    存储</h3>

    在存储数据的时候只往dirtymap中写

    存储情况如下：

<ol><li>当read中含有key，并且不为expunged时候，直接更新数据。为expunged说明已经存在dirty，并且该key没有进入dirty，需要走下面的情况更新dirty</li><li>当read中含有key，值为expunged时候，先插入entry到dirty中，然后更新值</li><li>read中不含有，dirty中含有的话，更新dirty</li><li>read中不含有，dirty中不含有，判断是否是dirty还没有生成，没有的话生成dirty，保存数据，已经生成得话直接保存数据</li></ol><h3>    删除</h3>

    删除的话采用滚动删除，流程如下：

<ol><li>dirty还未生成时：从read中将v置为nil</li><li>dirty生成时：从read中复制数据，所有expunged不复制，把所有v为nil的置为expunged然后不复制</li><li>dirty生成后：如果read中含有的话将v置nil,如果不存在的话，从dirty中删除</li></ol>

    从删除的流程中可以看出，当dirty没有生成时候，read中不含有expunged，被删除的数据全部是nil。dirty中不含有expunged的数据。read中会保留上一轮dirty所有的key，只是在复制到dirty的时候nil和expunged的不复制，从而实现滚动删除key

<h2>1.数据结构</h2> <pre class="has"><code> //Map是并发安全的，零Map是空且有效的 type Map struct { mu sync.Mutex //read包含Map的一部分内容，并且不需要持有锁即可以并发访问 //read本身load的时候是安全的，但是装载的时候需要持有锁 //Entries 存储在read中可能没有锁情况下被并发更新，但是更新先前删除的条目需要将条目复制到dirtymap并且用mu锁的情况下更新为未被擦除。     read atomic.Value // readOnly //dirty 包含一部分需要持有锁访问的内容。Dirty map中同时也包含没有被擦去的read entries 来确保快速dirty->read // 如果 dirtymap 是nil的话，下次写的时候从read浅复制来初始化，略过过时条目 dirty map[interface{}]*entry //misses 统计从read最后一次更新后(dirty转read)需要锁才能知道key是否存在 //一旦misses到了一定数量之后就把dirty->read里，下次存数据的时候初始化一个复制出一个新的dirty     misses int } // readOnly是一个不可变的结构，以原子方式存储在Map.read字段中. type readOnly struct {     m map[interface{}]*entry     amended bool // true if the dirty map contains some key not in m. } //expunged 是一个任意指针，用于标记从dirymap已删除的条目 var expunged = unsafe.Pointer(new(interface{})) type entry struct {      // p points to the interface{} value stored for the entry.      //p 指向 value 存在 entry中的interface{}      // If p == nil, the entry has been deleted and m.dirty == nil.      //如果p==nil，entry已经被删除，并且m.dirty==nil（最近一次dirty->read后没有插入操作，尚未未初始化） // If p == expunged, the entry has been deleted, m.dirty != nil, and the entry is missing from m.dirty.      // 如果p==expunged，entry已经被删除，m.dirty!=nil（已经初始化），并且m.dirty中没有这个entry(已经删除) // Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty!= nil, in m.dirty[key]. //否则的话，entry 有效并且记录在 read[key]中，如果dirty不为空的话，也在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.      //entry 可以被删除通过原子替换为nil，当dirty被创建后，原子替换为expunged 并且在dirty中置空      // 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!=expunged 可以通过原子替换更新entry关联值，p==expunged，先设置dirty[key] = e 之后再更新 entry的关联值 p unsafe.Pointer // *interface{} } </code></pre> <h2>2.存储数据</h2> <pre class="has"><code class="language-Go">// Store sets the value for a key. func (m *Map) Store(key, value interface{}) { //原子获取read     read, _ := m.read.Load().(readOnly) //如果read中有，并且没有被擦除的话，直接更新指针 //read中没有，需要插入 //被擦除说明dirty已经初始化，并且部在dirty中，不能直接更新，需要dirty插入 if e, ok := read.m[key]; ok && e.tryStore(&value) {         return     } //上锁流程     m.mu.Lock() //进入lock需要把lockfree中的情况再次判断     read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok { //存在，说明被擦除了，先expunged变为unexpunged(nil或者其他值)，这时候已经可以并发更新了，返回失败的话说明这个时候已经被先前并发程序置为unexpunged了，同时意味着dirty中加入了entry         if e.unexpungeLocked() { //把dirty中加入entry             m.dirty[key] = e         } //entry赋值         e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { //read中没有，dirty中有的话直接替换entry值即可         e.storeLocked(&value) } else { //如果read的修订标志是false的话，需要初始化dirtymap         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. //初始化dirtymap             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. // 尝试存储value，如果entry还没被擦除的话。如果已经被擦除的话返回false，值不变。被擦除的话再，插入需要插入到dirty，否则的话直接更新e.p即可，dirty持有的是指针 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         }     } } // unexpungeLocked 确保entry不是expunged,在mu解锁之前要保证entry被加入到dirty中，返回false的话说明已经不是expunged(已经初始化dirtymap) 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)) } //初始化dirtymap 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 { //已经为expunged，为nil的话换为expunged，这两种情况不复制进dirty         if !e.tryExpungeLocked() {             m.dirty[k] = e         }     } } //如果为expunged或者nil返回true,并且把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 }</code></pre> <h2>3.读取数据</h2> <pre class="has"><code class="language-Go">// 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 interface{}) (value interface{}, ok bool) { //原子加载只读     read, _ := m.read.Load().(readOnly) e, ok := read.m[key] //如果read中没有并且dirtymap已经被初始化的话，从dirtymap中找     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.)         read, _ = m.read.Load().(readOnly)         e, ok = read.m[key] //重新判断，因为在锁前read可能已经经历过一轮变化         if !ok && read.amended {   e, ok = m.dirty[key] //无论条目是否存在，记录一次未命中，miss次数和>=len(dirty)的话，将dirty提升为read             m.missLocked()         }         m.mu.Unlock()     }     if !ok {         return nil, false     }     return e.load() } //无论条目是否存在，记录一次未命中，miss次数和>=len(dirty)的话，将dirty提升为read 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 }</code></pre> <h2>4.删除代码</h2> <pre class="has"><code class="language-Go">// Delete deletes the value for a key. func (m *Map) Delete(key interface{}) {     read, _ := m.read.Load().(readOnly)     e, ok := read.m[key] //如果不存在，并且dirty已经加载的话删除dirty中的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         }         if atomic.CompareAndSwapPointer(&e.p, p, nil) {             return true         }     } }</code></pre> <h2>5.Range和LoadOrStore</h2>

LoadOrStore：如果有数据的话返回，没有的话存储，总体思路和上面差不多

Range：遍历，如果dirty有的话加锁便利dirty，如果dirty没有的话遍历read

<h2> </h2>

 

如果有没有表达清楚或者有误的地方欢迎斧正，码字不易，要是对您有所帮助的话还请点个赞

 

到此这篇关于“golang中map的并发 syncmap详解”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
通过实例深入理解sync.Map的工作原理
golang中map的并发 syncmap详解
golang map 详解
golang map 锁_golang中线程安全的map
Golang的map并发安全
golang 并发访问map遇到的问题
Golang从入门到放弃200618--Map(1)Map的初始化和基本操作
golang map中结构体元素是无法取地址的
golang map 锁_Golang线程安全的map
golang key map 所有_谨慎使用golang中的map