Sync.Map

Golang 的 sync.Map 是一个并发安全的 map 实现,在 Go 1.9 版本中被引入。它的设计思想和底层实现如下:

设计思想

  1. 读写分离 sync.Map 将读和写操作分离到不同的数据结构中,避免读写冲突。读操作主要在 read 视图中进行,写操作则在 dirty 视图中进行。
  2. 空间换时间 sync.Map 通过冗余的数据结构(read 和 dirty),以空间换取更好的读写性能。
  3. 双重检查 在读取数据时,sync.Map 先检查 read 视图,如果没有则检查 dirty 视图,避免读遗漏。
  4. 延迟删除 删除操作只是将数据从 read 视图中标记为已删除,而不是立即从内存中删除,减少删除操作的开销。

底层实现

  1. 数据结构
 type Map struct {
 // 该锁⽤来保护dirty
 mu Mutex
 // 存读的数据，因为是atomic.value类型，只读类型，所以它的读是并发安全的
 read atomic.Value // readOnly
 //包含最新的写⼊的数据，并且在写的时候，会把read 中未被删除的数据拷⻉到该dirty中，因为是普通的map
存在并发安全问题，需要⽤到上⾯的mu字段。
 dirty map[interface{}]*entry
 // 一个原子操作的计数器,用于统计 read 视图读取 miss 的次数。当 misses 达到一定阈值时,sync.Map 会将 dirty 视图提升为新的 read 视图。
 // 从read读数据的时候，会将该字段+1，当等于len（dirty）的时候，会将dirty拷⻉到read中（从⽽提升
读的性能）。
 misses int
}

 read 数据结构
type readOnly struct {
 m map[interface{}]*entry
 // 如果Map.dirty的数据和m 中的数据不⼀样是为true
 amended bool
}

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

sync.Map 使用 read 和 dirty 两个视图存储数据,前者用于读操作,后者用于写操作。 2. 读取流程 先在 read 视图中查找键值对,如果没有则在 dirty 视图中查找。如果 dirty 视图有新数据,则需要先将其提升(promote)到 read 视图。

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
	//因read只读，线程安全，先查看是否满⾜条件
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	//如果read没有，并且dirty有新数据，那从dirty中查找，由于dirty是普通map，线程不安全，这个时候⽤
	到互斥锁了
	if !ok && read.amended {
		m.mu.Lock()
		// 双重检查
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		// 如果read中还是不存在，并且dirty中有新数据
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// mssLocked（）函数是性能是sync.Map 性能得以保证的重要函数，⽬的讲有锁的dirty数据，
			替换到只读线程安全的read⾥
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}
//dirty 提升⾄read 关键函数，当misses 经过多次因为load之后，⼤⼩等于len（dirty）时候，讲dirty替换到read⾥，以此达到性能提升。
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
}
  1. 写入流程 新的键值对直接写入 dirty 视图。当 read 视图访问次数达到阈值时,sync.Map 会将 dirty 视图中的新数据提升到 read 视图。
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 {
		//如果entry被标记expunge，则表明dirty没有key，可添加⼊dirty，并更新entry
		if e.unexpungeLocked() {
			//加⼊dirty中
			m.dirty[key] = e
		}
		//更新value值
		e.storeLocked(&value)
		//dirty 存在该key，更新
	} else if e, ok := m.dirty[key]; ok {
		e.storeLocked(&value)
		//read 和dirty都没有，新添加⼀条
	} else {
		//dirty中没有新的数据，往dirty中增加第⼀个新键
		if !read.amended {
			//将read中未删除的数据加⼊到dirty中
			m.dirtyLocked()
			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中的元素都是未被删除的，可⻅expunge的元素不在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 尝试更新
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))
}
  1. 删除流程 删除操作只是将数据从 read 视图中标记为已删除,而不会立即从内存中删除,减少删除操作的开销。
func (m *Map) Delete(key interface{}) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	//如果read中没有，并且dirty中有新元素，那么就去dirty中去找
	if !ok && read.amended {
		m.mu.Lock()
		//这是双检查（上⾯的if判断和锁不是⼀个原⼦性操作）
		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 {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}

综上所述,sync.Map 通过读写分离、空间换时间、双重检查和延迟删除等优化策略,实现了高性能的并发安全 map。但对于频繁增删的场景,其性能可能不如使用 sync.RWMutex 加锁的方式

性能对比

  • sync.map

    • 读多写少
      • sync.Map 的结构优化了读取操作，适合在数据被频繁读取但不常更新的场景中使用。例如，缓存数据或配置值的存储。
    • 数据只增不减的情况
      • 在某些情况下，数据只会增加而不会减少，sync.Map 的性能表现会更优，因为写入操作不会频繁导致锁竞争。
    • 高并发访问
      • 对于多个 goroutine 同时访问的情况，sync.Map 能够有效减少锁的争用，提供更好的性能。

  • map 加锁

    • 写操作频繁
      • 当需要频繁写入数据时，使用 sync.Mutex 或 sync.RWMutex 可以更好地控制并发，尽管会引入锁的开销，但在写操作较多的情况下，性能会更稳定。
    • 复杂的读写逻辑
      • 如果需要在读写操作中进行复杂的逻辑处理，使用加锁的 map 可以更灵活地控制并发行为。
    • 数据一致性要求高
      • 在需要严格保证数据一致性的场景中，使用加锁的方式可以确保在读写操作中不会出现数据不一致的问题

  • 分段锁(concurrent-map)

  • 性能对比

    • 读性能 sync.Map 在读操作上表现优越，特别是在高并发的读场景中，能够通过原子操作和读缓存机制提供快速访问。
    • 写性能 sync.Map 的写性能相对较差，尤其是在频繁写入的情况下，可能导致性能下降，因为写操作需要加锁，且会影响到读操作的效率。
    • 锁竞争 使用 sync.Mutex 或 sync.RWMutex 的 map 在写操作时会引入锁竞争，可能导致性能瓶颈，尤其在高并发环境下。
    • 适用性 sync.Map 更适合于读多写少的场景，而加锁的 map 则在写操作频繁的情况下表现更好.