JVM 内部キャッシュを選択するにはどうすればいいですか?あなたの疑問に答える記事

[[332941]]

JVMの内部キャッシュとは何ですか

ネイティブJava

HashMap のチェーンメソッドに新しい参照を追加するだけで、HashMap とリンクリストの両方であるリンクリストを形成できます。このように、出力は順序付けされ、アクセスに応じて順序を動的に調整できるため、FIFO または LRU の特性を実現できます。

削除機能や手動削除なしで、ConcurrentHashMap をキャッシュとして使用します。しかし、検索効率は高く、スレッドセーフです

これにはいくつかの問題があることは明らかです。スレッドは安全ではなく、追加のロックが必要であり、機能構造は単純で、有効期限がないため、メモリリークが発生しやすくなります。

グアバ

LinkedHashMap に問題があったため、偉大なる神々はそれを基に Guava を作成しました。

HashMap はスレッドセーフではないため、CurrentHashMap (類似していますが、完全に同じではありません) を使用してください。有効期限を設定するには、データにタイムスタンプを追加します。書き込み後の有効期限と読み取り後の有効期限を実現するために、これら 2 つの構成では、それぞれ読み取りと書き込みを表す複数のキューを使用します。

エクヘド

Ehcache はローカルディスクへの永続性をサポートしていますが、Guava はサポートしていません。
Ehcache には既成のクラスタリングソリューションがありますが、Guava にはそれがありません。しかし、個人的には、JVM レベルのキャッシュには少し味気なく、重すぎると感じています。
Ehcache jar パッケージは非常に大きく、Guava Cache は Guava jar パッケージ内のツールの 1 つに過ぎず、後者は Ehcache よりもはるかに小さくなっています。
どちらのキャッシュも、キャッシュの有効期限が切れた場合やヒットがない場合にロードインターフェイスを介してデータを再ロードできますが、呼び出し方法は若干異なります。 2 つの主な違いは、Ehcache キャッシュがロードされるときに、ユーザーは null を返すことができますが、Guava Cache では null を返すことができません。Guava Cache は、値が null かどうかに基づいてロードするかどうかを決定するため、null を返すことはできませんが、使用時に空のオブジェクトに置き換えることができます。 null が返されることを許可しないことは良い考慮事項です。
Ehcache にはメモリ使用量の統計情報がありますが、Guava Cache にはないので、自分で開発する必要があります。
Ehcache がキャッシュを配置すると、K と V の両方がパッケージ化され、GC に一定の影響が生じます。

カフェイン

Caffeine は Spring 5 でサポートされているデフォルトのキャッシュであり、Spring がこれをいかに重視しているかがわかります。では、なぜ Spring は Guava を放棄して Caffeine を追求したのでしょうか?

キャッシュ削除戦略は、どのデータが短期的に再び使用される可能性が最も高いかを予測し、それによってキャッシュヒット率を向上させることです。 LRU は、実装が簡単で、実行時のパフォーマンスが効率的であり、一般的な使用シナリオでのヒット率が高いため、現時点では最適な実装アプローチである可能性があります。ただし、LRU は履歴データを通じて将来を予測することには限界があります。最後のデータは再度アクセスされる可能性が最も高いとみなされ、最高の優先順位が与えられます。これは、実際のホットデータを排除することを意味します。この問題を解決するために、業界ではデータ構造にいくつかの改良を加えて巧みに解決してきました。

以下の内容は翻訳の転載です。元の翻訳をご覧になりたい場合は、ここをクリックしてください。英語が得意な生徒は、英語の原文を直接見ることもできます。

キャッシュはパフォーマンスを向上させる一般的な方法であり、今日のほとんどのキャッシュ実装では従来の手法が使用されています。この記事では、Caffeine の最新の実装について説明します。 Caffeine は、高いヒット率と優れた同時実行性を提供するオープンソースの Java キャッシュライブラリです。これらのアイデアからインスピレーションを得て、好きなプログラミング言語に適用できるようになることを願っています。

立ち退き戦略

キャッシュ削除戦略は、どのデータが短期的に再度使用される可能性が最も高いかを予測し、キャッシュヒット率を向上させるように設計されています。 LRU (Least Recently Used) 戦略は、実装が簡単で、実行時のパフォーマンスが効率的で、一般的な使用シナリオでのヒット率が高いため、おそらく最も人気のあるエビクション戦略です。ただし、LRU は履歴データを通じて将来を予測することには限界があります。最後に到着したデータが再度アクセスされる可能性が最も高いと想定し、最高の優先度を与えます。

