JPH0728710A - データ・コーディング再生方法 - Google Patents

データ・コーディング再生方法

Info

Publication number
JPH0728710A
JPH0728710A JP6143535A JP14353594A JPH0728710A JP H0728710 A JPH0728710 A JP H0728710A JP 6143535 A JP6143535 A JP 6143535A JP 14353594 A JP14353594 A JP 14353594A JP H0728710 A JPH0728710 A JP H0728710A
Authority
JP
Japan
Prior art keywords
dasd
diagonal
parity
dasds
array
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
JP6143535A
Other languages
English (en)
Other versions
JP2750316B2 (ja
Inventor
Miguel M Blaum
ミグエル・マリオ・ブラーム
James T Brady
ジェームス・トムソン・ブラディ
Jehoshua Bruck
ジェオシュア・ブルック
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 JPH0728710A publication Critical patent/JPH0728710A/ja
Application granted granted Critical
Publication of JP2750316B2 publication Critical patent/JP2750316B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • 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

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)

Abstract

(57)【要約】 【目的】 Ｍ個で構成されるＤＡＳＤの配列中の２つ以
下のＤＡＳＤにデータのエラー・消去等が発生したとき
に、容易にそのデータを復元することのできるＤＡＳＤ
システムを提供する。 【構成】 本発明の方法及び手段は、データ配列に対し
て個別に（Ｍ−１）*（Ｍ−２）のデータ・ブロックか
ら（Ｍ−１）* Ｍのブロック配列を、行優先順及び対角
線優先順に、非再帰的単純パリティ・コーディングを用
いて生成することによる。Ｍは素数であり、対角線はト
ロイダル・トポロジで取られる。配列対角線それぞれの
パリティ値は、基準となる主対角線のそれと同じモード
（奇数または偶数）であり、各行のパリティ・モードは
偶数である。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、障害の影響を受けない
直接アクセス記憶装置（ＤＡＳＤ）の配列に関し、特
に、配列の最高２つまでのＤＡＳＤがその内容の消去等
によって同時に使用不能であっても該ＤＡＳＤ配列に格
納されたデータの可用性を維持することに関する。
【０００２】
【従来の技術】従来技術の場合、ＤＡＳＤ配列にデータ
・ブロックを分散させることで、配列に格納されたデー
タ・ブロックのアクセス、データ速度、フォールト・ト
レランス及び復元を改良することは充分に評価されてい
る。なかでも注目されるのは、ＤＡＳＤ単体の障害や消
去を補正するための単純パリティの使用（米国特許第４
０９２７３２号）や、最高２つ（米国特許出願第６５３
５９６号、同第７５１９５０号）または３つ（米国特許
出願第７１８７２４号）までの同時障害を補正するため
複雑な冗長コードの使用である。障害発生時にＤＡＳＤ
配列の動作を下位（degraded）モードからフォールト・
トレラント・モードに戻すために、いくつかのＤＡＳＤ
をホット・スペア（米国特許第４９１４６５６号）とし
て使用する方法が知られている。ホット・スペアは、切
替えによって故障したＤＡＳＤと交換でき、失われたデ
ータや消去されたデータを再生したものを格納するのに
使用できる。また、障害が予想され得るいくつかのＤＡ
ＳＤと同等な配列のＤＡＳＤ間にスペア・スペースを予
約すること（米国特許出願第７１４９６９号）で、配列
動作が下位モードで継続する場合でも可用性を維持す
る、または負荷の平衡を実現する（米国特許出願第５６
２１８８号）方法も知られている。
【０００３】Ouchiによる１９７８年５月３０日付米国
特許第４０９２７３２号"System forRecovering Data S
tored in a Failed Memory Unit"、は同じ論理ファイル
から障害の影響を受けないＮ−１個のＤＡＳＤへのデー
タ・ブロックの分散と、Ｎ番目のＤＡＳＤへのパリティ
・ブロックの記録について開示している。Ouchi による
と、パリティ・ブロックはＮ−１個の他のブロックの内
容とＸＯＲがとられる。アクセス不能な単体のＤＡＳＤ
からの内容は、パリティ・ブロックと残りのアクセス可
能なＮ−２個のＤＡＳＤ上に格納されたブロックのＸＯ
Ｒをとることで復元可能である。単一の障害が生じた場
合は、スペア・ディスクが再生されるまでに他の障害が
発生することでサブシステムが完全に使用不能になるの
で、動作は下位モードで行なわれる。この機能について
は後にHartnessによる１９８８年１０月４日付米国特許
第４７７５９７８号"Data Error Correction System"で
再び説明されている。
【０００４】Ouchi 型の配列の場合、ブロックを修正す
るには故障したＤＡＳＤを識別する必要がある。これは
ハミング・コードで可能であるが、このようなコードは
普通、ブロック・インタリーブされたＤＡＳＤ配列では
なくビットに用いられ、冗長性を実現する複数のＤＡＳ
Ｄは全体のかなりの部分を占める。このことは、Patter
sonらによる"A Case For Redundant Arrays Of Inexpen
sive Disks（RAID）"、Report No．UCB/CSD 87/391、１
９８７年１２月、Computer ScienceDivision、U．of Ca
lifornia、Berkelyに述べられている通りである。
【０００５】逆にブロック・インタリーブと簡単なパリ
ティ・コーディングでは、Ouchi が述べているように、
無限に近いパリティ・ドメインまたは横線幅が得られ、
冗長なＤＡＳＤを１つだけ関係させればよい。しかし、
故障したＤＡＳＤの識別は、しきい値ＥＣＣの再試行に
よる等、個別に実現しなければならない。ここでは、Du
nphyらによる１９９０年４月３日付米国特許第４９１４
６５６号"Disk DriveMemory"もあわせて参照されたい。
【０００６】ＤＡＳＤ障害からの最高速の回復は、完全
に複製またはミラーリングされ、第２記憶ドメインに格
納されたデータ・セットに電子的に切り替えることであ
る。明らかにこれは記憶コストを倍にしてしまう。ＤＡ
ＳＤ配列はOuchi及びDunphyが述べている通り、ある配
列における単一ＤＡＳＤ障害の可能性が高く、同時ＤＡ
ＳＤ障害のそれは低いことを前提にしている。また単一
障害が生じたシステムをフォールト・トレラント状態に
戻すためにはホット・スペアリングを用いる必要があ
る。
【０００７】ホット・スペアリングは、Dunphyが定義し
ている通り、ＤＡＳＤを予約しておき、スペアをドメイ
ンにそのドメイン内のＤＡＳＤが故障した後に代用し、
故障したブロックをスペア上に再生するものである。Ｄ
ＡＳＤ障害と、スペアへのデータの再生の完了とによっ
て決定されるインタバル内にネストされていない限り、
データが使用できない平均時間は非常に長くなるのであ
る。また、単体のＤＡＳＤの修正＋Ouchi及びDunphy の
いうスペアリングは、停止したＤＡＳＤすなわち冗長な
ＤＡＳＤの個数を最小に保つ。
【０００８】ホット・スペアリングに代わるものは、動
作が下位モードであっても可用性を維持するためか、ま
たは特に順次の書込み更新に関して負荷の平衡化を補助
するために、故障したＤＡＳＤのいくつかに等しいＤＡ
ＳＤ配列に、何らかのパターン化をもとにスペースを予
約することである。これについては、Mattson らによる
１９９１年６月１３日付米国特許出願第７１４９６９
号"Method and Meansfor Distributed Sparing in DASD
Arrays"、または同Mattsonらによる１９９０年８月３
日付米国特許出願第５６２１８８号"Method and Means
for ManagingDASD Array Accesses When Operating in
Degraded Mode"、を参照されたい。
【０００９】Blaumらによる１９９１年２月１１日付米
国特許出願第６５３５９６号"Methodand Means for Enc
oding and Rebuilding the Data Contents of Up to Tw
oUnavailable DASDs in an Array of DASDs "は、最高
２つのＤＡＳＤが故障した時、Ｍ（素数）個の同期ＤＡ
ＳＤ配列に（Ｍ−１）* Ｍのシンボル・データ配列をコ
ーディングし再生する方法を開示している。トポロジカ
ル・トーラスをカバーする対角線を主としたデータ配列
方向と交差行を主としたデータ配列方向にサンプル・パ
リティの対が再帰的にコーディングされる。２個以下の
ＤＡＳＤが使用できない時にデータを再生するには、コ
ーディング・ステップと似た排他的論理和演算しか関係
しない単純再帰動作が必要である。
【００１０】米国特許出願第６５３５９６号のコーディ
ングでは、決定性プロセスに従って、（Ｍ−１）* Ｍの
データ配列全体がカバーされるように、対角線パリティ
割当てと行パリティ割当てがジグザグに交互に繰返され
る。Ｍ回の対角線パリティ割当てそれぞれで、Ｍ−２個
のデータ要素のＸＯＲがとられ、その結果が第１パリテ
ィ位置に置かれる。この後、第１パリティ位置と交差す
る行のＭ−１個のデータ要素のＸＯＲがとられ、結果が
その行の第２パリティ位置に置かれる。
【００１１】Blaumらによる１９９１年８月２９日付米
国特許出願第７５１９５０号"Methodand Means For B-A
djacent Coding and Rebuilding Data From Up to TwoU
navailable DASDs in a DASD Array"は、Ｂ隣接コーデ
ィングを用い、ＤＡＳＤ配列のうち使用できない最高２
つまでのＤＡＳＤに格納されたデータ列の部分を訂正す
る方法とその手段を開示している。この方法は、（ａ）
故障したＤＡＳＤの個別識別と、（ｂ）残りのＤＡＳＤ
上の同じ文字列のブロックから得られた１対のシンドロ
ームの形成と解決、から成る。シンドローム対（Ｓ
（０）、Ｓ（１））は、２つの未知の式の中の独立した
２つのブール式から成る。
【００１２】上記文献で、各データ列はＮ個のデータ・
ブロック＋２つの冗長ブロックに分けられてから、Ｎ個
の対応するＤＡＳＤに書込まれる。冗長ブロック（Ｒ
（０）、Ｒ（１））がこの文字列について計算される。
最初の冗長ブロックＲ（０）は、Ｎ−２個のデータ・ブ
ロックのＸＯＲ、第２の冗長ブロックＲ（１）は、低濃
度（ａ５（Ｎ−ｉ））に累乗された有限フィールド（ガ
ロア・フィールド）のプリミティブ要素の積と、他のＮ
個のブロックのうち対応する１つのモジュロ２データ値
（ｂ（ｉ））のモジュロ２加算である。
【００１３】Blaumらによる１９９１年６月２１日付米
国特許出願第７１８７２４号"ErrorCorrection Codes F
or Multiple Failures In Disk Arrays And The Like"
は、先の米国特許出願第７５１９５０号のコードを拡張
したものである。ここでもパリティ・コーディングとＭ
の同期ＤＡＳＤ配列への（Ｍ−１）* （Ｍ−３）のデー
タ・ブロック配列の書込みが行なわれる。ＤＡＳＤのう
ち所定のものはパリティを格納するために予約される。
また最高３つまでのＤＡＳＤの非可用性に応答して、ス
ケジュール・ベースまたは機会ベースに使用可能なＭ−
３個のＤＡＳＤからのデータを使用してコーディングを
繰返すことによってデータを再生するステップと、再生
されたデータを再びスペア容量に書込むステップが含ま
れる。
【００１４】米国特許出願第７１８７２４号では、（Ｍ
−１）* Ｍ個のブロックの配列のコーディング（コード
化または再生）では、チェスのルーク、ビショップ及び
ナイトの正勾配の動きが、データ配列に対して周期的に
拡張されてエミュレートされる処理過程が、処理過程に
ついて論理的に組合わせた（ＸＯＲがとられた）値の和
がゼロになるようにたどられる。この方法では、比喩的
なナイトのコードの処理過程が、勾配が漸次に急峻にな
るよう変更されることによって４個以上のＤＡＳＤから
の回復にまで拡張できる。
【００１５】「パリティ・グループ」とは、先に挙げた
Dunphyの特許で用いられる通り、そこから取られたパリ
ティを格納するために用いられる少なくともＮ＋１番目
のＤＡＳＤを含むＮ個のＤＡＳＤの論理的関係を示す
が、データ・ブロックと、そこから取られたパリティま
たは代数コーディングされた他の冗長ブロックの論理的
関係をも言う。Patterson は、ＲＡＩＤ型５ＤＡＳＤ配
列については後者の定義を用いている。
【００１６】「データ・エラー」とは、ランダム・ノイ
ズやバースト・プロセスの結果としての格納された値の
変化をいう。１１１００１００等の２進値を格納するシ
ステムでは、残留磁化の状態が１がいくつか０になり、
０がいくつか１になるように変化する。これは１１００
０１０１のようになることである。ここで左から３番目
と８番目の位置がランダム・エラーである。
【００１７】「消去」とは、エラー位置が既知ではある
が、エラーの程度が未知であるエラーをいう。すなわ
ち、消去は記憶位置におけるデータ値の削除である。例
えば、データ列１ｘｘｘｘ１００は位置２乃至５で「消
去」が発生している。
【００１８】
【発明が解決しようとする課題】本発明の目的は、デー
タのエラー、消去及びＤＡＳＤ障害が発生した時にＤＡ
ＳＤ配列の可用性を高める方法及びその手段を提供する
ことである。
【００１９】本発明の他の目的は、たたみ込みコードの
場合のようにエラーを伝播させず、またリード−ソロモ
ン型コードのように代数的体に対して複雑な演算を実行
せずに、Ｍ個で構成されるＤＡＳＤの配列中から使用で
きない（例えば消去されている）最高２つまでのＤＡＳ
Ｄのデータ内容をコーディングし、再生する方法及びそ
の手段を提供することである。
【００２０】本発明の他の目的は、ハイレベルのＲＡＩ
Ｄ配列、特にＲＡＩＤ５型の配列で書込み動作を短縮す
ることのできる方法及び手段を提供することである。
【００２１】
【課題を解決するための手段】本発明の方法及び手段
は、データ配列に対して個別に（Ｍ−１）* （Ｍ−２）
のデータ・ブロックから（Ｍ−１）* Ｍのブロック配列
を、行優先順及び対角線優先順に、非再帰的単純パリテ
ィ・コーディングを用いて生成することによる。Ｍは素
数であり、対角線はトロイダル・トポロジで取られる。
配列対角線それぞれのパリティ値は、基準となる主対角
線のそれと同じモード（奇数または偶数）であり、各行
のパリティ・モードは偶数である。また対角線パリティ
値は、Ｍ−１番目の配列の列を、行パリティ値はＭ番目
の配列の列を形成する。配列の列は０乃至Ｍ−１と示さ
れる。単純パリティ・コーディングとは、対角線または
行の処理過程でデータ・ブロックのＸＯＲをとることを
意味する。
【００２２】少なくとも１つのＤＡＳＤが使用不能にな
った場合には、Ｍ−１またはＭ−２個の使用可能なＤＡ
ＳＤから参照された配列要素の単純パリティ・コーディ
ングによって、スケジュール・ベースまたは機会ベース
に上述のようにデータ・ブロック配列が再生され、先に
故障したＤＡＳＤにあったデータ・ブロック配列の部分
が、使用可能なＤＡＳＤに予約されたスペア・スペース
として、または故障したＤＡＳＤに代わるホット・スペ
アＤＡＳＤとしてのスペアのＤＡＳＤ配列容量に書込ま
れる。再生時、Ｍ−１番目のＤＡＳＤのパリティがＭ番
目のＤＡＳＤのパリティと等しくない場合には、基準対
角線のパリティ・モードが奇数として取られる。
【００２３】「非再帰的」（non-recursive） とは、行
または対角線のパリティの計算が、与えられた行または
対角線の処理過程のデータ・ブロックに対してのみ生
じ、他の行または対角線の処理過程のパリティ値は含ま
れない或いは考慮されない、という意味である。
【００２４】このような非再帰的パリティ・コーディン
グは、短い書込み操作には利点である。短い書込み操作
では、少なくとも１つのデータ・ブロックとそれに関連
するパリティが変更される。すなわちＲＡＩＤ５型のＤ
ＡＳＤ配列では、短い書込み操作で、変更対象のデータ
・ブロック及び対角線と行の両方のパリティ値だけがア
クセス、変更され、普通は再書込みされる。その場合、
更新トランザクション毎に読取り３回、書込み３回の操
作が必要である。つまり、古いデータ・ブロックと関連
する対角線及び行のパリティ値についてそれぞれ読取り
操作が１回、再計算された新しい値についてそれぞれ書
込み操作が１回である。新しい対角線パリティは、古い
対角線パリティ、古いデータ・ブロック及び新しいデー
タ・ブロックのＸＯＲであり、新しい行パリティは、古
い行パリティ、古いデータ・ブロック及び新しいデータ
・ブロックのＸＯＲである。
【００２５】ただし１つ注意すべきことがある。すなわ
ち更新されようとするデータ・ブロックが、「主要なま
たは基準としてのデータ・ブロック配列の対角線」にあ
る場合、先の方法には変更を加えなければならない。先
にも触れた通り、本発明のコーディング方法で１つの再
帰的結果は、主対角線または基準対角線のパリティ・モ
ード（偶数／奇数）を確認するステップである。このモ
ードは、残りの対角線についてパリティ値の割当てを制
御する。これを考慮するためには、短い書込みを伴う方
法は、配列内のＭ個の対角線パリティ値のそれぞれが読
取られ、再計算され、再び書込まれて、与えられた対角
線、古いデータ・ブロック及び新しいデータ・ブロック
について古いパリティ値のＸＯＲとして取られるように
変更される。古いデータ・ブロックと新しいデータ・ブ
ロックは、対角線パリティの再計算それぞれについて同
じである。また対角線パリティ値はこの場合、対応する
古いパリティ値の論理的補数として決定することができ
る。
【００２６】
【実施例】
【数１】 は以降ティルドＸと記載する。
【００２７】図１は、並行パス１１、１３、１５、１７
において高性能パリティ生成横線バッファ（ＰＳＢ）７
を結合する第１及び第２のＤＡＳＤパリティ・グループ
から成る配列を示す。ＣＰＵ１とＣＰＵ２から形成され
るプロセッサ配列はデータと制御のバス９に接続され
る。
【００２８】プロセッサ１または３によって発行される
読取りと書込みのコマンドにより、ＤＡＳＤのグループ
（グループ１または２）へのテーブル指向アクセス・パ
スが確立される。これは標準的なアクセス・プロトコル
と、バス９を介した共有メモリ５からＰＳＢ７へのデー
タ移動による。論理ファイルの論理的処理はＰＳＢ７で
実行される。ここで論理的処理は、横線（データのシリ
アル／並行変換）とパリティの生成及びチェックの両方
を含む。ＤＡＳＤとの間のパスはテーブル指向である。
基本的に読取りまたは書込みの引数で指定されたアドレ
スはＰＳＢ７によって、配列記憶アドレス・テーブルを
介して、ＰＳＢ７とＤＡＳＤの必須グループのＤＡＳＤ
上の位置の間の実際の物理パスに変換される。本発明の
目的上、グループ１を成すＤＡＳＤ等のグループはＭ個
のＤＡＳＤの配列とみなされる。「ホット・スペア」と
して追加されるＤＡＳＤも、ＭのＤＡＳＤ配列のうち最
高２つまでが故障した場合に配列へ追加するために使用
できる。これについては、Dunphyによる米国特許第４９
１４６５６号を参照されたい。
【００２９】ＰＳＢ７は、書込み更新コマンドを実行す
るには、最初にプロセッサから新しいデータ・ブロック
をバッファし、旧データ・ブロックを、また本発明の場
合には、ＭのＤＡＳＤ配列に格納された２つのパリティ
・ブロックを読取ってバッファしなければならない。新
しい対角線及び行のパリティは、旧データ、旧パリティ
及び新データを考慮して計算され、次に、新しいデータ
・ブロックと新しいパリティが対応するＤＡＳＤ配列に
記録される。
【００３０】読取り操作の場合、ＰＳＢ７はプロセッサ
からの読取りコマンドに応答して、書込みとは逆の操作
シーケンスを実行する。すなわち、読取るデータがその
中から抽出されるデータ配列がＰＳＢ７にバッファさ
れ、対応する行及び対角線のパリティがテストされて、
アドレスされたデータがバス９を通して共有メモリ５に
転送される。
【００３１】読取りでデータがアクセスされている時に
ＤＡＳＤ障害が発生した場合、ＰＳＢ７は選択肢の中か
ら１つを選択できる。これらには、（１）読取りコマン
ドの再試行、または、（２）本発明に従った、残りのＤ
ＡＳＤからのデータの再生と置換により、破壊されたデ
ータを素早く再生する操作が含まれる。
【００３２】読取りコマンドを発行するプロセッサ１ま
たは３については、１つの方法としては、読取りデータ
の移動完了後に障害発生をこれに通知することである。
これによりプロセッサが、Parkらによる方法により、各
パリティ・グループに排他的に予約されたプールから、
またはＤＡＳＤからのスペアＤＡＳＤの代用を制御する
ことができる。ＰＳＢ７は、DISABLE、RECONSTRUCT等の
プロセッサコマンドに応答して、スペアへのディレクト
リ・パスを、故障したＤＡＳＤのテーブル・ディレクト
リ・パスに代えるテーブルにより、故障したＤＡＳＤを
指定されたスペアＤＡＳＤと置換えることができる。次
に、故障したＤＡＳＤ上のデータを指定されたスペアＤ
ＡＳＤ上で再生できる。
【００３３】１実施例の場合、ＰＳＢ７は、ＤＡＳＤの
可用性のビット・マップ及びＤＡＳＤのアドレス・マッ
プを格納する。次に、可用性とアドレス・マップが各ア
クセス・コマンドの処理中に参照される。マップの変更
は、DISABLEとRECONSTRUCTのコマンドを使用するプロセ
ッサから行なえる。このような例では、スペアＤＡＳＤ
に永久アドレスが割当てられる。ここで重要なことは、
障害通知の後、プロセッサ１または３がＤＡＳＤのマッ
プをアドレスできることである。次に、可用性とアドレ
ス・マップが、各アクセス・コマンドの処理中に参照さ
れる。マップの変更はプロセッサによって、DISABLEとR
ECONSTRUCTのコマンドを使用して行なわれる。この実施
例は、永久アドレスをスペアＤＡＳＤに割当てるもので
ある。
【００３４】要点をまとめると、障害通知の後プロセッ
サは、（１）何もしないことにする、または、（２）ス
ペアＤＡＳＤのアドレスを、最高２つまでの故障したＤ
ＡＳＤのアドレスに代えるためのコマンドを生成し、且
つ、（３）後述の再生方法に従って、パリティとデータ
・ブロックを格納した残りのＤＡＳＤとのモジュロ２加
算により、最高２つまでの故障したＤＡＳＤの内容を割
当てられたスペア上に再生する。
【００３５】フォーマットされたスペアＤＡＳＤの、他
のＤＡＳＤとのオンラインでの動的代替が「ホット・ス
ペアリング」と呼ばれる。
【００３６】図２、図３、図４は、ＤＡＳＤの障害や消
去が発生した場合に短い書込み動作を実行することと応
答性とを目的とした、対角線及び行を主とした順序にお
ける（Ｍ−１）* Ｍのデータ・ブロック配列の非再帰的
単純パリティ・コーディング要素の制御の流れを示す。
すなわち、配列の形の論理配列に投射されたデータ・ブ
ロックは、所定の処理過程について、または配列の対角
線や行等のデータ・ブロックのサブセットについて計算
された冗長値を持ち得る。冗長値は次に、別のＤＡＳＤ
またはＤＡＳＤ配列上に予約されたスペースに格納され
る。最高２つまでの使用可能なＤＡＳＤに存在するデー
タの部分はパリティ値を使って再生し、スペアＤＡＳＤ
に、または残りのＭ−２のＤＡＳＤのスペア・スペース
に再び書込める。
【００３７】本発明で「コーディング」とは、データ・
ブロックの所定サブセットに対する冗長値の計算を意味
する。「再生」は、データ・ブロックのサブセットと冗
長値を用いた冗長性計算と同じプロセスによるデータ・
ブロックまたはパリティ・ブロックの計算を言う。「Ｘ
ＯＲ」は、２進フィールドに対する排他的論理和演算の
意味である。
【００３８】本発明の方法によれば、コーディングと短
い書込み操作における再帰をなくし、それらがデータの
単純パリティ・チェック、すなわち行と対角線のパリテ
ィ・チェックに置換えられる。変更されたデータ・ブロ
ックは、ほとんどの時間、２つの冗長（パリティ）値に
しか影響しないので、短い書込み動作は簡略化される。
【００３９】本発明ではＭ個のＤＡＳＤの配列を想定す
る。Ｍは素数である。データ・ブロックは（Ｍ−１）*
Ｍの論理配列に、ａ（ｉ、ｊ）が、ｊ番目のＤＡＳＤに
格納されたｉ番目のブロックになるように配置される。
ｉは閉じたインタバル［０、Ｍ−２］に、ｊは閉じたイ
ンタバル［０、Ｍ−１］に位置する。Ｍが素数であると
いう要件は実際には制限要因ではない。Ｍ未満のＤＡＳ
Ｄが必要な場合には、適切な数の（架空の）ＤＡＳＤが
０だけを格納すると仮定することによってコードを常に
短縮できるからである。
【００４０】データ・ブロックは最初のＭ−２個のＤＡ
ＳＤに、パリティ値はＭ−１番目とＭ番目のＤＡＳＤに
それぞれ格納される。またパリティ値は、Mattson らが
述べているようにＤＡＳＤ配列に分散させることもでき
る。
【００４１】パリティ値はブロックａ（Ｍ−１、ｊ）＝
０と想定している。ここで、ｊはインタバル［０、Ｍ−
１］にある。言い換えると、（架空の）全て０の行が想
定される。図２、図３、図４ではまた、全てのサブイン
デックスがモジュロＭとして扱われることを想定してい
る。
【００４２】次にコーディングについて説明する。短い
書込み操作と再生（デコーディング）の式は図２、図
３、図４に示す通りである。
【００４３】コーディングは図２で説明する。冗長性ａ
（ｔ、Ｍ−２）とａ（ｔ、Ｍ−１）の値はボックス２２
で与えられる。ここで、ｔはインタバル［０、Ｍ−２］
にある。特殊対角線（Ｍ−３、０）、（Ｍ−４、
１）、．．．、（０、Ｍ−３）のパリティの値Ｓは先に
ボックス２１で計算される。値Ｓは他の全ての対角線の
パリティを決定する（偶数または奇数）。手続き上、対
角線（Ｍ−３、０）、（Ｍ−４、１）、．．．、（０、
Ｍ−３）のパリティは、対角線を主とした順序で取られ
る残りの対角線のパリティを制御するモードとして用い
られる。この主対角線または基準対角線に沿ったデータ
・ブロックが偶数個の１である場合は、偶数パリティが
残りの対角線を制御する。行のパリティは常に偶数とし
て取られる。ここでは、２進値の例を示しているが、ブ
ロックのシンボルは任意のアルファベットにすることが
できる。
【００４４】ボックス２２で予測された値の書込み操作
はボックス２３で実行される。
【００４５】データ・ブロックａ（ｉ、ｊ）は、短い書
込み操作により、別の任意のデータ・ブロックｒに置換
えられる。ここで、ｉはインタバル［０、ｍ−２］に、
ｊはインタバル［０、ｍ−３］に位置する。この操作は
冗長ブロックに影響する。ほとんどの時間、冗長ブロッ
クは２つだけを変更すればよく、例外は、再び書込まれ
たデータ・ブロックａ（ｉ、ｊ）が基準対角線（Ｍ−
３、０）、（Ｍ−４、１）、．．．、（０、Ｍ−３）に
ある時である。その場合は、対角線パリティを全て変更
する必要がある。水平パリティは先の例のように変更さ
れる。これら２つの事例は再帰を伴わない。
【００４６】（Ｍ−１）×Ｍの配列はボックス３１でア
クセスされる。ボックス３２は、ａ（ｉ、ｊ）を置換え
る値の入力ｒを受取る。ボックス３３はａ（ｉ、ｊ）と
ｒのＸＯＲ演算を実行してバッファする。ボックス３４
で、実際に位置（ｉ、ｊ）にｒが書込まれ、ａ（ｉ、ｍ
−１）、ａ（ｉ、ｊ）及びｒのＸＯＲが位置（ｉ、ｍ−
１）で取られる。ボックス３５は、エントリ（ｉ、ｊ）
が基準対角線（Ｍ−３、０）、（Ｍ−４、
１）、．．．、（０、Ｍ−３）にあるかどうかチェック
される。存在しない場合はボックス３６で、ａ（ｉ＋ｊ
＋２、ｍ−２）、ａ（ｉ、ｊ）及びｒのＸＯＲがエント
リ（ｉ＋ｊ＋２、ｍ−２）に書込まれる。存在する場合
は、ボックス３７でインタバル［０、Ｍ−２］の各ｓに
ついて、ａ（ｓ、ｍ−２）、ａ（ｉ、ｊ）及びｒのＸＯ
Ｒがエントリ（ｓ、ｍ−２）に書込まれる。
【００４７】デコーディングのステップでは、最高２つ
までの使用不能なＤＡＳＤの内容を残りのＭ−２個のＤ
ＡＳＤから再生することができる。
【００４８】（Ｍ−１）×Ｍの配列はボックス４０１で
アクセスされる。ボックス４０２では、使用不能な２つ
のＤＡＳＤの入力ｉ、ｊが受信される。ここでｉ＜Ｊ、
ｉとｊはインタバル［０、Ｍ−１］に位置する。ボック
ス４０３は、ｊがＭ−１かどうか、すなわちＤＡＳＤが
水平冗長性を持つかどうかをチェックする。持つ場合、
コーディング操作と同様に対角線のパリティがボックス
４０５で予測される（奇数または偶数）。次に、失われ
たエントリａ（ｔ、ｉ）、ａ（ｔ、Ｍ−１）の値がボッ
クス４０６で予測される。ここで、ｔはインタバル
［０、Ｍ−２］にある。再生された値はスペア・ディス
クに書込まれ、使用不能なＤＡＳＤのｉとＭ−１が置換
えられる（ボックス４１２）。ｉ＝Ｍ−２の時には、図
２のコーディングの式が再び取得される。その意味でコ
ーディングはデコーディングの特別な場合である。
【００４９】ボックス４０３での答えがＮｏの場合は、
ボックス４０４でｊがＭ−２かどうか、すなわちＤＡＳ
Ｄが対角線冗長性を持つかどうかチェックされる。Ｙｅ
ｓの場合は、最初のステップでエントリａ（ｔ、ｉ）が
検索される。ここでｔはインタバル［０、Ｍ−２］にあ
る。これはボックス４０８において、水平パリティａ
（ｔ、Ｍ−１）を使用して行なわれる。エントリａ
（ｔ、ｉ）が復元されると、ボックス４０９で対角線パ
リティＳが予測される。次にボックス４１０で、対角線
パリティａ（ｔ、Ｍ−２）が取得される（ｔはインタバ
ル［０、Ｍ−２］）。再生された値はスペア・ディスク
に書込まれ、使用不能なＤＡＳＤのｉ、Ｍ−２がボック
ス４１２で置換えられる。
【００５０】ボックス４０４の答えがＮｏの場合、これ
は主要事例になる。すなわちデータ・ブロックを持つ２
つのＤＡＳＤ、ｉとｊは使用不能である。冗長なＤＡＳ
Ｄはいずれも影響を受けない。ボックス４０７で対角線
パリティが、冗長シンボルａ（ｔ、Ｍ−２）、ａ（ｔ、
Ｍ−１）全ての排他的論理和（ＸＯＲ）によって決定さ
れる。次にＤＡＳＤのｉ、ｊで失われたデータがボック
ス４１１で検索される。ボックス４１１での処理は再帰
である。インデックスｌは、１乃至Ｍ−１である。エン
トリはボックス４１１で指示される順序で検索される。
最初はｌ＝１、最後はｌ＝Ｍ−１である。従って、デコ
ーディングにおける再帰は必要であるが、ダブル・ディ
スク障害の発生時に限られ、これは極めて稀である。上
述のように、再生された値はスペアＤＡＳＤに書込ま
れ、使用不能なＤＡＳＤのｉ、ｊが置換えられる（ボッ
クス４１２）。
【００５１】以下ではコーディングの例をあげる。短い
書込み操作とデコーディングについては図２、図３、図
４で説明する。
【００５２】データ・ブロックはＭ＝５のＤＡＳＤの配
列に格納するのが望ましいとする。データとパリティ・
ブロックと値はａ（ｉ、ｊ）で示す。ここでｉはティル
ドＯ０、３ａに、ｊはティルドＯ０、４ａにある。基準
対角線（Ｍ−３、０）、（Ｍ−４、１）、．．．、
（０、Ｍ−３）に沿って取られたデータ・ブロックのパ
リティＳは、図２のボックス２１に従って次のように表
わされる。 S＝a（2、0）XOR a（1、1）XOR a（0、2）
【００５３】図２のボックス２２の式を用いると、Ｍ−
１番目のＤＡＳＤに格納されるＭ−２の対角線パリティ
値は次式に従って決定される。 a（0、3）＝a（3、0）XOR a（2、1）XOR a（1、2）XOR
S a（1、3）＝a（3、1）XOR a（2、2）XOR S a（2、3）＝a（0、0）XOR a（3、2）XOR S a（3、3）＝a（1、0）XOR a（0、1）XOR S
【００５４】Ｍ番目のＤＡＳＤに格納されるＭ−１の行
パリティ値は次のようにまとめられる。 a（i、4）＝a（i、0）XOR a（i、1）XOR a（i、2） ここで、ｉはティルドＯ０、３ａにある。
【００５５】パリティ・コード化される（Ｍ−１）*
（Ｍ−２）のデータ・ブロック・マトリックスを次のよ
うに仮定する（便宜上、データ・ブロックはどこでも長
さ１ビットになるように取る）。 1 0 1 0 1 1 1 1 0 0 1 0 ここで、上記式を用いて次を得る。 S＝a（2、0）XOR a（1、1）XOR a（0、2）＝1 XOR 1 XO
R 1＝1または奇数パリティ a（0、3）＝a（3、0）XOR a（2、1）XOR a（1、2）XOR
S＝0 XOR 1 XOR 1 XOR1＝1 a（1、3）＝a（3、1）XOR a（2、2）XOR S＝1 XOR 0 XO
R 1＝0 a（2、3）＝a（0、0）XOR a（3、2）XOR S＝1 XOR 0 XO
R 1＝0 a（3、3）＝a（1、0）XOR a（0、1）XOR S＝0 XOR 0 XO
R 1＝1 a（0、4）＝a（0、0）XOR a（0、1）XOR a（0、2）＝1
XOR 0 XOR 1＝0 a（1、4）＝a（1、0）XOR a（1、1）XOR a（1、2）＝0
XOR 1 XOR 1＝0 a（2、4）＝a（2、0）XOR a（2、1）XOR a（2、2）＝1
XOR 1 XOR 0＝0 a（3、4）＝a（3、0）XOR a（3、1）XOR a（3、2）＝0
XOR 1 XOR 0＝1
【００５６】最終的なコード化は次のようになる。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 対角線 水平 パリティ パリティ （奇数） （偶数） 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1
【００５７】以下は、本発明によって簡略化される短い
書込み操作である。Ｍ＝５とし、以下の（Ｍ−１）* Ｍ
のデータ・ブロック配列がＭ個のＤＡＳＤに格納される
とする。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1
【００５８】ａ（０、１）＝０を、ａ（０、１）＝１で
置換えるとする。エントリ（０、１）は、（２、０）、
（１、１）、（０、２）に沿った基準対角線上にないの
で、図３に従って、読取り３回と書込み３回だけで書込
み更新が可能になる。すなわち変更する必要があるの
は、データａ（０、１）、対角線パリティａ（３、３）
及び行パリティａ（０、４）だけである。従って、ａ
（０、１）＝１と変更すれば、ａ（３、３）＝１であ
り、奇数対角線パリティが維持され、ａ（０、４）＝１
であり、偶数行パリティが維持される。そこで新しい配
列は次のようになる。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1
【００５９】ここで、上記の配列に関しては、ａ（１、
１）＝０をセットすることが望ましい。これは主対角線
上にあるので、対角線パリティは全て、行パリティａ
（１、４）と共に変更しなければならない。これにより
次の新しい配列が得られる。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 対角線パリティは奇数から偶数に変わっている。
【００６０】ここで、再び図３の流れ図を参照し、短い
書込み操作について説明する。
【００６１】ＤＡＳＤの１つが故障した場合、これは与
えられた行が消去されたことと同じである。従ってｉ番
目の行またはＤＡＳＤが消去された場合、その内容は、
ＸＯＲによって、すなわち残りの行またはＤＡＳＤによ
って、Ouchi の特許と同じように再計算することができ
る。しかし、２つのＤＡＳＤ、ｉとｊが同時に故障し
た、または行が消去された場合、ｉ＜ｊ、ｉとｊがイン
タバル［０、Ｍ−１］にある時、図４の方法によって問
題を解決しなければならない。
【００６２】次の配列を考える。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 0 ? 0 1 ? 1 ? 0 0 ? 0 ? 1 0 ? 0 ? 0 0 ?
【００６３】シンボル"？"は、対応するエントリで情報
が失われたことを示す。この例の場合、ＤＡＳＤ１とＤ
ＡＳＤ４は使用不能、すなわちｉ＝１、ｊ＝Ｍ−１＝４
である。図４に従ってデコーディングを実現する際、ボ
ックス４０３はボックス４０５へ移る。そこで次のよう
に予測する。 S＝a（0、0）XOR a（3、2）XOR a（2、3）＝0 XOR 0 XO
R 0＝0または偶数パリティ
【００６４】次にボックス４０６で、ａ（ｔ、１）とａ
（ｔ、４）を次のように予測する。 a（0、1）＝a（1、0）XOR a（3、3）XOR S＝1 XOR 0 XO
R 0＝1 a（1、1）＝a（2、0）XOR a（0、2）XOR S＝0 XOR 0 XO
R 0＝0 a（2、1）＝a（3、0）XOR a（1、2）XOR a（0、3）XOR
S＝0 XOR 0 XOR 1 XOR0＝1 a（3、1）＝a（2、2）XOR a（1、3）XOR S＝1 XOR 0 XO
R 0＝1 a（0、4）＝a（0、0）XOR a（0、1）XOR a（0、2）＝0
XOR 1 XOR 0＝1 a（1、4）＝a（1、0）XOR a（1、1）XOR a（1、2）＝1
XOR 0 XOR 0＝1 a（2、4）＝a（2、0）XOR a（2、1）XOR a（2、2）＝0
XOR 1 XOR 1＝0 a（3、4）＝a（3、0）XOR a（3、1）XOR a（3、2）＝0
XOR 1 XOR 0＝1
【００６５】従って再生されたＤＡＳＤは次のようにな
る。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1
【００６６】同様に、ここでは以下の配列が受取られた
とする。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ ? 1 0 ? 1 ? 0 0 ? 1 ? 1 1 ? 0 ? 1 0 ? 1
【００６７】従って、ＤＡＳＤｉ＝０とｊ＝３は使用不
能である。ｊ＝Ｍ−２であるから、ボックス４０４はボ
ックス４０８に進み、そこでａ（ｔ、０）は次のように
予測される。 a（0、0）＝a（0、1）XOR a（0、2）XOR a（0、4）＝1
XOR 0 XOR 1＝0 a（1、0）＝a（1、1）XOR a（1、2）XOR a（1、4）＝0
XOR 0 XOR 1＝1 a（2、0）＝a（2、1）XOR a（2、2）XOR a（2、4）＝1
XOR 1 XOR 0＝0 a（3、0）＝a（3、1）XOR a（3、2）XOR a（3、4）＝1
XOR 0 XOR 1＝0
【００６８】次にボックス４０９に進み、対角線パリテ
ィが次のように予測される。 S＝a（2、0）XOR a（1、1）XOR a（0、2）＝0 XOR 0 XO
R 0＝0または偶数パリティ
【００６９】最後にボックス４１０で、ＤＡＳＤ３のシ
ンボルが次のように予測される。 a（0、3）＝a（3、0）XOR a（2、1）XOR a（1、2）XOR
S＝0 XOR 1 XOR 0 XOR0＝1 a（1、3）＝a（3、1）XOR a（2、2）XOR S＝1 XOR 1 XO
R 0＝0 a（2、3）＝a（0、0）XOR a（3、2）XOR S＝0 XOR 0 XO
R 0＝0 a（3、3）＝a（1、0）XOR a（0、1）XOR S＝1 XOR 1 XO
R 0＝0
【００７０】デコーディングの最終結果は次のようにな
る。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1
【００７１】ここで次の配列が受取られたとする。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ ? 1 ? 1 1 ? 0 ? 0 1 ? 0 ? 1 0 ? 1 ? 0 1
【００７２】従って、ＤＡＳＤｉ＝０、ｊ＝２は消去さ
れている。ｊ＝２＜３＝Ｍ−２であるから、ボックス４
０４はボックス４０７に進む。そこで対角線パリティが
次のように予測される。 S＝a（0、3）XOR a（0、4）XOR a（1、3）XOR a（1、
4）XOR a（2、3）XOR a（2、4）XOR a（3、3）XOR a
（3、4）＝1 XOR 1 XOR 0 XOR 1 XOR 1 XOR 0 XOR0 XOR
1＝1
【００７３】ここで、ボックス４１１における最後の再
帰が次のように求められる。 a（1、0）＝a（0、1）XOR a（3、3）XOR S＝1 XOR 0 XO
R 1＝0 a（1、2）＝a（1、0）XOR a（1、1）XOR a（1、4）＝0
XOR 0 XOR 1＝1 a（3、0）＝a（2、1）XOR a（1、2）XOR a（0、3）XOR
S＝0 XOR 1 XOR 1 XOR1＝1 a（3、2）＝a（3、0）XOR a（3、1）XOR a（3、4）＝1
XOR 1 XOR 1＝1 a（0、0）＝a（3、2）XOR a（2、3）XOR S＝1 XOR 1 XO
R 1＝1 a（0、2）＝a（0、0）XOR a（0、1）XOR a（0、4）＝1
XOR 1 XOR 1＝1 a（2、0）＝a（1、1）XOR a（0、2）XOR S＝0 XOR 1 XO
R 1＝0 a（2、2）＝a（2、0）XOR a（2、1）XOR a（2、4）＝0
XOR 0 XOR 0＝0
【００７４】最終的に再生された配列は次のようにな
る。 ＤＡＳＤ０ ＤＡＳＤ１ ＤＡＳＤ２ ＤＡＳＤ３ ＤＡＳＤ４ 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1
【００７５】
【発明の効果】本願発明によれば、複雑な演算の実行を
せずに、また、エラーを伝搬することなく故障したＤＡ
ＳＤを原状に復することができる。また、特にＭ個で構
成されるＤＡＳＤの配列中において２つまでのＤＡＳＤ
が故障したときに適用することができる。
【図面の簡単な説明】
【図１】横線、パリティ・コーディング、スペアリング
及びスペアに対するデータの再実行を示すハイレベルＲ
ＡＩＤ ＤＡＳＤ配列の図である。
【図２】（Ｍ−１）* （Ｍ−２）のデータ・ブロック配
列の非再帰的単純パリティ・コーディング要素について
対角線及び行を軸とした順序の制御の流れを示す図であ
る。
【図３】短い書込み動作を実行するために、（Ｍ−１）
* Ｍのデータ・ブロック配列の非再帰的単純パリティ・
コーディング要素について対角線及び行を軸とした順序
の制御の流れを示す図である。
【図４】最高２つまでのＤＡＳＤの障害が発生して再生
されたデータの制御の流れを示す図である。
【図５】最高２つまでのＤＡＳＤの障害が発生して再生
されたデータの制御の流れを示す図である。
【図６】最高２つまでのＤＡＳＤの障害が発生して再生
されたデータの制御の流れを示す図である。
【符号の説明】
１、３ プロセッサ ５ 共有メモリ ７ 高性能パリティ生成横線バッファ（ＰＳＢ） ９ バス １１、１３、１５、１７ 並行パス
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジェームス・トムソン・ブラディ アメリカ合衆国95120、カリフォルニア州 サン・ホセ、クイーンズブリッジ・コート 1060 (72)発明者 ジェオシュア・ブルック アメリカ合衆国94306、カリフォルニア州 パロ・アルト、ブライアント・ストリート 3278 (72)発明者 ジャイシャンカー・ムーセダス・メノン アメリカ合衆国95120、カリフォルニア州 サン・ホセ、ステアリング・ゲート・ドラ イブ 1095

