¿La mejor solución para encontrar 1 x 1 millón de intersección establecida? Redis, Mongo, otros
Hola a todos y gracias de antemano. Soy nuevo en el juego NoSQL, pero mi lugar de empleo actual me ha encargado 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 un promedio de 100 etiquetas
Un conjunto de etiquetas específicas puede tener hasta 300 etiquetas, pero un promedio de 40 etiquetas.
El cálculo previo no es una opción, ya que estamos buscando una base de clientes potencial de mil millones usuario.
(Estas etiquetas son jerárquicas, por lo que tener una etiqueta implica que también tiene sus etiquetas padre y antepasado. Deja esa información a un lado por el momento.)
Cuando un cliente llega a nuestro sitio, necesitamos intersectar su conjunto de etiquetas con un millón de conjuntos de etiquetas segmentadas lo más rápido posible. El conjunto de cliente debe contener todos los elementos del conjunto de destino para que coincida.
He estado explorando mis opciones y la intersección establecida en Redis parece que sería ideal. Sin embargo, mi trolling a través de Internet no ha revelado cuánta ram se requeriría para mantener un millón de conjuntos de etiquetas. Me doy cuenta de que la intersección sería muy rápida, pero es esta 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 las formas en que este tipo de problema se ha manejado en el pasado. Como se indicó anteriormente, las etiquetas se almacenan en un árbol. He comenzado a mirar Mongodb como una posible solución como bien.
Gracias de nuevo
3 answers
Este es un problema interesante, y creo que Redis puede ayudar aquí.
Redis puede almacenar conjuntos de enteros utilizando un formato "intset" optimizado. Véase 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 de destino, además de un índice inverso para asignar etiquetas a sus conjuntos de etiquetas de destino.
Para almacenar dos conjuntos de etiquetas:
0 -> [ 1 2 3 4 5 6 7 8 ]
1 -> [ 6 7 8 9 10 ]
Usaría:
# 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 inverso es muy fácil de mantener cuando se agregan/eliminan del sistema conjuntos de etiquetas específicos.
El consumo global de memoria depende del número de etiquetas que son comunes a varios conjuntos de etiquetas de destino. Es bastante fácil almacenar pseudo-datos en Redis y simular el consumo de memoria. Lo he hecho usando un nodo simple .js script .
Para 1 millón de conjuntos de etiquetas objetivo (las etiquetas son números de 8 dígitos, 40 etiquetas por conjunto), el consumo de memoria es cercano a 4 GB cuando hay muy pocas etiquetas compartidas por los conjuntos de etiquetas objetivo (más de 32M entradas en el índice inverso), y alrededor de 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 de destino que contienen todas las etiquetas de un cliente dado 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 de intersección es eficiente porque Redis es lo suficientemente inteligente como para ordenar los conjuntos por cardinalidad y comienza con el conjunto que tiene el menor cardinalidad.
Ahora entiendo que necesita implementar la operación converse (es decir, encontrar los conjuntos de etiquetas de destino que tengan todas sus etiquetas en el conjunto de etiquetas del cliente). El índice inverso todavía puede ayudar.
Aquí en un ejemplo en 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
Por lo que nunca tendrá que probar el conjunto de etiquetas de cliente contra conjuntos de etiquetas dirigidas de 1M. Puede confiar en el índice inverso para restringir el alcance de la búsqueda a un nivel aceptable.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-06-19 20:22:34
Esto podría ser útil:
Estudio de caso: Uso de Redis intersect en conjuntos muy grandes (120M+ con 120M+)
Http://redis4you.com/articles.php?id=016&name=Case+Study%3A+Using+Redis+intersect+on+very+large+sets
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-08-29 15:34:53
Las respuestas proporcionadas me ayudaron inicialmente. Sin embargo, a medida que nuestra base de clientes creció, me topé con una gran técnica que implica el uso de bits de cadena redis y operadores de bits para realizar análisis en cientos de millones de usuarios muy rápidamente.
Mira este artículo. Antirez, creador de redis, también hace mucho referencia a esto.
Http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-20 20:50:08