最新のキャッシュは履歴データの使用を拡張し、最新性とアクセス頻度を組み合わせてデータをより正確に予測します。履歴情報を保存する 1 つの方法は、人気スケッチ (圧縮された確率的データ構造) を使用して、多数の訪問イベントから頻繁に訪れる訪問者を見つけることです。カウントマトリックスと複数のハッシュメソッドによって実装される CountMin Sketch アルゴリズムを参照できます。読み取りが発生すると、マトリックス内の各行に対応するカウンターのカウントが増加します。頻度を推定する場合、すべての行の最小カウントに対応するデータが取得されます。このアプローチにより、行列の長さと幅を調整することで、スペース、効率、およびハッシュ衝突のエラー率の間でトレードオフを行うことができます。

Window TinyLFU (W-TinyLFU) アルゴリズムは、スケッチをフィルターとして使用します。新しいデータが削除されるデータよりも頻繁に発生する場合、そのデータはキャッシュによって受け入れられます。この許可ウィンドウにより、各データ項目はすぐにフィルタリングされるのではなく、人気度を蓄積する機会が与えられます。これにより、特にトラフィックが急増するシナリオで、短期間の繰り返しトラフィックが長時間保持されない場合に、継続的なミスを回避できます。履歴データを更新するために、すべてのカウンターを半分にする時間減衰プロセスが定期的または段階的に実行されます。

長期保存データの場合、W-TinyLFU はセグメント化された LRU (SLRU) 戦略を使用します。最初、データ項目は試用セグメントに保存され、その後アクセスされると保護セグメントに昇格されます (保護セグメントは総容量の 80% を占めます)。保護セグメントがいっぱいになると、一部のデータが削除されてトライアルセグメントに戻され、これにより、トライアルセグメントの削除が連鎖的にトリガーされることもあります。このメカニズムにより、アクセス間隔が短いホットデータは保持され、繰り返しアクセスが少ないコールドデータはリサイクルされます。

図のデータベースと検索シナリオの結果に示されているように、近接性と頻度を考慮することで LRU のパフォーマンスを大幅に向上できます。 ARC、LIRS、W-TinyLFU などの高度な戦略では、最適に近いヒット率が得られます。より多くのシナリオテストを確認するには、対応する論文を確認するか、シミュレータを使用して独自のシナリオをテストしてください。

有効期限ポリシー

有効期限の実装では、各データ項目の有効期限が異なることがよくあります。容量の制限により、期限切れのデータは遅延して削除する必要があります。そうしないと、期限切れのダーティデータがキャッシュ全体を汚染することになります。通常、キャッシュ内で専用のクリーニングスレッドが有効になり、キャッシュを定期的に走査してクリーニングします。この戦略は、バックグラウンドスレッドによって期限切れのデータをクリアする時間のオーバーヘッドが隠されるため、各読み取りおよび書き込み操作中に有効期限でソートされた優先キューを使用して期限切れのキャッシュを消去するよりも優れています。

ほとんどのシナリオではさまざまなデータ項目が固定の有効期限を使用しているため、Caffien は統一された有効期限アプローチを採用しています。この制限により、O(1) 順序付きキューを使用してデータを整理することが可能になります。書き込まれた後に期限が切れるデータについては書き込み順序キューが維持され、読み取られた後に期限が切れるデータについては読み取り順序キューが維持されます。キャッシュは、以下で紹介するエビクション戦略と同時実行メカニズムに基づいてキューを再利用できるため、期限切れのデータ項目はキャッシュのメンテナンスフェーズ中に破棄できます。

同時

ほとんどのキャッシュ戦略では、データの読み取りはキャッシュ状態への書き込みを伴うため、同時キャッシュ読み取りは難しい問題であると考えられます。従来の解決策は、同期ロックを使用することです。これは、ロック分割の最適化のためにキャッシュされたデータを複数のパーティションに分割することによって実行できます。残念ながら、ホットデータによって保持されるロックは他のデータよりも頻繁に保持されるため、このシナリオではロック分割によるパフォーマンスの向上はそれほど大きくありません。単一のロックに対する競合がボトルネックになった場合、次の典型的な最適化方法は、単一のデータのメタデータ情報のみを更新し、ランダムサンプリングと FIFO ベースの削除戦略を使用してデータ操作を削減することです。これらの戦略により、読み取りパフォーマンスは高くなりますが、書き込みパフォーマンスは低くなり、いつ削除するかを選択することが難しくなります。

