sync.Map的数据结构

首先看一下sync.Map的底层数据结构

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
type Map struct {
	
	// 互斥锁，锁定 dirty
	mu Mutex                        
	
	// 优先读
	read atomic.Value               
	
	// 保存最新map
	dirty map[interface{}]*entry   
	
	// 记录从read中读取不到数据次数
	// 当misses>=len(dirty)时，会将dirty作为read,然后dirty=nil
	// (源码中 missLocked函数)
	misses int                      
}

type readOnly struct {
    // 主要用于存储
    m       map[interface{}]*entry
    // 如果数据在dirty中但没有在read中，该值为true,作为修改标识
    amended bool 
}

type entry struct {
    // nil: 表示为被删除，调用Delete()可以将read map中的元素置为nil
    // expunged: 也是表示被删除，但是该键只在read而没有在dirty中，这种情况出现在将read复制到dirty中，即复制的过程会先将nil标记为expunged，然后不将其复制到dirty
    //  其他: 表示存着真正的数据
    p unsafe.Pointer // *interface{}
}
  1. mu 用于数据存取数据加锁
  2. read
  3. dirty
  4. misses

sync.Map的操作

存数据，Store(key,val)

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
// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			// The entry was previously expunged, which implies that there is a
			// non-nil dirty map and this entry is not in it.
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		e.storeLocked(&value)
	} else {
		if !read.amended {
			// We're adding the first new key to the dirty map.
			// Make sure it is allocated and mark the read-only map as incomplete.
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}
  1. 首先判断是否在map.read中，如果在，则调用entry的tryStore方法，tryStore方法使用了atomic.CompareAndSwapPointer操作，保证了操作原子性。如果成功，则直接返回①。当该key值已删去时tryStore方法返回false继续执行②
  2. 加锁，重新获取map.read值保证锁定操作期间数据最新且不会发生变化。
  3. 如果key存在于map.read中：
    1. 如果read中数据被删除③，则将k-v放到dirty中(dirty中没有该key)
    2. 如果read中数据未被删除④不处理
    3. 将v放到read中
  4. 如果key不存在于map.read中，存在于dirty中⑤，更新dirty中的值
  5. 如果key既不存在于map.read中，也不存在于map.dirty中：
    1. read与dirty中key一致（amended为false）⑥，初始化read，并标记amended参数为true，将数据存到dirty中
    2. 否则不做处理 ⑦
    3. 将数据存入dirty中
  6. 解锁返回

删除数据 Delete(key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	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 {
		e.delete()
	}
}
  1. 判断如果待删除的key不在map.read中且map.dirty中含有map.read中不存在的key，则：
    1. 锁定，重新判断map.read中是否有key，如果同上，则调用从map.dirty中删除的函数，然后解锁
  2. 否则，若key存在于map.read中，则调用entry中的delete（entry里只有一个参数，应该是val的指针）

访问map数据 Load(key)

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
// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		// Avoid reporting a spurious miss if m.dirty got promoted while we were
		// blocked on m.mu. (If further loads of the same key will not miss, it's
		// not worth copying the dirty map for this key.)
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// Regardless of whether the entry was present, record a miss: this key
			// will take the slow path until the dirty map is promoted to the read
			// map.
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}
  1. 判断如果待访问的key不在map.read中且map.dirty中含有map.read中不存在的key，则
    1. 对map加锁，再次判断为真，则调用map.missLocked()，（通过判断在map.read中miss的次数来决定是否将map.dirty替换掉map.read）
    2. 解锁
  2. 判断前边是否获得到val值，未获取到，则返回 nil,false
  3. 若前边取到val，则返回

LoadOrStore(key,val)

  1. 如果map中存在key，则返回对应的val
  2. 否则，保存参数中的key,val，并返回参数中的val

遍历Map: range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main

import (
	"fmt"
	"sync"
)

func main() {

	m := sync.Map{}
	m.Store("k1", "v1")
	m.Store("k2", "v2")

	m.Range(func(k, v interface{}) bool {
		fmt.Println(k, v)
		return true
	})
}

总结

map.read与map.dirty中数据一致性：

  1. map.dirty包含map.read中没有的key，map.read.amended为false，表明两者底层val引用是一致的，此时对数据的 更新、删除（此时删除操作实际是将底层val的指针置位nil，相当于只删除了val未删除key） 做cas操作即可
  2. 否则，map.read.amended为true，此时操作数据要考虑map.read与map.dirty中数据一致性
    1. load数据时，在map.read中访问不到次数大于等于map.dirty长度时，会用map.dirty替换map.read，并将map.dirty置为nil，此时map.read.amended为false（因为map.dirty中不包含map.read中不存在的key）
    2. store数据时，当map.dirty数据为空时，会将map.read中的key的val引用复制过来（此时会判断是否标记未删除，标记删除则不复制，删除了val的key也删除掉），再在map.dirty中增加k-v，此时map.read.amended为true