2005/10/31
RAIDの分類
RAIDの分類 （おさらい）（おさらい）RAID Level 0 (Nonredundant) ブロック単位分散，冗長性なし

データ工学特論（２）RAID Level 1 (Mirrored) ブロック単位分散，二重化

網掛け部分は冗長情報の部分を表す

RAID Level 2 (Memory-style ECC) ビット単位分散，Hamming符号

情報基盤センター
天野 浩文

RAID Level 3 (Bit-Interleaved Parity) ビット単位分散，パリティ
RAID Level 4 (Block-Interleaved Parity) ブロック単位，集中パリティ

この講義に関するwebサイト：
http://isabelle.cc.kyushu-u.ac.jp/~amano/data-engineering/

データ工学特論（２）RAID Level 5 (Block-Interleaved Distributed Parity) ブロック単位，分散パリティ

データ工学特論（２）1RAIDの分類についての補足（おさらい）
RAIDの分類についての補足（おさらい）

2

RAID-5のLargeRAID-5のLarge Read（おさらい）
Read（おさらい）z RAID-5の最適ブロック配置– 先頭から順次読み出す場合のディスクのアクセス順序が崩れないようにすると，すべてのディスクが読み出しに貢献できる– これはRAID-0と同じ

z“RAID Level n” を省略して，“RAID n” ということも多い．
z商用RAIDのカタログなどでは，Chen, Lee, Gibson, Kats,Pattersonの分類とはやや異なる表記が用いられることも多い．
カタログ等でよく用いられる表記
RAID 1 ストライピング無し，単一ディスクの二重化

RAID 0+1 ブロック単位分散＋二重化 ＝ RAID Level 0の二重化

0

12

3P0

5

67P1

41011P28915P3121314P416171819

各ディスクを１回ずつ順にアクセスできる
データ工学特論（２）

データ工学特論（２）3

データ工学特論（２）412005/10/31
RAIDの比較（１）
RAIDの比較（１）

RAIDの比較（２）
RAIDの比較（２）z RAID-0 と RAID-1– コスト： RAID-0＜RAID-1 （冗長ディスクの数が多い）

z RAID-2 と RAID-3– コスト： RAID-2＞RAID-3 （冗長ディスク数の差）– データディスク数が同一の場合のスループット性能
書き込み： RAID-0＞RAID-1
読み出し： RAID-0＜RAID-1– データディスク数が同一の場合のスループット性能
読み出し： RAID-2＝RAID-3
書き込み： RAID-2＜RAID-3

RAID Level 0 (Nonredundant) ブロック単位分散，冗長性なし
RAID Level 1 (Mirrored) ブロック単位分散，単なる二重化

RAID Level 2 (Memory-style ECC)
ビット単位分散，Hamming符号

データ

データ
パリティ

コピー
RAID Level 3 (Bit-Interleaved Parity)
ビット単位分散，パリティ

データ工学特論（２）

書き込みの際には，どちらも全ディスクにアクセスする

データ工学特論（２）56

RAIDの比較（３）
RAIDの比較（３）RAID-0,RAID-0, 1,1, 3,3, 55 のスループット性能の総合比較のスループット性能の総合比較

z RAID-3 と RAID-5– コスト： RAID-3＝RAID-5• 同一コスト（＝全ディスク数）で達成できるスループット性能のRAID-0 に対する相対値– スループット性能
小さな読み出し： RAID-3＜RAID-5
大きな読み出し： RAID-3＜RAID-5
小さな書き込み： RAID-3≦RAID-5
大きな書き込み： RAID-3＝RAID-5
RAID Level 3 (Bit-Interleaved Parity)
ビット単位分散，パリティ

RAID Level 5 (Block-Interleaved Distributed Parity)
ブロック単位，分散パリティ
データ工学特論（２）

データ工学特論（２）RAID-0

データパリティ

Small Read

Small Write

Large Read

111

Large Write Storage
Efficiency
11

RAID-1

1

1/2

1/2

1/2

1/2

RAID-3

1/(G－1)

1/G(G-1)/G(G-1)/G(G-1)/G

RAID-51max(1/G,1/4) 1(G-1)/G(G-1)/G

