数理解析研究所講究録
第 1604 巻 2008 年 19-30

19

完全二部グラフを用いた RAID6 での Data と Parity の配置
東邦大学理学部情報科学科
足立智子, 杉浦智吉

Toho University, Department of Information Sciences
Tomoko Adachi, Tomoyoshi Sugiura

1. はじめに
RAID 6 とは, 複数のディスクを組み合わせた RAID システムにおいて, 二重にパリティを生成し, ディスク故障を二個まで許容するシステムである. 一方,グラフ理論においては, マッ

チングや 1-因子分解に関して多くの研究がなされている. 本稿では,
RAID\^o での二個のディスク故障を許容するモテルについて論じる.

グラフの特性を用いたディスクでのブロックは, グラフの一組の辺 $(u, v)$ に対応し, タグ , V が割り当てられタグが を含んでいるすべてのブロックにおいて,ビット的な排他的論理和から得られた
$(u$

る.

$\}$

$v$

パリティは, 頂点$v$に対応するディスクでのブロックに格納される. パリティブロックは,己/レープ $(v, v)$ によって表され,自タグ $\{v, v\}$ が割り当てられる.

2. ディスク故障から復旧する仕組み
アレイのディスクが一個故障した場合に, この故障したディスクのデータブロック, バリティブロックを, 一連のステップを繰り返すことにより復旧を行う.
故障したディスクの中の復旧されていないブロック ーこのブロックはタグ $\{u, v\}$ を持っうち$u$を含むタグを持つすべてのブロックが故障していない場合,

は,残ってぃるブロックのまたは, 前の一連のステップで復旧が終わっている場合に, 一般性を失わずに, この一連のステップにより復旧できる.

この一連のステップの中では, 辺 $(u, v)$ がグラフ において頂点 と結合する唯一の辺である場合も起こりうる この場合, 故障したディスクの中でに対応するブロックは, 現在行
われているステップの中で, 復旧されないままである. 現在行われているステップが 1 番目で
$G$

$u$

$u$

あるなら, 辺 $(u, v)$ は故障したディスクの中のブロック
1 に結合するブロックーに対応する唯一の辺である.

を持っブロックを復旧した後, 同様にして,を含むタグ $\{v, w\}$ を持っブロックを復旧することができる. っまり, 残っているプロソクのうちを含むタグを持つすべてのブロックが, 故障していない場合, または,前の一連のステップで復旧が終わっている場合,
タグ $\{u, v\}$

$v$

$v$

故障したディスクでのブロックに対応する高々二本の辺は,と結合できる.
同様にして, この繰り返し $arrow f$ っているすべてのデータとタグがを含んでいるパリティ
$v$

$w$

ブロックは完全または前の繰り返しで復旧一により,ックだけを復旧することができる.
このようにして,$w$

を含むタグを持っているデータブロ

故障したディスク上の連続したデータブロックは, 辺が閉路とならないな

ら復旧することができる.

20

3.

個のディスクでのデータとパリティの配置$1V-1$$2N$個の頂点を持っ完全二部グラフを用いて, N-l 個のディスクでのディスク故障を許容する

アレイにおいて,どのようにデータとパリティの配置をモデル化すればよいのかを論じる.

この配置のモデル化には近似 1-因子分解を利用する. ここで, は, 素数 または $2P-1$ である.
が素数 である場合にっいては第 4 節で,が $2P-1$ ( は素数) である場合については第 5 節
$N$

$P$

で,

$N$

$P$

$N$

$P$

データとパリティの配置のモデル化を示す.

本節では,ディスクアレイのモデル化に関してその考え方の基幹となる近似 1-因子分解に関する定理を示す
定理 3.1$P$を素数とする,

えたグラフを$Q_{p.p}$個の頂点を持つ完全二部グラフの各頂点に自己ループを付け加とする. このとき.
は,個の 1-因子に分解でき, 任意の二つの
$2P$

$P$

