数百万プレイヤー向けのリアルタイムリーダーボードを設計してください

Question

IT Interview Practice · Accepted Answer

**スコアをキーとするRedisのsorted set（ZSET）を使います：ランクとtop-NがビルトインのO(log N)操作になるので、リクエストごとに数百万行をソートすることは決してありません。** ZSETはメンバーをスコア順に自動的に保ちます。それがまさにリーダーボードです。

## アーキテクチャ

```text
Game svc ──ZADD score──▶ Redis ZSET (sorted by score) ──ZREVRANGE 0 99──▶ Top-100 API
                              │
                              ├─ ZREVRANK user ─▶ "your rank" (around-me: rank±5)
                              └─ AOF/RDB + async ─▶ Postgres (durable source of truth)
```

## 仕組み

- **ZADD** はプレイヤーのスコアをO(log N)でupsertします。Redisは**スキップリスト**で順序を維持するので、再ソートは不要です。
- **Top-N**：`ZREVRANGE board 0 99 WITHSCORES` がO(log N + 100)でトップ100を返します。
- **自分のランク**：`ZREVRANK board user` が0始まりの順位を返します。**around-me** は `ZREVRANGE rank-5 rank+5` — 自分の近くのプレイヤーのスライスです。
- **耐久性**：Redisはインメモリです。リプレイのために**AOF**（append-only file）を有効にし、真のシステムオブレコードとして**Postgres**にスコアを非同期ミラーリングし、Redisの喪失を復旧可能にします。

## 数百万ユーザーのためのシャーディング

1つのZSETは数千万メンバーを問題なく保持します（メモリ律速、100万エントリで約100MB）。それを超える場合やグローバル規模では、**スコアレンジでシャーディング**（0–1k、1k–10k…）し、各シャードを連続した帯にします。グローバルtop-Nはトップシャードのみを読みます。ユーザーハッシュでのシャーディングは避けます。ランダムなシャードにまたがるランクの再結合は高コストです。

## 面接での観点

面接官は、あなたがSQLの `ORDER BY score LIMIT 100`（ヒットごとに再ソートし、書き込み負荷で死ぬ）ではなく、**適切なデータ構造に手を伸ばす**のを見たいのです。良い回答はZSETを挙げます。優れた回答は**around-meクエリ、同点、永続化、シャード戦略**をカバーします。典型的な罠：Redisが揮発性だと忘れ、それを真実の源として扱うこと。AOF/RDBまたはDBミラーがなければ、再起動でボードが消えます。

## トレードオフと障害

- **同点。** 同スコアはメンバーの辞書順で並び、ランダムに見えます。タイブレーカーをスコアにエンコード（例：`score * 1e13 - timestamp`）し、先に達成した者が上位になるようにします。
- **ホットキー。** 単一のグローバルZSETは1シャード上の1キーで、書き込みホットスポットです。`ZADD` をバッファ/バッチ化するか、時間バケット化されたボード（日次/週次）で負荷を分散します。
- **一貫性。** 読み取りは非同期DBミラーより数秒遅れることがあります。リーダーボードには問題ないが賞金には不可です。賞を授与する前にPostgresから照合します。
- **メモリコスト。** 数百万メンバーは実際のRAMを消費します。シーズンボードはTTLで失効させます。
- **不要な場合：** 毎分更新される数千人のリーダーボードは、キャッシュされたSQLクエリで十分です。Redis ZSETは書き込みが絶え間なくランクが即時である必要があるときに輝きます。

アーキテクチャ

仕組み

数百万ユーザーのためのシャーディング

面接での観点

トレードオフと障害

関連する質問