¿La mejor solución para encontrar una intersección de conjunto de 1 x 1 millón? Redis, Mongo, otro

Question

Hola a todos y gracias de antemano. Soy nuevo en el juego NoSQL, pero mi lugar de trabajo actual me ha encomendado la tarea de establecer comparaciones de algunos big data.

Nuestro sistema tiene conjunto de etiquetas de cliente y conjuntos de etiquetas específicas. Una etiqueta es un número de 8 dígitos.
Un conjunto de etiquetas de cliente puede tener hasta 300 etiquetas, pero promedia 100 etiquetas
Un conjunto de etiquetas específicas puede tener hasta 300 etiquetas pero promedia 40 etiquetas.

El cálculo previo no es una opción, ya que estamos buscando una base de clientes potenciales de mil millones de usuarios.

(Estas etiquetas son jerárquicos por lo que tener una etiqueta implica que también tiene sus marcas para padres y ancestros. Poner esa información a un lado por el momento.)

Cuando un cliente golpea nuestro sitio, tenemos que intersectan su etiqueta establecer contra un millón de conjuntos de etiquetas específicas lo más rápido posible. El conjunto de clientes debe contener todos los elementos del conjunto objetivo para que coincida.

He estado explorando mis opciones y la intersección establecida en Redis parece ideal. Sin embargo, mi búsqueda en Internet no ha revelado cuánto carnero se necesitaría para guardar un millón de juegos de etiquetas. Me doy cuenta de que la intersección sería muy rápida, pero es una solución factible con Redis.

Me doy cuenta de que esto es fuerza bruta e ineficiente. También quería usar esta pregunta como medio para obtener sugerencias sobre cómo se manejó este tipo de problema en el pasado. Como se dijo anteriormente, las etiquetas se almacenan en un árbol. También comencé a considerar a Mongodb como una posible solución.

Gracias de nuevo

Answer 1

Este es un problema interesante, y creo que Redis puede ayudar aquí.

Redis puede almacenar conjuntos de enteros utilizando un formato optimizado "intset". Ver http://redis.io/topics/memory-optimization para más información.

Creo que la estructura de datos correcta aquí es una colección de conjuntos de etiquetas específicas, más un índice inverso para asignar etiquetas a sus conjuntos de etiquetas específicas.

Para almacenar dos conjuntos de etiquetas específicas:

0 -> [ 1 2 3 4 5 6 7 8 ] 
1 -> [ 6 7 8 9 10 ] 

me gustaría utilizar:

# Targeted tag sets 
sadd tgt:0 1 2 3 4 5 6 7 8 
sadd tgt:1 2 6 7 8 9 10 
# Reverse index 
sadd tag:0 0 
sadd tag:1 0 
sadd tag:2 0 1 
sadd tag:3 0 
sadd tag:4 0 
sadd tag:5 0 
sadd tag:6 0 1 
sadd tag:7 0 1 
sadd tag:8 0 1 
sadd tag:9 1 
sadd tag:10 1 

Este índice inversa es bastante fácil de mantener cuando se añaden/eliminan del sistema de conjuntos de etiquetas específicas.

El consumo de memoria global depende de la cantidad de etiquetas que son comunes a múltiples conjuntos de etiquetas específicas. Es bastante fácil almacenar pseudodatos en Redis y simular el consumo de memoria. Lo he hecho usando un simple node.js script.

Para 1 millón de conjuntos de etiquetas específicas (etiquetas de 8 dígitos, 40 etiquetas por conjunto), el consumo de memoria es cercano a 4 GB cuando hay pocas etiquetas compartidas por los conjuntos de etiquetas específicas (más de 32 millones de entradas en el índice inverso), y aproximadamente 500 MB cuando las etiquetas se comparten mucho (solo 100K entradas en el índice inverso).

Con esta estructura de datos, encontrar los conjuntos de etiquetas específicas que contienen todas las etiquetas de un cliente determinado es extremadamente eficiente.

1- Get customer tag set (suppose it is 1 2 3 4) 
2- SINTER tag:1 tag:2 tag:3 tag:4 
    => result is a list of targeted tag sets having all the tags of the customer 

La operación intersección es eficiente porque Redis es lo suficientemente inteligente como para ordenar las series por cardinalidad y comienza con el conjunto que tiene la cardinalidad más bajo.

Ahora entiendo que debe implementar la operación inversa (es decir, encontrar los conjuntos de etiquetas específicas que tienen todas sus etiquetas en el conjunto de etiquetas del cliente). El índice inverso todavía puede ayudar.

Aquí, en un ejemplo en el feo pseudo-código:

1- Get customer tag set (suppose it is 1 2 3 4) 
2- SUNIONSTORE tmp tag:1 tag:2 tag:3 tag:4 
    => result is a list of targeted tag sets having at least one tag in common with the customer 
3- For t in tmp (iterating on the selected targeted tag sets) 
     n = SCARD tgt:t (cardinality of the targeted tag sets) 
     intersect = SINTER customer tgt:t 
     if n == len(intersect), this targeted tag set matches 

para que nunca tenga que probar la etiqueta del cliente frente a 1M dirigido conjuntos de etiquetas. Puede confiar en el índice inverso para restringir el alcance de la búsqueda a un nivel aceptable.

Answer 2

esto podría ser útil:

Estudio de caso: El uso de Redis se cruzan en conjuntos muy grandes (120M + 120M +) con

http://redis4you.com/articles.php?id=016&name=Case+Study%3A+Using+Redis+intersect+on+very+large+sets

Answer 3

Las respuestas proporcionadas me ayudaron inicialmente. Sin embargo, a medida que nuestra base de clientes creció, me topé con una gran técnica que incluía el uso de bits de redis y operadores de bits para realizar análisis de cientos de millones de usuarios muy rápidamente.

Revisa este artículo. Antirez, creador de redis, también hace referencia a esto mucho.

http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/