1. Go語(yǔ)言本地緩存的實(shí)現(xiàn)

Go語(yǔ)言實(shí)現(xiàn)本地緩存是非常容易的，考慮到語(yǔ)言本身的特性，只要解決了“并發(fā)安全”問題，基本就可以在生產(chǎn)環(huán)境中使用了，常見的解決方案有兩種：

• 使用 sync.Map
• 使用 map 配合 sync.RWMutex

Go語(yǔ)言內(nèi)置的map是非并發(fā)數(shù)據(jù)安全的結(jié)構(gòu)，對(duì)于緩存這種讀多寫少的業(yè)務(wù)，選擇 sync.RWMutex 是比較合適的。sync.Map 則是采用了“空間換時(shí)間“的思路，在讀多寫少的緩存場(chǎng)景中，鎖競(jìng)爭(zhēng)的頻率比 map + sync.RWMtex 更小。這兩種方案實(shí)現(xiàn)本地緩存也都存在一些缺陷：

• 緩存對(duì)象很多時(shí)，鎖競(jìng)爭(zhēng)嚴(yán)重，性能急劇下降
• 大量緩存對(duì)象的寫入導(dǎo)致gc掃描標(biāo)記stw時(shí)間過長(zhǎng)，cpu毛刺嚴(yán)重
• 內(nèi)存占用不可控，緩存對(duì)象不支持按寫入時(shí)間過期和淘汰

為了解決上述問題，大多數(shù)開發(fā)者會(huì)選擇使用開源成熟的庫(kù)；當(dāng)然也可以自己開發(fā)一個(gè)庫(kù)，前提是你要有解決這些問題的思路和過硬的編碼能力。無論從哪個(gè)角度考慮，學(xué)習(xí)一下開源庫(kù)的設(shè)計(jì)，讀一下源碼都是非常有收益的，下邊就帶著這幾個(gè)問題結(jié)合bigcache、fastcache開源庫(kù)的設(shè)計(jì)思路展開。

2. 鎖競(jìng)爭(zhēng)嚴(yán)重問題如何解決?

從實(shí)現(xiàn)上來講，cache的實(shí)現(xiàn)本質(zhì)上是一個(gè)并發(fā)安全的map，sync.RWMutex雖然對(duì)讀寫進(jìn)行了優(yōu)化，但對(duì)于寫操作是串行執(zhí)行的，緩存對(duì)象過多，寫操作的頻率也將變得不可控。一把大鎖終究是問題的瓶頸所在，解決思路是將鎖分片：將大的map拆分成小的map，每個(gè)小map配合一個(gè)sync.RWMutex做保護(hù)。bigcache 和 fastcache都采用了這種方式，bigcache中分片數(shù)量是可配置的。

fastcache更粗暴一點(diǎn)，直接硬編碼寫死了512個(gè)分片。

// source :  https://github.com/VictoriaMetrics/fastcache/blob/master/fastcache.go
const bucketsCount = 512
type Cache struct {
	buckets [bucketsCount]bucket
	bigStats BigStats
}

2.1 分片數(shù)量N如何選擇？

關(guān)于N的選擇，幾乎所有相關(guān)的開源庫(kù)都選擇了2的冪，畢竟位運(yùn)算相對(duì)于取模運(yùn)算可是要快很多的。對(duì)于2的冪N，等式 x mod N = (x & (N − 1)) 成立。

下邊是bigcache作者的實(shí)現(xiàn)：

// source : https://github.com/allegro/bigcache/blob/main/bigcache.go#L249
func (c *BigCache) Get(key string) ([]byte, error) {
	hashedKey := c.hash.Sum64(key)
	shard := c.getShard(hashedKey)
	return shard.get(key, hashedKey)
}
func (c *BigCache) Set(key string, entry []byte) error {
	hashedKey := c.hash.Sum64(key)
	shard := c.getShard(hashedKey)
	return shard.set(key, hashedKey, entry)
}
func (c *BigCache) getShard(hashedKey uint64) (shard *cacheShard) {
	return c.shards[hashedKey&c.shardMask]
}

fastcache的作者似乎并沒有意識(shí)到這一點(diǎn)(也許覺得這點(diǎn)cpu不值一提)，還是采用了取模的方法：

// source : https://github.com/VictoriaMetrics/fastcache/blob/master/fastcache.go
func (c *Cache) Set(k, v []byte) {
	h := xxhash.Sum64(k)
	idx := h % bucketsCount
	c.buckets[idx].Set(k, v, h)
}
func (c *Cache) Get(dst, k []byte) []byte {
	h := xxhash.Sum64(k)
	idx := h % bucketsCount
	dst, _ = c.buckets[idx].Get(dst, k, h, true)
	return dst
}

2.2 hash函數(shù)如何選擇?

