УказательРазделыОбозначенияАвторО проекте


{}_{.} Настоящий раздел поддерживается компанией


§

Математические основы излагаемых в разделе материалов ЗДЕСЬ

Страница — в переработке. Начало работ — 06.04.2016, окончание — ??.??.????


Математика отказоустойчивых дисковых массивов

Одним из способов повышения производительности при обмене данными с жестким диском является объединение нескольких дисков в единый массив и распараллеливание операций чтения и записи. RAID1) — технология хранения, обеспечивающая сохранность и/или возможность восстановления данных с помощью различных алгоритмических и технологических методов организации контроля процесса записи на диск. В настоящем разделе RAID-технология будет разбираться на примере задачи восстановления двух дисков (RAID-6).

При использовании этой технологии данные для обмена с жестким диском собираются в большие массивы — страйпы2), которые сегментируются (разбиваются) на блоки одинаковой длины. Количество таких блоков должно совпадать с количеством дисковых массивов, и операция записи на жесткий диск (или считывания с него) производится одновременно (параллельно) для всех блоков. Для упрощения терминологии, в настоящем разделе будем говорить о дисках, имея в виду составляющие страйп блоки.

Идея

Рассмотрим страйп, состоящий из пяти четырехразрядных дисков:

(D_0,D_1,D_2,D_3,D_4) \quad npu \quad D_j=(d_{j1},d_{j2},d_{j3},d_{j4}) , \quad \{d_{j\ell}\} \subset \{0,1\} \ .

Каждый из этих дисков будем считать элементом поля Галуа \mathbf{GF}(2^4), c операцией умножения, заданной по двойному модулю 2, f(x) при полиноме

f(x)=x^4+x+1

являющемся неприводимым.

Проверочные диски (синдромы) будем формировать по правилу3):

P=D_0+D_1+D_2+D_3+D_4 \pmod{2}

(контрольная сумма) и

Q=D_0\mathfrak A^{4}+ D_1\mathfrak A^{3}+D_2\mathfrak A^{2}+D_3\mathfrak A+D_4 \quad (\operatorname{modd} \ 2,f(x)) \ .

Здесь \mathfrak A \in \mathbf{GF}(16) — произвольный примитивный элемент поля; в данном примере можно взять \mathfrak A= x, что в дальнейшем и делается. В отличие от синдрома P_{} вычисление синдрома Q_{} требует операции умножения в поле \mathbf{GF}(16), т.е. нахождение коэффициентов остатка от деления полинома

(d_{01}x^3+d_{02}x^2+d_{03}x+d_{04})x^4 +(d_{11}x^3+d_{12}x^2+d_{13}x+d_{14})x^3+
+(d_{21}x^3+d_{22}x^2+d_{23}x+d_{24})x^2+ (d_{31}x^3+d_{32}x^2+d_{33}x+d_{34})x+
+(d_{41}x^3+d_{42}x^2+d_{43}x+d_{44})

на полином f_{}(x) с приведением коэффициентом по модулю 2_{}. Эффективная организация этого умножения — отдельная задача, которую обсудим позже. Можно, например, действовать по такой схеме:

\equiv_{_{2,f(x)}} (d_{01}x^3+d_{02}x^2+d_{03}x+d_{04})(x+1) +
+ \left( (d_{11}x^2+d_{12}x+d_{13})x^4+d_{14}x^3 \right)+
+\left( (d_{21}x+d_{22})x^4+d_{23}x^3+d_{24}x^2 \right) +
+d_{31}x^4+ (d_{32}x^2+d_{33}x+d_{34})x+
+(d_{41}x^3+d_{42}x^2+d_{43}x+d_{44}) \equiv
\equiv_{_{2,f(x)}} (d_{01}x^3+d_{02}x^2+d_{03}x+d_{04})(x+1) +
+(d_{11}x^2+d_{12}x+d_{13})(x+1)+d_{14}x^3 +
+(d_{21}x+d_{22})(x+1)+d_{23}x^3+d_{24}x^2 +
+d_{31}(x+1)+ (d_{32}x^2+d_{33}x+d_{34})x+
+(d_{41}x^3+d_{42}x^2+d_{43}x+d_{44}) \, ,

т.е. каждую возникающую при умножении степень x^4 заменять на x+1 (поскольку это и есть остаток от деления x^4 на полином f_{}(x) по модулю 2_{}). В результате получим полином

\equiv_{_{2,f(x)}} (d_{01}+d_{02}+d_{11}+d_{14}+d_{23}+d_{32}+d_{41})x^3+\dots+ (d_{01}+d_{04}+d_{13}+d_{22}+d_{31}+d_{44}) \, ,

коэффициенты которого и составляют вектор4) синдрома Q_{}:

\begin{array}{rl} Q= & (d_{01}+d_{02}+d_{11}+d_{14}+d_{23}+d_{32}+d_{41},\\ & d_{02}+d_{03}+d_{11}+d_{12}+d_{21}+d_{24}+d_{33}+d_{42}, \\ & d_{01}+d_{03}+d_{04}+d_{12}+d_{13}+d_{21}+d_{22} +d_{31}+d_{34} + d_{43}, \\ & d_{01}+d_{04}+d_{13}+d_{22}+d_{31}+d_{44} ) \, . \end{array}

Таким образом, для одного пятидискового страйпа мы создали две контрольные суммы, а если перевести на язык битов, то для 20 битов информационных составили 8_{} битов служебных. Если записать соотношения, связывающие служебные биты с информационными, то получим систему линейных уравнений, которую можно записать в матричном виде:

(D_0,D_1,D_2,D_3,D_4,P,Q) \mathbf H^{\top}= \mathbb O_{1\times 8}

при записи содержимого дисков в строку и при матрице \mathbf H имеющей порядок 8\times 28

\mathbf H =
=\left( \begin{array}{cccc|cccc|cccc|cccc|cccc|cccc|cccc} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) \, .

Структура этой матрицы будет понятной, если мы перепишем ее в блочном виде — так, как она уже ``разрезана'':

\mathbf H =\left( \begin{array}{lllllcc} E & E & E & E & E & E & \mathbb O \\ \mathbf H_{21} & \mathbf H_{22} & \mathbf H_{23} & \mathbf H_{24} & E & \mathbb O & E \end{array}\right) \ ;

здесь E_{} — единичная, а \mathbb O — нулевая матрицы порядка 4 \times 4. Матрицы \{ \mathbf H_{2j} \}_{j=1}^4 кажутся сформированными хаотично. Тем не менее, закономерность в их ряду имеется. Обозначим

\mathbf F= \mathbf H_{24}= \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array} \right) \, .

Тогда

\mathbf H_{23}= \mathbf F^2,\ \mathbf H_{22}= \mathbf F^3,\ \mathbf H_{21}= \mathbf F^4 \, .

Эта закономерность является проявлением общего правила, которое подробнее описано ЗДЕСЬ.

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

!

Этот момент принципиален: поврежденные информационные биты могут располагаться на разных дисках, но если все такие повреждения можно локализовать в одном или двух дисках, то восстановление возможно. Если же три поврежденных бита разбросаны по трём дискам, то их восстановление невозможно.

П

Пример. Пусть при записи страйпа

\big(\underbrace{1010}_{D_0},\ \underbrace{0111}_{D_1},\ \underbrace{0101}_{D_2},\ \underbrace{1010}_{D_3},\ \underbrace{0011}_{D_4}\big)

происходит потеря (порча) двух дисков D_1 и D_3. Для их восстановления снова используем значения синдромов — исходного страйпа и записанного; только в последнем не учитываем испорченные диски — формально обнуляем все их разряды:

\tilde D_0=D_0,\ \tilde D_1= (0000),\ \tilde D_2=D_2,\ \tilde D_3= (0000),\ \tilde D_4=D_4 \ .

Результаты вычисления синдромов: до записи —

P=(0001), Q=(0011) \, ,

а после записи —

\tilde P=(1100),\ \tilde Q=(1001) \ .

Для восстановления значений утерянных дисков D_1 и D_3 получаем систему сравнений:

\left\{ \begin{array}{rrl} D_1 & +D_3 & \equiv P + \tilde P \\ x^{3} D_1 & +x D_3 & \equiv Q + \tilde Q \end{array} \right. \quad (\operatorname{modd} \ 2,f(x)) \ .

Из первого сравнения выражаем D_3 через D_1 и подставляем во второе:

D_3 \equiv D_1 + P + \tilde P,
\Rightarrow \quad D_1= \left( Q + \tilde Q+ x(P + \tilde P) \right)(x^{3}+x)^{-1}
\Rightarrow \ D_1= \left( (Q + \tilde Q)x^{-1}+ P + \tilde P \right)(x^{2}+1)^{-1} \quad (\operatorname{modd} \ 2,f(x)) \ .

Вычисления отрицательных степеней элементов поля проводим с использованием стандартых упрощений и таблицы из ПУНКТА:

x^{-1} \equiv x^3+1 \, ,
x^2+1 \equiv x^8 \ \Rightarrow \ (x^2+1)^{-1}\equiv x^{-8} \equiv x^7 \equiv x^3 +x+1 \, .

Окончательно:

\begin{array}{ll} D_1&= (x^3+1)(x^3+x+1)(Q + \tilde Q)+(x^3+x+1)(P + \tilde P) \quad (\operatorname{modd} \ 2,f(x)) \equiv (0111),\\ D_3&=(0111)+(0001)+(1100) \pmod{2} =(1010) \ . \end{array}


В общем случае — когда происходит потеря двух дисков D_{j} и D_{k} при 0 \le j< k \le 4 — аналогичные рассуждения приводят к формулам

D_k \equiv D_j + P + \tilde P_{jk}, \quad D_j= \left( (Q + \tilde Q_{jk})x^{-(4-k)}+ P + \tilde P_{jk} \right)(x^{(k-j)}+1)^{-1} \quad (\operatorname{modd} \ 2,f(x)) \ .

Для универсального использования этих «восстанавливающих диски» формул желательно иметь заранее вычисленными выражения

(x^{-1})^t \quad u \quad (x^t+1)^{-1} \quad npu \quad t \in \{0,1,2,3,4\} \ .
§

На всякий случай подчеркну, что этот алгоритм будет работать и для произвольного количества N_{} четырехразрядных дисков в страйпе — если только N\le 15=2^{4}-1, т.е. N_{} не превосходит количества ненулевых элементов поля Галуа \mathbf{GF}(16). А вот в каком месте алгоритм может засбоить если это условие нарушить — догадайтесь сами.

§

Отличие идеологии RAID-6 от практики применения КОДОВ РИДА-СОЛОМОНА состоит в том, что в последней места испорченных дисков (блоков) считаются неизвестными; так что коды Рида-Соломона предназначены для решения более сложной задачи.

Выбор элементов поля, на которые домножаются разряды страйпа в виде убывающих степеней примитивного элемента поля \mathfrak A^{4},\mathfrak A^{3},\mathfrak A^{2},\mathfrak A,\mathfrak A^{0} как раз идет больше из традиции кодов Рида-Соломона. В следующем примере мы выберем другой набор и покажем, что это не повлияет на корректность работы алгоритма восстановления.

П

Пример. Страйп — тот же, что и в разобранном выше примере, так же как и синдром P_{}. Будем считать синдром Q_{}(x) по правилу:

Q(x)\equiv D_0(x)+ D_1(x)x+D_2(x)x^{2}+D_3(x)x^{3}+D_4(x)x^{4} \equiv x^3+1 \quad (\operatorname{modd} \ 2,f(x)) \ .

После потери D_1(x) и D_3(x) его значение: \tilde Q(x) \equiv x^3 \quad (\operatorname{modd} \ 2,f(x)). Формула восстановления:

D_1(x)= \left( (Q(x) + \tilde Q(x))x^{-3}+ P(x) + \tilde P(x) \right)(x^{-2}+1)^{-1} \equiv x^2+x+1 \quad (\operatorname{modd} \ 2,f(x)) .

§

Последний пример в переводе на язык матриц (линейных уравнений над \mathbf{GF}(2)) см. в конце ПУНКТА (только в том пункте нумерацию дисков увеличил на 1_{}).

Общий вид решения

Пусть в нашем распоряжении имеется программная реализация поля Галуа \mathbf{GF}(2^n) и наша задача состоит в восстановлении одного или двух потерянных дисков данных из N_{} записываемых на жесткий диск:

D_0,D_1,\dots,D_{N-1} \ .

Считаем, что количество дисков N \le 2^n-1 и каждый диск представляет собой n_{}-битный блок (A_0,A_1,\dots,A_{n-1}). Этот вектор (или же, в альтернативном представлении, полином A_0x^{n-1}+A_1x^{n-2}+\dots+A_{n-1}) мы будем считать элементом поля, которое порождается некоторым неприводимым полиномом f_{}(x) степени n_{} (т.е. операция умножения элементов поля определяется как умножение полиномов по двойному модулю 2,f(x)). Обозначим \mathfrak{A} — произвольный примитивный элемент поля \mathbf{GF}(2^n). Забегая вперед, отметим существенность условия примитивности элемента для целей настоящего раздела: нам нужно, чтобы степени

\mathfrak{A}^0, \mathfrak{A}^1, \mathfrak{A}^2,\dots, \mathfrak{A}^{2^n-2}

были все различными и, следовательно, порождали все поле \mathbf{GF}(2^n) — за исключением нулевого его элемента5) \mathfrak o.

Будем вычислять синдромы по правилам

\begin{array}{rcrrrr} P&=&D_0+&D_1+&\dots+& D_{N-1}, \\ Q&=&\mathfrak{A}^0 \cdot D_0+&\mathfrak{A}^1 \cdot D_1+&\dots+& \mathfrak{A}^{N-1} \cdot D_{N-1}. \end{array}

Здесь, как и ранее, суммирование понимается поразрядное, умножение — по двойному модулю 2,f(x). Таким образом, к уже имеющимся «информационным» дискам D_0,D_1,\dots,D_{N-1} нужно добавить еще два — «служебных, проверочных»6) диска P_{} и Q_{}, тем самым создается избыточность информации, заявленная в названии технологии RAID. Эта избыточность используется для восстановления дисков, испорченных в процессе записи.

!

Заметим, что, в отличие от Coder sapiens7), запоминающее устройство не способно учуять различия между информационными и служебными дисками, и может — с (примерно) одинаковой вероятностью — запортить любой из них.

Иными словами, испортиться могут не только какие-то из D_0,D_1,\dots,D_{N-1}, но и P_{} или Q_{} (и даже оба служебных диска вместе). Рассмотрим сначала более вероятный случай — порчи двух информационных дисков D_j и D_k при 0\le j < k \le N-1. Снова вычисляем значения синдромов — для набора дисков

