Ristretto 簡介：一個高性能 GO 緩存

這個博客登上了 Golang subreddit[1] 的頂部，並且在 Hacker News[2] 的 trending 上排在前十位。一定要在那裏參與討論，並通過給我們一個 star[3]，表達對我們的喜歡。

經過六個月的研發，我們自豪地宣佈緩存 Ristretto[4]：一個高性能、併發、可設置內存上限的 Go 緩存的初始版本。他是抗爭用、擴展性好、提供穩定的高命中率。

前言

這一切都始於 Dgraph[5] 中需要一個可設置內存上限的、併發的 Go 緩存。

我們四處尋找解決方案，但是沒有找到一個合適的。然後我們嘗試使用分片 map，通過分片驅逐來釋放內存，這導致了我們的內存問題。

之後我們重新利用了 Groupcache 的 LRU[6], 用互斥鎖保證線程安全。

使用了一年之後，我們注意到緩存存在嚴重的爭用問題。一個 commit[7] 刪除了該緩存，使我們的查詢延遲顯著改善了 5-10 倍。

本質上，我們的緩存正在減慢我們的速度!

我們得出的結論是，Go 中的併發緩存庫已經壞了，必須修復。

在三月, 我們寫了一篇關於 Go 中的緩存狀態 [8], 提到數據庫和系統需要一個智能的、可設置內存上限的緩存的問題，它可以擴展到 Go 程序所處的多線程環境。

我們將這些設置爲緩存的要求：

1. 併發的；

2. 緩存命中率高；

3. Memory-bounded (限制爲可配置的最大內存使用量)；

4. 隨着核數和協程數量的增加而擴展；

5. 在非隨機 key 訪問 (例如 Zipf) 分佈下很好的擴展；

發佈了博客文章 [9] 之後，我們組建了一個團隊來解決其中提到的挑戰，並創建了一個值得與非 Go 語言緩存實現進行比較的 Go 緩存庫。

Caffeine[10] 是一個基於 Java 8 的高性能、近乎最優的緩存庫。許多基於 Java 8 的數據庫都在使用它, 比如 Cassandra，HBase，和 Neo4j。這裏 [11] 有一篇關於 Caffeine 設計的文章。

Ristretto: Better Half of Espresso

從那以後我們閱讀了文獻 [12]， 廣泛測試了實現 ，並討論了在寫一個緩存庫時需要考慮的每一個變量。

今天，我們自豪地宣佈它已經準備好供更廣泛的 Go 社區使用和實驗。

在我們開始講解 Ristretto[4] 的設計之前, 這有一個代碼片段展示瞭如何使用它：

func main() {
cache, err := ristretto.NewCache(&ristretto.Config{
NumCounters: 1e7,     // key 跟蹤頻率爲（10M）
MaxCost:     1 << 30, // 緩存的最大成本 (1GB)。
BufferItems: 64,      // 每個 Get buffer的 key 數。
})
if err != nil {
panic(err)
}

cache.Set("key", "value", 1) // set a value
// 等待值通過 buffer
time.Sleep(10 * time.Millisecond)

value, found := cache.Get("key")
if !found {
panic("missing value")
}
fmt.Println(value)
cache.Del("key")
}

指導原則

Ristretto[4] 建立在三個指導原則之上：

1. 快速訪問；

2. 高併發和抗爭用；

3. 可設置內存上限；

在這篇博文中，我們將討論這三個原則以及如何在 Ristretto 中實現它們。

快速訪問

儘管我們喜歡 Go 和它對功能的固執己見，但一些 Go 的設計決策阻止我們榨取我們想要的所有性能。

最值得注意的是 Go 的併發模型。由於對 CSP 的關注，大多數其他形式的原子操作被忽略了。這使得難以實現在緩存庫中有用的無鎖結構。例如, Go 不提供 thread-local 存儲 [13]。

緩存的核心是一個 hash map 和關於進入和出去的規則。如果 hash map 表現不佳，那麼整個緩存將受到影響。

與 Java 不同, Go 沒有無鎖的併發 hashmap。相反，Go 的線程安全是必須通過顯式獲取互斥鎖來達到。

我們嘗試了多種實現方式（使用 Ristretto 中的store接口），發現sync.Map在讀取密集型工作負載方面表現良好，但在寫入工作負載方面表現不佳。

考慮沒有 thread-local 存儲，我們發現使用分片的互斥鎖包裝的 Go map 具有最佳的整體性能。 特別是，我們選擇使用 256 個分片，以確保即使在 64 核服務器上也能表現良好。

使用基於分片的方法，我們還需要找到一種快速方法來計算 key 應該進入哪個分片。這個要求和對 key 太長消耗太多內存的擔憂，導致我們對 key 使用 uint64，而不是存儲整個 key。理由是我們需要在多個地方使用 key 的哈希值，並且在入口處執行一次允許我們重用該哈希值，避免任何更多的計算。

爲了生成快速 hash，我們從 Go Runtime 借用了 runtime.memhash[14]。該函數使用匯編代碼快速生成哈希。

請注意，這個 hash 有一個隨機化器，每當進程啓動時都會初始化，這意味着相同的 key 不會在下一次進程運行時生成相同的哈希。但是，這對於非持久緩存來說沒問題。在我們的實驗 [15] 發現它可以在 10ns 內散列 64 字節的 key。

BenchmarkMemHash-32 200000000 8.88 ns/op
BenchmarkFarm-32    100000000 17.9 ns/op
BenchmarkSip-32      30000000 41.1 ns/op
BenchmarkFnv-32      20000000 70.6 ns/op

然後，我們不僅將此 hash 用作被存儲的 key，而且還用於確定 key 應該進入的分片。這個確實引入了 key 衝突的機會，這是我們計劃稍後處理的事情。

併發和抗爭用

實現高命中率需要管理有關緩存中，存在的內容以及緩存中應該存在的內容的元數據。當跨 goroutine 平衡緩存的性能和可擴展性時，這變得非常困難。

幸運的是，有一篇名爲 BP-Wrapper 的論文 [16] 寫了一個系統框架，可以使任何替換算法幾乎無鎖爭用。

本文介紹了兩種緩解爭用的方法：預取和批處理。我們只使用批處理。

批處理的工作方式與您想象的差不多。我們不是爲每個元數據變化獲取互斥鎖，而是等待 ring buffer 填滿，然後再獲取互斥鎖並處理變化。如論文中所述，這大大降低了爭用，而且開銷很小。

我們將此方法用於緩存的所有 Gets 和 Sets。

Gets

當然，所有對緩存的 Get 操作都會立即得到服務。困難的部分是捕獲 Get，因此我們可以跟蹤 key 訪問。在 LRU 緩存中，通常將 key 放在鏈表的頭部。在我們基於 LFU 的緩存中，我們需要增加一個 item 的命中計數器。這兩個操作都需要對緩存全局結構進行線程安全訪問。BP-Wrapper[16] 建議使用批處理來處理命中計數器增量，但問題是我們如何在不獲取另一個鎖的情況下實現此批處理過程。

這聽起來像是 Go chan 的完美用例，事實確實如此。不幸的是，chan 的吞吐量性能阻止了我們使用它們。相反，我們設計了一種巧妙的方法使用 sync.Pool 來實現條帶化的有損 ring buffers[17]，這些緩衝區具有出色的性能並且幾乎沒有數據丟失。

存儲在 pool 中的任何 item 都可能隨時自動刪除，不另行 [18] 通知。這引入了一個級別的有損行爲。 Pool 中的每個 item 實際上都是一批 key。當批次填滿時，它會被推送到一個 chan。chan 大小故意保持較小，以避免消耗太多 CPU 週期來處理它。如果 chan 已滿，則丟棄該批次。這引入了二級有損行爲。 一個 goroutine 從內部 chan 中獲取這批數據並處理這些 key，更新它們的命中計數器。

AddToLossyBuffer(key):
  stripe := b.pool.Get().(*ringStripe)
  stripe.Push(key)
  b.pool.Put(stripe)

一旦 buffer 填滿，push 到 chan:
  select {
  case p.itemsCh <- keys:
      p.stats.Add(keepGets, keys[0], uint64(len(keys)))
      return true
  default:
      p.stats.Add(dropGets, keys[0], uint64(len(keys)))
      return false
  }

