Top-K and trending in a time window

01 · CONTEXT AND REQUIREMENTS

What it means to ask for the most viewed

Top-K is a classic system design problem, with many variants. This case follows the Hello Interview walkthrough, which uses YouTube views: a huge stream of events comes in, each identifying a video, and the query asks for the K most-viewed videos in the last hour, the last day, the last month, and all time.

The walkthrough distinguishes two types of window. In the sliding window, the last hour is the interval between the current instant minus one hour and the current instant. In the fixed (tumbling) window, it is the last full hour, which starts and ends on the hour boundaries. The walkthrough proposes using fixed windows, which are easier to handle than sliding ones.

The core requirements: query the Top-K with at most a thousand results; tolerate at most one minute of delay between the view and the count; deliver precise results, with no approximation; and respond in tens of milliseconds. That last demand rules out many solutions and leads to favoring precomputation.

02 · SCALE ESTIMATION

Why a single database can't handle it

As an order of magnitude, the guide cites 70 billion views per day for YouTube Shorts. Dividing by 100 thousand seconds per day, the math gives 700 thousand writes per second. The guide notes that modern RDBMSs can handle more than 10 thousand writes per second per node under the right circumstances, and concludes that the load is far beyond that.

For storage, the guide estimates a naive per-video counter: 4 billion videos, 8 bytes per ID and 8 bytes per counter add up to 64 GB. Whenever the views of all videos must be kept, at least 64 GB will be needed.

03 · FIRST VERSION

One consumer and one Postgres

The guide prefers to start from a system that works and optimize it, rather than starting from an optimal system and trying to make it work. It assumes there is a Kafka stream of view events, fed by another system (the one that shows videos to users), and that the topic is partitioned by video ID. A simple consumer reads the events and updates a Postgres database.

1. View events arrive at a topic partitioned by video ID, and a simple consumer reads them.

2. The consumer updates the video's counter in Postgres.

3. To query, the service takes the first K from the list, the count index, which is basically a list of videos sorted by views; the query can be very efficient.

4. The cost is in the write: each update also has to update the index, and the guide acknowledges that this is a lot of writes on a single Postgres instance.

To support windows, the table gains a timestamp column and there is now one row per video viewed at least once in each hour. The number of writes does not change, since it is still one write per event, but the number of stored rows explodes. The window query becomes far less efficient: scans are when the database has to read all the rows of a segment to serve the query, and the guide warns that some cannot be avoided.

04 · WRITE AND READ

Partition, aggregate, and precompute

The first lever is partitioning the database using the same scheme as the topic, so that each partition holds only a subset of the videos. To bring the database load down to about 10 thousand writes per second, the guide would need 70 instances. With the database partitioned, each partition must be queried and the results merged; by taking the Top-K from each partition, the guide says the global Top-K is mathematically guaranteed to be in the final list, and the cron job now makes one call per partition.

Many views fall on a few videos. So, instead of one write per view, the writes for each video are grouped and the batches are flushed to the database periodically. The guide uses Flink with a one-hour fixed window to aggregate the views for each video, and with a wait for late events of about thirty seconds, under a minute. Since Flink reads from Kafka, if a machine fails or goes down it returns to the checkpoint offset in the topic and resumes from there. The guide expects writes to drop by 2 to 100 times and the partitions to fall in the range of 5 to 10.

1. Flink reads the topic and sums the views for each video in a one-hour fixed window, waiting a little for late events.

2. Instead of one write per view, Flink flushes batches to the database periodically, and the database is partitioned: each partition holds a subset of the videos.

3. The precomputation job makes one call per partition and merges the results, and the global Top-K is guaranteed to be in the final list.

4. At fixed intervals, the job computes the Top-K for each window and warms the cache.

5. The Top-K service only reads from the cache and never queries the database.

6. If a Flink machine fails or goes down, it returns to the checkpoint offset in the topic and resumes from there.

On reads, a cache returns the answer immediately when the entry exists. The problem is expiration: suddenly a flood of requests hits the database. The alternative is the periodic job described above, which precomputes the Top-K for each window at fixed intervals; this way the service only reads from the cache and never queries the database. Retaining entries for a few hours covers the case where the job runs late, and the service can serve slightly stale data for a short time instead of nothing.

For the windows, the guide proposes keeping aggregates for each window, rather than aggregates over arbitrary time partitions, and the cron job only needs to read the Top-K directly from the index. The approach moves complexity from reads to writes: writes now go to 4 tables instead of 1.

05 · APPROXIMATING WITH A SKETCH

Count-Min Sketch and sorted list

If users accept some risk of imprecision, efficiency improves drastically, and the guide observes that the top videos probably differ by a large factor. The proposed structure is the Count-Min Sketch (CMS), which uses several hash functions to map items to a matrix of counters. It forgets the actual items but remembers how many times they were seen through the hash, and estimates counts with far less memory than the full hash table, on the order of hundreds of megabytes.

The CMS has no list operation: when adding, the item's ID is lost. That is why the guide pairs it with a sorted list or heap. When a view arrives, it is added to the CMS; right after, the item's count is estimated, which gives an upper bound on the number of views and a good approximation; the count is then added to the list, which is periodically truncated so as not to use excessive memory. To get the Top-K, take the first K items of the list. Since users never query beyond the top thousand, the all-time list can have a thousand entries. For fixed windows, it is enough to keep one sketch and one list for each queried window.

1. Each view read from the topic is added to the CMS, which updates the sketch.

2. Right after, the consumer estimates the item's count; the result is an upper bound on the item's views and a good approximation.

3. The item's count is added to a sorted list (a Redis sorted set), periodically truncated so as not to use excessive memory; in Redis, the sorted set is kept trimmed to a thousand entries.

4. To query, the service takes the first K items of the sorted list.

5. The risk is durability: the Redis approach brings this concern, and there is a risk of losing data if a view enters the sketch but is not updated in the sorted list.

The original CMS paper describes a new sublinear-space data structure. Each item is mapped to one cell in each row of the counter matrix, and the item's estimate is the minimum across those cells. The paper states that CM sketches never underestimate counts and, to find frequent items (those with multiplicity above a fraction of the total) in the model where all updates are positive, it updates the sketch, queries the estimate, and puts into a heap the item whose estimate passes the threshold, keeping the heap small by checking. Because of the one-sided error guarantee, every frequent item enters the output, but non-frequent items may be included.

06 · SLIDING WINDOWS AND LIMITS

Where the design strains

Sketch approaches work well in fixed windows, where items are only added to the sketch during the window, but fall short in sliding windows. Removing items from the sketch cannot be done with the Redis approach. In tables, the sliding window is even more complex than the fixed one: each minute, the one-hour window counter increases by the views that arrived in that minute and decreases by those that occurred sixty minutes earlier, and minute-granularity data must be kept for an entire month.