(57)【要約】【課題】故障ディスクの復旧に関して最適に配置されたパリティディスクを有するストレージシステムを提供する。【解決手段】ストレージシステムは、情報を格納する複数のデータディスクと、パリティディスクを備える。パリティディスクは、複数のデータディスクのうちの一部を含むディスクグループに対応し、対応するディスクグループに含まれるデータディスクのデータに基づいて生成されたパリティ情報を格納する。また、データディスクのいずれかは、複数のディスクグループに含まれる。【選択図】図１
2015082150.tif 000002
【特許請求の範囲】
【請求項１】
情報を格納する複数のデータディスクと、
前記複数のデータディスクのうちの一部を含むディスクグループに対応し、該対応するディスクグループに含まれる前記データディスクのデータに基づいて生成されたパリティ情報を格納するパリティディスクを備え、
前記データディスクのいずれかは、複数の前記ディスクグループに含まれる
ことを特徴とするストレージシステム。
【請求項２】
前記複数のデータディスクのいずれも、前記ディスクグループのいずれかに含まれる
ことを特徴とする請求項１に記載のストレージシステム。
【請求項３】
前記ディスクグループ間において、該ディスクグループに含まれる前記データディスクの数が等しい
ことを特徴とする請求項１または２に記載のストレージシステム。
【請求項４】
前記複数のパリティディスクは、各パリティグループ内の任意のパリティディスクの対が、前記対応するディスクグループに同じデータディスクを含まないように、複数の該パリティグループに分類され、
前記複数のデータディスクのいずれも、前記パリティグループのそれぞれに含まれる前記パリティディスクに対応する前記ディスクグループのいずれかに含まれる
ことを特徴とする請求項１〜３のうちいずれか１項に記載のストレージシステム。
【請求項５】
前記データディスクのそれぞれはストライプのデータの格納順に昇順で識別番号が対応付けられており、前記パリティディスクのそれぞれに対応する前記ディスクグループに含まれる前記データディスクの識別番号の最小値が、データディスク数をパリティディスク数で割った数だけずれている
ことを特徴とする請求項１〜４のうちいずれか１項に記載のストレージシステム。
【請求項６】
前記ストレージシステムは、さらに、
１以上の前記データディスクが故障した場合、故障した前記データディスクを含む前記ディスクグループに対応する前記パリティディスクを用いて、前記故障したデータディスクのデータを復元する復元部
を備えることを特徴とする請求項１〜５のうちいずれか１項に記載のストレージシステム。
【請求項７】
前記復元部は、すべての前記故障したデータディスクが、選択する何れかのパリティディスクに対応する前記ディスクグループに含まれ、且つ、選択する全てのパリティディスクに対応する前記ディスクグループに１以上の前記故障したデータディスクを含むように、前記故障したデータディスクの数と等しい数のパリティディスクを選択し、選択した前記パリティディスクに基づいて、前記故障したデータディスクのデータを復元する
を備えることを特徴とする請求項６項に記載のストレージシステム。
【請求項８】
前記復元部は、前記すべての故障したデータディスクが、選択する何れかのパリティディスクの前記ディスクグループに含まれ、且つ、選択する全てのパリティディスクに対応する前記ディスクグループに１以上の前記故障したデータディスクを含み、さらに、選択するパリティディスクに対応する前記ディスクグループに含まれる前記データディスクの集合としての和が最小となるように、前記故障したデータディスクの数と等しい数のパリティディスクを選択し、選択した前記パリティディスクに基づいて、前記故障したデータディスクのデータを復元する
ことを特徴とする請求項７に記載のストレージシステム。
【請求項９】
コンピュータに、
情報を格納する複数のデータディスクと、前記複数のデータディスクのうちの一部を含むディスクグループに対応し、該対応するディスクグループに含まれるデータディスクのデータに基づいて生成されたパリティ情報を格納するパリティディスクとを備え、前記データディスクのいずれかは、複数の前記ディスクグループに含まれるストレージシステムにおいて、１以上の前記データディスクが故障した場合、故障した前記データディスクを含むディスクグループに対応するパリティディスクを用いて、前記故障したデータディスクのデータを復元する
処理を実行させることを特徴とするストレージプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ストレージの信頼性向上技術に関する。
【背景技術】
【０００２】
クラウドストレージの分野では、データを複製することによりディスク故障・ブロック故障によるデータロスを回避するレプリケーション技術が広く普及している。近年、データを効率的に符号化して最小限の冗長性を持たせることにより、更なる信頼性、容量効率の向上を実現するｅｒａｓｕｒｅ  ｃｏｄｅの技術が盛んに研究開発されている。
【０００３】
しかし、その代表的な方式であるＲＡＩＤ（Redundant Arrays of Inexpensive Disks）では、冗長化する全てのディスクからパリティを計算する必要がある。そのため分散ストレージにおいてはノード間のデータ転送量が増大し、ネットワークがボトルネック化するという問題が存在ある。
【０００４】
そこで、クラウドストレージにおいて、一部のパリティを全てのディスクではなく一部のディスクのみから計算することによって、単一ディスク復旧時のネットワークデータ転送量を削減する技術がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−４４１８２号公報
【特許文献２】特開２００７−２５７６３０号公報
【特許文献３】特開平７−２００１８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、一部のパリティを一部のディスクから計算するようにパリティが配置されたシステムにおいては、ディスクの多重障害に対応した、適切なパリティの配置がなされていない。この場合、ディスクが多重重障害を起こした場合はグローバルパリティ（全てのディスクのデータを使って計算するパリティ）を使って復旧する必要がある。また、データディスク数と同じ数のディスクから故障したディスクを管理するノードにデータを転送しなければならない。
【０００７】
そこで、１つの側面では、本発明は、故障ディスクの復旧に関して最適に配置されたパリティディスクを有するストレージシステムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
一態様によるストレージシステムは、情報を格納する複数のデータディスクと、パリティディスクを備える。パリティディスクは、複数のデータディスクのうちの一部を含むディスクグループに対応し、対応するディスクグループに含まれるデータディスクのデータに基づいて生成されたパリティ情報を格納する。また、データディスクのいずれかは、複数のディスクグループに含まれる。
【発明の効果】
【０００９】
１実施態様によれば、故障ディスクの復旧に関して最適に配置されたパリティディスクを有するストレージシステムを提供することができる。
【図面の簡単な説明】
【００１０】
【図１】ストレージシステムの一実施例の構成を図解した機能ブロック図である。
【図２】情報処理システムの構成の一例を示す。
【図３】管理サーバの構成の一例を示す。
【図４】実施形態１に係るローカルパリティの計算範囲の一例を示す。
【図５】実施形態１に係るディスク故障発生時の処理を図解したフローチャートである。
【図６】管理サーバのハードウェア構成の一例を示す。
【図７】実施形態２に係るローカルパリティの計算範囲の一例を示す。
【図８】実施形態３に係るローカルパリティの計算範囲の一例を示す。
【図９】実施形態４に係るローカルパリティの計算範囲の一例を示す。
【図１０】実施形態５に係るディスク故障発生時の処理を図解したフローチャートの前半である。
【図１１】実施形態５に係るディスク故障発生時の処理を図解したフローチャートの後半である。
【図１２】比較例１のデータ構成の一例を示す。
【図１３】比較例２のデータ構成の一例を示す。
【図１４】実施形態５と比較例との性能比較を示す図である。
【発明を実施するための形態】
【００１１】
図１は、ストレージシステムの一実施例の構成を図解した機能ブロック図である。図１においてストレージシステム１は、データディスク２、パリティディスク３、及び復元部４を備える。
【００１２】
データディスク２は、情報を格納する。パリティディスク３は、複数のデータディスク２のうちの一部を含むディスクグループに対応し、対応するディスクグループに含まれるデータディスク２のデータに基づいて生成されたパリティ情報を格納する。そして、データディスク２のいずれかは、複数のディスクグループに含まれる。
【００１３】
複数のデータディスク２のいずれも、ディスクグループのいずれかに含まれる。また、ディスクグループ間において、ディスクグループに含まれるデータディスク２の数が等しい。
【００１４】
複数のパリティディスク３は、各パリティグループ内の任意のパリティディスク３の対が、対応するディスクグループに同じデータディスク２を含まないように、複数のパリティグループに分類される。そして、複数のデータディスク２のいずれも、パリティグループのそれぞれに含まれるパリティディスク３に対応するディスクグループのいずれかに含まれる。
【００１５】
データディスク２のそれぞれはストライプのデータの格納順に昇順で識別番号が対応付けられており、各パリティディスク３に対応するディスクグループに含まれるデータディスク２の識別番号の最小値が、データディスク数をパリティディスク数で割った数だけずれている。
【００１６】
復元部４は、１以上のデータディスク２が故障した場合、故障したデータディスク２を含むディスクグループに対応するパリティディスク３を用いて、故障したデータディスク２のデータを復元する。また、復元部４は、すべての故障したデータディスク２が、選択する何れかのパリティディスク３に対応するディスクグループに含まれ、且つ、選択する全てのパリティディスク３に対応するディスクグループに１以上の故障したデータディスク２を含むように、故障したデータディスク２の数と等しい数のパリティディスク３を選択し、選択したパリティディスク３に基づいて、故障したデータディスク２のデータを復元する。さらに、復元部４は、すべての故障したデータディスク２が、選択する何れかのパリティディスク３のディスクグループに含まれ、且つ、選択する全てのパリティディスク３に対応するディスクグループに１以上の故障したデータディスク２を含み、さらに、選択するパリティディスク３に対応するディスクグループに含まれるデータディスク２の集合としての和が最小となるように、故障したデータディスク２の数と等しい数のパリティディスク３を選択し、選択したパリティディスク３に基づいて、故障したデータディスク２のデータを復元する。
【００１７】
（実施形態１）
図２は、実施形態１に係る情報処理システムの構成の一例を示す。図２において、情報処理システムは、クライアントサーバ２１、及び複数の管理サーバ２２（２２ａ〜２２ｃ）を含む。クライアントサーバ２１は複数の管理サーバ２２とネットワーク又はバスを介して接続される。そして各管理サーバ２２には、複数のディスク２３（２３ａ〜２３ｌ）が接続されており、各管理サーバ２２によりディスクに対するデータの入出力が行われる。
【００１８】
情報処理システムには、複数のディスクのうちのいくつかのディスクを含むディスクアレイが構成される。例えば、一つのディスクアレイとして、ディスク２３ａ、ディスク２３ｅ、ディスク２３ｉが含まれるディスクアレイが考えられる。また、別のディスクアレイとして、例えば、ディスク２３ａ、ディスク２３ｂ、ディスク２３ｃが含まれるディスクアレイが考えられる。
【００１９】
クライアントサーバ２１は、ユーザ端末からデータを受け付け、受け付けたデータを分割してディスクアレイを構成するディスクを管理する管理サーバ２２に送信する。
【００２０】
管理サーバ２２は、クライアントサーバ２１からデータを受信し、受信したデータを管理サーバ２２が管理するディスクに格納する。
【００２１】
ここで、ディスクアレイに格納されるデータは、所定のサイズずつ順番に、アレイ内の異なる物理ディスクに配置される。この所定のサイズの各ディスクに配置されたデータセットをストリップ（stlip）と呼ぶ。そして、複数のストリップを含むデータセットをストライプと呼ぶ。ディスクアレイの記憶スペースは、複数のストライプから構成される。
【００２２】
ディスクアレイは、データディスク、及びパリティディスクを含む。データディスクはディスクアレイを使用するユーザからのデータが格納されるディスクである。パリティディスクは、ディスク故障時にデータディスクのデータを復旧させるために用いられるパリティ情報が格納されるディスクである。
【００２３】
各パリティディスクは複数のデータディスクに対応付けられており、パリティディスクに格納されるパリティ情報は、そのパリティディスクに対応付けられた複数のデータディスクのデータを基に算出される。パリティディスクに対して対応付けられた複数のデータディスクのことを、以下の説明では、パリティディスクの計算範囲に含まれるデータディスクと記す場合がある。パリティ情報は、具体的には例えばリードソロモン符号であってよいし、種々のエラー訂正のための情報が用いられてもよい。
【００２４】
実施形態１においては、各パリティディスクの計算範囲に含まれるデータディスクは、ディスクアレイの全てのデータディスクではなく、一部のデータディスクとする。ここで、このように、計算範囲に含まれるデータディスクが、一部のデータディスクとなるパリティディスクを、以下の説明ではローカルパリティと記す場合がある。また、すべてのローカルパリティのうちの各々のローカルパリティは、互いに異なる計算範囲を有する。さらに各ローカルパリティは、少なくとも一つの他のローカルパリティの計算範囲に含まれるデータディスクと少なくとも一つの共通するデータディスクを計算範囲として含むものとする。さらに、ディスクアレイに含まれる各データディスクは、少なくともいずれかのローカルパリティの計算範囲に含まれるものとする。尚、各パリティディスクの計算範囲に含まれるデータディスクは、連続する複数のデータディスクであってもよい。データディスクが連続するとは、１つのストライプにおいて、一方のストリップの最後に書き込まれるデータの次に、他方のストリップの最初のデータとしてデータが書き込まれるようなデータディスク同士の関係を指す。
【００２５】
管理サーバ２２は、制御部３１、復元部３２、パリティ生成部３３、及び記憶部３４を含む。制御部３１は、クライアントサーバ２１または他の管理サーバ２２からの要求に応じて、ディスクのデータの読み込み及び書き込みを行い、その結果を要求元に返信する。復元部３２は、管理サーバ２２が管理するデータディスクが故障した場合に、故障したデータディスクのデータを、ローカルパリティのデータを用いて復元する。パリティ生成部３３は、各ローカルパリティの計算範囲に含まれるデータディスクに格納されたデータを用いて、パリティ情報を算出し、算出したパリティ情報をローカルパリティに格納する。記憶部３４は、ディスクアレイに含まれる各ローカルパリティと、ローカルパリティの計算範囲に含まれるデータディスクの情報を対応付けて、対応情報として記憶する。
【００２６】
以下の説明では、ディスクアレイに含まれる全ディスクの数をn、データディスク数をk、ローカルパリティのディスク数をp=n-kとすると、k=10、n=6の場合を説明する。
【００２７】
図４は、ローカルパリティの計算範囲の一例を示す。図４においては、１０個のデータディスクと６個のローカルパリティが含まれるディスクアレイの例である。そして各データディスクはＤ１〜Ｄ１０、各ローカルパリティはＬ１〜Ｌ６で示されている。
【００２８】
ローカルパリティＬ１は、Ｄ１〜Ｄ５の５つのデータディスクを計算範囲として含む。また、ローカルパリティＬ２、Ｌ３、Ｌ４、Ｌ５、Ｌ６はそれぞれ、Ｄ２〜Ｄ６、Ｄ４〜Ｄ７、Ｄ５〜Ｄ１０、Ｄ８〜Ｄ２、Ｄ９〜Ｄ３のデータディスクを計算範囲として含む。ここで、Ｌ１〜Ｌ６はいずれも、他のローカルパリティと計算範囲が同じではなく、また、少なくとも一つの他のローカルパリティと、少なくとも一つの共通するデータディスクを計算範囲として含んでいる。すなわち例えばＬ１に関していえば、Ｌ１はＬ２に対してＤ２〜Ｄ５のデータディスクを共通して計算範囲に含み、Ｌ６に対してＤ１〜Ｄ３のデータディスクを共通して計算範囲に含んでいる。
【００２９】
次に、データディスクが故障した場合の復旧について説明する。ディスクが故障した場合、先ず、故障したディスクを管理する管理サーバ２２は、他の装置（例えばクライアントサーバから）ディスクが故障したことの通知を受信する。すると管理サーバ２２の制御部３１は、故障したディスクの内容を復元したデータを格納するための、故障したディスクの代わりとなる予備のディスク（スタンバイディスク）を割り当てられる。
【００３０】
次に、管理サーバ２２の復元部３２は、ディスクアレイに含まれる複数のローカルパリティの中から、故障したディスクを復旧するために使用するローカルパリティを選択し、選択したローカルパリティのデータを用いて、故障したデータディスクのデータを復元する。
【００３１】
具体的には先ず、復元部３２は、復旧に使用するローカルパリティとして、以下の３つの条件（以下、選択条件と記す）を満たすローカルパリティの組み合わせを選択する。１つ目の選択条件は、ローカルパリティの組み合わせの要素数が、故障したデータディスク数と同じであることである。例えば、故障したデータディスクの数が３つであれば、組み合わせに含むローカルパリティとして、３つのローカルパリティが選択されることとなる。２つ目の選択条件は、組み合わせに含まれるローカルパリティの各々が、計算範囲に少なくとも一つの故障したデータディスクを含むことである。すなわち、故障したデータディスクを計算範囲に一つも含まないローカルパリティは、組み合わせの要素としては選択されない。３つ目の選択条件は、故障したデータディスクが、組み合わせに含まれるローカルパリティのいずれかの計算範囲に含まれることである。
【００３２】
復旧に使用するローカルパリティの組み合わせの選択について、図４の例を用いて説明する。図４の例において、Ｄ２、Ｄ５、Ｄ８の３つのデータディスクが故障した場合を考える。復旧に使用するローカルパリティの組み合わせは、選択条件を満たす。図４の例では、故障したデータディスク数は３つであるので、復旧に使用するデータディスクとしては３つのローカルパリティが選択される。選択されるローカルパリティは、計算範囲として少なくとも一つの故障したデータディスクを含むものであるので、Ｄ２、Ｄ５、Ｄ８のうち少なくとも一つを計算範囲に含むローカルパリティである、Ｌ１〜Ｌ６の何れかから選択される。そしてさらに、選択された３つのローカルパリティの何れかの計算範囲に、故障した各データディスクが含まれるという条件を満たすローカルパリティの組み合わせが選択される。Ｄ２、Ｄ５、Ｄ８の各々が、３つのローカルパリティのいずれかの計算範囲に含まれるような、ローカルパリティの組み合わせは、例えば以下のように決定される。
【００３３】
Ｄ２、Ｄ５、Ｄ８の各々が、３つのローカルパリティのいずれかの計算範囲に含まれるためには、Ｄ２、Ｄ５、Ｄ８のそれぞれを計算範囲として含むローカルパリティの集合から、１つずつ、ローカルパリティが重複しないように選択されればよい。すなわち、図４において、Ｄ２を計算範囲として含むローカルパリティの集合は、｛Ｌ１、Ｌ２、Ｌ５、Ｌ６｝である。Ｄ５を計算範囲として含むローカルパリティの集合は、｛Ｌ１、Ｌ２、Ｌ３、Ｌ４｝である。Ｄ８を計算範囲として含むローカルパリティの集合は、｛Ｌ４、Ｌ５｝である。このとき、Ｄ２、Ｄ５、Ｄ８のそれぞれを計算範囲として含むローカルパリティの集合から、１つずつ、選択したローカルパリティが重複しないように選択すればよい。したがって、ローカルパリティの組み合わせは、（Ｌ１、Ｌ２、Ｌ４）、（Ｌ１、Ｌ２、Ｌ５）、（Ｌ１、Ｌ３、Ｌ４）、（Ｌ１、Ｌ３、Ｌ５）、（Ｌ１、Ｌ４、Ｌ５）、（Ｌ２、Ｌ３、Ｌ４）、（Ｌ２、Ｌ３、Ｌ５）、（Ｌ２、Ｌ４、Ｌ５）、（Ｌ５、Ｌ３、Ｌ４）、（Ｌ６、Ｌ１、Ｌ４）、（Ｌ６、Ｌ１、Ｌ５）、（Ｌ６、Ｌ２、Ｌ４）、（Ｌ６、Ｌ２、Ｌ５）、（Ｌ６、Ｌ３、Ｌ４）、（Ｌ６、Ｌ３、Ｌ５）、（Ｌ６、Ｌ４、Ｌ５）のうちのいずれかとなる。これらの組み合わせののうちの何れかを、復元部３２は復旧に使用するローカルパリティの組み合わせとして選択する。
【００３４】
選択条件を満たすローカルパリティの組み合わせのうちの何れかを選択すると、復元部３２は、選択したローカルパリティの組み合わせを用いて、パリティ計算式を使用して連立一次方程式を解くことにより、故障したデータディスクのデータを復元する。
【００３５】
具体的には先ず、復旧に使用するローカルパリティの組み合わせを選択すると、復元部３２は、選択した組み合わせのローカルパリティのデータと、選択した組み合わせのローカルパリティの計算範囲に含まれるデータディスクのデータとを取得する。ただし、故障したデータディスクは取得の対象外とする。例えば、図４の例において、パリティの組み合わせとして、（Ｌ１、Ｌ２、Ｌ５）が選択された場合、復元部３２は、先ずＬ１、Ｌ２、Ｌ５のデータを取得する。それとともに復元部３２は、Ｌ１、Ｌ２、Ｌ５の計算範囲に含まれるデータディスクであって故障していないデータディスクである、Ｄ１、Ｄ３、Ｄ４、Ｄ６、Ｄ９、Ｄ１０のデータを取得する。尚、組み合わせを選択した復元部３２は、例えば取得対象のデータが格納されているディスクを管理する管理サーバ２２に取得対象データの取得要求を送信し、取得要求に対する応答を受信することにより、取得対象データを取得してもよい。また、復元部３２は、記憶部３４に記憶された対応情報を参照することにより、ローカルパリティの計算範囲に含まれるデータディスクを特定することができる。
【００３６】
復元部３２は、取得したローカルパリティのデータと、そのローカルパリティの計算範囲に含まれるデータディスクのデータとを用いて、パリティ計算式を使用して３元連立一次方程式を解くことによって、Ｄ２、Ｄ５、Ｄ８のデータを復元する。
【００３７】
そして復元部３２は、復元したＤ２、Ｄ５、Ｄ８のデータを、各々に対応する新しく割り当てられたスタンバイディスクに格納し、復旧を完了する。
【００３８】
尚、図４の例のようにp=6、すなわちローカルパリティが６個存在する場合は、６個のローカルパリティのパリティ計算式を使用して、最高で、６元一次方程式を解くことによって６個のデータディスクを復旧することができる。
【００３９】
多元一次方程式は、例えば、掃き出し法などの種々の方法を用いて解を求めることができる。
【００４０】
次に、故障したディスクに、データディスクとローカルパリティとが含まれる場合の復旧について説明する。ここでは、故障したローカルパリティは、計算範囲に故障したデータディスクを含むものとする。尚、計算範囲に故障したデータディスクを含まないローカルパリティが故障した場合は、復元部３２は、正常なデータディスクのデータを用いてローカルパリティの再作成を行う。
【００４１】
故障したディスクに、データディスクとローカルパリティとが含まれる場合には、データディスクのデータの復元には故障したローカルパリティのデータを使用できないため、復元部３２は正常なローカルパリティを使用してデータディスクのデータを復元する。その後、復旧したデータディスクのデータを用いて、復元部３２は故障したローカルパリティのデータを復旧（再作成）する。例えば図４の例において、Ｌ１、Ｄ５、Ｄ８が故障した場合、先ず、Ｄ５及びＤ８の復旧を正常なローカルパリティを用いて行う。その後、復旧したＤ５及びＤ１〜Ｄ４のデータを用いて、Ｌ１のパリティ情報が復旧（再作成）される。
【００４２】
尚、故障したディスクに、データディスクとローカルパリティとが含まれる場合の復旧方法は、復旧に使用するローカルパリティとして故障したローカルパリティを除外すること以外は、データディスクが故障した場合の復旧と同じである。
【００４３】
具体的には先ず、復元部３２は、復旧に使用するローカルパリティの組み合わせの選択において、上述した３つの選択条件に加えて、選択されるローカルパリティは故障していないことを条件とする、ローカルパリティの組み合わせを選択する。
【００４４】
図４の例において、Ｄ５及びＤ８が故障した場合に、故障したデータディスク数は２つであるので、復旧に使用するデータディスクとしては２つのローカルパリティが選択される。選択されるローカルパリティは、故障していないローカルパリティであって、計算範囲として少なくとも一つの故障したデータディスクを含むものであるので、Ｌ２〜Ｌ５の何れかから選択される。そしてさらに、選択された２つのローカルパリティの何れかの計算範囲に、故障した各データディスクが含まれるという条件を満たすローカルパリティの組み合わせが選択される。このような組み合わせは、（Ｌ２、Ｌ４）、（Ｌ２、Ｌ５）、（Ｌ３、Ｌ４）、（Ｌ３、Ｌ５）、（Ｌ４、Ｌ５）のいずれかである。これらの組み合わせのうちの何れかを、復元部３２は、復旧に使用するローカルパリティの組み合わせとして選択する。
【００４５】
そして復元部３２は、選択した組み合わせのローカルパリティのデータと、選択された組み合わせのローカルパリティの計算範囲に含まれるデータディスクであって故障していないデータディスクのデータと、を取得する。取得したデータを用いて、復元部３２は、パリティ計算式を使用して多元連立一次方程式を解くことによって、故障したデータディスクのデータを復元する。
【００４６】
故障したデータディスクの復旧が完了したら、復元部３２は、復旧したデータディスクのデータ、及び計算範囲に含まれるそのほかの正常なデータディスクのデータを用いてローカルパリティの再作成を行う。
【００４７】
尚、ディスクが故障した場合、他の装置から通知を受信するとしたが、故障ディスクを管理する管理サーバ２２の制御部３１がディスクの故障を検知してもよい。
【００４８】
次に、復旧オーバヘッドについて説明する。実施形態１では、復旧オーバヘッドは、故障したディスクを管理するノードが復旧時に受信するデータのデータ転送量と定義する。尚、説明のために、１つのディスクに格納されたデータのデータ転送量は１とカウントする。
【００４９】
一重障害時は、復旧に使用するローカルパリティの計算範囲に含まれるデータディスクの数がそのまま復旧オーバヘッドとなる。尚、以下の説明では、ローカルパリティの計算範囲に含まれるデータディスクの数を、ローカルパリティの計算範囲のサイズと記す場合がある。例えば図４の例の場合、一重障害時の復旧オーバヘッドは最大で６となる。ここで、Ｌ４の一重障害時の復旧オーバヘッドについて説明する。Ｌ４の計算範囲は、Ｄ５〜Ｄ１０の６個である。よって、Ｄ５〜Ｄ１０のうちの何れかのデータディスクが故障した場合にＬ４を用いて復旧する場合、Ｄ５〜Ｄ１０のうちの故障していない５個のデータディスクのデータとＬ４のデータの計６個のディスクのデータが転送されることとなる。従って、この場合復旧オーバヘッドは６となる。
【００５０】
多重障害時は、選択した組み合わせのローカルパリティのデータと、選択された組み合わせのローカルパリティの計算範囲に含まれるデータディスクであって故障していないデータディスクのデータと、の合計が復旧オーバヘッドとなる。例えば、二重障害時、図４において、Ｄ２とＤ５が故障して、Ｌ１とＬ６のデータを用いて復旧する場合は、Ｄ２、Ｄ５を管理する各管理サーバにそれぞれ、Ｄ１，Ｄ３，Ｄ４，Ｄ９、Ｄ１０，Ｌ１，Ｌ６の７個のディスクのデータが転送される。従って、この場合の復旧オーバヘッドは７となる。図４の構成の場合は、データディスクの二重障害時の復旧オーバヘッドは６または７のいずれかとなる（平均で６．３６）。
【００５１】
次に、初期パリティ生成時のオーバヘッド評価について説明する。実施形態１では、初期パリティ生成時のオーバヘッドは、ローカルパリティに格納されるパリティ情報を生成する際に、そのローカルパリティの管理サーバ２２が受信するデータのデータ転送量と定義する。
【００５２】
初期パリティ生成時には、各ローカルパリティの管理サーバ２２のパリティ生成部３３は、ローカルパリティの計算範囲に含まれる全てのデータディスクのデータを取得して、パリティを生成する。従って、初期パリティ生成時のオーバヘッドは、ローカルパリティの計算範囲のデータディスクに格納されたデータ量となる。
【００５３】
例えば図４の例では、初期パリティ生成時は、Ｄ１〜Ｄ５のデータがＬ１の管理サーバ２２へ、Ｄ２〜Ｄ６のデータがＬ２の管理サーバ２２へ、という形で並列に多対多のデータ転送が行われる。尚、データディスクからのデータの読み込みは各管理サーバ２２で１回のみ行われる（１回読み込んだデータをメモリ上にキャッシュして、複数ノードへ転送する）。
【００５４】
図４の例では、計算範囲が最大のローカルパリティはＬ４の６であるので、初期パリティ生成時には、最大で６個のデータディスクのデータが転送されることとなる。よって、図４のシステムにおける初期化オーバヘッドは６となる。
【００５５】
実施形態１における初期化オーバヘッドは、例えば、すべてのデータディスクを計算範囲に含むグローバルパリティを有するディスクアレイ装置における初期化オーバヘッドと比較すると、少なく抑えることができる。例えば、データディスク数が１０のグローバルパリティを有するディスクアレイ装置では、初期化オーバヘッドは１０となる。それに対して、例えば図４の例では初期化オーバヘッドは６であり、実施形態１では、初期化オーバヘッドを少なく抑えることができる。
【００５６】
次に、新規データディスクの追加時のオーバヘッド評価について説明する。実施形態１では、新規データディスクの追加時のオーバヘッドは、ディスクアレイに新規にデータディスクを追加する際に、パリティ情報の再計算が行われるローカルパリティの数とする。
【００５７】
新規データディスク追加時には、計算範囲が新規データディスクを含むように変更されるローカルパリティでは、パリティ情報の再計算が行われる。
【００５８】
例えば図４において、Ｄ５とＤ６の間に新規ディスクＤ’５を追加する場合を考える。この場合、Ｌ１、Ｌ２、Ｌ３、Ｌ４の計算範囲にＤ’５が加えられることとなる。これにより、Ｌ１〜Ｌ４の計算範囲のサイズは１増加する。計算範囲が変更されたＬ１〜Ｌ４を管理する管理サーバ２２のパリティ生成部３３は、変更後の計算範囲に含まれるすべてのデータディスクのデータを取得し、取得したデータを用いて、パリティ情報を算出する。そしてパリティ生成部３３は、算出したパリティ情報を、対応するローカルパリティに格納する。
【００５９】
一方で、Ｌ５、Ｌ６は計算範囲が変わらないため、パリティ情報の再計算は行われない。よって、図４において、新規ディスクＤ’５を追加した場合は、Ｌ１〜Ｌ４の４つのパリティ情報の再計算が行われるので、新規データディスクの追加時のオーバヘッドは４となる。このように、実施形態１では、新規データディスクを追加する際に、計算範囲が変わらないローカルパリティが存在することから、新規データディスク追加時のオーバヘッドを少なく抑えることができる。
【００６０】
図５は、実施形態１に係るディスク故障発生時の処理を図解したフローチャートである。
【００６１】
図５において、先ず復元部３２は、故障したディスクの中にローカルパリティが含まれるか否かを判定する（Ｓ１０１）。故障したディスクの中にローカルパリティが含まれる場合（Ｓ１０１でＹｅｓ）、復元部３２は、故障したローカルパリティを、復元に使用するローカルパリティの集合から除外する（Ｓ１０２）。そして、処理はＳ１０３に遷移する。
【００６２】
Ｓ１０１において、故障したディスクの中にローカルパリティが含まれない場合（Ｓ１０１でＮｏ）、復元部３２は、故障したデータディスクの数と同じ数のローカルパリティの組み合わせのうち、一つを選択する（Ｓ１０３）。ここで、復元部３２が選択する組み合わせは、Ｓ１０３において未だ選択されたことのないローカルパリティの組合せとする。
【００６３】
次に、復元部３２は、Ｓ１０３において選択した組み合わせが存在したか否かを判定する（Ｓ１０４）。組み合わせが存在しないと復元部３２により判定された場合（Ｓ１０４でＹｅｓ）、故障したデータディスクの復元ができないので、処理は異常終了する。
【００６４】
一方Ｓ１０４において、組み合わせが存在すると判定した場合（Ｓ１０４でＮｏ）、復元部３２は計算範囲に故障したデータディスクを全く含まないローカルパリティがＳ１０３で選択した組み合わせに存在するか否かを判定する（Ｓ１０５）。計算範囲に故障したデータディスクを全く含まないローカルパリティが存在する場合（Ｓ１０５でＹｅｓ）、処理はＳ１０３に遷移する。
【００６５】
一方Ｓ１０５において、計算範囲に故障したデータディスクを全く含まないローカルパリティが存在しない場合（Ｓ１０５でＮｏ）、復元部３２は、故障したデータディスクが、選択した組み合わせのどのローカルパリティの計算範囲にも含まれないか否かを判定する（Ｓ１０６）。故障したすべてのデータディスクが、選択した組み合わせのどのローカルパリティの計算範囲にも含まれないと判定された場合（Ｓ１０６でＹｅｓ）、処理はＳ１０３に遷移し、新たなローカルパリティの組み合わせが選択される。
【００６６】
一方Ｓ１０６において、故障したすべてのデータディスクが、選択した組み合わせの何れかローカルパリティの計算範囲に含まれると判定した場合（Ｓ１０６でＮｏ）、復元部３２は、連立一次方程式を解くことにより、データディスクを復旧する（Ｓ１０７）。具体的には、復元部３２はＳ１０３で選択した組み合わせのローカルパリティのデータと、選択した組み合わせのローカルパリティの計算範囲に含まれるデータディスクのデータとを取得する。ただし、故障したデータディスクは取得の対象外とする。そして復元部３２は、取得したローカルパリティのデータと、そのローカルパリティの計算範囲に含まれるデータディスクのデータとを用いて、パリティ計算式を使用して連立一次方程式を解くことによって故障したデータディスクのデータを復元する。
【００６７】
そして、処理は正常終了する。
次に、管理サーバ２２の構成について説明する。図６は、管理サーバ２２のハードウェア構成の一例を示す。
【００６８】
管理サーバ２２は、ＣＰＵ（Central Processing Unit）４０１、メモリ４０２、記憶装置４０３、読取装置４０４、及び通信インターフェース４０５を含む。ＣＰＵ４０１、メモリ４０２、記憶装置４０３、読取装置４０４、及び通信インターフェース４０５はバスを介して接続される。
【００６９】
ＣＰＵ４０１は、メモリ４０２を利用して上述のフローチャートの手順を記述したプログラムを実行することにより、制御部３１、復元部３２、及びパリティ生成部３３の一部または全部の機能を提供する。
【００７０】
メモリ４０２は、例えば半導体メモリであり、ＲＡＭ（Random Access Memory）領域およびＲＯＭ（Read Only Memory）領域を含んで構成される。記憶装置４０３は、例えばハードディスクである。なお、記憶装置４０３は、フラッシュメモリ等の半導体メモリであってもよい。また、記憶装置４０３は、外部記録装置であってもよい。記憶装置４０３は記憶部３４の一部または全部の機能を提供する。
【００７１】
読取装置４０４は、ＣＰＵ４０１の指示に従って着脱可能記憶媒体４５０にアクセスする。着脱可能記憶媒体４５０は、たとえば、半導体デバイス（ＵＳＢメモリ等）、磁気的作用により情報が入出力される媒体（磁気ディスク等）、光学的作用により情報が入出力される媒体（ＣＤ−ＲＯＭ、ＤＶＤ等）などにより実現される。尚、読取装置４０４は管理サーバ２２に含まれなくてもよい。
【００７２】
通信インターフェース４０５は、クライアントサーバ２１及び他の管理サーバ２２との間でデータを送受信する。
【００７３】
実施形態のプログラムは、例えば、下記の形態で管理サーバ２２に提供される。
（１）記憶装置４０３に予めインストールされている。
（２）着脱可能記憶媒体４５０により提供される。
（３）プログラムサーバ（図示せず）から通信インターフェース４０５を介して提供される。
【００７４】
さらに、実施形態の管理サーバ２２の一部は、ハードウェアで実現してもよい。或いは、実施形態の管理サーバ２２は、ソフトウェアおよびハードウェアの組み合わせで実現してもよい。
【００７５】
尚、クライアントサーバ２１と管理サーバ２２は、同一筐体に含まれてもよく、クライアントサーバ２１と管理サーバ２２の機能は同じＣＰＵにより提供されてもよい。また、管理サーバ２２は、ストレージ装置に含まれるコントローラモジュールであってもよい。
【００７６】
また、本実施形態では、データディスクとパリティディスクを区別して記載したが、ストライプ毎にパリティ情報を格納する物理ディスクを変更してもよい。すなわち、１つのストライプのデータと、他のストライプのパリティ情報が同じ物理ディスクに格納されてもよい。
【００７７】
実施形態１では、グローバルパリティを使用せずローカルパリティを使用することによって、初期パリティ生成時やディスクの二重障害時においてもネットワークデータ転送量を削減できる。従って、データの復旧時間を短縮できる。また、同様の理由により、整合性チェック時のデータ転送量を削減できる。
【００７８】
また、実施形態１のストレージシステムは、パリティの計算範囲を部分的に重ね合わせることにより、ローカルパリティのみでありながら、一定個数までのディスクが故障した場合の復旧に対応している。また、新規ディスク追加時は、一部のパリティのみを再計算すればよいため、データ転送量を削減できる。
【００７９】
（実施形態２）
実施形態２では、各ローカルパリティの計算範囲に含まれるデータディスクの数（計算範囲のサイズ）が均一となるように構成される。これにより、故障したデータディスクのデータを復旧する際に、どのローカルパリティから復旧する場合でも、復旧オーバヘッドが均一となる。よって、ワーストケースで見積もったＲＴＯ（Ｒｅｃｏｖｅｒｙ  Ｔｉｍｅ  Ｏｂｊｅｃｔｉｖｅ）を最小にすることができる。ＲＴＯは、ディスクが故障してから、復旧が完了するまでにかかる時間の目標値である。
【００８０】
実施形態２に係る情報処理システムの構成は、各ローカルパリティの計算範囲のサイズが均一となるように構成されること以外は、実施形態１と同様である。
【００８１】
図７は、実施形態２に係るローカルパリティの計算範囲の一例を示す図である。図７においては、１０個のデータディスクと６個のローカルパリティが含まれるディスクアレイの例である。そして各データディスクはＤ１〜Ｄ１０、各ローカルパリティはＬ１〜Ｌ６で示されている。
【００８２】
ローカルパリティＬ１は、Ｄ１〜Ｄ５の５つのデータディスクを計算範囲として含む。また、ローカルパリティＬ２、Ｌ３、Ｌ４、Ｌ５、Ｌ６はそれぞれ、Ｄ２〜Ｄ６、Ｄ３〜Ｄ７、Ｄ６〜Ｄ１０、Ｄ８〜Ｄ２、Ｄ９〜Ｄ３のデータディスクを計算範囲として含む。ここで、Ｌ１〜Ｌ６はいずれも、実施形態１と同様に、他のローカルパリティと計算範囲が同じではなく、また、少なくとも一つの他のローカルパリティと、少なくとも一つの共通するデータディスクを計算範囲として含んでいる。
【００８３】
実施形態１とは異なり図７の例では、Ｌ１〜Ｌ６のいずれも、計算範囲に含まれるデータディスクの数は５個となっており、均一になっている。
【００８４】
ディスクが故障した場合の復旧方法は、実施形態１と同様である。ただし、復旧に使用するローカルパリティの組み合わせの選択においては、選択条件を満たす複数の組み合わせのうちどれを選択したとしても、復旧オーバヘッドは等しくなる。
【００８５】
一重障害時は、復旧に使用するローカルパリティの計算範囲のサイズがそのまま復旧オーバヘッドとなる。よって、図７の例では、ローカルパリティの計算範囲のサイズは５であるので、一重障害時の復旧オーバヘッドは５となる。
【００８６】
多重障害時は、選択した組み合わせのローカルパリティのデータと、選択された組み合わせのローカルパリティの計算範囲に含まれるデータディスクであって故障していないデータディスクのデータと、の合計が復旧オーバヘッドとなる。よって、二重障害時、図７において、Ｄ２とＤ５が故障して、Ｌ１とＬ６のデータを用いて復旧する場合は、Ｄ２、Ｄ５を管理する各管理サーバにそれぞれ、Ｄ１，Ｄ３，Ｄ４，Ｄ９、Ｄ１０，Ｌ１，Ｌ６の７個のディスクのデータが転送される。
【００８７】
実施形態２のシステムは、実施形態１と比較すると、ワーストケースで見積もった場合のＲＴＯを最小にすることができる。
【００８８】
（実施形態３）
実施形態３では、ローカルパリティは、計算範囲に含まれるすべてのデータディスクが互いに異なるように、複数のグループに分類される。また、データディスクのいずれも、各グループに含まれるローカルパリティの計算範囲のいずれかに含まれるように、ローカルパリティは分類される。
【００８９】
実施形態３に係る情報処理システムの構成は、各ローカルパリティがグループに分類されるように構成されること以外は、実施形態２と同様である。
【００９０】
実施形態３では、全てのデータディスクが、グループ数と同じ数のローカルパリティの計算範囲に含まれることになり、グループ数と同じ数のディスク障害まで復旧可能となる。すなわち、最小ハミング距離が大きくなり、信頼性の評価が向上する。
【００９１】
図８は、実施形態３に係るローカルパリティの計算範囲の一例を示す図である。図８においては、１０個のデータディスクと６個のローカルパリティが含まれるディスクアレイの例である。そして各データディスクはＤ１〜Ｄ１０、各ローカルパリティはＬ１〜Ｌ６で示されている。
【００９２】
ローカルパリティＬ１は、Ｄ１〜Ｄ５の５つのデータディスクを計算範囲として含む。また、ローカルパリティＬ２、Ｌ３、Ｌ４、Ｌ５、Ｌ６はそれぞれ、Ｄ２〜Ｄ６、Ｄ３〜Ｄ７、Ｄ６〜Ｄ１０、Ｄ７〜Ｄ１（Ｄ７、Ｄ８、Ｄ９、Ｄ１０、Ｄ１）、Ｄ８〜Ｄ２（Ｄ８、Ｄ９、Ｄ１０、Ｄ１、Ｄ２）のデータディスクを計算範囲として含む。ここで、Ｌ１〜Ｌ６はいずれも、実施形態１と同様に、他のローカルパリティと計算範囲が同じではなく、また、少なくとも一つの他のローカルパリティと、少なくとも一つの共通するデータディスクを計算範囲として含んでいる。
【００９３】
実施形態３では、各ローカルパリティは複数のグループに分類される。各ローカルパリティのグループの分類は、同一のグループに含まれる各ローカルパリティの計算範囲に含まれるすべてのデータディスクが互いに異なるように行われる。言い換えると各ローカルパリティは、グループ内の任意のローカルパリティの対が、計算範囲に同じデータディスクを含まないように、複数のグループに分類される。また、データディスクのいずれも、各グループに含まれるローカルパリティの計算範囲のいずれかに含まれるように、ローカルパリティは分類される。
【００９４】
図８の例では、ローカルパリティは３つのグループに分類され、Ｌ１とＬ４、Ｌ２とＬ５、Ｌ３とＬ６が同じグループに含まれるように分類される。
【００９５】
Ｌ１の計算範囲に含まれるデータディスクは、Ｄ１〜Ｄ５であり、Ｌ４の計算範囲に含まれるデータディスクはＤ６〜Ｄ１０である。よって、Ｌ１とＬ４のグループは、各ローカルパリティの計算範囲に含まれる全てのデータディスクが互いに異なっている。言い換えると、Ｌ１とＬ４の計算範囲に含まれるデータディスクはＬ１とＬ４で重複していない。さらに、ディスクアレイを構成する全てのデータディスクＤ１〜Ｄ１０のいずれもが、Ｌ１とＬ４の計算範囲の何れかに含まれている。
【００９６】
実施形態２において説明した図７の例では、計算範囲にＤ２とＤ３を含むローカルパリティの数は４である一方で、計算範囲にＤ７とＤ８を含むローカルパリティの数は２である。これは、データディスクによって、データ消失率が異なることを意味する。例えば、一重障害の場合、Ｄ２のデータディスクは、Ｌ１、Ｌ２、Ｌ５、Ｌ６の４つ全てが故障しなければ復旧可能であるが、Ｄ７のデータディスクは、Ｌ３とＬ４が故障すると復旧不可能となる。図７の例では、最小ハミング距離は３となり、信頼性の評価は低い。
【００９７】
それに比較して、実施形態３の図８の例では、全てのデータディスクがグループ数と同じ数のローカルパリティの計算範囲に含まれることになる。すなわち、Ｄ１〜Ｄ１０のいずれも、データ消失率は等しくなる。例えば、一重障害の場合、Ｄ１〜Ｄ１０の各データディスクは、各々を計算範囲に含む３つのローカルパリティが故障しなければ復旧可能であり、最小ハミング距離は４となる。よって、図７の例と比較すると、信頼性の評価が向上する。
【００９８】
（実施形態４）
実施形態４では、ディスクアレイに含まれる全てのローカルパリティの計算範囲が等間隔でずれるように構成される。すなわち、全てのローカルパリティの計算範囲の最初のデータディスクが、（データディスク数）／（ローカルパリティ数）だけずらすように構成される。尚、kがpで割り切れる場合は、パリティの計算範囲の開始位置をデータディスク上で等間隔に配置されるが、そうでない場合は、k/pの値の前後の整数を使用し、ほぼ等間隔を満たすように配置される。例えば、k=10、p=6の場合は、kがpで割り切れないため（k/p=1.67）、開始位置の間隔を1または2とする。
【００９９】
実施形態４に係る情報処理システムの構成は、ディスクアレイに含まれる全てのローカルパリティの計算範囲が等間隔でずれるように構成されること以外は、実施形態３と同様である。
【０１００】
図９は、実施形態４に係るローカルパリティの計算範囲の一例を示す図である。図９においては、１０個のデータディスクと６個のローカルパリティが含まれるディスクアレイの例である。そして各データディスクはＤ１〜Ｄ１０、各ローカルパリティはＬ１〜Ｌ６で示されている。尚、各データディスクは、ストライプのデータが格納される順に昇順でＤ１〜Ｄ１０の識別番号が振られているものとする。
【０１０１】
ローカルパリティＬ１は、Ｄ１〜Ｄ５の５つのデータディスクを計算範囲として含む。また、ローカルパリティＬ２、Ｌ３、Ｌ４、Ｌ５、Ｌ６はそれぞれ、Ｄ３〜Ｄ７、Ｄ５〜Ｄ９、Ｄ６〜Ｄ１０、Ｄ８〜Ｄ２（Ｄ８、Ｄ９、Ｄ１０、Ｄ１、Ｄ２）、Ｄ１０〜Ｄ４（Ｄ１０、Ｄ１、Ｄ２、Ｄ３、Ｄ４）のデータディスクを計算範囲として含む。ここで、Ｌ１〜Ｌ６はいずれも、実施形態１と同様に、他のローカルパリティと計算範囲が同じではなく、また、少なくとも一つの他のローカルパリティと、少なくとも一つの共通するデータディスクを計算範囲として含んでいる。
【０１０２】
図９の例では、（データディスク数）／（ローカルパリティ数）＝１０／６＝１．６７であるので、各ローカルパリティの計算範囲の開始位置が、１または２だけずれている。これにより、複数のデータディスクの復旧時に計算範囲の開始位置が互いに近いローカルパリティを選択することが容易になる。その結果、ローカルパリティの計算範囲に含まれるデータディスクの数が小さくなり、復旧オーバヘッドを削減することができる。
【０１０３】
ディスクが故障した場合の復旧方法は、実施形態１と同様である。ただし、例えば図９の例において、Ｄ３とＤ８が故障した場合、データディスクの復旧に使用するローカルパリティの組み合わせとして、Ｌ２とＬ３を選択することができる。Ｌ２とＬ３を用いてＤ３とＤ８のデータを復元する場合、復旧のために転送されるデータは、Ｄ４、Ｄ５、Ｄ６、Ｄ７、Ｌ２、Ｌ３の６個のディスクのデータとなる。よってこの場合の復旧オーバヘッドは６となる。
【０１０４】
一方、例えば実施形態３の図８の例の場合、Ｄ３とＤ８が故障した場合、データディスクの復旧に使用するローカルパリティの組み合わせとして、Ｌ３とＬ４を選択することができる。Ｌ３とＬ４を用いてＤ３とＤ８のデータを復元する場合、復旧のために転送されるデータは、Ｄ４、Ｄ５、Ｄ６、Ｄ７、Ｄ９、Ｄ１０、Ｌ２、Ｌ３の８個のディスクのデータとなる。よってこの場合の復旧オーバヘッドは８となる。よって、実施形態４は、実施形態３と比較した場合、復旧オーバヘッドを削減することができる。
【０１０５】
このように実施形態４は、各ローカルパリティの計算範囲の開始位置が等間隔でずれるように構成されることにより、復旧オーバヘッドを削減することができる。
【０１０６】
（実施形態５）
故障したディスク数がローカルパリティの数より少ない場合、復旧に使用するローカルパリティの組み合わせには任意性が生じる。実施形態５では、復旧に使用するローカルパリティの組み合わせの選択において、組み合わせに含まれる全てのローカルパリティの計算範囲に含まれるデータディスクの集合としての和が最小になるように、組み合わせが選択される。
【０１０７】
例えば、図９の例において、Ｄ１とＤ２の２個のデータディスクが故障した場合を考える。この場合、選択条件を満たすローカルパリティの組み合わせは、（Ｌ１、Ｌ５）、（Ｌ１、Ｌ６）、（Ｌ５、Ｌ６）の３通りである。この３通りの組み合わせの何れの組み合わせを使用しても、Ｄ１及びＤ２の２個のデータディスクを復旧することは可能である。
【０１０８】
実施形態５では、選択条件を満たすローカルパリティの組み合わせのうち、組み合わせに含まれる全てのローカルパリティの計算範囲に含まれるデータディスクの集合としての和が最小になるように、復旧に使用するローカルパリティの組み合わせが選択される。図９の例において、（Ｌ１、Ｌ５）の組み合わせの場合、Ｌ１とＬ５の計算範囲に含まれるデータディスクの集合としての和は、｛Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、Ｄ８、Ｄ９、Ｄ１０｝の８個である。（Ｌ１、Ｌ６）の組み合わせの場合、Ｌ１とＬ６の計算範囲に含まれるデータディスクの集合としての和は、｛Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、Ｄ１０｝の６個である。（Ｌ５、Ｌ６）の組み合わせの場合、Ｌ５とＬ６の計算範囲に含まれるデータディスクの集合としての和は、｛Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ８、Ｄ９、Ｄ１０｝の７個である。よって、組み合わせに含まれるローカルパリティの計算範囲に含まれるデータディスクの集合としての和が最小になる組み合わせは、（Ｌ１、Ｌ６）となる。よって、復元部３２は、復旧に使用するローカルパリティの組み合わせとして、（Ｌ１、Ｌ６）の組み合わせを選択する。
【０１０９】
以下の説明では、組み合わせに含まれる全てのローカルパリティの計算範囲に含まれるデータディスクの集合としての和を、組み合わせの計算範囲の集合としての和と記す場合がある。
【０１１０】
次に、実施形態５に係るディスク故障発生時の処理の動作について、図１０及び図１１を参照して説明する。図１０は、実施形態５に係るディスク故障発生時の処理を図解したフローチャートの前半である。図１１は、実施形態５に係るディスク故障発生時の処理を図解したフローチャートの後半である。
【０１１１】
図１０において、先ず復元部３２は、故障したディスクの中にローカルパリティが含まれるか否かを判定する（Ｓ２０１）。故障したディスクの中にローカルパリティが含まれる場合（Ｓ２０１でＹｅｓ）、復元部３２は、故障したローカルパリティを、復元に使用するローカルパリティの集合から除外する（Ｓ２０２）。そして、処理はＳ２０３に遷移する。
【０１１２】
Ｓ２０１において、故障したディスクの中にローカルパリティが含まれない場合（Ｓ２０１でＮｏ）、復元部３２は、故障したデータディスクの数と同じ数のローカルパリティの組み合わせのうち、一つを選択する（Ｓ２０３）。ここで、復元部３２が選択する組み合わせは、Ｓ２０３において未だ選択されたことのないローカルパリティの組合せとする。
【０１１３】
次に、復元部３２は、Ｓ２０３において選択した組み合わせが存在したか否かを判定する（Ｓ２０４）。
【０１１４】
Ｓ２０４において、組み合わせが存在すると判定した場合（Ｓ２０４でＮｏ）、復元部３２は、Ｓ２０３において選択した組み合わせにおいて計算範囲に故障したデータディスクを全く含まないローカルパリティが存在するか否かを判定する（Ｓ２０５）。計算範囲に故障したデータディスクを全く含まないローカルパリティが存在する場合（Ｓ２０５でＹｅｓ）、処理はＳ２０３に遷移する。
【０１１５】
一方Ｓ２０５において、計算範囲に故障したデータディスクを全く含まないローカルパリティが存在しない場合（Ｓ２０５でＮｏ）、復元部３２は、故障したデータディスクが、Ｓ２０３で選択した組み合わせのどのローカルパリティの計算範囲にも含まれないか否かを判定する（Ｓ２０６）。故障したすべてのデータディスクが、選択した組み合わせのどのローカルパリティの計算範囲にも含まれないと判定された場合（Ｓ２０６でＹｅｓ）、処理はＳ２０３に遷移し、新たなローカルパリティの組み合わせが選択される。
【０１１６】
一方Ｓ２０６において、故障したすべてのデータディスクが、Ｓ２０３で選択した組み合わせのいずれかのローカルパリティの計算範囲に含まれると判定した場合（Ｓ２０６でＮｏ）、復元部３２は、組み合わせの候補と、計算範囲の集合としての和の数の比較を行う（Ｓ２０７）。ここで、組み合わせの候補は、Ｓ２０８において設定されるものである。具体的には復元部３２は、組み合わせの候補が存在する場合、直近のＳ２０３で選択された組み合わせの計算範囲の集合としての和が、組み合わせの候補の計算範囲の集合としての和より大きいか否かを判定する。直近のＳ２０３で選択された組み合わせの計算範囲の集合としての和が、組み合わせの候補の計算範囲の集合としての和より大きいと判定された場合（Ｓ２０７でＹｅｓ）、処理はＳ２０３に遷移し、新たなローカルパリティの組み合わせが選択される。
【０１１７】
一方Ｓ２０７において、直近のＳ２０３で選択された組み合わせの計算範囲の集合としての和が、組み合わせの候補の計算範囲の集合としての和より大きくないと判定された場合（Ｓ２０７でＮｏ）、直近のＳ２０３で選択された組み合わせを組み合わせの候補として再設定する（Ｓ２０８）。そして、処理はＳ２０３に遷移し、新たなローカルパリティの組み合わせが選択される。
【０１１８】
Ｓ２０４において、組み合わせが存在しないと判定した場合（Ｓ２０４でＹｅｓ）、復元部３２は、組み合わせの候補が存在するか否かを判定する（Ｓ２０９）（図１１参照）。ここで、組み合わせの候補は、Ｓ２０８で設定される組み合わせである。組み合わせの候補が存在すると判定した場合（Ｓ２０９でＹｅｓ）、復元部３２は、組み合わせの候補を用いて、連立一次方程式を解くことにより、データディスクを復旧する（Ｓ２１０）。具体的には、復元部３２は、組み合わせの候補のローカルパリティのデータと、組み合わせの候補のローカルパリティの計算範囲に含まれるデータディスクのデータとを取得する。ただし、故障したデータディスクは取得の対象外とする。そして復元部３２は、取得したローカルパリティのデータと、そのローカルパリティの計算範囲に含まれるデータディスクのデータとを用いて、パリティ計算式を使用して連立一次方程式を解くことによって故障したデータディスクのデータを復元する。そして処理は正常終了する。
【０１１９】
Ｓ２０９において、組み合わせの候補が存在しないと判定された場合（Ｓ２０９でＮｏ）、故障したデータディスクの復元ができないので、処理は異常終了する。
【０１２０】
次に、実施形態１〜５の利点の理解を助けるため、比較例１と比較例２について説明する。
【０１２１】
図１２は、比較例１のデータ構成の一例を示す。比較例１の分散ストレージにおいては、冗長化する全てのディスクのデータを用いて、パリティ情報が算出される。すなわち、図１２において、パリティディスク（グローバルパリティ）Ｇ１〜Ｇ６は、計算範囲にすべてのデータディスクを含んで構成される。
【０１２２】
図１３は、比較例２のデータ構成の一例を示す。比較例２の分散ストレージにおいては、一部ローカルパリティを用いて、パリティ情報が算出される。すなわち、図１３の例において、パリティディスク（グローバルパリティ）Ｇ１〜Ｇ４は、計算範囲にすべてのデータディスクを含み、ローカルパリティＬ１とＬ２は、計算範囲に互いに排他的なデータディスクを含んで構成される。ここで、比較例２においては、ローカルパリティＬ１とＬ２は、計算範囲に、共通するデータディスクを含んでいない。
【０１２３】
図１４は、本実施形態と比較例との性能比較を示す図である。図１４において、比較例１(10,6)のレコードは、図１２の構成のように、１０個のデータディスクと、６個のパリティディスクを含む比較例１の性能情報を示している。比較例２(10,6,5)のレコードは、図１３の構成のように、１０個のデータディスクと６個のパリティディスクを含み、ローカルパリティの計算範囲に含まれるデータディスクの数は５個である比較例２の性能情報を示している。実施形態５(10,6,5)のレコードは、１０個のデータディスクと６個のパリティディスクを含み、ローカルパリティの計算範囲に含まれるデータディスクの数は５個である実施形態５の性能情報を示している。尚、実施形態５(10,6,5)のパリティディスクの計算範囲は、実施形態４のように計算範囲の開始位置が均等に分散されているものとする。レプリケーション(10 x 3)のレコードは、データディスクが３重にレプリケーション（複製）された構成の情報処理システムの性能情報を示している。
【０１２４】
容量効率は、ディスクアレイで使用されるすべてのディスク容量から冗長データを引いた、実際に利用可能なディスク容量を示す。容量効率は、比較例１(10,6)、比較例２(10,6,5)、実施形態５(10,6,5)、レプリケーション(10 x 3)はそれぞれ、0.625、0.625、0.625、0.33となる。
【０１２５】
データディスク間の最小ハミング距離は、データディスクのみが故障した場合を対象とした最小ハミング距離の値を示す。データディスク間の最小ハミング距離は、比較例１(10,6)、比較例２(10,6,5)、実施形態５(10,6,5)はそれぞれ、7、7、7となる。
【０１２６】
全ディスク間の最小ハミング距離は、パリティディスク（ローカルパリティ）を含めたすべてのディスクが故障した場合を対象とした最小ハミング距離の値を示す。全ディスク間の最小ハミング距離は、比較例１(10,6)、比較例２(10,6,5)、実施形態５(10,6,5)、レプリケーション(10 x 3)はそれぞれ、7、6、4、3となる。
【０１２７】
書込み処理のオーバヘッドは、データディスクの１つのブロックに書き込み処理が発生した場合の、入出力数（読み込み及び書込み処理の数）の値を示す。比較例１(10,6)の場合、更新したいブロックのデータと、全てのパリティディスクＧ１〜Ｇ６のデータの読み込み及び書込みが発生するため、書込み処理のオーバヘッドは14となる。比較例２(10,6,5)の場合、更新したいブロックのデータとＧ１〜Ｇ４の5つと、Ｌ１またはＬ２のいずれかのデータの読み込み及び書込みが発生するため、書込み処理のオーバヘッドは12となる。実施形態５(10,6,5)の場合、更新したいブロックのデータとローカルパリティＬ１〜Ｌ６のうちのいずれか3つのデータの読み込み及び書込みが発生するため、書込み処理のオーバヘッドは8となる。レプリケーション(10 x 3)の場合、全てのデータディスクに書き込みが発生するため、書込み処理のオーバヘッドは3となる。よって、実施形態５では、比較例１、比較例２と比較すると、書込みオーバヘッドを削減することができる。
【０１２８】
一重障害時のリカバリオーバヘッドは、一重障害が発生した際の復旧オーバヘッドの値を示す。ここで復旧オーバヘッドは、故障したディスクを管理する管理サーバが復旧時に受信するデータ転送量である。比較例１(10,6)の場合、何れかのパリティディスクと、故障していない9つのデータディスクの読み込みが発生するため、一重障害時のリカバリオーバヘッドは10となる。比較例２(10,6,5)の場合、何れかのローカルパリティと、ローカルパリティの計算範囲に含まれる故障していない4つのデータディスクの読み込みが発生するため、一重障害時のリカバリオーバヘッドは5となる。実施形態５(10,6,5)の場合、故障したデータディスクを計算範囲に含む何れかのローカルパリティと、ローカルパリティに含まれる故障していない4つのデータディスクの読み込みが発生するため、一重障害時のリカバリオーバヘッドは5になる。レプリケーション(10 x 3)の場合、正常なディスクの読み込みが発生するため、一重障害時のリカバリオーバヘッドは1になる。よって、実施形態５では、比較例１と比較すると、一重障害時のリカバリオーバヘッドを削減することができる。
【０１２９】
同様に、二重障害時のリカバリオーバヘッドの値は、比較例１(10,6)、比較例２(10,6,5)、実施形態５(10,6,5)、レプリケーション(10 x 3)はそれぞれ、11、10または11、７または8（平均で7.36）、2となる。よって、実施形態５では、比較例１、比較例２と比較すると、二重障害時のリカバリオーバヘッドを削減することができる。
【０１３０】
同様に、三重障害時のリカバリオーバヘッドは、二重障害時のリカバリオーバヘッドの値は、比較例１(10,6)、比較例２(10,6,5)、実施形態５(10,6,5)はそれぞれ、12、12、9となる。尚、三重障害時レプリケーション(10 x 3)においては、データの復旧は不可能である。よって、実施形態５では、比較例１、比較例２と比較すると、三重障害時のリカバリオーバヘッドを削減することができる。
【０１３１】
scrub処理のオーバヘッドは、データ整合性（完全性）をチェックする処理において発生するデータ転送量である。scrub処理のオーバヘッドは、比較例１(10,6)、比較例２(10,6,5)、実施形態５(10,6,5)、レプリケーション(10 x 3)はそれぞれ、15、15、15、20となる。
【０１３２】
図１４に示すように、実施形態５は、全ての項目で最悪値がなく、バランスがとれている。
【０１３３】
尚、本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【０１３４】
１      ストレージシステム
２      データディスク
３      パリティディスク
４      復元部
２１      クライアントサーバ
２２      管理サーバ
２３      ディスク
３１      制御部
３２      復元部
３３      パリティ生成部
３４      記憶部
【図１】
2015082150.tif 000003
【図２】
2015082150.tif 000004
【図３】
2015082150.tif 000005
【図４】
2015082150.tif 000006
【図５】
2015082150.tif 000007
【図６】
2015082150.tif 000008
【図７】
2015082150.tif 000009
【図８】
2015082150.tif 000010
【図９】
2015082150.tif 000011
【図１０】
2015082150.tif 000012
【図１１】
2015082150.tif 000013
【図１２】
2015082150.tif 000014
【図１３】
2015082150.tif 000015
【図１４】
2015082150.tif 000016
【手続補正書】
【提出日】平成26年10月20日(2014.10.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７
【補正方法】変更
【補正の内容】
【請求項７】
前記復元部は、すべての前記故障したデータディスクが、選択する何れかのパリティディスクに対応する前記ディスクグループに含まれ、且つ、選択する全てのパリティディスクに対応する前記ディスクグループに１以上の前記故障したデータディスクを含むように、前記故障したデータディスクの数と等しい数のパリティディスクを選択し、選択した前記パリティディスクに基づいて、前記故障したデータディスクのデータを復元する
ことを特徴とする請求項６項に記載のストレージシステム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
しかしながら、一部のパリティを一部のディスクから計算するようにパリティが配置されたシステムにおいては、ディスクの多重障害に対応した、適切なパリティの配置がなされていない。この場合、ディスクが多重障害を起こした場合はグローバルパリティ（全てのディスクのデータを使って計算するパリティ）を使って復旧する必要がある。また、データディスク数と同じ数のディスクから故障したディスクを管理するノードにデータを転送しなければならない。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
以下の説明では、ディスクアレイに含まれる全ディスクの数をn、データディスク数をk、ローカルパリティのディスク数をp=n-kとすると、k=10、p=6の場合を説明する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
一方Ｓ１０５において、計算範囲に故障したデータディスクを全く含まないローカルパリティが存在しない場合（Ｓ１０５でＮｏ）、復元部３２は、故障したデータディスクが、選択した組み合わせのどのローカルパリティの計算範囲にも含まれないか否かを判定する（Ｓ１０６）。故障したデータディスクのいずれかが、選択した組み合わせのどのローカルパリティの計算範囲にも含まれないと判定された場合（Ｓ１０６でＹｅｓ）、処理はＳ１０３に遷移し、新たなローカルパリティの組み合わせが選択される。