Counters and approximate counting
Exact counters that shard, and sketches that count billions in kilobytes.
01The intuition
The problem it solves
A video gets a like. The app sends "like video 42" to a server, which runs UPDATE videos SET likes = likes + 1 WHERE id = 42. One row, one increment, done. Now a song goes viral and 20,000 people a second press like on the same video. Every increment must wait for the previous one to finish, because they all change the same row. A database row can take maybe 2,000 updates a second. The queue grows, the app shows a spinner, and the one hot row has stalled a database that is otherwise idle.
A second version of the problem: a billion views a day across a hundred million videos, and the question "which 10 videos were viewed most in the last hour" asked every few seconds. Keeping an exact counter per video per minute is tens of gigabytes a day and a sort over all of it every few seconds. The answers people want are often approximate anyway: nobody cares whether a video has 3,412,207 or 3,412,210 likes.
Build it one piece at a time
Step 1: count in memory, write in batches. Each server keeps the likes it received in a local map and flushes to the database every second: "video 42: +317". Twenty thousand increments become perhaps twenty database updates a second. The cost is that a server crash loses up to a second of likes, acceptable for likes, not for money.
| Second | Server 1 local | Server 2 local | Flush to database | Row value |
|---|---|---|---|---|
| 1 | 42: 150 | 42: 167 | +150, +167 | 317 |
| 2 | 42: 160 | 42: 155 | +160, +155 | 632 |
Step 2: shard the hot row. If even batched updates are too many for one row, split the counter into 100 rows, 42#0 to 42#99. Each increment picks one at random. Reading the total means summing 100 rows, which is cheap and can itself be cached for a second.
Step 3: never count the same event twice. A phone with a bad connection resends "like video 42". Give every event an ID and remember recent IDs in a set, so a replay is dropped. That is what makes "exactly once" true for a counter.
Step 4: a sketch for counting many things. For "how many times has each of 100 million videos been viewed this hour", replace the exact table with a Count-Min sketch: a grid of, say, 4 rows by 100,000 counters. For each view, hash the video ID four ways, one per row, and increment the four cells. To read a video's count, take the minimum of its four cells. Collisions can only make the estimate too high, never too low, and the minimum trims most of the error. The grid is 1.6 MB, regardless of how many videos exist.
Step 5: distinct counts. "How many different users watched this" over a billion events is a HyperLogLog: hash each user, look at the position of the first 1 bit, and keep the maximum position seen in each of a few thousand buckets. Twelve kilobytes estimates a billion distinct users within about 1 percent.
Why it works, with the numbers
Batching divides database writes by the batch size: 20,000 increments a second at one flush per server per second with 20 servers is 20 updates a second. Sharding divides contention by the shard count. For the sketch, with width w and depth d over N total events, the estimate for any item is at most
true count + 2N/w, with probability at least 1 − (1/2)d
At w = 100,000, d = 4 and a billion events an hour, the error bound is 20,000 views with 94 percent confidence, which is nothing for a video with 10 million views and everything for one with 50. So sketches are for the heavy hitters, and the exact counter stays for the number shown on the page. The invariant for the exact path is "every event is added once"; for the sketch it is "estimates never undercount".
The trade-off you must say out loud
Say which numbers must be exact (billing, inventory, money) and which may be approximate (views, trending, rate limits). Say how much you may lose on a crash with in-memory batching, and that exact counting still happens offline from the event log at the end of the day so the two can be reconciled. The follow-up is usually "how do you show the number to the user", and the answer is a cached total refreshed every second, not a live sum.
Where it shows up in the 100 Google problems
- Like and view counters: batching, sharded rows and event IDs for dedup.
- Trending topics: a Count-Min sketch per time window finds the heavy hitters in kilobytes.
- Ad click aggregation: approximate minute counts for dashboards, exact daily counts from the log for billing.
- Quota limiter: a per-user counter that is approximate between flushes and exact at the end of the day.
- YouTube: the view count under every video is this pattern at a billion views a day.