手撕 Golang 高性能內(nèi)存緩存庫(kù) bigcache! #4

1. 前言

你好哇！我是小翔。之前寫了三篇 #Golang 并發(fā)編程 的文章了，這次來(lái)?yè)Q換口味，開個(gè) 手撕源碼 的新坑！一起來(lái)扒一扒 Go 語(yǔ)言高性能 local cache 庫(kù) bigcache，看看能不能把開源大佬們的騷操作帶到項(xiàng)目里去裝一裝（？）

2. 為什么要學(xué)習(xí)開源項(xiàng)目

個(gè)人認(rèn)為學(xué)習(xí)開源項(xiàng)目的收益：

• 跟進(jìn)社區(qū)，不做井底之蛙 看到一個(gè)開源項(xiàng)目，可以思考下：大佬們最近都在解決哪些問(wèn)題？他們用到了哪些開源工具？我能拿到項(xiàng)目里用嗎？這玩意有 bug 嗎？要不要提個(gè) issue 或者提個(gè) PR 呢？
• 面向原理編程 我們?cè)趯?shí)際項(xiàng)目中會(huì)用上很多開源庫(kù)/框架，你是否好奇過(guò)它們的實(shí)現(xiàn)機(jī)制呢？理解用到的庫(kù)的實(shí)現(xiàn)機(jī)制，能幫我們避開很多坑，堪稱降維打擊
• 學(xué)習(xí)優(yōu)秀的設(shè)計(jì) 優(yōu)秀的開源項(xiàng)目經(jīng)過(guò)了成千上萬(wàn)開發(fā)者的 review，質(zhì)量一般會(huì)比公司趕進(jìn)度趕出來(lái)的質(zhì)量高得多得多，從中學(xué)習(xí)優(yōu)秀的設(shè)計(jì)，再在實(shí)際項(xiàng)目中多用用，同事會(huì)感嘆：

3. bigcache 簡(jiǎn)介

3.1 本地緩存與分布式緩存

緩存是系統(tǒng)提升并發(fā)能力、降低時(shí)延的利器，根據(jù)存儲(chǔ)介質(zhì)和使用場(chǎng)景，我們一般又會(huì)使用本地緩存與分布式緩存兩種手段。本地緩存一般是在進(jìn)程內(nèi)的，最簡(jiǎn)單的，用 go 的 sync.Map 就能實(shí)現(xiàn)一個(gè)簡(jiǎn)單的并發(fā)安全的本地緩存了。常見的，將一些靜態(tài)的、配置類的數(shù)據(jù)放置在本地緩存中，能有效降低到下游存儲(chǔ)的壓力。分布式緩存一般會(huì)用 redis 或 memcached 等分布式內(nèi)存數(shù)據(jù)庫(kù)來(lái)實(shí)現(xiàn)，能做到分布式、無(wú)狀態(tài)。這次先研究下 bigcache 后續(xù)有機(jī)會(huì)再挖一挖這里。

3.2 bigcache 誕生背景

bigcache 的開發(fā)者是 allegro，是波蘭的一個(gè)電商網(wǎng)站，參考資料中給出了他們的技術(shù)博客的原文，文中詳細(xì)描述了他們問(wèn)題的背景以及思考，值得研究。他們的需求主要是：

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

開發(fā)團(tuán)隊(duì)經(jīng)過(guò)了一番對(duì)比，選擇了 go 語(yǔ)言（高并發(fā)度、帶內(nèi)存管理安全性比 C/C++ 好），拋棄了分布式緩存組件（redis/memcached/couchbase），主要理由是多一跳網(wǎng)絡(luò)開銷。這里我表示懷疑，P999 400ms 的時(shí)延其實(shí)不至于擔(dān)心到 redis 網(wǎng)絡(luò)那點(diǎn)時(shí)間，分布式環(huán)境下 local cache 不同機(jī)器間的數(shù)據(jù)不一致帶來(lái)的 cache miss 可能更蛋疼。 最終開發(fā)團(tuán)隊(duì)選擇了實(shí)現(xiàn)一個(gè)支持以下特性的內(nèi)存緩存庫(kù)：

• 百萬(wàn)級(jí)緩存項(xiàng)時(shí)響應(yīng)速度也很快
• 并發(fā)安全
• 支持設(shè)置過(guò)期時(shí)間

4. 關(guān)鍵設(shè)計(jì)

4.1 并發(fā)與 sharding

設(shè)計(jì)上如何做到并發(fā)安全呢？最簡(jiǎn)單的思路就是給 map 上一把 sync.RWMutex 即讀寫鎖。然而當(dāng)緩存項(xiàng)過(guò)多時(shí)，并發(fā)請(qǐng)求會(huì)造成鎖沖突，因此需要降低鎖粒度。bigcache 采用了分布式系統(tǒng)里常用的 sharding 思路，即將一個(gè)大 map 拆分成 N 個(gè)小 map，我們稱為一個(gè) shard(分片)。

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

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