もう 1 つの実行可能な解決策は、データベース理論から生まれ、ログを送信することで書き込みパフォーマンスを拡張することです。書き込み操作は、データ構造に直接書き込まれるのではなく、最初にログに記録され、その後バッチで非同期的に実行されます。この考え方はキャッシュに適用でき、ハッシュテーブル操作を実行し、その操作をバッファーに記録してから、適切なタイミングでバッファーの内容を実行します。この戦略では、依然として同期ロックまたは tryLock が必要ですが、違いは、ロックの競合がバッファーへの追加書き込みに転送されることです。

Caffeine には、読み取りと書き込みを記録するために使用される一連のバッファーがあります。アクセスはまず、スレッドごとに異なるストリップされたリングバッファーにハッシュされます。競合が検出されると、バッファは自動的に拡張されます。リングバッファがいっぱいになると、非同期実行がトリガーされ、リングバッファが使用可能になるまで、リングバッファへの後続の書き込みは破棄されます。リングバッファーがいっぱいのためアクセスを記録できませんが、キャッシュされた値は呼び出し元に返されます。 W-TinyLFU は保存したいホットスポットを識別できるため、このポリシー情報の損失は大きな影響を及ぼしません。データ項目のキーをハッシュする代わりにスレッド固有のハッシュアルゴリズムを使用することで、キャッシュは一時的なホットキーの競合問題を回避します。

データを書き込むときは、より従来的な同時実行キューが使用され、各変更は即座に実行されます。データの損失は許容できませんが、書き込みバッファを最適化する方法は数多くあります。すべてのタイプのバッファは複数のスレッドによって書き込まれますが、単一のスレッドによって実行されます。この複数プロデューサー/単一コンシューマーパターンにより、よりシンプルで効率的なアルゴリズムを実装できます。

バッファと細粒度の書き込みにより、個々のデータ項目に対する操作が順序どおりに実行されない競合状態が発生します。挿入、読み取り、更新、削除はすべてさまざまな順序で再生される可能性があり、この戦略が適切に制御されていない場合は、ぶら下がりインデックスが発生する可能性があります。解決策は、ステートマシンを介して単一のデータ項目のライフサイクルを定義することです。

ベンチマークでは、ハッシュテーブルが大きくなるにつれてバッファも大きくなり、その使用は比較的リソース効率が高くなります。読み取りパフォーマンスは CPU コアの数に応じて直線的に増加し、ハッシュテーブルスループットの 33% になります。ハッシュテーブルの更新時の競合が主なオーバーヘッドであるため、書き込みのパフォーマンスが 10% 低下します。

カフェイン

例えば

MySQL キャッシュプールの内部実装は LRU ですが、その中に最後の 3/8 を指す中間ポイントがあり、その半分は古い領域で、残りの半分は新しい領域です。新しいデータは新しい領域に直接挿入されるため、実際の古いデータがフラッシュされるのを防ぎます。

多段キュー形式

LFU はこの特性と頻度を組み合わせて、キャッシュされたデータが将来使用されるかどうかをより正確に予測します。

ただし、従来の LFU には制限があります。

LFU の実装には、大規模で複雑なメタデータ (頻度統計など) の維持が必要です。

ほとんどの実際のワークロードでは、アクセス頻度は時間の経過とともに急激に変化し、従来の LFU では頻度を定期的に低下させることができません。

従来の LFU 実装では、外部の HashMap を接続して頻度をカウントしますが、HashMap にはハッシュの競合があり、頻度の統計が不正確になります。

これらの問題を解決するために、Caffeine は不正確な周波数統計とアクセス周波数減衰の問題を解決できる新しいアルゴリズム W-TinyLFU を提案します。このアプローチにより、行列の長さと幅を調整することで、スペース、効率、およびハッシュ衝突のエラー率の間でトレードオフを行うことができます。

従来のハッシュにはハッシュ競合の問題があります。 LFU アルゴリズムを使用して頻度を記録する場合、ハッシュの競合が発生すると、頻度の統計エラーが発生する可能性があります。

W-TinyLFU アルゴリズムは、Bloom フィルターと同様に、Count-Min Sketch を使用して大規模なメンテナンススペースの問題を解決し、競合の可能性を減らします。原理としては、複数のハッシュを分散させて、その最小値を頻度としてとらえるというものです。ハッシュの競合の確率が 1% の場合、ハッシュが 4 つの場合の確率は 1% の 4 乗となり、競合の可能性が大幅に減少します。

Caffeine に Count-Min Sketch を実装するために、村政府に 4 つのアルゴリズムを保存します。

ここで、randomSeed は乱数、sampleSize = 最初に設定された最大キャッシュツリー * 10。テーブル = 最大キャッシュ番号に最も近い 2 の累乗 (100 は 128、50 は 64)。テーブルマスク = テーブルの長さ-1;サイズ=0

データをキャッシュに入れるときに呼び出されます

