You are asked to design two distinct large-scale systems in a single system-design interview loop: a Facebook-like **search** product and a distributed **web crawler**. Treat each part independently — they share no infrastructure — but apply the same rigor to both: requirements, estimation, data model, the read/write path, scaling, and failure handling. A repeated failure mode on this loop is skipping the back-of-the-envelope math. When the interviewer says "the numbers are up to you," that is an invitation to estimate QPS, storage, bandwidth, and machine counts out loud — not permission to skip them. Pick reasonable numbers for a product at Facebook's scale and drive the estimation yourself. ### Constraints & Assumptions - **Part 1 (Search):** A Facebook-scale product searching across four verticals (people, pages, groups, posts). It serves interactive search, so queries must feel instant. Results must respect per-viewer privacy and stay reasonably fresh as content is created and edited. You decide the concrete QPS, latency target, corpus size, and machine count — and justify them. - **Part 2 (Crawler):** A fixed budget of roughly **10,000 machines**. The crawler runs continuously, must respect `robots.txt` and per-host politeness, deduplicate both URLs and page content, and you are expected to justify the machine split with capacity math (network throughput, storage, fetch rate). - Assume mature internal infrastructure is available: a durable log (e.g. Kafka), object storage, a distributed KV store, and a service mesh. You do not need to build these from scratch. ### Clarifying Questions to Ask - **Both:** What are the hard SLAs (p95/p99 latency for search; target pages/sec for the crawler) so I can size against them? - **Search:** Is autocomplete/typeahead in scope, or only full-query search? Is typo tolerance required? - **Search:** Do we return all four verticals in one blended ranked list, or in separate per-vertical sections? - **Search:** What is the freshness SLA — must a just-published post be searchable in seconds, or are minutes acceptable (and does that differ for posts vs. people/page/group metadata)? - **Crawler:** Is this a one-time bulk crawl or a continuous crawl with recrawl scheduling? What recrawl cadence is expected for high-churn sites? - **Crawler:** Are the 10,000 machines homogeneous, and roughly what NIC bandwidth and disk per machine should I assume? --- ### Part 1 — Social-network search Design a Facebook-like search product that lets a logged-in user search across **people, pages, groups, and posts**. The system must support low-latency queries, relevance ranking, personalization (results depend on *who* is searching), strict privacy enforcement, and near-real-time freshness for new and edited content. Walk through the indexing pipeline, the query-serving path, ranking, and — most importantly — how privacy is enforced without leaking unauthorized content through results. State your scale assumptions and size the fleet from them. ```hint Where to start Separate the **write path** (change-data-capture → indexing pipeline → inverted index) from the **read path** (parse → candidate retrieval → privacy filter → rank → blend verticals). Nail the data model of an index document before optimizing latency. ``` ```hint Index sharding Compare **document-id sharding** (scatter-gather, easy rebalancing, every query hits every shard) against **term sharding** (less fanout but hot shards for common terms). Which degrades more gracefully at this scale, and which lets a single slow shard cost you a few results instead of the whole query? ``` ```hint Privacy — the crux The audience of a document and the viewer's relationships both change constantly, so you cannot pre-bake every viewer's permissions into the index. Think "coarse filter at index time, authoritative check at query time." Then ask: besides the matching rows, what *else* could reveal the existence of content a viewer shouldn't see — snippets? result counts? cached fragments? ``` #### What This Part Should Cover - **Clean read/write separation** — an event-driven indexing pipeline (CDC → tokenize/enrich → inverted index, with a near-real-time segment for freshness) vs. a low-latency scatter-gather query path. - **A justified scale estimate** — corpus size, peak QPS, index footprint, shard count, and replication factor, with the fanout cost made explicit. - **A defensible privacy model** — reasons about *where* authorization lives, and closes the leak surfaces beyond the matching rows (snippets, result counts, viewer-agnostic caches). - **Two-stage ranking** — cheap candidate generation then learning-to-rank re-scoring, run only on the post-privacy-filter set, with sensible personalization features. ### Part 2 — Distributed web crawler Design a web-crawling platform that runs on roughly **10,000 machines**, discovers and fetches pages at scale, respects per-site crawl limits and `robots.txt`, deduplicates URLs and near-duplicate page content, and uses distributed caching where it helps. Crucially, **estimate the capacity** — fetch rate, bandwidth, daily storage — and use that math to justify how you allocate the 10,000 machines across roles (fetchers, parsers, frontier/scheduler, robots/DNS caches, dedup, storage). ```hint URL frontier & politeness The frontier must support priority, per-host delay, and dedup. A two-level queue is the classic shape: global priority queues pick *which host* to crawl next; per-host queues enforce a minimum delay between requests to *that host*. Partition by host so a single owner enforces politeness — consistent hashing maps host queues to scheduler nodes, and durable queues let ownership recover on node failure. ``` ```hint Deduplication layers You need several layers, not one: **URL canonicalization**, a **seen-URL set** (Bloom filter / KV set), an **exact content hash**, and **near-duplicate** detection (simhash / minhash). Ask what each layer catches that the others miss — e.g. what does simhash catch that SHA-256 cannot? ``` ```hint Capacity math — do not skip this This is exactly what candidates fail on, so do it out loud. From your own fetcher count and a sustainable per-fetcher rate, derive aggregate ingress, pages/sec, and daily storage. Then ask what actually gates the fetch rate: is it CPU, the NIC, or the per-host politeness limit — and which of those is binding for a polite crawler? ``` #### What This Part Should Cover - **A frontier design** that addresses priority, per-host politeness, dedup, and recovery of host-queue ownership on node failure. - **Layered dedup** — recognizes one mechanism is not enough and articulates what each layer (canonicalization, seen-URL, exact hash, simhash/minhash) catches that the others miss. - **Capacity math tied back to the 10,000-machine budget** — derives fetch rate, bandwidth, and storage, correctly identifies the binding constraint (politeness/bandwidth, not CPU), and lets the fetcher/parser/scheduler/cache split fall out of it. - **Where distributed caching helps** — robots rules, DNS, seen-URL fingerprints, and per-host backoff state, with the work each cache removes from the hot path. --- ### What a Strong Answer Covers These dimensions span both parts — the interviewer is watching for them regardless of which system you are on. - **Drives estimation unprompted** — states scale assumptions, then derives QPS/storage/bandwidth (and, for the crawler, the machine split) from them, rather than waiting to be asked. - **Failure handling & observability** — tail-latency control (hedging/timeouts) and graceful degradation for search; durable queues, idempotent work, retries/backoff/circuit-breakers for the crawler; and the *right* metrics for each (indexing lag, p99, privacy-drop rate vs. pages/sec, dup rate, queue age). - **Tradeoffs stated explicitly** — freshness vs. cost, politeness vs. throughput, Bloom-filter false positives, storing raw vs. canonical content, caching vs. privacy correctness. ### Follow-up Questions - **Search (Part 1):** A celebrity edits a privacy setting from public to friends-only. How do you ensure already-cached or already-indexed results stop surfacing that content, and how fast? - **Search (Part 1):** How would you implement personalized ranking (social-graph proximity, mutual friends) without making every query fan out to the social-graph service synchronously? - **Crawler (Part 2):** How do you avoid crawler traps (infinite calendar/pagination URLs, session-id explosions) and adversarial sites that try to waste your fetch budget? - **Crawler (Part 2):** A single popular host has millions of must-crawl URLs but a strict 1-request-per-second politeness limit. How do you keep that host from starving while keeping your fetchers busy?