Explication détaillée du code source de la liste chaînée compressée Redis Ziplist

La liste compressée (ziplist) est une liste composée d'une série de blocs mémoire spécialement codés. Elle joue un rôle très important dans l'optimisation du stockage des données Redis. Cet article partage principalement avec vous la ziplist, une structure de données très utilisée dans Redis. . Il n'est pas exagéré de dire que cette structure de données est omniprésente dans Redis. En plus des listes chaînées, de nombreuses autres structures de données l'utilisent également pour la transition, comme le SortedSet mentionné dans l'article précédent. Pas grand chose à dire ci-dessous, jetons un œil à l’introduction détaillée.

1. Introduction à la structure de données compressée de la liste ziplist

Tout d’abord, examinons la structure de la ziplist dans son ensemble, comme indiqué ci-dessous :

Diagramme de structure de liste compressée de liste chaînée

On peut voir qu'il existe de nombreux champs et différentes tailles d'octets, mais c'est l'essence des listes chaînées compressées. Résumons-les un par un.

字段	含义
zlbytes	该字段是压缩链表的第一个字段，是无符号整型，占用4个字节。用于表示整个压缩链表占用的字节数（包括它自己）。
zltail	无符号整型，占用4个字节。用于存储从压缩链表头部到最后一个entry（不是尾元素zlend）的偏移量，在快速跳转到链表尾部的场景使用。
zllen	无符号整型，占用2个字节。用于存储压缩链表中包含的entry总数。
zlend	特殊的entry，用来表示压缩链表的末尾。占用一个字节，值恒为255。

Il est résumé comme le début et la fin de la liste zip, et le champ de saisie le plus important est résumé ci-dessous.

De manière générale, une entrée se compose de trois champs : prevlen, encoding et Entry-Data. Cependant, lorsque l'entrée est un petit entier, le champ Entry-Data sera omis en fonction de l'encodage. Ce qui suit est un résumé :

Le premier est le champ prevlen : indiquant la longueur de l'entrée précédente, il existe deux méthodes d'encodage.

• Lorsque la longueur est inférieure à 255 octets, elle est stockée sur un octet.

• 
  

• Lorsque la longueur est supérieure ou égale à 255, cinq octets sont utilisés pour le stockage et le premier octet sera défini sur 255, indiquant que la longueur de l'entrée précédente est représentée par les quatre octets suivants.

Ensuite il y a le champ encodage : il utilisera différentes méthodes d'encodage en fonction du contenu de l'élément courant, comme suit :

1. Si le contenu de l'élément est une chaîne, les valeurs d'encodage sont :

00xx xxxx : Commencer par 00 indique que la longueur de la chaîne est représentée par 6 bits.

01xx xxx |

1000 0000 |

2. Si le contenu de l'élément est un nombre, les valeurs d'encodage sont :

1100 0000 : Indique que le numéro occupe les 2 octets suivants.

1101 0000 : Indique que le numéro occupe les 4 octets suivants.

1110 0000 : Indique que le numéro occupe les 8 octets suivants.

1111 0000 : Indique que le numéro occupe les 3 octets suivants.

1111 1110 : Indique que le numéro occupe l'octet suivant.

1111 1111 : Indique le dernier élément de la liste chaînée compressée (encodage spécial).

1111 xxxx : Indique que seuls les 4 derniers chiffres sont utilisés pour représenter les entiers de 0 à 12. Puisque 0000, 1110 et 1111 sont déjà occupés, c'est-à-dire que les quatre chiffres de xxxx ici ne peuvent représenter que 0001 à 1101. Une fois convertis en décimal , ce sont les nombres de 1 à 13. Cependant, redis stipule qu'il est utilisé pour représenter 0 ~ 12, donc lorsque nous rencontrons cet encodage, nous devons retirer les quatre derniers chiffres et soustraire 1 pour obtenir la valeur correcte.

