É assim que se parece a redundância
Os códigos de redundância* são amplamente utilizados em sistemas computacionais para aumentar a confiabilidade do armazenamento de dados. No Yandex eles são usados em muitos projetos. Por exemplo, usar códigos de redundância em vez de replicação em nosso armazenamento interno de objetos economiza milhões sem sacrificar a confiabilidade. Mas, apesar de seu uso generalizado, descrições claras de como funcionam os códigos de redundância são muito raras. Aqueles que desejam entender se deparam com aproximadamente o seguinte (de ):
Meu nome é Vadim, na Yandex estou desenvolvendo MDS de armazenamento interno de objetos. Neste artigo, descreverei em palavras simples os fundamentos teóricos dos códigos de redundância (códigos Reed-Solomon e LRC). Vou te contar como funciona, sem matemática complexa e termos raros. No final darei exemplos de uso de códigos de redundância no Yandex.
Não considerarei detalhadamente uma série de detalhes matemáticos, mas fornecerei links para quem quiser se aprofundar. Observo também que algumas definições matemáticas podem não ser estritas, uma vez que o artigo não se destina a matemáticos, mas a engenheiros que desejam compreender a essência do assunto.
* Na literatura de língua inglesa, os códigos de redundância são frequentemente chamados de códigos de apagamento.
1. A essência dos códigos de redundância
A essência de todos os códigos de redundância é extremamente simples: armazenar (ou transmitir) dados para que não sejam perdidos quando ocorrerem erros (falhas de disco, erros de transferência de dados, etc.).
Na maioria* dos códigos de redundância, os dados são divididos em n blocos de dados, para os quais são contados m blocos de códigos de redundância, resultando em um total de n + m blocos. Os códigos de redundância são construídos de tal forma que n blocos de dados podem ser recuperados usando apenas uma porção de n + m blocos. A seguir consideraremos apenas os códigos de redundância de blocos, ou seja, aqueles em que os dados são divididos em blocos.
Para recuperar todos os n blocos de dados, você precisa ter pelo menos n de n + m blocos, já que você não pode obter n blocos tendo apenas n-1 bloco (neste caso, você teria que pegar 1 bloco “fora do fino ar"). N blocos aleatórios de n + m blocos são suficientes para recuperar todos os dados? Isso depende do tipo de códigos de redundância, por exemplo, os códigos Reed-Solomon permitem recuperar todos os dados usando n blocos arbitrários, mas os códigos de redundância LRC nem sempre o fazem.
Armazenamento de dados
Em sistemas de armazenamento de dados, como regra, cada um dos blocos de dados e blocos de código de redundância é gravado em um disco separado. Então, se um disco arbitrário falhar, os dados originais ainda poderão ser restaurados e lidos. Os dados podem ser recuperados mesmo se vários discos falharem ao mesmo tempo.
Transferência de dados
Os códigos de redundância podem ser usados para transmitir dados de forma confiável em uma rede não confiável. Os dados transmitidos são divididos em blocos e os códigos de redundância são calculados para eles. Tanto os blocos de dados quanto os blocos de código de redundância são transmitidos pela rede. Se ocorrerem erros em blocos arbitrários (até um determinado número de blocos), os dados ainda poderão ser transmitidos pela rede sem erros. Os códigos Reed-Solomon, por exemplo, são usados para transmitir dados através de linhas de comunicação óptica e em comunicações por satélite.
* Existem também códigos de redundância em que os dados não são divididos em blocos, como os códigos Hamming e os códigos CRC, que são amplamente utilizados para transmissão de dados em redes Ethernet. São códigos para codificação de correção de erros, projetados para detectar erros, e não para corrigi-los (o código de Hamming também permite a correção parcial de erros).
2. Códigos Reed-Solomon
Os códigos Reed-Solomon são um dos códigos de redundância mais utilizados, inventados na década de 1960 e amplamente utilizados na década de 1980 para produção em massa de discos compactos.
Existem duas questões-chave para a compreensão dos códigos Reed-Solomon: 1) como criar blocos de códigos de redundância; 2) como recuperar dados usando blocos de código de redundância. Vamos encontrar respostas para eles.
Para simplificar, assumiremos ainda que n=6 e m=4. Outros esquemas são considerados por analogia.
Como criar blocos de código de redundância
Cada bloco de códigos de redundância é contado independentemente dos demais. Todos os n blocos de dados são usados para contar cada bloco. No diagrama abaixo, X1-X6 são blocos de dados, P1-P4 são blocos de código de redundância.
Todos os blocos de dados devem ter o mesmo tamanho e zero bits podem ser usados para alinhamento. Os blocos de código de redundância resultantes terão o mesmo tamanho dos blocos de dados. Todos os blocos de dados são divididos em palavras (por exemplo, 16 bits). Digamos que dividimos os blocos de dados em k palavras. Então todos os blocos de códigos de redundância também serão divididos em k palavras.
Para contar a i-ésima palavra de cada bloco de redundância, serão utilizadas as i-ésimas palavras de todos os blocos de dados. Eles serão calculados de acordo com a seguinte fórmula:
Aqui os valores x são as palavras dos blocos de dados, p são as palavras dos blocos de código de redundância, todos os alfa, beta, gama e delta são números especialmente selecionados que são iguais para todos os i. Deve-se dizer desde já que todos esses valores não são números comuns, mas elementos do corpo de Galois; as operações +, -, *, / não são operações familiares a todos nós, mas operações especiais introduzidas em elementos do corpo de Galois campo.
Por que os campos de Galois são necessários?
Parece que tudo é simples: dividimos os dados em blocos, os blocos em palavras, usando as palavras dos blocos de dados contamos as palavras dos blocos de código de redundância - obtemos blocos de código de redundância. Em geral é assim que funciona, mas o diabo está nos detalhes:
- Conforme afirmado acima, o tamanho da palavra é fixo, em nosso exemplo 16 bits. As fórmulas acima para códigos Reed-Solomon são tais que, ao usar números inteiros comuns, o resultado do cálculo de p pode não ser representável usando uma palavra de tamanho válido.
- Na recuperação dos dados, as fórmulas acima serão consideradas como um sistema de equações que devem ser resolvidas para a recuperação dos dados. Durante o processo de solução, pode ser necessário dividir números inteiros entre si, resultando em um número real que não pode ser representado com precisão na memória do computador.
Esses problemas impedem o uso de números inteiros para códigos Reed-Solomon. A solução para o problema é original, pode ser descrita da seguinte forma: vamos criar números especiais que possam ser representados usando palavras do comprimento necessário (por exemplo, 16 bits), e o resultado de realizar todas as operações nas quais (adição , subtração, multiplicação, divisão) também serão apresentados na memória do computador usando palavras com o comprimento necessário.
Esses números “especiais” têm sido estudados pela matemática há muito tempo; são chamados de campos. Um campo é um conjunto de elementos com operações de adição, subtração, multiplicação e divisão definidas para eles.
Os campos Galois* são campos para os quais existe um resultado único de cada operação (+, -, *, /) para quaisquer dois elementos do campo. Os campos de Galois podem ser construídos para números que são potências de 2: 2, 4, 8, 16, etc. (na verdade, potências de qualquer número primo p, mas na prática estamos interessados apenas em potências de 2). Por exemplo, para palavras de 16 bits, este é um campo contendo 65 elementos, para cada par dos quais você pode encontrar o resultado de qualquer operação (+, -, *, /). Os valores de x, p, alfa, beta, gama, delta das equações acima serão considerados elementos do campo de Galois para cálculos.
Assim, temos um sistema de equações com o qual podemos construir blocos de códigos de redundância escrevendo um programa de computador apropriado. Usando o mesmo sistema de equações, você pode realizar a recuperação de dados.
* Esta não é uma definição estrita, mas sim uma descrição.
Como recuperar dados
A restauração é necessária quando alguns dos blocos n + m estão faltando. Podem ser blocos de dados e blocos de código de redundância. A ausência de blocos de dados e/ou blocos de código de redundância significará que as variáveis x e/ou p correspondentes são desconhecidas nas equações acima.
As equações para os códigos Reed-Solomon podem ser vistas como um sistema de equações em que todos os valores alfa, beta, gama e delta são constantes, todos os x e p correspondentes aos blocos disponíveis são variáveis conhecidas e os restantes x e p são desconhecidos.
Por exemplo, deixe os blocos de dados 1, 2, 3 e o bloco de código de redundância 2 estarem indisponíveis, então para o i-ésimo grupo de palavras haverá o seguinte sistema de equações (as incógnitas estão marcadas em vermelho):
Temos um sistema de 4 equações com 4 incógnitas, o que significa que podemos resolvê-lo e restaurar os dados!
Deste sistema de equações seguem-se uma série de conclusões sobre a recuperação de dados para códigos Reed-Solomon (n blocos de dados, m blocos de código de redundância):
- Os dados podem ser recuperados se m blocos ou menos forem perdidos. Se m+1 ou mais blocos forem perdidos, os dados não poderão ser restaurados: é impossível resolver um sistema de m equações com m + 1 incógnitas.
- Para recuperar pelo menos um bloco de dados, você precisa usar qualquer n dos blocos restantes e pode usar qualquer um dos códigos de redundância.
O que mais eu preciso saber?
Na descrição acima, evito uma série de questões importantes que exigem um mergulho mais profundo na matemática para serem consideradas. Em particular, não estou dizendo nada sobre o seguinte:
- O sistema de equações para códigos Reed-Solomon deve ter uma solução (única) para qualquer combinação de incógnitas (não mais do que m incógnitas). Com base neste requisito, são selecionados os valores de alfa, beta, gama e delta.
- Um sistema de equações deve poder ser construído automaticamente (dependendo de quais blocos não estão disponíveis) e resolvido.
- Precisamos construir um campo de Galois: para um determinado tamanho de palavra, ser capaz de encontrar o resultado de qualquer operação (+, -, *, /) para quaisquer dois elementos.
No final do artigo há referências à literatura sobre essas importantes questões.
Escolha de n e m
Como escolher n e m na prática? Na prática, em sistemas de armazenamento de dados, códigos de redundância são usados para economizar espaço, portanto m é sempre escolhido menor que n. Seus valores específicos dependem de vários fatores, incluindo:
- Confiabilidade do armazenamento de dados. Quanto maior m, maior será o número de falhas de disco às quais é possível sobreviver, ou seja, maior será a confiabilidade.
- Armazenamento redundante. Quanto maior a relação m/n, maior será a redundância de armazenamento e mais caro será o sistema.
- Tempo de processamento da solicitação. Quanto maior a soma n + m, maior será o tempo de resposta às solicitações. Como a leitura de dados (durante a recuperação) requer a leitura de n blocos armazenados em n discos diferentes, o tempo de leitura será determinado pelo disco mais lento.
Além disso, o armazenamento de dados em vários DCs impõe restrições adicionais na escolha de n e m: se 1 DC estiver desligado, os dados ainda deverão estar disponíveis para leitura. Por exemplo, ao armazenar dados em 3 DCs, a seguinte condição deve ser atendida: m >= n/2, caso contrário pode haver uma situação em que os dados fiquem indisponíveis para leitura quando 1 DC for desligado.
3. LRC – Códigos de Reconstrução Local
Para recuperar dados usando códigos Reed-Solomon, você deve usar n blocos de dados arbitrários. Esta é uma desvantagem muito significativa para sistemas de armazenamento de dados distribuídos, porque para restaurar dados em um disco quebrado, você terá que ler dados da maioria dos outros, criando uma grande carga adicional nos discos e na rede.
Os erros mais comuns são a inacessibilidade de um bloco de dados devido a falha ou sobrecarga de um disco. É possível reduzir de alguma forma o excesso de carga para recuperação de dados neste caso (mais comum)? Acontece que você pode: existem códigos de redundância LRC específicos para essa finalidade.
LRC (códigos de reconstrução local) são códigos de redundância inventados pela Microsoft para uso no armazenamento do Windows Azure. A ideia do LRC é a mais simples possível: dividir todos os blocos de dados em dois (ou mais) grupos e ler parte dos blocos de código de redundância para cada grupo separadamente. Em seguida, alguns blocos de código de redundância serão contados usando todos os blocos de dados (no LRC eles são chamados de códigos de redundância global) e alguns - usando um dos dois grupos de blocos de dados (eles são chamados de códigos de redundância local).
LRC é denotado por três números: nrl, onde n é o número de blocos de dados, r é o número de blocos de código de redundância global, l é o número de blocos de código de redundância local. Para ler dados quando um bloco de dados não está disponível, você precisa ler apenas n/l blocos - isso é l vezes menos do que nos códigos Reed-Solomon.
Por exemplo, considere o esquema LRC 6-2-2. X1–X6 — 6 blocos de dados, P1, P2 — 2 blocos de redundância global, P3, P4 — 2 blocos de redundância local.
Os blocos de código de redundância P1, P2 são contados usando todos os blocos de dados. Bloco de código de redundância P3 - usando blocos de dados X1-X3, bloco de código de redundância P4 - usando blocos de dados X4-X6.
O resto é feito em LRC por analogia com os códigos Reed-Solomon. As equações para contagem das palavras dos blocos de códigos de redundância serão:
Para selecionar os números alfa, beta, gama, delta, uma série de condições devem ser atendidas para garantir a possibilidade de recuperação dos dados (ou seja, resolução do sistema de equações). Você pode ler mais sobre eles em .
Também na prática, a operação XOR é utilizada para calcular os códigos de redundância local P3, P4.
Uma série de conclusões decorrem do sistema de equações para LRC:
- Para recuperar qualquer 1 bloco de dados, basta ler n/l blocos (n/2 em nosso exemplo).
- Se os blocos r + l não estiverem disponíveis e todos os blocos estiverem incluídos em um grupo, os dados não poderão ser restaurados. Isso é fácil de explicar com um exemplo. Sejam os blocos X1–X3 e P3 indisponíveis: são r + l blocos do mesmo grupo, 4 no nosso caso. Então temos um sistema de 3 equações com 4 incógnitas que não podem ser resolvidas.
- Em todos os demais casos de indisponibilidade dos blocos r + l (quando pelo menos um bloco de cada grupo estiver disponível), os dados do LRC poderão ser restaurados.
Assim, o LRC supera os códigos Reed-Solomon na recuperação de dados após erros únicos. Nos códigos Reed-Solomon, para recuperar pelo menos um bloco de dados, é necessário usar n blocos, e no LRC, para recuperar um bloco de dados, basta usar n/l blocos (n/2 em nosso exemplo). Por outro lado, o LRC é inferior aos códigos Reed-Solomon em termos do número máximo de erros permitidos. Nos exemplos acima, os códigos Reed-Solomon podem recuperar dados para quaisquer 4 erros, e para LRC há 2 combinações de 4 erros quando os dados não podem ser recuperados.
O que é mais importante depende da situação específica, mas muitas vezes a economia em excesso de carga que o LRC proporciona compensa o armazenamento um pouco menos confiável.
4. Outros códigos de redundância
Além dos códigos Reed-Solomon e LRC, existem muitos outros códigos de redundância. Diferentes códigos de redundância usam matemática diferente. Aqui estão alguns outros códigos de redundância:
- Código de redundância usando o operador XOR. A operação XOR é realizada em n blocos de dados, e é obtido 1 bloco de códigos de redundância, ou seja, um esquema n+1 (n blocos de dados, 1 código de redundância). Usado em , onde blocos de dados e códigos de redundância são gravados ciclicamente em todos os discos do array.
- Algoritmo par-ímpar baseado na operação XOR. Permite construir 2 blocos de códigos de redundância, ou seja, o esquema n+2.
- Algoritmo STAR baseado na operação XOR. Permite construir 3 blocos de códigos de redundância, ou seja, o esquema n+3.
- Os códigos pirâmide são outros códigos de redundância da Microsoft.
5. Use no Yandex
Vários projetos de infraestrutura Yandex usam códigos de redundância para armazenamento confiável de dados. aqui estão alguns exemplos:
- Armazenamento interno de objetos do MDS, sobre o qual escrevi no início do artigo.
- — Sistema MapReduce do Yandex.
- (Yandex DataBase) - banco de dados distribuído newSQL.
O MDS usa códigos de redundância LRC, esquema 8-2-2. Os dados com códigos de redundância são gravados em 12 discos diferentes em servidores diferentes em 3 DCs diferentes: 4 servidores em cada DC. Leia mais sobre isso em .
YT usa códigos Reed-Solomon (Esquema 6-3), que foram os primeiros a implementar, e códigos de redundância LRC (Esquema 12-2-2), sendo o LRC o método de armazenamento preferido.
YDB usa códigos de redundância baseados em pares e ímpares (Figura 4-2). Já sobre códigos de redundância no YDB .
O uso de diferentes esquemas de códigos de redundância se deve a diferentes requisitos dos sistemas. Por exemplo, no MDS, os dados armazenados usando LRC são colocados em 3 DCs ao mesmo tempo. É importante para nós que os dados permaneçam disponíveis para leitura se 1 de qualquer DC falhar, portanto os blocos devem ser distribuídos entre os DCs para que se algum DC estiver indisponível, o número de blocos inacessíveis não seja maior que o permitido. No esquema 8-2-2, você pode colocar 4 blocos em cada DC, então quando qualquer DC for desligado, 4 blocos ficarão indisponíveis e os dados poderão ser lidos. Seja qual for o esquema que escolhermos ao colocá-lo em 3 DCs, em qualquer caso deverá haver (r + l) / n >= 0,5, ou seja, a redundância de armazenamento será de pelo menos 50%.
No YT a situação é diferente: cada cluster YT está inteiramente localizado em 1 DC (clusters diferentes em DCs diferentes), portanto não existe tal restrição. O esquema 12-2-2 oferece redundância de 33%, ou seja, o armazenamento de dados é mais barato, e também pode sobreviver a até 4 interrupções simultâneas de disco, assim como o esquema MDS.
Existem muito mais recursos do uso de códigos de redundância em sistemas de armazenamento e processamento de dados: nuances da recuperação de dados, o impacto da recuperação no tempo de execução da consulta, recursos de gravação de dados, etc. do uso de códigos de redundância na prática, se o tema for interessante.
6. Links
- Uma série de artigos sobre códigos Reed-Solomon e campos de Galois:
Eles analisam mais profundamente a matemática em linguagem acessível. - Artigo da Microsoft sobre LRC:
A Secção 2 explica brevemente a teoria e depois discute experiências com LRC na prática. - Esquema par-ímpar:
- Esquema ESTRELA:
- Códigos da pirâmide:
- Códigos de redundância no MDS:
- Códigos de redundância no YT:
- Códigos de redundância em YDB:
Fonte: habr.com