Interview concept

Google-Scale Search Indexing and Autocomplete System Design

Asked of: Software Engineer

Last updated

What's being tested

Interviewers are probing the candidate’s ability to design a low-latency, high-throughput search indexing and autocomplete service at scale: data structures for prefix/substring lookup, ingestion/update propagation, sharding/replication, caching, and operational tradeoffs (consistency, latency, cost). They want concrete capacity calculations, clear separation between read-path and write-path, and reasoning about failure modes and latency budgets relevant to a production backend engineer.

Core knowledge

  • Prefix vs full-text: prefix search (autocomplete) favors tries / radix trees / FSTs for O(length) lookup; inverted index supports full-text and substring queries with posting lists and term normalization.

  • Finite State Transducers (FSTs): compact, sorted-string keyed structure that maps prefixes to posting lists or suggestion IDs; memory-efficient for large vocabularies via shared suffixes and node compression.

  • Compressed trie / Patricia trie: reduces node count by coalescing single-child chains; useful when many long keys share long common paths to save RAM and cache lines.

  • Index size estimate: approximate nodes ≈ sum(lengths of unique strings). If V=100M strings, average length L=8, nodes≈800M; with node storage S≈16–40 bytes, RAM ~12–32 GB per 100M keys (use compression & disk-backed stores beyond that).

  • Serving storage choices: in-memory Redis/custom FST for ultra-low-latency hot prefixes; SSD-backed LevelDB/RocksDB/Bigtable for large cold indices. Hybrid caches reduce cost.

  • Sharding & routing: shard by hashed prefix range, by first N characters, or by high-frequency prefixes; use consistent hashing + routing layer (small proxy or gRPC-based) to map queries to shards.

  • Replication & consistency: replicate shards for availability; choose eventual consistency for suggestions if fresh results are not strictly required, or synchronous replication for strong consistency at higher latency/cost.

  • Update propagation: batch rebuilds (cheap, simpler), near-real-time streaming updates (using a change-log + log compaction), or hybrid: immediate hot-prefix update + periodic reindex. Tradeoff: freshness vs serve complexity.

  • Latency & capacity math: dimension by QPS and average processing time: required servers ≈ QPS * latency_per_request / acceptable_cpu_latency; aim for interactive p50 < 20ms and p99 < 100ms end-to-end.

  • Typo tolerance: implement edit-distance-aware suggestions using BK-trees, k-gram indexes, or precomputed fuzzy variants; runtime cost grows quickly with edit radius — prefer shallow correction or client-side heuristics for high QPS.

  • Ranking & personalization (service level): separate the candidate generation (fast, structural) from re-ranking (slower, feature-rich). Keep re-rank cheap or optional for first-page suggestions to meet latency budgets.

  • Caching strategies: multi-layer cache: CDN/browser → edge autocomplete cache → shard-local in-memory cache (LRU) → backing store. Use bloom filters to reject misses and reduce disk IOPS.

  • Observability & SLAs: instrument QPS, p50/p99 latency, index lag (time from source update to visible), error rates, cache hit ratio, and per-prefix hotness; set SLOs (e.g., 99.9% availability, p99 < 100ms).

Worked example — "Design an autocomplete service supporting 10k QPS and real-time updates"

First 30s: clarify constraints — target latency (p50/p99), suggestion depth (top-5), dataset size (unique queries and total vocabulary), update rate (writes/s), and freshness SLA. Skeleton: (1) choose candidate-generation DS (compressed FST or radix trie) stored in-memory for hot prefixes and SSD-backed for full index; (2) sharding scheme by prefix ranges to distribute QPS; (3) update pipeline: source change-log → streaming processor → per-shard incremental update + periodic full compaction; (4) caching/proxy layer to absorb peaks and return cold results quickly. Key tradeoff: real-time updates vs memory/CPU — maintain a small in-memory delta buffer for new entries (fast) and merge into main FST asynchronously to avoid full rebuilds. If I had more time, I’d sketch the RPC protocol (gRPC + protobuf), backpressure behavior for bursts, and a migration plan for rolling index compactions with zero downtime.

A second angle — "Add typo-tolerance and personalization while keeping p99 < 150ms"

Same core separation (candidate gen vs re-rank) but constraints shift: fuzzy matching increases candidate explosion. Practical choices: restrict fuzzy corrections to top-k frequent prefixes using a bloom-filter-guarded fuzzy index or precompute common 1-edit variants for hot keys to keep lookup O(1) for those. Personalization should happen in the re-rank stage with a light-weight feature set cached per user to avoid remote calls; heavy ML rerankers run asynchronously for offline metrics. Emphasize budgets: cap candidate set size and re-ranker time, and fall back to structural, non-personalized suggestions when profile data is missing or late.

Common pitfalls

Pitfall: Designing a single monolithic in-memory index and assuming it scales linearly — this ignores memory limits, GC pauses, and shard hotness. Prefer sharding, compressed structures, and hybrid memory/disk approaches.

Pitfall: Trying to support arbitrary fuzzy edits at query time for all prefixes — the candidate explosion kills latency and CPU. Instead, precompute common variants for hot prefixes and use bloom filters or k-gram indexes for cold ones.

Pitfall: Overfocusing on perfect freshness — synchronous updates for every write will drastically raise cost and latency; interviewers prefer articulated tradeoffs (delta buffers, TTLs, or eventual consistency) and a rollback/backpressure plan.

Connections

Interviewers may pivot to adjacent topics: ranking pipelines (how candidates are scored and reranked), streaming ingestion (change-data-capture and exactly-once semantics), or capacity & cost optimization (autoscaling policies and multi-tier storage). Be prepared to tie your design decisions to these areas without diving into ML model internals.

Further reading

Related concepts