構造的アルゴリズム
\( \def\vector#1{\boldsymbol{#1}} \)

キャッシュ

Takami Torao #LRU #MRU
  • このエントリーをはてなブックマークに追加

概要

キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムであり、そのデータを一時的に保存する高速な記憶領域である。本質的には局所参照性 (locality of reference)、すなはち「直近でアクセスのあったデータは近い将来に再度アクセスされる可能性が高い」という原理に基づいて機能する。具体的には、アクセス頻度の高いデータ、次にアクセスされることが予想されるデータ、あるいは生成や取得に多大な時間を要するデータを、高速なキャッシュに一時的にコピーし、以後、下層のオリジンデータではなくキャッシュにアクセスすることで、アプリケーションの応答を短縮してシステム全体の処理能力を向上させる。キャッシュシステムはキャッシュヒットによってデータをキャッシュから高速に取得することで、本来の経路 (オリジンデータへのアクセス) で取得するよりもはるかに低いレイテンシでアクセスすることを可能にする。

キャッシュの性能を最大化するためには、そのサイズとアクセス方法の最適化が不可欠である。キャッシュサイズが過度に小さい場合、データが頻繁に入れ替わるスラッシング (thrashing) が発生し、キャッシュミスの頻度が大幅に増大して効率が著しく低下する可能性がある。一方で、必要以上に大きいキャッシュはメモリ資源を消費し、リソースの使用効率を低下させるだけでなく、管理コストの増大やキャッシュ汚染 (cache pollution) のリスクもともなく。

キャッシュのサイズとアクセス方法を最適化する必要がある。キャッシュサイズが小さい場合、データの入れ替えが頻繁に発生して効率が低下する可能性がある。一方で、大きすぎるキャッシュは余分な領域が占有されるためリソースの効率が低下する。システムはデータをキャッシュから取得することで、本来の経路で取得するよりも高速にアクセスすることができる。

キャッシュの実態はその導入目的や配置レイヤーに応じて多岐にわたる。最も一般的なキャッシュは高速なメモリだが、Web プロキシのように大容量かつ永続性を必要とする場合にはローカルストレージ (ディスク) が使用されることもある。

Table of Contents

  1. 概要
  2. キャッシュ配置
  3. キャッシュポリシー
    1. 読み込みポリシー
    2. 書き込みポリシー
  4. キャッシュ置換アルゴリズム
  5. キャッシュ一貫性モデル
  6. キャッシュの構造とデータ表現
  7. キャッシュの監視とメトリクス
  8. 障害耐性と復旧
  9. 参考文献

キャッシュ配置

システムアーキテクチャのどこに、どのような形式でキャッシュを組み込むかは、キャッシュのアクセス速度、容量、データ一貫性の管理、そしてシステム全体のコストと複雑さに直接的な影響を与える。

キャッシュの配置は、プロセッサの回路内に配置されるナノ秒オーダーの超高速なハードウェアキャッシュから、ネットワークを介してアクセスされるミリ秒オーダーの分散型キャッシュ、あるいはユーザデバイス上のローカルキャッシュに至るまで多層的なレイヤーに存在し、それぞれが異なる目的を持っている。

  • CPU キャッシュ (L1, L2, L3 キャッシュ): プロセッサのコア内部 (L1) またはすぐ近く (L2, L3) に配置される、高速で小容量のハードウェアキャッシュ。命令とデータの両方をキャッシュし、CPU とメインメモリ間の速度ギャップを埋める。非常に高いキャッシュヒット率と数ナノ秒の極めて低いアクセスレイテンシーを持つが、コストが高く容量が限られている。マルチコアプロセッサ環境では、複数の CPU コアが同じデータをキャッシュし、書き込みが発生した際に他のキャッシュとの整合性を保つキャッシュコヒーレンシ問題 (cache coherent problem) が発生する。この問題はハードウェアレベルのコヒーレントプロトコル (coherent protocol) によって厳密に管理されている。

  • メインメモリキャッシュ (OS レベルのキャッシュ): オペレーティングシステム (OS) がディスク I/O の性能を向上させるためにメインメモリの一部をキャッシュとして使用する。代表例にページキャッシュやバッファキャッシュがあり、これらはファイルシステムへのアクセスを高速化する。CPU キャッシュより低速だがディスク I/O より格段に高速で、ほとんどの場合、アプリケーションからは透過的に利用される。

  • 分散キャッシュ (Distributed Cache): 分散システムにおいてネットワーク越しにアクセスされるキャッシュシステム。通常、インメモリデータストアとしてアプリケーションとは独立して運用される。Redis, Memcached Hazelcast などが代表例である。高いスケーラビリティと可用性を提供し、複数のアプリケーションインスタンス間でデータを共有できる。データベースアクセスや HTML レンダリングなどの時間のかかる処理の負荷を大きく軽減するが、ネットワークレイテンシーが伴う。また複数のノード間で共有されるデータの一貫性管理が複雑になり、キャッシュコヒーレンシ問題の解決にはリースやコールバックといった高度なメカニズムが必要となる。

  • CDN (Content Delivery Network): Web サイトの静的コンテンツ (画像、CSS、JavaScript、動画など) を世界中の地理的に分散したサーバ (エッジサーバ) にキャッシュし、ユーザに最も近いサーバから配信するネットワークサービス。コンテンツ配信のレイテンシーを削減し、オリジンサーバの負荷を劇的に軽減する。主に読み込み専用のコンテンツに利用され、キャッシュ更新は比較的緩やかな一貫性モデル (TTL など) に基づいて行われる。

  • プロキシキャッシュ (Proxy Cache): クライアントとオリジンサーバの間で、クライアントからのリクエストを仲介しつつ、取得したコンテンツをキャッシュするサーバ。Web プロキシサーバや、アプリケーションサーバ手前で負荷分散とキャッシュを兼ねるリバースプロキシ (Nginx, Varnish など) が含まれる。企業 LAN 内での Web アクセスの高速化や、Web サーバの負荷軽減を目的に使用される。全ユーザの共有キャッシュとして機能し、特定のコンテンツに対する重複リクエストを削減する。

  • ブラウザキャッシュ (Browser Cache): Web ブラウザがアクセスした Web ページのリソース (画像、CSS、JavaScript など) をユーザのローカルデバイス上に保存するキャッシュ。ユーザが同じページやリソースに再アクセスしたときの表示速度を大幅に向上させ、ネットワークトラフィックを削減する。主に Cache-Control などの HTTP ヘッダによって制御される。

キャッシュポリシー

キャッシュデータの読み書きにおいて、キャッシュと下層ストレージ (データベースやディスクなど、オリジンデータが格納されている場所) 間でデータをどのように同期し、一貫性を保つかを定義する一連の規則をキャッシュポリシーと呼ぶ。このポリシーは、キャッシュの性能、データの一貫性レベル、および実装の複雑性に直接影響を及ぼすため、アプリケーション要件に応じて慎重に選択されるべきである。

読み込みポリシー

データをキャッシュに読み込む際の振る舞いを決定する。

  • Cache-Aside (Lazy Loading): アプリケーションが直接キャッシュにデータを要求し、キャッシュにデータが存在しない場合 (キャッシュミス) にのみ、アプリケーション自身が下層ストレージからデータを読み込み、その後キャッシュに格納する方式。実装がシンプルで、キャッシュに不要なデータが読み込まれることを防ぐ性質を持つ。ただし、キャッシュミスのときには必ず下層ストレージへのアクセスとデータ読み込みが発生するため、アプリケーションのレイテンシーが増加する可能性がある。

  • Cache-Through: アプリケーションは常にキャッシュに対して読み込み要求を行う。キャッシュにデータが存在しない場合でも、アプリケーションが直接下層ストレージに問い合わせることはない。代わりに、キャッシュ自身が透過的に下層からデータを読み込み、キャッシュに格納した上で、アプリケーションに返す。アプリケーションはキャッシュ層のみを意識すれば良いため、データ取得ロジックがキャッシュ層にカプセル化される。これによりアプリケーションのコードが完結になる一方で、キャッシュミス時のデータ取得ロジックをキャッシュ自で吸収する仕組みが必要となるため、Cache-Aside より実装が複雑になる場合がある。

書き込みポリシー

データをキャッシュに読み込むときの振る舞いを決定する。

  • Write-Through: データがキャッシュに書き込まれると同時に、即座に下層ストレージにも書き込まれる方式。キャッシュと下層ストレージ間のデータの一貫性が常に高く保たれるため、データの信頼性が最優先される場合に適している。ただし、下層への書き込みレイテンシーが、キャッシュへの書き込みレイテンシーに常に加算されるため、書き込み性能は比較的低くなる。キャッシュに障害が発生しても、データは既に永続ストレージに書き込まれているため、データ損失リスクは低い。

  • Write-Back (Write-Behind): データはまずキャッシュにのみ書き込まれ、後でまとめて (または非同期で) 下層ストレージに書き込まれる方式。書き込みレイテンシーが非常に低く、複数の書き込み処理をバッチ操作でまとめて下層ストレージにコミットできるため、I/O が効率化されて高いスループットを実現できる利点がある。ただし、下層ストレージへの書き込みが完了する前にキャッシュが障害を起こした場合にデータ損失のリスクが存在する。このリスクを軽減するためには、キャッシュデータの永続化やレプリケーションといった障害耐性メカニズムと組み合わせる必要がある。

  • Write-Around: データはキャッシュを素通りし、直接下層に書き込まれる方式。キャッシュは読み込み操作のみを扱う。頻繁に更新される再利用頻度の低いデータによるキャッシュ汚染を防ぐ点で有利である。ただし、書き込まれたデータが直後に読み込まれる read-after-write のシナリオでは、必ずキャッシュミスが発生するするためレイテンシが増加する可能性がある。

キャッシュ置換アルゴリズム

一般にはキャッシュの領域は有限であり、キャッシュがいっぱいになると既存のデータを破棄する必要が出てくる。キャッシュ置換アルゴリズム (cache replacement algorithm) はキャッシュからどのようにデータを破棄するかを決定するための戦略である。これらのアルゴリズムはアプリケーションのアクセスパターン、キャッシュの容量、および求められる性能に応じて選択される。

LRU: Least Recently Used

最後にアクセスしてから最も長い時間が経過しているデータを破棄する戦略のアルゴリズム。参照局所性の原則に基づき、最近使われたデータは将来も使われる可能性が高いという仮説に基づく。最近アクセスのあったデータをキャッシュの一番上に保持することで、キャッシュの上限に達したときに一番下のデータを破棄するようなデータ構造を取る。LRU は理解と実装が簡単で良好な結果が得られるため、Web キャッシュで使用される最も一般的な置換アルゴリズムである。

MRU: Most Recently Used

LRU とは逆に、最も最近アクセスしたデータを最初に破棄する戦略のアルゴリズム。MRU は、一度アクセスのあったデータがしばらく参照されなかったり、古いデータほどアクセスされる可能性が高い場合に使用される。

LFU: Least Frequently Used

アクセス頻度の最も低いデータを破棄する戦略のアルゴリズム。使用頻度が高いデータは将来も使われる可能性が高いという仮定に基づく。このアルゴリズムはキャッシュのエントリーごとにカウンターを使用してアクセスの頻度を追跡する。一時的に高頻度のアクセスがあったがそれ以外では使用されていないデータをキャッシュアウトできない欠点がある。サーバ再起動後のような初期段階でキャッシュ内のすべてのアイテムは事実賞「新しいもの」と見なされたり、初期のトラフィックパターンが非常に偏っている場合は中長期的に影響が残るようなコールドスタート問題が考えられる。またカウント値のオーバーフローも考慮しなければならない。

ARC: Adaptive Replacement Cache

LRU と LFU の利点を組み合わせ、システムのアクセスパターンに動的に適応するアルゴリズム。IBM が開発し特許を保持している。「頻繁に参照されたもの」と「最近使用されたもの」の両方を管理し、両方の最近の削除履歴を保持することでそれぞれのリストのサイズを調整する。LRU や LFU 単体より高いキャッシュヒット率を達成することが多いが、実装はより複雑である。

FIFO: First In First Out

キャッシュに最も古くから存在するデータを削除する戦略のアルゴリズム。実装は単なるキュー構造であるため非常にシンプルだが、データが追加された順番しか考慮しないため、参照頻度や参照局所性を考慮せず、頻繁に使われるデータも古いという理由で破棄される可能性がある。

LIRS: Low Inter-reference Recency Set

参照時間間隔 (recency) と参照頻度 (frequency) の両方を考慮するアルゴリズム。特に、参照時間間隔が短いデータ (つまり最近も使われており将来も使われる可能性が高いデータ) を優先的に保持する。LRU や LFU より高いキャッシュヒット率を達成できる場合が多いが、実装はより複雑化し、多くのメタデータを必要とする。

Random

キャッシュがいっぱいになったとき、破棄するデータをランダムに選択する。実装が最も簡単でオーバーヘッドが少ない。ただし、キャッシュヒット率は他のアルゴリズムに比べて低い傾向がある。特定のアクセスパターンに対しては非常に非効率になる可能性がある。

TTL: Time to Live

各データに生存期間 (有効期限) を設定し、その期間が経過したデータを自動的にキャッシュから削除する。これは、厳密な一貫性は必要ないが、ある程度のデータ鮮度が求められる場合に有効である。データの一貫性維持の一環として利用されることが多く、特に揮発性のあるデータや、データが常に最新である必要が無い場合に適している。

一度しか利用されない、あるいは利用頻度が極めて低いデータがキャッシュ内に大量にロードされることで、本来キャッシュされるべき頻繁に利用されるデータが追い出されてしまう現象をキャッシュ汚染 (cache pollution) と呼ぶ。この問題は、不適切な置換アルゴリズムや読み込みポリシー (例えば Write-Around を使用しない Write-Through) によって引き起こされることがある。

Java では LinkedHashMapを簡易的なキャッシュ置換アルゴリズムとして使用することができる。このクラスは accessOrder に true を指定すると LRU アルゴリズム、false (デフォルト) を指定すると FIFO アルゴリズムの動作となる。

キャッシュ一貫性モデル

複数のキャッシュやクライアントが存在する分散システムにおいて、共有データに対する読み書き操作がどのような順序で見えるかや、キャッシュされたデータがいつ最新であると見なされるかを定義する規則の集合をキャッシュ一貫性モデル (cache consistency model) と呼ぶ。このモデルはシステムの複雑性、性能、可用性、および信頼性の間のトレードオフを決定する。

厳密な一貫性 (strong consistency, strict consistency) は常に最新のデータがすべてのキャッシュに反映されることを保証する。あるノードがデータを更新したとき、その更新は即座に他のすべてのノードから参照可能でなければならない。データの整合性は最も高く保たれるが、複数のキャッシュ間で厳密な同期が必要となるため、レイテンシーが大きくなり、システムのスケーラビリティや可用性が犠牲になる傾向がある。

データが書き換えられたとき、そのデータをキャッシュしている他のノードに対してキャッシュを無効化する通知を行う方式を Write-Invalidate、キャッシュの内容を新しいデータで更新する通知を行う方式を Write-Update と呼ぶ。またリース (lease) はキャッシュがデータの所有権を持つ期間 (リース期間) をサーバが保証し、その期間内の更新はサーバで遅延させる。リース方式はキャッシュのクロックドリフトが起きたときに既に期限が切れているキャッシュデータを有効と見なす可能性があることに注意。

結果整合性 (eventual consistency) は、ある時点ではキャッシュ間でデータが不整合な状態であっても、ネットワークやサーバの障害がない限り、最終的にはすべてのキャッシュが一致する状態に収束売ることを保証する。厳密な動機を必要としないため、高い可用性とスケーラビリティを実現できる。しかし、一時的に不整合が発生する可能性があるため、アプリケーションはそこの不整合を許容できる設計でなければならない。

セッション一貫性 (session consistency は、特定のユーザのセッション内では、ユーザは自身が書き込んだデータをそのセッション内で読み取れることを保証する。ただし、他のセッションに対しては書き込みが即座に反映されないこともある。結果整合性よりは強い保証を提供するが、厳密な一貫性よりは緩やかである。ユーザ体験を損なうことなく、高い可用性とスケーラビリティを両立させるために使用されることがある。

キャッシュの構造とデータ表現

キャッシュシステムでは、データの効率的な保存と検索を実現するための内部構造とデータ表現の方法が重要となる。Key-Value 型のデータ構造は多くのキャッシュで最も基本的な構造である。一方、単なるキーによる点検策だけでなく、データの範囲やソートといった取得要件がある場合には、B-Tree や B+Tree のようなツリー構造も考慮される。

Web アプリケーションの性能を向上させるために、データベースから取得した表形式のデータや Web API の JSON レスポンスをそのままキャッシュに格納することが一般に行われる。またオブジェクトキャッシュ (object cache) と呼ばれるキャッシュシステムでは、特定のプログラミング言語環境からアプリケーションで直接利用可能なオブジェクトとしてキャッシュすることができる。これはオブジェクトのシリアライズ/デシリアライズの実装コストを削減し、アプリケーションの処理を簡素化できる利点がある。

また、キャッシュに保存されるデータの容量を削減するためにデータ圧縮を行うことがある。これにより物理的なキャッシュ容量をより効率的に活用し、多くのデータをキャッシュ上に保持することができるただし、データの圧縮と展開には CPU リソースを消費するため、そのオーバーヘッドと、容量効率向上のバランスを慎重に検討する必要がある。

キャッシュの監視とメトリクス

キャッシュシステムの性能と健全性を評価し、最適化を行うためには、継続的な監視と適切なメトリクス (指標) の収集が不可欠である。最も基本的な指標にヒット率 (hit rate) とミス率 (miss rate) がある。ヒット率は、要求されたデータがキャッシュ内に存在し、オリジンデータを読み出すことなくキャッシュから直接取得できたリクエストの割合を示す、キャッシュの有効性を示す主要な指標である。一方、ミス率は、データがキャッシュに存在せず、オリジンデータを読み出す必要のあったリクエストであり、ヒット率と合わせてキャッシュの効率性を評価する。通常、ヒット率が高いほどバックエンドシステムへの負荷が軽減されており、全体的な性能が向上していることを意味する。

キャッシュに対するレイテンシー (latency) とスループット (throughput) も重要な指標である。これらのメトリクスは、キャッシュがアプリケーション要求を満たしているか (キャッシュを導入した効果が出ているか)、あるいは過負荷に陥っていないかを判断するために用いられる。

また、キャッシュが物理メモリまたは割り当てられた記憶領域をどれだけ消費しているかを示すメモリ使用量も注意する必要がある。過剰なメモリ使用はコスト増につながり、不足はミス率の増加につながるため、適度なバランスを見つけることが求められる。これは設置されるキャッシュの数を増減させるときの容量設計に不可欠であり、メモリの枯渇が性能劣化やシステム不安定化につながることを防ぐために継続的に監視する必要がある。

障害耐性と復旧

キャッシュシステムはその高速性という利点と引き換えに、障害発生時のデータ損失やサービス停止のリスクを伴う場合がある。

データ永続化はキャッシュデータをディスクなどの永続ストレージに保存する。これにより、キャッシュサーバの再起動やクラッシュが発生した場合でも、キャッシュされているデータを失うことなく復旧することができる。さらにレプリケーションを行うことで、複数のキャッシュノード間でデータを複製し、いずれかのノードが故障しても他のレプリカが処理を引き継ぐことができる。これはキャッシュの単一障害点 (SPoF; single point of failure) を回避し、システムの可用性を高める。レプリケーションには大きく同期と非同期があり、それぞれ一貫性の保証と性能のトレードオフがある。

キャッシュデータが破損したり、意図しない不整合状態に陥った場合に、パージ (purging) やキャッシュクリアの機能が必要な場合がある。これは特定のキャッシュエントリ、またはキャッシュ全体を強制的にクリアし再構築することを可能にする機能である。異常な状態から迅速に回復するために必要であり、緊急時のトラブルシューティングとして使うことができる。

キャッシュがほとんど空の状態でシステムの駆動を始めることをコールドスタート (cold start) と呼ぶ。コールドスタートの状況下では、初期の大量のキャッシュミスによって下層に過度な負荷がかかり、システム全体の性能が著しく低下するスラッシング (thrashing) が発生する可能性がある。

これを回避するため、特に大規模なシステムでシステム全体の再起動やフェイルオーバーなどの計画的切り替えを行うときに、オリジンデータを適切にキャッシュするウォームアップ (warm-up, preloading) が必要になることがある。キャッシュが空の状態で駆動を開始する予備動作は、頻繁にアクセスされるであろうデータを事前に下層から読み込みキャッシュに格納する、あるいは過去のアクセスログに基づいて重要なデータをウォームアップするといった手法が用いられる。

参考文献

  1. Areej M. Osman and Niemah I. Osman. A Comparison of Cache Replacement Algorithms for Video Services. International Journal of Computer Science & Information Technology (IJCSIT) Vol 10, No 2, April 2018