ch10-gaming-leaderboard

Chapter 10: Design a Real-time Gaming Leaderboard

volume2 leaderboard redis sorted-set real-time

Status: 🟩 Interview ready
Difficulty: Medium-Hard
Time to complete: 45 min read + practice

---

Overview

A gaming leaderboard tracks player scores and shows real-time rankings — who is at the top, and where you stand among all players. Examples: Clash of Clans, Fortnite, Candy Crush, any competitive online game.

Why this matters:

• Excellent Redis Sorted Set teaching problem (appears at many mid-size/large tech companies)
• Teaches real-time data structures, trade-offs between SQL and Redis, sharding strategies
• Practical and concrete — easy to discuss clearly in an interview

Problem Statement

Design a real-time gaming leaderboard that:

• Tracks player scores for a game (or multiple games)
• Shows the top-N players globally (default: top 10)
• Shows an individual player’s rank in real-time
• Updates scores as players earn points during gameplay
• Supports historical leaderboards (e.g., weekly, monthly)

---

Step 1: Requirements & Scope (5 min)

Functional Requirements

Clarifying questions:

• One global leaderboard or per-game? → Per game (each game has its own)
• How many players? → 5 million DAU
• Top how many players shown? → Top 10 (but system should support top-N)
• Can we show user’s own rank? → Yes, show their rank even if not in top 10
• How fresh does the ranking need to be? → Near real-time (within seconds)
• Historical data? → Yes, weekly and monthly leaderboards
• Score update volume? → 50 million score updates per day

Scope:

• Update a player’s score
• Get top-10 players with scores
• Get a specific player’s rank and score
• Per-game leaderboards
• Historical (weekly/monthly) leaderboards

Non-Functional Requirements

• Low latency reads: < 100ms for top-10 query and rank lookup
• High write throughput: 50M updates/day ≈ ~580 updates/sec average, ~2,500 peak
• Scalability: 5M DAU, growing
• Availability: 99.99% (leaderboard is customer-facing, but not life-critical)
• Consistency: Near real-time (eventual is acceptable, within a few seconds)
• Durability: Score data must survive restarts

---

Step 2: High-Level Design (10 min)

Two Core Operations

Operation 1: Score update

Client (game event: player earned 100 points)
  │
  ▼
API Server
  │
  ▼
Score Update Service
  │
  ├──▶ Leaderboard Store (update ranking)
  └──▶ Score DB (persist score history)

Operation 2: Leaderboard query

Client (show me the leaderboard)
  │
  ▼
API Server
  │
  ▼
Leaderboard Service
  │
  ▼
Leaderboard Store (Redis) → top-10 players + user's rank

High-Level Architecture

┌─────────────────────────────────────────────────────────────┐
│                        Game Server                          │
│  (Player scores point → generates score event)              │
└──────────────────────────┬──────────────────────────────────┘
                           │
                    ┌──────▼──────┐
                    │    Kafka    │  (decouple game server
                    │  (score     │   from score processing)
                    │   events)   │
                    └──────┬──────┘
                           │
              ┌────────────▼────────────┐
              │   Score Processor       │
              │   (Kafka consumer,      │
              │    validates events,    │
              │    deduplicates)        │
              └────┬─────────────┬──────┘
                   │             │
         ┌─────────▼──┐    ┌─────▼──────────┐
         │   Redis    │    │   MySQL /       │
         │  Sorted    │    │   PostgreSQL    │
         │    Set     │    │  (score history,│
         │ (rankings) │    │   persistence)  │
         └────────────┘    └────────────────┘
                   │
         ┌─────────▼──────────┐
         │  Leaderboard API   │
         │  (top-N, user rank)│
         └────────────────────┘
                   │
              ┌────▼────┐
              │ Clients │
              └─────────┘

API Design

Score operations:

POST /scores
Body: { "game_id": "chess", "player_id": "alice", "delta": 100 }
Response: { "player_id": "alice", "new_score": 1450, "rank": 7 }

Leaderboard queries:

GET /leaderboards/{game_id}/top?limit=10
Response: [
  { "rank": 1, "player_id": "bob",   "score": 9800 },
  { "rank": 2, "player_id": "carol", "score": 9700 },
  ...
]

GET /leaderboards/{game_id}/players/{player_id}/rank
Response: { "player_id": "alice", "rank": 42, "score": 1450 }

---

Step 3: Deep Dive (20 min)

