English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Introdução
A lista encadeada comprimida (ziplist) é composta por uma série de blocos de memória codificados de maneira especial, que desempenha um papel muito importante na otimização do armazenamento de dados do Redis. Este artigo resume um dos dados estruturais mais usados no Redis, a lista encadeada comprimida ziplist. Diz-se que essa estrutura de dados está em todos os lugares no Redis, não é exagero, além da lista, muitas outras estruturas de dados também usam para transição, por exemplo, o SortedSet mencionado no artigo anterior. Não há muito a dizer, vamos ver a introdução detalhada juntos.
Um, resumo do estrutura de dados da lista encadeada comprimida ziplist
Primeiro, vamos olhar para a estrutura geral da ziplist, conforme a figura a seguir:
Diagrama da estrutura da lista encadeada comprimida ziplist
Pode-se ver que há muitos campos e tamanhos de bytes diferentes, mas isso é a essência da lista encadeada comprimida, vamos resumir um a um.
| campo | significado |
|---|---|
| zlbytes | Este campo é o primeiro campo da lista encadeada comprimida, é um inteiro sem sinal e ocupa4bytes. Usado para representar o número total de bytes ocupados pela lista encadeada comprimida (inclusive dela mesma). |
| zltail | Inteiro sem sinal, ocupa4bytes. Usado para armazenar o deslocamento do início da lista encadeada comprimida até o último entry (não o elemento final zlend), usado em cenários de saltos rápidos para o final da lista. |
| zllen | Inteiro sem sinal, ocupa2bytes. Usado para armazenar o número total de entries contidas na lista encadeada comprimida. |
| zlend | Entry especial usada para representar o final da lista encadeada comprimida. Ocupa um byte e o valor é sempre255。 |
Resumindo, o cabeçalho e o final da ziplist, vamos agora resumir o campo crucial de entry.
Em geral, um entry é composto por prevlen, encoding e entry-data三个字段组成，但当entry是个很小的整数时，会根据编码省略掉entry-data字段。下面依次进行总结：
campos data, prevlen e encoding compõem, mas quando o entry é um inteiro muito pequeno, será omitido com base na codificação.
Em seguida, há o campo encoding: ele usará diferentes métodos de codificação com base no conteúdo do elemento atual, conforme a seguir:
1、se o conteúdo do elemento for uma string, os valores de encoding são:
00xx xxxx ：00 no início representa que o comprimento da string é representado usando6bits representam.
01xx xxxx | xxxx xxxx ：01O início representa que o comprimento da string é determinado por14bits representam, isso14bytes usam armazenamento big-endian.
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10O início representa que os próximos quatro bytes são a comprimento da string, isso32bytes usam armazenamento big-endian.
2、se o conteúdo do elemento for um número, os valores de encoding são:
1100 0000：representa a quantidade de bytes usados pelo número a seguir2bytes.
1101 0000：representa a quantidade de bytes usados pelo número a seguir4bytes.
1110 0000：representa a quantidade de bytes usados pelo número a seguir8bytes.
1111 0000 ：representa a quantidade de bytes usados pelo número a seguir3bytes.
1111 1110 ：representa a quantidade de bytes usados pelo número a seguir1bytes.
1111 1111 ：representa o último elemento da lista encadeada comprimida (codificação especial).
1111 xxxx ：representa apenas os últimos4dígitos representam 0~12um inteiro, pois 00001110and1111três tipos já estão ocupados, o que significa que os quatro dígitos xxxx aqui só podem representar 0001~1101，convertido para decimal é o número1~13，mas o Redis define que ele é usado para representar 0~12，portanto, quando encontrarmos essa codificação, precisamos pegar os últimos quatro dígitos e subtrair1para obter o valor correto.
No final, há o campo entry-data：se o valor do elemento for uma string, então é salva o valor do elemento em si. Se o valor do elemento for um número muito pequeno (segundo a regra de codificação acima, é 0~12），então não há esse campo.
A codificação da lista encadeada comprimida é muito complexa, mas isso é também a essência dessa estrutura de dados, vamos ver um exemplo:
Nota:Este exemplo é mencionado no código-fonte do Redis
//por elementos2,5formando a lista encadeada comprimida [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" fim //O conteúdo codificado da string "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
A seguir, um exemplo de representação hexadecimal2,5duas entradas formam uma lista encadeada comprimida.
A seguir, inserimos um elemento de string Hello World no final da lista encadeada comprimida, vamos ver como codificá-lo, de acordo com as regras de codificação acordadas, primeiro usamos um byte para representar o comprimento do elemento anterior, aqui o elemento anterior é5，em total ocupam dois bytes, portanto, primeiro usamos um byte para representar o comprimento do elemento anterior 02，a seguir é a codificação da string, a string que devemos adicionar tem um comprimento de11（espaço também conta），convertido para binário é1011，de acordo com as regras de codificação da string, usando 0000 1011Isso significa, convertido para hexadecimal é 0b, e adicionamos o código ASCII da string em si, resultando na codificação da string: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]。
Neste momento, toda a lista encadeada comprimida se torna:
[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álise de código-fonte do comando da lista encadeada comprimida ziplist
Após entender as regras de codificação acima, vamos analisar as operações de código-fonte da parte da lista encadeada comprimida ziplist. Este artigo resume os princípios básicos da lista encadeada comprimida através das operações de criação, inserção, exclusão e busca de elementos.
Primeiro é a criação:
//Definir o tamanho do cabeçalho da lista encadeada comprimida composta por zlbytes, zltail e zllen
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//Criar uma lista encadeada comprimida e retornar o ponteiro para a lista
unsigned char *ziplistNew(void) {
//Aqui, a razão é+1porque o elemento final ocupa um byte, isso é o tamanho mínimo de uma lista comprimida
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//Alocar memória
unsigned char *zl = zmalloc(bytes);
//Definir o tamanho da lista
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//Definir o deslocamento do último elemento
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//Definir o número de elementos
ZIPLIST_LENGTH(zl) = 0;
//Definir o elemento final (o que foi solicitado acima é apenas um espaço)
zl[bytes-1] = ZIP_END;
return zl;
}
A lógica para criar a lista comprimida é muito simples, é solicitar um espaço fixo que contenha os nós de cabeça e de cauda, e inicializar o contexto da lista.
Em comparação com a criação, o código-fonte para adicionar elementos é muito longo, para facilitar a compreensão, antes de olhar para o código-fonte, vamos organizar logicamente a lógica de adição de elementos.
Os três passos acima são os passos principais, além disso, há operações como atualizar o deslocamento do nó final, modificar o número de elementos da lista, etc. Claro, devido à implementação da lista comprimida com base em array, a cópia de memória também é inevitável ao inserir ou remover elementos.
Após concluir os passos acima, começamos a analisar o código-fonte passo a passo, o que é longo, vamos ver lentamente:
//Os quatro parâmetros são, em ordem: lista comprimida, posição de inserção (o novo elemento é inserido após o elemento p), valor do elemento, comprimento do elemento
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//Aqui é onde é salvo o comprimento atual da lista encadeada
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. O propósito lógico desse trecho é obter o comprimento do elemento anterior
if (p[0] != ZIP_END) {
//Se o elemento na posição de inserção não for o elemento final, obtenha o comprimento do elemento
//aqui foi dividido para facilitar o uso posterior, prevlensize armazena o comprimento do campo encoding, prevlen armazena o comprimento do elemento em si
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//se o elemento na posição de inserção for o elemento final, então é necessário inserir o novo elemento no final da lista
//obter o último elemento da lista (nota: o último elemento não é o elemento final)
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
//se o último elemento não for o elemento final, então este elemento é o elemento anterior do novo elemento, obtenha o comprimento deste elemento
prevlen = zipRawEntryLength(ptail);
}
//senão, isso significa que a lista ainda não tem nenhum elemento, ou seja, o comprimento do elemento anterior do novo elemento é 0
}
//2. codifique o novo elemento, obtenha o tamanho total do novo elemento
if (zipTryEncoding(s,slen,&value,&encoding)) {
//se for um número, codifique conforme o número
reqlen = zipIntSize(encoding);
} else {
//o comprimento do elemento é o comprimento da string
reqlen = slen;
}
//a nova elemento tem um comprimento total de comprimento do valor mais comprimento do elemento anterior e encoding
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//se a posição de inserção não for o final da lista encadeada, deve-se avaliar o campo prevlen do elemento subsequente novo
//de acordo com as regras de codificação acima, este campo pode precisar de aumento de capacidade
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) &63; zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {}}
nextdiff = 0;
forcelarge = 1;
}
//aumentar o tamanho do array conforme calculado, pois o endereço do novo array pode mudar, portanto, aqui é registrado o deslocamento antigo
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//calcular a posição de inserção no novo array
p = zl+offset;
//se o elemento inserido não estiver no final da lista encadeada
if (p[0] != ZIP_END) {
//copiar o elemento subsequente novo para o novo array,-1para elemento final
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//O campo prevlen do elemento subsequente do novo elemento
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//Atualizar o offset do último elemento
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//Quando o elemento subsequente do novo elemento não tiver apenas um, o novo offset do elemento final deve ser adicionado 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 {
//O novo elemento é inserido no final da lista, atualizando o offset do final
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0 indica que o comprimento do elemento subsequente mudou, portanto, precisamos atualizar cascata os elementos subsequentes do elemento subsequente
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
//Escrever o novo elemento na lista
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
//O número de elementos armazenados na lista encadeada comprimida+1
ZIPLIST_INCR_LENGTH(zl,1;
return zl;
}
Após analisar a lógica de inserção de elementos, respiramos aliviados, realmente longo, com muitos detalhes.
A seguir, vamos ver o processo de remoção de elementos, que é mais simples do que a adição. Após limpar o elemento atual, precisamos copiar um a um os elementos subsequentes (isto é a diferença entre as estruturas de dados de array e linked list), e, em seguida, verificar se há necessidade de atualização cascata, veja o código a seguir:
//Os parâmetros são, em ordem: a lista encadeada comprimida, a posição inicial do elemento a ser removido, e o número de elementos a serem removidos
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;
//Ler o elemento apontado por p e guardá-lo em first
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {}}
//Contar o comprimento total excluído
p += zipRawEntryLength(p);
//Contar o número de elementos excluídos realmente
deleted++;
}
//Número de bytes a serem excluídos do elemento
totlen = p-first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//Determinar se o tamanho do elemento mudou
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//Modificar o campo prevlen do elemento excluído
p -= nextdiff;
zipStorePrevEntryLength(p, first.prevrawlen);
//Atualizar o deslocamento do elemento final
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
//Quando o elemento a ser excluído tem mais de um elemento subsequente, o deslocamento do novo elemento final deve ser adicionado com nextdiff
zipEntry(p, &tail);
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//Mover os elementos restantes para a frente
memmove(first.p, p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1;
} else {
//Exclui diretamente até o final da lista, portanto, não é necessário copiar memória, apenas modificar o deslocamento do último elemento
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
//Redimensionar o tamanho do array
offset = first.p-zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
//Modificar o número de elementos da lista
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
//nextdiff != 0 indica que o tamanho do elemento mudou, e é necessário fazer uma atualização cascata
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl, p);
}
return zl;
}
Vamos analisar a operação de busca do elemento:
//Os parâmetros são: lista comprimida, valor do elemento a ser encontrado, comprimento do elemento a ser encontrado, número de elementos pulados entre comparações
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;
//Keep looping as long as it's not the end element
while (p[0] != ZIP_END) {
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
//Query the prevlen field of the current element in the list
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//Query the encoding field of the current element in the list
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
//Reached the position of the element to be compared
if (skipcnt == 0) {
//If the current element in the list is a string
if (ZIP_IS_STR(encoding)) {
//Compare with the string to be searched
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
//Matching successful, then the pointer to the element to be searched
return p;
}
} else {
//If the current element is a number and vencoding is 0
if (vencoding == 0) {
//Attempt to encode the value to be searched as a number
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
//If encoding fails, it means the element to be searched is not a number at all
//Then set vencoding to the maximum value, acting as a marker
//That is, there is no need to try to encode the value to be searched as a number later
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
//If vencoding != UCHAR_MAX, it means the element to be searched is successfully encoded as a number
if (vencoding != UCHAR_MAX) {
//Extract element from the current linked list by number
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) {
//Se dois números forem iguais, retorne o ponteiro do elemento
return p;
}
}
}
//Reiniciar o número de elementos a serem pulados
skipcnt = skip;
} else {
//Pular elemento
skipcnt--;
}
//Percorrer o próximo elemento
p = q + len;
}
//Percorreu toda a lista, mas não encontrou o elemento
return NULL;
}
Aqui, resumimos os princípios básicos de criação, adição, exclusão e busca de operações básicas do ziplist comprimido.
III. Resumo da Estrutura de Dados do Ziplist Comprimido
O ziplist comprimido é amplamente aplicado no redis, é considerado uma das estruturas de dados mais características do redis. A essência dessa estrutura de dados está realmente no artigo do primeiro parte resumiu as regras de codificação, antes de entender esse conteúdo, o código-fonte pode ser facilmente compreendido.
Devo admitir que a parte do código é realmente longa e requer paciência. Mesmo enquanto li, fiquei com a cabeça grande. Se você estiver interessado no código-fonte, recomendo que você organize primeiro o que precisa ser feito para uma operação específica (por exemplo, o elemento mencionado acima) e então olhar para o código pode ser mais fácil de entender.
Por fim, deixei uma pequena pergunta: se o ziplist do redis tem uma alta eficiência de uso de memória, por que ainda oferece a estrutura de lista comum para os usuários?
Não há resposta padrão para essa pergunta, cada um vê conforme sua própria visão e sabedoria.
Resumo
Isso é tudo que há neste artigo. Espero que o conteúdo deste artigo tenha algum valor de referência para o seu aprendizado ou trabalho. Se tiver dúvidas, pode deixar um comentário para trocar ideias. Obrigado pelo suporte ao Tutorial de Grito.
Declaração: O conteúdo deste artigo é extraído da Internet, pertence ao autor original, foi submetido e carregado voluntariamente pelos usuários da Internet. Este site não possui direitos de propriedade, não foi editado artificialmente e não assume responsabilidade legal. Se você encontrar conteúdo suspeito de violação de direitos autorais, por favor, envie um e-mail para: notice#oldtoolbag.com (ao enviar e-mail, substitua # por @ para denunciar e forneça provas. Aparentemente, o site deletará o conteúdo suspeito de violação de direitos autorais imediatamente.