How HyperLogLog Counts Billions of Unique Feed Views Using Two Kilobytes of Memory

In June 2007, French mathematician Philippe Flajolet presented a paper at a conference in southern France that fundamentally altered how internet platforms process data. His algorithm, named HyperLogLog, offered a mathematically rigorous way to estimate massive crowds without actually remembering anyone in them.[1]

Before this publication, tracking unique visitors required a system to maintain an exact list of every person who had previously loaded a page. If a user arrived, the database had to scan the entire historical list to ensure they were not being counted twice.[3]

That exact approach works perfectly for a local business website receiving a few hundred visitors a day. It collapses entirely when applied to a global social media feed where a single viral video might attract fifty million unique viewers in an afternoon.[3]

Storing fifty million standard 64-bit user identifiers requires roughly 400 megabytes of active memory for just one post. Multiply that footprint across the billions of posts circulating on a modern social network, and the server costs become economically unviable.[3]

Flajolet’s algorithm bypassed this bottleneck by abandoning the requirement for absolute precision. By accepting an error margin of less than one percent, HyperLogLog compresses the memory required to count a billion unique users down to just 1.5 kilobytes.[1]

The Memory Wall of Exact Sets

The core challenge of cardinality estimation—the mathematical term for counting unique items—is that duplicates are invisible unless you have a perfect memory. You cannot know if you have seen a specific user before unless you compare them against everyone you have already seen.[3]

Engineers initially tried to solve this by using hash sets, which mathematically scramble user IDs into fixed-length strings and store them in an indexed list. While faster than scanning a raw database, hash sets still require storing a unique entry for every single visitor.[2]

"The memory requirement grows linearly with the number of unique elements," the Redis documentation notes regarding standard set data structures. "If you need to count millions of unique items, you will quickly consume gigabytes of RAM just for the counters."[2]

This linear scaling meant that as a platform grew, its infrastructure costs grew at the exact same rate. Social media companies needed a mechanism where the memory footprint remained flat, regardless of whether a post had ten viewers or ten million.[3]

The solution required shifting from deterministic counting to probabilistic estimation. Instead of asking exactly how many people were in the room, engineers began asking what the statistical likelihood was of seeing a specific pattern of visitors.[1]

Coin Flips and Leading Zeros

HyperLogLog relies on a principle similar to tossing a coin and counting how many times it lands on heads in a row. If someone tells you they flipped heads once, you assume they only flipped the coin a few times.[3]

If they tell you they flipped heads twenty times in a row, you can mathematically deduce they must have been flipping that coin for a very long time. The algorithm applies this exact statistical probability to binary data.[1]

When a user views a post, the system runs their ID through a cryptographic hash function, converting it into a long string of random ones and zeros. The algorithm then simply counts how many zeros appear at the very beginning of that string.[2]

Half of all hashed IDs will start with a one, a quarter will start with a zero followed by a one, and an eighth will start with two zeros. Finding a hash that begins with ten consecutive zeros is exceedingly rare, occurring only once in every 1,024 visitors.[3]

By keeping track of the longest sequence of leading zeros it has ever seen, the algorithm can estimate the total size of the crowd. If the record is ten zeros, the system assumes roughly a thousand unique people have visited.[1]

Taming Outliers With Harmonic Averages

The obvious flaw in this coin-flipping approach is variance. A system could theoretically encounter a user whose hashed ID begins with twenty zeros on the very first view, which would trick the algorithm into thinking a million people had already visited.[3]

Flajolet solved this variance problem through stochastic averaging, splitting the incoming stream of viewers into thousands of separate buckets. The algorithm uses the first few bits of the hash to assign each user to a specific bucket, and then tracks the maximum leading zeros within each one independently.[1]

A standard implementation uses 16,384 distinct buckets, known as registers. By averaging the maximum zero counts across all of these registers, the algorithm smooths out the statistical anomalies and produces a highly stable estimate of the total population.[2]

However, a standard arithmetic mean remains too vulnerable to extreme outliers. If just one of the 16,384 buckets records an unusually high number of zeros, it can drag the entire average upward and artificially inflate the final view count.[3]

To counter this, HyperLogLog employs a harmonic mean, which calculates the average by dividing the number of values by the sum of their reciprocals. This specific mathematical operation heavily discounts large numbers, effectively neutralizing the impact of statistical freaks.[1]

The Engineering Trade-Off

The result of this harmonic averaging is a data structure that delivers a standard error rate of just 1.04 divided by the square root of the number of registers. For a typical 16,384-register setup, that translates to an accuracy margin of 0.81 percent.[2]

"HyperLogLog is a remarkable algorithm," the Redis engineering team explains in their technical documentation. "It allows you to estimate the cardinality of a set with an error of less than one percent, using a maximum of 12 kilobytes of memory."[2]

This represents a profound engineering compromise. By accepting that a view count of 100,000 might actually be 99,200 or 100,800, platforms can reduce their memory overhead by a factor of several million.[3]

While cloud providers frequently market their analytics suites as delivering perfect real-time precision, the underlying reality is entirely probabilistic. The infrastructure only scales because it quietly abandons the pursuit of exact numbers in favor of mathematical estimation.[3]

The algorithm also provides an inherent privacy benefit. Because the system only stores the maximum number of leading zeros observed in each bucket, it retains absolutely no identifying information about the users who generated those zeros.[1]

Scaling to Billions of Views

Modern implementations have optimized Flajolet's original design even further. Many systems now use sparse representations, which compress the registers when a post is new and only expand to the full 12-kilobyte footprint if the content goes viral.[2]

This compression means that the vast majority of posts on a social network—which typically receive only a handful of views—consume just a few bytes of memory each. The infrastructure scales dynamically based on actual traffic demands.[3]

The algorithm also allows for seamless distributed computing. Because the registers only track maximum values, engineers can merge the HyperLogLog data from a server in Tokyo with one in New York simply by taking the highest value for each bucket.[2]

This mergeability is what allows global platforms to display a unified view count in real time. The distributed servers do not need to share lists of users; they only need to exchange their tiny, two-kilobyte arrays of maximum zero counts.[3]

Two decades after its publication, Flajolet’s algorithm remains the invisible foundation of internet analytics. It stands as a definitive proof that in computer science, absolute certainty is often an unnecessary luxury, and strategic estimation is the only way to scale.[1]