Stop Using HashSet for Unique Counts
45sThe relatable struggle of a common interview question turns into a surprising twist with a massive scale problem, hooking viewers with the 'you're doing it wrong' element.
▶ Play ClipAI Summary
This video explains how to count unique items at massive scale, a common system design interview question. It introduces HyperLogLog, a probabilistic algorithm that estimates cardinality using only about 12 kilobytes of memory, regardless of the number of items. The video contrasts this with the naive approach of using a hash set, which would consume a terabyte of RAM for a hundred billion requests.
Chapters
[00:01]
The naive approach: hash set
Counting unique requests by storing IDs in a hash set works for small data, but fails at scale. For a hundred billion requests, a hash set would consume a terabyte of RAM.
[00:16]
HyperLogLog: a memory-efficient alternative
HyperLogLog estimates cardinality using a probabilistic algorithm that requires only about 12 kilobytes of memory, regardless of input size. It works for billions or even tens of billions of IDs.
[00:29]
How HyperLogLog works
It counts the number of leading zeros in a hash. 50% of items have one leading zero, 25% have two, and so on. The maximum number of leading zeros observed is used to estimate the total number of unique items.
[00:58]
Robustness and error bounds
By applying tricks for robustness, HyperLogLog provides estimates with guaranteed error bounds, making it reliable for approximate counting.
[01:11]
When to use HyperLogLog
Use HyperLogLog when you need to count uniques and don't need a precise value. It's faster and uses far less memory than a gigantic hash table.
HyperLogLog is a powerful tool for counting unique items at scale, offering a massive memory reduction compared to a hash set. It's a key concept for system design interviews and real-world applications where approximate counts are acceptable.
Study Flashcards (5)
What is the memory usage of HyperLogLog?
easy
Click to reveal answer
What is the memory usage of HyperLogLog?
easy
Click to reveal answer
About 12 kilobytes, regardless of input size.
00:29
How does HyperLogLog estimate cardinality?
medium
Click to reveal answer
How does HyperLogLog estimate cardinality?
medium
Click to reveal answer
By counting the maximum number of leading zeros in hashes of items.
00:29
What is the probability that an item has exactly one leading zero?
easy
Click to reveal answer
What is the probability that an item has exactly one leading zero?
easy
Click to reveal answer
50%.
00:29
What is the probability that an item has exactly two leading zeros?
easy
Click to reveal answer
What is the probability that an item has exactly two leading zeros?
easy
Click to reveal answer
25%.
00:44
What is the main advantage of HyperLogLog over a hash set?
medium
Click to reveal answer
What is the main advantage of HyperLogLog over a hash set?
medium
Click to reveal answer
It uses constant memory (12 KB) regardless of the number of items, while a hash set grows linearly.
00:16
💡 Key Takeaways
📊
HyperLogLog memory efficiency
Highlights the key advantage: constant memory usage regardless of input size.
00:16
🔧
Leading zeros counting technique
Explains the core probabilistic mechanism behind HyperLogLog.
00:29
⚖️
Guaranteed error bounds
Emphasizes that HyperLogLog provides reliable estimates with bounded error.
00:58Full Transcript
[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.
