Sobre Erasure Coding

A fragilidade dos dados

Imagine o seguinte cenário: um servidor falha. Os dados que estavam nele se perdem. A solução tradicional? Fazer cópias — muitas cópias — desses dados em diferentes lugares. Isso é conhecido como replicação, e tem sido uma prática comum para garantir que nada seja perdido.

Mas será que essa abordagem ainda é a mais eficiente, especialmente quando estamos lidando com terabytes ou até petabytes de informação? Fazer 2 ou 3 cópias de tudo consome muito espaço, largura de banda e claro, muito dinheiro.

E é aqui que entra o Erasure Coding…

O que é Erasure Coding?

Erasure Coding (EC) é uma técnica de proteção e recuperação de dados, criada nos anos 60 por Irvin Reed e Gustave Solomon, que funciona de forma diferente da replicação de dados tradicional. Em vez de simplesmente duplicar os dados, ela os divide em blocos menores, e depois cria blocos extras com informações de paridade. Assim, mesmo que alguns desses blocos sejam perdidos, ainda é possível reconstruir os dados originais através de um algoritimo matemático.

Uma analogia simples: Pense em um quebra-cabeça. Se você perder 2 peças, não consegue ver a imagem completa. Mas se tiver peças extras, que ajudam a preencher os espaços vazios, você consegue restaurar a imagem mesmo com algumas ausências.

Exemplo prático Vamos dizer que temos um arquivo dividido em 4 blocos de dados. Com Erasure Coding, podemos gerar 2 blocos adicionais (blocos de paridade), totalizando 6 blocos.

Qual a mágica? Você só precisa de qualquer 4 desses 6 blocos para reconstruir o arquivo original. Isso significa que você pode perder até 2 blocos sem ficar preocupado.

Esta configuração podemos chamar de (4, 2): 4 blocos de dados, 2 blocos de paridade.

[ D1 ] [ D2 ] [ D3 ] [ D4 ] + [ P1 ] [ P2 ]
  |      |      ✖️     ✖️        |      |
   →   Dados Reconstituídos com 4 blocos

Vantagens sobre a replicação

➡ Eficiência de armazenamento: Em vez de 3 cópias completas, você adiciona apenas uma fração extra.

➡ Alta resiliência: Mesmo com perdas múltiplas, os dados podem ser recuperados.

➡ Escalabilidade: Ideal para sistemas distribuídos, onde replicar tudo seria inviável.

➡ Segurança: Permite de maneira flexível implementar criptografia de dados em repouso e em trânsito, agrega de maneira nativa proteção contra DDoS e diminui consideravelmente o risco de Ransomware por conta do seu design distribuído.

Quem usa Erasure Coding hoje?

Erasure Coding já está por trás de muitos serviços que você nem pode imaginar:

➡ Backblaze: usa EC para armazenar dados com o menor custo possível, mantendo alta confiabilidade.

➡ Facebook (F4 System): aplica EC em seus sistemas internos para salvar espaço e melhorar a resiliência.

➡ Ceph, MinIO: E outros sistemas de armazenamento distribuído oferecem suporte nativo a EC.

➡ Veeam e soluções de backup corporativas: Usam EC em backends compatíveis para proteger dados críticos.

➡ Microsoft Azure: Aplicado em seu código para reconstrução local (LRCs), obtendo alta durabilidade e disponibilidade com armazenamento mais eficiente em comparação com os métodos de replicação tradicionais, reduzindo significativamente os custos de armazenamento.

Cuidados e limitações

Nem tudo são flores. O Erasure Coding também tem seus desafios:

➡ Maior uso de CPU: Requer mais processamento para codificar e decodificar blocos.

➡ Latência maior para arquivos pequenos: Pode não ser ideal para sistemas que lidam com muitos arquivos pequenos em alta velocidade.

➡ Configuração mais complexa: Exige planejamento e entendimento técnico maior do que uma simples replicação.

Mão na Massa!

Neste código eu implemento uma versão simplificada de Erasure Coding baseada em Reed-Solomon, usando operações sobre o campo finito GF(2^8) com a biblioteca pyfinite.

Ele faz o seguinte:

A. Codificação (encode_data): Divide os dados originais em k partes (chunks).

B. Gera n fragmentos (n ≥ k) Aplica uma transformação matemática linear (similar a uma matriz de Vandermonde) para cada fragmento, criando redundância, qualquer k fragmentos entre os n são suficientes para reconstruir os dados.

C. Decodificação (decode_data): Usa k fragmentos disponíveis e seus índices, resolvendo um sistema linear via eliminação gaussiana para recuperar os dados originais.

D. Campo Finito GF(2^8): Todas as operações matemáticas são feitas sobre esse campo, que garante resultados válidos para codificação binária (como arquivos ou bytes).

E. Tolerância a falhas: Simula perda de fragmentos, mesmo que 2 dos 4 fragmentos sejam perdidos, os dados são corretamente recuperados usando os outros 2.