Storage Option 1: Relational Database

Naive approach — store scores in MySQL:

CREATE TABLE player_scores (
    game_id    VARCHAR(50),
    player_id  VARCHAR(50),
    score      INT,
    updated_at TIMESTAMP,
    PRIMARY KEY (game_id, player_id)
);
 
-- Top-10 query:
SELECT player_id, score
FROM player_scores
WHERE game_id = 'chess'
ORDER BY score DESC
LIMIT 10;
 
-- User rank query (SLOW! Full table scan):
SELECT COUNT(*) + 1 AS rank
FROM player_scores
WHERE game_id = 'chess'
  AND score > (SELECT score FROM player_scores
               WHERE game_id = 'chess' AND player_id = 'alice');

Problems:

• ORDER BY score DESC LIMIT 10 — requires full table scan or full index scan for millions of rows
• Rank query requires counting all players with higher scores — O(N)
• At 5M players per game, every rank lookup is expensive
• Adding an index on (game_id, score) helps but still O(log N) per update + O(log N + K) per range query — the DB overhead and lock contention don’t compare to Redis

When SQL is OK: Game has < 100K players, or leaderboard updates are infrequent (daily refresh).

Storage Option 2: Redis Sorted Set (Best Choice!)

Redis Sorted Set is purpose-built for this exact use case:

• Members (player IDs) each have a score (float)
• Members are kept sorted by score automatically
• O(log N) for insert/update
• O(log N + K) for top-K range query
• O(log N) for rank lookup

Redis Sorted Set commands:

# Add or update a player's score
ZADD leaderboard:chess 1450 "alice"
# → O(log N)

# Increment score (most common: player earns delta points)
ZINCRBY leaderboard:chess 100 "alice"
# → atomically adds 100 to alice's score, O(log N)

# Get top 10 players (highest scores first)
ZREVRANGE leaderboard:chess 0 9 WITHSCORES
# → returns [ ("bob", 9800), ("carol", 9700), ... ]
# → O(log N + K) where K=10

# Get alice's rank (0-indexed, highest score = rank 0)
ZREVRANK leaderboard:chess "alice"
# → returns 41  (rank 42 = 0-indexed 41)
# → O(log N)

# Get alice's score
ZSCORE leaderboard:chess "alice"
# → returns 1450
# → O(1)

# Get players ranked 10-19 (for pagination)
ZREVRANGE leaderboard:chess 10 19 WITHSCORES
# → O(log N + K)

# Get total number of players in leaderboard
ZCARD leaderboard:chess
# → O(1)

# Remove a player (account deletion)
ZREM leaderboard:chess "alice"
# → O(log N)

Time complexity summary:

Operation	Command	Complexity	Notes
Add/update score	ZADD	O(log N)	Insert + maintain sorted order
Increment score	ZINCRBY	O(log N)	Atomic increment + re-sort
Top-K query	ZREVRANGE	O(log N + K)	Very fast for small K
User rank	ZREVRANK	O(log N)	No counting loop!
User score	ZSCORE	O(1)	Direct hash lookup
Player count	ZCARD	O(1)	Metadata

Why Redis Sorted Set beats SQL:

Aspect	SQL (ORDER BY)	Redis Sorted Set
Top-10 query	O(N log N) or full index scan	O(log N + 10)
Rank lookup	O(N) count query	O(log N)
Score update	O(log N) update + reindex	O(log N) ZINCRBY
Write throughput	Moderate (lock contention)	Very high (in-memory)
Data structure	B-tree index	Skip list (sorted by design)

Key Design: One Sorted Set Per Game

Key naming convention:
  leaderboard:{game_id}             → global leaderboard for a game
  leaderboard:{game_id}:weekly:{week}  → weekly leaderboard (e.g., week 202415)
  leaderboard:{game_id}:monthly:{month} → monthly (e.g., 2024-04)

Examples:
  leaderboard:chess                → global chess leaderboard
  leaderboard:chess:weekly:202415  → chess week 15 of 2024
  leaderboard:chess:monthly:202404 → chess April 2024

Persistence: Protecting Redis Data

Redis is in-memory, so we need persistence strategies:

Option 1: Redis AOF (Append-Only File)

Every write command is appended to a log file on disk.
On restart, Redis replays the log to rebuild state.
Pro: Near-zero data loss (configurable fsync: every second or every write)
Con: AOF file grows large over time (periodic rewrite/compaction needed)
Use: Production — set appendfsync everysec for 1-second max data loss

