Search Engine (Elasticsearch) — Full-Text Search & Inverted Index

1. What Is It?

Elasticsearch is a distributed search and analytics engine built on top of Apache Lucene. It stores data as JSON documents and indexes them using an inverted index — a data structure that maps every unique term to the list of documents containing it. This enables sub-second full-text search across billions of documents: instead of scanning documents one by one, Elasticsearch looks up a term in the inverted index once and instantly retrieves all matching document IDs.

Without Elasticsearch (or a similar search engine), teams implement "search" as SQL LIKE '%query%' — a full-table scan that scales poorly and has no concept of relevance ranking. Elasticsearch solves three problems that SQL databases cannot: (1) full-text search with linguistic analysis (stemming — reducing words to their root form, e.g. "running" → "run"; stop words — filtering out common words like "the" and "is" that don't carry search meaning; synonyms), (2) relevance scoring (which result is most relevant?), and (3) faceted/aggregated search ("show me results grouped by category with counts"). It's used for search boxes, log analytics, security monitoring, and increasingly for AI-powered semantic search via vector embeddings.

2. How It Works

The Inverted Index

The inverted index is the heart of Elasticsearch. When a document is indexed:

1. The text is passed through an analyzer: tokenizer (split into terms) → token filters (lowercase, remove stop words, stem words: "running" → "run")
2. Each resulting term is added to the inverted index with a pointer to the document

Documents:
  doc1: "Elasticsearch is fast and scalable"
  doc2: "Elasticsearch powers Wikipedia search"
  doc3: "Fast search with inverted index"

Inverted Index (simplified):
  elasticsearch → [doc1, doc2]
  fast          → [doc1, doc3]
  scalable      → [doc1]
  power         → [doc2]        ← stemmed from "powers"
  wikipedia     → [doc2]
  search        → [doc2, doc3]
  invert        → [doc3]        ← stemmed from "inverted"
  index         → [doc3]

Query "fast search" → INTERSECT lookup:
  fast → [doc1, doc3]
  search → [doc2, doc3]
  Result: doc3 (contains both), then doc1 and doc2 (contain one each, ranked by BM25 score)

Relevance Scoring: BM25

Since Elasticsearch 5.0, the default ranking algorithm is Okapi BM25, replacing TF-IDF. BM25 scores documents higher when:

• The query term appears frequently in the document (term frequency), but with diminishing returns (term saturation)
• The document is short (length normalization: long documents are penalized less than raw TF-IDF would suggest)

$\text{score}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{\text{avgdl}})}$

Where $k_1$ (term saturation, default 1.2) and $b$ (length normalization, default 0.75) are tunable parameters.

Write / Indexing Path

An Elasticsearch index is split into shards — independent chunks of the index, each stored on a different node. Each shard is a self-contained Lucene index. Replicas are copies of each shard stored on different nodes for redundancy and read throughput.

1. Document sent via HTTP PUT /index/_doc/id or bulk API
2. Document routed to correct primary shard: shard = hash(document_id) % num_primary_shards
3. Document written to the translog (WAL) for durability
4. Document added to the in-memory buffer
5. On refresh (~every 1 second): in-memory buffer written to a new Lucene segment → document becomes searchable (Near Real-Time)
6. On flush: translog cleared, segments written durably to disk
7. Background merge: small Lucene segments merged into larger ones to reduce file handles and improve query performance

Write → Translog (durability) + Buffer (in-memory)
  ↓ (every 1 second)
Refresh → New Lucene segment opened for search (NRT)
  ↓ (periodic)
Flush → Segments written to disk, translog cleared
  ↓ (background)
Merge → Small segments merged into larger segments

Read / Search Path

1. Query sent to any node (becomes the coordinating node)
2. Coordinating node broadcasts query to all relevant shards (primary or replica)
3. Each shard executes the query locally against its Lucene index, returns top-K hits with scores
4. Coordinating node merges results from all shards, re-ranks by global score, returns top results

Mermaid: Architecture Overview

-+ResetFullscreen

Mermaid: Indexing Pipeline

-+ResetFullscreen

3. Variants & Comparisons

Search Engine Options

Query Types in Elasticsearch

4. When to Use It (and When NOT To)

Use Elasticsearch When:

• Full-text search with relevance ranking: User-facing search boxes where "which result is most relevant?" matters. BM25 scoring, fuzzy matching, and linguistic analysis (stemming, synonyms) are built-in.
• Log aggregation and observability (ELK Stack): Ingest millions of log lines/second with Logstash, index in Elasticsearch, visualize in Kibana. At scale, this beats grep over files by orders of magnitude.
• Faceted/aggregated search: "Show me products in category X, price range Y, and count how many match each subcategory" — Elasticsearch aggregations are purpose-built for this.
• Near-real-time search on frequently changing data: Documents indexed become searchable within ~1 second. Suitable for social feeds, news, e-commerce inventory.
• Semantic / vector search: Dense vector fields + kNN (approximate nearest neighbor via HNSW) enable semantic search with text embeddings. Hybrid search combines BM25 + vector similarity.
• Multi-field search: Search across many JSON fields simultaneously with different boost weights per field.

Do NOT Use Elasticsearch When:

• Primary data store (source of truth): Elasticsearch is a search index, not a database. It lacks transactions, foreign keys, and strong consistency. Data lives in your primary DB; Elasticsearch gets a copy for search.
• Strong consistency required: Elasticsearch is eventually consistent. During writes, shard replicas may briefly diverge. Don't query Elasticsearch for financial or inventory decisions requiring strong consistency.
• Simple key-value lookups: A GET /users/123 lookup is better served by PostgreSQL or Redis. Don't use Elasticsearch as a glorified key-value store.
• Complex relational queries: JOINs in Elasticsearch are limited (nested documents or parent-child) and expensive. Use a relational database.
• Low-budget systems with sparse search traffic: Elasticsearch requires 3+ nodes for a production cluster. For a small app with occasional search, PostgreSQL's full-text search (tsvector, tsquery) is simpler and cheaper.
• Real-time ACID writes: The ~1-second NRT refresh means very recent writes aren't immediately searchable. For applications requiring instant read-your-write consistency, this is a problem.

Decision Triggers

5. Real-World Usage

Wikipedia → Elasticsearch (Site-Wide Search)

Wikipedia uses Elasticsearch to power its search across millions of articles in hundreds of languages. The challenge: multilingual full-text search with complex analyzers per language (different stemming rules, stopwords, character filters for non-Latin scripts), relevance ranking that considers article quality signals alongside BM25 scores, and near-real-time updates as articles are edited. Elasticsearch's per-field analysis and custom similarity plugins make this feasible.

GitHub → Elasticsearch (Code Search)

GitHub uses Elasticsearch to power its code repository search — billions of files searchable by code content, filename, language, and repository metadata. Code search requires specialized tokenizers (split on camelCase, underscores, brackets) rather than natural language analysis. GitHub has a massive deployment with strict latency SLAs for the search box on every repo page.

Netflix → Elasticsearch (15+ Clusters, ~800 Nodes)

Netflix's Elasticsearch deployment has grown to 15+ clusters with approximately 800 nodes, handling search and data retrieval for multiple internal and external use cases — content search, data discovery, internal tooling. Netflix's scale is a good illustration of the operational complexity of large Elasticsearch deployments: cluster upgrades, shard rebalancing, and index lifecycle management at this scale require significant investment.

6. Interview Cheat Sheet

5 Sentences to Show Deep Understanding

1. "Elasticsearch's inverted index is the inverse of a document store: instead of mapping document IDs to their content, it maps every term to the list of documents containing it — so a search query is just a set of O(1) lookups in this map, not a full scan."

2. "BM25 replaced TF-IDF as the default scorer in Elasticsearch 5.0; the key improvement is term frequency saturation — repeated occurrences of a term yield diminishing score increases, preventing documents that spam keywords from unfairly dominating results."

3. "Elasticsearch is near-real-time, not real-time: a document becomes searchable only after the next refresh (default: every 1 second), when the in-memory buffer is written to a new Lucene segment and opened. If you need instant read-after-write, you either call a manual refresh or accept the NRT constraint."

4. "Elasticsearch is a search index, not a primary database — it's eventually consistent, lacks transactions, and can lose very recent data if nodes fail before segments are flushed. The source of truth lives in your primary DB; Elasticsearch gets a copy via change data capture or dual-write."

5. "Vector search in Elasticsearch (v8+) uses HNSW (Hierarchical Navigable Small World) graphs for approximate kNN — you store dense vector embeddings as dense_vector fields and query by cosine similarity. Hybrid search combines BM25 lexical scoring with vector similarity for best of both worlds."

Common Follow-Up Questions

Q: What is the thundering herd / hot shard problem in Elasticsearch? A: If documents are unevenly distributed across shards (e.g., shard key correlates with a popular category), one shard receives disproportionate queries. Solution: (1) use routing with load spreading across multiple shards; (2) avoid using natural document IDs as routing keys; (3) monitor shard-level metrics and reindex with better distribution.

Q: What happens when the master node goes down? A: Elasticsearch automatically elects a new master from the master-eligible nodes. During master election, the cluster is temporarily unavailable for write operations (no shard allocation, index creation). Reads continue from existing shards. For production, run 3+ master-eligible nodes to tolerate one failure.

Q: How would you keep Elasticsearch in sync with your primary database? A: Three approaches: (1) Dual-write: application writes to DB and Elasticsearch transactionally (risk: partial failure leaves them out of sync). (2) CDC via Debezium/Kafka: stream database changes to Kafka, consume and index in Elasticsearch (eventual consistency, handles failures gracefully). (3) Bulk re-index on schedule: for batch workloads where NRT isn't needed. The Kafka CDC approach is most robust for production.

Q: How does Elasticsearch handle schema changes? A: Elasticsearch uses dynamic mapping (auto-detects field types on first write) but the mapping for a field, once set, cannot be changed on existing data (e.g., you can't change a keyword field to text). Schema changes require creating a new index with updated mapping and reindexing the data — the _reindex API or aliased indices with zero-downtime reindex strategies.

Connections to Other Building Blocks

• Message Queues (Kafka): The canonical pattern for keeping Elasticsearch in sync: DB writes stream via Kafka → Elasticsearch consumer indexes the changes. Kafka provides durability and backpressure.
• Document Store (MongoDB/DynamoDB): Elasticsearch is often layered on top of a document store. MongoDB stores the authoritative records; Elasticsearch provides the search layer. A change stream / DynamoDB Streams feeds changes to Elasticsearch.
• Caching (Redis): Cache popular search queries. A Redis GET query_hash check before hitting Elasticsearch reduces load for trending searches (e.g., "iPhone 15" on a product search on Black Friday).
• CDN & Edge Caching: Search results for popular queries can be cached at the edge for seconds (with a short TTL). Autocomplete suggestions (static-ish) can be cached aggressively.
• Sharding & Partitioning: Elasticsearch shards documents across nodes. Choosing shard count is critical: too few → one large shard per node limits parallelism; too many → overhead from coordination. Rule of thumb: aim for shards of 20–50 GB.