sync之Map

我们都知道map是不并发安全的，通常通过加互斥锁或读写锁进行并发，而官方提供了一个解决方案sync.Map。适用于读多写少的场景，那么它的内部也是通过加锁控制的吗？

一、写时复制(COW)

在Linux程序中，fork（）会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，出于效率考虑，linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。

写时复制技术：内核只为新生成的子进程创建虚拟空间结构，它们来复制于父进程的虚拟究竟结构，但是不为这些段分配物理内存，它们共享父进程的物理空间，当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间。

其实我们之前已经见过这种方式了，就是字符串的赋值，底层赋值是直接用指针替代的。

二、并发安全

1、常用的几种并发安全的map

因为go没有泛型，所以使用interface{}能匹配所有数据。

sync.Map对以下两种常用场景进行了优化：

• entry只写一次但是读很多次，比如只增长的缓存
• 多个goroutine在读写entry，互不干扰

在这两种情况下，使用sync.Map比单独使用互斥锁或读写锁的map好。

2、数据结构

1
2
3
4
5
6

type Map struct {
	mu Mutex
	read atomic.Value // readOnly
	dirty map[interface{}]*entry
	misses int
}

• 当涉及到脏数据时，需要用到锁
• read中包含了map内容中对并发访问是安全的部分，存储在read中的entry可以在没有锁的情况下并发更新，但是更新前删除的entry需要将entry复制给dirty，并保证不被删除。
• ditry包含了部分键值对，而dirty中的元素最终都会被赋值给read
• misses就是计数器，用于记录read中没有而在dirty中存在的数量，当misses=len(dirty)，那么就会把dirty迁移到read中。

而read的指针指向的是readOnly结构体

1
2
3
4

type readOnly struct {
	m map[interface{}]*entry
	amended bool 
}

这个amended是个标志位，如果为ture表明当前read只读数据m不完整，dirty中包含部分数据。

entry其实就是个指针，有以下几种情况：

• nil：entry被删除，并且m.dirty为空
• expunged：entry被删除，但m.dirty不为空，也不在m.dirty中
• 其他：正常值，指向了interface{}值，并记录在m.read.m[key]中

三、操作

1、查找

1.1、无锁读

1
2
3
4
5

read, _ := m.read.Load().(readOnly)
e, ok := read.m[key]
if !ok {
	return nil, false
}

优先从read的map中查找，如果没有找到就是不存在。此时从read中读取是不加锁的，是不影响性能的。

1.2、读写分离

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

if !ok && read.amended {
	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	e, ok = read.m[key]
	if !ok && read.amended {
		e, ok = m.dirty[key]
		m.missLocked()
	}
	m.mu.Unlock()
}

如果没有找到，并且标识dirty中存在数据，那么就要从dirty中查找，而在dirty操作时是需要加锁的。

这里有一点要特别注意，在加锁后，重新判断了一个read，这个是二次检查，防止在加锁之前，dirty已经迁移到read中。

在进入dirty查找时，不管有没有找到，都要使misses+1，因为去dirty查找了一次。

如果misses大于dirty的长度，那么就开始迁移dirty的数据到read中。

2、新增/更新

2.1、更新

1
2
3
4

read, _ := m.read.Load().(readOnly)
if e, ok := read.m[key]; ok && e.tryStore(&value) {
	return
}

先读取read，如果存在key，就尝试更新。这一步也是不加锁的

2.2、新增

如果不存在，那就要新增key了。新增这一步就需要加锁了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

read, _ = m.read.Load().(readOnly)
if e, ok := read.m[key]; ok {
	if e.unexpungeLocked() {
		m.dirty[key] = e
	}
	e.storeLocked(&value)
} else if e, ok := m.dirty[key]; ok {
	e.storeLocked(&value)
} else {
	if !read.amended { 
		m.dirtyLocked()
		m.read.Store(readOnly{m: read.m, amended: true})
	}
	m.dirty[key] = newEntry(value) 
}

而这里对应着以下场景

• 如果在read中，而key对应的value标识是已删除，那么先去dirty中添加，然后再更新
• 如果不在read中，在dirty中，直接更新值
• 如果都不存在，那么就把数据存在dirty中，然后修改read中的标志位。如果此时dirty没有数据，那么就从read中复制数据，并把标识为删除的数据清除。

这里在dirty写数据，不影响read中读取的数据，可以保证读取read的时候并发安全。

3、删除

看到这里，应该很容易推理出删除的逻辑

1、从read中查找key是否存在，如果不存在但是标志位显示dirty中有新数据，那么就加锁去dirty中查看，然后清除key。

2、如果真不存在，就结束

3、如果存在read中，就将entry置nil

其他几种方法，如LoadOrStore，Range就很容易知道是如何实现的了。

四、生命周期

以上，我们就能分析出key的生命周期

1、新增操作，将key保存在dirty中，并且标识read数据不完整

2、查询操作，在dirty中找到了key，并且满足迁移的条件，将dirty移到read中，修改标识，read数据完整

3、查询操作，直接在read中查询到key了

4、更新操作，直接在read中更新key

5、删除操作，把key对应的value置为nil

6、新增其他的key1，触发迁移条件，将read的数据复制到dirty中，此时key对应的value==nil，被修改为expunged，并且不添加到dirty中。

7、在下一次满足将dirty迁移到read中，就会将这个不存在的key删除

四、总结

1、空间换时间：通过两个冗余的数据结构(read，dirty)，减少锁对性能的影响

2、读操作尽量在read中进行，避免读写冲突

3、命中到dirty累加misses的值，当超出限制时，迁移dirty，避免dirty数据过多

4、二次检查，避免在非原子操作时产生数据错误

5、延迟删除，删除一个键值对只是打了个标签，只有在迁移到read中才清除删除的数据

6、优先从read中读、改和删除，因为对read的操作不用加锁，大大提升性能