В интернете много статей о восстановлении информации в массиве RAID-6 и о том, как сделать собственную реализацию такого массива. Но большинство этих статей напичканы математическими формулами. Чтобы понять реальный алгоритм, приходится тратить очень много времени.

В этой статье постараюсь показать простой пример собственной системы исправления ошибок на основе RAID-6. В частности, рассмотрим ситуацию, когда нужно обеспечить избыточность системы, чтобы она выдерживала сбой одного или двух накопителей.

В качестве бонуса информация о том, как работает исправление ошибок в RAID-5, потому что RAID-6 — это улучшенная версия RAID-5.

Обзор

Предположим, у вас три диска с некоторыми данными. Назовём их D1, D2 и D3. Чтобы применить систему типа RAID-6, вам понадобятся два дополнительных диска: PD и RS. Через несколько минут я опишу, что означают PD и RS. Итак, в общей сложности пять дисков: D1, D2, D3, PD и RS.



Итак, ситуация:

• D1, D2 и D3 содержат произвольные данные. Предположим, фотографии кошек.
  
• Специальный диск PD (Parity Drive, иногда P в документации) содержит заксоренные данные, автоматически сгенерированные из D1, D2 и D3.
  
• Второй специальный диск RS (коды Рида — Соломона, иногда его называют Q) для тех же данных, что и PD.

Посмотрим, как выполнять базовые операции на таком массиве.

Как работает восстановление

Если правильно рассчитать PD и RS, то можно безболезненно пережить сбой до двух дисков. Процедура восстановления зависит от того, какие конкретно диски выйдут из строя. Обычно рассматривается семь ситуаций. Ниже они отсортированы от простого к сложному.

1. Потеря PD (только одного диска).
   
   
   
   Очень простой случай. Диск PD содержит только автоматически сгенерированные данные, поэтому его можно восстановить, используя исходные данные на дисках D1, D2 и D3.
   
   
2. Потеря одного из дисков с данными: D1, D2 или D3 (только одного накопителя).
   
   
   
   В этом случае мы теряем данные, но только один диск, поэтому сценарий восстановления такой же, как и в RAID-5: используем PD с двумя оставшимися дисками данных для восстановления данных с отсутствующего диска. Если у нас осталось два диска данных и PD, мы всегда можем сгенерировать данные для третьего диска. В данном случае RS не нужен (и вообще не используется в этом сценарии).
   
   
3. Потеря RS (отказ только одного диска).
   
   
   
   Аналогично ситуации из пункта 1: у нас есть все накопители данных, и мы можем просто регенерировать RS, заново рассчитав коды Рида — Соломона.
   
   
4. Потеря PD и RS (отказ двух дисков).
   
   
   
   Этот случай очень похож на пункты 1 или 3. Все данные остались нетронуты, поэтому можно очень легко перегенерировать содержимое накопителя PD, а затем RS.
   
   
5. Потеря RS и одного накопителя данных (отказ двух накопителей).
   
   
   
   В этом случае мы теряем два диска, но только один из потерянных дисков заполнен данными. Поскольку у нас остался неповреждённый PD, мы можем использовать его для регенерации данных с отсутствующего диска данных, так что этот случай не так сильно отличается от случая № 2. После этого у нас в наличии все диски данных, так что можно легко регенерировать диск RS.
   
   
6. Потеря PD и одного накопителя данных (выход из строя двух накопителей).
   
   
   
   Этот случай гораздо сложнее. Мы теряем один диск с пользовательскими данными (в данном примере D3), и у нас нет диска PD, чтобы помочь с восстановлением. Придётся использовать RS в сочетании с оставшимися дисками пользовательских данных (D1 и D2), чтобы восстановить отсутствующий диск данных D3. После этого мы сможем вычислить содержимое отсутствующего PD. Это первый случай, когда вступает в игру восстановление с помощью кодов Рида — Соломона.
   
   
7. Потеря двух накопителей данных (отказ двух накопителей).
   
   
   
   Самый сложный сценарий. Нужно использовать как PD, так и RS для регенерации обоих накопителей данных. Это возможно только благодаря кодам Рида — Соломона.

