Подтвердить что ты не робот

Лучшее решение для поиска 1 х 1 млн. Пересечений? Редис, Монго, другие

Привет всем и спасибо заранее. Я новичок в игре NoSQL, но мое текущее место работы поставило перед собой задачу сопоставить некоторые большие данные.

Наша система имеет набор тегов клиента и целевые наборы тегов. Тег - это 8-значное число.
Набор тегов клиента может содержать до 300 тегов, но в среднем 100 тегов
Целевой набор тегов может содержать до 300 тегов, но в среднем 40 тегов.

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

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

Когда клиент попадает на наш сайт, нам нужно как можно быстрее пересечь их набор тегов на один миллион целевых наборов тегов. Набор клиентов должен содержать все элементы целевого набора, которые должны соответствовать.

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

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

Еще раз спасибо

4b9b3361

ОТВЕТЫ

Ответ 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 script.

Для 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

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

Ответ 3

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

Проверьте эту статью. Antirez, создатель redis, также ссылается на это много.

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