(57)【要約】【課題】有向グラフを使用するシャーディング方法及び装置を提供する。【解決手段】本発明にかかる方法は、ストレージボリューム内の各ブロックに頂点を有しながら、頂点対間に、ブロックのシャードを表す有向エッジを有する有向グラフを作成すること、各有向エッジに、対応する頂点対間の前記ブロックのシャードの相違性を表す重みを関連付けること、ストレージボリュームを分割するシャードの最大数（Ｋ）を選択すること、Ｋ以下のシャードの組み合わせで、現在の頂点に関連する最小重み合計を識別すること、有向グラフ内のすべての頂点に対して、最小重み合計の識別を行うこと、及び最後の頂点に関連する最小重み合計を選ぶことであって、それによってストレージボリュームにわたり、Ｋ以下のシャードのブロック間で最小の相違性を提供するシャーディングを判断すること、を含む。【選択図】図２
2007524922.tif 000002
【特許請求の範囲】
【請求項１】
ストレージボリューム内の各ブロックに頂点を有するとともに、頂点対間に、ブロックのシャード（shard）を表す有向エッジを有する有向グラフを作成すること（３０４）、
各有向エッジに、対応する前記頂点対間の前記ブロックのシャードの相違性を表す重みを関連付けること（３０６）、
前記ストレージボリュームを分割するシャードの最大数（Ｋ）を選択すること（４０２）、
Ｋ以下のシャードの組み合わせで、現在の頂点に関連する最小重み合計を識別すること（４０６）、
前記有向グラフ内のすべての頂点に対して、前記最小重み合計の識別を行うこと（４０６）、及び
最後の頂点に関連する前記最小重み合計を選ぶことであって、それによって前記ストレージボリュームにわたり、Ｋ以下のシャードのブロック間で最小の相違性を提供するシャーディング（sharding）を判断する（４０８）、選ぶこと、
を含む、ストレージボリュームをシャードに分割する方法。
【請求項２】
前記頂点対は、順次組み合わせられたブロック及び対応する異なるブロックのシャードのあらゆる順列を表す、請求項１に記載のストレージボリュームをシャードに分割する方法。
【請求項３】
２つ以上のブロックを有するシャードの前記相違性は、前記シャード内のブロック対間でのペアワイズ相違性測定を結合することによって求められる、請求項１に記載のストレージボリュームをシャードに分割する方法。
【請求項４】
前記ペアワイズ相違性は、
ストレージ空間の領域でのストレージアクセスアクティビティを監視すること、
所定のパラメータに従って、前記ストレージ空間の領域の複数の個々の部分の前記ストレージアクセスアクティビティの少なくとも１つの特性を測定すること、及び
個々の或る部分のストレージアクセスアクティビティの前記特性が、所定の基準に従って別の部分のストレージアクセスアクティビティの前記特性に類似するか否かを判断すること、
をさらに含む、請求項３に記載のストレージボリュームをシャードに分割する方法。
【請求項５】
ストレージアクセスアクティビティの前記特性を、別の部分のストレージアクセスアクティビティの前記特性に対して判断するための前記所定の基準は、前記各部分のＩ／Ｏサイズ測定を比較することを含む、請求項４に記載のストレージボリュームをシャードに分割する方法。
【請求項６】
ストレージアクセスアクティビティの前記特性を、別の部分のストレージアクセスアクティビティの前記特性に対して判断するための前記所定の基準は、前記各部分の読み出し／書き込み比を比較することを含む、請求項４に記載のストレージボリュームをシャードに分割する方法。
【請求項７】
ストレージアクセスアクティビティの前記特性を、別の部分のストレージアクセスアクティビティの前記特性に対して判断するための前記所定の基準は、前記各部分のＩ／Ｏ密度を比較することを含む、請求項４に記載のストレージボリュームをシャードに分割する方法。
【請求項８】
前記シャードの最大数（Ｋ）を選択することにより、前記ストレージボリューム上のデータへのアクセス効率が全体的に向上する、請求項１に記載のストレージボリュームをシャードに分割する方法。
【請求項９】
前記最小重み合計は、直前の有向エッジからの重みを、近傍頂点に関連する最小重みと結合することにより求められる、請求項１に記載のストレージボリュームをシャードに分割する方法。
【請求項１０】
解析のためにストレージボリューム内のシャードを有向グラフにマッピングする方法であって、
前記ストレージボリューム内の潜在的なシャードを識別すること（３０２）、
前記ストレージボリューム内の潜在的な各シャードに頂点、及び前記頂点対間に有向エッジを前記有向グラフに作成すること（３０４）、及び
各有向エッジに、前記有向エッジに対応するブロックシーケンスの相違性を表す重みを関連付けること（３０６）、
を含む、ストレージボリューム内のシャードを有向グラフにマッピングする方法。
【請求項１１】
前記ストレージボリューム内の潜在的なシャードは、前記ストレージボリュームにわたるペアワイズのブロックシーケンスに対応する、請求項１０に記載のストレージボリューム内のシャードを有向グラフにマッピングする方法。
【請求項１２】
エッジは、対応する前記頂点対間の前記ブロックシーケンスを表す、請求項１０に記載のストレージボリューム内のシャードを有向グラフにマッピングする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
本開示はストレージシステムの編成及びストレージパフォーマンス特性（characterristics）の改良に関する。
【背景技術】
【０００２】
近代のストレージシステムは多くの場合、ストレージボリュームを使用して情報を編成するとともに管理する。ストレージボリュームは、データの仮想容器又はデータに確保された空間量を表す論理的なエンティティである。ストレージボリュームは、装置に記憶することができるが、必ずしも単一の装置を表すわけではない。通常、ストレージボリュームの１つ又は複数の部分が１つ又は複数の物理的な装置にマッピングされる。多くの場合、こういったマッピングはかなり任意に行うことができ、装置は、いくつかのストレージボリュームのすべてとは言えないまでも一部を含むことができる。同様に、ストレージボリュームはいくつかの装置にマッピングすることができる。論理ボリュームマネージャ（ＬＶＭ）が、システムにおいてストレージボリュームの管理に使用されるツールである。
【０００３】
ストレージボリュームに記憶される情報の均質性を高めることには、多くの恩恵があり得る。データに頻繁にアクセスするコンピュータシステムは、より高速のアクセス特性を有するストレージボリュームに「ホットデータ」が記憶されている場合により良好なパフォーマンスを有することができる。同様に、あまり頻繁にアクセスされないデータすなわち「コールドデータ」を、より高価な高速アクセス特性を必要としないより低速のストレージボリュームにまとめても、パフォーマンスに対する影響はほとんどない。データの均質性を高めることにより、パフォーマンスを予測する能力、及び要求されるパフォーマンスニーズによりよくマッチしたストレージデバイス（device）及びハードウェアを配備する能力も向上する。
【０００４】
【非特許文献１】D. R. LIU, S. SHEKHAR: "Partitoninig Similarity Graphs: A Framework for Declustering Problems" INFORMATION SYSTEMS, PERGAMON PRESS, vol. 21, no. 6, September 1996 (1996-09), pages 475-496, XP002324185 OXFORD, UK ISSN: 0306-4379 page 475, paragraph 2 after "1. Introduction"
【非特許文献２】CHEHADEH Y C ET AL: "Application for parallel disks for efficient handling of object-oriented databases" PARALLEL AND DISTRIBUTED PROCESSING, 1993. PROCEEDINGS OF THE FIFTH IEEE SYMPOSIUM ON DALLAS, TX, USA 1-4 DEC. 1993, LOS ALAMITOS, CA,- USA,IEEE COMPUT. SOC, l December 1993 (1993-12-01), pages 184-191, XP010135523 ISBN: 0-8186-4222-X
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来のシステムは、管理者に頼って均質情報を識別し、次いで識別された均質情報を１つ又は複数のストレージボリュームに分配する。システムセットアップ時に、人間がまず１つのドライブを、頻繁にアクセスされる情報を保持するために割り振り、第２のドライブ又はストレージボリュームを、あまり頻繁にアクセスされない情報を保持するために割り振る。不都合なことに、この種の構成を手動で維持し、均質データをまとめておくことは困難且つ面倒である。管理者が「類似」するデータを識別することが困難なだけでなく、時間の経過に伴い、最初に割り振ったデータが成長して特定のストレージボリュームには大きくなりすぎる可能性があり、且つ／又は使用の振る舞いが変化する、又は変更されるにつれて異なるアクセスパターンが出現する可能性もあり、これによりマッピングを統計的に推定することが不可能になる。均質情報群を手動で物理的な別個のストレージボリュームに分割することは柔軟性に欠け、有用な時間期間のいずれにわたっても実効的である可能性は低い。
【０００６】
別の手法は、ストレージボリュームを均質データのシャードに自動的に分割するというものである。シャードは、均質のアクセス特性を有する情報を論理的に一緒にグループ化するために使用されるストレージボリュームの部分である。ストレージボリューム及び元となるデータのアクセス特性に応じて、異なるシャーディングの組み合わせが使用される。時間の経過に伴い、異なるシャーディングの組み合わせを使用して変化するアクセスパターンに対応し、ストレージボリュームに記憶されているデータをより均質にすることができる。
【０００７】
シャードのアクセスパターン及び均質データの識別は、２つ以上の元となるデータセットが同一であることは希であるため困難である。大半の場合、或るデータブロックのアクセスパターンは別のデータブロックに類似し得るが、同一ではない。ペアワイズの類似性測度により、データブロックを共に均質シャードにグループ化する一方法が提供される。１つ又は複数のブロックの性質が互いに類似するか相違するかを検出する他の多くの方法がある。
【０００８】
不都合なことに、ストレージボリュームのシャードへの分割には多くの異なる分割が考えられる。分割によっては、他よりも均質なアクセスパターンを有するシャードを生成するものがある。現在、最も均質なアクセスパターンを有するシャードセットを提供する最適なシャーディングを判断する効果的且つ効率的な方法はない。ストレージボリュームの考えられるあらゆるシャーディングを考慮することは時間がかかるとともにプロセッサ集約的である。
【０００９】
各種図面中の同様の参照番号及び呼称は、同様の要素を示す。
【課題を解決するための手段】
【００１０】
［発明の概要］
本発明の一態様は、解析のためにシャードを有向グラフにマッピングする。このマッピングは、ストレージボリューム内の潜在的なシャードを識別すること、ストレージボリュームでの潜在的なシャードのそれぞれについて頂点及び頂点対の間の有向エッジを有向グラフに作成すること、及び各有向エッジに、有向エッジに対応するブロックシーケンスの相違性を表す重みを関連付けること、を含む。
【００１１】
本発明の別の態様は、有向グラフを使用して、ストレージボリュームをシャードに分割する。この分割は、ストレージボリューム内の各ブロックに頂点を有するとともに、頂点対間に、ブロックのシャードを表す有向エッジを有する有向グラフを作成すること、各有向エッジに、対応する頂点対間のブロックのシャードの相違性を表す重みを関連付けること、ストレージボリュームを分割するシャードの最大数（Ｋ）を選択すること、Ｋ以下のシャードの組み合わせで、現在の頂点に関連する最小重み合計を識別すること、有向グラフ内のすべての頂点に対して、最小重み合計の識別を行うこと、及び最後の頂点に関連する最小重み合計を選ぶことであって、それによってストレージボリュームにわたり、Ｋ以下のシャードのブロック間で最小の相違性を提供するシャーディングを判断する、選ぶこと、を含む。
【００１２】
本発明の１つ又は複数の実施形態の詳細について、添付図面及び以下の説明に示す。本発明の他の特性及び利点も、説明、図面、及び特許請求の範囲から明らかになろう。
【発明を実施するための最良の形態】
【００１３】
［詳細な説明］
本発明の態様は、以下の方法のうちの少なくとも１つ又は複数において有利である。ストレージボリュームをシャードに分割することにより、シャードが比較的均質なブロック群に対応する場合にアクセス特性及びアクセスパフォーマンスを向上させることができる。この計算の複雑さを低減するために、ストレージボリューム内のブロック及び潜在的なシャードが、最短経路問題として解析するために有向グラフにマッピングされる。
【００１４】
異なる潜在的なシャーディングが多くあるストレージボリュームは、有向ブラフにおける近傍頂点に対して行われる計算を再利用することによってより高速に解析される。シャーディングセット間の総相違量を追跡し、且つ最小にすることにより、最終的にストレージボリュームのシャードへの最適な分割がもたらされる。
【００１５】
図１は、シャードに分割されたストレージボリュームを使用するシステムのブロック図である。システム１００は、ネットワーク１０８を介してストレージマネージャアプリケーション１１２にアクセスするシステム１１０２、システム２１０４、及びシステム３１０６を含む。ストレージマネージャ１１２は、シャード１１１８及びシャード２１２０を有するストレージボリューム１１１４、並びにシャード３１２２を有するストレージボリューム２１１６を管理する。シャード１１１８はブック１２４〜１２６から成り、シャード２１２０はブロック１２８〜１３０から成り、シャード３１２２はブロック１３２〜１３４から成る。したがって、各ストレージボリュームを１つ又は複数のシャードに分割してもよく、各シャードは１つ又は複数のブロックから成る。
【００１６】
１つのインプリメンテーションでは、各システム１１０２、システム２１０４、及びシステム３１０６は、図１に示すようにストレージマネージャ１１２及びネットワーク１０８を通してストレージにアクセスする。ストレージマネージャ１１２は、各ストレージボリュームのシャードへの最適な分割を判断する本発明によるロジックを含む。ストレージマネージャ１１２なしで動作する代替のインプリメンテーションはこれに代えて、各システム１１０２、システム２１０４、及びシステム３１０６内に直接に同様のロジックを備えるか、又はストレージボリューム１１１４及びストレージボリューム２１１６に対してより直接的に関連付けられる。分散ソリューションは、１つ又は複数のシステム１０２、１０４、及び１０６、ストレージマネージャ１１２、並びにストレージボリューム１１４及び１１６上の潜在的なオンボードロジックを組み合わせたものを介して処理を分散させることにより、本発明により最適なシャーディングを生成する。
【００１７】
動作に際して、本発明のインプリメンテーションは、システム内の各種ストレージボリュームについてのストレージアクセス情報・特性１１０を収集し、これは一般に、複数のストレージボリュームを有するストレージ空間でのＩ／Ｏアクティビティを記録することを含む。たとえば、Ｉ／Ｏアクティビティは、特定のストレージ領域でのＩ／Ｏ動作数、或る時間期間にわたるＩ／Ｏ動作レート、読み出しと書き込みとの比率、Ｉ／Ｏアクティビティの局所性、アクセスのバースト性、及び他の多くの特性を含んでもよい。これら特性は、１つ又は複数のストレージボリューム内での均質性を判断する際に他のストレージ測度と併せて考慮される。均質性情報を使用して、ストレージデバイスの将来の使われ方を予測し、アクセス及びパフォーマンスの向上のためにブロックを共にシャードにクラスタ化することができる。
【００１８】
１つのインプリメンテーションでは、ストレージマネージャアプリケーション１１２は、ストレージボリューム内のブロックのペアワイズ相違性を測定する相違性関数を使用する。この相違性関数を使用して、１つ又は複数のストレージボリュームの統計的な均質性を求める。次いで、本発明のインプリメンテーションは相違性結果を用いてストレージボリューム１１４及び１１６を３つのシャード、すなわちブロック１２４〜１２６から成るシャード１１１８、ブロック１２８〜１３０から成るシャード２１２０、及びブロック１３２〜１３４から成るシャード３１２２に分割する。上述したように、ストレージボリュームの均質部分を１つ又は複数のシャードにクラスタ化することにより、デバイスへのアクセス特性をよりよくマッチさせ、それによってストレージシステムのパフォーマンス及び管理のしやすさを向上させる。たとえば、頻繁にアクセスされるストレージ空間ほど、元となるストレージデバイスが高速である「ホット」シャードに置き、頻度の少ないストレージ空間ほど、低パフォーマンス指向のストレージデバイスで動作される「クール」シャードに分類することができる。相違性関数については、本明細書において後述するとともに、本発明の譲受人に譲渡され、その全体を参照により本明細書に援用する同時係属中のR. Becker-Szendy及びArif Merchantによる米国特許出願第０９／０５８，１８５号、「A Method and Apparatus for Measuring and Optimizing Spatial Segmentation of Electronic Workloads」にさらに記載されている。
【００１９】
図２は、本発明の１つのインプリメンテーションによる、ストレージボリュームとストレージボリュームに関連するシャードへのブロックの分配との間の関係をマッピングした概略ブロック図である。ストレージボリューム２０２は、パフォーマンス向上のために最適なシャードに編成される多くのストレージ空間の１つであることができる。内部では、ストレージボリューム２０２は、Ｎ個のストレージユニットの一連のブロック２０４又は他の論理的な分割として表すことができる。本発明のインプリメンテーションは、一連のブロック２０４内のＮ個のブロックに対応してＮ＋１個の頂点を作成する。一連のブロック２０４に示すように、Ｖ０からＶＮまでの頂点の異なる対に対応して、有向エッジが作成される。２頂点ＶｉとＶｊの間のエッジを使用して、ブロックＢｉ＋１〜Ｂｊを含むシャードを表す。これら頂点及びエッジを使用して、本明細書において後に示し説明するように有向グラフ２０９を作成する。
【００２０】
これらＮ個のブロック（Ｂ１〜ＢＮ）がアクセスされると、情報が収集され、ストレージアクセス情報・特性２０８に集められる。ストレージボリュームはブロックシーケンスであるため、ブロックとストレージボリュームの間の関係は
ストレージボリューム＝（ブロック１，ブロック２，Ｌ  ブロックＮ）
として表すことができる。
【００２１】
本発明では、ストレージボリューム及びストレージボリュームに含まれるブロックもブロッククラスタとして表すことができる。ストレージボリュームに関連するブロック範囲ｉ〜ｊに重点を置いた以下の表記を用いて、所与のシャードを表すことができる。
シャードｉｊ＝（ブロックｉ＋１，Ｋ，ブロックｊ）
但し、
ブロックｉ＋１＝シャードの最初のブロック
ブロックｊ＝シャードの最後のブロック
である。
【００２２】
相違性定量構成要素（dissimilarity determination component）２０６がストレージアクセス情報・特性２０８を処理して、解析中のＮ個のブロック間のペアワイズ相違性を求める。１つのインプリメンテーションでは、相違性は０〜１又は０〜１よりも大きな数の範囲を用いて表すことができ、ここで０は相違性がないことを示し、１又は１よりも大きな数は高い相違性を示す。特定のシャードの相違性は、シャード内に含まれる２つ以上のブロック間の相違性の和として計算することができる。形式上、ブロックｉ〜ブロックｊを含む所与のシャードの相違性（dissimilarity(shardｉｊ)）を、
【００２３】
【数１】
2007524922.tif 000003
【００２４】
として表すことができる。但し、
ブロックｉ＋１＝シャードの最初のブロック
ブロックｊ＝シャードの最後のブロック
０又は小さな値〜わずかな相違性
である。
【００２５】
望ましい場合、シャードの相違性は別法として、シャード内のブロック間のペアワイズ類似性を測定したものから導出することができる。ブロック類似性関数からシャード相違性関数に変換するには、以下の関係を用いることができる。
【００２６】
【数２】
2007524922.tif 000004
【００２７】
但し、
ブロックｉ＋１＝シャードの最初のブロック
ブロックｊ＝シャードの最後のブロック
である。
【００２８】
一般に、本発明のインプリメンテーションは、多くの異なる相違性関数と併せて使用することができ、相違性定量構成要素２０６は本明細書において述べる相違性関数との併用のみに限定されない。本発明のインプリメンテーションが、相違性関数を選択して相違性が最小のブロックを共にグループ化する最適なシャーディングを作成することは重要である。一例では、相違性関数が、ストレージアクセス情報・特性２０８に集められているストレージ空間の領域でのストレージアクセスアクティビティを監視する。次いで、監視情報／結果を用いて、所定のパラメータに従ってストレージ空間の１つ又は複数の個々の部分でのストレージアクセスアクティビティの少なくとも１つの特性を測定する。次いで、個々の或る部分のストレージアクセスアクティビティの特性が、所定の基準に従って別の部分のストレージアクセスアクティビティの特性と相違するか否かに基づいて、相違性が求められる。必要に応じて、相違性は上述したように類似性関数の補数として計算される。
【００２９】
この例において類似性を求めるために使用される所定のパラメータ及び基準は、以下のうちの１つ又は複数に（単独で、又は組み合わせて）基づくことができる。たとえば、類似性は、ストレージボリュームのストレージアクセスアクティビティの特性を監視しながら、ストレージボリュームの異なる部分のＩ／Ｏサイズ測定を比較することにより、各部分のＩ／Ｏサイズ測定を比較することにより、各部分の読み出し／書き込み比を比較することにより、また各部分のＩ／Ｏ密度を比較することにより求めることができる。本発明のインプリメンテーションに適合する１つの類似性関数についてのさらなる詳細が、R. Becker-Szendy及びArif Merchantによる「A Method and Apparatus for Measuring and Optimizing Spatial Segmentation of Electronic Workloads」にさらに詳細に記載されている。
【００３０】
有向グラフ２０９は、有向グラフ２０９の生成に使用される一連のブロック２０４に対応するエッジ及び頂点の一部を示す。エッジ及び頂点の多くは、本発明にかかる詳細及び本発明により使用される重みベクトルをよりよく示すために有向グラフ２０９から省かれている。この例では、有向グラフ２０９は、頂点Ｖ０、Ｖ１、Ｖ２、Ｖ３及びＶ４、並びに頂点間の複数のエッジを含む。相違性定量２０６に基づいてエッジに重みが関連付けられ、重みを使用して、有向グラフ２０９の各頂点に関連付けられる重みベクトルを満たす（fill）。有向グラフ２０９の解析については、本明細書においてさらに後述する。
【００３１】
有向グラフ２０９の解析後、本発明のインプリメンテーションは、各ストレージボリュームのブロックに最適なシャーディング又はクラスタ化を判断する。図２を参照すると、ストレージボリューム２０２は４つのシャードに、すなわちシャード１２１０をブロック２１８〜２２０に、シャード２２１２はブロック２２２〜２２４に、シャード３２１４はブロック２２６〜２２８に、及びシャード４２１６はブロック２３０〜２３２に分割される。
【００３２】
本発明のインプリメンテーションは、有向グラフを使用してストレージボリュームの潜在的なシャーディングをすべて表し、有向グラフから、ストレージ空間に最適なシャーディングの組み合わせを選択する。シャーディング動作を行う人物は、利用可能なストレージデバイスの１つ又は複数の特性に応じて、ストレージボリュームが分割されるシャード数（Ｋ）を制限する。たとえば、シャード数は、ストレージ空間内に相対的に異なる動作特性をそれぞれ有する６個の異なるストレージデバイスがあることによりＫ＝６に制限され得る。
【００３３】
本発明のインプリメンテーションは、シャーディング問題を有向グラフの最短経路問題に変換することによって正確且つ効率的にシャーディングを選択する。追加の制約として、総ストレージボリュームはＫよりも多くの異なるシャードには分割されない。この追加の制約は、検索を有向グラフのＫ以下のエッジに沿うものに制限し、解によりストレージ空間にＫ以下のシャードのシャーディングが生成されることを保証する。
【００３４】
図３は、本発明の実施形態による、有向グラフとしてのストレージボリュームのマッピングに関連する動作を提供するフローチャート図である。ストレージボリューム内のシャードを有向グラフにマッピングするにはまず、ストレージボリューム内のすべての潜在的なシャードを識別する（３０２）必要がある。多数のブロックを有する大きなストレージボリュームを処理する場合には、潜在的な異なるシャーディングの組み合わせは多くなり得る。ストレージボリューム内の潜在的なシャードは、ストレージボリュームにわたる各種のペアワイズのブロックシーケンスに対応する。各種のシャーディング組み合わせは本発明のインプリメンテーションにより後に解析されて、ストレージボリューム（複数可）の最適なシャーディングが判断される。
【００３５】
有向グラフ中の頂点対は、潜在的なシャーディングに対応し（３０４）、すなわち、各頂点対は頂点対間のブロックシーケンスに対応する。たとえば、頂点対（Ｖ０，Ｖ５）は、ブロック１、ブロック２、ブロック３、ブロック４、及びブロック５を含むブロックシーケンスを含むシャードに対応する。
【００３６】
加えて、有向エッジが各頂点対間に作成されて重みが関連付けられる。重みは、頂点対間のブロックシーケンスの相違性を表す（３０６）。１つのインプリメンテーションでは、有向エッジはアドレスの低いブロックから高いブロックへの向きを有し、有向グラフでの頂点アドレスの増大に対応する。各エッジは、低いアドレスで開始し、高いアドレスで終了するシャードを表すため、バックエッジは存在しない。たとえば、頂点Ｖ０とＶ５の間に順方向エッジは存在し得るが、頂点Ｖ５から頂点Ｖ０に向かうエッジは存在しない。こうして得られる、潜在的な各シャーディング毎に頂点対を有するとともに、頂点間の有向エッジに沿って重みを有する有向グラフは、本発明のインプリメンテーションによりストレージボリュームを効率的且つ正確に解析するためのコンテキストを提供する。
【００３７】
図４は、本発明の１つのインプリメンテーションによる、ストレージボリュームの潜在的なシャーディングを表す有向グラフを使用して最適なシャーディングを判断する動作を提供するフローチャート図である。解析を開始する前に、ストレージボリューム内の各ブロックに頂点を有するとともに、ブロックのシャードを表す、頂点対間の有向エッジを有する上述の有向グラフが作成されたものと仮定する。各有向エッジに、対応する頂点対間のブロックのシャードの相違性を表す重みが関連付けられる。
【００３８】
まず、ユーザ又はシステム設計者が、ストレージボリュームを分割するシャードの最大数（Ｋ）を選択する（４０２）。上述したように、シャードの最大数は一般に、ストレージボリュームに関連し、且つストレージシステムを設計又は構築する人物がよく知る或る物理的又は論理的な特性に従って設定される。シャードの最大数（Ｋ）は、本発明がＫ以下のシャードの各組み合わせを調べて、いずれが最適な組み合わせを提供するかを判断するような、超えるべきではない上限として設定される。各シャード内で行われる相違性測定に応じて、Ｋ未満のシャードの組み合わせが、最大数Ｋ個のシャードを使用した場合に可能なものよりも最適なストレージボリュームの分割を表すこともあり得る。たとえば、本発明の１つのインプリメンテーションは、シャードの最大数がＫ＝８であっても、ストレージボリュームを６個のシャードよりも３個のシャードに分割したほうが最適であると判断し得る。
【００３９】
重みベクトルが有向グラフ内の各頂点に関連付けられて、Ｋ以下の有向エッジからの重み合計を保持する（４０４）。有向グラフ内の各頂点が順次解析されて、Ｋ以下のシャードへの、その頂点までのブロックの相違性の最も低いシャーディングが識別される。現在の頂点について、本発明は、ｉ個のシャードの組み合わせに関連する最小重み合計を識別する（４０６）。但し、０＜ｉ＜Ｋ＋１である。重み合計は、有向エッジに関連する重みを、その他の頂点について先に計算された重みに加算することによって計算される。現在の頂点において識別された最小重み合計は、それまでの時点で最小の相違性を有するシャードの組み合わせを表す。多くのブロック及びシャードの組み合わせを有するストレージボリュームでは、この重み合計計算は複雑になる可能性があり、したがって本発明のインプリメンテーションは、各頂点に対して最小重み合計をそのまま全部計算するのではなく、近傍頂点に依って最小重み合計を求める。これは、多くの異なるシャーディング組み合わせの処理を大幅に簡易化し、これについては図５と併せてさらに詳述する。
【００４０】
最終的に、最小重み合計の識別は、本発明のインプリメンテーションにより有向グラフ内のすべての頂点に対して行われる。実際には、各頂点からの情報に対して行われる処理により、有向グラフ内のそのポイントまでの相違性が最小のシャード（１つ又は複数）が判断される。有向グラフ内の最後の頂点を使用して、ストレージボリュームの、Ｋ以下のシャードへの最適なシャーディングが判断される。したがって、最後の頂点に関連する最小重み合計を選ぶことにより、ストレージボリュームにわたるシャーディングが判断され、これはＫ以下のシャードのブロック間で最小の相違性を提供する（４０８）。この最小重みに対応する有向エッジのこの戻り経路を使用して、ストレージボリューム内のブロックを最適なシャーディングに分割する（４１０）。Ｋ以下の有向エッジが使用されるため、ストレージボリュームの分割はＫ以下のシャードに制限される。
【００４１】
図５は、ストレージボリュームでの潜在的なシャードを表す有向グラフに対して最小の重みを効率的に求める動作の、本発明の１つのインプリメンテーションによるフローチャート図を提供する。図５における動作は図４のステップ４０６をさらに詳述し、有向グラフで解析される頂点の最小重み合計を求める１つのインプリメンテーションについて説明している。上述したように、有向グラフ内の各頂点に、Ｋ以下の有向エッジからの重み合計を保持する重みベクトルが関連付けられる。重みベクトルは、ストレージボリュームを分割するシャードの最大数に対応するＫ個のエントリを有する１次元ベクトルであることができる。たとえば、最大シャードＫ＝３の場合、有向グラフでの各頂点は３エントリを有する重みベクトルを有するものと決まる。
【００４２】
各頂点のＫ番目の重みベクトルエントリは、現在の頂点までに少なくともＫ個の有向エッジシーケンスがない場合には「Ｘ」に初期化され、現在の頂点までに少なくともＫ個の有向エッジシーケンスがあり得るが、まだ計算されていない場合にはブランク値に初期化される（５０２）。一般に、有向グラフでの最初の頂点の重みベクトルのすべてのエントリは、最初の頂点への有向エッジがないため常に「Ｘ」エントリに初期化される。同様に、Ｋ＝３の場合、２番目の頂点の重みベクトルの２番目及び３番目のエントリは「Ｘ」に初期化され、最初のエントリは、最初はブランクである。この後者の場合、２番目の頂点までに１つだけ有向エッジがあるため、２番目の頂点の重みベクトルの最初のエントリのみが、計算する必要のある重み値を有する。
【００４３】
各繰り返しにおいて、有向グラフのすべての頂点を考慮し、処理したかが調べられて判断される（５０４）。すべての頂点を訪れ、処理した場合、上述したように有向グラフの最後の頂点の重みベクトルを調べることによって最適なシャーディングが判断され、処理は完了する（５０６）。その他の場合、各頂点が昇順に選択され、Ｋ個の対応する重みベクトルエントリが本発明により投入される（populated）（５０８）。
【００４４】
現在の頂点について、直前の（immediate）有向エッジの重みが、近傍頂点の有向エッジ最小重みと結合されて、Ｋ番目の重みベクトルエントリが識別される（５１０）。現在の頂点と有向グラフにおける最初の頂点との間のすべての有向エッジの重みを再計算するのではなく、近傍頂点の重みベクトルの値が使用される。このショートカット技法では、頂点間の最小重み（すなわち、最小の相違性）が増分的に求められて再使用されるため、処理負荷が低減するとともに時間が短縮される。
【００４５】
場合によっては、現在の頂点の重みベクトルエントリに入力することができる、有向エッジに関連する重みの複数の組み合わせがある（５１２）。これが発生する場合、本発明のインプリメンテーションは、組み合わせの中から最小重みを選択して現在の頂点の重みベクトルに入れる（５１４）。最小重みのみが重みベクトルのＫ個の各エントリに記憶されることを保証することで、後続する頂点がこの近傍情報を使用し、処理を迅速化することが可能になる。重みベクトルが投入されると、有向グラフにおける次の頂点が選択されて処理が続けられる（５１６）。
【００４６】
ストレージボリュームのシャーディングの有向グラフ表現処理に関連する動作は、以下提供するような疑似コードで表すこともできる。
【００４７】
プロシージャ最適シャーディング（Ｄ，Ｋ）
インプット：有向グラフＤ及び長さ制限Ｋ
０：それぞれ１≦ｉ≦Ｎ且つ１≦ｋ≦Ｋにつき
Ｗ０［ｊ］＝“Ｘ””クロスアウト”、Ｗｉ［ｋ］＝ブランクに設定
１：Ｆｏｒ  ｅａｃｈ  １≦ｉ≦Ｎ  ｄｏ
ｆｏｒ  ｅａｃｈ  １≦ｋ≦Ｋ  ｄｏ
Ｖｉに入る有向エッジである、ＶｉのＭの近傍を選ぶ
ｉｆ  Ｗｕ［ｋ−１］がすべての近傍Ｖｕ∈Ｍについてクロスアウトされている
ｔｈｅｎ  Ｗｉ［ｋ］＝クロスアウトに設定
【００４８】
【数３】
2007524922.tif 000005
【００４９】
に設定
２：ＷＮ［１Ｋ  Ｋ］から最小重みを選び、対応する有向パスを返す
但し、
Ｗは頂点Ｖに関連する最小重みエントリを有するＫ次元の重みベクトルであり、
Ｋはストレージボリュームを分割するシャードの最大数であり、
Ｎはストレージボリューム内のブロックの最大数であり、
Ｕは重みベクトルＷ内にエントリを有する近傍頂点の集合であり、
ｄｕｉは頂点Ｖの最短距離である。
【００５０】
図６Ａ〜図６Ｅは、本発明のインプリメンテーションにより処理された、ストレージボリューム内の各種シャードを表す有向グラフの概略図である。この有向グラフ例は、本発明の態様の明確化を助けるために他のストレージアプリケーションと比較して少数の頂点及び有向エッジを有し得るが、提供されるものと同じ又は同様の原理ははるかに多数の複雑なストレージボリュームにも同様に適用される。
【００５１】
図６Ａを参照すると、有向グラフは、本発明による処理の最初の繰り返しでの有向グラフ及び重みベクトルの状態を反映している。この例では、有向グラフは５個の頂点及び１０個の有向エッジ、すなわちＶ０、Ｖ１、Ｖ２、Ｖ３、Ｖ４及びＶ０Ｖ１、Ｖ１Ｖ２、Ｖ２Ｖ３、Ｖ３Ｖ４、Ｖ０Ｖ４、Ｖ０Ｖ２、Ｖ０Ｖ３、Ｖ１Ｖ４、Ｖ１Ｖ３、Ｖ２Ｖ４をそれぞれ有する。頂点Ｖ０の重みベクトル６０２はＫ個の「Ｘ」エントリを有するように初期化される。これは、Ｖ０頂点への有向エッジは１つもないためである。
【００５２】
図６Ｂは、本発明の１つのインプリメンテーションによる２回目の繰り返しでの有向グラフの頂点Ｖ１に関連する重みベクトルの処理を示す。ここで、Ｖ１頂点は１つのみの有向エッジを有するため、対応する重みベクトル６０４の最初のエントリはこの有向エッジの重みを有し、その他の残りのエントリには「Ｘ」エントリが与えられる。２番目及び３番目の重みベクトルには、最初の頂点Ｖ０から現在の頂点Ｖ１までに２つ又は３つの有向エッジシーケンスがないため「Ｘ」エントリが与えられる。
【００５３】
図６Ｃは、本発明の１つのインプリメンテーションによる３回目の繰り返しでの有向グラフの頂点Ｖ２に関連する重みベクトルの処理を示す。この繰り返しでは、重みベクトル６０６の最初の２つのエントリに数値が提供され、３番目のエントリには「Ｘ」エントリが与えられる。重みベクトルの最初のエントリは、１つの有向エッジに関連する重みが２であり、最初の頂点Ｖ０と現在の頂点Ｖ２の間には他に単一の有向エッジがないため２である。しかし、重みベクトルの２番目のエントリは、最初の頂点Ｖ０と頂点Ｖ２の間の、重み１及び２を有する２つの有向エッジを結合したものであるため値３を有する。重みベクトルの３番目のエントリには、最初の頂点Ｖ０と頂点Ｖ２の間に３個の有向エッジの組み合わせがないため「Ｘ」エントリが与えられる。
【００５４】
図６Ｄは、本発明の１つのインプリメンテーションによる４回目の繰り返しでの有向グラフの頂点Ｖ３に関連する重みベクトルの処理を示す。この例では、頂点Ｖ３の重みベクトル６０８の３個すべてのエントリが数値を収容する。その他の例と異なり、この重みベクトルは、評価して２番目のエントリに入れるべき２つの潜在的なエントリ、すなわち、重み９及びより低い重み４を有する。
【００５５】
２つの潜在的なエントリは、この例では、頂点Ｖ０と頂点Ｖ３の間にわたる２つの異なる有向エッジ対があるため発生し、これは、この合流点で評価する必要のあるストレージボリュームの潜在的なシャーディングが２つあることを意味する。第１の潜在的なシャードは、前の有向エッジＶ２Ｖ３に関連する重み値７を、近傍頂点Ｖ２の最初のベクトルエントリの重み値２と結合する。しかし、第１のシャードは、対応する重み７が第２の潜在的なシャードからの重み値４よりも大きいため選択されない。具体的には、第２のシャードの重みは、重み値３を有する前の有向エッジＶ１Ｖ３及び重み値１を有する近傍頂点Ｖ１に関連する重みベクトルの最初のエントリから導出される。
【００５６】
図６Ｅは、本発明の１つのインプリメンテーションによる５回目の繰り返しでの有向グラフの頂点Ｖ４に関連する重みベクトルの処理を示す。頂点Ｖ３に関連する重みベクトルと同様に、重みベクトル６１０は、ストレージボリュームを２分割又は３分割する場合に考慮すべき３つの可能なシャードを表す。ストレージボリュームが２個のシャードに分割される場合、これら２つの異なるシャードの組み合わせに関連する可能な重みとしては、１５、８、及び１３が含まれ、ストレージボリュームを３個のシャードに分割する場合には、可能な重みは９、１７、及び１２になる。ストレージボリュームを単一のシャードに分割する場合には、重み１９を有するたった１つのシャードしか提供されない。本発明によれば、重みベクトルは、ブロック間で最小の相違性を表す値を含むもののみが選択され、頂点Ｖ４に関連するこの重みベクトルには、１９、８、及び９の重みエントリが含まれる。最終的に、重み８に対応するシャーディングが、ストレージボリュームの相違性が最小のシャーディングを表すことから選択される。これら重みに関連する有向エッジを逆に辿ることにより、第１のシャードに関してはストレージボリュームをブロックＢ１、Ｂ２に分割し、第２のシャードに関してはブロックＢ３及びＢ４に分割するシャーディングが生成される。
【００５７】
図７は、本発明の装置又は方法を行う１つのインプリメンテーションにおいて使用されるシステム７００のブロック図である。システム７００は、実行中のプログラムを保持するメモリ７０２（通常、ランダムアクセスメモリ（ＲＡＭ）又はフラッシュＲＯＭ等の書き込み可能読み取り専用メモリ（ＲＯＭ））、ディスプレイ又は出力デバイスとインタフェースして駆動することが可能な表示（presentation）デバイスドライバ８０４、ドライバ又は頻繁に使用される他のプログラムを保持するプログラムメモリ７０８、データ通信のためのネットワーク通信ポート７１０、補助ストレージコントローラを有する補助ストレージ７１２、及びＩ／Ｏコントローラを有する入出力（Ｉ／Ｏ）ポート７１４を備え、これらは共にバス７１６を介して動作可能に接続されている。システム７００は、たとえばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）技術を使用してＲＯＭに予めプログラムすることができ、又は別のソースから（たとえば、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、又は別のコンピュータから）プログラムをロードすることによってプログラム（及び再プログラム）することができる。また、システム７００は、カスタマイズされた特定用途向け集積回路（ＡＳＩＣ）を使用して実施することもできる。
【００５８】
１つのインプリメンテーションでは、メモリ７０２は、ストレージボリュームシャーディング構成要素７１８、ストレージボリューム有向グラフ生成構成要素７２０、最適シャーディング有向グラフ解析構成要素７２２、ストレージボリューム使用・解析構成要素７２４、及びシステム７００上で上記構成要素のうちの１つ又は複数を処理する際に使用されるシステム資源を管理するランタイムモジュールを備える。
【００５９】
ストレージボリュームシャーディング構成要素７１８は、本発明により所与のストレージボリュームを１つ又は複数のシャードに分割するように設計される。ストレージボリューム有向グラフ選択構成要素７２０は、解くために最適シャーディング問題を有向グラフにマッピングする。有向グラフが作成されると、最適シャーディング有向グラフ解析構成要素７２２が、本発明により有向グラフを解析することによってストレージボリュームに最適なシャーディングを判断する。ストレージボリューム使用・解析構成要素７２４は、ストレージボリュームへのアクセスについての情報を収集し、先に示し説明したようにシステムの他の構成要素に統計情報を提供する。
【００６０】
例及びインプリメンテーションを説明したが、これらは本発明のいずれの態様も限定する役割を果たすべきではない。したがって、本発明のインプリメンテーションは、デジタル電子回路、又はコンピュータハードウェア、ファームウェア、ソフトウェア、若しくはこれらの組み合わせで実施することができる。本発明の装置は、機械可読ストレージデバイスに実体的に収容され、プログラマブルプロセッサにより実行されるコンピュータプログラム製品で実施することができ、本発明の方法ステップは、命令プログラムを実行し、入力データを操作し出力を生成することにより本発明の機能を行うプログラマブルプロセッサによって行うことができる。本発明は、結合されてデータストレージシステムを対象にデータ及び命令を送受する少なくとも１つのプログラマブルプロセッサ、少なくとも１つの入力デバイス、及び少なくとも１つの出力デバイスを備えるプログラマブルシステムで実行可能な１つ又は複数のコンピュータプログラムで有利に実施することができる。各コンピュータプログラムは、高水準の手続き型又はオブジェクト指向型のプログラミング言語で、又は所望であればアセンブリ言語若しくは機械語で実施することができ、いずれの場合でも、言語はコンパイル言語であっても、又はインタプリタ言語であってもよい。適したプロセッサとしては、汎用マイクロプロセッサ及び特定用途向けマイクロプロセッサが共に例として挙げられる。一般に、プロセッサは、読み取り専用メモリ及び／又はランダムアクセスメモリから命令及びデータを受け取る。一般に、コンピュータは、データファイルを記憶する１つ又は複数の大容量ストレージデバイスを備え、このようなデバイスとしては、内部ハードディスク及びリムーバブルディスク等の磁気ディスク、光磁気ディスク、及び光ディスクが挙げられる。コンピュータプログラム命令及びデータを実体的に収容するのに適したメモリデバイスとしては、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリデバイス等の半導体メモリ装置、内部ハードディスク及びリムーバブルディスク等の磁気ディスク、光磁気ディスク、及びＣＤ−ＲＯＭディスクを含むすべての形態の不揮発性メモリが挙げられる。上記のいずれもＡＳＩＣにより補完する、又はＡＳＩＣに組み込むことが可能である。
【００６１】
特定の実施形態について、例示を目的として本明細書において説明したが、各種変更を本発明の精神及び範囲から逸脱することなく行うことができる。したがって、本発明は上記インプリメンテーションに限定されず、全範囲の等価物を鑑みて添付の特許請求の範囲により規定される。
【図面の簡単な説明】
【００６２】
【図１】シャードに分割されたストレージボリュームを使用するシステムのブロック図である。
【図２】本発明の１つのインプリメンテーションによる、ストレージボリュームとストレージボリュームに関連するシャードへのブロックの分配との間の関係をマッピングした概略ブロック図である。
【図３】本発明の実施形態による、有向グラフとしてのストレージボリュームのマッピングに関連する動作を提供するフローチャート図である。
【図４】本発明の１つのインプリメンテーションによる、ストレージボリュームの潜在的なシャーディングを表す有向グラフを使用して最適なシャーディングを判断する動作を提供するフローチャート図である。
【図５】ストレージボリュームでの潜在的なシャードを表す有向グラフに対して最小重みを効率的に求める動作の、本発明の１つのインプリメンテーションによるフローチャート図である。
【図６Ａ】本発明のインプリメンテーションにより処理された、ストレージボリューム内の各種シャードを表す有向グラフの概略図である。
【図６Ｂ】本発明のインプリメンテーションにより処理された、ストレージボリューム内の各種シャードを表す有向グラフの概略図である。
【図６Ｃ】本発明のインプリメンテーションにより処理された、ストレージボリューム内の各種シャードを表す有向グラフの概略図である。
【図６Ｄ】本発明のインプリメンテーションにより処理された、ストレージボリューム内の各種シャードを表す有向グラフの概略図である。
【図６Ｅ】本発明のインプリメンテーションにより処理された、ストレージボリューム内の各種シャードを表す有向グラフの概略図である。
【図７】本発明の装置又は方法を行う１つのインプリメンテーションにおいて使用されるシステムのブロック図である。
【符号の説明】
【００６３】
１００・・・システム
１０２，１０４，１０６・・・システム
１０８・・・ネットワーク
１１０・・・ストレージアクセス情報・特性
１１２・・・ストレージマネージャアプリケーション
１１４，１１６・・・ストレージボリューム
１１８，１２０，１２２・・・シャード
２０２・・・ストレージボリューム
２０４・・・一連のブロック
２０６・・・相違性定量
２０８・・・ストレージアクセス情報・特性
２１０，２１２，２１４，２１６・・・シャード
７００・・・システム
７０２・・・メモリ
７０４・・・表示デバイスドライバ
７０６・・・プロセッサ
７０８・・・プログラムメモリ
７１０・・・ネットワーク通信ポート
７１２・・・補助ストレージ
７１４・・・Ｉ／Ｏポート
７１８・・・ストレージボリュームシャーディング構成要素
７２０・・・ストレージボリューム有向グラフ生成構成要素
７２２・・・最適シャーディング有向グラフ解析構成要素
７２４・・・ストレージボリューム使用・解析構成要素
７２６・・・ランタイムモジュール
【図１】
2007524922.tif 000006
【図２】
2007524922.tif 000007
【図３】
2007524922.tif 000008
【図４】
2007524922.tif 000009
【図５】
2007524922.tif 000010
【図６Ａ】
2007524922.tif 000011
【図６Ｂ】
2007524922.tif 000012
【図６Ｃ】
2007524922.tif 000013
【図６Ｄ】
2007524922.tif 000014
【図６Ｅ】
2007524922.tif 000015
【図７】
2007524922.tif 000016
【国際調査報告】
2007524922.tif 000017
2007524922.tif 000018