Tecnología de Erasure Coding para sistemas distribuidos
(transactional.blog)- Erasure Coding es una técnica de compromiso entre eficiencia de almacenamiento y tolerancia a fallas que divide los datos en fragmentos y paridad para resistir fallas usando menos espacio que la replicación completa
- El modelo básico es k+m=n, donde k es la cantidad de fragmentos de datos necesarios para la recuperación, m es la cantidad de fragmentos de paridad y también la cantidad de fallas tolerables, y n es la cantidad total de fragmentos
- En almacenes de objetos y blobs, en lugar de replicación completa triple se pueden usar configuraciones como 10+5, colocando fragmentos pequeños en más servidores y reduciendo la cantidad almacenada
- En sistemas de quorum, el ahorro de almacenamiento queda limitado con una mayoría simple; si, como HRaft, se cambia entre 3+2, 2+2, 1+2 según la cantidad de réplicas disponibles, aparecen cargas de re-encoding y aprovisionamiento de capacidad
- Para adoptarlo en la práctica, hay que validar la variación del costo de decodificación según la combinación de fragmentos que respondan y las diferencias en requisitos de metadatos y alineación entre Jerasure, ISA-L y liberasurecode
El compromiso básico entre eficiencia de almacenamiento y tolerancia a fallas
- Hay dos formas extremas de almacenar un archivo en N servidores
- Si se coloca una réplica completa del archivo en todos los servidores, no se pierde el archivo aunque desaparezcan N-1 servidores, pero el costo de almacenamiento es el mayor
- Si el archivo se divide en N fragmentos de igual tamaño y se guarda uno en cada servidor, la eficiencia de almacenamiento es la mejor, pero para leer se necesitan los N fragmentos
- Erasure Coding ajusta la eficiencia de almacenamiento y la tolerancia a fallas entre esos dos extremos
- Permite construir un código acorde al objetivo: “dividir el archivo en N fragmentos, pero poder recuperarlo aunque se destruyan M fragmentos”
- Proporciona los fragmentos del tamaño mínimo necesario para cumplir ese objetivo
- La intuición más simple es un ejemplo en el que se obtiene el archivo completo leyendo cualquier par de 2 servidores entre 3
- Se divide el archivo en dos fragmentos A y B
- El tercer fragmento C se crea como A ⊕ B
- Si se leen A y B, se combinan tal cual; si se leen A y C o B y C, se recupera el fragmento faltante con XOR
- Todos los Erasure Codes generalizan este patrón separando fragmentos de datos y fragmentos de paridad
Modelo k+m=n y overhead de almacenamiento
- La configuración de un Erasure Code se expresa como k + m = n
- k: cantidad de fragmentos en que se dividen los datos; para recuperar el valor se deben leer al menos k fragmentos
- m: cantidad de fragmentos de paridad que se generan; es la cantidad de fallas de lectura o fallas tolerables que pueden no completarse
- n: cantidad total de fragmentos generados
- El tamaño de cada fragmento resultante es 1/k del archivo original
- Un Erasure Code suele nombrarse como una tupla
k+m- Los nombres de variables no son consistentes entre publicaciones
x+ysignifica x fragmentos de datos e y fragmentos de paridad
- La razón por la que resulta atractivo para proveedores de almacenamiento es que ofrece tolerancia a fallas con bajo overhead de almacenamiento
- Backblaze B2 usa 17+3 y tolera 3 fallas con 1.18 veces el espacio de almacenamiento
- OVH Cloud usa un código 8+4 y tolera 4 fallas con 1.5 veces el espacio de almacenamiento
- Scaleway usa un código 6+3 y tolera 3 fallas con 1.5 veces el espacio de almacenamiento
- El costo principal es el intercambio entre menor espacio de almacenamiento y mayor cantidad de solicitudes de lectura
- En lugar de leer el tamaño del archivo desde un solo disco, se envían solicitudes a k+m discos
- Los sistemas de almacenamiento para datos poco accedidos son adecuados porque la carga adicional de IOPS es relativamente menor y el ahorro de almacenamiento es grande
Alcance de algoritmos y códigos MDS
- “Erasure Coding” no es un algoritmo específico, sino una familia de algoritmos
- Los códigos Reed-Solomon suelen poder usarse para implementar Erasure Codes con configuraciones k+m arbitrarias
- También existe correspondencia con RAID
- RAID-0 es Erasure Coding k+0
- RAID-1 es Erasure Coding 1+m
- RAID-4 y RAID-5 son Erasure Coding k+1 ligeramente distinto
- RAID-6 es Erasure Coding k+2
- El alcance de este artículo son los Erasure Codes MDS (Minimum Distance Separable)
- Los códigos MDS ofrecen una propiedad similar a quorum que tolera la pérdida de cualquier combinación de m fragmentos
- Otras familias de Erasure Codes pueden recuperar con menos de m fragmentos en algunas combinaciones, pero en otras pueden requerir más de m fragmentos
- Si se conocen los patrones de fallas esperados, puede convenir recuperar las fallas frecuentes con menos fragmentos y las fallas excepcionales con más fragmentos
- Local Reconstruction Codes y SD Codes de Azure Storage se tratan como ejemplos en esa dirección
Aplicación en almacenes de objetos y cachés
- El caso de uso más directo es reducir el costo de almacenamiento y aumentar la durabilidad en sistemas con un conjunto fijo de réplicas
- Ejemplos: almacenamiento de blobs, objetos o NFS
- Un servicio de metadatos mapea la ruta del archivo a los servidores que lo almacenan
- En lugar de que 3 réplicas guarden cada una el archivo completo, 15 réplicas pueden almacenar fragmentos de un archivo codificado con Erasure Coding 10+5
- La cantidad total de datos almacenados se reduce a la mitad
- La tolerancia a fallas aumenta a más del doble
- Un patrón más general es “en lugar de almacenar datos en X servidores, almacenarlos en X+m réplicas con un Erasure Code X+m”
- El ejemplo de sistema de caché de Marc Brooker aplica este patrón a cachés
- En lugar de elegir uno de k servidores de caché con hashing consistente, usa Erasure Code k+m en k+m servidores de caché
- No hace falta esperar las m respuestas más lentas
- Se pueden mejorar al mismo tiempo el espacio de almacenamiento y la latencia de cola
- Este ahorro viene acompañado de costos en forma de mayor IOPS/QPS o CPU
- Se necesita la premisa de que el recurso limitante del sistema es la capacidad de almacenamiento y que hay holgura de CPU
- En sistemas que ya están cerca del límite de CPU, puede no ser una idea de reducción de costos
Límites de los sistemas de quorum y HRaft
- Un quorum de mayoría simple con 5 réplicas, donde tanto lecturas como escrituras requieren al menos 3 réplicas, encaja bien con Erasure Code 3+2 desde el lado de lectura
- Porque una lectura puede completarse con los resultados de cualquier conjunto de 3 réplicas
- Una escritura puede completarse si la recibe cualquier conjunto de 3 réplicas, así que con un Erasure Code fijo solo se puede usar un código 1+2
- 1+2 equivale a 3 réplicas completas del archivo
- Con una aplicación simple no hay ahorro de almacenamiento
- RS-Paxos considera que, al aplicar Erasure Code a Paxos, solo hay ventaja cuando la intersección de dos quorums es mayor que 1 réplica
- Por ejemplo, si con 7 réplicas tanto lecturas como escrituras requieren al menos 5, la tolerancia a fallas es de 2 y se puede aplicar un código 3+2
- En general, con N réplicas y una tolerancia a fallas deseada f, lo mejor posible con Erasure Coding fijo es (N-2f)+f
- HRaft ajusta la codificación según la cantidad de réplicas disponibles incluso con quorum de mayoría simple
- Si las 5 están disponibles: 3+2
- Si hay 4 disponibles: 2+2
- Si hay 3 disponibles: 1+2
- El enfoque adaptativo tiene margen de mejora, pero también grandes restricciones operativas
- Cada escritura estima de forma optimista la cantidad actual de réplicas disponibles
- Si una réplica inesperadamente no confirma la escritura, hay que recodificarla y volver a enviarla a todas las réplicas
- Incluso al operar con configuración 1+2 después de dos fallas, hay que aprovisionar una configuración de réplicas capaz de almacenar el valor completo para que la disponibilidad no se rompa por falta de espacio en disco o throughput
- Si las fallas son raras y se recuperan rápido, la codificación adaptativa de HRaft ofrece una mejora considerable
Bibliotecas y ejemplos de uso
- Para cálculos de Erasure Coding existe una biblioteca estándar madura: Jerasure
- En procesadores Intel modernos, Intel Intelligent Storage Acceleration Library es una biblioteca optimizada con SIMD y se ubica consistentemente entre las mejores en benchmarks
- En Python se puede acceder a implementaciones de Erasure Coding con pyeclib
- El ejemplo usa el driver
liberasurecode_rs_vand - Cada fragmento lleva al inicio metadatos para identificar su posición
- También existen algunos bytes adicionales
- El ejemplo usa el driver
- Los resultados de ejemplo de HRaft según la cantidad de réplicas disponibles son los siguientes
- 3+2, original de 10000 bytes: 5 fragmentos, 3355 bytes por fragmento, total real 16775 bytes, eficiencia 59.61%
- 2+2, original de 10000 bytes: 4 fragmentos, 5021 bytes por fragmento, total real 20084 bytes, eficiencia 49.79%
- 1+2, original de 10000 bytes: 3 fragmentos, 10021 bytes por fragmento, total real 30063 bytes, eficiencia 33.26%
- Erasure Encoding 1+2 equivale a 3 réplicas completas de los datos, por lo que es igual a no aplicar Erasure Encoding
Costo de decodificación y diferencias entre implementaciones
- El rendimiento de decodificación varía según la cantidad de fragmentos de datos que haya que recuperar
- Decodificar un código 3+2 con 3 fragmentos de datos es computacionalmente casi trivial
- Para decodificar el mismo archivo con 2 fragmentos de datos y 1 fragmento de paridad hay que resolver un sistema de ecuaciones lineales con eliminación gaussiana
- Mientras más fragmentos de paridad se necesiten, mayor es el cómputo
- Al usar Erasure Code en un sistema de quorum, el costo de CPU puede variar según exactamente qué réplicas respondieron
- liberasurecode abstrae bibliotecas comunes de implementación de Erasure Coding, pero eso no significa que las implementaciones sean equivalentes entre sí
- Que dos códigos sean 3+2 no significa que estén construidos con la misma matemática
- liberasurecode agrega no solo operaciones de álgebra lineal, sino también metadatos necesarios para configurar y usar el decoder
- Estos metadatos no pueden desactivarse ni modificarse
- Al usar Jerasure o ISA-L directamente, se puede manejar solo datos codificados con Erasure Coding
- Sin embargo, por API hay que entregar junto con cada fragmento si es el N-ésimo fragmento de datos o de paridad, por lo que el índice debe mantenerse como metadatos de alguna manera
- Jerasure e ISA-L también difieren en requisitos de ordenamiento
- Jerasure aplica una permutación a la salida esperada del álgebra lineal
- Jerasure no puede leer de forma desordenada un subconjunto o superconjunto de lo que codificó
- ISA-L no aplica permutación, por lo que permite decodificar subconjuntos o superconjuntos desordenados
- Hay otras implementaciones disponibles
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- Si se vuelve un cuello de botella, se puede buscar una biblioteca más optimizada para el caso de uso específico, pero ISA-L suele ser suficientemente buena
Selección de algoritmo y construcción matemática
- En la práctica, se puede tratar Erasure Code como una función mágica que convierte 1 archivo en n fragmentos y luego lo recupera
- La construcción de n fragmentos generalmente se hace con álgebra lineal usando Galois Field
- No es necesario entender esta matemática para usar Erasure Code de forma productiva
- La mayoría de los códigos MDS se calculan con multiplicación de matrices
- La suma se reemplaza por XOR
- La multiplicación se reemplaza por una multiplicación más costosa sobre GF(256)
- Para casos especiales con 1 a 3 fragmentos de paridad, existen algoritmos solo con XOR que no son Reed-Solomon
- m=1: un único fragmento de paridad que es el XOR de todos los fragmentos de datos
- m=2: corresponde a RAID-6; se mencionan Liberation codes, HDP codes, EVENODD, X-Codes, entre otros
- m=3: es posible con STAR coding
- En el caso general se usa la familia Reed-Solomon
- Se usan construcciones con matriz de Vandermonde o matriz de Cauchy
- El objetivo es que el bloque superior k×k sea la matriz identidad, preservando cada fragmento de datos, y que siga existiendo una matriz inversa incluso después de eliminar m filas
- Codificar es multiplicar por esta matriz, y decodificar es eliminar las filas correspondientes a los fragmentos borrados y luego resolver un sistema de ecuaciones lineales
- La eliminación gaussiana que usa ISA-L es el método de decodificación más simple, pero también el más lento
- Con matrices de Cauchy se puede mejorar, y catid/cm256 usa ese enfoque
- El método más rápido actualmente parece estar implementado en catid/leopard, que usa Fast Fourier Transform para codificar y decodificar
Pasos para eficientizar la implementación
- Hay varias etapas para hacer rápida una implementación de Erasure Code que funcione con configuraciones k+m arbitrarias
- La primera etapa es implementar el algoritmo en C y depender de la autovectorización del compilador
- Es la opción más simple y portable
- Es importante usar
restricty especificar flags de compilación por arquitectura como-march=native
- La segunda es abstraer detalles de plataforma con bibliotecas de vectorización o intrinsics del compilador
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- builtins de extensión vectorial de GCC
- El núcleo de la codificación y decodificación es la multiplicación y suma en Galois Field
- Como bibliotecas optimizadas se mencionan catid/gf256 y James Plank’s Fast Galois Field Arithmetic Library
- La tercera es escribir directamente las funciones centrales de codificación y decodificación vectorizadas
- fast-gf-multiplication y xor_depends work del proyecto PARPAR tratan operaciones rápidas de GF(256)
- Se resume que hay consenso en que la multiplicación GF solo con XOR es más rápida que la multiplicación basada en tablas
- Más allá de eso, se puede especializar el código para una configuración k+m específica
- Se busca la matriz de codificación y el cronograma de XOR óptimos para un polinomio GF y una matriz de codificación específicos
- Se aplican optimizaciones de operaciones, memoria y caché
- Se explora programáticamente el cronograma óptimo de instrucciones para una arquitectura específica
- Como implementaciones y materiales relacionados se presentan yuezato/xorslp_ec, Thesys-lab/tvm-ec y "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques"
Materiales para profundizar
- Los siguientes enlaces son útiles como introducciones al álgebra lineal de Erasure Coding
- Para profundizar ampliamente, se sugiere empezar revisando las publicaciones de James S. Plank
1 comentarios
Opiniones en Hacker News
Me sorprende que no se hayan mencionado los códigos fountain sin tasa fija. Si te gusta este tema, el Luby Transform Code te va a parecer interesante: https://en.wikipedia.org/wiki/Luby_transform_code
Este paper también sirve como una introducción más detallada: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
Los códigos LT se usan como código externo en la codificación RaptorQ de tiempo lineal especificada en RFC6330: https://www.rfc-editor.org/rfc/rfc6330
En segundo lugar, el algoritmo en realidad se divide en dos partes: la segunda, la generación de bloques de recuperación, es lineal, pero la primera toma tiempo cúbico respecto de la cantidad de mensajes que se agrupan en un bloque. Es prácticamente eliminación gaussiana de matrices
Se pueden cachear partes de la codificación y decodificación, pero considero que la codificación en tiempo lineal de RaptorQ es básicamente una frase de marketing
Hace tiempo alguien propuso un algoritmo simpático de código de borrado que no dependía de discos giratorios, sino de redes multipath
Creo que lo llamaban network coding, y la idea era que, en una red con varias rutas, en vez de esperar el archivo completo desde el servidor principal, recibías de un upstream dos partes de un archivo, o un código de borrado que mezclaba dos archivos, para obtener el archivo más rápido
Sospecho que hay mucho de esto detrás de S3 y otros sistemas de almacenamiento en la nube, sobre todo en capas de almacenamiento de acceso poco frecuente. Aunque no es que conozca realmente los sistemas internos de AWS o GCP
Como referencia, Freenet usa al menos archivos codificados con FEC, lo que da flexibilidad sobre qué piezas recibir y reduce la posibilidad de que todo el archivo se rompa porque desapareció una sola pieza
La codificación de borrado existe desde hace muchísimo tiempo. ¿Recuerdan los archivos PAR2 de Usenet? https://en.wikipedia.org/wiki/Parchive
Si te interesa la codificación de borrado, vale la pena considerar también casos multidimensionales más grandes. No se trata solo de codificar a través de varios discos, sino de pensar también en otros dominios de falla, como racks, salas, centros de datos y regiones
El objetivo es resistir no solo fallas de componentes comunes, sino también fallas mayores del sistema o particiones. Buen artículo introductorio: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
Si el cable transoceánico de fibra óptica solo tiene 1 Tbps, mover todos los datos podría tomar más de 6 meses
Me pregunto si alguien ha usado Wirehair en algún proyecto: https://github.com/catid/wirehair
Me pregunto si está lo suficientemente bien definido como para tomarlo como base estándar para un proyecto de archivado de archivos grandes/recuperación de datos que vengo imaginando desde hace casi 10 años. Quisiera saber si, aunque no sea un estándar oficial, puede usarse como si fuera un estándar de facto
De todos los códigos de borrado para bloques grandes que he encontrado hasta ahora, es el único que tiene tanto un rendimiento de algoritmo ideal o casi ideal como una API ideal o casi ideal. Por eso, a diferencia de RaptorQ, donde pequeños detalles se filtran por todas partes y aumentan la complejidad y la rigidez del resto del stack, para mi caso de uso funciona como una buena caja negra
Dicho eso, Wirehair no es una especificación sino una implementación de una idea, y también parece una implementación experimental. Se ve estable, pero hasta que escriba una segunda implementación yo mismo o se use lo suficiente como para que salgan a la luz las aristas filosas del algoritmo, me preocupa si será fácil trasladarlo a una especificación confiable o a una segunda implementación
Dicho eso, Qualcomm podría afirmar que infringe sus patentes de RaptorQ, porque están relacionadas conceptualmente. Las patentes más antiguas de ese conjunto deberían estar por vencer o ya haber vencido, pero no he revisado los wrappers de archivos más recientes. Qualcomm hizo algunas promesas de no aplicar las patentes de RaptorQ fuera del ámbito inalámbrico, pero no recuerdo si eso solo cubre implementaciones conformes
Para usarlo en el protocolo principal de Bitcoin habría que especificarlo, así que en algún momento revisé qué haría falta. Yo y algunos desarrolladores de Bitcoin estamos bastante familiarizados con teoría de números y códigos de corrección de errores, pero ese trabajo no nos entusiasmaba demasiado. La estructura de Wirehair tiene bastantes detalles ad hoc, y por nuestra forma de ser podríamos caer en la trampa de intentar mejorarla
Es posible que vuelva a haber interés en usar ampliamente códigos fountain en el lado de Bitcoin, así que si esperas un poco quizá alguien escriba una especificación
Según el uso exacto, https://github.com/catid/fecal también podría ser interesante. Si la cantidad esperada de borrados es muy baja, puede ser más rápido que Wirehair
Leopard, mencionado en el artículo, no es un código fountain, pero el tamaño de bloque es bastante grande. En cuanto a especificación tiene ventajas, porque es simplemente una implementación muy rápida de un aburrido código Reed-Solomon, así que en la especificación quizá solo haría falta documentar el campo y la elección de generadores
Correcto. Esta es la tecnología central detrás de los pools de Erasure Code de Ceph: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
Pero no es gratis. No se pueden cambiar después los parámetros de codificación k, m, así que tienes que estar seguro de que esos valores seguirán siendo adecuados durante mucho tiempo, o empezar de nuevo desde cero
Por esta falta de elasticidad, la replicación sigue siendo la opción dominante para almacenamiento de datos con alta disponibilidad y tolerancia a fallas
Simplemente usa
--forcey deja un sistema de archivos dañadoQuizá solo sea el tipo de gracia de “tenías que estar ahí para reírte, y ojalá no hubiera sido yo”
¿Es correcto que un resultado generado en una situación de falla donde solo M de N están disponibles se codifique de forma distinta a cuando los N están disponibles? Si es así, parecería que debería haber un bit de bandera que indique “cuando N se recupere, hace falta recodificar”
Si no, quedan archivos con una resiliencia no muy buena ante pérdidas arbitrarias dentro del conjunto N
Todo sistema de almacenamiento distribuido necesita algún tipo de bibliotecario que revise y ordene las stripes para sacarlas del estado de riesgo
También me viene a la mente el algoritmo de dispersión de información de Rabin. Está descrito en este paper:
https://dl.acm.org/doi/10.1145/62044.62050
¿En la práctica solo es viable para cargas de trabajo de solo lectura o con muchísimas lecturas?