Requisitos: Recientemente vi un vídeo del algoritmo Redis Bloom en Bilibili para resolver el problema de la penetración de caché; en pocas palabras, añadir una capa de juicio lógico antes de acceder a la base de datos para determinar si los datos existen y, de ser así, acceder a la base de datos. Por ejemplo, si un sitio web es un sistema de noticias, las URLs de los artículos se generan mediante identificadores de clave primaria auto-incrementables (formato URL example:/news-1.html), el sitio web puede tener solo decenas de miles de artículos y cachés.
Originalmente:
Solicitar recurso de noticias -> Determinar si existe la caché -> Presencia -> La caché devuelve datos.
Solicitar recursos de noticias -> Determinar si la caché existe -> no existe -> Consultar desde la base de datos -> Presente -> Caché y devolver datos.
Solicitar un recurso de noticias -> Determinar si la caché existe -> no existe -> Consulta desde la base de datos -> No existe -> Devuelve un error 404.
Ahora mismo:
Solicitar recurso de noticias -> Algoritmo de Bloom -> Existencia -> Sigue la lógica original.
Solicita noticias -> algoritmo de Bloom -> no existe -> devuelve un error 404 directamente.
BloomFilter
El algoritmo BloomFilter es un algoritmo de planificación de big data. En un conjunto con una gran cantidad de datos, se puede determinar con precisión que un objeto no está en el conjunto; Es posible juzgar un objeto dentro de un conjunto y ocupar poco espacio. esoNo es adecuado para situaciones que requieren alta precisión y cero errores。 El uso eficiente del espacio se logra sacrificando una precisión parcial.
El algoritmo de Bloom es un método basado enSacrificar cierta precisión a cambio de un algoritmo de filtrado con bajo consumo de memoria, que puede realizar el filtrado, la deduplicación y otras operaciones de una gran cantidad de datos.
El algoritmo de Bloom es solo un concepto abstracto y puede implementarse de muchas maneras, y el uso de BitMap en Redis en el artículo es simplemente una implementación sencilla.
Referencia:El inicio de sesión del hipervínculo es visible.
Introducción al mapa de bits
BitMap es un mapa de bits, que en realidad es un array de bytes, representado en binario.Solo hay dos números, 0 y 1, el mapa de bits consiste en usar cada bit binario para almacenar o marcar el valor correspondiente a un elemento. Normalmente se utiliza para determinar si ciertos datos existen o no, porque se almacenan en bits, por lo que el propio mapa de bits ahorrará mucho espacio de almacenamiento.
Como se muestra en la figura siguiente, la cadena se almacena en forma binaria en el ordenador.
Tipos de datos BitMap en Redis
El tipo de dato proporcionado por Redis es BitMap, y cada bit corresponde a dos estados: 0 y 1. Aunque el almacenamiento interno sigue siendo del tipo String, Redis proporciona algunas instrucciones para manipular directamente BitMap, que pueden considerarse como un array de bits, y el subíndice del array es el desplazamiento.
Sus ventajas son:Baja sobrecarga de memoria y alta eficienciaY la operación es sencilla.
Ahorro de espacio: Se utiliza un bit para representar el valor o estado de un elemento, donde la clave es el valor del elemento correspondiente. De hecho, 8 bits pueden constituir un byte, así que ahorra espacio.
Alta eficiencia: La complejidad temporal del setbit y del getbit es O(1), y la eficiencia de otros bits también es alta.
Aquí tienes un ejemplo de cómo usar la colección de conjuntos y el almacenamiento en mapa de bits:
| tipo de dato | Cada userid ocupa espacio | La cantidad de usuarios que necesitan almacenarse | Todos ocupan memoria | | poner | 32 bits son 4 bytes (suponiendo que userid use enteros, muchas páginas web en realidad usan enteros largos) | 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 |
El tiempo se está estirando un poco
| | Un día | Un mes | Un año | | poner | 200M | 6G | 72G | | Mapa de bits | 12,5M | 375M | 4,5G |
Tras el cálculo, se descubrió que a medida que avanzaba el tiempo, la cantidad de datos a registrar aumentaba y el contraste se hacía más evidente, y BitMap ocupaba menos espacio que el set.
Redis proporciona las siguientes instrucciones para operar BitMap:
Documentación de mando:El inicio de sesión del hipervínculo es visible.
Ahora que tienes una breve comprensión del algoritmo y de las características y sintaxis del mapa de bits de Redis, usemos redis para hacer una operación sencilla.
Sintaxis de SETBIT:Valor de desplazamiento clave de SETBIT
Establece el artículo id:9, 10, 156 a 1, y el comando es el siguiente:
Sintaxis GETBIT: Desplazamiento de clave GETBIT
Para determinar si existe id: 10 o 11, el comando es el siguiente:
.NET/C# manipula el tipo BitMap de Redis
Aprendimos sobre varios comandos BitMap en redis y cómo operarlos programáticamente. Crea un nuevo proyecto de consola .NET 3.1, consulta el paquete StackExchange.Redis y utiliza el siguiente comando:
El código fuente es el siguiente:
Existen muchos otros escenarios de aplicación en mapa de bits para Redis, como sigue:
- Puede utilizarse como un filtro de Bloom simple para determinar si un usuario ha realizado ciertas acciones.
- Estadísticas de actividad diaria de los usuarios, actividad mensual y tasa de retención
- Ten en cuenta las estadísticas del número de lanzamientos de usuarios
- Presencia de usuarios en línea y estadísticas de personas
(Fin)
|
Publicado en 2/1/2023 17:37:01
|
|
|
|
Propietario|
Publicado en 2/1/2023 17:41:56
|
Publicado en 2/1/2023 20:42:47
|
