キャッシュ（コンピューティング）

コンピューティングでは、キャッシュ( / k æ ʃ / ^ⓘ KASH)^[1]は、将来のデータ要求をより速く処理できるようにデータを格納するハードウェアまたはソフトウェア コンポーネントです。キャッシュに格納されるデータは、以前の計算の結果である場合もあれば、他の場所に格納されているデータのコピー要求されたデータがキャッシュ内に見つかった場合はキャッシュ ヒットキャッシュ ミスが発生します。キャッシュ ヒットは、キャッシュからデータを読み取ることで処理されます。これは、結果を再計算したり、低速のデータ ストアから読み取ったりするよりも高速です。したがって、キャッシュから処理できる要求が多いほど、システムのパフォーマンスは速くなります。^[2]

コスト効率を高めるには、キャッシュを比較的小さくする必要があります。しかし、一般的なコンピュータ アプリケーションは高度な参照の局所性を持つデータにアクセスするため、キャッシュはコンピューティングの多くの領域で効果的です。このようなアクセス パターンは、最近要求されたデータが要求される時間的局所性と、すでに要求されたデータの近くに格納されているデータが要求される空間的局所性を示します。

メモリ設計においては、容量と速度の間にはトレードオフが存在します。容量が大きいほどサイズが大きくなり、信号が移動する物理的な距離が長くなり、伝播遅延が発生するからです。また、 SRAMなどの高性能テクノロジと、 DRAM、フラッシュ、ハードディスクなどの安価で大量生産が容易な商品との間にもトレードオフが存在します。

キャッシュによって提供されるバッファリングは、レイテンシとスループット (帯域幅) のいずれかまたは両方にメリットをもたらします。

リソースが大きいほど、アクセスにかなりのレイテンシが発生します。たとえば、最新の 4 GHz プロセッサが DRAM に到達するには、数百クロック サイクルかかることがあります。この問題は、後続の読み取りが近くの場所から行われ、キャッシュから読み取ることができることを期待して、大きなチャンクをキャッシュに読み込むことで軽減されます。予測または明示的なプリフェッチを使用すると、将来の読み取りがどこから行われるかを推測し、事前に要求を行うことができます。最適に実行されれば、レイテンシは完全に回避されます。

キャッシュを使用すると、複数の細粒度の転送をより大規模で効率的なリクエストにまとめることで、基盤となるリソースからのスループットを高めることもできます。DRAM 回路の場合、より広いデータ バスを使用することで、スループットをさらに高めることができます。

ハードウェアは、再度使用される可能性のあるデータを一時的に保存するためのメモリブロックとしてキャッシュを実装します。中央処理装置(CPU)、ソリッド ステート ドライブ(SSD)、およびハード ディスク ドライブ (HDD) には、ハードウェア ベースのキャッシュが含まれることがよくありますが、Web ブラウザーとWeb サーバーは、一般的にソフトウェア キャッシュに依存しています。

キャッシュはエントリのプールで構成されています。各エントリには、あるバッキング ストア内の同じデータのコピーであるデータが関連付けられています。また、各エントリには、エントリがコピーされているバッキング ストア内のデータの ID を指定する タグもあります。

キャッシュ クライアント (CPU、Web ブラウザー、オペレーティング システム) が、バッキング ストアに存在すると推定されるデータにアクセスする必要がある場合、最初にキャッシュをチェックします。目的のデータのタグと一致するタグを持つエントリが見つかった場合は、代わりにそのエントリのデータが使用されます。この状況は、キャッシュ ヒットと呼ばれます。たとえば、Web ブラウザー プログラムは、特定のURLの Web ページのコンテンツのローカル コピーがあるかどうかを確認するために、ディスク上のローカル キャッシュをチェックする場合があります。この例では、URL がタグであり、Web ページのコンテンツがデータです。キャッシュ ヒットとなるアクセスの割合は、キャッシュの ヒット率またはヒット率と呼ばれます。

キャッシュをチェックして、目的のタグを持つエントリが含まれていないことが判明した場合の別の状況は、キャッシュ ミスと呼ばれます。この場合、バックアップ ストアからのデータへのアクセスにコストがかかります。要求されたデータが取得されると、通常はキャッシュにコピーされ、次のアクセスに備えられます。

