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

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

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

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

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

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

2. 鎖競爭嚴(yán)重問題如何解決?

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

fastcache更粗暴一點，直接硬編碼寫死了512個分片。

// 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)的開源庫都選擇了2的冪，畢竟位運算相對于取模運算可是要快很多的。對于2的冪N，等式 x mod N = (x & (N − 1)) 成立。

下邊是bigcache作者的實現(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的作者似乎并沒有意識到這一點(也許覺得這點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查找時間復(fù)雜度是O(1)，核心實現(xiàn)就在于hash函數(shù)。hash函數(shù)實現(xiàn)有很多，對于本地緩存應(yīng)用場景來說，主要考慮的點有：

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

bigcache 默認(rèn)采用了fnv64a算法。這個算法的好處是采用位運算的方式在棧上進(jì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)點在于高度可移植性，可以在不同平臺上生成64位相同的哈希值。bigcache還為為Hash函數(shù)的實現(xiàn)定義了一個接口Hasher，開發(fā)者可以選擇不同的hash函數(shù)實現(xiàn)：

type Hasher interface {
	Sum64(string) uint64
}

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

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

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

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

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

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

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

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

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

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

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

4.1 覆蓋寫 or 自動擴容?

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

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

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

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

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

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

5. 小結(jié)

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

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

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

最新評論