Bloomfilter y Cassandra = ¿Por qué se usa y por qué hasheado varias veces?

Question

leí esto: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html

Mis preguntas:

1.) ¿Es correcto, que Cassandra sólo utiliza el filtro de floración, para averiguar la (tabla de cadenas Ordenado SST) que muy probablemente contiene la clave ? Como podría haber varias SST y Cassandra no sabe en qué SST podría estar una llave? Por lo tanto, para acelerar esta búsqueda en todos los SST, se utilizan filtros Bloom. ¿Es esto correcto? (Estoy tratando de entender cómo funciona Casandra ...)

2.) ¿Por qué las claves (como se explica en el enlace anterior) hasheñaron varias veces? ¿Es correcto que las claves necesiten procesarse con diferentes funciones Hash varias veces para obtener una mejor distribución aleatoria de los Bits? Si esto es incorrecto, ¿por qué una clave necesita ser hasheada varias veces? Esto costará ciclos de CPU? Si tengo la salida de varias funciones Hash, ¿qué se hace con los resultados? ¿Están ANDed o XORded? ¿Esto hace alguna diferencia?

3.) Usando MD5, ¿cuán grande es la diferencia de "Fales positivos usando el Bloomfilter" en comparación con SHA1 (que según los artículos se distribuye al azar)? ¿Por qué MD5 no se distribuye al azar?

Muchas gracias !! Jens

Answer 1

1) Sí, ver this en el cassandra wiki,

Cassandra utiliza filtros Bloom salvar IO cuando se realiza una búsqueda de claves: cada SSTable tiene un filtro de floración asociada con el que Cassandra comprueba antes de hacer cualquier disco busca, realizando consultas para las claves que no existen casi gratis

El columns of a key se puede extender en varias posiciones inestables. Si no fuera por los filtros bloom, cada lectura de una tecla debería leer cada variable, lo que es prohibitivamente costoso. Mediante el uso de filtros de bloom, cassandra casi siempre solo tiene que buscar en los elementos inestables que contienen datos para esa clave.

2) This puede darle una mejor comprensión de los filtros de floración. Usted hash k veces para dar posiciones independientes en una matriz de tamaño m. Por ejemplo, si A y B son los elementos en el conjunto, y tiene k = 2, sus funciones hash son MD5 y SHA1, y m = 16, se puede hacer

md5(A) % m = 7 
sha1(A) % m = 12 

md5(B) % m = 15 
sha1(B) % m = 12 

Esto le da m [7 ], m [12] y m [15] son ​​verdaderos para el filtro.

Para ver si C está en el conjunto, lo hace

md5(C) % m = 8 
sha1(C) % m = 12 

Como m [8] es falsa, ya sabes C no está en el conjunto, sin embargo, para D

md5(D) % m = 7 
sha1(D) % m = 15 

Ambos m [7] ym [15] son ​​verdaderos, pero D no está en el conjunto, entonces D es un falso positivo.

Esto cuesta ciclos de CPU, pero está intercambiando ciclos de CPU por io reducido, lo que tiene sentido para cassandra.

3) El artículo no menciona md5. md5 se distribuye aleatoriamente, y supongo que la diferencia entre md5 y sha-1 para los filtros de bloom no es grande.

Answer 2

Como una adición al 3er punto de la respuesta por puentes.

MD5 y SHA-1 se distribuyen aleatoriamente pero son funciones de cifrado hash. Al implementar cualquier tipo de filtro de floración, el único cuello de botella en el rendimiento es el tiempo necesario para el hash. Es por eso que las funciones criptográficas cuando se usan disminuyen el rendimiento de la aplicación.

Se recomienda utilizar funciones hash no criptográficas como Murmur hash. This paper, recomienda para construir y función hash como:

g(x) = h1(x) + i * h2(x) 

donde g (x) es la nueva función de hash, h1 y h2 son las funciones de hash estándar y i es el número de iteración que va de 0 a k.

Al usar esta técnica, se puede alcanzar el mismo rendimiento con dos funciones hash (suponiendo que k> 2).