# HyperLogLog > HyperLogLog (HLL) estimates how many distinct values appear in a dataset without storing every value. In system design, it makes large-scale unique-user and cardinality queries affordable when a small estimation error is acceptable. Source: https://sysround.com/concepts/hyperloglog Updated: 2026-11-05 ## How hyperloglog works Start by defining what counts as distinct: a user ID, device ID, or complete metric label set. Hash that value with a stable, well-distributed hash function. Repeated occurrences of the same value produce the same hash, so they do not increase the estimate. Split the hash into two parts. The first selects one of m registers; the remaining bits determine a rank, usually the number of leading zero bits plus one. For example, if those remaining bits begin 0001, the rank is 4. Keep only the largest rank seen in each register. Long runs of zeros are uncommon, so observing them provides evidence that many distinct values have arrived. HLL combines the register values using a harmonic-mean-based estimator, with corrections for ranges where the basic formula is biased. Use a tested implementation rather than implementing only the basic formula. Precision controls memory and error. The classic relative standard error is approximately 1.04 / sqrt(m). With 16,384 registers, that is about 0.81%; packing each register into six bits takes 12 KiB before metadata. This is a statistical error measure, not a guaranteed maximum error. Workers can build sketches independently and merge compatible sketches by taking the maximum of each corresponding register. This estimates the union, including users seen on multiple workers; adding their numeric estimates would double-count those users. For time windows, keep separate sketches per time bucket and merge the required buckets, because ordinary HLL cannot remove individual values. ## Worked example: Daily unique visitors across 32 workers Suppose a site receives 100 million page-view events per day and wants daily unique signed-in users, accepting about 1% standard error. Each of 32 ingestion workers updates a daily HLL using the stable user ID. Choose 16,384 registers: the classic standard error is about 0.81%, and six-bit registers occupy 12 KiB before overhead. The 32 worker sketches therefore use 384 KiB for this one daily metric. A query service merges corresponding registers by maximum, so a user visiting through several workers is not counted separately. Late events update the appropriate retained daily sketch. For weekly uniques, merge seven daily sketches rather than adding seven estimates. Keep raw events separately if exact reconciliation or identity corrections are required. ## Trade-offs - **Small memory footprint versus approximate answers.** For a chosen precision, register storage stays bounded as distinct values grow, but the result is unsuitable when every individual must be counted exactly. - **Better accuracy costs more memory.** Halving the standard error requires roughly four times as many registers. - **Cheap distributed unions require compatible sketches.** Register-wise merging needs matching identity encoding, hash behavior, and precision unless the implementation explicitly supports conversion. - **No ordinary deletion or subtraction.** Expiring individual users, correcting bad identities, or retracting events requires bucket expiration, rebuilding from retained data, or another data structure. - **Limited query capabilities.** HLL cannot list members or answer membership queries, and estimating small intersections by subtracting large union estimates can produce large relative errors. - **Bounded per sketch does not mean bounded overall.** Memory and merge work still multiply across tenants, dimensions, time buckets, and worker-local copies. ## When to use it in a system design interview - The requirement is approximate daily or monthly distinct users, devices, visitors, or other identifiers over a high-volume event stream. - An exact set would consume too much memory or require expensive distributed deduplication. - Data arrives on many workers, and the system needs a compact, mergeable representation of distinct values across them. - A monitoring pipeline needs approximate distinct-series counts to detect cardinality growth without retaining every series identity in the counting layer. - A live-viewer estimate can tolerate both statistical error and bucket-boundary error, with presence defined through recent heartbeats. ## How to bring it up in the interview - Define the identity and acceptable error before proposing HLL: 'We need distinct signed-in users per day, and roughly 1% standard error is acceptable.' Interviewers will probe anonymous users, multiple devices, and identity changes. - Size it explicitly using 1.04 / sqrt(m), then multiply storage by the number of groups, retained buckets, and worker copies. Expect questions about uncontrolled dimension cardinality. - Explain merging as register-wise maximum, not addition of estimates. Mention stable hashing and compatible sketch configuration across workers and deployments. - Describe event-time buckets, late-event handling, and expiration. For a rolling window, acknowledge that including partially overlapping buckets adds timing error beyond HLL's estimation error. - Separate approximate analytics from correctness-critical state. HLL can estimate unique clickers, but it cannot decide whether an event was already billed or whether a particular user is present. ## Common mistakes - Calling HLL an exact distinct counter, or presenting its standard error as a hard error bound. - Using HLL to test whether an identifier has already been processed; it does not support membership checks. - Adding daily or shard-level distinct estimates instead of merging their sketches to account for overlapping users. - Subtracting yesterday's sketch from a cumulative sketch, or assuming individual departures can decrement a live-viewer HLL. - Budgeting one small sketch while ignoring millions of tenant, page, campaign, and time-bucket combinations. ## Interview questions where it comes up - [Design Google Analytics](https://sysround.com/questions/design-google-analytics): Distinct-user queries across shards and time ranges are a direct use for mergeable HLL sketches when approximate answers are acceptable. - [Design a metrics monitoring system like Datadog](https://sysround.com/questions/design-metrics-monitoring-system): HLL can estimate distinct metric-series cardinality across ingestion workers to detect growth without storing an exact counting set. - [Design a live viewer count](https://sysround.com/questions/design-live-viewer-count): Bucketed HLL sketches can estimate distinct viewers from recent heartbeats, making expiration semantics and bucket-boundary error central design decisions. ## FAQ ### What is HyperLogLog used for? HyperLogLog estimates distinct counts, such as unique visitors or distinct metric series, using a compact sketch. It is useful when exact sets are too expensive and approximate analytics meet the requirement. ### How accurate is HyperLogLog? The classic relative standard error is approximately 1.04 divided by the square root of the register count. With 16,384 registers, it is about 0.81%, but individual estimates can deviate more than that. Accuracy also depends on sound hashing and the implementation's estimator and bias corrections. ### What is the difference between HyperLogLog and a Bloom filter? HyperLogLog answers 'approximately how many distinct values have appeared?' A Bloom filter answers 'might this particular value have appeared?' HLL cannot replace a membership filter, and neither structure alone provides exact event deduplication for billing. ## Related concepts - [Bloom filters](https://sysround.com/concepts/bloom-filter) - [Count-min sketch](https://sysround.com/concepts/count-min-sketch) - [Stream processing](https://sysround.com/concepts/stream-processing) - [Windowing and watermarks](https://sysround.com/concepts/windowing) --- SysRound (https://sysround.com) is an AI practice tool for system design interviews: a voice or typed AI interviewer, a shared whiteboard, then feedback on every skill and a model answer. Its feedback is AI-generated and can be wrong.