キャッシュとは — コンピュータの定義・仕組み・種類と置換戦略
キャッシュの基本を図解と例で分かりやすく解説。コンピュータでの定義・仕組み・種類、置換戦略やロカリティまで初心者向けに整理。
キャッシュとは、コンピュータサイエンスで使われる用語です。キャッシュ（発音は「キャッシュ」/ˈkæʃ/ KASH）の背後にある考え方は非常に単純です。非常に多くの場合、計算の結果を得ることは非常に時間がかかるので、結果を保存することは一般的に良いアイデアです。2種類の記憶媒体が使われています。1つは通常かなり大きなメディアですが、アクセスは「遅い」もので、もう1つはかなり高速にアクセスできますが、一般的には小さいものです。キャッシングの非常に基本的な考え方は、データのコピーを持つためにアクセスが速いメディアを使うことです。コピーとオリジナルの間に違いはありません。オリジナルのデータにアクセスするには、長い時間がかかるかもしれませんし、コストがかかるかもしれません（例：解くのに時間がかかる難しい問題の結果など）。このような理由から、単純にキャッシュからコピーしたデータを利用する方がはるかに「安い」のです。別の言い方をすれば、キャッシュとは、よく使うデータのコピーを一時的に保管しておく場所のことです。このキャッシュにデータのコピーがあると、元のデータを再取得したり再計算したりするよりも、このコピーを使った方が早いのです。これにより、データにアクセスするのに必要な平均時間が短くなります。新しい値をキャッシュに入れるということは、古い値を置き換える必要があることを意味することが多い。どのように置き換える値を選択するかについては、異なる考え（通常は「戦略」と呼ばれます）があります。
バッファはキャッシュと非常に似ています。バッファ内のデータにアクセスするクライアントはバッファがあることを知っていますが、バッファはアプリケーションによって管理されています。キャッシュの場合、データにアクセスするクライアントはキャッシュがあることを意識する必要はありません。
典型的なコンピュータアプリケーションは、非常に似た方法でデータにアクセスします。データが「ブロック」に構造化されていて、個別にアクセスできるとします。アプリケーションがブロックにアクセスするとき、元のブロックに「近い」ブロックにアクセス（または参照）する可能性が非常に高くなります。これは参照の局所性として知られています。このような「ロカリティ」にはさまざまな種類があります。参照のロカリティは、コンピューティングの多くの分野でキャッシュがうまく機能する理由の一つです。
うまく機能するためには、データ全体の量に比べてキャッシュは小さくしなければなりません。キャッシュが大きければ大きいほど、エントリを検索するのに時間がかかります。また、大きなキャッシュは構築コストが高くなります。
キャッシュの目的と利点
- 高速化 — 頻繁に使われるデータを速い記憶領域に置くことで、平均アクセス時間を下げる。
- 帯域幅節約 — 遠隔のストレージや高コストな計算を繰り返さずに済むため、ネットワークやCPUの負荷を減らせる。
- コスト低減 — 高速メモリは高価なので、小さなキャッシュを用いて大容量の安価な記憶を補助する。
キャッシュの基本的な仕組み
- ヒットとミス — 必要なデータがキャッシュにあれば「キャッシュヒット」、なければ「キャッシュミス」。ミスが発生すると元の（遅い）媒体からデータを取得し、キャッシュに格納する。
- 平均アクセス時間（AAT） — AAT = ヒット率 × ヒット時間 + ミス率 × ミスペナルティ。ミスペナルティは遅い媒体から読み込む時間など。
- キャッシュライン（ブロック） — 多くのキャッシュはデータを固定長のブロック単位（キャッシュライン）で扱う。空間的局所性を活かすために、要求されたデータ周辺も一緒に読み込む。
参照の局所性（ロカリティ）の種類
- 時間的局所性（Temporal locality） — 一度参照したデータは近い将来に再度参照されやすい。
- 空間的局所性（Spatial locality） — あるアドレスを参照すると、その近傍のアドレスも参照されやすい。
キャッシュの種類（用途別）
- CPUキャッシュ — L1（最速・最小）、L2、L3（共有で大きめ）などの階層を持つ。命令キャッシュとデータキャッシュに分かれることもある。
- OS/ページキャッシュ（ディスクキャッシュ） — OSがディスクI/Oのためにメモリの一部を使う。ディスクアクセスを減らす。
- ブラウザキャッシュ — Webページや画像、スクリプトを保存して再読み込みを速くする。
- CDN/プロキシキャッシュ — ネットワーク越しのコンテンツ配信を高速化するための中間保存。
- アプリケーションキャッシュ（メモリキャッシュ） — RedisやMemcachedのようなインメモリキャッシュで、頻繁に参照されるデータを保存する。
配置方法・連想度（アソシアティビティ）
- 直接マップ（Direct-mapped） — 各メモリアドレスがキャッシュ内の一つの場所にのみマップされる。実装が単純だが競合が起きやすい。
- 集合連想（Set-associative） — キャッシュを複数のセットに分け、各セット内で複数エントリを持てる方式。N-way と呼ぶ。
- 完全連想（Fully-associative） — 任意のエントリが任意の場所に入れられる（柔軟だがコストが高い）。
置換戦略（エビクションポリシー）
キャッシュが満杯のとき、どのエントリを追い出すかを決めるルールが必要です。代表的な戦略は次の通りです：
- LRU（Least Recently Used） — 最も長く使われていないものを破棄する。一般的で効果的だが実装コストがかかる場合がある。
- FIFO（First-In, First-Out） — 最も古く入ったものから追い出す。
- LFU（Least Frequently Used） — 使用頻度が最も低いものを破棄する。
- ランダム — ランダムに選ぶ。単純でハードウェア実装が容易。
- CLOCK — 擬似LRU。ハードウェア向けに効率化されたアルゴリズム。
- ARCや2Q — 頻度と最近性の両方を考慮する先進的アルゴリズム。
書き込みポリシー（Write policies）
- Write-through — キャッシュに書き込むと同時にバックエンド（メインメモリなど）にも書く。データ整合性は保ちやすいが書き込み遅延が大きい。
- Write-back（Write-back / write-behind） — キャッシュに書き込むだけで、追い出すときにまとめてバックエンドに書く。書き込み回数を減らせるが、データ整合性管理や障害時の復旧が必要になる。
- Write allocate / no-write allocate — 書き込み時にキャッシュにブロックをロードするかどうかの方針。
整合性・無効化（coherency / invalidation）
分散キャッシュやマルチコア環境では、複数のキャッシュ間で同じデータの整合性を保つ必要があります。キャッシュコヒーレンシプロトコル（MESIなど）や、分散システムではTTL（Time To Live）、明示的な無効化（invalidate）／更新通知（invalidate/refresh）などが用いられます。
キャッシュの性能指標とトレードオフ
- ヒット率（Hit rate） / ミス率（Miss rate） — キャッシュの基本的な指標。
- ヒット時間（Hit time） — キャッシュから読み出すのにかかる時間。
- ミスペナルティ（Miss penalty） — ミス時に遅い媒体から取り寄せる時間。
- 容量・レイテンシ・コストのトレードオフ — 大きなキャッシュはヒット率を上げるが遅延・消費電力・コスト増になる場合がある。
キャッシュに関する実務上の注意点・ベストプラクティス
- キャッシュキー設計は重要。キーに含める情報が不適切だとヒット率が下がる。
- 無効化（cache invalidation）は難しい問題。書き換えが頻繁なデータは短いTTLや同期更新を検討する。
- キャッシュスラム/スタンピード（複数の要求が同時にキャッシュミスしてバックエンドを圧迫する）を防ぐため、ロック、リクエスト合流（request coalescing）、遅延再試行を使う。
- キャッシュウォーミング（起動時に主要データを事前に読み込む）でスロースタートを避ける。
- 監視とメトリクス（ヒット率、レイテンシ、ミス時のバックエンド負荷）を継続的に確認する。
短いまとめ
キャッシュは「高速だが小さい」記憶と「遅いが大きい」記憶を組み合わせて、頻繁に使うデータのアクセスを速くする仕組みです。参照のロカリティを利用し、適切なサイズ、配置方式、置換戦略、書き込みポリシーを選ぶことでシステム全体の性能を大幅に向上させられます。一方で、整合性管理や無効化、キャッシュ設計の誤りは性能低下やバグの原因になるため、実装と運用には注意が必要です。
キャッシュの仕組み
キャッシュとは、再利用される可能性の高いデータを保存するためのメモリのブロックのことです。CPUやハードドライブは、WebブラウザやWebサーバーと同様にキャッシュを使用することが多いです。
キャッシュはプールと呼ばれる多数のエントリで構成されています。各エントリは、別の場所にあるデータのコピーであるデータム(データのビット)を保持します。キャッシュは通常、バッキングストアと呼ばれるものを使用します。バッキングストアは、キャッシュに比べてアクセスに時間がかかるか、コストがかかります。ディスクキャッシュは、例えばハードディスクをバッキングストアとして使用します。また、各エントリにはタグと呼ばれる小さな情報が添付されています。このタグは、元のデータが保存されている場所を見つけるために使用されます。
読書のためのキャッシュ
クライアント(CPU、ウェブブラウザ、オペレーティングシステム)は、バッキングストアにあると思われるビットデータにアクセスしたい場合、まず、そのデータがキャッシュにあるかどうかをチェックします。データがキャッシュ内にあれば、クライアントはそれを使用することができ、メインメモリを使用する必要はありません。これはキャッシュヒットとして知られています。したがって、例えば、Web ブラウザプログラムは、ディスク上のローカルキャッシュをチェックして、特定の URL に Web ページのコンテンツのローカルコピーがあるかどうかを確認するかもしれません。この例では、URL がタグであり、ウェブページの内容がデータムです。
他に発生する可能性のある状況は、タグを持つデータムがキャッシュ内で見つからないことです。これはキャッシュミスとして知られています。データムはバッキングストアからフェッチする必要があります。通常は、キャッシュにコピーされ、次回からはバッキングストアからデータを取得する必要がなくなります。
キャッシュのサイズには制限があります。以前にキャッシュされなかったエントリのためのスペースを確保するために、別のキャッシュされたエントリをキャッシュから削除する必要があるかもしれません。削除するのに最適なエントリを見つけるために特別なルールが使用されます。これらのルールは通常ヒューリスティックと呼ばれます。エントリを見つけるために使用されるヒューリスティックは置換ポリシーと呼ばれます。使用される非常に単純なルールは Least recently used (または LRU) と呼ばれます。これは単純に、最も長く前に使用されていたエントリを取ります。他のヒューリスティックはキャッシュアルゴリズムに記載されています。
書くためのキャッシュ
キャッシュはデータの書き込みにも使用することができます。この利点は、一度キャッシュに書き込まれたエントリをクライアントが操作を続けることができることです。
ただし、エントリーはある時点でバッキングストアに書き込まれなければなりません。これが発生するタイミングは、書き込みポリシーによって制御されます。
ライトスルーキャッシュでは、各エントリはキャッシュに格納されるだけでなく、すぐにバッキングストアに書き込まれます。
もう一つの選択肢は、キャッシュへの書き込みのみを行い、後からバッキングストアへの書き込みを行うことです。これは、write-back (またはwrite-behind)キャッシュとして知られています。キャッシュは、まだバッキングストアに書き込まれていないエントリにマークを付けます; 使用されるマークは、しばしばダーティフラグと呼ばれます。エントリがキャッシュから削除される前に、それらのエントリはバッキングストアに書き込まれます。これは遅延書き込みとして知られています。ライトバックキャッシュのミス(ブロックを別のブロックに置き換える必要がある)は、多くの場合、2回のメモリアクセスを必要とします: 1回は必要なデータを取得するためのもので、もう1回はキャッシュからストアに置き換えられたデータを書き込むためのものです。
また、キャッシュポリシーは、特定のデータムをキャッシュに書き込まなければならないと言っているかもしれません。クライアントはキャッシュ内のデータムに多くの変更を加えているかもしれません。それが完了した後、クライアントはキャッシュに明示的にデータを書き戻すように指示することができます。
ノーライトアロケーションとは、リードのみをキャッシュするキャッシュポリシーです。これにより、ライトバックやライトスルーキャッシュの必要性を回避することができます。書き込みは常にバッキングストアに行われます。
クライアントは、バッキングストア内のデータを変更するアプリケーションではありません。バッキングストア内のデータが変更された場合、キャッシュ内のコピーは古くなったり、古くなったりします。あるいは、クライアントがキャッシュ内のデータを更新すると、他のキャッシュ内のそのデータのコピーは陳腐化する。データを意味のあるものに保つためにキャッシュマネージャがお互いに話をすることを可能にする特別な通信プロトコルがあります。これらはコヒーレンシープロトコルとして知られています。
ＣＰＵメモリキャッシュの説明図
置換するエントリの選択
キャッシュは小さく、ほとんどの場合満杯か、ほぼ満杯になります。そのため、新しい値が追加されると、古い値を削除する必要があります。この選択には様々な方法があります。
- 先入れ先出し。キャッシュに追加されたエントリを、最も長い時間前に置き換えてください。
- 最後に使用されたもの。この考え方は上のFIFOと似ていますが、あるエントリが使用されると、そのタイムスタンプ/年齢が更新されます。
- 最も頻繁に使用されるものではありません。これもFIFOの場合と似ていますが、タイムスタンプを使用する代わりにカウンタを使用します。
- エントリーをランダムに選ぶ
歴史
キャッシュという言葉がコンピューティングで初めて使われるようになったのは1967年で、IBM Systems Journalに掲載される科学論文が準備されていました。その記事は、Model 85のメモリの新しい改良についてのものでした。モデル85はIBM System/360製品ラインのコンピュータでした。ジャーナルの編集者は、記事の中で使用されている高速バッファのためのより良い言葉を求めていました。彼は何の情報も得られず、「隠す」という意味のフランス語のcacherからcacheを提案しました。記事は1968年初頭に発表され、著者はIBMから表彰されました。彼らの仕事は広く歓迎され、改善されました。キャッシュはすぐにコンピュータの文献で標準的に使われるようになりました。
キャッシュを使用する場所
ＣＰＵキャッシュ
CPUチップ上またはその近くにある小さなメモリは、はるかに大きなメインメモリよりも高速にすることができます。1980年代以降のほとんどのCPUは、1つ以上のキャッシュを使用しています。パソコンに搭載されている現代の汎用CPUでは、半ダースものキャッシュを搭載している場合があります。各キャッシュは、プログラムを実行するタスクの異なる部分に特化している場合があります。
ディスクキャッシュ
CPUキャッシュは一般的にハードウェアで全て管理されており、他のキャッシュは別の種類のソフトウェアで管理されています。オペレーティングシステムは通常、メインメモリ内のページキャッシュを管理しています。コンピュータサイエンス以外のユーザーは通常、このキャッシュを仮想メモリと呼んでいます。これはオペレーティングシステムのカーネルによって管理されています。
最近のハードドライブにはディスクバッファがあります。これらは「ディスクキャッシュ」と呼ばれることもありますが、これは誤りです。これらのバッファの主な機能は、ディスクへの書き込みの順序付けと読み出しの管理です。ハードドライブのサイズに比べてバッファが非常に小さいため、キャッシュの繰り返しヒットはまれです。
ローカルハードディスクは、リモートサーバー、ローカルテープドライブ、光学ジュークボックスなどの他のストレージデバイスに比べて高速です。ローカルハードディスクをキャッシュとして使用することは、階層型ストレージ管理の主な概念です。
ウェブキャッシュ
WebブラウザやWebプロキシサーバーは、WebページなどのWebサーバーからの過去の応答を保存するためにキャッシュを使用しています。ウェブキャッシュは、ネットワークを介して送信する必要のある情報量を減らします。以前にキャッシュに保存された情報は、多くの場合、再利用することができます。これにより、ウェブサーバーの帯域幅や処理要件が削減され、ウェブのユーザーの応答性を向上させることができます。
最近のウェブブラウザは内蔵のウェブキャッシュを使用していますが、インターネットサービスプロバイダや組織によっては、キャッシングプロキシサーバを使用している場合もあります。これは、そのネットワークのすべてのユーザー間で共有されるウェブキャッシュです。
また、検索エンジンは、インデックスされたウェブページをキャッシュから利用できるようにすることもよくあります。例えば、Googleは各検索結果の横に「キャッシュされた」リンクを用意しています。これは、ウェブページがウェブサーバーから一時的にアクセスできない場合に便利です。
信頼性の低いネットワークでのキャッシング
書き込みスルー動作は、信頼性の低いネットワーク（イーサネットLANのようなもの）では一般的です。このような場合、複数の書き込みキャッシュが使用されている場合に、書き込みキャッシュ内のデータが意味のあるものであることを確認するために使用されるプロトコルは非常に複雑です。
例えば、ウェブページキャッシュやクライアント側のネットワークファイルシステムキャッシュ（NFSやSMBのようなもの）は、ネットワークプロトコルをシンプルで信頼性の高いものにするために、一般的に読み取り専用または書き込み専用になっています。
バッファとキャッシュの違い
バッファとキャッシュは相互に排他的なものではなく、一緒に使われることも多いです。しかし、これらが使用される理由は異なります。バッファは、CPU命令が周辺機器に保存されているデータを直接アドレス指定できないため、従来から使用されているメモリ内の場所です。コンピュータのメモリは、中間ストアとして使用されます。
さらに、このようなバッファは、（ストレージデバイスによって要求されるように）大規模なデータブロックが組み立てられたり分解されたりする場合や、データが生成された順序とは異なる順序で配信される場合に実行可能であるかもしれません。また、データのバッファ全体は通常、順次転送される（例えばハードディスクへの転送）ので、バッファリング自体が転送性能を向上させることもあります。これらの利点は、バッファリングされたデータが一度バッファに書き込まれ、一度バッファから読み出された場合でも存在します。
キャッシュは転送性能も向上させます。増加の一部は、複数の小さな転送が1つの大きなブロックに結合される可能性に由来しています。しかし、主な性能向上は、同じデータがキャッシュから何度か読み込まれるか、書き込まれたデータがすぐに読み込まれる可能性が高いために発生します。キャッシュの唯一の目的は、基礎となるより遅いストレージへのアクセスを減らすことです。また、キャッシュは通常、隣接するレイヤーからは見えないように設計された抽象化レイヤーでもあります。そうすれば、アプリケーションやクライアントはキャッシュがあることに気づかないかもしれません。
質問と回答
Q: キャッシュとは何ですか?
A: キャッシュとは、コンピュータサイエンスで使用される用語で、頻繁に使用されるデータのコピーを保存して、元のデータを再取得または再計算するよりも高速にアクセスできるようにすることを指します。
Q: キャッシングはどのように機能するのですか?
A: キャッシュは2種類の記憶媒体を使うことで機能します。1つは通常かなり大きいがアクセスに時間がかかるもの、もう1つはより速くアクセスできるが一般に小さいものです。キャッシュの背後にある考え方は、データのコピーを保存するために高速なメディアを使用することで、元のデータへのアクセスにかかる時間やコストを削減することです。
Q: バッファとは何ですか?
A: バッファは、より速いアクセスのためにデータのコピーを保存するという点でキャッシュと似ていますが、バッファでは、データにアクセスするクライアントはバッファがあることを知り、それがアプリケーションによって管理されるのに対し、キャッシュではクライアントはキャッシュがあることを意識する必要がありません。
Q:参照の局所性とは何ですか?
A:参照の局所性とは、アプリケーションが構造化されたデータの特定のブロックにアクセスするとき、最初にアクセスしたブロックに近い他のブロックにもアクセスする可能性があることを意味します。キャッシュは通常、利用可能なすべてのデータと比較して小さいので、これはキャッシュをうまく機能させるのに役立ちます。
Q:なぜ大きなキャッシュは、エントリーの検索に時間がかかるのですか?
A:キャッシュが大きいと時間がかかるのは、より多くの情報が格納されているため、検索に時間がかかるからです。また、ストレージに多くのリソースを必要とするため、より高価になります。
Q:局所性は、キャッシュをより良く機能させるのに役立ちますか?
A: ロカリティはキャッシュをより良く動作させるのに役立ちます。なぜなら、アプリケーションが構造化データの特定のブロックにアクセスするとき、その近くの他のブロックも必要になる可能性が高く、その場合、他の場所から取得したり再計算したりする代わりに、キャッシュから迅速に取得することができます。
百科事典を検索する