Estructura de datos básica de Redis
Las estructuras de datos para los valores en Redis son cadenas, listas, tablas hash, conjuntos y conjuntos ordenados, y se pueden encontrar en /p/fdd24839f460.
Hay seis estructuras de datos subyacentes, a saber, cadenas dinámicas simples, listas doblemente enlazadas, listas comprimidas, tablas hash, tablas de salto y matrices de enteros. La relación correspondiente entre ellos y los tipos de datos se muestra en la siguiente figura:
Se puede ver que la implementación subyacente del tipo String tiene solo una estructura de datos, que es una cadena dinámica simple. Hay dos implementaciones subyacentes para los cuatro tipos de datos Lista, Hash, Conjunto y Conjunto ordenado. Por lo general, llamamos a estos cuatro tipos tipos de recopilación, que se caracterizan por una clave correspondiente a una recopilación de datos.
Para lograr un acceso rápido de la clave al valor, Redis utiliza una tabla hash para guardar todos los pares clave-valor. Una tabla hash es en realidad una matriz, y cada elemento de la matriz se denomina depósito hash. Los elementos en el depósito de hash no contienen el valor en sí, sino un puntero a un valor específico.
Esto significa que, independientemente de si el valor es una cadena o un tipo de colección, los elementos en el depósito hash son punteros a ellos. En la imagen a continuación, puede ver que los elementos de entrada en el depósito de hash contienen punteros de clave y valor a las claves y valores reales, respectivamente.
Conflicto de hash, es decir, cuando los valores hash de dos claves y depósitos de hash se calculan de manera correspondiente, caen en el mismo depósito de hash. Después de todo, la cantidad de depósitos de hash suele ser menor que la cantidad de claves, lo que significa que inevitablemente habrá algunas claves cuyos hashes correspondan al mismo depósito de hash. El método de Redis para resolver conflictos de hash es el hash en cadena. El hash encadenado también es fácil de entender, es decir, varios elementos en el mismo depósito de hash se almacenan en una lista vinculada y se conectan mediante punteros.
Como se muestra en la siguiente figura: entrada1, entrada2 y entrada3 deben guardarse en el depósito de hash 3, lo que provocará un conflicto de hash. En este momento, el elemento entrada1 apuntará a la entrada2 a través del siguiente puntero y, de manera similar, la entrada2 apuntará a la entrada3 a través del siguiente puntero. De esta manera, incluso si hay 100 elementos en el depósito de hash 3, podemos conectarlos mediante el puntero en el elemento de entrada.
De hecho, para mejorar la eficiencia de las operaciones de reorganización, Redis utiliza dos tablas hash globales de forma predeterminada: la tabla hash 1 y la tabla hash 2. Cuando se insertan datos por primera vez, la tabla hash 1 se utiliza de forma predeterminada y la tabla hash 2 no tiene espacio asignado en este momento. A medida que los datos aumentan gradualmente, Redis comienza a realizar un nuevo lavado. El proceso se divide en tres pasos:
Este proceso parece simple, pero el segundo paso implica una gran cantidad de copias de datos si se migra a hash. tabla 1 a la vez Todos los datos harán que el hilo de Redis se bloquee y no pueda atender otras solicitudes. En este punto, Redis no podrá acceder a los datos rápidamente. Para evitar este problema, Redis utiliza una reorganización incremental.
En pocas palabras, al copiar datos en el segundo paso, Redis aún procesa las solicitudes de los clientes normalmente y copia todas las entradas en la primera posición del índice en la tabla hash 1 al hash de cada solicitud en la Tabla 2; En la siguiente solicitud, Redis también copia la entrada en la siguiente posición del índice en la tabla hash 1 en la tabla hash 2. Como se muestra en la siguiente figura:
Para los tipos de cadenas, puede agregar, eliminar, modificar y verificar directamente buscando en el depósito hash, por lo que la complejidad de la operación O (1) de la tabla hash es su complejidad. .
Para valores de tipo colección, el primer paso es encontrar la ubicación del depósito de hash correspondiente a través de la tabla hash global, y el segundo paso es agregar, eliminar y verificar nuevamente en la colección. En primer lugar, la complejidad operativa está relacionada con la estructura de datos subyacente de la colección. Por ejemplo, se puede acceder a una colección implementada mediante una tabla hash de manera más eficiente que a una colección implementada mediante una lista vinculada. En segundo lugar, la eficiencia de las operaciones está relacionada con las características de realizar estas operaciones en sí mismas. Por ejemplo, la operación de leer y escribir un elemento es más eficiente que la operación de leer y escribir todos los elementos.
Antes de esto, el tipo String correspondía a una cadena dinámica simple, y había cinco estructuras de datos subyacentes principales del tipo colección: matriz de enteros, lista doblemente enlazada, tabla hash, lista comprimida y tabla de salto.
Las matrices de enteros y las listas doblemente enlazadas también son muy comunes. Sus características de operación son lectura y escritura secuencial, es decir, acceder a la lista enlazada elemento por elemento a través de subíndices o punteros de matriz. N), y la eficiencia operativa es relativamente baja; las listas comprimidas y las tablas de salto pueden no tener mucho contacto en nuestra vida diaria, pero también son estructuras de datos importantes de Redis.
Una lista comprimida es en realidad similar a una matriz, y cada elemento de la matriz contiene un dato. A diferencia de las matrices, el encabezado de la lista comprimida tiene tres campos: zlbytes, zltail y zllen, que representan respectivamente la longitud de la lista, el desplazamiento al final de la lista y el número de entradas en la lista; zlend al final de la lista comprimida, que representa el final de la lista.
Tabla de salto Según la lista vinculada, agregamos un índice de varios niveles para lograr una ubicación rápida de los datos mediante múltiples saltos en la posición del índice, como se muestra en la siguiente figura:
Redis puede operar rápidamente pares clave-valor, por un lado, debido al uso extensivo de tablas hash de complejidad O (1), incluidas String, Hash y Set. Por el otro, la complejidad de la operación está básicamente determinada por la tabla hash; Por un lado, Sorted Set también utiliza una tabla de salto con complejidad O (logN). Sin embargo, la complejidad de las operaciones de rango en tipos de colección suele ser O(N) porque se debe atravesar la estructura de datos subyacente.
No podemos olvidar la mayor complejidad del tipo Lista. Sus dos estructuras de implementación subyacentes, la lista doblemente enlazada y la lista comprimida, tienen una complejidad de operación de O(N). Por lo tanto, se debe utilizar el tipo Lista cuando corresponda. Por ejemplo, dado que el tipo Lista es eficiente POP/PUSH, debe usarse principalmente en escenarios de cola FIFO en lugar de como una colección que se puede leer y escribir aleatoriamente.