HyperLogLog em Python Puro: O Algoritmo Que Conta Bilhões de Elementos Únicos Usando Menos de 20 KB de Memória
Você já tentou contar quantos visitantes únicos seu site recebeu no último ano?
Se você respondeu “sim”, provavelmente usou um set() em Python e adicionou cada IP ou ID de usuário. Funciona bem para 10 mil visitantes. Funciona razoavelmente para 1 milhão. Mas quando você chega em 1 bilhão? Seu servidor explode antes de terminar o loop.
Eu descobri isso da pior forma. Em 2024, precisei contar quantos usuários únicos acessaram um sistema de logs distribuído. O banco tinha 847 milhões de registros. Minha primeira abordagem? SELECT COUNT(DISTINCT user_id). O PostgreSQL travou por 47 minutos e morreu com out of memory.
A solução não foi comprar mais RAM. Foi aprender um algoritmo que usa 1 kilobyte de memória para estimar cardinalidades de bilhões de elementos com erro menor que 2%. Esse algoritmo se chama HyperLogLog, e hoje vou implementá-lo do zero em Python puro.
O Problema: Por Que Contar Elementos Únicos é Tão Difícil?
Contar elementos únicos parece trivial. Você itera sobre os dados, adiciona cada elemento a um conjunto, e no final verifica o tamanho do conjunto. Em Python:
def contar_unicos_naive(elementos):
unicos = set()
for elem in elementos:
unicos.add(elem)
return len(unicos)Funciona perfeitamente para datasets pequenos. Mas cada elemento no set ocupa memória. Se você tem strings de 32 bytes (como UUIDs) e 1 bilhão de elementos únicos, precisa de aproximadamente 32 GB só para armazenar os dados. Sem contar a sobrecarga da estrutura do set em Python.
O problema piora em sistemas distribuídos. Se você tem 10 servidores processando logs em paralelo, cada um precisa manter seu próprio set, e no final você precisa fazer a união de todos. A complexidade de memória cresce linearmente com o número de elementos únicos.
A Ideia Genial: Contar Observando Padrões em Bits
Em 2007, Philippe Flajolet e seus colegas publicaram o paper “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”. A ideia central é contraintuitiva: em vez de armazenar os elementos, observe os padrões estatísticos nos hashes desses elementos.
Funciona assim:
- Aplique uma função hash em cada elemento
- Observe quantos zeros consecutivos aparecem no início do hash em binário
- Use a posição do primeiro “1” para estimar a cardinalidade
Por que isso funciona? Pense em lançar uma moeda. A probabilidade de obter “cara” é 1/2. A probabilidade de obter “cara” duas vezes seguidas é 1/4. Três vezes? 1/8. Se você lançar uma moeda 1000 vezes e observar que a maior sequência de “caras” consecutivas foi 10, você pode estimar que lançou aproximadamente 2^10 = 1024 vezes.
Com hashes é a mesma lógica. Se você faz hash de N elementos e observa que o maior número de zeros à esquerda foi R, então N ≈ 2^R. Simples assim.
Do LogLog ao HyperLogLog: Evoluindo a Precisão
O algoritmo original de Flajolet-Martin (1985) usava essa ideia, mas tinha variância alta. O LogLog (2003) melhorou dividindo o hash em múltiplos “buckets” e tirando a média. O HyperLogLog refinou ainda mais usando a média harmônica em vez da aritmética.
A diferença é crucial. A média aritmética é sensível a outliers. Se um bucket tem um valor anômalo, ele puxa toda a estimativa. A média harmônica é mais robusta porque dá menos peso a valores extremos. Matematicamente:
# Média aritmética
media_arit = sum(valores) / len(valores)
# Média harmônica
media_harm = len(valores) / sum(1/v for v in valores)Essa pequena mudança reduziu o erro padrão de 1.30/√m para 1.04/√m, onde m é o número de buckets. Com 1024 buckets, isso significa erro de aproximadamente 3.25% em vez de 4.06%.
Implementando HyperLogLog em Python Puro
Chega de teoria. Vamos implementar. O algoritmo tem duas fases: adição de elementos e estimativa de cardinalidade.
Passo 1: A Função Hash
Precisamos de uma função hash que distribua uniformemente os elementos em um espaço de 32 ou 64 bits. Python tem o hashlib, mas para fins didáticos vou usar uma implementação simples de MurmurHash3:
def murmurhash3_x86_32(data, seed=0):
c1 = 0xcc9e2d51
c2 = 0x1b873593
h1 = seed
length = len(data)
rounded_end = (length & 0xfffffffc)
for i in range(0, rounded_end, 4):
k1 = (data[i] | (data[i+1] << 8) | (data[i+2] << 16) | (data[i+3] << 24))
k1 = (k1 * c1) & 0xffffffff
k1 = ((k1 << 15) | (k1 >> 17)) & 0xffffffff
k1 = (k1 * c2) & 0xffffffff
h1 ^= k1
h1 = ((h1 << 13) | (h1 >> 19)) & 0xffffffff
h1 = (h1 * 5 + 0xe6546b64) & 0xffffffff
k1 = 0
tail = length & 3
if tail >= 3:
k1 ^= data[rounded_end + 2] << 16
if tail >= 2:
k1 ^= data[rounded_end + 1] << 8
if tail >= 1:
k1 ^= data[rounded_end]
k1 = (k1 * c1) & 0xffffffff
k1 = ((k1 << 15) | (k1 >> 17)) & 0xffffffff
k1 = (k1 * c2) & 0xffffffff
h1 ^= k1
h1 ^= length
h1 ^= (h1 >> 16)
h1 = (h1 * 0x85ebca6b) & 0xffffffff
h1 ^= (h1 >> 13)
h1 = (h1 * 0xc2b2ae35) & 0xffffffff
h1 ^= (h1 >> 16)
return h1Passo 2: A Classe HyperLogLog
import math
import struct
class HyperLogLog:
def __init__(self, precision=14):
self.p = precision
self.m = 1 << precision
self.registers = [0] * self.m
if self.m == 16:
self.alpha = 0.673
elif self.m == 32:
self.alpha = 0.697
elif self.m == 64:
self.alpha = 0.709
else:
self.alpha = 0.7213 / (1 + 1.079 / self.m)
def add(self, item):
if isinstance(item, str):
item = item.encode('utf-8')
h = murmurhash3_x86_32(item)
j = h & (self.m - 1)
w = h >> self.p
rho = self._count_leading_zeros(w) + 1
self.registers[j] = max(self.registers[j], rho)
def _count_leading_zeros(self, value):
if value == 0:
return 32 - self.p
count = 0
for i in range(31 - self.p, -1, -1):
if (value & (1 << i)) == 0:
count += 1
else:
break
return count
def count(self):
indicator = sum(2.0 ** (-r) for r in self.registers)
estimate = self.alpha * self.m * self.m / indicator
if estimate <= 2.5 * self.m:
zeros = self.registers.count(0)
if zeros > 0:
estimate = self.m * math.log(self.m / zeros)
if estimate > (1 << 32) / 30.0:
estimate = -(1 << 32) * math.log(1 - estimate / (1 << 32))
return int(estimate)Passo 3: Testando a Implementação
hll = HyperLogLog(precision=14)
n_elements = 1_000_000
for i in range(n_elements):
hll.add(f"user_{i}")
estimativa = hll.count()
erro = abs(estimativa - n_elements) / n_elements * 100
print(f"Elementos reais: {n_elements}")
print(f"Estimativa: {estimativa}")
print(f"Erro: {erro:.2f}%")
print(f"Memória usada: {len(hll.registers)} bytes")Resultado típico:
Elementos reais: 1000000
Estimativa: 1008234
Erro: 0.82%
Memória usada: 16384 bytesMenos de 1% de erro usando apenas 16 KB de memória. Para comparação, um set() com 1 milhão de strings de 10 caracteres usa aproximadamente 50 MB.
Entendendo a Matemática Por Trás da Mágica
Vamos decompor o que acontece quando chamamos add():
- Hash do elemento: “user_123” → 0xA3F5B2C1 (em hex)
- Índice do bucket: Os primeiros 14 bits (0x3F5) → bucket 1013
- Bits restantes: 0xB2C1 → em binário: 1011001011000001
- Zeros à esquerda: 0 zeros antes do primeiro “1” → rho = 1
- Atualiza registro: registers[1013] = max(registers[1013], 1)
Se o hash fosse 0xA3F50001, os bits restantes seriam 0x0001 → 0000000000000001, com 15 zeros à esquerda. Isso indicaria um elemento muito raro, sugerindo alta cardinalidade.
A fórmula final é:
estimate = alpha_m * m^2 / sum(2^(-M[j]))Onde M[j] é o valor máximo observado no bucket j, e alpha_m é uma constante de correção que depende do número de buckets.
Otimizações Avançadas: Sparse vs Dense Representation
Quando a cardinalidade é muito baixa (menos de 10% dos buckets preenchidos), o HyperLogLog original desperdiça memória mantendo milhares de buckets zerados. Redis e outras implementações otimizam isso usando duas representações:
- Sparse: Armazena apenas buckets não-zeros como lista de pares (índice, valor)
- Dense: Array completo quando muitos buckets estão preenchidos
class HyperLogLogSparse(HyperLogLog):
def __init__(self, precision=14):
super().__init__(precision)
self.sparse = {}
self.use_sparse = True
def add(self, item):
if isinstance(item, str):
item = item.encode('utf-8')
h = murmurhash3_x86_32(item)
j = h & (self.m - 1)
w = h >> self.p
rho = self._count_leading_zeros(w) + 1
if self.use_sparse:
self.sparse[j] = max(self.sparse.get(j, 0), rho)
if len(self.sparse) > self.m * 0.1:
self.use_sparse = False
for idx, val in self.sparse.items():
self.registers[idx] = val
self.sparse = None
else:
self.registers[j] = max(self.registers[j], rho)
def count(self):
if self.use_sparse:
temp_registers = [0] * self.m
for idx, val in self.sparse.items():
temp_registers[idx] = val
indicator = sum(2.0 ** (-r) for r in temp_registers)
estimate = self.alpha * self.m * self.m / indicator
else:
indicator = sum(2.0 ** (-r) for r in self.registers)
estimate = self.alpha * self.m * self.m / indicator
if estimate <= 2.5 * self.m:
if self.use_sparse:
zeros = self.m - len(self.sparse)
else:
zeros = self.registers.count(0)
if zeros > 0:
estimate = self.m * math.log(self.m / zeros)
if estimate > (1 << 32) / 30.0:
estimate = -(1 << 32) * math.log(1 - estimate / (1 << 32))
return int(estimate)Mesclando HyperLogLogs: O Poder da Operação Merge
Uma das propriedades mais poderosas do HyperLogLog é que você pode mesclar múltiplas instâncias. Se você tem 10 servidores processando logs em paralelo, cada um mantém seu próprio HLL, e no final você faz o merge:
def merge_hll(*hlls):
if not hlls:
raise ValueError("Pelo menos um HyperLogLog necessário")
p = hlls[0].p
merged = HyperLogLog(precision=p)
for hll in hlls:
if hll.p != p:
raise ValueError("Todos os HLLs devem ter a mesma precisão")
for i in range(merged.m):
merged.registers[i] = max(merged.registers[i], hll.registers[i])
return merged
hll_server1 = HyperLogLog()
hll_server2 = HyperLogLog()
hll_server3 = HyperLogLog()
for user in server1_users:
hll_server1.add(user)
for user in server2_users:
hll_server2.add(user)
for user in server3_users:
hll_server3.add(user)
hll_total = merge_hll(hll_server1, hll_server2, hll_server3)
print(f"Total de usuários únicos: {hll_total.count()}")Isso é impossível com sets tradicionais sem transferir todos os dados. Com HLL, você só precisa enviar 16 KB por servidor.
Precisão vs Memória: Escolhendo o Parâmetro Certo
O parâmetro precision (tipicamente entre 10 e 16) controla o trade-off:
- precision=10: 1024 buckets, erro ~3.25%, memória 1 KB
- precision=12: 4096 buckets, erro ~1.63%, memória 4 KB
- precision=14: 16384 buckets, erro ~0.81%, memória 16 KB (padrão Redis)
- precision=16: 65536 buckets, erro ~0.41%, memória 64 KB
A fórmula do erro padrão é 1.04 / sqrt(m), onde m = 2^precision. Dobrar a precisão (de 14 para 15) reduz o erro pela metade, mas quadruplica a memória.
def erro_esperado(precision):
m = 1 << precision
return 1.04 / math.sqrt(m) * 100
for p in [10, 12, 14, 16]:
print(f"Precision {p}: erro {erro_esperado(p):.2f}%, memória {1 << p} bytes")Casos de Uso Reais: Onde HyperLogLog Brilha
1. Analytics de Tráfego Web: Contar visitantes únicos por dia/mês/ano sem explodir o banco de dados.
2. Detecção de DDoS: Estimar quantos IPs únicos estão acessando seu servidor em tempo real. Se o número explodir, é ataque.
3. Sistemas de Recomendação: Contar quantos itens únicos um usuário interagiu para calcular similaridade.
4. Monitoramento de Logs: Quantas mensagens de erro únicas apareceram nas últimas 24 horas? HLL te dá a resposta em milissegundos.
5. Redes Sociais: “Quantas pessoas únicas viram esse post?” Facebook e Twitter usam variantes de HLL para essas métricas.
Limitações: Quando NÃO Usar HyperLogLog
HyperLogLog é poderoso, mas não é bala de prata:
- Não suporta remoção: Uma vez adicionado, você não pode remover um elemento (para isso, existe o HyperLogLog++, mas é mais complexo)
- Apenas contagem: Você sabe quantos elementos únicos existem, mas não quais são
- Erro sistemático: Mesmo com 0.8% de erro, em 1 bilhão de elementos isso significa ±8 milhões. Para algumas aplicações, isso é inaceitável
- Cardinalidades muito pequenas: Para menos de 1000 elementos, use um set tradicional. O overhead do HLL não compensa
Comparação: HyperLogLog vs Bloom Filter vs Set Tradicional
Essas três estruturas resolvem problemas diferentes, mas são frequentemente confundidas:
- Set tradicional: Armazena todos os elementos, contagem exata, memória O(n)
- Bloom Filter: Testa se um elemento está no conjunto (pode ter falsos positivos), não conta elementos
- HyperLogLog: Estima quantos elementos únicos existem, não armazena os elementos, memória O(1)
Use Set quando precisa de precisão absoluta e os dados cabem na memória. Use Bloom Filter quando precisa testar pertinência rapidamente. Use HyperLogLog quando precisa contar elementos únicos em escala.
Implementação Completa com Testes de Precisão
import random
import string
def teste_precisao(n_elementos, n_testes=10, precision=14):
erros = []
for _ in range(n_testes):
hll = HyperLogLog(precision=precision)
elementos = set()
while len(elementos) < n_elementos:
elem = ''.join(random.choices(string.ascii_letters + string.digits, k=16))
elementos.add(elem)
hll.add(elem)
estimativa = hll.count()
real = len(elementos)
erro = abs(estimativa - real) / real * 100
erros.append(erro)
erro_medio = sum(erros) / len(erros)
erro_max = max(erros)
print(f"Elementos: {n_elementos:,}")
print(f"Erro médio: {erro_medio:.2f}%")
print(f"Erro máximo: {erro_max:.2f}%")
print(f"Memória: {1 << precision} bytes")
print()
teste_precisao(10_000)
teste_precisao(100_000)
teste_precisao(1_000_000)
teste_precisao(10_000_000)Serialização: Salvando e Carregando HyperLogLogs
Em produção, você quer persistir o estado do HLL para não recomeçar do zero a cada restart. Aqui está uma implementação simples de serialização:
import pickle
class HyperLogLogSerializable(HyperLogLog):
def save(self, filepath):
data = {'p': self.p, 'registers': self.registers}
with open(filepath, 'wb') as f:
pickle.dump(data, f)
@classmethod
def load(cls, filepath):
with open(filepath, 'rb') as f:
data = pickle.load(f)
hll = cls(precision=data['p'])
hll.registers = data['registers']
return hll
hll = HyperLogLogSerializable()
for user in users:
hll.add(user)
hll.save('hll_state.pkl')
hll_restaurado = HyperLogLogSerializable.load('hll_state.pkl')
print(f"Cardinalidade: {hll_restaurado.count()}")Conclusão: A Beleza da Aproximação
HyperLogLog é um daqueles algoritmos que muda sua forma de pensar sobre computação. Ele prova que, às vezes, desistir da precisão perfeita em troca de eficiência extrema não é preguiça — é inteligência.
Com menos de 20 KB de memória, você pode estimar cardinalidades de bilhões de elementos com erro menor que 1%. Isso é magia? Não. É matemática aplicada com elegância.
A próxima vez que você precisar contar elementos únicos em escala, antes de comprar mais RAM ou particionar o banco, pergunte-se: eu realmente preciso de precisão absoluta, ou 99% é bom o suficiente?
Na maioria das vezes, a resposta vai te surpreender.
Qual Automação Você Quer Ver?
Agora é sua vez. Qual problema de contagem em escala você enfrentou recentemente? Foi com logs, analytics, ou algo mais exótico? E qual algoritmo probabilístico você quer ver implementado do zero no próximo post? Bloom Filter? Count-Min Sketch? Reservoir Sampling?
Deixa nos comentários que eu implemento, testo em produção, e mostro os resultados reais — incluindo os bugs que encontrei no caminho.
Este post faz parte da série “Python Puro” do AutoMente, onde implementamos algoritmos e estruturas de dados do zero, sem dependências externas. Se você curte entender como as coisas funcionam por baixo do capô, assine o RSS e não perca o próximo.
