Los bloom filters son una función de análisis de información. Estos dejan determinar si un dato o bien conjunto de estos se hallan guardados en una base de datos o bien conjunto distribuido de datos. Su primordial peculiaridades es su extrema eficacia en esta labor. Es por esta peculiaridades, que son muy utilizados en sistemas donde se necesite contrastar la existencia de un dato especifico en 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 bien instrumentos que nos facilitan examinar grandes cantidades de información probabilística. Esto con el propósito de saber si un factor o bien dato es parte integrante de un conjunto. Esta es una función que resulta exageradamente útil en instantes en los que debemos manejar grandes volúmenes de datos. Singularmente cuando dicha información no puede ser procesada de forma manual con velocidad.

Es por este motivo que merced a las bloom filters, criptomonedas como Bitcoin tienen la función de monederos SPV. Mas asimismo vemos esta función en criptomonedas como Ethereum donde dejan buscar información en su blockchain de forma eficaz.

Y esto es merced a que los Bloom filters nos dejan tener soo 2 resultados: los falsos positivos o bien los negativos. Esto es, a través de la implementación de los bloom filters se puede saber de forma veloz y eficaz si en la memoria pueden existir algunos elementos, o bien si claramente no existen. Los resultados de falsos positivos lanzan la posibilidad de que un factor o bien dato pueda ser parte de un conjunto. Al tiempo que los resultados negativos concluyen de forma terminante que el factor o bien dato no está incluido en el conjunto evaluado. La herramienta al unísono nos deja descartar por completo los falsos negativos, lo que facilita en buena 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 planeta de la blockchain? Puesto que bien, esto lo vamos a ver ahora.

Howard Bloom autor de los filtros bloom

Origen de los bloom filters

Los filtros de Bloom fueron diseñados en la década de los setenta 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 eficaz que deja revisar si un factor o bien dato es parte integrante de un conjunto o bien no. El propósito tras su creación era el de crear una herramienta de clasificación de datos por medio de la aplicación de funciones hash que devuelven un resultado o bien una identificación. Al unísono que deje contestar con certidumbre si el factor que se está verificando no es parte del conjunto, o bien reflejando que seguramente sí esté dentro de él.

Así el diseño de estos filtros de Bloom dejan manejar grandes bases de datos o bien información a alta velocidad. Y al tiempo se hace un empleo eficaz del espacio de almacenaje. Esto merced a que los bloom filters no requieren contener o bien guardar los elementos o bien datos en sí, sino más bien sencillamente revisar si están o bien no en el conjunto. Una operación de solo lectura de datos que habilita un alto desempeño y grandes capacidades de procesamiento de información.

¿De qué manera se configuran los bloom filters?

Los bloom filters cuentan con lo que es conocido como una estructura de datos de matriz de entradas. Esta matriz tiene una longitud o bien capacidad de almacenaje tan grande como sea preciso. Esto desea decir que al instante de la construcción de un bloom filter se puede establecer qué tan grande va a ser la longitud del filtro, conforme se requiera. Definiendo cuántas entradas van a ser añadidos a la estructura de datos base y cuántas funciones hash van a ser usadas en el filtro, asociándose a cada una de estas entradas.

Así mismo, al instante de su diseño se debe tener en consideración que el rango de las funciones hash debe comenzar en 0 y acabar en el número de la cantidad de entradas existentes menos 1. Esto es, que si se diseña un bloom filter para diez entradas, este iniciara con el número 0 y acabará en el número nueve. Si se diseña uno para veinte entradas, el bloom filter comenzará en el número 0 y acabará en el número diecinueve. Una práctica de diseño computacional que busca optimar al límite los recursos de procesamiento del filtro.

Igualmente cuando el conjunto de entradas existentes se halle con sus valores en 0, desea decir que los datos no están en el bloom filter. Con lo que este se halla vacío. Con lo que en el instante en el que se empiece a incorporar datos o bien elementos al filtro, la información va a ser pasada por las respectivas funciones hash que situará a dicha información en el sitio pertinente en el bloom filter. Con lo que dichas localizaciones van a pasar a reflejar el valor 1, señalando que poseen elementos ya analizados.

A partir de estos valores se edifica el funcionamiento de los bloom filters que vamos a explicar a detalle ahora.

Funcionamiento de los bloom filters

