memcachedなどの外部アプリケーションをすぐに使用するというアイデアを拒否しました。これにより、グラフのエッジに沿った各遷移に避けられない追加の遅延が発生します。 アプリケーション内での実装について質問がありました。
TBBライブラリーにLRUキャッシュの実装があることをドキュメントが有益に示唆しています。 残念ながら、その時点でのこの実装はプレビュー状態でした（まだ存在する場合）。
私には選択肢がありました-バグを修正するのは素晴らしい冒険になるか、独自のテストを作成する、十分にテストされていない実装に依存します。 また、利用可能なキャッシュアルゴリズムの出版物をざっと見てみると、おそらくLRUが最も効率的なスキームではないと思うようになりました。 負荷の高いアプリケーションの場合、数パーセントの余分な効率でさえパンです。 見つけたものをすべて調べた後、 CARTアルゴリズムに決めました。
このスキームには、いくつかの有用な利点があります。
- スキャン保護。 データベース全体を一度調べても、これはキャッシュの有効性に影響しません。 このような状況は、たとえば分析ツールを使用するときに発生する可能性があります。
- 二重治療に対する保護。 多くの場合、同じデータベースアイテムが短い間隔で2回要求され、その後まったくアクセスされないことがあります。 これにより、そのような動作に対して保護されていない回路の効率が大幅に低下する可能性があります。そのように要求された要素は、回路内で優先順位を受け取るためです。
- キャッシュ内の各ヒットは、内部構造の重要な操作やメンテナンスを必要としません（LRUの重大な欠点です）。 これは、各処理でブロッキングを必要としないため、マルチスレッド実装では非常に重要です。
回路が実際にどれほど効果的であるかを見てみましょう。 他のスキームを実装してデバッグするのに十分な時間がなかったため、有効性をTBBライブラリの同じLRU実装と比較します。
最初に、3つのキャッシュサイズ（100、500、および1000）について、ランダムに生成された数字のシーケンス（0〜10000）で両方のスキームの有効性をテストします。
少ないほど良い。
乱数、キャッシュサイズ100
カートの結果：0.99、逃した994950/1005000
LRU結果：0.990057、995007 / 1005000を逃した
乱数、キャッシュサイズ500
カートの結果：0.949862、954611 / 1005000を逃した
LRU結果：0.95016、954911 / 1005000を逃した
乱数、キャッシュサイズ1000
カート結果：0.90002、904520 / 1005000を逃した
LRU結果：0.900309、904811 / 1005000を逃した
CARTは効率においてLRUをわずかに上回っていますが、率直に言って、完全なランダムアクセスは良いテストではありません。 さらに、このタイプのアクセスを伴う実際のアプリケーションでは、キャッシュの有効性は低くなります。
したがって、2番目のテストは実際のアプリケーションのようになりました。 ここでは、6つのバスケットから番号が取得されます。各バスケットの要素数は増加しているため、特定の番号を選択する可能性が低くなります。 したがって、合計0から150までの数字は、5000から10000までの数字と同じ確率で選択されます。この戦術は、たとえば、しばしば着信ユーザーがデータベースをプルするユーザーデータベースからのサンプリングパターンに似ています。
ビンの描画、キャッシュサイズ100
CART結果：0.920258、逃した924859/1005000
LRU結果：0.965795、逃した970624/1005000
ビンの描画、キャッシュサイズ500
CART結果：0.721484、逃した725091/1005000
LRU結果：0.84106、845265 / 1005000を逃した
ビンの描画、キャッシュサイズ1000
CART結果：0.581132、584038 / 1005000を逃した
LRU結果：0.71412、逃した717691/1005000
この場合、CARTはすでにLRUよりもかなり良い結果を示しています。 実際、これを達成したかったのです。 興味のある方は、サンプルをダウンロードして自分で起動することをお勧めします。
ここでこの実装を見つけます 。 負荷のかかった実際のアプリケーションでテストされましたが、可能性のあるバグが100％存在しないことを保証するものではありません。 言うまでもなく、あなた自身の危険とリスクで使用してください。 プロジェクトに統合するには、Includeフォルダー内のファイルのみが必要です。 HashMurmur3への依存は、自分に合った任意のハッシュ関数に置き換えることで排除できます。
依存関係では、この実装にはTBBしかありませんが、C ++でマルチスレッドアプリケーションを作成する人のほとんどがTBBを使用しています。 ボーナスとして、乱数ジェネレーターの適切な実装が添付されています。 また、元の実装ではSTLではなくEASTLを使用していますが、公開バージョンを投稿する前にこの依存関係を取り除きました。
サンプルソースはVS2010の下で構築されますが、Linuxポートは問題を引き起こさないはずです。 私は現在Linuxを手元に持っていないので、誰かがこれに少し時間を費やしてこのポートを作成してくれたら、コミュニティに感謝します。
PS優れたキャッシュスキームを適用する方法には、膨大な量があります。 たとえば、私にとって、この実装はメモリマップドファイルへのアクセスにも使用されます。ファイルは完全にマップされないため、大きなファイルで仮想メモリが大量に消費される可能性がありますが、それぞれ16 MBの小さな断片が制限されます。 キャッシュは、メモリから取り出す部分を制御します。 そのような欲求が突然発生した場合は、数百行で独自のmemcachedを作成することもできます。