Quais são as estruturas de dados subjacentes usadas pelo Redis?

Estou tentando responder duas perguntas em uma lista definitiva:

1. Quais são as estruturas de dados subjacentes usadas pelo Redis?
2. E quais são as principais vantagens / desvantagens / casos de uso para cada tipo?

Então, eu li que as listas Redis são realmente implementadas com listas vinculadas. Mas para outros tipos, não consigo descobrir nenhuma informação. Além disso, se alguém se deparar com essa questão e não tiver um resumo de alto nível dos prós e contras de modificar ou acessar diferentes estruturas de dados, ele terá uma lista completa de quando usar melhor tipos específicos para referência também.

Especificamente, estou procurando descrever todos os tipos: string, lista, conjunto, zset e hash.

Ah, eu olhei para estes artigos, entre outros, até agora:

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

Tentarei responder à sua pergunta, mas começarei com algo que pode parecer estranho no começo: se você não estiver interessado nos conteúdos internos do Redis , não se preocupe em como os tipos de dados são implementados internamente. Isso é por uma razão simples: para cada operação Redis, você encontrará a complexidade do tempo na documentação e, se você tiver o conjunto de operações e a complexidade do tempo, a única outra coisa que você precisa é ter alguma pista sobre o uso da memória (e porque realizamos muitas otimizações que podem variar de acordo com os dados; a melhor maneira de obter esses números é fazendo alguns testes triviais do mundo real).

Mas desde que você perguntou, aqui está a implementação subjacente de todos os tipos de dados Redis.

• As cadeias são implementadas usando uma biblioteca de cadeias de caracteres dinâmicas C, para que não pagemos (falando assintoticamente) pelas alocações nas operações de acréscimo. Dessa forma, temos O (N) anexados, por exemplo, em vez de ter um comportamento quadrático.
• As listas são implementadas com listas vinculadas.
• Conjuntos e Hashes são implementados com tabelas de hash.
• Conjuntos classificados são implementados com listas de pulos (um tipo peculiar de árvores balanceadas).

Porém, quando listas, conjuntos e conjuntos classificados são pequenos em número de itens e tamanho dos maiores valores, uma codificação diferente e muito mais compacta é usada. Essa codificação difere para tipos diferentes, mas possui o recurso de que é um blob compacto de dados que geralmente força uma varredura O (N) para cada operação. Como usamos esse formato apenas para objetos pequenos, isso não é um problema; a varredura de um pequeno blob O (N) é inconsciente do cache, portanto, na prática, é muito rápido e, quando há muitos elementos, a codificação é automaticamente alterada para a codificação nativa (lista vinculada, hash etc.).

Mas sua pergunta não era realmente sobre assuntos internos, seu argumento era que tipo usar para realizar o quê? .

Cordas

Este é o tipo base de todos os tipos. É um dos quatro tipos, mas também é o tipo base dos tipos complexos, porque uma Lista é uma lista de cadeias, um Conjunto é um conjunto de cadeias e assim por diante.

Uma sequência Redis é uma boa ideia em todos os cenários óbvios em que você deseja armazenar uma página HTML, mas também quando deseja evitar a conversão de dados já codificados. Por exemplo, se você possui JSON ou MessagePack, pode apenas armazenar objetos como strings. No Redis 2.6, você pode manipular esse tipo de objeto do lado do servidor usando scripts Lua.

Outro uso interessante de strings são bitmaps e, em geral, matrizes de acesso aleatório de bytes, já que o Redis exporta comandos para acessar intervalos aleatórios de bytes, ou mesmo bits únicos. Por exemplo, verifique esta boa postagem no blog: Métricas rápidas e fáceis em tempo real usando Redis .

Listas

As listas são boas quando é provável que você toque apenas nos extremos da lista: cauda próxima ou cabeça. As listas não são muito boas para paginar coisas, porque o acesso aleatório é lento, O (N). Portanto, bons usos das listas são filas e pilhas simples ou itens de processamento em loop usando RPOPLPUSH com a mesma origem e destino para "rotacionar" um anel de itens.

As listas também são boas quando queremos apenas criar uma coleção limitada de N itens, onde geralmente acessamos apenas os itens superiores ou inferiores, ou quando N é pequeno.

Conjuntos

Os conjuntos são uma coleta de dados desordenada, portanto, são bons toda vez que você possui uma coleção de itens e é muito importante verificar a existência ou o tamanho da coleção de uma maneira muito rápida. Outra coisa interessante sobre os conjuntos é o suporte para espreitar ou abrir elementos aleatórios (comandos SRANDMEMBER e SPOP).

Os conjuntos também são bons para representar relações, por exemplo, "O que são amigos do usuário X?" e assim por diante. Mas outras boas estruturas de dados para esse tipo de coisa são conjuntos classificados, como veremos.

Os conjuntos suportam operações complexas, como interseções, uniões e assim por diante, portanto, essa é uma boa estrutura de dados para usar o Redis de maneira "computacional", quando você tem dados e deseja realizar transformações nesses dados para obter alguma saída.

Conjuntos pequenos são codificados de maneira muito eficiente.

Hashes

Hashes são a estrutura de dados perfeita para representar objetos, compostos por campos e valores. Os campos de hashes também podem ser incrementados atomicamente usando HINCRBY. Quando você tem objetos como usuários, postagens no blog ou algum outro tipo de item , os hashes provavelmente são o caminho a percorrer, se você não quiser usar sua própria codificação como JSON ou similar.

No entanto, lembre-se de que pequenos hashes são codificados com muita eficiência pelo Redis, e você pode solicitar ao Redis que obtenha, ative ou defina atomicamente os campos individuais de maneira muito rápida.

Hashes também podem ser usados ​​para representar estruturas de dados vinculadas, usando referências. Por exemplo, verifique a implementação de comentários do lamernews.com.

Conjuntos classificados

Conjuntos classificados são as únicas outras estruturas de dados, além de listas, para manter os elementos ordenados . Você pode fazer várias coisas legais com conjuntos classificados. Por exemplo, você pode ter todos os tipos de listas dos principais itens em seu aplicativo da web. Os principais usuários por pontuação, as principais publicações por visualizações de página, o que for maior, mas uma única instância do Redis oferecerá suporte a toneladas de operações de inserção e obtenção de elementos principais por segundo.

Conjuntos classificados, como conjuntos regulares, podem ser usados ​​para descrever relações, mas também permitem que você pagine a lista de itens e lembre-se da ordem. Por exemplo, se me lembro de amigos do usuário X com um conjunto classificado, posso lembrá-los facilmente em ordem de amizade aceita.

Conjuntos classificados são bons para filas prioritárias.

Os conjuntos classificados são como listas mais poderosas, onde inserir, remover ou obter intervalos no meio da lista é sempre rápido. Mas eles usam mais memória e são estruturas de dados O (log (N)).

Conclusão

Espero ter fornecido algumas informações neste post, mas é muito melhor fazer o download do código fonte do lamernews em http://github.com/antirez/lamernews e entender como ele funciona. Muitas estruturas de dados da Redis são usadas no Lamer News, e há muitas dicas sobre o que usar para resolver uma determinada tarefa.

Desculpe pelos erros gramaticais, é meia-noite aqui e estou cansado demais para revisar a postagem;)

Na maioria das vezes, você não precisa entender as estruturas de dados subjacentes usadas pelo Redis. Mas um pouco de conhecimento ajuda você a fazer trocas de memória da CPU v / s. Também ajuda a modelar seus dados de maneira eficiente.

Internamente, o Redis usa as seguintes estruturas de dados:

1. Corda
2. Dicionário
3. Lista duplamente vinculada
4. Skip List
5. Zip List
6. Conjuntos Int
7. Zip Maps (descontinuado em favor da lista zip desde o Redis 2.6)

Para encontrar a codificação usada por uma chave específica, use o comando object encoding <key>.

1. Strings

