キャッシュとしてのConcurrentDictionary

多くの開発者は、多くの場合、データベースからのみデータを受信するか、いくつかのテーブルのキャッシュを保持するというジレンマに直面します。 基本的に、これらはレコードをほとんど含まないディレクトリであり、常に手元に必要です。 これはハリウッドの問題であり、この記事では対処しません。



.NET上のトランスポート監視システムの負荷の高いサーバーを設計するときに、同じ問題が目の前で発生しました。 その結果、キャッシュが必要であることが決定されました。 辞書キャッシュは、ConcurrentDictionaryのラッパーに格納されるようになりました。 このオプションは、スレッドセーフなディクショナリ用の標準の.NETツールであるため、あまり調査することなく採用されました。 今こそ、このソリューションのパフォーマンスをテストするときです。 これについては、実際には記事です。 また、この記事の最後には、ConcurrentDictionary内での配置方法に関する少しの研究があります。







問題の声明



キーと値のペアのスレッドセーフなコレクションが必要です。これにより、次のことが可能になります。

1. 識別子キーを持つオブジェクトを要求する-もちろん、最も頻繁に使用されます。
2. 新しい要素を変更、削除、追加することはまれですが、スレッドの安全性を確保する必要があります。
3. 値の操作-すべての値を要求し、値オブジェクトのプロパティで検索します。

条項3は辞書コレクションでは一般的ではないため、この構成の主なブレーキとなります。 ただし、ルックアップテーブルのキャッシュを使用する場合、そのような状況は避けられません（たとえば、編集のために管理パネルにディクショナリ全体を表示するのは簡単です）。



キャッシュが使用されるさまざまなシステムを検討してみましょう。 これらは、辞書を使用した操作の頻度が異なります。 これらの操作のタイプを形式化します。

• GET-キーによるオブジェクトのリクエスト、
• ADD-新しいキーで新しいオブジェクトを追加（そのようなキーが既に存在する場合は上書き）
• UPDATE-既存のキーの新しい値（キーがない場合は何もしません）
• SEARCH-イテレーターを使用します。この場合、最初の適切な値を検索します

テスト参加者のリスト

1. ConcurrentDictionary 。 これは、スレッドセーフが統合されたMicrosoftのターンキーソリューションです。 便利なメソッドTryGetValue、TryAdd、TryUpdate、AddOrUpdate、TryDeleteを実装します。これにより、競合解決ポリシーを簡単に設定できます。 実装機能については、記事の最後で説明します。
2. Monitorを介したロック付きの辞書 。 最も正面からの解決策は、すべての非スレッドセーフ操作がロック構造にラップされることです。
3. ReaderWriterLockを介したロック付きの辞書 。 以前のソリューションの最適化-操作は読み取り操作と書き込み操作に分けられます。 したがって、複数のストリームを同時に読み取ることができ、記録には排他的アクセスが必要です。
4. ReaderWriterLockSlimを介したロック付きの辞書 。 基本的に同じですが、新しいクラスを使用します（再帰制御設定を追加）。 このタスクのコンテキストでは、ReaderWriterLock以外を表示する必要はほとんどありません。
5. Wintellect PowerThreadingライブラリのOneManyResourceLockerを介したロック付き辞書 -Jeffrey RichterによるReaderWriterLockのトリッキーな実装。 NuGetパッケージではなく、公式サイトのバージョンが使用されたことを明確にします。バージョンが異なるため、気に入らなかったためです。
6. Hashtable.Synchronized 。 また、Microsoftの既成のソリューション-スレッドセーフなインデクサーを提供します。 非ジェネリックコレクション（ボックス化、読みやすさの低下）であり、Tryプレフィックスを持つメソッドがないため、使用するのは不便です（同時に追加/更新するためのポリシーを設定することは不可能です）。

ハンドラーの実装方法を正確に簡潔に説明します。

1. GET操作：すべての参加者は、IDictionaryインターフェイスからスレッドセーフなTryGetValueメソッドを使用します。 Hashtableの場合、タイプコード化されたインデクサーが使用されます。
2. ADD操作：ConcurrentDictionaryの場合-AddOrUpdate、Dictionaryの場合-ロックの書き込みとインデクサーの追加、Hashtableの場合-ロックなしのインデクサーの追加。
3. UPDATE操作：ConcurrentDictionaryの場合、最初にTryGetValue、次にTryUpdate。
   
   このメソッドは、これら2つのメソッド間で並行更新を実行できるという点で興味深い（テスト中にも明らかになった）。 この場合、oldValueがTryUpdateに渡されるため、このまれなケースでは書き換えが失敗します。 ディクショナリの場合、ContainsKeyを介して可用性を確認し、成功した場合は書き込みロックを設定して値を上書きします。 Hashtable用の便利なTryUpdateがないため、キーの存在を確認する手間がかからず、追加の場合のように、値はインデクサーによって上書きされます（このコレクションでは、これは重要ではありません-とにかくかなり悪かったです）。
