借助 PriorityQueue 實作簡單的 Lru Cache

Intro

在使用緩存的時候往往要考慮緩存限制以免緩存過多地占用套用記憶體而且這樣緩存的效率可能並不夠高

比較常見的做法是實作緩存驅逐/淘汰，比如 LRU Cache，redis 預設的記憶體策略也是基於 lru 的 allkeys-lru，

.NET 6 開始引入了 PriorityQueue 這一數據結構 ，在 .NET 9 中支持了 Remove ，我們可以透過 Remove + enqueue 來實作 update priority 的需要，今天我們就借助 .NET 裏的 PriorityQueue 來實作 LRU cache

Samples

首先我們來看下基於 PriorityQueue 的 LruCache 簡單實作


file interfaceICache
{
voidPrintKeys();
voidSet(string key, object? value);
bool TryGetValue<TValue>(string key, [MaybeNullWhen(false)] out TValue value);
}
file sealed class LruCache(int maxSize) : ICache
{
privatereadonly ConcurrentDictionary<string, object?> _store = new();
privatereadonly PriorityQueue<string, long> _priorityQueue = new PriorityQueue<string, long>();
privatereadonly JsonSerializerOptions _jsonSerializerOptions = new()
{
WriteIndented = true
};
public ICollection<string> Keys => _store.Keys;
publicvoidPrintKeys()
{
Console.WriteLine("PrintKeys:");
Console.WriteLine(JsonSerializer.Serialize(_store, _jsonSerializerOptions));
}
publicvoidSet(string key, object? value)
{
if (_store.ContainsKey(key))
{
_store[key] = value;
UpdateKeyAccess(key);
return;
}
while (_store.Count >= maxSize)
{
var keyToRemove = _priorityQueue.Dequeue();
_store.TryRemove(keyToRemove, out _);
}
_store[key] = value;
UpdateKeyAccess(key);
}
publicbool TryGetValue<TValue>(string key, [MaybeNullWhen(false)] out TValue value)
{
if (!_store.TryGetValue(key, outvar cacheValue))
{
value = default;
returnfalse;
}
UpdateKeyAccess(key);
value = (TValue)cacheValue!;
returntrue;
}
privatevoidUpdateKeyAccess(string key)
{
_priorityQueue.Remove(key, out _, out _);
_priorityQueue.Enqueue(key, DateTimeOffset.UtcNow.ToUnixTimeMilliseconds());
}
}










cache 主要定義了 Get/Set 兩個方法，LruCache 設定了最大的 cache 數量，簡單的按照 key 的數量來計算，沒有計算實際的記憶體占用等

用了一個 ConcurrentDictionary 來存 cache，這裏的 cache 出於簡單考慮不設定過期時間，只根據 cache keys limit 來計算，使用 PriorityQueue 來保存緩存最近一次存取的時間以根據存取的時間來決定需要驅逐的時候誰應該被驅逐

來看一個簡單的使用範例：

var cache = new LruCache(2);
cache.Set("name", "test");
cache.Set("age", "10");
cache.PrintKeys();
ConsoleHelper.HandleInputLoop(x =>
{
if (x.StartsWith("get:"))
{
var key = x["get:".Length..];
cache.TryGetValue(key, outstring? value);
Console.WriteLine($"key: {key}, value: {value}");
return;
}
cache.Set(x, "Hello .NET");
cache.PrintKeys();
}, "Input something to test lruCache, starts with 'get:' to try get cache value, otherwise set cache, input q to exit");
ConsoleHelper.ReadLine();



ConsoleHelper.HandInputLoop 是一個幫助方法，可以不斷的從 console 讀取 Input 並進行一定的處理，預設輸出 q 來結束迴圈，我們執行一下看下效果

首先先打印了一下緩存的數據，我們開始設定了 age 和 name 兩個緩存值，然後透過輸入迴圈來設定新的緩存和存取某一個緩存，

首先我們設定了一個 aa 緩存，因為我們設定了最多保留兩個緩存而且緩存中已經有了兩個緩存，這樣我們就需要驅逐一個 key 才能設定新的 key，首先加入的 key 被認為是最早存取的一個 key 應該被驅逐，所以 name 被移除了，然後新的 key aa 被加入到緩存中

之後我們再次設定了 aa ，因為之前已經在緩存裏了，無需驅逐緩存，可以直接更新已有的緩存並更新最後存取的時間

