Вс, 29 ноября 2020 г. :: # datarecovery :: # python

RAID 6 — похож на RAID 5, но имеет более высокую степень надёжности — два (или более) диска данных и два диска контроля чётности. Основан на кодах Рида — Соломона

Ограничения в вариантах по количеству дисков в массиве RAID 6 DP связаны со сложностью вычисления двойной четности «вертикальной полосы» данных на произвольном количестве дисков. Реализации с числом дисков, кратным простому числу, позволяют использовать простые алгоритмы для контроля целостности данных, тогда как в реализациях без таких ограничений используются сложные алгоритмы, что ещё сильнее замедляет работу дискового массива.
Преимуществом RAID 6 является его надёжность — она максимальна из всех массивов данных RAID, это обуславливает область применения массивов RAID 6 — вычислительные среды, в которых требуется обеспечить высокий уровень непрерывной готовности данных.
Недостатки RAID 6 — относительно большие затраты и потери в производительности по сравнению с RAID 5. Производительность RAID 6 — самая низкая среди всех массивов RAID.

RAID-DP
Существует модификация RAID-4 компании NetApp — RAID-DP (Dual Parity). Отличие от традиционного массива заключается в выделении под контрольные суммы двух отдельных дисков. Благодаря взаимодействию RAID-DP и файловой системы WAFL (все операции записи последовательны и производятся на свободное место) пропадает падение производительности как в сравнении с RAID-5, так и в сравнении с RAID-6.

Коды Рида — Соломона в RAID 6

Автор оригинала: Grzegorz Antoniak

Исправление ошибок Рида-Соломона в RAID-6

Оглавление:

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

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

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

Обзор

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

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

D1, D2 и D3 содержат произвольные пользовательские данные , неважно, каково их содержимое. FWIW вы можете предположить, что эти диски полны кошачьих картинок.
Специальный PD диск (названный в честь Parity Drive, иногда называемый Pв технических документах) содержит данные XOR, автоматически сгенерированные из D1, D2 и D3.
Второй специальный RS накопитель (названный в честь Reed-Solomon Drive, иногда также называемый Q) содержит коды Рида-Соломона, рассчитанные на основе тех же данных, что и PD, а именно с накопителей D1, D2 и D3.

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

Как работает рекавери

Если правильно рассчитать PD и RS диски, мы можем потерять до 2-х дисков. Как мы восстанавливаемся после сбоев, зависит от того, какие диски выйдут из строя. Обычно существует 7 случаев, с которыми может справиться RAID-6. В следующих пунктах будут описаны сценарии, отсортированные от самого простого к самому сложному.

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

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

Имейте в виду, что настоящие массивы RAID-6 на самом деле не выделяют весь диск для PD или RS. Реальные массивы охватывают эти дополнительные данные контрольной суммы по всем дискам. Есть несколько методов, используемых различными контроллерами: левый асинхронный, правый синхронный, может быть смещение данных RAID, могут быть задержки шаблонов и т.д. объем этого сообщения в блоге. Так что будем придерживаться только кодов Рида-Соломона.

Данные испытаний

Давайте определимся, как выглядят наши «пользовательские данные». Для простоты давайте представим, что наши «дисковые накопители» имеют размер 5 байтов.

Диск	Данные в ASCII	Данные в HEX
`D1`	первый	0x66, 0x69, 0x72, 0x73, 0x74
`D2`	второй	0x73, 0x65, 0x63, 0x6e, 0x64
`D3`	в третьих	0x74, 0x68, 0x69, 0x72, 0x64

Давайте рассмотрим вышеупомянутые сценарии более подробно.

Случай 1. Потеря `PD` привода.

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

Чтобы сгенерировать смещение 0 PD диска, вам нужно выполнить XOR для всех байтов со смещения 0 со всех дисков.
Затем, чтобы сгенерировать смещение 1 PD диска, вам нужно выполнить XOR байтов со смещения 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 диск:

Диск	Данные в 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, выполните XOR байтов со смещений 0 дисков с пользовательскими данными, которые вы не потеряли ( D1 и D3) вместе с байтом со смещения 0 на 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 и gfilog ):

# 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)

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

# 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 диск содержит эти данные:

Диск	Данные в 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`диска и одного диска с данными.

Этот случай тоже не сложный. Поскольку мы потеряли только 1 диск с данными, но у нас все еще есть 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данных путем деления 1на индекс мертвого диска ( gf_drive(2)) и умножения результата на partialRS. gf_drive(2)Аргумент задает индекс нашего мертвого диска — если наш D1диск потерпит неудачу, мы будем использовать gf_drive(1)здесь.

После регенерации D2все диски с данными будут регенерированы. В этом случае мы можем продолжить регенерацию PDподобного в случае №1: это делается в приведенном выше коде путем добавления gf_addданных со всех дисков. Если вы помните, gf_addнад полем Галуа выполняется простая операция XOR, поэтому вместо ручного выполнения 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. В этом примере у нас есть только 1 диск с данными, поэтому partialPDпараметром будет просто содержимое D1диска с данными. Но массивы RAID-6 могут охватывать множество дисков, поэтому, если бы у нас осталось более 1 диска с данными, например, если бы у нас было 3 все еще работающих диска с данными, то 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.

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

Затем нам нужно сгенерировать gпараметр, разделив его 1на сумму наших индексов неработающего диска ( D2и D3).

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

А теперь самое сложное. Мы можем рассчитать данные с первого отказавшего диска , поэтому данные с D2диска. Все, что нам нужно сделать, это умножить индекс второго отказавшего диска (диска D3) на xoredPDпараметр и добавить xoredRSпараметр к результату. Затем, умножив результат на gпараметр, мы получим содержимое D2диска. Ух!

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

Выполнено! Мы вернули все наши диски с данными.

Эпилог

Я выбрал язык Python, чтобы продемонстрировать, что восстановление после ошибок на основе кодов Рида-Соломона не требует большого количества программирования или вычислительной мощности. Это очень быстро, и реализация может быть довольно компактной. Конечно, чтобы сделать вещи еще быстрее, реализация, вероятно, должна быть написана с использованием параллельной обработки, но поскольку каждый байт может быть вычислен независимо от других, проблема распараллеливания не очень сложна.

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

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

Более новые альтернативы для кодов RS включают Turbocodes — я надеюсь, что у меня будет возможность в ближайшее время покопаться в них;)

В любом случае, получайте удовольствие!

RAID 6 и другие RAID-JBOD,0,01,1,1E,2,3,4,5,6,10,50,60,RAID-Z,RAID-Z2,RAID-Z3

Коды Рида — Соломона в RAID 6

Исправление ошибок Рида-Соломона в RAID-6

Обзор

Как работает рекавери

Данные испытаний

Случай 1. Потеря `PD` привода.

Случай 2. Потеря одного из дисков с данными: либо `D1`, `D2` либо `D3`.

Случай 3. Потеря `RS` привода.

Случай 4. Потеря `PD` привода и `RS` привода.

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

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

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

Эпилог

Добавить комментарий Отменить ответ

RAID 6 и другие RAID-JBOD,0,01,1,1E,2,3,4,5,6,10,50,60,RAID-Z,RAID-Z2,RAID-Z3

Коды Рида — Соломона в RAID 6

Исправление ошибок Рида-Соломона в RAID-6

Обзор

Как работает рекавери

Данные испытаний

Случай 1. Потеря PD привода.

Случай 2. Потеря одного из дисков с данными: либо D1, D2 либо D3.

Случай 3. Потеря RS привода.

Случай 4. Потеря PD привода и RS привода.

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

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

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

Эпилог

Добавить комментарий Отменить ответ

Случай 1. Потеря `PD` привода.

Случай 2. Потеря одного из дисков с данными: либо `D1`, `D2` либо `D3`.

Случай 3. Потеря `RS` привода.

Случай 4. Потеря `PD` привода и `RS` привода.

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

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