algorithm - query - redis type

¿Cuáles son las estructuras de datos subyacentes utilizadas para Redis? (3)

Estoy tratando de responder dos preguntas en una lista definitiva:

¿Cuáles son las estructuras de datos subyacentes utilizadas para Redis?
¿Y cuáles son las principales ventajas / desventajas / casos de uso para cada tipo?

Entonces, he leído que las listas de Redis están implementadas con listas enlazadas. Pero para otros tipos, no puedo desenterrar ninguna información. Además, si alguien se tropezara con esta pregunta y no tuviera un resumen de alto nivel de las ventajas y desventajas de modificar o acceder a diferentes estructuras de datos, tendría una lista completa de cuándo utilizar mejor los tipos específicos para hacer referencia también.

Específicamente, estoy buscando delinear todos los tipos: cadena, lista, conjunto, zset y hash.

Oh, he visto estos artículos, entre otros, hasta ahora:

Intentaré responder a su pregunta, pero comenzaré por algo que puede parecer extraño al principio: si no está interesado en los internos de Redis , no debería preocuparse por cómo se implementan los tipos de datos internamente. Esto es por una razón simple: para cada operación Redis encontrará la complejidad del tiempo en la documentación y, si tiene el conjunto de operaciones y la complejidad del tiempo, lo único que necesita es alguna pista sobre el uso de la memoria (y porque hacemos muchas optimizaciones que pueden variar dependiendo de los datos, la mejor manera de obtener estas últimas cifras es hacer algunas pruebas reales triviales).

Pero desde que lo pidió, aquí está la implementación subyacente de cada tipo de datos de Redis.

Las cadenas se implementan utilizando una biblioteca de cadenas dinámica en C para que no paguemos (de forma asintótica) las asignaciones en las operaciones de adición. De esta manera, tenemos apéndices O (N), por ejemplo, en lugar de tener un comportamiento cuadrático.
Las listas se implementan con listas enlazadas.
Conjuntos y Hashes se implementan con tablas hash.
Los conjuntos ordenados se implementan con listas de omisión (un tipo peculiar de árboles equilibrados).

Pero cuando las listas, los conjuntos y los conjuntos ordenados son pequeños en número de elementos y tamaño de los valores más grandes, se utiliza una codificación diferente, mucho más compacta. Esta codificación difiere para diferentes tipos, pero tiene la característica de que es un blob compacto de datos que a menudo obliga a una exploración O (N) para cada operación. Ya que usamos este formato solo para objetos pequeños, esto no es un problema; escanear un pequeño O (N) blob es un olvido de la memoria caché, por lo que prácticamente es muy rápido, y cuando hay demasiados elementos, la codificación se cambia automáticamente a la codificación nativa (lista enlazada, hash, etc.).

Pero su pregunta no era realmente sobre aspectos internos, su punto era ¿Qué tipo de uso utilizar para lograr qué? .

Instrumentos de cuerda

Este es el tipo base de todos los tipos. Es uno de los cuatro tipos, pero también es el tipo base de los tipos complejos, porque una Lista es una lista de cadenas, un Conjunto es un conjunto de cadenas, etc.

Una cadena Redis es una buena idea en todos los escenarios obvios en los que desea almacenar una página HTML, pero también cuando quiere evitar convertir sus datos ya codificados. Así, por ejemplo, si tiene JSON o MessagePack, puede almacenar objetos como cadenas. En Redis 2.6, incluso puede manipular este tipo de servidor de objetos del lado usando scripts Lua.

Otro uso interesante de las cadenas es el mapa de bits y, en general, las matrices de bytes de acceso aleatorio, ya que Redis exporta comandos para acceder a rangos aleatorios de bytes, o incluso bits individuales. Por ejemplo, consulte esta buena publicación de blog: Métricas rápidas y fáciles en tiempo real con Redis .

Liza

Las listas son buenas cuando es probable que toques solo los extremos de la lista: cerca de la cola o cerca de la cabeza. Las listas no son muy buenas para paginar cosas, porque el acceso aleatorio es lento, O (N). Por lo tanto, los buenos usos de las listas son colas y pilas simples, o el procesamiento de elementos en un bucle utilizando RPOPLPUSH con el mismo origen y destino para "rotar" un anillo de elementos.

