Game Leaderboard System Design

Design a real-time global game leaderboard that supports score updates and top-K queries for millions of players. The interviewer starts from a single-server skeleton (10 reads / 1 write per second, no friends) and incrementally piles on scale, friend leaderboards, time windows, and replication. Requirements Functional: submit a score for a player; read the current top-K (K defaults to 100, treat as configurable — top-10 vs top-100 only changes the cutoff cache and leaderboard size, not the architecture); read a player's personal best for a game (shown immediately after a session ends); read a specific player's rank; read a player's neighborhood (top-K around the player). The client must learn whether a submission updated personal-best, leaderboard, both, or neither. The interviewer may add friend-leaderboards and time-windowed leaderboards (daily, weekly, all-time) as follow-ups. Core framing: this is not a "store every score forever" system. Only two things matter to persist: a score that sets a new personal best, or one that breaks into the top-K. That single requirement reshapes the whole traffic pattern — a newly launched game bursts writes, but mature games go quiet because the top-K cutoff rises and most players stop qualifying. Both client and server can filter most writes before they hit durable storage. Priorities: availability over consistency. A slightly stale replica or one degraded region should show a slightly old leaderboard and let clients retry submission, rather than take the feature offline. Anti-cheat / score verification is assumed handled upstream by trusted game servers — the focus is storage, latency, and scaling. Scale anchor (incremental): starts at ~10 reads + 1 write per second on a single box. The interviewer escalates step by step toward 100K writes per second and 1M reads per second across a global user base. Decisions the interviewer drives at: Choice of primary storage (sorted set vs relational vs custom). Pushing toward Redis sorted sets is expected. Sharding strategy as scale grows (shard by player-id range, by game-id, by score band). Top-K read path under sharding (gather-and-merge from shards vs maintain a global top-K). Time-window aggregation (rolling Redis sorted sets per window vs an offline batch job feeding a serving cache). Friend-leaderboard scoping (small-friend-set fan-out vs precomputed materialized friend lists). Notes The single-server starting point is intentional. The interviewer wants to see whether the candidate can describe the trivial design ("in-memory sorted map, O(log N) per write, O(K) per top-K") before complicating it. Skipping ahead to Redis-sharded losses you points. The canonical primary store is Redis sorted sets (ZSET). ZADD and ZINCRBY for score update are O(log N); ZREVRANGE 0 K-1 WITHSCORES for top-K is O(log N + K); ZREVRANK for a player's rank is O(log N) and avoids a full scan. This combination is the cleanest building block for the design. Storage envelope for the primary store is small: roughly 26 bytes per entry × 25M monthly actives ≈ 650MB raw, doubled by skip-list overhead — still well within a single Redis instance for the whole leaderboard. The need to shard is driven by write throughput and replica fan-out, not by storage. Sharding the sorted set by player-id (Redis Cluster CRC16-mod-16384 slotting) divides writes evenly but turns top-K into a scatter-gather: fetch the top K from each shard, merge client-side, return top K of the union. Sharding by score band (one shard per score decile) makes top-K cheap (it lives in the top shard) but creates hot-shard problems on rank queries, breaks down when celebrity scores cross band boundaries, and complicates rebalancing as the score distribution shifts. For the friend leaderboard, the cleanest answer is to keep the global leaderboard untouched and compute friend-leaderboards on read: fetch the player's friend list (capped at ~1000), then ZSCORE each friend in parallel and sort client-side. This stays O(F) per query and avoids a friend-graph materialization layer. For time windows (daily / weekly), maintain one sorted set per window and roll the window over at the boundary. Tombstone old windows on a TTL. Hot-shard handling: a celebrity player whose score updates draw a thundering herd of rank queries benefits from a per-player rank cache with a short TTL (~1 second). The cache absorbs the duplicate reads. Read replicas are the cheapest read-scale lever; eventual consistency on rank reads is almost always acceptable in this domain. Write-filtering as the core optimization Separate "can this score matter?" from "store this score forever." Most scores should die in cache-level filtering and never become durable writes. Two filter layers: Client-side: the client caches its last-seen personal best and the leaderboard cutoff, and only submits if the new score beats one of them. Stale local state is fine — an old cutoff just lets a few extra candidates through; the server re-checks. Server-side: the submit API re-checks the candidate against the authoritative cached PB and cutoff (the client may be stale or malicious) and rejects obvious non-qualifiers without touching the database. Consequence over a game's lifetime: mature games become read-heavy / write-light (cutoff has risen, few qualify), while new launches are write-bursty ("all scores matter" because the top-K isn't full yet — worst case, nearly every finished session submits). This asymmetry is the main argument for cache-first reads plus a queue-buffered write path. Concrete capacity anchors Traffic shape (game-studio scale, not generic social): ~10M DAU, ~3 sessions/player/day → ~30M session-ends/day ≈ ~350/s average; evening/launch peak ~15× → ~5,000 session-ends/s. Steady-state mature games: only ~2% beat local PB or cutoff → ~100 candidate writes/s. Launch-day hot game: one new game's write peak can approach the full ~5,000/s. Reads: design for ~50,000 cache reads/s peak across games. Hot-data size is small enough to justify aggressive caching: leaderboard cache ≈ 100K games × 100 entries × ~64 bytes ≈ ~640MB raw; personal-best cache ≈ 200M (user_id, game_id) pairs × ~32 bytes ≈ ~6.4GB raw. The hard problem is not storage size — it is coordinating updates during bursts and on hot games. NFR targets worth stating: leaderboard & PB reads P95 < 50ms from cache; submission ack P95 < 200ms; availability 99.95%; eventual consistency acceptable (a few hundred ms of staleness is fine); no accepted submission may be lost once acked. Read models and cache keys Treat the two core queries as separate read models — do not force one table/query plan to answer both. Leaderboard query = "top 100 for game_id"; personal-best query = "best score for (game_id, user_id)". Practical scaling split: shard PersonalBest by hash of (game_id, user_id) (naturally horizontal); keep the per-game top-K as a single tiny cached object (Redis sorted set or processor memory) with DB snapshots behind it. Concrete cache keys to name out loud: top100:{game_id} -> sorted leaderboard payload cutoff:{game_id} -> current Kth-place score (e.g. 100th) pb:{game_id}:{user_id} -> player's best score leaderboard_version:{game_id} -> monotonic version for cache refresh / sync Rank is derived from a deterministic sort order, not stored as an independently edited field. Canonical tie-break: (score DESC, achieved_at ASC, submission_id ASC). Write path: durable log + processor Submit API validates the idempotency key and request shape, re-checks cached PB/cutoff, returns ignored for non-qualifiers, and otherwise appends the candidate to a durable log / queue partitioned by game_id (so updates for one game stay ordered). The queue's real job is not average throughput — it is launch-day burst absorption, natural per-game partitioning, retry/backoff during DB or cache hiccups, and scaling processors independently from APIs. A leaderboard processor consumes the log per game partition (one logical ordered updater per game), updates top100 / cutoff / pb / leaderboard_version in cache, then materializes snapshots and an audit trail into the primary DB. Because the log is durable, the DB can lag briefly without losing accepted submissions; Redis loss is recovered by DB snapshot + recent log replay while serving degraded responses during warm-up. Idempotency is mandatory: clients buffer pending qualifying scores locally during outages and retry with the same idempotency_key; dedupe by (game_id, user_id, session_id, idempotency_key). Out-of-order retries are handled by only raising PB when the new score is strictly larger than the stored best. Consistency dial: default availability-first — POST /scores durably queues, cache updates land within sub-second lag, client reads updated context from cache. If the interviewer insists on exact read-after-write on the submit response, upgrade the async processor into a per-game synchronous owner service that appends to the durable log and updates cache before ACK. Same architecture, higher complexity, lower staleness. A combined score-context read (returns PB + cutoff + version + top-100 together) is practical because the client wants both values right after a match. Signature sketch: # returns 200 with combined context; reads served entirely from cache def get_score_context(game_id, user_id) -> dict: return { "personal_best": cache.get(f"pb:{game_id}:{user_id}"), "cutoff_score": cache.get(f"cutoff:{game_id}"), "leaderboard_version": cache.get(f"leaderboard_version:{game_id}"), "entries": cache.get(f"top100:{game_id}"), # top-K payload } Hot-game handling (hierarchical top-K) The anti-pattern to name and reject: splitting one hot game's exact leaderboard into gameId-1, gameId-2, … and merging partial leaderboards on every read. That makes exact realtime ranking awkward. Better: keep one exact logical owner for a game's top-K, and scale around that owner. Assign hot games dedicated partitions/machines; pre-filter at the client and again at the submit API; and if still too hot, add hierarchical top-K: each ingress shard keeps a local candidate heap for the hot game and forwards only scores above a moving threshold to the game's global owner, which merges the shard top-K streams and maintains the exact top 100. Reserve this for truly extreme hotspots. Closing line: "I would not shard the exact global leaderboard and merge on every read. I would keep one exact owner for top 100 and use pre-filtering or hierarchical top-K before it." Preparation Memorize the Redis sorted-set API surface (ZADD, ZREVRANGE, ZRANK, ZSCORE) and their complexity. This is the load-bearing API for the round. Drill the four follow-up decisions out loud: sharding axis, top-K under sharding, time-window strategy, friend-leaderboard scoping. Each should take ~2 minutes to talk through. Have a single back-pocket trade-off comparison ready: sorted-set Redis vs an OLTP database with a (player_id, score) index. Be able to defend Redis on write throughput and on the rank-query latency floor. Walk the interviewer up the scale curve incrementally — start with single-box numbers, redesign at each order-of-magnitude jump. Jumping straight to a 100-shard cluster signals weak scoping discipline. Rehearse the two-tier write-filter argument (client PB/cutoff cache → server re-check) and be able to derive the "write traffic decays for mature games, bursts on launch" insight on the spot — it is the single point interviewers reward most on this prompt. Be ready to separate the personal-best read model ((game_id, user_id), hash-shardable) from the leaderboard read model (tiny per-game ranked object) and to defend hierarchical top-K over suffix-sharding for a single insanely-hot game.