(57)【要約】  一態様において、本発明は、きめ細かな、拡張可能な方法において、ファイルシステムのためのストレージを拡大する方法に向けられる。本方法は、スパンに対するランバイアスを、ファイルサーバによって判断するステップを含み、ここでランバイアスは、ファイルシステムのためのアドレス移行テーブルにおけるエントリに関連付けられたメモリの隣接するチャンクの数を示す。本方法は、ファイルシステムのためのメモリを拡大する要求を、ファイルサーバによって受信するステップを含む。本方法は、ストライプセット上の未使用のチャンクの数及びファイルシステムによって使用されているストライプセット上のチャンクの数に少なくとも部分的に基づいて、１つのグループのストライプセット中の各ストライプセットを、チャンク割り当て部によって採点するステップを含む。本方法は、最も高いスコアを有するストライプセット上のチャンクを、チャンク割り当て部によって割り当てるステップを含み、そこでは割り当てられたチャンクは、他のファイルシステムのために予約されたランの外側にある。
2016511879.tif 000002
【特許請求の範囲】
【請求項１】
ファイルサーバによってファイルシステムのためのストレージを拡大する方法であって、
前記ファイルシステムは、複数のストライプセットから選択された複数のチャンクを含み、前記ファイルサーバは、前記ファイルシステムの仮想アドレススペースを、前記チャンクに関連付けられた物理記憶アドレスに対応付け、
前記方法は、前記ファイルサーバによって、
ファイルシステムに関連付けられたチャンクを追跡するためのチャンクデータベースを維持するステップであって、該チャンクデータベースは、固定数のエントリを含み、各エントリは、ファイルシステムに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、ステップと、
ファイルシステムを拡大する要求を受信するステップと、
チャンクデータベースに基づいて、ファイルシステムに関連付けられた最後のチャンクを識別するステップと、
少なくとも１つのチャンクがファイルシステムへ割り当て可能である場合、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する前記少なくとも１つのチャンクを割り当てるステップと、
前記少なくとも１つの割り当てられたチャンクによって表される、連続したストレージの長さにおける増加を反映させるために、前記最後のチャンクに関連付けられたチャンクデータベースにおけるエントリを更新するステップと、
を備える、方法。
【請求項２】
請求項１に記載の方法であって、
前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、前記ファイルシステムへの割り当てに対して利用可能であるかどうかを判断する前に、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクを予約するステップであって、それによって、前記少なくとも１つのチャンクが利用可能な状態に留まる、ステップ、
を更に備える、方法。
【請求項３】
請求項１に記載の方法であって、
前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、前記ファイルシステムへ割り当て可能であるかどうかを判断するステップを更に備え、
そのような判断するステップは、
前記ファイルシステムに対するアクティブラン長を判断することと、
前記ファイルシステムへの割り当てに対して利用可能な少なくとも１つのチャンクが存在するのを判断することであって、この判断が行われるのは、前記アクティブラン長がランバイアス未満であり、且つ前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが存在する場合である、ことと、
を備える、方法。
【請求項４】
請求項３に記載の方法であって、
少なくとも１つのチャンクを割り当てるステップは、
前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接するＮ個までのチャンクを割り当てることであって、ここでＮは、前記アクティブラン長を引いた前記ランバイアスに等しい、こと、を備える、方法。
【請求項５】
請求項３に記載の方法であって、
前記ランバイアスを判断するステップを更に備える、方法。
【請求項６】
請求項５に記載の方法であって、
前記ランバイアスを判断するステップは、
ストライプセットの数及びファイルシステムの数に基づいて前記ランバイアスを判断することを備える、方法。
【請求項７】
請求項１に記載の方法であって、
異なるストライプセットから少なくとも１つのチャンクを割り当てるステップであって、この割り当てが行われるのは、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、利用できないと判断される場合である、ステップ、を更に備える、方法。
【請求項８】
データ記憶システムであって、
メモリであって、該メモリに、ファイルシステムに関連付けられたチャンクを追跡するためのチャンクデータベースが格納され、前記チャンクデータベースは固定数のエントリを含み、各エントリは、前記ファイルシステムに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、メモリと、
チャンク割り当て部であって、該チャンク割り当て部は、前記ファイルシステムを拡大する要求を受信し、前記チャンクデータベースに基づいて前記ファイルシステムに関連付けられた最後のチャンクを識別し、少なくとも１つのチャンクが前記ファイルシステムへの割り当てに対して利用可能である場合、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する前記少なくとも１つのチャンクを割り当て、且つ、前記少なくとも１つの割り当てられたチャンクによって表される隣接したチャンクの長さにおける増加を反映させるために、前記最後のチャンクに関連付けられた前記チャンクデータベースにおけるエントリを更新するように構成される、チャンク割り当て部と、
を備える、データ記憶システム。
【請求項９】
請求項８に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する前記少なくとも１つのチャンクを予約するように構成され、この予約が行われた後に、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、前記ファイルシステムへの割り当てに対して利用可能であるかどうかが判断され、それによって、前記少なくとも１つのチャンクが利用可能な状態に留まる、データ記憶システム。
【請求項１０】
請求項８に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、前記ファイルシステムへの割り当てに対して利用可能であるかを判断するように構成され、この判断は、前記ファイルシステムに対するアクティブラン長を判断すると共に、前記ファイルシステムへの割り当てに対して利用可能な少なくとも１つのチャンクが存在することを判断することによって行われ、この判断が行われるのは、前記アクティブラン長がランバイアス未満であり、且つ前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが存在する場合である、データ記憶システム。
【請求項１１】
請求項１０に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接するＮ個までのチャンクを割り当てることによって、少なくとも１つのチャンクを割り当てるように構成され、ここでＮは、前記アクティブラン長を引いた前記ランバイアスに等しい、データ記憶システム。
【請求項１２】
請求項１０に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記ランバイアスを判断するように更に構成される、データ記憶システム。
【請求項１３】
請求項１２に記載のデータ記憶システムであって、前記チャンク割り当て部は、ストライプセットの数及びファイルシステムの数に基づいて前記ランバイアスを判断することによって、前記ランバイアスを判断するように構成される、データ記憶システム。
【請求項１４】
請求項８に記載のデータ記憶システムであって、
前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが利用可能でないと判断される場合、前記チャンク割り当て部は、異なるストライプセットから、そのような少なくとも１つのチャンクを割り当てるように構成される、データ記憶システム。
【請求項１５】
請求項８に記載のデータ記憶システムであって、
前記チャンクデータベースは、ハードウェアにおいて維持され、且つ前記データ記憶システムは、前記チャンク割り当て部と前記ハードウェアとの間で結合されたインターフェースを含み、このインターフェースを通して、前記チャンク割り当て部は前記チャンクデータベースにアクセスする、データ記憶システム。
【請求項１６】
ファイルサーバによってファイルシステム用のストレージを拡大するためのコンピュータプログラムであって、
前記ファイルシステムは、複数のストライプセットから選択された複数のチャンクを含み、前記ファイルサーバは、前記ファイルシステムの仮想アドレススペースを、前記チャンクに関連付けられた物理記憶アドレスに対応付け、
前記コンピュータプログラムは、前記ファイルサーバが、
前記ファイルシステムに関連付けられた前記チャンクを追跡するためのチャンクデータベースを維持し、前記チャンクデータベースは固定数のエントリを含み、各エントリは、前記ファイルシステムに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能であり、
前記ファイルシステムを拡大する要求を受信し、
前記チャンクデータベースに基づいて、前記ファイルシステムに関連付けられた最後のチャンクを識別し、
少なくとも１つのチャンクが前記ファイルシステムへの割り当てに対して利用可能である場合、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する前記少なくとも１つのチャンクを割り当て、
且つ、前記少なくとも１つの割り当てられたチャンクによって表される、隣接するストレージの長さにおける増加を反映させるために、前記最後のチャンクに関連付けられたチャンクデータベースにおけるエントリを更新する、
ことを引き起こすように構成される、コンピュータプログラム。
【請求項１７】
請求項１６に記載のコンピュータプログラムであって、
前記ファイルサーバが、
前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、前記ファイルシステムへの割り当てに対して利用可能であるかを判断する前に、前記少なくとも１つのチャンクが利用可能な状態に留まるように、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する前記少なくとも１つのチャンクを予約する、
ことを引き起こすように更に構成される、コンピュータプログラム。
【請求項１８】
請求項１６に記載のコンピュータプログラムであって、
前記ファイルサーバが、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、前記ファイルシステムへ割り当て可能であるかを判断することを引き起こすように更に構成され、
そのような判断するステップは、
前記ファイルシステムに対するアクティブラン長を判断することと、
前記アクティブラン長がランバイアス未満であり、且つ前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが存在する場合、前記ファイルシステムへ割り当て可能な少なくとも１つのチャンクが存在すると判断することと、
を備える、コンピュータプログラム。
【請求項１９】
請求項１８に記載のコンピュータプログラムであって、
少なくとも１つのチャンクを割り当てるステップは、前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接するＮ個までのチャンクを割り当てることを備え、ここでＮは、前記アクティブラン長を引いた前記ランバイアスに等しく、
又は、前記コンピュータプログラムは、前記ファイルサーバが、前記ランバイアスを判断することを引き起こすように構成される、コンピュータプログラム。
【請求項２０】
請求項１６に記載のコンピュータプログラムであって、
前記ファイルサーバが、
前記最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが利用可能でないと判断される場合、異なるストライプセットからそのような少なくとも１つのチャンクを割り当てることを、
引き起こすように更に構成される、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ記憶システムに関し、且つ、特に、ファイルシステムにディスクスペースをよりきめ細かく、拡張可能に割り当てることが可能なデータ記憶システムに関する。
【背景技術】
【０００２】
今日の情報化時代では、データ記憶システムは、多くの場合、ファイルシステムを管理し、ファイルシステムは、時々、ディスクスペースの動的拡大を要求する。多くの場合、ファイルシステムは、ストレージの増加分において拡大される（本明細書では「チャンク」と呼ばれる）。記憶システムは、自身のサイズが指針チャンクサイズから外れるチャンクを割り当ててもよいが、データ記憶システムは、異なる指針チャンクサイズが選択されることを許可してもよい。１つの代表的なデータ記憶システムでは、チャンクサイズは、１ギガバイト（ＧｉＢ）から１００ＧｉＢまでの範囲にわたることが可能である。別の代表的なデータ記憶システムでは、チャンクサイズは、０．５ＧｉＢから１８ＧｉＢまでの範囲にわたることが可能である。
【０００３】
そのようなシステムのファイルサーバは、ファイルシステムスペースにおけるディスクスペースの仮想アドレスを、物理ストレージにおけるディスクスペースのアドレスに移行し、且つファイルシステムに割り当てられたディスクスペースのチャンクを追跡するために、固定サイズのテーブルを使用してもよい（例えば、テーブルは、１つの代表的なデータ記憶システムにおいて１０２３個のエントリを有し、ここで各エントリは、例えば、チャンクの開始物理アドレス及びチャンクのサイズに関する情報（例えば、チャンク長又はチャンクの終了アドレス）を格納するために使用され、仮想ファイルシステムアドレスの範囲に対応付けられる。固定サイズのテーブルを使用することは、一般にファイルシステムの最大サイズを制限し、即ち、ファイルシステムに割り当てられた所定最大数のチャンクだけを許可する。この固定サイズテーブルは、ハードウェアで履行されてもよく、且つ、いかなる場合も、より大きなファイルシステムがサポートされるのを許可するために、テーブルサイズを増加させることは実行不可能かもしれない。
【０００４】
特別なファイルシステムのために指針チャンクサイズを選択することは、本質的に、ユーザーがファイルシステムにどれだけ大きな成長を期待するかということと、ストレージ使用率の効率との間のトレードオフである。概して言えば、小さな指針チャンクサイズを選択することは、効率的なストレージ使用率に備えるが、ファイルシステムの最大サイズを制限する。その一方で、大きな指針チャンクサイズを選択することは、多くの場合、非効率的なストレージ使用率に帰着するが、最大ファイルシステムサイズを増加させる。
【発明の概要】
【課題を解決するための手段】
【０００５】
ある実施形態において、複数のストライプセットから選択された複数のチャンクを含むファイルシステムに対して、ストレージを拡大するための方法及びデータ記憶システムが提供され、そこでは、ファイルシステムの仮想アドレススペースは、チャンクに関連付けられた物理記憶アドレスに対応付けられる。本方法は、ファイルシステムに関連付けられたチャンクを追跡するための、チャンクデータベースを維持するステップであって、このチャンクデータベースは、固定数のエントリを含み、各エントリは、ファイルシステムに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、ステップと、ファイルシステムを拡大する要求を受信するステップと、チャンクデータベースに基づいて、ファイルシステムに関連付けられた最後のチャンクを識別するステップと、少なくとも１つのチャンクがファイルシステムへ割り当て可能である場合、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクを割り当てるステップと、少なくとも１つの割り当てられたチャンクによって表される、連続したストレージの長さにおける増加を反映させるために、最後のチャンクに関連付けられたチャンクデータベースにおけるエントリを更新するステップと、を含む。
【０００６】
様々な代替的実施形態において、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、ファイルシステムへの割り当て可能であるかを判断する前に、少なくとも１つの最後のチャンクが割り当て可能な状態に留まるように、最後のチャンクと同じストライプセットのうちの最後のチャンクに隣接する少なくとも１つのチャンクが予約されてもよい。
【０００７】
最後のチャンクと同じストライプセットのうちその最後のチャンクに隣接する少なくとも１つのチャンクが、ファイルシステムへ割り当て可能であるかを判断するステップは、ファイルシステムに対してアクティブラン長を判断することと、ファイルシステムへの割り当てに対して少なくとも１つの利用可能なチャンクが存在すると判断することであって、この判断が行われるのは、アクティブラン長がランバイアス未満であり、且つ最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが存在する場合である、こととを含んでもよい。この点に関して、少なくとも１つのチャンクを割り当てるステップは、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接するＮ個までのチャンクを割り当てることを含んでもよく、ここでＮは、アクティブラン長を引いたランバイアスに等しい。本方法はまた、ストライプセットの数及びファイルシステムの数に基づいてランバイアスを判断することによるような、ランバイアスを判断するステップを含む。
【０００８】
本方法は、異なるストライプセットから少なくとも１つのチャンクを割り当てるステップを更に含んでもよいが、この割り当てが行われるのは、最後のチャンクと同じストライプセットのうちの最後のチャンクに隣接する少なくとも１つのチャンクが、利用できないと判断される場合である。
【０００９】
ある実施形態において、チャンクデータベースはハードウェアにおいて維持されてもよく、且つ、データ記憶システムは、ソフトウェアを基本としたチャンク割り当て部とハードウェアとの間で結合されるインターフェースを含んでもよく、この場合、該ハードウェアを通して、チャンク割り当て部はチャンクデータベースにアクセスする。
【００１０】
他の実施形態において、きめ細かな、拡張可能な方法で、ファイルシステムに対してストレージを拡大するための方法及びデータ記憶システムが提供される。本方法は、スパンに対するランバイアスを、ファイルサーバによって判断するステップを含み、そこではランバイアスは、ファイルシステムのためのアドレス移行テーブルにおけるエントリに関連付けられたディスクスペースの隣接するチャンクの数を示す。本方法は、ファイルシステムのためにディスクスペースを拡大する要求を、ファイルサーバによって受信するステップを含む。本方法は、ストライプセット上の未使用のチャンク、及びファイルシステムによって使用されているストライプセット上のチャンクの数に基づいて、１つのグループのストライプセット中の各ストライプセットを、チャンク割り当て部によって採点するステップを含む。本方法は、最も高いスコアを有するストライプセット上のチャンクを、チャンク割り当て部によって割り当てるステップを含み、そこでは割り当てられたチャンクは、他のファイルシステムのために予約されたランの外側にある。
【００１１】
スパンに対するランバイアスを判断するステップは、初期設定ランバイアスを、ファイルサーバによって判断することを含んでもよい。スパンに対するランバイアスを判断するステップは、ストライプセットの数及びファイルシステムの数に基づいて、ランバイアスをファイルサーバによって判断することを含んでもよい。
【００１２】
各ストライプセットを採点するステップは、ファイルシステムの最後に割り当てられたチャンクの後のチャンクが利用可能であることを、チャンク割り当て部によって判断することと、ファイルシステムの現在のストライプセットに対するバイアスファクタを、チャンク割り当て部によって判断することであって、該現在のストライプセットは、ファイルシステムの最後に割り当てられたチャンクを含む、ことと、バイアスファクタを有する現在のストライプセットを、チャンク割り当て部によって採点することと、を含んでもよい。各ストライプセットを採点するステップは、ファイルシステムの最後に割り当てられたチャンクの後のチャンクが別のファイルシステムによって使用されるのを、チャンク割り当て部によって判断することと、ストライプセット上の未使用のチャンクの数と、他のファイルシステムのために予約されたチャンクの数との間の差に少なくとも部分的に基づいて、１つのグループのストライプセット中の各ストライプセットを、チャンク割り当て部によって採点することと、を含んでもよい。各ストライプセットを採点するステップは、ストライプセット上の未使用のチャンクの数、スパン加重、ファイルシステムによって使用されているストライプセット上のチャンクの数、及びファイルシステム加重に少なくとも部分的に基づいて、そのグループのストライプセット中の各ストライプセットを、チャンク割り当て部によって採点することを含んでもよい。
【００１３】
最も高いスコアを有するストライプセット上にチャンクを割り当てるステップは、ファイルシステムの最後に割り当てられたチャンクの後のチャンクを、チャンク割り当て部によって選択することを含んでもよい。最も高いスコアを有するストライプセット上にチャンクを割り当てるステップは、自身の長さが少なくともランバイアスである、予約されていないチャンクのランを、チャンク割り当て部によって検索することと、そのランにおける第１チャンクを、チャンク割り当て部によって選択することと、を含んでもよい。最も高いスコアを有するストライプセット上にチャンクを割り当てるステップは、自身の長さが少なくともランバイアスである予約されたチャンクのランを、チャンク割り当て部によって検索することと、そのランの後半における第１チャンクを、チャンク割り当て部によって選択することと、を含んでもよい。
【００１４】
更に他の実施形態において、複数のストライプセットから選択された複数のチャンクを含むファイルシステム対してストレージを拡大するための方法及びシステムが提供され、そこでは、ファイルシステムの仮想アドレススペースが、チャンクに関連付けられた物理記憶アドレスに対応付けられる。本方法は、複数のファイルシステムに関連付けられたチャンクを追跡するための、チャンクデータベースを維持するステップであって、該チャンクデータベースは固定数のエントリを含み、各エントリは、ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、ステップと、複数のファイルシステムにおいて、ファイルシステムを拡大する要求を受信するステップと、自身からストレージを割り当てるべきストライプセットを選択するステップと、ストライプセット上で開始アドレスを有するチャンクデータベースからエントリを受信するステップであって、そこではエントリは、複数のファイルシステムにおける、異なるファイルシステムのライブランに対応する、ステップと、ストライプセット上で少なくとも１つのチャンクを識別するステップであって、該ストライプセットは、ライブランにおける最後のチャンクに続き、且つこれに隣接するＮ個のチャンクの後に位置し、そこではＮは、ライブランのアクティブラン長を引いたランバイアスに等しい、ステップと、もし少なくとも１つのチャンクが利用可能である場合、少なくとも１つのチャンクをファイルシステムに割り当てるステップと、を含む。
【００１５】
様々な代替的実施形態において、本方法は、ストライプセット上に開始アドレスを有するチャンクデータベースからエントリを引き出し、且つ少なくとも１つのチャンクを識別することを継続するステップであって、該少なくとも１つのチャンクは、少なくとも１つのチャンクが利用可能となるまで、ライブランにおける最後のチャンクに続き、且つこれに隣接するＮ個のチャンクの後に位置する、ステップ、を更に含んでもよい。ストライプセット上で少なくとも１つのチャンクを識別するステップは、ランバイアスに等しい利用可能なチャンクのランを識別することか、又はストライプセット上で利用可能なチャンクの最も長いランを識別することを含んでもよい。
【００１６】
更に他の実施形態において、複数のストライプセットから選択された複数のチャンクを含むファイルシステムに対して、ストレージを拡大するための方法及びデータ記憶システムが提供され、そこではファイルシステムの仮想アドレススペースは、チャンクに関連付けられた物理記憶アドレスに対応付けられる。本方法は、複数のファイルシステムに関連付けられたチャンクを追跡するための、チャンクデータベースを維持するステップであって、該チャンクデータベースは、固定数のエントリを含み、各エントリは、ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、ステップと、複数のファイルシステムにおいて、ファイルシステムを拡大する要求を受信するステップと、要求に対するチャンクの数が、スパン上のストライプセットの数が掛けられたランバイアスにおけるチャンクの数を超えることを判断するステップと、要求に対するチャンクの数をストライプセットの数で割ることによって、各ストライプセットから割り当てるべきチャンクの数を判断するステップと、各ストライプセットから割り当てるべきチャンクの数に等しい、利用可能なチャンクのランを、各ストライプセット上で検索するステップと、利用可能なチャンクのランを、各ストライプセットから割り当てるステップと、利用可能なチャンクのランに関連付けられたチャンクデータベースにおけるエントリを、利用可能なチャンクの各ランに対して作成するステップであって、該エントリはランの長さを含む、ステップと、を含む。
【００１７】
実施形態はまた、上記方法のいずれかを実行するように構成されたコンピュータプログラムを含んでもよい。
【００１８】
実施形態はまた、有形のコンピュータ可読な媒体を備える装置を含んでもよく、該有形のコンピュータ可読な媒体は、上記方法のいずれかを実行するように構成されたコンピュータプログラムを、自身の中に具体化している。
【００１９】
付加的な実施形態が開示され、且つ請求されてもよい。
【図面の簡単な説明】
【００２０】
本発明の前述の特徴は、添付図面に関して得られた、以下の詳細な記述を参照することによって、より容易に理解されるであろう。
【図１】図１は、本発明の代表的な実施形態に従うファイル記憶システムの概略的ブロック図である。
【図２】図２は、本発明の代表的な実施形態に従うファイルシステムの一般的なフォーマットを示す概略的ブロック図である。
【図３】図３は、本発明の代表的な実施形態における、記憶ブロックとストライプセットとの間の関係を示す概略図である。
【図４】図４は、ファイル記憶システムのファイルサーバの概略的ブロック図である。
【図５】図５は、既に使用されている幾つかのチャンクと、ファイルシステムに自由に割り当てられるべき幾つかのチャンクとを含むストライプセットにおけるチャンクの概略的表現である。
【図６】図６は、テーブル９０２５の概略的表現であり、この表現は、代表的な先行技術の実施形態における特定の時点で見つけられるかもしれず、ここで各新しいチャンクのための情報は、別個のテーブルエントリに格納される。
【図７】図７は、テーブル９０２５の概略的表現であり、この表現は、代表的な実施形態における特定の時点で見つけられるかもしれず、ここで隣接するチャンクに対する情報は、図６に示されたテーブル９０２５の代わりに、単一のテーブルエントリに格納されてもよい。
【図８】図８は、テーブル９０２５の概略的表現であり、この表現は、１つの代表的な実施形態に従って、図７のテーブルエントリ９０３０が、２つの付加的な隣接するチャンクを組み込むために、いかにして修正されるかを示している。
【図９】図９は、図４のファイルシステムスペースの概略的表現であり、該ファイルシステムスペースは、１つの代表的な実施形態に従って、同じサイズ（例えば、Ｘ）の３つのチャンクだけ拡大される。
【図１０】図１０は、１つの代表的な実施形態に従う、包括的なチャンク割り当てプロセスのフローチャートである。
【図１１】図１１は、ファイルシステムに割り当てるべきストライプセット及びストライプセット上のチャンクを選択する方法の、代表的流れ図である。
【図１２】図１２は、ストライプセットを選択する方法の代表的な流れ図であり、該ストライプセットからチャンクが割り当てられるが、それは、現在のストライプセットが、図示され且つ説明されるファイルシステムに対して、拡大可能なライブランを含む場合である。
【図１３】図１３は、ストライプセットを選択する方法の代表的な流れ図であり、該ストライプセットからチャンクが割り当てられことになるが、それは、現在のストライプセットが、図示され且つ説明されるファイルシステムに対して、拡大可能なライブランを含まない場合である。
【図１４】図１４は、ファイルシステムに割り当てられるランのファイルシステムスペースにおいて、開始アドレス及び終了アドレスを格納する代表的なテーブルである。
【図１５】図１５は、スパンにわたる負荷均衡を改善するために、ランバイアスを低減する方法のための代表的な流れ図である。
【図１６】図１６は、ファイルシステムに割り当てるべきストライプセット上で、予約されていないチャンクを検索する方法のための代表的な流れ図である。
【図１７】図１７は、スパンにおける全てのストライプセットにわたって、ストレージを割り当てる方法のための代表的な流れ図である。  注意されるべきことであるが、前述の図及び、これの中に描かれた要素は、必ずしも一貫性のあるスケール、又は任意スケールに対して描かれていない。文脈で特に断りが無ければ、要素は参照符号によって示された通りである。
【発明を実施するための形態】
【００２１】
定義：この記述及び添付の請求項において使用されるように、以下の用語は、文脈で特に要求がなければ、示された意味を有するものとする。
【００２２】
「記憶装置」は、データを格納するために使用される装置又はシステムである。記憶装置は、１以上の磁気ディスクドライブ、又は光磁気ディスクドライブ若しくは光ディスクドライブ、固体記憶装置、又は磁気テープを含んでもよい。便宜上、記憶装置は、「ディスク」又は「ハードディスク」と時々呼ばれる。データ記憶システムは、同じ又は異なる記憶容量を有する、同じ又は異なるタイプの記憶装置を含んでもよい。
【００２３】
「ＲＡＩＤコントローラ」は、幾つかの記憶装置の記憶容量を、ストレージスペースの仮想区画に結合する装置又はシステムであり、このストレージスペースの仮想区画は、代わりに、「システムドライブ」（「ＳＤ」）、「論理ユニット」（「ＬＵ」又は「ＬＵＮ」）又は「ボリューム」と呼ばれてもよい。通常、ＳＤは単一の記憶装置よりも大きく、幾つかの記憶装置からスペースを引き出し、且つ冗長情報を含み、それによって、データを喪失することなく、ある数のディスクの故障にも耐えることが可能である。代表的な実施形態において、各ＳＤは、以下では「論理ユニット識別子」又は「ＬＵＩＤ」と呼ばれる一意識別子に関連付けられ、且つ各ＳＤは、所定最大サイズ、例えば２ＴＢ〜６４ＴＢ又はそれ以上、よりも大きくないであろう。コマンドがＳＤに送信されると、ＲＡＩＤコントローラは、通常、コマンドをＳＤの全ての記憶装置に同時に転送する。ＲＡＩＤコントローラは、典型的な記憶装置の３つの主な制限を克服するのを手伝うが、３つの主な制限とは、即ち、それらの記憶装置は通常、記憶システムの中で最も遅い構成装置であり、それらは通常、破局故障を最も受けやすく、且つそれらは通常、比較的小さな記憶容量を有することである。
【００２４】
「ＲＡＩＤシステム」は、１以上のＲＡＩＤコントローラと多数の記憶装置とを含む装置又はシステムである。通常、ＲＡＩＤシステムは、２つのＲＡＩＤコントローラ（これによって、もし一方が故障しても、他方が動き続け、且つ、更に、両方が正常である間は、負荷を共有する）と、数十の記憶装置とを含む。代表的な実施形態において、ＲＡＩＤシステムは、通常、２個と３２個の間のＳＤで構成されるが、しかし、様々な実施形態においては、代表的なＲＡＩＤシステムはより多くのＳＤを有してもよい。ファイルサーバがデータを格納するか、又は引き出す必要がある場合、ファイルサーバは、ＲＡＩＤシステムのＲＡＩＤコントローラにコマンドを送信し、今度はＲＡＩＤコントローラが責任を負い、個々の記憶装置に対して前方にコマンドを特定のルートで送信し、且つ、必要に応じて、データを格納するか又はデータを引き出す。幾つかのＲＡＩＤシステムによって、ＳＤ間でミラーの関係が確立され得る。それによって、１つのＳＤ（「一次ＳＤ」と呼ばれる）に書かれたデータは、冗長性の目的のために、ＲＡＩＤシステムによって別のＳＤ（本明細書では「二次ＳＤ」又は「ミラーＳＤ」と呼ばれる）に自動的に書かれる。二次ＳＤは、一次ＳＤと同じＲＡＩＤシステムによって、又は、異なるローカルＲＡＩＤシステム又は遠隔ＲＡＩＤシステムによって管理されてもよい。ＳＤを効率的にミラー化することは、ＳＤにわたるＲＡＩＤ（１＋０）機能性を提供するが、この目的は、１つのＳＤが喪失又は破損した場合、又は、幾つかの状況では、複数のＳＤでさえも喪失又は破損する場合が起こり得るが、そのような場合からの回復を提供することである。
【００２５】
「ファイルシステム」は、ファイル記憶システムに格納されるファイル及びディレクトリ（フォルダ）の構造である。幾つかの実施形態において、ファイルシステムは、１以上のストライプセットのチャンク上に存在するディスクスペースの仮想化された領域である。ファイル記憶システム内では、ファイルシステムは、通常、多数の仮想記憶構成を用いて管理され、且つ、代表的な実施形態においては、ファイルシステムは、レンジ、ストライプセット、及びスパンと呼ばれる仮想記憶構成の階層を用いて管理される。「レンジ」は、それ自身上の一次ＳＤか、又は同一のデータを含むと想定される一次／二次ＳＤペアのいずれかで構成され、且つ、それ故に、単一のＳＤと同じ記憶容量を提供する。「ストライプセット」は、１以上のレンジで構成される。幾つかの実施形態において、ストライプセットは、３２個までの論理ユニット（「ＬＵ」）を含むことが可能である。ストライプセットは、もしその全てのチャンクが使用中である場合、「一杯で」ある。そうでない場合、ストライプセットは「一杯ではない」。「スパン」は１以上のストライプセットから構成される（例えば、６４個までのストライプセットから構成され、ここでストライプセットは、同じ容量を持つ必要はなく、又は互いに同じ数のＬＵを含む必要はない）。幾つかの実施形態において、スパンは複数のファイルシステムを含む（例えば、１２８個までのファイルシステム）。従って、スパンは、結局、１以上のＳＤから構成される（通常、４個から５０個のＳＤ）。スパンは、１以上のファイルシステムに分割されることが可能であり、各ファイルシステムは別個の名称、及び識別子、並びに潜在的に異なる特性を有する（例えば、１つのファイルシステムは、３２ＫＢクラスタでフォーマットされ、且つ別のファイルシステムは、４ＫＢクラスタでフォーマットされてもよく、１つのファイルシステムは、ワーム（Ｗｏｒｍ、ライトワンス）であってもよく、別のファイルシステムは、そうでない、など）。スパン上の各ファイルシステムは、別々にフォーマットされ、利用可能な状態にされ、そして利用不可能な状態とされる。ファイルシステムは、任意の順に、且ついつでも、作成され、削除されてもよい。ファイルシステムは、自動的に拡大するように（又は、代わりに、自動拡大を防止、又は制限するように）構成され得るか、又は手動で拡大され得る。ある実施形態において、ファイルサーバは、「チャンクデータベース」にファイルシステムのディスクスペースの仮想アドレス及び物理アドレスを格納する。様々な実施形態において、ファイルサーバは、ディスクインターフェース（ＤＩ）チップ上のテーブルのエントリに、ファイルシステムのディスクスペースについての情報を格納する。テーブル中の各エントリは、ファイルシステムに割り当てられたディスクスペースの部分の開始位置及び終了位置を含む。
【００２６】
「チャンク」は、単一のストライプセット上のディスクスペースの領域である。幾つかの実施形態において、チャンクは、ファイルシステムに付加されるディスクスペースの増加分であってもよい。各チャンクは、単一のストライプセット上に存在し、例えば、チャンクは、複数のストライプセットにまたがらない。幾つかの実施形態において、チャンクのサイズは、１ギガバイト（ＧｉＢ）と１００ＧｉＢとの間の範囲にわたってもよい。チャンクがファイルシステムに割り当てられていない場合、チャンクは「利用可能」又は「空き」の状態である。チャンクが割り当てられている場合、チャンクは、「使用中」であり、別のファイルシステムに割り当てられ得ない、又は同じファイルシステムに再使用され得ない。チャンクは「空き」か、又は「使用中」かのいずれかであり、例えば、チャンクが部分的に使用され、且つ部分的に空きであることはあり得ない。幾つかの実施形態において、スパンが作成される場合、管理者は指針チャンクサイズを設定する。指針チャンクサイズは、スパンにおけるチャンクサイズの概数である。ファイルサーバは、異なるサイズのチャンクを割り当てることが許される。それ故に、スパンにおけるチャンクは、互いに異なる容量を有し、且つ指針チャンクサイズとは異なる容量を有する。
【００２７】
「ラン」は、一連の、１以上のチャンクであり、これら一連のチャンクは、ファイルシステムスペース内で、及び論理ユニットスペース内で隣接している。従って、ファイルサーバは、ランの中の全てのチャンクに対して、単一の連続読み出し又は書き込み動作を実行できるであろう。更には、読み出し又は書き込み動作は、ストライプセットにおける論理ユニットの各々に相当する動作に移行され、各論理ユニット上の同じアドレスで開始し、且つ各論理ユニット上の同じアドレスで終了する。典型的な実施形態において、ある環境下では、ランは、単一のチャンクとして始まり、且つ拡大され、単一のストライプセットからの複数の隣接するチャンクを含むことが可能である。
【００２８】
「ランバイアス」は、ランの好ましい長さであり、これは、ファイルシステムに割り当てられたディスクスペースのアドレスを記憶するテーブルにおける単一のエントリに格納される。ランバイアスは、ファイルサーバが、ストライプセットの中での負荷不均衡を許容する程度を示すかもしれない。ランバイアスがより低い場合、ファイルサーバは、スパンにわたって均衡された負荷を保つために、異なるストライプセットから、より頻繁にチャンクを割り当てる（例えば、ファイルサーバは、自身が別のストライプセットからチャンクを割り当て始める前に、１つのストライプセットからチャンクを割り当てることはほとんどない）。幾つかの実施形態において、スパンが、少数しかチャンクを有せず、しかし多くのストライプセットを有する場合、ファイルサーバは、スパンにわたる負荷均衡を改善するために、より低いランバイアスを決定する。
【００２９】
「ライブラン」（ｌｉｖｅ  ｒｕｎ）は、拡張され得るファイルシステムに割り当てられるチャンクのランである。このランは、ファイルシステムの中の最後のランであり、且つこのランには、このランと同じストライプセット上の空のチャンクが直ちに続く。
【００３０】
ストライプセット上の空のチャンクのランは、２つのランに分割され得る。これらのランの１つは、「請求されたラン」であり、これは、自身の長さがランバイアスよりも短いライブランに直ちに続く空のチャンクのランである。請求されたランは、その長さがランバイアスに等しいように、ライブランを拡大するのに必要とされる数のチャンクを含んでもよい。
【００３１】
「請求されないラン」は、請求されたランに直ちに続く空のチャンクのランである。チャンク割り当て部は、請求されないランから、チャンクを自由に割り当てる。
【００３２】
「チャンクデータベース」は、１以上のファイルシステムに関連付けられたチャンクを追跡するために使用される記憶構成である。図１は、本発明の１つの代表的な実施形態に従うファイル記憶システムの概略的ブロック図である。とりわけ、ファイル記憶システムは、多数のファイルサーバを含み（単一のファイルサーバ９００２が、簡単且つ便宜のために示されている）、これら多数のファイルサーバは、インターネット・プロトコル・ネットワーク（例えば、インターネット）のような通信ネットワーク９００４を通して様々なクライアント装置（９００６ｉ〜９００６Ｍ）と通信し、且つまた、ファイバーチャネル・ネットワークのような記憶ネットワーク９０１０を通して様々なＲＡＩＤシステム（９００８ｉ〜９００８Ｎ）と通信する。クライアント装置（９００６ｉ〜９００６Ｍ）及びファイルサーバ９００２は、ＣＩＦＳ及び／又はＮＦＳのような１以上のネットワーク・ファイル・プロトコルを用いて通信する。ファイルサーバ９００２及びＲＡＩＤシステム（９００８ｌ〜９００８Ｎ）はＳＣＳＩのような記憶プロトコルを用いて通信する。注意されるべきことであるが、ファイル記憶システムは、様々な配置で相互連結された、複数のファイルサーバ及び複数のＲＡＩＤシステムを含むことが可能であろう。ここで、様々な配置には完全なメッシュ配置が含まれ、このメッシュ配置の中で、任意のファイルサーバは、冗長で且つ切り替えられたファイバーチャネル・ネットワークを通して、任意のＲＡＩＤシステムと通信する。
【００３３】
ファイルサーバ９００２は、１以上のファイルシステムを管理する。ファイルサーバ９００２は、クライアントが、指定された名称下でのツリー又はサブツリーのような、ファイルシステムの部分にアクセスできるように構成され得る。ＣＩＦＳ用語では、そのようなアクセスは、「シェア」と呼ばれ、その一方で、ＮＦＳ用語では、そのようなアクセスは「エクスポート」と呼ばれるかもしれない。内部的には、ファイルサーバ９００２は、例えば米国特許出願第０９／８７９，７９８号及び米国特許出願第１０／８８９，１５８号（これらは、上記参照によって包含された）に記載されるハードウェア履行型及び／又はハードウェア加速型サブシステムを含んでもよく、且つ、例えば米国特許出願第１０／２８６，０１５号及び米国特許出願第１１／８４１，３５３号（これらは、上記参照によって包含された）に記載されるような複数の連鎖したサブモジュールを含む、ハードウェアを基本としたファイルシステムを含んでもよい。
【００３４】
各ＲＡＩＤシステム９００８は、ＲＡＩＤコントローラによって管理される多数の物理記憶装置（例えば、ディスク）はもちろんのこと、通常、少なくとも１つのＲＡＩＤコントローラ（及び、普通は冗長性のために２つのＲＡＩＤコントローラ）を含む。ＲＡＩＤシステム９００８は、その記憶リソースを多数のＳＤに統合する。例えば、各ＲＡＩＤシステム９００８は、２個から３２個の間のＳＤで構成されてもよいが、しかし、幾つかの例では、各ＲＡＩＤシステムはより多くのＳＤに対して構成されてもよい。各ＳＤは、所定最大サイズ（例えば、２ＴＢ〜６４ＴＢ又はそれ以上）に制限されてもよい。幾つかの記憶装置を１つのＳＤに結合することは、多くの利益を提供でき、これらの利益が含むものとして、増大される速度（個々の記憶装置は比較的遅いが、しかしデータは、ボトルネックを広げるために、幾つかの記憶装置にわたってストライプ化され得る）、増大される容量（個々の記憶装置は比較的小さいが、しかし幾つかの記憶装置は、より多くの使用可能なスペースを提供するために、結合され得る）、抽象作用（使用されるスペースの量は、単一の記憶装置のサイズよりも大きいか、又は小さいかのいずれかであり得る）及び障害許容力（パリティ情報又は冗長性情報が各記憶装置上に格納され、ＳＤは記憶装置の喪失に耐え得る）がある。
【００３５】
ファイルサーバ９００２は、１以上のＳＤを使用するように構成され、これらは、単一のＲＡＩＤシステムから、又は複数のＲＡＩＤシステムからのものであり得る。ファイルサーバ９００２は、各ＳＤが一次か二次であるかを見つけるために、普通はＲＡＩＤシステムに質問できる。どのＳＤがファイルサーバ９００２によって使用されるかを制御する方法は、本明細書では「認可」と呼ばれる。従って、実際には、ファイルサーバ９００２は、通常、幾つかのＳＤに対して認可され、他のＳＤに対して認可されない。
【００３６】
内部的には、ファイルサーバ９００２は、幾つかのＳＤを、本明細書で「スパン」と呼ばれるより大きな記憶プールに結合することが可能である。スパンは、本質的に、幾つかのＳＤのＲＡＩＤ−０アレイである。幾つかのＳＤを１つのスパンに結合することは、複数のディスクを１つのＳＤに結合することによって得られるのと同様な多くの利益を提供でき、これらの利益が含むものとして、増大された速度（複数のＲＡＩＤシステム上の複数のＳＤ間にＩ／Ｏを分散させることは、記憶ボトルネックを更に広げ得る）、増大された記憶容量（スパンは単一のＳＤよりも大きいことが可能であり、これは２テラバイトに制限されるかもしれない）、及び、より多くの柔軟なストレージスペースの割り当てに備える付加的な抽象作用がある。
【００３７】
図２は、本発明の代表的な実施形態に従うスパンの概略的ブロック図である。図示されるように、スパン９０１１は、論理的に隣接するストレージスペースを提供する多数のストライプセット（９０１２ｉ〜９０１２ｋで番号付けされる）から構成される。各ストライプセット９０１２は、今度は、１以上のレンジ及び、それ故に、１以上のＳＤから構成される。この例では、ストライプセット９０１２ｉは、９０１３ｉ〜９０１３ｊで番号付されたレンジを含む。
【００３８】
大量のデータがストライプセットに書かれる場合、ファイルサーバ９００２は、一般に、単一のレンジ／ＳＤに全てのデータを書くというよりも、ストライプセットの中の複数のレンジ／ＳＤにわたってデータを「ストライプ化」する。例えば、大量のデータが書かれる場合、ファイルサーバ９００２は、レンジ／ＳＤ９０１３１に最初の４ＭＢのデータを、レンジ／ＳＤ９０１３２に次の４ＭＢのデータを、などと言うように書いてもよく、レンジ／ＳＤ９０１３ｊまでデータを書いた後は、レンジ／ＳＤ９０１３１へ戻って再び循環する。とりわけ、そのような「ストライピング」は、ファイルサーバ９００２が、幾つかのＲＡＩＤシステムによって管理される可能性のある幾つかのＳＤ（及び、それ故に、幾つかの記憶装置）を使用する機会を増加させる。
【００３９】
注意されるべきことであるが、代表的な実施形態において、スパンが作成される場合、スパン９０１１は、初めは単一のストライプセットを含むが、しかし付加的なストライプセットが、時間と共にスパンに加えられてもよく、且つ異なるストライプセットが、異なる数のレンジ／ＳＤを有してもよい。代表的な実施形態において、各ストライプセットは、それらの容量とは無関係に、３２個までのＳＤを含むことが可能である。各ＳＤはミラー化されてもよく、しかしそのようなミラー化は、ファイルサーバ９００２によってというよりは、ＲＡＩＤシステムによって実行される。それ故に、ミラー化されたＳＤに対して、ファイルサーバ９００２は、一次ＳＤにだけコマンドを送信し、且つ一次ＳＤだけが、ストライプセット当たり３２個のＳＤの制限に向けて数を数える。また、代表的な実施形態において、いったんストライプセットが作成されると、それ以上のＳＤは、そのストライプセットに付加されない。それ故に、ＳＤをスパンに付加するためには、付加的なＳＤに対して、新しいストライプセットが形成され、且つ新しいストライプセットは、本質的に、スパンに現存するストライプセットに連結される。
【００４０】
従って、例えば、スパンは、０〜３で番号付けされた４つのＳＤを有する単一のストライプセットを初めは含んでもよい。５〜７で番号付けされた３つの新しいＳＤをスパンに付加するために、ＳＤ（５〜７）を含む第２ストライプセットが作成され、且つ第２ストライプセットは、第１ストライプセットに連結される。現存するデータは、スパンの中の全ての７つのＳＤにわたって、「再ストライプ化される」ことはない。
【００４１】
本質的には、ファイルシステムは、ストレージのＮ個の連続するブロックを有する連続したストレージスペースとして見ることが可能である。この議論のために、ブロックは、連続して０から（Ｎ−１）までで、論理的に番号付けされることが可能である。現実には、ファイルシステムストレージスペースは、スパン内で物理的に隣接していなくてもよく、且つ複数のストライプセットからのストレージを含んでもよい。概して言えば、ファイルサーバ９００２は、ファイルシステム記憶ブロックを、スパン内の物理記憶位置に対応させる。従って、ファイルシステムが複数のストライプセットからのストレージを含むような代表的な実施形態において、第１セットのファイルシステム記憶ブロックは、第１ストライプセットに対応付けされ、且つ第２セットのファイルシステム記憶ブロックは、第２ストライプセットに対応付けされる、などであろう。
【００４２】
図３は、本発明の代表的な実施形態における、記憶ブロックとストライプセットとの間の関係を示す概略図である。この例では、２つのストライプセットからのチャンクを備えた０から（Ｎ−１）までで番号付けされたＮ個の記憶ブロックがあり、そこでは、（０から（Ｍ−１）で番号付けされた）第１のＭ個のブロックは、ストライプセット１からのチャンクに対応付けられ、且つ（Ｍから（Ｎ−１）で番号付けされた）残りの（Ｎ−Ｍ）個のブロックは、ストライプセット２からのチャンクに対応付けられる。注意されるべきことであるが、各ストライプセットに関連付けられた数百万のブロックがあってもよく、且つブロックの数は、各ストライプセットで異なっていてもよい。注意されるべきことであるが、割り当ては、ファイルシステムに対して時間と共になされるため、典型的なファイルシステムは、各ストライプセットから多くの範囲を有するであろう。例えば、ファイルシステムは、ストライプセット０からの７ＧｉＢ、ストライプセット２からの９ＧｉＢ、ストライプセット１からの１３ＧｉＢ、ストライプセット０からの１１ＧｉＢ、ストライプセット１からの１８ＧｉＢ、ストライプセット０からの８ＧｉＢ、ストライプセット２からの２１ＧｉＢ、などを有するであろう。更に、ファイルシステムは、同じストライプセットの異なる領域から、幾つかの連続した範囲を有することが可能であり、このことは、もしスパンがただ１つ又は２つのストライプセットを含む場合、特にありそうなことである。
【００４３】
図４は、１つの代表的な実施形態に従う、ファイルサーバ９００２上のスパンマネージャ９００３の概略的ブロック図である。とりわけ、スパンマネージャ９００３は、１以上のチャンク割り当て部９０１４及びＶＬＳＩインターフェース９０１５を含み、ＶＬＳＩインターフェース９０１５を通して、スパンマネージャ９００３は、様々なハードウェアを基本としたファイルシステム構成要素とインターフェースで連結する。これらのファイルシステム構成要素は、ファイルシステムに割り当てられたランの位置を格納するテーブル９０２５を有するディスクインターフェース（ＤＩ）チップ９０２０を含む。スパンマネージャ９００３はまた、ファイルシステムに割り当てられたチャンクに関する情報を格納するチャンクデータベース９０３０とインターフェースで連結する。多くの実施形態において、チャンクデータベース９０３０は、スパン上のあらゆるチャンクについての情報を格納する。チャンクデータベース９０３０は、ディスク上に、メモリの中に、又はその両方に維持される。スパンマネージャ９００３のチャンク割り当て部９０１４は、チャンクデータベース９０３０を操作する。
【００４４】
ＤＩチップ９０２０は、物理ストレージとの接続性に対して（例えば、ディスク及び／又はバックエンドのファイバーチャネルＳＡＮ上の固体記憶装置）、及びいかにしてデータが格納され、且つそれらの物理的装置にわたって分散されるかを制御することに対して責任を負う。スパンマネージャ９００３が、ファイルシステムのディスクスペースを拡大する要求をクライアント装置９００６から受信すると、チャンク割り当て部９０１４は、ファイルシステムにどのチャンクを割り当てるべきかを判断する。
【００４５】
幾つかの実施形態において、ファイルサーバ９００２は、単一のチャンク割り当て部９０１４を含む。
【００４６】
チャンク割り当て部９０１４は、本明細書で更に説明されるように、異なるスパンに対して、スパン加重及びファイルシステム加重のセットを格納する。チャンク割り当て部９０１４は、拡大されているファイルシステムが存在するスパンに基づいて、スパン加重及びファイルシステム加重を選択する。他の実施形態において、ファイルサーバ９００２は、異なるチャンク割り当て部９０１４を含み、各チャンク割り当て部９０１４は、スパン加重及びファイルシステム加重の異なるセットを格納する。幾つかの実施形態において、スパンマネージャ９００３は、クライアント装置９００６に基づいて、チャンク割り当て部９０１４を選択する。幾つかの実施形態において、スパンマネージャ９００３は、拡大されるべきファイルシステムに基づいて、チャンク割り当て部９０１４を選択する。
【００４７】
チャンク割り当て部９０１４は、論理ユニットに対する装置識別子はもちろんのこと、論理ユニット上のディスクスペースにおいて、チャンクの仮想アドレス及び対応する物理アドレスを判断する。チャンク割り当て部９０１４は、チャンクデータベース９０２５において、及びＤＩチップ９０２０の中のテーブル９０２５において割り当てられるチャンクに関する情報を格納する。幾つかの実施形態において、チャンク割り当て部９０１４は、チャンクデータベース９０２５における、個々に割り当てられた各チャンクについての情報を格納する。チャンク割り当て部９０１４はまた、新しく割り当てられたチャンクを反映するために、ＶＬＳＩインターフェース９０１５を通して、ＤＩチップ９０２０上のテーブル９０２５を更新する。
【００４８】
幾つかの実施形態において、テーブル９０２５は、ボリューム対応付けテーブル及びストライプセット対応付けテーブルを含む。チャンク割り当て部９０１４は、ボリューム対応付けテーブルのエントリにおけるランに対して、ファイルシステムスペースにおける開始アドレス及び終了アドレスを格納し、且つ／又は更新する。ストライプセット対応付けテーブルは、ＳＤスペースにおけるアドレスと共に、ファイルシステムスペースにおけるアドレス間の関係を格納する。従って、ボリューム対応付けテーブル及びストライプセット対応付けテーブルを用いて、ファイルシステムは、自身に割り当てられているディスクスペースのチャンクにアクセスできる。幾つかの実施形態において、チャンク割り当て部９０１４は、仮想アドレス、物理アドレス、及びチャンクに対応する装置識別子のような情報を格納する。幾つかの実施形態において、仮想アドレスはファイルシステムのオフセットであり、装置識別子はＬＵ装置識別子であり、且つ物理アドレスは、論理ユニット上のオフセットである。
【００４９】
代表的な実施形態において、任意の方法でストライプセットからチャンクを割り当て、且つ付加された各チャンクに対してチャンクデータベース９０２５で別個のテーブルエントリを用いるというよりは、ファイルシステムが１以上のチャンクによって拡大される場合、スパンマネージャ９００３、及び特にチャンク割り当て部９０１４は、以下でより完全に議論されるある環境の下で、ファイルシステムにおいて現存する最後のチャンクと同じストライプセットのうちのその現存する最後のチャンクに隣接する１以上のチャンクを割り当て（即ち、チャンクデータベース９０２５に最後に追加されたエントリに関連付けられたチャンク）、且つチャンクデータベース９０２５の中で対応するエントリが更新され、ファイルシステムに割り当てられたディスクスペースにおける効果的な増加が反映される。このように、最後のテーブルエントリに関連付けられた仮想ファイルシステムアドレスの範囲は大きくなり、且つ物理ストレージの複数の隣接するチャンクに対応付けられるが、その際、付加的なテーブルエントリを使用することなく、且つ、そのため、更なる拡大のために利用可能な、それらのテーブルエントリを残すこともない。その結果、ファイルシステムは、一般に拡大され、それによって、テーブルのサイズを拡大することなく、より多数のチャンクを含むことが可能である（例えば、システムにおける１０２３個以上のチャンクは、１０２３個のエントリを有する固定サイズのテーブルを使用する）。
【００５０】
図５は、ストライプセットにおけるチャンクの概略的表現であり、ここでは、既に使用されている幾つかのチャンク、及びファイルシステムに自由に割り当てられる幾つかのチャンクが含まれる。便宜上、「空の」チャンクは、「空１」、「空２」などと呼ばれる。この実施形態において、ストライプセットは、使用中チャンクの、隣接していないランを含む。使用中チャンク１および使用中チャンク２は、同じファイルシステムに割り当てられる。ファイルサーバ９００２が、異なるファイルシステムに割り当てるべき空のチャンクを検索する場合、ファイルサーバ９００２は、所定数の空のチャンクを通り過ぎて検索するが、この所定数の空のチャンクは、本明細書で更に説明されるように、ファイルシステムのためのライブランに続く。従って、ファイルサーバ９００２は空のチャンクを迂回し、それによって、ファイルシステムは、後で、請求されたランにおけるチャンクの中に拡大する。ファイルサーバ９００２は、異なるファイルシステムに対して、請求されたラン、例えばチャンク「使用中３」の後に、チャンクを割り当てる。実証のために、スパンマネージャ９００３が所定のファイルシステムをサイズＸの３つのチャンクだけ拡大する要求が、受信されたとする。スパンマネージャは、利用可能なストレージから３つのチャンクを割り当てる。３つのチャンクは、単一のストライプセットに、又は、２つ又は３つの異なるストライプセットに由来し得るであろう。これに対して、この実証のために、図５からチャンク「空１」、チャンク「空２」及びチャンク「空３」がファイルシステムに対して割り当てられる。
【００５１】
図６は、代表的な先行技術の実施形態における特別な時点で見られるような、テーブル９０２５の概略的表現であり、ここで各新しいチャンクに対する情報は、別個のテーブルエントリに格納される。便宜上且つ簡単のために、テーブルは、チャンクポインタ及びサイズを格納するものとして表現されるが、しかし実際の実施形態においては、テーブルは、論理アドレス及び物理アドレス、並びにファイルシステムに割り当てられるチャンクに関連付けられた装置を、追跡するための付加的な及び／又は代替的な情報を含んでもよい（例えば、チャンクの、又はファイルシステムに割り当てられるチャンクのランの、開始アドレス及び終了アドレスを格納する）。ファイルシステムが最初に作成される場合、テーブル９０２５におけるフィールドは空である。ファイルサーバ９００２がファイルシステムにチャンクを割り当てるにつれて、新しく割り当てられた各チャンクのアドレス及びサイズが、エントリのフィールドに格納される。ファイルサーバ９００２は、３つの新しいチャンクをファイルシステムに割り当てることが可能であり、従って、テーブル９０２５の中で３つのエントリを占有する。第１チャンクに対する情報は、テーブルエントリ９０３０の中に書かれるが、これには、以前は空のフィールド９０４０におけるチャンクの開始に対するポインタ（この例では、チャンク「空１」の開始に対するポインタ）と、フィールド９０５０におけるチャンクサイズＸとが含まれる。第２チャンクに対する情報は、テーブルエントリ９０３１の中に書かれるが、これには、以前は空のフィールド９０４１におけるチャンクの開始に対するポインタ（この例では、チャンク「空２」の開始に対するポインタ）と、フィールド９０５１におけるチャンクサイズＸとが含まれる。且つ、第３チャンクに対する情報は、テーブルエントリ９０３２の中に書かれるが、これには、以前は空のフィールド９０４２におけるチャンクの開始に対するポインタ（この例では、チャンク「空３」の開始に対するポインタ）と、フィールド９０５２におけるチャンクサイズＸとが含まれる。仮想のファイルシステム・アドレス・スペースは３Ｘだけ増加される。代替的実施形態において、割り当てられた各チャンクは、同じサイズを有してもよい。これらの３つの実施形態において、テーブル９０２５は、単一のコラムを含み得るが、そこではコラムにおける各エントリは、チャンクの開始のアドレスを格納する。
【００５２】
図７は、代表的な実施形態における特別な時点で見つけられるような、テーブル９０２５の概略的表現であるが、そこでは隣接するチャンクに対する情報は、図６に示されたテーブル９０２５の代わりに、単一のテーブルエントリに格納されてもよい。具体的には、図５の隣接するチャンク「空１」、チャンク「空２」及びチャンク「空３」がファイルシステムに対して割り当てられる上記の例を用いて、テーブルエントリ９０３０が、３つの隣接するチャンクのランに対する情報を格納するために使用される。ランの開始に対するポインタ（この例では、チャンク「空１」の開始に対するポインタ）が、フィールド９０４０の中に書かれている。ランの終了に対するポインタ（この例では、チャンク「空３」の終了に対するポインタ）が、フィールド９０５０の中に書かれている。このように、スパンマネージャ９００３は、３つの新しいチャンクを割り当て、且つそれらのチャンクをファイルシステムに付加したものの、隣接するチャンクは、ただ１つのテーブルエントリだけを取り、より大きなチャンクサイズの単一チャンクとして（即ち、チャンクは格納されたアドレスをまたぐ）、テーブル９０２５の中に出現させられる。
【００５３】
更なる実証のために、スパンマネージャ９００３がファイルシステムをあと２つのチャンクだけ拡大するための更なる要求が受信され、且つスパンマネージャ９００３は、自身が、同じストライプセットから次の２つの隣接するチャンク（例えば、図５におけるチャンク「空４」及び「空５」）を割り当てることを決定すると仮定する。
【００５４】
図８はテーブル９０２５の概略的表現であり、これは、１つの代表的な実施形態に従って、図７のテーブルエントリ９０３０が、２つの付加的な隣接するチャンクを組み込むために、いかにして修正されるかを示している。具体的には、ランにおける第１チャンクの開始に対するポインタは、フィールド９０４０に留まるが、しかしフィールド９０５０に格納される、ランの終了アドレスは変化され（この例では、チャンク「空５」の終了に対して）、それによって、開始アドレスと終了アドレスとの間のディスクスペースは、付加的な２つの隣接して割り当てられたチャンクを取り囲む。このように、スパンマネージャ９００３は、今は、ストレージから５つの隣接するチャンクを割り当て、且つそれらのチャンクをファイルシステムに付加したものの、隣接するチャンクは、依然としてただ１つのテーブルエントリを取る。
【００５５】
典型的な実施形態において、統合された隣接するチャンクを用いたファイルシステムの拡大は、テーブル９０２５において最後に使用されたテーブルエントリ又は未使用のテーブルエントリのみによってなされ、それによって、仮想的なファイルシステム・アドレス・スペースに対応する拡張は、ファイルシステムの末端部に付加された新しいストレージに対応付けられる。例えば、図４を再び参照すると、もし３つのチャンクがファイルシステムに付加される場合、その時は、ファイルシステム・アドレス・スペースは、Ｎから（Ｎ＋３Ｘ）まで増加するであろう。しかし、ブロック０からブロック（Ｎ−１）に対するストレージに対応する物理アドレスは、変化しないままでなければならず、そうでなければ、特別な仮想的ファイルシステムアドレスは、その場合、無効な物理アドレス位置を示すかもしれない。図９は、サイズＸの３つのチャンクだけ拡大される、図４のファイルシステムスペースの概略的表現である。オリジナルファイルシステムスペース９０６０は、論理アドレス範囲が０から（Ｎ−１）までに留まり、且つ新しく割り当てられたファイルシステムスペース９０７０は、Ｎから（Ｎ＋３Ｘ−１）までの論理アドレス範囲にある。
【００５６】
図１０は、１つの代表的な実施形態に従う、包括的なチャンク割り当てプロセスに対するフローチャートである。具体的には、図１０は、ファイルサーバによってファイルシステムのためのストレージを拡大するための、包括的なチャンク割り当てプロセスを説明し、そこではファイルシステムは、複数のストライプセットから選択された複数のチャンクを含み、且つファイルサーバは、ファイルシステムの仮想アドレススペースを、チャンクに関連付けられた物理記憶アドレスに対応付ける。ブロック１００２に始まり、ファイルサーバは、ファイルシステムに関連付けられたチャンクを追跡するために、チャンクデータベースを維持し、該チャンクデータベースは、固定数のエントリを含み、各エントリは、ファイルシステムに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である。ブロック１００４では、ファイルサーバは、ファイルシステムを拡大する要求を受信する。ブロック１００６では、ファイルサーバは、チャンクデータベースに基づいて、ファイルシステムに関連付けられた最後のチャンクを識別する。ブロック１００８では、ファイルサーバは、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクが、ファイルシステムへの割り当てのために利用可能であるかを判断する。本明細書で議論される代表的な実施形態の文脈において、最後のチャンクと同じストライプセット及び最後のチャンクに隣接するストライプセットから、少なくとも１つのチャンクが、ファイルシステムへの割り当てに対して「利用可能」であるかどうかの判断には、単にチャンク（複数チャンクを含む）が空であるかどうかだけでなく、以下で説明されるように、ランバイアス及び他のファクタのような、他のファクタもまた考慮に入れてもよい。ブロック１０１０では、少なくとも１つのチャンクが利用可能であると判断される場合、ファイルサーバは、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接する少なくとも１つのチャンクを割り当てる。ブロック１０１２では、少なくとも１つの割り当てられたチャンクによって表される連続したストレージの長さにおける増加を反映させるために、ファイルサーバは、ファイルシステムの最後のチャンクに関連付けられたテーブルにおけるエントリを更新する。
【００５７】
ある代表的な実施形態において、（以下でより十分に議論される）様々な制限が、隣接したチャンクの数に課せられるが、これらの隣接したチャンクは、ストライプセットから割り当てられ、且つ単一のテーブルエントリに関連付けられ得る。それによって、ある状況では、もし付加的な隣接するチャンクが、特別なストライプセットから割り当てられ、且つ単一のテーブルエントリに関連付けられるとしても、少なくとも幾つかのチャンクは、複数のストライプセットにわたってストレージ（且つ、この故に、記憶アクセス）を分布させるために、異なるストライプセットから割り当てられる。例えば、特別なファイルシステムにおける最後のチャンクが、特別なストライプセット（これは、本明細書では、「アクティブラン長」と呼ばれてもよい）からのＡ個の隣接したチャンクのランの一部であるとする。ここでＡは、１よりも大きいか、又は１に等しいが、しかし所定のランバイアス未満である。また、ファイルシステムをＢ個のチャンクだけ拡大する要求が受信されるとする。ここで（Ａ＋Ｂ）は、所定のランバイアスよりも大きい。もしＢ個のチャンクが、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接するチャンクで利用可能であるとしても、チャンク割り当て部９０１４は、一般に、ストライプセットからＮ個のチャンクだけを割り当てるであろう。ここでＮは、アクティブラン長を引いたランバイアスに等しい。チャンク割り当て部９０１４は、所定の選択案に従って選択されるような、１以上の他のストライプセットから、残りのチャンクを割り当てるであろう。このことは、以下でより十分に議論される。しかしながら、幾つかの実施形態において、もしストライプセットがスパンに最近付加されており、且つ、他のストライプセットよりも比較的空いている場合、チャンク割り当て部９０１４は、ランバイアスの長さに拘わらず、より空いたストライプセット上に長いランを割り当ててもよい。
【００５８】
幾つかの代表的な実施形態において、１以上のチャンクが、最後のチャンクと同じストライプセットのうちのその最後のチャンクに隣接するチャンクとして割り当てられ得るかどうかを、チャンク割り当て部９０１４は実時間で判断してもよい。これに対して、ある代表的な実施形態において、チャンク割り当て部９０１４は、以下でより十分に議論されるある環境の下で、ストライプセットから１以上の隣接するチャンクを、少なくとも一時的に予約してもよい。この理由は、そのようなチャンクが、将来の時点において、ファイルシステムに割り当てられ得るようにするためである。具体的には、そのような環境下では、チャンク割り当て部９０１４が、ファイルシステムに割り当てるべきストライプセットから、１以上の隣接したチャンクを割り当てる場合、付加的な隣接するチャンクが、将来、ファイルシステムに割り当てられるかもしれない可能性があり、チャンク割り当て部９０１４は、割り当てられたチャンクに隣接するそのストライプセットの中で１以上のチャンクを予約してもよく、それによって、そのような予約されたチャンクは、仮に及び実際にファイルシステムが将来拡大される場合、ファイルシステムに割り当てるのに利用可能である。概して言えば、チャンク割り当て部９０１４は、予約されたチャンクが所定のランバイアスを超えずに割り当てられ得る程度に、チャンクを予約するだけであろう。即ち、もしストライプセットからファイルシステムに割り当てられてきた隣接するチャンクの数（これは、本明細書で、「アクティブラン長」と呼ばれてもよい）が、所定のランバイアスに既に到達している場合、その時は、チャンク割り当て部９０１４は、通常、いかなるチャンクも予約しない。そうでない場合、チャンク割り当て部９０１４は、Ｎ個までのチャンクを予約する。ここでＮは、アクティブラン長を引いた所定のランバイアスに等しい。チャンク割り当て部９０１４は、他のファイルシステムに対してチャンクを割り当てる場合、予約されたチャンクを回避するが、それは、少なくとも、予約されたチャンクが利用可能なチャンクの「プール」に戻されるまでのことである（例えば、仮に予約されたチャンクが、割り当てられるのに利用可能である唯一のチャンクになる場合）。注意されるべきことであるが、チャンク割り当て部９０１４は、多数の異なるファイルシステムの各々に対して、予約されたチャンクとは別個のグループ分けを維持してもよい。
【００５９】
従って、ファイルシステムのストレージが拡大するにつれて、ファイルサーバ９００２は、ファイルシステムのために予約されたランからチャンクを割り当ててもよい。複数のチャンクを有するランは、チャンクデータベースの中で単一のエントリを占有し得るので、ファイルシステムは、それによって、チャンクデータベースが別なやり方で許容するよりも、多くのチャンクを含んでもよい。従って、このシステムでは、ストレージは効率的に使用されるかもしれず、ファイルシステムはより小さな増加分でストレージを付加するかもしれず、ファイルシステムは拡張可能かもしれず、且つアドレス移行は迅速に実行されるかもしれない。
【００６０】
加えて、ファイルサーバ９００２は、ファイルシステムの累積負荷と各ファイルシステムの個々の負荷の両方を、ストライプセットにわたって分布させることに努めるかもしれない。ファイルシステムがディスクスペース拡大を要求する場合、ディスクスペースの次の割り当てに対して、どのストライプセットを選択するかを判断するために、ファイルサーバ９００２は、多数のファクタを考慮する。
【００６１】
ストライプセットを評価するための代表的なファクタは、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数と、ファイルシステムによって既に使用されているストライプセット上のチャンクの数とを含む。
【００６２】
幾つかの実施形態において、代表的なファクタは、ストライプセットにわたってファイルシステムの負荷を均衡させるよりも、ストライプセットにわたって全体的な負荷を均衡させることを優先的に履行する、又はその逆を優先的に履行する。スパン上のファイルシステムのほとんど又は全てが稼働中であると予想される場合、ストライプセットにわたって全体的な負荷を均衡させることは、より重要な優先事項であるかもしれない。
【００６３】
ファイルシステムの小さな部分が稼働中であると予想される場合、任意のある時間で、又はピーク時の間、ストライプセットにわたって各ファイルシステムの負荷を均衡させることは、優先事項となるかもしれない。これらの目標の相対的重要性は、パラメータに加えられる加重において履行され得るが、該パラメータはストライプセットを判断するためのものであり、このストライプセットから、ディスクスペースが次に割り当てられることになる。加重は、スパン加重及びファイルシステム加重であるかもしれない。より大きなスパン加重は、ストライプセットにわたってスパンの全体的な負荷を均衡させることを優先させ、且つスパン加重は、ストライプセットにわたるチャンク割り当ての不均衡の尺度に対して適用される（例えば、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数）。より大きなファイルシステム加重は、ストライプセットにわたってアクティブなファイルシステムの負荷を均衡させることを優先させ、且つファイルシステム加重は、ストライプセットにわたる、特別なファイルシステムに対するチャンク割り当ての不均衡の尺度に適用される。
【００６４】
幾つかの実施形態において、ファイルサーバ９００２は、スパン加重及びファイルシステム加重に対して異なる値を格納する単一のチャンク割り当て部９０１４を有する。様々な実施形態において、ファイルサーバ９００２は、スパン加重及びファイルシステム加重に対して異なる値を有するかもしれない、異なるチャンク割り当て部９０１４を有し、且つファイルサーバ９００２は、要求を作成するクライアント、拡大されているファイルシステム、又は任意の他の変数に基づいて、ディスクスペース拡大に対する要求を処理するための、チャンク割り当て部９０１４を選択してもよい。本明細書で議論される少なくとも１つのファクタに基づいて、ファイルサーバ９００２上のチャンク割り当て部９０１４は、ファイルシステムに割り当てられる最後のチャンクを含むストライプセット、又は新しいストライプセットのいずれかを選択する。
【００６５】
チャンク割り当て部９０１４が、ファイルシステムの最後に割り当てられたチャンクを有するストライプセットを選択する場合、チャンク割り当て部９０１４は、可能ならば、最後のチャンクに直ちに続くチャンクを割り当てる。チャンク割り当て部９０１４が新しいストライプセットを選択する場合、チャンク割り当て部９０１４は、チャンクを割り当て、且つまた、ファイルシステムからの将来の要求のために、その後の連続する多数のチャンクを予約する（例えば、請求されたラン）。従って、ファイルシステムが付加的なディスクスペースを要求する場合、チャンク割り当て部９０１４は、そのために既に取っておかれたディスクスペースからチャンクを割り当てることが可能である。更に、チャンク割り当て部９０１４が、新しいストライプセット上でディスクスペースを検索する場合、チャンク割り当て部９０１４は、他のファイルシステムのために既に予約されている利用可能なチャンクを迂回してもよい。
【００６６】
予約するべき連続したチャンクの数に関して、ファイルサーバ９００２は、スパンに対するランバイアスを判断してもよい。ファイルサーバ９００２は、ランバイアスに対応する多数のチャンクを割り当てるであろうが、幾つかの環境では、ファイルサーバ９００２は、以下でより詳細に議論されるように、異なる数を割り当ててもよい。
【００６７】
特定の代表的な実施形態の詳細が、ここで説明される。これらの特定の代表的な実施形態において、ファイルサーバ９００２は情報を受信するが、この情報は、ストライプセットにわたって個々のファイルシステムの負荷を分布させることに比較して、ストライプセットにわたってスパンの全体的な付加を分布させることが相対的に重要であることに関する。幾つかの実施形態において、ファイルサーバ９００２は、スパン加重及びファイルシステム加重に対する初期設定値を格納する。幾つかの実施形態において、ファイルサーバ９００２の管理者は、スパン加重及びファイルシステム加重をファイルサーバ９００２に入力できる。幾つかの実施形態において、管理者は、スパンにおける各ファイルシステムに対して、個々のファイルシステム加重及び／又は別個のファイルシステム加重を入力する。幾つかの実施形態において、ファイルサーバシステムに申し込むにあたり、又は新しいファイルシステムを要求するにあたり、クライアントは、ストレージに対するスパン加重及び／又はファイルシステム加重を、ファイルサーバ９００２によって入力してもよい。ファイルサーバ９００２は、チャンク割り当て部９０１４に加重を格納してもよい。幾つかの実施形態において、ファイルサーバ９００２は、スパン・ディスク上構成（例えば、Ｃｏｄ）に加重を格納する。
【００６８】
様々な実施形態において、加重の値は、ゼロ（０）と１０の間の範囲にわたることが可能である。スパン加重及び／又はファイルシステム加重の初期設定値は、１０であってもよい。幾つかの履行例において、もしクライアントが、負荷分布に対する優先事項に関する情報を提供しない場合、ファイルサーバ９００２は、スパン加重及びファイルシステム加重を同じ値に設定する。この値は、１０、５、又は当業者の一人によって望まれる他の任意の値であってもよい。
【００６９】
ファイルサーバ９００２は、スパンに対するランバイアスを判断する。幾つかの実施形態において、ファイルサーバ９００２は、クライアントのスパン及び／又はファイルシステムに対して、クライアントによって入力されたランバイアスを使用する。幾つかの実施形態において、ファイルサーバ９００２は、メモリに格納された初期設定値を使用する。初期設定ランバイアスは、６４個のチャンクであってもよいが、しかし、他の初期設定値が使用されてもよい。
【００７０】
幾つかの実施形態において、サーバ９００２は、ファイルシステムの数及びスパン上のストライプセットの数に基づいて、ランバイアスを判断する。例えば、スパンが、少しのチャンクしか有さず、且つ多くのストライプセットを有する場合、より小さなランバイアスは、ストライプセットにわたる負荷均衡を改善するかもしれない。ファイルサーバ９００２は、スパンのパラメータに従って、ランバイアスを減少させる。
【００７１】
幾つかの実施形態において、ファイルサーバ９００２は、ストライプセットの数を２で割ってもよい。ファイルサーバ９００２は、結果としての値を、ファイルシステムの数で割ってもよい。ファイルサーバ９００２は、結果としての値を、メモリに格納された初期設定ランバイアスと比較し、且つランバイアスをより小さな値に設定してもよい。幾つかの実施形態において、スパンに対するランバイアスは、０個のチャンクと２５０個のチャンクとの間であり得るが、しかし、ランバイアスの潜在的な値に対する他の範囲が使用されてもよい。
【００７２】
動作において、クライアント装置９００６でのユーザーは、ファイルサーバ９００２に、ファイルシステムのためにディスクスペースを拡大する要求を送信する。幾つかの実施形態において、要求は、ファイルシステムに付加するべきディスクスペースの総計を含む。ファイルサーバ９００２は、ディスクスペースの総計に対応するチャンクの数を判断するが、この判断は、例えば、要求されたディスクスペースの総計を、チャンクの指針サイズで割ることによる。
【００７３】
ファイルシステムを拡大する要求が受信される場合、チャンク割り当て部９０１４は、ファイルシステムへのチャンクの割り当てに対して、１以上のストライプセットを選択する。上で説明されたように、チャンク割り当て部９０１４は、ファイルシステムのために、ストライプセット上のランを予約してもよい。この理由のために、チャンク割り当て部９０１４が、ファイルシステムへの次の割り当てに対してストライプセットを判断する場合、チャンク割り当て部９０１４は、ファイルシステムの最も間近に割り当てられたチャンクを含むストライプセット（本明細書で、「現在のストライプセット」とも呼ばれる）に対してバイアスを有してもよい。幾つかの状況において、チャンク割り当て部９０１４は、それでも、割り当てに対して新しいストライプセットを選択する。チャンク割り当て部９０１４は、スパンの全体的な負荷を均衡させるために、又はストライプセットにわたるファイルシステム負荷を均衡させるために、若しくは他の任意の理由のために、別のストライプセットに変更してもよい。
【００７４】
幾つかの実施形態において、チャンク割り当て部９０１４は、ストライプセットを選択するが、その選択は、少なくとも、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数、拡大されているファイルシステムに割り当てられてきたストライプセット上で使用されたチャンクの数、スパン加重、及びファイルシステム加重に基づく。もしチャンク割り当て部９０１４が、現在のストライプセット上に留まることが有利かもしれないことを判断する場合、ストライプセットを選択する際に、チャンク割り当て部９０１４は、現在のストライプセット上で利用可能なチャンクの数に、バイアスファクタを付加することによって、その選択にバイアスを与える。
【００７５】
幾つかの実施形態において、チャンク割り当て部９０１４は、現在のストライプセットに対して、ストライプセットの選択にバイアスを与えるか否かを判断するために、様々な基準を使用してもよい。例えば、チャンク割り当て部９０１４は、その選択にバイアスを与えてもよいが、それは、仮にファイルシステムが既に少なくとも１つの割り当てられたチャンクを有しており、これによって、現在のストライプセットを有する場合だけである。この場合には、ファイルシステムの最後に割り当てられたチャンクの後のチャンクは利用可能であり、その結果、割り当て部は、次のチャンクを用いること、及び新しいランを開始する必要性を回避することに対して、常にバイアスが与えられる。ファイルシステムが最初に作成される場合、ファイルシステムは、ストライプセットにわたって分布させるべき負荷を未だ持たないので、チャンク割り当て部９０１４は、スパンの全体的な負荷を分布させることに主に関係してもよい。別の例では、もしファイルシステムの最後に割り当てられたチャンクに直ちに続くチャンクが利用可能である場合、チャンク割り当て部９０１４は、選択にバイアスを与える。もしこのチャンクが利用可能でない場合、その時は、ファイルシステムは、おそらく、自身のために予約されたチャンクのラン全体に拡大したであろう。次の割り当ては、テーブルの中で新しいエントリを要求するので、現在のストライプセット上に留まることは、必ずしも有利ではない。幾つかの実施形態において、ファイルサーバ９００２は、選択にバイアスを与える前に、１以上のこれらの条件を要求してもよい。
【００７６】
バイアスファクタは、多数の方法の中の任意の方法で判断されてもよい。幾つかの実施形態において、チャンク割り当て部９０１４は、拡大されているファイルシステムに割り当てるべきチャンクの数を判断する。例えば、チャンク割り当て部９０１４は、ファイルシステムによって要求された割り当てのサイズを、チャンクの指針サイズで割ってもよい。チャンク割り当て部９０１４は、現在のストライプセット上に割り当てられるかもしれないチャンクの数を判断してもよい。例えば、チャンク割り当て部９０１４は、拡大におけるチャンクの数を、割り当てられ得るディスクスペースを依然として有するストライプセットの数で割ってもよい。
【００７７】
チャンク割り当て部９０１４はバイアスファクタを計算してもよいが、このバイアスファクタは、ディスク上に大きなランを隣接して配置する望ましさ、及び、スパンが多くのファイルシステムを有する場合に、ばらばらになるランを回避する望ましさを説明する。前者を説明するために、チャンク割り当て部９０１４は、現在のストライプセット上に割り当てられてもよいチャンクの数と比較して（本明細書で「隣接ファクタ」とも呼ばれる）、ランバイアスをより大きく決定してもよい。後者を説明するために、ファイルサーバ９００２は、ファイルシステムの数を、ストライプセットの数で割ってもよい。もしこの商が１よりも大きい場合、バイアスファクタは、この商に隣接ファクタを掛けたものかもしれない。そうでない場合、バイアスファクタは、隣接ファクタに等しいかもしれない。
【００７８】
ストライプセットを選択するために、チャンク割り当て部９０１４は、各ストライプセットを採点し、且つ最も高いスコアを有するストライプセットを選択する。スコアは、スパン・サブスコア及びファイルシステム・サブスコアを含んでもよい。幾つかの実施形態において、スコアは、スパン・サブスコアとファイルシステム・サブスコアとの合計であってもよい。
【００７９】
スパン・サブスコアに対しては、チャンク割り当て部９０１４は、ストライプセットを、最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数を、第一に判断してもよい。幾つかの実施形態において、スパン・サブスコアは、スパン加重とチャンクの数との積であってもよく、ここでのチャンクは、ストライプセットを、最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなものである。従って、ストライプセットのスコアの一部は、スパンの負荷を仮定するための、他のストライプセットに対する、ストライプセットの入手可能性を説明する。ファイルシステム・サブスコアに対しては、チャンク割り当て部９０１４は、既にファイルシステムに割り当てられたストライプセット上のチャンクの数を判断してもよい。ファイルシステム・サブスコアは、ファイルシステム加重と、チャンクのこの数との積であってもよい。従って、ストライプセットのスコアの一部は、ストライプセットを、最も一杯なストライプセットと同じくらい一杯にするために、ストライプセットに割り当てられる必要がありそうなチャンクの数を説明してもよい。
【００８０】
幾つかの実施形態において、ファイルサーバ９００２が、現在のストライプセットに対する選択にバイアスを与えていない場合、チャンク割り当て部９０１４は、他のファイルシステムのために既に予約されているチャンクを説明してもよいが、それは、チャンク割り当て部９０１４が、ストライプセット上で利用可能なチャンクの数を判断する場合である。例えば、もし他のファイルシステムの任意のものが、ストライプセット上でライブランを有する場合、チャンク割り当て部９０１４は、ランバイアスに等しいラン長に対して、ライブランに追加される必要がありそうなチャンクの数を判断してもよい。チャンク割り当て部９０１４は、ストライプセット上で利用可能なチャンクの全数から、この数を差し引いてもよい。最終的な数は、ストライプセットのスパン・サブスコアを判断するために、スパン加重が掛けられてもよい。チャンク割り当て部９０１４は、その後、ストライプセットのファイルシステム・スコア及び合計スコアを判断する。チャンク割り当て部９０１４は、最も高いスコアを有するストライプセットを選択する。
【００８１】
幾つかの実施形態において、ファイルサーバ９００２が現在のストライプセットに対する選択にバイアスを与えている場合、ストライプセット上の可能なチャンクの数は、割り当てられていないチャンクの総数であってもよい。更に、チャンク割り当て部９０１４は、現在のストライプセット上の利用可能なチャンクの数に、バイアスファクタを付加してもよい。もし現在のストライプセットが最も高いスコアを有するか、又は最も高いスコアと同点である場合、チャンク割り当て部９０１４は、現在のストライプセットを選択する。そうでない場合、チャンク割り当て部９０１４は、あたかも自身が選択にバイアスを与えていないかのようにスコアを再計算し、且つ最も高いスコアを有するストライプセットを選択する。
【００８２】
幾つかの実施形態において、チャンク割り当て部９０１４が、新しいファイルシステムに対して第１チャンクを選択する場合、チャンク割り当て部９０１４は、１以上のＳＤ上で提供されるストライプセットを選択する。多くの実施形態において、ファイルシステムの第１チャンクは、ファイルシステムの構造に関する情報を含む（例えば、メガデータ）。１以上のＳＤ上で提供されるストライプセットを選択することによって、チャンク割り当て部９０１４は、そのような重要な情報を冗長的に格納し、もし別のコピーが失敗しても、少なくとも１つのコピーがアクセス可能であることを保証する。幾つかの実施形態において、チャンク割り当て部９０１４は、ストライプセットを選択する場合、単一のＳＤ上の全てのストライプセットを排除する。幾つかの実施形態において、もし複数ＳＤのストライプセットのどれもが空のチャンクを持たない場合、チャンク割り当て部９０１４は、単一ＳＤのストライプセットを考慮することに戻る。
【００８３】
チャンク割り当て部９０１４は、ファイルシステムに割り当てるべき選択されたストライプセット上で、１以上のチャンクを選択する。もしチャンク割り当て部９０１４が現在のストライプセットを選択する場合、チャンク割り当て部９０１４は、ファイルシステムの最後に割り当てられたチャンクに直ちに続くチャンクが利用可能であるかを判断してもよい。もしそうであれば、チャンク割り当て部９０１４は、そのチャンクをファイルシステムに割り当てる。
【００８４】
チャンク割り当て部９０１４が新しいストライプセットを選択する場合、チャンク割り当て部９０１４は、予約されていないチャンクのランを検索し、且つその中の第１チャンクをファイルシステムに割り当てる。チャンク割り当て部９０１４は、自身の長さが少なくともランバイアスである、予約されていないチャンクのランを検索してもよい。もしチャンク割り当て部９０１４がそのようなランを見つける場合、ファイルサーバ９００２は、そのランの中の第１チャンクをファイルシステムに割り当ててもよい。チャンク割り当て部９０１４は、ストライプセット上の予約されていないチャンクの最も長いランを検索し、且つこのランの中の第１チャンクをファイルシステムに割り当ててもよい。
【００８５】
幾つかの状況において、チャンク割り当て部９０１４は、ランバイアスのような、望ましい長さを有する予約されていないチャンクのランを見つけられないかもしれない。これらの状況では、チャンク割り当て部９０１４は、請求されたランを検索してもよい（例えば、他のファイルシステムのために予約され、割り当てられていないラン）。幾つかの実施形態において、チャンク割り当て部９０１４は、自身の長さがランバイアスに等しい、請求されていないランを検索してもよい。チャンク割り当て部９０１４は、請求されたランの後半における第１チャンクを、ファイルシステムに割り当ててもよい。幾つかの実施形態において、もしファイルシステムが、請求されたランにおける半分以上のチャンクを要求するディスクスペースの拡大を要求した場合、チャンク割り当て部９０１４は、請求されたランの前半の中でチャンクを識別し、それによって、要求されたチャンクの割り当ては、請求されたランの後半部分を満たすであろう。このように、利用可能なディスクスペースが少なくなる場合でさえも、ファイルサーバ９００２は、ファイルシステムに対して、何らかの拡張可能性を保持するかもしれない。もしチャンク割り当て部９０１４が、ランバイアスに等しい長さを有する請求されたランを見つけられない場合、チャンク割り当て部９０１４は、ストライプセット上の最も長い請求されたランを検索し、且つその第１チャンクをファイルシステムに割り当ててもよい。
【００８６】
幾つかの実施形態において、もしチャンク割り当て部９０１４が、割り当てるべきチャンクを見つけられない場合、割り当ては失敗するかもしれない。ファイルサーバ９００２は、エラーメッセージをクライアント９００６に戻してもよい。
【００８７】
幾つかの実施形態において、ランバイアスに等しい長さを有するランを検索する代わりに、チャンク割り当て部９０１４は、ストライプセット上に割り当てられると予想されるファイルシステムに対して、チャンクの数に等しいランを検索してもよい。上で説明されたように、この数は、一杯でないストライプセットの数で割った、ファイルシステムに割り当てられるべきチャンクの総数であってもよい。幾つかの実施形態において、チャンク割り当て部９０１４は、この長さに従って検索するが、それは、長さが、スパンに対するランバイアスを超える場合である。
【００８８】
幾つかの状況において、ファイルシステムのためにディスクスペースを拡大する要求は、ストライプセットの指示を含むが、この指示から、ディスクスペースが割り当てられるべきである。もしストライプセットが、ファイルシステムの現在のストライプセットでない場合、チャンク割り当て部９０１４は、本明細書で説明される方法のいずれかに従って、チャンクを検索してもよい。
【００８９】
もしストライプセットが、ファイルシステムの現在のストライプセットである場合、チャンク割り当て部９０１４は、ライブランの直ぐ後にチャンクを割り当ててもよい。もし拡大が１以上のチャンクを要求する場合、チャンク割り当て部９０１４は、ランの長さがランバイアスに等しくなるまで、チャンク割り当てを継続してもよい。幾つかの実施形態において、もしライブランの後のチャンクが利用可能である場合、チャンク割り当て部９０１４は、ランバイアスを超えてランを拡大してもよい。幾つかの実施形態において、拡大における残りのチャンクに対しては、チャンク割り当て部９０１４は、本明細書で説明される他の方法のいずれかに従って、ディスクスペースを検索してもよい。
【００９０】
幾つかの状況において、ユーザーからの要求は、ディスクスペースの大きな拡大に対する要求を含む。スパンにわたって新しい負荷を分布させるために、チャンク割り当て部９０１４は、利用可能なチャンクを有する各ストライプセットからファイルシステムに、チャンクを割り当ててもよい。幾つかの実施形態において、チャンク割り当て部９０１４は、要求におけるチャンクの数を、一杯でないストライプセットの数で割ってもよい。チャンク割り当て部９０１４は、自身の長さがその商に等しい、請求されていないランに対して、各ストライプセットを検索してもよく、且つ各ランは、ファイルシステムのテーブルの中で単一のエントリを占有してもよい。幾つかの状況において、チャンク割り当て部９０１４は、自身の長さがランバイアスよりも長いランを、各ストライプセット上に割り当ててもよい。幾つかの実施形態において、もし商がランバイアスよりも小さい場合、チャンク割り当て部９０１４は、本明細書で説明される方法のいずれかに従って、ストライプセットを選択し、且つランバイアスに等しいチャンクのランを割り当ててもよい。チャンク割り当て部９０１４は、要求における全てのディスクスペースがファイルシステムに割り当てられてしまうまで、ストライプセットを選択し、且つランバイアスのチャンクを割り当てることを継続してもよい。
【００９１】
さて図１１を参照すると、ファイルシステムに割り当てるべき、ストライプセット及びストライプセット上のチャンクを選択する方法の代表的な流れ図が示され、且つ説明される。本方法は、スパンに対してランバイアスを判断するステップを含み、そこではランバイアスは、ファイルシステムのためのアドレス移行テーブルにおけるエントリに関連付けられたディスクスペースの隣接するチャンクの数を示す（ステップ５００５）。チャンク割り当て部が、ファイルシステムに、ランバイアスに等しいストライプセット上のディスクスペースの、隣接する多数のチャンクを割り当てる場合、チャンク割り当て部は、ディスクスペース拡大を提供するために、新しいストライプセットを判断することが可能である。幾つかの実施形態において、ファイルサーバは、メモリに格納された初期設定ランバイアスを引き出すことが可能である。幾つかの実施形態において、ファイルサーバは、ストライプセットの数及びファイルシステムの数に基づいて、潜在的なランバイアスを判断する。例えば、ファイルシステムは、ストライプセットの数を２で割り、且つその結果としての値を、ファイルシステムの数で割ることが可能である。もしその結果が初期設定ランバイアスよりも小さい場合、その結果はランバイアスとなり得る。
【００９２】
本方法は、ファイルシステムのために、ディスクスペースを拡大する要求を受信するステップを含む（ステップ５０１０）。幾つかの実施形態において、ファイルサーバは、ディスクスペースの拡大を要求するファイルシステムに基づいて、スパン加重及びファイルシステム加重を引き出す。幾つかの実施形態において、ファイルサーバの単一のチャンク割り当て部は、スパン加重及びファイルシステム加重を引き出す。他の実施形態において、ファイルサーバは、ファイルシステムに基づいて、複数のチャンク割り当て部から、１つのチャンク割り当て部を選択する。これらの実施形態において、各チャンク割り当て部は、スパン加重とファイルシステム加重の唯一のペアを格納する。
【００９３】
本方法は、ストライプセット上の未使用のチャンクの数、及びファイルシステムによって使用されているストライプセット上のチャンクの数に少なくとも部分的に基づいて、１つのグループのストライプセット中の各ストライプセットを採点するステップを含む（ステップ５０１５）。各ストライプセットに対して、チャンク割り当て部は、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数を、スパン加重に掛けることが可能である。各ストライプセットに対して、チャンク割り当て部はまた、ファイルシステムによって使用されているストライプセット上のチャンクの数を、ファイルシステム加重に掛けることが可能である。チャンク割り当て部は、これら２つの積の和に等しいストライプセットに対して、スコアを設定することが可能である。幾つかの実施形態において、現在のストライプセットに対してスコアを判断する場合、チャンク割り当て部は、バイアスファクタを含むことが可能である。幾つかの実施形態において、ストライプセット上の未使用のチャンクの数は、他のファイルシステムのために予約されるディスクスペースの、割り当てられていないチャンクを説明することが可能である。
【００９４】
本方法は、最も高いスコアを有するストライプセット上のチャンクを割り当てるステップを含み、そこでは、割り当てられたチャンクは、他のファイルシステムのために予約されたランの外側にある（ステップ５０２０）。もしファイルシステムの現在のストライプセットが最も高いスコアを有する場合、チャンク割り当て部は、ファイルシステムの最後に割り当てられたチャンクの後に続くチャンクを割り当てることが可能である。幾つかの実施形態において、チャンク割り当て部は、予約されていないチャンクのランを検索し、且つそのランにおける第１チャンクをファイルシステムに割り当ててもよい。チャンク割り当て部は、自身の長さが少なくともランバイアスである、予約されていないチャンクのランを検索し、且つそのランにおける第１チャンクをファイルシステムに割り当ててもよい。チャンク割り当て部は、ストライプセット上の予約されていないチャンクの、最も長いランを検索し、且つこのランにおける第１チャンクを、ファイルシステムに割り当ててもよい。
【００９５】
幾つかの実施形態において、チャンク割り当て部は、自身の長さがランバイアスに等しい、請求されたランを検索することが可能である。チャンク割り当て部は、請求されたランの後半における第１チャンクをファイルシステムに割り当てるか、又は、本明細書で説明される他の方法によって説明される請求されたランにおける他の任意のチャンクを、ファイルシステムに割り当ててもよい。幾つかの実施形態において、チャンク割り当て部は、ストライプセット上の最も長い請求されたランを検索し、且つその第１チャンクをファイルシステムに割り当てることが可能である。
【００９６】
さて図１２を参照すると、ストライプセットを選択する方法の代表的な流れ図が示され、且つ説明される。ここで、該ストライプセットからチャンクが割り当てられることになるが、それは、現在のストライプセットが、ファイルシステムのための拡大可能なライブランを含む場合である。本方法は、ストライプセット上で、ファイルシステムの最後に割り当てられたチャンクの後のチャンクが利用可能であることを判断するステップを含む（ステップ６００５）。チャンク割り当て部は、ファイルシステムの最後に割り当てられたチャンクの位置を突き止め、且つ後に続くチャンクが利用可能かどうかを判断することが可能である。幾つかの実施形態において、チャンク割り当て部は、ファイルシステムのライブランの長さがランバイアスに等しくないことを判断することが可能である。
【００９７】
本方法は、ファイルシステムの最後に割り当てられたチャンクを有するストライプセットに対して、バイアスファクタを判断するステップを含む（ステップ６０１０）。幾つかの実施形態において、チャンク割り当て部は、第一に、拡大されているファイルシステムに割り当てるべきチャンクの数を判断するが、この判断は、例えば、ファイルシステムによって要求された割り当てのサイズを、チャンクの指針サイズで割ることによる。チャンク割り当て部は、現在のストライプセット上に割り当てられてもよいチャンクの数を判断できるが、この判断は、例えば、拡大におけるチャンクの数を、割り当てられ得るディスクスペースを依然として有するストライプセットの数で割ることによる。
【００９８】
バイアスファクタは、ディスクスペースに大きなランを隣接して配置する望ましさ、及び、スパンが多くのファイルシステムを有する場合に、ばらばらになるランを回避する望ましさを説明することが可能である。前者を説明するために、チャンク割り当て部は、現在のストライプセット上に割り当てられてもよいチャンクの数と比較して（本明細書では隣接ファクタとも呼ばれる）、ランバイアスをより大きく決定することが可能である。後者を説明するために、ファイルサーバは、ファイルシステムの数をストライプセットの数で割ることが可能である。もしこの商が１よりも大きい場合、バイアスファクタは、この商に隣接ファクタを掛けたものであり得る。
【００９９】
そうでない場合、バイアスファクタは隣接ファクタに等しいことが可能である。
【０１００】
本方法は、ファイルシステムの最後に割り当てられたチャンクを有するストライプセットを採点するステップを含み、この採点は、バイアスファクタ、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数、及び／又は、ファイルシステムによって使用されているストライプセット上のチャンクの数、に少なくとも部分的に基づく（ステップ６０１５）。チャンク割り当て部は、バイアスファクタを、ストライプセット上の利用可能なチャンクの数に付加することが可能である。チャンク割り当て部は、この数にスパン加重を掛け、且つファイルシステムによって使用されているストライプセット上のチャンクの数に、ファイルシステム加重を掛けることが可能である。これらの２つの積の和は、現在のストライプセットのスコアであり得る。
【０１０１】
本方法は、他のストライプセットの各々を採点するステップを含むことが可能であり、この採点は、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数、及び／又は、ファイルシステムによって使用されているストライプセット上のチャンクの数、に少なくとも部分的に基づく（ステップ６０２０）。各ストライプセットに対して、チャンク割り当て部は、スパン加重に、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数を掛け、且つファイルシステム加重に、ファイルシステムによって使用されているストライプセット上のチャンクの数を掛けることが可能である。これらの２つの積の和は、ストライプセットのスコアであり得る。
【０１０２】
本方法は、最も高いスコアを有するストライプセットを選択するステップを含むことが可能である（ステップ６０２５）。もし現在のストライプセットが最も高いスコアを有するか、又は最も高いスコアと同点である場合、ファイルサーバは、現在のストライプセットを選択する。そうでない場合、本明細書で説明されるように、ファイルサーバは、あたかも現在のストライプセットに対して、自身がその選択にバイアスを与えていないかのようにスコアを再計算し、且つ最も高いスコアを有するストライプセットを選択する。
【０１０３】
さて図１３を参照すると、ストライプセットを選択する方法の代表的な流れ図が示され、且つ説明されるが、これは、現在のストライプセットが、ファイルシステムのための拡大可能なライブランを含まない場合である。本方法は、ストライプセット上でファイルシステムの最後に割り当てられたチャンクが別のファイルシステムによって使用されている後に、チャンクが異なるストライプセット上に位置するか、又は存在しないことを判断するステップを含む（ステップ７００５）。チャンク割り当て部は、ファイルシステムの最後に割り当てられたチャンクの位置を突き止め、且つ後に続くチャンクが利用可能であるかどうかを判断する。幾つかの実施形態において、チャンク割り当て部は、このチャンクが既に他のファイルシステムに割り当てられたことを判断することが可能である。幾つかの実施形態において、チャンク割り当て部は、次のチャンクが存在しないという具合に、ファイルシステムの最後に割り当てられたチャンクがストライプセット上の最後のチャンクであることを判断することが可能である。幾つかの実施形態において、チャンク割り当て部は、次のチャンクが異なるストライプセット上にあることを判断することが可能である。
【０１０４】
本方法は、１つのグループのストライプセット中の各ストライプセットを採点するステップを含み、この採点は、ストライプセットを最も一杯なストライプセットと比例的に同程度に一杯にするために、ストライプセット上に割り当てられる必要がありそうなチャンクの数と、他のファイルシステムのために予約されたチャンクの数と、ファイルシステムによって使用されているストライプセット上のチャンクの数との間の差に、少なくとも部分的に基づく（ステップ７０１０）。各ストライプセットに対して、ファイルサーバは、未使用のチャンクの数及びファイルシステムのために予約されたチャンクの数を判断することが可能である。ファイルサーバは、未使用のチャンクの数から予約されたチャンクの数を差し引き、且つこの差にスパン加重を掛けることが可能である。ファイルサーバは、ファイルシステムによって使用されているストライプセット上のチャンクの数に、ファイルシステム加重を掛けることが可能である。その積の和は、ストライプセットのスコアであろう。
【０１０５】
本方法は、最も高いスコアを有するストライプセットを選択するステップを含む（ステップ７０１５）。ファイルサーバは、ストライプセットのスコアを比較し、且つ最も高いスコアを有するものを選択する。
【０１０６】
さて図１４を参照すると、代表的なテーブル９０２５’が示され、且つ説明されるが、このテーブルは、ファイルシステムに割り当てられたランのファイルシステムスペースに、開始アドレス及び終了アドレスを格納する。テーブル９０２５’は、ＤＩチップ９０２０のようなＤＩチップ上にある。代表的なテーブル９０２５’は、ボリューム対応付けテーブルである。代表的な実施形態において、ファイルシステムのためのボリューム対応付けテーブルは、やはりＤＩチップ上に格納される、関連したストライプセット対応付けテーブル（便宜上、図示せず）を有する。ボリューム対応付けテーブルにおけるエントリは、ランのためのファイルシステムスペースにアドレスを格納する。ストライプセット対応付けテーブルの中の対応するエントリは、ＳＤ上の位置を格納し、該位置に、ファイルシステムスペースにおけるアドレスが対応付けられる。
【０１０７】
テーブル９０５２’の１つの代表的使用法において、スパンは６４個のチャンクの初期設定ランバイアスを有し、且つファイルサーバ９００２は、そのランバイアスに対して初期設定ランバイアスを選択している。テーブル９０２５’は３つのエントリを有し、且つ各エントリは、ファイルシステムに割り当てられたチャンクのランのファイルシステムスペースにおける位置を格納する。第１のランに対して、チャンク割り当て部９０１４はストライプセットを選択し、且つ１６個のチャンクの請求されていないランを検索した。チャンク割り当て部９０１４は、テーブル中の第１エントリにおいて、請求されていないランにおける第１チャンクに対して、開始アドレスＢＡ１を選択し、且つ格納した。チャンク割り当て部９０１４はまた、テーブルエントリにおけるこのチャンクの最後のアドレスＥＡ１を格納したが、これはライブランの終了を意味する。ファイルシステムがディスクスペースの付加的な拡大を要求した時、チャンク割り当て部９０１４は、ＥＡ１の後に継続するチャンクを割り当て、且つランの格納された終了アドレスＥＡ１を更新したが、この割り当て／更新は、ＢＡ１とＥＡ１との間のファイルスペースが、ファイルシステムに割り当てられてきたディスクスペースの、１６個の隣接するチャンクに対応するまで行われた。
【０１０８】
次回ファイルシステムがディスクスペースの拡大を要求した場合、チャンク割り当て部９０１４は、ストライプセットを選択し、且つ１６個のチャンクの別の請求されていないランを検索した。チャンク割り当て部９０１４は、テーブル中の第２エントリにおいて、この次の請求されていないランにおける第１チャンクに対して、開始アドレスＢＡ２及び終了アドレスＥＡ２を選択し、且つ格納した。再び、チャンク割り当て部９０１４は、ＥＡ２の後に継続するチャンクを割り当てると共に、ランの終了アドレスＥＡ２を更新し、且つ格納したが、この割り当て／更新／格納は、ＢＡ２とＥＡ２との間のファイルスペースが、ファイルシステムに割り当てられてきたディスクスペースの、１６個の隣接するチャンクに対応するまで行われた。
【０１０９】
ディスクスペースの次の拡大に対して、チャンク割り当て部９０１４はストライプセットを再び選択し、且つ１６個のチャンクの請求されていないランを検索した。チャンク割り当て部９０１４は、テーブル中の第３エントリにおいて、この次の請求されていないランにおける第１チャンクに対して、開始アドレスＢＡ３及び終了アドレスＥＡ３を選択し、且つ格納した。再び、チャンク割り当て部９０１４は、ＥＡ３の後に続くチャンクを割り当てると共に、ランの終了アドレスＥＡ３を更新し、且つ格納したが、この割り当て／更新／格納は、ＢＡ３とＥＡ３との間のファイルスペースが、ファイルシステムに割り当てられてきたディスクスペースの、１６個の隣接するチャンクに対応するまで行われた。テーブル９０５２’の別の代表的な使用法において、スパンは、３つのストライプセット、及び１６個のチャンクの初期設定ランバイアスを有する。ファイルシステムは、３００個のチャンクに等しいディスクスペースの大きな割り当てを要求した。スパンにわたって負荷を均衡させるために、チャンク割り当て部９０１４は、３つのストライプセットの各々に対して、１００個のチャンクを割り当てることを試みる。この実施形態において、チャンク割り当て部９０１４は、１００個のチャンクの請求されていないランに対して、各ストライプセットを検索する。
【０１１０】
チャンク割り当て部９０１４は、アドレスＢＡ１とアドレスＥＡ１との間の第１ストライプセット上に、請求されていないランの１００個のチャンクを見つける。チャンク割り当て部９０１４は、これら１００個のチャンクをファイルシステムに割り当て、且つテーブル９０２５’の第１エントリにアドレスＢＡ１及びアドレスＥＡ１を格納する。チャンク割り当て部９０１４は、アドレスＢＡ２とアドレスＥＡ２との間の第２ストライプセット上に、請求されていないランの１００個のチャンクを見つける。チャンク割り当て部９０１４は、これら１００個のチャンクをファイルシステムに割り当て、且つテーブル９０２５’の第２エントリにアドレスＢＡ２及びアドレスＥＡ２を格納する。チャンク割り当て部９０１４は、アドレスＢＡ３とアドレスＥＡ３との間の第３ストライプセット上に、請求されていないランの１００個のチャンクを見つける。チャンク割り当て部９０１４は、これら１００個のチャンクをファイルシステムに割り当て、且つテーブル９０２５”の第３エントリにアドレスＢＡ３及びアドレスＥＡ３を格納する。このように、１６個のチャンクのランバイアスにもかかわらず、チャンク割り当て部９０１４は、可能な限り少ない付加的なテーブルエントリを使用しながら、スパンにわたってディスクスペースの割り当てを大きく分布させるために、より長いランを割り当てることが可能である。
【０１１１】
さて図１５を参照すると、スパンにわたって負荷均衡を改善するために、ランバイアスを減少させる方法のための代表的な流れ図が示され、且つ説明される。本方法は、初期設定ランバイアスを獲得するステップを含む（ステップ１５０５）。幾つかの実施形態において、ファイルサーバ９００２は、データ記憶システムのユーザーによって入力された初期設定ランバイアスをメモリから引き出す。他の実施形態において、ファイルサーバ９００２は、スパンの管理者によって設定された初期設定ランバイアスをメモリから引き出す。本方法は、ストライプセットの数を２で割り、且つその結果としての値をファイルシステムの数で割るステップを含む（ステップ１５１０）。本方法は、その結果としての商を、初期設定ランバイアスと比較するステップを含む（ステップ１５１５）。本方法は、より小さな値に等しいランバイアスを設定するステップを含む（ステップ１５２０）。
【０１１２】
さて図１６を参照すると、ファイルシステムに割り当てるべきストライプセット上で、予約されていないチャンクを検索する方法のための代表的な流れ図が示され、且つ説明される。本方法は、複数のファイルシステムに関連付けられたチャンクを追跡するために、チャンクデータベースを維持するステップを含み、このチャンクデータベースは、固定数のエントリを含み、各エントリは、ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である（ステップ１６０５）。本方法は、複数のファイルシステムにおいて、ファイルシステムを拡大する要求を受信するステップを含む（ステップ１６１０）。本方法は、自身からストレージを割り当てるべきストライプセットを選択するステップを含む（ステップ１６１５）。本方法は、ストライプセット上の開始アドレスを有するチャンクデータベースからエントリを引き出すステップを含み、そこではエントリは、複数のファイルシステムにおける異なるファイルシステムのライブランに対応する（ステップ１６２０）。本方法は、ストライプセット上で少なくとも１つのチャンクを識別するステップを含み、このチャンクは、ライブランにおける最後のチャンクに続き、且つこれに隣接するＮ個のチャンクの後に位置し、ここでＮは、ライブランのアクティブラン長を引いたランバイアスに等しい（ステップ１６２５）。本方法は、もし少なくとも１つのチャンクが利用可能である場合、少なくとも１つのチャンクをファイルシステムに割り当てるステップを含む（ステップ１６３０）。
【０１１３】
さて図１７を参照すると、ファイルサーバによって、ファイルシステムに対するストレージを拡大する方法のための代表的な流れ図が示され、且つ説明される。ここで、このファイルシステムは、複数のストライプセットから選択された複数のチャンクを含み、ファイルサーバは、ファイルシステムの仮想アドレススペースを、ファイルサーバによってチャンクに関連付けられた物理記憶アドレスに対応付ける。
【０１１４】
本方法は、複数のファイルシステムに関連付けられたチャンクを追跡するためのチャンクデータベースを維持するステップを含み、このチャンクデータベースは固定数のエントリを含み、各エントリは、ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である（ステップ１７０５）。本方法は、複数のファイルシステムにおいて、ファイルシステムを拡大する要求を受信するステップを含む（ステップ１７１０）。本方法は、要求に対するチャンクの数が、ランバイアスにおけるチャンクの数とスパン上のストライプセットの数との積を超えることを判断するステップを含む（ステップ１７１５）。本方法は、要求に対するチャンクの数をストライプセットの数で割ることによって、各ストライプセットから割り当てるべきチャンクの数を判断するステップを含む（ステップ１７２０）。本方法は、各ストライプセットから割り当てるべきチャンクの数に等しい、利用可能なチャンクのランを、各ストライプセット上で、検索するステップを含む（ステップ１７２５）。本方法は、利用可能なチャンクのランを、各ストライプセットから、割り当てるステップを含む（ステップ１７３０）。本方法は、利用可能なチャンクのランに関連付けられたチャンクデータベースにおいて、利用可能なチャンクの各ランに対して、エントリを作成するステップを含み、ここでエントリは、ランの長さを含む（ステップ１７３５）。
【０１１５】
上で説明された代表的な実施形態において、ランバイアスは、ファイルシステムに割り当てられたチャンクのラン長を制限するために使用されてもよい。従って、上で説明された代表的な実施形態は、一般に、更に多数のチャンクが、固定長のチャンクデータベースに基づいて、ファイルシステムに割り当てられることを可能にする一方で、例えば、ファイルシステムがＸ個のチャンクに制限されるというよりはむしろ、ランバイアスは、ファイルシステムがどれだけ拡大され得るかを依然として有効に制限し（ここでＸは、チャンクデータベースにおけるエントリの数である）、ファイルシステムは、ある実施形態において、（ランバイアス＊Ｘ）個のチャンクに有効に制限されてもよい。従って、様々な代替的実施形態において、ファイルシステムがその最後のチャンク・データベース・エントリにある場合、又はその近くにある場合、ランバイアス制限（及びランバイアスが適用される方法、並びにチャンクが予約される方法）は、より長いラン長を許可するために修正されてもよい。しかし、一例として、ファイルシステムがその最後のチャンク・データベース・エントリにある場合、ファイルシステムが拡大を継続することを可能にするために、ランバイアスは、ファイルシステムに対して増加されるか、又は完全に削除されてもよい。ランバイアスのそのような増加又は削除に関連して、より多数の隣接するチャンク、例えば所定最大数のチャンク又はファイルシステムの所定パーセント増加（例えば、所定パーセントだけファイルシステムを拡大するのに必要となりそうなチャンクの数）、が予約されてもよい。
【０１１６】
注意されるべきことであるが、用語「サーバ」は、本明細書では装置を説明するために使用されるが、この装置は、通信システムにおいて使用されてもよく、且つ本発明を任意の特別なタイプの装置に限定すると解釈されるべきではない。従って、本発明の実施形態は、クライアント、サーバ、コンピュータ、スイッチ、又は他のタイプの通信装置において履行されてもよい。
【０１１７】
本発明は、多くの異なる形態において具体化されてもよく、多くの異なる形態には、以下に限定されるものではないが、プロセッサ（例えば、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ、又は汎用コンピュータ）と共に使用するためのコンピュータ・プログラム・ロジック、プログラマブルロジック装置（例えば、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）又は他のＰＬＤ）と共に使用するためのプログラマブルロジック、個別部品、集積回路（例えば、特定用途向け集積回路（ＡＳＩＣ））又はこれらの任意の組み合わせを含む他の手段が含まれる。
【０１１８】
本明細書で先に説明された機能性の全て又は一部を履行するコンピュータ・プログラム・ロジックは、様々な形態で具体化されてもよい。様々な形態には、以下に限定されるものではないが、ソースコード形態、コンピュータ実行形態、及び様々な中間形態（例えば、アセンブラ、コンパイラ、リンカー、又はロケーターによって生成される形態）が含まれる。ソースコードは、様々なオペレーティングシステム又はオペレーティング環境と共に使用するための適切なプログラミング言語（例えば、目的コード、アセンブリ言語、又は、Ｆｏｒｔｒａｎ、Ｃ、Ｃ＋＋、ＪＡＶＡ、又はＨＴＭＬのような高レベル言語）において履行される、一連のコンピュータプログラム命令を含んでもよい。ソースコードは、様々なデータ構造及び通信メッセージを定義し、且つ使用する。ソースコードは、コンピュータ実行可能形態であってもよく（例えば、解釈プログラムを介して）、又はソースコードは、（例えば、翻訳プログラム、アセンブラ、又はコンパイラを介して）コンピュータ実行可能形態に変換されてもよい。
【０１１９】
コンピュータプログラムは、有形の記憶媒体において、永久的又は一時的のいずれかで、任意の形態（例えば、ソースコード形態、コンピュータ実行可能形態、又は中間形態）に固定されるが、有形の記憶媒体には、半導体メモリ装置（例えば、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭ、又はフラッシュ−プログラマブルＲＡＭ）磁気メモリ装置（例えば、ディスケット又は固定ディスク）、光メモリ装置（例えば、ＣＤ−ＲＯＭ）、ＰＣカード（例えば、ＰＣＭＣＩＡ）、又は他のメモリ装置のようなものが含まれる。コンピュータプログラムは、様々な通信技術の任意の技術を用いて、コンピュータに伝達可能である信号における任意の形態に固定されてもよく、様々な通信技術には、以下に限定されるものではないが、アナログ技術、デジタル技術、光技術、無線技術（例えば、ブルートゥース）、ネットワーク技術、及びインターネットワーキング技術が含まれる。コンピュータプログラムは、印字された文書又は電子文書（例えば、収縮包装されたソフトウェア）を伴ったリムーバブル記憶媒体として任意の形態で配布されてもよく、コンピュータシステムにプレインストールされているか（例えば、システムＲＯＭ又は固定ディスク上に）、又は、サーバ又は電子掲示板から通信システムを通して配布されてもよい（例えば、インターネット又はワールド・ワイド・ウェブ）。
【０１２０】
本明細書で先に説明された機能性の全て又は一部を履行するハードウェアロジック（プログラマブルロジック装置と共に使用するためのプログラマブルロジックを含む）は、伝統的な手動方法を用いて設計されてもよく、又は、コンピュータ支援設計（ＣＡＤ)，ハードウェア記述言語（例えば、ＶＨＤＬ又はＡＨＤＬ）又はＰＬＤプログラミング言語（例えば、ＰＡＬＡＳＭ、ＡＢＥＬ、又はＣＵＰＬ）のような様々なツールを用いて、設計され、データが取り込まれ、シミュレーションされ、又は電子的に文書化されてもよい。
【０１２１】
プログラマブルロジックは、半導体メモリ装置（例えば、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＥＰＲＯＭ、又はフラッシュ−プログラマブルＲＡＭ）、磁気メモリ装置（例えば、ディスケット、又は固定ディスク）、光メモリ装置（例えば、ＣＤ−ＲＯＭ）又は他のメモリ装置のような有形の記憶媒体に、永久的又は一時的のいずれかで固定される。プログラマブルロジックは、様々な通信技術の任意の技術を用いて、コンピュータに伝達可能である信号に固定されてもよく、様々な通信技術には、以下に限定されるものではないが、アナログ技術、デジタル技術、光技術、無線技術（例えば、ブルートゥース）、ネットワーク技術、及びインターネットワーキング技術が含まれる。プログラマブルロジックは、印字された文書又は電子文書（例えば、収縮包装されたソフトウェア）を伴ったリムーバブル記憶媒体として配布されてもよく、コンピュータシステムにプレインストールされるか（例えば、システムＲＯＭ又は固定ディスク上に）、又は、サーバ又は電子掲示板から通信システムを通して配布されてもよい（例えば、インターネット又はワールド・ワイド・ウェブ）。
【０１２２】
本発明の様々な実施形態は、この節に続く（且つこの出願の末端部に提供された実際の請求項の前の）節に列挙された潜在的な請求項によって特徴付けられてもよい。これらの潜在的な請求項は、この出願の書面による明細の一部を形成する。従って、次の潜在的な請求項の主題は、この出願、又はこの出願に基づいて優先権を主張する任意の出願を含む後の訴訟手続きにおいて、実際の請求項として提示されてもよい。そのような潜在的な請求項を包含することは、実際の請求項が、潜在的な請求項の主題を対象としないことを意味すると解釈されるべきではない。従って、後の訴訟手続きにおいて、これらの潜在的な請求項を提示しない決定は、一般の人々にその主題を寄贈するものと解釈されるべきではない。
【０１２３】
限定することなく、請求されるかもしれない潜在的な主題（以下に提示される実際の請求項との混乱を回避するように、文字「Ｐ」で始められる）は、以下を含む。
【０１２４】
［請求項Ｐ１６］
きめ細かな、拡張可能な方法でファイルシステムのためのストレージを拡大する方法であって、
スパンに対するランバイアスをファイルサーバによって判断するステップであって、前記ランバイアスは、ファイルシステムのためのアドレス移行テーブルにおけるエントリに関連付けられたメモリの隣接するチャンクの数を示す、ステップと、
前記ファイルシステムのためのメモリを拡大することに対する要求を、前記ファイルサーバによって受信するステップと、
１つのグループのストライプセット中の各ストライプセットをチャンク割り当て部によって採点するステップであって、この採点が、前記ストライプセットにおける未使用のチャンクの数、及び前記ファイルシステムによって使用されている前記ストライプセット上のチャンクの数に少なくとも部分的に基づく、ステップと、
最も高いスコアを有する前記ストライプセット上のチャンクを、前記チャンク割り当て部によって割り当てるステップであって、前記割り当てられたチャンクは、他のファイルシステムのために予約されたランの外側にある、ステップと、
を備える、方法。
【０１２５】
［請求項Ｐ１７］
請求項Ｐ１６に記載の方法であって、
スパンに対する前記ランバイアスを判断するステップは、
初期設定ランバイアスを前記ファイルサーバによって判断すること、
を備える、方法。
【０１２６】
［請求項Ｐ１８］
請求項Ｐ１６に記載の方法であって、
スパンに対する前記ランバイアスを判断するステップは、
ストライプセットの数及びファイルシステムの数に基づいて、前記ランバイアスを前記ファイルサーバによって判断すること、
を備える、方法。
【０１２７】
［請求項Ｐ１９］
請求項Ｐ１６に記載の方法であって、
各ストライプセットを採点するステップは、
前記ファイルシステムの最後に割り当てられたチャンクの後のチャンクが利用可能であることを、前記チャンク割り当て部によって判断することと、
前記ファイルシステムの現在のストライプセットのために、バイアスファクタを前記チャンク割り当て部によって判断することであって、前記現在のストライプセットは、前記ファイルシステムの前記最後に割り当てられたチャンクを含む、ことと、
前記バイアスファクタを有する前記現在のストライプセットを、前記チャンク割り当て部によって採点することと、
を備える、方法。
【０１２８】
［請求項Ｐ２０］
請求項Ｐ１６の方法であって、
各ストライプセットを採点するステップは、
前記ファイルシステムの最後に割り当てられたチャンクの後のチャンクが、別のファイルシステムによって使用されることを、前記チャンク割り当て部によって判断することと、
１つのグループのストライプセット中の各ストライプセットを前記チャンク割り当て部によって採点することであって、この採点は、前記ストライプセット上の未使用のチャンクの数と、他のファイルシステムのために予約されるチャンクの数との間の差に少なくとも部分的に基づく、ことと、
を更に備える、方法。
【０１２９】
［請求項Ｐ２１］
請求項Ｐ１６に記載の方法であって、
各ストライプセットを採点するステップは、
１つのグループのストライプセット中の各ストライプセットを、前記チャンク割り当て部によって採点することであって、この採点は、前記ストライプセット上の未使用のチャンクの数、スパン加重、前記ファイルシステムによって使用されている前記ストライプセット上のチャンクの数、及びファイルシステム加重に少なくとも部分的に基づく、こと、
を更に備える、方法。
【０１３０】
［請求項Ｐ２２］
請求項Ｐ１６に記載の方法であって、
最も高いスコアを有する前記ストライプセット上に前記チャンクを割り当てるステップは、
前記ファイルシステムの最後に割り当てられたチャンクの後のチャンクを、前記チャンク割り当て部によって選択すること、
を備える、方法。
【０１３１】
［請求項Ｐ２３］
請求項Ｐ１６に記載の方法であって、
最も高いスコアを有する前記ストライプセット上に前記チャンクを割り当てるステップは、
自身の長さが少なくとも前記ランバイアスである、予約されていないチャンクのランを、前記チャンク割り当て部によって検索することと、
前記ランにおける第１チャンクを、前記チャンク割り当て部によって選択することと、
を備える、方法。
【０１３２】
［請求項Ｐ２４］
請求項Ｐ１６に記載の方法であって、
最も高いスコアを有する前記ストライプセット上に前記チャンクを割り当てるステップは、
自身の長さが少なくとも前記ランバイアスである、予約されたチャンクのランを、前記チャンク割り当て部によって検索することと、
前記ランの後半における第１チャンクを、前記チャンク割り当て部によって選択することと、
を備える、方法。
【０１３３】
［請求項Ｐ２５］
データ記憶システムであって、
チャンク割り当て部を備えるファイルサーバであって、前記ファイルサーバは、スパンに対するランバイアスを判断するように構成され、前記ランバイアスは、ファイルシステムのためのアドレス移行テーブルにおけるエントリに関連付けられたメモリの隣接するチャンクの数を示し、且つ、
前記チャンク割り当て部は、１つのグループのストライプセット中の各ストライプセットを採点するように構成され、この採点は、前記ストライプセットにおける未使用のチャンクの数、及び前記ファイルシステムによって使用されている前記ストライプセット上のチャンクの数に少なくとも部分的に基づき、且つ、
前記チャンク割り当て部は、最も高いスコアを有する前記ストライプセット上にチャンクを割り当てるように構成され、前記割り当てられたチャンクは、他のファイルシステムのために予約されたランの外側にある、ファイルサーバ、
を備える、データ記憶システム。
【０１３４】
［請求項Ｐ２６］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記ファイルサーバは、初期設定ランバイアスを判断するように更に構成される、データ記憶システム。
【０１３５】
［請求項Ｐ２７］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記ファイルサーバは、ストライプセットの数及びファイルシステムの数に基づいて、前記ランバイアスを判断するように更に構成される、データ記憶システム。
【０１３６】
［請求項Ｐ２８］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記ファイルシステムの最後に割り当てられたチャンクの後のチャンクが利用可能であることを判断し、
前記ファイルシステムの現在のストライプセットに対するバイアスファクタを判断し、前記現在のストライプセットは、前記ファイルシステムの前記最後に割り当てられたチャンクを含み、
且つ、前記バイアスファクタを有する前記現在のストライプセットを採点する、
ように更に構成される、データ記憶システム。
【０１３７】
［請求項Ｐ２９］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記ファイルシステムの最後に割り当てられたチャンクの後のチャンクが別のファイルシステムによって使用されることを決定し、
且つ、前記ストライプセット上の未使用のチャンクの数と、他のファイルシステムのために予約されたチャンクの数との間の差に少なくとも部分的に基づいて、１つのグループのストライプセット中の各ストライプセットを採点する、
ように更に構成される、データ記憶システム。
【０１３８】
［請求項Ｐ３０］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記チャンク割り当て部は、１つのグループのストライプセット中の各ストライプセットのスコアを採点するように更に構成され、この採点は、前記ストライプセット上の未使用のチャンク、スパン加重、前記ファイルシステムによって使用されている前記ストライプセット上のチャンクの数、及びファイルシステム加重に少なくとも部分的に基づく、データ記憶システム。
【０１３９】
［請求項Ｐ３１］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記ファイルシステムの最後に割り当てられたチャンクの後のチャンクを選択するように更に構成される、データ記憶システム。
【０１４０】
［請求項Ｐ３２］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記チャンク割り当て部は、自身の長さが少なくともランバイアスである、予約されていないチャンクのランを検索し、
且つ前記ランにおける第１チャンクを選択する、
ように更に構成される、データ記憶システム。
【０１４１】
［請求項Ｐ３３］
請求項Ｐ２５に記載のデータ記憶システムであって、
前記チャンク割り当て部は、
自身の長さが少なくともランバイアスである、予約されたチャンクのランを検索し、
且つ前記ランの後半における第１チャンクを選択する、
ように更に構成される、データ記憶システム。
【０１４２】
［請求項Ｐ３４］
ファイルサーバによってファイルシステムのためのストレージを拡大する方法であって、
前記ファイルシステムは、複数のストライプセットから選択された複数のチャンクを含み、前記ファイルサーバは、ファイルシステムの仮想アドレススペースを、前記チャンクに関連付けられた物理記憶アドレスに対応付け、
前記方法は、ファイルサーバによって、
複数のファイルシステムに関連付けられた前記チャンクを追跡するためのチャンクデータベースを維持するステップであって、前記チャンクデータベースは固定数のエントリを含み、各エントリは、前記ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、ステップと、
前記複数のファイルシステムにおいて、ファイルシステムを拡大する要求を受信するステップと、
自身からストレージを割り当てるべきストライプセットを選択するステップと、
前記ストライプセット上で開始アドレスを有する前記チャンクデータベースからエントリを引き出すステップであって、前記エントリは、前記複数のファイルシステムにおける異なるファイルシステムのライブランに対応する、ステップと、
前記ストライプセット上で少なくとも１つのチャンクを識別するステップであって、前記ストライプセットは、ライブランにおける最後のチャンクに続き、且つライブランにおける最後のチャンクに隣接するＮ個のチャンクの後に位置し、Ｎは前記ライブランのアクティブラン長を引いたランバイアスに等しい、ステップと、
もし少なくとも１つのチャンクが利用可能である場合、前記ファイルシステムに前記少なくとも１つのチャンクを割り当てるステップと、
を備える、方法。
【０１４３】
［請求項Ｐ３５］
請求項Ｐ３４に記載の方法であって、
前記ストライプセット上に開始アドレスを有する前記チャンクデータベースからエントリを引き出し、且つ、少なくとも１つのチャンクが利用可能となるまで、前記少なくとも１つのチャンクを識別することを継続するステップであって、前記少なくとも１つのチャンクは、前記ライブランにおける最後のチャンクに続き、且つ前記ライブランにおける最後のチャンクに隣接するＮ個のチャンクの後に位置する、ステップ、
を更に備える、方法。
【０１４４】
［請求項Ｐ３６］
請求項Ｐ３４に記載の方法であって、
前記ストライプセット上で少なくとも１つのチャンクを識別するステップは、
ランバイアスに等しい利用可能なチャンクのランを識別すること、
を備える、方法。
【０１４５】
［請求項Ｐ３７］
請求項Ｐ３４に記載の方法であって、
前記ストライプセット上で少なくとも１つのチャンクを識別するステップは、
前記ストライプセット上で利用可能なチャンクの最も長いランを識別すること、
を備える、方法。
【０１４６】
［請求項Ｐ３８］
データ記憶システムであって、
メモリであって、該メモリに、複数のファイルシステムに関連付けられたチャンクを追跡するためのチャンクデータベースが格納され、前記チャンクデータベースは固定数のエントリを含み、各エントリは、前記ファイルシステムに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、メモリと、
チャンク割り当て部であって、該チャンク割り当て部は、前記複数のファイルシステムにおいてファイルシステムを拡大する要求を受信し、自身からストレージを割り当てるべきストライプセットを選択し、前記ストライプセット上に開始アドレスを有するチャンクデータベースからエントリを引き出し（前記エントリは、前記複数のファイルシステムにおける異なるファイルシステムのライブランに対応する）、前記ストライプセット上で少なくとも１つのチャンクを識別し（前記ストライプセットは、前記ライブランにおける最後のチャンクに続き、且つ前記ライブランにおける最後のチャンクに隣接するＮ個のチャンクの後に位置し、ここでＮは、前記ライブランのアクティブラン長を引いたランバイアスに等しい）、且つもし少なくとも１つのチャンクが利用可能である場合、前記ファイルシステムに少なくとも１つのチャンクを割り当てる、チャンク割り当て部と、
を備える、データ記憶システム。
【０１４７】
［請求項Ｐ３９］
請求項Ｐ３８に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記ストライプセット上に開始アドレスを有するチャンクデータベースからエントリを引き出し、且つ少なくとも１つのチャンクが利用可能になるまで、前記少なくとも１つのチャンクを識別するように更に構成され、前記少なくとも１つのチャンクは、前記ライブランにおける最後のチャンクに続き、且つ前記ライブランにおける最後のチャンクに隣接するＮ個のチャンクの後に位置する、データ記憶システム。
【０１４８】
［請求項Ｐ４０］
請求項Ｐ３８に記載のデータ記憶システムであって、
前記チャンク割り当て部は、ランバイアスに等しい利用可能なチャンクのランを識別するように更に構成される、データ記憶システム。
【０１４９】
［請求項Ｐ４１］
請求項Ｐ３８に記載のデータ記憶システムであって、
前記チャンク割り当て部は、前記ストライプセット上の利用可能なチャンクの最も長いランを識別するように更に構成される、データ記憶システム。
【０１５０】
［請求項Ｐ４２］
ファイルサーバによってファイルシステムのためのストレージを拡大する方法であって、
前記ファイルシステムは、複数のストライプセットから選択された複数のチャンクを含み、前記ファイルサーバは、前記ファイルシステムの仮想アドレススペースを、前記チャンクに関連付けられた物理記憶アドレスに対応付け、
前記方法は、前記ファイルサーバによって、
複数のファイルシステムに関連付けられた前記チャンクを追跡するためのチャンクデータベースを維持するステップであって、前記チャンクデータベースは固定数のエントリを含み、各エントリは、前記ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、ステップと、
前記複数のファイルシステムにおいてファイルシステムを拡大する要求を受信するステップと、
前記要求に対するチャンクの数が、ランバイアスにおけるチャンクの数及びスパン上のストライプセットの数を超えることを決定するステップと、
前記要求に対するチャンクの数をストライプセットの数で割ることによって、各ストライプセットから割り当てるべきチャンクの数を判断するステップと、
各ストライプセットから割り当てるべきチャンクの数に等しい利用可能なチャンクのランを、各ストライプセット上で検索するステップと
利用可能なチャンクの前記ランを、各ストライプセットから割り当てるステップと、
利用可能なチャンクの前記ランに関連付けられた前記チャンクデータベースにおけるエントリを、利用可能なチャンクの各ランに対して作成するステップであって、前記エントリは前記ランの長さを含む、ステップと、
を備える、方法。
【０１５１】
［請求項Ｐ４３］
データ記憶システムであって、
メモリであって、該メモリに、複数のファイルシステムに関連付けられたチャンクを追跡するためのチャンクデータベースが格納され、前記チャンクデータベースは固定数のエントリを含み、各エントリは、前記ファイルシステムの１つに割り当てられたストレージの一部の開始アドレス及び長さに関する情報を格納することが可能である、メモリと、
チャンク割り当て部であって、該チャンク割り当て部は、前記複数のファイルシステムにおいてファイルシステムを拡大する要求を受信し、前記要求に対するチャンクの数が、ランバイアスにおけるチャンクの数とスパン上のストライプセットの数との積を超えることを判断し、前記要求に対するチャンクの数をストライプセットの数で割ることによって、各ストライプセットから割り当てるべきチャンクの数を判断し、各ストライプセットから割り当てるべきチャンクの数に等しい利用可能なチャンクのランを各ストライプセット上で検索し、利用可能なチャンクのランを各ストライプセットから割り当て、利用可能なチャンクのランに関連付けられた前記チャンクデータベースにおいてエントリを、利用可能なチャンクの各ランに対して作成するように構成され、前記エントリは前記ランの長さを含む、チャンク割り当て部と、
を備える、データ記憶システム。
【０１５２】
本発明は、本発明の真の範囲を外れることなく、他の特定の形態において具体化されてもよい。説明された実施形態は、全ての点で、単に例証的であり、限定的ではないと考えられるべきである。
【図１】
2016511879.tif 000003
【図２】
2016511879.tif 000004
【図３】
2016511879.tif 000005
【図４】
2016511879.tif 000006
【図５】
2016511879.tif 000007
【図６】
2016511879.tif 000008
【図７】
2016511879.tif 000009
【図８】
2016511879.tif 000010
【図９】
2016511879.tif 000011
【図１０】
2016511879.tif 000012
【図１１】
2016511879.tif 000013
【図１２】
2016511879.tif 000014
【図１３】
2016511879.tif 000015
【図１４】
2016511879.tif 000016
【図１５】
2016511879.tif 000017
【図１６】
2016511879.tif 000018
【図１７】
2016511879.tif 000019
【手続補正書】
【提出日】平成27年9月29日(2015.9.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ファイルシステムの割り当てられたチャンクを示すチャンクデータベースを維持するステップと、
前記ファイルシステムは、複数のストライプセットに基づくストレージを管理するファイルサーバにより管理されており、前記複数のストライプセットの複数のチャンクのうちの割り当てられたチャンクの仮想化されたストレージ領域上に存在し、
前記複数のストライプセットの各々は、複数のチャンクを含む連続したストレージスペースに対応しており、
前記チャンクデータベースは、固定数のエントリを含み、
各エントリは、１以上の隣接し割り当てられたチャンクのランの開始アドレス及び長さを示す情報を格納するようになっており、
前記ファイルシステムのための前記ストレージを拡大する要求を受信した場合、前記維持されたチャンクデータベースの前記固定数のエントリに基づいて、最後に割り当てられたチャンクを識別するステップと、
前記識別されたチャンクと同じストライプセットから選択され記識別されたチャンクに隣接している１以上の更なるチャンクを割り当てるステップと、
隣接し割り当てられたチャンクであって前記識別されたチャンク及び前記１以上の更なるチャンクを含む２以上のチャンクのランの長さにおける増加を反映させるために、前記識別されたチャンクに関連付けられたエントリであって前記チャンクデータベースにおけるエントリを更新するステップと
をコンピュータに実行させるコンピュータプログラム。
【請求項２】
前記１以上の更なるチャンクが前記ファイルシステムへの割り当てに対して利用可能な状態に留まるように、前記１以上の更なるチャンクを割り当てる前に、前記１以上の更なるチャンクを予約するステップ、
を更にコンピュータに実行させるコンピュータプログラム。
【請求項３】
前記ファイルシステムへの割り当てを可能な状態に留めるために、前記１以上の更なるチャンクを割り当てた後に、これまで割り当てられてきた前記１以上の更なるチャンクに隣接している１以上のチャンクであって、前記識別されたチャンクと同じストライプセットのうちの１以上のチャンクを、予約するステップ、
を更にコンピュータに実行させる請求項１又は２に記載のコンピュータプログラム。
【請求項４】
Ｎ個までのチャンクが予約され、
Ｎは、所定のランバイアスに等しく、
前記所定のランバイアスは、アクティブラン長を引いた、隣接し割り当てられた１以上のチャンクのランの好ましい長さを示し、
前記アクティブラン長は、最後に割り当てられたチャンクを含む隣接したチャンクの数を示す、
請求項２又は３に記載のコンピュータプログラム。
【請求項５】
前記ファイルシステムについてのアクティブラン長を判断するステップと、
前記アクティブラン長は、前記最後に割り当てられたチャンクを含む隣接したチャンクの数を示し、
下記（１）及び（２）であると判断するステップと
（１）前記判断されたアクティブラン長が、隣接し割り当てられた１以上のチャンクのランの好ましい長さを示すランバイアスに満たなければ、前記ファイルシステムへの割り当てに対して少なくとも１つの更なるチャンクが存在する、
（２）前記最後に割り当てられたチャンクと同じストライプセットのうちの少なくとも１つのチャンクであって、前記最後に割り当てられたチャンクに隣接する少なくとも１つのチャンクが存在する、
を更にコンピュータに実行させる請求項１乃至４のうちのいずれか１項に記載のコンピュータプログラム。
【請求項６】
１以上の更なるチャンクを割り当てるステップでは、
前記識別されたチャンクと同じストライプセットから前記識別されたチャンクに隣接するＮ個までの更なるチャンクを割り当てる（Ｎは、前記アクティブラン長を引いた前記ランバイアスに等しい）、
請求項５に記載のコンピュータプログラム。
【請求項７】
ストライプセットの数及びファイルシステムの数に基づいて、前記ランバイアスを判断するステップ、
を更にコンピュータに実行させる請求項５又は６に記載のコンピュータプログラム。
【請求項８】
前記１以上の更なるチャンクを割り当てる前に、前記識別されたチャンクと同じストライプセットから選択され前記識別された最後のチャンクに隣接している１以上の更なるチャンクを、前記ファイルシステムに対して割り当て可能であるか否かを判断するステップ、
を更にコンピュータに実行させる請求項１乃至７のうちのいずれか１項に記載のコンピュータプログラム。
【請求項９】
前記１以上の更なるチャンクが割り当て可能でないと判断された場合、前記識別されたチャンクのストライプセットとは異なるいずれかの別のストライプセットを選択するステップと、
前記選択された別のストライプセットから１以上の更なるチャンクを割り当てるステップと
を更にコンピュータに実行させる請求項８に記載のコンピュータプログラム。
【請求項１０】
前記選択された別のストライプセットが、別のファイルシステムへの割り当てのために予約される、１以上の隣接したチャンクのラン、を含む場合、隣接し割り当てられる１以上のチャンクのランの好ましい長さを示すランバイアスに少なくとも対応する長さを有する１以上の予約されていないチャンクの別のランについて別のストライプセットを検索し、且つ、前記ファイルシステムへの割り当てのために、前記検索されたランにおける第１チャンクを選択するステップ
を更にコンピュータに実行させる請求項９に記載のコンピュータプログラム。
【請求項１１】
前記選択された別のストライプセットが、別のファイルシステムへの割り当てのために予約される、１以上の隣接したチャンクのランを含む場合、１以上の予約されていないチャンクの最も長いランについて別のストライプセットを検索し、且つ、前記ファイルシステムへの割り当てのために、前記検索された最も長いランにおける第１チャンクを選択するステップ
を更にコンピュータに実行させる請求項９又は１０に記載のコンピュータプログラム。
【請求項１２】
前記ファイルサーバは、前記ファイルシステムの仮想アドレススペースを、前記複数のチャンクに関連付けられた物理記憶アドレスに対応付けるように構成されている、
請求項１乃至１１のうちのいずれか１項に記載のコンピュータプログラム。
【請求項１３】
ファイルシステムの割り当てられたチャンクを示すチャンクデータベースを維持するステップと、
前記ファイルシステムは、複数のストライプセットに基づくストレージを管理するファイルサーバにより管理されており、前記複数のストライプセットの複数のチャンクのうちの割り当てられたチャンクの仮想化されたストレージ領域上に存在し、
前記複数のストライプセットの各々は、複数のチャンクを含む連続したストレージスペースに対応しており、
前記チャンクデータベースは、固定数のエントリを含み、
各エントリは、１以上の隣接し割り当てられたチャンクのランの開始アドレス及び長さを示す情報を格納するようになっており、
前記ファイルシステムのための前記ストレージを拡大する要求を受信した場合、前記維持されたチャンクデータベースの前記固定数のエントリに基づいて、最後に割り当てられたチャンクを識別するステップと、
前記識別され最後に割り当てられたチャンクと同じストライプセットから選択された１以上のチャンクであって、前記識別され最後に割り当てられたチャンクに隣接している１以上のチャンクである、１以上の更なるチャンクを割り当てるステップと、
隣接し割り当てられたチャンクであって前記識別された最後のチャンク及び前記１以上の更なるチャンクを含む２以上のチャンクのランの長さにおける増加を反映させるために、前記識別され最後に割り当てられたチャンクに関連付けられ前記チャンクデータベースにおけるエントリを、更新するステップと
を有する方法。
【請求項１４】
ファイルシステムの割り当てられたチャンクを示すチャンクデータベースを維持する手段と、
前記ファイルシステムは、ストレージの基になる複数のストライプセットの複数のチャンクのうちの割り当てられたチャンクの仮想化されたストレージ領域上に存在し、
前記複数のストライプセットの各々は、複数のチャンクを含む連続したストレージスペースに対応しており、
前記チャンクデータベースは、固定数のエントリを含み、
各エントリは、１以上の隣接し割り当てられたチャンクのランの開始アドレス及び長さを示す情報を格納するようになっており、
前記ファイルシステムのための前記ストレージを拡大する要求を受信した場合、前記維持されたチャンクデータベースの前記固定数のエントリに基づいて、最後に割り当てられたチャンクを識別する手段と、
前記識別され最後に割り当てられたチャンクと同じストライプセットから選択された１以上のチャンクであって、前記識別され最後に割り当てられたチャンクに隣接している１以上のチャンクである、１以上の更なるチャンクを割り当てる手段と、
隣接し割り当てられたチャンクであって前記識別された最後のチャンク及び前記１以上の更なるチャンクを含む２以上のチャンクのランの長さにおける増加を反映させるために、前記識別され最後に割り当てられたチャンクに関連付けられ前記チャンクデータベースにおけるエントリを、更新する手段と
を備えるファイルサーバ。
【請求項１５】
請求項１４に記載のファイルサーバと、
前記ファイルサーバに管理された１以上のファイルシステムのためにストレージを提供する１以上のＲＡＩＤシステムと、
を備えるファイル記憶システム。
【国際調査報告】
2016511879.tif 000020