Claims (10)

    【特許請求の範囲】
  1. 【請求項１】障害の影響を受けないＭ個のＤＡＳＤの配
    列と、上記ＤＡＳＤ配列のスペアとして動作可能な複数
    のＤＡＳＤのうち、または上記Ｍ個のＤＡＳＤに２つの
    ＤＡＳＤと同等のスペア・スペースが分散した配列のう
    ち、使用不能な最高２つまでのＤＡＳＤのデータ内容を
    コーディングし再生する方法であって、Ｍは素数であ
    り、上記データ内容が（Ｍ−１）*（Ｍ−２） のデータ
    ・ブロック配列として表現され、上記データ配列の各行
    のブロックが対応するＤＡＳＤに格納される上記方法
    は、 （ａ）（Ｍ−１）*（Ｍ−２） のデータ・ブロック配列
    の対角線と行の処理過程について、非再帰的単純パリテ
    ィ値を対角線及び行を主とした順序で計算することによ
    って（Ｍ−１）*（Ｍ−２） のデータ・ブロック配列か
    ら（Ｍ−１）*Ｍのデータ・ブロックを生成するステッ
    プであり、主対角線または基準対角線に沿ったデータ・
    ブロックのパリティ・モード（奇数または偶数）が、非
    基準対角線のそれぞれのパリティ値を計算するモードと
    して働き、各行のパリティ値が偶数モードに従って計算
    されるステップと、 （ｂ）上記（Ｍ−１）* Ｍのデータ配列の各行のブロッ
    クを上記障害の影響を受けないＭ個のＤＡＳＤのうち対
    応するＤＡＳＤに書込むステップと、 （ｃ）上記最高２つまでのＤＡＳＤが使用不能であるこ
    とに応答して、上記データ配列のうち消去された部分ま
    たは使用できない部分を、Ｍ−２個を超える使用可能な
    ＤＡＳＤから、スケジュール・ベースまたは機会ベース
    に再生し、対応するスペアＤＡＳＤまたは残りのＭ−２
    を超えるＤＡＳＤ上で使用可能なスペア・スペースのい
    ずれかに再生された部分を書込むステップと、 を含むデータ・コーディング再生方法。
  2. 【請求項２】複数のＤＡＳＤを有し、上記複数のＤＡＳ
    Ｄの１部が障害の影響を受けないＭ個のＤＡＳＤの配列
    を成し、該サブシステムが更に外部コマンドに応答し
    て、上記Ｍ個のＤＡＳＤからデータ・ブロックの（Ｍ−
    １）* （Ｍ−２）の配列に論理的にアドレスされたデー
    タ・ブロックのサブセットをアクセスするための手段を
    有しており、Ｍが素数であり、上記データ・ブロック配
    列が主対角線または基準対角線を有し、上記データ・ブ
    ロックが上記データ・ブロック配列に、対角線及び行を
    主とした順序に配置されており、上記データ・ブロック
    の対角線と行の順序がそれぞれパリティ・モード（奇数
    または偶数）を有する、システムにおいて、上記Ｍ個の
    ＤＡＳＤの配列のうち最高２つまでのＤＡＳＤが使用不
    能になった場合に上記配列の内容をコーディングし再生
    する方法であって、 （ａ）上記（Ｍ−１）*（Ｍ−２） のデータ・ブロック
    配列のデータ・ブロックの主対角線のパリティ・モード
    を突き止めるステップと、 （ｂ）ステップ（ａ）のモードに従って、対角線を主と
    した順序で上記データ・ブロックから単純パリティ値を
    計算してＭ−１番目の列を形成すると共に、偶数パリテ
    ィ・モードに従って行を主とした順序で上記データ・ブ
    ロックから単純パリティ値を計算してＭ番目の列を形成
    することによって、上記（Ｍ−１）* （Ｍ−２）のデー
    タ配列から（Ｍ−１）* Ｍのデータ・ブロック配列を生
    成するステップと、 （ｃ）ＤＡＳＤが使用できない場合に上記（Ｍ−１）*
    Ｍのデータ・ブロック配列を、上記ＭのＤＡＳＤ配列ま
    たは同等のスペースの対応する位置に書込むステップ
    と、 （ｄ）上記最高２つまでのＤＡＳＤが使用不能であるこ
    とに応答して、上記データ配列の消去された部分または
    使用できない部分を、使用可能なＭ−２を超えるＤＡＳ
    Ｄから、スケジュール・ベースまたは機会ベースに再生
    するステップと、 を含むコーディング再生方法。
  3. 【請求項３】上記アクセス手段が、所定の方法で上記Ｍ
    個のＤＡＳＤに割当てられたスペア容量を割当てるため
    の手段と、故障したＤＡＳＤに対してスペアＤＡＳＤを
    代用する手段とを含み、ステップ（ｄ）が、上記再生さ
    れた部分を、動作時にスペアと指定された上記複数のＤ
    ＡＳＤのうち対応するＤＡＳＤに、またはＭ−２を超え
    る残りのＤＡＳＤ上で使用可能なスペア・スペースに書
    込むステップを含む、請求項２記載の方法。
  4. 【請求項４】Ｍが素数ではない場合にはステップ
    （ｂ）、（ｃ）及び（ｄ）により、均一な２進値の列が
    追加されて、Ｍ'がＭよりも大きい素数を成す（Ｍ'−
    １）*Ｍ'の有効な配列を形成するよう拡張されたデータ
    ・ブロック配列をエミュレートする、請求項２記載の方
    法。
  5. 【請求項５】上記方法が、Ｍ個のＤＡＳＤの配列に格納
    された（Ｍ−１）* Ｍのデータ配列に対する上記アクセ
    ス手段を通して、少なくとも１つの短い書込みアクセス
    を実行し、第１及び第２のＤＡＳＤが単純パリティ値を
    格納し、他のＭ−２のＤＡＳＤがデータ・ブロックを格
    納する他、更に上記方法が、 （１）変更されるデータ・ブロックが上記データ・ブロ
    ック配列の主対角線上にあるかまたは基準対角線上にあ
    るかを突き止めるステップと、 （２）変更されるブロックが主対角線上にない場合に
    は、（ａ）旧データ・ブロックを上記ブロックを格納し
    たＤＡＳＤから読取り、旧対角線パリティ値と旧行パリ
    ティ値をそれぞれ第１及び第２の冗長なＤＡＳＤから読
    取るステップと、（ｄ）上記旧データ・ブロック、新デ
    ータ・ブロック及び旧対角線パリティ値のＸＯＲをとる
    ことによって、新しい対角線パリティ値を判定し、旧デ
    ータ・ブロック、新データ・ブロック及び旧行パリティ
    値のＸＯＲをとることによって新しい行パリティ値を判
    定するステップと、（ｃ）上記新データ・ブロック及び
    対角線と行の新パリティ値を、それぞれデータ・ブロッ
    クを格納したＤＡＳＤと第１及び第２の冗長なＤＡＳＤ
    に書込むステップと、 （３）変更されるブロックが主対角線上にある場合に
    は、（ａ）旧データ・ブロックを上記ブロックを格納し
    たＤＡＳＤから、旧行パリティ値を第２の冗長なＤＡＳ
    Ｄから、及びＭ個の対角線パリティ値を第１の冗長なＤ
    ＡＳＤから読取るステップと、（ｂ）Ｍ−１個の新対角
    線パリティ値のそれぞれを、対応する旧対角線パリティ
    値、旧データ・ブロック及び新データ・ブロックのＸＯ
    Ｒをとることによって判定し、新行パリティ値を、旧デ
    ータ・ブロック、新データ・ブロック及び旧行パリティ
    値のＸＯＲをとることによって判定するステップと、
    （ｃ）上記新データ・ブロック、新行パリティ値及びＭ
    個の新対角線パリティ値を、上記Ｍ個のＤＡＳＤのうち
    対応するＤＡＳＤに書込むステップと、を含む方法。
  6. 【請求項６】ステップ（３）（ｃ）が、上記データ・ブ
    ロックとパリティ値を上記対応するＤＡＳＤに書込むス
    テップを含む、請求項５記載の方法。
  7. 【請求項７】複数のＤＡＳＤを有し、ハイレベルのＲＡ
    ＩＤ構成における上記複数のＤＡＳＤのうち素数である
    Ｍ個のＤＡＳＤを動作可能にアクセスする手段を含み、
    該アクセス手段が外部コマンドに応答して、上記Ｍ個の
    ＤＡＳＤのうち選択されたＤＡＳＤに格納されたデータ
    ・ブロックの読取りと書込みを行ない、同期データ・ブ
    ロックが、（Ｍ−１）* （Ｍ−２）の論理配列に配置さ
    れており、上記配列の（Ｍ−１）の行のそれぞれの（Ｍ
    −２）のデータ・ブロックのそれぞれが、上記ＤＡＳＤ
    のうちＭ−２のＤＡＳＤの対応するＤＡＳＤに書込ま
    れ、上記複数のＤＡＳＤのいくつかがスペアと指定され
    ているシステムにおいて、 （ａ）上記論理配列の主対角線に分散したデータ・ブロ
    ックのパリティ・モードを突き止めるステップと、 （ｂ）（Ｍ−１）*Ｍの論理配列を、（Ｍ−１）*（Ｍ−
    ２）の論理配列から、パリティ値のＭ−１番目の列を、
    ステップ（ａ）のモードに従って、対角線を主とした順
    序で各対角線について単純パリティを計算して形成する
    と共に、パリティ値のＭ番目の列を、行を主とした順序
    で各列について単純パリティを計算して形成することに
    よって、生成するステップと、 （ｃ）生成された（Ｍ−１）* Ｍの論理配列を上記Ｍ個
    のＤＡＳＤに書込むステップと、 （ｄ）旧データ・ブロック、旧対角線パリティ値、及び
    旧行パリティ値を読取ることによって、上記論理配列の
    主対角線にはないデータ・ブロックを変更するために書
    込み更新コマンドに応答して、対角線と行の新しいパリ
    ティ値を計算し、変更されたデータ・ブロックと、対角
    線及び行の新しいパリティ値を、上記Ｍ個のＤＡＳＤに
    書込む他、主対角線に位置するデータ・ブロックを変更
    するために書込み更新コマンドに応答して、（Ｍ−１）
    の新しい対角線パリティ値と新しい行パリティ値の生成
    に関するステップ（ａ）及び（ｂ）を繰返し、変更され
    たデータ・ブロック、新対角線パリティ及び新行パリテ
    ィを上記Ｍ個のＤＡＳＤに書込むステップと、 （ｅ）最高２つまでのＤＡＳＤの非可用性に応答して、
    上記データ配列のうち消去された部分または使用できな
    い部分を、Ｍ−２を超える使用可能なＤＡＳＤから、ス
    ケジュール・ベースまたは機会ベースに再生し、再生さ
    れた部分を、スペアとして動作可能に指定された上記複
    数のＤＡＳＤのうち対応するＤＡＳＤに書込むステップ
    と、 を含む方法。
  8. 【請求項８】上記アクセス手段が、最高２つのＤＡＳＤ
    のスペアと同等のＭ−２のＤＡＳＤにスペア・スペース
    を予約するための手段を含み、ステップ（ｅ）が、上記
    再生された部分を、Ｍ−２の残りのＤＡＳＤを超えるＤ
    ＡＳＤ上で使用可能なスペア・スペースに書込むステッ
    プを含む、請求項７記載の方法。
  9. 【請求項９】主対角線上に位置するデータ・ブロックを
    変更するための書込み更新コマンドに応答して（Ｍ−
    １）の新対角線パリティ値を計算するステップが、対応
    する旧対角線パリティ値を論理的に補うステップを含
    む、請求項７記載の方法。
  10. 【請求項１０】（１）故障した２つのＤＡＳＤが、それ
    ぞれ対角線パリティ（Ｍ−１番目のＤＡＳＤ）と行パリ
    ティ（Ｍ番目のＤＡＳＤ）の値を格納したＤＡＳＤから
    成る場合には、ステップ（ｂ）を繰返し、再生された行
    とパリティの値を、それぞれ、Ｍ−１番目及びＭ番目の
    ＤＡＳＤの代用となるスペアＤＡＳＤに書込み、 （２）故障した２つのＤＡＳＤが、データ・ブロックを
    格納するＤＡＳＤ（ｉ番目のＤＡＳＤ）と、行パリティ
    値を格納するＤＡＳＤ（Ｍ番目のＤＡＳＤ）とから成る
    場合には、ｉ番目のＤＡＳＤを、主対角線のパリティ・
    モードを突き止めることによって再生し、ｉ番目のＤＡ
    ＳＤの各データ・ブロックを、突き止められたパリティ
    ・モードに従ってｉ番目のＤＡＳＤと交差する対角線に
    沿ったデータ・ブロックだけのＸＯＲをとることによっ
    て計算し、Ｍ番目のＤＡＳＤを、Ｍ番目のＤＡＳＤと交
    差する行に沿ったデータ・ブロックだけのＸＯＲをとっ
    て各行パリティ値を計算することによってＭ番目のＤＡ
    ＳＤを再生し、計算されたデータ・ブロックと行パリテ
    ィ値を、それぞれｉ番目及びＭ番目のＤＡＳＤの代用と
    なるスペアＤＡＳＤに書込み、 （３）故障した２つのＤＡＳＤが、データ・ブロックを
    格納するＤＡＳＤ（ｉ番目のＤＡＳＤ）と、対角線パリ
    ティ値を格納するＤＡＳＤ（Ｍ−１番目のＤＡＳＤ）と
    から成る場合には、ｉ番目のＤＡＳＤをｉ番目のＤＡＳ
    Ｄと交差する残りのデータ・ブロックそれぞれと行パリ
    ティ値のＸＯＲをとってｉ番目のＤＡＳＤの各データ・
    ブロックを計算することによって再生し、Ｍ−１番目の
    ＤＡＳＤを主対角線のパリティ・モードを突き止めるこ
    とによって再生し、Ｍ−１番目のＤＡＳＤと交差する対
    角線に沿ったデータ・ブロックのＸＯＲをとって、上記
    主対角線のパリティ・モードと共に各対角線パリティ値
    を計算し、検索されたデータ・ブロックと対角線パリテ
    ィ値を、それぞれｉ番目のＤＡＳＤとＭ−１番目のＤＡ
    ＳＤに代わるスペアＤＡＳＤに書込み、 （４）故障した２つのＤＡＳＤが、データ・ブロックを
    格納する１対のＤＡＳＤ（ｉ番目及びｊ番目のＤＡＳ
    Ｄ）から成る場合には、対角線パリティ値のＸＯＲが行
    パリティ値のＸＯＲと等しくなければ奇数として、他の
    場合には偶数として、主配列対角線のパリティ・モード
    を突き止め、ｉ番目またはｊ番目のＤＡＳＤの各データ
    ・ブロック値を、データ・ブロックの対角線と、計算さ
    れた上記各データ・ブロックと交差する対角線パリティ
    値とによって、またはデータ・ブロックの行と、計算さ
    れた上記各データ・ブロックと交差する行パリティ値と
    によって成る１つの未知の値を持つ単一式のＸＯＲ解と
    して突き止める、 ようにステップ（ｅ）が変更される、請求項７記載の方
    法。
