本文經(jīng)公眾號(hào)：騰訊科技公司(ID: Tencent _ TEG)許可，可以轉(zhuǎn)載。如果需要轉(zhuǎn)載，請(qǐng)聯(lián)系出處。

作者：deryzhou，騰訊 PCG 后臺(tái)開(kāi)發(fā)工程師

Go 中怎么實(shí)現(xiàn)內(nèi)存池，直接用 map 可以嗎？常用庫(kù)里 GroupCache、Bigcache 的內(nèi)存池又是怎么實(shí)現(xiàn)的？有沒(méi)有坑？對(duì)象池又是什么？想看重點(diǎn)的同學(xué)，可以直接看第 2 節(jié) GroupCache 總結(jié)。

0. 前言: tcmalloc 與 Go

以前 C++服務(wù)上線，遇到性能優(yōu)化一定會(huì)涉及 Google 大名鼎鼎的 tcmalloc。

相比 glibc，tcmalloc 在多線程下有巨大的優(yōu)勢(shì)：

vs tcmalloc

其中使用的就是內(nèi)存池技術(shù)。如果想了解 tcmalloc 的細(xì)節(jié)，盜一張圖解 TCMalloc中比較經(jīng)典的結(jié)構(gòu)圖：

圖解 TCMalloc

作為 Google 的得意之作，Golang自然也用上了 tcmalloc 的內(nèi)存池03 技術(shù)。因此我們普通使用 Golang 時(shí)，無(wú)需關(guān)注內(nèi)存分配的性能問(wèn)題。

1. 關(guān)于 map 你需要了解的

既然 Go 本身內(nèi)存已經(jīng)做了 tcmalloc 的管理，那實(shí)現(xiàn)緩存我們能想到的就是 map 了，是吧？（但仔細(xì)想想，map 不需要加鎖嗎？不加鎖用 更好嗎）

坑 1: 為什么不用

2020-05-09 補(bǔ)充：多位同學(xué)也提到了，bigcache 這個(gè)測(cè)試并不公平。查了下 issues，map+lock 和 的有人做過(guò)測(cè)試，性能確實(shí)低一些（單鎖的情況）

但如果是 shards map+lock 和 ，在不同的讀寫(xiě)比（比如讀多寫(xiě)少，當(dāng)超時(shí)才更新）時(shí)，這塊就不好判斷哪種實(shí)現(xiàn)更優(yōu)了，有興趣的同學(xué)可以嘗試深挖下（而且 doyenli 也提到， 內(nèi)部是 append only 的）

用過(guò) map 的同學(xué)應(yīng)該會(huì)知道，map 并不是線程安全的。多個(gè)協(xié)程同步更新 map 時(shí)，會(huì)有概率導(dǎo)致程序 core 掉。

那我們?yōu)槭裁床挥?？?dāng)然不是因?yàn)?go 版本太老不支持這種膚淺原因。

里有張對(duì)比數(shù)據(jù)，純寫(xiě) map 是比 要快很多，讀也有一定優(yōu)勢(shì)?？紤]到多數(shù)場(chǎng)景下讀多寫(xiě)少，我們只需對(duì) map 加個(gè)讀寫(xiě)鎖，異步寫(xiě)的問(wèn)題就搞定了（還不損失太多性能）。

map vs

除了讀寫(xiě)鎖，我們還可以使用 shard map 的分布式鎖來(lái)繼續(xù)提高并發(fā)（后面 bigcache 部分會(huì)介紹），所以你看最終的 cache 庫(kù)里，大家都沒(méi)用 ，而是用map+讀寫(xiě)鎖來(lái)實(shí)現(xiàn)存儲(chǔ)。

坑 2: 用 map 做內(nèi)存池就可以了？

并不能。map 存儲(chǔ) keys 也是有限制的，當(dāng) map 中 keys 數(shù)量超過(guò)千萬(wàn)級(jí)，有可能造成性能瓶頸。

