(57)【特許請求の範囲】
【請求項１】
コンピュータが実行する方法であって、
複数の符号化データオブジェクトを、記憶のために複数のディスクドライブを含むディスク記憶装置のプールにおいて割り当てるステップ
を含み、
複数の前記符号化データオブジェクトの少なくとも一部は、様々なエラー訂正アルゴリズムにより生成され、割り当ては、前記符号化データオブジェクトを生成するために用いられる前記様々なエラー訂正アルゴリズムに基づきドライブのあるグループに制限されず、
各ディスクドライブは、各々がパーティションとして定められる複数の論理記憶ユニットに分けられ、
論理記憶ユニットのグループ（ＬＳＵグループ）は、ディスクドライブのグループにわたるパーティションのグループを含み、前記ＬＳＵグループの複数の前記パーティションは、各々、同じサイズであり、前記ＬＳＵグループの複数の前記パーティションは、同じドライブ上には存在せず、
各符号化データオブジェクトの前記割り当ては、単一の割り当てビットマップを用いて実行され、前記単一の割り当てビットマップは、前記符号化データオブジェクトの記憶のために利用可能な位置を識別するよう、前記ＬＳＵグループにわたり、前記符号化データオブジェクトは、前記割り当てビットマップの連続したビットによって定まる１つの利用可能な位置に割り当てられるか、または、共通パーティション境界に沿って並ぶ２つの位置に少なくとも割り当てられて前記２つの位置の間の非連続割り当てのギャップを許容し、前記方法は、
前記割り当てビットマップを使用して、共通パーティション境界と並ぶ割り当てユニットを要求するステップ
を含む、方法。
【請求項２】
請求項１に記載の方法であって、
割り当てる前記ステップは、複数の前記符号化データオブジェクトを様々なデバイスに割り当てるステップを含む、
方法。
【請求項３】
請求項２に記載の方法であって、
割り当てる前記ステップは、様々なエラー訂正アルゴリズムによって符号化された複数の符号化データオブジェクトを割り当てるステップを含む、
方法。
【請求項４】
請求項１に記載の方法であって、
前記方法は、データを、様々なエラー訂正アルゴリズムによって符号化して複数の前記符号化データオブジェクトを生成するステップを含む、
方法。
【請求項５】
請求項４に記載の方法であって、
前記方法は、複数の前記符号化データオブジェクトのインデックスを維持するステップであって、前記インデックスは、各符号化データオブジェクトをそのそれぞれのエラー訂正アルゴリズムにマップする、ステップを含む、
方法。
【請求項６】
請求項１に記載の方法であって、
割り当てる前記ステップは、複数の符号化データオブジェクトを同じ論理記憶ユニットに割り当てるステップを含む、
方法。
【請求項７】
請求項１に記載の方法であって、
割り当てる前記ステップは、複数の符号化データオブジェクトを同じ論理記憶ユニットのグループに割り当てるステップを含む、
方法。
【請求項８】
請求項１に記載の方法であって、
符号化されるデータのオブジェクトサイズは固定である、
方法。
【請求項９】
請求項１に記載の方法であって、
符号化されるデータのオブジェクトサイズは可変である、
方法。
【請求項１０】
請求項１に記載の方法であって、
複数の前記符号化データオブジェクトは、様々なカテゴリのエラー訂正アルゴリズムによって符号化された、
方法。
【請求項１１】
請求項１または４に記載の方法であって、
複数の前記符号化データオブジェクトのインデックスを提供するステップであって、前記インデックスは、各符号化データオブジェクトをそのそれぞれのエラー訂正アルゴリズムにマップする、ステップ
を含む方法。
【請求項１２】
請求項１に記載の方法であって、各符号化データオブジェクトがそのそれぞれのエラー訂正アルゴリズムにマップされ、
割り当てる前記ステップは、割り当てビットマップを使用するステップであって、前記割り当てビットマップは、複数の割り当てビットを、前記それぞれのエラー訂正アルゴリズムのチャンクグループあたり割り当てる、ステップ
を含む、方法。
【請求項１３】
請求項１２に記載の方法であって、
前記割り当てビットマップは、論理アドレス空間にマップする、
方法。
【請求項１４】
請求項１３に記載の方法であって、
論理オブジェクト番号（ＬＯＮ）が、前記符号化データオブジェクトへのポインタを定める、
方法。
【請求項１５】
請求項１に記載の方法であって、
前記符号化データオブジェクトへのポインタが、インデックスレコードに記憶される、
方法。
【請求項１６】
請求項１５に記載の方法であって、
前記インデックスレコードは、前記符号化データオブジェクトへの複数のポインタを含む、
方法。
【請求項１７】
請求項１２に記載の方法であって、割り当てる前記ステップは、境界ビットマップを使用するステップを含み、前記境界ビットマップは、前記割り当てユニットに、前記符号化データオブジェクトの最初のチャンクの印を付ける、方法。
【請求項１８】
コンピュータに請求項１から１７の何れか一項に記載の方法のステップを実行させる命令が記憶されたコンピュータ可読記憶媒体。
【請求項１９】
請求項１から１７の何れか一項に記載の方法のステップを実行するように構成されたプログラマブル論理。
【請求項２０】
様々な入力データオブジェクトのために、複数の符号化データオブジェクトを生成するための様々なエラー訂正アルゴリズムを選択するように動作可能なエラー訂正アルゴリズム構成要素と、
複数の前記符号化データオブジェクトを、記憶のために複数のディスクドライブを含むディスク記憶装置のプールにおいて割り当てるためのディスク記憶割り当て構成要素であって、複数の前記符号化データオブジェクトの少なくとも一部は、様々なエラー訂正アルゴリズムにより生成され、前記符号化データオブジェクトを生成するために用いる前記様々なエラー訂正アルゴリズムに基づかずに、ドライブの同じまたは異なるグループに割り当てられる、ディスク記憶割り当て構成要素と
を備え、
各ディスクドライブは、各々がパーティションとして定められる複数の論理記憶ユニットに分けられ、
論理記憶ユニットのグループ（ＬＳＵグループ）は、ディスクドライブのグループにわたるパーティションのグループを含み、前記ＬＳＵグループの複数の前記パーティションは、各々、同じサイズであり、前記ＬＳＵグループの複数の前記パーティションは、同じドライブ上には存在せず、
前記割り当て構成要素は、単一の割り当てビットマップを用い、前記単一の割り当てビットマップは、前記符号化データオブジェクトの記憶のために利用可能な位置を識別するよう、前記ＬＳＵグループにわたり、前記符号化データオブジェクトは、前記割り当てビットマップの連続したビットによって定まる１つの利用可能な位置に割り当てられるか、または、共通パーティション境界に沿って並ぶ２つの位置に少なくとも割り当てられて前記２つの位置の間の非連続割り当てのギャップを許容し、前記ディスク記憶割り当て構成要素は、前記割り当てビットマップを使用して、共通パーティション境界と並ぶ割り当てユニットを要求する、
データ記憶システム。
【請求項２１】
請求項２０に記載の記憶システムであって、
複数の前記符号化データオブジェクトを記憶するためのディスク記憶装置の前記プールをさらに備える記憶システム。
【請求項２２】
請求項２０に記載の記憶システムであって、各符号化データオブジェクトがそのそれぞれのエラー訂正アルゴリズムにマップされ、
前記割り当てビットマップは、複数のビットを、前記それぞれのエラー訂正アルゴリズムのチャンクグループあたり割り当てる、
記憶システム。
【請求項２３】
請求項２０に記載の記憶システムであって、
各符号化データオブジェクトをそのそれぞれのエラー訂正アルゴリズムにマップする複数の前記符号化データオブジェクトのインデックス
を含む記憶システム。
【請求項２４】
コンピュータに請求項１から１７の何れか一項に記載の方法のステップを実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
[001]本発明は、コンピュータ記憶（ストレージ）システムと、複数の消去符号化アルゴリズムの使用を可能にするディスク記憶上でのデータの配置のための方法および装置とに関する。
【背景技術】
【０００２】
[002]ファイルシステム、オペレーティングシステムまたは他の記憶管理プログラムの重要な仕事は、ディスク記憶装置などの記憶媒体にデータを置くことである。どこにそのデータが書き込まれ（ディスク上に置かれ）、いつ、どのようにそれがアクセスされるかは、読取り／書込み性能に重要な影響を与え得る。
【０００３】
[003]もう１つの重要な仕事は、記憶媒体への物理的損害が発生した場合に損失からデータを保護することである（耐故障性）。ＲＡＩＤ、Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋ（独立ディスクの冗長アレイ）の頭文字語は、１つの（あるいは場合によっては複数の）ドライブ（複数可）が損害を受けた場合に、それらの失われたドライブのデータが回復可能であるように、複数の物理ドライブ間でデータを分け、複製する、様々なデータ記憶の仕組みのための包括的用語である。各仕組みは、以下の２つの主要目的の間で異なるバランスを提供する：データ信頼性の向上と、入力／出力（Ｉ／Ｏ）性能の向上。
【０００４】
[004]消去符号化は、複数のディスクドライブ（たとえば、ＲＡＩＤアレイの）に基づいて記憶システム内の故障したドライブの失われたデータの回復を可能にするエラー訂正アルゴリズムのコレクションである。消去符号化データを生成し、記憶に書き込むための一般的プロセスは、以下を含む：
１．データが、一連のブロックで到達する、
２．各ブロックが、サブブロックに分けられる、
３．消去符号化アルゴリズムが、サブブロックのグループに適用される、
４．その結果は、使用される（たとえば、パリティデータを含むために）特定のアルゴリズムによって判定されるものとしての多数のサブブロックである、
５．結果として生じたサブブロックが、使用されるその特定のアルゴリズムによって判定されるものとしての１つまたは複数のサブブロックのグループで、１デバイス（たとえば、ディスクドライブ）ごとに１グループで、記憶媒体に書き出される。
【０００５】
[005]その回復プロセス（すなわち、故障したディスクドライブで失われたデータの回復）は、次いで、以下のように続く：
１．その他の（故障していない）デバイスから残りのグループのサブブロックを読み取る、
２．その残りのサブブロックに回復アルゴリズムを適用して、失われたデータを生成する、
３．元の完全なデータブロックを戻す。
【０００６】
[006]前述のプロセスの説明は、一般的であり、多数の異なる消去符号化アルゴリズムに適用される。各符号化アルゴリズムは、以下に関するトレードオフの独自のセットを有する：
１．Ｉ／Ｏ性能、
２．ＣＰＵ利用率、
３．記憶効率、
４．許容されるドライブ故障の数。
【０００７】
[007]現在の業界基準によれば、データサイズ、消去符号化アルゴリズム、およびディスクドライブのアレイは、ドライブグループ化構成がデータおよびアルゴリズムについて確立された後は、消去符号化アルゴリズムが変更され得ないような、１つの総体全体として互いに結び付いている。そのようなシステムの設計において、選択は、必要とされる冗長性、記憶されるデータの量、およびデータブロックの細分性に基づいて行われる。これらのパラメータに基づいて、そして、アクセス時間および回復時間などの性能特性を平衡させて、構成アレイ（物理ディスクドライブの固定グループ）が選択される。このドライブグループ化が確立された後は、指定された消去符号化アルゴリズムのみが、それらのドライブでデータを記憶するために使用され得る。さらに、選択された消去符号化アルゴリズムによって指定される最小限より小さいサイズのデータの書込みは、単純に書込みではなくて、より多くの時間を要する読み出し／修正／書込みをそれが必要とするため、性能ヒット（低下）を引き起こす。
【０００８】
[008]したがって、ディスク記憶に消去符号化データを割り当てるためのより柔軟なシステムが必要である。柔軟性の増加は、Ｉ／Ｏ性能、ＣＰＵ利用率、記憶容量、耐故障性、および／または回復時間のうちの１つまたは複数を強化するために望ましいことになる。
【発明の概要】
【０００９】
[009]本発明の一実施形態によれば、割当てが固定グループのドライブに縛られないように、消去符号化データがドライブのプール内の複数のディスクドライブのうちのいずれかに記憶されることを可能にする割当てプロセスが、提供される。さらに、その符号化データは、やはり符号化データの記憶がそのデータを符号化するために使用される消去アルゴリズムに基づく単一グループのドライブに制限されない、複数の異なる消去符号化アルゴリズムのうちのいずれか１つによって生成され得る。さらに別の実施形態で、符号化データは、そのデータにアクセスするために必要とされるヘッドシークの数を減らすために、選択ドライブ上で「積み重ねる」（位置合わせする）ことができる。これらの改良の結果として、本システムは、先行技術でのように１つの特定のアルゴリズムおよび１つの特定のグループの記憶装置に縛られることなしに、複数の消去符号化アルゴリズムのうちのどの１つを所与の入力データブロックのために使用するかを動的に判定することができる。
【００１０】
[0010]本発明の一実施形態によれば、以下のコンピュータ実行可能アクションを備える記憶上でデータを見つけるためのコンピュータ実装された方法が、提供される：
ディスク記憶装置のプール内の同じまたは異なるデバイス上で記憶するために、同じまたは異なる消去符号によって符号化された複数の符号化データオブジェクトを割り当てるステップ、
複数の論理記憶ユニットで記憶されることになる各符号化されたオブジェクトについて、使用可能な割当てユニットの単一の要求として割当てビットマスクを使用してその複数の論理記憶ユニットでそれぞれの符号化されたオブジェクトを記憶するステップであって、その割当てビットマスクが複数の論理記憶ユニットにわたり、記憶される符号化されたオブジェクトのための開始パーティション境界と位置合わせされたギャップを含む、ステップ。
【００１１】
[0011]一実施形態で、その割り当てるステップは、符号化されたオブジェクトを異なるデバイス上で割り当てるステップを含む。
【００１２】
[0012]一実施形態で、その割り当てるステップは、異なる消去符号によって符号化された符号化オブジェクトを割り当てるステップを含む。
【００１３】
[0013]一実施形態で、その割り当てるステップは、同じローカル記憶ユニット上で複数の符号化オブジェクトを割り当てるステップを含む。
【００１４】
[0014]一実施形態で、その割り当てるステップは、同じ論理記憶ユニットグループ上で複数の符号化されたオブジェクトを割り当てるステップを含む。
【００１５】
[0015]一実施形態で、本方法は、その割当てビットマスクを使用して、論理記憶ユニット境界と位置合わせされた割当てユニットを要求するステップを含む。
【００１６】
[0016]一実施形態で、符号化されるデータのオブジェクトサイズは、固定である。
【００１７】
[0017]一実施形態で、符号化されるデータのオブジェクトサイズは、可変である。
【００１８】
[0018]一実施形態で、データオブジェクトは、異なるカテゴリの消去符号によって符号化される。
【００１９】
[0019]一実施形態で、本方法は、各符号化データオブジェクトをそのそれぞれの消去符号にマップする符号化データオブジェクトのインデックスを提供するステップを含む。
【００２０】
[0020]一実施形態で、その割り当てるステップは、使用可能な割当てユニットに印を付ける割当てビットマップを使用するステップを含む。
【００２１】
[0021]一実施形態で、その割当てビットマップは、論理アドレス空間にマップする。
【００２２】
[0022]一実施形態で、論理オブジェクト番号（ＬＯＮ）は、符号化されたオブジェクトへのポインタを定義する。
【００２３】
[0023]一実施形態で、符号化されたオブジェクトへのポインタは、インデックスレコードで記憶される。
【００２４】
[0024]一実施形態で、そのインデックスレコードは、符号化されたオブジェクトへの複数のポインタを含む。
【００２５】
[0025]一実施形態で、その割り当てるステップは、符号化されたオブジェクトの最初のチャンクの割当てユニットに印を付ける境界ビットマップを使用する。
【００２６】
[0026]本発明のもう１つの実施形態によれば、コンピュータにロードされるときに、前述の本方法のステップを実行する命令がそこに記憶された、コンピュータ可読媒体が提供される。
【００２７】
[0027]本発明のもう１つの実施形態によれば、前述の本方法のステップを実装するように構成されたプログラマブル論理が提供される。
【００２８】
[0028]本発明のもう１つの実施形態によれば、以下を備えるデータ記憶システムが提供される：
異なる入力データオブジェクトのために、符号化データオブジェクトを生成するための異なる消去符号化アルゴリズムを選択するように動作可能な消去符号化アルゴリズム選択構成要素と、
ディスク記憶装置のプール内の同じまたは異なるデバイス上の任意の使用可能な割当てユニットに異なるアルゴリズムによって符号化された符号化データオブジェクトを割り当てるためのディスク記憶割当て構成要素。
【００２９】
[0029]一実施形態で、本システムは、その符号化データを記憶するためのディスク記憶装置のプールを含む。
【００３０】
[0030]一実施形態で、そのディスク記憶割当て構成要素は、各符号化データオブジェクトについて、そのプール内の複数のデバイスに及ぶ論理記憶ユニットグループの１つまたは複数の論理記憶ユニットにわたる符号化されたオブジェクトを記憶するための使用可能な記憶ユニットを要求するために、割当てビットマスクを使用し、そのビットマスクは、そのプール内の少なくとも１つのデバイス上の複数の論理記憶ユニットでその符号化されたオブジェクトを記憶することを可能にするギャップを含む。
【００３１】
[0031]一実施形態で、本システムは、その符号化データオブジェクトのそれぞれの消去符号化アルゴリズムへのインデックスを含む。
【００３２】
[0032]本発明のもう１つの実施形態によれば、データ記憶を見つけるためのコンピューティング環境において、１つまたは複数の論理記憶ユニットにわたる符号化オブジェクトを記憶するための使用可能な割当てユニットを要求するための割当てビットマスクを備えるデータ構造が提供され、その符号化データオブジェクトは異なる消去符号で符号化され、その割当てビットマスクは複数のディスクドライブにわたる複数の論理記憶ユニットに及び、そして、そのビットマスクは、使用可能な割当てユニットが複数の論理記憶ユニットにわたって要求される、記憶される符号化オブジェクトの開始パーティション境界と位置合わせされたギャップを含む。
【図面の簡単な説明】
【００３３】
【図１】[0033]異なる消去符号化アルゴリズムを使った入力データオブジェクトの符号化と、ディスク記憶装置のプール内の記憶への符号化データのその後の割当てとを説明する、本発明の一実施形態の概略的高レベルシステムアーキテクチャを示す図である。
【図２】[0034]消去符号化アルゴリズムの選択およびディスク記憶装置のプール内のディスク記憶への符号化データの割当てのための本発明の一実施形態によるプロセスの流れ図である。
【図３Ａ】[0035]２オブ４の符号化アルゴリズムでデータオブジェクトを符号化する一例を示す図である。
【図３Ｂ】２オブ４の符号化アルゴリズムでデータオブジェクトを符号化する一例を示す図である。
【図３Ｃ】[0036]４オブ６の符号化アルゴリズムでデータオブジェクトを符号化するもう１つの例を示す図である。
【図３Ｄ】４オブ６の符号化アルゴリズムでデータオブジェクトを符号化するもう１つの例を示す図である。
【図３Ｅ】[0037]８オブ１０の符号化アルゴリズムでデータオブジェクトを符号化するさらなる一例を示す図である。
【図３Ｆ】８オブ１０の符号化アルゴリズムでデータオブジェクトを符号化するさらなる一例を示す図である。
【図４Ａ】[0038]各ドライブがパーティションに分けられたディスクドライブのプールと、そのプール内のドライブに広がる論理記憶ユニット（ＬＳＵ）グループとを示す図である。
【図４Ｂ】各ドライブがパーティションに分けられたディスクドライブのプールと、そのプール内のドライブに広がる論理記憶ユニット（ＬＳＵ）グループとを示す図である。
【図５】[0039]本発明の一実施形態による符号化データオブジェクトを割り当てるための割当てビットマスクの一例を示す図である。
【図６Ａ】[0040]本発明のもう１つの実施形態による符号化データオブジェクトを割り当てるための割当てビットマスクのもう１つの実施形態を示す図である。
【図６Ｂ】本発明のもう１つの実施形態による符号化データオブジェクトを割り当てるための割当てビットマスクのもう１つの実施形態を示す図である。
【図６Ｃ】本発明のもう１つの実施形態による符号化データオブジェクトを割り当てるための割当てビットマスクのもう１つの実施形態を示す図である。
【図７】[0041]データを処理および記憶するための一般的システム構成の一実施形態を示す図である。
【発明を実施するための形態】
【００３４】
[0042]本発明の様々な実施形態が、ここで、図面を参照して説明される。以下の記載では、説明を目的として、非常に多くの特定の詳細が、本発明の１つまたは複数の実装形態の完全な理解を提供するために記載される。しかし、本発明は、これらの特定の詳細なしに実施され得ることが、明らかであろう。他の例では、よく知られている構造およびデバイスが、本発明の説明を容易にするために、ブロック図の形式で示される。
【００３５】
[0043]本願では、「構成要素」および「システム」という用語は、コンピュータ関連実体、ハードウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、あるいは実行中のソフトウェアのいずれかを指すものである。たとえば、構成要素は、プロセッサで実行するプロセス、プロセッサ、オブジェクト、実行ファイル、実行ファイルのスレッド、プログラム、および／またはコンピュータでもよいが、これらに限定されない。例として、サーバで実行するアプリケーションとそのサーバの両方が、構成要素でもよい。１つまたは複数の構成要素が、実行ファイルのプロセスおよび／またはスレッド内にあってもよく、構成要素は、１つのコンピュータ上で局所化されてもおよび／または複数のコンピュータ間で分散されてもよい。
【００３６】
[0044]本発明はまた、本発明のプロセスの流れ図として説明され得る。説明の簡潔さを目的として、流れ図の形で示される１つまたは複数の方法論は一連のアクションとして記載されるが、いくつかのアクションは、本発明によれば、本明細書に図示および記載されるものとは異なる順番でおよび／または他のアクションと同時に生じ得るので、本発明はそのアクションの順番によって限定されないことを理解および認識されたい。たとえば、方法論は、別法として、状態図でなど、一連の相互に関連する状態または事象として表され得ることが、当業者には理解および認識されよう。さらに、示されたすべてのアクションが本発明による方法論を実装するために必要とされる訳ではない。
【００３７】
[0045]本明細書で開示される発明の様々な実施形態で、「データ」、「データ要素」または「データオブジェクト」という用語は、同義的に使用される。本明細書では、データは、不透明な一群のデータ、たとえば、コンピュータに入力する、そこで記憶もしくは処理する、または別のコンピュータに送信することができる任意の記号（通常は「０」および「１」で示される）の順番列、を意味する。本明細書では、データは、メタデータ、他のデータの記述、を含む。本明細書に記載の記憶システムに書き込まれるデータは、同サイズのデータオブジェクト、または可変サイズのデータオブジェクトでもよい。
【００３８】
[0046]本明細書で「記憶システム」という用語は、ディスク記憶にデータを格納するための任意のシステムまたはアプリケーション、たとえばファイルシステム、ブロック記憶装置、または他のシステム、でもよい。記憶システムは、識別子または名前を使用して記憶内の各データ要素を参照することができる。一例で、その名前は、そのデータ内容のハッシュ、好ましくはそのデータ内容の暗号ハッシュまたは衝突耐性のあるハッシュ、などのグローバル一意識別子（ＧＵＩＤ）である。各データ要素がユーザに記憶されたデータの再構成を許す記憶システム内の名前を有する限り、他の命名規則が可能である。一実施形態では、中央サーバが名前を生成する。データ名は、通常は、人間とは対照的に、プログラムによる使用を意図された固定長の２進列である。すべてのデータのインデックス（時には辞書またはカタログと称される）は、各データ要素にアクセスする（それを見つける）ために記憶システムによって必要とされ得る。インデックス内の各レコードは、データ要素の名前と、それの論理および／または物理的位置（アドレス）と、それぞれのデータ要素に関する他の情報とを含み得る。一実施形態で、各インデックス項目は、データオブジェクトが記憶されたディスク上の物理ブロックアドレスを指すポインタを含む。一実施形態で、固定のアルゴリズムが、データが記憶されたディスク上の物理的位置を見つけるために使用され得る。
【００３９】
Ａ．システムアーキテクチャ
[0047]図１は、本発明の一実施形態の高レベルシステムアーキテクチャ１００を示す。入力データオブジェクト１０２は、ディスク記憶装置プール１１２のディスク記憶装置ｄ１、ｄ２、ｄ３、ｄ４、ｄ５、ｄ６…上での配置のために記憶システム１０４によって受信される。システム１０４は、消去符号化アルゴリズム選択構成要素１０６およびディスク記憶割当て構成要素１０８を含む。各入力データオブジェクト（ＤＯ１、ＤＯ２、ＤＯ３…）について、構成要素１０６が、複数の消去符号化アルゴリズム（ＥＣＡ１、ＥＣＡ２、ＥＣＡ３…）のうちの１つを選択して、選択されたデータオブジェクトを符号化データチャンクグループ１１０（ＥＤ１、ＥＤ２、ＥＤ３…）に符号化する。構成要素１０８は、次いで、１デバイスごとに１チャンクグループで、そのようなデバイスのプール１１２内の複数のディスク記憶装置にこれらのチャンクグループを割り当て、そのデバイスへのチャンクグループの割当ては各データオブジェクトについて独立して行うことができ、その割当ては、デバイスプール１１２内のデバイスの隣接するまたは固定のセットに限定されない。たとえば、図１は、データオブジェクトＤＯ１の複数のチャンクグループＥＤ１がディスクｄ１、ｄ２、ｄ４、ｄ５…に割り当てられ、データオブジェクトＤＯ２の複数のチャンクグループＥＤ２がデバイスｄ２、ｄ６…に割り当てられ、ＤＯ３の複数のチャンクグループＥＤ３がデバイスｄ１、ｄ３、ｄ４…に割り当てられたことを示す。したがって、その３つの異なる符号化アルゴリズムについて、結果として生じる符号化データは、ディスクプール１１２内の同じまたは異なるサブグループのディスクで記憶することができる。
【００４０】
[0048]図２は、消去符号化アルゴリズムの選択およびディスク記憶装置のプール内のディスク記憶装置への符号化データの割当てのための本発明の一実施形態を説明するプロセスの流れ図である。２０２で、本プロセスは、入力データオブジェクト（ＤＯ）を受信することによって開始する。２０４で、本プロセスは、そのＤＯの符号化データを生成するために複数の異なる消去符号化アルゴリズム（ＥＣＡ１、ＥＣＡ２、ＥＣＡ３…）から１つを選択する。２０６で、その選択されたアルゴリズムは、符号化データＥＣＤＯを生成する。２０８で、本プロセスは、その符号化データＥＣＤＯをいくつかのチャンクグループに割り当て（選択されたＥＣアルゴリズムの要求に応じて）、デバイスのプール内のディスク記憶装置から対応する数のディスク記憶装置を選択する。２１０で、結果として生じるチャンクグループが、１デバイスにつき１チャンクグループで、選択されたディスク記憶装置に書き込まれる。ステップ２１２で、さらなる入力ＤＯがある場合、本プロセスはステップ２０２に戻る。そうでない場合、本プロセスは終了する。
【００４１】
[0049]本発明の様々な実施形態によれば、データを符号化するために選択される消去符号（ＥＣ）アルゴリズムは、異なる入力データオブジェクトで異なってもよい。たとえば、記憶システムは、システムの高い利用率が存在する、たとえば容量の８５％で稼働する、１日の忙しい時間帯に、より単純な消去符号アルゴリズムを選択する決定をして、そのデータを符号化するために必要とされるＣＰＵ時間を低減することができる。その代償は、ドライブ故障への耐性が低くなることである。しかし、ＣＰＵが忙しくないその日の遅くに、たとえば夜に、その記憶システムは、そのプールに記憶された符号化データから元データを検索し、異なるより複雑な消去符号を使用して元データを再計算し、次いで、この符号化データを記憶してデータ保護のレベルを上げることができる。
【００４２】
[0050]もう１つのシナリオで、どの消去符号を使用するかの決定は、受信されるデータのタイプに依存し得る。たとえば、より大きなデータオブジェクトは、多数の異なる消去符号化アルゴリズムを受け入れることができ、それらすべては記憶空間の効率的な利用と受入れ可能な数の計算周期とをもたらす。別法として、より小さなオブジェクトは、より少数のまたは異なるタイプの消去符号化アルゴリズムのみに適し得る。したがって、入力データに基づいて、記憶システムは、それぞれの入力データを符号化するためにどの消去符号アルゴリズムを使用するかを動的に決定することができる。
【００４３】
[0051]例として、図３Ａ〜３Ｆは、符号化データを生成するための異なる消去符号化アルゴリズムの使用を説明し、その符号化データは、次いで、ディスク記憶装置の共通のプールで記憶され得る。
【００４４】
[0052]この一連の例で、消去符号カテゴリは、「ａオブｂ（ａ  ｏｆ  ｂ）」のラベルを付され、「ｂ」は、１デバイスあたり１つのチャンクグループで、符号化データチャンクグループが記憶されることになるディスク記憶装置（たとえば、ドライブ）の数であり、そして、「ａ」は、元データを再生するために存在する必要があるデバイスの数である。図３Ａ〜３Ｂは、ＥＣカテゴリ２オブ４のアルゴリズムが、サイズ８ＫＢのデータオブジェクトを符号化するために使用される、例Ａを示す。図３Ｃ〜３Ｄは、ＥＣカテゴリ４オブ６のアルゴリズムがサイズ１６ＫＢのデータオブジェクトを符号化するために使用される、例Ｂを示す。図３Ｅ〜３Ｆは、ＥＣカテゴリ８オブ１０のアルゴリズムが、サイズ３２ＫＢのデータオブジェクトを符号化するために使用される、例Ｃを示す。アルゴリズム（複数可）は、他のサイズのデータオブジェクト、たとえば図３Ｃおよび３Ｅの表に示すもの、を符号化するために使用され得る。
【００４５】
[0053]図３Ａ〜３Ｂの例Ａで、データオブジェクト３０２は、３０４で２オブ４の消去アルゴリズムによって符号化され、その符号化されたデータは、ディスク記憶装置プール３０８内の４つのディスクドライブｄ１、ｄ２、ｄ４およびｄ６の各々に１つずつ、４つのチャンクグループ３０６として割り当てられる。図３Ｂは、サイズＸ＝８ＫＢの元データオブジェクト３０２が、集合的にオブジェクト３１２として示されるサイズＸ／８の８つの要素に分けられる符号化プロセスを示す。次に、その８つの要素は、エラー訂正アルゴリズム（ＥＣアルゴリズムによる）で結合され、集合的にオブジェクト３１４と示された各々サイズＸ／８の１６チャンクをもたらす。その１６チャンクは、各々サイズＸ／２の４つのチャンクグループに分けられ、その４つのチャンクグループは３１６ａ、３１６ｂ、３１６ｃ、および３１６ｄのラベルを付される。それらのチャンクグループのうちの異なるものが、図３Ａに示すようにプール３０８内の選択されたディスクドライブｄ１、ｄ２、ｄ４およびｄ６の各々に送信される。その符号化データのために使用される記憶総量は、１６ＫＢである（表３００）。これは、５０％の効率（１６ＫＢの記憶総量でサイズ８ＫＢのオブジェクトを記憶すること）を表す。
【００４６】
[0054]比較すると、例Ｂは、４オブ６のカテゴリアルゴリズムを使用して、６７％の効率、２４ＫＢの記憶総量で、サイズ１６ＫＢのより大きなオブジェクトを符号化する。別法として、より大きなオブジェクトサイズ、たとえば、３２ＫＢ、６４ＫＢ、１２８ＫＢ、および２５６ＫＢが、この４オブ６のアルゴリズムで符号化され、図３Ｃの表３２０内に示すのと同様の効率を生み出すことができる。この特定の例で、データオブジェクト３２２は、３２４で４オブ６のアルゴリズムによって符号化され、結果として生じる６つのチャンクグループ３２６は、図３Ａの２オブ４のカテゴリ符号化データで使用されるのと同じプール３０８内の任意の６つのディスクドライブ、ここではｄ１、ｄ２、ｄ４、ｄ５、ｄ６およびｄ７、で記憶される。図３Ｄは、サイズＸ＝１６ＫＢのデータオブジェクト３２２が、集合的にオブジェクト３３２と示されるサイズＸ／１６の１６の要素にどのように分割されるかを示す。次に、３３２の１６要素は、サイズＸ／１６の２４の等しいサイズのチャンク（エラー訂正要素を含む）、オブジェクト３２４として集合的に示される、に符号化される。次に、その２４チャンクは、ここでは３３６ａ〜ｆとして指示されるサイズＸ／４の６つの等しいサイズのチャンクグループに分けられ、６つのドライブｄ１、ｄ２、ｄ４、ｄ５、ｄ６、およびｄ７で記憶される。したがって、オブジェクトサイズ１６ＫＢの４オブ６の符号化は、２４ＫＢの記憶総量で、６７％の効率で記憶された。また、本発明によれば、この４オブ６のＥＣカテゴリアルゴリズム（図３Ａのアルゴリズムカテゴリとは異なる）からの符号化データは、２オブ４のカテゴリアルゴリズム（図３Ａの）からの符号化データとしてディスク記憶装置プール３０８内の同じドライブのすべてまたはいくつかで記憶され得る。
【００４７】
[0055]図３Ｅは、８オブ１０のＥＣカテゴリアルゴリズムが、８０％の効率で、４０ＫＢ記憶総量で３２ＫＢオブジェクトサイズを符号化するために使用される、例Ｃを示す。データオブジェクト３４２は、３４４で８オブ１０のＥＣアルゴリズムによって符号化され、プール３０８内の１０のディスクドライブ、ここではｄ１、ｄ２、ｄ３、ｄ４、ｄ５、ｄ６、ｄ７、ｄ９、ｄ１０およびｄ１１、のいずれかに送信される１０の等しいサイズのチャンクグループ３４６に区切られる。図３Ｆに示すように、サイズＸ＝３２ＫＢのデータオブジェクト３４２は、オブジェクト３５２として集合的に示されるサイズＸ／３２の３２要素に分割される。それらの要素は、次いで、エラー訂正符号を含み、オブジェクト３５４として集合的に示されるサイズＸ／３２の４０の等しいチャンクに符号化される。オブジェクト３５４は、次いで、各々サイズＸ／８の１０の等しいサイズのチャンクグループに分けられ、チャンクグループ３５６ａ〜ｊとして示される。再び、これらのチャンクグループは、図３Ａ、３Ｃおよび３Ｅに示されるプール３０８内の同ディスクドライブのいくつかまたはすべてで記憶される。この同じ８オブ１０のＥＣアルゴリズムは、表３４０に示すような他のデータサイズを符号化するために使用することができる。
【００４８】
Ｂ．ビットマスク割当ておよび位置合わせされた境界の割当て
[0056]符号化データが、割当ておよび回復プロセスを迅速に処理するために、１つまたは複数の位置合わせされた境界に沿った割当てのためのビットマスクを使用して複数の１つまたは複数のディスク記憶装置に割り当てられて、本発明のより具体的な実装形態が、ここで説明される。
【００４９】
[0057]一例では、インデックスで記憶されたデータオブジェクトの数（インデックス項目の数）に基づいて、そして、そのインデックスを記憶するための媒体のサイズに基づいて、最も小さいオブジェクトサイズが４ＫＢになるように選択される（すなわち、インデックス項目が表し得るデータの最小サイズ）。各インデックス項目は、オブジェクトが記憶されるディスク上の物理的位置を指すポインタを有する。このポインタは、４ＫＢ未満のデータを表すことはできない。ここで、割当てユニット（最小データサイズ要求）が、最小オブジェクトサイズ、すなわち４ＫＢ、と同じになるように選択される。結果として、割当てビットマスク上の１ビットと、以下に記載の対応する割当てビットマップおよび境界ビットマップの各々での１ビットとは、４ＫＢを表す。
【００５０】
[0058]図４Ａ〜４Ｂは、６つのディスクドライブ４０４ａ〜ｆを含むディスク記憶プール４０２の一実施形態を示す。本ドライブは、異なるタイプおよびサイズでもよい。各ディスクドライブは区切られ、各ディスクドライブが、パーティション４０６として各々定義された複数の論理記憶ユニットに分けられることを意味する。ドライブ４０４ａ〜ｆに広がるパーティションのグループ内の６つのパーティション４０６ａ〜ｆは、各々同じサイズであり、１つの論理記憶ユニットグループ４０８に属する。同ドライブ上の１つの論理記憶ユニットグループ内に２つのパーティションは存在し得ない。割当てビットマップおよび境界ビットマップは、以下に記載するようにそのドライブに消去符号化データを割り当てるために使用される。
【００５１】
[0059]図４Ｂは、ドライブ４０４ａ〜ｆのすべてに広がる１つの論理記憶ユニット（ＬＳＵ）グループ４０８ａの概略的表現を含む、図４Ａの同ドライブプール４０２の詳細をさらに示す。ＬＳＵグループ４０８ａは、各々がＬＳＵグループ４０８ａ内のすべてのドライブ（パーティション）に広がる複数の層状論理記憶ユニット４１２ａ〜ｏを含む。ＬＳＵグループ４０８ａの各パーティション４０６ａ〜ｆは、論理記憶ユニット４１２ａ〜ｏの複数の層状パーティションセグメントを有し、そのパーティション内の各々のＬＳＵセグメントは、ディスクドライブ４０４ａ〜ｆの各々についてそれぞれ４１４ａ〜ｆおよび４１６ａ〜ｆのラベルを付された、最初のパーティション境界４１４および終了パーティション境界４１６に沿って位置合わせされる。各パーティション４０６内のグループ４０８ａの複数の論理記憶ユニットは、等しいサイズであり、順に積み重ねられて示される。
【００５２】
[0060]一般に、符号化データは、以下のように単一の論理記憶ユニットグループに割り当てられ得る。先ず、そのデータが入り、オブジェクト（同じまたは可変サイズのデータ）に分割され、次いで、通常は、ハッシュされる。オブジェクト名（たとえば、ハッシュ）およびオブジェクトのサイズを含むオブジェクトレコードが、作成される。そのオブジェクトは、次いで、選択された消去符号に従って符号化され、そして、割当てビットマスクが、その符号化されたオブジェクトがどのように記憶される必要があるかをアロケータ、たとえば図１の構成要素１０８を参照、に説明するために生成される。そのアロケータは、そのビットマスクに一致する媒体（たとえば、ディスク記憶装置）上の記憶空間を見つける。そのデータは、次いで、その媒体に書き出され、ポインタが、インデックス内のそのオブジェクトのオブジェクトレコード内で記憶される。
【００５３】
[0061]一般に、そのアロケータは、割当てビットマスクと割当てビットマップの間でビット対ビット比較を実行する。単一の割当てビットマップが、システム全体のすべての記憶の状態（可用性）を記録するために、その記憶システムによって使用される。そのビットマップは、構成ファイル内で記憶され得る。割当てビットマスクおよび割当てビットマップの比較は、ビットマスク内のパターンがその下のビットマップに一致するまでそのビットマップの上でそのビットマスクを滑らせる（方向は問題にはならない）こととして（抽象的に）説明することができる。一致が見つかったとき、これは、そのデータを記憶するための位置を識別する。その位置は、次いで、ポインタとしてインデックス内のオブジェクトレコードで記憶される。一実施形態で、割当てビットマップは、論理アドレス空間にマップし、符号化されたオブジェクトへのポインタは、インデックス内のオブジェクトレコードで記憶される論理オブジェクト番号（ＬＯＮ）である。
【００５４】
[0062]図５は、本発明による単一の論理記憶ユニット上での符号化データの割当ての一例を示す。この例では、割当てビットマスク５０２が、ドライブプール、たとえば図１、３および４に示されるタイプのプール、の２４のドライブ上の使用可能な記憶の４０ＫＢを捜し出すことを目的としてオブジェクトに提供される。サイズ３２ＫＢのデータオブジェクトが、８オブ１０の消去符号化アルゴリズムによって符号化され、各々サイズ４ＫＢの１０の等しいサイズのチャンクグループをもたらす。ここで、割当てビットマスク５０２は、その論理記憶ユニットグループ内の２４のドライブの各々に１ビットで、２４の割当てセグメント（ビット）を有するように示される。第１の１０ビット（５０１）は「０」に設定され、それらがその論理記憶ユニットグループ内の任意の１０の隣接するドライブ上で符号化データを割り当てるために（１ドライブごとに１つのチャンクグループで、１０の符号化されたチャンクグループを記憶するために）必要とされる（要求される）ことを意味し、隣接は、次の論理記憶ユニット（ＬＳＵ）の第１のドライブに循環して戻ることを意味し得る。たとえば、第１の使用可能なブロックがＬＳＵ１１でドライブ２０にあった場合、１０チャンクグループを有するオブジェクトは、ＬＳＵ１１でドライブ２０〜２５にその第１の５チャンクグループを配置することによって記憶されることになり、残りの５チャンクグループはＬＳＵ１２のドライブ１に戻り、ＬＳＵ１２にあるドライブ１〜５で完全に記憶されるまで継続することになる。対照的に、図５の例では、使用可能な第１のブロックは、そのＬＳＵグループ内の第１のドライブと位置合わせする。残りの１４ビット（５０３）はＸのラベルを付され、それらが必要とされない（それらが空いていてもいなくても関係ない）ことを意味する。通常は、ビットマスクは、要求される「０」ビットの最短の長さ、この例では１０、まで短縮されることになる（たとえば、より少ないメモリの消費およびより少ない処理を理由として）。その結果として生じる割当てビットマップ５０４が、ビットマスク５０２の下に位置合わせされて示される。その割当てビットマップの第１の１０ビット（５０５）は、「１」のラベルを付され、したがって、そのプール内の第１の１０ドライブの各々に１つで、１０の符号化されたチャンクグループを割り当て、一方、その符号化データを記憶するために使用されないことになる残りの１４ビット（５０７）は、「０」のラベルを付される。これらのビットは、それらが前に割り当てられたかどうかに応じて、０か１のいずれかでもよい。この場合には、これらのビットは前に割り当てられてはいない。割当てビットマップ５０４の下に位置合わせされて示された境界ビットマップ５０６は同様に、２４セグメント（ビット）を有し、第１のビット（５０８）は、「１」のラベルを付されて、その符号化データオブジェクトの第１のチャンクがどのパーティション番号（どのドライブ）で記憶されるか、ここではＬＳＵグループ内の第１のドライブ、を指示する。
【００５５】
[0063]この符号化の仕組みによれば、全部のまたは部分的な論理記憶ユニットが、同時に割当ておよび書込みが可能である。また、部分的な論理記憶ユニットの読取り、たとえば要求されたオブジェクトのみを読み取ること、が可能である。
【００５６】
[0064]たとえば、オブジェクトの長さに沿ったそのオブジェクトのための開始ブロック（割当てユニット）が、インデックスレコードで記憶され得る。これは、１つのオブジェクトおよびそのオブジェクトのみを捜し出す（読み取る）ために必要とされる情報のすべてを提供することになる。しかし、一部の例では、そのオブジェクトサイズは、割当てビットマスクの容量を超える。この問題に対する１つの解決法が、図６Ａ〜６Ｃの符号化例によって示され、そこでは、各ドライブが８ＫＢのデータを保持する必要があるような、８オブ１０の消去符号の要件（１０ドライブ）内で大きなオブジェクト（８０ＫＢ）を符号化することが求められる。割当てビットマスクの各ビットは４ＫＢのデータのみを表し得ることが前に判定された（この例では）。これは選択につながる。
【００５７】
[0065]１つのオプションは、以下の積に等しい数にオブジェクトサイズを制限することである：（割当ての細分性）（ＥＣアルゴリズムによって必要とされるものとしてのチャンクグループの数）。これは、本例におけるもの（８０ＫＢ）などの大きなオブジェクトが、各々が異なる論理記憶ユニットグループに到達し得るまたは同じ論理記憶ユニットグループでの論理記憶ユニット間のギャップを有する、２つの別個のオブジェクトとして符号化されることを強制することになる。本発明の割当てビットマスクはギャップを可能にさせ、隣接しない割当てを許すので、このオプションは、隣接する割当てのみを可能にする先行技術の割当て方法よりさらに柔軟である。
【００５８】
[0066]本発明の好ましい実施形態による第２のオプションは、１つの要求が１チャンクグループにつき複数の割当てビットを有することを可能にする。この選択は、図６Ａ〜６Ｃに示される。図６Ａで、各チャンクグループが、割当てビットマスクで２つのビットを割り当てられ、各チャンクグループの最初のビットは、同じ論理記憶ユニットグループ内の２つの論理記憶ユニット６１５ａ、６１５ｂの共通の境界に沿って位置合わせされる。より一般には、その共通の境界は、任意のパーティション境界でもよく、すなわち、データチャンクは、その論理記憶ユニットグループ内の第１のドライブで記憶される必要はないが、そうではなくて、そのプール内の任意のドライブで開始して記憶することができる。図６Ａで、割当てビットマスク６０２は、８０ＫＢのデータを捜し出すことを１つの目的として、第１の論理記憶ユニット６０１（２４のドライブにわたる）を表す第１の２４ビットと、第２の論理記憶ユニット６０３（そ２４のドライブにわたる）を表す第２の２４ビットとを有する。その第１の論理記憶ユニットを表す第１の２４ビットのうちの第１の１０ビット（６０８）は、要求される（空いていなければならない）ものとしてそれらに印を付けるために陰影を付けられ、一方、その次の１４ビット（６１０）は、陰影を付けられていない（空いている必要はない）。また、その第２の論理記憶ユニットを表す第２の２４ビットのうちの第１の１０ビット（６１２）もまた陰影を付けられ（空いていることが要求される）、一方、その次の１４ビット（６１４）は必要とされない（２つの論理記憶ユニットのみが要求されるこの例では、無関係である）。その陰影を付けられていないビット６１０は重要である−−それらは、８０ＫＢのデータすべてが１０ドライブの２つの論理記憶ユニットにわたる１つの要求で割り当てられることを可能にする「ギャップ」を構成する。
【００５９】
[0067]ここで、単一のビットマスク６０２は、８０ＫＢの記憶総量に単一のオブジェクトを記憶するために使用され、記憶されるデータは、論理記憶ユニット境界６１５で位置合わせされた２つの等しい４０ＫＢ部分６０８、６１２内に割り当てられる。１４セグメントの割当てされない「ギャップ」６１０が、第１の論理記憶ユニットの割り当てられたセグメント１〜１０（６０８）と第２の論理記憶ユニットの割り当てられたセグメント１〜１０（６１２）との間でその割当てビットマスク内で提供され、共通の論理記憶ユニット境界６１５で位置合わせされた複数の論理記憶ユニットに符号化データを割り当てるために単一のビットマスクが使用されることを可能にする。前述のように、共通の境界は、任意のパーティション境界でもよく、それは論理記憶ユニット境界である必要はない。
【００６０】
[0068]図６Ｂは、結果として生じる割当てビットマップ６０４および境界ビットマップ６０６を示す。割当てビットマップ６０４は、同様に、４８セグメントを有し、第１の２４セグメントは第１の論理記憶ユニット６０１を指示し、第２の２４セグメントは第２の論理記憶ユニット６０３を指示する。第１のおよび第２の論理記憶ユニット６０１、６０３の各々の第１の１０セグメント６０８、６１２は、それぞれ、符号化されたオブジェクトデータの１０チャンクグループのために割り当てられる（各チャンクグループのための２ビット）。境界ビットマップ６０６は４８セグメントを有し、第１のセグメント６２５は、符号化されたオブジェクトの第１のチャンクを含むディスクブロック（第１の論理記憶ユニットの第１のブロック）を示す。
【００６１】
[0069]図６Ｃは、符号化データ６２８、６３２の２つの等しいサイズ４０ＫＢ部分がどのように、積み重ね整列で、同じパーティション（たとえば、論理記憶ユニット）境界６１５で位置合わせされるかを示す。図６Ｃは、ディスク記憶上で記憶された符号化データのビュー６３０であり、各列はドライブであり、各行は論理記憶ユニットである。共通の境界６１５で符号化データを積み重ねることによって、これは、ディスクヘッドが単一のドライブヘッドシークで符号化データの２つの論理記憶ユニットにアクセスすることを可能にする、すなわち、単一のヘッドが、その消去符号化の要件に反することなしに、複数の論理記憶ユニットでより大量の記憶されたデータにアクセスすることができる。これは、Ｉ／Ｏ性能を向上させる。この例では、２つのドライブが故障した場合、符号化データは、８ヘッドシークで再生され得る。対照的に、先行技術は、そのデータを再生するために１６ヘッドシークを必要とし得る。
【００６２】
[0070]前述の例は、消去符号要件に反することなしに、インデックス内の単一のポインタを使用して複数の論理記憶ユニットにわたって単一のオブジェクトをいかにして割り当てるかを説明する。割当てビットマップは、そのパーティション境界と整列する割り当てられないギャップを可能にする。それはまた、より大きなオブジェクトが単一の要求で符号化されることを可能にする。論理記憶ユニットグループ内の隣接するパーティションおよび隣接する論理記憶ユニットを横切る単一のオブジェクトを置くことによって、符号化データは、１つまたは複数のディスクドライブで積み重ねる（並べて表示する）ことができる。図６の例では、単一のビットマスク（要求）が使用されて各ドライブから４ＫＢブロックを連続的にマップし、最後のドライブがマップされた後は、第１のドライブに戻る。
【００６３】
[0071]さらに、本発明の一実施形態によれば、複数のデータオブジェクトを、論理記憶ユニットに置くことが可能であり、たとえば、図５に示す割当てビットマスク５０２上の残りの１４ドライブ、または図６の割当てビットマスク上の残りの１４ドライブは、他のデータオブジェクトを記憶することができる。また、論理記憶ユニット上の符号化データは、複数の異なる符号化アルゴリズムによって符号化することができる。ただ１つの要件は、符号化アルゴリズムによって必要とされるドライブの数が、論理記憶ユニットグループで記憶されることになるオブジェクトについて、この論理記憶ユニットグループ内のパーティションより少ないまたはそれと等しいことである。
【００６４】
[0072]前述の例で割当てビットマップは、どの論理オブジェクト番号（ＬＯＮ）がその符号化データを記憶するために使用可能であるかに印を付ける。境界ビットマップは、符号化されたオブジェクトの第１のチャンクを含むブロックに印を付ける。その境界ビットマップは、物理ブロック数（ＰＢＮ）からオブジェクトレコードへの逆マッピングのために使用される。たとえば、ディスクドライブが故障した場合、それが故障したときにそのドライブにあったデータを再生するためには、符号化データから欠損データを再計算するために、どのオブジェクトチャンクグループがその故障したドライブに存在したかを知る必要がある。これを行うための２つの方法がある：
１）故障したドライブに属するアドレスを有するすべてのオブジェクト（ＬＯＮからＬＯＮ＋長さ）のインデックスをスキャンし、基準に合うオブジェクトが見つけられたときに、残りのオブジェクトチャンクグループを読み取り、欠損データを再計算し、欠損チャンクグループを書き直す、あるいは、
２）故障したドライブに及ぶオブジェクト境界の割当ておよび境界ビットマップをスキャンし、見つけられたときに、残りのオブジェクトチャンクグループを読み取り、欠損データを再計算し、欠損チャンクグループを書き直す。
方法１は、ディスクおよびインデックス操作の両方を必要とする。方法２は、ディスク操作のみを必要とする。
【００６５】
Ｃ．コンピューティングおよび記憶環境
[0073]前述のＥＣアルゴリズム選択およびデータ記憶割当て方法は、たとえば、１つまたは複数のコンピュータで実行することができるコンピュータ実行可能命令との関連で、適切なコンピューティングおよび記憶環境において実装することができる。たとえば分散コンピューティング環境で、ある種のタスクは、通信ネットワークを介してリンクされた遠隔処理デバイスによって実行され、プログラムモジュールは、ローカルメモリ記憶装置および遠隔メモリ記憶装置の両方で捜し出され得る。その通信ネットワークは、グローバルエリアネットワーク、たとえばインターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、または、他のコンピュータネットワークを含み得る。本明細書に記載のネットワーク接続は、例示的であり、コンピュータ間の通信を確立する他の手段が使用され得ることが、理解されよう。
【００６６】
[0074]コンピュータは、処理ユニット、システムメモリ、およびシステムバスを含むことができ、そのシステムバスは、システムメモリおよび処理ユニットを含むがこれらに限定されないシステム構成要素を結合させる。コンピュータはさらに、ディスクドライブおよび外部構成要素へのインターフェースを含み得る。様々なコンピュータ可読媒体が、コンピュータによってアクセス可能であり、揮発性媒体および不揮発性媒体の両方、取外し可能媒体および取外し不能媒体を含む。コンピュータは、ディスプレイ画面、タッチ画面、キーボードまたはマウスを含む様々なユーザインターフェースデバイスを含み得る。
【００６７】
[0075]ここで図７を参照すると、コンピュータと複数のディスク記憶装置の間の通信のための一般的システム構成７００の一例が示される。そのディスク記憶は、その中でデータが、ハードディスクドライブ、フロッピディスクドライブおよび光ディスクドライブを含む１つまたは複数の回転ディスクの表面で様々な電子的、磁気的、光学的、または機械的方法によってデジタルで記録される、様々な記憶装置のいずれかでもよい。ＣＰＵ７０２はシステムメモリ７０４に接続されて示され、システムバス７０６はそのＣＰＵをチップセット７０８に接続する。そのチップセットは、ＩＯバス７１０および複数のＩＯスロット７１２を介して、複数のディスクドライブ７１６に接続するためのドライブコントローラなどの様々な入力／出力デバイスのいずれかに接続される。そのチップセットはまた、他の記憶装置７１８にも接続され得る。そのチップセットは、ビデオポート７２０、ネットワークポート７２２、マウスポート７２４、キーボードポート７２６などのうちの１つまたは複数を含み得る。
【００６８】
[0076]前述は、本発明の例を含む。もちろん、本発明の説明を目的として構成要素または方法論のあらゆる考えられる組合せを記載することは不可能であるが、本発明のさらなる組合せおよび置換が可能であることが、当業者には理解されよう。したがって、本発明は、本開示および／または特許請求の範囲内にあるすべてのそのような交換、修正および変化を包含するものである。
【図１】
0006346565.tif 000002
【図２】
0006346565.tif 000003
【図３Ａ】
0006346565.tif 000004
【図３Ｂ】
0006346565.tif 000005
【図３Ｃ】
0006346565.tif 000006
【図３Ｄ】
0006346565.tif 000007
【図３Ｅ】
0006346565.tif 000008
【図３Ｆ】
0006346565.tif 000009
【図４Ａ】
0006346565.tif 000010
【図４Ｂ】
0006346565.tif 000011
【図５】
0006346565.tif 000012
【図６Ａ】
0006346565.tif 000013
【図６Ｂ】
0006346565.tif 000014
【図６Ｃ】
0006346565.tif 000015
【図７】
0006346565.tif 000016