Código de apagamento 📖 Wikipedia

Na teoria de códigos, um código de apagamento (do inglês erasure code) é um código de correção antecipada de erros (FEC) sob a suposição de apagamentos de bits (em vez de erros de bits), que transforma uma mensagem de ${\displaystyle k}$ símbolos em uma mensagem mais longa (palavra-código) com ${\displaystyle n}$ símbolos, de tal forma que a mensagem original possa ser recuperada a partir de um subconjunto dos ${\displaystyle n}$ símbolos. A fração ${\displaystyle r=k/n}$ é chamada de taxa de código. A fração ${\displaystyle k'/k}$, onde ${\displaystyle k'}$ denota o número de símbolos necessários para a recuperação, é chamada de eficiência de recepção. O algoritmo de recuperação pressupõe que se sabe quais dos ${\displaystyle n}$ símbolos foram perdidos.

A codificação de apagamento foi inventada por Irving Reed e Gustave Solomon em 1960.^[1]

Existem muitos esquemas diferentes de codificação de apagamento. Os códigos de apagamento mais populares são a codificação de Reed-Solomon, os códigos de verificação de paridade de baixa densidade (códigos LDPC) e os turbo códigos.^[1]

A partir de 2023, sistemas modernos de armazenamento de dados podem ser projetados para tolerar a falha completa de alguns discos sem perda de dados, usando uma de 3 abordagens:^[2][3][4]

• Replicação
• RAID
• Codificação de Apagamento (Erasure Coding)

Embora o RAID possa ser tecnicamente visto como um tipo de código de apagamento,^[5] o termo "RAID" é geralmente aplicado a um arranjo conectado a um único computador hospedeiro (que é um ponto único de falha), enquanto "codificação de apagamento" geralmente implica em múltiplos hospedeiros,^[3] às vezes chamados de Redundant Array of Inexpensive Servers (RAIS). O código de apagamento permite que as operações continuem quando qualquer um desses hospedeiros para de funcionar.^[4][6]

Comparada aos sistemas RAID de nível de bloco, a codificação de apagamento em armazenamento de objetos possui algumas diferenças significativas que a tornam mais resiliente.^{[7][8][9][10][11]}

Os códigos de apagamento ótimos têm a propriedade de que quaisquer ${\displaystyle k}$ dos ${\displaystyle n}$ símbolos da palavra-código são suficientes para recuperar a mensagem original (ou seja, eles possuem eficiência de recepção ótima). Códigos de apagamento ótimos são códigos separáveis de distância máxima (códigos MDS).

A verificação de paridade é o caso especial em que ${\displaystyle n=k+1}$. A partir de um conjunto de ${\displaystyle k}$ valores ${\displaystyle \{v_{i}\}_{1\leq i\leq k}}$, uma soma de verificação (checksum) é calculada e anexada aos ${\displaystyle k}$ valores de origem:

${\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}$

O conjunto de ${\displaystyle k+1}$ valores ${\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}$ agora é consistente em relação à soma de verificação. Se um desses valores, ${\displaystyle v_{e}}$, for apagado, ele poderá ser facilmente recuperado somando as variáveis restantes:

${\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}$

O RAID 5 é uma aplicação amplamente utilizada do código de apagamento de verificação de paridade usando a operação XOR (Ou Exclusivo).^[1]

No caso simples onde ${\displaystyle k=2}$, símbolos de redundância podem ser criados amostrando diferentes pontos ao longo da reta entre os dois símbolos originais. Isso é ilustrado com um exemplo simples, chamado err-mail (correio com erros):

Alice quer enviar seu número de telefone (555629) para Bob usando o err-mail. O err-mail funciona exatamente como o e-mail, exceto que:

1. Cerca de metade de todo o correio se perde.
2. Mensagens com mais de 5 caracteres são ilegais.
3. É muito caro (semelhante ao correio aéreo).

Em vez de pedir a Bob para confirmar o recebimento das mensagens que ela envia, Alice elabora o seguinte esquema:

1. Ela divide seu número de telefone em duas partes ${\displaystyle a=555}$ e ${\displaystyle b=629}$, e envia 2 mensagens – "A=555" e "B=629" – para Bob.
2. Ela constrói uma função linear, ${\displaystyle f(i)=a+(b-a)(i-1)}$, neste caso ${\displaystyle f(i)=555+74(i-1)}$, de forma que ${\displaystyle f(1)=555}$ e ${\displaystyle f(2)=629}$.

