Detaillierte Erläuterung des Quellcodes der komprimierten Redis-Ziplist für verknüpfte Listen

Die komprimierte Liste (Ziplist) ist eine Liste, die aus einer Reihe speziell codierter Speicherblöcke besteht. Sie spielt eine sehr wichtige Rolle bei der Optimierung der Redis-Datenspeicherung. In diesem Artikel wird hauptsächlich die komprimierte verknüpfte Listen-Ziplist vorgestellt, eine häufig verwendete Datenstruktur in redis. Es ist keine Übertreibung zu sagen, dass diese Datenstruktur in Redis allgegenwärtig ist. Zusätzlich zu verknüpften Listen wird sie auch von vielen anderen Datenstrukturen für den Übergang verwendet, wie beispielsweise dem im vorherigen Artikel erwähnten SortedSet. Im Folgenden gibt es nicht viel zu sagen. Werfen wir einen Blick auf die ausführliche Einführung.

1. Einführung in die Ziplist-Datenstruktur komprimierter verknüpfter Listen

Schauen wir uns zunächst die Struktur der Ziplist als Ganzes an, wie unten dargestellt:

Komprimiertes Ziplist-Strukturdiagramm für verknüpfte Listen

Es ist ersichtlich, dass es viele Felder und unterschiedliche Bytegrößen gibt, aber das ist das Wesentliche der komprimierten verknüpften Liste. Fassen wir sie einzeln zusammen.

Es wird als Kopf und Ende der Ziplist zusammengefasst, und das wichtigste Eingabefeld ist unten zusammengefasst.

Im Allgemeinen besteht ein Eintrag aus drei Feldern: „prevlen“, „coding“ und „entry-data“. Wenn es sich bei dem Eintrag jedoch um eine kleine Ganzzahl handelt, wird das Feld „entry-data“ aufgrund der Codierung weggelassen. Das Folgende ist eine Zusammenfassung:

Das erste ist das Feld prevlen: Es gibt die Länge des vorherigen Eintrags an. Es gibt zwei Kodierungsmethoden.

• Wenn die Länge weniger als 255 Byte beträgt, wird sie in einem Byte gespeichert.

• 
  

• Wenn die Länge größer oder gleich 255 ist, werden fünf Bytes zum Speichern verwendet, und das erste Byte wird auf 255 gesetzt, was angibt, dass die Länge des vorherigen Eintrags durch die folgenden vier Bytes dargestellt wird.

Dann gibt es noch die Feldkodierung: Abhängig vom Inhalt des aktuellen Elements werden unterschiedliche Kodierungsmethoden verwendet, wie folgt:

1. Wenn der Elementinhalt eine Zeichenfolge ist, lauten die Kodierungswerte:

00xx xxxx: Beginnend mit 00 gibt an, dass die Länge der Zeichenfolge durch 6 Bits dargestellt wird.

01xx xxxx |

1000 0000 |. xxxx xxxx |. xxxx xxxx |

2. Wenn der Elementinhalt eine Zahl ist, lauten die Kodierungswerte:

1100 0000: Zeigt an, dass die Zahl die nächsten 2 Bytes belegt.

1101 0000: Zeigt an, dass die Zahl die nächsten 4 Bytes belegt.

1110 0000: Zeigt an, dass die Zahl die nächsten 8 Bytes belegt.

1111 0000: Zeigt an, dass die Zahl die nächsten 3 Bytes belegt.

1111 1110: Zeigt an, dass die Zahl das nächste Byte belegt.

1111 1111: Gibt das letzte Element in der komprimierten verknüpften Liste an (spezielle Codierung).

1111 xxxx : Zeigt an, dass nur die letzten 4 Ziffern zur Darstellung von Ganzzahlen von 0 bis 12 verwendet werden. Da 0000, 1110 und 1111 bereits belegt sind, können die vier Ziffern von xxxx hier nur 0001 bis 1101 darstellen. Bei Konvertierung in Dezimalzahlen Dies sind die Zahlen 1 bis 13. Redis legt jedoch fest, dass es zur Darstellung von 0 bis 12 verwendet wird. Wenn wir also auf diese Codierung stoßen, müssen wir die letzten vier Ziffern herausnehmen und 1 subtrahieren, um den korrekten Wert zu erhalten.