JP6143535A 1993-06-30 1994-06-24 データのコーディング及び再生方法 Expired - Lifetime JP2750316B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US8570793A 1993-06-30 1993-06-30
US085707 1993-06-30

Publications (2)

Publication Number Publication Date
JPH0728710A true JPH0728710A (ja) 1995-01-31
JP2750316B2 JP2750316B2 (ja) 1998-05-13

Family

ID=22193429

Family Applications (1)

Application Number Title Priority Date Filing Date
JP6143535A Expired - Lifetime JP2750316B2 (ja) 1993-06-30 1994-06-24 データのコーディング及び再生方法

Country Status (3)

Country Link
EP (1) EP0632376B1 (ja)
JP (1) JP2750316B2 (ja)
DE (1) DE69408498D1 (ja)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100472079B1 (ko) * 2001-05-24 2005-02-21 에스케이케미칼주식회사 불소수지의 제조방법
JP2008197886A (ja) * 2007-02-13 2008-08-28 Nec Corp ストレージ装置及びその制御方法
US7571291B2 (en) 2005-01-05 2009-08-04 Fujitsu Limited Information processing system, primary storage device, and computer readable recording medium recorded thereon logical volume restoring program
US7809979B2 (en) 2005-03-15 2010-10-05 Fujitsu Limited Storage control apparatus and method
US8386837B2 (en) 2007-10-31 2013-02-26 Fujistu Limited Storage control device, storage control method and storage control program
JP2014511158A (ja) * 2011-02-28 2014-05-12 インターナショナル・ビジネス・マシーンズ・コーポレーション ストレージ・アレイにデータを保管するための方法、システム、およびコンピュータ・プログラム、ならびにストレージ・アレイ内の消去を訂正するための方法およびコンピュータ・プログラム

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6247157B1 (en) * 1998-05-13 2001-06-12 Intel Corporation Method of encoding data signals for storage

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5271012A (en) * 1991-02-11 1993-12-14 International Business Machines Corporation Method and means for encoding and rebuilding data contents of up to two unavailable DASDs in an array of DASDs
US5258984A (en) * 1991-06-13 1993-11-02 International Business Machines Corporation Method and means for distributed sparing in DASD arrays
EP0519669A3 (en) * 1991-06-21 1994-07-06 Ibm Encoding and rebuilding data for a dasd array

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100472079B1 (ko) * 2001-05-24 2005-02-21 에스케이케미칼주식회사 불소수지의 제조방법
US7571291B2 (en) 2005-01-05 2009-08-04 Fujitsu Limited Information processing system, primary storage device, and computer readable recording medium recorded thereon logical volume restoring program
US7809979B2 (en) 2005-03-15 2010-10-05 Fujitsu Limited Storage control apparatus and method
JP2008197886A (ja) * 2007-02-13 2008-08-28 Nec Corp ストレージ装置及びその制御方法
US8386837B2 (en) 2007-10-31 2013-02-26 Fujistu Limited Storage control device, storage control method and storage control program
JP2014511158A (ja) * 2011-02-28 2014-05-12 インターナショナル・ビジネス・マシーンズ・コーポレーション ストレージ・アレイにデータを保管するための方法、システム、およびコンピュータ・プログラム、ならびにストレージ・アレイ内の消去を訂正するための方法およびコンピュータ・プログラム

