Design a News Aggregator like Google News: Feeds, Dedup, Story Clustering and Ranking

One article, from a publisher to a reader's screen

Follow a single article through the system. This is a good order to explain it in an interview.

1. 1

   Due

   The scheduler sees that the Technology feed of a news site is due. Its last check, 6 minutes ago, saved the feed's ETag, a version tag the server sent back.

2. 2

   Checked

   A fetcher for that host sends GET with If-None-Match and the saved ETag. The feed changed, so the server returns 200 with the new file. Had nothing changed, it would return 304 with no body.

3. 3

   Item found

   The fetcher reads one new item. It has a guid, the RSS item id, so the fetcher checks a fast 'seen ids' set. It is new. The fetcher checks robots.txt and fetches the full article page.

4. 4

   Logged

   The raw item and page go into the Kafka article log, keyed by host. The fetcher's work is done.

5. 5

   Cleaned and checked

   A worker strips menus and ads, detects English, and hashes the text: no exact match. Its SimHash differs from an article seen an hour ago in only 2 of 64 bits, so it is a reprint of a wire story. It is linked to the original and not shown on its own.

6. 6

   Clustered

   A second outlet's own article about the same event is not a copy. The clusterer finds a story from the last 48 hours that shares its people, places and key words, and adds it there. The story now has 12 publishers.

7. 7

   Ranked

   Within a minute the ranking job scores the story: high importance (12 publishers), high freshness (one hour old). It enters the US English Technology list and the US top-stories list in Redis.

8. 8

   Served

   A signed-in reader opens the app. The feed API reads both lists from memory, adds candidates from topics the reader follows, re-ranks about 500 stories with the reader's profile and returns the top 30. The story is near the top.

9. 9

   Learned from

   The reader taps the story. The click goes into the click log, and the profile job raises the weight of Technology for that reader.

These are the conversations the interviewer is steering you toward. Practice each one until you can talk through it without notes.

Ingestion: polling feeds, WebSub push and polite fetching

Most publishers offer a feed. RSS 2.0 and Atom are the two common formats. Both are small text files, written in a format called XML, that list the newest articles with a title, a link, a summary and a date. The simplest way to learn about new articles is to poll: download the feed on a timer and look for items not seen before. Polling 200,000 feeds every 5 minutes is about 670 requests a second, so each request must be cheap. HTTP conditional requests make it cheap. On each visit, save the ETag (a version tag) and the Last-Modified time the server sent. Next time, send them back in If-None-Match and If-Modified-Since. If nothing changed, the server answers 304 Not Modified, and by the HTTP standard a 304 carries no body. Next, choose the poll interval per feed. A wire service's main feed may change every minute; a small blog's changes once a week. A simple rule works well: halve the interval when a check finds new items, grow it by half when it finds none, and keep it between 2 minutes and 1 hour. RSS also lets a publisher give hints. The ttl element is the number of minutes a feed may be cached before it is checked again, and skipHours and skipDays name times an aggregator can skip. Push is the alternative. WebSub is a W3C Recommendation (W3C is the body that writes web standards). A feed names a hub; we send the hub a subscription request with our callback URL. The hub checks that we really asked by sending a random challenge string, which we must echo back. After that, when the publisher tells the hub about new content, the hub POSTs it to our callback. We can give a secret, and the hub then signs each delivery with an HMAC (a keyed hash) in the X-Hub-Signature header, so we can reject fakes. Subscriptions expire after the lease, so we must renew them. Push is fast, but a lost push is silent, so keep a slow poll running behind every subscription. Finally, politeness. Feeds often hold only a summary, so the fetcher downloads the article page too. Before fetching any page on a host, it reads that host's robots.txt. RFC 9309 says a crawler should not use a cached copy for more than 24 hours. If robots.txt returns a 4xx error (a client error such as 404 Not Found), the crawler may fetch anything; if it returns a 5xx error (the server itself failed), the crawler must assume it may fetch nothing. Put all requests for one host in one queue, so the limit per host holds however many workers you run. Google's crawlers apply a crawl capacity limit per site: when a site slows down or answers with 5xx or 429 (too many requests), the limit goes down. Retry a failed fetch after a wait that doubles each time (exponential backoff), and stop after a few tries, so a broken site never gets a storm of retries from us. The web crawler walkthrough on this site covers the URL frontier and politeness queues in more depth; a news aggregator needs a much smaller version of it, because it knows its sources in advance.

MIN_S, MAX_S = 120, 3600  # 2 minutes to 1 hour

