在Go中, 有这样一个数据结构sync.Map, 他的出现是为了提供一个并发安全的map.

Map

在了解sync.Map之前, 我们有必要知道为什么map不是并发安全的, 这里一笔带过了.

map这个数据结构在各个语言中都有实现, 基本上大同小异, 大部分都是通过数组+链表来实现的, 在Go中也不例外. 结构大体上就是:

使用数组存储
当发生hash冲突时, 通过链表解决
当内容过大时, 进行数组扩容

这里对map的具体实现不进行过多介绍, 只思考一下为什么map不是并发安全的. 其实现源码定义在文件runtime/map.go中. 感兴趣的可以研究一下.

对于map的操作无非两种读/写. 如果只是单纯的读, 是不会有并发问题的. 而在数据发生更新时, 可能正在进行扩容, 可能正在修改链表等等. 其中每一个操作都不是原子性的, 在每一个操作中, 都可能会发生新的读写. 而此时, 内存中的数据可能是残缺的, 甚至于丢失数据. (比如两个写操作都向同一个链表末尾追加元素, 其中一个可能就丢了)

这时候如果考虑并发竞争的情况, 必然会导致执行效率的降低(因为要加锁处理). 因此, 官方的实现比较简单, 在读/写时, 若发现已经在更新了, 则报错. 报错文案如下(也定义在map.go文件中, 感兴趣的可以看一下):

// 当更新与更新冲突时
concurrent map writes
// 当读取与更新冲突时
concurrent map read and map write

其实不光是Go, 大部分语言的map都不是并发安全的, 比如Java中的HashMap.

sync.Map

如果我们来实现一个并发安全的map, 我们可以怎么做呢? 很简单, 加读写锁. 当map发生更新的时候, 所有读写操作都等待. 当map读取的时候, 写操作等待, 但并发读是没有问题的.

而sync.Map则是官方为我们提供的一个并发安全的map实现. 一起来看看官方是如何处理map的并发操作的. 结构体定义如下(以下源码分析基于版本go1.18):

type Map struct {
    // 互斥锁
    mu Mutex
    // 这是一个只读的 map. 其值为 readOnly 结构体(在下面)
    read atomic.Value // readOnly
    // 脏数据. 这个 map 用于数据更新
    dirty map[any]*entry
    // 记录在 read 中读取数据失败的次数
    misses int
}
// 内存中的只读 map
type readOnly struct {
    m       map[any]*entry
    // Map.dirty 的数据和这里的数据不一样的时候，为true
    amended bool
}

可以看到, 其内部也是通过添加互斥锁实现的. 与我们不同的是, 其内部维护了两个map, 其中一个是只读的map. 通过其结构体, 我们可以大致猜测出其实现思路, 一句话概括就是: 将map拆分出一个read只用作读取. 数据更新的时候操作dirty, 这样在读取数据时无需加锁, 提高并发性能.

读取

我们先来看一下是如何从中读取数据的:

func (m *Map) Load(key any) (value any, ok bool) {
    // 从 read 中读取数据
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 若 read 中没有读到, 且 read 与 dirty 不一致, 则从 dirty 中读取
    if !ok && read.amended {
        m.mu.Lock()
        // 这里从 read 中再读一次, 双重检查. 
        // 因为上面的 读取 与 if 判断没有加锁, 在这期间可能数据已经添加过来了    
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        // 同上, 从 dirty 中读取
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // 记录 dirty 与 read 数据不一致, 触发数据同步
            // 因为这个 key 会导致加锁操作, 所以不管数据在不在都进行记录
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

// read 中数据 miss
// 这个操作全程被锁保护着
func (m *Map) missLocked() {
    m.misses++
    // 当 miss 次数大于 map 中元素数量时, 触发数据同步
    if m.misses < len(m.dirty) {
        return
    }
    // 将 dirty 数据同步给 read
  // 这里是原子操作
    m.read.Store(readOnly{m: m.dirty})
  // 清空 dirty, 为了减少空间占用
    m.dirty = nil
    m.misses = 0
}

从这个读取操作中, 我们可以看到读取数据的步骤是:

从read中读取
若read中没有, 且与dirty存在差异, 则加锁从dirty中读取

read内容的更新也仅仅在read中, 且更新全程被锁保护.

如此, 我们能够想到的是, 添加数据的时候加锁并修改dirty同时将read.amended置为TRUE. 但是更新和删除操作如何同步给read呢?

删除

当从map中删除数据的时候, 如何通知read呢?

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
    // 以下部分做的一件事就是, 从 read/dirty 中将数据读出来
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
      // 将数据从 dirty 中删除
            delete(m.dirty, key)
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if ok {
        // 若数据存在, 调用其 delete 方法, 在下面
        return e.delete()
    }
    return nil, false
}

// 删除元素
// 其操作是, 通过原子操作将数据置为 nil
// 对应与读取时的 load 函数, 也会进行 nil 的判断
func (e *entry) delete() (value any, ok bool) {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == nil || p == expunged {
            return nil, false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return *(*any)(p), true
        }
    }
}

