Najlepsze rozwiązanie dla znalezienia 1 x 1 milion zestaw przecięcia? Redis, Mongo, inne

Question

Najlepsze rozwiązanie dla znalezienia 1 x 1 milion zestaw przecięcia? Redis, Mongo, inne

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

Nasz system ma zestaw tagów klienta i docelowe zestawy tagów. Znacznik to 8-cyfrowy numer.
Zbiór znaczników klienta może mieć do 300 znaczników, ale średnio 100 znaczników
Docelowy zestaw znaczników może mieć do 300 znaczników, ale średnio 40 znaczników.

Wstępne obliczanie nie jest opcją, ponieważ strzelamy do potencjalnej bazy klientów wynoszącej miliard użytkowników.

(te znaczniki są hierarchiczne, więc posiadanie jednego znacznika oznacza, że masz również jego znaczniki nadrzędne i nadrzędne. Zostaw te informacje na chwilę.)

Gdy klient trafi na naszą stronę, musimy jak najszybciej przeciąć ich zestaw tagów z milionem docelowych zestawów tagów. Zestaw klienta musi zawierać wszystkie elementy zestawu docelowego, aby pasowały.

Sprawdzałem swoje możliwości i zestaw przecięcia w Redis wydaje się być idealny. Jednak moje trolling przez internet nie ujawnił, ile pamięci ram będzie potrzebne do przechowywania miliona zestawów tagów. Zdaję sobie sprawę, że skrzyżowanie będzie szybkie jak błyskawica, ale czy jest to wykonalne rozwiązanie z Redis.

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

Thanks again

26

mongodb redis nosql bigdata

Author: Community, 2012-06-19

Source

3 answers

To może być pomocne:

Studium przypadku: użycie Redis intersect na bardzo dużych zestawach (120m+z 120m+)

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

6

Author: Nick,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-08-29 15:34:53

Udzielone odpowiedzi początkowo mi pomogły. Jednak gdy nasza baza klientów rosła, natknąłem się na świetną technikę polegającą na używaniu bitów strunowych redis i operatorów bitów do bardzo szybkiego wykonywania analiz na setkach milionów użytkowników.

Zobacz ten artykuł. Antirez, twórca redis, również odnosi się do tego wiele.

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

5

Author: MFD3000,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-02-20 20:50:08

score 29 · Accepted Answer

Jest to interesujący problem i myślę, że Redis może tu pomóc.

Redis może przechowywać zestawy liczb całkowitych przy użyciu zoptymalizowanego formatu "intset". Zobacz http://redis.io/topics/memory-optimization aby uzyskać więcej informacji.

Uważam, że poprawną strukturą danych jest zbiór ukierunkowanych zestawów znaczników, plus odwrotny indeks do mapowania znaczników do ich docelowych zestawów znaczników.

Do przechowywania dwóch ukierunkowanych zestawów tagów:

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

Użyłbym:

 # 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

Ten odwrotny indeks jest dość łatwe w utrzymaniu, gdy docelowe zestawy znaczników są dodawane/usuwane z systemu.

Globalne zużycie pamięci zależy od liczby znaczników, które są wspólne dla wielu docelowych zestawów znaczników. Bardzo łatwo jest przechowywać pseudodane w Redis i symulować zużycie pamięci. Zrobiłem to używając prostego węzła.skrypt js .

Dla 1 miliona docelowych zestawów znaczników (znaczniki to 8 cyfr, 40 znaczników na zestaw), zużycie pamięci jest bliskie 4 GB, gdy są bardzo niewiele tagów współdzielonych przez docelowe zestawy tagów (ponad 32m wpisów w indeksie odwrotnym) i około 500 MB, gdy znaczniki są współdzielone dużo (tylko 100k wpisów w indeksie odwrotnym).

Dzięki tej strukturze danych wyszukiwanie docelowych zestawów znaczników zawierających wszystkie znaczniki danego klienta jest niezwykle efektywne.

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 przecięcia jest wydajna, ponieważ Redis jest wystarczająco inteligentny, aby zamówić zestawy na kartę i zaczyna się od zestawu o najniższym cardinality.

Teraz rozumiem, że musisz zaimplementować operację converse (tj. znalezienie docelowych zestawów znaczników posiadających wszystkie znaczniki w zestawie znaczników klienta). Odwrotny indeks nadal może pomóc.

Tutaj w przykładzie w brzydkim pseudo-kodzie:

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 nigdy nie musisz testować zestawu znaczników klienta z zestawami znaczników ukierunkowanych na 1M. Możesz polegać na odwrotnym indeksie, aby ograniczyć zakres wyszukiwania do akceptowalnego poziomu.