Go sync.Map

• map并发读线程安全，并发读写线程不安全。
• sync.Map 读写分离 空间换时间

Map

Golang1.6之前内置的map类型是部分goroutine安全的，并发读是没有问题的，但并发写则会报错。换言之，Golang中map只读是线程安全的（thread-safe），但在并发环境下读写是线程不安全的（写线程不安全），为什么呢？

例如：并发环境下同时读写map会发生致命错误，即多个goroutine同时读写一个map时会报错。

$ vim map_test.go

package test

import "testing"

func TestMap(t *testing.T){
    //创建int到int的映射
    m := make(map[int]int)
    //开启并发执行单元 用于写入
    go func(){
        //循环对map进行写入
        for{
            m[1] = 1
        }
    }()
    //开启并发执行单元 用于读取
    go func(){
        for{
            _ = m[1]
        }
    }()
    //无线循环让并发程序在后台一直执行
    for{

    }
}

$ go test map_test.go -v -run=TestMap
fatal error: concurrent map read and map write

致命错误: 并发的map读和map写

由于两个并发执行单元同时不断地对map进行读和写而产生了竞态问题，map内部会对这种并发操作进行检查并提前发现。

清理

map在Golang中是只增不减的一种数组结构，使用delete删除的时候会打标记，以说明该内存空间empty了，但不会立即回收。手工回收还需设置为nil。

package test

import (
    "log"
    "runtime"
    "testing"
)

func statMem(msg string){
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    log.Printf("%v: Alloc = %vKB, NumGC = %v\n", msg, m.Alloc / 1024, m.NumGC)
}

var m map[int]int
func TestMap(t *testing.T){
    statMem("BEGIN")

    //添加map值
    cnt := 10000
    m = make(map[int]int, cnt)
    for i:=0; i<cnt; i++{
        m[i] = i
    }

    //手工GC
    runtime.GC()
    statMem("GC")

    //手工nil
    m = nil
    runtime.GC()
    statMem("NIL")
}

$ go test map_test.go -v -run=TestMap
2021/04/12 18:40:36 BEGIN: Alloc = 193KB, NumGC = 0
2021/04/12 18:40:36 GC: Alloc = 492KB, NumGC = 1
2021/04/12 18:40:36 NIL: Alloc = 142KB, NumGC = 2

sync.RWMutex

• 利用传统的sync.RWMutex + map实现并发安全的map
• sync.RWMutex加锁的方式相当于MySQL中的表级锁

采用嵌入struct为map增加读写锁

var counter = struct{
    sync.RWMutex
    m map[string]int
}{
    m:make(map[string]int),
}

读取和写入数据时都可以很方便地加锁

• 读取数据时，采用读锁锁定。
• 写入数据时，采用写锁锁定。

counter.RLock()
val := counter.m["key"]
counter.RUnlock()
log.Println(val)

counter.Lock()
counter.m["key"]++
counter.Unlock()

• 并发读写时加锁，由于锁的粒度为整个map因此会存在优化的空间，因此性能并不很很高。
• 并发环境下由于锁的存在，同时只能有一个goroutine在临界区工作，因此效率会被大大降低。
• 当map数据非常大的情况下，一把锁会导致大并发的客户端共争一把锁。

Java的ConcurrentHashMap的解决方案会采用shard即在内部使用多个锁，每个区间共享一把锁，这样减少数据共享一把锁带来的性能影响。

sync.Map

Golang在1.9版本中提供了一种效率较高且并发安全的sync.Map，sync.Map与普通map不同，它不是以语言原生态的形式提供，而是在sync包下的特殊结构。

m := sync.Map{}
m.Store(1, 1)

cnt := 10000
go func(){
    i := 0
    for i<cnt {
        m.Store(i, i)
        i++
    }
}()

go func(){
    i := 0
    for i<cnt {
        m.Load(i)
        i++
    }
}()

time.Sleep(time.Second)
fmt.Println(m.Load(1))

• sync.Map除了互斥量之外，还运用了原子操作。
• sync.Map的思路来自于Java的ConcurrentHashMap
• sync.Map其实也相当于表级锁，只不过将读写进行分离，但本质依然是一样的。

Golang1.9中的sync.Map是如何提升对map的优化，解决并发提升的性能的呢？

• 优化的方向：把锁的粒度尽可能降低来提高运行速度
• 空间换时间，通过冗余的两个数据结构read和dirty实现加锁对性能的影响。
• 使用只读数据read来避免读写冲突
• 动态调整，当miss次数多了之后会将dirty数据提升为read。
• 双检查（double-checking）
• 延迟删除，删除一个键值只是打标记，只有在提升dirty的时候才会清理删除的数据。
• 优先从read中读取、更新、删除，因为对read的读取不需要锁。

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

sync.Map的数据结构很简单，包含四个字段mu、read、dirty、misses，它使用了冗余的数据结构read和dirty。dirty中会包含read中未删除的实体，新增的实体会加入到dirty中。

实现

sync.Map的实现思路可概括为：读写分离、空间换时间

• 通过read和dirty字段将读写分离，读的数据只存在只读字段read上，最新写入的数据则存在dirty字段上。
• 读取时会先检查read字段是否存在，若不存在则查询dirty字段。
• 写入时则只会写入到dirty字段
• 读取read字段并不需要加锁，但从dirty字段读取或写入时都需要加锁。
• 另外还提供了misses字段来统计read字段被穿透的次数，所谓的被穿透也就是说需要读取dirty字段的情况，当超过一定次数时则将dirty字段数据同步到read字段上。
• 删除数据时则直接通过标记来延迟删除

sync.Map

sync.Map特性

• sync.Map无需初始化，直接声明即可使用。
• sync.Map不能使用map的方式进行取值或设置，必须使用sync.Map专有的方法执行增删改查操作。
• sync.Map配合回调函数进行遍历，可通过回调函数返回内部遍历的值。

sync.Map中实际上存在两个map，一个是专门用于读操作的read map，使用atomic.Value方式存储。另一个是专门用于读写操作的dirty map，单纯使用map方式存储。

使用时会优先读read map，若不存在则加锁穿透读dirty map，同时会记录一条未从read map读到的计数。当计数值达到一定值，就会将read map用dirty map进行覆盖。

sync.Map通过空间换时间与读写分离的方式，适用于大量读少量写的应用场景。不适用于大量写的场景，因为大量写的场景会导致read map读不到数据而进一步加锁读取，同时dirty map也会一直晋升为read map，整体性能会比较差。

readOnly

read map的数据结构

type readOnly struct{
  m map[interface{}]*entry
  amended bool //若dirty中数据m不一致则为false
}

amended字段指明了Map.dirty中是否存在readOnly.m未包含的数据，若从Map.read字段中找不到数据的话，会进一步到Map.dirty中查找。另外对Map.read的修改是通过原子操作进行的。

虽然read和dirty存在冗余数据，但这些数据是通过指针指向同一个数据，所以尽管Map的value会很大，但冗余空间占用的还是很有限的。

entry

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

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

指针p具有三种值

• nil：entry已经被删除同时m.dirty为nil
• expunged：entry已被删除且m.dirty不为nil，同时这个entry不存在于m.dirty中。
• entry是一个正常的值

方法

Store

• 新增元素，写操作。Store可能会在某些情况下下，比如初始化或m.dirty刚被提升后，从m.read中复制数据，若此时m.read中数据量比较大，则可能会影响性能。

//写操作
func (m *Map) Store(key, value interface{})

Store

Load

• 读操作，提供一个键key来查找对应的值value，若不存在则通过ok反映。

// 读操作
func (m *Map) Load(key interface{}) (value interface{}, ok bool)

Load

Delete

Delete

由于数据可能存在两份，因此删除时必须考虑

• 若read map和dirty map都有，则认为是干净数据。
• 若read map没有而dirty map中有，则dirty map中存在还未升级的藏数据。
• 若read map存在而dirty map中不存在，则标记为待删除数据。

删除一个键值，删除操作是从m.read中开始的若此时entity中不存在于m.read中，同时m.dirty中存在新数据，则会加锁并尝试从m.dirty中删除元素。

删除操作是需要经过双检查的，从m.dirty中直接删除即可，就当它没有存在过。但如果从m.read中删除则并不会直接删除而会打标记。

Range

由于for...range是Golang内建的语言特性，所有没有办法使用for...range遍历sync.Map，但可以使用它的Range方法通过回调的方式来遍历。