HyperLogLog contó miles de millones de elementos distintos en kilobytes

La cardinalidad exacta —cuántos usuarios, direcciones IP o consultas de búsqueda distintos han aparecido— normalmente requiere memoria proporcional al número de elementos distintos, lo cual es imposible a escala de internet. En 2007, Philippe Flajolet y sus colegas de INRIA publicaron HyperLogLog, un boceto probabilístico que estima cardinalidades superiores a mil millones con una precisión de aproximadamente el 2 por ciento usando alrededor de 1,5 kilobytes de memoria.

El truco se basa en una intuición de lanzamiento de moneda: aplicar un hash a cada elemento para obtener un número aleatorio uniforme y observar la racha más larga de ceros iniciales. Una racha de n ceros es rara —probabilidad 2^-n—, así que cuando aparece, el conjunto probablemente sea lo bastante grande como para haberla producido, y 2^n es una buena estimación de la cardinalidad. HyperLogLog divide el flujo en muchos subconjuntos, mantiene un registro por subconjunto que guarda su racha de ceros más larga y los combina con una media armónica para que los valores atípicos no distorsionen la estimación.

El método desciende del algoritmo de Flajolet-Martin de 1984 y del algoritmo LogLog. La ingeniería que lo hizo listo para producción llegó en el artículo de 2013 «HyperLogLog in Practice», de Heule, Nunkesser y Hall en Google, que corrigió problemas de sesgo y de dispersión para cardinalidades grandes y pequeñas.

Redis convirtió HyperLogLog en una característica de producto: sus comandos PFADD, PFCOUNT y PFMERGE estiman hasta 2^64 elementos distintos con hasta 12 KB de memoria por clave y un error estándar del 0,81 por ciento, y los bocetos se fusionan, de modo que los recuentos diarios se combinan sin volver a leer el flujo original.

Estimar recuentos a partir de los ceros iniciales del hash

Un hash convierte datos arbitrarios en un número aleatorio uniforme con la misma cardinalidad

La racha más larga de ceros iniciales es una estimación natural y observable del tamaño del conjunto

La división en registros más una media armónica cancela el ruido

Los bocetos se fusionan, de modo que los recuentos diarios se combinan sin almacenar el flujo original

Cuando la respuesta solo necesita ser aproximada, deja de almacenar los datos: guarda un pequeño boceto cuya aleatoriedad revele el tamaño e intercambia un error acotado por una escala ilimitada.

HyperLogLog se convirtió en un componente estándar en analítica y bases de datos: Redis lo incluye como tipo de dato, y las mejoras del artículo de Google de 2013 son lo que lo hizo usable a escala en sistemas de producción. La lógica del boceto —guardar un pequeño registro de evidencia, no los datos— también sustenta estructuras posteriores como MinHash y Count-Min Sketch.