News aggregator (Google News)

01 · CONTEXT AND REQUIREMENTS

What a news aggregator does

A news aggregator gathers articles from thousands of publishers into a scrollable interface, for people who want to keep up with events. The example in this case is Google News, and the interview task it is based on describes the product this way.

The page lists three core requirements: see an aggregated feed of articles from thousands of publishers worldwide, scroll the feed “infinitely” and click an article to be redirected to the publisher's site, where the full content lives. It is a good starting point for the requirements gathering.

Personalizing the feed by interests is one of the items the page leaves out of the initial scope. Among the non-functional requirements, it prioritizes disponibilidade over consistency: users prefer to see slightly stale content to seeing no content at all.

02 · INGESTION

How articles arrive in the system

Before assembling any feed, the system needs to discover the articles. One documented discovery source is the news sitemap: Google's documentation for publishers says it is for the publisher to tell Google about its news articles and additional data about them.

The publisher should update the sitemap with new articles as it publishes them, and Google News crawls these sitemaps as often as it crawls the rest of the site.

The documentation asks that the sitemap include only URLs of articles created in the last two days. Each sitemap accepts up to 1,000 news:news tags; beyond that, the guidance is to split into smaller sitemaps.

The publication date provided should be the original one, from when the article came out on the publisher's site, not the time it was added to the sitemap.

1. The publisher maintains a news sitemap and updates it as it publishes.

2. The crawler checks the sitemap for new URLs. According to the documentation, Google News crawls these sitemaps as often as it crawls the rest of the site.

3. Each sitemap lists only recent articles and has an entry limit; beyond it, the guidance is to split into smaller sitemaps.

4. Each new URL becomes a message in the queue, and the crawler moves on to the next one.

5. The processor reads from the queue and extracts the title, text and publication date. The date must be the article's original one, not the time it entered the sitemap.

6. The result is written to the article store.

03 · DUPLICATES

Fingerprint deduplication

The paper “Detecting Near-Duplicates for Web Crawling,” presented at the WWW conference in 2007, deals with web documents, not specifically news. It separates two problems: exact duplicates are easy to identify with standard checksum techniques; the harder part is near-duplicates, identical in content but different in a small part of the document, such as ads, counters and timestamps.

The core technique is simhash, a fingerprint with the property that the fingerprints of near-duplicates differ in only a few bit positions. To compute it, the document becomes a set of features, each with a weight, and that set is reduced to a fixed-size fingerprint.

In the paper's experiment, for a repository of 8B pages, 64-bit fingerprints and k equal to 3 were considered reasonable. The criterion is to declare two documents near-duplicates when their fingerprints differ in at most 3 bits, and k equal to 3 is reasonable because precision and recall are close to 0.75.

The paper also reminds us that, in practice, the presence of a near-duplicate may not become a yes-or-no decision to eliminate pages; it can be one of a few scoring components.

1. The detector receives each newly processed article from the queue.

2. It converts the text into a set of weighted features and reduces that set to a fixed-size fingerprint. The paper describes the step for web pages.

3. Then it queries the index: is there any known fingerprint that differs from this one in at most k bits?

4. The paper's method builds several tables kept in the main memory of a set of machines; the alternative of probing a sorted table with all possible variations requires a prohibitive number of lookups.

5. If it finds a similar fingerprint, the detector can group the article with the earlier one; if not, it writes a new article and adds the fingerprint to the index. The paper notes that, in practice, the presence of a near-duplicate can be just one scoring component.

There is yet another kind of similarity. The paper mentions the case of, given a news story, finding stories from other sources that report the same event, and says this notion of similarity is semantic, quite different from the notion of duplicates and near-duplicates.

04 · FEED READ

Serving the feed quickly and with high availability

Serving the feed is the read path. Among the deep-dive questions the page raises are pagination, latency, article freshness, media handling and traffic spikes during breaking news. The table summarizes each one.

1. The reader opens the app; the feed request goes through the edge and reaches the feed API.

2. The API first queries the feed cache, which stores already-assembled pages.

3. If the cache does not have the page, the API assembles the feed from the article store and fills the cache.

4. When the cache offers a slightly old version of the feed, the design accepts serving it: the page prefers slightly stale content to no content.

5. As the user scrolls the list, the app asks the API for the next page, which repeats the path.

6. When clicking an article, the reader is redirected to the publisher's site to read the full content.

05 · LIMITS AND EXTENSIONS

What the public source does not cover

The page lists two bonus deep dives: supporting feeds by category, such as sports, politics and technology, and generating personalized feeds based on each person's reading behavior and preferences.

The public part of the page shows the requirements and the deep-dive questions, but stops before the final design: the text asks for a subscription to continue reading. For that reason, this case provides no capacity numbers or an architecture attributed to the real product.