Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Real-Time Concurrent Gaming Leaderboard
with Range & Rank Queries.

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.
Start the journey7 stages
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

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.

Full walkthrough · 7 stages
01
STAGE 01 · REQUIREMENTS & TIE-BREAKINGfoundation

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 earliest achieved_at_ms; identical timestamps break ties deterministically by player_id.
02
STAGE 02 · CORE ENGINEfoundation

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:

  1. Update(player_id, delta): Look up (old_score, old_ts) in HashMap in O(1)O(1) -> remove (old_score, old_ts, player_id) from Skip List in O(log⁡N)O(\log N) -> insert (new_score, now_ts, player_id) in O(log⁡N)O(\log N).
  2. GetNeighbors(player_id, k=5): Find rank rr in O(log⁡N)O(\log N), seek to max(1, r - 5) via span pointers in O(log⁡N)O(\log N), and walk 11 Level-0 pointers forward.

Score Update & Neighbor-Rank Query Flow

HashMap LookupSkip List DeleteSkip List InsertSpan Rank Seek
03
STAGE 03 · HORIZONTAL SCALINGintermediate

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 atomic total_players counter.
  • Global Rank: global_rank = sum(counts of higher score buckets) + local_rank_in_bucket.
  • Top-K Cache: Serve Top 100 from the highest bucket (cached for 200 ms at edge) so 80%+ of read traffic never hits the core engine.
04
STAGE 04 · SAFE ENGINE CODEintermediate

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)))
05
STAGE 05 · DURABILITYintermediate

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.
06
STAGE 06 · SKEW MITIGATIONadvanced

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_shards for the bottom 'unranked' tier (where exact rank isn't shown, only percentile/approximate rank).
07
STAGE 07 · GOTCHASadvanced

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 Redis ZSET hack) 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) and insert(new_bucket) via an idempotent saga/compensating retry so the player never appears in two buckets simultaneously.
Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does a real-time leaderboard pair a HashMap with an indexed Skip List instead of using only a Skip List?

Recommended Learning Flow