Golang Sync.Map 实现

本文主要简单介绍 sync.Map 的使用和实现。

众所周知,Golang 的map是非协程安全的(并发读写数据是不允许的,但是可以并发读)。因此,在 Golang1.9 的版本中加入了 sync.Map 包,用于并发的访问 map。

下面我们简单学习sync.Map 的使用和实现。

如何使用

sync.Map 和map 在使用上有较大区别。map 为内置类型,sync.Map 实质是实现了一个带有一些操作方法的Struct 对象。因此,在使用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
    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))

这里需要注意的是,在sync.Map中,没有提供 len 方法。

sync.Map 实现

为了更好的理解sync.Map,有必要学习 sync.Map 是如何实现的。数据结构如下:

 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{}))
  • mu 在数据访问上,通过互斥锁mu来保证 dirty 做读写操作的互不冲突。

  • read 对象通过原子访问的方式保存,保存对象为 readOnly 类型,包含了存储数据的 m, 和一个标识 amended。在大部分情况下,读 read 不需要加锁访问。这里可以减少抢锁带来的消耗。amended 标识是否在 dirty 中有 read 中没有的数据。

  • dirty 也保存了一个 map 数据。当用户写操作时,如果 read 中没有对应的 key,就会加锁把数据写入 dirty 中。dirty 如果不为 nil 的情况下,read 的数据应该是 dirty 数据的子集。

  • misses 为一个统计参数,在数据访问时,如果 key 在 read 中不存在, 且 amended 标识为 true, dirty 增加 1, 当 misses 值大于 dirty 中元素的大小时,将 dirty 中的数据替换为 read 的 map。

  • *entry.p 保存了value值的指针。p 存在多种情况:

    • p 为 expunged, 标记在 read 中将删除的数据。在下一次 dirty 转为 read 数据时将被删除。
    • p 为 nil,标识删除,但是 key 位置还保留,在 dirtyLocked 中,被转为 expunged
    • 数据存在,在调用 Delete 方法时,将被置为 nil

通过简单的描述,可以理解为读操作,尽量访问 read。写操作大部分情况下会访问 dirty (除非是做覆盖操作)。

下面,我们对比较常用的几个操作做细致分析。

Load

Load 操作从Map中获取 key 对应的value 值。

 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
}

Load 方法比较好理解。从read中取数据。在未取到并且存在脏数据的情况下,到dirty中取。如果miss过多的话,就把dirty放到read中。 Load中,如果在read中出现了,就不需要加锁。反之需要加锁。这里也可以看出,在读的频次远远大于写时,大部分情况下是不需要加锁的,这也是sync.Map 的优势。

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
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
		}
	}
}

Store 方法略微复杂,在read中存在对应key时,直接替换即可,此处也不需要加锁。 如果不存在,就需要加锁新增key 了。 如果dirty中存在,则直接保存。如果都不存在,则首先判断是否有修正过的数据,如果没有,需要调用dirtyLocked 方法,将read 方法中的未删除的数据copy 到新创建的map中,并标记read中nil值为 expunged(如果被标记过,那该value在read中不能被修改了)。重新设置amended 为 被修改的数据,并将新增的kv赋值到dirty中。

需要注意的是,在调用tryStore 更新 read 中的value值时,需要判断是否p 被标记为 unexpunged. 如果被标记为 unexpunged,则不能被更新。原因是: 在标记 unexpunged 后,在 dirty 中将不存在该值。如果做了更新,read中的数据将在dirty中不存在,导致在未来dirty迁移为read.m 时出现数据丢失。

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
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)
}
  • 对于在read中存在的数据,删除操作,只是通过标记value值为nil,并不会实际删除对应key. 这种情况下,不需要加锁。

技术总结

  1. 为什么在store中,read 可以不加锁修改map值。 正常情况下,对map的赋值是需要加锁的(不然可能会出现panic),但是,为了减少加锁的消耗,map中存储的是entry对象,对象中保存的entry。赋值只与entry.p 相关,与map的赋值没有关系了。
  2. 理论上,在read不存在key 的情况下,删除dirty中的key,只需要直接删除key 即可。(看github.com中源码已修改)
  3. 为了保证操作的原子性,在做entry中数据的赋值时,均采用 atomic.StorePointer, atomic.LoadPointer, atomic.CompareAndSwapPointer 保证了赋值的有序和原子性。
  4. 为了保证无锁状态下读取 read.m,read.m 对象是只读的,无法增加和删除key。通过标记p的值来删除,以及通过使用 dirty 替换 read.m 做数据的更新。
  5. 从源码角度看来性能:
  • 不存在删除的情况,且key值比较固定,大部分情况是不需要加锁的。
  • 对于读多写少的情况,大部分情况也是从read中取值,不需要加锁的。
  • 对于存取的kv数据量非常大(百万级别)的情况下,一次 Store 可能需要对所有的read做遍历,并将未标记删除的entry赋值给dirty,这时可能出现卡顿现象。

对于协程安全的map,除了可以使用sync.Map 对象外,还可以用map +读写锁的方式简单暴力的实现协程安全的map。另外github.com/orcaman/concurrent-map 包也是一个不错的实现。concurrent-map 采用分段锁的方式实现了一个协程安全的map,在某些场景下比 sync.Map 有很大优势。具体如何选取,我们在接下来的文章中做具体分析。

0%