00. 什么是 freecache？

freecache 是一個(gè)用 go 語(yǔ)言實(shí)現(xiàn)的本地緩存系統(tǒng)（類似于 lru）。

相關(guān)的 github 地址：https://github.com/coocood/freecache

它有幾個(gè)特性值得注意：

• 通過(guò)優(yōu)秀的內(nèi)存管理方案，實(shí)現(xiàn)了 go 語(yǔ)言的零 gc
• 是線程安全的，同時(shí)支持一定程度的并發(fā)，非常適合并發(fā)場(chǎng)景
• 支持設(shè)置失效時(shí)間，動(dòng)態(tài)失效過(guò)期緩存
• 在一定程度上支持 lru，即“最近最少使用”，會(huì)在容量不足的時(shí)候優(yōu)先淘汰較早的數(shù)據(jù)

這幾個(gè)優(yōu)秀特性使得他非常適合用在生產(chǎn)環(huán)境中作為本地緩存。

01. 簡(jiǎn)單用法

cacheSize := 100 * 1024 * 1024
cache := freecache.NewCache(cacheSize)
debug.SetGCPercent(20)
key := []byte("abc")
val := []byte("def")
expire := 60 // expire in 60 seconds
cache.Set(key, val, expire)
got, err := cache.Get(key)
if err != nil {
    fmt.Println(err)
} else {
    fmt.Println(string(got))
}
affected := cache.Del(key)
fmt.Println("deleted key ", affected)
fmt.Println("entry count ", cache.EntryCount())

02. 功能概覽

本文計(jì)劃先以自然語(yǔ)言描述下列功能的實(shí)現(xiàn)方式，再接下來(lái)的章節(jié)中深入源碼，扒出其具體實(shí)現(xiàn)

• 如何做到零 gc？
• 數(shù)據(jù)結(jié)構(gòu)
• 動(dòng)態(tài)索引
• 緩存失效

03. 如何做到 0 GC？

這個(gè)庫(kù)之所以做到了 0 gc，是因?yàn)樵O(shè)定了很巧妙的數(shù)據(jù)結(jié)構(gòu)，這個(gè)數(shù)據(jù)結(jié)構(gòu)有以下的特點(diǎn)：

• 無(wú)論存多少數(shù)據(jù)，都只會(huì)存在 512 個(gè)指針
• 所有的具體數(shù)據(jù)的存儲(chǔ)空間，都是預(yù)先就分配好的，而不是動(dòng)態(tài)分配的
• 使用了一些黑科技，比如強(qiáng)制類型轉(zhuǎn)換以及結(jié)構(gòu)體對(duì)齊等技術(shù)，將所有的動(dòng)態(tài)數(shù)據(jù)都管理在預(yù)先分配好的連續(xù)空間內(nèi)

04. 數(shù)據(jù)結(jié)構(gòu)

可以將這個(gè)數(shù)據(jù)結(jié)構(gòu)大體上抽象成一個(gè)哈希表。即你會(huì)看到哈希函數(shù)以及對(duì)應(yīng)的數(shù)組空間。但是他和傳統(tǒng)的哈希表是有區(qū)別的，主要有以下幾點(diǎn)：

• 線程安全，支持高并發(fā)，內(nèi)存空間高度優(yōu)化：

• 為了做到支持高并發(fā)以及線程安全，并且保證內(nèi)存空間的可用性，freecache 實(shí)際上劃分出了 256 個(gè)獨(dú)立數(shù)組空間用來(lái)存儲(chǔ)對(duì)應(yīng)的底層數(shù)據(jù)。
• 這樣在并發(fā)訪問(wèn)的時(shí)候，通過(guò)對(duì) key 進(jìn)行分片，使得請(qǐng)求只會(huì)打到一個(gè)數(shù)組空間上，即只會(huì)對(duì)這 256 個(gè)空間中的一個(gè)空間加鎖，這樣就大大降低了資源爭(zhēng)搶。

• 數(shù)據(jù)的組織方式與傳統(tǒng)哈希表不同：

• 傳統(tǒng)的哈希表只在數(shù)組空間中存 value。而 freecache 則不同，他將 key，value 全部存在了數(shù)組空間中。
• 傳統(tǒng)哈希表的數(shù)組是稀疏的。freecache 數(shù)據(jù)并不是稀疏的，而是連續(xù)的，即新的值會(huì)不斷 append 到最后。
• 傳統(tǒng)哈希表使用 hash func 對(duì) key 取索引，索引到稀疏數(shù)組中的位置。而 freecache 則通過(guò)維護(hù)了一個(gè)叫“slot（插槽）”的數(shù)據(jù)結(jié)構(gòu)，通過(guò)對(duì) key 進(jìn)行 hash func，先拿到對(duì)應(yīng)的 slot，然后 slot 中維護(hù)著一個(gè)索引，可以定位到具體的數(shù)據(jù)在數(shù)組中的位置。
• 解決哈希沖突的方式不同。當(dāng)遇到哈希沖突的時(shí)候，哈希表需要對(duì)底層的稀疏數(shù)組進(jìn)行擴(kuò)容，會(huì)導(dǎo)致可用性大大降低。而 freecache 則是只需要對(duì)“slot”的指針數(shù)組進(jìn)行擴(kuò)容，而無(wú)需改變底層數(shù)組。因?yàn)?slot 指針數(shù)組的大小遠(yuǎn)小于底層數(shù)組，所以擴(kuò)容的成本是非常非常低的。

• 為了實(shí)現(xiàn)緩存淘汰以及定時(shí)失效，它的數(shù)組空間在邏輯上是一個(gè)環(huán)狀的。這么做有以下原因