$Q_{p.p}$1-因子の和集合の辺がハミルトン閉路を形成するように 1-因子分解できる.
[証明]$(V, E)$,, ...,とする.
の各辺 $(u, v)$ に, $u+v$ (mod P) とラベル付けする. 次の (a), (b) を示せば定理が証明できる.
$Q_{p.p}=$$v_{1}=(0,$$V=V_{1}\cup V_{2},$$1$$P-1\}$,$V_{2}=\{P, P+1, ..., 2P-1\}$$Q_{p,\mathfrak{p}}$(a) 共通のラベルの辺との頂点を持っグラフはの 1-因子である. この命題を示すために, まず, 共通のラベルを持っ $P$ 本の独立した辺が存在することを指摘する.
これは, 共通のラベルを持っ 2 本の辺は隣接しないことからわかる. もし, 隣接する 2本の辺 $(u, v)$ と $(v, w)$ が共通のラベル を持つと仮定すると,$Q_{p,p}$$Q_{p,p}$$e$$e\equiv u+v$ (mod $P$)

$ib1$ っ$u+V\equiv$$v+w(/rodP)$. . $u\equiv w$$\cdot$となる. 頂点

$u$

と

$w$

$($

加 $dP)$に隣接しているので, 同じ部分集合に属する. した
これは仮定に矛盾している. さて, もしラベルを持っ辺がは, 共に頂点

がって $u=w$ となるが,$v$$e_{/}$

本より少ないならば,より多くなる. これは,$P$のとき, ラベル$e\equiv v+w$ (nod $P$)$\theta_{1}\neq e_{2}$$0_{\mu p}$,となるラベルを持つ辺が 本本の辺と $P$ 個のラベルがあることよりわかる. こ$0\leqq e_{1},$には$P^{\sim^{J}}$$e_{\sim^{J}}\leqq P-1$

$P$

$e_{2}$を持っ 2 本の辺は隣接しなければならない. これは矛盾している. したがって, 共通のラベルを持っ $P$ 本の独立した辺が存在する. この事実より, 共通のラ$e_{2}$

ベルを持つ辺集合によって誘導された辺誘導部分グラフは$Q_{p,p}$の 1-因子であることがわ

かる.
(b)

任意の二つの 1-因子の和集合の辺がハミルトン閉路を形成する. この命題を背理法で証明する. ラベル,を持つ二つの 1-因子の辺を交互に進むことにより閉路$e_{2}$$e_{/}$が形成できると仮定する. 一般性を失わずに, 辺,を持ち, $(V_{Z}V)_{J}(V_{p}V.)_{J}$色はラベルりを持つと仮定できる. このときは偶数であることに注意して, $t=2k_{J}k\langle P$ とおくと,$e_{1}\equiv(v_{l}+v)$(mod $P$),mod$V_{l\prime}V_{J}V_{p}\ldots V_{\ell,J}V_{l}(t<2\partial$$’(V_{I- 1r}V_{\ell})$はラベル$(V_{l}, V_{I}),$$(v_{p}\backslash V\supset$$V_{1})$$e_{i}$$\tau$$($$e_{l}\equiv(v_{J}+v)$となるので,$e_{\sim^{J}}\equiv(V_{\underline{?}}+V)$(mod ),$P$$e_{J}\equiv(V_{\iota-/}+V_{t})$$P$$P)_{J}$mod$($$e_{\sim^{\eta}}\equiv(v_{4}+v_{\overline{o}})$が容易にわかる. ゆえに $k(e_{l}-e_{2})\equiv 0$ (modP).
なので, これは矛盾する. 口$t(e_{J}-e_{2})/2\equiv 0(mdP)$と左は互いに素であり,$e_{l},$$e_{\underline{J}}$ぐ$P)_{J}$$e_{\text{ノ},-}\equiv(v_{t}+V_{l})(mdP)$$P)_{y}$

$P$

mod

$($

21

4.

$P-1$
$N$

個のディスクでのデータとパリティの配置

が素数

$P$

である場合に,$2N(=2P)$ 個の頂点の完全二部グラフを用い,

N-l $(=P-1)$ 個のディスクにおけるデータとパリティの配置のモデル化を示す
ディスクアレイのモデル化は, 素数 の値を固定して図示しても 般性を失わないので, 本
節の前半では, $P=5$ に固定した例や図を用いて, 一般の素数 の場合のディスクアレイの構成
$-$

$P$

$P$

法を説明する. 本節の後半では, このディスクアレイで二個のディスクが故障した際の復旧の手順を説明する.
. の各頂点に自己/L/–プを加えたグラフ
完全二部グラフ, を考える.
このグラフ
は,$2N$ 個の頂点と $N^{2}+2N$ 本の辺 (うち $2N$
本は自己ルーフりを持っ. グラフの本の自己ループ$K_{\backslash 1\backslash }$$Q_{N^{l},\backslash }$$Q_{\}.N}$$21\backslash T$$Q_{\aleph},,$$N$をパリティブロックに対応させ, 自己ループ以外の 本の辺をデータブロックに対応させる.
グラフに対応させて 2個のデータブロック $\{u, v\}(N\leqq u\leqq 2N-1,0\leqq v\leqq N-1)$ を 個のディ
スク Disk , Disk 1, Disk2,, Diskに配置する. このデータブロック o) 配置には, $2N$
個のパリティブロック $\{\{0,0\}, \{1,1\}, \{2,2\}, \cdots, \{2N-1,2N-1\}\}$ は含まれていない. N-l 個のディスクに配置するため, ディスクの個数を 1 個減らす必要があるが, その方法については後述す$N^{2}$$N^{2}$$Q_{\backslash ,\backslash }$

$N$

$0$

る.

また,

$\cdots$$\beta_{1}^{T}-1$

パリティブロックを配置する領域を作るためのデータブロックの取り除き方につぃても後述する.
素数 $P=5$ の場合, 完全二部グラフの各頂点に自己ループを加えたグラフ
は, 10 個の頂点と 35 本の辺 (うち 10 本は自己,’ –プ) を持っ. このグラフ Q5, 5 の自己ループを除く 25$K_{\overline{\cap},D}-$$Q_{\overline{\mathfrak{o}},s}r$$\triangleright$

本の辺をデータブロック $\{u, V\}$ $(5\leqq u\leqq 9,0\leqq v\leqq 4)$ に対応させて, 5 個のディスク DiskO, Disk
1, Disk2, Disk3, Disk4 に配置する. このデータブロックの配置には損失したデータを復旧する際に用いる 10 個のパリティブロックは含まれていない.
ここで,データブロックが配置されるディスクの定め方を説明する.

ータブロックの配置のディスク番号を

$M$

グラフ

q, 、におけるデ$(M=0, 1, 2, 3, \cdots, N-1)$ とすると, データブロッ

ク $\{u, v\}$ が配置されるディスクは,(mod N)$u+v\equiv M$を満たすディスクである. 例示している図は$!\backslash ^{\uparrow=}P=5$の場合であり, データブロック {9, 4} は,

9 $+4\equiv 3(mod 5)$であるため, Disk3 に配置される.
番号が定まる.

他のデータブロックについても同様に配置されるディスク

図 4. 2 グラフ

今, グラフ$Q_{5},5$に対応するデータブロックの配置に対応するディスアレイでは,個のデータブロックが個のディスクに配置されている. 配置したいディスクは N-l 個であるため, –.っのディスク Disk を, そのディスクに配置されている 個のデータブロックごと取り除く. グラフ
から DiskO を取り除
$Q_{!\backslash ,t^{I}}$$N^{\theta_{-}}$

$N$

$0$

$N$

$Q_{\backslash ,N}$

22

くことは,

グラフの頂点

$0$

と頂点

$N$

を,

これらの頂点に接続していることである. DiskO に配置されたデータブロソク $(N, 0]$ は, 頂点 $0,$

取り除かれているので,実際は $2N-2$ 本の辺を取り除く.
を取り除く. グラフ q, 、に対応する

$N$

さらに,

$2\beta_{\dot{\sqrt{}}}-1$本の辺ごと取り除くに接続しているが, すでに個のデータブロック個のデータブロソクの配置から,$h+(2N-2)+(N-1)=4^{\backslash }t-3$個のデータブロックを取り除くことにより, パリティブロックを配置するブロック (領域) が確保される. このようにして, N-l 個のディスクの $(N- 1)^{2}=N^{2}+2N+1$ 個の領域に, $N^{2}-(4N-3)=N^{2}-4h+3$ 個のデータブロックと) $2N-2$ 個のパリティブロック $\{\{1,1\},$ $\{2,2\}$ ,$[v+N,$ $v\}(1\leqq v\leqq 1N-1)$(3, 3},, ( $N-1,$ $N-1\},$( $N+1,$ $N+1\},$$N-1$$V^{2}$

が配置できる.
この図から DiskO に対応する 5 個のデータブ$\{N+2, N+2\}$ ,$\{h’+3, \beta_{Y}^{v}+3\},$

例示している図は $N=P=5$ の場合であるので,$\cdots$,

ロック $\{\{5,0\}, (6,4\}, (7,3\}, (8,2\}, \{9,1\}\}$ を取り除くことになる.

$(21\backslash |-1,2N-1\}\}$