Option 2: Redis RDB (Snapshot)

Redis forks and saves a point-in-time snapshot of all data to disk.
Configurable: every N seconds if M keys changed.
Pro: Fast restarts (load snapshot), compact storage
Con: Data loss between snapshots (e.g., lose 5 min if snapshot every 5 min)
Use: Secondary backup, or when small data loss is acceptable

Option 3: Redis + MySQL dual write

Score Processor writes to both Redis AND MySQL atomically (or near-atomically).
  → MySQL = source of truth (full history, durable)
  → Redis = cache layer (fast reads, ranking)

On Redis failure:
  → Rebuild sorted set by reading scores from MySQL
  → SELECT player_id, score FROM player_scores WHERE game_id = 'chess'
  → ZADD in bulk to recreate leaderboard

Best for production: Use Redis AOF for immediate durability +
MySQL as source of truth for full history and rebuilds.

Sharding for Large-Scale Games

Problem: One Redis sorted set per game can become a bottleneck for huge games (100M+ players).

Strategy 1: Shard by score range

Shard 1 (Redis instance A): players with score 0–9,999
Shard 2 (Redis instance B): players with score 10,000–19,999
Shard 3 (Redis instance C): players with score 20,000+

Top-10 query:
  → Query Shard 3 (highest scores) → get top-10 from that shard
  → If Shard 3 has fewer than 10 players, query Shard 2, merge results

Rank query for Alice (score 1450):
  → She is in Shard 1
  → Rank = (all players in Shard 3) + (all players in Shard 2) + (ZREVRANK in Shard 1)

Strategy 2: Shard by player_id hash (for write distribution)

Shard = hash(player_id) % N

Each shard stores a subset of players (by ID, not by score).
All shards together form the global leaderboard.

Top-10 global: Query all N shards, get top-10 from each, merge and sort.
→ Merge cost: O(N × 10) — acceptable when N is small (e.g., 10 shards)

User rank for Alice:
→ Find Alice's score on her shard (O(log N))
→ Count players with higher score on EACH other shard (range query)
→ Sum up = global rank
→ More expensive but doable

Recommendation:

• 5M DAU per game → single Redis sorted set easily handles this (millions of members per sorted set is fine)
• Shard by player_id hash if > 100M players in a single game leaderboard
• Score-range sharding is simpler for top-N queries but complicates rank lookup

Merging Shard Results

When top-10 requires merging multiple shards:

Shard A top-3: [(carol, 9700), (dave, 9600), (eve, 9500)]
Shard B top-3: [(bob, 9800), (frank, 9400), (grace, 9300)]
Shard C top-3: [(henry, 9100), (ivan, 9000), (judy, 8900)]

Merge (sorted merge of K sorted lists):
  bob:9800, carol:9700, dave:9600, eve:9500, frank:9400, grace:9300,
  henry:9100, ivan:9000, judy:8900, ...

Global top-3: [(bob, 9800), (carol, 9700), (dave, 9600)]

Algorithm: K-way merge (min-heap) — O(K log K) where K = number of shards × top-N per shard.

Score Tie-Breaking

Two players with the same score — who ranks higher?

Option 1: Earlier score wins (most common in gaming)

Encode score as composite float:
  encoded_score = (score × 10^13) - timestamp_ms

Alice: score=1450 at t=1000 → 14500000000000 - 1000 = 14499999999000
Bob:   score=1450 at t=2000 → 14500000000000 - 2000 = 14499999998000

ZADD leaderboard:chess 14499999999000 "alice"  ← higher score → better rank
ZADD leaderboard:chess 14499999998000 "bob"    ← same point score, later time → lower rank

Result: Alice ranks above Bob (she got there first)

Option 2: Alphabetical tiebreak (simpler but less fair)

Redis sorted sets use lexicographical order as a tiebreaker
for members with equal scores.
"alice" < "bob" alphabetically → alice ranks higher at same score.

Option 3: No tiebreak (allow shared ranks)

Both players at rank N — display "T-42" (tied 42nd).
Simple but requires extra logic to number the display.

Recommendation: Composite score encoding (Option 1) gives deterministic, fair ranking with no extra storage.

Historical Leaderboards

Weekly leaderboards:

Strategy:
  - Separate sorted set per week: leaderboard:chess:weekly:{year_week}
  - Score update goes to BOTH global AND current week's sorted set
  - At end of week: archive top-N to MySQL, set Redis key expiry

