Price Tracker

The problem

"Design a price tracker." Users paste a product link from an online shop, set a target price, and get an alert when the price falls to it or lower. Each product page shows a chart of its past prices.

This practice problem reuses the pattern of the Web Crawler: fetchers that take their work from a queue, and a gap between requests to one site. What's new: you check only what people watch, the popular products more often; you keep every price change; one drop can alert thousands; and many shops offer an official API. Park search across all shops (an index of product titles, as in Search Engine) and comparing one product across shops.

The numbers

From the interviewer: 50 million watches on 10 million different products. Checking every product once an hour is 10 million × 24 = 240 million checks a day; over 86,400 seconds that is about 2,800 a second, 7× the Web Crawler's 400.

Check per product, not per watch: ten people watching the same TV need its price once. Counting the 50 million watches instead would be about 14,000 a second.

Crawl priority: by watcher count

Watchers are very uneven: a few products have thousands, most have one or two. Give each product a priority from its watcher count:

watchers   products    check every   checks a day
1,000+     10,000      10 min        1.44 million
10–999     990,000     1 hour        23.76 million
1–9        9 million   1 day         9 million

That is 34.2 million checks a day, about 400 a second, 7× fewer than hourly for all. The 10,000 most watched products hold at least 10 million of the 50 million watches, and they are checked 6× more often than before. A scheduler keeps each product's priority and next check time, hands due products to the checkers, and updates the priority as watches come and go; a product nobody watches leaves the crawl.

Checking everything every 10 minutes would be 1.44 billion checks a day, about 17,000 a second, 40× the plan, mostly on products one person watches. Crawling each shop's whole catalog would fetch mostly pages nobody asked about.

Politeness: the shop's API first

Say one big shop holds 4 million of the 10 million watched products, so about 160 of the 400 checks a second go to it. Fetching its pages at that rate is about 14 million page loads a day from one visitor, which looks like an attack. If it has an official product API that returns 100 prices per call, the same checks are 1.6 calls a second, with clean data that doesn't break when the shop redesigns its pages. Use APIs and price feeds where they exist, within their limits and terms.

For shops without one, fetch pages under a rate limit per shop, a token bucket as in Rate Limiting, the way the Web Crawler keeps a gap per host, and obey robots.txt. If a shop's cap is lower than its share of checks, the scheduler stretches that shop's intervals, most watched first. Spreading requests over many IP addresses to dodge a shop's limits breaks its terms and gets you blocked.

Price history: a time series per product

Store a point (product, time, price) only when the price changes, keyed by product, then time:

product   time    price
TV        9:00    $500
TV        9:10    $399
TV        10:10   $420
TV        10:20   $399

Say a price changes on about 1 check in 20: 34.2 million ÷ 20 = about 1.7 million points a day, at about 20 bytes each about 34 MB a day, 12 GB a year. A chart is one range read, and "lowest in 90 days" is the smallest price in that range. A row for every check would be 684 MB a day, about 250 GB a year, for the same chart; saving the whole page on every check would be 3.4 TB a day. The product's own row keeps its current price and when it was last checked.

Alerts: fan-out, once a day

A TV with 50,000 watchers drops from $500 to $399, which meets 20,000 watchers' targets. Watches indexed by product and target find them in one range read: targets from $399 up to $500 (those of $500 or more were met already). Queue one message per watcher in the notification system, which sends at the providers' pace with retries, as in Notification System. Say it sends 1,000 a second for this job: about 20 seconds.

time    price   alerts
9:00    $500    none
9:10    $399    20,000
10:10   $420    none
10:20   $399    none: already sent today

Key each message by user, product and day: the price that flaps back to $399 at 10:20 finds every key already used, so nobody hears twice. Alerting on every check with the price at or below a target would repeat every 10 minutes, up to 144 alerts a day each. Sending the emails one by one from the checker, at say 50 ms each, would hold it for 1,000 seconds, about 17 minutes, and a crash halfway leaves no record of who got one.

Same pattern as the Web Crawler

From the crawler: a queue of work for the fetchers, politeness per site, retries with growing waits, and a parser that pulls one fact out of a page. What doesn't carry over is discovery: no links to follow, no seen set, no Bloom filter.

Summary

• Scope: watched products only; price history; alerts at a target.
• Data: watches (user, product, target), a price series per product.
• API: POST /watches with a product link and a target.
• Numbers: 10 million products, about 2,800 checks a second if all hourly.
• Scale: a priority by watcher count, about 400 checks a second.
• Politeness: shops' own APIs first, a rate limit per shop.
• Alerts: a range read on targets, the notification system's queue, one alert a day.