Введение
Код добавлен для восстановления потерянных данных. В теории кодирования код стирания — это код прямой коррекции ошибок (FEC), работающий при условии стирания битов (а не возникновения ошибок), который преобразует сообщение из k символов в более длинное сообщение (кодовое слово) из n символов, позволяя восстановить исходное сообщение из подмножества этих n символов. Отношение r = k/n называется коэффициентом кодирования. Отношение k'/k, где k' обозначает количество символов, необходимых для восстановления, называется эффективностью восстановления. Алгоритм восстановления предполагает, что известно, какие из n символов были потеряны, — в отличие от кодов прямой коррекции ошибок.
In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be recovered from a subset of the n symbols. The fraction r = k/n is called the code rate. The fraction k’/k, where k’ denotes the number of symbols required for recovery, is called reception efficiency. The recovery algorithm expects that it is known which of the n symbols are lost — unlike forward error correction codes.
Оптимальные коды стирания
Оптимальные коды стирания обладают свойством, что любые k из n символов кодовых слов достаточно для восстановления исходного сообщения (то есть, они обладают оптимальной эффективностью восстановления). Оптимальные коды стирания являются кодами с максимальным разделением расстояний (MDS-кодами).
Общее положение
Линейная конструкция выше может быть обобщена на полиномиальную интерполяцию. Кроме того, точки теперь вычисляются над конечным полем. Сначала мы выбираем конечное поле F с порядком не менее n, но обычно степенью 2. Отправитель нумерует символы данных от 0 до k − 1 и отправляет их. Затем он строит (многочлен Лагранжа) p(x) порядка k, такой что p(i) равен символу данных i. Затем он отправляет p(k), p(k+1), ..., p(n − 1). Приемник теперь также может использовать полиномиальную интерполяцию для восстановления потерянных пакетов, при условии, что он успешно получил k символов. Если порядок F меньше 2b, где b – количество бит в символе, то можно использовать несколько многочленов. Отправитель может создавать символы k до n − 1 «на лету», то есть равномерно распределять нагрузку между передачей символов. Если получатель хочет выполнять свои вычисления «на лету», он может построить новый многочлен q, такой что q(i) = p(i), если символ i < k был успешно получен, и q(i) = 0, когда символ i < k не был получен. Теперь определим r(i) = p(i) − q(i). Во-первых, мы знаем, что r(i) = 0, если символ i < k был успешно получен. Во-вторых, если символ i ≥ k был успешно получен, то r(i) = p(i) − q(i) может быть вычислен. Таким образом, у нас достаточно точек для построения r и вычисления его значений для нахождения потерянных пакетов. Следовательно, и отправителю, и приемнику требуется O(n(n − k)) операций и только O(n − k) памяти для работы «на лету».
Реальная реализация
Этот процесс реализуется кодами Рида — Соломона, с кодовыми словами, построенными на конечном поле с использованием матрицы Вандермонда. Большинство практических кодов стирания являются систематическими: каждый из исходных k символов можно найти скопированным, не закодированным, в качестве одного из n символов сообщения. В частности, различные реализации кодирования стирания Рида — Соломона используются в Apache Hadoop, RAID 6, встроенном в Linux, Microsoft Azure, Facebook cold storage и Backblaze Vaults. Классическим способом восстановления после сбоев в системах хранения была репликация. Однако репликация требует значительных накладных расходов в виде потраченных впустую байтов. Поэтому все более крупные системы хранения, такие как те, что используются в центрах обработки данных, используют хранение с кодированием стирания. Наиболее распространенной формой кодирования стирания, используемой в системах хранения, является код Рида — Соломона (RS) — продвинутая математическая формула, используемая для восстановления отсутствующих данных из известных данных, называемых блоками четности. В (k, m) RS-коде заданный набор k блоков данных, называемых "чанками", кодируется в (k + m) чанков. Весь набор чанков составляет полосу. Кодирование выполняется таким образом, что, пока доступно хотя бы k из (k + m) чанков, можно восстановить все данные. Это означает, что хранилище с (k, m) RS-кодированием может выдержать до m сбоев. Пример: в коде RS (10, 4), который используется в Facebook для их HDFS, 10 МБ пользовательских данных разделяются на десять блоков по 1 МБ. Затем создаются четыре дополнительных блока четности по 1 МБ для обеспечения избыточности. Это позволяет выдержать до 4 одновременных сбоев. Расходы на хранение здесь составляют 14/10 = 1.4X. В случае полностью реплицированной системы 10 МБ пользовательских данных должны быть реплицированы 4 раза, чтобы выдержать до 4 одновременных сбоев. В этом случае накладные расходы на хранение составят 50/10 = 5 раз. Это дает представление о меньших накладных расходах на хранение с кодированием стирания по сравнению с полной репликацией и, следовательно, о привлекательности современных систем хранения. Изначально коды стирания использовались для снижения стоимости эффективного хранения "холодных" (редко используемых) данных, но коды стирания также могут использоваться для повышения производительности обслуживания "горячих" (часто используемых) данных.