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

Estoy tratando de responder dos preguntas en una lista definitiva:

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

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

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

Oh, he visto este artículo, entre otros, hasta ahora:

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

Voy a tratar de responder a su pregunta, pero voy a empezar con algo que puede parecer extraño al principio: si no está interesado en partes internas Redis usted no debe preocuparse acerca de cómo se implementan tipos de datos internos. Esto es por una razón simple: para cada operación de 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 según los datos, la mejor manera de obtener estas últimas cifras es haciendo algunas pruebas triviales del mundo real).

Pero como usted preguntó, aquí está la implementación subyacente de cada tipo de datos Redis.

• Las cadenas se implementan utilizando una biblioteca de cadenas dinámicas C para que no paguemos (asintóticamente hablando) las asignaciones en las operaciones de agregar. De esta manera tenemos O (N) anexa, por ejemplo, en lugar de tener un comportamiento cuadrático.
• Las listas se implementan con listas vinculadas.
• Los 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 los diferentes tipos, pero tiene la característica de que es un bloque de datos compacto que a menudo obliga a un escaneo O (N) para cada operación. Dado que usamos este formato solo para objetos pequeños, esto no es un problema; escanear un pequeño blob O (N) no tiene memoria caché, por lo que prácticamente hablando es muy rápido, y cuando hay demasiados elementos, la codificación cambia automáticamente a la codificación nativa (lista vinculada, hash, etc.).

Pero su pregunta no era solo sobre aspectos internos, su punto era ¿Qué tipo usar 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, y así sucesivamente.

Una cadena de Redis es una buena idea en todos los escenarios obvios en los que desea almacenar una página HTML, pero también cuando desea evitar la conversión de sus datos ya codificados. Entonces, 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 utilizando scripts Lua.

Otro uso interesante de las cadenas son los mapas 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 toque 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). Entonces, los buenos usos de las listas son colas y pilas simples, o procesar elementos en un bucle usando RPOPLPUSH con el mismo origen y destino para "rotar" un anillo de elementos.

Las listas también son buenas cuando queremos crear una colección limitada de N ítems donde usualmente accedemos solo a los ítems superiores o inferiores, o cuando N es pequeño.

Conjuntos

Los conjuntos son una recopilación de datos desordenada, por lo que son buenos cada vez que tiene 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 sobre los conjuntos es el soporte para mirar o reventar elementos aleatorios (comandos SRANDMEMBER y SPOP).

Los conjuntos también son buenos para representar relaciones, por ejemplo, "¿Qué son 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 están codificados 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 se pueden incrementar atómicamente usando HINCRBY. Cuando tiene objetos como usuarios, publicaciones de blog o algún otro tipo de elemento , los hashes son probablemente el camino a seguir si no desea usar su propia codificación como JSON o similar.

Sin embargo, tenga en cuenta que Redis codifica los hashes pequeños de manera muy eficiente, y puede pedirle a Redis que OBTENGA, CONFIGURE o incremente atómicamente campos individuales de una manera muy rápida.

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

Conjuntos ordenados

Los conjuntos ordenados son las únicas otras estructuras de datos, además de las listas, para mantener los elementos ordenados . Puedes hacer varias cosas interesantes con conjuntos ordenados. Por ejemplo, puede tener todo tipo de listas Top Something en su aplicación web. Usuarios principales por puntuación, publicaciones principales por páginas vistas, lo que sea superior, 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 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 prioritarias.

Los conjuntos ordenados son como listas más potentes en las que insertar, eliminar u obtener rangos desde el medio 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 alguna información en esta publicación, 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.

Perdón por los errores tipográficos, aquí es medianoche y estoy 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 que las compensaciones de la memoria de CPU v / s. También le ayuda a modelar sus datos de manera eficiente.

Internamente, Redis utiliza las siguientes estructuras de datos:

1. Cuerda
2. Diccionario
3. Lista doblemente vinculada
4. Saltar lista
5. Lista Zip
6. Conjuntos int
7. Mapas Zip (en desuso a favor de la lista zip desde Redis 2.6)

Para encontrar la codificación que utiliza una clave determinada, utilice el comando object encoding <key>.

1. Cuerdas

En Redis, las cadenas se denominan cadenas dinámicas simples o SDS . Es un contenedor más pequeño char *que 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 de Redis son seguras binarias. 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:

1. Una cadena de caracteres que puede almacenar texto. Ver los comandos SET y GET .
2. Una matriz de bytes que puede almacenar datos binarios.
3. Un longque puede almacenar números. Consulte los comandos INCR , DECR , INCRBY y DECRBY .
4. Un Array (de chars, ints, longso cualquier otro tipo de datos) que puede permitir el acceso aleatorio eficiente. Vea los comandos SETRANGE y GETRANGE .
5. Una matriz de bits que le permite establecer u obtener bits individuales. Vea los comandos SETBIT y GETBIT .
6. Un bloque de memoria que puede usar para construir otras estructuras de datos. Esto se utiliza internamente para crear listas zip e intsets, que son estructuras de datos compactas y eficientes en memoria para un pequeño número de elementos. Más sobre esto a continuación.

2. Diccionario

Redis usa un Diccionario para lo siguiente:

1. Para asignar una clave a su valor asociado, donde el valor puede ser una cadena, hash, conjunto, conjunto ordenado o lista.
2. Para asignar una clave a su marca de tiempo de caducidad.
3. Para implementar tipos de datos Hash, Set y Sorted Set.
4. Para asignar comandos de Redis a las funciones que manejan esos comandos.
5. 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 de hash . En lugar de explicar la implementación, solo explicaré las cosas específicas de Redis:

1. Los diccionarios usan una estructura llamada dictTypepara extender 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 claves, c) destructor de claves yd) destructor de valores.
2. 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 . Consulte esta pregunta para obtener una explicación del algoritmo hash djb2 ).
3. Redis utiliza Hashing incremental, también conocido como cambio de tamaño incremental . El diccionario tiene dos tablas hash. Cada vez que se toca el diccionario , se migra un depósito de la primera tabla hash (más pequeña) a la segunda. De esta manera, Redis evita una costosa operación de cambio de tamaño.

La Setestructura de datos utiliza un diccionario para garantizar que no haya duplicados. El Sorted Setutiliza un diccionario para asignar un elemento a su puntuación, que es la razón por Zscore es un O (1) operación.

3. Listas doblemente vinculadas

El listtipo de datos se implementa utilizando Listas Doblemente Vinculadas . La implementación de Redis es directamente del libro de texto del algoritmo. El único cambio es que Redis almacena la longitud en la estructura de datos de la lista. Esto asegura que LLEN tenga una complejidad O (1).

4. Saltar listas

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

Los conjuntos ordenados usan una lista de saltos y un diccionario. El diccionario almacena la puntuación de cada elemento.

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

1. Redis permite puntajes duplicados. Si dos nodos tienen la misma puntuación, se ordenan por orden lexicográfico .
2. Cada nodo tiene un puntero hacia atrás en el nivel 0. Esto le permite recorrer elementos en orden inverso a la puntuación.

5. Lista postal

Una Lista Zip es como una lista doblemente vinculada, 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) y, por lo tanto, para listas pequeñas, una lista doblemente vinculada 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 hacia adelante y hacia atrás. Dado que los datos se almacenan en línea, no necesitamos un puntero de datos.

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

Con Zip Lists, tiene el poder de hacer una compensación entre la CPU y la memoria. Las Listas Zip son eficientes en cuanto a memoria, pero usan más CPU que una lista vinculada (o tabla Hash / Lista de Saltos). Encontrar un elemento en la lista zip es O (n). Insertar un nuevo elemento requiere reasignar memoria. Debido a esto, Redis usa esta codificación solo para pequeñas listas, hashes y conjuntos ordenados. Puede modificar este comportamiento alterando los valores de <datatype>-max-ziplist-entriesy <datatype>-max-ziplist-value>en redis.conf. Consulte Redis Memory Optimization, sección "Codificación especial de tipos de datos agregados pequeños" 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 int son un nombre elegante para "matrices enteras ordenadas".

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

Un Int Set es un conjunto ordenado de enteros. Para encontrar un elemento se utiliza un algoritmo de búsqueda binario . 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 grandes matrices de enteros.

Como una optimización adicional de la memoria, los Conjuntos Int 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 según el tamaño de los elementos. Cuando se agrega un nuevo elemento y excede el tamaño actual, Redis lo migra automáticamente al siguiente tamaño. Si se agrega una cadena, Redis convierte automáticamente el conjunto Int en un conjunto basado en una tabla hash normal.

