Cómo utilizar Bloomfilter para construir un sistema de caché Java a gran escala

El almacenamiento en caché es un concepto clave que resuelve muchos problemas del software actual. Las aplicaciones pueden consumir mucha CPU. Por supuesto, no querrás repetir estas operaciones una y otra vez. En cambio, puedes hacerlo sólo una vez y mantener el resultado en la memoria como caché. A veces, el cuello de botella del sistema radica en las operaciones de E / S, como consultar repetidamente la base de datos, intentar almacenar en caché los resultados y solo consultar los datos para actualizar el caché cuando los datos cambian.

De manera similar a la situación anterior, hay situaciones en las que se requiere una búsqueda rápida para decidir cómo manejar una nueva solicitud. Por ejemplo, considere la siguiente situación, en la que necesita confirmar si una URL apunta a un sitio web malicioso. Las necesidades pueden ser muchas. Si almacena en caché las URL de todos los sitios web maliciosos, ocupará mucho espacio. O en otro caso, debe confirmar que la cadena ingresada por el usuario contiene el nombre de un lugar en los Estados Unidos. Como "Museo de Washington" - en esta cadena,

Es por eso que necesitamos ir más allá de los diagramas de estructura de datos básicos y buscar respuestas en estructuras de datos más avanzadas como los filtros de floración. Puedes pensar en un filtro Bloom como un conjunto en Java al que agregas elementos para consultar si un elemento existe (como un HashSet). Si el filtro Bloom dice que no existe tal elemento, entonces definitivamente no contiene el elemento, pero si el filtro Bloom dice que sí existe un elemento, el resultado puede ser incorrecto. Si el filtro Bloom se diseña cuidadosamente, la probabilidad de error se puede controlar dentro de un rango aceptable.

(1) Explique que el filtro Bloom está diseñado como una matriz de bits de n elementos, con todos los bits establecidos en 0 al principio.

(2) Para agregar un elemento, debe agregar un elemento. Se deben proporcionar K funciones hash. Cada función puede devolver un valor, que debe ser el índice de la matriz de bits (se puede obtener tomando la longitud de la matriz). La matriz de bits en ese índice se establece en 1. Por ejemplo, la primera función hash opera en el elemento I y devuelve x. De manera similar, la segunda y tercera funciones hash devuelven y y z, por lo que:

(3. ) Encuentre el elemento por De la explicación anterior, podemos saber que si desea diseñar un buen filtro Bloom, debe seguir las siguientes pautas:

Una buena función hash puede devolver una amplia gama de valores hash ​​tanto como sea posible.

El tamaño de la matriz de bits (indicada por m) es importante: si es demasiado pequeña, pronto a todos los bits se les asignará el valor 1, aumentando la probabilidad de falsos positivos.

El número de funciones hash ( denotado por k), también es importante para la distribución uniforme de los valores del índice

La fórmula para calcular m es la siguiente:

Aquí p es la tasa aceptable de falsos positivos.

La fórmula para calcular k es la siguiente:

Aquí k=el número de funciones hash, m=el número de. matrices de bits, n=el número de elementos a detectar (estas letras se usarán más adelante). /p>

(4) Algoritmo hash El algoritmo hash es lo que afecta el rendimiento del filtro Bloom. Es necesario elegir un. Función hash eficiente pero que requiere mucho tiempo. En el artículo "Menos funciones hash, los mismos indicadores de rendimiento: construcción", analizamos cómo elegir dos funciones hash para simular k funciones hash. calcule dos funciones hash h1 (x) y h2 (x). Luego, puede usar esto. Se utilizan dos funciones hash para simular el efecto de generar k funciones hash:

El rango de valores de I aquí es. un número entero de 1 a k.

La biblioteca de clases de guayaba de Google utiliza esta tecnología para implementar el filtro Bloom. La lógica principal del algoritmo hash es la siguiente:

(5) Aplicación. A partir de la fórmula matemática, podemos saber claramente cómo usar el filtro Bloom para resolver el problema. Sin embargo, es necesario comprender bien las áreas donde los filtros Bloom pueden resolver el problema. todas las ciudades de Estados Unidos.

Dado que el número de ciudades se puede determinar de forma aproximada, se puede determinar el valor de n (el número de elementos a detectar). Modifique el valor de p (probabilidad de falso positivo) según sea necesario. En este caso, puede diseñar un mecanismo de almacenamiento en caché que requiera menos tiempo de consulta y tenga una alta utilización de memoria.

(6) Existe una implementación de la biblioteca de clases Google Guava. Al observar el constructor de esta clase, debe establecer la cantidad de elementos que se detectarán y la tasa de falsos positivos.