Apache DataSketches documenta que su CPC Sketch ahorra entre un 30% y un 40% de memoria frente a HyperLogLog con la misma precisión, cuando ambos sketches se serializan para guardarse o enviarse por red (fuente). ScopeDB, un motor de bases de datos, migró su conteo de valores únicos a ese sketch a comienzos de este año, y terminar ese port a Rust significó reconstruir con inteligencia artificial un generador de tablas que Apache DataSketches había perdido hace años.
Qué es un sketch probabilístico y qué sacrifica a cambio de memoria
Un sketch probabilístico es una estructura de datos que se actualiza elemento por elemento, mediante una función de hash, y que responde una pregunta agregada (cuántos valores distintos hay, cuál es la frecuencia de uno de ellos) con un margen de error acotado. La diferencia con guardar los datos completos es radical: un HashSet crece con cada valor nuevo, mientras que un sketch como HyperLogLog o CPC ocupa un tamaño fijo, decidido de antemano, sin importar si el flujo trae mil o mil millones de valores.
ScopeDB llegó a este problema por una razón concreta: necesitaba implementar approx_count_distinct, la función que estima cuántos valores únicos hay en una columna sin materializarlos todos en memoria (fuente). Esa necesidad (contar únicos en consultas analíticas de gran volumen) es la misma que enfrenta cualquier motor que reporta usuarios activos o consultas distintas por hora.
Cómo HyperLogLog cuenta sin guardar un solo valor
El mecanismo de HyperLogLog es el que casi todos los libros de texto enseñan primero. Cada elemento se hashea y ese hash decide dos cosas: en cuál de los K buckets cae y cuántos ceros tiene al principio (el 'leading zero count'). Cada bucket guarda solo el máximo de ceros iniciales que vio hasta ese momento, típicamente en 4 a 6 bits; cualquier otro hash que caiga en ese mismo bucket, si no supera ese máximo, se descarta sin dejar rastro (fuente). Cuando el sketch entra en modo denso, cada bucket mantiene un registro de ancho fijo, así que el tamaño total deja de depender de cuántos elementos distintos se procesaron.
Ese diseño es elegante, pero tiene un costo estadístico: al quedarse solo con el máximo por bucket, HyperLogLog descarta el resto de la información que pasó por ahí. Fue exactamente ese descarte el que Kevin J. Lang, investigador de Yahoo! Research, decidió cuestionar en 2017.
Cada bucket de HyperLogLog guarda entre 4 y 6 bits: solo el máximo de ceros iniciales visto.
CPC Sketch: la matriz que rescató el proceso FM85 original
En su paper Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm (2017), Lang propuso volver a una idea más antigua: en vez de quedarse solo con el máximo por bucket, guardar la matriz completa de K×64 bits del proceso FM85 original, el mismo coupon collector del que nace esta familia de algoritmos (fuente). Cada vez que la fila r ve un hash con c ceros iniciales, el sketch marca con un 1 el bit en la posición (r, c), sin descartar nada.
Tener esa matriz completa, en vez de un solo máximo, le permite a CPC combinar un estimador HIP (que corre en tiempo real, mientras llegan los datos) con un estimador ICON pensado para poder fusionarse (mergeable) sin reprocesar los datos originales; la combinación es más eficiente estadísticamente que el máximo simple de HyperLogLog (fuente). El precio aparece al guardar o transmitir el sketch: para que esa matriz no ocupe más que un HyperLogLog equivalente, CPC adapta su formato a la densidad de datos. Con pocos valores únicos usa una tabla dispersa de pares (fila, columna); con cardinalidades medias y altas combina una ventana deslizante de 8 bits, codificación Huffman de longitud limitada y permutaciones de columnas, para acercarse al límite teórico de entropía. Según la documentación de Apache DataSketches, ese formato comprimido ocupa entre 30% y 40% menos espacio que HyperLogLog con la misma precisión (fuente).
Por qué ScopeDB no se quedó con el primer crate de Rust que encontró
Antes de llegar a Apache DataSketches, el equipo de ScopeDB ya tenía una implementación de HyperLogLog funcionando: el crate open source cardinality-estimator, de Cloudflare. Lo abandonaron como dependencia directa porque el ecosistema de HLL en Rust era, en ese momento, desigual: ese crate se apoyaba fuerte en código unsafe y trucos manuales de empaquetado de bits, así que para mantener algo auditable y bajo su propio control terminaron bifurcándolo (fork) y manteniendo una copia interna dentro de ScopeDB (fuente). Es un detalle que la nota original menciona de paso, antes de llegar al tema central, pero resume bien el estado del ecosistema de sketches en Rust hace poco más de un año: maduro en Java y C++, inestable en Rust.
La salida fue portar Apache DataSketches, que ya tenía un HllSketch probado en producción además del más eficiente CpcSketch, pero solo en Java y C++. La propia comunidad de Apache DataSketches quería un port oficial a Rust; el autor se asoció con otros desarrolladores Rust especializados en algoritmos de sketching para construir datasketches-rust, empezando por HllSketch, y ScopeDB cambió su conteo de distintos a esa implementación poco después (fuente). CpcSketch llegó después, a fines de enero, vía el PR-75, y corre en producción en ScopeDB desde entonces, hace ya más de seis meses (fuente).
Qué significa esto para vos si programás en Rust y tu servicio necesita contar valores únicos a escala (telemetría, analítica, deduplicación de eventos): antes de depender de un crate que resuelve HLL a pura fuerza de código unsafe, revisá si datasketches-rust ya cubre tu caso. El HllSketch lleva más tiempo en producción; el CpcSketch es más nuevo, pero si tu cuello de botella es el tamaño serializado del sketch (porque lo guardás por cada partición o lo mandás por red entre nodos), el ahorro de 30-40% frente a HLL puede importar más que la madurez. Para un equipo LATAM que corre analítica sobre Rust en su propio Kubernetes o en un PaaS, la pregunta no es teórica: decide cuánta RAM reservar para contar usuarios únicos por hora.
El port de CpcSketch a Rust vía PR-75 corre en producción en ScopeDB desde fines de enero.
El código que faltaba: tablas mágicas sin generador
Portar CpcSketch desde las implementaciones originales en C++ y Java trajo un problema distinto al de programar el algoritmo: varias tablas de consulta venían con los valores escritos a mano en el código fuente, sin rastro de cómo se habían calculado. En total eran cuatro familias de tablas, repartidas entre compression_data.rs y estimator.rs: 23 tablas estáticas de codificación Huffman, 16 permutaciones de columnas para la ventana deslizante, 23 conjuntos de coeficientes de un polinomio de grado 19 para corrección estadística, y 4 tablas empíricas de cuantiles para los intervalos de confianza (fuente).
La práctica habitual del autor al portar una tabla de este tipo es derivar los valores desde cero dentro de un test unitario y compararlos, elemento por elemento, contra el arreglo estático original; así lo hizo con la tabla kxp_byte_lookup, recalculando cada uno de sus 256 valores a partir de la lógica de bits que los genera (fuente). Pero para las tablas de CompressionData y del estimador ICON no existía ningún código generador en ninguno de los repositorios de Apache DataSketches. El único rastro que quedaba era un comentario heredado con dos comandos de compilación en OCaml, que ejecutaban archivos llamados columnProbabilities.ml y generateHuffmanCodes.ml para producir una tabla en C (fuente). Esos archivos .ml nunca aparecieron en ninguno de los repositorios públicos del proyecto.
Sin el generador, el autor abrió el issue ISSUE-720 en datasketches-java preguntando dónde vivía ese código fuente (fuente). Lee Rhodes, mantenedor del proyecto, respondió en el hilo: contó que Kevin hacía la mayoría de sus simulaciones y su modelado matemático en OCaml, que ese código vivía solo en su computadora personal y que esa computadora ya no existe; para Rhodes, su código personal murió con él, y aunque alguien conservara una copia de esa máquina, sería como buscar una aguja en un pajar. Kevin Lang murió en abril de 2019 (fuente). Con el generador original dado por perdido, la reconstrucción terminó resolviéndose con un sistema de agentes de IA, Gemini 4 Carbon Orchestrator combinado con un 'Swarm' de agentes, que recreó la lógica de esos cuatro generadores (fuente). La validación, otra vez, fue la misma disciplina que ya usaba el autor para las tablas con generador conocido: comparar, tabla por tabla y valor por valor, la salida reconstruida contra los arreglos estáticos que ya corrían en producción en Java y C++.
flowchart TD A["Comentario legado: 2 comandos ocamlopt"] --> B["Buscar columnProbabilities.ml y generateHuffmanCodes.ml"] B --> C{"Archivos encontrados"} C -- "No, en ningun repo" --> D["ISSUE-720 en datasketches-java"] D --> E["Reconstruir con Gemini 4 Carbon Orchestrator + Swarm"] E --> F["Validar cada tabla contra los arreglos estaticos de Java y C++"] HyperLogLog, CPC Sketch o el crate de Cloudflare: cómo elegir
Para un equipo que arranca hoy un proyecto en Rust y necesita contar valores únicos, las tres opciones que aparecen en esta historia resuelven el mismo problema con compromisos distintos.
OpciónQué guardaPunto fuertePunto débilHyperLogLog (diseño clásico)Un máximo de ceros iniciales por bucketSimple de implementar y de razonar; décadas de uso en producción en distintos lenguajesDescarta información estadística útil; ocupa más al serializarse que CPC con la misma precisiónCPC Sketch (Apache DataSketches)La matriz completa K×64 del proceso FM85Ahorra 30-40% de memoria serializada frente a HyperLogLog (fuente)Formato de compresión complejo (Huffman, permutaciones, tablas de corrección); su port a Rust es más recientecardinality-estimator (crate de Cloudflare)Variante de HyperLogLog implementada directamente en RustDisponible antes de que existiera un port oficial de DataSketchesSe apoya en código unsafe y empaquetado manual de bits, difícil de auditar
Cuándo no conviene usar un sketch probabilístico
Un sketch probabilístico nunca da un número exacto: si tu caso de uso es facturación, cumplimiento regulatorio o cualquier conteo que tenga que cuadrar al último dígito, un HyperLogLog o un CPC no reemplazan un HashSet o un COUNT DISTINCT exacto sobre una tabla chica.
El port de CpcSketch a Rust, además, es joven comparado con las implementaciones en Java y C++ que lleva años probando Apache DataSketches: lleva en producción en ScopeDB algo más de seis meses, no décadas. Un equipo con requisitos estrictos de estabilidad puede preferir esperar a que el port acumule más uso real, o seguir en Java/C++ si ya tiene esa pila montada.
Y hay un riesgo más puntual, propio de esta historia: las tablas de compresión de CPC que no tenían generador público se reconstruyeron con un sistema de IA y luego se validaron manualmente contra los valores de referencia (fuente). Quien tome ese código para un fork propio debería repetir esa validación, tabla por tabla, en vez de asumir que la reconstrucción es correcta solo porque ya está en un repositorio público; conviene revisar la documentación oficial del proyecto (Apache DataSketches) antes de confiar en una implementación de terceros.
Preguntas frecuentes sobre HyperLogLog y CPC Sketch
¿CPC Sketch siempre gana en memoria a HyperLogLog?
Solo al serializarse: la ventaja de 30-40% que documenta Apache DataSketches aplica al tamaño guardado en disco o enviado por red, gracias a su codificación Huffman y permutaciones de columnas (fuente). Mientras el sketch vive solo en memoria, sin serializarse, la diferencia práctica es menor.
¿Se pueden combinar sketches calculados en nodos distintos?
Sí: HyperLogLog comparte esa propiedad por el mismo mecanismo ya descrito, fusionar dos sketches es simplemente quedarse, bucket por bucket, con el máximo de los máximos. CPC lleva esa misma idea a su estimador ICON, diseñado para ser mergeable sin reprocesar los datos originales (fuente), lo que permite sumar conteos parciales de distintas particiones de una consulta analítica.
Referencias
- Reverse-Engineering Kevin J. Lang's Lost OCaml Code in Apache DataSketches: fuente primaria de los datos, cifras y la cronología de este artículo.- PR-75 en apache/datasketches-rust: el pull request que incorporó CpcSketch al port oficial en Rust.- Apache DataSketches: documentación oficial del proyecto y de sus distintos sketches.- Hilo en Hacker News: discusión de la comunidad sobre la reconstrucción de las tablas de CPC Sketch.
Seguimos el tema en @programacion.