Top-K & leaderboards

Every part, and why it is there

Players

Millions of players post scores and check where they rank. They also see a “trending now” list of the most-played levels.

API gateway

Authenticates players and routes score writes and leaderboard reads to separate services.

Score service

Validates a score (anti-cheat checks), stores it, updates the leaderboard and emits an event. One write fans out to three places.

Score history

The durable record of every score, so a leaderboard can be rebuilt if Redis is lost.

Leaderboard (sorted sets)

A sorted set keeps members ordered by score: adding a score and reading the top 100 or a player’s rank both take logarithmic time, even with millions of players.

Play events

Every play and score as an event, for anything that needs counts over time windows.

Leaderboard API

Answers “top 100”, “my rank” and “players around me” straight from the sorted set, and “trending” from precomputed snapshots.

Heavy-hitter counter

Counts plays per level with a count-min sketch (a tiny fixed-size table of counters) and a small heap of the current top K. Exact counts for every key would need far more memory.

Top-K snapshots

The trending list for each window (last hour, last day), rewritten every few seconds. Readers fetch a single small document.

Exact daily recount

Recounts the day exactly from the event stream into the warehouse, for reports where approximate is not good enough.

Warehouse

Exact historical counts for analysts and season-end prizes.

Asked in interviews at

• meta
• linkedin
• google
• microsoft
• amazon
• bloomberg
• monzo
• uber

Concepts used here

• HyperLogLog: Count 10 million different visitors in 12 KB, to within about 1%, without storing a single ID.
• Count-Min Sketch: Count 500 million hashtags a day in about half a megabyte. It may overcount a little, but it never undercounts.
• Segment tree: Build a tree of totals over a ramen shop’s daily sales, then answer any “days l to r” question and absorb any change in about 20 steps for a million days.
• Skip list: Keep a million-player leaderboard in score order and find any score in about 40 steps, using a linked list, some extra lanes and a coin.
• Fenwick tree: Running totals that stay fast while the numbers keep changing, in one plain array the same size as the data. The binary of each position does the work.

Learn more

• Top-K System Design Interview Breakdown w/ Ex-Meta Senior Manager (Hello Interview)
• System Design Interview - Top K Problem (Heavy Hitters) (System Design Interview)
• Data Structures for Big Data in Interviews - Bloom Filters, Count-Min Sketch, HyperLogLog (Hello Interview)
• Top-K (Hello Interview)
• Real-time gaming leaderboard (ByteByteGo)
• Redis sorted sets (Redis)