Beste Lösung für die Suche nach 1 x 1 Million Schnittpunkt? Redis, Mongo, andere

Question

Hallo allerseits und vielen Dank im Voraus. Ich bin neu im NoSQL-Spiel, aber mein gegenwärtiger Arbeitsplatz hat mich mit Vergleichen von einigen Big Data beauftragt.

Unser System verfügt über Kunden-Tag-Set und gezielte Tag-Sets. Ein Tag ist eine 8-stellige Nummer.
Ein Kunden-Tag-Set kann bis zu 300 Tags enthalten, aber durchschnittlich 100 Tags.
Ein Targeted-Tag-Set kann bis zu 300 Tags enthalten, aber durchschnittlich 40 Tags.

Vorberechnung ist keine Option, da wir für einen potenziellen Kundenstamm von einer Milliarde Benutzer schießen.

(Diese Tags sind hierarchisch so einen Tag bedeutet hat, dass man auch seine Eltern und Vorfahren Tags hat. Legen Sie diese Informationen für den Moment beiseite.)

Wenn ein Kunde unserer Seite trifft, müssen wir ihren Tag schneiden Setzen Sie so schnell wie möglich eine Million Ziel-Tag-Sets ab. Der Kundensatz muss alle Elemente des Zielsatzes enthalten, die übereinstimmen müssen.

Ich habe meine Optionen untersucht und die Schnittmenge in Redis scheint, als wäre es ideal. Jedoch hat mein Trolling durch das Internet nicht offenbart, wie viel Ram benötigt würde, um eine Million Tagsets zu halten. Ich weiß, dass die Kreuzung blitzschnell sein würde, aber das ist eine machbare Lösung mit Redis.

Ich realisiere, das ist rohe Gewalt und ineffizient. Ich wollte diese Frage auch als Mittel nutzen, um Vorschläge dafür zu bekommen, wie diese Art von Problem in der Vergangenheit gehandhabt wurde. Wie bereits erwähnt, sind die Tags in einem Baum gespeichert. Ich habe angefangen, Mongodb als mögliche Lösung zu betrachten.

Thanks again

Answer 1

Dies ist ein interessantes Problem, und ich denke, Redis hier helfen kann.

Redis kann Ganzzahlsätze mit einem optimierten "intset" -Format speichern. Weitere Informationen finden Sie unter http://redis.io/topics/memory-optimization.

Ich glaube, dass die korrekte Datenstruktur hier eine Sammlung von zielgerichteten Tag-Sets ist, plus einen umgekehrten Index, um Tags ihren Ziel-Tag-Sets zuzuordnen.

zwei gezielte Tag Sätze speichern:

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

ich verwenden würde:

# 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 

Dieser umgekehrte Index ganz einfach ist, wenn Sätze gezielt Tages zu halten hinzugefügt/aus dem System entfernt.

Der globale Speicherverbrauch hängt von der Anzahl der Tags ab, die mehreren Ziel-Tag-Sets gemeinsam sind. Es ist ziemlich einfach, Pseudodaten in Redis zu speichern und den Speicherverbrauch zu simulieren. Ich habe es mit einem simple node.js script getan.

Für 1 Million ausgerichtete Tag-Sets (Tags sind 8-stellige Zahlen, 40 Tags pro Set) liegt der Speicherverbrauch nahe 4 GB wenn nur sehr wenige Tags von den Targeted-Tag-Sets geteilt werden (mehr als 32M Einträge) im umgekehrten Index) und ungefähr 500 MB, wenn die Tags viel geteilt werden (nur 100K Einträge im umgekehrten Index).

Mit dieser Datenstruktur ist das Auffinden der Ziel-Tag-Sets, die alle Tags eines bestimmten Kunden enthalten, äußerst effizient.

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 

Der Schnittvorgang ist effizient, weil Redis intelligent genug ist, um die Sätze pro Kardinalität bestellen und beginnt mit dem Satz der niedrigsten Kardinalität aufweisen.

Jetzt verstehe ich, müssen Sie die umgekehrte Operation implementieren (d. H. Die Ziel-Tag-Sets mit allen ihren Tags in der Kunden-Tag-Set zu finden). Der umgekehrte Index kann immer noch helfen.

Hier in einem Beispiel in hässlichen Pseudo-Code:

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 

So müssen Sie nie gegen 1 M gesetzt, den Kunden-Tag testen gezielte Tag-Sets. Sie können sich auf den umgekehrten Index verlassen, um den Umfang der Suche auf ein akzeptables Maß zu beschränken.

Answer 2

könnte dies nützlich sein:

Fallstudie: Mit Redis auf sehr große Mengen schneiden (120M + mit 120M +)

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

Answer 3

Die Antworten zunächst half mir zur Verfügung gestellt. Als unser Kundenstamm wuchs, stolperte ich jedoch über eine großartige Technik, die die Verwendung von Redis-String-Bit- und -Bit-Operatoren zur schnellen Analyse von Hunderten von Millionen von Benutzern umfasste.

Überprüfen Sie diesen Artikel aus. Antirez, der Schöpfer von Redis, bezieht sich auch sehr darauf.

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