Enfin, il y a le champ saisie-données : si la valeur de l'élément est une chaîne, la valeur de l'élément lui-même est enregistrée. Si la valeur de l'élément est un très petit nombre (0 ~ 12 selon les règles de codage ci-dessus), un tel champ n'existe pas.

L'encodage des listes chaînées compressées est très compliqué, mais c'est aussi l'essence de cette structure de données. Jetons un coup d'œil à un exemple :

. Remarque : Cet exemple est mentionné dans le code source de Redis

//由元素2，5组成的压缩链表
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
 |  |  | | | |
 zlbytes zltail entries "2" "5" end
//字符串"Hello World"编码后的内容
[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

Ce qui précède est une liste chaînée compressée composée de deux éléments, 2 et 5, exprimés en hexadécimal.

• Tout d'abord, les quatre premiers octets représentent le nombre d'octets occupés par la liste zip entière. Étant donné que Redis utilise un stockage Little-Endian, 15 octets sont représentés par 0f 00 00 00.

• 
  

• Les 4 octets suivants représentent le décalage du dernier élément, qui est le décalage entre l'en-tête de la liste zip (zlbytes) et le dernier élément (remarque : pas le nœud de queue. Il est également stocké en petit endian, il est donc exprimé par 0c). 00 00 00.

• 
  

• Vient ensuite le champ zllen composé de deux octets qui représente le nombre d'éléments. Dans notre exemple, il y a deux éléments, plus un stockage petit-boutiste, il est donc exprimé par 02 00.

• 
  

• Vient ensuite l'élément lui-même. Premièrement, une fin de mot de longueur variable représente la longueur de l'élément précédent. 2 est le premier élément. La taille de l'élément précédent est 0, il occupe donc un octet de 00. Selon les règles d'encodage mentionnées ci-dessus, les éléments 2 et 5 appartiennent à des nombres compris entre 0 et 12, et vous devez utiliser 1111. Encodez au format xxxx, 2 est converti en binaire sous la forme 0010, plus 1 est 0011 (la raison de l'ajout de 1 est expliquée ci-dessus), l'élément combiné 2 est représenté par 00 f3. De même, l'élément 5 est représenté par 02 f6.

• 
  

• Le dernier élément est l'élément de queue, utilisant le code inoccupé 1111 1111, qui est 255.

Ensuite, nous insérons un élément de chaîne Hello à la fin de cette liste chaînée compressée World, regardez d'abord comment encoder la chaîne. Selon les règles d'encodage convenues, utilisez d'abord des octets pour représenter la longueur de l'élément précédent. L'élément précédent ici est 5, qui occupe un total de deux octets, utilisez donc d'abord un mot. La section représente la longueur de l'élément précédent, 02. Vient ensuite l'encodage de la chaîne. La longueur de la chaîne que nous voulons ajouter est de 11 (les espaces sont également comptés lorsqu'elle est convertie en binaire, elle est de 1011. Selon le). règles d'encodage de la chaîne, utilisez 0000 1011 signifie que lorsqu'il est converti en hexadécimal, il s'agit de 0b. Enfin, plus le code ASCII de notre chaîne elle-même, nous obtenons l'encodage de la chaîne : [02] [0b] [48 65. 6c 6c 6f 20 57 6f 72 6c 64].

À ce stade, l'intégralité de 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

2. Analyse du code source de la commande ziplist de liste chaînée compressée

Après avoir compris les règles de codage ci-dessus, examinons certains des codes sources d'opération de la liste chaînée compressée. Cet article résume les principes de base des listes chaînées compressées à travers les quatre opérations de création d'une liste chaînée compressée, d'insertion d'éléments et de suppression. éléments et recherche d'éléments.

La première est de créer :

//定义由zlbytes，zltail跟zllen组成的压缩链表的头大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//创建一个压缩链表，并且返回指向该链表的指针
unsigned char *ziplistNew(void) {
 //这里之所以+1是因为尾元素占用一个字节，这也是一个压缩链表最小尺寸
 unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
 //分配内存
 unsigned char *zl = zmalloc(bytes);
 //设置链表大小
 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
 //设置最后一个元素的偏移量
 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
 //设置元素个数
 ZIPLIST_LENGTH(zl) = 0;
 //设置尾元素（上面只是申请空间）
 zl[bytes-1] = ZIP_END;
 return zl;
}

La logique de création d'une liste chaînée compressée est très simple : elle consiste à demander un espace fixe contenant les nœuds de tête et de queue, puis à initialiser le contexte de la liste chaînée.

与创建相比，添加元素的源码就非常冗长了，为了便于理解，在看源码之前我们先自己梳理一下添加元素的逻辑。

• 首先我们要找到指定插入位置的前一个元素的大小，因为该属性是新元素的组成部分之一。

• 
  

• 然后我们要对当前元素进行编码来获得相应的encoding字段跟实际元素值的字段。

• 
  

• 新插入元素的后继元素的prevlen字段要更新，因为它前面的元素已经改变。这里可能引起级联更新（删除元素也有该问题），原因就是prevlen字段大小是可变的。

上面三步是核心步骤，其余的还有更新尾节点偏移量，修改链表元素个数等操作。当然，由于压缩链表是基于数组实现的，因此在插入或删除元素的时候内存拷贝也是必不可少的。

总结好上面的步骤以后，我们开始一步一步分析源码，比较长，慢慢看：

//四个参数依次是：压缩链表，插入位置（新元素插入p元素后面），元素值，元素长度
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
 //这里是保存当前链表的长度
 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. 这段逻辑目的就是获取前置元素的长度
 if (p[0] != ZIP_END) {
 //如果插入位置的元素不是尾元素,则获取该元素的长度
 //这里为了后面使用方便进行了拆分，prevlensize保存encoding字段的长度，prevlen保存元素本身的长度
 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
 } else {
 //如果插入位置的元素是尾元素，那么需要把新元素插入链表尾端
 //获取到链表最后一个元素（注：最后一个元素不等于尾元素）
 unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);

 if (ptail[0] != ZIP_END) {
  //如果最后一个元素不是尾元素，则该元素为新元素的前置元素，获取该元素长度
  prevlen = zipRawEntryLength(ptail);
 }
 //否则说明链表还没有任何元素，即新元素的前置元素长度为0
 }

 //2. 对新元素进行编码，获取新元素的总大小
 if (zipTryEncoding(s,slen,&value,&encoding)) {
 //如果是数字，则按数字进行编码
 reqlen = zipIntSize(encoding);
 } else {
 //元素长度即为字符串长度
 reqlen = slen;
 }
 //新元素总长度为值的长度加上前置元素跟encoding元素的长度
 reqlen += zipStorePrevEntryLength(NULL,prevlen);
 reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

 //如果插入的位置不是链表尾，则要对新元素的后续元素的prevlen字段进行判断
 //根据上面的编码规则，该字段可能需要扩容
 int forcelarge = 0;
 nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
 if (nextdiff == -4 && reqlen <p>
	分析完插入元素的逻辑，长舒一口气，真的很长，细节也很多。</p><p>
	接下来在再看下删除元素的过程，与添加相比，删除相对要简单一些，清空当前元素以后，需要把后继元素一个一个拷贝上来（这也是数组跟链表两个数据结构的差别），然后注意是否需要级联更新，上代码：</p><pre class="brush:php;toolbar:false">//参数依次为：压缩链表，删除元素的其实位置，删除元素的个数
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;
 //读取p指向的元素保存在first中
 zipEntry(p, &first);
 for (i = 0; p[0] != ZIP_END && i  0) {
  if (p[0] != ZIP_END) {
   //判断元素大小是否有改变
   nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
   //修改删除元素之后的元素的prevlen字段
   p -= nextdiff;
   zipStorePrevEntryLength(p,first.prevrawlen);
   //更新末尾元素的偏移量
   ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
   //当删除元素的后继元素不止有一个时，新的末尾元素偏移量需要加上nextdiff
   zipEntry(p, &tail);
   if (p[tail.headersize+tail.len] != ZIP_END) {
    ZIPLIST_TAIL_OFFSET(zl) =
     intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
   }
   //把后面剩余的元素移动至前面
   memmove(first.p,p,
    intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
  } else {
   //直接删除到链表末尾，因此不需要内存拷贝，只需修改最后一个元素的偏移量
   ZIPLIST_TAIL_OFFSET(zl) =
    intrev32ifbe((first.p-zl)-first.prevrawlen);
  }
  //resize数组大小
  offset = first.p-zl;
  zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
  //修改链表元素个数
  ZIPLIST_INCR_LENGTH(zl,-deleted);
  p = zl+offset;
  //nextdiff != 0表示元素大小发生变化，需要进行级联更新
  if (nextdiff != 0)
   zl = __ziplistCascadeUpdate(zl,p);
 }
 return zl;
}

最后我们看下元素的查找操作：

//参数依次为：压缩链表，要查找元素的值，要查找元素的长度，每次比较之间跳过的元素个数
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;
 //只要还没到尾元素就不断循环
 while (p[0] != ZIP_END) {
  unsigned int prevlensize, encoding, lensize, len;
  unsigned char *q;
  //查询链表当前元素的prevlen字段
  ZIP_DECODE_PREVLENSIZE(p, prevlensize);
  //查询链表当前元素的encoding字段
  ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
  q = p + prevlensize + lensize;
  //已到达需要比较的元素位置
  if (skipcnt == 0) {
   //如果链表中的当前元素时字符串
   if (ZIP_IS_STR(encoding)) {
    //跟要查找的字符串进行比较
    if (len == vlen && memcmp(q, vstr, vlen) == 0) {
     //匹配成功，则要查找元素的指针
     return p;
    }
   } else {
    //如果当前元素为数字且vencoding为0
    if (vencoding == 0) {
     //尝试对要查找的值进行数字编码
     if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
      //如果编码失败，则说明要查找的元素根本不是数字
      //然后把vencoding设置为最大值，起一个标记作用
      //也就是说后面就不用尝试把要查找的值编码成数字了
      vencoding = UCHAR_MAX;
     }
     assert(vencoding);
    }
    //如果vencoding != UCHAR_MAX，则说明要查找的元素成功编码为数字
    if (vencoding != UCHAR_MAX) {
     //按数字取出当前链表中的元素
     long long ll = zipLoadInteger(q, encoding);
     if (ll == vll) {
      //如果两个数字相等，则返回元素指针
      return p;
     }
    }
   }
   //重置需要跳过的元素个数
   skipcnt = skip;
  } else {
   //跳过元素
   skipcnt--;
  }
  //遍历下个元素
  p = q + len;
 }
 //遍历完整个链表，没有找到元素
 return NULL;
}

到这里就把压缩链表的创建，添加，删除，查找四个基本操作原理总结完了。

三、压缩链表ziplist数据结构总结

压缩链表ziplist在redis中的应用非常广泛，它算是redis中最具特色的数据结构了。该数据结构的精髓其实就在于文章第一部分总结的编码规则，先理清楚这部分内容，后面的源码可以简单看下加深理解。

不得不说源码部分着实有点冗长，确实需要耐心，我自己在读的过程中也很头大。如果对源码感兴趣的话，建议按我的方法，先自己梳理某个操作（例如上面提到的插入元素）需要做哪些事情，然后再看代码可能会更好理解一些。

相关推荐：

深入剖析 redis 数据结构 ziplist

Redis源码分析（六）---ziplist压缩列表

Redis内部数据结构详解之ziplist

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!