キャッシュ置換ポリシー

Bélády’s algorithmEdit

最も効率的なキャッシュアルゴリズムは、将来最も長く必要とされない情報を常に破棄することです。 この最適な結果は、Bélády’s optimal algorithm/simply optimal replacement policyまたは千里眼アルゴリズムと呼ばれます。 将来の情報がどこまで必要とされるかを予測することは一般的に不可能であるため、これは一般的に実際には実装できません。 実用的な最小値は実験の後にのみ計算でき、実際に選択されたキャッシュアルゴリズムの有効性を比較することができます。

ページフォールトが発生した時点で、いくつかのページセットがメモリ内にあります。 この例では、次のシーケンスを使用しています。’5′, ‘0’, ‘1’ フレーム1、フレーム2、フレーム3によってそれぞれアクセスされます。 次に、’2’にアクセスすると、値’5’が近い将来にアクセスされないと予測されるため、フレーム1にある値’5’が置き換えられます。 実際の汎用オペレーティングシステムでは、’5’がいつアクセスされるかを実際に予測することはできないため、Béládyのアルゴリズムはそのようなシステムに実装することはできません。

First in first out(FIFO)Edit

このアルゴリズムを使用すると、キャッシュはFIFOキューと同じように動作します。 キャッシュは、以前にアクセスされた頻度や回数に関係なく、ブロックを追加された順序で削除します。

Last in first out(LIFO)またはFirst in last out(FILO)Edit

このアルゴリズムを使用すると、キャッシュはスタックと同じように動作し、FIFOキューとは正反対の動作をします。 キャッシュは、直前に追加されたブロックを、以前にアクセスされた頻度や回数に関係なく、最初に削除します。

最近使用されていない項目(LRU)Edit

最近使用されていない項目を最初に破棄します。 このアルゴリズムは、いつ使用されたかを追跡する必要があり、アルゴリズムが常に最も最近使用された項目を破棄するようにしたい場合は高価です。 この手法の一般的な実装では、キャッシュラインに”age bits”を保持し、age-bitsに基づいて”最も最近使用された”キャッシュラインを追跡する必要があります。 このような実装では、キャッシュラインが使用されるたびに、他のすべてのキャッシュラインの経過時間が変更されます。 LRUは実際には、Theodore JohnsonとDennis Shashaによる2Q、Pat O’Neil、Betty O’Neil、Gerhard WeikumによるLRU/Kなどのメンバーを含むキャッシュアルゴリズムのファミリーです。

以下の例のアクセスシーケンスはA B C D E D Fです。

上記の例では、A B C Dがシーケンス番号（新しいアクセスごとに増分1）を持つブロックにインストールされ、Eがアクセスされると、それはミスであり、ブロックのいずれかにインストールする必要があります。 LRUアルゴリズムによれば、Aのランクが最も低い(A(0))ので、EはAを置き換えます。

最後の2番目のステップでDがアクセスされ、シーケンス番号が更新

LRUは、他の多くの置換ポリシーと同様に、ベクトル空間内の状態遷移場を使用して特徴付けることができ、電磁場がその中に置かれた荷電粒子の動きをどのように決定するかと同様に、動的キャッシュ状態の変化を決定する。

Time aware Least Recently used(TLRU)Edit

Time aware Least Recently Used(TLRU)は、キャッシュに格納されたコンテンツが有効なライフタイムを持つ状況のために設計されたLRUの変種です。 このアルゴリズムは，情報中心ネットワーク（ＩＣＮ），コンテンツ配信ネットワーク（Ｃｄｎ），分散ネットワークなどのネットワークキャッシュアプリケーションに適している。 TLRUでは、新しい用語TTU（使用時間）が導入されています。 TTUは、コンテンツ/ページのタイムスタンプであり、コンテンツの局所性およびコンテンツ発行者の発表に基づいて、コンテンツのユーザビリティ時間を規定しています。 この地域ベースのタイムスタンプのために、TTUはネットワークストレージを規制するためにローカル管理者により多くの制御を提供します。TLRUアルゴリズムでは、コンテンツの一部が到着すると、キャッシュノードは、コンテンツ発行者によって割り当てられたTTU値に基づいてローカルTTU値を ローカルTTU値は、ローカルで定義された関数を使用して計算されます。 ローカルTTU値が計算されると、キャッシュノードに格納されている合計コンテンツのサブセットでコンテンツの置換が実行されます。 TLRUは、あまり人気がなく、小さな生活のコンテンツが入ってくるコンテンツに置き換える必要があることを保証します。

最近使用された(MRU)編集

