Finding hot keys without counting every request

transcript

To catch a hot key, you count every key's requests. Easy? That costs the most for exactly the keys you're hunting.

Exact counting stores a timestamp for every request. The hottest key has the most requests. So the biggest log. Worst exactly where it matters. So use a Count-Min Sketch. Fixed memory, however many keys you have. A few additions per request. And good enough for detection.

It's a grid. Say 7 rows of 10,000 counters. Each row has its own hash. A request comes in. Hash the key once per row. Add one at each spot. To read a count, hash again, and take the smallest of those counters.

Why the minimum? Other keys collide into the same counters. They only ever add. So it can overestimate. It never underestimates. It might raise a false alarm. It never misses a hot key.

So use it as a filter. A key's estimate passes 80 percent of the threshold. Now switch to exact counting. For that one key only. Over 1,000 a minute, for real? It's hot. Memory stays fixed for everyone else.

Approximate to find the suspects. Exact to convict them. Fixed memory, and no hot key slips through.

Full breakdown in the lecture.