10 billion URLs remembered in 12 GB, by choosing how to be wrong

transcript

Your crawler has seen 10 billion URLs. It must remember every one. The trick that fits them in memory? Being wrong. On purpose.

Every extracted link gets checked: seen it before? Stored exactly, that's about a terabyte. A Bloom filter does it in about 12 gigabytes. That fits in memory.

It spends about 9 point 6 bits per URL. Not 100 bytes. The price? For about 1 percent of new URLs, it says maybe. But it never says no for a URL it has seen. Not once.

Here's what matters. Notice which way the errors go. A URL it has seen is always caught. Nothing gets refetched by mistake. About 1 percent of new URLs get a false maybe. That URL is skipped this cycle. That's the whole cost.

For a crawler, skipping 1 percent of new URLs is acceptable. In return, 10 billion URLs fit in 12 gigabytes. Not a terabyte.

You can't always be exact at this scale. So choose which way you're wrong. Then make it the cheap way.

Full breakdown in the lecture.