Redis
 sql >> Base de Dados >  >> NoSQL >> Redis

Introdução às estruturas de dados do Redis:bitmaps

Bitmaps (também chamados de matrizes de bits, vetores de bits etc.) representação. É uma estrutura de dados muito popular sempre que o espaço de memória é escasso:kernels do sistema operacional (páginas de memória, inodes etc.), imagens digitais etc.


O Redis, sendo um servidor de estrutura de dados em memória, oferece suporte para operações de manipulação de bits. No entanto, não há uma estrutura de dados especial para Bitmaps no Redis. Em vez disso, as operações de nível de bits são suportadas na estrutura básica do Redis:Strings. Agora, o comprimento máximo das strings do Redis é de 512 MB. Assim, o maior domínio que o Redis pode mapear como Bitmap é 2 (512 MB =2 bytes =2 bits).

As operações relacionadas a bits no Redis são de dois tipos:Tempo constante (O(1)) ex. operações para obter/configurar um determinado bit e operações que são O(N) que basicamente operam em um grupo de bits. N nestes casos é o comprimento de bits que a operação precisará trabalhar. Vejamos alguns exemplos.

Comandos

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

Além de operadores que trabalham na própria chave, o BITOP operador é usado para operações lógicas bit a bit entre várias chaves. 

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

Internos

Como as operações de bitmap não possuem uma estrutura de dados própria, não há uma estrutura de dados especial para descrever. As próprias strings do Redis são implementadas como uma string binária segura. A estrutura de dados de string do Redis é chamada internamente de Simple Dynamic String (SDS). É essencialmente um char [] nativo com algumas informações adicionais de contabilidade. Os detalhes de implementação podem ser encontrados aqui.

A implementação das funções de bitmap está no arquivo bitops.c .

P.S.:Dada a importância dos algoritmos de manipulação de bits para o SO crítico e a funcionalidade gráfica, a maioria das arquiteturas fornece instruções especiais para tais operações. Um bom lugar para ler vários algoritmos aritméticos de computador interessantes é o clássico atemporal Hacker's Delight.

Aplicativos

Este popular blog do GetSpool é um ótimo exemplo de uso de bitmap para análise em tempo real em um grande conjunto de dados. Também é um exemplo do caso de uso clássico de um bitmap:armazenar informações booleanas de um domínio extremamente grande em um espaço (relativamente) pequeno, mantendo um desempenho decente.

O tamanho geralmente é uma preocupação para bitmaps realmente grandes, pois as operações mais úteis sobre ele são O(N). Para evitar trabalhar com chaves enormes, a documentação do Redis recomenda dividir chaves enormes em várias chaves menores. O desempenho de BITCOUNT permanece aceitável até que a chave fique grande. Nesse ponto, a recomendação é dividir as chaves ou usar os argumentos de intervalo para consultar de forma incremental. A recomendação para lidar com operações BITOP lentas é executá-lo em escravos. Portanto, em geral, faz sentido lidar com chaves de tamanho moderado e planejar o crescimento potencial futuro dividindo as chaves em várias chaves.

 Conjuntos do Redis x bitmap do Redis

A natureza da funcionalidade fornecida pelo Redis Sets e as operações de bitmap é semelhante. Portanto, muitas vezes é confuso qual das duas abordagens é melhor. Bem, isso realmente depende da natureza exata do caso de uso. Obviamente, essa discussão é válida apenas para o tipo de operações que os conjuntos e o bitmap podem realizar.

Os Conjuntos Redis são em geral eficientes e bem dimensionados e devem ser a estrutura de dados de escolha até que seu tamanho se torne insustentável. Os Conjuntos Redis também são mais fáceis de gerenciar, programar e depurar funcionaria bem para a maioria dos aplicativos. A facilidade de uso de Sets não deve ser subestimada:o código que manipula bitmaps geralmente é difícil de ler, entender, depurar e manter. Mesmo quando o domínio é muito grande, os conjuntos ainda podem ser apropriados. Por exemplo se um aplicativo se destina a rastrear visitas diárias a um site de comércio eletrônico popular, os resultados ainda podem se encaixar bem em um conjunto, pois normalmente apenas 5 a 10% de toda a base de usuários visitará o site diariamente. Isso obviamente muda para um site onde se espera que 60% de toda a base de usuários faça login diariamente. Em seguida, os bitmaps se tornam mais relevantes devido ao tamanho e desempenho das operações lógicas bit a bit em um grande número de chaves. Os Conjuntos Redis também têm a vantagem distinta de não precisar mapear IDs para deslocamentos de bits. Da mesma forma, se seus valores são de um domínio maior que 2, os Conjuntos Redis devem ser mais fáceis de usar do que descobrir mecanismos para dividir o domínio para bitmap.

Análise para um MOOC

Aqui está um exemplo inventado (mas bastante real!) para um local onde se pode aplicar operações de bitmap do Redis. Digamos que você esteja executando um MOOC online muito popular no qual centenas de milhares de alunos se inscreveram. A equipe acadêmica que facilita o curso deseja um painel onde possa ver o status em tempo real do progresso dos alunos, bem como o histórico geral dos alunos matriculados. Você decide implementar isso por meio de operações de bitmap do Redis. Aqui está uma abordagem passo a passo para isso.

  1. Crie um plano para mapear entre o ID do aluno e o deslocamento de bitmap. Pode ser tão simples quanto o ID sendo o deslocamento no bitmap.
  2. Crie e preencha vários bitmaps relacionados a dados demográficos assim que o curso começar. Por exemplo alunos matriculados em outros MOOCs da mesma universidade, nível educacional, gênero etc.
  3. Agora, à medida que o curso avança, você pode criar novos bitmaps para registrar o progresso do curso. Por exemplo alunos que assistiram a todas as aulas da semana 1, alunos que concluíram todas as tarefas da semana 1 etc.
  4. Agora, criar análises em tempo real com base nessas chaves seria um exercício muito simples e pode ser feito em uma interface do usuário de arrastar e soltar. Por exemplo
  • Um professor que deseja ver quantos alunos assistiram às aulas da semana 1 (A), mas não concluíram a tarefa da semana 1 (B):Operador:BITOP. Operação:A E (NÃO B).
  • Aluno que completou todas as tarefas da semana 1 (A), semana 2 (B), semana 3 (C) e semana 4 (D):Operador:BITOP. Operação A E B E C E D. Diga, essas são as pessoas que passaram no curso.
  • Todos os alunos do sexo masculino (M) que passaram no curso (conforme calculado acima, digamos, P):Operador:BITOP. Operação:M E P.
  • Número de alunos aprovados no curso:BITCOUNT P.

Da mesma forma, qualquer número de coortes interessantes pode ser configurado como bitmaps e tais permutações são executadas neles.

Nota de rodapé

Outras postagens em nossa série de estruturas de dados Redis:

  • Conjuntos
  • Hashes
  • Conjuntos classificados