你应该学会的 bigcache 优化技巧

本文作者:鸟窝 smallnest
原文链接:https://colobu.com/2019/11/18/how-is-the-bigcache-is-fast/
最近看到 yoko 翻译的一篇文章: [译] Go 开源项目 BigCache 如何加速并发访问以及避免高额的 GC 开销[1] , 翻译自 How BigCache avoids expensive GC cycles and speeds up concurrent access in Go[2], 应该是 Douglas Makey Mendez Molero 在阅读了 bigcache 的作者写的 bigcache 设计文章Writing a very fast cache service with millions of entries in Go[3]做的一些调研和总结 。
我在刚读取这篇文档的时候 , 顺着连接把相关的文章都找出来细细读了一遍 , 结合 bigcache 的代码 , 仔细学习了相关的优化设计 , 感觉设计非常的精妙 , 所以特意根据自己的理解又总结了一篇 。
bigcache 的精妙的设计也吸引了 fasthttp 的作者 Aliaksandr Valialkin , 他在 bigcache 的基础上 , 结合自己的公司的使用场景 , 进一步的做了相应的优化 , 也开源了这个项目 fastcache[4], 本文在最后也做了介绍 。
设计 BigCache 的初衷bigcache 的作者也不是想当然的开发一个库 , 而且项目遇到了需求 。需求如下:

  • 支持 http 协议
  • 支持 10K RPS (5k 写 , 5k 读)
  • cache 对象至少保持 10 分钟
  • 相应时间平均 5ms, p99.9 10 毫秒 ,  p99.999 400 毫秒
  • 其它 HTTP 的一些需求
为了满足这些需求 , 要求开发的 cache 库要保证:
  • 即使有百万的缓存对象也要非常快
  • 支持大并发访问
  • 一定时间后支持剔除
作者考察了一番缓存框架比如 memcached、redis、couchbase 等 , 发觉都不太满足需求 , 因为这些都是独立的程序 , 访问它们需要网络的开销 , 延时无法保障 , 作者需要一个进程内的基于内存的 cache 库 。虽然 Go 生态圈有众多的 cache 库如 LRU groups cache[5], go-cache[6], ttlcache[7], freecache[8] , 但是只有 freecache 满足需求 , 不过作者最后还是决定自己取开发一个 cache 库 。
以上是 bigcache 诞生的背景 , 接下来我们欣赏一下 bigcache 和其它库优美的设计 。
处理大并发访问cache 就像一个大的 hashtable, 可不可以使用一个map[string][]byte + sync.RWMutex实现满足需求的 cache 呢?
sync.RWMutex虽然对读写进行了优化 , 但是对于并发的读 , 最终还是把写变成了串行 , 一旦写的并发量大的时候 , 即使写不同的 key, 对应的 goroutine 也会 block 住 , 只允许一个写执行 , 这是一个瓶颈 , 并且不可控 。
解决并发的问题有一个方法叫做 shard (分片) , 每个分片一把锁 。很多大并发场景下为了减小并发的压力都会采用这种方法 , 大的场景比如数据库的分片 , 小的场景就如刚才的场景 。JAVA 8 之前的 ConcurrentMap 就是采用分片(segment)的方式减少竞争, Go 也有一个类似思想设计的 map 库:concurrent-map[9] 。
对于每一个缓存对象 , 根据它的 key 计算它的哈希值: hash(key) % N, N是分片数量 。理想情况下 N 个 goroutine 每次请求正好平均落在各自的分片上 , 这样就不会有竞争了 , 即使有多个 goroutine 落在同一个分片上 , 如果 hash 比较平均的话 , 单个 shard 的压力也会比较小 。
竞争小了有什么好处?延迟可以大大提高 , 因为等待获取锁的时间变小了 。
当然这里有一些要考虑的地方:
1、N 的选择
既然分片可以很好的降低锁的竞争 , 那么 N 是不是越大越好呢?当然不是 , 如果 N 非常大 , 比如每个缓存对象一个锁 , 那么会带来很多额外的不必要的开销 。可以选择一个不太大的值 , 在性能和花销上寻找一个平衡 。
另外, N 是 2 的幂 ,  比如 16、32、64 。这样设计的好处就是计算余数可以使用位运算快速计算 。
func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) { return c.shards[hashedKey&c.shardMask]}因为对于 2 的幂 N , 对于任意的x, 下面的公式成立:
x mod N = (x & (N − 1))所以只需要使用一次按位 AND (&)就可以求得它的余数 。
2、选择 hash 算法
以前已经有非常多的哈希算法 , 最近几年也出现了一些新的哈希算法 , 也被人使用 Go 语言来实现 。
很显然 , 一个优秀的哈希算法要保证:


推荐阅读