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

Resuelto Homer6 asked hace 12 años • 3 respuestas

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 de cada tipo?

Entonces, leí 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ía una lista completa de cuándo utilizar mejor tipos específicos para hacer referencia.

Específicamente, busco describir todos los tipos: cadena, lista, conjunto, zset y hash.

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

  • http://redis.io/topics/data-types
  • http://redis.io/topics/data-types-intro
  • http://redis.io/topics/faq
Homer6 avatar Mar 09 '12 04:03 Homer6
Aceptado

Intentaré responder a tu pregunta, pero comenzaré con algo que puede parecer extraño al principio: si no estás interesado en las partes internas de Redis, no deberías preocuparte por cómo se implementan internamente los tipos de datos. Esto se debe a una sencilla razón: para cada operación de Redis encontrará la complejidad temporal en la documentación y, si tiene el conjunto de operaciones y la complejidad temporal, 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 realizar algunas pruebas triviales del mundo real).

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

  • Las cadenas se implementan utilizando una biblioteca de cadenas dinámicas de C para que no paguemos (asintóticamente hablando) por asignaciones en operaciones de adición. De esta manera tenemos anexos O(N), 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, conjuntos y 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 y mucho más compacta. Esta codificación difiere para los diferentes tipos, pero tiene la característica de que es una masa compacta de datos que a menudo fuerza un escaneo O(N) para cada operación. Como utilizamos este formato sólo para objetos pequeños, esto no es un problema; escanear un pequeño blob O(N) no tiene en cuenta la caché , por lo que en la práctica 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 se refería solo a 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, etc.

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 puedes manipular este tipo de objetos del lado del servidor usando 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 a bits individuales. Por ejemplo, consulte esta buena publicación de blog: Métricas en tiempo real rápidas y sencillas utilizando Redis .

Liza

Las listas son buenas cuando es probable que toque sólo 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 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 solo queremos crear una colección limitada de N elementos donde generalmente accedemos solo a los elementos superiores o inferiores, o cuando N es pequeño.

Conjuntos

Los conjuntos son una colección de datos desordenada, por lo que son buenos cada vez que tienes una colección de elementos y es muy importante verificar la existencia o el tamaño de la colección de una manera muy rápida. Otra cosa interesante acerca de los conjuntos es la compatibilidad con la posibilidad de mirar o hacer estallar elementos aleatorios (comandos SRANDMEMBER y SPOP).

Los conjuntos también son buenos para representar relaciones, por ejemplo, "¿Cuáles son los amigos del usuario X?" Etcétera. Pero otras buenas estructuras de datos para este tipo de cosas son los 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 por 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 , 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 Redis codifica hashes pequeños de manera muy eficiente, y puede pedirle a Redis que OBTENGA, ESTABLEZCA o incremente atómicamente campos individuales de una manera muy rápida.

Los hashes también se pueden utilizar para representar estructuras de datos vinculadas, utilizando referencias. Por ejemplo, consulte 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, que mantienen elementos ordenados . Puedes hacer muchas cosas interesantes con conjuntos ordenados. Por ejemplo, puede tener todo tipo de listas de cosas destacadas en su aplicación web. Los mejores usuarios por puntuación, las mejores publicaciones por páginas vistas, lo mejor, lo que sea, pero una sola instancia de Redis admitirá toneladas de operaciones de inserción y obtención de elementos principales por segundo.

Los conjuntos ordenados, al igual que los conjuntos normales, se pueden utilizar para describir relaciones, pero también 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 prioritarias.

Los conjuntos ordenados son como listas más potentes en las que insertar, eliminar u obtener rangos desde el centro 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 algo de información en esta publicación, pero es mucho mejor descargar el código fuente de lamernews desde http://github.com/antirez/lamernews y comprender cómo funciona. Muchas estructuras de datos de Redis se utilizan dentro de Lamer News y hay muchas pistas sobre qué usar para resolver una tarea determinada.

Perdón por los errores tipográficos gramaticales, aquí es medianoche y estoy demasiado cansado para revisar la publicación;)

antirez avatar Mar 08 '2012 22:03 antirez

La mayoría de las veces, no es necesario comprender las estructuras de datos subyacentes utilizadas por Redis. Pero un poco de conocimiento le ayudará a hacer concesiones entre CPU y memoria. También le ayuda a modelar sus datos de manera eficiente.

