Podcast Z #7: Proyecto X - Filtros BLOOM

Autor: Jesús Cea & Pablo Lobariñas - Contacto: python2012@podcast.jcea.es
Fecha de grabación: 2011/12/06 - Duración: 48:46
Fecha de publicación: 2012/01/27
Palabras clave: Python, Bases de Datos, Algoritmos
Descarga el audio: MP3 (16201404 bytes) - OGG (9040121 bytes)

Notas:

• 01:00: Filtros Bloom. Tecnología interesante y desconocida.

• 01:30: El número de huellas ha ido creciendo, y la estructura de datos que usamos, "set()", tiene un coste en memoria proporcional al número de elementos. Estábamos usando 1.5GB en 32 bits, y 3GB en 64 bits.

• 04:30: Las huellas eran 40 millones de números (y creciendo) de 32 bits. Son 150MB en disco, pero 1.5/3 gigabytes al cargarlos en un "set()".

• 05:40: Idea simple para reducir los 1.5/3GB a 512MB: como trabajamos con números de 32bits, podemos tener una matriz de 2³² bits y ponerlos a cero o a uno según ese valor esté en la lista o no. Esto son 512MB.

• 07:15: Como tenemos una matriz de 2³² bits, pero solo un 1% estará a UNO, los 512MB resultantes se pueden comprimir muy bien, típicamente al 11% (unos 55MB), aptos para ser transmitidos por Internet.

• 08:40: La matriz así generada no tiene falsos positivos ni falsos negativos, pero como los datos de entrada son una lista de 32 bits, que es una "reducción" de la fuente real original, esa lista ya induce falsos positivos. Es decir, diferentes valores en el origen que generan el mismo número de 32 bits.

• 10:10: Para el cliente, reducir el consumo de memoria a 512MB sigue siendo insuficiente. Su objetivo es llegar a ocupar solo 64-128MB. Lo consigo reducir a 32MB, usando un filtro Bloom.

• 11:00: Si en vez de introducir falsos positivos en la reducción de 128bits a 32 bits, podemos utilizar los 128bits originales y usar una estructura de datos con falsos positivos, una estructura "probabilística".

• 13:50: Explicación de cómo funciona un filtro Bloom y su tasa de falsos positivos.

• 14:55: "Te lo voy a explicar a ti, a ver si explicándotelo me aclaro" :-).

• 17:10: Explicando el concepto de "colisiones" y por qué son inevitables. Falsos positivos.

• 23:00: Controlamos la tasa de falsos positivos añadiendo más o menos bits y controlando el número de bits puestos a UNO por cada valor original (y el número de bits que deben ser UNO para tener un "hit").

• 25:30: Ahora en cada búsqueda tenemos un 2% de falsos positivos en vez del 1% inicial, pero hacemos dos búsquedas, así que la tasa de falsos positivos es del 2% del 2%, o 4 de cada 10.000 (aproximadamente).

• 30:30: Filtro Bloom. Hay un número óptimo de búsquedas. Las ecuaciones están en la Wikipedia.

• 35:45: Un filtro Bloom no se puede comprimir, su entropía es máxima.

• 37:00: ¿Cómo "desdoblamos" los valores?. Es decir, que a partir de un valor de entrada, podemos poner varios bits a UNO, de forma no correlada.

• 40:30: En la bibliografía de la Wikipedia se estudian algoritmos y el impacto de rendimiento que supone que los bits puestos a UNO no sean completamente no correlados. Por ejemplo:

  Kirsch, Adam; Mitzenmacher, Michael (2006), "Less Hashing, Same Performance: Building a Better Bloom Filter", in Azar, Yossi; Erlebach, Thomas, Algorithms - ESA 2006, 14th Annual European Symposium, 4168, Springer-Verlag, Lecture Notes in Computer Science 4168, pp. 456-467, doi:10.1007/11841036

• 43:20: Estamos abusando de las matemáticas del filtro Bloom, así que antes de distribuir el filtro hacemos una simulación con él en el servidor.

• 45:30: Un filtro Bloom tiene falsos positivos, pero NO tiene falsos negativos.

• Volver a Podcast Z