Bird
Raised Fist0

Search Ranking and Relevance - TF-IDF, BM25 Intuition

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/6
Query Service

Receives user query

User submits query 'distributed systems'

Protocol:HTTP Request
BeforeNo active query processing for this user
AfterQuery Service has parsed and validated the query
Ranking Engine

Requests postings for query terms

Sends RPC to Inverted Index for 'distributed' and 'systems'

Protocol:RPC Call
BeforeRanking Engine has query terms but no document data
AfterRanking Engine received document lists for query terms
Inverted Index

Looks up postings lists

Retrieves document IDs and term frequencies for query terms

Protocol:Index Lookup
BeforeInverted Index has up-to-date term postings
AfterReturned postings lists to Ranking Engine
Metadata Store

Provides document metadata

Returns document lengths and corpus statistics for scoring

Protocol:DB Query
BeforeMetadata Store holds document stats but not yet queried
AfterRanking Engine has metadata needed for TF-IDF/BM25
Ranking Engine

Computes TF-IDF and BM25 scores

Ranks documents based on term frequency and inverse document freq

Protocol:Internal computation
BeforeRanking Engine has postings and metadata
AfterRanking Engine outputs ranked document list to Query Service
Query Service

Returns ranked results to user

Sends top documents back as HTTP response

Protocol:HTTP Response
BeforeQuery Service waiting for ranking results
AfterUser receives ranked search results
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────┐
│    Query Service      │
│  (receives user query)│
└──────────┬────────────┘
           │ HTTP Request
           ▼
┌───────────────────────┐
│   Ranking Engine      │
│ (computes TF-IDF/BM25)│
└──────────┬────────────┘
           │ RPC Call
           ▼
┌───────────────────────┐
│   Inverted Index      │
│ (stores term→doc ids) │
└──────────┬────────────┘
           │ Index Lookup
           ▼
┌───────────────────────┐
│  Metadata Store       │
│ (document metadata)   │
└──────────┬────────────┘
           │ DB Query
           ▼
┌───────────────────────┐
│  Indexing Service     │
│ (updates index & meta)│
└───────────────────────┘
Design Rationale

The Search Ranking and Relevance system processes user queries by first receiving them in the Query Service. The Ranking Engine then requests postings lists from the Inverted Index for each query term. The Inverted Index returns document IDs and term frequencies, which the Ranking Engine combines with document metadata from the Metadata Store. Using TF-IDF and BM25 scoring formulas, the Ranking Engine ranks documents by relevance. Finally, the Query Service returns the ranked results to the user. The Indexing Service runs asynchronously to update the Inverted Index and Metadata Store with new documents, ensuring fresh data for queries. This vertical flow emphasizes separation of concerns and efficient retrieval for relevance scoring.

Primary Focus

✓

Practice

(1/5)
1. A web application requires multiplexing multiple requests over a single TCP connection to reduce latency. Which HTTP version feature primarily enables this?
easy
A. HTTP/3 using UDP datagrams without multiplexing
B. HTTP/1.1 pipelining with multiple TCP connections
C. HTTP/2 multiplexing streams over one TCP connection
D. HTTP/1.1 using separate TCP connections per request

Solution

  1. Step 1: Identify multiplexing capability

    HTTP/1.1 uses pipelining but suffers head-of-line blocking; HTTP/2 introduces multiplexing streams over a single TCP connection, allowing concurrent requests without blocking.

  2. Step 2: Eliminate other options

    HTTP/3 uses UDP and multiplexing but is not the primary feature here; HTTP/1.1 with multiple TCP connections increases overhead and latency.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    HTTP/2 multiplexes streams on one TCP connection [check]
Hint: HTTP/2 multiplexes streams on one TCP connection [check]
Common Mistakes:
2. A high-traffic e-commerce platform expects sudden spikes of 1 million orders per minute. Which component best handles decoupling order intake from downstream inventory updates to maintain responsiveness?
easy
A. An in-memory cache with TTL eviction to buffer incoming orders
B. A relational database with strong ACID transactions for immediate consistency
C. A distributed message queue with partitioning and durable storage
D. A REST API gateway that throttles requests to downstream services

Solution

  1. Step 1: Identify decoupling need

    Immediate consistency via relational DB (A relational database with strong ACID transactions for immediate consistency) blocks on writes, causing latency spikes. In-memory cache (An in-memory cache with TTL eviction to buffer incoming orders) lacks durability and ordering guarantees. API gateway throttling (A REST API gateway that throttles requests to downstream services) limits throughput but doesn't decouple processing.

  2. Step 2: Durable queue with partitioning

    A distributed message queue (A distributed message queue with partitioning and durable storage) buffers spikes, partitions workload, and guarantees durability, enabling asynchronous downstream processing.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Distributed queue partitions spikes, ensures durability, decouples processing [check]
Hint: Use durable queues to buffer spikes and decouple processing [OK]
Common Mistakes:
3. Given the need for zero data loss during failover and minimal downtime, which architecture is best suited for GitHub's database cluster?
medium
A. Asynchronous replication with delayed failover to reduce load
B. Read-only replicas with manual failover triggered by monitoring
C. Multi-master replication with eventual consistency
D. Synchronous replication with consensus-based leader election

Solution

  1. Step 1: Evaluate replication and failover requirements

    Zero data loss requires synchronous replication; minimal downtime requires automated leader election.

  2. Step 2: Compare architectures

    Asynchronous replication (A) risks data loss; multi-master (C) complicates consistency; manual failover (D) increases downtime.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Synchronous replication + consensus election ensures data safety and fast failover [check]
Hint: Synchronous replication ensures no data loss during failover
Common Mistakes:
4. Without the transaction log (WAL) in a relational database, what exactly breaks during a crash recovery scenario?
medium
A. Committed transactions may be lost or partially applied, causing data inconsistency
B. The database cannot enforce foreign key constraints during recovery
C. The database will deadlock on concurrent transactions after restart
D. The query optimizer will choose inefficient plans after recovery

Solution

  1. Step 1: Role of transaction log (WAL)

    The WAL records all changes before commit to enable redo/undo during crash recovery.

  2. Step 2: Consequence of missing WAL

    Without WAL, committed transactions might not be replayed, causing partial or lost updates and inconsistency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Missing WAL -> lost committed transactions, inconsistent state [check]
Hint: WAL ensures durability; without it, committed data can vanish [check]
Common Mistakes:
5. At 10x scale of global traffic, which component in the BGP-based routing infrastructure is most likely to fail first, and why?
hard
A. Edge routers, because their CPU cannot handle the increased packet forwarding rate
B. Route reflectors, because they become overwhelmed maintaining full routing tables and propagating updates
C. Network monitoring systems, because data volume exceeds processing capacity causing delayed alerts
D. Client devices, because they cannot process rapid route changes at scale

Solution

  1. Step 1: Identify bottleneck at scale

    Edge routers handle packet forwarding at line rate; at 10x traffic, their CPU and forwarding ASICs are stressed first.

  2. Step 2: Evaluate other components

    Route reflectors (A) scale better with hierarchical design; monitoring systems (C) can be scaled horizontally; client devices (D) are downstream and less critical for routing stability.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Edge routers' CPU overload causes first failure at 10x traffic [check]
Hint: Edge routers hit CPU limits first at massive scale [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