這個(gè)是我在之前業(yè)務(wù)中實(shí)際遇到的情況，當(dāng)時(shí)服務(wù)里用了 GroupCache 做緩存，導(dǎo)致部分線上請(qǐng)求會(huì)超時(shí)(0.08%左右的超時(shí)率)。我們先暫時(shí)放下這個(gè)問(wèn)題，弄清原因再來(lái)介紹這里的差異。

找了下資料，發(fā)現(xiàn) 2014 年 Go 有個(gè) issue 提到 Large maps cause significant GC pauses 的問(wèn)題。簡(jiǎn)單來(lái)說(shuō)就是當(dāng) map 中存在大量 keys 時(shí)，GC 掃描 map 產(chǎn)生的停頓將不能忽略。

好消息是 2015 年 Go 開(kāi)發(fā)者已經(jīng)對(duì) map 中無(wú)指針的情況進(jìn)行了優(yōu)化：

GC ignore maps with no pointers

我們參考其中的代碼，寫(xiě)個(gè)GC 測(cè)試程序驗(yàn)證下：

package?main import?( ??"fmt" ??"os" ??"runtime" ??"time" ) //?Results?of?this?program?on?my?machine: // //?for?t?in?1?2?3?4?5;?do?go?run?ma?$t;?done // //?Higher?parallelism?does?help,?to?some?extent: // //?for?t?in?1?2?3?4?5;?do?GOMAXPROCS=8?go?run?ma?$t;?done // //?Output(go?1.14): //?With?map[int32]*int32,?GC?took?456.159324ms //?With?map[int32]int32,?GC?took?10.644116ms //?With?map?shards?([]map[int32]*int32),?GC?took?383.296446ms //?With?map?shards?([]map[int32]int32),?GC?took?1.023655ms //?With?a?plain?slice?([]main.t),?GC?took?172.776μs func?main()?{ ??const?N?=?5e7?//?5000w ??if?len)?!=?2?{ ????("usage:?%s?[1?2?3?4]n(number?selects?the?test)n",?os.Args[0]) ????return ??} ??switch?os.Args[1]?{ ??case?"1": ????//?Big?map?with?a?pointer?in?the?value ????m?:=?make(map[int32]*int32) ????for?i?:=?0;?i?<?N;?i++?{ ??????n?:=?int32(i) ??????m[n]?=?&n ????} ????run() ????("With?%T,?GC?took?%sn",?m,?timeGC()) ????_?=?m[0]?//?Preserve?m?until?here,?hopefully ??case?"2": ????//?Big?map,?no?pointer?in?the?value ????m?:=?make(map[int32]int32) ????for?i?:=?0;?i?<?N;?i++?{ ??????n?:=?int32(i) ??????m[n]?=?n ????} ????run() ????("With?%T,?GC?took?%sn",?m,?timeGC()) ????_?=?m[0] ??case?"3": ????//?Split?the?map?into?100?shards ????shards?:=?make([]map[int32]*int32,?100) ????for?i?:=?range?shards?{ ??????shards[i]?=?make(map[int32]*int32) ????} ????for?i?:=?0;?i?<?N;?i++?{ ??????n?:=?int32(i) ??????shards[i%100][n]?=?&n ????} ????run() ????("With?map?shards?(%T),?GC?took?%sn",?shards,?timeGC()) ????_?=?shards[0][0] ??case?"4": ????//?Split?the?map?into?100?shards ????shards?:=?make([]map[int32]int32,?100) ????for?i?:=?range?shards?{ ??????shards[i]?=?make(map[int32]int32) ????} ????for?i?:=?0;?i?<?N;?i++?{ ??????n?:=?int32(i) ??????shards[i%100][n]?=?n ????} ????run() ????("With?map?shards?(%T),?GC?took?%sn",?shards,?timeGC()) ????_?=?shards[0][0] ??case?"5": ????//?A?slice,?just?for?comparison?to?show?that ????//?merely?holding?onto?millions?of?int32s?is?fine ????//?if?they're?in?a?slice. ????type?t?struct?{ ??????p,?q?int32 ????} ????var?s?[]t ????for?i?:=?0;?i?<?N;?i++?{ ??????n?:=?int32(i) ??????s?=?append(s,?t{n,?n}) ????} ????run() ????("With?a?plain?slice?(%T),?GC?took?%sn",?s,?timeGC()) ????_?=?s[0] ??} } func?timeGC()??{ ??start?:=?() ??run() ??return?(start) }

