中
検索エンジン用のクエリキャッシュ(LRU)を設計せよ
課題
検索エンジンの前段に置く、直近のクエリ結果を保存するキャッシュを設計する。検索リクエストが来たら、同じクエリの結果がキャッシュにあれば(cache hit)即返し、無ければ(cache miss)裏のサービスから取得してキャッシュに保存する。メモリは有限なので、古いエントリを賢く捨てる必要がある。高可用が必須。『LRU(最近最も使われていないものから捨てる)をどんなデータ構造で実装するか』が核心です。
制約・前提
- 人気クエリはほぼ常にキャッシュに乗っている状態にしたい
- expire/refresh(いつ捨てる・更新するか)の方式を決める必要がある
- 高速lookup・低いマシン間レイテンシ・限られたメモリ
- ユーザーは10M(1000万)人
- クエリは10B(100億)/月
- 1検索あたり270 bytes、全部ユニークなら2.7 TB/月
- 平均4,000 req/s、高可用が必須
主要数値
概算（back-of-the-envelope）の出発点。
| 平均req/s | 4,000 req/s |
|---|---|
| クエリ数 | 10B (100億)/月 |
| 1検索のサイズ | 270 bytes |
| 全ユニーク時の月間データ量 | 2.7 TB/月 |
| LRUの計算量 | lookup/更新/削除すべて O(1) |
| LRUの実装 | doubly-linked list + hash table |
主要数値の可視化
リクエスト量と月間データ量
read
全ユニーク時の月間データ量
read-heavy (4,000 req/s) LRU(doubly-linked list + hash table)でlookup/更新/削除すべてO(1)。ホットなクエリをメモリに保持。
まず自分で設計を考えてから、1ステップずつ答え合わせをしましょう。
Step 1: 要件・ユースケース（まだ伏せられています）
考えてみよう（面接官の追加質問）
- LRUの代わりにLFU(Least Frequently Used)を使うとどう変わる? どんなアクセスパターンでLFUが有利か?
- 『1回だけ大量に来るが二度と来ないクエリ』がLRUを汚す問題(cache pollution)をどう防ぐ?
- 分散キャッシュであるノードが落ちたら、そのノードが持っていたエントリはどうなる? 影響を最小化するには?
- 検索結果の元データが更新されたとき、該当キャッシュをどうやって無効化(invalidate)する?
- TTLとLRUを併用する場合、それぞれが何の問題(古さ vs 容量)を解決しているか説明できるか?