Introduction

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 mm 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.

Try It: Merge Two Sketches

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.

<!-- Two-shard HyperLogLog merge demo: each shard has its own sketch, merge = element-wise max -->
<div class="app">
  <div class="shards">
    <div class="shard" id="shard-a">
      <div class="shard-title">Shard A</div>
      <div class="input-row">
        <input id="input-a" type="text" placeholder="Type a word…" maxlength="40" />
        <button id="btn-add-a" type="button">Add</button>
      </div>
      <div class="word-list" id="words-a"></div>
      <div class="sketch-label">Registers (M=16): <span class="reg-count" id="reg-count-a">—</span></div>
      <div class="regs" id="regs-a"></div>
      <div class="est-row">Local HLL estimate: <strong id="est-a">—</strong></div>
    </div>
    <div class="shard" id="shard-b">
      <div class="shard-title">Shard B</div>
      <div class="input-row">
        <input id="input-b" type="text" placeholder="Type a word…" maxlength="40" />
        <button id="btn-add-b" type="button">Add</button>
      </div>
      <div class="word-list" id="words-b"></div>
      <div class="sketch-label">Registers (M=16): <span class="reg-count" id="reg-count-b">—</span></div>
      <div class="regs" id="regs-b"></div>
      <div class="est-row">Local HLL estimate: <strong id="est-b">—</strong></div>
    </div>
  </div>
  <div class="merge-section">
    <button id="btn-merge" type="button" class="primary">Merge sketches</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="result-box" id="result-box" hidden>
    <div class="result-line">Merged registers (element-wise max): <span class="reg-count" id="reg-count-m">—</span></div>
    <div class="regs" id="regs-m"></div>
    <div class="result-stats">
      <div>True distinct count: <strong id="true-count">—</strong></div>
      <div>HLL merged estimate: <strong id="hll-est">—</strong></div>
      <div>Error: <strong id="hll-error">—</strong></div>
    </div>
  </div>
</div>

