Bird
Raised Fist0

Full-Text Search Architecture - Inverted Index Design from Scratch

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Full-Text Search Architecture - Inverted Index Design from Scratch
Design a scalable full-text search system using an inverted index from first principles
mediumSearch and IndexingFreq: common
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Index large volumes of documents with full-text content efficiently
  • Support keyword and phrase search queries with low latency (<100ms P99)
  • Provide real-time or near-real-time indexing of newly ingested documents
  • Support ranking and relevance scoring of search results
  • Allow filtering and faceted search on document metadata
  • Support incremental updates and deletions of documents in the index
📊
Non-Functional Requirements
  • Handle indexing and searching for 2 billion daily active users
  • Sustain peak write throughput of ~925K document updates per second
  • Achieve 99.99% availability for search queries
  • Ensure search query P99 latency under 100ms
  • Index storage must support retention of at least 30 days of data with replication
❓
Clarifying Questions to Ask
  • What is the average size and type of documents to be indexed?
  • What is the expected query QPS and query complexity (e.g., phrase, wildcard)?
  • Is near real-time indexing required or is batch indexing acceptable?
  • What metadata fields need to be filterable or faceted in search?
  • What is the expected retention period for indexed data?
  • Are there any SLAs for indexing latency or freshness guarantees?
Out of Scope
✗ Designing a ranking algorithm or machine learning relevance model
✗ User interface or frontend search experience
✗ Multi-language text analysis and stemming algorithms
✗ Distributed consensus or cluster management protocols
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 documents/messages per day on average
  • Average document size is 100 bytes
  • Retention period for index data is 30 days
  • Replication factor of 3 for durability
⚡
QPS Calculation
write qps2B users × 40 docs/user/day ÷ 86400 sec/day ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor during busy hours: 925,926 × 3 ≈ 2.78M writes/sec
read qpsAssuming 10% of DAU perform 10 queries/day: 2B × 10% × 10 ÷ 86400 ≈ 231,481 queries/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day uncompressed
30 day storage8 TB × 30 = 240 TB
with replication240 TB × 3 = 720 TB total storage
🖥️
Server Estimate
indexing nodesAssuming each indexing node handles 10K writes/sec, need ~278 nodes
query nodesAssuming each query node handles 5K QPS, need ~47 nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client Query  |
          +-------+--------+
                  |
          +-------v--------+
          |  Query Router  |
          +-------+--------+
                  |
      +-----------+------------+
      |                        |
+-----v-----+            +-----v-----+
| Query     |            | Indexing  |
| Service   |            | Service   |
+-----+-----+            +-----+-----+
      |                        |
      |                        |
      |                +-------v--------+
      |                |  Kafka Cluster |
      |                +-------+--------+
      |                        |
+-----v-----+            +-----v-----+
| Search   |            | Index     |
| Shards   |            | Builder   |
+-----+-----+            +-----+-----+
      |                        |
      +-----------+------------+
                  |
          +-------v--------+
          |  Storage Layer |
          | (Cassandra)    |
          +----------------+
🧩
Components
Kafka Cluster
Durable, distributed message queue for ingesting document updates asynchronously
Why thisKafka supports high throughput (millions of msgs/sec), partitioning, and retention for replay
Why notRabbitMQ lacks Kafka's horizontal scalability and partition retention guarantees at 2.7M writes/sec
Indexing Service
Consumes document updates from Kafka, tokenizes text, builds inverted index entries
Why thisCustom service allows control over tokenization and incremental index building for near real-time updates
Why notElasticsearch indexing nodes are tightly coupled with storage and less flexible for custom tokenization
Storage Layer (Apache Cassandra)
Stores inverted index data with high write throughput and horizontal scalability
Why thisCassandra provides linear write scalability, tunable consistency, and efficient range queries on partition keys
Why notPostgreSQL B-tree indexes do not scale linearly for 2.7M writes/sec and require complex sharding
Query Router
Receives search queries, routes them to appropriate query shards based on index partitioning
Why thisStateless router enables load balancing and query fan-out to multiple shards for parallelism
Why notDirect client-to-shard queries increase client complexity and reduce fault tolerance
Query Service / Search Shards
Executes search queries on local inverted index partitions, merges results for final response
Why thisSharding index by term or document ID enables parallel query execution and low latency
Why notMonolithic search service cannot handle 231K QPS with <100ms latency
🔄
Data Flow
1
Client → Kafka Cluster
Client submits documents to be indexed
Kafka partitions documents by document ID for balanced ingestion
2
Kafka Cluster → Indexing Service
Indexing service consumes document updates asynchronously
Allows decoupling of ingestion and indexing for scalability
3
Indexing Service → Storage Layer (Cassandra)
Builds inverted index entries and writes to Cassandra partitions
Partitions by term hash to distribute load evenly
4
Client Query → Query Router
Client sends search query
Router parses query and determines relevant shards
5
Query Router → Query Service / Search Shards
Fan-out query to shards holding relevant index partitions
Parallel execution reduces query latency
6
Query Service / Search Shards → Query Router
Return partial results
Router merges and ranks results before responding
7
Query Router → Client
Return final merged and ranked search results
Ensures low latency and relevance in responses

