go map设计实现及应用选型

Posted 2021-06-15 15:52 +0800 by ZhangJie ‐ 1 min read

map大致实现 ##

buckets & overflow ##

本文介绍了map的内部数据结构，每个桶8个kvpairs，超过了可以用溢出桶，但是溢出桶会降低map性能，所以会创建新的bucket将数据迁到新bucket里面。

hash & top hash table ##

一个kvpairs存储在哪个bucket里面呢，首先根据key计算hash，然后对buckets数量取余，再放到对应桶里面，如果有空位置就放入，没有就需要走前面提到的溢出桶的逻辑。

根据key计算出的hash除了计算key分布在哪个桶，还有其他用途，每个桶里都有一个top hash构成的数组，是为了map访问时加快查询key所在的数组索引的，通过减少比较key的耗时来加速访问。

mapaccess_faststr, mapaccess_fast64…访问map中元素时，根据key类型不同编译器插入不同的函数调用，函数名后缀表示key的类型，为什么有不同的函数呢？这是为了提高key的hash计算效率和比较效率。

load factor ##

装填因子，是用来控制map装填的元素数量，即元素数量除以桶数量。装填因子过小容易浪费内存空间，过大容易引发更多的碰撞冲突导致性能下降。

initialization && lazy initialization ##

map提前初始化再赋值，比lazy初始化后再赋值效率高，为什么呢？lazy初始化桶是后面创建的更花时间。但是lazy初始化相比较而言容易节省内存。

kvpairs padding ##

map中kvpairs的存储有考虑内存占用方面的优化，key的类型和value的类型可能不同，所以在数据对齐过程中padding会浪费不少内存，所以go map中的keys和values是分开存储的，先存储keys再存储values。

并发安全检测 ##

map中的并发读写问题，go提供了如下方式进行检查：

• data race detection：通过选项-race来检测是否存在data race，关于data race检测的问题，kavya joshi的分享里有介绍；

• concurrent map writes：map对应的数据结构hmap中有个字段flags来记录当前的map操作，比如当前执行m[1]=1，是一个kv的赋值，对应的函数是mapassign_fast64，如果执行的是delete(m, 1)，对应的函数是mapdelete_fast64，这里的map修改操作对应的函数内部会将hmap.flags^=hashWriting，如果已经有一个写操作在执行，后面又有一个写操作执行，后面的写操作就有很大概率检测到flags的hashWriting位被设置了，此时就会抛出错误“concurrent map writes”错误；

关于map为什么不直接提供并发安全的版本，原因也简单。并发安全的版本是有同步开销的，但是很多时候并不需要并发安全的版本，如果默认实现是并发安全的，性能上就要大打折扣了。不考虑并发安全问题的话，map比sync.Map要快7~10倍。

并发安全实现 ##

sync.Map是并发安全的实现，它对某些场景下的并发读写做了性能方面的优化：

“The Map type is optimized for two common use cases: (1) when the entry for a given key is only ever written once but read many times, as in caches that only grow, (2) when multiple goroutines read, write and overwrite entries for disjoint sets of keys. In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.”

意思就是说，sync.Map对于像缓存（caches）这种写一次（或次数很少）但是读取次数多的场景就很适用，或者存在多个goroutines并发读写，但是读写的keys集合是不相交的。

第三方实现：ShardedMap ##

sync.Map对于需要频繁执行删除的场景、更广泛的写场景，没有对其进行足够的优化，这两个场景可以参考shardedmap实现。

Benchmark及选型 ##

对map、sync.Map、concurrent_map（shardedmap）进行了benchmark，结果如下：

BenchmarkDeleteEmptyMap-8 20000000 86.9 ns/op
BenchmarkDeleteEmptySyncMap-8 300000000 5.16 ns/op
BenchmarkDeleteEmptyCMap-8 50000000 34.8 ns/op

BenchmarkDeleteMap-8 10000000 131 ns/op
BenchmarkDeleteSyncMap-8 10000000 135 ns/op
BenchmarkDeleteCMap-8 30000000 37.0 ns/op

BenchmarkLoadEmptyMap-8 20000000 87.9 ns/op
BenchmarkLoadEmptySyncMap-8 300000000 5.03 ns/op
BenchmarkLoadEmptyCMap-8 100000000 17.1 ns/op

BenchmarkLoadMap-8 20000000 111 ns/op
BenchmarkLoadSyncMap-8 100000000 12.8 ns/op
BenchmarkLoadCMap-8 100000000 22.5 ns/op

BenchmarkSetMap-8 10000000 187 ns/op
BenchmarkSetSyncMap-8 5000000 396 ns/op
BenchmarkSetCMap-8 20000000 84.9 ns/op

benchmark结果表明：

• map+rwmutex这种方式，锁粒度比加大，增删该查操作耗时相对来说都是比较明显的；
• sync.Map这种方式，写少读多的情况是非常合适的，效率比较明显，优于map、concurrent_map；
• concurrent_map，考虑了并发写比较频繁的情况，特别是删除，多shard执行删除操作时效率非常明显；

举个应用选型的例子：连接池明明显属于读多写少的场景，建议用sync.Map代替（key为ip:port，value为connection），后面transport如果要实现双工模式的时候，需要维护req.seqno\req的映射关系，增删频繁，可以考虑用concurrent_map（key为req.seqno，value为req）。

参考内容 ##

1. https://medium.com/a-journey-with-go/go-map-design-by-example-part-i-3f78a064a352?source=———45———————–
2. https://medium.com/a-journey-with-go/go-map-design-by-code-part-ii-50d111557c08
3. https://medium.com/a-journey-with-go/go-concurrency-access-with-maps-part-iii-8c0a0e4eb27e
4. https://github.com/orcaman/concurrent-map/blob/master/concurrent_map.go
5. https://golangexample.com/a-simple-and-efficient-thread-safe-sharded-hashmap-for-go/