Русский
Русский
English
Статистика
Реклама

Перевод Коды Рида Соломона в RAID6

В интернете много статей о восстановлении информации в массиве 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байт.

Диск Данные в ASCII Данные в HEX
D1 f i r s t 0x66, 0x69, 0x72, 0x73, 0x74
D2 s e c n d 0x73, 0x65, 0x63, 0x6e, 0x64
D3 t h i r d 0x74, 0x68, 0x69, 0x72, 0x64

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

Ситуация 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  =>  0x61PD[1] = 0x69 xor 0x65 xor 0x63  =>  0x64PD[2] = 0x72 xor 0x63 xor 0x69  =>  0x78PD[3] = 0x73 xor 0x6e xor 0x72  =>  0x6fPD[4] = 0x74 xor 0x64 xor 0x64  =>  0x74

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

Диск Данные в HEX
PD 0x61, 0x64, 0x78, 0x6f, 0x74

Таким образом, если выйдет из строя только 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.pydef 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.pyfrom gflog_tables import *# Additiondef 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]# Multiplicationdef 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 helperdef sub_gf8(a, b):    if a > b:        return a - b    else:        return (255 - (0 - (a - b)))# Divisiondef gf_div(a, b):    global gfilog    global gflog    return gfilog[sub_gf8(gflog[a], gflog[b])]

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

# case 3 -- recover_rs.pyfrom 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 содержит следующие данные:

Диск Данные в HEX
RS 0x4d, 0x1e, 0x0d, 0x7a, 0x31

На данный момент диски 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.pyfrom 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 deadimagePD = [0] * 5image2 = [0] * 5for 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.pyfrom 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] * 5image3 = [0] * 5for 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 3etc.

В нашем случае остался только один накопитель данных (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, что довольно круто.

Среди более современных альтернатив для кодов Рида Соломона можно назвать турбокоды надеюсь, у меня появится возможность покопаться и в них ;)
Источник: habr.com
К списку статей
Опубликовано: 03.12.2020 18:17:56
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Алгоритмы

Математика

Компьютерное железо

Накопители

Raid 6

Коды рида — соломона

Восстановление данных

Поле галуа

Конечное поле

Турбокоды

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru