¿Qué es un Bloom Filter?

Los bloom filters son una función de análisis de información. Estos permiten determinar si un dato o conjunto de estos se encuentran almacenados dentro de una base de datos o conjunto distribuido de datos. Su principal características es su extrema eficiencia en esta tarea. Es por esta características, que son muy usados en sistemas donde se necesite verificar la existencia de un dato especifico dentro de un enorme conjunto de estos.

Una de las herramientas más útiles para el análisis de la información probabilística y unidireccional son los bloom filters. Estos bloom filters son herramientas o instrumentos que nos facilitan analizar grandes cantidades de información probabilística. Esto con el fin de saber si un elemento o dato forma parte de un conjunto. Esta es una función que resulta extremadamente útil en momentos en los que debemos manejar grandes volúmenes de datos. Especialmente cuando dicha información no puede ser procesada de forma manual con rapidez.

Es por ello que gracias a las bloom filters, criptomonedas como Bitcoin tienen la función de monederos SPV. Pero también vemos esta función en criptomonedas como Ethereum donde permiten buscar información en su blockchain de manera eficiente.

Y esto es gracias a que los Bloom filters nos permiten tener soo dos resultados: los falsos positivos o los negativos. Es decir, mediante la implementación de los bloom filters se puede saber de forma rápida y eficiente si en la memoria pueden existir ciertos elementos, o si definitivamente no existen. Los resultados de falsos positivos arrojan la posibilidad de que un elemento o dato pueda formar parte de un conjunto. Mientras que los resultados negativos concluyen de forma definitiva que el elemento o dato no está incluido dentro del conjunto evaluado. La herramienta a la vez nos permite descartar por completo los falsos negativos, lo que facilita en gran medida el análisis de datos.

Pero ¿Qué llevó a la creación de los bloom filters? Cuál es la relación de estos con el mundo de la blockchain? Pues bien, esto lo veremos a continuación.

Así el diseño de estos filtros de Bloom permiten manejar grandes bases de datos o información a gran velocidad. Y al mismo tiempo se hace un uso eficiente del espacio de almacenamiento. Esto gracias a que los bloom filters no requieren contener o almacenar los elementos o datos en sí, sino simplemente comprobar si están o no dentro del conjunto. Una operación de solo lectura de datos que habilita un alto rendimiento y grandes capacidades de procesamiento de información.

¿Cómo se configuran los bloom filters?

Los bloom filters cuentan con lo que se conoce como una estructura de datos de matriz de entradas. Esta matriz posee una longitud o capacidad de almacenamiento tan grande como sea necesario. Esto quiere decir que al momento de la construcción de un bloom filter se puede establecer qué tan grande será la longitud del filtro, según se requiera. Definiendo cuántas entradas serán añadidos a la estructura de datos base y cuántas funciones hash serán utilizadas dentro del filtro, asociándose a cada una de estas entradas.

Así mismo, al momento de su diseño se debe tener en cuenta que el rango de las funciones hash debe iniciar en 0 y culminar en el número de la cantidad de entradas existentes menos 1. Es decir, que si se diseña un bloom filter para 10 entradas, éste iniciara con el número 0 y culminará en el número 9. Si se diseña uno para 20 entradas, el bloom filter iniciará en el número 0 y culminará en el número 19. Una práctica de diseño computacional que busca optimizar al máximo los recursos de procesamiento del filtro.

Igualmente cuando el conjunto de entradas existentes se encuentre con todos sus valores en 0, quiere decir que los datos no están en el bloom filter. Por lo que éste se encuentra vacío. Así que en el momento en el que se comience a añadir datos o elementos al filtro, la información será pasada por las respectivas funciones hash que ubicará a dicha información en el lugar correspondiente dentro del bloom filter. Por lo que dichas ubicaciones pasarán a reflejar el valor 1, indicando que contienen elementos ya analizados.

A partir de estos valores se construye el funcionamiento de los bloom filters que explicaremos a detalle a continuación.

Funcionamiento de los bloom filters

Entonces, una vez que se ha configurado el bloom filter podemos empezar a verificar si un elemento forma parte del conjunto o no. Para lograr esto, el proceso a seguir comienza con hacer pasar la entrada de datos que se quiere al algoritmo del bloom filter. Es decir, tomamos los datos del sistema y los procesamos usando las funciones hash del sistema. Estas funciones hash devolverán dos posiciones como resultado.

