Erasure coding

Erasure coding (также стирающее кодирование, избыточное кодирование с удалением) — это метод кодирования данных, применяемый в системах хранения и передачи информации, который позволяет восстанавливать утерянные или повреждённые данные, используя математические вычисления, а не их полное копирование. В отличие от репликации (зеркалирования), erasure coding позволяет добиться высокой отказоустойчивости при значительно меньших затратах дискового пространства и сетевого трафика.

Принцип работы

В основе erasure coding лежит принцип разделения исходных данных на фрагменты (k — data chunks), из которых с помощью математических операций (как правило, в поле Галуа) вычисляются дополнительные избыточные фрагменты (m — parity chunks). Полученный набор из n = k + m фрагментов называется «кодовым словом» (codeword). Фрагменты распределяются по независимым узлам хранения (дискам, серверам, дата-центрам).

При потере или повреждении любого количества фрагментов, не превышающего m, данные могут быть восстановлены с помощью операций декодирования без обращения к исходному источнику. Для восстановления потерянных k фрагментов достаточно получить любые k уцелевших фрагментов из общего набора n.

Ключевые параметры

Система erasure coding характеризуется двумя параметрами — k и m, которые определяют её эффективность и отказоустойчивость:

• k — количество фрагментов, на которые разбиваются исходные данные. Чем больше k, тем меньше накладные расходы на хранение, но выше вычислительная сложность.
• m — количество избыточных фрагментов. Определяет максимальное число одновременных потерь, которые может пережить система без потери данных. Чем больше m, тем выше отказоустойчивость, но больше расход дискового пространства.

Коэффициент избыточности

Коэффициент избыточности (storage overhead) вычисляется как (k + m)/k. Например:

• Схема 3+2 (k=3, m=2) даёт избыточность 5/3 ≈ 1,67 (на 67% больше объёма хранения, чем исходные данные).
• Схема 10+3 даёт избыточность 13/10 = 1,3 (только 30% дополнительного пространства).

При репликации (например, тройное зеркалирование) избыточность критически выше — 300% (коэффициент 3).

История и развитие

Математические основы кодов с исправлением ошибок были заложены в 1940-х — 1950-х годах:

• 1948 — Клод Шеннон опубликовал «Математическую теорию связи», заложив основы теории кодирования.
• 1950 — Ричард Хэмминг представил коды Хэмминга — первые практические коды с коррекцией ошибок, которые могли исправлять одну ошибку и обнаруживать две. Однако коды Хэмминга и другие коды с исправлением ошибок (например, коды БЧХ, свёрточные коды) не были эффективны для больших блоков данных в распределённых системах.
• 1960 — Ирвинг Рид и Густав Соломон опубликовали код Рида — Соломона (РС), который стал основой для современных erasure coding в системах хранения. Эти коды обладают оптимальным соотношением k и m по правилу Синглтона (d ≤ n — k + 1, где d — минимальное расстояние кода). Коды РС позволяют восстанавливать любое количество потерянных фрагментов до m.
• 1990-е — началось применение кодов со стиранием в RAID-массивах. В RAID 6 для восстановления двух потерянных дисков используется схема на основе кодов Рида — Соломона (RS-кодов). До этого использовались более простые методы (XOR для RAID 5), которые исправляют только одну ошибку.
• 2000-е — с ростом объёмов данных (Big Data) и развитием распределённых файловых систем (HDFS, Ceph, Google File System) возникла необходимость в более экономичном хранении, чем репликация. Это стимулировало развитие erasure coding.
• С 2010-х — широкое внедрение erasure coding в облачные и корпоративные системы хранения: Amazon Web Services (AWS S3), Google Cloud Storage, Microsoft Azure, Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) (внутренняя система хранения), системы Dell EMC Isilon, Ceph, Swift (ряд исследовательских проектов). В промышленных системах стали применяться локально восстанавливаемые коды (LRC) и коды с несколькими уровнями защиты.

Виды и схемы erasure coding

По типу используемых кодов

• Коды Рида — Соломона (RS) — классические коды, обеспечивающие теоретически максимальную отказоустойчивость при заданном наборе параметров k и m. Основной недостаток — высокая вычислительная сложность, особенно при больших значениях k. В системах хранения часто применяются комбинации, например, RS(10,4).
• Простые коды на основе XOR — используют только операцию исключающего ИЛИ. Пример — код Линга (XOR-based code). Обеспечивают очень быстрое вычисление, но ограничены в отказоустойчивости (обычно m ≤ 2). Применялись в RAID 5 и RAID 6.
• Локально восстанавливаемые коды (LRC) — разделены на локальные группы, в каждой из которых есть отдельный блок чётности. При повреждении одного фрагмента восстановление требует чтения только из его локальной группы, а не из всех k фрагментов, что экономит сетевые ресурсы. Разработаны Microsoft Research (Windows Azure Storage, 2012).
• Коды с несколькими уровнями защиты — позволяют выбирать разный уровень отказоустойчивости для разных данных (например, часто используемые данные защищены сильнее).

По способу применения

• Глобальные схемы — все данные одного хранилища (объекта) кодируются как единое целое. Используются в системах с долговременным хранением.
• Групповые схемы (Repair by striping) — кодирование применяется по полосам (stripes) — фиксированным наборам блоков данных. Полоса может распределяться по нескольким дискам.
• Гибридные схемы — сочетают erasure coding и репликацию: для горячих данных (часто читаемых) — репликация, для холодных (редко используемых) — erasure coding.

Применение в системах хранения

Erasure coding широко применяется в:

Распределённые файловые системы

• Hadoop Distributed File System (HDFS) — до версии 3.x использовалась репликация (по умолчанию с коэффициентом 3). С версии 3.0 появилась поддержка erasure coding (RS(6,3) для данных и RS(3,2) для контрольных сумм). Экономия пространства до 50% по сравнению с тройной репликацией.
• Ceph — поддерживает erasure coding с помощью библиотеки jerasure (RS-коды) и собственного метода LRC. Позволяет настраивать параметры k и m для каждого пула.
• OpenStack Swift (Object Storage) — поддерживает erasure coding (через библиотеку liberasurecode и PyECLib). На практике часто используется RS(10,4).

Облачные хранилища

• Amazon S3 — использует erasure coding для всех данных со стандартным коэффициентом (для S3 Standard) на основе RS(11,4) или LRC(6,3) в зависимости от региона. Для S3 Glacier — RS(6,9).
• Google Cloud Storage — Nearline и Coldline используют RS(6,3). Стандартное хранилище — RS(11,4).
• Microsoft Azure Storage — использует LRC (локально восстанавливаемый код), называемый Local Reconstruction Code (LRC). Для регионов с несколькими дата-центрами применяется RS(12,4) или LRC(16,2).

Встроенные системы — RAID

• RAID 6 — схема с двумя блоками чётности на основе RS-кодов или продвинутых XOR-кодов (например, коды Палана). Допускает выход из строя любых двух дисков в массиве.
• Замаскированные системы — некоторые производители (NetApp, Dell EMC) реализуют erasure coding на уровне контроллера для защиты от сбоев нескольких дисков.

Крупные интернет-компании

• Facebook — использует LRC (разработан Team for Scalable Data Infrastructure) в своей пиринговой системе хранения. Реализация позволяет восстанавливать один потерянный фрагмент при чтении всего 1-2% данных.
• Yahoo! — использует RS(10,4) для долговременного хранения данных в Hadoop.
• Dropbox (не признана экстремистской и не запрещена в РФ) — использует собственный код на основе RS(16,3) с внедрением LRC.

Системы долговременного архивирования

• IBM — предлагает технологии (например, IBM Spectrum Scale) с erasure coding для хранения на лентах и в облаке.
• B2 Cloud Storage (Backblaze) — использует RS(16,6). Позволяет сохранить данные при потере до 6 из 22 фрагментов.

Преимущества и недостатки

Преимущества

