Requisitos: Recentemente, vi um vídeo do algoritmo Redis Bloom no Bilibili para resolver o problema da penetração do cache, simplificando, adicionar uma camada de julgamento lógico antes de acessar o banco de dados para determinar se os dados existem e, se sim, acessar o banco de dados. Por exemplo, se um site é um sistema de notícias, as URLs dos artigos são geradas por IDs de chave primária auto-incrementáveis (formato URL example:/news-1.html), o site pode ter apenas dezenas de milhares de artigos e caches.
Originalmente:
Solicitar recurso de notícias -> Determinar se o cache existe -> Presença -> O cache retorna dados.
Solicitar recursos de notícias -> Determinar se o cache existe -> não existe -> Consultar do banco de dados -> Presente -> Cache e retornar dados.
Solicite um recurso de notícias -> Determine se o cache existe -> não existe -> Consulta do banco de dados -> Não existe -> Retorna um erro 404.
Agora:
Solicite recurso de notícias -> Algoritmo de Bloom -> Existência -> Siga a lógica original.
Solicite recurso de notícias -> algoritmo de Bloom -> não existe -> retorna um erro 404 diretamente.
BloomFilter
O algoritmo BloomFilter é um algoritmo de agendamento de big data. Em um conjunto com grande quantidade de dados, pode-se determinar com precisão que um objeto não está no conjunto; É possível julgar um objeto em um conjunto e ocupar pouco espaço. elaNão é adequado para situações que exigem alta precisão e zero erros。 O uso eficiente do espaço é alcançado sacrificando uma precisão parcial.
O algoritmo de Bloom é um método baseado emSacrificar certa precisão em troca de um algoritmo de filtragem com baixo consumo de memória, que pode realizar a filtragem, deduplicação e outras operações de uma grande quantidade de dados.
O algoritmo de Bloom é apenas um conceito abstrato e pode ser implementado de várias maneiras, e o uso do BitMap no Redis no artigo é apenas uma implementação simples.
Referência:O login do hiperlink está visível.
Introdução ao BitMap
BitMap é um bitmap, que na verdade é um array de bytes, representado em binário.Existem apenas dois números, 0 e 1, o bitmap é usar cada bit binário para armazenar ou marcar o valor correspondente a um elemento. Ele geralmente é usado para determinar se um determinado dado existe ou não, pois ele é armazenado em bits, então o próprio Bitmap economiza muito espaço de armazenamento.
Como mostrado na figura abaixo, a string é armazenada em forma binária no computador.
Tipos de dados BitMap no Redis
O tipo de dado fornecido pelo Redis é BitMap, e cada bit corresponde a dois estados: 0 e 1. Embora o armazenamento interno ainda esteja no tipo String, o Redis fornece algumas instruções para manipular diretamente o BitMap, que pode ser considerado um arranjo de bits, e o subscrito do array é o deslocamento.
Suas vantagens são:Baixa sobrecarga de memória e alta eficiênciaE a operação é simples.
Economia de espaço: Um bit é usado para representar o valor ou estado de um elemento, onde a chave é o valor do elemento correspondente. Na verdade, 8 bits podem formar um byte, então economiza espaço.
Alta eficiência: A complexidade temporal do setbit e do getbit é O(1), e a eficiência dos outros bits também é alta.
Aqui está um exemplo de uso da coleção de conjuntos e armazenamento BitMap:
| tipo de dado | Cada userid ocupa espaço | A quantidade de usuários que precisam ser armazenados | Todos ocupam a memória | | pôr | 32 bits equivale a 4 bytes (assumindo que userid usa inteiros, muitos sites na verdade usam inteiros longos) | 50,000,000 | 32 bits * 50.000.000 = 200 MB | | Mapa de bits | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
O tempo está se esticando um pouco
| | Um dia | Um mês | Um ano | | pôr | 200M | 6G | 72G | | Mapa de bits | 12,5M | 375M | 4,5G |
Após o cálculo, descobriu-se que, com o passar do tempo, a quantidade de dados a serem registrados aumentava, o contraste se tornava mais evidente, e o BitMap ocupava menos espaço do que o set.
O Redis fornece as seguintes instruções para operar o BitMap:
Documentação do comando:O login do hiperlink está visível.
Agora que você tem uma compreensão breve do algoritmo, das características e sintaxe do Bitmap do Redis, vamos usar o redis para fazer uma operação simples.
Sintaxe do SETBIT:Valor de deslocamento da chave SETBIT
Defina o artigo id:9, 10, 156 para 1, e o comando é o seguinte:
Sintaxe GETBIT: Deslocamento de chave GETBIT
Para determinar se id: 10 ou 11 existe, o comando é o seguinte:
.NET/C# manipula o tipo BitMap de Redis
Aprendemos sobre vários comandos BitMap no redis e como operá-los programaticamente. Crie um novo projeto de console .NET 3.1, consulte o pacote StackExchange.Redis e use o seguinte comando:
O código-fonte é o seguinte:
Existem muitos outros cenários de aplicação bitmap para Redis, como segue:
- Ele pode ser usado como um filtro de Bloom simples para determinar se um usuário realizou certas ações.
- Estatísticas de atividade diária dos usuários, atividade mensal e taxa de retenção
- Entenda as estatísticas do número de lançamentos de usuários
- Presença de usuários online e estatísticas de pessoas
(Fim)
|
Publicado em 02/01/2023 17:37:01
|
|
|
|
Senhorio|
Publicado em 02/01/2023 17:41:56
|
Publicado em 02/01/2023 20:42:47
|
