Your interviewer asks you to count how many unique requests your site had today. Easy, I'll throw their IDs in a HashSet. Done.

Then your interviewer says: it's 100 billion requests. Your HashSet just consumed a terabyte of RAM. Uh oh.

You could shard it and turn this into an expensive but solvable problem, but there's a much better approach called HyperLogLog.

HyperLogLog estimates cardinality like the number of uniques using a probabilistic algorithm that needs about 12 kilobytes of memory regardless of input size. A billion IDs or ten billion, no more memory is needed.

The way it works is by counting the number of leading 0's in a hash. 50% of items will have only 1 leading 0, 25% will have 2. The more items you are counting, the more likely you are to have a rare streak where a hash has a lot of 0s. If we keep track of the maximum number of 0s, and apply some tricks for robustness, we can estimate the number of uniques with guaranteed error bounds.

So remember, if you need to count uniques and don't need a precise value, HyperLogLog will do it faster and with less memory than a gigantic hash table.

Follow us for more system design. #shorts

Why System Design Interviews Ask You to Count Billions of Users Without a HashSet