Así es como se ve la redundancia
Los códigos de redundancia* se utilizan ampliamente en sistemas informáticos para aumentar la confiabilidad del almacenamiento de datos. En Yandex se utilizan en muchos proyectos. Por ejemplo, usar códigos de redundancia en lugar de replicación en nuestro almacenamiento interno de objetos ahorra millones sin sacrificar la confiabilidad. Pero a pesar de su uso generalizado, las descripciones claras de cómo funcionan los códigos de redundancia son muy raras. Aquellos que quieren comprender se enfrentan aproximadamente a lo siguiente (de ):
Mi nombre es Vadim, en Yandex estoy desarrollando MDS de almacenamiento interno de objetos. En este artículo, describiré en palabras sencillas los fundamentos teóricos de los códigos de redundancia (códigos Reed-Solomon y LRC). Te diré cómo funciona, sin matemáticas complejas y sin términos raros. Al final, daré ejemplos del uso de códigos de redundancia en Yandex.
No consideraré en detalle una serie de detalles matemáticos, pero proporcionaré enlaces para aquellos que quieran profundizar más. También señalaré que algunas definiciones matemáticas pueden no ser estrictas, ya que el artículo no está destinado a matemáticos, sino a ingenieros que quieran comprender la esencia del problema.
* En la literatura en idioma inglés, los códigos de redundancia a menudo se denominan códigos de borrado.
1. La esencia de los códigos de redundancia
La esencia de todos los códigos de redundancia es extremadamente simple: almacenar (o transmitir) datos para que no se pierdan cuando ocurren errores (fallos de disco, errores de transferencia de datos, etc.).
En la mayoría* de los códigos de redundancia, los datos se dividen en n bloques de datos, para los cuales se cuentan m bloques de códigos de redundancia, lo que da como resultado un total de n + m bloques. Los códigos de redundancia se construyen de tal manera que se puedan recuperar n bloques de datos utilizando sólo una parte de n + m bloques. A continuación, consideraremos únicamente los códigos de redundancia de bloques, es decir, aquellos en los que los datos se dividen en bloques.
Para recuperar los n bloques de datos, necesita tener al menos n de n + m bloques, ya que no puede obtener n bloques teniendo solo n-1 bloque (en este caso, tendría que tomar 1 bloque "de la nada"). aire"). ¿Son suficientes n bloques aleatorios de n + m bloques para recuperar todos los datos? Esto depende del tipo de códigos de redundancia; por ejemplo, los códigos Reed-Solomon le permiten recuperar todos los datos utilizando n bloques arbitrarios, pero los códigos de redundancia LRC no siempre lo hacen.
Almacenamiento de datos
En los sistemas de almacenamiento de datos, por regla general, cada uno de los bloques de datos y bloques de código de redundancia se escribe en un disco separado. Luego, si falla un disco arbitrario, los datos originales aún se pueden restaurar y leer. Los datos se pueden recuperar incluso si fallan varios discos al mismo tiempo.
Transferencia de datos
Los códigos de redundancia se pueden utilizar para transmitir datos de manera confiable a través de una red no confiable. Los datos transmitidos se dividen en bloques y para ellos se calculan códigos de redundancia. Tanto los bloques de datos como los bloques de códigos de redundancia se transmiten a través de la red. Si se producen errores en bloques arbitrarios (hasta un cierto número de bloques), los datos aún se pueden transmitir a través de la red sin errores. Los códigos Reed-Solomon, por ejemplo, se utilizan para transmitir datos a través de líneas de comunicación óptica y en comunicaciones por satélite.
* También existen códigos de redundancia en los que los datos no se dividen en bloques, como los códigos Hamming y los códigos CRC, que son muy utilizados para la transmisión de datos en redes Ethernet. Estos son códigos para codificación de corrección de errores, están diseñados para detectar errores y no para corregirlos (el código Hamming también permite la corrección parcial de errores).
2. Códigos Reed-Solomon
Los códigos Reed-Solomon son uno de los códigos de redundancia más utilizados, inventados en la década de 1960 y ampliamente utilizados por primera vez en la década de 1980 para la producción en masa de discos compactos.
Hay dos preguntas clave para comprender los códigos Reed-Solomon: 1) cómo crear bloques de códigos de redundancia; 2) cómo recuperar datos utilizando bloques de código de redundancia. Busquemos respuestas para ellas.
Por simplicidad, asumiremos además que n=6 y m=4. Otros esquemas se consideran por analogía.
Cómo crear bloques de código de redundancia
Cada bloque de códigos de redundancia se cuenta independientemente de los demás. Los n bloques de datos se utilizan para contar cada bloque. En el siguiente diagrama, X1-X6 son bloques de datos, P1-P4 son bloques de código de redundancia.
Todos los bloques de datos deben tener el mismo tamaño y se pueden utilizar cero bits para la alineación. Los bloques de código de redundancia resultantes tendrán el mismo tamaño que los bloques de datos. Todos los bloques de datos se dividen en palabras (por ejemplo, 16 bits). Digamos que dividimos los bloques de datos en k palabras. Luego, todos los bloques de códigos de redundancia también se dividirán en k palabras.
Para contar la i-ésima palabra de cada bloque de redundancia, se utilizarán las i-ésimas palabras de todos los bloques de datos. Se calcularán según la siguiente fórmula:
Aquí los valores x son las palabras de los bloques de datos, p son las palabras de los bloques de código de redundancia, todos alfa, beta, gamma y delta son números especialmente seleccionados que son iguales para todos los i. Hay que decir de inmediato que todos estos valores no son números ordinarios, sino elementos del campo de Galois; las operaciones +, -, *, / no son operaciones que todos conocemos, sino operaciones especiales introducidas en elementos de Galois. campo.
¿Por qué se necesitan los campos de Galois?
Parecería que todo es simple: dividimos los datos en bloques, los bloques en palabras, usando las palabras de los bloques de datos contamos las palabras de los bloques de código de redundancia; obtenemos bloques de código de redundancia. En general así es como funciona, pero el problema está en los detalles:
- Como se indicó anteriormente, el tamaño de la palabra es fijo, en nuestro ejemplo 16 bits. Las fórmulas anteriores para los códigos Reed-Solomon son tales que cuando se usan números enteros ordinarios, el resultado del cálculo de p puede no ser representable usando una palabra de tamaño válido.
- Al recuperar datos, las fórmulas anteriores se considerarán como un sistema de ecuaciones que deben resolverse para poder recuperar los datos. Durante el proceso de solución, puede ser necesario dividir números enteros entre sí, lo que da como resultado un número real que no se puede representar con precisión en la memoria de la computadora.
Estos problemas impiden el uso de números enteros para códigos Reed-Solomon. La solución al problema es original, se puede describir de la siguiente manera: inventemos números especiales que se puedan representar usando palabras de la longitud requerida (por ejemplo, 16 bits) y el resultado de realizar todas las operaciones en las que (suma , resta, multiplicación, división) también se presentarán en la memoria de la computadora utilizando palabras de la longitud requerida.
Estos números "especiales" han sido estudiados por las matemáticas durante mucho tiempo; se llaman campos. Un campo es un conjunto de elementos con operaciones de suma, resta, multiplicación y división definidas para ellos.
Los campos Galois* son campos para los cuales existe un resultado único de cada operación (+, -, *, /) para dos elementos cualesquiera del campo. Los campos de Galois se pueden construir para números que son potencias de 2: 2, 4, 8, 16, etc. (en realidad, potencias de cualquier número primo p, pero en la práctica solo nos interesan las potencias de 2). Por ejemplo, para palabras de 16 bits, este es un campo que contiene 65 536 elementos, para cada par de los cuales puede encontrar el resultado de cualquier operación (+, -, *, /). Los valores de x, p, alfa, beta, gamma, delta de las ecuaciones anteriores se considerarán elementos del campo de Galois para los cálculos.
Así, tenemos un sistema de ecuaciones con el que podemos construir bloques de códigos de redundancia escribiendo un programa de computadora apropiado. Usando el mismo sistema de ecuaciones, puedes realizar la recuperación de datos.
* Esta no es una definición estricta, sino más bien una descripción.
Cómo recuperar datos
Se necesita restauración cuando faltan algunos de los bloques n + m. Pueden ser tanto bloques de datos como bloques de códigos de redundancia. La ausencia de bloques de datos y/o bloques de código de redundancia significará que las variables x y/o p correspondientes son desconocidas en las ecuaciones anteriores.
Las ecuaciones para los códigos Reed-Solomon pueden verse como un sistema de ecuaciones en el que todos los valores alfa, beta, gamma y delta son constantes, todas las x y p correspondientes a los bloques disponibles son variables conocidas y las x y p restantes son desconocidos.
Por ejemplo, si los bloques de datos 1, 2, 3 y el bloque de código de redundancia 2 no están disponibles, entonces para el i-ésimo grupo de palabras habrá el siguiente sistema de ecuaciones (las incógnitas están marcadas en rojo):
¡Tenemos un sistema de 4 ecuaciones con 4 incógnitas, lo que significa que podemos resolverlo y restaurar los datos!
De este sistema de ecuaciones se desprenden una serie de conclusiones sobre la recuperación de datos para códigos Reed-Solomon (n bloques de datos, m bloques de códigos de redundancia):
- Los datos se pueden recuperar si se pierden m bloques o menos. Si se pierden m+1 o más bloques, los datos no se pueden restaurar: es imposible resolver un sistema de m ecuaciones con m + 1 incógnitas.
- Para recuperar incluso un bloque de datos, necesita usar n de los bloques restantes y puede usar cualquiera de los códigos de redundancia.
¿Qué más necesito saber?
En la descripción anterior, evito una serie de cuestiones importantes que requieren una inmersión más profunda en las matemáticas para considerarlas. En particular, no digo nada sobre lo siguiente:
- El sistema de ecuaciones para códigos Reed-Solomon debe tener una solución (única) para cualquier combinación de incógnitas (no más de m incógnitas). En base a este requisito se seleccionan los valores de alfa, beta, gamma y delta.
- Un sistema de ecuaciones debe poder construirse automáticamente (dependiendo de qué bloques no estén disponibles) y resolverse.
- Necesitamos construir un campo Galois: para un tamaño de palabra determinado, poder encontrar el resultado de cualquier operación (+, -, *, /) para dos elementos cualesquiera.
Al final del artículo hay referencias a la literatura sobre estos importantes temas.
Elección de n y m
¿Cómo elegir n y m en la práctica? En la práctica, en los sistemas de almacenamiento de datos, se utilizan códigos de redundancia para ahorrar espacio, por lo que m siempre se elige menor que n. Sus valores específicos dependen de varios factores, entre ellos:
- Fiabilidad del almacenamiento de datos. Cuanto mayor sea m, mayor será el número de fallas de disco a las que se puede sobrevivir, es decir, mayor será la confiabilidad.
- Almacenamiento redundante. Cuanto mayor sea la relación m/n, mayor será la redundancia de almacenamiento y más caro será el sistema.
- Solicitar tiempo de procesamiento. Cuanto mayor sea la suma n + m, mayor será el tiempo de respuesta a las solicitudes. Dado que la lectura de datos (durante la recuperación) requiere leer n bloques almacenados en n discos diferentes, el tiempo de lectura estará determinado por el disco más lento.
Además, almacenar datos en varios DC impone restricciones adicionales en la elección de n y m: si 1 DC está apagado, los datos aún deben estar disponibles para lectura. Por ejemplo, al almacenar datos en 3 DC, se debe cumplir la siguiente condición: m >= n/2; de lo contrario, puede haber una situación en la que los datos no estén disponibles para lectura cuando 1 DC está apagado.
3. LRC - Códigos de reconstrucción locales
Para recuperar datos utilizando códigos Reed-Solomon, debe utilizar n bloques de datos arbitrarios. Esta es una desventaja muy importante para los sistemas de almacenamiento de datos distribuidos, porque para restaurar datos en un disco roto, tendrá que leer datos de la mayoría de los demás, lo que crea una gran carga adicional en los discos y la red.
Los errores más comunes son la inaccesibilidad de un bloque de datos debido a una falla o sobrecarga de un disco. ¿Es posible reducir de alguna manera el exceso de carga para la recuperación de datos en este caso (el más común)? Resulta que puedes: existen códigos de redundancia LRC específicamente para este propósito.
Los LRC (códigos de reconstrucción local) son códigos de redundancia inventados por Microsoft para su uso en Windows Azure Storage. La idea de LRC es lo más simple posible: dividir todos los bloques de datos en dos (o más) grupos y leer parte de los bloques de código de redundancia para cada grupo por separado. Luego, algunos bloques de códigos de redundancia se contarán utilizando todos los bloques de datos (en LRC se denominan códigos de redundancia globales) y otros, utilizando uno de dos grupos de bloques de datos (se denominan códigos de redundancia locales).
LRC se indica con tres números: nrl, donde n es el número de bloques de datos, r es el número de bloques de código de redundancia global, l es el número de bloques de código de redundancia local. Para leer datos cuando un bloque de datos no está disponible, necesita leer solo n/l bloques; esto es XNUMX veces menos que en los códigos Reed-Solomon.
Por ejemplo, considere el esquema LRC 6-2-2. X1–X6: 6 bloques de datos, P1, P2: 2 bloques de redundancia global, P3, P4: 2 bloques de redundancia local.
Los bloques de códigos de redundancia P1, P2 se cuentan utilizando todos los bloques de datos. Bloque de código de redundancia P3 - usando bloques de datos X1-X3, bloque de código de redundancia P4 - usando bloques de datos X4-X6.
El resto se hace en LRC por analogía con los códigos Reed-Solomon. Las ecuaciones para contar las palabras de los bloques de código de redundancia serán:
Para seleccionar los números alfa, beta, gamma, delta, se deben cumplir una serie de condiciones para garantizar la posibilidad de recuperación de datos (es decir, resolver el sistema de ecuaciones). Puedes leer más sobre ellos en .
También en la práctica, la operación XOR se utiliza para calcular los códigos de redundancia locales P3, P4.
Del sistema de ecuaciones de LRC se desprenden varias conclusiones:
- Para recuperar 1 bloque de datos cualquiera, es suficiente leer n/l bloques (n/2 en nuestro ejemplo).
- Si los bloques r + l no están disponibles y todos los bloques están incluidos en un grupo, los datos no se pueden restaurar. Esto es fácil de explicar con un ejemplo. Dejemos que los bloques X1–X3 y P3 no estén disponibles: estos son bloques r + l del mismo grupo, 4 en nuestro caso. Entonces tenemos un sistema de 3 ecuaciones con 4 incógnitas que no se puede resolver.
- En todos los demás casos de indisponibilidad de los bloques r + l (cuando al menos un bloque está disponible de cada grupo), los datos en el LRC se pueden restaurar.
Por lo tanto, LRC supera a los códigos Reed-Solomon en la recuperación de datos después de errores únicos. En los códigos Reed-Solomon, para recuperar incluso un bloque de datos, necesita usar n bloques, y en LRC, para recuperar un bloque de datos, es suficiente usar n/l bloques (n/2 en nuestro ejemplo). Por otro lado, LRC es inferior a los códigos Reed-Solomon en términos del número máximo de errores permitidos. En los ejemplos anteriores, los códigos Reed-Solomon pueden recuperar datos de 4 errores cualesquiera, y para LRC hay 2 combinaciones de 4 errores cuando los datos no se pueden recuperar.
Lo que es más importante depende de la situación específica, pero a menudo los ahorros en exceso de carga que proporciona LRC superan el almacenamiento ligeramente menos confiable.
4. Otros códigos de redundancia
Además de los códigos Reed-Solomon y LRC, existen muchos otros códigos de redundancia. Los diferentes códigos de redundancia utilizan diferentes matemáticas. Aquí hay algunos otros códigos de redundancia:
- Código de redundancia utilizando el operador XOR. La operación XOR se realiza en n bloques de datos y se obtiene 1 bloque de códigos de redundancia, es decir, un esquema n + 1 (n bloques de datos, 1 código de redundancia). Utilizada en , donde se escriben cíclicamente bloques de datos y códigos de redundancia en todos los discos de la matriz.
- Algoritmo par-impar basado en la operación XOR. Le permite construir 2 bloques de códigos de redundancia, es decir, el esquema n+2.
- Algoritmo STAR basado en la operación XOR. Le permite construir 3 bloques de códigos de redundancia, es decir, el esquema n+3.
- Los códigos Pyramide son otros códigos de redundancia de Microsoft.
5. Usar en Yandex
Varios proyectos de infraestructura de Yandex utilizan códigos de redundancia para un almacenamiento de datos confiable. Aquí hay unos ejemplos:
- Almacenamiento de objetos interno MDS, sobre el que escribí al principio del artículo.
- — Sistema MapReduce de Yandex.
- (Yandex DataBase): nueva base de datos distribuida SQL.
MDS utiliza códigos de redundancia LRC, esquema 8-2-2. Los datos con códigos de redundancia se escriben en 12 discos diferentes en servidores diferentes en 3 DC diferentes: 4 servidores en cada DC. Lea más sobre esto en .
YT utiliza códigos Reed-Solomon (Esquema 6-3), que fueron los primeros en implementar, y códigos de redundancia LRC (Esquema 12-2-2), siendo LRC el método de almacenamiento preferido.
YDB utiliza códigos de redundancia basados en pares e impares (Figura 4-2). Acerca de los códigos de redundancia en YDB ya .
El uso de diferentes esquemas de códigos de redundancia se debe a diferentes requisitos de los sistemas. Por ejemplo, en MDS, los datos almacenados mediante LRC se colocan en 3 DC a la vez. Es importante para nosotros que los datos permanezcan disponibles para lectura si falla uno de los DC, por lo tanto, los bloques deben distribuirse entre los DC de modo que, si algún DC no está disponible, la cantidad de bloques inaccesibles no sea mayor que la permitida. En el esquema 1-8-2, puede colocar 2 bloques en cada DC, luego, cuando cualquier DC esté apagado, 4 bloques no estarán disponibles y los datos se podrán leer. Sea cual sea el esquema que elijamos a la hora de colocarlo en 4 DCs, en cualquier caso debería haber (r+l)/n >= 3, es decir, la redundancia de almacenamiento será al menos del 0,5%.
En YT la situación es diferente: cada clúster de YT está ubicado completamente en 1 DC (diferentes clústeres en diferentes DC), por lo que no existe tal restricción. El esquema 12-2-2 proporciona un 33% de redundancia, es decir, almacenar datos es más barato y también puede sobrevivir hasta 4 cortes de disco simultáneos, al igual que el esquema MDS.
Hay muchas más características del uso de códigos de redundancia en sistemas de procesamiento y almacenamiento de datos: matices de la recuperación de datos, el impacto de la recuperación en el tiempo de ejecución de la consulta, características de registro de datos, etc. Voy a hablar por separado sobre estas y otras características. del uso de códigos de redundancia en la práctica, si el tema resulta interesante.
6. Referencias
- Una serie de artículos sobre códigos Reed-Solomon y campos de Galois:
Profundizan en las matemáticas en un lenguaje accesible. - Artículo de Microsoft sobre LRC:
La sección 2 explica brevemente la teoría y luego analiza las experiencias con LRC en la práctica. - Esquema par-impar:
- Esquema ESTRELLA:
- Códigos piramidales:
- Códigos de redundancia en MDS:
- Códigos de redundancia en YT:
- Códigos de redundancia en YDB:
Fuente: habr.com