В следующих разделах изучим подробнее эти случаи и посмотрим исходный код (на Python), который выполняет фактическое восстановление данных.

Имейте в виду, что на самом деле в настоящих массивах RAID-6 не выделяется целый диск для PD или RS. Эти данные распределяются по всем дискам. Различные контроллеры используют разные методы: левый асинхронный (left asynchronous) или правый синхронный (right synchronous), может быть сдвиг относительно RAID-данных, задержки и т. д. Оставим в стороне обсуждение, почему всё происходит именно так и как выглядят реальные полосы данных RAID-6. Сфокусируемся конкретно на кодах Рида — Соломона.

Тестовые данные

Определим «пользовательские данные». Для простоты установим размер каждого «диска» 5 байт.


Теперь более подробно рассмотрим упомянутые сценарии.

Ситуация 1. Потеря диска PD

Чтобы сгенерировать PD, нужны только диски с пользовательскими данных. В нашем случае это D1, D2 и D3. Диск PD состоит просто из XOR всех пользовательских данных.

Чтобы сгенерировать смещение 0 для PD, нужно заксорить все байты из смещения 0 со всех дисков. То же самое для offset 1 и так далее:

PD[0] = D1[0] xor D2[0] xor D3[0]
PD[1] = D1[1] xor D2[1] xor D3[1]
PD[2] = D1[2] xor D2[2] xor D3[2]
PD[3] = D1[3] xor D2[3] xor D3[3]
PD[4] = D1[4] xor D2[4] xor D3[4]

Пример:

PD[0] = 0x66 xor 0x73 xor 0x74  =>  0x61
PD[1] = 0x69 xor 0x65 xor 0x63  =>  0x64
PD[2] = 0x72 xor 0x63 xor 0x69  =>  0x78
PD[3] = 0x73 xor 0x6e xor 0x72  =>  0x6f
PD[4] = 0x74 xor 0x64 xor 0x64  =>  0x74

Да, всё очень просто. Сделайте это для дисков целиком (в нашем случае 5-байтных), и получите корректно сгенерированный PD:


Таким образом, если выйдет из строя только PD, довольно тривиально восстановить его из D1, D2 и D3.

Ситуация 2. Потеря одного из накопителей данных: D1, D2 или D3

Кстати, именно так работает исправление ошибок RAID-5. Если только один диск с пользовательскими данными выйдет из строя, мы можем использовать диск PD для пересчёта недостающих пользовательских данных.

Допустим, потерян D2. В наличии остались D1, D3, PD и RS. В этом случае даже не трогаем RS. Нужны только диски D1, D3 и PD. Чтобы вычислить недостающие данные, можно снова использовать функцию XOR, как в предыдущей ситуации.

Чтобы восстановить пользовательские данные из смещения 0, ксорим байты из нулевых смещений дисков с пользовательскими данными, которые остались (D1 и D3), с байтом из нулевого смещения PD. Повторяем для смещения 1 и так далее:

D2[0] = D1[0] xor D3[0] xor PD[0]
D2[1] = D1[1] xor D3[1] xor PD[1]
D2[2] = D1[2] xor D3[2] xor PD[2]
D2[3] = D1[3] xor D3[3] xor PD[3]
D2[4] = D1[4] xor D3[4] xor PD[4]

Пример:

D2[0] = 0x66 xor 0x74 xor 0x61  =>  0x73 (s)
D2[1] = 0x69 xor 0x63 xor 0x64  =>  0x65 (e)
D2[2] = 0x72 xor 0x69 xor 0x78  =>  0x63 (c)
D2[3] = 0x73 xor 0x72 xor 0x6f  =>  0x6e (n)
D2[4] = 0x74 xor 0x64 xor 0x74  =>  0x64 (d)

Как видите, восстановить данные с пропавшего диска очень легко. Не имеет значения, какой диск отсутствует: функция XOR работает всегда.

Ситуация 3. Потеря диска RS

