Imagina un servicio de alta carga que procesa un flujo continuo de datos, como registros, direcciones IP e identificaciones de usuarios, generando miles de millones de entradas diariamente. El reto es determinar el número de visitantes únicos en una semana. Un enfoque inicial podría ser usar un HashSet para almacenar estas claves y verificar el tamaño al final. Aunque esta solución parece razonable, se vuelve impráctica con miles de millones de entradas debido a las limitaciones de memoria. Cada dirección IP, que requiere 4 bytes, incurre en un costo significativo por nodos, punteros y hashes, lo que resulta en un consumo de memoria de al menos 50-100 bytes por elemento. Por lo tanto, rastrear mil millones de entradas únicas podría requerir cerca de cien gigabytes de RAM, lo cual es costoso e inviable con múltiples instancias. Sin embargo, existe un algoritmo que puede abordar este problema utilizando aproximadamente 1.5 kilobytes de memoria con un margen de error del 2%, evitando la necesidad de almacenar los datos reales o mantener grandes clústeres. Aquí es donde entra HyperLogLog, un algoritmo estadístico que revoluciona la forma en que contamos elementos únicos en Big Data. HyperLogLog se utiliza en plataformas como Redis, BigQuery, ClickHouse y Presto. Este artículo explorará el funcionamiento de este algoritmo, su implementación en C y su contexto histórico.
HyperLogLog: Contando Valores Únicos en Terabytes de Datos Sin Almacenarlos
Descubre cómo el algoritmo HyperLogLog cuenta visitantes únicos en grandes conjuntos de datos sin necesidad de mucha memoria.
5 min readTecnología