No Redis, Strings são chamadas Simple Dynamic Strings, ou SDS . É um invólucro pequeno sobre um char *que permite armazenar o comprimento da string e o número de bytes livres como prefixo.

Como o comprimento da string é armazenado, strlen é uma operação O (1). Além disso, como o comprimento é conhecido, as seqüências de caracteres Redis são binárias seguras. É perfeitamente legal que uma string contenha o caractere nulo .

Strings são a estrutura de dados mais versátil disponível no Redis. A String é tudo do seguinte:

1. Uma sequência de caracteres que pode armazenar texto. Consulte os comandos SET e GET .
2. Uma matriz de bytes que pode armazenar dados binários.
3. Um longque pode armazenar números. Consulte os comandos INCR , DECR , INCRBY e DECRBY .
4. Uma matriz (de chars, ints, longsou qualquer outro tipo de dados) que pode permitir o acesso aleatório eficiente. Veja SetRange e GetRange comandos.
5. Uma matriz de bits que permite definir ou obter bits individuais. Veja SETBIT e GETBIT comandos.
6. Um bloco de memória que você pode usar para criar outras estruturas de dados. Isso é usado internamente para criar ziplists e intsets, que são estruturas de dados compactas e com eficiência de memória para um pequeno número de elementos. Mais sobre isso abaixo.

2. Dicionário

O Redis usa um dicionário para o seguinte:

1. Para mapear uma chave para seu valor associado, em que o valor pode ser uma sequência, hash, conjunto, conjunto ou lista classificada.
2. Para mapear uma chave para seu carimbo de data / hora de expiração.
3. Para implementar os tipos de dados Hash, Set e Sorted Set.
4. Para mapear comandos Redis para as funções que manipulam esses comandos.
5. Para mapear uma chave Redis para uma lista de clientes que estão bloqueados nessa chave. Veja BLPOP .

Os dicionários Redis são implementados usando tabelas de hash . Em vez de explicar a implementação, explicarei apenas as coisas específicas do Redis:

1. Os dicionários usam uma estrutura chamada dictTypepara estender o comportamento de uma tabela de hash. Essa estrutura possui ponteiros de função e, portanto, as seguintes operações são extensíveis: a) função de hash, b) comparação de chaves, c) destruidor de chaves ed) destruidor de valor.
2. Os dicionários usam o murmurhash2 . (Anteriormente, eles usavam a função hash djb2 , com seed = 5381, mas a função hash foi alterada para murmur2 . Consulte esta pergunta para obter uma explicação do algoritmo hash djb2 .)
3. O Redis usa Hashing Incremental, também conhecido como Redimensionamento Incremental . O dicionário possui duas tabelas de hash. Sempre que o dicionário é tocado , um bloco é migrado da primeira tabela de hash (menor) para o segundo. Dessa forma, o Redis impede uma operação de redimensionamento dispendiosa.

A Setestrutura de dados usa um dicionário para garantir que não haja duplicatas. O Sorted Setusa um dicionário para mapear um elemento para sua pontuação, e é por isso que ZSCORE é uma operação O (1).

3. Listas duplamente vinculadas

O listtipo de dados é implementado usando listas duplamente vinculadas . A implementação do Redis é um livro didático direto do algoritmo. A única alteração é que o Redis armazena o comprimento na estrutura de dados da lista. Isso garante que o LLEN tenha complexidade O (1).

4. Pular listas

O Redis usa Skip Lists como estrutura de dados subjacente para conjuntos classificados. A Wikipedia tem uma boa introdução. O artigo de William Pugh Skip Lists: uma alternativa probabilística às árvores equilibradas tem mais detalhes.

Os conjuntos classificados usam uma lista de ignorados e um dicionário. O dicionário armazena a pontuação de cada elemento.

A implementação da Lista de ignorados do Redis é diferente da implementação padrão das seguintes maneiras:

1. Redis permite pontuações duplicadas. Se dois nós tiverem a mesma pontuação, eles serão classificados pela ordem lexicográfica .
2. Cada nó tem um ponteiro de volta no nível 0. Isso permite que você percorra os elementos na ordem inversa da pontuação.

