HyperLogLog counts millions of different viewers in about 12 kilobytes by keeping lottery cards, not people.
It counts how many different people did something, such as how many unique viewers watched a clip today, rather than total views. Counting exactly means remembering every person, which grows to millions and billions of entries. HyperLogLog throws that whole list away and still gives the number, usually within about 1%, using almost no memory.
It gives an estimate, not an exact number: instead of exactly 82 lakh 31,004 people it says about 8.2 million, usually off by about 1%, sometimes a bit more. You give up being exactly right, and in return memory barely grows. It also cannot tell you whether one specific person watched.
If the odds of winning are 1 in 10 lakh and someone wins, about 10 lakh people probably played. A 1 in 100 win means about 100 players, a 1 in a crore win about a crore. Each viewer gets a scratch card, and keeping only the rarest win seen tells you roughly how many watched.
A person's scratch card is decided by who they are, so the same person always gets the exact same card. If they watch 100 times, it is the same card 100 times over, producing no new win and changing nothing. That is why HyperLogLog measures different people rather than total views.
A single rarest win is shaky: if the first of only five viewers gets a one in a million card, the estimate screams a million. Instead, each viewer goes into one of 16,000 boxes by ID, each box guesses its own crowd, and a typical box is multiplied up. A freak card only disturbs one box.
It is just a hash. The viewer's ID is hashed into a random looking row of zeros and ones, and the win is a run of leading zeros. Six zeros is a one in 64 result; 20 zeros is about one in a million. Each box stores only the longest run of leading zeros it has seen.
The common setup uses about 16,000 boxes, fitting in about 12 kilobytes and landing within roughly 1%. More boxes give a steadier total but use a little more memory. Whether a million or a billion people watch, it is the same 16,000 boxes, so memory does not grow: about 12 kilobytes for a billion people.
Because a person always lands in the same box number on every server, you merge box by box, keeping the bigger rarest win of the two. That gives exactly the boxes one single server would have had, and never double counts. The same works for combining seven daily sets into weekly unique viewers.
Merging only ever adds crowds together. You can add up servers, days or regions freely, but you cannot subtract one day back out later, and you cannot find the overlap between two of them. Adding yes, subtracting no.
Redis has it built in with a 12 kilobyte sketch, Reddit uses it to show post view counts, and most big data warehouses offer approximate count distinct built on it. Avoid it for billing, audits or anything you must defend, and if the set is small enough to count exactly, just do that.
“Not how many views, how many different people.”
“It only ever gives you the count, never a yes or no about one person.”
“Nobody counted the players, but the rarity of the win tells you how many were there.”
“A repeat viewer adds nothing at all.”
“So the total barely moves. One wild guess was shaky. 16000 small guesses side by side are steady.”
“About 12 kilobytes for a billion different people.”
“HyperLogLog — count millions of unique things in a few KB.” https://www.youtube.com/watch?v=UNf6UR_5-_M. Transcript summary by WhipScribe, https://whipscribe.com/transcript-pages/hyperloglog-count-millions-of-unique-things-in-a-few-kb.html.