手撕 Golang 高性能内存缓存库 bigcache!( 二 ) _Golang

例如使用 1024 作为 shard num 时，mask 值为 1024 - 1 即二进制的 '111111111'，使用 num & mask 时，即可获得 num % mask 的效果
需要注意，这里的 hash 可能是会冲突的，虽然概率极小，当出现 hash 冲突时，bigcache 将直接返回结果不存在：
func (s *cacheShard) get(key string, hashedKey uint64) ([]byte, error) {s.lock.RLock()wrAppedEntry, err := s.getWrappedEntry(hashedKey)if err != nil {s.lock.RUnlock()return nil, err}// 这里会将二进制 buffer 按顺序解开// 在打包时将 key 打包的作用就体现出来了// 如果这次操作的 key 和打包时的 key 不相同// 则说明发生了冲突，不会错误地返回另一个 key 的缓存结果if entryKey := readKeyFromEntry(wrappedEntry); key != entryKey {s.lock.RUnlock()s.collision()if s.isVerbose {s.logger.Printf("Collision detected. Both %q and %q have the same hash %x", key, entryKey, hashedKey)}return nil, ErrEntryNotFound}entry := readEntry(wrappedEntry)s.lock.RUnlock()s.hit(hashedKey)return entry, nil}4.2 cacheShard 与 bytes queue 设计bigcache 对每个 shard 使用了一个类似 ringbuffer 的 BytesQueue 结构，定义如下：
type cacheShard struct {// hashed key => bytes queue indexhashmapmap[uint64]uint32entriesqueue.BytesQueuelocksync.RWMutexentryBuffer []byteonRemoveonRemoveCallbackisVerboseboolstatsEnabled boolloggerLoggerclockclocklifeWindowuint64hashmapStats map[uint64]uint32statsStats}下图很好地解释了 cacheShard 的底层结构~

文章插图
图片来自 https://medium.com/codex/our-go-cache-library-choices-406f2662d6b
在处理完 sharding 后，bigcache 会将整个 value 与 key、hashedKey 等信息序列化后存进一个 byte array，这里的设计是不是有点类似网络协议里的 header 呢？

// 将整个 entry 打包到当前 shard 的// byte array 中w := wrapEntry(currentTimestamp, hashedKey, key, entry, &s.entryBuffer)func wrapEntry(timestamp uint64, hash uint64, key string, entry []byte, buffer *[]byte) []byte {keyLength := len(key)blobLength := len(entry) + headersSizeInBytes + keyLengthif blobLength > len(*buffer) {*buffer = make([]byte, blobLength)}blob := *buffer// 小端字节序binary.LittleEndian.PutUint64(blob, timestamp)binary.LittleEndian.PutUint64(blob[timestampSizeInBytes:], hash)binary.LittleEndian.PutUint16(blob[timestampSizeInBytes+hashSizeInBytes:], uint16(keyLength))copy(blob[headersSizeInBytes:], key)copy(blob[headersSizeInBytes+keyLength:], entry)return blob[:blobLength]}

这里存原始的 string key ，我理解单纯是为了处理 hash 冲突用的。
每一个 cacheShard 底层的缓存数据都会存储在 bytes queue 中，即一个 FIFO 的 bytes 队列，新进入的 entry 都会 push 到末尾，如果空间不足，则会产生内存分配的过程，初始的 queue 的大小，是可以在配置中指定的：

func initNewShard(config Config, callback onRemoveCallback, clock clock) *cacheShard {// 1. 初始化指定好大小可以减少内存分配的次数bytesQueueInitialCapacity := config.initialShardSize() * config.MaxEntrySizemaximumShardSizeInBytes := config.maximumShardSizeInBytes()if maximumShardSizeInBytes > 0 && bytesQueueInitialCapacity > maximumShardSizeInBytes {bytesQueueInitialCapacity = maximumShardSizeInBytes}return &cacheShard{hashmap:make(map[uint64]uint32, config.initialShardSize()),hashmapStats: make(map[uint64]uint32, config.initialShardSize()),// 2. 初始化 bytes queue，这里用到了上面读取的配置entries:*queue.NewBytesQueue(bytesQueueInitialCapacity, maximumShardSizeInBytes, config.Verbose),entryBuffer:make([]byte, config.MaxEntrySize+headersSizeInBytes),onRemove:callback,isVerbose:config.Verbose,logger:newLogger(config.Logger),clock:clock,lifeWindow:uint64(config.LifeWindow.Seconds()),statsEnabled: config.StatsEnabled,}}

注意到这点，在初始化时使用正确的配置，就能减少重新分配内存的次数了。
4.3 GC 优化bigcache 本质上就是一个大的哈希表，在 go 里，由于 GC STW(Stop the World) 的存在大的哈希表是非常要命的，看看 bigcache 开发团队的博客的测试数据：
With an empty cache, this endpoint had maximum responsiveness latency of 10ms for 10k rps. When the cache was filled, it had more than a second latency for 99th percentile. Metrics indicated that there were over 40 mln objects in the heap and GC mark and scan phase took over four seconds.
缓存塞满后，堆上有 4 千万个对象，GC 的扫描过程就超过了 4 秒钟，这就不能忍了。
主要的优化思路有：