图解sync.Map

package main

import (
 "fmt"
 "sync"
)

func main() {
 // m零值是有效的，可以直接使用
 var m sync.Map

 // 添加元素到sync.Map
 m.Store("name", "mingyong")
 m.Store("age", 20)

 // 访问sync.Map中元素
 v, ok := m.Load("name")
 fmt.Println(v, ok)

 // 遍历sync.Map
 m.Range(func(k, v interface{}) bool {
  fmt.Println(k, v)
  return true
 })

 // 删除sync.Map中的元素
 m.Delete("name")
}

type Map struct {
 mu Mutex
    
 // 把read看成一个安全的只读的map.atomic.Value是一个interface类型的结构体，里面实际装的是
 // 一个map,对atomic.Value中的元素更新是通过原子操作进行的，
 read atomic.Value // readOnly

 // dirty需要使用上面的mu加锁才能访问里面的元素，dirty中包含所有在read字段中但未被expunged(删除)
 // 的元素以及新加的元素
 dirty map[interface{}]*entry

 // misses是一个计数器，记录在从read中读取数据的时候，没有命中的次数，一旦misses值和dirty长度
 // 一样之后，会把dirty内容提升为read
 misses int
}

// readOnly是存在Map结构中read字段中的内容，它以原子方式存储
type readOnly struct {
 m map[interface{}]*entry
 // amended为true表示dirty中包含read中没有的数据，为false表示dirty中的数据在read都
 // 存在
 amended bool // true if the dirty map contains some key not in m.
}

// expunged用来标识map中的key是已经删掉的指针，在sync.Map删除一个key时，并不是立即将其从
// map中删除，而是将key对应的value标记为nil或者expunged，在以后的处理过程中才有机会真正删除
var expunged = unsafe.Pointer(new(interface{}))

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

// Store保存或更新一个键值对
func (m *Map) Store(key, value interface{}) {
 // 检查key是否在read中存在
 read, _ := m.read.Load().(readOnly)
 // 如果key在read中，有3种情况:
 // 1.p=nil,表示key已删除，并且dirty中不存在数据
 // 2.p=expunged,表示key已删除，dirty中存在数据且该key不在dirty中
 // 3.p=&entry，表示key存在，指向一个真实的value
 // 对情况1和情况3，直接将value的值存在p中，对情况2不存value，继续走后面的逻辑
 if e, ok := read.m[key]; ok && e.tryStore(&value) {
  return
 }

 m.mu.Lock()
 // 加锁后，继续检查read中是否有key存在
 read, _ = m.read.Load().(readOnly)
 // key在read中，继续检查key是否已经被删除
 if e, ok := read.m[key]; ok {
  if e.unexpungeLocked() {
   // 如果key已被删除，并且处于expunged状态，说明此key存在read但不在dirty中
   // 并且此时dirty非空，需要将此key加入到dirty中，并且更新e.p的值指向value
   m.dirty[key] = e
  }
  e.storeLocked(&value)
 } else if e, ok := m.dirty[key]; ok {
  // key不在read中但在dirty中，直接更新dirty中e.p的值，指向value
  e.storeLocked(&value)
 } else {
  // 走到这里说明key既不在read中也不在dirty中，肯定是一个新的key.
  // 并且dirty中所有的key都在read中
  if !read.amended {
   // 如果dirty为nil,需要创建dirty对象，并且标记read的amended为true，
   // 说明有元素存在于dirty中但不在read中
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
  }
  // new一个新entry，将新值加入到dirty对象中
  m.dirty[key] = newEntry(value)
 }
 m.mu.Unlock()
}

// tryStore尝试将value的值存在e.p中
func (e *entry) tryStore(i *interface{}) bool {
 for {
  p := atomic.LoadPointer(&e.p)
  // 如果p为expunged，不能直接存储，因为此时的read中所有处于非expunged状态的key都
  // 在dirty中，将key加回到read的时候，也需要将其加入到dirty中，此处不处理这种情况
  // 直接返回
  if p == expunged {
   return false
  }
  // p为nil或指向&entry对象，设置e.p为i的值，即将e.p指向存入的value
  if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
   return true
  }
 }
}

// unexpungeLocked将e.p从expunged修改为nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
 return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// storeLocked原子操作，将i存储到e.p中，此处的i不能是expunged值
func (e *entry) storeLocked(i *interface{}) {
 atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

func (m *Map) dirtyLocked() {
 // 如果dirty字段已经存在，就不需要在创建了
 if m.dirty != nil {
  return
 }
 // 获取read字段
 read, _ := m.read.Load().(readOnly)
 m.dirty = make(map[interface{}]*entry, len(read.m))
 // 遍历read字段，将里面不是punged状态的键值对复制到dirty中
 for k, e := range read.m {
  if !e.tryExpungeLocked() {
   m.dirty[k] = e
  }
 }
}

// Load方法返回key对应的value，第二bool型参数表示key是否在map中存在
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
 read, _ := m.read.Load().(readOnly)
 // 优先从无锁map read中读取
 e, ok := read.m[key]
 // 如果无锁map中不存在并且dirty中有元素不在read中，进一步从dirty中读取
 if !ok && read.amended {
  m.mu.Lock()
  // 双重检查，进一步查看read中是已有key存在
  read, _ = m.read.Load().(readOnly)
  // 如果key已存在，直接返回对应的value
  e, ok = read.m[key]
  // key还是不存在，并且dirty中有数据，不得不检查dirty中是否有
  if !ok && read.amended {
   // 从dirty中获取数据
   e, ok = m.dirty[key]
   // 不管key在不在dirty中，命中记录数misses都会加1，当misses大于等于
   // dirty中数据元素的个数时，dirty中的数据会被提升到read中，提升之后
   // dirty将会被清空，命中记录数misses清零
   m.missLocked()
  }
  m.mu.Unlock()
 }
 // key在read和dirty中都不存在，返回nil和false
 if !ok {
  return nil, false
 }
 // 返回value值，e可能来自read也可能来自dirty，所以value可能是从read获得的，也可能是从
 // dirty获得的
 return e.load()
}

func (m *Map) missLocked() {
 // misses计数+1
 m.misses++
 // 如果没有达到临界值(dirty的长度)，直接返回
 if m.misses < len(m.dirty) {
  return
 }
 // 将dirty字段的内容提升为read
 m.read.Store(readOnly{m: m.dirty})
 // 清空dirty,dirty为map类型，清空方法是直接赋值nil，让GC清理掉里面的内容
 m.dirty = nil
 // misses计数重置为0
 m.misses = 0
}

func (e *entry) load() (value interface{}, ok bool) {
 // 原子操作，获取e.p中值
 p := atomic.LoadPointer(&e.p)
 // p为nil或expunged状态都表示key被删除了，所以直接返回nil,false
 if p == nil || p == expunged {
  return nil, false
 }
 // 返回value的值
 return *(*interface{})(p), true
}

// Range 方法对sync.Map进行遍历操作，需要传入一个func(key, value interface{}) bool类型的
// 函数f，会对遍历到的键值对调用f进行处理，如果函数f返回false,对sync.Map的迭代将停止。
// Range 方法在遍历的时候会对sync.Map的元素至多访问一次，如果在执行Range操作的时候，有其他协程并发
// 的添加或删除元素，可能会导致有些元素未被遍历到。
// Range 方法是一个O(N)时间复杂度的操作，对于存在元素在dirty不在read的情况，进行了一个优化，将dirty
// 提升为read了，所以下次在进行Range的时候，直接对read进行遍历，不用加锁。
func (m *Map) Range(f func(key, value interface{}) bool) {
 
 // 如果所有的元素都在read中，直接对read进行遍历
 read, _ := m.read.Load().(readOnly)
 // 确认是否有元素存在dirty中而不在read中
 if read.amended {
  m.mu.Lock()
  read, _ = m.read.Load().(readOnly)
  if read.amended {
   // 有元素在dirty中，对dirty进行遍历
   read = readOnly{m: m.dirty}
   // 进行一个优化，将dirty提升为read
   m.read.Store(read)
   // 将dirty提升为read之后，dirty置为nil
   m.dirty = nil
   // 计数器清理0
   m.misses = 0
  }
  m.mu.Unlock()
 }
    // 对遍历到的每个元素，调用传入的函数f进行处理
 for k, e := range read.m {
  v, ok := e.load()
  if !ok {
   continue
  }
  if !f(k, v) {
   break
  }
 }
}

