Код стирания

Добавлен код, позволяющий восстановить потерянные данные.

В теории кодирования код стирания — это код с прямым исправлением ошибок (FEC) при допущении стирания битов (а не битовых ошибок), который преобразует сообщение из k символов в более длинное сообщение (кодовое слово) с n символами так, что исходное сообщение может быть восстановлено из подмножества n символов. Дробь r  =  k / n называется скоростью кода . Дробь k'/k , где k' обозначает количество символов, необходимое для восстановления, называется эффективностью приема.

Оптимальные коды стирания

Оптимальные стирающие коды обладают тем свойством, что любых k из n символов кодового слова достаточно для восстановления исходного сообщения (т. е. они имеют оптимальную эффективность приема). Оптимальными стирающими кодами являются коды, разделяемые на максимальное расстояние (MDS-коды).

Проверка четности

Проверка четности — это особый случай, когда n  =  k  + 1. Из набора k значений вычисляется контрольная сумма, которая добавляется к k исходным значениям: ${\displaystyle \{v_{i}\}_{1\leq i\leq k}}$

${\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}$

Набор из k  + 1 значений теперь согласован в отношении контрольной суммы. Если одно из этих значений стерто, его можно легко восстановить, суммируя оставшиеся переменные: ${\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}$ ${\displaystyle v_{e}}$

${\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}$

Полиномиальная передискретизация

Пример: сообщение об ошибке ( k  = 2)

В простом случае, когда k  = 2, избыточные символы могут быть созданы путем выборки различных точек вдоль линии между двумя исходными символами. Это показано на простом примере под названием err-mail:

Алиса хочет отправить свой номер телефона (555629) Бобу по электронной почте. Err-mail работает так же, как и электронная почта, за исключением

1. Около половины всей почты теряется. ^[1]
2. Сообщения длиной более 5 символов являются незаконными.
3. Это очень дорого (аналогично авиапочте).

Вместо того, чтобы просить Боба подтвердить отправленные ею сообщения, Алиса придумывает следующую схему.

1. Она разбивает свой номер телефона на две части a = 555, b = 629 и отправляет Бобу два сообщения – «A=555» и «B=629».
2. Она строит линейную функцию , в данном случае такую, что и . ${\displaystyle f(i)=a+(b-a)(i-1)}$ ${\displaystyle f(i)=555+74(i-1)}$ ${\displaystyle f(1)=555}$ ${\displaystyle f(2)=629}$

1. Она вычисляет значения f (3), f (4) и f (5), а затем передает три избыточных сообщения: «C=703», «D=777» и «E=851».

Боб знает, что форма f ( k ) равна , где a и b — две части телефонного номера. Теперь предположим, что Боб получает «D=777» и «E=851». ${\displaystyle f(i)=a+(b-a)(i-1)}$

Боб может восстановить номер телефона Алисы, вычислив значения a и b на основе полученных им значений ( f (4) и f (5)). Боб может выполнить эту процедуру, используя любые два сообщения об ошибке, поэтому вероятность стирания кода в этом примере составляет 40%.

Обратите внимание, что Алиса не может закодировать свой номер телефона только в одном сообщении об ошибке, поскольку оно содержит шесть символов, а максимальная длина одного сообщения об ошибке составляет пять символов. Если бы она отправила свой номер телефона по частям, прося Боба подтвердить получение каждого фрагмента, в любом случае пришлось бы отправить как минимум четыре сообщения (два от Алисы и два подтверждения от Боба). Таким образом, код стирания в этом примере, требующий пять сообщений, весьма экономичен.

Этот пример немного надуман. Для действительно общих кодов стирания, которые работают с любым набором данных, нам понадобится что-то иное, чем заданное f ( i ).

Общий случай

Линейную конструкцию, приведенную выше, можно обобщить до полиномиальной интерполяции . Кроме того, точки теперь вычисляются по конечному полю .

Сначала мы выбираем конечное поле F порядка не менее n , но обычно степени 2. Отправитель нумерует символы данных от 0 до k  − 1 и отправляет их. Затем он строит полином (Лагранжа) p ( x ) порядка k такой, что p ( i ) равен символу данных i . Затем он отправляет p ( k ), ..., p ( n  − 1). Получатель теперь также может использовать полиномиальную интерполяцию для восстановления потерянных пакетов при условии, что он успешно получит k символов. Если порядок F меньше 2 ^b , где b — количество битов в символе, то можно использовать несколько полиномов.

