Top K Elements: App Store Rankings, Amazon Bestsellers — System Design Interview Practice

Interview prompt

Design a Top-K ranking system that continuously tracks changing item scores and serves the best K items quickly for use cases such as App Store rankings, Amazon bestsellers, or trending content.

• Define the ranking window, score freshness, tie-breaking, and what consistency users need from a result.
• Separate fast candidate updates from the read-optimized Top-K materialization and explain when a heap is insufficient.
• Handle hot keys, high-cardinality partitions, late events, score corrections, and ties without unbounded rescans.
• Keep experimentation, historical analytics, and full result exports asynchronous to protect the serving path.

Requirements and scale assumptions

• Ingest score events for items, such as installs, sales, votes, views, or weighted engagement.
• Return the Top-K items for a named scope, category, region, or time window with scores and rank positions.
• Refresh rankings as events arrive and expose the observed timestamp and ranking version.
• Support item eligibility, suppression, deletion, score corrections, and deterministic tie-breaking.
• Target p95 under 100 ms for a cached Top-K read and under 2 seconds for normal score-to-ranking freshness.
• Do not lose accepted score events; consumers must be idempotent under at-least-once delivery.
• Serve predictable results during bursts, hot categories, large K values, and partial worker or cache failures.
• A ranking projection may be eventually consistent, but its window, version, freshness, and fallback behavior must be explicit.
• 100 million eligible items, 10,000 ranking scopes, and 1 million score events per second at peak.
• Most reads request K <= 100, while a small number of export clients request larger pages through an asynchronous job.
• Rankings include hourly, daily, and rolling-7-day windows; event volume and score distributions vary significantly by scope.
• Retain raw events for replay and auditing, but keep serving state bounded to active items and configured windows.

• Peak event rate: ~1M/s — Score updates arrive in bursts; partition ingestion by scope and item while isolating hot scopes.
• Serving latency: p95 <=100ms — Read a precomputed Top-K snapshot instead of sorting all eligible items per request.
• Ranking freshness: <=2 seconds — The target for ordinary scopes; return version and observedAt when a projection is behind.
• Default K: K <=100 — Bound the synchronous response and route large result sets through paginated or asynchronous exports.

Key entities

• ScoreEventeventId, itemId, scoreDelta, source, occurredAt, sequence

  Versioned score update for an item.

• RankingRuleruleId, scope, window, weights, tieBreak, version

  Rule defining score calculation and tie-breaking for a ranking scope.

• TopKSnapshotscope, window, k, items, watermark, generatedAt

  Materialized ranking response with freshness and score versions.

• WindowStatescope, window, bucket, itemScores, retentionUntil, status

  Bounded time-window state used to expire and recompute scores.

Data flow

1. 1. Accept score updatesThe event API validates item, scope, timestamp, rule version, and idempotency, then appends a score event.
2. 2. Maintain window statePartitioned workers apply deltas to time buckets, expire old contributions, and isolate hot items or scopes.
3. 3. Compute Top-K candidatesProjectors combine per-item scores with a heap, sorted set, or bounded candidate structure and apply deterministic ties.
4. 4. Publish ranking snapshotsA snapshot writer atomically publishes the best K items with score versions, watermark, and freshness.
5. 5. Serve and rebuildThe ranking API serves the latest acceptable snapshot while replay jobs recalculate after rule changes, late events, or drift.

Deep dives and trade-offs

• Window expiration and score semanticsFor the continuously updated Top-K ranking system, every ranking snapshot must identify its rule, window, watermark, and deterministic tie-break semantics. Design for the failure case where late events, score bursts, rule changes, and hot items must not make rank results silently inconsistent; keep retries, versions, and repair state explicit. Expose freshness, version, lineage, or audit metadata so operators and clients can distinguish current, pending, and degraded state.
• Hot-item candidate maintenanceFor the continuously updated Top-K ranking system, every ranking snapshot must identify its rule, window, watermark, and deterministic tie-break semantics. Keep this concern off unrelated request paths and partition it by the continuously updated Top-K ranking system access key. Expose freshness, version, lineage, or audit metadata so operators and clients can distinguish current, pending, and degraded state.
• Snapshot freshness and rebuildFor the continuously updated Top-K ranking system, every ranking snapshot must identify its rule, window, watermark, and deterministic tie-break semantics. Keep this concern off unrelated request paths and partition it by the continuously updated Top-K ranking system access key. Expose freshness, version, lineage, or audit metadata so operators and clients can distinguish current, pending, and degraded state.
• Exact Top-K versus approximate candidatesUse exact per-scope state where K and update rate fit, and bounded sketches/candidates where high-volume use cases tolerate approximation. Approximation without an error or freshness contract undermines trust in the ranking.
• Push projection versus query-time computationCompute snapshots asynchronously and serve them from a low-latency index; reserve query-time work for narrow filters. Recomputing all scores on each read causes tail latency and duplicate work.
• Short windows versus recompute costUse bucketed windows and incremental expiry, with periodic rebuilds for correctness. Very short buckets increase write overhead; no rebuild path lets numerical drift accumulate.