Small: １ブロック内に収まるアクセス
Large: １ストライプ全体に渡るアクセス
G:
パリティグループのサイズ

プラッタが表示されているものはブロック単位，そうでないものはビット単位でストラ
イピング
7

データ工学特論（２）822005/10/31
小さな読み出しのスループット
小さな読み出しのスループット

小さな書き込みのスループット
小さな書き込みのスループット
1

1

RAID- を１とした相対スループット

RAID- を１とした相対スループット

0.9
RAID-1

0.8

0RAID-5

00.7
0.6
0.5

RAID-1
RAID-3
RAID-5

RAID-30.4
0.30.20.1

0.80.7

RAID-1

0.6

RAID-1
RAID-3
RAID-5

RAID-3, 50.5

RAID-5

0.4
0.3
0.2

RAID-30.10002468
10 12 14
パリティグループサイズ

1618020

データ工学特論（２）246810
12 14
16
パリティグループサイズ

1820

データ工学特論（２）9大きな読み出しのスループット
大きな読み出しのスループット

10

大きな書き込みのスループット
大きな書き込みのスループット
1

1

RAID-5

RAID-1

0.9

RAID- を１とした相対スループット

RAID- を１とした相対スループット
00.9

RAID-3

0.8

00.7
0.6

RAID-1
RAID-3
RAID-5

0.5
0.4
0.3
0.2
0.1

0.9
RAID-3, 5

0.8
0.7
0.6

RAID-1RAID-3
RAID-50.5
RAID-1

0.4
0.30.20.100024681012 1416
パリティグループサイズ
データ工学特論（２）

データ工学特論（２）18020

1124681012 1416
パリティグループサイズ
データ工学特論（２）

1820

123

2005/10/31
RAID-3
RAID-3 の相対スループットの相対スループット
1

RAID- を基準とした相対スループット

RAID- を基準とした相対スループット
0

RAID-5
RAID-5 の相対スループットの相対スループット

0.9
0.8
Large Reads &Writes
Small Reads &Writes

0.7
Large Reads & Writes

0.6

00.5
Small Reads & Writes

0.4
0.3
0.2
0.10024

Small & Large Reads1
Small & Large
Reads
Small Writes

Large Writes

0.80.6Large Writes

0.4

Small Writes

0.206 8 10 12 14 16 18 20
パリティグループサイズ
データ工学特論（２）1.20132468
10 12 14
パリティグループサイズ

161820データ工学特論（２）14RAIDの信頼性を左右する要因（１）
RAIDの信頼性を左右する要因（１）

RAIDの信頼性を左右する要因（２）
RAIDの信頼性を左右する要因（２）z MTBF（mean time between failure）とMTTF（mean time tofailure）

z １台のディスクにランダムに発生する障害だけを考える場合– RAID-5 の MTTF (mean time to failure)– どちらも，故障・障害が発生するまでの平均時間のこと．
– MTBFは，障害発生後，修理して使用を再開するような装置・部品に対して用いることが多い．
– MTTFは，障害発生後は修理せず交換してしまうような装置・部品に対して用いることが多い．その意味で，「平均寿命」と考えることもできよう．
z MTBF（MTTF）と障害発生確率λの関係

MTBF ( MTTF ) =1

λ

データ工学特論（２）

データ工学特論（２）15⎛NMTTR ( disk ) × (G − 1) ⎞⎜⎜⎟⎟×
MTTF ( disk )⎝ MTTF ( disk )⎠2
MTTF ( disk )=N × (G − 1) × MTTR ( disk )−1(MTTR: mean time to repair)– N=100, G=16, MTTF(disk)=200,000時間，MTTR(disk)＝1時間とすると，RAID-5 の MTTF ＝約3,000年
z だが，実際には...
データ工学特論（２）1642005/10/31
RAIDの信頼性を左右する要因（３）
RAIDの信頼性を左右する要因（３）

RAIDの信頼性を左右する要因（４）
RAIDの信頼性を左右する要因（４）z システムクラッシュ
停電，操作ミス，ハードウェア障害，ソフトウェア障害– I/O操作が途中で止まる
パリティ等の不整合が生じる⇒RAID の異常ではないが，データには異常が残る

z 訂正不能なビットエラー (uncorrectable bit error)…1014に 1 ビット程度の割合– ディスクの磁性面の摩滅などによるデータ損失– read の際にパリティ異常で露見する

z システムクラッシュ時のパリティ不整合を防ぐ方法– 書き込みのたびに，パリティ回復に必要な情報をログに残す．
– ただし，不揮発性 RAM などのハードウェアサポートがなければ大幅な性能低下は必至

データ工学特論（２）17z 障害ディスクのデータの回復⇒それ以外の全ディスクの読み出しが必要！
再度，訂正不能なビットエラーが起こると，データは回復不能になる⇒100GBの RAID では，0.8%程度のデータは回復不能
z 訂正不能なビットエラーを防ぐには...
読み出しが危なくなってきたら，ハードウェア的に警告を出させる．読めなくなる前にオペレータが対処．

データ工学特論（２）18RAIDの信頼性を左右する要因（５）
RAIDの信頼性を左右する要因（５）MTTDL
MTTDL (Mean(Mean TimeTime toto DataData Loss)
Loss) （１）（１）

z RAID-1 ～ RAID-5 …単一ディスクの障害しか考えていないz RAIDにとり最も深刻な事態

z 複数のディスクが相次いで故障することもある– 地震，電源異常，落雷，etc.

– データが失われること
z データが失われるケース– ２台のディスクに同時に障害が発生する– システムクラッシュ後にディスク障害が起こる– ディスク障害発生後，再構築中に訂正不能なビットエラーが出る
z 典型的なパラメータの例– 同一の製造ラインから出荷されたディスクが同時期に故障する...
z 単一ディスクの障害が発見されてから，再構築が完了する前に次のトラブルが起こったら...
⇒そのデータは失われる

ユーザディスク数
100台（500GB）
ディスクサイズ
5 GBセクタサイズ
512 バイト
ビットエラー率（ビット）1/1014
ビットエラー率（セクタ）
1/(2.4×1010)
全セクタが読める確率（p(disk)） 99.96%
パリティグループサイズ
16 ディスク
データ工学特論（２）

データ工学特論（２）19データ工学特論（２）MTTF(disk) 200,000時間
MTTF(disk2) 20,000時間
MTTR(disk) 1時間
MTTF(sys) 1ヶ月
MTTR(sys) 1時間
2052005/10/31
スペアディスク
スペアディスクMTTDL（２）
MTTDL（２）z RAID-5 （N＝ディスク総数）
MTTDL

10年間のデー
タ損失確率

ディスク障害＋ビットエラー

MTTF (disk ) × MTTF (disk 2)= 285年
N × (G − 1) × MTTR (disk )MTTF ( sys) × MTTF ( disk )= 154 年
N × MTTR ( sys)
MTTF (disk )= 36年
N × (1 − ( p(disk )) G −1 )ソフトウェアRAID（上記の調和平均＝26年）

31.6%

ハードウェアRAID(NVRAM付き)（「システムクラッシュ＋ディスク障害」を除いた調和平均＝32年）

26.8%

ディスクの二重障害
システムクラッシュ＋ディスク障害

データ工学特論（２）z ディスクアレイを構成するディスクが故障した場合に，それの代替となるディスクが内蔵されていることも多い– 例：RAID Level 3 での構成の一例

3.4%

パリティ
ディスク

データディスク

スペアディスク

6.3%
障害発生時

24.4%

内蔵スペアディスクでなく交換用ディスクの場合でも同じ
Exclusive-OR
21

データ工学特論（２）22

ディスクアレイの状態に関する情報
ディスクアレイの状態に関する情報システムクラッシュ後のパリティ再構築
システムクラッシュ後のパリティ再構築

z ディスクアレイが保持する情報– データ– パリティ（あるいはその他の冗長情報）– 状態記述情報(metastate information)例：どのディスクが故障しているのか
故障したディスクのうちどのセクタまで修復済みであるか
どのセクタが修復中であるかz 状態記述情報の保持のしかた– システムクラッシュがあっても正しく保持されている必要がある– セクタあるいはストライピングユニット単位にvalid/invalidを記
録する

z 書き込み中にシステムクラッシュ↓
そのとき書き込もうとしたパリティは不正になる可能性がある．
しかし，どのパリティセクタが不正なのか，ディスクアレイ全体をスキャンする以外に確実に判定する方法がない
z パリティセクタごとに valid/invalid を記録する．
– 書き込み処理前にそのセクタをinvalid としておく．
– ときどき，全セクタをvalid とするか，あるいは，パリティ書き込み処理が完了するたびにそのセクタをvalid と記録する．
– システムクラッシュから回復したら，invalid と記録されているパリティセクタをすべて再構築する．

データ工学特論（２）

データ工学特論（２）

データ工学特論（２）23246

2005/10/31
故障ディスクが出た場合の対処（１）
故障ディスクが出た場合の対処（１）

故障ディスクが出た場合の対処（２）故障ディスクが出た場合の対処（２）z スペアディスクがある場合⇒デマンド再構築（demand reconstruction）

z スペアディスクがない場合⇒パリティスペアリング（parity sparing）– 故障ディスクを含むストライプへのアクセスが発生すると，故障ディスクのデータを再構築してスペアディスクに書き込む．
（残りの部分はバックグラウンドプロセスで再構築）
RAID Level 4 の場合
データ

パリティ

スペア– 故障ディスクを含むストライプへのアクセスが発生すると，対応するパリティをつぶして書き込み，relocated と記録する．
– 故障ディスクが交換されたら relocated マークのついたセクタを書き戻し，パリティを再構築し，relocated マークを消す．
RAID Level 4 の場合
データ(1)アクセス
要求発生

パリティ

(2) 再構築(2) パリティをつぶして書き込む(1)書き込み
要求発生
データ工学特論（２）25

データ工学特論（２）26Orthogonal
Orthogonal RAID
RAIDRAIDRAID Level
Level 55 の書き込み性能の改良（１）の書き込み性能の改良（１）z 数台のディスクが１本のバスにつながる場合，１つのコントローラが故障すると，それにつながるディスクは全滅する．
z Orthogonal RAIDz RAID Level 5 における書き込み…４回のディスクアクセス– 共有されるハードウェアと「直交」する向きにパリティグループを構成する．
コントローラ– Read-Modify-Write(1) データディスクから変更前のデータを読む(2) パリティディスクから変更前のパリティを読む
新パリティ＝旧パリティ ＋ 旧データ ＋ 新データ
(3) 新しいデータを書き込む(4) 新しいパリティを書き込む(1) (3)(2)(4)

コントローラz 改良策– バッファリングとキャッシング
– フローティングパリティ– パリティロギング

コントローラコントローラ

データ工学特論（２）

データ工学特論（２）27

データ工学特論（２）2872005/10/31
RAID
RAID Level
Level 55 の書き込み性能の改良（２）の書き込み性能の改良（２）RAID
RAID Level
Level 55 の書き込み性能の改良（３）の書き込み性能の改良（３）z バッファリング(buffering)…非同期書き込み– 書き込み処理が完了する前にホスト側にacknowledgeする

z フローティングパリティ (floating parity)
トラック
Menon et al. 1993
– Read-modify-write の読み出しが終了してから書き込みが可能になるまでディスクが１回転するのを待たなければならない– 元のブロックではなく，もっとも近い空きブロックに書き込むようにする
ヘッド– 空きブロックが必要⇒領域の効率の問題
空きブロックの位置の情報の管理も必要
ディスクコントローラの中にハードウェア的に実装する
z フローティングデータ(floating data)– パリティだけでなくデータもフロートさせる– データが不連続になりやすく，領域はさらに非効率的– バッファが不揮発性メモリでできていなければ，システムクラッシュ時にデータが失われる– 低負荷時のレスポンスタイムは向上する– 同一ストライプへの書き込みをまとめて，フルストライプアクセ
スにすることができれば，スループットも多少は向上
z キャッシング(caching)– 通常のデータ処理では，対象データを読み込んでから新しい値を計算し，書き込むのが普通⇒最初の読み込みのときにRead-Modify-Write用のデータをキャッシュしておく
データ工学特論（２）29

データ工学特論（２）RAID
RAID Level
Level 55 の書き込み性能の改良（４）の書き込み性能の改良（４）パリティデクラスタリング(Parity
パリティデクラスタリング(Parity Declustering)Declustering)z パリティロギング (parity logging)
Stodolsky and Gibson 1993

z ディスクアレイの再構築中でも通常の処理を続けたい
あるいは，サービス再開までの時間を短縮したい
z RAID Level 5 の再構築時の負荷の集中の問題
複数台のRAID を用いる場合，再構築の行われる範囲が集中

z 旧パリティの読み出しと新パリティの書き込みを遅らせる– 新旧パリティの差分（パリティ更新イメージ）のログを不揮発性メモリに記録– 不揮発性メモリが一杯になったら，ディスク上のファイルに転記– ログが一杯になったら，旧パリティとパリティ更新イメージをメモリに読み込み，まとめてパリティを更新する– パリティブロックに対する小さな書き込みをまとめてやや大きな書き込みにできるので，効率が向上する

データ工学特論（２）

データ工学特論（２）3130

z パリティデクラスタリング Gibson et al. 1990

データ工学特論（２）3282005/10/31
分散スペアリング
分散スペアリング (Distributed(Distributed Sparing)
Sparing)

パリティスペアリング
パリティスペアリング (Parity(Parity Sparing)
Sparing)z 正常運転時には遊んでいるスペアディスクを活用する
Menon et al. 1991

z スペアディスクもパリティに使用する
Chandy and Reddy 1993

パリティディスク

パリティディスク

スペアディスク

スペアディスク

パリティブロック

パリティブロックスペアブロックz 半分のサイズのディスクアレイ２つとして扱ったり，２つのパリティブロックのうちシーク時間の短いほうを動的に選んで使う

z 正常運転時の性能が上がる
z ディスクに故障がおきたときには，スペアブロックに再構築
データ工学特論（２）

データ工学特論（２）3334仮想ストライピング
仮想ストライピング (Kitsuregwa(Kitsuregwa etet al.
al. 1993)（１）
1993)（１）

仮想ストライピング（２）仮想ストライピング（２）z RAID-5 の小さな書き込みが遅くなる原因
Read-Modify-Writeのために４回のディスクアクセスが必要

z n ドライブに対する n 個の小さな書き込みをまとめて，新しいストライプを作る⇒フルストライプ書き込みになる（速い）– i 番目のディスクのブロックは一番近い空きブロックに書く．

z 論理データブロックを物理データブロックに固定しない
どのブロックがどこにあるかは別にテーブルで管理
仮想ストライプ

仮 想 ス トラ イ プ 番 号

D isk 0D isk 1…

D isk n - 1

汚染ブ ロック数

0

1, 1

3, 6…

1, 240125, 3

1, 48…

50, 1922

1, 37

2, 11…

35, 4

1:

：

：

：

：：

M*, **, **, **, *

0

シリンダ

データ工学特論（２）

データ工学特論（２）ブロック

空きストライプ
35– 場所が変わったブロックは「汚染ブロック」とする．
– 後でガーベジコレクションが必要．
z n データブロックの書き込み– RAID-5： n ×４回アクセス– 仮想ストライピング： n ＋１回アクセス

データ工学特論（２）3692005/10/31
仮想ストライピング（３）仮想ストライピング（３）まとめまとめz 物理状態テーブル…各ブロックの状態を登録– FREE：使われていない– ACTIVE：正しいデータが入っている– DIRTY：更新されたので古い値になっている

z RAIDの比較– RAID-5は，小さな書き込みにやや難点があるものの，他のレベルのRAIDに比べて，バランスの取れた理論性能を持つ．
z RAIDの信頼性を左右する要因– MTBFとMTTF• 単純なMTTFの計算では，RAIDは非常に長い寿命を持つはずだが...
– MTTDLz RAID-5の性能を向上させるためのさまざまなアイディアz ガーベジコレクション– ACTIVEブロック数最小のストライプ（犠牲者ストライプ）のACTIVEブロックをよそのストライプのDIRTYブロックと交換，パリティを更新– 犠牲者ストライプのブロックをすべて FREE に
犠牲者ストライプ

ACTIVEDIRTY
PARITY

データ工学特論（２）

データ工学特論（２）37

データ工学特論（２）3810