D_0,\dots,D_{j-1},\tilde D_j=\mathfrak o,D_{j+1},\dots,D_{k-1},\tilde D_k=\mathfrak o,D_{k+1},\dots,D_{N-1} \ ,

в котором значения запорченных дисков обнуляются:

P_{jk}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} D_{\ell},\quad Q_{jk}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} \mathfrak A^{\ell} D_{\ell} \ .

Тем самым количество служебных дисков увеличивается до четырех. Складывая по модулю 2_{} значения соответствующих синдромов, получаем систему уравнений8)

\left\{ \begin{array}{rrr} D_j+&D_k=&P+P_{jk}, \\ \mathfrak{A}^j D_j+&\mathfrak{A}^k D_k =&Q+Q_{jk}. \\ \end{array} \right.

Мы хотим, чтобы эта система была разрешимой и разрешимой единственным образом в поле \mathbf{GF}(2^n) относительно неизвестных D_j и D_k.

!

Более того, мы хотим, чтобы такими же — однозначно разрешимыми — были все системы при любом выборе индексов j_{} и k_{} (0\le j < k \le N-1).

Это требование оказывается выполненным. В самом деле, домножим первое уравнение на \mathfrak{A}^j и прибавим ко второму (опять же, по модулю 2_{}):

(\mathfrak{A}^j+\mathfrak{A}^k) D_k=\mathfrak{A}^j (P+P_{jk})+Q+Q_{jk} \ .

Утверждается, что \mathfrak{A}^j+\mathfrak{A}^k \ne \mathfrak o. Действительно, в поле характеристики 2_{} имеем \mathfrak{A}^k =-\mathfrak{A}^k (элемент поля \mathbf{GF}(2^n) противоположен сам себе). Таким образом, \mathfrak{A}^j+\mathfrak{A}^k =\mathfrak{A}^j-\mathfrak{A}^k, и вот в этот момент происходит использование свойства примитивности элемента \mathfrak{A}: \mathfrak{A}^j \ne \mathfrak{A}^k. Поскольку любой ненулевой элемент поля имеет обратный относительно умножения, то получаем однозначное разрешение последнего уравнения:

D_k=(\mathfrak{A}^j+\mathfrak{A}^k)^{-1} \left( \mathfrak{A}^j (P+P_{jk})+Q+Q_{jk} \right) \ .

Поскольку обращение элементов поля является нетривиальной задачей, то, имея в виду универсальность использования последней формулы — ее планируется использовать при любых наборах индексов \{j,k\}, 0\le j < k \le N-1, — имеет смысл хранить заранее вычисленными выражения для (\mathfrak{A}^j+\mathfrak{A}^k)^{-1} при всех этих значениях индексов. Легко увидеть, что количество таких элементов равно C_{N-1}^2=(N-1)(N-2)/2. Имеет смысл уменьшить это число, за счет небольшого упрощения последней формулы:

D_k=(\mathfrak e+\mathfrak{A}^{k-j})^{-1} \left( P+P_{jk}+\mathfrak{A}^{-j}(Q+Q_{jk}) \right) \ ;

здесь \mathfrak e — единичный элемент поля9). Количество обращений элементов снизилось до 2N-1. Можно еще уменьшить количество обращений, если воспользоваться цикличностью последовательности \{\mathfrak{A}^{\ell}\}: \mathfrak{A}^{2^n-1}=\mathfrak e и, следовательно, \mathfrak{A}^{-j} = \mathfrak{A}^{2^n-1-j}.

После нахождения значения диска D_k, величина второго испорченного диска определяется из линейного соотношения

D_j=D_k+(P+P_{jk}) \ .

Теперь посмотрим, что произойдет, если запорчен только один информационный диск, скажем D_j, а также один синдром, например Q. В этом случае D_j определяется из соотношений для оставшегося синдрома P_{} и его значения P_{j} , пересчитанного в предположении D_j=\mathfrak o :

D_j=P+ P_j \qquad при \qquad P_j=\sum_{\ell=0 \atop \ell \ne j }^{N-1} D_{\ell} \ .

В случае, когда испорченными являются блоки D_j и P_{}, восстанавливающая формула:

D_j=\mathfrak{A}^{-j} \left(Q+ Q_j \right) \qquad при \qquad Q_j= \sum_{\ell=0 \atop \ell \ne j}^{N-1} \mathfrak A^{\ell} D_{\ell} \ .

Из двух синдромов P_{} и Q вычисление именно последнего наиболее затратно. Любая экономия приветствуется. Одна из них лежит на виду — это схема Хорнера вычисления значения полинома:

Q= D_0+\mathfrak{A} \left( D_1+\mathfrak{A} \left( D_2+\mathfrak{A} \left( D_3+\dots+ \mathfrak{A} \left( D_{N-2} +\mathfrak{A} D_{N-1} \right) \dots \right) \right) \right) \ .

