(57)【特許請求の範囲】
【請求項１】
オーディオ及び／又はビデオデータのようなデータのブロックを記憶媒体から取り出し、これらブロックを最大でＮmaxなる複数のデータストリームの形でユーザに供給するシステムであって、各データストリームは毎秒Ｒmaxデータ要素なる同一の最大消費率を有し、前記記憶媒体は少なくとも毎秒Ｎmax＊Ｒmaxデータ要素なる帯域幅を有し、該記憶媒体が複数の記憶ユニットを有するようなシステムにおいて、
ブロックの所定の選択群が、該選択群の個々のブロックが全体として少なくとも２つの異なる且つ実質的にランダムに選択された記憶ユニットに記憶されることにより、前記記憶媒体に多重に記憶され、
前記システムが、
前記データストリーム用のブロックの前記記憶媒体からの読み取りを、各ブロックに対して、当該ブロックが記憶される全ての記憶ユニットの対応する組から当該ブロックが読み取られるべき１つの記憶ユニットを選択すると共に、対応する読取要求を該選択された記憶ユニットに割り当てることにより制御するようなスケジューラであって、該記憶ユニットを前記組から前記複数の記憶ユニットの負荷がバランスするように選択するスケジューラと、
ブロック読取要求に応答して、対応するブロックを前記割り当てられた記憶ユニットから読み取り、対応するデータストリームでユーザに供給する読取器と、を有し、
前記スケジューラは、
前記複数の記憶ユニットの負荷を、巡回的に
次のサイクル内で読み取られるべきブロックの群を決定し、
該群の全てのブロックに対して、割り当てられたブロック読取要求から生じる前記複数の記憶ユニットの負荷がバランスされるように、前記選択及び割り当てを実行し、
前記読取器に前記割り当てられた記憶ユニットから対応するブロックを読み取らせること、
によりバランスさせ、
前記群のブロックの各々のブロックに対して、予備的な記憶ユニットを選択すると共に対応するブロック読取要求を該選択された予備的な記憶ユニットに割り当て、
前記群のブロックを順番に処理すると共に各ブロックに対して、
前記対応する組から、前記群のブロックに既に割り当てられているブロック読取要求から生じるその時点で最低の負荷を有する記憶ユニットを選択し、
対応するブロック読取要求を上記選択された記憶ユニットに割り当てること、
により、所定の条件が満たされるまで反復的に記憶ユニットを再選択すると共に対応するブロック読取要求を再割り当てする、
ことを特徴とするシステム。
【請求項２】
請求項１に記載のシステムにおいて、前記条件が、前記記憶ユニットの少なくとも１つの最大負荷が前回の反復の終了時における前記記憶ユニットの少なくとも１つの最大負荷と同一であることであることを特徴とするシステム。
【請求項３】
請求項１に記載のシステムにおいて、前記スケジューラは、前記群のブロックの各々のブロックに対して、予備的な記憶ユニットを選択すると共に対応するブロック読取要求を該選択された予備的な記憶ユニットに割り当て、更に前記スケジューラは、前記群のブロックに対して、
ブロック読取要求の前記予備的割り当てから生じる最大負荷をｋ単位だけ低下させることができるか否かを、
ノードｎiのネットワークを経るソースからドレインへの最大フローを計算することにより最大フロー問題を解き、ここで、各記憶ユニットｓiに対しては対応するノードｎiが定義され、前記ソースはmax（k+li-lmax, 0）なる容量を持つ対応する弧を介して各ノードｎiに接続されているものとし、ここで、ｌiはｓiに予備的に割り当てられたブロック読取要求から生じる記憶ユニットｓiへの負荷に対応すると共にｌmax＝max{li}が成り立ち、各ノードｎiは、ｓi及びSjの両方に記憶されると共に対応するブロック読取要求がｓiに割り当てられているようなブロックの数に対応する容量を持つ対応する弧を介してｎj（ｎi≠ｎj）に接続され、各ノードｎiはmax（lmax-li-k, 0）なる容量を持つ対応する弧を介して前記ドレインに接続されているものとし、
算出された前記ネットワークを経る最大フローが、前記ソースから各ノードｎiへのフローがmax（k+li-lmax, 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）に再割り当てする、
ことにより記憶ユニットを再選択すると共に対応するブロック読取要求を再割り当てすることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶媒体からオーディオ及び／又はビデオデータのようなデータのブロックを取り出し、これらブロックを最大でＮmaxなる複数のデータの流れ（データストリーム）の形でユーザに供給するようなシステムであって、各データストリームが毎秒Ｒmaxデータ要素なる同一の最大消費率を有し、前記記憶媒体が少なくとも毎秒Ｎmax＊Ｒmaxデータ要素なる帯域幅を有し、該記憶媒体が複数の記憶ユニットを有するようなシステムに関する。
【背景技術】
【０００２】
この種のシステムは、マルチメディアサーバ、もっと特定的にはビデオオンデマンドサーバ又は準ビデオオンデマンドサーバに使用されている。このようなシステムにおける一般的な要件は、連続した途切れのないデータストリームを各活動状態ユーザに供給することである。典型的には、データはハードディスクのような通常の記憶媒体から読み取られ、これらディスクはＲＡＩＤシステムのようなディスクアレイとして構成されている。一般的に、固定消費率システムと可変消費率システムとの間の区別がなされている。固定消費率システムにおいては、データは典型的には固定レートのデータストリームとしてユーザに供給される。通常、該システムにおける各データストリームに関してはレートは同一である。このようなシステムの一例は準ビデオオンデマンドシステムであり、該システムにおいては複数の映画を並列に再生することができると共に、同一の映画を数重に並列に再生することができ、その場合、例えば５分毎又は１５分毎のように規則的に同一の映画の新たなコピーが開始されるようになる。可変消費率システムにおいては、ユーザがデータを消費するレートは時間にわたり変化する。典型的には、各ストリームに対して最大消費率を規定することができる。実際には、ストリームを異なる最大消費率（例えば、オーディオストリームに対して或る最大値を、合成されたビデオ及びオーディオストリームに対して他の最大値を）で効率的に処理することもできるが、通常は全てのストリームに対して同一の最大消費率が使用される。可変消費率システムは、例えば、ポーズ又はスローモーションのようなＶＣＲ的な機能を扱うシステム、又はMPEG-2のような可変ビットレートのデータ圧縮方法を使用するシステム用に使用される。
【０００３】
ユーザに対してデータを連続したデータストリームとして供給するために、ディスクからデータを読み取るための特別なスケジューリング構成が、読み取られたデータを該データがユーザに供給される前に一時的にバッファする適切な構成と共に必要である。固定消費率システムの場合は、典型的には、各ストリームに対して固定の規則的な間隔で、一定量（１周期継続するに十分な）のデータが読み取られバッファに記憶される。可変消費率システムにおいては、異なるストリームがバッファの所定のブロックを異なる時点で空にすることがあり得る。典型的には、間隔の間に、データのブロックに対して余裕のあるバッファのストリームに関してのみデータが読み取られる。他のストリームは飛び越される。結果として、データを読み取るための間隔の持続時間は可変となり、全ての活動状態ストリームが新たなデータブロックを必要とするような状況により制限されることとなる。
【０００４】
全てのデータストリームが最大データレートで消費する場合に必要とされるような大きなディスク帯域幅を保証するために、データはアレイ内の全てのディスクにわたって分割（ストライプ）される。特に可変データレートシステムに関しては、このことは各データブロックを全ディスクにわたって、該ブロックを読み取る要求が上記ディスクの各々へのディスクアクセスを意味するように、分割することにより達成される。結果として、これらのディスクの負荷は最適にバランスされる。
【０００５】
通常、ディスクアレイ内のディスクの数は、並列に扱われるデータストリームの数に鑑みて所要の帯域幅により決定される。従って、ディスクの数はデータストリームの最大数と共に線形に増加する。ディスクへのアクセスの有効性がおおよそ一定に維持されるのを保証するために、１つのデータストリームのために個々のディスクから読み取られるブロックの大きさは同一に維持されねばならない（ディスクのあまりにも小さいブロックの読み取りは、特に該大きさがトラックの大きさ以下になると、オーバーヘッドを増加させる）。結果として、全ディスク上にストライプされた累積されたブロックの大きさは、ディスクの数に伴って、従ってデータストリームの最大数と共に、線形に増加する。この結果、バッファの大きさもデータストリームの最大数と共に線形に増加する。各データストリームに対してバッファが必要であるから、合成効果は、バッファの全体の大きさがデータストリームの最大数に対して略２次的に依存し、バッファの価格を、特に多数のデータストリームを扱うシステムに対して、支配的な要因にさせてしまう。他の不利な効果は、当該システムの新たなデータストリームを活性状態にさせる応答時間が略線形に増加する点にあり、その理由は、バッファを再充填するに要する時間間隔が線形に増加し、このような間隔内では新たなユーザが当該システムに参加できないからである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、上述したような種類のシステムであって、バッファの価格が、扱われるデータストリームの最大数と共に線形に増加するようなシステムを提供することにある。他の目的は、応答時間が、扱われるデータストリームの最大数に無関係に略同一に維持されるようなシステムを提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明によるシステムは、ブロックの所定の選択群が、該選択群の個々のブロックが全体として少なくとも２つの異なる且つランダムに選択された記憶ユニットに記憶されることにより、前記記憶媒体に多重に記憶され、該システムが、前記データストリーム用のブロックの前記記憶媒体からの読み取りを、各ブロックに対して、当該ブロックが記憶される全ての記憶ユニットの対応する組から当該ブロックが読み取られるべき１つの記憶ユニットを選択すると共に、対応する読取要求を該選択された記憶ユニットに割り当てることにより制御するようなスケジューラであって、該記憶ユニットを前記組から前記複数の記憶ユニットの負荷がバランスするように選択するスケジューラと、ブロック読取要求に対応して、対応するブロックを前記割り当てられた記憶ユニットから読み取り、応答するデータストリームでユーザに供給する読取器と、を有していることを特徴としている。
【０００８】
１つのブロックが少なくとも２つの異なる記憶ユニットに記憶されることを保証することにより、上記スケジューラは、再生の間に上記ブロックが何の記憶ユニットから読み取られるかを選択する選択度を有する。これにより、スケジューラは記憶ユニットの負荷がバランスするように記憶ユニットを選択することが可能となる。各ブロックをランダムに選択された記憶ユニットに記憶することにより、可変レートシステムに関してさえも、再生の間に比較的一様な負荷を達成することができる。このような可変レートシステムに関して、さもなければ、活性状態ストリームに関して個々の記憶ユニットに時間的にどのように負荷が発生するかを予測することは、困難又は不可能でさえある。単純なシステムでは、全てのタイトルの全てのブロックが当該システムに２度、即ち当該システムの２つの異なる記憶ユニットに、記憶される。ブロックの選択群は、他の例としては、全ブロックの一部であってもよく、その場合残りのブロックは１度だけ記憶される。
【０００９】
本発明によるシステムにより提供される解決策は、帯域幅と違って記憶媒体の容量は主要な決定要因ではなく、ハードディスクの容量は平均して帯域幅（典型的には年４０％の増加）より高いレート（典型的には、年６０％）で増加しているので、斯かる容量は益々決定要因ではなくなるという見通しから有利である。２年以内に典型的なディスクが２５Ｇバイトの記憶容量及び８５Ｍbits/secなる保証されたデータレートを持つようになると仮定すると、以下の２つの筋書きを描くことができる。第１の筋書きでは、本発明によるシステムのビデオオンデマンド版は、映画館におけるように、２０までの範囲の映画を最大で１０００人のユーザに提供するように使用される。これら映画はMPEG2を用いて４Ｍbits/secなる平均レートで符号化される。映画が平均して９０分の長さを有していると仮定すると、映画当たり90*60*4.106＝21.6*109bits＝2.5Ｇバイトなる合計記憶容量が必要とされ、結果として、必要とされる全記憶容量は約５０Ｇバイトとなる。全てのブロックが２度記憶されるとすると、容量は約１００Ｇバイトでなければならず、これは４ないし５個のディスクに相当する。同時に１０００人のユーザを扱うことができるには、４０００Ｍbits/secなる合計の保証された帯域幅が必要とされ、これは４７個のディスクに相当する。このようなシステムにおいて２３５を越える映画を記憶する必要がある場合にのみ、上記ディスクの容量は妥当なものとなる。本発明によるシステムが、ホテルにおいて典型的であるように、１００人までのユーザに対して映画の選択を提供するよう使用されるような、もっと緩やかな第２の筋書きでは、帯域幅に関しては５つのディスクが必要となる。全ブロックの完全な二重化の場合は、上記５つのディスクは２３の映画を記憶することができ、これは斯様なシステムにおいて通常提供されるよりも多い。
【００１０】
更に、本発明は、データブロックは多重に記憶されてはいるが、典型的なシステムにおいては実際には、本発明によるシステムでは従来のシステムにおけるより少ない記憶ユニットしか必要とされないという洞察に基づいている。既に前記筋書きで示したように、帯域幅が殆どの実際のシステムに関しては制限要因であり、益々そうなるであろう。データブロックを個々の記憶ユニットにわたって最早分割（ストライプ）するのではなく、代わりに、１つのディスクから全体のブロックを読み取ることにより、記憶ユニットからデータを読み取る効率が改善される。前記第１の筋書きでは、丁度２％を越えるような効率の改善の結果、既に、ディスクが節約される。
【００１１】
本発明による本実施例の他の利点は、当該システムの強さが改善される点にある。一例として、１２個のディスクのうちの１つが故障し、全ブロックが二重化されているとすると、前記スケジューラは、平均し１０個のブロックのうちの１つに関しては、当該ブロックを何のユニットから読み取るべきであるかを選択することができないであろう。結果として１つの記憶ユニットの平均負荷は５．３％増加し、残りの記憶ユニットの１つの最大負荷も略同じような割合で増加するであろうことが分かる。システムが最大数のユーザによっては使用されないような殆どの状況では、これにより、故障したディスクを交換する十分な機会が与えられる。パリティディスクのような他の手段は必要とされない。
【００１２】
更に、該システムの拡張性が増加する。もし追加の帯域幅（又は記憶容量）が必要な場合は、追加のディスクを当該システムに付加することができる。次に、既に存在するディスクから新たなディスクへブロックを移動する必要がある。移動されるべきブロックは、ランダムに選択することができる。典型的には、移動されるべきブロックの数は、略、１つのディスク上に記憶されるブロックの平均数であろう。本発明によるシステムにおいては、当該システムの動作に対する影響は極めて少ない。５０個のディスクのシステムにおいては、ブロックの２％だけしか移動する必要がない。他の全てのブロックは全く影響を受けない。また、移動作業は、ブロックを移動させるための容量が利用可能な場合に何時でも実行することができる（即ち、該作業は当該システムが動作している間にバックグラウンドで実行することができる）。ブロックが上記の新たなディスクに移動されるにつれて、当該システムの容量は、最終的に所望の数のブロックが該新たなディスクに移動されてしまうまで、緩やかに増加する。これとは対照的に、ブロックが全ディスクにわたりストライプされている典型的なシステムにおいては、全てのディスクがアクセスされねばならず、新たなディスク上にデータを記憶するためにブロックは再構築さえされなければならない。このような大きな作業は、通常、当該システムがオフライン状態にある間になされねばならない。
【００１３】
ロサンゼルスのような町を経る建築学的歩行のような三次元対話型アプリケーション用のディスク利用型記憶サーバが、Compocon’96（41stIEEE Computer Society International Conference, Santa Clara, 25-28Febr., 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 Reassignment algorithm）と呼ぶが、上記初期割り当ては線形割り当てアルゴリズム（Linear Assignment algorithm）により実行される。
【００４０】
本発明による他の実施例においては、スケジューラ１７０は当該群のブロックに関するブロック読取要求を、近似最大フロー問題（analogous maximum flow problem）を解くことから導出される割当に従って割り当てる。第３図のステップ３１０と同様に、スケジューラ１７０は当該群のブロックの各々に対して予備的な記憶ユニットを選択し、この予備的に選択された記憶ユニットに対して対応するブロック読取要求を割り当てることにより、先ず初期割り当てを実行する。近似最大フロー問題は以下のように定義される。各記憶ユニットｓiに対して対応するノード（頂点）ｎiを含むようなノードｎiのネットワークが定義される。このネットワークは、ソースノード（ｓ）及びドレインノード（又はシンクノード）（ｄ）も有している。各ノードｎiは対応する弧（有向辺）を介してｎj（ｎi≠ｎj）に接続されており、該弧はｓi及びｓjの両方に記憶され且つ対応するブロック読取要求がｓiに割り当てられているようなブロックの数に対応する容量を有する。従って、該容量はｓiからｓjに再割り当てすることができるブロックの数を示している。第４ａ図は、ノードｎ1ないしｎ3により各々表された３つの記憶ユニットｓ1ないしｓ3に関するネットワークを図示している。この例では、記憶ユニットｓ1ないしｓ3の各初期負荷が１５、１２及び１０であると仮定されている（対応ノードの中心に示されているように）。或るノードから他のノードへの弧の傍には、これらノードに対応する記憶ユニットの間で幾つのブロック読取要求を再割り当てすることができるかが示されている（例えば、本例では、３個のブロックをｓ1からｓ2に、２つのブロックをｓ2からｓ1に再割り当てすることができる）。前記問題は、記憶ユニットの最大負荷ｌmaxをｋ単位だけ低下させることができるかを判断することができるというように定義され、ここで上記負荷はブロック読取要求のこれら記憶ユニットへの前記予備的割り当ての結果である。この目的のため、ソースｓがmax（k＋li-lmax, 0）なる容量の対応する弧を介して各ノードｎiに接続される。この式において、ｌiは、予備的にｓiに割り当てられたブロック読取要求の結果としての記憶ユニットｓiの負荷に対応する。結果として、最大負荷ｌmaxは、全記憶ユニットにわたるｌmax＝max{ｌi}により与えられる。第４ａ図の例では、ｌmaxは１５である。更に、各ノードｎiはmax（ｌmax-li-k, 0）なる容量を持つ対応する弧を介してドレインｄに接続されている。第４ａ図の例では、ｋは２に選択され、前記ソースから各ノードへの及びこれらノードから上記ドレインへの対応する容量が示されている。次に、当該ネットワークを経る最大フローが計算される。第４ｂ図は、算出されたフローの可能性のある結果を示している。各弧の隣に（第４ａ図では容量が示されたのとは異なり）フローが示されている。弧内のフローは該弧の容量を超えることはできない。ソースｓから各ノードへの弧の容量は、ソースｓから各ノードへの算出されたフローが当該容量に一致する（即ち、容量が完全に使用される）場合及びこのような場合にのみ、上記最大負荷がｋ単位だけ確かに低下させることができるというように、定義される。一例として、或るノードの負荷が最大負荷ｌmaxに等しい場合は、容量max（k+li-lmax, 0）＝max��k＋lmax-lmax, 0）＝ｋを反映して、該ノードの負荷をｋ単位だけ低下させることが望ましい。同様に、ｌmax−１なる負荷を持つノードに関しては、容量max（k＋lmax-1-lmax, 0）＝max（k-1, 0）＝k-1（ｋ＞＝０と仮定する）を反映して、該負荷はｋ−1単位だけ低下させることが望ましい。上記式は、ｌmax−ｋ（又は、それよりもっと低い）なるノードの負荷は低下させる必要がないことも表している。同様に、各ノードからドレインｄへの弧の容量は、当該ノードへの負荷を、ｌmax−ｋなる所望の最大負荷を越えることなく、どれだけ多くの単位だけ増加させることができるかを表している。各ノードからドレインへの算出されたフローは、当該システムがいっぱいには負荷されていないことを反映して（第４ｂ図ではｎ3からドレインへのフローは１であるのに対し、その容量は３であり、ｎ3への負荷は未だ更に２つのブロックまでは増加することができることを示している）、各容量よりは低いであろうことが分かるであろう。算出された最大フローが最大負荷をｋ単位だけ低下することができることを示している場合は、スケジューラ１７０は、結果として算出されたｎiからｎjへのフローに等しいようなブロック読取要求の数をｓiからｓj（ｓi≠ｓj）へ再割り当てする。第４ｃ図は、第４ｂ図に示される算出されたフローによる再割り当てを示している。当該ネットワークを介しての最大フローを計算するには、よく知られているフォード＆ファルカーソン（ford&Fulkerson）アルゴリズムのような如何なる好適なアルゴリズムも使用することができる。最大フロー理論の詳細は、１９８９年のケンブリッジ大学出版の第９６〜１０６頁にアラン・ギブソンにより掲載された”アルゴリズム的グラフ理論”に記載されている。
【００４１】
良好にバランスされたシステムの記憶ユニットに対する最大負荷は、（境界を含み）これら記憶ユニットへの切り上げ（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）に再割り当てされることができる（ｋは１からｌ−１の範囲である）。このような経路が存在するか否かの判断には、如何なる好適なアルゴリズムも使用することができる。一例として、記憶ユニットｓ1ないしｓ3（ノードｎ1ないしｎ3により表されている）に関して第４図に図示したようなグラフを形成することができ、該グラフを介してツリー検索を実行することができる。経路が存在した場合は、ステップ５４０においてスケジューラ１７０は、１からｌ−１の範囲のｋに対してブロック読取要求をｓpkからｓp（k+1）に再割り当てする。次に、該手順はステップ５２０において再開される。その時点で、ｓiの負荷は１だけ低下されている。他の記憶ユニットが依然としてｓiが前に有していたのと同様の最大負荷を有している場合は、これらユニットのうちの１つがステップ５２０において選択される。ｓiが上記最大負荷を有する唯一の記憶ユニット（又は最後の記憶ユニット）であった場合は、これは自動的に当該システムの最大負荷を１だけ低下させたことになるであろう。結果として、前よりは１だけ低下しているが、ｓiは今や再び最大負荷を有する（通常、幾つかの他の記憶ユニットも該最大負荷を有する）ことになる。この処理は、記憶ユニッ��に対して負荷を低下させるような経路を見つけることができなくなるまで繰り返される。
【００４３】
本発明による３つのアルゴリズム、即ち線形割り当て（Linear Assignment;LA）、線形再割り当て（Linear Reassignment;LR）及び最大フロー割り当て（Maximum Flow Assignment;MFA）の振る舞いがシミュレーションされた。ｍ＝５〜３０個のディスクに関して（５のステップで）、シミュレーションが実行され、ここで更に活動ストリームの数が、ストリームの数をディスクの数で割った値が５〜３０（５のステップで）の範囲となるように、変化された。従って、当該システムにおける活動ストリームの数は２５〜９００の範囲である。下記の表は、該シミュレーションの1,000,000回の連続する掃引に関する結果を示している。全ブロックが完全に二重化され、各掃引においてデータブロックが各活動ストリームに対して取り込まれ、全ストリームが最大レートで連続的に消費する最悪状況の筋書きを反映した。この表に示される３つの結果の各群のうち、上の結果はＬＡアルゴリズムに関係し、真ん中の結果はＬＲアルゴリズムに関係し、下の結果はＭＦＡアルゴリズムに関係するものである。各結果は最大の観測された負荷を示し、ここで該最大負荷が観測された回数が括弧内に示されている。
【表１】
0004151991.tif 000002
これらシミュレーションは、比較的単純なＬＲアルゴリズムで以て、最大負荷が観測される回数はＭＦＡアルゴリズムの場合よりも多いが、殆ど全ての状況においてＭＦＡアルゴリズム（該アルゴリズムは達成可能な最良の負荷バランスを提供する）で得られるのと同様の最大負荷を伴うような良好な結果が達成され得ることを示している。また、これらシミユレーションは、ブロックを完全に二重化すると共にこれらブロックをランダムに記憶することにより、特にＬＲ及びＭＦＡアルゴリズムの場合に、殆どのシミュレーションされた状況に対して、下限である平均負荷より３ないし１０％だけしか高くないような最大負荷を達成することができることを示している。かくして、達成することができるバランスは極めて良好である。
【００４４】
下記の表は、同一のシミュレーションに関して観測された平均最大負荷を示し、特に大きなシステムに関しては、最大負荷が平均して全ディスクの平均負荷に近づいていることを確認している。
【表２】
0004151991.tif 000003
【００４５】
第６図は、１５個のディスクと２２５個の活性状態データストリームとの場合（平均負荷はディスク当たり１５ストリームとなる）の、1,000,000回の連続した掃引に対するＭＦＡアルゴリズムのシミュレーションされた結果を示し、ここで多重係数は１（多重化無し）から２（完全な二重化）まで変化された。１．２５なる多重係数（２５％の二重化）は、４ブロックのうちの１つが二重化されたことを示している。該図は、何回（垂直方向）最大負荷（水平方向）が観測されたかを示している。各ブロックが１回だけしか記憶されていないようなシステム（０％二重化）に関しては、該図は観測された最大負荷が略１８ストリーム／ディスクと２８ストリーム／ディスクとの間にあり、３０を優に越えるような最大負荷が時々生じることを示している。このような構成が採られると、斯様なシステムはディスク当たり約３０ストリームを処理することができるように設計値が決められねばならないことになるが、平均負荷はディスク当たり１５ストリームに過ぎないから、２なる係数分過剰設計となることが分かるであろう。５０％なる多重係数のシステムに関しては、観測された最大負荷は略１５ストリーム／ディスクと１８ストリーム／ディスクとの間にある。このようなシステムを例えば２０ストリーム／ディスク用に設計すること（３３％の過剰設計）は、決して矛盾（即ち、２０を越えるような最大負荷）を生じることはないであろう。従って、第６図は、記憶容量が制限要因であるようなシステムに対しては、１００％未満の二重化程度で良好な結果が達成されることを示している。シミュレーションは、約６０ないし８０％の範囲の二重化程度で既に良好な結果が得られることを示している。そのような場合、過剰設計は２５％未満であればよく、もっと大きなシステムでは、それより大幅に低くてもよい。１００％の二重化の場合は、ＬＲ及びＭＦＡアルゴリズムに対しては、１５個のディスクを備え、ディスク当たり１６ストリームを扱うように設計された（６．７％の過剰設計）システムは、シミュレーションにおいて何の問題も観測されずに、２２５のストリーム（平均で、１５ストリーム／ディスク）を扱うことができる。実際の状況では、結果はもっと良いことが理解された。上記シミュレーションは、全てのストリームが最大消費率でデータを消費し、ディスクの効率が特定された最低であるような最悪の状況を仮定して実行された。実際には、ディスクの効率はもっと良好であり、可変消費率システムの場合は、平均消費率は最大消費率よりも大幅に低いであろう。結果として、特に大きなシステムに関しては、過剰設計の程度は更に低下させることができる。
【図面の簡単な説明】
【００４６】
【図１】本発明によるシステムのブロック図を示す。
【図２】再生のために記憶ユニットを選択する線形順次方法のフローチャートを示す。
【図３】再生のために記憶ユニットを選択する反復線形順次方法のフローチャートを示す。
【図４】ノードのネットワークを経る最大のフローを解くことに基づいて再生のための記憶ユニットを選択する方法を図示する。
【図５】再生のために記憶ユニットを選択する他の反復手順を図示する。
【図６】ブロックの多重化無しから全ブロックの完全な二重化までの多重係数の範囲に対するシミュレーションされた結果を示す。
【図１】
0004151991.tif 000004
【図２】
0004151991.tif 000005
【図３】
0004151991.tif 000006
【図４ａ】
0004151991.tif 000007
【図４ｂ】
0004151991.tif 000008
【図４ｃ】
0004151991.tif 000009
【図５】
0004151991.tif 000010
【図６】
0004151991.tif 000011