Cadena de estructura de datos subyacente de Redis

Todos sabemos que Redis está escrito en lenguaje C. En el lenguaje C, la forma estándar de las cadenas termina con el carácter nulo \0 como terminador, pero las cadenas en Redis no siguen directamente a las cadenas del lenguaje C. Principalmente porque en lenguaje C, puede llamar a la función estándar strlen para obtener la longitud de una cadena. La complejidad temporal de esta función es O (N). Dado que Redis es de un solo subproceso, no puede soportar esta complejidad temporal.

En el artículo anterior, presentamos la estructura de datos de RedisObject de Redis, como se muestra a continuación:

Para diferentes objetos, Redis utilizará diferentes tipos para almacenar. Para el mismo tipo habrá diferentes formas de almacenamiento de codificación. Para cadenas de tipo cadena, existen tres métodos de codificación subyacentes, a saber, int, embstr y raw.

Utilice la clave de codificación de objetos para ver el tipo de codificación correspondiente a la clave, como se muestra a continuación:

Para los dos tipos de codificación embstr y raw, sus métodos de almacenamiento no son los mismos. Para el tipo embstr, las direcciones de memoria del encabezado del objeto RedisObject y el objeto SDS están conectadas entre sí, pero para el tipo sin formato, las direcciones de memoria de los dos no son consecutivas.

Al presentar el tipo de almacenamiento del tipo cadena, mencionamos que los métodos de almacenamiento de los tipos embstr y raw son diferentes, pero el puntero ptr en última instancia apunta a una estructura SDS. Entonces, ¿qué es SDS? La cadena en Redis se llama Cadena dinámica simple, o SDS para abreviar. En comparación con la estructura de cadena original del lenguaje C ordinario, sds tiene una información de encabezado adicional de sdshdr. La estructura de datos básica de sdshdr es la siguiente:

Se puede ver que la estructura de SDS es algo similar a. eso en Java. buf[] representa el contenido real de la cadena almacenada, alloc representa la longitud de la matriz asignada, len representa la longitud real de la cadena y, debido a la existencia del atributo len, Redis puede obtener la matriz dentro de la complejidad temporal de O( 1) longitud.

Para lograr la máxima optimización de la memoria, la capa inferior de Redis utilizará diferentes estructuras para representar cadenas de diferentes longitudes. Hay cinco tipos de sdshdr en el código fuente de sds.h en Redis, de la siguiente manera:

Como se mencionó anteriormente, la capa inferior de Redis determinará qué tipo de sdshdr usar según la longitud de la cadena. . Se puede ver que sdshdr5 es obviamente diferente de las otras cuatro estructuras. Generalmente solo se usa para almacenar cadenas cuya longitud no cambia y cuya longitud es inferior a 32 caracteres. Pero ahora esta estructura generalmente ya no se usa porque su estructura no tiene los dos atributos len y alloc, y no tiene operaciones de expansión dinámica. Una vez que se agota el espacio de memoria preasignado, es necesario reasignar la memoria. datos copiados y migrados Similar a la operación de expansión de ArrayList, esta operación tiene un gran impacto en el rendimiento.

Como se mencionó anteriormente al introducir el atributo sdshdr, el atributo de bandera se usa para identificar qué tipo de sdshdr se usa. Los tres bits inferiores de la bandera identifican el tipo de sds actual, de la siguiente manera:

Al mismo tiempo, observe que hay un atributo ((empaquetado)) en la definición del encabezado de cada sdshdr. Esto es para indicarle a gcc que cancele la alineación de optimización, de modo que las direcciones de memoria asignadas para cada campo estén estrechamente organizadas. Redis La transferencia de parámetros de cadena utiliza directamente el puntero char*. El principio de implementación es que, dado que la asignación de memoria sdshdr prohíbe la alineación optimizada, sds [-1] apunta a la dirección de memoria del atributo flags y el atributo flags se puede utilizar para. determine los atributos de sdshdr y luego se pueden leer los campos del encabezado para determinar los atributos relevantes de sds.

El diagrama lógico de sds es el siguiente:

En comparación con la cadena original del lenguaje C, sdshdr tiene algunas ventajas.

Dado que el atributo len existe en sdshdr, la longitud se puede obtener con una complejidad de tiempo de O (1); en el lenguaje C tradicional, se debe usar la función estándar strlen para obtener la longitud, con un tiempo; complejidad de O (N).

El lenguaje C original siempre usa memoria que coincide con la longitud, por lo que cuando agregar una cadena hace que la longitud de la cadena cambie, se debe reasignar la memoria. La reasignación de memoria implica algoritmos complejos y llamadas al sistema, lo que consume rendimiento y tiempo. Para Redis, es de un solo subproceso. Si se utiliza la estructura de cadena original, inevitablemente provocará una reasignación de memoria frecuente, lo que obviamente no es razonable.

Por lo tanto, cada vez que sds asigna memoria, la preasignará para reducir la cantidad de reasignaciones de memoria causadas por la modificación de cadenas. Este principio se puede utilizar como parámetro para ArrayList en Java. Generalmente, cuando se utiliza ArrayList, se recomienda utilizar un método de construcción con capacidad para evitar cambios de tamaño frecuentes.

Para SDS, cuando usa append para agregar una cadena, el programa usará alloc-len para comparar si la memoria libre restante es suficiente para asignar el contenido agregado. Si no es suficiente, lo hará naturalmente. desencadena la reasignación de memoria. Y si el espacio de memoria restante no utilizado es suficiente, se asignará directamente sin reasignación de memoria. La estrategia de expansión es que cuando el tamaño de la cadena es inferior a 1 M, cada asignación es len * 2, lo que significa que se reservan 100 redundancias cuando es mayor que 1 M. Para evitar el desperdicio, solo se asigna 1 M más de espacio; .

A través de esta estrategia de preasignación, SDS reduce la cantidad de reasignaciones de memoria necesarias para hacer crecer continuamente una cadena N veces desde ciertas N veces hasta un máximo de N veces.

El desbordamiento del búfer se refiere a la operación anormal que ocurre cuando ciertos datos exceden el límite del controlador. En el lenguaje C original, el codificador asigna memoria de cadena. Cuando no hay suficiente asignación de memoria, se produce un desbordamiento del búfer. La función de modificación de sds determinará la memoria antes de la modificación y la asignará dinámicamente, eliminando la posibilidad de desbordamiento del búfer.

Para la cadena original en lenguaje C, determinará si es el final de la cadena juzgando si hay un carácter nulo \0 en la cadena actual. Por lo tanto, en algunos casos, como cuando se utilizan espacios para dividir una cadena, o si hay \0 en archivos binarios como imágenes o vídeos, se producirán problemas. SDS no utiliza la cadena vacía para determinar si la cadena ha llegado al final, sino que utiliza el valor del campo len.

Por lo tanto, SDS también tiene la característica de seguridad binaria, es decir, puede almacenar datos binarios de forma segura en un formato especial.

blogs.com/reecelin/p/13358432.html