Internamente, Redis utiliza las siguientes estructuras de datos:

  1. Cadena
  2. Diccionario
  3. Lista doblemente enlazada
  4. Saltar lista
  5. Lista postal
  6. Conjuntos internacionales
  7. Zip Maps (obsoleto en favor de la lista zip desde Redis 2.6)

Para encontrar la codificación utilizada por una clave en particular, use 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 le permite almacenar la longitud de la cadena y el número de bytes libres como prefijo.

Debido a que se almacena la longitud de la cadena, strlen es una operación O(1). Además, como se conoce la longitud, las cadenas de Redis son binariamente 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:

  1. Una cadena de caracteres que puede almacenar texto. Consulte los comandos SET y GET .
  2. Una matriz de bytes que puede almacenar datos binarios.
  3. A longque puede almacenar números. Consulte los comandos INCR , DECR , INCRBY y DECRBY .
  4. Una matriz (de chars, o cualquier otro tipo de datos) que puede permitir un acceso aleatorio eficiente ints. longsConsulte los comandos SETRANGE y GETRANGE .
  5. Una matriz de bits que le permite configurar u obtener bits individuales. Consulte los comandos SETBIT y GETBIT .
  6. Un bloque de memoria que puede utilizar para construir otras estructuras de datos. Esto se usa internamente para crear ziplists e intsets, que son estructuras de datos compactas y con uso eficiente de la memoria para una pequeña cantidad de elementos. Más sobre esto a continuación.

2. Diccionario

Redis utiliza un diccionario para lo siguiente:

  1. 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.
  2. Para asignar una clave a su marca de tiempo de vencimiento.
  3. 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 de Redis a una lista de clientes que están bloqueados en esa clave. Ver BLPOP .

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

  1. Los diccionarios utilizan una estructura llamada dictTypepara 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 claves, c) destructor de claves y d) destructor de valores.
  2. Los diccionarios utilizan 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. Utiliza Sorted Setun diccionario para asignar un elemento a su puntuación, razón por la cual ZSCORE es una operación O(1).

3. Listas doblemente enlazadas

El listtipo de datos se implementa mediante listas doblemente enlazadas . La implementación de Redis proviene directamente del libro de texto de algoritmos. El único cambio es que Redis almacena la longitud en la estructura de datos de la lista. Esto garantiza que LLEN tenga complejidad O(1).

4. Saltar listas

Redis utiliza listas de omisión como estructura de datos subyacente para conjuntos ordenados. Wikipedia tiene una buena introducción. El artículo de William Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees 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 Skip List de Redis se diferencia de la implementación estándar en los siguientes aspectos:

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

5. Lista postal

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) y, por lo tanto, para listas pequeñas, una lista doblemente enlazada es muy ineficiente.

Una Zip List almacena elementos secuencialmente en una Redis String. Cada elemento tiene un pequeño encabezado 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 utiliza para almacenar listas pequeñas, conjuntos ordenados y hashes. Los conjuntos ordenados se aplanan en una lista similar [element1, score1, element2, score2, element3, score3]y se almacenan en la Lista Zip. Los hashes se aplanan en una lista como [key1, value1, key2, value2]etc.

Con Zip Lists tienes el poder de hacer un equilibrio entre CPU y memoria. Las listas zip consumen mucha memoria, pero utilizan más CPU que una lista vinculada (o tabla hash/lista omitida). 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 listas pequeñas, hashes y conjuntos ordenados. Puede modificar este comportamiento alterando los valores de <datatype>-max-ziplist-entriesy <datatype>-max-ziplist-value>en redis.conf. Consulte Optimización de la memoria de Redis, 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 completamente esta estructura de datos sin tener que leer el código.

6. Conjuntos internacionales

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

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

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

Como 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 utilizar 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 cuanto a memoria y, para conjuntos pequeños, son más rápidos que una tabla hash. Pero después de una cierta cantidad de elementos, el tiempo de recuperación O (log N) y el costo de reasignar la memoria se vuelven demasiado. Según los experimentos, se encontró que el umbral óptimo para cambiar a una tabla hash normal es 512. Sin embargo, puede aumentar este umbral (disminuirlo no tiene sentido) según 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 listas zip.

Los mapas Zip han quedado obsoletos 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 .

Sripathi Krishnan avatar May 11 '2012 08:05 Sripathi Krishnan