Estos hash y las posiciones que devuelven como resultado son almacenadas y relacionadas con los datos que le dan origen. Así el filtro sigue recolectando información, aplicando sobre ellas funciones hash y almacenando los resultados de su funcionamiento. Sin embargo, este proceso cuenta con un procedimiento adicional que maximiza su eficiencia y mejora el tiempo de respuesta de los sistemas que aplican este tipo de filtros a sus estructuras.

En primer lugar, si los datos que se han pasado al filtro pasan por las funciones hash y devuelven posiciones con valores diferentes de 0, entonces el elemento está dentro del conjunto. Esto es lo que se conoce como positivo indicando la existencia de ese elemento en el conjunto. También puede darse el caso en el que los hash devuelvan resultados con valores diferentes.

Por el contrario, si una de las posiciones o ambas, muestran un valor 0, entonces el elemento definitivamente no está dentro del conjunto. Otra situación previstas por el algoritmo y que recibe el nombre de negativo o falso positivo. Este resultado sí es definitivo o concluyente ya que los bloom filters nunca darán como resultado a falsos negativos. Es decir, si el algoritmo de un bloom filter detecta un negativo o un falso positivo, definitivamente esa información no está en el conjunto de datos analizado.

Por otra parte, al momento de configurar un bloom filter es de gran importancia definir la cantidad de bits y de funciones hash que se aplicarán. Pues a mayor número de funciones hash, se reduce en gran medida el ratio de error, por lo que la probabilidad de tener resultados de falsos positivos será menor. Así mismo, una vez que el conjunto de bits del bloom filter se llene por completo, los datos introducidos no podrán ser borrados. Esto con la finalidad de no causar la aparición de falsos negativos en el filtro.

¿Qué importancia tienen los falsos positivos y negativos dentro de los bloom filters?

La importancia de los estados falsos positivos y negativos de los bloom filter radica en la eficiencia. Como ya hemos mencionado, los bloom filter son programados para tener en cuenta ambos estados. Y en caso de que se presenten, podemos tomar las acciones pertinentes para dar una respuesta acorde.

Por ejemplo, si trabajamos con un sistema de almacenamiento de datos para generar una caché un bloom filter nos es de gran ayuda. Esto gracias a que cada vez que el sistema reciba un dato, lo que debemos hacer es verificar si dicho dato no está en la data que hemos almacenado en la caché. Así que si introducimos este dato y el bloom filter nos devuelve un negativo o un falso positivo, podemos estar seguros de que dicho dato no está en el conjunto de información que manejamos. Y en ese punto, podemos proceder a almacenar este nuevo dato en la cache para que luego podamos acceder al mismo de forma rápida y eficiente.

Si por el contrario, el bloom filter nos devuelve un positivo, podemos simplemente descartar almacenar la información y trabajar con la que tenemos en la caché, dando un mejor acceso a la información y salvando con ello recursos computacionales valiosos.

Este tipo de funcionamiento no es ajeno al software que usamos de forma diaria. Por ejemplo, los navegadores web usan memoria caché almacenada en nuestros discos duros para darnos acceso a ciertos recursos de forma rápida, en comparación a consultar dichos datos vía online. Las bases de datos de servidores y otros sistemas que manejan inmensas cantidades de datos también usan bloom filters o algoritmos parecidos para mejorar la eficiencia de sus respuestas y tratamiento de datos.

Funciones hash dentro de los bloom filters

Al momento de configurar un bloom filter se deben emplear funciones hash independientes y distribuidas de manera uniforme. Estas funciones hash permiten asignar un identificador a cualquier tipo de datos, que puede ser utilizado para indexar o comparar a dichos datos dentro de un conjunto.

Cuando hablamos de funciones hash hablamos de las conocidas SHA-256, MD5 u otras funciones como CRC32. Sin embargo, en los bloom filters hay que ser cuidadosos. Usar muchas funciones hash agrega seguridad pero también hace más complejo y lento al mismo, por lo que debe elegirse las funciones de forma de que se exploten al máximo sus capacidades.

Por su parte, la característica unidireccional de las funciones hash permiten que se pueda determinar o crear un identificador a partir de un elemento o dato, pero que no se pueda realizar el proceso contrario. Por lo que si un usuario descubre un identificador, no podrá conocer cuales son los datos o elementos relacionados a él.

