Entendiendo los filtros Bloom con ejemplos

 (llimllib.github.io)
2 puntos por GN⁺ 2025-07-01 | 1 comentarios | Compartir por WhatsApp
  • Un filtro Bloom es una estructura de datos probabilística que permite verificar rápidamente si un elemento pertenece a un conjunto usando la memoria de forma eficiente
  • Solo indica si un elemento definitivamente no está en el conjunto o si podría estar, y existe una probabilidad de falsos positivos
  • Su estructura básica usa un vector de bits y varias funciones hash para establecer en 1 los bits correspondientes a cada elemento
  • La tasa de error y el rendimiento dependen del tamaño del filtro y de la cantidad de funciones hash, por lo que pueden ajustarse según el caso de uso
  • También se presentan funciones hash recomendadas, métodos de configuración óptima, eficiencia de espacio y casos de uso reales

¿Qué es un filtro Bloom?

  • Un filtro Bloom es una estructura de datos que permite determinar de forma rápida y eficiente en memoria si un elemento existe en un conjunto
  • Para lograr esta eficiencia, el filtro Bloom es una estructura de datos probabilística, por lo que el resultado de la consulta se divide entre "definitivamente no está" en el conjunto o "podría estar"
  • La estructura central de un filtro Bloom es un vector de bits
  • Al agregar un elemento, este se hashea varias veces y los bits en esos índices se establecen en 1
  • Si todos los bits correspondientes a los índices producidos por cada función hash están en 1, se considera que "podría existir"; de lo contrario, se trata como "definitivamente no está"

Ejemplo de cómo funciona

  • Varias funciones hash (por ejemplo, Fnv, Murmur) mapean un elemento a múltiples índices de bits
  • Al agregar un elemento, los bits de los índices calculados cambian a 1
  • Al comprobar si un elemento existe, si todos los índices calculados con las mismas funciones hash y del mismo modo están en 1, se considera que "podría existir"
  • Si aunque sea uno de esos bits está en 0, puede determinarse con certeza que "no está en el conjunto"
  • Debido a esto, existe la posibilidad de falsos positivos

Temas avanzados

Atención: el autor no tiene experiencia aplicando filtros Bloom en servicios reales a gran escala

Selección de funciones hash

  • Se recomiendan funciones hash independientes y con distribución uniforme
  • Las funciones hash criptográficas (sha1, etc.) no son adecuadas porque son lentas
  • Ejemplos de funciones hash rápidas y simples: Murmur, xxHash, Fnv, HashMix, etc.
  • En un caso real, cambiar de md5 a murmur produjo una mejora de velocidad superior al 800%

Cómo determinar el tamaño del filtro Bloom

  • Cuanto mayor sea el tamaño del filtro (m), menor será la tasa de falsos positivos
  • La tasa de falsos positivos suele aproximarse con (1-e^(-kn/m))^k
  • Hay que definir adecuadamente la cantidad esperada de elementos (n), el tamaño del filtro (m) y la cantidad de funciones hash (k)

¿Cuántas funciones hash usar?

  • Cuantas más funciones hash haya, más lenta será la operación y más rápido se llenará el filtro
  • Si hay muy pocas, aumenta la tasa de falsos positivos
  • El valor ideal de k se calcula como (m/n)ln(2)
  • Al diseñarlo, se sigue normalmente este proceso:
    • Estimar la cantidad esperada de elementos n
    • Definir la cantidad de bits m
    • Calcular el k óptimo
    • Verificar si se obtiene la tasa de error deseada; si no, ajustar m

Rendimiento y eficiencia de espacio

  • En un filtro Bloom, agregar elementos/verificar existencia tiene complejidad temporal O(k)
  • La eficiencia de espacio depende del margen de error aceptable y del rango de elementos
  • Si no es posible predecir ni siquiera de manera aproximada el rango de elementos, puede convenir más una tabla hash o un filtro Bloom escalable

Casos de uso

  • Para ejemplos de uso más detallados, consulta Wikipedia
  • C. Titus Brown presenta un caso de aplicación de filtros Bloom en bioinformática