Las listas también son buenas cuando solo queremos crear una colección con un límite de N elementos donde normalmente accedemos solo a los elementos superiores o inferiores, o cuando N es pequeño.

Conjuntos

Los conjuntos son una recopilación de datos no ordenada, por lo que son buenos cada vez que tienes una recopilación de elementos y es muy importante verificar la existencia o el tamaño de la recopilación de una manera muy rápida. Otra cosa interesante acerca de los conjuntos es el soporte para ver o sacar elementos aleatorios (comandos SRANDMEMBER y SPOP).

Los conjuntos también son buenos para representar relaciones, por ejemplo, "¿Qué son los amigos del usuario X?" Etcétera. Pero otras buenas estructuras de datos para este tipo de cosas son conjuntos ordenados como veremos.

Los conjuntos admiten operaciones complejas como intersecciones, uniones, etc., por lo que esta es una buena estructura de datos para usar Redis de manera "computacional", cuando tiene datos y desea realizar transformaciones en esos datos para obtener algún resultado.

Los conjuntos pequeños se codifican de una manera muy eficiente.

Hashes

Los hashes son la estructura de datos perfecta para representar objetos, compuestos de campos y valores. Los campos de hashes también pueden incrementarse atómicamente usando HINCRBY. Cuando tiene objetos como usuarios, publicaciones de blog o algún otro tipo de elemento , es probable que los hashes sean el camino a seguir si no desea utilizar su propia codificación como JSON o similar.

Sin embargo, tenga en cuenta que los hashes pequeños están codificados de manera muy eficiente por Redis, y puede pedirle a Redis que GET, SET o aumente campos individuales de forma muy rápida.

Los hashes también pueden usarse para representar estructuras de datos vinculadas, utilizando referencias. Por ejemplo, verifique la implementación de lamernews.com de los comentarios.

Conjuntos ordenados

Los conjuntos ordenados son las únicas otras estructuras de datos, además de las listas, para mantener los elementos ordenados . Puedes hacer una serie de cosas geniales con conjuntos ordenados. Por ejemplo, puede tener todo tipo de listas Top Something en su aplicación web. Los mejores usuarios por puntuación, las principales publicaciones por páginas visitadas, los mejores, pero una sola instancia de Redis admitirá toneladas de operaciones de inserción y obtención de elementos superiores por segundo.

Los conjuntos ordenados, como los conjuntos regulares, se pueden usar para describir relaciones, pero también le permiten paginar la lista de elementos y recordar el orden. Por ejemplo, si recuerdo a los amigos del usuario X con un conjunto ordenado, puedo recordarlos fácilmente en orden de amistad aceptada.

Los conjuntos ordenados son buenos para las colas de prioridad.

Los conjuntos ordenados son como listas más poderosas donde insertar, eliminar o obtener rangos desde la mitad de la lista siempre es rápido. Pero usan más memoria y son estructuras de datos O (log (N)).

Conclusión

Espero haber proporcionado información en este post, pero es mucho mejor descargar el código fuente de lamernews desde http://github.com/antirez/lamernews y entender cómo funciona. Muchas estructuras de datos de Redis se usan dentro de Lamer News, y hay muchas pistas sobre qué usar para resolver una tarea determinada.

Disculpe los errores gramaticales, es medianoche aquí y demasiado cansado para revisar la publicación;)

La mayoría de las veces, no necesita comprender las estructuras de datos subyacentes utilizadas por Redis. Pero un poco de conocimiento lo ayuda a hacer concesiones de memoria de CPU v / s. También le ayuda a modelar sus datos de una manera eficiente.

Internamente, Redis usa las siguientes estructuras de datos:

Cuerda
Diccionario
Lista doblemente vinculada
Omitir lista
Zip List
Conjuntos Int
Zip Maps (en desuso a favor de la lista zip desde Redis 2.6)

