Skip to content

Latest commit

 

History

History
215 lines (155 loc) · 7.06 KB

2-5.sync.Map的实现.md

File metadata and controls

215 lines (155 loc) · 7.06 KB
Raw

概述

和 JAVA 中 concurrent hashmap 分段的设计思路不同，sync.Map 的主要思想是做读写分离，底层用了2个 map，read 和 dirty，将频繁变更的数据，和极少变更的数据分离。

极少变更的数据放到 read 里，读 read 无需加锁，更新 read 依靠 CAS 也不用加锁，性能极高。

新增的数据放到 dirty 里。这类数据的读写需要加锁。

读取数据时，先查 read，再查 dirty，当读 read cache miss 累计到一定次数时，说明该 key 读多写少了，将数据从 dirty 移入 read

实现

数据结构

// src/sync/map.go
type Map struct {
    // 当涉及到脏数据(dirty)操作时候，需要使用这个锁
    mu Mutex
    
    // read 字段指向下面的 readOnly 结构，里面有个 map
    // 【读/更新】不需要加锁，只需要通过 atomic 加载最新的指针即可
    read atomic.Value 
    
    // dirty 包含部分 map 的键值对，如果操作需要 mutex 获取锁
    // 【新增】键值时写入这个字段
    dirty map[interface{}]*entry
    
    // misses是一个计数器，用于记录read中没有的数据而在dirty中有的数据的数量。
    // 也就是说如果read不包含这个数据，会从dirty中读取，并misses+1
    // 当misses的数量等于dirty的长度，就会将dirty中的数据迁移到read中
    misses int
}

read的数据结构 readOnly：

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m 包含所有只读数据，不会进行任何的数据增加和删除操作 
    // 但是可以修改 entry 的指针（即更新 value），因为这个不会导致map的元素移动
    m map[interface{}]*entry
    
    // 标志位，如果为true则表明当前read只读map的数据不完整，dirty map中包含部分数据
    amended bool // true if the dirty map contains some key not in m.
}

entry

type entry struct {
    p unsafe.Pointer // *interface{}
}

p有三种值：

  • nil: entry已被删除了，并且m.dirty为nil
  • expunged: entry已被删除了，并且m.dirty不为nil，但这个entry在于m.dirty中
  • 其它：entry是一个正常的值

查找

先查找 read ，read 中没有再查找 dirty 、并增加 cache misses 计数

cache misses 数量累计至 dirty 的长度后，将 dirty 所有数据迁移至 read 中，并清空 dirty

// src/sync/map.go

// 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 的 map 中查找，这时不需要加锁
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    // 如果没有找到，并且 read.amended 为 true，说明 dirty 中有新数据，从 dirty 中查找，开始加锁了
    if !ok && read.amended {
        m.mu.Lock() // 加锁
        
       // 又在 readonly 中检查一遍，因为在加锁的时候 dirty 的数据可能已经迁移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        // read 还没有找到，并且dirty中有数据
        if !ok && read.amended {
            e, ok = m.dirty[key] //从 dirty 中查找数据
            
            // 不管m.dirty中存不存在，都在missLocked() 中将 misses + 1。misses = len(m.dirty)时就会把 dirty 中的数据迁到 read 中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

 // 如果数据不在 read 中，经过几次 miss 后，dirty 中的数据便会迁移到 read 中，这时又可以从 read 中查找到
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) { //misses 次数小于 dirty 的长度，就不迁移数据，直接返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //开始迁移数据
    m.dirty = nil   //迁移完 dirty 就赋值为 nil
    m.misses = 0    //迁移完 misses 归0
}

新增和更新

如果 read 中已有 key，通过 CAS 来更新值

新增 key，或者更新 dirty 中的数据，需要加锁并写入 dirty。其中新增 key 时还会把 read 中的 kv 倒灌回 dirty

// src/sync/map.go

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在 read 中查找值，找到了，就尝试 tryStore 更新值, tryStore 里使用 for 循环 + CAS 的方式进行更新
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok { // double check，因为 lock 前 read 里可能又有了
        if e.unexpungeLocked() {  // 未被标记成删除
            m.dirty[key] = e      // 加入到 dirty 里
        }
        e.storeLocked(&value)             // 设置值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中，直接更新
        e.storeLocked(&value)
    } else {                // read 和 dirty 中都没有，即插入新数据
        if !read.amended {  // if dirty 为空，即向 dirty 中第一次加载数据
            m.dirtyLocked() // 会将 read 里的所有数据加载到 dirty 中，并将 read 里的键值标记为 expunged
            m.read.Store(readOnly{m: read.m, amended: true}) // 将 read.amended 字段标记为true，下次查找会启用dirty查找
        }
        m.dirty[key] = newEntry(value) // 将这个entry加入到m.dirty中
    }
    m.mu.Unlock()
}

func (e *entry) tryStore(i *any) bool {
	  for {
		    p := atomic.LoadPointer(&e.p)
		    if p == expunged {
			      return false
		    }
		    if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
			      return true
		    }
	  }
}

// 遍历 read 中的 key 并写入 dirty
// 这个效率应该很差吧
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
		}
	}
}

删除

和新增差不多，只不过不设置值了，而是调用底层 map 的 delete 方法

总结

仅建议用于如下两种场景：

  1. 写一次，读多次。比如程序初始化时加载配置。
  2. 多协程环境下，不同协程读写不同的key。

这两种场景下，相比于使用原生map + 全局锁的情况，sync.Map 能显著优化加锁带来的性能开销。

如果是读写穿插的情况，会频发触发 dirtyLocked 函数，里面会遍历 map 的 key 并进行迁移，效率非常差。

问题

既然读写 read 可以 CAS，那只要 read 不要 dirty 可不可以？

  • 那同原生 map 就没有区别了。sync.Map 中，read 仅用于读和更新已有 key（这俩场景才能用 CAS），无法用于新增 key 和触发扩容，后者的场景就需要用到 dirty 了。