1. Anforderungshintergrund
In diesem Anwendungsszenario muss DMP viele ID-Daten von Drittanbietern verwalten, einschließlich der Zuordnungsbeziehung zwischen jedem Medien-Cookie und seinem eigenen Cookie (im Folgenden zusammengefasst). als Superrid bezeichnet) sowie Es enthält das Populations-Tag von Superrid, das Populations-Tag von Mobil-IDs (hauptsächlich IDFA und IMEI) sowie einige Blacklist-IDs, IPs und andere Daten.
Es ist nicht schwierig, HDFS zum Offline-Speichern von Hunderten Milliarden Datensätzen zu verwenden, aber für DMP müssen Echtzeitabfragen auf Millisekundenebene bereitgestellt werden. Da die Cookie-ID selbst instabil ist, führt das Surfverhalten vieler realer Benutzer zur Generierung einer großen Anzahl neuer Cookies. Nur die Zuordnungsdaten können rechtzeitig synchronisiert werden, um das DMP-Populations-Tag zu erreichen, und es können keine höheren Treffer erzielt werden durch Vorheizen, was große Herausforderungen an die Cache-Speicherung mit sich bringt.
Nach tatsächlichen Tests erfordert die herkömmliche Speicherung von mehr als 5 Milliarden kv-Datensätzen mehr als 1 T Speicher. Wenn mehrere Kopien mit hoher Verfügbarkeit erforderlich sind, ist der Verbrauch enorm wird auch verursachen Es bringt eine starke Speicherfragmentierung mit sich, was eine sehr umfangreiche Speicherlösung erfordert, um die oben genannten Probleme zu lösen.
2. Welche Art von Daten werden gespeichert?
Personen-Tags sind hauptsächlich Cookie, IMEI, IDFA und ihr entsprechendes Geschlecht (Geschlecht), Alter (Altersgruppe), Geo (Region) usw.; Es handelt sich hauptsächlich um die Medienzuordnung von Cookies zu Superriden. Das Folgende ist ein Beispiel für die Datenspeicherung:
1) PC-seitige ID:
Mediennummer – Mediencookie=>supperid
supperid => , geo= >Geolocation-Kodierung}
2) Geräteseitige ID:
imei oder idfa => PC Die Daten müssen zwei Arten von key=>value und key=>hashmap speichern, während die Gerätedaten einen Typ von
key=>hashmap speichern müssen.
3. Dateneigenschaften
Superid ist eine 21-stellige Zahl: z. B. 1605242015141689522; imei ist Kleinbuchstabe md5: z 4103633 ;idfa ist ein Großbuchstabe mit „-“ md5: für Beispiel: 51DFFC83 – 9541-4411-FA4F-356927E39D04; 3) Obwohl die Beliebtheit von Cookies anhand ihres Verhaltens vorhergesagt werden kann, gibt es immer noch viele neu generierte IDs Tag (der Prozentsatz ist sensibel und wird vorerst nicht bekannt gegeben);
5) Aus geschäftlicher Sicht werden grundsätzlich alle Daten für mindestens 35 Tage aufbewahrt Tage oder sogar länger;
5.1 Eliminierungsstrategie
Da täglich große Mengen neuer Daten in die Datenbank gelangen, ist es besonders wichtig, die Daten rechtzeitig zu bereinigen, was eine wichtige Rolle spielt Grund für Lagermangel. Die Hauptmethode besteht darin, heiße Daten zu erkennen und zu speichern und kalte Daten zu eliminieren.
Die Zahl der Netzwerknutzer erreicht bei weitem nicht die Milliardengrenze, und ihre IDs werden sich im Laufe der Zeit weiterhin ändern und eine gewisse Lebensdauer haben. Die von uns gespeicherten IDs sind also größtenteils ungültig. Tatsächlich ist die Logik der Front-End-Abfrage die Werbepräsenz, die mit menschlichem Verhalten zusammenhängt, sodass das Zugriffsverhalten einer ID in einem bestimmten Zeitfenster (vielleicht eine Kampagne, ein halbes Jahr) ein gewisses Maß an Wiederholbarkeit aufweist Monat, ein paar Monate).
Vor der Dateninitialisierung verwenden wir zunächst hbase, um Protokoll-IDs zu aggregieren und zu deduplizieren und den TTL-Bereich abzugrenzen, normalerweise 35 Tage, sodass IDs, die in den letzten 35 Tagen nicht angezeigt wurden, abgeschnitten werden können. Darüber hinaus ist die Ablaufzeit in Redis auf 35 Tage eingestellt. Beim Zugriff und Drücken wird der Schlüssel erneuert, die Ablaufzeit verlängert und diejenigen, die nicht innerhalb von 35 Tagen angezeigt werden, werden auf natürliche Weise entfernt. Dies kann für stabile Cookies oder IDs effektiv sein. Es ist tatsächlich erwiesen, dass die Lebensverlängerungsmethode für IDFA und IMEI praktischer ist und eine langfristige Akkumulation sehr ideale Ergebnisse erzielen kann.
5.2 Erweiterung reduzieren
Die Größe des Hash-Tabellenbereichs und die Anzahl der Schlüssel bestimmen die Konfliktrate (oder gemessen am Auslastungsfaktor): Je mehr Schlüssel, desto größer die Hash-Tabelle Speicherplatz und Verbrauch Der Speicher wird natürlich groß sein. Darüber hinaus handelt es sich bei vielen Zeigern selbst um Long-Integer-Typen, sodass die Speichererweiterung erheblich ist. Lassen Sie uns zunächst darüber sprechen, wie Sie die Anzahl der Schlüssel reduzieren können. Lassen Sie uns zunächst eine Speicherstruktur verstehen. Gemäß den folgenden Schritten kann key1=>value1 in Redis gespeichert werden, was wir erwarten. Verwenden Sie zunächst einen zufälligen Hash-MD5-Wert (Schlüsselwert) fester Länge als Redis-Schlüssel, den wir BucketId nennen, und speichern Sie key1 => value1 in der Hashmap-Struktur, damit der Client beim Abfragen dem obigen Prozess folgen kann. Berechnen Sie den Hash und fragen Sie ihn ab Wert1.
Die Prozessänderungen werden einfach wie folgt beschrieben: get(key1) -> hget(md5(key1), key1) um value1 zu erhalten.
Wenn wir durch Vorberechnung zulassen, dass viele Schlüssel im BucketId-Bereich kollidieren, kann davon ausgegangen werden, dass sich unter einer BucketId mehrere Schlüssel befinden. Wenn beispielsweise durchschnittlich 10 Schlüssel pro BucketId vorhanden sind, reduzieren wir theoretisch die Anzahl der Redis-Schlüssel um mehr als 90 %.
Die spezifische Implementierung ist etwas mühsam und Sie müssen über die Kapazitätsskala nachdenken, bevor Sie diese Methode verwenden. Der MD5, den wir normalerweise verwenden, ist ein 32-Bit-Hex-String (Hexadezimalzeichen) und sein Speicherplatz ist zu groß. Wir müssen mehrere zehn Milliarden speichern, was etwa 33 Bit entspricht Berechnen Um einen Hash mit der entsprechenden Anzahl von Ziffern zu generieren und um Speicherplatz zu sparen, müssen wir anstelle von HexString alle Zeichentypen (ASCII-Codes zwischen 0 und 127) zum Füllen verwenden, damit die Länge des Schlüssels verkürzt werden kann auf die Hälfte.
Das Folgende ist die spezifische Implementierungsmethode
public static byte [] getBucketId(byte [] key, Integer bit) {
MessageDigest mdInst = MessageDigest.getInstance("MD5");
mdInst.update(key);
byte [] md = mdInst.digest();
byte [] r = new byte[(bit-1)/7 + 1];// 因为一个字节中只有7位能够表示成单字符
int a = (int) Math.pow(2, bit%7)-2;
md[r.length-1] = (byte) (md[r.length-1] & a);
System.arraycopy(md, 0, r, 0, r.length);
for(int i=0;i<r.length if r return></r.length>Nach dem Login kopieren
Die endgültige Größe des BucketId-Raums wird durch das Parameterbit bestimmt. Der optionale Satz von Raumgrößen ist eine diskrete ganzzahlige Potenz von 2. Hier finden Sie eine Erklärung, warum in einem Byte nur 7 Bits verfügbar sind. Dies liegt daran, dass Redis beim Speichern des Schlüssels ASCII (0 ~ 127) und kein Byte-Array sein muss. Wenn wir zig Milliarden Speicher planen und 10 KVs pro Bucket gemeinsam nutzen möchten, benötigen wir nur 2^30=1073741824 Buckets, was der endgültigen Anzahl an Schlüsseln entspricht.
5.3 Fragmentierung reduzieren
Der Hauptgrund für die Fragmentierung besteht darin, dass der Speicher nicht ausgerichtet werden kann und der Speicher nach Ablauf und Löschung nicht neu zugewiesen werden kann. Mit der oben beschriebenen Methode können wir Bevölkerungsbezeichnungen und Zuordnungsdaten auf die oben beschriebene Weise speichern. Der Vorteil besteht darin, dass die Redis-Schlüssel gleich lang sind. Darüber hinaus haben wir auch relevante Optimierungen für den Schlüssel in der Hashmap vorgenommen und die letzten sechs Ziffern des Cookies oder der Geräte-ID als Schlüssel abgefangen, wodurch auch die Speicherausrichtung sichergestellt werden kann. Theoretisch besteht die Möglichkeit eines Konflikts, aber die Wahrscheinlichkeit des gleichen Suffixes im gleichen Bucket Extrem niedrig (Stellen Sie sich vor, die ID ist eine nahezu zufällige Zeichenfolge. Die Wahrscheinlichkeit, dass 10 zufällige IDs aus längeren Zeichen mit demselben Suffix bestehen * Anzahl der Bucket-Stichproben = erwarteter Konfliktwert
Darüber hinaus gibt es eine sehr geringe, aber effektive Möglichkeit, die Fragmentierung zu reduzieren. Starten Sie den Slave neu und erzwingen Sie dann einen Failover, um den Master und den Slave zu wechseln.
Empfehlen Sie die Speicherzuweisung von Google-tcmalloc und facebook-jemalloc, die die Speicherfragmentierung und den Speicherverbrauch reduzieren können, wenn der Wert nicht groß ist. Einige Leute haben gemessen, dass libc wirtschaftlicher ist, wenn der Wert groß ist.
6. Probleme, die bei der MD5-Hash-Bucket-Methode beachtet werden müssen
1) Die Größe der KV-Speicherung muss im Voraus geplant werden. Der Floating-Bereich beträgt etwa das Zehn- bis Fünfzehnfache der Anzahl der Buckets Wenn Sie beispielsweise Dutzende Milliarden KV speichern möchten, wählen Sie am besten 30 Bit bis 31 Bit als Anzahl der Buckets. Mit anderen Worten, es gibt kein Problem beim Geschäftswachstum innerhalb eines angemessenen Bereichs (10- bis 15-faches Wachstum), was dazu führt, dass das Hashset zu schnell wächst, die Abfragezeit verlängert und sogar ausgelöst wird Der Schwellenwert für die Zip-Liste wird überschritten, was dazu führt, dass der Speicher dramatisch zunimmt.
2) Wenn der Wert zu groß ist oder zu viele Felder vorhanden sind, ist dies nicht geeignet, da bei dieser Methode der Wert auf einmal herausgenommen werden muss. Die Bevölkerungsbezeichnung ist beispielsweise a Sehr kleine Kodierung, sogar nur 3 oder 4 Bits (Bit) können eingebaut werden. 3) Die typische Methode zum Austausch von Zeit gegen Speicherplatz. Da unser Geschäftsszenario keine extrem hohen QPS erfordert, die im Allgemeinen bei 100 Millionen bis 1 Milliarde pro Tag liegen, ist es auch sehr wirtschaftlich, die CPU-Miete sinnvoll zu nutzen Wert.
Nach der Verwendung von Information Digest kann der Schlüssel nicht zufällig von Redis generiert werden, da die Größe des Schlüssels reduziert und die Länge begrenzt ist. Wenn ein Export erforderlich ist, muss dieser in Kaltdaten exportiert werden.
5) Ablauf muss von Ihnen selbst implementiert werden. Da der Verbrauch nur während des Schreibvorgangs zunimmt, wird er während des Schreibvorgangs in einem bestimmten Verhältnis abgetastet und zur Bestimmung werden HLEN-Treffer verwendet ob mehr als 15 Einträge vorhanden sind. Abgelaufene Schlüssel werden gelöscht und der TTL-Zeitstempel wird in den ersten 32 Bits des Werts gespeichert.
6) Statistiken zum Bucket-Verbrauch müssen erstellt werden. Abgelaufene Schlüssel müssen regelmäßig bereinigt werden, um sicherzustellen, dass Redis-Abfragen nicht langsamer werden.
7. Testergebnisse
10 Milliarden Datensätze mit Bevölkerungskennzeichnung und Kartierungsdaten.
Vor der Optimierung wurden etwa 2,3 T Speicherplatz verwendet, und die Fragmentierungsrate betrug etwa 2. Nach der Optimierung wurden etwa 500 g Speicherplatz verwendet, und die durchschnittliche Nutzung jedes Buckets betrug etwa 4. Die Fragmentierungsrate liegt bei etwa 1,02. Dies verbraucht beim Abfragen sehr wenig CPU.
Es sollte auch erwähnt werden, dass der Verbrauch jedes Eimers nicht wirklich gleichmäßig ist, sondern einer Polynomverteilung entspricht.
Mit der obigen Formel kann die Wahrscheinlichkeitsverteilung des Eimerverbrauchs berechnet werden. Diese Formel soll nur alle daran erinnern, dass der Bucket-Verbrauch nicht selbstverständlich ist. Es ist möglich, dass einige Buckets Hunderte von Schlüsseln enthalten. Aber die Wahrheit ist nicht so übertrieben. Stellen Sie sich vor, Sie werfen eine Münze und es gibt nur zwei mögliche Ergebnisse: Kopf und Zahl. Es ist gleichbedeutend mit nur zwei Eimern. Wenn Sie unendlich oft werfen, entspricht jedes Mal einem Bernoulli-Experiment, dann sind die beiden Eimer definitiv sehr gleichmäßig. Wenn Sie viele verallgemeinerte Bernoulli-Experimente durchführen und mit vielen Fässern konfrontiert werden, ist die Wahrscheinlichkeitsverteilung wie eine unsichtbare Magie, die über Ihnen schwebt. Die Verbrauchsverteilung der Buckets tendiert zu einem stabilen Wert. Werfen wir als Nächstes einen Blick auf die spezifische Bucket-Verbrauchsverteilung:
Durch Stichprobenstatistik
31-Bit-Buckets (mehr als 2 Milliarden) beträgt der durchschnittliche Verbrauch 4,18
#🎜 🎜#
10 Milliarden haben 1,8T Speicher eingespart. Originaltext umgeschrieben:
Dadurch wurden nicht nur 78 % des ursprünglichen Speichers eingespart, sondern auch der Bucket-Verbrauchsindikator lag deutlich unter dem erwarteten Endwert von 15.
Es gibt auch eine bestimmte Anzahl von Buckets, die nicht angezeigt werden, was zu einer ungenauen Planung führt. Tatsächlich stimmt die Anzahl mit der Binomialverteilung überein Buckets zum Speichern von 2^32 kV gibt es nicht. Es gibt ungefähr (Millionen Level, geringe Auswirkung) Buckets:
Math.pow((1 - 1.0 / Math.pow(2, 30)) , Math.pow(2, 32)) * Math.pow(2, 30);
Machen Sie sich keine allzu großen Sorgen über das Problem des ungleichmäßigen Bucket-Verbrauchs im Laufe der Zeit, Buckets mit HLEN Über 15 wird beim Schreiben gemäß der Polynomverteilung reduziert. Das Prinzip besteht darin, dass die Eimerverteilung tendenziell gleichmäßig ist, wenn die Anzahl der Experimente ein bestimmtes Niveau erreicht (wenn eine Münze unzählige Male geworfen wird, verringert sich die Anzahl der Köpfe und Die Enden sollten gleich sein), aber wir haben den Eimerverbrauch durch die Ablaufstrategie reduziert. Tatsächlich wurde für jedes Fass viel experimentiert.
Das obige ist der detaillierte Inhalt vonSo implementieren Sie Redis zig Milliarden wichtiger Speicherlösungen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