map查找時(shí)間復(fù)雜度是O(1)，核心實(shí)現(xiàn)就在于hash函數(shù)。hash函數(shù)實(shí)現(xiàn)有很多，對(duì)于本地緩存應(yīng)用場(chǎng)景來說，主要考慮的點(diǎn)有：

• 哈希值產(chǎn)生的速度，這是衡量hash函數(shù)好壞最關(guān)鍵的指標(biāo)，越快越好。
• 哈希值的隨機(jī)程度，產(chǎn)生的哈希值越隨機(jī)越不容易產(chǎn)生hash沖突，查找性能就越好。
• 耗費(fèi)資源情況(需要分配多少內(nèi)存，對(duì)gc是否產(chǎn)生壓力)。當(dāng)然越小越好。

bigcache 默認(rèn)采用了fnv64a算法。這個(gè)算法的好處是采用位運(yùn)算的方式在棧上進(jìn)行運(yùn)算，避免在堆上分配。

// source : https://github.com/allegro/bigcache/blob/main/fnv.go
type fnv64a struct{}
const (
	// offset64 FNVa offset basis. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
	offset64 = 14695981039346656037
	// prime64 FNVa prime value. See https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function#FNV-1a_hash
	prime64 = 1099511628211
)
// Sum64 gets the string and returns its uint64 hash value.
func (f fnv64a) Sum64(key string) uint64 {
	var hash uint64 = offset64
	for i := 0; i < len(key); i++ {
		hash ^= uint64(key[i])
		hash *= prime64
	}
	return hash
}

fastcache 則采用了XXH64哈希算法，優(yōu)點(diǎn)在于高度可移植性，可以在不同平臺(tái)上生成64位相同的哈希值。bigcache還為為Hash函數(shù)的實(shí)現(xiàn)定義了一個(gè)接口Hasher，開發(fā)者可以選擇不同的hash函數(shù)實(shí)現(xiàn)：

type Hasher interface {
	Sum64(string) uint64
}

3. 零GC的實(shí)現(xiàn)

Go語(yǔ)言自帶垃圾回收機(jī)制，對(duì)于map，垃圾回收器會(huì)并發(fā)標(biāo)記(mark)和掃描(scan)其中的每一個(gè)元素，如果緩存中包含數(shù)百萬(wàn)的緩存對(duì)象，垃圾回收器對(duì)這些對(duì)象的無意義的檢查導(dǎo)致不必要的時(shí)間開銷。

如果我們使用sync.Map或map + sync.RWMutex的實(shí)現(xiàn)方案，垃圾回收將不可避免。而bigcache和fastcache庫(kù)都實(shí)現(xiàn)了零GC。它們都是采用了哪些手段呢？我們一起來看一下。

3.1 使用堆外內(nèi)存

垃圾回收器檢查的是堆上資源，如果不把對(duì)象放到堆上，就自然沒有GC的壓力了。fastcache 使用了這個(gè)思路，分配緩存數(shù)據(jù)內(nèi)存時(shí)使用了golang.org/x/sys/unix庫(kù)，它提供了定制的Mmap方法。但是堆外內(nèi)存非常容易造成內(nèi)存泄漏，慎用！

3.2 map非指針優(yōu)化

Go的開發(fā)者在1.5版本中針對(duì)map的垃圾回收進(jìn)行了優(yōu)化runtime: do not scan maps when k/v do not contain pointers，對(duì)于不包含指針的map，雖然也是分配在堆上，但是垃圾回收可以無視它們。所以說只要將map定義成map[int]int，就能減少gc的壓力。

但是業(yè)務(wù)中我們無法要求緩存對(duì)象只包含int、bool這樣的基礎(chǔ)數(shù)據(jù)類型，為了解決這個(gè)問題，bigcache和fastcache都采用了一種相同的巧妙的解決方法：使用哈希值作為map[uint64]uint32的key。 把緩存對(duì)象序列化后放到一個(gè)預(yù)先分配的大的字節(jié)數(shù)組中，然后將它在數(shù)組中的offset作為map[uint64]uint32的value。下面是bigcache實(shí)現(xiàn)原理架構(gòu)圖：

BytesQueue是一個(gè)字節(jié)數(shù)組，能夠做到按需分配，所以bigcache是能夠根據(jù)緩存大小，自動(dòng)擴(kuò)容的，當(dāng)加入一個(gè)entry時(shí)，會(huì)將它轉(zhuǎn)化為[]byte添加到末尾，也就是說更新元素的值，只是在末尾新增了元素的新值，更新了map[uint64]uint32中的index而已。刪除操作也是將緩存key從map[uint64]uint32中剔除了而已。