代碼中一共測(cè)試了 5 種情況，寫(xiě)入5000w的 keys 后，主動(dòng)觸發(fā) 2 次 GC 來(lái)測(cè)量耗時(shí)：

[1]?With?map[int32]*int32,?GC?took?456.159324ms [2]?With?map[int32]int32,?GC?took?10.644116ms [3]?With?map?shards?([]map[int32]*int32),?GC?took?383.296446ms [4]?With?map?shards?([]map[int32]int32),?GC?took?1.023655ms [5]?With?a?plain?slice?([]main.t),?GC?took?172.776μs

可以看到，當(dāng) map 中沒(méi)有指針時(shí)，掃描停頓時(shí)間大約在 10ms 左右，而包含指針int32時(shí)則會(huì)擴(kuò)大 45 倍。

先看 5 的數(shù)據(jù)，單純的 slice 速度飛快，基本沒(méi)有 GC 消耗。而 map shards 就有點(diǎn)耐人尋味了，為什么我們沒(méi)有對(duì) map 加鎖，分 shard 后 GC 時(shí)間還是縮短了呢？說(shuō)好的將鎖分布式化，才能提高性能呢？

坑 3: shards map 能提高性能的元兇(原因)

要了解 shards map 性能變化的原因，需要先弄清楚 Golang GC 的機(jī)制。我們先加上GODEBUG=gctrace=1觀察下 map 里包含指針與沒(méi)有指針的 gc 差異：

map[]*int: gc 11 @11.688s 2%: 0.004+436+0.004 ms clock, 0.055+0/1306/3899+0.049 ms cpu, 1762->1762->1220 MB, 3195 MB goal, 12 P (forced)map[]int: gc 10 @9.357s 0%: 0.003+14+0.004 ms clock, 0.046+0/14/13+0.054 ms cpu, 1183->1183->746 MB, 2147 MB goal, 12 P (forced)

輸出各字段含義可以看GODEBUG 之 gctrace 干貨解析，這里我們只關(guān)注 cpu 里 0.055+0/1306/3899+0.049 ms cpu 這段的解釋?zhuān)?/p>

• Mark Prepare (STW) - 0.055 表示整個(gè)進(jìn)程在 mark 階段 STW 停頓時(shí)間
• Marking - 0/1306/3899 三段信息，其中 0 是 mutator assist 占用時(shí)間，1306 是 dedicated mark workers+fractional mark worker 占用的時(shí)間，3899 是 idle mark workers 占用的時(shí)間（雖然被拆分為 3 種不同的 gc worker，過(guò)程中被掃描的 P 還是會(huì)暫停的，另外注意這里時(shí)間是所有 P 消耗時(shí)間的總和）
• Mark Termination (STW) - 0.049 表示整個(gè)進(jìn)程在 markTermination 階段 STW 停頓時(shí)間

只有 Mark 的前后兩個(gè)階段會(huì)導(dǎo)致 Stop-The-World(STW)，中間 Marking 過(guò)程是并行的。這里 1306ms 是因?yàn)槲覀儐?dòng)了 12 個(gè) P，1306ms 和 3899ms 是所有 P 消耗時(shí)間的綜合。雖然說(shuō)是 Marking 是并行，但被掃描到的 P 還是會(huì)被暫停的。因此這個(gè)時(shí)間最終反映到業(yè)務(wù)程序上，就是某個(gè) P 處理的請(qǐng)求，在 GC 時(shí)耗時(shí)突增（不穩(wěn)定），不能被簡(jiǎn)單的忽略

那回到上面的問(wèn)題了，shards map 的性能又是如何得到提升（近 10 倍）的？