1. Ela calcula os valores ${\displaystyle f(3)}$, ${\displaystyle f(4)}$ e ${\displaystyle f(5)}$, e então transmite três mensagens redundantes: "C=703", "D=777" e "E=851".

Bob sabe que a forma de ${\displaystyle f(k)}$ é ${\displaystyle f(i)=a+(b-a)(i-1)}$, onde ${\displaystyle a}$ e ${\displaystyle b}$ são as duas partes do número de telefone. Agora suponha que Bob receba "D=777" e "E=851".

Bob pode reconstruir o número de telefone da Alice computando os valores de ${\displaystyle a}$ e ${\displaystyle b}$ a partir dos valores (${\displaystyle f(4)}$ e ${\displaystyle f(5)}$) que ele recebeu. Bob pode realizar esse procedimento usando quaisquer dois err-mails, então o código de apagamento neste exemplo tem uma taxa de 40%.

Note que Alice não pode codificar seu número de telefone em apenas um err-mail, porque ele contém seis caracteres, e o comprimento máximo de uma mensagem de err-mail é de cinco caracteres. Se ela enviasse seu número de telefone em pedaços, pedindo a Bob para confirmar o recebimento de cada pedaço, pelo menos quatro mensagens teriam que ser enviadas de qualquer maneira (duas da Alice e duas confirmações do Bob). Logo, o código de apagamento neste exemplo, que requer cinco mensagens, é bastante econômico.

Este exemplo é um pouco artificial. Para códigos de apagamento verdadeiramente genéricos que funcionem sobre qualquer conjunto de dados, precisaríamos de algo diferente da ${\displaystyle f(i)}$ fornecida.

A construção linear acima pode ser generalizada para a interpolação polinomial. Além disso, os pontos agora são computados sobre um corpo finito.

Primeiro escolhemos um corpo finito ${\displaystyle F}$ com ordem de pelo menos ${\displaystyle n}$, mas geralmente uma potência de ${\displaystyle 2}$. O remetente numera os símbolos de dados de ${\displaystyle 0}$ a ${\displaystyle k-1}$ e os envia. Em seguida, ele constrói um polinômio (de Lagrange) ${\displaystyle p(x)}$ de grau ${\displaystyle k}$ de modo que ${\displaystyle p(i)}$ seja igual ao símbolo de dados ${\displaystyle i}$. Ele então envia ${\displaystyle p(k),\dots ,p(n-1)}$. O receptor agora também pode usar a interpolação polinomial para recuperar os pacotes perdidos, desde que receba ${\displaystyle k}$ símbolos com sucesso. Se a ordem de ${\displaystyle F}$ for menor que ${\displaystyle 2^{b}}$, onde ${\displaystyle b}$ é o número de bits em um símbolo, então múltiplos polinômios podem ser usados.

O remetente pode construir os símbolos de ${\displaystyle k}$ a ${\displaystyle n-1}$ "em tempo real" (on the fly), ou seja, distribuir a carga de trabalho de forma uniforme entre a transmissão dos símbolos. Se o receptor quiser fazer seus cálculos "em tempo real", ele pode construir um novo polinômio ${\displaystyle q}$, tal que ${\displaystyle q(i)=p(i)}$ se o símbolo ${\displaystyle i<k}$ for recebido com sucesso e ${\displaystyle q(i)=0}$ quando o símbolo ${\displaystyle i<k}$ não for recebido. Agora seja ${\displaystyle r(i)=p(i)-q(i)}$. Em primeiro lugar, sabemos que ${\displaystyle r(i)=0}$ se o símbolo ${\displaystyle i<k}$ foi recebido com sucesso. Em segundo lugar, se o símbolo ${\displaystyle i\geq k}$ foi recebido com sucesso, então ${\displaystyle r(i)=p(i)-q(i)}$ pode ser calculado. Então, temos pontos de dados suficientes para construir ${\displaystyle r}$ e avaliá-lo para encontrar os pacotes perdidos. Portanto, tanto o remetente quanto o receptor exigem ${\displaystyle O(n(n-k))}$ operações e apenas ${\displaystyle O(n-k)}$ espaço para operar "em tempo real".

Este processo é implementado pelos códigos de Reed-Solomon, com palavras-código construídas sobre um corpo finito usando uma matriz de Vandermonde.

A maioria dos códigos de apagamento práticos são códigos sistemáticos — cada um dos ${\displaystyle k}$ símbolos originais pode ser encontrado copiado, sem codificação, como um dos ${\displaystyle n}$ símbolos da mensagem.^[12] (Códigos de apagamento que suportam compartilhamento de segredos nunca usam um código sistemático).

