HyperLogLog: Counting a Billion Users with 12 KB?

Counting distinct users sounds simple until the input becomes enormous. If an application receives billions of user identifiers, the obvious solution is to place every identifier in a set and count the set at the end. That produces an exact answer, but the memory required by the set grows with the number of distinct users. At sufficiently large scale, the identifiers themselves become the dominant cost.

HyperLogLog takes a different approach. Instead of remembering every user, it stores a compact statistical summary of the evidence observed in the input. It hashes each identifier, examines patterns such as leading zeros in the hash, and records a small amount of information about unusually rare patterns. From those observations, it estimates how many distinct values were present.

The result is not an exact count. It is a probabilistic estimate. The important trade-off is that the memory used by the summary can remain very small even when the number of distinct users is extremely large. This is the central idea behind the question in the title: how can a system estimate a billion users with roughly 12 KB of state?

The distinct-counting problem​

Suppose a service wants to answer questions such as:

• How many unique users visited today?
• How many distinct devices appeared in an event stream?
• How many different search terms were submitted?
• How many unique keys were observed by a data pipeline?

The number of distinct values in a collection is called its cardinality. If a stream contains A, B, A, and C, its cardinality is three because the distinct values are A, B, and C.

The direct exact solution is a set:

seen = empty set

for each user_id:
    seen.add(user_id)

answer = size(seen)

This algorithm is easy to understand. A set stores each identifier once, ignores duplicates, and returns the exact number of members. Its disadvantage is memory usage. The set must retain enough information to distinguish all values that have appeared. With millions or billions of distinct values, that requirement can be too expensive for one process and costly to distribute across many machines.

A database can perform an exact COUNT(DISTINCT ...), and a query engine may use hashing, sorting, indexes, or distributed aggregation internally. Those techniques can be highly effective, but exact counting still requires a substantial representation of the distinct values or an equivalent amount of information about them.

HyperLogLog intentionally gives up exactness to obtain a compact, fixed-size summary. It is useful when an approximate cardinality is acceptable and memory efficiency matters more than knowing the precise set of identifiers.

Hashing creates a random-looking input​

HyperLogLog does not analyze user identifiers directly. It first applies a hash function to each identifier. A hash maps an input value to a fixed-width bit sequence that should behave approximately like a random sequence for the values being processed.

For example, an identifier might produce a hash beginning like this:

1011010010010110...

The exact hash value is not important to the algorithm as long as the hash is deterministic and sufficiently well distributed. Similar identifiers should not systematically produce similar output patterns, and the output bits should be reasonably balanced between zero and one.

Hashing provides two important benefits:

1. It removes dependence on the original format of the identifier.
2. It converts the input into a random-looking sequence whose patterns have predictable probabilities.

Those probabilities make estimation possible. In a random binary sequence, one leading zero is common, two leading zeros are less common, three are rarer, and so on. A hash with an unusually long run of leading zeros is evidence that many hash values may have been examined.

This can seem counterintuitive. Why should a rare event reveal the size of the entire input? The reason is that the longest rare pattern observed tends to become more likely as more independent values are tested. A small collection has little opportunity to produce an extremely rare pattern. A huge collection has many opportunities.

Leading zeros as a scale indicator​

Consider a random hash represented in binary. The probability that it begins with at least one zero is approximately one half. The probability that it begins with at least two zeros is approximately one quarter. The probability of at least three leading zeros is approximately one eighth. More generally, the probability of observing at least r leading zeros is close to:

1 / 2^r

This leads to a rough relationship:

number of leading zeros ≈ log2(number of observations)

This is not an exact counting rule. Random variation is significant, especially when only a small number of values have been processed. Nevertheless, across many observations, unusually long zero prefixes carry information about the scale of the input.

If a stream contains only a few distinct values, it is unlikely that any hash will begin with a very long run of zeros. If the stream contains a very large number of distinct values, eventually one of the hashes is likely to contain a long zero prefix.

The algorithm records the strongest leading-zero evidence it has encountered. It does not store every hash, and it does not preserve the original identifier. It stores a small numeric summary of selected hash patterns.

Why a single maximum is too noisy​

A natural first attempt would be to process every hash and remember only the maximum number of leading zeros. This idea contains the core intuition, but it is too noisy to be a reliable estimator by itself.

A single maximum is highly sensitive to luck. Two streams with the same number of distinct values can produce different maximum values. One stream may happen to contain an unusually rare hash pattern, while another may not. If the estimate depends on only one extreme observation, its variation can be large.

