Комментарии 32
Забавно, очень много Азуры с закрытыми сырцами и ни слова про ceph, у которого всё это есть (включая локальные коды избыточности) и есть сырцы, которые можно почитать.
Правильно ли я понимаю, что в данном случае не только можно восстановить данные на сломавшемся носителе, но и задетектить случай, когда носитель как бы нормальный, работает, но данные испортил? Ну или если кто-то ещё подгадил: ошибка передачи по сети, глючное железо и т.д.
Теоретически с помощью кодов избыточности можно обнаружить ошибки, если сравнить исходный блок данных с блоком данных, полученным с помощью восстановления. Но для этого нужно определить, какой блок сравнивать.
На практике в системах хранения данных коды избыточности используют только для восстановления, а для обнаружения ошибок используют контрольные суммы. Например, вместе с каждым блоком может храниться его контрольная сумма (md5, sha256 и т.п.). Перед чтением данных контрольная сумма считается повторно. Если она не совпадает с сохраненной, значит данные повреждены.
Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
На практике в системах хранения данных коды избыточности используют только для восстановления, а для обнаружения ошибок используют контрольные суммы. Например, вместе с каждым блоком может храниться его контрольная сумма (md5, sha256 и т.п.). Перед чтением данных контрольная сумма считается повторно. Если она не совпадает с сохраненной, значит данные повреждены.
Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
Теоретически с помощью кодов избыточности можно обнаружить ошибки, если сравнить исходный блок данных с блоком данных, полученным с помощью восстановления. Но для этого нужно определить, какой блок сравнивать.Ну вот неправильно.
Ниже я уже написал, в русском языке правильный термин «избыточное кодирование». Степень избыточности позволяет контролировать целостность данных и/или восстанавливать ошибки. Бит четности — тоже избыточное кодирование, позволяющее обнаружить наличие нечетного кол-ва битовых ошибок. Код Хемминга позволяет исправить одну и обнаружить две ошибки. А дальше, блочные, цикличиские…
Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
Опять же неправильно. Помехоустойчивое кодирование — это совокупность методов, которые позволяют избежать и корректировать ошибки для определенного типа канала передачи. И внезапно, там везде применяется избыточное кодирование. Вы сами даете ссылку на корректирующий код, который по сути и является избыточностью при избыточном кодирование, и там есть ссылка на циклические коды, частным случаем которых является код Рида-Соломона.
Извините, но может математика у вас в статье и правильная, но теория у вас какая-то спутанная.
Например, для слов размером 16 бит это поле, содержащее 65 536 элементов, для каждой пары которых можно найти результат любой операции (+, -, *, /). Значения x, p, альфа, бета, гамма, дельта из уравнений выше для расчётов будут считаться элементами поля Галуа.
- Не для каждой пары и любой операции можно найти результат.
- Нельзя просто взять значение и сказать, что оно принадлежит полю.
Под термином «коды избыточности» я подразумеваю термин «erasure codes», причем как инженерный термин, а не строгое теоретическое понятие, имеющее четкое определение. Добавил это в начало статьи, чтобы не было терминологической путаницы.
Название «коды избыточности» прижилось у нас исторически.
Название «erasure codes», конечно, используется чаще. Но и «код(ы) избыточности» иногда употребляют.
Название «коды избыточности» прижилось у нас исторически.
Название «erasure codes», конечно, используется чаще. Но и «код(ы) избыточности» иногда употребляют.
Странно, что 4 года назад к этому термину ни у кого вопросов не было :)
В моей дипломной работе, я использовал термины «коды с коррекцией ошибок» и «самовосстанавливающиеся коды»
Может все-таки «избыточное кодирование»?
- Как сказано выше, размер слова — фиксированный, в нашем примере 16 бит. Формулы выше для кодов Рида — Соломона таковы, что при использовании обычных целых чисел результат вычисления p может быть не представим с помощью слова допустимого размера.
- При восстановлении данных формулы выше будут рассматриваться как система уравнений, которую нужно решить, чтобы восстановить данные. В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера.
Простите, если вы не знаете, обратитесь к тому, кто знает.
Зачем писать отсебятину?
Как вы же сами и сказали, все 4 операции это не «классические» операции сложения/вычитания/умножения/деления, а операции над полем Галуа (которые, тем не менее, обладают почти всеми привычными нам с детства свойствами). Соответственно, слова «В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера» никакого отношения к реальности в контексте кодов Рида-Соломона иметь не могут (как и слова про представимость с помощью слова допустимого размера)
Эти два пункта объясняют, какие проблемы возникнут, если попробовать использовать целые числа. Из-за них нельзя использовать целые числа для кодов Рида — Соломона, а нужно использовать элементы поля Галуа. Об этом я пишу в тексте сразу за названными проблемами:
Эти проблемы не позволяют использовать для кодов Рида — Соломона целые числа
А приведите, может быть, пример тогда таких полей Галуа? Не обязательно для 65536 элементов, а вот, скажем, для 8. А то «ядра — чистый изумруд» получается.
Этому примеру посвящена короткая статья на Хабре. В ней как раз рассматривается поле из 8 элементов GF(2^3).
В качестве введения в тему также можно использовать другую статью.
Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.
Для использования на практике не обязательно глубоко погружаться в теорию полей Галуа, можно просто считать, что есть некоторые таблицы сложения, вычитания, умножения и деления, и все вычисления происходят с использованием этих таблиц.
Например, можно использовать популярную библиотеку Jerasure для построения кодов избыточности (кодирования) и восстановления данных (декодирования). Решение систем уравнений (которые представляются в виде матричных уравнений), арифметика полей Галуа — это будет выполняться на уровне библиотеки.
В качестве введения в тему также можно использовать другую статью.
Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.
Для использования на практике не обязательно глубоко погружаться в теорию полей Галуа, можно просто считать, что есть некоторые таблицы сложения, вычитания, умножения и деления, и все вычисления происходят с использованием этих таблиц.
Например, можно использовать популярную библиотеку Jerasure для построения кодов избыточности (кодирования) и восстановления данных (декодирования). Решение систем уравнений (которые представляются в виде матричных уравнений), арифметика полей Галуа — это будет выполняться на уровне библиотеки.
Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.
Мда? Поля Галуа — это просто другое название для конечных полей. Берёте любое простое число (например, 3) и рассматривайте остатки по его модулю — т.е. числа 0, 1, 2. Операции сложения и умножения в этом поле — обычные операции над числами, только берутся по модулю 3.
Если брать не простой модуль то ситуация несколько сложнее.
Выше нужно было написать «нетривиальный пример» для полей GF(2^k), которые в основном используются.
Поле Галуа устроено довольно просто:
- Берется кольцо вычетов по простому модулю p. В Данном случае по модулю 2.
- Берется неприводимый многочлен степени k над данным полем. Например x^3+x+1.
- Берется кольцо вычетов по модулю данного многочлена.
Таким образов получается поле Галуа из 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). То есть время чтения будет больше, если нужно восстанавливать данные.
Обе схемы успешно используются на практике, а выбор схемы зависит сразу от ряда факторов. В первой схеме, например, ключи можно записывать независимо, а во второй нужно будет накапливать достаточное количество ключей, и записывать их пачками. С другой стороны, в первой схеме нужно хранить больше служебной информации на дисках, что может сильно увеличивать стоимость хранения маленьких ключей.
1. Если каждый ключ с данными разбивать на части и записывать сразу на все диски, то для чтения ключа нужно будет читать сразу с n дисков. В нормальном режиме чтение будет с n дисков с блоками данных, в режиме восстановления — с n дисков, часть из которых — диски с блоками данных, а часть — диски с блоками кодов избыточности. Читать с разных дисков можно параллельно, поэтому время чтения всего ключа будет определяться временем чтения с самого медленного диска. Чем больше будет n, тем сильнее будет увеличиваться общее время чтения ключа с данными (в среднем).
2. Можно записывать ключи с данными по-другому: брать некоторое количество ключей, формировать из них последовательность, и уже эту последовательность разбивать на части, дополнять кодами избыточности и записывать на разные диски. В этом случае многие ключи будут целиком располагаться на 1 диске, и чтения будут в среднем выполняться быстрее. Однако, если диск, где хранятся данные, будет недоступен, то для восстановления данных придется делать восстановление, а для этого читать из n дисков (n/l в случае LRC). То есть время чтения будет больше, если нужно восстанавливать данные.
Обе схемы успешно используются на практике, а выбор схемы зависит сразу от ряда факторов. В первой схеме, например, ключи можно записывать независимо, а во второй нужно будет накапливать достаточное количество ключей, и записывать их пачками. С другой стороны, в первой схеме нужно хранить больше служебной информации на дисках, что может сильно увеличивать стоимость хранения маленьких ключей.
В начале приводится скриншот с Википедии с этими формулами-кракозябрами. Ну, думаю, наконец объяснят на контрасте всё простым языком. И далее по тексту снова всякие формулы и скобки… -_-
Да вроде нормальная статья, но её можно слегка сократить:
0. Коды избыточности занимают меньше места, чем цельная копия.
1. При помощи систем уравнений можно строить подходящее кол-во блоков избыточности.
2. Разбив данные на несколько пачек — можно считать для них коды избыточности отдельно.
3. Готовые библиотеки за вас всё посчитают, детали вам в принципе не нужны.
Детальные формулы есть на википедии.
0. Коды избыточности занимают меньше места, чем цельная копия.
1. При помощи систем уравнений можно строить подходящее кол-во блоков избыточности.
2. Разбив данные на несколько пачек — можно считать для них коды избыточности отдельно.
3. Готовые библиотеки за вас всё посчитают, детали вам в принципе не нужны.
Детальные формулы есть на википедии.
Возможно еще одна хорошая ссылка для желающих с любой степенью глубины познакомится с кодами:
«Коды, исправляющие ошибки» Питерсон У., Уэлдон Э. издательство Мир.
«Коды, исправляющие ошибки» Питерсон У., Уэлдон Э. издательство Мир.
Коды Хэмминга и Рида-Соломона, частные случаи БЧХ кода. Собственно большинство кодов Рида-Соломона с фиксированными размерами были получены подставляя те или иные коффициенты в БЧХ код.
Но чистый мат аппарат БЧХ кодов, это отдельная книга в целом.
Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.
Но чистый мат аппарат БЧХ кодов, это отдельная книга в целом.
Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.
Автор отвечает только на критику в той теме, где он что-то понимает. Ему не интересно, что «код избыточности» даже не гуглится. Он уверен в своей математике. И мы ему ничего не докажем. Он просто пришел в этот проект(в яндексе). Зачем тратиться.
Просто, ТС не упомянул, что в любых системах хранениях данных HDD/SDD и так применяется избыточное кодирование на аппаратном уровне и им (в яндексе) нужно примемять что-то сверху, и собственно им нужно немного по-другому подходить к вопросу потому, что у них выпадают целые «железные» блоки (известного размера), и я думаю, что там можно упростить математику. Но, что я могу помнить из лекций, как связист…
Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.Стоит упомянуть, что это все относительно размера слова, на 8 битах все легко, но вот когда размер слова измеряется килобайтами становится весело.
Просто, ТС не упомянул, что в любых системах хранениях данных HDD/SDD и так применяется избыточное кодирование на аппаратном уровне и им (в яндексе) нужно примемять что-то сверху, и собственно им нужно немного по-другому подходить к вопросу потому, что у них выпадают целые «железные» блоки (известного размера), и я думаю, что там можно упростить математику. Но, что я могу помнить из лекций, как связист…
Выше ответил на Вашу критику. Насколько я понимаю, она касается терминологии.
Хорошая книга по теории помехоустойчивого кодирования с примерами:
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгортмы, применение.
Моя настольная книга по ECC.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Коды избыточности: простыми словами о том, как надёжно и дёшево хранить данные