> For the complete documentation index, see [llms.txt](https://wtifs.gitbook.io/diva-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wtifs.gitbook.io/diva-notes/go/5.-bing-fa-bian-cheng/25.sync.map-de-shi-xian.md).

# 2-5.sync.Map的实现

## 概述

和 JAVA 中 `concurrent hashmap` 分段的设计思路不同，`sync.Map` 的主要思想是做读写分离，底层用了2个 `map`，`read` 和 `dirty`，将频繁变更的数据，和极少变更的数据分离。

极少变更的数据放到 `read` 里，读 `read` 无需加锁，更新 `read` 依靠 `CAS` 也不用加锁，性能极高。

新增的数据放到 `dirty` 里。这类数据的读写需要加锁。

读取数据时，先查 `read`，再查 `dirty`，当读 `read` cache miss 累计到一定次数时，说明该 `key` 读多写少了，将数据从 `dirty` 移入 `read`

## 实现

### 数据结构

```go
// src/sync/map.go
type Map struct {
    // 当涉及到脏数据(dirty)操作时候，需要使用这个锁
    mu Mutex
    
    // read 字段指向下面的 readOnly 结构，里面有个 map
    // 【读/更新】不需要加锁，只需要通过 atomic 加载最新的指针即可
    read atomic.Value 
    
    // dirty 包含部分 map 的键值对，如果操作需要 mutex 获取锁
    // 【新增】键值时写入这个字段
    dirty map[interface{}]*entry
    
    // misses是一个计数器，用于记录read中没有的数据而在dirty中有的数据的数量。
    // 也就是说如果read不包含这个数据，会从dirty中读取，并misses+1
    // 当misses的数量等于dirty的长度，就会将dirty中的数据迁移到read中
    misses int
}
```

**read的数据结构 readOnly：**

```go
// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m 包含所有只读数据，不会进行任何的数据增加和删除操作 
    // 但是可以修改 entry 的指针（即更新 value），因为这个不会导致map的元素移动
    m map[interface{}]*entry
    
    // 标志位，如果为true则表明当前read只读map的数据不完整，dirty map中包含部分数据
    amended bool // true if the dirty map contains some key not in m.
}
```

**entry**

```go
type entry struct {
    p unsafe.Pointer // *interface{}
}
```

p有三种值：

* nil: entry已被删除了，并且m.dirty为nil
* expunged: entry已被删除了，并且m.dirty不为nil，但这个entry在于m.dirty中
* 其它：entry是一个正常的值

### 查找

先查找 `read` ，`read` 中没有再查找 `dirty` 、并增加 `cache misses` 计数

`cache misses` 数量累计至 `dirty` 的长度后，将 `dirty` 所有数据迁移至 `read` 中，并清空 `dirty`

```go
// src/sync/map.go

// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 先从只读 read 的 map 中查找，这时不需要加锁
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    
    // 如果没有找到，并且 read.amended 为 true，说明 dirty 中有新数据，从 dirty 中查找，开始加锁了
    if !ok && read.amended {
        m.mu.Lock() // 加锁
        
       // 又在 readonly 中检查一遍，因为在加锁的时候 dirty 的数据可能已经迁移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        // read 还没有找到，并且dirty中有数据
        if !ok && read.amended {
            e, ok = m.dirty[key] //从 dirty 中查找数据
            
            // 不管m.dirty中存不存在，都在missLocked() 中将 misses + 1。misses = len(m.dirty)时就会把 dirty 中的数据迁到 read 中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

 // 如果数据不在 read 中，经过几次 miss 后，dirty 中的数据便会迁移到 read 中，这时又可以从 read 中查找到
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) { //misses 次数小于 dirty 的长度，就不迁移数据，直接返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //开始迁移数据
    m.dirty = nil   //迁移完 dirty 就赋值为 nil
    m.misses = 0    //迁移完 misses 归0
}
```

### 新增和更新

如果 `read` 中已有 `key`，通过 `CAS` 来更新值

新增 `key`，或者更新 `dirty` 中的数据，需要加锁并写入 `dirty`。其中新增 `key` 时还会把 `read` 中的 kv 倒灌回 `dirty`

```go
// src/sync/map.go

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在 read 中查找值，找到了，就尝试 tryStore 更新值, tryStore 里使用 for 循环 + CAS 的方式进行更新
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok { // double check，因为 lock 前 read 里可能又有了
        if e.unexpungeLocked() {  // 未被标记成删除
            m.dirty[key] = e      // 加入到 dirty 里
        }
        e.storeLocked(&value)             // 设置值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中，直接更新
        e.storeLocked(&value)
    } else {                // read 和 dirty 中都没有，即插入新数据
        if !read.amended {  // if dirty 为空，即向 dirty 中第一次加载数据
            m.dirtyLocked() // 会将 read 里的所有数据加载到 dirty 中，并将 read 里的键值标记为 expunged
            m.read.Store(readOnly{m: read.m, amended: true}) // 将 read.amended 字段标记为true，下次查找会启用dirty查找
        }
        m.dirty[key] = newEntry(value) // 将这个entry加入到m.dirty中
    }
    m.mu.Unlock()
}

func (e *entry) tryStore(i *any) bool {
	  for {
		    p := atomic.LoadPointer(&e.p)
		    if p == expunged {
			      return false
		    }
		    if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
			      return true
		    }
	  }
}

// 遍历 read 中的 key 并写入 dirty
// 这个效率应该很差吧
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
		}
	}
}
```

### 删除

和新增差不多，只不过不设置值了，而是调用底层 `map` 的 `delete` 方法

## 总结

仅建议用于如下两种场景：

1. 写一次，读多次。比如程序初始化时加载配置。
2. 多协程环境下，不同协程读写不同的key。

这两种场景下，相比于使用原生map + 全局锁的情况，`sync.Map` 能显著优化加锁带来的性能开销。

如果是读写穿插的情况，会频发触发 `dirtyLocked` 函数，里面会遍历 `map` 的 `key` 并进行迁移，效率非常差。

## 问题

既然读写 `read` 可以 `CAS`，那只要 `read` 不要 `dirty` 可不可以？

* 那同原生 `map` 就没有区别了。`sync.Map` 中，`read` 仅用于读和更新已有 `key`（这俩场景才能用 `CAS`），无法用于新增 `key` 和触发扩容，后者的场景就需要用到 `dirty` 了。