JPH08263228A - アレイにデータを格納する方法および記憶アレイ・システム - Google Patents

Abstract

(57)【要約】 【課題】 十分なパフォーマンスと信頼性を達成するた
め、ならびに低コスト・ハードウェアＲＡＩＤのパフォ
ーマンスを改善するために、ソフトウェアで実現された
ＲＡＩＤアレイで使用可能なシステムおよび方法を提供
する。 【解決手段】 基本ＲＡＩＤ実施態様の機能強化によっ
て、ソフトウェアＲＡＩＤのための復旧時間が高速化さ
れる。好ましい実施例のこの機能強化では、同様の目的
のためにハードウェアＲＡＩＤが使用するＮＶＲＡＭに
取って代わり、不整合パリティ・グループをマーキング
するためにディスク上に格納されたＰＧＳビット・マッ
プというビット・マップを使用する。また、別の機能強
化によって、順次入出力データ・ストリームが最適化さ
れる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データ記憶システ
ムに関し、より具体的にはソフトウェアまたは低コスト
・ハードウェアで実現した記憶アレイ・システムにデー
タを格納するためのシステムおよび方法に関する。

【０００２】

【従来の技術】独立ディスクの冗長アレイ（ＲＡＩＤ）
は、１つのディスク・ドライブが故障したときに、全ド
ライブに格納された冗長データを使用することによって
ユーザ・データを再生成することができる１組のディス
ク・ドライブである。Patterson, D.、Gibson, G.、お
よびKatz, R. H.によるReliable Arrays of Inexpensiv
eDisks (RAID)（１９８８年６月、ACM SIGMOD Conferen
ce 1988、pp. 109-116）に記載されているように、５つ
のレベルのＲＡＩＤが一般に知られている。ＲＡＩＤレ
ベル５ディスク・アレイは、高い信頼性と可用性を達成
するためにパリティ技法を使用している。１つのパリテ
ィ・ブロックがそのパリティ・グループ内のデータ・ブ
ロックを保護している。パリティ・ブロックは、そのパ
リティ・グループ内のデータ・ブロックについて排他的
論理和（ＸＯＲ）演算を行った結果である。１つのパリ
ティ・グループ内の各ブロックは、アレイの異なるディ
スク・ドライブに格納される。ＲＡＩＤ５では、パリテ
ィ・ブロックがすべてのディスクに（ほかのパリティ・
グループからのデータ・ブロックとともに）格納され
る。

【０００３】ＲＡＩＤ５ディスク・アレイは、単一ディ
スクのクラッシュに対して強固である。１つのディスク
が故障した場合、そのディスク上のデータは、アレイ内
の残りのディスクからデータを読み取って、適切なＸＯ
Ｒ演算を実行することによって再生成することができ
る。

【０００４】データ・ブロックを更新するための要求が
行われた場合、整合性を維持するために対応するパリテ
ィ・ブロックも更新しなければならない。データが修正
されるたびにパリティを変更しなければならないので、
データ・ブロックを更新するためにＲＡＩＤでは、
（１）古いデータの読取り、（２）古いパリティの読取
り、（３）新しいデータの書込み、（４）新しいパリテ
ィの書込みという４回のディスク・アクセスが必要であ
る。１回の更新につき４回のディスク・アクセスが必要
であることは、ＲＡＩＤ５の更新上の不利であると言わ
れることが多い。必要な４回のディスク・アクセスに続
いて、更新の完了がホスト・システムに提示される。

【０００５】一般にＲＡＩＤは、特殊ハードウェアを有
するディスク制御装置内に実現される。ＸＯＲハードウ
ェアは、ＸＯＲ演算を実行してパリティを計算する。キ
ャッシュとも呼ばれる不揮発性ＲＡＭ（ＮＶＲＡＭ）に
よって、ＲＡＩＤのパフォーマンスと信頼性が改善され
ている。このようなＲＡＩＤの実施態様は、ハードウェ
アＲＡＩＤと呼ばれている。低コスト・ハードウェアＲ
ＡＩＤの中には、ＮＶＲＡＭを備えていないものあれ
ば、小型のＮＶＲＡＭを備えているものもある。ソフト
ウェアＲＡＩＤは、純粋にホスト・コンピュータ上で実
行されるソフトウェアで実現されている。ソフトウェア
ＲＡＩＤは特殊ハードウェアにアクセスすることができ
ないので、特殊アルゴリズムを使用する必要が生じるこ
とが多い。特に、ソフトウェアＲＡＩＤでは、不整合パ
リティ・グループのマーキングや電源障害からの復旧時
にハードウェアＲＡＩＤが頻繁に使用するＮＶＲＡＭに
アクセスすることができない。

【０００６】より高度なハードウェアＲＡＩＤでは、書
込みキャッシュ（システムによるアクセスをより容易に
するためにキャッシュでの書込みを維持すること）や高
速書込み（ＮＶＲＡＭに書き込まれたときに書込み動作
が完了したと見なすこと）を実現することによって書込
みパフォーマンスを改善するためにＮＶＲＡＭを使用し
ている。ほかのハードウェアＲＡＩＤでは、不整合パリ
ティ・グループ（新しいデータがすでに書き込まれた
が、新しいパリティがまだ書き込まれていないパリティ
・グループ）のマーキングと更新要求の最中の電源障害
からの復旧のためにだけＮＶＲＡＭを使用する。

【０００７】ソフトウェアＲＡＩＤの例としては、Chan
tal/BusLogic社のParagonシステムやCorel社のCorelＲ
ＡＩＤシステムがある。いずれも、Novell社のNetware
サーバ用のシステムである。

【０００８】ＲＡＩＤ５の現行ソフトウェア実施態様で
は、不整合パリティ・グループを検出して修正するため
に、電源障害またはシステム・クラッシュ後にすべての
ディスク・ブロックを完全に走査する必要がある。ほと
んどの実用実施態様では、復旧時間が長くなることは受
け入れられない。

【０００９】復旧時のディスク障害によって、データが
失われることがある。壊れたディスク上のデータは、通
常、残りのディスクからのデータを使用して再構築され
るはずである。しかし、パリティ・グループが不整合で
ある場合、データを正確に再構築することができない。
復旧時にすべてのパリティ・グループを走査しなければ
ならないことに関連する問題は、パリティ・グループ内
のデータ・ブロックの１つを読み取ることができない場
合（たとえば、ディスク・ブロック上の訂正不能ＥＣＣ
エラー）、パリティ・グループが整合している可能性が
あるので、データ紛失状況が発生することである。走査
しなければならないパリティ・グループが多ければ多い
ほど、データ紛失状況が発生する可能性が高くなる。も
う１つの２次的問題は、データとパリティが逐次書き込
まれ、両方ともディスクに書き込まれるまでロックが保
持されるので、パリティ・グループのロック時間が長く
なりすぎることである。

【００１０】Chen, P. M.他によるRAID: High-Performa
nce, Reliable Secondary Storage,ACM Computing Surv
eys（１９９４年６月、vol 26(2)、pp 145-186）には、
パリティ・グループに対する書込みが行われるたびに、
パリティ・グループが修正されたディスクに標識が書き
込まれるというシステムが提案されている。このような
書込みでは、（１）パリティ・グループが修正されたと
いう標識の書込み、（２）古いデータの読取り、（３）
古いパリティの読取り、（４）新しいデータの書込み、
（５）新しいパリティの書込み、（６）パリティ・グル
ープが修正されていないという標識の書込みという６回
のディスク・アクセスが必要になる。Chenは、不整合に
なっている可能性のあるパリティ・セクタからなる固定
サイズのリストの管理を提案している。このリストは、
ディスク上とメモリ内に維持される。Chenは、グループ
・コミット機構を使用することによってこのリストの維
持に必要なディスク入出力の回数を低減している。この
ため、応答時間が増す反面、スループットが改善されて
いる。

【００１１】一般に、前述のソフトウェアＲＡＩＤの提
案では、ＲＡＩＤに関連する並行性とロックの問題は論
じられていない。このような議論が存在する範囲で、１
つのパリティ・グループに対して複数回の更新が同時に
行われるのを防止するためにロックを使用するという想
定がなされている。また、１つのパリティ・グループに
対する複数回の更新の並行処理を最適化することが望ま
しい。

【００１２】

【発明が解決しようとする課題】本発明の一目的は、十
分なパフォーマンスと信頼性を達成するため、ならびに
低コスト・ハードウェアＲＡＩＤのパフォーマンスを改
善するために、ソフトウェアＲＡＩＤ５アレイで使用可
能なシステムを提供することにある。

【００１３】本発明の一目的は、ソフトウェアＲＡＩＤ
のための復旧時間を高速化する基本ＲＡＩＤアルゴリズ
ムの機能強化を提供することにある。好ましい実施例の
この機能強化では、同様の目的のためにハードウェアＲ
ＡＩＤが使用するＮＶＲＡＭに取って代わり、不整合パ
リティ・グループをマーキングするためにディスク上に
格納されたＰＧＳビット・マップというビット・マップ
を使用する。また、順次入出力データ・ストリームを最
適化するために別の機能強化も提供される。このような
最適化は、ソフトウェアＲＡＩＤが使用する場合もあれ
ば、ハードウェアＲＡＩＤが使用する場合もある。この
ようなシステムおよび方法は、ハードウェアＲＡＩＤの
うち、高速書込み動作のためにＮＶＲＡＭを使用しない
ＲＡＩＤに特に適用可能である。

【００１４】

【課題を解決するための手段】複数の記憶装置からなる
アレイにデータを格納するための方法が提供される。記
憶装置上の複数のブロック位置は、１つのパリティ・グ
ループとして論理的に配置され、１つのパリティ・グル
ープの一部として１つのブロック位置に格納されたパリ
ティ・ブロックは、そのパリティ・グループに格納され
た複数のデータ・ブロックの組合せから論理的に導出さ
れ、１つのパリティ・グループ内の各ブロックは別々の
記憶装置に格納される。複数のパリティ・グループは、
１つのパリティ・グループ・セットにグループ化され
る。記憶装置上のブロック位置に新しいデータ・ブロッ
クを書き込むための要求が受信される。そのブロック位
置に格納されている古いデータ・ブロックが読み取られ
る。新しいデータ・ブロックがそのブロック位置に書き
込まれる。現行書込み以前にパリティ・グループ・セッ
トが未修正状態になっている場合は、そのパリティ・グ
ループ・セットが修正状態になったという標識が記憶装
置に書き込まれる。

【００１５】一実施例では、古いデータ・ブロックと新
しいデータ・ブロックからそのパリティ・グループ用の
変更パリティが計算される。ブロック位置が属している
パリティ・グループ用の古いパリティ・ブロックが読み
取られる。変更パリティと古いパリティから新しいパリ
ティ・ブロックが計算される。記憶装置上の古いパリテ
ィ・ブロックの位置に新しいパリティが書き込まれる。
新しいパリティの書込み後、未修正状態のパリティ・グ
ループごとに、パリティ・グループ・セットが未修正状
態になっているという標識がディスクに書き込まれる。

【００１６】好ましい実施例では、パリティ・グループ
・セットが修正状態になっているときに、ビット・セッ
トを有するビット・マップに各パリティ・グループ・セ
ットが表される。各パリティ・グループ・セットは、パ
リティ・グループ・セットを現在修正している書込み動
作の回数を示すセット・カウンタを有し、セット・カウ
ンタがゼロになると、パリティ・グループ・セット用の
ビットが変更される。

【００１７】システムは、修正されたパリティ・グルー
プ・セットをまず識別することによって、障害から復旧
する。修正されたパリティ・グループ・セット内の各パ
リティ・グループごとに、不整合パリティ・ブロックを
有するパリティ・グループがあれば、そのパリティ・グ
ループのデータ・ブロックに基づいて更新される。

【００１８】他の好ましい実施例では、具体的には順次
データ・ストリームの処理の場合、新しいデータ・ブロ
ックが順次データ・ストリーム内にあるかどうかの判定
が行われる。古いデータ・ブロックと新しいデータ・ブ
ロックからそのパリティ・グループ用の変更パリティが
計算される。書き込むべき新しいデータ・ブロックが先
行する順次データ・ストリーム内になくなるまで、順次
データ・ストリームの処理が続行される。次に、順次デ
ータ・ストリームの一部であるブロック位置が属する各
パリティ・グループごとに、古いパリティ・ブロックが
読み取られる。このようなパリティ・グループのそれぞ
れについて、パリティ・グループ用の変更パリティとパ
リティ・グループ用の古いパリティ・ブロックに基づい
て、新しいパリティ・ブロックが計算される。このよう
なパリティ・グループのそれぞれの新しいパリティ・ブ
ロックは、記憶装置上のそのパリティ・グループ用の古
いパリティ・ブロックの位置に書き込まれる。新しいデ
ータ・ブロックが境界を横切って新しいパリティ・グル
ープ・セットに入ると、パリティ・グループ・セットが
修正状態になっているという標識が設定される。新しい
データの書込み後、未修正状態の各パリティ・グループ
ごとに、パリティ・グループ・セットが未修正状態にな
っているという標識が書き込まれる。

