Merging HyperLogLog Sketches

How many distinct users visited your website yesterday? On a single machine you might sort the log, or keep a hash set. But what if the log is split across a hundred servers, and the full set of user IDs won't fit in memory on any of them?

HyperLogLog (Flajolet et al., 2007) is a probabilistic data structure that estimates the number of distinct elements — the cardinality — of a multiset using only a few kilobytes of memory, with a typical error under 2%. It does this by hashing each item and tracking, in each of $m$ registers, the maximum number of leading zeros seen so far.

The insight that makes it beloved in distributed systems is its merge property: to combine two independent HyperLogLog sketches built on different data shards, you simply take the element-wise maximum of their register arrays. The result is identical to a sketch built on the union of both datasets. No communication is needed beyond swapping a tiny array; no re-scanning of data; no shared state.

That single max per register is what lets engineers count distinct events across fleets of machines in real time — and it follows directly from the mathematics of how the registers are filled.

Each panel below represents a data shard on a different machine. Add words to each shard — the shard builds its own HyperLogLog sketch locally. Then press Merge sketches to combine them with the element-wise maximum and read the estimated distinct count for the union.

<!-- {{c_html_intro}} -->
<div class="app">
  <div class="shards">
    <div class="shard" id="shard-a">
      <div class="shard-title">{{lbl_shard_a}}</div>
      <div class="input-row">
        <input id="input-a" type="text" placeholder="{{ph_add_word}}" maxlength="40" />
        <button id="btn-add-a" type="button">{{btn_add}}</button>
      </div>
      <div class="word-list" id="words-a"></div>
      <div class="sketch-label">{{lbl_registers}} <span class="reg-count" id="reg-count-a">—</span></div>
      <div class="regs" id="regs-a"></div>
      <div class="est-row">{{lbl_local_est}} <strong id="est-a">—</strong></div>
    </div>
    <div class="shard" id="shard-b">
      <div class="shard-title">{{lbl_shard_b}}</div>
      <div class="input-row">
        <input id="input-b" type="text" placeholder="{{ph_add_word}}" maxlength="40" />
        <button id="btn-add-b" type="button">{{btn_add}}</button>
      </div>
      <div class="word-list" id="words-b"></div>
      <div class="sketch-label">{{lbl_registers}} <span class="reg-count" id="reg-count-b">—</span></div>
      <div class="regs" id="regs-b"></div>
      <div class="est-row">{{lbl_local_est}} <strong id="est-b">—</strong></div>
    </div>
  </div>
  <div class="merge-section">
    <button id="btn-merge" type="button" class="primary">{{btn_merge}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="result-box" id="result-box" hidden>
    <div class="result-line">{{lbl_merged_regs}} <span class="reg-count" id="reg-count-m">—</span></div>
    <div class="regs" id="regs-m"></div>
    <div class="result-stats">
      <div>{{lbl_true_count}} <strong id="true-count">—</strong></div>
      <div>{{lbl_hll_est}} <strong id="hll-est">—</strong></div>
      <div>{{lbl_error}} <strong id="hll-error">—</strong></div>
    </div>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: .9rem; }
