English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Prefazione
La lista compressa (ziplist) è costituita da una serie di blocchi di memoria codificati specialmente e gioca un ruolo molto importante nell'ottimizzazione dello storage dei dati di Redis. Questo articolo riassume una struttura dati molto utilizzata in Redis, la lista compressa ziplist. Questa struttura dati è onnipresente in Redis, non è un'esagerazione, oltre alla lista, molte altre strutture dati la utilizzano come transizione, come la SortedSet menzionata nell'articolo precedente. Non c'è molto da dire, diamo un'occhiata all'introduzione dettagliata.
Introduzione alla struttura dati della lista compressa ziplist
Prima di tutto, diamo un'occhiata alla struttura della ziplist, come nell'immagine seguente:
Diagramma della struttura della ziplist compressa
Si può vedere che ci sono molti campi e le dimensioni dei byte sono diverse, ma questo è proprio il nucleo della lista compressa. Riassumiamo in ordine.
| Campo | Significato |
|---|---|
| zlbytes | Questo campo è il primo campo della lista compressa, è un intero unsigned e occupa 4 byte. Utilizzato per rappresentare il numero di byte occupati dalla lista compressa nel suo complesso (inclusi i suoi stessi byte). |
| zltail | Intero unsigned, che occupa 4 byte. Utilizzato per memorizzare l'offset dalla testa della lista compressa all'ultimo entry (non l'elemento di coda zlend), utile in scenari di transizione rapida alla fine della lista. |
| zllen | Intero unsigned, che occupa 2 byte. Utilizzato per memorizzare il numero totale di entry contenute nella lista compressa. |
| zlend | Un entry speciale utilizzato per rappresentare la fine della lista compressa. Occupa un byte e il valore è sempre 255. |
Riassumiamo la testa e la coda della ziplist, e ora riassumiamo il campo entry, che è di fondamentale importanza.
Di solito, un entry è composto dai campi prevlen, encoding ed entry-data, ma quando l'entry è un piccolo intero, il campo entry-data viene omesso in base alla codifica. Di seguito, riassumiamo in ordine:
Firstly, the field prevlen: it indicates the length of the previous entry and has two encoding methods.
Then there is the field encoding: it will use different encoding methods according to the different content of the current element, as follows:
1. If the content of the element is a string, the encoding values are as follows:
00xx xxxx : the 00 starting indicates that the length of the string is represented by 6 bits.
01xx xxxx | xxxx xxxx : the 01 starting indicates that the length of the string is represented by 14 bits, and these 14 bits are stored in big-endian format.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx : the 10 starting indicates that the next four bytes are the string length, and these 32 bits are stored in big-endian format.
2. If the content of the element is a number, the encoding values are as follows:
1100 0000: it means the number occupies the next 2 bytes.
1101 0000: it means the number occupies the next 4 bytes.
1110 0000: it means the number occupies the next 8 bytes.
1111 0000 : it means the number occupies the next 3 bytes.
1111 1110 : it means the number occupies the next 1 byte.
1111 1111 : it means the last element in the compressed linked list (special encoding).
1111 xxxx : it means that only the last 4 bits are used to represent the integer 0~12, since 0000, 1110 and 1111 are already occupied, it means that the four bits of xxxx can only represent 0001~1101, which is the decimal number 1~13, but Redis specifies that it is used to represent 0~12, so when this encoding is encountered, we need to take the last four bits and subtract 1 to get the correct value.
Finally, the field entry-data: if the value of the element is a string, then save the value of the element itself. If the value of the element is a very small number (i.e., 0~12 according to the above encoding rules), then there is no such field.
The encoding of the compressed linked list is very complex, but this is also the essence of this data structure. Let's take a look at an example together:
Note:This example is mentioned in the Redis source code
// Compressed linked list composed of elements 2, 5 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end //Il contenuto codificato della stringa "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
Quello sopra è una parte della lista compressa composta da due elementi 2, 5 rappresentati in esadecimale.
Quindi, aggiungiamo un elemento di stringa "Hello World" alla fine di questa lista compressa, vediamo prima come codificare questa stringa, secondo le regole di codifica convenzionali, è necessario rappresentare la lunghezza dell'elemento precedente in byte, qui l'elemento precedente è 5, che occupa in totale due byte, quindi si utilizza un byte per rappresentare la lunghezza dell'elemento precedente 02, seguita dalla codifica della stringa, la lunghezza della stringa da aggiungere è 11 (spazio incluso), convertita in binario è 1011, secondo le regole di codifica della stringa, si utilizza 0000 1011 per rappresentarla, convertita in esadecimale è 0b, infine si aggiunge l'ASCII dell'intera stringa, combinando tutto si ottiene la codifica della stringa: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64].
In questo momento l'intera lista compressa diventa:
[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
Secondo, analisi del codice delle comandi della lista compressa ziplist
Dopo aver chiarito le regole di codifica sopra, guardiamo le parti di codice delle operazioni sulla lista compressa ziplist, in questo articolo, riassumiamo i principi fondamentali della lista compressa attraverso le operazioni di creazione, inserimento, rimozione e ricerca degli elementi.
Prima di tutto è la creazione:
//Definire la dimensione dell'intestazione della lista compressa composta da zlbytes, zltail e zllen
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//Creare una lista compressa e restituire il puntatore alla lista
unsigned char *ziplistNew(void) {
//Il motivo per cui +1 è che l'elemento finale occupa un byte, che è anche la dimensione minima di una lista compressa
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//Assegnare memoria
unsigned char *zl = zmalloc(bytes);
//Impostare la dimensione della lista
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//Impostare l'offset dell'ultimo elemento
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//Impostare il numero di elementi
ZIPLIST_LENGTH(zl) = 0;
//Impostare l'elemento finale (sopra è stato richiesto lo spazio)
zl[bytes-1] = ZIP_END;
return zl;
}
La logica per creare una lista compressa è molto semplice, ovvero richiedere uno spazio fisso che contiene i nodi di testa e di coda, quindi inizializzare il contesto della lista.
In confronto con la creazione, il codice per aggiungere elementi è molto più lungo, per facilitare la comprensione, prima di guardare il codice, prima di tutto dobbiamo chiarire la logica di aggiunta degli elementi.
Questi tre passaggi sono le operazioni fondamentali, tra cui anche aggiornare l'offset del nodo finale, modificare il numero di elementi della lista, ecc. Certo, poiché la lista compressa è implementata su array, durante l'inserimento o la rimozione degli elementi, la copia in memoria è assolutamente necessaria.
Dopo aver organizzato i passaggi sopra menzionati, iniziamo a analizzare passo per passo il codice sorgente, è lungo, guardiamolo lentamente:
//四个参数依次是：压缩链表，插入位置（新元素插入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;
}
//La lunghezza totale dell'elemento nuovo è la lunghezza del valore più la lunghezza dell'elemento precedente e della lunghezza dell'elemento encoding
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//Se la posizione di inserimento non è alla fine della lista, deve essere valutato il campo prevlen degli elementi successivi del nuovo elemento
//Secondo le regole di codifica menzionate sopra, questo campo potrebbe richiedere una capacità espansa
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
//Espandere la capacità in base alla nuova dimensione del array calcolata, poiché l'indirizzo del nuovo array potrebbe cambiare, quindi registrare l'offset precedente
offset = p - zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//Calcolare la posizione di inserimento sul nuovo array
p = zl+offset;
//Se l'elemento inserito non è alla fine della lista
if (p[0] != ZIP_END) {
//Copia l'elemento successivo del nuovo elemento nel nuovo array, -1 per l'elemento finale
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//Il campo prevlen del successore del nuovo elemento
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//Aggiornare l'offset dell'ultimo elemento
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//Quando l'elemento successivo del nuovo elemento non ha più di uno, l'offset finale del nuovo elemento deve essere aggiunto 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 {
//Nuovo elemento inserito alla fine della coda della lista, aggiornare l'offset finale
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0表示后继元素的长度发生变化，因此我们需要级联更新后继元素的后继元素
if (nextdiff != 0) {
offset = p - zl;
zl = __ziplistCascadeUpdate(zl, p + reqlen);
p = zl+offset;
}
//把新元素写入链表
p += zipStorePrevEntryLength(p, prevlen);
p += zipStoreEntryEncoding(p, encoding, slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p, s, slen);
} else {
zipSaveInteger(p, value, encoding);
}
//压缩链表存储元素数量+1
ZIPLIST_INCR_LENGTH(zl, 1);
return zl;
}
分析完插入元素的逻辑，长舒一口气，真的很长，细节也很多。
接下来再看下删除元素的过程，与添加相比，删除相对要简单一些，清空当前元素以后，需要把后继元素一个一个拷贝上来（这也是数组跟链表两个数据结构的差别），然后注意是否需要级联更新，上代码：
//参数依次为：压缩链表，删除元素的起始位置，删除元素的个数
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 < num; i++) {
//统计总共删除的长度
p += zipRawEntryLength(p);
//统计实际删除元素的个数
deleted++;
}
//需要删除元素的字节数
totlen = p - first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//判断元素大小是否有改变
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//Modifica il campo prevlen degli elementi dopo l'elemento eliminato
p -= nextdiff;
zipStorePrevEntryLength(p,first.prevrawlen);
//Aggiorna l'offset dell'elemento finale
ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//Quando l'elemento da eliminare ha più di un elemento successivo, l'offset dell'elemento finale nuovo deve essere aggiunto nextdiff
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//Sposta gli elementi rimanenti dietro
memmove(first.p,p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
} else {
//Elimina direttamente alla fine della lista, quindi non è necessario copiare la memoria, è sufficiente modificare l'offset dell'ultimo elemento
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//Modifica la dimensione dell'array
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//Modifica il numero di elementi della lista
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0 indica che la dimensione dell'elemento è cambiata e è necessaria una aggiornamento cascata
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl,p);
}
return zl;
}
Vediamo ora l'operazione di ricerca dell'elemento:
//Parametri in ordine: ziplist, valore dell'elemento da cercare, lunghezza dell'elemento da cercare, numero di elementi saltati tra le comparazioni
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#oldtoolbag.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。