可以看到, 数据删除的时候, 其实map中的元素仍然在, 只是将其p字段置为nil. 这也是为了保证read的读取性能, 减少read的加锁范围及加锁时间, 所以不对read进行修改, 而仅仅是修改元素.

有没有发现, 删除操作是没有加锁的(当数据在read中存在时). 为什么嘞? 因为删除操作没有修改map, 而是仅仅修改元素. 是不是很妙?

添加

这里操作就不将所有源码都列出来了, 只列出一些主要步骤, 感兴趣的可自行查看.

添加和更新时同一个函数:

func (m *Map) Store(key, value any) {
    // 若数据在 read 中存在, 则尝试更新 read, 直接将指针指向新的地址
    // tryStore 中是一个自旋锁
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    // 全程加锁
    m.mu.Lock()
    // 这里从 read 中再读一次, 原因相同. 因为上面的读取操作没有加锁
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        // 若元素已经在 read 中被删除了, 则说明 dirty 中不存在此 key
        // 原因可看上面的删除操作, 数据在删除时会将 dirty 中对应 key 删除
        if e.unexpungeLocked() {
            m.dirty[key] = e
        }
        // 将值指向新的地址
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        // 若在 read 中没有, 但在 dirty 中存在, 则直接修改
        e.storeLocked(&value)
    } else { // 若 read/dirty 中均没有
        // 若当前 read dirty 相同
        if !read.amended {
            // dirty 数据初始化
            // 因为在 missLocked 同步数据时, 将 dirty 置为 nil 了
            // 所以这里需要对其初始化
      // 初始化操作就是, 将 read 中的所有内容赋值给 dirty
            m.dirtyLocked()
            // 将 amended 标记为 true
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        // 记录新数据
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

在添加的时候, 若数据存在则更新, 不存在则新建. 那么更新操作是如何同步给read的呢? 因为其全程使用指针存储, 不管数据从read中还是dirty中读到, 修改指针后, 双方同步修改.

总结

看了sync.Map的源码后, 确实要比我自己想的实现高明许多, 其主要设计有这么几个点:

将map单独拆分一个只读read, 这样读操作不需要加锁
数据更新全程使用指针, 既map本身没有修改, 而是修改元素. 因此也不需要加锁
数据删除将元素中的指针变量置为nil, 元素本身仍然存在. map也没有修改, 不需要加锁
等等吧…

可以看到, 通过只读map, 可以满足大量的并发读取. 但是, 当写多读少的时候, 因为其写操作进行了一些额外的处理, 所以性能并没有比map+metux更好. 而且sync.Map在写时, 可能会触发read map的全量复制, 会降低效率.

可以看到sync.Map的整体思路是读写分离, 在读多写少的情况性能较好. 但是在写多读少的情况下, 性能并没有比普通加锁实现更好.

那么最初的map+metux的方式, 如何能够提高性能呢? 有了, 如果我们将1个map拆分为 n 个map, 这样每次操作的时候, 加锁的范围就变小了, 并发性能不就自然提高了么? 别说, 还真有人这么干了, 地址放这了, 有时间翻翻源码看看. https://github.com/orcaman/concurrent-map

原文地址 https://hujingnb.com/archives/849

转载请保留原文连接: Go sync.Map探究 | 烟草的香味