JP2000515709A - ビデオサーバにおいてデータを取り出すシステム - Google Patents

Abstract

(57)【要約】 オーディオ／ビデオサーバ（１００）において、データのブロックが読取器（１８０）により記憶媒体（１１０）から読み取られ、データストリームの形でユーザに供給される。記憶媒体（１１０）は、複数の記憶ユニット（１０２、１０４、１０６、１０８）を有している。上記ブロックは、少なくとも２つの異なる且つランダムに選択された記憶ユニットに記憶される。スケジューラ（１７０）がブロックの記憶媒体（１１０）からの読み取りを制御する。読み取られるべき各ブロックに関して、スケジューラ（１７０）は当該ブロックが記憶されている記憶ユニットから１つの記憶ユニットを、記憶ユニットの再生負荷がバランスされるように選択する。スケジューラ（１７０）は読取器（１８０）に読取要求を送出して、上記の選択された記

Description

【発明の詳細な説明】 ビデオサーバにおいてデータを取り出すシステム 技術分野 本発明は、記憶媒体からオーディオ及び／又はビデオデータのようなデータの ブロックを取り出し、これらブロックを最大でＮ_maxなる複数のデータの流れ(デ ータストリーム)の形でユーザに供給するようなシステムであって、各データス トリームが毎秒Ｒ_maxデータ要素なる同一の最大消費率を有し、前記記憶媒体が 少なくとも毎秒Ｎ_max＊Ｒ_maxデータ要素なる帯域幅を有し、該記憶媒体が複数の 記憶ユニットを有するようなシステムに関する。 背景技術 この種のシステムは、マルチメディアサーバ、もっと特定的にはビデオオンデ マンドサーバ又は準ビデオオンデマンドサーバに使用されている。このようなシ ステムにおける一般的な要件は、連続した途切れのないデータストリームを各活 動状態ユーザに供給することである。典型的には、データはハードディスクのよ うな通常の記憶媒体から読み取られ、これらディスクはＲＡＩＤシステムのよう なディスクアレイとして構成されている。一般的に、固定消費率システムと可変 消費率システムとの間の区別がなされている。固定消費率システムにおいては、 データは典型的には固定レートのデータストリームとしてユーザに供給される。 通常、該システムにおける各データストリームに関してはレートは同一である。 このようなシステムの一例は準ビデオオンデマンドシステムであり、該システム においては複数の映画を並列に再生することができると共に、同一の映画を数重 に並列に再生することができ、その場合、例えば５分毎又は１５分毎のように規 則的に同一の映画の新たなコピーが開始されるようになる。可変消費率システム においては、ユーザがデータを消費するレートは時間にわたり変化する。典型的 には、各ストリームに対して最大消費率を規定することができる。実際には、ス トリームを異なる最大消費率（例えば、オーディオストリームに対して或る最大 値を、合成されたビデオ及びオーディオストリームに対して他の最大値を）で効 率的に処理することもできるが、通常は全てのストリームに対して同一の最大消 費率が使用される。可変消費率システムは、例えば、ポーズ又はスローモーショ ンのようなＶＣＲ的な機能を扱うシステム、又はMPEG-2のような可変ビットレー トのデータ圧縮方法を使用するシステム用に使用される。 ユーザに対してデータを連続したデータストリームとして供給するために、デ ィスクからデータを読み取るための特別なスケジューリング構成が、読み取られ たデータを該データがユーザに供給される前に一時的にバッファする適切な構成 と共に必要である。固定消費率システムの場合は、典型的には、各ストリームに 対して固定の規則的な間隔で、一定量（１周期継続するに十分な）のデータが読 み取られバッファに記憶される。可変消費率システムにおいては、異なるストリ ームがバッファの所定のブロックを異なる時点で空にすることがあり得る。典型 的には、間隔の間に、データのブロックに対して余裕のあるバッファのストリー ムに関してのみデータが読み取られる。他のストリームは飛び越される。結果と して、データを読み取るための間隔の持続時間は可変となり、全ての活動状態ス トリームが新たなデータブロックを必要とするような状況により制限されること となる。 全てのデータストリームが最大データレートで消費する場合に必要とされるよ うな大きなディスク帯域幅を保証するために、データはアレイ内の全てのディス クにわたって分割（ストライプ）される。特に可変データレートシステムに関し ては、このことは各データブロックを全ディスクにわたって、該ブロックを読み 取る要求が上記ディスクの各々へのディスクアクセスを意味するように、分割す ることにより達成される。結果として、これらディスクの負荷は最適にバランス される。 通常、ディスクアレイ内のディスクの数は、並列に扱われるデータストリーム の数に鑑みて所要の帯域幅により決定される。従って、ディスクの数はデータス トリームの最大数と共に線形に増加する。ディスクへのアクセスの有効性がおお よそ一定に維持されるのを保証するために、１つのデータストリームのために個 々のディスクから読み取られるブロックの大きさは同一に維持されねばならな い(ディスクのあまりにも小さいブロックの読み取りは、特に該大きさがトラッ クの大きさ以下になると、オーバーヘッドを増加させる)。結果として、全ディ スク上にストライプされた累積されたブロックの大きさは、ディスクの数に伴っ て、従ってデータストリームの最大数と共に、線形に増加する。この結果、バッ ファの大きさもデータストリームの最大数と共に線形に増加する。各データスト リームに対してバッファが必要であるから、合成効果は、バッファの全体の大き さがデータストリームの最大数に対して略２次的に依存し、バッファの価格を、 特に多数のデータストリームを扱うシステムに対して、支配的な要因にさせてし まう。他の不利な効果は、当該システムの新たなデータストリームを活性状態に させる応答時間が略線形に増加する点にあり、その理由は、バッファを再充填す るに要する時間間隔が線形に増加し、このような間隔内では新たなユーザが当該 システムに参加できないからである。 発明の開示 本発明の目的は、上述したような種類のシステムであって、バッファの価格が 、扱われるデータストリームの最大数と共に線形に増加するようなシステムを提 供することにある。他の目的は、応答時間が、扱われるデータストリームの最大 数に無関係に略同一に維持されるようなシステムを提供することにある。 上記目的を達成するため、本発明によるシステムは、ブロックの所定の選択群 が、該選択群の個々のブロックが全体として少なくとも２つの異なる且つランダ ムに選択された記憶ユニットに記憶されることにより、前記記憶媒体に多重に記 憶され、該システムが、 前記データストリーム用のブロックの前記記憶媒体からの読み取りを、各ブロ ックに対して、当該ブロックが記憶される全ての記憶ユニットの対応する組から 当該ブロックが読み取られるべき１つの記憶ユニットを選択すると共に、対応す る読取要求を該選択された記憶ユニットに割り当てることにより制御するような スケジューラであって、該記憶ユニットを前記組から前記複数の記憶ユニットの 負荷がバランスするように選択するスケジューラと、 ブロック読取要求に応答して、対応するブロックを前記割り当てられた記憶ユ ニットから読み取り、対応するデータストリームでユーザに供給する読取器と、 を有していることを特徴としている。 １つのブロックが少なくとも２つの異なる記憶ユニットに記憶されることを保 証することにより、上記スケジューラは、再生の間に上記ブロックが何の記憶ユ ニットから読み取られるかを選択する選択度を有する。これにより、スケジュー ラは記憶ユニットの負荷がバランスするように記憶ユニットを選択することが可 能となる。各ブロックをランダムに選択された記憶ユニットに記憶することによ り、可変レートシステムに関してさえも、再生の間に比較的一様な負荷を達成す ることができる。このような可変レートシステムに関して、さもなければ、活性 状態ストリームに関して個々の記憶ユニットに時間的にどのように負荷が発生す るかを予測することは、困難又は不可能でさえある。単純なシステムでは、全て のタイトルの全てのブロックが当該システムに２度、即ち当該システムの２つの 異なる記憶ユニットに、記憶される。ブロックの選択群は、他の例としては、全 ブロックの一部であってもよく、その場合残りのブロックは１度だけ記憶される 。 本発明によるシステムにより提供される解決策は、帯域幅と違って記憶媒体の 容量は主要な決定要因ではなく、ハードディスクの容量は平均して帯域幅（典型 的には年４０％の増加）より高いレート（典型的には、年６０％）で増加してい るので、斯かる容量は益々決定要因ではなくなるという見通しから有利である。 ２年以内に典型的なディスクが２５Ｇバイトの記憶容量及び８５Ｍbits/secなる 保証されたデータレートを持つようになると仮定すると、以下の２つの筋書きを 描くことができる。第１の筋書きでは、本発明によるシステムのビデオオンデマ ンド版は、映画館におけるように、２０までの範囲の映画を最大で１０００人の ユーザに提供するように使用される。これら映画はMPEG2を用いて４Ｍbits/sec なる平均レートで符号化される。映画が平均して９０分の長さを有していると仮 定すると、映画当たり90*60*4.10⁶＝21.6*10⁹bits＝2.5Ｇバイトなる合計記憶容 量が必要とされ、結果として、必要とされる全記憶容量は約５０Ｇバイトとなる 。全てのブロックが２度記憶されるとすると、容量は約１００Ｇバイトでなけれ ばならず、これは４ないし５個のディスクに相当する。同時に１０００人のユー ザを扱うことができるには、４０００Ｍbits/secなる合計の保証さ れた帯域幅が必要とされ、これは４７個のディスクに相当する。このようなシス テムにおいて２３５を越える映画を記憶する必要がある場合にのみ、上記ディス クの容量は妥当なものとなる。本発明によるシステムが、ホテルにおいて典型的 であるように、１００人までのユーザに対して映画の選択を提供するよう使用さ れるような、もっと緩やかな第２の筋書きでは、帯域幅に関しては５つのディス クが必要となる。全ブロックの完全な二重化の場合は、上記５つのディスクは２ ３の映画を記憶することができ、これは斯様なシステムにおいて通常提供される よりも多い。 更に、本発明は、データブロックは多重に記憶されてはいるが、典型的なシス テムにおいては実際には、本発明によるシステムでは従来のシステムにおけるよ り少ない記憶ユニットしか必要とされないという洞察に基づいている。既に前記 筋書きで示したように、帯域幅が殆どの実際のシステムに関しては制限要因であ り、益々そうなるであろう。データブロックを個々の記憶ユニットにわたって最 早分割（ストライプ）するのではなく、代わりに、１つのディスクから全体のブ ロックを読み取ることにより、記憶ユニットからデータを読み取る効率が改善さ れる。前記第１の筋書きでは、丁度２％を越えるような効率の改善の結果、既に 、ディスクが節約される。 本発明による本実施例の他の利点は、当該システムの強さが改善される点にあ る。一例として、１２個のディスクのうちの１つが故障し、全ブロックが二重化 されているとすると、前記スケジューラは、平均し１０個のブロックのうちの１ つに関しては、当該ブロックを何のユニットから読み取るべきであるかを選択す ることができないであろう。結果として１つの記憶ユニットの平均負荷は５.３ ％増加し、残りの記憶ユニットの１つの最大負荷も略同じような割合で増加する であろうことが分かる。システムが最大数のユーザによっては使用されないよう な殆どの状況では、これにより、故障したディスクを交換する十分な機会が与え られる。パリティディスクのような他の手段は必要とされない。 更に、該システムの拡張性が増加する。もし追加の帯域幅（又は記憶容量）が 必要な場合は、追加のディスクを当該システムに付加することができる。次に、 既に存在するディスクから新たなディスクへブロックを移動する必要がある。移 動されるべきブロックは、ランダムに選択することができる。典型的には、移動 されるべきブロックの数は、略、１つのディスク上に記憶されるブロックの平均 数であろう。本発明によるシステムにおいては、当該システムの動作に対する影 響は極めて少ない。５０個のディスクのシステムにおいては、ブロックの２％だ けしか移動する必要がない。他の全てのブロックは全く影響を受けない。また、 移動作業は、ブロックを移動させるための容量が利用可能な場合に何時でも実行 することができる(即ち、該作業は当該システムが動作している間にバックグラ ウンドで実行することができる)。ブロックが上記の新たなディスクに移動され るにつれて、当該システムの容量は、最終的に所望の数のブロックが該新たなデ ィスクに移動されてしまうまで、緩やかに増加する。これとは対照的に、ブロッ クが全ディスクにわたりストライプされている典型的なシステムにおいては、全 てのディスクがアクセスされねばならず、新たなディスク上にデータを記憶する ためにブロックは再構築さえされなければならない。このような大きな作業は、 通常、当該システムがオフライン状態にある間になされねばならない。 ロサンゼルスのような町を経る建築学的歩行のような三次元対話型アプリケー ション用のディスク利用型記憶サーバが、Compocon'96（41^st IEEE Computer So ciety International Conference，Santa Clara，25-28 Febr.，1996）の“リア ルタイムディスクＩ／Ｏ用のランダム化されたデータ割り当て”に記載されてい る。少なくともテラバイト程度の非常に大きな三次元モデルを考えている該シス テムにおいては、遅延の上限及び資源利用性に関してはＩ／Ｏストリームの性質 が、これらの点が（殆ど）予測可能であるようなビデオオンデマンドシステムと は非常に異なっている。このシステムの場合、ユーザの予測不可能なアクション が、当該モデルの全く新たな部分が見えるようになるか及びユーザに提示しなけ ればならないかを決定する。上記モデルの新たな部分を提示するために必要とさ れる大きなピーク帯域幅を提供することができるように、データブロックは典型 的には７つのブロックの群を形成する７個のディスク上にストライプされ、各ブ ロックがディスク上の１つの完全なトラックを占有している。７個のディスクの 群が利用可能なディスクの全組からランダムに選択される。上記７つのブロック のうちの１つはパリティブロックである。各群のランダムな分散の結果、待ち 行列の長さは統計的に変化する。上記可変性は、ｇ個のブロックの群のうちのｇ −１個のブロックのみを読み取ることにより減少させることができる。読み取ら れなかったブロックがデータブロックである場合は、前記パリティブロックが該 読み取られなかったブロックを再生するために使用される。 請求項２に記載された構成は簡単なスケジューリングのやり方を説明しており 、この場合、記憶媒体からデータブロックを取り込むための要求はスケジューラ により個別に処理され、典型的には、これら要求が該スケジューラに到達する順 に処理される。各要求に対して、スケジューラは、既に割り当てられたブロック 読取要求の結果としてのその時点の実際の負荷に基づいて、何の記憶ユニットに 当該要求が割り当てられるべきかを判定する。この記憶ユニットは、読み取られ るべき上記ブロックを記憶している全ての記憶ユニットのうちの最低の負荷を有 している記憶ユニットとなる。 請求項３に記載された構成は、読み取られるべき一群のブロックのための要求 を分散させることにより負荷をバランスさせる。これにより、既に割り当てられ た要求が最早影響を受けないような上記要求を個別的に割り当てる場合に比較し て、一層一様な負荷が可能となる。一例として、要求を個別に割り当てると結果 として以下のような状況となる。或る要求が、等しい負荷を持つ２つの可能性の ある記憶ユニットＡ及びＢから選択された記憶ユニットＡに割り当てられるとす る。記憶ユニットＣの負荷は、Ａ及びＢの初期負荷より１だけ大きいとする。次 の要求に対しては、記憶ユニットＡ及びＣの間で選択がなされねばならない。こ の場合、Ａ及びＣは共に等しい負荷を有していることになるから、どのような選 択をしても、これらの記憶ユニットの一方の負荷を常に増加させる結果となる。 一方、両要求を１つの群として扱うことにより、上記最初の要求がＢに、第２の 要求がＡに割り当てられるようにし、上記３つのユニットの最大負荷を低くする ことができる。殆どのシステムにおいては、記憶ユニットは同期された方法で読 み取られ(即ち、読み取り動作は全てのディスクに対して同時に開始され、ここ で読み取り自体はディスクのヘッドの１つの掃引動作で実行される)、最も重い 負荷を伴う記憶ユニットの負荷の増加は、結果として記憶ユニットからの読み取 りの間隔が長くなることを意味することになる。この結果、新たなユニットを受 け付ける応答時間が長くなる。 請求項４に記載の構成は、一群の要求に対して負荷をバランスさせる簡単なス ケジューリング法を述べており、そこでは、前記記憶媒体からデータブロックを 取り込むための要求は、スケジューラにより個別に、及び典型的にはこれら要求 が該スケジューラに到達する順序で処理される。各要求に対して、スケジューラ は、既に割り当てられているブロック読取要求から生じるその時点での実際の負 荷に基づいて、この要求が何の記憶ユニットに割り当てられるべきかを判定する 。ここで、上記記憶ユニットは読み取られるべき当該ブロックを記憶する全ての 記憶ユニットのうちの最低の負荷を持つ記憶ユニットであるとする。更に、現在 処理されている又は記憶ユニットに既に確実に割り当てられている（例えば、当 該ディスクの次の掃引動作において読み取られるべきブロックに関する要求を記 憶するハードウェアの読取要求バッファに既に送出されている）要求は、考慮す る必要がない。負荷が各連続した群内で一様にバランスされることを保証するこ とにより、連続した群の結果として、記憶ユニットの比較的一様な負荷が維持さ れる。 請求項５に記載された構成によれば、記憶ユニットへの非常に一様な負荷を得 ることができる。シミュレーションは、請求項５で述べられている順次再割り当 ての丁度１循環が後続するような請求項４に記載の初期順次割り当てを用いるこ とにより、分散が最適値に極めて近くなることを示している。次の反復を実行す るための条件は単純にカウンタ（１個のみの再割り当てステップを実行するよう な）であり得るが、例えば、最大負荷及び平均負荷の点での、それまでに得られ た分散の品質に依存させることもできることが分かるであろう。請求項６に記載 した構成は、前の反復ステップの結果改善が得られたか否かの簡単な判断基準を 与える。 請求項７に記載した構成は、最大フロー問題の類推に基づいて、如何に負荷の 最適な分散を達成することができるかを述べている。 請求項８に記載した構成は、最適な負荷を達成する効果的且つ単純な方法を提 供する。 請求項９に記載した構成は、各タイトルが、当該タイトルの多重化のレベルを 示す多重係数に関連付けられることを述べている。有利には、当該システムにお いて２以上の異なる多重係数を用いることができる。例えば、最も好まれている タイトルの群に対しては大きい多重係数が選択され(例えば、２より大きい、こ れはタイトルに関してタイトルの一部からというよりは、ブロックの量の２倍を 越えるものが記憶されることを示す)、それ程規則的にアクセスされない、古い 好みのような、ものに対しては小さい多重係数（例えば、タイトルを記憶するの に殆ど余分のブロックを用いないものから、ブロック数の１.５倍を使用するも のまで）が使用される。シミュレーションは、同様の評判を持つ映画に関しては 、約１.７５なる多重係数（即ち、再生の間にブロックの７５％が２倍利用可能 である）で既に良好な結果を達成することができることを示している。最も評判 の良いタイトルを多重にすることにより、タイトルの実質的に７５％未満を二重 化することによって再生の間の７５％なる全多重係数が既に達成される。 上記タイトル特有の多重化は、多重にブロックを記憶するような何らかの形で 他のシステムにも応用することができる。このようなシステムは、オーディオ及 び／又はビデオデータのようなデータのブロックを記憶媒体から取り出すと共に 、これらブロックを複数のデータストリームの形態でユーザに供給するようなシ ステムとして説明することができ、この場合、上記憶媒体が複数の記憶ユニット を有し、ブロックの所定の選択群が、該選択群の個々のブロックが少なくとも１ つの記憶ユニットの少なくとも２つの異なる且つ重ならない群に記憶されること により、前記記憶媒体に多重に記憶され、前記ブロックが複数のタイトルに関係 し、各タイトルが一連のデータブロックを有すると共に所定の多重係数に関連付 けられ、１つのタイトルの多重係数が該タイトルに関して前記記憶媒体に記憶さ れたブロック数と該タイトルのブロック数との比に関するものであり、当該シス テムが、 前記データストリーム用のブロックの前記記憶媒体からの読み取りを、各ブロ ックに対して、当該ブロックが記憶される少なくとも１つの記憶ユニットの全て の群の対応する組から、当該ブロックが読み取られるべき１つの群を選択すると 共に、対応する読取要求を該選択された群に割り当てることにより制御するよう なスケジューラと、 ブロック読取要求に応答して、対応するブロックを少なくとも１つの記憶ユニ ットの前記割り当てられた群から読み取り、対応するデータストリームでユーザ に供給する読取器と を有している。 １つのブロックは単一の記憶ユニット記憶することもできるし、又は２以上の 記憶ユニットの群にも記憶することができる（例えば、２、３の記憶ユニット又 は前記記憶媒体上に分割して帯域幅を増加させる）ことが分かるであろう。ブロ ックが多重に記憶される場合は、該ブロックの各データ要素は少なくとも２つの 異なる記憶ユニットに記憶される(完全な重なりはない)。このようにして冗長性 が達成され、該冗長性は強さを増加させるのみならず、再生の間のバランスを可 能にする。例えば、もし１つのブロックが２つのディスクの群上にストライプさ れ(即ち、２つの副ブロックＳＢ１及びＳＢ２として記憶される)、且つ、３度記 憶されたとすると、好ましくは、上記２つの異なる副ブロックの各々は３つの異 なる記憶ユニットに記憶される。この場合、１つの記憶ユニットが故障したとし ても、各副ブロックは依然として少なくとも２つの記憶ユニットから利用するこ とができる。好ましくは、上記記憶ユニットの群は“ランダム”に選択され、再 生の間に負荷のバランスを増加させる。しかしながら、当該システムは高度に非 ランダムな記憶戦略にも利点を与えることができる。しばしば使用される非ラン ダム記憶戦略は、所謂、ラウンドロビン法である。このようなシステムにおいて は、１つのタイトルのブロックは順次のディスク上に再生の順序で記憶される。 一例として、７つの主ディスクを備えるシステムに関しては、タイトルの最初の ブロックはディスク１に、ブロック２はディスク２に、…、ブロック７はディス ク７に、ブロック８はディスク１に、ブロック９はディスク２に、等々のように 記憶される。このようなシステムにおいて冗長性を達成するために、典型的には パリティディスク（本例では、ディスク８）が追加され、その場合、該パリティ ディスクは各サイクル（ブロック１ないしブロック７、ブロック８ないしブロッ ク１５）に対し、当該サイクルのブロックに対して算出された１つのパリティブ ロックを記憶する。全ての主ディスクが機能しているとすると、１つのサイクル は７個の連続したディスクアクセスを要する(ディスクの各々につき１アクセ ス)。しかしながら、もし主ディスクの１つが故障すると、６個の通常のアクセ スと７つの追加のアクセス（直接読み取れないブロック用であり、パリティディ スクへの１つのアクセスと依然として動作している主ディスクへの６つのアクセ スとである）とが必要である。結果として、このような状況における当該システ ムの性能は殆ど半分となる。他の例として、１つのサイクルの全ての通常にアク セス可能なブロックをメモリに維持し、利用不可能なディスクからのブロックを 上記パリティブロックとの組み合わせで再構築するために使用することもできる 。しかしながら、この方法はメモリの要件を大幅に増加させ、典型的には、大幅 に少ないユーザにしかサービスを提供することができなくなる結果となる。ブロ ックを多重に記憶することにより、当該システムの強さが増加される。好ましく は、同一のブロックは最適に“位相をずらして”記憶され、最悪の場合のアクセ ス遅延を減少させる。一例として、上述したシステムにおいてブロックが各々２ 回記憶されるとすると、好ましくは、ブロック１はディスク３（又はディスク４ ）にも記憶され、新たなユーザに対する最悪の場合の遅延を、１サイクルの持続 時間の代わりに半サイクルの持続時間まで減少させる。主ディスクの１つが故障 したとしても、全てのブロックは依然として利用可能である。１サイクルの７つ のブロックのうちの２つのみが１つのディスク上で利用可能であろう。通常のラ ウンドロビン読み取り方法は最早使用することができない。好ましくは、各ブロ ックに対して、実際の負荷に基づいて、何の記憶ユニットから当該ブロックが読 み取られるべきかを判断する。ブロックのランダム記憶を伴うシステムについて 前述したように、全てのブロックが多重には利用可能でなくても、バランスはそ れ程厳しくは影響を受けない。従って、性能の劣化は伝統的なラウンドロビン方 法と較べて僅かである。ブロックの多重記憶は記憶コストを増加させるかもしれ ない。このような増加は、別個のパリティディスクを使用しないことにより（一 部）相殺することができる。例えば、ラウンドロビン様式のシステムでは、２０ ％の最も評判の良いタイトル（通常、使用の少なくとも８０％をカバーする）は ２回記憶されるが、他の全てのタイトルは１回だけしか記憶されない。パリティ ディスクは最早使用されない。１つのディスクが故障した場合、ユーザの８０％ は影響を受けない。８０％のあまり評判のよくないタイトルはテープのようなバ ックア ップ記憶部から取り出され、多分、ユーザの２０％は影響を受ける。このような 場合、これらのタイトルのうちの幾つか又は全ては、故障したディスクが取り替 えられ再組み込みされるまで提供することは可能ではないであろう。多重化の概 念は、各記憶ユニットが直接アクセス可能であり且つ冗長性及び負荷バランスが もっぱらこれら記憶ユニットの群に生じるような１つのコヒーレントな記憶媒体 に関わるものであることが分かるであろう。このような記憶媒体の一例は、１群 のデイスクを備え、１つの共有バスを介してコントローラに接続されたディスク アレイである。含まれていないのは上記のようなディスクアレイと、タイトルの ブロックを記憶するテープのようなバックアップ記憶部との組み合わせであるこ とが分かるであろう。小さなディスクアレイが集合されて大きなディスクアレイ を形成するような階層的ディスクアレイにおいては、前記記憶媒体は、１つのタ イトルの全ブロックを記憶するために使用される方の、小さい方のディスクアレ イか又は大きい方のディスクアレイの何れかに関わるものとなる。 請求項１０に記載した構成は、１つのタイトルは全体として多重に（例えば、 ２回又は３回）記憶されることができ、他の例として又はそれに追加して、該タ イトルの個々のブロックの或る割合が多重に記憶されるようにしてもよいことを 示している。一例として、１.７５なる多重係数は、当該タイトルを４つのブロ ックの重なり合わない連続した群の系列と見ることができ、ここで、各群の３つ のブロック（例えば最初の３つのブロック）は２回記憶され、１つのブロック（ 例えば、最後のブロック）は１回だけ記憶されることを表すことができる。同様 に、２.５なる多重係数は、当該タイトルの奇数毎のブロックは２回記憶され、 偶数毎のブロックは３回記憶されることを表すことができる。 図面の簡単な説明 本発明の上記及び他の特徴を図示の実施例に基づいて説明するが、図面におい て： 第１図は、本発明によるシステムのブロック図を示す。 第２図は、再生のために記憶ユニットを選択する線形順次方法のフローチャー トを示す。 第３図は、再生のために記憶ユニットを選択する反復線形順次方法のフローチ ャートを示す。 第４図は、ノードのネットワークを経る最大のフローを解くことに基づいて再 生のための記憶ユニットを選択する方法を図示する。 第５図は、再生のために記憶ユニットを選択する他の反復手順を図示する。 第６図は、ブロックの多重化無しから全ブロックの完全な二重化までの多重係 数の範囲に対するシミュレーションされた結果を示す。 発明を実施するための最良の形態 第１図は、本発明によるシステム１００のブロック図を示している。このよう なシステム１００の一例はマルチメディアサーバである。マルチメディアアプリ ケーションは、視聴覚材料の広範な使用により特徴付けられる。オーディオ又は ビデオの再生のためには、オーディオ／ビデオデータの（準）連続的な供給が必 要とされる。マルチメディアサーバの既知の例は、準ビデオオンデマンドサーバ 及びビデオオンデマンドサーバを含む。準ビデオオンデマンドサーバシステムに おいては、サービスプロバイダが何時タイトルが再生されるかを決定する。該タ イトルのデータを含むデータストリームは、多くのユーザにより同時に受信する ことができる。ビデオオンデマンドシステムにおいては、典型的には、ユーザが タイトルを選択し、ＶＣＲ的な制御により該タイトルの再生を制御する。対話の レベルは高く、データストリームは典型的には一人のユーザによってのみ消費さ れる。マルチメディアサーバは、通常、同様のデータレート（典型的には同一の 最大データレートにより制限される）の多数のユーザ用の連続したデータストリ ームを並列に供給するように特別に設計されたファイルサーバを用いて実施化さ れる。通常、１つ又はそれ以上のマルチメディアタイトルがバックグラウンド記 憶媒体１１０に記憶される。現時点では、普通、ハードディスクのようなディス クが、それらの低価格大記憶容量及びランダムアクセスが可能であることから、 該バックグラウンド記憶媒体１１０として使用されている。光ディスクのような 他の記憶媒体、又は固体メモリさえも使用することもできることが分かるであろ う。該記憶媒体は、一例として１０２、１０４、１０６及び１０８で示されてい るように、複数の記憶ユニットに分割されている。従って、記憶媒体１１０はＲ ＡＩＤシステムのように一群（クラスタ）の記憶ユニットにより形成されること になる。ハードディスクのような該記憶ユニットは、それ自体更に副分割するこ とができる(結果として、階層的クラスタとなる)。本説明の目的で、この様に副 分割された記憶ユニットは１つの記憶ユニット（記憶ユニット内の副ユニットよ りも広い帯域幅及び／又は大きな記憶容量を持つ）とみなす。ディスク型の記憶 媒体を使用する典型的なビデオオンデマンドシステムに関しては、記憶媒体１１ ０を形成する記憶ユニットの数は所要の帯域幅により決定される。典型的には、 全てのデータストリームは毎秒Ｒ_maxデータ要素なる同一の最大消費率により制 限され、ここで１データ要素は例えば１バイトである。MPEG-2で符号化された題 材に関しては、最大消費率は、所望の品質に応じて、典型的には約２Ｍbits/sec と約１５Ｍbits/secとの間に選定される。同時にＮ_max個までのデータストリー ムを扱うよう設計されたシステムは、略Ｎ_max＊Ｒ_max／Ｂ個の記憶ユニットを必 要とし、ここでＢは個々の記憶ユニットの帯域幅である。実際には、幾つかのデ ータストリームに対する最大消費率は、もし例えば対応するタイトルが低品質又 は異なる形式（例えばオーディオ、ところが殆どのストリームがオーディオとビ デオとの組み合わせに関するものである）のものである場合は、当該システムが 通常設計される最悪の状況よりも低くてもよい場合があることが分かるであろう 。 当該システム１００は記憶媒体１１０からデータを読み取る読取器１８０を有 している。該読取器１８０は、例えば、ＳＣＳＩインターフエースを用いて構成 することができる。有利には、記憶媒体１１０も当該システム１００に含まれる ものとする。ディスク型記憶媒体１１０の場合は、データはディスクアクセスブ ロック（ＤＡＢ）として取り出される。選択されたスケジューリングアルゴリズ ムに応じて、データを固定サイズのＤＡＢとして読み取るか又は可変サイズのＤ ＡＢとして読み取るかに優先度が付与される。同一のディスクから順次読み取ら れるＤＡＢは、典型的には、当該ディスク上には連続的には記憶されてはいない 。通常、同一のディスクから順次読み取られるＤＡＢは、当該ディスクが複数の データストリームに関するＤＡＢを何らかのインターリーブされた態様で供給し なければならないので、異なるファイルに属している(ここで、１つのファイル は １つのタイトルに属するブロックの集合である)。連続的に読み取られるべきＤ ＡＢが同一のファイルに属しているとしても、本発明によれば、１つのファイル の連続したブロックは１つの記憶ユニットに連続的に記憶されるのではなく、記 憶媒体１１０の各記憶ユニット上にランダムに分散される。非連続なＤＡＢを読 み取る結果、ディスクヘッドはＤＡＢを読み取る間に移動される必要があり、次 のＤＡＢの適切な開始点を待たねばならない。このような切り替えは相当の時間 を要し、その間データは読み取ることができない。この切り替えオーバーヘッド を減少させるために、所謂ディスク掃引技術がしばしば使用される。このような 方法では、読取器１８０は記憶ユニット１１０から例えば８個のような多数のＤ ＡＢを１バッチで読み取ることができる。該バッチのＤＡＢは、それらの物理的 トラック位置に基づいて配列されている。読み取り動作に関しては、ディスクヘ ッドは１方向のみ（例えば、最内側位置から最外側位置まで、又はその逆）に移 動され、当該バッチのＤＡＢを読み取るためにのみ停止する。このようにして、 上記切り替えオーバーヘッドは大幅に減少される。有利には、読み取り要求のバ ッチを受け、要求された読み取り動作の所要のスケジューリングを反復実施して 特定のディスクに関して最適の掃引を行うような読取器１８０が使用される。読 取器１８０は、ディスクから読み取られたデータを、潜在的にディスクから読み 取られたのとは異なる順序で、バス１４０を介して当該システム１００の残部に 供給する前に、一時的に記憶するためのキャッシュメモリも含んでいる。上記読 み取りの制御、掃引順序の管理及び読み取られたデータのキャッシュ記憶のよう な当該読取器の役割は分散させることができ、その場合、上記記憶ユニットの各 々がこれら機能を果たす自身のコントローラを有することが分かるであろう。も しそうなら、読取器１８０の主たる仕事は、これらの種々の“インテリジェント ”制御ユニットの動作を協調させることとなる。 特にビデオに関しては、データストリームは非常に大量となる。この量を減ら すために、典型的には、圧縮技術が使用される。圧縮方法の結果、例えばMPEG-1 符号化の固定レート様式を用いた固定レートのデータストリームが、又は例えば MPEG-2符号化の可変レート様式を用いた可変レートデータストリームが得られる 。本発明によるシステムは、可変データレートストリームに対しては毎秒Ｒ_max データ要素なる固定の同一の最大消費率が与えられることを仮定し、該最大 消費率は当該システムが最悪の状況（例えば、全てのデータストリームが最大の データレートでデータを消費する場合）においても動作するのを保証するために 該システムの規模（例えば、当該システムの帯域幅及び／又は記憶部のサイズ） の決定に使用される。通常、データは圧縮された形態で記憶媒体１１０内に記憶 され、当該システム１００により処理される。ユーザ１３０においてのみ、デー タストリームはデコーダを用いて伸張される。特に可変レートシステムの場合は 、システム１００はＶＣＲ的な制御機能を扱うこともできる。このような場合は 、データストリームは活性状態及び停止された状態のような複数の状態のうちの １つにあり、ここで、活性データストリームはユーザにデータを供給し、停止さ れたデータストリームは目下ユーザにはデータを供給しない。典型的には、ユー ザがデータの消費を一時的に停止している場合は、当該ストリームは活性状態の ままである。ユーザがストリームを切り替えると(例えば、明示的に新たなタイ トルを選択するか、又は当該システムに高速順方向送りモードを指示する結果と して同一のタイトルが高速で表示されるような新たなストリームが選択されるこ とにより暗黙的に新ストリームが提供される)、当該ストリームは一時的に停止 され、新たなデータがロードされるのを可能とする。スローモーション機能はデ ータを低いレートで消費することにより(当該ストリームは活性状態のままであ る)、又は新しいストリームに切り替える（当該ストリームは一時的に停止され る）ことにより実施することができることが分かるであろう。システム１００は 、当該データストリームに対して、現在の状態を示すストリーム状態を維持する 。１又はそれ以上のデータストリームのストリーム状態は、当該サーバの主メモ リ（ＲＡＭ）又は特別なレジスタのような状態メモリ１９０に記憶することがで きる。 データは、１度に１つのデータストリームのみに対して、又は前述したように １つのバッチのデータストリームに対して、記憶媒体１１０から読み取られ、そ の場合、上記バッチのデータはバス１４０を介して時間多重されたストリームと して供給される。何れの場合においても、記憶媒体１１０は当該システムの全て のユーザに対して連続したデータストリームを同時に供給することはできない。 その代わりに、データストリームの部分集合に対するデータが読み取られ、当該 システム１００の残りの部分に対して、対応するデータストリームによりその時 点で消費される高いデータレートで供給される。従って、当該システム１００は 、各ユーザ１３０へのデータの所要のレートでの供給を達成するために、バッフ ァ１２０を有している。通常、バッファ１２０はＲＡＭを用いて構成される。当 該システム１００は、更に、上記データストリームのデータをユーザに伝送する ための通信手段１５０を有している。この通信手段１５０は、当該システム１０ ０の近くに位置するユーザに対して上記データを供給するためのローカルエリア ネットワークのような何らかの好適な手段により形成することができる。実際に は、長い距離にわたり上記データを供給するために電気通信回路網又はケーブル 回路網が使用される。 システム１００は、当該システム１００を制御するための制御ユニット１６０ も有している。該制御ユニットの主要部分はスケジューラ１７０により形成され ており、該スケジューラはバッファ１２０のアンダーフロー又はオーバーフロー を防止するために読取器１８０により記憶媒体１１０から何のＤＡＢが読み取ら れるべきであるかを決定する。該制御ユニットは、典型的には、ＲＩＳＣ型マイ クロプロセッサ又はＣＩＳＣ型マイクロプロセッサのようなプロセッサにより形 成され、該プロセッサはＲＯＭ又はハードディスクのような記憶媒体からロード されるリアルタイムオペレーティングシステムの制御の下で動作する。スケジュ ーラ１７０は、上記オペレーティングシステムに統合されたソフトウェアモジュ ールとして構成されるか、又はアプリケーションプログラムとしてロードするこ とができる。典型的には、スケジューラ１７０は前記バッファの充填度のような 状態情報を受け取り、該情報をスケジューラ１７０は判断の基とする。ＶＣＲ的 な制御を提供するようなシステムに関しては、上記スケジューラはストリームの 状態に関する情報も入力する。このようなシステムにおいては、典型的には、制 御情報はユーザ１３０から通信手段１５０を介して入力される。 本発明によるシステムにおいては、ブロックの選択組が、少なくとも２つの異 なるランダムに選択された記憶ユニットに記憶されることにより、記憶媒体１１ ０に多重に記憶される。該ブロックは完全に多重化される。結果として、このよ うなブロックは当該ブロックが記憶されている全ての記憶ユニットから完全に利 用可能である(１つのブロックの一部を他の記憶ユニットに記憶された他の部分 から再生することができるような或る形態のエラー検出及び訂正符号を使用する 場合とは対照的に)。これらブロックはオフライン（即ち、データをユーザに供 給している当該システムの動作中ではない）で記憶ユニットに記憶することがで きる。例えば、当該システム（又はシステムの一部）をオフラインに切り替え、 タイトルを記憶ユニットに追加（又は、から削除）することを可能にすることが できる。他の例として、上記記憶ユニットを取り外し可能型とし、その場合、別 のシステム（タイトルの所有者側に位置するか、又はビデオオンデマンドサーバ プロバイダへのタイトルの供給者側に位置する）が上記タイトルを所望の態様で 記憶ユニットに記憶するために使用される。しかしながら、通常、タイトルはデ ィスクが動作中の場合に記憶ユニットに記憶される。前記帯域幅の一部が記憶ユ ニットに記憶されたタイトルの変更のために確保されるか、又は、このような操 作は当該システムがいっぱいに負荷を受けていないような場合に（即ち、特にウ ィークデイの夜の或る一部の間では普通であるように、当該システムが最大数の データストリームを処理していない場合に）実行される。当該システム（又は別 のシステム）は、ブロックの選択群を、このようなブロックが少なくとも２つの 記憶ユニットに確実に記憶されるようにして、前記記憶媒体に多重に記憶する手 段（図示略）を有している。好ましくは、このようなブロックは正確に２つの記 憶ユニットに記憶されるようにし、その場合、これら記憶ユニットは記憶媒体１ １０の記憶ユニットの上記組からランダムに選択される。ディスクの選択は、多 重に記憶されるべき各ブロックに対して別々になされる。（疑似）ランダム順序 発生器が、利用可能な記憶ユニットの範囲内でランダムな数を発生するために使 用される。上記ブロックの選択群における順次のブロックの各々に対して、次の ランダム数は前記手段が当該ブロックを記憶する記憶ユニットを示す。以下に詳 述するように、記憶ユニットをランダムに選択することは、ブロックを取り出す 場合に負荷の良好なバランスを可能にする。記憶ユニット（又は複数の記憶ユニ ット）を（疑似）ランダム的な態様で選択するのとは別に、当業者は、或るシス テムに対して所望の“ランダム”効果を達成するような適切なアルゴリズムを設 計又は選択することができるであろう。明らかに、多重に記憶される１つのブロ ックが各々異なる記憶ユニットに記憶されるのが好ましく、さもなければ該多重 化が負荷のバランスの改善（又は強さの改善）という結果をもたらさないからで ある。このことは、発生されたランダム数が当該ブロックを既に記憶している記 憶ユニットに対応している場合は、次のランダム数を使用することにより、簡単 に達成することができる。選択された１つのブロックを２つの記憶ユニットに記 憶する代わりに、ブロックをもっと多くの記憶ユニットに記憶することもできる ことが分かるであろう。より多くの記憶ユニットが使用されるにつれて、ブロッ クの記憶ユニットへの割り当てはあまり“ランダム”である必要がなくなる。こ こで、１９９４年の計算理論についてのＡＣＭシンポジウムの第５９３〜６０２ 頁に掲載されたY.Azar e.a.の“バランスされた割り当て”は、ｎ個のボールが ｎ個の箱に投入されるようし、ここで各ボールにはランダムに２つの箱が選択さ れ、当該ボールは投入時点においてより満たされていない箱に投入されるように すると、最も満たされた箱は、高い確率で、ln ln n/ln 2+0(1)個のみのボール を含むことになる、と述べている。これは、上記ボールが１個のランダムに選択 された箱に投入された場合（この場合は、最も満たされた箱は、高い確率で、ln n/ln ln n(1+o(1))個のボールを含む結果になるであろう）よりも指数関数的に 少ない。これらの結果は、特に多数のブロックに関しては、全てのブロックを完 全に二重化し、これらブロックをランダムに２つのディスクに記憶すると、これ らディスクは略同一の数のブロックを有する結果になることを示している。実用 的目的のため、特定のディスクに記憶されるブロックの数は、全てのディスクに 記憶されるブロックの数の平均に近いと仮定することができる。 多重に記憶されるブロックの選択組は、当該システム内の全てのタイトルの全 てのブロックとすることができる。他の例として、ブロックの選択組は、当該シ ステムにおける全てのタイトルの部分集合の全てのブロックに対応する。有利に は、このような部分集合は最も好まれているタイトル（例えば、ユーザによる全 アクセスの９０％のような所定のパーセント、又は最も頻繁にアクセスされる全 タイトルの１０％のようなパーセントをカバーするタイトルの集合）により形成 される。代わりとして又は組み合わせとして、上記ブロックの選択は、或るタイ トルのブロックの部分集合に対応するようにしてもよい。例えば、或るタイトル の１つ置きのブロックが多重に記憶される一方、該タイトルの他のブロックは１ 回だけ記憶されるようにする。多くの変形が可能であることが分かるであろう。 例えば、或るタイトルの３つの連続したブロックの群のうち、最初のブロックは １度だけ記憶され、２番目のブロックは２回記憶され、３番目のブロックは３回 記憶されるようにする。また、或る群のブロックのうち何のブロックが多重に記 憶されるかは異なってもよい(例えば、ランダムに選択されてもよい)。 通常、記憶媒体１１０に記憶されるブロックは複数のタイトルに関係し、ここ で各タイトル（通常ファイルとして記憶される）は一連のデータブロックを有し ている。好ましくは、各タイトル（又はタイトルの群）が所定の多重係数に関連 付けられる。タイトルの多重係数は、当該タイトルに関して上記記憶媒体に記憶 されたブロックの数と、当該タイトルのブロックの数との比に関係する。一例と して、当該タイトルがＮ個のブロックを有し、該タイトルがＭ個のブロック（Ｍ ≧Ｎ）として記憶される場合は、多重係数はＭ／Ｎで与えられる。例えば、或る タイトルの１０００なる全ブロック（Ｎ＝１０００）が二重化され、結果として Ｍ＝２０００となる場合は、多重係数は２である。同様に、全ブロックが３重に 記憶される場合は、多重係数は３である。従って、タイトルの多重係数は、該タ イトルの個々のブロックが記憶媒体に何回記憶されているかを示す。他方、或る タイトルのブロックの半分が２回記憶され、他の半分が１回しか記憶されていな い場合は、多重係数は１.５となる。或るタイトルの４つのブロックの内の３つ （即ち、該タイトルの７５％）が２回記憶され、残りの４分の１が１回しか記憶 されていない場合は、多重係数は１.７５（Ｍ＝750*2＋250*1＝1750）となる。 これらの例では、タイトルの多重係数は、該タイトルのブロックの何パーセント が記憶媒体中に多重に記憶されているかを示している。好ましくは、多重係数の 全体部分（引く１）が当該タイトルの個々のブロックが記憶媒体に何回記憶され たかを示し、残りが当該タイトルの記憶媒体１１０にもう１度記憶されたブロッ クのパーセント（全ブロックよりも少ない）を示すようにする。他の組み合わせ も可能であることが分かるであろう。例えば、ブロックの半分が１回記憶され、 他の半分が３回記憶された場合も、多重係数は２である(Ｍ＝500*1＋500*3＝ 2000)。このような特定の多重化策は特定のタイトルに使用することができ、そ の場合、例えば当該タイトルの一部は非常に頻繁にアクセスされるが他の部分は 通常飛び越される。Ｍ／Ｎなる多重係数の代わりに、選択されたブロックの多重 の程度を表すような他の多重係数を使用することもできることが分かるであろう 。 好ましくは、タイトルの多重係数は当該タイトルの評判に依存させるようにす る。有利には、最も好まれているタイトルに対しては大きい多重係数が選択され 、それ程頻繁にアクセスされない“古い好み”のものに対しては小さい多重係数 が使用される。多重係数は、当該システムの典型的な使用（即ち、評判のよいタ イトルとそれ程評判がよくないタイトルとの間の平均したバランスで）に対して 、平均多重係数が所望のレベルとなるように選定される。明らかに、上記多重係 数はタイトルの群に対して選択することもできるし、個々のタイトルに対しても 選択することができる。 スケジューラ１７０は記憶媒体１１０からのブロックの読み取りを制御する。 動作中に、スケジューラ１７０は、例えばバッファ１２５の１つが新たなブロッ クを記憶する余裕がある場合、又はユーザが新たなタイトルを選択した場合に、 新たなブロックを読み取る要求を受け取る。スケジューラ１７０がバッファ１２ ５に新たなブロックのための余裕があるか否かを積極的にチェックしてもよいこ とが分かるであろう。新たなブロックが必要な場合は、スケジューラ１７０は当 該ブロックが記憶される記憶ユニットの組を決定する。該ブロックが単一の記憶 ユニットのみに記憶される（即ち、当該ブロックが多重に記憶されるブロックの 選択組に属していない）場合は、スケジューラは当該ブロックを読み取るための 読取要求を該記憶ユニットに割り当てる。当該ブロックが多重に記憶される場合 は、スケジューラ１７０は、それらの記憶ユニットのうちの１つを選択し、この 選択された記憶ユニットに当該ブロックを読み取るための読取要求を割り当てる 。スケジューラは、前記組から上記記憶ユニットを、記憶媒体１１０の各記憶ユ ニットの負荷がバランスするように選択する。 スケジューラ１７０が送出したブロック読取要求に応答して、読取器１８０は 対応するブロックが上記の割り当てられた記憶ユニットから読み取られるように 制御する。読み取られたブロックはバッファ１２５のうちの、当該ブロックがユ ーザへの供給のために読み取られたデータストリームに対応する１つに記憶され る。 本発明によるシステムの簡素な実施例においては、スケジューラ１７０はデー タストリームのためのブロックの取り込み要求を個別に取り扱う。要求が到来す る（又は、スケジューラ１７０が新たなブロックが必要であることを自ら検出す る）毎に、該スケジューラは、対応する群のうちのその時点で最も負荷が軽い記 憶ユニットを選択する。以前の読取要求の再割り当てはなされず、スケジューラ に既に到来しているであろうブロックの取り込み要求は考慮されない。以前のブ ロック要求の唯一の影響は、既に割り当てられているが未だブロックが読み取ら れていないようなブロック読取要求に基づいて判定される各記憶ユニットの負荷 を介してのものである。実際の状況では、スケジューラ１７０は、当該スケジュ ーラ１７０が依然として状態を決定することができるような割り当てられたブロ ック要求を考慮に入れることができるのみであることが分かる。一例として、読 取器１８０（又は、上記記憶ユニットの個々のコントローラ）は掃引順序を最適 化するためにハードウェアで何らかの形の内部スケジューリングを実施すること ができる。一旦読取要求が発せられると、スケジューラ１７０は、最早、何時実 際のブロックが読み取られようとしているか又は読み取られているかを決定する ことはできない。従って、スケジューラ１７０は斯かるブロック読取要求を完了 されたもと、及び負荷に最早寄与しないものと見なすことができる。 本発明によるシステムの他の実施例においては、スケジューラ１７０はブロッ クを取り込むための２以上の要求の群を一度に扱うことにより各記憶ユニットへ の負荷をバランスさせる。これは、一層良好なバランスを可能とするのみならず 、ビデオサーバにおいて通常使用されている巡回的なやり方に調和しており、そ こでは各サイクルにおいて何のデータストリームに対してブロックを読み取る必 要があるかを先ず判断し、次いで対応するブロック読取要求が割り当てられ、最 後に、これらブロックが１つの掃引動作により読み取られる。この掃引動作は、 任意選択的に、全ての記憶ユニットに対し同期される。本発明によれば、スケジ ューラ１７０は、先ず、次のサイクルにおいて読み取られるべきブロックの群を 決定する。スケジューラ１７０は、次に、該群の全てのブロックに関して、該群 の 全てのブロックに関して、これら記憶ユニットへの負荷がバランスするには何の 記憶ユニットから上記ブロックを読み取るべきかを選択し、対応する読取要求を 割り当てる。最後に、スケジューラ１７０は読取器１８０により対応するブロッ クを上記の割り当てられた記憶ユニットから読み取らせる。上記群の割り当てか ら生じる負荷のみを考慮することにより、負荷は、少なくとも関係する記憶ユニ ット（即ち、読み取られるべきブロックのうちの１つのコピーを有する各記憶担 体）に関してはバランスされる。典型的には、上記群は記憶ユニットの合計数よ り大幅に大きいので、通常は、全ての記憶ユニットが関係する。他の例として、 スケジューラ１７０は、それらブロックが未だ全て読み取られていないなら、以 前の群の割り当ての結果としての負荷も考慮することができる。上述したように 、通常、ブロック読取要求はスケジューラ１７０により、読取器１８０が前の群 の全てのブロックを読み取った辺りでのみ送出されるであろう。このようなやり 方においては、当該群のブロックから生じる負荷をバランスさせるだけで十分で ある。何故なら、他の群から生じる負荷は残っていないからである。 第２図は、本発明によるシステムの他の実施例におけるスケジューラ１７０の 動作のフローチャートを示し、ここで該スケジューラは前記群の各ブロックを順 次処理する。これらブロックには何らかの順序が存在すると仮定する。この順序 自体は重要ではない。この順序は、例えば、スケジューラ１７０がブロックを取 り込むための要求を受ける順序であり得る。他の例の順序は、当該ブロックが意 図されるバッファの順序に基づくものかもしれない。好ましくは、異なる多重係 数を用いるシステムに関しては、上記順序は多重係数に基づいて決定され、その 場合、小さな多重係数を持つブロックの読取要求が最初に割り当てられ、大きな 多重係数を持つブロックの要求は最後に割り当てられるものとする。このように して、全てのブロックに対して選択の自由度があり(最初の方のブロックに関し ては記憶ユニットは未だ大きな負荷を掛けられておらず、最後の方のブロックに 関しては高いレベルの多重の結果としての選択により)、一層良好な負荷バラン スが得られる。ステップ２００において、スケジューラは該順序の最初のブロッ クを選択する。選択されたブロックは、ステップ２１０、２２０及び任意選択的 にステップ２３０において処理される。ステップ２４０においては、スケジュー ラ１７０は該群の全てのブロックが処理されたかを判断する。もしそうなら、動 作は終了する。そうでない場合は、ステップ２５０において当該群の次のブロッ クが選択され、処理がステップ２１０において継続される。各ブロックに対して 、スケジューラ１７０はステップ２１０において、当該ブロックが記憶される記 憶ユニットの群を判定する。ステップ２１５においては、全てのブロックが多重 に記憶されているのではないようなシステムで使用される任意選択的な判断がな される。当該ブロックが単一の記憶ユニットにのみ記憶されている（即ち、当該 ブロックが多重に記憶されたブロックの選択群に属していない）場合は、スケジ ューラは、ステップ２２０において、当該ブロックを読み取るための読取要求を 該記憶ユニットに割り当てる。当該ブロックが多重に記憶されている場合は、ス ケジューラ１７０はステップ２３０において該群から記憶ユニットの１つを選択 し、ステップ２２０において当該ブロックを読み取るための読取要求を、この選 択された記憶ユニットに割り当てる。スケジューラ１７０は、その時点で当該群 の以前に処理されたブロックのために既に割り当てられていたブロック読取要求 の結果として最も低い負荷を有している記憶ユニットを選択する。このアルゴリ ズムは、以下では、線形割り当てアルゴリズム（Linear Assignment algorithm ）と呼ぶ。 第３図は、本発明によるシステムの他の実施例におけるスケジューラ１７０の 動作のフローチャートを示す。ステップ３１０において、スケジューラ１７０は 初期割り当てを実行する。該スケジューラは当該群のブロックの各々に対して予 備的な記憶ユニットを選択し、対応するブロック読取要求を、上記の予備的に選 択された記憶ユニットに割り当てる。上記の選択過程は、常に当該群から最初の 記憶ユニットを選択するか(この場合、各記憶ユニットは順番に配列されている と考える)、又は記憶ユニットの前記群から記憶ユニットの１つをランダムに選 択するというように、単純なものとすることができる。好ましくは、ステップ３ １０の初期割り当ては、ブロックの群内のバランスを考慮した第２図の順次割り 当て方法を用いて実行される。この初期割り当てに続いて、スケジューラ１７０ は、当該群の各ブロックに対して１つの記憶ユニットが再選択されると共に、対 応するブロック読取要求が再割り当てされるような反復手順を開始する。好まし くは、上記再割り当ては第２図に示した方法に対応するような下記の方法により 実行される。再び、これらブロックには何らかの順序が存在すると仮定すると、 スケジューラ１７０はステップ３２０において該順序の最初のブロックを選択す る。選択されたブロックは、ステップ３３０、３４０及び３５０で処理される。 ステップ３６０においては、スケジューラ１７０は当該群の全てのブロックが処 理されたかを判断する。もしそうなら、該反復手順のループは完了する。もしそ うでないなら、ステップ３７０において当該群の次のブロックが選択され、ステ ップ３３０において処理が継続される。ステップ３８０においては、スケジュー ラ１７０は当該ループを終了するための条件が満たされているかを判断する。も しそうなら、当該ループからは抜け出され、さもなければ次のループがステップ ３２０において開始される。上記条件自体は、当該ループが所定の回数実行され たか否か、又は最後のループの結果としての最大負荷が当該ループが開始された 以前と同じであるか否か等の、単純な条件である。各ブロックに対して、スケジ ューラ１７０はステップ３３０において、何の群の記憶ユニットに当該ブロック が記憶されているかを判定する。ステップ３３５においては、全てのブロックが 多重には記憶されていないようなシステムで使用することができる任意選択的な 判断がなされる。当該ブロックが１つの記憶ユニットにのみ記憶されている（即 ち、当該ブロックが多重に記憶されたブロックの選択群には属していない）場合 は、該スケジューラはステップ３４０において、当該ブロックを読み取るための 読取担要求を該記憶ユニットに割り当てる。当該ブロックが多重に記憶されてい る場合は、スケジューラ１７０はステップ３５０において当該群から記憶ユニッ トのうちの１つを選択し、ステップ３４０において当該ブロックを読み取るため の読取要求を、この選択された記憶ユニットに割り当てる。スケジューラ１７０ は、その時点で、当該群の以前に処理されたブロックに対して既に割り当てられ ていたブロック読取要求の結果として最低の負荷を持つ記憶ユニットを選択する 。このアルゴリズムは、以下では線形再割り当てアルゴリズム（Linear Reassig nment algorithm）と呼ぶが、上記初期割り当ては線形割り当てアルゴリズム（L inear Assignment algorithm）により実行される。 本発明による他の実施例においては、スケジューラ１７０は当該群のブロック に関するブロック読取要求を、近似最大フロー問題（analogous maximum flow p roblem）を解くことから導出される割当に従って割り当てる。第３図のステップ ３１０と同様に、スケジューラ１７０は当該群のブロックの各々に対して予備的 な記憶ユニットを選択し、この予備的に選択された記憶ユニットに対して対応す るブロック読取要求を割り当てることにより、先ず初期割り当てを実行する。近 似最大フロー問題は以下のように定義される。各記憶ユニットｓ_iに対して対応 するノード（頂点）ｎ_iを含むようなノードｎ_iのネットワークが定義される。こ のネットワークは、ソースノード（ｓ）及びドレインノード（又はシンクノード ）(ｄ)も有している。各ノードｎ_iは対応する弧（有向辺）を介してｎ_j（ｎ_i≠ ｎ_j）に接続されており、該弧はｓ_i及びｓ_jの両方に記憶され且つ対応するブロ ック読取要求がｓ_iに割り当てられているようなブロックの数に対応する容量を 有する。従って、該容量はｓ_iからｓ_jに再割り当てすることができるブロックの 数を示している。第４ａ図は、ノードｎ₁ないしｎ₃により各々表された３つの記 憶ユニットｓ₁ないしｓ₃に関するネットワークを図示している。この例では、記 憶ユニットｓ₁ないしｓ₃の各初期負荷が１５、１２及び１０であると仮定されて いる(対応するノードの中心に示されているように)。或るノードから他のノード への弧の傍には、これらノードに対応する記憶ユニットの間で幾つのブロック読 取要求を再割り当てすることができるかが示されている(例えば、本例では、３ 個のブロックをｓ₁からｓ₂に、２つのブロックをｓ₂からｓ₁に再割り当てするこ とができる)。前記問題は、記憶ユニットの最大負荷ｌ_maxをｋ単位だけ低下させ ることができるかを判断することができるというように定義され、ここで上記負 荷はブロック読取要求のこれら記憶ユニットへの前記予備的割り当ての結果であ る。この目的のため、ソースｓがmax(k＋l_i-l_max，0)なる容量の対応する弧を介 して各ノードｎ_iに接続される。この式において、ｌ_iは、予備的にｓ_iに割り当 てられたブロック読取要求の結果としての記憶ユニットｓ_iの負荷に対応する。 結果として、最大負荷ｌ_maxは、全記憶ユニットにわたるｌ_max＝max{ｌ_i}により 与えられる。第４ａ図の例では、ｌ_maxは１５である。更に、各ノードｎ_iはmax( l_max-l_i-k，0)なる容量を持つ対応する弧を介してドレインｄに接続されている 。第４ａ図の例では、ｋは２に選択され、前記ソースから各ノ ードへの及びこれらノードから上記ドレインへの対応する容量が示されている。 次に、当該ネットワークを経る最大フローが計算される。第４ｂ図は、算出され たフローの可能性のある結果を示している。各弧の隣に（第４ａ図では容量が示 されたのとは異なり）フローが示されている。弧内のフローは該弧の容量を超え ることはできない。ソースｓから各ノードへの弧の容量は、ソースｓから各ノー ドへの算出されたフローが当該容量に一致する（即ち、容量が完全に使用される ）場合及びこのような場合にのみ、上記最大負荷がｋ単位だけ確かに低下させる ことができるというように、定義される。一例として、或るノードの負荷が最大 負荷ｌ_maxに等しい場合は、容量max(k＋l_i-l_max，0)＝max(k+l_max-_max，0)＝ｋ を反映して、該ノードの負荷をｋ単位だけ低下させることが望ましい。同様に、 ｌ_max−１なる負荷を持つノードに関しては、容量max(k＋l_max-1-l_max，0)＝max (k-1，0)＝k-1（ｋ＞＝０と仮定する）を反映して、該負荷はｋ−1単位だけ低下 させることが望ましい。上記式は、ｌ_max−ｋ（又は、それよりもっと低い）な るノードの負荷は低下させる必要がないことも表している。同様に、各ノードか らドレインｄへの弧の容量は、当該ノードへの負荷を、ｌ_max−ｋなる所望の最 大負荷を越えることなく、どれだけ多くの単位だけ増加させることができるかを 表している。各ノードからドレインへの算出されたフローは、当該システムがい っぱいには負荷されていないことを反映して(第４ｂ図ではｎ₃からドレインへの フローは１であるのに対し、その容量は３であり、ｎ₃への負荷は未だ更に２つ のブロックまでは増加することができることを示している)、各容量よりは低い であろうことが分かるであろう。算出された最大フローが最大負荷をｋ単位だけ 低下することができることを示している場合は、スケジューラ１７０は、結果と して算出されたｎ_iからｎ_jへのフローに等しいようなブロック読取要求の数をｓ_i からｓ_j（ｓ_i≠ｓ_j）へ再割り当てする。第４ｃ図は、第４ｂ図に示される算出 されたフローによる再割り当てを示している。当該ネットワークを介しての最大 フローを計算するには、よく知られているフォード＆ファルカーソン（Ford&Ful kerson）アルゴリズムのような如何なる好適なアルゴリズムも使用することがで きる。最大フロー理論の詳細は、１９８９年のケンブリッジ大学出版の第９６〜 １０６頁にアラン・ギブソンにより掲載された“アルゴリズム的グラ フ理論”に記載されている。 良好にバランスされたシステムの記憶ユニットに対する最大負荷は、（境界を 含み）これら記憶ユニットへの切り上げ(upwardly rounded)平均負荷ｌ_avgと、 前記予備的割り当ての結果としての最大負荷ｌ_maxとの間にあるであろう。従っ て、ｋは１とｌ_max−ｌ_avgとの間に選択することができる(ｌ_maxがｌ_avgに等し い場合は、負荷は低下させることはできない)。最大負荷を低下させることがで きるｋの最大値を決定するには、種々の方法を使用することができる。例えば、 所望の結果に到達するまで、境界の一方から始めてｋの全ての値を順次試す(例 えば、ｋ＝ｌ_max−ｌ_avgで開始して最大フローを計算する；そして、成功しなか った場合は成功するまで又はｋ（ｋ＝１）なる最終値が不成功に試されるまでｋ を低下させる)。また、“二進サーチ”を実行することもでき、ここではｋは間 隔の略中間に選択される。もし成功した場合は該間隔の上側半分で繰り返され、 さもなければ該間隔の下側半分で繰り返される。斯かる処理は、ｋの値に到達す るまで繰り返される。 本発明によるシステムの一実施例においては、前述した最大フロー問題に基づ くアルゴリズムを解くことにより得られるのと同じ結果が、反復手順を実行する スケジューラ１７０により達成され、これが第５図に示されている。前述と同様 に、最初のステップ５１０は、当該群のブロックの各々に対して予備的な記憶ユ ニットを選択し、対応するブロック読取要求を該予備的に選択された記憶ユニッ トに割り当てることにより初期割り当てを実行することである。この初期割り当 てに続いて、スケジューラ１７０は反復手順を開始し、該手順においてはブロッ ク読取要求を最大負荷を持つ記憶ユニットからｌ_max−１より少ない負荷を持つ 記憶ユニットへ再割り当てする試みがなされる。この再割り当ては或る記憶担体 から他の記憶ユニットへの直接的なものでもよいが、一連の再割り当ても起こり 得る。ステップ５２０においては、スケジューラ１７０は、ｓ_iへの負荷が複数 の記憶ユニットの最大負荷ｌ_maxに等しいような負荷を持つ記憶ユニットｓ_iを選 択する。この負荷は現在割り当てられているブロック読取要求からの結果である 。２以上の記憶ユニットが最大負荷を持つ可能性があることが分かるであろう。 もしそうなら、これらのうちの何れか（例えば、これらのうちの最初のもの）を 選択することができる。ステップ５３０においては、スケジューラは、ｓ_iから ｌ_max−１未満の負荷を持つ別の記憶ユニットｓ_jへの経路が存在するか否かを判 断する。該経路を介して１つの読取要求をｓ_iからｓ_jへ移動することが意図され 、これによりｓ_iへの負荷を１つ減らし、ｓ_jの負荷を１つ増やす。改善を得るに は、ｓ_jへの結果としての負荷がｌ_max未満でなければならず、これはｓ_jの初期 負荷がｌ_max−１未満でなければならないことを意味する。上記経路に沿つて読 取要求を移動することができるように、該経路はｓ_i＝ｓ_p1及びｓ_j＝ｓ_p1である ような一連の記憶ユニットｓ_p1,ｓ_p2,…,ｓ_p1により形成され、ここで各対ｓ_pk, ｓ_p(k+1)に対してブロック読取要求がｓ_pkからｓ_p(k+1)に再割り当てされること ができる（ｋは１からｌ−１の範囲である）。このような経路が存在するか否か の判断には、如何なる好適なアルゴリズムも使用することができる。一例として 、記憶ユニットｓ₁ないしｓ₃（ノードｎ₁ないしｎ₃により表されている）に関し て第４図に図示したようなグラフを形成することができ、該グラフを介してツリ ー検索を実行することができる。経路が存在した場合は、ステップ５４０におい てスケジューラ１７０は、１からｌ−１の範囲のｋに対してブロック読取要求を ｓ_pkからｓ_p(k+1)に再割り当てする。次に、該手順はステップ５２０において再 開される。その時点で、ｓ_iの負荷は１だけ低下されている。他の記憶ユニット が依然としてｓ_iが前に有していたのと同様の最大負荷を有している場合は、こ れらユニットのうちの１つがステップ５２０において選択される。ｓ_iが上記最 大負荷を有する唯一の記憶ユニット（又は最後の記憶ユニット）であった場合は 、これは自動的に当該システムの最大負荷を１だけ低下させたことになるであろ う。結果として、前よりは１だけ低下しているが、ｓ_iは今や再び最大負荷を有 する（通常、幾つかの他の記憶ユニットも該最大負荷を有する）ことになる。こ の処理は、記憶ユニットに対して負荷を低下させるような経路を見つけることが できなくなるまで繰り返される。 本発明による３つのアルゴリズム、即ち線形割り当て(Linear Assignment;LA) 、線形再割り当て（Linear Reassignment;LR）及び最大フロー割り当て（Maximu m Flow Assignment;MFA）の振る舞いがシミュレーションされた。ｍ＝５〜３０ 個のディスクに関して(５のステップで)、シミュレーションが実行され、ここで 更に活動ストリームの数が、ストリームの数をディスクの数で割った値が５〜３ ０（５のステップで）の範囲となるように、変化された。従って、当該システム における活動ストリームの数は２５〜９００の範囲である。下記の表は、該シミ ュレーションの1,000,000回の連続する掃引に関する結果を示している。全ブロ ックが完全に二重化され、各掃引においてデータブロックが各活動ストリームに 対して取り込まれ、全ストリームが最大レートで連続的に消費する最悪状況の筋 書きを反映した。この表に示される３つの結果の各群のうち、上の結果はＬＡア ルゴリズムに関係し、真ん中の結果はＬＲアルゴリズムに関係し、下の結果はＭ ＦＡアルゴリズムに関係するものである。各結果は最大の観測された負荷を示し 、ここで該最大負荷が観測された回数が括弧内に示されている。 これらシミュレーションは、比較的単純なＬＲアルゴリズムで以て、最大負荷が 観測される回数はＭＦＡアルゴリズムの場合よりも多いが、殆ど全ての状況にお いてＭＦＡアルゴリズム（該アルゴリズムは達成可能な最良の負荷バランスを提 供する）で得られるのと同様の最大負荷を伴うような良好な結果が達成され得る ことを示している。また、これらシミユレーションは、ブロックを完全に二重化 すると共にこれらブロックをランダムに記憶することにより、特にＬＲ及びＭＦ Ａアルゴリズムの場合に、殆どのシミュレーションされた状況に対して、下限で ある平均負荷より３ないし１０％だけしか高くないような最大負荷を達成するこ とができることを示している。かくして、達成することができるバランスは極め て良好である。 下記の表は、同一のシミュレーションに関して観測された平均最大負荷を示し 、特に大きなシステムに関しては、最大負荷が平均して全ディスクの平均負荷に 近づいていることを確認している。 第６図は、１５個のディスクと２２５個の活性状態データストリームとの場合（ 平均負荷はディスク当たり１５ストリームとなる）の、1,000,000回の連続し た掃引に対するＭＦＡアルゴリズムのシミュレーションされた結果を示し、ここ で多重係数は１（多重化無し）から２（完全な二重化）まで変化された。１.２ ５なる多重係数（２５％の二重化）は、４ブロックのうちの１つが二重化された ことを示している。該図は、何回（垂直方向）最大負荷（水平方向）が観測され たかを示している。各ブロックが１回だけしか記憶されていないようなシステム （０％二重化）に関しては、該図は観測された最大負荷が略１８ストリーム／デ ィスクと２８ストリーム／ディスクとの間にあり、３０を優に越えるような最大 負荷が時々生じることを示している。このような構成が採られると、斯様なシス テムはディスク当たり約３０ストリームを処理することができるように設計値が 決められねばならないことになるが、平均負荷はディスク当たり１５ストリーム に過ぎないから、２なる係数分過剰設計となることが分かるであろう。５０％な る多重係数のシステムに関しては、観測された最大負荷は略１５ストリーム／デ ィスクと１８ストリーム／ディスクとの間にある。このようなシステムを例えば ２０ストリーム／ディスク用に設計すること（３３％の過剰設計）は、決して矛 盾（即ち、２０を越えるような最大負荷）を生じることはないであろう。従って 、第６図は、記憶容量が制限要因であるようなシステムに対しては、１００％未 満の二重化程度で良好な結果が達成されることを示している。シミュレーション は、約６０ないし８０％の範囲の二重化程度で既に良好な結果が得られることを 示している。そのような場合、過剰設計は２５％未満であればよく、もっと大き なシステムでは、それより大幅に低くてもよい。１００％の二重化の場合は、Ｌ Ｒ及びＭＦＡアルゴリズムに対しては、１５個のディスクを備え、ディスク当た り１６ストリームを扱うように設計された（６.７％の過剰設計）システムは、 シミュレーションにおいて何の問題も観測されずに、２２５のストリーム（平均 で、１５ストリーム／ディスク）を扱うことができる。実際の状況では、結果は もっと良いことが理解された。上記シミュレーションは、全てのストリームが最 大消費率でデータを消費し、ディスクの効率が特定された最低であるような最悪 の状況を仮定して実行された。実際には、ディスクの効率はもっと良好であり、 可変消費率システムの場合は、平均消費率は最大消費率よりも大幅に低いであろ う。結果として、特に大きなシステムに関しては、過剰設計の程度は更に低下さ せる ことができる。

