Entrevista de Ingeniería de Datos: ¿Cómo usarías HyperLogLog para conteos únicos distribuidos?

Planteamiento y alcance

Esta es una pregunta de entrevista de ingeniería de datos y procesamiento de transmisiones (stream processing). La plataforma ingesta miles de millones de eventos, realiza consultas por hora, inquilino y región, y permite aproximadamente un 1% de error relativo para los paneles de control (dashboards). La facturación, la aplicación de cuotas y los informes de auditoría aún requieren valores exactos. Aclara el margen de error tolerado, el tipo de ventana, el límite de retraso (lateness bound), la necesidad de operaciones de conjuntos y si el identificador constituye un dato personal.

El banco de preguntas ya cubre streaming, particiones calientes (hot partitions) y arquitecturas de procesamiento por lotes frente a streaming. Este planteamiento se centra en cómo un bosquejo (sketch) de cardinalidad fusionable cambia el costo del conteo de distintos distribuido, en lugar de enfocarse en un producto de base de datos específico.

Qué evalúa el entrevistador

• Si distingues entre cardinalidad, pertenencia y frecuencia en lugar de tratar a HLL como un filtro de Bloom o un Count-Min Sketch.
• Si explicas los sketches de tamaño fijo por partición (shard) y la fusión por el máximo registro por registro en lugar de sumar estimaciones locales.
• Si transformas el error, la tardanza, el reinicio, la privacidad y la exactitud del negocio en contratos verificables.

Una respuesta débil dice "usa Redis HLL porque es pequeño". Una respuesta sólida ofrece una línea base exacta, nombra los modos de falla de la aproximación y define la reproducción (replay), el muestreo y el monitoreo de desviación (drift).

Aclaraciones antes de responder

1. ¿Qué error es aceptable? Un panel de control puede aceptar cerca del 1%; los informes de facturación o cumplimiento normativo necesitan una ruta exacta o una ruta de conciliación calibrada.
2. ¿Las consultas son sobre ventanas fijas o rangos arbitrarios? Los sketches horarios se adaptan a intervalos fijos; los rangos arbitrarios requieren intervalos fusionables con límites y retención explícitos.
3. ¿Con cuánto retraso pueden llegar los eventos? El límite de retraso determina si se debe reabrir un intervalo, retener eventos sin procesar o aceptar una marca de agua (watermark) de finalización.
4. ¿Se requieren intersecciones, diferencias o listados de miembros? HLL es potente para la cardinalidad de unión; la pertenencia, la intersección o la eliminación necesitan otra estructura o un recálculo exacto.

Una respuesta de 30 segundos

"Mantendría un conjunto exacto como línea base de corrección, pero su costo de memoria, shuffle de red y fusión entre particiones crece con los usuarios únicos. Si el panel de control acepta aproximadamente un 1% de error, cada partición mantiene un HyperLogLog de precisión fija indexado por hora, inquilino y región. En el momento de la consulta, tomo el máximo registro por registro a través de los sketches y ejecuto un solo estimador; nunca sumo estimaciones locales. HLL responde a la cardinalidad aproximada de la unión, no a la pertenencia, eliminación o lista de identidades. Utilizo el tiempo del evento y una marca de agua para cerrar intervalos, aceptar tardanzas acotadas y enviar correcciones más antiguas a reproducción exacta. Finalmente, concilio los intervalos cerrados muestreados contra conteos exactos y monitoreo el error relativo, intervalos vacíos, duplicados, fusiones de sketches y riesgos de privacidad."

Respuesta detallada paso a paso

Paso 1: Construir la línea base exacta.

Almacena un conjunto de identificadores de usuario para cada (hour, tenant, region). Es exacto, pero las particiones deben enviar muchos identificadores o realizar un shuffle global. Sumar los valores locales de COUNT(DISTINCT) cuenta dos veces a un usuario presente en múltiples particiones.

Paso 2: Describir el estado de HLL.

Divide un hash estable en un índice de registro y un rango de ceros a la izquierda. Cada entrada actualiza solo su registro con un rango máximo. El estimador deriva una cardinalidad a partir de todos los registros y aplica correcciones para rangos pequeños. No prometas un error universal sin nombrar la precisión, el comportamiento del hash y el rango del estimador.

Paso 3: Explicar la fusión distribuida.

Los sketches para una misma dimensión deben usar la misma cantidad de registros, convención de hash y codificación. Realiza la fusión tomando el máximo en cada registro, no sumando estimaciones. Por lo tanto, los sketches por minuto pueden consolidarse en respuestas horarias sin transferir identificadores sin procesar mediante shuffle.

for each event(user_id, bucket, tenant, region):
    i, rank = hash_and_rank(user_id, precision)
    sketch[bucket, tenant, region][i] = max(sketch[...][i], rank)