//?With?map[int32]int32,?GC?took?11.285541ms gc?1?@0.001s?7%:?0.010+2.1+0.012?ms?clock,?0.12+0.99?ms?cpu,?4->6->6?MB,?5?MB?goal,?12?P ... gc?8?@2.374s?0%:?0.003+3.9+0.018?ms?clock,?0.042+0.31?ms?cpu,?649->649->537?MB,?650?MB?goal,?12?P gc?9?@4.834s?0%:?0.003+7.5+0.021?ms?clock,?0.040+0/14?ms?cpu,?1298->1298->1073?MB,?1299?MB?goal,?12?P gc?10?@9.188s?0%:?0.003+26+0.004?ms?clock,?0.045+0/26?ms?cpu,?1183->1183->746?MB,?2147?MB?goal,?12?P?(forced) gc?11?@9.221s?0%:?0.018+9.4+0.003?ms?clock,?0.22+0/17?ms?cpu,?746->746->746?MB,?1492?MB?goal,?12?P?(forced) //?With?map?shards?([]map[int32]int32),?GC?took?1.017494ms gc?1?@0.001s?7%:?0.010+2.9+0.048?ms?clock,?0.12+0.26?ms?cpu,?4->7->6?MB,?5?MB?goal,?12?P ... gc?12?@3.924s?0%:?0.003+3.2+0.004?ms?clock,?0.040+1.2?ms?cpu,?822->827->658?MB,?840?MB?goal,?12?P gc?13?@8.096s?0%:?0.003+6.1+0.004?ms?clock,?0.044+6.0/14/32+0.053?ms?cpu,?1290->1290->945?MB,?1317?MB?goal,?12?P gc?14?@11.619s?0%:?0.003+1.2+0.004?ms?clock,?0.045+0?ms?cpu,?1684->1684->1064?MB,?1891?MB?goal,?12?P?(forced) gc?15?@11.628s?0%:?0.003+0.91+0.004?ms?clock,?0.038+0?ms?cpu,?1064->1064->1064?MB,?2128?MB?goal,?12?P?(forced)

從倒數(shù)第三輪內(nèi)存最大的時(shí)候看，GC worker 的耗時(shí)都是接近的；唯一差異較大的，是 markTermination 階段的 STW 時(shí)間，shard 方式下少了 1/10，因此推測(cè)和該階段得到優(yōu)化有關(guān)。

至于這個(gè)時(shí)間為什么能減少，我也不清楚為什么（這個(gè)坑挖得太深，只能以后找到資料再來(lái)填...)

2. GroupCache

言歸正傳（眾人：什么？！前面寫(xiě)這么多你還沒(méi)進(jìn)入正文。我：咳..咳..），我們總結(jié)下用 map 實(shí)現(xiàn)內(nèi)存池的要點(diǎn)：

內(nèi)存池用 map 不用 ；map 要加讀寫(xiě)鎖map 盡量存非指針(key 和 value 都不包含指針)map 里存放指針，需要注意 keys 過(guò)多會(huì)帶來(lái)的 GC 停頓問(wèn)題使用 shards map

然后我們看看GroupCache 的實(shí)現(xiàn)方法，這個(gè)定義在 lru 里：

//?Cache?is?an?LRU?cache.?It?is?not?safe?for?concurrent?access. type?Cache?struct?{ ??cache?map[interface{}]*li }

從 cache 的定義可以看出，這是我們說(shuō)的 map 里包含指針的情況，而且還是不分 shards 的。所以如果你單機(jī) GroupCache 里 keys 過(guò)多，還是要注意下用法的。

注：截止目前 1.14，map 里包含指針時(shí) idle worker 耗時(shí)問(wèn)題還未有結(jié)論，有興趣可以參考 10ms-26ms latency from GC in go1.14rc1, possibly due to 'GC (idle)' work 里面的例子和現(xiàn)象。

3. BigCache