接著我們存取了一下 age 緩存，這樣我們最近存取的緩存就變成了它，下次有新的緩存進來就不應該淘汰 age 緩存

之後我們設定一個 aaa 緩存，從輸出結果可以看到，此時緩存中的 key 是 age/aaa，aa 的存取時間較早所以被淘汰了

我們再來設定一下 aa ，此時 age 就被淘汰了，緩存中剩下 aaa / aa

這裏我們只是記錄了一下最後的存取時間，我們也可以記錄下存取的次數，根據存取時間+存取次數做一個權重計算一個綜合之後的優先級，這樣就比單獨按照時間來計算更加具體參考意義，你覺得有別的需要記錄也可以考慮記錄下來，然後透過自訂比較器來決定誰應該被驅逐誰應該被保留

下面是一個帶有存取次數的一個 lru cache 的範例

file sealed record CacheAccessEntry
{
publicint AccessCount { get; set; }
publiclong AccessTimestamp { get; set; }
}
file sealed class CacheAccessEntryComparer(Func<CacheAccessEntry, long>? priorityFactory) : IComparer<CacheAccessEntry>
{
publicCacheAccessEntryComparer() : this(null)
{
}
publicintCompare(CacheAccessEntry? x, CacheAccessEntry? y)
{
ArgumentNullException.ThrowIfNull(x);
ArgumentNullException.ThrowIfNull(y);
if (priorityFactory is not null)
{
return priorityFactory(x).CompareTo(priorityFactory(y));
}
if (x.AccessCount == y.AccessCount)
{
return x.AccessTimestamp == y.AccessTimestamp
? 0
: (x.AccessTimestamp > y.AccessTimestamp ? 1 : -1)
;
}
return x.AccessCount > y.AccessCount ? 1 : -1;
}
}
file sealed class LruCacheV2(int maxSize) : ICache
{
privatereadonly ConcurrentDictionary<string, object?> _store = new();
privatestaticreadonly CacheAccessEntryComparer CacheEntryComparer = new();
privatereadonly PriorityQueue<string, CacheAccessEntry> _priorityQueue =
new(CacheEntryComparer);
public ICollection<string> Keys => _store.Keys;
publicvoidPrintKeys()
{
Console.WriteLine("PrintKeys:");
Console.WriteLine(JsonSerializer.Serialize(_store));
}
publicvoidSet(string key, object? value)
{
if (_store.ContainsKey(key))
{
_store[key] = value;
UpdateKeyAccess(key);
return;
}
while (_store.Count >= maxSize)
{
var keyToRemove = _priorityQueue.Dequeue();
_store.TryRemove(keyToRemove, out _);
}
_store[key] = value;
UpdateKeyAccess(key);
}
publicbool TryGetValue<TValue>(string key, [MaybeNullWhen(false)] out TValue value)
{
if (!_store.TryGetValue(key, outvar cacheValue))
{
value = default;
returnfalse;
}
UpdateKeyAccess(key);
value = (TValue)cacheValue!;
returntrue;
}
privatevoidUpdateKeyAccess(string key)
{
_priorityQueue.Remove(key, out _, outvar entry);
entry ??= new();
entry.AccessTimestamp = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
entry.AccessCount += 1;
_priorityQueue.Enqueue(key, entry);
}
}















使用範例和前面類似，只需要把 LruCache 改成 LruCacheV2 即可

var cache = new LruCacheV2(2);
cache.Set("name", "test");
cache.Set("age", "10");
cache.PrintKeys();
ConsoleHelper.HandleInputLoop(x =>
{
if (x.StartsWith("get:"))
{
var key = x["get:".Length..];
cache.TryGetValue(key, outstring? value);
Console.WriteLine($"key: {key}, value: {value}");
return;
}
cache.Set(x, "Hello .NET");
cache.PrintKeys();
}, "Input something to test lruCache, starts with 'get:' to try get cache value, otherwise set cache, input q to exit");



執行結果如下：

這裏我們針對 age 存取了兩次，雖然之後存取了 aa ， aa 的最後存取時間是最新的，但是存取次數較少，V2 版本預設優先了存取次數，導致 age 的驅逐優先級低於 aa , aa 被淘汰

以上範例僅作參考，具體程式碼可以從文末的 Github 連結獲取，實際要實作緩存的驅逐建議只是標記一下已刪除，實際刪除工作交給後台任務去執行，以免緩存驅逐的過程導致效能問題

References