Source code
Revision control
Copy as Markdown
Other Tools
# This Source Code Form is subject to the terms of the Mozilla Public
# License, v. 2.0. If a copy of the MPL was not distributed with this
"""Distinct affected-client counting for BHR via HyperLogLog.
For the "percentage of affected users" metric we need a distinct-client count
per hang signature that is small and, above all, mergeable across days, so a
trailing 7 / 28 / 365 day window can be counted without re-scanning every user.
HyperLogLog gives exactly that: a bounded sketch that unions by a register-wise
maximum.
p=11 gives 2048 registers, measured at about 1.5% mean relative error and 2.6%
at the 95th percentile over the cardinalities we see, which is well inside what
a percentage-of-users figure needs. Precision is deliberately modest because a
sketch is stored per signature per day for a 365-day window, so the per-sketch
size matters far more here than the last fraction of a percent.
Only sketches and counts are ever emitted, never client ids. The HLL is a
minimal pure-Python implementation (no dependency); a production build could
swap in Apache datasketches or BigQuery HLL_COUNT without changing the
interface.
"""
import base64
import hashlib
import math
class HyperLogLog:
"""Minimal HyperLogLog cardinality estimator (classic algorithm).
precision `p` gives m = 2**p registers and a relative standard error of
about 1.04 / sqrt(m) (p=14 -> ~0.81%). Uses linear counting for small
cardinalities. 64-bit hashing, so the large-range correction is unneeded.
"""
def __init__(self, p=11):
if not 4 <= p <= 18:
raise ValueError("p must be in [4, 18]")
self.p = p
self.m = 1 << p
self.registers = bytearray(self.m)
@property
def _alpha(self):
"""Bias-correction constant, lifted from the HyperLogLog paper.
Flajolet, Fusy, Gandouet and Meunier (2007), "HyperLogLog: the analysis
of a near-optimal cardinality estimation algorithm", section 3. The
exact constant is defined by an integral,
alpha_m = (m * integral over u of log2((2 + u) / (1 + u))**m) ** -1
which is not worth evaluating at runtime, so the paper gives it
precomputed for the small register counts and an asymptotic
approximation for m >= 128. These are those values verbatim.
"""
if self.m == 16:
return 0.673
if self.m == 32:
return 0.697
if self.m == 64:
return 0.709
return 0.7213 / (1 + 1.079 / self.m)
@staticmethod
def _hash64(item):
digest = hashlib.blake2b(str(item).encode("utf-8"), digest_size=8).digest()
return int.from_bytes(digest, "big")
def add(self, item):
x = self._hash64(item)
idx = x >> (64 - self.p) # top p bits pick the register
w = x & ((1 << (64 - self.p)) - 1) # remaining bits
width = 64 - self.p
rank = (width - w.bit_length() + 1) if w else (width + 1)
self.registers[idx] = max(self.registers[idx], rank)
def merge(self, other):
if other.p != self.p:
raise ValueError("cannot merge HLLs of different precision")
self.registers = bytearray(
max(a, b) for a, b in zip(self.registers, other.registers)
)
return self
def serialize(self):
"""Serialize as {"p", "d"}: the register array, base64 encoded.
Storing only the nonzero registers is the obvious encoding, since most
are zero for a signature with few clients, and it is smaller as raw
JSON. It is the wrong choice here anyway: state and artifacts are
gzipped, and a mostly-zero register array is a long run of one byte,
which compresses far better than a map of scattered indices. Measured
over a 200-signature, 10-day state file, gzipped: 1.25 MB for a sparse
object, 1.04 MB storing the indices and values as parallel arrays, and
0.61 MB dense. Dense also has a fixed size, so one popular signature
cannot blow up the file.
"""
return {
"p": self.p,
"d": base64.b64encode(bytes(self.registers)).decode("ascii"),
}
@classmethod
def deserialize(cls, data):
"""Rebuild a HyperLogLog from a `serialize` map."""
hll = cls(data["p"])
hll.registers = bytearray(base64.b64decode(data["d"]))
return hll
@classmethod
def merged(cls, sketches):
"""Union a sequence of serialized sketches into one HyperLogLog.
register-wise max across all inputs. Returns None if the sequence is
empty (nothing to count). All inputs must share the same precision.
"""
result = None
for sketch in sketches:
if sketch is None:
continue
hll = cls.deserialize(sketch)
if result is None:
result = hll
else:
result.merge(hll)
return result
def count(self):
z = sum(2.0**-r for r in self.registers)
estimate = self._alpha * self.m * self.m / z
if estimate <= 2.5 * self.m:
zeros = self.registers.count(0)
if zeros:
estimate = self.m * math.log(self.m / zeros) # linear counting
return int(round(estimate))