p.itemCh processing:
  func (p *tinyLFU) Push(keys []uint64) {
    for _, key := range keys {
      p.Increment(key)
    }
  }

使用 sync.Pool 比其他任何東西（slice、攜帶互斥鎖等）的性能都好，主要是由於 thread-local 存儲的內部使用，這是 Go 用戶無法從公共 API 獲得的東西。

Sets

Set buffer 的要求與 Get 略有不同。

在 Gets 中，我們緩衝 key，只有在 buffer 填滿後才處理它們。在 Sets 中，我們希望儘快處理 key。

因此，我們使用一個 chan 來捕獲 Set，如果 chan 已滿則將它們丟掉以避免爭用。幾個後臺 goroutine 從 chan 中挑選 set 並處理 set。

與 Gets 一樣，此方法旨在優化抗爭用性。但是，有一些注意事項，如下所述。

select {
case c.setBuf <- &item{key: hash, val: val, cost: cost}:
    return true
default:
    // 丟棄 set 操作並避免阻塞
    c.stats.Add(dropSets, hash, 1)
    return false
}

注意事項

Ristretto[4] 中的 Set 進入 buffer 排隊，控制權返回給調用者，然後將 buffer 應用於緩存。這有兩個副作用：

1. 無法保證會應用 Set 操作 它可以立即刪除以避免爭用，也可以稍後被策略拒絕。

2. 即使應用了 Set，在調用返回給用戶後也可能需要幾毫秒。用數據庫術語來說，它是一個 最終的一致性 模型。

但是，如果緩存中已存在密鑰，則 Set 將立即更新該密鑰。這是爲了避免緩存的 key 保存過時的值。

抗爭用

Ristretto 針對抗爭用進行了優化。這在高併發負載下表現非常好，正如我們將在下面的吞吐量基準測試中看到的那樣。但是，它會丟失一些元數據以換取更好的吞吐量性能。

有趣的是，由於密鑰訪問分佈的性質，信息丟失不會影響我們的命中率性能。如果我們確實丟失了元數據，它通常會均勻丟失，而密鑰訪問分佈仍然是不均勻的。因此，我們仍然實現了高命中率，並且命中率下降很小，如下圖所示。

可設置內存上限

Key 成本

無限大的緩存實際上是不可能的。 緩存的大小必須有界。許多緩存庫會將緩存大小視爲元素的數量。我們發現這種方法 很幼稚。當然，它適用於值大小相同的工作負載。

然而，大多數工作負載具有可變大小的值。一個值可能需要幾個字節，另一個可能需要幾千字節，還有一個需要幾兆字節。將它們視爲具有相同的內存成本是不現實的。

在 Ristretto[4] 中, 我們將成本附加到每個 key-value 用戶可以在調用 Set 時指定該成本是多少。我們將此成本計入緩存的 MaxCost。當緩存滿負荷運行時，一個 重 的 item 可能會取代許多 輕 的 item。這種機制很好，因爲它適用於所有不同的工作負載，包括每個 key-value 成本爲 1 的樸素方法。

通過 TinyLFU 的准入策略

” 我們應該讓什麼進入緩存？“

顯然，我們的目標是讓比當前 item 更 “有價值” 的新 item 進入。但是，如果您考慮跟蹤相關 item 的與 “價值” 問題有關的信息所需的開銷（延遲和內存），這將成爲一個挑戰。

儘管這是一個有據可查的提高命中率的策略，但大多數 Go 緩存庫根本沒有準入策略。事實上，許多 LRU 驅逐實現都假定最新的密鑰是最有價值的。

此外，大多數 Go 緩存庫使用純 LRU 或 LRU 的近似值作爲它們的驅逐策略。儘管 LRU 近似的質量很高，但某些工作負載更適合 LFU 逐出策略。我們在使用各種跟蹤的基準測試中發現了這種情況。

對於我們的准入政策，我們看了一篇引人入勝的新論文名爲 TinyLFU[19]: 一個高效的緩存准入策略 在非常高的層次上，TinyLFU 提供了三種方法：

