源码版本1.22

数据结构

关键源码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

type Map struct {
	_ noCopy

    // 互斥锁
	mu Mutex

    // 只读map
	read atomic.Pointer[readOnly]

    // 有锁的读写map
	dirty map[any]*entry

    // 只读map的miss次数
	misses int
}

type readOnly struct {

    // 无锁化的只读map
	m       map[any]*entry
	
    // 标记只读map是否缺失数据
    amended bool
}

通过read map（只读）和dirty map + 互斥锁两个map来实现读写分离（空间换取时间） entry的三种状态：

• 存活态：正常指向元素
• 软删除态：指向nil（向软删除的数据插入或者更新时会直接通过read map的一个CAS操作进行更新）
• 硬删除态：指向固定的全局变量expunged（在dirty map中已经物理上删除了）

读流程

1. 首先读取read map，如果amended状态为false，表示read map中已经是全量数据，这时就看能不能再read map中找到数据，然后如果找到的数据他的entry对应为nil或者expunged也表示没找到。

2. 如果read map中没找到并且amended为true时，表示read map中没找到并且read map中不是全量数据时。这时会去dirty map中查找（会加锁），在查找之前会进行一个对read map的 二次检查 （防止在此期间其他goroutine的操作让read map的数据覆盖了），如果read中的amended为false时，就会去read中查找并判断返回。如果read map不可用，就读取dirty中的数据判断返回，并把misses++（到达阈值（跟dirty长度相等）时将read中数据进行覆盖）。

覆盖流程

关键源码misslocked：

1
2
3
4
5
6
7
8
9

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

如果misses大于等于dirty中数据的数量时，会使用dirty覆盖read并将amended变为false。此时dirty为nil，misses计数器清零。

写流程（插入或更新）

1. 如果read中存在key并且entry不是expunged，就可以通过CAS的操作来进行一个更新（直接将entry指向新插入的数据）

2. 如果read中不存在或者是硬删除态，就会进入dirty中，同样会先进行一个read的二次检查，如果read中没有，就看dirty中是否存在，存在就进行更新操作（修改dirty），不存在就进行插入操作。插入时要判断amended，如果为false，就会执行dirtyLocked流程，并将amended置为true。

dirtyLocked流程

关键源码dirtyLocked：

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

func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }


    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[any]*entry, len(read.m))
    for k, e := range read.m {
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

当将dirty覆盖给read之后，dirty应该为nil，如果执行时为nil说明已经执行过了，可以直接返回。如果不是nil，就通过for循环线性的将read中的非删除态数据拷贝回dirty中，并将其中的软删除态的数据更新为硬删除态。

dirtyLocked的拷贝是线性的，性能不好。

诱发dirtyLocked的原因：写多读少 ，大量的新数据的插入，同时很多读操作在read中未命中。造成misslocked，然后又一次写操作越过了read和dirty，就会进入dirtyLocked流程。

删除流程

1. 如果read中存在key，通过CAS的操作将对应的value置为nil（软删除态）

2. 如果read中不存在，去dirty中查找，会先进行二次检查。如果read中不存在并且amended为true，则去dirty中查找删除（物理删除）并返回旧值（方法要返回），然后将misses++。如果read中存在或者amended为false，就会去read中判断删除。

遍历流程

1. 首先获取read，然后判断amended，如果amended为true，就会将dirty中的数据覆盖到read中，并将dirty置为nil并将misses归零。

2. 然后遍历read并执行传入的函数，通过返回值判断何时终止。