HyperLogLog reduces this variation by dividing the hash space into multiple groups, commonly called registers. Each register maintains its own maximum leading-zero observation. Instead of relying on one extreme value, the algorithm preserves many smaller summaries and combines them.

The core process is:

1. Hash each input value.
2. Use part of the hash to select a register.
3. Use the remaining part to measure a leading-zero rank.
4. Update that register with the largest rank observed for it.
5. Combine all register values into a cardinality estimate.

The registers act as multiple samples of the hash distribution. They make the estimate more stable than relying on one global maximum.

Splitting a hash into an index and a rank​

Assume that each input is mapped to a hash with a fixed number of bits. HyperLogLog divides those bits into two logical portions:

[ register-selection bits ][ remaining bits for rank measurement ]

The first portion selects one of m registers. If m is a power of two, a fixed number of bits is sufficient to identify the register. The remaining bits are used to measure the rank, usually based on the position of the first one bit or, equivalently, the number of zeros before that one.

Different descriptions and implementations may use slightly different rank conventions. Some count the number of leading zeros directly; others define the rank as that number plus one. The exact convention changes the numeric values but not the underlying idea: a longer zero prefix produces a larger rank.

Suppose the selection bits identify register 5. If the remaining bits begin with four zeros before the first one, the algorithm computes the corresponding rank and updates register 5 if the new value is larger than the value already stored there:

register[5] = max(register[5], observed_rank)

Every input updates exactly one register. A duplicate identifier hashes to the same output and therefore produces the same update. Once its rank has already been recorded, processing that duplicate normally leaves the register array unchanged. This is why the structure estimates distinct values rather than simply counting events.

What a register represents​

Each register is a small piece of evidence about how many values were assigned to its part of the hash space.

If a register receives very few distinct values, its maximum rank will usually be small. If many distinct values are assigned to it, the register has more opportunities to encounter a rare long prefix, so its maximum rank tends to become larger.

The complete register array forms a compact statistical fingerprint of the input cardinality. It does not reveal which users were present, and it cannot reconstruct the original identifiers. It stores only enough information to estimate how much distinct activity occurred.

This distinction is important:

• An exact set can answer membership questions such as “Was this user seen?”
• A HyperLogLog summary answers an aggregate question such as “Approximately how many distinct users were seen?”

HyperLogLog is not a compressed set that can later be decompressed into its members. It is a purpose-built measurement sketch. Its compactness comes partly from discarding information that is not needed for cardinality estimation.

From registers to an estimate​

After all input values have been processed, HyperLogLog combines the register values into an estimate. The standard estimator gives more influence to registers with smaller values and less influence to registers with larger values. Conceptually, this is a harmonic-mean-style aggregation rather than a simple arithmetic average.

The reason is that register values are related exponentially to the number of observations. Increasing a rank by one corresponds approximately to doubling the rarity of the observed prefix. An aggregation that accounts for this exponential relationship is more appropriate than simply averaging the rank numbers.

At a high level, the estimate has the form:

estimate ≈ constant × m^2 / sum(2^(-register[i]))

Here:

• m is the number of registers.
• register[i] is the stored rank for register i.
• The constant is a calibration factor associated with the estimator and register count.

The exact formula contains implementation details and may be supplemented by corrections for particular ranges. The intuition is more important than memorizing the expression: each register contributes an exponentially weighted signal, and the combined result is scaled according to the number of registers.

If most registers contain small values, the algorithm infers that the stream was relatively small. If many registers contain larger values, it infers that more distinct values were needed to produce those observations.

Why the memory is so small​

The major memory saving comes from what HyperLogLog refuses to store. It does not retain:

• The original user identifiers.
• A complete hash for every user.
• A list of all values that have appeared.
• A separate record for each event or user.

Instead, it keeps a fixed-size array of small registers. Once that array has been allocated, processing more values does not cause the summary to grow. Whether the stream contains thousands, millions, or billions of distinct users, the sketch updates the same register array.

The frequently mentioned “12 KB” figure should be understood as an approximate, configuration-dependent illustration rather than a universal property of every implementation. Memory depends on the number of registers, the number of bits used for each register, and implementation overhead. A configuration with several thousand compact registers can occupy roughly that order of magnitude.

The conceptual relationship is straightforward:

memory ≈ number of registers × bits per register

A real implementation may also include metadata, alignment, serialization details, or object overhead. Even so, the main advantage remains: the sketch size is fixed after configuration and does not grow in proportion to the number of distinct input values.

This is what the title’s comparison means. A billion users are not being stored in 12 KB as a recoverable list. Instead, approximately 12 KB can hold a statistical summary from which the number of users can be estimated.