Material de referencia

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-07-01
Comentarios en Hacker News
  • Siento que este artículo es perfecto para gente como yo. Había escuchado el nombre, pero siempre dejaba para después investigarlo. Esta vez por fin lo revisé, y se sintió exactamente como la guía introductoria que quería
    • La primera vez que conocí los Bloom filters fue al implementar la función de búsqueda de iBooks. Ya pasaron más de 10 años de eso
    • Los Bloom filters son realmente divertidos. Cuando estás resolviendo un problema y llega el momento de necesitar uno, emociona bastante, aunque da pena que según el dominio no pase tan seguido
  • Una sugerencia para la persona autora. La parte interactiva está muy bien. Para ayudar a entender mejor las propiedades del Bloom filter, estaría bueno mostrar un ejemplo donde dos cadenas produzcan una colisión de hash, hacer que se ingrese una y luego la otra en una segunda caja de entrada. Así se entiende fácilmente por qué aparece esa lógica tan característica de "no es seguro que esté en el conjunto, pero quizá sí (maybe)"
    • Por ejemplo, "bloom" y "demonstrators " (incluyendo el espacio final) colisionan en fnv: 7, murmur: 12
  • En 2009, cuando estaba en la universidad, implementé un Bloom filter con CUDA. Mi asesor había trabajado antes en Nvidia. Pero en mi carrera terminé yéndome por un camino totalmente ajeno a la programación en GPU. A veces pienso que, si hubiera elegido distinto, quizá habría ganado 100 millones de dólares
    • Como es una idea de ciencias de la computación de 1970, creo que igual no habría sido posible. Da la impresión de que las ideas relacionadas con GPGPU ya estaban bastante exploradas. Yo también implementé Hashcash en GPU hace 10 años, y visto hoy su valor es casi cero
    • Yo porté un algoritmo de machine learning a CUDA como proyecto final de carrera y luego me cambié a programación embebida, pensando que no era gran cosa
    • A mí me pasó algo parecido. En 2009, con una GeForce 8 y CUDA v1(!), creo que hice uno de los primeros toolkits de bioinformática optimizados para GPU. Lo hice por curiosidad y después me fui por un rumbo completamente distinto, perdiendo la oportunidad de ganar mucho dinero
    • El comentario medio en broma de que si hubieran comprado Bitcoin habrían ganado todavía más dinero
  • Tengo un truco que me gusta. Para conjuntos pequeños donde puede haber pocos elementos pero se hacen verificaciones de pertenencia con frecuencia, meter un Bloom filter de 64 bits junto con una función hash muy simple. Suena tonto, pero el costo es tan bajo que se puede usar casi como una apuesta. Si no funciona, apenas agrega como 10 ns a la verificación o al insert; pero cuando sí encaja, reduce muchísimo la carga de trabajo
    • Chromium también usa este tipo de trucos por todos lados. El artículo solo menciona Safe Browsing, pero en la capa de Blink usan activamente rapidhash y estos micro-filtros. Por ejemplo, en querySelector(), en prefiltros de diccionarios de búsqueda por hash en buckets de CSS, y en rechazos rápidos al buscar atributos Aria para accesibilidad. Los filtros pequeños de 32 y 64 bits sí funcionan bien en la práctica. También se usan Bloom filters más grandes cuando corresponde; yo mismo agregué funciones de ese tipo
  • Hace poco usé un Bloom filter para una función antispam de mensajes de log. Se hace hash del mensaje y se mete en el filtro; si ya está en el filtro, no se imprime. Periódicamente se limpian todos los bits del filtro. Ni siquiera hace falta limpiar todos los bits de forma atómica: aunque algunos bits se borren mientras entran mensajes, lo único que pasa es que el log vuelve a aparecer. Antes llevaba contadores por mensaje por separado, pero este enfoque fue mucho más eficiente. Fue uno de esos casos en los que aplicar un Bloom filter directamente a un problema real me dejó muy satisfecho
  • Como ejemplo de visualización de Bloom filters, esta página tiene muy buen material al final
  • Recomiendo otro artículo introductorio sobre Bloom filters escrito por Eli Bendersky. Si quieren profundizar más, vean aquí
  • Creo que casi el 95% de los conceptos necesarios para entender un Bloom filter, un set y una tabla hash se superponen. Un set es una tabla hash donde solo importan las keys, y un Bloom filter es un set que aprovecha deliberadamente las propiedades de colisión del hashing. Usa funciones hash diseñadas para que las colisiones ocurran con facilidad. Si cierta key se insertó alguna vez, siempre va a coincidir. Pero puede haber otra key con el mismo valor hash. Así que no es un bug, sino una característica intencional
    • Yo también suelo pensar en el Bloom filter como una tabla hash a la que le quitaron los datos y solo se siguen los buckets. Me alegra ver que no soy el único con esa forma de pensarlo
    • Estaría bueno complementar con la parte de que los Bloom filters usan varias funciones hash para reducir colisiones. Por ejemplo, solo se considera que está en el set si las 3 funciones hash coinciden. Gracias a esa estructura, se reduce la probabilidad de falsos positivos mientras que nunca aparecen falsos negativos
    • Si ya entendiste el Bloom filter, probablemente también puedas entender pronto las proyecciones aleatorias o algunas implementaciones de Locality Sensitive Hashes
  • Me obsesioné con los Bloom filters mientras depuraba un pico de lecturas en Cassandra. Me parecía extraño que hubiera demasiadas consultas a sstable para keys que en realidad no existían. Tardé en entender qué significaban los Bloom filters adjuntos a cada sstable. La tasa predeterminada de falsos positivos era 0.1, demasiado alta para nuestro caso. Casi todo eran cache misses, y por culpa de esos falsos positivos había demasiadas consultas inútiles. Al bajarla a 0.01, el uso de memoria subió un poco, pero las lecturas innecesarias cayeron bastante y la latencia de lectura p99 bajó entre 16% y 18%
  • Me encantan los Bloom filters. Cuando hablo de temas técnicos, siempre trato de explicar tres conceptos clave: Bloom filters, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing) y el Cumulative flow diagram. Creo que esos tres conceptos son esenciales para operar sistemas distribuidos complejos
    • También pienso que las estructuras de tablas hash distribuidas son un tema igual de importante. Por ejemplo, circle, chord, CAN, kademlia y otras arquitecturas diversas