Os códigos de apagamento quase ótimos requerem ${\displaystyle (1+\varepsilon )k}$ símbolos para recuperar a mensagem (onde ${\displaystyle \varepsilon >0}$). A redução de ${\displaystyle \varepsilon }$ pode ser feita ao custo de tempo de CPU. Os códigos de apagamento quase ótimos trocam capacidades de correção por complexidade computacional: algoritmos práticos podem codificar e decodificar com complexidade de tempo linear.

Os códigos fonte (Fountain codes, também conhecidos como códigos de apagamento sem taxa fixa) são exemplos notáveis de códigos de apagamento quase ótimos. Eles podem transformar uma mensagem de ${\displaystyle k}$ símbolos em uma forma codificada praticamente infinita, ou seja, podem gerar uma quantidade arbitrária de símbolos de redundância que podem ser todos usados para correção de erros. Os receptores podem iniciar a decodificação após terem recebido pouco mais de ${\displaystyle k}$ símbolos codificados.

Os códigos regeneradores tratam da questão de reconstruir (também chamado de reparar) fragmentos codificados perdidos a partir de fragmentos codificados existentes. Esse problema ocorre em sistemas de armazenamento distribuído, onde a comunicação para manter a redundância codificada é um problema.^[12]

A codificação de apagamento é agora uma prática padrão para armazenamento de dados confiável.^[13][14][15] Em particular, várias implementações de codificação de apagamento de Reed-Solomon são usadas pelo Apache Hadoop, pelo RAID-6 embutido no Linux, Microsoft Azure, armazenamento frio (cold storage) do Facebook e Backblaze Vaults.^[15][12]

A maneira clássica de se recuperar de falhas em sistemas de armazenamento era usar a replicação. No entanto, a replicação incorre em uma sobrecarga significativa em termos de bytes desperdiçados. Portanto, sistemas de armazenamento cada vez maiores, como os usados em data centers, usam armazenamento codificado por apagamento. A forma mais comum de codificação de apagamento usada em sistemas de armazenamento é o código Reed-Solomon (RS), uma fórmula matemática avançada usada para permitir a regeneração de dados ausentes a partir de pedaços de dados conhecidos, chamados blocos de paridade. Em um código RS ${\displaystyle (k,r)}$, um dado conjunto de blocos de dados, chamados "pedaços" (chunks), é codificado em ${\displaystyle k+r}$ pedaços. O conjunto total de pedaços compõe uma "faixa" (stripe). A codificação é feita de tal forma que, desde que pelo menos ${\displaystyle k}$ dos ${\displaystyle k+r}$ pedaços estejam disponíveis, é possível recuperar todos os dados. Isso significa que um armazenamento codificado em RS ${\displaystyle (k,m)}$ pode tolerar até ${\displaystyle m}$ falhas. (Isso é diferente da notação RS${\displaystyle (n,k)}$ padrão, com ${\displaystyle n=k+r}$.)

Exemplo: No código ${\displaystyle {\text{RS}}(10,4)}$, que é usado no Facebook para o seu HDFS (agora parte do Apache Hadoop), 10 MB de dados de usuário são divididos em dez blocos de 1 MB. Em seguida, quatro blocos de paridade adicionais de 1 MB são criados para fornecer redundância. Isso pode tolerar até 4 falhas simultâneas. A sobrecarga de armazenamento aqui é ${\displaystyle 14/10=1{,}4\times }$.^[16]

No caso de um sistema totalmente replicado, os 10 MB de dados de usuário teriam que ser replicados 4 vezes para tolerar até 4 falhas simultâneas. A sobrecarga de armazenamento nesse caso seria de ${\displaystyle 50/10=5}$ vezes.

Isso dá uma ideia da menor sobrecarga de armazenamento do armazenamento com código de apagamento em comparação com a replicação total, e consequentemente, o porquê de ser atraente nos sistemas de armazenamento de hoje.

O esquema Hitchhiker pode ser combinado com a codificação RS para reduzir a quantidade de computação e transferência de dados necessárias para a reconstrução de blocos de dados. Ele também é implementado como um codec HDFS, embora uma política precise ser definida manualmente para que seja usado.^[12]

Inicialmente, os códigos de apagamento eram usados para reduzir o custo de armazenamento eficiente de dados "frios" (pouco acessados); mas os códigos de apagamento também podem ser usados para melhorar o desempenho no fornecimento de dados "quentes" (acessados com mais frequência) em comparação com esquemas de redundância mais simples (espelhamento).^[12]

