JP2514289B2 - デ―タの修復方法およびシステム - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は故障独立型直接アクセス
記憶装置（ＤＡＳＤ）の配列に関し、更に詳しくはこの
ＤＡＳＤ配列上に記憶されるデータの保守可用性に関す
る。

【０００２】

【従来の技術】外部記憶装置における１つのプロセサに
よる設計は論理トラックを有する膨大な論理ＤＡＳＤを
考慮することである。各論理トラックは外部記憶（ＤＡ
ＳＤ配列）を構成する物理的ＤＡＳＤの物理的トラック
範囲の何倍もの範囲を要する。エラー訂正コーディング
及び再作成の目的に、論理トラック内のデータを論理空
間行列上にマップされる一連のビット、バイト或いはブ
ロックと見なすことが都合が良い。配列形式の論理トラ
ックから物理配列へのマッピングは本発明において使用
される重要な技術の１つである。

【０００３】数学的には配列は添字変数（subscripted
variable）であり、添字は変数の各例の相対的な位置順
序、特に論理トラック内における各ビット、バイト或い
はブロックの位置順序を指標付けする。また、添字の要
素は配列の次元を定義する。従って、配列Ａ（ｉ、ｊ）
はその相対位置が２次元の閉じた整数間隔（１、１＜
（ｉ、ｊ）＜Ｎ、Ｋ）上にマップされる変数“Ａ”を特
定する。

【０００４】配列次元は相互に排他的である。従って、
閉じた整数間隔１＜ｉ＜Ｎ及び１＜ｊ＜Ｋにより表され
る次元はそれぞれ装置や時間などの順序（指標）を示
し、Ｎ及びＫは整数の上限である。慣例により、列順序
は１つの配列次元を指定し、行順序は他の配列次元を指
定する。この点に関しては、ＮがＤＡＳＤの番号を、ま
たＫが１つのＤＡＳＤのトラック当たりのビット、バイ
ト或いはブロックの番号を示す。

【０００５】同期してアクセスされるＮ個のＤＡＳＤの
物理的な配列はＤＡＳＤ配列を構成する。これに関連し
て、配列のフォーマット及びその後のアクセスが行わ
れ、行或いは列のどちらか一方を基本とする連続する位
置へ値を挿入することにより記憶が進行する。オペレー
ションが列方向に実行されると、それは列メジャー順序
“column major order”と称される。同様に、行方向に
実行されると、行メジャー順序“row major order”と
称される。

【０００６】ＤＡＳＤ配列及び属性 ＤＡＳＤ配列は、プロセサ或いはプロセサ配列の広帯域
データ及び制御パスの終端に位置する入出力（Ｉ／Ｏ）
境界において、これらと接続される外部記憶装置形態で
ある。更に詳しくは、ＤＡＳＤ配列は、共通モード或い
は手段により動作される論理的に関連するＤＡＳＤセッ
トを意味し、その際、ＤＡＳＤセットは同期式に選択さ
れオペレートされる。ＤＡＳＤ配列はハイ・データ・レ
ート、大論理トラック・サイズ及び超高度可用性を支援
する特徴を示す。

【０００７】ハイ・データ・レートはＤＡＳＤの同期式
アクセスを必要とする。また、ＤＡＳＤの片方のグルー
プを横断する書き込みアクセスの場合には、所定のサイ
ズ（ビット、バイト、ワード、ブロック、レコード）に
区切られたデータのシリアルからパラレルへのマッピン
グが必要となり、一方、読み出しアクセスの場合にはパ
ラレルからシリアルへのマッピングが必要となる。この
マッピングはインターリービング“interleaving”或い
はストライピング“striping”と称される。

【０００８】同期式動作はＮ個のＤＡＳＤに対して同一
のｒｐｍで回転すること、同一の角度オフセットを有す
ること、また同一の形式により同時にアクセスされるこ
とを要求する。この解決はデータ転送レートを最大化す
るが、一方では並行性を最小化する。

【０００９】情報の冗長性、コーディング及びブロッキ
ング Patterson により述べられるように、Ｎ個のＤＡＳＤ上
に記憶されるデータは、もし完全に複写されれば、トー
タル２Ｎ個の装置を必要とする。ＤＡＳＤの故障、ノイ
ズ或いはバースト・エラー、或いは不注意な消去により
データの上限以内のデータが使用不能となると、単にこ
のデータを複写する代わりに何らかの代数コーディング
形式が使用される。

【００１０】代数コーディングは境像データにより占有
されるほんの一部のＤＡＳＤ空間を占有することはよく
知られている。使用されるコードに依存して、ＤＡＳＤ
空間の８５％以上が１次データ記憶用に使用可能であ
る。例えば、簡単なパリティ・コーディング（XORing）
により、任意の小空間が確保される。例えば、パリティ
は１０或いは２０ブロックに渡って取られる。従って、
１０或いは２０個のＤＡＳＤグループの中の１つのＤＡ
ＳＤだけが除外されることになる。

【００１１】障害データ或いは欠損データの検出或いは
／及び訂正のために使用される代数コードには数多くの
タイプがある。このことは、いくつかのコードはエラー
を生じたデータの値を決定するだけではなく、消去され
たデータの値を決定するためにも使用されることを意味
する。また、選択されるコードは可用性に関する他の技
術的、経済的な面とも密接な関係を有する。例えば、Pa
rkなどによる１９８６年１１月７日発行の“Providing
Fault Tolerance in Parallel SecondaryStorage Syste
ms”、Princeton University Report CS-TR-057-86 で
はPattersonの場合と同様に、ハミング・コード（Hammi
ng code） がビット・インタリーブ或いはストライプ・
グループにおいて、単純なパリティ・コードが必要とす
る以上のＤＡＳＤを要求することを指摘している。

