Loading article…
コンピューティングでは、キャッシュ( / k æ ʃ /ⓘ KASH [ 1 ] ) は、将来のデータ要求をより速く処理できるようにデータを保存するハードウェアまたはソフトウェアコンポーネントです。キャッシュに保存されるデータは、以前の計算結果または他の場所に保存されているデータのコピーである可能性があります。要求されたデータがキャッシュ内で見つかった場合、キャッシュヒットがキャッシュミスが発生します。キャッシュヒットは、キャッシュからデータを読み取ることで処理されます。これは、結果を再計算したり、より低速なデータストアから読み取ったりするよりも高速です。したがって、キャッシュから処理できる要求が多いほど、システムのパフォーマンスは速くなります。 [ 2 ]
コスト効率を高めるためには、キャッシュは比較的小さくなければなりません。しかしながら、一般的なコンピュータアプリケーションは参照の局所性が高いデータにアクセスするため、キャッシュはコンピューティングの多くの分野で効果的です。このようなアクセスパターンは、最近要求されたデータが要求されるという時間的局所性と、既に要求されたデータの近くに格納されているデータが要求されるという空間的局所性を示します。
メモリ設計においては、容量と速度の間には本質的なトレードオフが存在する。容量が大きくなればサイズも大きくなり、信号が伝わる物理的な距離が長くなるため、伝搬遅延が生じるからである。また、 SRAMのような高性能技術と、 DRAM、フラッシュメモリ、ハードディスクといった安価で大量生産しやすい汎用品の間にもトレードオフが存在する。
キャッシュによって提供されるバッファリングは、レイテンシとスループット（帯域幅）のいずれか、または両方にメリットをもたらします。
より大きなリソースへのアクセスには、大きなレイテンシが発生します。例えば、最新の4GHz プロセッサでもDRAMにアクセスするには数百クロックサイクルかかることがあります。これを軽減するために、大きなチャンクをキャッシュに読み込み、後続の読み取りが近くの場所から行われ、キャッシュから読み取れるようにすることが推奨されます。予測または明示的なプリフェッチを使用して、将来の読み取りがどこから行われるかを予測し、事前に要求することができます。最適に実行すれば、レイテンシを完全に回避できます。
キャッシュを使用することで、複数の細粒度転送をより大規模で効率的なリクエストにまとめることができ、基盤となるリソースのスループットを向上させることができます。DRAM回路の場合、より広いデータバスを使用することで、スループットをさらに向上させることができます。
ハードウェアは、再利用される可能性のあるデータを一時的に保存するためのメモリブロックとしてキャッシュを実装します。中央処理装置（CPU）、ソリッドステートドライブ（SSD）、ハードディスクドライブ（HDD）にはハードウェアベースのキャッシュが搭載されていることが多く、一方、WebブラウザやWebサーバーは一般的にソフトウェアキャッシュに依存しています。
キャッシュはエントリのプールで構成されます。各エントリには関連付けられたデータがあり、これは何らかのバックアップストアにある同じデータのコピーです。各エントリにはタグもあり、これはエントリがコピーされているバックアップストア内のデータの識別情報を指定します。
キャッシュクライアント（CPU、Webブラウザ、オペレーティングシステムなど）が、バックエンドストアに存在すると想定されるデータにアクセスする必要がある場合、まずキャッシュをチェックします。目的のデータと一致するタグを持つエントリが見つかった場合、そのエントリ内のデータが使用されます。この状況はキャッシュヒットと呼ばれます。たとえば、Webブラウザプログラムは、特定のURLにあるWebページのコンテンツのローカルコピーがあるかどうかを確認するために、ディスク上のローカルキャッシュをチェックする場合があります。この例では、URLがタグであり、Webページのコンテンツがデータです。キャッシュヒットとなるアクセスの割合は、キャッシュのヒット率またはヒット比率と呼ばれます。
キャッシュをチェックした結果、目的のタグを持つエントリが見つからない場合、それはキャッシュミスと呼ばれます。この場合、バックエンドストアからのデータアクセスはよりコストがかかります。要求されたデータが取得されると、通常はキャッシュにコピーされ、次のアクセスに備えられます。
キャッシュミスが発生すると、通常、新しく取得したデータのためのスペースを確保するために、以前存在していたキャッシュエントリが削除されます。置き換えるエントリを選択するために使用されるヒューリスティックは、置換ポリシーとして知られています。よく用いられる置換ポリシーの1つであるLRU（Least Recently Used：最小使用頻度）は、最も古いエントリ、つまり他のどのエントリよりもアクセス頻度が低いエントリを置き換えます。より高度なキャッシングアルゴリズムでは、エントリの使用頻度も考慮されます。
キャッシュへの書き込みは最終的にバッキングストアに伝播される必要があります。このタイミングは書き込みポリシーによって制御されます。主な書き込みポリシーは次の 2 つです。[ 3 ]
ライトバックキャッシュは、どの場所が既に書き込まれたかを追跡し、後でバッキングストアに書き込むためにダーティとしてマークする必要があるため、実装がより複雑になります。これらの場所のデータは、キャッシュから追い出されたときにのみバッキングストアに書き戻されます。このプロセスは遅延書き込みと呼ばれます。このため、ライトバックキャッシュでの読み取りミスでは、バッキングストアへのメモリアクセスが2回必要になる場合があります。1回はダーティデータを書き戻すため、もう1回は要求されたデータを取得するためです。他のポリシーによってもデータのライトバックがトリガーされる場合があります。クライアントがキャッシュ内のデータに多くの変更を加え、その後、キャッシュに明示的にデータの書き戻しを通知する場合があります。
書き込み操作ではデータは返されません。したがって、書き込みミスが発生した場合、データをキャッシュにロードするかどうかを決定する必要があります。これは、以下の書き込みミスポリシーによって決定されます。
どちらの書き込みポリシーも書き込みミスポリシーのいずれかを実装できますが、通常は次のようにペアになっています。[ 4 ] [ 5 ]
キャッシュ以外のエンティティがバックエンドストアのデータを変更する場合、キャッシュ内のコピーが古くなったり、陳腐化したりする可能性があります。また、クライアントがキャッシュ内のデータを更新すると、他のキャッシュにあるそのデータのコピーも陳腐化します。データの一貫性を維持するキャッシュマネージャ間の通信プロトコルは、キャッシュの一貫性に関連しています。
キャッシュ読み取りミスが発生した場合、デマンドページングポリシーを採用しているキャッシュは、バッキングストアから最小限のデータを読み取ります。一般的なデマンドページング方式の仮想メモリ実装では、 ディスクから仮想メモリの1ページ（多くの場合4KB）をRAM内のディスクキャッシュに読み取ります。一般的なCPUは、DRAMから128バイトのL2キャッシュラインを1つ L2キャッシュに、 L2キャッシュから64バイトのL1キャッシュラインを1つL1キャッシュに読み取ります。
プリフェッチ入力キューやより一般的な予測型ページングポリシーを備えたキャッシュは、さらに一歩進んで、要求されたデータを読み取るだけでなく、次の1つか2つのデータチャンクがすぐに必要になると予測し、そのデータを事前にキャッシュにプリフェッチします。予測型ページングは、ディスクストレージやDRAMのように、最初のチャンクを読み取るのに長いレイテンシがあり、次の数個のチャンクを順次読み取るのに非常に短い時間しかかからないバックエンドストレージの場合に特に有効です。
一部のオペレーティングシステムは、実行可能ファイル全体を常にRAMにプリロードするローダーを備えています。一部のキャッシュはさらに進んで、ファイル全体をプリロードするだけでなく、プリフェッチャに関連付けられたページキャッシュやリンクプリフェッチに関連付けられたWebキャッシュなど、まもなく要求される可能性のある他の関連ファイルのロードも開始します。
CPU上またはその近くにある小さなメモリは、はるかに大きなメインメモリよりも高速に動作できます。[ 6 ] 1980年代以降のほとんどのCPUは、1つ以上のキャッシュを使用しており、場合によってはカスケード接続されています。最新のハイエンド組み込み、デスクトップ、およびサーバーマイクロプロセッサは、最大6種類のキャッシュ（レベルと機能の間）を備えている場合があります。[ 7 ]特定の機能を持つキャッシュの例としては、Dキャッシュ、Iキャッシュ、およびメモリ管理ユニット（MMU）の変換ルックアサイドバッファなどがあります。
初期のグラフィックス処理ユニット（GPU）は、読み取り専用のテクスチャキャッシュが限られており、2次元の参照局所性を向上させるためにスウィズリングを使用していた。ミップマッピングを使用しない場合など、キャッシュミスが発生するとパフォーマンスに深刻な影響を及ぼした。キャッシュは、ピクセルあたりわずか4ビット程度のテクスチャデータに対して、32ビット（およびそれ以上）の転送速度を活用するために重要だった。
GPUの進化に伴い、グラフィックス処理ユニットと演算カーネル上で汎用コンピューティングをサポートするようになったことで、シェーダー用の命令キャッシュなど、CPUキャッシュによく見られる機能を備えた、より大規模で汎用性の高いキャッシュが開発されるようになりました。これらのキャッシュは、スレッド間の同期プリミティブやアトミック操作を処理し、CPUスタイルのMMUと連携するように拡張されています。
デジタル信号プロセッサも同様に長年にわたって汎用化されてきました。初期の設計では、ダイレクトメモリアクセスによって供給されるスクラッチパッドメモリを使用していましたが、現代のDSPでは、CPUと非常によく似たキャッシュセット（共有L2、分割L1命令キャッシュ、データキャッシュを備えた改良型ハーバードアーキテクチャなど）が含まれていることがよくあります。[ 8 ]
メインメモリからページテーブルエントリを取得するメモリ管理ユニット（MMU）には、仮想アドレスから物理アドレスへの変換結果を記録するための専用キャッシュがあります。この専用キャッシュは、変換ルックアサイドバッファ（TLB）と呼ばれます。[ 9 ]
情報中心型ネットワーク(ICN) は、永続的な接続性とエンドツーエンドの原則に基づくホスト中心のパラダイムから、識別された情報に焦点を当てたネットワーク アーキテクチャへとインターネットインフラストラクチャを進化させるアプローチです。ICN のノードには固有のキャッシュ機能があるため、キャッシュの緩やかに接続されたネットワークと見なすことができ、キャッシュ ポリシーに独自の要件があります。しかし、ユビキタスなコンテンツ キャッシュは、不正アクセスに対するコンテンツ保護に課題をもたらし、特別な注意とソリューションが必要になります。[ 10 ]
プロキシサーバーとは異なり、ICNではキャッシュはネットワークレベルのソリューションです。そのため、キャッシュの状態は急速に変化し、リクエストの到着率も高くなります。さらに、キャッシュサイズが小さいほど、コンテンツ削除ポリシーに異なる要件が課されます。特に、ICNの削除ポリシーは高速かつ軽量である必要があります。さまざまなICNアーキテクチャとアプリケーション向けに、多様なキャッシュ複製および削除方式が提案されています。
時間認識型最小使用頻度（TLRU）は、キャッシュに保存されたコンテンツに有効期間がある状況向けに設計されたLRUの派生アルゴリズムです。このアルゴリズムは、ICN、コンテンツ配信ネットワーク（CDN）、および一般的な分散ネットワークなどのネットワークキャッシュアプリケーションに適しています。TLRUでは、使用時間（TTU）という新しい用語が導入されています。TTUは、コンテンツのローカル性とコンテンツ発行者からの情報に基づいて、コンテンツの使用可能時間を規定するコンテンツへのタイムスタンプです。このローカルベースのタイムスタンプにより、TTUはローカル管理者がネットワーク内ストレージを制御するためのより多くの制御機能を提供します。
TLRUアルゴリズムでは、コンテンツが到着すると、キャッシュノードはコンテンツ発行者によって割り当てられたTTU値に基づいてローカルTTU値を計算します。ローカルTTU値は、ローカルで定義された関数を使用して計算されます。ローカルTTU値が計算されると、キャッシュノードに格納されているコンテンツ全体のサブセットに対してコンテンツの置き換えが実行されます。TLRUは、人気のない短命なコンテンツが受信コンテンツで置き換えられることを保証します。[ 11 ]
最近使用頻度が最も低い (LFRU) キャッシュ置換方式は、LFU と LRU 方式の利点を組み合わせたものです。LFRU は、ICN、CDN、および一般的な分散ネットワークなどのネットワーク キャッシュ アプリケーションに適しています。LFRU では、キャッシュは特権パーティションと非特権パーティションと呼ばれる 2 つのパーティションに分割されます。特権パーティションは保護されたパーティションと見なすことができます。コンテンツが非常に人気がある場合は、特権パーティションにプッシュされます。特権パーティションの置換は、まず非特権パーティションからコンテンツを追い出し、次に特権パーティションから非特権パーティションにコンテンツを押し込み、最後に新しいコンテンツを特権パーティションに挿入することによって行われます。上記の手順では、特権パーティションには LRU が使用され、非特権パーティションには近似 LFU (ALFU) 方式が使用されます。基本的な考え方は、ALFU 方式を使用してローカルで人気のあるコンテンツをキャッシュし、人気のあるコンテンツを特権パーティションにプッシュすることです。[ 12 ]
2011年、天気予報機能付きスマートフォンの使用によりAccuWeatherサーバーに過負荷がかかり、同じエリアからの2つのリクエストが別々のリクエストを生成するようになりました。エッジサーバーによる最適化により、GPS座標の小数点以下の桁数を減らすことで、近くのクエリからのキャッシュされた結果が使用されるようになりました。1日あたりのサーバーへのルックアップ回数は半減しました。[ 13 ]
CPUキャッシュは一般的にハードウェアによって完全に管理されますが、その他のキャッシュはさまざまなソフトウェアによって管理されます。メインメモリ内のページキャッシュは、オペレーティングシステムのカーネルによって管理されます。
ハードディスクドライブやソリッドステートドライブに組み込まれているディスクバッファは、時としてディスクキャッシュと誤解を招く形で呼ばれることがあるが、その主な機能は書き込み順序付けと読み出しプリフェッチである。ハイエンドのディスクコントローラには、ハードディスクドライブのデータブロック用のオンボードキャッシュが搭載されていることが多い。
最後に、高速なローカルハードディスクドライブは、リモートサーバー（Webキャッシュ）やローカルテープドライブ、光ディスクジュークボックスなど、さらに低速なデータストレージデバイスに保存されている情報をキャッシュすることもできます。このような仕組みは、階層型ストレージ管理の基本的な概念です。また、高速なフラッシュベースのソリッドステートドライブ（SSD）は、低速な回転式ハードディスクドライブのキャッシュとして使用でき、ハイブリッドドライブとして連携して動作します。
ウェブブラウザやウェブプロキシサーバーは、ローカルまたはインターネットサービスプロバイダ（ISP）のいずれにおいても、ウェブページや画像などのウェブサーバーからの過去の応答を保存するためにウェブキャッシュを使用します。ウェブキャッシュは、キャッシュに以前保存された情報を再利用できるため、ネットワークを介して送信する必要のある情報の量を削減します。これにより、ウェブサーバーの帯域幅と処理要件が削減され、ウェブユーザーの応答性が向上します。 [ 14 ]
キャッシュのもう1つの形態はP2Pキャッシングであり、ピアツーピアアプリケーションによって最も頻繁に要求されるファイルがISPキャッシュに保存され、P2P転送が高速化されます。同様に、分散型の同等のものも存在し、コミュニティがP2Pトラフィックに対して同じタスクを実行できます。たとえば、Corelliなどです。[ 15 ]
キャッシュは、バックエンドストアから取得するのではなく、必要に応じて計算されたデータを格納できます。メモ化は、リソースを大量に消費する関数呼び出しの結果をルックアップテーブルに格納する最適化手法であり、後続の呼び出しで格納された結果を再利用して、繰り返し計算を回避できます。これは、動的計画法アルゴリズムの設計手法に関連しており、動的計画法もキャッシュの一種と考えることができます。
コンテンツ配信ネットワーク（CDN）とは、ユーザーの地理的位置、ウェブページの配信元、およびコンテンツ配信サーバーに基づいて、ウェブページやその他のウェブコンテンツをユーザーに配信する分散型サーバーのネットワークです。
CDNは、HTMLページ、画像、動画などの静的コンテンツの配信を高速化する方法として1990年代後半に導入されました。CDNは、コンテンツを世界中の複数のサーバーに複製し、ユーザーの所在地に基づいて配信することで、Webサイトやアプリケーションの速度と可用性を大幅に向上させることができます。ユーザーがコンテンツをリクエストすると、CDNはキャッシュにそのコンテンツのコピーがあるかどうかを確認します。コピーがある場合は、CDNはキャッシュからユーザーにコンテンツを配信します。[ 16 ]
クラウドストレージゲートウェイは、ローカルネットワークを1つ以上のクラウドストレージサービス（通常はAmazon S3などのオブジェクトストレージサービス）に接続するハイブリッドクラウドストレージデバイスです。頻繁にアクセスされるデータのキャッシュを提供し、クラウドストレージサービス内の頻繁にアクセスされるデータへの高速ローカルアクセスを実現します。クラウドストレージゲートウェイは、従来のファイルサーバープロトコルを介してクラウドオブジェクトストレージにアクセスしたり、接続障害時にキャッシュされたデータに継続的にアクセスしたりといった追加の利点も提供します。[ 17 ]
DNSキャッシュは、ドメイン名とIPアドレスのマッピングをキャッシュします。このようなキャッシュを提供するサービスの例としては、 BINDデーモンやキャッシュ型DNSリゾルバライブラリなどがあります。
信頼性の低いネットワーク上で動作する場合、複数のライトバックキャッシュ間で通信が不安定なときに必要となる整合性プロトコルが非常に複雑になるため、ライトスルー動作が一般的です。例えば、Webページのキャッシュや分散ファイルシステム（ NFSやSMBなど）のクライアント側キャッシュは、ネットワークプロトコルをシンプルかつ信頼性の高いものに保つために、通常は読み取り専用またはライトスルーになっています。
ウェブ検索エンジンは、インデックス登録済みのウェブページをキャッシュから利用できるようにすることもよくあります。これは、ウェブサーバー上のウェブページが一時的または永続的にアクセス不能になった場合に役立ちます。
データベースキャッシングは、例えばインデックス、データ辞書、頻繁に使用されるデータサブセットの処理において、データベースアプリケーションのスループットを大幅に向上させることができます。
分散キャッシュ[ 18 ]は、ネットワークホストを使用して、アプリケーションにスケーラビリティ、信頼性、パフォーマンスを提供します。[ 19 ]ホストは同じ場所に設置することも、異なる地理的地域に分散させることもできます。
Android RuntimeとCommon Language Runtimeは、ストレージベースのJITキャッシュを利用する例です。[ 20 ]
バッファとキャッシュの意味論は完全に異なるわけではありませんが、キャッシングのプロセスとバッファリングのプロセスには、意図において根本的な違いがあります。
基本的に、キャッシングは繰り返し転送されるデータの転送においてパフォーマンス向上を実現します。読み取りキャッシュの場合、データ項目が元の場所から少なくとも一度フェッチされていなければ、その後のデータ項目の読み取りは、データの元の場所ではなく、キャッシュのより高速な中間ストレージからフェッチできるため、パフォーマンスが向上しません。書き込みキャッシュの場合、データ項目がキャッシュの中間ストレージに即座に格納され、データ項目の元のストレージへの転送が後段で行われるか、またはバックグラウンドプロセスとして実行されるため、データ項目の最初の書き込み時にデータ項目の書き込みパフォーマンスが向上する可能性があります。厳密なバッファリングとは異なり、キャッシングプロセスは、キャッシュの中間ストレージとデータが格納されている場所との一貫性を維持するために、分散キャッシュコヒーレンシプロトコルに準拠する必要があります。
一方、バッファリングは、通信するプロセス間で新規データとなる場合の転送回数を削減し、多数の小規模な転送に伴うオーバーヘッドを、より少ない規模の大きな転送に分散させます。また、直接転送が不可能な通信プロセス間の仲介役として機能したり、転送に関与する通信プロセスのうち少なくとも一方が必要とする最小限のデータサイズや表現形式を保証したりします。
一般的なキャッシュ実装では、初めて読み書きされるデータ項目は実質的にバッファリングされます。キャッシュはほぼ必ず何らかのバッファリングを伴いますが、厳密なバッファリングは必ずしもキャッシュを伴うとは限りません。
バッファは、CPU命令が周辺機器に格納されたデータに直接アクセスできないため、従来から使用されている一時的なメモリ領域です。そのため、アドレス指定可能なメモリが中間段階として使用されます。さらに、このようなバッファは、ストレージデバイスが必要とするように、大きなデータブロックを組み立てたり分解したりする場合、またはデータが生成された順序とは異なる順序で配信される場合に必要となることがあります。また、バッファ内のデータ全体は通常、順次転送されるため（たとえば、ハードディスクへの転送）、バッファリング自体が、転送速度の向上や、転送遅延の変動やジッターの低減につながる場合があります。これは、遅延を低減することを目的とするキャッシングとは対照的です。これらの利点は、バッファリングされたデータがバッファに一度書き込まれ、バッファから一度読み出される場合でも得られます。
キャッシュは転送パフォーマンスも向上させます。パフォーマンス向上の一因は、複数の小さな転送が1つの大きな転送にまとめられる可能性にあります。しかし、主なパフォーマンス向上は、同じデータがキャッシュから複数回読み取られる可能性が高いこと、または書き込まれたデータがすぐに読み取られる可能性が高いことに起因します。キャッシュの唯一の目的は、基盤となる低速なストレージへのアクセスを減らすことです。また、キャッシュは通常、隣接するレイヤーからは見えないように設計された抽象化レイヤーです。
サーバーが処理するリクエスト数は1日あたり3億～5億件減少。