相比分布式場(chǎng)景的 GroupCache，如果你本地依然有千萬(wàn)級(jí)的 keys，那推薦你用 bigcache。無(wú)數(shù)經(jīng)驗(yàn)證明，超大 map 的內(nèi)存池導(dǎo)致的 GC 延遲，是可以通過(guò)切 bigcache 解決的。那 bigcache 到底怎么做到的？

簡(jiǎn)單來(lái)說(shuō)：shards map + map[uint]uint + []byte + free link = BigCache

1. 定義 shards cache，避免鎖粒度過(guò)大
2. map 里只存放 uint 避免指針
3. 實(shí)現(xiàn)一個(gè) queue 結(jié)構(gòu)（實(shí)際是[]byte，通過(guò) uint 下標(biāo)追加分配）
4. 采用 free 鏈機(jī)制，刪除保留空洞最后一起回收（這塊邏輯還蠻復(fù)雜的，先留個(gè)不大不小的坑吧...）

其內(nèi)存池定義如下：

type?cacheShard?struct?{ ??hashmap?????map[uint64]uint32????????//?key在entries中的位置 ??entries?????queue.BytesQueue?????????//?實(shí)際是[]byte，新數(shù)據(jù)來(lái)了后copy到尾部 }

這樣 GC 就變成了map 無(wú)指針+[]byte 結(jié)構(gòu)的掃描問(wèn)題了，因此性能會(huì)高出很多。

坑 4: 兩種方式(GroupCache 和 BigCache)對(duì)具體業(yè)務(wù)到底有多大影響？

上面只是 map 實(shí)現(xiàn)內(nèi)存池的模擬分析，以及兩種典型 Cache 庫(kù)的對(duì)比。如果你也和我一樣，問(wèn)自己“具體兩種 Cache 對(duì)業(yè)務(wù)有多大影響呢”？那只能很高興的對(duì)你說(shuō)：歡迎來(lái)到坑底 -_-

我們線上大概需要單機(jī)緩存 1000 萬(wàn)左右的 keys。首先我嘗試模擬業(yè)務(wù)，向兩種 Cache 中插入 1000w 數(shù)據(jù)來(lái)測(cè)試 GC 停頓。然而因?yàn)閷?shí)驗(yàn)代碼或其他未知的坑，最后認(rèn)為這個(gè)方法不太可側(cè)

最后討論，覺(jué)得還是用老辦法，用 Prometheus 的 histogram 統(tǒng)計(jì)耗時(shí)分布。我們先統(tǒng)計(jì)底層存儲(chǔ)（redis）的耗時(shí)分布，然后再分別統(tǒng)計(jì) BigCache 和 GroupCache 在寫(xiě)入 500w 數(shù)據(jù)后的實(shí)際情況。分析結(jié)論可知：

40ms 以上請(qǐng)求

從 redis 數(shù)據(jù)看，40ms 以上請(qǐng)求占比0.08%；BigCache 的 40ms 以上請(qǐng)求占0.04%（即相反有一半以上超時(shí)請(qǐng)求被 Cache 擋住了） GroupCache 則是0.2%，將這種長(zhǎng)時(shí)間請(qǐng)求放大了1倍多（推測(cè)和 map 的鎖機(jī)制有關(guān)）

10ms-40ms 請(qǐng)求

redis 本身這個(gè)區(qū)間段請(qǐng)求占比24.11%；BigCache 則只有15.51%，相當(dāng)于擋掉了33%左右的高延遲請(qǐng)求（證明加熱點(diǎn) Cache 還是有作用的） GroupCache 這個(gè)區(qū)間段請(qǐng)求占比21.55%，也比直接用 redis 來(lái)得好

詳細(xì)數(shù)據(jù)分布：

