手撕 Golang 高性能內存緩存庫 bigcache

1. 前言

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

2. 爲什麼要學習開源項目

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

3. bigcache 簡介

3.1 本地緩存與分佈式緩存

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

3.2 bigcache 誕生背景

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

開發團隊經過了一番對比，選擇了 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:  20000000
GC pause for bigcache:  22.382827ms
GC pause for freecache:  41.264651ms
GC pause for map:  72.236853ms

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

5. 小結

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

翔叔架構筆記 專注 Golang 後端開發與架構，分享優質內容與獨立音樂。關於翔叔：鵝廠長大的 T10，5 年互聯網後端服務與架構設計研發經驗，擅長社交領域、數據中臺等系統的設計與實現、獨立音樂愛好者。希望與你共同成長 :)

參考資料

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UH1b46mhDBvE5M3sgglQcw

猜你喜歡