• Increment(key uint64)

• Estimate(key uint64) int (referred as ɛ)

• Reset

該論文 [20] 對其進行了最好的解釋，但 TinyLFU 是一種與逐出無關的准入策略，旨在以極少的內存開銷提高命中率。主要思想是隻有當新 item 的估計值高於被驅逐 item 的估計值時，才允許新 item 進入。我們使用 Count-Min[21] 在 Ristretto[4] 中實現了 TinyLFU。它使用 4 位計數器來估算 item (ɛ) 的訪問頻率。每個 key 的這種小成本，使我們能夠跟蹤比使用普通的頻率 map，更大的全局 key 空間裏的樣本。

TinyLFU 還通過重置功能維護 key 訪問的新近度。每 N 個 key 遞增後，計數器減半。因此，一個很久沒有出現的 key，其計數器將被重置爲零；爲最近出現的 key 鋪平道路。

通過採樣 LFU 的驅逐策略

當緩存達到容量時，每個傳入的 key 都應替換緩存中存在的一個或多個 key。不僅如此，傳入 key 的 ε 應該高於被驅逐 key 的 ε。爲了找到一個 ε 低的 key，我們使用 Go map 迭代提供的自然隨機性 [22] 來選擇 key 樣本並循環，在它們之上找到具有最低ε的 key。

然後我們將這個 key 的 ɛ 與傳入的 key 進行比較。如果傳入的 key 具有更高的 ε，則該 key 將被逐出（驅逐策略）。否則，傳入的 key 將被拒絕（准入策略）。重複此機制，直到傳入 key 的成本可以放入緩存中。因此，一個傳入的 key 可能取代一個以上的 key。注意，傳入 key 的成本在選擇驅逐 key 時不起作用。

使用這種方法，在各種工作負載下，命中率與精確 LFU 策略的誤差在 1% 以內。 這意味着我們在同一個包中獲得了准入策略、保守內存使用和較低爭用的好處。

// 准入和驅逐算法的片段
incHits := p.admit.Estimate(key)
for ; room < 0; room = p.evict.roomLeft(cost) {
    sample = p.evict.fillSample(sample)
    minKey, minHits, minId := uint64(0), int64(math.MaxInt64), 0
    for i, pair := range sample {
        if hits := p.admit.Estimate(pair.key); hits < minHits {
            minKey, minHits, minId = pair.key, hits, i
        }
    }
    if incHits < minHits {
        p.stats.Add(rejectSets, key, 1)
        return victims, false
    }
    p.evict.del(minKey)
    sample[minId] = sample[len(sample)-1]
    sample = sample[:len(sample)-1]
    victims = append(victims, minKey)
}

DoorKeeper

在我們將新 key 放入 TinyLFU 之前，Ristretto[4] 使用布隆過濾器首先檢查該 key 是否曾被見過。只有當該 key 已經存在於布隆過濾器中時，它纔會被插入到 TinyLFU 中。這是爲了避免 TinyLFU 被那些不被多次看到的長尾 key 所 污染。

在計算一個 key 的 ε 時，如果 item 包含在 bloom filter 中，它的頻率估計就是 TinyLFU 的 Estimate 加一。在 TinyLFU重置期間，布隆過濾器也被清除。

Metrics

雖然是可選的，但瞭解緩存的行爲方式是很重要的。我們希望確保跟蹤與緩存相關的指標不僅是可能的，而且這樣做的開銷足夠低，可以打開並保持。

除了命中和未命中，Ristretto 還追蹤一些指標，如添加、更新和逐出的 key 及其成本，set 操作被丟棄或拒絕，以及 get 操作丟棄或保留的次數。所有這些數字有助於瞭解各種工作負載下的緩存行爲，並且爲了進一步優化鋪平道路。

我們最初爲這些使用原子計數器。然而，開銷是巨大的。我們把原因縮小到 False Sharing[23]。考慮多核系統，其中不同的原子計數器 (每個 8 字節) 位於統一 cache line（通常爲 64 字節）。任何更新改變計數器，都會導致其他計數器被標記 無效。這會強制爲持有該緩存的所有其他核心重新加載緩存，從而在 cache line 上產生寫入爭用。

