Design Typeahead Suggestion/Autocomplete — System Design Interview Practice

Interview prompt

Design a low-latency typeahead service that returns relevant, safe, locale-aware suggestions for each prefix while absorbing billions of queries and frequent ranking updates.

• Define prefix normalization, language/locale, candidate eligibility, popularity/relevance windows, personalization, safety filtering, and ranking versions.
• Use compact prefix indexes and hot-prefix caches; explain updates, stale suggestions, long-tail behavior, and memory bounds.
• Separate query serving from asynchronous aggregation and index builds, with atomic snapshot publication and rollback.
• Explain abuse/privacy filtering, deletion, cache stampedes, regional failover, observability, and a safe fallback.

Requirements and scale assumptions

• Accept a prefix, locale, surface, and optional user context; return ranked suggestions with labels, scores, and index freshness.
• Ingest query/click feedback, blacklist unsafe or private terms, support popularity windows, and publish versioned index snapshots.
• Support tenant or locale isolation, deletion propagation, cache invalidation, replay, and fallback to popular static prefixes.
• Meet p95 suggestion latency under 50ms at the edge and keep index freshness within 15 minutes.
• Scale to billions of queries per day with extreme hot-prefix skew without a single hot key or unbounded synchronous work.
• Do not lose committed state; make retries and duplicate events safe.
• Degrade safely when downstream workers, caches, or external dependencies fail.
• 5B queries/day, 500k queries/second peak, and millions of indexed phrases
• Partition by the primary tenant, user, item, or geographic key and isolate hot partitions.
• Keep serving state bounded; retain raw events or durable records for replay and auditing.

• Peak scale: 5B queries/day; 500k queries/s peak — Capacity assumption that drives partitioning and backpressure.
• Latency target: edge p95 < 50ms; index freshness < 15m — User-facing budget for the primary request or read path.
• Durable boundary: Committed before async — Versioned suggestion data and policy lists are authoritative; caches and serving indexes are rebuildable.
• Async boundary: At-least-once workers — Keep Trie data structure for prefix matching, Cache popular queries, Precompute top suggestions off the synchronous path.

Key entities

• DocumentVersiondocumentId, sourceVersion, contentHash, aclVersion, language, updatedAt

  Canonical typeahead suggestion autocomplete content and access-policy version used for indexing.

• IndexGenerationgenerationId, sourceWatermark, schemaVersion, status, alias, createdAt

  Rebuildable typeahead suggestion autocomplete index generation that can be validated before an atomic alias swap.

• QuerySessionqueryId, tenantId, normalizedQuery, filters, generationId, nextCursor

  Auditable typeahead suggestion autocomplete query context with filters, cursor, and the generation used to answer it.

• RankingFeedbackqueryId, documentId, position, action, modelVersion, occurredAt

  Privacy-scoped typeahead suggestion autocomplete relevance signal for offline evaluation and ranking improvement.

Data flow

1. 1. Accept and authorize source changesThe typeahead suggestion autocomplete ingestion boundary validates content, tenant ownership, ACLs, versions, and idempotency before publishing a document change.
2. 2. Retrieve and rank candidatesThe query service applies authorization filters, retrieves from the active typeahead suggestion autocomplete generation, ranks within the latency budget, and returns generation freshness.
3. 3. Build a safe index generationPartitioned workers transform typeahead suggestion autocomplete documents, checkpoint progress, validate counts and ACL parity, then atomically swap the serving alias.
4. 4. Handle freshness and deletesTombstones and ACL changes propagate through the same pipeline so deleted or newly restricted typeahead suggestion autocomplete content is not left searchable.
5. 5. Measure relevance and recoverFeedback, query traces, lag, and failed partitions drive typeahead suggestion autocomplete ranking evaluation, replay, and bounded degraded behavior.

Deep dives and trade-offs

• ACL correctness and index generationsFilter typeahead suggestion autocomplete results by tenant and effective ACL, or prove the active generation contains the same policy snapshot. Build shadow generations and swap aliases atomically so partial reindexes are never visible. Keep source versions and ACL snapshots for replay when permissions or content change.
• Latency, cursors, and graceful degradationUse bounded candidate retrieval, stable sort keys, and generation-aware cursors for typeahead suggestion autocomplete pagination. Serve the last healthy generation when a new build is incomplete, but expose freshness and avoid silently violating authorization. Protect the query path with timeouts, circuit breakers, and per-tenant quotas.
• Relevance feedback without leakageSeparate typeahead suggestion autocomplete click or conversion signals from personally identifying data and honor retention or deletion requests. Evaluate ranking by query class and tail latency, not only aggregate click-through. Use replayable query sets and staged model or synonym changes before production rollout.
• Synchronous indexing versus queued indexingCommit the source version synchronously and index asynchronously with a visible freshness contract. Waiting for index mutation makes writes fragile and cannot guarantee immediate consistency at scale.
• Denormalized ACL fields versus filter-time checksDenormalize safe, versioned authorization facts when it meets the policy model, while retaining a source-of-truth check for sensitive results. Stale permissions can become a data-leak path if index updates are treated as authoritative.
• Lexical, vector, or hybrid retrievalStart with the retrieval method that matches the corpus and latency budget, then add hybrid ranking behind an experiment and rollback boundary. Adding embeddings without freshness, explainability, or access-control design increases cost without improving user trust.