Si alguien te pregunta cuántas personas había en un concierto, no las cuentas una a una: miras, calculas a ojo y dices “unas cinco mil”. Te puedes equivocar en unos cientos, pero has tardado dos segundos y no has necesitado apuntar el nombre de nadie. Las estructuras de datos probabilísticas hacen exactamente eso: dan una respuesta aproximada, con un error que conoces de antemano, a cambio de usar una fracción minúscula de la memoria.
Anton Zhiyanov, el mismo de Go Concurrency Distilled, ha publicado un repaso a cinco de ellas junto con unsure, un paquete de Go que las implementa usando sólo la biblioteca estándar. Es de esos artículos que te explican algo que conoces de oídas y que, al terminar, por fin entiendes.
Las cinco estructuras
Lo que más ayuda a entender para qué sirven es ver cuánto ocupan comparadas con la solución “exacta” (un map o un set), con las cifras del propio artículo para un millón de elementos:
| Estructura | Para qué | Exacto | Probabilístico | Error |
|---|---|---|---|---|
| Bloom filter | ¿Está este elemento? | ~64 MB | ~1,24 MB | 1 % de falsos positivos |
| Count-min sketch | ¿Cuántas veces ha aparecido? | ~64 MB | ~0,55 MB | 0,01 % del total |
| HyperLogLog | ¿Cuántos distintos hay? | ~64 MB | 16 KB | ~0,8 % |
| T-digest | ¿Cuál es el percentil 99? | 8 MB | ~8 KB | ~0,03 % en rango |
| Top-k | ¿Cuáles son los más frecuentes? | — | ~360 KB para el top 1000 | casi siempre exacto |
Dieciséis kilobytes para contar un millón de elementos distintos. Cuesta creerlo hasta que ves cómo funciona.
Bloom filter. Un array de bits y varias funciones hash: al añadir un elemento se encienden unos cuantos bits, y al consultar se mira si están todos encendidos. Puede decirte que algo está cuando no está (falso positivo), pero nunca que no está cuando sí. Es perfecto para no hacer una consulta cara a disco o a red cuando sabes seguro que el dato no existe. No se pueden borrar elementos ni recorrerlos.
Count-min sketch. Una tabla de contadores con varias filas; cada elemento suma uno en un contador por fila y la estimación es el mínimo de todos. Nunca se queda corto, aunque puede pasarse, y se equivoca más con los elementos raros. Sirve para cosas como limitar peticiones por IP o decidir qué clave merece estar en caché.
HyperLogLog. Se fija en cuántos ceros seguidos tienen los hashes al principio: si has visto un hash que empieza por muchos ceros, es que has visto muchos elementos distintos (como quien deduce que ha tirado muchas monedas porque le han salido diez caras seguidas). Es lo que usan muchas bases de datos para estimar cardinalidades; DuckDB, por ejemplo, guarda estadísticas HyperLogLog en su formato, algo que comenté al hablar de los formatos de archivo de DuckDB.
T-digest. Para percentiles de un flujo de números, como las latencias. Guarda grupos de valores (centroides) pequeños en los extremos y grandes en el centro, así que es más preciso justo donde importa: en el percentil 99 que te despierta de madrugada.
Top-k. Para encontrar los elementos más frecuentes (las URL más pedidas, los usuarios más activos) sin guardar el recuento de todos. Funciona mejor cuando hay unos pocos elementos que destacan mucho sobre el resto, que es lo habitual en el tráfico real.
El paquete unsure
La API es tan sencilla como cabría esperar:
filter := bloom.New(1000, 0.01)
filter.Add([]byte("alice"))
filter.Contains([]byte("alice")) // true
sketch := hll.New()
sketch.Add([]byte("alice"))
sketch.Count() // aproximadamente 1
Se instala con go get github.com/nalgeon/unsure y cada estructura vive en su propio subpaquete (bloom, countmin, hll, tdigest y topk). No arrastra dependencias, y eso, en Go, se agradece.
El artículo incluye comparativas con las librerías habituales (bits-and-blooms, BoomFilters, axiom, influxdata, dgryski…), y en casi todas sale ganando: según los números del autor, el Bloom filter va unas cuatro veces más rápido que bits-and-blooms y el HyperLogLog cuenta entre cientos y miles de veces más rápido que el de axiom. Ojo, son benchmarks del propio autor sobre su propio paquete, así que antes de cambiar nada en producción toca medir con tus datos. Él mismo reconoce que en algunos casos (HyperLogLog con muy pocos elementos) la alternativa es más precisa y ocupa menos.
Por qué me gusta
Lo mejor del artículo no es el paquete, sino que te quita el miedo a estas estructuras. Hay mucho problema del día a día (contar visitantes únicos, saber qué endpoints se llaman más, sacar percentiles de latencia) que resolvemos con un map que crece y crece hasta que un día el proceso se queda sin memoria. Saber que existe una alternativa que ocupa kilobytes y se equivoca menos de un 1 % cambia la forma de plantear el problema. No siempre necesitas la cifra exacta: muchas veces basta con saber que en el concierto había unas cinco mil personas.
