(57)【要約】【課題】行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法を提供する。【解決手段】行列ストライプキャッシュ（ＭＳＣ）によって入出力を行単位で決定した後、列単位で各要素を読出しと書込み毎に結合を試みて入出力の数を減らして断片化された書込みの性能を向上させ、低下モードの小さな読出し性能を犠牲にして一般モードの読出し性能を向上させる。本発明は、ディスクに書込みを行う単位ＭＳＣから行結合前の読出し書込み行列であるｒｘｗ行列を生成し、第１ステップで生成された行結合前ｒｘｗ行列から行結合によって最終読出し書込み行列である行結合されたｒｘｗ行列を生成し、第２ステップで生成された行結合されたｒｘｗ行列をパターンとして読出しを実行し、行結合されたｒｘｗ行列の各行毎にＸＯＲ演算を実行し、行結合されたｒｘｗ行列の各列毎に書込みを実行する。【選択図】図４
2008004069.tif 000002
【特許請求の範囲】
【請求項１】
ＲＡＩＤシステムの入出力性能を向上させる方法において、ディスクに書込みを行う単位ＭＳＣから行結合前の読出し書込み行列であるｒｘｗ行列を生成する第１ステップと、前記第１ステップで生成された行結合前ｒｘｗ行列から行結合によって最終読出し書込み行列である行結合されたｒｘｗ行列を生成する第２ステップと、前記第２ステップで生成された行結合されたｒｘｗ行列をパターンとして読出しを実行した後、前記行結合されたｒｘｗ行列の各行毎にＸＯＲ演算を実行し、行結合されたｒｘｗ行列の各列毎に書込みを実行する第３ステップと、を含むことを特徴とする行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項２】
前記単位ＭＳＣがストライプサイズのキャッシュであることを特徴とする請求項１に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項３】
前記第１ステップにおける行結合前ｒｘｗ行列の生成が各行毎に生成されることを特徴とする請求項１に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項４】
前記第２ステップにおける行結合が、前記行結合前ｒｘｗ行列の中の読出しだけが含まれた読出し行列において、列毎に読出し要素と読出し要素の間の要素に必ず読出し動作があるように読出しを挿入し、かつ、前記行結合前ｒｘｗ行列の中で書込みだけ含まれた書込み行列において、書込み要素と書込み要素の間の要素に必ず書込み動作があるように書込みを挿入することを特徴とする請求項１に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項５】
前記行結合前ｒｘｗ行列で各列毎に読出し動作がある要素と他の読出し動作がある要素との間に、読出し動作がない要素の数があらかじめ決められた最大読出し距離値より大きい場合には読出し動作を挿入せず、また書込みの場合にも読出しの場合と同様に決められた最大書込み距離値より大きい場合には書込み動作を挿入しないことを特徴とする請求項４に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項６】
前記決められた最大読出し距離は、ＲＡＩＤを生成する時にＩＯ間隔による実行時間を測定して連続読出し性能より最初により速い性能を示すＩＯ間隔値であり、前記決められた最大書込み距離は、ＲＡＩＤを生成する時にＩＯ間隔による実行時間を測定して連続書込み性能より最初により速い性能を示すＩＯ間隔値であることを特徴とする請求項５に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項７】
ＲＡＩＤシステムの入出力性能を向上させる方法において、単位ＭＳＣの書込みが始まると、前記単位ＭＳＣに少なくとも一つ以上のダーティーブロックがあるかどうかを検査する第１ステップと、前記ダーティーブロックがあると判断されると前記単位ＭＳＣの各行毎に前記ダーティーブロックを使用するための動作を行結合前ｒｘｗ行列に記入する第２ステップと、前記行結合前ｒｘｗ行列の各列毎に、連結されていない読出しと読出しの間に読出しを挿入して、読出しと読出しの間の読出しがない要素の数が決められた最大読出し距離より大きければ、その間のすべての読出し結合を実行しない読出し結合を実行する第３ステップと、前記行結合前ｒｘｗ行列の各列毎に連結されていない書込みと書込みとの間に書込みを挿入し、書込みと書込みの間に書込みがない要素の数が決められた最大書込み距離より大きければ、書込みを挿入することを実行しない第４ステップと、前記第３及び第４ステップによって行結合されたｒｘｗ行列で読出しが一つ以上かどうかを検査して、一つ以上なら前記行結合されたｒｘｗ行列の各列毎に読出しを実行する第５ステップと、前記行結合されたｒｘｗ行列の各行毎にＸＯＲ演算を実行した後、前記行結合されたｒｘｗ行列の各列毎に書込みを実行する第６ステップと、を含むことを特徴とする行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項８】
前記単位ＭＳＣが、ストライプサイズのキャッシュであることを特徴とする請求項７に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項９】
前記決められた最大読出し距離が、ＲＡＩＤを生成する時にＩＯ間隔による実行時間を測定して連続読出し性能より最初により速い性能を示すＩＯ間隔値であり、前記決められた最大書込み距離はＲＡＩＤを生成する時にＩＯ間隔による実行時間を測定して連続書込み性能より最初により速い性能を示すＩＯ間隔値であることを特徴とする請求項７に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項１０】
前記第３ステップで、読出しを挿入する要素に該当するブロックがダーティーブロックなら目的メモリが臨時メモリである読出し動作を挿入し、そうでなければそのブロックの読出し動作を挿入することを特徴とする、請求項７に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項１１】
前記第４ステップで、書込みと書込みの間の書込みがない要素の中で、読出しがなくて該当のブロックが空のブロックである要素があれば、その間のすべての書込み結合を実行しないことを特徴とする、請求項７に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項１２】
ＲＡＩＤシステムの入出力性能を向上させる方法において、読出し要求が発生して読出しが開始すると、読出し要求が少なくとも二つ以上の単位ＭＳＣにかかるとその読出し要求を単位ＭＳＣ毎にいくつかの読出し要求に分離する第１ステップと、エラーのあるディスクがないかどうか検査する第２ステップと、前記第２ステップの検査の結果、エラーのあるディスクがなければ該当の単位ＭＳＣに空のブロックがあるかどうかを検査する第３ステップと、前記第３ステップの検査結果、空のブロックがある場合、該当の単位ＭＳＣが全体読出し実行中なのかどうかを検査する第４ステップと、前記第４ステップで全体読出し実行中と判断されると該当の単位ＭＳＣのブロッキングリストに該当の読出し要求を追加する第５ステップと、前記第４ステップで全体読出し実行中ではないと判断されると前記該当の単位ＭＳＣのすべての空のブロックに対する読出し書込み行列であるｒｘｗ行列を作って、前記行列をベースにディスク全体に読出しを実行する第６ステップと、前記第６ステップの全体読出し実行完了後、該当の単位ＭＳＣのブロッキングリストにある読出し要求のすべての読出しを終了させる第７ステップと、を含むことを特徴とする行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項１３】
前記単位ＭＳＣが、ストライプサイズのキャッシュであることを特徴とする請求項１２に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項１４】
前記第２ステップでエラーのあるディスクがないと判断されると読出し要求ごとに読出しブロックの中で前記単位ＭＳＣの空のブロックを読出し実行して読出しを終了することを特徴とする請求項１２に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【請求項１５】
前記第６ステップで前記生成されたｒｘｗ行列に対して全体読出し実行以前に読出し結合を実行することを特徴とする請求項１２に記載の行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＲＡＩＤ(Redundant Arrays of Inexpensive Disks)システムの入出力性能を向上させる方法に関するもので、特に行列ストライプキャッシュ（Matrix Stripe Cache：以下、ＭＳＣと略称する）によって入出力を行単位で決定した後、行列の各要素を列単位で、読出しと書込みに分けてそれぞれ結合させて入出力の数を減らすことにより、断片化された書込みの性能を向上させて、低下モード(degraded mode)の小さな読出し性能を犠牲にして一般モード(normal mode)の読出し性能を向上させるようにする行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法に関するものである。なお、「読出し結合」とはｒｘｗ行列の各列において読み出しが不連続となっている要素と要素との間のそれぞれの要素に読み出しを挿入することであって、「書込み結合」とは、同様にｒｘｗ行列の各列において書き込みが不連続となっている要素と要素の間のそれぞれの要素に書き込みを挿入することである。
【背景技術】
【０００２】
ＲＡＩＤシステムは、複数の独立したディスク保存装置を一つに集めてそれぞれのディスクにデータを分散収容して複数のディスクへ同時にアクセスできるようにすることによって入出力特性を向上させ、また、ホストコンピューターシステムとしては、複数の独立したディスク保存装置が一つのディスクのように見えるようにすることで、大容量保存装置の実現を可能にしている。
【０００３】
また、ディスク複製やエラー検査・訂正（Error Checking and Correction：ＥＣＣ）コードまたはパリティデータのような補助データを同時に収容することで、ＲＡＩＤシステム中のいずれか一つのディスクに故障が発生してもデータを自動的に復旧させることができる方法を提供することで、システムの有用性を高めることができる。
【０００４】
図１は、一般的なＲＡＩＤシステムの概略的な構成図である。ＲＡＩＤシステムは、システム本体と言えるホストシステム１０、ホストシステム１０に連結された多数のハードディスク３０、前記ホストシステム１０とハードディスク３０の間でハードディスク３０を管理するＲＡＩＤ制御器２０からなり、ＲＡＩＤ制御器２０内にはホストシステム１０とハードディスク３０との間の速度差を補うためのメモリ２１が含まれている。
【０００５】
また、ＲＡＩＤシステムは、構成形態によって様々なレベルに分けられ、パターソン等が発表した論文によれば、ＲＡＩＤシステムを五つの形態すなわち、ＲＡＩＤレベルを１から５に区分した。
【０００６】
まず、ＲＡＩＤレベル１は、Ｎ個のディスクにデータを保存して、また他のＮ個のディスクにデータを保存して、さらに他のミラー(Mirror)ディスクに同じデータをコピーして保存する形態である。データ書込み時にはいつも２個のディスクにデータを保存しなければならず、読出し時には二つのディスクの中でアクセス時間が早いディスクを選択してデータを読出すことができる。万一、一方のディスクに故障が発生すると、複製された他のディスクでサービスを継続することができる。
【０００７】
ＲＡＩＤレベル２は、ハミングコードを使用してデータを保護する方法で、ＲＡＩＤレベル１のミラー技法よりはディスクにかかる費用が少ない。
【０００８】
ＲＡＩＤレベル３は、Ｎ個で構成されたデータディスクグループに一つのパリティディスクを追加して構成した形態である。データの書込み時にはデータをビットあるいはバイト単位に分散させて各データをディスクに保存し、パリティディスクにはそれぞれデータディスクに保存されたデータに対して排他的論理和（ＥＸＯＲ）で演算されたパリティを保存する。読出し時には、Ｎ個のディスクを同時にアクセスしなければならない。また、万一一つのディスクに故障が発生すれば、パリティディスクに保存されたパリティデータを利用して情報を復旧させることができる。
【０００９】
ＲＡＩＤレベル４は、ＲＡＩＤレベル３のようにＮ＋１個のディスクからなり、Ｎ個のディスクにはデータを保存して、残り一つのディスクはパリティを保存する。但し、ＲＡＩＤレベル３と異なる点は、データをブロック単位に分散させて保存することである。したがって、データ書込み時には一つのデータディスクとパリティディスクのアクセスが必要であり、読出し時には一つのディスクだけアクセスすれば良い。そして、一つのディスクが故障した時にはパリティディスクに保存されたパリティを利用して情報を復旧させることができる。
【００１０】
ＲＡＩＤレベル５は、ＲＡＩＤレベル４と同様にデータをブロック単位で保存する形態であるが、パリティを一つのディスクに固定して保存しないでデータと一緒に各ディスクに分散させて保存する技法である。データを読み書きすること及び一つのディスクの故障時に対するデータ復旧方法もＲＡＩＤレベル４と同じである。
【００１１】
この外にも補助データを使わないで単純にデータだけを分散させて収容したＲＡＩＤレベル０と、リードソロモンコードを使用して、Ｐ＋Ｑエラー復旧方法を備えたＲＡＩＤレベル６がある。ＲＡＩＤレベル６は、同時に二つのディスクに故障が発生しても情報を復旧させることができるのでパリティを使用する方法よりシステムの有用性が高い形態である。現在、大部分のＲＡＩＤシステムは、ＲＡＩＤレベル０、１、３、５、そしてＲＡＩＤレベル０と１の複合形態であるＲＡＩＤレベル０／１をほとんどが支援していて、使用者の応用環境に適合した形態を選択して使用する。
【００１２】
一方、ＲＡＩＤレベル５等のパリティを伴うＲＡＩＤは、小さな書込みに対して非常に低い性能を見せる。これらを解決するため、デステージアルゴリズム等が研究されて来た。
【００１３】
デステージと言うのは、書込み要求があった時に書込むデータを直ちにディスクに伝達しないでキャッシュにコピーしておいてから、後でディスクで書き込むことを言う。デステージアルゴリズムとしては、ＷＯＷ(Wise Ordering for Write)、ＨＬＷＭ(High Low Water Mark)、ＬＣＳ(Least Cost Scheduling)等がある。
【００１４】
また、読出し性能を向上させるためにディスクの入出力の数を減らすためのキャッシュ置換アルゴリズムとして、ＡＲＣ、２Ｑ、ＭＱ、ＬＲＵ−２、ＡＬＲＦＵ、ＬＩＲＳ、ＭＲＵ、ＬＲＵ等がある。読出しと書込みの区別なしにディスクの入出力を高める方法としては、ＣＳＣＡＮ、ＳＳＴＦ、Ａｎｔｉｃｉｐａｒｉｔｙ等のようなディスクスケジューリングがある。
【００１５】
そして、従来のＲＡＩＤシステムと関連した特許として、特許文献１ではＲＡＩＤの書込み性能を高めるためにデステージ時に書込みサイズとディスクのトラックサイズとを比べてデステージを実行している。
【００１６】
また、非特許文献１は、ＲＡＩＤの構造を提案しただけで、ＲＡＩＤの入出力性能向上のための方法が提示されていない。また、非特許文献２は、単にＲＡＩＤの書込み性能を向上させるためのデステージアルゴリズムの中の一つであり、非特許文献３は、ディスクの読出し及び書込み性能を向上させる多様なディスクスケジューリング技法を紹介している。
【００１７】
そして、ＲＡＩＤシステムで一般的な場合の書込みは、順次的な書込みにより発生する。しかし、ファイルシステムが断片化（一つのファイルが、ディスクに連続的にすなわち一塊として保存されずに、多くの断片に分けられて不連続的に保存されること）されることが多くなると、その書込みはディスクの立場から断片化された順次的書込みとして現われる。すなわち、書込みのパターンがストライドパターンすなわち、間を空けて飛び越えた形態になる。このような場合には、非常に性能が悪くなる。また、ＲＡＩＤはディスク故障にも対処できる機能を提供しなければならないので、ＲＡＩＤ制御器がディスクをその最大性能まで利用することができない。そして、ＲＡＩＤはディスクが故障した時に（低下モードで）データ損失なしにデータを読めるようにしている。しかし、その実現の複雑性のために読出し動作時に多くのオーバーヘッドを有しているので、結果的に一般モードと低下モードの両方で読出し性能が低下する。
【特許文献１】米国特許ＵＳ６，７０４，８３７号
【非特許文献１】「Ａ  Ｃａｓｅ  ｆｏｒ  Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙｓ  ｏｆ  Ｉｎｅｘｐｅｎｓｉｖｅ  Ｄｉｓｋｓ（ＲＡＩＤ）」（ＡＣＭ  ＳＩＧＭＯＤ．  １９８８年，  Ｄ．  Ａ．  Ｐａｔｔｅｒｓｏｎ等）
【非特許文献２】「ＷＯＷ  ：  Ｗｉｓｅ  Ｏｒｄｅｒｉｎｇ  ｆｏｒ  Ｗｒｉｔｅｓ  −  Ｃｏｍｂｉｎｉｎｇ  Ｓｐａｔｉａｌ  ａｎｄ  Ｔｅｍｐｏｒａｌ  Ｌｏｃａｌｉｔｙ  ｉｎ  Ｎｏｎ−ｖｏｌａｔｉｌｅ  Ｃａｃｈｅｓ」（ＵＳＥＮＩＸ  ＦＡＳＴ  ２００５年，  Ｂｉｎｎｙ  Ｓ．  Ｇｉｌｌ等）
【非特許文献３】「Ｓｃｈｅｄｕｌｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｍｏｄｅｒｎ  ｄｉｓｋ  ｄｒｉｖｅｓ」（ＳＩＧＭＥＴＲＩＣＳ、Ｄ．  Ｌ．  Ｗｏｒｔｈｉｎｇｔｏｎ）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
したがって、本発明はこのような点を勘案したもので、本発明は既存のデステージアルゴリズム、キャッシュ置換アルゴリズム、さらにディスクスケジューリングの範疇に属さない、ＲＡＩＤの性能を向上させる行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向させることが目的である。
【００１９】
本発明の他の目的は、断片化された順次書込み性能を向上させてＲＡＩＤを効率的に実現できるようにすることで、ＲＡＩＤの書込み性能を向上させると共にＲＡＩＤの低下モードで小さな読出しの性能を犠牲して、一般モードで早い読出しを提供して読出し性能を向上させるようにした、行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能を向上させる方法を提供することにある。
【課題を解決するための手段】
【００２０】
前記の目的を達成するために本発明による行列ストライプキャッシュを利用したＲＡＩＤシステムの入出力性能向上の方法は、ＲＡＩＤシステムの入出力性能向上の方法であって、ディスクに書込みを行う単位ＭＳＣ(Matrix Stripe Cache)から行結合前の読出し書込み行列であるｒｘｗ行列を生成する第１ステップと、前記第１ステップで生成された行結合前ｒｘｗ行列から行結合によって最終読出し書込み行列である行結合されたｒｘｗ行列を生成する第２ステップと、前記第２ステップで生成された行結合されたｒｘｗ行列をパターンとして読出しを実行した後、前記行結合されたｒｘｗ行列の各行毎にＸＯＲ演算を実行して、行結合されたｒｘｗ行列の各列毎に書込みを実行する第３ステップとを含むことを特徴とする。
【００２１】
前記第２ステップにおける行結合は、前記行結合前ｒｘｗ行列の中で読出しだけ含まれた読出し行列において、列毎に読出し要素と読出し要素間への要素に必ず読出し動作があるように読出しを挿入して、前記行結合前ｒｘｗ行列の中で書込みだけ含まれた書込み行列において列毎に書込み要素と書込み要素間の要素に必ず書込み動作があるように書込みを挿入することを特徴とする。
【００２２】
また、前記行結合前ｒｘｗ行列で各列に読出し動作がある要素と異なる読出し動作がある要素の間に読出し動作がない要素の数が、あらかじめ決められた最大読出し距離値より大きい場合には、読出し動作を挿入しないで、また書込みの場合にも読出しの場合と同じく決められた最大書込み距離値より大きい場合には書込み動作を挿入しないことを特徴とする。
【００２３】
そして、前記決められた最大読出し距離は、ＲＡＩＤを生成する時にＩＯ間隔による実行時間を測定して連続読出し性能よりさらに速い性能を初めて示すＩＯ間隔値であり、かつ、前記決められた最大書込み距離は、ＲＡＩＤを生成する時にＩＯ間隔による実行時間を測定して連続書込み性能よりさらに速い性能を初めて示すＩＯ間隔値であることを特徴とする。
【００２４】
また、前記目的を達成するために本発明は、ＲＡＩＤシステムの入出力性能を向上させる方法であって、単位ＭＳＣの書込みが始まると、前記単位ＭＳＣに少なくとも一つ以上のダーティーブロック（特定ブロックで書込みが発生した場合、その書込みデータが前記単位ＭＳＣの該当の要素にコピーされると、その要素はダーティーブロックになる）があるかどうかを検査する第１ステップと、前記ダーティーブロックがあると判断されると前記単位ＭＳＣの各行において前記ダーティーブロックを使用するための動作を行結合前ｒｘｗ行列に記入する第２ステップと、前記行結合前ｒｘｗ行列の各列毎に、連結されていない読出しと読出しとの間に読出しを挿入して、読出しと読出しとの間に読出しがない要素の数が、決められた最大読出し距離より大きければその間のすべての読出し結合を実行しないで、小さければ読出し結合を実行する第３ステップと、前記行結合前ｒｘｗ行列の各列毎に連結されていない書込みと書込みとの間に書込みを挿入して、書込みと書込みとの間の書込みがない要素の数が、決められた最大書込み距離より大きければ、書込みを挿入することを実行しない第４ステップと、前記第３及び第４ステップによって行結合されたｒｘｗ行列で読出しが一つ以上かどうかを検査して、一つ以上なら前記行結合されたｒｘｗ行列の各列毎に読出しを実行する第５ステップと、前記行結合されたｒｘｗ行列の各行毎にＸＯＲ演算を実行した後、前記行結合されたｒｘｗ行列の各列毎に書込みを実行する第６ステップと、を含むことを特徴とする。
【００２５】
前記目的を達成するために本発明は、ＲＡＩＤシステムの入出力性能を向上させる方法であって、読出し要求が発生して読出しが開始すると、読出し要求が少なくとも二つ以上の単位ＭＳＣにまたがるとその読出し要求を単位ＭＳＣ毎にいくつかの読出し要求に分離する第１ステップと、エラーがあるディスクがないかどうか検査する第２ステップと、前記第２ステップの検査の結果、エラーがあるディスクがなければ該当の単位ＭＳＣに空のブロックがあるかどうかを検査する第３ステップと、前記第３ステップの検査の結果、空のブロックがある場合、該当の単位ＭＳＣが全体の読出しを実行中であるかどうかを検査する第４ステップと、前記第４ステップで全体読出し実行中と判断されると該当の単位ＭＳＣのブロッキングリストに該当の読出し要求を追加する第５ステップと、前記第４ステップで全体読出し実行中ではないと判断されると前記該当の単位ＭＳＣのすべての空きブロックに対する読出し書込み行列であるｒｘｗ行列を作って、前記行列を基にディスク全体に読出しを実行する第６ステップと、前記第６ステップの全体読出し実行完了後、該当の単位ＭＳＣのブロッキングリストにある読出し要求を全て読出し終了させる第７ステップと、を含むことを特徴とする。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の好ましい実施形態を添付された図面を参照してより詳細に説明する。但し、下記の実施形態は本発明を例示するだけのものであって本発明の内容が下記の実施形態に限定されるものではない。
【００２７】
まず、本発明は既存のデステージアルゴリズム、キャッシュ置換アルゴリズム、ディスクスケジューリング方法等と互換性があり、このようなアルゴリズム等と本発明は互いに両立することができ、ＲＡＩＤレベル０、ＲＡＩＤレベル１、ＲＡＩＤレベル５、ＲＡＩＤレベル６等の様々なＲＡＩＤに適用することができる。
【００２８】
本発明の主要部分は、図２と図３に示したディスクの特性を効果的に利用している。図２は、様々なＩＯ間隔が飛んでいる読出し形態で、同じ目的のブロック位置までハードディスクの読出し時間を測定したものである。飛ばす読出し形態と言うのは、ＩＯ間隔が１なら連続的な読出し、すなわちデータが断片化されていないためブロックを順に連続的に読みだすことを意味して、ＩＯ間隔が２なら一ブロックは飛ばして次の一ブロックを読出すことで、ＩＯ間隔が３なら二つのブロックを飛ばして次の一ブロックを読出すことを意味する。
【００２９】
図３は、飛ばす書込み形態でハードディスクの実行時間を測定したものである。図２と図３での結果は、ＩＯ間隔が２で突然に性能低下が発生し、ＩＯ間隔が相当開いてはじめて順次的ＩＯの性能がよりよくなる。本発明はこのようなディスクの特徴を利用して、ＲＡＩＤの性能を向上させる。
【００３０】
本発明では、入出力性能を高めるためにキャッシュを使用する。本発明で提示する方法での単位キャッシュのサイズは、一ストライプのサイズである。例えば、ＲＡＩＤレベル５でストリップ(strip)のサイズが１２８ｋＢでディスク数が５ならパリティ部分を除いた一ストライプのサイズは、５１２ｋＢになる。前記単位キャッシュの単位でキャッシュ置換アルゴリズムやデステージアルゴリズムが実行される。すなわちデステージでは一ストライプ全体が書込みに対象になる。このストライプサイズのキャッシュを本発明では単位行列ストライプキャッシュ（ＭＳＣ： Matrix Stripe Cache）と言う。単位ＭＳＣを構成する行列の各要素は、入出力の論理的最小サイズのブロックになり、各列はＲＡＩＤを構成する各ディスクを指している。
【００３１】
そして、本発明はＭＳＣによって読出し、ＸＯＲ、書込みを、従来同様行単位で決定した後、列単位で各要素を読出しと書込み毎に結合を試みる。そして、入出力の数を減らすことにより断片化された書込みの性能を高める。ＭＳＣ単位で管理されるキャッシュは、大きいサイズの書込みや順次的書込みに効率的なＲＡＩＤ実装を可能にし、ＭＳＣそれ自体として地域的局所性(Spatial Locality)をもたらすことができる。また、低下モードの小さな読出し性能を犠牲にしてより重要な一般モードの読出しを向上させる。このような本発明は、図１のＲＡＩＤ制御器で実行する。
【００３２】
本発明は、様々なＲＡＩＤ方式に適用されるが、ＲＡＩＤの中でＲＡＩＤレベル５を例にあげて説明する。
【００３３】
図４は、本発明の書込み動作の一実施形態を示したもので、５個のディスクでＲＡＩＤレベル５に構成されている。図において、ｒはディスクからブロックのキャッシュメモリにブロックを読み出す、ｔは、ディスクから臨時メモリ（ＭＳＣをデステージする間にだけ割当て、デステージが終わればメモリ割当てを解除するキャッシュメモリ）にブロックを読み出す、ｗは、ブロックのキャッシュメモリからディスクに書き込む、ｘは、ブロックのキャッシュメモリのデータをＸＯＲする、ｘｘは、ブロックのキャッシュメモリのデータと臨時メモリのデータをＸＯＲする、＿は、ＸＯＲ演算の結果を割り当てるブロックである目的地をそれぞれ意味している。ＲＡＩＤ−５の全ての動作はこの六つの動作に分類することができる。
【００３４】
ＲＡＩＤで伝達された書込み命令は、一旦図１のＲＡＩＤ制御器２０内のメモリ２１にキャッシュされる。キャッシュは、単位ＭＳＣ１００で管理される。ここでの管理の意味は、キャッシュ置換やデステージアルゴリズムが単位ＭＳＣ１００ごとに適用されることを意味する。
【００３５】
ＭＳＣの空のブロックには、実装されているキャッシュメモリが割り当てられていないこともある。または一つのＭＳＣのすべてのブロックにすべてのキャッシュメモリがあらかじめ割り当てられていても良い。本発明は、この二つの方法の特定のものに限定されるわけではない。
【００３６】
図４での単位ＭＳＣ１００は、各要素がダーティーブロック、クリーンブロックまたは空のブロックである。図４でＤは、ダーティーブロックを、Ｃはクリーンブロックを、文字のない箱は、空きブロックを意味する。単位ＭＳＣ１００の各要素は、ＲＡＩＤのストライプのそれぞれのブロックに対応する。すなわち、列はディスクを、行は増加する順序でのデータのブロックを意味する。特定のブロックに書込みが発生すると、その書込みデータをＭＳＣ１００の該当の要素にコピーする。その結果、その要素はダーティーブロックになる。あるブロックを読出したりＭＳＣ１００のダーティーブロックをディスクに書込めば、そのブロックはクリーンブロックになる。ＭＳＣ１００で空のブロックは、その要素に意味あるデータがないことを意味する。
【００３７】
そして、デステージアルゴリズムによって書込みを実行する単位ＭＳＣ１００を選択すると、その単位ＭＳＣ１００は読出し書込み行列であるｒｘｗ行列１１０の生成と行結合１４０を実行した後、ハードディスクに入出力が伝達される。
【００３８】
書込みを実行する単位ＭＳＣ１００でｒｘｗ行列１１０の生成は、各行毎に成り立つ。何故ならば各行毎にパリティブロックの依存性を有する。各行毎にパリティブロックを生成するための方法は、既存の方式に従う。すなわち、パリティブロックは次のような二つの方法で生成される。
【００３９】
第一、ダーティーブロックに該当するディスクの古いデータと、そのダーティーブロックの新しいデータと、そのダーティーブロックが属したパリティブロックグループの古いデータを排他的論理演算（ＸＯＲ）をしたものがそのパリティブロックの新しいパリティデータである。
【００４０】
第二、一つのパリティブロックグループでパリティブロックを除くすべてのブロックをＸＯＲしたものがそのパリティブロックである。但し、そのパリティブロックグループで空のブロックは読出しが必要である。
【００４１】
この二つの方法の中で最も入出力の数が少ないものを選択する。但し、二つの方式が等しい入出力の数を有する時は、後者の方法を選択する。但し、パリティブロックグループと言うのは、パリティブロックを生成するために必要なブロックのグループである。
【００４２】
前述したように、図４で‘ｒ’はそのブロックの読出し動作を、‘ｔ’は読出し動作であるが目的のメモリが臨時メモリである。‘ｘ’はそのブロックがＸＯＲ演算の被演算子であることを、ｘｘはそのブロックの‘ｔ’動作による臨時メモリとそのブロックのキャッシュメモリが被演算子であることを、‘＿’はＸＯＲ演算の目的地を、‘ｗ’はそのブロックの書込み動作を示す。
【００４３】
各パリティブロックグループ毎にパリティブロックを生成して、ダーティーブロックを書込むための方式を図４を通じて例を挙げる。行結合前のｒｘｗ行列１１０の初めの行は、初めの列、すなわちＤ０ディスクにだけダーティーブロックがあって残りは空のブロックである。その場合、一番目のパリティブロック方式を使用する。そのｒｘｗ行列１１０の（１、１）要素はｔｘｘｗになり、そのパリティブロックグループのパリティブロックである（１、５）要素はｒｘ＿ｗになる。すなわち、（１、１）要素は‘ｔ’動作をし、（１、５）要素は‘ｒ’動作をして、（１、１）要素の臨時メモリのデータと（１、５）要素のキャッシュメモリのデータをＸＯＲ演算をして、（１、１）要素と（１、５）要素が‘ｗ’動作を実行する。
【００４４】
そのｒｘｗ行列１１０の３行は例えば、単位ＭＳＣ１００の（３、３）要素がダーティーブロックで、（３、１）要素がクリーンブロックである。それで（３、１）要素は‘ｘ’、（３、２）要素は’ｒｘ’、（３、３）要素は’ｘｗ’、（３、４）要素は’ｒｘ’、（３、５）項は’＿ｗ’になる。
【００４５】
行結合前のｒｘｗ行列１１０を読出し動作だけを選んで示した読出し行列１２０が、図４に表示されている。この読出し行列１２０は、行列１１０とは別に存在する行列ではない。ｒｘｗ行列１１０における読出し動作のみを確認するために、読出し行列１２０を図４に表示しただけである。書込み行列１３０も同様に書込み動作のみを分かりやすく表示するためのものであって、別に存在する行列ではない。
【００４６】
既存のＲＡＩＤレベル５動作で決定されたｒｘｗ行列１１０の生成が完了すると、行結合を実行しなければならない。行結合の基本原理を下記に示す。
【００４７】
読出し行列１２０で、列毎に読出し要素と読出し要素間の要素に必ず読出し動作があるように読出しを挿入して、書込み要素と書込み要素間の要素にも必ず書込み動作があるように書込み動作を挿入する。但し、読出し動作を挿入する時にその要素がダーティーブロックなら‘ｔ’動作をし、そうでなければ‘ｒ’動作をする。
【００４８】
また、書込み動作を挿入する時にその要素がクリーンブロックだったり、その要素に‘ｒ’動作がない時には書込み動作ができない。書込み要素と書込み要素との間に書込み動作を挿入することができない要素が一つでもあれば、その間のすべての書込み動作を挿入することは行われない。
【００４９】
読出し／書込み動作を挿入するには他の制限条件がある。行結合前ｒｘｗ行列１１０で各列毎に読出し動作がある要素とその要素とは異なる読出し動作がある要素との間に読出し動作がない要素の数が、あらかじめ決められた“最大読出し距離”値より大きい場合には、読出し動作を挿入しない。書込みの場合にも同じく、決められた“最大書込み距離”値より大きい場合には、書込み動作を挿入しない。
【００５０】
前記決められた“最大読出し距離”は、ＲＡＩＤを生成する時に図２に示したＩＯ間隔による実行時間を測定して、連続読出し性能よりさらに速い性能を初めて示すＩＯ間隔値が“最大読出し距離”になる。また、前記決められた“最大書込み距離”も同様に連続書込み性能よりさらに速い性能を初めて示すＩＯ間隔値が“最大書込み距離”になる。“最大読出し距離”と“最大書込み距離”値は、永久に保存することができる所に保存しておく。
【００５１】
行結合前のｒｘｗ行列１１０が行結合後、最終のｒｘｗ行列１４０が作られる。行結合された最終のｒｘｗ行列１４０で、読出しまたは書込みだけを選び出して示す実際には存在しない読出しｒｘｗ行列１５０と書込みｒｘｗ行列１６０を、それぞれ、行結合前の読出しｒｘｗ行列１２０と書込みｒｘｗ行列１３０と比べると、どのようにして行結合が成り立つのか容易に分かるであろう。
【００５２】
結合された最終ｒｘｗ行列１４０をパターンとして読出しを実行してそれが完了すると、ＸＯＲを実行した後に、書込みを実行する。書込みが完了すると、その単位ＭＳＣの書込み動作が完了する。
【００５３】
このように読出しを挿入し、書込みを挿入すると、いくつかの読出しまたは書込みディスク命令がデータ長はさらに長いが一つのディスク命令を形成する。後者のディスク命令が前者のディスク命令よりさらに速い性能を見せるようになる。
【００５４】
以上の単位ＭＳＣ１００で行結合ｒｘｗ行列生成までのステップを図５の流れ図に示した。
【００５５】
単位ＭＳＣ１００の書込みが開始２００されると、単位ＭＳＣ１００に一つ以上のダーティーブロックがあるかどうか検査する第１ステップ２０１を実行する。第１ステップ２０１で論理が正しければ第２ステップ２０２を実行し、そうでなければ単位ＭＳＣ１００の書込みが完了する２１１。
【００５６】
第２ステップ２０２では、単位ＭＳＣ１００の各行毎にダーティーブロックを使用するための動作（ｔ、ｒ、ｘ、＿、ｗ）等をｒｘｗ行列１１０に記入する。
【００５７】
次に第３ステップ２０３である読出し結合を実行する。読出し結合では、ｒｘｗ行列１１０の各列毎に、連結されていない読出し（‘ｒ’または‘ｔ’）と読出しの間に読出しを挿入する。但し、その間の読出しがない要素の数が“最大読出し距離”より大きければ、その間のすべての読出し結合を実行しない。読出しを挿入する要素に該当するブロックがダーティーブロックなら‘ｔ’を挿入して、そうではなければ‘ｒ’を挿入する。
【００５８】
次に第４ステップ２０４である書込み結合を実行する。書込み結合では、ｒｘｗ行列１１０の各列毎に連結されていない書込み（‘ｗ’）と書込みとの間に書込みを挿入する。但し、その間の書込みがない要素の数が“最大書込み距離”より大きければ、書込みを挿入することを実行しない。また、その間の書込みがない要素の中で、読出し（‘ｒ’または‘ｔ’）がなく、該当のブロックが空のブロックである要素があれば、その間のすべての書込み結合を実行しない。
【００５９】
次に、ｒｘｗ行列で読出し（‘ｒ’または‘ｔ’）が一つ以上かどうかを検査する第５ステップ２０５を実行する。一つ以上でなければ第８ステップ２０８を実行する。第５ステップ２０５で論理が正しければ、行結合された最終のｒｘｗ行列１４０の各列毎に読出しを実行する第６ステップ２０６を実行する。第７ステップの読出し実行完了２０７の後に、行結合された最終のｒｘｗ行列１４０の各行毎にＸＯＲ演算を実行する第８ステップ２０８を実行する。そして、続けて行結合された最終のｒｘｗ行列１４０の各列毎に書込みを実行する第９ステップ２０９と書込み実行完了第１０ステップ２１０を終えると、書込みが終了２１１になる。
【００６０】
書込み結合は、読出し結合よりさらに多くの制約を有する。すなわち、書込み結合で書込みを挿入する対象の要素がクリーンブロックでかつ読出し動作がなければ、書込み結合が成り立たない。それで、このような制約を減らすために、さらに積極的にクリーンブロックを読出し、結合条件と関係なしに読出しを追加できるようにｒｗｘ行列の行結合を拡張することができる。
【００６１】
次に、本発明の読出し性能向上の方法に対して詳しく見る。
読出し性能向上の技法と書込み性能向上の技法は互いに独立である。
【００６２】
本発明の読出し性能の向上技法は、一般モードの読出し性能を向上させる。その代わり、低下モードでの小さな読出し性能を犠牲にすることになる。低下モードではパリティのキャッシュを利用して読出し性能を改善させなければならない。そのために読出し要求の間に複雑な依存性が生じ、それによってＲＡＩＤの読出しの実現が複雑になり、読出しにおいても相当なオーバーヘッドを有する。
【００６３】
このようなオーバーヘッドを無くすため、低下モードでの読出しはいつもストライプ全体を読出す。そして、読出し要求間の複雑な依存性を減らす。しかし、小さな読出しに対する性能は悪くなる。
【００６４】
このような読出し性能向上の技法を図６の流れ図に示した。
【００６５】
読出し要求が発生して読出しが開始３００されると、まず読出し要求が二つ以上の単位ＭＳＣ１００にまたがっていれば、その読出し要求を単位ＭＳＣ１００毎にいくつかの読出し要求に分離する第１ステップ３０１を実行する。
【００６６】
そして、エラーのあるディスクがないかどうか検査する第２ステップ３０２を実行する。エラーのあるディスクがなければ、読出し要求ごとに、読出しブロックの中で単位ＭＳＣ１００の空のブロックを読出し実行する第３ステップ３０３を実行して読出しが終了３０９する。
【００６７】
前記の第３ステップ３０３で単位ＭＳＣ１００によってはキャッシュヒットになるブロックもある。または、読出しを要求するブロックが全てキャッシュヒットになることもある。この場合、読出し動作なしに読出し要求が終了する。
【００６８】
そして、前記第２ステップ３０２でエラーのあるディスクがあれば、該当の単位ＭＳＣ１００に空のブロックがあるかどうか検査する第４ステップ３０４を実行する。第４ステップ３０４の論理が正しければ第５ステップ３０５を実行し、そうでなければ読出し終了３０９になる。該当の単位ＭＳＣ１００が全体読出し実行中なのかどうかを検査する第５ステップ３０５で論理が正しければ、該当の単位ＭＳＣ１００のブロッキングリストに該当の読出し要求を追加する第８ステップ３０８を実行する。そうすると、その読出し要求は第７ステップ３０７で終わる。
【００６９】
前記第５ステップ３０５の論理が偽なら、該当の単位ＭＳＣ１００のすべての空のブロックに対するｒｘｗ行列を作って、その行列に対して読出し結合を実行した後に、その行列をベースにディスク全体への読出しを実行する第６ステップ３０６を実行する。但し、読出し結合は省略できる。その次に、全体読出し実行が完了した後、該当の単位ＭＳＣ１００のブロッキングリストにある読出し要求をすべて読出し終了させる第７ステップ３０７を実行して読出し終了３０９になる。
【００７０】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当の技術分野の熟練した当業者は、特許請求の範囲に記載された本発明の思想及び領域から逸脱しない範囲内で本発明を多様に修正または変形して実施することができる。
【００７１】
以上で詳しく見たように、本発明はＲＡＩＤレベル５の断片化された順次書込み、地域的局所性が高い書込みの性能を向上させることができる。
【００７２】
すなわち、本発明は、断片化された順次書込み性能を高めるためにＲＡＩＤの単位ＭＳＣの束で書込みを実行して、ＲＡＩＤレベル５の場合には各行において各要素の読出し／ＸＯＲ／書込みを決定するｒｘｗ行列を生成して、再びこのｒｘｗ行列で各列毎に読出しと読出しとの間に追加的な読出しを挿入して二つの読出しを一つの読出しにし、可能なら、書込みと書込みの間に追加的な書込みを挿入して二つの書込みを一つの書込みにする。このように追加的な読出しと書込みが加えられたｒｘｗ行列をベースに各ディスクに読出し命令と書込み命令を発行することで、読出しと書込みの入出力の数が減り、書込みの性能を向上させることができる。また、二つの要素を連結する時に事前に与えられた距離以上に離れたもの同士は連結しないで、単位ＭＳＣでキャッシュを管理することで単位キャッシュの数が減って単位キャッシュの閉鎖及び割当／解除の数が減って実現の簡便化をもたらす。すなわち、大きい書込みに非常に効率的なＲＡＩＤ実現が可能になり、それによって順次書込み性能が向上する。
【００７３】
次に、本発明は、低下モードでの小さな読出し性能を犠牲にして一般モードの読出し性能を向上させる。低下モードではパリティのキャッシュを利用して読出し性能を改善させなければならない。そのために読出し要求の間に複雑な依存性が生じ、それによってＲＡＩＤの読出しの実施が複雑になり、それによって読出しでも相当なオーバーヘッドを有する。このようなオーバーヘッドを無くすため、低下モードでの読出しはいつもストライプ全体を読出す。そして、読出し要求の間の複雑な依存性を減らすことが可能になる。
【図面の簡単な説明】
【００７４】
【図１】一般的なＲＡＩＤシステムの概略的なブロック構成図。
【図２】読出し間隔の変化によるハードディスクの読出し実行時間に対するグラフ。
【図３】書込み間隔の変化によるハードディスクの書込み実行時間に対するグラフ。
【図４】本発明による行列ストライプキャッシュ（ＭＳＣ）を利用した書込みの一実施形態の説明図。
【図５】本発明によるＭＳＣを利用した書込みに対する流れ図。
【図６】本発明によるＭＳＣを利用した読出しに対する流れ図。
【符号の説明】
【００７５】
１００：単位ＭＳＣ、１１０：行結合前のｒｘｗ行列、１２０：読出し行列、１３０：書込み行列、１４０：行結合されたｒｘｗ行列、１５０：読出しｒｘｗ行列、１６０：書込みｒｘｗ行列
【図１】
2008004069.tif 000003
【図２】
2008004069.tif 000004
【図３】
2008004069.tif 000005
【図４】
2008004069.tif 000006
【図５】
2008004069.tif 000007
【図６】
2008004069.tif 000008