手撕 Golang 高性能內(nèi)存緩存庫(kù) bigcache! #4
1. 前言
你好哇！我是小翔。之前寫(xiě)了三篇 #Golang 并發(fā)編程 的文章了，這次來(lái)?yè)Q換口味，開(kāi)個(gè) 手撕源碼 的新坑！一起來(lái)扒一扒 Go 語(yǔ)言高性能 local cache 庫(kù) bigcache，看看能不能把開(kāi)源大佬們的騷操作帶到項(xiàng)目里去裝一裝（？）
2. 為什么要學(xué)習(xí)開(kāi)源項(xiàng)目
個(gè)人認(rèn)為學(xué)習(xí)開(kāi)源項(xiàng)目的收益：
跟進(jìn)社區(qū)，不做井底之蛙 看到一個(gè)開(kāi)源項(xiàng)目，可以思考下：大佬們最近都在解決哪些問(wèn)題？他們用到了哪些開(kāi)源工具？我能拿到項(xiàng)目里用嗎？這玩意有 bug 嗎？要不要提個(gè) issue 或者提個(gè) PR 呢？ 面向原理編程 我們?cè)趯?shí)際項(xiàng)目中會(huì)用上很多開(kāi)源庫(kù)/框架，你是否好奇過(guò)它們的實(shí)現(xiàn)機(jī)制呢？理解用到的庫(kù)的實(shí)現(xiàn)機(jī)制，能幫我們避開(kāi)很多坑，堪稱(chēng)降維打擊 學(xué)習(xí)優(yōu)秀的設(shè)計(jì) 優(yōu)秀的開(kāi)源項(xiàng)目經(jīng)過(guò)了成千上萬(wàn)開(kāi)發(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ā)安全的本地緩存了。常見(jiàn)的，將一些靜態(tài)的、配置類(lè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 的開(kāi)發(fā)者是 allegro，是波蘭的一個(gè)電商網(wǎng)站，參考資料中給出了他們的技術(shù)博客的原文，文中詳細(xì)描述了他們問(wèn)題的背景以及思考，值得研究。他們的需求主要是：
用 HTTP 協(xié)議處理 GET POST 請(qǐng)求，body 不大 10k rps(requests per second) 5k 讀 5k 寫(xiě) 緩存至少 10 分鐘 低延時(shí)：平均 5ms ，P99 < 10ms，P999 < 400ms
總結(jié)一下，他們需要一個(gè)快速、支持過(guò)期淘汰、支持 RESTful api 的字典服務(wù)
開(kāi)發(fā)團(tuán)隊(duì)經(jīng)過(guò)了一番對(duì)比，選擇了 go 語(yǔ)言（高并發(fā)度、帶內(nèi)存管理安全性比 C/C++ 好），拋棄了分布式緩存組件（redis/memcached/couchbase），主要理由是多一跳網(wǎng)絡(luò)開(kāi)銷(xiāo)。這里我表示懷疑，P999 400ms 的時(shí)延其實(shí)不至于擔(dān)心到 redis 網(wǎng)絡(luò)那點(diǎn)時(shí)間，分布式環(huán)境下 local cache 不同機(jī)器間的數(shù)據(jù)不一致帶來(lái)的 cache miss 可能更蛋疼。 最終開(kāi)發(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 即讀寫(xiě)鎖。然而當(dāng)緩存項(xiàng)過(guò)多時(shí)，并發(fā)請(qǐng)求會(huì)造成鎖沖突，因此需要降低鎖粒度。bigcache 采用了分布式系統(tǒng)里常用的 sharding 思路，即將一個(gè)大 map 拆分成 N 個(gè)小 map，我們稱(chēng)為一個(gè) shard(分片)。
如 bigcache.go 的聲明，我們初始化得到的 BigCache，核心實(shí)際上是一個(gè) []*cacheShard，緩存的寫(xiě)入、淘汰等核心邏輯都在 cacheShard 中了。
type BigCache struct {
shards []*cacheShard
lifeWindow uint64
clock clock
hash Hasher
config Config
shardMask uint64
close chan struct{}
}
那么在寫(xiě)入一個(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 類(lèi)型的 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 按順序解開(kāi)
// 在打包時(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è)類(lèi)似 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)類(lèi)似網(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 開(kāi)發(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)化思路有：
offheap（堆外內(nèi)存），GC 只會(huì)掃描堆上的對(duì)象，那就把對(duì)象都搞到棧上去，但是這樣這個(gè)緩存庫(kù)就高度依賴(lài) offheap 的 malloc 和 free 操作了 參考 freecache 的思路，用 ringbuffer存 entry，繞過(guò)了 map 里存指針，簡(jiǎn)單瞄了一下代碼，后面有空再研究一下（繼續(xù)挖坑利用 Go 1.5+ 的特性：
當(dāng) map 中的 key 和 value 都是基礎(chǔ)類(lèi)型時(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ǔ)類(lèi)型可以顯著降低 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 《鳥(niǎo)窩 - 妙到顛毫: 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)存
往期推薦
想要了解Go更多內(nèi)容，歡迎掃描下方?? 關(guān)注 公眾號(hào)，回復(fù)關(guān)鍵詞 [實(shí)戰(zhàn)群] ,就有機(jī)會(huì)進(jìn)群和我們進(jìn)行交流~
分享、在看與點(diǎn)贊，至少我要擁有一個(gè)叭~