Она позволяет сократить количество умножений на N-1.

Модификации

Три синдрома: полет нормальный

Рассматриваем снова диски данных

D_0,D_1,\dots,D_{N-1}

как элементы поля Галуа \mathbf{GF}(2^n) и ставим задачу состоит в восстановлении от одного до трех потерянных из их числа.

Для решения задачи кажется естественным обобщить правило вычисления синдромов:

\begin{array}{lcrrrr} P_0&=&D_0+&D_1+&\dots+ &D_{N-1} , \\ P_1&=&D_0+&\mathfrak{A}^1 \cdot D_1+&\dots+& \mathfrak{A}^{N-1} \cdot D_{N-1}, \\ P_2&=&D_0+&\mathfrak{B}^1 \cdot D_1+&\dots+& \mathfrak{B}^{N-1} \cdot D_{N-1} \end{array}

при \mathfrak{B} — примитивном элементе поля, отличном от \mathfrak{A}. Выполнения какого свойства мы хотим от этих соотношений? — Если они предназначены для восстановления потерянных дисков в любом количестве от 1_{} до 3_{} (включая, возможно, и синдромы), то необходимое условие заключается в возможности разрешимости любой подсистемы из этих линейных уравнений относительно такого же количества дисков. Это требование можно переписать в виде условия на миноры матрицы этой системы

M =\left[ \begin{array}{lllll} \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^1 & \mathfrak A^2 & \dots & \mathfrak A^{N-1} \\ \mathfrak e & \mathfrak B^1 & \mathfrak B^2 & \dots & \mathfrak B^{N-1} \end{array} \right]_{3\times N} \ .

И от этой матрицы нам нужно, чтобы все ее миноры (любого порядка) были ненулевыми. Ввиду рассуждений предыдущего пункта, понятно, что элементы поля \mathfrak A и \mathfrak B_{} должны быть примитивными и различными: \mathfrak A\ne \mathfrak B. Также понятно, что матрица M_{} — это матрица Вандермонда. Смотрим в таблицу логарифмов с целью найти примитивный элемент поля \mathfrak B, отличный от уже выбранного элемента \mathfrak A. Например, в соответствии с теоремой 3, приведенной ЗДЕСЬ, можно взять \mathfrak B = \mathfrak A^2. Таким образом,

M= \left[ \begin{array}{llllll} \mathfrak e & \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^1 & \mathfrak A^2 & \mathfrak A^3 & \dots & \mathfrak A^{N-1} \\ \mathfrak e & \mathfrak A^2 & \mathfrak A^4 & \mathfrak A^6 & \dots & \mathfrak A^{2(N-1)} \end{array} \right] \, .

Все ее элементы отличны от нуля. Ее миноры второго порядка — одного из следующих видов

\left| \begin{array}{cc} \mathfrak e & \mathfrak e \\ \mathfrak A^{k} & \mathfrak A^{\ell} \end{array} \right|=\mathfrak A^{\ell}-\mathfrak A^k, \ \left| \begin{array}{cc} \mathfrak e & \mathfrak e \\ \mathfrak A^{2k} & \mathfrak A^{2\ell} \end{array} \right|=\mathfrak A^{2\ell}-\mathfrak A^{2k}, \ \left| \begin{array}{cc} \mathfrak A^{k} & \mathfrak A^{\ell} \\ \mathfrak A^{2k} & \mathfrak A^{2\ell} \end{array} \right|=\mathfrak A^k\mathfrak A^{\ell} (\mathfrak A^{\ell}-\mathfrak A^k) \quad npu \quad 0\le k < \ell \le N-1 ;

и все они отличны от нуля. Эти условия гарантируют нам возможность восстановления содержимого любых двух информационных дисков даже в случае, когда дополнительно отказывает любой из служебных. В самом деле, если потеряны диски D_j и D_k, а, в дополнение к ним, еще и P_0, то мы пересчитываем значения синдромов P_{1} и P_{2}, считая поврежденные диски нулевыми (т.е. игнорируя их содержимое):

P_1^{(jk)}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} \mathfrak A^{\ell} D_{\ell} \ , \ P_2^{(jk)}= \sum_{\ell=0 \atop \ell \not\in \{ j, k\}}^{N-1} \mathfrak A^{2\ell} D_{\ell} \ .

Сложив эти уравнения с уравнениями, задающими исходные значения синдромов, получим систему уравнений

\left\{ \begin{array}{rrr} \mathfrak{A}^j D_j+&\mathfrak{A}^k D_k=&P_1+P_1^{(jk)}, \\ \mathfrak{A}^{2j} D_j+&\mathfrak{A}^{2k} D_k =&P_2+P_2^{(jk)}, \end{array} \right.

которая является линейной относительно утерянных дисков D_{j} и D_{k}. Разрешаем систему (либо по формулам Крамера, либо по методу Гаусса), получаем

\begin{array}{ccl} D_j &=& (\mathfrak e+\mathfrak A^{k-j})^{-1}\left[ \mathfrak A^{k-2j} \left( P_1+P_1^{(jk)} \right)+ \mathfrak A^{-2j} \left(P_2+P_2^{(jk)} \right)\right], \\ D_k &=& (\mathfrak e+\mathfrak A^{k-j})^{-1}\left[ \mathfrak A^{-k} \left( P_1+P_1^{(jk)} \right)+ \mathfrak A^{-k-j} \left(P_2+P_2^{(jk)} \right)\right]. \end{array}

Рассмотрим теперь случай порчи трех информационных дисков D_i,D_j,D_k, 0\le i< j < k \le N-1. Им соответствует минор третьего порядка матрицы M_{}

\Delta_{ijk}= \left| \begin{array}{lll} \mathfrak e & \mathfrak e & \mathfrak e \\ \mathfrak A^{i} & \mathfrak A^{j} & \mathfrak A^{k} \\ \mathfrak A^{2i} & \mathfrak A^{2j} & \mathfrak A^{2k} \end{array} \right| = \Delta_{ijk}=(\mathfrak A^{k}-\mathfrak A^{j})(\mathfrak A^{j}-\mathfrak A^{i})(\mathfrak A^{k}-\mathfrak A^{i}) \, .

(определитель Вандермонда ). Он отличен от нуля по условию примитивности элемента \mathfrak A_{}. Пересчитываем значения синдромов P_0, P_{1} и P_{2}, считая поврежденные диски нулевыми (т.е. игнорируя их содержимое):

P_0^{(ijk)}= \sum_{\ell=0 \atop \ell \not\in \{i, j, k\}}^{N-1} D_{\ell},\ P_1^{(ijk)}= \sum_{\ell=0 \atop \ell \not\in \{i, j, k\}}^{N-1} \mathfrak A^{\ell} D_{\ell} \ , \ P_2^{(ijk)}= \sum_{\ell=0 \atop \ell \not\in \{i, j, k\}}^{N-1} \mathfrak A^{2\ell} D_{\ell} \ .

Сложив эти уравнения с уравнениями, задающими исходные значения синдромов, получим систему уравнений

\left\{ \begin{array}{rrrr} D_i + & D_j + & D_k=& P_0+ P_0^{(ijk)}, \\ \mathfrak{A}^i D_i+&\mathfrak{A}^j D_j+&\mathfrak{A}^k D_k=&P_1+P_1^{(ijk)}, \\ \mathfrak{A}^{2i} D_i+&\mathfrak{A}^{2j} D_j+&\mathfrak{A}^{2k} D_k =&P_2+P_2^{(ijk)}, \end{array} \right.

которая однозначно разрешима относительно потерянных дисков.

Четыре синдрома: начинаются проблемы

Дальнейшее развитие идеологии формирования синдромов кажется очевидным. С привлечением матричного формализма можно записать 4_{} вычислительные формулы в виде

\underbrace{\left[ \begin{array}{lllll} \mathfrak e & \mathfrak e & \mathfrak e & \dots & \mathfrak e \\ \mathfrak e & \mathfrak A^1 & \mathfrak A^2 & \dots & \mathfrak A^{N-1} \\ \mathfrak e & \mathfrak A^2 & \mathfrak A^4 & \dots & \mathfrak A^{2(N-1)} \\ \mathfrak e & \mathfrak A^3 & \mathfrak A^6 & \dots & \mathfrak A^{3(N-1)} \end{array} \right]}_{M} \left(\begin{array}{c} D_0 \\ D_1 \\ D_2 \\ \vdots \\ D_{N-1} \end{array}\right)= \left(\begin{array}{c} P_0 \\ P_1 \\ P_2 \\ P_{3} \end{array}\right) \, .

Первая проблема: не для всяких полей \mathbf{GF}(2^n) элемент \mathfrak A^3 будет примитивным. Для n\in \{4,6,8,10,\dots \} точно не будет.

(x^3)^5 \equiv 1 \quad (\operatorname{modd} \ 2,x^4+x+1),
(x^3)^{17} \equiv 1 \quad (\operatorname{modd} \ 2,x^8+x^4+x^3+x+1),
(x^3)^{85} \equiv 1 \quad (\operatorname{modd} \ 2,x^8+x^4+x^3+x^2+1) \ .

Здесь полиномы x^8+x^4+x^3+x^2+1 и x^8+x^4+x^3+x+1 — неприводимые, и каждый из них порождает поле \mathbf{GF}(2^8). На чем это может сказаться?

П

Пример. Поле \mathbf{GF}(2^4), f(x)=x^4+x+1, \mathfrak A=x. Информационные диски D_0,D_1,D_2,D_3,D_4,D_5. Матрица M_{} имеет вид

\left[ \begin{array}{cccccc} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & x & x^2 & x^3 & x+1 & x^2+x \\ 1 & x^2 & x+1 & x^3 + x^2 & x^2+1 & x^2 +x +1 \\ 1 & x^3 & x^3+x^2 & x^3 + x & x^3 +x^2 +x +1 & 1 \end{array} \right] \, .

Теперь предположим, что теряются диски D_0,D_5 и P_1, P_2. Действуя по аналогии с предыдущим пунктом, пересчитаем значения этих двух синдромов, считая D_0=(0000),D_5=(0000), составим систему уравнений

\left\{ \begin{array}{rr} D_0+D_5=&P_0+P_0^{(1234)}, \\ D_0+D_5 =&P_2+P_2^{(1234)} \end{array} \right.

относительно потерянных дисков D_0,D_5. Если она совместна, т.е. P_0+P_0^{(1234)} = P_2+P_2^{(1234)}, то она не может быть однозначно разрешена.

Как обойти эту проблему? Можно было бы заменить последнюю строку матрицы M_{} на строку степеней другого примитивного элемента \mathfrak B_{}, отличного от \mathfrak A_{} и \mathfrak A^2. Однако такая замена приведет к другой проблеме, о которой будет рассказано ниже.

Можно пойти другим путем: отказаться от требования примитивности, и убедиться только, что все участвующие в матрице M_{} степени

\mathfrak e, \mathfrak A^3, \mathfrak A^6, \dots , \mathfrak A^{3(N-1)}

являются различными. Так, если мы действуем в поле \mathbf{GF}(2^8), порожденным полиномом x^8+x^4+x^3+x+1, то вполне спокойно можем применять матрицу M_{} для \mathfrak A=x, если только в наших исправительных работах участвуют не более N=17 дисков. А если взять порождающим полиномом поля f(x)=x^8+x^4+x^3+x^2+1, то количество дисков можно увеличить вплоть до N=85.

§

Иными словами, примитивность элемента \mathfrak A — хорошее свойство, но особенно сильно держаться за него не стоит. Если можно гарантировать различность элементов \mathfrak e, \mathfrak A, \mathfrak A^2, \dots , \mathfrak A^{(N-1)} — то для целей этого вполне достаточно. В терминологии полей Галуа — показатель элемента \mathfrak A должен быть больше N-1. Для поля \mathbf{GF}(2^n) этот показатель находится среди делителей числа 2^n-1 (так что достаточно проверить на равенство 1_{} нескольких вполне определенных степеней элемента, а не всех подряд идущих…)

Такое решение проблемы позволяет сохранить структуру матрицы M_{} как матрицы Вандермонда. Это обстоятельство гарантирует выполнение условия: любой минор порядка 4_{} этой матрицы

\left| \begin{array}{llll} \mathfrak e & \mathfrak e & \mathfrak e & \mathfrak e \\ \mathfrak A^{j_1} & \mathfrak A^{j_2} & \mathfrak A^{j_3} & \mathfrak A^{j_4} \\ \mathfrak A^{2j_1} & \mathfrak A^{2j_2} & \mathfrak A^{2j_3} & \mathfrak A^{2j_4} \\ \mathfrak A^{3j_1} & \mathfrak A^{3j_2} & \mathfrak A^{3j_3} & \mathfrak A^{3j_4} \end{array} \right|=
=(\mathfrak A^{j_2}-\mathfrak A^{j_1})(\mathfrak A^{j_3}-\mathfrak A^{j_1})(\mathfrak A^{j_4}-\mathfrak A^{j_1}) (\mathfrak A^{j_3}-\mathfrak A^{j_2})(\mathfrak A^{j_4}-\mathfrak A^{j_2})(\mathfrak A^{j_4}-\mathfrak A^{j_3})

отличен от нуля; здесь 0\le j_1<j_2<j_3<j_4 \le N-1. Система линейных уравнений, матрица которой заключена в этом определителе, будет однозначно разрешимой относительно 4 неизвестных. Следовательно, мы всегда сможем восстановить содержимое утерянных информационных дисков D_0,D_1,\dots,D_{N-1}, если их количество \le 4.

Так вот, вторая проблема возникает в случае, если наряду с потерянными информационными дисками, будут потеряны еще и служебные, т.е. синдромы.

П

Пример. Поле \mathbf{GF}(2^8), f(x)=x^8+x^4+x^3+x^2+1, \mathfrak A=x. Информационные диски D_0,D_1,D_2,\dots, D_{36}. Портятся информационные диски D_1, D_4, D_{36} и синдром P_1. Определитель, составленный из коэффициентов при поврежденных дисках в первом, третьем и четвертом уравнениях для оставшихся синдромов, имеет вид10)

\left|\begin{array}{ccc} 1 & 1 & 1 \\ x^2 & x^8 & x^{72} \\ x^3 & x^{12} & x^{108} \end{array} \right|\equiv \left|\begin{array}{ccc} 1 & 1 & 1 \\ x^2 & x^4+x^3+x^2+1 & x^6+x^5+x^2+1 \\ x^3 & x^7+x^6+x^3+x^2+1 & x^7+x^6+x^4 \end{array} \right| \equiv 0 \quad (\operatorname{modd} \ 2,x^8+x^4+x^3+x^2+1)

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

Откуда взялась такая напасть? — Из потери структуры вандермондности. Определитель, который нам встретился, имел пропуск строки степеней, т.е. в общем случае, имел вид

\left|\begin{array}{ccc} 1 & 1 & 1 \\ x_1^2 & x_2^2 & x_3^2 \\ x_1^3 & x_2^3 & x_3^3 \end{array} \right| \, .

В отличие от определителя Вандермонда, его выражение

\equiv (x_3-x_2)(x_3-x_1)(x_2-x_1)(x_1x_2+x_1x_3+x_2x_3)

сильно затрудняет возможность проверки на равенство 0_{} при всех возможных комбинациях значений x_1, x_2, x_3. Условие различности всех элементов сохраняется как необходимое, но как гарантировать выполнение x_1x_2+x_1x_3+x_2x_3 \ne 0?

§

Тут выделяется отдельная задача (в произвольных, не только конечных, полях) вычисления обобщенного определителя Вандермонда, т.е.

\left| \begin{array}{cccc} x_1^{n_1} & x_2^{n_1} & \dots & x_m^{n_1} \\ x_1^{n_2} & x_2^{n_2} & \dots & x_m^{n_2} \\ \vdots & & & \vdots \\ x_1^{n_m} & x_2^{n_m} & \dots & x_m^{n_m} \end{array} \right| \quad npu \quad n_1<n_2<\dots < n_m \, .

Один из подходов к решению этой задачи см. ЗДЕСЬ. Итог неутешителен для целей восстановления утерянных дисков: всегда возникает условие на элементы x_1,x_2,\dots, x_m, трудное в проверке.

Как решать эту проблему? — Можно попробовать использовать другой тип матриц, отличный от матриц Вандермонда. От кандидата мы хотим только одного: простоты проверки на равенство нулю любого его минора. Лезем в запасники — нет ли чего у классиков? Есть! У Коши всё есть! Определитель Коши

\det \left[\frac{1}{a_j+b_k} \right]_{j,k=1}^n= \left|\begin{array}{cccc} \frac{1}{a_1+b_1} &\frac{1}{a_1+b_2}&\ldots&\frac{1}{a_1+b_n}\\ & & & \\ \frac{1}{a_2+b_1} &\frac{1}{a_2+b_2}&\ldots&\frac{1}{a_2+b_n}\\ & & & \\ \vdots & \vdots & & \vdots\\ \frac{1}{a_n+b_1} &\frac{1}{a_n+b_2}&\ldots&\frac{1}{a_n+b_n} \end{array}\right|_{n\times n}=\frac{ \displaystyle{\prod_{1\le j < k\le n}[(a_j-a_k)(b_j-b_k)]}} {\displaystyle{\prod_{j, k= 1}^n(a_j+b_k)}}

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

Систематическое кодирование

Заметим, что во всех контрпримерах предыдущего параграфа специфической особенностью являлось вычеркивание строк в матрице Вандермонда, что немедленно влекло за собой усложнение вычисления миноров. Это вычеркивание строк было вызвано установкой, что порче подвергались не только информационные диски, но и диски синдромов. То есть, если каким-то образом удалось бы гарантировать, что «старые» значения синдромов не стираются, то можно было бы спокойно распространить вандермондовский подход на любое число информационных дисков.

Но как этого добиться?

Источники

[1]. Anvin H.P. The mathematics of RAID-6. Текст ЗДЕСЬ.

[2]. RAID. Wikipedia, The Free Encyclopedia.

[3]. Standard RAID levels. Wikipedia, The Free Encyclopedia.

1) Redundant Array of Independent Disks (первоначальный вариант расшифровки аббревиатуры — Redundant Array of Inexpensive Disks) — избыточный массив независимых (жестких) дисков
2) stripe (англ.) — полоса.
3) Обозначения P_{} и Q_{} — традиционные.
4) Мы намеренно не заостряем внимания каким именно вектором — столбцом или строкой — являются рассматриваемые векторы. В теории кодирования больше тяготеют к формализму строк. Мы будем использовать обе возможности.
5) На всякий случай, напомню: нулевой элемент поля \mathfrak o интерпретируется либо как нулевой n_{}-битный блок (0,\dots,0), либо как тождественно нулевой полином 0\cdot x^{n-1}+0\cdot x^{n-2}+\dots+0\cdot x + 0.
6) В слэнге RAID-технологов принята терминология «data disks - redundancy disks». Терминологию «информационный-проверочный» я перетащил из теории кодирования.
7) (лат.) — программист разумный; редкий подвид Homo sapiens ;-)
8) Cтрого говоря, это — система сравнений по двойному модулю 2,f(x).
9) Его всегда можно считать либо n-битным блоком (0,0,\dots,0,1) или тождественно равным 1_{} полиномом 0\cdot x^{n-1}+0\cdot x^{n-2}+\dots+ 0\cdot x+1.
10) Проверялось, естественно, на вручную!

2018/06/22 10:21 редактировал au