Skip to content

Search Engine (Elasticsearch-like)#

Problem statement (interviewer prompt)

Design a search engine like Elasticsearch: index billions of documents with an inverted index, support keyword + phrase + range + boolean queries, rank by BM25 + custom signals, return in <100ms p99, shard horizontally, and handle real-time updates.

Elasticsearch logo, the distributed inverted-index search engine
Elasticsearch logo, © Elastic NV, via Wikimedia Commons.
flowchart LR
  D[Documents]
  IDX[Indexer]
  INV[(Inverted index<br/>shards / replicas)]
  Q[Query]
  RNK([Ranker])
  D --> IDX --> INV
  Q --> INV --> RNK --> Q

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class D,IDX,Q service;
    class INV datastore;
    class RNK compute;

flowchart TB
  subgraph Ingest
    DOC[Documents]
    CDC[CDC from primary DB]
    NORM[Normalize / tokenize / stem]
    ANALY[Analyzers / language]
    EMBED([Optional: vector embeddings])
  end

  subgraph Index[Index Tier]
    SHARDS[Shards per index]
    REPL[Replicas per shard]
    SEGS[Lucene segments]
    BLOOM[Bloom / FST]
    POST[Posting lists]
    VECINDEX[HNSW vector index]
  end

  subgraph Cluster
    MASTER[Master / coordinator]
    INGEST_N([Ingest nodes])
    DATA_N[Data nodes]
    ROUTING[Routing layer]
  end

  subgraph Query
    PARSE([Query parser DSL / Lucene])
    PLAN[Planner: term + filter + rerank]
    RECALL[Recall stage: text + vector]
    RERANK([Reranker: BM25 + ML])
    HIL[Highlight + snippet]
    AGG[Aggregations / facets]
  end

  subgraph Ops
    SNAP[Snapshots to S3]
    BACKFILL[Reindex]
    HOT_WARM[Hot / warm / cold tiers]
    ILM[Index lifecycle mgmt]
  end

  Ingest --> Index
  Index --- Cluster
  Query --> Cluster
  Cluster --> Query
  Ops --- Index

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class DOC,NORM,ANALY,SHARDS,REPL,SEGS,BLOOM,POST,VECINDEX,MASTER,DATA_N,ROUTING,PLAN,RECALL,HIL,AGG,BACKFILL,HOT_WARM,ILM service;
    class CDC datastore;
    class EMBED,INGEST_N,PARSE,RERANK compute;
    class SNAP storage;

Posting lists & scoring#

  • Each term → sorted list of (doc_id, term_freq, positions).
  • Score = BM25 by default; pluggable.
  • Conjunctive AND queries iterate intersecting posting lists.

Sharding & routing#

  • Index split into shards (Lucene index instances).
  • Each shard has primary + replicas; routing by document ID hash.
  • Query fans out to all shards; coordinator merges.

Vector + BM25 hybrid#

  • Modern stacks combine lexical (BM25) and dense vector (HNSW) recall, then rerank.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD Sharding horizontal partitioning across nodes database-sharding
HLD Leader/follower replication sync/semi-sync/async replication, failover replication-leader-follower
HLD Change Data Capture WAL/binlog tailing, outbox publishing change-data-capture
HLD Search internals inverted index, BM25, embeddings, ANN search-internals

Quick reference#

Functional#

  • Full-text search with relevance.
  • Filters, facets, aggregations.
  • Geo queries.
  • Near-real-time indexing.
  • Vector / hybrid search.

Non-functional#

  • p99 search < 200 ms for typical queries.
  • Near-real-time indexing 1-10 s.
  • 99.95% availability.

Trade-offs#

  • Per-segment immutability = fast reads, slow updates.
  • Reindex on schema change is common; plan zero-downtime swap.
  • Vector indices need different sharding (HNSW graphs).

Refs#

  • Apache Lucene / Elasticsearch / OpenSearch docs.
  • "Information Retrieval" Manning et al.
  • Vespa.ai, Vespa engineering blog.
  • Algolia / Typesense as managed search.

FAQ#

How does a search engine work?#

A search engine crawls documents, tokenizes them, builds an inverted index from term to posting list, and at query time intersects posting lists to compute relevance scores.

What is BM25 ranking?#

BM25 is a probabilistic relevance function that scores documents by term frequency normalized by document length and inverse document frequency, outperforming plain TF-IDF.

How is a search engine sharded?#

Indexes are partitioned by document ID or term. Queries fan out to all shards, each returns top-k local results, and a coordinator merges them into the final top-k.

How does Elasticsearch handle real-time updates?#

New documents land in an in-memory buffer, are flushed into searchable segments every refresh interval, and merged into larger segments over time for read efficiency.

Why is search different from a SQL query?#

SQL filters rows by exact predicates. Search ranks documents by relevance, supports tokenization, stemming, and typo tolerance, and treats text as a first-class data type.

Search engines use n-gram indexes, edit distance algorithms like Levenshtein, and phonetic encoders so misspelled queries still match the intended documents.

Further reading#

Curated, high-credibility sources for going deeper on this topic.