キャッシュ ミスが発生すると、通常、新しく取得したデータのためのスペースを確保するために、以前に存在していた他のキャッシュ エントリが削除されます。置き換えるエントリを選択するために使用されるヒューリスティックは、置換ポリシーと呼ばれます。一般的な置換ポリシーの 1 つである LRU (Least Recently Used) では、最も古いエントリ、つまり他のエントリよりも最近アクセスされたエントリが置き換えられます。より高度なキャッシュ アルゴリズムでは、エントリの使用頻度も考慮されます。

システムがキャッシュにデータを書き込む場合、ある時点でそのデータをバックアップストアにも書き込む必要があります。この書き込みのタイミングは、書き込みポリシーと呼ばれるものによって制御されます。基本的な書き込み方法は2つあります。^[3]

• ライトスルー: 書き込みはキャッシュとバッキング ストアの両方に同期して実行されます。
• ライトバック: 最初は、書き込みはキャッシュに対してのみ行われます。バッキング ストアへの書き込みは、変更されたコンテンツが別のキャッシュ ブロックに置き換えられるまで延期されます。

ライトバック キャッシュは、どの場所が上書きされたかを追跡し、後でバッキング ストアに書き込むためにダーティとしてマークする必要があるため、実装がより複雑になります。これらの場所のデータは、キャッシュから削除された場合にのみバッキング ストアに書き戻されます。このプロセスは、遅延書き込みと呼ばれます。このため、ライトバック キャッシュでの読み取りミスでは、多くの場合、サービスへの 2 回のメモリ バッキング ストア アクセスが必要になります。1 回はライトバック用、もう 1 回は必要なデータを取得するためです。他のポリシーによっても、データのライトバックがトリガーされることがあります。クライアントは、キャッシュ内のデータに多くの変更を加えた後、キャッシュにデータを書き戻すように明示的に通知する場合があります。

書き込み操作では要求元にデータが返されないため、書き込みミス時にデータをキャッシュにロードするかどうかを決定する必要があります。

• 書き込み割り当て(書き込み時のフェッチとも呼ばれます): 書き込みミスの場所のデータがキャッシュにロードされ、その後に書き込みヒット操作が実行されます。このアプローチでは、書き込みミスは読み取りミスと同様です。
• 非書き込み割り当て(書き込み非割り当てまたは書き込みアラウンドとも呼ばれます) : 書き込みミスの場所のデータはキャッシュにロードされず、直接バッキング ストアに書き込まれます。このアプローチでは、データは読み取りミスの場合にのみキャッシュにロードされます。

ライトスルーポリシーとライトバックポリシーはどちらもこれらのライトミスポリシーのいずれかを使用できますが、通常はペアで使用されます。^{[4] [5]}

• ライトバック キャッシュは、書き込み割り当てを使用して、現在キャッシュされている同じ場所への後続の書き込み (または読み取り) を期待します。
• ライトスルー キャッシュは、書き込みなしの割り当てを使用します。この場合、後続の書き込みは、依然としてバッキング ストアに直接書き込む必要があるため、利点はありません。

キャッシュ以外のエンティティがバッキング ストア内のデータを変更する場合、キャッシュ内のコピーは古くなるか、古くなる可能性があります。また、クライアントがキャッシュ内のデータを更新すると、他のキャッシュ内のそのデータのコピーは古くなります。データの一貫性を保つキャッシュ マネージャー間の通信プロトコルは、キャッシュの一貫性と関連しています。

キャッシュ読み取りミスが発生すると、デマンド ページングポリシーを持つキャッシュは、バッキング ストアから最小限の量を読み取ります。一般的なデマンド ページング仮想メモリ実装では、ディスクから 1 ページの仮想メモリ (多くの場合 4 KB) を RAM のディスク キャッシュに読み取ります。一般的な CPU は、128 バイトの単一の L2 キャッシュ ラインを DRAM から L2 キャッシュに読み取り、64 バイトの単一の L1 キャッシュ ラインを L2 キャッシュから L1 キャッシュに読み取ります。

