本文介绍了支持高并发、低延迟应用的高性能 Go 内存缓存 BigCache，探讨其分片机制、哈希算法等性能优化机制。原文：BigCache: High-Performance Memory Caching in Go
BigCache 是基于 Go 实现的高性能内存缓存库，专为高并发、低延迟应用而设计。本文将探讨 BigCache 的性能优化技术，包括其分片机制、高效哈希算法、读写锁的使用等，并基于源码进行详细解释。
分片和锁
从用户角度来看，缓存的作用类似于大型哈希表，用于存储键值对（k/v）。那是否可以基于 map[string][]byte 和 sync.RWMutex 来实现呢？
当然可以，但这种实现仅适用于低性能需求的情况。尽管 sync.RWMutex 对读写进行了优化，但会对并发写入进行串行处理，即使对不同的键进行操作也是如此。这在高写入并发的情况下会造成瓶颈，阻塞多个协程，每次只允许一个写入者进行操作。
BigCache 通过采用受 Java 的 ConcurrentMap 启发的分片机制来解决这一问题。它将大型哈希表划分为多个较小的分片，每个分片都由其自身的锁进行保护。这种策略在 MongoDB 分片之类的高并发场景中被广泛使用，能够有效减少竞争。Go 还有一个第三方实现：concurrent-map。
源码示例：BigCache 分片
// https://github.com/allegro/bigcache/blob/a2f05d7cbfdc7000a8b7e1c40f27d3f239c204df/bigcache.go#L58type BigCache struct { shards []*cacheShard shardMask uint64 config Config}func newBigCache(ctx context.Context, config Config, clock clock) (*BigCache, error) { ...... cache := &BigCache{ shards: make([]*cacheShard, config.Shards), lifeWindow: lifeWindowSeconds, clock: clock, hash: config.Hasher, config: config, shardMask: uint64(config.Shards - 1), close: make(chan struct{}), } ...... for i := 0; i < config.Shards; i++ { cache.shards[i] = initNewShard(config, onRemove, clock) } ...... return cache, nil}
复制代码
每个缓存对象根据键计算哈希值：hash(key) % N。理想情况下，并发请求均匀分布在各个分片上，从而最大限度减少锁竞争并减少延迟。
最优分片数（N)
N 越大越好吗？不一定，过多分片会导致不必要的开销。通过选择合理的 N 来平衡性能和成本至关重要，通常选择 2 的幂为 N（例如 16、32、64），从而模运算可以通过快速位运算进行计算：
// https://github.com/allegro/bigcache/blob/a2f05d7cbfdc7000a8b7e1c40f27d3f239c204df/bigcache.go#L253func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) { return c.shards[hashedKey & c.shardMask]}
复制代码
因为 N 是 2 的幂，对于任意 x，等式 x mod N = （x & （N - 1）） 成立，因此只需进行一次与运算（&）就可以找到它的余数。
选择正确的哈希算法
计算机科学家发明了许多哈希算法，Go 也实现了其中许多算法。理想的哈希算法应当满足以下条件：
哈希值具有高度随机性。
计算速度快。
极小的内存需求，以减轻垃圾回收（GC）压力。
BigCache 的默认实现使用 fnv64a 算法，通过在栈上进行位运算来避免堆分配。
type fnv64a struct{}const ( offset64 = 14695981039346656037 prime64 = 1099511628211)func (f fnv64a) Sum64(key string) uint64 {var hash uint64 = offset64for i := 0; i < len(key); i++ { hash ^= uint64(key[i]) hash *= prime64 }return hash}
复制代码
内存优化
在 Go 中，垃圾回收器在标记和扫描阶段会检查 map 中的每个元素。如果缓存中包含了数百万个缓存对象，那么垃圾回收器对这些对象进行检查就会导致不必要的时间开销。这是因为如果哈希表中的元素包含指针，那么在标记阶段，垃圾回收器会扫描包含指针的每一个元素；如果不包含指针，则会在标记阶段跳过这些元素。我们可以通过一个简单例子来验证。
var pointMap map[int]*int var noPointMap map[int]int func BenchmarkPointMap(b *testing.B) { pointMap = make(map[int]*int) for i := 0; i < 10e6; i++ { pointMap[i] = &i } b.ResetTimer() for i := 0; i < b.N; i++ { delete(pointMap, i) pointMap[i] = &i } } func BenchmarkNoPointMap(b *testing.B) { noPointMap = make(map[int]int) for i := 0; i < 10e6; i++ { noPointMap[i] = i } b.ResetTimer() for i := 0; i < b.N; i++ { delete(noPointMap, i) noPointMap[i] = i } }
复制代码
结果：
➜ gc git:(main) ✗ GOMAXPROCS=1 go test --bench=. goos: darwingoarch: arm64pkg: blog-example/go/gccpu: Apple M1 ProBenchmarkPointMap 5273188 209.4 ns/opBenchmarkNoPointMap 7037848 178.5 ns/op
复制代码
然后，分别运行两个测试来分析 GC：
go test -bench=BenchmarkPointMap -trace trace_point.out go test -bench=BenchmarkNoPointMap -trace trace_no_point.out
复制代码
NoPointMap 的协程等待时间（Wall Duration）仅为 PointMap 的 2%。尽管 PointMap 的并发度较低，且不存在 goroutine 的竞争情况，但由于元素数量众多，在标记/扫描阶段的垃圾回收过程需要花费数百毫秒来进行标记和遍历。
BigCache 如何解决这个问题？禁止用户在 BigCache 中使用指针来存储数据。开个玩笑，如果真这么做了，用户立马会抛弃 BigCache。其实有几种方法可以解决这个问题。
参考 offheap，用自定义 Malloc() 和 Free() 函数来手动管理内存，同时绕过运行时垃圾回收机制，但这样做更有可能导致内存泄漏。
参考 freecache，通过减少指针数量来实现零垃圾回收开销的 map。它将键和值存储在环形缓冲区中，并使用索引来查找对象。BigCache 实现此功能的方式是将哈希值用作 map[int]int 的键，将缓存对象序列化为预分配的大字节数组，然后用数组偏移量作为 map[int]int 的值。
//https://github.com/allegro/bigcache/blob/a2f05d7cbfdc7000a8b7e1c40f27d3f239c204df/shard.go#L18type cacheShard struct { hashmap map[uint64]uint32 entries queue.BytesQueue lock sync.RWMutex entryBuffer []byte onRemove onRemoveCallback isVerbose bool statsEnabled bool logger Logger clock clock lifeWindow uint64 hashmapStats map[uint64]uint32 stats Stats}
func (s *cacheShard) set(key string, hashedKey uint64, entry []byte) error { currentTimestamp := uint64(s.clock.Epoch()) s.lock.Lock() if previousIndex := s.hashmap[hashedKey]; previousIndex != 0 { // Check for old entries with the same hash key if previousEntry, err := s.entries.Get(int(previousIndex)); err == nil { resetHashFromEntry(previousEntry) // reset hash of old entries delete(s.hashmap, hashedKey) // Remove old entries from the hash table } } if !s.cleanEnabled...= s.entries.Push(w); err == nil { // Try to push new entries into the queue s.hashmap[hashedKey] = uint64(index)// Update the hash table s.lock.Unlock() return nil } if s.removeOldestEntry(NoSpace) != nil { // If there is not enough space, delete the oldest entry s.lock.Unlock() return errors.New("entry is bigger than max shard size") } } }
func (s *cacheShard) getValidWrapEntry(key string, hashedKey uint64) ([]byte, error) { wrappedEntry, err := s.getWrappedEntry(hashedKey) if err != nil { return nil, err } if !compareKeyFromEntry(wrappedEntry, key) { s.collision() if s.isVerbose { s.logger.Printf("Collision detected. Both %q and %q have the same hash %x", key, readKeyFromEntry(wrappedEntry), hashedKey) } return nil, ErrEntryNotFound } s.hitWithoutLock(hashedKey) return wrappedEntry, nil }
复制代码
queue.BytesQueue 是按需使用的字节数组。当添加 []byte 数据时，会将数据复制到数组末尾。当 BigCache 删除缓存元素时，只是从 map[uint64]uint32 中移除该元素被添加的索引，并将 queue.BytesQueue 队列中的数据设置为 0。删除操作会创建许多“空洞”，而这些空洞不会被重组或删除。因为是基于字节数组实现的，所以删除“空洞”是一个耗时的操作，会导致锁时间过长。BigCache 只能等待清理机制来移除这些“空洞”。
其他一些细节：
在 BigCache 中缓存的对象无法刷新其过期时间，所有缓存最终都会过期。
所有缓存的生命周期由 config.LifeWindow 进行配置，无法针对单个键进行单独设置。
你好，我是俞凡，在 Motorola 做过研发，现在在 Mavenir 做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓厚的兴趣，平时喜欢阅读、思考，相信持续学习、终身成长，欢迎一起交流学习。为了方便大家以后能第一时间看到文章，请朋友们关注公众号"DeepNoMind"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的支持和动力，激励我持续写下去，和大家共同成长进步！
评论