Schließlich gibt es noch das Feld „entry-data“: Wenn der Wert des Elements ein String ist, wird der Wert des Elements selbst gespeichert. Wenn der Wert des Elements eine sehr kleine Zahl ist (0 bis 12 gemäß den oben genannten Codierungsregeln), gibt es kein solches Feld.

Die Kodierung komprimierter verknüpfter Listen ist sehr kompliziert, aber das ist auch die Essenz dieser Datenstruktur. Schauen wir uns ein Beispiel an:

Hinweis: Dieses Beispiel wird im Redis-Quellcode

//由元素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]

erwähnt Das Obige ist eine komprimierte verknüpfte Liste, die aus zwei Elementen besteht, 2 und 5, ausgedrückt in Hexadezimalzahl.

• Erstens stellen die ersten vier Bytes die Anzahl der von der gesamten Ziplist belegten Bytes dar. Da Redis Little-Endian-Speicher verwendet, werden 15 Bytes als 0f 00 00 00 dargestellt.

• 
  

• Die nächsten 4 Bytes stellen den Offset des letzten Elements dar, also den Offset vom Ziplist-Header (zlbytes) zum letzten Element (Hinweis: nicht zum Endknoten). Er wird ebenfalls in Little Endian gespeichert und wird daher als 0c ausgedrückt 00 00 00.

• 
  

• Als nächstes folgt das Zllen-Feld, das aus zwei Bytes besteht und die Anzahl der Elemente darstellt. In unserem Beispiel gibt es zwei Elemente plus Little-Endian-Speicher, daher wird es als 02 00 ausgedrückt.

• 
  

• Als nächstes steht das Element selbst. Das Ende eines Wortes mit variabler Länge stellt die Länge des vorherigen Elements dar. Die Größe des vorherigen Elements beträgt also 0. Gemäß den oben genannten Kodierungsregeln gehören die Elemente 2 und 5 zu Zahlen zwischen 0 und 12, und Sie müssen 1111 verwenden Im xxxx-Format kodieren, 2 wird als 0010 in Binär umgewandelt, plus 1 ist 0011 (der Grund für das Hinzufügen von 1 wird oben erklärt), das kombinierte Element 2 wird als 00 dargestellt f3. Ebenso wird Element 5 als 02 f6 dargestellt.

• 
  

• Das letzte ist das Schwanzelement mit dem unbesetzten Code 1111, 1111 oder 255.

Als nächstes fügen wir am Ende dieser komprimierten verknüpften Liste ein Zeichenfolgenelement „Hello“ ein Schauen Sie sich zunächst an, wie die Zeichenfolge gemäß den vereinbarten Codierungsregeln codiert wird. Verwenden Sie zunächst Bytes, um die Länge des vorherigen Elements darzustellen. Das vorherige Element belegt hier insgesamt zwei Bytes Der Abschnitt stellt die Länge des vorherigen Elements dar, 02. Als nächstes folgt die Codierung der Zeichenfolge, die wir hinzufügen möchten, 11 (Leerzeichen werden ebenfalls gezählt, also 1011). Codierungsregeln für die Zeichenfolge verwenden Sie 0000 1011 bedeutet, dass es bei der Konvertierung in Hexadezimalzahl 0b ist. Zusammen mit dem ASCII-Code unseres Strings selbst erhalten wir schließlich die Codierung des Strings: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64].

Zu diesem Zeitpunkt lautet die gesamte komprimierte verknüpfte Liste:

[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 des Quellcodes des Ziplist-Befehls für komprimierte verknüpfte Listen

Nachdem wir die oben genannten Codierungsregeln verstanden haben, werfen wir einen Blick auf einige Operationsquellcodes der komprimierten verknüpften Liste ziplist. Dieser Artikel fasst die Grundprinzipien komprimierter verknüpfter Listen anhand der vier Vorgänge zusammen: Erstellen einer komprimierten verknüpften Liste, Einfügen von Elementen und Löschen Elemente und Suche nach Elementen.

Die erste besteht darin, Folgendes zu erstellen:

//定义由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;
}

Die Logik zum Erstellen einer komprimierten verknüpften Liste ist sehr einfach. Sie besteht darin, einen festen Raum zu beantragen, der die Kopf- und Endknoten enthält, und dann den Kontext der verknüpften Liste zu initialisieren.

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

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

• 
  

• 然后我们要对当前元素进行编码来获得相应的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

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung des Quellcodes der komprimierten Redis-Ziplist für verknüpfte Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!