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

データの修復方法およびシステム

Info

Publication number
JPH04310137A
JPH04310137A JP3320232A JP32023291A JPH04310137A JP H04310137 A JPH04310137 A JP H04310137A JP 3320232 A JP3320232 A JP 3320232A JP 32023291 A JP32023291 A JP 32023291A JP H04310137 A JPH04310137 A JP H04310137A
Authority
JP
Japan
Prior art keywords
data
array
parity
dasd
dasds
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP3320232A
Other languages
English (en)
Other versions
JP2514289B2 (ja
Inventor
Miguel M Blaum
ミギュエル・マリオ・ブラウム
Hsieh T Hao
フィエ・タン・ハオ
Richard L Mattson
リチャード・ルイス・マトソン
Jaishankar M Menon
ジャイシェンカー・ムーセダス・メノン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH04310137A publication Critical patent/JPH04310137A/ja
Application granted granted Critical
Publication of JP2514289B2 publication Critical patent/JP2514289B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C29/00—Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation
    • G11C29/70—Masking faults in memories by using spares or by reconfiguring
    • G11C29/88—Masking faults in memories by using spares or by reconfiguring with partially good memories
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G06F11/1092—Rebuilding, e.g. when physically replacing a failing disk
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10—Digital recording or reproducing
    • G11B20/18—Error detection or correction; Testing, e.g. of drop-outs
    • G11B20/1833—Error detection or correction; Testing, e.g. of drop-outs by adding special lists or symbols to the coded information
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
    • G06F11/1012—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using codes or arrangements adapted for a specific type of error

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Quality & Reliability (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Signal Processing (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)
  • Detection And Correction Of Errors (AREA)
  • Hardware Redundancy (AREA)

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は故障独立型直接アクセス
記憶装置（ＤＡＳＤ）の配列に関し、更に詳しくはこの
ＤＡＳＤ配列上に記憶されるデータの保守可用性に関す
る。
【０００２】
【従来の技術】外部記憶装置における１つのプロセサに
よる設計は論理トラックを有する膨大な論理ＤＡＳＤを
考慮することである。各論理トラックは外部記憶（ＤＡ
ＳＤ配列）を構成する物理的ＤＡＳＤの物理的トラック
範囲の何倍もの範囲を要する。エラー訂正コーディング
及び再作成の目的に、論理トラック内のデータを論理空
間行列上にマップされる一連のビット、バイト或いはブ
ロックと見なすことが都合が良い。配列形式の論理トラ
ックから物理配列へのマッピングは本発明において使用
される重要な技術の１つである。
【０００３】数学的には配列は添字変数（ｓｕｂｓｃｒ
ｉｐｔｅｄ　ｖａｒｉａｂｌｅ）であり、添字は変数の
各例の相対的な位置順序、特に論理トラック内における
各ビット、バイト或いはブロックの位置順序を指標付け
する。また、添字の要素は配列の次元を定義する。従っ
て、配列Ａ（ｉ、ｊ）はその相対位置が２次元の閉じた
整数間隔（１、１＜（ｉ、ｊ）＜Ｎ、Ｋ）上にマップさ
れる変数“Ａ”を特定する。
【０００４】配列次元は相互に排他的である。従って、
閉じた整数間隔１＜ｉ＜Ｎ及び１＜ｊ＜Ｋにより表され
る次元はそれぞれ装置や時間などの順序（指標）を示し
、Ｎ及びＫは整数の上限である。慣例により、列順序は
１つの配列次元を指定し、行順序は他の配列次元を指定
する。この点に関しては、ＮがＤＡＳＤの番号を、また
Ｋが１つのＤＡＳＤのトラック当たりのビット、バイト
或いはブロックの番号を示す。
【０００５】同期してアクセスされるＮ個のＤＡＳＤの
物理的な配列はＤＡＳＤ配列を構成する。これに関連し
て、配列のフォーマット及びその後のアクセスが行われ
、行或いは列のどちらか一方を基本とする連続する位置
へ値を挿入することにより記憶が進行する。オペレーシ
ョンが列方向に実行されると、それは列メジャー順序“
ｃｏｌｕｍｎ　ｍａｊｏｒ　ｏｒｄｅｒ”と称される。 同様に、行方向に実行されると、行メジャー順序“ｒｏ
ｗ　ｍａｊｏｒ　ｏｒｄｅｒ”と称される。
【０００６】ＤＡＳＤ配列及び属性 ＤＡＳＤ配列は、プロセサ或いはプロセサ配列の広帯域
データ及び制御パスの終端に位置する入出力（Ｉ／Ｏ）
境界において、これらと接続される外部記憶装置形態で
ある。更に詳しくは、ＤＡＳＤ配列は、共通モード或い
は手段により動作される論理的に関連するＤＡＳＤセッ
トを意味し、その際、ＤＡＳＤセットは同期式に選択さ
れオペレートされる。ＤＡＳＤ配列はハイ・データ・レ
ート、大論理トラック・サイズ及び超高度可用性を支援
する特徴を示す。
【０００７】ハイ・データ・レートはＤＡＳＤの同期式
アクセスを必要とする。また、ＤＡＳＤの片方のグルー
プを横断する書き込みアクセスの場合には、所定のサイ
ズ（ビット、バイト、ワード、ブロック、レコード）に
区切られたデータのシリアルからパラレルへのマッピン
グが必要となり、一方、読み出しアクセスの場合にはパ
ラレルからシリアルへのマッピングが必要となる。この
マッピングはインターリービング“ｉｎｔｅｒｌｅａｖ
ｉｎｇ”或いはストライピング“ｓｔｒｉｐｉｎｇ”と
称される。
【０００８】同期式動作はＮ個のＤＡＳＤに対して同一
のｒｐｍで回転すること、同一の角度オフセットを有す
ること、また同一の形式により同時にアクセスされるこ
とを要求する。この解決はデータ転送レートを最大化す
るが、一方では並行性を最小化する。
【０００９】情報の冗長性、コーディング及びブロッキ
ング Ｐａｔｔｅｒｓｏｎ　により述べられるように、Ｎ個の
ＤＡＳＤ上に記憶されるデータは、もし完全に複写され
れば、トータル２Ｎ個の装置を必要とする。ＤＡＳＤの
故障、ノイズ或いはバースト・エラー、或いは不注意な
消去によりデータの上限以内のデータが使用不能となる
と、単にこのデータを複写する代わりに何らかの代数コ
ーディング形式が使用される。
【００１０】代数コーディングは境像データにより占有
されるほんの一部のＤＡＳＤ空間を占有することはよく
知られている。使用されるコードに依存して、ＤＡＳＤ
空間の８５％以上が１次データ記憶用に使用可能である
。例えば、簡単なパリティ・コーディング（ＸＯＲｉｎ
ｇ）により、任意の小空間が確保される。例えば、パリ
ティは１０或いは２０ブロックに渡って取られる。従っ
て、１０或いは２０個のＤＡＳＤグループの中の１つの
ＤＡＳＤだけが除外されることになる。
【００１１】障害データ或いは欠損データの検出或いは
／及び訂正のために使用される代数コードには数多くの
タイプがある。このことは、いくつかのコードはエラー
を生じたデータの値を決定するだけではなく、消去され
たデータの値を決定するためにも使用されることを意味
する。また、選択されるコードは可用性に関する他の技
術的、経済的な面とも密接な関係を有する。例えば、Ｐ
ａｒｋなどによる１９８６年１１月７日発行の“Ｐｒｏ
ｖｉｄｉｎｇ　Ｆａｕｌｔ　Ｔｏｌｅｒａｎｃｅ　ｉｎ
　Ｐａｒａｌｌｅｌ　ＳｅｃｏｎｄａｒｙＳｔｏｒａｇ
ｅ　Ｓｙｓｔｅｍｓ”、Ｐｒｉｎｃｅｔｏｎ　Ｕｎｉｖ
ｅｒｓｉｔｙ　Ｒｅｐｏｒｔ　ＣＳ−ＴＲ−０５７−８
６　ではＰａｔｔｅｒｓｏｎの場合と同様に、ハミング
・コード（Ｈａｍｍｉｎｇ　ｃｏｄｅ）　がビット・イ
ンタリーブ或いはストライプ・グループにおいて、単純
なパリティ・コードが必要とする以上のＤＡＳＤを要求
することを指摘している。
【００１２】セグメンティング（ストライピング）、単
純パリティ、及びデータ再作成（Ｄａｔａ　Ｒｅｄｏ）
典型的には、データ・ストリームが最初にＤＡＳＤスト
リング或いは配列に書き込まれるか更新されるときに、
１つ或いはそれ以上のコード文字がデータ・ストリーム
から算出される。同時にデータ・ストリームはＮブロッ
クに分割（セグメント化）され、Ｎ個のＤＡＳＤを横断
して書き込まれ、一方、代数コード化文字はＮ＋１番目
のＤＡＳＤに書き込まれる。
【００１３】この方法はＯｕｃｈｉ　による１９７８年
５月３０日公報の米国特許第４０９２７３２号“Ｓｙｓ
ｔｅｍ　ｆｏｒ　Ｒｅｃｏｖｅｒｉｎｇ　Ｄａｔａ　Ｓ
ｔｏｒｅｄ　ｉｎ　ａ　Ｆａｉｌｅｄ　Ｍｅｍｏｒｙ　
Ｕｎｉｔ”　で説明されている。Ｏｕｃｈｉ　は最初に
論理ファイルをＮデータ・ブロックにセグメント化し、
このＮデータ・ブロックの内容の排他的論理和（ＸＯＲ
ｉｎｇ）を取ることによりパリティ・ブロックを形成し
、次にこれらのデータとパリティ・ブロックをＮ＋１個
の故障独立型のＤＡＳＤを横断して書き込むことを開示
した。
【００１４】Ｏｕｃｈｉ　によれば、アスセス不能ない
ずれか１つのＤＡＳＤからの内容は、パリティ・ブロッ
クと残りのＮ個のアクセス可能なＤＡＳＤ上に記憶され
たブロックとの排他的論理和を取ることにより回復可能
である。Ｐａｔｔｅｒｓｏｎ　が指摘するように、単一
パリティ・エンコーディングの魅力的な側面の１つは、
各書き込み更新オペレーションに対し、旧ブロック、変
更ブロック及び旧パリティの排他的論理和としてパリテ
ィが再計算されることである。
【００１５】ＤＡＳＤの冗長性、予備（スペアリング）
、及びデータ再作成 データの冗長性及び関連する予備のＤＡＳＤ空間に加え
、配列の可用性もまたＤＡＳＤの冗長性と関わる。これ
らの冗長なＤＡＳＤは　“スペア”（ｓｐａｒｅ）と称
される。この点に関し、Ｄｕｎｐｈｙ　等による米国特
許第４９１４６５６号“Ｄｉｓｋ　Ｄｒｉｖｅ　Ｍｅｍ
ｏｒｙ”（１９９０年４月３日公報）では“ホット・ス
ペア”（ｈｏｔ　ｓｐａｒｅ）　と称される所定数のフ
ォーマットされたＤＡＳＤを未指定のプール（ｐｏｏｌ
）として確保する。１つのＤＡＳＤが複数の独立にアド
レス可能な同期式ＤＡＳＤグループ内で故障すると、ス
ペアの１つがこれを置換する。ここで置換されたＤＡＳ
Ｄ上に情報を再作成する問題がまだ残っている。
【００１６】米国特許第４９１４６５６号によれば、配
列に与えられる各データ・ストリングをセグメント化し
、セグメントのパリティを算出し、選択される一方の同
期式ＤＡＳＤグループのＮ個のＤＡＳＤにセグメントと
パリティを書き込む。１つのＤＡＳＤの故障は、故障し
ているＤＡＳＤからのデータがこのグループの残りのＮ
−１個のＤＡＳＤから再計算されるようにする。
【００１７】失われたデータの再計算或いは再作成スケ
ジューリングは、データの再作成（ｄａｔａ　ｒｅｄｏ
）　期間中に同一のグループ内で別の故障が発生すると
、スループットの保守と配列のサブシステムを使用不能
とするリスクとのトレード・オフを伴う。
【００１８】ＤＡＳＤ配列故障許容モード及び性能低下
モード・オペレーション故障許容はシステムが故障を耐
え、可用性のロスを伴うこと無くオペレーションを継続
する能力を言う。故障発生から配列を以前の情報状態に
戻すまでの間隔を性能低下モード・オペレーションと称
する。
【００１９】Ｏｕｃｈｉ　及びＤｕｎｐｈｙのシステム
では、もしパリティに障害が生ずると、スループットに
何らかの変更を来すこと無くデータをアクセスできる。 しかし、データに障害が起こると、各アクセスは残りの
データから影響を受けたデータの再計算とパリティを要
求するため、スループットは極端に低下する。スペアリ
ングとデータ再作成が無い場合は、第２の故障がデータ
を使用不能とする。
【００２０】パリティ・グループの２つの意味上述のＤ
ｕｎｐｈｙの特許で使用されるように、“パリティ・グ
ループ”とは少なくとも（Ｎ＋１）番目のＤＡＳＤを含
む（ここにはＮ個のＤＡＳＤに渡るパリティが記憶され
る）Ｎ個のＤＡＳＤの論理関係を意味する。しかし、こ
の用語はまたデータ・ブロックとパリティ或いは他の代
数的にコード化された冗長ブロックとの論理関係も示す
。Ｐａｔｔｅｒｓｏｎ　はＲＡＩＤタイプ５ＤＡＳＤ配
列において後者の定義を使用している。
【００２１】データ・エラー及び消去 記憶内容における“データ・エラー”はランダム・ノイ
ズ或いはバースト処理の結果、記憶値が変化することを
意味する。１１１００１００のような２進値を記憶する
システムにおいて、残留磁気状態が変化し、データの１
が０にまた０が１に化けてしまう。これにより、例えば
１１０００１０１のようになる。ここで左から３番目及
び８番目の値はランダム・エラーである。バースト源に
よるエラーの発生は、例えば１１１１１１１０のように
現れる。ここで最初の７つの連続する位置はオーバライ
トされており、位置３から７までは実際にエラーである
。
【００２２】“消去”は記憶ロケーションからのデータ
値の除去を言う。例えば、データ・ストリング１ｘｘｘ
ｘ１００は位置２から５において２進値が省かれている
。
【００２３】パリティ及び他の代数コード代数コーディ
ングは異なるデータ内容におけるエラーを検出し訂正す
る数多くの入念なコード及び工夫に富んでいる。後者に
はノイズの多いチャネルにおける通信やＤＡＳＤ配列上
へのインタリーブ化ビット、バイト或いはブロックの記
録が含まれる。冗長記憶の単純化及び最小化処理のため
に、多くの著者が単純なパリティ・コードを利用してき
た。これは上述のＯｕｃｈｉ　の特許の中で述べられて
いる。
【００２４】単純なパリティ・コードを用いる有限及び
半無限配列内のデータのエラー検出及び訂正は、データ
配列に渡ってパリティを縦断的同様、対角線方向にまた
横断的に取ることにより拡張される。これらのパリティ
・コードはブロック・タイプであり、１つの有限配列に
関し取られるアクションがその隣の配列に関し取られる
アクションとは独立であることを意味する。これにより
エラーの伝搬或いはサイクリックなコードにおいて見ら
れるようなブロックからブロックへの間違いが回避され
る。
【００２５】ブロック及びコンボルーション・コードに
おける従来のパリティ・コードＥａｃｈｕｓによる米国
特許第３６８５０１６号“Ａｒｒａｙ　Ｍｅｔｈｏｄ　
Ａｎｄ　Ａｐｐａｒａｔｕｓ　ＦｏｒＥｎｃｏｄｉｎｇ
　Ｄｅｔｅｃｔｉｎｇ　Ａｎｄ／Ｏｒ　Ｃｏｒｒｅｃｔ
ｉｎｇ　Ｄａｔａ”（１９７２年８月１５日公報）では
コンボルーショナル・コード化データの準無限ストリン
グに適応される多数決論理エラー検出方法が開示されて
いる。Ｅａｃｈｕｓの場合、Ｎ＊Ｋデータ配列はＮビッ
トに渡る最初のチェック・セグメントのデコードを配列
の各列に沿う一連のＸＯＲ加算として使用する。ここで
Ｎは素数である。Ｅａｃｈｕｓはまた、Ｎビットに渡る
第２及び第３のチェック・セグメントのデコードを、配
列をよぎる一連の各左右の対角線に沿う一連のＸＯＲ加
算として開示している。
【００２６】更に、Ｐａｔｅｌによる米国特許第４２０
１９７６号“Ｐｌｕｒａｌ　Ｃｈａｎｎｅｌ　Ｅｒｒｏ
ｒＣｏｒｒｅｃｔｉｎｇ　Ｍｅｔｈｏｄｓ　Ａｎｄ　Ｍ
ｅａｎｓ　Ｕｓｉｎｇ　Ａｄａｐｔｉｖｅ　Ｒｅａｌｌ
ｏｃａｔｉｏｎ　ｏｆ　ＲｅｄｕｎｄａｎｔＣｈａｎｎ
ｅｌｓ　Ａｍｏｎｇ　ＧｒｏｕｐｓＯｆ　Ｃｈａｎｎｅ
ｌｓ”　（１９８０年５月６日公報）、及び同じくＰａ
ｔｅｌによる米国特許第４２０５３２４号“Ｓｉｍｕｌ
ｔａｎｅｏｕｓｌｙ　ＣｏｒｒｅｃｔｉｎｇＳｅｖｅｒ
ａｌ　Ｃｈａｎｎｅｌｓ　Ｉｎ　Ｅｒｒｏｒ　Ｉｎ　Ａ
　Ｐａｒａｌｌｅｌ　Ｍｕｌｔｉ　Ｃｈａｎｎｅｌ　Ｄ
ａｔａ　Ｓｙｓｔｅｍ　ＵｓｉｎｇＣｏｎｔｉｎｕｏｕ
ｓｌｙ　Ｍｏｄｉｆｉａｂｌｅ　Ｓｙｎｄｒｏｍｅｓ　
Ａｎｄ　Ｓｅｌｅｃｔｉｖｅ　Ｇｅｎｅｒａｔｉｏｎ　
Ｏｆ　ＩｎｔｅｒｎａｌＣｈａｎｎｅｌ　Ｐｏｉｎｔｅ
ｒｓ”（１９８０年５月２７日公報）を参照されたい。 これらの特許では、Ｅａｃｈｕｓの場合をスペア行列を
使用することにより拡張している。この行は対角線及び
横断パリティを支援することにより、多重トラック磁気
テープ記憶データ・システムにおけるエラー訂正を拡張
している。
【００２７】Ｐａｔｅｌの方法はＰｒｕｓｉｎｋｉｅｗ
ｉｃｚ及びＢｕｄｋｏｗｓｋｉによる“Ａ　Ｄｏｕｂｌ
ｅ　Ｔｒａｃｋ　ＥｒｒｏｒＣｏｒｒｅｃｔｉｏｎ　Ｃ
ｏｄｅ　ｆｏｒ　Ｍａｇｎｅｔｉｃ　Ｔａｐｅ”（ＩＥ
ＥＥ訳Ｃｏｍｐｕｔｅｒｓ、ｐｐ６４２−６４５、１９
７６年６月）を基本としている。ここでは準無限フィー
ルド上に定義されるサイクリック・コードすなわち無限
テープ上のコンボルーション・コードを構成する。Ｐａ
ｔｅｌは第２の対角線を追加している。不都合にも、エ
ンコード化シーケンスがたとえどんなに長くても、コン
ボルーション・コード内のエラーはエンコード化シーケ
ンスを通じて伝搬する。ブロック・コードはエラー伝搬
を個々の長さに制限する。
【００２８】Ｓｃｈｉｌｌｉｎｇ等による米国特許第４
７９６２６０号“Ｓｃｈｉｌｌｉｎｇ−Ｍａｎｅｌａ　
ＦｏｒｗａｒｄＥｒｒｏｒ　Ｃｏｒｒｅｃｔｉｏｎ　ａ
ｎｄ　Ｄｅｔｅｃｔｉｏｎ　Ｃｏｄｅ　Ｍｅｔｈｏｄ　
ａｎｄ　Ａｐｐａｒａｔｕｓ”（１９８９年１月３日公
報）では任意のＧ＊Ｈデータ配列の異なるスロープの対
角線パリティを２セット使用することを開示している。
【００２９】スモール・ライト・オペレーション数多く
の出願が、配列へまた配列から長いデータ・ストリーム
をパスする方法に関係している。しかし、トランザクシ
ョン処理は通常非常に多くの異なる短いデータ・ストリ
ームを使用する。プロセサと外部記憶装置或いはＤＡＳ
Ｄ配列との間で短いデータ・ストリームをパスすること
は、“スモール・リード”及び“スモール・ライト”オ
ペレーションと称される。書き込みオペレーションは典
型的には、旧データ及び旧パリティの読み出し、旧デー
タ、旧パリティ及び新データの関数としての新パリティ
の計算、ＤＡＳＤ配列への新データ及び新パリティの書
き込み、そして書き込み後のベリファイ・リードといっ
た３或いは４ステップを含む。
【００３０】
【発明が解決しようとする課題】本発明の目的はデータ
・エラー、消去及びＤＡＳＤ故障に対するＤＡＳＤ配列
の可用性を拡張させるための方法及び手段を提供するこ
とである。
【００３１】本発明の別の目的は、Ｍ個のＤＡＳＤ配列
における最大２個までの使用不能ＤＡＳＤの消去を含む
、データ内容のエンコーディング及び再作成方法及び手
段を提供する。
【００３２】更に本発明の別の目的は、（１）第２のＤ
ＡＳＤ故障においても低下モード・オペレーションを許
可し、（２）単純パリティ・グループ・コーディング及
びスペアＤＡＳＤ上へのデータ再作成方法を提供する。 これによりＤＡＳＤ配列は故障許容に復帰する。
【００３３】
【課題を解決するための手段】その他の関連する目的と
しては、（３）単純パリティ・エンコーディング及びデ
コーディング、或いはＲｅｅｄ−Ｓｏｌｏｍｏｎの場合
に見られるような有限フィールドにおける代数オペレー
ションを回避するためにＸＯＲオペレーションを使用す
ること、（４）Ｐａｔｅｌ　の場合のようなコンボルー
ション・タイプ・コーディングではなく、ブロックに渡
るＸＯＲパリティ・コーディングだけを実行すること、
（５）書き込み更新及び単純パリティ・エンコーディン
グの実行に関するオペレーション数の削減が含まれる。
【００３４】前述の目的は以下に示すステップを含む方
法及び手段により達成される。 （ａ）トロイダル（ジグザグ及び巡回）横断線による臨
界次元のデータ配列上における繰り返し単純パリティ・
エンコーディング、（ｂ）ＤＡＳＤ配列へのパリティ・
コード化データ配列のストライピング及び書き込み、（
ｃ）２つまでのＤＡＳＤ故障への対応、データ配列への
アクセスによるパターン的或いはランダム的なデータの
再作成及び上記ステップ（ａ）及び（ｂ）の繰り返し、
ここで前記横断線は使用不能ＤＡＳＤを考慮して、多少
変更される。
【００３５】更に詳しくは、上記方法は前述のパリティ
・エンコーディングを含め、（Ｍ−１）＊Ｍデータ・ビ
ット配列内のビットに関する単純パリティ・エンコーデ
ィング対の繰り返し生成を含む。それぞれの対角線メジ
ャー及び行メジャー順序におけるこの生成では、データ
配列をトポロギー的円柱としてカバーする。すなわち、
１つのパリティ・エンコーディングは対角線パリティと
交差する行において取得される。ここで配列次元Ｍは素
数でなければならない。
【００３６】用語“トロイド”及び“トポロギー的円柱
”は（Ｍ−１）＊Ｍデータ配列のコーディング（エンコ
ーディング及びデコーディング）横断線により定義され
る理論幾何学的な平面を意味する。この点に関して、ト
ロイド（トーラス）は半径ｒの円をこの円と同じ平面内
にある軸の回りを中心からの距離ａ＞ｒで回転させるこ
とにより得られる表面である。
【００３７】次に、データ配列或いはこの一部のコーデ
ィングの完了時に、対角線メジャー順序におけるその時
のＭビットがストライプされ、Ｍ個の故障独立型ＤＡＳ
Ｄの対のものに書き込まれる。最終的に、最大２つまで
のＤＡＳＤの不可用性に応じて、消去を含むデータ配列
をアクセスすることにより、またパリティ・コーディン
グが当初処理されたのと同様にステップ（ａ）及び（ｂ
）をスケジュール的に或いは好機に繰り返すことにより
、使用不能なデータが少なくとも（Ｍ−２）以上の使用
可能なＤＡＳＤから再作成される。
【００３８】（Ｍ−１）＊Ｍ配列では各行及び対角線は
偶数パリティを有する。例えば参照されるバイトを構成
するビットは水平的ではなく対角的に読み出される。横
断線はＭ本の対角線を定義する左上コーナから任意にス
タートする。こうしたダブル・コード化パリティ及び横
断線の使用により、（Ｍ−１）＊Ｍ配列コードはＭが素
数の場合に限り任意のバイトを訂正可能である。
【００３９】有利な点として、配列へのスモール或いは
ショート書き込みにおいて、本質的に単一パリティ・エ
ンコーディング及びデータ再作成で定義された場合と同
一な方法を使用する。このためにオペレーション／更新
の数は最小に維持される。
【００４０】配列がいくつかのＤＡＳＤをスペアとして
確保しているか或いは配列内のＤＡＳＤ上に空間を確保
していると、スペアが故障したＤＡＳＤの代用として機
能し、再作成されるデータはスペアを含むＭ個のＤＡＳ
Ｄ配列に書き込まれる。
【００４１】最終的に本発明の方法及び手段は同期式で
あるかどうかに関わらず、ＤＡＳＤ配列上において実施
される。同期式でない場合には、スループットは同期式
の場合ほど高くはない。
【００４２】
【実施例】図１を参照すると、並列パス１１、１３、１
５及び１７上において知能的パリティ生成及びストライ
ピング・バッファ（ＰＳＢ）７と結合される、第１及び
第２のパリティ・グループにより構成される配列が示さ
れている。ＣＰＵ１及びＣＰＵ２から成るプロセサ配列
はデータ及び制御バス９に結合される。
【００４３】プロセサ１或いは３に由来する読み出し及
び書き込みコマンドは、標準のアクセス・プロトコル及
びメモリ５により共用されるバス９上におけるＰＳＢ７
へのデータ転送により、ＤＡＳＤパリティ・グループへ
のテーブル指向アクセス・パスを形成する。論理ファイ
ルの論理処理はＰＳＢ７により実行される。この点に関
し、論理処理はストライピング（データのシリアル／パ
ラレル変換）及びパリティ生成及びチェックを含む。Ｄ
ＡＳＤへのパスからは直接にテーブル指向される。原則
的には、読み出し或いは書き込み引数内で特定されるア
ドレスは、配列記憶アドレス・テーブルを介してＰＳＢ
７により、ＰＳＢ７とパリティ・グループのＤＡＳＤ上
のロケーションとの間の実際の物理的パスに変換される
。
【００４４】書き込みコマンドを実行するために、ＰＳ
Ｂ７は最初にプロセサからのデータをバッファし、読み
出し、そしてＤＡＳＤパリティ・グループからの（Ｍ−
１）＊Ｍデータ配列をバッファする。このパリティ・グ
ループ内にはブロックのストライプ或いはインタリーブ
要素が書き込まれる。そして、旧データ、旧パリティ、
及び新データを考慮しながら新たに指定される対角線及
び行パリティを含む配列を繰り返し計算し、次に修正さ
れたデータ配列をＤＡＳＤパリティ・グループ上に再書
き込みする。
【００４５】読み出しオペレーションでは、ＰＳＢ７は
プロセサからの読み出しコマンドに応答して、書き込み
オペレーションの場合と逆のシーケンスを達成する。す
なわち、読み出されるべきデータが抽出されなければな
らないデータ配列が、ＰＳＢ７においてバッファされ、
適当な行及び対角線パリティがテストされ、アドレスさ
れたデータがバス９を介して共用メモリ５に転送される
。
【００４６】ＤＡＳＤ故障及びホット・スペアリングデ
ータの読み出しアクセス中にＤＡＳＤ故障が発生した場
合は、ＰＳＢ７は数多くの代替の中から１つを選択でき
る。これらには（１）読み出しコマンドの再試行、或い
は（２）本発明による残りのＤＡＳＤからのデータの再
作成及び置換の一方により、即座に障害を来たしたデー
タを再生成することが含まれる。
【００４７】読み出しコマンドの発生元となるプロセサ
１或いは３に関し、データ読み出し動作の完了後におい
てのみ故障の発生を知らせることが１つの戦略である。 これはプロセサに対し、Ｐａｒｋ等の場合、同様に、ス
ペアＤＡＳＤをプールから或いは各パリティ・グループ
に専用に確保されているＤＡＳＤから代用するかを制御
させる。使用禁止及び再作成などのプロセサ・コマンド
に応答して、ＰＳＢ７はこのスペアへのディレクトリ・
パスを故障ＤＡＳＤのテーブル・ディレクトリ・パスに
代用するテーブルを使用することにより、故障ＤＡＳＤ
を指定したスペアＤＡＳＤにより置換する。次に、故障
ＤＡＳＤ上のデータが、指定されたスペアＤＡＳＤ上に
再作成される。
【００４８】１つの実施例では、ＰＳＢ７はＤＡＳＤ可
用性のビット・マップとＤＡＳＤのアドレス・マップを
記憶する。また、可用性及びアドレスのマップは各アク
セス・コマンドの処理期間中に参照される。このマップ
への変更は使用禁止及び再作成コマンドを使用するプロ
セサに由来する。こうした実施例においては、永久アド
レスがスペアＤＡＳＤに対して割り当てられる。故障を
知らされた後、プロセサ１或いは３はＤＡＳＤのマップ
をアドレスできる点が重要である。一方、前述の可用性
及びアドレスのマップは各アクセス・コマンドの処理期
間中に参照される。このマップへの変更は使用禁止及び
再作成コマンドを使用するプロセサに由来する。本実施
例においては、スペアＤＡＳＤについて永久アドレスを
割り当てている。
【００４９】故障を知らされた後、プロセサは以下を実
行できる。 （１）無処理を選択する。 （２）スペアＤＡＳＤのアドレスを最大２個までの故障
ＤＡＳＤのアドレスに代用させるコマンドを生成する。 （３）下記で説明される再作成方法により、パリティと
残りのデータ用ＤＡＳＤとのモジューロ２加算により、
割り当てられたスペア上に最大２つまでの故障ＤＡＳＤ
の内容を再作成する。
【００５０】ここで、スペア・フォーマットされたＤＡ
ＳＤのオンライン上における他のＤＡＳＤに対するダイ
ナミックな代用は“ホット・スペアリング”と称される
。
【００５１】本発明のフロー図 図２を参照すると、本発明による各（Ｍ−１）＊Ｍビッ
トのデータ配列におけるパリティ・エンコーディング・
ステップのフローが示されている。基本的には、それぞ
れ正のスロープのデータ配列対角線及び交差する行より
形成されるペアはパリティ・コード化される。これは単
に対角線上のビットはモジューロ２でカウントされ、そ
の結果が使用可能なパリティ位置に設定されることを意
味する。この対角線のパリティ位置と交差する配列行の
ビットはモジューロ２でカウントされ、その結果は使用
可能なパリティ位置に設定される。この処理はデータ配
列がカバーされるまで対角線及び行メジャー順序で繰り
返される。
【００５２】最大２つの使用不能なＤＡＳＤからのデー
タの回復或いは再作成に関する作用の相違は、消去を含
むデータ配列が少なくともＭ−２以上のＤＡＳＤからア
クセスされる後に生ずる。
【００５３】本発明によるエンコーディング例下記に示
すエンコーディング及びデコーディング／再作成の例に
おいて、ＤＡＳＤ配列は５つの同期式ＤＡＳＤすなわち
Ｃ１−Ｃ５により構成される。Ｃ１、Ｃ２及びＣ３はデ
ータの記憶用に割り当てられ、Ｃ４及びＣ５は単純パリ
ティを記憶するために確保される。また、この配列はビ
ット・インタリーブされるものと仮定する。このことは
３つのビットと２つのパリティ・ビット（Ｍ＝５）が同
時にＣ１−Ｃ５から読み出され、また書き込まれること
を意味する。従って、Ｍ＝５の場合、データ配列は４＊
５次元を有することになる。
【００５４】Ｍが素数ａである（Ｍ−１）＊Ｍデータ配
列は下記のようになる。
【００５５】
【００５６】別の行及び対角線によるダブル・パリティ
のエンコーディング 配列は円柱状に循環するものと仮定する。この場合、エ
ンコーディングは行パリティ割当（ジグザグ状エンコー
ディング）により追従される繰り返し対角線パリティ割
当を含む。下記のコーディング作用の読み出しにおいて
、作用結果は次の連続する図によって示される。これら
の図は正のスロープによる配列方向を取っている（左下
から右上に向かう）。
【００５７】ダミー行Ｓ５がトロイダル（ジグザグ）横
断線の概念化を容易にするために追加される。
【００５８】 ステップ１：第１のパリティ・エンコード位置Ｓ１Ｃ４
をインターセプトする第１の対角線Ｓ４Ｃ１に着目し、
位置Ｓ１Ｃ４に偶数パリティを挿入する。
【００５９】 ステップ２：行Ｓ１の位置Ｓ１Ｃ５に偶数パリティを割
り当てる。
【００６０】 ステップ３：パリティ・エンコード位置Ｓ１Ｃ５をイン
ターセプトする次の対角線Ｓ４Ｃ２に着目し、位置Ｓ２
Ｃ４に偶数パリティを挿入する。
【００６１】 ステップ４：行Ｓ２の位置Ｓ２Ｃ５に偶数パリティを割
り当てる。
【００６２】 ステップ５：位置Ｓ２Ｃ５をインターセプトする次の対
角線Ｓ４Ｃ３に着目し、位置Ｓ３Ｃ４に偶数パリティを
挿入する。
【００６３】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　０　　　　１　　　　
０　　　　０　　　　１ｄ　　０　　　　１　　　　０
　　　　０　　　　　　Ｓ２　　　　１　　　　１　　
　　１　　　　１　　　　０ｄ　　１　　　　１　　　
　１　　　　１　　　　０　　　　　　Ｓ３　　　　０
　　　　１　　　　０　　　　０ｄ　　ｘ　　　　０　
　　　１　　　　０　　　　０　　　　ｘ　　　　　　
Ｓ４　　　　０　　　　１　　　　１ｄ　　ｘ　　　　
ｘ　　　　０　　　　１　　　　１　　　　ｘ　　　　
ｘ　　　　　　Ｓ５　　　　０　　　　０　　　　０　
　　　０　　　　０　　　　０　　　　０　　　　０　
　　　０　　　　０　　 ステップ６：行Ｓ３の位置Ｓ３Ｃ５に偶数パリティを割
り当てる。
【００６４】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　０　　　　１　　　　
０　　　　０　　　　１ｄ　　０　　　　１　　　　０
　　　　０　　　　　　Ｓ２　　　　１　　　　１　　
　　１　　　　１　　　　０ｄ　　１　　　　１　　　
　１　　　　１　　　　０　　　　　　Ｓ３　　　　０
　　　　１　　　　０　　　　０ｄ　　１　　　　０　
　　　１　　　　０　　　　０　　　　１　　　　　　
Ｓ４　　　　０　　　　１　　　　１ｄ　　ｘ　　　　
ｘ　　　　０　　　　１　　　　１　　　　ｘ　　　　
ｘ　　　　　　Ｓ５　　　　０　　　　０　　　　０　
　　　０　　　　０　　　　０　　　　０　　　　０　
　　　０　　　　０　　 ステップ７：位置Ｓ１Ｃ２をインターセプトする次の対
角線Ｓ４Ｃ４に着目し、位置Ｓ４Ｃ４に偶数パリティを
挿入する。
【００６５】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　０　　　　１　　　　
０　　　　０　　　　１　　　　０ｄ　　１　　　　０
　　　　０　　　　　　Ｓ２　　　　１　　　　１　　
　　１　　　　１　　　　０　　　　１ｄ　　１　　　
　１　　　　１　　　　０　　　　　　Ｓ３　　　　０
　　　　１　　　　０　　　　０　　　　１ｄ　　０　
　　　１　　　　０　　　　０　　　　ｘ　　　　　　
Ｓ４　　　　０　　　　１　　　　１　　　　０ｄ　　
ｘ　　　　０　　　　１　　　　１　　　　ｘ　　　　
ｘ　　　　　　Ｓ５　　　　０　　　　０　　　　０　
　　　０　　　　０　　　　０　　　　０　　　　０　
　　　０　　　　０　　 ステップ８：行Ｓ４の位置Ｓ４Ｃ５に偶数パリティを割
り当てる。
【００６６】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　０　　　　１　　　　
０　　　　０　　　　１　　　　０ｄ　　１　　　　０
　　　　０　　　　　　Ｓ２　　　　１　　　　１　　
　　１　　　　１　　　　０　　　　１ｄ　　１　　　
　１　　　　１　　　　０　　　　　　Ｓ３　　　　０
　　　　１　　　　０　　　　０　　　　１ｄ　　０　
　　　１　　　　０　　　　０　　　　ｘ　　　　　　
Ｓ４　　　　０　　　　１　　　　１　　　　０ｄ　　
０　　　　０　　　　１　　　　１　　　　ｘ　　　　
ｘ　　　　　　Ｓ５　　　　０　　　　０　　　　０　
　　　０　　　　０　　　　０　　　　０　　　　０　
　　　０　　　　０　　 これでエンコード完了である。
【００６７】素数配列の場合の処理と同等な処理が、１
０＊８配列のような非素数次元配列の処理においても、
０により満たされたダミー列を付加することにより達成
される。このようにして、１０＊８配列は３列を追加す
ることにより１０＊１１配列に変換される。ここで付加
された列においては決してエラーが生じないことが知ら
れている。
【００６８】ダブルＤＡＳＤ故障からのデータ回復この
例では、（Ｍ−１）＊Ｍデータ配列は本発明によるコー
ディング方法によりエンコードされるものとする。 処理を開始するに当たり、最初に選択される対角線は左
側に位置する最初の欠損列からそのすぐ左列までと交差
する正のスロープの対角線である。
【００６９】ここでＤＡＳＤのＣ２及びＣ５は使用不能
と仮定する。
【００７０】 ダミー行Ｓ５がトロイダル（ジグザグ）横断線を形成す
るために追加される。
【００７０】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　ｘ　　　　１　　　　
０　　　　ｘ　　　　１ｄ　　ｘ　　　　１　　　　０
　　　　ｘ　　　　　　Ｓ２　　　　１　　　　ｘ　　
　　１　　　　１　　　　ｘｄ　　１　　　　ｘ　　　
　１　　　　１　　　　ｘ　　　　　　Ｓ３　　　　０
　　　　ｘ　　　　０　　　　０ｄ　　ｘ　　　　０　
　　　ｘ　　　　０　　　　０　　　　ｘ　　　　　　
Ｓ４　　　　０　　　　ｘ　　　　１ｄ　　０　　　　
ｘ　　　　０　　　　ｘ　　　　１　　　　０　　　　
ｘ　　　　　　Ｓ５　　　　０　　　　０ｄ　　０　　
　　０　　　　０　　　　０　　　　０　　　　０　　
　　０　　　　０　　 ステップ１は対角線Ｓ４Ｃ３−Ｓ１Ｃ１に着目し、Ｓ２
Ｃ５に偶数パリティｐを挿入する。
【００７１】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　ｘ　　　　１　　　　
０　　　　ｘ　　　　１ｄ　　ｘ　　　　１　　　　０
　　　　ｘ　　　　　　Ｓ２　　　　１　　　　ｘ　　
　　１　　　　１　　　　０ｄｐ１　　　　ｘ　　　　
１　　　　１　　　　ｘ　　　　　　Ｓ３　　　　０　
　　　ｘ　　　　０　　　　０ｄ　　ｘ　　　　０　　
　　ｘ　　　　０　　　　０　　　　ｘ　　　　　　Ｓ
４　　　　０　　　　ｘ　　　　１ｄ　　０　　　　ｘ
　　　　０　　　　ｘ　　　　１　　　　０　　　　ｘ
　　　　　　Ｓ５　　　　０　　　　０ｄ　　０　　　
　０　　　　０　　　　０　　　　０　　　　０　　　
　０　　　　０　　 ステップ２は対角線パリティと交差する行Ｓ２に着目し
、Ｓ２Ｃ２に偶数パリティｐを挿入する。
【００７２】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　ｘ　　　　１　　　　
０　　　　ｘ　　　　１　　　　ｘ　　　　１ｄ　　０
　　　　ｘ　　　　　　Ｓ２　　　　１　　　　１ｐ　
　１　　　　１　　　　０　　　　１　　　　１ｄｐ１
　　　　１　　　　０　　　　　　Ｓ３　　　　０　　
　　ｘ　　　　０　　　　０　　　　ｘ　　　　０ｄ　
　ｘ　　　　０　　　　０　　　　ｘ　　　　　　Ｓ４
　　　　０　　　　ｘ　　　　１　　　　０　　　　ｘ
ｄ　　０　　　　ｘ　　　　１　　　　０　　　　ｘ　
　　　　　Ｓ５　　　　０　　　　０　　　　０　　　
　０ｄ　　０　　　　０　　　　０　　　　０　　　　
０　　　　０　　 ステップ３はＳ２Ｃ２で行２をインターセプトする対角
線Ｓ４Ｃ５−Ｓ１Ｃ３に着目し、Ｓ４Ｃ５に偶数パリテ
ィｐを挿入する。
【００７３】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　ｘ　　　　１　　　　
０　　　　ｘ　　　　１　　　　ｘ　　　　１ｄ　　０
　　　　ｘ　　　　　　Ｓ２　　　　１　　　　１　　
　　１　　　　１　　　　０　　　　１　　　　１ｄ　
　１　　　　１　　　　０　　　　　　Ｓ３　　　　０
　　　　ｘ　　　　０　　　　０　　　　ｘ　　　　０
ｄ　　ｘ　　　　０　　　　０　　　　ｘ　　　　　　
Ｓ４　　　　０　　　　ｘ　　　　１　　　　０　　　
　０ｄｐ０　　　　ｘ　　　　１　　　　０　　　　０
ｐ　　　　Ｓ５　　　　０　　　　０　　　　０　　　
　０ｄ　　０　　　　０　　　　０　　　　０　　　　
０　　　　０　　 ステップ４は対角線パリティをインターセプトする行Ｓ
４に着目し、Ｓ４Ｃ２に偶数パリティｐを挿入する。
【００７４】 　　　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ
４　　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５
　　　　Ｓ１　　　　１　　　　ｘ　　　　１　　　　
０　　　　ｘ　　　　１　　　　ｘ　　　　１ｄ　　０
　　　　ｘ　　　　　　Ｓ２　　　　１　　　　１　　
　　１　　　　１　　　　０　　　　１　　　　１ｄ　
　１　　　　１　　　　０　　　　　　Ｓ３　　　　０
　　　　ｘ　　　　０　　　　０　　　　ｘ　　　　０
ｄ　　ｘ　　　　０　　　　０　　　　ｘ　　　　　　
Ｓ４　　　　０　　　　１ｐ　　１　　　　０　　　　
０ｄ　　０　　　　１ｐ　　１　　　　０　　　　０　
　　　　　Ｓ５　　　　０　　　　０　　　　０　　　
　０ｄ　　０　　　　０　　　　０　　　　０　　　　
０　　　　０　　 ステップ５はＳ４Ｃ２において行Ｓ４をインターセプト
する対角線Ｓ４Ｃ２−Ｓ１Ｃ５に着目し、Ｓ１Ｃ５に偶
数パリティｐを挿入する。
【００７５】 　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　
　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５　　
　　Ｓ１　　１　　　　ｘ　　　　１　　　　０　　　
　０ｐ　　１　　　　ｘ　　　　１　　　　０　　　　
０ｄｐ　　　　Ｓ２　　１　　　　１　　　　１　　　
　１　　　　０　　　　１　　　　１　　　　１　　　
　１ｄ　　０　　　　　　Ｓ３　　０　　　　ｘ　　　
　０　　　　０　　　　ｘ　　　　０　　　　ｘ　　　
　０ｄ　　０　　　　ｘ　　　　　　Ｓ４　　０　　　
　１　　　　１　　　　０　　　　０　　　　０　　　
　１ｄ　　１　　　　０　　　　０　　　　　　Ｓ５　
　０　　　　０　　　　０　　　　０　　　　０　　　
　０ｄ　　０　　　　０　　　　０　　　　０　　 ステップ６はＳ１Ｃ５において対角線パリティをインタ
ーセプトする行Ｓ１に着目し、Ｓ１Ｃ２に偶数パリティ
ｐを挿入する。
【００７６】 　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　
　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５　　
　　Ｓ１　　１　　　　０ｐ　　１　　　　０　　　　
０　　　　１　　　　０ｐ　　１　　　　０　　　　０
ｄ　　　　Ｓ２　　１　　　　１　　　　１　　　　１
　　　　０　　　　１　　　　１　　　　１　　　　１
ｄ　　０　　　　　　Ｓ３　　０　　　　ｘ　　　　０
　　　　０　　　　ｘ　　　　０　　　　ｘ　　　　０
ｄ　　０　　　　ｘ　　　　　　Ｓ４　　０　　　　１
　　　　１　　　　０　　　　０　　　　０　　　　１
ｄ　　１　　　　０　　　　０　　　　　　Ｓ５　　０
　　　　０　　　　０　　　　０　　　　０　　　　０
ｄ　　０　　　　０　　　　０　　　　０　　 ステップ７はＳ１Ｃ２において行Ｓ１をインターセプト
する対角線Ｓ４Ｃ４−Ｓ１Ｃ２に着目し、Ｓ３Ｃ５に偶
数パリティｐを挿入する。
【００７７】 　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　
　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５　　
　　Ｓ１　　１　　　　０　　　　１　　　　０　　　
　０　　　　１　　　　０ｄ　　１　　　　０　　　　
０　　　　　　Ｓ２　　１　　　　１　　　　１　　　
　１　　　　０　　　　１ｄ　　１　　　　１　　　　
１　　　　０　　　　　　Ｓ３　　０　　　　ｘ　　　
　０　　　　０　　　　１ｄｐ０　　　　ｘ　　　　０
　　　　０　　　　１ｐ　　　　Ｓ４　　０　　　　１
　　　　１　　　　０ｄ　　０　　　　０　　　　１　
　　　１　　　　０　　　　０　　　　　　Ｓ５　　０
　　　　０　　　　０ｄ　　０　　　　０　　　　０　
　　　０　　　　０　　　　０　　　　０　　 ステップ８はＳ３Ｃ５において対角線パリティをインタ
ーセプトする行Ｓ３に着目し、Ｓ３Ｃ２に偶数パリティ
ｐを挿入する。
【００７８】 　　　　　　　　　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　
　Ｃ５　　Ｃ１　　Ｃ２　　Ｃ３　　Ｃ４　　Ｃ５　　
　　Ｓ１　　１　　　　０　　　　１　　　　０　　　
　０　　　　１　　　　０ｄ　　１　　　　０　　　　
０　　　　　　Ｓ２　　１　　　　１　　　　１　　　
　１　　　　０　　　　１ｄ　　１　　　　１　　　　
１　　　　０　　　　　　Ｓ３　　０　　　　１ｐ　　
０　　　　０　　　　１ｄ　　０　　　　１ｐ　　０　
　　　０　　　　１　　　　　　Ｓ４　　０　　　　１
　　　　１　　　　０ｄ　　０　　　　０　　　　１　
　　　１　　　　０　　　　０　　　　　　Ｓ５　　０
　　　　０　　　　０ｄ　　０　　　　０　　　　０　
　　　０　　　　０　　　　０　　　　０　　 これでデータ回復が完了する。
【００７９】ここでパリティ・エンコードとデータ再作
成の唯一の違いは、前者ではＤＡＳＤの最後の２つの列
Ｃ４及びＣ５が計算されて書き込まれた値を有するのに
対し、後者ではそれがＣ２及びＣ５となる。実際に、エ
ンコーディングは本発明によるデコーディング方法の特
定なケースである。
【００８０】本発明によるスモール書き込みの例既に述
べたように、スモール或いはショート書き込みオペレー
ションは、例えばＭ個のＤＡＳＤ配列内の１つのＤＡＳ
Ｄ上のいくつかのビットの置換或いは更新書き込みを意
味する。例えば、ダミー行としてＳ５を有する（Ｍ−１
）＊Ｍデータ・ビット配列がこれに相当する。
【００８１】 　　ここで列Ｃ２をＲ１＝０、Ｒ２＝１、Ｒ３＝１、Ｒ
４＝０、Ｒ５＝０により置換することが望まれる。
【００８２】本発明による方法によれば、行及び対角線
パリティの両方を再計算する必要がある。その際、新た
なパリティは旧データ、旧パリティ及び新データの排他
的論理和であることを考慮しなければならない。
【００８３】列Ｃ２がＲ１−Ｒ５により置換され再計算
された配列は下記のようになる。
【００８４】 列Ｃ４及びＣ５上の単純パリティは列Ｃ２の更新を反映
して再計算されている。
【００８５】ここで、（ｘ、ｙ）は配列軸におけるデー
タ値とする。更に、（ｘ、ｙ）´は新たな配列値とする
。例えば、新たなパリティ計算は次のように示される。
【００８６】新たなパリティ計算 　　（１、４）´＝（１、４）ＸＯＲ（（３、２）ＸＯ
Ｒ（Ｒ３））　　　　　　　　　　　　　　＝０　ＸＯ
Ｒ　（１　ＸＯＲ　１）　　　　　　　　　　　　　　
＝０ ここで、（１、４）は旧パリティ、（３、２）は旧デー
タ、Ｒ３は新データである。
【００８７】 　　（１、５）´＝（１、５）ＸＯＲ（（１、４）ＸＯ
Ｒ（１、４）´）ＸＯＲ　　　　　　　　　　　　　　
　　（（１、２）ＸＯＲ（Ｒ１））　　　　　　　　　
　　　　　　　＝１　ＸＯＲ　（０　ＸＯＲ　０）ＸＯ
Ｒ（１　ＸＯＲ　０）　　　　　　　　　　　　　　＝
０ であり、（１、５）は旧パリティ、（１、４）は隣接旧
パリティ、（１、４）´は隣接新パリティ、（１、２）
は旧データ、Ｒ１は新データである。
【００８８】 　　（４、５）´＝（４、５）ＸＯＲ（（４、４）ＸＯ
Ｒ（４、４）´）ＸＯＲ　　　　　　　　　　　　　　
　　（（２、２）ＸＯＲ（Ｒ２））　　　　　　　　　
　　　　　　　＝０　ＸＯＲ　（１　ＸＯＲ　１）ＸＯ
Ｒ（０　ＸＯＲ　１）　　　　　　　　　　　　　　＝
１ となり、（４、５）は旧パリティ、（４、４）は隣接旧
パリティ、（４、４）´は隣接新パリティ、（２、２）
は旧データ、Ｒ２は新データである。
【００８９】
【発明の効果】以上説明したように、本発明によれば、
第２番目のＤＡＳＤ故障が発生した場合においても低下
モード・オペレーションを可能とし、単純パリティ・グ
ループ・コーディング方法及びスペアＤＡＳＤ上におけ
るデータ再作成方法が提供でき、これによりＤＡＳＤ配
列は故障許容され復帰される。
【図面の簡単な説明】
【図１】ストライピング、パリティ・エンコーディング
、スペアリング、及びスペア上でのデータ再作成を説明
するための同期式ＤＡＳＤ配列を示す図である。
【図２】交互の行及び対角線を使用するダブル・パリテ
ィのエンコーディング、及びダブルＤＡＳＤ故障を有す
る配列からのデータ回復動作のフロー図である。

Claims (11)

    【特許請求の範囲】
  1. 【請求項１】Ｍ個の故障独立型のＤＡＳＤ配列からの最
    大２個の使用不能ＤＡＳＤのデータ内容のエンコーディ
    ング及び再作成方法であって、（ａ）トロイダル（ジグ
    ザグ及び循環）横断線に従う（Ｍ−１）＊Ｍビット・デ
    ータ配列上の繰り返し単純パリティ・エンコーディング
    であり、該エンコーディングは各々が１つの配列対角線
    と該対角線に割り当てられるパリティと交差する行とに
    より形成されるペア上において定義され、（ｂ）前記Ｍ
    個のＤＡＳＤ配列にパリティ・コード化データ配列をス
    トライピング、及び書き込み、（ｃ）最大２個のＤＡＳ
    Ｄ故障に応答し、前記データ配列をアクセスすることに
    よりパターン的或いはランダム的にデータを再作成し、
    逆の横断線によりステップ（ａ）及び（ｂ）を繰り返す
    ことを特徴とする方法。
  2. 【請求項２】Ｍ個の故障独立型のＤＡＳＤ配列からの最
    大２個の使用不能ＤＡＳＤのデータ内容のエンコーディ
    ング及び再作成方法であって、（ａ）パリティ・エンコ
    ーディングを含む（Ｍ−１）＊Ｍデータ・ビット配列内
    のビット上の単純パリティ・エンコーディングのペアを
    繰り返し生成し、前記生成は前記配列をトポロギ的円柱
    としてカバーする各々の対角線メジャー及び行メジャー
    順序において実施され、各対角線上に１つのパリティ・
    エンコーディング、及び前記対角線パリティと交差する
    前記行上に１つのパリティ・エンコーディングが存在し
    、Ｍは素数であり、（ｂ）対角線メジャー順序において
    、前記配列内のＭ個の故障独立型ＤＡＳＤの対のＤＡＳ
    ＤにＭビットを同時にをストライピング及び書き込み、
    （ｃ）最大２個のＤＡＳＤの不可用性に応答し、消去を
    含むデータ配列をアクセスすることにより少なくとも（
    Ｍ−２）以上の使用可能ＤＡＳＤからのデータを再作成
    し、スケジュール的に或いは好機にステップ（ａ）及び
    （ｂ）を繰り返すことを特徴とする方法。
  3. 【請求項３】前記ＤＡＳＤ配列は所定の方法により割り
    当てられたスペア容量を有し、更に前記再作成ステップ
    は前記使用不能ＤＡＳＤの代用に前記スペアＤＡＳＤ配
    列容量を使用して、前記再作成されるデータをストライ
    ピング及び書き込むことを特徴とする請求項２記載の方
    法。
  4. 【請求項４】前記スペアＤＡＳＤ容量はスペアとして確
    保されるＤＡＳＤの形態を取ることを特徴とする請求項
    ３記載の方法。
  5. 【請求項５】前記データ配列は２次元分布に沿って生成
    され、該分布は複数ＤＡＳＤ或いは第１次元がＭ個のＤ
    ＡＳＤにより形成され、第２次元が各Ｍ個のＤＡＳＤの
    少なくとも１トラック上の（Ｍ−１）ビットの記録範囲
    から形成されることを特徴とする請求項３記載の方法。
  6. 【請求項６】Ｍ個のＤＡＳＤ配列内の最大２個の使用不
    能ＤＡＳＤのデータ内容のエンコーディング及び再作成
    方法であって、（ａ）ブロック・エンコーディングし、
    Ｍが素数である前記Ｍ個のＤＡＳＤ配列上の対のロケー
    ションに（Ｍ−１）＊Ｍデータ配列の元のデータ要素を
    書き込み、前記エンコーディングは前記データ配列をト
    ポロギ的円柱としてカバーし、交互する対角線及び行に
    おいて実行され、各エンコーディング作用は第１及び第
    ２の単純パリティ（ＸＯＲ）結果を生じ、前記第１及び
    第２のパリティはＭ個のＤＡＳＤ配列のそれぞれ第１及
    び第２の故障独立型ＤＡＳＤ上に記憶され、（ｂ）少な
    くとも２個以下の不可用性に応答して前記使用不能ＤＡ
    ＳＤからのデータを再作成し、該再作成はＭ−１或いは
    Ｍ−２個の他の使用可能ＤＡＳＤから参照される配列要
    素の単純パリティ・コーディングにより行われ、トポロ
    ギ的円柱として前記データ配列をカバーするエンコーデ
    ィング及び書き込み処理によりスケジュール的或いは好
    機にスペアＤＡＳＤ配列容量上に再作成ことを特徴とす
    る方法。
  7. 【請求項７】Ｍが素数でない場合は、前記データ配列が
    一律な２進値を有する追加の列を含むように拡張され、
    Ｍ´が素数である配列（Ｍ´−１）＊Ｍ´を生成し、ス
    テップ（ａ）及び（ｂ）を実行することを特徴とする請
    求項６記載の方法。
  8. 【請求項８】Ｍ個のＤＡＳＤ配列内の最大２個の使用不
    能ＤＡＳＤの内容をコーディング及び再作成するための
    コンピュータによる実施方法であって、前記ＤＡＳＤ配
    列はコントローラを介して計算システムに接続され、（
    ａ）ブロック・エンコーディングし、Ｍが素数である前
    記Ｍ個のＤＡＳＤ配列上に単純パリティ・エンコード化
    データの少なくとも１つの（Ｍ−１）＊Ｍデータ配列を
    交互の対角線及び行メジャー循環順序により書き込み、
    データ配列対角線に沿う各パリティ・エンコーディング
    はＭ−２個のデータ要素をインターセプトし、前記パリ
    ティ結果は前記Ｍ個のＤＡＳＤの第１のＤＡＳＤ上の第
    １の位置にセットされ、データ配列行に沿う各パリティ
    ・エンコーディングは前記第１のパリティ位置と交差し
    、Ｍ−１データ要素をインターセプトし、前記パリティ
    結果は前記Ｍ個のＤＡＳＤの第２のＤＡＳＤ上の前記行
    の第２のパリティ位置にセットされ、（ｂ）使用不能な
    ＤＡＳＤへのアクセスに応答して、前記使用不能ＤＡＳ
    Ｄからのデータを再作成し、該再作成はＭ−１或いはＭ
    −２個の他の使用可能ＤＡＳＤから参照される配列要素
    の単純パリティ・コーディングにより行われ、交互の対
    角線及び行メジャー循環順序により前記データ配列をカ
    バーするエンコーディング及び書き込み処理によりスケ
    ジュール的或いは好機にスペアＤＡＳＤ配列容量上に再
    作成することを特徴とする方法。
  9. 【請求項９】前記コンピュータはＭ個のＤＡＳＤ配列上
    に記憶される（Ｍ−１）＊Ｍデータ配列への少なくとも
    １回のスモール書き込みアクセスを実行し、前記第１及
    び第２のＤＡＳＤは単純パリティを記憶し、前記Ｍ−２
    個の他のＤＡＳＤはデータを記憶し、前記方法は更に少
    なくとも１個のデータ用ＤＡＳＤから旧データを読み出
    し、旧パリティを前記第１及び第２のＤＡＳＤから読み
    出し、新パリティ（ｘ、ｙ）´は旧データ、新データ、
    旧パリティ、旧隣接パリティ及び新隣接パリティの排他
    的論理和により決定され前記第１及び第２のＤＡＳＤ上
    に書き込まれることを特徴とする請求項８記載の方法。
  10. 【請求項１０】ＣＰＵ、少なくともＭ個のＤＡＳＤ及び
    スペアＤＡＳＤの配列、及び前記ＣＰＵと前記配列を相
    互接続し選択的にＤＡＳＤを同期アクセスする手段を有
    するシステムにおいて、前記手段はＭ個のＤＡＳＤ上に
    ストライプされるＭビットを同時に読み出し及び書き込
    むアクセスを含み、前記相互接続手段は更に、（ａ）前
    記配列のＭ個のＤＡＳＤ上に、繰り返し生成される対角
    線メジャー及び交差行メジャー順序のパターンに従って
    、単純パリティ・エンコーディングを含む（Ｍ−１）＊
    Ｍデータ・ビット配列をフォーマットする手段であって
    、前記順序はトポロギ的円柱を横断し、ここでＭは素数
    であり、（ｂ）最大２個のＤＡＳＤの不可用性に応答し
    、前記データ配列をアクセスすることにより少なくとも
    （Ｍ−２）以上の使用可能ＤＡＳＤからのデータを再作
    成し、スケジュール的に或いは好機に反対のスロープを
    有する配列対角線によりステップ（ａ）及び（ｂ）を繰
    り返すことを特徴とするシステム。
  11. 【請求項１１】前記配列は未割当のスペアＤＡＳＤを含
    み、更に前記相互接続手段は前記スペアＤＡＳＤを故障
    ＤＡＳＤに代用し、再作成されたデータを前記代用され
    るＤＡＳＤを含むＭ個のＤＡＳＤを横断して書き込むこ
    とを特徴とする請求項１０記載のシステム。
JP3320232A 1991-02-11 1991-12-04 デ―タの修復方法およびシステム Expired - Lifetime JP2514289B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US653596 1991-02-11
US07/653,596 US5271012A (en) 1991-02-11 1991-02-11 Method and means for encoding and rebuilding data contents of up to two unavailable DASDs in an array of DASDs

Publications (2)

Publication Number Publication Date
JPH04310137A true JPH04310137A (ja) 1992-11-02
JP2514289B2 JP2514289B2 (ja) 1996-07-10

Family

ID=24621534

Family Applications (1)

Application Number Title Priority Date Filing Date
JP3320232A Expired - Lifetime JP2514289B2 (ja) 1991-02-11 1991-12-04 デ―タの修復方法およびシステム

Country Status (3)

Country Link
US (1) US5271012A (ja)
EP (1) EP0499365A3 (ja)
JP (1) JP2514289B2 (ja)

Families Citing this family (102)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5579475A (en) * 1991-02-11 1996-11-26 International Business Machines Corporation Method and means for encoding and rebuilding the data contents of up to two unavailable DASDS in a DASD array using simple non-recursive diagonal and row parity
JP2923702B2 (ja) * 1991-04-01 1999-07-26 株式会社日立製作所 記憶装置及びそのデータ修復方法
JP2743606B2 (ja) * 1991-04-11 1998-04-22 三菱電機株式会社 アレイ型記録装置
US5301297A (en) * 1991-07-03 1994-04-05 Ibm Corp. (International Business Machines Corp.) Method and means for managing RAID 5 DASD arrays having RAID DASD arrays as logical devices thereof
US5826075A (en) * 1991-10-16 1998-10-20 International Business Machines Corporation Automated programmable fireware store for a personal computer system
US5341381A (en) * 1992-01-21 1994-08-23 Tandem Computers, Incorporated Redundant array parity caching system
US5469566A (en) * 1992-03-12 1995-11-21 Emc Corporation Flexible parity generation circuit for intermittently generating a parity for a plurality of data channels in a redundant array of storage units
US5331646A (en) * 1992-05-08 1994-07-19 Compaq Computer Corporation Error correcting code technique for improving reliablility of a disk array
JPH05341918A (ja) * 1992-05-12 1993-12-24 Internatl Business Mach Corp <Ibm> 二重化デイスク記憶装置システムを構成するための接続装置
WO1994003857A1 (en) * 1992-08-10 1994-02-17 Advanced Logic Research, Inc. Computer interface for concurrently performing plural seeks on plural disk drives
US5459853A (en) * 1992-11-23 1995-10-17 International Business Machines Corporation Efficient variable-block data storage system employing a staggered fixed-block-architecture array
DE69408498D1 (de) * 1993-06-30 1998-03-19 Ibm Kodierung und Rekonstruktion des Dateninhaltes von bis zu zwei nichtverfügbaren DASDs in einer DASD-Anordnung
US5564011A (en) * 1993-10-05 1996-10-08 International Business Machines Corporation System and method for maintaining file data access in case of dynamic critical sector failure
US5485571A (en) * 1993-12-23 1996-01-16 International Business Machines Corporation Method and apparatus for providing distributed sparing with uniform workload distribution in failures
US5644695A (en) * 1994-01-03 1997-07-01 International Business Machines Corporation Array combinatorial decoding with multiple error and erasure detection and location using cyclic equivalence testing
US5537567A (en) * 1994-03-14 1996-07-16 International Business Machines Corporation Parity block configuration in an array of storage devices
US5623595A (en) * 1994-09-26 1997-04-22 Oracle Corporation Method and apparatus for transparent, real time reconstruction of corrupted data in a redundant array data storage system
US5524204A (en) * 1994-11-03 1996-06-04 International Business Machines Corporation Method and apparatus for dynamically expanding a redundant array of disk drives
JPH08249133A (ja) * 1994-12-15 1996-09-27 Internatl Business Mach Corp <Ibm> ディスク・ドライブ・アレイの故障対策の方法及びシステム
US5699503A (en) * 1995-05-09 1997-12-16 Microsoft Corporation Method and system for providing fault tolerance to a continuous media server system
US6449730B2 (en) 1995-10-24 2002-09-10 Seachange Technology, Inc. Loosely coupled mass storage computer cluster
US5862312A (en) * 1995-10-24 1999-01-19 Seachange Technology, Inc. Loosely coupled mass storage computer cluster
US5941994A (en) * 1995-12-22 1999-08-24 Lsi Logic Corporation Technique for sharing hot spare drives among multiple subsystems
US6055577A (en) * 1996-05-06 2000-04-25 Oracle Corporation System for granting bandwidth for real time processes and assigning bandwidth for non-real time processes while being forced to periodically re-arbitrate for new assigned bandwidth
US5862313A (en) * 1996-05-20 1999-01-19 Cray Research, Inc. Raid system using I/O buffer segment to temporary store striped and parity data and connecting all disk drives via a single time multiplexed network
US5893100A (en) * 1996-11-27 1999-04-06 Teralogic, Incorporated System and method for tree ordered coding of sparse data sets
KR100267366B1 (en) * 1997-07-15 2000-10-16 Samsung Electronics Co Ltd Method for recoding parity and restoring data of failed disks in an external storage subsystem and apparatus therefor
CA2245603C (en) * 1997-08-14 2011-06-28 Stewart Crozier Method of enhanced max-log-a posteriori probability processing
US6138125A (en) * 1998-03-31 2000-10-24 Lsi Logic Corporation Block coding method and system for failure recovery in disk arrays
JP2000003255A (ja) * 1998-06-12 2000-01-07 Nec Corp ディスクアレイ装置
US6243827B1 (en) 1998-06-30 2001-06-05 Digi-Data Corporation Multiple-channel failure detection in raid systems
JP2000242440A (ja) * 1999-02-25 2000-09-08 Alps Electric Co Ltd ディスク装置
US6351838B1 (en) 1999-03-12 2002-02-26 Aurora Communications, Inc Multidimensional parity protection system
US6493847B1 (en) * 1999-06-15 2002-12-10 Applied Micro Circuits Corporation Sonet B2 parity byte calculation method and apparatus
US6557123B1 (en) 1999-08-02 2003-04-29 Inostor Corporation Data redundancy methods and apparatus
US7389466B1 (en) * 1999-08-12 2008-06-17 Texas Instruments Incorporated ECC in computer system with associated mass storage device, and method for operating same
KR100388498B1 (ko) 2000-12-30 2003-06-25 한국전자통신연구원 복수 개의 레이드를 구비한 계층적 레이드 시스템
US7219353B2 (en) * 2001-02-27 2007-05-15 Broadcom Corporation Finite state machine with a single process context for a RAID system
US6851082B1 (en) 2001-11-13 2005-02-01 Network Appliance, Inc. Concentrated parity technique for handling double failures and enabling storage of more than one parity block per stripe on a storage device of a storage array
US7055058B2 (en) * 2001-12-26 2006-05-30 Boon Storage Technologies, Inc. Self-healing log-structured RAID
US7640484B2 (en) * 2001-12-28 2009-12-29 Netapp, Inc. Triple parity technique for enabling efficient recovery from triple failures in a storage array
US7613984B2 (en) * 2001-12-28 2009-11-03 Netapp, Inc. System and method for symmetric triple parity for failing storage devices
US6993701B2 (en) * 2001-12-28 2006-01-31 Network Appliance, Inc. Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array
US7073115B2 (en) * 2001-12-28 2006-07-04 Network Appliance, Inc. Correcting multiple block data loss in a storage array using a combination of a single diagonal parity group and multiple row parity groups
US8402346B2 (en) 2001-12-28 2013-03-19 Netapp, Inc. N-way parity technique for enabling recovery from up to N storage device failures
US7080278B1 (en) * 2002-03-08 2006-07-18 Network Appliance, Inc. Technique for correcting multiple storage device failures in a storage array
US6898668B2 (en) * 2002-06-24 2005-05-24 Hewlett-Packard Development Company, L.P. System and method for reorganizing data in a raid storage system
EP1547252A4 (en) * 2002-07-29 2011-04-20 Robert Halford MULTIDIMENSIONAL DATA PROTECTION AND MIRRORING METHOD FOR MICROBIAL DATA
ATE349828T1 (de) * 2002-08-13 2007-01-15 Matsushita Electric Industrial Co Ltd Hybrides automatisches wiederholungsaufforderungsprotokoll
US6848022B2 (en) * 2002-10-02 2005-01-25 Adaptec, Inc. Disk array fault tolerant method and system using two-dimensional parity
US7424637B1 (en) 2003-03-21 2008-09-09 Networks Appliance, Inc. Technique for managing addition of disks to a volume of a storage system
US7664913B2 (en) * 2003-03-21 2010-02-16 Netapp, Inc. Query-based spares management technique
US7216195B1 (en) * 2003-03-29 2007-05-08 Emc Corporation Architecture for managing disk drives
US7350126B2 (en) * 2003-06-23 2008-03-25 International Business Machines Corporation Method for constructing erasure correcting codes whose implementation requires only exclusive ORs
DE10350590A1 (de) * 2003-10-30 2005-06-16 Ruprecht-Karls-Universität Heidelberg Verfahren und Vorrichtung zum Sichern von Daten bei mehreren unabhängigen Schreib-Lese-Speichern
US7428691B2 (en) * 2003-11-12 2008-09-23 Norman Ken Ouchi Data recovery from multiple failed data blocks and storage units
US7263629B2 (en) * 2003-11-24 2007-08-28 Network Appliance, Inc. Uniform and symmetric double failure correcting technique for protecting against two disk failures in a disk array
US7647451B1 (en) 2003-11-24 2010-01-12 Netapp, Inc. Data placement technique for striping data containers across volumes of a storage system cluster
TWI310497B (en) * 2004-02-06 2009-06-01 Hon Hai Prec Ind Co Ltd System and method for disk fault tolerance
US20050228745A1 (en) * 2004-04-09 2005-10-13 Cmarket, Inc. Method and apparatus for conducting on-line auction events in coordination with incentive promotion for bidders
TWI543120B (zh) * 2004-05-07 2016-07-21 內數位科技公司 分派混合自動重複請求過程之方法及裝置
US7467281B2 (en) * 2004-06-10 2008-12-16 Intel Corporation Mapping data blocks to storage blocks to wrap around storage devices
US7318190B2 (en) * 2004-06-10 2008-01-08 Intel Corporation Storage device parity computation
TWI307836B (en) * 2004-07-02 2009-03-21 Hon Hai Prec Ind Co Ltd System and method for a plurality of disks fault tolerance efficienctly
US7330998B2 (en) * 2004-09-20 2008-02-12 Intel Corporation Data integrity verification
US7249307B2 (en) * 2004-10-21 2007-07-24 Nokia Corporation Flexible rate and punctured zigzag codes
US7945729B2 (en) * 2004-11-24 2011-05-17 International Business Machines Corporation System and method for tolerating multiple storage device failures in a storage system using horizontal and vertical parity layouts
US7343546B2 (en) * 2004-12-23 2008-03-11 Intel Corporation Method and system for syndrome generation and data recovery
JP4457019B2 (ja) * 2005-01-05 2010-04-28 富士通株式会社 情報処理システム及び一次ストレージ装置
US7380088B2 (en) * 2005-02-04 2008-05-27 Dot Hill Systems Corp. Storage device method and apparatus
EP1849237A2 (en) * 2005-02-09 2007-10-31 Nokia Siemens Networks Oy Low complexity hybrid arq scheme based on rate compatible zigzag codes
JP4754852B2 (ja) * 2005-03-15 2011-08-24 富士通株式会社 ストレージ制御装置および方法
US7568122B2 (en) * 2005-03-16 2009-07-28 Dot Hill Systems Corporation Method and apparatus for identifying a faulty component on a multiple component field replaceable unit
US7401253B2 (en) * 2005-05-09 2008-07-15 International Business Machines Corporation Convolution-encoded data storage on a redundant array of independent devices
US8560503B1 (en) 2006-01-26 2013-10-15 Netapp, Inc. Content addressable storage system
US7822921B2 (en) 2006-10-31 2010-10-26 Netapp, Inc. System and method for optimizing write operations in storage systems
US7613947B1 (en) 2006-11-30 2009-11-03 Netapp, Inc. System and method for storage takeover
US7647526B1 (en) 2006-12-06 2010-01-12 Netapp, Inc. Reducing reconstruct input/output operations in storage systems
WO2008103622A1 (en) * 2007-02-21 2008-08-28 Smithkline Beecham Corporation Continuous coating of pellets
US8370715B2 (en) * 2007-04-12 2013-02-05 International Business Machines Corporation Error checking addressable blocks in storage
US8209587B1 (en) 2007-04-12 2012-06-26 Netapp, Inc. System and method for eliminating zeroing of disk drives in RAID arrays
US7945836B2 (en) * 2007-06-20 2011-05-17 Motorola Solutions, Inc. Method and apparatus for reducing signaling overhead in a communication system using hybrid automatic repeat request
KR101597733B1 (ko) * 2007-07-30 2016-02-25 마벨 이스라엘 (엠.아이.에스.엘) 리미티드 무선 통신 시스템을 위한 레이트 매칭
US7975102B1 (en) 2007-08-06 2011-07-05 Netapp, Inc. Technique to avoid cascaded hot spotting
US7797605B2 (en) * 2007-08-28 2010-09-14 Beceem Communications Inc. Managing storage of HARQ packets
US7890795B1 (en) 2008-06-02 2011-02-15 Emc Corporation Auto-adapting cache memory system and memory
US8335966B1 (en) * 2008-08-01 2012-12-18 Dell Products L.P. Dual parity RAID wherein no more than N+1 data symbols contribute to any parity symbol
EP2178214A1 (en) 2008-10-16 2010-04-21 Thomson Licensing Method and apparatus for algebraic erasure decoding
EP2178215A1 (en) * 2008-10-16 2010-04-21 Thomson Licensing Method for error correction and error detection of modified array codes
US8495417B2 (en) * 2009-01-09 2013-07-23 Netapp, Inc. System and method for redundancy-protected aggregates
US9009575B2 (en) * 2009-07-30 2015-04-14 Cleversafe, Inc. Rebuilding a data revision in a dispersed storage network
CN101719086B (zh) * 2009-11-30 2012-10-03 成都市华为赛门铁克科技有限公司 磁盘阵列容错处理方法和装置及容错系统
US9305597B2 (en) * 2009-12-29 2016-04-05 Cleversafe, Inc. Accessing stored multi-media content based on a subscription priority level
US10360106B2 (en) * 2011-12-12 2019-07-23 International Business Machines Corporation Throttled real-time writes
US8990669B2 (en) * 2013-03-14 2015-03-24 The Aerospace Corporation Linear feedback shift register with single bit error detection
US20150261623A1 (en) * 2014-03-15 2015-09-17 Macronix International Co., Ltd. Method and device for recovering data
CN104809035B (zh) * 2015-05-05 2017-07-28 中国科学技术大学 一种能快速单盘修复的存储系统构建方法
US9983959B2 (en) * 2015-06-29 2018-05-29 Microsoft Technology Licensing, Llc Erasure coding of data within a group of storage units based on connection characteristics
US12468467B2 (en) 2015-10-31 2025-11-11 Netapp, Inc. Sequential write based durable file system
US10379742B2 (en) 2015-12-28 2019-08-13 Netapp, Inc. Storage zone set membership
US10514984B2 (en) * 2016-02-26 2019-12-24 Netapp, Inc. Risk based rebuild of data objects in an erasure coded storage system
US11385980B2 (en) 2017-11-13 2022-07-12 Weka.IO Ltd. Methods and systems for rapid failure recovery for a distributed storage system

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS5024819A (ja) * 1973-07-07 1975-03-17
JPS5488109A (en) * 1977-12-23 1979-07-13 Ibm Error corrector
JPH0281123A (ja) * 1988-09-19 1990-03-22 Hitachi Ltd 並列データ転送方法及び装置
JPH02291011A (ja) * 1989-04-28 1990-11-30 Fujitsu Ltd 記憶装置

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
BE757116A (fr) * 1969-10-29 1971-03-16 Honeywell Inc Procede et dispositif de codage de segments de codes de controle
US4092732A (en) * 1977-05-31 1978-05-30 International Business Machines Corporation System for recovering data stored in failed memory unit
US4205324A (en) * 1977-12-23 1980-05-27 International Business Machines Corporation Methods and means for simultaneously correcting several channels in error in a parallel multi channel data system using continuously modifiable syndromes and selective generation of internal channel pointers
US4796260A (en) * 1987-03-30 1989-01-03 Scs Telecom, Inc. Schilling-Manela forward error correction and detection code method and apparatus
US4993030A (en) * 1988-04-22 1991-02-12 Amdahl Corporation File system for a plurality of storage classes
US4914656A (en) * 1988-06-28 1990-04-03 Storage Technology Corporation Disk drive memory
US5022030A (en) * 1989-03-17 1991-06-04 Digital Equipment Corporation Skewed XOR data storage process
WO1991001524A1 (en) * 1989-07-19 1991-02-07 Cray Research, Inc. An error recovery method and apparatus for high performance disk drives
US5130992A (en) * 1990-04-16 1992-07-14 International Business Machines Corporaiton File-based redundant parity protection in a parallel computing system

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS5024819A (ja) * 1973-07-07 1975-03-17
JPS5488109A (en) * 1977-12-23 1979-07-13 Ibm Error corrector
JPH0281123A (ja) * 1988-09-19 1990-03-22 Hitachi Ltd 並列データ転送方法及び装置
JPH02291011A (ja) * 1989-04-28 1990-11-30 Fujitsu Ltd 記憶装置

Also Published As

Publication number Publication date
EP0499365A2 (en) 1992-08-19
EP0499365A3 (en) 1993-05-19
US5271012A (en) 1993-12-14
JP2514289B2 (ja) 1996-07-10

Similar Documents

Publication Publication Date Title
JP2514289B2 (ja) デ―タの修復方法およびシステム
US5351246A (en) Method and means for coding and rebuilding that data contents of unavailable DASDs or rebuilding the contents of DASDs in error in the presence of reduced number of unavailable DASDs in a DASD array
US5303244A (en) Fault tolerant disk drive matrix
US5579475A (en) Method and means for encoding and rebuilding the data contents of up to two unavailable DASDS in a DASD array using simple non-recursive diagonal and row parity
US6154854A (en) Logical partitioning of a redundant array storage system
US7315976B2 (en) Method for using CRC as metadata to protect against drive anomaly errors in a storage array
US5333143A (en) Method and means for b-adjacent coding and rebuilding data from up to two unavailable DASDS in a DASD array
US5504858A (en) Method and apparatus for preserving data integrity in a multiple disk raid organized storage system
US8839028B1 (en) Managing data availability in storage systems
US7409625B2 (en) Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array
US6532548B1 (en) System and method for handling temporary errors on a redundant array of independent tapes (RAIT)
US20050229023A1 (en) Dual redundant data storage format and method
US20040123032A1 (en) Method for storing integrity metadata in redundant data layouts
KR20060052772A (ko) 데이터 저장 서브시스템 및 데이터 갱신 방법
JPH04230512A (ja) Ｄａｓｄアレイのための更新記録方法及び装置
US20070180303A1 (en) Uniform and symmetric double failure correcting technique for protecting against two disk failures in a disk array
US7934120B2 (en) Storing data redundantly
US7743308B2 (en) Method and system for wire-speed parity generation and data rebuild in RAID systems
EP0632376B1 (en) Encoding and rebuilding the data content of up to two unavailable DASDs in a DASD array
US7007193B1 (en) Method and system for reconstructing data serially arranged on a magnetic tape track
JP3676793B2 (ja) ディスクアレイ装置
US12468601B1 (en) Load balancing for erasure coding with multiple parities
US9471429B2 (en) Scalable protection scheme for protecting destaged data units
CN104881252A (zh) 一种基于e码的磁盘阵列布局结构
JPH0816327A (ja) ディスクアレイ装置