jonnify·redis /redis-patterns/data-modeling/probabilistic-data-structures/hyperloglog

R7.03.1 · dive 1

Cardinality at a fixed 12KB.

HyperLogLog estimates how many distinct items a set holds, at a fixed 12KB regardless of how many you add, with about 0.81% standard error. The probabilistic trade in its clearest form.

A plain Set is exact — one billion unique ids cost roughly 12GB. A HyperLogLog is fixed: 12KB for that billion, and for a thousand, and for a trillion. Select a representation; the readout reports its memory and its error. It answers how many, never which — so it cannot stand in for EchoMQ's exact dedup.

The memory cliff The commands The EchoMQ contrast References
One billion unique ids — two representations. Select a representation; the readout reports its memory cost and what it can answer.
memory for 1,000,000,000 unique ids (log scale) exact Set ~12 GB · stores every member · answers how many AND which HyperLogLog ~12 KB · fixed · answers how many (±0.81%), not which ~1,000,000× smaller — exactness traded for a flat, tiny footprint
§1

The memory cliff

probabilistic-data-structures.md.txt · cardinality

A plain Set is exact: to count one billion unique ids it stores all one billion, roughly 12GB of RAM. A HyperLogLog is fixed: 12KB for that billion, and 12KB for a thousand, and 12KB for a trillion. The cost does not grow with the cardinality — it is paid once.

The structure hashes each element and watches the maximum run of leading zeros. The chance of an N-zero run is 1/2N, so a long run is evidence of many distinct elements. A single estimator would be noisy, so HLL keeps many registers and combines them with a harmonic mean. The result is an estimate with about 0.81% standard error — for one million actual uniques, typically between 991,900 and 1,008,100.

The trade is exactness for memory. You cannot ask an HLL “is user:123 in here?” — it stores no members, only the evidence of how many there were. What comes back is a count, close but not exact.

A 12GB exact count becomes a 12KB estimate with a 0.81% error. The cost is fixed for any cardinality, and the price is that an HLL answers how many, never which.

§2

The commands — core Valkey

probabilistic-data-structures.md.txt · PFADD / PFCOUNT / PFMERGE

HyperLogLog is core Valkey: PFADD, PFCOUNT, and PFMERGE ship in the engine, no module needed. The PF prefix is a nod to Philippe Flajolet, who co-invented the algorithm.

PFADD visitors:2024-01-30 "user:123" "user:456" "user:789"   # add elements (creates the key)
PFCOUNT visitors:2024-01-30                                  # the estimated cardinality
PFMERGE visitors:week visitors:2024-01-28 visitors:2024-01-29  # union of HLLs — no double-count

PFADD returns 1 if the internal registers changed (a likely-new element) and 0 if not. PFMERGE computes the union — the count of distinct elements across several HLLs — which is how a daily uniques HLL rolls up into a weekly one without double-counting a visitor who returned. Hover the steps below to follow an add and a count through the registers.

An add and a count, through the registers. Select a command; the readout reports what it does to the register array.
PFADD hash → max zeros PFCOUNT harmonic mean PFMERGE per-register max the register array (16384 registers, ~12KB dense) r0 r1 r2 r3 r4 r5 … each register keeps a leading-zero maximum; the count is derived, the members are not stored

Notes on ValkeyPFADD returns 1 when the registers changed and 0 otherwise; an HLL is stored in a string and starts in a compact sparse encoding, converting to the fixed-size dense encoding as the cardinality grows — which is why a small HLL is under 12KB and a large one settles at 12KB — valkey.io/commands/pfadd.

Three core commands — add, count, merge — over a string of registers. The count is derived from the registers, not from stored members, which is why the footprint is fixed and the answer is an estimate.

§3

The EchoMQ contrast — exact, by choice

echo_mq/metrics.ex · the road not taken

EchoMQ counts and dedups exactly, and uses no HyperLogLog anywhere. Its dedup parks each producer idempotency key at a real string key holding the actual branded job id:

echo/apps/echo_mq/lib/echo_mq/metrics.ex · get_deduplication_job_id/3frozen
def get_deduplication_job_id(conn, queue, dedup_id) when is_binary(dedup_id) do
  key = Keyspace.queue_key(queue, "de:" <> dedup_id)
  case Connector.command(conn, ["GET", key]) do
    {:ok, nil} -> :absent
    {:ok, id} when is_binary(id) -> {:ok, id}
    other -> other
  end
end

The difference is the question each answers. An HLL answers “how many distinct ids” approximately. EchoMQ's de: key answers “which id, exactly” — it must, because the dedup decides whether to admit or drop a job, and a wrong “already seen” silently loses work. HyperLogLog cannot answer the membership question at all (it stores no members), and even if it could, its error rate is the wrong property for idempotency. So the road EchoMQ took is the exact key; HyperLogLog is the road for the other problem — counting a huge population cheaply.

the pattern

HyperLogLog: cardinality of a huge set at a fixed 12KB, ~0.81% error. Exactness traded for a flat, tiny footprint; no members stored.

EchoMQ (counter-example)

The emq:{q}:de:<dedupId> key is exact membership — O(n) memory, zero false positives. The dedup must be exact, so EchoMQ pays the memory rather than estimate.

HyperLogLog is the trade in its clearest form: a 12GB exact count becomes a 12KB estimate. Use it when you need how many across a huge population and a sub-percent error is fine — and notice it cannot answer which, which is exactly why EchoMQ's idempotency keeps an exact key. A codemojex note, forward-tense: counting distinct players per day — PFADD cm:uniques:2024-01-30 <player> on each guess, PFCOUNT for the dashboard — is the natural HLL fit, but codemojex ships no HLL surface today, so it is a possibility for the workshop's “uniques” view, not a claim about the live code.

/redis-patterns/data-modeling/primary-database/system-of-record

The exact-dedup home

The emq:{q}:de:<dedupId> key and the @enqueue EXISTS refusal are taught in full in R7.1, the system of record: the job HASH is the record of truth, and its dedup is exact by the same logic.

/bcs

The architecture

The exact dedup follows from the Branded Component System discipline — the branded id is the identity the de: key is built from. The Branded Component System is the architecture EchoMQ is built to.

§4

References

sources · related

Sources

Related in this course