Теперь вступают в дело коды Рида — Соломона и поля Галуа. Но не волнуйтесь, необязательно быть математиком, чтобы их использовать.

Когда мы теряем только диск RS или создаём новую систему типа RAID-6, то нужно просто заново сгенерировать коды. Для этого используются таблицы gflog и gfilog с неизменяемым содержимым, а также данные с существующих накопителей D1, D2 и D3.

Таблица gflog всегда выглядит так:

0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf.

Таблица gfilog также постоянна:

0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01.

Необязательно включать эти таблицы в программу, можно использовать такой алгоритм генерации в рантайме:

# gflog_tables.py

def generate_tables():
    polynomial = 0x11d
    s = 8
    gf_elements = 1 << s

    gflog = gf_elements * [0]
    gfilog = gf_elements * [0]

    b = 1
    for i in range(0, gf_elements):
        gflog[b] = i & 255
        gfilog[i] = b & 255
        b <<= 1
        if b & gf_elements:
            b ^= polynomial

    gflog[1] = 0;
    return (gflog, gfilog)

def dump_table(caption, tab):
    item = 0
    print("--- {} ---".format(caption))
    for i in tab:
        print("0x{:02x}, ".format(i), end="")
        item += 1
        if item % 16 == 0:
            item = 0
            print()
    print("")

(gflog, gfilog) = generate_tables()

# Uncomment if you want to see the tables on the console:
#
# dump_table("gflog", gflog)
# dump_table("gfilog", gfilog)

После объявления таблиц нужно определить некоторые операции. Сейчас мы работаем в конечном поле (поле Галуа), так что основные арифметические операции имеют другую реализацию (хотя смысл отчасти схож). Нужно переопределить основные операции — сложение, умножение и деление:

# rs_functions.py

from gflog_tables import *

# Addition
def gf_add(*args):
    result = 0
    for arg in args:
        result ^= arg

    return result

# Indexing
# First drive is 1, second drive is 2, etc...
def gf_drive(index):
    global gfilog

    return gfilog[index - 1]

# Multiplication
def gf_mul(a, b):
    global gflog
    global gfilog

    if a == 0 or b == 0:
        return 0
    else:
        return gfilog[(gflog[a] + gflog[b]) % 255]

# Division helper
def sub_gf8(a, b):
    if a > b:
        return a - b
    else:
        return (255 - (0 - (a - b)))

# Division
def gf_div(a, b):
    global gfilog
    global gflog

    return gfilog[sub_gf8(gflog[a], gflog[b])]

Поскольку вспомогательные функции объявлены, попробуем сгенерировать данные диска RS.

# case 3 -- recover_rs.py

from rs_functions import *

# Here are our drives, together with their data.
image1 = [ ord('f'), ord('i'), ord('r'), ord('s'), ord('t') ]
image2 = [ ord('s'), ord('e'), ord('c'), ord('n'), ord('d') ]
image3 = [ ord('t'), ord('h'), ord('i'), ord('r'), ord('d') ]

# This is a placeholder for our RS drive. It will be regenerated
# in the lines below.
imageRS = [0] * 5

# And this is our loop that generates the RS data using nothing more
# than the user data drives.
for i in range(0, 5):
    imageRS[i] = gf_add(gf_mul(gf_drive(1), image1[i]),
                        gf_mul(gf_drive(2), image2[i]),
                        gf_mul(gf_drive(3), image3[i]))

dump_table("imageRS", imageRS)

После запуска скрипта recover_rs.py диск RS содержит следующие данные:


На данный момент диски D1, D2 и D3 защищены полным алгоритмом исправления ошибок RAID-6, поскольку у нас есть правильно сгенерированные PD и RS.

Важно помнить, что текущие данные RS действительны только для D1, D2 и D3 в этом конкретном порядке. Таким образом, RS для D1, D2 и D3 будет отличаться от D3, D2 и D1, даже если фактические данные на дисках одинаковы. Это важно помнить, потому что при восстановлении данных RAID-6 нужно знать правильную последовательность дисков внутри массива. К счастью, если массив невелик, можно принудительно сгенерировать данные RS, чтобы обнаружить правильную последовательность дисков.

Ситуация 4. Потеря PD и RS

Это тоже простая ситуация: выполняем сначала сценарий № 1, а затем № 3.

Повторяю, в этом случае пользовательские данные не тронуты. Мы можем использовать их для создания PD. Затем для создания RS. Оба случая уже были описаны в пунктах 1 и 3.

Ситуация 5. Потеря RS и одного диска с данными

И здесь несложно. Мы потеряли один диск с данными, но остался PD, поэтому можно выполнить сценарий № 2, чтобы восстановить отсутствующий диск данных. Затем использовать все диски данных для регенерации RS, как в сценарии № 3. Теперь полный набор дисков восстановлен.

Ситуация 6. Потеря PD и одного диска с данными

Общий подход заключается в том, чтобы сначала восстановить отсутствующий диск с данными, используя другие диски в сочетании с RS, а затем, после того как восстановим все диски данных, приступить к регенерации PD (сценарий № 2).

В этой ситуации придётся сделать некоторые расчёты. Предположим, что вместе с PD мы потеряли и диск данных D2. Итак, у нас в наличии D1, D3 и RS.

Благодаря диску RS мы можем восстановить D2, скомбинировав D1, D3 и RS, вот так:

# case 6 -- recover_d2_and_pd.py

from rs_functions import *

# We have these drives...
image1 = [ ord('f'), ord('i'), ord('r'), ord('s'), ord('t') ]
image3 = [ ord('t'), ord('h'), ord('i'), ord('r'), ord('d') ]
imageRS = [ 0x4d, 0x1e, 0x0d, 0x7a, 0x31 ]

# ...and these drives are dead
imagePD = [0] * 5
image2 = [0] * 5

for i in range(0, 5):
    partialRS = gf_add(gf_mul(gf_drive(1), image1[i]),
                       imageRS[i],  # Use RS drive instead of the dead drive.
                       gf_mul(gf_drive(3), image3[i]))

    # gf_drive(2) is our dead drive.
    div_result = gf_div(1, gf_drive(2))

    # This will generate the data from the dead D2 drive.
    image2[i] = gf_mul(div_result, partialRS)

    # This will generate the data from the dead PD drive.
    imagePD[i] = gf_add(image1[i], image2[i], image3[i])

dump_table("image2", image2)
dump_table("imagePD", imagePD)

Во-первых, нужно сгенерировать значение partialRS путём прибавления (gf_add) возвращаемых значений gf_mul для всех байтов всех допустимых дисков вместе со значением RS вместо отсутствующего диска данных (в нашем случае D2).

Затем используем значение partialRS для регенерации данных D2 путём деления единицы на индекс мёртвого диска (gf_drive(2)) и умножения результата на partialRS. Аргумент gf_drive(2) указывает индекс нашего мёртвого диска. Если бы из строя вышел D1, мы бы здесь использовали gf_drive(1).

После регенерации D2 восстановим все диски данных. В этом случае производим регенерацию PD как в сценарии № 1: в приведённом выше коде это делается с помощью сложения (gf_add) данных со всех дисков. Если помните, gf_add над полем Галуа — простая операция XOR, поэтому вместо ручного ксоринга байтов со всех дисков данных можно использовать операцию gf_add.

Ситуация 7. Потеря двух накопителей данных

Это самый интересный и самый сложный сценарий. Предположим, диски D2 и D3 вышли из строя. В этом случае нужно каким-то образом использовать диски D1, PD и RS для регенерации недостающих дисков.

Это особый подход, отличный от предыдущих случаев. Общий подход заключается в том, чтобы сначала сгенерировать данные для D2, а затем использовать ту же оценку, что и в сценарии № 2, для генерации данных D3. Вот код:

# case 7 -- recover_d2_and_d3.py

from rs_functions import *

# These drives are still alive.
image1 = [ ord('f'), ord('i'), ord('r'), ord('s'), ord('t') ]
imagePD = [ 0x61, 0x64, 0x78, 0x6f, 0x74 ]
imageRS = [ 0x4d, 0x1e, 0x0d, 0x7a, 0x31 ]

