(57)【要約】      （修正有）【課題】データおよびメタデータの両方を流れのグループとして記憶する方法を提供する。【解決手段】データを可変サイズの第１の流れデータ構造に記憶し、メタデータ（６８、７０、７２、７３）を可変サイズの第２の流れデータ構造（６６）に記憶する。メタデータはデータの記憶を記述し、第１の識別子を介してデータを位置決めするためのエントリを有する。第２の可変サイズの流れデータ構造は第２の識別子（７０、ワークＩＤ  ０）を有し、第２の識別子（７０、ワークＩＤ  ０）は、該第２の識別子（７０、ワークＩＤ  ０）を介して前記メタデータを位置決めするために予め定められる。【選択図】図１１
2007128543.tif 000002
【特許請求の範囲】
【請求項１】
ディスク記憶装置（１６）およびオペレーティングシステム（２４）を実行する情報処理手段（１２）を有するデータ処理システム（１０）における前記ディスク記憶装置（１６）にデータを記憶するための方法であって、
ａ）前記ディスク記憶装置（１６）に、論理的に隣接するデータバイトを保持するための可変サイズの第１の流れデータ構造（６０）に、データを記憶するステップと、
なお、ここで前記第１の流れデータ構造（６０）は第１の識別子（６２）を有し、
ｂ）前記ディスク記憶装置（１６）に、メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）を論理的なデータバイトを保持するための可変サイズの第２の流れデータ構造（６６、１１０）に記憶するステップと、
なお、ここで前記メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）は前記データの記憶を記述し、前記第１の識別子（６２）を介して前記データを位置決めするためのエントリ（６２）を有し、前記第２の可変サイズの流れデータ構造（６８、１１０）は第２の識別子（７０、ワークＩＤ  ０）を有し、該第２の識別子（７０、ワークＩＤ  ０）は、該第２の識別子（７０、ワークＩＤ  ０）を介して前記メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）を位置決めするために予め定められており、
ｃ）前記流れデータ構造（６０、６６、１１０）の各々について、記述の識別子（３４）を含む予め定められたフォーマットの流れ記述子（２８）を記憶するステップと
なお、ここで、前記記述の識別子（３４）は、
それにより前記データおよび前記メタデータが前記記述の識別子（３４）を使用することによりアクセス可能となる対応の流れデータ構造（６０、６８、１１０）の記述と
前記ディスク記憶装置（１６）中の流れデータ構造（６０、６６、１１０）のタイプを規定し、その結果前記データおよび前記メタデータが類似の形態で記述されるタイプ識別子（３２）と
を保持し、
を有することを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）を記憶するステップは、さらに、
関連データ（８６、８８、９０、９２、９４、９６、９８、１００）を保持する第３の流れデータ構造（６０；７８、８０、８２、８４）に対するインデックス（１１７）を記憶するステップ
を有することを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記インデックス（１１７）を記憶するステップは、さらに、
前記第３の流れデータ構造（６０；７８、８０、８２、８４）に対するＢツリーインデックスを記憶するステップを
有することを特徴とする方法。
【請求項４】
請求項１乃至３のいずれかに記載の方法において、前記流れデータ構造（６０、６６、１１０）の各々について、前記流れ記述子（２８）を記憶するステップは、さらに、
前記可変サイズの第１および第２の流れデータ構造（６０、６６、１１０）中に前記流れデータ構造（６０、６６、１１０）の各々について、前記流れ記述子（２８）を記憶するステップ
を有することを特徴とする方法。
【請求項５】
請求項１乃至４のいずれかに記載の方法において、前記可変サイズの第１の流れデータ構造（６０）で前記データを記憶するステップは、
論理的に隣接するバイトのデータを有する第４の流れデータ構造（３４；３６、４２）で、前記ディスク記憶装置（１６）に１つのデータの流れを記憶するステップと、
前記第４の流れデータ構造（３４；３６、４２）についての流れ記述子（２８）を前記ディスク記憶装置に記憶するステップと
を有することを特徴とする方法。
【請求項６】
請求項５に記載の方法において、前記第４の流れデータ構造（３４；３６、４２）についての流れ記述子（２８）を記憶するステップは、さらに、
別の流れデータ構造（６０）で、前記第４の流れデータ構造（３４；３６、４２）についての流れ記述子（２８）を記憶するステップ
を有することを特徴とする方法。
【請求項７】
請求項１乃至６のいずれかに記載の方法において、さらに、
ファイルのデータおよびそれらに関連する流れ記述子を前記可変サイズの第２の流れデータ構造（６６、１１０）中で記憶する複数の流れデータ構造（３４；３６、４２）を前記ディスク記憶装置（１６）に記憶するステップ
を有することを特徴とする方法。
【請求項８】
請求項１乃至６のいずれかに記載の方法において、さらに、
ディレクトリのデータおよびそれらに関連する流れ記述子（２８）を前記可変サイズの第２の流れデータ構造（６６、１１０）中で記憶する複数の流れデータ構造（３４；３６、４２）を前記ディスク記憶装置（１６）に記憶するステップ
を有することを特徴とする方法。
【請求項９】
請求項１乃至６のいずれかに記載の方法において、さらに、
サブディレクトリおよびそれらに関連する流れ記述子を前記可変サイズの第２の流れデータ構造（６６、１１０）中で記憶する複数の流れデータ構造（３４；３６、４２）を前記ディスク記憶装置（１６）に記憶するステップ
を有することを特徴とする方法。
【請求項１０】
請求項１乃至９のいずれかに記載の方法において、さらに、
関連のデータを記憶する可変サイズの流れデータ構造（６６、１１０）のグループをカタログデータ構造（１１０）中に記憶するステップ
有することを特徴とする方法。
【請求項１１】
請求項１乃至１０のいずれかに記載の方法において、さらに、
前記可変サイズの第２の流れデータ構造（６６、１１０）中には記憶されず、関連データ（８６、８８、９０、９２、９４、９６、９８、１００）を記憶する流れデータ構造（７８、８０、８２、８４）および
その関連流れ記述子（２８）を
前記ディスク記憶装置（１６）中の可変サイズの第５の流れデータ構造（６６）に記憶するステップを有することを特徴とする方法。
【請求項１２】
請求項１１に記載の方法において、さらに、
前記可変サイズの第２の流れデータ構造および前記可変サイズの第５の流れデータ構造を、前記ディスク記憶装置（１６）中のディスクスペースの固定サイズのバケット(バケット１〜Ｎ)のアレイ（１０２）に記憶するステップ
を有することを特徴とする方法。
【請求項１３】
請求項１２に記載の方法において、さらに、
前記アレイ（１０２）を第６の流れデータ構造（１１０）に記憶するステップ
を有することを特徴とする方法。
【請求項１４】
請求項１３に記載の方法において、第６の流れデータ構造についての流れ記述子（２８）を、関連データを記憶する可変サイズの複数のデータ構造（１１０）の１つに記憶することを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、固定サイズの複数のバケット（バケット１〜Ｎ）のアレイ（１０２）の中の予め定められた固定サイズのバケットに前記カタログデータ構造を記憶することを特徴とする方法。
【請求項１６】
請求項１乃至１５のいずれかに記載の方法において、さらに、
可変サイズの流れデータ構造（６６、１１０）を前記ディスク記憶装置（１６）のディスクスペースの固定サイズの複数のバケット（バケット１〜Ｎ）のアレイ（１０２）に記憶するステップと、
の、ここで、各バケットバケット（バケット１〜Ｎ）は関連の識別子を有しており、
前記アレイ（１０２）内の１つのバケット（バケット１〜Ｎ）についてのバケット識別子を示すエントリー（１０６、１０８）を保持するマッピング構造（１０４）を記憶するステップと、
なお、ここで、前記エントリー（１０６、１０８）は前記可変サイズの流れデータ構造（６６、１１０）の識別子（７０）により示され、
前記マッピング構造（１０４）を使用して、その識別子（７０）が与えられる、前記アレイ（１０２）中の前記可変サイズの流れデータ構造（６６、１１０）の１つを位置決めするステップと
を有することを特徴とする方法。
【請求項１７】
請求項１６に記載の方法において、前記アレイ（１０２）は前記ディスク記憶装置（１６）内の前記複数の流れデータ構造（１１０）の１つに記憶され、前記アレイを記憶する流れについての流れ記述子（２８）は、前記ディスク記憶装置（１６）内に記憶されることを特徴とする方法。
【請求項１８】
請求項１６または１７に記載の方法において、前記マッピング構造（１０４）はディスク記憶装置（１６）内の複数の流れデータ構造（１１０）の１つに記憶され、前記マッピング構造を記憶する流れ記述子（２８）はディスク記憶装置（１６）内に記憶されることを特徴とする方法。
【請求項１９】
請求項１８に記載の方法において、前記アレイ（１０２）を記憶する流れについての流れ記述子（２８）および前記マッピング構造を記憶する流れ記述子（２８）は複数の前記可変サイズの流れデータ構造（６６、１１０）の中の選択された１つに記憶されることを特徴とする方法。
【請求項２０】
請求項１９に記載の方法において、選択された前記流れデータ構造は前記アレイ（１０２）の複数のバケット（バケット１〜Ｎ）の１つに記憶されることを特徴とする方法。
【請求項２１】
請求項１乃至２０のいずれかに記載の方法において、前記タイプ識別子（３２）が小規模のトランザクションを示す場合には、特定の流れ記述子（２８）の記述フィールド（３４）は関連の流れデータ構造を記憶することを特徴とする方法。
【請求項２２】
請求項１乃至２１のいずれかに記載の方法において、流れデータ構造がイクステント（４２）に記憶されている場合にはことを前記タイプ識別子（３２）が示している場合には、前記特定の流れ記述子（２８）の記述フィールドは関連の流れデータ構造を記憶するイクステント（４２）に対する参照（３６）を記憶することを特徴とする方法。
【請求項２３】
ディスク記憶装置（１６）と、
前記ディスク記憶装置（１６）に、論理的に隣接するデータバイトを保持するための可変サイズの第１の流れデータ構造（６０）に、データを記憶する手段（１２）と、
なお、ここで前記第１の流れデータ構造（６０）は第１の識別子（６２）を有し、
前記ディスク記憶装置（１６）に、メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）を論理的なデータバイトを保持するための可変サイズの第２の流れデータ構造（６６、１１０）に記憶する手段（１２）と、
なお、ここで前記メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）は前記データの記憶を記述し、前記第１の識別子（６２）を介して前記データを位置決めするためのエントリ（６２）を有し、前記第２の可変サイズの流れデータ構造（６８、１１０）は第２の識別子（７０、ワークＩＤ  ０）を有し、該第２の識別子（７０、ワークＩＤ  ０）は、該第２の識別子（７０、ワークＩＤ  ０）を介して前記メタデータ（６８、７０、７２、７３、１０２、１０５、１１２、１１４、１１６、１１７）を位置決めするために予め定められており、
前記流れデータ構造（６０、６６、１１０）の各々について、記述の識別子（３４）を含む予め定められたフォーマットの流れ記述子（２８）を記憶する手段（１２）と
なお、ここで、前記記述の識別子（３４）は、
それにより前記データおよび前記メタデータが前記記述の識別子（３４）を使用することによりアクセス可能となる対応の流れデータ構造（６０、６８、１１０）の記述と
前記ディスク記憶装置（１６）中の流れデータ構造（６０、６６、１１０）のタイプを規定し、それにより前記データおよび前記メタデータタイプ識別子（３２）が類似の形態で記述されるタイプ識別子（３２）と
を保持し、
を有することを特徴とするデータ処理システム。
【請求項２４】
データ処理システム（１０）に請求項１乃至２２に記載の方法を実行させるコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にデータ処理システムに係り、より詳細には、ファイルシステムによりディスクにデータを記憶する方法に係る。
【背景技術】
【０００２】
従来のファイルシステムは、ファイルデータをディスクに効率的に記憶する点で問題がある。従来の多くのシステムは、全てのデータをディスクに単一サイズの記憶単位で記憶する手法を採用している。不都合なことに、この手法は、ディスクにファイルデータを効率良く記憶するものではない。特に、ファイルデータはサイズが変化し、従って、所定の記憶単位サイズに良好に一致するものではない。従来の他のシステムは、多数の異なるフォーマットの１つを採用するオプションをユーザに与えるものである。ファイルデータがユーザに使用できるようになる前に、どのフォーマットを採用するか判断しなければならない。その結果、ユーザによるフォーマットの選択は単なる推測となり、実際のファイルデータとうまく対応しないことがしばしばある。従って、ファイルデータが効率的に記憶されないことが頻繁である。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来のオペレーティングシステムでは、各ファイルに固定数のディスクスペースのブロックが割り当てられ、ファイルデータと、ファイルに関する制御情報を記憶する。これらのブロックは、単位を素早く割り当てたり割り当て解除したりできるように固定サイズにされている。ファイル及びファイルデータに対する制御情報は、しばしば可変サイズとされ、これが少なくとも２つの問題を課することになる。第１に、ファイルデータ及び／又は制御情報が１つのブロックを埋めるに充分なほど大きくないときには、割り当て単位内のディスクスペースが浪費される。第２に、ファイルデータ及び／又は制御情報が１つのブロックに記憶するには大き過ぎるときには、それが多数のブロックに記憶されねばならず、データがどこに記憶されるかを指定するために多数のポインタが維持されねばならない。このようなポインタを維持しそして使用することは、かなり厄介であることが多い。
【０００４】
従来のファイルシステムでは、データとメタデータ（即ち、他のデータの記憶を記述するデータ）とが個別のエントリーとして処理されている。特に、データとメタデータは、従来のファイルシステムでは異なるフォーマットで記憶されている。更に、データ及びメタデータに対して作用する個別のツールが設けられている。データとメタデータをこのように分けて考える結果、オーバーヘッド及び複雑さが増大している。
【課題を解決するための手段】
【０００５】
本発明の第１の特徴によれば、ディスク記憶装置と、オペレーティングシステムを実行する処理手段とを有するデータ処理システムにおける方法が実施される。この方法において、データは、ディスク記憶装置に、第１の可変サイズの流れデータ構造で記憶される。メタデータは、ディスク記憶装置に、第２の可変サイズの流れデータ構造で記憶される。各々の流れデータ構造に対して流れ記述子が記憶される。この流れ記述子は、流れデータ構造がディスク記憶装置内のディスクにいかに記憶されるかを識別するタイプ識別子を含んでいる。
【０００６】
本発明の別の特徴によれば、データの流れは、ディスク記憶装置に流れデータ構造で記憶される。データの流れは、論理的に隣接するデータバイトから形成される。各流れデータ構造に対しディスク記憶装置に流れ記述子が記憶される。各流れ記述子は、流れデータ構造がディスク記憶装置にいかに記憶されるかを記述するタイプ識別子を含んでいる。関連データを記憶する流れデータ構造は、それらに組み合わされた流れ記述子と共に、第１の可変サイズのデータ構造に記憶される。
【０００７】
本発明の更に別の特徴によれば、データの流れは、ディスク記憶装置に流れデータ構造で記憶される。各流れデータ構造ごとに流れ記述子がディスク記憶装置に記憶される。各流れ記述子は、流れデータ構造がディスク記憶装置にいかに記憶されるかを記述するタイプ識別子を含む。関連データを記憶する流れデータ構造は、それに組み合わされた流れ記述子と共に、ディスク記憶装置に可変サイズのデータ構造で記憶される。関連データを記憶する可変サイズのデータ構造のグループは、カタログデータ構造で記憶される。
【０００８】
本発明の更に別の特徴によれば、ディスク記憶装置を有するデータ処理システムにおける方法が実施される。この方法では、データの流れはディスク記憶装置に流れデータ構造で記憶される。流れは、論理的に隣接するデータバイトによって形成される。各流れデータ構造ごとに流れ記述子がディスク記憶装置に記憶される。関連データを記憶する流れデータ構造は、それらに組み合わされた流れ記述子と共に、ディスク記憶装置に各々可変サイズのデータ構造で記憶される。各可変サイズのデータ構造は、それに組み合わされた識別子を有している。可変サイズのデータ構造は、ディスク記憶装置におけるディスクスペースの固定サイズの識別可能なバケットのアレイに記憶される。このアレイ内のバケットに対するバケット識別子を指定するエントリーを保持するマッピング構造がディスク記憶装置に記憶される。上記エントリーは、可変サイズデータ構造の識別子によってインデックスされる。このマッピング構造は、その識別子が与えられると、上記アレイ内の可変サイズデータ構造の１つを位置決めするのに使用される。
【発明を実施するための最良の形態】
【０００９】
(実施例)
本発明の好ましい実施例は、データとメタデータの両方をディスクに「流れ」のグループとして記憶するファイルシステムを提供する。「流れ」とは、データのバイトの、論理的に隣接しランダムにアクセスできる可変サイズのアレイであって、ディスク上の論理記憶単位として働くものをいう。ファイルのデータへのほとんどのプログラムアクセスは、これらの流れによって行われる。各流れは、多数の異なる表示(representation)の１つのためにディスクに記憶される。異なる表示の各々は、流れの特定のサイズ及び使用に良く適したものである。従って、各流れは、そのサイズに最も良く適した表示形態のためにディスクに記憶される。
【００１０】
各流れには流れ記述子が組み合わされ、これはファイルシステムに制御構造において記憶される。流れ記述子は、流れにアクセスし、そして流れに関する情報を得るのに使用される。流れ記述子は、流れのデータを記憶し、表示するための記述を与える。関連データを保持するデータの流れは、オノード(onode)として知られているデータ構造へとカプセル化される。オノードとは、ファイル、ディレクトリ又はサブディレクトリにほぼ類似した可変サイズの構造である。関連オノードのグループは、次いで、オブジェクト記憶カタログ又はオブジェクト記憶として知られているデータ構造に記憶される。従って、データ及びメタデータ（オブジェクト記憶カタログのような）は、同様の形態でハイアラーキに記述され、これについては以下で詳細に説明する。
【００１１】
図１は、本発明の好ましい実施例によるデータ処理システム１０のブロック図である。図１のシステム１０は単一プロセッサシステムであるが、本発明は分散型システムのようなマルチプロセッサシステムでも実施できることが当業者に明らかであろう。データ処理システム１０は、中央処理ユニット（ＣＰＵ）１２と、メモリ１４と、ディスク記憶装置１６と、キーボード１８と、マウス２０と、ビデオディスプレイ２２とを備えている。ディスク記憶装置１６は、ハードディスク及び他の形式のディスク記憶装置を含む。キーボード１８、マウス２０及びビデオディスプレイ２２は、従来型の入力／出力装置である。
【００１２】
メモリ１４は、オペレーティングシステム２４のコピーを保持し、これはシステムに記憶されたファイルを管理するためのファイルシステムマネージャ２６を含んでいる。オペレーティングシステム２４は、オブジェクト指向のオペレーティングシステムである。ここに述べる本発明の好ましい実施例は、オペレーティングシステム２４の一部分として実施される。本発明の好ましい実施例は、オペレーティングシステム２４の一部分として説明するが、当業者であれば、本発明は、オペレーティングシステムとは別の他の形式のコードでも実施できることが明らかであろう。
【００１３】
上記したように、本発明の好ましい実施例においては、流れは、多数の異なる表示の際に得られる。流れについての異なる表示を理解するために、流れに対して与えられる流れ記述子のフォーマットを検討することが有用であろう。図２は、流れ記述子２８のフォーマットを示す図である。流れ記述子２８は、本発明の好ましい実施例で使用できる流れの異なる表示形態の各々を記述することができる。流れ記述子２８は、サイズフィールド３０、タイプフィールド３２及び記述フィールド３４の３つのフィールドを含んでいる。サイズフィールド３０は、流れのサイズをバイトで指定する値を保持する。タイプフィールド３２は、流れのタイプを指定し、そして記述フィールド３４は、流れの記述（即ち、記述フィールド３４の形式）を保持する。これらフィールド３０、３２及び３４に保持された値は、それに関連する流れの表示形態と共に変化する（以下で詳細に述べる）。
【００１４】
「極小の流れ」は、本発明の好ましい実施例に使用できる流れの第１の例である。この極小の流れは、記憶媒体（即ち、ディスク記憶装置１６のディスク）の割り当て単位に対して非常にサイズの小さいデータを記憶するのに使用されるものである。記憶媒体の「割り当て単位」とは、ファイルを記憶するために割り当てられるディスク記憶装置１６のディスクメモリスペースの基本単位を指す。例えば、ＦＡＴベースのファイルシステムでは、最小割り当て単位はディスクセクタである。不都合なことに、このセクタは、システム１０で形成される流れデータよりも相当に大きいことがしばしばある。図３は、極小の流れに対する流れ記述子２８のフォーマットを示している。サイズフィールド３０は流れのサイズを指定する値を保持し、そしてタイプフィールド３２は、流れが極小の流れであることを指定する。記述フィールド３４は、流れのデータを保持し、従って、流れのデータの即時表示を与える。この即時表示は、少量のデータを記憶するための非常に効率的な手段を形成する。特に、データは、流れ記述子に直接的に合体されて、容易に且つ速やかにアクセスできるようにされる。
【００１５】
本発明の好ましい実施例に使用できる別の例は、小さな流れである。「小さな流れ」とは、データの単一のイクステントで記憶される流れである。イクステントとは、割り当て単位の可変サイズの隣接した延びである。流れのデータは、流れ記述子に直接記憶するには大き過ぎるのでイクステントに記憶される。この小さな流れに対する流れ記述子２８のフォーマットが図４に示されている。タイプフィールド３２は、それに関連した流れが小さな流れであることを指定し、そして記述フィールド３４は、流れのデータが記憶されるイクステント４２を記述するイクステント記述子３６を保持する。イクステント４２は、ディスク記憶装置１６のディスクに記憶される。イクステント記述子３６は、２つのサブフィールド３８及び４０を含む。サブフィールド３８はイクステント４２の長さを指定する値を保持し、そしてサブフィールド４０は、イクステントのディスクアドレス（即ち、イクステントがディスクの論理アドレススペースのどこに位置しているか）を保持する。
【００１６】
本発明の好ましい実施例に使用できる第３の例は、「大きな流れ」である。この大きな流れは、多数のイクステントに記憶される流れである。この大きな流れは、多量のデータを有する流れを記憶するのに適している。図５は、このような大きな流れに対する流れ記述子２８のフォーマットを示している。タイプフィールド３２は、流れが大きな流れであることを指定する。記述フィールド３４は、イクステント記述子を保持する流れ４４を記述する第２の流れ記述子４３を保持する。この第２の流れ記述子４３は極小の流れを記述し、そしてイクステント記述子の流れ４４を保持する記述フィールド３４’を含んでいる。イクステント記述子３６’、３６”及び３６”’は、図４について述べたイクステント記述子３６と同じフォーマットを有する。その結果、単一の流れ３４’によって多数のイクステント４２’、４２”及び４２”’が記述される。イクステント記述子の数があまりに多過ぎる場合には、第２の流れ記述子４３は、極小の流れではなくて小さな流れを記述する。更に、イクステント記述子の数が小さな流れに対して多過ぎる場合には、第２の流れ記述子４３は、大きな流れを記述する。大きな流れは、一般に、ディスクスペースの大きな隣接ブロックが得られない場合に使用される。この大きな流れは、多量のデータをディスクに対して分散されたイクステントにおいて単一の流れとして容易に記憶するものである。その結果、大きな流れは、ディスクが更に細分化されそして流れが成長するときにも、良好にスケーリングされる。
【００１７】
流れのサイズが成長するときには、流れの効率的な記憶を容易にするために、流れの表示が流れ表示のハイアラーキを登るように促される。ハイアラーキは、極小の流れ、小さな流れ及び大きな流れを含む。流れは、極小の流れから小さな流れへそして大きな流れへと促進される。一般に、上記したように、流れに含まれたデータの量及び細分の量に基づいて流れに最も適した表示形態が選択される。
【００１８】
本発明の好ましい実施例に使用できる４つの基本的な流れの形式を以上に説明した。流れ記述子２８のタイプフィールド３２は、流れ内に記憶されるデータの特殊な記述を指定するのにも使用できる。図６は、流れが圧縮データを保持するときの流れ記述子２８のフォーマットの一例である。タイプフィールド３２は、流れのデータが圧縮されることを指定する値を保持し、一方、記述フィールド３４は、圧縮データに対する流れ記述子を保持する。記述フィールド３４に保持される流れ記述子は、流れに含まれるデータの量に基づいて、極小の流れ、小さな流れ、又は大きな流れである。
【００１９】
図７は、流れ記述子が暗号データの流れを記述するときの流れ記述子２８のフォーマットを示している。タイプフィールド３２は、流れが暗号データを保持することを指定する値を保持する。記述フィールド３４は、暗号データのための流れ記述子を保持する。又、流れ記述子は、暗号キーの値５０も含む。この暗号キーの値５０は、流れに記憶されたデータを暗号解読するのに使用できる。記述フィールド３４に保持された暗号データに対する流れ記述子は、極小の流れ、小さな流れ、又は大きな流れである。
【００２０】
データの特殊な記述を指定するようにタイプフィールド３２を使用する別の例が図８に示されている。図８は、小規模のトランザクションに対する流れ記述子２８を示している。小規模のトランザクションとは、データベースのデータに対する変更を行う場合に、影響を受ける全てのデータの変更に関連したオーバーヘッドを被ることを保証するに充分な数の他の変更が生じるまで、データを直接的に変更しないことを指す。タイプフィールド３２は、記述フィールド３４が小規模なトランザクションに対するデータを保持することを指定する。記述フィールド３４は、第１の流れ記述子５２と、第２の流れ記述子５４を保持する。第１の流れ記述子５２は、データの元の流れを記述する。第２の流れ記述子５４は、元の流れに対して行われた変更を指定する流れを記述する。データの元の流れは、第２の流れに保持された変更を実施することによって更新される。
【００２１】
図９は、複製データを保持する流れに対する流れ記述子２８の例を示す。データのロスが破壊的な結果を招かないように、データをしばしば複製しなければならない。特に、システムが多数のコピーをディスクに維持するところの、選択されたデータ構造体がある。このような場合に、データ構造体は、ディスク上の２つの異なる位置にコピーされる。流れ記述子２８は、第１の流れ記述子５６と、第２の流れ記述子５８をその記述フィールド３４に含んでいる。第１の流れ記述子５６は、第１のデータコピーを保持する第１の流れを記述し、そして第２の流れ記述子５８は、別のデータコピーを保持する第２の流れを記述する。タイプフィールド３２は、流れが複製データを含むことを指定する値を保持する。
【００２２】
本発明の好ましい実施例では、流れに関する情報が図１０に示すようなフィールド記述子６０に記憶される。このフィールド記述子６０は、流れＩＤを保持する流れＩＤフィールド６２を含んでいる。この流れＩＤは、オノード（以下で詳細に述べる）内の流れを独特に識別する４バイト長さの識別番号である。更に、フィールド記述子６０は、フラグビットを保持するフラグフィールド６４を備えている。フィールド記述子６０の最終フィールドは、流れに対する流れ記述子２８である。
【００２３】
流れは、関連ファンクションに基づいて「オノード」にグループ分けされる。オノードはオブジェクトの論理表示に対応し、典型的に、ファイル、ディレクトリ又はサブディレクトリを構成する全ての流れを保持する。各オノードは、これに含まれる流れの可変サイズの集合体を記述するに必要な情報を含む。
【００２４】
図１１は、オノード６６のフォーマットを示す図である。各オノード６６は、関連ファンクションの流れを保持している。各オノード６６は、次のフィールドを含む。即ち、長さフィールド６８と、ワークＩＤフィールド７０と、フラグフィールド７２と、クラスＩＤフィールド７３と、フィールド記述子６０（図１０に示すような）のアレイを保持するフィールド７６とである。長さフィールド６８は、オノードの長さを指定する値を保持し、一方、ワークＩＤフィールド７０は、以下で詳細に述べるように、ワークＩＤマッピングアレイ１０４（図１４）へのインデックスを保持する。ワークＩＤは長さが４バイトである。フラグフィールド７２（図１１）はフラグビットを保持し、そしてクラスＩＤフィールド７３は、オノードに対するクラスＩＤを保持する。フィールド７６は、フィールド記述子６０のパックアレイを保持し、これは、オノード６６と共に保持される流れの各々に対するフィールド記述子６０を含む。フィールド７６のフィールド記述子のアレイに含まれる流れの数は、変化し得る。更に、フィールド７６のフィールド記述子のアレイにおける各流れの長さも、変化し得る。従って、オノード６６は可変サイズ構造である。オノード６６の可変サイズ特性は、ディスク記憶装置１６のディスクにおける割り当て単位での内部分割を最小にするよう助成する。
【００２５】
オノード６６に関するあるデータは、オノードに直接組み込まれない。そうではなくて、このデータは、図１２に示すように個別の流れに記憶される。流れ７８は、関連オノード６６（図１１）に関する多数の異なる形式の状態情報を保持する。この状態情報は、フィールド８６に保持されたタイムスタンプであって、オノード６６が形成された時間を指定するタイムスタンプを含んでいる。フィールド８８は、オノード６６が変更された最後の時間を指定するタイムスタンプを保持する。同様に、フィールド９０は、オノード６６がアクセスされた最後の時間を指定するタイムスタンプを保持する。フィールド９２は、オノード６６のサイズを指定する値を保持し、そしてフィールド９４は、オノードのオーナーに対する機密記述子を保持する。流れ７８に保持された全ての情報は、関連オノード６６に保持されたファイルデータを管理するのに有用である。
【００２６】
図１２には、状態情報の第２の流れ８０も示されている。この流れ８０は、３つのフィールド９６、９８及び１００を備えている。各オノード６６は、データ処理システム１０のグローバルネームスペースに見ることができ、そしてこのグローバルネームスペースは、ルートオノード以外の各オノードが親ノードを有する論理ツリー構造である。フィールド９６は、親オノードのワークＩＤを保持する。フィールド９８は、オノード６６のための全般的に独特のＩＤ（ＵＵＩＤ）を保持する。更に、フィールド１００は、オノード６６のクラスを指定するクラスＩＤを保持する。各オノード６６には独特のクラスが組み合わされる。特に、各オノード６６は、特定のクラスのオブジェクトの例である。
【００２７】
状態情報の２つの付加的な流れ８２及び８４も記憶される。流れ８２は、親に対するオノード６６のネームを保持し、そして流れ８４は、オノードのためのアクセス制御リスト（機密で使用される）を保持する。
【００２８】
流れ７８、８０、８２及び８４は、少なくとも次の２つの理由で別々に記憶される。第１に、この情報を別々に記憶すると、オノード６６の平均サイズが減少される。流れ７８、８０、８２及び８４は、各オノードごとに記憶されない。その結果、オノードの平均サイズが減少する。第２に、この情報を別々に記憶すると、各オノード６６からコードを検索するのに複雑なコードを必要とすることなく、情報の関連グループにプログラムアクセスすることができる。
【００２９】
オノード６６（図１１）は、オノードバケットアレイ１０２（図１３）に記憶される。このオノードバケットアレイ１０２は、固定サイズバケットのアレイで構成された可変サイズデータ構造である。バケットのサイズ（例えば、４Ｋ）はデータ処理システム１０のアーキテクチャに基づくものであるが、システム１０のページサイズに一致してもよい。これらバケットは、図１３の例では１ないしＮと番号付けされている。アレイ１０２の各バケットは、オノード６６のパックされた組を含んでいる。図１３の例では、バケット２は、単一のオノードのみを含み、一方、バケット１は、２つのオノードを含み、そしてバケット３は、３つのオノードを含むことが明らかである。
【００３０】
オノードバケットアレイ１０２は、ファイルデータが移動、削除又は挿入されたときにシャフルされねばならないデータの量を最小にするために使用される。ディスクスペースのブロックを割り当て及び割り当て解除する粒度は固定とされる。換言すれば、メモリブロックは、固定サイズのバケットで、割り当て及び割り当て解除される。そうではなくて、ファイルデータを記憶するために可変サイズの構造が使用された場合には、割り当ての粒度は固定されず、割り当ての粒度を非常に大きくすることができる。
【００３１】
効率化のために、オペレーティングシステム２４（図１）は、関連オノード６６（図１１）をアレイ１０２（図１４）の同じバケットに記憶するか、又はディスク記憶装置１６のディスク上で互いに接近したバケットに記憶する。この記憶戦術は、ディスク上でオノード６６を探すシーク時間を、最小にする。一般に、通常一緒にアクセスされるファイルは同じバケットに配置される。一緒にアクセスされるファイルは、例えば、共通のサブディレクトリ又はディレクトリにあるファイルである。
【００３２】
オノードバケットアレイ１０２（図１３）は、流れとしてアクセスされる。システム１０は、通常、多数のオノードバケットアレイ１０２を記憶し、従って、オノードバケットアレイを保持する多数の流れを記憶する。内部では、オノード間の全ての参照は、ワークＩＤに基づいている。アレイ１０２のバケット内でオノード６６（図１１）を位置決めするには、そのオノードに対するワークＩＤを探すことが必要である。ワークＩＤのマッピングアレイ１０４（図１４）は、ワークＩＤからオノードバケットアレイ１０２のバケット番号へマップする。次いで、番号付けされたバケットが、オノードに対し整合ワークＩＤでサーチされる。特に、特定ノード６６のワークＩＤは、ワークＩＤマッピングアレイ１０４へインデックスを与える。指定されたインデックスにおけるエントリーは、オノード６６を保持するバケット番号を識別する。例えば、図１４に示すように、ワークＩＤマッピングアレイ１０４のエントリー１０６及び１０８は、関連するワークＩＤを有するオノード６６がバケット１に保持されることを指定する値を保持する。
【００３３】
各オノード６６（図１１）は、フィールド記述子７６のアレイに保持される流れの中に記憶されるネームインデックスの流れを含んでいる。ネームインデックスの流れは、オノード６６内に含まれた流れ記述子に対するＢツリーインデックスを保持する。ネームインデックスの流れは、流れの流れＩＤを、オノード６６内に保持された流れ記述子を位置決めするためのキーとして使用する。Ｂツリーインデックスは、本発明と同日に出願された共通の譲受人に譲渡された「ファイルシステムにオブジェクトを効率的に記憶する方法(Efficient Storage of Objects in a File System) 」と題する特許出願に詳細に示されている。この特許出願の開示を参考としてここに取り上げる。
【００３４】
流れの関連収集体が、オノード６６（図１１）へと収集されるのと同様に、オノードの関連収集体がオブジェクト記憶カタログとして知られたデータ構造へ収集される。オノード６６のワークＩＤは、オブジェクト記憶カタログ内のオノードを識別するためのベースとして働く。オブジェクト記憶カタログは、図１５に示すようなオブジェクト記憶カタログオノード１１０によって記述される。オブジェクト記憶カタログオノード１１０は、長さフィールド６８と、ワークＩＤフィールド７０と、フラグフィールド７２と、他のオノード６６で見つかったフィールド記述子７６のアレイとを含んでいる。フィールド記述子７６のアレイは、流れ記述子１１２、１１４及び１１６が記憶されたフィールド記述子を含む。
【００３５】
流れ記述子１１２は、ワークＩＤマッピングアレイの流れ１０４を記述する。流れ記述子１１４は、オノードバケットアレイの流れ１０２を記述し、そして流れ記述子１１６は、ネームインデックスの流れ１１７を記述する。ワークＩＤマッピングアレイの流れ１０４及びオノードバケットアレイの流れ１０２は、関連データを記憶するので、これらは共通のオノード（即ち、オブジェクト記憶カタログオノード１１０）に記憶される。このように、オブジェクト記憶カタログオノード１１０は、ワークＩＤマッピングアレイの流れ１０４、オノードバケットアレイの流れ１０２及びネームインデックスの流れ１１７を関係付けるビークルを形成する。オブジェクト記憶カタログオノード１１０は、ワークＩＤ  ０におけるカタログを構成するオノードのグループ内に記憶される。ワークＩＤ  ０とは、その定義により、オノードバケットアレイの流れ１０２の第１エレメントに常に配置される。ワークＩＤ  ０における第１バケットは、既知の位置を有する区別されたバケットである。従って、バケット内に記憶されたデータ構造は容易に且つ簡単にアクセスされる。
【００３６】
本発明を好ましい実施例について説明したが、特許請求の範囲に規定された本発明の範囲から逸脱せずにその形態及び細部に種々の変更がなされ得ることが当業者に明らかであろう。
【図面の簡単な説明】
【００３７】
【図１】本発明の好ましい実施例によるデータ処理システムのブロック図である。
【図２】本発明の好ましい実施例に用いられる流れ記述子のフォーマットを示す図である。
【図３】本発明の好ましい実施例による極小の流れに対する流れ記述子の図である。
【図４】本発明の好ましい実施例による小さな流れに対する流れ記述子の図である。
【図５】本発明の好ましい実施例による大きな流れに対する流れ記述子の図である。
【図６】本発明の好ましい実施例による圧縮流に対する流れ記述子の図である。
【図７】本発明の好ましい実施例による暗号流に対する流れ記述子の図である。
【図８】本発明の好ましい実施例による小規模トランザクションに対する流れ記述子の図である。
【図９】本発明の好ましい実施例による複製データに対する流れ記述子の図である。
【図１０】本発明の好ましい実施例によるフィールド記述子の図である。
【図１１】本発明の好ましい実施例によるオノードの図である。
【図１２】図１１のオノードについての適切な情報を保持するシステムの図である。
【図１３】本発明の好ましい実施例によるバケットアレイの図である。
【図１４】本発明の好ましい実施例によるワークＩＤマッピングアレイ及びオノードバケットアレイの図である。
【図１５】本発明の好ましい実施例によるオブジェクト記憶カタログの図である。
【符号の説明】
【００３８】
１０  データ処理システム
１２  中央処理ユニット
１４  メモリ
１６  ディスク記憶装置
１８  キーボード
２０  マウス
２２  ビデオディスプレイ
２４  オペレーティングシステム
２６  ファイルシステム
２８  流れ記述子
３０  サイズフィールド
３２  タイプフィールド
３４  記述フィールド
３８、４０  サブフィールド
４２  イクステント
４３  第２の流れ記述子
６０  フィールド記述子
６６  オノード
６８  長さフィールド
７０  ワークＩＤフィールド
７２  フラグフィールド
７３  クラスＩＤフィールド
７６  フィールド
７８  流れ
８０  第２の流れ
【図１】
2007128543.tif 000003
【図２】
2007128543.tif 000004
【図３】
2007128543.tif 000005
【図４】
2007128543.tif 000006
【図５】
2007128543.tif 000007
【図６】
2007128543.tif 000008
【図７】
2007128543.tif 000009
【図８】
2007128543.tif 000010
【図９】
2007128543.tif 000011
【図１０】
2007128543.tif 000012
【図１１】
2007128543.tif 000013
【図１２】
2007128543.tif 000014
【図１３】
2007128543.tif 000015
【図１４】
2007128543.tif 000016
【図１５】
2007128543.tif 000017