ZADD leaderboard:chess          100  "alice"  ← global
ZADD leaderboard:chess:weekly:202415 100 "alice"  ← week 15, 2024

At start of new week (Sunday midnight):
  1. Read top-1000 from leaderboard:chess:weekly:202415
  2. INSERT INTO weekly_archive (game_id, week, rank, player_id, score)
  3. SET EXPIRE leaderboard:chess:weekly:202415 604800 (keep 7 more days for queries)
  4. New key leaderboard:chess:weekly:202416 starts fresh at zero

Monthly leaderboards:

Same pattern: leaderboard:chess:monthly:2024-04
Archive at month end, expire Redis key after a grace period.

Score reset:

Option A: Use separate keys per period (above) — no reset needed
Option B: Single key, reset at period boundary
  → RENAME leaderboard:chess:weekly to leaderboard:chess:weekly:prev
  → DEL leaderboard:chess:weekly (start fresh)
  → Option B loses granularity; Option A is preferred

Score Update Pipeline

For high-throughput score updates, use a message queue:

Game Server
  │ Produces: { game_id, player_id, delta, event_id, timestamp }
  ▼
Kafka Topic: "score-events"
  │ (partitioned by game_id for ordering within a game)
  ▼
Score Processor (Kafka Consumer Group)
  │ 1. Deduplication: check event_id (idempotency key) in Redis/DB
  │ 2. Validate: delta is positive, player exists, game exists
  │ 3. ZINCRBY leaderboard:{game_id} {delta} {player_id}
  │ 4. UPDATE player_scores SET score = score + delta WHERE ...
  ▼
Redis Sorted Set + MySQL

Why Kafka:

• Buffer bursts (game events spike during tournaments)
• Decouple game server from score processing
• Replay events on processor failure
• Multiple consumers (leaderboard + analytics + notifications)

Idempotency: Each score event has a unique event_id. Score Processor checks if event_id already processed before applying. Prevents double-counting if event replays.

Leaderboard for Friends / Regional

Friends leaderboard:

At query time:
  1. Fetch user's friend list (from social graph service)
  2. ZSCORE leaderboard:{game_id} {friend_id} for each friend
  3. Build and sort in application layer

Or pre-compute:
  - Maintain per-user sorted set of friend scores (expensive at scale)
  - Preferred: query-time computation for small friend lists (< 500 friends)

Regional leaderboard:

Separate sorted set per region:
  leaderboard:{game_id}:region:us-east
  leaderboard:{game_id}:region:eu-west

Score updates fan out to global + regional sorted set.
Same Redis Sorted Set commands — just different key.

---

Design Summary

Concern	Choice	Reasoning
Core data structure	Redis Sorted Set	O(log N) insert + rank, O(1) score lookup
Score updates	ZINCRBY	Atomic increment, no read-modify-write race
Top-N query	ZREVRANGE	O(log N + K), purpose-built
Rank lookup	ZREVRANK	O(log N), no COUNT query needed
Persistence	Redis AOF + MySQL dual write	Durability + rebuild capability
Score pipeline	Kafka + Score Processor	Decouple, buffer bursts, idempotency
Historical	Separate sorted set per period, archive to MySQL	No global reset risk, full history
Tie-breaking	Composite score (score × M - timestamp)	Fair FIFO tiebreak
Sharding	By player_id hash if > 100M players	Write distribution + K-way merge for top-N
Friends leaderboard	Query-time ZSCORE per friend	Simple, no pre-computation for small lists

Final Architecture

┌────────────────────────────────────────────────────────────────┐
│                     API Gateway                                │
└──────────────────────────┬─────────────────────────────────────┘
                           │
           ┌───────────────┼───────────────┐
           │                               │
  ┌────────▼────────┐             ┌────────▼────────┐
  │  Leaderboard    │             │  Score Update   │
  │  Service        │             │  Service        │
  │  (Read path)    │             │  (Write path)   │
  └────────┬────────┘             └────────┬────────┘
           │                               │
           │                        ┌──────▼──────┐
           │                        │    Kafka    │
           │                        └──────┬──────┘
           │                               │
           │                      ┌────────▼────────┐
           │                      │ Score Processor  │
           │                      │ (dedup, validate)│
           │                      └────────┬─────────┘
           │                               │
           └────────────┐  ┌───────────────┘
                        │  │
               ┌────────▼──▼────────┐
               │   Redis Cluster    │
               │                   │
               │  leaderboard:chess │
               │  leaderboard:chess │
               │  :weekly:202415    │
               │  ...               │
               └────────┬───────────┘
                        │ AOF + snapshots
               ┌────────▼───────────┐
               │     MySQL          │
               │  (player_scores,   │
               │   weekly_archive)  │
               └────────────────────┘

