[go: up one dir, main page]

JP2002529878A - 記憶システム - Google Patents

記憶システム

Info

Publication number
JP2002529878A
JP2002529878A JP2000580372A JP2000580372A JP2002529878A JP 2002529878 A JP2002529878 A JP 2002529878A JP 2000580372 A JP2000580372 A JP 2000580372A JP 2000580372 A JP2000580372 A JP 2000580372A JP 2002529878 A JP2002529878 A JP 2002529878A
Authority
JP
Japan
Prior art keywords
blocks
storage
data unit
data
storage units
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
JP2000580372A
Other languages
English (en)
Inventor
ハー エム コルスト，ヨハネス
エフ アー コウマンス，パスカル
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.)
Koninklijke Philips NV
Original Assignee
Philips Electronics NV
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 Philips Electronics NV filed Critical Philips Electronics NV
Publication of JP2002529878A publication Critical patent/JP2002529878A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
    • H04N21/231—Content storage operation, e.g. caching movies for short term storage, replicating data over plural servers, prioritizing data for deletion
    • H04N21/2312—Data placement on disk arrays
    • H04N21/2318—Data placement on disk arrays using striping
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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; CALCULATING OR 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
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/061—Improving I/O performance
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/064—Management of blocks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0683—Plurality of storage devices
    • G06F3/0689—Disk arrays, e.g. RAID, JBOD
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/21—Server components or server architectures
    • H04N21/218—Source of audio or video content, e.g. local disk arrays
    • H04N21/21815—Source of audio or video content, e.g. local disk arrays comprising local storage units
    • H04N21/2182—Source of audio or video content, e.g. local disk arrays comprising local storage units involving memory arrays, e.g. RAID disk arrays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
    • H04N21/232—Content retrieval operation locally within server, e.g. reading video streams from disk arrays
    • H04N21/2326—Scheduling disk or memory reading operations

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Signal Processing (AREA)
  • Human Computer Interaction (AREA)
  • Multimedia (AREA)
  • Databases & Information Systems (AREA)
  • Quality & Reliability (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Television Signal Processing For Recording (AREA)
  • Signal Processing For Digital Recording And Reproducing (AREA)
  • Indexing, Searching, Synchronizing, And The Amount Of Synchronization Travel Of Record Carriers (AREA)

Abstract

(57)【要約】 ビデオオンデマンドシステムのような記憶システムはディスクドライブのような複数の記憶ユニットからなる。記憶ユニットの各々は相互に異なる予想されたデータ検索時間を有する多数の記憶ゾーンを有する。データはデータユニットに記憶され、各データユニットはＮ個のブロックからなり、ここでＮ≧２である。データユニットのブロックは記憶ユニットにわたり分布される。ブロックはＮ個のブロックのＮ−Ｋからなる複数の選択のいずれの一つもデータユニットを検索するために満足され、ここでＫ≧１である。記憶ユニットからデータユニットを検索するために、リーダーは選択過程に基づいて検索するためにＮ個のブロックのどのＮ−Ｋかを決定する。選択過程は帯域幅利用を最適化するために予想されたデータ検索時間を考慮に入れる。

Description

【発明の詳細な説明】
【０００１】 本発明はビデオ又はオーディオデータのようなデータのブロックを記憶する複
数の記憶ユニットと複数の記憶ユニットからブロックを検索するリーダーとから
なるビデオオンデマンドのような記憶システムに関する。
【０００２】 ビデオオンデマンドシステムは論文“Ｒａｎｄｏｍｉｚｅｄ ｄａｔａ Ａｌ
ｌｏｃａｔｉｏｎ ｆｏｒ Ｒｅａｌ−ｔｉｍｅ Ｄｉｓｋ Ｉ／Ｏ”，Ｃｏｍ
ｐｃｏｎ‘９６(４１ｓｔ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｉｎ
ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ，Ｓａｎｔａ Ｃｌａｒａ，２
５−２８ Ｆｅｂｒ，１９９６)から知られている。知られているシステムでは
、データユニットは各々がディスク上で一のフルトラックを占有する一群のＧブ
ロックを形成するＧディスク上にストライプされる。Ｇディスクのこの群はＤの
利用可能なディスクの組からランダムに選択される。Ｇブロックの一つはパリテ
ィブロックである。群のランダムな分布からディスク上のロードのバランスが得
られる。ランダムパリティブロックは更なるロードバランスを可能にし、これは
ロードを最小化する一群のＧブロックの（Ｇ−１）ブロックのみを読みとること
により達成される。読まれなかったブロックがデータブロックである場合にはパ
リティブロックは読まれなかったブロックを再構成するために用いられる。
【０００３】 本発明の目的は請求項の前半に規定されるような記憶システムを提供すること
にあり、これはディスクの帯域幅をより効率的に用いることである。この目的の
ために、本発明は請求項１に規定される記憶システムを提供する。
【０００４】 データの検索に対して記憶媒体に関して読み取りヘッドの動きを用いる記憶ユ
ニットでは、そのような記憶ユニットの一例はディスクドライブであるが、デー
タのある部分の予想された検索時間は第一の成分として例えばトラック内の右の
トラック及び右の位置である右位置でヘッドを位置決めするために要求されるス
イッチ時間と、第二の成分として実際の読み取り処理に対して必要な時間とから
なる。連続データの大きな量が一度に読み込まれたと仮定する場合に、一つのデ
ータの予想される検索時間はこの第二の成分により大幅に決定される。ほとんど
の記憶ユニットで、データの任意の一つを実際に読み取るために必要とされる時
間は記憶空間内のその一つのデータの場所に依存する。例えばディスクドライブ
では外側のトラックの記憶容量は内側トラックよりも高い。現在のディスクドラ
イブでは、トラック容量は連続的ではなく段階的に変化し、それにより、記憶ゾ
ーンの限定された数が典型的には十から二十のオーダーで識別され、それらの各
々で、すべてのトラックが等しい記憶容量を有する。ディスクドライブの一定の
角速度の観点からディスクドライブのスピンドルに近接した記憶ゾーンに記憶さ
れたブロックの予想される検索時間はディスクドライブの外周部近くの記憶ゾー
ンに記憶されたブロックより高い。本発明によれば、選択手順は予想された検索
時間を考慮に入れて用いられ、これは検索に対して低く予想された検索時間を有
する好ましい選択ブロックにより利用可能なディスク帯域幅のより効率的な使用
を可能にする。これはディスク帯域幅が記憶容量の代わりにシステムボトルネッ
クを決定するビデオサーバーに対して特に好ましい。ディスク帯域幅のより効率
的な使用によりまたより厳しくないバッファ要求及びより良い応答時間が得られ
る。
【０００５】 好ましくは選択過程は複数の記憶ユニットでのロード分布を更に考慮に入れる
。このようにして、冗長な情報により提供された自由度はロードバランスと用い
られる帯域幅の改善の両方を同時に達成するために用いられる。更なる利点はデ
ータユニットの最少全体検索時間の一のデータユニットから他への変動はより少
ない。選択過程は各リクエストされたユニットそれぞれでなされ、この場合には
選択過程は他のデータユニットを参照することなしにある基準により最適な選択
を決定するよう試行する。或いは選択過程は提供をペンディングされたデータユ
ニットのバッチでなされる。後者の方法で、自由度は帯域幅利用をロードバラン
スし及び／又は改善するためにすら、より良く用いられうる。例えば、特定のデ
ータユニットに対して最適である選択はロードバランスの観点からそれに続くデ
ータユニットに対して問題を引き起こすことがある。そのような場合には、選択
過程に対して、一度に多数のデータユニットにアドレスすることがより好ましい
。
【０００６】 任意の時点で、各記憶ユニットは記憶ユニットから検索されるのを待つそれぞ
れのブロックに対する読み取りリクエストのエンプティ又はエンプティでないキ
ューを有する。考慮に入れられるロード分布として、選択過程はキュー長さを開
始点とし、即ち、選択過程はキュー長さを均衡させることを目的とする。或いは
選択過程は実際のキュー長さを無視して、記憶ユニットにわたりデータの現在リ
クエストされたデータユニット又はバッチのロードを等しく分配するよう試行す
るのみである。両方の方法は選択過程がその時点でキュー長さがゼロである故に
、前のデータユニット又はデータユニットのバッチのブロックが検索された後に
なされたときには本質的に同一である。
【０００７】 本発明の更なる利点は従属請求項に記載されている。
【０００８】 本発明は又記憶システムのデータユニットを記憶する複数の記憶ユニット及び
ローダーからなる。本発明は更に複数の記憶ユニットからなるシステムのデータ
ユニットを検索する方法及び記憶方法に関する。
【０００９】 本発明のこれら及び他の特徴は以下の実施例を参照した詳細な説明から明らか
となる。
【００１０】 図面では、 図１は本発明によるシステムの概略図を示す。
【００１１】 図２は本発明のシステムで用いられる選択過程の第二の実施例の段階を示す。
【００１２】 図１は本発明によるシステムの概略図を示す。各水平バー１１０から１２０は
記憶ユニットの概略を示す。この実施例では、各記憶ユニット１１０から１２０
はディスクドライブであることが仮定されている。各記憶ユニット１１０から１
２０は６つの記憶ゾーンに副分割される。例えば記憶ユニット１１０は記憶ゾー
ン１２１から１２６からなる。各記憶ゾーン１２１から１２６は同一の記憶容量
を有する多数の円形トラックからなる。或いは各記憶ゾーン１２１から１２６は
概略同一の記憶容量を有する多数のトラックからなる。故に、記憶ゾーンとして
考えられるのは実際には一定の記憶容量の幾つかの物理的な記憶ゾーンの堆積（
collection）である。ディスクドライブの外周部近くに配置されたトラックはデ
ィスクドライブのスピンドルに近く配置されたトラックより高い記憶容量を有す
る。ディスクドライブの一定の角速度の観点からディスクドライブのスピンドル
に近接した記憶ゾーンに記憶されたブロックの予想される検索時間はディスクド
ライブの外周部近くの記憶ゾーンに記憶されたブロックより高い。図１では、予
想された検索時間は左から右へ減少すると仮定している。例えば、記憶ゾーン１
２１はスピンドル付近のトラックからなり、記憶ゾーン１２６は外周付近のトラ
ックからなる。
【００１３】 システム１００に記憶されたデータ（例えばムービー）は４ブロックのデータ
ユニットに配列される。各データユニットはデータの自己充足的（self-contain
ed）部分（例えばビデオフレーム）又はデータの特徴に関連した特定の関係を有
さず、データの固定された量のみに対応する。好ましくはブロックの大きさはト
ラックの整数番号である。通常、各ブロックは記憶ゾーンを部分的に満たすのみ
である。或いは記憶ゾーンの数又はブロックの大きさはブロック及び記憶ゾーン
が概略同一の大きさを有するように増加される。システム１００は更にブロック
を記憶ユニット１１０から１２０へ検索し、検索されたブロックをクライアント
に配布するリーダー１４０を含む。
【００１４】 データユニットを形成する４ブロックは記憶ユニット１１０から１２０にわた
りランダム又はランダムに近い形で分配される。図１で、任意の例示的データユ
ニットの４つのブロックからなる４つの記憶ゾーンは記憶ゾーン１２３、１２７
、１２８、１２９である。４つのブロックは４つのブロックのいずれの２つの検
索も例示的なデータユニットの検索に十分であるように冗長な情報からなる。故
に、例示的データユニットの検索に対して、合計で４ブロックからの６つの選択
がなされる。それにより、リーダー１４０では選択過程がある基準に基づいて検
索に対するその選択を決定することに責任を持つように設定される。データユニ
ットは正確に２つのみのブロックだけが検索される必要がある４つのブロックか
らなることは本発明に本質的ではない。本発明の文脈から、データユニットはＮ
≧２であるＮ個のブロックからなり、加えられた冗長性はＮ−Ｋブロックが検索
される必要があるようになされ、ここでＫ≧１である。
【００１５】 知られたシステムでは、ブロックの選択の自由度が又表され、記憶ユニット上
の一時的なロードをバランスする目的で用いられる。図１のシステムでは、記憶
ユニットにわたるブロックの多少のランダム分布により既に達成されたロードバ
ランスに加えて、更なるロードバランスが以下のように達成される。通常の動作
中に、各記憶ユニットは記憶ユニットから検索されるのを待機する各ブロックに
対する読み取りリクエストのエンプティ又はエンプティでないキューを有する。
ある時点で、記憶ユニット１１４が過重なロード下に置かれている、即ち、記憶
ユニット１１４に対する読み取りリクエストのキューが他の記憶ユニット１１０
、１１２、１１６−１２０のそれより長いことを想定する。例示的なデータユニ
ットに対して記憶ユニット１１４が含まれていない３つの選択のどの一つを選択
することもバランスしたロードを達成するために記憶ユニット１１４のキューが
更に成長することを防止する。そのような選択は、例えば、記憶ゾーン１２３に
記憶されたブロック、及び記憶ゾーン１２８に記憶されたブロックからなる。選
択の自由度を有することの更なる利点は記憶ユニット１１０から１２０が故障又
は置き換えられたプロセスにある場合にも、システム１００はなおデマンドに対
して協働可能であり、即ち、リクエストされたデータユニットを配布することが
できる。ロードバランスに対して、記憶ユニット１１０から１２０のいずれもデ
ータユニット当たり一以上のブロックを含まず、それにより代替的なブロックの
数は最大である。本発明の文脈で、データユニット当たりのブロック数はシステ
ム内の記憶ユニットの数と等しく、この場合に対応する冗長データを含むデータ
ユニットはすべての記憶ユニットにわたりストライプ化される。
【００１６】 本発明の特徴によれば、選択の自由度はシステムの帯域幅を増加するために更
に用いられる。それにより、選択過程は記憶ゾーンのより速いもののブロックに
対して、即ちディスクドライブの外周に最も近接した可能な４つのブロックのそ
れらのブロックに対して利点を有する。換言すると、選択過程はブロックの予想
される検索時間をあれこれと考慮に入れる。例えば、例示的なデータユニットを
検索するために選択過程は記憶ゾーン１２７に記憶されたブロック及び記憶ゾー
ン１２９に記憶されたブロックを選択する。
【００１７】 好ましくは選択の自由度はロードバランス及び帯域幅の両方の同時の最適化に
対して用いられる。それに対して、選択過程はさらに該複数の記憶ユニットの一
時的なロード分布を考慮に入れる。図１の例示的なデータユニットを検索するこ
とに対して、実際の記憶ユニット１１４が相対的に高いロードの下にあるときに
好ましいシステムは記憶ゾーン１２３、１２９の２つのブロックを検索するため
に例えば選択され、それにより記憶ユニット１１４を緩和するのみならず、シス
テム帯域幅利用を改善し、即ちデータユニットの全検索時間を最小化する。両方
の目的を達成する選択過程の幾つかの可能な実施例は良い結果が得られた。第一
の実施例は以下のように動作する。まず、選択過程が最も過酷に用いられた記憶
ユニットを廃棄する選択候補の数を減少する。次に残りの３つの選択候補から比
較的ブロックの多い数がより速い記憶ゾーンに配置される選択が選択される。よ
り一般的には、データユニットを形成するＮ個のブロックの内からＬ（Ｌ＜Ｋ）
ブロックがロードバランスに対して廃棄され、それに続いて、残りのＮ−Ｌブロ
ックの最も遅い（Ｋ−Ｌ）ブロックがシステム帯域幅を最適化するために廃棄さ
れる。
【００１８】 図２は本発明のシステムで用いられうる選択過程の第二の実施例の段階を示す
。ロードバランスのために、これは各データユニットにそれぞれアドレスするの
ではなく一度にデータユニットリクエストのバッチに選択過程を適用するために
一般的に好ましい。これは国際出願ＰＣＴ／ＩＢ９８／００７２０及び対応する
米国特許出願０９／０８３６９３（ＰＨＮ１６３７５）で説明され、ここではま
たそのような多数のロードバランス選択過程が又示され、それは多数のデータユ
ニットを同時に考慮に入れる。これらの選択過程は以下のような方法で新たな選
択過程を形成するよう本発明と結合される。第一段階で、ロードバランスは例え
ば上記の国際出願ＰＣＴ／ＩＢ９８／００７２０の選択過程の一つであるような
任意のロードバランス選択により達成される。第二段階では、各ディスクのロー
ドを不変に保つ間に、ディスクの外側トラックから読み取られたブロックの数を
増加することが目的である。この第二の段階は以下のように実施される。第一の
段階で得られた初期選択を与えるために、方向付け重み付けグラフが構成され、
ここで各ディスクドライブ１１０から１２０はノードとして表される。そのよう
なグラフの例は図２に示される。更にまた、第一のデータユニットのブロックは
図１の例示的なデータユニットのブロックと同様に分布され、これはグラフにノ
ード１１０、１１４、１１８の下にダッシュにより示され、ダッシュはこれらの
記憶ユニットが第一のデータユニットのブロックを含むことを示す。同様に、第
二のデータユニットは記憶ユニット１１０、１１４、１１８、１２０に含まれた
ブロックと共に表されると仮定され、これは図２に関連するノード１１０、１１
４、１１８、１２０上のダッシュにより示される。更にまた第一の段階の後に、
ロードバランスの観点から受容可能な初期的な選択が存在し、この選択は記憶ユ
ニット１１０から１１６（図２に円により示される）から第一のデータユニット
を検索し、記憶ユニット１１８から１２０（図２に三角により示される）から第
二のデータユニットを検索することを含む。
【００１９】 グラフは更に４つの初期的な選択されたブロックの各一つに対してノードｖか
らｗへの３つの矢印（ｖ、ｗ）からなり、ここでノードｖは選択されたブロック
を含み、ノードｗは関連するデータユニットの代替的なブロックを含む３つのノ
ードの一つである。例えば３つの矢印はノード１１０を離れ、それぞれノード１
１４から１１８へ向かい、後者は第一のデータユニットの他のブロックを含む。
各矢印（ｖ、ｗ）に対して重みはデータユニットを検索するためにノードｖの代
わりにノードｗを用いることにより増加されるものを表すように属性を付与され
る。これにより記憶ユニットの各記憶ゾーンは序数１から６を与えられ、これら
は予想されるデータ検索時間と共に増加する。重みは記憶ゾーンに関連するノー
ドの序数間の差と考えられ、これらの重みは矢印の隣に示される。例えばノード
１１０からノード１１８への矢印は重み２を有し、一方第一のデータユニットの
ブロックを含む記憶ユニット１１０の記憶ゾーンが序数３を有し、第一のデータ
ユニットのブロックを含む記憶ユニット１１８の記憶ゾーンが序数５を有し、こ
れは図１に示される。更に、第二のデータユニットに関するブロックが各記憶ユ
ニットの最も遅い記憶ゾーンにすべて配置されると仮定される。これにより、第
二のデータユニットに関する矢印の重みがゼロである結果を生じ、この重みは明
確に示すために図２の左の外にある。矢印に重みを付与する多くの代替的な方法
は本発明の原理から離れることなく可能である。
【００２０】 サイクルは矢印｛（ｖ１，ｖ２），（ｖ２，ｖ３），．．．（ｖｋ，ｖ１）｝
の閉じた連続である。矢印に沿った重みの和が正であるサイクルはより速い記憶
ゾーンから読み出されたブロックの数の増加を生ずるために矢印に沿って一ブロ
ックを“転送”することにより初期検索選択の調整に対応する。明らかに、各デ
ィスクのロードは変化せず、何故ならば、交換に含まれる各ディスクはなお同数
のブロックを検索しなければならないからである。交換をなした後に、グラフは
次のように調整されなければならない：交換に含まれる各矢印（ｖ、ｗ）は矢印
（ｗ，ｖ）により置き換えられ、ここで新たな矢印の重みは消去された矢印の重
みの否定（negation）である。
【００２１】 図２の簡単な例では、記憶ユニット１１０、１１８のみがこれらが両方のデー
タユニットのブロックを含む次の第一の段階で選択された記憶ユニットのみであ
るようなスワップ処理で用いられうる。故に、ロード分布を変化することなく帯
域幅使用を増加するためになされる唯一のスワップは太い矢印により示されるス
ワップであり、即ち、第一のデータユニットは記憶ユニット１１０からの代わり
に記憶ユニット１１８からブロックを読み取り、第二のデータユニットに対して
も逆も成立する。より多くのデータユニットが同時に考慮されるときに、問題は
即座に解決するためには複雑すぎ、サイクルの捜索は自動化しなければならない
。上記の戦略は種々の方法で実施されうる。例えば、与えられた最大長さのサイ
クルに対する捜索を限定することも考えられる。或いはグラフ表現も又可能であ
り、ここで２つのノードｖ、ｗの間で、唯一の（方向付けられていない）“矢印
”を有し、それは４つの重み表現を有する：（１）ｗのより速い記憶から検索さ
れうるｖから検索されたブロックの数、（２）ｗのより遅い記憶ゾーンから検索
されうるｖから検索されたブロックの数、（３）ｖのより速い記憶ゾーンから検
索されうるｗから検索されたブロックの数、（４）ｖのより遅い記憶から検索さ
れうるｗから検索されたブロックの数。
【００２２】 上記選択過程で、それがデータユニットに対応する４ブロックのどの２つの検
索に対しても十分なまでデータユニットを検索することが仮定されている。より
簡単な実施はシステムに記憶されたデータユニットの２つのブロックの各一つの
２つのコピーを記憶することからなる。換言すると、各データユニットは対とし
て同一である４つのブロックからなる。これはデータユニットの大きさＮを２に
減少し、ランダムブロックＫの数を１に減少し、データユニットのブロックは相
互にコピーされる。図２のグラフから、矢印の数はデータユニットのすべてのブ
ロックがもはや相互に交換されないように消去されなければならない。状況（Ｎ
，Ｋ）＝（２，１）の場合は上記国際出願ＰＣＴ／ＩＢ９８／００７２０に詳細
に記載されている。
【００２３】 上記選択過程では、ロードバランス及びシステム帯域幅利用の改善は２つの別
の段階で達成される。本発明のシステムで用いられる選択過程の第三の実施例は
唯一の段階しか要求しない。これに関して、選択過程はブロックの位置を考慮に
入れた変更されたキュー長さに基づいて選択される。キューの各エントリは予想
されたより悪い場合の検索時間に対して考慮するよう重み付けられる。例えば、
スピンドル付近のブロックに対する読み取りリクエストは外周部分に近いブロッ
クに対するリクエストより重い重みを有する。これらの（Ｎ−Ｋ）ブロックは最
少の変更されたキュー長さで記憶ユニットに記憶されるよう選択される。或いは
データユニットのバッチが選択過程により同時に取り扱われるときに、選択され
たブロックは変更されたキュー長さの均衡化（leveling）を達成するものであり
、それにより記憶ユニットの一時的に変更されたキュー長さ、又はそれらの間の
記憶ユニットにわたり均衡な分布を有するものを考慮に入れる。上記国際出願Ｐ
ＣＴ／ＩＢ９８／００７２０の例のようなロードバランス選択過程のどの種類も
ロードバランス及び最適帯域幅利用を同時に達成するためにここに記載されたよ
うに変更される。
【００２４】 本発明による記憶システムの性能は大部分ロード戦略、即ちデータが複数の記
憶ユニット上に記憶される方法により決定されることは明らかである。ローダー
はシステム内に記憶されるデータをＮの記憶されるブロックに変換するタスクを
有し、それによりＮ−Ｋブロックのみがデータユニットを検索するよう検索され
る必要があるように冗長なデータをブロックに含み、記憶ユニットの異なる一つ
に記憶されるＮ個のブロックの各一つに記憶される。ロードバランスの観点から
既に指摘したように、それはＮ個のブロックをＮの異なる記憶ユニットにランダ
ム又は疑似ランダムに分配するために好ましい。本発明の観点で、Ｎ個のブロッ
クをデータユニットのブロックがデータ検索時間がより多く予測された記憶ゾー
ン及びより少なく予測された記憶ゾーンにわたり多少とも等しく分布されるよう
にＮ個のブロックを分配する間に予想されたデータ検索時間を考慮に入れること
は更なる利点である。これは同様に記憶ゾーンをランダム又は疑似ランダムに選
択することにより達成されうる。或いは各データユニットのブロックはあるアル
ゴリズムによりより遅い及びより速いゾーンにわたり注意深く分配される。
【００２５】 例えば、各データユニットが相互に協働する２つのブロックからなる（即ちＮ
＝２、Ｋ＝１）場合に、ローダーは第一のブロックをディスクドライブの内側ト
ラックの一つに記憶し第二のブロックを外側トラックの一つに記憶する。この例
で、選択過程は内側トラックの群と外側トラックの群とをそれぞれ考慮する記憶
ゾーンが物理的な記憶ゾーンと実際には一致していないが、ディスクドライブの
後者は通常丁度２よりも大きい数からなる。選択過程は一度にデータユニットの
バッチを考慮すると仮定した場合にそれは外側のトラックのできるだけ多くのブ
ロックを選択しようと試み、同時に、ロードバランスを達成するよう試みる。こ
れにより、本発明による選択過程は任意のロードバランスアルゴリズムに基づき
、これは異なる記憶ゾーンの予想された検索時間が考慮されるように提供される
。例えば、外側トラック（外側ブロック）のブロックの予想された検索時間は内
側トラック（内側ブロック）のブロックの予想された検索時間の４／５である場
合には、選択過程は記憶ユニット当たりのブロックの最大数を最小化するように
試みる代わりに、内側ブロック及び外側ブロックの数の重み付けられた和を最小
化するように試みる。それにより内側ブロックは重み５を外側ブロックは重み４
を得る。ここで幾つかの異なる選択により同一の重み付けられた和が得られる。
例えば４つの内側ブロック及び５つの外側ブロックが４０の重み付けられた和を
有するが、また８つの内側ブロック又は１０の外側ブロックが重み付けられた和
を有する。更なる詳細として、スイッチ時間がより少ない故により少ないブロッ
クを読み取ることが好ましいことを考慮に入れる。内及び外側ブロック間の明ら
かな識別により、最悪のスイッチ時間が生ずる場合はより少ない。これは更に帯
域幅利用を改善する。余分の獲得された帯域幅利用はより少ないバッファリング
に変換されうる。
【００２６】 上記の実施例は本発明を制限するものではなく、例示のためであり、請求項の
範囲から離れることなく多くの代替実施例を設計することは当業者には明らかで
ある。請求項では、括弧内の如何なる符号も請求項を制限するものではない。本
発明は幾つかの異なる要素からなるハードウエア手段及び適切にプログラムされ
たコンピュータにより実施される。幾つかの手段を列挙する装置請求項では、こ
れらの手段の幾つかは一及び同一のハードウエアアイテムにより実施されうる。
【図面の簡単な説明】
【図１】 本発明によるシステムの概略図を示す。
【図２】 本発明のシステムで用いられる選択過程の第二の実施例の段階を示す。
───────────────────────────────────────────────────── フロントページの続き (71)出願人 Ｇｒｏｅｎｅｗｏｕｄｓｅｗｅｇ １， 5621 ＢＡ Ｅｉｎｄｈｏｖｅｎ， Ｔｈ ｅ Ｎｅｔｈｅｒｌａｎｄｓ Ｆターム(参考） 5C052 AA01 AB03 AC08 DD04 DD06 5C053 FA20 FA23 FA28 GB06 GB11 HA29 JA01 JA21 5D044 AB05 AB07 BC01 CC05 DE03 DE25 DE53 DE72 DE92 5D077 AA22 BA18 CB04 EA04 EA31 EA35

Claims (7)

    【特許請求の範囲】
  1. 【請求項１】 複数の記憶ユニットと； 該複数の記憶ユニットからデータユニットを検索するリーダーとからなり、 該複数の記憶ユニットのそれぞれ一つは相互に異なる予想されたデータ検索時間
    を有する複数の記憶ゾーンからなり、少なくとも一つのデータユニットは該複数
    の記憶ユニットに記憶され、該データユニットはＮ個のブロックからなり（Ｎ≧
    ２）、このブロックはＮ個のブロックの内のＮ−Ｋからなる複数の選択のどの一
    つもデータユニットを検索するために満足される（Ｋ≧１）ように冗長な情報か
    らなり、 リーダーは選択過程に基づいて該複数の選択の特定の一つを決定するように配置
    され、選択過程は該予想されたデータ検索時間を考慮に入れる記憶システム。
  2. 【請求項２】 Ｎ個のブロックが該記憶ユニットのＮ個の異なる一つに記憶
    され、選択過程は更に該複数の記憶ユニットの一時的なロード分布を更に考慮に
    入れる請求項１記載の記憶システム。
  3. 【請求項３】 第一段階で選択過程がロードバランスを目的とし、第二段階
    で帯域幅利用を改善することを目的とする請求項２記載の記憶システム。
  4. 【請求項４】 選択過程はシステムのその時点と、予想された検索時間の両
    方を考慮に入れる請求項２記載の記憶システム。
  5. 【請求項５】 複数の記憶ユニットと； 該複数の記憶ユニットにデータユニットを記憶するローダーとからなり、 該複数の記憶ユニットのそれぞれ一つは相互に異なる予想されたデータ検索時間
    を有する複数の記憶ゾーンからなり、 該ローダーは該データユニットをＮ個のブロックに変換するために配置され（Ｎ
    ≧２）、該ブロックはＮ個のブロックのＮ−Ｋからなる複数の選択のどの一つも
    データユニットを検索するために満足される（Ｋ≧１）ように冗長な情報からな
    り、各記憶ユニットは多くとも該Ｎ個のブロックの一つからなり、該Ｎ個のブロ
    ックが該記憶ゾーンのより速い及びより遅い一つの中で少なくとも概略等しいよ
    うに分布されるように該複数の記憶ユニットに該Ｎ個のブロックを記憶する記憶
    システム。
  6. 【請求項６】 複数の記憶ユニットからなり、該複数の記憶ユニットのそれ
    ぞれ一つは相互に異なる予想されたデータ検索時間を有する複数の記憶ゾーンか
    らなり、少なくとも一つのデータユニットは該複数の記憶ユニットに記憶され、
    該データユニットはＮ個のブロックからなり（Ｎ≧２）、このブロックはＮ個の
    ブロックのＮ−Ｋからなる複数の選択のどの一つもデータユニットを検索するた
    めに満足される（Ｋ≧１）ように冗長な情報からなり、 該複数の選択の特定の一つを決定し、それにより該予想されたデータ検索時間
    を考慮に入れ； その特定の選択に関するブロックを検索する各段階からなるシステムからデー
    タユニットを検索する方法。
  7. 【請求項７】 複数の記憶ユニットからなり、該複数の記憶ユニットのそれ
    ぞれ一つは相互に異なる予想されたデータ検索時間を有する複数の記憶ゾーンか
    らなり、 該データユニットをＮ個のブロックに変換し（Ｎ≧２）、このブロックはＮ個
    のブロックのＮ−Ｋからなる複数の選択のどの一つもデータユニットを検索する
    ために満足される（Ｋ≧１）ように冗長な情報からなり、 各記憶ユニットが多くとも該Ｎ個のブロックの一つであり、該Ｎ個のブロック
    は該記憶ゾーンのより速い及びより遅い一つの中で少なくとも概略均等に分配さ
    れるように該複数の記憶ユニットに該Ｎ個のブロックを記憶する各段階からなる
    システムのデータユニットを記憶する方法。
JP2000580372A 1998-10-30 1999-10-05 記憶システム Pending JP2002529878A (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
EP98203681 1998-10-30
EP98203681.6 1998-10-30
PCT/EP1999/007498 WO2000027108A1 (en) 1998-10-30 1999-10-05 Storage system

Publications (1)

Publication Number Publication Date
JP2002529878A true JP2002529878A (ja) 2002-09-10

Family

ID=8234282

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2000580372A Pending JP2002529878A (ja) 1998-10-30 1999-10-05 記憶システム

Country Status (4)

Country Link
US (1) US6446162B1 (ja)
EP (1) EP1046280A1 (ja)
JP (1) JP2002529878A (ja)
WO (1) WO2000027108A1 (ja)

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6657070B2 (en) 2000-12-13 2003-12-02 Wyeth Production of chirally pure α-amino acids and N-sulfonyl α-amino acids
JP3950720B2 (ja) * 2002-03-18 2007-08-01 株式会社日立製作所 ディスクアレイサブシステム
US7761678B1 (en) 2004-09-29 2010-07-20 Verisign, Inc. Method and apparatus for an improved file repository
US9071608B2 (en) * 2008-04-28 2015-06-30 International Business Machines Corporation Method and apparatus for load balancing in network based telephony application
US8862847B2 (en) 2013-02-08 2014-10-14 Huawei Technologies Co., Ltd. Distributed storage method, apparatus, and system for reducing a data loss that may result from a single-point failure
CN103984607A (zh) * 2013-02-08 2014-08-13 华为技术有限公司 分布式存储的方法、装置和系统
US20140281157A1 (en) * 2013-03-13 2014-09-18 Kabushiki Kaisha Toshiba Memory system, memory controller and method

Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH046672A (ja) * 1990-04-25 1992-01-10 Canon Inc 情報記録方法
JPH0756691A (ja) * 1993-08-12 1995-03-03 Toshiba Corp ストライピングディスクのデータブロック自動再配置機能を持つ情報処理装置
JPH0869359A (ja) * 1994-08-29 1996-03-12 Hitachi Ltd ディスクアレイ装置
JPH08115172A (ja) * 1994-10-18 1996-05-07 Fuji Xerox Co Ltd ディスクアレイ装置
JPH0926854A (ja) * 1995-04-28 1997-01-28 Hewlett Packard Co <Hp> データを格納し供給するサーバー・システム
JPH0970013A (ja) * 1995-03-27 1997-03-11 Hewlett Packard Co <Hp> ビデオ・データ・レイアウト方法およびシステム
JPH09154109A (ja) * 1995-05-22 1997-06-10 Sun Microsyst Inc ビデオサーバシステムに於いて平均的なシーク時間及びバンド幅を達成するための方法及びシステム
JPH09198194A (ja) * 1995-12-18 1997-07-31 Symbios Logic Inc ディスクのゾーンに基づいてビデオ・データを配置するための方法および装置
JPH09305328A (ja) * 1996-05-13 1997-11-28 Fujitsu Ltd ディスクアレイ装置

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5287459A (en) * 1991-10-03 1994-02-15 International Business Machines Corporation Method and apparatus for reducing response time in automated library data retrieval systems
US5926649A (en) * 1996-10-23 1999-07-20 Industrial Technology Research Institute Media server for storage and retrieval of voluminous multimedia data
EP0919035B1 (en) * 1997-05-26 2005-07-27 Koninklijke Philips Electronics N.V. System for retrieving data in a video server

Patent Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH046672A (ja) * 1990-04-25 1992-01-10 Canon Inc 情報記録方法
JPH0756691A (ja) * 1993-08-12 1995-03-03 Toshiba Corp ストライピングディスクのデータブロック自動再配置機能を持つ情報処理装置
JPH0869359A (ja) * 1994-08-29 1996-03-12 Hitachi Ltd ディスクアレイ装置
JPH08115172A (ja) * 1994-10-18 1996-05-07 Fuji Xerox Co Ltd ディスクアレイ装置
JPH0970013A (ja) * 1995-03-27 1997-03-11 Hewlett Packard Co <Hp> ビデオ・データ・レイアウト方法およびシステム
JPH0926854A (ja) * 1995-04-28 1997-01-28 Hewlett Packard Co <Hp> データを格納し供給するサーバー・システム
JPH09154109A (ja) * 1995-05-22 1997-06-10 Sun Microsyst Inc ビデオサーバシステムに於いて平均的なシーク時間及びバンド幅を達成するための方法及びシステム
JPH09198194A (ja) * 1995-12-18 1997-07-31 Symbios Logic Inc ディスクのゾーンに基づいてビデオ・データを配置するための方法および装置
JPH09305328A (ja) * 1996-05-13 1997-11-28 Fujitsu Ltd ディスクアレイ装置

Also Published As

Publication number Publication date
WO2000027108A1 (en) 2000-05-11
EP1046280A1 (en) 2000-10-25
US6446162B1 (en) 2002-09-03

Similar Documents

Publication Publication Date Title
JP3308814B2 (ja) ビデオサーバシステムに於いて平均的なシーク時間及びバンド幅を達成するための方法及びシステム
US6233607B1 (en) Modular storage server architecture with dynamic data management
KR100377092B1 (ko) 다중 사용자 데이터 분배 시스템내 저장장치 서브세트상에 데이터 스트림을 스트라이핑하는 방법
US5915094A (en) Disk access method for delivering multimedia and video information on demand over wide area networks
US6061732A (en) Data streaming system utilizing an asynchronous technique for retrieving data from a stream server
US5510905A (en) Video storage server using track-pairing
US5721950A (en) Method for scheduling I/O transactions for video data storage unit to maintain continuity of number of video streams which is limited by number of I/O transactions
US6240243B1 (en) Method and apparatus for storing and retrieving scalable video data in a disk-array-based video server
US5732239A (en) Method for operating a disk storage system which stores video data so as to maintain the continuity of a plurality of video streams
JP3117390B2 (ja) 複数のディスク間でデータ・セットを分配する方法及び関連する装置・方法
JP2902975B2 (ja) メモリバッファ管理方法及びシステム
EP0740247A2 (en) Data stream server system
US20030103055A1 (en) Digital video recorder file system
US5758151A (en) Serial data storage for multiple access demand
US6415328B1 (en) System for retrieving data in a video server
JP2002528817A (ja) シームレスな拡張容易性分散型メディアサーバ
JP2002529878A (ja) 記憶システム
KR20020019597A (ko) 저장 매체로부터 블록들을 판독하는 방법 및 시스템
US6678469B1 (en) Recorded information reproducing apparatus
CN1574052A (zh) 将可交换存储装置用于存储节目数据的系统和方法
US20060167959A1 (en) Storing programs on disk for multiple-user retrieval
JPH0285962A (ja) 画像データ検索システム
KR100444524B1 (ko) 비디오서버의대화형편집기능지원방법
TW402700B (en) Method of allocating the service request
JPH10191299A (ja) データ配送用サーバ装置

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20061002

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20070614

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20070626

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20071120