关于golang:动手实现一个localcache-欣赏优秀的开源设计

前言

哈喽，大家好，我是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梦工厂】