グラフ
から Disk のデータブロックに対応する辺 (青破線で表示) を取り除いたグラフと, 対応するデータブロックの配置を下図に示す

グラフ$Q_{\overline{\gamma}.\overline{\backslash }}$$Q_{\overline{\circ}.5}$$0$から, Di $skO$ に配置されたデータブロックに対応する 5 本の辺は取り除かれていと頂点 5 に接続している辺 (赤破線) を取り除くと, 図 4. 5 の実線のグラフになる. 頂と頂点 5 に接続している辺は 9 本あるが, 辺 5, に対応したデータブロックは DiskO に配置され, すでに取り除かれているので, 赤破線の辺は 8 本になる. 図 4. 4 には DiskO に対応す
る頂点 5 が存在しているので, データブロック $(\{5,1\},$ $\{5,2\},$ $\{5,3), \{5,4\}\}$ を取り除くと, 図
4. 6 になる. さらに, 図 4. 6 から, 同様にして, 頂点 に接続する辺に対応するデータブロッ
る. 頂点

点

$0$

$0$

$\{$

$0\}$

$0$

ク $\{\{6,0\}, \{7, 0\}, \{8, 0\}, (9, 0\}\}$ を取り除くと,図 4. 5

図 4. 7 になる.

23

図 4. 6

頂点 5 に接続する辺に対応するデータを除いた配置

図 4. 7頂点に接続する辺に対応するデータを除いた配置$0$

上図の配置において, データを取り除かれたブロックは, バツ印と無印がある. この違いについて説明する. 本節のディスクアレイでは, 最初に, $N^{2}(=5^{l})$ 個のブロックにデータを配置しているが, 求めるディスクアレイは, $(N- 1)^{}$ $(=4^{2})$ 個のブロックにデータとパリテ
ィを配置することである. そこで, データだけでなくブロックごと取り除く場合にはバツ印を記し, データを取り除いたブロックに後でパリティを配置する場合には無印で表す
さらに, 図 4. 7 から, 4 個のデータブロック $(v+5,$ $v\}(1\leqq v\leqq 4)$ , すなわち, $\{\{6,4\}$ , {7, 3},
ここで,{8, 2}, {9, 1} を取り除くと,図 4. 9 になる. このデータブロックの配置に対応するグラフは,$\}$

図 4. 8 であり,取り除かれたデータブロックに対応する辺は緑破線で示している.
$rtJ*\cdots\vee A\sim k$.

く2

嬢 $*-arrow 8$ $$lY*j...\cdot$$\^{r}$$\cdot$$t\underline{l\}}$..

.

$**\iota$$(_{i^{*}\wedge}i^{*}’\iota\}$

図 4. 8 辺 $\{v+5,$ $v)$ (緑破線) を除いたグラフ
グラフ

図 4. 9 データ $\{v+5, v\}$ を除いた配置

個のデータブロックの配置から, $5+8+4=17$ 個のデータブロッ
クを取り除くことにより, パリティブロックを配置するブロック (領域) が確保された. 4 個のディスクの $4^{2}=16$ 個の領域に, 8 個のデータブロック $\{(6,2\},$ {6, 3}, {7, 1}, {7, 4}, (8, 1),{8, 4}, {9, 2] , (9, 3}} と, 8 個のパリティブロック $\{\{1,1\},$ $\{2,2),$ $\{3,3\},$ $\{4,4\},$ $\{6,6\},$,{8, 8}, \’i9, 9} を配置すると, 図 4. 11 のディスクアレイになる. パリティは青地で表示している. 対応するグラフは図 4. 10 である.
$Q_{5,\gamma}$
「

に対応する

$5^{\prime p}=25$$\cdot$$\{7,7\}$$\}$

パリティブロックが配置されるディスクの定め方を説明する. グラフ . におけるデータブロックの配置のディスク番号を $(M=0, 1, 2, \cdots, N-1)$ とすると, パリティブロッ
ここで,$Q_{N}$$a^{\ovalbox{\tt\small REJECT}}|$$M$

ク $\{w, w\}$ が配置されるディスクは,$w+w\equiv M$(mod N)を満たすディスクである. 例示しているは $N=P=5$ の場合であり, パリティブロック {9, 9} は,
9 $+9\equiv 3(mod 5)$24であるため, Disk3 に配置される. 他のパリティブロックについても同様に配置されるディス
ク番号が定まる.