Para encontrar la codificación utilizada por una clave en particular, use el object encoding <key> comando object encoding <key> .

1. cuerdas

En Redis, las cadenas se llaman cadenas dinámicas simples o SDS . Es una envoltura pequeña sobre un char * que le permite almacenar la longitud de la cadena y el número de bytes libres como prefijo.

Debido a que la longitud de la cadena está almacenada, strlen es una operación O (1). Además, debido a que se conoce la longitud, las cadenas Redis son binarias seguras. Es perfectamente legal que una cadena contenga el carácter nulo .

Las cadenas son la estructura de datos más versátil disponible en Redis. Una cadena es todo lo siguiente:

Una cadena de caracteres que puede almacenar texto. Ver los comandos SET y GET .
Una matriz de bytes que puede almacenar datos binarios.
Un long que puede almacenar números. Ver los DECR INCR , DECR , INCRBY y DECRBY .
Una matriz (de chars , chars , longs o cualquier otro tipo de datos) que pueda permitir un acceso aleatorio eficiente. Ver los comandos SETRANGE y GETRANGE .
Una matriz de bits que le permite establecer u obtener bits individuales. Ver los comandos SETBIT y GETBIT .
Un bloque de memoria que puede utilizar para construir otras estructuras de datos. Esto se usa internamente para construir ziplists e intsets, que son estructuras de datos compactas y eficientes en memoria para una pequeña cantidad de elementos. Más sobre esto a continuación.

2. Diccionario

Redis usa un Dictionary para lo siguiente:

Para asignar una clave a su valor asociado, donde el valor puede ser una cadena, un hash, un conjunto, un conjunto ordenado o una lista.
Para asignar una clave a su fecha y hora de caducidad.
Para implementar tipos de datos Hash, Set y Set ordenados.
Para asignar los comandos de Redis a las funciones que manejan esos comandos.
Para asignar una clave Redis a una lista de clientes que están bloqueados en esa clave. Ver BLPOP .

Los diccionarios Redis se implementan utilizando tablas hash . En lugar de explicar la implementación, solo explicaré las cosas específicas de Redis:

Los diccionarios utilizan una estructura llamada dictType para ampliar el comportamiento de una tabla hash. Esta estructura tiene punteros de función, por lo que las siguientes operaciones son extensibles: a) función hash, b) comparación de teclas, c) destructor de teclas yd) destructor de valores.
Los diccionarios usan el murmurhash2 . (Anteriormente usaban la función hash djb2 , con seed = 5381, pero luego la función hash se cambió a murmur2 . Consulta esta pregunta para obtener una explicación del algoritmo hash djb2 ).
Redis usa Hashing incremental, también conocido como cambio de tamaño incremental . El diccionario tiene dos tablas hash. Cada vez que se toca el diccionario, un grupo se migra de la primera tabla hash (más pequeña) a la segunda. De esta manera, Redis evita una operación costosa de cambio de tamaño.

La estructura de datos del Set utiliza un Diccionario para garantizar que no haya duplicados. El Sorted Set utiliza un diccionario para asignar un elemento a su puntaje, por lo que ZSCORE es una operación O (1).

3. Listas doblemente vinculadas

El tipo de datos de la list se implementa utilizando listas de enlaces dobles . La implementación de Redis es un libro de texto directamente del algoritmo. El único cambio es que Redis almacena la longitud en la estructura de datos de la lista. Esto asegura que LLEN tenga O (1) complejidad.

4. Saltar listas

Redis usa Skip Lists como la estructura de datos subyacente para los conjuntos ordenados. Wikipedia tiene una buena introducción. El papel de William Pugh Skip Lists: Una alternativa probabilística a los árboles equilibrados tiene más detalles.

Los conjuntos ordenados utilizan tanto una lista de omisión como un diccionario. El diccionario almacena la puntuación de cada elemento.

La implementación de la Lista de Saltos de Redis es diferente de la implementación estándar de las siguientes maneras:

Redis permite duplicar puntuaciones. Si dos nodos tienen la misma puntuación, se ordenan por orden lexicográfico .
Cada nodo tiene un puntero de retroceso en el nivel 0. Esto le permite atravesar elementos en orden inverso a la puntuación.

