LRUキャッシュの実装アルゴリズムについて議論しましょう

ビジネスモデル

読み取り、書き込み、削除の比率はおよそ 7:3:1 です。少なくとも 500 万個のキャッシュ (キャッシュあたり平均 6k) をサポートする必要があり、比較的優れたパフォーマンスのキャッシュ アルゴリズムの設計が必要です。

アルゴリズム分析

MemCached や Velocity などの既存のキー値キャッシュ ソリューションを考慮せず、.NET gc を使用せずにメモリを個別に管理したり、ランダムおよびシーケンシャルなデータ読み取りのシナリオを考慮しなくても、現在、次の LRU キャッシュ ソリューションが利用可能です。

現在、いくつかのソリューションではマルチスレッドでのロックが必要であり、ロックフリーのソリューションを設計するのは簡単ではありません。次のリンクはマルチスレッドをサポートするソリューションですが、原理はまだ完全には理解されていません。

高性能マルチスレッドLRUキャッシュ
http://www.codeproject.com/KB/recipes/LRUCache.aspx

通常のリンクリストを使用したLRUキャッシュのシンプルな実装

以下は、最後のソリューションの簡単な実装です。このソリューションを最適化する価値があるかどうか、または他のどのソリューションがより適しているかについて説明しましょう。

公共 クラスLRUCacheHelper {
読み取り専用辞書 _dict;
読み取り専用リンクリスト _queue =新しいリンクリスト（）;

_dict.TryGetValue(キー、出力ret); //O(1)
ret.Next.Previous = ret.Previous //O(1)
ret. 前へ. 次へ. = ret. 次へ //O(1)
_queue.AddFirst(キー); //O(1)

改良したリンクリストは要件をほぼ満たしています。

切り捨てる場合、キャッシュがいっぱいになったときに、最も使用頻度の低いキャッシュ項目の何パーセントを切り捨てるかを指定できます。

もう 1 つは、複数のスレッドを使用するときにロックを最適化する方法を確認することです。辞書のスレッドセーフ バージョンがあります。.NET 3.0 の読み取り/書き込みロックを削除し、通常の汎用辞書を ThreadSafelyDictionay にするだけです。パフォーマンスは良好になるはずです。

リンクリストでのスレッド同期に読み取り/書き込みロックを使用するのは簡単ではありません。せいぜい、ミューテックスロックを使用できますが、ロックの粒度を考慮する必要があります。Move、AddFirst、およびRemoveLastの場合、操作されるノードは1つまたは2つだけです。これらのノードのみをロックする方法を見つけることは可能ですか？Truncateの場合、多くのノードをバッチで操作する必要があるため、大規模なリンクリストロックが必要ですが、このとき、データベースのテーブルロックや行ロックと同様に、他の操作を停止する方法を考慮する必要があります。

LRUキャッシュ実装コード

公共 クラスDoubleLinkedListNode {
 
    パブリックT 値 { 取得; 設定; }

両端リンクリストでテストした結果、1 秒あたり800,000 回以上の読み取りと 1 秒あたり200,000 回以上の書き込みが可能となり、パフォーマンスは許容範囲内であると感じました。

プログラムは 200 万のキャッシュ エントリを初期化し、その後エントリを追加し続けます。500 万のエントリが追加されるたびに 10 分の 1 が切り捨てられ、その後もその数は増加し続けます。

テスト モデルにおける 1 秒あたりの読み取りと書き込みの比率は 7:3 です。以下は、3 つの時点を連続してキャプチャしたパフォーマンス カウンターのグラフです。
図1

図2

図3

最大メモリは1Gに達し、CPUも平均90％を超えています。ただし、テストの後半では、最後のスクリーンショットに示すように、スループットが1〜2秒間0になることがよくあります。後で観察すると、1〜2秒の一時停止は第2世代メモリのリサイクルであることがわかります。一時停止がない場合、#gen 2コレクションは1つ増加します。これは、リンクリストが原因であると考えられます。リンクリストのノードの追加と削除は、オブジェクトが頻繁に作成および破棄されるため、GCの負荷が非常に高くなります。

LRU キャッシュフォローアップの改善

1. 通常の両端リンク リストの代わりにカーソル リンク リストを使用します。プログラムは、まず固定サイズの配列を割り当て、次に配列インデックスを使用してリンク リストを作成します。これにより、ノードが追加または削除されるたびに GC を実行する必要がなくなります。これは手動のメモリ管理と同等ですが、C# で適切な実装をまだ見つけていません。

2. リンクリストはマルチスレッド環境での使用には適していないという意見もあります。リンクリストの各操作にはミューテックス ロックが必要で、読み取り/書き込みロックも使用できないためです。現在の実装では、スレッド同期にミューテックス ロックを直接使用しており、スループットは 1 秒あたり 70 万から 80 万です。ロックがボトルネックになっているとは感じていません。改善したい場合は、Dictionary を ThreadSafelyDictionary に置き換えてから、リンクリストにミューテックス ロックを使用できます (当初想定されていた、リンクリスト操作で操作するノードをいくつかロックして同時実行の競合を減らすという考え方は、賢明ではなく、厳密ではありません)。

3. もう一つの箇所は、ロックを細分化することです。リンクリストは依然としてリンクリストですが、リンクリストの各ノードは HashSet です。HashSet に対する操作が読み取り、書き込み、削除のみで、トラバーサルがない場合、スレッド同期は必要ありません (Set はコレクションなので、必要ないと思います。1 つのスレッドが挿入し、1 つのスレッドが削除し、1 つのスレッドが読み取ります。問題はないはずです。最大でも、読み込んだデータがすぐに削除され、Set 全体の構造が破壊されることはありません)。そして、新しいデータを追加するときは、リンク リストの先頭の Set に挿入します。特定のデータを読み取るときは、そのデータがあるノードの Set からデータを削除し、リンク リストの先頭の Set に新しいデータを挿入します。操作を繰り返すと、リンク リストの最後のノードの Set のデータはすべて古いデータになり、安全に削除できます。もちろん、この削除中はリンク リスト全体をロックする必要があります。各 Set には 20w などの上限が必要ですが、Set を安全にトラバースできないため、現在のサイズを取得できません。そのため、Set データを追加および削除する場合は、Interlocked.Decrement() および Interlocked.Increment() を使用して Count を維持する必要があります。Set がいっぱいになると、リンク リストの先頭に新しい Set ノードが追加されます。

LRU キャッシュ パフォーマンス テスト スクリプト

クラスプログラム { 
    プライベート 静的パフォーマンスカウンタ_addCounter; 
    プライベート 静的パフォーマンスカウンタ_getCounter; 
   
    静的  void Main(文字列[] 引数) {
        セットアップカテゴリ();
        _addCounter =新しいPerformanceCounter( "wawasoft.lrucache" 、 "add/sec" 、 false );
        _getCounter =新しいPerformanceCounter( "wawasoft.lrucache" 、 "get/sec" 、 false );
        _addCounter.RawValue = 0 ;
        _getCounter.RawValue = 0 ; 
   
        ランダム rnd = new Random(); 
        定数 整数最大値 = 500 * 10000 ; 
   
   
        LRUCacheHelper< int , int > キャッシュ = new LRUCacheHelper< int , int >( 200 * 10000 , max); 
   
         ( int i = 10000 * 100000 - 1 ; i >= 0 ; i--)の場合
        { 
             (i % 10 > 7 )の場合
            {
                スレッドプール.QueueUserWorkItem(
                    代表者
                        {
                            キャッシュに追加(rnd.Next( 0 , 10000 ), 0 );
                            _addCounter.Increment();
                        });
            } 
            それ以外 
            {
                スレッドプール.QueueUserWorkItem(
                   代表者
                   { 
                        int pop = キャッシュ.Get(i);
                       _getCounter.Increment();
                   });
            }
        }
        コンソールのキーを読み取ります。
    } 
   
    プライベート 静的  voidセットアップカテゴリ() { 
         if (!PerformanceCounterCategory.Exists( "wawasoft.lrucache" )) { 
   
            カウンター作成データコレクション CCDC =新しいカウンター作成データコレクション(); 
   
            カウンター作成データ addcounter =新しいカウンター作成データ();
            カウンタを追加します。カウンタタイプ = PerformanceCounterType.RateOfCountsPerSecond32;
            addcounter.CounterName = "追加/秒" ;
            CCDC.Add(カウンタを追加します); 
   
   
            カウンター作成データ getcounter = new CounterCreationData();
            getcounter.CounterType = PerformanceCounterType.RateOfCountsPerSecond32;
            getcounter.CounterName = "get/sec" ;
            CCDC.Add(カウンタを取得); 
   
            パフォーマンス カウンタ カテゴリを作成します ( "wawasoft.lrucache" 、 "lrucache" 、CCDC)。 
   
        }
    } 
   
 }