[00:01] how many unique requests your site had today? You think, easy, I'll throw their IDs in a hash set. Done. Then your interviewer says, it's a hundred billion requests. Your hash set just consumed a terabyte of RAM. You could shard it and
[00:16] 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
[00:29] 12 kilobytes of memory regardless of input size. A billion IDs or 10 billion, you don't need more memory. The way it works is by counting the number of leading zeros in a hash. 50% of items will have only one leading zero. 25%
[00:44] will have two. The more items you're counting, the more likely you are to have a rare streak where a hash has a lot of leading zeros. If we keep track of the maximum number of leading zeros and apply some tricks for robustness, we
[00:58] 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 way less memory than a gigantic hash table. Follow us
[01:11] than a gigantic hash table. Follow us for more system design.