(57)【要約】【課題】分散ストレージシステムにおいて、冗長構成により高い信頼性を確保しつつ、冗長構成によるデータ転送速度の増大を回避して高速なデータ読み出しを可能とすること。【解決手段】複数のストレージへのデータ保存の際に、二重の冗長化を行ったデータを保存することで高い信頼性を確保し、複数のストレージからのデータ読み出しの際には、通常はいずれか一方の冗長データが揃った時点で残りのデータの転送を待たずに、到着している冗長データを元にすべてのデータの復元を行い、データ読み出しを完了させることでデータ読み出しを高速化する。【選択図】  図５
2004192483.tif 000002
【特許請求の範囲】
【請求項１】
１つのデータを複数のストレージに分割して保存する分散ストレージシステムの管理方法であって、保存対象のデータを分割する際に各ストレージに保存する分割データにそれぞれエラー訂正のための第１の冗長データを付加し、さらに各分割データの対応するビット同士の複数ストレージに跨る方向の各組に対してそれぞれエラー訂正のための第２の冗長データを付加し、これらを複数ストレージに分割して保存し、前記保存対処データを復元する際に、該複数ストレージからデータを転送し、１つを除くすべてのストレージからの分割データが到着した時点で、前記エラー訂正のための第２の冗長データにより、残り１つのストレージから転送されるデータを復元し、分割データを結合することにより該データの転送を完了させることを特徴とする分差ストレージシステムの管理方法。
【請求項２】
前記複数ストレージからのデータ転送で復元すべき残り１つのストレージから転送されるデータが前記エラー訂正のための第２の冗長データのみである場合に、該データの復元を行わずに、転送済みの分割データを結合することによりデータの転送を完了させることを特徴とする請求項１に記載の分散ストレージシステムの管理方法。
【請求項３】
前記複数ストレージへのデータ保存時に、１つのストレージへのデータ保存のみを遅延させることを特徴とする請求項１に記載のストレージシステムソフトウェア。
【請求項４】
前記複数ストレージからのデータ転送で１つを除くすべてのストレージからの分割データが到着した時点で、残りの１つのストレージに対してデータの転送を中止する通知を行うことを特徴とする請求項１に記載の分散ストレージシステムの管理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、分散ストレージシステムに関し、各ストレージの信頼性確保および分散ストレージシステム全体での信頼性確保の双方を実現するために二重に冗長化したデータを保存する分散ストレージシステムの管理方式に関する。
【０００２】
【従来の技術】
複数のストレージからなるストレージシステムとしては、ディスクアレイ装置があるが、ディスクアレイ装置では、複数のストレージでグループを作り、そのグループに対するパリティを別のストレージに保存する冗長構成をとることで、そのグループ内の一部のストレージに故障などの障害が発生した際にそのストレージシステムに保存されていたデータの回復を可能とする方式が広く知られている。また、そのような冗長構成をより高信頼なものとする技術として、特許文献１には二重の冗長データを保存することで、冗長データを作成する元のデータを保持する複数のストレージで構成されるグループ内に同時に複数の障害が発生した際にもより高い確率でデータの回復を可能とする技術が開示されている。このような冗長構成をとったディスクアレイ装置では、データの読み出しの際に、元のデータの読み出しに加えて冗長データの読み出しと、読み出したデータの正当性の確認が必要であり、冗長構成としない場合に比べて読み出し処理に要する時間が増加する。しかし通常の場合、ディスクアレイ装置では、複数のストレージと、それらストレージとの間でデータの送受信を行うコントローラ部とは均一かつ密に結合されており、複数のストレージからコントローラへのデータ転送においては、いずれのストレージからの転送時間もほぼ同一となる。よって、ストレージとコントローラ間のデータ転送のための通信路が十分に用意されていれば、冗長構成による処理時間の増大は、ほぼデータの正当性を確認するのに要する時間となる。
一方、複数のストレージを別々の場所に設置し、それらをまとめて１つのストレージシステムとする分散ストレージシステムにおいても、ディスクアレイ装置と同様に冗長構成をとることが普通である。ところが、分散ストレージシステムでは、複数のストレージと、それらストレージとの間でデータの送受信を行うコントローラ部とはかならずしも均一かつ密に結合されているわけではない。特に分散ストレージシステム専用の通信路ではなく、インターネットなどの通信路を使用する場合には、データ転送に要する時間や、転送バンド幅に複数のストレージ間で大きな差が出ることがある。そのため、より高い信頼性をもたせた冗長構成をとった場合、ディスクアレイ装置の場合と異なり、複数ストレージからコントローラへのデータ転送に要する時間のばらつきによりデータ読み出しに要する時間が更に増大する。これは、データの読み出しがすべての複数ストレージからのデータが揃わなければ完了しないために、複数ストレージの中でコントローラへのデータ転送に要する時間が最大のものによって転送時間が決定されるためである。
【０００３】
【発明が解決しようとする課題】
本発明は、冗長データによる正当性の確認のために読み出し時間増加することに加えて、分散ストレージシステム特有の個々のストレージ装置からのデータ転送時間のばらつきによりデータ読み出し時間がますます増加するという上記の問題を解決するものである。別の言葉で言えば、保存データを冗長構成にすることによるデータの信頼性は保ったままでデータの読み出し時間の増大を押さえて、高速にデータ読み出しを行うことの可能な分散ストレージを提供することが本発明の一つの目的である。
【０００４】
【課題を解決するための手段】
本発明で開示される代表的実施例の特徴は、複数のストレージへのデータ保存の際に、各ストレージ内の方向と、複数ストレージに跨る方向とに二重の冗長化を行ったデータを保存し、複数のストレージからのデータ読み出しの際には、１つのストレージを除く残りのストレージからデータが揃った時点で残りのデータの転送を待たずに複数ストレージに跨る方向の冗長データを用いてデータの復元を行い、データ読み出しを完了することにある。
他の特徴は発明の実施の形態の項で明らかにされる。
【０００５】
【発明の実施の形態】
図１に実施例の全体構成を示す。分散ストレージシステム６は、複数のストレージ装置５とストレージコントローラ３およびその間を接続する通信路４で構成される。このストレージシステム６はサーバコンピュータもしくはクライアントコンピュータ１などと通信路２で結合される。サーバ／クライアントコンピュータ１からの要求に応じてストレージコントローラ３はストレージ装置５にデータの保存およびストレージ装置５からのデータの読み出しを行う。本発明に特徴的なデータの保存方法および読み出しに方法は、ストレージコントローラが行うデータ処理で実現される。。
図２は、本実施例における分散ストレージへのデータ保存時のストレージコントローラ内での処理フローである。
最初に分散ストレージシステムに保存するデータを転送サイズなどの固定的な処理単位に分割する（ステップ１１）。
そして、ストレージコントローラは、その固定的なサイズのデータを保存するストレージの数に応じてデータの分割を行う。この際に、保存先のストレージ数がＮ＋１個の場合、データはＮ個に分割する。これら分割されたＮ個のデータを分割データと呼ぶ（ステップ１２）。
次にＮ個の分割データそれぞれにエラー訂正のための冗長データを付加する。この冗長データにより、個々の分割データに対するエラー訂正を可能とし、ストレージや通信路におけるエラーから元の分割データを復元することを可能とする（ステップ１３）。
上記で生成されたＮ個の冗長データ付きの分割データに対し、それらＮ個のデータ間でのエラー訂正のための冗長データを生成する（ステップ１４）。これを冗長分割データと呼ぶ。この冗長分割データは、Ｎ個の冗長データ付きの分割データの内の１つが欠けた場合にも、その欠けた１つの冗長データ付きの分割データを復元できるものとする。
最後に、上記までに生成されたＮ個の分割データと１個の冗長分割データの合計Ｎ＋１個のデータＮ＋１個のストレージに転送して保存を行う（ステップ１５）。
図３は図２で説明した本実施例の分散ストレージへのデータ保存時のストレージコントローラ内での処理を６４Ｂｙｔｅのサイズのデータを例に模式的に示した図である。図３の例では、ストレージの数が９個であるので、６４Ｂｙｔｅのデータ２１を８分割して、１つの分割データが８Ｂｙｔｅとする。次に、８個の８Ｂｙｔｅ分割データ２２に対して、１ビットエラー    を訂正する能力のある１ＢｙｔｅのＥＣＣ符号２３を冗長データとして付加し、合計９Ｂｙｔｅの冗長データ付きの分割データとする。そして、これら８個の９Ｂｙｔｅ冗長データ付きの分割データそれぞれのビットごとにパリティ２４を生成する。例えば、先頭ビット８つ（図３ではｂｉｔ０、６４，１２８，１９２，２５６，３２０，３８４，４４８）に対するパリティビット（図３ではＰａｒｉ.０）として１ビットを生成する。パリティビットの集合はＥＣＣ付きの分割データ９Ｂｙｔｅと同じサイズの９Ｂｙｔｅとなる。上記処理により、９Ｂｙｔｅのデータが９個生成され、これら９個のデータを９個のストレージそれぞれに転送して保存する。なお、９個のストレージへのデータ転送の内、１個のストレージへのデータ転送については、他の８個のストレージへのデータ転送に比べて遅延して行ってもよい。これは、８個のストレージからのデータが揃うことにより、元のデータが復元できるためであり、これによりストレージコントローラとストレージ間の通信路が混雑している場合や、他に優先すべきデータ転送がある場合、保存先のストレージが一時的に混雑もしくは停止している場合にもデータの保存を行うことができる。
図４は、本実施例の分散ストレージからのデータ読み出し時のストレージコントローラ内での処理フローである。
最初に各ストレージから分割されて保存されていたデータをそれぞれ読み出して転送し、それぞれの冗長データにより分割データの正当性の確認を行う。転送されてきた分割データにエラーがある場合には、冗長データによりエラー訂正を行う。この処理は各分散ストレージ毎に行えるため並列に実行可能である。（ステップ３１）
次に各ストレージからのデータをまとめるが、１つを除くすべてのストレージからのデータが揃った時点で、残りの１つのデータを保存時に付加した冗長データにより復元する（ステップ３２）。つまり、Ｎ＋１個のストレージに分割して保存されていたデータを読み出す場合には、Ｎ個のストレージからのデータについて、前述のステップ３１で述べたデータの正当性の確認もしくはエラー訂正が完了した時点で、残り１つのストレージから読み出されるべきデータを復元する。最初に揃ったＮ個のストレージからのデータが、すべて保存時に分割・生成されたＮ個の冗長データ付きの分割データである場合には、残り１つのストレージからのデータは冗長分割データであるので、復元する必要はない。一方、最初に揃ったＮ個のストレージからのデータが、保存時に分割・生成されたＮ−１個の冗長データ付きの分割データと１個の冗長分割データであった場合には、１個の冗長データ付きの分割データの復元が必要である。冗長分割データはＮ−１個の冗長データ付きの分割データから残り１個の冗長データ付きの分割データを復元できる能力をもったものとして、保存時に生成されているので、これにより残り１個の冗長データ付きの分割データを復元することができる。
最後に冗長分割データを除くＮ個の冗長データ付きの分割データを結合して元データを復元する（ステップ３３）。図５は図４で説明した実施例の分散ストレージからのデータ読み出し時のストレージコントローラ内での処理を６４Ｂｙｔｅのサイズのデータを例に模式的に示した図である。この例は、図３に示した方法で保存された６４Ｂｙｔｅのデータを読み出す場合の処理を示している。図３と同様に図５の例では、９個のストレージ（４１，４２）において、８個のストレージ（ストレージ＃１〜＃８）には９Ｂｙｔｅの冗長データ付き分割データ、１個のストレージ（ストレージ＃９）には９Ｂｙｔｅの冗長分割データが保存されている。この中で、図５ではストレージ＃２から読み出されるｂｉｔ６４〜ｂｉｔ１２７＋ＥＣＣ０〜ＥＣＣ７の９Ｂｙｔｅのデータに１ビットのビットエラー（４５）が起こったとする。このビットエラー（４５）は、ストレージ＃２からの９Ｂｙｔｅのデータに含まれる１ＢｙｔｅのＥＣＣデータによりエラー訂正が行われ、正しいデータに復元できる。次に、ストレージ＃６（４１）からのデータはストレージ障害や通信遅延などの理由によりストレージコントローラ４８への到着が遅れているため、ストレージコントローラ４８内の待ち合わせバッファ（４７）にストレージ＃６（４１）を除くすべてのストレージからのデータが到着したとする。そこで、ストレージコントローラ４８内では揃った８つの９Ｂｙｔｅデータからストレージ＃６（４１）から読み出されるべきデータを復元する。次に、復元されたストレージ＃６（４１）からのデータを含め、ストレージ＃１〜ストレージ＃８に保存されていた元データを分割した８Ｂｙｔｅの分割データを結合して６４Ｂｙｔｅの元データ（４９）が復元される。以上が本発明による分散ストレージシステムにおけるデータの読み出し処理の例である。また、ストレージ＃６（４１）に対しては、上記方法によりデータの復元が可能となった時点で読み出し処理を中止してよいことを通知することにより、ストレージ＃６（４１）とストレージコントローラ（４８）間の通信路のデータ転送を低減させることが可能である。
図６にストレージ＃６（５１）のデータの詳細な復元方法の例を示す。ストレージ＃６（５１）から読み出されるデータの先頭ビット（ｂｉｔ３２０）の復元を例に説明する。ストレージ＃１〜ストレージ＃５およびストレージ＃７〜ストレージ＃９（５２）の先頭ビットにおいて、図６の例では、ストレージ＃９（５２）のビットＰａｒｉ．０（５３）がパリティビットである。よって、ストレージ＃１〜ストレージ＃８（５１，５２）の先頭ビットのパリティが、Ｐａｒｉ．０（５３）とならなければならない。図６の例では、ストレージ＃６（５１）を除くストレージ＃１〜ストレージ＃８の先頭ビット（ｂｉｔ０，ｂｉｔ６４，ｂｉｔ１２８，ｂｉｔ１９２，ｂｉｔ２５６，ｂｉｔ３８４，ｂｉｔ４４８）が１，０，０，０，０，０，０で、Ｐａｒｉ．０（５３）が１であるので、残りのストレージ＃６（５１）からのｂｉｔ３２０（５４）は０と補完される。同様の処理を後続のビットに関しても繰り返すことによりストレージ＃６（５１）からのデータをすべて復元することができる。
図７に本発明による効果を示す。図７の例では、Ｎ＋１個のストレージからデータを読み出す場合に、右方向を時間として、読み出し・転送にかかる時間を棒グラフの長さで示している。つまり、ストレージ＃１からの読み出し・転送にかかる時間が最も長く、ストレージ＃２からの読み出し・転送にかかる時間が二番目に長いとする。この場合に、従来方式では全ストレージからの転送が完了した後にデータチェックを行い、すべてのデータ読み出し処理が終了するので、処理時間はＴ２となる。一方、本発明の方式では、最も遅いストレージ＃１からのデータを待たずにＮ個のストレージからのデータが揃った時点、つまりストレージ＃２からのデータが到着した時点でデータの復元およびデータのチェックを行い、すべてのデータ読み出し処理が終了するので、処理時間はＴ１となる。よって、読み出し処理の短縮時間（Ｔ２−Ｔ１）が本発明による効果である。
できるだけ広げ、他社製品・他社方式への応用についても記載する。
（４）発明の創作検討段階で考えたことは、たとえ当社が採用しないもの   であっても記載する。
（例）
以下、本発明の実施例を図ｎにより説明する。
（以下、実施例の構成及び動作の説明）
……本実施例によれば……の効果がある。
【０００６】
【発明の効果】
本発明の効果は、複数のストレージからなるストレージシステムにおいて、冗長構成をとった場合のデータ読み出し時間の増大が、例えば各ストレージが別々の場所に設置されており各ストレージとコントローラ間の通信路が不均一もしくは疎である分散ストレージシステムなどのように、複数ストレージからのデータ転送時間によって影響を受ける場合に、複数のストレージへのデータ保存の際に、二重の冗長化を行ったデータを保存しておき、複数のストレージからのデータ読み出しの際には、いずれか一方の冗長データが揃った時点で残りのデータの転送を待たずにデータの復元を行い、データ読み出しを完了することにより、冗長度は保ったままでデータの読み出し時間の増大を押さえて、高速にデータ読み出しを行うことを実現可能とする点である。
【図面の簡単な説明】
【図１】本発明が対象とする分散ストレージシステムの構成図。
【図２】本発明による分散ストレージシステムへのデータ保存の処理フローを示した図。
【図３】本発明による分散ストレージシステムへのデータ保存の処理内容を示す図。
【図４】本発明による分散ストレージシステムからのデータ読み出しの処理フローを示した図。
【図５】本発明による分散ストレージシステムからのデータ読み出しの処理内容を示す図。
【図６】本発明による分散ストレージ間でのデータ補完方法を模式的に示した図。
【図７】本発明による分散ストレージシステムによるデータ読み出し時間の短縮効果を模式的に示した図。
【符号の説明】
１：サーバ/クライアントコンピュータ、
２：コンピュータとストレージシステムを結ぶ通信路、
３，４８：ストレージコントローラ、
４：分散ストレージ間を結ぶ通信路、
５，２５，４２，５２：ストレージ、
６：分散ストレージシステム、
１１〜１５： データ保存処理における処理内容、
２１，４９：元データ、
２２：分割された元データ、
２３，４６：分割された元データのエラー訂正符号、
２４，４３，５３：分割された元データ間のパリティ符号、
３１〜３３：データ読み出し処理における処理内容、
４１，５１：ストレージ障害もしくは通信遅延を起こしたストレージ、
４４，５４：ストレージ障害もしくは通信遅延を起こしたストレージに保存されているデータ、
４５：ビットエラー、
４７：分割データ待ち合わせバッファ。
【図１】
2004192483.tif 000003
【図２】
2004192483.tif 000004
【図３】
2004192483.tif 000005
【図４】
2004192483.tif 000006
【図５】
2004192483.tif 000007
【図６】
2004192483.tif 000008
【図７】
2004192483.tif 000009