from pyfinite import ffield

# Configuração do campo finito GF(2^8)
F = ffield.FField(8)

# Função para exponenciação no campo finito GF(2^8)
def gf_pow(base, exp, field):
    result = 1
    for _ in range(exp):
        result = field.Multiply(result, base)
    return result

def encode_data(data, n, k):
    """
    Codifica os dados usando Reed-Solomon (erasure coding)
    n = número total de fragmentos
    k = número mínimo de fragmentos necessários para reconstrução
    """
    if len(data) % k != 0:
        data += b'\x00' * (k - (len(data) % k))  # Padding

    fragments = [bytearray() for _ in range(n)]
    chunk_size = len(data) // k

    for i in range(chunk_size):
        chunk = data[i*k : (i+1)*k]

        # Para cada fragmento de saída
        for j in range(n):
            val = 0

            # Calcula o valor do fragmento usando x = j+1 (para evitar x=0)
            for idx, byte in enumerate(chunk):
                power = gf_pow(j + 1, idx, F)  # Corrigido
                product = F.Multiply(byte, power)
                val = F.Add(val, product)

            fragments[j].append(val)

    return fragments

def decode_data(fragments, n, k, fragment_indices):
    """
    Decodifica os dados a partir de k fragmentos disponíveis
    fragment_indices = índices dos fragmentos disponíveis (0-based)
    """
    if len(fragment_indices) < k:
        raise ValueError(f"Precisamos de pelo menos {k} fragmentos para reconstrução")

    available_fragments = [fragments[i] for i in fragment_indices[:k]]
    chunk_size = len(available_fragments[0])
    reconstructed = bytearray()

    for i in range(chunk_size):
        # Construir a matriz Vandermonde
        A = []
        b = []

        for j in range(k):
            x = fragment_indices[j] + 1  # x = índice + 1
            row = [gf_pow(x, m, F) for m in range(k)]  # Corrigido
            A.append(row)
            b.append(available_fragments[j][i])

        # Eliminação Gaussiana
        for col in range(k):
            # Encontrar pivot não-zero
            pivot_row = col
            while pivot_row < k and A[pivot_row][col] == 0:
                pivot_row += 1

            if pivot_row == k:
                continue  # Matriz singular

            # Trocar linhas
            A[col], A[pivot_row] = A[pivot_row], A[col]
            b[col], b[pivot_row] = b[pivot_row], b[col]

            # Normalizar linha atual
            pivot = A[col][col]
            inv_pivot = F.Inverse(pivot)
            for j in range(col, k):
                A[col][j] = F.Multiply(A[col][j], inv_pivot)
            b[col] = F.Multiply(b[col], inv_pivot)

            # Eliminar outras linhas
            for row in range(k):
                if row != col and A[row][col] != 0:
                    factor = A[row][col]
                    for j in range(col, k):
                        A[row][j] = F.Add(A[row][j], F.Multiply(A[col][j], factor))
                    b[row] = F.Add(b[row], F.Multiply(b[col], factor))

        # Os bytes originais estão agora em b
        reconstructed.extend(b[:k])

    return reconstructed

# Let's go o/
if __name__ == "__main__":
    # Dados de exemplo
    original_data = b"Exemplo para Erasure Coding"

    # Configuração (4 fragmentos totais, precisamos de 2 para reconstruir)
    n = 4
    k = 2

    print(f"Dados originais: {original_data.decode()}")
    print(f"Tamanho: {len(original_data)} bytes")

    # Codifica os dados
    fragments = encode_data(original_data, n, k)
    print(f"\nFragmentos gerados (todos {n}):")
    for i, frag in enumerate(fragments):
        print(f"Fragmento {i}: {frag.hex()}")

    # Simula perda de 2 fragmentos (usaremos apenas fragmentos 0 e 3)
    available_indices = [0, 3]
    print(f"\nUsando fragmentos {available_indices} para reconstrução...")

    # Decodifica os dados
    reconstructed = decode_data(fragments, n, k, available_indices)

    # Remove padding se necessário
    reconstructed = reconstructed[:len(original_data)]

    print(f"\nDados reconstruídos: {reconstructed.decode()}")
    print(f"Tamanho: {len(reconstructed)} bytes")

    # Verifica se a reconstrução foi bem-sucedida
    assert reconstructed == original_data, "A reconstrução falhou!"
    print("\nVerificação: Dados reconstruídos são idênticos aos originais!")

Output esperado…

Refs

Conclusão: A nova era da resiliência de dados

Em um mundo onde o volume de dados cresce exponencialmente, proteger sem desperdiçar é essencial. O Erasure Coding oferece uma solução moderna, confiável e econômica para esse desafio.

Se a sua infraestrutura ainda depende exclusivamente de replicação, talvez seja hora de rever essa estratégia. Afinal, quando os dados são o novo petróleo, perder um barril sequer pode custar caro.