HyperLogLog in OxiMem: the same counts as Redis, 3x faster unions

OxiMem, OxiDB's in-memory engine, speaks the Redis protocol. As of today it also knows Redis's HyperLogLog commands: PFADD, PFCOUNT and PFMERGE. The math is exactly Redis's, so for the same elements it returns the same number Redis does. The encoding is different, and that has a cost. This post explains how HyperLogLog works, how it is written in OxiMem, and how it measures against Redis 8.6 side by side. OxiDB is open source; the code is on GitHub: github.com/parisxmas/OxiDB.

The problem: how many distinct?

The "readers" number on the side of this blog shows how many different people have read the site. The obvious way to do that is a set: add every reader, ask for the set's size. That is how the site first counted: each reader was kept as a 16-character digest, which comes to a few megabytes at 100,000 readers.

A set counts exactly, but it keeps everything it has seen and grows with it. Daily unique users of an ad network, distinct IPs hitting an API or distinct queries in a search engine run into millions and billions. Keeping every item there is expensive. And most of the time an exact number is not needed: "about 3.2 million" is enough.

HyperLogLog exists for exactly this. It estimates how many distinct items it has seen without keeping them, in fixed memory, with a small error. Redis's version takes 12 KB and has a standard error of 0.81%.

How HyperLogLog works

The coin-flip intuition

A friend flips a coin and tells you just one thing: the longest run of tails in a row. If the answer is "at most 2", they probably flipped a few times. If it is "20 in a row", that is a one-in-a-million event, so they must have flipped a great many times.

Hash functions behave like coin flips. The bits of a good hash look random, and seeing exactly k zero bits at the end of a hash happens once in 2^(k+1). So the longer the longest run of zeros among the hashes you have seen, the more distinct items you have seen. The same item always gives the same hash, so repeats do not change the number. That is where "distinct" comes from.

One measurement is not enough: buckets

A single longest run is very noisy. One lucky hash doubles the estimate. So HyperLogLog splits hashes into buckets (registers) and keeps a separate longest run in each:

hash = MurmurHash64A(element)                      64 bits

  ┌──────────── 50 bits ───────────┬── 14 bits ─┐
  │  the rest                      │  register  │
  └────────────────────────────────┴────────────┘
                                         │
         trailing zero count + 1 ────────┼──► rank
                                         ▼
               register[r] = max(register[r], rank)

Redis and OxiMem use 2^14 = 16,384 registers. The low 14 bits of the hash pick the register. One more than the number of trailing zeros in the remaining 50 bits is the element's "rank". A sentinel bit at position 50 caps the rank at 51. The register is updated if it holds a smaller rank.

That is all there is to adding an element: one hash, one mask, one zero count and at most one write.

The estimate

Each register's rank is roughly the logarithm of how many elements landed in it. To get back to a count, those guesses are averaged. Not with the arithmetic mean but with the harmonic mean, which stops one lucky register from skewing the whole result. The formula from the original 2007 paper:

E = α · m² / Σ 2^(−register[j])

m is the number of registers and α a correction constant. The formula drifts at very small and very large counts, so the original algorithm switches to "count the empty registers" for small numbers and uses empirical bias tables in between.

Since 4.0 Redis uses Otmar Ertl's improved estimator from 2017, and so does OxiMem. It looks not at the registers but at the rank histogram: how many registers hold each rank. Two series (sigma and tau in the code) handle the edges correctly. The result is a single formula: no bias tables, no switching, the same computation from zero to billions.

The error comes from the number of registers: the standard error is 1.04 / √m, which at 16,384 registers is 0.81%. For 10,000 distinct items the answer will mostly land between 9,920 and 10,080.

Merging

HyperLogLog's nicest property is that it merges. The union of two counters is found by comparing them register by register and keeping the larger one: register[j] = max(a[j], b[j]). The result is the same as if you had counted the union from scratch. Daily counters give weekly unique users this way, per-server counters give the total. PFMERGE and multi-key PFCOUNT do exactly this.

The implementation in OxiMem

The code is in oxidb-server/src/hll.rs and came in two commits: the commands first (c4502f2b), then the speedups (0cd23297).

Same math, same numbers

The goal was to return Redis's number for the same elements, so every detail matches Redis:

• MurmurHash64A with Redis's seed (0xadc83b19), read little-endian on every host. Its output is pinned by test vectors produced from the C reference.
• 2^14 registers. The register is the low 14 bits; the rank is the trailing zeros of the rest plus one.
• Ertl's estimator, rounded the way Redis rounds it.

I measured it myself, adding the same user:0, user:1 ... elements to both:

On every row both servers give the same number, and the error stays around the 0.81% standard error.

A different encoding: ASCII

Redis stores a HyperLogLog as a binary blob: in dense form each of the 16,384 registers takes 6 bits, 12 KB in all. OxiMem cannot do that. Its values are Rust Strings, so they must be valid UTF-8, and they are written as text to the JSON snapshot and to the optional SQL mirror. A blob of arbitrary bytes would break all of that.

So there are two ASCII encodings:

• Sparse (HYLLs): only the non-zero registers, sorted by index. Each one is index << 6 | rank, 20 bits, written as 4 base64url characters. An empty HyperLogLog is just the 5-byte header.
• Dense (HYLLd): one character per register, '0' + rank, 16,389 bytes in all.