LRUとは対照的に、最近使用された項目を最初に破棄します。 第11回VLDB会議で発表された調査結果では、ChouとDeWittは、”ファイルが参照パターンで繰り返しスキャンされている場合、MRUは最良の置換アルゴリズムです。”その後、第22回VLDB会議で発表された他の研究者は、ランダムアクセスパターンと大規模なデータセット（サイクリックアクセスパターンとしても知られてい MRUアルゴリズムは、アイテムが古いほどアクセスされる可能性が高くなる状況で最も便利です。

以下の例のアクセスシーケンスはA B C D E C D Bです。

ここでは、利用可能なスペースがまだあるため、a B C Dがキャッシュに配置されます。 5番目のアクセスEでは、このブロックが最も最近使用されたため、Dを保持していたブロックがEに置き換えられていることがわかります。 Cへの別のアクセスとDへの次のアクセスでは、CはDの直前にアクセスされたブロックと同じように置き換えられます。P>

擬似LRU(PLRU)編集

大きな結合性を持つCPUキャッシュ（一般的に>4つの方法）の場合、LRUの実装コストは法外になります。 多くのCPUキャッシュでは、ほとんどの場合、最も最近使用されていない項目のいずれかを破棄するスキームで十分であるため、多くのCPU設計者は、キャッシPLRUは、通常、わずかに悪いミス比を有し、わずかに良好なレイテンシを有し、LRUよりもわずかに少ない電力を使用し、LRUと比較して低いオーバーヘッドを有する。

次の例は、ビットが最近使用されていないサブツリーを指す1ビットポインタのバイナリツリーとしてどのように機能するかを示しています。 リーフノードへのポインタチェーンに続くと、置換候補が識別されます。 アクセス時には、アクセスされたウェイのリーフノードからルートノードへのチェーン内のすべてのポインタが、アクセスされたウェイを含まないサブツリーを指すように設定されます。

アクセスシーケンスはB C D Eです。

ここでの原則は、矢印ポインタだけを見れば簡単に理解できます。 値へのアクセスがあり、’A’と言うと、キャッシュ内でそれを見つけることができない場合は、メモリからロードし、矢印が現在指しているブロックに上か 我々はそのブロックを配置した後、彼らは反対の方法を指すように、我々はそれらの同じ矢印を反転します。 上記の例では、’A’がどのように配置され、その後に’B’、’C、’D’が続いているかを見ています。 その後、キャッシュがいっぱいになると、矢印がその時を指していた場所であり、’A’につながった矢印が反対方向を指すように反転されたため、’E’が’A’に置き換わりました。 矢印は、次のキャッシュミスで置き換えられたブロックになります’B’につながりました。

ランダム置換（RR）編集

ランダムに候補アイテムを選択し、必要に応じてスペースを作るためにそれを破棄します。 このアルゴリズムは、アクセス履歴に関する情報を保持する必要はありません。 簡単にするために、ARMプロセッサで使用されています。 それは効率的な確率的シミュレーションを認めています。

以下の例のアクセスシーケンスは、B C D E B D F

Segmented LRU(SLRU)Edit

SLRUキャッシュは、保護セグメントと保護セグメントの二つのセグメントに分割され 各セグメント内の行は、最も最近アクセスされた行から最も最近アクセスされた行に順序付けされます。 ミスからのデータは、保護観察セグメントの最後にアクセスされた最後にキャッシュに追加されます。 ヒットは、現在存在する場所から削除され、保護されたセグメントの最後にアクセスされた端に追加されます。 保護されたセグメント内の行は、このように少なくとも二度アクセスされています。 保護されたセグメントは有限であるため、保護されたセグメントから保護されたセグメントへの行の移行は、保護されたセグメント内のLRU行を保 保護されたセグメントのサイズ制限は、I/Oワークロードパターンに従って変化するSLRUパラメータです。 キャッシュからデータを破棄する必要がある場合は常に、行は保護観察セグメントのLRU端から取得されます。

最も頻繁に使用される（LFU）編集

アイテムが必要な頻度をカウントします。 最も頻繁に使用されていないものは、最初に破棄されます。 これはLRUと非常によく似ていますが、ブロックが最近アクセスされた回数の値を格納するのではなく、アクセスされた回数の値を格納します。 だからもちろん、アクセスシーケンスを実行している間、私たちは私たちのキャッシュから最も少ない時間使用されたブロ たとえば、Aが5回使用され（アクセスされた）、Bが3回使用され、他のCとDがそれぞれ10回使用された場合、Bを置き換えます。

最近使用された頻度が最も低い(LFRU)Edit