【００１２】セグメンティング（ストライピング）、単
純パリティ、及びデータ再作成（Data Redo） 典型的には、データ・ストリームが最初にＤＡＳＤスト
リング或いは配列に書き込まれるか更新されるときに、
１つ或いはそれ以上のコード文字がデータ・ストリーム
から算出される。同時にデータ・ストリームはＮブロッ
クに分割（セグメント化）され、Ｎ個のＤＡＳＤを横断
して書き込まれ、一方、代数コード化文字はＮ＋１番目
のＤＡＳＤに書き込まれる。

【００１３】この方法はOuchi による１９７８年５月３
０日公報の米国特許第４０９２７３２号“System for R
ecovering Data Stored in a Failed Memory Unit” で
説明されている。Ouchi は最初に論理ファイルをＮデー
タ・ブロックにセグメント化し、このＮデータ・ブロッ
クの内容の排他的論理和（XORing）を取ることによりパ
リティ・ブロックを形成し、次にこれらのデータとパリ
ティ・ブロックをＮ＋１個の故障独立型のＤＡＳＤを横
断して書き込むことを開示した。

【００１４】Ouchi によれば、アスセス不能ないずれか
１つのＤＡＳＤからの内容は、パリティ・ブロックと残
りのＮ個のアクセス可能なＤＡＳＤ上に記憶されたブロ
ックとの排他的論理和を取ることにより回復可能であ
る。Patterson が指摘するように、単一パリティ・エン
コーディングの魅力的な側面の１つは、各書き込み更新
オペレーションに対し、旧ブロック、変更ブロック及び
旧パリティの排他的論理和としてパリティが再計算され
ることである。

【００１５】ＤＡＳＤの冗長性、予備（スペアリン
グ）、及びデータ再作成 データの冗長性及び関連する予備のＤＡＳＤ空間に加
え、配列の可用性もまたＤＡＳＤの冗長性と関わる。こ
れらの冗長なＤＡＳＤは “スペア”（spare）と称され
る。この点に関し、Dunphy 等による米国特許第４９１
４６５６号“Disk Drive Memory”（１９９０年４月３
日公報）では“ホット・スペア”（hot spare） と称さ
れる所定数のフォーマットされたＤＡＳＤを未指定のプ
ール（pool）として確保する。１つのＤＡＳＤが複数の
独立にアドレス可能な同期式ＤＡＳＤグループ内で故障
すると、スペアの１つがこれを置換する。ここで置換さ
れたＤＡＳＤ上に情報を再作成する問題がまだ残ってい
る。

【００１６】米国特許第４９１４６５６号によれば、配
列に与えられる各データ・ストリングをセグメント化
し、セグメントのパリティを算出し、選択される一方の
同期式ＤＡＳＤグループのＮ個のＤＡＳＤにセグメント
とパリティを書き込む。１つのＤＡＳＤの故障は、故障
しているＤＡＳＤからのデータがこのグループの残りの
Ｎ−１個のＤＡＳＤから再計算されるようにする。

【００１７】失われたデータの再計算或いは再作成スケ
ジューリングは、データの再作成（data redo） 期間中
に同一のグループ内で別の故障が発生すると、スループ
ットの保守と配列のサブシステムを使用不能とするリス
クとのトレード・オフを伴う。

【００１８】ＤＡＳＤ配列故障許容モード及び性能低下
モード・オペレーション故障許容はシステムが故障を耐
え、可用性のロスを伴うこと無くオペレーションを継続
する能力を言う。故障発生から配列を以前の情報状態に
戻すまでの間隔を性能低下モード・オペレーションと称
する。

【００１９】Ouchi 及びDunphyのシステムでは、もしパ
リティに障害が生ずると、スループットに何らかの変更
を来すこと無くデータをアクセスできる。しかし、デー
タに障害が起こると、各アクセスは残りのデータから影
響を受けたデータの再計算とパリティを要求するため、
スループットは極端に低下する。スペアリングとデータ
再作成が無い場合は、第２の故障がデータを使用不能と
する。

【００２０】パリティ・グループの２つの意味 上述のDunphyの特許で使用されるように、“パリティ・
グループ”とは少なくとも（Ｎ＋１）番目のＤＡＳＤを
含む（ここにはＮ個のＤＡＳＤに渡るパリティが記憶さ
れる）Ｎ個のＤＡＳＤの論理関係を意味する。しかし、
この用語はまたデータ・ブロックとパリティ或いは他の
代数的にコード化された冗長ブロックとの論理関係も示
す。Patterson はＲＡＩＤタイプ５ＤＡＳＤ配列におい
て後者の定義を使用している。

【００２１】データ・エラー及び消去 記憶内容における“データ・エラー”はランダム・ノイ
ズ或いはバースト処理の結果、記憶値が変化することを
意味する。１１１００１００のような２進値を記憶する
システムにおいて、残留磁気状態が変化し、データの１
が０にまた０が１に化けてしまう。これにより、例えば
１１０００１０１のようになる。ここで左から３番目及
び８番目の値はランダム・エラーである。バースト源に
よるエラーの発生は、例えば１１１１１１１０のように
現れる。ここで最初の７つの連続する位置はオーバライ
トされており、位置３から７までは実際にエラーであ
る。

【００２２】“消去”は記憶ロケーションからのデータ
値の除去を言う。例えば、データ・ストリング１ｘｘｘ
ｘ１００は位置２から５において２進値が省かれてい
る。

【００２３】パリティ及び他の代数コード 代数コーディングは異なるデータ内容におけるエラーを
検出し訂正する数多くの入念なコード及び工夫に富んで
いる。後者にはノイズの多いチャネルにおける通信やＤ
ＡＳＤ配列上へのインタリーブ化ビット、バイト或いは
ブロックの記録が含まれる。冗長記憶の単純化及び最小
化処理のために、多くの著者が単純なパリティ・コード
を利用してきた。これは上述のOuchi の特許の中で述べ
られている。