5. Lista Zip

Uma Lista Zip é como uma lista duplamente vinculada, exceto que não usa ponteiros e armazena os dados em linha.

Cada nó em uma lista duplamente vinculada possui 3 ponteiros - um ponteiro para frente, um ponteiro para trás e um ponteiro para referenciar os dados armazenados nesse nó. Os ponteiros requerem memória (8 bytes em um sistema de 64 bits) e, portanto, para pequenas listas, uma lista duplamente vinculada é muito ineficiente.

Uma Lista Zip armazena elementos seqüencialmente em uma Cadeia de caracteres Redis. Cada elemento possui um cabeçalho pequeno que armazena o comprimento e o tipo de dados do elemento, o deslocamento para o próximo elemento e o deslocamento para o elemento anterior. Esses deslocamentos substituem os ponteiros para frente e para trás. Como os dados são armazenados em linha, não precisamos de um ponteiro de dados.

A lista Zip é usada para armazenar pequenas listas, conjuntos classificados e hashes. Os conjuntos classificados são achatados em uma lista como [element1, score1, element2, score2, element3, score3]e armazenados na Lista Zip. Os hashes são achatados em uma lista como [key1, value1, key2, value2]etc.

Com as Listas Zip, você tem o poder de fazer uma troca entre CPU e Memória. As listas zip são eficientes em termos de memória, mas usam mais CPU do que uma lista vinculada (ou tabela Hash / Skip List). Encontrar um elemento na lista zip é O (n). A inserção de um novo elemento requer a realocação da memória. Por esse motivo, o Redis usa essa codificação apenas para pequenas listas, hashes e conjuntos classificados. Você pode ajustar esse comportamento alterando os valores de <datatype>-max-ziplist-entriese <datatype>-max-ziplist-value>no redis.conf. Consulte Otimização de memória Redis, seção "Codificação especial de pequenos tipos de dados agregados" para obter mais informações.

Os comentários no ziplist.c são excelentes e você pode entender completamente essa estrutura de dados sem precisar ler o código.

6. Conjuntos Int

Conjuntos Int são um nome sofisticado para "Matrizes de números inteiros classificados".

No Redis, os conjuntos geralmente são implementados usando tabelas de hash. Para conjuntos pequenos, uma tabela de hash é ineficiente em termos de memória. Quando o conjunto é composto apenas por números inteiros, uma matriz geralmente é mais eficiente.

Um conjunto de int é uma matriz classificada de números inteiros. Para encontrar um elemento, um algoritmo de pesquisa binária é usado. Isso tem uma complexidade de O (log N). Adicionar novos números inteiros a essa matriz pode exigir uma realocação de memória, o que pode se tornar caro para matrizes inteiras grandes.

Como uma otimização adicional da memória, os Int Sets vêm em 3 variantes com diferentes tamanhos inteiros: 16 bits, 32 bits e 64 bits. O Redis é inteligente o suficiente para usar a variante correta, dependendo do tamanho dos elementos. Quando um novo elemento é adicionado e excede o tamanho atual, o Redis o migra automaticamente para o próximo tamanho. Se uma sequência for adicionada, o Redis converterá automaticamente o Conjunto Int em um conjunto regular baseado em Tabela Hash.

Conjuntos Int são uma troca entre CPU e Memória. Os conjuntos Int são extremamente eficientes em termos de memória e, para conjuntos pequenos, são mais rápidos que uma tabela de hash. Porém, após um certo número de elementos, o tempo de recuperação de O (log N) e o custo de realocação de memória se tornam excessivos. Com base em experimentos, o limite ideal para alternar para uma tabela de hash regular foi de 512. No entanto, você pode aumentar esse limite (diminuí-lo, não faz sentido) com base nas necessidades do seu aplicativo. Veja set-max-intset-entriesem redis.conf.

7. Zip Maps

Os Mapas Zip são dicionários achatados e armazenados em uma lista. Eles são muito semelhantes às Listas de Zip.

