{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"C\u00f3digos de redundancia: en t\u00e9rminos simples, c\u00f3mo almacenar datos de manera confiable y econ\u00f3mica","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"C\u00f3digos<\/p>\n

<\/p>\n

As\u00ed es la redundancia<\/em><\/p>\n

<\/p>\n

Los c\u00f3digos de redundancia* se utilizan ampliamente en sistemas inform\u00e1ticos para aumentar la fiabilidad del almacenamiento de datos. En Yandex, se aplican en muchos proyectos. Por ejemplo, el uso de c\u00f3digos de redundancia en lugar de replicaci\u00f3n en nuestro almacenamiento de objetos interno ahorra millones sin disminuir la fiabilidad. Pero a pesar de su amplia difusi\u00f3n, descripciones claras de c\u00f3mo funcionan los c\u00f3digos de redundancia son muy raras. Aquellos que desean entender se enfrentan a lo siguiente (de Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Me llamo Vadim, en Yandex me encargo del desarrollo del almacenamiento de objetos interno MDS. En este art\u00edculo, describir\u00e9 con palabras simples los fundamentos te\u00f3ricos de los c\u00f3digos de redundancia (c\u00f3digos de Reed-Solomon y LRC). Explicar\u00e9 c\u00f3mo funciona, sin matem\u00e1ticas complejas ni t\u00e9rminos poco comunes. Al final, proporcionar\u00e9 ejemplos del uso de c\u00f3digos de redundancia en Yandex.<\/p>\n

<\/p>\n

No profundizar\u00e9 en una serie de detalles matem\u00e1ticos, pero proporcionar\u00e9 enlaces para aquellos que deseen profundizar m\u00e1s. Tambi\u00e9n se\u00f1alar\u00e9 que algunas definiciones matem\u00e1ticas pueden no ser estrictas, ya que el art\u00edculo est\u00e1 dirigido no a matem\u00e1ticos, sino a ingenieros que quieren comprender la esencia del asunto.<\/p>\n

<\/p>\n

* En la literatura en ingl\u00e9s, los c\u00f3digos de redundancia a menudo se denominan erasure codes.<\/p>\n

<\/a><\/noindex><\/p>\n

1. La esencia de los c\u00f3digos de redundancia<\/h1>\n

<\/p>\n

La esencia de todos los c\u00f3digos de redundancia es extremadamente simple: almacenar (o transmitir) datos de manera que no se pierdan ante la aparici\u00f3n de errores (fallos de discos, errores de transmisi\u00f3n de datos, etc.). <\/p>\n

<\/p>\n

En la mayor\u00eda* de los c\u00f3digos de redundancia, los datos se dividen en n bloques de datos, y para ellos se consideran m bloques de c\u00f3digos de redundancia, en total se obtienen n + m bloques. Los c\u00f3digos de redundancia se construyen de tal manera que se puedan recuperar n bloques de datos utilizando solo una parte de los n + m bloques. A continuaci\u00f3n, solo examinaremos los c\u00f3digos de redundancia de bloques, es decir, aquellos en los que los datos se dividen en bloques.<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Para recuperar todos los n bloques de datos, se necesita tener al menos n de n + m bloques, ya que no se pueden obtener n bloques con solo n-1 bloque (en este caso, se necesitar\u00eda tomar 1 bloque \u00abdel aire\u00bb). \u00bfSon suficientes n bloques arbitrarios de n + m bloques para recuperar todos los datos? Depende del tipo de c\u00f3digos de redundancia. Por ejemplo, los c\u00f3digos de Reed-Solomon permiten recuperar todos los datos con n bloques arbitrarios, mientras que los c\u00f3digos de redundancia LRC no siempre lo permiten.<\/p>\n

<\/p>\n

Almacenamiento de datos<\/h3>\n

<\/p>\n

En los sistemas de almacenamiento de datos, generalmente, cada uno de los bloques de datos y bloques de c\u00f3digos de redundancia se graba en un disco separado. As\u00ed, en caso de que falle un disco arbitrario, los datos originales a\u00fan se pueden recuperar y leer. Los datos pueden recuperarse incluso en caso de que varios discos fallen simult\u00e1neamente.<\/p>\n

<\/p>\n

Transmisi\u00f3n de datos<\/h3>\n

<\/p>\n

Se pueden usar c\u00f3digos de redundancia para la transmisi\u00f3n confiable de datos en una red no confiable. Los datos transmitidos se dividen en bloques y se calculan c\u00f3digos de redundancia para ellos. Tanto los bloques de datos como los bloques de c\u00f3digos de redundancia se transmiten por la red. En caso de errores en bloques arbitrarios (hasta cierto n\u00famero de bloques), los datos a\u00fan se pueden transmitir sin errores a trav\u00e9s de la red. Los c\u00f3digos de Reed-Solomon, por ejemplo, se utilizan para la transmisi\u00f3n de datos a trav\u00e9s de l\u00edneas de comunicaci\u00f3n \u00f3pticas y en comunicaci\u00f3n por sat\u00e9lite.<\/p>\n

<\/p>\n

* Tambi\u00e9n existen c\u00f3digos de redundancia en los que los datos no se dividen en bloques, como los c\u00f3digos de Hamming y los c\u00f3digos CRC, que se utilizan ampliamente para la transmisi\u00f3n de datos en redes Ethernet. Estos son c\u00f3digos para codificaci\u00f3n resistente a fallos, destinados a la detecci\u00f3n de errores, y no a su correcci\u00f3n (el c\u00f3digo de Hamming tambi\u00e9n permite corregir errores parcialmente).<\/p>\n

<\/p>\n

2. C\u00f3digos de Reed-Solomon<\/h1>\n

<\/p>\n

Los c\u00f3digos de Reed-Solomon son uno de los c\u00f3digos de redundancia m\u00e1s ampliamente utilizados, inventados en la d\u00e9cada de 1960 y que encontraron su aplicaci\u00f3n generalizada en la d\u00e9cada de 1980 para la producci\u00f3n en serie de discos compactos.<\/p>\n

<\/p>\n

Hay dos preguntas clave para comprender los c\u00f3digos de Reed-Solomon: 1) \u00bfc\u00f3mo se crean los bloques de c\u00f3digos de redundancia?; 2) \u00bfc\u00f3mo se recuperan los datos utilizando bloques de c\u00f3digos de redundancia? Buscaremos respuestas a estas preguntas.
\nPara simplificar, a partir de ahora consideraremos que n=6 y m=4. Otras configuraciones se analizan por analog\u00eda.<\/p>\n