4. 操作SEARCH ：ConcurrentDictionaryの場合、LINQのFirstOrDefaultが使用され、残りの場合、同じFirstOrDefaultに対して読み取りロックが使用されます。

試験台



テスト用に、コンソールアプリケーションが作成されました（ リンク ）。

1. 特定のすべてのタイプの操作を処理できる一連のハンドラーが作成されます。
2. N個の要素のディクショナリが作成されます（デフォルトでは10,000）。
3. Mの量のさまざまなタイプのタスクのコレクションが作成されます（デフォルトでは10,000）。
4. 各ハンドラーは、生成された辞書内のすべてのタスク（すべてのハンドラーに共通）の並列処理を実行します。
5. 実験（ポイント2〜4）は、指定された回数（デフォルトでは10回）実行され、取得された時間は平均されます。 測定は、Core 2 Quad 2.66 GHzと8 GBのメモリを搭載したマシンで行われました。

デフォルト値は非常に小さいですが、値を増やしても基本的には何も変わりません。



試験結果



テストは、操作のタイプごとに異なる分散オプションを使用して実行され、テーブルが大きすぎることが判明しました。全体をここで確認できます（ リンク ） わかりやすくするために、合計操作数の値による読み取りの割合に応じてマイクロ秒単位でテスト実行時間のグラフを示します（書き込み操作は20％に固定され、残りはキーによって読み取られます）。







結論



すべての参加者のパフォーマンスは、書き込み操作の回数に関係なく、値ごとの読み取り回数に比例して低下します。

1. ConcurrentDictionary 。 実験により、このツールはこのタスクに最適であることが示されています。 値による読み取りはパフォーマンスに大きく影響しますが、他の参加者よりも高速です。
2. 辞書+モニター 。 大幅に遅い、期待される結果。
3. 辞書+ ReaderWriterLock 。 以前のバージョンの最適化もすべて期待されています。
   
   記録操作が多いほど、差は小さくなることに注意してください。 ある時点から、ブロックプロセス自体のオーバーヘッドが小さくなるため、Monitorがさらに好ましい状態になります。
4. 辞書+ ReaderWriterLockSlim 何らかの理由で、私は単純なモニターでさえも何とか失いました。 強化された機能（以前のバージョンと比較して）がパフォーマンスに影響したか、それを調理する方法がわかりません。
5. 辞書+ OneManyResourceLock 。 リヒターは、読み取り/書き込みロックからすべてを絞り出したようです。 テスト結果によると、これは辞書の最速使用です。 しかし、ConcurrentDictionaryはさらに高速です。
6. ハッシュテーブル 。 予想される失敗。 おそらく私はそれを誤って使用しましたが、他の参加者に匹敵する結果を得ることができるとは思いません。 とにかく、一般的でないコレクションを扱うのはどういうわけか気のめいるようでした。

内部デバイスConcurrentDictionary



勝者を詳しく見てみましょう。つまり、ConcurrentDictionaryのソースを見てみましょう。



このクラスを作成すると、 CapacityおよびConcurrencyLevelの 2つのパラメーターが設定されます。 最初の（ Capacity ）はコレクションに馴染みがあり、内部コレクションを展開せずに記録できる要素の数を設定します。 この場合、リンクされたリストが作成されます（m_buckets、バスケットと呼ばれます） デフォルト値は31です。



2番目のパラメーター（ ConsurrencyLevel ）は、辞書に同時に書き込むことができるスレッドの数を決定します。 これは、モニターによるロック用のオブジェクトのコレクションを作成することにより実現されます。 このような各ブロッキングオブジェクトは、ほぼ同じ数のバスケットを担当します。 デフォルト値はEnvironment.ProcessorCount * 4です。



したがって、ディクショナリ内の各オブジェクトは、それが存在するバスケットと書き込み用のロックオブジェクトに一意に関連付けられます。 これは、次の方法で行われます。

/// <summary> /// Computes the bucket and lock number for a particular key. /// </summary> private void GetBucketAndLockNo( int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount) { bucketNo = (hashcode & 0x7fffffff) % bucketCount; lockNo = bucketNo % lockCount; Assert(bucketNo >= 0 && bucketNo < bucketCount); Assert(lockNo >= 0 && lockNo < lockCount); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

奇妙なことに、ConcurrencyLevel = 1であっても、ConcurrentDictionaryは通常のロック辞書よりも高速です。 また、クラスがイテレータを介して使用するために最適化されていることも注目に値します（テストが示したとおり）。 特に、ToArray（）メソッドを呼び出すと、すべてのバスケットでロックが実行され、イテレーターが比較的安価に使用されます。



例：dictionary.Values.ToArray（）よりもdictionary.Select（x => x.Value）.ToArray（）を使用することをお勧めします。



この記事は、同社の一流開発者によって書かれました。

ご清聴ありがとうございました！