algorithm - Uso del filtro Bloom
data-structures bloom-filter (3)
Estoy luchando para entender la utilidad del filtro de floración. Recibo su lógica subyacente, compactación de espacio, búsquedas rápidas, falsos positivos, etc. Simplemente no puedo poner ese concepto en una situación de la vida real como algo beneficioso. Una aplicación frecuente es el uso de filtros bloom en el almacenamiento en caché web. Usamos el filtro bloom para determinar si una URL dada está en el caché o no. ¿Por qué no simplemente accedemos al caché para determinar eso? Si obtenemos un sí, todavía tenemos que ir al caché para recuperar la página web (que podría no estar allí), pero en caso de que no, podríamos haber obtenido la misma respuesta utilizando el caché (que probablemente esté optimizado para búsquedas rápidas). ¿de todas formas?).
El problema es que tu ejemplo no es tan bueno.
en un caché web, si la url no está presente, tiene que hacer una llamada costosa a la red de todos modos, así que guardar un acceso al disco no es un gran problema. así que tienes razón al cuestionar esto (y el comentario de Diego Basch no está muy bien pensado, imho).
Así que fui a buscar por qué usaste ese ejemplo. y resulta que el artículo de wikipedia menciona que el caché de la web de squid usa filtros bloom. pero no se usan de la manera que describiste. en su lugar, se utilizan para decidir qué caché seleccionar entre un conjunto de cachés distribuidos. y se utilizan principalmente para ahorrar espacio (porque squid puede almacenar muchos objetos en caché, por lo que estas tablas serían muy grandes).
Para obtener más información sobre los filtros de calamar y floración, visite http://wiki.squid-cache.org/SquidFaq/CacheDigests
de lo contrario, la otra respuesta aquí, de templatetypedef, está bien: comprobar si hay sitios malos es un ejemplo mucho mejor.
Los filtros Bloom están diseñados para situaciones en las que un falso negativo es una cosa muy mala y un falso positivo es aceptable.
Por ejemplo, suponga que está creando un navegador web y tiene una lista negra conocida de sitios web fraudulentos. Su lista negra es enorme, en cientos de gigabytes, por lo que no puede enviarla con el navegador. Sin embargo, puede almacenarlo en sus propios servidores. En ese caso, podría enviar el navegador con un filtro Bloom de un tamaño apropiado que contenga todas las URL. Antes de visitar un sitio, lo buscas en el filtro. Luego, si obtiene una respuesta negativa, tiene la garantía de que la URL no está en la lista negra y solo puede visitar el sitio. Si obtiene una respuesta de "sí", el sitio puede ser malo, por lo que puede hacer que el navegador llame a su servidor principal para obtener la respuesta real. El hecho de que pueda guardar una gran cantidad de llamadas al servidor aquí sin sacrificar la precisión es importante.
La idea de caché es similar a esta configuración. Puede consultar el filtro para ver si la página está en el caché. Si obtiene una respuesta negativa, tiene la garantía de que no se almacenará en la memoria caché y puede realizar una operación costosa para extraer los datos de la fuente principal. De lo contrario, puede verificar el caché para ver si realmente está allí. En raras ocasiones es posible que necesite verificar el caché, ver que no esté allí, luego extraerlo de la fuente principal, pero nunca perderá accidentalmente algo realmente en el caché.
¡Espero que esto ayude!
Los filtros Bloom pueden ser útiles cuando se cumplen las dos condiciones siguientes:
- Un falso negativo es inaceptable
- El costo de la búsqueda es costoso en relación con el costo de la búsqueda en un filtro Bloom
El primer punto es bastante simple. El segundo punto generalmente se vuelve significativo cuando se puede almacenar un filtro Bloom en la memoria primaria, pero la búsqueda real puede tener resultados en la base de datos, lo que puede ser muy "costoso" en relación con la realización de cierto número de hashes en la clave seguida de una búsqueda en memoria (es decir, un filtro de Bloom).
Si solo se cumple uno de los criterios anteriores, los filtros Bloom no son la mejor solución al problema.
Los ahorros llegan cuando uno puede eliminar una búsqueda costosa porque se sabe que no hay posibilidad de obtener una coincidencia. Este es el valor del primer punto: los filtros Bloom no generan falsos negativos, por lo que si no se encuentra una coincidencia en el filtro, no tiene sentido pasar al siguiente paso, más costoso, de recuperar los datos asociados con la clave.
Cuando el filtro tiene un impacto, se requiere una búsqueda costosa para verificar el resultado (eliminar los falsos positivos) y recuperar datos relacionados. Aquí existe la posibilidad de no encontrar nada debido a un falso positivo y es por esto que el filtro debe ajustarse para minimizar este riesgo a un nivel aceptable. Un filtro Bloom funcional debe tener una tasa de falsos positivos baja para que el costo general de la búsqueda permanezca bajo.
Ahora, si, como usted dice, su caché ya está optimizada para una búsqueda rápida, entonces la utilidad de un filtro Bloom puede ser cuestionable.