// Delete删除一个key
func (m *Map) Delete(key interface{}) {
 // 先检查key是否在read中
 read, _ := m.read.Load().(readOnly)
 e, ok := read.m[key]
 // 如果key不在read中，并且此时dirty中存在数据不在read中，继续检查dirty
 if !ok && read.amended {
  m.mu.Lock()
  // 加锁再进行一次检查
  read, _ = m.read.Load().(readOnly)
  e, ok = read.m[key]
  if !ok && read.amended {
   // 直接从dirty中删除key,此时read中是不存在的，dirty中删掉之后，两边都是
   // 不存在了
   delete(m.dirty, key)
  }
  m.mu.Unlock()
 }
 // 满足ok为true，read中肯定是有该key的， dirty有两种情况:
 // 1是dirty中没有该key， 2是dirty中也有该key
 // 对于情况1，因为dirty中不存，直接将read中e.p设置为nil,标记为删除状态
 // 对于情况2，dirty中key对应的e和read中该key对应的e是同一个，所以直接将
 // read中的e.p设置为nil,其实也是将dirty中e.p也设置为nil了
 if ok {
  e.delete()
 }
}

func (e *entry) delete() (hadValue bool) {
 for {
  p := atomic.LoadPointer(&e.p)
  // p为nil和expunged都表示之前已删除过了，直接返回false表示未进行实际的删除
  if p == nil || p == expunged {
   return false
  }
  // 将e.p置为nil, key并未从read中删除，如果key存在于dirty中，key也是未从dirty
  // 中删除的
  if atomic.CompareAndSwapPointer(&e.p, p, nil) {
   return true
  }
 }
}

// LoadOrStore 可以看做Load操作和Store操作的组合，如果key已存在m中（无论是在read中还是dirty中），
// 就是只要key没有被删除，就返回当前的key对应的value值，否则将存储传入的value值，
// 第二返回参数是一个bool值，表示最后执行的是load操作还是store操作
func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
 // 还是优先检查read，避免加锁
 read, _ := m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
  // 尝试load和store操作，如果ok为true，表示load成功
  actual, loaded, ok := e.tryLoadOrStore(value)
  if ok {
   return actual, loaded
  }
 }

 m.mu.Lock()
 // 双重检查
 read, _ = m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok {
  // e.p为expunged状态，表示m.dirty非空且dirty不存在该key
  // 需要将key-value加到dirty中，这里dirty和read实际上key
  // 指向的是同一个e，更新e值，dirty和read中都存有该key-value了
  if e.unexpungeLocked() {
   m.dirty[key] = e
  }
  actual, loaded, _ = e.tryLoadOrStore(value)
 } else if e, ok := m.dirty[key]; ok {
  // key在dirty中不在read中，
  actual, loaded, _ = e.tryLoadOrStore(value)
  m.missLocked()
 } else {
  if !read.amended {
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
  }
  m.dirty[key] = newEntry(value)
  actual, loaded = value, false
 }
 m.mu.Unlock()

 return actual, loaded
}

func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) {
 p := atomic.LoadPointer(&e.p)
 // key已被删除，需要进一步判断处理，这里先终止处理
 if p == expunged {
  return nil, false, false
 }
 // key存在，value值有效，直接返回之前的value值，即执行Load操作
 if p != nil {
  return *(*interface{})(p), true, true
 }

 // 走到这里说明key也是已经被删除，e.p为nil,并且dirty是空的，所以直接将i存储在e.p中即可，不用关心dirty
 ic := i
 for {
  // 原子更新e.p的值，更新前为nil
  if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
   return i, false, true
  }
  // 进一步判断e.p是不是被别的地方已经修改为非nil了
  p = atomic.LoadPointer(&e.p)
  // 如果p为expunged，说明key在其他地方已经被删除了，需要进一步判断处理，这里先终止处理
  if p == expunged {
   return nil, false, false
  }
  // e.p已经被其他地方设置值了，这里直接返回已设置的值
  if p != nil {
   return *(*interface{})(p), true, true
  }
 }
}

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