共计 3960 个字符,预计需要花费 10 分钟才能阅读完成。
前言
哈喽,大家好,我是
asong
。上篇文章:入手实现一个 localcache – 设计篇 介绍了设计一个本地缓存要思考的点,有读者敌人反馈能够借鉴 bigcache 的存储设计,能够缩小 GC 压力,这个是我之前没有思考到的,这种开源的优良设计值得咱们学习,所以在入手之前我浏览了几个优质的本地缓存库,总结了一下各个开源库的优良设计,本文咱们就一起来看一下。
高效的并发拜访
本地缓存的简略实现能够应用 map[string]interface{}
+ sync.RWMutex
的组合,应用 sync.RWMutex
对读进行了优化,然而当并发量上来当前,还是变成了串行读,期待锁的 goroutine
就会 block
住。为了解决这个问题咱们能够进行分桶,每个桶应用一把锁,缩小竞争。分桶也能够了解为分片,每一个缓存对象都依据他的 key
做hash(key)
,而后在进行分片:hash(key)%N
,N 就是要分片的数量;现实状况下,每个申请都均匀落在各自分片上,根本无锁竞争。
分片的实现次要思考两个点:
-
hash
算法的抉择,哈希算法的抉择要具备如下几个特点:- 哈希后果离散率高,也就是随机性高
- 防止产生多余的内存调配,防止垃圾回收造成的压力
- 哈希算法运算效率高
- 分片的数量抉择,分片并不是越多越好,依据教训,咱们的分片数能够抉择
N
的2
次幂,分片时为了提高效率还能够应用位运算代替取余。
开源的本地缓存库中 bigcache
、go-cache
、freecache
都实现了分片性能,bigcache
的 hash
抉择的是 fnv64a
算法、go-cache
的 hash
抉择的是 djb2 算法、freechache
抉择的是 xxhash
算法。这三种算法都是非加密哈希算法,具体选哪个算法更好呢,须要综合思考下面那三点,先比照一下运行效率,雷同的字符串状况下,比照benchmark
:
func BenchmarkFnv64a(b *testing.B) {b.ResetTimer()
for i:=0; i < b.N; i++{fnv64aSum64("test")
}
b.StopTimer()}
func BenchmarkXxxHash(b *testing.B) {b.ResetTimer()
for i:=0; i < b.N; i++{hashFunc([]byte("test"))
}
b.StopTimer()}
func BenchmarkDjb2(b *testing.B) {b.ResetTimer()
max := big.NewInt(0).SetUint64(uint64(math.MaxUint32))
rnd, err := rand.Int(rand.Reader, max)
var seed uint32
if err != nil {b.Logf("occur err %s", err.Error())
seed = insecurerand.Uint32()}else {seed = uint32(rnd.Uint64())
}
for i:=0; i < b.N; i++{djb33(seed,"test")
}
b.StopTimer()}
运行后果:
goos: darwin
goarch: amd64
pkg: github.com/go-localcache
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkFnv64a-16 360577890 3.387 ns/op 0 B/op 0 allocs/op
BenchmarkXxxHash-16 331682492 3.613 ns/op 0 B/op 0 allocs/op
BenchmarkDjb2-16 334889512 3.530 ns/op 0 B/op 0 allocs/op
通过比照后果咱们能够观察出来 Fnv64a
算法的运行效率还是很高,接下来咱们在比照一下随机性,先随机生成 100000
个字符串,都不雷同;
func init() {insecurerand.Seed(time.Now().UnixNano())
for i := 0; i < 100000; i++{randString[i] = RandStringRunes(insecurerand.Intn(10))
}
}
var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
func RandStringRunes(n int) string {b := make([]rune, n)
for i := range b {b[i] = letterRunes[insecurerand.Intn(len(letterRunes))]
}
return string(b)
}
而后咱们跑单元测试统计抵触数:
func TestFnv64a(t *testing.T) {m := make(map[uint64]struct{})
conflictCount :=0
for i := 0; i < len(randString); i++ {res := fnv64aSum64(randString[i])
if _,ok := m[res]; ok{conflictCount++}else {m[res] = struct{}{}
}
}
fmt.Printf("Fnv64a conflict count is %d", conflictCount)
}
func TestXxxHash(t *testing.T) {m := make(map[uint64]struct{})
conflictCount :=0
for i:=0; i < len(randString); i++{res := hashFunc([]byte(randString[i]))
if _,ok := m[res]; ok{conflictCount++}else {m[res] = struct{}{}
}
}
fmt.Printf("Xxxhash conflict count is %d", conflictCount)
}
func TestDjb2(t *testing.T) {max := big.NewInt(0).SetUint64(uint64(math.MaxUint32))
rnd, err := rand.Int(rand.Reader, max)
conflictCount := 0
m := make(map[uint32]struct{})
var seed uint32
if err != nil {t.Logf("occur err %s", err.Error())
seed = insecurerand.Uint32()}else {seed = uint32(rnd.Uint64())
}
for i:=0; i < len(randString); i++{res := djb33(seed,randString[i])
if _,ok := m[res]; ok{conflictCount++}else {m[res] = struct{}{}
}
}
fmt.Printf("Djb2 conflict count is %d", conflictCount)
}
运行后果:
Fnv64a conflict count is 27651--- PASS: TestFnv64a (0.01s)
Xxxhash conflict count is 27692--- PASS: TestXxxHash (0.01s)
Djb2 conflict count is 39621--- PASS: TestDjb2 (0.01s)
综合比照下,应用 fnv64a
算法会更好一些。
缩小 GC
Go
语言是带垃圾回收器的,GC
的过程也是很耗时的,所以要真的要做到高性能,如何防止 GC
也是一个重要的思考点。freecacne
、bigcache
都号称防止高额 GC
的库,bigcache
做到防止高额 GC
的设计是基于 Go
语言垃圾回收时对 map
的非凡解决;在 Go1.5
当前,如果 map 对象中的 key 和 value 不蕴含指针,那么垃圾回收器就会忽视他,针对这个点们的 key
、value
都不应用指针,就能够防止 gc
。bigcache
应用哈希值作为 key
,而后把缓存数据序列化后放到一个事后调配好的字节数组中,应用offset
作为 value
,应用事后调配好的切片只会给 GC 减少了一个额定对象,因为字节切片除了本身对象并不蕴含其余指针数据,所以 GC 对于整个对象的标记工夫是 O(1) 的。具体原理还是须要看源码来加深了解,举荐看原作者的文章:https://dev.to/douglasmakey/h…;作者在 BigCache 的根底上本人写了一个简略版本的 cache,而后通过代码来阐明下面原理,更通俗易懂。
freecache
中的做法是本人实现了一个 ringbuffer
构造,通过缩小指针的数量以零 GC 开销实现 map,key
、value
都保留在 ringbuffer
中,应用索引查找对象。freecache
与传统的哈希表实现不一样,实现上有一个 slot
的概念,画了一个总结性的图,就不细看源码了:
举荐文章
- https://colobu.com/2019/11/18…
- https://dev.to/douglasmakey/h…
- https://studygolang.com/artic…
- https://blog.csdn.net/chizhen…
总结
一个高效的本地缓存中,并发拜访、缩小 GC
这两个点是最重要的,在入手之前,看了这几个库中的优雅设计,间接颠覆了我之前写好的代码,真是没有美中不足的设计,无论怎么设计都会在一些点上有就义,这是无奈防止的,软件开发的路线上依然道阻且长。本人实现的代码还在缝缝补补当中,前面欠缺了后发进去,全靠大家帮忙 CR
了。
好啦,本文到这里就完结了,我是asong
,咱们下期见。
** 欢送关注公众号:【Golang 梦工厂】