Bird
Raised Fist0

Search Ranking and Relevance - TF-IDF, BM25 Intuition

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Search Ranking and Relevance - TF-IDF, BM25 Intuition
Design a scalable search ranking system using TF-IDF and BM25 relevance scoring
mediumSearch and IndexingFreq: high
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Index documents with term frequencies and document frequencies for TF-IDF and BM25 calculations
  • Support keyword search queries returning ranked documents by relevance score
  • Update index incrementally as new documents arrive or existing documents change
  • Support multi-field ranking (e.g., title, body) with configurable weights
  • Provide top-k results with low latency (e.g., under 100ms P99)
  • Allow configurable ranking parameters (e.g., BM25 k1, b) for tuning relevance
📊
Non-Functional Requirements
  • Handle indexing and querying at scale: 2 billion daily active users generating 40 search queries per user per day
  • Achieve 99.99% availability for search query service
  • Maintain query latency under 100ms P99
  • Index storage must support retention of 90 days of documents with replication for durability
  • Support horizontal scaling to handle peak write QPS and read QPS
❓
Clarifying Questions to Ask
  • What is the expected average document size and vocabulary size?
  • Are documents static or frequently updated/deleted?
  • What is the expected query QPS and peak traffic patterns?
  • Should ranking support multi-field weighting or just single field?
  • Is near real-time indexing required or is batch indexing acceptable?
  • What is the SLA for indexing latency from document ingestion to query availability?
Out of Scope
✗ Natural language understanding or semantic search beyond TF-IDF/BM25
✗ User personalization or learning-to-rank models
✗ Full-text indexing of multimedia content (images, video)
✗ Complex query parsing or advanced boolean operators
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user issues 40 search queries per day on average
  • Average document size is 1 KB
  • Average query returns top 10 results
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec (indexing queries as writes)
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qps2B × 40 / 86400 ≈ 925,926 reads/sec (search queries)
💾
Storage Estimate
daily storage gb2B docs × 1 KB = 2,000,000,000 KB = 1,907 GB/day
retention days90
total storage gb1,907 GB/day × 90 days = 171,630 GB ≈ 171.6 TB
with replication171.6 TB × 3 replicas = 514.8 TB
🖥️
Server Estimate
indexing nodesAssuming each indexing node handles 50K writes/sec, need 2.78M / 50K ≈ 56 nodes
query nodesAssuming each query node handles 50K QPS with 100ms latency, need 925,926 / 50K ≈ 19 nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client Search |
          +-------+--------+
                  | Query
                  v
          +-------+--------+
          |  Query Service |
          +-------+--------+
                  | Search Request
                  v
          +-------+--------+
          |  Ranking Engine|
          +-------+--------+
                  | Fetch postings
                  v
          +-------+--------+
          | Inverted Index |
          +-------+--------+
                  ^
                  | Index Updates
          +-------+--------+
          |  Indexing Svc  |
          +-------+--------+
                  | Document Ingest
                  v
          +----------------+
🧩
Components
Inverted Index
Stores term-to-document postings with term frequency and document frequency metadata
Why thisElasticsearch provides a distributed inverted index with built-in support for TF-IDF and BM25 scoring, sharding, and replication
Why notApache Lucene alone lacks distributed scaling and requires manual cluster management
Indexing Service
Processes incoming documents, extracts terms, updates inverted index asynchronously
Why thisKafka streams enable a scalable, fault-tolerant ingestion pipeline with exactly-once semantics for index updates
Why notDirect writes to Elasticsearch risk overloading the cluster and lack buffering for spikes
Query Service
Receives search queries, parses them, forwards to ranking engine, returns top-k results
Why thisStateless microservice horizontally scalable to handle 1M+ QPS with low latency
Why notMonolithic service would bottleneck and increase latency under high QPS
Ranking Engine
Computes TF-IDF and BM25 scores for candidate documents, applies multi-field weighting
Why thisCustom ranking module integrated with Elasticsearch scoring APIs allows tuning and extensibility
Why notPure Elasticsearch scoring lacks flexibility for custom multi-field weights and parameter tuning
Metadata Store
Stores document metadata, schema, and configuration for ranking parameters
Why thisCassandra provides a scalable, highly available key-value store with tunable consistency for metadata
Why notRelational DBs like PostgreSQL do not scale linearly at 1M+ QPS and require complex sharding
🔄
Data Flow
1
Client Search → Query Service
Submit search query
Client sends keyword query with optional filters
2
Query Service → Ranking Engine
Parse query and request candidate documents
Query service forwards parsed query to ranking engine
3
Ranking Engine → Inverted Index
Fetch postings lists for query terms
Retrieve term frequency and document frequency for scoring
4
Inverted Index → Ranking Engine
Return postings with TF and DF
Postings include document IDs and term stats
5
Ranking Engine → Query Service
Compute TF-IDF/BM25 scores, rank documents, return top-k
Apply multi-field weights and return ranked results
6
Client Search → Indexing Service
Submit new or updated documents
Documents ingested asynchronously for indexing
7
Indexing Service → Kafka
Publish document indexing events
Kafka buffers and distributes indexing workload
8
Kafka → Inverted Index
Consume events and update index
Index updated asynchronously with replication

