Design a Leaderboard / Top-K / Distributed Counter

A trap wearing a trivial costume

A leaderboard looks trivial ("sort players by score") and is a trap, because the naive SQL answer collapses under load. The interview tests whether you know the right data structure (a sorted set), how to scale it, how to handle hot counters, and where approximation is a legitimate win.

The sorted set

The wrong instinct is SELECT ... ORDER BY score DESC LIMIT 10 plus, for a player's rank, SELECT COUNT(*) WHERE score > my_score. Both do a full sort or scan on every request, and at tens of millions of players and constant score updates they melt. The right primitive is a Redis sorted set (ZSET). A ZSET keeps members ordered by score in a skip list, giving O(log n) inserts/updates (ZADD), O(log n + k) top-K reads (ZREVRANGE 0 k), and O(log n) rank lookup (ZREVRANK). That single structure answers both "top 10" and "my rank" without scanning everyone.

Interview nuance: the interviewer wants you to reject the SQL-sort-per-request answer and name the sorted set with its complexities. Saying "Redis ZSET, ZREVRANGE for top-K, ZREVRANK for my rank, both O(log n)" is the seniority signal.

Sharding the ZSET

A single ZSET has limits at tens of millions of members and high write rate, so shard it. Segment by natural boundaries (region, league, time window like daily/weekly boards) so each ZSET stays a manageable size, and maintain a smaller global top-N ZSET merged from the top of each shard for the global board (only the top entries of each shard can be globally top-N, so you merge cheaply). All-time boards are snapshotted periodically. "My rank" within a segment is exact; global exact rank across shards is expensive, so global rank is often approximate or bucketed ("top 1%").

Hot counters and approximation

A single hot key (global likes, total views, a mega-popular player's score) taking millions of increments/sec becomes a write hotspot and lock contention point. The fix is a sharded/distributed counter: split the logical counter into N sub-counters (counter:0..N-1), increment a random shard per write so writes fan out, and sum the N shards on read. This trades a slightly more expensive read for massive write parallelism.

Where exactness is not required, approximate structures are a big memory win. HyperLogLog counts unique items (unique players seen, unique visitors) with ~2 percent error in ~12 KB regardless of cardinality, versus gigabytes for an exact set. Count-Min Sketch estimates per-item frequencies and heavy hitters (approximate top-K of a stream) in fixed memory with bounded overcount. Use these when "about 4.2M unique" or "roughly the top trending items" is good enough.

score update -> DB (truth) + ZADD to segment ZSET (O(log n))
top-K:  ZREVRANGE segment 0 k          (O(log n + k))
my rank: ZREVRANK segment player       (O(log n))
global:  merge top-N of each shard ZSET
hot counter: INCR counter:rand(0..N) ; read = SUM(counter:0..N-1)
unique count: HyperLogLog ; trending top-K: Count-Min Sketch

Durability matters: Redis is the fast serving/index layer, not the system of record. Persist authoritative scores in a database and treat the ZSET as a rebuildable index (write-behind, or rebuild from an event stream), so a Redis loss is a rebuild, not data loss.

Recap: use a Redis sorted set for O(log n) updates and top-K/rank reads instead of SQL sort-per-request, shard the ZSET by segment with a merged global top-N, break hot counters into summed sub-counters for write parallelism, reach for HyperLogLog and Count-Min Sketch when approximate is good enough, and keep authoritative scores in a database with Redis as a rebuildable index.