(57)【特許請求の範囲】
【請求項１】
ドキュメントを管理するファイルシステムを有し、前記ファイルシステムはドキュメント変更情報をレコードの永続的ログにストアするコンピュータシステムにおいて、少なくとも１つの他のドキュメント情報のファイルを更新する方法であって、前記永続的ログへの追加の通知を受信するステップと、前記永続的ログからレコードを読み取るステップと、前記レコードを処理して、ドキュメントに関する変更情報および他のドキュメント変更情報に対する前記ドキュメント変更情報の位置を示すシーケンス番号を取得するステップと、前記ドキュメントの変更情報に基づいて前記他のファイルを更新するステップと、前記レコードのシーケンス番号を永続的ストレージに記録するステップとを備えたことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記レコードをメモリに書き込むステップと、前記レコードを周期的にシリアル化して永続的データ構造に入れるステップと、前記永続的データ構造から前記レコードを読み取るステップとをさらに備えたことを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前記レコードをメモリに書き込むステップと、前記レコードを周期的にシリアル化してキャッシュに入れるステップと、前記キャッシュから前記レコードを読み取るステップとをさらに備えたことを特徴とする方法。
【請求項４】
請求項１に記載の方法において、前記レコードはシリアルに前記ログファイルに追加され、前記シーケンス番号は各レコードが前記ログファイルに置かれている位置に対応していることを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記他のファイルを更新するステップは、ドキュメント識別子と前記変更情報とを、前記永続的データストレージから読み取られたレコードから取得するステップと、前記ドキュメント識別子と前記変更情報とを使用して前記他のファイルを更新するステップと、前記永続的データストレージから前記レコードを除去するステップとを含むことを特徴とする方法。
【請求項６】
請求項１に記載の方法において、前記レコードのシーケンス番号を前記永続的ストレージから取り出すステップと、取り出した前記シーケンス番号に基づいて前記永続的ログからレコードを読み取るステップとをさらに備えたことを特徴とする方法。
【請求項７】
請求項６に記載の方法において、取り出した前記シーケンス番号に対応するレコードよりもシーケンスが後になっている少なくとも１つの他のレコードを前記永続的ログから読み取るステップと、前記レコードに対応するドキュメントに関する変更情報を取得するために前記レコードを処理するステップとをさらに備えたことを特徴とする方法。
【請求項８】
請求項１に記載の方法において、ディレクトリ情報を入力デバイスから受け取るステップと、複数のシーケンシャルレコードを前記ログファイルから読み取るステップと、レコードのサブセットを取得するために前記ディレクトリ情報に基づいて前記複数のレコードをフィルタリングするステップと、複数のドキュメントに関する変更情報および前記ログファイル内のレコードの位置を示すシーケンス番号を取得するために前記レコードのサブセットを処理するステップとをさらに備えたことを特徴とする方法。
【請求項９】
請求項１に記載の方法において、前記通知を待つステップをさらに備えたことを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、前記通知を待つステップは、前記通知についてポーリングするステップを備えたことを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、前記通知を待つステップは、新しいレコードであることを示すシグナルの受信を待つステップを備えたことを特徴とする方法。
【請求項１２】
請求項１に記載の方法において、前記他のファイルはドキュメントのプロパティを含むインデックスであり、および前記他のファイルを更新するステップは、前記ドキュメントの変更されたプロパティに基づいて前記インデックスを変更するステップを含むことを特徴とする方法。
【請求項１３】
請求項１に記載の方法において、前記ドキュメントは複数のボリューム上にストアされていて、前記ファイルシステムはドキュメント変更情報をシリアルにレコードからなる複数の永続的ログにストアし、各ログは１つのボリュームに対応しており、ボリューム識別子を前記ログの１つから読み取られた各レコードに付けるステップをさらに備えたことを特徴とする方法。
【請求項１４】
ドキュメントを管理するファイルシステムを有し、前記ファイルシステムは変更されたドキュメントに関する情報をレコードの永続的ログにストアし、各レコードは前記ドキュメントに対応するドキュメント識別子を収めているコンピュータシステムにおいて、少なくとも１つのインデックスであってドキュメントのプロパティを含むものを更新するためのシステムであって、前記ログから新しいレコードの通知を受け取るための手段と、前記新しいレコードを前記永続的ログから読み取るためのインタフェースと、前記ドキュメント識別子および前記ドキュメント識別子に対応するドキュメントに関する変更情報を取得するために前記レコードを処理するための手段と、前記ドキュメント識別子と前記変更情報に基づいて前記インデックスを更新するために前記レコードを処理するための手段からのドキュメントに関する前記ドキュメント変更情報および前記変更情報を取得するサーチエンジンとを備えたことを特徴とするシステム。
【請求項１５】
請求項１４に記載のシステムにおいて、各レコードは前記ログ内のレコードの相対位置を示すシーケンス番号をさらに含み、および前記レコードを処理するための手段は前記レコードから前記シーケンス番号を取得するための手段を含み、および前記新しいレコードのシーケンス番号を記録するための永続的データ構造をさらに備えたことを特徴とするシステム。
【請求項１６】
請求項１５に記載のシステムにおいて、前記永続的データ構造から前記シーケンス番号を取り出すための手段と、前記シーケンス番号に基づき数値をインタフェースに与え、前記数値に対応するレコードを読み取るための手段とをさらに備えたことを特徴とするシステム。
【請求項１７】
請求項１５に記載のシステムにおいて、前記ドキュメントは複数の個別ボリューム上にストアされていて、前記ファイルシステムは前記ドキュメント変更情報をレコードの複数の永続的ログにシリアルにストアし、各ログは１つのボリュームに対応しており、およびボリューム識別子を前記ログの１つから読み取られた各レコードに付けるための手段をさらに備え、および前記新しいレコードのシーケンス番号を記録するための前記永続的データ構造は各個別ボリュームごとにシーケンス番号を記録するための複数の位置を含むことを特徴とするシステム。
【請求項１８】
請求項１５に記載のシステムにおいて、変更されたドキュメントに関する情報を永続的なレコードのログにストアしない少なくとも１つの他のファイルシステムと、前記他のファイルシステムから他の変更通知を受け取るための手段と、前記他の変更通知に基づいて別のインデックスを更新するための手段とをさらに備えたことを特徴とするシステム。
【請求項１９】
請求項１４に記載のシステムにおいて、前記ログから読み取られたレコードをストアするためのメモリと、前記レコードをシリアル化して永続的データ構造に入れるための手段とをさらに備え、および前記レコードを処理するための手段は前記永続的データ構造を読み取るための手段を含むことを特徴とするシステム。
【請求項２０】
請求項１４に記載のシステムにおいて、前記通知を受け取るための手段は前記ファイルシステムからシグナルを受信するための手段を含むことを特徴とするシステム。
【請求項２１】
請求項１４に記載のシステムにおいて、前記通知を受け取るための手段はポーリング機構を含むことを特徴とするシステム。
【請求項２２】
ドキュメントを管理するファイルシステムを有し、前記ファイルシステムはドキュメント変更情報をレコードからなる永続的ログにストアしているコンピュータシステムにおいて、ドキュメント情報を伴う少なくとも１つのドキュメントプロパティのインデックスを更新する方法であって、前記永続的ログからレコードを読み取るステップと、前記レコードを処理して、ドキュメントに関する変更情報および前記ログファイル内のレコードの相対位置を示すシーケンス番号を取得するステップと、前記ドキュメントの変更されたプロパティに基づいて前記インデックスを変更することにより、前記ドキュメントの変更情報に基づいて前記インデックスを更新するステップと、前記レコードのシーケンス番号を永続的データ構造に記録するステップとを備えたことを特徴とする方法。
【請求項２３】
請求項２２に記載の方法において、前記レコードのシーケンス番号を前記永続的データ構造から取り出すステップと、取り出した前記シーケンス番号に基づいて前記永続的ログからレコードを読み取るステップとをさらに備えたことを特徴とする方法。
【請求項２４】
請求項２３に記載の方法において、前記レコードよりもシーケンスが後に置かれている少なくとも１つの他のレコードを、取り出した前記シーケンス番号に基づいて前記永続的ログから読み取るステップと、前記他のレコードに対応するドキュメントに関する変更情報を取得するために前記他のレコードを処理するステップとをさらに備えたことを特徴とする方法。
【請求項２５】
請求項２２に記載の方法において、ディレクトリ情報を入力デバイスから受け取るステップと、複数のシーケンシャルレコードを前記ログファイルから読み取るステップと、レコードのサブセットを取得するための前記複数のレコードを前記ディレクトリ情報に基づいてフィルタリングするステップと、複数のドキュメントに関する変更情報および前記ログファイル内のレコードの位置を示すシーケンス番号を取得するために前記レコードのサブセットを処理するステップと、前記ドキュメントの変更情報に基づいて前記インデックスを更新するステップと、最も大きいシーケンス番号を持つレコードのシーケンス番号を永続的データ構造に記録するステップとをさらに備えたことを特徴とする方法。
【請求項２６】
請求項２２に記載の方法において、新しいレコードが前記永続的ログに追加されたとの通知を待つステップと、前記通知を受け取るステップとをさらに備えたことを特徴とする方法。
【請求項２７】
請求項２６に記載の方法において、前記新しいレコードの通知を待つステップは、前記通知についてファイルシステムにポーリングするステップを備えたことを特徴とする方法。
【請求項２８】
請求項２６に記載の方法において、前記新しいレコードの通知を待つステップは、前記ファイルシステムからのシグナルの受信を待つステップを備えたことを特徴とする方法。
【請求項２９】
請求項２２に記載の方法において、前記レコードを処理するステップは、前記レコードをメモリに書き込むステップと、前記レコードを周期的にシリアル化して永続的データ構造に入れるステップと、前記レコードを前記永続的データ構造から読み取るステップとを含むことを特徴とする方法。
【請求項３０】
請求項２９に記載の方法において、前記インデックスを更新するステップは、ドキュメント識別子と前記変更情報を、前記永続的データ構造から読み取られたレコードから取得するステップと、前記ドキュメント識別子と前記変更情報をサーチエンジンに与えて前記インデックスを更新するステップと、前記レコードを前記永続的データ構造から除去するステップとを含むことを特徴とする方法。
【請求項３１】
請求項２２に記載の方法において、前記ドキュメントは複数のボリューム上にストアされており、前記ファイルシステムはドキュメント変更情報をレコードからなる複数の永続的ログにシリアルにストアし、各ログは１つのボリュームに対応しており、および前記ログの１つから読み取られた各レコードにボリューム識別子を付けるステップをさらに備え、前記レコードのシーケンス番号を永続的データ構造に記録するステップは前記シーケンス番号を前記ボリューム識別子と関連付けて記録するステップを含むことを特徴とする方法。
【請求項３２】
請求項２２に記載の方法において、レコードの読み取り時にエラーを検出するステップと、前記エラーに対する応答として、前記インデックスにインデックス付けされているドキュメントのセットを判断するステップと、  前記ファイルシステム内のドキュメントのツリーを選択し、前記ツリー内のドキュメントを選択するステップと、各選択したドキュメントが前記インデックスにインデックス付けされているか否かを判断し、インデックス付けされていなければ、前記ドキュメントを前記インデックスにインデックス付けするステップと、  前記ドキュメントが前記インデックスにインデックス付けされているが、前記ツリーに存在しないか否かを判断し、存在しなければ、前記ドキュメントのインデックス付けを前記インデックスから除去するステップと、選択したドキュメントが前記ツリーに存在し、および前記インデックスにインデックス付けされていれば、前記ツリー内のドキュメントが前記インデックス内のドキュメントと同期しているか否かを判断し、同期していなければ、前記ドキュメントに再インデックス付けするステップとをさらに備えたことを特徴とする方法。
【請求項３３】
請求項２２に記載の方法において、壊れたインデックスを検出するステップと、前記ファイルシステム内のドキュメントのツリーをスキャンすることによって前記インデックスを再構築するステップとをさらに備えたことを特徴とする方法。
【請求項３４】
データのソースへの変更に関する変更情報がレコードの永続的ログ内に与えられたコンピュータシステムにおいて、データ構造を更新する方法であって、前記永続的ログに対する変更の通知を受信するステップと、レコードを前記永続的ログから読み取るステップと、データ変更情報および前記変更情報の他の変更情報に対する相対位置を示すシーケンス番号を取得するために前記レコードを処理するステップと、前記ドキュメントの変更情報に基づいてデータ構造を更新するステップと、前記レコードのシーケンス番号を永続的ストレージに記録するステップとを備えたことを特徴とする方法。
【請求項３５】
請求項３４に記載の方法において、前記レコードを処理するステップは、前記レコードをメモリに書き込むステップと、前記レコードを周期的にシリアル化して永続的データ構造に入れるステップと、前記レコードを前記永続的データ構造から読み取るステップとを含むことを特徴とする方法。
【請求項３６】
請求項３４に記載の方法において、前記データのソースはファイルシステムであることを特徴とする方法。
【請求項３７】
請求項３４に記載の方法において、前記データのソースはデータベースであることを特徴とする方法。
【請求項３８】
請求項３４に記載の方法において、前記データ構造はファイルであることを特徴とする方法。
【請求項３９】
請求項３４に記載の方法において、前記データ構造はインデックスであることを特徴とする方法。
【請求項４０】
請求項３９に記載の方法において、前記他のファイルを更新するステップは、ドキュメント識別子と前記変更情報を、前記永続的データ構造から読み取られたレコードから取得するステップと、前記ドキュメント識別子と前記変更情報をサーチエンジンに与えて前記インデックスを更新するステップと、前記レコードを前記永続的データ構造から除去するステップとを含むことを特徴とする方法。
【発明の詳細な説明】
【０００１】
発明の分野
本発明は、一般的には、コンピュータおよびファイルシステムに関し、さらに具体的には、ファイルシステム上のドキュメントのコンテンツ（内容）およびプロパティ（属性）にインデックス（索引）付けするときなどのように、ドキュメント変更をモニタリングすることに関する。
【０００２】
発明の背景
ファイルシステムのドキュメントのインデックスを自動的に生成し、維持するプログラムのように、ファイルシステム上のファイルアクティビティをトラッキング（追跡）するプログラムは、ストレージメカニズムがストアするファイル数が絶え間なく増加すると共に重要なユーザツールとなりつつある。例えば、Ｍｉｃｒｏｓｏｆｔ Ｃｏｒｐｏｒａｔｉｏｎの製品であるインデックス・サーバは１つまたは２つ以上のファイルシステムに置かれたドキュメントのコンテンツおよびプロパティにインデックスを付け、そのインデックスをクエリー（ｑｕｅｒｙ：照会すること）し、一致するドキュメントの所在を高速に突き止めるサーチエンジンをユーザに提供している。インデックス・サーバの望ましい特徴は、それがバックグランドで実行されて、ユーザがドキュメントを変更すると、その内部インデックスを自動的に最新の状態に保つことである。新規作成されたドキュメントはインデックス付けされ、変更されたドキュメントは再インデックス付けされ、削除されたドキュメントはユーザがそのドキュメントを変更したときインデックス・サーバのインデックスから除去される。この目的のために、インデックス・サーバはドキュメントの変更を見つけるために、Ｗｉｎ３２アプリケーションプログラミングインタフェース（Ａｐｐｌｉｃａｔｉｏｎ Ｐｒｏｇｒａｍｍｉｎｇ Ｉｎｔｅｒｆａｃｅ  ＡＰＩ）のＦｉｎｄＦｉｒｓｔＣｈａｎｇｅＮｏｔｉｆｉｃａｔｉｏｎとＦｉｎｄＮｅｘｔＣｈａｎｇｅＮｏｔｉｆｉｃａｔｉｏｎを使用してファイルシステムをモニタリングしている。これらのＡＰＩはほどほどの働きをしているが、それから得られる情報はほとんどすべてのファイルアクティビティにわたっており、この中にはインデックス付け方式 （ｉｎｄｅｘｉｎｇ ｓｃｈｅｍｅ） 全体にとって重要でない過渡的情報も含まれているために効率が悪い。さらに、現存のメカニズムは、ドキュメントがインデックス付けのために利用可能になる前に（例えば、ファイルがユーザによってロックされ、オープンのままになっているとき）変更通知を出すことがたびたびある。
【０００３】
以上のようにインデックス・サーバおよびこの種の他のプログラムは重要なユーザツールとなっているが、情況によっては、これらのプログラムは停止されることがある。ユーザは、これらのバックグランドプログラムが停止されたときでもドキュメントの変更を続けることができるが、ファイルシステムのアクティビティが正しく追跡されないという事態が起こっている。例えば、インデックス・サーバはプログラムエラーが原因でクラッシュすることがあり、この状態は突然のシャットダウンとも呼ばれている。インデックス・サーバのようなダイナミックインデックス付けプログラム（ｄｙｎａｍｉｃ ｉｎｄｅｘｉｎｇ ｐｒｏｇｒａｍ）では、このようなクラッシュが起こると、最新でないインデックス（ｏｕｔ−ｏｆ−ｄａｔｅ ｉｎｄｅｘ）が得られることになる。さらに、インデックス・サーバの特徴は、低資源状態のとき（例えば、ディスクスペースが少なくなったとき）、プログラムがドキュメント変更通知を受け取ることを中止するようになっていることである。ユーザは低資源状態のときでもドキュメントの変更を続けることができるが、インデックス・サーバのインデックスは、十分なディスクスペースの空きができるまでインデックス・サーバ・プログラムは変更を受け付けないので、最新の状態が保たれないことになる。この場合も、このようなことが起こると、最新でないインデックスが得られることになる。
【０００４】
インデックスが最新の状態でなくなったとき、インデックス・サーバは、インデックス・サーバが停止された以後に、またはインデックス・サーバが変更情報を受け取ることを中止した以後に変更されたドキュメントのリストを判断する必要がある。１つの取り得る解決方法は、スタートアップのたびに始め（ｓｃｒａｔｃｈ）からすべてのファイルに単に再インデックス付けすることであるが、この解決方法はドキュメント数がわずか数千の場合でも、許容し得ないほど低速化するという問題がある。
【０００５】
より高度な解決方法は、ファイルシステム内の各ドキュメントをインデックス・サーバのインデックスに保存されている、そのファイル上の情報と比較し、これら２つの間の違いを同期化することである。インデックスに保存されるプロパティ（属性）としては、ドキュメント名、ドキュメントの物理パス、書き込み時間、つまり、ファイルが最後に変更された時間、およびドキュメントのＩＤ（これは内部インデックス内の、すべてのドキュメントにユニークな識別子である）がある。スタートアップ後、インデックス付きボリューム （ｉｎｄｅｘｅｄ ｖｏｌｕｍｅ） のツリー走査 （ｔｒｅｅ ｔｒａｖｅｒｓａｌ） が実行され、インデックス付きボリューム上のすべてのファイルがスキャンされる。このツリー走査としては、幅優先（横型）探索 （ｂｒｅａｄｔｈ−ｆｉｒｓｔ ｓｅａｒｃｈ） または深さ優先（縦型）探索 （ｄｅｐｔｈ−ｆｉｒｓｔ ｓｅａｒｃｈ） などの、周知のアルゴリズムが使用できる。ツリー走査を行うとき、プロセスはファイルシステムに存在するドキュメントがインデックスにも存在するかどうかを調べる。インデックスに存在しないが、ファイルシステムに見つかったドキュメントはインデックス・サーバのシャットダウン後に作成された新規ドキュメントであるので、そのような各ドキュメントはインデックス付けされるドキュメントのリストに追加される。これとは逆に、インデックスに存在するが、ファイルシステムに見つからなかったドキュメントはインデックス・サーバのシャットダウン後に削除されたドキュメントであるので、そのような各ドキュメントは内部インデックスから除去される。内部インデックスにも存在し、ツリー走査時にも見つかったドキュメントについては、ファイルシステムに存在するドキュメントの書き込み時間が、内部インデックスに存在するそのドキュメントの書き込み時間と比較される。ファイルシステムに存在していて、インデックスにおける書き込み時間よりも最近の書き込み時間をもつドキュメントはシャットダウン以後に変更されているので、再インデックス付けされる。
【０００６】
上述したツリー走査による解決方法はスタートアップ時にすべてのドキュメントに再インデックス付けする場合よりも、大幅に高速化されているが、この解決方法は大きなインデックスの場合にはまだ遅すぎる。例えば、インデックスに数十万のドキュメントや数百万ものドキュメントがある場合には、このプロセスを完了するのに数時間オーダの処理時間が必要になる。インデックスが成長して大きくなっていくと、この処理時間は許容し得ないほどに長くなる。
【０００７】
発明の目的と概要
従って、本発明の目的は、ファイルシステムのアクティビティ追跡プログラム （ａｃｔｉｖｉｔｙ−ｔｒａｃｋｉｎｇ ｐｒｏｇｒａｍ） または類似プログラムがシャットダウンしてからスタートアップされるまでの間にどのドキュメントが変更されたかを判断するための改良方法およびシステムを提供することにある。
【０００８】
上記目的を達成するに当たり、本発明の関連目的は、上述した特徴をもち、変更されたドキュメントの判断を大幅に高速化する方法およびシステムを提供することにある。
【０００９】
本発明の別の目的は、ドキュメントインデックス付けプログラムと共に使用される方法およびシステムを提供することにある。
【００１０】
本発明のさらに別の目的は、インデックス付けプロセスをより効率化することにある。
【００１１】
本発明のさらに別の目的は、信頼性があり、強固で、効率的で、柔軟性と拡張性のある、上記種類の方法およびシステムを提供することにある。
【００１２】
要約すると、ドキュメントのファイルシステムを搭載し、ファイルシステムがドキュメント変更情報をレコードでなる永続的ログにシリアルにストアしているコンピュータシステムにおいて、本発明は、インデックスなどのように、ドキュメント情報の少なくとも１つの他のファイルを更新する方法およびシステムを提供する。レコードは永続的ログから読み取られ、ドキュメント識別子、ドキュメントに関する変更情報、およびそのレコードがログファイルに配置されている相対位置（従って、変更の相対時間）を示しているシーケンス番号が得られるように処理される。この処理としては、レコードをメモリキューに置くこと、レコードをシリアル化して永続的ストレージに置くこと、レコードを永続的ストレージからリトリーブ（取り出す）することがある。インデックスまたは他のファイルは、レコードにストアされているドキュメントの変更情報に基づいて更新され、処理された最高レコードのシーケンス番号は永続的データ構造に記録される。
【００１３】
更新／モニタリングプログラム（例えば、インデックス付けプログラム）がシャットダウンすると、リスタート時にシーケンス番号が永続的データ構造からリトリーブされ、インデックスはリトリーブしたシーケンス番号に基づいてレコードをログから読み取ることによって更新される。
【００１４】
本発明のその他の目的および利点は、添付図面を参照して以下で詳しく説明する。
【００１５】
好適実施形態の詳細な説明
動作環境の例
図１および以下の説明は、本発明の実装が可能である適当なコンピューティング環境の概要を要約して説明することを目的としている。以下では、その必要がないかも知れないが、プログラムモジュールのように、パーソナルコンピュータによって実行されるコンピュータ実行可能な命令の一般的コンテキストの中で本発明を説明することにする。一般的に、プログラムモジュールとしては、特定のタスクを実行し、あるいは特定の抽象データ型 （ａｂｓｔｒａｃｔ ｄａｔａ ｔｙｐｅ） を実装しているルーチン、プログラム、オブジェクト、コンポーネント、データ構造などがある。
【００１６】
さらに、この分野の精通者ならば理解されるように、本発明は他のコンピュータシステム構成と共に実施可能であり、そのようなコンピュータシステム構成としては、ハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサベースのコンシューマエレクトロニクスやプログラマブルコンシューマエレクトロニクス、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどがある。また、本発明は、通信ネットワークを通してリンクされているリモート処理デバイスによってタスクが実行されるような、分散コンピューティング環境で実施することも可能である。分散コンピューティング環境では、プログラムモジュールはローカルとリモートの両方のメモリストレージデバイスに置いておくことが可能になっている。
【００１７】
図１を参照すると、本発明を実施するための例示システムは、従来のパーソナルコンピュータ２０などの形態をした汎用コンピューティングデバイスを含んでおり、このコンピューティングデバイスは処理ユニット２１、システムメモリ２２、およびシステムメモリを含む種々のシステムコンポーネントを処理ユニット２１に結合しているシステムバス２３を装備している。システムバス２３は、メモリバスやメモリコントローラ、ペリフェラルバス（ｐｅｒｉｐｈｅｒａｌ ｂｕｓ）、およびローカルバスといったように、種々のバスアーキテクチャのいずれかを使用しているものならば、どのタイプのバス構造にすることも可能である。システムメモリとしては、リードオンリメモリ （ＲＯＭ） ２４およびランダムアクセスメモリ  （ＲＡＭ） ２５がある。例えば、スタートアップ時にパーソナルコンピュータ２０内のエレメント間で情報を転送するときに役立つ基本ルーチンを収めている基本入出力システム （ＢＩＯＳ） ２６はＲＯＭ ２４に格納されている。パーソナルコンピュータ２０は、ハードディスク（図示せず）に読み書きするためのハードディスクドライブ２７、取り外し可能磁気ディスク２９に読み書きするための磁気ディスクドライブ２８、およびＣＤ−ＲＯＭや他の光媒体などの、取り外し可能光ディスク３１に読み書きするための光ディスクドライブ３０をさらに装備することも可能である。ハードディスクドライブ２７、磁気ディスクドライブ２８、および光ディスクドライブ３０は、それぞれハードディスクドライブインタフェース３２、磁気ディスクドライブインタフェース３３、および光ドライブインタフェース３４を介してシステムバス２３に接続されている。これらのドライブおよびそれに関連するコンピュータ読み取り可能媒体は、パーソナルコンピュータ２０のためのコンピュータ読み取り可能命令、データ構造、プログラムモジュールおよびその他のデータを永続的にストアしている（不揮発性ストレージ）。ここで説明している例示の環境では、ハードディスク、取り外し可能磁気ディスク２９、および取り外し可能光ディスク３１が採用されているが、この分野の精通者ならば理解されるように、コンピュータがアクセスできるデータをストアしておくことができる、他のタイプのコンピュータ読み取り可能媒体などを例示の動作環境で使用することも可能であり、そのようなものとして、磁気カセット、フラッシュメモリカード、ディジタルビデオディスク、ベルヌーイ （Ｂｅｒｎｏｕｌｌｉ） カートリッジ、ランダムアクセスメモリ（ＲＡＭ）、リードオンリメモリ（ＲＯＭ）などがある。
【００１８】
ハードディスク、磁気ディスク２９、光ディスク３１、ＲＯＭ ２４またはＲＡＭ ２５には、複数のプログラムモジュールをストアすることが可能であり、その中には、オペレーティングシステム３５（好ましくは、Ｗｉｎｄｏｗｓ ＮＴ）、１つまたは２つ以上のアプリケーションプログラム３６、その他のプログラムモジュール３７およびプログラムデータ３８が含まれている。ユーザは、キーボード４０やポインティングデバイス４２などの入力デバイスを通してコマンドと情報をパーソナルコンピュータ２０に入力することができる。その他の入力デバイス（図示せず）としては、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ （ｓａｔｅｌｌｉｔｅ ｄｉｓｈ）、スキャナなどがある。上記およびその他の入力デバイスは、システムバスに結合されているシリアルポートインタフェース４６を通して処理ユニット２１に接続されていることが多いが、パラレルポート、ゲームポートまたはユニバーサルシリアルバス （ＵＳＢ） などの、他のインタフェースを介して接続することも可能である。モニタ４７や他のタイプのディスプレイデバイスも、ビデオアダプタ４８などのインタフェースを介してシステムバス２３に接続されている。モニタ４７のほかに、パーソナルコンピュータは、スピーカやプリンタなどの、他のペリフェラルアウトプットデバイス（ｐｅｒｉｐｈｅｒａｌ ｏｕｔｐｕｔ ｄｅｖｉｃｅｓ）（図示せず）を含んでいるのが代表的である。
【００１９】
パーソナルコンピュータ２０は、リモートコンピュータ４９などの１つまたは２つ以上のリモートコンピュータとの論理コネクション （ｌｏｇｉｃａｌ ｃｏｎｎｅｃｔｉｏｎ） を使用して、ネットワーク環境で動作することが可能である。リモートコンピュータ４９は、別のパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア（対等）デバイスまたは他の共通ネットワークノードにすることもでき、図１にはメモリストレージデバイス５０だけが示されているが、パーソナルコンピュータ２０に関連して上述したエレメントの多くまたはすべてを備えているのが代表的である。図１に示す論理コネクションはローカルエリアネットワーク （ｌｏｃａｌ ａｒｅａ ｎｅｔｗｏｒｋ  ＬＡＮ） ５１と広域ネットワーク （ｗｉｄｅ ａｒｅａ ｎｅｔｗｏｒｋ  ＷＡＮ） ５２を含んでいる。このようなネットワーキング環境はオフィス、エンタープライズワイドのコンピュータネットワーク、イントラネットおよびインターネットでは常識になっている。
【００２０】
ＬＡＮネットワーキング環境で使用されるときは、パーソナルコンピュータ２０はネットワークインタフェースまたはアダプタ５３を通してローカルネットワーク５１に接続されている。ＷＡＮネットワーキング環境で使用されるときは、パーソナルコンピュータ２０は、インターネットのような広域ネットワーク５２上のコミュニケーションを確立するためのモデム５４または他の手段を備えているのが代表的である。モデム５４としては、内臓モデムと外部モデムがあるが、どちらの場合も、シリアルポートインタフェース４６を介してシステムバス２３に接続されている。ネットワーク接続環境では、パーソナルコンピュータ２０に関連して示されているプログラムモジュールまたはその一部は、リモートメモリストレージデバイスにストアしておくことが可能である。以上から理解されるように、図示されているネットワークコネクションは単なる例示であり、コンピュータ間の通信リンクを確立する他の手段を使用することも可能である。
【００２１】
ドキュメント変更のモニタリング
本発明の目的上、上述してきたパーソナルコンピュータ２０は、好ましくは、マイクロソフト社（Ｍｉｃｒｏｓｏｆｔ Ｃｏｒｐｏｒａｔｉｏｎ）のＷｉｎｄｏｗｓ ＮＴオペレーティングシステム、Ｗｉｎｄｏｗｓ ＮＴファイルシステム （ＮＴＦＳ） およびインデックス・サーバ（または別のドキュメントモニタリングプログラム）を搭載している。当然に理解されるように、本発明はインデックス付け（ｉｎｄｅｘｉｎｇ）に限定されるものではなく、ファイルシステムのファイルに対する変更をモニタリングしたり、ドキュメントをサーチエンジンでモニタリングしたりするなどの、どのタイプのプログラムにも適用され、その中にはバックアッププログラムやレプリケーション （ｒｅｐｌｉｃａｔｉｏｎ） プログラムが含まれている。さらに、本発明は、ファイルシステム以外にも、データベースのように、順序付けされた変更リスト （ｏｒｄｅｒｅｄ ｌｉｓｔ ｏｆ ｃｈａｎｇｅｓ） を変更モニタリングプロセスに渡してインデックスなどのデータ構造を変更するように配置されたデータのソースと共に動作する。しかしながら、説明を簡単にするために、以下では、ファイルシステムドキュメントのコンテンツとプロパティ（属性）のインデックス付けを、特にマイクロソフト社のインデックス・サーバ６０を使用して行う場合を中心にして、本発明を説明することにする。
【００２２】
図２に示すように、Ｗｉｎｄｏｗｓ ＮＴファイルシステム （ＮＴＦＳ） ６４はドキュメント変更の永続的リストを、更新シーケンス番号 （Ｕｐｄａｔｅ Ｓｅｑｕｅｎｃｅ Ｎｕｍｂｅｒ  ＵＳＮ） ログファイル６２に保存している。特に、ファイルが追加、削除または変更されると、ＮＴＦＳは、どのファイルであるかを特定し、ファイルに対する種々の変更を記述しているボリュームごとのストリーム（ＵＳＮログファイル６２）にＵＳＮレコードを付加する。通知は、ＮＴファイルシステム６４を経由してＵＳＮログファイル６２からインデックス・サーバ６０に渡される。
【００２３】
図３に示すように、各ＵＳＮレコード６２１−６２ｎは、更新されたドキュメントを特定しているドキュメント識別子 （ＩＤ）、更新の時間に対応するタイムスタンプ、変更のタイプを示している理由フィールド、および更新シーケンス番号 （ＵＳＮ） と呼ばれる６４ビット番号を含んでいる。ＵＳＮは特定のレコードがストリーム内に置かれているときのオフセットであり、レコードはストリームに付加されるので、ＵＳＮは単調に増加していくというプロパティを持っている。例えば、ａ．ｄｏｃと名付けたドキュメントがｂ．ｄｏｃと名付けたドキュメントの前に変更されていれば、ａ．ｄｏｃ のこの特定の変更に対するＵＳＮは、ｂ．ｄｏｃ の変更に対するＵＳＮよりも小さくなっている。なお、ＵＳＮは別の方法でも生成できることはもちろんであるので（例えば、新しいレコードごとにインクリメントされる、ディスク上の永続的ＵＳＮカウンタ）、本発明はどのような形態で実現されるかに限定されるものではない。従って、ある変更を他の変更から見たときの相対位置（時間的またはその他）を追跡するどのデータも、ＵＳＮとなることができる。
【００２４】
ドキュメント識別子は、ボリューム上のドキュメントをユニークに識別する番号 （ＦｉｌｅＲｅｆｅｒｅｎｃｅＮｕｍｂｅｒ） にすることも、ボリューム上のフルパス （ＦｉｌｅＮａｍｅ） （例えば、ｃ：＼ｄｉｒｅｃｔｏｒｙ１＼ｐａｔｅｎｔ．ｄｏｃ）にすることも可能である。このアーキテクチャでは、カーネルモードのファイルシステム６４は通知レコードを追加することを担当しているので、通知はインデックス・サーバ６０がシャットダウンした場合でも継続して追加されることになる。
【００２５】
インデックス・サーバ６０はＷｉｎｄｏｗｓ ＮＴファイルシステムのＲｅａｄＵｓｎ ＡＰＩ ６６を介してＵＳＮログ６２からその通知を取得する。図４に示すように、ＲｅａｄＵｓｎ ＡＰＩはインデックス・サーバ６０などのユーザモード変更モニタリングプログラムが、カーネルモードのＵＳＮログ６２を読み取るときのインタフェースとなっているので、該当するどのデータソースからでも（例えば、Ｗｉｎｄｏｗｓ ＮＴファイルシステム６４またはデータベース）通知を受け取ることが可能になっている。このＡＰＩ ６６を使用すると、正しいセキュリティ特権を持っていれば、どの変更モニタリングプログラムでもＵＳＮログファイル６２を読み取ることができる。ＲｅａｄＵｓｎ ＡＰＩはＳｔａｒｔＵｓｎパラメータを受け取り、ＵＳＮログファイル６２の読み取りはそのパラメータから開始される。ＲｅａｄＵｓｎからは、ＵＳＮレコード６２１−６２ｎがＵＳＮの昇順に戻される。
【００２６】
本発明の一形態によれば、インデックス・サーバ６０（または類似のモニタリングプログラム）はこれらのＵＳＮレコード通知を使用して、インデックス６８などの１つまたは２つ以上のデータ構造を維持している。通知を使用するために、ＵＳＮ通知レコード（例えば、６２２）がインデックス・サーバ６０によって受信されたとき、インデックス・サーバ６０はＣｈａｎｇｅＬｉｓｔ ７０と名付けたリンクリスト （ｌｉｎｋｅｄ ｌｉｓｔ） に通知レコードを置いておく。高速化のために、このＣｈａｎｇｅＬｉｓｔは（高速）ＲＡＭ ２５に格納されている。そのあと、インデックス・サーバ６０はシリアル化プロセス （ｓｅｒｉａｌｉｚｉｎｇ ｐｒｏｃｅｓｓ） ７２を使用して、ＣｈａｎｇｅＬｉｓｔ ７０内の通知を周期的にシリアル化してＣｈａｎｇｅＬｏｇ ７４と名付けたディスク上の永続的ログに入れる。そのあと、本発明にとっては必ずしも必要ではないが、ＣｈａｎｇｅＬｉｓｔ ７０はシリアル化された（ｓｅｒｉａｌｉｚｅｄ）ＣｈａｎｇｅＬｉｓｔ ７５と名付けられた、キャッシュの働きをする別のインメモリリスト （ｉｎ−ｍｅｍｏｒｙ ｌｉｓｔ） に移しておくこともできる。永続的ＣｈａｎｇｅＬｏｇ ７４から読み取りを行うと（これについては以下で説明する）、ディスク読み取りが行われるので、この方法によるのではなく、シリアル化されたＣｈａｎｇｅＬｉｓｔ ７５を使用すると、読み取りが高速化される。もちろん、シリアル化されたＣｈａｎｇｅＬｉｓｔ ７５が空であれば（例えば、リスタート後）、永続的ＣｈａｎｇｅＬｏｇ ７４が読み取られる。いずれの場合も、ＣｈａｎｇｅＬｉｓｔ ７０は空にされ、ＣｈａｎｇｅＬｉｓｔ ７０からシリアル化された最大ＵＳＮがＵｓｎＦｌｕｓｈｅｄテーブル７６に永続的に書き出される。なお、以下で詳しく説明するように、テーブルが使用されるのは、ＵＳＮがボリュームごとであり、インデックス・サーバ６０は複数のボリュームをサポートし、各々のボリュームは１つまたは２つ以上のインデックス６８が関連付けられている。
【００２７】
インデックス６８を維持するために、通知レコードはインデックス・サーバ６０によってＣｈａｎｇｅＬｏｇ ７４の先頭から（レコードが存在するときは、インメモリキャッシュ、つまり、シリアル化されたＣｈａｎｇｅＬｉｓｔ ７５から）サーチエンジン７８などによって読み取られる。前述したように、各通知レコード（例えば、６２２）は、どのドキュメントが変更されたか、従ってどのドキュメントにインデックスを付け直す必要があるかを示している。また、それが削除通知レコードであれば、どのドキュメントが削除されたか、従ってどのドキュメントをインデックスから除去する必要があるかを示している。ドキュメントが正しくインデックス付けされたか、あるいは除去されると（または、なんらかの理由でドキュメントにインデックス付けができないときは、失敗イベントがログに記録された後で）、対応するシリアル化された通知レコード６２２がＣｈａｎｇｅＬｏｇ ７４の先頭から除去される。永続的データ構造に書き込むとき、シャドウコピー（ｓｈａｄｏｗ ｃｏｐｙｉｎｇ） やライトアヘッドロギング（ｗｒｉｔｅ ａｈｅａｄ ｌｏｇｇｉｎｇ） などの周知のトランザクション手法は、永続的データログが突然のクラッシュが原因で壊されるのを防止するために使用される。ＲｅａｄＵｓｎ ＡＰＩ ６６は、最終ハンドルがそのファイルでクローズされたときだけファイル変更アクティビティを報告するように構成することができる。以上から理解されるように、インデックス付けの目的のために、このようにすると、ＦｉｎｄＦｉｒｓｔＣｈａｎｇｅＮｏｔｉｆｉｃａｔｉｏｎおよびＦｉｎｄＮｅｘｔＣｈａｎｇｅＮｏｔｉｆｉｃａｔｉｏｎ ＡＰＩ ８０、８２を使用するよりも効率が大幅に向上するという利点が得られる。これらのＡＰＩから得られる情報は、ほとんどすべてのファイルアクティビティにわたっており、この中には、ファイルがオープンしていて、サーチエンジンがアクセスできないことが起こったとき発生する過渡的情報も含まれているからである。しかし、図１１を参照して説明したように、これらのＡＰＩ ８０、８２はＦＡＴ（ｆｉｌｅ ａｌｌｏｃａｔｉｏｎ ｔａｂｌｅ：ファイルアロケーションテーブル）ベースのファイルシステム８４などの、他のファイルシステムの変更にインデックス付けするときはまだ必要とされているのが一般である。
【００２８】
本発明によれば、クリーンな（突然でない）シャットダウンの前に、インデックス・サーバ ６０はシリアル化周期を待つことなく、ＣｈａｎｇｅＬｉｓｔ ７０をシリアル化して永続的ＣｈａｎｇｅＬｏｇ ７４に入れ、正常にシリアル化された最後の変更通知のＵＳＮを永続的にＵｓｎＦｌｕｓｈｅｄテーブル７６に書き込んでいる。リスタートした後、インデックス・サーバ６０はこの永続的に格納された（ｓａｖｅｄ）ＵＳＮから始まっているＵＳＮログ６２を読み取っていき、各ＵＳＮレコード（例えば、６２１）内のドキュメント名と変更情報から変更のリストを得ている。以上から容易に理解されるように、ツリー走査および見つかったアレイ処理 （ｓｅｅｎ ａｒｒａｙ ｐｒｏｃｅｓｓｉｎｇ）（以下で詳しく説明する）とは異なり、変更のリストを判断する時間はインデックス６８のサイズから独立している。代表例として、変更の数が少なければ、このことは、本発明のＵＳＮベースの方法によれば、変更のリストを判断するのに要する時間は数秒から数分であることを意味するため、ツリー走査や見つかったアレイ処理手法よりも大幅に高速化するのが通常である。
【００２９】
次に、図５乃至図８のフロー図を参照して本発明のオペレーションについて説明する。インデックス・サーバ６０が初めてインストールされ、システムで実行されるとき、ファイルシステム６４内の該当するドキュメントすべてがインデックス付けされる。なお、このことはインデックス・サーバ６０が初めて実行されるとき、基本的にすべてのインデックスが空であることを意味している。初期インデックス付けを行うために、ツリー走査が図５に示すように実行される。
【００３０】
図５のステップ５００から始まるとき、変数ＵｓｎＭａｘは、ＵＳＮログ６２内の最大ＵＳＮ値にセットされる。なお、ＵＳＮログ６２内の最大ＵＳＮは、ＲｅａｄＵｓｎ ＡＰＩ ６６を使用して見つけることができる。次に、ステップ５０２で、ゼロ（０）のＵＳＮがＵｓｎＦｌｕｓｈｅｄテーブル７６に書き出される。以下で詳しく説明するように、このゼロはツリー走査によるインデックス付けが正常に完了するまでＵｓｎＦｌｕｓｈｅｄテーブル７６に残っており、正常に完了すると、ドキュメントが正しくインデックス付けされたかどうかが通知される。
【００３１】
ステップ５０４で、ツリー走査によるインデックス付けプロセスは、横優先探索または深さ優先探索アルゴリズムまたは類似のアルゴリズムを使用してファイルシステム６４のドキュメントを選択する。ステップ５０６で、選択されたドキュメントはインデックス・サーバ６０によってインデックス付けされる。別の方法として、このドキュメントをリストに入れておき、インデックス・サーバ６０によるインデックス付けをそのあとで行うことも可能である（例えば、ステップ５０８の後で）。いずれの場合も、ステップ５０８で、ツリー走査は該当するドキュメントがすべてスキャンされるまで続けられる。そのあと、ステップ５１０で、ＵＳＮログ６２内のＵＳＮの最大値ＵｓｎＭａｘはＵｓｎＦｌｕｓｈｅｄテーブル７６に書き出される。このようにして、すべての該当ドキュメントはインデックス付けされる。このような初期スキャンは通常の場合には時間がかかるが、本発明によればこの初期スキャンは繰り返されることがない。
【００３２】
なお、インデックス６８を更新する別の方法によれば、クリーンな／空のインデックスから始めるとき、ツリー走査は行われず、その代わりにＵＳＮログ６２内の各レコードはレコード１から始まって処理されるようになっている。ここで、レコード１とは、ボリュームが作成またはフォーマットし直された後の、最初のＵＳＮ通知レコードのことである。しかし、この更新プロセスでは、ＵＳＮレコード１は、以下で説明すように、アロケーションが解除されていないことが条件になっている。さらに、このタイプの更新は、ボリュームが長期間にわたって使用中であると、多数の通知レコードが存在することになり、ディスク上のファイルの現在数よりも多くなる可能性があるため、ツリー走査よりも低速であるのが一般的である。もちろん、このようなＵＳＮベースのインデックス構築プロセスは、ＵＳＮロギングをサポートしていない以前のフォーマットから、ＵＳＮロギングをサポートするようになったフォーマットにアップグレードされたボリュームの場合にも有効な働きをしない。
【００３３】
いずれの場合も、初期インデックス付けプロセスは図９に進み、そこでインデックス・サーバ６０は、ＵｓｎＦｌｕｓｈｅｄテーブル７６内の値（この値はこの時点ではＵｓｎＭａｘに等しくなっているのが普通である）から始めてＵＳＮログ６２を読み取ることによってドキュメントに対する変更をモニタリングする。しかし、初期ツリー走査は正常に完了していなかったことも起こり得る。従って、図９のステップ９００から始めて、ＵＳＮ値はＵｓｎＦｌｕｓｈｅｄテーブル７６から読み取られ、その値がゼロに等しくなっているかがテストされ、判断される。ゼロならば、このことはツリー走査が正常に完了しなかったこと（つまり、ステップ５１０が正常に完了したツリー走査に続いて正しく実行されなかったこと）を示している。その場合には、ツリー走査が再び試みられる。なお、ツリー走査にチェックポイントを設けると、ツリー走査が失敗して、ツリー走査がリスタートされるとき（この時点では、ＵｓｎＭａｘはまだゼロである）、初めからスタートする必要がなくなるので最適化されることになる。例えば、正常に走査されたサブディレクトリは、ディスク上のテーブルなどに永続的に記録しておくことができる。そのあと、ツリー走査が完了する前にクラッシュが起こった場合は、テーブルがディスクから読み取られるので、記録されたディレクトリは再び走査する必要がない。リスタートプロセスは、ディレクトリレベルを多くすると、作業量が少なくなるように改良することが可能である。
【００３４】
通常は、初期ツリー走査が正常に行われると、ＵＳＮはステップ９００でゼロに等しくなっていないので、プロセスはステップ９０２に分岐することになる。ステップ９０２で、ＳｔａｒｔＵｓｎパラメータはＵＳＮログ６２内の値にセットされるので、ＵＳＮログ６２は最後にインデックス付けされたＵＳＮから前方向に、つまり、ＵｓｎＭａｘから始まって読み取られていく。プロセスは図７に進み、そこでＵＳＮレコードは読み取られ、本発明に従ってインデックス付けされる。なお、ＵｓｎＭａｘがＵｓｎＦｌｕｓｈｅｄテーブル７６に書き出されてから（ステップ５０６）ステップ８０２が実行されるまでの間に、ドキュメントに対する変更が行われていることもあり、それにより、ＵｓｎＦｌｕｓｈｅｄテーブル７６内の値はもはやＵＳＮログ６２内の最大ＵＳＮになっていない。その場合には、通知レコードは、図７と図８を参照して下述するように読み取られ、インデックス付けされる。
【００３５】
ＵｓｎＭａｘよりも大きいかまたは等しい新しいＵＳＮ通知レコードがＵＳＮログ６２に存在しないこと、つまり、ドキュメントがまだ変更されていないため新しいレコードが追加されなかったことも、頻繁に起こり得る。本発明によれば、保留中の通知が存在しないとき、インデックス・サーバ６０はバックグランドで実行され、ドキュメント変更の通知があるのを待っている。インデックス・サーバ６０は２通りの方法で通知を待つことができる。１つは待ちをポーリングによって実現する方法であり、この方法によると、インデックス・サーバ６０は新しいＵＳＮ通知があるかどうかを周期的にチェックする。しかし、より好ましい方法は、待ちをブロッキングによって行い、新しいＵＳＮ通知があるとのシグナルを受けるまで別のスレッドを待たせる方法である。
【００３６】
図７および図８は、その代表的なオペレーションを行っているときのインデックス・サーバ６０のプロセスを示す概要図である。ステップ７００から始まって、インデックス・サーバ６０は新しいＵＳＮ通知を待つ別のスレッドを作成する（または通知について周期的にポーリングする）。なお、ポーリングモデルが使用される場合は、インデックス・サーバ６０は、ＣｈａｎｇｅＬｉｓｔ ７２を周期的にシリアル化してＣｈａｎｇｅＬｏｇ ７４に入れ（ステップ７０６−７１２）、ＣｈａｎｇｅＬｏｇ ７４内でシリアル化された変更通知に基づいてファイルにインデックス付けする（ステップ８００−８０６）といった、他のオペレーションをあるポーリングオペレーションから次のポーリングオペレーションの間に実行する。ポーリングによるか、ブロッキングによるかに関係なく、新しいＵＳＮ通知（またはエラーコードなどの他のメッセージ）が受信されると、ステップ７０２は、その通知が変更されたドキュメントに対応する有効な通知であるかどうか、またはエラーの通知であるかどうかをテストする。
【００３７】
通知が受信され、エラーが存在しないような代表的な場合には、ステップ７０２はステップ７０４に分岐し、そこでＵＳＮレコードはインメモリ・リンクされたＣｈａｎｇｅＬｉｓｔ（ＦＩＦＯキュー）７０に入れられる。前述したように、インメモリＣｈａｎｇｅＬｉｓｔ ７０は周期的にシリアル化されて永続的ＣｈａｎｇｅＬｏｇ ７４に入れられる。この目的のために、ステップ７０６はシリアル化するための該当周期を検出し、その周期に到達するまでステップ７００に戻って、新しい通知を待ち、その通知をキューに入れておく。シリアル化するためのサイクルに到達すると、ステップ７０６はステップ７０８に分岐し、そこでＣｈａｎｇｅＬｉｓｔ ７０はシリアル化されて永続的ＣｈａｎｇｅＬｏｇ ７４に入れられる。そのあと、ステップ７１０で、ＣｈａｎｇｅＬｉｓｔ ７０はインメモリの、シリアル化されたＣｈａｎｇｅＬｉｓｔ（キャッシュ）７５に移動され、ＣｈａｎｇｅＬｉｓｔ ７０は空にされる。もちろん、シリアル化周期は実際の時間隔である必要はなく、別の方法として、ＣｈａｎｇｅＬｉｓｔ ７０内の通知の数といった、他のなんらかの要因を基礎にすることも可能である。ＣｈａｎｇｅＬｉｓｔが空にされると、ステップ７１０は最後にシリアル化されてＵｓｎＦｌｕｓｈｅｄテーブル７６に入れられたＵＳＮの番号を書き込む。
【００３８】
図８は、シリアル化されてＣｈａｎｇｅＬｏｇ ７４に入れられたＵＳＮ通知レコードに基づいて行われる再インデックス付けオペレーションを示す概要図である。なお、インデックス付けは、通知を待つスレッドとは別のスレッドで実行されることが好ましいので、図８に示すステップは図７に示すステップと並行に実行される。別の方法として、ポーリングモデルでは、図８のステップは、新しいＵＳＮ通知を待っている間や周期的シリアル化時間の間にステップ８００−８０６を実行するといったように、図７のステップと統合化することも可能である。いずれの場合も、ステップ８００は、シリアル化された通知がＧｈａｎｇｅＬｏｇ ７４で未処理になっているかどうかを判断し、そうでなければ、戻って１つまたは２つ以上の通知レコードを待つことになる。なお、永続的ＣｈａｎｇｅＬｏｇ ７４で新しいレコードを待つことは、ＵＳＮログ６２で新しいＵＳＮ通知レコードを待つこととは同じでない。少なくとも１つのレコードが存在していれば、最初の通知レコードが、ステップ８０２で、ＦＩＦＯ ＣｈａｎｇｅＬｏｇ ７４の先頭から（レコードがキャッシュ７５に存在していれば、キャッシュから）読み取られる。そのあと、インデックス６８はステップ８０４で通知レコードに示されたドキュメントに従って更新され、正しく更新されると、その通知レコードはステップ８０６で、ＣｈａｎｇｅＬｏｇ ７４の先頭（またはキャッシュ７５）から除去される。ステップ８０６はステップ８００に戻り、そこで次の通知レコードがあれば、上記と同じように処理される。
【００３９】
低資源状態に起因するシャットダウンのような、計画されたシャットダウンが起こる前に、インデックス・サーバ６０はＣｈａｎｇｅＬｉｓｔ ７０を空にし、ＵＳＮログ６２からＵＳＮ通知を読み取ることを中止する。同様に、突然のシャットダウンが起こってクラッシュした後は、インデックス・サーバ６０はＵＳＮログ６２からＵＳＮ通知を読み取ることができなくなる。しかし、ファイルシステム６４は通知レコードをＵＳＮログ６２に追加することを受け持っているので、通知レコードはインデックス・サーバ６０がシャットダウンしたときでも、引き続きＵＳＮログ６２に追加されることになる。
【００４０】
本発明の別の形態によれば、インデックス・サーバ６０がリスタートした後（例えば、低資源状態がクリアされた後）、インデックス・サーバ６０は図９のリスタートプロセスに戻る。つまり、インデックス・サーバ６０は最後に正常に処理されたＵＳＮをＵｓｎＦｌｕｓｈｅｄテーブル７６から読み取り、そのＵＳＮ値から始まってＵＳＮログ６２を読み取っていく。
【００４１】
なお、図７のステップ７０２で、存在しなくなったＵＳＮログ６２の部分からレコードを読み取ろうとすると、エラーが起こることがある。具体的に説明すると、ファイルシステム６４は、ドキュメントが変更されるたびに新しい通知レコードを作成し、それをＵＳＮログ６２に付加するので、ＵＳＮログ６２はサイズが増加し続けることになる。スペースを節約するために、ＵＳＮログ６２の最大サイズ、および最大サイズまでになったときアロケーションが解除されるＵＳＮログ６２のサイズはユーザ構成可能になっている。その結果、ファイルシステム６４はＵＳＮログ６２の一部のアロケーションを、周期的にＵＳＮログ６２の先頭から解除できるようになっている。ファイルの先頭からのアロケーション解除は、「ファイルシステムでディスクスペースを解放する方法およびメカニズム（Ｍｅｔｈｏｄ ａｎｄ Ｍｅｃｈａｎｉｓｍ ｆｏｒ Ｆｒｅｅｉｎｇ Ｄｉｓｋ Ｓｐａｃｅ ｉｎ ａ Ｆｉｌｅ Ｓｙｓｔｅｍ）」という名称の米国特許出願第０８／８１３，６２１号（本願発明の譲受人に譲渡済み）に記載されており、それを引用することによってその内容全体は本明細書の一部を構成するものである。
【００４２】
アロケーションが解除されたＵＳＮレコードは読み取りができなくなるので、アロケーションが解除されたＵＳＮレコードを読み取ろうとすると、エラーコード（アロケーション解除スペースを読み取る試みが失敗したことを示している）が戻されることになる。非常に多数の通知が非常に短時間にインデックス・サーバ６０によって受信されたために、インデックス・サーバ６０が着信通知のペースについて行けなくなり、ＵＳＮログ６２の対応する部分がアロケーション解除された場合には、インデックス・サーバ６０は該当のエラーコードを受け取ることになる。このようなことが起こった場合には、インデックス・サーバ６０はそのインデックスを更新する必要があるが、アロケーションが解除されたばかりのＵＳＮログ６２を使用することができない。従って、更新を行うために、インデックス・サーバ６０は図６のステップを実行することによって、見つかったアレイ処理 （ｓｅｅｎ−ａｒｒａｙ ｐｒｏｃｅｓｓｉｎｇ） ツリー走査を実行する。
【００４３】
しかるに、ステップ７４０は、最初に、ＵＳＮログ６２内の最大ＵＳＮをＵｓｎＭａｘ変数に格納する。そのあと、ゼロのＵＳＮがステップ７４２でＵｓｎＦｌｕｓｈｅｄテーブル７６に書き込まれる。前述したように、ＵｓｎＦｌｕｓｈｅｄテーブル７６内のゼロのＵＳＮは、走査が成功したかどうかを示すフラグの働きをする。つまり、成功していれば、ＵｓｎＦｌｕｓｈｅｄテーブル７６内のＵＳＮはゼロから変更される。
【００４４】
次に、図６に詳細を示すように、見つかったアレイ処理がステップ６００から始まって実行される。最初に、ステップ６００で、見つかったアレイと名付けたブールフラグのアレイ（インデックス内のドキュメントごとに１つのフラグ）は、そのエントリの各々がｄｏｃ＿ｎｏｔ＿ｓｅｅｎの値にセットされている。次に、ステップ６０２で、ファイルシステム６２内のドキュメントはツリー走査アルゴリズムを使用して、例えば、横優先探索や深さ優先探索などの周知のアルゴリズムを使用することによって選択される。ステップ６０４は、選択したドキュメントが内部インデックス６８に存在するかどうかをテストする。ドキュメントが内部インデックス６８に存在しなければ、これはインデックス・サーバ６０が通知を処理できなかったときに追加された新しいドキュメントである。従って、インデックス付けされていないドキュメントをインデックス付けリスト （ｔｏ−ｂｅ−ｉｎｄｅｘｅｄ ｌｉｓｔ） に追加するステップ６０６が、そのドキュメントに対して実行される。
【００４５】
そのドキュメントがインデックス６８の１つまたは２つ以上に存在していれば、ステップ６０４はステップ６０８に分岐し、そこでドキュメントの見つかったアレイフラグがｄｏｃ＿ｓｅｅｎにセットされる。同期テストがステップ６１０で実行され、ドキュメントがインデックスで最後に更新された時間（インデックス書き込み時間）が、ドキュメントがファイルシステム６４に最後に書き込まれた時間と突き合わせて比較される。書き込み時間が同期を示していれば、プロセスはステップ６１２に分岐する。２つの時間が同期していなければ、ステップ６１０はステップ６０６に分岐し、そこでドキュメントはインデックス付けリストに追加され、そのあと、プロセスはステップ６１２に進む。ステップ６１２は、追加のドキュメントがツリー走査で見つからなくなるまで、ステップ６０２に戻ることによって見つかったアレイ処理を繰り返す。
【００４６】
すべてのドキュメントがスキャンされると、プロセスはステップ６１４に進む。以上から理解されるように、インデックス６８にあるが、該当ツリーの走査で見つからなかったドキュメントは削除されると同時に、インデックス・サーバ６０は、その削除に対応するＵＳＮ通知レコードを受け取ることができなくなる。従って、ステップ６１４で、そのフラグがまだｄｏｃ＿ｎｏｔ＿ｆｏｕｎｄから変更されていないドキュメントがあると、そのドキュメントはインデックス６８から除去される。最後に、ステップ６１６で、インデックス付けリスト内のドキュメントはインデックス・サーバ６０によってインデックス付けされる。
【００４７】
ステップ６１６は図７のステップ７４４に戻り、そこで、格納されていたＵｓｎＭａｘ値がＵｓｎＦｌｕｓｈｅｄテーブル７６に書き出される。なお、ツリー走査が正常に実行されなかった場合は、ゼロがＵｓｎＦｌｕｓｈｅｄテーブル７６に残っているので、ツリー走査が再試行されることになる。インデックス・サーバプロセス６０は図９へと続き、ＵｓｎＦｌｕｓｈｅｄテーブル７６内の値から始めてＵＳＮログ６２を読み取ることによってドキュメントの変更をモニタリングするが、その時点では、その値はＵｓｎＭａｘに等しくなっているのが普通である。
【００４８】
インデックス６８やＣｈａｎｇｅＬｏｇ ７４などの永続的データ構造が壊されないように注意が払われている（例えば、トランザクション型コピーをしている）場合でも、インデックス・サーバ６０は、そのような永続的データ構造が壊されるという稀なケースを扱うことができる。このような破損を調べるテストは、ファイルシステムのチェックによっても、インデックス・サーバ６０自身によっても行うことができる。図１０に概要を示すように、インデックス・サーバ６０がステップ１０００で破損に気づくと、インデックス・サーバ６０はステップ１００２ですべての内部インデックス６８を削除し、ステップ１００４でＣｈａｎｇｅＬｉｓｔ７０とＣｈａｎｇｅＬｏｇ７４を空にする。そのあと、ゼロのＵＳＮがＵｓｎＦｌｕｓｈｅｄテーブル７６に書き出され、ボリュームが初めてインデックス付けされるかのようにボリュームの初期ツリー走査が行われる。このことから容易に理解されるように、これによりインデックス６８は正しく構築される。
【００４９】
別の強化機能として、インデックス・サーバ６０を使用すると、ボリュームの一部だけにインデックス付けすることができる。例えば、ｃ：＼ｖｏｌｕｍｅ全体にインデックス付けする代わりに、ユーザはインデックスディレクトリｃ：＼ｄｉｒ１とｃ：＼ｄｉｒ２およびこれら２つのディレクトリをルートとするディレクトリツリーだけにインデックス付けすることができる。このような場合には、初期ツリー走査のときボリューム全体を走査するのではなく、関係するディレクトリツリーだけを走査すればよいことになる。ＮＴファイルシステム６４はボリューム全体のＵＳＮログ６２をボリュームごとの方式で維持しているので、特定のディレクトリリスト内のドキュメントを参照しているＵＳＮ通知だけを処理すればよいことになる。一例として、ＵＳＮ通知レコードが、ｃ：＼ｄｉｒ１＼ｐａｔｅｎｔ．ｄｏｃのような、ドキュメントのフルパスを収めていて、さらに、インデックス付けされるディレクトリのリストが｛ｃ：＼ｄｉｒ１，ｃ：＼ｄｉｒ２｝であるとする。ｃ：＼ｄｉｒ１はｃ：＼ｄｉｒ１＼ｐａｔｅｎｔ．ｄｏｃのプレフィックスであるので、この特定のＵＳＮ通知レコードは処理されるはずである。しかるに、ｃ：＼ｄｉｒ３＼ｒｅｖｉｅｗ．ｄｏｃのようなドキュメントの場合は、プレフィックスが一致しないので、そのＵＳＮ通知レコードはいずれも無視されるはずである。関係ドキュメントおよび／または通知レコードだけをフィルタリングするには、「ドキュメントとフォルダとのマッピングを使用してサーチエンジンでドキュメントをスコープテストする（Ｓｃｏｐｅ Ｔｅｓｔｉｎｇ ｏｆ Ｄｏｃｕｍｅｎｔｓ ｉｎ ａ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ Ｕｓｉｎｇ Ｄｏｃｕｍｅｎｔ ｔｏ Ｆｏｌｄｅｒ Ｍａｐｐｉｎｇ）」という名称の米国特許出願第０８／８１３，６１８号（本願発明の譲受人に譲渡済み、それを引用することによってその全内容は本明細書の一部を構成する）に記載されているようなフィルタリングメカニズムを使用することが可能である。この種のメカニズムを使用すると、ディレクトリのリストをアセンブルしてそれに基づく包含フィルタリングを行い、この種の別のリストをアセンブルして排他フィルタリングを行うことができる。
【００５０】
さらに、インデックス・サーバ６０を使用すると、インデックス付けするディレクトリのリストを、インデックス・サーバ６０の実行中に動的に変更することができる。この目的のために、ディレクトリツリーが新たにインデックス６８に追加されるとき、ツリー走査（上述した）が実行され、そのツリー内のドキュメントがインデックス６８に追加される。そのあと、ディレクトリはＵＳＮ通知レコードをフィルタリングするために使用されるディレクトリのリストに追加される。これとは逆に、ディレクトリツリーが除去されるときは、ツリーは、ＵＳＮ通知レコードをフィルタリングするために使用されるディレクトリのリストから除去される。図６を参照して前述したような、見つかったアレイ処理が次に実行され、そのディレクトリツリー内のすべてのドキュメントがインデックス・サーバ６０の内部インデックス６８から除去される。
【００５１】
本発明では必ずしも必要でないが、インデックス・サーバ６０は２つ以上のボリューム、例えば、ｃ：＼とｄ：＼にインデックス付けすることができる。両ボリュームがＮＴＦＳボリュームであれば、ＮＴファイルシステム６４は各ＮＴボリュームごとに別のＵＳＮログ６２を用意し、２つの異なるボリュームからのＵＳＮ通知レコードは相互に独立している。この独立関係を維持するために、インデックス・サーバ６０はＶｏｌｕｍｅＩｄと名付けたユニークな識別子を各ボリュームに割り当てている。ＵＳＮ通知がＵＳＮログ６２から読み取られるとき、そのボリュームのユニークなＶｏｌｕｍｅＩｄが付けられる。ＵｓｎＦｌｕｓｈｅｄテーブル７６のフォーマットはインデックス付けされるボリュームごとにＵｓｎＭａｘをストアし、新しいボリュームがインデックス付けされると大きくなる構成になっている。ＣｈａｎｇｅＬｉｓｔ７０がシリアル化されてＣｈａｎｇｅＬｏｇ７４に入れられるとき、各ＶｏｌｕｍｅＩｄのＵｓｎＭａｘがＵｓｎＦｌｕｓｈｅｄテーブル７６に書き出される。与えられたＶｏｌｕｍｅＩｄに通知がなければ、そのＶｏｌｕｍｅＩｄのＵｓｎＭａｘは更新されない。なお、インデックス・サーバ６０によってインデックス付けされるボリュームはローカルボリュームだけに限定する必要はなく、ＵＮＣ命名規則においてリモートシェア （ｒｅｍｏｔｅ ｓｈａｒｅｓ） にすること、つまり、＼＼ｓｅｒｖｅｒ＿ｎａｍｅ＼ｓｈａｒｅにすることが可能である。各リモートシェアにも、ユニークなＶｏｌｕｍｅＩｄが割り当てられる。
【００５２】
最後に、図１１に示すように、インデックス・サーバ６０および本発明は十分に柔軟性があり、拡張可能であるので、スキャンベースのＦｉｎｄＦｉｒｓｔＣｈａｎｇｅＮｏｔｉｆｉｃａｔｉｏｎとＦｉｎｄＮｅｘｔＣｈａｎｇｅＮｏｔｉｆｉｃａｔｉｏｎモニタリング方式を、本発明のＵＳＮベースのモニタリング方式と組み合わせることが可能である。また、本発明は通知メカニズムを備えていないファイルシステムとも互換性があるので、そのファイルのインデックスはこれらのファイルを周期的にスキャンして変更を見つけることによって更新される。Ｗｉｎｄｏｗｓ ＮＴオペレーティングシステムを使用すると、ＮＴＦＳやＦＡＴなどの、同時にロードされる異なるファイルシステムを、ボリューム単位でボリューム上に置いておくことができる。この目的のために、インデックス・サーバ６０はどちらのモニタリング方式が特定のボリュームで使用されているかを記憶しており、スタートアップ後そのモニタリング方式を使用する。もちろん、ＵＳＮベースのモニタリング方式や類似の方式を使用すると、これまでに説明してきたスピードと効率の面で顕著な利点が得られることになる。
【００５３】
上述してきた詳細説明から理解されるように、ドキュメントインデックス付けプログラムなどの、ファイルシステムモニタリングシステムがシャットダウンしてからリスタートするまでの間にどのドキュメントが変更されたかを判断するための改良方法およびシステムが提供されている。この方法およびシステムは、変更されたドキュメントの判断を大幅に高速化すると同時、インデックス付けプロセスを効率化している。この方法およびシステムは信頼性があり、強固で、効率的で、柔軟性と拡張性がある。
【００５４】
本発明は種々の態様に変更し、別の構造にすることが可能であるが、それらのいくつかの実施形態を図面に示し、詳細に説明してきた。しかし、当然に理解されるように、本発明は上述した具体的実施形態に限定されるものではなく、本発明は本発明の精神と範囲内に属するすべての変更、代替実施形態および均等物を包含するものである。
【図面の簡単な説明】
【図１】本発明を組み込むことが可能であるコンピュータシステムを示すブロック図である。
【図２】本発明の種々のコンポーネントを示すブロック図である。
【図３】ファイルシステムによって維持されるＵＳＮレコードのログを示すブロック図である。
【図４】本発明の種々のコンポーネントを示すブロック図である。
【図５】ドキュメントのセットに初期インデックス付けするために取られる一般的ステップを示すフロー図である。
【図６】見つかったアレイ処理と共にツリー走査を実行してドキュメントを更新するために取られる一般的ステップを示すフロー図である。
【図７】本発明の一形態に従って通知を処理するために取られる一般的ステップを示すフロー図である。
【図８】本発明の別の形態に従って通知に基づいてドキュメントにインデックス付けするために取られる一般的ステップを示すフロー図である。
【図９】本発明の別の形態に従ってインデックス付けプログラムをリスタートするために取られる一般的ステップを示すフロー図である。
【図１０】壊れたインデックスが検出されたとき取られる一般的ステップを示すフロー図である。
【図１１】複数ボリュームとファイルシステムを含む本発明の種々のコンポーネントを示す代替ブロック図である。
【図１】
0003556170.tif 000002
【図２】
0003556170.tif 000003
【図３】
0003556170.tif 000004
【図４】
0003556170.tif 000005
【図５】
0003556170.tif 000006
【図６】
0003556170.tif 000007
【図７】
0003556170.tif 000008
【図８】
0003556170.tif 000009
【図９】
0003556170.tif 000010
【図１０】
0003556170.tif 000011
【図１１】
0003556170.tif 000012