English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Prólogo
La lista comprimida (ziplist) está compuesta por una serie de bloques de memoria codificados de manera especial, lo que tiene un papel muy importante en la optimización de almacenamiento de datos de Redis. Este artículo resume uno de los datos estructurales más utilizados en Redis, la lista enlazada comprimida ziplist. Dicho sea de paso, no es exagerado decir que esta estructura de datos está en todas partes en Redis, además de la lista, muchas otras estructuras de datos también la utilizan como transición, como se mencionó en el artículo anterior, SortedSet. Sin más preámbulos, veamos una introducción detallada.
I. Introducción a la estructura de datos de lista enlazada comprimida ziplist
Primero, observemos la estructura general de ziplist, como se muestra en la siguiente imagen:
Esquema de estructura de ziplist
Se puede ver que hay muchos campos y diferentes tamaños de bytes, pero esto es esencialmente la esencia de la lista enlazada comprimida, resumamos en sucesión.
| campo | significado |
|---|---|
| zlbytes | Este campo es el primer campo de la lista enlazada comprimida, es un entero sin signo, ocupa4bytes. Se utiliza para representar el número total de bytes ocupados por la lista enlazada comprimida (incluso a sí misma). |
| zltail | Entero sin signo, ocupa4bytes. Se utiliza para almacenar la cantidad de desplazamiento desde la cabeza de la lista enlazada comprimida hasta el último entry (no el elemento final zlend), utilizado en escenarios de saltos rápidos al final de la lista. |
| zllen | Entero sin signo, ocupa2bytes. Se utiliza para almacenar el número total de entry que contiene la lista enlazada comprimida. |
| zlend | Entry especial utilizado para representar el final de la lista enlazada comprimida. Ocupa un byte y el valor es constante de255。 |
Resumiendo, la cabeza y el final de ziplist, a continuación, hablemos brevemente de los campos más importantes de entry.
En general, un entry consta de prevlen, encoding y entry-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-los campos data, prevlen y entry forman, pero cuando el entry es un número muy pequeño, se omiten según la codificación.
campo data. A continuación, se realiza una resumen:
Luego es el campo encoding：dependiendo del contenido del elemento actual, adopta diferentes métodos de codificación, como se muestra a continuación:
1、si el contenido del elemento es una cadena de caracteres, los valores de encoding son:
00xx xxxx ：00 al principio indica que la longitud de la cadena de caracteres se utiliza6bits representan.
01xx xxxx | xxxx xxxx ：01El principio indica que la longitud de la cadena de caracteres se14bits representan, esto14bits se almacenan en orden mayor.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10El principio indica que los cuatro bytes posteriores son la longitud de la cadena de caracteres, esto32bits se almacenan en orden mayor.
2、si el contenido del elemento es un número, los valores de encoding son:
1100 0000：representa que el número ocupa los bytes posteriores2bytes.
1101 0000：representa que el número ocupa los bytes posteriores4bytes.
1110 0000：representa que el número ocupa los bytes posteriores8bytes.
1111 0000 ：representa que el número ocupa los bytes posteriores3bytes.
1111 1110 ：representa que el número ocupa los bytes posteriores1bytes.
1111 1111 ：representa el último elemento de la lista enlazada comprimida (codificación especial).
1111 xxxx ：representa que solo se utilizan los bits posteriores4bits representan 0~12enteros, ya que 0000,1110como el primer elemento, el tamaño del elemento anterior es 0, por lo que ocupa un byte 00. Según las reglas de codificación que mencionamos anteriormente, el elemento1111tres ya están ocupados, lo que significa que aquí los cuatro dígitos xxxx solo pueden representar 0001~1101convertido a decimal es el número1~13pero Redis regula que se utiliza para representar 0~12，por lo que cuando se encuentra con esta codificación, es necesario extraer las últimas cuatro cifras y restar1para obtener el valor correcto.
último es el campo entry-data：si el valor del elemento es una cadena de caracteres, se guarda el valor del elemento en sí. Si el valor del elemento es un número muy pequeño (según la regla de codificación anterior, es 0~12），no hay ese campo.
La codificación de la lista enlazada comprimida es muy compleja, pero también es la esencia de esta estructura de datos, veamos un ejemplo:
Nota:Este ejemplo es mencionado en el código fuente de Redis
//constituida por los elementos2,5formada por la lista enlazada comprimida [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end //El contenido codificado de la cadena de caracteres "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
La parte superior es un fragmento representado en hexadecimal2,5una lista enlazada comprimida formada por dos elementos.
a continuación, insertamos un elemento de cadena de caracteres Hello World en la cola de esta lista enlazada comprimida, primero veamos cómo codificar la cadena de caracteres, según las reglas de codificación acordadas, primero se utiliza un byte para representar la longitud del elemento anterior, aquí el elemento anterior es5ocupa dos bytes en total, por lo que primero se utiliza un byte para representar la longitud del elemento anterior 02a continuación, es la codificación de la cadena de caracteres, la longitud de la cadena de caracteres que vamos a agregar es11el espacio en blanco también se considera), convertido en binario es1011de acuerdo con las reglas de codificación de la cadena de caracteres, utilizando 0000 1011lo que representa, convertido en hexadecimal es 0b, y luego se agrega el código ASCII de la cadena de caracteres en sí, combinándolos se obtiene la codificación de la cadena de caracteres: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。
En este momento, toda la lista enlazada comprimida se convierte en:
[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
Segundo, análisis del código fuente del comando de lista enlazada comprimida ziplist
Después de entender las reglas de codificación anteriores, veamos algunas operaciones del código fuente de la lista enlazada comprimida ziplist. En este artículo, se resume el principio básico de la lista enlazada comprimida a través de las operaciones de creación, inserción, eliminación y búsqueda de elementos.
Primero es la creación:
//Definir el tamaño de la cabecera de la lista enlazada comprimida compuesta por zlbytes, zltail y zllen
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//Crear una lista enlazada comprimida y devolver el puntero a la lista
unsigned char *ziplistNew(void) {
//la razón por la que aquí es+1debido a que el elemento final ocupa un byte, esto es también el tamaño mínimo de una lista comprimida
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//Asignar memoria
unsigned char *zl = zmalloc(bytes);
//Establecer el tamaño de la lista
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//Establecer el desplazamiento del último elemento
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//Establecer el número de elementos
ZIPLIST_LENGTH(zl) = 0;
//Establecer el elemento final (solo se solicitó espacio anteriormente)
zl[bytes-1]= ZIP_END;
return zl;
}
La lógica de creación de la lista comprimida es muy simple, es decir, solicitar un espacio fijo que contenga los nodos de encabezado y final, y luego inicializar el contexto de la lista.
En comparación con la creación, el código fuente de la adición de elementos es muy largo, para facilitar la comprensión, antes de ver el código, primero ordenamos lógicamente la lógica de adición de elementos.
Estos tres pasos son las etapas clave, y las otras incluyen operaciones como actualizar el desplazamiento del nodo final, modificar el número de elementos de la lista, etc. Por supuesto, debido a que la lista comprimida se implementa basada en un array, la copia de memoria también es indispensable en el momento de la inserción o eliminación de elementos.
Después de resumir los pasos anteriores, comenzamos a analizar paso a paso el código fuente, es largo, veamos lentamente:
//Los cuatro parámetros en sucesión son: lista comprimida, posición de inserción (nuevo elemento insertado después del elemento p), valor del elemento, longitud del elemento
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//Aquí se guarda la longitud actual de la lista enlazada
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. El propósito de esta lógica es obtener la longitud del elemento anterior
if (p[0] != ZIP_END) {
//Si el elemento en la posición de inserción no es el elemento final, obtener la longitud del elemento
//aquí se ha dividido para facilitar su uso posterior, prevlensize guarda la longitud del campo encoding, prevlen guarda la longitud del elemento en sí
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//si el elemento en la posición de inserción es el elemento final, entonces es necesario insertar el nuevo elemento en el extremo de la lista
//obtener el último elemento de la lista (nota: el último elemento no es el elemento final)
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
//si el último elemento no es el elemento final, entonces este elemento es el elemento previo del nuevo elemento, obtener la longitud de este elemento
prevlen = zipRawEntryLength(ptail);
}
//de lo contrario, significa que la lista aún no tiene ningún elemento, es decir, la longitud del elemento previo del nuevo elemento es 0
}
//2. codificar el nuevo elemento, obtener el tamaño total del nuevo elemento
if (zipTryEncoding(s,slen,&value,&encoding)) {
//si es un número, se codifica según el número
reqlen = zipIntSize(encoding);
} else {
//la longitud del elemento es la longitud de la cadena
reqlen = slen;
}
//la longitud total del nuevo elemento es la longitud del valor más la longitud del elemento previo y la longitud del encoding
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//si la posición de inserción no es la parte final de la lista enlazada,则需要判断新元素的后续元素的prevlen campo
//según las reglas de codificación anteriores, este campo puede necesitar expandirse
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) &63; zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {}}
nextdiff = 0;
forcelarge = 1;
}
//expandir según el nuevo tamaño del array calculado, ya que la dirección del nuevo array puede cambiar, por lo tanto, aquí se registra el desplazamiento antiguo
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//calcular la posición de inserción en el nuevo array
p = zl+offset;
//si el elemento insertado no está en la parte final de la lista enlazada
if (p[0] != ZIP_END) {
//copiar el elemento siguiente al nuevo elemento al nuevo array,-1para el elemento final
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//El campo prevlen del elemento siguiente del nuevo elemento
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//Actualizar el desplazamiento del último elemento
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//Cuando el elemento siguiente del nuevo elemento no tiene más de un elemento, el nuevo desplazamiento del elemento final debe sumar 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 {
//Insertar el nuevo elemento al final de la lista y actualizar el desplazamiento del final
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0 indica que el tamaño del elemento siguiente ha cambiado, por lo tanto, necesitamos actualizar en cadena los elementos siguientes del elemento siguiente
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//Escribir el nuevo elemento en la lista
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
//El almacenamiento de la lista de compactación almacena la cantidad de elementos+1
ZIPLIST_INCR_LENGTH(zl,1;
return zl;
}
Después de analizar la lógica de inserción de elementos, suspiro aliviado, realmente es largo, y hay muchos detalles.
Después de analizar el proceso de eliminación de elementos, suspiro aliviado, realmente es largo, y hay muchos detalles.
//Los parámetros son: la lista de compactación, la posición inicial del elemento a eliminar, y la cantidad de elementos a eliminar
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;
//Leer el elemento apuntado por p y guardarlo en first
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {}}
//contar la longitud total eliminada
p += zipRawEntryLength(p);
//contar el número real de elementos eliminados
deleted++;
}
//número de bytes a eliminar del elemento
totlen = p-first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//juzgar si el tamaño del elemento ha cambiado
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//modificar el campo prevlen del elemento eliminado
p -= nextdiff;
zipStorePrevEntryLength(p, first.prevrawlen);
//actualizar el desplazamiento del elemento final
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//cuando el elemento siguiente a eliminar tiene más de un elemento, se debe agregar nextdiff al desplazamiento del nuevo elemento final
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//mover los elementos restantes detrás al frente
memmove(first.p, p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1;
} else {
//eliminar directamente hasta el final de la lista, por lo que no se requiere copia de memoria, solo se debe modificar el desplazamiento del último elemento
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//redimensionar el tamaño del array
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//modificar el número de elementos en la lista
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0 indica que el tamaño del elemento ha cambiado, por lo que se requiere una actualización en cascada
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl, p);
}
return zl;
}
Veamos la operación de búsqueda del elemento al final:
//Los parámetros son: lista enlazada comprimida, valor del elemento a buscar, longitud del elemento a buscar, número de elementos saltados entre comparaciones
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) {
//Si dos números son iguales, devolver el puntero del elemento
return p;
}
}
}
//Reiniciar la cantidad de elementos que se deben saltar
skipcnt = skip;
} else {
//Saltar elementos
skipcnt--;
}
//Recorrer el siguiente elemento
p = q + len;
}
//Se ha recorrido toda la lista sin encontrar el elemento
return NULL;
}
Hasta aquí, se han resumido los principios de las cuatro operaciones básicas de creación, adición, eliminación y búsqueda de la lista comprimida.
Tercero, resumen de la estructura de datos de lista comprimida ziplist
La aplicación de la compresión de lista ziplist en redis es muy amplia, es una de las estructuras de datos más características de redis. La esencia de esta estructura de datos realmente radica en las reglas de codificación resumidas en la primera parte del artículo. Después de entender este contenido, puede profundizar en la comprensión del código posterior.
Hay que decir que la parte del código es realmente larga, realmente necesita paciencia, incluso estaba muy confundido mientras leía. Si están interesados en el código, sugiero seguir mi método, primero organizar por sí mismos qué debe hacer una operación específica (por ejemplo, la inserción de elementos mencionada anteriormente), y luego ver el código puede ser más fácil de entender.
Dejamos un pequeño problema al final, si el ziplist de redis tiene una alta utilización de memoria, ¿por qué aún se proporciona la estructura de lista común para su uso?
No hay respuesta estándar a esta pregunta, cada persona tiene su propia interpretación.
Resumen
Eso es todo el contenido de este artículo. Espero que el contenido de este artículo tenga un valor de referencia para su aprendizaje o trabajo. Si tienen alguna pregunta, pueden dejar comentarios para intercambiar. Gracias por su apoyo a la tutorial de gritos.
Declaración: El contenido de este artículo se ha obtenido de la red, es propiedad del autor original, el contenido se ha contribuido y subido por los usuarios de Internet de manera autónoma. Este sitio no posee los derechos de propiedad, no ha sido editado por humanos y no asume ninguna responsabilidad legal relacionada. Si encuentra contenido sospechoso de copyright, por favor envíe un correo electrónico a: notice#oldtoolbag.com (al enviar un correo electrónico, reemplace # con @) para denunciar y proporcionar evidencia relevante. Una vez confirmado, este sitio eliminará inmediatamente el contenido sospechoso de infracción.