Practice

(1/5)
1. In a Redis Cluster using consistent hashing, at Step 4 of a key lookup, the client sends a request to a node that responds with a MOVED error. What happens next?
easy
A. The client updates its slot-to-node mapping and redirects the request to the correct node
B. The client retries the request on the same node until it succeeds
C. The node automatically forwards the request to the correct node without client involvement
D. The client drops the request and returns an error to the user

Solution

  1. Step 1: Identify MOVED error semantics

    MOVED indicates the key's hash slot is now served by a different node; client must update mapping.

  2. Step 2: Client reaction to MOVED

    Client updates its slot-to-node cache and retries request on the correct node (The client updates its slot-to-node mapping and redirects the request to the correct node).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Client updates mapping and retries -> correct node receives request [check]
Hint: MOVED error -> client updates mapping and retries correct node [OK]
Common Mistakes:
2. In the newsfeed system, at Step 4 the Delivery Worker reads a fan-out event from Kafka and attempts to deliver it to followers. What happens if a follower's device is offline at this step?
easy
A. Delivery Worker marks the message as sent but not delivered, queues for retry later
B. Delivery Worker drops the message to avoid blocking other deliveries
C. Delivery Worker retries immediately until the follower is online
D. Delivery Worker pushes the message to the follower's device cache directly

Solution

  1. Step 1: Trace Delivery Worker behavior at Step 4

    The Delivery Worker reads fan-out events from Kafka and attempts delivery. If the follower is offline, immediate retry (A) would block and reduce throughput. Dropping messages (C) causes data loss. Pushing directly to device cache (D) is impossible if offline.

  2. Step 2: Understand retry mechanism

    The system marks the message as sent but not delivered, queues it for retry later when the follower reconnects, ensuring eventual delivery without blocking.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Offline followers cause queued retries, not immediate blocking [check]
Hint: Offline followers cause queued retries, not immediate blocking [check]
Common Mistakes:
3. A web application experiences frequent database read spikes causing high latency. Which component best reduces this latency by serving repeated reads efficiently?
easy
A. Implement an in-memory cache layer like Redis to serve repeated reads
B. Use a relational database with read replicas to distribute load
C. Add more application servers to handle increased traffic
D. Use a message queue to buffer incoming read requests

Solution

  1. Step 1: Identify the latency cause

    High latency is due to repeated database reads causing load spikes, which read replicas help but still hit the database.

  2. Step 2: Recognize caching benefits

    An in-memory cache like Redis serves repeated reads from memory, drastically reducing latency and database load.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Cache serves repeated reads faster than replicas [check]
Hint: Cache repeated reads to avoid DB spikes [check]
Common Mistakes:
4. Without a distributed consensus system (like Paxos or Raft) coordinating leader election, what exactly breaks in a system designed for 99.999% availability?
medium
A. Clients receive stale data but system continues operating normally
B. Multiple nodes may believe they're leader simultaneously, causing conflicting writes and data corruption
C. The system automatically fails over to a backup leader without downtime
D. Leader election happens instantly with no impact on availability

Solution

  1. Step 1: Role of distributed consensus in leader election

    Consensus protocols ensure exactly one leader at a time, preventing split-brain scenarios.

  2. Step 2: Consequences of missing consensus

    Without consensus, multiple nodes may act as leader simultaneously, causing conflicting writes and data corruption, breaking availability guarantees.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    No consensus -> split-brain -> conflicting writes -> data corruption [check]
Hint: No consensus -> split-brain -> conflicting writes break availability [check]
Common Mistakes:
5. For a real-time ML inference system requiring minimal latency and high availability during model updates, which architecture is preferable and why?
medium
A. Monolithic model server that loads new models sequentially, blocking requests during reload
B. Single model server with periodic batch reloads and request queueing during reload
C. Blue-green deployment with two identical model serving clusters switching traffic atomically
D. Client-side model loading with periodic updates pushed to clients

Solution

  1. Step 1: Evaluate architectures for latency and availability

    Monolithic (A) and single server batch reload (C) block requests during reload, increasing latency. Client-side loading (D) adds complexity and inconsistent versions.

  2. Step 2: Understand blue-green deployment benefits

    Blue-green (B) runs two clusters; new model loads on inactive cluster, then traffic switches atomically, ensuring zero downtime and minimal latency impact.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Blue-green enables atomic switch with zero downtime [check]
Hint: Blue-green switches traffic atomically, avoiding reload blocking [OK]
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