Levon's Blog

微信: L6241425

0%

golang的sync.Map实现原理

发表于 更新于 分类于 ， ， 阅读次数： Valine：
本文字数： 6.1k 阅读时长 ≈ 6 分钟

map的读写删除都不是原子操作，因此需要控制并发访问，而Go的原生map不支持并发读写；Go在1.9的版本中新增了sync.Map的数据结构，两个map实现分离。

  1. 不会引发扩容的操作（查，改）使用read map，可能引发扩容操作（新增）使用 dirty map。

  2. 读写 read 并不需要加锁，而读或写 dirty 则需要加锁。

  3. 适合读多 append 少的场景，其实是读写和追加分离。

  • 使用方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var syncMap sync.Map

// 添加数据
syncMap.Store(1, "test-1")
syncMap.Store(2, "test-2")
syncMap.Store(3, "test-3")

// 读取数据
v, ok := syncMap.Load(1)
if !ok {
        fmt.Println("数据不存在")
        return
}
fmt.Println(v)

// LoadOrStore方法用于不存在则添加，存在则返回
fmt.Println(syncMap.LoadOrStore(1, "www.liuvv.com"))

// 删除数据
syncMap.Delete(1)

// 循环遍历读取数据获取长度
len := 0
syncMap.Range(func(k, v interface{}) bool {
        len++
        fmt.Println(k, v)
        return true
})
fmt.Println("syncMap长度:", len)

1. 介绍

1.1 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// sync.Map的核心数据结构
type Map struct {
    mu Mutex                          // 对 dirty 加锁保护，线程安全
    read atomic.Value                 // readOnly 只读的 map，充当缓存层
    dirty map[interface{}]*entry     // 负责写操作的 map，当misses = len(dirty)时，将其赋值给read
    misses int                        // 未命中 read 时的累加计数，每次+1
}

// 上面read字段的数据结构
type readOnly struct {
    m  map[interface{}]*entry 
    amended bool // Map.dirty的数据和这里read中 m 的数据不一样时，为true
}

// 上面m字段中的entry类型
type entry struct {
    // 可见value是个指针类型，虽然read和dirty存在冗余情况（amended=false），但是由于是指针类型，存储的空间应该不是问题
    p unsafe.Pointer // *interface{}
}

1.2 原理

sync.Map底层使用了两个原生map，一个叫read，用于正常读写；一个叫dirty，用于追加最新写入的key-value数据。

image-20240709231114492
  • 追加的时候，在dirty增加数据，然后给 read 的 amended置为 true。
image-20240709231316578
  • 如果misses增加，=len(dirty)，这时候把dirty 提升。然后重置 amended，和misses。
image-20240709231915591

可概括为：

  1. 通过 read 和 dirty 实现数据的读写和追加分离，读写的数据存在只读字段 read 上，将最新append的数据则存在 dirty 字段上。
  2. 读取时会先查询 read，不存在再查询 dirty，追加时则只写入 dirty。
  3. 读取 read 并不需要加锁，而读或写 dirty 则需要加锁。
  4. 另外有 misses 字段来统计 read 被穿透的次数（被穿透指需要读 dirty 的情况），超过一定次数则将 dirty 数据更新到 read 中（触发条件：misses=len(dirty)）

在这里插入图片描述

  • 删除逻辑

    1. 正常删除，把底层的指针置为空。

    2. 追加后删除，这时候dirty还没有提升。提升后把删除的指针置为 expunged(生僻的删除)。

image-20240709232549731

2. 源码分析

2.1 load 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 因read只读，线程安全，优先读取
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    // 如果read没有，并且dirty有新数据，那么去dirty中查找（read.amended=true：dirty和read数据不一致）
    if !ok && read.amended {
        m.mu.Lock()
        // 双重检查（原因是前文的if判断和加锁非原子的，害怕这中间发生故事）
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        // 如果read中还是不存在，并且dirty中有新数据
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // m计数+1
            m.missLocked()
        }
        
        m.mu.Unlock()
    }
    
    // !ok && read.amended=false：dirty和read数据是一致的，read 和 dirty 中都不存在，返回nil
    if !ok {
        return nil, false
    }
    
    // ok && read.amended=true：dirty和read数据不一致，dirty存在但read不存在该key，直接返回dirty中数据
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    
    // 将dirty置给read，因为穿透概率太大了(原子操作，耗时很小)
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

在这里插入图片描述

因为写操作仅针对dirty（负责写操作的map），所以dirty是包含read的，最新且全量的数据。

2.2 store 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
func (m *Map) Store(key, value interface{}) {
    // 如果m.read存在这个key，并且没有被标记删除，则尝试更新。
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    // 如果read不存在或者已经被标记删除
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
   
    if e, ok := read.m[key]; ok { // read 存在该key
    // 如果read值域中entry已删除且被标记为expunge，则表明dirty没有key，可添加入dirty，并更新entry
        if e.unexpungeLocked() { 
            // 加入dirty中，这里是指针
            m.dirty[key] = e
        }
        // 更新value值
        e.storeLocked(&value) 
        
    } else if e, ok := m.dirty[key]; ok { // dirty 存在该 key，更新
        e.storeLocked(&value)
        
    } else { // read 和 dirty都没有
        // 如果read与dirty相同，则触发一次dirty刷新（因为当read重置的时候，dirty已置为 nil了）
        if !read.amended { 
            // 将read中未删除的数据加入到dirty中
            m.dirtyLocked() 
            // amended标记为read与dirty不相同，因为后面即将加入新数据。
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value) 
    }
    m.mu.Unlock()
}

// 将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))
    
    // 遍历read。
    for k, e := range read.m {
        // 通过此次操作，dirty中的元素都是未被删除的，可见标记为expunged的元素不在dirty中！！！
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

// 判断entry是否被标记删除，并且将标记为nil的entry更新标记为expunge
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    
    for p == nil {
        // 将已经删除标记为nil的数据标记为expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

// 对entry尝试更新 （原子cas操作）
func (e *entry) tryStore(i *interface{}) bool {
    p := atomic.LoadPointer(&e.p)
    if p == expunged {
        return false
    }
    for {
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
    }
}

// read里 将标记为expunge的更新为nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// 更新entry
func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}
在这里插入图片描述

2.3 delete 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func (m *Map) Delete(key interface{}) {
    // 读出read，断言为readOnly类型
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果read中没有，并且dirty中有新元素，那么就去dirty中去找。这里用到了amended，当read与dirty不同时为true，说明dirty中有read没有的数据。
    
    if !ok && read.amended {
        m.mu.Lock()
        // 再检查一次，因为前文的判断和锁不是原子操作，防止期间发生了变化。
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        if !ok && read.amended {
            // 直接删除
            delete(m.dirty, key)
        }
        m.mu.Unlock()
    }
    
    if ok {
    // 如果read中存在该key，则将该value 赋值nil（采用标记的方式删除！）
        e.delete()
    }
}

func (e *entry) delete() (hadValue bool) {
    for {
        // 再次加载数据的指针，如果指针为空或已被标记删除，那么返回false，删除失败
        p := atomic.LoadPointer(&e.p)
        if p == nil || p == expunged {
            return false
        }
        
        // 原子操作
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return true
        }
    }
}
在这里插入图片描述

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

为了提升性能，load、delete、store等操作尽量使用只读的read；为了提高read的key击中概率，采用动态调整，将dirty数据提升为read；对于数据的删除，采用延迟标记删除法，只有在提升dirty的时候才删除。

3. 头脑风暴

  • 底层使用了两个原生map，不会引发扩容的操作（查，改）使用read map，可能引发扩容操作（新增）使用 dirty map。
  • 两个原生map，其实是读写和追加分离，读取 read 并不需要加锁，而读或写 dirty 则需要加锁。

4. 参考资料

可以加首页作者微信，咨询相关问题！