キャッシュ置換ポリシー

このアルゴリズムでは、キャッシュはFIFOキューのように動作します。つまり、ブロックが追加された順序でブロックが追い出され、それ以前にどれだけ頻繁にアクセスされたか、あるいは何回アクセスされたかは関係ありません。

キャッシュはスタックのように動作し、FIFOキューとは異なります。キャッシュは、過去にどれだけ頻繁にアクセスされたか、あるいはアクセス回数に関係なく、最も最近追加されたブロックを最初に追い出します。

SIEVE は、キーバリュー キャッシュやコンテンツ配信ネットワークなどの Web キャッシュ向けに特別に設計されたシンプルな削除アルゴリズムです。遅延昇格と高速降格の考え方を使用しています。^{[ 5 ]}そのため、SIEVE はキャッシュヒット時にグローバルデータ構造を更新せず、削除時まで更新を遅延させます。一方、キャッシュワークロードはワンヒットワンダー率が高くなる傾向があり、新しいオブジェクトのほとんどはキャッシュに保持する価値がないため、新しく挿入されたオブジェクトを迅速に削除します。SIEVE は単一の FIFO キューを使用し、移動ハンドを使用して削除するオブジェクトを選択します。キャッシュ内のオブジェクトには、キャッシュに受け入れられた後にオブジェクトが要求されたかどうかを示す 1 ビットのメタデータがあります。削除ハンドは最初はキューの末尾を指し、時間の経過とともに先頭に向かって移動します。CLOCK 削除アルゴリズムと比較すると、SIEVE で保持されたオブジェクトは古い位置に留まります。そのため、新しいオブジェクトは常に先頭にあり、古いオブジェクトは常に末尾にあります。手が頭の方へ移動すると、新しい物体はすぐに追い出されます（迅速な降格）。^{[ 6 ]}

最も使用頻度の低いアイテムから順に破棄します。このアルゴリズムでは、何がいつ使用されたかを追跡する必要があり、煩雑です。キャッシュラインに「エイジビット」が必要で、これらのエイジビットに基づいて最も使用頻度の低いキャッシュラインを追跡します。キャッシュラインが使用されると、他のキャッシュラインのエイジが変更されます。LRUは、 Theodore JohnsonとDennis Shashaによる2Q ^{[ 7 ]}やPat O'Neil、Betty O'Neil、Gerhard WeikumによるLRU/K ^{[ 8 ]}などを含む、キャッシュアルゴリズムのファミリーです。例のアクセスシーケンスはABCDEDFです。

ABCD がシーケンス番号 (新しいアクセスごとに 1 増加) を持つブロックにインストールされ、E にアクセスすると、ミスとなり、ブロックにインストールする必要があります。LRU アルゴリズムでは、A のランクが最も低い (A(0)) ため、E が A を置き換えます。最後から 2 番目のステップでは、D にアクセスしてシーケンス番号を更新します。次に F にアクセスし、ランクが最も低い (B(1)) B を置き換えます。 

時間認識型、最も最近使用されていないもの（TLRU）^{[ 9 ]}は、キャッシュの内容に有効な有効期限がある場合に設計されたLRUの派生形です。このアルゴリズムは、情報中心型ネットワーク（ICN）、コンテンツ配信ネットワーク（CDN）、および一般的な分散ネットワークなどのネットワークキャッシュアプ​​リケーションに適しています。TLRUでは、TTU（使用時間）という用語が導入されています。これは、コンテンツのローカルとコンテンツの発行者に基づいて、コンテンツの使用可能時間を規定するコンテンツ（またはページ）のタイムスタンプです。TTUにより、ローカル管理者はネットワークストレージを制御する際に、より多くの制御が可能になります。

TLRUの対象となるコンテンツが到着すると、キャッシュノードはコンテンツ発行元によって割り当てられたTTUに基づいてローカルTTUを計算します。ローカルTTU値は、ローカルで定義された関数を使用して計算されます。ローカルTTU値が計算されると、キャッシュノードの全コンテンツの一部に対してコンテンツ置換が実行されます。TLRUは、人気のないコンテンツや寿命の短いコンテンツが、受信したコンテンツで確実に置き換えられるようにします。

LRUとは異なり、MRUは最も最近使用されたアイテムを最初に破棄します。第11回VLDB会議で、ChouとDeWittは次のように述べています。「ファイルが[ループシーケンシャル]参照パターンで繰り返しスキャンされている場合、MRUは最適な置換アルゴリズムです。」^{[ 10 ]}第22回VLDB会議で発表した研究者らは、ランダムアクセスパターンと大規模データセットに対する繰り返しスキャン（循環アクセスパターンとも呼ばれる）の場合、MRUキャッシュアルゴリズムは古いデータを保持する傾向があるため、LRUよりもヒット数が多いと指摘しました。^{[ 11 ]} MRUアルゴリズムは、アイテムが古いほどアクセスされる可能性が高い状況で最も役立ちます。例のアクセスシーケンスはABCDECDBです。

空きスペースがあるため、ABCDはキャッシュに格納されます。5回目のアクセス（E）では、Dが格納されていたブロックが、最後に使用されたブロックであるEに置き換えられます。次のアクセス（Dへのアクセス）では、Dの直前にアクセスされたブロックであるCが置き換えられます。

SLRU キャッシュは、プロベーショナリー セグメントとプロテクテッド セグメントの 2 つのセグメントに分割されます。各セグメントのラインは、最も最近アクセスされたものから最も最近アクセスされていないものへと順序付けられます。ミスのデータは、プロベーショナリー セグメントの最も最近アクセスされた端のキャッシュに追加されます。ヒットは、その存在場所から削除され、プロテクテッド セグメントの最も最近アクセスされた端に追加されます。プロテクテッド セグメントのラインは、少なくとも 2 回アクセスされています。プロテクテッド セグメントは有限です。プロベーショナリー セグメントからプロテクテッド セグメントへのラインの移動は、プロテクテッド セグメントの LRU ラインをプロベーショナリー セグメントの最も最近使用された端に移動させ、このラインが置き換えられる前にもう一度アクセスされる機会を与えます。プロテクテッド セグメントのサイズ制限は、I/Oワークロード パターンに応じて変化する SLRU パラメータです。キャッシュからデータを破棄する必要がある場合、プロベーショナリー セグメントの LRU 端からラインが取得されます。^{[ 12 ]}

LRU（Least Recently Used：最小更新回数）方式は、アソシアティビティの高いキャッシュではコストが高くなる可能性がある。実際のハードウェアでは、より低いハードウェアコストで同等の性能を実現するために、通常は近似的な手法が用いられる。

擬似LRU（PLRU）

連想度が高い（一般的に4ウェイ以上） CPUキャッシュの場合、LRUの実装コストは法外なものになります。多くのCPUキャッシュでは、使用頻度が最も低いアイテムをほぼ常に破棄するアルゴリズムで十分です。多くのCPU設計者は、キャッシュアイテムごとに1ビットしか必要としないPLRUアルゴリズムを選択します。PLRUは通常、LRUよりもミス率がわずかに悪く、レイテンシがわずかに優れ、消費電力がわずかに少なく、オーバーヘッドもLRUより低くなっています。

ビットは、使用頻度の低いサブツリーを指す1ビットポインタのバイナリツリーとして機能します。ポインタチェーンをたどってリーフノードに到達すると、置換候補が特定されます。アクセスが行われると、アクセスされたパスのリーフノードからルートノードまでのチェーン内のすべてのポインタが、アクセスされたパスを含まないサブツリーを指すように設定されます。例のアクセスシーケンスはABCDEです。

値（例えばA）にアクセスでき、それがキャッシュに存在しない場合、メモリからロードされ、例の矢印が指しているブロックに配置されます。そのブロックが配置されると、矢印は反転して反対方向を指すようになります。A、B、C、Dが配置され、キャッシュがいっぱいになると、矢印が指していたEがAに置き換わります。そして、Aにつながる矢印は反転して反対方向（次のキャッシュミスで置き換えられるブロックであるB）を指すようになります。

LFUアルゴリズムは、アイテムが必要とされる頻度をカウントし、使用頻度の低いアイテムから順に破棄します。これはLRUと似ていますが、ブロックへのアクセス回数が保存されるのに対し、アクセス頻度は最近ではなく、過去に何回アクセスされたかが記録されます。アクセスシーケンスの実行中、最も使用頻度の低いブロックがキャッシュから削除されます。

最近最も使用頻度の低い (LFRU) ^{[ 16 ]}アルゴリズムは、LFU と LRU の利点を組み合わせたものです。LFRU は、ICN、CDN、および一般的な分散ネットワークなどのネットワーク キャッシュ アプリケーションに適しています。LFRU では、キャッシュは特権パーティションと非特権パーティションの 2 つのパーティションに分割されます。特権パーティションは保護されており、コンテンツが人気がある場合は、特権パーティションにプッシュされます。特権パーティションを置き換える際、LFRU は非特権パーティションからコンテンツを追い出し、特権パーティションから非特権パーティションにコンテンツを押し込み、新しいコンテンツを特権パーティションに挿入します。特権パーティションには LRU が使用され、非特権パーティションには近似 LFU (ALFU) アルゴリズムが使用されます。

動的エイジング付き LFU (LFUDA) というバリアントは、動的エイジングを使用して、人気のあるオブジェクトのセットの変動に対応します。新しいオブジェクトがキャッシュに追加されるか、既存のオブジェクトが再参照されるときに、参照カウントにキャッシュ年齢係数を追加します。 LFUDA は、ブロックを追い出すときに、追い出されたオブジェクトのキー値に設定することでキャッシュ年齢をインクリメントし、キャッシュ年齢は常にキャッシュ内の最小キー値以下になります。^{[ 17 ]}オブジェクトが過去に頻繁にアクセスされ、人気がなくなった場合、長期間キャッシュに残ります (新しく、または人気のないオブジェクトがそれを置き換えるのを防ぎます)。動的エイジングは、そのようなオブジェクトの数を減らし、置き換えの対象にします。また、キャッシュが小さい場合、LFUDA は LFU によって引き起こされるキャッシュ汚染を減らします。

これは、2023 年に設計された新しい削除アルゴリズムです。既存のアルゴリズムは主に LRU (最も最近使用されていないもの) をベースにしていますが、S3-FIFO は 3 つの FIFO キューのみを使用します。キャッシュ スペースの 10% を占める小さなキュー、キャッシュ スペースの 90% を使用するメイン キュー、およびオブジェクトのメタデータのみを格納するゴースト キューです。小さなキューは、ワンヒットワンダー (短時間で 1 回しかアクセスされないオブジェクト) をフィルタリングするために使用されます。メイン キューは、よく使用されるオブジェクトを格納するために使用され、再挿入を使用してキャッシュに保持されます。ゴースト キューは、小さなキューから削除された、よく使用される可能性のあるオブジェクトをキャッチするために使用されます。オブジェクトは最初に小さなキューに挿入されます (ゴースト キューに見つからない場合、見つかった場合はメイン キューに挿入されます)。小さなキューから削除された場合、オブジェクトが要求されている場合はメイン キューに再挿入され、そうでない場合は削除され、メタデータがゴースト キューで追跡されます。^{[ 18 ]}

RRIP ^{[ 20 ]}は、 Intelが提案した柔軟なポリシーで、再利用されていない古いキャッシュ ラインをエビクトすることを許可しながら、優れたスキャン耐性を提供しようとします。すべてのキャッシュ ラインには、ラインが再利用されると予想されるタイミングと相関する予測値 RRPV (再参照予測値) があります。RRPV は通常、挿入時に高くなります。ラインがすぐに再利用されない場合、スキャン (一度だけ使用される大量のデータ) がキャッシュを埋め尽くすのを防ぐために、ラインはエビクトされます。キャッシュ ラインが再利用されると、RRPV はゼロに設定され、ラインが一度再利用され、再び再利用される可能性が高いことを示します。

キャッシュミスが発生した場合、RRPVが最大可能な値に等しい行が追い出されます。3ビット値の場合、RRPVが2³ ^- 1 = 7の行が追い出されます。この値を持つ行がない場合は、いずれかの行がこの値に達するまで、セット内のすべてのRRPVが1ずつ増加されます。同値の場合は、通常は左端の最初の行が決定されます。この増加は、古い行が適切に経過し、再利用されない場合は追い出されることを保証するために必要です。

Hawkeye ^{[ 19 ]}は、PC による過去のアクセスを利用して、生成されるアクセスがキャッシュフレンドリー (後で使用される) アクセスかキャッシュアウェア (後で使用される) アクセスかを予測することで、Bélády のアルゴリズムを模倣しようとしています。これは、アラインメントされていないキャッシュ セットを複数サンプリングし、長さの履歴を使用します。$キャッシュサイズの 8 倍$そして、これらのアクセスに対してベラディのアルゴリズムをエミュレートします。これにより、ポリシーはどのラインをキャッシュすべきか、どのラインをキャッシュすべきでないかを決定し、命令がキャッシュフレンドリーかキャッシュアバージョンかを予測できます。このデータは次に RRIP に渡されます。キャッシュフレンドリーな命令からのアクセスは RRPV 値が低く (後で追い出される可能性が高い)、キャッシュアバージョン命令からのアクセスは RRPV 値が高く (より早く追い出される可能性が高い) なります。RRIP バックエンドが追い出しの決定を行います。サンプリングされたキャッシュとOPTジェネレータは、挿入されたキャッシュラインの初期 RRPV 値を設定します。Hawkeye は 2017 年に CRC2 キャッシュ選手権で優勝し^{[ 23 ]} 、 Harmony ^{[ 24 ]}はプリフェッチのパフォーマンスを向上させる Hawkeye の拡張です。

