妙到顛毫：你應該學會的 bigcache 優化技巧

本文作者：鳥窩 smallnest

原文連結：https://colobu.com/2019/11/18/how-is-the-bigcache-is-fast/

最近看到 yoko 翻譯的一篇文章: [譯] Go 開源項目 BigCache 如何加速並發訪問以及避免高額的 GC 開銷[1]，翻譯自 How BigCache avoids expensive GC cycles and speeds up concurrent access in Go[2], 應該是 Douglas Makey Mendez Molero 在閱讀了 bigcache 的作者寫的 bigcache 設計文章Writing a very fast cache service with millions of entries in Go[3]做的一些調研和總結。

我在剛讀取這篇文檔的時候，順著連接把相關的文章都找出來細細讀了一遍，結合 bigcache 的代碼，仔細學習了相關的優化設計，感覺設計非常的精妙，所以特意根據自己的理解又總結了一篇。

bigcache 的精妙的設計也吸引了 fasthttp 的作者 Aliaksandr Valialkin，他在 bigcache 的基礎上，結合自己的公司的使用場景，進一步的做了相應的優化，也開源了這個項目 fastcache[4], 本文在最後也做了介紹。

設計 BigCache 的初衷

bigcache 的作者也不是想當然的開發一個庫，而且項目遇到了需求。需求如下：

• 支持 http 協議
• 支持 10K RPS (5k 寫，5k 讀)
• cache 對象至少保持 10 分鐘
• 相應時間平均 5ms, p99.9 10 毫秒， p99.999 400 毫秒
• 其它 HTTP 的一些需求

為了滿足這些需求，要求開發的 cache 庫要保證：

• 即使有百萬的緩存對象也要非常快
• 支持大並發訪問
• 一定時間後支持剔除

作者考察了一番緩存框架比如 memcached、redis、couchbase 等，發覺都不太滿足需求，因為這些都是獨立的程序，訪問它們需要網絡的開銷，延時無法保障，作者需要一個進程內的基於內存的 cache 庫。雖然 Go 生態圈有眾多的 cache 庫如 LRU groups cache[5], go-cache[6], ttlcache[7], freecache[8]，但是只有 freecache 滿足需求，不過作者最後還是決定自己取開發一個 cache 庫。

以上是 bigcache 誕生的背景，接下來我們欣賞一下 bigcache 和其它庫優美的設計。

處理大並發訪問

cache 就像一個大的 hashtable, 可不可以使用一個map[string][]byte + sync.RWMutex實現滿足需求的 cache 呢？

sync.RWMutex雖然對讀寫進行了優化，但是對於並發的讀，最終還是把寫變成了串行，一旦寫的並發量大的時候，即使寫不同的 key, 對應的 goroutine 也會 block 住，只允許一個寫執行，這是一個瓶頸，並且不可控。

解決並發的問題有一個方法叫做 shard (分片)，每個分片一把鎖。很多大並發場景下為了減小並發的壓力都會採用這種方法，大的場景比如資料庫的分片，小的場景就如剛才的場景。Java 8 之前的 ConcurrentMap 就是採用分片(segment)的方式減少競爭, Go 也有一個類似思想設計的 map 庫:concurrent-map[9]。

對於每一個緩存對象，根據它的 key 計算它的哈希值: hash(key) % N, N是分片數量。理想情況下 N 個 goroutine 每次請求正好平均落在各自的分片上，這樣就不會有競爭了，即使有多個 goroutine 落在同一個分片上，如果 hash 比較平均的話，單個 shard 的壓力也會比較小。

競爭小了有什麼好處？延遲可以大大提高，因為等待獲取鎖的時間變小了。

當然這裡有一些要考慮的地方：

1、N 的選擇

既然分片可以很好的降低鎖的競爭，那麼 N 是不是越大越好呢？當然不是，如果 N 非常大，比如每個緩存對象一個鎖，那麼會帶來很多額外的不必要的開銷。可以選擇一個不太大的值，在性能和花銷上尋找一個平衡。

另外, N 是 2 的冪， 比如 16、32、64。這樣設計的好處就是計算餘數可以使用位運算快速計算。

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

因為對於 2 的冪 N，對於任意的x, 下面的公式成立:

x mod N = (x & (N − 1))

所以只需要使用一次按位 AND (&)就可以求得它的餘數。

2、選擇 hash 算法