Los Conjuntos Int son una compensación entre CPU y Memoria Los Conjuntos Int son extremadamente eficientes en memoria, y para 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 de O (log N) y el costo de reasignación de memoria se vuelven demasiado. Según los experimentos, se encontró que el umbral óptimo para cambiar a una tabla hash regular es 512. Sin embargo, puede aumentar este umbral (disminuirlo no tiene sentido) en función de las necesidades de su aplicación. Ver set-max-intset-entriesen redis.conf.

7. Mapas Zip

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

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

Redis almacena claves que apuntan a valores. Las claves pueden tener cualquier valor binario hasta un tamaño razonable (se recomienda el uso de cadenas ASCII cortas para fines de lectura y depuración). Los valores son uno de los cinco tipos de datos nativos de Redis.

1.cadenas: una secuencia de bytes seguros binarios 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 ordenar

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 binarias seguras (lo que significa que tienen una longitud conocida no determinada por ningún carácter especial de terminación), por lo que puede almacenar cualquier cosa hasta 512 megabytes en una cadena.

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

Para todas las operaciones posibles en cadenas, consulte 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 (es decir, no puede tener un campo hash que tenga un valor de una lista o conjunto u otro hash), pero puede usar campos hash para apuntar a otros valores complejos de nivel superior. La única operación especial que puede realizar en valores de campo hash es el incremento / disminución atómica de contenido numérico.

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

Las representaciones directas de objetos son simples de entender. Los objetos tienen un nombre (la clave del hash) y una colección de claves internas con valores. Vea el siguiente ejemplo 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 una pequeña cantidad 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 plantea un comportamiento interesante: es más eficiente tener 100 hash 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 hashes 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 con este truco extraño.

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

Liza

Las listas de Redis actúan como listas vinculadas.

Puede insertar, eliminar y recorrer listas desde el encabezado o el final de una lista.

Use 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 rendimiento de inserción se degradará si inserta lejos de su posición inicial).

Las listas de Redis a menudo se usan como colas de productor / consumidor. Inserte elementos en una lista y luego extraiga elementos de la lista. ¿Qué sucede si sus consumidores intentan salir de una lista sin elementos? Puede pedirle a Redis que espere a que aparezca un elemento y que se lo devuelva inmediatamente cuando se agregue. Esto convierte a Redis en un sistema de cola / evento / trabajo / tarea / notificación en tiempo real.

Puede eliminar atómicamente elementos de cualquier extremo de una lista, permitiendo que cualquier lista sea tratada 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, consulte los documentos de listas

Conjuntos

Los conjuntos de Redis son, bueno, conjuntos.

Un conjunto de Redis contiene cadenas de Redis desordenadas únicas donde cada cadena solo existe una vez por conjunto. Si agrega el mismo elemento diez veces a un conjunto, solo aparecerá una vez. Los conjuntos son excelentes para garantizar 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 era 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 pueden almacenarse en un nuevo conjunto para su uso posterior.

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

Para todas las operaciones posibles en conjuntos, consulte los documentos de 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 clasificación de los elementos está definido 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, para propósitos de unicidad, se define por su contenido de cadena. Insertar el elemento "manzana" con la puntuación de clasificación 3, luego insertar el elemento "manzana" con la puntuación de clasificación 500 da como resultado un elemento "manzana" con la puntuación de clasificación 500 en su conjunto ordenado. Los conjuntos solo son únicos según los datos, no según los pares (puntuación, datos).

Asegúrese de que su modelo de datos se base en el contenido de la cadena y no en la puntuación del elemento por su singularidad. Las puntuaciones se pueden repetir (o incluso cero), pero, por última vez, los elementos del conjunto 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 de la identificación del usuario, terminará almacenando solo la última época de inicio de sesión para todos sus usuarios. Su conjunto crecería al tamaño de su base de usuarios y no al tamaño deseado de los inicios de sesión de la base de usuarios *.

Los elementos se agregan a su conjunto con puntajes. Puede actualizar el puntaje de cualquier elemento en cualquier momento, simplemente agregue el elemento nuevamente con un nuevo puntaje. Las puntuaciones se representan mediante dobles puntos de coma flotante, por lo que puede especificar la granularidad de las marcas de tiempo de alta precisión si es necesario. Varios elementos pueden tener el mismo puntaje.

Puede recuperar elementos de diferentes maneras. Como todo está ordenado, puede solicitar elementos que comiencen con los puntajes más bajos. Puede solicitar elementos que comiencen con los puntajes más altos ("en reversa"). 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.