⏱️ Lectura: 12 min
Un firewall que ve millones de paquetes por segundo no puede abrir una entrada en una tabla hash por cada IP distinta que procesa: se queda sin memoria en minutos. Necesita contar sin guardar cada evento, y ahí entra el count-min sketch, una estructura de datos probabilística que estima cuántas veces ocurrió algo usando apenas unos kilobytes.
📑 En este artículo
El count-min sketch resuelve ese problema con una matriz pequeña y varias funciones hash: cambia certeza absoluta por una estimación con error acotado y memoria constante. Es la misma idea detrás de cómo Redis, Apache Flink y los sistemas de detección de anomalías de red cuentan eventos a gran escala sin que la memoria crezca con la cantidad de claves distintas.
TL;DR
- Vas a entender cómo el count-min sketch estima frecuencias sin guardar cada evento individual.
- Vas a poder calcular el ancho y la profundidad de la matriz según el error que estés dispuesto a tolerar.
- Vas a implementar un count-min sketch básico en JavaScript en menos de 30 líneas.
- Vas a saber usar CMS.INITBYDIM, CMS.INCRBY y CMS.QUERY del módulo RedisBloom en Redis.
- Vas a distinguir cuándo conviene un count-min sketch frente a un Bloom filter o un HyperLogLog.
- Vas a conocer el ‘conservative update’, la técnica que reduce la sobreestimación del conteo.
- Vas a identificar los errores más comunes al elegir los parámetros epsilon y delta.
Qué es el count-min sketch y por qué importa
Un mapa hash exacto guarda una entrada por cada clave distinta: si hay diez millones de IPs únicas, la memoria crece con esas diez millones de entradas. El count-min sketch rompe esa relación: su tamaño depende solo del error que tolerás, no de cuántas claves distintas aparezcan en el stream.
Graham Cormode y S. Muthukrishnan publicaron el algoritmo en 2005 como respuesta a un problema concreto: contar frecuencias en flujos de datos demasiado grandes para caber en memoria. Desde entonces se volvió una pieza estándar en sistemas de streaming, bases de datos analíticas y monitoreo de redes.
El canal ya cubrió otras estructuras probabilísticas con propósitos distintos: los filtros de Bloom responden ‘existe este elemento’, HyperLogLog responde ‘cuántos elementos distintos hay’. El count-min sketch responde una tercera pregunta, ‘cuántas veces apareció este elemento’, y esa diferencia importa porque cada una resuelve un problema que las otras dos no pueden.
Cómo funciona por dentro
La estructura es una matriz de w columnas por d filas, todas inicializadas en cero. Cada fila tiene asociada una función hash independiente que mapea cualquier elemento a una columna dentro de esa fila.
Para incrementar un elemento, el algoritmo calcula sus d posiciones (una por fila) y suma el conteo en cada una de esas celdas. Para consultar la frecuencia estimada, vuelve a calcular esas mismas d posiciones y devuelve el mínimo de los valores encontrados.
El mínimo importa porque cada fila puede sufrir colisiones: dos elementos distintos que caen en la misma celda inflan su valor. Tomar el mínimo entre varias filas independientes reduce ese ruido. La garantía matemática es que la estimación nunca es menor al conteo real, pero puede ser mayor.
Cormode y Muthukrishnan demostraron que con un ancho w = ⌈e/ε⌉ y una profundidad d = ⌈ln(1/δ)⌉ (donde e es el número de Euler), la estimación se mantiene dentro de un error de ε·N respecto al conteo real, con probabilidad de al menos 1-δ, siendo N la suma total de todos los conteos.
flowchart TD
A["Evento: IP 203.0.113.7"] --> B["Hash 1"]
A --> C["Hash 2"]
A --> D["Hash 3"]
B --> E["Fila 1, columna h1"]
C --> F["Fila 2, columna h2"]
D --> G["Fila 3, columna h3"]
subgraph Matriz
E
F
G
endEjemplos prácticos con código
El primer ejemplo implementa un count-min sketch desde cero, sin dependencias, para ver la mecánica interna sin la capa de un motor externo.
class CountMinSketch {
constructor(width, depth) {
this.width = width;
this.depth = depth;
this.matrix = Array.from({ length: depth }, () => new Uint32Array(width));
this.seeds = Array.from({ length: depth }, (_, i) => i * 2654435761);
}
hash(item, seed) {
let h = seed;
for (let i = 0; i < item.length; i++) {
h = (h * 31 + item.charCodeAt(i)) >>> 0;
}
return h % this.width;
}
add(item, count = 1) {
for (let row = 0; row < this.depth; row++) {
const col = this.hash(item, this.seeds[row]);
this.matrix[row][col] += count;
}
}
estimate(item) {
let min = Infinity;
for (let row = 0; row < this.depth; row++) {
const col = this.hash(item, this.seeds[row]);
min = Math.min(min, this.matrix[row][col]);
}
return min;
}
}
const cms = new CountMinSketch(2000, 5);
cms.add("203.0.113.7");
cms.add("203.0.113.7");
cms.add("198.51.100.23");
console.log(cms.estimate("203.0.113.7")); // 2, salvo colisionCada llamada a add incrementa cinco celdas (una por fila); estimate vuelve a calcular esas cinco posiciones y devuelve la menor. Con w=2000 y d=5, dos IPs distintas rara vez colisionan en las cinco filas a la vez.
El segundo ejemplo usa el módulo RedisBloom, que expone el count-min sketch como comandos nativos de Redis en lugar de reimplementarlo en la aplicación.
redis-cli CMS.INITBYDIM ip_counter 2000 5
redis-cli CMS.INCRBY ip_counter 203.0.113.7 1
redis-cli CMS.QUERY ip_counter 203.0.113.7El primer comando crea la matriz con ancho 2000 y profundidad 5. El segundo incrementa el contador asociado a esa IP. El tercero devuelve la estimación actual: en este ejemplo, 1.
const Redis = require("ioredis");
const redis = new Redis();
await redis.call("CMS.INITBYDIM", "ip_counter", 2000, 5);
await redis.call("CMS.INCRBY", "ip_counter", "203.0.113.7", 1);
const estimado = await redis.call("CMS.QUERY", "ip_counter", "203.0.113.7");
console.log(estimado); // ["1"]Esta versión delega la matriz y el hashing a Redis, lo que permite compartir el mismo sketch entre varios procesos sin coordinarlos manualmente.
sequenceDiagram
participant C as Cliente
participant R as Redis
C->>R: CMS.INCRBY ip_counter 203.0.113.7 1
R-->>C: OK
C->>R: CMS.QUERY ip_counter 203.0.113.7
R-->>C: estimacion aproximada
Note over C,R: la estimacion nunca es menor al conteo realCómo empezar paso a paso
Para probarlo hoy mismo sin instalar nada en tu sistema, levantá Redis Stack en Docker:
docker run -d --name redis-stack -p 6379:6379 redis/redis-stack:latestCon el contenedor corriendo, creá el sketch y probá los tres comandos básicos:
redis-cli CMS.INITBYDIM visitas_por_pagina 2000 5
redis-cli CMS.INCRBY visitas_por_pagina /blog/count-min-sketch 1
redis-cli CMS.QUERY visitas_por_pagina /blog/count-min-sketchPara confirmar que la estructura está activa y con los parámetros esperados, usá CMS.INFO, que devuelve el ancho, la profundidad y la suma total de conteos registrados:
redis-cli CMS.INFO visitas_por_pagina
# 1) width
# 2) (integer) 2000
# 3) depth
# 4) (integer) 5
# 5) count
# 6) (integer) 1Si el ancho o la profundidad no coinciden con los que esperabas, el sketch fue creado con otros parámetros y hay que recrearlo: no se puede redimensionar una vez inicializado.
Casos de uso reales
La detección de heavy hitters en tráfico de red es el caso clásico: identificar qué IPs o qué flujos concentran el grueso del tráfico sin mantener una tabla de flujo completa, algo inviable cuando hay millones de conexiones simultáneas.
Twitter usó una estructura equivalente en su biblioteca Algebird para contar apariciones de hashtags y términos en streams de tweets, donde guardar un contador exacto por cada palabra distinta habría sido impracticable a esa escala.
Motores de bases de datos analíticas usan sketches parecidos para estimar la selectividad de una columna antes de elegir un plan de ejecución, sin necesidad de escanear la tabla completa. Proyectos como Apache DataSketches empaquetan el count-min sketch junto a otras estructuras probabilísticas para pipelines de datos a gran escala.
💡 Tip: si tu objetivo es limitar peticiones por usuario (rate limiting), un count-min sketch con ventana temporal (reiniciando la matriz cada cierto intervalo) suele consumir muchísima menos memoria que un contador exacto por usuario.
Errores comunes y buenas prácticas
El error más frecuente es tratar la estimación como un número exacto. El count-min sketch nunca subestima, pero sí puede sobreestimar, así que no es apto para decisiones donde un falso positivo por sobreconteo sea inaceptable, como facturación exacta por evento.
Otro error es elegir un ancho o una profundidad arbitrarios. Si el error tolerado ε es muy pequeño, el ancho w crece proporcionalmente, y si la probabilidad de fallo δ es muy exigente, la profundidad d crece con ella: conviene calcular ambos valores en función del presupuesto de memoria real disponible, no adivinarlos.
Las distribuciones muy sesgadas (unos pocos elementos con conteos enormes, el resto con conteos bajos) son las que más sufren: un elemento con millones de ocurrencias puede inflar la estimación de elementos que colisionan en su misma celda. Aumentar la profundidad o aplicar conservative update mitiga ese efecto.
⚠️ Ojo: un count-min sketch básico no soporta eliminar o decrementar elementos de forma confiable; si tu caso de uso necesita eso, mirá la variante Count Sketch antes de forzar la estructura básica.
Comparativa con alternativas
| Estructura | Qué responde | Memoria | Cuándo usarla |
|---|---|---|---|
| Hash map exacto | Frecuencia exacta | Crece con claves distintas | Pocos elementos o memoria abundante |
| Bloom filter | ¿Existe el elemento? | Fija (bits) | Verificar membresía, no frecuencia |
| HyperLogLog | ¿Cuántos elementos distintos hay? | Fija (unos KB) | Cardinalidad aproximada (COUNT DISTINCT) |
| Count-Min Sketch | ¿Cuántas veces apareció? | Fija (w × d) | Frecuencias aproximadas en streams masivos |
| Count Sketch | Frecuencia con menor sesgo | Fija, similar a CMS | Cuando la sobreestimación sistemática es un problema |
Profundizando: conservative update y variantes avanzadas
El conservative update es una optimización simple pero efectiva: en vez de sumar el conteo completo a las d celdas, primero calculá cuál sería el nuevo valor mínimo entre esas celdas y subí cada una solo hasta ese valor, nunca más allá. Esto reduce la sobreestimación acumulada sin cambiar la lógica de consulta.
La variante Count Sketch agrega un signo aleatorio (+1 o -1) por cada función hash, y en la consulta devuelve la mediana en lugar del mínimo. El resultado es un estimador sin sesgo sistemático, aunque a diferencia del count-min sketch, sí puede subestimar el conteo real.
Cuando el problema es identificar los k elementos más frecuentes (top-k) en lugar de estimar frecuencias individuales, el algoritmo Space-Saving de Misra-Gries suele ser más preciso con memoria similar, porque mantiene explícitamente los candidatos más pesados en vez de una matriz genérica.
Una propiedad clave para sistemas distribuidos es la mergeabilidad: dos count-min sketches con el mismo ancho, profundidad y funciones hash se pueden combinar sumando sus matrices celda por celda. Esto permite que cada nodo de un cluster cuente su porción del stream por separado y se agreguen los resultados al final, sin coordinación previa.
flowchart TD
Q["Que necesitas saber?"] --> M["Existe el elemento?"]
Q --> D["Cuantos distintos hay?"]
Q --> F["Cuantas veces aparecio?"]
M --> BF["Bloom filter"]
D --> HLL["HyperLogLog"]
F --> CMS["Count-Min Sketch"]📖 Resumen en Telegram: Ver resumen
Tu próximo paso: levantá Redis Stack con el comando de Docker de este artículo, corré CMS.INCRBY sobre un archivo de logs real y comparalo contra un conteo exacto con awk o uniq -c para ver el margen de error en la práctica.
Preguntas frecuentes
¿El count-min sketch puede dar un resultado menor al conteo real?
No. La estructura solo puede sobreestimar, nunca subestimar, porque toma el mínimo entre varias filas que solo suman valores positivos.
¿Cómo elijo el ancho y la profundidad de la matriz?
El ancho w se calcula como ⌈e/ε⌉ y la profundidad d como ⌈ln(1/δ)⌉, donde ε es el error tolerado y δ la probabilidad de fallo aceptada. Menor error exige más ancho; menor probabilidad de fallo exige más filas.
¿Un count-min sketch se puede fusionar con otro?
Sí, siempre que ambos usen el mismo ancho, profundidad y funciones hash. Fusionarlos es sumar sus matrices celda por celda, lo que lo hace ideal para conteos distribuidos entre varios nodos.
¿Sirve para contar elementos que después quiero eliminar?
La versión básica no soporta decrementos de forma confiable. Para eso existe el Count Sketch, una variante con signos aleatorios que permite estimaciones sin sesgo, aunque puede subestimar.
¿Qué diferencia hay con un Bloom filter?
Un Bloom filter responde si un elemento existe o no; el count-min sketch responde cuántas veces apareció. Resuelven preguntas distintas y suelen combinarse en el mismo sistema.
¿Qué es el conservative update?
Es una optimización donde, al incrementar un elemento, cada celda solo sube hasta el nuevo valor mínimo necesario en vez de sumarle el conteo completo, lo que reduce la sobreestimación acumulada.
Referencias
- Wikipedia: Count-min sketch: descripción formal del algoritmo, autores originales y garantías matemáticas.
- GitHub: RedisBloom: implementación open source del módulo que expone CMS.INITBYDIM, CMS.INCRBY y CMS.QUERY en Redis.
- Apache DataSketches: biblioteca de estructuras probabilísticas, incluido el count-min sketch, usada en pipelines de datos a gran escala.
- Redis: documentación oficial del proyecto y de sus módulos de estructuras probabilísticas.
📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.
Imagen destacada: Foto de Logan Voss en Unsplash
0 Comentarios