Skip to main content

Design a Search Engine

Search is a fundamental capability of modern applications. Whether it's Google Search, Bing, Elasticsearch, OpenSearch, Amazon Product Search, GitHub Code Search, or an internal enterprise search, the underlying architecture involves crawling, indexing, ranking, and query processing at massive scale. Designing a search engine requires expertise in information retrieval, distributed systems, and large‑scale data processing. In this article, we walk through building a production‑grade search engine from first principles, covering the core components, scaling strategies, and trade‑offs.

Step 1: Requirements Clarification​

Functional Requirements​

  • Index documents – Accept structured or unstructured documents for future retrieval.
  • Full‑text search – Find documents containing specified keywords.
  • Phrase search – Match exact phrases.
  • Boolean search – Support AND, OR, NOT operators.
  • Auto‑complete / suggest – Provide real‑time query suggestions as users type.
  • Spell correction – Correct misspelled queries.
  • Highlight matched terms – Return snippets with matching terms highlighted.
  • Filtering and sorting – Narrow results by attributes (category, price, date) and sort (relevance, newest, price).
  • Pagination – Allow users to page through results.
  • Faceted search – Provide aggregated counts across dimensions (e.g., number of results per category).

Non-Functional Requirements​

  • Low latency – Most queries should return in under 200 ms.
  • High availability – 99.95%+ uptime; search is critical to user experience.
  • Horizontal scalability – Must scale to billions of documents and millions of queries per second.
  • High indexing throughput – New documents must be searchable within seconds (near real‑time).
  • Fault tolerance – No single point of failure; automatic failover.
  • High relevance – Results must be ordered by relevance to the query.
  • High durability – Index data must not be lost on node failure.

Step 2: Capacity Estimation​

Assume a large e‑commerce platform:

  • Total documents: 10 billion products.
  • Average document size (indexed JSON): 5 KB.
  • Documents indexed per day: 50 million (new/updated).
  • Search queries per second: 50,000 average; 500,000 peak.
  • Index size: raw data ~50 TB; inverted index overhead 1–2x, total ~100–150 TB.
  • Cache: result cache for top queries can dramatically reduce load; a few TB of memory.

Search workloads are heavily read‑oriented. Indexing is write‑intensive but happens asynchronously; queries are the online critical path.

Step 3: API Design​

The search service exposes RESTful or gRPC APIs.

  • Index Document
    POST /api/v1/index/{index_name}/doc – add or update a document. Returns { _id, result }. Idempotent with document ID.
  • Delete Document
    DELETE /api/v1/index/{index_name}/doc/{id}
  • Search
    GET /api/v1/search?q={query}&filter={field:value}&sort={field}&from={offset}&size={limit}
    Returns: { hits: [{ _source, _score }], total, aggregations }
  • Autocomplete
    GET /api/v1/autocomplete?prefix={prefix}&size=10
  • Suggest
    GET /api/v1/suggest?q={query} – returns corrected query and suggestions.
  • Get Document
    GET /api/v1/index/{index_name}/doc/{id}

Pagination uses from and size for moderate result sets; for deep pagination, cursor‑based or search‑after (search_after) approaches avoid performance degradation.

Step 4: High-Level Architecture​

A modern search engine is typically a cluster of nodes, each running the same software (e.g., Elasticsearch, OpenSearch) and working together.

  • Search API / Coordinator receives queries, distributes them to shards, aggregates results, and applies final ranking.
  • Query Parser tokenizes the query, applies stemming, stop‑word removal, and generates the query tree.
  • Ranking Service scores documents using relevance models (BM25, TF‑IDF, or ML‑based).
  • Shards (primary and replica) hold portions of the inverted index.
  • Document Store holds the original documents (often separated from the index for efficiency).
  • Cache stores results of frequently executed queries and filters.

Step 5: Crawling and Document Collection​

Data must be collected before indexing. Sources include:

  • Web crawling – A crawler discovers pages, follows links, and downloads content. Politeness policies (robots.txt, crawl delay) must be respected. Distributed crawlers use a URL frontier (priority queue) and duplicate detection (URL canonicalization, content hashing).
  • Internal data ingestion – In enterprise or e‑commerce, data is pushed via APIs, message queues (Kafka), or batch uploads. For example, when a merchant adds a product, a ProductUpdated event triggers re‑indexing.
  • Change detection – Incremental updates are captured via database triggers, Change Data Capture (CDC) from the primary store, or event streams. This enables near real‑time indexing without re‑processing the entire dataset.

Crawling and ingestion should be decoupled from the query‑serving path.

Step 6: Indexing​

The core data structure of a search engine is the inverted index.

Text Processing Pipeline:

  1. Tokenization – Split text into terms (words, numbers).
  2. Lowercasing – Normalize case.
  3. Stop words removal – Optionally remove extremely common words (the, is, at) to save space, though many modern systems retain them for phrase queries.
  4. Stemming / Lemmatization – Reduce words to a base form (“running” → “run”, “better” → “good”). Stemming is heuristic; lemmatization uses vocabulary and morphological analysis.