【００２４】単純なパリティ・コードを用いる有限及び
半無限配列内のデータのエラー検出及び訂正は、データ
配列に渡ってパリティを縦断的同様、対角線方向にまた
横断的に取ることにより拡張される。これらのパリティ
・コードはブロック・タイプであり、１つの有限配列に
関し取られるアクションがその隣の配列に関し取られる
アクションとは独立であることを意味する。これにより
エラーの伝搬或いはサイクリックなコードにおいて見ら
れるようなブロックからブロックへの間違いが回避され
る。

【００２５】ブロック及びコンボルーション・コードに
おける従来のパリティ・コードEachusによる米国特許第
３６８５０１６号“Array Method And Apparatus ForEn
coding Detecting And/Or Correcting Data”（１９７
２年８月１５日公報）ではコンボルーショナル・コード
化データの準無限ストリングに適応される多数決論理エ
ラー検出方法が開示されている。Eachusの場合、Ｎ＊Ｋ
データ配列はＮビットに渡る最初のチェック・セグメン
トのデコードを配列の各列に沿う一連のＸＯＲ加算とし
て使用する。ここでＮは素数である。Eachusはまた、Ｎ
ビットに渡る第２及び第３のチェック・セグメントのデ
コードを、配列をよぎる一連の各左右の対角線に沿う一
連のＸＯＲ加算として開示している。

【００２６】更に、Patelによる米国特許第４２０１９
７６号“Plural Channel ErrorCorrecting Methods And
Means Using Adaptive Reallocation of RedundantCha
nnels Among GroupsOf Channels” （１９８０年５月６
日公報）、及び同じくPatelによる米国特許第４２０５
３２４号“Simultaneously CorrectingSeveral Channel
s In Error In A Parallel Multi Channel Data System
UsingContinuously Modifiable Syndromes And Select
ive Generation Of InternalChannel Pointers”（１９
８０年５月２７日公報）を参照されたい。これらの特許
では、Eachusの場合をスペア行列を使用することにより
拡張している。この行は対角線及び横断パリティを支援
することにより、多重トラック磁気テープ記憶データ・
システムにおけるエラー訂正を拡張している。

【００２７】Patelの方法はPrusinkiewicz及びBudkowsk
iによる“A Double Track ErrorCorrection Code for M
agnetic Tape”（IEEE訳Computers、ｐｐ６４２−６４
５、１９７６年６月）を基本としている。ここでは準無
限フィールド上に定義されるサイクリック・コードすな
わち無限テープ上のコンボルーション・コードを構成す
る。Patelは第２の対角線を追加している。不都合に
も、エンコード化シーケンスがたとえどんなに長くて
も、コンボルーション・コード内のエラーはエンコード
化シーケンスを通じて伝搬する。ブロック・コードはエ
ラー伝搬を個々の長さに制限する。

【００２８】Schilling等による米国特許第４７９６２
６０号“Schilling-Manela ForwardError Correction a
nd Detection Code Method and Apparatus”（１９８９
年１月３日公報）では任意のＧ＊Ｈデータ配列の異なる
スロープの対角線パリティを２セット使用することを開
示している。

【００２９】スモール・ライト・オペレーション 数多くの出願が、配列へまた配列から長いデータ・スト
リームをパスする方法に関係している。しかし、トラン
ザクション処理は通常非常に多くの異なる短いデータ・
ストリームを使用する。プロセサと外部記憶装置或いは
ＤＡＳＤ配列との間で短いデータ・ストリームをパスす
ることは、“スモール・リード”及び“スモール・ライ
ト”オペレーションと称される。書き込みオペレーショ
ンは典型的には、旧データ及び旧パリティの読み出し、
旧データ、旧パリティ及び新データの関数としての新パ
リティの計算、ＤＡＳＤ配列への新データ及び新パリテ
ィの書き込み、そして書き込み後のベリファイ・リード
といった３或いは４ステップを含む。

【００３０】

【発明が解決しようとする課題】本発明の目的はデータ
・エラー、消去及びＤＡＳＤ故障に対するＤＡＳＤ配列
の可用性を拡張させるための方法及び手段を提供するこ
とである。

【００３１】本発明の別の目的は、Ｍ個のＤＡＳＤ配列
における最大２個までの使用不能ＤＡＳＤの消去を含
む、データ内容のエンコーディング及び再作成方法及び
手段を提供する。

【００３２】更に本発明の別の目的は、（１）第２のＤ
ＡＳＤ故障においても低下モード・オペレーションを許
可し、（２）単純パリティ・グループ・コーディング及
びスペアＤＡＳＤ上へのデータ再作成方法を提供する。
これによりＤＡＳＤ配列は故障許容に復帰する。

【００３３】

【課題を解決するための手段】その他の関連する目的と
しては、（３）単純パリティ・エンコーディング及びデ
コーディング、或いはReed-Solomonの場合に見られるよ
うな有限フィールドにおける代数オペレーションを回避
するためにＸＯＲオペレーションを使用すること、
（４）Patel の場合のようなコンボルーション・タイプ
・コーディングではなく、ブロックに渡るＸＯＲパリテ
ィ・コーディングだけを実行すること、（５）書き込み
更新及び単純パリティ・エンコーディングの実行に関す
るオペレーション数の削減が含まれる。

【００３４】前述の目的は以下に示すステップを含む方
法及び手段により達成される。 （ａ）トロイダル（ジグザグ及び巡回）横断線による臨
界次元のデータ配列上における繰り返し単純パリティ・
エンコーディング、（ｂ）ＤＡＳＤ配列へのパリティ・
コード化データ配列のストライピング及び書き込み、
（ｃ）２つまでのＤＡＳＤ故障への対応、データ配列へ
のアクセスによるパターン的或いはランダム的なデータ
の再作成及び上記ステップ（ａ）及び（ｂ）の繰り返
し、ここで前記横断線は使用不能ＤＡＳＤを考慮して、
多少変更される。

