(57)【要約】【課題】  情報システムの複数サーバの動作状況の把握とキャッシュ管理を、管理者の手間を増やさず、かつ効率的に行う。【解決手段】  複数のサーバ（１０、１０…）が、相互支援により動的再構成されるマルチキャスト階層を構成し、この上でサーバ状態（１０９）、キャッシュ・ディレクトリ（１０８）、ヴァリデーションの通信（１０６）を行う。【効果】  管理者は他のいくつかのサーバを指定してサーバを立ち上げる以外、サーバ間の連携を管理する必要がない。キャッシュ・ディレクトリの交換によってサーバ間のキャッシュが共有されるとともに、ヴァリデーション時間が削減されることで、高速なユーザ反応時間が得られる。【選択図】  図１
2008165833.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークで互いに接続された１つ以上のサーバ機能を有する計算機からな
り、該計算機はそれぞれ一意な番号（ＩＤ）を持ち、それぞれ独立に動作または
停止することができ、該ＩＤを用いて該計算機間の通信先を指定し、動作中の計
算機を１つ以上の第１のグループに分類して管理するサーバ分散管理方法であっ
て、
第１のグループに属する計算機のそれぞれに、該計算機の属するグループを構
成する計算機のＩＤを通知する処理と、
管理者が動作中の計算機の初期ＩＤを１つ以上与えて第１の計算機を新たに起
動した際に、該計算機を第１のグループのいずれかに追加する処理と、
第１のグループのいずれかの台数が第１の定数を超えた場合に、第１のグルー
プを分類し直して、各グループを第１の定数以下の台数に再分類する処理と、
からなることを特徴とするサーバ分散管理方法。
【請求項２】
前記第１のグループのそれぞれがリーダを持ち、
前記追加する処理は、
前記初期ＩＤに対応する１つ以上の計算機から、該計算機が保持する動作中の
計算機の表を前記第１の計算機に送信する処理と、
第１の計算機が該表中の第２の計算機を選択する処理と、
第１の計算機をグループに追加する要求を、第１の計算機が第２の計算機経由
で、第２の計算機の属するグループのリーダである第３の計算機へ送信する処理
と、
第３の計算機が第１の計算機を該グループへ追加する処理と
からなる請求項１に記載のサーバ分散管理方法。
【請求項３】
前記動作中の計算機が、前記第１のグループの相互の上下関係を決定し、もっ
て第１のグループが階層構造を形成する請求項１に記載のサーバ分散管理方法。
【請求項４】
前記再分類する処理は、
前記第１の定数を超えたグループのリーダが新たなグループを作成する処理と
、  該超えたグループに属する計算機の一部を該新たなグループに移動する処理
と、からなる請求項１に記載のサーバ分散管理方法。
【請求項５】
前記再分類する処理は、前記第１の定数を超えたグループのリーダが、該リー
ダの属するグループを構成する計算機の一部を前記階層構造で隣接するグループ
に移動する処理を含む請求項３に記載のサーバ分散管理方法。
【請求項６】
前記第１の計算機をグループに追加する要求を送信する処理は、
前記動作中の計算機の一部または全部との通信速度を計測する処理と、
第１の計算機との通信速度が大きい計算機が属するグループへ追加の要求を送
信する処理と、
からなる請求項２に記載のサーバ分散管理方法。
【請求項７】
ネットワークで互いに接続された１つ以上のサーバ機能を有する計算機からな
り、該計算機はそれぞれ一意な番号（ＩＤ）を持ち、それぞれ独立に動作または
停止することができ、該ＩＤを用いて該計算機間の通信先を指定し、動作中の計
算機を１つ以上の第１のグループに分類して管理するサーバ分散管理方法であっ
て、
第１のグループに属する計算機のそれぞれに、該計算機の属するグループを構
成する計算機のＩＤを通知する処理と、
管理者が動作中の計算機の初期ＩＤを１つ以上与えて第１の計算機を新たに起
動した際に、該計算機を第１のグループのいずれかに追加する処理と、
第１のグループのいずれかの台数が第１の定数を超えた場合に、第１のグルー
プを分類し直して、各グループを第１の定数以下の台数に再分類する処理と、
動作中の計算機のいずれかが停止または故障または通信が不能になった場合に
、該計算機の属するグループから該計算機を削除する処理と、
前記第１のグループのいずれかの台数が第２の定数未満となった場合に、第１
のグループに属する一部または全部の計算機を第２のグループに移動させる処理
と、
からなることを特徴とするサーバ分散管理方法。
【請求項８】
前記第２のグループとして、請求項３の階層構造で隣接するグループを用いる
請求項７に記載のサーバ分散管理方法。
【請求項９】
前記第１のグループに属する計算機が、第１のグループを構成する計算機のＩ
Ｄを収集する処理を行う請求項１または請求項７に記載のサーバ分散管理方法。
【請求項１０】
前記第１のグループに属する計算機のそれぞれが、該計算機の属するするグルー
プを構成するすべての計算機のＩＤを保持する表を持つ請求項１または請求項７
に記載のサーバ分散管理方法。
【請求項１１】
前記第１のグループの１つである第３のグループに属する計算機が、第３のグル
ープを構成する計算機の一部または全部に１つのデータを送信する場合に、第３
のグループを構成する計算機の間で該データを順に回覧する請求項１または請求
項７に記載のサーバ分散管理方法。
【請求項１２】
前記第３のグループに属する計算機が、前記第３のグループを構成する１つ以上
の計算機からデータを収集する場合に、１つのメッセージを該１つ以上の計算機
の間で回覧し、回覧時に該１つ以上の計算機の各々が該メッセージにデータを付
加する請求項１または請求項７に記載のサーバ分散管理方法。
【請求項１３】
ネットワークで互いに接続されて情報を利用するクライアントと、１つ以上の
情報を保持してクライアントにより指定された情報を提供する２つ以上のサーバ
とからなり、１つのサーバが保持する情報を別のサーバに移動させるサーバ分散
管理方法であって、
第１のサーバが保持する第１の情報を第２のサーバに移動させることを１つ以
上の第３のサーバに予告する移動予告メッセージを第３のサーバに送付する処理
と、
該メッセージを受け取った第３のサーバが、第３のサーバが持つ第２の情報を
第２のサーバに移動する動作を中止する処理と、
からなることを特徴とするサーバ分散管理方法。
【請求項１４】
前記第３のサーバが、請求項１または請求項７に記載のグループに属する計算
機である請求項１３に記載のサーバ分散管理方法。
【請求項１５】
前記移動予告メッセージを請求項１１に記載の順に回覧して第３のサーバに送
付する請求項１３に記載のサーバ分散管理方法。
【請求項１６】
前記移動予告メッセージを受け取った第３のサーバは、前記第２のサーバへの
情報の移動数が第１の定数以上である場合に第２の情報を第２のサーバに移動す
る動作を中止する請求項１３に記載の情報サーバ分散管理方法。
【請求項１７】
ネットワークで互いに接続された、情報を利用するクライアントと、１つ以上
の情報を保持し、クライアントからの依頼により指定された情報を提供する２つ
以上のサーバからなり、サーバが保持するデータを破棄することができるサーバ
分散管理方法であって、
第１のサーバが保持する第１の情報を破棄する際に、第１の情報のコピーを持
つ可能性がある１つ以上の第２のサーバに、該破棄を予告する破棄予告メッセー
ジを送付する処理と、
該破棄予告メッセージを受け取った第２のサーバが自身の保持する第１の情報
のコピーの破棄を中止する処理と、
からなるサーバ分散管理方法。
【請求項１８】
前記第２のサーバが、請求項１または請求項７に記載のグループに属する計算
機である請求項１７に記載のサーバ分散管理方法。
【請求項１９】
前記破棄予告メッセージを、請求項１１に記載の順に回覧して第２のサーバに送
付する請求項１７に記載のサーバ分散管理方法。
【請求項２０】
前記第２のサーバが第２の情報を破棄する際に、回覧された前記破棄予告メッ
セージに、該破棄の予告を追加して回覧する請求項１７に記載のサーバ分散管理
方法。
【請求項２１】
前記第２のサーバが、前記第１のサーバ及び第２のサーバのうち、第１の情報
またはそのコピーを持つ可能性があるサーバの数の予測である保持数を保持し、
前記破棄予告メッセージに記載の第１の情報またはそのコピーの破棄予告数を
得、
該保持数から該破棄予告数を減じた数が１以下であれば、第２のサーバが保持
する第１の情報またはそのコピーの破棄を中止する
請求項１７に記載のサーバ分散管理方法。
【請求項２２】
ネットワークで互いに接続された、情報を利用するクライアントと、１つ以上
の情報のコピーを保持し、クライアントからの依頼により指定された情報を提供
するサーバと、１つ以上の情報を保持し、サーバまたはクライアントに情報を提
供する２つ以上の外部サーバとからなり、サーバまたはクライアントが情報のコ
ピーが最新かどうかを問合わせるヴァリデーションに対して外部サーバが答える
サーバ分散管理方法であって、
サーバが保持する情報のうち、前回のヴァリデーションから１回以上参照され
た情報を、所定の時間毎に、サーバが外部サーバにヴァリデーションを行うこと
を特徴とするサーバ分散管理方法。
【請求項２３】
前記所定の時間として、８時間以上２４時間以下の時間を用いる請求項２２に
記載のサーバ分散管理方法。
【請求項２４】
前記所定の時間毎のヴァリデーションにかえて、前記情報を外部サーバから入
手してから８時間以上２４時間以下で、かつサーバの負荷またはサーバ近辺のネ
ットワークの負荷が所定の値以下の時にヴァリデーションを行う請求項２２に記
載のサーバ分散管理方法。
【請求項２５】
前記所定の時間毎のヴァリデーションにかえて、前記情報を外部サーバから入
手してから８時間以上２４時間以下で、かつ管理者が指定した時間帯の中でヴァ
リデーションを行う請求項２２に記載の情報サーバ分散管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は計算機システムに関し、特にネットワークによって接続された複数の
計算機が、情報を流通・共有・変更するシステム（情報システム）を構築する際
のシステムの管理方法に関し、さらに具体的にはＷｏｒｌｄ―Ｗｉｄｅ  Ｗｅｂ
（ＷＷＷ）に好適なサーバ分散管理方法に関する。
【背景技術】
【０００２】
現在の情報システムは、ネットワークで接続された複数の計算機が情報を提供
、または入手することによって運営されている。主に情報を提供する計算機のハ
ードウェアとソフトウェアを総称してサーバ、主に情報を入手する計算機のハー
ドウェアとソフトウェアを総称してはクライアントと呼ぶ。
【０００３】
従来用いられている情報システムでは、サーバが複数ある場合、これらのサー
バの間にはまったく連携が存在しない（例えば第１のサーバと第２のサーバがあ
っても、互いに存在を知らないか、依存しあわない）か、強く連携しあっている
（例えば第１のサーバと第２のサーバがデータを互いに交換したり、キャッシュ
する）かのいずれかである。
【０００４】
第１のサーバの動作中に第２のサーバが新設されるか起動された場合（総称し
てサーバの追加と呼ぶ）や、第２のサーバが一時停止したり故障（サーバ自身の
故障と、サーバへの通信回線の故障の両方を含む）した場合（総称してサーバの
削除と呼ぶ）に、第１のサーバと第２のサーバを連携させるためには、従来は管
理者が第１のサーバと第２のサーバの設定を適切に行う必要があった。
【０００５】
このことは、サーバがごく少数である場合には特に問題にならなかった。しか
し、サーバが多数になった場合、新たなサーバが追加または削除される際に、管
理者に大きな負担となる。
【０００６】
近年のインターネットとＷＷＷの爆発的な成長により、サーバの数が非常に多
数にわたる場面が発生している。まずＷＷＷで用いられている技術（公知例１と
呼ぶ）を説明する。
【０００７】
ＷＷＷでは、ＷＷＷサーバが保持すべき情報を「ホームページ」と呼ばれる単
位で保持している。ホームページは、それぞれＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓ
ｏｕｒｃｅ  Ｌｏｃａｔｏｒの略）と呼ばれる名前を持っている。ＷＷＷクライ
アントのユーザが、アクセスしたいホームページのＵＲＬをＷＷＷクライアント
に指定すると、ＷＷＷの第１の処理形態では、ＷＷＷクライアントは当該ＵＲＬ
で指定されるＷＷＷサーバに対して、当該ＵＲＬに対応するホームページの送信
を依頼する。当該ＷＷＷサーバは、この要求に応えて、当該ホームページを当該
ＷＷＷクライアントに与える。
【０００８】
また第２の処理形態では、ＷＷＷクライアントが、ユーザが与えたＵＲＬで指
定されるＷＷＷサーバに依頼を行なうかわりに、「プロキシ・サーバ（または単
にプロキシ）」と呼ばれる別の種類のサーバに依頼を行なう。プロキシは、当該
ＷＷＷサーバから当該ＵＲＬに対応するホームページを得るか、さらに別のプロ
キシに当該ＵＲＬを転送する。プロキシの依頼が複数段階である場合、プロキシ
は親子関係を持つ。親子関係を持つプロキシに関しては、例えばＡ.Ｃｈａｎｋ
ｈｕｎｔｈｏｄ他の文献”Ａ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｉｎｔｅｒｎｅｔ  
Ｏｂｊｅｃｔ  Ｃａｃｈｅ”（１９９６  ＵＳＥＮＩＸ  Ｔｅｃｈｎｉｃａｌ  
Ｃｏｎｆｅｒｅｎｃｅ、ｐｐ.１５３―１６３、１９９６）に記載されている。
ＷＷＷのプロキシは、複数のクライアントによって共有されるキャッシュを持つ
ことができる。このため、多くのプロキシを擁する第２の処理形態が現在のイン
ターネットでは広く用いられている。各プロキシがどのプロキシに依頼を転送す
るかは、管理者が設定する。
【０００９】
また、ＷＷＷ以外にもいくつかの情報システムが広く用いられているが、いず
れのシステムでも複数のサーバ間の連携は、管理者が設定する固定的な関係にと
どまっている。
【００１０】
ネットワーク・ニュース・システム（以後公知例２と呼ぶ。Ｂ.Ｋａｎｔｏｒ
他著の文献”Ｎｅｔｗｏｒｋ  Ｎｅｗｓ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ
：Ａ  Ｐｒｏｐｏｓｅｄ  Ｓｔａｎｄａｒｄ  ｆｏｒ  ｔｈｅ  Ｓｔｒｅａｍ―
Ｂａｓｅｄ  Ｔｒａｎｓｍｉｓｓｉｏｎ  ｏｆ  Ｎｅｗｓ”Ｎｅｔｗｏｒｋ  Ｗ
ｏｒｋｉｎｇ  Ｇｒｏｕｐ  ＲＦＣ―９７７等に記載されている）は情報システ
ムの別の例であり、ＷＷＷ同様複数のサーバによって構成される。
【００１１】
ネットワーク・ニュース・システムの複数のサーバは、クライアントが購読お
よび投稿する「ニュース記事」のコピーを互いに配布しあっている。各サーバの
管理者は、それぞれのサーバが別のどのサーバとニュース記事の授受を行うかを
設定する。新たなサーバが追加された場合、既存のサーバの設定を手動で変更す
る必要がある。
【００１２】
さらに、ＤＮＳドメイン名前サービス（公知例３と呼ぶ。例えばＰ.Ｍｏｃｋ
ａｐｅｔｒｉｓ著の文献”Ｄｏｍａｉｎ  Ｎａｍｅｓ―Ｉｍｐｌｅｍｅｎｔａｔ
ｉｏｎ  ａｎｄ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ”Ｎｅｔｗｏｒｋ  Ｗｏｒｋｉｎ
ｇ  Ｇｒｏｕｐ  ＲＦＣ―１０３５の特に第２節に記載されている）も情報シス
テムの別の例であり、複数のサーバによって構成される。
【００１３】
ＤＮＳはインターネットのホスト名と、そのホスト名の付随情報（ＩＰアドレ
スやメールサーバ）とを対応づける。この対応情報を保持するため、複数のＤＮ
Ｓサーバが木構造を構成する。クライアントの依頼は当該木構造をたどって、複
数のサーバの間を転送され、処理される。
【００１４】
各ＤＮＳサーバが、別のどのＤＮＳサーバに依頼を転送するかは、各ＤＮＳサ
ーバの管理者が設定する。あるＤＮＳサーバが置き換わる場合には、隣接するＤ
ＮＳサーバの設定を手動で変更する必要がある。また、前記木構造の各ノードは
、２つ以上のＤＮＳサーバによって冗長構成をとっているが、これらのＤＮＳサ
ーバが故障した場合（またはこれらのＤＮＳサーバへのネットワーク経路が故障
した場合）には、やはり隣接するＤＮＳサーバの設定を手動で変更する必要があ
る。
【００１５】
ローカル・エリア・ネットワーク（ＬＡＮ）内の分散ファイルシステムにおい
て、キャッシュのための空間を複数のコンピュータで共有する「協調キャッシン
グ」とよばれる方法も知られている。例えばＭｉｃｈａｅｌ  Ｄａｈｌｉｎ他著
の文献”Ｃｏｏｐｅｒａｔｉｖｅ  Ｃａｃｈｉｎｇ：Ｕｓｉｎｇ  Ｒｅｍｏｔｅ
Ｃｌｉｅｎｔ  Ｍｅｍｏｒｙ  ｔｏ  Ｉｍｐｒｏｖｅ  Ｆｉｌｅ  Ｓｙｓｔｅ
ｍ  Ｐｅｒｆｏｒｍａｎｃｅ”（Ｆｉｒｓｔ  ＵＳＥＮＩＸ  Ｓｙｍｐｏｓｉｕ
ｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍ
ｐｌｅｍｅｎｔａｔｉｏｎ、ｐｐ.２６７―２８０、１９９４）（公知例４と呼
ぶ）では、「マネージャ」と呼ばれるサーバが、どのファイル・ブロックがどの
ファイル・サーバに格納されているかを保持している。マネージャがクライアン
トからファイル・ブロックの転送を依頼されると、クライアントにファイル・ブ
ロックが格納されているコンピュータを返答するか、当該ファイル・サーバにク
ライアントの要求を転送する。マネージャは複数存在することができるが、ファ
イル・ブロックとマネージャとの対応関係はあらかじめ定められており、この対
応関係を変更するためには管理者が手動で設定を変更する必要がある。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
ＷＷＷでは、ある統計ではサーバ数が１９９６年６月から１９９７年１月まで
の半年で２.８倍に増加するなど、急激な成長が続いている。このため、ＷＷＷ
全体の情報量も爆発的に増えている。プロキシは、複数のクライアントによって
共有されるキャッシュとしてユーザの反応時間（ユーザが情報を要求してからそ
の情報がユーザの手元に届くまでの時間）を減少させる役目があるが、ＷＷＷ全
体の情報量に比してキャッシュの容量が小さいため、現状では低い効果しか得ら
れていない。
【００１７】
本発明が解決しようとする第１の課題は、ＷＷＷのプロキシのように複数のサ
ーバを連携して動作させる際の、管理者の手間を減らすことである。これによっ
て、プロキシを多数擁する大規模なキャッシュの実現において、管理に大量の時
間と人数が必要であるという課題を解決する。具体的には、第１のサーバが追加
または削除される場合に、管理者が１つ以上の既存の第２のサーバの設定を変更
することなしに、第１のサーバの存在（または存在しないこと）を第２のサーバ
に知らせ、また第１のサーバに第２のサーバの存在（または存在しないこと）を
知らせることが課題である。
【００１８】
なお第１の課題の解決には、ＷＷＷはインターネットの上で動作しており接続
マシン数が膨大であり、かつ管理組織も多数にわたるため、ブロードキャストを
用いる方法や、単一のサーバにすべての設定を集める方法は現実的な解決法とな
らない。また、第２のサーバが多数になった場合には、第１のサーバと第２のサ
ーバのすべてが連携することすら現実的ではなくなる。このようにサーバ数が非
常に多くなった場合には、連携するべきサーバの数を制限するための仕組みが必
要となる。
【００１９】
また第１の課題が解決された場合に、複数のサーバに分散して存在するキャッ
シュを運営するために、複数のサーバ間で互いのキャッシュのリストを効率よく
交換し、以て１つのサーバのキャッシュにない情報を別のサーバに問い合わせる
方法が必要となる。この方法を実現することが第２の課題である。
【００２０】
さらに、第１および第２の課題が解決された場合に、複数のサーバに跨る大規
模なキャッシュが実現されることになるが、この際、ＷＷＷで用いられている通
信プロトコルＨＴＴＰ（Ｒ.Ｆｉｅｌｄｉｎｇ他著の文献”Ｈｙｐｅｒｔｅｘｔ
Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ―ＨＴＴＰ／１.１、”Ｎｅｔｗｏｒｋ
Ｗｏｒｋｉｎｇ  Ｇｒｏｕｐ  ＲＦＣ―２０６８等に記載されている）では、
キャッシュが十分に新しい情報を保持しているかを確認する動作（ヴァリデーシ
ョン動作と呼ぶ）を要求しているが、このヴァリデーション動作がユーザ反応時
間を悪化させていることがわかった。このため、ヴァリデーション動作がユーザ
反応時間を悪化させないようにすることも本発明が解決しようとする第３の課題
である。
【課題を解決するための手段】
【００２１】
第１の課題を解決するために本発明の情報システム分散管理方法では、サーバ
動作情報（動作しているサーバのリスト）を分散管理するための「サーバ状態伝
播プロトコル」を持つ。各サーバは、管理者から与えられた少数の他のサーバの
名前から出発して、サーバ群の相互支援によってサーバ動作情報のマルチキャス
ト階層を動的に構築する。マルチキャスト階層はサーバ群が構成する木構造のグ
ループであり、各グループは数台から数十台のサーバからなる。一部のサーバが
停止したり再起動するに従って、マルチキャスト階層の動的再構成が行われる。
【００２２】
このサーバ状態伝播プロトコルにより、上記第１の課題である複数のサーバを
連携して動作させる際の、管理者の手間が低減される。本発明では、サーバの起
動時に、他のサーバの名前をいくつか与えるだけでよく、その後複数のサーバの
うち一部が停止したり再起動する度毎に管理者が各サーバの設定を変更する必要
がないためである。また、本発明のサーバ状態伝播プロトコルは、ブロードキャ
ストを必要とせず、マルチキャストも動作中のサーバ群にのみ行われるので、イ
ンターネット上での使用に耐える。また、各サーバがサーバ動作情報を交換する
際には近接サーバ優先で通信することにより、サーバ数が膨大になった場合にも
動作する。すなわち、これにより第１の課題が解決される。
【００２３】
第２の課題を解決するために本発明の情報システム分散管理方法では、「広域
協調キャッシュ管理プロトコル」を備える。このプロトコルは、前記サーバ状態
伝播プロトコルが形成するマルチキャスト階層を用いてキャッシュ・ディレクト
リ（ＵＲＬと当該ＵＲＬをキャッシュ中に保持するサーバのリスト）の伝播と、
キャッシュ制御（どのサーバがどのＵＲＬをキャッシュ中に保持するか、いつ、
どのＵＲＬをあるサーバから別のサーバに移動させるか）を、公知例４のマネー
ジャにあたる集中管理サーバなしで行う。
【００２４】
サーバがある情報を別のサーバに移動させる場合があるが、この場合には移動
先サーバを決定する必要がある。この目的で、サーバが受け入れ可能なキャッシ
ュ価値の最小値（受け入れ可能キャッシュ価値と呼ぶ）を他サーバに回覧する。
また、１つのグループの複数のサーバが一斉に情報の移動を予定している場合、
移動先が１つのサーバに集中する恐れがある。この問題を解決するために、各サ
ーバは移動しようとする情報および予定移動先のリストを回覧する。これにより
各サーバは、他のサーバが選んでいない移動先を避けて移動先サーバを決定する
ことができる。さらに、近接する複数のサーバが同一情報のキャッシュを保持し
ている場合、このキャッシュのコピーすべてが一斉に破棄されないように工夫す
ることが必要である。集中サーバを用いずに近似的な方法でこの状態に近づける
ために、破棄しようとする情報のリスト（破棄予定リストと呼ぶ）をサーバの間
で回覧する。自分が破棄しようとする情報のキャッシュがグループのメンバが保
持する最後のコピーである場合には、予定した破棄を中止する。以上により第２
の課題が解決される。
【００２５】
第３の課題を解決するために本発明の情報システム分散管理方法では、従来の
ようにユーザが情報を要求した時点でヴァリデーション動作を行うのではなく、
ユーザの要求以前にあらかじめヴァリデーション動作を行っておく「先行ヴァリ
デーション」を備える。先行ヴァリデーションは、一定時間ごとや、ＵＲＬが参
照されてから一定時間経過後などに行う。この先行ヴァリデーションをＨＴＴＰ
のプロトコルで許された範囲内で行う。これにより従来ユーザ反応時間の多くの
部分を占めていたヴァリデーション動作による消費時間をユーザ反応時間から取
り除くことができ、第３の課題が解決される。
【発明の効果】
【００２６】
サーバ動作情報（動作しているサーバのリスト）を分散管理するためのサーバ
状態伝播プロトコルを持ったことにより、ＷＷＷのプロキシのように複数のサー
バを連携して動作させる際の、管理者の手間を減らすことができる。管理者は他
のいくつかのサーバを指定してサーバを立ち上げる以外、サーバ間の連携を管理
する必要がない。
【００２７】
サーバ状態伝播プロトコルが形成するマルチキャスト階層を用いてキャッシュ
・ディレクトリの伝播と、キャッシュ制御を、集中管理サーバなしで行う広域協
調キャッシュ管理プロトコルを備えたことにより、複数のサーバに分散して存在
するキャッシュを運営するために、複数のサーバ間で互いのキャッシュのリスト
を効率よく交換し、以て１つのサーバのキャッシュにない情報を別のサーバに問
い合わせることができる。
【００２８】
ユーザの要求以前にあらかじめヴァリデーション動作を行っておく「先行ヴァ
リデーション」を備えたことにより、ヴァリデーション動作がユーザ反応時間を
悪化させないようにすることができる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明の実施の一形態を図面を参照しながら説明する。簡単のため「発
明の実施の形態」を「実施例」と呼ぶ。
【００３０】
図１と図２を用いて実施例の構成を説明する。
【００３１】
外部サーバ１３、１３’、１３”、…は、情報システムが提供する情報を保持
し、要求に応じてクライアント１１またはサーバ１０、１０’、１０”、…に情
報を提供する計算機である。サーバ１０、１０’、１０”、…は情報システムの
キャッシュを保持するサーバである。クライアント１１はユーザが利用する計算
機で、ネットワーク１２を通じて外部サーバ１３、１３’、１３”、…またはサ
ーバ１０、１０’、１０”、…から提供された情報をユーザに表示する。サーバ
１０、１０’、１０”、…は外部サーバ１３、１３’、１３”、…の中で、最近
クライアント１１が利用した情報や、クライアント１１が今後利用すると予想さ
れる情報をキャッシュとして保持する。このキャッシュの目的にはいくつか考え
うるが、代表的な目的はクライアント１１が情報を得るのに要する時間を高速化
することである。クライアント１１が外部サーバ１３、１３’、１３”、…の代
わりにサーバ１０、１０’、１０”、…にアクセスすることにより、外部サーバ
１３、１３’、１３”、…がネットワーク１２の遠くにある場合でも高速に情報
にアクセスできる。
【００３２】
この実施例の計算機は、いわゆるパーソナル・コンピュータ、ワークステーシ
ョン、並列計算機、大型計算機等、任意のコンピュータでよい。クライアント１
１はサーバ１０、１０’、１０”、…と通信し、情報を表示する機能があればよ
いので、各種コンピュータ端末装置、携帯通信端末（いわゆるパーソナル・デジ
タル・アシスタンスＰＤＡやハンドヘルド・パーソナル・コンピュータＨＰＣ）
、ネットワーク・コンピュータなどでも差し支えない。
【００３３】
外部サーバ１３、１３’、１３”、…、クライアント１１、サーバ１０、１０
’、１０”、…は計算機ではなく、計算機とソフトウェアの組合わせで実現して
も差し支えない。特に、計算機自身には変更を加えず、計算機上で動作するプロ
グラム（プロセス）によって、本発明を実施しても差し支えない。
【００３４】
ネットワーク１２は、ある団体（企業や学校や類似の団体）の全体や位置部門
でよく使用されるＬＡＮでもよく、また地理的に分散した複数の地点を結合する
ＷＡＮの一部または全部でもよい。またネットワーク１２は、計算機間結合網や
並列計算機内部のプロセッサ要素間の結合網でもよい。
【００３５】
サーバ１０はクライアント要求処理部１００、キャッシュ管理部１０１、サー
バ管理部１０２、通信部１０６の各処理部分を含み、キャッシュ表１０７、キャ
ッシュ・ディレクトリ１０８、サーバ状態表１０９、グループ表１１０の各デー
タ構造を含む。また、キャッシュ管理部１０１は更にキャッシュ価値評価部１０
４とキャッシュ移動破棄部１０５の各処理部分を含む。また、サーバ１０、１０
’、１０”、…はそれぞれ一意な番号であるサーバＩＤ（または単にＩＤ）を持
つ。サーバＩＤとしては、サーバＩＤからサーバの通信用アドレスを対応づけ、
通信を行うことができるＩＤを用いる。例えば、ＩＰアドレスをサーバＩＤとし
て用いても差し支えない。
【００３６】
クライアント要求処理部１００は、クライアント１１が情報の取得を要求した
際に、応対を行う部分である。クライアント要求処理部１００からのメッセージ
送信は通信部１０６を経由して（１２７）、ネットワーク１２に送出される。逆
にネットワーク１２からクライアント要求処理部１００へのメッセージは、通信
部１０６を経由してクライアント要求処理部１００に送られる（１２６）。クラ
イアント要求処理部１００はキャッシュ表１０７に対する読み出し（１４６）を
行う。キャッシュ表１０７に対する書き込み（１４７）を行う場合もあるが、稀
である。
【００３７】
キャッシュ管理部１０１は、サーバ１０が保持するキャッシュを管理する部分
である。キャッシュ管理部１０１は、通信部１０６を経由してネットワーク１２
へのメッセージの受信と送信を行う（１２８と１２９）。またキャッシュ管理部
１０１はキャッシュ表１０７に対する書き込みと読み込み（１３４と１３５）、
キャッシュ・ディレクトリ１０８に対する書き込みと読み込み（１３６と１３７
）、およびサーバ状態表１０９に対する書き込みと読み込み（１３８と１３９）
を行う。キャッシュ管理部１０１中のキャッシュ価値評価部１０４は、特定の情
報のキャッシュを保持することがどのくらい有用かを判定する部分である。また
キャッシュ管理部１０１中のキャッシュ移動破棄部１０５は、ある情報のキャッ
シュをサーバ１０に置いておくべきでない場合に、当該キャッシュを破棄したり
、１つ以上の他のサーバ１０’、１０”、…に当該キャッシュを移動する部分で
ある。
【００３８】
サーバ管理部１０２は、他のサーバ１０’、１０”、…をリストアップし、こ
れらのサーバの動作状況を管理する部分である。サーバ管理部１０２は、通信部
１０６を経由してネットワーク１２へのメッセージの受信と送信を行う（１３０
と１３１）。またサーバ管理部１０２はサーバ状態表１０９に対する書き込みと
読み込み（１４０と１４１）、およびグループ表１１０に対する書き込みと読み
込み（１４２と１４３）を行う。
【００３９】
ヴァリデーション管理部１０３は、先行ヴァリデーションの制御を行う部分で
ある。ヴァリデーション管理部１０３は、通信部１０６を経由してネットワーク
１２へのメッセージの受信と送信を行う（１３２と１３３）。ヴァリデーション
管理部１０３はキャッシュ表１０７に対する書き込みと読み込み（１４４と１４
５）を行う。
【００４０】
通信部１０６は、クライアント１１、他のサーバ１０’、１０”、…、外部サ
ーバ１３、１３’、１３”、…と通信を行う部分である。クライアント１１から
の受信と送信は１２０と１２１による。他のサーバ１０’、１０”、…からの受
信と送信は１２２と１２３による。外部サーバ１３、１３’、１３”、…からの
受信と送信は１２４と１２５による。
【００４１】
キャッシュ表１０７は、サーバ１０のキャッシュの実体およびキャッシュの各
種属性を保持する表である。キャッシュ表１０７は１つ以上のキャッシュ表エン
トリ２００からなる。１つのキャッシュ表エントリ２００は１つの情報の１つの
キャッシュに対応しており、ＵＲＬ２０１が当該情報のＵＲＬを保持し、サイズ
２０２が当該情報のバイト数を保持し、日付２０３が当該情報の最終更新日付を
保持し、参照回数２０４が当該情報の最近の参照回数を保持する。キャッシュ内
容２０５は当該情報のコピーを保持する。
【００４２】
キャッシュ・ディレクトリ１０８は、サーバ１０、１０’、１０”、…のどれ
が、どの情報のキャッシュを持っているかという情報を保持する表である。キャ
ッシュ・ディレクトリ１０８は１つ以上のキャッシュ・ディレクトリ・エントリ
２１０からなる。１つのキャッシュ・ディレクトリ・エントリ２１０が、１つの
別のサーバが持つ１つの情報に対応しており、ＵＲＬ２１１が当該情報のＵＲＬ
を、サーバＩＤ２１２が当該サーバのサーバＩＤを保持する。
【００４３】
サーバ状態表１０９は、サーバ１０、１０’、１０”、…のうちいくつかのＩ
Ｄと動作状態等の属性とを保持する表である。サーバ状態表１０９は１つ以上の
サーバ状態表エントリ２２０からなる。１つのサーバ状態表１０９が１つのサー
バに対応しており、サーバＩＤ２２１が当該サーバのサーバＩＤを保持し、スル
ープット２２２が当該サーバへ至る通信回線のスループット（ビット／秒）、レ
イテンシ２２３が当該サーバへ至る通信回線のレイテンシ（秒）を保持する。サ
ーバ状態表１０９にあるサーバのエントリがないか、スループット２２２が０で
あるか、レイテンシ２２３が「無限大」であれば、当該サーバが動作中でないか
、当該サーバへ至る通信回線に障害が発生していることを意味する。
【００４４】
グループ表１１０は、サーバ状態表１０９に格納されているサーバ群のうち、
いくつかの近接のサーバ群を選んで保持する表である。１つのグループは最大Ｍ
ＡＸ台（ＭＡＸは定数）のサーバ（メンバ）からなる。各グループのサーバ群は
、サーバＩＤによってグループ内で順序づけされる。グループ内で最も若いサー
バＩＤを持つサーバを「リーダ」と呼ぶ。リーダは、１つ上のグループ（上位グ
ループ）の一員となることができ、グループ間でマルチキャスト通信を行う際に
は、その通信の中継役となる。もしリーダに障害が発生した場合には、リーダの
次に若いサーバＩＤを持つサーバが代行リーダとなる。この構造を表現するため
にグループ表１１０は、リーダのサーバＩＤを保持するリーダ・サーバＩＤ２３
１、メンバのサーバＩＤを保持するサーバＩＤ２３２、２３２’、…、上位グル
ープのリーダを保持する上位リーダ・サーバＩＤ  ２３３、上位グループのメン
バのサーバＩＤを保持する上位サーバＩＤ  ２３４、２３４’、…からなる。
【００４５】
次に、図３を用いて、サーバ１０、１０’、１０”、…が相互に通信する際に
用いるメッセージの種類と、その形式を説明する。
【００４６】
グループ参加メッセージ３００は、新たにグループに参加しようとするサーバ
が発するメッセージである。１つのサーバがグループに参加しようとする場合と
、複数のサーバがグループに参加（または変更）しようとする場合の両方に用い
る。グループ参加メッセージ３００は新規サーバＩＤ  ３０１、３０１’、…を
格納しており、それぞれが新たにグループに参加しようとするサーバ群のＩＤで
ある。
【００４７】
階層維持メッセージ３１０は、グループのメンバの動作状況を確認するために
用いるメッセージである。通常、あるグループのリーダが発し、当該グループお
よび他のいくつかのグループの動作中のメンバの間を回覧されて、再びリーダに
戻る。階層維持メッセージ３１０は、当該メッセージを最初に発したサーバのＩ
Ｄである送信元サーバＩＤ３１１と、動作中のサーバ群のＩＤである新規サーバ
ＩＤ３１２、３１２’、…と、ネスト数３１３からなる。ネスト数３１３は、複
数のグループに跨って１つの階層維持メッセージ３１０を回覧する際に用い、何
段先のグループまで階層維持メッセージ３１０を回覧するかを指定する。
【００４８】
グループ更新メッセージ３２０は、グループに参加することが許可されたサー
バに（通常リーダから）送られるメッセージである。グループ更新メッセージ３
２０は、参加すべきグループのリーダのＩＤである新リーダ・サーバＩＤ３２１
を格納する。
【００４９】
ヴァリデーション依頼メッセージ３３０は、先行ヴァリデーションを行う時に
、先行ヴァリデーションを依頼するサーバから、先行ヴァリデーションの依頼を
受けるサーバに送られるメッセージで、先行ヴァリデーションの対象となる１つ
以上のＵＲＬを持つ。ヴァリデーション依頼メッセージ３３０は１つ以上のヴァ
リデーション依頼メッセージ・エントリ３３１からなり、各エントリは依頼元サ
ーバのＩＤであるサーバＩＤ３３２、先行ヴァリデーションの対象となるＵＲＬ
であるＵＲＬ３３３、依頼元サーバが知っているＵＲＬの最終更新日付である日
付３３４を格納する。
【００５０】
キャッシュ価値メッセージ３４０は、サーバ同士が各自のキャッシュ全体のキ
ャッシュ価値の指標を交換し合うために用いるメッセージである。キャッシュ価
値メッセージ３４０は１つ以上のキャッシュ価値メッセージ・エントリ３４１か
らなり、各エントリはサーバを指定するサーバＩＤ３４２と、当該サーバのキャ
ッシュ価値の指標であるキャッシュ価値３４３を含む。
【００５１】
移動予告メッセージ３５０は、第１のサーバが、キャッシュの中で（一般には
キャッシュ価値の低い）１つ以上の情報を第２のサーバに移動させる予定である
ことを、他の複数のサーバに知らせる際に用いる。移動予告メッセージ３５０は
１つ以上の移動予告メッセージ・エントリ３５１からなり、移動予告メッセージ
・エントリ３５１は第１のサーバのＩＤであるサーバＩＤ３５２、当該情報のＵ
ＲＬであるＵＲＬ３５３、および第２のサーバのＩＤである移動先サーバＩＤ３
５４を格納する。
【００５２】
破棄予告メッセージ３６０は、第１のサーバが、キャッシュの中で（一般には
キャッシュ価値の低い）１つ以上の情報を破棄する予定であることを、他の複数
のサーバに知らせる際に用いる。破棄予告メッセージ３６０は１つ以上の破棄予
告メッセージ・エントリ３６１からなり、各エントリは第１のサーバのＩＤであ
るサーバＩＤ３６２と、当該情報のＵＲＬであるＵＲＬ３５３を格納する。
【００５３】
ホストＵＲＬメッセージ３７０は、サーバ同士が各自のキャッシュにどのよう
な情報が格納されているかを交換し合うために用いるメッセージである。ホスト
ＵＲＬメッセージ３７０は１つ以上のホストＵＲＬメッセージ・エントリ３７１
からなり、各エントリはキャッシュを持つサーバのＩＤであるサーバＩＤ３７２
、１つの情報のＵＲＬであるＵＲＬ３７３、および当該ＵＲＬが存在するか存在
しないかを示すフラグ３７４を格納する。
【００５４】
サーバ状態伝播
本発明の情報システム分散管理方法では、サーバ動作情報（動作しているサー
バのリスト）を分散管理するための「サーバ状態伝播プロトコル」を持つ。以下
、このプロトコルの動作を説明する。
【００５５】
（１）階層形成処理
まず図４を用いて、主にサーバ初期化時に行う階層形成処理を説明する。以下
の処理手順の説明では、説明をわかりやすくするために動作の骨子に絞って説明
を行う。すなわち、エラー処理やタイミング依存の動作等は省略する。
【００５６】
管理者は、０個または１つ以上の他のサーバのサーバＩＤを与えて、サーバ１
０を起動する。サーバ１０が起動されるとすべての表を「空」に初期化した後サ
ーバ管理部１０２に制御を移し、与えられたサーバＩＤをサーバ状態表１０９に
格納してから、他のサーバ１０’、１０”、…の動作状態を調べ、他のサーバ１
０’、１０”、…をより多く取得し、１つのグループに参加する動作を行う。
【００５７】
ステップ４０１で、サーバ状態表１０９が空であるかを判定する。判定結果が
Ｙ（ＹＥＳの略）であれば（４０２）、他のサーバが一切わからないので、ステ
ップ４０３で、サーバ状態表１０９に新たなサーバ状態表エントリ２２０を追加
し、当該エントリのサーバＩＤ２２１に自分のＩＤを、スループット２２２に「
無限大」を、レイテンシ２２３に「０」を格納する。そして、階層形成処理を終
了する（４１７）。
【００５８】
一方、ステップ４０１の判定結果がＮ（ＮＯの略）であれば（４０４）、サー
バ状態表１０９から第１のサーバを１つ選択し（ステップ４０５）、第１のサー
バに「グループ表転送」の要求メッセージを送信する（ステップ４０６）。ステ
ップ４０６では同時に、第１のサーバとサーバ１０との通信速度の計測を開始す
る。なお第１のサーバが「グループ表転送」の要求メッセージを受け取ると、第
１のサーバのグループ表１１０をメッセージに詰め、返答としてサーバ１０に送
る。続くステップ４０７で、第１のサーバが返答として返したグループ表を受信
し、同時に通信速度の計測を終了する。
【００５９】
ステップ４０８では、サーバ状態表１０９に計測した通信速度を反映させると
ともに、受け取った第１のサーバのグループ表を自サーバのサーバ状態表１０９
に反映させる。具体的には、サーバ状態表エントリ２２０でサーバＩＤ２２１が
第１のサーバのＩＤに等しいエントリを探し、当該エントリのスループット２２
２とレイテンシ２２３を計測した通信速度を用いて更新する。更新の方法には、
平均をとる、置き換えるなどいくつか考えられるが、本実施例では置き換える方
法をとる。次に、受け取った第１のサーバのグループ表に含まれるリーダ・サー
バＩＤ、サーバＩＤ、上位リーダ・サーバＩＤ、上位サーバＩＤのうち、サーバ
状態表１０９に対応するサーバ状態表エントリ２２０がないサーバのＩＤの各々
について、新たなサーバ状態表エントリ２２０を追加し、サーバＩＤ２２１に当
該サーバのＩＤを、スループット２２２に「０」を、レイテンシ２２３に「無限
大」を格納する。これにより、第１のサーバに近接のサーバ群がいくつか、サー
バ状態表１０９に追加される。
【００６０】
ステップ４０９では、上記ステップ４０５から４０８をＮ回（Ｎは定数）繰り
返したかどうかを判定する。判定がＮなら（４１０）、ステップ４０５に戻る。
判定がＹなら（４１１）、ステップ４１２に移る。ステップ４１２では、サーバ
状態表に格納されたサーバ群のうち、最も近接のサーバ（例えばスループット２
２２をレイテンシ２２３で割った値が最大のサーバ）に対してグループ参加メッ
セージ３００を送る。この際新規サーバＩＤ３０１には自分のサーバＩＤを格納
する。ステップ４１３で、当該グループ参加メッセージ３００に対する返答であ
るグループ更新メッセージ３２０を受信すると、ステップ４１４でグループ更新
メッセージ３２０の新リーダ・サーバＩＤ３２１に対応するリーダに向けて、「
グループ表転送」の要求メッセージを送信する（ステップ４１５）。リーダは「
グループ表転送」の要求メッセージを受け取ると、リーダのグループ表１１０を
メッセージに詰め、返答としてサーバ１０に送る。続くステップ４０７で、第１
のサーバが返答として返したグループ表を受信し、さらにステップ４１６で、受
け取ったグループ表を自サーバのグループ表１１０に反映させる。
【００６１】
以上が階層形成処理の手順である。なお、グループ更新メッセージ３２０がこ
の手順以外に受信される場合もありうる。この場合、当該グループ更新メッセー
ジ３２０の新リーダ・サーバＩＤ３２１を用いて、ステップ４１４、４１５、４
１６の処理を行う。
【００６２】
（２）グループ参加要求処理
次にグループ参加メッセージ３００を受信した場合の処理を、５を用いて説明
する。
【００６３】
サーバ１０がグループ参加メッセージ３００を受け取ると、ステップ５０１で
自分がリーダがどうかを判定する。具体的には、グループ表１１０のリーダ・サ
ーバＩＤ２３１が「空」であるか、自分のサーバＩＤが格納されているならば、
リーダである。ステップ５０１の判定がＮなら（５０２）、ステップ５０３でリ
ーダ（グループ表１１０のリーダ・サーバＩＤ２３１に格納されているサーバＩ
Ｄ）に現在処理中のグループ参加メッセージ３００を転送し、グループ参加要求
処理を終了する（５０４）。
【００６４】
一方ステップ５０１の判定がＹなら（５０５）、グループのメンバ数がどのよ
うに変化するかによってどのようにグループを構成するかを決定する。まず現在
グループに参加しているメンバの数（グループ表１１０のサーバＩＤ  ２３２、
２３２’、…の数）を調べ「旧メンバ数」とする。そして、グループ参加メッセ
ージ３００に含まれるサーバの数（新規サーバＩＤ  ３０１、３０１’、…の数
）を「新メンバ数」とする。ステップ５０６では、旧メンバ数と新メンバ数の和
が前記ＭＡＸ未満かどうかを調べる。この判定がＹなら（５０７）、ステップ５
０８で、グループ参加メッセージ３００に含まれる新規サーバＩＤ  ３０１、３
０１’、…をグループ表１１０のサーバＩＤ  ２３２、２３２’、…に追加する
。ステップ５０９でグループ更新メッセージ３２０の新リーダ・サーバＩＤ３２
１にサーバ１０のサーバＩＤを格納し、当該メッセージをグループ参加メッセー
ジ３００の新規サーバＩＤ  ３０１、３０１’、…に対応するサーバ群に返答す
る。そして、グループ参加要求処理を終了する（５１０）。
【００６５】
一方、ステップ５０６の判定がＮなら（５１１）、ステップ５１２で旧メンバ
数を１増加してもＭＡＸ未満かどうかを調べる。この判定がＹなら（５１３）、
５１４で、グループ参加メッセージ３００の新規サーバ  ＩＤ３０１をグループ
表１１０のサーバ  ＩＤ２３２、２３２’、…に追加する。そしてステップ５１
５で新規サーバＩＤ３０１には新リーダ・サーバＩＤ３２１にサーバ１０のサー
バＩＤを格納したグループ更新メッセージ３２０を送信し、新規サーバＩＤ  ３
０１’、３０１”、…には新リーダ・サーバＩＤ３２１に新規サーバＩＤ３０１
を格納したグループ更新メッセージ３２０を送信する。そして、グループ参加要
求処理を終了する（５１６）。
【００６６】
一方、ステップ５１２の判定がＮなら（５１７）、ステップ５１８で新グルー
プを作成する。この新グループのメンバは、サーバ１０と新規サーバＩＤ３０１
のサーバ、およびサーバＩＤ２３２のサーバである。現在のグループのリーダは
サーバＩＤ２３２に譲る。具体的には、現在のグループを、サーバＩＤ２３２を
リーダとしたグループとするために、サーバＩＤ  ２３２、２３２’、…に対し
、新リーダ・サーバＩＤ３２１にサーバＩＤ２３２を格納したグループ更新メッ
セージ３２０を送信する。サーバＩＤ２３２のサーバはこれによってリーダにな
り、かつ既にのべた動作によって、上位リーダをサーバ１０に設定する。次に新
グループを形成するため、グループ表１１０のサーバＩＤ  ２３２、２３２’、
…に、新規サーバＩＤ３０１とサーバＩＤ２３２を格納する。続くステップ５１
９で、新規サーバＩＤ３０１には新リーダ・サーバＩＤ３２１にサーバ１０のサ
ーバＩＤを格納したグループ更新メッセージ３２０を送信し、新規サーバＩＤ  
３０１’、３０１”、…には新リーダ・サーバＩＤ３２１に新規サーバＩＤ３０
１を格納したグループ更新メッセージ３２０を送信する。
【００６７】
以上がグループ参加要求処理である。以上の動作によって、各グループの最大
数をＭＡＸ以下に保ちながら、サーバの動的な増加に対応して階層化して行くこ
とが可能となる。
【００６８】
（３）階層維持メッセージ受信処理
サーバ１０がリーダの場合、タイマー等を用いて定期的に階層維持メッセージ
３１０を発行する。階層維持メッセージは、サーバ１０が属するグループのメン
バの他、上下Ｋ段（Ｋは階層維持メッセージ受信処理開始時の引数）のグループ
階層を伝って回覧され、再びサーバ１０に戻る。この動作を実現する処理の手順
を図６を用いて説明する。階層維持メッセージ３１０に対し各メンバは、自分が
動作中であるというデータを付加して次のメンバに送る。もし次のメンバとの通
信ができなければ、その次のメンバを試みる。この動作の結末は、（１）動作中
のメンバ全員を回って階層維持メッセージ３１０がリーダに返る、（２）階層維
持メッセージ３１０を保持中のメンバが障害を起して階層維持メッセージ３１０
、（３）リーダが障害を起し、最終送信先がなくなる、のいずれかとなる。以下
のプロトコルでは代行リーダとタイムアウトの使用により、（１）、（２）、（
３）のいずれにも対処できる。
【００６９】
サーバ１０が階層維持メッセージ３１０を受け取ると、まずステップ６０１で
送信元サーバＩＤ３１１が自分のＩＤと等しいかどうかを判定する。判定がＹな
ら（６０２）、階層維持メッセージ受信処理は終了である。
【００７０】
一方ステップ６０１の判定がＮなら（６０３）、ステップ６０４で階層維持メ
ッセージ３１０に自分のサーバＩＤを新規サーバＩＤ３１２、３１２’、…に追
加する。
【００７１】
なおこの時、すでに新規サーバＩＤ３１２、３１２’、…に自分のサーバＩＤ
が含まれている場合、同じ階層維持メッセージ３１０が２度回ってきたことを意
味する。この場合、リーダが受け取るべきメッセージを受け取れなかったために
、自分が代行リーダになったことを意味する。この場合で、階層維持メッセージ
３１０がグループ表１１０の上位サーバＩＤ  ２３４、２３４’、…のいずれか
から送られた場合には上位グループのリーダになるため、上位サーバＩＤ  ２３
４、２３４’、…のサーバ群に対して、新リーダ・サーバＩＤ３２１に自分のサ
ーバＩＤを格納したグループ更新メッセージ３２０を送信する。また、階層維持
メッセージ３１０がグループ表１１０のサーバＩＤ２３２、２３２’、…のいず
れかから贈られた場合にはグループのリーダになるため、サーバＩＤ  ２３２、
２３２’、…のサーバ群に対して、新リーダ・サーバＩＤ３２１に自分のサーバ
ＩＤを格納したグループ更新メッセージ３２０を送信する。
【００７２】
続いて、自分がリーダで、かつネスト数３１３が１に等しいかを判定する（ス
テップ６０５）。判定がＹなら（６０６）、ステップ６０６で階層維持メッセー
ジ３１０にグループ表１１０のサーバＩＤ  ２３２、２３２’、…を新規サーバ
ＩＤ３１２、３１２’、…に追加し、ステップ６１０に進む（６０８）。また、
ステップ６０５の判定がＮなら、ここでは何もしない（６０９）。
【００７３】
続いて、自分がリーダで、かつネスト数３１３が２以上かを判定する（ステッ
プ６１０）。判定がＹなら（６１１）、ステップ６１２で送信元サーバＩＤ３１
１をサーバ１０のＩＤに変更してネスト数３１３を１減じ、ステップ６１３でメ
ンバの１つに階層維持メッセージ３１０を送信する。具体的には、グループ表１
１０のサーバＩＤ  ２３２、２３２’、…を上から走査していき、階層維持メッ
セージ３１０の送信がうまくいくまで試みる。ステップ６１４でメンバから階層
維持メッセージ３１０が戻ってきたら、階層維持メッセージ３１０の送信元サー
バＩＤ３１１を元に戻し、次の処理に進む（６１５）。
【００７４】
なお、ステップ６１３とステップ６１４の間で回覧される送信元サーバＩＤ３
１１が、メンバの障害やネットワーク１２の障害によって、失われる可能性もあ
る。この際、サーバ１０はタイムアウトによりステップ６１４の受信をあきらめ
、次の処理に進む（６１５）。
【００７５】
次に、ステップ６１７で、階層維持メッセージ３１０が上位メンバから受け取
ったものかを判定する。判定がＹなら（６１８）、当該階層維持メッセージ３１
０は上位メンバを回覧されているので、送信先も上位メンバから選択するのが良
い。具体的にはステップ６１９で、グループ表１１０の上位サーバＩＤ  ２３４
、２３４’、…のうちサーバ１０のＩＤが格納されているエントリを探す。もし
この条件に合うエントリがあり、そのエントリの次のエントリのサーバがあれば
、当該サーバに階層維持メッセージ３１０の送信を試みる。もし当該サーバへの
送信が失敗した場合（すなわち当該サーバの障害かネットワーク１２の障害の場
合）、さらに次のエントリ、その次のエントリ、…を試みる。もし最後のエント
リも試したら、上位リーダ・サーバＩＤ  ２３３を試みる。これを上位リーダ・
サーバＩＤ  ２３３および上位サーバＩＤ２３４をすべて試みるまで続け、もし
どこにも送信できなければ送信をあきらめる。次にステップ６２２に進む（６２
０）。また、ステップ６１７の判定がＮなら（６２１）、ステップ６２２に進む
。
【００７６】
ステップ６２２では、階層維持メッセージ３１０がメンバから受け取ったもの
かを判定する。判定がＹなら（６２３）、当該階層維持メッセージ３１０はメン
バを回覧されているので、送信先もメンバから選択するのが良い。具体的にはス
テップ６２４で、グループ表１１０のサーバＩＤ  ２３２、２３２’、…のうち
サーバ１０のＩＤが格納されているエントリを探す。もしこの条件に合うエント
リがあり、そのエントリの次のエントリのサーバがあれば、当該サーバに階層維
持メッセージ３１０の送信を試みる。もし当該サーバへの送信が失敗した場合（
すなわち当該サーバの障害かネットワーク１２の障害の場合）、さらに次のエン
トリ、その次のエントリ、…を試みる。もし最後のエントリも試したら、リーダ
・サーバＩＤ２３１を試みる。これをリーダ・サーバＩＤ２３１およびサーバＩ
Ｄ２３２をすべて試みるまで続け、もしどこにも送信できなければ送信をあきら
め（６２６）、階層維持メッセージ受信処理を終了する。また、ステップ６２２
の判定がＮなら（６２６）、そのまま階層維持メッセージ受信処理を終了する。
【００７７】
以上が階層維持メッセージの処理の手順である。階層維持メッセージの受信処
理が終了してから、サーバ１０は階層維持メッセージ３１０の新規サーバＩＤ３
１２をサーバ状態表１０９に反映する。すなわち、サーバ状態表１０９に対応す
るサーバ状態表エントリ２２０がないサーバのＩＤの各々について、新たなサー
バ状態表エントリ２２０を追加し、サーバＩＤ２２１に当該サーバのＩＤを、ス
ループット２２２に「０」を、レイテンシ２２３に「無限大」を格納する。これ
により、第１のサーバに近接のサーバ群がいくつか、サーバ状態表１０９に追加
される。
【００７８】
階層維持メッセージ３１０のうちネスト数３１３が０のメッセージは、特にグ
ループ内のサーバの活動状態を調べ、メンバに伝播するのに用いる。この場合、
リーダが階層維持メッセージ３１０を送信して、動作中のメンバを一周してリー
ダに戻る。この後、同じメッセージにネスト数３１３に「―１」を格納してメン
バに回覧する。ネスト数３１３が―１の階層維持メッセージ３１０を受け取った
ら、サーバは階層維持メッセージ３１０の新規サーバＩＤ３１２、３１２’、…
をサーバＩＤ  ２３２、２３２’、…に格納して、次のメンバに同じメッセージ
を渡す。この手順により、メンバの活動状態がグループ全体に伝播する。
【００７９】
（４）階層再構成処理
あるグループのサーバ数が一定数以下になった場合、グループを再構成する。
この手順を図７を用いて説明する。
【００８０】
サーバ１０がリーダの場合、グループ表１１０が変化する度に階層再構成処理
を起動する。ステップ７０１で、グループ表１１０のサーバＩＤ  ２３２、２３
２’、…の数がＭＩＮ以下（ＭＩＮは定数）かつ、上位リーダ・サーバＩＤ  ２
３３が「空」でなく、かつ上位リーダ・サーバＩＤ  ２３３が自分のサーバＩＤ
以外であるかを判定する。この判定がＮなら（７０２）、階層再構成処理を終了
する。
【００８１】
一方、ステップ７０１の判定がＹなら（７０３）、上位リーダ・サーバＩＤ  
２３３に対応するサーバに、グループ参加メッセージ３００を送る。この際の新
規サーバＩＤ  ３０１、３０１’、…には、自分のサーバＩＤおよびグループ表
１１０のサーバＩＤ  ２３２、２３２’、…を格納する。
【００８２】
これにより、既に説明したグループ参加要求処理が上位グループで起動され、
サーバ１０の属するグループは再構成されて、通常別のグループに吸収される。
【００８３】
以上（１）から（４）の各処理によって実現されるサーバ状態伝播プロトコル
によって、以下の特長が得られる。相互支援によってマルチキャスト階層を動的
に構築することによって、他サーバの動作状況の変化および通信速度の変化を、
集中サーバを必要とせずに把握すること。伝播するサーバ情報を一定数以下の近
接サーバの情報と遠隔サーバの情報に絞り、伝播先をマルチキャスト階層の構造
にしたがって一定数以下にすることによって、サーバが多数になっても、管理の
ための通信が爆発しないこと。マルチキャスト階層再構築によって、システム動
作中の動的なサーバの参加・脱退に対応することと、一部サーバまたはネットワ
ークの障害時に対処すること。管理者が与える設定を、サーバ起動時に最初に通
信する少数のサーバのみに絞り、管理者の設定が簡単にすること。
【００８４】
広域協調キャッシュ管理
本発明の情報システム分散管理方法では、「広域協調キャッシュ管理プロトコ
ル」を備える。このプロトコルは、前記サーバ状態伝播プロトコルが形成するマ
ルチキャスト階層を用いてキャッシュ・ディレクトリの伝播と、キャッシュ制御
（どのサーバがどのＵＲＬをキャッシュ中に保持するか、いつ、どのＵＲＬをあ
るサーバから別のサーバに移動させるか）を集中管理サーバなしで行う。
【００８５】
（１）キャッシュの検索とキャッシュ・ディレクトリの伝播
サーバ１０が、クライアント１１が発した第１のＵＲＬの情報に対する要求を
受け付けると、クライアント要求処理部１００がこの要求を処理する。クライア
ント要求処理部１００は、キャッシュ表１０７を第１のＵＲＬを用いて検索し、
ＵＲＬ２０１が第１のＵＲＬに等しいキャッシュ表エントリ２００があればキャ
ッシュ内容２０５をクライアント１１に返し、参照回数２０４を１増加させる。
このようなエントリがなければ、キャッシュ管理部１０１に制御を移す。
【００８６】
キャッシュ管理部１０１では、キャッシュ・ディレクトリ１０８を第１のＵＲ
Ｌを用いて検索し他のサーバ１０’、１０”、…が第１のＵＲＬの情報を保持し
ていないかを調べる。すなわち、ＵＲＬ２１１が第１のＵＲＬに等しいキャッシ
ュ・ディレクトリ・エントリ２１０があれば、当該キャッシュ・ディレクトリ・
エントリ２１０のサーバＩＤ２１２に対応するサーバにクライアント１１の要求
を転送する。もしこのようなエントリがなければ、第１のＵＲＬを処理可能な外
部サーバ１３、１３’、１３”、…にクライアント１１の要求を送信する。
【００８７】
他のサーバ１０’、１０”、…と外部サーバ１３、１３’、１３”、…に送信
した要求の返答は、ＨＴＴＰのプロトコルで返される。このプロトコルの詳細は
省略するが、情報の内容、サイズ、最終更新日付が付加されるのが普通である。
この返答を受け取ったキャッシュ管理部１０１は、キャッシュ表１０７に新たな
キャッシュ表エントリ２００を作り、該エントリのＵＲＬ２０１に第１のＵＲＬ
を、サイズ２０２にサイズを、日付２０３に最終更新日付を、参照回数２０４に
０を、キャッシュ内容２０５に情報の内容を格納する。
【００８８】
グループのキャッシュ・ディレクトリ１０８を更新するために、新たな情報を
入手したサーバ１０は、グループのメンバに対してホストＵＲＬメッセージ３７
０を送る。ホストＵＲＬメッセージ３７０のサーバＩＤ３７２はサーバ１０のＩ
Ｄを、ＵＲＬ３７３は当該情報のＵＲＬを、フラグ３７４は「存在」を保持する
。
【００８９】
（２）キャッシュ価値回覧処理
本発明では、サーバ１０、１０’、１０”、…がキャッシュされた情報のキャ
ッシュ価値を「キャッシュ価値=（参照回数）×（予測再入手時間）／（情報の
サイズ）」の式で評価する。予測再入手時間は、外部サーバ１３、１３’、１３
”、…と他のサーバ１０’、１０”、…から入手する時間を予測する。他のサー
バ１０’、１０”、…との予測際入手時間の予測には、サーバ状態表１０９のス
ループット２２２とレイテンシ２２３を用いる。外部サーバ１３、１３’、１３
”、…を用いた予測再入手時間は、スループットとレイテンシともに一律な定数
を用いる。
【００９０】
サーバ１０、１０’、１０”、…は、キャッシュに保持している各情報のキャ
ッシュ価値を計算し、情報を順序付けする。この順序に従って、必要に応じて情
報をキャッシュから破棄したり、他のサーバ１０’、１０”、…へ移動する。
【００９１】
サーバ１０が第１の情報を他のサーバ１０’、１０”、…の１つに移動させる
場合には、移動先サーバを決定する必要がある。この目的でサーバ１０、１０’
、１０”、…は、自分が受け入れ可能なキャッシュ価値の最小値（受け入れ可能
キャッシュ価値と呼ぶ）を他サーバに回覧する。受け入れ可能キャッシュ価値に
は、例えば、キャッシュされている情報のうち、最下位から数えてＭ番目（Ｍは
適当な定数）のキャッシュ価値を用いる。この受け入れ可能キャッシュ価値を用
いて、各サーバは移動先サーバを選択する。
【００９２】
受け入れ可能キャッシュ価値回覧処理の手順を、図８を用いて説明する。
【００９３】
リーダのキャッシュ価値評価部１０４は、一定時間毎にキャッシュ価値回覧処
理を起動する。またリーダ以外のキャッシュ価値評価部１０４は、キャッシュ価
値メッセージ３４０を受け取った時点でキャッシュ価値回覧処理を行う。キャッ
シュ価値回覧処理を開始すると、ステップ８０１で自分がリーダであるかどうか
を判定する。
【００９４】
ステップ８０１の判定がＹの場合（８０２）、ステップ８０３で上記の要領で
自分の回覧すべき受け入れ可能キャッシュ価値を計算する。次に、新たなキャッ
シュ価値メッセージ３４０を作成し、新たなキャッシュ価値メッセージ・エント
リ３４１を作り、当該エントリのサーバＩＤ３４２に自分のサーバＩＤを、キャ
ッシュ価値３４３に計算した受け入れ可能キャッシュ価値を格納する。そして、
ステップ８０４で作成したキャッシュ価値メッセージ３４０を送信する。送信先
は、階層維持メッセージの回覧と同様、グループ表１１０を用いて決定する。
【００９５】
続くステップ８０５では動作中のメンバを一周してきたキャッシュ価値メッセ
ージ３４０を受信する。そして受け取ったメッセージをもう一周回覧するために
、ステップ８０６で再びメンバに受け取ったキャッシュ価値メッセージ３４０を
送信する。さらにステップ８０７でキャッシュ価値メッセージ３４０を受信する
。これによって、キャッシュ価値回覧処理の間動作中のメンバは２回キャッシュ
価値メッセージ３４０を受け取ることになる。
【００９６】
一方ステップ８０１の判定がＮの場合（８０８）、まずステップ８０９でキャ
ッシュ価値メッセージ３４０を受信し、ステップ８１０でキャッシュ価値メッセ
ージ３４０の自分のキャッシュ価値メッセージ・エントリ３４１があるかを判定
する。具体的には、受信したキャッシュ価値メッセージ３４０のキャッシュ価値
メッセージ・エントリ３４１のうち、サーバＩＤ３４２が自分のサーバＩＤに等
しいエントリがあるかを調べる。この判定がＮの場合（８１１）、ステップ８１
２で回覧すべき受け入れ可能キャッシュ価値を計算し、ステップ８１３でキャッ
シュ価値メッセージ３４０に自分のキャッシュ価値メッセージ・エントリ３４１
を追加する。すなわち、新たなキャッシュ価値メッセージ・エントリ３４１を作
り、当該エントリのサーバＩＤ３４２に自分のサーバＩＤを、キャッシュ価値３
４３に計算した受け入れ可能キャッシュ価値を格納する。そして、ステップ８１
４で次のメンバにキャッシュ価値メッセージ３４０を送る。送信先は、階層維持
メッセージの回覧と同様、グループ表１１０を用いて決定する。
【００９７】
また、ステップ８１０の判定がＹの場合（８１５）、すなわち二周目の回覧の
場合、ステップ８１６で、受信したキャッシュ価値メッセージ３４０をキャッシ
ュ価値評価部１０４の中に保存する。続いてステップ８１４の処理を行い、キャ
ッシュ価値回覧処理を終了する。
【００９８】
（３）移動予告回覧によるキャッシュ移動集中の回避
１つのグループの複数のサーバが一斉に情報の移動を予定している場合、移動
先が１つのサーバに集中する恐れがある。この問題を解決するために、各サーバ
は移動しようとする情報および予定移動先のリスト（移動予定リストと呼ぶ）を
移動予告メッセージ３５０にのせて回覧する。これにより各サーバは、他のサー
バが選んでいない移動先を避けて移動先サーバを決定することができる。
【００９９】
移動予告回覧処理の手順を、図９を用いて説明する。
【０１００】
リーダのキャッシュ移動破棄部１０５は、一定時間毎に移動予告回覧処理を起
動する。またリーダ以外のキャッシュ移動破棄部１０５は、移動予告メッセージ
３５０を受け取った時点で移動予告回覧処理を行う。移動予告回覧処理を開始す
ると、ステップ９０１で自分がリーダであるかどうかを判定する。
【０１０１】
ステップ９０１の判定がＹの場合（９０２）、ステップ９０３で上記の要領で
移動予告リストを作成する。移動予告リストはステップ９０４で移動予告メッセ
ージ３５０に格納される。すなわち、新たな移動予告メッセージ３５０を作成し
、移動すべき情報毎に新たな移動予告メッセージ・エントリ３５１を作り、当該
エントリのサーバＩＤ３５２に自分のサーバＩＤを、ＵＲＬ３５３に移動すべき
情報のＵＲＬを、そして移動先サーバＩＤ３５４に移動先サーバを格納する。そ
して、ステップ９０５で作成した移動予告メッセージ３５０を送信する。送信先
は、階層維持メッセージの回覧と同様、グループ表１１０を用いて決定する。続
くステップ９０６で、移動処理を行う。すなわち、移動すべき情報のそれぞれに
対し、情報を移動すべきサーバに情報をネットワーク１２経由で転送する。
【０１０２】
一方ステップ９０１の判定がＮの場合（９０７）、まずステップ９０８で移動
予告メッセージ３５０を受信し、ステップ９０９で移動予告メッセージ３５０を
もとに自分の移動予告リストを更新する。すなわち、もし自分が移動を予定して
いる移動先サーバが、移動予告メッセージ３５０の上記Ｍ個以上の移動予告メッ
セージ・エントリ３５１の移動先サーバＩＤ３５４に格納されていれば、別の移
動先サーバを選択する。次にステップ９１０で、更新した自分の移動予告リスト
を移動予告メッセージ３５０に反映する。すなわち、移動すべき情報毎に新たな
移動予告メッセージ・エントリ３５１を作り、当該エントリのサーバＩＤ３５２
に自分のサーバＩＤを、ＵＲＬ３５３に移動すべき情報のＵＲＬを、そして移動
先サーバＩＤ３５４に移動先サーバを格納する。続くステップ９１１で、作成し
た移動予告メッセージ３５０を送信する。送信先は、階層維持メッセージの回覧
と同様、グループ表１１０を用いて決定する。続くステップ９０６で、移動処理
を行う。すなわち、移動すべき情報のそれぞれに対し、情報を移動すべきサーバ
に情報をネットワーク１２経由で転送する。
【０１０３】
（４）破棄予告回覧によるキャッシュ一斉破棄の回避
近接する複数のサーバが同一情報のキャッシュを保持している場合、このキャ
ッシュのコピーすべてが一斉に破棄されないように工夫することが必要である。
理想的には、近接する複数のサーバに対して情報のコピーがただ１つ存在するの
が望ましい。本発明のシステムでは、集中の管理サーバを用いずに近似的な方法
でこの状態に近づける。このために、破棄しようとする情報のリスト（破棄予定
リストと呼ぶ）をメンバの間で回覧する。自分が破棄しようとする情報のキャッ
シュがグループのメンバが保持する最後のコピーである場合には、予定した破棄
を中止する。
【０１０４】
破棄予告回覧処理の手順を、図１０を用いて説明する。
【０１０５】
リーダのキャッシュ移動破棄部１０５は、一定時間毎に破棄予告回覧処理を起動
する。またリーダ以外のキャッシュ移動破棄部１０５は、破棄予告メッセージ３
６０を受け取った時点で破棄予告回覧処理を行う。破棄予告回覧処理を開始する
と、ステップ１００１で自分がリーダであるかどうかを判定する。
【０１０６】
ステップ１００１の判定がＹの場合（１００２）、ステップ１００３で上記の
要領で破棄予告リストを作成する。破棄予告リストはステップ１００４で破棄予
告メッセージ３６０に格納され、送信される。すなわち、新たな破棄予告メッセ
ージ３６０を作成し、破棄すべき情報毎に新たな破棄予告メッセージ・エントリ
３６１を作り、当該エントリのサーバＩＤ３６２に自分のサーバＩＤを、ＵＲＬ
３６３に破棄すべき情報のＵＲＬを格納する。送信先は、階層維持メッセージの
回覧と同様、グループ表１１０を用いて決定する。続くステップ１００５で、破
棄予告メッセージ３６０の受信を行い、しかる後にステップ１００６で破棄処理
を行う。すなわち、破棄すべき情報のそれぞれをキャッシュ表１０７から削除す
る。この際、グループのキャッシュ・ディレクトリ１０８を更新するために、サ
ーバ１０はグループのメンバに対してホストＵＲＬメッセージ３７０を送る。ホ
ストＵＲＬメッセージ３７０のサーバＩＤ３７２はサーバ１０のＩＤを、ＵＲＬ
３７３は当該ＵＲＬ３３３を、フラグ３７４は「存在しない」を保持する。
【０１０７】
一方ステップ１００１の判定がＮの場合（１００７）、まずステップ１００８
で破棄予告メッセージ３６０を受信し、ステップ１００９で破棄予告メッセージ
３６０とキャッシュ・ディレクトリ１０８をもとに自分の破棄予告リストを更新
する。すなわち、もし自分が破棄を予定している情報のそれぞれについて、「（
キャッシュ・ディレクトリ１０８に登場する回数）―（破棄予告メッセージ３６
０に登場する回数）」が１以下であれば、破棄をしないことにし、破棄予定リス
トから取り除く。次にステップ１０１０で、更新した自分の破棄予告リストを破
棄予告メッセージ３６０に反映する。すなわち、破棄すべき情報毎に新たな破棄
予告メッセージ・エントリ３６１を作り、当該エントリのサーバＩＤ３６２に自
分のサーバＩＤを、ＵＲＬ３６３に破棄すべき情報のＵＲＬを格納する。続くス
テップ１０１１で、作成した破棄予告メッセージ３６０を送信する。送信先は、
階層維持メッセージの回覧と同様、グループ表１１０を用いて決定する。続くス
テップ１００６で、すでに説明した破棄処理を行う。
【０１０８】
先行ヴァリデーション
ＷＷＷではキャッシュのヴァリデーションに消費する時間がユーザの反応時間
のかなりの部分を占める。そこで、定期的にキャッシュされた情報のヴァリデー
ションを行っておくことで、キャッシュの新鮮さを常に一定以上に保つ先行ヴァ
リデーションを導入する。先行ヴァリデーションは、ユーザの要求が特にないと
きにでも、ヴァリデーションをサーバ１０、１０’、１０”、…が行うことであ
る。これにより、ユーザがＷＷＷページを参照した時点でのヴァリデーションを
できる限り回避する。
【０１０９】
ヴァリデーション間隔をどの程度まで広く取ることが可能かを見積るために、
１度参照されたＷＷＷページが、別のユーザから参照されるまでの時間を、我々
の組織のＷＷＷ利用記録から得た。１時間以内に再参照されるＷＷＷページは参
照されるＷＷＷページ全体の２.３%に過ぎず、１２時間以内でも９.９%である。
また全体を平均すると再参照間隔は１７７.７時間であることが明らかとなった
。正確な時間はユーザの母集団に左右されることが予想されるが、基本的にヴァ
リデーションの時間間隔は８時間から１２時間程度でもユーザが得るキャッシュ
の新鮮さにほとんど影響を与えないことが言える。また、ヴァリデーション動作
を変更する場合、広く用いられているＨＴＴＰ／１.０およびＩｎｔｅｒｎｅｔ
Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ（ＩＥＴＦ）に標準化提案さ
れているＨＴＴＰ／１.１に準拠することが望ましい。ＨＴＴＰ／１.１ではキャ
ッシュの古さが２４時間以内なら、ユーザに警告を行う必要なしと決められてい
る。このため、８時間以上２４時間以下が、望ましい先行ヴァリデーション間隔
となる。また、サーバが置かれている組織の都合により、管理者が明示的に指定
した時間帯を先行ヴァリデーションに用いてもよい。こうすることで、企業の従
業員がサーバ１０を利用しない時間帯を選んで先行プリフェッチを行うことが可
能となる。
【０１１０】
さらに、先行ヴァリデーションに際しては、先行ヴァリデーションを行うサー
バおよび当該サーバ付近のネットワークに相当の負荷が発生するため、クライア
ントからのサーバへの負荷が低い時間帯（オペレーティング・システムへの問合
わせにより、サーバの負荷を得ることが可能である）、またはネットワークの負
荷が低い時間帯（グループ内のサーバとの通信速度の変化を記録することにより
、ネットワークの負荷の概算を得ることができる）とを別の条件として用いると
よい。
【０１１１】
また、先行ヴァリデーションは、各サーバが外部サーバ１３、１３’、１３”
、…に対して行うことができるが、複数のサーバが行うべき先行ヴァリデーショ
ンの対象となるＵＲＬを、１つのサーバに集めて、一括してヴァリデーションを
行った方が、１つのＵＲＬを何回もヴァリデーションする無駄が少なくなる。そ
こで、あるサーバから別のサーバに先行ヴァリデーションを依頼するヴァリデー
ション依頼メッセージ３３０を用いる。
【０１１２】
先行ヴァリデーションの処理を図１１を用いて説明する。
【０１１３】
リーダのヴァリデーション管理部１０３は、上記の時間間隔に基づく考察によ
り、一定時間毎にヴァリデーション処理を起動する。またリーダ以外のヴァリデ
ーション管理部１０３は、同じく一定時間毎にヴァリデーション処理を起動する
。ヴァリデーション処理を開始すると、ステップ１１０１で自分がリーダである
かどうかを判定する。
【０１１４】
ステップ１１０１の判定がＹの場合（１１０２）、ステップ１１０３でメンバ
から送られてくるヴァリデーション依頼を受信する。一定時間ヴァリデーション
依頼を受け付けたあと、ステップ１１０４に移り、ヴァリデーション処理を行う
。この処理の内容は、ヴァリデーション依頼メッセージ３３０中の各ヴァリデー
ション依頼メッセージ・エントリ３３１のＵＲＬ３３３について、ＨＴＴＰの「
ＨＥＡＤ」要求を用いて、最終更新日付を外部サーバ１３、１３’、１３”、…
から入手することである。ヴァリデーション処理が終わると、続くステップ１１
０５で、ヴァリデーション依頼を受信した各サーバに、ヴァリデーションの結果
を返す。ヴァリデーションの結果はヴァリデーション依頼と同じヴァリデーショ
ン依頼メッセージ３３０であるが、各ヴァリデーション依頼メッセージ・エント
リ３３１の日付３３４はそれぞれ、ステップ１１０４で得た最新の最終更新日付
で置き換えてから送信する。
【０１１５】
一方ステップ１１０１の判定がＮの場合（１１０７）、まずステップ１１０８
でヴァリデーション依頼メッセージ３３０を作成する。ヴァリデーション依頼メ
ッセージ３３０には、ヴァリデーションの対象となる情報（すなわちキャッシュ
表１０７に含まれる情報のうち、参照回数２０４がＴ回以上の情報（Ｔは定数）
）に関してそれぞれヴァリデーション依頼メッセ−ジ３３０には、ヴァリデーシ
ョンの対象となる情報（すなわちキャッシュ表１０７に含まれる情報のうち、参
照回数２０４がＴ回以上の情報（Ｔは定数））に関してそれぞれヴァリデーショ
ン依頼メッセージ・エントリ３３１を作成し、サーバＩＤ３３２に自分のサーバ
ＩＤを、ＵＲＬ３３３に当該情報のＵＲＬを格納する。日付３３４には「空」を
格納する。続くステップ１１０８で作成したヴァリデーション依頼メッセージ３
３０をリーダに対して送信する。続くステップ１１０９では、リーダがヴァリデ
ーション結果を返答として返すのを待って受け取る。ステップ１１０９ではヴァ
リデーション結果をもとにキャッシュ表１０７を更新する。すなわち、ヴァリデ
ーション結果であるヴァリデーション依頼メッセージ３３０に格納されたヴァリ
デーション依頼メッセージ・エントリ３３１のそれぞれについて、ＵＲＬ３３３
がキャッシュ表１０７のＵＲＬ２０１に等しいキャッシュ表エントリ２００を検
索し、もしそのようなキャッシュ表エントリ２００があれば、参照回数２０４に
０を格納する。そして、当該キャッシュ表エントリ２００の日付２０３を当該ヴ
ァリデーション依頼メッセージ・エントリ３３１の日付３３４と比較する。もし
日付３３４がより新しければ、キャッシュ表１０７中の情報は古いので、当該キ
ャッシュ表エントリ２００を削除する。この際、グループのキャッシュ・ディレ
クトリ１０８を更新するために、サーバ１０はグループのメンバに対してホスト
ＵＲＬメッセージ３７０を送る。ホストＵＲＬメッセージ３７０のサーバＩＤ３
７２はサーバ１０のＩＤを、ＵＲＬ３７３は当該ＵＲＬ３３３を、フラグ３７４
は「存在しない」を保持する。
【０１１６】
なお、上記定数Ｔの設定に際しては、ＷＷＷのローカリティが低いことを考慮
することが重要である。例えば、我々の組織では、ユーザが要求したＷＷＷの情
報のうち７０%近くが、一回しか参照されないことがわかった。このため、例え
ばＴを１にすると、キャッシュされた情報のうちヴァリデーションをすべき情報
を、効果的に絞りこむことができ、大量の情報をすべてヴァリデーションしなく
てもよい。
【０１１７】
以上の手順で、先行ヴァリデーションが行われ、キャッシュ表１０７の中の情
報は常にある程度以上の新鮮さが保証される。
【図面の簡単な説明】
【０１１８】
【図１】本発明の内部構成を示すブロック図。
【図２】データ構造を示す図。
【図３】メッセージの形式を説明する図。
【図４】サーバ初期化時の階層形成処理のフローチャート。
【図５】グループ参加要求処理のフローチャート。
【図６】階層維持メッセージ受信処理のフローチャート。
【図７】階層再構成処理のフローチャート。
【図８】キャッシュ価値回覧処理のフローチャート。
【図９】移動予告回覧処理のフローチャート。
【図１０】破棄予告回覧処理のフローチャート。
【図１１】ヴァリデーション処理のフローチャート。
【符号の説明】
【０１１９】
１０、１０’、１０”、…：サーバ、１１：クライアント、１２：ネットワー
ク、１３、１３’、１３”、…：外部サーバ、１００：クライアント要求処理部
、１０１：キャッシュ管理部、１０２：サーバ管理部、１０３：ヴァリデーショ
ン管理部、１０４：キャッシュ価値評価部、１０５：キャッシュ移動破棄部、１
０６：通信部、１０７：キャッシュ表、１０８：キャッシュ・ディレクトリ、１
０９：サーバ状態表、１１０：グループ表。
【図１】
2008165833.tif 000003
【図２】
2008165833.tif 000004
【図３】
2008165833.tif 000005
【図４】
2008165833.tif 000006
【図５】
2008165833.tif 000007
【図６】
2008165833.tif 000008
【図７】
2008165833.tif 000009
【図８】
2008165833.tif 000010
【図９】
2008165833.tif 000011
【図１０】
2008165833.tif 000012
【図１１】
2008165833.tif 000013
【手続補正書】
【提出日】平成20年3月19日(2008.3.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワークで互いに接続された、情報を利用するクライアントと、１つ以上の情報のコピーを保持し、クライアントからの依頼により指定された情報を提供するサーバと、１つ以上の情報を保持し、サーバまたはクライアントに情報を提供する２つ以上の外部サーバとからなるシステムで、前記サーバまたは前記クライアントが情報のコピーが最新かどうかを問合わせるヴァリデーションに対して外部サーバが答えるサーバ分散管理方法であって、
サーバが保持する情報のうち、前回のヴァリデーションから１回以上参照された情報を、所定の時間毎に、前記サーバが前記外部サーバにヴァリデーションを行うことを特徴とするサーバ分散管理方法。
【請求項２】
前記所定の時間として、８時間以上２４時間以下の時間を用いる請求項１に記載のサーバ分散管理方法。
【請求項３】
ネットワークで互いに接続された、情報を利用するクライアントと、１つ以上の情報のコピーを保持し、クライアントからの依頼により指定された情報を提供するサーバと、１つ以上の情報を保持し、サーバまたはクライアントに情報を提供する２つ以上の外部サーバとからなるシステムで、サーバまたはクライアントが情報のコピーが最新かどうかを問合わせるヴァリデーションに対して外部サーバが答えるサーバ分散管理方法であって、
サーバが保持する情報のうち、前回のヴァリデーションから１回以上参照された情報を、前記情報を外部サーバから入手してから８時間以上２４時間以下で、かつサーバの負荷またはサーバ近辺のネットワークの負荷が所定の値以下の時に前記サーバが前記外部サーバにヴァリデーションを行うサーバ分散管理方法。
【請求項４】
ネットワークで互いに接続された、情報を利用するクライアントと、１つ以上の情報のコピーを保持し、クライアントからの依頼により指定された情報を提供するサーバと、１つ以上の情報を保持し、サーバまたはクライアントに情報を提供する２つ以上の外部サーバとからなるシステムで、サーバまたはクライアントが情報のコピーが最新かどうかを問合わせるヴァリデーションに対して外部サーバが答えるサーバ分散管理方法であって、
サーバが保持する情報のうち、前回のヴァリデーションから１回以上参照された情報を、前記情報を外部サーバから入手してから８時間以上２４時間以下で、かつ管理者が指定した時間帯の中で、前記サーバが前記外部サーバにヴァリデーションを行うサーバ分散管理方法。
【請求項５】
ネットワークで互いに接続された、情報を利用するクライアントと、１つ以上の情報のコピーを保持し、クライアントからの依頼により指定された情報を提供するサーバと、１つ以上の情報を保持し、サーバまたはクライアントに情報を提供する２つ以上の外部サーバとからなるシステムで、前記サーバまたは前記クライアントが情報のコピーが最新かどうかを前記外部サーバへ問合わせるヴァリデーションを行うためのプログラムであって、
サーバが保持する情報のうち、前回のヴァリデーションから１回以上参照された情報を、所定の時間以内に、サーバが外部サーバにヴァリデーションを行う機能を有するプログラム。