skip to content

Redis exposes a HyperLogLog type through the PFADD and PFCOUNT commands. What problem does it solve, and what do you give up compared with putting the same items into a Redis Set and calling SCARD?

level: middleimportance: should knowfreq 45%

answer

  1. PFADD / PFCOUNT / PFMERGE
  2. ~12 KB fixed, 16384 six-bit registers
  3. 0.81% standard error
  4. no membership, no removal, no intersection
  5. stored as a Redis String

basics

~20 s

It counts unique items approximately in fixed memory. PFADD adds an element; PFCOUNT returns an estimated distinct count with about 0.81% standard error, using at most ~12 KB per key however many items you add. Unlike a Set it stores no members, so you cannot list them, test membership, or remove one.

solid answer

~50 s

A HyperLogLog is a probabilistic cardinality estimator. PFADD folds each element's hash into a register array; PFCOUNT returns an estimate of the number of distinct elements added, with a standard error near 0.81%. A key costs at most about 12 KB whether you added 100 or 100 million distinct items, and small counts cost far less because Redis starts with a sparse encoding. A Set gives an exact SCARD, but stores every member, so memory grows linearly: tens of millions of user IDs become hundreds of megabytes per counter. The HyperLogLog trades away three things. Exactness: the answer is an estimate. Membership: there is no SISMEMBER equivalent, and the 1/0 PFADD returns means a register changed, not that the element was new. Removal: there is no PFREM, you can only DEL and rebuild. Use it for unique-visitor dashboards at scale, never for anything billed or audited.

code

text · 9 lines
text
PFADD uv:2026-08-14 user:1 user:2 user:1
(integer) 1
PFCOUNT uv:2026-08-14
(integer) 2
TYPE uv:2026-08-14
string

SADD uv:exact:2026-08-14 user:1 user:2 user:1
SCARD uv:exact:2026-08-14   # exact, but stores every member

go deeper

for a junior

Know that it counts unique items approximately in tiny fixed memory, using PFADD and PFCOUNT, and that it does not store the items.

for a middle

Give the numbers (~12 KB, ~0.81% standard error) and contrast concretely with a Set on memory, exactness, and membership.

for a senior

Explain the register/hash intuition, sparse-to-dense growth, and state when the estimate is unacceptable, such as billing or small counts you can afford exactly.

for a principal

Frame it as a capacity decision: how many counter dimensions you can afford, where exactness is contractually required, and what hybrid exact/approximate design you would run.

## The problem Counting distinct things is much harder than counting events. INCR cannot do it, because a counter has no memory of what it already saw. The exact approach in Redis is a Set: SADD uv:2026-08-14 user:42 on every request, then SCARD for the answer. That is correct and O(1) to read, but every distinct member is stored. Forty million member strings can easily be several hundred megabytes, and you usually want one counter per day, per page, per country, so the cost multiplies. ## What a HyperLogLog is A HyperLogLog trades exactness for a fixed, tiny footprint. Conceptually: hash each element to a 64-bit value, use some leading bits to pick one of m registers, and record in that register the largest number of leading zero bits seen in the rest of the hash. Long runs of zeros are rare, so a register that has seen a long run is evidence that many distinct values passed through it. Averaging across all m registers (harmonic mean, plus bias correction) yields a cardinality estimate. Redis uses m = 16384 registers of 6 bits, which is 12 KB of registers plus a small header, and gives a standard error of 1.04/sqrt(m), about 0.81%. Crucially, the same element hashed twice lands in the same register with the same zero-run, so it changes nothing. That is why the structure is idempotent under repeats without storing members: it keeps a statistical fingerprint of the stream, not the stream. ## The API - PFADD key el [el ...] adds elements, creating the key if needed. It returns 1 if at least one internal register was modified, 0 otherwise. - PFCOUNT key returns the estimated cardinality. With several keys it returns the estimated cardinality of their union. - PFMERGE dest src [src ...] stores the union of the sources into dest. Redis stores the structure inside an ordinary String value, so TYPE reports string, and DUMP/RESTORE or GET/SET move it between instances unchanged. ## What you lose Exactness is the obvious one: 0.81% is a standard error, not a hard bound, so individual keys can be further off. Membership is the subtle one, and interviewers love the trap of using PFADD's return value as "have I seen this user before". A register can stay unchanged for a genuinely new element, so the answer is unreliable per element even though it is fine in aggregate. Deletion is impossible: registers only ever move upward, so the structure cannot shrink. And there is no intersection: PFMERGE is a union only, so "users who visited both pages" cannot be computed accurately from HyperLogLogs. ## When to use which Use a Set when the cardinality is small, when you need the members back, when you need per-element membership, or when the number must be exact (billing, compliance, invoices). Use a HyperLogLog when you have many high-cardinality counters, only need the count, and can tolerate roughly 1% error — unique visitors per URL per hour is the canonical fit. A common hybrid is exact Sets for today's small slices plus HyperLogLogs for long-horizon rollups.

  • PFADD returned 0 for a user ID. Can you conclude that the user was already counted?
    No. The return value only says whether an internal register was modified. A brand-new element frequently maps into a register whose stored value is already greater or equal, so nothing changes and you get 0. It is a useful hint for skipping redundant writes, not a membership test.
  • How much memory would 10,000 daily HyperLogLog keys use?
    At most about 120 MB if every key is in the dense encoding, since dense is roughly 12 KB. Keys with low cardinality stay in the sparse encoding and are often only a few hundred bytes, so real usage is usually far lower until the counters grow.

Like judging festival attendance from the rarest wristband number you happen to spot, instead of keeping every wristband.

saying these in an interview costs you the question

  • Treating PFADD's 1/0 reply as 'was this element new'
  • Claiming PFCOUNT is exact, or that the error shrinks as you add more items
  • Thinking the elements are stored and can be enumerated or removed
  • Expecting an intersection command to exist alongside PFMERGE
  • Using it for billable or audited counts where a 1% error is unacceptable

context

resolving links…