用 Go 實現一個 LRU cache

• 2021 年 12 月 20 日
• 筆記
• golang, gRPC, LRU

前言

早在幾年前寫過關於 LRU cache 的文章：
//crossoverjie.top/2018/04/07/algorithm/LRU-cache/

當時是用 Java 實現的，最近我在完善 ptg 時正好需要一個最近最少使用的數據結構來存儲歷史記錄。

ptg: Performance testing tool (Go), 用 Go 實現的 gRPC 客戶端調試工具。

Go 官方庫中並沒有相關的實現，考慮到程式的簡潔就不打算依賴第三方庫，自己寫一個；本身複雜度也不高，沒有幾行程式碼。

配合這個數據結構，我便在 ptg 中實現了請求歷史記錄的功能：

將每次的請求記錄存儲到 lru cache 中，最近使用到的歷史記錄排在靠前，同時也能提供相關的搜索功能；具體可見下圖。

實現

實現原理沒什麼好說的，和 Java 的一樣：

• 一個雙向鏈表存儲數據的順序
• 一個 map 存儲最終的數據
• 當數據達到上限時移除鏈表尾部數據
• 將使用到的 Node 移動到鏈表的頭結點

雖然 Go 比較簡潔，但好消息是基本的雙向鏈表結構還是具備的。

所以基於此便定義了一個 LruCache:

根據之前的分析：

• size 存儲快取大小。
• 鏈表存儲數據順序。
• map 存儲數據。
• lock 用於控制並發安全。

接下來重點是兩個函數：寫入、查詢。

寫入時判斷是否達到容量上限，達到後刪除尾部數據；否則就想數據寫入頭部。

而獲取數據時，這會將查詢到的結點移動到頭結點。

這些結點操作都由 List 封裝好了的。

所以使用起來也比較方便。

最終就是通過這個 LruCache 實現了上圖的效果，想要了解更多細節的可以參考源碼:

//github.com/crossoverJie/ptg/blob/main/gui/lru.go