JPH0926854A - データを格納し供給するサーバー・システム - Google Patents

データを格納し供給するサーバー・システム

Info

Publication number
JPH0926854A
JPH0926854A JP8095315A JP9531596A JPH0926854A JP H0926854 A JPH0926854 A JP H0926854A JP 8095315 A JP8095315 A JP 8095315A JP 9531596 A JP9531596 A JP 9531596A JP H0926854 A JPH0926854 A JP H0926854A
Authority
JP
Japan
Prior art keywords
data
chunks
disk drive
disk
chunk
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP8095315A
Other languages
English (en)
Inventor
Yitzhak Birk
イザック・ビルク
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
HP Inc
Original Assignee
Hewlett Packard Co
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Hewlett Packard Co filed Critical Hewlett Packard Co
Publication of JPH0926854A publication Critical patent/JPH0926854A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • G06F11/1076—Parity data used in redundant arrays of independent storages, e.g. in RAID systems
    • G06F11/1088—Reconstruction on already foreseen single or plurality of spare disks
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10—Digital recording or reproducing
    • G11B20/18—Error detection or correction; Testing, e.g. of drop-outs
    • G11B20/1803—Error detection or correction; Testing, e.g. of drop-outs by redundancy in data representation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N7/00—Television systems
    • H04N7/16—Analogue secrecy systems; Analogue subscription systems
    • H04N7/173—Analogue secrecy systems; Analogue subscription systems with two-way working, e.g. subscriber sending a programme selection signal
    • H04N7/17309—Transmission or handling of upstream communications
    • H04N7/17336—Handling of requests in head-ends

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Signal Processing (AREA)
  • Quality & Reliability (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Television Signal Processing For Recording (AREA)
  • Signal Processing For Digital Recording And Reproducing (AREA)
  • Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)

Abstract