Os Mapas Zip foram descontinuados desde o Redis 2.6, e pequenos hashes são armazenados nas Listas de Zip. Para saber mais sobre essa codificação, consulte os comentários em zipmap.c .

O Redis armazena chaves apontando para valores. As chaves podem ter qualquer valor binário até um tamanho razoável (recomenda-se o uso de cadeias ASCII curtas para fins de legibilidade e depuração). Os valores são um dos cinco tipos de dados Redis nativos.

1.strings - uma sequência de bytes binários seguros até 512 MB

2.hashes - uma coleção de pares de valores-chave

3.lists - uma coleção de strings em ordem de inserção

4.sets - uma coleção de strings exclusivas, sem pedidos

5. sortidos - uma coleção de strings únicas ordenadas pela pontuação definida pelo usuário

Cordas

Uma sequência Redis é uma sequência de bytes.

As seqüências de caracteres no Redis são binárias seguras (o que significa que elas têm um comprimento conhecido não determinado por caracteres especiais de terminação), portanto, você pode armazenar qualquer coisa até 512 megabytes em uma sequência.

Strings são o conceito canônico de "armazenamento de valores-chave". Você tem uma chave apontando para um valor, em que chave e valor são cadeias de texto ou binárias.

Para todas as operações possíveis em strings, consulte o http://redis.io/commands/#string

Hashes

Um hash Redis é uma coleção de pares de valores-chave.

Um hash Redis contém muitos pares de valores-chave, onde cada chave e valor é uma sequência. Os hashes Redis não suportam valores complexos diretamente (ou seja, você não pode ter um campo de hash com o valor de uma lista ou conjunto ou outro hash), mas pode usar campos de hash para apontar para outros valores complexos de nível superior. A única operação especial que você pode executar em valores de campo de hash é incremento / decremento atômico do conteúdo numérico.

Você pode pensar em um hash Redis de duas maneiras: como uma representação direta de objeto e como uma maneira de armazenar muitos valores pequenos de maneira compacta.

Representações diretas de objetos são simples de entender. Os objetos têm um nome (a chave do hash) e uma coleção de chaves internas com valores. Veja o exemplo abaixo para, bem, um exemplo.

Armazenar muitos valores pequenos usando um hash é uma técnica inteligente de armazenamento de dados massiva Redis. Quando um hash possui um pequeno número de campos (~ 100), o Redis otimiza a eficiência de armazenamento e acesso de todo o hash. A otimização de armazenamento de hash pequeno da Redis gera um comportamento interessante: é mais eficiente ter 100 hashes, cada um com 100 chaves e valores internos, em vez de ter 10.000 chaves de nível superior apontando para valores de string. O uso de hashes Redis para otimizar seu armazenamento de dados dessa maneira exige uma sobrecarga adicional de programação para rastrear onde os dados terminam, mas se o armazenamento de dados for baseado principalmente em cadeia, você poderá economizar muita sobrecarga de memória usando esse truque estranho.

Para todas as operações possíveis em hashes, consulte os documentos de hash

Listas

As listas Redis funcionam como listas vinculadas.

Você pode inserir, excluir e percorrer listas a partir da cabeça ou da cauda de uma lista.

Use as listas quando precisar manter os valores na ordem em que foram inseridos. (O Redis oferece a opção de inserir em qualquer posição da lista arbitrária, se necessário, mas o desempenho da inserção será prejudicado se você inserir longe da sua posição inicial.)

As listas Redis são frequentemente usadas como filas de produtores / consumidores. Insira itens em uma lista e, em seguida, pop itens da lista. O que acontece se seus consumidores tentarem sair de uma lista sem elementos? Você pode pedir ao Redis para aguardar a exibição de um elemento e devolvê-lo imediatamente quando for adicionado. Isso transforma o Redis em um sistema de fila de mensagens / evento / trabalho / tarefa / notificação em tempo real.

Você pode remover elementos atomicamente de cada extremidade de uma lista, permitindo que qualquer lista seja tratada como uma pilha ou uma fila.