$cdot\cdot....t_{m^{}^{\vee^{\backslash .\cdot...x_{\backslash }^{{}^{t}t}}}})..\cdot\cdot.\cdot\cdot 1^{\cdot},\cdot:\}\backslash ..\grave{k}_{\backslash I}^{\prime’}.\cdot.\backslash .*\backslash ^{i^{-\alpha_{-}}}\frac{\ddot{1}}{\sim\sim}ft_{\frac{=*}{\backslash v\sim f}}’i.\cdot\cdot\backslash \nwarrow\vee^{q’.\dot{a}}\searrow_{*}.\alpha\tau_{\grave{}^{\backslash }}\bigvee_{b}w_{\ddot{\dot{1}}_{\backslash }’}.\nearrow\backslash \cdot\cdot..e_{\backslash }r^{v_{\Lambda}}\cdot\cdot\cdot w\}’.\cdot$$\searrow/\cdot$$\ltimes$:$:\ldots 8_{i:^{\wedge}}^{\tau_{j}}\sim\wedge..\cdot\cdot\backslash \searrow^{=}r...\sim\vee\sim’\wedge i^{\sim\sim}\backslash i\}^{}.i1$$\nearrow.V_{v}’\sqrt{}^{\backslash _{\alpha_{4}}.a_{h}}b$$_{4\gamma}\tilde{\grave{q}_{i^{\kappa^{A}}}^{\prime-}u}\cdot\cdot’.\cdot\cdot\cdot\cdot\cdot\cdot=$$\bigwedge_{\tau_{\vee^{\backslash }\backslash }}..\backslash \backslash \backslash ^{t}4^{\backslash }|\sim-.\cdot.$.

図 4.10 Q 晒から派生したグラフ

このようにして,

図 4.11 Q 漏からのディスクアレイが素数 である場合について, 完全二部グラフ取、の各頂点に自己ループを加えたグラフ . 、からある条件で辺 (データブロック) を取り除いていくことにより,
N-l $(=P-1)$ 個のディスク, すなわち個のブロックに, データとパリティを配置することができる.
次に, このディスクアレイにおいて, ディスクが二個故障した際での復旧の仕組みを説明す
る. Diskl, 2 が故障したとすると, データとパリティの配置は図 4.13 になる. 損失したデー
$N$

$P$

$Q_{N}$$(!\backslash \uparrow-1)^{2}(=(P-1)^{l})$タのグラフは図 4. 12 となる.

6$’\vee$2$\overline{l}$.

$\backslash _{x_{b}}.\backslash \cdot\backslash .$/8$r^{M}.\prime’J^{\cdot}\nearrow’r^{\nearrow}$$i_{\wedge}\sim*$$\hat{\mu}$.

$\mathscr{J}\cdot;_{t_{c_{4}}}r_{I,\wedge}’$$\backslash _{h}$$\mathscr{J}^{\cdot}$$\theta$$\backslash$$-^{\sim}p$$\mathscr{J}^{J}..\cdot\cdot$$\wedge\neg:_{A}$$\iota$

図 4.12 Diskl (実線), Disk2(破線) のグラフ

図 4.13 Diskl,2 故障時のアレイ損失したデータ $\{(3,3\}, \{7,4\}, \{8,8\}, \{9,2\}, \{6,6\}, \{1,1\}, \{8,4\}, \{9,3\}\}$ は, 各頂点の一本の辺しか失われていなければ, 残りデータから復旧可能である. このことより頂点 7 に注目すると {7, 4} しか損失されていないため復旧される. (7, 4} が復旧されたことにより頂点 4 から損