Also Published As

Publication number Publication date
EP0632376A2 (en) 1995-01-04
DE69408498D1 (de) 1998-03-19
JP2750316B2 (ja) 1998-05-13
EP0632376A3 (en) 1995-03-01
EP0632376B1 (en) 1998-02-11

Similar Documents

Publication Publication Date Title
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
US5271012A (en) Method and means for encoding and rebuilding data contents of up to two unavailable DASDs in an array of DASDs
US5504858A (en) Method and apparatus for preserving data integrity in a multiple disk raid organized storage system
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
US5333143A (en) Method and means for b-adjacent coding and rebuilding data from up to two unavailable DASDS in a DASD array
US7281089B2 (en) System and method for reorganizing data in a raid storage system
US5303244A (en) Fault tolerant disk drive matrix
US5581690A (en) Method and apparatus for preventing the use of corrupt data in a multiple disk raid organized storage system
US7409625B2 (en) Row-diagonal parity technique for enabling efficient recovery from double failures in a storage array
CN102346694B (zh) 一种在存储系统中计算奇偶校验的方法
US7529970B2 (en) System and method for improving the performance of operations requiring parity reads in a storage array system
US5566316A (en) Method and apparatus for hierarchical management of data storage elements in an array storage device
US6269453B1 (en) Method for reorganizing the data on a RAID-4 or RAID-5 array in the absence of one disk
JP3177242B2 (ja) データ記憶装置における書込みオペレーション識別子の不揮発性メモリ記憶
JP3742494B2 (ja) 大容量記憶装置
JPH09305328A (ja) ディスクアレイ装置
US20070083710A1 (en) Semi-static distribution technique
JPH04230512A (ja) Ｄａｓｄアレイのための更新記録方法及び装置
JP2000207136A (ja) 複数ドライブ故障トレラントｒａｉｄアルゴリズム
JPH0731579B2 (ja) Ｄａｓｄアレイの階層を管理する方法および装置
JPH05143471A (ja) 記憶装置の冗長アレイ内の故障記憶装置のオンライン再構成方法
JPH06504863A (ja) コピーバックキャッシュを有する記憶装置アレイ
JP2750316B2 (ja) データのコーディング及び再生方法
JP2004164675A (ja) ディスクアレイ装置
JP2570614B2 (ja) デイスクアレイ装置