分散キャッシュの設計

要件と規模の見積もり

まず機能要件と非機能要件を切り分けます。機能要件は「キーに対する値の取得・更新・削除」「TTLによる自動失効」の3操作に集約されます。非機能要件こそがキャッシュ設計の主戦場で、低レイテンシ（p99で1ミリ秒未満）、高可用性、水平スケール、そして「キャッシュミスや障害でDBを守れること」を満たす必要があります。

規模をフェルミ推定で桁だけ押さえます。想定はSNSのタイムラインやプロフィール取得で、ピーク読み取り500,000 QPS、読み書き比を50対1として書き込み10,000 QPS。キャッシュ対象は10億エントリ、1エントリの値が平均1KB、キー・メタデータ込みで実効1.5KBとすると、必要メモリは 10^9 × 1.5KB = 1.5TB。1台あたり実装可能なメモリを64GBと置けば、1.5TB / 64GB ≒ 24台。冗長化とヘッドルームで各シャードにレプリカ1台を足し、余裕を見て合計60〜70台規模のクラスタになります。

帯域も見積もります。読み取り500,000 QPS × 1.5KB = 750MB/s ≒ 6Gbps。これをノード数で割ると1台あたり約100Mbpsで、10GbE NICなら十分に収まります。逆に言えば、この帯域計算がキーサイズやQPSの前提に敏感なので、値が大きいユースケース（画像バイナリ等）ではキャッシュではなくオブジェクトストレージ＋CDNへ寄せる判断になります。

大枠の設計

APIは意図的に薄く保ちます。get(key)、set(key, value, ttl)、delete(key) の3つが基本で、複数キーをまとめる mget / mset を性能最適化として足します。データモデルはキーバリューに限定し、値の構造化はアプリ層の責務とします（キャッシュに検索やJOINを持ち込むと、それはもうキャッシュではなくDBだからです）。

全体構成は「アプリ → クライアントライブラリ（ルーティング担当）→ キャッシュノード群」の3層です。ルーティングをクライアント側に置くのはプロキシのホップを1段削ってレイテンシを稼ぐためですが、ノード一覧の配布が課題になるため、後述のようにルーティング表を中央のディレクトリ（例: ZooKeeper/etcd）から配ります。

キャッシュ配置パターンは要件で選びます。読み取り主体ならcache-asideが基本形です。

# cache-aside（読み取り時）
value = cache.get(key)
if value is None:            # キャッシュミス
    value = db.query(key)
    cache.set(key, value, ttl)
return value

# cache-aside（更新時）: DBを更新し、キャッシュは削除して次回に再読込
db.update(key, new_value)
cache.delete(key)            # set ではなく delete が定石

更新時に cache.set ではなく cache.delete を使うのが定石です。2つの並行更新が「DB書き込み→キャッシュ書き込み」の順序で交差すると、古い値が新しい値を上書きして残る競合が起きるためで、削除にしておけば次の読み取りが必ずDBから正しい値を取り直します。

write-backは書き込みスループットを稼げますが、非同期反映の途中でノードが落ちると確定していない書き込みが消えます。金額など喪失が許されないデータには使わず、閲覧数カウンタのように「多少の誤差と喪失を許容できる」用途に限定するのが判断基準です。この配置戦略の背後には、書き込みをどこで永続化するかというデータベース側の一貫性設計と地続きの問題があります。

主要コンポーネントの深掘り

シャーディング: 一貫性ハッシュと仮想ノード

数十台へキーを分配する方法として、素朴な hash(key) % N は破綻します。ノードが1台増減してNが変わると、ほぼ全キーの割り当て先がずれてキャッシュが総崩れになり、その瞬間にDBへ全リクエストが流れ込むからです。

これを避けるのが一貫性ハッシュ（consistent hashing）です。ハッシュ空間を円環と見なし、ノードとキーを同じ空間へ写像して「キーから時計回りで最初に出会うノード」に割り当てます。ノードを1台足しても割り当てが変わるのは、その新ノードと反時計回り側の隣ノードに挟まれた区間のキーだけで、影響はキー全体の約1/Nに限定されます。