プリフェッチ入力キューまたはより一般的な予測ページング ポリシーを備えたキャッシュはさらに進んで、要求されたデータを読み取るだけでなく、次の 1 つか 2 つのデータ チャンクがすぐに必要になると推測し、そのデータを事前にキャッシュにプリフェッチします。予測ページングは​​、ディスクストレージや DRAM など、バッキング ストアで最初のチャンクを読み取るのに長い待ち時間があり、次のいくつかのチャンクを順番に読み取るのに非常に短い時間しかない場合に特に役立ちます。

いくつかのオペレーティング システムでは、さらに進んで、実行可能ファイル全体を常に RAM にプリロードするローダーが使用されています。いくつかのキャッシュではさらに進んで、ファイル全体をプリロードするだけでなく、プリフェッチャーに関連付けられたページ キャッシュやリンク プリフェッチに関連付けられたWeb キャッシュなど、すぐに要求される可能性のある他の関連ファイルのロードも開始します。

CPU上またはCPUの近くにある小さなメモリは、はるかに大きなメインメモリよりも高速に動作できます。^[6] 1980年代以降のほとんどのCPUは1つ以上のキャッシュを使用しており、カスケードレベルで使用されている場合もあります。現代の高性能な組み込み、デスクトップ、およびサーバーマイクロプロセッサには、6種類ものキャッシュ（レベルと機能）がある場合があります。^[7]特定の機能を持つキャッシュの例としては、Dキャッシュ、Iキャッシュ、およびメモリ管理ユニット（MMU）のトランスレーションルックアサイドバッファがあります。

以前のグラフィックス プロセッシング ユニット(GPU) では、読み取り専用のテクスチャ キャッシュが制限されていることがよくあり、スウィズリングを使用して2D参照の局所性を改善していました。キャッシュ ミスは、たとえばミップマッピングを使用していない場合、パフォーマンスに大きく影響します。キャッシュは、ピクセルあたり 4 ビットしかないことが多いテクスチャ データの 32 ビット (およびそれ以上) 転送を活用するために重要でした。

GPU が進化し、グラフィックス プロセッシング ユニットとコンピューティング カーネルでの汎用コンピューティングをサポートするにつれて、シェーダーの命令キャッシュなど、CPU キャッシュによく見られる機能を備えた、より大規模で汎用性の高いキャッシュが開発されました。これらのキャッシュは、スレッドとアトミック操作間の同期プリミティブを処理し、CPU スタイルの MMU とインターフェイスするよう に拡張されました。

デジタル信号プロセッサも同様に長年にわたって一般化してきました。初期の設計では、直接メモリアクセスによって供給されるスクラッチパッドメモリが使用されていましたが、 Qualcomm Hexagonなどの最新のDSPには、 CPUと非常によく似たキャッシュセットが含まれていることがよくあります（例：共有L2、分割L1 IキャッシュとDキャッシュを備えた修正ハーバードアーキテクチャ）。 ^[8]

メインメモリからページテーブルエントリを取得するメモリ管理ユニット（MMU）には、仮想アドレスから物理アドレスへの変換結果を記録するために使用される特殊なキャッシュがあります。この特殊なキャッシュは、変換ルックアサイドバッファ（TLB）と呼ばれます。^[9]

情報中心ネットワーク(ICN) は、インターネットインフラストラクチャを、永続的な接続性とエンドツーエンドの原則に基づくホスト中心のパラダイムから、識別された情報に焦点を置いたネットワーク アーキテクチャへと進化させるアプローチです。ICN 内のノードには固有のキャッシュ機能があるため、ICN はキャッシュの緩く接続されたネットワークと見なすことができ、キャッシュ ポリシーに固有の要件があります。ただし、ユビキタス コンテンツ キャッシュは、不正アクセスに対するコンテンツ保護に課題をもたらし、特別な注意とソリューションを必要とします。^[10]

プロキシ サーバーとは異なり、ICN ではキャッシュはネットワーク レベルのソリューションです。そのため、キャッシュ状態が急速に変化し、要求の到着率が高くなります。さらに、キャッシュ サイズが小さいと、コンテンツ削除ポリシーに異なる要件が課せられます。特に、ICN の削除ポリシーは高速かつ軽量である必要があります。さまざまな ICN アーキテクチャとアプリケーション向けに、さまざまなキャッシュ複製および削除スキームが提案されています。^{[引用が必要]}

