Go - sync.Map

[Petelin]

Go - sync.Map

include #56

为什么说map或者slice是线程不安全的？

因为他们内部时间不能保证各个函数是原子操作，并发执行时不能保证函数执行的正确性。
比如

func appendValue(i int) {
	// mu.Lock()
	// defer mu.Unlock()
	s = append(s, i)
	m[strconv.Itoa(i)] = i
	wg.Done()
}

func main() {
	for i := 0; i < 10000; i++ { // 10000个协程同时添加切片
		wg.Add(1)
		go appendValue(i)
	}
	wg.Wait()

	fmt.Println(len(s))
	fmt.Println(len(m))
}

最后的slice里面没有1w个元素，而map根本不允许这样操作，直接报错
fatal error: concurrent map writes

sync.Map 和 map的区别

sync.Map 不是 map + mutex. 大多数时候应该用自己定义的map+mutex或者其他同步机制。
一下两种场景可以使用sync.Map:

1. 读远远多于写和删
2. 不同goroutine, read,write,overwrite的是不想交的keys

[Petelin]

sync.Map设计

type Map struct {
  // 读 map
  read atomic.Value

  // mu 锁
  mu Mutex
  
  // 写map
  dirty map[interface{}]*entry
  
  // 统计读map不命中次数
  misses int
}

读写流程

考虑一个最简单的实现方式：读全部在read,写全部落在dirty。 读的时候统计未命中read的次数（misses），次数过多就把dirty转移到read中。

这样虽然简单，但不是最佳方案，还有很多优化工作可以处理，我们按照增删改查这四个接口来考虑一下还有哪些优化方式。

增

只能通过加锁的方式来进行，没有优化空间。

查

read map 以 atomic.Value的方式存储在Map中，直接通过原子load取出后即可查询。如果没有命中，那么需要加锁查。
加锁查会慢，所以要找合适的实际，把read map同步成最新的。
这里有一个优化： 如果查询不命中的次数太高，sync.Map会把read替换成dirty。这里隐含的意思是：我们要时刻保证dirty是read的超集。

改

先去read进行查询，如果命中，通过原子操作的方式修改entry。避免去dirty修改，减少锁的使用。

上述操作要想达成需要2点保证：

dirty和read都是指向的同一个entry，map[interface{}]*entry的指针地址相同，改写的不是entry指针，而是entry结构体内的内容。这样对read的修改就是对dirty的修改，不会引起读写map不一致。

entry结构体内的内容能够原子的修改，在源码中，entry结构体内存储的是unsafe.Pointer指针（支持atomic操作），通过对p指针的cas操作，完美实现无锁改。

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

func (e *entry) tryStore(i *interface{}) bool {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == expunged { //表示dirty map已删除对应值 返回false 让其更新完dirty map 再更新read map
            return false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {// 直接更新值
            return true
        }
    }
}

删

删除的优化思路和改类似，如果删除一个在read中存在的数据，用nil指针进行标记删除，避免对dirty的修改。

标记删除虽然好用但是有个致命缺点。如果map中的key一直不删除，会导致key不断增大，浪费内存空间。那么如何进行真正的删除呢？

答案是当需要从read中copy数据到dirty时，copy的过程中会遍历read中的数据，如果发现是软删除的数据，就不再复制到dirty中（同时把值设为expunged，代表dirty中没有这个key）。等下次misses达到阈值，会再把dirty转移到read，这样一来一回，key就算真正删除了。

tips:这个逻辑在某些场景下会导致一个严重的bug踩了 Golang sync.Map 的一个坑

看到这里大家可能会有一个疑惑，dirty为什么会从read中copy数据呢，dirty不是read的超集吗？ 上面我们讲了，当read的数据命中率变低时，sync.map会把dirty覆盖到read。

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

覆盖完成后，dirty会被置为nil；等下次需要写dirty时，再从readcopy一份。

总结

以上就是分享的全部内容，源码讲的不多，更多的是自己学习sync.map时的一些理解。可能存在部分错误，欢迎指出哈。末尾再来总结一下sync.map的优化思路：

• 空间换时间。 通过冗余的两个数据结构(read、dirty),实现加锁对性能的影响。
• 优先从read读取、更新、删除，用原子操作代替锁。
• 使用只读数据(read)，提升读性能，使得读不干扰写性能
• read缓存miss次数多了之后，将dirty数据提升为read。 m.misses < len(m.dirty)
• 软删除，删除一个键值只是打标记，只有在read -> dirty的时候才清理删除的数据。