Dragonfly adds mergeable HyperLogLog counters

Counting events and counting distinct participants require different state. Repeated visits can increment a normal counter, but a distinct count has to account for whether a visitor appeared before. Dragonfly's May 18 release adds the HyperLogLog command family for workloads that can accept an estimate of distinct cardinality.

The useful property is that the structure can combine summaries without retaining every original identifier. The release adds PFADD, PFCOUNT, and PFMERGE together, so an application can accumulate observations, read an estimate, and construct an aggregate. That combination supports a different data model from maintaining a growing exact set.

I find bounded summaries attractive in a cache because memory consumption is part of the reason to consider Dragonfly. The trade is explicit here. An estimate can answer an analytics question without storing all distinct values, but it cannot supply the membership information that an exact set retains.

The representation contains registers

The HyperLogLog implementation included in this release describes a 64-bit hash and 16,384 registers, each six bits wide. The dense register area occupies 12,288 bytes. A sixteen-byte header records the format and other metadata, so the register area alone is not the entire stored string.

Hashing determines which register an observation affects and supplies information about the bit pattern used by the estimator. The structure preserves register information instead of a list of identifiers. Repeating an identifier produces the same hash contribution, which is why repeated observations do not behave like independent increments to a conventional event counter.

The implementation stores HyperLogLog data as a string. No separate top-level database type is necessary. The header begins with a format marker and identifies the encoding. Consequently, a key being a string does not establish that its contents form a valid HyperLogLog. The command implementation validates that representation before using it.

The Dragonfly command integration creates a dense representation for a new counter. It also converts a valid sparse representation to dense form when needed. Its comment specifically mentions that sparse values can originate in Redis through replication or an RDB load.

That distinction affects small datasets. The underlying format includes a sparse encoding for many zero registers, but this Dragonfly path chooses dense storage for newly created counters. An expectation based on Redis's sparse-storage behaviour would therefore be a poor estimate of the space occupied by many small Dragonfly counters in this release.

Adding observations does not return a count

A small example separates the commands and their responsibilities:

redis-cli PFADD visits:morning alice bob alice
redis-cli PFADD visits:afternoon bob carol
redis-cli PFCOUNT visits:morning
redis-cli PFCOUNT visits:morning visits:afternoon
redis-cli PFMERGE visits:day visits:morning visits:afternoon
redis-cli PFCOUNT visits:day

The identifiers are illustrative observations. The multi-key count estimates the union of the two summaries, and the merge stores a combined summary at another key. An overlap such as bob must not be treated as an additional distinct visitor merely because it occurs in a second time interval.

The PFADD integration returns whether the underlying structure changed, capped at one. It does not return the estimated cardinality, and it does not return the number of new identities in the arguments. A successful register update is a different observation from a precise membership test.

This follows from the information retained by the sketch. Different identifiers can contribute to registers that already contain sufficient information. A caller cannot use an unchanged sketch as proof that a particular identity was previously present. Admission control or an exact deduplication requirement needs a representation that can answer the actual membership question.

For a nonexistent key, the single-key count path returns zero. For an existing value of the wrong database type, it returns a wrong-type error. A string with invalid HyperLogLog contents takes a separate invalid-value path. These distinctions keep absence separate from an incompatible value occupying the intended key.

Aggregation crosses internal shards

Single-key counting uses Dragonfly's single-hop transaction path. Multi-key counting allocates a collection for each internal shard, reads the relevant strings from their owning shards, and gathers pointers to those representations for the cardinality calculation. This is where a familiar command has to accommodate the shared-nothing engine.

The command does not compute the union by adding the counts returned for individual keys. Adding those estimates would count overlap incorrectly. It combines the representations and asks the HyperLogLog implementation for a union estimate. An aggregate across time windows can therefore retain overlap information that separate numeric results have already discarded.

Merging has a related but distinct implementation. Dragonfly schedules the transaction, reads the relevant summaries, builds a dense output, and writes the resulting string into the destination. The transaction remains active across the read and write stages. The source shows this as a multi-stage operation with an explicit concluding write.

Temporary storage also belongs in the capacity model. The command integration gathers string copies for the keys involved in a multi-key operation. A fixed-size stored sketch does not imply that merging an arbitrary number of keys has no additional memory cost. The number of participating summaries affects the working data the command collects.

I prefer this model when the desired output is a distinct-count estimate across overlapping intervals. Its value is the preserved ability to combine summaries, not merely the compactness of one counter. Keeping only a numeric estimate for each interval would discard information needed to estimate their union correctly.

Counter lifetime is part of the application model

A HyperLogLog summary does not retain a reversible history of individual observations. The added command family includes accumulation, estimation, and merging. It does not provide a corresponding command to remove one person's contribution. Time-windowed applications therefore need keys whose lifetimes match the intervals they intend to query.

Separate interval keys also make aggregation explicit. The application chooses which summaries belong to the question being asked and supplies those keys to the count or merge operation. The stored representation remains compact while the selection of intervals stays outside the sketch itself.

Version 1.3 includes other compatibility work, such as extending HELLO with authentication and connection-name options. It also permits a Unix-domain socket without a TCP listener. Those changes concern how clients establish connections. HyperLogLog support concerns what information applications can retain once connected, with the dense format and merge path defining its concrete memory behaviour.