この記事では、RAID-6に基づく独自のエラー修正システムの簡単な例を示します。特に、1つまたは2つのドライブの障害に耐えられるように、システムの冗長性を提供する必要がある状況を考慮してください。
ボーナスとして、RAID-6はRAID-5の改良版であるため、RAID-5でエラー修正がどのように機能するかに関する情報。
概要概要
データを含む3つのディスクがあるとします。それらをD1、D2、D3と呼びましょう。RAID-6システムを使用するには、PDとRSの2つの追加ドライブが必要です。数分で、PDとRSの略について説明します。つまり、D1、D2、D3、PD、RSの合計5つのドライブです。
だから状況：
- D1、D2、およびD3には任意のデータが含まれています。猫の写真としましょう。
- 特別なディスクPD（パリティドライブ、ドキュメントではPの場合もあります）には、D1、D2、およびD3から自動的に生成されたzipデータが含まれています。
- PDと同じデータ用の2番目の特別なディスクRS（Reed-Solomonコード、Qと呼ばれることもあります）。
このようなアレイで基本的な操作を実行する方法を見てみましょう。
リカバリの仕組み
PDとRSを正しく計算すれば、最大2つのディスクの障害に苦労せずに耐えることができます。回復手順は、どの特定のディスクに障害が発生したかによって異なります。通常、7つの状況が考慮されます。以下では、簡単なものから複雑なものまで並べ替えられています。
- PDの喪失（1つのディスクのみ）。
非常に単純なケースです。PDには自動生成されたデータのみが含まれているため、D1、D2、およびD3ドライブの元のデータを使用して復元できます。
- : D1, D2 D3 ( ).
, , , RAID-5: PD . 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）を確認します。
実際のRAID-6アレイは、実際にはドライブ全体をPDまたはRSに割り当てるわけではないことに注意してください。このデータはすべてのドライブに分散されます。コントローラーが異なれば、使用する方法も異なります。左非同期または右同期、RAIDデータ、待ち時間などに関連してシフトが発生する可能性があります。これが発生する理由と実際のストライプがどのように見えるかについては説明しません。 RAID-6。特にリード-ソロモンコードに焦点を当てましょう。
テストデータ
「ユーザーデータ」を定義しましょう。簡単にするために、各「ディスク」のサイズを5バイトに設定しましょう。
| ディスク | ASCIIデータ | HEXのデータ |
|---|---|---|
D1
|
最初 | 0x66、0x69、0x72、0x73、0x74 |
D2
|
2番目 | 0x73、0x65、0x63、0x6e、0x64 |
D3
|
第3 | 0x74、0x68、0x69、0x72、0x64 |
次に、前述のシナリオを詳しく見てみましょう。
状況1.PDディスクの紛失
PDを生成するには、ユーザーデータディスクのみが必要です。私たちの場合、これらはD1、D2、およびD3です。PDディスクは、すべてのユーザーデータのXORを実行するだけです。
PDのオフセット0を生成するには、オフセット0からのすべてのバイトをすべてのディスクに圧縮する必要があります。オフセット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からPDを復元するのは簡単です。
状況2.データストアの1つが失われた：D1、D2、またはD3
ちなみに、これがRAID-5エラー修正の仕組みです。1つのユーザーデータディスクのみに障害が発生した場合、PDディスクを使用して、欠落しているユーザーデータを再計算できます。
D2が失われたとしましょう。D1、D3、PD、RSは在庫がありました。この場合、RSには触れないでください。ドライブD1、D3、およびPDのみが必要です。欠落しているデータを計算するには、前の状況と同様にXOR関数を再度使用できます。
オフセット0からユーザーデータを回復するには、残っているユーザーデータディスク（D1およびD3）のゼロオフセットからのバイトをゼロオフセットPDからのバイトでxorimします。オフセット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ディスクの紛失
これで、Reed-SolomonおよびGaloisフィールドコードが機能します。しかし、心配しないでください。それらを使用するために数学者である必要はありません。
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)
テーブルが宣言された後、いくつかの操作を定義する必要があります。現在、 有限フィールド（Galoisフィールド）で作業しているため、基本的な算術演算の実装は異なります（意味は多少似ていますが）。基本的な操作（加算、乗算、除算）を再定義する必要があります。
# 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 |
現時点では、PDとRSが正しく生成されているため、D1、D2、およびD3ドライブは完全なRAID-6エラー修正アルゴリズムによって保護されています。
現在のRSデータは、その特定の順序でD1、D2、およびD3に対してのみ有効であることを覚えておくことが重要です 。したがって、ドライブ上の実際のデータが同じであっても、D1、D2、およびD3のRSはD3、D2、およびD1とは 異なります。RAID-6データを回復するときは、アレイ内の正しいディスクシーケンスを知る必要があるため、これを覚えておくことが重要です。幸い、アレイが小さい場合は、RSデータを強制的に生成して、正しいディスクシーケンスを見つけることができます。
状況4.PDとRSの喪失
これも単純な状況です。最初にシナリオ＃1を実行し、次にシナリオ＃3を実行します。
繰り返しますが、この場合、ユーザーデータは影響を受けません。それらを使用してPDを作成できます。次に、RSを作成します。どちらの場合も、ポイント1と3ですでに説明されています。
状況5.RSと1つのデータディスクの喪失
そしてここでは難しいことではありません。1つのデータディスクが失われましたが、PDが残っているため、シナリオ＃2を実行して、失われたデータディスクを回復できます。次に、シナリオ＃3のように、すべてのデータディスクをRSの再生成に使用します。これで、ディスクの完全なセットが回復しました。
状況6.PDと1つのデータディスクの喪失
一般的なアプローチは、最初にRSと組み合わせて他のディスクを使用して欠落しているデータディスクを回復し、次にすべてのデータディスクが回復した後、PDの再生成に進みます（シナリオ＃2）。
この状況では、いくつかの計算を行う必要があります。 PDとともにデータディスクD2を失ったとします。したがって、D1、D3、RSの在庫があります。
RSディスクのおかげで、次のようにD1、D3、RSを組み合わせてD2を復元できます。
# 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)
まず、欠落しているデータディスク（この場合はD2）の代わりに、RS値とともに、すべての有効なディスクのすべてのバイトの
partialRS
戻り値
gf_mul
を加算（gf_add）して 値を生成する必要があります 。
次に、この値
partialRS
を使用して、 1をデッドディスクインデックス（
gf_drive(2)
）で除算し、その結果に
partialRS
。を掛けて、D2データを再生成 し ます。引数
gf_drive(2)
は、デッドディスクのインデックスを示します。 D1が失敗した場合は、ここで使用します
gf_drive(1)
。
D2を再生成した後、すべてのデータディスクを復元します。この場合、シナリオ＃1のようにPDの再生成を実行します。上記のコードでは、これはすべてのディスクから（gf_add）データを追加することによって実行されます。覚えている場合
gf_add
は、Galoisフィールドに単純なXOR操作があるため、すべてのデータディスクからバイトを手動でxorする代わりに、操作を使用できます
gf_add
。
状況7.2つのデータコレクターの喪失
これは最も興味深く、最も難しいシナリオです。ディスク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アレイは複数のドライブにまたがっています。したがって、複数のデータディスク、たとえば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.
この場合、データストレージデバイス（D1）は1つしかないため、
partialRS
単純
gf_mul(gf_drive(1), image1[i])
です。
次に、
g
1をデッドディスクインデックス（D2とD3）の合計で割ってパラメータを生成する必要があります 。
次はパラメータ
xoredPD
です;これは、PDの内容を
partialPD
以前に計算されたパラメーターに追加することによって計算されます 。次のパラメータは 、RSコンテンツに
xoredRS
追加することにより、同様の方法で計算され
partialRS
ます。
トリッキーな部分です。最初に壊れたディスク、つまりD2ディスクからデータを計算できます 。これを行うには、2番目に壊れたディスクのインデックスを乗算する必要があります （D3）をパラメーター
xoredPD
に追加し、パラメーターを結果に追加します
xoredRS
。次に、結果にパラメータを掛けた後
g
、D2ディスクの内容を取得します 。
D2のデータを回復したばかりなので、このケースはシナリオ＃2と同じです。1つのデータディスク（D3）が失われます。D3ドライブを作成するには、すべてのライブデータドライブ（D1およびD2）をPDに追加する必要があります。
完了しました。ディスク一式を返却しました。
エピローグ
Reed-Solomonコードでエラーを修正するのに、プログラミングや処理能力がそれほど必要ないことを示すために、Pythonを選択しました。すべてが非常に高速で、実装は非常にコンパクトになります。もちろん、より効率的な実装は、並列処理を念頭に置いて作成する必要があります。各バイトは他のバイトとは独立して計算されるため、並列化は難しくありません。
説明したデータ回復方法は、個別の物理ディスクで使用する必要がないことに注意してください。 「ディスク」は、信頼性の低いチャネルを介してデータを送信するプロセスにおける「バッファ」と考えることができ、このようなエラー修正は引き続き有効です。ハミングコードよりも集中的な計算が必要ですが、2つのフォールドストリームが発生する可能性があります。これは強力な復元機能です。
もちろん、RAID-6は新しい発明とはほど遠いものであり、Reed-Solomonコードはさらに古いものです。それらはVoyager2ミッションで使用されまし たが、これはかなりクールです。
Reed-Solomonコードのより現代的な代替案の中には、 ターボコードがあります -私もそれらを掘り下げる機会があることを願っています。