请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

关于sync.Map问题

老师你好,可以麻烦在讲解下延迟删除的具体流程吗?以及map删除时状态nil和expunged的区别和转换的时机是什么时候呢?

正在回答 回答被采纳积分+3

2回答

少林码僧 2024-03-21 16:17:36

从上面的代码中我们可以看出,当key在read中时

 if ok {
    return e.delete()
  }

e.delete是将e.p设置为nil,将read中的对应entry指针中的p置为nil,注意置为nil之后,entry作为map的元素,其空间其实并不会被回收.

标记为nil,说明是正常的delete操作,此时dirty中不一定存在

(1)dirty赋值给read后,此时dirty不存在 

(2)dirty初始化后,肯定存在

标记为expunged,说明是在dirty初始化的时候操作的,此时dirty中肯定不存在。

为什么dirty是直接删除,而read是标记删除?

read的作用是在dirty前头优先度,遇到相同元素的时候为了不穿透到dirty,所以采用标记的方式。 同时正是因为这样的机制+amended的标记,可以保证read找不到&&amended=false的时候,dirty中肯定找不到

为什么dirty是可以直接删除,而没有先进行读取存在后删除?

删除成本低。读一次需要寻找,删除也需要寻找,无需重复操作。

我们继续来看写入操作:

// unexpungeLocked 将 expunged 的标记变成 nil。
func (e *entry) unexpungeLocked() (wasExpunged bool) {
  return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
// storeLocked 将 entry.p 指向具体的值
func (e *entry) storeLocked(i *interface{}) {
  atomic.StorePointer(&e.p, unsafe.Pointer(i))
}
// tryExpungeLocked 尝试 entry.p == nil 的 entry 标记为删除(expunged)
func (e *entry) tryExpungeLocked() (isExpunged bool) {
  p := atomic.LoadPointer(&e.p)
  // for 循环的作用,可以保证 p != nil,
  // 保证写时复制过程中,p == nil 的情况不会被写到 dirty map 中。
  for p == nil {
    if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
      return true
    }
    p = atomic.LoadPointer(&e.p)
  }
  return p == expunged
}
// dirtyLocked 写时复制,两个 map 都找不到新增的 key 的时候调用
func (m *Map) dirtyLocked() {
  // if !read.amended {...}
  if m.dirty != nil {
    return
  }
  // 遍历 readOnly map,把里面的内容都复制到新创建的 dirty map 中。
  read, _ := m.read.Load().(readOnly)
  m.dirty = make(map[interface{}]*entry, len(read.m))
  for k, e := range read.m {
    // tryExpungeLocked 将 entry.p == nil 设置为 expunged,
    // 遍历之后,所有的 nil 都变成 expunged 了。
    // 返回 false 说明 p 是有值的,要拷贝到 dirty 里。
    // Delete 操作会把有值的状态,转移为 nil,
    // 并不会把 expunged 状态转移为 nil
    if !e.tryExpungeLocked() {
      // 如果没有被删除,拷贝到 dirty map 中。
      m.dirty[k] = e   
 }
  }
}


func (m *Map) Store(key, value interface{}) {
  // 如果 readOnly map 有对应的 key,
  // 通过 e.tryStore 直接写入
  // 注意,tryStore 会在 entry.p == expunged 的情况下失败。
  read, _ := m.read.Load().(readOnly)
  if e, ok := read.m[key]; ok && e.tryStore(&value) {
    return
  }
  // readOnly map 找不到,或者 key 被删除了,
  // 那就写到 dirty map 里面。
  m.mu.Lock()
  read, _ = m.read.Load().(readOnly)
  if e, ok := read.m[key]; ok {
    // unexpungeLocked 将 expunged 的标记变成 nil。
    // 当 entry.p == expunged,并且成功替换为 nil,返回 true。
    // 
    // 这个分支的意义在于,写时复制 dirtyLocked 的时候, 数据从 readOnly map 搬迁到 dirty map 中,
    // 如果 p 是被删除的,dirty 是不会有这个 key 的,所以要把它也写进 dirty 中,保证数据的一致性。
    if e.unexpungeLocked() {
      m.dirty[key] = e    
      }
    // 写入值。
    e.storeLocked(&value)
  } else if e, ok := m.dirty[key]; ok {
    // 如果 dirty map 存在就直接更新进去,这个很好理解,
    // 因为 readOnly map 找不到会来 dirty 查。
    e.storeLocked(&value)
  } else {
    // 两个 map 都找不到的时候,说明这是一个新的 key。
    // 
    // 1. 如果 dirty 之前被提升为 readOnly,那就导一份没有被删除的 key 进来。
    if !read.amended {
      // 初始化 m.dirty,并把值写进去(写时复制)
      m.dirtyLocked()
      // amended 设置为不一致。
      // amended 表示 dirty 是否包含了 readOnly 没有的记录,
      // 很明显,read.m[key] 是 !ok 的,
      // 下面把值存到 dirty map 里面了。
      m.read.Store(readOnly{m: read.m, amended: true})
    }
    // 2. 这里,把值存到 dirty map 中。
    m.dirty[key] = newEntry(value)
  }
  m.mu.Unlock()}




entry的指针一共有三个可选值,nil、expunged和指向真实的元素。

主要是两个操作会引起p状态的变化:Store(新增/修改) 和 删除

Store(新增/修改):
在Store更新时,如果key在read中存在,并且被标记为已删除,会将kv加入dirty,此时read中key的p指向的是expunged,经过unexpungeLocked函数,read中的key的p指向会从expunged改为nil,然后经过storeLocked更新value值,p从指向nil,改为指向正常              (p->expunged) =====> (p->nil) =====> (p->正常)

在Store增加时,如果需要从read中刷新dirty数据,会将read中未删除的元素加入dirty,此时会将所有指向nil的p指针,改为指向expunged           (p->nil) =====> (p->expunged)

 删除(Delete)

在Delete时,删除value时,p从指向正常值,改为指向nil  (p->正常) =====> (p->nil)

0 回复 有任何疑惑可以回复我~
少林码僧 2024-03-21 16:17:26

直接看核心源码:

// 标志该值已经从map的read中删除且不存在于dirty中。
var expunged = unsafe.Pointer(new(interface{}))
type entry struct {
    // p为指针,可指向:
  // -> nil,表示对应键值已从map的read中删除,但存在于dirty中
  // -> expunged,表示对应键值已从map中删除,但不存在于dirty中
  // -> 其他地址,指向真实数据
  //可见value是个指针类型,虽然read和dirty存在冗余情况(amended=false),但是由于是指针类型,所以实际存储的值指向同一块内存空间
    p unsafe.Pointer
}

func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
  read, _ := m.read.Load().(readOnly)
  e, ok := read.m[key]
  // key 不存在的时候并且 readOnly map 和 dirty map 不一致时,
  // 把 dirty map 对应的记录删了。
  if !ok && read.amended {
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    e, ok = read.m[key]
    if !ok && read.amended {
      // 数据不一致的时候,最终读出来的值以 dirty map 为主,
      // 即使 readOnly map 是 !ok 的,但 dirty map 可能是 ok 的,
      // 既然值可能是存在的,那就读取出来。
      e, ok = m.dirty[key]
      // 删除操作
      delete(m.dirty, key)
      // 递增数据不一致的计数器。
      // 太多不一致会把 dirty map 提升为 readOnly map。
      这里在dirty map 提升为 readOnly map时,先将dirty拷贝给readOnly,再将dirty 设置为nil,dirty 会交给go的垃圾回收器进行回收
      也就是删除具体key的时候只做标记,最后触发dirty map 提升为 readOnly map时会统一由GC负责回收内存空间
      m.missLocked()
    }
    m.mu.Unlock()
  }
  // key 存在的时候,把 key 置为 nil,注意这里不是 expunged
  if ok {
  //采用标记的方式删除
    return e.delete()
  }
  return nil, false
}


 dirty map 提升为 readOnly map时,先将dirty拷贝给readOnly,再将dirty 设置为nil,dirty 会交给go的垃圾回收器进行回收
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
}

// Delete deletes the value for a key.func (m *Map) Delete(key interface{}) {
  m.LoadAndDelete(key)
}
// delete 将对应的 key 置为 nil!而不是 expunged!

func (e *entry) delete() (value interface{}, ok bool) {
  for {
    p := atomic.LoadPointer(&e.p)
    if p == nil || p == expunged {
      return nil, false
    }
    if atomic.CompareAndSwapPointer(&e.p, p, nil) {
      return *(*interface{})(p), true
    }
  }}


0 回复 有任何疑惑可以回复我~
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信