Practice

(1/5)
1. In a Raft consensus system, at Step 4, the Leader sends AppendEntries RPCs to followers. What happens if a follower's log is inconsistent at this step?
easy
A. The follower immediately accepts the entries and overwrites conflicting logs
B. The follower rejects the AppendEntries, prompting the leader to decrement the nextIndex and retry
C. The follower crashes and restarts to recover the log state
D. The follower ignores the AppendEntries and waits for the next heartbeat

Solution

  1. Step 1: Understand Raft's log replication mechanism

    If a follower's log is inconsistent with the leader's, it rejects the AppendEntries RPC to signal a mismatch.

  2. Step 2: Leader's response to rejection

    The leader decrements the nextIndex for that follower and retries AppendEntries until logs match.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Follower rejects inconsistent logs -> leader retries with decremented nextIndex [check]
Hint: Follower rejects mismatched logs; leader retries with lower index [check]
Common Mistakes:
2. A high-throughput messaging system must guarantee no data loss even if consumers are slow or temporarily offline. Which component best ensures durability without blocking producers?
easy
A. Use a distributed log like Kafka with replication and disk persistence
B. Use a cache like Redis with asynchronous persistence
C. Use a relational database with immediate commit on every message
D. Use an in-memory queue with periodic snapshots to disk

Solution

  1. Step 1: Identify durability guarantees needed

    In-memory queues and caches (A, D) risk data loss on crashes; relational DB (C) can block producers due to synchronous commits.

  2. Step 2: Evaluate Kafka's role

    Kafka provides durable, replicated logs that persist to disk and decouple producers from slow consumers, ensuring no data loss.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka replication and disk persistence ensure durability without blocking [check]
Hint: Durability needs disk + replication, not just memory or sync DB [check]
Common Mistakes:
3. If the OT engine component crashes and loses its in-memory operation buffer before persisting, what is the most likely failure observed by users during collaborative editing?
medium
A. The document becomes read-only until the OT engine restarts
B. Users' concurrent edits are lost or cause inconsistent document states without recovery
C. Users see duplicate edits because operations are replayed multiple times
D. Users experience delayed edits but no data loss due to persistent storage

Solution

  1. Step 1: Identify OT engine's role in buffering and transforming operations

    The OT engine buffers concurrent operations in memory to transform and order them before persistence.

  2. Step 2: Trace failure impact of OT engine crash losing in-memory buffer

    Without the buffer, the engine cannot process new edits correctly, causing the system to block new edits (read-only) until recovery.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    OT engine crash causes editing to block (read-only), not silent data loss [check]
Hint: OT engine crash blocks edits; no silent data loss [check]
Common Mistakes:
4. For delivering videos globally with low latency, should the system use a centralized origin server with global CDN caching, or a peer-to-peer (P2P) delivery network? Assume millions of users worldwide and variable network conditions.
medium
A. Use a centralized origin server with a global CDN to ensure consistent video availability and latency
B. Use P2P delivery combined with CDN fallback to optimize bandwidth and reliability
C. Use P2P delivery exclusively to reduce CDN costs and improve scalability
D. Use multiple regional origin servers without CDN to reduce latency

Solution

  1. Step 1: Evaluate delivery approaches for global scale and latency

    P2P (A) alone is unreliable due to variable user upload bandwidth and NAT traversal issues. Multiple regional origins without CDN (D) add complexity and don't scale well globally. P2P with CDN fallback (C) adds complexity and inconsistent performance.

  2. Step 2: Recognize CDN benefits

    A centralized origin with global CDN (B) provides consistent availability, low latency via edge caching, and simplifies management, making it the best fit for millions of users worldwide.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Global CDN ensures consistent low-latency delivery [check]
Hint: Global CDN with origin beats P2P for consistent delivery [check]
Common Mistakes:
5. At 10x scale, which component in the blob store architecture is most likely to fail first due to stateful connection limits, and why?
hard
A. Front-end API servers, because they maintain stateful client sessions and cannot easily shard connections
B. Storage nodes, because disk I/O bandwidth saturates with large blob volumes
C. Metadata service, because it cannot shard metadata fast enough across nodes
D. Distributed log system, because partition leaders become overloaded with write requests

Solution

  1. Step 1: Identify stateful bottleneck at front-end API servers

    API servers maintain stateful client sessions (e.g., HTTP keep-alive or TLS), limiting horizontal scaling due to connection affinity.

  2. Step 2: Eliminate other options

    Storage nodes scale with added disks; metadata service shards metadata; distributed log partitions scale with more brokers.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful client sessions limit API server horizontal scaling [check]
Hint: Stateful API servers limit scaling due to connection affinity [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard