How to design a top songs widget
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
- The problem
- Clarifying questions
- The requirements menu
- Non-functional requirements
- Estimates
- Core entities
- The API
- The high-level design
- What breaks first
- The deep dives
- Entity fields
- Counting 700,000 plays a second
- Windows and fast reads
- Exact or approximate
- Variants
- What each level is expected to show
- The 30-second answer
- Quiz
The problem
The top songs widget lists the K most played songs for the last hour, the last day, the last month and all time, with K up to 1,000. About 700,000 plays a second arrive and a play has to show in the charts within a minute, so the design turns on where the counting happens: a stream processor adds up each song's plays in each window before anything reaches a database, and a job writes the finished list for each window into a cache, so a read is one lookup rather than a sort over billions of rows.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
How many plays arrive, and over how many songs? | The write rate decides whether plays can be counted one by one in a database or have to be added up in a stream first, and the song count decides whether exact counters fit in memory. | About 70 billion plays a day, about 700,000 a second, spread over roughly 3.6 billion songs with about 1 million new ones a day. The interviewer's figures borrow YouTube Shorts scale as a stand-in for Spotify. |
Which windows, and does the last hour slide or sit on the clock? | A clock-aligned hour is one tumbling window per hour. A sliding hour refreshed each minute needs per-minute buckets and far more state, so the choice shapes the stream job. | Last hour, last day, last month and all time, each ending now. Clock-aligned windows are acceptable at first; a sliding hour is a likely follow-up, so leave room for it. |
Do the counts have to be exact? | Exact counts for billions of songs mean a large keyed store; an approximate sketch fits in memory but overstates some songs, which matters near the cutoff of the list. | Exact counts first. Approximate counts are allowed later, for the month and all-time windows, when the interviewer says so. |
How fresh must the charts be, and how fast must a read answer? | Freshness bounds how long the stream job may hold a count before flushing it, and read latency rules out computing the list on request. | A play counts within 1 minute, and a request answers in tens of milliseconds. |
What is the largest K, and do we page through the list? | A fixed small K lets you precompute and cache the whole list; paging or an unbounded K would push you toward querying the store on each read. | K is at most 1,000 and the API returns the whole list, so no pagination. |
Do we need charts per user, per country, or over arbitrary ranges? | Each extra dimension multiplies the number of lists to keep, and arbitrary ranges rule out precomputing them. | No. Arbitrary time ranges, windows that end anywhere but now, and per-user or per-country charts are out of scope. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
A play shows up in the counts within 1 minute | The stream job may hold a count for well under a minute before flushing, the lateness allowance for out-of-order plays has to fit inside that budget, and the job that refreshes the cached lists has to run at least that often. |
Answers in tens of milliseconds | A read can't sort counts or scan a table. The top K for each window is computed ahead of time and served from a cache as one key. |
Exact counts first; approximate only when the interviewer allows it | The main design keeps a real counter per song per window, sharded by song id, which is about 64 GB for all-time counts. A count-min sketch is an addition you bring in when told rough counts are fine, not the default. |
About 700,000 plays a second at YouTube Shorts scale (Hello Interview) | With a node taking roughly 10,000 writes per second, one write per play means about 70 shards, so plays have to be summed in the stream and written in batches. This figure decides the shape of the write path. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Shards if each play is one database write | 700,000 plays a second ÷ 10,000 writes a node a second = 70 | About 70 shards | The counter store with no batching, and the reason to aggregate in the stream first. |
Writes a second after batching in the stream | 5 to 10 shards × 10,000 writes a node = 50,000 to 100,000 writes a second; 700,000 ÷ 100,000 = 7, 700,000 ÷ 50,000 = 14 | A cut of about 7 to 14 times, down to 5 to 10 shards | The counter store once the stream job has summed each song's plays in a window before writing. |
Plays that pass through the job in one minute | 700,000 plays a second × 60 seconds = 42 million plays processed a minute | About 42 million plays a minute | The input a one-minute flush interval has to absorb; the job keeps one running sum per song seen, not these plays, and the write count is the number of distinct songs played in that minute, not 42 million. |
Minute buckets a sliding window needs | An hour is 60 minutes; a month is 30 × 24 × 60 = 43,200 minutes | 60 buckets for a sliding hour, 43,200 for a sliding month | The state multiplier of a sliding window with a one-minute slide, and why you slide the hour but not the month. |
Lateness allowance inside the freshness target | 1 minute = 60 seconds; hold windows open roughly 30 seconds so late plays can land, leaving roughly 30 seconds to flush and refresh the cache | About 30 seconds of allowed lateness | The allowed lateness in the stream job, set alongside the watermark delay: long enough for most late plays, short enough to meet the 1 minute target. |
Size of one cached top K list | 1,000 entries × (8-byte song id + 8-byte count) = 16,000 bytes, about 16 KB; four windows = 64 KB | About 16 KB a list, 64 KB for all four | The cache and the response body: small enough to hold as one key per window and return whole. |
Memory of a count-min sketch | Error ε = 5 × 10^-7 of plays seen, failure probability δ = 0.01: width w = ⌈e ÷ ε⌉ ≈ 5.4 million columns, depth d = ⌈ln(1 ÷ δ)⌉ = 5 rows; 5.4 million × 5 × 8-byte counters ≈ 217 MB; 64 GB ÷ 217 MB ≈ 300 | About 217 MB, roughly 300 times smaller than 64 GB of exact counters | The approximate counter for the month and all-time windows, and the saving over the roughly 64 GB that exact counts for about 4 billion ids would take. |
How far the sketch can overstate a song | Bound is ε × plays seen, with probability 1 − δ = 99%: month = 70 billion × 30 days = 2.1 trillion plays, × 5 × 10^-7 = 1.05 million; 10 years = 70 billion × 3,650 days = 255 trillion plays, × 5 × 10^-7 ≈ 128 million | Up to about 1.05 million extra plays on a monthly count, about 128 million on a ten-year count | The accuracy you give up near the bottom of the list, and why the all-time sketch needs a wider table or a coarser promise. |
Core entities
| Entity | What it holds |
|---|---|
Song | The thing being ranked. The charts need its id; title and artist come from the catalog service when the widget renders. |
Play event | One record per play, written to the stream and read by the counting job. It is the unit the whole write path moves. |
Window | One count table per span: a song's total for one hour, one day, one month, or all time. |
Top K list | The finished chart for one window, written by the precompute job and read by the service. The one thing a user request touches. |
The API
| Endpoint | Notes |
|---|---|
| One cache read keyed by window, then the list is cut to k. The service validates window against the four allowed values and caps k at 1,000. Return |
| The API appends to the stream and answers |
| Keying by song id puts all plays of one song on one partition, which lets the counting job keep each song's running sum on one task. It also means a hit song concentrates on one partition, which the counting section addresses. |
The high-level design
Step 1 of 4
Record plays and rank on read
Start with the two paths and nothing clever. The app reports a play to a play API, which adds one to that song's counter in a count store. The same app asks a top K service for the chart, and the service sorts the counts and returns the first K. This is correct for a small catalog and it shows the interviewer the shape: one write path, one read path, a store between them. At about 700,000 plays a second, each a write of its own, the count store would need about 70 shards, and a sort over about 3.6 billion rows on each read can't meet tens of milliseconds, so the next steps rework both paths.
What breaks first
The deep dives
Counting 700,000 plays a second. About 700,000 plays a second arrive, and each has to appear in the counts within a minute. Walk one play from the app to the count store: where is it summed, when is it written, and what happens to in-flight counts if the counting process dies?
Windows and fast reads. A request asks for the top 100 songs of the last hour and expects an answer in tens of milliseconds. Where does that list come from, how are the hour, day and month totals kept without scanning the table, and what does the user see if the work behind the list runs late?
Exact or approximate. Rough counts are now acceptable for the month and all-time charts, and an exact counter for each of roughly 3.6 billion songs takes a lot of memory. Which approximate structure do you use, which way does its error go, how much memory does it save, and where does it live?
Concepts this guide uses
Sources
- Wikipedia: Shard (database architecture)
- Wikipedia: Partial sorting
- Wikipedia: Count-min sketch
- Redis documentation source on GitHub: Redis sorted sets (redis-doc/docs/data-types/sorted-sets.md)
- Confluent Developer: Intro to Kafka Partitions
- Apache Flink documentation: Windows
- Apache Flink documentation: Streaming Analytics (event time, watermarks, lateness)
- Apache Flink blog: An Overview of End-to-End Exactly-Once Processing in Apache Flink
- Confluent Cloud for Apache Flink: Windowing Table-Valued Functions
- Confluent Developer: Exactly-Once Processing in Apache Flink
- PostgreSQL documentation: Indexes and ORDER BY