深度解密 Go 语言中的 sync.map

2020-06-16 17:00:00于海丽

LoadOrStore

这个函数结合了 Load 和 Store 的功能,如果 map 中存在这个 key,那么返回这个 key 对应的 value;否则,将 key-value 存入 map。这在需要先执行 Load 查看某个 key 是否存在,之后再更新此 key 对应的 value 时很有效,因为 LoadOrStore 可以并发执行。

具体的过程不再一一分析了,可参考 Load 和 Store 的源码分析。

Range

Range 的参数是一个函数:

f func(key, value interface{}) bool

由使用者提供实现,Range 将遍历调用时刻 map 中的所有 k-v 对,将它们传给 f 函数,如果 f 返回 false,将停止遍历。

func (m *Map) Range(f func(key, value interface{}) bool) {
	read, _ := m.read.Load().(readOnly)
	if read.amended {
		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
		}
	}
}

当 amended 为 true 时,说明 dirty 中含有 read 中没有的 key,因为 Range 会遍历所有的 key,是一个 O(n) 操作。将 dirty 提升为 read,会将开销分摊开来,所以这里直接就提升了。

之后,遍历 read,取出 entry 中的值,调用 f(k, v)。

其他

关于为何 sync.map 没有 Len 方法,参考资料里给出了 issue,bcmills 认为对于并发的数据结构和非并发的数据结构并不一定要有相同的方法。例如,map 有 Len 方法,sync.map 却不一定要有。就像 sync.map 有 LoadOrStore 方法,map 就没有一样。

有些实现增加了一个计数器,并原子地增加或减少它,以此来表示 sync.map 中元素的个数。但 bcmills 提出这会引入竞争:atomic 并不是 contention-free 的,它只是把竞争下沉到了 CPU 层级。这会给其他不需要 Len 方法的场景带来负担。

总结

sync.map 是线程安全的,读取,插入,删除也都保持着常数级的时间复杂度。 通过读写分离,降低锁时间来提高效率,适用于读多写少的场景。 Range 操作需要提供一个函数,参数是 k,v,返回值是一个布尔值:f func(key, value interface{}) bool。 调用 Load 或 LoadOrStore 函数时,如果在 read 中没有找到 key,则会将 misses 值原子地增加 1,当 misses 增加到和 dirty 的长度相等时,会将 dirty 提升为 read。以期减少“读 miss”。 新写入的 key 会保存到 dirty 中,如果这时 dirty 为 nil,就会先新创建一个 dirty,并将 read 中未被删除的元素拷贝到 dirty。 当 dirty 为 nil 的时候,read 就代表 map 所有的数据;当 dirty 不为 nil 的时候,dirty 才代表 map 所有的数据。

参考资料