• 數(shù)組存的數(shù)據(jù)邏輯上是連續(xù)的，而非稀疏數(shù)組。充分利用了CPU對(duì)數(shù)組讀取的緩存優(yōu)化
• 通過(guò)使用了一系列的首尾計(jì)算方式，是足以保證讀取和存儲(chǔ)在首尾的連續(xù)性。比如讀數(shù)據(jù)的時(shí)候讀到結(jié)尾如果還沒(méi)讀完，會(huì)跳轉(zhuǎn)到頭部繼續(xù)往下讀。
• 能以 O（1） 的時(shí)間復(fù)雜度完成新數(shù)據(jù)對(duì)舊數(shù)據(jù)的淘汰。我們假設(shè)如果數(shù)組在邏輯上不是環(huán)形的，那么當(dāng)數(shù)組寫滿的時(shí)候再寫入新的數(shù)據(jù)，就需要把數(shù)組頭部的數(shù)據(jù)刪除掉，然后再把之后的數(shù)據(jù)統(tǒng)統(tǒng)向左移動(dòng)刪除數(shù)據(jù)的長(zhǎng)度，然后再?gòu)淖钣叶藢懭胄碌臄?shù)據(jù)。反之，如果數(shù)組是環(huán)形的，只需要在數(shù)組頭部把舊數(shù)據(jù)覆蓋即可
• 通過(guò)一些算法手段，可以實(shí)現(xiàn)一個(gè)很 hack 的 lru 功能。在一定程度上能保證“最近最少使用”的淘汰。

05. 動(dòng)態(tài)索引

通過(guò)上面對(duì)數(shù)據(jù)結(jié)構(gòu)的分析，我們知道他和傳統(tǒng)的哈希表的實(shí)現(xiàn)方式大相徑庭。它實(shí)際上是使用了一種叫“插槽”的數(shù)據(jù)結(jié)構(gòu)，專門負(fù)責(zé)通過(guò) key 索引到數(shù)據(jù)空間中的某個(gè)位置。他的實(shí)現(xiàn)比較有意思。它的底層是一個(gè)結(jié)構(gòu)體指針數(shù)組。他是可以動(dòng)態(tài)擴(kuò)容的。每個(gè)插槽有一個(gè) id，叫 slotId，范圍是 0～255。當(dāng)遇到哈希沖突的時(shí)候，比如出現(xiàn)了2個(gè) slotId 為 100 的 slot，他就會(huì)檢測(cè)當(dāng)前的最大重復(fù) slotID 數(shù)量 n。如果這個(gè) 2 大于 n，他就會(huì)擴(kuò)容到 2n。

// slot 的數(shù)據(jù)結(jié)構(gòu)
type entryPtr struct {
	offset   int64  // 記錄了當(dāng)前 slot 在環(huán)形數(shù)組中的偏移量
	hash16   uint16 // 一個(gè) hash 值，用于在 segment 中定位到具體的 slot
	keyLen   uint16 // used to compare a key
	reserved uint32
}
// 每個(gè)分片的數(shù)據(jù)結(jié)構(gòu)
type segment struct {
	rb            RingBuf // 環(huán)形數(shù)組
	segId         int
	hitCount      int64
	missCount     int64
	entryCount    int64
	totalCount    int64      // 之后計(jì)算 lru 的時(shí)候會(huì)用到，用于衡量一個(gè)數(shù)據(jù)是否是熱點(diǎn)數(shù)據(jù)
	totalTime     int64      // 之后計(jì)算 lru 的時(shí)候會(huì)用到，用于衡量一個(gè)數(shù)據(jù)是否是熱點(diǎn)數(shù)據(jù)
	totalEvacuate int64      // used for debug
	totalExpired  int64      // used for debug
	overwrites    int64      // used for debug
	vacuumLen     int64      // 環(huán)形數(shù)組可用容量，主要用于環(huán)形數(shù)組首尾相接的算法
	slotLens      [256]int32 // 每個(gè) slotId 的長(zhǎng)度的數(shù)組
	slotCap       int32      // 每個(gè) slotId 的容量
	slotsData     []entryPtr // 存儲(chǔ) slots 的切片，根據(jù) hash16 進(jìn)行順序排列。相同的 hash16 擁有相同的 slotId
}

06. 緩存失效

緩存失效主要包括兩種：

• 基于過(guò)期時(shí)間的失效
• 基于最近最少使用的失效

這兩種失效都有缺陷。

首先它是一種被動(dòng)失效，而不是通過(guò)一個(gè)額外的線程定期check。而是每次 set 新的值的時(shí)候，如果發(fā)現(xiàn)空間不夠用了，他才會(huì)嘗試從環(huán)形數(shù)組的頭端進(jìn)行check。如果發(fā)現(xiàn)當(dāng)前check的數(shù)據(jù)過(guò)期了，或者使用頻率過(guò)低，就會(huì)將記錄有效數(shù)據(jù)的頭指針進(jìn)行偏移，即相當(dāng)于“失效”。如果檢查多次都沒(méi)能找到需要失效的數(shù)據(jù)，那么他會(huì)將這些檢查過(guò)的數(shù)據(jù)轉(zhuǎn)移到尾部，并強(qiáng)制當(dāng)前的頭部的數(shù)據(jù)失效。

這種失效是不可靠的。比如一個(gè)數(shù)據(jù)，如果在環(huán)形數(shù)組的中間，那么即便它過(guò)期了，也很難被 check 到。并且存在一定的失誤概率，即將一個(gè)熱點(diǎn)數(shù)據(jù)給失效了。

以上就是Go 語(yǔ)言進(jìn)階freecache源碼學(xué)習(xí)教程的詳細(xì)內(nèi)容，更多關(guān)于Go語(yǔ)言freecache的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論