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.
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).