(57)【要約】 【課題】 ビデオ・オンデマンド・システムのバッファ
リングの必要性を減らし、負荷のバランスおよび故障耐
性を向上させる。 【解決手段】 ビデオ・タイトル（映画）のデータかた
まりを格納するk個のディスクドライブのうち最も長い
待ち行列を持つものを判断し、その長さが所定値を越え
るとき、そのディスクからの読み出しに代えて、他のデ
ィスクからのデータおよびk+1番目のパリティ・ディス
クからのデータから当該ディスクから読み出すべきデー
タかたまりを、誤り訂正符号手法により再構築する。こ
うして最も混雑するディスクドライブをバイパスするこ
とができる。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明は、ビデオ記憶装置
サーバーに関し、より具体的には、データの多数の並行
ストリームを支援するビデオ・オンデマンド（即時応答
ビデオ）記憶装置サーバーに関する。
【０００２】
【従来の技術】ビデオ・オンデマンド（VOD）記憶装置
サーバーは、複数の磁気ディスク駆動機構を含み、デー
タの多数の並行ストリームを支援することを要求され
る。圧縮したビデオ・データでは、各ストリームのレー
トは、一つの磁気ディスク装置の維持された転送速度よ
り数倍遅い。記憶装置のコストが、VOD記憶装置サーバ
ーのコストの大きい部分であり、そして、並行ストリー
ムの数が大きいためにしばしば記憶装置サブシステムが
容量制限されるよりもバンド幅制限されるので、単位記
憶装置あたりのコストを最小にするためにディスクドラ
イブの最も効率的な利用を計ることが望ましい。したが
って、サーバーのスループットは、重要な設計ゴールで
ある。
【０００３】一般的に言って、VOD記憶装置サーバー
は、典型的には磁気ディスク駆動装置からバッファーメ
モリーにデータの「かたまり」を読み、それからバッフ
ァーメモリーの内容を通信ネットワークの上の転送先に
小さい「セル」で送る操作を行う。小さい「セル」の送
信は、「ストリーミング」と呼ばれる。ビデオ・ストリ
ームあたりのセルのレートは、そのストリームについて
のレートで決まる。ユーザがデータのストリームを見始
めるならば、付加的なデータを読んでいるとき、サーバ
は利用可能なバッファリングの量を越えてはならない
し、バッファーメモリーは空にならされてはならない。
実際、バッファーメモリーは、磁気ディスクから通信網
へのデータ転送をなめらかにする。
【０００４】ビデオ・データで、バッファリングのため
に必要な半導体メモリは、VOD記憶装置サーバーの全部
のコストの別の大きい部分である。それゆえに、必要な
バッファーメモリーの量を抑えることは、重要な設計ゴ
ールである。したがってまた、磁気ディスクの上のデー
タ配置とバッファーメモリーへのそのデータの検索のス
ケジューリングはVOD記憶装置サーバーの設計において
重要な重要な点である。具体的には、配置とスケジュー
リングが、並行ストリームの最大数、ユーザ要求への応
答時間、所与のストリームのためのかたまりが磁気ディ
スクから実際に読み出される速度の変動性およびディス
ク速度とストリーム速度の相違を隠す（マスクする）の
に必要なバッファリングの量を決める。
【０００５】ビデオ・データのための記憶装置の使用
は、他のアプリケーションでの記憶装置の使用とかなり
異なる。たとえば、科学的な計算または医学画像処理シ
ステムにおいては、単一のストリーム・レートの要求を
満足するためにディスクアレイが使用される。もう一つ
の例として、ディスクがオンライン・トランザクション
処理において使用されるとき、単位時間あたりの小さ
い、無関係なデータ・ブロックへのアクセスの数が最も
重要で、「なめらかさ」は意味を持たず、スループット
は二次的な重要性である。
【０００６】
【発明が解決しようとする課題】VOD記憶装置において
は、コスト、スループットおよびなめらかさが、重要な
設計上の考慮事項である。ユーザがなすビューイング
（視聴）の選択に関係なくすべてのディスクドライブの
転送バンド幅を利用することができるようにするためお
よび他の理由で、それぞれの映画を多くの、しばしば全
部のディスクドライブにわたって「縞状（ストライプ）
にする」のが一般的である。このため、映画の第１のか
たまりを第１のディスクドライブに、次のかたまりを次
のものに等等の記録を必要とし、最終的には、第１のも
のに戻り、別のラウンドを開始する必要があった。縞状
にすること（ストライピング）はよく知られており、
「負荷平衡」のためおよび単一の大きな要求のために転
送速度を最大にするための両方に使われてきた。かたま
りのサイズは、ディスクが、実際にデータ（読取りヘッ
ドを動かすのに対して）を転送することができる時間部
分を高く保つように選ばれている。しかし、かたまりの
サイズを増やすことは、バッファーメモリーの必要サイ
ズを増やすことになり、そして、新しいユーザ要求に対
してより長い応答時間を生じるかもしれない。
【０００７】多数のディスクドライブの使用は、ディス
ク故障によるシステム使用不能の問題を引き起こす。こ
の問題は、一つのディスクの故障がすべてのデータを利
用価値のないものにするので、複数のディスクドライブ
にわたってデータが損傷を受けることによって悪化す
る。この問題への解法は、一つの付加ディスクドライブ
を追加し、このディスクドライブに他のディスクのデー
タの「パリティ」を記録することである。この方法は、
RAID（Redundant Array of InexpensiveDisks、低コス
トのディスクの冗長な配列）として知られている。たと
えば、あらゆるディスクドライブの第１のビットを考慮
する。「1」の数が奇数であるならば、パリティ・ディ
スクの第１のビットの位置に「1」が記録され、さもな
ければ、「0」が記録される。このプロセスは、ディス
クの他のビットについても同様である。ディスク故障の
場合、故障しているディスクドライブが識別されると、
パリティ・ドライブおよび故障ドライブの役割を逆にし
て、パリティービットをつくるために使用したのと同じ
プロセスを使用することによって、故障したディスクが
含んだビットのそれぞれを、残りのディスクドライブの
対応するビットから再構築することができる。
【０００８】不良ディスクで運転を許すために、使用で
きるものから不良ディスクのデータを迅速に再構築する
ためにメモリに全ストライプを読み込まなければならな
い。全ストライプのデータがコンピュータによる処理に
必要とされるから、そうすることは多くのアプリケーシ
ョンにおいて自然である。データのかたまりの典型的な
サイズは、ビデオ視聴時間の1秒の十分のいくつかに対
応する。したがって、単にそれらが同じストライプに属
しているだけで多数のかたまりをバッファーメモリーに
読み込むことは、ストリームにつき長時間大量のメモリ
を拘束することになる。具体的には、ストリームあたり
のメモリの量は、パリティ・グループを形成しているデ
ィスクドライブの数に比例する。サーバが並行して生成
することができるストリームの数はディスクドライブの
数と比例するから、ストリームをバッファするのに必要
なメモリの全量は、ディスクの数とともに２次関数的に
増加する。サーバは数十または数百のディスクを含むこ
とがあるから、これは破滅的である。このように、メモ
リに全ストライプを読み込まなければならないことは、
ビデオ・サーバーにとって重大な問題である。
【０００９】RAID手法は、近年より大きい性能を得るた
めに修正されている。それでも、RAIDおよびその修正手
法は、まだ重大な欠点をもっている。
【００１０】RAIDへの一つの修正は、互い違いのアクセ
ス(staggered access)と呼ばれる。ここで、システムは
データを従来のRAIDにおけると同じ態様で配置するが、
異なるディスクへのアクセス予定は、調和して互い違い
にされる。この結果、それぞれのストリームのデータが
一度に決まった量ずつ供給され、ストリームあたりのバ
ッファ・サイズは一定である。この手法の一つの不利
は、それがディスク故障に効果的に耐えることができな
いということである。ディスク故障の場合、この手法
は、データのそれぞれのかたまりが二回（故障したディ
スクのデータを再構築するのを助けるために一度、伝送
の順番が来るとき一度）読取られることを必要とする
か、さもなければ従来のRAIDにおけると同じ大量のバッ
ファーメモリーが必要である。別の欠点は、異なるディ
スクへのアクセス予定の密な結合、および時を同じくし
たユーザ要求に起因する絶え間ない混雑、または異なる
ビデオ・ストリームの速度の小さな相違である。別の不
利益は、故障したディスクの内容を新しいディスクに再
構築することは、すべてのディスクの全バンド幅を消費
するほどものであるということである。
【００１１】RAIDへの別の修正は、区分化したRAIDとし
て知られている。ここでは、M個のディスクドライブが
サイズk+lの集合に区分される（k+1でMを分ける）。任
意の一つのRAIDのk+1個のディスクはすべて同時にアク
セスされるが、異なるRAIDへのアクセス予定は、時間内
に互い違いに配列される。kが十分に小さいならば、こ
の方式は大きいバッファーメモリーの必要性を和らげる
が、故障したディスクでは、ストリーミング容量が（k/
k+ 1）に落ち、そして、再構築が実効的にサーバーの全
バンド幅を消費しうることになる。また、互い違いのア
クセスについて触れられた絶え間ない混雑の問題がここ
でも生じる。
【００１２】さらに、規則的なデータ・レイアウトをも
ち、読み込み時にディスクの選択に真の「ゆるみ」がな
いすべての方式は、ユーザによって生成されるシナリオ
（視聴者の動作の間の相関）を記憶装置シナリオ（異な
るディスク上の負荷の間の相関）に直接変換することで
苦しむ。これが、持続する混雑問題を引き起こし、そし
て、そのような問題を起こるのを防ぐことは、一般に不
可能である。
【００１３】このように、負荷平衡および故障耐性を提
供するばかりでなく、混雑の持続性を最小にし、合理的
な量のバッファリングだけを必要とするデータ記憶装置
および検索技法に対する必要性がある。
【００１４】
【課題を解決するための手段】広く言うと、この発明
は、ディスクドライブ上のデータ・タイトル（たとえ
ば、映画）の非レギュラーの（たとえば、ランダムの）
データ・レイアウト、ディスクドライブのサブセットに
わたるデータの冗長性、および適応性負荷平衡のための
方法およびシステムに関する。この発明に従う記憶装置
サーバーは、混雑問題が持続することを防ぎ、バッファ
リングの必要性を減らし、負荷平衡および故障耐性を提
供する。この発明は、装置、システムまたは方法として
実施することができる。
【００１５】この発明に従ってデータを格納し供給する
サーバー・システムは、データを格納するための複数の
ディスク・ドライブ、間もなく供給すべきディスクドラ
イブからのデータの一部分を一時格納するためのバッフ
ァーメモリー、現在のパリティ・グループに属するデー
タを保持しているディスクドライブの少なくとも1つ
が、（そのディスクが、不良であるから、またはそれの
ためのすでに多くの待ち行列に入れられた読取り要求が
あるから）バイパスされうるように、複数の残りのディ
スクドライブからのデータの部分を使用して、ディスク
ドライブの少なくとも1つからのデータの部分を再構築
するための再構築ユニット、サーバー・システム（要求
のスケジューリングおよび待ち行列を含む）を制御する
ための制御ユニット、および、バッファーメモリーおよ
び再構築ユニットの片方または両方からのデータを出力
するための出力手段、を含む。好ましくは、サーバー・
システムはビデオ記憶装置サーバであり、格納されるデ
ータはビデオ・データである。
【００１６】方法として、この発明は、ディスクドライ
ブへのデータの格納、ディスクドライブのデータ・スト
リームの読み出し、またはその両方に関連する。ビデオ
・タイトル（例えば、映画）を複数のディスクドライブ
にこの発明に従って格納するための方法を、まず説明す
る。この方法は、ディスクドライブ・シーケンスを形成
するようディスクドライブに繰り返し命令し、記録され
るべきビデオ・タイトルを複数のデータのかたまりに分
割し、ビデオ・タイトルの一組の同じサイズの連続的な
データのかたまりを選び、ディスクドライブ・シーケン
スの一組のディスクドライブに一組のデータのかたまり
をそれぞれ記録し、データのかたまりの組について冗長
なかたまりを決め、そして、ディスクドライブ・シーケ
ンスの次のディスクドライブに冗長なかたまりを記録す
る。
【００１７】一般に、この方法は、映画をそれぞれがい
くつかの同じサイズのかたまりに分割されるブロックに
分割することを必要とする。これらのかたまりは、ビデ
オ・タイトルにおける出現の順にディスク・シーケンス
の連続したディスクに記録され、ゼロまたは「冗長な」
かたまりがその後に続く。このように、かたまりのサイ
ズ、かたまりの数、および冗長なかたまりの数は、ブロ
ックごとに変わりうる。冗長なかたまりの数のためのい
ろいろなオプション、およびそれらを利用する方法は、
誤り訂正符号の技術において知られている。
【００１８】この発明に従って、ディスクドライブから
データストリームを供給する方法を次に説明する。そこ
からデータストリームが読みとられるビデオ・データ
（例えば、映画）は、好ましくは、上述した記憶方法で
ディスクドライブに先に格納されていると仮定する。ビ
デオをディスクドライブに格納する際に、ビデオ・デー
タはブロックに分割され、各ブロックが一組のデータの
かたまりに分割されて、一組のディスクドライブに格納
される。さらに、データのかたまりのそれぞれの組につ
いて少なくとも一つの冗長なかたまりがディスクドライ
ブのもう一つに格納される。ビデオ・データのブロック
のそれぞれに関連するディスクドライブが、グループを
形づくる。この発明による検索または供給は、ディスク
ドライブのそれぞれについてのアクセス要求の待ち行列
を維持し、グループ内の待ち行列の待ち行列状態情報を
調べ、再構築かたまりに対応する待ち行列状態情報およ
びデータのかたまりの少くとも1つに対応する待ち行列
状態情報の両方に基づいて、その組の他のデータのかた
まりおよび関連した再構築かたまりから、その組のデー
タかたまりの少なくとも1つを選択的に再構築し、そし
て、転送先にそのデータかたまりを供給する。
【００１９】この発明は、データストリームの格納およ
び読出しについて従来の技法に対して多数の利点を提供
する。記録時でのディスクドライブの順位付けにおける
ランダム化は、ユーザによって誘発されるシナリオと記
憶システムのシナリオとの間の相関性を妨げる。このよ
うに、たとえ瞬間的な混雑が起こるとしても、持続する
ことはありそうにない。複製化(replication)の代わり
に「k+l」方式を使用することによって、記憶装置オー
バーヘッドは、1/kに減らされる。kのそれぞれのシーケ
ンスにおいて少なくとも最も長い待ち行列を避けること
ができることによって、一時的な混雑（不規則な記憶パ
ターンによる）を避けることができ、（新しい要求を最
も長い待ち行列に入れないことによって）そのような一
時的な混雑の見込みが著しく減らされる。
【００２０】この発明のその他の面および利点が、次の
詳細な説明から明白になるであろう。
【００２１】
【発明の実施の形態】この発明は、ディスクドライブ上
のデータストリームの非レギュラー（例えばランダム化
した）データレイアウトおよびディスクドライブのサブ
セットにわたってデータ冗長性を使用する記憶装置サー
バーに関する。データ再構築は、故障耐性を提供するた
めに冗長データを使用して実行される。また、この発明
は、任意の所与のストリームについて一つのパリティ・
グループのデータかたまりを保持する(k)個のディスク
のk個の待ち行列の任意のグループにおいて、少くとも1
つの過度に長い待ち行列を避けるためにも使用すること
ができる。これにより、ディスクドライブ上での「ラン
ダムな」混雑に起因して時折生じる過大な遅延を避ける
ことができ、バッファに対する要求を減らすことができ
る。さらに、すでに長い待ち行列に要求を追加しないこ
とによって、負荷平衡が改善され、待ち行列が過度に長
くなるのを減らすことができる。
【００２２】この発明の実施例を図1ないし6を参照して
説明する。しかし、この発明がこれらの限られた実施例
を越えて広がるもので、ここでこれらの図に関連してな
される詳細な説明が、説明的な目的のためのものである
ことが、当業者には容易にわかるであろう。
【００２３】図1は、発明の実施例に従う記憶装置サー
バー 2のブロック図である。記憶装置サーバー2は、複
数の記憶装置（ディスクドライブ）4、バス6、バッファ
ーメモリー8、再構築ユニット10、および制御ユニット1
2を含む。記憶装置4は好ましくはディスクドライブ5で
あるけれども、ランダムアクセス・メモリ、ビデオ・メ
モリのようなものであってもよい。記憶装置4がディス
クドライブであるとき、ディスクドライブ4は、磁気デ
ィスクドライブ、光ディスクドライブ、光磁気その他デ
ータを格納する記憶装置ドライブであってよい。必要な
のは、記憶容量が、それぞれ同様の通信バンド幅をもつ
複数のメモリ・ユニットに分割されることである。この
発明の貢献は、有効データ・ディスク転送速度が増加す
るとき増大する。同じ記憶ユニット内で連続するメモリ
ーアドレスから転送されるデータ量が増加するからであ
る。
【００２４】この実施例において、記憶装置サーバー2
は、ビデオ記憶装置サーバであり、したがって格納され
るデータはビデオ・データである。ディスクドライブ4
のそれぞれは、ディスクドライブ4をバッファーメモリ
ー8と制御ユニット12に接続するバス6に接続される。そ
れゆえに、バス6は、ディスクドライブ4、バッファーメ
モリー8、および制御ユニット12の間の切替および相互
接続手段として働く。バス6を実行するいろいろな方法
または他の切替および相互接続手段が当業者に明らかで
あろう。バッファーメモリー8は、ディスクドライブ4か
らのデータ受け取って、切替ユニット14にデータを出力
する。切替ユニット14に出力されるデータは、その後通
信網（図示しない）を介して遠隔のロケーションに送ら
れる。再構築ユニット10は、バッファーメモリー8と制
御ユニット12に接続され、他の関連するかたまりからデ
ータのかたまりを再構築する作用をする。
【００２５】ビデオ・サーバー2の操作は、バス6、バッ
ファーメモリー8および再構築ユニット10に接続された
制御ユニット12で制御される。図1に示されないけれど
も、制御ユニット12は、ディスクドライブ4のそれぞれ
のために優先順位付けされたアクセス要求の待ち行列を
維持する。再構築ユニット10が他の関連するかたまりか
らデータかたまりを再構築するようにすることによっ
て、制御ユニット12は、特定のディスクをバイパスす
る。好ましい実施例において、特定のディスクは、他の
関連するかたまりを保持するディスクのなかで最も長い
待ち行列遅延をもつのでバイパスされる。したがって、
特定のディスクでの混雑は、この発明によって軽減され
る。
【００２６】パリティ・グループ内のかたまりの再構築
は、好ましくは次のように達成される。パリティ・グル
ープは、k個のかたまりのデータおよび一つの関連した
パリティかたまりからなる。データかたまりが再構築さ
れるべきとき、そのパリティ・グループにおける残りの
kのかたまりは、k個の異なるディスクドライブ4からバ
ッファーメモリー8にそれぞれ読み込まれる。次いでk個
のかたまりが任意の順序で一つずつ再構築ユニット10に
コピーされる。再構築ユニット10は、一つのかたまりの
サイズに等しいかこれを越えるサイズのメモリ・バッフ
ァを持つ。再構築に先立ち、再構築ユニット10は、その
メモリにおける一つのかたまりに等しい領域を割り当て
て、そのすべてのビットを「0」にセットする。再構築
ユニット10にコピーされたすべてのビットがビットごと
に再構築ユニット10の内容とXORされる。すべてのk個の
かたまりがこのようにコピーされたならば、再構築ユニ
ット10におけるメモリ・バッファの内容は、そのデータ
が再構築されるべきかたまりと同じである。 再構築さ
れたかたまりが、バッファーメモリー8にコピーされ、
再構築において使用され、もはや必要とされないパリテ
ィかたまりを上書きする。他の誤り修正方式が使用され
るならば、再構築ユニット10は、当業者に自明な方法で
しかるべく修正される。また、この発明の異なる実施例
において、再構築は、ディスクからバッファまたはバッ
ファから切り替えユニットへの途中で、または切替ユニ
ット内で生じてもよい。最後に、再構築ユニット10にお
ける再構築は一度にかたまりの一部分に生じてもよく、
再構築ユニット10内に別々の再構築バッファが割り当て
られているならば、異なるかたまりの再構築が、時間的
にインターリーブ（はめ込み）されてもよい。
【００２７】ビデオ記憶装置サーバー2は、ディスクド
ライブ4にデータを記録し、ディスクドライブ4からデー
タを再生する作用をする。ビデオ記憶装置サーバー2
は、最終的には通信ネットワークにデータを供給する。
記録および再生動作の間のビデオ記憶装置サーバー2の
動作を、図2ないし4を参照して説明する。
【００２８】図2は、発明の実施例に従う記録手順16の
フローチャートである。記録手順16は、ディスクドライ
ブ・シーケンスを形づくるようにM個のディスクドライ
ブ4を繰り返しランダムに順序づける(18)ことから開始
する。たとえば、ビデオ記憶装置サーバー2がM個のディ
スクドライブ4を持つとき、それらは、ディスクドライ
ブ番号の長いシーケンスを形づくるためにランダムに繰
り返し順序づけられる。たとえば、10個ののディスクド
ライブがあるならば、ディスクドライブ・シーケンス
は、ディスクドライブ番号の長いシーケンスを形づくる
ために繰り返し互いに連結された10個のドライブのラン
ダムな順序を含む。ディスクドライブの順位付けには更
に制約がある。すなわち、任意の所与のパリティ・グル
ープのかたまりメンバーの位置を決めるために使用され
るシーケンスのk+1連続要素は、すべて異ならなければ
（ディスク番号）ならない。
【００２９】例えば、これは、そのような番号のシーケ
ンスにおいて所与のディスクドライブ番号の連続的な出
現が、少なくともk個の他の番号によって分離されなけ
ればならないという、より厳しい制約を課することによ
って保証することができる。ここで、k+1は、パリティ
・グループにおけるかたまりがとりうる最も大きい数で
ある。また、ディスクドライブ・シーケンスは、非周期
的であるか、またはMの実質的な倍数より大きい周期を
持つべきである。それぞれのドライブがMの合理的に小
さい整数倍の範囲において本質的に等しい回数現れる限
り、順序付けは、すべてのディスク・ディスクドライブ
番号の連鎖する置換を形成することに限定されない。素
直なシーケンスが、ランダムな選択に続いてそれらを制
約に従うよう修正するか、または符号理論の技術におい
て知られている「コード・シーケンス」を使用すること
によって生成される。少なくとも、k+lのドライブ4があ
る限り、ビデオ記憶装置サーバー2は、ほとんど任意の
数のディスクドライブ4を使用することができる。好ま
しくは、少なくとも、3k個のディスクドライブ4がある
のがよい。
【００３０】次にビデオ・タイトル（たとえば映画）の
記録すべき最初のk個の連続するデータのかたまりが選
ばれる(20)。好ましくは、記録されるビデオ・タイトル
は、データのブロックに分割され、各ブロックがさらに
いくつかのデータのかたまりに分割される。データの1
つのブロック内では、かたまりは同じサイズであるが、
異なるブロックは、異なるかたまりサイズおよび異なる
kを持つことができる。
【００３１】いずれにせよ説明の便宜上、この後かたま
りは、同じサイズであると仮定する。選ばれたデータか
たまりが、次いでディスクドライブ・シーケンスの最初
のk個のディスクドライブに記録される(22)。すなわ
ち、最初のデータかたまりが、シーケンスの第１のディ
スクドライブに格納され、第２のデータかたまりが、シ
ーケンスの第２のディスクドライブに格納される、等々
である。k個のデータかたまりがk個のディスクドライブ
に記録されると、k個のデータかたまりのためのパリテ
ィかたまりが決められ(24)、次いでk+ 1番目のディスク
ドライブに記録される(26)。たとえば、k = 3ならば、
シーケンスの4番目のディスクドライブは、第１、第
２、および第３のデータかたまりのためのパリティかた
まりを格納する。パリティ符号化方式を使用して他のデ
ータかたまりからのパリティかたまりを決める(24)エラ
ー修正技法は、よく知られている。
【００３２】その後、記録すべき付加的なデータかたま
りがあるかないかに基づいて、決定(28)がなされる。さ
もなければ、記録手順16が完了する。一方、記録すべき
付加的なデータかたまりがあるならば、ビデオ・タイト
ルの次のk個のデータかたまりが選ばれ(30)、k個のデー
タかたまりの次のグループを使用してブロック22ー26
が、ディスクドライブ・シーケンスの次のk個のディス
クドライブが使用されること以外同様の形態で繰り返さ
れる。
【００３３】かたまりは、選ばれたディスク内の任意に
選ばれたからの位置に記録することができる。一つのよ
い実施例において、パリティ・グループのすべてのデー
タかたまりの記録が、すべてのディスク上のそれぞれ同
じ位置で行われる。また、ディスク内で、ビデオ・デー
タ（例えば、映画）のかたまりがディスク上の連続した
位置に記録されることが好ましい。もう一つの多分好ま
しい実施例において、ディスクへの記録は、パリティ・
グループの細分性とともに使われるトラック・ペアリン
グ(Track-Pairing)方式に従ってなされる。トラック・
ペアリング方式は、米国特許出願第08/128,418号、およ
びヨーロッパ特許公報0 645 929 A2 に記載されてい
る。
【００３４】図3は、発明の実施例に従う再生手順32の
フローチャートである。再生手順32は、所望のストリー
ムの最初のパリティ・グループを含むデータかたまりを
保持するk+l個のディスクドライブの待ち行列の長さを
調べる(34)ことから始まる。パリティ・グループは、そ
れぞれがビデオ・データのデータのブロックと関連する
データのかたまりを格納するk個のディスクドライブ、
およびビデオ・データのブロックに関連するパリティか
たまりを格納するk+l番目のディスクドライブを含む。
【００３５】次に、再生手順32が、k個のディスクドラ
イブのうち最も長い列長さ（QLLONG）を持つデータかた
まりを保持するものを判断する(36)。最も長い列の長さ
をもつ待ち行列は、最も混雑した待ち行列である。最も
長い列の長さ（QLLONG）、およびパリティ（k+l番目
の）ディスクドライブの列の長さに基づいて決定(38)が
なされる。特に、最も長い列の長さ（QLLONG）がパリテ
ィ（k+ 1番目）ドライブの列の長さプラスあらかじめ決
められたしきい値量を越えるならば、ビデオ記憶装置サ
ーバー2の性能が、この発明によって増進される。この
条件が正しいとき、k個のディスクドライブ4から長さが
（QLLONG）列に等しいものを除くドライブおよびk+1番
目のディスク・ドライブ4からデータかたまりが読みと
られ(40)、バッファーメモリー8に格納される。この場
合、混雑したディスクドライブ4からはデータかたまり
が読みとられないことに注意されたい。最も長い列の長
さ（QLLONG）を持つディスクドライブ4と関連するデー
タかたまりが再構築され42、バッファーメモリー8に格
納される。それゆえに、読みとられなかった混雑したデ
ィスクドライブ4からのデータかたまりの代わりに再構
築されたデータかたまりが使用される。最も長い列の長
さ（QLLONG）を持っているディスクドライブ4をバイパ
スすることによって、もっとも混雑した待ち行列は、ビ
デオ記憶装置サーバー2の性能をもはや妨げない。
【００３６】一方、最も長い列の長さ（QLLONG）がパリ
ティ（k+ I番目の）ドライブの列長さプラスがあらかじ
め決められたしきい値量より大きくないことを決定38が
示すとき、データかたまりは、ディスクドライブ4から
読取られ46、再構築操作なしでバッファーメモリー8に
格納される。
【００３７】決定38の結果に関係なく、ブロック42およ
び46に続いて、データかたまりが送られる44。伝送され
るデータかたまりは、バッファーメモリー8から切替装
置14を通して通信網に供給される。データかたまりの実
際の伝送は、ビデオ記憶装置サーバー2によって提供さ
れるスケジューリングによって制御される。図5および6
が、この発明で使用することができる多数の可能なスケ
ジューリング方式の一つを図示する。
【００３８】最後に、送るべき付加的なデータかたまり
があるかないかに基づいて決定48がなされる。送るべき
データかたまりの付加ブロックがないならば、再生手順
32は、完了する。一方、伝送すべきデータかたまりがあ
るならば、再生手順32が、送られていたデータストリー
ムのデータかたまりの次のパリティ・グループを格納す
るk+1個のディスクドライブの次の組を使用してブロッ
ク34-46を繰り返す。k+1個のディスクドライブの組の内
のドライブは、データストリームが記録されたランダム
化されたディスクドライブ・シーケンスに従って変化す
る。
【００３９】図4は、この発明の別の実施例に従う再生
手順50のブロック図である。再生手順50は、パリティ・
グループを含むかたまりを保持するk+l個のディスクド
ライブの列の長さを調べる52ことから始まる。パリティ
・グループが、それぞれがビデオ・データのブロックと
関連するデータのかたまりを格納するk個のディスクド
ライブ、およびビデオ・データのブロックに関連するパ
リティかたまりを格納するk+ 1番目のディスクドライブ
を含む。
【００４０】次に、決定54が、パリティ・グループのか
たまりを保持するk+1個のディスクドライブの待ち行列
の長さの比較に基づいてなされる。第１のドライブ（QL
1）の待ち行列の長さが、パリティ・ドライブ（QLk+1）
の待ち行列の長さプラスあらかじめ決められたしきい値
量より大きいならば、この発明は、ビデオ記憶装置サー
バー2を従来より能率的に操作する。この実施例におい
て、伝送すべきデータ・ストリームのために最も早く必
要とされるデータを保持するのはこの待ち行列であるの
で、比較はパリティ・グループの最初の待ち行列の列長
さを使用する。パリティ・グループの他の待ち行列の状
況は、これらのかたまりがストリーミングのために読み
とられるまでには、本質的に変わるかもしれない。いず
れにしても、決定54が肯定的に答えられるとき、k個の
ディスクドライブのうち最も長い列の長さ（QLLONG）を
もつものが判断される56。そして、 最も長い列の長さ
を持つディスクドライブを除いて、データかたまりが、
パリティ・グループのすべてのディスクドライブから読
取られる58。読みとられたデータかたまり58が、バッフ
ァーメモリー8に格納される60。
【００４１】この実施例において要求をサービスするた
めの優先規則は、「ストリーミングが早いもの優先」で
ある。再構築が生じるべきとき、優先のための「ストリ
ーミング時間」は、かたまり自身のストリーミング時間
と再構築されたかたまりのものとの早い方である。しか
し、ストリーミングに先立つある時点で待ち行列に要求
を置くことは、スケジューリングの優先度がそのストリ
ーミング時間だけに依存するとしても、２つの目的にか
なう。すなわち、(i)関連するディスクの将来の負荷に
関するヒントを提供し、それによって新しい要求の到来
を低減させ、そして、(ii)サーバーがアイドル状態にな
るのを低減する。
【００４２】次に、最も長い列の長さ（QLLONG）を持つ
ディスクドライブに関連するデータかたまりが、データ
・パリティ・グループ内のすべての他のディスクドライ
ブからのかたまりを使用して再構築される(62)。パリテ
ィ・グループ内の他のディスクドライブからのデータか
たまりは、以前に読まれ(58)、バッファーメモリー8に
格納されている(60)。これらのデータかたまりを使用し
て、再生手順50は、最も長い列の長さを持っているディ
スクドライブに対応するデータかたまりを再構築するこ
とができる。再構築されたデータかたまりが、バッファ
ーメモリーに格納される(64)。したがって、最も長い待
ち行列長さを持つディスクドライブから、データかたま
りを読みとる代わりに、ビデオ記憶装置サーバー2は、
他のデータかたまりからデータかたまりを再構築して、
それをバッファーメモリー8に格納する。好ましくは、
再構築されたデータかたまりは、もはや不要なパリティ
かたまりの代わりにバッファーメモリー8に格納され
る。したがって、最も長い列の長さを持っているディス
クドライブは、この特定のデータかたまりを送るために
利用されない。その結果、負荷の平衡が生じ、システム
は、最も長い列の長さを持っているディスクドライブが
その長い遅延から回復するのを可能にする。
【００４３】一方、決定54が否定ならば、データストリ
ームの最初の2つのデータかたまりがバッファーメモリ
ー8に読み込まれる(68)。それ後、パリティ・グループ
の残っているk-2個のデータかたまりは、必要とされる
バッファーメモリー8に読み込まれる(70)。事実、残り
のk-2個のかたまりは時間に間に合うように要求されさ
えすればよいので、それらは、ストリーミングに必要と
される前に読まれる。このスケジューリング手法は、デ
ータストリームを支援するに要求なバッファー記憶装置
の量を最小にする。データの2つのかたまりを最初に要
求する（またはバッファに予備のかたまり持つ）利点
は、パリティ・グループの間の境界での時間が、バッフ
ァがからになる最も弱みのある時間であることである。
【００４４】決定54の結果に関係なく、ブロック64また
は70に続いて、データかたまりは、切替装置14を通して
通信ネットワーク上で１つまたは複数の転送先に送られ
る。ブロック66に続き、伝送すべき付加的なデータかた
まりのブロックがあるかどうかに基づいて、決定72がな
される。送るべきるデータかたまりのブロックがもうな
いならば、再生手順50が完了する。さもなければ、ブロ
ック52-70は、伝送すべき残りのデータかたまりのブロ
ックのそれぞれのについて繰り返される。
【００４５】また、所望される特定の最適化に依存して
上述の再生手順32および50の変形も可能である。例え
ば、図4の決定54は、列長さがなんらかの措置を必要と
するほど大きいかどうか見みるため、第１のドライブ
（QL1）の列の長さをしきい値量と最初に比較すること
によってより複雑なものにすることもできる。列長さが
十分大きければ、再構築に関連するオーバーヘッドを考
え、再構築がなんらかの利益を提供するかどうか判断す
るため、決定54を実行する。
【００４６】図3および4で述べなかったが、パリティ・
グループのかたまりを格納するk個のディスクの一つが
故障する場合、不良のディスク上のデータかたまりの再
構築は、列の長さに関係なく行われる。上記の処理は、
列の長さの比較によって常にそのかたまりの再構築を引
き起こすように不良ディスクの列の長さを比較的に大き
い数にセットすることによってこの場合を含むことがで
きる。
【００４７】図5は、再構築が必要でない場合における
メモリ・バッファ利用法を図示する。水平軸が時間を表
現し、長方形の幅がビデオ速度で一つのかたまりを上映
するのに必要な時間を示す。それぞれの時間スロットで
積み重ねられた長方形が、メモリ・バッファにある（す
なわち、かたまりを上映する時間に等しい）かたまりを
表現する。図の例において、かたまりn+1からはじめて
５つのパリティかたまりの読み出しおよびストリーミン
グを考える。このグループを考えるとき、バッファはま
だ前のパリティ・グループに属するかたまりn-1およびn
を含んでいる。このとき、かたまりn+ 1とn+2が要求さ
れ、そして、バッファの必要性を最大にする状況を反映
して、両方が直ちに受け取られる。一つのタイムスロッ
ト後には、かたまりn-1は上映されており、したがって
なくなっており、そして、かたまりn+3が要求され、再
び直ちに受け取られるので、バッファ・サイズは、一定
のままである。4つの時間スロット後には、パリティ・
グループのすべての５つのかたまりが要求され、受け取
られているので、新しい要求は出されず、バッファ占有
が1に落ちる。次の時間スロットにおいて、次のパリテ
ィ・グループが考慮される。再び、再構築しないという
決定がなされ、最初の2つのかたまりn+6とn+7が要求さ
れ受け取られ、 再びバッファ使用を4まで上昇させる。
【００４８】図6は、再構築が不良ディスクまたは長い
待ち行列を避けるために利用される場合のメモリ・バッ
ファ利用法を図示する。図の例は、k個のかたまり（k-1
個のデータおよび一つのパリティかたまり）が、要求さ
れて、直ちに受け取られ、そして、これに先立ち2つの
かたまり（nとn-1）が、バッファにあった場合を描写す
る。パリティ・グループのストリーミング時間の残りに
おいて、さらにかたまりが要求されることはないので、
時間スロットごとにバッファ使用が一つのかたまりずつ
落ちる。
【００４９】図４ないし６に示す読みとり要求を発する
方針および要求に応える優先順位の両方とも好ましい実
施例にすぎない。この発明は、上映順、再構築する必要
性、バッファリング要求、およびあまりに早く受け取り
バッファしなければならないデータの分枝を考慮に入れ
た、より広いスケジューリング方針および優先順位を含
む。これが、例えば、要求が、待ち行列に置かれた後に
おいても、k個のデータかたまりのいずれかの所与のグ
ループについてパリティ（冗長）かたまりを使用するか
どうかの決定の変更を許す方針、および単に列の長さだ
けではなく待ち行列に入れられた要求の優先順位を調べ
る決定方針を含む。具体的には、上で説明した実施例
は、最も長い列の長さまたは最初の列の長さをパリティ
列の長さと比較するけれども、データのかたまりを再構
築するための決定をするために他の基準を使用すること
ができる。例えば、データ待ち行列の平均長さ対パリテ
ィ待ち行列の長さ、待ち行列に入れられた要求をサービ
スする仕事の量、または待ち行列に入れられた要求の優
先順位のスケジューリングおよびそれらの締切期限を使
用することができる。
【００５０】上で説明した実施例は、一つのディスクの
故障または大きな待ち行列の長さを補償するためにパリ
ティ方式を使用する。特に、実施例は、データのk個の
かたまりのためのエラー訂正符号を実行するために一つ
のパリティかたまりを使用した。この手法は、他の誤り
訂正符号を使用するよう容易に一般化することができ、
特定のディスクを誤り修正情報の格納のために占有する
必要はない。例えば、この発明の概念は、（k+1個のか
たまりから）k+r個のかたまりに一般化されることがで
きる。ここで、rは、各k個のデータかたまりのためのパ
リティかたまりの数を表現する。また、この技術分野に
おいてよく理解されているように他の誤り訂正符号を使
用してもよい。
【００５１】バンド幅とバッファ要求事項の間にはトレ
ードオフがある。上で説明された実施例において、デー
タの所与のかたまりは、最高でも一度、読みとられた。
代わりに、再構築のために必要なデータかたまり当たり
２度ディスクドライブから読み出すことによってバッフ
ァ・スペースを節約することができる。それは、再構築
の目的で一度読みとられ実際にストリーミングのために
必要とされるとき一度読み出される（順序は、これおよ
びストリームにおいて再構築されたかたまりの相対的な
位置に依存する）。
【００５２】図1を参照して説明したこの発明の実施例
において、なくしたデータの再構築は、バッファーメモ
リー8から再構築ユニット10にデータかたまりを読み込
み、それから再構築されたデータかたまりをバッファー
メモリー8に書き込むことによって行われる。再構築さ
れたデータは、冗長データかたまりを上書きしてもよ
く、しなくてもよい。しかし、再構築がディスクドライ
ブからバッファーメモリー8への途中、またはバッファ
ーメモリー8から通信ネットワークへの途中で起こって
もよいことが認識される。また、むしろ全かたまりにつ
いてよりも、一つのかたまりより小さい部分を基礎とし
て再構築を実行してもよい。最後に、再構築は、共用メ
モリー・バッファ8においてまたは再構築ユニット10の
記憶装置メモリにおいて複数の進行中の再構築のために
部分的な結果を格納することによって増加的に実行する
ことができる。
【００５３】この発明の多くの特徴と利点が以上の説明
から明白であり、そして、特許請求の範囲は、この発明
のすべてのそのような特徴および利点をカバーすること
を意図している。更に当業者にとって多数の修正と変更
が自明であろうから、以上に図示し説明した構造および
操作にこの発明を制限することは、意図していない。そ
れゆえに、すべての適当な修正および均等物はこの発明
の範囲内である。
【００５４】この発明は、例として、次の実施態様を含
む。 1. データを格納し供給するためのサーバー・システム
であって、それぞれがデータを格納する複数のディスク
ドライブと、上記ディスクドライブから間もなく供給さ
れるべきデータの部分を一時的に格納するために上記デ
ィスクドライブに接続されたバッファーメモリーと、少
くとも上記ディスクドライブの1つがバイパスされうる
ように、複数の残りのディスクドライブからのデータの
一部を使用して上記ディスクドライブの少なくとも1つ
からデータの一部を再構築するために、上記バッファー
メモリーに接続された再構築ユニットと、上記ディスク
ドライブに関連する待ち行列と、上記サーバー・システ
ムを制御するための制御ユニットであって、待ち行列情
報を得るために上記待ち行列を調べ、ついで待ち行列情
報に基づいて、上記ディスクドライブのいずれかをバイ
パスするかどうか決定する制御ユニットと、上記バッフ
ァーメモリーおよび上記再構築ユニットの一方または両
方からデータを出力するための出力装置と、を備える上
記サーバー・システム。 2. 上記サーバー・システムがビデオ記憶装置サーバで
あり、格納されるデータがビデオ・データである、上記
１に記載のサーバー・システム。 3. 待ち行列のそれぞれが、上記ディスクドライブの一
つと関連する上記１に記載のサーバー・システム。 4. 上記ディスクドライブに格納されるデータが、デー
タかたまりの組に分割され、それぞれの組のなかで、デ
ータかたまりが、同サイズであり、そして、所与の組の
データかたまりのそれぞれがが上記ディスクドライブの
異なるものに格納される、上記１に記載のサーバー・シ
ステム。 5. データかたまりの組のそれぞれが、同じも数のデー
タかたまりを含む、上記４に記載のサーバー・システ
ム。 6. すべての組のデータかたまりが同サイズである、上
記４に記載のサーバー・システム。
【００５５】7. データがk個の同サイズのデータかた
まりの組に分割され、k個のデータかたまりのうち任意
のr個のデータが、複数の残りのデータかたまりのデー
タおよび同じ組のかたまりの冗長かたまりから再構築さ
れることができるよう、k個のデータかたまりのそれぞ
れについてr個の冗長かたまりがつくられ、各組のk個の
データかたまりおよびr冗長かたまりが、k+r個の異なる
ディスクドライブに格納される（kおよびrは正の整
数）、上記１に記載のサーバー・システム。
【００５６】8. rが1に等しく、そして、k個のデータ
かたまりの各組の一つの冗長かたまりがパリティ情報を
含み、そして、上記再構築ユニットが、パリティ情報お
よおび他のディスクドライブからの他のデータを使用し
て、バイパスされる上記ディスクドライブに格納される
データかたまりを再構築する、上記７に記載のサーバー
・システム。
【００５７】9.上記制御ユニットが、待ち行列のそれぞ
れにおける混雑を調べるための手段と、データかたまり
の所与の組のデータかたまりを保持している上記ディス
クドライブのなかから、もっとも混雑した待ち行列と関
連する上記ディスクドライブを識別するための手段と、
を備える上記４に記載のサーバー・システム。
【００５８】10. データかたまりの組のそれぞれが複
数のデータかたまり、および少くとも1つの再構築かた
まりを含み、もっとも混雑する待ち行列での混雑の量
が、少くとも再構築かたまりの中の1つをそばに格納す
るディスクドライブと関連する待ち行列での混雑よりあ
らかじめ決められた量以上だけ大きいとき、上記再構築
ユニットが、最も混雑する待ち行列と関連するディスク
ドライブに関連するデータかたまりを再構築する、上記
９に記載のサーバー・システム。 11. 待ち行列での混雑が列の長さおよびスケジュール
優先度のうちの少なくとも1つを考慮することによって
調べられる上記１０に記載のサーバー。 12. データかたまりの組のそれぞれが、複数のデータ
かたまりおよび少くとも1つの再構築かたまりを含み、
少くとも１つのデータかたまりを格納するディスクドラ
イブに関連する待ち行列での混雑の量が、再構築かたま
りのうちの少なくとも1つを格納するディスクドライブ
と関連する列での混雑よりあらかじめ決められた量以上
大きいとき、上記再構築ユニットが、一組のデータかた
まりの少くとも1つのデータかたまりを再構築する、上
記９に記載のサーバー・システム。
【００５９】13. データかたまりの組のそれぞれが、
複数のデータかたまりと少くとも1つの再構築かたまり
を含み、第１のデータかたまりを格納しているディスク
ドライブに関連する待ち行列での混雑の量が、再構築か
たまりのうちの少なくとも1つを格納するディスクドラ
イブに関連する待ち行列での混雑よりあらかじめ決めら
れた量以上大きいとき、上記再構築ユニットが、一組の
データかたまりの最初のデータかたまりと関連するディ
スクドライブと関連するデータかたまりを再構築する、
上記９に記載のサーバー・システム。 14. 上記制御ユニットが、操作情報を得るため上記デ
ィスクドライブの操作状態を調べ、待ち行列情報と操作
可能情報の両方を使用して、上記ディスクドライブのの
いずれかをバイパスするかどうか決める、上記１に記載
のサーバー・システム。 15. ビデオ・タイトルをいくつかのディスクドライブに
格納するための方法であって、(a)ディスクドライブ・
シーケンスを形づくるよう繰り返してディスクドライブ
を順序づけるステップと、(b) 記録すべきビデオ・タイ
トルを複数のデータかたまりに分割するステップと、
(c)組内でデータかたまりのそれぞれが等しいサイズを
持つ、ビデオ・タイトルの一組の連続的なデータかたま
りを選ぶステップと、(d)ディスクドライブ・シーケン
スにおける一組のディスクドライブにデータかたまりの
組をそれぞれ記録するステップと、(e)データかたまり
の組のための冗長かたまりを決定するステップと、(f)
ディスクドライブ・シーケンスにおける次のディスクド
ライブに冗長かたまりを記録するステップと、を含む上
記方法。 16. 上記上記順位付けステップ(a)が、非周期的である
かまたはディスクドライブの数より非常に大きい周期を
持つディスク番号のシーケンスをつくり、少なくともい
くらかのあらかじめ指定された長さを持つシーケンスの
任意の連続内であらゆるディスク番号が本質的に等しい
回数再起することを保証すし、同じディスク番号の再起
の間に、少なくともあるあらかじめ指定された距離を確
保する、上記１５に記載の方法。 17. (g)組内ではデータかたまりのそれぞれは等しいサ
イズを持ち、記録されつつあるビデオ・タイトルの次の
組のデータかたまりを選ぶステップと、(h)次のビデオ
・タイトルのデータかたまりの組をディスクドライブ・
シーケンスの次の組のディスクドライブへそれぞれ記録
するステップと、(i)(g)において選ばれた次の組のデー
タかたまりのための冗長かたまりを決定するステップ
と、(j)ディスクドライブ・シーケンスの次のディスク
ドライブに冗長かたまりを記録するステップと、を含む
上記16に記載の方法。 18. (k)ビデオタイトルのすべてのデータかたまりが記
録されるまで上記(g)ないし(j)のステップを繰り返すス
テップを含む上記17に記載の方法。 19. 上記決定するステップ(e)が、データかたまりの関
連した組の内容に基づいて複数の冗長かたまりを判断
し、上記記録するステップ(f)が、それぞれ冗長かたま
りのそれぞれをディスクドライブ・シーケンスの次のデ
ィスクドライブに記録する、上記15に記載の方法。 20. ディスクドライブ・シーケンスを形成するとき、
上記順位付けステップ(a)は、ランダムにディスクドラ
イブを順序づける、上記15に記載の方法。 21. データストリームが、ディスクドライブから得られ
るビデオ・データから形成され、ビデオ・データが、ブ
ロックに分割され、それぞれのブロックが、一組の異な
るディスクドライブに格納される一組のデータかたまり
に分割され、データかたまりの各組のための少くとも1
つの冗長かたまりが、ディスクドライブにつき一つのか
たまり、ディスクドライブの他のものに格納され、そし
て、ビデオデータのブロックそれぞれのデータかたまり
が、少なくとも1つの冗長かたまりとともにグループを
形成する、ことを含む、ディスク・ドライブから転送先
までデータを供給するための方法であって、(a)ディス
クドライブのそれぞれのためにアクセス要求の待ち行列
を維持するステップと、(b)グループと関連するディス
クドライブの待ち行列の待ち行列状態情報を調べるステ
ップと、(c)再構築かたまりに対応する待ち行列状態情
報および少くとも1つのデータかたまりに対応する待ち
行列状態情報の両方に基づいて、組の少くとも1つのデ
ータかたまりを、その組の他のデータかたまりおよび関
連する再構築かたまりから選択的に再構築するステップ
と、(d)転送先にデータかたまりを供給するステップ
と、を含む上記方法。 22. ディスクドライブへのデータかたまりの格納が、
ディスクドライブ・シーケンスに従って、そしてディス
クドライブ・シーケンスを形づくるために行われ、上記
方法は、非周期的であるかまたはディスクドライブの数
よりかなり大きい周期を持つディスク番号のシーケンス
をつくり、少なくともあらかじめ指定された長さを持つ
シーケンスの部分シーケンス内であらゆるディスク番号
の本質的に等しい数の再起を保証し、同じディスク番号
の再起の間に少なくともあるあらかじめ指定された距離
を確保する、上記21に記載の方法。
【００６０】23. 上記再構築ステップ(c)は、グループ
のために、少なくとも１つのデータかたまりに対応する
待ち行列状態情報に関し再構築かたまりに対応する待ち
行列状態情報を比較することによって少くともデータか
たまりの1つを再構築するかどうか決定する、上記21に
記載の方法。
【００６１】24. 上記再構築ステップ(c)が、グループ
内の最初のデータかたまりに対応する待ち行列状態情報
および再構築かたまりに対応する待ち行列状態情報の両
方に基づいて、少くともデータかたまりの1つを再構築
するかどうか決定する、上記21に記載の方法。
【００６２】25. 待ち行列状態情報が列の長さであ
る、上記21に記載の方法。
【００６３】26．上記再構築するステップ(c)が、再構
築かたまりに対応する列の長さおよびグループのデータ
かたまりの列の長さの中で最も長い列の長さの両方に基
づいて、少くともデータかたまりの1つを再構築するか
どうか決定する、上記25に記載の方法。
【００６４】27. 上記再構築するステップ(c)が、(c1)
上記ディスクドライブにアクセス要求を発するステップ
を含み、アクセス要求が対応するディスクドライブに発
せられる優先順位が、冗長かたまりの再構築のためまた
はデータかたまりの上記供給ステップ(d)のためにデー
タかたまりが必要とされる時に依存する、上記21に記載
の方法。
【００６５】28.グループ内の複数のデータかたまりが
同じサイズである、上記21に記載の方法。
【００６６】
【発明の効果】この発明によると、ディスクドライブの
読み出し混雑を回避し、負荷のバランスおよび故障耐性
が得られる。
【図面の簡単な説明】
【図１】この発明の実施例に従うビデオ記憶装置サーバ
ーのブロック図。
【図２】この発明の実施例に従う記録手順のフローチャ
ート。
【図３】この発明の実施例に従う再生手順のフローチャ
ート。
【図４】この発明の別の実施例に従う再生手順のブロッ
ク図。
【図５】再構築が必要でない場合のメモリ・バッファ利
用法を示す図表。
【図６】再構築が利用される場合のメモリ・バッファ利
用法を示す図表。
【符号の説明】
４ ディスクドライブ ８ バッファメモリー １０ 再構築ユニット １２ 制御ユニット １４ 切替ユニット

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】 データを格納し供給するためのサーバー
    ・システムであって、 それぞれがデータを格納する複数のディスクドライブ
    と、 上記ディスクドライブから間もなく供給されるべきデー
    タの部分を一時的に格納するために上記ディスクドライ
    ブに接続されたバッファーメモリーと、 上記ディスクドライブの少くとも1つがバイパスされう
    るように、複数の残りのディスクドライブからのデータ
    の一部を使用して該ディスクドライブの少なくとも1つ
    のデータの一部を再構築するために、上記バッファーメ
    モリーに接続された再構築ユニットと、 上記ディスクドライブに関連する待ち行列と、 上記サーバー・システムを制御するための制御ユニット
    であって、待ち行列情報を得るために上記待ち行列を調
    べ、次いで待ち行列情報に基づいて、上記ディスクドラ
    イブのいずれかをバイパスするかどうか決定する制御ユ
    ニットと、 上記バッファーメモリーおよび上記再構築ユニットの一
    方または両方からデータを出力するための出力装置と、 を備える上記サーバー・システム。
