(57)【特許請求の範囲】
【請求項１】
予め定められた数のｉｎｏｄｅを格納しうる第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当てる方法であって、
前記コンピューティングファイルシステムのコンピュータに、
前記第１のｉｎｏｄｅテーブルに、前記予め定められた数のｉｎｏｄｅが格納されているか否かを判断するステップと、
前記コンピューティングファイルシステムにおいて、新たなｉｎｏｄｅを割り当てる場合に、前記判断するステップにより、前記第１のｉｎｏｄｅテーブルに、前記予め定められた数のｉｎｏｄｅが格納されていると判断されたときは、前記コンピューティングファイルシステムにおいて、第２のｉｎｏｄｅテーブルを作成するステップと、
前記第１のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を含む第１のｉｎｏｄｅマップ、および、前記第２のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を含む第２のｉｎｏｄｅマップを作成するステップと
を実行させ、
前記第１のｉｎｏｄｅマップは、前記第２のｉｎｏｄｅマップの位置情報を含む
方法。
【請求項２】
前記第２のｉｎｏｄｅテーブルに、予め定められた数のｉｎｏｄｅが格納されている場合に、少なくとも１つの第３のｉｎｏｄｅテーブルを作成するステップと、
前記第３のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を含む第３のｉｎｏｄｅマップを作成するステップと
を前記コンピュータにさらに実行させ、
前記第２のｉｎｏｄｅマップは、前記第３のｉｎｏｄｅマップの位置情報をさらに含む
請求項１に記載の方法。
【請求項３】
各前記ｉｎｏｄｅテーブルに格納されうるｉｎｏｄｅの数は、ディスク空間の総量と、各前記ｉｎｏｄｅマップで参照されるｉｎｏｄｅテーブルアドレスの個数との関数である
請求項２に記載の方法。
【請求項４】
ファイルシステムの作成中に、前記ｉｎｏｄｅの数を求めるステップ
を前記コンピュータにさらに実行させる請求項３に記載の方法。
【請求項５】
予め定められた数のｉｎｏｄｅをそれぞれ格納しうる少なくとも第１のｉｎｏｄｅテーブルと、第２のｉｎｏｄｅテーブルとを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当て解除する方法であって、
前記コンピューティングファイルシステムのコンピュータに、
前記第２のｉｎｏｄｅテーブルに、ｉｎｏｄｅが格納されているか否かを判断するステップと、
前記判断するステップにより、前記第２のｉｎｏｄｅテーブルにｉｎｏｄｅが格納されていると判断された場合以外は、前記第２のｉｎｏｄｅテーブルを削除するステップと、
前記第２のｉｎｏｄｅテーブルを削除した場合に、前記第１のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を少なくとも含む第１のｉｎｏｄｅマップから、前記第２のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を少なくとも含む第２のｉｎｏｄｅマップの位置情報を削除するステップと
を実行させる方法。
【請求項６】
前記第２のｉｎｏｄｅテーブルを削除した場合に、前記第２のｉｎｏｄｅテーブルに対応する前記第２のｉｎｏｄｅマップを削除するステップ
を前記コンピュータにさらに実行させる請求項５に記載の方法。
【請求項７】
予め定められた数のｉｎｏｄｅを格納しうる第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当てるコンピュータプログラムであって、
前記コンピューティングファイルシステムのコンピュータに、
前記第１のｉｎｏｄｅテーブルに、前記予め定められた数のｉｎｏｄｅが格納されているか否かを判断するステップと、
前記コンピューティングファイルシステムにおいて、新たなｉｎｏｄｅを割り当てる場合に、前記判断するステップにより、前記第１のｉｎｏｄｅテーブルに、前記予め定められた数のｉｎｏｄｅが格納されていると判断されたときは、前記コンピューティングファイルシステムにおいて、第２のｉｎｏｄｅテーブルを作成するステップと、
前記第１のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を含む第１のｉｎｏｄｅマップ、および、前記第２のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を含む第２のｉｎｏｄｅマップを作成するステップと
を実行させ、  
前記第１のｉｎｏｄｅマップは、前記第２のｉｎｏｄｅマップの位置情報を含む
コンピュータプログラム。
【請求項８】
前記第２のｉｎｏｄｅテーブルに、予め定められた数のｉｎｏｄｅが格納されている場合に、少なくとも１つの第３のｉｎｏｄｅテーブルを作成するステップと、
前記第３のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を含む第３のｉｎｏｄｅマップを作成するステップと
を前記コンピュータにさらに実行させ、
前記第２のｉｎｏｄｅマップは、前記第３のｉｎｏｄｅマップの位置情報をさらに含む
請求項７に記載のコンピュータプログラム。
【請求項９】
各前記ｉｎｏｄｅテーブルに格納されうるｉｎｏｄｅの数は、ディスク空間の総量と、各前記ｉｎｏｄｅマップで参照されるｉｎｏｄｅテーブルアドレスの個数との関数である
請求項８に記載のコンピュータプログラム。
【請求項１０】
ファイルシステムの作成中に、前記ｉｎｏｄｅの数を求めるステップ
を前記コンピュータにさらに実行させる
請求項９に記載のコンピュータプログラム。
【請求項１１】
予め定められた数のｉｎｏｄｅをそれぞれ格納しうる少なくとも第１のｉｎｏｄｅテーブルと、第２のｉｎｏｄｅテーブルとを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当て解除するコンピュータプログラムであって、
前記コンピューティングファイルシステムのコンピュータに、
前記第２のｉｎｏｄｅテーブルに、ｉｎｏｄｅが格納されているか否かを判断するステップと、
前記判断するステップにより、前記第２のｉｎｏｄｅテーブルにｉｎｏｄｅが格納されている場合以外は、前記第２のｉｎｏｄｅテーブルを削除するステップと、
前記第２のｉｎｏｄｅテーブルを削除した場合に、前記第１のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を少なくとも含む第１のｉｎｏｄｅマップから、前記第２のｉｎｏｄｅテーブルのディスクブロックアドレスの一覧を少なくとも含む第２のｉｎｏｄｅマップの位置情報を削除するステップと
を実行させるコンピュータプログラム。
【請求項１２】
前記第２のｉｎｏｄｅテーブルを削除した場合に、前記第２のｉｎｏｄｅテーブルに対応する前記第２のｉｎｏｄｅマップを削除するステップ
を前記コンピュータにさらに実行させる請求項１１に記載のコンピュータプログラム。
【請求項１３】
請求項７に記載のコンピュータプログラムを記憶したコンピュータ可読媒体。
【請求項１４】
請求項１１に記載のコンピュータプログラムを記憶したコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、ｉｎｏｄｅの割り当ておよび割り当て解除の方法およびコンピュータプログラムに関する。
【背景技術】
【０００２】
ｉｎｏｄｅは、ファイル、ディレクトリ、又は他のファイルシステムオブジェクトについての基本的なメタデータを記憶するために、多くのファイルシステムによって利用されるデータ構造である。ｉｎｏｄｅを利用するファイルシステムの例には、数ある中でも、ＵＮＩＸ（登録商標）ファイルシステム（ＵＦＳ）、Ｖｅｒｉｔａｓファイルシステム（ＶｘＦＳ）、及びＥＸＴ２ファイルシステムが含まれる。
【０００３】
ｉｎｏｄｅは、ファイルシステム作成中にｉｎｏｄｅテーブルで事前に割り当てられると共に、事前に初期化される。ファイルシステムは、ファイルシステムパーティションのサイズ及び平均ファイルサイズを考慮するアルゴリズムを使用することによって、ｉｎｏｄｅテーブルに設けられるｉｎｏｄｅの個数を計算する。ファイルシステムは、次に、ディスク空間の連続ブロック（すなわち、ｉｎｏｄｅテーブル）の固定オフセットにｉｎｏｄｅを記憶する。この連続ブロックは、実際のデータを記憶するのに使用されるディスク空間の部分とは異なる。ＵＮＩＸ（登録商標）ファイルシステムでは、ｉｎｏｄｅ番号をオフセットとして直接使用してｉｎｏｄｅをフェッチすることを可能にするために、ｉｎｏｄｅはｉｎｏｄｅテーブルに連続した順序で記憶される。すなわち、ｉｎｏｄｅ番号は、ｉｎｏｄｅのディスクブロックアドレス（すなわち、ｉｎｏｄｅテーブルにおけるｉｎｏｄｅのロケーション）へ直接マッピングされる。
【０００４】
ファイルシステムが作成されると、ｉｎｏｄｅテーブルにおけるｉｎｏｄｅの個数は増加させることも減少させることもできない。すなわち、ｉｎｏｄｅテーブルは固定される。ファイルシステムは多くの場合、ｉｎｏｄｅテーブルにおける利用可能なすべてのｉｎｏｄｅを最終的には利用し得る多くの小さなファイルを記憶するようにプログラミングされたアプリケーションを含み、それによって、たとえ利用可能なディスク空間が存在しても、他のアプリケーションがさらなるファイルを記憶することを防止する。代替形態では、ファイルシステムは過剰なｉｎｏｄｅを事前に割り当てる場合があり、その結果、ファイルシステムは、ファイルシステムの作成中に不要な処理オペレーションを実行する。これは特に、ファイルシステムが少数の大きなファイルを記憶する常駐アプリケーションを有する場合である。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、ｉｎｏｄｅの割り当ておよび割り当て解除のための方法およびプログラムなどを提供する。
【課題を解決するための手段】
【０００６】
本発明の一形態は、第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当てる方法であって、前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かを判断するステップと、前記第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるとの判断に応答して、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルを作成するステップとを含む方法である。
【０００７】
次に、本発明をより明確に確認することができるようにするために、例として、添付図面を参照して実施形態を説明する。
【発明を実施するための最良の形態】
【０００８】
コンピューティングファイルシステムでｉｎｏｄｅの割り当て及び割り当て解除を行う方法及びコンピュータプログラムが提供される。
【０００９】
一実施形態では、ｉｎｏｄｅを割り当てる方法は、コンピューティングファイルシステムに設けられた第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化されているか否かを判断するステップと、第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化されているとの判断に応じて、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルを作成するステップとを含む。
【００１０】
別の実施形態では、コンピューティングシステムのコンピュータ可読媒体上で実施されると、上述したｉｎｏｄｅ割り当て方法ステップをコンピューティングシステムに実施させる少なくとも１つの命令を含むコンピュータプログラムが提供される。
【００１１】
別の実施形態では、少なくとも第１のｉｎｏｄｅテーブル及びさらなるｉｎｏｄｅテーブルを含むコンピューティングファイルシステムにおいてｉｎｏｄｅを割り当て解除する方法であって、さらなるｉｎｏｄｅテーブルが、初期化されたｉｎｏｄｅを含まないかを判断するステップと、さらなるテーブルが初期化されたｉｎｏｄｅを含まないと判断されたことに応答して、さらなるｉｎｏｄｅテーブルを削除するステップとを含む方法が提供される。
【００１２】
別の実施形態では、コンピューティングシステムのコンピュータ可読媒体上で実施されると、上述したｉｎｏｄｅ割り当て解除方法ステップをコンピューティングシステムに実施させる少なくとも１つの命令を含むコンピュータプログラムが提供される。
【００１３】
本明細書の文脈において、「ｉｎｏｄｅテーブル」という語句は、その範囲内に、任意の適したディスク空間に記憶することができ、初期化又は初期化解除（de-initialize）のいずれかを行うことができる少なくとも１つのｉｎｏｄｅを含む任意のテーブルを含む。
【００１４】
また、図１に示すクライアント−サーバコンピューティングシステム１００等のコンピューティングシステムも提供される。このクライアント−サーバコンピューティングシステム１００は、上述した方法を実施するように構成されている。一実施形態では、クライアント−サーバコンピューティングシステム１００は、インターネットの形態のネットワーク１０６を介してクライアント１０４に接続されているサーバ１０２を備える。クライアント１０４は、サーバ１０２と通信する標準的なハードウェア及びソフトウェアを備えるパーソナルコンピューティングデバイス１０４ａ、１０４ｂの形態を有する。クライアント１０４は、伝送制御プロトコル／インターネットプロトコル（ＴＣＰ／ＩＰ）のプロトコルスイートを使用してサーバ１０２と通信する。ストレージデバイス１０８もネットワーク１０６に接続されている。
【００１５】
図２を参照すると、サーバ１０２のハードウェア及びソフトウェアのブロック図が示されている。サーバ１０２は、説明する実施形態によれば、Hewlett Packard社から入手可能なＨＰ−ＵＸ  ｒｘ５６７０サーバの形態を有する。サーバ１０２は、ＵＮＩＸ（登録商標）スタックを有するＵＮＩＸ（登録商標）オペレーティングシステムの形態のオペレーティングシステムを実行する。この実施形態では、サーバ１０２はＵＮＩＸ（登録商標）オペレーティングシステムを実施するが、他の実施形態は、たとえばＬＩＮＵＸオペレーティングシステム等の異なるオペレーティングシステムを含むことができることに留意すべきである。
【００１６】
ＵＮＩＸ（登録商標）オペレーティングシステムは、Ｕｎｉｘ（登録商標）ファイルシステム（ＵＦＳ）の形態のファイルシステムも含む。ＵＦＳは、シリンダグループの集まりから成り、ネットワーク１０６とハードディスク１２２との間のデータの転送を制御するソフトウェアを含む。メモリ１１８の一部から成るバッファキャッシュは、このデータ転送用のバッファとして使用される。また、バッファキャッシュは、頻繁に起こる待ち時間の大きなディスクＩ／Ｏを削減する目的でディスクブロックのコンテンツを保持するようにも構成されている。
【００１７】
サーバ１０２はさらに、システムバス１１４に結合されるクアドＩｎｔｅｌ  Ｉｔａｎｉｕｍ  ２プロセッサ１１２ａ、１１２ｂ（米国のIntel社から入手可能、http://www.intel.com/）の形態の複数のプロセッサ１１２も含む。メモリコントローラ／キャッシュ１１６もシステムバス１１４に結合され、ダブルデータレートＤＤＲ  ＳＤＲＡＭの形態を有するメモリ１１８をインターフェースするように構成されている。また、Ｉ／Ｏバス１２６経由でＩ／Ｏバスブリッジ１２４に接続されている、高速グラフィックアドレス指定をハンドリングするグラフィックスアダプタ１２０及びＡＴＡギガバイトハードディスク１２２も設けられている。メモリコントローラ１１６及びＩ／Ｏバスブリッジは、図２に示すように相互接続することができる。
【００１８】
Ｉ／Ｏバス１２６には、ＰＣＩバス１３０ａ、１３０ｂ、１３０ｃを介してサーバ１０２に接続されるデバイスへのインターフェースを提供するＰＣＩバスブリッジ１２８ａ、１２８ｂ、１２８ｃが接続されている。モデム１３２及びネットワークアダプタ１３４は、ＰＣＩバス１３０ａに結合されている。ネットワークアダプタ１３４は、サーバ１０２がＴＣＰ／ＩＰプロトコルを使用してクライアント１０４とデータを交換することを可能にするように構成されている。当業者によって認識されるように、ＣＤ−ＲＯＭ等の追加のＩ／Ｏデバイスも、Ｉ／Ｏバス１３０ａ、１３０ｂ、１３０ｃを介してサーバ１０２に結合することができる。
【００１９】
上述したように、ＵＦＳは、サーバ１０２のハードディスク１２２を複数のシリンダグループに分割する。従来のＵＦＳディスクレイアウトでは、各シリンダグループは、ファイルシステムスーパーブロックのバックアップコピーと、グループヘッダ（統計値、フリーリスト、及びそのシリンダグループを記述する他の情報を含む）と、一定の個数の事前に割り当てられると共に事前に初期化されているｉｎｏｄｅを含むｉｎｏｄｅテーブルとから成る。ｉｎｏｄｅテーブルのサイズは、ファイルシステム作成中（すなわち、コマンドｍｋｆｓがＵＦＳオペレーティングシステムで起動された時）に、ファイルパーティションのサイズ及び平均ファイルサイズに基づいて計算される。従来のシリンダディスクレイアウトを図３に示す。
【００２０】
本発明の実施形態は、ファイルシステムによる要求に応じて、（通常は、別のｉｎｏｄｅテーブル又は追加のｉｎｏｄｅテーブルと呼ばれるブロックで）追加のｉｎｏｄｅを割り当てる動的なｉｎｏｄｅ割り当て方法を利用する。追加のｉｎｏｄｅは、初期ファイルシステム作成後に割り当てることができるので、最初に割り当てられるｉｎｏｄｅの個数は、従来のファイルシステムによって必要とされるものよりも大幅に少なくすることができる。この方法論は、ファイルシステムが、現在割り当てられているｉｎｏｄｅの個数をもはや必要としない場合に、ｉｎｏｄｅを割り当て解除することもできる。
【００２１】
次に、図４のフロー図を参照して、第１のｉｎｏｄｅテーブルを含むコンピューティングファイルシステムのｉｎｏｄｅ割り当て方法を本発明の一実施形態に従って説明する。説明する実施形態では、第１のｉｎｏｄｅテーブルはファイルシステムを作成する時に作成され、第１のｉｎｏｄｅテーブルのｉｎｏｄｅは常駐アプリケーションによる要求に応じて初期化される。ステップ４０２において、第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みであるか否かについての判断が行われる。ステップ４０４において、ファイルシステムによって必要とされるｉｎｏｄｅの個数が第１のｉｎｏｄｅテーブルの容量を超えている（すなわち、第１のｉｎｏｄｅテーブルのすべてのｉｎｏｄｅが初期化済みである）と判断された場合には、追加のｉｎｏｄｅを割り当てるさらなるｉｎｏｄｅテーブルが作成される。後続の段落でより詳細に説明するように、利用可能なディスク空間の量にのみ応じて、任意の個数のさらなるｉｎｏｄｅテーブル／追加のｉｎｏｄｅテーブルをこの方法で作成でき、任意の適したディスクロケーションに記憶することができることが容易に理解されよう。
【００２２】
常駐アプリケーションが所望のｉｎｏｄｅを突き止めることを可能にするために、ステップ４０６において、ｉｎｏｄｅマップの形態のデータ構造（以下、「alloc_map」と呼ぶ）が作成される。alloc_mapは、実質的には、連続したｉｎｏｄｅテーブル（以下、「inode_chunk（ｉｎｏｄｅチャンク）」）を指し示すディスクブロックアドレスのアレイである。図６は、alloc_mapの一般的な構造を示している。図示するように、alloc_mapのｎ番目のエントリーは、（ｎ×inodechunksize）〜（（（ｎ＋１）×inodechunksize）−１）の番号が付けられたｉｎｏｄｅを含むinode_chunkを指し示す。一方、マップを１つだけ使用すると、ｉｎｏｄｅは（allocmapsize）×（inodechunksize）に制限される。したがって、必要な場合に、割り当てられたすべてのｉｎｏｄｅを参照するために、さらなるalloc_mapを作成することができる。拡張されたallloc_map又はinode_chunkに必要なディスク空間は、ファイルシステムによって事前に確保しておく必要はない。
【００２３】
図５は、上述した方法をより詳細に示している。簡単にするために、図５を参照して説明する方法論は、各alloc_mapが４つのinode_chunkのディスクアドレスを指し示すように構成されることを提供する。ファイルシステムの作成中に、第１のalloc_map５０２及び第１のinode_chunk５０４のみが割り当てられる。図示するように、alloc_map５０２の最初のエントリーは第１のinode_chunk５０４を指し示す。ｉｎｏｄｅの個数が、第１のinode_chunk５０４の容量を超えると、さらなるinode_chunk５０６が割り当てられる。同様に、alloc_map５０２の容量を超えると（ここでは、さらなるinode_chunk５１０が割り当てられると）、新しいalloc_map５０８が割り当てられ、前のalloc_map５０２にリンクされる。
【００２４】
上記で概説した方法論を使用してｉｎｏｄｅを取り出すのに使用することができる擬似コンピュータプログラマブルコードの一例を以下に提供する。
IGET (inode_number) ：ｉｎｏｄｅを返す
{
inode_chunk_number = inode_number / chunksize
alloc_map_number = inode_chunk_number / allocmapsize
if (alloc_map_numberに対応するalloc_mapが存在しない)
{
＊サイズallocmapsizeの新しいalloc_mapを割り当てる
＊alloc_mapのエントリーを適切に初期化する
＊このalloc_mapを前のalloc_map及び次のalloc_mapにリンクする
}
if (inode_chunk_numberに対応するinode_chunkが存在しない)
{
＊サイズchunksizeのinode_chunkを割り当てる
＊alloc_mapの（inode_chunk_number % allocmapsize）番目のエントリーを、このinode_chunkの開始アドレスに初期化する
}
＊オフセット（inode_chunk_number % allocmapsize）におけるalloc_mapからinode_chunkの開始アドレスを得る
＊オフセット（inode_number % chunksize）におけるinode_chunkから、必要とされるｉｎｏｄｅをフェッチし、このｉｎｏｄｅを返す
}
【００２５】
以下の式１は、上述した方法を使用してｉｎｏｄｅをフェッチするための全時間を求めるのに使用される。示すように、このデータは、その後、最も適切なinode_chunk及びalloc_mapサイズを確立するためにファイルシステムにより利用することができる。
Ｔ＝Ｔｃａ＋Ｔｃｉ＋Ｔｓａ＋Ｔａａ＋Ｔｉａ＋Ｔｓｉｃ＋Ｔａｉ＋Ｔｉｉ＋Ｔｓｉ
（式１）
式中、
Ｔｃａ＝alloc_map数を計算するための時間
Ｔｃｉ＝inode_chunk数を計算するための時間
Ｔｓａ＝必要とされるalloc_mapを検索してフェッチするための時間
Ｔａａ＝新しいalloc_mapを割り当てるための時間
Ｔｉａ＝alloc_mapを初期化するための時間
Ｔｓｉｃ＝必要とされるinode_mapを検索してフェッチするための時間
Ｔａｉ＝新しいinode_chunkを割り当てるための時間
Ｔｉｉ＝inode_chunkを初期化するための時間
Ｔｓｉ＝inode_chunkから、必要とされるｉｎｏｄｅを検索してフェッチするための時間
【００２６】
式１において、Ｔｃａ及びＴｃｉは共に一定時間であり（すなわち、ディスクアクセスを必要としない）、したがって、Ｋｃａ及びＫｃｉによってそれぞれ表すことができる。また、（alloc_map及びinode_chunkについての）新しいディスクブロックの割り当て及び初期化は、スーパーブロックを更新するためにそれぞれ１回しかディスクアクセスを必要としない（これは、スーパーブロックの「インメモリ」コピーのみを変更することによって回避することもできる）。したがって、これらの時間（すなわち、Ｔａａ、Ｔｉａ、Ｔａｉ、及びＴｉｉ）は、定数Ｋａａ、Ｋｉａ、Ｋａｉ、及びＫｉｉによってそれぞれ表すことができる。alloc_mapを検索するステップはalloc_mapの個数に正比例する。ｎをファイルシステムにおけるalloc_mapの個数とすると、alloc_mapを検索するプロセスはｎ回のディスクアクセスを必要とする。すなわち、Ｔｓａ＝ｎ×Ｋｓａである。ここで、Ｋｓａは、１つのalloc_mapをフェッチするのに必要な時間を表す定数である。次に、Ｔｓｉｃ及びＴｓｉも（アルゴリズムで示されるように）一定時間のオペレーションである。これらをＫｓｉｃ及びＫｓｉによってそれぞれ表すものとする。
【００２７】
したがって、アルゴリズムによって必要とされる全時間は、
Ｔ＝（Ｔｃａ＋Ｔｃｉ）＋（Ｔｓｉｃ＋Ｔｓｉ）＋（Ｔａａ＋Ｔｉａ＋Ｔａｉ＋Ｔｉｉ）＋Ｔｓａ
＝Ｋ＋ｎ×Ｋｓａ（簡単にするためにすべての定数の合計をＫによって置き換える）
となる。
【００２８】
したがって、このアルゴリズムの時間計算量は、
Ｏ（Ｔ）＝Ｏ（Ｋ）＋Ｏ（ｎ×Ｋｓａ）
近似値＝Ｏ（ｎ）  （Ｋ及びＫｓａは定数であるので）
となる。
【００２９】
すなわち、本明細書で説明したアルゴリズムの性能オーバーヘッドは、alloc_mapの個数に関する一次方程式である。性能は、ｎの値が非常に大きい場合（＞１００）には劣化する可能性があるが、alloc_map及びinode_chunkの双方のサイズ（ファイルシステムの作成時に設定される）は、アルゴリズムの性能に対する影響を回避するために、ファイルシステムサイズの関数として計算される。一般に、alloc_mapの個数（ｎ）は、４を超える必要はない。
【００３０】
たとえば、１テラバイトのサイズのファイルシステムを考え、alloc_mapのサイズを１メガバイトと考え、inode_chunkのサイズを５１２キロバイトと考える。８バイトのアドレスを仮定すると、単一のalloc_mapは、２１７個のinode_chunkのアドレスを保持することができる。たとえinode_chunkが、５１２個のｉｎｏｄｅしか保持することができなくても、（２１７）×（２９）＝（２２６）個のｉｎｏｄｅをハンドリングするのに、単一のalloc_mapで十分である。したがって、４つのalloc_map（２２８）を使用することによって、２６８４３５４５６個のｉｎｏｄｅが提供される。これは、ほとんどの実際のシナリオにとって十分な大きさである。
【００３１】
本明細書で説明した実施形態は、ｉｎｏｄｅテーブルの割り当ての方法を説明しているが、この方法は、複数のｉｎｏｄｅテーブル（すなわち、第１のｉｎｏｄｅテーブル及びさらなるｉｎｏｄｅテーブル又は追加のｉｎｏｄｅテーブル）を含むコンピューティングファイルシステムにおいて、ｉｎｏｄｅ及びｉｎｏｄｅテーブルの割り当て解除（又は削除）も同様にすることができることに留意されたい。ファイルシステムのファイルが削除されると、対応するｉｎｏｄｅはｉｎｏｄｅ初期化解除コードによって初期化解除され、それによって、別のファイルがそのｉｎｏｄｅを使用することが可能になる。初期化解除されているｉｎｏｄｅが関連付けられたｉｎｏｄｅテーブルに残っている最後のｉｎｏｄｅであるとｉｎｏｄｅ初期化解除コードが判断した場合には、そのコードパスは、ｉｎｏｄｅテーブル全体を割り当て解除（すなわち、削除）し、それに従って、関連付けられたｉｎｏｄｅマップを更新する。
【００３２】
割り当て方法及び割り当て解除方法の実施形態は、コンピューティングシステムのコンピュータ可読媒体上で実施されると上述した方法ステップをコンピューティングシステムに実施させる命令を含むコンピュータプログラム（ハードウェア、ソフトウェア、又はこの２つの組み合わせのいずれかによる）によって実施することができる。
【００３３】
必須ではないが、このコンピュータプログラムは、開発者による使用のために、アプリケーションプログラミングインターフェース（ＡＰＩ）を介して実施される場合があり、別のソフトウェアアプリケーション内のコードで実施することができる。一般に、ソフトウェアアプリケーションは、特定の機能を実行するか又は特定の機能の実行を助けるルーチン、プログラム、オブジェクト、コンポーネント、及びデータファイルを含むので、ソフトウェアアプリケーションを、複数のルーチン、オブジェクト、及びコンポーネントにわたって分散させることができるが、実施形態及び本明細書で権利を主張するより広い発明と同じ機能を達成することができることが理解されよう。このような変形及び変更は、当業者の理解の範囲内にあるであろう。
【００３４】
サーバに設けられたハードウェアは実施態様に応じて変化し得ることが、当業者には認識されよう。図１及び図２に示すハードウェアに加えて又はこれに代えて、他の内部ハードウェアも使用することができる。たとえば、追加のメモリコントローラ、ハードディスク、テープストレージデバイス等を含むことができる。
【００３５】
さらに、当業者には、スタンドアロンコンピューティングデバイス又は分散ネットワーク接続構成でも本発明を実施することができることが理解されよう。たとえば、本発明は、クライアントコンピューティングデバイス、サーバコンピューティングデバイス、パーソナルコンピューティングデバイス等で、単独又は組み合わせで実施することができる。
【００３６】
例示的な実施形態の上記説明は、どの当業者も本発明の製作又は使用することができるように提供されている。本発明は、特定の図示した実施形態に関して説明されてきたが、これらの実施形態に対するさまざまな変形は、当業者には容易に明らかであり、本明細書で定義される包括的な原理は、本発明の趣旨又は範囲から逸脱することなく他の実施形態にも適用することができる。したがって、本実施形態は、すべての点で、制限ではなく例示とみなされることが望まれている。したがって、本発明は、上述した実施形態に限定されるように意図されておらず、本明細書で開示した原理及び新規な機能と一致するより広い範囲を与えられている。
【図面の簡単な説明】
【００３７】
【図１】本発明の一実施形態によるコンピューティングシステムの概略図である。
【図２】本発明の実施形態を実施することができるサーバのブロック図である。
【図３】第１のシリンダグループの従来のＵＮＩＸ（登録商標）ファイルシステムのディスクレイアウトを示すブロック図である。
【図４】本発明の一実施形態による、ｉｎｏｄｅを割り当てる方法を示すフロー図である。
【図５】本発明の一実施形態による、図２に示すサーバのハードディスクにおけるｉｎｏｄｅの割り当てを示すブロック図である。
【図６】本発明によるｉｎｏｄｅマップの概略図である。
【符号の説明】
【００３８】
１００・・・クライアント−サーバコンピューティングシステム
１０２・・・サーバ
１０４・・・クライアント
１０４ａ、１０４ｂ・・・パーソナルコンピューティングデバイス
１０６・・・ネットワーク
１０８・・・ストレージデバイス
１１２ａ、１１２ｂ・・・プロセッサ
１１４・・・システムバス
１１６・・・メモリコントローラ／キャッシュ
１１８・・・メモリ
１２０・・・グラフィックスアダプタ
１２２・・・ディスク
１２４・・・Ｉ／Ｏブリッジ
１２６・・・Ｉ／Ｏバス
１２８ａ〜１２８ｃ・・・ＰＣＩバスブリッジ
１３０ａ〜１３０ｃ・・・ＰＣＩバス
１３２・・・モデム
１３４・・・ネットワークアダプタ
５０２、５０８・・・alloc_map
５０４、５０６、５１０・・・inode_chunk
【図１】
0004907605.tif 000002
【図２】
0004907605.tif 000003
【図３】
0004907605.tif 000004
【図４】
0004907605.tif 000005
【図５】
0004907605.tif 000006
【図６】
0004907605.tif 000007