Golang:sync.Map

由于map在gorountine 上不是安全的，所以在大量并发读写的时候，会出现错误。

在1.9版的时候golang推出了sync.map.

sync.map

通过阅读源码我们发现sync.map是通过冗余的两个数据结构(read、dirty),实现性能的提升。

为了提升性能，load、delete、store等操作尽量使用只读的read；

为了提高read的key命中概率，只有当read中读取不到的累计miss次数大于等于dirty的长度时，将dirty数据提升为read；

对于数据的删除，采用延迟标记删除法，只有在提升dirty的时候才删除。

数据结构

 1   type map struct {
 2     // 读写dirty时使用的锁
 3     mu mutex
 4     read atomic.value 
 5     dirty map[interface{}]*entry
 6     // 从read中读取不到，从dirty读取到数据时，+1
 7     misses int
 8 }
 9 
10 type readonly struct {
11     m  map[interface{}]*entry
13     amended bool 
14 }
15 
16 type entry struct {
17     //指针类型
18     p unsafe.pointer
19 }

 

delete

 1 func (m *map) delete(key interface{}) {
 2     read, _ := m.read.load().(readonly)
 3     e, ok := read.m[key]
 4     if !ok && read.amended {
 5         m.mu.lock()
 6         read, _ = m.read.load().(readonly)
 7         e, ok = read.m[key]
 8         if !ok && read.amended { //double check
 9             delete(m.dirty, key)
10         }
11         m.mu.unlock()
12     }
13     if ok {
14         e.delete()
15     }
16 }

 1 func (e *entry) delete() (hadvalue bool) {
 2     for {
 3         p := atomic.loadpointer(&e.p)
 4         if p == nil || p == expunged {
 5             return false
 6         }
 7         if atomic.compareandswappointer(&e.p, p, nil) { //原子操作，加删除标记
 8             return true
 9         }
10     }
11 }

删除时，如果read中没有，就直接从dirty删除。如果read中有，就把read中标记为删除。

 load

 1 func (m *map) load(key interface{}) (value interface{}, ok bool) {
 2     read, _ := m.read.load().(readonly)
 3     e, ok := read.m[key]
 4     if !ok && read.amended {
 5         m.mu.lock()
 6         read, _ = m.read.load().(readonly)
 7         e, ok = read.m[key]
 8         if !ok && read.amended {
 9             e, ok = m.dirty[key] // read中读取不到，从dirty读，miss++
10             m.misslocked()
11         }
12         m.mu.unlock()
13     }
14     if !ok {
15         return nil, false
16     }
17     return e.load()
18 }

load返回存储在映射中的键值（read中读取不到，从dirty读），如果没有值，则返回nil。ok结果指示是否在映射中找到值。

 

misslocked和store

 

1 func (m *map) misslocked() {
2     m.misses++
3     if m.misses < len(m.dirty) {
4         return
5     }
6     m.read.store(readonly{m: m.dirty})
7     m.dirty = nil
8     m.misses = 0
9 }

 1 func (m *map) store(key, value interface{}) {
 2     //如果在read 读取到,就原子操作直接对值进行更新
 3     read, _ := m.read.load().(readonly)
 4     if e, ok := read.m[key]; ok && e.trystore(&value) {
 5         return
 6     }
 7 
 8     //如果未在read 中读取到值或读取到值进行更新时更新失败,则加锁进行后续处理
 9     m.mu.lock()
10     read, _ = m.read.load().(readonly)
11     if e, ok := read.m[key]; ok {
12         // double check,如果读取到的值处于删除状态,将值写入dirty map中
13         if e.unexpungelocked() {
14             m.dirty[key] = e
15         }
16         // 原子操作更新key对应的值
17         e.storelocked(&value)
18     } else if e, ok := m.dirty[key]; ok {
19         //如果在dirty map中读取到值，则直接使用原子操作更新值
20         e.storelocked(&value)
21     } else {
22         //如果dirty map中不含有值，则说明dirty map已经升级为read map,或者第一次进入
23         //需要初始化dirty map，并将read map的key添加到新创建的dirty map中．
24         if !read.amended {
25             m.dirtylocked()
26             m.read.store(readonly{m: read.m, amended: true})
27         }
28         m.dirty[key] = newentry(value)
29     }
30     m.mu.unlock()
31 }

一些观点，当有大量并发读写发生的时候，会有很多的miss导致不断的dirty升级。可能会影响效率。

尝试使用sync.map

 1 package main
 2 
 3 import (
 4     "fmt"
 5     "sync"
 6 )
 7 
 8 func main() {
 9     var m sync.map
10     m.store(1, "a")
11     m.store(2, "b")
12     m.store(3, "c")
13     m.store(4, "d")
14 
15     m.range(func(k, v interface{}) bool {
16         fmt.println(k, v)
17         return true
18     })
19     //loadorstore
20     v, ok := m.loadorstore(5, "e")
21     fmt.println(ok, v)
22 
23     v, ok = m.loadorstore(1, "bbb")
24     fmt.println(ok, v)
25 
26     //load
27     v, ok = m.load(1)
28     if ok {
29         fmt.println("it's an existing key,value is ", v)
30     } else {
31         fmt.println("it's an unknown key")
32     }
33 
34     m.range(func(k, v interface{}) bool {
35         fmt.println(k, v)
36         return true
37     })
38 
39     m.delete(1)
40     fmt.println(m.load(1))
41 
42 }

 1 4 d
 2 1 a
 3 2 b
 4 3 c
 5 false e
 6 true a
 7 it's an existing key,value is  a
 8 2 b
 9 3 c
10 4 d
11 5 e
12 1 a
13 <nil> false

 

运行结果是：