¿Cómo contar millones de usuarios de Internet con una moneda? Un truco matemático ahorra gigabytes de memoria

Calcular 100 millones de visitantes únicos de un sitio web se puede hacer gastando apenas 12 KB de memoria. Para comparar, a un contador convencional que guarda los identificadores de cada usuario le harían falta cientos de megabytes. La enorme diferencia la permite el algoritmo HyperLogLog, que estima la cantidad de personas mediante probabilidades y combinaciones raras de ceros y unos. Además, es posible entender su funcionamiento con una moneda corriente.

Imaginemos un gran sitio de noticias que recibe millones de visitantes diarios. Un lector abre diez artículos, otro vuelve varias veces al día, un tercero actualiza la página cada cinco minutos. El sistema de analítica debe saber cuántas personas distintas visitaron el sitio y no contar las visitas repetidas como nuevos visitantes. El método más obvio requiere almacenar identificadores de usuarios y comprobar cada nueva visita en una lista enorme. Pero cuanto mayor es la audiencia, más memoria hay que asignar.

Los matemáticos encontraron una solución inesperada. En lugar de guardar todos los identificadores, se pueden recordar eventos raros y estimar el número total de participantes por su frecuencia. En la base del truco matemático hay una regularidad sencilla que es fácil de comprobar lanzando una moneda.

La probabilidad de sacar cara en un lanzamiento es del 50%. Sacar dos caras seguidas es más difícil, la probabilidad baja al 25%. Tres caras seguidas ocurren con una probabilidad del 12,5%, y diez caras al comienzo de una serie de lanzamientos aparecen en promedio sólo en uno de cada 1024 casos. Con cada cara adicional que salga del lado deseado, la combinación se vuelve el doble de rara.

Ahora imaginemos a una persona que lanza la moneda muchas veces y anota la racha más larga de caras que ha salido desde el inicio de un intento. Si el récord alcanza diez, se puede suponer que la persona hizo alrededor de mil intentos. Claro que la secuencia inusual podría aparecer mucho antes o después. Pero la longitud de la racha récord ya permite estimar aproximadamente el número de lanzamientos, incluso si nadie los contó exactamente.

HyperLogLog aplica un principio parecido a los datos digitales. Pero en lugar de una moneda, el ordenador usa ceros y unos. Cada identificador de usuario el programa lo pasa por una función hash que transforma la información original en una secuencia de bits de longitud fija. Una buena función hash distribuye los valores obtenidos de forma bastante uniforme, por lo que los bits individuales se pueden considerar como aleatorios.

A continuación, el programa busca cuántos ceros consecutivos hay al inicio de una parte determinada de la secuencia. Diez ceros aparecen aproximadamente una vez entre mil valores aleatorios; veinte ceros son aún más raros, aproximadamente una vez entre un millón. Cuanto más larga sea la racha detectada, más identificadores únicos habrá procesado probablemente el sistema.

Hay también una característica importante. Si un visitante abre el sitio veinte veces, la función hash dará el mismo resultado cada vez para el mismo identificador. Las visitas repetidas no aumentan la racha máxima de ceros. Por eso el contador puede estimar el número de usuarios únicos sin guardar la lista completa de visitas.

Sin embargo, basarse en un único récord es arriesgado. Veinte ceros seguidos pueden aparecer por casualidad incluso entre una cantidad pequeña de valores, y el programa sobreestimaría mucho el conteo. Para reducir la influencia de la suerte, HyperLogLog reparte los identificadores entrantes entre muchas agrupaciones. En cada grupo el algoritmo registra la longitud máxima de la racha de ceros y luego combina los resultados mediante una fórmula matemática. El cálculo considera las cifras de todos los grupos y atenúa la influencia de récords excesivamente grandes.

El ahorro de memoria es impresionante. Por ejemplo, la implementación de HyperLogLog en Redis utiliza 16 384 pequeños registros, que ocupan alrededor de 12 KB. Incluso si el contador procesa mil millones de valores únicos, no necesitará asignar memoria para mil millones de registros. Según la documentación de Redis, el error relativo estándar es de aproximadamente 0,81%. Un conteo individual puede fallar más, pero para muchas tareas analíticas de precisión media es suficiente.

Para comparar, si se almacenan 100 millones de identificadores de ocho bytes cada uno, sólo los valores ocuparían 800 MB. Se necesitaría memoria adicional para búsquedas rápidas y comprobación de repeticiones. HyperLogLog se conforma con unos pocos kilobytes, porque solo guarda un pequeño resumen estadístico.

El algoritmo resultó útil también para agregar estadísticas. Supongamos que un gran sitio está atendido por decenas de servidores. Cada servidor calcula por su cuenta su audiencia y luego el sistema combina los resultados sin recopilar una base enorme común de identificadores. De forma análoga, se puede calcular el número aproximado de visitantes de una semana a partir de contadores diarios separados, sin sumar a las mismas personas varias veces.

HyperLogLog ya lleva tiempo funcionando en servicios populares. Google usa HyperLogLog++, una versión mejorada del algoritmo, en Google Analytics 4 para estimar el número de usuarios y sesiones. Por eso algunos indicadores de audiencia en la analítica de Google pueden diferir ligeramente de los valores exactos. Un enfoque similar sirve para contar consultas de búsqueda únicas, analizar enormes flujos de eventos de red y estimar la cantidad de direcciones distintas que contactan con un servidor.

El propio algoritmo se presentó en 2007. Los matemáticos Philippe Flajolet, Éric Fusy, Olivier Gandouet y Frédéric Meunier demostraron que se puede estimar el número de elementos incluso en conjuntos que superan mil millones de registros, con un error típico de alrededor del 2%, usando sólo 1,5 KB de memoria. Posteriormente desarrolladores de otros sistemas mejoraron la precisión y adaptaron el método para procesar flujos masivos de información.

HyperLogLog tiene limitaciones. El algoritmo no permite saber quién visitó el sitio, recuperar la lista de usuarios ni obtener un número exacto de forma garantizada. Además, una misma persona puede contarse varias veces si el sitio asigna distintos identificadores a sus dispositivos o navegadores. Pero cuando hay que estimar rápidamente una audiencia de decenas de millones de personas, un pequeño error suele ser un precio aceptable por el enorme ahorro de recursos. En lugar de guardar una base de datos inmensa, el ordenador almacena unos pocos miles de números y, a partir de las raras cadenas de ceros, reconstruye la escala aproximada del flujo.