Filtros Bloom en Apache Cassandra

Los filtros Bloom se utilizan para mejorar el rendimiento de las lecturas. Su nombre es por su inventor, Burton Bloom. Los filtros Bloom son algoritmos muy rápidos y no deterministas para comprobar si un elemento es miembro de un conjunto. No son deterministas porque es posible obtener una lectura de falsos positivos de un filtro Bloom, pero no un falso negativo.

Los filtros Bloom funcionan al mapear los valores de un conjunto de datos en una matriz de bits y condensar un conjunto de datos más grande en una cadena de resumen mediante una función hash. El compendio, por definición, utiliza una cantidad de memoria mucho menor que la de los datos originales. Los filtros se almacenan en la memoria y se utilizan para mejorar el rendimiento al reducir la necesidad de acceso al disco en las búsquedas de claves. El acceso al disco suele ser mucho más lento que el acceso a la memoria. Entonces, en cierto modo, un filtro Bloom es un tipo especial de caché. Cuando se realiza una consulta, el filtro Bloom comprueba primero antes de acceder al disco.

Debido a que los falsos negativos no son posibles, si el filtro indica que el elemento no existe en el conjunto, ciertamente no lo hace; pero si el filtro piensa que el elemento está en el conjunto, se accede al disco para asegurarse.

Los filtros Bloom son implementados por la clase org.apache.cassandra.utils.BloomFilter. Cassandra proporciona la capacidad de aumentar la precisión del filtro Bloom (reduciendo el número de falsos positivos) al aumentar el tamaño del filtro, a costa de más memoria. Esta posibilidad positiva falsa es ajustable por tabla.

Los filtros Bloom se utilizan en otras bases de datos distribuidas y tecnologías de almacenamiento en caché, como Apache Hadoop, Google Bigtable y Squid Proxy Cache.