1. Planteamiento
Un sistema de registro recibe miles de millones de identificadores de usuario cada día y debe estimar la cantidad de usuarios únicos del día en tiempo real. El presupuesto de memoria es de solo unos pocos KB y se acepta un pequeño error. Diseñe un algoritmo para flujos continuos (streaming) y explique su error, cómo combinar fragmentos y en qué casos no puede reemplazar la deduplicación exacta.
2. Restricciones y aclaraciones
- La entrada es un flujo continuo de identificadores; utilice una sola pasada y memoria fija.
- La consulta solicita la cardinalidad aproximada (conteo de elementos distintos) en una ventana de tiempo.
- Asuma un hash distribuido uniformemente y que cada fragmento utiliza el mismo algoritmo de hash, cantidad de registros y codificación.
- No se requiere eliminación; las ventanas deslizantes, la expiración y los valores exactos con consistencia fuerte requieren estructuras adicionales.
3. Idea central
HyperLogLog (HLL) divide un hash en un índice de registro y los bits restantes. Con m = 2^p registros, los primeros p bits seleccionan un registro; en los bits restantes, la cantidad de ceros iniciales más uno es rho. Cada registro almacena únicamente el mayor rho que haya observado.
La intuición es que una secuencia muy larga de ceros iniciales en un registro es evidencia de que han aparecido más elementos distintos en el espacio muestral. Estime la cardinalidad con una media armónica:
E = alpha_m * m^2 / sum(2^(-M[j]))
Aquí M[j] es el registro j y alpha_m es una constante de corrección basada en la cantidad de registros. Las implementaciones en producción también utilizan corrección por conteo lineal (linear counting) para cardinalidades pequeñas y una corrección para rangos grandes cerca del límite del espacio de hash.
4. Implementación de referencia
El pseudocódigo a continuación muestra la actualización, la estimación y la combinación. Una implementación real debería usar enteros de ancho fijo, una función de hash explícita y un límite para rho.
init(p):
m = 1 << p
M = array(m, fill=0)
add(x):
h = hash64(x)
j = high_bits(h, p)
w = remaining_bits(h, p)
r = leading_zero_count(w) + 1
M[j] = max(M[j], r)
estimate():
z = sum over j of 2^(-M[j])
e = alpha(m) * m * m / z
if e <= small_range_threshold(m) and zero_registers(M) != 0:
e = m * log(m / zero_registers(M))
return large_range_correction_if_needed(e)
merge(other):
require same p, hash function, and register encoding
for j in 0..m-1:
M[j] = max(M[j], other.M[j])5. Complejidad y corrección
Cada elemento requiere un hash y una actualización de registro, por lo que la complejidad temporal es O(1); la complejidad espacial es O(m), independiente de la longitud del flujo. HLL estándar tiene un error estándar relativo de aproximadamente 1.04 / sqrt(m): para m = 16,384, eso es aproximadamente 0.81%. Este es un error de estimación probabilístico, no una promesa de que cada consulta se encuentre en un intervalo fijo.
Debido a que las actualizaciones toman un máximo, agregar el mismo elemento repetidamente no continúa cambiando el estado, lo que otorga idempotencia. Los fragmentos se pueden combinar tomando un máximo registro por registro, siempre que la función de hash, p y la codificación sean idénticos; de lo contrario, sus distribuciones estadísticas son incompatibles.
6. Preguntas de seguimiento y trampas comunes
- HLL devuelve una estimación; no puede reemplazar un conjunto exacto cuando el producto necesita una lista exacta por usuario, un registro de auditoría o una cantidad para facturación.
- Limpiar los registros representa únicamente una nueva ventana. Una ventana deslizante necesita cubetas de tiempo (time buckets), múltiples HLL o una variante con soporte para eliminación, además del manejo de límites y almacenamiento.
- Las colisiones de hash y el sesgo de entrada afectan la estimación. Elija un hash estable de 64 bits o más amplio y estandarícelo a través de los límites de los servicios.
- El estimador armónico sin procesar está sesgado para cardinalidades pequeñas; el conteo lineal utiliza el número de registros en cero para reducir ese sesgo.
7. Lecturas adicionales
- Documentación del comando PFCOUNT y del tipo de datos HyperLogLog en Redis.
- Documentación de cardinalidad aproximada en Snowflake.
- Descripción general de Meta Engineering sobre HyperLogLog en Presto.
8. Puntos de evaluación para la entrevista
Puede explicar el estado
El candidato debe explicar los m = 2^p registros, el índice, el origen de rho y por qué cada registro conserva únicamente un máximo.
Puede derivar el error y las correcciones
Debe proporcionar el orden de magnitud 1.04 / sqrt(m), explicar el conteo lineal para rangos pequeños y la corrección para rangos grandes, y distinguir el error probabilístico de una garantía exacta.
Puede manejar la combinación distribuida
Debe indicar que la combinación es un máximo registro por registro y que cada fragmento debe compartir la función de hash, la precisión y la codificación.
Puede identificar los límites del producto
Debe distinguir la analítica aproximada de las listas exactas, las ventanas deslizantes, la eliminación y la facturación, y explicar por qué esos requisitos necesitan un diseño adicional.