你应该学会的 bigcache 优化技巧( 二 ) _bigcache

哈希值应该比较随机 (质量)
哈希速度比较快 (速度)
尽量不产生额外的内存分配，避免对垃圾回收产生压力 (耗费资源少)

项目hash-bench[10]对常用的几种 Hash 算法进行了比较。
bigcache 提供了一个默认的 Hash 的实现，采用 fnv64a 算法。这个算法的好处是采用位运算的方式在栈上进行运算，避免在堆上分配。
type fnv64a struct{}const ( // offset64 FNVa offset basis. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash offset64 = 14695981039346656037 // prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash prime64 = 1099511628211)// Sum64 gets the string and returns its uint64 hash value.func (f fnv64a) Sum64(key string) uint64 { var hash uint64 = offset64 for i := 0; i < len(key); i++ {hash ^= uint64(key[i])hash *= prime64 } return hash}忽略内存开销对于 Go 语言中的 map, 垃圾回收器在 mark 和 scan 阶段检查 map 中的每一个元素, 如果缓存中包含数百万的缓存对象，垃圾回收器对这些对象的无意义的检查导致不必要的时间开销。
bigcache 的作者做了测试。他们测试了简单的 HTTP/JSON 序列化(不会访问 cache) 。在 cache 为空的时候 1 万的 QPS 的耗时大约 10 毫秒。当 cache 填满的时候， 99% 的请求都会超过 1 秒。监控显示堆中包含 4 千万的对象， GC 过程中的 mark 和 scan 也需要 4 秒。
我们可以很容易测试这种状况，比如下面的代码：
package mainimport "time"type Item struct { A string B string C string D string E string F string G G}type G struct { H int I int K int L int M int N int}func main() { m := make(map[int]*Item, 10*1024*1024) for i := 0; i < 1024*1024; i++ {m[i] = &Item{} } for i := 0; ; i++ {delete(m, i)m[1024*1024+i] = &Item{}time.Sleep(10 * time.Millisecond) }}只有一个 map 对象，里面包含一百万的元素，每 10 毫秒删一个放一个。
并发量相当小，并且单个的 goroutine 也没有竞争，但是由于元素的数量巨大，垃圾回收在mark/scan阶段需要花费上百毫秒进行标记和遍历。

文章插图

那么如何解决这个问题呢？
我们知道垃圾回收器检查的是堆上的资源，如果不把对象放在堆上，不就解决这个问题了吗？还真有这样的项目offheap[11] ，它提供了定制的Malloc() 和 Free() ，但是你的缓存需要基于这些方法定制。当然一些基于垃圾回收的编程语言为了减少垃圾回收的时间，都会提供相应的库，比如Java: ChronicleMap, Part 1: Go Off-Heap[12] 。堆外内存很容易产生内存泄漏。
第二种方式是使用 freecache[13] 。freecache 通过减少指针的数量以零 GC 开销实现 map 。它将键和值保存在ringbuffer中，并使用索引查找对象。
第三种优化方法是和 Go 1.5 中一个修复有关(#9477[14]), 这个 issue 还描述了包含大量对象的 map 的垃圾回收时的耗时问题， Go 的开发者优化了垃圾回收时对于 map 的处理，如果 map 对象中的 key 和 value 不包含指针，那么垃圾回收器就会对它们进行优化：

runtime: do not scan maps when k/v do not contain pointers
Currently we scan maps even if k/v does not contain pointers. This is required because overflow buckets are hanging off the main table. This change introduces a separate array that contains pointers to all overflow buckets and keeps them alive. Buckets themselves are marked as containing no pointers and are not scanned by GC (if k/v does not contain pointers).
This brings maps in line with slices and chans -- GC does not scan their contents if elements do not contain pointers.
Currently scanning of a map[int]int with 2e8 entries (~8GB heap) takes ~8 seconds. With this change scanning takes negligible time.
https://go-review.googlesource.com/c/go/+/3288

所以如果我们的对象不包含指针，虽然也是分配在堆上，但是垃圾回收可以无视它们。
如果我们把 map 定义成 map[int]int ，就会发现 gc 的耗时就会降下来了。