def next_interval(current_s, new_items, ttl_min=None):
    if new_items > 0:
        nxt = current_s / 2    # busy feed: come back sooner
    else:
        nxt = current_s * 1.5  # nothing new: back off
    if ttl_min:                # RSS <ttl>: cache this long
        nxt = max(nxt, ttl_min * 60)
    return int(min(MAX_S, max(MIN_S, nxt)))

print(next_interval(600, 3))      # 300
print(next_interval(600, 0))      # 900
print(next_interval(600, 3, 60))  # 3600

Giving each article one identity

Before you can find copies, you need to know when two items are the very same article. That is harder than it looks. In RSS 2.0 every element of an item is optional, including the guid, the item's unique id. When a guid is present, the spec says an aggregator may use it to decide whether an item is new. Atom is stricter: every entry must have exactly one id, a permanent and unique identifier. So the rule is: use the guid or Atom id when there is one, and fall back to the article URL. URLs need cleaning first. Remove tracking parameters such as utm_source, lower-case the host, drop the fragment after #, and follow the page's canonical link (a tag in the page that names the preferred URL). The article_id is then a hash of that canonical URL. Using it as the database key makes every write safe to repeat. Kafka can deliver a message twice after a crash, and writing a row twice changes nothing. To make the first check fast, keep the ids seen in the last few days in a set in memory, or in a Bloom filter, a compact structure that answers 'definitely new' or 'probably seen' using a few bits per item. A 'probably seen' answer is then confirmed in the database. Timestamps need care too. The publisher's published date can be missing, wrong, or in another time zone, and some sites re-date old articles. Store it, but rank on first_seen_at, the time this system first saw the article, which you control.

Near-duplicate detection with SimHash

News is full of near-copies. A wire service sends one story to hundreds of sites, and each site prints it with its own headline, a dateline, or a line at the end. An exact hash of the text sees these as different. We need a fingerprint where similar texts get similar fingerprints. Two classic tools do this. Broder's shingling (1997) cuts a document into shingles, runs of a few words in a row, and measures how much two documents' shingle sets overlap; MinHash estimates that overlap from small samples. Charikar's SimHash (2002) builds a short fingerprint where the number of differing bits tracks how different two documents are. Google engineers tested SimHash for finding near-duplicate pages during web crawling. Manku, Jain and Das Sarma (WWW 2007) concluded that for 8 billion web pages, 64-bit fingerprints with a limit of k = 3 differing bits are reasonable. The method is short. Split the text into features (here, 3-word shingles). Hash each feature to 64 bits. Keep 64 counters. For each feature, add 1 to counter i if bit i of its hash is 1, and subtract 1 if it is 0. At the end, bit i of the fingerprint is 1 if counter i is positive. Small edits change only a few features, so only a few counters cross zero. The code below shows it. A dateline added to a 62-word story changed 3 bits; a different story changed 33. Finding matches among 30 million fingerprints needs one more idea. If two 64-bit fingerprints differ in at most 3 bits, then after cutting them into 4 blocks of 16 bits, at least one block is identical in both, because 3 differences can touch at most 3 blocks. So file each fingerprint under 4 keys, one per block. A new article looks up its 4 blocks, gets a few hundred candidates per block, and compares each one in full: an XOR (a bit operation that marks every bit where two numbers differ) and a count of the marked bits. The 2007 paper builds its sorted, permuted tables on this idea. One warning matters in an interview. The 3-bit limit was tuned on long web pages. News articles are shorter, and in the test below one changed word gave 4 bits. Tune the limit on labelled pairs of your own articles, and for short texts consider a smaller shingle size or MinHash.

import hashlib

def simhash(text, bits=64):
    w = text.lower().split()
    sh = [" ".join(w[i:i+3]) for i in range(len(w)-2)]
    v = [0] * bits
    for s in sh:
        d = hashlib.md5(s.encode()).digest()
        h = int.from_bytes(d[:8], "big")
        for i in range(bits):
            v[i] += 1 if (h >> i) & 1 else -1
    return sum(1 << i for i in range(bits) if v[i] > 0)

def distance(a, b):
    return bin(a ^ b).count("1")  # differing bits

# copy = "WASHINGTON " + wire
# distance(simhash(wire), simhash(copy))  -> 3
# distance(simhash(wire), simhash(other)) -> 33

Story clustering: grouping different articles about one event

