Design Best-Seller Rankings

A large online store wants a "Best Sellers" page for every category in its catalog, from broad ones like Kitchen down to narrow ones like Milk Frothers, plus a badge on product pages such as "#3 in Milk Frothers".

The catalog has about 100 million products in a tree of 50,000 categories, and the store takes tens of millions of orders a day, with huge spikes during sale events. Rankings should reflect recent sales, be refreshed every hour, and be hard to game with fake orders. Cancelled and returned orders should not count.

In 45 minutes, agree on what "best seller" means, size the order stream, design how sales are counted and turned into per-category rankings every hour, and how millions of shoppers read those rankings cheaply.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Commerce & Payments · problem 28 of 70

Ask before you design. Try answering each yourself, then compare.

1. What does best seller mean exactly?
   Typical answer

   Units sold, weighted toward recent hours, over roughly the last 24 hours. Revenue-based ranking is a follow-up.

2. Does a sale count in parent categories too?
   Typical answer

   Yes. A frother sale counts in Frothers, Coffee and Kitchen.

3. How many products per ranking?
   Typical answer

   Top 100 per category; the page shows 50 at a time.

4. What scale should we plan for?
   Typical answer

   About 50 million orders a day with 3 line items each, 5x spikes during sale events, and 100 million products.

5. How fresh must rankings be?
   Typical answer

   Recomputed every hour; a ranking up to 90 minutes old is acceptable.

6. How do cancellations, returns and fraud affect counts?
   Typical answer

   Cancellations and returns subtract. Orders flagged as fraudulent or from a single buyer buying unusual quantities are excluded or capped.

Requirements

Functional

• Maintain the top 100 best-selling products for each of 50,000 categories, including parent categories.
• Refresh rankings every hour from the order stream, accounting for cancellations and returns.
• Serve a category's ranking page and a product's best rank badge.
• Exclude or cap suspicious orders.

Non-functional

• Ranking page and badge reads p99 under 50 ms at 100,000 reads per second.
• New rankings published within 15 minutes after each hour ends.
• Ingest 150 M order lines a day with peaks of 10,000 per second.
• Rankings are swapped atomically per run; a failed run leaves the previous hour live.

Out of scope

• Personalised rankings and recommendations.
• Search ranking.

Back-of-the-envelope estimates

• Order lines: 50 M orders × 3 lines = 150 M a day ≈ 1,700 per second, about 9,000 per second during sale peaks.
• Active products: only products sold in the last 24 hours matter, typically a few million out of 100 M, so each hourly run handles about 5 M product scores, not 100 M.
• Fan-out to categories: with an average depth of 5, 5 M products produce about 25 M (category, product, score) pairs, small enough for one Spark job of a few minutes.
• Hourly counts: 5 M products × 24 buckets × ~16 B ≈ 2 GB of live state.
• Output: 50,000 categories × 100 entries × ~16 B ≈ 80 MB per run; trivially cached.
• Reads: about 1 B category and product page views a day ≈ 12,000 per second, 60,000 at peak, served from CDN and cache.

The sparsity of recent sales and the tiny output make an hourly batch over pre-counted data cheap; the main work is clean, deduplicated counting.

API

GET /v1/bestsellers/{categoryId}?limit=50&offset=0
    -> {categoryId, generatedAt, runId, items:[{rank, productId, change}]}
GET /v1/products/{productId}/rank
    -> {bestRank: {categoryId, rank}, generatedAt}
(internal) OrderLineEvent {lineId, orderId, productId, units, ts, type: SALE|CANCEL|RETURN}

Responses carry the runId they came from, so pages and badges built from the same run agree, and caches can be keyed by run.

Data model