【００３５】更に詳しくは、上記方法は前述のパリティ
・エンコーディングを含め、（Ｍ−１）＊Ｍデータ・ビ
ット配列内のビットに関する単純パリティ・エンコーデ
ィング対の繰り返し生成を含む。それぞれの対角線メジ
ャー及び行メジャー順序におけるこの生成では、データ
配列をトポロギー的円柱としてカバーする。すなわち、
１つのパリティ・エンコーディングは対角線パリティと
交差する行において取得される。ここで配列次元Ｍは素
数でなければならない。

【００３６】用語“トロイド”及び“トポロギー的円
柱”は（Ｍ−１）＊Ｍデータ配列のコーディング（エン
コーディング及びデコーディング）横断線により定義さ
れる理論幾何学的な平面を意味する。この点に関して、
トロイド（トーラス）は半径ｒの円をこの円と同じ平面
内にある軸の回りを中心からの距離ａ＞ｒで回転させる
ことにより得られる表面である。

【００３７】次に、データ配列或いはこの一部のコーデ
ィングの完了時に、対角線メジャー順序におけるその時
のＭビットがストライプされ、Ｍ個の故障独立型ＤＡＳ
Ｄの対のものに書き込まれる。最終的に、最大２つまで
のＤＡＳＤの不可用性に応じて、消去を含むデータ配列
をアクセスすることにより、またパリティ・コーディン
グが当初処理されたのと同様にステップ（ａ）及び
（ｂ）をスケジュール的に或いは好機に繰り返すことに
より、使用不能なデータが少なくとも（Ｍ−２）以上の
使用可能なＤＡＳＤから再作成される。

【００３８】（Ｍ−１）＊Ｍ配列では各行及び対角線は
偶数パリティを有する。例えば参照されるバイトを構成
するビットは水平的ではなく対角的に読み出される。横
断線はＭ本の対角線を定義する左上コーナから任意にス
タートする。こうしたダブル・コード化パリティ及び横
断線の使用により、（Ｍ−１）＊Ｍ配列コードはＭが素
数の場合に限り任意のバイトを訂正可能である。

【００３９】有利な点として、配列へのスモール或いは
ショート書き込みにおいて、本質的に単一パリティ・エ
ンコーディング及びデータ再作成で定義された場合と同
一な方法を使用する。このためにオペレーション／更新
の数は最小に維持される。

【００４０】配列がいくつかのＤＡＳＤをスペアとして
確保しているか或いは配列内のＤＡＳＤ上に空間を確保
していると、スペアが故障したＤＡＳＤの代用として機
能し、再作成されるデータはスペアを含むＭ個のＤＡＳ
Ｄ配列に書き込まれる。

【００４１】最終的に本発明の方法及び手段は同期式で
あるかどうかに関わらず、ＤＡＳＤ配列上において実施
される。同期式でない場合には、スループットは同期式
の場合ほど高くはない。

【００４２】

【実施例】図１を参照すると、並列パス１１、１３、１
５及び１７上において知能的パリティ生成及びストライ
ピング・バッファ（ＰＳＢ）７と結合される、第１及び
第２のパリティ・グループにより構成される配列が示さ
れている。ＣＰＵ１及びＣＰＵ２から成るプロセサ配列
はデータ及び制御バス９に結合される。

【００４３】プロセサ１或いは３に由来する読み出し及
び書き込みコマンドは、標準のアクセス・プロトコル及
びメモリ５により共用されるバス９上におけるＰＳＢ７
へのデータ転送により、ＤＡＳＤパリティ・グループへ
のテーブル指向アクセス・パスを形成する。論理ファイ
ルの論理処理はＰＳＢ７により実行される。この点に関
し、論理処理はストライピング（データのシリアル／パ
ラレル変換）及びパリティ生成及びチェックを含む。Ｄ
ＡＳＤへのパスからは直接にテーブル指向される。原則
的には、読み出し或いは書き込み引数内で特定されるア
ドレスは、配列記憶アドレス・テーブルを介してＰＳＢ
７により、ＰＳＢ７とパリティ・グループのＤＡＳＤ上
のロケーションとの間の実際の物理的パスに変換され
る。

【００４４】書き込みコマンドを実行するために、ＰＳ
Ｂ７は最初にプロセサからのデータをバッファし、読み
出し、そしてＤＡＳＤパリティ・グループからの（Ｍ−
１）＊Ｍデータ配列をバッファする。このパリティ・グ
ループ内にはブロックのストライプ或いはインタリーブ
要素が書き込まれる。そして、旧データ、旧パリティ、
及び新データを考慮しながら新たに指定される対角線及
び行パリティを含む配列を繰り返し計算し、次に修正さ
れたデータ配列をＤＡＳＤパリティ・グループ上に再書
き込みする。

【００４５】読み出しオペレーションでは、ＰＳＢ７は
プロセサからの読み出しコマンドに応答して、書き込み
オペレーションの場合と逆のシーケンスを達成する。す
なわち、読み出されるべきデータが抽出されなければな
らないデータ配列が、ＰＳＢ７においてバッファされ、
適当な行及び対角線パリティがテストされ、アドレスさ
れたデータがバス９を介して共用メモリ５に転送され
る。

【００４６】ＤＡＳＤ故障及びホット・スペアリング データの読み出しアクセス中にＤＡＳＤ故障が発生した
場合は、ＰＳＢ７は数多くの代替の中から１つを選択で
きる。これらには（１）読み出しコマンドの再試行、或
いは（２）本発明による残りのＤＡＳＤからのデータの
再作成及び置換の一方により、即座に障害を来たしたデ
ータを再生成することが含まれる。