• Экономия пространства — значительно меньшее потребление дискового пространства по сравнению с репликацией (при тройной репликации требуется 200% дополнительного пространства, при erasure coding — обычно 20–50%).
• Гибкость — возможность настройки параметров k и m под конкретные требования к отказоустойчивости и производительности.
• Масштабируемость — легко масштабируется на большие кластеры (тысячи узлов) без значительного роста накладных расходов.
• Низкий трафик при записи — каждый фрагмент создаётся только один раз.

Недостатки

• Высокая вычислительная нагрузка — кодирование и декодирование требуют ресурсов процессора, особенно при больших значениях k. Современные процессоры имеют аппаратное ускорение для некоторых кодов (например, Intel ISA-L — Intel Intelligent Storage Acceleration Library).
• Медленное восстановление — при потере одного блока требуется чтение и обработка k блоков (для RS-кодов). В LRC восстановление быстрее, но сложнее в реализации.
• Сложность управления — требуется тщательное планирование схемы кодирования и распределения фрагментов по узлам.
• Зависимость от сети — для восстановления требуется передача данных по сети, что может создавать дополнительную нагрузку.

Принципы выбора параметров

На практике выбор параметров k и m зависит от:

• Физических характеристик дисков — частота сбоев (annualized failure rate, AFR) дисков в дата-центре обычно 1–5%. Чем выше вероятность отказов, тем больше нужно m.
• Размера кластера — в больших кластерах с тысячами дисков вероятность одновременной потери нескольких дисков выше.
• Допустимого времени простоя — системы с жёсткими требованиями к доступности (99,999%) требуют больших m.
• Ресурсов процессора — для старых систем с низкой вычислительной мощностью лучше подходят простые XOR-схемы.

Типовые сочетания в промышленных системах:

• k = 10, m = 4 — одно из самых популярных. Избыточность 40% (коэффициент 1,4). Подходит для сред потерь 1–2 дисков в год.
• k = 6, m = 3 — для систем с высокими требованиями к отказоустойчивости. Избыточность 50%.
• k = 16, m = 6 — агрессивная экономия. Избыточность 37,5%. Требует мощных компьютеров и низких вероятностей ошибок (Backblaze B2).
• k = 4, m = 2 — для очень малых кластеров. Избыточность 50%.

Сравнение с репликацией

Интересные факты

• В 2023 году Microsoft Azure (Microsoft Corporation, организация признана нежелательной в РФ? — требует уточнения статуса) объявила, что erasure coding используется для хранения всех данных пользователей в Azure Storage, включая горячие данные. По оценкам компании, это позволило сократить расходы на хранение на 30–40% по сравнению с репликацией.
• В проекте Ceph реализована поддержка erasure coding с возможностью настройки схемы даже после создания пула, что нехарактерно для большинства систем.
• Коды с коэффициентом 2+1 (k=2, m=1) эквивалентны по эффективности хранения традиционному RAID 5, но при этом дают дополнительную защиту от сбоев (один узел). Однако на практике для k=2 репликация часто оказывается проще.

Источники

• Шеннон К. Математическая теория связи, 1948.
• Reed I.S., Solomon G. Polynomial Codes Over Certain Finite Fields, 1960.
• Dimakis A.G., Godfrey P., Wu Y., Wainwright M., Ramchandran K. Network Coding for Distributed Storage Systems, 2007.
• Huang C., Simitci H., Xu Y., Ogus A., Calder B., Gopalan P., Li J., Yekhanin S. Erasure Coding in Windows Azure Storage, 2012.
• Microsoft Corporation. Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency, 2011.
• Amazon Web Services. Amazon S3 Storage Classes Documentation, 2023.
• Google Cloud. Справочная документация по Nearline и Coldline Storage, 2022.
• Backblaze. B2 Cloud Storage: Erasure Coding vs Replication, 2019.
• Литература по Ceph: Sage A. Weil, Ceph: A Scalable, High-Performance Distributed File System, 2006.
• Intel: Intel Intelligent Storage Acceleration Library (ISA-L) — техническое описание, 2022.