Golang 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

    var cache sync.Map
	var k1 = "key1"
	var v1 = []int{1, 2, 3}

	println("==>Store, Load<==")
	cache.Store(k1, v1)

	if val, ok := cache.Load(k1); ok {
		fmt.Println(val.([]int))
	}

	println("==>LoadOrStore<==")
	k2 := "key2"
	v2 := "val2"

	fmt.Println(cache.LoadOrStore(k2, v2))
	fmt.Println(cache.LoadOrStore(k2, v2))

	println("==>Range<==")
	cache.Range(func(k, v interface{}) bool {
		fmt.Println(k, v)
		return true
	})

	println("==>Delete k2<==")
	cache.Delete(k2)
	fmt.Println(cache.Load(k2))

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

type Map struct {
	mu Mutex // 锁map的互斥锁
	read atomic.Value // 读结构
	dirty map[interface{}]*entry
	misses int // 统计
}

type readOnly struct {
	m       map[interface{}]*entry
	amended bool // 标记 dirty 中存在 read 里不存在的key
}

type entry struct {
    p unsafe.Pointer
}

var expunged = unsafe.Pointer(new(interface{}))

 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

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 读操作首先从read中读取，如果读到数据，则返回
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
        // 如果没有读到数据，并且存在dirty中有，read中没有的数据
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
            // 出现了从read取失败的情况，miss += 1, 并考虑是否需要将dirty数据搬迁至read
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}


func (m *Map) missLocked() {
	m.misses++
    // misses 过多的话，就做一次copy
	if m.misses < len(m.dirty) {  
		return
	}
	m.read.Store(readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}

 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

func (m *Map) Store(key, value interface{}) {
	// 首先看read中是否存在对应的key，如果存在，直接替换即可
	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() { 
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {  
		// 如果 read 中不存在， dirty 中存在，那和store 一样，保存即可
		e.storeLocked(&value)
	} else {  
		// read/dirty 中都不存在
		if !read.amended {
			// 构造一个dirty 数据集 （包含目前 read 中的非删除的数据）  O(n)
			m.dirtyLocked()  
			// 设置 amended 与 dirty 不一致
			m.read.Store(readOnly{m: read.m, amended: true})  
		}
		m.dirty[key] = newEntry(value) // 数据保存至dirty
	}
	m.mu.Unlock()
}

// 清理read.m中的数据
func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}

	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[interface{}]*entry, len(read.m))
	for k, e := range read.m {   // 真正删除数据
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

 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

func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]

	// 删除操作大部分情况下也只是做nil标记，并不是直接删除
	if !ok && read.amended { // 如果read 里面没有，并且有脏数据的时候，就需要检查 dirty 的数据
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			m.missLocked()  // 可能需要将 dirty -> read
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete() // 标记 e.p = nil
	}
	return nil, false
}

// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
	m.LoadAndDelete(key)
}