After copies are gone, many different articles about one event remain: five newspapers each write their own report on one storm. They share few sentences, so SimHash calls them different, and they are. Readers still want to see one story with five sources, so the next step is clustering: putting articles about one event in one group. Do it as each article arrives, so new stories show up fast. First, describe the article. Pull out named entities (people, places, organisations) and weight the other words with TF-IDF, a score that is high for words common in this article and rare across all articles. An embedding can be used as well: a list of numbers, made by a language model, that captures what a text means. Second, find candidates. Keep an inverted index, a lookup table from each entity or key word to the stories that contain it, covering only stories active in the last 48 hours. Looking up the new article's entities returns a handful of candidate stories, so you never compare it with everything. Third, decide. Measure cosine similarity (how closely two word-weight lists point the same way, from 0 to 1) between the article and each candidate's average. If the best score is above a threshold, join that story. If not, start a new one. Pick the threshold from pairs of articles that people have labelled. Online clustering makes mistakes in both directions. Two stories about one event can start apart and should later merge, and a story can grow so wide that it should split. Run a slower job every few minutes that re-clusters the last day of articles and fixes this. When two stories merge, keep the old id as a pointer to the new one, so cached lists and shared links never break. Watch for a race. Two workers can receive two articles about a brand-new event within one second, find no story, and each start one. Route articles by their main entity to one worker partition so they meet, and let the merge job catch the rest. Each story also needs a lead article, the one shown on top. Good signals are the first or most original report and the publisher's authority. Count publishers, not articles, so one site posting five updates does not look like five sources.

Categorization, language and region

Each story needs sections (World, Business, Technology and so on), a language and a region, because the front page is built per edition, which is a region plus a language. Start with the cheap hints. A publisher often has one feed per section, so an article from its technology feed is probably technology. RSS items can also carry category elements chosen by the publisher. Hints are noisy, so add a text classifier trained on labelled articles, and allow more than one section, because a story about a chip maker's results belongs in Business and in Technology. Detect the language from the text itself, not from the site, because many sites publish in more than one language. Region comes from the publisher's location and from the places named in the article; a local story belongs on local pages even when a national paper wrote it. A story takes the sections and region most of its articles agree on. Google's own help pages list location and language among the factors that rank Google News, next to relevance, prominence, authoritativeness, freshness and usability.

Ranking: freshness against importance

Two forces pull against each other. A story loses value every hour, so freshness must count. But the newest article is often a small one, and a major story from this morning should still beat it. So the score multiplies a strength by a freshness factor. Freshness as a half-life is easy to explain and tune: the factor halves every 6 hours, so it is 0.5 after 6 hours and 0.25 after 12. Strength comes from signals you can count. The number of different publishers covering the story is a strong one, because editors around the world have voted with their own articles. Use its logarithm, so going from 1 to 10 publishers counts as much as going from 10 to 100. Add the authority of the sources, the story's velocity (how fast new articles are joining) and, for a reader, how well the story matches their topics. Figure 5 shows a property that surprises people. When both stories decay at one rate, their order never changes after both exist. A new story beats an older one only if its strength is higher than the older one's strength, halved once for every 6 hours between them. So the strength must keep updating as publishers join: a story picked up by 30 more outlets has to be able to climb. Source quality matters as much as volume: a network of copycat sites or a content farm should add little, so keep a per-publisher authority score and a block list. Two more rules keep the list useful. Limit how many stories from one publisher appear near the top. And keep a small slot for stories that are fresh but not yet proven, so new events can be discovered before they have many publishers. Every weight here is a starting guess. Google's 2007 paper chose its weights by running live experiments and comparing clicks, and that is how you should tune them too.

import math

HALF_LIFE_H = 6.0  # a first guess; tune with live tests

def story_score(publishers, age_h, topic_match=0.0):
    strength = 1 + math.log1p(publishers) + 2 * topic_match
    freshness = 0.5 ** (age_h / HALF_LIFE_H)
    return strength * freshness

print(round(story_score(40, 6), 2))      # 2.36
print(round(story_score(4, 0), 2))       # 2.61
print(round(story_score(4, 0, 1.0), 2))  # 4.61

Personal feed vs global feed: fan-out and when to compute

Fan-out means sending one thing to many places. A social network usually fans out on write: when you post, your post is copied into the feed of each follower, so reading a feed is a quick lookup. The Meta news feed walkthrough on this site explains that design and its limits. Copy it onto news and the numbers break. Assume 200,000 stories a day (1 million articles, about 5 per story) and say 1 reader in 10 is interested in an average story. That is 200,000 x 10,000,000 = 2 trillion inbox writes a day, mostly for readers who will never open the app before the story is old. Precomputing each reader's whole feed on a timer is not much better: 100 million readers every 15 minutes is 111,111 feed builds a second, 6.4 times the busiest page-view rate. News has a different shape from a social feed. Each person follows different people, but every reader in an edition draws from the same few thousand fresh stories. So compute the shared part once and the personal part on read. The ranking job writes one list per edition and section once a minute. On each page view, the feed API takes a few hundred candidates from the lists that matter to this reader (their edition's top stories, the sections and topics they follow), drops sources they hid and stories they read, and re-ranks the rest with their profile. That is about 500 small score calculations per page view, done only for readers who show up. Google's 2007 paper describes this split. The news front end could supply the candidate stories, chosen by edition, language and freshness, and the recommender scored them within a few hundred milliseconds. The profile itself is updated in the background from clicks, with counts that decay over time so recent interest counts more. A new reader with no clicks yet gets the edition's top stories plus any topics they pick at sign-up, and the profile fills in as they read. One precompute is still worth it: a small 'For you' candidate list per heavy reader, refreshed when they click, so the read path has less to gather.