Accuracy and the memory trade-off​

HyperLogLog trades memory for estimation error. More registers provide more observations of the hash distribution. More observations generally reduce random variation, but they require more memory.

Using fewer registers provides:

• A smaller summary.
• Lower memory consumption.
• More variation in the estimate.

Using more registers provides:

• A larger summary.
• More statistical samples.
• Better typical accuracy.

Therefore, “a billion users with 12 KB” is not a universal guarantee. A more accurate statement is that a carefully selected compact configuration can estimate very large cardinalities while using memory measured in kilobytes rather than memory proportional to the number of users.

The right configuration depends on the acceptable error, the expected cardinality range, and the available memory. An engineer should choose the sketch size from those requirements instead of selecting a register count solely because a particular number sounds impressive.

A useful design process is to define an error budget first. For example, decide whether the application needs a rough trend, a planning metric, or a value accurate enough to compare populations. Then evaluate a configuration against representative workloads. The sketch should be treated as an engineering component with measurable behavior, not as a magic constant-counting device.

Why duplicates do not normally increase the result​

HyperLogLog naturally handles duplicate values because repeated identifiers produce repeated hash observations. A register already containing a rank at least as large as the repeated value’s rank remains unchanged.

Imagine that a user identifier hashes to a value assigned to register 7 with rank 5. The first occurrence may update register 7 from zero to five. Later occurrences of the same identifier produce the same hash and rank, so register 7 stays at five. The sketch does not need to maintain a counter or a separate record for that user.

This behavior makes the sketch suitable for distinct-user estimation in event streams, where one user may generate many events. Counting events and counting distinct users are different tasks:

• A normal event counter increases for every record.
• A HyperLogLog sketch estimates how many different identifiers generated at least one record.

The hash function is essential to this behavior. The same logical identifier must consistently produce the same hash. If different parts of an application use different normalization rules, logically identical identifiers may be treated as different values before hashing. Case normalization, whitespace handling, encoding, and identifier formatting should therefore be defined consistently by the surrounding system.

Merging summaries across machines​

A particularly useful property of HyperLogLog is that summaries can be merged. Suppose a large stream is divided among several machines. Each machine processes its local values into a sketch. The sketches can then be combined register by register:

merged[i] = max(summary_a[i], summary_b[i])

For several summaries, the same idea is applied repeatedly:

merged[i] = max(summary_1[i], summary_2[i], ..., summary_k[i])

The merged result represents the union of the values processed by the participating summaries. Machines do not need to exchange every user identifier. They exchange compact, fixed-size register arrays instead.

The merge operation is simple and can be performed in stages. For example, worker summaries can be merged at a shard, shard summaries can be merged by region, and regional summaries can be combined by a reporting service. Each intermediate result remains a compact sketch.

There is an important condition: the summaries must use compatible parameters and hashing behavior. They need to agree on the hash function or hash domain, the number of registers, the rank interpretation, and the sketch format. Combining incompatible summaries can produce an invalid estimate.

Merging is especially valuable when the raw data is distributed or when data movement is expensive. Instead of shipping a potentially enormous collection of identifiers to one location, each producer can send a bounded-size summary. The trade-off is that the final result remains approximate and cannot support operations that require the original members.

A small conceptual example​

Consider a toy sketch with four registers. Suppose the first two hash bits select the register and the remaining bits determine the rank. Hashes beginning with selection bits 00 go to register 0, hashes beginning with 01 go to register 1, and so on.

Assume several distinct identifiers produce these updates:

value 1 -> register 0, rank 2
value 2 -> register 3, rank 1
value 3 -> register 0, rank 4
value 4 -> register 2, rank 2
value 5 -> register 3, rank 3

The resulting register array is:

[4, 0, 2, 3]

Register 0 is four because it saw ranks two and four, and the larger rank was retained. Register 1 remains zero because none of the processed hashes selected it in this toy example.

Four registers are far too few for a useful production estimate. This example is only intended to demonstrate the update rule. A realistic sketch uses many more registers so that it can observe a more representative distribution of ranks across the hash space.

The example also demonstrates the lossy nature of the structure. After the updates, the sketch contains only the register values. It cannot determine which five identifiers produced them, or even prove that exactly five identifiers were responsible. Several different input sets can lead to the same register array.

Small-cardinality behavior​

The main estimator is designed around the statistical behavior of registers at moderate and larger cardinalities. When the number of distinct values is small compared with the number of registers, many registers may remain empty or at their initial value.