【００４７】読み出しコマンドの発生元となるプロセサ
１或いは３に関し、データ読み出し動作の完了後におい
てのみ故障の発生を知らせることが１つの戦略である。
これはプロセサに対し、Park等の場合、同様に、スペア
ＤＡＳＤをプールから或いは各パリティ・グループに専
用に確保されているＤＡＳＤから代用するかを制御させ
る。使用禁止及び再作成などのプロセサ・コマンドに応
答して、ＰＳＢ７はこのスペアへのディレクトリ・パス
を故障ＤＡＳＤのテーブル・ディレクトリ・パスに代用
するテーブルを使用することにより、故障ＤＡＳＤを指
定したスペアＤＡＳＤにより置換する。次に、故障ＤＡ
ＳＤ上のデータが、指定されたスペアＤＡＳＤ上に再作
成される。

【００４８】１つの実施例では、ＰＳＢ７はＤＡＳＤ可
用性のビット・マップとＤＡＳＤのアドレス・マップを
記憶する。また、可用性及びアドレスのマップは各アク
セス・コマンドの処理期間中に参照される。このマップ
への変更は使用禁止及び再作成コマンドを使用するプロ
セサに由来する。こうした実施例においては、永久アド
レスがスペアＤＡＳＤに対して割り当てられる。故障を
知らされた後、プロセサ１或いは３はＤＡＳＤのマップ
をアドレスできる点が重要である。一方、前述の可用性
及びアドレスのマップは各アクセス・コマンドの処理期
間中に参照される。このマップへの変更は使用禁止及び
再作成コマンドを使用するプロセサに由来する。本実施
例においては、スペアＤＡＳＤについて永久アドレスを
割り当てている。

【００４９】故障を知らされた後、プロセサは以下を実
行できる。 （１）無処理を選択する。 （２）スペアＤＡＳＤのアドレスを最大２個までの故障
ＤＡＳＤのアドレスに代用させるコマンドを生成する。 （３）下記で説明される再作成方法により、パリティと
残りのデータ用ＤＡＳＤとのモジューロ２加算により、
割り当てられたスペア上に最大２つまでの故障ＤＡＳＤ
の内容を再作成する。

【００５０】ここで、スペア・フォーマットされたＤＡ
ＳＤのオンライン上における他のＤＡＳＤに対するダイ
ナミックな代用は“ホット・スペアリング”と称され
る。

【００５１】本発明のフロー図 図２を参照すると、本発明による各（Ｍ−１）＊Ｍビッ
トのデータ配列におけるパリティ・エンコーディング・
ステップのフローが示されている。基本的には、それぞ
れ正のスロープのデータ配列対角線及び交差する行より
形成されるペアはパリティ・コード化される。これは単
に対角線上のビットはモジューロ２でカウントされ、そ
の結果が使用可能なパリティ位置に設定されることを意
味する。この対角線のパリティ位置と交差する配列行の
ビットはモジューロ２でカウントされ、その結果は使用
可能なパリティ位置に設定される。この処理はデータ配
列がカバーされるまで対角線及び行メジャー順序で繰り
返される。

【００５２】最大２つの使用不能なＤＡＳＤからのデー
タの回復或いは再作成に関する作用の相違は、消去を含
むデータ配列が少なくともＭ−２以上のＤＡＳＤからア
クセスされる後に生ずる。

【００５３】本発明によるエンコーディング例 下記に示すエンコーディング及びデコーディング／再作
成の例において、ＤＡＳＤ配列は５つの同期式ＤＡＳＤ
すなわちＣ１−Ｃ５により構成される。Ｃ１、Ｃ２及び
Ｃ３はデータの記憶用に割り当てられ、Ｃ４及びＣ５は
単純パリティを記憶するために確保される。また、この
配列はビット・インタリーブされるものと仮定する。こ
のことは３つのビットと２つのパリティ・ビット（Ｍ＝
５）が同時にＣ１−Ｃ５から読み出され、また書き込ま
れることを意味する。従って、Ｍ＝５の場合、データ配
列は４＊５次元を有することになる。

【００５４】Ｍが素数である（Ｍ−１）＊Ｍデータ配列
は下記のようになる。

【００５５】

【００５６】別の行及び対角線によるダブル・パリティ
のエンコーディング 配列は円柱状に循環するものと仮定する。この場合、エ
ンコーディング（ジグザグ状エンコーディング）は行パ
リティ割当により追従される繰り返し対角線パリティ割
当を含む。下記のコーディング作用の読み出しにおい
て、作用結果は次の連続する図によって示される。これ
らの図は正のスロープによる配列方向を取っている（左
下から右上に向かう）。

【００５７】ダミー行Ｓ５がトロイダル（ジグザグ）横
断線の概念化を容易にするために追加される。

【００５８】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ｘ ｘ Ｓ２ １ １ １ ｘ ｘ Ｓ３ ０ １ ０ ｘ ｘ Ｓ４ ０ １ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ステップ１：第１のパリティ・エンコード位置Ｓ１Ｃ４
をインターセプトする第１の対角線Ｓ４Ｃ１−Ｓ１Ｃ４
に着目し、位置Ｓ１Ｃ４に偶数パリティを挿入する。

【００５９】 ステップ２：行Ｓ１の位置Ｓ１Ｃ５に偶数パリティを割
り当てる。

【００６０】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ｄ ０ Ｓ２ １ １ １ｄ ｘ ｘ Ｓ３ ０ １ｄ ０ ｘ ｘ Ｓ４ ０ｄ １ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ステップ３：パリティ・エンコード位置Ｓ１Ｃ５をイン
ターセプトする次の対角線Ｓ４Ｃ２−Ｓ１Ｃ５に着目
し、位置Ｓ２Ｃ４に偶数パリティを挿入する。

【００６１】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ｄ Ｓ２ １ １ １ １ｄ ｘ Ｓ３ ０ １ ０ｄ ｘ ｘ Ｓ４ ０ １ｄ ０ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ステップ４：行Ｓ２の位置Ｓ２Ｃ５に偶数パリティを割
り当てる。