Sparse turns into dense past 750 registers (3,000 bytes, Redis's hll-sparse-max-bytes default). The value is a plain string: TYPE says "string", GET, SET, RENAME, COPY and the snapshot carry it like any string, and the TTL survives a PFADD. A PFADD on a string that is not a HyperLogLog answers WRONGTYPE, as Redis does, and leaves the value alone. Because merging a corrupt value would corrupt counts, out-of-order indexes, out-of-range ranks or a wrong length are refused.

I measured the cost too. Size in bytes of the same keys:

For small keys there is hardly a difference. Around 1,000 elements OxiMem goes dense before Redis does, because its sparse form spends 4 bytes per register while Redis's skips runs of empty registers with a single opcode. A full key is 12 KB in Redis and 16 KB in OxiMem, so dense OxiMem uses about 33% more memory. Text cannot pack tighter: a register's 6 bits are exactly one base64 character, so the best case is still one character per register. The gap only closes if OxiMem gets a binary value type. The larger layout also pays something back, as the measurements show.

Speedups

The first version was correct but slower than Redis; according to the commit message, PFMERGE ran at about a quarter of Redis's speed. The second commit changed this:

• Counting straight from the encoding: the estimator only needs the rank histogram, so single-key PFCOUNT no longer builds a 16 KB register array; it reads the histogram off the encoding. A sparse key costs only its entries.
• Folding into one array: PFMERGE and multi-key PFCOUNT fold every source into a single register array (merge_into) instead of decoding each into its own and merging afterwards.
• Branch-free loops: an early-exit check per byte kept the dense loop from vectorizing, at about 6 µs per source. The check now goes to a flag that is looked at after the pass; a test pins that corrupt bytes are still refused.
• Building bytes: building the dense encoding as a byte vector rather than one character at a time took it from 10 µs to 2.5 µs.
• Four sub-histograms: most registers sit on one or two rank values, so a single histogram keeps incrementing the same counter, each increment waiting on the last. Writing to four histograms in turn and adding them up at the end took the dense count from 9.8 µs to 6.8 µs.

Measured against Redis

Correction (3 November 2026): the numbers in the first version of this section came from a run where Redis was started with --daemonize. macOS runs daemonized processes at a lower priority, which made Redis look slower and OxiMem better than they are. The runs were redone with both servers started the same way; the numbers below are the corrected ones.

Setup:

• Apple M4 (10 cores), macOS 26.3.
• Redis 8.6.1 and oxidb-server 0.45.1 (master, 0cd23297) on the same machine, both started the same way from the same shell (in the foreground, under nohup), persistence off.
• Five scenarios with redis-benchmark, each 5 rounds, alternating Redis and OxiMem. The tables show the median. Rounds mostly differ by less than 5%.
• The dense key holds 1 million elements, the sparse key 200. The union and PFMERGE use three overlapping dense keys.

50 clients, no pipelining

In this round the single-key commands bunch up around 230,000 requests/s on both sides. That is mostly the ceiling of the single-threaded redis-benchmark on this machine, not of the servers. PFADD and PFCOUNT on a sparse key are even. OxiMem is 12% behind counting a dense key and 5% behind on PFMERGE.

The real difference is the union: OxiMem is 3.1 times faster. Both fold the sources into one register array, but Redis's dense encoding packs registers into 6 bits, so merging extracts each one with bit shifts. In OxiMem every register is a byte, so the same loop is branch-free and vectorizes. This is where the 33% paid in memory comes back.

50 clients, pipeline 16, 4 threads

With pipelining each client sends 16 commands without waiting for replies, which moves the bottleneck from the client to the server. This is where the real differences show.

Four things stand out:

1. OxiMem has a ceiling. On cheap commands (PFADD, sparse PFCOUNT) OxiMem stops at 1.6 to 1.7 million requests/s while Redis reaches 2.4 to 2.7 million. Stopping at the same place whatever the command suggests the gap comes not from the HyperLogLog code but from OxiMem's per-request overhead (protocol and command dispatch). I have not looked into it yet.
2. The union gap widens to 5.3 times. With the server fully loaded, unpacking 6-bit registers one by one costs more visibly.
3. Redis counts a single dense key 3.8 times faster. On top of the ceiling above there is a second reason: Redis keeps the last estimate in an 8-byte cache in the key's header and does not recompute it until the key changes. The key never changes in this test, so Redis answers from the cache every time, while OxiMem rebuilds the histogram of 16,384 registers each time (about 6.8 µs). On a sparse key that work is tiny, so only the ceiling gap remains there. The fix is clear: a cache field in the value's header. That is the next step.
4. OxiMem's tail latency is higher. Its median latency is equal to or lower than Redis's in most scenarios, but under pipelining its p99 climbs to 1.7 to 24 ms while Redis stays at 0.4 to 10.5 ms. I have not looked into why yet either.

In short: on single-key work OxiMem is for now level with or a little behind Redis, and clearly behind under load. On multi-key counts it is 3 to 5 times ahead.

Using it

The commands are the same as in Redis and work with redis-cli or any Redis client:

$ redis-cli -p 6380 PFADD readers:2026-11-03 ip:203.0.113.7 ip:198.51.100.9
(integer) 1
$ redis-cli -p 6380 PFADD readers:2026-11-04 ip:203.0.113.7 ip:192.0.2.44
(integer) 1
$ redis-cli -p 6380 PFCOUNT readers:2026-11-03 readers:2026-11-04
(integer) 3
$ redis-cli -p 6380 PFMERGE readers:week readers:2026-11-03 readers:2026-11-04
OK
$ redis-cli -p 6380 TYPE readers:week
string

This blog's reader count now works this way too: a salted digest of each reader's IP address goes into a single PFADD key and the number is read with PFCOUNT. Nothing is kept per reader, the key stays at 16 KB at most however many readers there are, and in exchange the number is an estimate with 0.81% error rather than exact.