Design a Real-Time Leaderboard
TL;DR
A real-time leaderboard ranks players by score and returns any player's rank instantly. Redis sorted sets (ZADD/ZRANK at O(log N)) handle this for up to 100 million players on a single instance. The hard parts are friend-scoped leaderboards (show me where I rank among my friends, not globally), tie-breaking (two players with score 1,000 -- who is higher?), approximate ranking at billion scale (when O(log N) per query is too slow for 1 million queries/sec), and anti-cheat (a score submitted from the client can be spoofed). Most candidates know about sorted sets. The interview differentiator is knowing what to do when sorted sets are not enough.
The System
A leaderboard shows ranked players -- who is #1, where do I rank, what are the top 100, and who is near me on the board. It updates in real-time: when a player completes a level or earns points, their position changes immediately and every affected player's rank shifts.
Clash Royale has 100+ million players and maintains real-time leaderboards per season. Fortnite Battle Royale needs leaderboards for 350+ million registered accounts. Strava's segment leaderboards rank millions of athletes on every road segment worldwide. Duolingo maintains leaderboards across language learning leagues. Mobile games with gacha mechanics (Genshin Impact, Honkai Star Rail) use leaderboards for competitive events. Even non-gaming applications use leaderboards: sales team performance dashboards, LeetCode contest rankings, and fantasy sports. The common thread: reads are much more frequent than writes (players check the leaderboard far more often than they update scores), but writes must instantly update rankings.
Requirements
Functional
- Update score: When a player earns points, update their total score and recompute their rank
- Get top K: Return the top K players globally (leaderboard page 1, 2, ...)
- Get rank: Given a player, return their exact rank (e.g., "You are #47,832 out of 10M players")
- Get neighbors: Return the K players immediately above and below a given player ("You are #47,832 -- here are #47,830 through #47,834")
- Friend leaderboard: Show the player's rank among their friends only
- Time-scoped: Support daily, weekly, monthly, and all-time leaderboards
- Tie-breaking: When two players have the same score, rank the one who achieved it first higher
Non-Functional
- Write latency: Score update reflected in the leaderboard within 100ms
- Read latency: Top-K and rank queries complete in under 10ms at p99
- Write throughput: 50,000 score updates/sec (peak during competitive events)
- Read throughput: 500,000 rank queries/sec (10:1 read-write ratio)
- Scale: Up to 100 million players on a single leaderboard
- Accuracy: Exact rankings (not approximate) for the top 10,000. Approximate (within 0.1%) acceptable for lower-ranked players
Back-of-Envelope Math
Players: 100M
Score updates: 50K/sec peak
Redis sorted set operations:
ZADD (update score): O(log N) = O(log 100M) = ~27 operations in skip list
ZRANK (get rank): O(log N) = ~27 operations
ZRANGE (top K): O(log N + K) = ~27 + K operations
At 50K ZADD/sec: 50K * 27 = 1.35M internal operations/sec
At 500K ZRANK/sec: 500K * 27 = 13.5M internal operations/sec
Total: ~15M internal operations/sec
Redis handles 50M+ internal operations/sec on modern hardware. Fine.
Memory:
Each sorted set member: key (user_id, 8 bytes) + score (8 bytes) +
skip list overhead (~40 bytes per entry)
100M entries * 56 bytes = 5.6 GB
Fits in a single Redis instance with room to spare.
Friend leaderboard:
Average friends per player: 50
Player queries friend leaderboard: fetch 50 friends' scores, sort
Option 1: 50 ZSCORE calls = 50 * O(1) = 50 operations
Option 2: Maintain per-user sorted sets (memory: 100M users * 50 friends * 56B = 280 GB -- too much)
The Naive Design
┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ Game │────>│ API Server │────>│ MySQL │
│ Server │<────│ │<────│ │
└──────────┘ └──────────────┘ └──────────────┘
-- Update score:
UPDATE players SET score = score + 100 WHERE id = 'player_123';
-- Get rank:
SELECT COUNT(*) + 1 as rank FROM players WHERE score >
(SELECT score FROM players WHERE id = 'player_123');
-- Get top K:
SELECT * FROM players ORDER BY score DESC LIMIT 100;
Works for 10,000 players. The rank query is O(N) -- it counts how many players have a higher score. At 100M players, this query scans 100M rows per request.
Where Does This Break First?
The rank query. COUNT(*) WHERE score > X is a full table scan filtered by an index on score. At 100M rows, even with a B-tree index, each rank query reads thousands of index pages. At 500K queries/sec, the database melts.
Where It Breaks
Problem 1: Rank queries are O(N). SQL databases do not natively support "what is the ordinal position of row X in a sorted set?" The query COUNT(*) WHERE score > X is the best SQL can do, and it is a range scan across the index. At 100M rows, this takes 50-100ms. At 500K queries/sec, you need the query to take under 2 microseconds. SQL is 25,000x too slow.
Problem 2: Write-read contention. At 50K writes/sec (score updates), the B-tree index on score is constantly being modified. Read queries on the same index compete for the same pages. Row-level locking helps but does not eliminate contention at this write rate.
Problem 3: Friend leaderboard is a JOIN. "Rank me among my friends" requires fetching my friends' scores, sorting them, and finding my position. In SQL: SELECT * FROM players WHERE id IN (friend_ids) ORDER BY score DESC. For 50 friends, this is fast. But if 10M players query their friend leaderboard at 100K queries/sec, each querying 50 friends, you are doing 5M ZSCORE-equivalent lookups per second. The database cannot handle this.
Problem 4: Tie-breaking. Two players with score 1,000 need a deterministic ordering. SQL ORDER BY score DESC, achieved_at ASC works but adds complexity to the index and every query.
The Real Design
┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ Game │────>│ Leaderboard │────>│ Redis │
│ Server │<────│ Service │<────│ (sorted set)│
└──────────┘ └──────────────┘ └──────┬───────┘
│
┌────────v───────┐
│ PostgreSQL │
│ (persistence, │
│ history) │
└────────────────┘
Redis Sorted Sets (The Core)
Redis sorted sets are the purpose-built data structure for leaderboards. Each member has a score, and the set is maintained in sorted order using a skip list + hash map.
ZADD leaderboard 1500 "player_123" # Set player_123's score to 1500
ZADD leaderboard 1700 "player_456" # Set player_456's score to 1700
ZREVRANK leaderboard "player_123" # Returns 1 (0-indexed, rank #2)
ZREVRANGE leaderboard 0 9 # Top 10 players
ZREVRANGEBYSCORE leaderboard +inf -inf LIMIT 0 100 # Top 100 by score
ZCOUNT leaderboard 1000 2000 # How many players have score 1000-2000
Complexity:
| Operation | Command | Complexity | At 100M entries |
|---|---|---|---|
| Update score | ZADD | O(log N) | ~27 comparisons |
| Get rank | ZREVRANK | O(log N) | ~27 comparisons |
| Get top K | ZREVRANGE 0 K-1 | O(log N + K) | ~27 + K |
| Get neighbors | ZREVRANGE rank-5 rank+5 | O(log N + K) | ~27 + 11 |
| Get score | ZSCORE | O(1) | 1 lookup |
Why skip lists (Redis internals): Redis sorted sets use a skip list (not a balanced BST or B-tree). Skip lists have O(log N) insertion, deletion, and rank queries. The key advantage over balanced trees: skip lists support O(log N) rank operations natively (count the number of nodes skipped at each level). Balanced BSTs require augmented data (subtree sizes) for rank queries, which is more complex to maintain.
Memory at 100M entries: Each skip list node has ~40 bytes of overhead (pointers, level). With 8-byte member (user_id) and 8-byte score: 56 bytes per entry. 100M * 56 bytes = 5.6 GB. A single 8 GB Redis instance handles this.
Tie-Breaking with Timestamp Encoded in Score
Two players with score 1,000 -- who ranks higher? Common tie-breaking rules: the one who achieved the score first, or the one who achieved it most recently.
Technique: encode timestamp in the score's decimal portion
Redis scores are IEEE 754 doubles (64-bit floating point). They have 52 bits of mantissa, giving 15-16 significant decimal digits of precision.
Score: 1000 points, achieved at Unix timestamp 1714000000
Encoded score = 1000 + (MAX_TIMESTAMP - 1714000000) / 10^10
= 1000 + (9999999999 - 1714000000) / 10^10
= 1000 + 8285999999 / 10^10
= 1000.8285999999
Player A: scored 1000 at T=1714000000 -> 1000.8286000000
Player B: scored 1000 at T=1714000100 -> 1000.8285999900
A > B, so A ranks higher (achieved score first).
The MAX_TIMESTAMP - actual_timestamp inversion ensures earlier timestamps produce higher encoded scores (since Redis sorts ascending by score, and we use ZREVRANGE for descending).
Precision limitation: With 15 significant digits, you can encode scores up to ~100,000 with nanosecond-precision timestamps. For most games (scores under 1M), this gives sub-second tie-breaking precision.
Alternative: concatenated score key
If scores are integers and precision is critical, use a string score format:
ZADD leaderboard 0 "player_123"
HSET player_scores "player_123" "000001000:1714000000"
# Sort by string comparison: score DESC, timestamp ASC
This gives exact tie-breaking but requires application-level sorting for range queries.
Friend-Scoped Leaderboard (3 Solutions)
"Show me my rank among my 50 friends" is harder than it looks. Redis sorted sets give you global rank, not per-group rank.
Solution 1: Query friends' scores and sort in-app
def get_friend_leaderboard(player_id):
friend_ids = get_friends(player_id) # 50 friends
# Pipeline: fetch all friends' scores in one round trip
pipe = redis.pipeline()
for fid in friend_ids:
pipe.zscore("leaderboard", fid)
scores = pipe.execute()
# Combine and sort
friend_scores = [(fid, score) for fid, score in zip(friend_ids, scores) if score]
friend_scores.sort(key=lambda x: x[1], reverse=True)
# Find player's position
player_score = redis.zscore("leaderboard", player_id)
rank = sum(1 for _, s in friend_scores if s > player_score) + 1
return friend_scores, rank
Pros: No extra storage. Works with any friend count. Cons: O(F) Redis calls per request (pipelined, so 1 round trip, but F ZSCORE commands). At 50 friends: 50 operations. At 500K requests/sec: 25M ZSCORE ops/sec. Redis handles this.
Solution 2: Per-user friend sorted set
Maintain a separate sorted set for each player's friend leaderboard:
When any player's score changes, update their entry in all friends' sorted sets.
Pros: Friend rank queries are O(log F), very fast. Cons: Write amplification. A score update for player X requires updating X's entry in all F friends' boards. At 50 friends: 50K writes/sec * 50 = 2.5M writes/sec. And memory: 100M users * 50 friends * 56 bytes = 280 GB. Both are problematic.
Solution 3: Hybrid -- precompute for active players only
Maintain friend leaderboard sorted sets only for players who have viewed their friend leaderboard in the last 24 hours. For the majority of players (who have not checked), compute on demand (Solution 1). For active leaderboard viewers (maybe 10% of players), precompute.
Active friend board viewers: 10M (10% of 100M)
Memory: 10M * 50 * 56 bytes = 28 GB. Manageable.
Write amplification: 50K * 50 * 0.1 = 250K writes/sec. Fine.
I would go with Solution 1 (on-demand computation) for most interviews. It is simple, has no write amplification, and 50 ZSCORE calls pipelined to Redis take under 1ms. Only mention Solution 3 if the interviewer pushes on read latency for friend leaderboards.
Deep Dives
Deep Dive 1: Approximate Ranking at Billion Scale
At 1 billion players, Redis sorted set memory is 56 GB. That fits in a large Redis instance. But ZRANK at O(log 1B) = ~30 comparisons, and at 500K queries/sec, you are doing 15M internal operations/sec. Redis can handle this, but what if you need 5M queries/sec?
Percentile bucket approximation:
Divide the score range into 10,000 buckets. Each bucket tracks the count of players in that score range.
Score range: 0 to 100,000
Bucket size: 10 points
Buckets: [0-9], [10-19], [20-29], ..., [99,990-99,999]
Bucket counts:
bucket[0-9]: 12,345 players
bucket[10-19]: 45,678 players
...
bucket[1000-1009]: 89,012 players
...
Player with score 1,005 is in bucket[1000-1009]
Approximate rank = sum(bucket counts for all buckets with higher scores)
+ (bucket[1000-1009].count / 2)
Implementation in Redis:
HINCRBY bucket_counts "100" 1 # increment bucket for score 1000-1009
HINCRBY bucket_counts "100" -1 # decrement when player's score changes
# Compute rank: sum all buckets above the player's bucket
# Pre-compute prefix sums every 5 seconds:
rank_of_player = prefix_sum[player_bucket_index + 1]
This gives approximate rank with O(1) read latency (just a prefix sum lookup) and O(1) write latency (increment one bucket counter). Accuracy: within one bucket width (10 points in this example). For a player ranked #47,832, the approximate rank might be #47,790 to #47,870. Acceptable for "You are in the top 0.05%."
When to use this: When you need exact rank for the top 10,000 (use Redis sorted set for top players) and approximate rank for everyone else (use bucket approximation). The top 10,000 is a sorted set of 10K entries (560 KB). The rest use bucket counters.
Deep Dive 2: Time-Scoped Leaderboards (Daily/Weekly/Monthly)
A weekly leaderboard resets every Monday. A monthly leaderboard resets on the 1st.
Approach: one sorted set per time scope
ZADD leaderboard:daily:2025-04-18 1500 "player_123"
ZADD leaderboard:weekly:2025-W16 1500 "player_123"
ZADD leaderboard:monthly:2025-04 1500 "player_123"
ZADD leaderboard:alltime 15000 "player_123"
When a player earns 100 points, update all 4 sorted sets:
def update_score(player_id, points):
today = date.today().isoformat()
week = date.today().strftime("%Y-W%V")
month = date.today().strftime("%Y-%m")
pipe = redis.pipeline()
pipe.zincrby(f"leaderboard:daily:{today}", points, player_id)
pipe.zincrby(f"leaderboard:weekly:{week}", points, player_id)
pipe.zincrby(f"leaderboard:monthly:{month}", points, player_id)
pipe.zincrby("leaderboard:alltime", points, player_id)
pipe.execute()
Memory: 4 sorted sets * 100M entries * 56 bytes = 22.4 GB. Fits in a 32 GB Redis instance.
Cleanup: Old daily leaderboards (older than 7 days) are deleted. Old weekly leaderboards (older than 4 weeks) are archived to PostgreSQL for historical queries. Alltime is never deleted.
Reset handling: When the daily leaderboard resets at midnight UTC, the old sorted set is simply abandoned (with a TTL for auto-deletion). The new day's set starts empty and fills up as players score. No expensive "reset all scores to 0" operation.
Deep Dive 3: Anti-Cheat (Server-Authoritative Scores)
The #1 rule of leaderboard integrity: never trust the client.
Client-submitted scores are trivially spoofable:
// Client sends: POST /api/score { "player_id": "123", "score": 999999 }
// An attacker can send this with any score.
Server-authoritative scores: The game server calculates the score based on game events, not the client.
# WRONG: Client sends final score
@app.post("/api/score")
def submit_score(player_id, score):
redis.zadd("leaderboard", {player_id: score}) # NO!
# RIGHT: Server calculates score from game events
@app.post("/api/game/complete")
def complete_game(player_id, game_session_id):
session = get_game_session(game_session_id)
# Validate session: was this game actually played?
if not session or session.player_id != player_id:
return 403
# Calculate score from server-tracked events
score = calculate_score(
kills=session.kills,
time_survived=session.time_survived,
accuracy=session.accuracy
)
# Validate: is this score physically possible?
if score > MAX_POSSIBLE_SCORE:
flag_for_review(player_id, score)
return 400
redis.zincrby("leaderboard", score, player_id)
Statistical anomaly detection: Track each player's score distribution. If a player's average score is 500 and they suddenly submit 50,000, flag for review. If a player's scores improve by 10x overnight without increasing play time, flag for review.
Replay verification: For top 100 leaderboard entries, store the full game replay (sequence of inputs). A verification system replays the inputs to confirm the score. Clash Royale and many competitive games use this for tournament integrity.
Alternative Designs
Alternative 1: B-tree with Augmented Counts (PostgreSQL)
Use a B-tree index on score, augmented with subtree counts at each node. The augmented tree supports O(log N) rank queries. PostgreSQL does not support this natively, but you can approximate it with a materialized view that caches rank.
Alternative 2: Segment Tree in Custom Service
Build an in-memory segment tree over the score range. Each leaf represents a score value. Internal nodes store the count of players in that score range. Rank query: sum of counts in all nodes with higher scores. Update: increment one leaf and propagate. Both O(log S) where S is the score range.
Alternative 3: Database with Periodic Rank Snapshot
Compute ranks every 5 minutes (batch job) and cache the results. Between snapshots, ranks are slightly stale.
| Aspect | Redis Sorted Set | Augmented B-tree (DB) | Segment Tree | Periodic Snapshot |
|---|---|---|---|---|
| Rank query latency | O(log N), sub-ms | O(log N), 1-5ms | O(log S), sub-ms | O(1), sub-ms |
| Update latency | O(log N), sub-ms | O(log N), 1-10ms | O(log S), sub-ms | Batch (minutes) |
| Memory (100M players) | 5.6 GB | DB-managed | Score range dependent | Rank table: 1.6 GB |
| Exactness | Exact | Exact | Exact | Stale (5 min) |
| Operational complexity | Low (managed Redis) | Low (PostgreSQL) | High (custom service) | Low |
| Scale limit | ~500M (single instance) | ~50M (B-tree depth) | Unlimited (sharded) | Unlimited |
| Friend leaderboard | Manual (Solution 1/2/3) | SQL JOIN | Not natively supported | Precomputed |
Redis sorted set is the right answer for 99% of leaderboard interviews. Mention the segment tree if the interviewer pushes to 1B+ players or needs O(1) rank queries. Mention periodic snapshots if eventual consistency is acceptable (most non-competitive leaderboards).
Scaling Math Verification
Redis sorted set at 100M entries:
- Memory: 5.6 GB. Single Redis instance (16 GB) handles this with 10 GB to spare.
- ZADD at 50K/sec: 50K * 27 skip list operations = 1.35M ops/sec. Redis handles 50M+ internal ops/sec. 2.7% utilization.
- ZREVRANK at 500K/sec: 500K * 27 = 13.5M ops/sec. 27% utilization.
- Combined: 30% utilization. Massive headroom.
Friend leaderboard (Solution 1):
- 500K requests/sec * 50 ZSCORE calls = 25M ZSCORE ops/sec. ZSCORE is O(1). Redis handles this.
- Round trip: 1 pipelined call per request. At 500K requests/sec, Redis processes 500K pipelines/sec. Each pipeline has 50 commands. Total: 25M commands/sec. At the edge of a single Redis instance's capacity (~30M ops/sec for O(1) commands). Add a read replica for headroom.
Time-scoped leaderboards (4 sets):
- Memory: 4 * 5.6 GB = 22.4 GB. Need a 32 GB Redis instance.
- Writes: 50K * 4 ZINCRBY = 200K/sec. Each ZINCRBY is O(log N). Total: 200K * 27 = 5.4M internal ops/sec. 10.8% utilization.
Failure Analysis
| Component | Current capacity | At 10x (1B players) | Breaks? | Fix |
|---|---|---|---|---|
| Redis memory | 5.6 GB (100M) | 56 GB (1B) | Maybe | 64 GB Redis instance, or shard by score range |
| ZRANK throughput | 13.5M internal ops/sec | 135M ops/sec | Yes | Shard leaderboard by score range (top 10K exact, rest approximate) |
| ZADD throughput | 1.35M internal ops/sec | 13.5M ops/sec | No | Redis handles this |
| Friend leaderboard | 25M ZSCORE ops/sec | 250M ops/sec | Yes | Precompute friend boards for active users, or use approximation |
| Time-scoped sets | 22.4 GB | 224 GB | Yes | Shard each scope to a separate Redis instance |
| Persistence (PostgreSQL) | Async write-behind | 500K writes/sec | Maybe | Batch writes every 5 seconds instead of per-update |
The first bottleneck at 1 billion players is Redis memory (56 GB for the sorted set alone, plus time-scoped copies). The fix is architectural: exact leaderboard (sorted set) for the top 100,000 players, approximate leaderboard (percentile buckets) for everyone else. This reduces memory from 56 GB to ~6 GB (100K sorted set entries + bucket counters).
The second bottleneck is friend leaderboard compute at 250M ZSCORE ops/sec. At this scale, precompute friend leaderboards asynchronously: when a player's score changes, push the update to their friends' precomputed boards via a Kafka consumer. This shifts the cost from read time to write time.
What's Expected at Each Level
| Aspect | Mid-Level | Senior | Staff+ |
|---|---|---|---|
| Core data structure | "Use a sorted structure" | Redis sorted sets, ZADD/ZRANK, O(log N) | Skip list internals, why not B-tree, memory layout |
| Tie-breaking | "Sort by timestamp too" | Encode timestamp in score float | Precision limits of IEEE 754, alternative concatenated keys |
| Friend leaderboard | "Filter the global leaderboard" | Pipeline ZSCORE for all friends | Three solutions with trade-offs, hybrid active/on-demand |
| Scale to 1B | "Shard Redis" | Multiple Redis instances | Percentile buckets for approximate rank, exact for top K only |
| Time-scoped boards | "Reset every day" | Separate sorted sets per time window | TTL-based cleanup, no explicit reset, memory math for 4 scopes |
| Anti-cheat | "Validate scores" | Server-authoritative scores | Statistical anomaly detection, replay verification |
| Persistence | "It's in Redis" | Async write to PostgreSQL | RDB snapshots, AOF persistence, recovery strategy |
| Real-world reference | None | "Redis sorted sets" | Skip list vs B-tree trade-off, Clash Royale's replay verification |
The single most important signal at any level: do you immediately reach for Redis sorted sets? This is one of the few system design problems where there is a near-perfect data structure match. The sorted set gives you O(log N) updates, O(log N) rank queries, and O(log N + K) top-K queries, all in-memory, all from a single Redis instance for up to 500M players. The interview depth comes from what you do beyond the sorted set: friend leaderboards, tie-breaking, and approximate ranking at billion scale.
References from Our Courses
- Redis Data Structures and Use Cases — sorted sets for O(log N) rank queries
- Partition and Clustering Keys — Cassandra for historical leaderboard snapshots
- Flink and Stream Processing — real-time score aggregation from event streams
Red Team This Design
Ready to stress-test this architecture? The Attack companion tears apart every decision in this design — from hardware physics to security holes to what actually happens at 10x scale.