• Order events on a stream keyed by product_id, with line_id as a dedupe key.
• Hourly counts (wide-column store): (product_id, hour) -> units_net, orders, distinct_buyers, with a 30-day TTL. Partitioned by product, written by upsert so replays are safe.
• Catalog (relational, read-only here): products(product_id, leaf_category_id) and categories(category_id, parent_id), loaded into memory by the ranker as a parent map.
• Ranking store (key-value): rank:{runId}:{categoryId} -> [productId...], badge:{runId}:{productId} -> (categoryId, rank), and a single pointer current_run. Old runs expire after a day.

High-level design

Counting: when an order is placed, cancelled or returned, the Order Service publishes an order-line event to the Order Events stream, keyed by product. The Sales Counter (a streaming job) drops duplicate line IDs, applies fraud caps such as counting at most a few units per buyer per product, and adds the net units into the current hour bucket. Every minute it flushes upserts to Hourly Counts.

Ranking: a few minutes after each hour, the Hourly Ranker reads all products with sales in the last 24 hours, computes a recency-weighted score, looks up each product's category path in the Catalog, and emits the score to every ancestor category. A top-k per category with a bounded heap produces the lists, plus each product's best rank. The job writes everything under a new run ID into the Ranking Store, verifies counts, then flips the current_run pointer.

Reading: shoppers hit the CDN, which caches ranking pages for a few minutes. Misses go to the Ranking API, which reads through the Ranking Cache keyed by run, and from the store on a miss. Product pages fetch the badge the same way.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Defining a score that resists noise

Plain units over 24 hours makes rankings jump at the boundary when a big hour drops out of the window. Use hourly buckets with an exponential decay, for example weight 0.9 per hour of age, so the score fades smoothly. Count net units after cancellations and returns, and cap each buyer's contribution per product so one bulk purchase cannot crown a product. Require a minimum number of distinct buyers before a product can rank in a small category. Small categories can use a longer window, such as 7 days, to avoid rankings built on a handful of sales.

Top-k across a category tree

Expand each product into its ancestors during the ranking job, not in the stream: the tree changes, and doing it hourly in batch means a recategorised product moves cleanly in the next run. For each category keep a min-heap of size 100; push a product's score, and pop the smallest when the heap overflows. Distributed, this is a map step emitting (category, score, product) and a reduce step per category. Very broad categories receive millions of entries, so first compute partial top-100 lists per worker and merge them, which is exact because any global top-100 item is in its worker's local top-100.

Publishing without half-written rankings

Write each run under its own run ID, never in place. After the job finishes, run checks: every category with sales has a list, list lengths are sensible, and the top products have not shifted by an implausible amount compared to the previous run. Only then update the single current_run pointer, which readers fetch with a short TTL. Rolling back is just pointing at the previous run. Caches and the CDN key on run ID, so a new run naturally bypasses stale entries without mass invalidation.

Counting at sale-event peaks

During a flash sale, a single deal product can take thousands of orders a second, all landing on one stream partition. Pre-aggregate in the order service or in a combiner stage, sending per-product counts every few seconds instead of every line, and spread hot product keys across sub-partitions that the counter merges per minute. Because the ranking only needs hourly totals, a minute of buffering costs nothing in freshness while reducing writes to the counts store by orders of magnitude.

Failure modes

• If the ranking job fails or its checks fail, the pointer stays on the previous run, pages show slightly older rankings, and on-call is alerted.
• If the Sales Counter falls behind, the ranker waits up to a deadline for the hour to be complete, then runs with what it has and marks the run partial.
• If the counts store loses data, replay the order stream from its retention window, since counts are idempotent upserts.
• If the ranking cache is flushed, the store serves reads at a few thousand QPS while the cache refills; the CDN absorbs most traffic.
• If a category is restructured mid-day, the next run uses the new tree; badges for moved products update an hour later.

Core algorithm in code

from collections import defaultdict
import heapq

WINDOW_HOURS = 24
DECAY = 0.9


