English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Einführung
Die komprimierte Liste (ziplist) besteht aus einer Reihe speziell codierter Speicherblöcke und spielt eine sehr wichtige Rolle bei der Datenstoredoptimierung von Redis. In diesem Artikel werde ich eine der häufig verwendeten Datenstrukturen in Redis, die komprimierte Liste ziplist, zusammenfassen. Diese Datenstruktur ist in Redis überall präsent, was nicht übertreiben ist, außer der Liste, viele andere Datenstrukturen verwenden sie auch als Übergang, wie die im vorliegenden Artikel erwähnte SortedSet. Viel reden ist nicht mehr notwendig, lasst uns gemeinsam einen detaillierten Überblick darüber geben.
1. Kurze Einführung in die Datenstruktur der komprimierten Liste ziplist
Zunächst betrachten wir die Struktur der ziplist im Ganzen, wie im folgenden Bild gezeigt:
Strukturdiagramm der komprimierten Liste ziplist
Es ist erkennbar, dass viele Felder vorhanden sind und die Größen der Bytes unterschiedlich sind, aber das ist auch der Kern der komprimierten Liste. Wir fassen dies nacheinander zusammen.
| Feld | Bedeutung |
|---|---|
| zlbytes | Dieses Feld ist der erste Feld der komprimierten Liste und ist ein unsignierter Integer, der4Bytes. Verwendet zur Angabe der Anzahl der Bytes, die die gesamte komprimierte Liste belegt (einschließlich ihrer selbst). |
| zltail | Unsignierte Integer, die4Bytes belegen. Verwendet zur Speicherung des Offset von der Kopfenden der komprimierten Liste bis zum letzten entry (nicht dem Elements zlend) für den schnellen Sprung zum Ende der Liste. |
| zllen | Unsignierte Integer, die2Bytes. Verwendet zur Speicherung der Anzahl der enthaltenen entrys in der komprimierten Liste. |
| zlend | Besondere entrys, die zur Darstellung des Endes der komprimierten Liste verwendet werden. Sie belegen einen Byte und den Wert255。 |
Zusammengefasst: Kopf und Ende des ziplist, ferner eine Zusammenfassung des wichtigsten Felds entry.
In der Regel besteht ein entry aus prevlen, encoding und entry-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-data字段。下面依次进行总结：
drei Felder data bestehen, aber wenn der entry eine sehr kleine Ganzzahl ist, wird er nach der Kodierung weggelassen.
dann wird mit fünf Bytes gespeichert, wobei der erste Byte auf
1、wenn der Inhalt des Elements eine Zeichenkette ist, die Werte von encoding sind:
00xx xxxx ：00 beginnt mit der Angabe, dass die Länge der Zeichenkette mit6Bits dargestellt wird.
01xx xxxx | xxxx xxxx ：01Der Anfang zeigt an, dass die Länge der Zeichenkette durch14Bits darstellen, das14Bits verwenden großen Endian Speicherung.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10Der Anfang zeigt an, dass die nächsten vier Bytes die Länge der Zeichenkette sind, das32Bits verwenden großen Endian Speicherung.
2、wenn der Inhalt des Elements eine Zahl ist, die Werte von encoding sind:
1100 0000：stellt die Anzahl der Bytes, die von der Nummer belegt werden, dahinter2Bytes.
1101 0000：stellt die Anzahl der Bytes, die von der Nummer belegt werden, dahinter4Bytes.
1110 0000：stellt die Anzahl der Bytes, die von der Nummer belegt werden, dahinter8Bytes.
1111 0000 ：stellt die Anzahl der Bytes, die von der Nummer belegt werden, dahinter3Bytes.
1111 1110 ：stellt die Anzahl der Bytes, die von der Nummer belegt werden, dahinter1Bytes.
1111 1111 ：stellt den letzten Element der komprimierten Liste (spezielle Kodierung) dar.
1111 xxxx ：stellt nur die letzten4stellen darstellen 0~12von Ganzzahlen, da 0000,1110und1111Drei sind bereits belegt, das bedeutet, dass die vier Stellen xxxx hier nur 000 darstellen können1~1101zu darstellen, in Dezimalzahl ist dies die Zahl1~13，aber Redis bestimmt, dass es verwendet wird, um 0~12，daher müssen wir, wenn wir auf diese Kodierung stoßen, die letzten vier Stellen abziehen und1um den richtigen Wert zu erhalten.
Schließlich ist das Feld entry-data：Wenn der Wert des Elements eine Zeichenkette ist, wird der Wert des Elements selbst gespeichert. Wenn der Wert des Elements sehr kleine Zahlen sind (gemäß den obigen Kodierungsregeln sind dies 0~12），dann gibt es kein solches Feld.
Die Kodierung der komprimierten Liste ist sehr komplex, aber das ist auch der Kern dieser Datenstruktur, sehen wir uns ein Beispiel an:
Anmerkung:Dieser Beispiel ist im Redis-Quellcode erwähnt
//bestehend aus Elementen2,5bestehend aus einer komprimierten Liste [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end //Der Inhalt der nach dem Kodieren der Zeichenkette "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
Oben ist ein Abschnitt, der in Hexadezimal dargestellt wird2,5eine Komprimierte Liste aus zwei Elementen.
Fügen wir am Ende der komprimierten Liste einen String-Element "Hello World" hinzu. Schauen wir uns zunächst an, wie der String kodiert wird. Gemäß den vereinbarten Kodierungsregeln müssen wir zunächst ein Byte zur Angabe der Länge des vorherigen Elements verwenden. Hier ist das vorherige Element5，insgesamt zwei Bytes belegt, daher wird zunächst ein Byte zur Angabe der Länge des vorherigen Elements 0 verwendet2，nächste ist die Kodierung des Strings. Wir müssen die Länge des Strings hinzufügen, die wir hinzufügen möchten11（Leerzeichen sind auch enthalten），in Binär ist das1011，gemäß den Kodierungsregeln des Strings, verwenden wir 0000 1011Das bedeutet, in Hexadezimal ist es 0b, und schließlich fügen wir den ASCII-Code unseres Strings hinzu. Insgesamt ergibt sich die Kodierung des Strings: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。
Dadurch wird die gesamte komprimierte Liste zu:
[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
Zwei: Analyse des Quellcodes der Befehle der komprimierten Liste ziplist
Nachdem wir die obigen Kodierungsregeln verstanden haben, schauen wir uns die Quellcodes für einige Operationen der komprimierten Liste ziplist an. In diesem Artikel werden wir die grundlegenden Prinzipien der komprimierten Liste anhand der vier Operationen Erstellen, Element hinzufügen, Element löschen und Element suchen zusammenfassen.
Zunächst das Erstellen:
//Definieren Sie die Größe des Headers einer komprimierten Liste, die aus zlbytes, zltail und zllen besteht
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//Erstellen Sie eine komprimierte Liste und geben Sie den Zeiger auf diese Liste zurück
unsigned char *ziplistNew(void) {
//Hier liegt der Grund+1weil der Fußknoten einen Byte belegt, das ist auch die minimale Größe einer komprimierten Liste
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//Speicher zuweisen
unsigned char *zl = zmalloc(bytes);
//Die Größe der Liste einstellen
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//Den Offset des letzten Elements einstellen
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//Die Anzahl der Elemente einstellen
ZIPLIST_LENGTH(zl) = 0;
//Den letzten Knoten einstellen (das war nur der Raum, der angefordert wurde)
zl[bytes-1] = ZIP_END;
return zl;
}
Die Logik zum Erstellen einer komprimierten Liste ist sehr einfach, es geht darum, einen festen Raum für den Kopf- und Fußknoten anzufordern und die Listenkontexte zu initialisieren.
Im Vergleich zum Erstellen ist der Quellcode zum Hinzufügen von Elementen sehr lang, um das Verständnis zu erleichtern, schauen wir uns die Logik des Hinzufügens von Elementen vor dem Betrachten des Quellcodes selbst durch.
Diese drei Schritte sind die Kernschritte,其余的还有更新尾节点偏移量，修改链表元素个数等操作。Natürlich, da die komprimierte Liste auf einem Array basiert, ist eine Speicherkopie unvermeidlich, wenn Elemente eingefügt oder entfernt werden.
Nachdem die obigen Schritte zusammengefasst sind, beginnen wir mit einer schrittweisen Analyse des Quellcodes, was ziemlich lang ist, also schauen wir uns das langsam an:
//Die vier Parameter sind in dieser Reihenfolge: komprimierte Liste, Einfügeposition (neues Element wird hinter dem Element p eingefügt), Wert des Elements, Länge des Elements
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//Hier wird die Länge der aktuellen Liste gespeichert
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. Das Ziel dieser Logik ist es, die Länge der vorderen Elemente zu ermitteln
if (p[0] != ZIP_END) {
//Wenn der Elemente an der Einfügeposition nicht der letzte Element ist, wird die Länge des Elements abgerufen
//这里为了后面使用方便进行了拆分，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) &63; zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {}}
nextdiff = 0;
forcelarge = 1;
}
//按照新计算出的数组大小进行扩容，由于新数组的地址可能会改变，因此这里记录旧的偏移量
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//在新数组上计算插入位置
p = zl+offset;
//如果新插入的元素不在链表末尾
if (p[0] != ZIP_END) {
//将新元素及其后续元素复制到新的数组中，-1用于尾元素
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//Das prevlen-Feld des nachfolgenden Elements des neuen Elements
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//Aktualisieren Sie den Offset des letzten Elements
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//Wenn das nächste Element des neuen Elements nicht nur ein Element hat, muss der neue Offset des Endelements um nextdiff hinzugefügt werden
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 {
//Neues Element am Ende der Liste einfügen, aktualisieren Sie den Offset am Ende
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0 bedeutet, dass die Länge der nachfolgenden Elemente geändert wurde, daher müssen wir die nachfolgenden Elemente der nachfolgenden Elemente kaskadiert aktualisieren
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//Neues Element in die Liste einfügen
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
//Komprimierte Zeilenliste speichert Anzahl der Elemente+1
ZIPLIST_INCR_LENGTH(zl,1;
return zl;
}
Nach der Analyse der Logik des Einfügens atmen wir tief durch, es war wirklich lang und es gibt viele Details.
Jetzt schauen wir uns den Prozess der Löschung von Elementen an, im Vergleich zum Hinzufügen ist das Löschen relativ einfach, nach dem das aktuelle Element geleert wird, müssen die nachfolgenden Elemente nacheinander kopiert werden (das ist auch der Unterschied zwischen Array und Zeilenliste als Datenstrukturen), und dann darauf achten, ob eine Kaskadenummerung erforderlich ist, hier der Code:
//Die Parameter sind in der Reihenfolge: Komprimierte Zeilenliste, Anfangsposition des zu löschenden Elements, Anzahl der zu löschenden Elemente
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;
//Lesen Sie das von p Zeiger referenzierte Element und speichern Sie es in first
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {}}
//Zähle die gesamte gelöschte Länge
p += zipRawEntryLength(p);
//Zähle die Anzahl der tatsächlich gelöschten Elemente
deleted++;
}
//Anzahl der Bytes, die gelöscht werden müssen
totlen = p-first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//Überprüfen Sie, ob die Größe des Elements geändert wurde
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//Ändern Sie das prevlen-Feld des Elements nach dem gelöschten Element
p -= nextdiff;
zipStorePrevEntryLength(p, first.prevrawlen);
//Aktualisieren Sie den Offset des Endelements
ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//Wenn das Nachfolger-Element des gelöschten Elements nicht nur ein Element ist, muss der Offset des neuen Endelements um nextdiff erhöht werden
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//Bewegen Sie die verbleibenden Elemente nach vorne
memmove(first.p, p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1;
} else {
//Löschen Sie direkt bis zum Ende der Liste, daher ist keine Speicherkopie erforderlich, nur die Offset des letzten Elements muss geändert werden
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//Größe der Array-Größe anpassen
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//Ändern Sie die Anzahl der Elemente in der Liste
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0 bedeutet, dass die Größe des Elements geändert wurde und eine Kaskadener更新 erforderlich ist
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl, p);
}
return zl;
}
Schauen wir uns nun das Suchen von Elementen an:
//Die Parameter sind in der folgenden Reihenfolge: Komprimierte Liste, Wert des zu suchenden Elements, Länge des zu suchenden Elements, Anzahl der Elemente, die zwischen den Vergleichen übersprungen werden
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 对内存利用率如此之高，那为什么还要提供普通的链表结构供用户使用呢？
这个问题没有标准答案，仁者见仁，智者见智。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或工作具有一定的参考价值。如果有疑问，大家可以留言交流，感谢大家对呐喊教程的支持。
声明：本文内容来自网络，版权归原作者所有。内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：notice#example.com。3codebox.com（在发邮件时，请将#更换为@）进行举报，并提供相关证据。一经查实，本站将立即删除涉嫌侵权内容。