Search System Design

Overview

A search system takes a few words from a user and returns the most relevant documents out of millions, in well under a second. Product search, site search, log search and code search all work the same way underneath.

A database scan cannot do this. Finding every row whose text contains the word 'jacket' with LIKE '%jacket%' reads every row, and it cannot say which match is best. Search engines solve both problems with two ideas. An inverted index finds the matching documents without reading the others. A relevance score, usually BM25, ranks them.

At scale the design questions are distributed-systems questions. How do you split the index across machines, answer a query that touches all of them, keep the index in step with the database, and change the index layout without downtime? This chapter uses Elasticsearch, which is built on the Apache Lucene library, as the running example, because it is what most interviewers expect you to know.

What you will be able to do

• Build an inverted index by hand and use it to answer a query.
• Explain how text is analyzed into tokens, and why the same analysis must run on documents and queries.
• Explain BM25 in plain words: rare words count more, repeats help less and less, long documents are discounted.
• Design a sharded search cluster, a pipeline that keeps it in sync with the database, and a zero-downtime reindex.
• Add type-ahead and typo tolerance without making every query slow.

Key concepts

• Inverted index
• Analyzers and tokens
• BM25 ranking
• Shards and replicas
• Query then fetch
• Near real-time refresh
• Indexing pipeline
• Aliases and reindexing
• Type-ahead and fuzzy matching

Interview questions

• Design product search for an online store with 50 million products.
• What is an inverted index, and how does it answer a two-word query?
• Explain BM25 without the formula.
• How does a search run across many shards, and what makes it slow?
• How do you keep the search index consistent with the database?
• How would you change an index's mapping or shard count with no downtime?
• How do you build search-as-you-type that answers on every keystroke?
• Why is search near real-time rather than real-time?

More System Design topics

• Returns and Refund Management System
• RPO & RTO
• Saga Pattern for Distributed Transactions
• Scaling Reads
• Scaling Writes
• Search Ranking System
• Security
• Segmented Log
• Semantic Cache for LLM Responses
• Sentiment Analysis System
• Serverless vs Traditional
• Shopify