Distributed Search
Maintain a near-real-time searchable index over mutable documents with permission checks, deletion semantics and safe rebuilds.
Maintain a near-real-time searchable index over mutable documents with permission checks, deletion semantics and safe rebuilds. This worked design targets SDE-3; the scale figures below are exercise assumptions, not claims about a named company's implementation.
Clarify the prompt
| Ask the interviewer | Decision to record |
|---|---|
| Which corpus, ranking signals and query grammar? | Web search and product search have different ingestion scope. |
| What is the accepted update-to-search delay? | Acknowledged source writes do not imply immediate index visibility. |
| Are ACL revocations and deletes allowed to lag like ordinary edits? | Usually they need stricter enforcement. |
Requirements and scope
The core deliverable is: Maintain a near-real-time searchable index over mutable documents with permission checks, deletion semantics and safe rebuilds. The first design implements the APIs below and the state constraints in the data model. Agree the latency, freshness, retention and failure policy before adding infrastructure. Every successful acknowledgment must have an explicit meaning: accepted intent, committed state or completed external work. These are separate milestones.
Capacity and bottleneck reasoning
Assume one billion 2 KB documents: 2 TB raw before postings, stored fields and replicas. At 50,000 updates/s and a 10-second freshness target, at least 500,000 updates may be in flight. Query fanout to 100 shards at 1,000 QPS means 100,000 shard requests/s.
Keep average and peak demand separate. Add replication, indexes, retries and safety headroom to raw arithmetic before selecting capacity. Load-test the busiest ownership key and recovery traffic as well as uniform happy-path throughput.
APIs and data model
- PUT /documents/{id} {version,body} -> authoritative source version
- GET /search?q=...&cursor=... -> ranked authorized hits and index watermark
- POST /indexes/rebuild -> generation and validation status
document(doc_id PK,version,tenant,acl_version,deleted_at)
change(event_id,doc_id,version,payload_or_tombstone)
index_generation(name,source_checkpoint,alias); shard(doc_hash_range,replicas)Authorize resource ownership at the API boundary; do not trust IDs or state supplied by a client. Bind retry identity to the caller and payload for mutating operations. Reject an incompatible replay instead of returning an unrelated stored result.
Component relationships
Read the diagram
Follow the labeled relationship panels; they are separate directed paths, not one global timeline.
Step-by-step design
1. Establish the authority
Ingest from an authoritative source or crawler into a durable change log. Partition by document identity and apply only newer versions; tombstones must outlive plausible late updates so deleted documents are not resurrected.
2. Make retries and concurrent work safe
Tokenize into inverted indexes with immutable segments and background merges. Search coordinators fan out to bounded shards, merge top-K candidates and enforce deadlines. State whether partial shard results are allowed and mark them explicitly.
3. Scale and recover the critical path
Recheck current access for sensitive hits at serving time. Build a new index generation from a snapshot plus change replay, compare counts and sampled queries at a common checkpoint, then atomically switch the alias and retain a rollback generation.
Worked request and concurrency example
Document D changes from version 4 to 5, then is deleted at version 6. Delivery order is 5,6,4. The index accepts 5, records the tombstone for 6 and rejects 4. A user whose access is revoked must not receive a stale sensitive hit merely because the index has not refreshed. During a reindex, snapshot checkpoint C plus every later change through cutover checkpoint H must be incorporated before alias switch.
Failure and recovery walkthrough
A shard times out. Either fail the search or return explicitly partial results with the affected scope; never describe an incomplete result as exhaustive. A failed rebuild leaves the active alias unchanged, and rollback must preserve current permission/deletion filters.
Read the diagram
This numbered trace follows one scenario; explain the durable evidence at each transition.
Decisions and alternatives
| Decision | Trade-off |
|---|---|
| Alternative 1 | More shards reduce per-shard data but amplify query fanout and tail latency. Routing by tenant limits fanout while creating hot-tenant placement challenges. |
| Alternative 2 | Frequent refresh lowers visibility lag at higher segment/merge cost. A stricter deletion path can enforce privacy without forcing all updates to be synchronous. |
Operational contract
Track source-to-index lag, tombstone age, shard p99 latency, merge debt, relevance regressions and unauthorized-hit tests. Rehearse reordered updates, shard loss and index recreation from source checkpoints.
Choose alert thresholds from the agreed user-facing objective. Assign an owner for stuck work and a replay/repair procedure that preserves the original business identity. Bound queue depth, concurrency and recovery throughput so an outage does not produce an uncontrolled catch-up burst.
Foundation, senior and staff depth
- Foundation: explain the user action, model, first complete request and the correctness constraint without relying on a list of technologies.
- Senior: defend this lesson's partition/coordination boundary, capacity estimate and failure recovery; explain the cost of the rejected alternative.
- Staff: identify failure domains and operational ownership, stage a rollout with measured guardrails, and state when rollback stops being safe.
Practice before revealing the answer
Spend 45 minutes: 5 clarifying scope, 7 on capacity/APIs/state, 12 on the first architecture, 15 on the concurrency and failure examples, and 6 on trade-offs and operations. Draw your own design before comparing it with this chapter.
Question: How does a CDC stream avoid resurrecting a deleted document?
Show answer and explanation
Answer: Carry a monotonically comparable source version with both updates and tombstones. Apply only newer versions and retain deletion evidence long enough to cover replay and retention policies; event arrival time alone is insufficient.
Verification and rollout
Reproduce the worked example using two concurrent actors or a repeated request where applicable. Inject the stated failure between the durable transition and its acknowledgment; verify the resulting state and user-visible outcome. For read/ML paths, test missing or stale dependencies and verify the documented fallback still enforces permissions. Use a small canary, compare correctness and user-facing latency with the baseline, and roll back when those guardrails regress. Do not use an average throughput number as evidence that a tail-latency target is met.
Primary technical reference
Official documentation for the mechanism used in this exercise. This lesson is an original interview design, not a description of undisclosed company internals.
Related study
Before this design, review these mechanisms and identify which owns the critical state transition:
Use the Interview Playbook to adapt the depth and timing, then return to the question breakdown overview.
How does a CDC stream avoid resurrecting a deleted document?
Your design draft
Clarify assumptions, explain your approach, and test the difficult cases. Save your draft, then compare it with the study notes.
Self-review checklist
Self-guided practice. Automated AI feedback and code execution are not connected.