最近使用された頻度が最も低い(LFRU)キャッシュ置換スキームは、LFUスキームとLRUスキームの利点を兼ね備えています。 LFRUは、情報中心ネットワーク(ICN)、コンテンツ配信ネットワーク(Cdn)、一般的な分散ネットワークなどの”ネットワーク内”キャッシュアプリケーションに適しています。 LFRUでは、キャッシュは特権パーティションと非特権パーティションと呼ばれる2つのパーティションに分割されます。 特権パーティションは、保護されたパーティションとして定義できます。 コンテンツが非常に人気がある場合は、特権パーティションにプッシュされます。 LFRUは、非特権パーティションからコンテンツを削除し、特権パーティションから非特権パーティションにコンテンツをプッシュし、最後に新しいコンテン 上記の手順では、LRUが特権パーティションに使用され、近似LFU（ALFU）スキームが非特権パーティションに使用されるため、略語LFRUが使用されます。

基本的な考え方は、ALFUスキームでローカルで人気のあるコンテンツを除外し、人気のあるコンテンツを特権パーティションのいずれかにプッシュするこ

lfu with dynamic aging(LFUDA)Edit

ダイナミックエイジングを使用して人気のあるオブジェクトのセットのシフトに対応するlfu with Dynamic Aging(LFUDA)と呼ばれるバリアント。 新しいオブジェクトがキャッシュに追加されたとき、または既存のオブジェクトが再参照されたときに、参照カウントにキャッシュ経過係数が追 LFUDAは、ブロックを削除するときに、削除されたオブジェクトのキー値に設定することにより、キャッシュの年齢を増分します。 したがって、キャッシュの有効期間は常にキャッシュ内の最小キー値以下になります。 オブジェクトが過去に頻繁にアクセスされ、今では不人気になったとき、それは長い間キャッシュに残り、それによって新しくまたはあまり人気のな そのため、この動的老化は、そのようなオブジェクトの数を減らすために導入され、それによって交換の対象となります。 LFUDAの利点は、キャッシュサイズが非常に小さいときにLFUによって引き起こされるキャッシュ汚染を減らすことです。 キャッシュサイズが大きい場合は、いくつかの置換の決定で十分であり、キャッシュ汚染は問題になりません。

Low inter-reference recency set(LIRS)Edit

LIRSは、LRUや他の多くの新しい置換アルゴリズムよりもパフォーマンスが向上したページ置換 これは、再利用距離を指標として使用して、アクセスされたページを動的にランク付けして置換決定を行うことによって実現されます。 LIRSは、交換決定を行うための参照間最新性（IRR）を評価するために最新性を使用することによって、LRUの限界に効果的に対処します。上の図では、”x”は、時間tでブロックにアクセスされることを表しています。

上の図では、”x” ブロックA1が時間1でアクセスされた場合、これが最初にアクセスされたブロックであるため、Recencyは0になり、A1が時間3で再びアクセスされる A4がアクセスされてからの時間2では、a4が最も最近アクセスされたオブジェクトであり、IRRが4になり、それが続くため、最近はA4では0、A1では1になります。 時間１ ０において、ＬＩＲＳアルゴリズムは、ＬＩＲセット＝｛Ａ１，Ａ２｝及びＨＩＲセット＝｛Ａ３，Ａ４，Ａ５｝の２つのセットを有する。 10時にA4へのアクセスがある場合、ミスが発生します。 LIRSアルゴリズムは現在、その最大の最新性のためにA5の代わりにA2を立ち退かせます。

CLOCK-ProEdit

LRUアルゴリズムは、オーバーヘッドが高いため、オペレーティングシステムなどのコンピュータシステムのクリティカルパスに直接実装するこ CLOCKと呼ばれるLRUの近似が実装に一般的に使用されます。 同様に、CLOCK-Proは、システムでの低コスト実装のためのLIRSの近似値です。 CLOCK-Proは基本的なCLOCKフレームワークの下にありますが、3つの大きなメリットがあります。 まず、CLOCK-Proは、一つの”手”だけが使用される時計の単純な構造とは対照的に、三つの”時計の手”を持っています。 CLOCK-Proは、三つの針を使用して、おおよその方法でデータアクセスの再利用距離を測定することができます。 第二に、LIRSのすべてのメリットは、ワンタイムアクセスおよび/または低局所性データ項目を迅速に排除するなど、保持されます。 第三に、CLOCK-Proの複雑さはCLOCKの複雑さと同じであるため、低コストで実装するのが簡単です。 現在のバージョンのLinuxでのバッファキャッシュ置換の実装は、LRUとCLOCK-Proの組み合わせです。