Você também pode manter listas de tamanho fixo (coleções limitadas) cortando sua lista para um tamanho específico após cada inserção.

Para todas as operações possíveis nas listas, consulte os documentos da lista

Conjuntos

Os conjuntos Redis são, bem, conjuntos.

Um conjunto Redis contém seqüências de caracteres Redis não ordenadas exclusivas, onde cada sequência existe apenas uma vez por conjunto. Se você adicionar o mesmo elemento dez vezes a um conjunto, ele será exibido apenas uma vez. Os conjuntos são ótimos para garantir preguiçosamente que algo existe pelo menos uma vez sem se preocupar com elementos duplicados acumulando e desperdiçando espaço. Você pode adicionar a mesma sequência quantas vezes quiser, sem precisar verificar se ela já existe.

Os conjuntos são rápidos para verificação, inserção e exclusão de membros no conjunto.

Os conjuntos têm operações eficientes de conjuntos, como seria de esperar. Você pode obter a união, interseção e diferença de vários conjuntos ao mesmo tempo. Os resultados podem ser retornados ao chamador ou os resultados podem ser armazenados em um novo conjunto para uso posterior.

Os conjuntos têm acesso a tempo constante para verificações de associação (ao contrário das listas), e o Redis ainda possui remoção e retorno aleatórios convenientes de membros ("retire um elemento aleatório do conjunto") ou membros aleatórios retornando sem substituição ("dê-me 30 usuários únicos aleatórios" ") ou com substituição (" dê-me 7 cartões, mas após cada seleção, coloque o cartão de volta para que possa ser amostrado novamente ").

Para todas as operações possíveis em conjuntos, consulte os documentos de conjuntos .

Conjuntos classificados

Os conjuntos classificados Redis são conjuntos com uma ordem definida pelo usuário.

Para simplificar, você pode pensar em um conjunto classificado como uma árvore binária com elementos exclusivos. (Os conjuntos classificados Redis são, na verdade, ignorar listas .) A ordem de classificação dos elementos é definida pela pontuação de cada elemento.

Conjuntos classificados ainda são conjuntos. Os elementos podem aparecer apenas uma vez em um conjunto. Um elemento, para fins de exclusividade, é definido pelo conteúdo da sequência. Inserir o elemento "apple" com a classificação 3 e, em seguida, inserir o elemento "apple" com a classificação 500 resulta em um elemento "apple" com a classificação 500 no seu conjunto classificado. Os conjuntos são exclusivos apenas com base em dados, não com base em pares (pontuação, dados).

Verifique se o modelo de dados se baseia no conteúdo da sequência e não na pontuação do elemento para exclusividade. É permitido que as pontuações sejam repetidas (ou mesmo zero), mas, uma última vez, os elementos do conjunto podem existir apenas uma vez por conjunto classificado. Por exemplo, se você tentar armazenar o histórico de cada login de usuário como um conjunto classificado, fazendo com que a pontuação seja a época do login e o valor do ID do usuário, você acabará armazenando apenas a última época de login para todos os usuários. Seu conjunto aumentaria para o tamanho da sua base de usuários e não para o tamanho desejado de logins da base de usuários *.

Os elementos são adicionados ao seu conjunto com pontuações. Você pode atualizar a pontuação de qualquer elemento a qualquer momento, basta adicionar o elemento novamente com uma nova pontuação. As pontuações são representadas por pontos flutuantes duplos, para que você possa especificar a granularidade de carimbos de data / hora de alta precisão, se necessário. Vários elementos podem ter a mesma pontuação.

Você pode recuperar elementos de algumas maneiras diferentes. Como tudo está classificado, você pode solicitar elementos a partir das pontuações mais baixas. Você pode solicitar elementos começando com as pontuações mais altas ("ao contrário"). Você pode solicitar elementos por sua classificação, em ordem natural ou inversa.

Para todas as operações possíveis em conjuntos classificados, consulte os documentos dos conjuntos classificados.