0

I'm studying some system design and came across an example of designing a web crawler. One of the requirements of the design is to have a URL dedupe service so that the same content isn't crawled multiple times.

The example then goes into how to identify the dupes. They are expecting to crawl 15 billion distinct URLs. They start out by converting parsed links to canonical URLs. Then they talk about generating a fixed size checksum.

Then they say this:

How much storage we would need for URL’s store? If the whole purpose of our checksum is to do URL dedupe, then we just need to keep a unique set containing checksums of all previously seen URLs. Considering 15 billion distinct URLs and 4 bytes for checksum, we would need:

15B * 4 bytes => 60 GB

If I did my math right, 4 bytes allows around 4 billion unique checksums. The rest of the example suggests all that is getting stored is the checksum and not the URL itself.

I'm unsure how this could work correctly. It seems like if the first 4 billion pages crawled were given unique checksums, there wouldn't be any more checksums for the remaining 11 billion. That would imply checksums are reused for multiple URLs. Wouldn't that mean that everything after URL 4 billion would be considered a dupe regardless of whether it is?

The only way I could see this working is if the checksum was used as the key in a hash map, and the value stored there was a list of all URLs that hashed to that checksum. But they say they are only storing the checksum, so that doesn't seem to make sense.

Edit:

I read a bit more and there is some mention about the system being distributed and each server having it's own subset of URLs. It's still not entirely clear. It seems like the design works, but requires at least 4 separate servers (of 4 billion URL checksums each).

3

You are right, a 4-byte hash can only distinguish 4,294,967,296 distinct values.

Wouldn't that mean that everything after URL 4 billion would be considered a dupe regardless of whether it is?

Actually, it's much, much worse than that, because you're not filling those 4 billion possibilities in order, but essentially at random. You could get unlucky, and the first two URLs you process happen to have the same hash. The more URLs you hash, the higher the probability of a collision, until eventually you reach a probability of 1.

This probability actually grows surprisingly fast (it's a generalised case of the "birthday problem"), and if you plug in some numbers for a 32-bit hash you'll find that by the time you've hashed just seventy-seven thousand URLs with an ideal 32-bit hash, there's a 50-50 chance you'll have computed the same hash for two different URLs!

So, there is no way the proposed system will work with a hash that small. Even doubling the hash size to 64 bits gives us only a 1 in 100 chance of successfully distinguishing 15 billion URLs. Only once we reach an 80-bit hash do we get a more acceptable probability: there's now only a 1 in 10000 chance we thought a URL was a duplicate on our way to 15 billion.

So our actual hash table is going to grow to 15 billion × 10 bytes = 150 gigabytes. Still not actually that bad at modern storage densities, but suggestive that the article authors hadn't done their homework.

3
  • Wow, I didn't realize it took that few hashes to have a 50-50 chance of collision. That's much worse than I thought it was.
    – Dan
    Jan 27 at 22:36
  • 1
    Which is why the birthday problem is also called the birthday paradox. It's generally a surprise when you first come across it.
    – Useless
    Jan 27 at 22:40
  • Yeah, there's definitely some things in the article the authors didn't do very well. In fact, I'm scratching my head on a different app design because the numbers don't add up there either. Oddly enough, I think it's a widely used source. And one I paid a bit of money for.
    – Dan
    Jan 27 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.