sql >> Base de Datos >  >> NoSQL >> Redis

Introducción a las estructuras de datos de Redis:mapas de bits

Los mapas de bits (también llamados arreglos de bits, vectores de bits, etc.) son la estructura de datos que aparece inmediatamente en su cabeza cuando la necesidad es mapear información booleana para un dominio enorme en un formato compacto. representación. Es una estructura de datos muy popular siempre que el espacio de memoria sea escaso:núcleos del sistema operativo (páginas de memoria, inodos, etc.), imágenes digitales, etc.

Redis, al ser un servidor de estructura de datos en memoria, brinda soporte para operaciones de manipulación de bits. Sin embargo, no existe una estructura de datos especial para mapas de bits en Redis. Más bien, las operaciones a nivel de bits se admiten en la estructura básica de Redis:cadenas. Ahora, la longitud máxima de las cadenas de Redis es de 512 MB. Por lo tanto, el dominio más grande que Redis puede asignar como mapa de bits es 2 (512 MB =2 bytes =2 bits).

Las operaciones relacionadas con bits en Redis son de dos tipos:tiempo constante (O(1)), p. operaciones para obtener/establecer un bit en particular y operaciones que son O(N) que básicamente operan en un grupo de bits. N en estos casos es la longitud de bits en los que la operación necesitará trabajar. Veamos algunos ejemplos.

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

Además de los operadores que trabajan en la clave misma, el BITOP El operador se utiliza para operaciones lógicas bit a bit entre varias claves.

# 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

Dado que las operaciones de mapa de bits no tienen una estructura de datos propia, no hay una estructura de datos especial para describir. Las propias cadenas de Redis se implementan como una cadena binaria segura. La estructura de datos de cadena de Redis se denomina internamente Cadena dinámica simple (SDS). Es esencialmente un char [] nativo con alguna información adicional de contabilidad. Los detalles de implementación se pueden encontrar aquí.

La implementación de las funciones de mapa de bits se encuentra en el archivo bitops.c .

P.D.:Dada la importancia de los algoritmos de manipulación de bits para la funcionalidad crítica del sistema operativo y los gráficos, la mayoría de las arquitecturas brindan instrucciones especiales para tales operaciones. Un buen lugar para leer sobre varios algoritmos aritméticos informáticos interesantes es el clásico atemporal Hacker's Delight.

Aplicaciones

Este popular blog de GetSpool es un gran ejemplo del uso de mapas de bits para análisis en tiempo real sobre un gran conjunto de datos. También es un ejemplo del caso de uso clásico de un mapa de bits:almacenar información booleana de un dominio extremadamente grande en un espacio (relativamente) pequeño mientras se conserva un rendimiento decente.

El tamaño suele ser una preocupación para los mapas de bits realmente grandes, ya que las operaciones más útiles sobre él son O(N). Para evitar trabajar con claves grandes, la documentación de Redis recomienda dividir las claves grandes en varias más pequeñas. El rendimiento de BITCOUNT sigue siendo aceptable hasta que la clave crece. En ese momento, la recomendación es dividir las claves o usar los argumentos de rango para consultar de forma incremental. La recomendación para lidiar con operaciones BITOP lentas es ejecutarlo en esclavos. Por lo tanto, en general, tiene sentido tratar con claves de tamaño moderado y planificar el crecimiento potencial futuro dividiendo las claves en varias claves.

 Conjuntos de Redis frente a mapas de bits de Redis

La naturaleza de la funcionalidad proporcionada por Redis Sets y las operaciones de mapa de bits es similar. Por lo tanto, a menudo es confuso cuál de los dos enfoques es mejor. Bueno, realmente depende de la naturaleza exacta del caso de uso. Obviamente, esta discusión es válida solo para el tipo de operaciones que pueden lograr tanto los conjuntos como el mapa de bits.

Los conjuntos de Redis son, en general, eficientes y se escalan bien, y deberían ser la estructura de datos elegida hasta que su tamaño se vuelva insostenible. Los conjuntos de Redis también son más fáciles de administrar, programar y depurar y funcionarían bien para la mayoría de las aplicaciones. La facilidad de uso de los conjuntos no debe subestimarse:el código que manipula mapas de bits suele ser difícil de leer, comprender, depurar y mantener. Incluso cuando el dominio es muy grande, los conjuntos pueden seguir siendo apropiados. Por ej. si una aplicación está destinada a realizar un seguimiento de las visitas diarias a un sitio de comercio electrónico popular, los resultados aún pueden encajar bien en un conjunto, ya que generalmente solo el 5-10% de la base de usuarios completa visitará el sitio diariamente. Obviamente, esto cambia para un sitio en el que se espera que el 60 % de toda la base de usuarios inicie sesión diariamente. Luego, los mapas de bits se vuelven más relevantes dado el tamaño y el rendimiento de las operaciones lógicas de bits en una gran cantidad de claves. Los conjuntos de Redis también tienen la clara ventaja de no tener que asignar ID a compensaciones de bits. Del mismo modo, si sus valores son de un dominio mayor que 2, entonces los conjuntos de Redis deben ser más fáciles de usar que descubrir mecanismos para dividir el dominio para el mapa de bits.

Analítica para un MOOC

Aquí hay un ejemplo inventado (¡pero bastante real!) de un lugar donde se pueden aplicar operaciones de mapa de bits de Redis. Digamos que está ejecutando un MOOC en línea muy popular en el que se han inscrito cientos de miles de estudiantes. El equipo académico que facilita el curso quiere un tablero donde puedan ver el estado en tiempo real del progreso de los estudiantes, así como los antecedentes generales de los estudiantes inscritos. Decide implementar esto a través de operaciones de mapa de bits de Redis. Aquí hay un enfoque paso a paso.

  1. Cree un plan para mapear entre la identificación del estudiante y el desplazamiento del mapa de bits. Podría ser tan simple como que el ID sea el desplazamiento en el mapa de bits.
  2. Cree y complete varios mapas de bits relacionados con la demografía una vez que comience el curso. Por ej. estudiantes matriculados en otros MOOC de la misma universidad, nivel educativo, género, etc.
  3. Ahora, a medida que avanza el curso, puede crear nuevos mapas de bits para registrar el progreso del curso. Por ej. estudiantes que terminaron de ver todas las conferencias de la semana 1, estudiantes que completaron todas las tareas de la semana 1, etc.
  4. Ahora, crear análisis en tiempo real basados ​​en estas claves sería un ejercicio muy simple y se puede hacer en una interfaz de usuario de arrastrar y soltar. Por ejemplo
  • Un profesor que quiere ver cuántos estudiantes vieron las conferencias de la semana 1 (A) pero no completaron la tarea de la semana 1 (B):Operador:BITOP. Operación:A Y (NO B).
  • Estudiante que completó todas las tareas para la semana 1 (A), la semana 2 (B), la semana 3 (C) y la semana 4 (D):Operador:BITOP. Operación A Y B Y C Y D. Diga, estas son las personas que aprobaron el curso.
  • Todos los estudiantes varones (M) que aprobaron el curso (como se calculó anteriormente, por ejemplo, P):Operador:BITOP. Operación:M Y P.
  • Número de alumnos que aprobaron el curso:BITCOUNT P.

Del mismo modo, se puede configurar cualquier cantidad de cohortes interesantes como mapas de bits y tales permutaciones se ejecutan en ellas.

Nota al pie

Otras publicaciones en nuestra serie de estructuras de datos de Redis:

  • Conjuntos
  • Hashes
  • Conjuntos ordenados