5. Lista Zip

Una Lista Zip es como una lista doblemente enlazada, excepto que no utiliza punteros y almacena los datos en línea.

Cada nodo en una lista doblemente enlazada tiene 3 punteros: un puntero hacia adelante, un puntero hacia atrás y un puntero para hacer referencia a los datos almacenados en ese nodo. Los punteros requieren memoria (8 bytes en un sistema de 64 bits), por lo que para las listas pequeñas, una lista doblemente enlazada es muy ineficiente.

Una lista Zip almacena elementos secuencialmente en una cadena Redis. Cada elemento tiene un encabezado pequeño que almacena la longitud y el tipo de datos del elemento, el desplazamiento al siguiente elemento y el desplazamiento al elemento anterior. Estas compensaciones reemplazan los punteros de avance y retroceso. Como los datos se almacenan en línea, no necesitamos un indicador de datos.

La lista Zip se usa para almacenar listas pequeñas, conjuntos ordenados y hashes. Los conjuntos [element1, score1, element2, score2, element3, score3] se aplanan en una lista como [element1, score1, element2, score2, element3, score3] y se almacenan en la Lista Zip. Los hash se aplanan en una lista como [key1, value1, key2, value2] etc.

Con las listas Zip, tiene el poder de hacer un intercambio entre la CPU y la memoria. Las listas Zip son eficientes en la memoria, pero usan más CPU que una lista vinculada (o tabla Hash / Lista de omisión). Encontrar un elemento en la lista zip es O (n). La inserción de un nuevo elemento requiere la reasignación de memoria. Debido a esto, Redis usa esta codificación solo para listas pequeñas, hashes y conjuntos ordenados. Puede modificar este comportamiento modificando los valores de <datatype>-max-ziplist-entries y <datatype>-max-ziplist-value> en redis.conf. Consulte Redis Optimización de la memoria, sección "Codificación especial de pequeños tipos de datos agregados" para obtener más información.

Los comentarios en ziplist.c son excelentes, y puede comprender esta estructura de datos completamente sin tener que leer el código.

6. Conjuntos Int.

Los conjuntos de int son un nombre elegante para "arrays de enteros ordenados".

En Redis, los conjuntos generalmente se implementan usando tablas hash. Para conjuntos pequeños, una tabla hash es ineficaz en cuanto a memoria. Cuando el conjunto se compone solo de números enteros, una matriz suele ser más eficiente.

Un conjunto de int es una matriz ordenada de enteros. Para encontrar un elemento se utiliza un algoritmo de búsqueda binaria . Esto tiene una complejidad de O (log N). Agregar nuevos enteros a esta matriz puede requerir una reasignación de memoria, lo que puede resultar costoso para las matrices de enteros grandes.

Como una optimización adicional de la memoria, los Int Sets vienen en 3 variantes con diferentes tamaños de enteros: 16 bits, 32 bits y 64 bits. Redis es lo suficientemente inteligente como para usar la variante correcta dependiendo del tamaño de los elementos. Cuando se agrega un nuevo elemento y supera el tamaño actual, Redis lo migra automáticamente al siguiente tamaño. Si se agrega una cadena, Redis convierte automáticamente el conjunto de int en un conjunto basado en tabla de hash regular.

Los conjuntos de int son una compensación entre la CPU y la memoria. Los conjuntos de int son extremadamente eficientes en memoria, y para los conjuntos pequeños son más rápidos que una tabla hash. Pero después de un cierto número de elementos, el tiempo de recuperación O (log N) y el costo de reasignar la memoria se vuelven demasiado altos. Según los experimentos, se encontró que el umbral óptimo para cambiar a una tabla hash regular es de 512. Sin embargo, puede aumentar este umbral (disminuirlo no tiene sentido) según las necesidades de su aplicación. Ver set-max-intset-entries en redis.conf.

7. Zip Maps

Los mapas Zip son diccionarios aplanados y almacenados en una lista. Son muy similares a las listas zip.

