Think of a library where every book has been torn apart, and each word from every page has been pinned to a giant corkboard with a note saying which book and page it came from. When you ask for books about “distributed consensus”, the librarian goes directly to the “distributed” pin and the “consensus” pin, takes the intersection of their page-lists, and hands you the relevant books - all in seconds, without scanning a single full text. This is the inverted index: a mapping from terms to the documents that contain them, built offline so that query time is a lookup, not a scan.

The engineering challenge at 10 billion documents is that no single machine can hold this corkboard. A typical English web document averages 500 unique tokens. At 10B documents that is roughly 5 trillion term-document pairs. Even with aggressive compression, the index for a corpus of this size runs into hundreds of terabytes. A naive full-text scan at 1GB/s throughput would take over 100,000 seconds per query - roughly 27 hours. We need to make query time a function of the result set size, not the corpus size.

Three forces pull in opposite directions. Write latency versus index freshness: building a high-quality compressed index takes time - Lucene-style segment merging can lag by seconds to minutes. But users expect documents they just published to be searchable immediately. Compression ratio versus decode speed: delta-encoded variable-byte posting lists compress 10x better than raw arrays, but decoding them requires sequential iteration - the exact bottleneck at query time when intersecting thousands of candidates. Sharding for parallelism versus ranking quality: splitting documents across shards parallelizes index lookup, but BM25 ranking needs global statistics (document frequency across the entire corpus) that live on different shards.

We need to solve for inverted index structure, posting list compression, near-real-time indexing with segment merging, BM25 scoring with global stats, shard-aware query execution, and sub-100ms p99 latency at 10B documents simultaneously.

Requirements and Constraints

Functional Requirements

• Index 10 billion documents averaging 500 tokens each
• Support full-text keyword queries with relevance ranking
• Return top-K results (K = 1 to 100) with BM25 scores
• Support phrase queries (“exact phrase”) and boolean operators (AND, OR, NOT)
• Near-real-time indexing: documents searchable within 5 seconds of ingestion
• Support document updates and deletions (mark deleted, filter at query time)
• Field-aware search: title, body, tags with per-field boost weights

Non-Functional Requirements

• Query latency: p50 < 20ms, p99 < 100ms at 50,000 QPS
• Index ingestion throughput: 100,000 documents per second sustained
• Total corpus: 10 billion documents, approximately 5TB of raw text
• Index storage: target under 500GB per shard with 10 shards (5TB total index)
• Availability: 99.9% uptime, zero data loss on shard failure
• Replication factor: 3 replicas per shard for read scaling and fault tolerance

Constraints and Assumptions

• Documents are in English; multilingual support is out of scope
• Maximum document size: 1MB of raw text
• Query terms are pre-tokenized to match the index vocabulary
• We do not support vector/semantic search - keyword relevance only
• The document store (raw document retrieval) is a separate system; the index stores only postings metadata

High-Level Architecture

The system has six major components working across two logical paths: the write path that builds and maintains the index, and the read path that executes queries against it.

The Document Ingestor receives raw documents via Kafka and applies the text analysis pipeline - tokenization, lowercasing, stopword removal, and stemming. It writes tokenized posting data into an In-Memory Write Buffer on the target shard node, where a Segment Flusher periodically persists buffered data to immutable on-disk segments. A background Segment Merger runs the LSM-style compaction process, consolidating small segments into larger ones to keep per-query segment count bounded.

On the read path, queries arrive at the Query Router, which uses a consistent shard map to fan out to the relevant shards. Each shard runs a Shard Query Executor that parses the query, looks up posting lists for each term, intersects them using DAAT (Document-at-a-Time) traversal, scores candidates with BM25 using locally cached global statistics, and returns the top-K results. The Query Router merges partial results from all shards, applies global re-ranking, and returns the final ordered list to the client.

The Inverted Index Structure

The inverted index maps each unique term in the corpus to a posting list: an ordered list of document IDs (docIDs) that contain the term, along with the term frequency within each document.

Think of a phone book but reversed: instead of name-to-number, you have word-to-document. The phone book analogy breaks down at scale because a common English word like “the” appears in virtually every document - its posting list would have 10 billion entries. This is why we separate the index into two tiers: a term dictionary (the vocabulary, stored in a B-tree or FST for O(log n) prefix lookup) and a posting store (the actual docID lists, stored in compressed binary format on disk).

Each posting list entry stores:

• doc_id (4 bytes, delta-encoded against the previous entry)
• term_freq (variable-byte encoded, typically 1-2 bytes)
• Optional: positions list for phrase queries (variable-byte, per-position delta)