Ventajas y desventajas de utilizar bloom filter

Ventajas

• Los bloom filters, al no almacenar un conjunto de datos como tal, son más eficientes en cuanto al uso del espacio de almacenamiento. Ya que sólo guardan si una información o elemento existe o no dentro del bloom filter.
• Así mismo, esta característica permite que la verificación de los datos o elementos pueda realizarse de forma mucho más rápida y eficiente. Aunque también hay que tener en cuenta que a mayor número de funciones hash, mayor será el tiempo requerido por el bloom filter para verificar la existencia de los elementos o datos.
• Como los bloom filters utilizan el concepto de hash unidireccional. Si un usuario obtiene acceso a ellos no podrá conocer de forma directa ninguna de la información que está contenida en estos filtros.

Desventajas

• Estas herramientas no devuelven los datos verificados. En su lugar sólo permiten comprobar si posiblemente existen o no.
• Cuando se tienen resultados positivos sólo se puede asumir que probablemente sean correctos. No se puede tener la certeza o la plena seguridad de que los datos positivos forman parte del conjunto. Al contrario de lo que ocurre en caso de obtener resultados negativos. Donde sí se puede tener una respuesta o un resultado decisivo final.
• Cuando se diseña el filtro de bloom se le deba asignar un tamaño, sin importar si se trata de unos cuantos bits o de millones de éstos. Una vez que le sea designado un tamaño, éste no se reducirá ni crecerá más de lo previamente establecido. Por lo que para que el bloom filter sea eficiente hay que definir o tener claro con antelación cuántos datos se añadirán. Por lo que si no se conoce esta información es probable que se diseñe un bloom filter con muy pocos items que no resulte tan eficaz para el manejo de la información que se quiere. O puede darse el caso en el que se diseñe un bloom filter muy amplio que demande un espacio de almacenamiento muy grande para la poca cantidad de información a manejar. Lo que resultaría en un desperdicio de espacio.

Casos de uso de los bloom filters

Criptomonedas: Bitcoin y Ethereum

El sistema Bitcoin emplea bloom filters para la acelerar la sincronización de las wallets o monederos SPV; los cuales permiten que éstos puedan especificar sólo las transacciones para las que desean recibir las actualizaciones del sistema. Formando un conjunto de transacciones que pueden transmitir a los nodos completos de la red. Allí se puede verificar a través de estos filtros. Recibiendo luego la confirmación de si este conjunto de transacciones se ha añadido o no a la cadena. Sin necesidad de manejar una copia completa de la blockchain. En Bitcoin esta funcionalidad está siendo cambiada por los Compact Block mencionados en el BIP-158.

Por su parte, la red Ethereum hace uso de los filtros de bloom como un mecanismo a través del cual puede encontrar logs dentro de su blockchain. Así, mediante la implementación de estos filtros, se puede buscar con facilidad los eventos ocurridos dentro del sistema de Ethereum. Sin sobrecargarlo por un manejo de información excesiva. Haciendo que las aplicaciones puedan gestionar esta información de forma mucho más eficiente. Al tiempo que no se requiere de una gran cantidad de espacio de almacenamiento. Ya que con los filtros de bloom no hay necesidad de almacenar datos que pudieran estar duplicados dentro del sistema.

En Ethereum, cuando un bloque es generado y verificado, la dirección del contrato y los campos indexados de los registros se añaden a un filtro de bloom. Este filtro se ubica en el encabezado del bloque. Por lo que si una aplicación desea encontrar todas las entradas del registro, el nodo sólo debe escanear el encabezado. Así puede reconocer si los datos requeridos están allí o no. Por lo que estos elementos no son añadidos al bloque como tal, con la finalidad de ahorrar espacio de almacenamiento.

Redes y canales de información

Otra implementación importante de los filtros de bloom permite a las redes o canales de información poder hacer recomendaciones de artículos a los usuarios. Permitiendo que estos no se repitan. Es decir, se puede conocer qué artículos ha leído un usuario para recomendarle los que no haya visto aún.

Así mismos, grandes centros de datos y de distribución de contenidos (CDN) usan bloom filters para maximizar la eficiencia de almacenamiento de datos y de uso de red, evitando que elementos repetidos o poco usados formen parte de sus sistemas sobrecargándolos. Esto incluye a empresa como Akamai, Namecheap CDN, Fastly o Cloudflare.