/* Layout for the two-shard HyperLogLog merge demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// HyperLogLog cardinality estimator with M registers.
// Each register stores the max leading-zero position seen in its bucket.
const M = 16; // 16 buckets — small enough to see the registers visually
const MASK = M - 1;

// FNV-1a 32-bit hash: fast, uniform, deterministic
function hash32(str) {
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = (h * 0x01000193) >>> 0;
  }
  return h;
}

// rho(bits): position of the leftmost 1-bit (1-indexed from MSB)
function rho(bits) {
  if (bits === 0) return 32;
  let pos = 1;
  while ((bits & 0x80000000) === 0) { bits <<= 1; pos++; }
  return pos;
}

// Create a zeroed sketch
function newSketch() { return new Uint8Array(M); }

// Add an item to a sketch: hash, pick bucket, update register with max rho
function sketchAdd(regs, item) {
  const h = hash32(item);
  const j = h & MASK;
  const w = h >>> 4; // remaining bits after taking the bucket index
  const r = rho(w);
  if (r > regs[j]) regs[j] = r;
}

// Merge two sketches: element-wise max — the core of the algorithm
function sketchMerge(a, b) {
  const m = new Uint8Array(M);
  for (let j = 0; j < M; j++) m[j] = Math.max(a[j], b[j]);
  return m;
}

// Estimate cardinality via harmonic mean of 2^(-register)
function estimate(regs) {
  const alpha = 0.7213 / (1 + 1.079 / M);
  let sum = 0;
  for (let j = 0; j < M; j++) sum += Math.pow(2, -regs[j]);
  return Math.round(alpha * M * M / sum);
}

// Per-shard state: word history, unique-word set, register array
const stateA = { words: [], set: new Set(), regs: newSketch() };
const stateB = { words: [], set: new Set(), regs: newSketch() };

function addWord(state, word, listId, regsId, estId, cntId) {
  const w = word.trim().toLowerCase();
  if (!w) return;
  sketchAdd(state.regs, w);
  const isDup = state.set.has(w);
  if (!isDup) state.set.add(w);
  state.words.push({ w, isDup });
  renderWords(state, listId);
  renderRegs(state.regs, regsId, cntId);
  document.getElementById(estId).textContent = estimate(state.regs);
}

function renderWords(state, listId) {
  const el = document.getElementById(listId);
  el.innerHTML = '';
  state.words.forEach(({ w, isDup }) => {
    const t = document.createElement('span');
    t.className = 'word-tag' + (isDup ? ' dup' : '');
    t.textContent = w;
    el.appendChild(t);
  });
}

function renderRegs(regs, regsId, cntId) {
  const el = document.getElementById(regsId);
  const max = Math.max(...regs, 1);
  el.innerHTML = '';
  regs.forEach(v => {
    const d = document.createElement('div');
    d.className = 'reg' + (v > 0 ? (v >= max ? ' high' : ' lit') : '');
    d.textContent = v || '';
    el.appendChild(d);
  });
  if (cntId) document.getElementById(cntId).textContent = M;
}

function doMerge() {
  const merged = sketchMerge(stateA.regs, stateB.regs);
  const unionSet = new Set([...stateA.set, ...stateB.set]);
  const trueCount = unionSet.size;
  const hllEst = estimate(merged);
  const err = trueCount > 0 ? Math.abs(hllEst - trueCount) / trueCount * 100 : 0;

  renderRegs(merged, 'regs-m', 'reg-count-m');
  document.getElementById('true-count').textContent = trueCount;
  document.getElementById('hll-est').textContent = hllEst;
  document.getElementById('hll-error').textContent = i18nFmt('%pct%%', { pct: err.toFixed(1) });
  document.getElementById('result-box').hidden = false;
}

function doReset() {
  stateA.words = []; stateA.set.clear(); stateA.regs = newSketch();
  stateB.words = []; stateB.set.clear(); stateB.regs = newSketch();
  ['words-a','words-b'].forEach(id => document.getElementById(id).innerHTML = '');
  ['regs-a','regs-b'].forEach(id => { document.getElementById(id).innerHTML = ''; });
  ['reg-count-a','reg-count-b','est-a','est-b'].forEach(id => document.getElementById(id).textContent = '—');
  document.getElementById('result-box').hidden = true;
}

function setupInput(inputId, btnId, state, listId, regsId, estId, cntId) {
  const inp = document.getElementById(inputId);
  const btn = document.getElementById(btnId);
  btn.addEventListener('click', () => { addWord(state, inp.value, listId, regsId, estId, cntId); inp.value = ''; inp.focus(); });
  inp.addEventListener('keydown', e => { if (e.key === 'Enter') btn.click(); });
}

setupInput('input-a', 'btn-add-a', stateA, 'words-a', 'regs-a', 'est-a', 'reg-count-a');
setupInput('input-b', 'btn-add-b', stateB, 'words-b', 'regs-b', 'est-b', 'reg-count-b');
document.getElementById('btn-merge').addEventListener('click', doMerge);
document.getElementById('btn-reset').addEventListener('click', doReset);

// Seed both shards with sample words so the demo starts populated
const seedA = ['apple','banana','cherry','date','elderberry','fig','grape','honeydew'];
const seedB = ['apple','grape','kiwi','lemon','mango','nectarine','orange','papaya'];
seedA.forEach(w => addWord(stateA, w, 'words-a', 'regs-a', 'est-a', 'reg-count-a'));
seedB.forEach(w => addWord(stateB, w, 'words-b', 'regs-b', 'est-b', 'reg-count-b'));
Result
Console

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.

The Real Complexity

Why does taking the register maximum work?

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

Because the update is a max, two independent sketches AA and BB on disjoint data satisfy:

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

This is exactly what a single sketch built on A∪BA \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=2bm = 2^b registers the standard error is approximately 1.04/m1.04 / \sqrt{m}. Using b=14b = 14 (16 384 registers, about 12 KB) gives roughly 0.8% error. Each register needs only ⌈log⁡2log⁡2n⌉\lceil \log_2 \log_2 n \rceil bits — 5 bits suffices for datasets up to 2322^{32} — so the total sketch is tiny.

  • Space: O(mlog⁡log⁡n)O(m \log \log n) bits per sketch — kilobytes, not gigabytes.
  • Update: O(1)O(1) — one hash, one register update.
  • Merge: O(m)O(m) — one max per register, independent of data size.
  • Query: O(m)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.

Where It Matters

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.

Conclusion

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))\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)O(1), and merges across any number of shards in O(m)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hyperloglog-merge/Content licensed under CC BY-NC 4.0.