Design a Search Service

This case study simulates a realistic FAANG system design interview for architecting a distributed full-text search service similar to Elasticsearch or Algolia. It explores inverted indexing, document sharding vs. term sharding, auto-complete Suggest engines, and search result ranking.

1. Present the Interview Question

2. Clarifying Questions

The candidate scopes the query rates and indexing latencies:

• Candidate: What is the search query rate at peak?
  Interviewer: We need to support 50,000 search queries per second (QPS) at peak.
• Candidate: What is the frequency of catalog modifications (creations, price updates)?
  Interviewer: Ingestion is write-heavy: we process roughly 10,000 updates/sec. New updates must be searchable within 1 second.
• Candidate: What search query types do we support?
  Interviewer: We support text matching with spelling corrections (fuzzy search), facet filtering (categories, price), and real-time auto-complete suggestions as the user types.
• Candidate: How are search results ranked?
  Interviewer: Results are ranked by text relevance (keyword matching score) combined with static product metrics (sales popularity and item ratings).

3. Functional Requirements

• Full-text Search: Search items by keywords, supporting fuzzy matching (handling spelling typos).
• Facet Filtering: Filter results dynamically by categories, price bounds, and stock availability.
• Auto-complete Suggestions: Return query suggestions as users type (under 10ms response).
• Relevance Ranking: Rank documents using text similarity (TF-IDF/BM25) combined with static popularity fields.

4. Non-Functional Requirements

• Sub-50ms Search Latency: Retrieval queries must execute in under 50ms.
• Near Real-time Ingestion: Updates must index within <1 second.
• High Read Scalability: Reliably support 50,000 QPS read queries.
• Fault Isolation: Disk intensive indexing must not degrade read search queries latency.

5. Capacity Estimation

1. Index Size Sizing

• Total items: 100 Million documents.
• Average raw document content: 2 KB.
• Raw database size: 100M * 2 KB = 200 GB.
• Inverted index structure (terms, dictionaries, offsets, lists) introduces roughly 1.5x overhead.
• Total Index Size: ~300 GB. (Because 300 GB is small, we can store the entire index in RAM across a cluster to ensure sub-50ms speeds).

2. Read & Write Bandwidth

• Search Ingress: 50,000 QPS. Average response size is 10 KB (top 20 product cards metadata).
  Egress Bandwidth: 50,000 * 10 KB = 500 MB/s (~4 Gbps network card links).
• Ingestion Ingress: 10,000 updates/sec. Average write size is 2 KB.
  Ingress Bandwidth: 10,000 * 2 KB = 20 MB/s.

6. Identify Core Components

• Search Query Service: Processes client search and filter queries.
• Auto-Complete Service: Returns dynamic prefix matches using an in-memory Trie structure.
• Ingestion Service: Consumes catalog updates and routes them to indexing nodes.
• Document Analyzer: Tokenizes text, stem words, and cleans stop-words.
• Distributed Index Shards (Lucene nodes): Hold inverted index segments.
• Coordinator Nodes: Receive search queries, fan them out to shards, merge results, and apply ranking.

7. High-Level Architecture

The High-Level setup separates write ingestion pipelines from read-replicated index search pathways:

8. API Design

1. Full-Text Search and Filter

GET /api/v1/search

Request Parameters:

• q: "leather running shoes" (Search query)
• category: "footwear" (Filter)
• priceMin: 50, priceMax: 150 (Filter bounds)
• limit: 20, offset: 0 (Pagination)

Response Payload (200 OK):

2. Auto-Complete Suggest

GET /api/v1/suggest

Request Parameters:

• prefix: "leat"

Response Payload (200 OK):

9. Data Model: Inverted Index Structure

Full-text search requires building an Inverted Index. The index maps terms (words) to the list of documents containing them (Posting List):

10. Database Selection

We choose a dedicated search engine based on Apache Lucene (like Elasticsearch) over SQL relational databases.
Justification: SQL databases do not support fast substring tokenization or ranking based on text relevance (like BM25/TF-IDF) out of the box. Indexing text columns using standard B-Trees does not support multiple keyword matching, resulting in slow table scans (LIKE %query%). Lucene maps keywords directly to documents, keeping queries fast at scale.

11. Deep Dive: Sharding Strategy

To scale past a single server's limits, we partition the 300 GB index across multiple shards. The candidate compares sharding models:

1. Term Partitioning (Shard by Term)

Each shard holds the complete posting lists for a subset of terms (e.g. Shard 1 holds A–D, Shard 2 holds E–H).
Drawback: A single write (updating a product document title with 5 words) requires updating 5 different shards. This creates distributed write locks and coordination overhead, failing to meet our 10,000 updates/sec target.

2. Document Partitioning (Shard by Document ID) - Recommended

Each shard contains the complete inverted index for a subset of documents. The shard key is hash(document_id) % total_shards.
- Writes: When indexing a product, the request goes to a single shard. Writing is highly efficient and runs in parallel with zero coordination lock overhead.
- Reads: When searching, the Coordinator Node sends the query to all shards. Each shard calculates its local top-K results. The coordinator merges the results, recalculates relevance rankings, and returns the top-K.
- Scaling reads: We deploy replica nodes for each shard to distribute the 50,000 QPS search traffic.

12. Request Lifecycle

1. Document Indexing Lifecycle (Write Ingress)

1. Upstream catalog service publishes a product update to Kafka.
2. Indexing Workers consume the update event.
3. Document Analyzer tokenizes the title: "Leather Shoes" -> ["leather", "shoes"] (stemming changes "shoes" to "shoe" and removes stop-words).
4. The worker hashes the product ID to identify the shard (e.g. Shard 1).
5. The segment is written to Shard 1's memory buffer (transient index segment).
6. Every 1 second, the buffer commits the segment to disk, making the new item searchable.

2. Search Retrieval Lifecycle (Read Ingress)

1. Client calls GET /api/v1/search?q=leather+shoes. The request hits a Coordinator Node.
2. Coordinator node parses and tokenizes the query terms.
3. Coordinator node broadcasts the search query to all active shard replicas.
4. Each shard scans its local posting lists, calculates BM25 text relevance scores, and returns its local top-100 product matches to the coordinator.
5. Coordinator merges all shard responses, applies static popularity ranking adjustments, and selects the global top 20 items.
6. The coordinator returns the product details to the client (Latency: ~25ms).

13. Scaling Strategy

• Decouple Reads from Writes: We partition our nodes into separate roles:
  - Data Nodes: Host index shards on NVMe SSD drives.
  - Search Replica Nodes: Receive read traffic and scale horizontally to handle the 50,000 QPS.
  - Ingestion/Primary Shards: Receive write updates.
• Redis Auto-complete Trie Cache: To offload prefix auto-complete traffic from search shards, we pre-compile a Trie structure in memory. The client suggestions request maps to this high-speed cache, returning suggestions in <10ms.

14. Bottleneck Analysis

• Heap Garbage Collection Pauses: Lucene cache structures are Java-based. During heavy reads, GC sweeps block execution threads, causing search latency spikes.
  Mitigation: Configure JVM options using Garbage First (G1) GC. Keep heap sizes under 32 GB (utilizing compressed pointers) and allocate the rest of server RAM to the OS filesystem cache. Lucene naturally relies on the OS cache to keep index segments in memory, bypassing JVM garbage collection.
• High-Frequency Term Fan-out: Queries for popular words (e.g. "shoes") scan huge posting lists across all shards.
  Mitigation: Deploy Query Cache at the coordinator layer. Caches store common query-result pairs (e.g., top-50 results for "shoes"), returning cached lists immediately.

15. Trade-off Discussion: Segment Commits

Candidate: Writing segment files directly to disk on every document update is called synchronous indexing. Lucene segment files are immutable. Writing on every document arrival would generate millions of tiny segment files, saturating disk write bandwidth and triggering heavy segment merges. By caching writes in a memory buffer and committing them as a single segment file once every 1 second, we reduce disk IO and support high-throughput writes (10,000 updates/sec), trading off real-time search availability for ingestion performance.

16. Failure Scenarios

Handling cluster partitioning:

• Split-Brain Outage: A network partition splits our 9-node search cluster into two halves (5 nodes and 4 nodes). Both groups elect a master node, creating conflicting index states.
  Mitigation: Configure quorum-based elections. Enforce a rule that a master can only be elected if a majority of nodes are present: minimum_master_nodes = (total_nodes / 2) + 1. This prevents split-brain partitions, as only the majority partition can elect a master, while the minority partition shuts down writes.

17. Security Design

• Query Escaping: Sanitize incoming search queries to prevent Lucene query injection (e.g. injecting wildcard filters to scrape hidden products).
• Payload Encryption: Enforce TLS encryption for inter-node shard replication traffic.

18. Monitoring & Observability

• Search Latency (p99): Alert if search query response times exceed 100ms.
• Segment Merge Queue: Track the number of background segment merge tasks. A backlog indicates disk bottleneck limits.

19. Cost Optimization

Historical analytics search queries (e.g. searching invoice records from 3 years ago) are rarely accessed but consume expensive SSD space.
We implement Hot-Warm-Cold Architecture Tiering:
- Hot Nodes: Keep recent product catalog shards on expensive, high-speed NVMe drives.
- Warm Nodes: Store historical logs on cheaper HDDs.
- Cold Nodes: Archive older logs in compressed formats on S3, keeping storage costs low.

20. Production Improvements: Trie Auto-complete

To serve auto-complete suggestions under 10ms, we build a dedicated Trie structure in-memory:
- As catalog data updates, terms are inserted into a Trie (Prefix Tree).
- For each prefix node, we store the top 10 most popular completed terms.
- The Trie is compiled into a Redis Sorted Set (ZSET) cache. When a user types a prefix, the Suggest Service queries Redis using range queries, returning matching suggestions near-instantly.

21. Interviewer Follow-up Questions

Candidate: Lucene documents are immutable. An update is technically a Delete-and-Insert operation:
1. When a price changes, Lucene marks the old document ID as "deleted" in a bitset file.
2. A new document containing the updated price is written to a new index segment.
3. During queries, deleted documents are filtered out using the bitset.
4. During background segment merges, the deleted rows are permanently purged, reclaiming space.

22. Final Architecture

The complete search service setup featuring document sharding, query coordinators, and Trie caches:

23. Summary

We designed a distributed search service to index 100M items at 50,000 QPS. We chose Document Partitioning (sharding by Document ID) to avoid distributed lock bottlenecks during writes. Lucene segment buffering guarantees near real-time ingestion under 1 second, while OS filesystem caching keeps search latency below 50ms.

24. Cheat Sheet

25. Candidate Interview Evaluation