大家好，我是烟花易冷。
今天给大家分享的是Go语言本地缓存的一些内容，主要是结合bigcache和fastcache两个优秀的开源代码库，总结一些设计思路和感悟。
1. Go语言本地缓存的实现
Go语言实现本地缓存是非常容易的，考虑到语言本身的特性，只要解决了“并发安全”问题，基本就可以在生产环境中使用了，常见的解决方案有两种：
- 使用 sync.Map
- 使用 map 配合 sync.RWMutex
Go语言内置的map是非并发数据安全的结构，对于缓存这种读多写少的业务，选择 sync.RWMutex 是比较合适的。sync.Map 则是采用了“空间换时间“的思路，在读多写少的缓存场景中，锁竞争的频率比 map + sync.RWMtex 更小。这两种方案实现本地缓存也都存在一些缺陷：
- 缓存对象很多时，锁竞争严重，性能急剧下降
- 大量缓存对象的写入导致gc扫描标记stw时间过长，cpu毛刺严重
- 内存占用不可控，缓存对象不支持按写入时间过期和淘汰
为了解决上述问题，大多数开发者会选择使用开源成熟的库；当然也可以自己开发一个库，前提是你要有解决这些问题的思路和过硬的编码能力。无论从哪个角度考虑，学习一下开源库的设计，读一下源码都是非常有收益的，下边就带着这几个问题结合bigcache、fastcache开源库的设计思路展开。
2. 锁竞争严重问题如何解决?
从实现上来讲，cache的实现本质上是一个并发安全的map，sync.RWMutex虽然对读写进行了优化，但对于写操作是串行执行的，缓存对象过多，写操作的频率也将变得不可控。一把大锁终究是问题的瓶颈所在，解决思路是将锁分片：将大的map拆分成小的map，每个小map配合一个sync.RWMutex做保护。bigcache 和 fastcache都采用了这种方式，bigcache中分片数量是可配置的。
fastcache更粗暴一点，直接硬编码写死了512个分片。
// source : https://github.com/VictoriaMetrics/fastcache/blob/master/fastcache.go
const bucketsCount = 512
type Cache struct {
buckets [bucketsCount]bucket
bigStats BigStats
}
2.1 分片数量N如何选择？
关于N的选择，几乎所有相关的开源库都选择了2的幂，毕竟位运算相对于取模运算可是要快很多的。对于2的幂N，等式 x mod N = (x & (N − 1)) 成立。
下边是bigcache作者的实现：
// source : https://github.com/allegro/bigcache/blob/main/bigcache.go#L249
func (c *BigCache) Get(key string) ([]byte, error) {
hashedKey := c.hash.Sum64(key)
shard := c.getShard(hashedKey)
return shard.get(key, hashedKey)
}
func (c *BigCache) Set(key string, entry []byte) error {
hashedKey := c.hash.Sum64(key)
shard := c.getShard(hashedKey)
return shard.set(key, hashedKey, entry)
}
func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
return c.shards[hashedKey&c.shardMask]
}
fastcache的作者似乎并没有意识到这一点(也许觉得这点cpu不值一提)，还是采用了取模的方法：
// source : https://github.com/VictoriaMetrics/fastcache/blob/master/fastcache.go
func (c *Cache) Set(k, v []byte) {
h := xxhash.Sum64(k)
idx := h % bucketsCount
c.buckets[idx].Set(k, v, h)
}
func (c *Cache) Get(dst, k []byte) []byte {
h := xxhash.Sum64(k)
idx := h % bucketsCount
dst, _ = c.buckets[idx].Get(dst, k, h, true)
return dst
}
2.2 hash函数如何选择?
map查找时间复杂度是O(1)，核心实现就在于hash函数。hash函数实现有很多，对于本地缓存应用场景来说，主要考虑的点有：
- 哈希值产生的速度，这是衡量hash函数好坏最关键的指标，越快越好。
- 哈希值的随机程度，产生的哈希值越随机越不容易产生hash冲突，查找性能就越好。
- 耗费资源情况(需要分配多少内存，对gc是否产生压力)。当然越小越好。
bigcache 默认采用了fnv64a算法。这个算法的好处是采用位运算的方式在栈上进行运算，避免在堆上分配。
// source : https://github.com/allegro/bigcache/blob/main/fnv.go
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
}
fastcache 则采用了XXH64哈希算法，优点在于高度可移植性，可以在不同平台上生成64位相同的哈希值。bigcache还为为Hash函数的实现定义了一个接口Hasher，开发者可以选择不同的hash函数实现：
type Hasher interface {
Sum64(string) uint64
}
3. 零GC的实现
Go语言自带垃圾回收机制，对于map，垃圾回收器会并发标记(mark)和扫描(scan)其中的每一个元素，如果缓存中包含数百万的缓存对象，垃圾回收器对这些对象的无意义的检查导致不必要的时间开销。
如果我们使用sync.Map或map + sync.RWMutex的实现方案，垃圾回收将不可避免。而bigcache和fastcache库都实现了零GC。它们都是采用了哪些手段呢？我们一起来看一下。
3.1 使用堆外内存
垃圾回收器检查的是堆上资源，如果不把对象放到堆上，就自然没有GC的压力了。fastcache 使用了这个思路，分配缓存数据内存时使用了golang.org/x/sys/unix库，它提供了定制的Mmap方法。但是堆外内存非常容易造成内存泄漏，慎用！
3.2 map非指针优化
Go的开发者在1.5版本中针对map的垃圾回收进行了优化runtime: do not scan maps when k/v do not contain pointers，对于不包含指针的map，虽然也是分配在堆上，但是垃圾回收可以无视它们。所以说只要将map定义成map[int]int，就能减少gc的压力。
但是业务中我们无法要求缓存对象只包含int、bool这样的基础数据类型，为了解决这个问题，bigcache和fastcache都采用了一种相同的巧妙的解决方法：使用哈希值作为map[uint64]uint32的key。 把缓存对象序列化后放到一个预先分配的大的字节数组中，然后将它在数组中的offset作为map[uint64]uint32的value。下面是bigcache实现原理架构图：
BytesQueue是一个字节数组，能够做到按需分配，所以bigcache是能够根据缓存大小，自动扩容的，当加入一个entry时，会将它转化为[]byte添加到末尾，也就是说更新元素的值，只是在末尾新增了元素的新值，更新了map[uint64]uint32中的index而已。删除操作也是将缓存key从map[uint64]uint32中剔除了而已。
fastcache官方文档介绍，它的灵感来自于bigcache。所以整体的思路和bigcache很类似，数据通过bucket进行分片。fastcache由512个bucket构成。每个bucket维护一把读写锁。在bucket内部数据同理是索引、数据两部分构成。索引用map[uint64]uint64存储。数据采用chunks二维的切片(二维数组)存储。我们前边提到了fastcache使用的是堆外内存，根据chunks大小进行内存分配与管理，下边是fastcache实现的原理架构图：
4. 内存占用和过期淘汰策略的抉择?
4.1 覆盖写 or 自动扩容?
对于内存占用和过期淘汰策略这两点特性支持上，bigcache和fastcache分别采用了不同的处理思路。
首先fastcache受初始化时内存的限制，初始化时指定的内存大小平均分配给512个bucket(例如总量为 2GB, 那么每个桶的数据就是 4MB)，当桶中的数据写满时，会根据ringbuffer的特性覆盖写，剔除比较旧的内容。
而bigcache则会根据缓存对象大小自动扩容，扩容是个很耗时的工作，可能会产生大量数据的copy。这是fastcache性能比bigcache好的一个原因。
4.2 数据过期需要支持吗？
fastcache比bigcache性能好的另外一个原因是：fastcache不支持缓存数据的自动过期，因此也就没必要像bigcache一样做额外的检查与数据清理工作了。对bigcache而言，要维护数据的过期策略首先在增加一个元素之前，会检查最老的元素要不要删除；其次，在添加一个元素失败后，会清理空间删除最老的元素。同时，还会专门有一个定时的清理goroutine, 负责移除过期数据。而这些都是以牺牲性能为代价的，那么这样做到底有没有意义呢？
或许有吧！不过fastcache官方文档上提出的另外一个观点是：其实数据的过期，可以由业务方将数据的过期时间戳写入到缓存数据中，自行判断数据是否过期。从其功能实现上而言，也确实是这样，毕竟删除数据支持操作了map[uint64]uint64的映射关系，数据并没有从ringbuffer中真正的清理掉。
5. 小结
本节我们围绕Go语言本地缓存的设计展开，提出了设计一个本地缓存需要考虑的几大因素。然后结合bigcache和fastcache两个优秀的开源库分析了它们的实现，还有一些思路上的折中。这些思路都是可以在业务开发中借鉴的。
也并不是说这些开源库的实现都那么的尽善尽美，如果业务中有特殊的需求，还可以基于开源库做二次开发，比如：是否有可能实现一个本地缓存库，既支持缓存对象单独设置缓存时间，又能实现高性能、占用内存少呢？又比如：是否能实现一个只占用固定内存，但可以占用大量磁盘空间，依然保持高性能的缓存库呢？我曾经思考过这些问题，但是奈何水平有限，没有什么突破性的进展。如果有感兴趣或者有思路的小伙伴，可以在评论区进行交流～
