System Design Problems
Design a Search Engine
A search engine indexes the entire web and returns relevant results in milliseconds. Google processes 8.5 billion searches daily across 100+ billion web pages, requiring inverted indices, relevance ranking (PageRank), and distributed query processing.
- Crawling ā Discover and download web pages continuously
- Indexing ā Build inverted indices mapping words to documents
- Ranking ā Score and order results by relevance
The core challenge is balancing index completeness (covering the entire web) with query speed (returning results in < 200ms) across billions of documents.
Requirements
Functional Requirements
- Users can search with keywords and get ranked results
- Results include title, snippet, URL, and metadata
- Support for operators (AND, OR, NOT, exact phrase)
- Autocomplete and spell correction
- Search in multiple languages
- Personalized results based on search history
Non-Functional Requirements
- Latency: Results in < 200ms (p99)
- Relevance: Top 10 results must be highly relevant
- Scale: 100 billion indexed pages, 100K QPS
- Freshness: New pages indexed within 1 hour
- Availability: 99.99%
Back-of-the-Envelope Estimation
Inverted Index
PageRank
High-Level Architecture
Query Processing
- Parse: Tokenize query, correct spelling, expand synonyms
- Planner: Determine which index shards to query (scatter-gather)
- Retrieve: Look up inverted index for each term
- Score: Compute TF-IDF + PageRank + personalization
- Rank: Sort by relevance score
- Rerank: Apply ML model for final ranking
- Return: Top 10 results with snippets
Practice Exercises
-
Algorithm: Implement an inverted index in code. What data structure maps terms to posting lists efficiently?
-
Scale: If the index has 100 billion documents and 1 billion unique terms, estimate the memory needed for the inverted index with 4-byte doc IDs and TF values.
-
Ranking: Design a ranking function that combines TF-IDF, PageRank, click-through rate, and freshness. How would you weight these signals?
-
Freshness: How would you update the inverted index when a page changes without rebuilding the entire index? Design an incremental update strategy.
What to Learn Next
-> Design Web Crawler Discovering and downloading web pages for indexing.
-> Design Search Autocomplete Trie-based typeahead suggestions.
-> Database Indexing B-tree and LSM-tree index structures.
-> Design Recommendation System ML-based ranking and personalization.
-> CDNs Serving search results from edge locations.
-> Databases Distributed storage for inverted indices.