Go语言——sync.Map详解

sync.Map是1.9才推荐的并发安全的map，除了互斥量以外，还运用了原子操作，所以在这之前，有必要了解下Go语言——原子操作

struct

go1.10\src\sync\map.go

type Map struct {
   mu Mutex
    
   read atomic.Value // readOnly

   dirty map[interface{}]*entry

   misses int
}

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

• read: readOnly, 保存了map中可以并发读的数据。并发写有可能不需要互斥，但是更新之前标记删除的数据（从一个value指针变成expunged指针），就需要将条目拷贝到dirty中，并且unexpunged操作（？还不懂什么意思，将expunged指针变成value指针？）需要锁。
• dirty: 脏数据需要锁。为了尽快提升为read，dirty需要保存read中所有未标记删除的数据（减少数据拷贝？）。标记删除的条目不保存的dirty里面（那就是保存在read里面咯）
• misses: 从read里面读，miss之后再从dirty里面读。当miss多次之后，就将dirty提升为read。

type entry struct {
   // If p == nil, the entry has been deleted and m.dirty == nil.
   //
   // If p == expunged, the entry has been deleted, m.dirty != nil, and the entry
   // is missing from m.dirty.
   //
   // Otherwise, the entry is valid and recorded in m.read.m[key] and, if m.dirty
   // != nil, in m.dirty[key].
   p unsafe.Pointer // *interface{}
}

entry分为三种情况：

1. nil：已经被删除，并且dirty不存在
2. expunged：已经被删除了，dirty存在，且条目不在dirty里面。标记删除
3. 其他情况：保存在read和dirty（存在）中

Store

func (m *Map) Store(key, value interface{}) {
   read, _ := m.read.Load().(readOnly)
   if e, ok := read.m[key]; ok && e.tryStore(&value) {
      return
   }

从read中读取key，如果key存在就tryStore。

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

1. 原子地读取条目的值
2. 如果条目被标记删除了（空接口指针），返回false；按照之前的逻辑，就是说如果条目被标记了，就继续store
3. 尝试CAS新的value值，成功代表更新条目值成功。
4. CAS失败，重新原子load，继续CAS，除非发现条目被其他的G标记了。

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

func (e *entry) unexpungeLocked() (wasExpunged bool) {
   return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

注意这里开始需要加锁，因为需要操作dirty。

条目在read中，首先取消标记，然后将条目保存到dirty里。（因为标记的数据不在dirty里）

最后原子保存value到条目里面，这里注意read和dirty都有条目。

   else if e, ok := m.dirty[key]; ok {
      e.storeLocked(&value)
   } else {
      if !read.amended {
         m.dirtyLocked()
         m.read.Store(readOnly{m: read.m, amended: true})
      }
      m.dirty[key] = newEntry(value)
   }
   m.mu.Unlock()
}

1. 如果条目在dirty里，就保存value。这里注意哈，read里没有这个条目，而dirty里面有。
2. 其他情况，新增条目。将所有未标记的条目保存到dirty里面。

总结一下Store：

1. 新增操作，将条目保存在dirty里
2. 更新操作，在read中，如果没有被其他G标记，就直接在read里面更新
3. 在read中，取消标记，保存到dirty中，并且赋值
4. 在dirty中，就直接更新

这里可以看到dirty保存了数据的修改，除非可以直接原子更新read，继续保持read clean。

Load

有了之前的经验，可以猜测下load流程：

1. 先从read里面直接读
2. 加锁
3. 更新miss
4. 从dirty里面读
5. 解锁

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
   read, _ := m.read.Load().(readOnly)
   e, ok := read.m[key]
   if !ok && read.amended {
      m.mu.Lock()
      // Avoid reporting a spurious miss if m.dirty got promoted while we were
      // blocked on m.mu. (If further loads of the same key will not miss, it's
      // not worth copying the dirty map for this key.)
      read, _ = m.read.Load().(readOnly)
      e, ok = read.m[key]
      if !ok && read.amended {
         e, ok = m.dirty[key]
         // Regardless of whether the entry was present, record a miss: this key
         // will take the slow path until the dirty map is promoted to the read
         // map.
         m.missLocked()
      }
      m.mu.Unlock()
   }
   if !ok {
      return nil, false
   }
   return e.load()
}

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. 读了两次read，做了一个double-check
2. 更新miss还有额外操作，即dirty升级；原来miss的阈值是dirty长度。

Delete

由于数据保存两份，所以删除考虑：

1. read & dirty都有，干净的数据
2. read没有，dirty有，dirty中还未升级的数据
3. read有，dirty没有，标记删除的数据

func (m *Map) Delete(key interface{}) {
   read, _ := m.read.Load().(readOnly)
   e, ok := read.m[key]
   if !ok && read.amended {
      m.mu.Lock()
      read, _ = m.read.Load().(readOnly)
      e, ok = read.m[key]
      if !ok && read.amended {
         delete(m.dirty, key)
      }
      m.mu.Unlock()
   }
   if ok {
      e.delete()
   }
}

先看第二种情况。加锁直接删除dirty数据。思考下貌似没什么问题，本身就是脏数据。

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

第一种和第三种情况唯一的区别就是条目是否被标记。标记代表删除，所以直接返回。否则CAS操作置为nil。这里总感觉少点什么，因为条目其实还是存在的，虽然指针nil。

标记

看了一圈貌似没找到标记的逻辑，因为删除只是将他变成nil。

func (e *entry) tryExpungeLocked() (isExpunged bool) {
   p := atomic.LoadPointer(&e.p)
   for p == nil {
      if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
         return true
      }
      p = atomic.LoadPointer(&e.p)
   }
   return p == expunged
}

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

之前以为这个逻辑就是简单的将为标记的条目拷贝给dirty，现在看来大有文章。

p == nil，说明条目已经被delete了，CAS将他置为标记删除。然后这个条目就不会保存在dirty里面。

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
}

这里其实就跟miss逻辑串起来了，因为miss达到阈值之后，dirty会全量变成read，也就是说标记删除在这一步最终删除。这个还是很巧妙的。

真正的删除逻辑：

1. delete将条目变成nil
2. store的时候，将nil的条目标记，并且这些条目不会存在于dirty中
3. load的时候，如果miss达到阈值，就将dirty全量变成read，变现地删除了nil条目

很绕。。。。