.app { display: flex; flex-direction: column; gap: .8rem; padding: .4rem 0; }
.shards { display: grid; grid-template-columns: 1fr 1fr; gap: .8rem; }
@media (max-width: 520px) { .shards { grid-template-columns: 1fr; } }
.shard { border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem .8rem; background: #f5f8fa; }
.shard-title { font-weight: 700; font-size: 1rem; margin-bottom: .5rem; color: #1d3557; }
.input-row { display: flex; gap: .4rem; margin-bottom: .5rem; }
.input-row input { flex: 1; padding: .35rem .6rem; border: 1px solid #adb1b8; border-radius: 7px; font-size: .88rem; }
.input-row button { padding: .35rem .7rem; background: #1d3557; color: #fff; border: none; border-radius: 7px; cursor: pointer; font-size: .85rem; }
.word-list { display: flex; flex-wrap: wrap; gap: .3rem; min-height: 1.6rem; margin-bottom: .4rem; }
.word-tag { background: #dde8f0; border-radius: 5px; padding: .1rem .45rem; font-size: .8rem; color: #1d3557; }
.word-tag.dup { opacity: .5; text-decoration: line-through; }
.sketch-label { font-size: .78rem; color: #666; margin-bottom: .2rem; }
.reg-count { font-weight: 600; }
.regs { display: flex; flex-wrap: wrap; gap: 2px; margin-bottom: .4rem; }
.reg { width: 14px; height: 14px; border-radius: 3px; background: #d0dce6; display: inline-flex; align-items: center; justify-content: center; font-size: 8px; color: #fff; font-weight: 700; }
.reg.lit { background: #457b9d; }
.reg.high { background: #e63946; }
.est-row { font-size: .82rem; color: #555; }
.merge-section { display: flex; gap: .5rem; }
button.primary { background: #1d3557; color: #fff; border: none; border-radius: 8px; padding: .45rem 1rem; font: 600 .9rem system-ui; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; border: 1px solid #1d3557; border-radius: 8px; padding: .45rem .9rem; font: 600 .9rem system-ui; cursor: pointer; }
.result-box { border: 2px solid #457b9d; border-radius: 10px; padding: .7rem .9rem; background: #e8f4fb; }
.result-line { font-size: .78rem; color: #444; margin-bottom: .25rem; }
.result-stats { display: flex; flex-wrap: wrap; gap: .6rem 1.2rem; margin-top: .4rem; font-size: .88rem; }
.result-stats strong { color: #1d3557; }

// Code not found

Notice that the merged estimate is close to the true count of unique words across both shards, even though neither shard alone knew what the other contained. Items that appear in both shards are counted only once — exactly as if a single sketch had seen everything from the start.

Why does taking the register maximum work?

Each register $M[j]$ stores the maximum position of the leftmost 1-bit seen in any hash that fell into bucket $j$. If item $x$ hashes into bucket $j$ with leftmost-1 position $\rho(x)$, the register update is simply $M[j] \leftarrow \max(M[j],\, \rho(x))$.

Because the update is a max, two independent sketches $A$ and $B$ on disjoint data satisfy:

$$\text{merge}(A, B)[j] = \max(A[j],\, B[j])$$

This is exactly what a single sketch built on $A \cup B$ would record. The merge is lossless with respect to the sketch state — no information beyond what the registers already hold is needed.

The error bound is well understood. With $m = 2^b$ registers the standard error is approximately $1.04 / \sqrt{m}$. Using $b = 14$ (16 384 registers, about 12 KB) gives roughly 0.8% error. Each register needs only $\lceil \log_2 \log_2 n \rceil$ bits — 5 bits suffices for datasets up to $2^{32}$ — so the total sketch is tiny.

• Space: $O(m \log \log n)$ bits per sketch — kilobytes, not gigabytes.
• Update: $O(1)$ — one hash, one register update.
• Merge: $O(m)$ — one max per register, independent of data size.
• Query: $O(m)$ — apply the harmonic-mean estimator once.

This is a solved problem in the streaming-algorithms sense: the space-accuracy trade-off is essentially optimal for this type of query, as shown by lower-bound arguments for cardinality estimation in the streaming complexity model.

The merge property is what turns HyperLogLog from a curiosity into infrastructure:

• Web analytics: count distinct visitors per country, then merge country sketches to get a global total — no raw data ever leaves the regional server.
• Database query optimizers: systems like BigQuery, Spark and PostgreSQL use HyperLogLog to estimate COUNT(DISTINCT ...) without a full sort or hash-set, and merge partial results across partitions.
• Network monitoring: each router counts distinct source IPs per minute; a central aggregator merges sketches to detect scanning attacks without collecting raw flow data.
• A/B testing: reach (unique users who saw a variant) is a distinct-count query; sketches from different data-center shards merge in milliseconds.
• Redis HyperLogLog: the PFMERGE command implements exactly the register-max merge, letting users combine independent counters with a single command.

Any system that needs to answer "how many unique things happened across these partitions?" without reuniting the raw data is a candidate for HyperLogLog merge. It sits alongside streaming complexity and data compression as a case where accepting a tiny, controlled approximation unlocks otherwise-impossible scale.

HyperLogLog's power comes from a remarkably simple invariant: each register is a max, and max is associative and commutative. That one mathematical fact — $\max(\max(a, b), c) = \max(a, \max(b, c))$ — is what makes distributed distinct counting both accurate and cheap.

You sacrifice a small, tunable margin of error. In return you get a sketch that fits in kilobytes, updates in $O(1)$, and merges across any number of shards in $O(m)$ — exactly the kind of trade-off that separates a textbook exercise from a production system handling billions of events per day.

The next time your analytics pipeline needs a COUNT(DISTINCT ...) across partitioned data, remember that the answer is already in those tiny register arrays, waiting to be merged with a single max.