那么在寫入一個(gè) key value 緩存時(shí)，是如何做分片的呢？

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

這里會(huì)首先進(jìn)行一次 hash 操作，將 string key hash 到一個(gè) uint64 類型的 key。再根據(jù)這個(gè)數(shù)字 key 去做 sharding。

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

這里把取余的操作用位運(yùn)算來(lái)實(shí)現(xiàn)了，這也解釋了為什么在使用 bigcache 的時(shí)候需要使用 2 的冪來(lái)初始化 shard num 了。

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

例如使用 1024 作為 shard num 時(shí)，mask 值為 1024 - 1 即二進(jìn)制的 '111111111'，使用 num & mask 時(shí)，即可獲得 num % mask 的效果。

需要注意，這里的 hash 可能是會(huì)沖突的，雖然概率極小，當(dāng)出現(xiàn) hash 沖突時(shí)，bigcache 將直接返回結(jié)果不存在：

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
    }
    // 這里會(huì)將二進(jìn)制 buffer 按順序解開
    // 在打包時(shí)將 key 打包的作用就體現(xiàn)出來(lái)了
    // 如果這次操作的 key 和打包時(shí)的 key 不相同
    // 則說(shuō)明發(fā)生了沖突，不會(huì)錯(cuò)誤地返回另一個(gè) key 的緩存結(jié)果
    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 設(shè)計(jì)

bigcache 對(duì)每個(gè) shard 使用了一個(gè)類似 ringbuffer 的 BytesQueue 結(jié)構(gòu)，定義如下：

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 的底層結(jié)構(gòu)~

在處理完 sharding 后，bigcache 會(huì)將整個(gè) value 與 key、hashedKey 等信息序列化后存進(jìn)一個(gè) byte array，這里的設(shè)計(jì)是不是有點(diǎn)類似網(wǎng)絡(luò)協(xié)議里的 header 呢？

// 將整個(gè) entry 打包到當(dāng)前 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

    // 小端字節(jié)序
    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 沖突用的。

每一個(gè) cacheShard 底層的緩存數(shù)據(jù)都會(huì)存儲(chǔ)在 bytes queue 中，即一個(gè) FIFO 的 bytes 隊(duì)列，新進(jìn)入的 entry 都會(huì) push 到末尾，如果空間不足，則會(huì)產(chǎn)生內(nèi)存分配的過(guò)程，初始的 queue 的大小，是可以在配置中指定的：

func initNewShard(config Config, callback onRemoveCallback, clock clock) *cacheShard {
    // 1. 初始化指定好大小可以減少內(nèi)存分配的次數(shù)
    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,
    }
}

注意到這點(diǎn)，在初始化時(shí)使用正確的配置，就能減少重新分配內(nèi)存的次數(shù)了。

4.3 GC 優(yōu)化

bigcache 本質(zhì)上就是一個(gè)大的哈希表，在 go 里，由于 GC STW(Stop the World) 的存在大的哈希表是非常要命的，看看 bigcache 開發(fā)團(tuán)隊(duì)的博客的測(cè)試數(shù)據(jù)：

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 千萬(wàn)個(gè)對(duì)象，GC 的掃描過(guò)程就超過(guò)了 4 秒鐘，這就不能忍了。

主要的優(yōu)化思路有：

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

當(dāng) map 中的 key 和 value 都是基礎(chǔ)類型時(shí)，GC 就不會(huì)掃到 map 里的 key 和 value

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

經(jīng)過(guò)優(yōu)化，bigcache 在 2000w 條記錄下 GC 的表現(xiàn)：

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

效果挺明顯，但是對(duì)于低延時(shí)的服務(wù)來(lái)說(shuō)，22ms 的 GC 時(shí)間還是很致命的，對(duì)象數(shù)還是盡量能控制住比較好。

5. 小結(jié)

認(rèn)真學(xué)完 bigcache 的代碼，我們至少有以下幾點(diǎn)收獲：

• 可以通過(guò) sharding 來(lái)降低資源競(jìng)爭(zhēng)
• 可以用位運(yùn)算來(lái)取余數(shù)做 sharding （需要是 2 的整數(shù)冪 - 1）
• 避免 map 中出現(xiàn)指針、使用 go 基礎(chǔ)類型可以顯著降低 GC 壓力、提升性能
• bigcache 底層存儲(chǔ)是 bytes queue，初始化時(shí)設(shè)置合理的配置項(xiàng)可以減少 queue 擴(kuò)容的次數(shù)，提升性能

參考資料

• 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優(yōu)化技巧》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 設(shè)計(jì)與分析》https://pandaychen.github.io/2020/03/03/BIGCACHE-ANALYSIS/
• https://github.com/coocood/freecache
• https://github.com/glycerine/offheap 堆外內(nèi)存