In that situation, an implementation can use a small-range correction based on the number of empty registers. The intuition is straightforward: if many registers have not received a meaningful observation, the input is probably small. Using that information can produce a better estimate than applying the main estimator without adjustment.

This is one reason production implementations may contain more than the basic “hash, count zeros, take maxima” mechanism. They may choose among estimation regimes depending on the observed register state. The general lesson is that probabilistic sketches often need calibration and boundary corrections to behave well over a broad range of input sizes.

The corrections do not change the central concept. The sketch still consists of compact register summaries, and the estimate still comes from statistical patterns in hashed values.

Large-cardinality and hash-width considerations​

A hash has finite width, so any estimator built from it has a finite representable range. At extremely large cardinalities, an implementation may need to account for hash collisions, register saturation, or the limits of the chosen hash representation.

Hash collisions deserve careful interpretation. Two different identifiers can produce the same hash. HyperLogLog is already probabilistic, and collisions add another source of indistinguishability. A sufficiently wide and well-distributed hash reduces the practical impact, but it does not make collisions mathematically impossible.

The engineering conclusion is not that HyperLogLog is unsuitable for large datasets. Rather, the hash width and implementation must be appropriate for the expected range. A production design should document its hash function, register count, register width, expected cardinality range, and behavior near implementation limits.

Choosing a hash function​

Hash quality matters because the estimator assumes that hash bits behave approximately randomly. A poor hash can create patterns that do not match the leading-zero probabilities on which the estimator relies.

For application identifiers, the hash should generally be:

• Deterministic: the same identifier produces the same result.
• Well distributed: outputs should not cluster in a small portion of the hash space.
• Sufficiently wide: the output should support the intended cardinality range.
• Consistent across machines: distributed summaries must use the same hashing rules.

A hash does not need to be cryptographic merely because it is called a hash. The appropriate choice depends on performance, interoperability, and the application’s threat model. However, replacing a suitable hash with an arbitrary weak transformation can undermine the estimator.

Input canonicalization matters just as much. If one service hashes User-42 while another hashes a normalized form such as user-42, the systems may disagree about whether the values are identical. HyperLogLog cannot fix inconsistent identity rules. It only sees the bytes supplied to the hash function.

Practical applications​

A distinct-count sketch is useful when the desired result is an aggregate rather than a per-item lookup. Conceptual uses include:

• Estimating daily active users.
• Measuring unique visitors in a large event stream.
• Estimating the number of distinct devices or accounts.
• Tracking unique keys in logs.
• Summarizing cardinality by time window, region, product, or another dimension.
• Reducing the amount of data exchanged between distributed workers.

The same compactness that helps estimate a billion-user population also helps when many independent sketches must be maintained. An application could keep one summary per time window or per category. The memory for each summary remains bounded by its configuration rather than by the number of raw events in that category.

There is still a cost to grouping. If an application maintains millions of independent groups, a fixed-size sketch per group can become expensive. HyperLogLog solves the problem of storing every member of each group, but it does not eliminate the cost of maintaining an unlimited number of group summaries.

Time-window semantics also need to be explicit. A sketch represents the values processed into it. If one sketch is updated continuously, it estimates cumulative history. To estimate distinct users per hour or per day, the application needs separate sketches for those windows or another time-aware design.

When HyperLogLog is the wrong tool​

HyperLogLog is not a universal replacement for a set or an exact database query. It is a poor choice when the application requires:

• An exact answer.
• The ability to list the distinct users.
• A reliable membership check for a particular identifier.
• Deletion of an individual value.
• Detailed frequency information for every value.
• A guarantee that the estimate never deviates from the truth.

If the question is “Have we seen this exact account before?”, a HyperLogLog summary cannot answer reliably. It has discarded the identity information needed for that operation.

Likewise, if a compliance, billing, or audit workflow requires an exact count, an approximate sketch should not silently replace the source of record. HyperLogLog may still be useful as a monitoring metric, capacity-planning signal, or fast exploratory statistic while an exact system provides authoritative results.

The right comparison is not whether HyperLogLog is always better than an exact set. The real question is whether an approximate cardinality estimate is valuable enough to justify the memory savings and loss of detail.

Common implementation mistakes​

Several mistakes can make a HyperLogLog deployment misleading or incorrect.

Treating the estimate as exact​

The output is an estimate. Dashboards, APIs, and reports should communicate that clearly, particularly when decisions depend on small differences. An estimate of two nearby values may not justify claiming that one population is definitively larger.

Using inconsistent hashing​

All producers and merge targets must agree on the hashing procedure. Differences in encoding, normalization, seed, or hash function can cause the same logical identifier to be treated differently.

Merging incompatible configurations​

Register count and register interpretation are part of the sketch format. A summary with one configuration cannot necessarily be combined directly with a summary using another configuration.

Choosing too few registers​

A tiny sketch may save memory but produce too much variation for the application’s needs. Register count should be selected from an error budget and tested against representative data rather than chosen from memory alone.

Forgetting time-window semantics​

A continuously updated sketch measures the cumulative input. It does not automatically provide a daily or hourly count. Windowed metrics require windowed sketches or a separate design.

Assuming individual deletion is supported​

A register stores a maximum rank. Removing one input can invalidate that maximum, because the sketch does not know which other value produced the previous rank. Standard HyperLogLog is therefore not a simple insert-and-delete set.

Testing an implementation​

Testing should cover both deterministic behavior and statistical behavior.

For deterministic checks, verify that:

• The same identifier produces the same hash and register update.
• Processing a duplicate does not behave like adding a new distinct value.
• Merging compatible summaries gives the same result as processing the union through one summary, subject to the implementation’s details.
• Empty input produces the expected empty-sketch behavior.
• Serialization and deserialization preserve the register state.

For statistical checks, generate many test datasets with known cardinalities and examine the distribution of estimates. One run can be unusually lucky or unlucky, so a meaningful evaluation needs repeated trials or representative workloads. Test several scales, including small inputs, moderate inputs, and the largest cardinalities relevant to the application.

It is also useful to test unusual input formats. Identifiers that share prefixes, contain repeated patterns, or arrive in different encodings should still behave appropriately after hashing. If a chosen hash function performs poorly for the actual identifier domain, repeated tests may reveal systematic bias.

When possible, compare the sketch with an exact set on smaller samples or controlled workloads. Such comparisons do not prove behavior at every scale, but they can reveal incorrect rank calculations, indexing errors, incompatible merges, and serialization bugs.

The deeper idea: measuring without remembering​

HyperLogLog belongs to a broad family of streaming and probabilistic algorithms. These algorithms answer useful questions without storing the complete input history.

The general pattern is:

1. Identify the quantity of interest.
2. Transform incoming values into a distribution with predictable behavior.
3. Store a bounded summary of that distribution.
4. Estimate the answer from the summary.
5. Accept controlled error in exchange for lower resource usage.

For HyperLogLog, the quantity is distinct count. The transformation is hashing. The observed signal is the leading-zero rank. The bounded summary is the register array. The final estimate combines the register values.

The technique works because a random hash stream contains statistical information about how many values generated it. The sketch does not need to remember which values caused the observations. It only needs to preserve carefully selected evidence about how rare the observed patterns were.

That is the conceptual answer to the title’s question. A billion users do not fit into 12 KB as a recoverable list. Instead, a system can use memory on that order to retain a statistical summary from which the billion-scale cardinality can be estimated.

Practical design checklist​

Before adopting HyperLogLog, clarify the following:

1. What is being counted? Define the identifier and its normalization rules.
2. Is an estimate acceptable? Identify the business or technical error tolerance.
3. What cardinality range is expected? Select a suitable hash width and sketch configuration.
4. How many registers are needed? Balance memory against expected estimation variation.
5. Will summaries be merged? Standardize the hash and sketch format across producers.
6. What are the time windows? Decide whether a sketch represents a session, hour, day, or cumulative history.
7. How will results be labeled? Make it clear in APIs, dashboards, and reports that the value is approximate.
8. How will accuracy be monitored? Compare against exact counts on sampled or smaller workloads when possible.
9. What happens at boundaries? Understand small-range behavior, hash limits, and register saturation.
10. What information is required later? Keep an exact system if membership, enumeration, deletion, or auditability is required.

These questions turn an appealing algorithmic idea into a reliable production component.

Final takeaway​

HyperLogLog estimates distinct values by replacing identity storage with statistical evidence. Each identifier is hashed into a random-looking bit sequence. Part of the hash selects a register, while the remaining bits reveal a leading-zero rank. Each register keeps only the largest rank observed for it. After the stream is processed, the collection of register values is combined into a cardinality estimate.

The memory remains bounded because the sketch stores a fixed array of compact registers rather than one record per user. The approximately 12 KB figure is therefore a statement about the size of a particular compact configuration, not a claim that the billion identifiers themselves have been compressed into a recoverable form.

Use HyperLogLog when the goal is a scalable estimate of distinct counts, especially in streaming or distributed systems. Do not use it when the application needs exact membership, enumeration, deletion, or guaranteed precision. Its power comes from a clear and useful trade-off: a small, mergeable summary in exchange for an approximate answer.