Inverted Index Structure: An inverted index maps each term to a posting list of document IDs where the term appears, along with frequency, positions (for phrase queries), and other metadata.

Term: "elasticsearch"
  → (doc_id=1, freq=3, positions=[5, 12, 20])
  → (doc_id=5, freq=1, positions=[2])

Index Segments: Instead of rebuilding the entire index on every update, writes go to an in‑memory buffer. Periodically, the buffer is flushed to disk as an immutable segment. A background merge process combines smaller segments into larger ones to reduce the number of segments searched at query time.

This approach allows high‑throughput writes while maintaining fast search.

Step 7: Query Processing​

When a search request arrives, the coordinator handles:

  1. Query parsing – The search string is parsed into a query tree (e.g., ("distributed" AND "systems") OR "elasticsearch").
  2. Query rewriting – Synonyms, spell correction, and auto‑expansion are applied.
  3. Tokenization and normalization – The query is processed through the same tokenization pipeline as documents.
  4. Boolean & phrase queries – The coordinator determines which posting lists to retrieve and if position information is needed.
  5. Distributed execution – For a multi‑shard index, the coordinator sends the query to each primary or replica shard. Each shard performs a local search on its segments, scores documents, and returns the top results to the coordinator.
  6. Aggregation – The coordinator merges and re‑ranks the per‑shard results to produce the global top hits. Aggregations (facets, statistics) are merged similarly.

For auto‑complete and suggest, a finite state transducer (FST) or prefix tree built from terms allows fast lookups.

Step 8: Ranking​

Ranking determines the order of results.

Classic Algorithms:

  • TF‑IDF (Term Frequency – Inverse Document Frequency): Weighs terms that are frequent in a document but rare across the whole corpus.
  • BM25: The state‑of‑the‑art probabilistic model that improves on TF‑IDF by normalizing document length and saturating term frequency. It’s the default in Elasticsearch.

Modern Signals (used by web search engines):

  • Click‑through rate – How often users click on a result.
  • Freshness – Newer content may be preferred for trending topics.
  • Popularity – PageRank or similar graph‑based authority scores.
  • Personalization – User’s location, search history, preferences.
  • Business rules – Boosting or burying specific documents (e.g., sponsored products).

A multi‑stage ranking pipeline may be used: a fast, lightweight model (BM25) retrieves the top 1000 documents; a more complex machine learning model (e.g., gradient boosted trees, learning‑to‑rank) re‑ranks the top 100.

Step 9: Distributed Index Architecture​

A single node cannot hold billions of documents. The index is partitioned into shards.

  • Sharding – Each shard is a fully independent Lucene index. Documents are assigned to a shard based on a routing key (e.g., hash(doc_id) % num_primary_shards). The number of primary shards is fixed at index creation.
  • Replicas – Each primary shard can have one or more replica shards. Replicas provide high availability and read scalability. Queries can be served by either primary or replica shards.
  • Distributed query – The coordinating node sends the query to all shards (or uses an adaptive replica selection strategy). Each shard returns its local top N. The coordinator merges.
  • Index rebalancing – When nodes are added or removed, shards are automatically reassigned to balance disk and CPU.

Elasticsearch and OpenSearch use this exact model.

Step 10: Caching Strategy​

Caching is essential to meet latency targets.

  • Query cache – The result of a filter context (e.g., category:electronics) is cached as a bitset of matching document IDs. Lucene caches these per segment.
  • Result cache – The full ranked result for frequently executed queries can be cached at the search API layer (e.g., in Redis). This is especially effective for head queries that account for a large fraction of traffic.
  • Document cache – When fetching documents for display, the document store’s cache avoids disk hits.
  • CDN / Edge cache – For public search APIs (e.g., site search), edge caches can serve static or semi‑static query responses.
  • Cache invalidation – When new documents are indexed, the relevant caches must be invalidated. A simple TTL or event‑driven invalidation (e.g., send a purge event after a bulk update) is employed.

Step 11: Scalability Strategies​

  • Horizontal scaling – Add more nodes to the cluster. The index is automatically rebalanced. More replicas increase read throughput.
  • Sharding – Properly sizing the number of shards. Too many shards adds coordination overhead; too few limits parallelism. A general rule is 10–50 GB per shard.
  • Read replicas – Increase replica count to handle higher search QPS without affecting indexing performance.
  • Multi‑region deployment – For global applications, deploy a cluster in each region, with asynchronous replication (cross‑cluster replication, CCR) to keep indices in sync. Users query the nearest region.
  • Near real‑time indexing – Refreshing the index every 1–2 seconds makes new documents searchable quickly. By default, Elasticsearch refreshes every 1 second.
  • Autoscaling – In cloud environments, add or remove nodes based on CPU, heap usage, and QPS.

To handle billions of documents, a cluster might have hundreds of nodes, with indices partitioned into thousands of shards.