Отправитель может создавать символы от k до n  - 1 «на лету», т. е. равномерно распределять рабочую нагрузку между передачей символов. Если получатель хочет выполнить свои вычисления «на лету», он может построить новый полином q , такой, что q ( i ) = p ( i ), если символ i < k был получен успешно, и q ( i ) = 0, когда символ i  <  k не было получено. Теперь пусть р ( я ) = п ( я ) -  q ( я ). Во-первых, мы знаем, что r ( i ) = 0, если символ i < k был получен успешно. Во-вторых, если символ i  ≥  k был получен успешно, то можно вычислить r ( i ) =  p ( i ) −  q ( i ). Итак, у нас есть достаточно точек данных, чтобы построить r и оценить его, чтобы найти потерянные пакеты. Таким образом, и отправителю, и получателю требуется O ( n ( n  −  k )) операций и только O ( n  −  k ) пространства для работы «на лету».

Реализация в реальном мире

Этот процесс реализуется кодами Рида-Соломона с кодовыми словами, построенными над конечным полем с использованием матрицы Вандермонда .

Наиболее практичными кодами стирания являются систематические коды : каждый из исходных k символов можно найти скопированным в незакодированном виде как один из n символов сообщения. ^[2] (Коды стирания, поддерживающие обмен секретами, никогда не используют систематический код).

Почти оптимальные коды стирания

Почти оптимальные коды стирания требуют (1 + ε) k символов для восстановления сообщения (где ε>0). Уменьшение ε можно сделать за счет процессорного времени.Почти оптимальные стирающие коды обменивают возможности коррекции на вычислительную сложность: практические алгоритмы могут кодировать и декодировать с линейной временной сложностью.

Фонтанные коды (также известные как коды стирания без скорости ) являются яркими примерами почти оптимальных кодов стирания . Они могут преобразовать сообщение k- символов в практически бесконечную закодированную форму, т. е. они могут генерировать произвольное количество избыточных символов, которые все можно использовать для исправления ошибок. Получатели могут начать декодирование после того, как они получили чуть больше k закодированных символов.

Регенерация кодов решает проблему восстановления (также называемого восстановлением) потерянных закодированных фрагментов из существующих закодированных фрагментов. Эта проблема возникает в распределенных системах хранения, где связь для поддержания избыточности кодирования является проблемой. ^[2]

Применение стирающего кодирования в системах хранения данных

Стирающее кодирование теперь является стандартной практикой для надежного хранения данных. ^{[3] [4] [5]} В частности, различные реализации стирающего кодирования Рида-Соломона используются Apache Hadoop , RAID-6, встроенным в Linux, Microsoft Azure, холодным хранилищем Facebook и Backblaze Vaults. ^{[5] [2]}

Классическим способом восстановления после сбоев в системах хранения было использование репликации. Однако репликация сопряжена со значительными накладными расходами в виде потраченных впустую байтов. Поэтому все более крупные системы хранения, например те, которые используются в центрах обработки данных, используют хранилище со стирающим кодом. Наиболее распространенной формой стирающего кодирования, используемой в системах хранения, является код Рида-Соломона (RS) , усовершенствованная математическая формула, используемая для восстановления недостающих данных из частей известных данных, называемых блоками четности. В коде RS ( k ,  m ) заданный набор из k блоков данных, называемых «фрагментами», кодируется в ( k  +  m ) фрагментов. Общий набор чанков представляет собой полосу . Кодирование выполняется таким образом, что, пока доступно хотя бы k из ( k  +  m ) фрагментов, можно восстановить все данные. Это означает, что хранилище ( k ,  m ) с RS-кодированием может выдержать до m сбоев.

Пример: В коде RS (10, 4), который используется в Facebook для их HDFS , ^[6] 10 МБ пользовательских данных делятся на десять блоков по 1 МБ. Затем создаются четыре дополнительных блока четности по 1 МБ для обеспечения избыточности. Это может допустить до 4 одновременных сбоев. Накладные расходы на хранение здесь составляют 14/10 = 1,4X.