時間を考慮した Least Recently Used (TLRU) ^{[11] は、}キャッシュに格納されたコンテンツに有効な存続期間がある場合のために設計された LRU の変形です。このアルゴリズムは、ICN、コンテンツ配信ネットワーク(CDN)、一般的な分散ネットワークなどのネットワーク キャッシュ アプリケーションに適しています。TLRU では、TTU (Time to Use) という新しい用語が導入されています。TTU は、コンテンツ/ページのタイム スタンプであり、コンテンツの地域とコンテンツ発行者のアナウンスに基づいて、コンテンツの使用可能時間を規定します。この地域に基づくタイム スタンプにより、TTU はネットワーク ストレージを規制するためのローカル管理者に詳細な制御を提供します。

TLRU アルゴリズムでは、コンテンツが到着すると、キャッシュ ノードはコンテンツ パブリッシャーによって割り当てられた TTU 値に基づいてローカル TTU 値を計算します。ローカル TTU 値は、ローカルで定義された関数を使用して計算されます。ローカル TTU 値が計算されると、キャッシュ ノードに保存されている全コンテンツのサブセットに対してコンテンツの置き換えが実行されます。TLRU により、人気のないコンテンツや有効期限の短いコンテンツが、到着したコンテンツに置き換えられることが保証されます。

LFRU (Least Frequent Recently Used) ^[12]キャッシュ置換方式は、LFU 方式と LRU 方式の利点を組み合わせたものです。LFRU は、ICN、CDN、分散ネットワーク全般などの「ネットワーク内」キャッシュ アプリケーションに適しています。LFRU では、キャッシュは特権パーティションと非特権パーティションと呼ばれる 2 つのパーティションに分割されます。特権パーティションは、保護されたパーティションとして定義できます。コンテンツの人気が高い場合は、特権パーティションにプッシュされます。特権パーティションの置換は、次のように行われます。LFRU は、非特権パーティションからコンテンツを追い出し、特権パーティションから非特権パーティションにコンテンツをプッシュし、最後に新しいコンテンツを特権パーティションに挿入します。上記の手順では、特権パーティションに LRU が使用され、非特権パーティションには近似 LFU (ALFU) 方式が使用されるため、略語は LFRU です。基本的な考え方は、ALFU 方式を使用してローカルで人気のあるコンテンツをフィルターし、人気のあるコンテンツを特権パーティションの 1 つにプッシュすることです。

2011年、天気予報オプション付きのスマートフォンの使用により、AccuWeatherサーバーに過度の負荷がかかり、同じ公園内で2つのリクエストが別々のリクエストを生成することがありました。エッジサーバーによるGPS座標の小数点以下の桁数を減らす最適化により、以前のクエリからキャッシュされた結果が使用されるようになりました。1日あたりのサーバー検索回数は半分に減少しました。^[13]

CPU キャッシュは一般にハードウェアによって完全に管理されますが、その他のキャッシュはさまざまなソフトウェアによって管理されます。ディスク キャッシュの一例であるメイン メモリ内のページ キャッシュは、オペレーティング システムカーネルによって管理されます。

ハードディスク ドライブまたはソリッド ステート ドライブの統合部分であるディスク バッファは、誤解を招くように「ディスク キャッシュ」と呼ばれることもありますが、その主な機能は書き込みシーケンスと読み取りプリフェッチです。バッファのサイズがドライブの容量に比べて小さいため、キャッシュ ヒットが繰り返されることは比較的まれです。ただし、ハイエンドのディスク コントローラには、ハードディスク ドライブのデータ ブロックの独自のオンボード キャッシュが搭載されていることがよくあります。

最後に、高速なローカル ハード ディスク ドライブは、リモート サーバー (Web キャッシュ) やローカルテープ ドライブ、光ジュークボックスなどのさらに低速なデータ ストレージ デバイスに保存されている情報をキャッシュすることもできます。このようなスキームは、階層型ストレージ管理の主要概念です。また、高速なフラッシュ ベースのソリッド ステート ドライブ (SSD) は、低速な回転メディア ハード ディスク ドライブのキャッシュとして使用でき、ハイブリッド ドライブまたはソリッド ステート ハイブリッド ドライブ(SSHD) として連携して動作します。

