Filtros de Bloom: pertenencia probabilística a un conjunto sin falsos negativos

Qué es

Un filtro de Bloom es un array de m bits junto con k funciones hash. Al insertar un elemento se activan los k bits que seleccionan sus hashes; al consultar, se comprueban esos mismos bits. Si alguno está a 0, el elemento nunca se insertó; si todos están a 1, o bien se insertó, o bien otros elementos activaron esos bits, lo que constituye un falso positivo. La documentación de PostgreSQL sobre su índice bloom describe la estructura como eficiente en espacio y propensa a informar falsos positivos, por lo que cada coincidencia del índice debe volver a comprobarse contra la fila real. La documentación de Redis ofrece un filtro que se crea indicando la tasa de falsos positivos deseada y la capacidad esperada. El filtro básico no permite borrar: poner a 0 un bit podría eliminar la huella de otro elemento. Para esa necesidad existen los filtros de Bloom con contadores y los filtros cuckoo.

Por qué importa

El filtro cabe en memoria cuando el conjunto completo no lo hace, y responde «no» a bajo coste, lo que ahorra una lectura de disco, una ida y vuelta por la red o una consulta a la base de datos para claves que con certeza no existen. Los motores de almacenamiento usan uno por archivo de datos para saltarse archivos, los rastreadores web lo usan para saber si ya han visto una URL y las cachés lo emplean para evitar consultas al backend por claves desconocidas.

Cómo aplicarlo

• Dimensiona el filtro a partir del número esperado de elementos y de la tasa objetivo de falsos positivos; esa tasa aumenta a medida que el filtro se llena por encima de su capacidad de diseño, así que hay que planificar para el máximo o usar una variante escalable.
• Trata cada positivo como «consulta el almacén real»; omite la verificación solo cuando un falso positivo sea inocuo, como un fallo de cache adicional.
• Guarda el filtro junto con los identificadores de sus funciones hash, la semilla y el tamaño; cualquier cambio obliga a reconstruirlo a partir del conjunto completo.
• Despliégalo donde dominen las consultas negativas (nombres de usuario desconocidos, claves eliminadas, objetos fríos) y mide qué proporción de consultas filtra antes de conservarlo.
• Reconstrúyelo de forma periódica cuando el conjunto subyacente se reduzca; el filtro solo crece.

Trampas

Obtener los k hashes a partir de funciones correlacionadas aumenta los falsos positivos. Un filtro compartido entre procesos o lenguajes requiere un hash idéntico bit a bit. No se puede listar, contar ni eliminar nada. Un filtro cuya semilla o tamaño difiere de los usados al construirlo devuelve respuestas erróneas en silencio, en lugar de errores. Dimensionarlo para el tamaño medio del conjunto y no para el máximo anula su propósito.