CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 2 of 8 · 2 min read

Scope and numbers

Count billions of clicks correctly.

Think of a toll road with thousands of booths. Every car leaves a ticket. At the end of each minute, someone must add up how many tickets each booth produced, and the total decides who is paid. The sums cannot lose tickets or count one twice, and the numbers are needed within a few minutes.

Digital advertising has a fast auction, called real-time bidding (RTB), that decides which ad to show. It finishes in under a second. Click counts feed back into budgets and billing. Two key measures use them: click-through rate (CTR), the share of views that lead to a click, and conversion rate, the share of clicks that lead to a purchase.

Questions and the answers assumed here (from the book's sample talk).

  1. Input? Log files on many servers. Each line is a click: ad id, time, user id, IP address and country.
  2. Scale? 1 billion clicks a day, 2 million ads, growing 30 per cent a year.
  3. Queries? (a) the number of clicks for an ad in the last M minutes; (b) the 100 most clicked ads in the last minute, with both numbers adjustable; (c) filters by IP, user or country.
  4. Edge cases? Events arrive late, and parts may fail and need recovery.
  5. Delay? A few minutes from click to result is fine for billing and reports.

Requirements.

  • R1. Correct counts, since they drive billing.
  • R2. Handle late events.
  • R3. Robust to partial failure.
  • R4. End-to-end delay of a few minutes at most.

Numbers (from the book). 1 billion clicks a day is about 10,000 per second (the exact figure is 11,574). Peak is 5 times, about 50,000 per second. One event is 0.1 KB, so a day is 100 GB, and a year about 36.5 TB.

The key point: the write rate is high and steady, and results must be exact.

Click-through rate (CTR)

Click-through rate is the number of clicks divided by the number of times an ad was shown.

Example: 50 clicks on 10,000 views is a CTR of 0.5 per cent.

Check yourself: 1. Why is exactness more important here than in a page-view counter? 2. What is the peak rate in the example? 3. Why is a delay of minutes acceptable?