shard map分片锁
0.前言
1.写并发量大的时候,goroutine会阻塞,只允许一个写,此时可以通过使用shard技术。分片,减小锁力度,在使用shard时,经常配合fnv算法 hash获取某一个shard。
2.gc会在标记阶段访问map中的每一个元素,当map非常大时会对性能产生巨大影响,此时可以使用key和value都不包含指针的map。
今天这一节看了一下concurrent-map的源码,并给大家介绍如何使用,内部的一些实现细节。此外,像bigcache这种高性能localcache,内部的实现也是与concurrent-map实现类似,fnv+shard map。
1.使用
concurrent-map如其名字,是一个并发map,在sync.Map出来之前,go标准库是不支持map并发的,即使出来之后,相比较于sync.Map来说,这里使用了shard Map使用起来,性能可能不低于sync.Map。
https://github.com/orcaman/concurrent-map
m := cmap.New()
// 设置变量m一个键为“foo”值为“bar”键值对
m.Set("foo", "bar")
// 从m中获取指定键值.
if tmp, ok := m.Get("foo"); ok {
bar := tmp.(string)
}
// 删除键为“foo”的项
m.Remove("foo")
fnv
fnv是一个非密码学hash算法,其维基百科地址见下方。
https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
在golang中其实现在hash/fnv/fnv.go中。
也可以在下方地址直接看到对应的源码,在map中作为hash算法来说使用非常有用,可以快速找到hash的桶/分片等。
go源码中进行了封装,看起来可能比较晦涩,以fnv32为例子:
其中2166136261为offset_basis,16777619为FNV_prime。
开源项目中便使用到了fnv32算法来做hash。
https://github.com/orcaman/concurrent-map/blob/master/concurrent_map.go#L316
hash := uint32(2166136261)
const prime32 = uint32(16777619)
keyLength := len(key)
for i := 0; i < keyLength; i++ {
hash *= prime32
hash ^= uint32(octet_of_data)
}
return hash
}
本节完~