分散キャッシュ（Redis）── キャッシュ戦略と整合性のトレードオフ
扱うCS概念：キャッシュ置換アルゴリズム（LRU/LFU）、キャッシュ無効化、シャーディング、冪等性
この章で何ができるようになるか：キャッシュの各戦略（Cache-Aside, Write-Through, Write-Back）をユースケースに応じて選択できるようになる。キャッシュが引き起こす整合性問題とその対処法を説明できるようになる。
問題設定
「DB が遅い」を解決する最も手軽な手段がキャッシュだ。しかしキャッシュを導入した途端、整合性の問題が生まれる。
「キャッシュのデータ」と「DBのデータ」が食い違う
→ ユーザーAが更新した内容が、ユーザーBには古い値が見える
→ 在庫が0なのにキャッシュには1が残っている
→ 決済済みなのにキャッシュにはカート情報が残っているさらに、大規模になると：
Thundering Herd（サンダリングハード）：
人気記事のキャッシュが切れた瞬間、数千リクエストが一斉にDBへ流れ込む
Cache Stampede（キャッシュスタンピード）：
同じキーへの並行リクエストが全てキャッシュミスし、同じDBクエリを並行実行する
Cold Start：
サーバー再起動後、キャッシュが空の状態でリクエストが殺到するこれらを理解するには、キャッシュの基本戦略を整理することが必要だ。
3つのキャッシュ書き込み戦略
1. Cache-Aside（Lazy Loading）
最も一般的なパターン。アプリケーションがキャッシュとDBの両方を管理する。
def get_user(user_id: int) -> dict:
# 1. キャッシュを確認
cached = redis.get(f"user:{user_id}")
if cached:
return json.loads(cached) # キャッシュヒット
# 2. キャッシュミス → DB から取得
user = db.query("SELECT * FROM users WHERE id = %s", user_id)
# 3. キャッシュに書き込み（TTL=3600秒）
redis.setex(f"user:{user_id}", 3600, json.dumps(user))
return user
def update_user(user_id: int, data: dict):
# 4. DB を更新
db.execute("UPDATE users SET ... WHERE id = %s", user_id)
# 5. キャッシュを削除（次回読み込み時に再生成させる）
redis.delete(f"user:{user_id}")sequenceDiagram
participant App
participant Cache as Redis
participant DB
App->>Cache: GET user:123
Cache-->>App: nil（ミス）
App->>DB: SELECT * FROM users WHERE id=123
DB-->>App: {id:123, name:"Alice"}
App->>Cache: SET user:123 "{...}" EX 3600
App->>App: データを返す
Note over App,DB: 更新時
App->>DB: UPDATE users SET name="Bob"
App->>Cache: DEL user:123✅ 長所：読み込みが多いユースケースに最適。キャッシュが落ちてもDBに直接アクセスできるため障害耐性が高い。
❌ 短所：初回アクセス（コールドスタート）は必ずキャッシュミスする。書き込みとキャッシュ削除の間にわずかな不整合窓がある。
2. Write-Through
書き込み時にキャッシュとDBの両方を同時に更新する。
def update_user(user_id: int, data: dict):
# DB と キャッシュを同時更新
db.execute("UPDATE users SET ... WHERE id = %s", user_id)
redis.setex(f"user:{user_id}", 3600, json.dumps(data))
# キャッシュは常に最新✅ 長所：キャッシュが常に最新。読み込みは必ずキャッシュヒット。
❌ 短所：書き込みレイテンシが増加（DB + キャッシュの2回）。書き込まれたデータが二度と読まれない場合も必ずキャッシュに書く（無駄なメモリ消費）。
3. Write-Back（Write-Behind）
書き込みはキャッシュのみ行い、DBへの書き込みは非同期にバッファリングする。
def update_user(user_id: int, data: dict):
# キャッシュのみ即時更新（高速）
redis.setex(f"user:{user_id}", 3600, json.dumps(data))
# DB への書き込みはキューに入れる（非同期）
message_queue.publish("db_write", {
"table": "users",
"id": user_id,
"data": data
})
# バックグラウンドワーカーが DB に書き込む
def db_writer():
while True:
msg = message_queue.consume("db_write")
db.execute("UPDATE users SET ... WHERE id = %s", msg["id"])✅ 長所：書き込み速度が極めて高速。DBへの書き込みをバッチ処理できる（I/O効率）。
❌ 短所：キャッシュが落ちるとデータロス。実装が複雑。強整合性が必要な場面（決済など）には使えない。
3つの比較
| Cache-Aside | Write-Through | Write-Back | |
|---|---|---|---|
| 読み込み速度 | 初回は遅い | 常に速い | 常に速い |
| 書き込み速度 | 速い | やや遅い | 非常に速い |
| 整合性 | 弱（短い窓あり） | 強 | 最弱 |
| データロスリスク | なし | なし | あり |
| 向いているユース | 読み多・書き少 | 読み書きバランス | 書き込み集中 |
キャッシュ置換アルゴリズム
Redis は maxmemory-policy でエビクション（削除）戦略を設定できる。
# redis.conf
maxmemory 4gb
maxmemory-policy allkeys-lruLRU（Least Recently Used）
直近で使われていないものを削除する。実装は「ハッシュマップ + 双方向リンクリスト」の組み合わせが O(1) で実現できる。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict() # 挿入順を保持
def get(self, key: str):
if key not in self.cache:
return None
# アクセスされたら末尾（最新）に移動
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: str, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
# 先頭（最も古い）を削除
self.cache.popitem(last=False)LFU（Least Frequently Used）
最もアクセス頻度が低いものを削除する。
import heapq
from collections import defaultdict
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache: dict = {} # key → value
self.freq: dict = defaultdict(int) # key → 頻度
self.freq_map: dict = defaultdict(OrderedDict) # 頻度 → {key: ...}
self.min_freq = 0
def _update(self, key: str):
f = self.freq[key]
del self.freq_map[f][key]
if not self.freq_map[f]:
del self.freq_map[f]
if self.min_freq == f:
self.min_freq += 1
self.freq[key] += 1
self.freq_map[f + 1][key] = True
def get(self, key: str):
if key not in self.cache:
return None
self._update(key)
return self.cache[key]
def put(self, key: str, value):
if key in self.cache:
self.cache[key] = value
self._update(key)
else:
if len(self.cache) >= self.capacity:
# 最小頻度の中で最も古いものを削除
evict_key, _ = self.freq_map[self.min_freq].popitem(last=False)
del self.cache[evict_key]
del self.freq[evict_key]
self.cache[key] = value
self.freq[key] = 1
self.freq_map[1][key] = True
self.min_freq = 1LRU vs LFU の選択
| シナリオ | 向いているアルゴリズム |
|---|---|
| SNSのバズり投稿（一時的に爆発的アクセス） | LRU（バズが終わったら自然と削除） |
| 商品の定番人気ページ（長期的に人気） | LFU（人気のあるページを保持） |
| 動画・ニュースの時系列コンテンツ | LRU（新しいものが次々と参照される） |
Thundering Herd 対策
人気コンテンツのキャッシュが期限切れした瞬間、多数のリクエストがDBに殺到する問題だ。
対策1：Mutex（分散ロック）
最初の1リクエストだけDBアクセスを許可し、残りはロックが解放されるまで待つ。
def get_popular_content(content_id: int):
cached = redis.get(f"content:{content_id}")
if cached:
return json.loads(cached)
# 分散ロックを取得（他のリクエストはここで待機）
lock_key = f"lock:content:{content_id}"
acquired = redis.set(lock_key, "1", nx=True, ex=10) # NX=Only if Not exists
if acquired:
try:
content = db.get_content(content_id)
redis.setex(f"content:{content_id}", 3600, json.dumps(content))
return content
finally:
redis.delete(lock_key)
else:
# ロック取得できなかった → 少し待ってリトライ
time.sleep(0.1)
return get_popular_content(content_id) # 再帰的にリトライ対策2：Probabilistic Early Expiration（確率的早期失効）
TTL が切れる「少し前」から、確率的にキャッシュを再生成し始める。急なキャッシュ切れを防ぐ。
import math
import time
def get_with_pee(key: str, ttl: int, fetch_fn, beta: float = 1.0):
"""
PEE (Probabilistic Early Expiration)
残り時間が短くなるほど、再取得する確率が高くなる
"""
data_bytes = redis.get(key)
if data_bytes:
data = json.loads(data_bytes)
remaining = redis.ttl(key)
# delta：前回の取得にかかった時間（より長い処理ほど早めに再生成）
delta = data.get("_fetch_time", 0.1)
# 確率的に早期再生成するかどうか判定
should_refresh = (-delta * beta * math.log(random.random())) >= remaining
if not should_refresh:
return data["value"]
# 再生成
start = time.time()
value = fetch_fn()
fetch_time = time.time() - start
payload = json.dumps({"value": value, "_fetch_time": fetch_time})
redis.setex(key, ttl, payload)
return value対策3：背景再生成（Stale-While-Revalidate）
HTTP キャッシュ制御ヘッダー stale-while-revalidate と同じ発想をアプリ層で実装する。
def get_with_background_refresh(key: str):
cached = redis.get(f"data:{key}")
if cached:
data = json.loads(cached)
remaining_ttl = redis.ttl(f"data:{key}")
# TTL が 20% 以下になったらバックグラウンドで更新
if remaining_ttl < data.get("original_ttl", 3600) * 0.2:
executor.submit(refresh_cache, key) # 非同期
return data["value"] # 古いデータを即座に返す
# キャッシュなし → 同期的に取得
return sync_fetch_and_cache(key)Redis Cluster：分散ハッシュスロット
Redis を複数ノードにスケールアウトする場合、Redis Cluster を使う。
Redis Cluster は16384 個のハッシュスロットを複数ノードで分担する。
ノード1：スロット 0 〜 5460
ノード2：スロット 5461 〜 10922
ノード3：スロット 10923 〜 16383キーのルーティング：
def get_slot(key: str) -> int:
# { } で囲まれた部分だけをハッシュ（ハッシュタグ）
# 例: "user:{123}:profile" → "123" だけをハッシュ
match = re.search(r'\{(.+?)\}', key)
hash_key = match.group(1) if match else key
return crc16(hash_key) % 16384ハッシュタグは同一ユーザーの複数キーを同じスロット（同じノード）に配置するための仕組みだ。
# ハッシュタグなし → 異なるノードに分散
redis.set("user:123:profile", ...) # スロット 8976 → ノード2
redis.set("user:123:settings", ...) # スロット 3421 → ノード1
# MULTI/EXEC（トランザクション）が使えない！
# ハッシュタグあり → 同じノードに配置
redis.set("user:{123}:profile", ...) # ハッシュキー "123" → 同じスロット
redis.set("user:{123}:settings", ...) # ハッシュキー "123" → 同じスロット
# MULTI/EXEC が使える ✅まとめ
| 課題 | 解決策 | トレードオフ |
|---|---|---|
| 読み込み速度 | Cache-Aside | 初回ミス・弱い整合性 |
| 書き込みの一貫性 | Write-Through | 書き込みレイテンシ増 |
| 書き込みスループット | Write-Back | データロスリスク |
| メモリ効率 | LRU / LFU（用途次第） | アクセスパターン依存 |
| Thundering Herd | 分散ロック / PEE / 背景更新 | 複雑さとのトレードオフ |
| 水平スケール | Redis Cluster（16384スロット） | クロスノードトランザクション不可 |
キャッシュは「銀の弾丸」ではない。整合性要件・障害耐性・書き込みパターンを整理してから戦略を選ぶことが重要だ。
次章では、Kafka がどうやって「絶対に落とさない」メッセージキューを実現しているかを見ていく。