merged[i] = max(sketch_a[i], sketch_b[i])
estimate = hll_estimator(merged)

Paso 4: Manejar la tardanza y las ventanas.

Agrupa en intervalos por tiempo del evento y utiliza una marca de agua para marcar los intervalos como definitivos. Acepta actualizaciones solo dentro del límite de tardanza máxima; envía eventos más antiguos a reproducción de registros sin procesar o a una tabla de corrección exacta. HLL no puede eliminar a un solo usuario, por lo que revocar un evento requiere reconstruir el intervalo afectado.

Paso 5: Separar los resultados aproximados de la corrección del negocio.

Un trabajo de conciliación muestrea intervalos cerrados y calcula la verdad con un conjunto exacto o SQL fuera de línea. Registra el error relativo, la dirección del sesgo y las dimensiones con anomalías. Mantén libros contables exactos para facturación, cuotas y eliminación por privacidad; utiliza sketches para observación o estimación de bajo costo.

Paso 6: Controlar el costo y la privacidad.

Limita las combinaciones de dimensiones, la retención de intervalos y los sketches por inquilino para que las etiquetas de alta cardinalidad no generen un estado ilimitado. Normaliza la entrada de hash de manera consistente y gestiona la rotación de claves; autoriza el acceso al sketch. Un sketch no es una garantía de anonimización porque el tamaño agregado aún puede revelar un grupo.

Respuesta de muestra de alta calidad

"Primero preguntaría si el resultado puede ser aproximado. Los conjuntos exactos se adaptan a facturación y auditoría, pero miles de millones de eventos a través de particiones y ventanas extensas hacen que la memoria y el shuffle sean costosos. Para un panel de control con una tolerancia de cerca del 1%, cada partición mantiene un HLL configurado de manera idéntica por intervalo de tiempo y dimensión. Un hash estable actualiza un registro, y la consulta toma los máximos registro por registro antes de ejecutar el estimador; sumar estimaciones locales contaría a los usuarios dos veces.

Cierro los intervalos basados en el tiempo del evento con una marca de agua y mantengo una ventana de tardanza acotada. Las correcciones fuera de esa ventana pasan por una reproducción de registros sin procesar porque HLL no puede eliminar un solo elemento. Los metadatos registran la precisión, la convención de hash y los límites del intervalo para que los sketches sigan siendo fusionables. Monitoreo el tamaño del sketch, la latencia de fusión, la tasa de duplicados y el error relativo, y concilio los intervalos muestreados con conjuntos exactos. La facturación y la eliminación por cumplimiento normativo se mantienen exactas; HLL es una capa de aceleración analítica."

Errores comunes

• Sumar estimaciones de las particiones → el mismo usuario puede aparecer en varias particiones → fusiona registros y luego estima una sola vez.
• Afirmar que HLL puede responder si un usuario apareció → almacena un resumen estadístico → usa un conjunto o filtro de Bloom para la pertenencia y declara los falsos positivos.
• Restar un evento tardío o eliminado de un sketch → el máximo de un registro no tiene un contribuyente reversible → reconstruye el intervalo o utiliza una tabla de corrección exacta.
• Fusionar formatos de precisión o hash arbitrarios → los significados de los registros difieren → almacena metadatos de precisión, hash, codificación y versión.
• Tratar un sketch como protección de privacidad → el tamaño agregado aún puede filtrar información de grupos → combina autorización, dimensiones mínimas, retención y revisión de privacidad.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: El negocio solicita cualquier rango de 37 días. ¿Cómo lo divides en intervalos?

Los sketches por minuto generan más estado, pero una consulta puede fusionar minutos contiguos; los sketches horarios y diarios reducen las lecturas para rangos extensos. Los intervalos multinivel necesitan límites explícitos y no superpuestos. El planificador elige la combinación no superpuesta más gruesa y rellena los bordes entre niveles con intervalos más finos.

Pregunta de seguimiento 2: La eliminación de un usuario debe surtir efecto dentro de 24 horas. ¿Puede permanecer HLL?

HLL no puede realizar eliminaciones por usuario. Mantén un índice de eventos exacto borrable o un mapeo cifrado, reconstruye los intervalos afectados y oculta las versiones antiguas en la capa del panel de control; trata al sketch como no definitivo. Si la regulación exige evidencia de eliminación, utiliza el registro de eliminación exacto y la verificación por reproducción.

Pregunta de seguimiento 3: El error salta del 1% al 8% después de una fusión. ¿Qué inspeccionas primero?

Compara los metadatos del sketch: precisión, semilla de hash, codificación de registros y versión. Verifica si una partición serializó una estimación en lugar de los registros, fusionó la misma entrada dos veces o recibió una distribución de hash anómala. Reproduce un conjunto pequeño paso a paso con una partición, dos particiones y una fusión para aislar defectos del estimador o de serialización.