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

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

Рассмотрим страйп, состоящий из пяти четырехразрядных дисков: $$ (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 $$ являющемся неприводимым.

Проверочные диски (синдромы) будем формировать по правилу³⁾: $$ 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}) \, , $$ коэффициенты которого и составляют вектор⁴⁾ синдрома $ 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\} \ . $$

Выбор элементов поля, на которые домножаются разряды страйпа в виде убывающих степеней примитивного элемента поля $ \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^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) $ — за исключением нулевого его элемента⁵⁾ $ \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} $ нужно добавить еще два — «служебных, проверочных»⁶⁾ диска $ P_{} $ и $ Q_{} $, тем самым создается избыточность информации, заявленная в названии технологии RAID. Эта избыточность используется для восстановления дисков, испорченных в процессе записи.

Иными словами, испортиться могут не только какие-то из $ 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_{} $ значения соответствующих синдромов, получаем систему уравнений⁸⁾ $$ \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 $.

Это требование оказывается выполненным. В самом деле, домножим первое уравнение на $ \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 $ — единичный элемент поля⁹⁾. Количество обращений элементов снизилось до $ 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 \mbox{ при } \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 \mbox{ при } \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 $.

Такое решение проблемы позволяет сохранить структуру матрицы $ 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 $. Определитель, составленный из коэффициентов при поврежденных дисках в первом, третьем и четвертом уравнениях для оставшихся синдромов, имеет вид¹⁰⁾

$$ \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 $?

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