この AddTask は Runnable であり、run メソッドが increment メソッドを呼び出します。

カフェインはグアバよりも優れているのでしょうか?

W-TinyLFU

従来の LFU は期間によって大きく影響されます。そのため、減衰期間、または最近の期間における頻度に基づいて、さまざまな LFU バリアントが出現しました。同様に、LFU は、データがキャッシュ内にない場合でも、各データアクセスの頻度を記録するために追加のスペースを使用するため、維持するために必要な追加のスペースは非常に大きくなります。

このメンテナンススペース用に hashMap を作成し、各データ項目がこの hashMap 内に存在すると想像できます。データ量が特に多い場合、この hashMap も特に大きくなります。

LRU に戻ると、LRU はまったく役に立たないわけではありません。 LRU はデータ頻度を蓄積する必要がないため、バーストトラフィックに非常にうまく対応できます。

したがって、W-TinyLFU は、LRU と LFU の機能に加え、他のいくつかのアルゴリズムも組み合わせています。

周波数記録

まず最初にお話しするのは、周波数記録の問題についてです。私たちの目標は、限られたスペースを使用して、時間の経過とともに変化するアクセス頻度を記録することです。 W-TinyLFU では、アクセス頻度を記録するために Count-Min Sketch を使用します。これも Bloom フィルターのバリエーションです。

値を記録する必要がある場合は、複数のハッシュアルゴリズムで処理し、対応するハッシュアルゴリズムのレコードに +1 を追加する必要があります。なぜ複数のハッシュアルゴリズムが必要なのでしょうか?これは圧縮アルゴリズムなので、競合は必ず発生します。たとえば、Long の配列を作成し、各データのハッシュ位置を計算します。たとえば、Zhang SanとLi Siは1などの同じハッシュ値を持つ場合があります。その場合、Long[1]ポジションの頻度はそれに応じて増加します。張三は1万回訪問し、李斯は1回訪問した。すると龍[1]は10,000と1になります。李斯の訪問率を取ると10,001が取り出されますが、李斯は一度しか訪問していません。この問題を解決するために、複数のハッシュアルゴリズムが使用されますが、これは long[][] 2次元配列の概念として理解できます。たとえば、最初のアルゴリズムでは、張三と李思は競合しますが、2 番目と 3 番目のアルゴリズムでは競合しない可能性が高くなります。たとえば、1 つのアルゴリズムの競合の確率が 1% の場合、4 つのアルゴリズムが競合する確率は 1% の 4 乗になります。このモデルを通じて、Li Si のアクセスレートを取得する場合、すべてのアルゴリズムの中で Li Si が最も低い頻度で訪問する回数を取得します。だから彼の名前はカウントミンスケッチです。

簡単な例を使って、前の例との比較を示します。この頻度を記録するために hashMap を使用する場合、データが 100 個あるとすると、この HashMap にはこのデータの 100 個のアクセス頻度を保存する必要があります。キャッシュの容量が 1 であっても、Lfu ルールにより、100 個のデータすべてのアクセス頻度を記録する必要があります。もっとデータがあれば、もっと記録できたでしょう。

Count-Min Sketchでは、caffeine（FrequencySketchクラス）での実装について直接説明します。キャッシュサイズが 100 の場合、100 に最も近い 2 の累乗、つまり 128 のサイズの長い配列が生成されます。この配列はアクセス頻度を記録します。 caffeine では、最大周波数は 15 と指定されています。15 の 2 進数は 1111 で、合計 4 ビットですが、Long 型は 64 ビットです。したがって、各 Long 型は 16 個のアルゴリズムを保持できますが、Caffeine ではこれは実行されません。使用するハッシュアルゴリズムは 4 つだけです。各 Long タイプは 4 つのセグメントに分かれており、各セグメントには 4 つのアルゴリズムの頻度が格納されます。これを行う利点は、ハッシュの競合をさらに減らすことができることです。元のハッシュサイズ 128 は 128X4 になります。

Long の構造は次のとおりです。

私たちの 4 つのセグメントは A、B、C、D に分かれており、後でそのように呼ぶことにします。各セグメントの 4 つのアルゴリズムを s1、s2、s3、s4 と呼びます。例を見てみましょう。デジタル周波数 50 を追加したい場合はどうすればよいでしょうか?例としてsize=100を使用します。