Claims (1)

1. 【特許請求の範囲】 １．オーディオ及び／又はビデオデータのようなデータのブロックを記憶媒体か ら取り出し、これらブロックを最大でＮ_maxなる複数のデータストリームの形 でユーザに供給するシステムであって、各データストリームは毎秒Ｒ_maxデー タ要素なる同一の最大消費率を有し、前記記憶媒体は少なくとも毎秒Ｎ_max＊ Ｒ_maxデータ要素なる帯域幅を有し、該記憶媒体が複数の記憶ユニットを有す るようなシステムにおいて、 ブロックの所定の選択群が、該選択群の個々のブロックが全体として少なく とも２つの異なる且つ実質的にランダムに選択された記憶ユニットに記憶され ることにより、前記記憶媒体に多重に記憶され、 前記システムが、 前記データストリーム用のブロックの前記記憶媒体からの読み取りを、各ブ ロックに対して、当該ブロックが記憶される全ての記憶ユニットの対応する組 から当該ブロックが読み取られるべき１つの記憶ユニットを選択すると共に、 対応する読取要求を該選択された記憶ユニットに割り当てることにより制御す るようなスケジューラであって、該記憶ユニットを前記組から前記複数の記憶 ユニットの負荷がバランスするように選択するスケジューラと、 ブロック読取要求に応答して、対応するブロックを前記割り当てられた記憶 ユニットから読み取り、対応するデータストリームでユーザに供給する読取器 と、 を有していることを特徴とするシステム。 ２．請求項１に記載のシステムにおいて、前記スケジューラは、データストリー ム用のブロックを取り込む要求に応答して、既に割り当てられたブロック読取 要求から生じる最低の負荷をその時点で有しているような記憶ユニットを前記 対応する組から選択することを特徴とするシステム。 ３．請求項１に記載のシステムにおいて、前記スケジューラは前記複数の記憶ユ ニットの負荷を、巡回的に 次のサイクル内で読み取られるべきブロックの群を決定し、 該群の全てのブロックに対して、割り当てられたブロック読取要求から生じ る前記複数の記憶ユニットの負荷がバランスされるように、前記選択及び割り 当てを実行し、 前記読取器に前記割り当てられた記憶ユニットから対応するブロックを読み 取らせる、 ことによりバランスさせることを特徴とるシステム。 ４．請求項３に記載のシステムにおいて、前記スケジューラは前記群のブロック を順番に処理することにより前記選択及び割り当てを実行すると共に、各ブロ ックに対して、 前記群のブロックに対して既に割り当てられているブロック読取要求から生 じる最低の負荷をその時点で有している記憶ユニットを前記対応する組から選 択し、 対応するブロック読取要求を前記選択された記憶ユニットへ割り当てる、 ことを特徴とするシステム。 ５．請求項３に記載のシステムにおいて、前記スケジューラは、前記群のブロッ クの各々のブロックに対して、予備的な記憶ユニットを選択すると共に対応す るブロック読取要求を該選択された予備的な記憶ユニットに割り当て、更に前 記スケジューラは、前記群のブロックを順番に処理すると共に各ブロックに対 して、 前記対応する組から、前記群のブロックに既に割り当てられているブロック 読取要求から生じるその時点で最低の負荷を有する記憶ユニットを選択し、 対応するブロック読取要求を上記選択された記憶ユニットに割り当てる、 ことにより、所定の条件が満たされるまで反復的に記憶ユニットを再選択する と共に対応するブロック読取要求を再割り当てすることを特徴とするシステム 。 ６．請求項５に記載のシステムにおいて、前記条件が、前記記憶ユニットの少な くとも１つの最大負荷が前回の反復の終了時における前記記憶ユニットの少な くとも１つの最大負荷と同一であることであることを特徴とするシステム。 ７．請求項３に記載のシステムにおいて、前記スケジューラは、前記群のブロッ クの各々のブロックに対して、予備的な記憶ユニットを選択すると共に対応す るブロック読取要求を該選択された予備的な記憶ユニットに割り当て、更に前 記スケジューラは、前記群のブロックに対して、 ブロック読取要求の前記予備的割り当てから生じる最大負荷をｋ単位だけ低 下させることができるか否かを、 ノードｎ_iのネットワークを経るソースからドレインへの最大フローを計 算することにより最大フロー問題を解き、ここで、各記憶ユニットｓ_iに対 しては対応するノードｎ_iが定義され、前記ソースはmax(k+l_i-l_max，0)なる 容量を持つ対応する弧を介して各ノードｎ_iに接続されているものとし、こ こで、ｌ_iはｓ_iに予備的に割り当てられたブロック読取要求から生じる記憶 ユニットｓ_iへの負荷に対応すると共にｌ_max＝max{l_i}が成り立ち、各ノー ドｎ_iは、ｓ_i及びS_jの両方に記憶されると共に対応するブロック読取要求が ｓ_iに割り当てられているようなブロックの数に対応する容量を持つ対応す る弧を介してｎ_j（ｎ_i≠ｎ_j）に接続され、各ノードｎ_iはmax(l_max-l_i-k，0 )なる容量を持つ対応する弧を介して前記ドレインに接続されているものと し、 算出された前記ネットワークを経る最大フローが、前記ソースから各ノー ドｎ_iへのフローが_max(k+l_i-l_max，0)に等しいようなものであれば、前記最 大負荷はｋ単位だけ低下させることができると判定する、 ことにより判定し、 前記最大負荷をｋ単位だけ低下することができる場合は、結果として算出さ れたｎ_iからｎ_jへのフローに等しいようなブロック読取要求の数をｓ_iからｓ_j （ｓ_i≠ｓ_j）に再割り当てする、 ことにより記憶ユニットを再選択すると共に対応するブロック読取要求を再割 り当てすることを特徴とするシステム。 ８．請求項３に記載のシステムにおいて、前記スケジューラは、前記群のブロッ クの各々のブロックに対して、予備的な記憶ユニットを選択すると共に対応す るブロック読取要求を該選択された予備的な記憶ユニットに割り当て、更に前 記スケジューラは、前記群のブロックに対して、反復的に、 ｓ_i上の負荷が前記複数の記憶ユニットの最大負荷ｌ_maxに等しいような記 憶ユニットを選択し、ここで、該負荷は現在割り当てられているブロック読取 要求から生じるものとし、 ｓ_iからｌ_max−１未満の負荷を持つ記憶ユニットｓ_jへの経路が存在するか 否かを判定し、ここで、前記経路はｓ_i＝ｓ_p1及びｓ_j＝ｓ_p1とした場合一連の 記憶ユニットｓ_p1，ｓ_p2，…，ｓ_p1により形成され、ｋが１からｌ−１までの 範囲である場合に各対ｓ_pk，ｓ_p(k+1)に関してブロック読取要求をｓ_pkからｓ _p(k+1)に再割り当てすることができるものとし、 経路が存在する場合に、１からｌ−１の範囲のｋに対して、ブロック読取要 求をｓ_pkからｓ_p(k+1)に再割り当てする、 ことにより記憶ユニットを再選択すると共に対応するブロック読取要求を再割 り当てすることを特徴とするシステム。 ９．請求項１に記載のシステムにおいて、前記ブロックが複数のタイトルに関係 し、各タイトルが一連のデータブロックを有すると共に所定の多重係数に関連 付けられ、１つのタイトルの多重係数が該タイトルに関して前記記憶媒体に記 憶されたブロック数と該タイトルのブロック数との比に関するものであること を特徴とするシステム。 １０．請求項９に記載のシステムにおいて、１つのタイトルの前記多重係数は、 当該タイトルの個々のブロックが前記記憶媒体に何重に記憶されているか、及 び／又は当該タイトルのブロックの何の割合が前記記憶媒体に多重に記憶され ているかを決定することを特徴とするシステム。