Entonces, en el momento en que se ha configurado el bloom filter podemos comenzar a contrastar si un factor es parte del conjunto o bien no. Para conseguir esto, el proceso a proseguir empieza con hacer pasar la entrada de datos que se quiere al algoritmo del bloom filter. Esto es, tomamos los datos del sistema y los procesamos utilizando las funciones hash del sistema. Estas funciones hash van a devolver 2 situaciones como resultado.

Estos hash y las situaciones que devuelven como resultado son guardadas y relacionadas con los datos que le dan origen. De esta manera el filtro prosigue recogiendo información, aplicando sobre ellas funciones hash y guardando los resultados de su funcionamiento. No obstante, este proceso cuenta con un procedimiento auxiliar que maximiza su eficacia y mejora el tiempo de contestación de los sistemas que aplican esta clase de filtros a sus estructuras.

En primer sitio, si los datos que se han pasado al filtro pasan por las funciones hash y devuelven situaciones con valores diferentes de 0, entonces el factor está en el conjunto. Esto es lo que es conocido como positivo señalando la existencia de ese elemento en el conjunto. Asimismo puede darse el caso en el que los hash devuelvan resultados con valores diferentes.

Por el contrario, si una de las situaciones o bien las dos, muestran un valor 0, entonces el factor claramente no está en el conjunto. Otra situación previstas por el algoritmo y que recibe el nombre de negativo o bien falso positivo. Este resultado sí es terminante o bien concluyente puesto que los bloom filters jamás van a dar como resultado a falsos negativos. O sea, si el algoritmo de un bloom filter advierte un negativo o bien un falso positivo, claramente esa información no está en el conjunto de datos analizado.

Por otra parte, al instante de configurar un bloom filter es de suma importancia acotar la cantidad de bits y de funciones hash que se van a aplicar. Puesto que a mayor número de funciones hash, se reduce en buena medida el ratio de fallo, con lo que la probabilidad de tener resultados de falsos positivos va a ser menor. Del mismo modo, en el momento en que el conjunto de bits del bloom filter se llene por completo, los datos introducidos no van a poder ser borrados. Esto con la meta de no ocasionar la aparición de falsos negativos en el filtro.

Como marcha un Bloom Filter o bien Filtro Bloom

¿Qué relevancia tienen los falsos positivos y negativos en los bloom filters?

La relevancia de los estados falsos positivos y negativos de los bloom filter se encuentra en la eficacia. Como ya hemos citado, los bloom filter son programados para tener en consideración los dos estados. Y en el caso de que se presenten, podemos tomar las acciones pertinentes para dar una contestación acorde.

Por ejemplo, si trabajamos con un sistema de almacenaje de datos para producir una caché un bloom filter nos resulta de mucha ayuda. Esto merced a que toda vez que el sistema reciba un dato, lo que debemos hacer es contrastar si dicho dato no está en la data que hemos guardado en la caché. Conque si introducimos este dato y el bloom filter nos devuelve un negativo o bien 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 guardar este nuevo dato en la cache a fin de que entonces podamos acceder al mismo de forma veloz y eficaz.

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

Este género de funcionamiento no es extraño al software que utilizamos de forma diaria. Por servirnos de un ejemplo, los navegadores web emplean memoria caché guardada en nuestros discos duros para darnos acceso a determinados recursos de forma veloz, en comparación a preguntar dichos datos vía on line. Las bases de datos de servidores y otros sistemas que manejan enormes cantidades de datos asimismo utilizan bloom filters o bien algoritmos similares para progresar la eficacia de sus contestaciones y tratamiento de datos.

Funciones hash en los bloom filters

Al instante de configurar un bloom filter se deben emplear funciones hash independientes y distribuidas de forma uniforme. Estas funciones hash dejan asignar un identificador a cualquier clase de datos, que puede ser usado para indexar o bien equiparar a dichos datos en un conjunto.

Cuando charlamos de funciones hash charlamos de las conocidas SHA-doscientos cincuenta y seis, MD5 o bien otras funciones como CRC32. No obstante, en los bloom filters hay que ser cautelosos. Emplear muchas funciones hash añade seguridad mas asimismo hace más complejo y lento al mismo, con lo que debe seleccionarse las funciones de forma de que se exploten al límite sus capacidades.

Por su parte, la característica unidireccional de las funciones hash dejan que se pueda determinar o bien crear un identificador desde un elemento o bien dato, mas que no se pueda efectuar el proceso contrario. Con lo que si un usuario descubre un identificador, no va a poder conocer cuales son los datos o bien elementos relacionados a él.

Ventajas y desventajas de usar bloom filter

