golang中sync.map的实现

sync.map

适用于读多写少的场景。对于写多的场景,会导致 read map 缓存失效,需要加锁,导致冲突变多;而且由于未命中 read map 次数过多,导致 dirty map 提升为 read map,这是一个 O(N) 的操作,会进一步降低性能。

  type Map struct {
    //当涉及到dirty数据的操作的时候,需要使用这个锁
    mu Mutex
    // 一个只读的数据结构,因为只读,所以不会有读写冲突。
    // 所以从这个数据中读取总是安全的。
    // 实际上,实际也会更新这个数据的entries,如果entry是未删除的(unexpunged), 并不需要加锁。如果entry已经被删除了,需要加锁,以便更新dirty数据。
    read atomic.Value // readOnly
    // dirty数据包含当前的map包含的entries,它包含最新的entries(包括read中未删除的数据,虽有冗余,但是提升dirty字段为read的时候非常快,
        不用一个一个的复制,而是直接将这个数据结构作为read字段的一部分),有些数据还可能没有移动到read字段中。
    // 对于dirty的操作哦需要加锁,因为对它的操作可能会有读写竞争。
    // 当dirty为空的时候, 比如初始化或者刚提升完,下一次的写操作会复制read字段中未删除的数据到这个数据中。
    dirty map[interface{}]*entry
    // 当从Map中读取entry的时候,如果read中不包含这个entry,会尝试从dirty中读取,这个时候会将misses加一,
    // 当misses累积到 dirty的长度的时候, 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁。
    misses int
  }

互斥量 mu 保护 read 和 dirty。

read 是 atomic.Value 类型,可以并发地读。但如果需要更新 read,则需要加锁保护。对于 read 中存储的 entry 字段,可能会被并发地 CAS 更新。但是如果要更新一个之前已被删除的 entry,则需要先将其状态从 expunged 改为 nil,再拷贝到 dirty 中,然后再更新。

dirty 是一个非线程安全的原始 map。包含新写入的 key,并且包含 read 中的所有未被删除的 key。这样,可以快速地将 dirty 提升为 read 对外提供服务。如果 dirty 为 nil,那么下一次写入时,会新建一个新的 dirty,这个初始的 dirtyread 的一个拷贝,但除掉了其中已被删除的 key。

每当从 read 中读取失败,都会将 misses 的计数值加 1,当加到一定阈值以后,需要将 dirty 提升为 read,以期减少 miss 的情形。


    type readOnly struct {
          m       map[interface{}]*entry
          amended bool // 如果Map.dirty有些数据不在中的时候,这个值为true
  }

都是先从操作m.read开始的,不满足条件再加锁,然后操作m.dirty。

原文地址:https://www.cnblogs.com/forgo/p/15072615.html