1. 前言

你好哇！我是小翔。之前寫了三篇 #Golang 并發編程 的文章了，這次來換換口味，開個 手撕源碼 的新坑！一起來扒一扒 Go 語言高性能 local cache 庫 bigcache，看看能不能把開源大佬們的騷操作帶到項目里去裝一裝（？）

2. 為什么要學習開源項目

個人認為學習開源項目的收益：

• 跟進社區，不做井底之蛙 看到一個開源項目，可以思考下：大佬們最近都在解決哪些問題？他們用到了哪些開源工具？我能拿到項目里用嗎？這玩意有 bug 嗎？要不要提個 issue 或者提個 PR 呢？
• 面向原理編程 我們在實際項目中會用上很多開源庫/框架，你是否好奇過它們的實現機制呢？理解用到的庫的實現機制，能幫我們避開很多坑，堪稱降維打擊
• 學習優秀的設計 優秀的開源項目經過了成千上萬開發者的 review，質量一般會比公司趕進度趕出來的質量高得多得多，從中學習優秀的設計，再在實際項目中多用用，同事會感嘆：

3. bigcache 簡介

3.1 本地緩存與分布式緩存

緩存是系統提升并發能力、降低時延的利器，根據存儲介質和使用場景，我們一般又會使用本地緩存與分布式緩存兩種手段。本地緩存一般是在進程內的，最簡單的，用 go 的 sync.Map 就能實現一個簡單的并發安全的本地緩存了。常見的，將一些靜態的、配置類的數據放置在本地緩存中，能有效降低到下游存儲的壓力。分布式緩存一般會用 redis 或 memcached 等分布式內存數據庫來實現，能做到分布式、無狀態。這次先研究下 bigcache 后續有機會再挖一挖這里。

3.2 bigcache 誕生背景

bigcache 的開發者是 allegro，是波蘭的一個電商網站，參考資料中給出了他們的技術博客的原文，文中詳細描述了他們問題的背景以及思考，值得研究。他們的需求主要是：

• 用 HTTP 協議處理 GET POST 請求，body 不大
• 10k rps(requests per second) 5k 讀 5k 寫
• 緩存至少 10 分鐘
• 低延時：平均 5ms ，P99 < 10ms，P999 < 400ms總結一下，他們需要一個快速、支持過期淘汰、支持 RESTful api 的字典服務

開發團隊經過了一番對比，選擇了 go 語言（高并發度、帶內存管理安全性比 C/C++ 好），拋棄了分布式緩存組件（redis/memcached/couchbase），主要理由是多一跳網絡開銷。這里我表示懷疑，P999 400ms 的時延其實不至于擔心到 redis 網絡那點時間，分布式環境下 local cache 不同機器間的數據不一致帶來的 cache miss 可能更蛋疼。 最終開發團隊選擇了實現一個支持以下特性的內存緩存庫：

• 百萬級緩存項時響應速度也很快
• 并發安全
• 支持設置過期時間

4. 關鍵設計

4.1 并發與 sharding

設計上如何做到并發安全呢？最簡單的思路就是給 map 上一把 sync.RWMutex 即讀寫鎖。然而當緩存項過多時，并發請求會造成鎖沖突，因此需要降低鎖粒度。bigcache 采用了分布式系統里常用的 sharding 思路，即將一個大 map 拆分成 N 個小 map，我們稱為一個 shard(分片)

如 bigcache.go 的聲明，我們初始化得到的 BigCache，核心實際上是一個 []*cacheShard，緩存的寫入、淘汰等核心邏輯都在 cacheShard 中了

type BigCache struct {
    shards     []*cacheShard
    lifeWindow uint64
    clock      clock
    hash       Hasher
    config     Config
    shardMask  uint64
    close      chan struct{}
}

那么在寫入一個 key value 緩存時，是如何做分片的呢？

func (c *BigCache) Set(key string, entry []byte) error {
    hashedKey := c.hash.Sum64(key)
    shard := c.getShard(hashedKey)
    return shard.set(key, hashedKey, entry)
}

這里會首先進行一次 hash 操作，將 string key hash 到一個 uint64 類型的 key。再根據這個數字 key 去做 sharding

func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
    return c.shards[hashedKey&c.shardMask]
}

這里把取余的操作用位運算來實現了，這也解釋了為什么在使用 bigcache 的時候需要使用 2 的冪來初始化 shard num 了

cache := &BigCache{
    shards:     make([]*cacheShard, config.Shards),
    lifeWindow: uint64(config.LifeWindow.Seconds()),
    clock:      clock,
    hash:       config.Hasher,
    config:     config,
    // config.Shards 必須是 2 的冪
    // 減一后得到一個二進制結果全為 1 的 mask
    shardMask:  uint64(config.Shards - 1),  
    close:      make(chan struct{}),
}

例如使用 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 index
    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
}

下圖很好地解釋了 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 + keyLength

    if 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.MaxEntrySize
    maximumShardSizeInBytes := 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 秒鐘，這就不能忍了。

主要的優化思路有：

1. offheap（堆外內存），GC 只會掃描堆上的對象，那就把對象都搞到棧上去，但是這樣這個緩存庫就高度依賴 offheap 的 malloc 和 free 操作了
2. 參考 freecache 的思路，用 ringbuffer 存 entry，繞過了 map 里存指針，簡單瞄了一下代碼，后面有空再研究一下（繼續挖坑
3. 利用 Go 1.5+ 的特性：

當 map 中的 key 和 value 都是基礎類型時，GC 就不會掃到 map 里的 key 和 value

最終他們采用了 map[uint64]uint32 作為 cacheShard 中的關鍵存儲。key 是 sharding 時得到的 uint64 hashed key，value 則只存 offset ，整體使用 FIFO 的 bytes queue，也符合按照時序淘汰的需求，非常精巧。

經過優化，bigcache 在 2000w 條記錄下 GC 的表現

go version go version go1.13 linux/arm64

go run caches_gc_overhead_comparison.go Number of entries:  20000000GC pause for bigcache:  22.382827msGC pause for freecache:  41.264651msGC pause for map:  72.236853ms

效果挺明顯，但是對于低延時的服務來說，22ms 的 GC 時間還是很致命的，對象數還是盡量能控制住比較好。

5. 小結

認真學完 bigcache 的代碼，我們至少有以下幾點收獲：

• 可以通過 sharding 來降低資源競爭
• 可以用位運算來取余數做 sharding （需要是 2 的整數冪 - 1）
• 避免 map 中出現指針、使用 go 基礎類型可以顯著降低 GC 壓力、提升性能
• bigcache 底層存儲是 bytes queue，初始化時設置合理的配置項可以減少 queue 擴容的次數，提升性能

參考資料

• https://github.com/allegro/bigcache
• 《allegro.tech blog - Writing a very fast cache service with millions of entries in Go》https://blog.allegro.tech/2016/03/writing-fast-cache-service-in-go.html
• 《鳥窩 - 妙到顛毫: bigcache優化技巧》https://colobu.com/2019/11/18/how-is-the-bigcache-is-fast/
• 《Stefanie Lai - Our Go Cache Library Choices》https://medium.com/codex/our-go-cache-library-choices-406f2662d6b
• 《熊喵君的博客 - Golang 高性能 LocalCache：BigCache 設計與分析》https://pandaychen.github.io/2020/03/03/BIGCACHE-ANALYSIS/
• https://github.com/coocood/freecache
• https://github.com/glycerine/offheap 堆外內存

本文轉載自微信公眾號「 翔叔架構筆記」，可以通過以下二維碼關注。轉載本文請聯系翔叔架構筆記公眾號。