Go の sync.Map について調べる

[suzuki-shunsuke]

map と sync.RWMutex を使って map[string]string に関して sync.Map 的なものを実装してみた。

https://github.com/suzuki-shunsuke/go-thread-safe

sync.Map のドキュメントにも書いてあるが、 sync.Map だと型が interface{} なため、
個別に自分で実装したほうがいいんじゃないかなと思った。

ベンチーマークを取って sync.Map とパフォーマンスを比較した

• StringMap.GetOk vs sync.Map.Load
• StringMap.Set vs sync.Map.Store
• StringMap.RangeB vs sync.Map.Range

その結果、 Get/Set に関しては go-thread-safe のほうが良いが、Range に関しては sync.Map のほうが良かった

$ go test -bench="VersusSyncMap" -benchmem
goos: darwin
goarch: amd64
pkg: github.com/suzuki-shunsuke/go-thread-safe/safe
BenchmarkMapString_VersusSyncMap/MapString.Set-16                   9332            127778 ns/op          166913 B/op         33 allocs/op
BenchmarkMapString_VersusSyncMap/sync.Map.Store-16                  3772            313465 ns/op          194440 B/op       5043 allocs/op
BenchmarkMapString_VersusSyncMap/MapString.GetOk-16                28759             38566 ns/op               0 B/op          0 allocs/op
BenchmarkMapString_VersusSyncMap/sync.Map.Load-16                  22934             51165 ns/op               0 B/op          0 allocs/op
BenchmarkMapString_VersusSyncMap/MapString.RangeB-16               17863             66442 ns/op           81952 B/op          2 allocs/op
BenchmarkMapString_VersusSyncMap/sync.Map.Range-16                 84883             13320 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/suzuki-shunsuke/go-thread-safe/safe  9.967s

どうも allocation が発生しているらしい。
自分の実装では read lock を取って map[string]string をコピーしたあとに
コピーした map を使って loop を回しているが、

https://github.com/suzuki-shunsuke/go-thread-safe/blob/v0.7.0/safe/map_string.go#L159-L172

sync.Map ではパット見そんな実装にはなっていない。
そこでどういうふうに実現しているのか、ちょっと見てみたいと思う。

[suzuki-shunsuke]

sync.Map に関するリファレンス

https://golang.org/pkg/sync/#Map

なぜ sync.Map を実装したか Gophercon で発表された資料が公開されていた。

https://github.com/gophercon/2017-talks/blob/master/lightningtalks/BryanCMills-AnOverviewOfSyncMap/An%20Overview%20of%20sync.Map.pdf

また、 sync.Map のパフォーマンスに関する issue でも作者がコメントしている。

golang/go#28938

• sync: Map has poor performance golang/go#28938 (comment)

Also note that much of the overhead that sync.Map avoids comes from cache contention, which can make individual operations O(N) with the number of physical cores: with N cores executing those operations concurrently, you can get O(N²) behavior.

どうもマルチコアで並列に操作した場合の cache contention を解決するために sync.Map を実装したっぽい。

golang/go#28938 (comment)

ただ、 sync.Map に関しては performance issue があるっぽい。

• sync: reduce pointer overhead in Map golang/go#21031
• sync: reduce contention between Map operations with new-but-disjoint keys golang/go#21035

[suzuki-shunsuke]

https://golang.org/pkg/sync/#Map

• sync.Map は特定のユースケースに特化
• 大抵の場合、 map と lock を使うべき
  • 型による安全性
  • to make it easier to maintain other invariants along with the map content

2 つの common use case に最適化されている

1. 同じキーに一度しか書き込まれず、何度も読み取られる場合 (cache)
2. 複数の goroutine がそれぞれ別の key 群を読み書きする場合

この 2 つのユースケースの場合、 sync.Map を使うと sync.(RW)Mutex を使う場合に比べて
lock contention (ロックの競合) を大幅に減らせる

[suzuki-shunsuke]

読み取りと書き込みを atomic にやるような API は sync.Map は提供していないので、そういう用途では使えない。
例えば同じキーの int の value を increment するような操作を複数の goroutine でやればそれは thread safe ではない。

これは atomic.Value についても言えること。

そういう場合は、 読み取りから書き込みまで sync.(RW)Mutex でロックしたりする必要がある。

https://github.com/suzuki-shunsuke/go-thread-safe/blob/v0.7.0/safe/map_string.go#L135-L142

[suzuki-shunsuke]

sync.Map には size を取得する API がないっぽい https://golang.org/pkg/sync/#Map

issue もある golang/go#20680

[suzuki-shunsuke]

こんなものもある。
https://github.com/orcaman/concurrent-map

The stdlib sync.Map is designed for append-only scenarios.
So if you want to use the map for something more like in-memory db, you might benefit from using our version