<\/p>\n

C\u00f3mo crear bloques de c\u00f3digos de redundancia<\/h3>\n

<\/p>\n

Cada bloque de c\u00f3digos de redundancia se considera independientemente de los dem\u00e1s. Para calcular cada bloque se utilizan todos los n bloques de datos. En el esquema a continuaci\u00f3n, X1-X6 son bloques de datos y P1\u2013P4 son bloques de c\u00f3digos de redundancia.<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Todos los bloques de datos deben tener el mismo tama\u00f1o; para la alineaci\u00f3n se pueden usar bits nulos. Los bloques de c\u00f3digos de redundancia resultantes tendr\u00e1n el mismo tama\u00f1o que los bloques de datos. Todos los bloques de datos se dividen en palabras (por ejemplo, de 16 bits). Supongamos que hemos dividido los bloques de datos en k palabras. Entonces, todos los bloques de c\u00f3digos de redundancia tambi\u00e9n se dividir\u00e1n en k palabras.<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Para calcular la i-\u00e9sima palabra de cada bloque de redundancia se utilizar\u00e1n las i-\u00e9simas palabras de todos los bloques de datos. Se calcular\u00e1n seg\u00fan la siguiente f\u00f3rmula:<\/p>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

Aqu\u00ed los valores x son las palabras de los bloques de datos, p son las palabras de los bloques de c\u00f3digos de redundancia, todos alfa, beta, gamma y delta son n\u00fameros especialmente escogidos, iguales para todos los i. Debo mencionar que todos estos valores no son n\u00fameros ordinarios, sino elementos del campo de Galois; las operaciones +, -, *, \/ no son las operaciones comunes que conocemos, sino operaciones especiales definidas sobre los elementos del campo de Galois.<\/p>\n

<\/p>\n

\u00bfPara qu\u00e9 sirven los campos de Galois?<\/h3>\n

<\/p>\n

\"C\u00f3digos<\/p>\n

<\/p>\n

A primera vista, todo parece simple: dividimos los datos en bloques, los bloques en palabras, y usando las palabras de los bloques de datos calculamos las palabras de los bloques de c\u00f3digos de redundancia, obteniendo as\u00ed bloques de c\u00f3digos de redundancia. En general, as\u00ed es como funciona, pero el diablo est\u00e1 en los detalles:<\/p>\n

