Durgesh Tiwari
Author
A Search Engine helps users quickly find the most relevant information from a very large collection of documents.
A scalable search engine mainly performs two types of work:
Indexing: Prepare documents before users search.
Querying: Find and rank relevant documents when a user searches.
The core idea is simple:
Do expensive document processing before the user searches so query-time work stays fast.
A Search Engine finds relevant information from a large collection of documents.
Depending on the product, documents may be:
Web pages
E-commerce products
PDFs
Internal company documents
Articles
Images or videos
The basic flow is:
User Query
↓
Search Engine
↓
Relevant Ranked DocumentsThe difficult part is not simply finding documents containing a word. The system must find the best documents quickly and at massive scale.
Feature | Database Search | Search Engine |
|---|---|---|
Basic Approach | Queries stored records directly | Uses a pre-built search index |
Large-Scale Search | Scanning billions of documents becomes expensive | Uses an inverted index for fast lookup |
Query-Time Work | More work happens when the query runs | Most expensive processing happens before queries arrive |
Example | Search through 10 billion documents for | Lookup posting lists for |
Performance at Large Scale | Can become slow for full-text search across huge datasets | Designed for fast retrieval across very large document collections |
Main Data Structure | Tables, rows, indexes depending on database | Inverted index |
Assume we are designing a large web search engine.
The system should support:
Keyword and multi-word search
Ranked results
Pagination
Fresh content
Autocomplete
Spell correction
Filters when required
The core requirement is:
Given a query,
return the most relevant documents.Matching documents is not enough.
If millions of pages contain the word java, the system must determine which pages should appear first.
Ranking may consider:
Text relevance
Document quality
Freshness
Link authority
Query intent
Language
Location
User context
The exact signals depend on the product.
Users normally receive only a small number of results at once.
Page 1 → Results 1–10
Page 2 → Results 11–20For large or frequently changing result sets, cursor-based pagination can be more stable than deep offset pagination.
New and updated documents should eventually become searchable.
For time-sensitive content such as news, the delay between publication and search availability should be small.
This requirement is called index freshness.
Important requirements include:
Low query latency
High availability
High read throughput
Horizontal scalability
Fault tolerance
Good relevance
Fresh indexing
A large search engine may need to support billions of documents, petabytes of index data, and very high query throughput.
No single server can handle that scale.
A successful search engine needs both:
Low Latency
+
Good RelevanceFast but irrelevant results are not useful, while excellent results that take several seconds are also a poor user experience.
A search engine is easier to design when we separate it into two major paths.
This prepares documents for future searches.
Crawling
↓
Parsing
↓
Document Processing
↓
Indexing
↓
Search Index
This serves user searches.
User Query
↓
Query Processing
↓
Search Index
↓
Candidate Retrieval
↓
Ranking
↓
Top ResultsThe indexing path can perform expensive processing in advance so the online path remains fast.
OFFLINE / INDEXING PATH
Seed URLs
↓
URL Frontier
↓
Distributed Crawlers
↓
Page Fetcher
↓
Parser
┌─────┴─────┐
↓ ↓
Document Store Links
↓ │
Indexer └──→ URL Frontier
↓
Search Index
ONLINE QUERY PATH
User
↓
API / Query Service
↓
Query Cache
↓
Query Coordinator
↓
Distributed Index Shards
↓
Candidate Results
↓
Ranking
↓
Top ResultsThe architecture has two independent workloads:
Crawler and Indexer continuously prepare searchable data.
Query infrastructure serves users with low latency.
A Web Crawler automatically visits web pages and discovers new URLs.
Suppose crawling starts from:
<https://example.com>The crawler downloads the page and finds links such as:
/products
/blog
/about
/contactThese URLs are scheduled for future crawling.
Seed URLs
↓
Fetch Page
↓
Extract Links
↓
Add New URLs
↓
Fetch More PagesThis process continuously expands the set of known pages.
A crawler needs initial starting points called seed URLs.
They may come from:
Known websites
Sitemaps
Previously crawled domains
Submitted URLs
Trusted directories
Discovered URLs are placed into a URL Frontier.
Discovered URLs
↓
URL Frontier
↓
Crawler WorkersThe URL Frontier is more than a simple FIFO queue. It decides what to crawl and when.
It may consider:
Page importance
Last crawl time
Historical update frequency
Domain priority
Freshness requirements
Per-domain crawl limits
A crawler should not overload external websites.
For example, sending thousands of simultaneous requests to one small domain could disrupt it.
The crawler therefore applies crawl politeness and per-host rate limits.
Domain A Queue → controlled rate
Domain B Queue → controlled rate
Domain C Queue → controlled rateThe crawler should also respect applicable site-level crawling instructions.
Keeping URLs organized by host or domain makes rate enforcement easier.
The same URL may be discovered many times.
Page A ──→ Page X
Page B ──→ Page X
Page C ──→ Page XWithout deduplication, Page X could be crawled repeatedly.
At small scale, a database or hash set may be sufficient.
At very large scale, a Bloom filter can help reduce expensive membership checks.
A Bloom filter can answer:
Definitely not present
or
Probably presentIt is memory-efficient but may produce false positives.
URL deduplication and content deduplication are different problems:
URL deduplication prevents repeatedly crawling the same URL.
Content deduplication identifies different URLs containing the same or very similar content.
The Page Fetcher downloads content over HTTP.
URL
↓
HTTP Request
↓
HTML ResponseThe system may record:
HTML/content
HTTP status
Headers
Fetch timestamp
Content type
Redirect information
The Parser then converts raw content into a normalized document.
It may extract:
Title
Main text
Headings
Links
Metadata
Language
Canonical information
Structured data
For example:
<h1>Learn Distributed Systems</h1>
<p>A distributed system uses multiple machines...</p>can become:
Title: Learn Distributed Systems
Text: A distributed system uses multiple machines...This normalized representation is easier to index.
Links serve two major purposes:
Discover new documents.
Provide signals that may later help ranking.
Parser
↓
Link Extractor
↓
URL FrontierThis creates the crawling loop:
Fetch → Parse → Extract Links → Schedule → FetchDifferent URLs can contain identical or nearly identical content.
For example:
example.com/product?id=100
example.com/products/100
example.com/product?id=100&utm_source=emailIndexing every copy wastes storage and can reduce result quality.
A document can therefore be assigned a fingerprint:
Document
↓
Fingerprint / Hash
↓
Duplicate DetectionExact hashes work for identical content.
Near-duplicate detection requires similarity-based fingerprints or algorithms.
A search engine may keep normalized document information separately from the search index.
Example:
document_id
url
title
content
language
crawl_time
metadata
content_hash
statusThe document store can support:
Re-indexing
Debugging
Snippet generation
Ranking features
Freshness tracking
The search index does not need to contain every field from the original document.
The inverted index is the core data structure used for fast text retrieval.
Suppose we have:
Document 1: "system design interview"
Document 2: "search engine design"
Document 3: "system design course"A document-oriented representation is:
Doc 1 → system, design, interview
Doc 2 → search, engine, design
Doc 3 → system, design, courseAn inverted index reverses that relationship:
system → Doc 1, Doc 3
design → Doc 1, Doc 2, Doc 3
interview → Doc 1
search → Doc 2
engine → Doc 2
course → Doc 3So for:
system designthe engine can quickly inspect the posting lists for system and design instead of scanning every document.
Normal representation:
Document → TermsInverted representation:
Term → DocumentsThe relationship is inverted to optimize term-based lookup.
The documents associated with a term form its posting list.
search →
Doc 10
Doc 21
Doc 40
Doc 80A posting may contain more than a document ID:
document_id
term_frequency
positions
field_informationFor example:
search →
Doc 10: frequency=5, positions=[3, 17, 28, 50, 91]Positions are useful for phrase and proximity searches.
Before indexing, document text is converted into searchable tokens.
"Building a scalable search engine"may become:
building
a
scalable
search
engineProcessing may include:
Tokenization
Case normalization
Language detection
Stop-word handling
Stemming or lemmatization
For example:
Search
SEARCH
searchmay normalize to:
searchRelated word forms may also be normalized:
running → run
runs → runThis can improve recall, but overly aggressive normalization may create incorrect matches.
That creates a precision vs recall trade-off.
Modern search systems also do not necessarily remove every stop word because words such as the, a, and of can matter in phrases.
The complete indexing path is:
Raw Document
↓
Parser
↓
Text Processing
↓
Tokenizer / Normalizer
↓
Indexer
↓
Inverted IndexThis processing happens before user queries arrive.
Suppose a user searches:
distributed database designThe online path may perform:
Receive Query
↓
Normalize
↓
Spell Correction / Query Understanding
↓
Retrieve Candidates
↓
Rank Candidates
↓
Return Top ResultsQuery normalization should generally be compatible with the normalization used during indexing.
For:
search engine designthe inverted index may contain:
search → D1, D4, D7, D20
engine → D1, D4, D11, D20
design → D1, D9, D20, D30Documents such as:
D1
D20match all three terms and become strong candidates.
A production search engine may retrieve a much larger candidate set before final ranking.
Retrieval answers:
Which documents might match?
Ranking answers:
Which matching documents should appear first?
A simplified score might combine:
Text Relevance
+ Document Quality
+ Freshness
+ Authority
+ Query Intent
+ Contextual SignalsRanking is product-specific. An e-commerce search engine and a web search engine may use very different signals.
TF-IDF is a classic information-retrieval concept.
It gives more importance to terms that:
Appear frequently in a particular document.
Are relatively uncommon across the whole collection.
A common word such as the provides little information, while a term such as consistent hashing can be much more useful.
BM25 is a widely used text-ranking approach that considers factors such as:
Term frequency
Document length
Term rarity
An important idea is that repeating a keyword hundreds of times should not increase relevance indefinitely.
For interviews, understanding this intuition is usually more important than memorizing the formula.
Text matching alone may not identify high-quality web pages.
Links between documents can provide additional authority signals.
Trusted Page A ──┐
├──→ Page X
Trusted Page B ──┘If high-quality pages reference Page X, that can contribute to its authority score.
Freshness is another ranking signal, but its importance depends on the query.
"how binary search works"may not require recent content.
But:
"latest football results"requires very fresh results.
Ranking should therefore consider query intent.
Running an expensive ranking model over billions of documents is impractical.
Large search systems therefore use multiple stages.
Billions of Documents
↓
Fast Candidate Retrieval
↓
10,000
↓
Lightweight Ranking
↓
1,000
↓
Advanced Ranking
↓
100
↓
Top ResultsEarly stages are fast and broad.
Later stages are more expensive but process far fewer candidates.
This provides a practical balance between relevance and latency.
The complete index may be too large for one machine.
We therefore partition it into shards.
Suppose:
1 billion documents
100 shardsEach shard may hold roughly a portion of the document collection and maintain its own inverted index.
Query
↓
Query Coordinator
/ | \
↓ ↓ ↓
Shard 1 Shard 2 Shard 3
\ | /
↓ ↓ ↓
Merge ResultsQueries can execute across shards in parallel.
A common approach is:
Shard 1 → Documents 1–10M
Shard 2 → Documents 10M–20M
Shard 3 → Documents 20M–30MEach shard searches its local index and returns its best candidates.
Another approach partitions by terms:
Shard A → A–F
Shard B → G–M
Shard C → N–ZHowever, multi-term queries may require communication across several term shards.
Document-based partitioning is often easier to reason about for distributed query execution.
The Query Coordinator sends a query to relevant shards.
Query
↓
Coordinator
├──→ Shard 1
├──→ Shard 2
├──→ Shard 3
└──→ Shard NEach shard may return its local top results.
Shard 1 → Top 100
Shard 2 → Top 100
Shard 3 → Top 100
↓
Merge + Rank
↓
Top 10This is known as the scatter-gather pattern:
Scatter: send work to multiple shards.
Gather: collect and merge their results.
Each index shard should have replicas.
Shard 5
├── Replica A
├── Replica B
└── Replica CIf one replica fails, another can serve queries.
Replication improves:
Availability
Fault tolerance
Read throughput
The trade-off is higher storage and infrastructure cost.
Scatter-gather introduces a straggler problem.
Suppose:
99 shards → 40 ms
1 shard → 2 secondsWaiting indefinitely for one slow shard can destroy query latency.
Possible strategies include:
Timeouts
Replica fallback
Hedged requests
Partial results
Shard health tracking
For many search products, returning slightly incomplete results quickly is preferable to waiting several seconds.
Popular queries may be repeated thousands of times.
Query
↓
Cache
├── HIT → Return Cached Results
└── MISS → Search IndexCaching reduces:
Query latency
Shard load
Ranking computation
A cache key may include:
query
language
country
filters
safe_search_settingsPersonalized search makes caching harder because different users may receive different rankings.
Cached results should expire.
Frequently changing queries can use shorter TTLs, while stable informational queries can use longer TTLs.
This creates another freshness vs performance trade-off.
When the user types:
system desthe engine may suggest:
system design
system design interview
system design course
system design questionsAutocomplete must be extremely fast because requests occur after almost every keystroke.
Prefix-oriented structures such as a Trie can help conceptually, although large systems usually require distributed, compressed representations.
Suggestions may be ranked using:
Search popularity
Recent trends
Language
Location
Freshness
Personal history when appropriate
Autocomplete is often implemented as a separate service because its latency and access patterns differ from normal search.
A user may type:
serch engneand receive:
search engineSpell correction can use:
Edit distance
Dictionary frequency
Query logs
Context
Language models
Historical query logs can also support:
Autocomplete
Trending queries
Spell correction
Ranking improvements
Analytics
User data should be handled according to appropriate privacy and retention policies.
Search results often include a short preview.
System Design Guide
Learn how to design scalable distributed systems,
including caching, databases, queues...Snippets can be:
Generated during indexing
Generated at query time
Generated using a hybrid approach
Pre-generated snippets are faster.
Query-time snippets can be more relevant to the specific query but require additional computation.
Rebuilding the entire index whenever a document changes would be expensive.
A practical design may maintain:
Main Index
+
Fresh IndexNew documents are written into smaller fresh segments and become searchable quickly.
Later, background merging combines them into larger optimized segments.
Index segments are often immutable.
Benefits include:
Simpler concurrency
Easier replication
Efficient compression
Safer reads
When a document changes, the system can:
Mark Old Version Obsolete
+
Index New VersionFor deletion:
Document
status = DELETEDQuery servers exclude deleted versions.
Background compaction eventually removes obsolete data physically.
This avoids expensive in-place modifications to large index structures.
Posting lists can consume enormous amounts of storage.
Instead of storing document IDs:
1, 10, 13, 17, 20, 22, 25, 30the system may store gaps:
1, 9, 3, 4, 3, 2, 3, 5Smaller values can often be compressed more efficiently.
Compression reduces:
Disk space
Memory usage
Disk I/O
Network transfer
The trade-off is additional CPU for encoding and decoding.
One crawler eventually becomes insufficient.
URL Frontier
↓
┌──────────┼──────────┐
↓ ↓ ↓
Crawler 1 Crawler 2 Crawler 3The frontier and deduplication system need distributed coordination so workers do not repeatedly process the same URLs.
One possible strategy is domain-based partitioning:
hash(domain) → crawler partitionFor example:
example.com → Crawler Partition 2
site.com → Crawler Partition 8Keeping a domain on the same logical partition can simplify crawl-rate enforcement.
Hot domains may still require additional balancing.
The URL Frontier should be durable.
A worker can temporarily claim a URL:
URL Frontier
↓
Worker Claims URL
↓
Fetch + Process
↓
Acknowledge CompletionIf the worker crashes before completion, the URL can become available for retry.
This is similar to a reliable distributed task queue.
A search engine normally uses multiple storage systems because different datasets have different access patterns.
Document Metadata
document_id
url
title
crawl_time
content_hash
language
statusLink Graph
source_document
target_documentCrawl State
url
last_crawled
next_crawl
priority
statusSearch Index
term → posting listQuery Logs
query
timestamp
result_clicks
latencyThis is an example of polyglot persistence: choosing storage according to workload instead of forcing all data into one database.
OFFLINE / INDEXING PATH
Seed URLs
↓
URL Frontier
↓
┌──────────────┼──────────────┐
↓ ↓ ↓
Crawler 1 Crawler 2 Crawler N
└──────────────┬──────────────┘
↓
Parser
┌─────┴─────┐
↓ ↓
Document Store Links
↓ │
Indexer └──→ URL Frontier
↓
Search Index Shards
ONLINE QUERY PATH
User
↓
API / Query Service
↓
Query Cache
↓
Query Coordinator
↓
┌────────────┬────────────┬────────────┐
↓ ↓ ↓ ↓
Shard 1 Shard 2 Shard 3 Shard N
└────────────┴─────┬──────┴────────────┘
↓
Candidate Merge
↓
Ranker
↓
Top ResultsSuppose the crawler discovers:
example.com/search-engine-guideThe flow is:
URL Discovered
↓
URL Frontier
↓
Crawler Fetches Page
↓
Parse Content + Extract Links
↓
URL / Content Deduplication
↓
Store Normalized Document
↓
Tokenize + Normalize
↓
Build Posting Lists
↓
Publish Searchable Index SegmentNewly discovered links return to the URL Frontier.
The page has now moved from an unknown URL to a searchable document.
Suppose a user searches:
search engine architectureThe flow is:
User Query
↓
API / Query Service
↓
Query Cache
↓
Query Processing
↓
Query Coordinator
↓
Index Shards
↓
Candidate Results
↓
Ranking
↓
Snippet Generation
↓
Top ResultsIf the cache contains a sufficiently fresh result, some of the distributed search work can be avoided.
A search engine balances freshness, relevance, latency, availability, and cost.
Crawl Freshness vs Cost: Frequent crawling improves freshness but increases cost.
Index Freshness vs Efficiency: Fresh segments improve freshness but add merging overhead.
Relevance vs Latency: Better ranking improves relevance but increases latency.
Replication vs Cost: More replicas improve availability but increase cost.
Personalization vs Cacheability: Personalization improves relevance but reduces cache reuse.
Consistency vs Availability: Eventual consistency improves availability with small indexing delays.
HLD focuses on overall architecture and scalability, while LLD focuses on component-level implementation.
Feature | HLD | LLD |
|---|---|---|
Focus | Architecture and scale | Implementation details |
Main Topics | Crawling, indexing, sharding, caching, ranking | Classes, interfaces, data structures |
Components | Crawler, Indexer, Query Service, Shards | Parser, Tokenizer, PostingList, RankingStrategy |
Main Question | How does the system work and scale? | How is each component implemented? |
A search engine evolves gradually as data size, traffic, and system requirements grow.
Start with a simple search server and local index for a small dataset.
Documents
↓
Search Server
↓
Local IndexAdd automated components to collect, process, and index documents.
Crawler
Indexer
Document StoreAdd caching and query replicas to handle increasing search traffic.
Load Balancer
Query Replicas
Query CacheDistribute crawling and indexing when the dataset becomes too large for a single system.
Distributed Crawling
Index Sharding
Parallel Queries
Replication
Background Segment MergingAdd advanced distributed features to support massive scale, freshness, and relevance.
Multi-Region Infrastructure
Advanced Ranking
Distributed Link Analysis
Fresh Indexes
Autocomplete
Spell Correction
Large Query Caches
Advanced Crawler SchedulingThe architecture should grow with actual requirements rather than starting with unnecessary complexity.
Answer: I would separate it into an offline indexing path and an online query path.
The offline path crawls, parses, deduplicates, and indexes documents.
The online path processes queries, searches distributed index shards, retrieves candidates, ranks them, and returns the top results.
At scale, I would add sharding, replication, caching, fresh index segments, and fault-tolerant crawling.
Answer: An inverted index maps searchable terms to the documents containing them.
database → D1, D5, D19Instead of scanning every document, the engine directly reads posting lists for the query terms.
Answer: At billions of documents, full scans would require enormous computation and create unacceptable latency.
An inverted index moves expensive processing to indexing time and makes query-time retrieval much faster.
Answer: Start with seed URLs, fetch pages, parse them, extract links, deduplicate discovered URLs, and schedule new URLs through a URL Frontier.
At scale, add prioritization, crawl politeness, durable state, distributed workers, and retries.
Answer: A URL Frontier schedules URLs waiting to be crawled.
It manages crawl priority, recrawl timing, domain rate limits, and worker assignment.
Answer: Normalize URLs and maintain visited-URL state. Bloom filters can help at very large scale.
For content, use hashes for exact duplicates and similarity-based fingerprints for near duplicates.
Answer: First retrieve a manageable candidate set, then rank it using signals such as text relevance, quality, authority, freshness, and query intent.
At large scale, use multi-stage ranking so expensive models run only on a smaller candidate set.
Feature | TF-IDF | BM25 |
|---|---|---|
Purpose | Classic relevance scoring | Practical text ranking |
Term Frequency | Yes | Yes |
Term Rarity | Yes | Yes |
Document Length | Limited/basic handling | Explicit normalization |
Term-Frequency Saturation | Basic | Better handled |
Main Use | Understanding relevance fundamentals | Ranking matching documents |
Answer: Partition the index across multiple shards.
Each shard stores part of the document collection. Queries run across shards in parallel, and a coordinator merges their best results.
Answer: The coordinator scatters the query across multiple shards and gathers their local results to calculate the global top results.
The main challenge is slow or failed shards.
Answer: Replicate index shards and run multiple query servers.
Use load balancing, health checks, timeouts, replica fallback, and failure-aware routing.
Answer: Use timeouts, replica fallback, hedged requests where appropriate, and shard health tracking.
For many search systems, slightly incomplete results are better than making the entire request wait for one slow shard.
Answer: Add new documents to a smaller fresh index or immutable segment and publish it quickly.
Background merging later combines smaller segments into optimized indexes.
Answer: For updates, index the new version and mark the old version obsolete.
For deletion, use a deletion marker and remove obsolete data later through background compaction.
Answer: Use distributed crawling, partitioned storage, sharded inverted indexes, replication, compressed posting lists, parallel query execution, and caching.
No single machine should own the complete workload.
Answer: Store popular query prefixes in a prefix-optimized structure and rank suggestions using popularity, freshness, language, and location.
Autocomplete is usually a separate low-latency service.
Answer: Generate likely corrections using edit distance, dictionary frequency, historical queries, context, and language models.
Apply corrections automatically only when confidence is sufficiently high; otherwise suggest them.
Answer: Popular queries repeat frequently.
Caching avoids repeated distributed searches and ranking work, reducing latency and backend load.
Answer: Recrawl important or frequently changing pages more often and use fresh index segments so new content becomes searchable quickly.
Answer: Use inverted indexes, query caching, parallel shard execution, replicas, efficient posting lists, compression, multi-stage ranking, and timeouts for slow shards.
Most importantly, avoid unnecessary expensive work at query time.
Answer: Compression reduces memory, disk, I/O, and network requirements for large posting lists.
The trade-off is additional CPU for decompression.
Answer: Use query caching first so repeated requests do not repeatedly hit every shard.
Also use replicated query servers, load balancing, capacity scaling, and rate limiting where appropriate.
Answer: The core inverted-index architecture remains useful, but ranking signals change.
Product search may consider:
Text relevance
Category
Price
Availability
Popularity
Ratings
Sales
Personalization
Filters and facets also become important.
Answer: Crawl tasks should come from a durable URL Frontier.
Workers temporarily claim URLs. If a worker crashes before completing them, those URLs become available for retry.
Answer: Common bottlenecks include crawl bandwidth, indexing throughput, hot shards, slow shard responses, ranking computation, cache misses, replication, segment merging, and popular-query spikes.
Monitor each stage separately instead of treating search latency as a single metric.
Avoid these mistakes:
Designing only the query API and ignoring crawling/indexing
Saying “use Elasticsearch” without explaining the architecture
Scanning documents at query time
Ignoring URL and content deduplication
Ignoring crawl politeness
Keeping the complete index on one machine
Ignoring slow shards and partial failures
Rebuilding the entire index for every update
Applying expensive ranking to every document
Requiring strong consistency everywhere
Ignoring index freshness
Adding personalization without discussing caching and privacy
Naming technologies before explaining requirements
A strong design explains the reason behind each architectural decision.