Tecnologia de Erasure Coding para sistemas distribuídos
(transactional.blog)- Erasure Coding é uma técnica de compromisso entre eficiência de armazenamento e tolerância a falhas que divide os dados em fragmentos e paridade para suportar falhas com menos espaço de armazenamento do que a replicação completa
- O modelo básico é k+m=n, em que k é o número de fragmentos de dados necessários para recuperação, m é o número de fragmentos de paridade e também o número de falhas toleráveis, e n é o número total de fragmentos
- Em armazenamentos de objetos e blobs, em vez de replicação completa tripla, pode-se usar configurações como 10+5 para distribuir pequenos fragmentos em mais servidores e reduzir o volume armazenado
- Sistemas de quorum têm redução limitada de armazenamento apenas com maioria simples; se, como no HRaft, mudarem para 3+2, 2+2, 1+2 conforme o número de réplicas disponíveis, surgem custos de recodificação e de provisionamento de capacidade
- Na adoção real, é preciso validar a variação do custo de decodificação conforme a combinação de fragmentos recebidos e as diferenças de metadados e exigências de ordenação entre Jerasure, ISA-L e liberasurecode
O compromisso básico entre eficiência de armazenamento e tolerância a falhas
- Existem duas abordagens extremas para armazenar um arquivo em N servidores
- Se houver uma cópia completa do arquivo em todos os servidores, o arquivo não se perde mesmo que N-1 servidores desapareçam, mas o custo de armazenamento é o maior possível
- Se o arquivo for dividido em N fragmentos de tamanho igual e um for armazenado em cada servidor, a eficiência de armazenamento é máxima, mas na leitura são necessários todos os N fragmentos
- Erasure Coding ajusta eficiência de armazenamento e tolerância a falhas entre esses dois extremos
- É possível montar um código que atenda ao objetivo de “dividir o arquivo em N fragmentos, mas permitir recuperação mesmo que M fragmentos sejam destruídos”
- Ele fornece os menores fragmentos possíveis necessários para satisfazer esse objetivo
- A intuição mais simples é o exemplo em que, entre 3 servidores, basta ler quaisquer 2 para obter o arquivo completo
- O arquivo é dividido em dois fragmentos, A e B
- O terceiro fragmento C é criado como A ⊕ B
- Se A e B forem lidos, basta combiná-los; se forem lidos A e C ou B e C, o fragmento faltante é recuperado com XOR
- Todo Erasure Code generaliza esse padrão separando fragmentos de dados e fragmentos de paridade
Modelo k+m=n e sobrecarga de armazenamento
- A configuração de um Erasure Code é expressa como k + m = n
- k: número de fragmentos em que os dados são divididos; para recuperar o valor, é preciso ler pelo menos k fragmentos
- m: número de fragmentos de paridade gerados; também representa o número de falhas de leitura ou falhas toleradas
- n: número total de fragmentos gerados
- O tamanho de cada fragmento resultante é 1/k do arquivo original
- Erasure Code costuma ser chamado pelo tuplo
k+m- Os nomes das variáveis não são consistentes na literatura
x+ysignifica x fragmentos de dados e y fragmentos de paridade
- Isso é atraente para provedores de armazenamento porque oferece tolerância a falhas com baixa sobrecarga de armazenamento
- O Backblaze B2 usa 17+3 para tolerar 3 falhas com 1,18x de espaço de armazenamento
- O OVH Cloud usa código 8+4 para tolerar 4 falhas com 1,5x de espaço de armazenamento
- A Scaleway usa código 6+3 para tolerar 3 falhas com 1,5x de espaço de armazenamento
- O principal custo é a troca entre menos espaço consumido e mais requisições de leitura
- Em vez de ler o tamanho do arquivo em um único disco, envia-se requisição para k+m discos
- Sistemas de armazenamento para dados acessados com pouca frequência são adequados porque a carga extra de IOPS é relativamente pequena e a economia de armazenamento é grande
Escopo dos algoritmos e códigos MDS
- “Erasure Coding” não é um único algoritmo específico, mas uma família de algoritmos
- Códigos Reed-Solomon geralmente podem ser usados para implementar Erasure Codes em configurações arbitrárias de k+m
- Também há correspondência com RAID
- RAID-0 é Erasure Coding k+0
- RAID-1 é Erasure Coding 1+m
- RAID-4 e RAID-5 são formas um pouco diferentes de Erasure Coding k+1
- RAID-6 é Erasure Coding k+2
- O escopo deste texto é o Erasure Code MDS (Minimum Distance Separable)
- Códigos MDS oferecem uma propriedade parecida com quorum, suportando a perda de quaisquer m fragmentos
- Outras famílias de Erasure Code podem recuperar com menos de m fragmentos em algumas combinações, mas em outras podem exigir mais do que m
- Se o padrão de falhas esperado for conhecido, pode ser vantajoso recuperar falhas comuns com menos fragmentos e deixar falhas excepcionais para recuperação com mais fragmentos
- Local Reconstruction Codes e SD Codes do Azure Storage são apresentados como exemplos dessa direção
Aplicação em armazenamento de objetos e cache
- O caso de uso mais direto é reduzir custo de armazenamento e aumentar durabilidade em sistemas com um conjunto fixo de réplicas
- Exemplos incluem armazenamento de blobs, objetos ou armazenamento NFS
- Um serviço de metadados mapeia o caminho do arquivo para os servidores que armazenam aquele arquivo
- Em vez de 3 réplicas, cada uma armazenando o arquivo completo, 15 réplicas podem armazenar os fragmentos de um arquivo com Erasure Coding 10+5
- O volume total de dados armazenados cai pela metade
- A tolerância a falhas aumenta para mais do que o dobro
- Um padrão mais geral é “em vez de armazenar os dados em X servidores, armazená-los em X+m réplicas usando X+m Erasure Code”
- O exemplo de sistema de cache de Marc Brooker aplica esse padrão ao cache
- Em vez de escolher um entre k servidores de cache com hashing consistente, usa-se k+m Erasure Code sobre k+m servidores de cache
- Não é necessário esperar pelas m respostas mais lentas
- É possível melhorar ao mesmo tempo o uso de armazenamento e a latência de cauda
- Essa economia vem acompanhada de aumento em IOPS/QPS ou CPU
- Parte-se do pressuposto de que o recurso limitante do sistema é a capacidade de armazenamento e que há folga de CPU
- Em sistemas já próximos do limite de CPU, isso pode não representar redução de custos
Limites dos sistemas de quorum e HRaft
- Em 5 réplicas, um quorum de maioria simples em que leitura e escrita exigem pelo menos 3 combina bem com Erasure Code 3+2 do ponto de vista de leitura
- Porque a leitura pode ser concluída com o resultado de quaisquer 3 réplicas
- Como a escrita pode ser concluída quando quaisquer 3 réplicas recebem os dados, em um Erasure Code fixo só se pode usar código 1+2
- 1+2 equivale a 3 réplicas completas do arquivo
- Portanto, numa aplicação simples não há economia de armazenamento
- O RS-Paxos considera que, ao aplicar Erasure Code ao Paxos, só há vantagem quando a interseção entre dois quoruns é maior que 1 réplica
- Por exemplo, em 7 réplicas, se leitura e escrita exigirem pelo menos 5, é possível aplicar código 3+2 mantendo tolerância a 2 falhas
- Em geral, com N réplicas e tolerância a falhas desejada f, o melhor possível com Erasure Coding fixo é (N-2f)+f
- O HRaft ajusta a codificação de acordo com o número de réplicas disponíveis, mesmo em quorum de maioria simples
- Se as 5 estiverem disponíveis: 3+2
- Se 4 estiverem disponíveis: 2+2
- Se 3 estiverem disponíveis: 1+2
- A abordagem adaptativa tem potencial de melhora, mas também fortes restrições operacionais
- Cada escrita estima de forma otimista o número atual de réplicas disponíveis
- Se uma réplica inesperadamente não confirmar a escrita, é preciso recodificar a escrita e reenviá-la para todas as réplicas
- Mesmo operando em configuração 1+2 após duas falhas, é preciso provisionar réplicas capazes de armazenar o valor completo para que a disponibilidade não seja quebrada por falta de espaço em disco ou throughput
- Se falhas forem raras e se recuperarem rapidamente, a codificação adaptativa do HRaft pode trazer melhorias significativas
Bibliotecas e exemplos de uso
- Para o cálculo de Erasure Coding, existe a biblioteca padrão madura Jerasure
- Em processadores Intel modernos, a Intelligent Storage Acceleration Library da Intel é uma biblioteca com otimização SIMD e aparece com frequência entre os melhores benchmarks
- Em Python, é possível acessar implementações de Erasure Coding com pyeclib
- O exemplo usa o driver
liberasurecode_rs_vand - Cada fragmento recebe na frente metadados para identificação de posição
- Também há alguns bytes adicionais
- O exemplo usa o driver
- Os resultados de exemplo do HRaft por quantidade de réplicas disponíveis são os seguintes
- 3+2, original de 10000 bytes: 5 fragmentos, 3355 bytes por fragmento, total real de 16775 bytes, eficiência de 59,61%
- 2+2, original de 10000 bytes: 4 fragmentos, 5021 bytes por fragmento, total real de 20084 bytes, eficiência de 49,79%
- 1+2, original de 10000 bytes: 3 fragmentos, 10021 bytes por fragmento, total real de 30063 bytes, eficiência de 33,26%
- A codificação Erasure 1+2 equivale a 3 réplicas completas dos dados, ou seja, é o mesmo que não aplicar Erasure Encoding
Custo de decodificação e diferenças entre implementações
- O desempenho da decodificação varia conforme o número de fragmentos de dados que precisam ser recuperados
- Decodificar um código 3+2 com 3 fragmentos de dados é computacionalmente quase trivial
- Para decodificar o mesmo arquivo com 2 fragmentos de dados e 1 fragmento de paridade, é preciso resolver um sistema de equações lineares com eliminação de Gauss
- Quanto maior o número de fragmentos de paridade necessários, maior o volume de cálculo
- Em sistemas de quorum, ao usar Erasure Code, o custo de CPU pode variar dependendo exatamente de quais réplicas responderam
- O liberasurecode abstrai bibliotecas comuns de implementação de Erasure Coding, mas isso não significa que as implementações sejam equivalentes entre si
- O fato de dois códigos serem ambos 3+2 não significa que tenham sido construídos com a mesma matemática
- O liberasurecode adiciona metadados necessários não só para operações de álgebra linear, mas também para configurar e usar o decodificador
- Esses metadados não podem ser desativados nem modificados
- Ao usar Jerasure ou ISA-L diretamente, é possível lidar apenas com os dados codificados por Erasure Code
- Porém, como a API exige informar se cada fragmento é o N-ésimo fragmento de dados ou de paridade, os índices precisam ser mantidos como metadados de alguma forma
- Jerasure e ISA-L também diferem nas exigências de ordenação
- O Jerasure aplica uma permutação ao resultado esperado da álgebra linear
- O Jerasure não consegue ler de forma não ordenada um subconjunto ou superconjunto do que foi codificado
- O ISA-L não aplica essa permutação, então consegue decodificar subconjuntos ou superconjuntos não ordenados
- Outras implementações também entram como opção
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- Se isso virar gargalo, pode valer procurar uma biblioteca mais otimizada para um caso de uso específico, mas o ISA-L geralmente é bom o suficiente
Escolha de algoritmo e construção matemática
- Na prática, não há problema em tratar Erasure Code como uma função mágica que transforma 1 arquivo em n fragmentos e depois o reconstrói
- Uma construção com n fragmentos normalmente é feita com álgebra linear usando Galois Field
- Não é obrigatório entender essa matemática para usar Erasure Code em produção
- A maioria dos códigos MDS é calculada por multiplicação de matrizes
- A soma é substituída por XOR
- A multiplicação é substituída por uma multiplicação mais cara sobre GF(256)
- Para casos especiais com 1 a 3 fragmentos de paridade, existem algoritmos dedicados a XOR em vez de Reed-Solomon
- m=1: um único fragmento de paridade que é o XOR de todos os fragmentos de dados
- m=2: equivalente ao RAID-6, com menção a Liberation codes, HDP codes, EVENODD e X-Codes
- m=3: possível com STAR coding
- No caso geral, usa-se a família Reed-Solomon
- São usadas construções com matriz de Vandermonde ou matriz de Cauchy
- O objetivo é que o bloco superior k×k seja a matriz identidade, preservando cada fragmento de dados, e que ainda exista matriz inversa mesmo após remoção de m linhas
- Codificar consiste em multiplicar essa matriz; decodificar consiste em remover as linhas correspondentes aos fragmentos apagados e resolver o sistema de equações lineares
- A eliminação de Gauss usada pelo ISA-L é o método de decodificação mais simples, mas também o mais lento
- Em matrizes de Cauchy, isso pode ser melhorado, e catid/cm256 usa essa abordagem
- O método mais rápido atualmente parece ser o implementado em catid/leopard, que usa Fast Fourier Transform para codificação e decodificação
Etapas de otimização de implementação
- Há várias etapas para tornar rápida uma implementação de Erasure Code que funcione em configurações arbitrárias de k+m
- A primeira etapa é implementar o algoritmo em C e confiar na vetorização automática do compilador
- É a abordagem mais simples e mais portátil
- O uso de
restricte a definição de flags de compilação específicas da arquitetura, como-march=native, são importantes
- A segunda etapa é abstrair detalhes da plataforma com bibliotecas de vetorização ou intrinsics do compilador
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- builtins de extensão vetorial do GCC
- O núcleo de codificação e decodificação está na multiplicação e soma em Galois Field
- Como bibliotecas otimizadas, são mencionadas catid/gf256 e James Plank’s Fast Galois Field Arithmetic Library
- A terceira etapa é escrever diretamente vetorizadas as funções centrais de codificação e decodificação
- O projeto PARPAR, com fast-gf-multiplication e xor_depends work, aborda operações rápidas em GF(256)
- O texto resume que há consenso de que multiplicação GF dedicada a XOR é mais rápida do que multiplicação baseada em tabelas
- Também é possível ir além e especializar o código para uma configuração específica de k+m
- Busca-se a melhor matriz de codificação e o melhor cronograma de XOR para um polinômio GF e uma matriz de codificação específicos
- Aplicam-se otimizações de operação, memória e cache
- É possível explorar por programa o melhor escalonamento de instruções para uma arquitetura específica
- Como implementações e materiais relacionados, são apresentados yuezato/xorslp_ec, Thesys-lab/tvm-ec e "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques"
Materiais para aprofundamento
- Como introdução à álgebra linear de Erasure Coding, os links a seguir são úteis
- Introdução básica do Backblaze: básica
- Fred Akalin: "A Gentle Introduction to Erasure Codes"
- "Reed-Solomon Error Correcting Codes from the Bottom Up"
- NASA: Tutorial on Reed-Solomon Error Correction Coding
- Para se aprofundar de forma ampla, sugere-se começar pelas publicações de James S. Plank
1 comentários
Opiniões do Hacker News
Fiquei surpreso por códigos fountain sem taxa fixa não terem sido mencionados. Se você gosta desse tipo de tema, o Luby Transform Code deve ser interessante: https://en.wikipedia.org/wiki/Luby_transform_code
Este artigo também é bom como uma visão geral mais detalhada: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
Códigos LT são usados como código externo na codificação RaptorQ de tempo linear especificada na RFC6330: https://www.rfc-editor.org/rfc/rfc6330
Em segundo lugar, o algoritmo na prática se divide em duas partes: a segunda, a geração de blocos de recuperação, é linear, mas a primeira leva tempo cúbico em relação ao número de mensagens agrupadas em um bloco. É quase uma eliminação gaussiana de matrizes
Dá para armazenar em cache partes da codificação e da decodificação, mas a codificação em tempo linear do RaptorQ é, na prática, um slogan de marketing
Há algum tempo, alguém propôs um algoritmo bonitinho de erasure coding que dependia não de discos giratórios, mas de rede multipath
Acho que chamavam isso de network coding, e a ideia era que, em uma rede com múltiplos caminhos, em vez de esperar pelo arquivo inteiro do servidor principal, você receberia de um upstream duas partes do arquivo, ou um código de apagamento misturando dois arquivos, para obter o arquivo mais rápido
Imagino que haja bastante disso por trás do S3 ou de outros sistemas de armazenamento em nuvem, especialmente em camadas de armazenamento de acesso pouco frequente. Mas não é que eu realmente conheça os sistemas internos da AWS ou do GCP
Para referência, o Freenet usa pelo menos arquivos codificados com FEC, o que dá flexibilidade sobre quais fragmentos receber e reduz a chance de o arquivo inteiro quebrar porque um único fragmento desapareceu
Erasure coding existe há muito tempo. Lembra dos arquivos PAR2 da Usenet? https://en.wikipedia.org/wiki/Parchive
Se você se interessa por erasure coding, também vale considerar casos multidimensionais maiores. Não é só codificar entre vários discos, mas também levar em conta outros domínios de falha, como racks, salas, data centers e regiões
O objetivo é tolerar não apenas falhas de componentes comuns, mas também falhas ou partições maiores do sistema. Um bom texto introdutório: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
Se o cabo submarino transoceânico tiver só 1 Tbps, mover todos os dados pode levar mais de 6 meses
Fico curioso se alguém já usou o Wirehair em um projeto: https://github.com/catid/wirehair
Quero saber se ele é bem definido o suficiente para servir como base de um padrão para um projeto de arquivamento de arquivos grandes/recuperação de dados que venho concebendo há quase 10 anos. Mesmo que não seja um padrão oficial, gostaria de saber se dá para usá-lo como um padrão de facto
Entre os códigos de apagamento para blocos grandes que encontrei até agora, este é o único que tem tanto desempenho de algoritmo ideal, ou quase ideal, quanto uma boa API. Por isso, para o meu uso, ele funciona como uma boa caixa-preta, ao contrário do RaptorQ, em que pequenos detalhes vazam por todos os lados e aumentam a complexidade e a rigidez do restante da pilha
Só que o Wirehair não é uma especificação, é uma implementação de uma ideia, e também parece uma implementação experimental. Ele parece estável, mas fico preocupado se será fácil confiar nele como uma especificação confiável, ou migrar para uma segunda implementação, até que eu mesmo escreva essa segunda implementação ou até que ele seja usado de forma ampla o suficiente para que as arestas afiadas do algoritmo apareçam
Só que a Qualcomm poderia alegar que ele infringe as patentes do RaptorQ, porque os conceitos são relacionados. As patentes mais antigas entre elas devem expirar em breve, ou talvez já tenham expirado, mas não verifiquei os wrappers de arquivos mais recentes. A Qualcomm fez algumas promessas de não aplicar as patentes do RaptorQ fora do contexto sem fio, mas não lembro se isso se aplica apenas a implementações conformes
Para usá-lo no protocolo principal do Bitcoin, seria necessário especificá-lo, então cheguei a analisar o que seria preciso. Eu e alguns desenvolvedores do Bitcoin somos bastante familiarizados com teoria dos números e códigos de correção de erros, mas esse trabalho não nos pareceu muito atraente. A estrutura do Wirehair tem uma boa quantidade de detalhes ad hoc, e, pelo nosso perfil, poderíamos acabar caindo em armadilhas ao tentar melhorá-la
Pode ser que volte a haver interesse em usar fountain codes de forma ampla no lado do Bitcoin, então, se você esperar um pouco, talvez alguém escreva uma especificação
Dependendo do uso exato, https://github.com/catid/fecal também pode ser interessante. Se o número esperado de apagamentos for muito baixo, ele pode ser mais rápido que o Wirehair
O Leopard mencionado no texto não é um fountain code, mas tem um tamanho de bloco bem grande. Em termos de especificação, isso é uma vantagem: é apenas uma implementação muito rápida do velho e tedioso código Reed-Solomon, então talvez a especificação só precise documentar o campo e a escolha do gerador
Certo. Essa é a tecnologia central por trás dos pools com Erasure Code do Ceph: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
Mas isso não vem sem custo. Depois, não dá para alterar os parâmetros de codificação k, m, então é preciso ter certeza de que esses valores vão continuar corretos por muito tempo, ou começar tudo de novo do zero
Por causa dessa falta de elasticidade, a replicação ainda é a escolha dominante para armazenamento de dados tolerante a falhas e de alta disponibilidade
Ele simplesmente usa
--forcee deixa para trás um sistema de arquivos corrompidoTalvez seja só aquele tipo de engraçado “era para você ter estado lá para rir, e não eu”
É correto que o artefato produzido em uma situação de falha em que só M de N estão disponíveis seja codificado de forma diferente de quando todos os N estão disponíveis? Se for, parece que deveria haver um bit flag indicando “recodificação necessária quando N for recuperado”
Caso contrário, ficam arquivos que não têm uma resiliência muito boa quando ocorre uma perda arbitrária dentro do conjunto N
Todo sistema de armazenamento distribuído precisa de algum tipo de bibliotecário que verifique e arrume as stripes para tirá-las do estado de risco
Também me vem à mente o algoritmo de dispersão de informação de Rabin. Ele é descrito neste artigo:
https://dl.acm.org/doi/10.1145/62044.62050
Na prática, isso só é viável para workloads somente leitura ou com leitura muito intensa?