---

Interview Questions & Answers

Q: Why is Redis Sorted Set better than SQL ORDER BY for a leaderboard?
A: SQL ORDER BY requires a full index scan on (game_id, score) for top-N queries — O(N) to scan and sort, and counting rows for rank lookup is O(N). Redis Sorted Set maintains elements in sorted order at all times using a skip list. ZREVRANGE (top-K) is O(log N + K) and ZREVRANK is O(log N). At 5M players, O(log 5M) ≈ 23 operations vs O(5M) for a count. Redis also has much higher write throughput (in-memory, no lock contention).

Q: How do you handle tie-breaking when two players have the same score?
A: Encode a composite score into the Redis sorted set value: composite = score × 10^13 - timestamp_ms. Players who reached the same score earlier get a higher composite value, so they rank above later players with the same score. This is purely numeric and fits in a 64-bit float. The tiebreak is deterministic and fair (first to reach the score wins) with no extra storage.

Q: How would you shard the leaderboard for a game with 100M+ players?
A: Shard by hash(player_id) % N across N Redis instances. Each shard holds a sorted set for a subset of players. For top-10 global: query all N shards for their top-10, then K-way merge (min-heap) the results — O(N × log(N×10)) computation on the application layer. For user rank: get user’s score from their shard, then count players with higher scores on each other shard using ZCOUNT, sum them up. This scales writes linearly but merging adds latency — profile N to keep merge latency under budget.

Q: How do you implement historical (weekly/monthly) leaderboards?
A: Use a separate Redis sorted set per time period (e.g., leaderboard:chess:weekly:202415). Score updates write to both the global sorted set and the current period’s sorted set. At the period boundary: read the top players, archive to MySQL, and set an expiry on the Redis key. Start a fresh key for the new period. This avoids risky in-place resets and keeps history accessible for a grace period via the expiring Redis key, with permanent storage in MySQL.

Q: What happens if Redis goes down?
A: With AOF enabled (appendfsync everysec), at most 1 second of score updates is lost on restart. Redis replays the AOF log to reconstruct state. If the loss is unacceptable, also write scores to MySQL (dual write). On Redis restart or complete failure, rebuild the sorted set from MySQL: SELECT player_id, score FROM player_scores WHERE game_id = X, then ZADD in bulk. Piplined ZADD can load millions of records in seconds.

---

Key Takeaways

1. Redis Sorted Set is the definitive data structure for leaderboards: O(log N) insert + rank, O(log N + K) top-K — purpose-built for this.
2. ZINCRBY enables atomic score increments: No read-modify-write, no race conditions.
3. SQL ORDER BY doesn’t scale: O(N) rank lookup via COUNT becomes unacceptable at millions of players.
4. Persist with AOF + MySQL dual write: Redis AOF for fast recovery; MySQL as source of truth for rebuilds and history.
5. Kafka decouples score events from processing: Buffers traffic spikes, enables deduplication, replays on failure.
6. Tie-breaking via composite score encoding: Encode score × scale factor - timestamp into Redis float — no extra fields.
7. Historical leaderboards use separate keys per period: Archive to MySQL at period end; never reset in-place.

---

Related Resources

• ch05-consistent-hashing - Consistent hashing for distributed Redis shards
• ch09-s3-object-storage - Contrasting storage design (metadata vs data planes)
• distributed-system-components - Redis data structures and use cases
• key-patterns - Real-time data patterns, message queues

---

Practice this design! Great interview question with clear right answers. Be ready to:

1. Immediately say Redis Sorted Set and explain the commands (ZADD, ZREVRANGE, ZREVRANK, ZINCRBY)
2. Compare time complexity vs SQL ORDER BY
3. Discuss persistence (AOF vs MySQL dual write)
4. Explain Kafka pipeline for score updates
5. Handle historical leaderboards and tie-breaking

---

Last Updated: 2026-04-13
Status: Medium-Hard — Clear winner (Redis Sorted Set) — Nail the commands and complexity!