以前已經有非常多的哈希算法，最近幾年也出現了一些新的哈希算法，也被人使用 Go 語言來實現。

很顯然，一個優秀的哈希算法要保證:

• 哈希值應該比較隨機 (質量)
• 哈希速度比較快 (速度)
• 儘量不產生額外的內存分配，避免對垃圾回收產生壓力 (耗費資源少)

項目hash-bench[10]對常用的幾種 Hash 算法進行了比較。

bigcache 提供了一個默認的 Hash 的實現，採用 fnv64a 算法。這個算法的好處是採用位運算的方式在棧上進行運算，避免在堆上分配。

type fnv64a struct{}

const (

\t// offset64 FNVa offset basis. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
\toffset64 = 14695981039346656037

\t// prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
\tprime64 = 1099511628211
)

// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {
\tvar hash uint64 = offset64
\tfor i := 0; i < len(key); i++ {
\t\thash ^= uint64(key[i])
\t\thash *= prime64
\t}

\treturn hash
}

忽略內存開銷

對於 Go 語言中的 map, 垃圾回收器在 mark 和 scan 階段檢查 map 中的每一個元素, 如果緩存中包含數百萬的緩存對象，垃圾回收器對這些對象的無意義的檢查導致不必要的時間開銷。

bigcache 的作者做了測試。他們測試了簡單的 HTTP/JSON 序列化(不會訪問 cache)。在 cache 為空的時候 1 萬的 QPS 的耗時大約 10 毫秒。當 cache 填滿的時候， 99% 的請求都會超過 1 秒。監控顯示堆中包含 4 千萬的對象， GC 過程中的 mark 和 scan 也需要 4 秒。

我們可以很容易測試這種狀況，比如下面的代碼：

package main

import "time"

type Item struct {
\tA string
\tB string
\tC string
\tD string
\tE string
\tF string
\tG G
}

type G struct {
\tH int
\tI int
\tK int
\tL int
\tM int
\tN int
}

func main() {
\tm := make(map[int]*Item, 10*1024*1024)

\tfor i := 0; i < 1024*1024; i++ {
\t\tm[i] = &Item{}
\t}

\tfor i := 0; ; i++ {
\t\tdelete(m, i)
\t\tm[1024*1024+i] = &Item{}
\t\ttime.Sleep(10 * time.Millisecond)
\t}
}

只有一個 map 對象，裡面包含一百萬的元素，每 10 毫秒刪一個放一個。

並發量相當小，並且單個的 goroutine 也沒有競爭，但是由於元素的數量巨大，垃圾回收在mark/scan階段需要花費上百毫秒進行標記和遍歷。

那麼如何解決這個問題呢？

我們知道垃圾回收器檢查的是堆上的資源，如果不把對象放在堆上，不就解決這個問題了嗎？還真有這樣的項目offheap[11]，它提供了定製的Malloc() 和 Free()，但是你的緩存需要基於這些方法定製。當然一些基於垃圾回收的程式語言為了減少垃圾回收的時間，都會提供相應的庫，比如Java: ChronicleMap, Part 1: Go Off-Heap[12]。堆外內存很容易產生內存泄漏。

第二種方式是使用 freecache[13]。freecache 通過減少指針的數量以零 GC 開銷實現 map。它將鍵和值保存在ringbuffer中，並使用索引查找對象。