まず、ハッシュ 50 がどのセグメントにあるかを判断します。ハッシュ & 3 (2 進数の 3 は 11) を使用すると、4 未満の数値を確実に取得できます。ハッシュ & 3 = 0 と仮定すると、セグメント A にあります。
50 のハッシュは、他のハッシュアルゴリズムを使用して再度ハッシュされ、長い配列の位置、つまり長さ 128 の配列内の位置が取得されます。s1 アルゴリズムが 1、s2 アルゴリズムが 3、s3 アルゴリズムが 4、s4 アルゴリズムが 0 を取得するとします。
S1アルゴリズムは1を取得するため、long[1]のAセグメントのs1の位置に1を加算し（1As1プラス1と呼ばれる）、3As2に1を加算し、4As3に1を加算し、0As4に1を加算します。

このとき、最大頻度が 15 というのは少なすぎるのではないかという疑問を抱く人もいるかもしれません。それは問題ではありません。このアルゴリズムでは、たとえば、サイズが 100 の場合、サイズ * 10、つまり 1000 回グローバルに増加されると、グローバルに 2 で割られて減少します。崩壊後も増加し続ける可能性があります。このアルゴリズムは、期間のアクセス頻度に適応しやすいことが W-TinyLFU 論文で証明されています。

読み取りおよび書き込みパフォーマンス

グアバキャッシュでは、読み取りおよび書き込み操作が有効期限の処理と混在していると述べました。つまり、Put 操作で削除操作も実行できるため、読み取りおよび書き込みのパフォーマンスがある程度影響を受けます。上の図からわかるように、読み取りおよび書き込み操作では、caffeine は確かに guava キャッシュよりも優れています。これは主に、Caffeine ではこれらのイベントの操作が非同期操作によって行われ、イベントがキューに送信されるためです。ここでのキューのデータ構造は RingBuffer です。よくわからない場合は、この記事を読んで、知っておくべき高性能なロックフリーキュー Disruptor を確認してください。次に、デフォルトの ForkJoinPool.commonPool() または自己構成されたスレッドプールを使用してキュー操作が実行され、その後、後続の削除および有効期限切れ操作が実行されます。

もちろん、読み取り用と書き込み用ではキューが異なります。 Caffeine では、キャッシュの読み取りは書き込みよりもずっと重要であると考えられているため、書き込み操作ではすべてのスレッドがリングバッファーを共有します。

読み取り操作は書き込み操作よりも頻繁に行われるため、競合をさらに減らすために、各スレッドに RingBuffer が構成されます。

データ除去戦略

caffeine では、すべてのデータは ConcurrentHashMap に格納されます。これは、ConcurrentHashMap に似た構造を実装する guava cache とは異なります。 Caffeine にはレコード参照用の LRU キューが 3 つあります。

Eden キュー: カフェインでは、キャッシュ容量の %1 までしか使用できないと規定されています。サイズが 100 の場合、このキューの有効サイズは 1 になります。このキューは、以前のアクセス頻度の不足によりバーストトラフィックが排除されるのを防ぐために、新しく到着したデータを記録します。例えば、新しいドラマがスタートしたとき、実は最初はアクセス頻度がゼロなんです。オンラインになった後に他のキャッシュによって削除されないように、この領域に追加されます。他のデータによって排除されにくい、最も快適で平和なエリアであるエデン地区。
試用キュー: 試用キューと呼ばれます。このキューに入っているということは、データが比較的冷たく、すぐに削除されることを意味します。有効なサイズは、size から eden と protected を引いたサイズです。
保護されたキュー: このキューでは、当面は排除されないので安心です。しかし、心配しないでください。試用キューにデータがない場合や保護キューがいっぱいの場合は、排除されるという恥ずかしい状況に直面することになります。もちろん、このキューになりたい場合は、試用キューを一度訪問する必要があり、その後、保護キューに昇格されます。有効サイズは（サイズからエデンを引いた値）×80%です。サイズ = 100 の場合は 79 になります。

これら 3 つのキューの関係は次のとおりです。

すべての新しいデータは Eden に送られます。
エデンは満員となり、プレイヤーは脱落し、仮釈放となります。
保護観察期間中にデータにアクセスした場合、そのデータは保護対象にアップグレードされます。
保護がいっぱいになった場合は、保護期間が保護期間にダウングレードされます。

データの削除が発生すると、保護観察から削除されます。このキュー内のデータキューの先頭は、犠牲者と呼ばれます。このキューの先頭の人が最初に入場する必要があります。 LRU キューアルゴリズムによれば、彼は排除されるはずですが、ここでは犠牲者としか呼べません。この待ち行列は執行猶予付きの待ち行列であり、つまり彼はもうすぐ処刑されることになる。キューの最後にいる人は候補者と呼ばれ、攻撃者とも呼ばれます。ここで被害者は攻撃者と競争し、どちらが排除されるかを決定します。

Count-Min Sketch に記録された頻度データから、次のような判断が得られます。