JP8095315A 1995-04-28 1996-04-17 データを格納し供給するサーバー・システム Pending JPH0926854A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US431,189 1995-04-28
US08/431,189 US5592612A (en) 1995-04-28 1995-04-28 Method and apparatus for supplying data streams

Publications (1)

Publication Number Publication Date
JPH0926854A true JPH0926854A (ja) 1997-01-28

Family

ID=23710851

Family Applications (1)

Application Number Title Priority Date Filing Date
JP8095315A Pending JPH0926854A (ja) 1995-04-28 1996-04-17 データを格納し供給するサーバー・システム

Country Status (3)

Country Link
US (1) US5592612A (ja)
EP (1) EP0740247A3 (ja)
JP (1) JPH0926854A (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1998045771A1 (en) * 1997-04-07 1998-10-15 Sony Corporation Recording and reproducing device
JP2002529878A (ja) * 1998-10-30 2002-09-10 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 記憶システム
US6564295B2 (en) 2000-09-20 2003-05-13 Matsushita Electric Industrial Co., Ltd. Data storage array apparatus, method of controlling access to data storage array apparatus, and program and medium for data storage array apparatus
US6813685B1 (en) 1997-10-17 2004-11-02 Fujitsu Limited System for storing data and method of controlling the writing of redundant data
JP2007529060A (ja) * 2003-07-14 2007-10-18 インターナショナル・ビジネス・マシーンズ・コーポレーション 冗長アレイからのマルチパス・データ取出

Families Citing this family (72)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5724543A (en) * 1995-06-19 1998-03-03 Lucent Technologies Inc. Video data retrieval method for use in video server environments that use striped disks
US5826110A (en) * 1995-06-19 1998-10-20 Lucent Technologies Inc. System for video server using coarse-grained disk striping method in which incoming requests are scheduled and rescheduled based on availability of bandwidth
US5787482A (en) * 1995-07-31 1998-07-28 Hewlett-Packard Company Deadline driven disk scheduler method and apparatus with thresholded most urgent request queue scan window
JP3617879B2 (ja) * 1995-09-12 2005-02-09 株式会社東芝 実時間ストリームサーバのディスク修復方法及びディスク修復装置
JPH0981497A (ja) * 1995-09-12 1997-03-28 Toshiba Corp 実時間ストリームサーバ並びに実時間ストリームデータの格納方法および転送方法
DE69610552T2 (de) * 1995-12-01 2001-05-31 Koninkl Philips Electronics Nv Datenleseverfahren und -system für eine anzahl von verwendern
US5719983A (en) * 1995-12-18 1998-02-17 Symbios Logic Inc. Method and apparatus for placement of video data based on disk zones
JP2914261B2 (ja) * 1995-12-20 1999-06-28 富士ゼロックス株式会社 外部記憶制御装置及び外部記憶装置制御方法
US6018765A (en) * 1996-01-23 2000-01-25 Storage Concepts, Inc. Multi-channel multimedia data server
US5832198A (en) * 1996-03-07 1998-11-03 Philips Electronics North America Corporation Multiple disk drive array with plural parity groups
US5870551A (en) * 1996-04-08 1999-02-09 Lucent Technologies Inc. Lookahead buffer replacement method using ratio of clients access order offsets and buffer data block offsets
JPH09284745A (ja) * 1996-04-09 1997-10-31 Sony Corp 双方向情報伝送システムおよび双方向情報伝送方法
US6078989A (en) * 1996-10-04 2000-06-20 Sony Corporation Disc array control method and disc array control apparatus
US6161165A (en) * 1996-11-14 2000-12-12 Emc Corporation High performance data path with XOR on the fly
JPH10303840A (ja) * 1997-04-25 1998-11-13 Sony Corp マルチチャンネル放送システム
JP3745506B2 (ja) * 1997-07-12 2006-02-15 ソニー株式会社 データ処理装置及び方法
JP3810530B2 (ja) * 1997-09-18 2006-08-16 富士通株式会社 ビデオサーバシステム、コンテンツ動的配置装置及びコンテンツ動的配置方法
US6088766A (en) * 1997-10-06 2000-07-11 Emc Corporation Method for exchanging data blocks on disk storage devices utilizing disk access statistics and testing for the effect of a change
US6061761A (en) 1997-10-06 2000-05-09 Emc Corporation Method for exchanging logical volumes in a disk array storage device in response to statistical analyses and preliminary testing
JPH11231849A (ja) * 1997-11-04 1999-08-27 Matsushita Electric Ind Co Ltd 画像合成装置
US6415373B1 (en) 1997-12-24 2002-07-02 Avid Technology, Inc. Computer system and process for transferring multiple high bandwidth streams of data between multiple storage units and multiple applications in a scalable and reliable manner
US6374336B1 (en) * 1997-12-24 2002-04-16 Avid Technology, Inc. Computer system and process for transferring multiple high bandwidth streams of data between multiple storage units and multiple applications in a scalable and reliable manner
CA2316239A1 (en) * 1997-12-24 1999-07-08 Avid Technology, Inc. Computer system and process for transferring multiple high bandwidth streams of data between multiple storage units and multiple applications in a scalable and reliable manner
US7010532B1 (en) * 1997-12-31 2006-03-07 International Business Machines Corporation Low overhead methods and apparatus for shared access storage devices
US5950203A (en) * 1997-12-31 1999-09-07 Mercury Computer Systems, Inc. Method and apparatus for high-speed access to and sharing of storage devices on a networked digital data processing system
US6694317B1 (en) * 1997-12-31 2004-02-17 International Business Machines Corporation Method and apparatus for high-speed access to and sharing of storage devices on a networked digital data processing system
US6658417B1 (en) 1997-12-31 2003-12-02 International Business Machines Corporation Term-based methods and apparatus for access to files on shared storage devices
US6321345B1 (en) * 1999-03-01 2001-11-20 Seachange Systems, Inc. Slow response in redundant arrays of inexpensive disks
CA2393621C (en) * 1999-12-10 2010-02-09 Diva Systems Corporation Method and apparatus for performing user migration within a video on demand environment
US7113998B1 (en) * 2000-02-03 2006-09-26 International Business Machines Corporation System and method for grouping recipients of streaming data
US20010025343A1 (en) * 2000-03-27 2001-09-27 Roy Chrisop Random bit mask generation for obscuring data on nonvolatile memory device
US7191242B1 (en) * 2000-06-22 2007-03-13 Apple, Inc. Methods and apparatuses for transferring data
US6993604B2 (en) * 2000-11-15 2006-01-31 Seagate Technology Llc Dynamic buffer size allocation for multiplexed streaming
US6996742B2 (en) * 2000-11-28 2006-02-07 Sedna Patent Services, Llc Method for regenerating and streaming content from a video server using RAID 5 data striping
US6834315B2 (en) 2001-03-26 2004-12-21 International Business Machines Corporation Method, system, and program for prioritizing input/output (I/O) requests submitted to a device driver
US8392586B2 (en) * 2001-05-15 2013-03-05 Hewlett-Packard Development Company, L.P. Method and apparatus to manage transactions at a network storage device
US7904931B2 (en) * 2001-09-12 2011-03-08 Cox Communications, Inc. Efficient software bitstream rate generator for video server
AU2003206140A1 (en) * 2002-02-21 2003-09-09 Fujitsu Limited A method and system for internet content acquisition according to a program guide
JP3950720B2 (ja) 2002-03-18 2007-08-01 株式会社日立製作所 ディスクアレイサブシステム
US7912954B1 (en) * 2003-06-27 2011-03-22 Oesterreicher Richard T System and method for digital media server load balancing
US7216021B2 (en) * 2003-10-30 2007-05-08 Hitachi, Ltd. Method, system and computer program for managing energy consumption
JP2005309818A (ja) * 2004-04-22 2005-11-04 Hitachi Ltd ストレージ装置、そのデータ読出方法、及びそのデータ読出プログラム
EP2264604A1 (en) * 2009-06-15 2010-12-22 Thomson Licensing Device for real-time streaming of two or more streams in parallel to a solid state memory device array
US8291277B2 (en) * 2009-10-29 2012-10-16 Cleversafe, Inc. Data distribution utilizing unique write parameters in a dispersed storage system
US8316175B2 (en) * 2009-11-03 2012-11-20 Inphi Corporation High throughput flash memory system
US8689040B2 (en) * 2010-10-01 2014-04-01 Lsi Corporation Method and system for data reconstruction after drive failures
US9170878B2 (en) 2011-04-11 2015-10-27 Inphi Corporation Memory buffer with data scrambling and error correction
US8880790B2 (en) 2011-04-11 2014-11-04 Inphi Corporation Methods and apparatus for transferring data between memory modules
US8687451B2 (en) 2011-07-26 2014-04-01 Inphi Corporation Power management in semiconductor memory system
US9158726B2 (en) 2011-12-16 2015-10-13 Inphi Corporation Self terminated dynamic random access memory
US8949473B1 (en) 2012-02-16 2015-02-03 Inphi Corporation Hybrid memory blade
US9230635B1 (en) 2012-03-06 2016-01-05 Inphi Corporation Memory parametric improvements
US8861277B1 (en) 2012-06-26 2014-10-14 Inphi Corporation Method of using non-volatile memories for on-DIMM memory address list storage
US9575806B2 (en) * 2012-06-29 2017-02-21 Intel Corporation Monitoring accesses of a thread to multiple memory controllers and selecting a thread processor for the thread based on the monitoring
US9647799B2 (en) 2012-10-16 2017-05-09 Inphi Corporation FEC coding identification
CN103558574B (zh) * 2013-10-24 2014-11-19 国家电网公司 基于eeprom数据读写的智能电能表软件容错能力测试方法
US10185499B1 (en) 2014-01-07 2019-01-22 Rambus Inc. Near-memory compute module
US9553670B2 (en) 2014-03-03 2017-01-24 Inphi Corporation Optical module
CN104092968A (zh) * 2014-06-13 2014-10-08 清华大学 超高清视频的视频数据存储控制装置
US9874800B2 (en) 2014-08-28 2018-01-23 Inphi Corporation MZM linear driver for silicon photonics device characterized as two-channel wavelength combiner and locker
US9325419B1 (en) 2014-11-07 2016-04-26 Inphi Corporation Wavelength control of two-channel DEMUX/MUX in silicon photonics
US9473090B2 (en) 2014-11-21 2016-10-18 Inphi Corporation Trans-impedance amplifier with replica gain control
US9553689B2 (en) 2014-12-12 2017-01-24 Inphi Corporation Temperature insensitive DEMUX/MUX in silicon photonics
US9461677B1 (en) 2015-01-08 2016-10-04 Inphi Corporation Local phase correction
US9547129B1 (en) 2015-01-21 2017-01-17 Inphi Corporation Fiber coupler for silicon photonics
US9484960B1 (en) 2015-01-21 2016-11-01 Inphi Corporation Reconfigurable FEC
US9548726B1 (en) 2015-02-13 2017-01-17 Inphi Corporation Slew-rate control and waveshape adjusted drivers for improving signal integrity on multi-loads transmission line interconnects
US9632390B1 (en) 2015-03-06 2017-04-25 Inphi Corporation Balanced Mach-Zehnder modulator
US9847839B2 (en) 2016-03-04 2017-12-19 Inphi Corporation PAM4 transceivers for high-speed communication
TWI764856B (zh) * 2021-12-13 2022-05-11 慧榮科技股份有限公司 記憶體控制器與資料處理方法
WO2025170203A1 (ko) * 2024-02-06 2025-08-14 삼성전자주식회사 메모리 풀을 관리하는 서버, 방법, 및 비-일시적 컴퓨터 판독 가능 기록 매체
CN118837726B (zh) * 2024-09-20 2024-12-17 绍兴圆方半导体有限公司 Mems芯片的测试方法及系统、存储介质

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4543628A (en) * 1983-01-28 1985-09-24 Digital Equipment Corporation Bus for data processing system with fault cycle operation
US5202979A (en) * 1985-05-08 1993-04-13 Thinking Machines Corporation Storage system using multiple independently mechanically-driven storage units
US4942579A (en) * 1987-06-02 1990-07-17 Cab-Tek, Inc. High-speed, high-capacity, fault-tolerant error-correcting storage system
US5072378A (en) * 1989-12-18 1991-12-10 Storage Technology Corporation Direct access storage device with independently stored parity
US5278838A (en) * 1991-06-18 1994-01-11 Ibm Corp. Recovery from errors in a redundant array of disk drives
GB2270791B (en) * 1992-09-21 1996-07-17 Grass Valley Group Disk-based digital video recorder
US5463765A (en) * 1993-03-18 1995-10-31 Hitachi, Ltd. Disk array system, data writing method thereof, and fault recovering method
US5455934A (en) * 1993-03-23 1995-10-03 Eclipse Technologies, Inc. Fault tolerant hard disk array controller
US5367669A (en) * 1993-03-23 1994-11-22 Eclipse Technologies, Inc. Fault tolerant hard disk array controller
US5414455A (en) * 1993-07-07 1995-05-09 Digital Equipment Corporation Segmented video on demand system
US5442390A (en) * 1993-07-07 1995-08-15 Digital Equipment Corporation Video on demand with memory accessing and or like functions
US5510905A (en) * 1993-09-28 1996-04-23 Birk; Yitzhak Video storage server using track-pairing
US5623595A (en) * 1994-09-26 1997-04-22 Oracle Corporation Method and apparatus for transparent, real time reconstruction of corrupted data in a redundant array data storage system

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1998045771A1 (en) * 1997-04-07 1998-10-15 Sony Corporation Recording and reproducing device
US6308007B1 (en) 1997-04-07 2001-10-23 Sony Corporation Recording and reproducing device
US6813685B1 (en) 1997-10-17 2004-11-02 Fujitsu Limited System for storing data and method of controlling the writing of redundant data
JP2002529878A (ja) * 1998-10-30 2002-09-10 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 記憶システム
US6564295B2 (en) 2000-09-20 2003-05-13 Matsushita Electric Industrial Co., Ltd. Data storage array apparatus, method of controlling access to data storage array apparatus, and program and medium for data storage array apparatus
JP2007529060A (ja) * 2003-07-14 2007-10-18 インターナショナル・ビジネス・マシーンズ・コーポレーション 冗長アレイからのマルチパス・データ取出

Also Published As

Publication number Publication date
US5592612A (en) 1997-01-07
EP0740247A3 (en) 1998-02-11
EP0740247A2 (en) 1996-10-30

Similar Documents

Publication Publication Date Title
JPH0926854A (ja) データを格納し供給するサーバー・システム
US5559764A (en) HMC: A hybrid mirror-and-chained data replication method to support high data availability for disk arrays
EP0727750B1 (en) Continuous data server apparatus and data transfer scheme enabling multiple simultaneous data accesses
US6996742B2 (en) Method for regenerating and streaming content from a video server using RAID 5 data striping
Berson et al. Fault tolerant design of multimedia servers
US6529994B1 (en) Method of striping data onto a storage array
US7308602B2 (en) Method and apparatus for striping data onto a plurality of disk drives
US5649093A (en) Server disk error recovery system
US5878280A (en) Data buffering system for plural data memory arrays
Özden et al. Fault-tolerant architectures for continuous media servers
Mourad Issues in the design of a storage server for video-on-demand
US5799174A (en) Staggered striping in multimedia information systems
US6301711B1 (en) System and method for the network support of full motion video using a redundant array of inexpensive disks
US6079028A (en) Fault tolerant architectures for continuous media servers
Birk Random RAIDs with selective exploitation of redundancy for high performance video servers
Gafsi et al. Data striping and reliability aspects in distributed video servers
Lau et al. Scheduling and replacement policies for a hierarchical multimedia storage server
US6449248B1 (en) Method to increase bandwidth of a cluster system
Chang et al. The designs of RAID with XOR engines on disks for mass storage systems
Prabhakaran Multimedia Storage and Retrieval
Streaming 16th Very Large Data Bases Conference, pages 162 {173, 1990. Mou95] Antoine Mourad. Reliable disk striping in video-on-demand servers. In Proceedings of the Inter-national Conference on Distributed Multimedia
Golubchik et al. Fault tolerance issues in multidisk video-on-demand storage servers
JPH10283295A (ja) データ転送システム、及びそのデータ転送方法
Furht Seon Ho Kim 2
Shim Supporting I/O-intensive applications in a high performance storage system