ウェブブラウザとウェブプロキシサーバーは、ウェブページや画像など、ウェブサーバーからの以前の応答を保存するためにウェブキャッシュを使用します。ウェブキャッシュは、以前にキャッシュに保存された情報を再利用できるため、ネットワークを介して送信する必要がある情報の量を削減します。これにより、ウェブサーバーの帯域幅と処理要件が削減され、ウェブユーザーの応答性が向上します。 ^[14]

Web ブラウザは組み込みの Web キャッシュを使用しますが、一部のインターネット サービス プロバイダー(ISP) または組織は、そのネットワークのすべてのユーザー間で共有される Web キャッシュであるキャッシュ プロキシ サーバーも使用します。

キャッシュの別の形態はP2Pキャッシュであり、ピアツーピアアプリケーションが最も検索するファイルをISPキャッシュに保存してP2P転送を高速化する。同様に、コミュニティがP2Pトラフィックに対して同じタスクを実行できるようにする分散型の同等のものが存在する（例：Corelli）。^[15]

キャッシュは、バックアップ ストアから取得するのではなく、オンデマンドで計算されたデータを保存できます。メモ化は、リソースを消費する関数呼び出しの結果を参照テーブル内に保存する最適化手法です。これにより、後続の呼び出しで保存された結果を再利用して、繰り返し計算を回避できます。これは、キャッシュの手段とも考えられる 動的プログラミングアルゴリズム設計方法論に関連しています。

コンテンツ配信ネットワーク (CDN) は、ユーザーの地理的位置、Web ページの発信元、コンテンツ配信サーバーに基づいて、ページやその他の Web コンテンツをユーザーに配信する分散サーバーのネットワークです。

CDN は、HTML ページ、画像、動画などの静的コンテンツの配信を高速化する方法として 1990 年代後半に始まりました。世界中の複数のサーバーにコンテンツを複製し、ユーザーの所在地に基づいて配信することで、CDN は Web サイトやアプリケーションの速度と可用性を大幅に向上させることができます。ユーザーがコンテンツを要求すると、CDN はキャッシュにコンテンツのコピーがあるかどうかを確認します。コピーがある場合、CDN はキャッシュからユーザーにコンテンツを配信します。^[16]

クラウドストレージゲートウェイは、エッジファイラーとも呼ばれ、ローカルネットワークを1つ以上のクラウドストレージサービス（通常はAmazon S3などのオブジェクトストレージサービス）に接続するハイブリッドクラウドストレージデバイスです。頻繁にアクセスされるデータのキャッシュを提供し、クラウドストレージサービス内の頻繁にアクセスされるデータへの高速なローカルアクセスを提供します。クラウドストレージゲートウェイには、従来のファイルサービスプロトコルを介してクラウドオブジェクトストレージにアクセスしたり、接続が切断されている間もキャッシュされたデータに継続的にアクセスしたりするなど、追加の利点もあります。^[17]

BIND DNSデーモンは、リゾルバ ライブラリと同様に、 ドメイン名とIP アドレスのマッピングをキャッシュします。

ライトスルー操作は、信頼性の低いネットワーク (イーサネット LAN など) で操作する場合によく使用されます。これは、通信が信頼性の低い場合に複数のライトバック キャッシュ間で必要な一貫性プロトコルが非常に複雑になるためです。たとえば、Web ページ キャッシュやクライアント側の ネットワーク ファイル システムキャッシュ ( NFSやSMBなど) は、通常、ネットワーク プロトコルをシンプルかつ信頼性の高い状態に保つために、読み取り専用またはライトスルーになっています。

検索エンジンは、インデックスした Web ページをキャッシュから利用できるようにすることもよくあります。たとえば、Google は各検索結果の横に「キャッシュ済み」リンクを提供します。これは、Web サーバーの Web ページが一時的または永続的にアクセスできない場合に役立ちます。

データベース キャッシュを使用すると、インデックス、データ ディクショナリ、頻繁に使用されるデータのサブセット の処理など、データベースアプリケーションのスループットを大幅に向上できます。

