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 filtros de floración. Estos filtros de flores 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 los filtros bloom, las 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 filtros Bloom no permiten tener tantos resultados: los falsos positivos o los negativos. Es decir, mediante la implementación de los filtros bloom 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 filtros bloom? ¿Cuál es la relación de estos con el mundo de la blockchain? Pues bien, esto lo veremos a continuación.
Origen de los filtros bloom
Los filtros de Bloom fueron diseñados en la década de los 70 por el desarrollador Burton Howard Bloom. Bloom quien se graduó en Ciencias de la Computación en el MIT, diseñó estos filtros como una estructura de datos probabilística de espacio eficiente que permite comprobar si un elemento o dato forma parte de un conjunto o no. El objetivo tras su creación era el de crear una herramienta de clasificación de datos a través de la aplicación de funciones hash que devuelven un resultado o una identificación. A la vez que permita responder con certeza si el elemento que se está comprobando no forma parte del conjunto, o reflejando que probablemente sí esté dentro de él.
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 filtros bloom 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 filtros bloom?
Los filtros de floración 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 necesaria. Esto quiere decir que al momento de la construcción de un filtro bloom se puede establecer qué tan grande será la longitud del filtro, según se requiera. Definiendo podrán entradas se añadirán a la estructura de datos base y podrán funciones se utilizarán 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 filtro bloom para 10 entradas, iniciar éste 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 encuentra con todos sus valores en 0, quiere decir que los datos no están en el filtro bloom. 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 filtro bloom. Por lo que dichas pasarán a reflejar el valor 1, indicando que contienen elementos ya analizados.
A partir de estos valores se construye el funcionamiento de los filtros bloom que explicaremos a detalle a continuación.
Funcionamiento de los filtros bloom
Entonces, una vez que se ha configurado el filtro bloom 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 filtro bloom. 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 guardados y relacionados 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 cuenta del caso en el que los hash devuelvan resultados con diferentes valores.
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 prevista por el algoritmo y que recibe el nombre de negativo o falso positivo. Este resultado sí es definitivo o concluyente ya que los filtros bloom nunca darán como resultado falsos negativos. Es decir, si el algoritmo de un filtro de floración detecta un negativo o un falso positivo, definitivamente esa información no está en el conjunto de datos analizados.
Por otra parte, al momento de configurar un filtro de floración es de gran importancia definir la cantidad de bits y las funciones hash que se utilizarán. Pues a mayor número de funciones hash, se reduce en gran medida la proporción 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 filtro bloom 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 filtros bloom?
La importancia de los estados falsos positivos y negativos de los bloom filter radica en la eficiencia. Como ya hemos mencionado, los filtros de floración 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 filtro bloom nos es de gran ayuda. Esto gracias a que cada vez que el sistema recibe un dato, lo que debemos hacer es verificar si dicho dato no está en los datos 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 caché 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é guardada 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 filtros de floración o algoritmos parecidos para mejorar la eficiencia de sus respuestas y tratamiento de datos.
Funciones hash dentro de los filtros bloom
Al momento de configurar un filtro bloom 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 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 filtros bloom hay que ser cuidadosos. Usar muchas funciones hash agrega pero seguridad 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 permite 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 cuáles son los datos o elementos relacionados a él.
Ventajas y desventajas de utilizar el filtro bloom
ventajas
- Los filtros bloom, 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 existe una información o elemento o no dentro del filtro bloom.
- 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 filtro bloom para verificar la existencia de los elementos o datos.
- Como los filtros bloom 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 se permite comprobar si posiblemente existe 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 estos. 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 filtro de floración con muy pocos elementos que no resulte tan eficaz para el manejo de la información que se quiere. O puede darse cuenta del caso en el que se diseña un filtro de floración muy amplio que demanda 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 filtros bloom
Criptomonedas: Bitcoin y Ethereum
El sistema Bitcoin emplea filtros de floración para acelerar el efecto de las billeteras o monederos SPV; los cuales permiten que estos puedan especificar solo 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 agregado o no a la cadena. Sin necesidad de manejar una copia completa de la cadena de bloques. 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 floración como un mecanismo a través del cual puede encontrar registros dentro de su cadena de bloques. 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 excesivo. 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 floración no hay necesidad de almacenar datos que podrían 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 floración. 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 informacion
Otra implementación importante de los filtros de floración 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, los grandes centros de datos y de distribución de contenidos (CDN) usan filtros bloom 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 una empresa como Akamai, Namecheap CDN, Fastly o Cloudflare.