fastcache官方文檔介紹，它的靈感來自于bigcache。所以整體的思路和bigcache很類似，數(shù)據(jù)通過bucket進(jìn)行分片。fastcache由512個(gè)bucket構(gòu)成。每個(gè)bucket維護(hù)一把讀寫鎖。在bucket內(nèi)部數(shù)據(jù)同理是索引、數(shù)據(jù)兩部分構(gòu)成。索引用map[uint64]uint64存儲(chǔ)。數(shù)據(jù)采用chunks二維的切片(二維數(shù)組)存儲(chǔ)。我們前邊提到了fastcache使用的是堆外內(nèi)存，根據(jù)chunks大小進(jìn)行內(nèi)存分配與管理，下邊是fastcache實(shí)現(xiàn)的原理架構(gòu)圖：

4. 內(nèi)存占用和過期淘汰策略的抉擇?

4.1 覆蓋寫 or 自動(dòng)擴(kuò)容?

對(duì)于內(nèi)存占用和過期淘汰策略這兩點(diǎn)特性支持上，bigcache和fastcache分別采用了不同的處理思路。

首先f(wàn)astcache受初始化時(shí)內(nèi)存的限制，初始化時(shí)指定的內(nèi)存大小平均分配給512個(gè)bucket(例如總量為 2GB, 那么每個(gè)桶的數(shù)據(jù)就是 4MB)，當(dāng)桶中的數(shù)據(jù)寫滿時(shí)，會(huì)根據(jù)ringbuffer的特性覆蓋寫，剔除比較舊的內(nèi)容。

而bigcache則會(huì)根據(jù)緩存對(duì)象大小自動(dòng)擴(kuò)容，擴(kuò)容是個(gè)很耗時(shí)的工作，可能會(huì)產(chǎn)生大量數(shù)據(jù)的copy。這是fastcache性能比bigcache好的一個(gè)原因。

4.2 數(shù)據(jù)過期需要支持嗎？

fastcache比bigcache性能好的另外一個(gè)原因是：fastcache不支持緩存數(shù)據(jù)的自動(dòng)過期，因此也就沒必要像bigcache一樣做額外的檢查與數(shù)據(jù)清理工作了。對(duì)bigcache而言，要維護(hù)數(shù)據(jù)的過期策略首先在增加一個(gè)元素之前，會(huì)檢查最老的元素要不要?jiǎng)h除；其次，在添加一個(gè)元素失敗后，會(huì)清理空間刪除最老的元素。同時(shí)，還會(huì)專門有一個(gè)定時(shí)的清理goroutine, 負(fù)責(zé)移除過期數(shù)據(jù)。而這些都是以犧牲性能為代價(jià)的，那么這樣做到底有沒有意義呢？

或許有吧！不過fastcache官方文檔上提出的另外一個(gè)觀點(diǎn)是：其實(shí)數(shù)據(jù)的過期，可以由業(yè)務(wù)方將數(shù)據(jù)的過期時(shí)間戳寫入到緩存數(shù)據(jù)中，自行判斷數(shù)據(jù)是否過期。從其功能實(shí)現(xiàn)上而言，也確實(shí)是這樣，畢竟刪除數(shù)據(jù)支持操作了map[uint64]uint64的映射關(guān)系，數(shù)據(jù)并沒有從ringbuffer中真正的清理掉。

5. 小結(jié)

本節(jié)我們圍繞Go語(yǔ)言本地緩存的設(shè)計(jì)展開，提出了設(shè)計(jì)一個(gè)本地緩存需要考慮的幾大因素。然后結(jié)合bigcache和fastcache兩個(gè)優(yōu)秀的開源庫(kù)分析了它們的實(shí)現(xiàn)，還有一些思路上的折中。這些思路都是可以在業(yè)務(wù)開發(fā)中借鑒的。

也并不是說這些開源庫(kù)的實(shí)現(xiàn)都那么的盡善盡美，如果業(yè)務(wù)中有特殊的需求，還可以基于開源庫(kù)做二次開發(fā)，比如：是否有可能實(shí)現(xiàn)一個(gè)本地緩存庫(kù)，既支持緩存對(duì)象單獨(dú)設(shè)置緩存時(shí)間，又能實(shí)現(xiàn)高性能、占用內(nèi)存少呢？又比如：是否能實(shí)現(xiàn)一個(gè)只占用固定內(nèi)存，但可以占用大量磁盤空間，依然保持高性能的緩存庫(kù)呢？我曾經(jīng)思考過這些問題，但是奈何水平有限，沒有什么突破性的進(jìn)展。如果有感興趣或者有思路的小伙伴，可以在評(píng)論區(qū)進(jìn)行交流～

以上就是Go語(yǔ)言實(shí)現(xiàn)本地緩存的策略詳解的詳細(xì)內(nèi)容，更多關(guān)于Go本地緩存的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！