English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Préambule
La liste compressée (ziplist) est composée d'une série de blocs mémoire codés de manière spéciale, elle joue un rôle très important dans l'optimisation du stockage des données de Redis. Cet article résume un des structures de données très utilisées dans Redis, la liste chainée compressée ziplist. Cette structure de données est partout dans Redis, à part la liste, de nombreuses autres structures de données utilisent également pour la transition, par exemple, le SortedSet mentionné dans l'article précédent. Ne disons pas plus, regardons ensemble la présentation détaillée.
I. Introduction à la structure de données de la liste chainée compressée ziplist
Tout d'abord, regardons la structure globale de ziplist, comme dans le graphique suivant :
Schéma de structure de la liste chainée compressée ziplist
Il est évident que les champs sont nombreux et les tailles des octets sont différentes, mais c'est aussi l'essence de la liste chainée compressée. Nous allons les résumer l'un après l'autre.
| champ | signification |
|---|---|
| zlbytes | Ce champ est le premier champ de la liste chainée compressée, c'est un entier sans signe, occupant4octets. Utilisé pour représenter le nombre d'octets occupés par toute la liste chainée compressée (y compris elle-même). |
| zltail | Un entier sans signe, occupant4octets. Utilisé pour stocker le décalage de l'entrée de la tête de la liste chainée compressée au dernier entry (pas l'élément de queue zlend), utilisé dans la scène de saut rapide à la fin de la liste. |
| zllen | Un entier sans signe, occupant2octets. Utilisé pour stocker le nombre total d'entries contenues dans la liste chainée compressée. |
| zlend | Des entrées spéciales, utilisées pour représenter la fin de la liste chainée compressée. Elle occupe un octet et la valeur est constante de255。 |
Résumé de la tête et de la queue de ziplist, voici une autre synthèse de l'entrée la plus importante.
En règle générale, un entry est composé de prevlen, encoding et entry-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-Les trois champs data, field et prevlen composent, mais lorsqu'il s'agit d'un petit entier, l'entrée peut être omise selon l'encodage.
Le premier est le champ prevlen : il représente la longueur de l'entrée précédente, qui a deux méthodes d'encodage.
ensuite est le champ encoding : il utilise différentes méthodes d'encodage selon le contenu actuel de l'élément, comme suit :
1、si le contenu de l'élément est une chaîne, les valeurs de encoding sont :
00xx xxxx : 00 au début indique que la longueur de la chaîne est représentée par6bits représentent.
01xx xxxx | xxxx xxxx : 01Le début indique que la longueur de la chaîne est représentée par14bits représentent, ce qui signifie que14bits sont stockés en grand boutisme.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx :10Le début indique que les quatre octets suivants représentent la longueur de la chaîne, c'est-à-dire32bits sont stockés en grand boutisme.
2、si le contenu de l'élément est un nombre, les valeurs de encoding sont :
1100 0000 : cela signifie que le nombre occupe les bits suivants2octets.
1101 0000：cela signifie que le nombre occupe les bits suivants4octets.
1110 0000：cela signifie que le nombre occupe les bits suivants8octets.
1111 0000 : cela signifie que le nombre occupe les bits suivants3octets.
1111 1110 : cela signifie que le nombre occupe les bits suivants1octets.
1111 1111 : cela signifie que le dernier élément de la liste de chaines compressées (codage spécial).
1111 xxxx : cela signifie que seuls les bits suivants4bits représentent 0~12un entier, en raison de 0000,1110et1111Les trois premiers sont déjà occupés, ce qui signifie que les quatre bits xxxxx ici ne peuvent représenter que 0001~1101, converti en décimal, c'est le nombre1~13, mais Redis stipule qu'il est utilisé pour représenter 0~12, donc lorsque nous rencontrons ce codage, nous devons extraire les quatre derniers bits et les soustraire1pour obtenir la valeur correcte.
dernier est le champ entry-data：si la valeur de l'élément est une chaîne, elle sauvegarde la valeur de l'élément lui-même. Si la valeur de l'élément est un nombre très petit (selon les règles de codage ci-dessus, c'est-à-dire 0~12），s'il n'y a pas ce champ.
L'encodage de la liste de chaines compressées est très complexe, mais c'est aussi l'essence de cette structure de données, regardons un exemple :
Remarque :Cet exemple est mentionné dans le code source de Redis
//composée des éléments2,5composée de la liste de chaines compressées [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end //Le contenu codé de la chaîne "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
Ci-dessus est une séquence en hexadécimal2,5une liste de chaines compressées composée de deux éléments.
Ensuite, insérons un élément de chaîne Hello World à la fin de cette liste chaînée compressée, regardons d'abord comment encoder cette chaîne, selon les règles de codage convenues, il faut d'abord utiliser un octet pour représenter la longueur de l'élément précédent, ici l'élément précédent est5，elle occupe deux octets au total, donc d'abord utiliser un octet pour représenter la longueur de l'élément précédent 02，à suivre est le codage de la chaîne, la longueur de la chaîne à ajouter est11（l'espace est aussi pris en compte), converti en binaire c'est1011，selon les règles de codage de la chaîne, en utilisant 0000 1011Cela signifie, converti en hexadécimal c'est 0b, puis ajoutons le code ASCII de la chaîne de caractères elle-même, combinés pour obtenir le codage de la chaîne : [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。
À ce moment-là, toute la liste chaînée compressée devient :
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff] | | | | | | | zlbytes zltail entries "2" "5" "Hello World" end
Deuxième partie : analyse du code source des commandes ziplist
Une fois que nous avons compris les règles de codage ci-dessus, nous allons examiner les opérations source de la partie ziplist compressée. Dans cet article, nous allons résumer les principes fondamentaux de la liste chaînée compressée en créant une liste chaînée compressée, insérant un élément, supprimant un élément et recherchant un élément.
Tout d'abord, créons
//Définir la taille de l'en-tête de la liste chaînée compressée composée de zlbytes, zltail et zllen
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//Créer une liste chaînée compressée et renvoyer un pointeur vers cette liste
unsigned char *ziplistNew(void) {
//C'est pourquoi+1C'est parce que l'élément final occupe un octet, ce qui est également la taille minimale d'une liste chaînée compressée
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//Allouer de la mémoire
unsigned char *zl = zmalloc(bytes);
//Définir la taille de la liste
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//Définir l'offset du dernier élément
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//Définir le nombre d'éléments
ZIPLIST_LENGTH(zl) = 0;
//Définir l'élément final (ce qui n'est qu'une demande d'espace au-dessus)
zl[bytes-1] = ZIP_END;
return zl;
}
La logique de création de la liste chaînée compressée est très simple, il s'agit de demander un espace fixe contenant les noeuds d'en-tête et de fin, puis d'initialiser le contexte de la liste.
En comparaison avec la création, le code source de l'ajout d'éléments est très long. Pour faciliter la compréhension, avant de voir le code source, nous devons d'abord organiser la logique de l'ajout d'éléments.
Ces trois étapes sont les étapes clés, d'autres opérations comme la mise à jour de l'offset du noeud final, la modification du nombre d'éléments de la liste, etc. Bien sûr, étant donné que la liste chaînée compressée est implémentée sur la base d'un tableau, la copie de mémoire est inévitable lors de l'insertion ou de la suppression d'éléments.
Après avoir résumé les étapes ci-dessus, nous allons commencer à analyser les lignes de code source, c'est long, voyons lentement :
//Les quatre paramètres sont respectivement : la liste chaînée compressée, la position d'insertion (l'élément nouveau est inséré après l'élément p), la valeur de l'élément, la longueur de l'élément
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//C'est ici que l'on sauvegarde la longueur actuelle de la liste chaînée
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789;
zlentry tail;
//1. L'objectif de cette logique est de obtenir la longueur de l'élément précédent
if (p[0] != ZIP_END) {
//Si l'élément à la position d'insertion n'est pas l'élément final, obtenir la longueur de cet élément
//ici, pour faciliter l'utilisation future, il a été découpé, prevlensize enregistre la longueur de l'élément encoding, prevlen enregistre la longueur de l'élément lui-même
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//si l'élément à la position d'insertion est l'élément final, alors il faut insérer l'élément nouveau à la fin de la liste chaînée
//obtenir le dernier élément de la liste chaînée (note : le dernier élément n'est pas l'élément final)
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
//si le dernier élément n'est pas l'élément final, alors cet élément est l'élément préalable de l'élément nouveau, obtenir la longueur de cet élément
prevlen = zipRawEntryLength(ptail);
}
//sinon cela signifie que la liste chaînée n'a pas encore d'éléments, c'est-à-dire que la longueur de l'élément préalable de l'élément nouveau est de 0
}
//2. coder l'élément nouveau pour obtenir la taille totale de l'élément nouveau
if (zipTryEncoding(s,slen,&value,&encoding)) {
//si c'est un nombre, il faut le coder comme un nombre
reqlen = zipIntSize(encoding);
} else {
//la longueur de l'élément est égale à la longueur de la chaîne
reqlen = slen;
}
//la longueur totale de l'élément nouveau est la longueur de la valeur plus la longueur de l'élément préalable et de l'élément encoding
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//si la position d'insertion n'est pas à la fin de la liste chaînée, il faut vérifier le champ prevlen du élément suivant de l'élément nouveau
//selon les règles de codage ci-dessus, ce champ peut nécessiter un agrandissement
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {}}
nextdiff = 0;
forcelarge = 1;
}
//agrandir le tableau selon la nouvelle taille calculée, car l'adresse du nouveau tableau peut changer, donc ici enregistrer l'ancien décalage
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//calculer la position d'insertion sur le nouveau tableau
p = zl+offset;
//si l'élément inséré n'est pas à la fin de la liste
if (p[0] != ZIP_END) {
//copier l'élément suivant et l'élément nouveau dans le nouveau tableau,-1pour l'élément final
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//Le champ prevlen des éléments suivants de l'élément nouveau
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//Mise à jour de l'offset du dernier élément
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//Lorsque l'élément suivant du nouvel élément n'a pas qu'un seul élément, l'offset de l'élément de fin nouveau doit être ajouté nextdiff
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
//L'élément nouveau est inséré à la fin de la liste, la mise à jour de l'offset de la fin
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0 signifie que la longueur des éléments suivants a changé, par conséquent, nous devons mettre à jour en cascade les éléments suivants des éléments suivants
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//Écrire l'élément nouveau dans la liste
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
//Le stockage de la liste de compression contient le nombre d'éléments+1
ZIPLIST_INCR_LENGTH(zl,1;
return zl;
}
Après l'analyse de la logique d'insertion des éléments, on respire un soupir de soulagement, c'est vraiment long, et les détails sont nombreux.
Ensuite, examinons le processus de suppression des éléments, par rapport à l'ajout, la suppression est relativement simple, après avoir vidé l'élément actuel, il faut copier les éléments suivants un par un (c'est la différence entre les structures de données tableau et liste), puis attention à la mise à jour en cascade, voici le code :
//Les paramètres sont les suivants : liste de compression, position initiale de l'élément à supprimer, nombre d'éléments à supprimer
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int nextdiff = 0;
zlentry first, tail;
//Lecture de l'élément pointé par p et stocké dans first
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {}}
//Compte la longueur totale supprimée
p += zipRawEntryLength(p);
//Compte le nombre d'éléments réellement supprimés
deleted++;
}
//Le nombre d'octets à supprimer de l'élément
totlen = p-first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//Déterminer si la taille de l'élément a changé
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//Modification du champ prevlen de l'élément suivant après la suppression
p -= nextdiff;
zipStorePrevEntryLength(p, first.prevrawlen);
//Mise à jour de l'offset de l'élément de fin
ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//Lorsque le successeur de l'élément supprimé n'a pas qu'un seul élément, l'offset du nouvel élément de fin doit être ajouté nextdiff
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//Déplacer les éléments restants à l'avant
memmove(first.p, p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1;
} else {
//Suppression directe jusqu'à la fin de la liste, pas besoin de copie de mémoire, il suffit de modifier l'offset du dernier élément
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//Redimensionnement de la taille de l'array
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//Modification du nombre d'éléments de la liste
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0 signifie que la taille de l'élément a changé, une mise à jour en cascade est nécessaire
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl, p);
}
return zl;
}
Enfin, regardons l'opération de recherche d'éléments :
//Les paramètres sont les suivants : liste de compression, valeur de l'élément à trouver, longueur de l'élément à trouver, nombre d'éléments sautés entre chaque comparaison
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
int skipcnt = 0;
unsigned char vencoding = 0;
long long vll = 0;
//Tant que n'est pas arrivé à l'élément de fin, continuez à boucler
while (p[0] != ZIP_END) {
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
//Recherchez le champ prevlen de l'élément courant de la liste
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//Recherchez le champ encoding de l'élément courant de la liste
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
//Arrivé à la position de l'élément à comparer
if (skipcnt == 0) {
//Si l'élément courant de la liste est une chaîne
if (ZIP_IS_STR(encoding)) {
//Comparez avec la chaîne à chercher
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
//La correspondance réussie, le pointeur de l'élément à chercher
return p;
}
} else {
//Si l'élément courant est un nombre et vencoding est 0
if (vencoding == 0) {
//Tentez d'encoder le valeur à chercher en nombre
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
//Si l'encodage échoue, cela signifie que l'élément à chercher n'est pas un nombre
//Ensuite, configurez vencoding à la valeur maximale pour jouer un rôle de marqueur
//C'est-à-dire qu'il n'est plus nécessaire de tenter d'encoder le valeur à chercher en nombre
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
//Si vencoding n'est pas égal à UCHAR_MAX, cela signifie que l'élément à chercher a été encodé avec succès en nombre
if (vencoding != UCHAR_MAX) {
//按数字取出当前链表中的元素
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) {
//Si deux nombres sont égaux, retournez le pointeur de l'élément
return p;
}
}
}
//Réinitialiser le nombre d'éléments à sauter
skipcnt = skip;
} else {
//Sauter l'élément
skipcnt--;
}
//Parcourir l'élément suivant
p = q + len;
}
//Après avoir parcouru toute la liste, l'élément n'a pas été trouvé
return NULL;
}
Jusqu'ici, nous avons résumé les principes des quatre opérations de base de la création, ajout, suppression et recherche de la liste compressée.
Troisième partie : Résumé de la structure de données de liste compressée ziplist
L'application de la compression de la liste ziplist dans Redis est très large, c'est l'une des structures de données les plus caractéristiques de Redis. L'essence de cette structure de données réside vraiment dans les règles de codage résumées dans la première partie de l'article. Si vous avez bien compris cette partie, vous pouvez voir le code source pour approfondir votre compréhension.
Il faut dire que la partie source est assez longue, il faut vraiment avoir de la patience, et même moi, pendant que je lis, je suis un peu accablé. Si vous êtes intéressé par le code source, je recommande de suivre ma méthode : d'abord, clarifiez les opérations nécessaires pour une certaine action (par exemple, l'insertion d'un élément mentionné ci-dessus), puis regardez le code, ce qui peut être plus facile à comprendre.
Pour finir, laissons une petite question :既然redis中的ziplist对内存利用率如此之高，那为什么还要提供普通的链表结构供用户使用呢？
Il n'y a pas de réponse standard à cette question, chacun voit ce qu'il veut voir, et chacun voit ce qu'il voit.
Résumé
Voici la totalité du contenu de cet article, j'espère que le contenu de cet article aura une certaine valeur de référence pour vos études ou votre travail. Si vous avez des doutes, vous pouvez laisser des messages pour échanger, merci de votre soutien au tutoriel d'alarme.
Déclaration : Le contenu de cet article est issue du réseau, propriété des auteurs respectifs, le contenu est contribué et téléchargé par les utilisateurs d'Internet, ce site n'est pas propriétaire des droits d'auteur, n'a pas été traité par l'éditeur humain et n'assume aucune responsabilité juridique. Si vous trouvez du contenu suspect de violation de droits d'auteur, veuillez envoyer un e-mail à : notice#oldtoolbag.com (veuillez remplacer # par @ lors de l'envoi d'un e-mail pour signaler une violation, et fournir des preuves pertinentes. Une fois confirmée, ce site supprimera immédiatement le contenu suspect de violation de droits d'auteur.)