Así se ve a redundancia
Os códigos de redundancia* úsanse amplamente nos sistemas informáticos para aumentar a fiabilidade do almacenamento de datos. En Yandex úsanse en moitos proxectos. Por exemplo, usar códigos de redundancia en lugar de replicar no noso almacenamento de obxectos interno aforra millóns sen sacrificar a fiabilidade. Pero a pesar do seu uso xeneralizado, as descricións claras de como funcionan os códigos de redundancia son moi raras. Aqueles que queiran entender enfróntanse aproximadamente ao seguinte (de ):
Chámome Vadim, en Yandex estou a desenvolver MDS de almacenamento de obxectos internos. Neste artigo, describirei con palabras sinxelas os fundamentos teóricos dos códigos de redundancia (códigos Reed-Solomon e LRC). Vouche contar como funciona, sen matemáticas complexas e termos raros. Ao final darei exemplos de uso de códigos de redundancia en Yandex.
Non vou considerar unha serie de detalles matemáticos en detalle, pero proporcionarei ligazóns para aqueles que queiran mergullarse máis a fondo. Tamén notarei que algunhas definicións matemáticas poden non ser estritas, xa que o artigo non está destinado a matemáticos, senón a enxeñeiros que queiran comprender a esencia do problema.
* Na literatura en lingua inglesa, os códigos de redundancia adoitan denominarse códigos de borrado.
1. A esencia dos códigos de redundancia
A esencia de todos os códigos de redundancia é extremadamente sinxela: almacenar (ou transmitir) datos para que non se perdan cando se produzan erros (fallos de disco, erros de transferencia de datos, etc.).
Na maioría dos* códigos de redundancia, os datos divídense en n bloques de datos, para os que se contan m bloques de códigos de redundancia, o que resulta nun total de n + m bloques. Os códigos de redundancia constrúense de tal xeito que se poden recuperar n bloques de datos usando só unha parte de n + m bloques. A continuación, consideraremos só os códigos de redundancia de bloques, é dicir, aqueles nos que os datos están divididos en bloques.
Para recuperar todos os n bloques de datos, cómpre ter polo menos n de n + m bloques, xa que non podes obter n bloques tendo só n-1 bloque (neste caso, terías que sacar 1 bloque do aire”). Son suficientes n bloques aleatorios de n + m bloques para recuperar todos os datos? Isto depende do tipo de códigos de redundancia, por exemplo, os códigos de Reed-Solomon permítenche recuperar todos os datos mediante n bloques arbitrarios, pero os códigos de redundancia LRC non sempre o fan.
Almacenamento de datos
Nos sistemas de almacenamento de datos, por regra xeral, cada un dos bloques de datos e bloques de códigos redundantes escríbese nun disco separado. Entón, se falla un disco arbitrario, os datos orixinais aínda se poden restaurar e ler. Os datos pódense recuperar aínda que fallen varios discos ao mesmo tempo.
Transferencia de datos
Os códigos de redundancia pódense usar para transmitir datos de forma fiable a través dunha rede pouco fiable. Os datos transmitidos divídense en bloques e calcúlanse códigos de redundancia para eles. Tanto os bloques de datos como os bloques de códigos redundantes transmítense pola rede. Se se producen erros en bloques arbitrarios (ata un número determinado de bloques), os datos aínda poden transmitirse pola rede sen erros. Os códigos Reed-Solomon, por exemplo, úsanse para transmitir datos a través de liñas de comunicación óptica e en comunicacións por satélite.
* Tamén existen códigos de redundancia nos que os datos non se dividen en bloques, como os códigos Hamming e os códigos CRC, que son moi utilizados para a transmisión de datos en redes Ethernet. Son códigos para a codificación de corrección de erros, están deseñados para detectar erros, e non para corrixilos (o código Hamming tamén permite a corrección parcial de erros).
2. Códigos Reed-Solomon
Os códigos Reed-Solomon son un dos códigos redundantes máis utilizados, inventados na década de 1960 e utilizados por primeira vez na década de 1980 para a produción en masa de discos compactos.
Hai dúas preguntas clave para comprender os códigos Reed-Solomon: 1) como crear bloques de códigos redundantes; 2) como recuperar datos usando bloques de códigos de redundancia. Imos atopar respostas a eles.
Para simplificar, suporemos ademais que n=6 e m=4. Outros esquemas considéranse por analoxía.
Como crear bloques de código redundante
Cada bloque de códigos de redundancia cóntase independentemente dos outros. Todos os n bloques de datos úsanse para contar cada bloque. No diagrama de abaixo, X1-X6 son bloques de datos, P1-P4 son bloques de código redundante.
Todos os bloques de datos deben ter o mesmo tamaño e pódense usar cero bits para o aliñamento. Os bloques de código de redundancia resultantes terán o mesmo tamaño que os bloques de datos. Todos os bloques de datos están divididos en palabras (por exemplo, 16 bits). Digamos que dividimos os bloques de datos en k palabras. A continuación, todos os bloques de códigos redundantes tamén se dividirán en k palabras.
Para contar a i-ésima palabra de cada bloque de redundancia, utilizaranse as i-ésimas palabras de todos os bloques de datos. Calcularanse segundo a seguinte fórmula:
Aquí os valores x son as palabras dos bloques de datos, p son as palabras dos bloques de códigos redundantes, todos alfa, beta, gamma e delta son números especialmente seleccionados que son iguais para todos i. Hai que dicir de inmediato que todos estes valores non son números ordinarios, senón elementos do campo de Galois; as operacións +, -, *, / non son operacións familiares para todos nós, senón operacións especiais introducidas en elementos do Galois. campo.
Por que son necesarios os campos de Galois?
Parece que todo é sinxelo: dividimos os datos en bloques, os bloques en palabras, utilizando as palabras dos bloques de datos contamos as palabras dos bloques de códigos redundantes: obtemos bloques de códigos redundantes. En xeral, así funciona, pero o demo está nos detalles:
- Como se dixo anteriormente, o tamaño da palabra é fixo, no noso exemplo 16 bits. As fórmulas anteriores para códigos Reed-Solomon son tales que cando se usan números enteiros ordinarios, o resultado do cálculo de p pode non ser representable usando unha palabra de tamaño válido.
- Á hora de recuperar datos, as fórmulas anteriores consideraranse como un sistema de ecuacións que se deben resolver para recuperar os datos. Durante o proceso de solución, pode ser necesario dividir os números enteiros entre si, dando como resultado un número real que non se pode representar con precisión na memoria do ordenador.
Estes problemas impiden o uso de números enteiros para códigos Reed-Solomon. A solución do problema é orixinal, pódese describir do seguinte xeito: imos dar con números especiais que se poidan representar usando palabras da lonxitude requirida (por exemplo, 16 bits) e o resultado de realizar todas as operacións nas que (adición , resta, multiplicación, división) tamén se presentarán na memoria do ordenador utilizando palabras da lonxitude requirida.
Estes números "especiais" foron estudados polas matemáticas durante moito tempo; chámanse campos. Un campo é un conxunto de elementos con operacións de suma, resta, multiplicación e división definidas para eles.
Os campos de Galois* son campos para os que hai un resultado único de cada operación (+, -, *, /) para dous elementos calquera do campo. Os campos de Galois pódense construír para números que son potencias de 2: 2, 4, 8, 16, etc. (en realidade potencias de calquera número primo p, pero na práctica só nos interesan as potencias de 2). Por exemplo, para palabras de 16 bits, este é un campo que contén 65 elementos, para cada par dos cales podes atopar o resultado de calquera operación (+, -, *, /). Os valores de x, p, alfa, beta, gamma, delta das ecuacións anteriores consideraranse elementos do campo de Galois para os cálculos.
Así, temos un sistema de ecuacións co que podemos construír bloques de códigos redundantes escribindo un programa informático axeitado. Usando o mesmo sistema de ecuacións, pode realizar a recuperación de datos.
* Esta non é unha definición estrita, senón unha descrición.
Como recuperar datos
A restauración é necesaria cando faltan algúns dos n + m bloques. Estes poden ser tanto bloques de datos como bloques de código redundante. A ausencia de bloques de datos e/ou bloques de códigos de redundancia significará que as variables x e/ou p correspondentes sexan descoñecidas nas ecuacións anteriores.
As ecuacións dos códigos Reed-Solomon pódense ver como un sistema de ecuacións no que todos os valores alfa, beta, gamma e delta son constantes, todos x e p correspondentes aos bloques dispoñibles son variables coñecidas e os restantes x e p son descoñecidos.
Por exemplo, deixe que os bloques de datos 1, 2, 3 e o bloque de código de redundancia 2 non estean dispoñibles, entón para o i-ésimo grupo de palabras haberá o seguinte sistema de ecuacións (as incógnitas están marcadas en vermello):
Temos un sistema de 4 ecuacións con 4 incógnitas, o que significa que podemos resolvelo e restaurar os datos!
Deste sistema de ecuacións seguen unha serie de conclusións sobre a recuperación de datos para códigos Reed-Solomon (n bloques de datos, m bloques de códigos de redundancia):
- Os datos pódense recuperar se se perden m bloques ou menos. Se se perden m+1 ou máis bloques, os datos non se poden restaurar: é imposible resolver un sistema de m ecuacións con m + 1 incógnitas.
- Para recuperar mesmo un bloque de datos, cómpre utilizar calquera dos bloques restantes e pode utilizar calquera dos códigos de redundancia.
O que máis precisas saber
Na descrición anterior, evito unha serie de cuestións importantes que requiren unha inmersión máis profunda nas matemáticas. En particular, non digo nada sobre o seguinte:
- O sistema de ecuacións dos códigos Reed-Solomon debe ter unha solución (única) para calquera combinación de incógnitas (non máis de m incógnitas). Con base neste requisito, selecciónanse os valores de alfa, beta, gamma e delta.
- Un sistema de ecuacións debe poder construírse automaticamente (dependendo de que bloques non estean dispoñibles) e resolverse.
- Necesitamos construír un campo de Galois: para un tamaño de palabra dado, ser capaz de atopar o resultado de calquera operación (+, -, *, /) para dous elementos calquera.
Ao final do artigo hai referencias á literatura sobre estas importantes cuestións.
Elección de n e m
Como escoller n e m na práctica? Na práctica, nos sistemas de almacenamento de datos utilízanse códigos de redundancia para aforrar espazo, polo que sempre se escolle m menor que n. Os seus valores específicos dependen dunha serie de factores, incluíndo:
- Fiabilidade no almacenamento de datos. Canto maior m, maior será o número de fallos de disco aos que se poden sobrevivir, é dicir, maior será a fiabilidade.
- Almacenamento redundante. Canto maior sexa a relación m/n, maior será a redundancia de almacenamento e máis caro será o sistema.
- Solicitude de tempo de tramitación. Canto maior sexa a suma n + m, maior será o tempo de resposta ás solicitudes. Dado que a lectura de datos (durante a recuperación) require ler n bloques almacenados en n discos diferentes, o tempo de lectura estará determinado polo disco máis lento.
Ademais, almacenar datos en varios DC impón restricións adicionais á elección de n e m: se 1 DC está desactivado, os datos aínda deben estar dispoñibles para a súa lectura. Por exemplo, ao almacenar datos en 3 DC, debe cumprirse a seguinte condición: m >= n/2, se non, pode haber unha situación na que os datos non estean dispoñibles para a lectura cando 1 DC está desactivado.
3. LRC - Códigos de Reconstrución Local
Para recuperar datos usando códigos Reed-Solomon, ten que usar n bloques de datos arbitrarios. Esta é unha desvantaxe moi importante para os sistemas de almacenamento de datos distribuídos, porque para restaurar os datos nun disco roto, terás que ler os datos da maioría dos outros, creando unha gran carga adicional nos discos e na rede.
Os erros máis comúns son a inaccesibilidade dun bloque de datos debido a unha falla ou sobrecarga dun disco. É posible reducir dalgún xeito o exceso de carga para a recuperación de datos neste caso (máis común)? Resulta que podes: hai códigos de redundancia LRC especificamente para este fin.
LRC (Local Reconstruction Codes) son códigos redundantes inventados por Microsoft para usar en Windows Azure Storage. A idea de LRC é o máis sinxela posible: dividir todos os bloques de datos en dous (ou máis) grupos e ler parte dos bloques de código de redundancia para cada grupo por separado. Despois, algúns bloques de códigos de redundancia contaranse utilizando todos os bloques de datos (en LRC chámanse códigos de redundancia global) e algúns, usando un dos dous grupos de bloques de datos (denomínanse códigos de redundancia local).
LRC denotase con tres números: nrl, onde n é o número de bloques de datos, r é o número de bloques de código de redundancia global, l é o número de bloques de código de redundancia local. Para ler datos cando un bloque de datos non está dispoñible, cómpre ler só n/l bloques; isto é l veces menos que nos códigos Reed-Solomon.
Por exemplo, considere o 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.
Os bloques de códigos de redundancia P1, P2 cóntanse utilizando todos os bloques de datos. Bloque de código de redundancia P3 - utilizando bloques de datos X1-X3, bloque de código de redundancia P4 - utilizando bloques de datos X4-X6.
O resto faise en LRC por analoxía cos códigos Reed-Solomon. As ecuacións para contar as palabras dos bloques de códigos redundantes serán:
Para seleccionar os números alfa, beta, gamma, delta débense cumprir unha serie de condicións para garantir a posibilidade de recuperación de datos (é dicir, resolver o sistema de ecuacións). Podes ler máis sobre eles en .
Tamén na práctica, a operación XOR utilízase para calcular códigos de redundancia local P3, P4.
Do sistema de ecuacións para LRC se desprenden unha serie de conclusións:
- Para recuperar calquera bloque de datos 1, abonda con ler n/l bloques (n/2 no noso exemplo).
- Se os bloques r + l non están dispoñibles e todos os bloques están incluídos nun grupo, non se poden restaurar os datos. Isto é fácil de explicar cun exemplo. Que os bloques X1–X3 e P3 non estean dispoñibles: son bloques r + l do mesmo grupo, 4 no noso caso. Entón temos un sistema de 3 ecuacións con 4 incógnitas que non se poden resolver.
- En todos os demais casos de indisponibilidade dos bloques r + l (cando polo menos hai un bloque dispoñible de cada grupo), pódense restaurar os datos do LRC.
Así, LRC supera os códigos Reed-Solomon na recuperación de datos despois de erros individuais. Nos códigos Reed-Solomon, para recuperar mesmo un bloque de datos, cómpre usar n bloques, e en LRC, para recuperar un bloque de datos, abonda con usar n/l bloques (n/2 no noso exemplo). Por outra banda, LRC é inferior aos códigos Reed-Solomon en canto ao número máximo de erros permitidos. Nos exemplos anteriores, os códigos Reed-Solomon poden recuperar datos de calquera erro 4, e para LRC hai 2 combinacións de 4 erros cando os datos non se poden recuperar.
O que é máis importante depende da situación específica, pero moitas veces o aforro no exceso de carga que proporciona LRC supera o almacenamento un pouco menos fiable.
4. Outros códigos de redundancia
Ademais dos códigos Reed-Solomon e LRC, hai moitos outros códigos de redundancia. Os diferentes códigos de redundancia usan diferentes matemáticas. Aquí tes outros códigos de redundancia:
- Código de redundancia mediante o operador XOR. A operación XOR realízase en n bloques de datos, e obtense 1 bloque de códigos de redundancia, é dicir, un esquema n+1 (n bloques de datos, 1 código de redundancia). Usado en , onde os bloques de datos e os códigos de redundancia se escriben cíclicamente en todos os discos da matriz.
- Algoritmo par-impar baseado na operación XOR. Permite construír 2 bloques de códigos redundantes, é dicir, o esquema n+2.
- Algoritmo STAR baseado na operación XOR. Permite construír 3 bloques de códigos redundantes, é dicir, o esquema n+3.
- Os códigos Pyramide son outros códigos redundantes de Microsoft.
5. Use en Yandex
Varios proxectos de infraestrutura de Yandex usan códigos de redundancia para almacenar datos fiables. Aquí tes algúns exemplos:
- Almacenamento interno de obxectos MDS, sobre o que escribín ao comezo do artigo.
- - Sistema MapReduce de Yandex.
- (Base de datos Yandex) - base de datos distribuída newSQL.
MDS usa códigos de redundancia LRC, esquema 8-2-2. Os datos con códigos de redundancia escríbense en 12 discos diferentes en diferentes servidores en 3 DCs diferentes: 4 servidores en cada DC. Ler máis sobre isto en .
YT usa códigos Reed-Solomon (Esquema 6-3), que foron os primeiros en implementar, e códigos de redundancia LRC (Esquema 12-2-2), sendo LRC o método de almacenamento preferido.
YDB usa códigos de redundancia baseados en pares e impares (Figura 4-2). Xa sobre os códigos de redundancia en YDB .
O uso de diferentes esquemas de códigos de redundancia débese a diferentes requisitos dos sistemas. Por exemplo, en MDS, os datos almacenados mediante LRC colócanse en 3 DC á vez. É importante para nós que os datos estean dispoñibles para a súa lectura se 1 de calquera DC falla, polo tanto, os bloques deben distribuírse entre os DC para que, se algún DC non está dispoñible, o número de bloques inaccesibles non é máis que permitido. No esquema 8-2-2, pode colocar 4 bloques en cada DC, entón cando calquera DC estea desactivado, 4 bloques non estarán dispoñibles e os datos pódense ler. Sexa cal sexa o esquema que elixamos ao situalo en 3 DC, en todo caso debería haber (r + l) / n >= 0,5, é dicir, a redundancia de almacenamento será polo menos do 50%.
En YT a situación é diferente: cada clúster de YT está totalmente situado en 1 DC (distintos clústeres en diferentes DC), polo que non existe esa restrición. O esquema 12-2-2 proporciona un 33% de redundancia, é dicir, o almacenamento de datos é máis barato e tamén pode sobrevivir ata 4 cortes de disco simultáneos, igual que o esquema MDS.
Hai moitas máis características do uso de códigos de redundancia nos sistemas de almacenamento e procesamento de datos: matices da recuperación de datos, o impacto da recuperación no tempo de execución da consulta, características da gravación de datos, etc. Vou falar por separado destas e outras características. do uso de códigos redundantes na práctica, se o tema é interesante.
6. Ligazóns
- Unha serie de artigos sobre códigos Reed-Solomon e campos de Galois:
Afondan nas matemáticas nunha linguaxe accesible. - Artigo de Microsoft sobre LRC:
A sección 2 explica brevemente a teoría e, a continuación, discute experiencias con LRC na práctica. - Esquema par-impar:
- esquema STAR:
- Códigos pirámides:
- Códigos de redundancia en MDS:
- Códigos de redundancia en YT:
- Códigos de redundancia en YDB:
Fonte: www.habr.com