キャッシュ
Cache ・ きゃっしゅ
一度取得・計算した結果を速い場所に写して再利用する仕組み。速さと引き換えに鮮度を手放す。
✦ 30秒で試す — 航海速さを手に入れた瞬間、答えが古くなる危うさも抱え込むヒット率を90%から99%に上げると、DBに届く要求は？予想してみる概要
キャッシュとは、一度取得したり計算したりした結果を手元の速い場所に写しておき、次に同じものが要求されたら写しのほうを返す仕組みです。時間のかかる処理を毎回やり直す代わりに「前回の答えを使い回す」ことで応答を速くし、元の資源（サーバやデータベース）の負荷を減らします。要求されたデータが写しの中にあることを「ヒット」、なくて本来の取得先まで取りに行くことを「ミス」と呼び、全要求のうちヒットした割合をヒット率と呼びます。
この考え方はシステムのあらゆる層に現れます。CPU の内部にはメモリより高速なCPUキャッシュがあり、ブラウザは一度ダウンロードした画像やCSSをディスクに保存し、CDNは世界中の拠点にコンテンツの写しを置き、アプリケーションは重いSQLの結果をメモリに保持します。「遅い場所へのアクセスを、速い場所の写しで肩代わりする」という一つの原理が、規模を変えて何重にも重なっているのです。
ただし写しは写しです。元のデータが書き換わっても、写しは自分からは変わりません。キャッシュを入れた瞬間から、システムには「速いが古いかもしれない答え」と「遅いが正しい答え」の2つが同居します。キャッシュ設計の中心は、ヒット率を上げることと、古い写しをどれだけの時間まで許すかを決めること、この2つの綱引きです。
なぜ生まれたか
コンピュータには「速い記憶装置は小さく高価で、大きく安価な記憶装置は遅い」という宿命的なトレードオフがあります。CPU の演算に対してメモリは遅く、メモリに対してディスクはさらに遅く、ネットワーク越しのアクセスはその何桁も遅い。この段差の積み重なりがメモリ階層で、すべてのデータを最上段の速い装置に置くことは経済的に不可能です。
一方で、アクセスには強い偏りがあります。直前に使ったデータは近いうちにまた使われやすく（時間的局所性）、使ったデータの隣もすぐ使われやすく（空間的局所性）、人気のあるページには要求が集中します。ならば「よく使われる一部だけを速い場所に写しておけば、大部分の要求は速い場所でさばける」。1965年に Maurice Wilkes が小さな高速メモリを主記憶の前に置く「スレーブメモリ」を提案し、1968年に発表された IBM System/360 Model 85 が商用機として初めてこれを実装しました。「キャッシュ」という呼び名も、このころ IBM の論文で使われて広まったものです。全体を速くする代わりに、よく使う部分だけを速くする。コストと速度の矛盾を、偏りを利用して実用的に解いたのが始まりです。
同じ問題は Web の時代にも形を変えて現れました。利用者が増えると、同じ商品ページを表示するために同じ SQL が毎秒何百回も実行され、データベースが先に音を上げます。1997年に仕様化された HTTP/1.1 は Cache-Control ヘッダで「この応答はどこに何秒まで写してよいか」を送り手が宣言できるようにし、2003年には LiveJournal の Brad Fitzpatrick が、複数のサーバで共有できるメモリ上のキャッシュ memcached を作りました。「DB の手前に速い写しを置き、同じ質問には DB を起こさずに答える」という形が、ここで Web アプリケーションの定番になります。
詳細
読み取りの基本形 — キャッシュアサイド
アプリケーションのキャッシュで最も一般的なのは、キャッシュアサイド（cache-aside、別名 lazy loading）という形です。主役はアプリケーション自身で、キャッシュと DB はどちらもアプリから見た「問い合わせ先」にすぎません。アプリはまずキャッシュに GET を投げ、値が返ればそれをそのまま応答します（ヒット）。空が返れば DB に問い合わせ、得た値を TTL（Time To Live、写しの有効期限）付きでキャッシュに SET してから応答します（ミス）。ミスした要求だけが DB まで届き、しかもその1回で写しが作られるので、同じキーへの次の要求からはヒットになります。
ヒットとミスの差は桁で違います。キャッシュ（Redis や memcached）への GET は同じデータセンター内なら1ミリ秒未満で返りますが、DB への問い合わせは、ディスクを読んだり集計したりすれば数十〜数百ミリ秒かかります。平均の応答時間はほぼ「ミス率 × DB の遅さ」で決まるので、ヒット率が90%から99%に上がると、DB に届く要求は10分の1に減ります。そしてヒット率を押し上げているのはアクセスの偏りです。上位の数個のキーに要求が集中していれば、小さなキャッシュでも大部分の要求を手前で折り返せます。
下の部品では、人気の偏った商品ページへの要求が流れています。キャッシュに写しがある商品は手前で折り返し、ない商品は DB まで飛んで遅れて戻ります。DB の行を押して値を書き換えると、何が起きるかを確かめてください。
人気の偏った商品ページへの要求が流れています。写しのある商品はキャッシュで折り返し、ない商品だけが DB まで行きます。右の DB の「商品A」の行を押して値を書き換えてください。
写しは、元が書き換わったことを知りません。TTL が切れるまでの間、キャッシュは古い版を「ヒット」として速く返し続けます。TTL を長くすればヒット率は上がって DB は楽になりますが、古い答えを返す時間も延びます。短くすれば新鮮になる代わりにミスが増えます。キャッシュは速さと鮮度の交換であり、TTL はその交換レートを決めるつまみです。
書き込みの戦略
読み取りの形が決まっても、書き込みのときにキャッシュをどう扱うかで性質は大きく変わります。キャッシュアサイドで最もよく使われるのは「DB を更新してから、キャッシュのキーを消す」やり方です。値を上書きせずに消すのは、次に読まれたときに DB から取り直させるほうが、書き込みの競合で古い値を置いてしまう危険が小さいからです。これを含めて、書き込みの代表的な形は3つあります。
ライトスルー（write-through）は、書き込みをキャッシュと DB の両方に同期して行う形で、写しと元がいつもそろう代わりに、書き込みのたびに両方を待ちます。ライトバック（write-back、write-behind）は、キャッシュに書いた時点で完了とし、DB への反映はあとでまとめて行う形です。書き込みが速く DB の負荷も下がりますが、反映前にキャッシュが落ちれば、書いたはずの値が失われます。CPU キャッシュやディスクの書き込みバッファがこの形で、電源断に備えた仕組みとセットで使われます。ライトアラウンド（write-around）は、書き込みを DB に直接行い、キャッシュは避けて通る形です。書かれただけで読まれないデータで写しの枠を埋めずに済み、キャッシュアサイドの「更新してから消す」もこの仲間です。
なお、キャッシュアサイドとよく並べられるのがリードスルー（read-through）です。こちらはミスしたときに DB を読むのがアプリではなくキャッシュ自身で、アプリはキャッシュだけに話しかけます。コードは簡単になりますが、キャッシュ層が DB の読み方を知っている必要があり、ライブラリや製品の機能として提供されることが多い形です。
どこにキャッシュを置くか
Web システムでは、利用者に近い順に何層ものキャッシュが重なります。ブラウザキャッシュは HTTP の Cache-Control ヘッダで制御され、ネットワークの往復そのものを省ける最速の層です。CDN は利用者に地理的に近い拠点でコンテンツを返し、オリジンのサーバへの到達を減らします。サーバ側ではリバースプロキシが応答をまるごと写し、アプリケーション層では Redis や memcached のようなインメモリストアがセッション情報や DB クエリの結果を保持します。DB 自身も、ディスクから読んだページをメモリに置くバッファキャッシュを持っています。SSG は「ビルド時に全ページを作り置きする」という意味で、キャッシュの考え方を極限まで進めた形と見ることもできます。
層を重ねるほど、同じデータの写しの数が増えます。DB の値を1つ書き換えたとき、アプリのキャッシュ、リバースプロキシ、CDN の全拠点、そして利用者のブラウザにある写しのどれがいつ新しくなるのかを答えられないと、「直したはずなのに古い画面が見える」という問い合わせに答えられません。層ごとに TTL と消し方を決めておくことが、多層キャッシュの設計の中身です。
捨て方こそが難しい
キャッシュの本当の難しさは、貯め方ではなく捨て方にあります。Netscape のエンジニアだった Phil Karlton の言葉として知られる「計算機科学で難しいことは2つしかない。キャッシュの無効化と、名前付けだ」は、このことを言っています。対策は大きく3つあります。一定時間で自動的に捨てる TTL、更新時に明示的に消す無効化（invalidation）、そしてキャッシュのキーに内容の版番号やハッシュを含め、更新後は新しいキーを使わせて古い写しを自然に使われなくする方法です。静的ファイルの名前に app.3f9a1c.js のようなハッシュを付けるのは3つ目の典型で、これなら TTL を1年にしても古いファイルが返ることはありません。
明示的に消す方法にも落とし穴があります。「要求Aがミスして DB から古い値を読む → その間に書き込みBが DB を更新してキーを消す → A が読んでおいた古い値を SET する」という順序になると、消したはずの古い値がキャッシュに戻り、次の TTL 切れまで居座ります。明示的な削除を使うときも TTL は保険として残しておくのが実務の定石です。
容量があふれたときにどれを追い出すかも設計点で、「最も長く使われていないものから捨てる」LRU（Least Recently Used）が代表的なアルゴリズムです。使われた回数で決める LFU（Least Frequently Used）もあり、Redis は最大メモリに達したときの追い出し方をこれらから選べます。
典型的な落とし穴
人気キーの TTL が切れた瞬間、そのキーへの大量の要求が一斉にミスし、全員が同じ重いクエリを DB に投げる。これがキャッシュスタンピード（thundering herd）です。1件なら50ミリ秒で終わるクエリでも、同時に千件来れば DB は詰まり、詰まったせいで写しがなかなか作られず、ミスがさらに積み上がります。対策の基本は「作り直すのは1人だけにする」ことで、次のようにロックを使います。
ロックのほかにも手があります。TTL が切れる少し前から、残り時間が短いほど高い確率で1つの要求だけが先回りして作り直す「確率的な早期再計算」（Vattani らが2015年に XFetch として定式化）は、ロックなしで作り直しを1人に絞れます。HTTP の stale-while-revalidate（RFC 5861）のように、期限切れの値をいったん返しつつ裏で作り直す方法もあります。大量のキーを同時に作ったときに TTL がそろって一斉に切れないよう、TTL に数秒〜数分の揺らぎ（ジッター）を足すのも定番です。
ほかにも、キャッシュサーバの再起動でヒット率がゼロになり、写しがない状態（コールドキャッシュ）の全要求が DB に押し寄せて連鎖的に倒れる事故や、利用者ごとに違う応答を誤って共有キャッシュに載せ、他人の個人情報が表示される事故がよく知られています。前者は再起動前に写しを温めておくウォームアップと、DB 側の流量の天井で、後者は Cache-Control: private や、キャッシュのキーに利用者を含めることで防ぎます。どちらも「キャッシュが空でも正しく、耐えられる速さで動くか」「何を写してよいか」を先に決めておくことが根本の対策です。
設計上のトレードオフ
キャッシュは常に「鮮度」と「速さ・負荷」の交換です。株価や在庫数のように古いと実害が出るデータと、プロフィール画像のように多少古くても困らないデータでは、適切な TTL がまったく違います。古い値が返りうる時間を「最長で TTL 分」と言葉にして、その値を業務側と合意しておくと、設計の判断がぶれません。写しと元が一時的に食い違うことを許すという意味で、キャッシュは結果整合性の一つの形です。
また、キャッシュで隠された性能問題は負荷試験で見えにくく、ヒット率が落ちた本番で初めて顕在化することがあります。「キャッシュがなくても許容できる性能か」を先に確認し、キャッシュはあくまで上乗せとして使うのが健全です。読み取りの高速化という意味では DB のインデックスと目的が似ていますが、インデックスがいつも最新の答えを速く引く仕組みであるのに対し、キャッシュは写しゆえに古くなりうる。この違いを意識しておくと、どちらを使うべきかがはっきりします。
試問
利用者から商品ページへの要求が流れ、アプリはまずキャッシュ（写しの置き場、4件まで）を見ます。写しがあれば手前で答え、なければ DB まで読みに行って写しを置きます。写しは TTL（有効期限）が切れると消えます。DB の行を押すとその商品の値が書き換わり、下のボタンで TTL と「書き換えたときに何をするか」を選べます。
人気の偏った商品ページへの要求が流れています。写しのある商品はキャッシュで折り返し、ない商品だけが DB まで行きます。右の DB の「商品A」の行を押して値を書き換えてください。