Wiki を眺めていたらキャッシュアルゴリズムの一つでLRU（Least Recently Used）というものを見つけたので C# で実装してみたいと思います。
LRUの実装方法ですが、データの時間的局所性という概念（最近アクセスされたデータは近いうちにまた使われやすいが、古いものは参照されにくい）という特性に注目して、データが最後に使われたのはいつであるかを記録して、最近最も使われなかったデータをキャッシュから削除する方式で C# のキャッシュ管理クラスを実装します。
問題を単純化するためにデータを取得するときだけキャッシュ状態をチェックします。
作成環境
- Windows 11 + コンソールアプリで実装
- Visual Studio2022
- .NET 8 + C# 12 に準拠
古い環境（.NET Framework）などではコンパイルエラーが発生します。
実装例
さっくりと実装例は以下の通りです。
Get (キャッシュからオブジェクトの取得) / Clear (キャッシュクリア) のみで、使い終わったら Dispose して終了を想定しています。
また参考程度にヒット率を HitRate プロパティで取得できます。一般的に、0.5 はキャッシュの意味が薄い、0.9 まで行くとキャッシュがかなり活用できていると言われています。
同期版
/// <summary> /// データが最後に使われたのはいつであるかを記録し /// 最近最も使われなかったデータをキャッシュから削除するキャッシュアルゴリズム(LRU)の実装です。 /// </summary> /// <typeparam name="TKey">管理対象を表すキー</typeparam> /// <typeparam name="TValue">管理対象のオブジェクトの型</typeparam> public class LruCache<TKey, TValue> : IDisposable where TKey : notnull, IEquatable<TKey> { // キャッシュの容量 readonly int _capacity; // オブジェクトのロード方法 readonly Func<TKey, TValue> _createFunc; // キャッシュ管理用のオブジェクト readonly Dictionary<TKey, LinkedListNode<CacheItem>> _cacheMap = []; readonly LinkedList<CacheItem> _lruList = new(); // ロック用のオブジェクト readonly object _lockObj = new(); // 破棄したかどうか(true: 破棄済み) bool _disposed; // 全アクセス数 long _totalAccesses; // ヒット率 long _hitCount; // キャッシュのヒット率を取得する(0～1.0の範囲) double HitRate => _totalAccesses == 0 ? 0.0 : (double)_hitCount / _totalAccesses; // エラーが発生したときに状況を通知する public event Action<Exception> Faulted; // キャパシティとオブジェクトの作成方法を指定してインスタンスを作成 public LruCache(int capacity, Func<TKey, TValue> createFunc) { if (capacity < 1) throw new ArgumentOutOfRangeException(nameof(capacity), "Capacity must be over 0."); ArgumentNullException.ThrowIfNull(createFunc); _capacity = capacity; _createFunc = createFunc; } // 破棄する public void Dispose() { Dispose(true); GC.SuppressFinalize(this); } protected virtual void Dispose(bool disposing) { if (_disposed) return; if (disposing) { Clear(); } _disposed = true; } // オブジェクトを取得する // キャッシュにあればキャッシュから取得、キャッシュに無ければ新規作成 public TValue Get(TKey key) { ArgumentNullException.ThrowIfNull(key); ObjectDisposedException.ThrowIf(_disposed, this); lock (_lockObj) { _totalAccesses++; if (_cacheMap.TryGetValue(key, out var item)) { _hitCount++; _lruList.Remove(item); // 先頭に移動 _lruList.AddFirst(item); return item.Value.Value; } else { var newObj = _createFunc(key); AddValue(key, newObj); return newObj; } } } // キャッシュを全てクリアする public void Clear() { lock (_lockObj) { foreach (CacheItem node in _lruList) { DisposeOne(node.Value); } _cacheMap.Clear(); _lruList.Clear(); } } // オブジェクトを管理データに追加する void AddValue(TKey key, TValue value) { if (_cacheMap.Count >= _capacity) { // 最後のものを削除 LinkedListNode<CacheItem> lastNode = _lruList.Last; _lruList.RemoveLast(); _cacheMap.Remove(lastNode.Value.Key); DisposeOne(lastNode.Value.Value); Console.WriteLine($"キャッシュから削除した: {lastNode.Value.Key}"); } LinkedListNode<CacheItem> node = new(new CacheItem(key, value)); _lruList.AddFirst(node); _cacheMap[key] = node; } // 削除する要素を破棄する void DisposeOne(TValue value) { var tempValue = value; if (tempValue is IDisposable d) d.Dispose(); else if (tempValue is IAsyncDisposable da) { var _ = da.DisposeAsync().AsTask().ContinueWith(t => { if (t.IsFaulted) Faulted?.Invoke(t.Exception); // 通知のみ }); } } // 内部データ管理用のオブジェクト readonly struct CacheItem(TKey key, TValue value) { // 管理上は変更しないからimmutableにしておく public readonly TKey Key = key; public readonly TValue Value = value; } }
非同期版
こっちは非同期版です。内容は同じです。
/// <summary> /// データが最後に使われたのはいつであるかを記録し /// 最近最も使われなかったデータをキャッシュから削除するキャッシュアルゴリズム(LRU)の実装です。 /// </summary> /// <typeparam name="TKey">管理対象を表すキー</typeparam> /// <typeparam name="TValue">管理対象のオブジェクトの型</typeparam> public class LruCacheAsync<TKey, TValue> : IAsyncDisposable where TKey : IEquatable<TKey> { // キャッシュの容量 readonly int _capacity; // オブジェクトのロード方法 readonly Func<TKey, Task<TValue>> _createFunc; // キャッシュ管理用のオブジェクト readonly Dictionary<TKey, LinkedListNode<CacheItem>> _cacheMap = []; readonly LinkedList<CacheItem> _lruList = new(); // ロック用のオブジェクト //readonly object _lockObj = new(); readonly SemaphoreSlim _lockObj = new(1, 1); // 破棄したかどうか(true: 破棄済み) bool _disposed; // 全アクセス数 long _totalAccesses; // ヒット率 long _hitCount; // キャッシュのヒット率を取得する(0～1.0の範囲) public double HitRate => _totalAccesses == 0 ? 0.0 : (double)_hitCount / _totalAccesses; // キャパシティとオブジェクトの作成方法を指定してインスタンスを作成 public LruCacheAsync(int capacity, Func<TKey, Task<TValue>> createFunc) { if (capacity < 1) throw new ArgumentOutOfRangeException(nameof(capacity), "Capacity must be over 0."); ArgumentNullException.ThrowIfNull(createFunc); _capacity = capacity; _createFunc = createFunc; } // 破棄する public async ValueTask DisposeAsync() { await DisposeAsync(true); GC.SuppressFinalize(this); } protected async virtual ValueTask DisposeAsync(bool disposing) { if (_disposed) return; if (disposing) { await ClearAsync(); } _disposed = true; } // オブジェクトを取得する // キャッシュにあればキャッシュから取得、キャッシュに無ければ新規作成 public async ValueTask<TValue> GetAsync(TKey key) { ArgumentNullException.ThrowIfNull(key); ObjectDisposedException.ThrowIf(_disposed, this); await _lockObj.WaitAsync(); try { _totalAccesses++; if (_cacheMap.TryGetValue(key, out var item)) { _hitCount++; _lruList.Remove(item); // 先頭に移動 _lruList.AddFirst(item); return item.Value.Value; } else { var newObj = await _createFunc(key); await AddValueAsync(key, newObj); return newObj; } } finally { _lockObj.Release(); } } // キャッシュを全てクリアする public async ValueTask ClearAsync() { await _lockObj.WaitAsync(); try { foreach (CacheItem node in _lruList) { await DisposeValueAsync(node.Value); } _cacheMap.Clear(); _lruList.Clear(); } finally { _lockObj.Release(); } } // オブジェクトを管理データに追加する async ValueTask AddValueAsync(TKey key, TValue value) { if (_cacheMap.Count >= _capacity) { // 最後のものを削除 LinkedListNode<CacheItem> lastNode = _lruList.Last; _lruList.RemoveLast(); _cacheMap.Remove(lastNode.Value.Key); await DisposeValueAsync(lastNode.Value.Value); Console.WriteLine($"キャッシュから削除した: {lastNode.Value.Key}"); } LinkedListNode<CacheItem> node = new(new CacheItem(key, value)); _lruList.AddFirst(node); _cacheMap[key] = node; } // 削除する要素を破棄する static async ValueTask DisposeValueAsync(TValue value) { if (value is IDisposable d) { d.Dispose(); } else if (value is IAsyncDisposable da) { await da.DisposeAsync(); } } // 内部データ管理用のオブジェクト readonly struct CacheItem(TKey key, TValue value) { // 管理上は変更しないからimmutableにしておく public readonly TKey Key = key; public readonly TValue Value = value; } }
使い方
同期版でキャッシュが効いているかの確認とクラスの使い方です。
static void Main(string[] args) { // オブジェクトの生成方法を指定してキャッシュ管理を作成 LruCache<int, string> cache = new(3, key => { Console.WriteLine($"キャッシュに追加した: {key}"); return key.ToString(); }); // データ取得例 cache.Get(1); cache.Get(2); cache.Get(3); // キャッシュに追加 cache.Get(1); // 先頭に移動 cache.Get(4); // 2が削除され、4が追加 cache.Get(5); // 3が削除され、5が追加 cache.Get(6); // 1が削除され、6が追加 // 出力ログ: // キャッシュに追加した: 1 // キャッシュに追加した: 2 // キャッシュに追加した: 3 // キャッシュに追加した: 4 // キャッシュから削除した: 2 // キャッシュに追加した: 5 // キャッシュから削除した: 3 // キャッシュに追加した: 6 // キャッシュから削除した: 1 }
今回は簡単めに実装しましたが以下のような処理を追加しても面白いと思います。
- タイマーを使用した期限付きキャッシュで古い時間が経ったキャッシュを積極的に破棄する実装を追加する
- 削除するときにカスタム破棄処理を挿入する
キャッシュを IEnumerable\<TValue> で取得し、foreach で列挙するアイデアは面白いかもしれませんが実用上は全く使うことがないと思うので実装はしていません。
以上です。