Mockingjay ^{[ 25 ]}は、いくつかの点で Hawkeye を改良しようとしています。バイナリ予測を廃止し、どのキャッシュラインを追い出すかについてよりきめ細かな決定を下せるようにし、より多くの情報が利用可能になったときにどのキャッシュラインを追い出すかの決定を保留します。

Mockingjayは、一意のアクセス、それらを生成したPC、およびそれらのタイムスタンプのサンプリングされたキャッシュを保持します。サンプリングされたキャッシュ内の行が再度アクセスされると、時間差が再利用距離予測器に送信されます。RDPは時間差学習^{[ 26 ]}を使用し、外れ値を補正するために新しいRDP値が小さな数値だけ増減されます。数値は次のように計算されます。${\displaystyle w=\min \left(1,{\frac {\text{タイムスタンプの差}}{16}}\right)}$値が初期化されていない場合は、観測された再利用距離が直接挿入されます。サンプリングされたキャッシュがいっぱいで、行を破棄する必要がある場合は、最後にアクセスしたPCがストリーミングアクセスを生成するようにRDPに指示されます。

アクセスまたは挿入が発生すると、この行の推定再利用時間（ETR）が更新され、予測される再利用距離が反映されます。キャッシュミスが発生すると、ETR値が最も高い行が削除されます。Mockingjayは、最適なBéládyアルゴリズムに近い結果を示しています。

LIRSは、LRUや他の新しい置換アルゴリズムよりも優れたパフォーマンスを持つページ置換アルゴリズムです。再利用距離は、置換決定を行うためにアクセスされたページを動的にランク付けするための指標です。^{[ 31 ]} LIRSは、置換決定を行うために相互参照の最新性（IRR）を評価するために最新性を使用することで、LRUの限界に対処します。

図では、X はブロックが特定の時間にアクセスされたことを示します。ブロック A1 が時間 1 でアクセスされた場合、その最新性は 0 になります。これは最初にアクセスされたブロックであり、IRR は 1 になります。これは、A1 が時間 3 で再びアクセスされると予測されるためです。時間 2 では、A4 がアクセスされるため、最新性は A4 で 0、A1 で 1 になります。A4 は最も最近アクセスされたオブジェクトであり、IRR は 4 になります。時間 10 では、LIRS アルゴリズムは 2 つのセットを持ちます。LIR セット = {A1, A2} と HIR セット = {A3, A4, A5} です。時間 10 で A4 へのアクセスがあった場合、ミスが発生します。LIRS は、A2 よりも最新性が高い A5 を排除します。

適応型置換キャッシュ（ARC）は、LRUとLFUのバランスを常に調整して、総合的な結果を改善します。^{[ 32 ]}最近追い出されたキャッシュ項目の情報を使用して、保護セグメントと試用セグメントのサイズを調整し、利用可能なキャッシュスペースを最大限に活用することで、SLRUを改善します。^{[ 33 ]}

適応型置換機能付きクロック（CAR）は、ARCとクロックの利点を兼ね備えています。CARはARCと同等の性能を発揮し、LRUやクロックよりも優れた性能を示します。ARCと同様に、CARは自己調整機能を備えており、ユーザーによるパラメータ指定は不要です。

マルチキュー置換（MQ）アルゴリズムは、サーババッファキャッシュなどの第2レベルバッファキャッシュのパフォーマンスを向上させるために開発され、Zhou、Philbin、およびLiによる論文で紹介されました。^{[ 34 ]} MQキャッシュには、 m個のLRUキューQ0 _、 Q1 _、 ...、Qm _{- 1が含まれています。m}の値は、そのキュー内のすべてのブロックの寿命に基づく階層を表します。^{[ 35 ]}

Pannier ^{[ 36 ]}は、可変アクセスパターンを持つブロックのコンテナを識別するコンテナベースのフラッシュキャッシングメカニズムです。Pannier は、コンテナ内のライブデータに比例する生存時間に基づいてコンテナをランク付けする優先度キューベースの生存キュー構造を備えています。