Comment mettre en œuvre Redis des dizaines de milliards de solutions de stockage de clés

1. Contexte des exigences

Ce scénario d'application est une exigence de stockage de cache DMP, et DMP doit gérer de nombreux Les données d'identification de tiers, y compris la relation de mappage entre chaque cookie multimédia et son propre cookie (ci-après collectivement appelés superrid), incluent également la balise de population de superid, la balise de population de l'identifiant mobile (principalement IDFA et imei), et certains ID de liste noire, IP et autres données.

Il n'est pas difficile d'utiliser HDFS pour stocker des centaines de milliards d'enregistrements hors ligne, mais pour DMP, il doit fournir des requêtes en temps réel de l'ordre de la milliseconde. Étant donné que l'ID du cookie lui-même est instable, le comportement de navigation de nombreux utilisateurs réels entraînera la génération d'un grand nombre de nouveaux cookies. Seules les données cartographiques peuvent être synchronisées à temps pour atteindre la balise de population DMP, et des hits plus élevés ne peuvent pas être obtenus. via le préchauffage, ce qui pose de grands défis au stockage du cache.

Après des tests réels, pour les données ci-dessus, le stockage conventionnel de plus de 5 milliards d'enregistrements kv nécessite plus de 1 To de mémoire si plusieurs copies haute disponibilité sont nécessaires, la consommation sera également énorme. , kv Les longueurs inégales entraîneront également une grande fragmentation de la mémoire, ce qui nécessite une solution de stockage à très grande échelle pour résoudre les problèmes ci-dessus.

2. Quels types de données sont stockés ? Le sexe, l'âge, la géolocalisation correspondants sont principalement le mappage des cookies multimédias avec superid. Voici un exemple de stockage de données : 1) ID du PC :

Numéro de média - cookie multimédia=>supperid

supperid => ; {age=>codage du groupe d'âge, genre=>codage du genre, geo=>codage de l'emplacement géographique}

2) ID côté appareil :

imei ou idfa = > >hashmap, et les données de l'appareil doivent stocker un type de

key=>hashmap.

3. Caractéristiques des données

Touche courte valeur courte : où superid est un numéro à 21 chiffres : tel que 1605242015141689522 ; imei est en minuscule md5 : tel que 2d131005dc0f37d362a5d97094103633 ; idfa est en majuscule avec "-" md5 : tel que : 51DFFC83-9541-4411-FA4F-356 927E39D04;#🎜🎜 #

Les propres cookies des médias varient en longueur ;

1. doit fournir des services pour la quantité totale de données, superrid c'est des dizaines de milliards, la cartographie médiatique représente des centaines de milliards, et l'identification mobile représente des milliards de niveaux

2. Il y a des milliards de relations cartographiques générées chaque jour
3. # ; 🎜🎜#

   Pour les données relativement chaudes, elles peuvent être prédites dans une large fenêtre de temps (il reste quelques cookies stables restants

4. Les données chaudes ne peuvent pas être prédites pour les données cartographiques actuelles, dont beaucoup sont des cookies nouvellement générés ;

4.

6. 1) Différentes longueurs peuvent facilement provoquer une fragmentation de la mémoire

2) En raison du grand nombre de pointeurs, le taux d'extension de la mémoire est relativement élevé, généralement 7 fois, ce qui est un problème courant dans le stockage en mémoire pure ;

3) Bien que sa popularité puisse être prédite par le comportement des cookies, il y a encore de nombreux identifiants nouvellement générés chaque jour (le pourcentage est sensible et ne sera pas divulgué pour le moment); 4) En raison des exigences de service dans l'environnement du réseau public (délai du réseau public domestique de 60 ms ou moins) dans les 100 ms, donc en principe, la cartographie et les balises de population nouvellement mises à jour du day doit être entièrement en mémoire, afin de ne pas laisser la requête tomber dans les données froides du backend ; 5) En termes de business, toutes les données doivent en principe être conservées pendant au au moins 35 jours voire plus ;

