前言
哈喽，大家好，我是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: darwingoarch: 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)
}
···
然后我们跑单元测试统计冲突数：
```go
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/how-bigcache-avoids-expensive-gc-cycles-and-speeds-up-concurrent-access-in-go-12bb；作者在BigCache的基础上自己写了一个简单版本的cache，然后通过代码来说明上面原理，更通俗易懂。
freecache中的做法是自己实现了一个ringbuffer结构，通过减少指针的数量以零GC开销实现map，key、value都保存在ringbuffer中，使用索引查找对象。freecache与传统的哈希表实现不一样，实现上有一个slot的概念，画了一个总结性的图，就不细看源码了：
总结
一个高效的本地缓存中，并发访问、减少GC这两个点是最重要的，在动手之前，看了这几个库中的优雅设计，直接推翻了我之前写好的代码，真是没有十全十美的设计，无论怎么设计都会在一些点上有牺牲，这是无法避免的，软件开发的道路上仍然道阻且长。自己实现的代码还在缝缝补补当中，后面完善了后发出来，全靠大家帮忙CR了。
好啦，本文到这里就结束了，我是asong，我们下期见。