第三種優化方法是和 Go 1.5 中一個修復有關(#9477[14]), 這個 issue 還描述了包含大量對象的 map 的垃圾回收時的耗時問題，Go 的開發者優化了垃圾回收時對於 map 的處理，如果 map 對象中的 key 和 value 不包含指針，那麼垃圾回收器就會對它們進行優化：

runtime: do not scan maps when k/v do not contain pointers

Currently we scan maps even if k/v does not contain pointers. This is required because overflow buckets are hanging off the main table. This change introduces a separate array that contains pointers to all overflow buckets and keeps them alive. Buckets themselves are marked as containing no pointers and are not scanned by GC (if k/v does not contain pointers).

This brings maps in line with slices and chans -- GC does not scan their contents if elements do not contain pointers.

Currently scanning of a map[int]int with 2e8 entries (~8GB heap) takes ~8 seconds. With this change scanning takes negligible time.

https://go-review.googlesource.com/c/go/+/3288

所以如果我們的對象不包含指針，雖然也是分配在堆上，但是垃圾回收可以無視它們。

如果我們把 map 定義成 map[int]int，就會發現 gc 的耗時就會降下來了。

遺憾的是，我們沒辦法要求用戶的緩存對象只能包含int、bool這樣的基本數據類型。

解決辦法就是使用哈希值作為map[int]int的 key。把緩存對象序列化後放到一個預先分配的大的位元組數組中，然後將它在數組中的 offset 作為map[int]int的 value。

type cacheShard struct {
\thashmap     map[uint64]uint32
\tentries     queue.BytesQueue
\tlock        sync.RWMutex
\tentryBuffer []byte
\tonRemove    onRemoveCallback
\tisVerbose    bool
\tstatsEnabled bool
\tlogger       Logger
\tclock        clock
\tlifeWindow   uint64
\thashmapStats map[uint64]uint32
\tstats        Stats
}
func (s *cacheShard) set(key string, hashedKey uint64, entry []byte) error {
\tcurrentTimestamp := uint64(s.clock.epoch())
\ts.lock.Lock()
    // 查找是否已經存在了對應的緩存對象，如果存在，將它的值置為空
\tif previousIndex := s.hashmap[hashedKey]; previousIndex != 0 {
\t\tif previousEntry, err := s.entries.Get(int(previousIndex)); err == nil {
\t\t\tresetKeyFromEntry(previousEntry)
\t\t}
\t}
    // 觸發是否要移除最老的緩存對象
\tif oldestEntry, err := s.entries.Peek(); err == nil {
\t\ts.onEvict(oldestEntry, currentTimestamp, s.removeOldestEntry)
\t}
    // 將對象放入到一個位元組數組中，如果已有的位元組數組(slice)可以放得下此對象，則重用，否則新建一個位元組數組
\tw := wrapEntry(currentTimestamp, hashedKey, key, entry, &s.entryBuffer)
\tfor {
        // 嘗試放入到位元組隊列中，成功則加入到map中
\t\tif index, err := s.entries.Push(w); err == nil {
\t\t\ts.hashmap[hashedKey] = uint32(index)
\t\t\ts.lock.Unlock()
\t\t\treturn nil
        }
        // 如果空間不足，移除最老的元素
\t\tif s.removeOldestEntry(NoSpace) != nil {
\t\t\ts.lock.Unlock()
\t\t\treturn fmt.Errorf("entry is bigger than max shard size")
\t\t}
\t}
}
func wrapEntry(timestamp uint64, hash uint64, key string, entry []byte, buffer *[]byte) []byte {
\tkeyLength := len(key)
\tblobLength := len(entry) + headersSizeInBytes + keyLength
\tif blobLength > len(*buffer) {
\t\t*buffer = make([]byte, blobLength)
\t}
\tblob := *buffer
\tbinary.LittleEndian.PutUint64(blob, timestamp)
\tbinary.LittleEndian.PutUint64(blob[timestampSizeInBytes:], hash)
\tbinary.LittleEndian.PutUint16(blob[timestampSizeInBytes+hashSizeInBytes:], uint16(keyLength))
\tcopy(blob[headersSizeInBytes:], key)
\tcopy(blob[headersSizeInBytes+keyLength:], entry)
\treturn blob[:blobLength]
}

queue.BytesQueue 是一個位元組數組，可以做到按需分配。當加入一個[]byte時，它會把數據 copy 到尾部。

值得注意的是刪除緩存元素的時候 bigcache 只是把它的索引從map[uint64]uint32中刪除了，並把它在queue.BytesQueue隊列中的長度置為 0。那麼刪除操作會不會在queue.BytesQueue中造成很多的「蟲洞」？從它的實現上來看，會, 而且這些"蟲洞"不會被整理，也不會被移除。因為它的底層是使用一個位元組數組實現的，"蟲洞"的移除是一個耗時的操作，會導致鎖的持有時間過長。那麼尋找合適的"蟲洞"重用呢？雖然遍歷的方法尋找"蟲洞"也是一個比較耗時的操作，我覺得這裡有優化的空間。

bigcache 只能等待清理最老的元素的時候把這些"蟲洞"刪除掉。

剔除

對於 bigcache 來說，剔除還有意義嗎？或許有。如果我們不想使用某個 key 的緩存對象，我們可以把它刪除。

首先，在增加一個元素之前，會檢查最老的元素要不要刪除。

if oldestEntry, err := s.entries.Peek(); err == nil {
\ts.onEvict(oldestEntry, currentTimestamp, s.removeOldestEntry)
}

其次，在添加一個元素失敗後，會清理空間刪除最老的元素。

同時， 還會專門有一個定時的清理 goroutine, 負責移除過期數據。

另外需要注意的是緩存對象沒有讀取的時候刷新過期時間的功能，所以放入的緩存對象最終免不了過期的命運。

另外所有的緩存對象的 lifewindow 都是一樣的，比如 30 分鐘、兩小時。

所以，如果你真的使用 bigcache, 還是得需要注意它的這些設計，看看這些設計是否和你的場景相吻合。

fastcache

bigcache 在特定時候還是有問題，就是當 queue.BytesQueue 的容量不夠的時候，它會進行擴展，擴展是一個很重的操作，它會複製原來的數據到新的位元組數組上。

fasthttp 的作者採用類似 bigcache 的思想實現了fastcache[15]，他使用 chunks [][]byte替換 queue.BytesQueue，chunk 是一個 ring buffer, 每個 chunk 64KB。

type bucket struct {
\tmu sync.RWMutex
\t// chunks is a ring buffer with encoded (k, v) pairs.
\t// It consists of 64KB chunks.
\tchunks [][]byte
\t// m maps hash(k) to idx of (k, v) pair in chunks.
\tm map[uint64]uint64
\t// idx points to chunks for writing the next (k, v) pair.
\tidx uint64
\t// gen is the generation of chunks.
\tgen uint64
\tgetCalls    uint64
\tsetCalls    uint64
\tmisses      uint64
\tcollisions  uint64
\tcorruptions uint64
}

雖然chunks [][]byte也包含很多的 chunk, 但是由於 chunk 的 size 比較大，所以可以大大縮小垃圾回收需要 mark/scan 的對象的數量。帶來的好處就是擴容的時候只需要增加更多的 chunk 即可。

刪除還是一樣，只是從 map 中刪除，不會從chunks中刪除。

fastcache 沒有過期的概念，所以緩存對象不會被過期剔除。

參考文檔

1. http://allegro.tech/2016/03/writing-fast-cache-service-in-go.html
2. https://github.com/allegro/bigcache
3. https://dev.to/douglasmakey/how-bigcache-avoids-expensive-gc-cycles-and-speeds-up-concurrent-access-in-go-12bb
4. https://pengrl.com/p/35302/
5. https://github.com/VictoriaMetrics/fastcache
6. https://www.openmymind.net/Shard-Your-Hash-table-to-reduce-write-locks/
7. https://medium.com/@itsromiljain/curious-case-of-concurrenthashmap-90249632d335
8. https://segmentfault.com/a/1190000012926722
9. https://github.com/coocood/freecache

文中連結

[1]

[譯] Go開源項目BigCache如何加速並發訪問以及避免高額的GC開銷: https://pengrl.com/p/35302/

[2]

How BigCache avoids expensive GC cycles and speeds up concurrent access in Go: https://dev.to/douglasmakey/how-bigcache-avoids-expensive-gc-cycles-and-speeds-up-concurrent-access-in-go-12bb

[3]

Writing a very fast cache service with millions of entries in Go: https://allegro.tech/2016/03/writing-fast-cache-service-in-go.html

[4]

fastcache: https://github.com/VictoriaMetrics/fastcache

[5]

LRU groups cache: https://github.com/golang/groupcache/tree/master/lru

[6]

go-cache: https://github.com/patrickmn/go-cache

[7]

ttlcache: https://github.com/diegobernardes/ttlcache

[8]

freecache: https://github.com/coocood/freecache

[9]

concurrent-map: https://github.com/orcaman/concurrent-map

[10]

hash-bench: https://github.com/smallnest/hash-bench

[11]

offheap: https://godoc.org/github.com/glycerine/offheap

[12]

Java: ChronicleMap, Part 1: Go Off-Heap: https://dzone.com/articles/java-chroniclemap-part-1-go-off-heap

[13]

freecache: https://github.com/coocood/freecache

[14]

#9477: https://github.com/golang/go/issues/9477

[15]

fastcache: https://github.com/VictoriaMetrics/fastcache

喜歡本文的朋友，歡迎關注「Go語言中文網」：

Go語言中文網啟用微信學習交流群，歡迎加微信：274768166