6) La mémoire reste relativement chère, et des solutions de stockage avec des dizaines de milliards de clés voire des centaines de milliards de clés sont impératives !

5. Solution

5.1 Stratégie d'élimination #🎜🎜 #

Une grande quantité de nouvelles données entre dans la base de données chaque jour, il est donc particulièrement important de nettoyer les données en temps opportun. C'est une raison majeure du manque de stockage. La méthode principale consiste à découvrir et à conserver les données chaudes et à éliminer les données froides. Le nombre d'utilisateurs du réseau est loin d'atteindre les milliards, et leurs identifiants continueront d'évoluer au fil du temps et auront une certaine durée de vie. Ainsi, dans une large mesure, les identifiants que nous stockons sont en réalité invalides. En fait, la logique de la requête frontale est l'exposition publicitaire, qui est liée au comportement humain, il y aura donc un certain degré de répétabilité dans le comportement d'accès d'un identifiant dans une certaine fenêtre de temps (peut-être une campagne, une demi-heure). mois, quelques mois).

Avant l'initialisation des données, nous utilisons d'abord hbase pour agréger et dédupliquer les identifiants de journaux, et délimiter la plage TTL, généralement 35 jours, afin que les identifiants qui ne sont pas apparus au cours des 35 derniers jours puissent être coupés. De plus, le délai d'expiration est fixé dans Redis à 35 jours. Lors de l'accès et de l'activation, la clé sera renouvelée, le délai d'expiration sera prolongé et celles qui n'apparaissent pas dans les 35 jours seront naturellement éliminées. Cela peut être efficace pour les cookies ou les identifiants stables. Il a en fait été prouvé que la méthode de prolongation de la durée de vie est plus pratique pour l'IDFA et l'IMEI, et que l'accumulation à long terme peut donner des résultats très idéaux.

5.2 Réduire l'expansion

La taille de l'espace de la table de hachage et le nombre de clés déterminent le conflit taux (ou Mesuré par le facteur de charge), dans une plage raisonnable, plus il y a de clés, plus l'espace de la table de hachage est grand et la mémoire consommée sera naturellement grande. De plus, un grand nombre de pointeurs eux-mêmes sont des entiers longs, ce qui rend l'extension de la mémoire de stockage considérable. Parlons d’abord de la façon de réduire le nombre de clés.

Commençons par comprendre une structure de stockage. Selon les étapes suivantes, key1=>value1 peut être stocké dans Redis, ce à quoi nous nous attendons. Utilisez d'abord une valeur de hachage aléatoire md5 (clé) de longueur fixe comme clé Redis, que nous appelons BucketId, et stockez key1=>value1 dans la structure hashmap, afin que le client puisse suivre le processus ci-dessus lors de l'interrogation Calculer le hachage et l'interrogation valeur1.

Les modifications du processus sont simplement décrites comme : get(key1) -> hget(md5(key1), key1) pour obtenir value1.

Si nous permettons à de nombreuses clés d'entrer en collision dans l'espace BucketId via un pré-calcul, alors on peut considérer qu'il y a plusieurs clés sous un seul BucketId. Par exemple, s’il y a en moyenne 10 clés par BucketId, nous réduirons théoriquement le nombre de clés redis de plus de 90 %.

La mise en œuvre spécifique est un peu gênante et vous devez réfléchir à l'échelle de capacité avant d'utiliser cette méthode. Le md5 que nous utilisons habituellement est une hexString de 32 bits (caractères hexadécimaux), et son espace est de 128 bits. Cette grandeur est trop grande. Ce que nous devons stocker, c'est des dizaines de milliards, soit environ 33 bits, nous avons donc besoin d'un mécanisme pour le stocker. calculer Pour générer un hachage avec le nombre approprié de chiffres, et afin d'économiser de la mémoire, nous devons utiliser tous les types de caractères (codes ASCII entre 0 et 127) pour remplir au lieu de HexString, afin que la longueur de la clé puisse être raccourcie à la moitié.