# These drives are dead, we can't read from them.
image2 = [0] * 5
image3 = [0] * 5

for i in range(0, 5):
    partialPD = gf_add(image1[i]) # add other drives if they exist
    partialRS = gf_add(gf_mul(gf_drive(1), image1[i])) # add other drives if they exist

    g = gf_div(1, gf_add(gf_drive(2), gf_drive(3)))
    xoredPD = gf_add(partialPD, imagePD[i])
    xoredRS = gf_add(partialRS, imageRS[i])
    mid = gf_add(gf_mul(gf_drive(3), xoredPD), xoredRS) # gf_drive(3) is the second drive we've lost

    # Regenerate data for D2.
    data = gf_mul(mid, g)
    image2[i] = data

    # Regenerate data for D3.
    image3[i] = gf_add(image1[i], image2[i], imagePD[i])

    # or:
    #
    # image3[i] = gf_add(data, xoredPD)

dump_table("image2", image2)
dump_table("image3", image3)

Во-первых, нужно сложить все байты со всех существующих дисков данных, чтобы сгенерировать partialPD. В этом примере у нас только один диск данных, поэтому параметр partialPD будет просто содержимым диска D1. Но массивы RAID-6 охватывают множество дисков. Поэтому если у нас более одного диска данных, например, три живых диска данных, то вычисление partialPD выглядело бы следующим образом:

partialPD = gf_add(image1[i], image2[i], image3[i])

Далее нам понадобится параметр partialRS. Его можно вычислить, добавив данные с существующих дисков следующим образом:

partialRS = gf_add(A, B, C, ..., Z)

where A = gf_mul(gf_drive(1), image1[i])
      B = gf_mul(gf_drive(2), image2[i]) if we have drive 2
      C = gf_mul(gf_drive(3), image3[i]) if we have drive 3

etc.

В нашем случае остался только один накопитель данных (D1), поэтому наш partialRS — это просто gf_mul(gf_drive(1), image1[i]).

Затем нужно сгенерировать параметр g, разделив единицу на сумму индексов мёртвых дисков (D2 и D3).

Далее следует параметр xoredPD; он вычисляется путём добавления содержимого PD к параметру partialPD, вычисленному ранее. Следующий параметр xoredRS вычисляется аналогично, путём добавления partialRS к содержимому RS.

Теперь сложная часть. Можно вычислить данные с первого сломанного диска, то есть с диска D2. Для этого нужно умножить индекс второго сломанного диска (D3) на параметр xoredPD и добавить к результату параметр xoredRS. Затем, после умножения результата на параметр g, мы получим содержимое диска D2.

Поскольку мы только что восстановили данные для D2, отныне этот случай ничем не отличается от сценария № 2 — потери одного диска данных (D3). Чтобы создать диск D3, нужно сложить с PD все живые диски данных (D1 и D2).

Готово! Мы вернули полный комплект дисков.

Эпилог

Я выбрал Python для демонстрации, что исправление ошибок с помощью кодов Рида — Соломона не требует особого программирования и вычислительной мощности. Всё очень быстро, и реализация может быть довольно компактной. Конечно, более эффективную реализацию следует написать с учётом параллельной обработки. Поскольку каждый байт вычисляется независимо от других, распараллеливание не сложное.

Стоит отметить, что описанный метод восстановления данных не обязательно использовать на отдельных физических дисках. «Диски» можно рассматривать как «буферы» в процессе передачи данных по ненадёжному каналу, и такое исправление ошибок остаётся эффективным. Здесь требуются более интенсивные вычисления, чем с кодами Хэмминга, зато можно поднять два упавших потока. Это мощная фича для обеспечения отказоустойчивости.

Конечно, RAID-6 далеко не новое изобретение, а коды Рида — Соломона ещё старше. Они использовались ещё в миссии «Вояджер-2», что довольно круто.

Среди более современных альтернатив для кодов Рида — Соломона можно назвать турбокоды — надеюсь, у меня появится возможность покопаться и в них.