数据结构

type Map struct {
    mu Mutex

    // read contains the portion of the map's contents that are safe for
    // concurrent access (with or without mu held).
    //
    // The read field itself is always safe to load, but must only be stored with
    // mu held.
    //
    // Entries stored in read may be updated concurrently without mu, but updating
    // a previously-expunged entry requires that the entry be copied to the dirty
    // map and unexpunged with mu held.
    read atomic.Value // readOnly

    // dirty contains the portion of the map's contents that require mu to be
    // held. To ensure that the dirty map can be promoted to the read map quickly,
    // it also includes all of the non-expunged entries in the read map.
    //
    // Expunged entries are not stored in the dirty map. An expunged entry in the
    // clean map must be unexpunged and added to the dirty map before a new value
    // can be stored to it.
    //
    // If the dirty map is nil, the next write to the map will initialize it by
    // making a shallow copy of the clean map, omitting stale entries.
    dirty map[interface{}]*entry

    // misses counts the number of loads since the read map was last updated that
    // needed to lock mu to determine whether the key was present.
    //
    // Once enough misses have occurred to cover the cost of copying the dirty
    // map, the dirty map will be promoted to the read map (in the unamended
    // state) and the next store to the map will make a new dirty copy.
    misses int
}

使用 m.read 是只读视图减少加锁, m.dirty是 写视图, m.dirty 会同步到 m.read, m.dirty的操作是需要加锁的, misses的统计作为 m.dirty同步到 m.read的条件

常规实现

1.Store Store(k, v)的时候, 会先将数据写入到 m.dirty 中. Load的时候, 因为只有m.dirty中有数据, 所以最终是从 m.dirty中获取数据的. 当频繁查询数据的时候, 临界条件: m.misses >= len(m.dirty), 就会将数据 放入 m.read 中, 实现加速查询, 因为 m.read 是只读的, 所以实现上并没有加锁. 这个时候有几个状态需要处理.

  1. 又加入/修改新的key-value, m.read 并不会立即反映出这个变化, 内部怎么实现呢? 这种情况下， m.read 就会标记上 amended: true 的标记, 这样, 在读取的时候, 如果 m.read 查询不到, 并且 m.read 是 amended: true 的标记, 就会从 m.dirty中寻找,同样, 如果m.dirty 查询次数超过了临界值, 会将dirty的数据放到 m.read 中.

  2. 如果修改 read中已经存在的数据呢? 会修改m.read中的数据, 如果这个时候m.dirty正在从 m.read同步数据的话, 存在静态条件. 2.1 m.read 需要修改数据, 2.2 m.dirty需要复制 m.read 的数据, 如果是nil不复制. 2.3 冲突的场景: 当delete 在 store 的情况下, m.read的修改的数据会丢失, 导致数据丢失. 2.4 解决方法: 新增一个状态值: expunged = unsafe.Pointer(new(interface{})), 通过cas实现, 同时, 在 m.read修改数据的时候, 如果 m.read的数据是 nil 或者 expunged, 就在dirty中添加key/value, 保证数据对齐.

  3. Load 会先尝试从 m.read 中读取, 这种不需要加锁. m.read中不存在, 通过标记判断是否存在 m.dirty 中, 尝试获取

  4. Delete 同上, 不过变成了 delete 操作

特殊的处理:

为了减少内存的压力, 当进行m.read同步的时候, m.dirty会被清空. 当重新加入新的值, m.dirty 会从m.read同步回数据, 在添加新的值. 在同步的时候, 需要处理delete的情况, 如果 之前key被删除过, 在 m.read 中还是存在的, 只是内部p的指针是nil, 所以, 在同步处理的时候, 需要通过cas操作将 p的值 重置成 expunged, 避免了加锁.