【００６２】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ｄ Ｓ２ １ １ １ １ｄ ｘ Ｓ３ ０ １ ０ｄ ｘ ｘ Ｓ４ ０ １ｄ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ステップ５：位置Ｓ２Ｃ５をインターセプトする次の対
角線Ｓ４Ｃ３−Ｓ１Ｃ１に着目し、位置Ｓ３Ｃ４に偶数
パリティを挿入する。

【００６３】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ １ｄ ０ １ ０ ０ Ｓ２ １ １ １ １ ０ｄ １ １ １ １ ０ Ｓ３ ０ １ ０ ０ｄ ｘ ０ １ ０ ０ ｘ Ｓ４ ０ １ １ｄ ｘ ｘ ０ １ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ステップ６：行Ｓ３の位置Ｓ３Ｃ５に偶数パリティを割
り当てる。

【００６４】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ １ｄ ０ １ ０ ０ Ｓ２ １ １ １ １ ０ｄ １ １ １ １ ０ Ｓ３ ０ １ ０ ０ｄ １ ０ １ ０ ０ ｘ Ｓ４ ０ １ １ｄ ｘ ｘ ０ １ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ステップ７：位置Ｓ１Ｃ２をインターセプトする次の対
角線Ｓ４Ｃ４−Ｓ１Ｃ２に着目し、位置Ｓ４Ｃ４に偶数
パリティを挿入する。

【００６５】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ １ ０ｄ １ ０ ０ Ｓ２ １ １ １ １ ０ １ｄ １ １ １ ０ Ｓ３ ０ １ ０ ０ １ｄ ０ １ ０ ０ ｘ Ｓ４ ０ １ １ ０ｄ ｘ ０ １ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ ステップ８：行Ｓ４の位置Ｓ４Ｃ５に偶数パリティを割
り当てる。

【００６６】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ １ ０ｄ １ ０ ０ Ｓ２ １ １ １ １ ０ １ｄ １ １ １ ０ Ｓ３ ０ １ ０ ０ １ｄ ０ １ ０ ０ ｘ Ｓ４ ０ １ １ ０ｄ ０ ０ １ １ ｘ ｘ Ｓ５ ０ ０ ０ ０ ０ ０ ０ ０ ０ ０ これでエンコード完了である。

【００６７】素数配列の場合の処理と同等な処理が、１
０＊８配列のような非素数次元配列の処理においても、
０により満たされたダミー列を付加することにより達成
される。このようにして、１０＊８配列は３列を追加す
ることにより１０＊１１配列に変換される。ここで付加
された列においては決してエラーが生じないことが知ら
れている。

【００６８】ダブルＤＡＳＤ故障からのデータ回復 この例では、（Ｍ−１）＊Ｍデータ配列は本発明による
コーディング方法によりエンコードされるものとする。
処理を開始するに当たり、最初に選択される対角線は左
側に位置する最初の欠損列からそのすぐ左列までと交差
する正のスロープの対角線である。

【００６９】ここでＤＡＳＤのＣ２及びＣ５は使用不能
と仮定する。

【００７０】 ダミー行Ｓ５がトロイダル（ジグザグ）横断線を形成す
るために追加される。

【００７０】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ｘ １ ０ ｘ １ｄ ｘ １ ０ ｘ Ｓ２ １ ｘ １ １ ｘｄ １ ｘ １ １ ｘ Ｓ３ ０ ｘ ０ ０ｄ ｘ ０ ｘ ０ ０ ｘ Ｓ４ ０ ｘ １ｄ ０ ｘ ０ ｘ １ ０ ｘ Ｓ５ ０ ０ｄ ０ ０ ０ ０ ０ ０ ０ ０ ステップ１は対角線Ｓ４Ｃ３−Ｓ１Ｃ１に着目し、Ｓ２
Ｃ５に偶数パリティｐを挿入する。

【００７１】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ｘ １ ０ ｘ １ｄ ｘ １ ０ ｘ Ｓ２ １ ｘ １ １ ０ｄｐ１ ｘ １ １ ｘ Ｓ３ ０ ｘ ０ ０ｄ ｘ ０ ｘ ０ ０ ｘ Ｓ４ ０ ｘ １ｄ ０ ｘ ０ ｘ １ ０ ｘ Ｓ５ ０ ０ｄ ０ ０ ０ ０ ０ ０ ０ ０ ステップ２は対角線パリティと交差する行Ｓ２に着目
し、Ｓ２Ｃ２に偶数パリティｐを挿入する。

【００７２】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ｘ １ ０ ｘ １ ｘ １ｄ ０ ｘ Ｓ２ １ １ｐ １ １ ０ １ １ｄｐ１ １ ０ Ｓ３ ０ ｘ ０ ０ ｘ ０ｄ ｘ ０ ０ ｘ Ｓ４ ０ ｘ １ ０ ｘｄ ０ ｘ １ ０ ｘ Ｓ５ ０ ０ ０ ０ｄ ０ ０ ０ ０ ０ ０ ステップ３はＳ２Ｃ２で行２をインターセプトする対角
線Ｓ４Ｃ５−Ｓ１Ｃ３に着目し、Ｓ４Ｃ５に偶数パリテ
ィｐを挿入する。

【００７３】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ｘ １ ０ ｘ １ ｘ １ｄ ０ ｘ Ｓ２ １ １ １ １ ０ １ １ｄ １ １ ０ Ｓ３ ０ ｘ ０ ０ ｘ ０ｄ ｘ ０ ０ ｘ Ｓ４ ０ ｘ １ ０ ０ｄｐ０ ｘ １ ０ ０ｐ Ｓ５ ０ ０ ０ ０ｄ ０ ０ ０ ０ ０ ０ ステップ４は対角線パリティをインターセプトする行Ｓ
４に着目し、Ｓ４Ｃ２に偶数パリティｐを挿入する。