Los mapas Zip han quedado en desuso desde Redis 2.6, y los hashes pequeños se almacenan en las listas Zip. Para obtener más información sobre esta codificación, consulte los comentarios en zipmap.c .

Redis almacena claves apuntando a valores. Las claves pueden ser de cualquier valor binario hasta un tamaño razonable (se recomienda utilizar cadenas ASCII cortas para facilitar la lectura y la depuración). Los valores son uno de los cinco tipos de datos nativos de Redis.

1.strings: una secuencia de bytes binarios seguros de hasta 512 MB
2.hashes - una colección de pares de valores clave
3.listas - una colección de cadenas en orden de inserción
4.sets - una colección de cadenas únicas sin ordenamiento
5. conjuntos clasificados: una colección de cadenas únicas ordenadas por puntuación definida por el usuario

Instrumentos de cuerda

Una cadena Redis es una secuencia de bytes.

Las cadenas en Redis son seguras para archivos binarios (lo que significa que tienen una longitud conocida no determinada por ningún carácter de terminación especial), por lo que puede almacenar cualquier cosa hasta 512 megabytes en una cadena.

Las cuerdas son el concepto canónico de "almacén de valores clave". Tiene una clave que apunta a un valor, donde tanto la clave como el valor son cadenas de texto o binarias.

Para todas las operaciones posibles en cadenas, consulte la http://redis.io/commands/#string

Hashes

Un hash de Redis es una colección de pares de valores clave.

Un hash de Redis contiene muchos pares de valores clave, donde cada clave y valor es una cadena. Los hash de Redis no admiten valores complejos directamente (lo que significa que no es posible que un campo de hash tenga un valor de lista o conjunto u otro hash), pero puede usar los campos de hash para señalar otros valores complejos de nivel superior. La única operación especial que puede realizar en los valores de campo hash es el incremento / decremento atómico de los contenidos numéricos.

Puede pensar en un hash de Redis de dos maneras: como una representación directa de objetos y como una forma de almacenar muchos pequeños valores de forma compacta.

Las representaciones directas de objetos son fáciles de entender. Los objetos tienen un nombre (la clave del hash) y una colección de claves internas con valores. Vea el ejemplo a continuación para, bueno, un ejemplo.

Almacenar muchos valores pequeños utilizando un hash es una técnica inteligente de almacenamiento masivo de datos de Redis. Cuando un hash tiene un pequeño número de campos (~ 100), Redis optimiza la eficiencia de almacenamiento y acceso de todo el hash. La pequeña optimización de almacenamiento de hash de Redis genera un comportamiento interesante: es más eficiente tener 100 hashes cada uno con 100 claves y valores internos en lugar de tener 10,000 claves de nivel superior que apuntan a valores de cadena. El uso de hash de Redis para optimizar su almacenamiento de datos de esta manera requiere una sobrecarga de programación adicional para rastrear dónde terminan los datos, pero si su almacenamiento de datos se basa principalmente en cadenas, puede ahorrar mucha sobrecarga de memoria usando este truco extraño.

Para todas las operaciones posibles en hashes, vea los documentos hash

Liza

Las listas redis actúan como listas enlazadas.

Puede insertar, eliminar y atravesar listas desde la cabecera o la cola de una lista.

Utilice las listas cuando necesite mantener los valores en el orden en que se insertaron. (Redis le da la opción de insertar en cualquier posición de lista arbitraria si lo necesita, pero su desempeño de inserción se degradará si inserta lejos de su posición de inicio).

Las listas de redis se utilizan a menudo como colas de productor / consumidor. Insertar elementos en una lista y luego sacar elementos de la lista. ¿Qué sucede si sus consumidores intentan saltar de una lista sin elementos? Puedes pedirle a Redis que espere a que aparezca un elemento y te lo devuelva de inmediato cuando se agregue. Esto convierte a Redis en una cola de mensajes en tiempo real / evento / trabajo / tarea / sistema de notificación.

Puede eliminar elementos atómicamente de cualquiera de los extremos de una lista, lo que permite que cualquier lista se trate como una pila o una cola.