redis?????[??0.1]?0.00% redis?????[??0.5]?0.38% redis?????[????1]?3.48% redis?????[????5]?71.94% redis?????[???10]?22.90% redis?????[???20]?1.21% redis?????[???40]?0.07% redis?????[?+Inf]?0.01% bigcache??[??0.1]?0.40% bigcache??[??0.5]?16.16% bigcache??[????1]?14.82% bigcache??[????5]?53.07% bigcache??[???10]?14.85% bigcache??[???20]?0.66% bigcache??[???40]?0.03% bigcache??[?+Inf]?0.01% groupcache[??0.1]?0.24% groupcache[??0.5]?9.59% groupcache[????1]?9.69% groupcache[????5]?58.74% groupcache[???10]?19.10% groupcache[???20]?2.45% groupcache[???40]?0.17% groupcache[?+Inf]?0.03%

然而我們測(cè)完只能大致知道：本地使用 GroupCache 在 500w 量級(jí)的 keys 下，還是不如 BigCache 穩(wěn)定的（哪怕 GroupCache 實(shí)現(xiàn)了 LRU 淘汰，但實(shí)際上因?yàn)橛?Hot/Main Cache 的存在，內(nèi)存利用效率上不如 BigCache）

分布式情況下，GroupCache 和 BigCache 相比又有多少差距，這個(gè)就只能挖坑等大家一起跳了。

4. 對(duì)象池與零拷貝

在實(shí)際業(yè)務(wù)中，往往 map 中并不會(huì)存儲(chǔ) 5000w 級(jí)的 keys。如果我們只有 50w 的 keys，GC 停頓就會(huì)驟減到 4ms 左右（其間 gc worker 還會(huì)并行工作，避免 STW）。

例如無(wú)極（騰訊內(nèi)部的一個(gè)配置服務(wù)）這類(lèi)配置服務(wù)（或其他高頻數(shù)據(jù)查詢場(chǎng)景），往往需要 Get(key) 獲取對(duì)應(yīng)的結(jié)構(gòu)化數(shù)據(jù)。而從 BigCache，CPU 消耗發(fā)現(xiàn)（如圖），相比網(wǎng)絡(luò) IO 和 Protobuf 解析，Get 占用0.78%、Set 占用0.9%，基本可以忽略：

CPU profile

因此優(yōu)化的思路也很明確，我們參考 GroupCache 的 lru 實(shí)現(xiàn)，將 JSON 提前解析好，在業(yè)務(wù)側(cè) Get 時(shí)直接返回 struct 的指針即可。具體流程不復(fù)雜，直接 ppt 截圖：

zero-copy

我們把接口設(shè)計(jì)成注冊(cè)的方式（注冊(cè)需要解析 JSON 數(shù)據(jù)的結(jié)構(gòu)），然后再 Get 時(shí)返回該結(jié)構(gòu)的指針實(shí)現(xiàn)零拷貝。下面 benchmark 可以反映性能差異和內(nèi)存分配情況（Client_Get 是實(shí)時(shí) JSON 解析，F(xiàn)ilter_Get 是優(yōu)化的對(duì)象池 API），可以切實(shí)看到0 allocs/op：

goos:?linux goarch:?amd64 pkg:?open-wuji/go-sdk/wujiclient BenchmarkClient_Get-8??????????????1000000????????1154?ns/op???????????1.00?hits????????87?B/op????????3?allocs/op BenchmarkFilter_Get-8??????????????4899364?????????302?ns/op???????????1.00?hits?????????7?B/op????????1?allocs/op BenchmarkClient_GetParallel-8??????8383149?????????162?ns/op???????????1.00?hits????????80?B/op????????2?allocs/op BenchmarkFilter_GetParallel-8?????13053680????????91.4?ns/op???????????1.00?hits?????????0?B/op????????0?allocs/op PASS ok????open-wuji/go-sdk/wujiclient?93.494s Success:?Benchmarks?passed.

目前無(wú)極尚未對(duì)外開(kāi)源。對(duì)具體實(shí)現(xiàn)感興趣的同學(xué)，可以看 gist 中filter API 的實(shí)現(xiàn)代碼

完整分享 PPT 可在后臺(tái)回復(fù) txgo 獲取

---

喜歡本文的朋友，歡迎關(guān)注“Go語(yǔ)言中文網(wǎng)”