Golang sync.Map

Nov 19, 2020 21:30 · 1540 words · 4 minute read Golang

介绍

众所周知 Golang 中的 map 是不能并发读写的，会直接 panic：

func main() {
    m := map[int]int{}

    go func() {
        for {
            m[0] = 1
        }
    }()

    go func() {
        for {
            fmt.Println("load from map:", m[0])
        }
    }()

    select {}
}

sync 标准库中给了一个并发安全 map 的实现 sync.Map，可以直接拿来使用：

func main() {
    m := &sync.Map{}

    go func() {
        for {
            m.Store(0, 1)
        }
    }()

    go func() {
        for {
            v, ok := m.Load(0)
            if ok {
                fmt.Println("load from map:", v.(int))
            }
        }
    }()

    select {}
}

我们深入探索一下 sync.Map 的实现原理。

源码

sync.Map 是一个结构体：https://github.com/golang/go/blob/go1.15.5/src/sync/map.go#L27-#L60

// The zero Map is empty and ready for use. A Map must not be copied after first use.
type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

既然要并发安全，互斥锁是必须的
只能原子操作的 read 不上锁，并发更新数据时先将记录存入此处
内部维护一个 dirty map，保持最新
统计 read 上一次更新后，需要上锁来确定 key 是否存在的次数

Map.read 字段存 readOnly 结构的数据。

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    m       map[interface{}]*entry
    amended bool // true if the dirty map contains some key not in m.
}

当 dirty map 和 m 不一致时为 true

读

// 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, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended {
        m.mu.Lock()
        // Avoid reporting a spurious miss if m.dirty got promoted while we were
        // blocked on m.mu. (If further loads of the same key will not miss, it's
        // not worth copying the dirty map for this key.)
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // Regardless of whether the entry was present, record a miss: this key
            // will take the slow path until the dirty map is promoted to the read
            // map.
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil
    m.misses = 0
}

优先从 read 读
如果没读到并且 dirty map 和 read.m 不一致时，上锁后再次确认从 read.m 读不到，就去 dirty map 那读
都上锁了，misses 计数肯定是要 +1 的
misses 超过了 dirty map 的体积，用 dirty map 覆盖掉 read.m，清掉 dirty map 和 misses 计数重新开始
卸锁

写

// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }

    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() {
            // The entry was previously expunged, which implies that there is a
            // non-nil dirty map and this entry is not in it.
            m.dirty[key] = e
        }
        e.storeLocked(&value)
    } else if e, ok := m.dirty[key]; ok {
        e.storeLocked(&value)
    } else {
        if !read.amended {
            // We're adding the first new key to the dirty map.
            // Make sure it is allocated and mark the read-only map as incomplete.
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value)
    }
    m.mu.Unlock()
}

// unexpungeLocked ensures that the entry is not marked as expunged.
//
// If the entry was previously expunged, it must be added to the dirty map
// before m.mu is unlocked.
func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// storeLocked unconditionally stores a value to the entry.
//
// The entry must be known not to be expunged.
func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

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
        }
    }
}

优先从 read 读，如果存在就直接在这搞了
如果没读到就要上锁了，再次于 read 确认，如果这回读到了，
要确认 read 真没有，再去 dirty map 确认一下，毕竟那边是最新的
两次确认下来真没有，如果 dirty map 和 read 是一样的，提前将 amended 设置为 true，因为这把下来一定不一致，然后才将记录写入 dirty map，毕竟那边要保持最新的
卸锁

结论

无论读写，sync.Map 都没有无脑上锁，都是先从 read 读（赌）一把再说，有一定的概率完全规避掉上锁，但如果更新频率极高，导致 read 和 dirty map 总是处于不一致的状态，那就要额外消耗不少时间来维护双 map 结构。所以 sync.Map 只适用于读多写少的场景。

基准测试

我们来写个全写场景（当然实际上是不可能的，光写不读就没有意义了）来验证上述结论：

map + RWMutex

func BenchmarkMap(b *testing.B) {
    mm := &struct {
        d map[int]int
        sync.RWMutex
    }{
        d: map[int]int{},
    }
    wg := &sync.WaitGroup{}

    for i := 0; i < 100; i++ {
        wg.Add(1)
        go func(wg *sync.WaitGroup, index int) {
            for j := 0; j < b.N; j++ {
                mm.Lock()
                mm.d[index] = j
                mm.Unlock()
            }
            wg.Done()
        }(wg, i)
    }

    wg.Wait()
}

➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkMap-16           149883              8071 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.648s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkMap-16           151221              8810 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.567s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkMap-16           148266              8090 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.415s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkMap-16           147584              8081 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.633s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkMap-16           129171              8138 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.278s

sync.Map

func BenchmarkSyncMap(b *testing.B) {
    m := &sync.Map{}
    wg := &sync.WaitGroup{}

    for i := 0; i < 100; i++ {
        wg.Add(1)
        go func(wg *sync.WaitGroup, index int) {
            for j := 0; j < b.N; j++ {
                m.Store(index, j)
            }
            wg.Done()
        }(wg, i)
    }

    wg.Wait()
}

➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkSyncMap-16        51980             24231 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.870s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkSyncMap-16        55140             29292 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   3.152s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkSyncMap-16        57424             26719 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.887s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkSyncMap-16        59796             20039 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   1.541s
➜ client2 go test -bench=. -run=none
goos: darwin
goarch: amd64
pkg: github.com/crazytaxii/go-test/client2
BenchmarkSyncMap-16        50023             21081 ns/op
PASS
ok      github.com/crazytaxii/go-test/client2   2.468s

从基准测试结果可以看出全写场景下 sync.Map 相比简单实现的带读写锁 map 有着两倍以上的性能差距。

介绍

源码

读

写

结论

基准测试

map + RWMutex

sync.Map

查看更多