Лучшее решение для поиска пересечения 1 x 1 миллион наборов? Редис, Монго, другие

Это интересная проблема, и я думаю, что Redis может помочь здесь.

Redis может хранить наборы целых чисел, используя оптимизированный формат «intset». Дополнительную информацию см. на странице http://redis.io/topics/memory-optimization.

Я считаю, что правильная структура данных здесь представляет собой набор целевых наборов тегов, а также обратный индекс для сопоставления тегов с их целевыми наборами тегов.

Чтобы сохранить два целевых набора тегов:

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

Я хотел бы использовать:

 # 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

Этот обратный индекс довольно легко поддерживать, когда из системы добавляются/удаляются целевые наборы тегов.

Потребление глобальной памяти зависит от количества тегов, которые являются общими для нескольких целевых наборов тегов. В Redis довольно легко хранить псевдоданные и моделировать потребление памяти. Я сделал это с помощью простого скрипта node.js.

Для 1 миллиона целевых наборов тегов (теги представляют собой 8-значные числа, 40 тегов в наборе) потребление памяти приближается к 4 ГБ, когда целевые наборы тегов используют очень мало общих тегов (более 32 МБ). записей в обратном индексе) и около 500 МБ, если теги часто используются совместно (всего 100 тыс. записей в обратном индексе).

С такой структурой данных поиск целевых наборов тегов, содержащих все теги данного клиента, чрезвычайно эффективен.

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

Операция пересечения эффективна, поскольку Redis достаточно умен, чтобы упорядочить наборы по количеству элементов и начать с набора с наименьшим количеством элементов.

Теперь я понимаю, что вам нужно реализовать обратную операцию (т. е. найти целевые наборы тегов, все теги которых входят в набор тегов клиента). Обратный индекс все еще может помочь.

Вот пример в уродливом псевдокоде:

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

Таким образом, вам никогда не придется тестировать набор тегов клиента в сравнении с 1 миллионом целевых наборов тегов. Вы можете положиться на обратный индекс, чтобы ограничить область поиска до приемлемого уровня.

это может быть полезно:

Практический пример: использование Redis intersect на очень больших наборах (120+ миллионов с 120+ миллионов)

http://redis4you.com/articles.php?id=016&name=Case+Study%3A+Использование+Redis+intersect+on+very+large+sets

Предоставленные ответы помогли мне изначально. Однако по мере того, как наша клиентская база росла, я наткнулся на отличный метод, включающий использование строковых битов Redis и битовых операторов для очень быстрого анализа сотен миллионов пользователей.

Проверьте эту статью. Антирез, создатель Redis, также часто ссылается на это.

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