(57)【要約】  複数のメモリ装置に対する複数の操作ストリームを管理する方法およびシステムを提示する。本方法は、複数の操作間の相互依存関係を判定し、この相互依存関係を基づき、これらの操作の実行を最適化する。また、システム動作にほとんど悪影響を及ぼすことなく複数のメモリ装置を同期化する方法を提示する。本方法は、複数のオブジェクトを所定の順番でサンプリングするステップを伴う。サンプリングはシステムの通常使用中に行われるので、少なくとも１つのターゲットオブジェクトに対して実行される操作が受け付けられる。ターゲットオブジェクトの状態が判定される。ターゲットオブジェクトが修正状態である場合は、修正が第２の記憶システムに対して実行され、当該操作はターゲットオブジェクトに適用されるが、第２のメモリ装置に対する当該操作の適用は、ターゲットオブジェクトが最終状態になるまで延期される。【選択図】図２
2008541204.tif 000002
【特許請求の範囲】
【請求項１】
操作ストリームを最適化する方法であって、
操作ストリームを受け付けるステップと、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の前記延期された各操作を適用するための最適化された順番を判定するステップと、を含む方法。
【請求項２】
請求項１に記載の方法であって、前記サブセット内の各操作を含む、延期された操作のリストを形成するステップをさらに含み、前記リストによって前記サブセット内の前記操作間の相互依存関係が特定される方法。
【請求項３】
請求項２に記載の方法であって、
前記リスト上の延期された操作のうち特定の延期された操作を適用するステップと、
前記適用に応じて、前記特定の延期された操作を前記リストから削除するステップと、をさらに含む方法。
【請求項４】
請求項３に記載の方法であって、前記特定の延期された操作によって阻止されていた前記リスト上の他の複数の延期された操作を適用するステップをさらに含む方法。
【請求項５】
請求項１に記載の方法であって、前記相互依存関係に基づき前記操作のいくつかを論理的に組み合わせて単一の操作にするステップをさらに含む方法。
【請求項６】
請求項１に記載の方法であって、前記サブセット内の操作を前記最適化された順番で適用するステップをさらに含む方法。
【請求項７】
請求項１に記載の方法であって、前記延期された操作のうちの１つが親オブジェクトと子オブジェクトとを有するマルチオブジェクト操作であり、前記方法は、
前記マルチオブジェクト操作を前記親オブジェクトに対する延期された操作の親リストに追加するステップと、
前記マルチオブジェクト操作を前記子オブジェクトに対する延期された操作の子リストに追加するステップと、
前記マルチオブジェクト操作が前記親リストまたは前記子リストのどちらかに含まれる別の操作によって阻止されない場合にのみ、前記マルチオブジェクト操作を適用するステップと、を含む方法。
【請求項８】
請求項７に記載の方法であって、相互に依存関係のない複数のマルチオブジェクト操作に対してそれぞれ別個の親リストを作成するステップをさらに含む方法。
【請求項９】
請求項７に記載の方法であって、相互に依存関係のない複数のマルチオブジェクト操作に対してそれぞれ別個の子リストを作成するステップをさらに含む方法。
【請求項１０】
１つ以上のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法であって、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の前記延期された各操作を前記メモリ装置のそれぞれに適用するための最適化された順番を判定するステップと、を含む方法。
【請求項１１】
請求項１０に記載の方法であって、前記操作間の相互依存関係に基づき前記操作のいくつかを組み合わせて単一の操作にするステップをさらに含む方法。
【請求項１２】
複数のオブジェクトと複数の対応オブジェクトとを有する複数のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法であって、
前記複数のオブジェクトを所定の順番でサンプリングするステップであって、前記サンプリングによって前記複数のオブジェクトの状態を変更するステップと、
前記複数のオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付けるステップと、
前記ターゲットオブジェクトの状態を判定するステップと、
前記複数のメモリ装置において前記複数のオブジェクトと前記複数の対応オブジェクトとを比較するステップと、
前記ターゲットオブジェクトの前記状態に基づき、前記操作を前記ターゲットオブジェクトに適用するタイミングと前記操作を前記第２のメモリ装置に適用するタイミングとを判定するステップと、
前記ターゲットオブジェクトが修正状態の場合は、前記操作を前記ターゲットオブジェクトに適用し、前記第２のメモリ装置への前記操作の適用を延期するステップと、を含む方法。
【請求項１３】
請求項１２に記載の方法であって、
修正を実行すべきか否かを判定するステップと、
前記第２のメモリ装置の前記対応オブジェクトを前記修正状態の前記ターゲットオブジェクトとほぼ同様にするために、前記対応オブジェクトに対して前記修正を実行するステップと、をさらに含む方法。
【請求項１４】
請求項１２に記載の方法であって、前記サンプリングが第１のスレッドで実行され、前記方法は前記対応オブジェクトに対する修正を第２のスレッドで行うステップをさらに含む方法。
【請求項１５】
請求項１２に記載の方法であって、前記サンプリングは阻止領域によって行われ、前記阻止領域とは別個に修正領域が存在し、前記阻止領域によって覆われたオブジェクトは阻止状態であり、前記修正領域によって覆われたオブジェクトは修正状態である方法。
【請求項１６】
請求項１５に記載の方法であって、前記阻止領域と前記修正領域とが互いに隣接する方法。
【請求項１７】
請求項１５に記載の方法であって、前記修正領域のサイズを調整することによって、延期される操作の最大数を制御するステップをさらに含む方法。
【請求項１８】
請求項１５に記載の方法であって、前記阻止領域のサイズを最小化するステップをさらに含む方法。
【請求項１９】
請求項１５に記載の方法であって、
前記ターゲットオブジェクトが前記阻止状態である間に前記複数のメモリ装置からオブジェクト情報を集めるステップと、
前記ターゲットオブジェクトが前記修正状態である間に前記複数のメモリ装置において前記複数のオブジェクトと前記複数の対応オブジェクトとを比較するステップと、をさらに含む方法。
【請求項２０】
請求項１２に記載の方法であって、前記ターゲットオブジェクトが阻止状態である場合は、前記ターゲットオブジェクトへの変更を防止するステップをさらに含む方法。
【請求項２１】
請求項１２に記載の方法であって、前記オブジェクトはサンプリング前は初期状態であり、サンプリング後は最終状態であり、前記方法は、
前記ターゲットオブジェクトが前記初期状態の場合は、前記操作を前記ターゲットオブジェクトにのみ適用するステップと、
前記ターゲットオブジェクトが前記最終状態の場合は、前記操作を前記ターゲットオブジェクトと前記第２のメモリ装置内の対応オブジェクトとに適用するステップと、をさらに含む方法。
【請求項２２】
請求項１２に記載の方法であって、
前記延期された操作の適用を第１のスレッドで準備するステップと、
前記延期された操作を第２のスレッドで適用するステップと、をさらに含む方法。
【請求項２３】
請求項１２に記載の方法であって、前記第２のメモリ装置への前記操作の適用を延期するステップがオブジェクト識別子をキャッシュするステップを含む方法。
【請求項２４】
請求項１２に記載の方法であって、前記所定のサンプリング順をファイル識別子の順番として特定するステップをさらに含む方法。
【請求項２５】
請求項１２に記載の方法であって、前記所定の順番がファイルシステム内のファイルの深さまたは幅に応じて決まる方法。
【請求項２６】
請求項１２に記載の方法であって、前記所定の順番がメモリブロックの順番である方法。
【請求項２７】
請求項１２に記載の方法であって、前記操作が最終状態または修正状態のどちらかである第１のターゲットオブジェクトと、初期状態である第２のターゲットオブジェクトとに関わるときは、前記ターゲットオブジェクトのためのゴーストエントリを追加するステップをさらに含み、前記ゴーストエントリによって前記操作の結果を前記サンプリングに対して隠す方法。
【請求項２８】
請求項２７に記載の方法であって、前記操作を延期し、前記操作が確実に実行されるように前記延期された操作に前記ゴーストエントリを関連付けるステップをさらに含む方法。
【請求項２９】
請求項２７に記載の方法であって、複数の操作が前記ターゲットオブジェクトに対して実行される場合は、前記ターゲットオブジェクトに対するゴーストエントリのリストを作成するステップをさらに含む方法。
【請求項３０】
請求項２９に記載の方法であって、前記リスト上のゴーストエントリは親オブジェクトによって索引付けされ、各親オブジェクトは１つ以上のリストを有し、各リストは子名ごとに固有である方法。
【請求項３１】
請求項１２に記載の方法であって、前記操作が複数のオブジェクトに影響する場合は、前記操作によって影響を受ける全てのターゲットオブジェクトが最終状態になるまで前記操作を延期するステップをさらに含む方法。
【請求項３２】
請求項１２に記載の方法であって、
前記操作に必要なオブジェクトが前記操作のために利用可能であるか否かを判定するステップと、
前記修正状態で延期された前記操作を、前記ターゲットオブジェクトが最終状態になる前に、前記第２のメモリ装置に適用するステップと、をさらに含む方法。
【請求項３３】
請求項１２に記載の方法であって、前記操作の延期が決定され次第、前記操作を前記ターゲットオブジェクトに対する延期された操作の待ち行列に追加するステップをさらに含む方法。
【請求項３４】
請求項３３に記載の方法であって、
前記操作が適用され次第、前記操作を前記延期された操作の待ち行列から削除するステップと、
前記削除の結果として適用できるようになった他の複数の操作を特定するために、前記延期された操作の待ち行列に残っている操作を見直すステップと、をさらに含む方法。
【請求項３５】
請求項３４に記載の方法であって、前記見直しステップが、前記待ち行列内の前記他の操作間の相互依存関係を分析するステップを含む方法。
【請求項３６】
請求項３３に記載の方法であって、前記操作が親オブジェクトと子オブジェクトとを有するマルチオブジェクト操作であり、前記方法が、
前記延期された操作を前記親オブジェクトに対する延期された操作の親リストに追加するステップと、
前記延期された操作を前記子オブジェクトに対する延期された操作の子リストに追加するステップと、をさらに含む方法
【請求項３７】
請求項３６に記載の方法であって、前記操作を前記ターゲットオブジェクトに適用する前に、前記操作が前記親リスト上の先頭の項目であり、かつ前記子リスト上の先頭の項目であることを検証するステップをさらに含む方法。
【請求項３８】
請求項３６に記載の方法であって、
前記親オブジェクトに対して複数の親リストを作成するステップと、
相互に依存しない複数の操作をそれぞれ別個の親リストに追加するステップと、をさらに含む方法。
【請求項３９】
請求項３６に記載の方法であって、
前記子オブジェクトに対して複数の子リストを作成するステップと、
相互に依存しない複数の操作をそれぞれ別個の子リストに登録するステップと、をさらに含む方法。
【請求項４０】
請求項３６に記載の方法であって、前記操作の適用後に、前記操作を前記親リストおよび前記子リストから削除するステップをさらに含む方法。
【請求項４１】
請求項４０に記載の方法であって、前記操作が削除され次第、前記複数のリスト内の延期された操作を見直し、前記削除の結果として適用できるようになった他の複数の操作を特定するステップをさらに含む方法。
【請求項４２】
請求項３３に記載の方法であって、前記操作が前記ターゲットオブジェクトに対して実行された後で、前記操作を前記単純操作の待ち行列から削除するステップをさらに含む方法。
【請求項４３】
請求項３３に記載の方法であって、前記待ち行列内の項目が実行できるようになったと判定され次第、前記延期された操作の待ち行列に残っている複数の項目を調べるステップをさらに含む方法。
【請求項４４】
請求項１２に記載の方法であって、前記操作が第１の操作であり、前記方法は、
前記第１の操作の後に第２の操作を受け付けるステップと、
前記第１の操作と前記第２の操作とが延期される場合は、前記第１の操作と第２の操作とを論理的に組み合わせて１つの組み合わせ操作にするステップと、をさらに含む方法。
【請求項４５】
請求項４４に記載の方法であって、前記第１の操作と前記第２の操作とを論理的に組み合わせるステップが、前記第１の操作と第２の操作との間の相互依存関係を分析するステップを含む方法。
【請求項４６】
操作ストリームを最適化するシステムであって、
操作ストリームを受け付ける第１のモジュールと、
操作間の相互依存関係を分析する第２のモジュールと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期する第３のモジュールと、
前記サブセット内の延期された各操作を適用するための最適化された順番を判定する第４のモジュールと、を含むシステム。
【請求項４７】
請求項４６に記載のシステムであって、前記サブセット内の各操作を含む、延期された操作のリストを形成する第５のモジュールをさらに含み、前記リストによって前記サブセット内の操作間の相互依存関係が特定されるシステム。
【請求項４８】
請求項４７に記載のシステムであって、前記第５のモジュールは、前記延期された操作のリスト内の特定の延期された操作を適用し、前記適用に応じて、前記特定の延期された操作を前記リストから削除するシステム。
【請求項４９】
請求項４８に記載のシステムであって、前記第５のモジュールは、前記特定の延期された操作によって阻止されていた前記リスト上の他の延期されていた操作を適用するシステム。
【請求項５０】
請求項４６に記載のシステムであって、前記相互依存関係に基づき前記操作のいくつかを論理的に組み合わせて単一の操作にする第５のモジュールをさらに含むシステム。
【請求項５１】
請求項４６に記載のシステムであって、前記サブセット内の操作を前記最適化された順番で適用する第５のモジュールをさらに含むシステム。
【請求項５２】
複数のメモリ装置間でデータを管理するシステムであって、
複数のオブジェクトを有する第１のメモリ装置と、
複数の対応オブジェクトを有する第２のメモリ装置と、
前記複数のオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付ける入力部と、
前記第１のメモリ装置内の前記複数のオブジェクトをサンプリングし、前記ターゲットオブジェクトの状態を判定し、修正を実行すべきか否かを判定し、前記操作を前記ターゲットオブジェクトに適用するタイミングを判定し、前記操作を前記複数の対応オブジェクトに適用するタイミングを判定するプロセッサと、を備え、
前記ターゲットオブジェクトが修正状態の場合は、前記プロセッサは、前記操作を前記ターゲットオブジェクトに適用するが、前記複数の対応オブジェクトへの前記操作の適用を延期するシステム。
【請求項５３】
請求項５２に記載のシステムであって、前記プロセッサは、前記複数の対応オブジェクを前記ターゲットオブジェクトとほぼ同様にするために、前記修正を前記修正状態の前記複数の対応オブジェクトに対して実行するシステム。
【請求項５４】
請求項５２に記載のシステムであって、延期された操作のリストを保存するメモリをさらに備え、前記延期された操作が前記リストに追加されるシステム。
【請求項５５】
請求項５４に記載のシステムであって、前記延期された操作間の相互依存関係を判定するモジュールをさらに備えるシステム。
【請求項５６】
請求項５５に記載のシステムであって、前記モジュールは、前記特定の操作が前記複数の対応オブジェクトに適用され次第、前記特定の操作を前記延期された操作のリストから削除するシステム。
【請求項５７】
請求項５６に記載のシステムであって、前記モジュールは、前記特定の操作が削除され次第、何れか他の延期された操作が適用できるようになったか否かを判定するために、前記リスト上に残っている延期された複数の操作を見直すシステム。
【請求項５８】
請求項５２に記載のシステムであって、前記プロセッサは、阻止領域と修正領域とによって前記各オブジェクトをトラバースすることによって前記複数のオブジェクトをサンプリングし、サンプリングされていないオブジェクトは初期状態であり、前記阻止領域によって覆われたオブジェクトは阻止状態であり、前記修正領域によって覆われたオブジェクトは前記修正状態であり、前記修正状態から出たオブジェクトは最終状態であるシステム。
【請求項５９】
請求項５９に記載のシステムであって、前記阻止領域と前記修正領域とが互いに隣接するシステム。
【請求項６０】
請求項５９に記載のシステムであって、前記ターゲットオブジェクトが前記阻止状態である場合は、前記プロセッサは前記ターゲットオブジェクトへの一切の変更を防止するシステム。
【請求項６１】
請求項５９に記載のシステムであって、前記ターゲットオブジェクトが初期状態である場合は、前記プロセッサは前記操作を前記ターゲットオブジェクトに対してのみ実行するシステム。
【請求項６２】
請求項５９に記載のシステムであって、前記ターゲットオブジェクトが前記最終状態である場合は、前記プロセッサは前記操作を前記ターゲットオブジェクトと前記複数の対応オブジェクトとに対して実行するシステム。
【請求項６３】
請求項５２に記載のシステムであって、前記プロセッサが前記第１のメモリ装置を調べる際のトラバース順を記憶するメモリをさらに備え、前記トラバース順がファイル識別子の順であるシステム。
【請求項６４】
請求項５２に記載のシステムであって、前記プロセッサが前記第１のメモリ装置を調べる際のトラバース順を記憶するメモリをさらに備え、前記トラバース順がファイルシステム内のファイルの深さまたは幅に応じて決まるシステム。
【請求項６５】
請求項５２に記載のシステムであって、ゴーストエントリを生成するモジュールをさらに備え、前記プロセッサは、前記第１のメモリ装置の調査中に前記ターゲットオブジェクトが操作されるときは、前記ゴーストエントリを前記ターゲットオブジェクトに追加し、前記ゴーストエントリによって前記操作の結果を隠すシステム。
【請求項６６】
請求項６５に記載のシステムであって、前記ゴーストエントリと前記結果が隠された操作との間のリンクをさらに備え、前記操作が延期されるシステム。
【請求項６７】
請求項６５に記載のシステムであって、マルチオブジェクト操作における親オブジェクトのためのゴーストエントリのリストをさらに備え、前記リストは子名に固有であり、異なる子名に固有の追加リストが前記親オブジェクトに対して存在するシステム。
【請求項６８】
請求項５２に記載のシステムであって、前記操作は親オブジェクトと子オブジェクトとを有するマルチオブジェクト操作であり、前記システムは、
前記親オブジェクトに対する延期された操作の親リストと、
前記子オブジェクトに対する延期された操作の子リストと、をさらに備えるシステム。
【請求項６９】
請求項６８に記載のシステムであって、延期された操作が前記親オブジェクトの前記親リスト上の先頭項目であり、かつ第１の前記子オブジェクトの前記子リスト上の先頭項目である場合にのみ、前記プロセッサが前記延期された操作をターゲットオブジェクトに適用するシステム。
【請求項７０】
請求項５２に記載のシステムであって、前記プロセッサは複数の延期された操作を論理的に組み合わせて単一の操作にするシステム。
【請求項７１】
請求項７０に記載のシステムであって、前記プロセッサは、前記複数の延期された操作を論理的に組み合わせる前に、前記複数の延期された操作間の相互依存関係を見直すシステム。
【請求項７２】
操作ストリームを最適化する方法のための複数のコンピュータ実行可能命令が搭載されたコンピュータ可読媒体であって、前記方法が、
操作ストリームを受け付けるステップと、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の延期された各操作を適用するための最適化された順番を判定するステップと、を含む、コンピュータ可読媒体。
【請求項７３】
請求項７２に記載のコンピュータ可読媒体であって、前記サブセット内の各操作を含む、延期された操作のリストを形成するステップをさらに含み、前記リストによって前記サブセット内の操作間の相互依存関係が特定されるコンピュータ可読媒体。
【請求項７４】
請求項７３に記載のコンピュータ可読媒体であって、
前記延期された操作のリスト上の特定の延期された操作を適用するステップと、
前記適用に応じて、前記特定の延期された操作を前記リストから削除するステップと、をさらに含むコンピュータ可読媒体。
【請求項７５】
請求項７４に記載のコンピュータ可読媒体であって、前記特定の延期された操作によって阻止されていた前記リスト上の他の複数の延期された操作を適用するステップをさらに含むコンピュータ可読媒体。
【請求項７６】
請求項７２に記載のコンピュータ可読媒体であって、前記相互依存関係に基づき前記操作のいくつかを論理的に組み合わせて単一の操作にするステップをさらに含むコンピュータ可読媒体。
【請求項７７】
請求項７２に記載のコンピュータ可読媒体であって、前記サブセット内の操作を前記最適化された順番で適用するステップをさらに含むコンピュータ可読媒体。
【請求項７８】
請求項７２に記載のコンピュータ可読媒体であって、前記延期された操作の１つが親オブジェクトと子オブジェクトとを有するマルチオブジェクト操作であり、
前記マルチオブジェクト操作を、前記親オブジェクトに対する延期された操作の親リストに追加するステップと、
前記マルチオブジェクト操作を、前記子オブジェクトに対する延期された操作の子リストに追加するステップと、
前記マルチオブジェクト操作が前記親リストまたは前記子リストのどちらかに含まれている別の操作によって阻止されない場合にのみ、前記マルチオブジェクト操作を適用するステップと、をさらに含むコンピュータ可読媒体。
【請求項７９】
請求項７２に記載のコンピュータ可読媒体であって、相互に依存関係のない複数のマルチオブジェクト操作に対してそれぞれ別個の親リストを作成するステップをさらに含むコンピュータ可読媒体。
【請求項８０】
請求項７２に記載のコンピュータ可読媒体であって、相互に依存関係のない複数のマルチオブジェクト操作に対してそれぞれ別個の子リストを作成するステップをさらに含むコンピュータ可読媒体。
【請求項８１】
１つ以上のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法のための複数のコンピュータ実行可能命令を搭載したコンピュータ可読媒体であって、前記方法が、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の延期された各操作を前記メモリ装置のそれぞれに適用するための最適化された順番を判定するステップと、を含むコンピュータ可読媒体。
【請求項８２】
複数のオブジェクトと複数の対応オブジェクトとを有する複数のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法のためのコンピュータ実行可能命令が搭載されているコンピュータ可読媒体であって、前記方法が、
前記複数のオブジェクトを所定の順番でサンプリングするステップであって、前記サンプリングによって前記複数のオブジェクトの状態を変更するステップと、
前記複数のオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付けるステップと、
前記ターゲットオブジェクトの状態を判定するステップと、
前記複数のメモリ装置において前記複数のオブジェクトと前記複数の対応オブジェクトとを比較するステップと、
前記ターゲットオブジェクトの前記状態に基づき、前記操作を前記ターゲットオブジェクトに適用するタイミングと、前記操作を前記第２のメモリ装置に適用するタイミングとを判定するステップと、
前記ターゲットオブジェクトが修正状態の場合は、前記操作を前記ターゲットオブジェクトに適用し、前記第２のメモリ装置への前記操作の適用を延期するステップと、を含むコンピュータ可読媒体。
【請求項８３】
請求項８２に記載のコンピュータ可読媒体であって、前記方法が、
修正を実行すべきか否かを判定するステップと、
前記第２のメモリ装置の前記対応オブジェクトを前記修正状態の前記ターゲットオブジェクトとほぼ同様にするために、前記対応オブジェクトに対して前記修正を実行するステップと、をさらに含むコンピュータ可読媒体。
【請求項８４】
請求項８２に記載のコンピュータ可読媒体であって、前記サンプリングが第１のスレッドで実行され、前記方法が前記複数の対応オブジェクトの修正を第２のスレッドで行うステップをさらに含むコンピュータ可読媒体。
【請求項８５】
請求項８２に記載のコンピュータ可読媒体であって、前記サンプリングは阻止領域によって行われ、前記阻止領域とは別個に修正領域が存在し、前記阻止領域によって覆われたオブジェクトは阻止状態であり、前記修正領域によって覆われたオブジェクトは修正状態であるコンピュータ可読媒体。
【請求項８６】
請求項８５に記載のコンピュータ可読媒体であって、前記阻止領域と前記修正領域とが互いに隣接するコンピュータ可読媒体。
【請求項８７】
請求項８５に記載のコンピュータ可読媒体であって、前記方法は、前記修正領域のサイズを調整することによって、延期される操作の最大数を制御するステップをさらに含む、コンピュータ可読媒体。
【請求項８８】
請求項８５に記載のコンピュータ可読媒体であって、前記方法は、前記阻止領域のサイズを最小化するステップをさらに含む、コンピュータ可読媒体。
【請求項８９】
請求項８５に記載のコンピュータ可読媒体であって、前記方法は、
前記ターゲットオブジェクトが前記阻止状態である間に前記複数のメモリ装置からオブジェクト情報を集めるステップと、
前記複数のオブジェクトが前記修正状態である間に前記複数のオブジェクトを前記第２のメモリ装置内の前記複数の対応オブジェクトと比較するステップと、をさらに含む、コンピュータ可読媒体。
【請求項９０】
請求項８２に記載のコンピュータ可読媒体であって、前記方法は、前記ターゲットオブジェクトが阻止状態である場合に、前記ターゲットオブジェクトへの変更を防止するステップをさらに含む、コンピュータ可読媒体。
【請求項９１】
請求項８２に記載のコンピュータ可読媒体であって、前記オブジェクトはサンプリング前は初期状態であり、サンプリング後は最終状態であり、前記方法は、
前記ターゲットオブジェクトが前記初期状態である場合は、前記操作を前記ターゲットオブジェクトにのみ適用するステップと、
前記ターゲットオブジェクトが前記最終状態である場合は、前記操作を前記ターゲットオブジェクトと前記第２のメモリ装置内の対応オブジェクトとに適用するステップと、をさらに含む、コンピュータ可読媒体。
【請求項９２】
請求項８２に記載のコンピュータ可読媒体であって、前記方法は、
前記延期された操作の適用を第１のスレッドで準備するステップと、
前記延期された操作を第２のスレッドで適用するステップと、をさらに含むコンピュータ可読媒体。
【請求項９３】
請求項８２に記載のコンピュータ可読媒体であって、前記第２のメモリ装置への前記操作の適用を延期するステップがオブジェクト識別子をキャッシュするステップを含むコンピュータ可読媒体。
【請求項９４】
請求項８２に記載のコンピュータ可読媒体であって、前記方法が前記所定のサンプリング順をファイル識別子の順番として特定するステップをさらに含むコンピュータ可読媒体。
【請求項９５】
請求項８２に記載のコンピュータ可読媒体であって、前記所定の順番がファイルシステム内のファイルの深さまたは幅に応じて決まるコンピュータ可読媒体。
【請求項９６】
請求項８２に記載のコンピュータ可読媒体であって、前記所定の順番がメモリブロックの順番であるコンピュータ可読媒体。
【請求項９７】
請求項８２に記載のコンピュータ可読媒体であって、前記方法は、前記操作が最終状態または修正状態のどちらかである第１のターゲットオブジェクトと、初期状態である第２のターゲットオブジェクトとに関わるときに、前記ターゲットオブジェクトのためのゴーストエントリを追加するステップをさらに含み、前記ゴーストエントリによって前記操作の結果を前記サンプリングに対して隠すコンピュータ可読媒体。
【請求項９８】
請求項９７に記載のコンピュータ可読媒体であって、前記方法は、前記操作を延期し、前記延期された操作が確実に実行されるように前記延期された操作に前記ゴーストエントリを関連付けるステップをさらに含む、コンピュータ可読媒体。
【請求項９９】
請求項９７に記載のコンピュータ可読媒体であって、前記方法は、複数の操作が前記ターゲットオブジェクトに対して実行される場合に、前記ターゲットオブジェクトに対するゴーストエントリのリストを作成するステップをさらに含むコンピュータ可読媒体。
【請求項１００】
請求項９９に記載のコンピュータ可読媒体であって、前記リスト内のゴーストエントリは親オブジェクトによって索引付けされ、各親オブジェクトは１つ以上のリストを有し、各リストは子名に固有であるコンピュータ可読媒体。
【請求項１０１】
請求項８２に記載のコンピュータ可読媒体であって、前記方法は、前記操作が複数のオブジェクトに影響する場合は、前記操作によって影響される全てのターゲットオブジェクトが最終状態になるまで前記操作を延期するステップをさらに含むコンピュータ可読媒体。
【請求項１０２】
請求項８２に記載のコンピュータ可読媒体であって、前記方法は、
前記操作に必要なオブジェクトが前記操作のために利用可能であるか否かを判定するステップと、
前記ターゲットオブジェクトが最終状態になる前に、前記修正状態で延期された前記操作を前記第２のメモリ装置に適用するステップと、をさらに含むコンピュータ可読媒体。
【請求項１０３】
請求項８２に記載のコンピュータ可読媒体であって、前記方法は、前記操作の延期が決定され次第、前記ターゲットオブジェクトに対する延期された操作の待ち行列に前記操作を追加するステップをさらに含む、コンピュータ可読媒体。
【請求項１０４】
請求項１０３に記載のコンピュータ可読媒体であって、前記方法は、
前記操作が適用され次第、前記延期された操作の待ち行列から前記操作を削除するステップと、
前記削除の結果として適用できるようになった他の複数の操作を特定するために、前記延期された操作の待ち行列に残っている操作を見直すステップと、をさらに含む、コンピュータ可読媒体。
【請求項１０５】
請求項１０４に記載のコンピュータ可読媒体であって、前記見直しステップが前記待ち行列内の前記他の操作間の相互依存関係を分析するステップを含むコンピュータ可読媒体。
【請求項１０６】
請求項１０３に記載のコンピュータ可読媒体であって、前記操作が親オブジェクトと子オブジェクトとを有するマルチオブジェクト操作であり、前記方法は、
前記延期された操作を前記親オブジェクトに対する延期された操作の親リストに追加するステップと、
前記延期された操作を前記子オブジェクトに対する延期された操作の子リストに追加するステップと、をさらに含むコンピュータ可読媒体。
【請求項１０７】
請求項１０６に記載のコンピュータ可読媒体であって、前記方法は、前記操作を前記ターゲットオブジェクトに適用する前に、前記操作が前記親リスト上の先頭項目であり、かつ前記子リスト上の先頭項目であることを検証するステップをさらに含むコンピュータ可読媒体。
【請求項１０８】
請求項１０６に記載のコンピュータ可読媒体であって、前記方法は、
前記親オブジェクトに対して複数の親リストを作成するステップと、
相互に依存しない複数の操作をそれぞれ別個の親リストに追加するステップと、をさらに含む、コンピュータ可読媒体。
【請求項１０９】
請求項１０６に記載のコンピュータ可読媒体であって、前記方法は、
前記子オブジェクトに対して複数の子リストを作成するステップと、
相互に依存しない複数の操作をそれぞれ別個の子リストに追加するステップと、をさらに含むコンピュータ可読媒体。
【請求項１１０】
請求項１０６に記載のコンピュータ可読媒体であって、前記方法は、前記操作の適用後に、前記操作を前記親リストと前記子リストとから削除するステップをさらに含むコンピュータ可読媒体。
【請求項１１１】
請求項１１０に記載のコンピュータ可読媒体であって、前記方法は、前記操作が削除され次第、前記複数のリスト上の延期された操作を見直し、前記削除の結果として適用できるようになった他の複数の操作を特定するステップをさらに含むコンピュータ可読媒体。
【請求項１１２】
請求項１０３に記載のコンピュータ可読媒体であって、前記方法は、前記操作が前記ターゲットオブジェクトに対して実行された後で、前記操作を前記単純操作の待ち行列から削除するステップをさらに含むコンピュータ可読媒体。
【請求項１１３】
請求項１０３に記載のコンピュータ可読媒体であって、前記方法は、前記待ち行列内の項目が実行できるようになったと判定され次第、前記延期された操作の待ち行列に残っている複数の項目を調べるステップをさらに含む、コンピュータ可読媒体。
【請求項１１４】
請求項８２に記載のコンピュータ可読媒体であって、前記操作が第１の操作であり、前記方法は、
前記第１の操作の後に第２の操作を受け付けるステップと、
前記第１の操作と前記第２の操作とが延期される場合は、前記第１の操作と第２の操作とを論理的に組み合わせて１つの組み合わせ操作にするステップと、をさらに含むコンピュータ可読媒体。
【請求項１１５】
請求項１１４に記載のコンピュータ可読媒体であって、前記第１の操作と前記第２の操作とを論理的に組み合わせるステップは、前記第１の操作と第２の操作との間の相互依存関係を分析するステップを含むコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にメモリ装置に関し、特に、ある期間にわたる（複数の）入力操作ストリーム全体にわたって操作を最適化するためのメモリ装置の内容および操作の管理に関する。
【背景技術】
【０００２】
１つ以上のメモリ装置（たとえば、記憶システム、データベース、ノード）の内容に対する操作を管理するプロセスは、ファイルシステムの操作、分散コンピューティング、およびデータベースなど、さまざまなコンテキストで使用されるが、これだけに限定されるものではない。このプロセスは、最適化という観点から単一の操作ストリームを管理するには有用である。このプロセスは、さまざまな状況において最適化された正しいストリームを出力するために、複数の入力操作ストリームを管理するためにも使用できる。
【０００３】
たとえば、複数のメモリ装置の内容を同期化するという問題は、複数のメモリ装置が空白すなわち空である全く同じ状態に初めから同一のデータを追加してゆけば解決できることは自明である。この管理プロセスは、同一の操作を各装置に伝播することによる。実際には、この単純な同期化方法は余り役に立たない。その理由は、同一操作の伝播が常に可能であるとは限らないことも、このプロセス中に内容が失われ、内容が非対称的または非同一になることもありうるからである。
【０００４】
複数のメモリ装置を同期化してそれぞれの内容をほぼ同一にするという問題を扱うときは、考慮すべき入力ストリームが（少なくとも）２つ存在する。一方の入力ストリームは、メモリ装置に対して行われる通常のユーザ操作であり、もう一方の入力ストリームは、これらのメモリ装置を比較するプロセスと、一方を更新して他方とほぼ同一にするためのプロセスとを含む。通常操作と同期化プロセスの両方が同時に発生する場合は、複数のメモリ装置の内容をほぼ同一にするという目標は移動標的である。このプロセスを管理するための単純な方法は、同期化の実施中は通常操作を阻止して、標的を移動させないことである。ただし、この単純な方法は、ユーザ操作に対してメモリ装置が不当に長時間使用不能になるという欠点がある。
【０００５】
複数の操作ストリームが正しく、かつ効率的に実行されるように複数のメモリ装置に対する操作を管理する方法およびシステムは、たとえば装置間を比較または同期化する場合に必要となるが、これだけに限定されるものではない。
【発明の開示】
【課題を解決するための手段】
【０００６】
一態様において、本発明は、操作ストリームを最適化する方法である。本方法は、操作ストリームを受け付けるステップと、操作間の相互依存関係を分析するステップと、延期すべき操作のサブセットを特定し、このサブセット内の操作を延期するステップと、このサブセット内の延期された操作を適用するための最適化された順番を判定するステップとを伴う。
【０００７】
本方法は、複数のメモリ装置を含むシステムにも、あるいは複数の操作ストリームを含むシステムにも適合化させうる。複数のメモリ装置および／または複数の操作ストリームに関わる場合は、サブセット内の延期された各操作を各メモリ装置に適用するための最適化された順番が決められる。
【０００８】
別の態様において、本発明は、複数のオブジェクトと複数の対応オブジェクトとを有する複数のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法である。本方法は、これらのオブジェクトの所定の順番でサンプリングするステップを伴い、このサンプリングによって各オブジェクトの状態を変化させる。これらのオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作が受け付けられ、ターゲットオブジェクトの状態が判定される。複数のメモリ装置において複数のオブジェクトと複数の対応オブジェクトとが比較される。ターゲットオブジェクトの状態に基づき、本方法は、当該操作をターゲットオブジェクトに適用するタイミングと、当該操作を第２のメモリ装置に適用するタイミングとを判定する。ターゲットオブジェクトが修正状態であると、当該操作はターゲットオブジェクトに適用されるが、第２のメモリ装置に対しては延期される。
【０００９】
さらに別の態様において、本発明は、操作ストリームを最適化するシステムである。本システムは、操作ストリームを受け付ける第１のモジュールと、操作間の相互依存関係を分析する第２のモジュールと、延期する操作のサブセットを特定し、このサブセット内の各操作を延期する第３のモジュールと、サブセット内の延期された各操作を適用するための最適化された順番を判定する第４のモジュールとを含む。
【００１０】
本発明は、複数のメモリ装置間でデータを管理するためのシステムをさらに含む。本システムは、複数のオブジェクトを有する第１のメモリ装置と、複数の対応オブジェクトを有する第２のメモリ装置と、これらのオブジェクトのうち少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付ける入力部とを含む。プロセッサは、第１のメモリ装置内の各オブジェクトをサンプリングし、ターゲットオブジェクトの状態を判定し、修正を実施すべきか否かを判定し、当該操作をターゲットオブジェクトに適用するタイミングを判定し、当該操作を複数の対応オブジェクトに適用するタイミングを判定する。ターゲットオブジェクトが修正状態であると、プロセッサは当該操作をターゲットオブジェクトに適用するが、ターゲットオブジェクトが修正状態である場合は複数の対応オブジェクトへの操作の適用を延期する。
【００１１】
さらに別の態様において、本発明は、第１の記憶システムと第２の記憶システムとの間でデータを管理する上記方法とデータ処理を最適化する上記方法とのためのコンピュータ実行可能命令が搭載されたコンピュータ可読媒体である。
【発明を実施するための最良の形態】
【００１２】
次に、図面を参照して本発明を詳細に説明する。これらの図面は、当業者が本発明を実施できるように本発明の実施例として提供されている。本発明は、当業者には明らかなように、ソフトウェア、ハードウェア、および／またはファームウェア、あるいはこれらの何れかの組み合わせを用いて実施しうる。本願明細書においては、同期化プロセスを経る記憶システムの例示的実装に言及しながら本発明の好適な実施形態を説明する。ただし、本発明は、この例示的実装に限定されるものではない。たとえば、本発明は、特定の機能、性能属性、および／または結果を提供するように装備および構成しうる複数の資源を含むコンピューティングシステムであれば、何れのコンピューティングシステムにおいても実施できる。本発明の態様は、比較および同期化などのファイルシステムの管理およびデータの最適化以外のコンテキストにも使用しうる。
【００１３】
本願明細書で使用される「メモリ装置」とは、情報（たとえば、メタデータ、データ）を複数のオブジェクトの形態で記憶でき、これらのオブジェクトに対する操作（たとえば、リンク、作成、削除）を許容する装置である。メモリ装置は、データベース、ファイルシステム、または記憶システムでもよいが、これだけに限定されるものではない。本願明細書で使用される「同期化」とは、データ（メタデータ、可視データ、属性など）を２つ以上のシステム間でほぼ同一にするプロセスを示すものである。１つの「操作」は、当該システムのユーザから受け付けた「書き込み（Ｗｒｉｔｅ）」、「削除（Ｒｅｍｏｖｅ）」、「リンク（Ｌｉｎｋ）」、および「リネーム（Ｒｅｎａｍｅ）」などのコマンドまたは命令の集合である。「修正」は、第２のメモリ装置の内容を第１のメモリ装置の内容に一致させるために第２のメモリ装置に行われる一連の編集であり、「同期化」との主な違いは新規操作の適用を伴わない点である。「オブジェクト」とは、メモリ装置に記憶されているデータの一部を指す。ブロックレベル（ボリュームレベルとも呼称）構造を有するメモリ装置においては、１つのデータブロックを１つのオブジェクトにしうる。ファイルシステム構造を有するメモリ装置においては、１つのディレクトリ、サブディレクトリ、またはファイルを１つのオブジェクトにしうる。場合によっては、複数のデータブロックまたは複数のディレクトリ／ファイルを１つのオブジェクにしうる。
【００１４】
図１は、阻止領域１２によって第１のメモリ装置のオブジェクト１４が矢印１６で示される方向にサンプリングされる阻止式同期化プロセス１０を模式的に示す。阻止領域１２がオブジェクト１４をサンプリングしてゆくと、阻止領域１２によってオブジェクト１４のいくつかが覆われ、阻止状態になる。サンプリングの継続に伴い、複数の異なるオブジェクト１４が阻止状態になる。まだサンプリングされていないオブジェクト１４は初期状態であり、サンプリングされたオブジェクトは最終状態である。全てのオブジェクト１４が最終状態になると、サンプリングの実行が終了する。少なくとも理論上は、サンプリングの実行終了時に全てのオブジェクト１４が第２の記憶装置と同期化されている。
【００１５】
メモリ装置の通常動作中に阻止式同期化プロセス１０が発生すると、同期化中に操作コマンドが受け付けられる。１つの操作は、全てのオブジェクト１４のうち少なくとも１つのターゲットオブジェクトを対象とする。ターゲットオブジェクトが初期状態であると、当該操作は第１のメモリ装置のみに適用され、第２のメモリ装置には適用されない。初期状態では、第２のメモリ装置との比較は行われない。操作が受け付けられたときにターゲットオブジェクトが阻止状態であると（たとえば、ターゲットオブジェクトが阻止領域１２によって覆われていると）、当該操作は阻止される。サンプリングプロセスが継続してこのターゲットオブジェクトが阻止状態から最終状態に移行するまで、当該操作は阻止されている。この阻止状態においては、第２のメモリ装置内の対応オブジェクトを第１のメモリ装置内のターゲットオブジェクトとほぼ同一にするために必要な修正が全て実施される。この修正プロセスは時間がかかることもある。ターゲットオブジェクトが最終状態であると、当該操作は第１のメモリ装置に対してのみ行われ、同じ操作が第２のメモリ装置に対して繰り返される。
【００１６】
阻止式同期化プロセス１０の問題の１つは、操作が長時間阻止されたままになることである。その理由の１つは、阻止状態で実施される修正プロセスが長時間を要しうるからである。特に阻止領域１２が長い場合は、操作が長時間阻止されたままになりうる。この問題に対する１つの解決策として阻止領域１２のサイズの縮小が考えられるが、この調整によって同期化プロセス全体が減速化するという望ましくない結果がもたらされることが多い。同期化プロセスの遅さが特に問題となるのは、２つのメモリ装置間のレイテンシ（送信データのラウンドトリップ時間）が高い場合である。
【００１７】
ファイルとディレクトリとで編成されているファイルシステムにオブジェクト１４が存在する場合は、阻止式同期化プロセス１０はさらなる問題を引き起こす。たとえば、ある操作によってファイルが初期状態のディレクトリから最終状態のディレクトリに移動された場合は、完全な同期化の達成は難しい。当該ファイルが削除されたオブジェクトに阻止領域１２が到達するまでに、そこにコピーされるべきファイルが存在しない。ただし、このファイルが現在存在するディレクトリは最終状態であるので、阻止領域１２がこの最終状態を再視察することはない。この結果は、同期化プロセスの半ばで移動されたファイルが完全に見失われる「オブジェクトが行方不明」という状況である。全てのオブジェクトが最終状態になるまで全ての操作を阻止すれば、「オブジェクトが行方不明」という状況を回避できるが、この全面的な「ロック」は、多くの操作が不当に長時間阻止されうるため望ましくない。影響を受ける全てのオブジェクトに対してこの「ロック」をかけた結果として、単純操作でさえ阻止されることがある。
【００１８】
図２は、本発明による延期式同期化プロセス２０を模式的に示す。延期式同期化プロセス２０では、阻止式同期化プロセス１０に比べ、操作が阻止される領域および期間が縮小される。阻止式同期化プロセス１０では操作が阻止されている間に修正プロセスが実施されるのに対して、延期式同期化プロセス２０では、修正プロセスが阻止状態から分離されるので、潜在的に時間がかかる修正プロセスの間に操作を（阻止せずに）受け付けることができる。結果として、この延期式同期化プロセス２０において操作が阻止される時間は、必要な情報を収集し、内容を２つのメモリ装置間で比較するために必要な時間だけである。
【００１９】
この修正プロセスの分離は、修正領域２８を阻止領域２２から切り離すことによって実現される。修正領域２８によって覆われたオブジェクト２４は修正状態である。修正状態は、阻止状態と最終状態との間の遷移状態である。修正領域２８と阻止領域２２とは互いに隣接し、阻止領域２２が修正領域２８に先行することが好ましい。
【００２０】
阻止状態のオブジェクトに対しては修正も操作も行われない。初期状態のオブジェクト２４は、上記のように初期状態のオブジェクト１４と同様に扱われる。同様に、最終状態のオブジェクト２４も最終状態のオブジェクト１４と同様に扱われる。第２のメモリ装置内の対応オブジェクトをターゲットオブジェクトの内容に一致させるための第２のメモリ装置の修正は修正状態において実施される。修正状態において受け付けられた操作は全て受け入れられるが、最終状態まで延期される。したがって、最終状態においては、延期されていた操作と新たに受け付けられた操作とがオブジェクト２４と第２のメモリ装置内の対応オブジェクトとに適用される。
【００２１】
阻止領域２２と修正領域２８とによって、初期状態のオブジェクト２４は最終状態のオブジェクト２４に変換される。阻止領域２２と修正領域２８とによって、これらのオブジェクト２４は矢印２６で示されている方向にサンプリングされる。阻止状態から出たオブジェクトが直ちに修正状態に入るように、阻止領域２２は修正領域２８に隣接していることが好ましい。修正状態のオブジェクトに対しては、次の２種類の変更が行われる。すなわち、１）これらのオブジェクトを第２のメモリ装置内の対応オブジェクトとほぼ同一にするために必要な修正、および２）最近受け付けた操作である。修正を行うには、第１のメモリ装置と第２のメモリ装置とを比較する必要がある。修正状態のオブジェクト２４に対して行われる変更の大半は、ローカルに適用されるだけであり、この状態では第２のメモリ装置に対しては一切の変更が適用されない。ただし、これらの変更は記憶され（たとえば、キャッシュされ）、オブジェクト２４が最終状態になるまで延期され、最終状態になった時点で第２のメモリ装置に適用される。
【００２２】
阻止領域２２は、その固有のプロセスまたはスレッドに応じて所定のサンプリング経路を前進する。オブジェクト２４が修正状態を出て最終状態に入った後で、待ち行列内の延期されている操作が第２のメモリ装置に送られる（すなわち、延期されていた操作が「再生される」）。オブジェクト２４が最終状態になると、その後に受け付けられた到来操作が第１のメモリ装置に適用され、遅延なく第２のメモリ装置にも適用される。
【００２３】
オブジェクト２４がこの潜在的に時間がかかる修正状態である間、オブジェクト２４は新たな操作を受け付けられる状態にある。したがって、所与の時点で修正状態であるオブジェクトの数が極めて多数になっても、第１のメモリ装置の大部分が操作に利用できなくなる心配はない。
【００２４】
延期式同期化プロセス２０の有用性は、延期された操作が占有するメモリ空間が小さいという事実によって強化される。プロセス２０がメモリ空間の使用量の点で効率的である理由は、修正状態で行われる全ての変更を（たとえば、キャッシュに）記憶する必要がないからである。実施される全ての変更を記憶する代わりに、当該操作に関わるオブジェクトの識別子、操作中の名前、操作範囲、および属性のみを記憶するだけで済む。たとえば、延期される操作が「書き込み（Ｗｒｉｔｅ）」の場合は、その書き込みのオフセットと長さのみを記憶すればよく、書き込まれる全てのデータを記憶する必要はない。影響を受ける各オブジェクトが最終状態に達し、延期されていた「書き込み」操作が再生されると、同期化コードによってデータの指示部分が第１のメモリ装置から複製される。
【００２５】
入力された操作を低速化することによって、たとえば、その内容を参照によって本願明細書に援用するものとする、２００５年１月２４日提出の米国特許出願第１０／９９７，１９８号明細書「記憶システムのためのサービス品質を管理するシステムおよび方法」に記載されている方法を用いることによって、延期される操作の数をある程度制限できる。到来操作を低速化する別の方法として、延期された操作をさらに追加できるスレッドというコンテキストで、延期された操作の再生を行ってもよい。修正領域２８のサイズを調整することによって延期される操作の数を制限してもよい。
【００２６】
いくつかの修正および／または延期された操作を複数のスレッドで実施してもよい。複数のスレッドを使用すると、混乱を来たすことなく、さらに多くの修正および／または延期される操作を容易に追加できる。
【００２７】
さまざまな目的のために、上記の４つの状態以外の情報を追跡してもよい。たとえば、同期化プロセスがあるディレクトリの内容を修正するために、見失った全てのオブジェクトをそのディレクトリに先ず作成し、次にそのディレクトリに残っている余分なオブジェクトを削除する場合、我々はこの修正状態を作成段階と削除段階の２段階に分割することができる。この結果、作成段階の経過後に「削除」操作を受け付けた場合は、我々は、影響を受けるオブジェクトが依然として修正状態であっても、この操作を延期せずに直ちに第２のメモリ装置に複製することができる。このような場合、延期された操作を記憶する必要はない。その理由は、必要なオブジェクトが作成されているので、第２のメモリ装置に送られた「削除」操作が成功するからである。作成段階が完了する前に複製を行われることになると、削除対象のオブジェクトがまだ作成されていないため、この操作は失敗するはずである。
【００２８】
状態情報を永続的にメモリ装置に保存することもできるが、状態情報をキャッシュメモリに一時的に保存する方が現実的である。余分な状態情報を保存しておくと、新たにキャッシュされたオブジェクトの状態を判定するときに役立つか、または同期化プロセスに関わるオブジェクトのキャッシュからの削除を防止するため役立つことがある。同期化プロセスの開始後にオブジェクトをキャッシュすることも可能であるが、トラバースの進行に対するオブジェクトの位置が不明になるため、これらのオブジェクトは不完全な同期化状態になる。トラバースに対するオブジェクトの位置が分からないと、そのオブジェクトに割り当てるべき状態の判定が困難になる。同期化状態に関する情報が不完全なオブジェクトに対しては、延期された操作の再生を同期化プロセスの最後に行ってもよい。不完全な同期化状態を有するオブジェクトに対して延期されている操作は、これらのオブジェクトがその後に初期状態であると判定された場合は、廃棄してもよい。
【００２９】
１つの操作は複数のオブジェクトに関わりうる。たとえば、「リネーム」操作は、リネーム対象の子オブジェクトと、旧親ディレクトリと、新親ディレクトリとに関わる。この場合、受け付けた操作の扱い方を決めるときに、全てのオブジェクトの状態が考慮される。たとえば、以下に説明するように、領域にまたがる操作は、影響を受けるオブジェクトの何れもが修正状態でないときは（たとえば、一方の親が初期状態であり、他方の親が最終状態であるときは）、延期される。
【００３０】
新たに受け付けた操作の扱い方を決めるときは、影響を受けるオブジェクトの状態と共に、以前に延期された操作も考慮される。以下に説明するように、影響を受けるオブジェクトが修正状態でなくても、以前に延期された操作によって新規操作の延期が引き起こされうる。
【００３１】
オブジェクトの状態は、同期化プロセスによって影響されるばかりでなく、操作によっても影響されうる。たとえば、複数のハードリンクを有するファイルは、最終状態の修正領域で最後のリンクが削除され、残っている全てのリンクが初期状態であると、最終状態から初期状態に逆に遷移しうる。
【００３２】
延期式同期化プロセス２０の完了後は、全てのオブジェクトが最終状態になる。その後に別の同期化プロセスを実行する予定であれば、最終状態を示すために使用された信号が次に初期状態を示すように、およびこの逆が行われるように、状態指示フラグを反転できる。この方法によって、すべてのオブジェクトを視察してそれぞれの状態を変更する手間を省くことができる。
【００３３】
図３は、本発明の方法を使用しうるファイルシステム３０を示す。例示的ファイルシステム３０は、ディレクトリ（Ａ、Ｂ、Ｃ）およびサブディレクトリ（たとえばＤ、Ｅ）を含む。ファイルシステムという「木」の「葉」に相当するＦ、Ｇ、Ｈ、Ｉ、Ｊ、Ｋ、Ｌ、およびＭなどは、サブディレクトリまたはファイルでもよい。各ファイルおよびディレクトリ（サブディレクトリを含む）には、固有の数値識別子が対応付けられる（下付き文字で表記）。第１の実施形態において、オブジェクト２４は、ファイルの数値識別子に従って並べられる。したがって、阻止領域によるサンプリングはＢ1で開始され、その後にＥ2、／3、Ｈ4、Ｋ5と進んでゆく。第２の実施形態において、オブジェクト２４は、それぞれの深さに従って並べられるので、サンプリングは／で開始され、Ａ−Ｄ−Ｊ−Ｋ−Ｅ−Ｌ−Ｍ−Ｂ−．．．と進んでゆく。第３の実施形態において、阻止領域によるサンプリングは、メタデータの幅に従って行われるので、サンプリングは／で開始され、Ａ−Ｂ−Ｃ−Ｄ−Ｅ−Ｊ−Ｋ−Ｌ−Ｍ−Ｆ−．．．の順に進んでゆく。これらは、オブジェクト２４を順序付けるための例示的方法にすぎず、順序付け方法の候補を網羅したものではない。
【００３４】
上記のように、メモリ空間のブロックを「オブジェクト」にすることもできる。ブロックレベルの同期化では、低レベルブロック装置内の各ブロックがサンプリングされることになる。
【００３５】
延期された操作間の相互依存関係
延期された操作の再生は、延期された操作間の相互依存関係によって複雑になりうる。たとえば、ディレクトリＡ内のサブディレクトリＢ（Ａ／Ｂ）の「作成」操作と、サブディレクトリＢ内の下位サブディレクトリＣ（Ｂ／Ｃ）の「作成」操作とを延期すると、後者の操作の再生は、前者の操作の再生後にしか行えない。ＢとＣとが最終状態であったとしても、Ａ／Ｂ操作が実施されるまでは、Ｂ／Ｃ操作を実施することはできない。このような場合は、ディレクトリＡの状態がＡ／Ｂ操作を行える状態に変わるときに、再生待ちのＢ／Ｃ操作が存在することを知っておくことが重要である。多数の操作が延期されている場合、特に多数のマルチオブジェクト操作が延期されている場合は、相互の依存関係を追跡する方法が有用になるであろう。目標は、相互依存関係を尊重した順番で操作を再生すること、およびどの操作も必要以上に長時間延期されないように可及的速やかに各操作を再生することである。
【００３６】
相互依存関係の問題に対処するための１つの方法は、操作を単純操作とマルチオブジェクト操作の２群に分類することである。「書き込み」、「属性変更」、または「切り捨て」などの単純操作は、単一のオブジェクトにのみ関わる。「作成」、「削除」、「リンク」、または「リネーム」などのマルチオブジェクト操作は、複数のオブジェクトを含む。（「削除」が複数のオブジェクトに関わる理由は、削除される子オブジェクトとその親オブジェクトとに影響が及ぶからである。）単純操作は、ターゲットオブジェクトの待ち行列に順次、たとえば到着順に、入れられる。マルチオブジェクト操作は、以下に説明する親子管理プロセスを用いて編成される。
【００３７】
図４は、マルチオブジェクト操作において相互依存関係を追跡するために有用な親子リスト管理プロセス４０を模式的に示す。各オブジェクトは、親リストと子リストとを有する。親リストは、特定のオブジェクトが親として扱われる操作の一覧であり、子リストは、特定のオブジェクトが子として扱われる操作の一覧である。延期された各マルチオブジェクト操作は、親オブジェクトについては親リストに登録され、子オブジェクトについては子リストに登録される。「親」オブジェクトとは、ファイルシステム内で上位にあって「子」オブジェクトを含むオブジェクトを指す。
【００３８】
図４の具体例においては、「Ａ／Ｂの作成（Ｃｒ  Ａ／Ｂ）」、「Ａ／ＢからＣ／Ｂへのリネーム」、および「Ｂ／Ｄの作成（Ｃｒ  Ｂ／Ｄ）」の３つの操作が受け付けられている。「リネーム」操作は、「Ｃ／Ｂのリンク（Ｌｎ  Ｃ／Ｂ）」と「Ａ／Ｂの削除（Ｒｍ  Ａ／Ｂ）」の２つの下位操作に分割できる。図４の凡例に示されているように、Ａ、Ｂ、Ｃ、およびＤはオブジェクトを示す。オブジェクト識別子の隣にある「コロン」の上側の点は、特定のオブジェクトに対する親リストを表し、「コロン」の下側の点は子リストを表す。「コロン」のこれらの点を４つの操作に結び付けている線は、それぞれの操作が登録されているリストを示す。たとえば、オブジェクトＡの上側の点はＣｒ  Ａ／ＢとＲｍ  Ａ／Ｂとに結び付けられているので、この２つの操作においては、オブジェクトＡが親ディレクトリであることを示す。オブジェクトＡの下側の点がどの操作にも結び付けられていない事実は、オブジェクトＡが現在延期されている何れの操作においても子オブジェクトではないことを示す。
【００３９】
オブジェクトが最終状態に遷移し、延期されていた操作のいくつかの再生が可能になると（上記のように、オブジェクトが最終状態に遷移する前に操作を再生できる場合とは対照的に）、当該操作の再生が阻止されないことを確認するために、当該オブジェクトの親リストおよび子リスト上の先頭の操作が調べられる。たとえば、図４のオブジェクトＢが最終状態に遷移したと想定する。システムはオブジェクトＢの親リストを見て、Ｃｒ  Ｂ／Ｄが、延期されている操作のリスト上の先頭の（この場合は唯一の）操作であることを確認する。システムは、オブジェクトＤをチェックし、当該操作がオブジェクトＤの待ち行列内の先頭の操作でもあるかどうかを調べ、この場合はそうであることを確認する。ただし、システムがオブジェクトＢの子リストを同様の方法でチェックすると、操作Ｃｒ  Ａ／ＢによってサブディレクトリＢが出現するまでは、操作Ｃｒ  Ｂ／Ｄの再生を実際には行えないことが明らかになる。したがって、Ｃｒ  Ｂ／Ｄは、Ｃｒ  Ａ／Ｂが実施され次第実施されるように準備される。
【００４０】
次に、オブジェクトＣが最終状態に遷移したと想定する。システムは、オブジェクトＣの親リストをチェックすることによって、Ｌｎ  Ｃ／Ｂがそのリストの先頭にあることを確認する。ただし、オブジェクトＢの子リストをチェックし、操作Ｌｎ  Ｃ／Ｂがそのリストの先頭にあるか否かを調べると、先頭には無いことが分かる。Ｂのリスト上のＬｎ  Ｃ／Ｂ操作は、操作Ｃｒ  Ａ／Ｂによって阻止される。したがって、オブジェクトＣが最終状態であっても、操作Ｌｎ  Ｃ／Ｂは、操作Ｃｒ  Ａ／Ｂが完了するまで、さらに延期される。
【００４１】
あるオブジェクトに対して延期されていた操作を再生するときは、そのオブジェクトの親および子リストが調べられ、阻止されていた何れか他の操作が現在再生可能であるかどうかが確認される。リスト上の２番目の項目が再生可能である場合は２番目の項目が再生され、３番目の項目が調べられる。この調査・再生ルーチンは、リスト上の延期されている次の操作が再生不可であるまで継続する。
【００４２】
不要な阻止を回避し、無意味な依存関係の作成を回避するために、単一のオブジェクトに複数の親リストおよび／または複数の子リストを持たせてもよい。たとえば、「Ａ／Ｂの作成」と「Ａ／Ｃの作成」とがオブジェクトＡに対する２つの操作である場合は、一方の操作は他方の操作の前には実施できないので、これらの操作を２つのリストに分割することが好ましい。両方の操作を単一のリストに入れると、これらの操作を順序付けする必要が生じるため、不要な依存関係が作成される。
【００４３】
上記の子親リストに関連付けられた規則に加え、延期された操作を再生する順番を判定するための規則を追加してもよい。たとえば、何れかのオブジェクトに対する「作成」操作の再生は、このオブジェクトに対する他の全ての操作の前に行う必要がある。その理由は、操作対象のオブジェクトが先ず存在する必要があるからである。同様に当然のことであるが、あるオブジェクトの「削除」操作の再生は、そのオブジェクトに対する他の全ての操作が再生された後に行う必要がある。
【００４４】
記憶すべき延期された操作の数を減らすために、および相互依存関係の複雑度を低減するために、延期された操作のいくつかを組み合わせて１つの延期された操作にすることができる。たとえば、「Ａ／ＢからＣ／Ｂへのリネーム」とこれに続く「Ｃ／ＢからＤ／Ｂへのリネーム」とは、単一の「Ａ／ＢからＤ／Ｂへのリネーム」操作に統合できる。場合によっては、延期された操作のいくつかを廃棄できる。たとえば、「Ａ／Ｂの作成」、「Ｂへの書き込み」、および「Ａ／Ｂの削除」の一続きの操作は、最終的には開始点と同じ状態に戻るのであるから、全て廃棄できる。親ディレクトリＡに対してタイムスタンプの更新がある場合は、このタイムスタンプを保存してもよい。これらの具体例に加え、操作を組み合わせるための他の数多くのケースが存在し、適切な規則を作成しうる。隣接する複数の「書き込み」操作を組み合わせて単一の「書き込み」操作にしてもよい。複数の「書き込み」操作に、これらの「書き込み」を消去する「切り捨て」操作が続く場合は、この両方の操作を廃棄してもよい。オブジェクトの属性（たとえば、許可）を変更する一連の操作を、そのオブジェクトの最終的な属性を設定する単一の操作に置き換えてもよい。
【００４５】
延期された操作間の相互依存関係を管理する上記の方法は、複数の操作を適用前に記憶し、これらの操作をそれぞれの到来順とは異なる順番に適用できる場合に適用可能である。たとえば、本方法は、下にあるファイルシステムまたはディスクにおいて適用される複数の操作のインテントログにしてもよく、あるいは遠隔システムへの複製を待ち合わせる複数の操作のインテントログにすることもできる。具体的な例は、その内容を参照により本願明細書に援用するものとする、２００４年６月１０日に提出された米国特許出願第１０／８６６，２２９号明細書に記載されているパーシステントインテントログ（ＰＩＬ：Ｐｅｒｓｉｓｔｅｎｔ  Ｉｎｔｅｎｔ  Ｌｏｇ）である。記憶システムの同期化は、本方法の用途の一例であるが、この実装に限定されるものではない。
【００４６】
相互依存関係の管理によって、複数の操作の適用によるエラーの発生（たとえば、子の作成時に親が存在しない）が防止されるため、これらの操作の適用によって正しい結果が確実に達成される。より具体的には、相互依存関係の管理によって以下が可能になる。
１．  操作を直ちに適用できないときの判定、
２．  特定の操作を適用したときに、その特定の操作によって阻止されていた他の操作のうち、次に適用できる操作の判定、
３．  １および２に基づき、阻止される操作群の最小セットまたは適用できる操作群の最大セットの判定、および、
４．  延期された操作のうち、組み合わせて実行を効率化できる候補操作の特定。
【００４７】
ゴースト
最終状態または修正状態のオブジェクトと初期状態のオブジェクトとの両方に影響を及ぼすマルチオブジェクト操作が同期化プロセス中に発生することもある。上で説明したように、これは「オブジェクトが行方不明」という状況を招きうる（たとえば、まだ視察されていないディレクトリから最終状態のディレクトリにファイルが移動された場合）。たとえば、「Ｉ／ＤからＦ／Ｄへのリネーム」という操作を受け付けたときに、ディレクトリＩは初期状態であり、ディレクトリＦは最終状態であると想定する。この操作を実行すると、まだサンプリングされていないディレクトリＩからファイルＤが取り出され、既にサンプリングされたディレクトリＦに追加される。この場合の問題は、ディレクトリＩがサンプリングされるときに、ファイルＤがディレクトリＩに存在しないために、同期化プロセス中にファイルＤが完全に見失われることである。ファイルＤはディレクトリＦに存在するが、ディレクトリＦのサンプリングはファイルＤが存在する前に行われており、ディレクトリＦは再視察されないからである。
【００４８】
あるいは、同期化中に実施されたマルチオブジェクト操作の結果として、「多重視察」という状況も発生しうる。「多重視察」という状況が発生するのは、既に視察されたディレクトリから初期状態のディレクトリにファイルが移動された場合である。この状況では、当該ファイルが視察される回数は２回である。すなわち１回目は旧ディレクトリにおいて、２回目は新ディレクトリにおいて行われる。「オブジェクトが行方不明」または「多重視察」のような問題は、移動されるオブジェクトがファイルではなく、ディレクトリまたはサブディレクトリであると、問題の規模が拡大しうる。
【００４９】
図５は、更新されたオブジェクトの「ゴーストエントリ」を使用することによって「オブジェクトが行方不明」という状況を回避するゴースト作成プロセス５０を示す。ゴーストエントリは、同期化プロセスに対するマーカであり、オブジェクトが実際に存在するか否かにかかわらず、その位置にオブジェクトが存在するか、またはその位置にオブジェクトが存在しないかのどちらかを示すものである。ゴーストエントリは、通常のファイルシステム操作には見えず、同期化プロセスにのみ見える。したがって、ゴーストエントリが見える同期化プロセスにとっては、ゴーストエントリによって記述されているとおりにオブジェクトが見える。
【００５０】
正のゴーストエントリと負のゴーストエントリとの２種類のゴーストエントリを使用してもよい。正のゴーストエントリは、当該操作の前には存在したが、当該操作中に削除されたオブジェクトに対して使用される。正のゴーストエントリは、ゴーストエントリが存在する場所に当該オブジェクトが存在していると同期化プロセスに思わせる。負のゴーストエントリは、当該操作によって新しい名前で出現したオブジェクトを隠すために使用される。負のゴーストエントリは、そこに存在するオブジェクトが存在していないと同期化プロセスに思わせるために使用される。
【００５１】
図５は、初期状態のオブジェクトと最終状態のオブジェクトとに影響を及ぼす操作が同期化プロセスの半ばで受け付けられた場合でも、オブジェクトが行方不明という状況を回避するためのゴーストエントリの使い方を示す。ゴーストが作成されたオブジェクト（たとえば、Ｉ／Ｄ）に対する操作が発生すると、これらの操作は延期され、これらの操作のゴーストも作成される。各オブジェクトに対して一連のゴーストエントリが存在しうる。同期化プロセスには、所与の子名に対する最旧ゴーストのみが見える。次に、延期されていた各操作が再生されると、それぞれのゴーストエントリが削除され、次のゴーストエントリが見えるようになる。
【００５２】
図５の例示的ケースにおいては、独立オブジェクトＦ3と、親オブジェクトＩ5と、親オブジェクトＩ5内の子オブジェクトＤ7とが存在する。「Ｉ／ＤからＦ／Ｄへのリネーム」操作が受け付けられ実行されると、子オブジェクトＤ7は、親オブジェクトＩ5ではなく、親オブジェクトＦ3内に存在するようになる。オブジェクトＤ7の完全な行方不明を回避するために、オブジェクトＤ7のゴーストが作成される。オブジェクトＦ3の下に負のゴーストエントリを作成することによって、そこに存在するオブジェクトＤ7を隠し、場合によっては、正のゴーストエントリをオブジェクトＩ5に作成することによって、オブジェクトＤ7はオブジェクトＩ5に存在すると同期化プロセスに思わせる。両ゴーストエントリは、ゴーストが作成されて延期された「リネーム」に関連付けられるので、同期化プロセスの最後（すなわち、延期されていた全ての操作が再生された後）に、ファイルＤは正しく親オブジェクトＦに出現する。
【００５３】
図６は、複数の操作のゴーストを作成し延期しうることを示す。図６の例においては、図５の最後でゴーストが作成された状態に「Ｉ5／Ｄ9の作成」操作が追加される。この操作が実行されると、新しい子オブジェクトＤ9が親オブジェクトＩ5内に作成される。次に、新しく形成された子オブジェクトＤ9を同期化プロセスから隠すために負のゴーストが作成され、延期されゴーストが作成された「作成」操作へのリンクが張られる。最後に、ゴーストが作成されて延期された２つの操作がオブジェクトＤ7およびＤ9に関連付けられている。この２つの操作間には相互依存関係が存在するので、Ｄ9の作成前にＤ7のリネームを行う必要がある（この逆であると、Ｄ9がＤ7と共に移動される）。この２つの操作を正しい順で実行するには、図４を参照して上で説明した親子リスト管理プロセスを使用する。
【００５４】
１つの親に対して、一意な子名ごとに別個のゴーストエントリリストを存在させうる。たとえば、ファイルＢをＡ／ＢからＸ／Ｂにリネームするときは、ファイル名Ｂに固有のゴーストエントリが親Ａに対して作成されうる。ファイルＣをＡ／ＣからＹ／Ｃにリネームする場合は、親ディレクトリＡに対して第２のリストが形成される。この第２のリストはファイルＣに固有であり、ファイル名Ｂに固有のリストとは別個のものである。その後に新規ファイルＢを作成すると（そのファイル識別子はＢと呼ばれていた以前のファイルとは異なる）、別のゴーストエントリがファイル名Ｂに固有のリストに追加される。
【００５５】
図７は、メモリ装置Ａの例示的実施形態を示す。この場合のメモリ装置Ａは記憶システムである。クライアント（ＮＦＳ、ＣＩＦＳ、ローカルアプリケーション、または内部的に生成された操作など）から各種プロトコルまたはＡＰＩを介して到来した操作は、バックエンド記憶装置２２８Ａに適用される前に、インテントログ２５０Ａおよびパーシステントインテントログ２６０Ａに保存される。保存された操作間の相互依存関係は、上記のように記録される。最適性能を達成するために、操作は並列に（すなわち同時に）、通常は順不同で（すなわち、到着順とは異なる順番で）、バックエンド記憶装置２２８Ａに適用される。操作間の相互依存関係によって、システムには所与の時点で適用できる操作と、まだ適用されていない他の操作によって阻止される操作とが分かる。操作が適用されると、相互依存関係によって（直前に適用された操作によって阻止が解除されるため）、システムには次に適用できる操作が分かる。相互依存関係に基づき、システムは上記のように組み合わせが可能な操作を効率的に組み合わせることができるので、バックエンド記憶装置２２８Ａに適用する必要がある操作の数が減る。これは、インテントログ２５０Ａおよび２６０Ａに情報を保存するための要件の低減、およびバックエンド記憶装置２２８Ａに適用する必要がある操作の数の減少による性能の向上など、複数の利点がある。
【００５６】
操作をインテントログ２５０Ａおよび２６０Ａから第２の、通常は遠隔の、メモリ装置Ｂに適用することもできる（すなわち、複製できる）。メモリ装置Ｂは、メモリ装置Ａの構成要素と機能的に同様の構成要素を有し、それぞれのメモリ装置で同様の機能を果たす構成要素は、同じ参照数字とこれに続くメモリ装置識別子ＡまたはＢによって識別される。両ログ内の操作間の相互依存関係に基づき、第２のメモリ装置Ｂに対する操作の組み合わせ、最適化、および正しい並び替えを行うことができる。
【００５７】
第１のメモリ装置Ａと第２のメモリ装置Ｂとを同期化する必要がある場合、同期化プロセスは両システムに保存されているオブジェクトを所定の順番でサンプリングする。この所定の順番に基づき各システムのオブジェクトを非同期的にサンプリングすることによって性能を向上できる。サンプリングが完了すると、各オブジェクトは初期状態から中間状態を経て最終状態へと遷移する。この中間状態では、どの同期化規則を適用するかが制御される。新たに到来した操作は、各オブジェクトに対する適用可能な同期化規則によって決められているように、ローカルに適用されるか、阻止されるか、延期されるか、または第１のメモリ装置および第２のメモリ装置の両方に適用される。これらの規則の一例は上で説明した。
【００５８】
延期された操作間の相互依存関係は、上記の方法で追跡され、これらの操作を遠隔システムに適用する順番を決めるために用いられる。相互依存関係によって、操作が確実に正しく適用されるばかりでなく、性能の点から最適な順番および最適な時点を最適化できる。相互依存関係に基づき、複数の操作を効率的に組み合わせて性能を向上することもできる。それぞれ異なる領域にある複数のオブジェクトに影響を及ぼす操作が到来することもあるので、これらのオブジェクトの変更によってサンプリング順が損なわれないようにするには、ゴーストを（上記のように）使用する。
【００５９】
本発明の好適な実施形態に言及して本発明を具体的に説明してきたが、本発明の精神および範囲から逸脱することなく形態および細部の変更および修正が可能であることは当業者には容易に明らかなはずである。付属の特許請求の範囲には、このような変更および修正が含まれるものとする。上記のさまざまな実施形態は必ずしも網羅的なものではなく、本発明の精神および範囲を逸脱することなく一部の実施形態の特徴を他の実施形態の特徴と組み合わせうることも当業者には明らかなはずである。
【００６０】
たとえば、一連の操作を組み合わせて単一の操作にすること、または操作間の相互依存関係の管理の基底をなす概念は、同期化または複製を伴わない状況にも適用しうる。たとえば、２００４年６月１０日に提出された米国特許出願第１０／８６６，２２９号明細書においては、操作はパーシステントインテントログ（ＰＩＬ）に入力され、その後にその下にあるファイルシステムに排出される。どの操作を排出できるかを判定するときに、操作間の依存関係を本願明細書に開示されている方法で管理できる。同様に、排出待ちの操作を、本願明細書に開示されている方法で組み合わせることによって操作の数を減らすことができる。
【図面の簡単な説明】
【００６１】
【図１】阻止領域によって第１の記憶システムの各オブジェクトがサンプリングされる阻止式同期化プロセスを模式的に示す。
【図２】阻止領域および修正領域によって第１の記憶システムの各オブジェクトがサンプリングされる延期式同期化プロセスを模式的に示す。
【図３】本発明の方法を使用しうるファイルシステムを示す。
【図４】マルチオブジェクト操作のための相互依存関係の追跡に有用な親子リスト管理プロセスを模式的に示す。
【図５】「ゴーストエントリ」を使用することによって同期化中にオブジェクトを見失うことを回避するゴースト作成プロセスを示す。
【図６】複数の操作のゴーストを作成し延期しうることを示す。
【図７】本願明細書で開示される各方法を実現するために使用しうる例示的システムである。
【図１】
2008541204.tif 000003
【図２】
2008541204.tif 000004
【図３】
2008541204.tif 000005
【図４】
2008541204.tif 000006
【図５】
2008541204.tif 000007
【図６】
2008541204.tif 000008
【図７】
2008541204.tif 000009
【手続補正書】
【提出日】平成19年12月17日(2007.12.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
操作ストリームを最適化する方法であって、
操作ストリームを受け付けるステップと、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の前記延期された各操作を適用するための最適化された順番を判定するステップと、を含む方法。
【請求項２】
請求項１に記載の方法であって、前記サブセット内の各操作を含む、延期された操作のリストを形成するステップをさらに含み、前記リストによって前記サブセット内の前記操作間の相互依存関係が特定される方法。
【請求項３】
請求項２に記載の方法であって、
前記リスト上の延期された操作のうち特定の延期された操作を適用するステップと、
前記適用に応じて、前記特定の延期された操作を前記リストから削除するステップと、をさらに含む方法。
【請求項４】
請求項３に記載の方法であって、前記特定の延期された操作によって阻止されていた前記リスト上の他の複数の延期された操作を適用するステップをさらに含む方法。
【請求項５】
１つ以上のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法であって、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の前記延期された各操作を前記メモリ装置のそれぞれに適用するための最適化された順番を判定するステップと、を含む方法。
【請求項６】
複数のオブジェクトと複数の対応オブジェクトとを有する複数のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法であって、
前記複数のオブジェクトを所定の順番でサンプリングするステップであって、前記サンプリングによって前記複数のオブジェクトの状態を変更するステップと、
前記複数のオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付けるステップと、
前記ターゲットオブジェクトの状態を判定するステップと、
前記複数のメモリ装置において前記複数のオブジェクトと前記複数の対応オブジェクトとを比較するステップと、
前記ターゲットオブジェクトの前記状態に基づき、前記操作を前記ターゲットオブジェクトに適用するタイミングと前記操作を前記第２のメモリ装置に適用するタイミングとを判定するステップと、
前記ターゲットオブジェクトが修正状態の場合は、前記操作を前記ターゲットオブジェクトに適用し、前記第２のメモリ装置への前記操作の適用を延期するステップと、を含む方法。
【請求項７】
操作ストリームを最適化するシステムであって、
操作ストリームを受け付ける第１のモジュールと、
操作間の相互依存関係を分析する第２のモジュールと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期する第３のモジュールと、
前記サブセット内の延期された各操作を適用するための最適化された順番を判定する第４のモジュールと、を含むシステム。
【請求項８】
請求項７に記載のシステムであって、前記サブセット内の各操作を含む、延期された操作のリストを形成する第５のモジュールをさらに含み、前記リストによって前記サブセット内の操作間の相互依存関係が特定されるシステム。
【請求項９】
請求項８に記載のシステムであって、前記第５のモジュールは、前記延期された操作のリスト内の特定の延期された操作を適用し、前記適用に応じて、前記特定の延期された操作を前記リストから削除するシステム。
【請求項１０】
請求項９に記載のシステムであって、前記第５のモジュールは、前記特定の延期された操作によって阻止されていた前記リスト上の他の延期されていた操作を適用するシステム。
【請求項１１】
請求項７に記載のシステムであって、前記相互依存関係に基づき前記操作のいくつかを論理的に組み合わせて単一の操作にする第５のモジュールをさらに含むシステム。
【請求項１２】
請求項７に記載のシステムであって、前記サブセット内の操作を前記最適化された順番で適用する第５のモジュールをさらに含むシステム。
【請求項１３】
複数のメモリ装置間でデータを管理するシステムであって、
複数のオブジェクトを有する第１のメモリ装置と、
複数の対応オブジェクトを有する第２のメモリ装置と、
前記複数のオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付ける入力部と、
前記第１のメモリ装置内の前記複数のオブジェクトをサンプリングし、前記ターゲットオブジェクトの状態を判定し、修正を実行すべきか否かを判定し、前記操作を前記ターゲットオブジェクトに適用するタイミングを判定し、前記操作を前記複数の対応オブジェクトに適用するタイミングを判定するプロセッサと、を備え、
前記ターゲットオブジェクトが修正状態の場合は、前記プロセッサは、前記操作を前記ターゲットオブジェクトに適用するが、前記複数の対応オブジェクトへの前記操作の適用を延期するシステム。
【請求項１４】
操作ストリームを最適化する方法のための複数のコンピュータ実行可能命令が搭載されたコンピュータ可読媒体であって、前記方法が、
操作ストリームを受け付けるステップと、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の延期された各操作を適用するための最適化された順番を判定するステップと、を含む、コンピュータ可読媒体。
【請求項１５】
１つ以上のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法のための複数のコンピュータ実行可能命令を搭載したコンピュータ可読媒体であって、前記方法が、
操作間の相互依存関係を分析するステップと、
延期すべき操作のサブセットを特定し、前記サブセット内の各操作を延期するステップと、
前記サブセット内の延期された各操作を前記メモリ装置のそれぞれに適用するための最適化された順番を判定するステップと、を含むコンピュータ可読媒体。
【請求項１６】
複数のオブジェクトと複数の対応オブジェクトとを有する複数のメモリ装置によって受け付けられる複数の操作ストリームを最適化する方法のためのコンピュータ実行可能命令が搭載されているコンピュータ可読媒体であって、前記方法が、
前記複数のオブジェクトを所定の順番でサンプリングするステップであって、前記サンプリングによって前記複数のオブジェクトの状態を変更するステップと、
前記複数のオブジェクトのうちの少なくとも１つのターゲットオブジェクトに対して実行される操作を受け付けるステップと、
前記ターゲットオブジェクトの状態を判定するステップと、
前記複数のメモリ装置において前記複数のオブジェクトと前記複数の対応オブジェクトとを比較するステップと、
前記ターゲットオブジェクトの前記状態に基づき、前記操作を前記ターゲットオブジェクトに適用するタイミングと、前記操作を前記第２のメモリ装置に適用するタイミングとを判定するステップと、
前記ターゲットオブジェクトが修正状態の場合は、前記操作を前記ターゲットオブジェクトに適用し、前記第２のメモリ装置への前記操作の適用を延期するステップと、を含むコンピュータ可読媒体。