Ventajas

  • Los bloom filters, al noguardar un conjunto de datos como tal, son más eficaces en lo que se refiere al empleo del espacio de almacenamiento. En tanto que solo guardan si una información o bien elemento existe o bien no en el bloom filter.
  • Así mismo, esta característica deja que la verificación de los datos o bien elementos pueda efectuarse de forma considerablemente más veloz y eficiente. Si bien asimismo hay que tomar en consideración que a mayor número de funciones hash, mayor va a ser el tiempo requerido por el bloom filter para contrastar la existencia de los elementos o bien datos.
  • Como los bloom filters emplean el término de hash unidireccional. Si un usuario consigue acceso a ellos no va a poder conocer de manera directa ninguna de la información que está contenida en estos filtros.

Desventajas

  • Estas herramientas no devuelven los datos verificados. En su sitio solo dejan revisar si probablemente existen o bien no.
  • Cuando se tienen resultados positivos solo se puede aceptar que seguramente sean adecuados. No se puede tener la certidumbre o bien la plena seguridad de que los datos positivos son parte del conjunto. Al revés de lo que sucede en el caso de conseguir resultados negativos. Donde sí se puede tener una contestación o bien un resultado definitivo final.
  • Cuando se diseña el filtro de bloom se le deba asignar un tamaño, sin importar un mínimo si se trata de varios bits o bien de millones de estos. Una vez que le resulte designado un tamaño, este no se reducirá ni medrará más de lo anteriormente establecido. Con lo que a fin de que el bloom filter sea eficaz hay que acotar o bien tener claro con cierta antelación cuántos datos se agregarán. Con lo que si no se conoce esta información probablemente se diseñe un bloom filter con poquísimos items que no resulte tan eficiente para el manejo de la información que se quiere. O bien puede darse el caso en el que se diseñe un bloom filter amplísimo que demande un espacio de almacenaje muy grande para la poca cantidad de información a manejar. Lo que resultaría en un desperdicio de espacio.

¿Cuánto sabes, criptonauta?

¿Los Bloom Filters mejoran la capacidad de contestación de la blockchain y su red?

Casos de empleo de los bloom filters

Criptomonedas: Bitcoin y Ethereum

El sistema Bitcoin emplea bloom filters para la acelerar la sincronización de las wallets o bien monederos SPV; los que dejan que estos puedan detallar solo las transacciones para las que desean percibir las actualizaciones del sistema. Formando un conjunto de transacciones que pueden trasmitir a los nodos completos de la red. Allá se puede contrastar por medio de estos filtros. Recibiendo entonces la confirmación de si este conjunto de transacciones se ha añadido o bien no a la cadena. Sin precisar manejar una copia completa de la blockchain. En Bitcoin esta funcionalidad es cambiada por los Compact Block mentados en el BIP-158.

Por su parte, la red Ethereum emplea los filtros de bloom como un mecanismo a través del que puede hallar logs en su blockchain. De este modo, a través de la implementación de estos filtros, se puede buscar con sencillez los acontecimientos ocurridos en el sistema de Ethereum. Sin sobrecargarlo por un manejo de información excesiva. Haciendo que las aplicaciones puedan administrar esta información de forma considerablemente más eficaz. Mientras que no se precisa de un sinnúmero de espacio de almacenaje. Puesto que con los filtros de bloom no es preciso guardar datos que pudiesen estar duplicados en el sistema.

En Ethereum, en el momento en que un bloque es generado y verificado, la dirección del contrato y los campos indizados de los registros se agregan a un filtro de bloom. Este filtro se sitúa en el encabezado del bloque. Con lo que si una aplicación quiere localizar todas y cada una de las entradas del registro, el nodo solo debe escanear el encabezado. De este modo puede reconocer si los datos requeridos están allá o bien no. Con lo que estos elementos no son añadidos al bloque como tal, con el propósito de ahorrar espacio de almacenaje.

Redes y canales de información

Otra implementación esencial de los filtros de bloom deja a las redes o bien canales de información poder hacer recomendaciones de artículos a los usuarios. Dejando que estos no se repitan. Esto es, se puede conocer qué artículos ha leído un usuario para aconsejarle los que no haya visto aún.

Así mismos, grandes centros de datos y de distribución de contenidos (CDN) emplean bloom filters para aumentar al máximo la eficacia de almacenaje de datos y de empleo de red, eludiendo que elementos repetidos o bien poco utilizados formen una parte de sus sistemas sobrecargándolos. Esto incluye a empresa como Akamai, Namecheap CDN, Fastly o bien Cloudflare.