O exemplo clássico da codificação de apagamento melhorando o desempenho é o RAID 5, que fornece a mesma proteção contra falha de um único drive enquanto requer menos discos rígidos em comparação com o RAID 1. Os discos rígidos extras podem então ser usados para armazenar mais dados e aproveitar o multiplicador aprimorado de velocidade de leitura/gravação no RAID 5. Isso também se aplica ao RAID 6 (redundância dupla: uma paridade e um código de apagamento), assumindo que o poder de processamento seja suficiente.^[1] O RAID generalizado pode funcionar com qualquer número de discos de redundância. Existem duas notações para o RAID generalizado: RAID 7.${\displaystyle x}$ refere-se a um sistema com ${\displaystyle x}$ discos de redundância, permitindo a recuperação quando até ${\displaystyle x}$ discos falham.^[17] Alternativamente, RAID ${\displaystyle N+M}$ refere-se a ${\displaystyle N}$ discos de dados regulares com ${\displaystyle M}$ discos de redundância, sendo capaz de recuperar todos os dados quando quaisquer ${\displaystyle M}$ discos falham.^[1]

Um exemplo mais avançado é o EC-Cache, um cache de cluster, ou seja, um cache distribuído entre vários nós. Tais sistemas podem sofrer de desequilíbrio de carga quando um nó hospeda itens mais populares, e um método comum para resolver esse problema é a replicação seletiva, ou seja, criar mais réplicas para objetos mais populares. No entanto, esse método é limitado pela quantidade de memória disponível. Dividindo individualmente cada objeto em ${\displaystyle k}$ partes e ${\displaystyle r}$ unidades de redundância, o balanceamento de carga perfeito pode ser alcançado em vez disso, com um mínimo de desperdício de memória.^[12]

Aqui estão alguns exemplos de implementações dos vários códigos:

• Códigos Tornado
• Códigos de verificação de paridade de baixa densidade (LDPC)

• Código Fonte (Fountain code)
• Códigos Online
• Códigos LT
• Códigos Raptor
• Códigos de Rede (Network Codes)
• Códigos triangulares

• Paridade XOR, adicionando um símbolo apagável. Usado em RAID 4, RAID 5.
• Códigos de Reed-Solomon. É ótimo quando usado no modo de apagamento, permitindo ${\displaystyle k}$ apagamentos para ${\displaystyle k}$ símbolos adicionados. Quando usado no modo de correção de erros, também é ótimo, permitindo ${\displaystyle \lfloor k/2\rfloor }$ erros.
  • O formato de arquivo Parchive 1.0, 2.0, e (aberto) 3.0 usa RS. O 3.0 também suporta outros códigos lineares.
  • O RAID 6 usa uma variedade de códigos de apagamento ótimos, mas o RS é uma escolha comum.
  • O Tahoe-LAFS inclui o zfec, uma implementação do RS clássico.
• Erasure Resilient Systematic Code, um código MDS que permite pacotes mais redundantes que o Reed-Solomon no mesmo tamanho de símbolo, veja RS(4,2) com 2 bits ou RS(9,2) com 3 bits.
• Códigos Regeneradores^[18][19]
• Qualquer outro código separável de distância máxima

• Códigos de Correção antecipada de erros (Forward error correction).
• Compartilhamento de segredos (difere por manter o segredo original criptografado e oculto até que o quórum de decodificação seja alcançado)
• Alfabeto de soletração
• Canal de apagamento binário

• Jerasure é uma biblioteca de Software Livre que implementa técnicas de codificação de apagamento de Reed-Solomon e Cauchy com otimizações SIMD.
• Software FEC in computer communications por Luigi Rizzo descreve códigos de correção de apagamento ótimos.
• Feclib é uma extensão quase ótima para o trabalho de Luigi Rizzo que usa matrizes de banda. Muitos parâmetros podem ser definidos, como o tamanho da largura da banda e o tamanho do corpo finito. Ela também explora com sucesso o grande tamanho de registrador das CPUs modernas. Não se sabe como ele se compara aos códigos quase ótimos mencionados acima.
• Coding for Distributed Storage wiki para códigos regeneradores e reconstrução de códigos de apagamento.
• ECIP "Erasure Code Internet Protocol" Desenvolvido em 1996, foi o primeiro uso de FEC (Forward Error Correction) na Internet. Foi usado comercialmente pela primeira vez para transmitir vídeo ao vivo de Sir Arthur C. Clarke no Sri Lanka para a UIUC em Indiana.