Step 12: Reliability and Fault Tolerance​

  • Replica shards – If a node holding a primary shard fails, a replica is promoted to primary. Queries continue uninterrupted.
  • Retry – The client or coordinator retries on transient network errors or shard failures.
  • Failover – Master node election (using Zen discovery or Raft in newer versions) ensures cluster coordination continues.
  • Snapshots – Indices are backed up to a snapshot repository (S3, HDFS) for disaster recovery. Snapshots are incremental.
  • Cluster recovery – On a full cluster restart, shard data is replayed from the transaction log to prevent data loss.
  • Rolling upgrades – Nodes are upgraded one by one without downtime.
  • Split‑brain prevention – Minimum master nodes (discovery.zen.minimum_master_nodes or voting configuration) ensures a quorum is required to elect a master.

Step 13: Security​

  • Authentication – API keys, JWT, or basic auth for access to the search API.
  • Authorization – Role‑based access control (RBAC): some users can only search, others can also manage indices.
  • Index‑level permissions – Limit which indices a user or application can access.
  • Document‑level security – Filter results based on user attributes (e.g., a user can only see documents from their own department). Complex but possible with per‑query filtering.
  • Encryption – TLS for inter‑node and client communication. Encryption at rest for index files and snapshots.
  • Audit logging – Record who performed which search and indexing operations.

Consider an online marketplace with millions of products. The search engine must handle product uploads, full‑text search, filtering by attributes, and ranking.

  1. Merchant upload – The product data is sent via API and published to a message queue.
  2. Indexing worker – Consumes the event, transforms the data into the search document schema, and indexes it into the search cluster.
  3. User search – The search coordinator first checks the query cache. On miss, it distributes the query to all shards. Each shard searches its local segments, scores using BM25, applies filters, and returns top results. The coordinator aggregates and returns the response with facets (brands, price ranges).
  4. Ranking – BM25 provides baseline relevance. Business rules boost sponsored products. A secondary ranking service (ML model) re‑ranks the top 100 documents based on user click history, conversion rate, and margin.
  5. Cache – Frequent searches like “wireless headphones” are cached to reduce cluster load. New product updates trigger targeted cache invalidation for affected queries.

The search cluster is scaled horizontally: 30 primary shards across 15 nodes, each with 1 replica. Near real‑time refresh is set to 2 seconds to keep product availability current.

Trade-offs​

  • Freshness vs. indexing cost: Refreshing every 1 second makes indexing highly responsive but consumes CPU and disk I/O. Many applications can tolerate 5–10 second delays, reducing resource usage.
  • Ranking quality vs. latency: ML‑driven re‑ranking improves relevance but adds 50–100ms. A two‑stage approach (fast retrieval + ML re‑ranking on top N) balances both.
  • Sharding vs. operational complexity: More shards increase parallelism but also increase coordination overhead and small segment issues. Large shards reduce overhead but slow down recovery.
  • Cache size vs. memory cost: Caching top queries dramatically improves latency, but memory is expensive. Eviction policies like LRU and short TTLs manage memory.
  • Elasticsearch vs. relational database: Relational databases support LIKE and full‑text search but cannot match the speed and relevance of dedicated inverted indexes at scale. A purpose‑built search engine is necessary for large‑scale, relevance‑ranked queries.

Common Mistakes​

  • Using SQL LIKE for large‑scale search – Impossible to achieve relevant ranking and scalable full‑text search.
  • Ignoring stemming and tokenization – Without proper text processing, recall is poor (e.g., “run” won’t match “running”).
  • Oversharding – Creating hundreds of shards for a small dataset increases overhead and latency. Right‑size shards.
  • No replica shards – Losing a node means data loss and service interruption.
  • Poor ranking strategy – Default BM25 may not be optimal for all domains; relevance tuning is essential.
  • Ignoring cache – Frequent identical queries should be cached; otherwise, they needlessly hit the search cluster.
  • Rebuilding the entire index too frequently – Use incremental indexing and segment merging instead of full rebuilds.

Interview Perspective​

Search engine design appears in many system design interviews. Expect questions such as:

  • Design a web search engine like Google.
  • How does an inverted index work?
  • How would you shard a search index?
  • How do you rank search results?
  • How do you implement autocomplete?
  • How do you achieve near real‑time indexing?
  • When would you use Elasticsearch vs a relational database?

Demonstrate understanding of the inverted index, distributed query execution, sharding and replication, and the trade‑offs between freshness, relevance, and performance.

Summary​

A production search engine combines crawling or event‑driven ingestion, an efficient inverted index, distributed sharding and replication, a multi‑stage query processor, and customizable ranking. Near real‑time indexing and caching ensure fresh results at low latency. Reliability is provided by replica shards, snapshot backups, and automatic failover. The architecture scales horizontally to petabytes of data and millions of queries per second. By mastering these principles, you can design search systems that power everything from e‑commerce product discovery to enterprise knowledge bases.

Further Reading​