Web crawler and newsfeed

A web crawler gathers pages from the open web, mainly to feed a search index. A newsfeed chooses, from everything your connections produced, the few items worth showing you now. The first is a throughput and politeness problem. The second is a selection and ranking problem.

Starting from seed URLs, fetch pages, extract links, and follow them, storing page content for later processing. It must scale to billions of pages, be polite (never overload a website), avoid fetching the same page twice, handle bad or malicious pages, and recrawl pages to keep them fresh.

Assume 1 billion pages a month. That is about 385 pages per second (1B / 2.6M seconds). At about 100 KB per page, that is 100 TB per month of raw content, and around 6 PB over five years. Compressing content and storing it in object storage keeps this affordable.

The crawler is a loop around a few parts.

1. Seed URLs start the process.
2. The URL frontier is the queue of URLs waiting to be fetched.
3. Fetchers download pages, using a DNS resolver with a cache, since a DNS lookup per page would be a bottleneck.
4. A parser extracts text and links.
5. A duplicate content check drops pages already seen under another URL, by comparing a hash or a similarity fingerprint of the content.
6. Extracted links pass through URL filters (allowed types, blocked sites, normalization) and a URL-seen test, and only new URLs go back into the frontier.
7. Content goes to storage, and an indexer reads it later.

Checking whether a URL was already visited must be very fast, because it happens for every link of every page. Keeping every URL in a database lookup is too slow, and in memory too large. A Bloom filter is a compact structure that answers "have I seen this?" with either "definitely not" or "probably yes". It never gives a false "no", so it never makes us miss a new URL it has really not seen, and a small false-positive rate only means we occasionally skip a page.

For 1 billion URLs at a 1 percent false-positive rate, a Bloom filter needs about 9.6 bits per element, roughly 1.2 GB. That fits in memory on one machine, whereas the URLs themselves would take tens of gigabytes.

Fetching as fast as possible from one site can look like an attack. The frontier therefore enforces politeness: only one request at a time per host, with a delay between requests. The standard design has one queue per host, a mapping that sends each host's queue to a particular worker, and a delay timer. Fetchers read and honor each site's robots.txt, caching it per host.

Not all URLs are equal. A priority layer ranks URLs by importance, such as how many pages link to them, so valuable pages are fetched first and frequently changing pages are recrawled more often than static ones. Use breadth-first traversal in general, since depth-first can wander into one site forever.

• Spider traps: an endless calendar or dynamically generated links can produce infinite URLs. Limit depth and URL length, and cap pages per site.
• Normalization: treat different spellings of one URL as the same by lowercasing the host, removing fragments, and sorting parameters.
• Bad content: set time and size limits on downloads, handle encodings, and skip non-text types.
• Distribution: split the URL space across crawler nodes by hashing the host, using consistent hashing, so politeness for a site is handled by one node and adding nodes moves little.
• Resilience: save the frontier and the Bloom filter periodically so a crash resumes instead of restarting.

Show each user a ranked list of recent items from friends, pages and groups they follow, including text, photos and shares. Loading must be fast, and a feed must feel relevant, so it is not simply the newest first.

The earlier Instagram and Twitter lessons covered how to gather and store feed items using fan-out on write, on read, or a hybrid. This lesson focuses on what happens after: deciding what to show.

A typical pipeline has stages.

1. Candidate generation: gather perhaps a thousand recent items from the precomputed lists and the merge of high-volume sources.
2. Ranking: score each candidate for this user. Classic signals include affinity (how often you interact with the author), content weight (a video may count more than a plain link), and time decay (older items fall). Modern systems predict the probability of a like, comment or share with a trained model, then combine predictions into one score.
3. Filtering and diversification: remove items the user hid, blocked or already saw, apply privacy checks, and avoid ten posts in a row from one source.
4. Mixing other content, such as ads and suggested items, at set positions.
5. Return the top page.

Scoring a thousand items with a heavy model for every request is too slow, so systems use two stages: a cheap model prunes to a few hundred, then a richer model orders those.

• Pagination uses a cursor, such as the id or score of the last item seen, not an offset, because new items arriving would shift offsets and cause repeats or gaps.
• Caching: keep the ranked feed for active users for a short time, so scrolling and refreshing are cheap, and refresh in the background.
• Fresh updates: tell the app when new items exist, by a push notification, a long poll or a server sent event, instead of reloading blindly.
• Features and storage: the model needs fast access to features such as your recent interactions, held in a low-latency feature store.
• Failure: if ranking is slow or unavailable, fall back to a simpler chronological feed from the cache. An imperfect feed is better than none.

Both manage a huge, constantly changing set where doing everything for everyone is impossible, so each makes a cheap first pass (a Bloom filter, candidate generation) before an expensive second pass (fetching and parsing, deep ranking). Both depend on queues to smooth load, sharding by a key that fits access, and approximate, probabilistic structures where exactness is not worth the cost.