適応型置換キャッシュ

適応型置換キャッシュ（ARC）は、LRU（最も最近使われていないページ）よりも優れたパフォーマンスを発揮するページ置換アルゴリズムです^[1] 。これは、頻繁に使用されるページと最近使用されたページの両方を追跡し、両方の最近の削除履歴を保持することで実現されます。このアルゴリズムは、 IBMアルマデン研究センターで開発されました^[2]。2006年に、IBMは適応型置換キャッシュポリシーの特許を取得しました。

基本的な LRU は、キャッシュ内のリソース エントリの順序付きリスト (キャッシュ ディレクトリ) を管理します。このリストの並び順は、最新のアクセス時刻に基づきます。新しいエントリは、一番下のエントリが削除された後、リストの一番上に追加されます。キャッシュ ヒットは一番上に移動し、他のすべてのエントリは下に押し下げられます。

ARC は、キャッシュ ディレクトリを最近参照されたエントリと頻繁に参照されるエントリの 2 つのリスト (T1 と T2) に分割することで、基本的な LRU 戦略を改良します。次に、これらの各リストは、2 つのリストの下部にアタッチされたゴーストリスト (B1 または B2) で拡張されます。これらのゴーストリストは、最近削除されたキャッシュ エントリの履歴を追跡することでスコアカードとして機能し、アルゴリズムはゴーストヒットを使用して、リソース使用の最近の変更に適応します。ゴーストリストにはメタデータ (エントリのキー) のみが含まれ、リソース データ自体は含まれないことに注意してください。つまり、エントリがゴーストリストに削除されると、そのデータは破棄されます。結合されたキャッシュ ディレクトリは、4 つの LRU リストに編成されます。

1. T1、最近のキャッシュエントリ用。
2. T2 は、頻繁に参照されるエントリで、少なくとも 2 回参照されます。
3. B1、ゴーストエントリは最近 T1 キャッシュから削除されましたが、まだ追跡されています。
4. B2、同様のゴーストエントリですが、T2 から排除されています。

T1 と B1 を合わせて L1 と呼びます。これは、最近の単一参照の結合履歴です。同様に、L2 は T2 と B2 の組み合わせです。

キャッシュ ディレクトリ全体を 1 行で視覚化できます。

. . . [    B1 <- [      T1 <- ! -> T2    ] -> B2    ] . .
       [ . . . . [ . . . . . . ! . . ^ . . . . ] . . . . ] 
                [   固定キャッシュサイズ (c)     ]

内側の[ ]括弧は実際のキャッシュを示します。サイズは固定されていますが、B1 および B2 履歴間で自由に移動できます。

L1 は、上から始めて右から左へ表示され、!マーカーで示されます。 ^ はT1 のターゲット サイズを示し、実際のサイズと等しいか、それより小さいか、または大きい場合があります ( !で示されます)。

• 新しいエントリは!の左側の T1 に入り、徐々に左に押し出され、最終的に T1 から B1 に追い出され、最終的に完全に削除されます。
• L1 内のエントリがもう一度参照されると、もう一度チャンスが与えられ、中央の!マーカーのすぐ右側の L2 に入ります。そこから、エントリは再び外側に押し出され、T2 から B2 に入ります。もう一度ヒットした L2 内のエントリは、これを無期限に繰り返すことができ、最終的に B2 の右端でドロップアウトします。

エントリがキャッシュ (T1、T2) に (再) 入ると、!がターゲット マーカー^に向かって移動します。キャッシュに空き領域がない場合、このマーカーによって、T1 または T2 のどちらがエントリを削除するかが決まります。

• B1 のヒットにより T1 のサイズが増加し、^が右に押し出されます。T2 の最後のエントリは B2 に追い出されます。
• B2 のヒットにより T1 が縮小され、^が左に押し戻されます。T1 の最後のエントリは B1 に追い出されます。
• キャッシュ ミスは^ には影響しませんが、!境界は^に近づきます。

ARC は現在、IBM の DS6000/ DS8000ストレージ コントローラに導入されています。

Sun MicrosystemsのスケーラブルファイルシステムZFS は、仮想メモリ内の従来のSolarisファイルシステムのページキャッシュの代替として、ARC のバリアント^[3]を使用します。これは、現在使用中で空けることができないロックされたページを許可するように変更されています。

PostgreSQLはバッファマネージャでARCを短期間使用していました（バージョン8.0.0）が、ARCに関するIBMの特許に関する懸念を理由に、すぐに別のアルゴリズムに置き換えました。^[4]

VMwareのvSAN（旧称Virtual SAN）は、VMwareが開発したハイパーコンバージドのソフトウェア定義ストレージ（SDS）製品です。キャッシュアルゴリズムにはARCの一種が使用されています。^[5]

OpenZFS は、読み取りキャッシュとしてマルチレベル キャッシュの ARC と L2ARC の使用をサポートしています。OpenZFS では、ディスク読み取りは ARC を使用して RAM 内の第 1 レベルのディスク キャッシュにヒットすることがよくあります。SSD が第 2 レベルのディスク キャッシュを格納するように設定されている場合、それは L2ARC と呼ばれます。L2ARC は同じ ARC アルゴリズムを使用しますが、キャッシュされたデータを RAM に格納する代わりに、L2ARC はキャッシュされたデータを高速 SSD に格納します。^{[6] [7] [8] [9] [10] [11]}

• 適応型置換機能付き時計
• LIRS キャッシュアルゴリズム

• ARC: 自己チューニング、低オーバーヘッドの置換キャッシュ (2003)、Nimrod Megiddo、Dharmendra Modha 著
• Linux メモリ管理 Wiki
• ブルボネ、ロック。 ZFS ダイナミクス
• Python 実装、レシピ 576532
• LRU、ARCなどの比較