Указатель — Разделы— Обозначения — Автор — О проекте
Математические основы излагаемых в разделе материалов ☞ ЗДЕСЬ
Страница — в переработке. Начало работ — 06.04.2016, окончание — ??.??.????
Одним из способов повышения производительности при обмене данными с жестким диском является объединение нескольких дисков в единый массив и распараллеливание операций чтения и записи. RAID1) — технология хранения, обеспечивающая сохранность и/или возможность восстановления данных с помощью различных алгоритмических и технологических методов организации контроля процесса записи на диск. В настоящем разделе RAID-технология будет разбираться на примере задачи восстановления двух дисков (RAID-6).
При использовании этой технологии данные для обмена с жестким диском собираются в большие массивы — страйпы2), которые сегментируются (разбиваются) на блоки одинаковой длины. Количество таких блоков должно совпадать с количеством дисковых массивов, и операция записи на жесткий диск (или считывания с него) производится одновременно (параллельно) для всех блоков. Для упрощения терминологии, в настоящем разделе будем говорить о дисках, имея в виду составляющие страйп блоки.
Рассмотрим страйп, состоящий из пяти четырехразрядных дисков:
Каждый из этих дисков будем считать элементом поля Галуа ,
c операцией умножения, заданной по двойному модулю
при полиноме
являющемся неприводимым.
Проверочные диски (синдромы) будем формировать по правилу3):
(контрольная сумма) и
Здесь — произвольный примитивный элемент поля; в данном примере можно взять
, что в дальнейшем и делается.
В отличие от синдрома
вычисление синдрома
требует операции умножения в поле
, т.е. нахождение
коэффициентов остатка от деления полинома
на полином с приведением коэффициентом по модулю
. Эффективная организация этого умножения — отдельная задача, которую обсудим позже. Можно, например, действовать по такой схеме:
т.е. каждую возникающую при умножении степень заменять на
(поскольку это и есть остаток от деления
на полином
по модулю
). В результате получим полином
коэффициенты которого и составляют вектор4) синдрома :
Таким образом, для одного пятидискового страйпа мы создали две контрольные суммы, а если перевести на язык битов, то для битов информационных составили
битов служебных. Если записать соотношения, связывающие служебные биты с информационными,
то получим систему линейных уравнений, которую можно записать в матричном виде:
при записи содержимого дисков в строку и при матрице имеющей порядок
Структура этой матрицы будет понятной, если мы перепишем ее в блочном виде — так, как она уже ``разрезана'':
здесь — единичная, а
— нулевая матрицы порядка
. Матрицы
кажутся сформированными хаотично. Тем не менее, закономерность в их ряду имеется. Обозначим
Тогда
Эта закономерность является проявлением общего правила, которое подробнее описано ☞ ЗДЕСЬ.
На практике, в символьном виде синдромы не хранят, а вычисляют каждый раз для конкретных дисков. Теперь посмотрим как эти синдромы можно использовать для восстановления содержания поврежденных дисков.
Этот момент принципиален: поврежденные информационные биты могут располагаться на разных дисках, но если все такие повреждения можно локализовать в одном или двух дисках, то восстановление возможно. Если же три поврежденных бита разбросаны по трём дискам, то их восстановление невозможно.
Пример. Пусть при записи страйпа
происходит потеря (порча) двух дисков и
. Для их восстановления снова используем значения синдромов — исходного страйпа и записанного; только в последнем не учитываем испорченные диски — формально обнуляем все их разряды:
Результаты вычисления синдромов: до записи —
а после записи —
Для восстановления значений утерянных дисков и
получаем систему сравнений:
Из первого сравнения выражаем через
и подставляем во второе:
Вычисления отрицательных степеней элементов поля проводим с использованием стандартых упрощений и таблицы из ☞ ПУНКТА:
Окончательно:
В общем случае — когда происходит потеря двух дисков и
при
— аналогичные рассуждения приводят к формулам
Для универсального использования этих «восстанавливающих диски» формул желательно иметь заранее вычисленными выражения
На всякий случай подчеркну, что этот алгоритм будет работать и для произвольного количества четырехразрядных дисков в страйпе — если только
, т.е.
не превосходит количества ненулевых элементов поля Галуа
. А вот в каком месте алгоритм может засбоить если это условие нарушить — догадайтесь сами.
Отличие идеологии RAID-6 от практики применения КОДОВ РИДА-СОЛОМОНА состоит в том, что в последней места испорченных дисков (блоков) считаются неизвестными; так что коды Рида-Соломона предназначены для решения более сложной задачи.
Выбор элементов поля, на которые домножаются разряды страйпа в виде убывающих степеней примитивного элемента поля как раз идет больше из традиции кодов Рида-Соломона. В следующем примере мы выберем другой набор и покажем, что это не повлияет на корректность работы алгоритма восстановления.
Пример. Страйп — тот же, что и в разобранном выше примере, так же как и синдром . Будем считать синдром
по правилу:
После потери и
его значение:
. Формула восстановления:
♦
Последний пример в переводе на язык матриц (линейных уравнений над ) см. в конце
☞
ПУНКТА (только в том пункте нумерацию дисков увеличил на
).
Пусть в нашем распоряжении имеется программная реализация поля Галуа и наша задача состоит в восстановлении одного или двух потерянных дисков данных из
записываемых на жесткий диск:
Считаем, что количество дисков и каждый диск представляет собой
-битный блок
. Этот вектор (или же, в альтернативном представлении, полином
) мы будем считать элементом поля, которое порождается некоторым неприводимым полиномом
степени
(т.е. операция умножения элементов поля определяется как умножение полиномов по двойному модулю
). Обозначим
— произвольный примитивный элемент поля
. Забегая вперед, отметим существенность условия
примитивности
элемента для целей настоящего раздела: нам нужно, чтобы степени
были все различными и, следовательно, порождали все поле — за исключением нулевого его элемента5)
.
Будем вычислять синдромы по правилам
Здесь, как и ранее, суммирование понимается поразрядное, умножение — по двойному модулю . Таким образом, к уже имеющимся «информационным» дискам
нужно добавить еще два — «служебных, проверочных»6) диска
и
, тем самым создается избыточность информации, заявленная в названии технологии RAID. Эта избыточность используется для восстановления дисков, испорченных в процессе записи.
Заметим, что, в отличие от Coder sapiens7), запоминающее устройство не способно учуять различия между информационными и служебными дисками, и может — с (примерно) одинаковой вероятностью — запортить любой из них.
Иными словами, испортиться могут не только какие-то из , но и
или
(и даже оба служебных диска вместе). Рассмотрим сначала более вероятный случай — порчи двух информационных дисков
и
при
.
Снова вычисляем значения синдромов — для набора дисков
в котором значения запорченных дисков обнуляются:
Тем самым количество служебных дисков увеличивается до четырех. Складывая по модулю значения соответствующих синдромов, получаем систему уравнений8)
Мы хотим, чтобы эта система была разрешимой и разрешимой единственным образом в поле относительно неизвестных
и
.
Более того, мы хотим, чтобы такими же — однозначно разрешимыми — были все системы при любом выборе индексов и
(
).
Это требование оказывается выполненным. В самом деле, домножим первое уравнение на и прибавим ко второму (опять же, по модулю
):
Утверждается, что . Действительно, в поле характеристики
имеем
(элемент поля
противоположен сам себе). Таким образом,
, и вот в этот момент происходит использование свойства примитивности элемента
:
.
Поскольку любой ненулевой элемент поля имеет обратный относительно умножения, то получаем однозначное разрешение последнего уравнения:
Поскольку обращение элементов поля является нетривиальной задачей, то, имея в виду универсальность использования последней формулы — ее планируется использовать при любых наборах индексов , — имеет смысл хранить заранее вычисленными выражения для
при всех этих значениях индексов. Легко увидеть, что количество таких элементов равно
. Имеет смысл уменьшить это число, за счет небольшого упрощения последней формулы:
здесь — единичный элемент поля9).
Количество обращений элементов снизилось до
. Можно еще уменьшить количество обращений, если воспользоваться цикличностью последовательности
:
и, следовательно,
.
После нахождения значения диска , величина второго испорченного диска определяется из линейного соотношения
Теперь посмотрим, что произойдет, если запорчен только один информационный диск, скажем , а также один синдром, например
. В этом случае
определяется из соотношений для оставшегося синдрома
и его значения
, пересчитанного в предположении
:
В случае, когда испорченными являются блоки и
, восстанавливающая формула:
Из двух синдромов и
вычисление именно последнего наиболее затратно. Любая экономия приветствуется. Одна из них лежит на виду — это схема Хорнера вычисления значения полинома:
Она позволяет сократить количество умножений на .
Рассматриваем снова диски данных
как элементы поля Галуа и ставим задачу состоит в восстановлении от одного до трех потерянных из их числа.
Для решения задачи кажется естественным обобщить правило вычисления синдромов:
при — примитивном элементе поля, отличном от
. Выполнения какого свойства мы хотим от этих соотношений? —
Если они предназначены для восстановления потерянных дисков в любом количестве от
до
(включая, возможно, и синдромы), то необходимое условие заключается в возможности разрешимости любой подсистемы из этих линейных уравнений относительно такого же количества дисков.
Это требование можно переписать в виде условия на миноры матрицы этой системы
И от этой матрицы нам нужно, чтобы все ее миноры (любого порядка) были ненулевыми. Ввиду рассуждений предыдущего пункта, понятно, что элементы поля и
должны быть примитивными и различными:
. Также понятно, что матрица
— это матрица Вандермонда. Смотрим в таблицу логарифмов с целью найти примитивный элемент поля
, отличный от уже выбранного элемента
. Например, в соответствии с теоремой
, приведенной
☞
ЗДЕСЬ, можно взять
. Таким образом,
Все ее элементы отличны от нуля. Ее миноры второго порядка — одного из следующих видов
и все они отличны от нуля. Эти условия гарантируют нам возможность восстановления содержимого любых двух информационных дисков даже в случае, когда дополнительно отказывает любой из служебных. В самом деле, если потеряны диски и
, а, в дополнение к ним, еще и
,
то мы пересчитываем значения синдромов
и
, считая поврежденные диски нулевыми (т.е. игнорируя их содержимое):
Сложив эти уравнения с уравнениями, задающими исходные значения синдромов, получим систему уравнений
которая является линейной относительно утерянных дисков и
. Разрешаем систему (либо по формулам Крамера, либо по методу Гаусса), получаем
Рассмотрим теперь случай порчи трех информационных дисков ,
.
Им соответствует минор третьего порядка матрицы
(определитель Вандермонда ). Он отличен от нуля по условию примитивности элемента .
Пересчитываем значения синдромов
и
, считая поврежденные диски нулевыми (т.е. игнорируя их содержимое):
Сложив эти уравнения с уравнениями, задающими исходные значения синдромов, получим систему уравнений
которая однозначно разрешима относительно потерянных дисков.
Дальнейшее развитие идеологии формирования синдромов кажется очевидным. С привлечением матричного формализма можно записать вычислительные формулы в виде
Первая проблема:
не для всяких полей элемент
будет примитивным. Для
точно не будет.
Здесь полиномы и
— неприводимые, и каждый из них порождает поле
.
На чем это может сказаться?
Пример. Поле ,
. Информационные диски
.
Матрица
имеет вид
Теперь предположим, что теряются диски и
. Действуя по аналогии с предыдущим пунктом, пересчитаем значения этих двух синдромов, считая
, составим систему уравнений
относительно потерянных дисков . Если она совместна, т.е.
, то она не может быть однозначно разрешена.
♦
Как обойти эту проблему? Можно было бы заменить последнюю строку матрицы на строку степеней другого примитивного элемента
, отличного от
и
. Однако такая замена приведет к другой проблеме, о которой будет рассказано ниже.
Можно пойти другим путем: отказаться от требования примитивности, и убедиться только, что все участвующие в матрице степени
являются различными. Так, если мы действуем в поле , порожденным полиномом
, то вполне спокойно можем применять матрицу
для
, если только в наших исправительных работах участвуют не более
дисков.
А если взять порождающим полиномом поля
, то количество дисков можно увеличить вплоть до
.
Иными словами, примитивность элемента — хорошее свойство, но особенно сильно держаться за него не стоит. Если можно гарантировать различность элементов
— то для целей этого вполне достаточно. В терминологии полей Галуа — показатель элемента
должен быть больше
. Для поля
этот показатель находится среди делителей числа
(так что достаточно проверить на равенство
нескольких вполне определенных степеней элемента, а не всех подряд идущих…)
Такое решение проблемы позволяет сохранить структуру матрицы как матрицы Вандермонда. Это обстоятельство гарантирует выполнение условия: любой минор порядка
этой матрицы
отличен от нуля; здесь . Система линейных уравнений, матрица которой заключена в этом определителе, будет однозначно разрешимой относительно
неизвестных. Следовательно, мы всегда сможем восстановить содержимое утерянных информационных дисков
, если их количество
.
Так вот, вторая проблема возникает в случае, если наряду с потерянными информационными дисками, будут потеряны еще и служебные, т.е. синдромы.
Пример. Поле ,
. Информационные диски
.
Портятся информационные диски
и синдром
. Определитель, составленный из коэффициентов при поврежденных дисках в первом, третьем и четвертом уравнениях для оставшихся синдромов, имеет вид10)
Отсюда следует, что из соотношений для оставшихся неповрежденными синдромов (их исходных и пересчитанных после обнаружения повреждений) невозможно однозначно восстановить значения указанных информационных дисков. ♦
Откуда взялась такая напасть? — Из потери структуры вандермондности. Определитель, который нам встретился, имел пропуск строки степеней, т.е. в общем случае, имел вид
В отличие от определителя Вандермонда, его выражение
сильно затрудняет возможность проверки на равенство при всех возможных комбинациях значений
. Условие различности всех элементов сохраняется как необходимое, но как гарантировать выполнение
?
Тут выделяется отдельная задача (в произвольных, не только конечных, полях) вычисления обобщенного определителя Вандермонда, т.е.
Один из подходов к решению этой задачи см.
☞
ЗДЕСЬ. Итог неутешителен для целей восстановления утерянных дисков: всегда возникает условие на элементы , трудное в проверке.
Как решать эту проблему? — Можно попробовать использовать другой тип матриц, отличный от матриц Вандермонда. От кандидата мы хотим только одного: простоты проверки на равенство нулю любого его минора. Лезем в запасники — нет ли чего у классиков? Есть! У Коши всё есть! Определитель Коши
имеет структуру, хотя и более сложную, чем Вандермонда, но у него просто условие проверки на ноль его самого и любого его минора.
Заметим, что во всех контрпримерах предыдущего параграфа специфической особенностью являлось вычеркивание строк в матрице Вандермонда, что немедленно влекло за собой усложнение вычисления миноров. Это вычеркивание строк было вызвано установкой, что порче подвергались не только информационные диски, но и диски синдромов. То есть, если каким-то образом удалось бы гарантировать, что «старые» значения синдромов не стираются, то можно было бы спокойно распространить вандермондовский подход на любое число информационных дисков.
Но как этого добиться?
[1]. Anvin H.P. The mathematics of RAID-6. Текст ☞ ЗДЕСЬ.
[2]. RAID. Wikipedia, The Free Encyclopedia.
[3]. Standard RAID levels. Wikipedia, The Free Encyclopedia.