【００１９】好ましい実施例では、古いデータが読み取
られる前に新しいデータ用のブロック位置がロックされ
る。新しいデータが書き込まれた後、このブロック位置
がロック解除される。古いパリティ・ブロックのブロッ
ク位置は、古いパリティが読み取られる前にロックさ
れ、新しいパリティが書き込まれた後でロック解除され
る。

【００２０】好ましい実施例では、記憶アレイ・システ
ムが提供される。この記憶アレイは複数の記憶装置を含
み、それぞれの記憶装置は複数のブロック位置を含む。
記憶装置上の複数のブロック位置から複数のパリティ・
グループが論理的に編成され、そのパリティ・グループ
は１つのパリティ・グループ・ブロック位置に格納され
たパリティ・ブロックを含み、そのパリティ・ブロック
はパリティ・グループに格納された複数のデータ・ブロ
ックの組合せから論理的に導出され、１つのパリティ・
グループ内の各ブロックは別々の記憶装置に格納され
る。複数のパリティ・グループ・セットは、複数のパリ
ティ・グループからそれぞれ編成される。記憶装置上の
ブロック位置に新しいデータ・ブロックを書き込み、そ
のブロック位置に格納された古いデータ・ブロックを読
み取るための手段が提供される。パリティ・グループ・
セットが未修正状態になっているという標識を記憶装置
に書き込むための手段が提供される。パリティ・グルー
プ用の古いパリティ・ブロックを読み取り、古いデータ
・ブロック、古いパリティ・ブロック、新しいデータ・
ブロックからパリティ・グループ用の新しいパリティを
計算し、記憶装置上の古いパリティ・ブロックの位置に
新しいパリティを書き込むための手段が提供される。ま
た、パリティ・グループ・セットが未修正状態になって
いるという標識を記憶装置に書き込むための手段も提供
される。

【００２１】

【発明の実施の形態】図１を参照すると、ソフトウェア
で実現したＲＡＩＤシステムは、中央演算処理装置（Ｃ
ＰＵ）１４に接続されたランダム・アクセス・メモリ
（ＲＡＭ）１２と、入出力バスへのインタフェース１６
とを有するホスト・コンピュータ１０を有する。ホスト
・システムは、マイクロ・チャネルまたは他の通信リン
ク２１を介して複数のディスク・ドライブからなるアレ
イ２０と通信する。ディスク・ドライブ２０は、ＲＡＭ
２３とＣＰＵ２４とを含むＳＣＳＩアダプタ２２によっ
て制御される。また、このアダプタは、不揮発性キャッ
シュ（ＮＶＲＡＭまたは不揮発性記憶装置ＮＶＳとい
う）１８を含むこともできる。

【００２２】ソフトウェアで実現したＲＡＩＤのＲＡＩ
Ｄ機能は、ディスク・アダプタまたは個別の制御装置で
制御されるのではなく、ＲＡＭ１２にロードされたソフ
トウェアを使用してホスト・システム１０によって制御
される。

【００２３】ホスト・システム２６上で動作するアプリ
ケーション・プログラムは、ドライブ２０に格納された
データを読み書きするための要求を出す。このデータ
は、装置アダプタ３０を介してファイル・システム２７
および論理ボリューム・マネージャ２８を使用して位置
が特定される。通常、ソフトウェアＲＡＩＤは、オペレ
ーティング・システムのデバイス・ドライバとしてまた
はオペレーティング・システムの論理ボリューム・マネ
ージャ（ＬＶＭ）内に、ファイル・システムの下に実現
される。

【００２４】図２を参照すると、１〜５と表示された５
つのディスク・ドライブ２０からなる組が４＋Ｐアレイ
として編成されている。複数の数字からなる各垂直列３
２はディスク・ドライブを表す。各参照番号３３はデー
タ・ブロックを表し、各水平行３４はパリティ・グルー
プを表す。複数の連続ブロックからなる次のグループが
第２のディスクに格納される前に、ディスクに格納され
る連続データ・ブロックの数はさまざまである。Ｘ個の
連続ブロックからなる各組は１つのストライプ・ユニッ
トを構成する。パリティ・ストライプ・ユニットは、Ｘ
＝２の場合のＰ１とＰ２のように、ディスクからのＸ個
のパリティ・ブロックからなる連続した組である。１つ
のストライプは、Ｎ個のディスクからのＮ個の対応する
ストライプ・ユニットから構成される。Ｘ個の連続パリ
ティ・ブロックは１つのストライプを構成する。典型的
な実施態様では、１つのストライプ・ユニットが８つの
ブロックの倍数から構成されることになる。したがっ
て、１つのストライプは、８つのパリティ・グループの
倍数から構成される。

【００２５】図２に示すように、パリティ・ブロック３
６の位置はトラックごとにディスク・ドライブ間を循環
する。

【００２６】データ優先方法 たとえば、ディスクＩ上のブロックＢのパリティがディ
スクＪ上のブロックＢであり、古いパリティ値がＰでこ
れをＰ'に変更する必要がある場合、ホストがディスク
Ｉ上のブロックＢを書き込んで（更新して）その値をＤ
からＤ'に変更するための要求を出すと、書込み要求を
満足するために以下のステップが行われる（データ優先
方法という）。 （１）アレイ内のすべてのディスク上のブロックＢから
構成されるパリティ・グループをロックする。 （２）並行して、ディスクＩからブロックＢ（古いデー
タ）を読み取り、ディスクＪからブロックＢ（古いパリ
ティ）を読み取るための要求を出す。多くのディスク実
施態様により、この書込みを連鎖して、ディスクＩのブ
ロックＢに対する前回の読取りと同時に出すことができ
る。 （３）ディスクＩ上のブロックＢの読取り後に次のディ
スクの回転中に行われるように、できるだけすみやかに
ディスクＩ上のブロックＢにＤ'を書き込むための要求
を待ち行列化する。 （４）Ｄ'が確実にディスクに書き込まれた後、できる
だけすみやかに「完了」をシステムに返す。 （５）ＤまたはＰのどちらが先に使用可能になったかに
よって決まる順序で、Ｄ'とＤおよびＰとのＸＯＲ演算
を実行することによってＰ'を計算する。 （６）ディスクＪのブロックＢにＰ'を書き込む。この
ステップは、Ｄ'がディスクＩのブロックＢに確実に書
き込まれるまで開始する必要はない。 （７）パリティ・グループをロック解除する。

【００２７】上記のステップの間に電源が故障する可能
性がある。電源障害から復旧したら、すべてのパリティ
・グループを走査して、パリティの整合性を確認する必
要がある。パリティ・グループの整合性を判定するた
め、以下の手順が実行される。 （１）各パリティ・グループごとに、すべてのデータ・
ブロックのＸＯＲをとって、予期パリティを生成し、こ
れをパリティ・ブロックと比較する。（２）パリティが
整合していない（予期パリティが実際のパリティ・ブロ
ックと等しくない）場合は、前に計算した予期パリティ
をディスク上のパリティ・ブロックに書き込むことによ
ってパリティを整合させる。

【００２８】より高速の代替態様では、それを先に検査
せずに、計算したパリティをディスク上のパリティ・ブ
ロックに必ず書き込むだけである。これは、通常動作中
は必ずデータが先に書き込まれ、次にパリティが書き込
まれるからである。データが書き込まれる前に電源が故
障した場合は、パリティが整合することになる。データ
は書き込まれたがパリティが正常に書き込まれる前に電
源が故障した場合は、復旧時にパリティを整合させるこ
とが適当である。データを書き込んでいる最中に電源が
故障した場合は、データ・フィールドが不要情報を含む
可能性がある。しかし、書込み要求の完了がホストに伝
達されていないので、ホスト・ソフトウェアはこのデー
タを復旧することができる。これは、標準の（非ＲＡＩ
Ｄ）ディスクでも発生する問題である。

【００２９】マシンへの電源を切断する前にユーザが規
則正しい「遮断」を行った場合、長い復旧時間を短縮す
ることができる。遮断中、ソフトウェアＲＡＩＤは、進
行中の更新をすべて完了し、すべてのパリティ・グルー
プを整合させ、「整合」フラグをディスクに書き込む。
復旧すると、ＲＡＩＤソフトウェアは、ディスク上の既
知の位置から整合フラグを読み取る。フラグが設定され
ている場合、ディスク上のフラグをオフにするが、復旧
が不要であることが分かる。フラグがリセットされてい
る場合、前述のように長い復旧の実行にとりかかる。こ
れは、システム・クラッシュまたは電源障害の場合の
み、長い復旧が開始されることを意味する。

【００３０】並列方法 データ優先書込み方法に代わるものとしては、並列書込
み方法がある。これは、ロックが保持される時間がより
短くなるように、データとパリティの書込みを並行して
続行できるようにするものである。この並列性は、ディ
スク・ブロックにタイム・スタンプを添えることによっ
て達成される。ブロックの先頭に追加されたフィールド
と、そのブロックの末尾で繰り返される同じフィールド
によって、書込みの最中の電源障害によるブロックの部
分書込みが検出される。２つのフィールドが同一ではな
い場合はブロックの部分書込みが検出され、同一である
場合はブロックが自己検証する。

【００３１】復旧時にタイム・スタンプは、不整合パリ
ティ・グループの不整合ブロックを正確に示すための手
段になる。たとえば、ディスク２のタイム・スタンプが
ディスク１の対応するデータ・ブロックのタイム・スタ
ンプより遅いことをパリティ・ブロックが示している場
合、ディスク１のデータ・ブロックは古いレベルのもの
なので、最新のものにする必要がある。タイム・スタン
プの使用により、より積極的な更新アルゴリズムが可能
になり、データとパリティが並行して書き込まれる。

【００３２】２ビットのタイム・スタンプを使用し、そ
のタイム・スタンプが実際は新しい書込みが行われるご
とに（０まで）増分するカウンタであることが好まし
い。

【００３３】ホスト書込み要求を満足するために、以下
のステップが実行される。 （１）同じパリティ・グループへのホスト書込みが遅れ
ないようにするために、アレイ内のすべてのディスクか
らのブロックＢから構成されるパリティ・グループをロ
ックする。 （２）並行して、ディスクＩからブロックＢ（古いデー
タ）を読み取り、ディスクＪからブロックＢ（古いパリ
ティ）を読み取るための要求を出す。 （３）（ＤまたはＰのどちらが先に使用可能になったか
によって決まる順序で）Ｄ'とＤおよびＰとのＸＯＲを
とり、Ｐ'を生成する。 （４）ディスクＩ上のブロックＢの読取り後に次のディ
スクの回転中に行われるように、できるだけすみやかに
ディスクＩ上のブロックＢにＤ'を書き込むための要求
を待ち行列化する。これは、前のステップが完了する前
に行われることもある。Ｄ'に伴うタイム・スタンプ
は、Ｄに伴うタイム・スタンプを増分することによって
得られる。Ｄ'の書込みは、連鎖してＤの読取りと同時
に出すことはできない。 （５）ディスクＪのブロックＢに（生成されるとすぐ
に）Ｐ'を書き込むための要求を待ち行列化する。Ｐ'
は、Ｄ'の書込みと並行して書き込むことができる。Ｐ'
に伴うタイム・スタンプは、Ｐに関連する複数のタイム
・スタンプのうちの適切なものを増分することによって
生成される。 （６）Ｄ'またはＰ'のいずれか早い方が確実にディスク
に書き込まれた直後に「完了」をシステムに返す。 （７）Ｄ'またはＰ'のいずれか遅い方が確実にディスク
に書き込まれた後で、パリティ・グループをロック解除
する。