爲了實現可擴展性，我們確保每個原子計數器完全佔據一個完整的 cache line。所以，每個核在不同的 cache line 上工作。Ristretto 通過爲每個 metric 分配 256 個 uint64 來使用它，在每個活動的 uint64 之間留下 9 個未使用的 uint 64。爲了避免額外的計算，重用 key hash 值去決定要增加哪個 uint64。

Add:
valp := p.all[t]
// 通過在兩個將遞增的原子計數器之間填充至少 64 字節的空間來避免 false sharing。
idx := (hash % 25) * 10
atomic.AddUint64(valp[idx], delta)

Read:
valp := p.all[t]
var total uint64
for i := range valp {
total += atomic.LoadUint64(valp[i])
}
return total

讀取指標時，會讀取全部的 uint64 並求和，以獲取最新的數字。使用這種方法，metrics 跟蹤只對緩存性能添加 10% 左右的開銷。

Benchmarks

現在你瞭解了 Ristretto[4] 中存在的各種各樣的機制，讓我們看看與其他流行的 Go 緩存相比的命中率和吞吐量 benchmark。

命中率

命中率是使用 Damian Gryski 的 cachetest[24] 和我們自己的 benchmarking 套件 [25] 測量的. 兩個程序的命中率數字相同，但我們添加了讀取某些 trace 格式 (特別是 LIRS and ARC) 以及 CSV 輸出的功能，以便於繪製圖表。如果你想編寫自己的 benchmark 或者添加一種 trace 格式，請查看 sim[26] 包。

爲了更好地瞭解改進空間，我們添加了一個理論上最佳的 [27] 緩存實現, 它使用未來的知識來驅逐在其的整個生命週期內命中次數最少的. 注意這是一個能預見未來的 LFU 驅逐策略，其他能預見未來的策略可能用 LRU。根據工作負載，LFU 或 LRU 可能更適合，但我們發現能預見未來的 LFU 對於與 Ristretto[4] 的 Sampled LFU 進行比較很有用。

查找

這個 trace 被描述爲 “由大型商業搜索引擎發起的磁盤讀取訪問，以響應各種網絡搜索請求”

數據庫

這個 trace 被描述爲 “在一個商業數據庫上，一個商業網站正運行一個 ERP 應用，一個數據庫服務運行在上面 “

循環

這個 trace 演示了循環訪問模式。我們不能在此和後續的 benchmark 中包括 Fastcache、Freecache 或 Bigcache 實現，因爲它們具有會影響結果的最低容量要求。一些跟蹤文件很小並且需要小容量來進行性能測量。

CODASYL

這個 trace 被描述爲” 在一小時內引用 CODASYL 數據庫。“ 請注意與這裏的其他庫相比 Ristretto[4] 的性能受到影響。這是因爲 LFU 逐出策略不適合此工作負載。

吞吐量

吞吐量是使用與上一篇 [28] 博文相同程序 [29] 測量的，該程序會生成大量 key，並根據設置的工作負載在 Get 和 Set 的 goroutine 之間交替。

所有吞吐量基準測試均在具有 16gb RAM 的英特爾酷睿 i7-8700K (3.7GHz) 上運行。

混合: 25% Writes, 75% Reads

讀取: 100% Reads

寫入: 100% Writes

未來的改進

正如您可能已經在 CODASYL benchmark 中注意到的那樣，Ristretto[4] 的性能在 LRU 繁重的工作負載中受到影響. 然而，對於大多數工作負載，我們的 Sampled LFU 策略表現相當好。這個問題就變成了 “我們怎麼能兩全其美”

在一篇名爲 Adaptive Software Cache Management 的論文 [30] , 探討了這個確切的問題. 這個基本思想是在主緩存片段之前放置一個 LRU 窗口，並且使用爬山（hill-climbing）技術自適應地調整該窗口的大小以最大化命中率。Caffeine 已經通過這個 [31] 看到了重大 [32] 的結果。我們相信 Ristretto 將來也能從中收益。

特別感謝

