Sized for 1% false positives. Now it's 44%.

transcript

You sized a Bloom filter for 1 percent false positives. After the flash sale, it's wrong 44 percent of the time.

A Bloom filter hashes each key to k bits. Any of them zero? Definitely never seen. All ones? Maybe. Other keys may have set them.

You planned for 100 million event ids. So 9 point 6 bits per key. And 7 hash functions. One percent false positives.

Then the flash sale pushes in 300 million. Nobody resets it. Nothing errors. Nothing alerts.

At the plan: 1 percent. At twice the keys: about 16 percent. At three times: about 44. Maybe, to almost half.

Here's the catch. A Bloom filter can't grow in place. More keys set more bits. More bits mean more maybes.

Size it for the peak, with headroom. Rotate filters by time. One per hour. And alert once half the bits are set.

The n you sized for is a promise. Keep it.

Full breakdown in the lecture.