go源码系列之sync.Map

map的结构体定义

type Map struct {
  //此锁是为了维护Map的dirty数据
  mu Mutex
  //用来存读的数据，只对类型，不会造成读写抵触
  read atomic.Value 
  dirty map[interface{}] *entry
  //当读数据时分，该字段不在read中，测验从dirty中读取，不论是否在dirty中读取到数据，missed+1
  //当累计到len(dirty) 时，会将dirty拷贝到read，并将dirty清空，以此提高读功能
  missed int
}

在sync.Map中用到了冗余数据结构read、dirty。其间read的类型是atomic.Value，它会经过atomic.Value的Load办法将其断语为readOnly目标，因而read的实际类型为readOnly

read, _ := m.read.Load().(readOnly)

readOnly的数据结构如下

type readOnly struct {
  m map[interface{}]*entry
  //当sync.Map.dirty中包含了某些不存在的key时，amend的值为true
  amended bool
}

• amend属性的作用是志明dirty中是否有readOnly.m中未包含的数据，因而当对sync.Map的读操作在read中找不到数据时分，将进一步在dirty中查找

• readOnly.m和Map.dirty中map存储的值类型是*entry,它包含一个指针p，指向存储的value值。

type entry struct {
  p unsafe.Pointer
}

entry.p的值有三种类型

• nil:entry现已被删去，且m.dirty为nil
• expunged:entry被删去，m.dirty不为nil，但entry不存在m.dirty中
• 其他：entry有效，记录在m.read中，若dirty不为空，也会记录在dirty中

虽然read和dirty存在冗余数据，可是这些数据entry是经过指针指向的，因而，尽管map的value可能会很大，可是空间存储还是足够。

办法

sync.Map有四个办法完成，分别是Load、Store、Delete和Range

Load

加载办法，经过提供的key，查找对应的值value

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
  //从m的read中经过Load办法得到readOnly
  read, _ := m.read.Load().(readOnly)
  //从read的m中查找key
  e, ok := read.m[key]
  //假如在read中没有找到，且标明有新数据在dirty中
  //那么在dirty中查找
  if !ok &&read.amended {
    m.mu.Lock()
    //两层检查防止在本次加锁的时分，有其他的goroutine正好将map中的dirty数据复制到了read中
    //Map.read的并发安全性确保就在他的修正是经过原子操作的，因而需要再一次的load
    read, _ = m.read.Load().(readOnly)
    e, ok := read.m[k]
    if !ok && read.amended {
      e, ok := m.dirty[key]
      //不论是否从dirty中找到数据，都要讲missed加一
      m.missLocked()
    }
    m.mu.Unlock()
  }
  if !ok {
    return nil, false
  }
  //经过map的load办法，将entry.p加载为对应的指针，再回来指针指向的值
  return e.load()
}

Map的missLocked函数是确保sync.Map功能的重要函数，他的目的是将存在有所的dirty中的数据，转移导只读现成安全的read中去

func (m *Map) missLocked() {
  m.misses++
  if m.misses < len(m.dirty) {
    return
  }
  //将dirty复制到read中
  m.read.Store(readOnly{m: m.dirty})
  m.dirty = nil //将dirty清空
  m.misses = 0  //计数清零
}

Store

该办法用于更新或许新增键值对key-value

func (m *Map) Store(key,value interface{}) {
  //假如read中存在该兼职，且兼职美哦与被删去，则测验直接存储
  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 {
    //判别entry是否被符号删去
    if e.unexpungeLocked() {
      //假如entry被符号删去，则将entry参加导dirty中
      m.dirty[key] = e
    }
    //更新entry指向的value地址
    e.storeLocked(&value)
  }else if e,ok := m.dirty[key];ok { //dirty中有该键值，则更新
    e.storeLocked(&value)
  }else{ //dirty和read中均无该键值
    if !read.amended {
      m.dirtyLocked() //从m.read中复制未删去的数据导dirty中
      m.read.Store(readOnly{m:read.m, amended:true})
    }
    //将entry添加到dirty中
    m.dirty[key] = newEntry(value)
  }
}

Store每次的操作都是从read开始的，先不满足条件时，才加锁操作dirty。可是因为存在从read中复制数据的状况，当m.read中数据量很大的状况，会对功能造成影响。

Delete

删去某个键值

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()
  }
}
func (e *entry) delete()(hadValue bool) {
  for {
    p := atomic.LoadPointer(&e.p)
    //假如p指针为空，或许被符号清除
    if p == nil || p ==  expunged {
      return false
    }
    //经过原子操作将e.p符号为nil
    if atomic.CompareAndSwapPointer(&e.p, p, nil{
      return true
    }
  }
}

Delete中的逻辑和Store逻辑相似，都是从read开始，假如这个key不在read中，且dirty中有新的数据，则加锁从dirty中删去，而且需要做两层检查。

Range

想要遍历sync.Map，不能经过for range的形式，因而他本身提供了Range办法，经过回调方法遍历

func (m *Map) Range(f func(key, value interface{}) bool) {
  read, _ := m.read.Load().(readOnly)
  if read.amended {
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if read.amended  {
      //将dirty复制到read中
      read = readOnly{m:m.dirty}
      m.read.Store(read)
      m.dirty = nil
      m.misses = 0
    }
    m.mu.Unlock()
  }
  //遍历整理过后的read
  for k,e := range read.m {
    v, ok := e.load()
    if !ok {
      continue
    }
    if !f(k,v) {
      break
    }
  }
}

sync.Map总结

• 空间换时刻：经过两个冗余的数据结构（read、dirty），削减锁对功能的影响
• 读操作运用read，防止读写抵触
• 动态调整，经过misses值，防止dirty数据过多
• 双检查机制：防止在非原子操作是产生过错
• 延迟删去机制：删去一个键值仅仅先打符号，只有等提高dirty（复制到read中，并清空本身）时才清理删去的数据。
• 优先从read中读、改和删去，因为对read操作不用加锁，大大提高功能。

运用示例

func main() {
  var sm sync.Map
  sm.Store(1,"a")
  sm.Store(2,"b")
  sm.Store("c",3)
  if v, ok := sm.Load("c"); ok {
    fmt.Println(v)
  }
  //删去
  sm.Delete(1)
  //遍历
  //参数func中的参数是遍历取得的key和value，回来一个bool值
  sm.Range(func(key,value interface{}) bool {
    fmt.Println(key, value)
    return true
  })
}