В случае полностью реплицированной системы 10 МБ пользовательских данных придется реплицировать 4 раза, чтобы выдержать до 4 одновременных сбоев. Накладные расходы на хранение в этом случае составят 50/10 = 5 раз.

Это дает представление о меньших затратах на хранилище со стирающим кодом по сравнению с полной репликацией и, следовательно, о привлекательности современных систем хранения.

Первоначально коды стирания использовались для эффективного снижения стоимости хранения «холодных» (редко доступных) данных; но коды стирания также можно использовать для повышения производительности при обработке «горячих» (более часто используемых) данных. ^[2]

Примеры

Вот несколько примеров реализации различных кодов:

Почти оптимальные коды стирания

• Коды Торнадо
• Коды проверки четности низкой плотности

Почти оптимальные коды фонтанного (бесскоростного стирания)

• Код фонтана
• Онлайн коды
• LT-коды
• Коды Раптора
• Сетевые коды
• Треугольные коды

Оптимальные коды стирания

• Четность : используется в системах хранения RAID .
• архив
• Tahoe-LAFS включает zfec
• Коды Рида – Соломона
• Erasure Resilient Systematic Code, код MDS, превосходящий Рида-Соломона по максимальному количеству избыточных пакетов, ^{[ по мнению кого? ]} см. RS(4,2) с 2 битами или RS(9,2) с 3 битами
• Регенерирующие коды ^{[7] [8]}
• любой другой код, разделяемый на максимальное расстояние

Смотрите также

• Коды прямого исправления ошибок .
• Совместное использование секрета (отличается тем, что исходный секрет шифруется и скрывается до тех пор, пока не будет достигнут кворум декодирования)
• Орфографический алфавит

Рекомендации

1. Некоторые версии этой истории относятся к демону err-mail.
2. Рашми Винаяк. «Стирающее кодирование для систем больших данных: теория и практика». 2016. с. 2: раздел «Реферат». п. 9: раздел «Систематические коды». п. 12: раздел «Регенерация кодов».
3. «Стирающее кодирование — практика и принципы». 2016.
4. Мэтт Саррел. «Стирающее кодирование 101». 2022.
5. Брайан Бич. «Исходный код стирающего кодирования Рида-Соломона с открытым исходным кодом Backblaze» . 2015.
6. Ся, Минъюань; Саксена, Мохит; Блаум, Марио; Пиз, Дэвид А. (2015). История о двух стирающих кодах в {HDFS}. стр. 213–226. ISBN 978-1-931971-20-1.
7. Димакис, Александрос Г.; Годфри, П. Брайтен; Ву, Юньнань; Уэйнрайт, Мартин Дж.; Рамчандран, Каннан (сентябрь 2010 г.). «Сетевое кодирование для распределенных систем хранения». Транзакции IEEE по теории информации . 56 (9): 4539–4551. arXiv : cs/0702015 . CiteSeerX 10.1.1.117.6892 . дои : 10.1109/TIT.2010.2054295. S2CID  260559901. 
8. "домашняя страница [Erasure Coding для распределенного хранилища Wiki]" . 2017-07-31. Архивировано из оригинала 31 июля 2017 г. Проверено 20 августа 2023 г.

Внешние ссылки

• Jerasure — это библиотека бесплатного программного обеспечения, реализующая методы стирания кода Рида-Соломона и Коши с оптимизацией SIMD.
• Программное обеспечение FEC в компьютерных коммуникациях Луиджи Риццо описывает оптимальные коды коррекции стирания.
• Feclib — это почти оптимальное расширение работы Луиджи Риццо, в котором используются ленточные матрицы. Можно установить множество параметров, таких как размер ширины полосы и размер конечного поля. Он также успешно использует большой размер регистров современных процессоров. Неизвестно, как он соотносится с почти оптимальными кодами, упомянутыми выше.
• Вики-сайт «Кодирование для распределенного хранилища» для регенерации кодов и восстановления кодов стирания.
• ECIP «Интернет-протокол стирания кода», разработанный в 1996 году, стал первым использованием FEC «прямого исправления ошибок» в Интернете. Впервые он был использован в коммерческих целях для потоковой передачи живого видео сэра Артура Кларка в Шри-Ланке на UIUC в Индиане.