Adaptive replacement cache(ARC)Edit

常に組み合わせた結果を改善するために、LRUとLFUの間でバランスをとります。 ARCは、最近削除されたキャッシュ項目に関する情報を使用して、保護されたセグメントと保護対象セグメントのサイズを動的に調整し、使用可能なキャ 適応置換アルゴリズムを例で説明した。

AdaptiveClimb(AC)Edit

最近のヒット/ミスを使用してジャンプを調整し、climbではいずれかのヒットが1つのスロットの位置をトップに切り替え、LRU hitではヒットの位置をトップに切り替えます。 したがって、プログラムが固定スコープにあるときのclimbの最適性と、LRUのように新しいスコープへの迅速な適応の恩恵を受けます。 また、参照がキャッシュの上部にあるときに余分なものを解放することにより、コア間のキャッシュ共有をサポートしています。

適応置換とクロック（CAR）編集

適応置換キャッシュ（ARC）とクロックの利点を兼ね備えています。 CARはARCに匹敵する性能を持ち、LRUとCLOCKの両方を大幅に上回っています。 ARCと同様に、CARはセルフチューニングであり、ユーザー指定の魔法パラメータを必要としません。 二つのクロックT1とT2と二つの単純なLRUリストB1とB2：それは4つの二重リンクリストを使用しています。 T1clockは”recency”または”short term utility”に基づいてページを格納しますが、T2は”frequency”または”long term utility”のページを格納します。 T1とT2にはキャッシュ内にあるページが含まれ、B1とB2にはそれぞれt1とT2から最近削除されたページが含まれます。 このアルゴリズムは、これらのリストB1≤T2およびB2≤T1のサイズを維持しようとします。 新しいページがT1またはT2に挿入されます。 B1にヒットがある場合はT1のサイズが増加し、同様にB2にヒットがある場合はT1のサイズが減少します。 使用される適応ルールは、ARCのそれと同じ原則を持っています,より多くのページがそれに追加されたときに、より多くのヒットを与えるリストに多

Multi queue(MQ)Edit

multi queue algorithmまたはMQは、サーババッファキャッシュなどの第二レベルバッファキャッシュのパフォーマンスを向上させるために開発されました。 これはZhou,Philbin,Liの論文で紹介されています.MQキャッシュにはm個のLRUキューが含まれています:Q0,Q1,…、Qm-1。 ここで、mの値は、その特定のキュー内のすべてのブロックの有効期間に基づく階層を表します。 たとえば、j>iの場合、QjのブロックはQiのブロックよりも長い寿命を持ちます。 これらに加えて、別の履歴バッファQout、それらのアクセス頻度とともにすべてのブロック識別子のリストを維持するキューがあります。 Qoutがいっぱいになると、最も古い識別子が削除されます。 これは、MQアルゴリズムによって動的に定義され、同じファイルへの2つのアクセス間の最大時間距離、またはキャッシュブロックの数のいずれか大きい方に定義されます。 有効期間内にブロックが参照されていない場合は、QiからQi−1に降格されるか、q0にある場合はキャッシュから削除されます。 キュー Qi内のブロックが2i回以上アクセスされた場合、このブロックは2i+1回以上アクセスされるか、その有効期限が切れるまでQi+1に昇格され LRUによると、特定のキュー内では、ブロックはアクセスの最新性によってランク付けされます。

図から見ることができます。 m個のLRUキューがキャッシュにどのように配置されるか。 また、図から参照されたい。 Qoutがブロック識別子とそれに対応するアクセス頻度をどのように格納するか。 アクセス頻度が2と4であるため、bとcがそれぞれQ1とQ2にどのように配置されたかをQoutで確認できます。 ブロックが配置されるキューは、log2(f)としてアクセス頻度(f)に依存します。 キャッシュがいっぱいになると、削除される最初のブロックはQ0の先頭になります。aがもう一度アクセスされると、bの下のQ1に移動します。

Pannier:compound objectsEditのコンテナベースのキャッシュアルゴリズム

Pannierは、そこに保持されているブロックが非常に変化するアクセスパターンを持つ発散(異種)コンテナを識別するコンテナベースのフラッシュキャッシングメカニズムです。 Pannierは、優先キューベースの生存キュー構造を使用して、コンテナ内のライブデータに比例する生存時間に基づいてコンテナをランク付けします。 Pannierは、ホットデータとコールドデータを分離するセグメント化されたLRU(S2LRU)に基づいて構築されています。 また、Pannierはマルチステップフィードバックコントローラを使用してフラッシュ書き込みを抑制し、フラッシュの寿命を確保します。