分散キャッシュ[ ^18]は、ネットワーク化されたホストを使用して、アプリケーションにスケーラビリティ、信頼性、パフォーマンスを提供します。^[19]ホストは同じ場所に配置することも、異なる地理的領域に分散させることもできます。

「バッファ」と「キャッシュ」の意味はまったく異なるわけではありませんが、キャッシュのプロセスとバッファリングのプロセスの間には、意図に根本的な違いがあります。

基本的に、キャッシュは繰り返し転送されるデータの転送パフォーマンスの向上を実現します。キャッシュ システムは、データ項目の最初の (通常は書き込み) 転送時にパフォーマンスの向上を実現する場合がありますが、このパフォーマンスの向上は、キャッシュ システム内で発生するバッファリングによるものです。

読み取りキャッシュでは、データ項目をその常駐場所から少なくとも 1 回フェッチする必要があります。そうしないと、その後のデータ項目の読み取りでは、データの常駐場所ではなく、キャッシュの (より高速な) 中間ストレージからフェッチできるため、パフォーマンスが向上します。書き込みキャッシュでは、データ項目を最初に書き込むときに、データ項目がすぐにキャッシュの中間ストレージに格納され、データ項目の常駐ストレージへの転送が後の段階で延期されるか、バックグラウンド プロセスとして実行されるため、データ項目の書き込みのパフォーマンスが向上します。厳密なバッファリングとは異なり、キャッシュ プロセスは、キャッシュの中間ストレージとデータが存在する場所の間の一貫性を維持するために、(分散されている可能性のある) キャッシュ一貫性プロトコルに準拠する必要があります。一方、バッファリングでは、

• 通信プロセス間での新規データの転送回数を減らし、複数の小さな転送にかかるオーバーヘッドを、より少ない、より大きな転送に分散する。
• 相互に直接転送できない通信プロセスの仲介を提供する、または
• 転送に関与する通信プロセスの少なくとも 1 つに必要な最小データ サイズまたは表現を保証します。

一般的なキャッシュ実装では、初めて読み書きされるデータ項目は、実質的にバッファリングされます。書き込みの場合、ほとんどの場合、書き込み元のアプリケーションのパフォーマンスが向上します。さらに、キャッシュ プロトコルで、個々の書き込みが書き込みのバッチに延期される部分は、バッファリングの形式です。キャッシュ プロトコルで、個々の読み取りが読み取りのバッチに延期される部分も、バッファリングの形式ですが、この形式は、少なくとも最初の読み取りのパフォーマンスに悪影響を与える可能性があります (個々の読み取りの合計のパフォーマンスにはプラスの影響を与える可能性がありますが)。実際には、キャッシュにはほとんどの場合、何らかの形式のバッファリングが含まれますが、厳密なバッファリングにはキャッシュは含まれません。

バッファは、CPU命令が周辺機器に格納されたデータを直接アドレス指定できないために従来から使用されている一時的なメモリ位置です。したがって、アドレス指定可能なメモリは中間段階として使用されます。さらに、このようなバッファは、(ストレージ デバイスの要件に従って) 大きなデータ ブロックをアセンブルまたはディスアセンブルする場合や、データが生成された順序とは異なる順序で配信される場合に使用できます。また、通常、データのバッファ全体は順番に転送されるため (たとえば、ハード ディスクに)、バッファリング自体によって転送パフォーマンスが向上したり、転送のレイテンシの変動やジッタが軽減されたりすることがあります。これは、レイテンシの削減を目的とするキャッシュとは対照的です。これらの利点は、バッファリングされたデータがバッファに 1 回書き込まれ、バッファから 1 回読み取られる場合でも得られます。

キャッシュは転送パフォーマンスも向上させます。同様に、複数の小さな転送が 1 つの大きなブロックに結合される可能性によって、パフォーマンスも向上します。しかし、主なパフォーマンス向上は、同じデータがキャッシュから複数回読み取られる可能性が高いか、書き込まれたデータがすぐに読み取られる可能性があるために発生します。キャッシュの唯一の目的は、基盤となる低速ストレージへのアクセスを減らすことです。また、キャッシュは通常、隣接するレイヤーから見えないように設計された 抽象化レイヤーでもあります。

• 「すべてのプログラマがメモリについて知っておくべきこと」
• 「分散環境でのキャッシュ」