Caching top stories per region and section

The front page for one edition is the same for every signed-out reader there, and it is the most-read thing in the system. Cache it in layers. The ranking job writes each list whole, as one Redis value under a key such as top:us:tech. Each feed API server copies every list into its own memory and refreshes them every few seconds. All 500 lists together are under 1 MB, so this costs nothing. Signed-out pages can also be cached by a CDN for a few seconds, so most of those requests never reach our servers. This layout avoids two classic failures. The first is a cache stampede: a popular key expires, and thousands of requests miss at once and all try to rebuild it, overloading the database. Here no reader request ever rebuilds a list. A timer does, and if the ranking job fails, readers keep getting the last good list, a minute or ten minutes old, which is far better than an error. The second is a hot key: the US front page is read by everyone, and a single Redis machine holding it could be overwhelmed. Because every API server holds its own copy, that key is read from local memory, not from one Redis node. For signed-in readers, cache the parts that are shared (lists, story details) and compute only the final re-ranking per request. When an editor or a legal request must remove a story at once, publish a removal event that every server applies to its copy right away, without waiting for the next refresh.

Breaking news, bursts and failure modes

The hard minutes are the ones when something big happens. Hundreds of publishers post within minutes, feeds change on every check, and readers arrive at the same moment. Several things protect the system. The article log absorbs the burst on the write side: fetchers keep writing, and workers catch up a few minutes later without losing anything. Watch the lag, the number of messages written but not yet processed, and add workers when it grows. One story becomes very hot in the clusterer, because every new article matches it. Make the join step a cheap append, and update the story's counts in small batches, so one busy story does not become a lock that everything waits on. Back-pressure, slowing down the producer when the consumer is behind, should apply per host on the fetch side: a publisher whose site is struggling under its own readers should get fewer requests from us, never more. On the read side, the shared lists and their copies in memory carry the load, and the CDN absorbs signed-out readers. Other failures to name: a publisher's feed breaks or changes format (alert when a big feed stops producing items, and keep serving its old articles); a WebSub lease expires unnoticed (the safety poll covers it); a bad clustering threshold merges two unrelated events (the background re-clustering job and a split tool for editors fix it); and the ranking job crashes (readers see slightly old lists, and an alert fires when the lists' built_at time gets too old). The Back Pressure lesson in the course explains how a slow consumer can push back on a fast producer step by step.

How a News Aggregator actually does it

One of the few detailed public descriptions of a large news aggregator's personalization is Google's 2007 paper by Das, Datar, Garg and Rajaram. At the time Google News had several million unique visitors over a few days and several million stories, where a story is a cluster of news articles. Three methods scored each candidate story: MinHash clustering of users by the stories they clicked, PLSI (a probability model of user interests), and covisitation, which counts two stories clicked by one user within a few hours. Scores were added with weights chosen by live experiments. The candidates could come from the news front end, based on the edition, the reader's language and story freshness. Pages were generated within a second, which left the recommender a few hundred milliseconds, and its counts were time-decayed so recent clicks weighed more. In a test over 5 to 6 months, both weighted mixes got 38% more clicks on average than ranking by popularity alone. For near-duplicates, Manku, Jain and Das Sarma at Google showed in 2007 that Charikar's SimHash, with 64-bit fingerprints and up to 3 differing bits, is reasonable for a store of 8 billion web pages, and showed how to keep those fingerprints in permuted, sorted tables so each lookup is fast. Broder's 1997 paper on resemblance and shingles is the root of the MinHash family. On the ingestion side, the standards are public: RSS 2.0 (every item element optional, a ttl hint in minutes), Atom (RFC 4287, exactly one permanent id per entry), WebSub (a W3C Recommendation with publisher, hub and subscriber roles, leases and signed deliveries), HTTP conditional requests and 304 Not Modified (RFC 9110), and robots.txt (RFC 9309, cache at most 24 hours, a 5xx means fetch nothing). Google's crawling docs describe the politeness rule this page uses: crawl less when a site slows down or returns 5xx or 429. Google's help pages say Google News ranking is done by algorithms using relevance, prominence, authoritativeness, freshness, usability, and location and language, with some sections personalized.

Frequently asked questions