Golang中sync.Map的实现原理
发布时间：2022-02-24 编辑：jiaochengji.com
教程集为您提供Golang中sync.Map的实现原理等资源，欢迎您收藏本站，我们将为您提供最新的Golang中sync.Map的实现原理资源
<h1>前言</h1>
<h3>Store方法</h3>
<blockquote>
到此这篇关于“Golang中sync.Map的实现原理”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！
前面，我们讲了map的用法以及原理Golang中map的实现原理，但我们知道，map在并发读写的情况下是不安全。需要并发读写时，一般的做法是加锁，但这样性能并不高，Go语言在 1.9 版本中提供了一种效率较高的并发安全的 sync.Map，今天，我们就来讲讲 sync.Map的用法以及原理
<h1>使用方法</h1> <pre><code class="lang-go hljs">func main() { var m sync.Map //插入 m.Store("1","a") //取值 fmt.Println(m.Load("1")) //删除 m.Delete("1") //循环 m.Range(func(k, v interface{}) bool { fmt.Println(k,v) return true }) } </code></code></pre>sync.Map与map不同，不是以语言原生形态提供，而是在 sync 包下的特殊结构：
<ul><li>无须初始化，直接声明即可。
</li> <li>sync.Map 不能使用 map 的方式进行取值和设置等操作，而是使用 sync.Map 的方法进行调用，Store 表示存储，Load 表示获取，Delete 表示删除。
</li> <li>使用 Range 配合一个回调函数进行遍历操作，通过回调函数返回内部遍历出来的值，Range 参数中回调函数的返回值在需要继续迭代遍历时，返回 true，终止迭代遍历时，返回 false。
</li> </ul><h1>原理</h1> <blockquote>注意：我会把源码中每个方法的作用都注释出来，可以参考注释进行理解。
</blockquote> <h3>数据结构</h3>我们下来看下sync.Map结构体
<blockquote>sync/map.go:Map
</blockquote> <pre><code class="lang-go hljs">// 这里的 Map 是为了两种用例来优化的: // (1) 当某个指定的 key 只会被写入一次，但是会被读取非常多次，例如像不断增长的 caches。 // (2) 当多个 goroutine 分别分布读、写和覆盖不同的 key。 // 这两种场景下，使用 sync.Map，相比普通的 map 配合 Mutex 或 RWMutex，可以大大降低锁的竞争 // Map 的零值是可以使用的空 Map。当 Map 被首次使用之后，就不能再被拷贝了 type Map struct { mu Mutex // read 包含了 map 内容的一部分，是一个只读的结构，所以没有读写冲突 read atomic.Value // readOnly //dirty 包含了 map 中那些在访问时需要持有 mu 的部分内容 //为了确保 dirty map 的元素能够被快速地移动到 read map 中 // 它也包含了那些 read map 中未删除(non-expunged)的项 // expunged 掉的 entries 不会在 dirty map 中存储。被 expunged 的 entry， // 如果要存新值，需要先执行 expunged 逆操作，然后添加到 dirty map，然后再进行更新 //当dirty为空的时候， 比如初始化或者刚提升完，下一次的写操作会复制read字段中未删除的数据到这个数据中。 dirty map[interface{}]*entry //当从Map中读取entry的时候，如果read中不包含这个entry,会尝试从dirty中读取，这个时候会将misses加1， // 当misses累积到 dirty的长度的时候， 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁 misses int } </code></code></pre> <blockquote>sync/map.go:readOnly
</blockquote> <pre><code class="lang-go hljs">//readOnly是原子形式存储在Map.read字段中的不变结构。 type readOnly struct { m map[interface{}]*entry // 如果 dirty map 中包含有不在 m 中的项，那么 amended = true amended bool } </code></code></pre> <blockquote>sync/map.go:entry
</blockquote> <pre><code class="lang-go hljs">//entry 是 map 对应一个特定 key 的槽 type entry struct { // // 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指向为map的interface {} value值。 //如果 p == nil, 那么说明对应的 entry 被删除了，且m.dirty == nil //如果 p == expunged，说明 entry 被删除了，但 m.dirty != nil，且该 entry 在 m.dirty 中不存在 //除此以外，entry 则是合法的值并且在 m.read.m[key] 中存在 // 如果 m.dirty != nil，也会在 m.dirty[key] 中 p unsafe.Pointer // *interface{} } </code></code></pre>结构体之间的关系如下图所示：
在这里插入图片描述
sync/map.go:Store
</blockquote> <pre><code class="lang-go hljs">//为某一个 key 的 value 赋值 func (m *Map) Store(key, value interface{}) { read, _ := m.read.Load().(readOnly) //通过key从read中取出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未被标记为删除 m.dirty[key] = e } //将value地址赋值给entry中的p e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { //key存在dirty中 //直接更新p e.storeLocked(&value) } else { //新值 if !read.amended { //为 dirty map 增加第一个新的 key //将read中为被标记为expunged复制过来给dirty m.dirtyLocked() // 确保已分配它，并将readOnly标记为，即amended=true m.read.Store(readOnly{m: read.m, amended: true}) } //赋值 m.dirty[key] = newEntry(value) } //释放锁 m.mu.Unlock() } </code></code></pre> <blockquote>sync/map.go:tryStore
</blockquote> <pre><code class="lang-go hljs">//更新value func (e *entry) tryStore(i *interface{}) bool { for { p := atomic.LoadPointer(&e.p) //如果p是删除状态 if p == expunged { //返回失败 return false } //否则，cas操作将值更新 if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } } } </code></code></pre> <blockquote>sync/map.go:dirtyLocked
</blockquote> <pre><code class="lang-go hljs">//将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 { if !e.tryExpungeLocked() { m.dirty[k] = e } } } //判断是否被被标记为expunged func (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) // 将已经删除标记为nil的数据标记为expunged for p == nil { if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged } </code></code></pre>总结一下：
<ol><li>判断ready中是否存在该key：如果存在，则直接通过cas操作更新value的值</li> <li>通过mu.Lock()加锁，判断key的位置： <ol><li>如果key存在ready中，且未被标记expunged（删除），更新ready中key对应的value值</li> <li>如果key存在dirty中，更新dirty中key对应的value值</li> <li>否则，key为新值。将ready中未删除的值全部赋值给dirty，并将key新值赋值给dirty</li> </ol></li> <li>最后，释放锁，结束赋值过程</li> </ol><h3>Load方法</h3> <blockquote>sync/map.go:Load
</blockquote> <pre><code class="lang-go hljs">//查询 func (m *Map) Load(key interface{}) (value interface{}, ok bool) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] //如果key不在ready中 //且存在dirty中 if !ok && read.amended { //加锁 //说明需要去dirty中寻找 m.mu.Lock() //双重校验，防止在加锁区间，m.dirty提升为m.read read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] //misses //同时判断misses是否超过dirty的length //如果超过，则将dirty整个结构体赋给ready，同时将dirty=nil，misses=0 m.missLocked() } //释放锁 m.mu.Unlock() } //如果ready和dirty都不存在，返回false if !ok { return nil, false } //否则，就是存在ready中，则直接返回val return e.load() } </code></code></pre> <blockquote>sync/map.go:missLocked
</blockquote> <pre><code class="lang-go hljs">func (m *Map) missLocked() { m.misses if m.misses < len(m.dirty) { return } //直接将结构体赋给read，不用一个一个值赋值，速度更快 m.read.Store(readOnly{m: m.dirty}) //清0 m.dirty = nil m.misses = 0 } </code></code></pre> <blockquote>sync/map.go:load
</blockquote> <pre><code class="lang-go hljs">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 } </code></code></pre>Load方法比较简单，总结一下：
<ol><li>如果key不存在ready中，且存在dirty中，则需要加锁，同时再次确认该key是不存在ready，但存在dirty中（双重校验，防止加锁区间，m.dirty提升为m.read）。从dirty中获取值，同时，misses加1，并且判断是否满足m.dirty提升为m.read的条件，最后，释放锁</li> <li>如果key即不存在于ready中，也不存在于dirty中，则直接返回false和nil值</li> <li>最后，key存在ready中，直接去ready中未被删除的值中寻找</li> </ol><h3>Delete方法</h3> <blockquote>sync/map.go:Delete
</blockquote> <pre><code class="lang-go hljs">func (m *Map) Delete(key interface{}) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] //存在dirty中 if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] //同上，双重校验 if !ok && read.amended { //调用map的内置函数，直接删除 delete(m.dirty, key) } m.mu.Unlock() } //存放在ready中 if ok { e.delete() } } </code></code></pre> <blockquote>sync/map.go:delete
</blockquote> <pre><code class="lang-go hljs">func (e *entry) delete() (hadValue bool) { for { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return false } //将值变为nil if atomic.CompareAndSwapPointer(&e.p, p, nil) { return true } } } </code></code></pre>总结如下：
<ol><li>key存在dirty中，则加锁并进行双重检验，然后通过map的内置函数delete删除</li> <li>key存在ready中，则将value的地址变为nil</li> </ol><h1>总结</h1> <ul><li>sync.Map采用空间换时间的思想， 通过冗余的两个数据结构(read、dirty),减少加锁对性能的影响</li> <li>使用只读数据(read)，避免读写冲突</li> <li>优先从read读取、更新、删除，因为对read的读取不需要锁</li> <li>采用了延迟删除，删除一个键值只是打标记（会将key对应value的pointer置为nil，但read中仍然有这个key:key;value:nil的键值对），只有在提升dirty的时候才清理删除的数据</li> </ul>到此这篇关于“Golang中sync.Map的实现原理”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！
您可能感兴趣的文章：
通过实例深入理解sync.Map的工作原理
golang key map 所有_golang系列——高级语法之map
golang map 锁_Golang线程安全的map
golang map 锁_golang中线程安全的map
Golang map线程安全实现及sync.map使用及原理解析。
go二维map_Golang使用Map的正确姿势
Golang中sync.Map的实现原理
踩了 Golang sync.Map 的一个坑
golang map并发读写问题踩坑记录 `concurrent map read and map write`
golang key map 所有_谨慎使用golang中的map
[关闭]