Q71 — Design a live leaderboard (gaming or contests at scale)

What the system must do

Players earn scores during a game or contest. The leaderboard shows the current top N players ranked by score. Players can look up their own rank among all participants. Scores update in real time as players earn points.

Requirements:

Update a player's score instantly (score events arrive continuously)
Query top-N players by score (global leaderboard)
Query a specific player's rank (out of potentially millions)
Support millions of players, thousands of score updates per second
Near-real-time display (leaderboard feels live, not delayed by minutes)

Why a relational database is not enough

The naive implementation: store (player_id, score) in a Postgres table, query SELECT player_id, score FROM scores ORDER BY score DESC LIMIT 100 for the top-100.

This works fine at 10,000 players. At 10 million players with thousands of score updates per second:

Reads: ORDER BY score DESC LIMIT 100 is an index scan on the score column. With a B-tree index on score, this is fast for the top-100. But "what is player 42's rank?" requires SELECT COUNT(*) FROM scores WHERE score > (SELECT score FROM scores WHERE player_id = 42). Counting all rows with a higher score is O(N) on large tables — taking seconds at millions of rows.

Writes: thousands of UPDATEs per second to the scores table, each requiring a B-tree index update. The index must be rebalanced for each update. At high write rates, this creates index contention and write amplification.

Concurrent read-write contention: heavy read traffic (leaderboard polls) and heavy write traffic (score updates) on the same table create lock contention and degrade both.

The database is fundamentally the wrong tool for this specific problem.

Redis sorted sets — the right data structure

Redis sorted sets (ZSETs) are designed for exactly this problem. A sorted set is a collection of members, each with a floating-point score. Members are sorted by score. Operations:

code

ZADD leaderboard <score> <player_id>   # add or update player's score → O(log N)
ZREVRANK leaderboard <player_id>       # player's rank (0 = highest score) → O(log N)
ZREVRANGE leaderboard 0 99 WITHSCORES # top-100 players with scores → O(log N + 100)
ZINCRBY leaderboard <delta> <player_id> # increment score → O(log N)

Every operation is O(log N) (plus M for the M entries a range returns) — fast even at millions of players. Redis keeps the sorted set data structure updated in memory on every ZADD/ZINCRBY. No separate index rebuild, no sort at query time.

At 10M players in the sorted set:

ZADD (score update): ~1ms
ZREVRANK (get rank): ~1ms
ZREVRANGE 0 99 (top-100): ~2ms

Thousands of score updates per second: Redis can handle 100,000+ operations per second on a single instance.

This is why leaderboards are the canonical Redis sorted set use case — the data structure is perfectly matched to the access pattern.

Data model

code

Redis:
  Key: "leaderboard:game_42:season_3"
  ZSET: { player_id → score }
  ZADD / ZINCRBY for updates
  ZREVRANGE for top-N
  ZREVRANK for player rank

Postgres (source of truth / audit):
  scores(player_id, game_id, score, updated_at)
  Used for historical reporting, compliance, rebuilding Redis on failure

Redis is the hot path — all live queries go to Redis. Postgres is the durable record — updated asynchronously from Redis (or from the score events). If Redis data is lost (Redis restart without persistence), rebuild the sorted set from Postgres.

Handling score updates

Score events come from the game servers: "player 42 earned 150 points." These must be applied to the leaderboard atomically and quickly.

Synchronous path: game server → API → ZINCRBY leaderboard 150 player_42 → done. The update is immediately reflected in all leaderboard queries. This is correct and simple.

At very high event rates (100,000+ score events/second across all games), batch updates reduce Redis round trips: accumulate events per player in a short window (100ms), then apply the aggregate increment once. Reduces network overhead at the cost of 100ms staleness.

Async path: for non-critical contests, score events go to Kafka. A consumer applies them to Redis in batches. Provides backpressure (Q32) and decouples game servers from Redis. Adds latency (100ms–1s) to leaderboard updates — acceptable for many use cases, not for live competitive games.

Global rank at scale — the approximation trade-off

ZREVRANK gives the exact rank among all players in the sorted set — but only for a single sorted set. For a global leaderboard across 10M players, one Redis sorted set is fine (Redis ZSETs handle tens of millions of members efficiently).

But if the leaderboard is partitioned by region (each region has a regional leaderboard plus a global leaderboard), or by player segment (casual vs. competitive tiers), computing cross-partition rank requires merging multiple sorted sets. Redis supports ZUNIONSTORE (merge multiple ZSETs into one) — use this to periodically (every minute) compute the combined global leaderboard from regional shards.

For true real-time global rank with billions of players (beyond what fits in one Redis instance): approximate rank using count-min sketch or order statistics trees — probabilistic data structures that estimate rank within a confidence interval. Saves memory at the cost of exact precision.

Near-real-time display without hammering Redis

The leaderboard page might be viewed by 100,000 users simultaneously, each polling for updates. 100,000 ZREVRANGE calls per second to Redis for the same top-100 is wasteful — the top-100 changes rarely.

Application-layer cache: cache the top-100 result for 1 second in a local in-memory cache on each API server. 100,000 users across 10 servers = 10,000 requests/server. One actual Redis call per second per server, 10 total. The leaderboard is 1 second stale — imperceptible to users.

Push via WebSockets/SSE: instead of polling, push leaderboard updates to connected clients. A background process watches for changes in the top-N (compare current top-100 to previous top-100 every second), and pushes the diff to connected clients. Users see updates without polling overhead.

The mental model

code

Problem with relational DB:
  ORDER BY score DESC = full index scan for top-N
  COUNT(*) WHERE score > X = O(N) rank computation
  Write + read contention under high update rate

Redis sorted set = purpose-built for this:
  ZADD: O(log N) insert/update
  ZINCRBY: O(log N) increment
  ZREVRANGE 0 99: O(log N + 100) top-100
  ZREVRANK: O(log N) exact rank
  Handles millions of members, 100K ops/sec on single instance

Architecture:
  Hot path: score event → ZINCRBY leaderboard → instant update
  Cold path: async sync to Postgres (durable record)
  Rebuild: on Redis failure → replay from Postgres

Display optimization:
  1-second app cache → 100K viewers = O(10) Redis calls/sec
  WebSocket push → diff-based updates, no polling overhead

Partitioned leaderboard:
  Regional ZSETs → ZUNIONSTORE periodically → global ZSET
  Approximate rank at billions scale: count-min sketch

Update rate:
  Low (thousands/sec): synchronous ZINCRBY
  High (100K+/sec): batch increments per player per 100ms window

Key insight: the data structure determines the system
  Redis sorted set provides O(log N) for every operation you need
  When you find the right data structure, the architecture becomes obvious

The leaderboard is a perfect example of data structure–driven design. Once you know that Redis sorted sets give O(log N) for rank, top-N, and update — all three operations you need — the architecture follows naturally. The interesting work is handling scale (batching, caching the display, partitioned global leaderboards) not the core mechanism.