Как стать автором
Обновить

Коды избыточности: простыми словами о том, как надёжно и дёшево хранить данные

Время на прочтение 11 мин
Количество просмотров 31K
Всего голосов 62: ↑58 и ↓4 +54
Комментарии 32

Комментарии 32

Забавно, очень много Азуры с закрытыми сырцами и ни слова про ceph, у которого всё это есть (включая локальные коды избыточности) и есть сырцы, которые можно почитать.

Правильно ли я понимаю, что в данном случае не только можно восстановить данные на сломавшемся носителе, но и задетектить случай, когда носитель как бы нормальный, работает, но данные испортил? Ну или если кто-то ещё подгадил: ошибка передачи по сети, глючное железо и т.д.

Теоретически с помощью кодов избыточности можно обнаружить ошибки, если сравнить исходный блок данных с блоком данных, полученным с помощью восстановления. Но для этого нужно определить, какой блок сравнивать.

На практике в системах хранения данных коды избыточности используют только для восстановления, а для обнаружения ошибок используют контрольные суммы. Например, вместе с каждым блоком может храниться его контрольная сумма (md5, sha256 и т.п.). Перед чтением данных контрольная сумма считается повторно. Если она не совпадает с сохраненной, значит данные повреждены.

Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
Теоретически с помощью кодов избыточности можно обнаружить ошибки, если сравнить исходный блок данных с блоком данных, полученным с помощью восстановления. Но для этого нужно определить, какой блок сравнивать.
Ну вот неправильно.
Ниже я уже написал, в русском языке правильный термин «избыточное кодирование». Степень избыточности позволяет контролировать целостность данных и/или восстанавливать ошибки. Бит четности — тоже избыточное кодирование, позволяющее обнаружить наличие нечетного кол-ва битовых ошибок. Код Хемминга позволяет исправить одну и обнаружить две ошибки. А дальше, блочные, цикличиские…
Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.

Опять же неправильно. Помехоустойчивое кодирование — это совокупность методов, которые позволяют избежать и корректировать ошибки для определенного типа канала передачи. И внезапно, там везде применяется избыточное кодирование. Вы сами даете ссылку на корректирующий код, который по сути и является избыточностью при избыточном кодирование, и там есть ссылка на циклические коды, частным случаем которых является код Рида-Соломона.

Извините, но может математика у вас в статье и правильная, но теория у вас какая-то спутанная.
Например, для слов размером 16 бит это поле, содержащее 65 536 элементов, для каждой пары которых можно найти результат любой операции (+, -, *, /). Значения x, p, альфа, бета, гамма, дельта из уравнений выше для расчётов будут считаться элементами поля Галуа.

  1. Не для каждой пары и любой операции можно найти результат.
  2. Нельзя просто взять значение и сказать, что оно принадлежит полю.
Под термином «коды избыточности» я подразумеваю термин «erasure codes», причем как инженерный термин, а не строгое теоретическое понятие, имеющее четкое определение. Добавил это в начало статьи, чтобы не было терминологической путаницы.

Название «коды избыточности» прижилось у нас исторически.
Название «erasure codes», конечно, используется чаще. Но и «код(ы) избыточности» иногда употребляют.
НЛО прилетело и опубликовало эту надпись здесь
Странно, что 4 года назад к этому термину ни у кого вопросов не было :)
НЛО прилетело и опубликовало эту надпись здесь
В моей дипломной работе, я использовал термины «коды с коррекцией ошибок» и «самовосстанавливающиеся коды»
Может все-таки «избыточное кодирование»?
  • Как сказано выше, размер слова — фиксированный, в нашем примере 16 бит. Формулы выше для кодов Рида — Соломона таковы, что при использовании обычных целых чисел результат вычисления p может быть не представим с помощью слова допустимого размера.
  • При восстановлении данных формулы выше будут рассматриваться как система уравнений, которую нужно решить, чтобы восстановить данные. В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера.

Простите, если вы не знаете, обратитесь к тому, кто знает.
Зачем писать отсебятину?
Как вы же сами и сказали, все 4 операции это не «классические» операции сложения/вычитания/умножения/деления, а операции над полем Галуа (которые, тем не менее, обладают почти всеми привычными нам с детства свойствами). Соответственно, слова «В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера» никакого отношения к реальности в контексте кодов Рида-Соломона иметь не могут (как и слова про представимость с помощью слова допустимого размера)
Эти два пункта объясняют, какие проблемы возникнут, если попробовать использовать целые числа. Из-за них нельзя использовать целые числа для кодов Рида — Соломона, а нужно использовать элементы поля Галуа. Об этом я пишу в тексте сразу за названными проблемами:

Эти проблемы не позволяют использовать для кодов Рида — Соломона целые числа


А приведите, может быть, пример тогда таких полей Галуа? Не обязательно для 65536 элементов, а вот, скажем, для 8. А то «ядра — чистый изумруд» получается.

Этому примеру посвящена короткая статья на Хабре. В ней как раз рассматривается поле из 8 элементов GF(2^3).
В качестве введения в тему также можно использовать другую статью.

Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.

Для использования на практике не обязательно глубоко погружаться в теорию полей Галуа, можно просто считать, что есть некоторые таблицы сложения, вычитания, умножения и деления, и все вычисления происходят с использованием этих таблиц.

Например, можно использовать популярную библиотеку Jerasure для построения кодов избыточности (кодирования) и восстановления данных (декодирования). Решение систем уравнений (которые представляются в виде матричных уравнений), арифметика полей Галуа — это будет выполняться на уровне библиотеки.
Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.