【００３４】上記のステップの間に電源が故障する（ま
たはシステムがクラッシュする）可能性がある。復旧し
たら、すべてのパリティ・グループを走査して、パリテ
ィが整合していることを検査する。パリティが整合して
いない場合は、以下のようにパリティを整合させる。 （１）まず、すべてのブロックが自己検証していること
を確認する。自己検証している場合は、パリティ・ブロ
ック内の対応するタイム・スタンプは異なるタイム・ス
タンプを有するデータ・ブロックを検出し、データ・ブ
ロックまたはパリティ・ブロックのうち、タイム・スタ
ンプが早い方を修正する。（２）１つのブロック（デー
タ・ブロックまたはパリティ・ブロックのいずれか）だ
けが自己検証していない場合は、パリティ・グループの
残りのメンバーを使用してそれを計算する。（２）２つ
のブロック（１つのデータ・ブロックとパリティ・ブロ
ック）がどちらも自己検証していない場合（データ・ブ
ロックとパリティ・ブロックの両方が部分的に書き込ま
れ、データとパリティの両方が不要情報になったときに
電源障害が発生した場合）は、不要情報データ・フィー
ルドの任意のタイム・スタンプを使用し、両方のブロッ
クを自己検証させる。この自己検証データ・ブロックと
残りのデータ・ブロックを使用して、整合パリティ・ブ
ロックを生成する。書込み要求の完了がホストに伝達さ
れていないので、データ・ブロックがまだ不要情報を含
んでいても問題にはならない。ホスト・ソフトウェアは
このデータを復旧することができる。

【００３５】ロックの単位 典型的な更新では４Ｋバイト（８つのセクタ）を修正す
る可能性があるので、８つのパリティ・グループのロッ
クが必要になる可能性がある。更新の並行性を犠牲にし
てロックを高速化するため、より大きい単位をロックす
ることができる。

【００３６】ロックのタイプ 前の更新要求による更新の最中であるデータ・ブロック
への読取り要求がデータ・ブロックの更新した値を返さ
なければならない場合、読取り要求もロックを獲得する
必要がある。この場合、読取り要求は共用ロックを獲得
するはずである。多くの共用ロックは、特定のパリティ
・グループ、ストライプ、または適切と見なされるすべ
てのロック単位に対して保持することができる。このた
め、１つのロック単位に対して多くの読取りを同時に実
行することができる。これに対して、更新要求は、他の
更新または読取り要求を同時に行えないように、排他ロ
ックを獲得する。

【００３７】待ち行列としてのロックの実現 ロックを待っている要求について、待ち行列を使用す
る。たとえば、同じブロック（複数も可）に対する２つ
の並行更新、または同じブロック（複数も可）に対する
並行読取り更新の場合、これらの要求を受け取った順に
実行する必要がある可能性もある。これは、通常、待ち
行列（ロック）ヘッダと、（ロック単位当たりの）待機
要求の待ち行列とによって実施される。待ち行列ヘッダ
を編成して位置を特定するための最も便利な方法は、ハ
ッシュ・テーブルによる方法である。待ち行列ヘッダ
（および待ち行列）は、対応するパリティ・グループま
たはストライプに対する未解決の要求が存在する場合
（または最近、要求が存在した場合）のみメモリを占有
するはずである。

【００３８】待ち行列内の複数の要求が機能することも
可能である。たとえば、待ち行列内のすべての要求が読
取り要求である場合、これらはすべて実行することがで
きる。しかし、更新要求が実行を開始すると、待ち行列
内の他の要求は自分の番が来るまで待たなければならな
い。

【００３９】並行性の改善のための機能強化 同じパリティ・グループ内のデータ・ブロックに対する
複数の並行更新を防止するパリティ・グループ・ロック
に代わるものとしては、データ優先アルゴリズムのため
にパリティ・グループ内のブロックに対する複数の並行
更新を可能にする方法がある。データの読取りおよび書
込みと、パリティの読取りおよび書込みは、同じブロッ
クへの他のディスク入出力によって中断することができ
ない原始的な（アトミック）動作として扱われる。デー
タ・ブロックへのホスト読取りは、データの読取りおよ
び書込みの間に行うこともできる。

【００４０】図３に示すように、個々のブロックにロッ
クが置かれる。まず、データに関するロックを獲得し、
次にその順序でパリティに関するロックを獲得する。デ
ータおよびパリティに関するロックをそれぞれ獲得した
後で、データおよびパリティ・ディスクに関する動作を
開始する。ディスクへの新しいデータと新しいパリティ
の書込みをそれぞれ完了した後、データおよびパリティ
・ロックを解除する。

【００４１】並行性を強化したデータ優先方法では、以
下のステップを実施する。 （１）データ（ディスクＩのブロックＢ）に関するロッ
クを獲得する（３６）。必要であれば待機する。 （２）ディスクＩ上のブロックＢからＤ（古いデータ）
を読み取り、ディスクＩのブロックＢにＤ'（新しいデ
ータ）を書き込むためのアトミック要求対を出す（３
７）。この要求は、同じディスク上の他のブロックへの
要求と、このブロック用のホスト読取りによって中断す
ることができる。 （３）パリティ（ディスクＪのブロックＢ）に関するロ
ックを獲得する（３８）。必要であれば待機する。この
ロックは、データに関するロックを獲得した後で獲得し
なければならない。 （４）ディスクにＤ'を確実に書き込んだ後で、できる
だけすみやかにシステムに完了を返す（３９）。これ
は、パリティに関するロックを獲得する前に行われる場
合もある。 （５）ディスクにＤ'を書き込んだ後、ただちにデータ
に関するロックを解除する（４０）。これは、パリティ
に関するロックを獲得する前に行われる場合もある。 （６）Ｄ'とＤのＸＯＲをとり、デルタＰを生成する
（４１）。これは、ディスクからＤを読み取った後、た
だちに行われる場合もある。 （７）ディスクＪからブロックＢ（古いパリティ）を読
み取るための要求を出す（４２）。これは、パリティに
関するロックを獲得した後、いつでも行うことができ
る。 （８）古いパリティとデルタＰとのＸＯＲとして新しい
パリティＰ'を計算する（４３）。 （９）ディスクＪのブロックＢにＰ'を書き込むための
要求を出す（４４）。この要求は、古いパリティの読取
り後、ブロックＢに対する次の要求でなければならない
（パリティに関するロックがこれを保証する）。（１
０）パリティに関するロックを解除する（４５）。

【００４２】並行性の強化を達成するための方法とし
て、より単純であるがより制限的なもう１つの代替方法
は、データおよびパリティの読取りおよび書込みを、他
のディスク入出力によって中断できないアトミック動作
として扱うことである。ホスト読取りによっては、この
ために応答時間が減速する可能性もあるが、ロックを必
要としないので、その実現はより簡単である。

【００４３】個々のブロックのロックに代わるもう１つ
の代替方法は、ストライプ単位をロックすることであ
る。これは、並行性が低下されるものの、ロック・オー
バヘッドを低減するものである。というのは、典型的な
更新要求では（データ・ブロックに関する８つのロック
と、パリティ・ブロックに関する８つのロックの代わり
に）１つのデータ・ストライプ単位に関して１つのロッ
クと、１つのパリティ・ストライプ単位に関して１つの
ロックのみ必要とするからである。

【００４４】特定のブロックに対するＮ個の更新要求が
存在するかどうかを確認することによって、前述の並列
方法も、複数の並行更新を可能にするように強化するこ
とができる。この場合、データに対するＮ回の読取りお
よび書込みを処理する順序は、パリティに対するＮ回の
読取りおよび書込みを処理する順序と同じである。

【００４５】以下のステップは、並列方法を使用して複
数の並行更新用のブロック・レベルのロックを実施する
ものである。 （１）データに関するロックを獲得し、次にその順序で
パリティに関するロックを獲得する。 （２）データに関するロックを獲得した後、データ・デ
ィスクに対する操作を開始する。 （３）パリティに関するロックを獲得した後、パリティ
・ディスクに対する操作を開始する。 （４）両方のロックを獲得するまでいずれのロックも解
除しない。 （５）ディスクへの新しいデータの書込みが完了した
後、データ・ロックを解除する。ディスクへの新しいパ
リティの書込みが完了した後、パリティ・ロックを解除
する。この方法がデータ優先アルゴリズムの方式と異な
る点は、両方のロックを獲得するまでロックを解除でき
ないことだけである。

【００４６】ストライプ単位ロックを使用するには、並
行性とロック・オーバヘッドの低減とのトレードオフを
伴う可能性がある。

【００４７】並列アルゴリズムのために並行性の強化を
達成するためのもう１つの代替方法は、別の更新要求の
処理を開始する前にそれぞれのディスクでの更新要求に
ついて、データとパリティ両方の操作を開始するかまた
は待ち行列化することである。

【００４８】ロックを行わない並行性強化並列方法は以
下の通りである。 （１）ディスクＩからブロックＢ（古いデータ）を読み
取り、ディスクＩのブロックＢにＤ'（新しいデータ）
を書き込むためのアトミック要求を出す。 （２）古いデータが使用可能になるとただちに、Ｄ'と
ＤのＸＯＲをとり、デルタＰを生成する。 （３）古いデータが使用可能になるとただちに、ディス
クＪからブロックＢ（古いパリティ）を読み取るための
要求を出す。 （４）ステップ１〜３を完了するまで、別のホスト要求
を許可しない。 （５）古いパリティとデルタＰとのＸＯＲとして新しい
パリティＰ'を計算する。ディスクＪのブロックＢにＰ'
を書き込むための要求を出す。この要求は、古いパリテ
ィの読取り後、次に実行されるものでなければならな
い。 （６）Ｄ'またはＰ'のいずれかがディスクに書き込まれ
た後、ただちに要求側に「完了」を出す。

【００４９】パリティ・グループ・セット ソフトウェアＲＡＩＤは、両方ではなく（不整合状態に
なっている）データまたはパリティのいずれかが更新さ
れるような修正処理中のパリティ・グループのマーキン
グのためのＮＶＲＡＭを備えていない。システム障害が
発生した場合には、パリティ・グループの整合性を保護
するために、ディスクに対してさらに書込みを行う必要
がある。システム障害の場合、修正されたすべてのパリ
ティ・グループは（前述のように）整合状態にする必要
がある。図２に示すように、本発明の好ましい実施例
は、複数のパリティ・グループ３４を集めてパリティ・
グループ・セット（ＰＧＳ）４８を形成するようになっ
ている。

【００５０】ＰＧＳは、更新処理中である可能性のある
パリティ・グループを識別するための集合ユニットとし
て使用する。更新処理中である可能性のあるパリティ・
グループを含むと思われるＰＧＳとして標識が識別した
ＰＧＳ内のパリティ・グループのみ、修正して整合状態
にする必要がある。ＰＧＳは、１つのストライプまたは
それ以上であることが好ましい。たとえば、３００００
個のパリティ・グループを有するアレイでは、それぞれ
のＰＧＳが１００個のパリティ・グループを含む、３０
０個のパリティ・グループ・セット（ＰＧＳ）を形成す
ることができる。最初の１００個のパリティ・グループ
は第１のＰＧＳ内に入り、次の１００個のパリティ・グ
ループは第２のＰＧＳに入り、以下同様になるはずであ
る。

【００５１】図４を参照すると、それぞれのビット５１
が１つのＰＧＳを表すビット・マップ５１が使用されて
いる。ＰＧＳ内のいずれかのパリティ・グループが整合
していない可能性がある場合、ＰＧＳ用のビットが設定
される。このビット・マップはメモリ内のディスク上で
管理されるが、ディスク・バージョンはメモリ・バージ
ョンを密接に追跡するが、２つのバージョンがいつも同
一であるわけではない。パリティ・グループが整合して
いない場合、ビット・マップのディスク・バージョンで
はそのビットが設定されることになる。電源障害の場合
は、ディスクのＰＧＳビット・マップにビットが設定さ
れたＰＧＳのみ、走査する必要がある。

【００５２】ＰＧＳビット・マップ５０は単一ディスク
・ブロック５２に収まることが好ましい。ＰＧＳビット
・マップ５０の２つのコピーがディスクに格納され、交
互に書き込まれる。このため、ＰＧＳビット・マップ・
ブロックの書込みの最中の電源障害による問題が回避さ
れる。最新コピーを判定し、ＰＧＳブロックの部分書込
みを検出するため、ＰＧＳビット・マップ・ブロックの
最初のバイトと最後のバイトにタイム・スタンプ５４が
格納される。最初のバイトのタイム・スタンプが最後の
バイトのタイム・スタンプと同じではない場合、部分書
込みが検出される。電源障害後に復旧したら、両方のＰ
ＧＳブロックが自己検証してる場合は、両方のＰＧＳブ
ロックを読み取って最新タイム・スタンプがついている
バージョンを決定する。ＰＧＳディスク・ブロックの一
方が一部分だけ書き込まれ、その結果、自己検証してい
ない場合は、もう一方のＰＧＳブロックを復旧に使用す
る。２つのＰＧＳディスク・ブロックは、アレイ内の既
知の固定位置に格納される（たとえば、アレイの第１の
ディスクのブロック０とブロック１）。ＰＧＳビット・
マップを保管するディスクが故障した場合は、ＰＧＳビ
ット・マップを保管するために別のディスクが選択され
る。電源障害後、どのディスクがどのアレイに属してい
るかなど、他の構成情報を検出するのに使用するものと
同様の機構を使用して、ビット・マップを含むディスク
が検出される。

【００５３】さらに、各ＰＧＳごとに、そのＰＧＳに対
して進行中の並行更新の数を示すカウントが管理され
る。

【００５４】パリティ・グループ・セットのビット・マ
ップとともに、データ優先または並列アルゴリズムのい
ずれかを使用して、書込み動作の復旧パフォーマンスを
改善するためのプロセスが使用される。このプロセスで
は、ビット・マップまたはＰＧＳカウントあるいはその
両方を検査または変更するために、ＰＧＳビット・マッ
プに関するグローバル・ロックを使用する。また、強制
フラグ、書込み進行中フラグ、変更済みフラグという３
つのグローバル・フラグも使用する。第１のフラグが設
定されている場合は、ＰＧＳビット・マップをただちに
強制的にディスクに書き込まなければならないことを意
味する。このフラグは、ＰＧＳビット・マップ内の１つ
のビットが設定されている場合に必ずオンになる。第２
のフラグが設定されている場合は、ビット・マップがデ
ィスクに書き込まれている最中であることを意味する。
第３のフラグが設定されている場合は、ビット・マップ
が最後の書込み以降、変更されたことを意味するが、そ
の変更をただちにディスクに書き込む必要はない。これ
は、ビット・マップの最後の書込み以降、ＰＧＳビット
・マップ内の１つまたは複数のビットがリセットされた
が、いずれも設定されていない場合である。

【００５５】データを書き込むためのプロセスについて
は、図５の流れ図６０を参照して説明する。

【００５６】まず、データまたはパリティがディスクに
書き込まれる（６１）まで、データ優先方法または並列
方法用に概略を示したステップをたどる。パリティ・グ
ループ・ロックの書込み後であって、データまたはパリ
ティの書込みを開始する前の任意の時点で、ＰＧＳビッ
ト・マップに関するロックを獲得する（６２）。次に、
このＰＧＳ用のビットが設定されているかどうか（６
３）を確認するためにＰＧＳビット・マップを検査す
る。すでに設定されている場合は、次のステップに移行
する。設定されていない場合は、このＰＧＳ用のビット
・マップにビットを設定し（６４）、強制フラグを設定
する。書込み進行中フラグが設定されていない場合は、
ＰＧＳビット・マップ書込みプロセスを始動するこのフ
ラグを設定する。書込み進行中フラグがすでに設定され
ている場合は、ＰＧＳビット・マップ書込みプロセスが
現在、そのビット・マップに対して前に行った変更を書
き込んでいる。したがって、古い書込みが完了すると、
そのビット・マップに対する新しい変更を含む書込み要
求が自動的に開始される（詳細については以下を参照の
こと）。次に、適切なＰＧＳ用のＰＧＳカウントが増分
される（６５）。その後、ＰＧＳビット・マップがロッ
ク解除される（６６）。

【００５７】ＰＧＳビット・マップにまだビットが設定
されていない場合は、書込み動作の残りを続行する（６
８）前に、そのビットが設定されたＰＧＳビット・マッ
プがディスクに書き込まれたことをＰＧＳビット・マッ
プ書込みプロセスが報告するまで待機する。

【００５８】パリティ・グループの更新（７０）後、Ｐ
ＧＳビット・マップがロックされ、適切なＰＧＳ用のＰ
ＧＳカウントが減分される（７１）。カウント＝０の場
合（７２）は、ＰＧＳビット・マップの適切なビットが
リセットされる。変更済みフラグが設定され、ＰＧＳビ
ット・マップがロック解除される。

【００５９】ビット・マップ書込みプロセスは、以下の
ように機能する。 （１）書込み進行中フラグが設定されるまで待つ。 （２）ＰＧＳビット・マップをロックする。強制フラグ
を検査する。設定されていない場合は、書込み進行中フ
ラグをリセットし、ＰＧＳビット・マップをロック解除
し、復帰する。設定されている場合は、ディスクに書き
込むＰＧＳビット・マップの個別のメモリ・コピーを作
成し、強制フラグと変更済みフラグをリセットし、ＰＧ
Ｓビット・マップをロック解除する。 （３）ＰＧＳビット・マップとともに書き込むタイム・
スタンプを増分し、代替位置を指し示すようにビット・
マップを書き込むアドレスを変更する。 （４）ＰＧＳビット・マップのメモリ・コピーをディス
クに書き込む。 （５）完了したら、書込み完了を通知する。

【００６０】強制フラグがオンになっていなくても、変
更済みフラグがオンの場合には、ＰＧＳビット・マップ
をディスクにダンプするためにビット・マップ書込みプ
ロセスを使用することもある。更新要求当たり必要な４
回のディスク入出力に加え、５回目のディスク入出力を
使用して、ＰＧＳビット・マップを書き込むこともあ
る。この５回目のディスク入出力は、ＰＧＳビット・マ
ップの適切なビットがまだ設定されていない場合のみ必
要になる。すなわち、選択したＰＧＳに対する更新がま
だ進行していない場合のみ、５回目の入出力が必要にな
る。また、ＰＧＳビット・マップの適切なビットがまだ
設定されていなくても、５回目の入出力が不要な場合も
ある。ビット１を設定して、ＰＧＳビット・マップの１
回目の書込みを開始するようなＰＧＳ１の更新を行う
と、ディスク入出力が５回行われる。ＰＧＳ２を更新す
ると、ビット２が設定され、ＰＧＳビット・マップをも
う１回書き込むことが必要になる。しかし、ビット・マ
ップ書込みプロセスがＰＧＳビット・マップの書込みに
使用されているので、この２回目の書込みはただちに開
始されるわけではない。ＰＧＳビット・マップの１回目
の書込みが完了する前にＰＧＳの更新がすべて受領され
ると、ＰＧＳの各ビットもビット・マップに設定され、
ビット・マップの２回目のディスク書込みでは、このよ
うなすべての更新要求のためのビット・マップ書込みが
１回のディスク入出力に結合される。したがって、必要
な１回の余分なディスク入出力が後続の更新要求間で共
用され、それぞれの更新要求が個別に５回のディスク入
出力を必要とするわけではない。

【００６１】ＰＧＳサイズが小さい場合、通常動作中に
余分なディスク入出力が行われる代わりに復旧時間が改
善される。ＰＧＳサイズが大きい場合は、復旧時間が長
くなるが、通常の更新パフォーマンスは改善される可能
性がある。

【００６２】分散ＰＧＳビット・マップ 可能性は低いが、ＰＧＳビット・マップを書き込む速度
によってアレイのスループットが制限される可能性もあ
る。これは、他のディスク入出力がアレイの全ディスク
間に分散され、ＰＧＳビット・マップの書込みはすべて
１個のディスクに対して行われるからである。

【００６３】ある代替実施例では、ＰＧＳビット・マッ
プがアレイ内の全ディスク間に分散される。たとえば、
アレイにＮ個のディスクがある場合、第１の１／Ｎ Ｐ
ＧＳに関連するビット・マップはディスク１に（その代
替位置とともに）格納することができ、第２の１／Ｎ
ＰＧＳに関連するビット・マップはディスク２に格納す
ることができ、以下同様になる。この分散の場合、アレ
イ内のディスク当たり２つのＰＧＳディスク・ブロック
が存在し、ＰＧＳビット・マップ書込みがボトルネック
になる可能性は低い。

【００６４】好ましい代替実施例（図４に示す）では、
ビット・マップ全体がＮ個のディスクすべてに複写さ
れ、最初にディスク１にビット・マップを書き込み、次
にディスク２、・・・、次にディスクＮ、次にディスク
１に戻り、以下同様というようにビット・マップをディ
スクに書き込む順序を確立する。Ｎ個のディスクにビッ
ト・マップをＮ回書き込む作業を同時に進行させること
はできず、これが可能な場合には、電源障害によって、
ビット・マップのＮ個のディスク・コピーすべてが破壊
されてしまう。ただし、Ｎ−１回の並行ビット・マップ
書込みは可能である。電源障害後、最新のビット・マッ
プが最新の自己検証タイム・スタンプを備えたビット・
マップであると判定することができる。ディスクが故障
した場合は、このディスクは書込みローテンションから
外さなければならず、電源障害後の始動中にアクセス可
能になるようにこの情報を記録しなければならない。こ
の情報は、始動時に必要な他のアレイ構成情報を記録す
るのと同じ方法で記録することができる。

【００６５】障害から復旧するためのプロセスは図７に
示す。ビット・マップにビットが設定されているパリテ
ィ・グループ・セットの場合（８０）、それぞれのパリ
ティ・グループを走査して不整合パリティ・グループを
識別する。（前述のように）不整合パリティ・グループ
を整合させて（８２）、標準のＲＡＩＤ５復旧手順に基
づいて障害を訂正する（８４）。

【００６６】順次作業負荷の機能強化 順次更新を含む作業負荷について、パフォーマンスを改
善することができる。すなわち、要求ストリームが、ブ
ロック１更新、ブロック２更新、・・・、ブロックＮ更
新という形式になっている場合である。複数の連続デー
タ・ブロックをディスク間にストライプ化するための方
法はいくつかある。１つは、１つのストライプが１つの
パリティ・グループと等しくなるようにデータ・ブロッ
クをストライプ化する方法である。別の方法としては、
複数の連続データ・ブロックを１個のディスクに格納し
てから、次の複数の連続ブロックを２個目のディスクに
格納し、以下同様に格納することができる。すなわち、
１つのストライプを複数のパリティ・グループにするこ
とができる。これは、データ・ストライプ・インタリー
フ深さがＮであるという。

【００６７】パリティ・キャッシュの最適化 本発明の一実施例では、ディスクに書き込む必要がある
が、まだ書き込まれていないパリティを格納するため
に、パリティ・キャッシュ（使用可能な場合）を使用す
る。以下のステップは、データ優先方法で前述した書込
み動作のためのパリティ・キャッシュを実現するもので
ある。 （１）アレイ内のすべてのディスクからのブロックＢか
ら構成されるパリティ・グループをロックする。 （２）ディスクＩからブロックＢ（古いデータ）を読み
取るための要求を出す。古いパリティがないかどうかパ
リティ・キャッシュを検査する。パリティ・キャッシュ
に古いパリティがない場合は、ディスクＪからブロック
Ｂ（古いパリティ）を読み取るための要求を出す。 （３）ディスクＩのブロックＢの読取り後、次のディス
ク回転中に行われるように、できるだけすみやかにディ
スクＩのブロックＢにＤ'を書き込むための要求を待ち
行列化する。 （４）ディスクにＤ'が確実に書き込まれた後、できる
だけすみやかにシステムに完了を返す。 （５）ＤまたはＰのどちらが先に使用可能になったかに
よって決まる順序でＤ'とＤおよびＰとのＸＯＲをと
り、Ｐ'を生成する。このＸＯＲは、前のステップが実
行される前に開始することもできる。 （６）パリティ・キャッシュにＰ'を保管する。ディス
クにはまだ書き込まない。 （７）パリティ・グループをロック解除する。

【００６８】このプロセスは、データ優先方法またはＰ
ＧＳビット・マップを使用するデータ優先方法のいずれ
にも適用することができる。（図６の８８に示すよう
に）ＰＧＳビット・マップを使用する場合、複数の更新
からなる順次ストリームがすべて同じＰＧＳに入るので
あれば（そうなる可能性が高い）、ＰＧＳビット・マッ
プの書込みに必要なディスク入出力は１回だけである。
ＰＧＳビット・マップを使用すると、パリティが実際に
ディスクに書き込まれるまで、ビット・マップのビット
はリセットされない。

【００６９】ディスクが故障し、アレイが低下動作モー
ドに入った場合は、パリティ・キャッシュがディスクに
書き込まれ、予備のディスクへの故障したディスクの再
構築が完了するまで、後続のすべての更新要求はパリテ
ィ・キャッシュの最適化を行わずに実行される。これに
より、アレイがまだ低下モードになっている間に電源障
害またはシステム・クラッシュが発生した場合に失う恐
れのあるデータの量が最小限になる。

【００７０】デルタ・パリティ・キャッシュの最適化 本発明の他の実施例では、パリティ・キャッシュの最適
化を実現し、（図６の９０に示すように）順次更新スト
リームが切断されるまでパリティの読取りと書込みの両
方を遅延させる。したがって、ブロック１が更新される
と、ブロック１が読み取られて新しいデータが書き込ま
れ、ブロック１の古い値と新しい値のＸＯＲがデルタ・
パリティとしてキャッシュに格納される。このデルタ・
パリティは、その後、新しいパリティを計算するために
パリティに適用しなければならない。ブロック２が更新
されると、ブロック２が読み取られて新しいデータが書
き込まれ、新しいデルタ・パリティが計算される（古い
デルタ・パリティＸＯＲブロック２の古い値ＸＯＲブロ
ック２の新しい値）。順次ストリームが切断されると、
パリティ・ブロック（複数も可）が読み取られ、デルタ
・パリティ（複数も可）が適用され、パリティ・ブロッ
ク（複数も可）がディスクに再書込みされる。

【００７１】連続更新のストリームが大きければ大きい
ほど、パリティ・キャッシュよりデルタ・パリティ・キ
ャッシュの方が有利である度合いが強くなる。デルタ・
パリティ・キャッシュは、データ事前取出し（後述す
る）によっても拡張することができる。パリティ・キャ
ッシュとデルタ・パリティ・キャッシュの最適化は、入
出力パターンがランダムでも、ハードウェアＲＡＩＤに
よって使用することができる。このような最適化は、大
量書込みキャッシュと高速書込みのために大型のＮＶＲ
ＡＭを用意することができない低コスト・ハードウェア
ＲＡＩＤに最も適している。

【００７２】図６は、パリティ・グループ・セットとし
て編成されたパリティ・グループ用の順次書込み要求を
処理し、デルタ・パリティ・キャッシュを使用する好ま
しい実施例の流れ図を示している。

【００７３】デルタ・パリティおよび部分パリティ・キ
ャッシュの最適化 本発明の他の代替実施例では、パリティ・グループ全体
を更新した場合にパリティの読取り値を保管する。この
最適化では、デルタ・パリティと部分パリティの両方を
以下のようにキャッシュすることが必要である。（１）
ブロック１を更新するときは、ブロック１を読み取って
書き込む。（２）デルタ・パリティ（ブロック１の新し
い値ＸＯＲブロック１の古い値）と部分パリティ（ブロ
ック１の新しい値）をキャッシュに保管する。（３）ブ
ロック２を更新するときは、ブロック２を読み取って書
き込む。また、新しいデルタ・パリティ（古いデルタ・
パリティＸＯＲブロック２の古い値ＸＯＲブロック２の
新しい値）と新しい部分パリティ（古い部分パリティＸ
ＯＲブロック２の新しい値）をキャッシュに保管する。
（４）パリティ・グループ全体を更新する場合は、キャ
ッシュ内に生成された部分パリティから単純に新しいパ
リティを計算することができる。パリティ・グループ全
体を更新するわけではない場合は、ディスクから古いパ
リティを読み取って、それにデルタ・パリティを適用す
ることによって新しいパリティが計算される。

【００７４】データ事前取出しの最適化 本発明の他の実施例では、順次更新が存在するときに１
つのパリティ・グループのデータ・ブロックがＮＶＲＡ
Ｍに事前取出しされる。インタリーフ深さが１であるデ
ータをストライプ化する場合、プロセスは以下のように
機能する。 （１）第１のブロックを更新するときは、データ・ブロ
ック１を読み取って書き込み、パリティＰ１を読み取
る。 （２）Ｐ１の新しい値が計算され、パリティ・キャッシ
ュに格納されるが、ディスクには書き込まれない。 （３）次の連続ブロックであるブロック２を更新すると
きは、ブロック２を読み取って書き込み、Ｐ１の新しい
値を計算してパリティ・キャッシュに入れる。同時に、
パリティ・グループ内の次の連続ブロックであるブロッ
ク３と４の更新を見越して、ブロック３と４を事前取出
しする。 （４）ブロック３と４を更新するときは、ディスクにブ
ロック３を書き込むと更新が完了する。すなわち、更新
動作の応答時間に関連するディスク入出力は１回だけで
ある。１つのパリティ・グループ内のＮ個のブロックの
うちの２個が更新されるか、１つのパリティ・グループ
内のＮ／２個のブロックが更新されるか、または選択し
た他の基準が満足されるとただちに、ブロックの事前取
出しが起動される。

【００７５】前述のように、パリティの書込みは、更新
要求の順次ストリームが切断されるまで遅延される。更
新要求ストリームの切断が早すぎる場合は、無駄な作業
が実行される可能性がある。

【００７６】前述の事前取出しは複数のディスク・ドラ
イブにまたがって行われるので、多くのディスク・ドラ
イブによって自動的に行われる事前取出しとは異なって
いる。

【００７７】キャッシュの機能強化 更新がランダムであっても、ディスク入出力を低減する
ためにデータおよびパリティ・ブロックのキャッシュを
使用することができる。このような汎用キャッシュは、
提示したすべての方法にとって補足的なものである。デ
ータとパリティをキャッシュする際は、以下の追加ポイ
ントが適用される。

【００７８】前述のようにロックが獲得されるが、キャ
ッシュで新しいパリティが更新されるとただちにパリテ
ィに関するロックを解除することができる。パリティが
ディスクに書き込まれるまで待つ必要はない。

【００７９】適切なロックが獲得された後、まずデータ
（パリティ）がないかどうかキャッシュ内を検査する。
キャッシュは、（１）データ（パリティ）がキャッシュ
内にあること、（２）データ（パリティ）がキャッシュ
内にないが、別の要求のためにディスクから取り出して
いること、または（３）データ（パリティ）がキャッシ
ュ内にないことのいずれかを返さなければならない。第
１のケースでは、その要求がキャッシュからのデータ
（パリティ）を使用する。第２のケースでは、要求は入
出力が完了するまで待ち、次にキャッシュからのデータ
（パリティ）を使用する。第３のケースでは、要求はデ
ィスクからデータ（パリティ）を取り出しているという
マークをキャッシュに入れるので、その後、同じデータ
またはパリティ・グループへの更新要求が適切に通知さ
れる。

【００８０】データ（パリティ）は、１つまたは複数の
要求によって必要とされる間、キャッシュ内に固定され
る。このため、使用している間に通常のＬＲＵ置換方針
によってそれを置き換えることができなくなる。

【００８１】パリティ・キャッシュを伴う完全強化デー
タ優先方法 並行性が強化され、復旧が強化された、パリティ・キャ
ッシュとデータ・キャッシュを伴うデータ優先書込みの
ために以下に記載するデータ優先アルゴリズムの完全強
化実施例については、図８を参照して説明する。 （１）データ（ディスクＩのブロックＢ）に関するロッ
クを獲得する（１００）。必要であれば待機する。 （２）キャッシュ内にＤ'用の空間を割り振り、ホスト
からキャッシュにＤ'を入れる。 （３）古いデータがないかどうかキャッシュを検査する
（１０２）。存在するか取出し中の場合は、キャッシュ
・コピーを使用し、ステップ４に移行する。存在せず、
取出し中でもない場合は、古いデータＤを読み取るため
の要求を出す（１０４）。 （４）データに関するロックを獲得した後で、パリティ
（ディスクＪのブロックＢ）に関するロックを獲得する
（１０６）。必要であれば待機する。このロックを獲得
しなければならないのは、データに関するロックを獲得
した後に限られる。 （５）パリティ・ロックの獲得後、古いパリティがない
かどうかパリティ・キャッシュを検査する（１０８）。
古いパリティがパリティ・キャッシュ内になく、取出し
中でもない場合は、古いパリティを読み取るための要求
を出す（１１０）。それ以外の場合は、キャッシュ・コ
ピーを使用する。 （６）ＰＧＳビット・マップに関するロックを獲得する
（１１２）。これは、パリティに関するロックを獲得す
る前に試みることができる。このＰＧＳのビットが設定
されているかどうかを確認するためにＰＧＳビット・マ
ップを検査する。すでに設定されている場合は、次のス
テップに移行する。設定されていない場合は、ビット・
マップにビットを設定する（１１４）。 （７）強制フラグを設定する。書込み進行中が設定され
ていない場合は、ＰＧＳビット・マップ書込みプロセス
を始動するこのフラグを設定する。書込み進行中がすで
に設定されている場合は、ＰＧＳビット・マップ書込み
プロセスが現在、ビット・マップに対して前に行った変
更を書き込んでいる。したがって、古い書込みが完了す
ると、そのビット・マップに対する新しい変更を含む書
込みが自動的に開始される（詳細については以下を参照
のこと）。 （８）適切なＰＧＳ用のＰＧＳカウントを増分する（１
１６）。ＰＧＳビット・マップをロック解除する（１１
７）。 （９）前に検査したときにＰＧＳビット・マップにビッ
トがまだ設定されていない場合は、ステップ６でビット
が設定されたＰＧＳビット・マップがディスクに書き込
まれたことをＰＧＳビット・マップ書込みプロセスが報
告するまで待機する（１１８）。 （１０）Ｄが読み取られた後、できるだけすみやかにデ
ィスクＩのブロックＢにＤ'を書き込むための要求を待
ち行列化する。これは、必要な場合にＰＧＳビット・マ
ップが書き込まれた後にのみ、起こりうるが、パリティ
・ロックを獲得する前にも起こりうる。 （１１）ディスクにＤ'が確実に書き込まれた後、でき
るだけすみやかにシステムに完了を返す（１２０）。こ
れは、パリティに関するロックを獲得する前に起こりう
る。 （１２）Ｄ'がディスクに書き込まれ、Ｄ'がディスク上
のブロックの新しい値として確立されるとただちにデー
タに関するロックを解除する（１２２）。これは、パリ
ティに関するロックを獲得する前に起こりうる。 （１３）ＤまたはＰのどちらが先に使用可能になったか
によって決まる順序で、Ｄ'とＤおよびＰとのＸＯＲを
とり、Ｐ'を生成する（１２４）。ＸＯＲは、ステップ
３と同じ時期に開始することができる。これは、ステッ
プ３と５がともに完了するまで完了できない。 （１４）パリティ・キャッシュにＰ'を保管する（１２
６）。まだディスクには書き込まない。これは、パリテ
ィ書込みプロセスによって書き込まれる（以下を参照の
こと）。 （１５）パリティに関するロックを解除する（１２
８）。 （１６）キャッシュからＤおよびＰを除去する（１３
０）。

【００８２】上記の一連のステップのうち、ステップ
１、２、３、６、７、８、９、１０、１１は、この順序
で実行しなければならない。ステップ４はステップ１の
後、ステップ５はステップ４の後のいつでも実行するこ
とができる。ステップ１２は、ステップ３からのデータ
が使用可能になるか、またはステップ５からのパリティ
が使用可能になるとただちに開始することができる。ス
テップ１２は、データとパリティの両方が使用可能にな
るまで完了することができない。ステップ１３、１４、
１５は、順次、ステップ１２に続いていなければならな
い。

【００８３】ビット・マップ書込みプロセスは、以下の
ように機能する。 （１）書込み進行中フラグが設定されるのを待つ。 （２）ＰＧＳビット・マップをロックする。 （３）強制フラグを検査する。 （４）強制フラグが設定されていない場合は、書込み進
行中フラグをリセットし、ＰＧＳビット・マップをロッ
ク解除し、ステップ１に戻る。強制フラグが設定されて
いる場合は、ディスクに書き込むＰＧＳビット・マップ
の個別のメモリ・コピーを作成し、強制フラグと変更済
みフラグをリセットし、ＰＧＳビット・マップをロック
解除する。 （５）ＰＧＳビット・マップとともに書き込むタイム・
スタンプを増分し、代替位置を指し示すようにビット・
マップを書き込むアドレスを変更する。 （６）ＰＧＳビット・マップのメモリ・コピー（ステッ
プ３で作成）をディスクに書き込む。 （７）完了したら、書込みの完了を待っているすべての
要求側に通知する。ステップ２に移行する。

【００８４】パリティ書込みプロセスは、以下のように
機能する。 （１）複数の更新からなる順次ストリームが切断された
とき、またはそれ以降に、ディスクにパリティを書き込
む。 （２）キャッシュから素早くフラッシュされるように、
パリティをＬＲＵブロックにする。 （３）ＰＧＳビット・マップをロックし、適切なＰＧＳ
用のＰＧＳカウントを減分する。カウント＝０の場合
は、ＰＧＳビット・マップの適切なビットをリセットす
る。変更済みフラグを設定し、ＰＧＳビット・マップを
ロック解除する。

【００８５】強制フラグが設定されていなくても、変更
済みフラグが設定されている場合は、ＰＧＳビット・マ
ップをディスクにダンプするために、随時、ビット・マ
ップ書込みプロセスを始動する。

【００８６】規則正しい遮断中にＲＡＩＤサブシステム
は、ＰＧＳビット・マップがすべてゼロになるまでキャ
ッシュしたパリティまたはデータを強制的にディスクに
書き込み、ＰＧＳビット・マップは強制的にディスクに
書き込まれる。次の電源投入時の復旧時間は、素早く達
成される。

【００８７】ランダム作業負荷 ランダム作業負荷（特に、完全強化デルタ・パリティ・
キャッシュ手法）の場合でもすべての実施例を使用する
ことができる。並行性の改善や、パリティ用の入出力の
最適化の機会など、本発明を使用する際の利点は数多
い。というのは、これらは、より好都合な時間と入出力
の結合が可能になるまで遅延することができるからであ
る。

【００８８】結論 好ましい実施例に関して本発明を具体的に示し説明して
きたが、特許請求の範囲に定義するように、本発明の精
神および範囲を逸脱せずに、形式および細部についてさ
まざまな変更が可能であることに留意されたい。

【００８９】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００９０】（１）プロセッサとメモリとを含む複数の
記憶装置のアレイにデータを格納する方法において、 （Ａ）パリティ・グループの一部としてブロック位置に
格納された１つのパリティ・ブロックが前記パリティ・
グループのブロック位置に格納された複数のデータ・ブ
ロックの組合せから論理的に導出され、１つのパリティ
・グループ内の各ブロックが別々の記憶装置に格納され
るように、記憶装置上の複数のブロック位置を複数のパ
リティ・グループとして論理的に配置するステップと、 （Ｂ）複数のパリティ・グループのセットを１つのパリ
ティ・グループ・セットにグループ化するステップと、 （Ｃ）記憶装置上のデータ・ブロック位置に１つの新し
いデータ・ブロックを書き込む際に（i）前記データ・
ブロック位置に格納された古いデータ・ブロックを読み
取るステップと、（ii）前記データ・ブロック位置に新
しいデータ・ブロックを書き込むステップと、（iii）
前記ブロック位置が属するパリティ・グループ及びパリ
ティ・グループ・セットを識別するステップと、（iv）
新しいデータ・ブロックの書込み前に前記識別されたパ
リティ・グループ・セットが未修正状態になっていると
きにのみ、前記識別されたパリティ・グループ・セット
が、回復プロセスの間識別されたパリティ・グループ・
セットのすべてのパリティ・グループがパリティの不整
合検査されることを示す、修正状態になっているという
標識を前記記憶装置に書き込むステップとを含むことを
特徴とする方法。 （２）（Ｄ）前記データ・ブロック位置が属する前記識
別されたパリティ・グループ用の古いパリティ・ブロッ
クを読み取るステップと、（Ｅ）古いデータ・ブロック
と、古いパリティ・ブロックと、新しいデータ・ブロッ
クとから前記識別されたパリティ・グループ用の新しい
パリティ・ブロックを計算するステップと、（Ｆ）前記
記憶装置上の古いパリティ・ブロック用の位置に新しい
パリティ・ブロックを書き込むステップと、（Ｇ）ステ
ップ（Ｆ）の完了後に、前記識別されたパリティ・グル
ープが未修正状態であることを示すステップと、（Ｈ）
前記識別されたパリティ・グループ・セットの全てのパ
リティ・グループが未修正状態であるかどうかを決定す
るステップと、（Ｉ）前記パリティ・グループ・セット
の全てのパリティ・グループが未修正状態である、各パ
リティ・グループ・セットについて、前記パリティ・グ
ループ・セットが未修正状態であることを示す標識をメ
モリに書き込むステップと、をさらに含むことを特徴と
する、上記（１）に記載の複数の記憶装置のアレイにデ
ータを格納する方法。 （３）（Ｄ）古いデータ・ブロックと新しいデータ・ブ
ロックとから前記識別されたパリティ・グループ用の変
更パリティ・ブロックを計算するステップと、（Ｅ）前
記データ・ブロック位置が属する前記識別されたパリテ
ィ・グループ用の古いパリティ・ブロックを読み取るス
テップと、（Ｆ）変更パリティ・ブロックと古いパリテ
ィ・ブロックとから新しいパリティ・ブロックを計算す
るステップと、（Ｇ）前記記憶装置上の古いパリティ・
ブロック用の位置に新しいパリティ・ブロックを書き込
むステップと、（Ｈ）ステップ（Ｇ）の完了後に、前記
識別されたパリティ・グループが未修正状態であること
を示すステップと、（Ｉ）前記識別されたパリティ・グ
ループ・セットの全てのパリティ・グループが未修正状
態であるかどうかを決定するステップと、（Ｊ）前記パ
リティ・グループ・セットの全てのパリティ・グループ
が未修正状態である、各パリティ・グループ・セットに
ついて、前記パリティ・グループ・セットが未修正状態
であることを示す標識をメモリに書き込むステップと、
をさらに含むことを特徴とする、上記（１）に記載の複
数の記憶装置のアレイにデータを格納する方法。 （４）各パリティ・グループ・セットが修正状態になっ
ているとき、ビットが設定されたビット・マップ中で前
記パリティ・グループ・セットが表されることを特徴と
する、上記（１）に記載の複数の記憶装置のアレイにデ
ータを格納する方法。 （５）各パリティ・グループ・セットが、該パリティ・
グループ・セットを現在修正している書込み動作の回数
を示すセット・カウンタを有し、該セット・カウンタが
ゼロになったときに、前記パリティ・グループ・セット
用のビットがリセットされることを特徴とする、上記
（４）に記載の複数の記憶装置のアレイにデータを格納
する方法。 （６）上記（１）に記載の複数の記憶装置のアレイにデ
ータを格納する方法を使用する記憶システムの障害から
復旧する方法において、（Ａ）修正されたパリティ・グ
ループ・セットを識別する標識を記憶装置から読み取る
ステップと、（Ｂ）各修正されたパリティ・グループ・
セットごとに、不整合パリティ・ブロックを有する前記
修正されたパリティ・グループ・セット内の各不整合パ
リティ・グループを識別するステップと、（Ｃ）前記各
不整合パリティ・グループごとに、前記不整合パリティ
・グループのデータ・ブロックに基づいて前記不整合パ
リティ・グループ用のパリティ・ブロックを更新するス
テップとを含むことを特徴とする方法。 （７）上記（４）に記載の複数の記憶装置のアレイにデ
ータを格納する方法を使用する記憶システムの障害から
復旧する方法において、（Ａ）パリティ・グループ・セ
ット・ビット・マップを記憶装置から取り出すステップ
と、（Ｂ）ビットが設定された各パリティ・グループ・
セットごとに、不整合パリティ・ブロックを有する各不
整合パリティ・グループを識別するステップと、（Ｃ）
前記各不整合パリティ・グループごとに、前記不整合パ
リティ・グループのデータ・ブロックに基づいて前記不
整合パリティ・グループ用のパリティ・ブロックを更新
するステップとを含むことを特徴とする方法。 （８）データ記憶装置上の２つの位置にパリティ・グル
ープ・セット・ビット・マップを書き込むステップと、
ビット・マップが前記データ記憶装置に書き込まれたと
きにビット・マップの先頭と末尾にタイム・スタンプを
書き込むステップと、復旧プロセス中に前記ビット・マ
ップを取り出すときにビット・マップの最新整合タイム
・スタンプ付きバージョンを前記データ記憶装置から取
り出すステップとをさらに含むことを特徴とする、上記
（７）に記載の障害から復旧する方法。 （９）（Ｄ）新しいデータ・ブロックが順次データ・ス
トリームの継続であるかどうかを判定するステップと、 （Ｅ）古いデータ・ブロックと新しいデータ・ブロック
とから前記識別されたパリティ・グループ用の変更パリ
ティ・ブロックを計算するステップと、 （Ｆ）前記新しいデータ・ブロックが前記順次データ・
ストリームの継続ではないときに、（i）順次データ・
ストリームの一部である各ブロック位置が属する各パリ
ティ・グループ用の古いパリティ・ブロックを読み取る
ステップと、（ii）前記各パリティ・グループ用の変更
パリティ・ブロックと、前記各パリティ・グループ用の
古いパリティ・ブロックとに基づいて、順次データ・ス
トリームの一部である各ブロック位置が属する各パリテ
ィ・グループ用の新しいパリティ・ブロックを計算する
ステップと、（iii）順次データ・ストリームの一部で
ある各ブロック位置が属する各パリティ・グループ用の
新しいパリティ・ブロックを、前記各パリティ・グルー
プの古いパリティ・ブロック用のブロック位置に書き込
むステップとをさらに含むことを特徴とする、上記
（１）に記載の複数の記憶装置のアレイにデータを格納
する方法。 （１０）新しいデータ・ブロックが、前記データ・スト
リームの古いデータ・ブロックの前記パリティ・グルー
プ・セットから新しいパリティ・グループ・セット内の
パリティ・グループ内にあると決定された後、前記識別
されたパリティ・グループ・セットが修正状態になって
いるという標識が記憶装置に書き込まれることを特徴と
する、上記（９）に記載の複数の記憶装置のアレイにデ
ータを格納する方法。 （１１）（iv）ステップ（Ｆ）（iii）の完了後に、未
修正状態になっている各パリティ・グループ・セットご
とに、前記パリティ・グループ・セットが未修正状態に
なっているという標識をメモリに書き込むステップをさ
らに含むことを特徴とする、上記（１０）に記載の複数
の記憶装置のアレイにデータを格納する方法。 （１２）ステップ（Ｃ）（i）の前にデータ・ブロック
位置をロックするステップと、ステップ（Ｃ）（ii）の
後にデータ・ブロック位置をロック解除するステップ
と、ステップ（Ｄ）の前に古いパリティ・ブロックのブ
ロック位置をロックするステップと、ステップ（Ｆ）の
後に古いパリティ・ブロックのブロック位置をロック解
除するステップとをさらに含むことを特徴とする、上記
（２）に記載の複数の記憶装置のアレイにデータを格納
する方法。 （１３）複数の記憶装置のアレイ内のブロック位置に新
しいデータ・ブロックを書き込む方法において、（Ａ）
ブロック位置のパリティ・グループに対応する古いパリ
ティ・ブロックを決定するステップと（Ｂ）前記ブロッ
ク位置をロックするステップと、（Ｃ）前記ブロック位
置に格納された古いデータ・ブロックを読み取るステッ
プと、（Ｄ）前記ブロック位置に新しいデータ・ブロッ
クを書き込むステップと、（Ｅ）前記ブロック位置をロ
ック解除するステップと、（Ｆ）古いパリティ・ブロッ
クのブロック位置をロックするステップと、（Ｇ）前記
古いパリティ・ブロックを読み取るステップと、（Ｈ）
古いデータ・ブロックと、古いパリティ・ブロックと、
新しいデータ・ブロックとに基づいて、前記パリティ・
グループ用の新しいパリティ・ブロックを計算するステ
ップと、（Ｉ）古いパリティ・ブロックのブロック位置
に新しいパリティ・ブロックを書き込むステップと、
（Ｊ）古いパリティ・ブロックのブロック位置をロック
解除するステップとを含むことを特徴とする方法。 （１４）それぞれの記憶装置が複数のブロック位置を含
む、複数の記憶装置と、パリティ・グループがパリティ
・グループ・ブロック位置の１つに格納された１つのパ
リティ・ブロックを含み、前記パリティ・ブロックが前
記パリティ・グループ・ブロック位置に格納された複数
のデータ・ブロックの組合せから論理的に導出され、１
つのパリティ・グループ内の各データ及びパリティ・ブ
ロックが別々の記憶装置に格納されるように、記憶装置
上の複数のブロック位置から論理的に編成された複数の
パリティ・グループと、各パリティ・グループ・セット
が前記複数のパリティ・グループのセットを含む複数の
パリティ・グループ・セットと、１つの記憶装置上の１
つのブロック位置に新しいデータ・ブロックを書き込む
手段と、前記パリティ・グループ・ブロック位置の１つ
に格納された古いデータ・ブロックを読み取る手段と、
前記パリティ・グループ・ブロック位置の１つが属する
パリティ・グループ・セットの１つを識別する手段と、
前記パリティ・グループ・セットの１つが未修正状態に
なっていることを示す標識を前記パリティ・グループ・
セットの１つが有しないときを判定する手段と、前記パ
リティ・グループ・セットの１つが修正状態になってい
るという標識を前記記憶装置に書き込む手段とを含むこ
とを特徴とする、記憶アレイ・システム。 （１５）前記パリティ・グループ・ブロック位置が属す
るパリティ・グループを判定する手段と、前記判定され
たパリティ・グループ用の古いパリティ・ブロックを読
み取る手段と、古いデータ・ブロックと、古いパリティ
・ブロックと、新しいデータ・ブロックとから前記判定
されたパリティ・グループ用の新しいパリティ・ブロッ
クを計算する手段と、記憶装置上の古いパリティ・ブロ
ックが格納されていたパリティ・グループ・ブロック位
置に新しいパリティ・ブロックを書き込む手段と、未修
正状態になっている各パリティ・グループ・セットを判
定する手段と、前記パリティ・グループ・セットのうち
の少なくとも１つが未修正状態になっているという標識
を記憶装置に書き込む手段とをさらに含むことを特徴と
する、上記（１４）に記載のシステム。 （１６）前記パリティ・グループ・セットのうちの少な
くとも１つが未修正状態および修正状態になっているこ
とを示す標識が、修正状態になっている各パリティ・グ
ループごとにビットが設定されたパリティ・グループ・
セット・ビット・マップと、各パリティ・グループごと
にパリティ・グループ・セットを現在修正している書込
み動作の回数を示すセット・カウンタとを含み、セット
・カウンタがゼロになると、前記パリティ・グループ・
セット用のビットが変更されることを特徴とする、上記
（１５）に記載のシステム。 （１７）修正されたパリティ・グループ・セットを識別
する手段と、不整合パリティ・ブロックを有する修正さ
れたパリティ・グループ・セット内のパリティ・グルー
プを識別する手段と、前記パリティ・グループのデータ
・ブロックに基づいて、各不整合パリティ・グループ用
のパリティ・ブロックを更新する手段とをさらに含むこ
とを特徴とする、上記（１４）に記載のシステム。 （１８）新しいデータ・ブロックが順次データ・ストリ
ームの継続かどうかを判定する手段と、古いデータ・ブ
ロックと新しいデータ・ブロックとからパリティ・グル
ープ用の変更パリティ・ブロックを計算する手段と、順
次データ・ストリームの一部であるブロック位置が属す
る各パリティ・グループ用の古いパリティ・ブロックを
読み取る手段と、各パリティ・グループ用の変更パリテ
ィと、各パリティ・グループ用の古いパリティ・ブロッ
クとに基づいて、順次データ・ストリームの一部である
ブロック位置が属する各パリティ・グループ用の新しい
パリティ・ブロックを計算する手段と、順次データ・ス
トリームの一部であるブロック位置が属する各パリティ
・グループ用の新しいパリティ・ブロックを、前記記憶
装置上の前記パリティ・グループ用の古いパリティ・ブ
ロックの各ブロック位置に書き込む手段とをさらに含む
ことを特徴とする、上記（１４）に記載のシステム。 （１９）媒体内にコンピュータ・プログラム・コードを
有する、コンピュータにより読取り可能な記憶媒体であ
って、（Ａ）パリティ・グループの一部としてブロック
位置に格納された１つのパリティ・ブロックが前記パリ
ティ・グループのブロック位置に格納された複数のデー
タ・ブロックの組合せから論理的に導出され、１つのパ
リティ・グループ内の各ブロックが別々の記憶装置に格
納されるように、記憶装置上の複数のブロック位置を複
数のパリティ・グループとして論理的に配置する、コン
ピュータ・プログラム・コード手段と、（Ｂ）複数のパ
リティ・グループのセットを１つのパリティ・グループ
・セットにグループ化するコンピュータ・プログラム・
コード手段と、 （Ｃ）記憶装置上のデータ・ブロック位置に１つの新し
いデータ・ブロックを書き込む際に（i）前記データ・
ブロック位置に格納された古いデータ・ブロックを読み
取るコンピュータ・プログラム・コード手段と、（ii）
前記データ・ブロック位置に新しいデータ・ブロックを
書き込むコンピュータ・プログラム・コード手段と、
（iii）前記ブロック位置が属するパリティ・グループ
及びパリティ・グループ・セットを識別するコンピュー
タ・プログラム・コード手段と、（iv）新しいデータ・
ブロックの書込み前に前記識別されたパリティ・グルー
プ・セットが未修正状態になっているときにのみ、前記
識別されたパリティ・グループ・セットが、回復プロセ
スの間識別されたパリティ・グループ・セットのすべて
のパリティ・グループがパリティの不整合検査されるこ
とを示す、修正状態になっているという標識を前記記憶
装置に書き込むコンピュータ・プログラム・コード手段
とを含むことを特徴とする、記憶媒体。 （２０）（Ｄ）前記データ・ブロック位置が属する前記
識別されたパリティ・グループ用の古いパリティ・ブロ
ックを読み取るコンピュータ・プログラム・コード手段
と、（Ｅ）古いデータ・ブロックと、古いパリティ・ブ
ロックと、新しいデータ・ブロックとから前記識別され
たパリティ・グループ用の新しいパリティ・ブロックを
計算するコンピュータ・プログラム・コード手段と、
（Ｆ）前記記憶装置上の古いパリティ・ブロック用の位
置に新しいパリティ・ブロックを書き込むコンピュータ
・プログラム・コード手段と、（Ｇ）ステップ（Ｆ）の
完了後に、前記識別されたパリティ・グループが未修正
状態であることを示すコンピュータ・プログラム・コー
ド手段と、（Ｈ）前記識別されたパリティ・グループ・
セットの全てのパリティ・グループが未修正状態である
かどうかを決定するコンピュータ・プログラム・コード
手段と、（Ｉ）前記パリティ・グループ・セットの全て
のパリティ・グループが未修正状態である、各パリティ
・グループ・セットについて、前記パリティ・グループ
・セットが未修正状態であることを示す標識をメモリに
書き込むコンピュータ・プログラム・コード手段と、を
さらに含むことを特徴とする、上記（１９）に記載の媒
体。

【図面の簡単な説明】

【図１】記憶アレイ・システムの概略図である。

【図２】記憶アレイ・システム内のパリティ・グループ
・セットの概略図である。

【図３】記憶アレイ・システムにデータを書き込むため
のプロセスを示す流れ図である。

【図４】記憶装置上に格納されたパリティ・グループ・
セットのビット・マップ表現を示す図である。

【図５】パリティ・グループ・セット単位に編成された
データ・ブロックを有する記憶アレイ・システムにデー
タを書き込むためのプロセスを示す流れ図である。

【図６】記憶アレイ・システム内の障害から復旧するプ
ロセスを示す流れ図である。

【図７】パリティ・グループ・セット単位に編成され、
不揮発性キャッシュを有する記憶アレイ・システムにデ
ータを書き込むためのプロセスを示す流れ図である。

【図８】パリティ・グループ・セット単位に編成され、
不揮発性キャッシュを有する記憶アレイ・システムにデ
ータを書き込むためのプロセスの他の実施例を示す流れ
図である。

【符号の説明】

３６ ブロックＢをロックする ３７ ブロックＢの古いデータを読み取る ブロックＢに新しいデータを書き込む ３８ ブロックＢ用のパリティ・ブロックをロックする ３９ 「完了」を返す ４０ ブロックＢをロック解除する ４１ 古いデータと新しいデータからΔＰを計算する ４２ 古いパリティを読み取る ４３ 古いパリティとΔＰから新しいパリティを計算す
る ４４ 新しいパリティを書き込む ４５ パリティ・ブロックに関するロックを解除する

フロントページの続き (72)発明者 ジェームズ・クリストファー・ウィリー アメリカ合衆国95030 カリフォルニア州 モンテ・セレーノ チャドボーン・レーン 18392 (72)発明者 ジェフリー・エイ・リーゲル アメリカ合衆国95128 カリフォルニア州 サンノゼヒーサーデール・レーン 1592

Claims (20)

【特許請求の範囲】
1. 【請求項１】プロセッサとメモリとを含む複数の記憶装
   置のアレイにデータを格納する方法において、 （Ａ）パリティ・グループの一部としてブロック位置に
   格納された１つのパリティ・ブロックが前記パリティ・
   グループのブロック位置に格納された複数のデータ・ブ
   ロックの組合せから論理的に導出され、１つのパリティ
   ・グループ内の各ブロックが別々の記憶装置に格納され
   るように、記憶装置上の複数のブロック位置を複数のパ
   リティ・グループとして論理的に配置するステップと、 （Ｂ）複数のパリティ・グループのセットを１つのパリ
   ティ・グループ・セットにグループ化するステップと、 （Ｃ）記憶装置上のデータ・ブロック位置に１つの新し
   いデータ・ブロックを書き込む際に（i）前記データ・
   ブロック位置に格納された古いデータ・ブロックを読み
   取るステップと、（ii）前記データ・ブロック位置に新
   しいデータ・ブロックを書き込むステップと、（iii）
   前記ブロック位置が属するパリティ・グループ及びパリ
   ティ・グループ・セットを識別するステップと、（iv）
   新しいデータ・ブロックの書込み前に前記識別されたパ
   リティ・グループ・セットが未修正状態になっていると
   きにのみ、前記識別されたパリティ・グループ・セット
   が、回復プロセスの間識別されたパリティ・グループ・
   セットのすべてのパリティ・グループがパリティの不整
   合検査されることを示す、修正状態になっているという
   標識を前記記憶装置に書き込むステップとを含むことを
   特徴とする方法。
2. 【請求項２】（Ｄ）前記データ・ブロック位置が属する
   前記識別されたパリティ・グループ用の古いパリティ・
   ブロックを読み取るステップと、 （Ｅ）古いデータ・ブロックと、古いパリティ・ブロッ
   クと、新しいデータ・ブロックとから前記識別されたパ
   リティ・グループ用の新しいパリティ・ブロックを計算
   するステップと、 （Ｆ）前記記憶装置上の古いパリティ・ブロック用の位
   置に新しいパリティ・ブロックを書き込むステップと、 （Ｇ）ステップ（Ｆ）の完了後に、前記識別されたパリ
   ティ・グループが未修正状態であることを示すステップ
   と、 （Ｈ）前記識別されたパリティ・グループ・セットの全
   てのパリティ・グループが未修正状態であるかどうかを
   決定するステップと、 （Ｉ）前記パリティ・グループ・セットの全てのパリテ
   ィ・グループが未修正状態である、各パリティ・グルー
   プ・セットについて、前記パリティ・グループ・セット
   が未修正状態であることを示す標識をメモリに書き込む
   ステップと、をさらに含むことを特徴とする、請求項１
   に記載の複数の記憶装置のアレイにデータを格納する方
   法。
3. 【請求項３】（Ｄ）古いデータ・ブロックと新しいデー
   タ・ブロックとから前記識別されたパリティ・グループ
   用の変更パリティ・ブロックを計算するステップと、 （Ｅ）前記データ・ブロック位置が属する前記識別され
   たパリティ・グループ用の古いパリティ・ブロックを読
   み取るステップと、 （Ｆ）変更パリティ・ブロックと古いパリティ・ブロッ
   クとから新しいパリティ・ブロックを計算するステップ
   と、 （Ｇ）前記記憶装置上の古いパリティ・ブロック用の位
   置に新しいパリティ・ブロックを書き込むステップと、 （Ｈ）ステップ（Ｇ）の完了後に、前記識別されたパリ
   ティ・グループが未修正状態であることを示すステップ
   と、 （Ｉ）前記識別されたパリティ・グループ・セットの全
   てのパリティ・グループが未修正状態であるかどうかを
   決定するステップと、 （Ｊ）前記パリティ・グループ・セットの全てのパリテ
   ィ・グループが未修正状態である、各パリティ・グルー
   プ・セットについて、前記パリティ・グループ・セット
   が未修正状態であることを示す標識をメモリに書き込む
   ステップと、をさらに含むことを特徴とする、請求項１
   に記載の複数の記憶装置のアレイにデータを格納する方
   法。
4. 【請求項４】各パリティ・グループ・セットが修正状態
   になっているとき、ビットが設定されたビット・マップ
   中で前記パリティ・グループ・セットが表されることを
   特徴とする、請求項１に記載の複数の記憶装置のアレイ
   にデータを格納する方法。
5. 【請求項５】各パリティ・グループ・セットが、該パリ
   ティ・グループ・セットを現在修正している書込み動作
   の回数を示すセット・カウンタを有し、該セット・カウ
   ンタがゼロになったときに、前記パリティ・グループ・
   セット用のビットがリセットされることを特徴とする、
   請求項４に記載の複数の記憶装置のアレイにデータを格
   納する方法。
6. 【請求項６】請求項１に記載の複数の記憶装置のアレイ
   にデータを格納する方法を使用する記憶システムの障害
   から復旧する方法において、 （Ａ）修正されたパリティ・グループ・セットを識別す
   る標識を記憶装置から読み取るステップと、 （Ｂ）各修正されたパリティ・グループ・セットごと
   に、不整合パリティ・ブロックを有する前記修正された
   パリティ・グループ・セット内の各不整合パリティ・グ
   ループを識別するステップと、 （Ｃ）前記各不整合パリティ・グループごとに、前記不
   整合パリティ・グループのデータ・ブロックに基づいて
   前記不整合パリティ・グループ用のパリティ・ブロック
   を更新するステップとを含むことを特徴とする方法。
7. 【請求項７】請求項４に記載の複数の記憶装置のアレイ
   にデータを格納する方法を使用する記憶システムの障害
   から復旧する方法において、 （Ａ）パリティ・グループ・セット・ビット・マップを
   記憶装置から取り出すステップと、 （Ｂ）ビットが設定された各パリティ・グループ・セッ
   トごとに、不整合パリティ・ブロックを有する各不整合
   パリティ・グループを識別するステップと、 （Ｃ）前記各不整合パリティ・グループごとに、前記不
   整合パリティ・グループのデータ・ブロックに基づいて
   前記不整合パリティ・グループ用のパリティ・ブロック
   を更新するステップとを含むことを特徴とする方法。
8. 【請求項８】データ記憶装置上の２つの位置にパリティ
   ・グループ・セット・ビット・マップを書き込むステッ
   プと、 ビット・マップが前記データ記憶装置に書き込まれたと
   きにビット・マップの先頭と末尾にタイム・スタンプを
   書き込むステップと、 復旧プロセス中に前記ビット・マップを取り出すときに
   ビット・マップの最新整合タイム・スタンプ付きバージ
   ョンを前記データ記憶装置から取り出すステップとをさ
   らに含むことを特徴とする、請求項７に記載の障害から
   復旧する方法。
9. 【請求項９】（Ｄ）新しいデータ・ブロックが順次デー
   タ・ストリームの継続であるかどうかを判定するステッ
   プと、 （Ｅ）古いデータ・ブロックと新しいデータ・ブロック
   とから前記識別されたパリティ・グループ用の変更パリ
   ティ・ブロックを計算するステップと、 （Ｆ）前記新しいデータ・ブロックが前記順次データ・
   ストリームの継続ではないときに、（i）順次データ・
   ストリームの一部である各ブロック位置が属する各パリ
   ティ・グループ用の古いパリティ・ブロックを読み取る
   ステップと、（ii）前記各パリティ・グループ用の変更
   パリティ・ブロックと、前記各パリティ・グループ用の
   古いパリティ・ブロックとに基づいて、順次データ・ス
   トリームの一部である各ブロック位置が属する各パリテ
   ィ・グループ用の新しいパリティ・ブロックを計算する
   ステップと、（iii）順次データ・ストリームの一部で
   ある各ブロック位置が属する各パリティ・グループ用の
   新しいパリティ・ブロックを、前記各パリティ・グルー
   プの古いパリティ・ブロック用のブロック位置に書き込
   むステップとをさらに含むことを特徴とする、請求項１
   に記載の複数の記憶装置のアレイにデータを格納する方
   法。
10. 【請求項１０】新しいデータ・ブロックが、前記データ
    ・ストリームの古いデータ・ブロックの前記パリティ・
    グループ・セットから新しいパリティ・グループ・セッ
    ト内のパリティ・グループ内にあると決定された後、前
    記識別されたパリティ・グループ・セットが修正状態に
    なっているという標識が記憶装置に書き込まれることを
    特徴とする、請求項９に記載の複数の記憶装置のアレイ
    にデータを格納する方法。
11. 【請求項１１】（iv）ステップ（Ｆ）（iii）の完了後
    に、未修正状態になっている各パリティ・グループ・セ
    ットごとに、前記パリティ・グループ・セットが未修正
    状態になっているという標識をメモリに書き込むステッ
    プをさらに含むことを特徴とする、請求項１０に記載の
    複数の記憶装置のアレイにデータを格納する方法。
12. 【請求項１２】ステップ（Ｃ）（i）の前にデータ・ブ
    ロック位置をロックするステップと、 ステップ（Ｃ）（ii）の後にデータ・ブロック位置をロ
    ック解除するステップと、 ステップ（Ｄ）の前に古いパリティ・ブロックのブロッ
    ク位置をロックするステップと、 ステップ（Ｆ）の後に古いパリティ・ブロックのブロッ
    ク位置をロック解除するステップとをさらに含むことを
    特徴とする、請求項２に記載の複数の記憶装置のアレイ
    にデータを格納する方法。
13. 【請求項１３】複数の記憶装置のアレイ内のブロック位
    置に新しいデータ・ブロックを書き込む方法において、 （Ａ）ブロック位置のパリティ・グループに対応する古
    いパリティ・ブロックを決定するステップと （Ｂ）前記ブロック位置をロックするステップと、 （Ｃ）前記ブロック位置に格納された古いデータ・ブロ
    ックを読み取るステップと、 （Ｄ）前記ブロック位置に新しいデータ・ブロックを書
    き込むステップと、 （Ｅ）前記ブロック位置をロック解除するステップと、 （Ｆ）古いパリティ・ブロックのブロック位置をロック
    するステップと、 （Ｇ）前記古いパリティ・ブロックを読み取るステップ
    と、 （Ｈ）古いデータ・ブロックと、古いパリティ・ブロッ
    クと、新しいデータ・ブロックとに基づいて、前記パリ
    ティ・グループ用の新しいパリティ・ブロックを計算す
    るステップと、 （Ｉ）古いパリティ・ブロックのブロック位置に新しい
    パリティ・ブロックを書き込むステップと、 （Ｊ）古いパリティ・ブロックのブロック位置をロック
    解除するステップとを含むことを特徴とする方法。
14. 【請求項１４】それぞれの記憶装置が複数のブロック位
    置を含む、複数の記憶装置と、 パリティ・グループがパリティ・グループ・ブロック位
    置の１つに格納された１つのパリティ・ブロックを含
    み、前記パリティ・ブロックが前記パリティ・グループ
    ・ブロック位置に格納された複数のデータ・ブロックの
    組合せから論理的に導出され、１つのパリティ・グルー
    プ内の各データ及びパリティ・ブロックが別々の記憶装
    置に格納されるように、記憶装置上の複数のブロック位
    置から論理的に編成された複数のパリティ・グループ
    と、 各パリティ・グループ・セットが前記複数のパリティ・
    グループのセットを含む複数のパリティ・グループ・セ
    ットと、 １つの記憶装置上の１つのブロック位置に新しいデータ
    ・ブロックを書き込む手段と、 前記パリティ・グループ・ブロック位置の１つに格納さ
    れた古いデータ・ブロックを読み取る手段と、 前記パリティ・グループ・ブロック位置の１つが属する
    パリティ・グループ・セットの１つを識別する手段と、 前記パリティ・グループ・セットの１つが未修正状態に
    なっていることを示す標識を前記パリティ・グループ・
    セットの１つが有しないときを判定する手段と、 前記パリティ・グループ・セットの１つが修正状態にな
    っているという標識を前記記憶装置に書き込む手段とを
    含むことを特徴とする、記憶アレイ・システム。
15. 【請求項１５】前記パリティ・グループ・ブロック位置
    が属するパリティ・グループを判定する手段と、 前記判定されたパリティ・グループ用の古いパリティ・
    ブロックを読み取る手段と、 古いデータ・ブロックと、古いパリティ・ブロックと、
    新しいデータ・ブロックとから前記判定されたパリティ
    ・グループ用の新しいパリティ・ブロックを計算する手
    段と、 記憶装置上の古いパリティ・ブロックが格納されていた
    パリティ・グループ・ブロック位置に新しいパリティ・
    ブロックを書き込む手段と、 未修正状態になっている各パリティ・グループ・セット
    を判定する手段と、 前記パリティ・グループ・セットのうちの少なくとも１
    つが未修正状態になっているという標識を記憶装置に書
    き込む手段とをさらに含むことを特徴とする、請求項１
    ４に記載のシステム。
16. 【請求項１６】前記パリティ・グループ・セットのうち
    の少なくとも１つが未修正状態および修正状態になって
    いることを示す標識が、修正状態になっている各パリテ
    ィ・グループごとにビットが設定されたパリティ・グル
    ープ・セット・ビット・マップと、各パリティ・グルー
    プごとにパリティ・グループ・セットを現在修正してい
    る書込み動作の回数を示すセット・カウンタとを含み、
    セット・カウンタがゼロになると、前記パリティ・グル
    ープ・セット用のビットが変更されることを特徴とす
    る、請求項１５に記載のシステム。
17. 【請求項１７】修正されたパリティ・グループ・セット
    を識別する手段と、 不整合パリティ・ブロックを有する修正されたパリティ
    ・グループ・セット内のパリティ・グループを識別する
    手段と、 前記パリティ・グループのデータ・ブロックに基づい
    て、各不整合パリティ・グループ用のパリティ・ブロッ
    クを更新する手段とをさらに含むことを特徴とする、請
    求項１４に記載のシステム。
18. 【請求項１８】新しいデータ・ブロックが順次データ・
    ストリームの継続かどうかを判定する手段と、 古いデータ・ブロックと新しいデータ・ブロックとから
    パリティ・グループ用の変更パリティ・ブロックを計算
    する手段と、 順次データ・ストリームの一部であるブロック位置が属
    する各パリティ・グループ用の古いパリティ・ブロック
    を読み取る手段と、 各パリティ・グループ用の変更パリティと、各パリティ
    ・グループ用の古いパリティ・ブロックとに基づいて、
    順次データ・ストリームの一部であるブロック位置が属
    する各パリティ・グループ用の新しいパリティ・ブロッ
    クを計算する手段と、 順次データ・ストリームの一部であるブロック位置が属
    する各パリティ・グループ用の新しいパリティ・ブロッ
    クを、前記記憶装置上の前記パリティ・グループ用の古
    いパリティ・ブロックの各ブロック位置に書き込む手段
    とをさらに含むことを特徴とする、請求項１４に記載の
    システム。
19. 【請求項１９】媒体内にコンピュータ・プログラム・コ
    ードを有する、コンピュータにより読取り可能な記憶媒
    体であって、 （Ａ）パリティ・グループの一部としてブロック位置に
    格納された１つのパリティ・ブロックが前記パリティ・
    グループのブロック位置に格納された複数のデータ・ブ
    ロックの組合せから論理的に導出され、１つのパリティ
    ・グループ内の各ブロックが別々の記憶装置に格納され
    るように、記憶装置上の複数のブロック位置を複数のパ
    リティ・グループとして論理的に配置する、コンピュー
    タ・プログラム・コード手段と、 （Ｂ）複数のパリティ・グループのセットを１つのパリ
    ティ・グループ・セットにグループ化するコンピュータ
    ・プログラム・コード手段と、 （Ｃ）記憶装置上のデータ・ブロック位置に１つの新し
    いデータ・ブロックを書き込む際に（i）前記データ・
    ブロック位置に格納された古いデータ・ブロックを読み
    取るコンピュータ・プログラム・コード手段と、（ii）
    前記データ・ブロック位置に新しいデータ・ブロックを
    書き込むコンピュータ・プログラム・コード手段と、
    （iii）前記ブロック位置が属するパリティ・グループ
    及びパリティ・グループ・セットを識別するコンピュー
    タ・プログラム・コード手段と、（iv）新しいデータ・
    ブロックの書込み前に前記識別されたパリティ・グルー
    プ・セットが未修正状態になっているときにのみ、前記
    識別されたパリティ・グループ・セットが、回復プロセ
    スの間識別されたパリティ・グループ・セットのすべて
    のパリティ・グループがパリティの不整合検査されるこ
    とを示す、修正状態になっているという標識を前記記憶
    装置に書き込むコンピュータ・プログラム・コード手段
    とを含むことを特徴とする、記憶媒体。
20. 【請求項２０】（Ｄ）前記データ・ブロック位置が属す
    る前記識別されたパリティ・グループ用の古いパリティ
    ・ブロックを読み取るコンピュータ・プログラム・コー
    ド手段と、 （Ｅ）古いデータ・ブロックと、古いパリティ・ブロッ
    クと、新しいデータ・ブロックとから前記識別されたパ
    リティ・グループ用の新しいパリティ・ブロックを計算
    するコンピュータ・プログラム・コード手段と、 （Ｆ）前記記憶装置上の古いパリティ・ブロック用の位
    置に新しいパリティ・ブロックを書き込むコンピュータ
    ・プログラム・コード手段と、 （Ｇ）ステップ（Ｆ）の完了後に、前記識別されたパリ
    ティ・グループが未修正状態であることを示すコンピュ
    ータ・プログラム・コード手段と、 （Ｈ）前記識別されたパリティ・グループ・セットの全
    てのパリティ・グループが未修正状態であるかどうかを
    決定するコンピュータ・プログラム・コード手段と、 （Ｉ）前記パリティ・グループ・セットの全てのパリテ
    ィ・グループが未修正状態である、各パリティ・グルー
    プ・セットについて、前記パリティ・グループ・セット
    が未修正状態であることを示す標識をメモリに書き込む
    コンピュータ・プログラム・コード手段と、をさらに含
    むことを特徴とする、請求項１９に記載の媒体。