Design top-K and leaderboards

"Top 100 songs this hour", "trending hashtags", "your rank among 50 million players". All of these ask for the biggest few out of a huge, fast-changing set. With a few thousand items you sort a table; with hundreds of millions of events an hour you need sharded counting, time buckets and sometimes a sketch that trades a little accuracy for a thousand times less memory. It follows the interview framework phase by phase.

1. The prompt

Two related interview questions, often asked as one: "Design a real-time game leaderboard" (exact ranks for every player) and "Design top-K most played songs or trending items" (the top few out of billions of events, per time window).

They share the word "top" but not the solution: a leaderboard is a sorted index you can ask "where am I?", while top-K is a counting problem over a stream. Say which you're designing, or cover both in turn.

2. Frame the problem

3. What it must do

1. Leaderboard: update a player's score; show the top 100 and any player's exact rank and neighbours.
2. Top-K: the top 100 items for the last minute, hour and day, globally and per region.

Not now:

• Anti-cheat (mention it).
• Recommendation (a different problem).

4. How well it must do it

5. Numbers that change the design

6. The nouns

• Score: a player's current total.
• Play event: one play of one item, with a time.
• Bucket: counts per item for one minute.
• Chart: a precomputed top-K list for a window and region.

scores     (game_id, player_id) → score, reached_at           (database: the source of truth)
lb:{game}  Redis sorted set: member player_id, score            (rebuilt from scores)
play       item_id, user_id, region, played_at                  (event stream, partitioned by item_id)
buckets    (shard, minute) → item_id → count
charts     (window, region) → [(item_id, count) × 100]           (cache)

7. The contract

POST /v1/games/{g}/scores {delta}           → ZINCRBY lb:{g} delta player   (player from the session)
GET  /v1/games/{g}/top?n=100                → ZREVRANGE lb:{g} 0 99 WITHSCORES
GET  /v1/games/{g}/rank/{player}            → ZREVRANK lb:{g} player  (+ ZREVRANGE around it for neighbours)
GET  /v1/charts/top?window=1h&region=IN&n=100  → precomputed list from cache

Data flow: leaderboard: (1) score update → (2) database + sorted set → (3) reads go to replicas. Top-K: (1) play events into a stream partitioned by item → (2) counter shards keep minute buckets → (3) each shard reports its local top K → (4) a merger combines them every few seconds → (5) charts cached for readers.

8. First working version

One database table of scores and one table of play events, queried directly.

8.1 "What's my rank?"

8.2 Top songs this hour

SELECT item_id, COUNT(*) FROM plays WHERE played_at > now() - 1h GROUP BY item_id ORDER BY 2 DESC LIMIT 100, on every request.

9. Make it hold up

9.1 Exact leaderboards with sorted sets speed · exact

9.2 Beyond one node scale

Most "leaderboards" are naturally many small ones: split by game, region or season, and each is its own sorted set. For one giant global board, shard by score range and keep a count per shard, so a rank is "players in higher shards + rank inside my shard". Ties are broken consistently (earliest to reach the score, folded into the stored score) so ranks don't flicker.

9.3 Top-K over a stream fresh · scale

• Shard by item id: every play of song 4200 goes to the same counter shard (partition the event stream by item id). Each shard keeps exact counts for its items and its local top K.
• Merge: because each item lives on exactly one shard, the global top K is the top K of all the shards' local top-K lists combined. That is exact, and the merge is tiny.
• Serve from cache: recompute the lists every few seconds and cache them; readers never touch the counters.

9.4 Sliding windows with buckets fresh

Keep counts in one-minute buckets. "Last hour" = sum of the last 60 buckets; slide by adding the newest minute and subtracting the one that fell out. Hour and day buckets roll up from minutes, so "last day" sums 24 hour buckets instead of 1,440 minute ones. Old buckets are dropped; the raw stream is kept elsewhere if anyone needs to recount.

9.5 When memory is the limit: Count-Min Sketch scale · cost

A Count-Min Sketch is a small grid of counters: d rows, each with its own hash function, w columns wide. To count an item, add 1 to one cell per row; to estimate it, take the minimum of its cells. Collisions only ever add, so the estimate is never too low, and a wider grid means fewer collisions. Keep a small heap of the K items with the highest estimates, and you have approximate top-K in kilobytes instead of a counter for every item. Redis Open Source includes Count-Min Sketch and Top-K data structures.

Use it where small errors are fine (trending, analytics). For anything paid out (game prizes, royalties), use exact counts, or use the sketch only to pick candidates and count those exactly. Race the two in section 13.

9.6 Hot items scale

One viral item on one shard can overload it. Pre-aggregate on the producer side (count locally for a second, send one increment of +350 instead of 350 increments), or split the key as in Design D17 and add the parts during the merge.

9.7 The whole design after the deep dives

A score update and a chart refresh through the final design. Press Play or drag the timeline.

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Exact vs approximate: exact counting needs memory per distinct item; sketches need fixed memory and give one-sided errors.
• Freshness vs cost: recomputing top-K every second is costly; every 10–60 seconds is usually enough for charts.
• Sorted set in memory, database as the truth.
• Shard by item so the merge stays exact.

What we'd watch:

• Rank read p99.
• Chart age.
• Consumer lag per shard.
• Sketch error vs an exact sample.
• Hot keys.

At 10×:

• More counter shards.
• Producer pre-aggregation by default.
• Sketches for long-tail windows.
• Score-range sharding for giant boards.

Common mistakes:

• COUNT(*) for ranks.
• Sharding counts randomly, then merging local top-Ks (inexact).
• One counter reset hourly.
• Sketches for prize money.
• No source of truth behind the cache.

13. Try it, check yourself, read more

60,000 plays of 5,000 songs, where a few songs are hugely popular (a Zipf distribution, like real charts). Watch the top 10 race with exact counts on the left and a Count-Min Sketch with 4 rows on the right. Red bars are songs the sketch wrongly ranks in the top 10.