Design a real-time global gaming leaderboard for 50M daily active players handling 200K score updates/sec and 500K rank/top-K queries/sec with < 10 ms p99 latency, deterministic tie-breaking (higher score first; earlier timestamp wins ties), neighbor-window queries ('show 5 players above and below me'), and crash durability.
From patterns to decisions.
Pair an in-memory HashMap + `span`-indexed Skip List for O(log N) rank/neighbor queries with composite `(score DESC, ts ASC)` keys, shard/partition routing for >200K RPS, and async WAL/snapshot persistence.
Scale Math & Deterministic Composite Sort Keys.
- Scale: 50M players × ~96 bytes (node + HashMap entry) ≈ 4.8 GB RAM—fits easily across a small cluster of memory-optimized nodes.
- Deterministic Tie-Breaking: Store
( -score, achieved_at_ms, player_id )as the sort key. Higher scores sort first; equal scores sort by earliestachieved_at_ms; identical timestamps break ties deterministically byplayer_id.
HashMap + Span-Indexed Skip List for O(log N) Rank & Neighbors.
A Skip List alone cannot find a player's old score in O(1) when updating score += delta. Pairing it with a HashMap solves both halves:
- Update(
player_id, delta): Look up(old_score, old_ts)in HashMap in -> remove(old_score, old_ts, player_id)from Skip List in -> insert(new_score, now_ts, player_id)in . - GetNeighbors(
player_id, k=5): Find rank in , seek tomax(1, r - 5)viaspanpointers in , and walk 11 Level-0 pointers forward.
Score Update & Neighbor-Rank Query Flow
Scaling Past Single-Node Throughput with Score-Range Buckets.
A single-threaded Redis ZSET tops out around ~100K ops/sec and holds ~5 GB on one core. To scale:
- Score-Range Partitioning: Split the score space into dynamic buckets (e.g.,
[0–1000),[1000–5000),[5000+)), each with its own Skip List shard and an atomictotal_playerscounter. - Global Rank:
global_rank = sum(counts of higher score buckets) + local_rank_in_bucket. - Top-K Cache: Serve
Top 100from the highest bucket (cached for 200 ms at edge) so 80%+ of read traffic never hits the core engine.
Idempotent Score Update with WAL Append & Bounded Retry/DLQ.
Game servers frequently retry timed-out RPCs; applying +delta twice corrupts rankings. Gate updates with a short-TTL idempotency key (match_id:player_id) and route failed WAL flushes through bounded retries to a DLQ:
import time, random
def apply_score_update(dedup_cache, hashmap, skiplist, wal, dlq, event, max_retries=3):
idem_key = f"{event['match_id']}:{event['player_id']}"
if not dedup_cache.set_if_absent(idem_key, ttl_sec=3600):
return hashmap.get(event['player_id']) # Idempotent no-op on retry
old = hashmap.get(event['player_id'])
new_score = (old.score if old else 0) + event['delta']
new_key = (-new_score, event['ts_ms'], event['player_id'])
if old:
skiplist.delete((-old.score, old.ts_ms, event['player_id']))
skiplist.insert(new_key, new_score)
hashmap[event['player_id']] = new_key
for attempt in range(max_retries):
try:
wal.append_async(event['player_id'], new_score, event['ts_ms'])
return new_key
except WalTransientError:
if attempt == max_retries - 1:
dlq.publish(event, reason='wal_append_failed')
return new_key
time.sleep(min(0.5, 0.02 * (2 ** attempt) + random.uniform(0, 0.02)))Async WAL, Periodic Snapshots & Fast Node Recovery.
- Periodic Snapshots (fork/CoW): Every 5–10 minutes, write a compact binary snapshot
(player_id, score, ts_ms)to object storage. - WAL Replay: On restart, load the latest snapshot and replay only the trailing WAL segments in sequential order—restoring 10M entries per shard in < 5 seconds.
Handling Score-Bucket Skew (e.g., 80% of Players at Score 0–100).
In real games, 70–80% of players sit in the lowest score bracket. Fix this with adaptive bucket splitting:
- When a bucket exceeds 5M entries or 80K writes/sec, split it either by finer score sub-ranges or by
hash(player_id) % sub_shardsfor the bottom 'unranked' tier (where exact rank isn't shown, only percentile/approximate rank).
Floating-Point Precision Loss, Tie-Breaker Collisions & Cross-Bucket Moves.
- Float64 Bit-Packing Overflow: Packing
(score, inverted_ts)into a 53-bit IEEE-754 float (common RedisZSEThack) silently loses timestamp precision for large scores. Use a native 128-bit composite key or separate(score, ts)comparator. - Cross-Bucket Moves: When a player's score crosses a bucket boundary, execute
remove(old_bucket)andinsert(new_bucket)via an idempotent saga/compensating retry so the player never appears in two buckets simultaneously.
Practice: Make the trade-off yourself.
Why does a real-time leaderboard pair a HashMap with an indexed Skip List instead of using only a Skip List?