8} の一本になるため {4, 8} が復旧可能になり, {4, 8} が復旧される. {4, 8}が復旧されたことにより頂点 8 の損失された辺が {8, 8) だけになり, (8, 8} が復旧される. 同様に頂点 2 に注目すると {2, 9} が復旧され, {2, 9} が復旧されたことにより {9, 3} が復旧可能になり (9, 3} が復旧される. そして {9, 3} が復旧されたことにより {3, 3} が復旧される. {6,6 , (1, 1} は Disk3, Disk4 の残っているデータブロックから復旧可能である. このステップを失された辺が {4,$\rangle$$\}$

繰り返すことにより, すべての辺が復旧される. よって, このディスクアレイは, ディスクニ
個の故障を許容する.

25

5.

$2P-2$

個のディスクでのデータとパリティの配置

本節では,

$N$

が $2P-1$ ($P$は素数) である場合について取り扱う. $2N(=2P)$ 個の頂点を持つ完全二部グラフを用い, $N-1(=2P-2)$ 個のディスクによるデータとパリティの配置のモデル化を説明する.

完全二部グラフ. の各頂点に自己ループを加えたグラフ . を考える. 素数 $P=5$ の場合,$=2P-1=9$ となる. 完全二部グラフ K9,9 の各頂点に自己ノレープを加えたグラフ Q9.9 を考え, 前節$K_{\backslash .a}$$N$

$Q_{\searrow,h^{I}}|$と同様にデータとパリティの配置を行う.
DiskO に対応する 9 個のデータブロック $\{\{9,0\}$ , {10, 8}, {11, 7}, {12, 6), {13, 5}, {14, 4},{15, 3}, {16, 2}, {17, 1} (青破線に対応) を取り除くと, 下図が得られる.
$\}$

図 5. 1

グラフ
頂点

$0$

{9, 8},$Q_{9,9}$から, DiskO に配置されたデータブロックに対応する 9 本の辺は取り除かれている.

と頂点 9 に接続してぃる 16 本の辺 $\{(9,1\},$ (9, 2}, {9, 3}, (9, 4), {9, 5}, {9, 6}, (9, 7),
10,
11, , 12, , 13, , 14, , 15, , 16, , 17,を取り除き, さ$($$0\})$らに, 辺 $(v+9,$

$\{$

$0\}$

$0\}$

$\{$

$v\}(1\leqq v\leqq 8)$

,

$\{$

$0\}$

$0\}$

$\{$

$0\}$

$\{$

$0\}$

$\{$

$0\}\}$

すなわち $\{\{10,1\}, \{11, 2\}, \{12, 3\}, \{13, 4\}, \text{\’{i}} 14, 5\}$ ,{16, 7}, {7, 8} を取り除くと下図になる.
$\}$

$\{$

\’i15, 6},

26

図 5. 3

頂点 , 9,$0$$(v+9$ ,V$\}$を取り除いた配置

前節同様, 対応するパリティを配置させると下図になる.

図 5. 5グラフ$Q_{q.q}$から派生したグラフ

27

6.

$N$

個のディスクでのデータとパリティの配置

第 3 節から第 5 節では, N-l 個のディスクによるデータとパリティの配置のモデル化を説明した. N-l 個のディスクでの配置では,は素数 または $2P-1$ ( は素数) であった. 本節では,が素数 である場合に, $2N$ 個の頂点の完全二部グラフを用$N(N=P)$ 個のディスクによるデー
$N$

$P$

$P$

$P$

$N$

$A^{a},$

タとパリティの配置のモデル化を説明する.
完全二部グラフの各頂点に自己ループを加えたグラフ儀、を考える. このグラフ
は,$2N$ 個の頂点と $N^{2}+2N$本の辺 (うち $2N$ 本は自己ルーフりを持っ. グラフの $2N$ 本の自己/レープ$K_{N^{\mathfrak{l}},\backslash }$$\Re_{I},N$$Q_{N,h^{1}}$をパリティブロックに対応させ, 自己’m プ以外の をデータブロックに対応させる. グラフに対応させ, 自己ループ以外の 個のデータブロック , v $(N\leqq u\leqq 2h^{T}-1,0\leqq v\leqq N-1)$ を個のディスク DiskO, Diskl, Disk2,
Disk N-l に西 置する.
素数 $P=5$ の場合, 完全二部グラフの各頂点に自己ループを加えたグラフ
は図 6. 1 になる. N-l 個のディスク時には, 頂点 と頂点 , それに対応する辺を取り除いてきたが, 今回は個のディスクであるため の値をそのまま用いることができる.
グラフのデータブロックの配置は図 6. 2 になる. グラフ
データブロックの配置には$N^{2}$$Q_{N,N}$$N^{2}$$\{u$$\cdots$

$)$

$N$

$E$

)

$K_{\overline{\mathfrak{o}}.5}$$Q_{\overline{\mathfrak{o}},5}$

$0$

$N$

$P$

$P$

