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

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

§

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

⊗

Страница — в переработке. Начало работ — 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) Проверялось, естественно, на вручную!