[00:02] you visit against a list of millions of malicious sites instantly without sending your browser history to Google servers? A database lookup on every navigation would be too slow and a privacy nightmare. So, Chrome needs
[00:15] something that lives on your device. The obvious approach is to download the full list of bad URLs and store them locally in a hash set. It sounds reasonable until you do the math. Millions of URLs at even 50 bytes each blows past what
[00:29] you want sitting in browser memory. And the list is changing constantly. What you actually need is a way to check membership instantly at scale without storing every URL. Chrome uses a Bloom filter. It's a fixed-size bit array.
[00:44] When you add a URL to the filter, you hash into multiple positions and flip those bits. To check membership, you hash the URL again and see if all of the positions are set. If any bit is zero, that URL is definitely on the list. If
[01:01] all of the bits are set, it probably is, but occasionally other entries flip those same bits, giving you what's called a false positive. Bloom filters guarantee zero false negatives, so if it's in the list, you're going to know,
[01:14] but they trade a configurable false positive rate for massive memory savings. In Chrome's case, a false positive just means you make one extra server call to verify a URL that turns out to be fine. It's acceptable. A false
[01:27] negative of missing an actually malicious URL would be a real bug. The numbers back it up. Tracking a billion URLs at a 1% false positive rate costs URLs at a 1% false positive rate costs about 1.2 gigs. A hash set storing the
[01:40] same data would be 10 to 20 times more. The same pattern shows up in web crawlers checking visited URLs, spam filters, and any system doing high-volume membership testing at scale. Want to hear about more tricks like
[01:53] Want to hear about more tricks like this? Follow us for more system design.