Si habéis utilizado Cassandra, sabréis que se caracteriza por ser tremendamente rápida en las escrituras y lecturas, y esto se debe en parte a una estructura de datos denominada Bloom Filter.
Bloom Filter es una manera extremadamente eficiente de preguntar si un dato existe en un conjunto o no (lo cual utiliza Cassandra para evitar accesos a disco en vano, que es la parte más lenta del tinglado). ¿La pega? Es un algoritmo probabilista y puede haber falsos positivos (aunque nunca falsos negativos).
Funciona con dos elementos:
- Un array de m bits, inicializado a a cero.
- Un conjunto de k funciones hash que, dado un dato, generarán números entre 0 y m-1.
Cuando insertemos un dato lo pasaremos por las funciones hash, las cuales nos devolverán posiciones del array donde cambiaremos sus valores a 1. Así, cuando lleguen nuevas cadenas, para saber que seguro el elemento no existe en el conjunto, solamente debemos comprobar que alguna de las posiciones en el array generada por alguna de las funciones hash nos devuelve 0.
Para intentar enteder esto mejor vamos a hacerlo con un pequeño juego.
Imaginemos una partida de «¿Quién es quién?», pero con multiples sospechosos. El jugador A añade sospechosos, y el jugador B pregunta al jugador A en base a los atributos de los sospechosos. En este caso los sospechosos serán los datos, sus atributos serán las funciones hash, y la lista total de atributos que guarde el jugador A será el array de bits. Éstos serán nuestros sospechosos.
Pongamos que el jugador A añade como sospechoso a Bill Gates. Eso significa que ahora el jugador A tiene como características «Rico», «Filántropo» y «Gafas». Por lo tanto, cuando el Jugador B pregunte por Steve Jobs, pese a que las propiedades de «Gafas» y «Rico» si que están, la de «Americano» no, así que puede estar seguro de que Steve Jobs no es uno de los sospechosos.
Pero, ¿qué pasa si ahora añadimos a Mark Zuckerberg? Al hacerlo, añadimos dos propiedades nuevas, por lo tanto ahora nuestra lista de características será la siguiente:
«Rico», «Filántropo», «Gafas», «Americano» y «Joven».
Así que, ahora, ¿qué pasa si preguntamos por Steve Jobs otra vez? Como todos sus atributos están en la lista, podríamos pensar que es uno de los sospechosos, pero no es el caso. Es decir, podemos estar seguros de cuándo alguien no es sospechoso, pero nunca de si lo es. Si insertamos a Steve Jobs nuestra lista no se alterará. ¿Qué pasa entonces si preguntamos por Stephen Hawking? Incluso con tres sospechosos ya metidos, como Stephen Hawking tiene dos atributos que aún no han sido insertados, podemos afirmar categóricamente que no está en la lista de sospechosos.
Y así funciona (muy por encima). Si queréis información en mayor profunidad, sobre cómo por ejemplo hacer para reducir el porcentaje de falsos positivos, o cómo lidiar con con borrados aquí tenéis una página interesante.
Why Bloom filters work the way they do
Y si os apetece jugar un poco con él, en esta web podréis encontrar diversas implementaciones en python, que os pueden ser útiles cuando queráis manejar grandes datos, como por ejemplo… datos del Titanic