<\/p>\n

    \n
  1. Como se mencion\u00f3 anteriormente, el tama\u00f1o de la palabra es fijo, en nuestro ejemplo, 16 bits. Las f\u00f3rmulas anteriores para los c\u00f3digos de Reed-Solomon son tales que al usar n\u00fameros enteros comunes, el resultado del c\u00e1lculo de p puede no ser representable con una palabra de tama\u00f1o permitido.<\/li>\n
  2. Al recuperar datos, las f\u00f3rmulas anteriores se considerar\u00e1n como un sistema de ecuaciones que debe resolverse para recuperar los datos. En el proceso de resoluci\u00f3n, puede ser necesario realizar divisiones de n\u00fameros enteros entre s\u00ed, cuyo resultado ser\u00e1 un n\u00famero decimal que no puede ser representado con precisi\u00f3n en la memoria de la computadora.<\/li>\n<\/ol>\n

    <\/p>\n

    Estos problemas impiden usar n\u00fameros enteros para los c\u00f3digos de Reed-Solomon. La soluci\u00f3n es original y se puede describir de la siguiente manera: inventemos n\u00fameros especiales que se puedan representar mediante palabras de la longitud necesaria (por ejemplo, 16 bits), y el resultado de todas las operaciones realizadas sobre ellos (suma, resta, multiplicaci\u00f3n, divisi\u00f3n) tambi\u00e9n se representar\u00e1 en la memoria de la computadora mediante palabras de la longitud necesaria.<\/p>\n

    <\/p>\n

    Estos n\u00fameros \"especiales\" han sido estudiados durante mucho tiempo en matem\u00e1ticas, y se les llama campos. Un campo es un conjunto de elementos con operaciones definidas de suma, resta, multiplicaci\u00f3n y divisi\u00f3n.<\/p>\n

    <\/p>\n

    Los campos de Galois* son campos que tienen un resultado \u00fanico para cada operaci\u00f3n (+, -, *, \/) entre cualesquiera dos elementos del campo. Se pueden construir campos de Galois para n\u00fameros que son potencias de 2: 2, 4, 8, 16, etc. (de hecho, para cualquier potencia de un n\u00famero primo p, pero en la pr\u00e1ctica solo nos interesan las potencias de 2). Por ejemplo, para palabras de 16 bits, este campo contiene 65,536 elementos, para los cuales se puede encontrar el resultado de cualquier operaci\u00f3n (+, -, *, \/) para cada par de ellos. Los valores x, p, alfa, beta, gamma, delta de las ecuaciones anteriores se considerar\u00e1n como elementos del campo de Galois para los c\u00e1lculos.<\/p>\n

    <\/p>\n

    Por lo tanto, tenemos un sistema de ecuaciones con el que se pueden construir bloques de c\u00f3digos de redundancia, escribiendo un programa de computadora correspondiente. Con este mismo sistema de ecuaciones, se puede llevar a cabo la recuperaci\u00f3n de datos.<\/p>\n

    <\/p>\n

    * Esta no es una definici\u00f3n estricta, m\u00e1s bien es una descripci\u00f3n.<\/p>\n

    <\/p>\n

    C\u00f3mo recuperar datos<\/h3>\n

    <\/p>\n

    La recuperaci\u00f3n es necesaria cuando de n + m bloques, algunos bloques est\u00e1n ausentes. Estos pueden ser bloques de datos o bloques de c\u00f3digos de redundancia. La ausencia de bloques de datos y\/o bloques de c\u00f3digos de redundancia significar\u00e1 que en las ecuaciones anteriores se desconocen las variables correspondientes x y\/o p.<\/p>\n

    <\/p>\n

    Las ecuaciones para los c\u00f3digos de Reed-Solomon se pueden considerar como un sistema de ecuaciones en el que todos los valores alfa, beta, gamma, delta son constantes, todos los x y p correspondientes a los bloques disponibles son variables conocidas, y los dem\u00e1s x y p son desconocidos.<\/p>\n

    <\/p>\n

    Por ejemplo, supongamos que los bloques de datos 1, 2, 3 y el bloque de c\u00f3digos de redundancia 2 no est\u00e1n disponibles, entonces para el i-\u00e9simo grupo de palabras habr\u00e1 el siguiente sistema de ecuaciones (los desconocidos est\u00e1n marcados en rojo):<\/p>\n

    <\/p>\n

    \"C\u00f3digos<\/p>\n

    <\/p>\n

    \u00a1Tenemos un sistema de 4 ecuaciones con 4 inc\u00f3gnitas, as\u00ed que podemos resolverlo y recuperar los datos!<\/p>\n

    <\/p>\n

    De este sistema de ecuaciones se derivan varias conclusiones sobre la recuperaci\u00f3n de datos para los c\u00f3digos de Reed-Solomon (n bloques de datos, m bloques de c\u00f3digos de redundancia):<\/p>\n

    <\/p>\n