También puede mantener listas de longitud fija (colecciones con límite) recortando su lista a un tamaño específico después de cada inserción.

Para todas las operaciones posibles en las listas, vea la lista de documentos.

Conjuntos

Los conjuntos redis son, bueno, conjuntos.

Un conjunto Redis contiene cadenas Redis desordenadas únicas donde cada cadena solo existe una vez por conjunto. Si agrega el mismo elemento diez veces a un conjunto, solo se mostrará una vez. Los conjuntos son geniales para asegurar perezosamente que algo existe al menos una vez sin preocuparse por la acumulación de elementos duplicados y el desperdicio de espacio. Puede agregar la misma cadena tantas veces como desee sin necesidad de verificar si ya existe.

Los conjuntos son rápidos para la verificación de membresía, inserción y eliminación de miembros en el conjunto.

Los conjuntos tienen operaciones de conjuntos eficientes, como es de esperar. Puede tomar la unión, la intersección y la diferencia de varios conjuntos a la vez. Los resultados pueden devolverse a la persona que llama o los resultados pueden almacenarse en un nuevo conjunto para su uso posterior.

Los conjuntos tienen acceso de tiempo constante para las verificaciones de membresía (a diferencia de las listas), y Redis incluso tiene la eliminación y devolución conveniente de miembros aleatorios ("saca un elemento aleatorio del conjunto") o miembros aleatorios que regresan sin reemplazo ("dame 30 usuarios únicos aleatorios ") o con reemplazo (" dame 7 tarjetas, pero después de cada selección, vuelve a colocar la tarjeta para que pueda ser probada nuevamente ").

Para todas las operaciones posibles en los conjuntos, consulte la documentación de los conjuntos .

Conjuntos ordenados

Los conjuntos ordenados de Redis son conjuntos con un orden definido por el usuario.

Para simplificar, puede pensar en un conjunto ordenado como un árbol binario con elementos únicos. (Los conjuntos ordenados de Redis son en realidad listas de omisión ). El orden de los elementos se define por la puntuación de cada elemento.

Los conjuntos ordenados siguen siendo conjuntos. Los elementos solo pueden aparecer una vez en un conjunto. Un elemento, por razones de singularidad, se define por el contenido de su cadena. Insertar el elemento "manzana" con el puntaje de clasificación 3, luego insertar el elemento "manzana" con el puntaje de clasificación 500 da como resultado un elemento "manzana" con el puntaje de clasificación 500 en su conjunto clasificado. Los conjuntos solo son únicos en base a los datos, no en base a los pares (puntaje, datos).

Asegúrese de que su modelo de datos se basa en el contenido de la cadena y no en la puntuación del elemento para la unicidad. Se permite que las puntuaciones se repitan (o incluso cero), pero, por última vez, los elementos establecidos solo pueden existir una vez por conjunto ordenado. Por ejemplo, si intenta almacenar el historial de cada inicio de sesión de usuario como un conjunto ordenado, haciendo que la puntuación sea la época del inicio de sesión y el valor del ID de usuario, terminará almacenando solo la última época de inicio de sesión para todos sus usuarios. Su conjunto crecerá hasta el tamaño de su base de usuarios y no el tamaño deseado de los inicios de sesión de userbase *.

Los elementos se añaden a su conjunto con las puntuaciones. Puede actualizar el puntaje de cualquier elemento en cualquier momento, solo agregue el elemento nuevamente con un nuevo puntaje. Las puntuaciones están representadas por dobles de punto flotante, por lo que puede especificar la granularidad de las marcas de tiempo de alta precisión si es necesario. Múltiples elementos pueden tener la misma puntuación.

Puede recuperar elementos de diferentes maneras. Dado que todo está ordenado, puede solicitar elementos que comiencen en los puntajes más bajos. Puede solicitar elementos a partir de los puntajes más altos ("a la inversa"). Puede solicitar elementos por su puntuación de clasificación, ya sea en orden natural o inverso.

Para todas las operaciones posibles en conjuntos ordenados, consulte los documentos de conjuntos ordenados.