我們誠摯的感謝 Ben Manes[33]。他的知識深度和專注,、無私的分享是我們取得任何進步的重要隱私，我們很榮幸能與他就緩存的所有方面進行對話。沒有他的指導、支持和我們內部 Slack 頻道 99.9% [34] 的可用性，Ristretto 是不可能的。

我們還要感謝 Damian Gryski[35] 在對 Ristretto 進行基準測試和編寫參考 TinyLFU[19] 實現方面提供的幫助。

結論

我們的目標是讓緩存庫與 Caffeine 競爭。雖然沒有完全實現, 但我們確實通過使用其他人可以學習的一些新技術，創造了比目前 Go 世界中大多數其他人更好 [36] 的東西。在 Dgraph 中使用此緩存的一些初步實驗看起來很有希望。並且我們希望將 Ristretto[4] 整合到 Dgraph[5] 和 Badger[37] 在接下來的幾個月裏一定要查看它 [38]，也許可以使用 Ristretto 來加快您的工作負載。

相關鏈接：

[1]https://www.reddit.com/r/golang/comments/d6taoq/introducing_ristretto_a_highperformance_go_cache/

[2]https://news.ycombinator.com/item?id=21023949

[3]https://github.com/dgraph-io/dgraph

[4]https://github.com/dgraph-io/ristretto

[5]https://github.com/dgraph-io/dgraph

[6]https://github.com/golang/groupcache/blob/master/lru/lru.go

[7]https://github.com/dgraph-io/dgraph/commit/b9990f4619b64615c2c18bb7627d198b4397109c

[8]https://blog.dgraph.io/post/caching-in-go/

[9]https://blog.dgraph.io/post/caching-in-go/

[10]https://github.com/ben-manes/caffeine

[11]http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html

[12]https://dgraph.io/blog/refs/bp_wrapper.pdf

[13]https://groups.google.com/d/msg/golang-nuts/M9kF6Tdh2Vo/3tLSFYYOGgAJ

[14]https://github.com/dgraph-io/ristretto/blob/master/z/rtutil.go#L42-L44

[15]https://github.com/dgraph-io/ristretto/blob/master/z/rtutil_test.go#L11-L44

[16]https://dgraph.io/blog/refs/bp_wrapper.pdf

[17]https://github.com/dgraph-io/ristretto/blob/master/ring.go#L99-L104

[18]https://golang.org/pkg/sync/#Pool

[19]https://dgraph.io/blog/refs/TinyLFU%20-%20A%20Highly%20Efficient%20Cache%20Admission%20Policy.pdf

[20]https://dgraph.io/blog/refs/TinyLFU%20-%20A%20Highly%20Efficient%20Cache%20Admission%20Policy.pdf

[21]https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

[22]https://blog.golang.org/go-maps-in-action

[23]https://dzone.com/articles/false-sharing

[24]https://github.com/dgraph-io/benchmarks/blob/master/cachebench/cache_bench_test.go

[25]https://github.com/dgraph-io/benchmarks/tree/master/cachebench

[26]https://github.com/dgraph-io/ristretto/tree/master/sim

[27]https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm

[28]https://blog.dgraph.io/post/caching-in-go/

[29]https://github.com/dgraph-io/benchmarks/blob/master/cachebench/cache_bench_test.go

[30]https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Management.pdf

[31]https://github.com/ben-manes/caffeine/wiki/Design#adaptivity

[32]https://github.com/ben-manes/caffeine/wiki/Efficiency#adaptivity

[33]https://github.com/ben-manes

[34]https://en.wikipedia.org/wiki/High_availability#%22Nines%22

[35]https://twitter.com/dgryski

[36]https://en.wikipedia.org/wiki/Ristretto

[37]https://github.com/dgraph-io/badger

[38]https://github.com/dgraph-io/ristretto

原文地址：

Introducing Ristretto: A High-Performance Go Cache

原文作者：

Dmitry Filimonov

**本文永久鏈接：**https://github.com/gocn/translator/blob/master/2023/w05_Introducing%20Ristretto%20A%20High-Performance%20Go%20Cache%20-%20Dgraph%20Blog.md

譯者：784909593

校對：b8kings0ga

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Tn9-aUc72ltMatSGGMGT6w