Filtro de Bloom: una estructura de datos para cuando la RAM es costosa

Al finalizar este tema

Podrás explicar el principio del filtro de Bloom y comprender por qué "no está" es una respuesta segura, pero "está" puede ser incorrecta en ocasiones.

Problema: 100 millones de usuarios y la necesidad de verificar la duplicidad de IDs

Al registrarse, se verifica si el ID ya está en uso. Si hay 100 usuarios, basta con una consulta SELECT a la base de datos. Pero, ¿qué pasa si hay 100 millones de usuarios?

Consultar la base de datos cada vez es lento. Por otro lado, cargar los 100 millones de IDs en la memoria no es viable debido a la falta de RAM. Incluso considerando un promedio de 10 bytes por ID, se requiere 1 GB.

El filtro de Bloom reduce estos 1 GB a 12 MB. Sin embargo, esto conlleva una condición.

Principio: función hash + arreglo de bits

El filtro de Bloom es un arreglo de bits que solo almacena ceros y unos. Inicialmente, todos son cero.

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Al registrar el ID "alice", se ejecutan tres funciones hash para obtener tres posiciones:

hash_A("alice") → 2
hash_B("alice") → 5
hash_C("alice") → 8

[0, 0, 1, 0, 0, 1, 0, 0, 1, 0]
         ↑        ↑        ↑

También se registra el ID "bob":

hash_A("bob") → 1
hash_B("bob") → 5  ← coincide con alice
hash_C("bob") → 7

[0, 1, 1, 0, 0, 1, 0, 1, 1, 0]

Ahora "charlie" intenta registrarse. Comprobación de duplicados:

hash_A("charlie") → 3 → 0 → "¡No encontrado!"

Si alguno de los resultados del hash es 0, nunca se ha registrado. No es necesario consultar la base de datos; se puede responder inmediatamente que está "disponible".

La trampa: "existe" a veces miente

El problema radica en el caso contrario. Al verificar "dave", las tres posiciones eran 1. Se concluyó que "¡ya existe!", pero en realidad podría ser que, al registrarse alice y bob, por casualidad se marcaran las mismas posiciones como 1.

Esto se conoce como falso positivo (False Positive).

• Si dice "no existe" → realmente no existe (100% seguro)
• Si dice "existe" → probablemente exista, pero a veces se equivoca (probabilístico)

Cuanto mayor sea el arreglo de bits y mayor el número de funciones hash, menor será la probabilidad de falsos positivos. En la práctica, se mantiene por debajo del 1%.

¿Dónde se utiliza?

¿Podría ser útil una estructura de datos que "a veces se equivoca"? Sorprendentemente, se utiliza muchísimo:

Filtrado de URLs maliciosas en Chrome — Almacena la lista de sitios maliciosos mediante un filtro Bloom. Si la URL que se va a visitar "no existe", se permite el acceso directamente; si "podría existir", entonces se verifica con el servidor.

Optimización de consultas en bases de datos — Antes de un SELECT, se verifica primero con un filtro Bloom si "¿es posible que este valor esté en esta tabla?". Si se confirma que no está, no es necesario realizar la lectura de disco.

Verificación de duplicados en el registro de usuarios — Si el filtro Bloom indica "no existe", se aprueba inmediatamente; si indica "podría existir", entonces se consulta la base de datos. Esto reduce drásticamente la carga de la base de datos.

El patrón central siempre es el mismo: confirmar rápidamente que "no existe" para omitir operaciones costosas.

Funcionalidades que no tiene el filtro Bloom

Un punto importante: el filtro Bloom no permite eliminar elementos. Si se cambia un bit a 0, se podrían corromper los datos porque otros elementos podrían estar usando esa misma posición.

Cuando se requiere la eliminación, se utiliza una variante llamada Counting Bloom Filter. En lugar de bits, almacena contadores para implementar la eliminación mediante "incrementar 1 / decrementar 1". A cambio, consume más memoria.

Además, no se pueden recuperar los datos insertados. El filtro Bloom solo responde a la pregunta "¿existe o no?". No puede responder a "¿qué hay dentro?", ya que la información original se pierde al pasar por las funciones hash.

En resumen, el filtro Bloom es una estructura que solo permite preguntar "¿existe esto?", pero no "¿qué hay?" ni "elimina esto". Conocer esta limitación lo convierte en una herramienta que ahorra memoria de forma drástica; ignorarla puede ser la causa de errores.

Puntos clave

El filtro Bloom es una estructura de datos probabilística que confirma con certeza cuando "no existe", pero a veces se equivoca cuando indica "existe". Su principio consiste en marcar un arreglo de bits mediante funciones hash, lo que ahorra memoria de forma significativa. El propósito siempre es el mismo: confirmar rápidamente la ausencia de resultados para evitar procesos costosos.