Najlepsze rozwiązanie do wyszukiwania skrzyżowania o 1 x 1 milion? Redis, Mongo, inne

Question

Witam wszystkich i z góry dziękuję. Jestem nowy w grze NoSQL, ale moje obecne miejsce pracy zleciło mi zestaw porównań dużych danych.

Nasz system ma zestawy tagów klienta i ukierunkowane zestawy tagów. Znacznik to ośmiocyfrowa liczba.
Zestaw tagów klienta może zawierać do 300 tagów, ale średnie 100 tagów
Docelowy zestaw tagów może zawierać do 300 tagów, ale średnio 40 tagów.

Wstępne obliczenia nie są opcją, ponieważ kręcimy dla potencjalnej bazy klientów liczącej miliard użytkowników.

(Znaczniki te są hierarchiczne więc posiadające jeden znacznik oznacza, że ​​masz również podmiotem dominującym i-przodków tagi. Umieścić te informacje na bok na chwilę).

Gdy klient trafia na naszą stronę, musimy przecinać ich tag ustąpić jednemu milionowi wybranych zestawów tagów tak szybko, jak to możliwe. Zestaw klientów musi zawierać wszystkie elementy wybranego zestawu, aby pasowały do ​​siebie.

Przeglądałem moje opcje, a przecięcie zestawu w Redis wydaje się idealne. Jednak moje trollingowanie przez Internet nie ujawniło, ile pamięci RAM będzie wymagało posiadania miliona zestawów tagów. Zdaję sobie sprawę, że skrzyżowanie będzie błyskawiczne, ale jest to rozwiązanie możliwe z Redis.

Zdaję sobie sprawę, że jest to brutalna siła i nieefektywna. Chciałem również użyć tego pytania jako sposobu, aby uzyskać sugestie dotyczące sposobów rozwiązywania tego typu problemów w przeszłości. Jak wspomniano wcześniej, tagi są przechowywane w drzewie. Zacząłem też patrzeć na Mongodb jako na możliwe rozwiązanie.

Dzięki ponownie

Answer 1

To jest ciekawy problem i myślę, Redis może pomóc tutaj.

Redis może przechowywać zestawy liczb całkowitych za pomocą zoptymalizowanego formatu "intset". Aby uzyskać więcej informacji, patrz http://redis.io/topics/memory-optimization.

Uważam, że poprawna struktura danych jest tutaj zbiorem ukierunkowanych zestawów znaczników oraz indeksem odwrotnym do mapowania znaczników do ich docelowych zestawów znaczników.

przechowywanie dwóch docelowych zestawach TAG:

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

byłoby używać:

# 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 

odwracała wskaźnika jest bardzo łatwe w obsłudze, gdy docelowe ustawia znacznik dodano/usuwa się z układu.

Globalne zużycie pamięci zależy od liczby tagów, które są wspólne dla wielu docelowych zestawów znaczników. Łatwo jest przechowywać pseudo-dane w Redis i symulować zużycie pamięci. Zrobiłem to przy użyciu simple node.js script.

Dla 1 miliona ukierunkowanych zestawów znaczników (znaczniki to 8 cyfr, 40 znaczników na zbiór), zużycie pamięci jest bliskie 4 GB, gdy jest bardzo mało znaczników udostępnianych przez docelowe zestawy znaczników (więcej niż 32M wpisów w odwrotnym indeksie) i około 500 MB, gdy tagi są współużytkowane dużo (tylko 100 k wpisów w odwrotnym indeksie).

Dzięki tej strukturze danych znalezienie ukierunkowanych zestawów znaczników zawierających wszystkie znaczniki danego klienta jest niezwykle wydajne.

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 

Operacja jest efektywne, ponieważ skrzyżowanie Redis jest wystarczająco inteligentny, aby zamówić zestawy za liczności i zaczyna z zestawem posiadającym najniższy liczność.

Teraz rozumiem, że musisz zaimplementować operację odwrotną (tj. Znaleźć ukierunkowane zestawy znaczników mające wszystkie znaczniki w zestawie znaczników klienta). Odwrotny indeks nadal może pomóc.

tu za przykład w brzydkim pseudo-kod:

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 

więc nie trzeba testować tag klienta ustawiony na 1M ukierunkowane zestawy znaczników. Możesz polegać na indeksie wstecznym, aby ograniczyć zakres wyszukiwania do akceptowalnego poziomu.

Answer 2

to może być pomocne:

Case Study: Korzystanie Redis przecinają się na bardzo dużych zbiorów (120M 120M + z +)

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

Answer 3

udzielonych odpowiedzi pomogły mi początkowo. Jednak wraz z rozwojem naszej bazy klientów natknąłem się na świetną technikę wykorzystującą bity ciągów Redis i operatory bitów do szybkiego przeprowadzania analityki setek milionów użytkowników.

Sprawdź ten artykuł. Antirez, twórca redis, również odnosi się do tego bardzo często.

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