Мда? Поля Галуа — это просто другое название для конечных полей. Берёте любое простое число (например, 3) и рассматривайте остатки по его модулю — т.е. числа 0, 1, 2. Операции сложения и умножения в этом поле — обычные операции над числами, только берутся по модулю 3.
Если брать не простой модуль то ситуация несколько сложнее.
Выше нужно было написать «нетривиальный пример» для полей GF(2^k), которые в основном используются.

Поле Галуа устроено довольно просто:


  1. Берется кольцо вычетов по простому модулю p. В Данном случае по модулю 2.
  2. Берется неприводимый многочлен степени k над данным полем. Например x^3+x+1.
  3. Берется кольцо вычетов по модулю данного многочлена.

Таким образов получается поле Галуа из 8 элементов.
Элементы поля — многочлены с коэффициентами из Z_2 степени не выше k.
Сложение и умножение многочленов выполняется по модулю x^3+x+1, а сложение и умножение их коэффициентов — по модулю 2.

НЛО прилетело и опубликовало эту надпись здесь
Да, этот момент я упустил — гнев застлил глаза и чтение статьи остановилось.
Прошу прощения!
Однако, выше другими собеседниками приводится более конструктивная критика этого фрагмента текста
Время обработки запросов. Чем больше сумма n + m, тем дольше будет время ответа на запросы. Так как для чтения данных (во время восстановления) нужно прочитать n блоков, хранящихся на n разных дисках, то время чтения будет определяться самым медленным диском.

Но ведь чем больше n, тем меньше блоков с каждого диска нужно прочитать. А значит среднее время чтения будет меньше.
Время чтения зависит от способа записи данных и режима работы (нормальный, когда все блоки данных доступны, или восстановление, когда часть блоков данных недоступна).

1. Если каждый ключ с данными разбивать на части и записывать сразу на все диски, то для чтения ключа нужно будет читать сразу с n дисков. В нормальном режиме чтение будет с n дисков с блоками данных, в режиме восстановления — с n дисков, часть из которых — диски с блоками данных, а часть — диски с блоками кодов избыточности. Читать с разных дисков можно параллельно, поэтому время чтения всего ключа будет определяться временем чтения с самого медленного диска. Чем больше будет n, тем сильнее будет увеличиваться общее время чтения ключа с данными (в среднем).

2. Можно записывать ключи с данными по-другому: брать некоторое количество ключей, формировать из них последовательность, и уже эту последовательность разбивать на части, дополнять кодами избыточности и записывать на разные диски. В этом случае многие ключи будут целиком располагаться на 1 диске, и чтения будут в среднем выполняться быстрее. Однако, если диск, где хранятся данные, будет недоступен, то для восстановления данных придется делать восстановление, а для этого читать из n дисков (n/l в случае LRC). То есть время чтения будет больше, если нужно восстанавливать данные.

Обе схемы успешно используются на практике, а выбор схемы зависит сразу от ряда факторов. В первой схеме, например, ключи можно записывать независимо, а во второй нужно будет накапливать достаточное количество ключей, и записывать их пачками. С другой стороны, в первой схеме нужно хранить больше служебной информации на дисках, что может сильно увеличивать стоимость хранения маленьких ключей.
НЛО прилетело и опубликовало эту надпись здесь

В начале приводится скриншот с Википедии с этими формулами-кракозябрами. Ну, думаю, наконец объяснят на контрасте всё простым языком. И далее по тексту снова всякие формулы и скобки… -_-

Совсем без формул, к сожалению, не получится разобраться в теме.
НЛО прилетело и опубликовало эту надпись здесь
Да вроде нормальная статья, но её можно слегка сократить:
0. Коды избыточности занимают меньше места, чем цельная копия.
1. При помощи систем уравнений можно строить подходящее кол-во блоков избыточности.
2. Разбив данные на несколько пачек — можно считать для них коды избыточности отдельно.
3. Готовые библиотеки за вас всё посчитают, детали вам в принципе не нужны.
Детальные формулы есть на википедии.
Возможно еще одна хорошая ссылка для желающих с любой степенью глубины познакомится с кодами:
«Коды, исправляющие ошибки» Питерсон У., Уэлдон Э. издательство Мир.
Коды Хэмминга и Рида-Соломона, частные случаи БЧХ кода. Собственно большинство кодов Рида-Соломона с фиксированными размерами были получены подставляя те или иные коффициенты в БЧХ код.
Но чистый мат аппарат БЧХ кодов, это отдельная книга в целом.
Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.
Автор отвечает только на критику в той теме, где он что-то понимает. Ему не интересно, что «код избыточности» даже не гуглится. Он уверен в своей математике. И мы ему ничего не докажем. Он просто пришел в этот проект(в яндексе). Зачем тратиться.
Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.
Стоит упомянуть, что это все относительно размера слова, на 8 битах все легко, но вот когда размер слова измеряется килобайтами становится весело.
Просто, ТС не упомянул, что в любых системах хранениях данных HDD/SDD и так применяется избыточное кодирование на аппаратном уровне и им (в яндексе) нужно примемять что-то сверху, и собственно им нужно немного по-другому подходить к вопросу потому, что у них выпадают целые «железные» блоки (известного размера), и я думаю, что там можно упростить математику. Но, что я могу помнить из лекций, как связист…
Выше ответил на Вашу критику. Насколько я понимаю, она касается терминологии.

Хорошая книга по теории помехоустойчивого кодирования с примерами:
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгортмы, применение.
Моя настольная книга по ECC.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий