skip to content

Redis documents a standard error of about 0.81% and a footprint of about 12 KB for a HyperLogLog. What do those two numbers actually mean for a counter tracking roughly 50 million uniques, and why is a freshly created key far smaller than 12 KB?

level: seniorimportance: should knowfreq 32%

answer

  1. 1.04/sqrt(16384) = 0.81% standard error, not a bound
  2. 68/95 rule: one and two sigma
  3. 16384 registers x 6 bits = 12288 bytes + header
  4. sparse -> dense at hll-sparse-max-bytes (3000), one-way
  5. MEMORY USAGE / STRLEN to check real cost

basics

~20 s

0.81% is a standard deviation, not a bound: at 50 million uniques a typical estimate is off by ~400k, and a couple of percent happens. 12 KB is the dense form of 16384 six-bit registers; small keys use a compact sparse encoding and convert to dense once they exceed hll-sparse-max-bytes, irreversibly.

solid answer

~50 s

The 0.81% figure is the relative standard error, from 1.04/sqrt(m) with m = 16384 registers. It describes a distribution, not a guarantee: roughly two thirds of estimates fall within one standard error, about 95% within two. At 50 million uniques that is a typical deviation near 400,000 and a plausible outlier near 800,000. Numbers also shift when a counter is rebuilt, which surprises stakeholders reading a dashboard. The 12 KB is the dense encoding: 16384 registers times 6 bits, plus a small header. Redis does not allocate that up front. Low-cardinality keys use a sparse encoding that records only the non-zero registers compactly, so a key with a few hundred elements can be a few hundred bytes. Once it grows past hll-sparse-max-bytes (default 3000), or a register value exceeds what sparse can express, Redis converts to dense permanently — the key never returns to sparse, because elements can never be removed.

code

text · 11 lines
text
PFADD hll a b c
STRLEN hll
(integer) 26          # sparse: tiny

# after adding a few hundred thousand distinct elements
STRLEN hll
(integer) 12304       # dense: 12288 register bytes + 16-byte header

CONFIG GET hll-sparse-max-bytes
1) "hll-sparse-max-bytes"
2) "3000"

go deeper

for a junior

Know the two headline numbers: about 0.81% typical error and at most about 12 KB per key.

for a middle

Explain that 0.81% is a standard deviation derived from 16384 registers, and that small keys start sparse and grow.

for a senior

Translate the error into absolute numbers at real scale, explain the sparse-to-dense trigger and its CPU/memory tradeoff, and verify with MEMORY USAGE.

for a principal

Set policy: which metrics may be approximate, how the error is communicated to consumers, and how counter count times footprint drives cluster memory sizing.

## Reading the error figure honestly A HyperLogLog's accuracy is set by its register count m. Redis fixes m at 16384, and the theory gives a relative standard error of 1.04/sqrt(m) = 1.04/128, about 0.81%. The word standard is load bearing. It is the standard deviation of the estimator, so the estimate behaves like a draw from a distribution centred on the true cardinality: about 68% of the time within +/-0.81%, about 95% within +/-1.6%, with a tail beyond that. Concretely at 50 million uniques: one standard error is about 405,000. A dashboard reading 50.3M when the truth is 50.0M is behaving exactly as designed. Two things follow operationally. First, never put a HyperLogLog behind a number with legal or financial meaning. Second, be careful with derived metrics: a day-over-day delta of 0.3% is entirely noise at this scale, so alerting on small movements in a HyperLogLog-derived series produces false pages. The estimate is deterministic for given key content — the same key always yields the same number — but a rebuild after data loss, or a differently ordered ingestion into different buckets, can land on a slightly different figure. Tell consumers the metric is approximate before they see it. ## Where 12 KB comes from Dense encoding stores all 16384 registers at 6 bits each: 98304 bits, or 12288 bytes, plus a 16-byte header holding magic bytes, the encoding and a cached cardinality. That is the ceiling, and it is independent of cardinality — a key holding a billion uniques is the same size as one holding 100,000. ## Sparse encoding At low cardinality most registers are still zero, so paying 12 KB would be wasteful when you have thousands of near-empty keys. Redis therefore creates HyperLogLogs in a sparse encoding: a compact run-length-style representation storing runs of zero registers and the small non-zero values. A key with a handful of elements can be tens of bytes, and one with a few thousand is still typically under 3 KB. Two triggers force conversion to dense: the sparse representation growing beyond hll-sparse-max-bytes (default 3000), or a register needing a value larger than the sparse format can encode. Conversion is one-way. Lowering the config later, or deleting elements, will not bring a key back — there is no deletion at all. The config is a genuine tradeoff, which is why it exists. Raising hll-sparse-max-bytes keeps more keys small, at the cost of CPU: sparse keys must be walked and decoded on access, so PFADD and PFCOUNT slow down as the sparse blob grows. Values well above a few thousand bytes are discouraged for exactly that reason. With millions of tiny counters and low query rates, raising it saves a lot of memory; with a few hot counters, leave it alone. ## Checking reality MEMORY USAGE on the key tells you what a counter actually costs. OBJECT ENCODING reports raw, because the structure lives inside a String value, and STRLEN gives the byte length — the quickest way to see whether a key has crossed into dense (about 12304 bytes) or is still sparse.

  • You have five million low-traffic HyperLogLog keys. Would you raise hll-sparse-max-bytes?
    Possibly, since keeping keys sparse is the difference between a few hundred bytes and 12 KB each, which at that key count is tens of gigabytes. The cost is CPU: sparse blobs are decoded on every access, so PFADD and PFCOUNT slow down as the limit rises. Raise it moderately and only if the access rate on those keys is low.
  • Can a key that converted to dense ever go back to sparse?
    No. The conversion is one-way for the life of the key, because registers only ever increase and there is no way to remove elements. If you truly need it small again you must DEL the key and rebuild it from source data.

saying these in an interview costs you the question

  • Describing 0.81% as a maximum error the estimate can never exceed
  • Assuming every HyperLogLog key occupies 12 KB from creation
  • Believing accuracy improves as you add more elements
  • Thinking a key shrinks back to sparse after conversion or cleanup
  • Alerting on sub-percent movements in a HyperLogLog-derived metric

context

resolving links…