(57)【要約】本発明の種々の実施形態は、複数の記憶装置（ディスク）上のデータにアクセスする複数のクライアントを代表して動作するストレージサーバによって実施されるＩ／Ｏオペレーションを最適化するための方法、システム、及びコンピュータ製品を提供する。本発明の種々の実施形態によれば、新たなデータが書き込まれることになる物理データブロックをゼロ化することによって、新たなデータを物理データブロックに書き込むための特定の読み出し処理の必要性を無くす。さらに、新たなパリティを計算するための古いパリティの読み出しの必要性も無くなる。代わりに、新たなパリティは、古いパリティや、ストレージサーバからパリティを記憶するディスクへコマンドを送信することを必要とせずに、書き込まれるデータから計算される。パリティを記憶するディスクにて実施されるモジュールは、ストレージサーバにより古いパリティを読み出すことなく、そのコマンドを実行する。古いデータや古いパリティを読み出す必要性を無くすことにより、回転遅延が幾らか無くなり、システムの全体的処理能力が向上する。【選択図】図２
2010508604.tif 000002
【特許請求の範囲】
【請求項１】
ゼロ化コマンドを発行することにより、複数の記憶装置に対してゼロ化プロセスを開始するように構成されたゼロ化モジュールと、
前記ゼロ化モジュールに結合され、前記コマンドによって特定される空きの物理データブロックをゼロ値とみなすことにより、前記ゼロ化コマンドを実行するように構成されたストレージモジュールとを含み、
前記ストレージモジュールは、書き込み命令、及び関連データを含むクライアントからのアクセス要求に応答し、前記空きの物理データブロックにアクセスし、前記データが書き込まれることになるゼロ化された物理データブロックを読み出すことなく、前記データを前記空きの物理データブロックに書き込むように構成される、ストレージサーバ。
【請求項２】
パリティを記憶する記憶装置に対し、前記物理データブロックに書き込まれたデータに対応する新たなパリティを計算するためのコマンドを発行するように構成された最適化モジュールと、
前記複数の記憶装置のそれぞれにおいて実施され、前記データが前記物理データブロックに書き込まれる前の前記物理データブロックに関連するパリティを前記ストレージモジュールにより読み出すことなく、前記物理データブロックに書き込まれるデータに対応する新たなパリティを計算するように構成されたコマンド実行モジュールとさらに含む、請求項１に記載のストレージサーバ。
【請求項３】
前記ゼロ化モジュール、及び前記ストレージモジュールはそれぞれ、前記ストレージサーバの一、又は複数のプロセッサにおいて実行されるプログラムコードを含む、請求項１に記載のストレージサーバ。
【請求項４】
前記コマンド実行モジュールは、前記記憶装置の一、又は複数のコントローラにおいて実行されるプログラムコードを含む、請求項２に記載のストレージサーバ。
【請求項５】
前記コマンド実行モジュールは、
前記ストレージサーバから、物理データブロックに書き込むべき新たなデータを受信し、
前記物理データブロックに関連する行パリティを読み出し、
前記行パリティ、及び前記物理データブロックに書き込まれる新たなデータに対し、排他的論理和（ＸＯＲ）演算を実施するようにさらに構成される、請求項２に記載のストレージサーバ。
【請求項６】
どのデータブロックが空いているかを示す第１のデータ構造、及びどのデータブロックがゼロ値であるものとみなされるかを示す第２のデータ構造を記憶するように構成されたメモリをさらに含む、請求項１に記載のストレージサーバ。
【請求項７】
前記空きの物理データブロックはデータを記憶しない、請求項１に記載のストレージサーバ。
【請求項８】
前記パリティは行パリティである、請求項２に記載のストレージサーバ。
【請求項９】
前記パリティは対角パリティである、請求項２に記載のストレージサーバ。
【請求項１０】
複数のクライアントによるアクセス要求に応答してストレージサーバによって実施されるＩ／Ｏオペレーションを最適化する方法であって、
ゼロ化モジュールによって、複数の記憶装置における空きの物理データブロックをゼロ値とみなすためのゼロ化コマンドを発行するステップと、
ストレージモジュールによって、前記コマンドにより特定される物理データブロックをゼロ値であるものとみなすことにより、前記ゼロ化コマンドを実行するステップと、
書き込み命令、及び関連データを含むアクセス要求をクライアントから受信するステップと
前記データが書き込まれるゼロ化された物理データブロックを読み出すことなく、前記記憶装置の前記物理データブロックに前記データを書き込むステップとを含む方法。
【請求項１１】
前記ストレージサーバによって、パリティを記憶する記憶装置に対し、データを記憶する前記記憶装置の前記物理データブロックに書き込まれる前記データに対応する新たなパリティを計算するためのコマンドを発行するステップと、
パリティを記憶する前記記憶装置において実施される前記コマンド実行モジュールによって、前記物理データブロックに書き込まれるデータブロックに対応する新たなパリティを計算するステップと
をさらに含み、前記パリティは、前記データが前記物理データブロックに書き込まれる前の前記物理データブロックに関連するパリティを前記ストレージサーバにより読み出すことなく計算される、請求項１０に記載の方法。
【請求項１２】
前記新たなパリティを計算するステップは、前記データが前記物理データブロックに書き込まれる前の前記物理データブロックに関連するパリティ、及び前記物理データブロックに書き込まれるデータに対して排他的論理和（ＸＯＲ）演算を実施することを含む、請求項１１に記載の方法。
【請求項１３】
クライアントから受信した、故障した記憶装置にデータを書き込むための要求に応答し、ストレージサーバによって実施されるＩ／Ｏオペレーションを最適化する方法であって、
ゼロ化モジュールによって、複数の記憶装置における空きの物理データブロックをゼロ値とみなすためのゼロ化コマンドを発行するステップと、
ストレージモジュールによって、前記コマンドにより特定される物理データブロックをゼロ値であるものとみなすことにより、前記ゼロ化コマンドを実行するステップと、
故障した記憶装置にデータを書き込むため、書き込み命令、及び関連データを含む要求を、クライアントから受信するステップと、
記憶装置のコマンド実行モジュールによって、コマンドを受信し、ゼロ化されたデータブロック以外の物理データブロックを前記ストレージモジュールにより読み出すことなく、前記データに対応する新たなパリティを計算するステップと
を含む方法。
【請求項１４】
クライアントから受信した、複数の記憶装置に新たなデータを書き込むための要求に応答し、ストレージサーバによって実施されるＩ／Ｏオペレーションを最適化する方法であって、
ストレージサーバによって、新たなデータが書き込まれることになる物理データブロックに記憶されているデータおｗメモリに読み出すステップと、
前記新たなデータに関連する新たなパリティを計算するためのコマンドを、パリティを記憶する記憶装置へ送信するステップと、
パリティを記憶する記憶装置におけるモジュールによって、前記メモリから、新たなデータが書き込まれることになるデータブロックに記憶されているデータを読み出し、さらに、行パリティブロックから、記憶されたデータに関連する古いパリティを読み出すことにより、コマンドを実行するステップと、
前記ストレージサーバによって前記物理データブロックから古いパリティを読み出すことなく、前記コマンド実行モジュールによって、新たなパリティを計算するステップと
を含む方法。
【請求項１５】
複数の記憶装置を備え、そのうちの一つに故障があるシステムにおいて、メディアエラーを有する記憶装置に記憶されたデータを読み出す方法であって、
ゼロ化モジュールによって、複数の記憶装置における空きの物理データブロックをゼロ値とみなすためのコマンドを発行し、故障を有する記憶装置が、ゼロ値を記憶するようにするステップと、
ストレージモジュールによって、前記コマンドにより特定される空きの物理データブロックをゼロ値を有するものとみなすことにより、前記ゼロ化コマンドを実行するステップと、
メディアエラーを有する記憶装置に記憶されているデータを読み出すための要求をクライアントから受信するステップと、
前記記憶装置によって、前記故障した記憶装置からデータを読み出すことなく、メディアエラーを有する記憶装置からデータを読み出すステップと
を含む方法。
【請求項１６】
前記メディアエラーを有する記憶装置からデータを読み出すステップは、
メディアエラーを有する記憶装置以外の記憶装置、及び前記故障した記憶装置からデータを読み出すステップと、
メディアエラーを有する記憶装置に記憶されたデータに関連するパリティを読み出すステップと、
前記記憶装置から読み出されたデータ、及び前記パリティに対し、排他的論理和演算を実施するステップと
をさらに含む、請求項１５に記載の方法。
【請求項１７】
複数のクライアントによるアクセス要求に応答し、ストレージサーバによって実施されるＩ／Ｏオペレーションを最適化するためのコンピュータプログラムコードを有するコンピュータ読取可能媒体を含む、コンピュータプログラム製品であって、前記コンピュータプログラムコードが、
複数の記憶装置における空きの物理データブロックをゼロ値と見なすためのゼロ化コマンドを発行し、
前記コマンドにより特定される物理データブロックをゼロ値とみなすことにより、前記ゼロ化コマンドを実行し、
書き込み命令、及び関連データを含むアクセス要求をクライアントから受信し、
前記データが書き込まれるゼロ化された物理データブロックを読み出すことなく、前記記憶装置の物理データブロックにデータを書き込むように構成される、コンピュータプログラム製品。
【請求項１８】
パリティを記憶する記憶装置に対し、データを記憶する前記記憶装置の前記物理データブロックに書き込まれるデータに対応する新たなパリティを計算するためのコマンドを発行し、
パリティを記憶する記憶装置において実施されるコマンド実行モジュールによって、前記物理データブロックに書き込まれるデータに対応する新たなパリティを計算するようにさらに構成され、
前記パリティは、前記データが前記物理データブロックに書き込まれる前の前記物理データブロックに関連するパリティを前記ストレージサーバによって読み出すことなく計算される、請求項１７に記載のコンピュータプログラム製品。
【請求項１９】
前記データが前記物理データブロックに書き込まれる前の前記物理データブロックに関連するパリティ、及び前記物理データブロックに書き込まれるデータに対し、排他的論理和（ＸＯＲ）演算を実施することにより、新たなパリティを計算するようにさらに構成される、請求項１７に記載のコンピュータプログム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージシステムに関し、詳しくは、データ書き込み処理の最適化に関する。
【背景技術】
【０００２】
ストレージサーバは、入出力（Ｉ／Ｏ）クライアント要求に応答し、一、又は複数のクライアント処理システム（「クライアント」）の代わりに、データを記憶、及び取得するように構成された処理システムである。ストレージサーバは、多種多様な目的に使用される場合があり、例えば複数のユーザに対し、共有データへのアクセスや、データのバックアップを提供することがある。
【０００３】
ストレージサーバの一例はファイルサーバである。ファイルサーバは、一、又は複数のクライアントの代わりに、共有ファイルを一組の磁気ディスク、又は光ディスク、あるいは磁気テープのような大容量記憶装置に記憶し、管理する働きをする。大容量記憶装置は、ＲＡＩＤ（Redundant Array of Independent or Inexpensive Disks）の一、又は複数のボリュームとして編成される場合がある。ストレージサーバの他の例には、記憶されたデータへのファイルレベルアクセスではなくブロックレベルアクセスをクライアントに提供する装置、あるいは、ファイルレベルアクセスとブロックレベルアクセスの両方をクライアントに提供する装置がある。
【０００４】
ストレージサーバでは、時々、例えば、大容量記憶装置の一つが故障したときに、データが破損したり、失われたりすることがある。そのため、近代的なストレージサーバは全て、記憶されたデータを保護するための種々の技術を実施している。現在、そのような技術は、データ保護値（例えば、パリティ）を計算し、パリティを種々の場所に記憶することを必要とする。パリティは、ディスクアレイ中の複数のディスクにわたって広がる１つのストライプ中のデータブロックの排他的論理和（ＸＯＲ）として計算される場合がある。例えばＲＡＩＤ４、又はＲＡＩＤ５のような単一パリティ方式では、ストライプ上の任意のブロックにおける誤りを単一のパリティブロック（「行パリティ」とも呼ばれる）を使用して訂正することが出来る。例えばＲＡＩＤダブルパリティ（ＲＡＩＤ−ＤＰ）のような二重パリティ方式では、カリフォルニア州サニーベイルにあるネットワーク・アプライアンス，インコーポレイテッドが発明した技術により、２台のディスク故障から生じるエラーを２つのパリティブロックを使用して訂正することができる。第１のパリティは、ストライプ中のデータブロックのＸＯＲの結果として計算される行パリティブロックである。第２のパリティは、対角パリティセットにおけるデータブロックの排他的論理和演算（ＸＯＲ）として計算される場合がある。
【０００５】
上記のパリティ保護方式は、データ保護を提供するものの、ディスク上のデータブロックを変更するために、つまり、新たなパリティを計算するために、複数の読み出し処理、及び書き込み処理を実施しなければならない。例えば、あるＲＡＩＤ５方式では、データブロック（複数の場合もあり）を変更するために、パリティブロックを読み出す。さらに、変更されるデータブロックのデータも読み出される。そして、そのパリティブロックとデータブロックに対して、排他的論理和（ＸＯＲ）演算が実施される。新たなパリティを計算するために、先のステップのＸＯＲの結果が、新たなデータとＸＯＲ演算される。新たなデータと新たなパリティは、ディスクに書き込まれる。このように、２回の読み出し処理（パリティブロックの読み出しと、データブロックの読み出し）、及び２回の書き込み処理（新たなデータの書き込みと、新たなパリティの書き込み）が必要になる。このプロセスは、しばしば、「リード・モディファイ・ライト」、又は「パリティ・バイ・サブトラクション・ライト」と呼ばれることがある。予備的な読み出し処理を行うシステムの中には、書き込み処理を実施する前に、記憶装置（例えば、ディスク）が元の位置まで回転して戻るのを待たなければならないシステムもある。従って、データブロックを変更するために複数回の読み出し処理を実施すれば、回転遅延が発生し、回転遅延は、システムの全体的処理能力に影響を与えることになる。
【０００６】
特定の幾つかの読み出し処理の省略を試みる幾つかの既知の解決策がある。ある一つの既知の解決策では、新たなパリティを含めて、１つのストライプ全体を書き込まなければならない。この技術は、「フル・ストライプ・ライト」と呼ばれる。しかしながら、ファイルシステムが古くなるのにつれて、フル・ストライプ・ライトを行うファイルシステムの能力は低下する。
【０００７】
特定の幾つかの読み出し処理を省略するための他の解決策は、新たなデータが書き込まれることになるデータブロックから、データをメモリキャッシュに記憶することである。古いデータは現在キャッシュにあるため、新たなデータを書き込む前に古いデータを読み出す必要はない。ただし、この解決策は、相当な量のメモリキャッシュを必要とするので、あまり効果的ではない場合がある。
【０００８】
従って、複数回の読み出し処理の実施に伴う待ち時間の増加を無くすために、Ｉ／Ｏオペレーションを最適化する方法、及びシステムが必要とされている。
【発明の概要】
【課題を解決するための手段】
【０００９】
本発明の種々の実施形態は、複数のクライアントの代わりに、複数のディスクのような記憶装置上のデータをアクセスし、取得する動作をするストレージサーバによって実施されるＩ／Ｏオペレーションを最適化する方法、システム、及びコンピュータプログラム製品を提供する。本発明の種々の実施形態によれば、ディスク上の空きの物理的データブロックはゼロ化される。クライアントシステムが、新たなデータを書き込むために、ストレージサーバに対してアクセス要求を行うと、ストレージサーバは、その要求を解読し、一、又は複数のディスク上の物理データブロックにデータを書き込むための内部コマンドを発行する。本発明の実施形態によれば、新たなデータが書き込まれる物理的データブロックは既にゼロ化されているので、新たなデータを書き込むときに、それらのデータブロックを読み出す必要は無い。さらに、本発明のの実施形態によれば、一、又は複数の物理的データブロックに変更が加えられたストライプについて、新たなパリティを計算するために、古いパリティを読み出す必要は無い。代わりに、新たなパリティは、書き込まれるデータから完全に計算され、あるいは、ストレージサーバが、新たなデータが書き込まれるストライプに関するパリティを記憶するディスクに対し、コマンド（複数の場合もあり）を発行する。そのディスクのモジュールは、そのコマンド、及び書き込まれる新たなデータ（又は、新たなデータに対するＸＯＲ演算の結果）を受信し、ストレージサーバが、古いパリティを読み出す必要なく、その新たなデータが書き込まれるストライプについて、新たなパリティを計算する。新たなデータが書き込まれる物理的データブロックを読み出す必要を無くすと共に、古いパリティを読み出す必要性を無くすことにより、多少の回転待ち時間が不要になり、ストレージサーバの処理能力は向上する。
【００１０】
また、本発明によれば、ＲＡＩＤ４、又はＲＡＩＤ５においてあるディスクが故障し、他のディスク（そのディスクはメディアエラーを有する）上の一、又は複数のデータブロックからデータを読み出すことが出来ないとき、あるいは二重パリティ方式ＲＡＩＤにおいて２台のドライブが故障し、他のディスク上の一、又は複数のデータブロックからデータを読み出すことが出来ないときにおける、データ保護を向上させることができる。ストレージサーバは、故障したディスクの一つがゼロ値を記憶していることを知っているので、メディアエラーのあるディスクからデータを復元することが出来る。このデータは、通常ならば、ＲＡＩＤ４やＲＡＩＤ５、あるいは二重パリティＲＡＩＤシステムにおいても復元出来ないであろう。
【００１１】
さらに別の実施形態として、ストレージオペレーティングシステムが、データの書き込みのためにライト・イン・プレイス（ＷＩＰＬ）メカニズムを実施するときに、本発明は、書き込み処理を最適化する。すなわち、本発明は、ＷＩＰＬメカニズムを利用するオペレーティングシステムの能力を利用し、古いデータをメモリに読み込み、それをディスク上のどこかに書き込み、古いデータが記憶されたメモリ上のアドレスを指すポインタを生成し、その古いデータをアクセスできるようにする。本発明の一実施形態によれば、古いデータが既に読み込まれているので、新たなパリティを計算するために古いデータを読み出す必要はない。その代わり、データの変更が行われるストライプのパリティを記憶しているディスクに対し、コマンドが送信される。ディスクのモジュールは、古いパリティを読み出し、新たなパリティを計算することによって、ストレージサーバが古いパリティを読み出す必要性を無くす。
【００１２】
本発明は、単一パリティデータ保護方式と、二重パリティデータ保護方式のいずれにおいても、書き込み処理の最適化のために使用することができる。
【００１３】
本発明の他の態様は、本発明の原理を例として示す添付の図面、及び下記の詳細な説明から明らかになるであろう。
【００１４】
本発明の一、又は複数の実施形態は、添付の図面の種々の図において、制限ではなく、例として示される。図中、同じ符号は、同様の要素を指している。
【図面の簡単な説明】
【００１５】
【図１Ａ】ＲＡＩＤ−４によるディスク上のデータブロックの構成を示す図である。
【図１Ｂ】ＲＡＩＤ−５によるディスク上のデータブロックの構成を示す図である。
【図２】本発明の一実施形態によるストレージサーバを含むネットワーク環境を示す図である。
【図３】本発明の一実施形態による、図２に示したストレージサーバのアーキテクチャを示す図である。
【図４】本発明の一実施形態による、図２に示したストレージサーバのストレージオペレーティングシステムを示す図である。
【図５】図４に示したファイルシステムの構成要素を示す図である。
【図６】ディスク上のデータブロックをゼロ化するために、図５に示したゼロ化モジュール、及び図４に示したＲＡＩＤコントローラモジュールによって実施される種々のステップを示すイベント図である。
【図７】本発明の一実施形態による、単一パリティＲＡＩＤシステムにおいて書き込み処理を実施する方法を示すフロー図である。
【図８】ＲＡＩＤ−ＤＰシステムにおける対角集合を例示する図である。
【図９】本発明の一実施形態による、二重パリティＲＡＩＤシステムにおいて書き込み処理を実施する方法を示すフロー図である。
【発明を実施するための形態】
【００１６】
本発明の種々の実施形態によれば、複数のクライアントの代わりに、複数のディスクのような記憶装置上のデータをアクセスし、取得する働きをするストレージサーバによって実施されるＩ／Ｏオペレーションを最適化する方法、システム、及びコンピュータプログラム製品が得られる。本発明の種々の実施形態によれば、ディスク上の空きの物理的データブロックが、ゼロ化される。クライアントシステムが、新たなデータを書き込むために、ストレージサーバに対してアクセス要求を行うと、ストレージサーバは、その要求をデコードし、一、又は複数のディスク上の物理的データブロックにデータを書き込むための内部コマンドを発行する。本発明の実施形態によれば、新たなデータを書き込むときに、新たなデータが書き込まれる物理データブロックが既にゼロ化されているので、それらのデータブロックを読み出す必要性は無くなる。さらに、本発明の実施形態によれば、一、又は複数の物理データブロックに対して変更が加えられるストライプについて、新たなパリティを計算するために、古いパリティを読み出す必要も無くなる。代わりに、ストレージサーバは、新たなデータが書き込まれるストライプのパリティを記憶しているディスクに対し、コマンド（複数の場合もあり）を発行する。そのディスクのモジュールは、そのコマンド、及び書き込むべき新たなデータ（又は、新たなデータに対するＸＯＲ演算の結果）を受信し、ストレージサーバが、古いパリティを読み出す必要なく、新たなデータが書き込まれることになるストライプについて、新たなパリティを計算する。新たなデータが書き込まれる物理データブロックを読み出す必要性を無くすと共に、古いパリティを読み出す必要性を無くすことにより、多少の回転待ち時間を無くすことができ、ストレージサーバの処理能力は向上する。
【００１７】
本発明の他の利点として、劣化モードにおける書き込み能力を向上させることが出来るかもしれない点が挙げられる。さらに、本発明によれば、ＲＡＩＤ−４、又はＲＡＩＤ−５において一台のディスクが故障し、他のディスクにメディアエラーがある状況におけるデータ復旧が可能となり、さらに、二重パリティＲＡＩＤシステムにおいて２台のディスクが故障し、他のディスクにメディアエラーがある状況におけるデータ復旧も可能になる。さらに、本発明によれば、「ライト・イン・プレイス」メソッドをサポートするファイルシステムにおける書き込み能力を最適化することができる。本発明によれば、メモリに読み込まれた古いデータへのポインタを作成することにより、新たなデータが書き込まれるデータブロックから古いデータを読み出す必要性は無くなる。書き込み最適化技術を実施する方法の詳細については、以下に記載される。
【００１８】
実施形態の詳細な説明へ進む前に、下記のような定義を行う。本明細書では、「データブロック」という用語は、システムが、個々のエンティティとして認識し、操作することが可能な任意のデータチャンクを言う。従って、本明細書では、「物理的データブロック」とは、ディスクに書き込まれるデータを記憶するブロックを言い、「パリティブロック」とは、物理データブロックに記憶されたデータを保護するためのパリティを記憶するブロックを言う。
【００１９】
本明細書では、「古いデータ」とは、物理データブロックに現在記憶されているデータを言い、「新たなデータ」とは、データブロックに書き込まれるデータを言う。「古いパリティ」とは、書き込みコマンドが実行される前に、すなわち、新たなデータがデータブロック（複数の場合もあり）に書き込まれる前に計算されたパリティを言う。「新たなパリティ」とは、書き込みコマンドが実行された後に、すなわち、新たなデータがデータブロック（複数の場合もあり）に書き込まれた後に計算されたパリティを言う。「行パリティ」とは、特定ストライプ中のデータブロックの排他的論理和（ＸＯＲ）として計算されるパリティを言う。
【００２０】
次に、図１Ａ、及び図１Ｂを参照すると、これらは、ＲＡＩＤ−４、及びＲＡＩＤ−５による記憶装置上のデータブロックの構成をそれぞれ示している。図１Ａ、及び図１Ｂにおいて、書き込み処理の一部に従ってクライアント（複数の場合もあり）からストレージサーバへ送信され、記憶されるデータは、まず、固定サイズ、例えば４キロバイトの複数のブロックに分割される場合があり、次に、それらが、幾つかのグループに編成され、アレイ内の複数のディスクにわたる「ストライプ」（例えば、ストライプＩ、ストライプIIなど）の中に、幾つかの物理データブロックとして記憶される。行パリティは、例えばストライプ中のデータの排他的論理和（ＸＯＲ）として計算され、ディスクＤ上のパリティ保護ブロックに記憶される場合がある。行パリティの位置は、実施される保護方式やプロトコルのタイプによって異なる場合がある。図１Ａは、例えばＰ（０−２）、Ｐ（３−５）、Ｐ（６−８）、及びＰ（９−１１）のような行パリティが専用ディスク（ディスクＤ）に記憶される、ＲＡＩＤ−４方式を示している。図１Ｂは、行パリティがアレイ内の複数のディスクにわたって分散される、ＲＡＩＤ−５方式を示している。二重パリティ保護方式の詳細については、図８を参照して説明する。
【００２１】
１．システム・アーキテクチャ
上記のように、図２に示すようなストレージサーバでは、特定の幾つかの読み出し処理を省略するメカニズムを実施することがある。図２は、複数のクライアント２１０、ストレージサーバ２００、及びディスクサブシステム２４０を含むネットワーク環境を示している。ストレージサーバ２００は、クライアント２１０の代わりに、ディスク型、又はテープ型の磁気ストレージ、又は光学ストレージのような一組の大容量記憶装置に共有ファイルを記憶し、管理する働きをする。前述のように、ストレージサーバ２００は、クライアント２１０に対し、記憶されたデータに対するブロックレベルアクセス（ファイルレベルアクセスではなく）を提供する装置であることもあれば、ブロックレベルアクセスとファイルレベルアクセスの両方をクライアントに提供する装置であることもある。図２に記載のストレージサーバ２００は、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、又はインターネットのような接続システム２３０を介して、一組のクライアント２１０にローカル接続される。接続システム２３０は、イーサネット(R)ネットワークとして実施される場合もあれば、ファイバ・チャネル（ＦＣ）ネットワークとして実施される場合もある。各クライアント２１０は、ＴＣＰ／ＩＰのような所定のプロトコルに従って個々のデータフレーム、又はデータパケットをやりとりすることにより、接続システム２３０を介してストレージサーバ２００と通信することができる。
【００２２】
各クライアント２１０は、例えば、従来のパーソナル・コンピュータ（ＰＣ）や、ワークステーション等である。ストレージサーバ２００は、クライアント２１０から種々の要求を受信し、要求に応じる。ストレージサーバ２００は、分散アーキテクチャを有することもあり、例えば、ストレージサーバ２００は、独立したＮ−（「ネットワーク」）ブレード、及びＤ−（ディスク）ブレード（図示せず）を有する場合がある。そのような一実施形態において、Ｎブレードは、クライアント２１０との間の通信に使用され、Ｄブレードは、ファイルシステム機能を有し、ディスクサブシステム２４０との間の通信に使用される。Ｎブレード、及びＤブレードは、内部プロトコルを使用して互いに通信する。あるいは、ストレージサーバ２００は、統合アーキテクチャを有することがあり、その場合、ネットワークコンポーネントとデータコンポーネントは、全て単一のボックスに収容され、密接に一体化されることがある。ストレージサーバ２００は更に、切り替え装置を通して他の同様のストレージサーバ（図示せず）に接続される場合があり、それら他のストレージサーバは独自のローカルディスクサブシステムを有する場合がある。このように、全てのディスクサブシステム２４０から、単一のストレージプール、又はクラスタを形成することができ、いずれのファイルサーバのいずれのクライアントも、そうしたストレージプール、又はクラスタにアクセスすることができる。
【００２３】
ディスクサブシステム２４０は、ディスク２５０のような一組の大容量記憶装置を備える。各ディスク２５０は、コントローラ２８０を備え、コントローラ２８０は、コマンド実行モジュール２６０を実施する。コマンド実行モジュール２６０の機能については、後で説明する。従って、好ましい実施形態において、コマンド実行モジュール２６０は、コントローラ２８０のようなハードウェアデバイスに組み込まれたファームウェアとして実施される。他の実施形態として、コマンド実行モジュール２６０は、ディスクメモリ２７０に記憶されるソフトウェアとして実施される場合がある。
【００２４】
図３は、本発明の一実施形態によるストレージサーバ２００のアーキテクチャを示している。ストレージサーバ２００は、バスシステム３２３に接続された一、又は複数のプロセッサ（複数の場合もあり）３２１、及びメモリ３２２を含む。図３に示すバスシステム３２３は、適当なブリッジ、アダプタ、及び／又はコントローラによって接続された、任意の一、又は複数の独立した物理的バス、及び／又はポイント・ツー・ポイント接続を表す。従って、バスシステム３２３としては、例えば、システムバス、周辺機器相互接続（ＰＣＩ）バス、ハイパートランスポート、又はＩＳＡ（Industry Standard Architecture）バス、ＳＣＳＩ（Small Computer System Interface）バス、ユニバーサルシリアルバス（ＵＳＢ）、又は、ＩＥＥＥ（Institute of Electrical and Electronics Engineers）規格１３９４バス（「ファイアワイヤ」とも呼ばれることがある）などが挙げられる。
【００２５】
プロセッサ（複数の場合もあり）３２１は、ストレージサーバ２００の中央演算処理装置（ＣＰＵ）であり、従って、ストレージサーバ２００全体の動作を制御する。実施形態によっては、プロセッサ（複数の場合もあり）３２１は、メモリ３２２に記憶された、本明細書にさらに詳しく記載されるようなソフトウェアを実行することによって、この制御を実現する場合がある。プロセッサ３２１としては、例えば、一、又は複数のプログム可能な汎用の、又は特殊目的のマイクロプロセッサ、デジタル・シグナル・プロセッサ（ＤＳＰ）、プログラマブル・コントローラ、特定用途向け集積回路（ＡＳＩＣ）、プログラマブル・ロジック・デバイス（ＰＬＤ）などが挙げられ、あるいは、それらのデバイスの組み合わせであってもよい。
【００２６】
メモリ３２２は、本発明に関連するソフトウェアプログラムやデータ構造を記憶するために、プロセッサ３２１やアダプタによってアドレス指定可能な複数の記憶場所を有する。そして、プロセッサ３２１、及びアダプタは、ソフトウェアプログラムを実行し、種々のデータ構造を操作するように構成された処理要素、及び／又は論理回路を含む場合がある。メモリ３２２は、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）、又はフラッシュメモリ等であってよく、あるいはそれらのデバイスの組み合わせであってもよい。メモリ３２２は、とりわけ、ストレージサーバ２００のストレージオペレーティングシステム３２４を記憶している。当業者には明らかなように、本明細書に記載する本発明に関係するプログラム命令の記憶、及び実行には、種々のコンピュータ実行可能媒体を含む、他の処理手段、又は他の記憶手段を使用してもよい。
【００２７】
さらに、プロセッサ（複数の場合もあり）３２１には、バスシステム３２３を通して、ストレージアダプタ３２６やネットワークアダプタ３２７も接続される。ストレージアダプタ３２６は、ストレージサーバ２００で実行されるストレージオペレーティングシステム３２４と協働し、ディスク２５０からデータを取得する。ストレージアダプタ３２６は、従来の高性能ファイバチャネル（ＦＣ）リンクトポロジのようなＩ／Ｏ相互接続構成を介してディスク２５０（図２に示す）に接続するための入出力（Ｉ／Ｏ）回路を有する複数のポートを備える。
【００２８】
ネットワークアダプタ３２７は、ポイント・ツー・ポイントリンク、ワイド・エリア・ネットワーク、公衆通信回線上で実施される仮想私設ネットワーク、又は共有ローカル・エリア・ネットワークを介してストレージサーバ２００を一、又は複数のクライアントに接続するように構成された複数のポートを有する。従って、ネットワークアダプタ３２７は、ノードをネットワークに接続するために必要とされる機械的、電気的、及び信号回路を含む場合がある。
【００２９】
２．ストレージ・オペレーティング・システム
図４は、ストレージサーバ２００のストレージオペレーティングシステム３２４の一例を示す。一実施形態として、ストレージオペレーティングシステム３２４は、カリフォルニア州サニーベイルにあるネットワーク・アプライアンス・インコーポレイテッドから入手可能なＮｅｔＡｐｐ  Ｄａｔａ  ＯＮＴＡＰストレージオペレーティングシステムであってもよい。このストレージオペレーティングシステムは、Ｗｒｉｔｅ  Ａｎｙｗｈｅｒｅ  Ｆｉｌｅ  Ｌａｙｏｕｔ（ＷＡＦＬ）ファイルシステムを実施する。ただし、当然ながら、本明細書に記載する原理に従って任意の適当なストレージシステムを使用することが可能である。本明細書では、「ストレージオペレーティングシステム」という用語は一般に、データアクセスを管理するストレージ機能を実施するために、コンピュータ上で実行されるコンピュータ実行可能コードを意味する。なお、ストレージオペレーティングシステム３２４は、マイクロカーネルとして実施しても、ＵＮＩＸやＷｉｎｄｏｗｓ  ＮＴのような汎用オペレーティングシステム上で動作するアプリケーションプログラムとして実施してもよく、あるいは、本明細書の記載に従ってストレージアプリケーションのために構成された変更可能な機能を有する汎用ストレージオペレーティングシステムとして実施してもよい。
【００３０】
ディスク２５０へのデータアクセスを可能にするために、ストレージオペレーティングシステム３２４は、ファイルシステム４３０を実施する。ファイルシステム４３０は、情報を名前付きディレクトリ、及びファイルの階層構造としてディスク上に論理編成する。一実施形態において、ファイルシステム４３０は、ディスク２５０によって提供される記憶空間を「仮想化」するｗｒｉｔｅ−ａｎｙｗｈｅｒｅファイルシステムである。各ファイルは、データのような情報を記憶するように構成された一組のデータブロックとして実施される場合がある一方、ディレクトリは、特殊なフォーマットのファイルとして実施される場合があり、その中に、他のファイルやディレクトリの名前、及びリンクが記憶される。
【００３１】
ストレージオペレーティングシステム３２４は、プロトコルモジュール４３２、ネットワークアドレスモジュール４３３、ＲＡＩＤコントローラモジュール４３６、及びストレージドライバモジュール４３５をさらに含む。そして、ＲＡＩＤコントローラモジュール４３６は、ＲＡＩＤ最適化モジュール４４０（本明細書では「最適化モジュール」とも呼ばれる）を実施する。ＲＡＩＤ最適化モジュール４４０の動作については、後で詳しく説明する。
【００３２】
プロトコルモジュール４３２は、ネットワークファイルシステム（ＮＦＳ）、コモン・インターネット・ファイル・システム（ＣＩＦＳ）、ハイパーテキスト・トランスファ・プロトコル（ＨＴＴＰ）、及び／又はトランスミッション・コントロール・プロトコル／インターネット・プロトコル（ＴＣＰ／ＩＰ）のような種々の上位ネットワークプロトコルのうちの一、又は複数を実施し、到来するクライアント要求をエンコードし、又はクライアント要求に対する応答を適当なプロトコルに従ってエンコードする。ネットワークアドレスモジュール４３３は、一、又は複数のドライバを含み、これらのドライバが、イーサネット(R)のようなネットワークを介して通信するための一、又は複数の下位レベルプロトコルを実施する。プロトコルモジュール４３２、及び関連ネットワークアクセスモジュール４３３は、ストレージサーバ２００が、通信システム２３０を介して（例えば、クライアント２１０と）通信出来るようにする。
【００３３】
ストレージドライバモジュール４３５は、ストレージサーバ２００が、ディスクサブシステム２４０と通信出来るようにする。ストレージドライバモジュール４３５は、ファイバチャネルプロトコル（ＦＣＰ）、ＳＣＳＩ（Small Computer Systems Interface）プロトコル、シリアルＡＴＡ（ＳＡＴＡ）、又はシリアル・アタッチドＳＣＳＩ（ＳＡＳ）のような下位ストレージデバイスアクセスプロトコルを実施する。
【００３４】
ＲＡＩＤコントローラモジュール４３６（本明細書では「ストレージモジュール」とも呼ばれる）は、ＲＡＩＤシステムにおけるディスクのような記憶装置を管理する。ＲＡＩＤコントローラモジュールは、クライアント２１０からのアクセス要求に応答して、データの記憶、及び読み出しを管理する。アクセス要求には、データを書き込むための要求、及び／又はデータを読み出すための要求がある。一実施形態において、ＲＡＩＤコントローラモジュール４３６は、ストレージサーバ２００上で実施されるソフトウェアモジュールであってもよい。代替実施形態において、ＲＡＩＤコントローラモジュール４３６は、ハードウェアとして実施される独立したエンクロージャであってもよい。ＲＡＩＤコントローラモジュール４３６は、クライアント要求に応答し、ディスク２５０に対して内部Ｉ／Ｏコマンドを発行する。これらのコマンドは、ディスク２５０のある物理ブロック番号の位置にデータを書き込むコマンドである場合もあれば、ディスク２５０のある物理ブロック番号の位置からデータを読み出すコマンドである場合もある。
【００３５】
ＲＡＩＤ最適化モジュール４４０は、一、又は複数の物理データブロックに変更が加えられるストライプのパリティを記憶しているディスク（複数の場合もあり）に対し、コマンドを発行するように構成される。一実施形態において、このコマンドは、２００６年９月２２日にＴ１０技術委員会から草案が出版されたＳＣＳＩブロックコマンド、第二世代に記載の、ＳＣＳＩ規格によって提供されるＸＰＷｒｉｔｅコマンドである（www.t10.org参照）。ＸＰＷｒｉｔｅコマンドは、データの書き込み先にあたるブロックの論理ブロックアドレス（ＬＢＡ）、並びにデータの書き込みに要するブロック数を含む。ＲＡＩＤ最適化モジュール４４０によって実行される種々のステップについては、図７、及び図９を参照し、もっと詳しく説明する。本発明は、ＸＰＷｒｉｔｅコマンドを例として説明されているが、当業者には、ＸＰＷｒｉｔｅコマンドが、本発明を実施する一例であることが分かるであろう。
【００３６】
次に、図５を参照すると、図５は、ファイルシステム４３０の種々のコンポーネントを示している。ファイルシステム４３０は、ゼロ化モジュール５１０を実行する。ゼロ化モジュール５１０は、ＲＡＩＤコントローラモジュール４３６に対してゼロ化コマンドを発行し、ディスク２５０上の空き物理データブロックをゼロ値にする。ＲＡＩＤコントローラモジュール４３６は、このコマンドを受信すると、ディスク２５０（複数の場合もあり）上の空き物理データブロックをゼロ化する。ゼロ化モジュール５１０は、どの物理的データブロックが空いていて、どの物理的データブロックが割り当て済みであるかを、種々のデータ構造を使用して特定する。一実施形態において、ファイルシステム４３０は、どのデータブロックが割り当て済みであるかを示すデータマップ５２０、及び、どのデータブロックがゼロ値を有しているかを示すデータマップ５３０を記憶している。本明細書では、何らかのデータ、又はメタデータによって現在占有されているデータブロックを「割り当て済みデータブロック」と呼ぶ。何らかのデータ、又はメタデータで現在占有されていないデータブロックは、「空きデータブロック」、又は「未割り当てのデータブロック」と呼ばれる。当業者であれば、データマップ５３０とデータマップ５２０を、一つのデータ構造として実施してもよいことが分かるであろう。
【００３７】
次に、図６を参照すると、図６は、ゼロ化モジュール５１０、及びＲＡＩＤコントローラモジュール４３６によって実施される、空きデータブロックをゼロ化するための処理を示している。一実施形態において、データブロックをゼロ化する処理は、空き時間に実施される。本明細書において、「空き時間」とは、クライアント２１０からの要求が少ないと予想される時間（例えば、週末、休日、及びピークを外した時間等）を言う。他の実施形態として、ファイルシステム４３０は、あるストライプにおける空きブロックのゼロ化を、そのストライプ中の他のデータブロックへのデータの書き込みと同時に実施する場合がある。
【００３８】
ステップ６２０において、ゼロ化モジュール５１０は、データマップ５２０、及び５３０を使用して、ゼロ化されていない空きデータブロックを特定する。ゼロ化モジュール５１０は、まだゼロ化されていない空きデータブロックを見つけると、空きデータブロックをゼロ化するための要求６２５をＲＡＩＤコントローラモジュール４３６へ送信する。次に、ＲＡＩＤコントローラモジュール４３６は、その要求を受信し、その空きデータブロックをゼロ化する（６３０）。ステップ６４０において、ＲＡＩＤコントローラモジュール４３６は、ゼロ化されるデータブロックを含むストライプのパリティを更新する。その目的のために、一実施形態において、ＲＡＩＤコントローラモジュール４３６は、ゼロ化されるストライプ中の物理データブロックからデータを読み出し、そのストライプのパリティブロックを読み出し、そのデータをプロセッサ３２１へ送信し、データ、及びパリティに対してＸＯＲ演算を実施し、新たなパリティを求める。ＲＡＩＤコントローラモジュール４３６は、その新たなパリティを、データブロックがゼロ化されたストライプ中のパリティブロックに書き込み、データブロックをゼロ化する。ゼロ化プロセスが完了すると、ＲＡＩＤコントローラモジュール４３６は、確認メッセージ６４５をゼロ化モジュール５１０へ送信する。ステップ６６０において、ゼロ化モジュール５１０は、どの空きデータブロックが初期化されたかを知らせるために、データマップ５３０を更新する（６５０）。
【００３９】
図２を再び参照すると、各ディスク２５０のコントローラ２８０において実施されるコマンド実行モジュール２６０は、ＲＡＩＤ最適化モジュール４４０によって発行されたコマンドを実行する。一実施形態において、モジュール４４０は、一、又は複数の物理データブロックに対して変更が加えられたストライプのパリティを記憶しているディスクに対し、ＸＰＷｒｉｔｅコマンドを発行する。このコマンドは、新たなパリティが書き込まれることになるブロック番号、及びそのパリティの書き込みに要するブロック数を含む。さらに、このコマンドは、コマンドのタイプを示すオペレーションコード（オペコード）を含む。ストレージドライバモジュール４３５は、コマンドをディスクへ送信する。一、又は複数の物理データブロックに変更が加えられたストライプのパリティを記憶しているディスクのコマンド実行モジュール２６０は、そのコマンドを受信し、そのコマンド中に示されたパリティブロックをディスクメモリ２７０に読み込む。コマンド実行モジュール２６０は、オペコードからコマンドのタイプを識別し、そのコマンドを実行するためのデータをストレージドライバモジュール４３５に要求する。一実施形態において、ストレージドライバ４３５は、同じストライプ中の物理データブロックに書き込まれるものと同じデータを、コマンド実行モジュール２６０へ送信する。コマンド実行モジュール２６０は、ストレージドライバモジュール４３５から新たなデータを受信し、その新たなデータを、ディスクメモリ２７０に記憶されているパリティとＸＯＲ演算し、そのＸＯＲ演算の結果を、ＸＰＷｒｉｔｅコマンド中に示される物理データブロックに書き込む。
【００４０】
他の実施形態として、もし新たなデータが、二以上の物理ディスクに書き込まれる場合、そのディスクのコマンド実行モジュール２６０は、ストレージドライバモジュール４３５から、新たなデータに対するＸＯＲ演算の結果を受信する。コマンド実行モジュール２６０は、ストレージドライバモジュール４３５から受信したデータを、ディスクメモリ２７０に記憶されているパリティとＸＯＲ演算し、そのＸＯＲ演算の結果を、一、又は複数の物理データブロックに変更が加えられたストライプのパリティを記憶しているディスク上の物理データブロックに書き込む。
【００４１】
新たなデータが書き込まれる宛先のデータブロックは既にゼロ化されているので、それらのデータブロックを読み出す必要はなくなる。モジュール２６０によるＸＰＷｒｉｔｅコマンドの実行の結果、ＲＡＩＤコントローラモジュール４３６により古いパリティを読み出す必要はなくなる。なぜなら、ディスク２５０上のコマンド実行モジュール２６０が、新たなパリティを計算するために、古いパリティを読み出すからである。
【００４２】
もし書き込みが行われない他のドライブ上のがゼロ化される場合、それらのデータブロックを読み出す必要もなくなる。新たなパリティは、書き込まれるデータブロックのＸＯＲ演算の結果になるので、読み出し処理は何も必要とされない。
【００４３】
本発明の種々の実施形態によるＲＡＩＤ最適化技術を使用する例が、以下に記載される。
【００４４】
３．単一パリティ保護方式においてＲＡＩＤ最適化技術を使用する例
例示的実施形態における下記の説明を分かりやすくするために、物理データブロックに変更が加えられたときは常に、新たなデータが、ディスク２５０上の新たな物理的位置に書き込まれるものと仮定する。本明細書では、この性質を「アウト・オブ・プレイス書き込み」と呼ぶ。
【００４５】
Ａ．減算によるパリティ書き込み
図１Ａを再び参照すると、ストレージサーバ２００へ送信され、記憶されるデータは、例えば４キロバイトのような固定サイズの複数のブロック（例えば、Ｄ０からＤｎ）に分割され、それらが、複数のディスクにわたる一、又は複数のストライプに記憶される場合がある。行パリティは、例えば、ストライプ中のデータ（例えば、Ｄ０からＤｎ）の排他的論理和（ＸＯＲ）として計算され、ディスクＤ上の保護ブロックに記憶される。第１のストライプ、ストライプＩの行パリティは、Ｄ０、Ｄ１、及びＤ２のＸＯＲ演算の結果として得られ、それらのブロックから、行パリティブロックＰ（０−２）の値が生成される。Ｄ０を変更する要求をストレージサーバ２００が受信したものと仮定する。その場合、ストレージサーバ２００は、その要求を解読し、要求をファイルシステム４３０に渡す。ファイルシステム４３０は、データが書き込まれる場所の論理ブロック番号を識別し、データを特定ディスク（例えば、ディスクＡ）上の論理ブロック番号の位置に書き込むための要求をＲＡＩＤコントローラモジュール４３６へ送信する。ＲＡＩＤコントローラモジュール４３６は、減算によるパリティ書き込み方法を使用して、あるデータブロックに、例えばＤ０を記憶しているデータブロックに新たなデータを書き込む。その目的のために、ＲＡＩＤコントローラモジュール４３６は、読み出しコマンドをディスクＡへ送信し、Ｄ０を記憶しているデータブロックからデータを読み出す。モジュール４３６はさらに、読み出しコマンドをディスクＤにも送信し、Ｐ（０−２）を記憶しているパリティブロックからデータを読み出す。
【００４６】
ディスクＡのコントローラ２８０は、第１の読み出しコマンドを受信し、そのコマンドを次のように実行する。すなわち、コントローラ２８０は、Ｄ０を記憶しているデータブロックからデータを読み出し、そのデータをモジュール４３６へ転送する。そして、モジュール４３６は、そのデータをメモリ３２４に記憶する。
【００４７】
ディスクＤのコントローラ２８０は、第２の読み出しコマンドを受信し、そのコマンドを次のように実行する。すなわち、コントローラ２８０は、Ｐ（０−２）を記憶しているブロックからデータを読み出し、そのデータをモジュール４３６へ転送する。そして、モジュール４３６は、そのデータをメモリ３２４に記憶する。
【００４８】
次に、モジュール４３６は、Ｄ０、Ｐ（０−２）、及び新たなデータのＸＯＲを計算する。
【００４９】
次に、モジュール４３６は、書き込みコマンドをディスクＡへ送信し、Ｄ０を記憶しているデータブロックに新たなデータを書き込む。ストレージドライバモジュール４３５は、そのコマンドをＳＣＳＩ要求に入れ、コマンドをディスクＡへ送信する。
【００５０】
ディスクＡのコントローラ２８０は、そのコマンドを受信すると、データを受信する準備が出来たことを示す指示をモジュール４３５に渡す。モジュール４３５からデータを受信すると、コントローラ２８０は、そのデータを書き込み、Ｄ０を置き換える。
【００５１】
モジュール４３６は、ディスクＤに対して書き込みコマンドを発行し、新たなパリティを書き込み、Ｐ（０−２）を置き換える。ストレージモジュール４３５は、そのコマンドをＳＣＳＩ要求にいれ、コマンドをディスクＤへ送信する。
【００５２】
ディスクＤのコントローラ２８０は、そのコマンドを受信すると、データを受信する準備が出来たことを示す指示をモジュール４３５に渡す。モジュール４３５からデータ（すなわち、ＸＯＲ演算の結果）を受信すると、コントローラ２８０は、そのデータを、Ｄ０を記憶しているストライプのパリティブロックに書き込む。
【００５３】
このように、ストライプＩのデータブロックを変更するために、ＲＡＩＤコントローラモジュール４３６は、２回の読み出し処理（一つは、Ｄ０を記憶するデータブロックからのデータの読み出し、もう一つは、Ｐ（０−２）を記憶するパリティブロックからの行パリティの読み出し）を実施しなければならないであろう。
【００５４】
本発明の一実施形態によれば、あるデータブロック、例えば、Ｄ０を記憶しているデータブロックを変更するために、ＲＡＩＤコントローラモジュール４３６は、ディスクＡに対し、Ｄ０を記憶している物理データブロックに変更を加えるための書き込みコマンドを発行する。ＲＡＩＤ最適化モジュール４４０は、パリティを記憶しているディスク（すなわち、ディスクＤ）に対し、ＸＰＷｒｉｔｅコマンドを発行する。このコマンドは、ブロック番号、及びブロック数を含む。ストレージドライバモジュール４３５は、このコマンドを、パリティを記憶しているディスク（すなわち、ディスクＤ）へ送信する。
【００５５】
パリティを記憶しているディスクのコマンド実行モジュール２６０は、そのコマンドを受信すると、コマンド中に示されたパリティブロック（すなわち、Ｐ（０−２））をディスクメモリ２７０に読み込む。コマンド実行モジュール２６０は、ＸＰＷｒｉｔｅコマンドを実行するためのデータを受信する準備が出来たことを示す指示をストレージドライバモジュール４３５に渡す。ストレージドライバ４３５は、Ｄ０に変更を加えるためにディスクＡへ送信されたものと同じデータを、パリティを記憶しているディスクのコマンド実行モジュール２６０へ送信する。パリティを記憶しているディスクのコマンド実行モジュール２６０は、ストレージドライバ４３５から新たなデータを受信すると、その新たなデータをディスクメモリ２７０に記憶されているパリティとＸＯＲ演算し、そのＸＯＲ演算の結果を、パリティを記憶しているディスク上のパリティブロックに書き込む。
【００５６】
本発明の一実施形態によれば、Ｄ０を記憶している物理データブロックは、ゼロ値を有するものとみなされ、データをゼロとＸＯＲ演算しても、データは変更されないので、このデータブロックをＲＡＩＤコントローラ４３６によって読み出す必要性は無くなる。さらに、Ｐ（０−２）を記憶しているパリティブロックをＲＡＩＤコントローラ４３６によって読み出す必要性も無くなる。なぜなら、ＸＰＷｒｉｔｅコマンドの実行結果として、モジュール２６０が、パリティブロックＰ（０−２）をディスクメモリ２７０に読み込み、新たなデータ、及びパリティブロックの中身に対してＸＯＲ演算を実施するからである。このように、新たなデータが書き込まれることになる宛先のデータブロックをゼロ化することにより、ＲＡＩＤコントローラモジュール４３６が、古いデータを読み出したり、ディスク（複数の場合もあり）２５０から古いデータを転送する必要がなくなるので、回転遅延は幾らか抑制される。また、古いパリティは、パリティを記憶しているディスクのモジュール２６０によって読み込まれるので、古いパリティが、ＦＣリンクのような通信リンクを介してストレージサーバ２００へ転送されることもない。
【００５７】
Ｂ．再計算によるパリティ書き込み
再計算によるパリティ書き込み方法が、例えば、Ｄ０、及びＤ１を記憶しているデータブロックのような、２以上のデータブロックへの新たなデータの書き込みに使用されるものと仮定する。再計算によりパリティ書き込みを使用して新たなデータを書き込む従来のメカニズムを使用した場合、下記のステップが、ＲＡＩＤコントローラモジュール４３６によって実施される場合がある。すなわち、新たなデータが書き込まれるデータブロック（Ｄ０、Ｄ１）以外のデータブロック、例えばＤ２からデータを読み出すステップ、（Ｄ２と新たなデータの）ＸＯＲ演算を実施することにより新たな行パリティを計算するステップ、新たなデータを書き込むステップ、及び新たな行パリティをパリティブロックに書き込むステップである。
【００５８】
従って、新たなデータを２以上の物理ディスクに書き込むためには、ファイルシステム４３０は、少なくとも一回の読み出し処理を実施しなければならないであろう。
【００５９】
本発明の一実施形態によれば、新たなデータが書き込まれるデータブロックをゼロ化する場合、ＲＡＩＤコントローラモジュール４３６は、行パリティＰ（０−２）が、書き込まれる新たなデータとパリティのＸＯＲ演算の結果であることを反映するように、行パリティを更新する。従って、Ｄ０、及びＤ１がゼロ値を記憶し、（０、０、及びＤ２）のＸＯＲがＤ２であるから、新たなデータが書き込まれる前の行パリティはＤ２である。本発明の一実施形態による書き込み処理を実施するために、下記のステップが実施される場合がある。ＲＡＩＤコントローラモジュール４３６は、Ｄ０、及びＤ１を置き換えるために新たなデータを書き込む前に、新たなデータのＸＯＲを計算する。ＲＡＩＤ最適化モジュール４４０は、一、又は複数の物理データブロックに変更が加えられたストライプのパリティを記憶しているディスク（ディスクＤ）に対し、ＸＰＷｒｉｔｅコマンドを発行する。ストレージドライバモジュール４３５は、そのコマンドをディスクＤへ送信する。ディスクＤのコマンド実行モジュール２０は、そのコマンドを受信すると、コマンド中に示されたパリティブロックをディスクメモリ２７０に読み込む。コマンド実行モジュール２６０は、ＸＰＷｒｉｔｅコマンドを実行するためのデータを受信する準備が出来たことを示す指示をストレージドライバモジュール４３５に渡す。
【００６０】
ストレージドライバモジュール４３５は、ＸＯＲ演算の結果をモジュール２６０へ送信する。コマンド実行モジュール２６０は、ストレージドライバモジュール４３５から受信したデータを、ディスクメモリ２７０に記憶されているパリティとＸＯＲ演算する。モジュール２６０は、このＸＯＲ演算の結果を、ＸＰＷｒｉｔｅコマンド中に示される物理データブロックに書き込む。
【００６１】
図７は、本発明の一実施形態による、単一パリティ保護方式において減算によるパリティ書き込み、及び再計算によるパリティ書き込みを実施するための、ＲＡＩＤコントローラモジュール４３６、及びＲＡＩＤ最適化モジュール４４０によって実施される種々の処理を示すフロー図である。
【００６２】
ステップ７１０において、モジュール４４０は、データがストライプ中の全てのデータブロックに書き込まれるか否かを判定する。ステップ７１０における肯定的な判定結果に応答し、モジュール４３６は、データマップ５３０上のデータブロックをゼロ化されていないものとしてマーキングし（７１５）、従来の方法を使用してパリティを計算する。例えば、モジュール４３６は、行パリティを計算するために、新たなデータのＸＯＲを計算する（７２０）。ステップ７３０において、モジュール４３０は、新たなデータを物理データブロックに書き込み、ＸＯＲ演算の結果を行パリティブロックに書き込む。
【００６３】
あるいは、ステップ７１０において、もしデータがストライプ中の全てのデータブロックには書き込まれないことが判明した場合、ステップ７４０において、モジュール４３６は、ストライプ中の他の全てのデータブロックが、ゼロ値を記憶している（ゼロ化されている）か否かを判定する。ステップ７４０における肯定的な判定結果に応答し、モジュール４３６は、データマップ５３０を使用して、書き込みを受けるデータブロックをゼロ化されていないものとしてマーキングする（７４５）。ステップ７５０において、モジュール４３６は、データが、ストライプ中の２以上のデータブロックに書き込まれるか否かを判定する。もしデータが、ストライプ中の２以上のデータブロックに書き込まれる場合、ＲＡＩＤコントローラモジュール４３６は、新たなデータのＸＯＲを計算する（７６０）。モジュール４３６は、新たなデータを物理データブロックに書き込み（７７０）、ＸＯＲ演算の結果をパリティブロックに書き込む。
【００６４】
あるいは、ステップ７５０において、新たなデータが一つのデータブロックに書き込まれる場合、モジュール４３６は、新たなデータを幾つかの物理データブロックに書き込み（７７２）、新たなデータを行パリティブロックに書き込む。なぜなら、行パリティは、新たなデータと同じであるからである。
【００６５】
ステップ７７４において、上書きされるデータブロックがゼロ値を記憶している場合、モジュール４３６は、データマップ５３０を使用して、書き込まれるデータブロックをゼロ化されていないものとしてマーキングする（７７６）。ステップ７７８において、モジュール４３６は、新たなデータが、ストライプ中の２以上のデータブロックに書き込まれるか否かを判定する。肯定的な判定結果、例えば、データが２以上のデータブロックに書き込まれるという判定結果に応答し、モジュール４３６は、全ての新たなデータに対するＸＯＲ演算を実施することにより、新たなデータのパリティを計算する。次に、モジュール４３６は、新たなデータを、書き込みコマンド中に示されたブロックに書き込む（７８２）。
【００６６】
次に、モジュール４４０は、一、又は複数の物理データブロックに対して変更が加えられたストライプのパリティを記憶しているディスクに対し、ＸＰＷｒｉｔｅコマンドを発行する。ディスクのモジュール２６０は、そのコマンドを受信すると、そのコマンドを次のように実行する。モジュール２６０は、行パリティ（書き込まれないデータブロックのＸＯＲ演算の結果）をディスクメモリ２７０に読み込む。モジュール２６０は、ストレージドライバモジュール４３５から、新たなデータに対するＸＯＲ演算の結果を受信する。モジュール２６０は、ＸＯＲ演算の結果を行パリティとＸＯＲ演算する。モジュール２６０は、そのＸＯＲ演算の結果を行パリティブロックに書き込む。その結果、本発明の一実施形態によれば、新たなデータが書き込まれることになるデータブロック以外のデータブロックに記憶された古いデータを読み出さなければならないという、従来の再計算によるパリティ書き込み方法の要件を、データが書き込まれることになるデータブロックをゼロ化することによって、無くすことができる。ＸＰＷｒｉｔｅコマンドの実行により、古い行パリティを読み出す必要性は無くなる。
【００６７】
あるいは、もしストライプ中の一つのデータブロックにしか書き込みが行われない場合、モジュール４３６は、新たなデータを物理データブロックに書き込む（７８４）場合がある。次に、モジュール４４０は、物理データブロックに対して変更が加えられたストライプのパリティを記憶しているディスクに対し、ＸＰＷｒｉｔｅコマンドを発行する。ディスク２５０上のモジュール２６０は、そのコマンドを受信すると、そのコマンドを次のように実行する。モジュール２６０は、古いパリティをディスクメモリ２７０に読み込む。モジュール２６０は、ストレージドライバモジュール４３５から、物理データブロックに書き込むべきデータ（変更すべき物理データブロックへ送信されたものと同じデータ）を受信する。モジュール２６０は、そのデータを古いパリティとＸＯＲ演算し、そのＸＯＲ演算の結果をパリティディスク上のパリティブロックに書き込む。その結果、本発明の一実施形態によれば、古いパリティをストレージサーバ２００上のＲＡＩＤコントローラモジュール４３６によって読み出し、そのパリティをＦＣリンクのような通信チャネルを介して転送しなければならないという、従来の減算によるパリティ書き込み方法の要件を無くすことができる。
【００６８】
ステップ７７４において、もしストライプ中にゼロ値を記憶しているデータブロックが一つも無く、データが、唯一つのデータブロックにしか書き込まれない場合、例えば、減算によるパリティ書き込み、又は再計算によるパリティ書き込み（７８６）のような従来の方法を使用して、書き込み処理を実施してもよい。ステップ７８８において、モジュール４３６は、データマップ５３０を使用し、書き込みを受けるデータブロックをゼロ化されていないものとしてマーキングする（７７６）。先に説明したように、減算によるパリティ書き込み方法によれば、古いパリティブロックが、読み出される。さらに、新たなデータが書き込まれる場所にあるデータブロックも読み出される。そして、その古いパリティ、及び古いデータに対して排他的論理和（ＸＯＲ）演算が実施される。新たなパリティを求めるために、その結果が、新たなデータとＸＯＲ演算される。新たなデータは、データブロックに書き込まれ、新たなパリティは、パリティブロックに書き込まれる。再計算によるパリティ書き込みによれば、行パリティを計算するために、ストライプ中のデータブロックのうち、データが書き込まれる宛先となるデータブロック以外のデータブロックが読み出され、新たなデータとＸＯＲ演算される。新たなデータはデータブロックに書き込まれる。計算されたパリティは、パリティブロックに書き込まれる。
【００６９】
４．二重パリティ保護方式においてＲＡＩＤ最適化技術を使用する例
本発明のＲＡＩＤ最適化技術は、二重パリティ保護方式にも適用可能である。二重パリティ保護方式については、Ｐｅｔｅｒ  Ｆ．Ｃｏｒｂｅｔｔ他による「ROW-DIAGONAL PARITY TECHNIQUE FOR ENABLING EFFICIENT RECOVERY FRO DOUBLE FAILURES IN A STORAGE ARRAY」と題する米国特許出願第１０／０３５，６０７号に記載されており、この特許出願の開示は全て、参照により、本明細書に援用される。
【００７０】
背景として、ディスクサブシステム２４０は、ｎ個の記憶装置（例えばディスク）を備える場合が有る。ただし、ｎ＝ｐ＋１であり、ｐは素数である。記憶装置は、複数のブロックに分割される。各記憶装置内から、ｎ−２個のブロックが任意に選択され、全ての記憶装置にわたる一つストライプを形成するようにグループ化される。ストライプ中の一つの装置は、他の装置から入力としてブロックを選択することにより形成されるパリティを保持する装置に指定される。この装置は、対角パリティ装置と呼ばれ、この装置が保持するパリティは、対角パリティと呼ばれる。各ストライプ内において、ストライプ内における対角パリティ装置ではない装置から、それぞれ一つのブロックが選択される。このブロックの集合は、行と呼ばれる。行の形成は、ストライプ内のブロックのうち、対角パリティ装置上にないブロックが全て、ちょうど一行に割り当てられるまで継続される。全部でｎ−２個の行が存在する。各ストライプ内における対角パリティ装置ではない装置のうち、一つを除く全ての装置から、それぞれ一つのブロックが選択され、その際、選択されるブロックのうちの２つが、同じ行に属してはならないという制限がさらに課せられる。これは、対角パリティセット、または「対角」と呼ばれる。対角の形成は、例えば、データ装置、行パリティ装置、及び対角パリティ装置に０からｎ−１まで番号を付し、行に０からｎ−３まで番号を付し、そして、装置ｉ、行ｊにあるブロックを対角（ｉ＋ｊ＋１）ｍｏｄ（ｎ−１）に割り当てることによって行われる場合がある。対角の形成は、ストライプ中のブロックのうち、対角パリティ装置上にはないブロックが全て対角に割り当てられるまで継続される。ただしその際、同じ装置上のブロックを何も有しない２つの対角が存在しないようにするという制限がさらに課せられる。ｎ−１個の対角が存在する。ｎ−１個の対角の中から、ｎ−２個の対角が選択される。それらの対角中のブロックは、データを保持しているか、パリティを保持しているかに関わらず、互いに結合され、一つの対角パリティブロックを形成する。ｎ−２個の対角パリティブロックは、そのストライプ中の対角パリティを保持している装置上の、そのストライプ中のｎ−２個のブロックに、任意の順序で記憶される。
【００７１】
次に、図８を参照すると、ＲＡＩＤ−ＤＰによるアレイ８００における対角パリティセットの一例が示されている。図８の例において、一つのストライプは、行１〜行４を含むものとして描かれている。データは、ディスク１〜ディスク４に記憶される。ディスク０は、各行について行パリティを記憶する。ディスク５は、各対角について対角パリティを記憶する。あるストライプ中の各データブロックは、行、及びディスク番号によって識別される。各データブロック中の番号は、そのデータブロックが属する対角パリティセットを示す。図８に示す例において、行パリティは下記のように計算される。
【００７２】
行１の行パリティは、｛行１、ディスク１｝、｛行１、ディスク２｝、｛行１、ディスク３｝、及び｛行１、ディスク４｝に記憶されたデータに対するＸＯＲ演算の結果である。
【００７３】
行２の行パリティは、｛行２、ディスク１｝、｛行２、ディスク２｝、｛行２、ディスク３｝、及び｛行２、ディスク４｝に記憶されたデータに対するＸＯＲ演算の結果である。
【００７４】
行３の行パリティは、｛行３、ディスク１｝、｛行３、ディスク２｝、｛行３、ディスク３｝、及び｛行３、ディスク４｝に記憶されたデータに対するＸＯＲ演算の結果である。
【００７５】
行４の行パリティは、｛行４、ディスク１｝、｛行４、ディスク２｝、｛行４、ディスク３｝、及び｛行４、ディスク４｝に記憶されたデータに対するＸＯＲ演算の結果である。
【００７６】
ｐ−１個の対角パリティセットについて、対角パリティが記憶される。ただし、ｐは、３以上の素数である。従って、対角パリティセット４についての対角パリティは、記憶されない。対角パリティが記憶されないこの対角パリティセットは、「欠落した」対角と呼ばれる。ある対角パリティセットの対角パリティは、その対角パリティセットを構成するデータブロック、及び行パリティブロックに記憶されたデータの排他的論理和（ＸＯＲ）として計算される。
【００７７】
対角パリティセット０は、データブロック｛行１、ディスク０｝、｛行４、ディスク２｝、｛行３、ディスク３｝、及び｛行２、ディスク４｝上にデータを有する。対角パリティセット０の対角パリティは、それらのデータブロックに記憶されたデータのＸＯＲを計算することによって求まる。対角パリティセット０について計算された対角パリティは、データブロック｛行１、ディスク５｝に記憶される。
【００７８】
対角パリティセット１は、データブロック｛行１、ディスク１｝、｛行２、ディスク０｝、｛行４、ディスク３｝、及び｛行３、ディスク４｝上にデータを有する。対角パリティセット１の対角パリティは、それらのデータブロックに記憶されたデータのＸＯＲを計算することによって求まる。対角パリティセット１について計算された対角パリティは、データブロック｛行２、ディスク５｝に記憶される。
【００７９】
対角パリティセット２は、データブロック｛行３、ディスク０｝、｛行２、ディスク１｝、｛行１、ディスク２｝、及び｛行４、ディスク４｝上にデータを有する。対角パリティセット２の対角パリティは、それらのデータブロックに記憶されたデータのＸＯＲを計算することによって求まる。対角パリティセット２について計算された対角パリティは、データブロック｛行３、ディスク５｝に記憶される。
【００８０】
対角パリティセット３は、データブロック｛行４、ディスク０｝、｛行３、ディスク１｝、｛行２、ディスク２｝、及び｛行１、ディスク３｝上にデータを有する。対角パリティセット３の対角パリティは、それらのデータブロックに記憶されたデータのＸＯＲを計算することによって求まる。対角パリティセット３について計算された対角パリティは、データブロック｛行１、ディスク５｝に記憶される。
【００８１】
対角パリティセット４は、データブロック｛行４、ディスク１｝、｛行３、ディスク２｝、｛行２、ディスク３｝、及び｛行１、ディスク４｝上にデータを有する。対角パリティセット４は、欠落した対角であり、この対角の対角パリティは記憶されない。
【００８２】
ディスクＤ１は、ゼロ値を記憶し、減算によるパリティ書き込み方法を使用して、新たなデータが、ディスク１に書き込まれるものと仮定する。従来の方法によれば、ＲＡＩＤコントローラモジュール４３６は、下記のステップを実施する必要があるであろう。すなわち、
ディスク１上のデータを読み出すステップ；
行パリティを読み出すステップ；
対角パリティを読み出すステップ；
ディスク０に記憶されたデータ、行パリティ、及び新たなデータのＸＯＲ演算を実施することにより、新たな行パリティを計算するステップ；
Ｄ０に記憶されたデータ、対角パリティ、及び新たなデータのＸＯＲ演算を実施することにより、新たな対角パリティを計算するステップ；
新たなデータをディスク１に書き込むステップ；
新たな行パリティをディスク０に書き込むステップ；及び
新たな対角パリティをディスク５に書き込むステップである。
【００８３】
このように、書き込み処理を実施するために、ＲＡＩＤコントローラ４３６は、３回の読み出し処理を実施しなければならない場合がある。
【００８４】
本発明の一実施形態によれば、もし新たなデータが書き込まれる場所にあるデータブロック（複数の場合もあり）が、ゼロ値を記憶していた場合、古いデータ、行パリティ、又は対角パリティを読み出す必要はない。本発明の一実施形態による書き込み処理を実施するために、ＲＡＩＤ最適化モジュール４４０は、下記のようなステップを実施する。なお、ストレージサーバ２００上のメモリ３２２は、行パリティを記憶するためのメモリブロック、及び対角パリティを記憶するためのメモリブロックを有している。
【００８５】
上書きされるデータブロック（複数の場合もあり）が全て、ゼロを有している場合、
１．書き込むべき最初のデータブロックを、行パリティ用のメモリブロックにコピーし；
２．書き込むべき最初のデータブロックを、対角パリティ用のメモリブロックにコピーし；
３．新たなデータに基いて行パリティを計算し；
４．新たなデータに基いて対角パリティを計算し；
５．データを物理データブロックに書き込み；
６．ステップ３の結果を行パリティディスクにＸＰＷｒｉｔｅし；
７．ステップ４の結果を対角パリティディスクにＸＰＷｒｉｔｅする。
【００８６】
以下は、新たなデータに基いて対角パリティを計算し、どのデータブロックを使用して対角パリティを計算すべきかを識別するためのステップの概要を示すアルゴリズムを示す。
【００８７】
ｐ＝素数
対角パリティセットの数＝ｐ−１
ディスク数＝ｐ＋１
ｉ＝ディスク番号０．．．ｎ
ｋ＝対角パリティセット０．．．ｍ
Ｆｏｒ（ｋ＝０；ｋ＜対角セット数；ｋ＋＋）
｛
対角ストライプブロックのオフセットを得る。ただし、オフセットは、メモリの先頭から始まるブロックのアドレスを示す；
（ディスク番号＋ｋ）％ｐ＝オフセット。ただし％は、モジューロ（（ディスク数＋ｋ）とｐの除算の余り）である；
ｉｆ（オフセット＝＝（ｐ−１））
ｔｈｅｎ  ｓｋｉｐ
ｅｌｓｅ
対角ストライプブロックを対角パリティ用メモリブロックに記憶されたデータのオフセットに対してＸＯＲ演算
｝
Ｉｆ  ２以上のディスクを書き込み
｛
Ｆｏｒ（ｘ＝１；ｘ＜書き込まれるディスクの数；ｘ＋＋）
｛
書き込むべきデータブロックを行パリティ用メモリブロックにＸＯＲ演算する
Ｆｏｒ（ｋ＝０；ｋ＜対角セット数；ｋ＋＋）
対角ストライプブロックのオフセットを得る
（ディスク番号＋ｋ）％ｐ＝オフセット
ｉｆ（オフセット＝＝（ｐ−１））
ｔｈｅｎ  ｓｋｉｐ
ｅｌｓｅ
対角ストライプブロックを対角パリティメモリのオフセットとＸＯＲ演算
｝
｝
行パリティ用ブロックに記憶された結果を、対角パリティ用メモリの中にＸＯＲ演算
｝。
【００８８】
行パリティディスクへ送信されたＸＰＷｒｉｔｅコマンドの実行（ステップ６で述べたような）の結果、行パリティディスク（例えば、図８におけるディスク０）上のモジュール２６０は、コマンド中に示されたブロック番号にある古い行パリティをディスクメモリ２７０に読み込み、ストレージドライバモジュール４３５から、新たなデータに基いて計算された行パリティを受信し、その新たなデータについて計算された行パリティを古い行パリティとＸＯＲ演算し、そのＸＯＲ演算の結果を行パリティディスクに書き込む。
【００８９】
対角パリティディスクへ送信されたＸＰＷｒｉｔｅコマンドの実行（ステップ７で述べたような）の結果、対角パリティを記憶しているディスク（例えば、図８におけるディスク５）上のモジュール２６０は、コマンド中に示されたブロック番号にある古い対角パリティをディスクメモリ２７０に読み込み、ストレージドライバモジュール４３５から、新たなデータに基いて計算された対角パリティを受信し、その新たなデータについて計算された対角パリティを古い対角パリティとＸＯＲ演算し、そのＸＯＲ演算の結果を対角パリティディスクに書き込む。このアルゴリズムの応用形態の一例を、以下に示す。
【００９０】
図８を再び参照し、全てのディスクがゼロ化され、新たなデータ｛２、３、４、５｝が、ディスク２に書き込まれるものと仮定する。
【００９１】
まず、新たなデータは、メモリ３２２の行パリティ用のブロックにコピーされる。メモリ３２２の行パリティ用のブロックは、現在、｛２、３、４、５｝を記憶している。ディスク１〜４に記憶されたデータは、ゼロ化されているので、行パリティは、新たなデータと同じである。
【００９２】
次に、新たなデータは、メモリ３２２の対角パリティ用のブロックにコピーされる。メモリ３２２の対角パリティ用のブロックは、現在、｛２、３、４、５｝を記憶している。各対角パリティセットについて、対角パリティが、下記のように計算される。
【００９３】
１．ディスク２の各対角ストライプブロックについて、対角ストライプブロックを対角パリティにＸＯＲ演算する；
２．ディスク２の第１のブロックについて、対角ストライプブロック番号を見つける：（２＋０）％５＝２。第１のブロックを、対角ストライプブロック２に対して適当なオフセットにある対角パリティにＸＯＲ演算する。（２ＸＯＲ４＝６）
３．ディスク２における第２のブロックについて対角ストライプブロック番号を見つける：（２＋１）％５＝３；
第２のストライプブロックを、メモリ３２２の対角パリティ用ブロックの対角ストライプブロック３に関する適当なオフセットにあるブロックにＸＯＲ演算する。（３ＸＯＲ５＝６）
４．ディスク２の第３のブロックについて、対角ストライプブロック番号を見つける：（２＋２）％５＝４。対角ストライプブロック４は、対角パリティに属しない。従って、対角ストライプブロック４は、欠落した対角であり、対角パリティを記憶する目的に使用されない；
５．ディスク２の第４のブロックについて、対角ストライプブロック番号を見つける：（２＋３）％５＝０
第４のストライプブロックを、対角パリティ用メモリ３２２の対角ストライプブロック０に対する適当なオフセットにＸＯＲ演算する。（５ＸＯＲ２＝７）。
【００９４】
次に、図１を参照すると、図１は、提供した例に関する、計算された行パリティ、及び対角パリティを示している。
【００９５】
【表１】
2010508604.tif 000003
【００９６】
表１に示すように、ディスク２は、｛２、３、４、５｝を記憶し、ディスク０は、｛２、３、４、５｝を記憶している。ディスク５は、上記のアルゴリズムを使用して計算された対角パリティを記憶している。
【００９７】
図９は、本発明の一実施形態による、ＲＡＩＤ−ＤＰにおいて減算によるパリティ書き込み、及び再計算によるパリティ書き込みを実施するための、ＲＡＩＤ最適化モジュール４４０、及びＲＡＩＤコントローラモジュール４３６によって実施される種々の処理を示すフロー図である。
【００９８】
ステップ９１０において、モジュール４３６は、データが、ストライプ中の全てのデータブロックに書き込まれるか否かを判定する。ステップ９１０における肯定的な判定結果に応答し、モジュール４３６は、データマップ５３０を使用して、書き込まれるデータブロックをゼロ化されていないものとしてマーキングする（９１５）。ステップ９２０において、モジュール４３６は、新たなデータに対するＸＯＲ演算を行い、行パリティを求める。モジュール４３６はさらに、本明細書に記載されるような対角パリティを計算するためのアルゴリズムを使用して、対角パリティを計算する。ステップ９３０において、モジュール４３０は、新たなデータを物理データブロックに書き込み、ＸＯＲ演算の結果を行パリティブロックに書き込み、対角パリティを対角パリティブロックに書き込む。
【００９９】
あるいは、もしデータが、ストライプ中の全てのデータブロックには書き込まれない場合、ステップ９４０において、モジュール４３６は、ストライプ中の他の全てのデータブロックが、ゼロ値を記憶しているか否かを判定する。ステップ９４０における肯定的な判定結果に応答し、モジュール４３６は、データマップ５３０を使用して、書き込まれるデータブロックをゼロ化されていないものとしてマーキングする（９４５）。ステップ９５０において、モジュール４３６は、データが、ストライプ中の２以上のデータブロックに書き込まれるか否かを判定する。もし、データがストライプ中の２以上のデータブロックに書き込まれる場合、モジュール４３６は、新たなデータに対するＸＯＲ演算９６０を実施することにより、行パリティを計算する。モジュール４３６は、対角パリティをさらに計算する。そして、モジュール４３６は、新たなデータをディスク（複数の場合もあり）２５０上の物理データブロックに書き込み、ＸＯＲ演算の結果を行パリティブロックに書き込み、対角パリティを対角パリティブロックに書き込む。
【０１００】
あるいは、ステップ９５０において、もし新たなデータが、一つのデータブロックに書き込まれる場合、モジュール４３６は、本明細書に記載されるような対角パリティを計算するためのアルゴリズムを使用して、対角パリティを計算する。ステップ９７４において、新たなデータは、データブロックに書き込まれ、新たなデータは、行パリティブロックに書き込まれ、対角パリティは、対角パリティブロックに書き込まれる。
【０１０１】
ステップ９７６において、モジュール４３６は、上書きされるデータブロックがゼロ化されているか否かを判定する。ステップ９７６における肯定的な判定結果に応答し、モジュール４３６は、データマップ５３０を使用して、書き込みを受けるデータブロックをゼロ化されていないものとしてマーキングする（９７８）。ステップ９８０において、モジュール４３６は、新たなデータが、ストライプ中の２以上のデータブロックに書き込まれるか否かを判定する。もし２以上のデータブロックに対して書き込みが行われる場合、モジュール４３６は、書き込まれるデータブロックを物理データブロックとＸＯＲ演算することによって行パリティを計算する（９８２）。モジュール４３６はさらに、本明細書に記載されるような対角パリティを計算するためのアルゴリズムを使用して、対角パリティを計算する。
【０１０２】
ステップ９８４において、モジュール４３６は、新たなデータを物理データブロックに書き込む。ステップ９８４において、モジュール４４０は、一、又は複数のデータブロックに変更が加えられたストライプの行パリティを記憶しているディスクに対し、コマンドを発行する。一実施形態において、このコマンドは、ＸＰＷｒｉｔｅコマンドである。行パリティを記憶しているディスクのモジュール２６０は、このコマンドを受信し、コマンドを次のように実行する。モジュール２６０は、コマンドによって示されたブロック番号にある古い行パリティをディスクメモリ２７０に読み込む。モジュール２６０は、ストレージドライバモジュール２３５から、物理データブロックに書き込まれるデータに対するＸＯＲ演算の結果を受信する。モジュール２６０は、そのＸＯＲ演算の結果を古い行パリティとＸＯＲ演算し、その結果を、行パリティを記憶しているディスク上の、コマンドによって示された行パリティブロックに書き込む。
【０１０３】
モジュール４４０はさらに、対角パリティを記憶しているディスク（対角パリティディスク）に対し、第２のＸＰＷｒｉｔｅコマンドを発行する。ディスク２５０のモジュール２６０は、このコマンドを次のように実行する。モジュール２６０は、コマンド中に示されたブロック番号にある古い対角パリティをディスクメモリ２７０に読み込む。モジュール２６０は、ストレージドライバモジュール２３５から、新たなデータに基いて計算された対角パリティを受信する。モジュール２６０は、その新たなデータについて計算された対角パリティを古い対角パリティとＸＯＲ演算し、そのＸＯＲ演算の結果を対角パリティを記憶しているディスク上の、対角パリティブロックに書き込む。
【０１０４】
あるいは、もしストライプ中の唯一つのデータブロックに対してしか書き込みが行われない場合、モジュール４３６は、本明細書に記載されるような対角パリティを計算するためのアルゴリズムを使用して、対角パリティを計算する（９８６）。ステップ９８８において、モジュール４３６は、新たなデータを物理データブロックに書き込む。モジュール４４０は、物理データブロックに変更が加えられたストライプの行パリティを記憶しているディスクに対し、一つのＸＰＷｒｉｔｅコマンドを発行し、変更が加えられた物理データブロックを含む対角セットの対角パリティを記憶しているディスクに対し、もう一つのＸＰＷｒｉｔｅコマンドを発行する。モジュール２６０は、それらのコマンドを受信し、コマンドを下記のように実行する。
【０１０５】
もし、ストライプ中にゼロ値を記憶しているデータブロックが一つもなかった場合、モジュール４３６は、例えば減算によるパリティ書き込み、及び再計算によるパリティ書き込みのような従来の方法を使用９９０して、行パリティ、及び対角パリティを計算し、書き込み処理を実施する。ステップ９９２において、モジュール４３６は、データマップ５３０を使用して、書き込まれるデータブロックをゼロ化されていないものとしてマーキングする。前述の場合と同様に、減算によるパリティ書き込み方法によれば、古い行パリティブロック、古い対角パリティブロック、及び新たなデータが書き込まれる場所に有るデータブロックが、読み出される。新たな行パリティを求めるために、古い行パリティ、古いデータ、及び新たなデータに対するＸＯＲが計算される。新たな対角パリティを求めるために、古いデータ、古い行パリティ、古い対角パリティ、及び新しいデータに対するＸＯＲが計算される。新たなデータは、データブロックに書き込まれ、新たな行パリティ、及び新たな対角パリティは、対応するパリティブロックに書き込まれる。
【０１０６】
再計算によるパリティ書き込みによれば、データの書き込みが行われないデータブロックから、データは読み出される。行パリティは、新たなデータ、及び新たなデータが書き込まれないデータブロックから読み出されたデータに対するＸＯＲ演算として計算される。同様に、対角パリティは、新たなデータ、及び新たなデータが書き込まれないデータブロックから読み出されたデータに対するＸＯＲ演算として計算される。新たなデータはデータブロックに書き込まれ、行パリティは、行パリティブロックに書き込まれ、対角パリティは、対角パリティブロックに書き込まれる。
【０１０７】
５．劣化モード書き込み
これまでのところ、ストレージサーバ２００の動作は、通常動作、例えば、クライアント２１０からのＩ／Ｏアクセス要求に対し、ストレージサーバ２００が応答するときに、ディスク２５０からのデータの読み出しや、ディスク２５０へのデータの書き込みが可能である場合を例として説明してきた。一、又は複数のディスクが故障した状況において、ストレージサーバ２００は、劣化モードで動作する。新たなデータが、故障したディスクに書き込まれるとき、データ自体は、ディスクに書き込まれないが、パリティは、新たなデータを含むように計算される。その目的のために、ＲＡＩＤコントローラモジュール４３６は、ストライプ中のアレイにおける他の全てのディスクからデータを読み出し、読み出したデータを新たなデータとＸＯＲ演算してパリティを求め、ストライプ中のパリティブロックをその新たなパリティで更新する。下記の例は、劣化モードにおけるストレージサーバ２００の動作を示す。
【０１０８】
図１Ａを参照し、ディスクＡが故障し、新たなデータは、ディスクＡのブロックＤ０に書き込まれるものと仮定する。再計算によるパリティ書き込み方法を使用した場合、ＲＡＩＤコントローラモジュール４３６は、データを書き込むために、下記のステップを実施しなければならないであろう。すなわち、
ストライプ０におけるデータが書き込まれるディスク（ディスクＡ）以外のディスク（ディスクＢ、及びディスクＣ）からデータを読み出すステップ；
ディスクＢ上のデータ、ディスクＣ上のデータ、及び新たなデータに対するＸＯＲを計算することにより、ストライプ０についての新たな行パリティを求めるステップ；及び
新たな行パリティを行パリティブロックＰ（０−２）に書き込むステップである。
【０１０９】
本発明の一実施形態によれば、もし、ゼロ化プロセスの一部としてディスクＡが既にゼロ化されていれば、ストライプ０の行パリティは、ディスクＢに記憶されたデータとディスクＣに記憶されたデータのＸＯＲ演算の結果になる。ディスクＡはゼロ値を記憶しているので、行パリティは、ディスクＢに記憶されたデータと、ディスクＣに記憶されたデータのＸＯＲ演算の結果になる。本発明の一実施形態によれば、例えば、ディスクＢ、及びディスクＣからデータを読み出すような、特定の読み出し処理を避けるために、モジュール４４０は、変更が加えられた物理データブロックを含むストライプのパリティを記憶しているディスク（すなわち、ディスクＤ）に対し、ＸＰＷｒｉｔｅコマンドを発行する。
【０１１０】
ディスクＤのモジュール２６０は、サーバシステム２００からそのコマンドを受信し、コマンドを次のように実行する。モジュール２６０は、行パリティ（すなわち、ディスクＢに記憶されたデータと、ディスクＣに記憶されたデータのＸＯＲ演算の結果）をディスクメモリ２７０に読み込み；ストレージドライバモジュール４３５から、ディスクＡのための新たなデータを受信し；行パリティを新たなデータとＸＯＲ演算し、そのＸＯＲ演算の結果を、ディスクＤの、コマンド中に示されたブロックに書き込む。
【０１１１】
従って、ディスクＡが故障し、新たなデータをディスクＡに書き込むことは出来ないが、もしディスク故障がなければ新たなデータが書き込まれるはずであったストライプの行パリティは、新たなデータを含むように計算される。本発明の一実施形態によれば、空きデータブロックのゼロ化により、それらのデータブロックからデータを読み出す必要はなくなり、また、新たなデータが書き込まれる宛先のデータブロック以外のデータブロックからも、データを読み出す必要はなくなる。
【０１１２】
６．メディアエラー
ディスク上のメディアエラーは、そのディスクから特定ブロック、又は複数のブロックからデータを読み出すことが出来ないときに発生する。次に、表２を参照すると、表２は、物理データブロックを記憶するディスクのアレイを示している。この例には、一つのストライプ（ストライプ０）しか描かれていない。データは、ディスク１〜ディスク４に記憶される。ディスク０は、行パリティを記憶する。
【０１１３】
【表２】
2010508604.tif 000004
【０１１４】
ディスク１が故障し、ディスク２がメディアエラーを有するものと仮定する。一般に、メディアエラーを有するディスク２上のデータブロックからデータを復元するためには、ＡＲＩＤコントローラモジュール４３６は、下記のようなステップを実施しなければならないであろう。すなわち、
ディスク１、ディスク３、及びディスク４に記憶されている、ストライプ０に関するデータを読み出すステップ；
ディスク０から、ストライプ０に関する行パリティを読み出すステップ；
ディスク１、ディスク３、及びディスク４に記憶されている、ストライプ０に関するデータをＸＯＲ演算するステップ；及び
上記ステップの結果をストライプ０の行パリティとＸＯＲ演算するステップである。
【０１１５】
しかしながら、ディスク１が故障していて、ディスク２に記憶されたデータを復元するために、ディスク１に記憶されたデータを得ることはできないので、ディスク２上の、メディアエラーを有する物理データブロックに記憶されたデータも、復元できない場合がある。本発明の一実施形態によれば、もし、ディスク１がゼロ値を記憶していれば、ＲＡＩＤコントローラモジュール４３６は、ディスク２上のストライプ０にある物理データブロックからデータを復元するために、下記のステップを実施する場合がある。すなわち、
ディスク３、及びディスク４上のストライプ０に関するデータを読み出すステップ；
ストライプ０の行パリティを読み出すステップ；
ディスク３、及びディスク４上のストライプ０に関するデータをＸＯＲ演算するステップ；及び
上記ステップの結果を、ストライプ０の行パリティとＸＯＲ演算するステップである。
【０１１６】
もしディスク１がゼロを記憶していれば、ディスク１、ディスク３、及びディスク４に記憶されたデータに対するＸＯＲ演算の結果は、ディスク３、及びディスク４に記憶されたデータに対するＸＯＲ演算と同じになるので、ディスク１上のデータを読み出す必要はなくなる。従って、あるストライプにおいて、ディスクの１つがゼロ値を記憶していることを知っていれば、ファイルシステム４３０は、ＲＡＩＤ−４、及びＲＡＩＤ−５においてディスク故障が存在するときに、メディアエラーの有るディスクからデータを復元することが可能になる。
【０１１７】
また、故障したドライブが２つ有り、さらに３つ目のディスク上にメディアエラーを有する二重パリティＲＡＩＤアレイの場合、メディアエラーを有するドライブ上のデータは、もしいずれかの故障したドライブ上の対応するブロックが、ゼロ化されたブロックであれば、復元可能である。このデータは、通常ならば復元できないであろう。
【０１１８】
７．ライト・イン・プレイス（ＷＩＰＬ）を使用する最適化
上記の実施形態は、例えば、新たなデータをディスク上の新たな物理的場所に書き込むような、変更の加えられたデータをディスク上の「別の場所に」書き込むファイルシステム４３０を例として説明されている。本発明の他の実施形態によれば、ファイルシステム４３０は、「ライト・イン・プレイス」（ＷＩＰＬ）メカニズムを使用して、データを書き込む場合がある。ＷＩＰＬでは、新たなデータの書き込み要求に応答し、ファイルシステム４３０は、そのデータをディスクに書き込むためのコマンドをＲＡＩＤコントローラモジュール４３６へ送信する。これに応答し、ＲＡＩＤコントローラモジュール４３６は、ディスクから古いデータをメモリ３２４に読み込み、スナップショット機能を提供するために、その古いデータをディスク上のどこかに書き込む。ファイルシステム４３０は、その古いデータが記憶されたメモリ３２４上のアドレスへのポインタを生成し、その古いデータを何時でもアクセスできるようにする。
【０１１９】
引き続き表２を参照すると、新たなデータはディスク１に書き込まれる。従来技術を使用してＷＩＰＬにおける書き込み処理を実現するために、ＲＡＩＤコントローラモジュール４３６は、下記のステップを実施する場合がある。すなわち、
新たなデータを書きまれる場所にあるデータブロックからデータ（例えば、ディスク１に記憶されたデータ）を読み出すステップ；
行パリティを読み出すステップ；
ディスク１に記憶されたデータ、行パリティ、及び新たなデータに対するＸＯＲを計算することにより、新たな行パリティを求めるステップ；
新たなデータをディスク１に書き込むステップ；及び
新たな行パリティを行パリティディスクに書き込むステップである。
【０１２０】
本発明の一実施形態によれば、データのコピーが作成されるときに、データはディスク１からメモリ３２４へ既に読み込まれ、そのデータのコピーの記憶場所へのポインタが作成されているので、そのデータを再度読み出す必要はない。従って、ＷＩＰＬにおいて書き込み要求を完了するために、下記のステップが実施される場合がある。すなわち、
モジュール４３６が、新たなデータを、メモリ３２４に記憶された古いデータとＸＯＲ演算するステップ；
モジュール４３６が、新たなデータをディスク１に書き込むステップ；及び
モジュール４４０が、物理データブロックに変更が加えられたストライプに関するパリティを記憶しているディスク（すなわち、ディスク０）に対し、ＸＰＷｒｉｔｅコマンドを発行するステップである。
【０１２１】
ＸＰＷｒｉｔｅコマンドの実行の結果、ディスク０のモジュール２６０は、下記のステップを実行する。すなわち、
モジュール２６０が、古いパリティをディスクメモリ２７０に読み出すステップ；
モジュール２６０が、ストレージドライバモジュール４３５から、古いデータと新たなデータのＸＯＲ演算の結果を受信するステップ；
モジュール２６０が、先のステップにおけるＸＯＲ演算の結果を、古いパリティとＸＯＲ演算するステップ；及び
モジュール２６０が、そのＸＯＲ演算の結果を、ディスク０上の、コマンド中に示されたパリティブロックに書き込むステップである。
【０１２２】
このように、古いデータは、既にメモリ３２４にコピーされ、古いデータが記憶された記憶場所へのポインタが作成されるので、本発明のこの実施形態によれば、新たなパリティを計算するために古いデータをＲＡＩＤコントローラモジュール４３６によって読み出す必要はなくなる。代わりに、ＲＡＩＤ最適化モジュール４４０は、パリティディスクにコマンドを送信する。
【０１２３】
このように、本発明の種々の実施形態によれば、物理データブロックを変更するための幾つかの特定の読み出し処理は不要になる。これは、空きデータブロックをゼロ化し、古いデータへのポインタを作成し、さらに、パリティを記憶しているディスクに対して送信されるＸＰＷｒｉｔｅコマンドの機能を活用することにより達成される。その結果、回転遅延が幾らか無くなり、システム処理能力が向上する。本発明は、ＲＡＩＤ−４、ＲＡＩＤ−５、ＲＡＩＤ−６、及びＤＡＩＤ−ＤＰのいずれのデータ保護方式において実施することも出来る。
【０１２４】
当然ながら、下記の変形実施形態、及び例は、本発明を網羅的に表現することも、本発明を制限することも意図していない。それらの変形実施形態、及び例は、本発明の種々の実施形態をより深く理解してもらうために提供される。
【０１２５】
本発明は、例示のために、特定の幾つかの実施形態を例として説明されているが、本発明が、記載した実施形態に制限されることはないものと考えられる。当業者であれば、それらの実施形態に対して修正、又は変更を加えた形で本発明を実施することも可能であり、また、添付の特許請求の範囲の思想、及び範囲内にある他の実施形態で本発明を実施することも可能であることが、分かるであろう。
【０１２６】
また、互いに依存関係のない動作は、並列に実施される場合がある。本発明の原理、及びその実用的な実施形態を最もよく説明し、それによって当業者が、本発明、並びに、想定する特定の用途にふさわしい種々の変更が施された実施形態を最もよく利用できるようにする目的で、実施例は選択され、説明された。
【０１２７】
さらに、明細書の到る所における「一実施形態」という語の使用は、必ずしも同じ実施形態を意味してはいない。本発明の幾つかの特定の実施形態について説明したが、本発明をそれらの特定の実施形態に制限してはならない。従って、明細書、及び図面は、制限ではなく、例示とみなすべきである。
【０１２８】
特に断り書きがない限り、本明細書全体を通じて、「処理する」、「計算する」、「求める」、「判定する」、又は「表示する」といった用語の使用は、コンピュータシステムレジスタ、及びメモリ内に物理（例えば電気的）量として表現されるデータを操作し、コンピュータシステム内に物理量として同様に表現される他のデータに変換するコンピュータシステム、又は類似の電子計算装置の動作、及びプロセスを意味する。
【０１２９】
本発明は、本明細書に記載する処理を実施するための装置によって実施することができる。この装置は、必要とされる目的に合わせて特別に構成される場合もあれば、コンピュータに記憶されるコンピュータプログラム（例えば、機械やプロセッサによって実行される一群の命令）によって選択的に駆動され、又は再構成される汎用コンピュータのような機械からなる場合もある。そのようなコンピュータプログラムは、コンピュータ読取可能な記憶媒体に記憶される場合があり、限定はしないが、例えばフロッピー(R)ディスク、光ディスク、及び磁気光ディスクのような任意のタイプのディスク、リード・オンリ・メモリ、ランダム・アクセス・メモリ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード、光カード、あるいは、物理的（例えば、電気的）構成の記憶に適した任意のタイプの媒体に記憶される場合があり、それぞれが、コンピュータシステムバスに結合される。これらの媒体はそれぞれ、媒体を読み出し、又は書き込むための適当なデバイスの使用を通じて、コンピュータシステムバスに結合される場合がある。
【図１Ａ】
2010508604.tif 000005
【図１Ｂ】
2010508604.tif 000006
【図２】
2010508604.tif 000007
【図３】
2010508604.tif 000008
【図４】
2010508604.tif 000009
【図５】
2010508604.tif 000010
【図６】
2010508604.tif 000011
【図７】
2010508604.tif 000012
【図８】
2010508604.tif 000013
【図９】
2010508604.tif 000014
【国際調査報告】
2010508604.tif 000015
2010508604.tif 000016