erasure-coding.js·5 scenarios
Erasure coding (Reed-Solomon k=6, m=3) concept page. Client communicates with RS Encoder/Decoder which split objects into 6 data + 3 parity shards distributed across 3 racks (AZ-1, AZ-2, AZ-3). Five scenarios: WRITE encode, READ fast path, single rack failure recovery, catastrophic loss beyond m, and storage cost comparison with replication.
3x репликация — стандартный путь к durability: храни 3 копии объекта, переживёшь потерю любых 2. Просто, быстро, безотказно работает в продакшене. Но на петабайтах стоит до неприличия: на 1 PB полезных данных тратишь 3 PB сырых дисков плюс 3x write bandwidth. Для S3, Backblaze, Facebook это миллионы долларов в год только на оборудование, не считая электричества и охлаждения.
Erasure coding — математическая альтернатива. Вместо копий храним «уравнения», восстанавливающие данные из любых k фрагментов из (k+m). Тот же уровень durability (11+ nines) — за 33-50% overhead вместо 200%. На петабайтах это экономия storage в 4-6 раз. Поэтому EC живёт везде, где доминирует storage cost: S3, Glacier, B2, Azure Blob, HDFS, Ceph, MinIO.
Цена — read/write амплификация, дорогой CPU на encode/decode, тяжёлая reconstruction при failures. Поэтому EC почти всегда = cold/warm tier, а hot tier остаётся replicated. Понимать, когда переключаться между стратегиями, — навык, отличающий junior-архитектора от того, кто умеет считать TCO.
Replication = храни 3 копии, потеряй 2 — выживешь. Erasure coding = храни k+m шардов, потеряй любые m из (k+m) — восстановишь через линейную алгебру. Дешевле по storage, дороже по CPU/IO/latency при чтении и recovery.
EC(k, m) — это контракт: «делю объект на k data-шардов, считаю m parity-шардов, раскидываю k+m по разным fault domains, переживаю ровно m одновременных failures». Не больше, не меньше — m+1 одновременных потерь = data loss навсегда.
Reed-Solomon (RS) — классическая MDS-схема (Maximum Distance Separable): оптимальная по storage overhead, никакая EC-схема не может быть дешевле при том же m. LRC (Local Reconstruction Codes, Azure) жертвует чуть-чуть overhead ради быстрой single-failure reconstruction — читаем не все k шардов, а локальную группу 3-4.
На канвасе EC(6, 3) — 6 data shards + 3 parity, 9 шардов всего, раскиданы по 3 racks (AZ-1/2/3) по 3 шарда в каждом.
client, encoder (RS encoder), decoder (RS decoder). Клиент не знает про шарды — общается только с энкодером/декодером (proxy pattern).ADR на узле encoder фиксирует выбор между 3x / EC 6+3 / EC 12+4 по tier'ам — открой Decisions, чтобы прочитать развёрнутое обоснование.
write-encode — happy path WRITE. Клиент шлёт 60MB объект энкодеру. Энкодер делит на 6 шардов по 10MB и считает 3 parity-шарда через P = G * D над GF(256), где G — Vandermonde matrix. Параллельно раскладывает по 3 шарда в каждый rack. Учит: write — это fan-out 9-way + CPU на parity, дороже репликации по computation, но дешевле по storage (90MB сырого vs 180MB при 3x). Cluster bandwidth остаётся ~1.5x от replication благодаря маленьким parity-шардам.
read-fast-path — все диски живы. Decoder параллельно читает только 6 data-шардов, склеивает 6×10MB = 60MB, возвращает. Parity не трогаем, decode не выполняется. Учит: fast path EC по latency сопоставим с replication — параллельные read'ы на 6 дисков, latency определяется самым медленным из 6 (tail latency). Никакой математики, никакого CPU. Поэтому EC жизнеспособен для warm-tier при разумных размерах объектов.
recover-single-rack — потеря Rack B (d3, d4, p2). Decoder читает 6 живых шардов (4 data + 2 parity), решает линейную систему D_lost = G_inv * (P - G_known * D_known) над GF(256) и восстанавливает d3, d4. Учит: reconstruction = network IO на k шардов + CPU на decode (десятки ms на 60MB single-thread, SIMD ускоряет в 4-8x). Клиент не замечает failure. Background repair-job перекодирует потерянные шарды на новый rack — на это уходят часы для больших объектов, и в это время система работает в degraded mode (m-1 = 2 tolerance вместо 3). Именно эту проблему решают LRC: single-failure recovery читает 3-4 шарда вместо 6.
catastrophic-loss — теряем 4 шарда (Rack B + d5). Имеем 5 живых из 9, нужно минимум k=6 для решения системы — underdetermined. Данные потеряны навсегда. Учит: EC(k, m) — не магия. Переживает ровно m failures, точка. m+1 = смерть. Митigation: гео-репликация EC pools поверх (S3 cross-region replication работает именно так), увеличение m (но это растит overhead), правильный rack-aware placement.
cost-compare — экономика на 1 PB. При $20/TB/мес: 3x = $60K/мес, EC 6+3 = $30K/мес, EC 12+4 = $26.6K/мес, EC 17+3 (Backblaze) = $23.6K/мес. Экономия $400K-440K в год на 1 PB. При 100 PB (масштаб S3) — десятки миллионов. Caveat: CPU + network + worse latency должны учитываться в TCO, иначе цифра врёт.
ADR-001: 3x replication vs EC 6+3 vs EC 12+4 по tier'ам.
Context. На петабайтах storage cost доминирует над compute. Выбор durability-стратегии задаёт capex (диски) и opex (питание/охлаждение). 3x — простая, быстрая, безотказная: read = 1 IO, write = 3 параллельных IO, single-failure recovery = копирование одной реплики. EC даёт радикальное сокращение storage (33-50% overhead), но требует CPU для encode/decode и k параллельных reads при reconstruction. RS любит большие immutable объекты (>1MB, лучше >10MB) и ненавидит маленькие частые updates — каждый byte change = read-modify-write всех соседних шардов для пересчёта parity. EC на маленьких объектах (<100KB) теряет смысл: per-object metadata overhead (locations, checksums, version) съедает выигрыш в data storage.
Decision. Гибридная архитектура по tier'ам:
Все шарды раскидываем по разным fault domains (rack/AZ), иначе rack failure = потеря всего объекта. Для small objects (<100KB) EC не применяем — собираем в большие append-blocks и шифруем единицей. Tier transitions автоматические по policy (last_access_time), как S3 lifecycle rules.
MINIO_STORAGE_CLASS_STANDARD=EC:N.Концепты на этом сайте:
Кейсы:
Внешние источники: