(57)【要約】【課題】待機ピアによって離脱ピアが担当していた小空間が担当させることで、システムを速やかに安定した状態に回復する。【解決手段】システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録しておく。システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱すると、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索する。そして、検索した待機ピアに対して離脱ピアの存在を通知し、通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当させる。【選択図】　図１
2004072603.tif 000002
【特許請求の範囲】
【請求項１】
システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録する登録手段と、
システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにおいて予め決められた探索鍵を用いて待機ピアを検索する検索手段と、
検索した待機ピアに対して離脱ピアの存在を通知する通知手段と
を具備し、
通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当させるということを特徴とする障害回復システム。
【請求項２】
システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録し、
システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索し、
検索した待機ピアに対して離脱ピアの存在を通知し、
通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当させることを特徴とする障害回復方法。
【請求項３】
システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録するステップと、
システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索するステップと、
検索した待機ピアに対して離脱ピアの存在を通知するステップと、
通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当するステップと
をコンピュータに実行させることを特徴とする障害回復プログラム。
【請求項４】
システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録するステップと、
システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索するステップと、
検索した待機ピアに対して離脱ピアの存在を通知するステップと、
通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当するステップと
をコンピュータに実行させる障害回復プログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、障害回復システム、障害回復方法、障害回復プログラムおよび記録媒体に関する。
【０００２】
【従来の技術】
ハッシュ表は、（探索鍵Ｋ、値Ｖ）のペアを、探索鍵にハッシュ関数Ｈ（）を適用して得られるハッシュアドレスＨ（Ｋ）に登録した表である。ハッシュ表からある探索鍵Ｋに対応する値Ｖを検索する場合、探索鍵Ｋにハッシュ関数Ｈ（）を適用して得られるハッシュアドレスＨ（Ｋ）を参照することで該当項目が得られる。ハッシュ表に対する（探索鍵Ｋ、値Ｖ）のペアの登録と削除も検索時と同様に探索鍵Ｋにハッシュ関数Ｈ（）を適用して得られるハッシュアドレスＨ（Ｋ）に対して行われる。ハッシュ表は検索・登録・削除の手間がハッシュ関数Ｈ（）の計算だけですむため、表中の登録項目数によらず極めて効率のよいデータ構造となっている。
【０００３】
ピアツーピア型分散ハッシュ表管理システムＣＡＮは、ＳＩＧＣＯＭＭ２００１で提案されている。ＣＡＮは、ピアツーピア環境においてハッシュ表を分散型で実現するものである。ＣＡＮでは、まず、任意の正数ｄを選び、ｄ次元トーラス状論理空間［０，１］×［０，１］×…×［０，１］を想定する。そして、値域が［０，１］のハッシュ関数をｄ個用意する。それらをＨ１（）、Ｈ２（）、…、Ｈｄ（）とする。さらに、値域が整数値のハッシュ関数Ｈ０（）を用意する。
【０００４】
ＣＡＮでは、システムに参加するピアは、必ず上記論理空間内の小空間［Ｄ１ｌ，Ｄ１ｕ］×［Ｄ２ｌ，Ｄ２ｕ］×…×［Ｄｄｌ，Ｄｄｕ］を担当している。システムに参加する各ピアの担当する小空間は、それぞれ重ならず、それらの領域を全て合わせると、上記論理空間［０，１］×［０，１］×…×［０，１］を構成する。また、ピアは、必ず隣接する空間を担当するピアのアドレスを知っている。（探索鍵Ｋ、値Ｖ）のペアは、探索鍵Ｋに対してｄ個のハッシュ関数を適用することで得られる座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））を含む小空間を担当しているピアに対して、Ｈ０（Ｋ）をハッシュアドレスとして用いて登録される。すなわち、各ピアは、探索鍵Ｋにｄ個のハッシュ関数を適用して得られる座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））が、自身が担当する小空間内に存在するような（探索鍵Ｋ、値Ｖ）のペアを自身のハッシュ表に登録している。各ピアは、それぞれハッシュ表の一部を格納しており、それらが集まれば全体として１つのハッシュ表となっている。
【０００５】
上述したような構造をもったシステムを構築するために、ＣＡＮでは以下の手段を用いる。システムの開始時、ピアは、１つだけであり、想定した論理空間の全てを担当している。また、ハッシュ表全体もこのピアに格納されている。このとき、開始ピアの領域が論理空間全体であり、どの次元のどちら方向に対しても隣接する空間は、自分自身であるので、上記条件は満たされている。
【０００６】
次に、ピアがシステムに参加する場合、ＤＮＳやその他のシステム外の方法により、既にシステムに参加しているピアのアドレスを知る。このピアをエントリポイントピアと呼ぶ。エントリポイントピアは、その時々によって変わりうる。システムに初めて新規参加ピアが現れた場合には、システムに参加しているピアは１つだけなので、エントリポイントピアは開始ピアである。
【０００７】
次に、新規参加ピアは、自身のための探索鍵（Ｐ）をランダムに生成する。ｄ個のハッシュ関数をＰに対して適用することで、ｄ次元空間上の座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））が得られる。新規参加ピアは、エントリポイントピアに対して、座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））を担当しているピアを検索する要求を送信する。エントリポイントピアは、自身が担当する小空間内に座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））がある場合には、自身がそうであるとして応答する。そうでない場合には、メッセージ転送処理に入る。
【０００８】
メッセージ転送処理では、自身が担当する小空間［Ｄ１ｌ，Ｄ１ｕ］×［Ｄ２ｌ，Ｄ２ｕ］×…×［Ｄｄｌ，Ｄｄｕ］と検索要求を受けている座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））とを比較し、どの次元のどちらの方向の隣接ピアに転送すべきかを判断する。全ての次元ｉについて、Ｈｉ（Ｐ）が［Ｄｉｌ，Ｄｉｕ］の範囲に存在するかどうかを比較し、もし範囲外に存在する場合には、その次元ｊに対して、Ｈｊ（Ｐ）への絶対値が小さくなる方向、すなわちトーラスで見たときにＨｊ（Ｐ）に対してｊｌの方が近いかｊｕの方が近いかを比較して近い方向を転送方向と決める。転送方向にある隣接ピアを転送先ピアと判断する。
【０００９】
座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））は、転送先ピアに転送され、上述したのと同様に転送先ピアの担当する小空間内に座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））があるかどうかを判断する。なければ、再びメッセージ転送処理に入り、自身の担当する小空間内に座標（Ｈ１（Ｐ），Ｈ２（Ｐ），…，Ｈｄ（Ｐ））があるようなピアに到達するまで繰り返される。
【００１０】
自身の担当する小空間内に座標（Ｈ１（Ｐ）、Ｈ２（Ｐ）、…、Ｈｄ（Ｐ））があるピアが検索要求を受け取った場合、小空間分割処理に入る。
【００１１】
小空間分割処理では、直前に分割した次元の次の次元について、自身が担当する小空間を二分し、自身がその二分されたうちの片方を新たに担当することとし、もう一方を担当する権利を、検索要求を出した新規参加ピアに委譲する。二分された小空間のうち、担当する権利を委譲される小空間について、その小空間内に存在する座標をハッシュアドレスとするハッシュ表のエントリは、以後、新規参加ピアに格納される。
【００１２】
隣接ピアに対して、自身の空間が分割されたこと、および、新規参加ピアに分割された空間のうちの一方を担当する権利を委譲したことを通知し、それぞれの隣接ピア情報の更新を促す。
【００１３】
小空間分割処理を経ても、各ピアが担当する小空間を全て合わせると全体の論理空間になること、および、全ての次元に対して隣接ピアのアドレスを知っていることは守られる。ハッシュ表についても、各ピアがそれぞれ格納している部分を集めれば、全体として１つのハッシュ表になることは守られる。
【００１４】
システムに（探索鍵Ｋ、値Ｖ）のペアが登録される場合には、探索鍵Ｋをｄ個のハッシュ関数を適用することで座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ）を得る。エントリポイントピアをＤＮＳやその他の方法で見付だし、座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））の検索要求を送信する。必要に応じてメッセージ転送処理を経て、自身の担当する小空間内に座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））を含むピアに検索要求が到達し、（探索鍵Ｋ、値Ｖ）のペアは、そのピアに対して、Ｈ０（Ｋ）をハッシュアドレスとして登録される。
【００１５】
システムに対して、探索鍵Ｋに関連する値を検索する場合には、上記とほぼ同じ手段をとる。探索鍵Ｋをｄ個のハッシュ関数を適用することで座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））を得る。エントリポイントピアをＤＮＳやその他の方法で見付だし、座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））の検索要求を送信する。必要に応じて、メッセージ転送処理を経て、自身の担当する小空間内に座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））を含むピアに検索要求が到達し、Ｈ０（Ｋ）をハッシュアドレスとして登録されている（探索鍵Ｋ、値Ｖ）のペアが取り出される。
【００１６】
システムに参加するピアは、定期的なキープアライブメッセージによって、隣接ピアの状態をお互いに監視している。隣接ピアがネットワークまたはそのピア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合、キープアライブメッセージ応答のタイムアウトを待って隣接ピアが離脱したと判断し、障害回復処理に入る。離脱ピアに隣接する複数のピアがそれぞれ独立に障害回復処理に入りうる。
【００１７】
障害回復処理では、まず、テイクオーバタイマを起動する。この時、予め決められた定数に自身の担当する小空間の大きさをかけた時間のタイマを用いる。
【００１８】
タイマが終了したら、自身の担当する小空間の大きさを書き込んだテイクオーバメッセージを離脱ピアに隣接する全てのピアに送信する。
【００１９】
テイクオーバメッセージを受け取ったら、メッセージに書き込まれた小空間の大きさと自身の担当する小空間の大きさとを比較する。もし、自身の担当する小空間の方が大きかったならタイマをキャンセルする。そうでなければ、自身の担当する小空間の大きさを書き込んだテイクオーバメッセージで応答する。
【００２０】
自身が送信したテイクオーバメッセージに対して応答がなければ、テイクオーバ処理に入る。このとき、離脱ピアの隣接ピアのうち、アクティブで一番小さな小空間を持ったピアがテイクオーバの権利を得ている。
【００２１】
テイクオーバ処理では、テイクオーバの権利を得だピアは、離脱ピアが担当していた小空間を、自身の担当している小空間に加えて担当する。そのために、離脱ピアの全ての隣接ピアとの間に新たに隣接関係を構築する。
【００２２】
テイクオーバの結果として、１つのピアが本来複数のピアによって担当されていた複数の小空間を担当することになる。この状況に対して、定期的に小空間再割り当て処理を行う。
【００２３】
小空間再割り当て処理では、テイクオーバの結果として本来複数のピアによって担当されていた複数の小空間を担当することとなったピアは、隣接するピアとネゴシエーションを行い、担当する小空間の大きさがなるべく均等化されるように、お互いの小空間を適切に分割する。
【００２４】
まず、自身の担当する小空間が最後に分割された次元方向を確認し、その次元方向についての隣接ピアを確認する。もし、この隣接ピアが自身と同じ大きさの小空間を担当していれば、自身とその隣接ピアとが小空間再割り当ての対象ピアとなる。そうでない場合、すなわち、隣接ピアが自身の担当する小空間よりも小さい小空間を担当している場合には、隣接ピアにおいて同様の確認を行う。必要に応じてこの確認を繰り返し、同じ大きさの小空間を担当する２つのピアを確認する。この２つのピアが小空間再割り当ての対象ピアとなる。
【００２５】
小空間再割り当て対象の２つのピアは、一方が他方の小空間をテイクオーバし、他方は本来離脱ピアが担当していた小空間をテイクオーバする。
【００２６】
【発明が解決しようとする課題】
ところで、上述した従来技術による、ピアツーピア型分散ハッシュ表管理システムＣＡＮでは、システム構成ピアの離脱時に、離脱ピアの隣接ピアによってテイクオーバが行われ、離脱ピアの担当していた小空間がテイクオーバを行うピアによって担当される。テイクオーバを行ったピアは、本来複数のピアによって担当されていた複数の小空間を担当することとなるため、この状況に対して、小空間再割り当て処理が行われる。しかしながら、いずれの処理もピア間での調停が不可欠であり、処理終了までのしばらくの間システムは不安定な状態におかれてしまうという問題があった。
【００２７】
この発明は上述した事情に鑑みてなされたもので、離脱ピアの存在を感知した離脱ピアの隣接ピアによって、待機ピアに対して離脱ピアの存在を通知し、通知された待機ピアによって離脱ピアが担当していた小空間が担当されることで、システムを速やかに安定した状態に回復することができる障害回復システム、障害回復方法、障害回復プログラムおよび記録媒体を提供することを目的とする。
【００２８】
【課題を解決するための手段】
上述した問題点を解決するために、請求項１記載の発明では、システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録する登録手段と、システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにおいて予め決められた探索鍵を用いて待機ピアを検索する検索手段と、検索した待機ピアに対して離脱ピアの存在を通知する通知手段とを具備し、通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当させるということを特徴とする。
【００２９】
また、上述した問題点を解決するために、請求項２記載の発明では、システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録し、システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索し、検索した待機ピアに対して離脱ピアの存在を通知し、通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当させることを特徴とする。
【００３０】
また、上述した問題点を解決するために、請求項３記載の発明では、システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録するステップと、システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索するステップと、検索した待機ピアに対して離脱ピアの存在を通知するステップと、通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当するステップとをコンピュータに実行させることを特徴とする。
【００３１】
また、上述した問題点を解決するために、請求項４記載の発明では、システムに参加するピアを待機ピアとして予め決められたシステム共通の探索鍵と関連付けて登録するステップと、システム構成ピアがネットワークまたはそのビア自身に起きたなんらかの障害によって、あるいは自発的にシステムから離脱する場合に、その離脱ピアの存在を感知した離脱ピアの隣接ピアにより、予め決められた探索鍵を用いて待機ピアを検索するステップと、検索した待機ピアに対して離脱ピアの存在を通知するステップと、通知を受けた待機ピアにより、離脱ピアに代わって離脱ピアが担当していた小空間を担当するステップとをコンピュータに実行させる障害回復プログラムを記録したことを特徴とする。
【００３２】
この発明では、障害回復処理の時点で待機ピアがシステムに登録されている場合は、その待機ピアによって、離脱ピアによって担当されていた小空間が担当され、そのために１つのピアによって本来複数のピアによって担当されていた複数の小空間が担当されるという状況の発生を解消することが可能となり、システムを速やかに安定した状態に回復することが可能となる。
【００３３】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。
Ａ．実施形態の構成
図１は、本発明の実施形態による障害回復システムを構成するピアの内部構成を示すブロック図である。図１において、ピア１は、他ピアからのメッセージを受信する受信処理部２と、他ピアヘのメッセージを送信する送信処理部３と、キープアライブメッセージを用いて隣接ピアの状態などを定期的に診断する隣接ピア情報処理部４と、隣接ピアのアドレス情報などを格納する隣接ピア情報格納表５と、与えられた探索鍵にハッシュ関数を適用してハッシュアドレスを生成するためのハッシュアドレス生成処理部６と、（探索鍵、値）のペアを格納するためのハッシュ表７と、自身の担当する小空間に関する情報などを格納する自ビア情報格納表８とから構成されている。
【００３４】
次に、図２は、複数のピアによるハッシュ表管理システムの構成例を示す概念図である。図において、上部には、ハッシュ表管理システムの論理空間上におけるピアの配置を示しており、下部には、実際のネットワークにおけるピアａ〜ｊのそれぞれの配置を示している。
【００３５】
ハッシュ表管理システムを構成するトーラス状論理空間の次元数ｄとして「２」を採用し（すなわち、論理空間は［０，１］×［０，１］）、ハッシュ関数としてＨ０（）、Ｈ１（）、Ｈ２（）を採用した場合に、１０個のピアａ〜ｊがそれぞれ、
ａ：［０，０．２５］×［０，０．５］
ｂ：［０．２５，０．５］×［０，０．２５］
ｃ：［０．２５，０．５］×［０．２５，０．５］
ｄ：［０．５，０．７５］×［０，０．５］
ｅ：［０．７５，１］×［０，０．５］
ｆ：［０，０．２５］×［０．５，１］
ｇ：［０．２５，０．５］×［０．５，１］
ｈ：［０．５，０．７５］×［０．５，０．７５］
ｉ：［０．５，０．７５］×［０．７５，１］
ｊ：［０．７５，１］×［０．５，１］
の小空間を担当している状態を示している。
【００３６】
ビアａ〜ｊは、それぞれの担当する小空間により、同図の上部にあるように、論理空間上にマッピングされる。
【００３７】
また、ハッシュ関数Ｈ０（）、Ｈ１（）、Ｈ２（）は、それぞれ値域として、０＜＝Ｈ０（）＜２＾３２
０＜＝Ｈ１（）＜１
０＜＝Ｈ２（）＜１
を取るものとする。
【００３８】
Ｂ．処理体系
Ｂ−１．ピアの通常処理
既にシステムに参加しているピアは、メッセージ受信処理、メッセージ送信処理、隣接ビア情報処理、ハッシュアドレス計算処理、ハッシュ表検索処理、ハッシュ表登録処理、ハッシュ表削除処理、メッセージ転送処理を並列して行う。
【００３９】
Ｂ−２．メッセージ受信処理
メッセージ受信処理では、入力してくるメッセージを常時監視し、キープアライブメッセージであれば、隣接ピア情報処理を行い、登録要求メッセージ、あるいは、削除要求メッセージ、あるいは、検索要求メッセージであれば、ハッシュアドレス計算処理を行う。
【００４０】
Ｂ−３．メッセージ送信処理
メッセージ送信処理では、与えられたメッセージを与えられたアドレスに対して送信する。
【００４１】
Ｂ−４．隣接ピア情報処理
隣接ピア情報処理では、受け取ったキープアライブメッセージが、キープアライブ要求であった場合には、自ビア情報をメッセージとして、送信元であるピアに対してメッセージ送信処理を行う。キープアライブ応答であった場合には、送信元であるピアの情報を抽出して、隣接ピア情報を更新する。キープアライブ要求と応答で用いられるピア情報とは、具体的には、ピアのアドレス、担当している小空間の座標である。
【００４２】
また、隣接ピア情報処理では、定期的にキープアライブ要求をメッセージとして、隣接ピアのそれぞれを宛先として、それぞれにメッセージ送信処理を行う。同時にタイマを設定し、タイムアウトまでにキープアライプ応答が受信できなかった場合には、隣接ピアに障害が発生したものと判断し、障害回復処理に移る。
【００４３】
Ｂ−５．ハッシュアドレス計算処理
ハッシュアドレス計算処理では、受け取った探索鍵Ｋについて、ｄ個のハッシュ関数Ｈ１（）〜Ｈｄ（）を適用して、座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））を生成する。生成した座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））が自ピアの担当する小空間に存在しないときは、メッセージ転送処理に入る。一方、自ピアの担当する小空間に存在する場合には、以下の処理を行う。受け取ったメッセージが検索要求であれば、ハッシュ表検索処理を行う。受け取ったメッセージが登録要求であれば、ハッシュ表登録処理を行う。受け取ったメッセージが削除要求であれば、ハッシュ表削除処理を行う。
【００４４】
Ｂ−６．ハッシュ表検索処理
ハッシュ表検索処理では、受け取った探索鍵Ｋについて、ハッシュ関数Ｈ０（）を適用し、ハッシュアドレスＨ０（Ｋ）を得る。ハッシュ表からＨ０（Ｋ）をハッシュアドレスとしてもつエントリを検索する。
【００４５】
Ｂ−７．ハッシュ表登録処理
ハッシュ表登録処理では、受け取った探索鍵Ｋについて、ハッシュ関数Ｈ０（）を適用し、ハッシュアドレスＨ０（Ｋ）を得る。ハッシュ表のうちＨ０（Ｋ）をハッシュアドレスとしてもつエントリに対して、（探索鍵Ｋ、値Ｖ）のペアを登録する。
【００４６】
Ｂ−８．ハッシュ表削除処理
ハッシュ表削除処理では、受け取った探索鍵Ｋについて、ハッシュ関数Ｈ０（）を適用し、ハッシュアドレスＨ０（Ｋ）を得る。ハッシュ表のうちＨ０（Ｋ）をハッシュアドレスとしてもつエントリに対して、（探索鍵Ｋ、値Ｖ）のペアを削除する。
【００４７】
Ｂ−９．メッセージ転送処理
メッセージ転送処理では、座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））と隣接ピアのそれぞれが担当する小空間の座標とを比較して、いずれの隣接ピアに転送するのが座標（Ｈ１（Ｋ），Ｈ２（Ｋ），…，Ｈｄ（Ｋ））へ到達するため最適であるかを判断する。具体的には、自身が担当する小空間［Ｄ１ｌ，Ｄ１ｕ］×［Ｄ２１，Ｄ２ｕ］×…×［Ｄｄｌ，Ｄｄｕ］と検索要求を受けている座標（Ｈ１（Ｋ）、Ｈ２（Ｋ）、…、Ｈｄ（Ｋ）とを比較し、どの次元のどちらの方向の隣接ピアに転送すべきかを判断する。全ての次元ｉについて、Ｈｉ（Ｋ）が［Ｄｉｌ，Ｄｉｕ］の範囲に存在するかどうかを比較し、もし範囲外に存在する場合には、その次元ｊに対して、Ｈｊ（Ｋ）ヘの絶対値が小さくなる方向、すなわちトーラスで見たときにＨｊ（Ｋ）に対してＤｊｌの方が近いかＤｊｕの方が近いかを比較して近い方向を転送方向と決める。転送方向にある隣接ピアを転送先ピアと判断する。決定した転送先ピアに対してメッセージ送信処理を行う。
【００４８】
Ｂ−１０．待機ピアの登録処理
システム外から新たに参加するピアは、自身を待機ビアとして登録するかどうかを選択する。待機ピアとして登録することを選択したピアは、ＤＮＳやシステム外のその他の方法を利用して、エントリポイントピアの発見を行う。エントリポイントピアとは、システム外から最初にシステムにアクセスするためのピアのことである。発見したエントリポイントピアに対して、（探索鍵ＫＳ、自身のアドレスＡＳ）のペアを登録する要求のメッセージ送信処理を行う。ここで、ＫＳは、予め決められたシステム共通の探索鍵である。
【００４９】
（ＫＳ、ＡＳ）のペアをシステムに登録する手段は、通常の（探索鍵Ｋ、値Ｖ）のペアをシステムに登録する場合と同様である。すなわち、システムを構成する各ピアにおいて、必要に応じてハッシュアドレス計算処理とメッセージ転送処理を繰り返し、自身の担当する小空間内に座標（Ｈ１（ＫＳ）、Ｈ２（ＫＳ）、…、Ｈｄ（ＫＳ））を含むピアに登録要求が到達し、（ＫＳ、ＡＳ）のペアはそのピアに対して、Ｈ０（ＫＳ）をハッシュアドレスとして登録される。Ｈ０（ＫＳ）に対して既に待機ピアが登録されていた場合には、リスト構造などを用いて新たな待機ビア情報を追加する。このようにすることで、同時に複数の待機ピアをシステムに登録することができる。
【００５０】
Ｂ−１１．障害回復処理
障害回復処理では、まず、隣接ピアが離脱したと判断し、障害回復処理に入ったピアは、障害回復処理の開始時において、テイクオーバに入る前に、システムに待機ピアが登録されているかどうかを検索する。
【００５１】
待機ピアの検索は、予め決められた探索鍵ＫＳを用いて行われる。予め決められた探索鍵ＫＳにｄ個のハッシュ関数を適用することで、座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ），…，Ｈｄ（ＫＳ））を得る。自身が担当する小空間内に座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ），…，Ｈｄ（ＫＳ））が含まれる場合には、Ｈ０（ＫＳ）をハッシュアドレスとして登録されている待機ビア情報を取り出す。そうでない場合には、必要に応じて、メッセージ転送処理を経て、自身が担当する小空間内に座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ），…，Ｈｄ（ＫＳ））を含むピアに検索要求が到達し、Ｈ０（ＫＳ）をハッシュアドレスとして登録されている待機ピア情報が取り出される。
【００５２】
複数の待機ピア情報が格納されている場合には、任意に、あるいは、何らかのポリシー（登録順など）によって待機ピアを選択する。
【００５３】
Ｂ−１２．待機ピアヘの通知
上記手順によって得られた待機ビア情報から待機ピアのアドレスを知り、待機ピアに対して、離脱ピアの発生によって障害回復の必要のある小空間が存在することを通知する。
【００５４】
Ｂ−１３．待機ピアによるテイクオーバ
障害回復の必要のある小空間の存在を通知された待機ピアは、本来テイクオーバを行うはずであったピアに代わって、テイクオーバの権利を得る。テイクオーバの権利を得た待機ピアは、離脱ピアが担当していた小空間を、自身の担当する小空間として担当する。そのために、離脱ピアの全ての隣接ピアとの間に新たに隣接関係を構築する。離脱ピアが格納していたハッシュ表の一部についても、以後はテイクオーバを行った待機ピアが格納する。
【００５５】
待機ピアによるテイクオーバが行われるため、本来のテイクオーバは取りやめる。待機ピアは、テイクオーバによって、小空間を担当する通常のシステム参加ピアとなるため、待機ピアとしての登録を削除する。通常の（探索鍵Ｋ、値Ｖ）のペアの削除と同様の手順でシステムの削除を行う。
【００５６】
Ｃ．実施形態の動作
次に、図３は、ピアｎが新たにシステムに参加する際に、待機ピアの登録の様子を示す概念図である。また、図４は、図３に示す状況をプロトコルシーケンスで示すシーケンス図である。ピアｎが、自身を待機ピアとしてシステムに登録することを選択したとする。ピアｎは、ＤＮＳをルックアップすることでエントリポイントピアとしてピアｇのアドレスを得る（Ｓａ１）。続いてピアｎは、エントリポイントのピアｇに対して、予め決められた探索鍵ＫＳを用いて（探索鍵ＫＳ、自身のアドレスＡＳ）のペアを登録する要求を送信する（Ｓａ２）。
【００５７】
ここでは、ハッシュアドレス計算処理部６により得られた座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））が、０．５＜Ｈ１（ＫＳ）＜０．７５、０＜Ｈ２（ＫＳ）＜０．５であるとする。ピアｇは、受け取った座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））が自身の担当する小空間内に存在しないため、メッセージ転送処理を行う（Ｓａ３）。これらの処理を繰り返すことで、登録要求は、ピアｃを経てピアｄに到達する。
【００５８】
ビアｄでは、ハッシュアドレス計算処理部６により得られた座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））が自身の担当する小空間内に存在するため、ハッシュ表登録処理を受け付ける。ピアｄにおけるハッシュ表登録処理では、ハッシュアドレス計算処理部６によりＨ０（ＫＳ）を得て、ハッシュ表のハッシュアドレスＨ０（ＫＳ）のエントリに対して、（探索鍵ＫＳ、ピアｎのアドレスＡＳ）のペアを格納する（Ｓａ４）。
【００５９】
次に、図５は、離脱ピアの発生とそれを感知した隣接ピアとを示す概念図である。また、図６は、図５に示す状況をプロトコルシーケンスで示すシーケンス図である。ピアｈが何らかの理由によりシステムより離脱する（Ｓｂ１）。ビアｊは、ビアｈとの間で行っていたキープアライブメッセージの交換がタイムアウトすることによりピアｈの離脱を検知する（Ｓｂ２）。結果として、ピアｊにより障害回復処理が開始される。
【００６０】
次に、図７は、離脱ピアを感知した隣接ピアによる待機ピアの検索（障害回復処理）を示す概念図である。また、図８は、図７に示す状況をプロトコルシーケンスで示すシーケンス図である。ピアｊは、システムに待機ピアが登録されているかどうかを検索する。ハッシュアドレス計算処理部６により、予め決められた探索鍵ＫＳに対してハッシュ関数Ｈ１（）、Ｈ２（）を適用し、座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））を得る。座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））は、自身の担当する小空間内に存在しない座標であるので、メッセージ転送処理を行う（Ｓｃ１）。以上の処理を繰り返すことで、ビアｅを経て（Ｓｃ２）、検索要求はビアｄに到達する。
【００６１】
ハッシュアドレス計算処理部６により得られた、座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））は、ピアｄが担当する小空間内の座標であるので、検索要求はピアｄによって処理される。次いで、ピアｄの格納するハッシュ表７が検索され、ハッシュアドレスＨ０（ＫＳ）のエントリに対して登録された待機ピアの情報が取り出される（Ｓｃ３）。最後に、取り出された待機ピアのアドレス情報がピアｊに返される（Ｓｃ４）。
【００６２】
次に、図９は、離脱ピア発生の待機ピアヘの通知を示す概念図である。ピアｊは、得られた待機ピアｎの情報から待機ピアｎのアドレスを用いて、待機ピアｎに対して離脱ピアの発生により障害回復が必要な小空間が存在することを通知する（Ｓｄ１）。
【００６３】
次に、図１０は、本来離脱ピアの担当していた小空間の待機ピアによるテイクオーバを示す概念図である。また、図１１は、図１０に示す状況をプロトコルシーケンスで示すシーケンス図である。通知を受けた待機ピアｎは、直ちにテイクオーバを行う（Ｓｅ１）。すなわち、隣接ピア情報処理部４により、直ちに隣接ピアとの間でピア情報の交換を行い、それぞれの隣接ピア情報格納表５の内容を更新する。ピアｎは、自身が待機ピアではなくなったので、システムから待機ピアとしての登録を削除する。登録時の手順と同様に、座標（Ｈ１（ＫＳ），Ｈ２（ＫＳ））に関連して登録された自身の情報を削除する要求を転送する（Ｓｅ２）。削除要求を受け取ったピアｄは、ハッシュアドレス計算処理部６により、格納するハッシュ表からハッシュアドレスＨ０（ＫＳ）のエントリに対して登録されているピアｎの情報を削除する（Ｓｅ３）。
【００６４】
なお、上述した実施形態において、ピア１の各部の機能は、図示しない記憶部に記憶されたプログラムを実行することで実現するようになっている。記憶部は、ハードディスク装置や光磁気ディスク装置、フラッシュメモリ等の不揮発性メモリやＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）のような揮発性のメモリ、あるいはこれらの組み合わせにより構成されるものとする。また、上記記憶部とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含む。
【００６５】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワークや電話回線等の通信回線のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、上述した処理の一部を実現するためのものであってもよい。さらに、上述した処理をピア１に既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００６６】
以上、この発明の実施形態を、図面を参照して詳述してきたが、具体的な構成は、上記実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００６７】
【発明の効果】
以上説明したように、本発明によれば、離脱ピアの存在を感知した離脱ピアの隣接ピアによって、待機ピアに対して離脱ピアの存在を通知するようにしたので、システムに待機ピアが登録されている限りは、待機ピアによるテイクオーバによって、離脱ピアの担当していた小空間を担当させることができ、これにより、システムを速やかに安定した状態に回復することができるという利点が得られる。
【図面の簡単な説明】
【図１】本発明の実施形態による障害回復システムを構成するピアの内部構成を示すブロック図である。
【図２】複数のピアによるハッシュ表管理システムの構成例を示す概念図である。
【図３】ピアｎが新たにシステムに参加する際に、待機ピアの登録の様子を示す概念図である。
【図４】図３に示す状況をプロトコルシーケンスで示すシーケンス図である。
【図５】離脱ピアの発生とそれを感知した隣接ピアとを示す概念図である。
【図６】図５に示す状況をプロトコルシーケンスで示すシーケンス図である。
【図７】離脱ピアを感知した隣接ピアによる待機ピアの検索（障害回復処理）を示す概念図である。
【図８】図７に示す状況をプロトコルシーケンスで示すシーケンス図である。
【図９】離脱ピア発生の待機ピアヘの通知を示す概念図である。
【図１０】本来離脱ピアの担当していた小空間の待機ピアによるテイクオーバを示す概念図である。
【図１１】図１０に示す状況をプロトコルシーケンスで示すシーケンス図である。
【符号の説明】
１　ピア
２　受信処理部
３　送信処理部
４　隣接ピア情報処理部
５　隣接ピア情報格納表
６　ハッシュアドレス計算処理部
７　ハッシュ表
８　自ピア情報格納表
【図１】
2004072603.tif 000003
【図２】
2004072603.tif 000004
【図３】
2004072603.tif 000005
【図４】
2004072603.tif 000006
【図５】
2004072603.tif 000007
【図６】
2004072603.tif 000008
【図７】
2004072603.tif 000009
【図８】
2004072603.tif 000010
【図９】
2004072603.tif 000011
【図１０】
2004072603.tif 000012
【図１１】
2004072603.tif 000013