素朴な一貫性ハッシュはノードが円環上に偏ると負荷が不均等になるため、各物理ノードを100〜200個の仮想ノード（virtual node）として円環へばらまきます。仮想ノードを増やすほど区間長の分散が小さくなり、負荷が平準化されます。この仕組みの内部動作は一貫性ハッシュ法とシャーディング戦略で詳述しています。

TTLとエビクション: LRUとLFU

メモリは有限なので、TTLによる時間失効に加え、満杯時にどのキーを追い出すか（エビクション）を決めます。代表がLRU（Least Recently Used、最も長く使われていない物を追い出す）とLFU（Least Frequently Used、最も参照回数が少ない物を追い出す）です。

LRUはバッチ処理などの全件走査で本当のホットキーが追い出される弱点があり、LFUは頻度カウンタが古い人気を引きずる弱点があります。実務ではこの中間を狙ったTinyLFUやW-TinyLFU（小さなLRU窓とLFU本体を組み合わせ、頻度推定にカウント最小スケッチを使う）が採用されます。

ホットキーとレプリケーション

特定キー（急上昇の投稿など）に読み取りが集中すると、そのキーを持つ1シャードだけがCPU・帯域を使い切り、他が空いていても詰まります。一貫性ハッシュは平均を均しますが、単一キーへの集中は解けません。

対策は2段です。第1に、ホットキーだけを複数ノードへ複製し、読み取りをレプリカへ分散します。第2に、アプリのプロセス内に短TTL（数百ミリ秒〜数秒）のローカルキャッシュを置き、集中読み取りをネットワークに出す前に吸収します。ローカルキャッシュは失効までの短時間だけ古い値を許容するトレードオフを伴うため、鮮度要件と引き換えに秒間数万の同一キー読み取りを1台の内部で捌けるかを見て採否を決めます。

ボトルネックとトレードオフ

横にスクロール

キャッシュスタンピード（thundering herd）

人気キーのTTLが切れた瞬間、そのキーを読む全リクエストが同時にミスし、一斉にDBへ殺到して過負荷を起こす現象がキャッシュスタンピード（thundering herd）です。対策は3系統あります。

第1はロックによる単一実行（single-flight）で、最初にミスした1リクエストだけがDBを引き、残りは短時間待って再取得します。第2は確率的早期再計算（probabilistic early expiration）で、失効が近づいたキーを一定確率で失効前に前倒し再計算し、全員が同時に切れる事態を確率的にずらします。第3は論理TTLで、実TTLとは別に値へ「論理的な失効時刻」を埋め込み、論理失効後は古い値を返しつつ裏で1つだけ再計算を走らせます（stale-while-revalidate）。

# 確率的早期再計算の考え方（擬似コード）
value, computed_at, ttl, delta = cache.read(key)
now = current_time()
# delta は再計算コストの目安。乱数と組み合わせ、失効が近いほど前倒し確率が上がる
if value is None or now - computed_at >= ttl + delta * ln(random()):
    value = recompute_and_store(key)
return value

無効化戦略と一貫性のトレードオフ

キャッシュ設計の最難問は無効化です。正確さ（DBの最新値と乖離させない）と、低レイテンシ・低負荷は本質的に綱引きの関係にあります。選択肢は、TTL失効（実装単純だが失効までは古い値を返す）、更新時の明示削除（乖離は最小だがDBとキャッシュの二重書き込みの原子性が問題）、write-through（読みは常に最新だが書き込みが遅い）の組み合わせです。

最終的な設計判断は要件次第です。強い整合が要る残高表示はwrite-throughか都度DB参照、多少の遅延を許せるプロフィールやタイムラインはcache-aside＋短TTL＋ジッタ、という住み分けになります。ここで問われるのは結局、どこまで古い値を許すかというCAP定理的な割り切りであり、キャッシュとは「一貫性を意図的に少し緩める代わりに、桁違いの読み取り性能を買う」仕組みだと整理できます。無効化イベントを複数ノードへ確実に配る部分は、メッセージキューの配信保証の考え方がそのまま効いてきます。