【００７４】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ｘ １ ０ ｘ １ ｘ １ｄ ０ ｘ Ｓ２ １ １ １ １ ０ １ １ｄ １ １ ０ Ｓ３ ０ ｘ ０ ０ ｘ ０ｄ ｘ ０ ０ ｘ Ｓ４ ０ １ｐ １ ０ ０ｄ ０ １ｐ １ ０ ０ Ｓ５ ０ ０ ０ ０ｄ ０ ０ ０ ０ ０ ０ ステップ５はＳ４Ｃ２において行Ｓ４をインターセプト
する対角線Ｓ４Ｃ２−Ｓ１Ｃ５に着目し、Ｓ１Ｃ５に偶
数パリティｐを挿入する。

【００７５】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ｘ １ ０ ０ｐ １ ｘ １ ０ ０ｄｐ Ｓ２ １ １ １ １ ０ １ １ １ １ｄ ０ Ｓ３ ０ ｘ ０ ０ ｘ ０ ｘ ０ｄ ０ ｘ Ｓ４ ０ １ １ ０ ０ ０ １ｄ １ ０ ０ Ｓ５ ０ ０ ０ ０ ０ ０ｄ ０ ０ ０ ０ ステップ６はＳ１Ｃ５において対角線パリティをインタ
ーセプトする行Ｓ１に着目し、Ｓ１Ｃ２に偶数パリティ
ｐを挿入する。

【００７６】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ｐ １ ０ ０ １ ０ｐ １ ０ ０ｄ Ｓ２ １ １ １ １ ０ １ １ １ １ｄ ０ Ｓ３ ０ ｘ ０ ０ ｘ ０ ｘ ０ｄ ０ ｘ Ｓ４ ０ １ １ ０ ０ ０ １ｄ １ ０ ０ Ｓ５ ０ ０ ０ ０ ０ ０ｄ ０ ０ ０ ０ ステップ７はＳ１Ｃ２において行Ｓ１をインターセプト
する対角線Ｓ４Ｃ４−Ｓ１Ｃ２に着目し、Ｓ３Ｃ５に偶
数パリティｐを挿入する。

【００７７】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ １ ０ｄ １ ０ ０ Ｓ２ １ １ １ １ ０ １ｄ １ １ １ ０ Ｓ３ ０ ｘ ０ ０ １ｄｐ０ ｘ ０ ０ １ｐ Ｓ４ ０ １ １ ０ｄ ０ ０ １ １ ０ ０ Ｓ５ ０ ０ ０ｄ ０ ０ ０ ０ ０ ０ ０ ステップ８はＳ３Ｃ５において対角線パリティをインタ
ーセプトする行Ｓ３に着目し、Ｓ３Ｃ２に偶数パリティ
ｐを挿入する。

【００７８】 Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｓ１ １ ０ １ ０ ０ １ ０ｄ １ ０ ０ Ｓ２ １ １ １ １ ０ １ｄ １ １ １ ０ Ｓ３ ０ １ｐ ０ ０ １ｄ ０ １ｐ ０ ０ １ Ｓ４ ０ １ １ ０ｄ ０ ０ １ １ ０ ０ Ｓ５ ０ ０ ０ｄ ０ ０ ０ ０ ０ ０ ０ これでデータ回復が完了する。

【００７９】ここでパリティ・エンコードとデータ再作
成の唯一の違いは、前者ではＤＡＳＤの最後の２つの列
Ｃ４及びＣ５が計算されて書き込まれた値を有するのに
対し、後者ではそれがＣ２及びＣ５となる。実際に、エ
ンコーディングは本発明によるデコーディング方法の特
定なケースである。

【００８０】本発明によるスモール書き込みの例 既に述べたように、スモール或いはショート書き込みオ
ペレーションは、例えばＭ個のＤＡＳＤ配列内の１つの
ＤＡＳＤ上のいくつかのビットの置換或いは更新書き込
みを意味する。例えば、ダミー行としてＳ５を有する
（Ｍ−１）＊Ｍデータ・ビット配列がこれに相当する。

【００８１】 ここで列Ｃ２をＲ１＝０、Ｒ２＝１、Ｒ３＝１、Ｒ４
＝０、Ｒ５＝０により置換することが望まれる。

【００８２】本発明による方法によれば、行及び対角線
パリティの両方を再計算する必要がある。その際、新た
なパリティは旧データ、旧パリティ及び新データの排他
的論理和であることを考慮しなければならない。

【００８３】列Ｃ２がＲ１−Ｒ５により置換され再計算
された配列は下記のようになる。

【００８４】 列Ｃ４及びＣ５上の単純パリティは列Ｃ２の更新を反映
して再計算されている。

【００８５】ここで、（ｘ、ｙ）は配列軸におけるデー
タ値とする。更に、（ｘ、ｙ）´は新たな配列値とす
る。例えば、新たなパリティ計算は次のように示され
る。

【００８６】新たなパリティ計算 （１、４）´＝（１、４）ＸＯＲ（（３、２）ＸＯＲ（Ｒ３）） ＝０ ＸＯＲ （１ ＸＯＲ １） ＝０ ここで、（１、４）は旧パリティ、（３、２）は旧デー
タ、Ｒ３は新データである。

【００８７】 （１、５）´＝（１、５）ＸＯＲ（（１、４）ＸＯＲ（１、４）´）ＸＯＲ （（１、２）ＸＯＲ（Ｒ１）） ＝１ ＸＯＲ （０ ＸＯＲ ０）ＸＯＲ（１ ＸＯＲ ０） ＝０ であり、（１、５）は旧パリティ、（１、４）は隣接旧
パリティ、（１、４）´は隣接新パリティ、（１、２）
は旧データ、Ｒ１は新データである。

【００８８】 （４、５）´＝（４、５）ＸＯＲ（（４、４）ＸＯＲ（４、４）´）ＸＯＲ （（２、２）ＸＯＲ（Ｒ２）） ＝０ ＸＯＲ （１ ＸＯＲ １）ＸＯＲ（０ ＸＯＲ １） ＝１ となり、（４、５）は旧パリティ、（４、４）は隣接旧
パリティ、（４、４）´は隣接新パリティ、（２、２）
は旧データ、Ｒ２は新データである。

【００８９】

【発明の効果】以上説明したように、本発明によれば、
第２番目のＤＡＳＤ故障が発生した場合においても低下
モード・オペレーションを可能とし、単純パリティ・グ
ループ・コーディング方法及びスペアＤＡＳＤ上におけ
るデータ再作成方法が提供でき、これによりＤＡＳＤ配
列は故障許容され復帰される。

【図面の簡単な説明】

【図１】ストライピング、パリティ・エンコーディン
グ、スペアリング、及びスペア上でのデータ再作成を説
明するための同期式ＤＡＳＤ配列を示す図である。

【図２】交互の行及び対角線を使用するダブル・パリテ
ィのエンコーディング、及びダブルＤＡＳＤ故障を有す
る配列からのデータ回復動作のフロー図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 フィエ・タン・ハオ アメリカ合衆国カリフォルニア州、ロ ス・アルトス、ストーリ・ヒル・レーン 28060番地 (72)発明者 リチャード・ルイス・マトソン アメリカ合衆国カリフォルニア州、サ ン・ホセ、ロックビュー・コート 6838 番地 (72)発明者 ジャイシェンカー・ムーセダス・メノン アメリカ合衆国カリフォルニア州、サ ン・ホセ、モントロ・ドライブ 6017番 地 (56)参考文献 特開 昭54−88109（ＪＰ，Ａ) 特開 平２−81123（ＪＰ，Ａ) 特開 平２−291011（ＪＰ，Ａ) 実公 昭50−24819（ＪＰ，Ｙ２)

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】 Ｍ個の故障独立型のＤＡＳＤ配列におけ
   るパリティ・コード化及び最大２個の使用不能ＤＡＳＤ
   のデータ内容の再作成方法であって、 （ａ）（Ｍ−１）＊Ｍビット・データ配列を円柱状に循
   環させ、各々が１つの配列対角線と該対角線に割り当て
   られるパリティ位置と交差する行とのペアにおいて単純
   パリティ・コード化を行ってパリティ・ビットを生成
   し、 （ｂ）パリティ・コード化されたデータ配列を前記Ｍ個
   のＤＡＳＤ配列にストライピングして書き込み、 （ｃ）最大２個のＤＡＳＤが故障したとき、前記データ
   配列をアクセスし、該データ配列に含まれるパリティ・
   ビットをデータ・ビットとして扱い、故障ＤＡＳＤにパ
   リティ・ビットを生成して書き込むかのように前記ステ
   ップ（ａ）及び（ｂ）を繰り返すことによってデータ・
   ビットを修復する、 パリティ・コード化およびデータの修復方法。
2. 【請求項２】 Ｍ個のＤＡＳＤ配列内のパリティ・コー
   ド化及び最大２個の使用不能ＤＡＳＤのデータ内容の再
   作成方法であって、 （ａ）（Ｍ−１）＊Ｍデータ配列の元のデータ要素をＭ
   個のＤＡＳＤ上の対応する位置にブロック・コード化し
   て書き込むに際し、前記データ配列をトポロギ的円柱状
   に網羅して対角線及び該対角線に割り当てられるパリテ
   ィ位置と交差する行で交互に第１及び第２の単純パリテ
   ィ（ＸＯＲ）を生成し、該第１及び第２のパリティを前
   記Ｍ個のＤＡＳＤ配列の第１及び第２の故障独立型ＤＡ
   ＳＤ上に記憶させ、 （ｂ）２個以下のＤＡＳＤが使用不能のとき、使用可能
   な（Ｍ−１）個または（Ｍ−２）個のＤＡＳＤからのデ
   ータ配列に対してトポロギ的円柱状に該データ配列を網
   羅して対角線及び該対角線に割り当てられるパリティ位
   置と交差する行で交互に第１及び第２の単純パリティ
   （ＸＯＲ）を生成し、前記使用不能のＤＡＳＤのデータ
   をＤＡＳＤ配列の予備容量に再生する、 パリティ・コード化及びデータの修復方法。
3. 【請求項３】 ＣＰＵ、Ｍを素数とする少なくともＭ個
   のＤＡＳＤの配列、及びＭ個のＤＡＳＤにストライピン
   グしたＭビットを同時に読み出し又は書き込むため該Ｍ
   個のＤＡＳＤを同期アクセスするよう前記ＣＰＵおよび
   前記ＤＡＳＤの配列を結合する手段を有するシステムに
   おいて、結合手段は更に、 （ａ）（Ｍ−１）＊Ｍビット・データ配列を円柱状に循
   環させ、各々が１つの配列対角線と該対角線に割り当て
   られるパリティ位置と交差する行とのペアにおいて単純
   パリティ・コード化を行ってパリティ・ビットを生成
   し、パリティ・コード化されたデータ配列を前記Ｍ個の
   ＤＡＳＤ配列にストライピングして書き込む手段と、 （ｂ）最大２個のＤＡＳＤが故障したとき、前記データ
   配列をアクセスし、該データ配列に含まれるパリティ・
   ビットをデータ・ビットとして扱い、各々が１つの配列
   対角線と該対角線に割り当てられるパリティ位置と交差
   する行とのペアにおいて単純パリティ・コード化を行っ
   てパリティ・ビットを生成してデータ・ビットを再作成
   する手段と、 を備えたパリティ・コード化及びデータの再作成システ
   ム。