Voici la méthode d'implémentation spécifique

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><p>La taille finale de l'espace BucketId est déterminée par le bit de paramètre L'ensemble facultatif de tailles d'espace est une puissance entière discrète de 2. Voici une explication de la raison pour laquelle seuls 7 bits sont disponibles dans un octet. En effet, lorsque Redis stocke la clé, elle doit être ASCII (0 ~ 127), et non un tableau d'octets. Si nous prévoyons des dizaines de milliards de stockage et prévoyons de partager 10 KV par compartiment, nous n'avons alors besoin que de 2 ^ 30 = 1073741824 compartiments, ce qui correspond au nombre final de clés. </p>
<p><strong><em>5.3 Réduire la fragmentation</em></strong></p>
<p>La principale raison de la fragmentation est que la mémoire ne peut pas être alignée et que la mémoire ne peut pas être réaffectée après expiration et suppression. Grâce à la méthode décrite ci-dessus, nous pouvons stocker les étiquettes de population et les données de cartographie de la manière ci-dessus. L'avantage est que les clés Redis sont de longueur égale. De plus, nous avons également apporté des optimisations pertinentes pour la clé dans le hashmap, en interceptant les six derniers chiffres du cookie ou de l'identifiant de l'appareil comme clé, ce qui peut également garantir l'alignement de la mémoire. En théorie, il existe une possibilité de conflit, mais la probabilité. du même suffixe dans le même compartiment Extrêmement faible (Imaginez que l'ID est une chaîne presque aléatoire. La probabilité de 10 ID aléatoires composés de caractères plus longs avec le même suffixe * nombre d'échantillons de compartiment = valeur attendue du conflit </p>
<p>De plus, il existe un moyen très simple mais efficace de réduire la fragmentation. Redémarrez l'esclave, puis forcez le basculement pour basculer le maître et l'esclave. Cela équivaut à défragmenter la mémoire du maître. </p>
<p>Recommandez l'allocation de mémoire Google-tcmalloc et facebook-jemalloc, ce qui peut réduire la fragmentation de la mémoire et la consommation de mémoire lorsque la valeur n'est pas grande. Certaines personnes ont mesuré que la libc est plus économique lorsque la valeur est importante. </p>
<p><em><strong>6. Problèmes auxquels il faut prêter attention dans la méthode du seau de hachage md5</strong></em></p>
<p>1) L'ampleur du stockage kv doit être planifiée à l'avance. La plage flottante est d'environ dix à quinze fois le nombre de seaux. Par exemple, si vous souhaitez stocker des dizaines de milliards de KV, il est préférable de choisir 30 bits ~ 31 bits comme nombre de compartiments. En d'autres termes, il n'y a aucun problème de croissance de l'entreprise dans une plage raisonnable (croissance de 10 à 15 fois). Si l'entreprise se développe trop souvent, le hashset augmentera trop rapidement, augmentera le temps de requête et même déclenchera. le seuil de la liste zip, ce qui entraîne une augmentation spectaculaire de la mémoire. </p>
<p>2) Convient aux valeurs courtes. Si la valeur est trop grande ou s'il y a trop de champs, cela ne convient pas, car cette méthode doit nécessiter que la valeur soit retirée en une seule fois. Par exemple, l'étiquette de population est un. très petit encodage, même seulement 3 ou 4 bits (bit) peuvent être installés. 3) La méthode typique d'échange de temps contre de l'espace. Étant donné que notre scénario commercial ne nécessite pas de qps extrêmement élevés, qui se situent généralement entre 100 millions et 1 milliard par jour, il est également très économique d'utiliser de manière raisonnable la location du processeur. valeur. </p>
<p>Après avoir utilisé le résumé d'informations, la clé ne peut pas être générée aléatoirement à partir de Redis car la taille de la clé est réduite et la longueur est limitée. Si un export est nécessaire, il doit être exporté en données froides. </p>
<p>5) expire doit être implémenté par vous-même. L'algorithme actuel est très simple, puisque la consommation n'augmentera que pendant l'opération d'écriture, elle est échantillonnée selon une certaine proportion pendant l'opération d'écriture. il y a plus de 15 entrées. Les clés expirées sont supprimées et l'horodatage TTL est stocké dans les 32 premiers bits de la valeur. </p>
<p>6) Des statistiques de consommation des seaux sont à faire. Les clés expirées doivent être nettoyées régulièrement pour garantir que les requêtes Redis ne ralentiront pas. </p>
<p><em><strong>7. Résultats des tests </strong></em></p>
<p>10 milliards d'enregistrements de données d'étiquetage et de cartographie de la population. </p>
<p>Avant l'optimisation, environ 2,3 T d'espace de stockage étaient utilisés et le taux de fragmentation était d'environ 2 et après l'optimisation, environ 500 g d'espace de stockage étaient utilisés et l'utilisation moyenne de chaque seau était d'environ 4 ; Le taux de fragmentation est d'environ 1,02. Cela consomme très peu de CPU lors des requêtes. </p>
<p>Il faut également mentionner que la consommation de chaque seau n'est pas réellement uniforme, mais conforme à une distribution polynomiale. </p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/887/227/168543988688361.png" class="lazy" alt="Comment mettre en œuvre Redis des dizaines de milliards de solutions de stockage de clés"></p>
<p>La formule ci-dessus peut calculer la distribution de probabilité de la consommation du seau. Cette formule vise simplement à rappeler à tous que la consommation du bucket ne peut pas être considérée comme acquise. Il est possible que certains buckets contiennent des centaines de clés. Mais la vérité n’est pas si exagérée. Imaginez que vous lancez une pièce de monnaie et qu'il n'y a que deux résultats possibles : pile et face. Cela équivaut à n'avoir que deux seaux. Si vous lancez un nombre infini de fois, chaque fois équivaut à une expérience de Bernoulli, alors les deux seaux seront certainement très égaux. Lorsque vous effectuez de nombreuses expériences de Bernoulli généralisées et que vous faites face à de nombreux barils, la distribution de probabilité est comme une magie invisible qui plane sur vous. La répartition de la consommation des seaux tendra vers une valeur stable. Examinons ensuite la répartition spécifique de la consommation des buckets : </p>
<p>Grâce aux statistiques d'échantillonnage</p>
<p>31 bits (plus de 2 milliards) de buckets, la consommation moyenne est de 4,18</p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/887/227/168543988662298.png" class="lazy" alt="Comment mettre en œuvre Redis des dizaines de milliards de solutions de stockage de clés"></p>
<p>10 milliards, économisant 1,8T de mémoire. Texte original réécrit :

Non seulement cela a permis d'économiser 78 % de la mémoire d'origine, mais l'indicateur de consommation du compartiment était également bien inférieur à la valeur finale attendue de 15. </p>
<p>Il y a aussi un certain nombre de buckets qui n'apparaissent pas. S'il y en a trop, la planification sera inexacte. En fait, le nombre est cohérent avec la distribution binomiale pour 2^30 buckets pour stocker 2^32kv. il y a environ (millions) de buckets inexistants. Niveau, peu d'impact) : </p>
<p>Math.pow((1 - 1.0 / Math.pow(2, 30)), Math.pow(2, 32)) * Math. .pow(2, 30);</p>
<p>pour Ne vous inquiétez pas trop du problème de consommation déséquilibrée des buckets. Au fil du temps, les buckets avec HLEN dépassant 15 seront réduits lors de l'écriture selon le principe de distribution polynomiale. le nombre d'expériences atteint un certain niveau, la répartition des seaux aura tendance à être relativement uniforme (la pièce est lancée d'innombrables fois, donc le nombre de têtes et de queues doit être cohérent), mais nous réduisons la consommation du seau grâce à la stratégie d'expiration En fait, chaque seau a connu de nombreuses expériences. </p></r.length>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!