$Q_{5},5$グラフ$Q_{5,5}$$Q_{5},$の自己/レープ (パリティデータ)$\{\{0,0\},$$\{1,1\},$$\{2,2\},$「$1$$\{3,3\},$$\{4,4\},$$\{5,5\},$$\{6,6\}${7, 7}, {8, 8}, {9, 9} は含まれていない.
ここで, データブロックの配置については, 前節と同様であり,

,

$\}$

$u+v\equiv M$(mod N)を満たすディスクにデータを配置する.

図 6. 1

グラフ$Q_{5,\overline{\circ}}$

図 6. 2 グラフ $Q_{5}$に対応するデータブロックの配置「).

第 3 節から第 5 節での $N-1$ 個のディスク時では 頂点

$0$

と頂点

$P$

に対応する辺を取り除くことによりパリティの配置する領域を確保したが, 本節では 個のディスク時によるものなので,$N$

N-l 個のディスク時の構成法をそのまま用いるわけにはいかない しかし, 次のグラフ理論の知見一グラフ$Q_{p.\mathfrak{p}}$の任意の二つの 1-因子の組み合わせはハミルトン閉路になる一は, 本節でも同様に用いることとする. この知見を用いることにより, パリティブロックを配置できる領域
が$)$

この 1-因子の組み合わせによるハミルトン閉路を取り除いたブロックによって確保され

る.

グラフ

$Q_{\overline{o}.\overline{o}}$に対応するデータブロックの配置 (図 6. 2) からパリティに対応する二つの 1-因子の組み合わせ (図 6. 3) を取り除く.

28$\overline{\mathfrak{Q}}rightarrow 0$.

ブ$\dot{\}}0$
5 $\neg$$\mathscr{J}^{r}0$$\overline{r_{J}}\bullet\backslash$$f$.

$p_{\supset}\cdots-arrow-\cdot-\cdot 1$

6.

$\iota$ヂ 1$fi$$d^{\wedge}1$$\bullet_{1}\dot{4}|$$/$$;_{j}$$/\mathfrak{l}\backslash /\{$

$t\nearrow$$l^{p\prime^{d}}$$\lambda^{*}$$r_{f}\triangleright-\cdot 2$$\overline{l^{l}}d^{A}$

7$\backslash ,.\prime 2$$j_{i}$

皇$I^{/^{t_{l_{\}}}}}$$’\prime^{1}$.

$8rightarrow Il3$

8$/^{t}\prime 1\backslash _{f^{\bullet}}\backslash |\dagger$.
$q_{l_{\sim}}\sim il$

図 6. 38$e\swarrow$$q_{\iota}^{Y}i$

.

/

1

/

$i_{i}$$w_{f}^{\}}’.3$$\nearrow$$|$$r.\cdot:$$\swarrow$$llt;’\lambda$$L$$|d^{\alpha}\sim’\sim i\iota$

Q5, 3 の二っの 1-因子 (左図・中央図) とその組み合わせによるハミルトン閉路 (右図)1-因子の組み合わせによるハミルトン閉路に対応しているデータブロック{7, 2),{8, 3),(9, 4},$\{\{5,0\}$(6, 1},,{5, 4}, {6, , 7, 1), {8,{9, 3} (図 6. 3 右図) を, グラフ 「に対
(
図
6.
2)
応するデータブロックの配置から取り除くと, ハミルトン閉路を除いたアレイ (図 6. 4)$0)$$2\}\rangle$

$\{$

$\}$

$Q_{5,0}$になる.

図 6. 4

一般に,ハミルトン閉路を除いたアレイ

グラフ賑に対応する 個のデータブロソクの配置から,個のデータブロツクを取り除くことにより, パリティブロックを配置するブロック (領域) が確保される.
個のデ
ィスクの 個の領域に,個のデータブロックと,個のパリティブロックが配置される.
$N^{2}$$2N$$N$$N^{2}-2N$$L\backslash :2$$2N$

ここでは, $N=P=5$ の場合を考えているので, グラフに対応する $5^{2}=25$ 個のデータブロ
ックの配置から, 10 個のデータブロックを取り除くことにより, パリティブロックを配置する
ブロック (領域) が確保された. 5 個のディスクの $5^{L}-25$ 個の領域に,15 個のデータブロック (図$Q_{5,5}$

6. 1. 4) と, 10 個のパリティブロック $\{\{0,0\},$ $\{1,1\},$ $(2,2\},$ $\{3,3),$ $\{4,4\},$ $(5,5\},$ $\{6,6\},$,{8, 8}, {9, 9} を配置すると, 図 6. 5 のディスクアレイになる. バリティブロックは青地で表示$\{7,7\}$

$\}$

