第2章 — エビクション: 何を捨てるか
キャッシュは有限
「キャッシュのメモリは無限じゃない。満杯になったら、何かを捨てて新しいデータを入れる必要がある。この『何を捨てるか』を決めるのがエビクションアルゴリズムだ」
ケンジはそう切り出した。
主要なエビクションアルゴリズム
LRU（Least Recently Used）
最も長い間使われていないデータを捨てる。最も広く使われるアルゴリズム。
Loading diagram...
| メリット | デメリット |
|---|---|
| 実装がシンプル（連結リスト+ハッシュマップ） | スキャン耐性がない |
| 多くのワークロードで良好 | 頻度を考慮しない |
| O(1) の読み書き | 一度だけ大量アクセスされたデータに弱い |
LFU（Least Frequently Used）
最もアクセス回数が少ないデータを捨てる。
| メリット | デメリット |
|---|---|
| 人気データを長く保持 | 過去の人気が永続する（キャッシュ汚染） |
| スキャン耐性がある | 実装が複雑（ヒープが必要） |
| 安定したヒット率 | 新しいデータが定着しにくい |
FIFO（First In, First Out）
最も古く追加されたデータを捨てる。単純なキュー。
TTL（Time To Live）
一定時間経過後に自動で期限切れにする。他のアルゴリズムと組み合わせて使う。
# Redis での TTL 設定
Rails.cache.write("product:123", product, expires_in: 1.hour)ARC（Adaptive Replacement Cache）
LRU と LFU を動的に組み合わせる先進的アルゴリズム。ワークロードの変化に自動適応する。
Loading diagram...
INFO
ARC は IBM が開発し、ZFS ファイルシステムで有名。退去されたデータの「ゴースト履歴」を追跡し、LRU と LFU のバランスを動的に調整する。
アルゴリズム比較
Loading chart...
Redis のエビクションポリシー
Redis は8種類のエビクションポリシーを提供する。
| ポリシー | 対象 | 動作 |
|---|---|---|
noeviction | — | メモリ上限でエラー |
allkeys-lru | 全キー | LRU で退去 |
volatile-lru | TTL 付きキー | LRU で退去 |
allkeys-lfu | 全キー | LFU で退去 |
volatile-lfu | TTL 付きキー | LFU で退去 |
allkeys-random | 全キー | ランダム退去 |
volatile-random | TTL 付きキー | ランダム退去 |
volatile-ttl | TTL 付きキー | TTL が短い順 |
# redis.conf
maxmemory 256mb
maxmemory-policy allkeys-lru
WARNING
Redis の LRU は厳密な LRU ではなく「近似 LRU」。サンプリングベースで、maxmemory-samples パラメータでサンプル数を調整できる（デフォルト5、増やすと精度向上・CPU増加）。
選び方ガイド
Loading diagram...
マナミの選択
FreshMarket では人気商品が固定的で、セール時に一時的なアクセス急増がある。
マナミは Redis の allkeys-lfu を選んだ。人気商品を長く保持しつつ、セール終了後の一時的データは自然に退去される。さらに TTL を1時間に設定し、データの鮮度も保証した。
次の章では、Web キャッシュの根幹——HTTP キャッシュ——を深掘りする。