How to design a real-time leaderboard — cheat sheet — System Design

A leaderboard is two unrelated problems: top-k shards perfectly, rank is a global aggregate that does not, and rank is where all the work goes.

The core distinction

Top-k: decomposable. A global top-10 member is in its own shard’s top 10, so merge 10 x 64 = 640 local entries, take 10. One fan-out, microseconds.
Rank = 1 + count of players scoring higher. A global count; local ranks do not sum. No cheap local answer.
Sorted set (ZSET): members with numeric scores kept in score order. Rank 1 is best.
Redis commands: ZADD (write score), ZREVRANK (rank from top), ZCOUNT (count in range), ZUNIONSTORE (merge sets).

Numbers and targets

500 M registered, 50 M DAU, 10 submits + 5 rank reads per active player/day (all rates from DAU).
Submissions 5,787/s, peak x3 = 17,361/s. Rank reads 2,894/s, peak x3 = 8,682/s. Ratio ~2 writes per read (backwards from most systems; forbids precomputing per-player rank).
Score visible < 1 s; rank p99 < 50 ms.
Accuracy: exact in top 10,000, within 1% below that (a fixed error is 500x too large for the champion, invisible for the median). Accuracy must vary with rank.
ZSET is a cache; the append-only score log is the record.

Cost of the sorted set

ZSET = skiplist (ordered, O(log n) rank via span sums) + hash table (O(1) point lookup). Every player paid for twice.
~100 bytes per entry; 500 M x 100 = 50 GB (12.5x over the ~4 GB payload). That tax buys O(log n) rank.
Skiplist promotion prob p = 0.25 fixes avg height 1/(1-p) = 1.33 levels. A rank touches ~53 nodes x 100 ns = 5.3 us. (2.9 us quote is wrong: it assumes p=0.5; measured touches ~1.8x log2 n.)
CPU is not the bind: 17,361 x 5.3 us = 9.2% of one core.

What binds first

Limit	Number	Consequence
Memory	50 GB/process	> ~25 GB: `BGSAVE`/failover slow
Persistence fork	copy-on-write doubles RSS to 100 GB	provision 2x or drop persistence
Failover	async repl 1 ms lag = ~17 writes in flight	~17 scores lost unless log is record
One key	no sharding for one ZSET	every scaling answer splits it

Rebuild from log: 500M / 200k ZADD/s = 41.7 min RTO. Snapshot + tail replay keeps it to minutes.
Shard into S = 64 ZSETs on a hash ring by player_id: 0.78 GB and 7.8 M players each; adding a machine moves only 1/(N+1).

Rank at scale: two answers

A. Exact scatter-gather: local ranks don’t sum but local counts do. Each shard ZCOUNT above score s, add 64 answers = exact. Dies to tail amplification: latency = max of S samples, 1 - 0.99^S = 47% at S=64, 99.4% at S=512. Hedged requests (duplicate after p95, ~5% extra load) buy back most, works to a few hundred shards.
B. Bucketed histogram: cut score line into B equi-depth buckets (each N/B players; equi-width piles 25 M into the modal bucket, 50x worse error). Approx rank = count in buckets above; worst error = one bucket’s population.
- Size: N/B <= 0.01 x 10,000 = 100 → B >= 5,000,000 buckets, 80 MB. Query via Fenwick tree (prefix sum + update O(log B)), ~64 refs = 6.4 us, ~12% of a core, one hop.
- A bucket boundary is a score, so B is capped by distinct scores: 21-bit field floors error at 238; 28-bit gives 268 M distinct scores.

Exact head, bucketed tail

Same error means opposite things: 5,000 at rank 10 = 500x; at rank 10 M = 0.0005.
Keep top 10,000 as an exact ZSET (1 MB, replicated to every read machine); histogram for everyone below; scatter-gather only for explicit exact deep rank (profile/dispute).

flowchart TD
    R["rank(player)"] --> H{"in top 10,000?"}
    H -->|yes| HEAD["exact head board, 1 MB"]
    H -->|no| E{"caller wants exact?"}
    E -->|no| HIST["histogram, one hop, 6.4 us"]
    E -->|yes| SG["scatter-gather 64x ZCOUNT, slow tail"]

Ties, updates, windows

Redis breaks score ties lexically by member; players expect first-to-reach wins. Pack into the double’s 53 exact bits: points * 2**32 + (2**32 - 1 - t_seconds). Max = 2^53 - 1, nothing rounds. Rebase clock to season start → 28 bits for points (also feeds the histogram).
Timestamp at the score service, not the game server (clock skew/rewind reorders history).
Idempotency: ZADD board GT composite member (writes only if greater) is a safe no-op replay. ZINCRBY is not (double-counts) → dedup on match_id.
Windowed boards: dailies are the primitive; roll weeklies/monthlies nightly and incrementally with ZUNIONSTORE ... AGGREGATE MAX (SUM invents phantom scores and blows the 2^53 budget). Multipliers 3.5x weekly, 8x monthly (distinct players, not 7x/30x). Snapshot closed windows to disk, TTL each daily key; all-time never expires.

Cheating

Score is server-authoritative computed from match events, or it is nothing. Client signing fails: key ships in binary, a signed forgery beats your own anomaly detection.
Layers: (1) server simulation, (2) plausibility bounds, (3) token bucket rate limit tuned to honest behavior (refill 1/60 s, cap 5 → 144x honest max), (4) anomaly quarantine not rejection (p99.99 flags 50,000/day; withhold pending replay), (5) idempotency (match_id dedup + ZADD GT).

Rejected alternatives

SQL COUNT(*) WHERE score > x: index walk ~250 M rows, ~250 s.
Precomputed rank column: staleness (2 writes/read, rank shifts in seconds).
Streaming quantile sketch (KLL, t-digest): no deletion; a score update is delete + insert.
Elasticsearch/OLAP: p99 in hundreds of ms, no O(log n) rank.