している.

パリティブロックが配置されるディスクの定め方を説明する. グラフ . こおける
データブロックの配置のディスク番号をとすると, パリティブロッ
ここで,$Q_{N}$$N|$$M(M=0,1, 2, \cdots, I\backslash \mathfrak{s}-1)$

ク $\{w, w\}$ が配置されるディスクは,$w+w\equiv M$(mod N)を満たすディスクである. 例示している図は $N=P=5$ の場合であり, パリティブロック (9, 9}

は,

29

9 $+9\equiv 3(mod 5)$であるため, Disk3 に配置される.
ク番号が定まる.

図 6. 5$Q_{\dot{\gamma}},$$\urcorner$

他のパリティブロックについても同様に配置されるディスから派生したグラフとそのディスクアレイ

次に,このディスクアレイ (図 6. 5) において, ディスクが二個故障した際の復旧の仕組みを説明する. Disk2, 4 が故障したとすると, データとパリティの配置は図 6.6 になる.
損失したデータに対応するグラフの辺を図 6. 7 に示す

図 6.6 Disk2, 4 の故障
図 6. 7 より,

図 6.7

Disk2(破線), Disk4(実線) のグラフ

損失したデータは頂点から一本辺が失われていなければ復旧可能である.

{5, 2}, {2, 2}.
{3, 3}, {6, 6}.
9,, $\{0,7\}$ , {7, 7}.
{4, 4}, {8, 1}, {1, 1}.
のように順に復旧可能であるため, すべての辺が復旧される. 上で記したデータブロック,$\{$

リティブロックは,

$0\}$

パ

一連のステップにより復旧できるブロックを各行に表示している. この一個のディスクでのデータとパリティの配置

連のステップにより,が素数 である場合に,は, 二個のディスク故障を許容する.
$N$

$P$

$N$

30

7.

結論

ディスクでのブロックは, グラフでのマッチングの辺に対応し, 任意の二個のディスクのブ
ロックの組み合わせはグラフの閉路に対応する. この条件を満たすグラフは, 二個のディスクの故障を許容する. このようなグラフの構成法, すなわち,が素数 または $2P-1$ の場合に,N-l 個のディスクでのアレイの構成法を与え, が素数 の場合に, 個のディスクでのアレイの構成法を与えた. そして, 各グラフが二個のディスクの故障に許容性があるアレイをモデル化する際に, 前述の状態を満たすことを示すことによって, それらの正当性を立証した.
$N$

$N$

$P$

$P$

$N$

参考文献
[1] B. A. Anderson: “Synrnetry Groups of Some Perfect
1-Factorizations of Complete Graphs”.
Discre $te$ Ma thema tics 18 (1977), 227-234.
[2] N. Deo and S. Nanda : $0ne$-Factors and Hamiltonian
Paths in Modeling Data and Parity
Placement in Disk Arrays”.
, 191-199.
[3] 恵羅博土屋守正 : 『グラフ理論』. 産業図書, 1997.
[4] 伊勢雅英 :『伊勢 雅英のストレージ最前線』.
2005.
LRL: http: //enterpri se. watch. impress. co. $jp/cda/storage/2005/05/09/5191$ . html
[5] 小林章彦 :『普及が始まった 「 $RAID6$ 」 とは .
2006.
URL: http: $//www$. atmarkit. co. iP/fsys/keyWOrd/019raid6/019raid6. html
[6] M. Kobayashi: “On Perfect $0ne$ -Factorizationof the Complete Graph”.
and
Combins torics 5 (1989), 351-353.
[7] S. Nanda and N. Deo : “Methods for Placing
Data and Parity to Tolerate Two Disk Failires
in Di sk Arrays Using Complete Bipartite Graphs”. COlVGRESSlS $\Lambda lMR4^{A}/TI\ell M179$ (2006),$W\Lambda^{\gamma}GR\mathcal{E}SSl/SAtMR4A^{j}TI\mathscr{U}176(2005)$$j|$$K_{2p}$$G\tau 3\beta hs$

167-179.

[8] 宇野俊夫 :『ディスクアレイテクロノジ
RAID . エーアイ出版株式会社,$\ovalbox{\tt\small REJECT}$

2000.