class SalesCounter:
    """Units sold per product per hour, deduplicated by order line."""
    def __init__(self):
        self.hourly = defaultdict(lambda: defaultdict(int))   # product -> hour -> units
        self.seen = set()

    def record(self, line_id, product, hour, units):
        if line_id in self.seen:          # at-least-once delivery from the order stream
            return
        self.seen.add(line_id)
        self.hourly[product][hour] += units

    def score(self, product, now_hour):
        total = 0.0
        for hour, units in self.hourly[product].items():
            age = now_hour - hour
            if 0 <= age < WINDOW_HOURS:
                total += units * DECAY ** age
        return total


def ancestors(category, parents):
    while category:
        yield category
        category = parents.get(category)


def rank(counter, parents, product_category, now_hour, k):
    heaps = defaultdict(list)             # category -> min-heap of (score, product), size <= k
    for product in counter.hourly:
        s = counter.score(product, now_hour)
        if s <= 0:
            continue
        for cat in ancestors(product_category[product], parents):
            h = heaps[cat]
            if len(h) < k:
                heapq.heappush(h, (s, product))
            elif s > h[0][0]:
                heapq.heapreplace(h, (s, product))
    return {cat: [p for s, p in sorted(h, reverse=True)] for cat, h in heaps.items()}


parents = {"Espresso Machines": "Coffee", "Frothers": "Coffee", "Coffee": "Kitchen", "Kitchen": None}
product_category = {"barista-pro": "Espresso Machines", "mini-press": "Espresso Machines",
                    "froth-200": "Frothers", "whisk-mini": "Frothers"}
c = SalesCounter()
for line, prod, hour, units in [
    ("o1-1", "barista-pro", 100, 40), ("o2-1", "mini-press", 110, 25), ("o3-1", "froth-200", 118, 30),
    ("o4-1", "whisk-mini", 119, 12), ("o4-1", "whisk-mini", 119, 12),   # duplicate delivery
    ("o5-1", "mini-press", 119, 10), ("r9-1", "froth-200", 119, -20),  # a bulk return
]:
    c.record(line, prod, hour, units)
for cat, top in sorted(rank(c, parents, product_category, now_hour=120, k=2).items()):
    print("%-18s %s" % (cat, top))
print("scores:", {p: round(c.score(p, 120), 1) for p in product_category})

Trade-offs

• Hourly batch ranking is simple, cheap and verifiable but is up to 90 minutes stale; streaming top-k is fresher but harder to validate.
• Exponential decay smooths rankings but makes the score harder to explain to sellers than a plain 24-hour count.
• Per-buyer caps and distinct-buyer thresholds resist gaming but can undercount genuine bulk demand.
• Run-versioned keys give atomic switches and easy rollback but double storage briefly and need expiry.
• Pre-aggregating hot products in the stream reduces writes but delays counts by seconds.

What a strong answer shows

• Defines the ranking score precisely, including window, decay, returns and anti-gaming rules.
• Uses sparsity: only recently sold products are ranked, not the whole catalog.
• Expands sales to ancestor categories and computes top-k with bounded heaps or a mergeable partial top-k.
• Separates continuous counting from hourly ranking and makes counting idempotent.
• Publishes rankings atomically with versioned runs and a pointer, with validation and rollback.
• Serves reads from CDN and cache with run-keyed entries.

Mistakes to avoid

• Sorting all 100 million products every hour.
• Maintaining a live sorted set per category updated on every order, which explodes writes across ancestors and hot keys.
• Overwriting ranking lists in place so readers see a mix of two runs.
• Ignoring returns, cancellations and bulk or fake orders.
• Hard-coding category paths into the stream so tree changes require reprocessing.

Follow-ups to expect

• How would you add a 'Movers and Shakers' list? (Compare this run's score with the score 24 hours earlier; rank by relative gain with a minimum volume.)
• How would you make rankings per country? (Add region to the count key and the ranking key; most categories are sparse, so share small ones.)
• How would you refresh every 5 minutes instead of hourly? (Incremental top-k over changed products only, or streaming top-k with periodic full recompute.)
• Sellers complain a product vanished from the list. How do you debug it? (Store run inputs and per-product score breakdowns for a few days.)

Practice next