(57)【要約】【課題】トポロジが動的に変化し易いネットワーク内に分散配置されたデータの可用性を高めるとともに、データの種類に応じた柔軟な一貫性制御を実現する。【解決手段】各データについて、ネットワーク内にデータの更新が可能なコアデータ１７を一つ配置し、読み出しのみが可能な複製データ２７、３７、４７を複数分散配置することにより、データの一貫性を保持しつつデータの可用性を高める。コアデータ１７は決まった場所に配置するのではなく、データの利用状況やネットワークの状況に応じて動的に移動させる。また、各複製データ１７、２７、３７はそれぞれの利用頻度に応じた複製レベルを定め、コアデータ１７は複製レベルに応じて各複製データ２７、３７、４７との間の同期をとる。【選択図】      図１
2004171278.tif 000002
【特許請求の範囲】
【請求項１】
無線または有線のインタフェースを含む複数のノードを有し、一意な識別子で識別されるデータおよび該データの複製である複製データが前記ノード内に配置され、ユーザが前記識別子を用いて前記データへのアクセスを実行すると、該データあるいはいずれかの複製データへのアクセスが可能なネットワークにおける、データの複製管理方法であって、
データ生成時には、該データの生成、修正、あるいは削除のいずれかの操作である更新操作を実行可能なコアデータを生成して、該データの生成ノードに配置し、該データを参照したノードに該データの参照操作のみが実行可能な複製データを生成して、配置し、
各複製データは、前記コアデータが存在するノードのネットワークアドレス、該コアデータと該複製データの最新性の度合いを表す複製レベル、該複製データが有効であることを保証する有効期間、該複製データの更新時刻を表す複製リビジョン番号、および該複製データが認識している該コアデータの最新更新時刻を表すコアリビジョン番号を保持し、
前記コアデータは、全ての複製データの、ネットワークアドレスと複製レベルと有効期間から構成されるテーブル、および自身のデータのリビジョン番号を保持し、
前記コアデータが更新を受け付けた場合、前記テーブル上の各複製データの複製レベルにしたがって更新内容およびリビジョン番号を複製データに通知することにより各複製データとの同期を行い、
前記コアデータがノードを移動する際には、移動先の複製データにデータ内容および前記テーブルの情報を通知して複製データと同期をとった後、移動先の複製データをコアデータに変更し、移動前に把握していた全ての複製データに対して移動後のアドレスを通知する、データの複製管理方法。
【請求項２】
コアデータが存在するノードでデータへの更新操作要求が発生した場合、
該コアデータは、全複製データの内、同期保証が必要な、厳密な複製データに対し、データのリビジョン番号あるいはデータのリビジョン番号とデータからなる更新内容を通知し、
前記コアデータから更新を通知された厳密な複製データは更新内容を記憶するとともに前記コアデータへ了解した旨を通知し、
もし該コアデータが該更新の通知を行ってから一定時間内に全ての厳密な複製データから了解の通知を受けた場合、更新の実行依頼、およびデータが有効であることを保証する新しい有効期間を全ての複製データへ通知し、
もし前記コアデータが該更新の通知を行ってから一定時間内に了解の通知を受信できない厳密な複製データが存在する場合、前記コアデータが保持している該了解の通知を受信できなかった複製データのネットワークアドレスを削除し、了解の通知を送信してきた全ての複製データへ更新の失敗を通知し、
前記コアデータから更新を通知された複製データが一定時間内に更新の実行依頼を受信した場合、更新を通知された際に記憶した更新内容で該データを更新し、実行依頼で通知された、最新であることを保証する有効期間を記憶し、
前記コアデータから更新を通知された厳密な複製データが、前記コアデータから更新の失敗を通知された場合、あるいは一定時間内に更新の実行を依頼されなかった場合、該複製データを削除する、請求項１に記載のデータの複製管理方法。
【請求項３】
各複製データは前記有効期間が切れる前に該複製データの有効期間の延長要求を前記コアデータに対して送信し、同時に現在時刻＋規定値で計算される仮の有効期限を一時記憶し、
延長要求を受け取ったコアデータは延長要求の応答を該複製データに対して送信し、同時に該複製データに対して現在時刻＋規定値で計算される有効期限を改めて設定、記憶し、
延長要求の送信を行ってから一定時間内に延長要求の応答を受信した複製データは、一時記憶した仮の有効期限を新しい有効期限として改めて設定、記憶し、延長要求の送信を行ってから一定時間内に延長要求の応答を受信できなかった複製データは一時記憶した仮の有効期限を破棄する、請求項１または２に記載のデータ複製管理方法。
【請求項４】
各複製データは、同期保証を要求する強整合同期または強整合通知のレベル、あるいは同期保証を必要としない弱整合同期または弱整合通知の、いずれかの複製レベルを保持し、
前記コアデータがデータの更新要求を受けた場合、前記コアデータは複製レベルが強整合同期の複製データには請求項２に記載の同期保証を伴う方法でデータのリビジョン番号およびデータ内容を通知し、複製レベルが強整合通知の複製データには請求項２に記載の同期保証を伴う方法でデータのリビジョン番号のみを通知し、複製レベルが弱整合同期の複製には、複製レベルが強整合同期および強整合通知である複製データへの同期保証を伴う同期動作が完了した後、データのリビジョン番号およびデータ内容を前記複製データに通知し、複製レベルが弱整合通知の複製データには、複製レベルが強整合同期および強整合通知である複製データの同期保証を伴う同期動作が完了した後、データのリビジョン番号のみ前記複製データに通知し、
複製データがデータの更新を受けた場合、更新内容を前記コアデータへ転送して更新処理を依頼する、データの複製管理方法。
【請求項５】
各複製データは、同期保証を要求する強整合同期または強整合通知、あるいは同期保証を必要としない弱整合同期または弱整合通知の、いずれかの複製レベルを保持し、前記コアデータは各複製データのアドレスと複製レベルおよび有効期間を保持し、
クライアントはデータ参照時に参照ポリシとして、最新のデータを優先する「最新」または小さな処理遅延を優先する「局所」のいずれかのポリシを指定し、前記コアデータがデータの参照要求を受けた場合は、指定された参照ポリシにかかわらず自身のデータを、最新のデータであることを意味する付加情報「最新」とともに要求元へ通知し、
複製レベルが強整合同期または強整合通知である複製データがデータの参照要求を受け、かつ、指定された参照ポリシ「最新」であった場合において、もし要求発生時刻が該複製データの、最新であることを保証する有効期間を過ぎておらず、さらに該複製データの保持するコアデータのリビジョン番号と自身のリビジョン番号が等しい場合、該複製データ自身のデータを参照して付加情報「最新」とともに要求元へ通知し、もし要求発生時刻が該複製データの、最新であることを保証する有効期間を過ぎているか、あるいは該複製データの保持するコアデータのリビジョン番号と自身のリビジョン番号が等しくない場合、前記コアデータへの参照要求を転送し、参照処理を依頼し、
複製レベル強整合同期または強整合通知である複製データがデータの参照要求を受け、かつ指定された参照ポリシが「局所」であった場合において、もし要求発生時刻が該複製データの、最新であることを保証する有効期間を過ぎておらず、さらに該複製データの保持するコアデータのリビジョン番号と自身のリビジョン番号が等しい場合、該複製データ自身のデータを参照して付加情報「最新」とともに要求元へ通知し、もし要求発生時刻が該複製データの、最新であることを保証する有効期間を過ぎているか、あるいは該複製データの保持するコアデータのリビジョン番号と自身のリビジョン番号が等しくない場合、該複製データ自身のデータを参照して、古いデータであることを意味する付加情報「非最新」とともに要求元へ通知し、
複製レベルが弱整合同期または弱整合通知である複製データがデータの参照要求を受け、かつ、指定された参照ポリシが「最新」であった場合において、前記コアデータの最新のリビジョン番号を問い合わせ、もし自身のリビジョン番号と等しいならば該複製データ自身のデータを参照して付加情報「最新」とともに要求元へ通知し、自身のリビジョン番号と等しくないならば前記コアデータへ参照要求を転送し、参照処理を依頼し、
複製レベルが弱整合同期または弱整合通知である複製データがデータの参照要求を受け、かつ、指定された参照ポリシが「局所」であった場合において、該複製データの保持するコアデータのリビジョン番号と自身のリビジョン番号が等しい場合、該複製データ自身のデータを参照して、おそらく最新のデータであることを意味する付加情報「準最新」とともに要求元へ通知し、該複製データの保持するコアデータのリビジョン番号と自身のリビジョン番号が等しくない場合、該複製データ自身のデータを参照して付加情報「非最新」とともに要求元へ通知する、データの複製管理方法。
【請求項６】
各ノードにデータマネージャと呼ばれる実行プロセスが存在し、該データマネージャは、有線ネットワークにおけるサブネットあるいは無線ネットワークにおける一ホップの無線リンクによって定義される隣接ノード上のデータマネージャとの間で定期的に相互通信し、
その結果として隣接ネットワークリンクの接続・切断の有無を検知し、
接続あるいは切断があった場合には自ノード上に存在する複製データとコアデータに、接続あるいは切断の情報を通知する、請求項１から５のいずれか１項に記載のデータの複製管理方法。
【請求項７】
任意の複製データがコアデータとのネットワークの接続性が失われたことを検出した場合、該複製データは通信可能な範囲の複製データのリビジョン番号を調査し、最も新しいリビジョン番号を返した複製データを新たにコアデータに昇格させ、その後は請求項１から６のいずれかに記載の方法と同様の処理を行なう、データの複製管理方法。
【請求項８】
請求項６に記載の方法によりネットワークの接続性を検出し、任意のコアデータがネットワークの新たな接続を通知された場合、該コアデータはネットワーク全体へのブロードキャストによって該複製データと同じデータ識別子を持つコアデータの存在を探索し、
同じ識別子を持つ自分以外のコアデータを発見した場合、該コアデータの変更点を組み合わせて新たなコアデータを生成し、自己を除く全てのコアデータを複製データへ降格させ、
その後は請求項１〜７のいずれかに記載のデータの複製管理方法と同様の複製管理を継続する、データの複製管理方法。
【請求項９】
無線または有線のインタフェースを有し、ネットワークを構成するノードで行われる情報処理方法であって、
クライアントがデータ生成要求を送信するステップと、
前記データ生成要求を受けてデータマネージャがコアデータを生成するステップと、
前記コアデータが自身のローカルデータを生成して、前記クライアントに生成応答を返すステップと、
前記クライアントがデータを参照したい場合、前記コアデータにデータ参照要求を送信するステップと、
前記コアデータが自身のデータを参照し、参照応答を返すステップと、
前記クライアントがデータを更新したい場合、前記コアデータにデータ更新要求を送信するステップと、
前記コアデータが自身のデータに対し更新を実行し、更新の成否を更新応答として前記クライアントへ返すステップを有する情報処理方法。
【請求項１０】
無線または有線のインタフェースを有し、複製データが存在しない、ネットワークを構成するノードで行われる情報処理方法であって、
クライアントがデータマネージャに対してデータ参照要求を送信するステップと、
前記データマネージャが、ネットワーク上で隣接するノードのデータマネージャに対してブロードキャストによってコアデータ検索要求を送信するステップと、
前記データマネージャは前記コア検索要求に対して、隣接するノードのコアデータのオブジェクトＩＤを含むコア通知を受信すると、隣接するノードのデータマネージャにデータ参照要求を送信するステップと、
前記データマネージャは隣接するノードのデータマネージャからそのコアデータが保持するデータを内容とする参照応答を受信すると、該参照応答をデータ参照要求元のクライアントへ返送するステップと、
前記データマネージャが複製データを生成し、前記参照応答に含まれていたデータと、システムで規定の、複製データの最新性の度合いを表す複製レベルを仮登録するステップと、
前記複製データが隣接するノードのコアデータに対して複製データ追加要求を送信すると同時に、タイマを起動するステップと、
前記複製データが、隣接するノードのコアデータから複製データ生成実行をタイマが起動されてから一定時間内に受信すると、仮登録されたデータを本登録し、一定期間内に受信できなかった場合、仮登録されたデータを破棄するステップを有する情報処理方法。
【請求項１１】
有線または無線のインタフェースを有し、複製データが存在し、ネットワークを構成するノードで行われる情報処理方法であって、
クライアントが自ノードの複製データに対してデータ参照要求を送信するステップと、
前記データ参照要求に付帯される参照ポリシが「局所」である場合、あるいは前記複製データの最新性の度合いを示す複製レベルが「強整合同期」である場合、あるいは前記複製データの複製レベルが「強整合通知」で、かつ前記複製データの持つ、該複製データの更新時刻を表わすリビジョン番号とコアデータの最新更新時刻を表すコアリビジョン番号が一致している場合、複製データは自身のローカルデータを参照し、要求元クライアントへ参照応答として返送し、このとき、前記複製データの複製レベルが「強整合同期」の場合、あるいは複製データの複製レベルが「強整合通知」で、かつ前記複製データの持つリビジョン番号とコアリビジョン番号が一致している場合は、参照データが最新であることを意味する「最新」を付加情報として参照応答に含め、前記複製データの複製レベルが「弱整合同期」の場合、あるいは前記複製データの複製レベルが「弱整合通知」で、かつ前記複製データの持つリビジョン番号とコアリビジョン番号が一致している場合は、参照データがおそらく最新であることを意味する「準最新」を付加情報として参照応答に含め、前記複製データの複製レベルが「強整合通知」か「弱整合通知」の場合で、かつ前記複製データの持つリビジョン番号とコアリビジョン番号が一致していない場合は、参照データが古いことを意味する「非最新」を付加情報として参照応答に含めるステップと、
前記クライアントが、前記複製データに対して参照ポリシが「最新」であるデータ参照要求を送信するステップと、
前記複製データの複製レベルが「強整合同期」である場合、あるいは複製データの複製レベルが「強整合通知」で、かつ前記複製データの持つリビジョン番号とコアリビジョン番号が一致している場合は、前記データ参照要求の場合と同じようにノードでローカルに処理を行い、一方、前記複製データの複製レベルが「強整合通知」で、かつ前記複製データの持つリビジョン番号とコアリビジョン番号が一致していない場合、前記複製データの把握するコアデータに対して、データ参照要求元クライアントのオブジェクトＩＤを含めたデータ参照要求を送信するステップと、
前記クライアントが、前記コアデータがローカルの最新データを参照して返送してきた参照応答を受信するステップと、
前記複製データの複製レベルが「弱整合同期」または「弱整合通知」の場合、前記複製データがリビジョン参照要求を前記コアデータに対して送信し、前記参照応答に含まれるコアデータのリビジョン番号と自身のリビジョン番号を比較し、比較の結果が一致していない場合、前記コアデータに対して前記クライアントのオブジェクトＩＤを含めたデータ参照要求を送信し、比較の結果が一致した場合は前記複製データが自身のローカルデータを参照して前記クライアントに参照応答を返送するステップを有する情報処理方法。
【請求項１２】
有線または無線のインタフェースを有し、複製データが存在する、ネットワークを構成するノードで行われる情報処理方法であって、
クライアントが自ノード上の複製データにデータ更新要求を送信するステップと、
データ更新要求を受信した複製データが、データ更新要求を隣接するノードのコアデータに転送するステップと、
前記コアデータから更新要求を受信した前記複製データが、前記コアデータに対して確認応答を返送すると同時にタイマを起動するステップと、
前記複製データが前記コアデータから一定時間以内に更新実行を受信すると、更新要求で通知されたデータにしたがって更新処理を行うステップとを有する情報処理方法。
【請求項１３】
前記コアデータがタイマが起動されてから一定時間内に確認応答を受信できず、更新を破棄し、更新の失敗を更新応答として返送してくると、クライアントが前記複製データへ更新取消を通知するステップをさらに有する、請求項１２に記載の情報処理方法。
【請求項１４】
有線または無線のインタフェースを有し、複製データが存在する、ネットワークを構成するノードで行われる情報処理方法であって、
複製データが複製期限延長要求を隣接するノードのコアデータに送信すると同時にタイマを起動するステップと、
前記コアデータから延長応答を受信した複製データが、該延長応答に含まれる新たな有効期限を自身に設定し、延長応答が失われた場合、タイムアウトによって複製データ自身を破棄するステップを有する情報処理方法。
【請求項１５】
データ更新要求をクライアントから受信した複製データが他ノードのコアデータへコア移動を送信するステップと、
前記コアデータからコア移動応答を受信した複製データがコアデータへと昇格するステップを有する、請求項１２に記載の情報処理方法。
【請求項１６】
有線または無線のインタフェースを有し、複製データが存在する、ネットワークを構成するノードデータにおける情報処理方法であって、
クライアントが複製データにデータ参照要求を送信するステップと、
該データ参照要求を受信した複製データが、複製データの最新性の度合いを示す複製レベルと参照ポリシの関係から他ノードのコアデータへアクセスする必要があったとき、他ノードのコアデータへデータ参照要求を送信し、同時にタイマを起動し、コアデータからの参照応答を待つステップと、
タイムアウトが起こり、前記複製データは前記コアデータとのネットワーク接続が失われたことを認識すると、コア探索をネットワークブロードキャストによって他ノードへ送信し、コアデータを探索し、同時にタイマを起動するステップと、
前記複製データはタイムアウトまでの一定時間を待機してコア探索応答の受信を待ち、タイムアウトの後、コア探索応答のあった複製データと自分自身の中から、最も新しいリビジョン番号を持つ複製データを選択し、選んだ複製データに対してコア生成要求を送信するステップと、
コア生成応答を受信した前記複製データはコアデータが再生されたことを認識し、新しいコアデータに対して改めてデータ参照要求を送信し、データの参照を行うステップを有する情報処理方法。
【請求項１７】
有線または無線のインタフェースを有し、コアデータが存在するネットワークを構成するノードにおける情報処理方法であって、
データマネージャが、直接通信可能な全ての隣接ノード上のデータマネージャに向けて定期的に持続性調査メッセージを送信するステップと、
他ノードとの接続が回復した後、新たに該他ノード上のデータマネージャから接続応答を受信すると、自ノード上のコアデータに新規接続を通知するステップと、
前記コアデータが、該データの識別子を含んだコア存在確認メッセージをネットワークブロードキャストによって全てのノード上のデータマネージャに対して送信するステップと、
コア存在確認を受信したデータマネージャが、該識別子で識別されるデータが存在してコア存在応答を返送すると、前記コアデータが、自分のデータ内容を含めてコア統合を送信するステップと、
コア統合を受信したコアデータがデータの統合に成功し、コア統合応答を返送すると、これを受信した前記コアデータが自身を複製データに降格するステップを有する情報処理方法。
【請求項１８】
有線または無線のインタフェースと、クライアントと、データの生成、修正、あるいは前除のいずれかの操作である更新操作を実行可能なコアデータと、前記コアデータをデータ生成時に生成し、該データを参照した他のノードに該データの参照操作のみが可能な複製データを生成するデータマネージャを有し、前記コアデータは、全ての複製データの、ネットワークアドレスと複製レベルと有効期間から構成されるテーブル、および自身のデータのリビジョン番号を保持し、前記コアデータは、更新を受け付けた場合、前記テーブル上の各複製データの複製レベルにしたがって更新内容およびリビジョン番号を複製データに通知することにより各複製データとの同期を行い、前記コアデータがノードを移動する際には、前記コアデータは、移動先の複製データにデータ内容および前記テーブルの情報を通知して複製データと同期をとった後、移動先の複製データをコアデータに変更し、移動前に把握していた全ての複製データに対して移動後のアドレスを通知する第１のノードと、
有線または無線のインタフェースと、クライアントと、データマネージャと、他ノードのコアデータの参照操作のみが実行可能な複製データを有し、前記複製データは、前記コアデータが存在するノードのネットワークアドレス、該コアデータと該複製データの最新性の度合いを表す複製レベル、該複製データが有効であることを保証する有効期間、該複製データの更新時刻を表す複製リビジョン番号、および該複製データが認識している該コアデータの最新更新時刻を表すコアリビジョン番号を保持している１つ以上の第２のノードを含むネットワーク。
【請求項１９】
有線または無線のインタフェースと、クライアントと、データの生成、修正、あるいは削除のいずれかの操作である更新操作を実行可能なコアデータと、前記コアデータをデータ生成時に生成し、該データを参照した他のノードに該データの参照操作のみが可能な複製データを生成するデータマネージャを有し、
前記コアデータは、全ての複製データの、ネットワークアドレスと複製レベルと有効期間から構成されるテーブル、および自身のデータのリビジョン番号を保持し、
前記コアデータは、更新を受け付けた場合、前記テーブル上の各複製データの複製レベルにしたがって更新内容およびリビジョン番号を複製データに通知することにより各複製データとの同期を行い、
前記コアデータがノードを移動する際には、前記コアデータは、移動先の複製データにデータ内容および前記テーブルの情報を通知して複製データと同期をとった後、移動先の複製データをコアデータに変更し、移動前に把握していた全ての複製データに対して移動後のアドレスを通知するノード。
【請求項２０】
有無または無線のインタフェースと、クライアントと、データマネージャと、他ノードのコアデータの参照操作のみが実行可能な複製データを有し、
前記複製データは、前記コアデータが存在するノードのネットワークアドレス、該コアデータと該複製データの最新性の度合いを表す複製レベル、該複製データが有効であることを保証する有効期間、該複製データの更新時刻を表す複製リビジョン番号、および該複製データが認識している該コアデータの最新更新時刻を表すコアリビジョン番号を保持しているノード。
【請求項２１】
請求項１から１７のいずれか１項に記載の方法をコンピュータに実行させるためのプログラム。
【請求項２２】
請求項２１に記載のプログラムを記録したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は有線または無線のインタフェースを含む複数のノードを有し、一意な識別子で識別されるデータおよび該データの複製である複製データが前記ノード内に配置され、ユーザが識別子を用いてデータへのアクセスを実行すると、該データあるいはいずれかの複製データへのアクセスが可能なネットワークにおける、データの複製管理方法に関する。
【０００２】
【従来の技術】
従来、複製データの管理方法として、ネットワーク内の単一、かつ固定のマスタデータのみが更新可能とし、規定の同期ポリシにしたがってマスタデータの更新内容を通信により逐次複製データにも反映させる、あるいは複製データは必ずしも最新であることを保証しない、などの方法がとられてきた。
【０００３】
また、マスタデータへの負荷の集中を避ける目的や、ネットワーク内のトラフィック削減のため、そしてネットワーク切断によりマスタデータとの通信が不可能になった場合のために、マスタデータ以外の複製データに対しても更新を認める方法が考えられている。
【０００４】
例えばキャッシュを用いる分散ファイルシステムにおいては、ファイルサービスを利用するクライアント端末上にファイルの一部をキャッシュとして保存しておき、ファイルの可用性を高めている。非特許文献１で述べられている分散フィルムシステムＣｏｄａにおける複製管理方法では、クライアントからサーバへアクセスできない切断状態においては、クライアントのキャッシュに対して操作を行うことを許す。その後サーバへ再接続したときには該キャッシュへの更新情報とサーバ内の情報を比較する。比較の結果、切断時に同時にデータが更新されたことによって生じた不整合を検出した場合は、ユーザに通知して人手による修復を行う。この手法は完全に楽観的なデータ一貫性制御であり、一時的なデータの不整合は許している。
【０００５】
一方、非特許文献２では、移動可能、かつ単一の更新可能なデータとしてコアデータを定義し、全ての複製データに有効期限を設けることによって厳密な一貫性制御を可能にしている。コアデータが受け付けられた更新内容は複製データへと同期されるが、このとき全ての有効期限内の複製データへの同期完了が確認できなかった場合には更新操作は取り消され失敗し、同期完了が確認できなかった複製データの有効期限が切れるのを待って、再度更新を試みる。このため、ネットワークリンクが不安定で通信メッセージが失われやすい環境においても、更新内容の同期を厳密に保証できる複製データ管理が実現できる。また、更新を行う端末に予めコアデータを移動しておくことにより、ネットワーク切断のタイミングが既知でない場合においても、離脱した端末において継続的にデータの更新が可能となる。
【０００６】
【発明が解決しようとする課題】
【０００７】
【非特許文献１】
Ｋｉｓｔｌｅｒ，  Ｊ．  Ｊ．，  Ｓａｔｙａｎａｒａｙａｎａｎ，  Ｍ．  著、“Ｄｉｓｃｏｎｎｅｃｔｅｄ  Ｏｐｅｒａｔｉｏｎ  ｉｎ  ｔｈｅ  Ｃｏｄａ  Ｆｉｌｅ  Ｓｙｓｔｅｍ”，  ｉｎ  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ，  Ｆｅｂ．  １９９２，  Ｖｏｌ．  １０，  Ｎｏ．１，  ｐｐ．３−２５
【非特許文献２】
中村元紀、井上知洋、久保田稔、“アドホックットワーク環境のためのデータ管理方式”信学総大Ｂ―１５―６，    ２００２年３月。
【０００８】
無線リンクによって構成されるネットワークが現在以上に普及し、ユーザの利用形態が多様化する将来のネットワーク環境では、トポロジが動的に変化するネットワークが一般化すると考えられる。このような環境では、モバイル端末が単独で移動してネットワークから離脱するだけではなく、無線リンクなどによって構成されるネットワークそのものが、ネットワークの単位で移動し、基幹ネットワークから離脱するようなケースが想定される。このような環境において従来の複製データ管理方法では、データの可用性を十分に保つことができない。
【０００９】
前述のように、Ｃｏｄａなどの分散ファイルシステムでは、楽観的な一貫性制御を行い、マスタデータとなるファイルサーバとのネットワーク接続が失われている場合にもクライアント端末上のキャッシュデータの更新を許している。しかしマスタデータは常に固定のファイルサーバ上に存在しているため、複数のクライアント端末を含むネットワークがネットワークの単位で移動しファイルサーバとの接続を失った場合、クライアント端末上のキャッシュデータ間では同期が全く行われない。この結果、クライアント端末の数に応じて異なる内容のキャッシュデータが生成されてしまう可能性があり、これらの無数のバージョンのデータの入手により統合するコストを考えると、現実的なデータの運用が不可能になってしまう。
【００１０】
一方、非特許文献２では、マスタデータの位置を移動可能とすることによってトポロジの動的なネットワークにおいてもデータの一貫性制御を実現している。しかし、厳密な一貫性制御ポリシのみを考慮しているため、ネットワークの分割に伴ってマスタデータとの接続を失ってしまったネットワーク内の端末は、複製データの有効期限切れ以降、該データに対して全くアクセスできなくなってしまうという問題がある。
【００１１】
また、全ての複製データに対して同期完了を確認した後に更新をコミットするため、  複製データの数が多くなった場合に更新が失敗する確率が高くなってしまう、あるいは更新完了までの遅延時間が長くなってしまう。
【００１２】
本発明の目的は、トポロジが動的に変化してネットワークの分割が起こり得るネットワーク環境において、なるべくデータの可用性を保ちながら、ユーザの要求に応じた柔軟な一貫性制御を実現する複製データの管理方法を提供することにある。
【００１３】
【課題を解決するための手段】
非特許文献２の複製データ管理方法は以下の二点を特徴としている。
【００１４】
（１）分散配置されたデータの複製のうちの一つの複製（以下コアデータと呼ぶ）のみに該データの更新権を与え、該コアデータと通信可能な複製のみを有効とすることによって複製データ間の一貫性を厳格に保証する。
【００１５】
（２）コアデータは端末に固定的なものではなく、任意の端末に動的に変更可能とする。
【００１６】
本発明の複製データ管理方法においては前記目的を達成するために、上記の（１）（２）に加えて、以下の三点を実現する。
【００１７】
（３）複製データは、同期が必要な度合いに応じて複数の「複製レベル」を選択可能とする。
【００１８】
（４）コアデータを失ったネットワークにおいては、既存の複製データの中から一つを選んでコアデータとして再生させ、複製データを継続する。
【００１９】
（５）継続されたネットワーク上で同一の識別子で識別されるデータについて、コアデータが複数見つかった場合は、それらのコアデータを統合して新しいデータを生成し、そのデータを単一のコアデータとして複製データ管理を継続する。
【００２０】
本発明の複製データ管理方法では、（３）によって、同期保証の必要な複製データの数を削減することが可能となり、更新の失敗確率および更新完了までの遅延時間を小さくすることができる。また、（４）および（５）によって、ネットワークの分割が起こった場合においてもそれぞれのネットワーク内でデータの一貫性制御が可能となり、同時に発生するデータのバージョン数は孤立したネットワークの数程度に限られる。
【００２１】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００２２】
図１は本発明の一実施形態のネットワークの構成図である。
【００２３】
本実施形態の無線ネットワークは、それぞれ無線ネットワークインタフェースを有するノード１０とノード２０、ノード３０、ノード４０と、無線ネットワークインタフェースを有する無線アクセスポイント０１と無線アクセスポイント０２から構成される。なお、無線ネットワークインタフェースの代りに有線ネットワークインタフェースを有していてもよい。
【００２４】
ノード１０はノード２０のみと、ノード２０はノード１０と無線アクセスポイント０１のみと、ノード３０はノード４０と無線アクセスポイント０２のみと、ノード４０はノード３０のみと、それぞれ直接通信可能である。無線アクセスポイント０１は無線アクセスポイント０２およびノード２０のみと、無線アクセスポイント０２は無線アクセスポイント０１およびノード３０のみと、それぞれ直接通信可能である。また、無線アクセスポイント０１、０２はリピータハブとして動作し、受信した通信内容をそのまま無線ネットワークインタフェースから再送する動作を行う。このため、ノード２０とノード３０は無線アクセスポイント０１と０２を経由して互いに通信可能である。
【００２５】
初期状態では各ノード１０、２０、３０、４０にはクライアントからのデータ操作要求を受け付けるデータマネージャ１３、２３、３３、４３と、データ操作を要求するクライアント１５、２５、３５、４５が存在し、コアデータ１７、２７および複製データ３７、４７は存在しない。
【００２６】
データマネージャ１３はデータ生成時には、該データの生成、修正、あるいは削除のいずれかの操作である更新操作を実行可能なコアデータ１７を生成して、該データの生成ノード１０に配置し、該データ１７を参照したノード２０、３０、４０に該データの参照操作のみが実行可能な複製データ２７、３７、４７を生成して、配置する。各複製データ２７、３７、４７はコアデータ１７が存在するノード１０のネットワークアドレス、コアデータ１７と複製データ２７、３７、４７の最新性の度合いを表す複製レベル、複製データ２７、３７、４７が有効であることを保証する有効期間、複製データ２７、３７、４７の更新時刻を表す複製リビジョン番号、および複製データ２７、３７、４７が認識しているコアデータ１７の最新更新時刻を表すコアリビジョン番号を保持している。コアデータ１７は、全ての複製データ２７、３７、４７のネットワークアドレスと複製レベルと有効期間から構成されるテーブル、および自身のデータのリビジョン番号を保持している。
【００２７】
本実施形態においては、クライアント、データマネージャ、コアデータおよび複製データは互いに通信相手のオブジェクトＩＤを指定することにより、位置に依存せず非同期にメッセージ通信可能である。さらに、本実施形態においては、各ノード１０、２０、３０、４０から無線の届く範囲に存在する全てのノードへのブロードキャスト、いくつかのノードへのマルチキャスト、および特定のノードへのユニキャスト通信が可能であるとする。また、いくつかのノードが通信を中継することにより、無線の届かない範囲に存在するノードに対してもユニキャストおよびマルチキャスト通信が可能であるものとする。
【００２８】
図２はデータマネージャによるデータの実現方法を示している。データマネージャ１３、２３、３３、４３（以下、総称してデータマネージャ６１と称す）は一意な識別子であるデータ名６３と、該データに対応するデータオブジェクト（以下、単にデータと表記）６４のオブジェクトＩＤとの対応表であるデータ対応表６２と、ノード６０上で生成されたデータ名を記録した作成済データ表６３を管理するものとする。ここで、データ名はノードＩＤと任意の文字列から構成されるものとし、オブジェクトＩＤはノードＩＤと任意の数字の列から構成されるものとする。また、データマネージャ６１は他ノードや自ノード６０の他のオブジェクトからデータ生成要求やデータ更新要求やデータ参照要求を受信するものとし、各要求は対応するデータ名を含むものとする。
【００２９】
図３は本実施形態におけるデータマネージャ６１の動作を示すフローチャートである。
【００３０】
メッセージ受信待ちし（ステップ１０１）、メッセージを受信する（ステップ１０２）と、メッセージ種別を判断する（ステップ１０３）。
【００３１】
データ生成要求を受信した際、もし作成済データ表６３あるいはデータ対応表６２に、該データ生成要求中のデータ名に対応するエントリが存在したら、要求元にエラーを返す（ステップ１０４―１０６）。そうでなければ自ノードにデータ６４を作成して該データ生成要求の要求元をデータ６４に通知するとともに、該データ生成要求中のデータ名に対応するオブジェクトＩＤとして、データ６４のオブジェクトＩＤを登録し（ステップ１０７）、該データ生成要求中のデータ名を作成済データ表６３に登録する（ステップ１０８）。
【００３２】
データマネージャ６１がデータ更新要求あるいはデータ参照要求を受信した際、もし該データ名を含むエントリがデータ対応表６２に存在すれば、対応するオブジェクトＩＤに対して該要求を転送する（ステップ１０９、１１０）。データがデータ対応表６２に存在しなければ、周りのノードのコアデータ検索要求をブロードキャストする（ステップ１１１）。なお、コアデータ検索要求には検索元オブジェクトＩＤとシーケンス番号を含める。コアデータ検索要求に対するコアデータ通知を一定時間受信しなかったら、データ更新要求あるいはデータ参照要求の要求元にエラーを返す（ステップ１１２、１１４）。もし一定時間内にコアデータ通知を受信した場合、自ノードにデータ６４を作成して該コア通知内に含まれるコアデータのオブジェクトＩＤ、および該データ更新要求あるいはデータ参照要求元をデータ６４に通知する（ステップ１１２、１１３）。
【００３３】
データマネージャ６１がコアデータ検索要求を受信した場合、もし該コアデータ検索要求の検索元オブジェクトＩＤが自身のオブジェクトＩＤと一致するか、該コアデータ検索要求の検索元オブジェクトＩＤとシーケンス番号の組を既に受信済であったら、該コアデータ検索要求を破棄する（ステップ１１５―１１７）。そうでなければ、もし該コアデータ検索要求中のデータ名がデータ対応表６２に存在すれば、該当するエントリのオブジェクトＩＤを該コアデータ検索要求の要求元オブジェクトＩＤに対して返送する（ステップ１１８、１１９）。上記のどちらの条件も当てはまらなければ、該コアデータ検索要求の検索元オブジェクトＩＤとシーケンス番号の組を記憶し、該コアデータ検索要求を周りのノードにブロードキャストする（ステップ１１８、１２０）。
【００３４】
データは他ノードや自ノード内の他のオブジェクトからデータ更新要求やデータ参照要求を受信するものとし、各要求は対応するデータ名を含むものとする。
【００３５】
図４は図１のネットワークにおいてノード１０でデータ生成要求が発生し、その後続けてデータの参照要求と更新要求が発生した場合のデータ生成動作のシーケンスを示している。図１において、初期状態として全てのノード１０、２０、３０、４０にはデータマネージャ１３、２３、３３、４３とクライアント１５、２５、３５、４５だけが存在し、コアデータ１７、２７および複製データ３７、４７は存在しない。
【００３６】
まず、ノード１０上のクライアント１５がメモリ上のファイルの保存などのため、データの生成要求をノード１０上のデータマネージャ１３に送信する（ステップ１２１）。データマネージャ１３はノード１０上にコアデータ１７を生成し、コアデータ１７は自身のローカルデータを生成して（ステップ１２３）、クライアント１５へ生成応答を返す（ステップ１２４）。次に、クライアント１５がデータを参照したい場合、ノード１０上のコアデータ１７にデータ参照要求を送信する（ステップ１２５）。コアデータ１７は自身のデータを参照し（ステップ１２７）、クライアント１５へ参照応答を返す（ステップ１２８）。次に、クライアント１５がデータを更新したい場合、コアデータ１７にデータ更新要求を送信する（ステップ１３０）。コアデータ１７は自身のデータに対し更新を実行し（ステップ１３２）、更新の成否を更新応答としてクライアント１５へ返す（ステップ１３３）。更新が成功した場合、コアデータ１７のリビジョン番号は１増加する。以後、コアデータへの更新操作が成功した場合には該コアデータのリビジョン番号は常に１ずつ増加することとする。
【００３７】
図５は図１のネットワークにおいて複製データの存在しないノード２０でデータの参照要求が発生した場合の動作のシーケンスを示している。
【００３８】
ノード２０上のクライアント２５は該データに対する複製データあるいはコアデータのオブジェクトＩＤを知らないため、ネットワーク上で隣接するデータマネージャに対してブロードキャストによってコアデータ検索要求を送信する（ステップ１４０）。本実施形態では、コア検索要求を受信したデータマネージャ１５がコアデータ１７のオブジェクトＩＤを知っているため、コアデータ１７のオブジェクトＩＤをコア通知１４２に含めてデータマネージャ２３へ返送する。コア通知を受信した（ステップ１４２）データマネージャ２３は通知されたオブジェクトＩＤに基づいて、データマネージャ１３に対してデータ参照要求を送信する（ステップ１４５）。データ参照要求を受信した（ステップ１４６）データマネージャ１３はコアデータ１７が保持するデータを参照し（ステップ１４７）、データの内容を参照応答としてデータマネージャ２３へ返送する（ステップ１４８）。参照応答を受信したデータマネージャ２３は、参照応答をデータ参照要求の要求元であるクライアント２５へ返送する（ステップ１４０）。
【００３９】
その後、データマネジャー２３はノード２０上に複製データを生成し（ステップ１５０）、参照応答に含まれていたデータと、システムで規定の複製レベルを仮登録する（ステップ１５１）。その後、複製データ２７はコアデータ１７に対して、複製データ追加要求を送信する（ステップ１５２）と同時にタイマを設定する（ステップ１５３）。複製データ追加要求を受信したコアデータ１７は、複製データ追加要求に含まれる複製データ２７のオブジェクトＩＤ（アドレス）とシステム規定の複製有効期限と複製レベルを記憶し（ステップ１５４）、複製データ２７に対して複製データ生成実行を送信する（ステップ１５５）。複製データ２７が複製データ生成実行を一定時間以内に受信できた場合、複製データ２７は仮登録されたデータを本登録する（ステップ１５６）。複製データ２７が複製データ生成実行を一定時間以内に受信できなかった場合、複製データ２７が仮登録されたデータを破棄することにより複製データ２７のコアデータ１７への登録操作は取り消される。
【００４０】
図６は図１のネットワークにおいて複製データの存在するノード２０でデータの参照要求が発生した場合の動作のシーケンスを示している。
【００４１】
複製データ２７は、同期保証（全ての厳密な複製データについてデータの更新同期あるいは更新通知）を要求する強整合同期または強整合通知のレベル、あるいは同期保証を必要としない弱整合同期または弱整合通知の、いずれかの複製レベルを保持している。
【００４２】
ノード２９上のクライアント２５は、自ノード上の複製データ２７に対してデータ参照要求を送信する（ステップ１６０）。データ参照要求に付帯される参照ポリシが「局所」である場合、あるいは複製データ２７の複製レベルが「強整合同期」である場合、あるいは複製データ２７の複製レベルが「強整合通知」で、かつ複製データ２７の持つリビジョン番号とコアリビジョン番号が一致している場合、複製データ２７は自身のローカルデータを参照し（ステップ１６１）、要求元クライアント２５へ参照応答として返送する（ステップ１６２）。このとき複製データ２７の複製レベルが「強整合同期」の場合、あるいは複製データ２７の複製レベルが「強整合通知」で、かつ複製データ２７の持つリビジョン番号とコアリビジョン番号が一致している場合は、参照データが最新であることを意味する「最新」を付加情報として参照応答に含める。複製データ２７の複製レベルが「弱整合同期」の場合、あるいは複製データ２７の複製レベルが「弱整合通知」で、かつ複製データ２７の持つリビジョン番号とコアリビジョン番号が一致している場合は、参照データがおそらく最新であることを意味する「準最新」を付加情報として参照応答に含める。複製データ２７の複製レベルが「強整合通知」か「弱整合通知」の場合で、複製データ２７の持つリビジョン番号とコアリビジョン番号が一致していない場合は、参照データが古いことを意味する「非最新」を付加情報として参照応答に含める。
【００４３】
次に、ノード２０上のクライアント２５は、自ノード上の複製データ２７に対して参照ポリシが「最新」であるデータ参照要求を送信する（ステップ１６３）。複製データ２７の複製レベルが「強整合同期」である場合、あるいは複製データ２７の複製レベルが「強整合通知」で、かつ複製データ２７の持つリビジョン番号とコアリビジョン番号が一致している場合は、上記データ参照要求の場合と同じようににノード２０でローカルに処理が行われる。一方、複製データ２７の複製レベルが「強整合通知」で、かつ複製データ２７の持つリビジョン番号とコアリビジョン番号が一致していない場合、複製データ２７の把握するコアデータ１７に対して、データ参照要求元クライアント２５のオブジェクトＩＤを含めたデータ参照要求を送信し（ステップ１０４）、コアデータ１７はローカルの最新データを参照して要求元クライアント２５に参照応答として返送する（ステップ１６７）。複製データ２７の複製レベルが「弱整合同期」あるいは「弱整合通知」の場合は、複製データ２７のリビジョン参照要求をコアデータ１７に対して送信し（ステップ１６４）、参照応答に含まれるコアデータのリビジョン番号と自身のリビジョン番号を比較する。比較の結果が一致していない場合、コアデータ１７に対してデータ参照要求元クライアント２５のオブジェクトＩＤを含めたデータ参照要求を送信し（ステップ１６６）、コアデータ１７はローカルの最新データを参照して要求元クライアント２５に参照応答として返送する（ステップ１６７）。比較の結果が一致した場合は複製データ２７自身のローカルデータを参照し要求元クライアント２５に参照応答を返送する。なお、参照ポリシが「最新」である参照要求１６３に対する参照応答には常に付加情報「最新」が含まれる。
【００４４】
図７は図１のネットワークにおいてノード２０でデータの最新要求が発生した場合の動作のシーケンスを示している。図７においては、最初の状態ではノード１０、２０、３０、４０上にそれぞれコアデータ１７、複製データ２７、３７、４７が存在しているとし、複製データ２７、３７、４７の複製レベルはそれぞれ「強整合同期」、「強整合通知」、「弱整合同期」であるとする。
【００４５】
まず、ノード２０のクライアント２５が自ノード上の複製データ２７にデータ更新要求を送信する（ステップ１７０）。データ更新要求を受信した複製データ２７は、データ更新要求をコアデータ１７に転送する（ステップ１７２）。データ更新要求を受信したコアデータ１７は、複製レベルが「強整合同期」あるいは「強整合通知」である複製データ２７、３７に対し更新要求を送信する（ステップ１７３、１７４）と同時にタイマを設定する（ステップ１７５）。このとき複製レベルが「強整合同期」である複製データ２７には更新されたデータのリビジョン番号とともにデータの内容を含めて更新要求を送信するが（ステップ１７３）、複製レベルが「強整合通知」である複製データ３７には更新されたデータのリビジョン番号のみを含めて更新要求を送信する（ステップ１７４）。
【００４６】
更新要求を受信した複製データ２７、３７は更新内容を記憶し、コアデータ１７に対して確認応答をそれぞれ返送する（ステップ１７６、１７７）と同時にタイマを設定する（ステップ１８８、１８９）。コアデータ１７がタイマを設定して（ステップ１７５）から一定時間以内に全ての複製データから確認応答を受信できた場合、コアデータ１７は、複製データ２７と３７への更新の同期成功を保証できたこととなり、データ更新要求に含まれるデータを用いてローカルデータの更新を行う（ステップ１７８）。
【００４７】
その後コアデータ１７は複製データ２７と３７に更新の実行依頼、およびデータが有効であることを示す新しい有効期間を含む更新実行を送信する（ステップ１８０、１８１）。同時に複製レベルが「弱整合同期」である複製データ４７に対して、更新内容のデータとリビジョン番号を含んだ更新要求を送信する（ステップ１８２）。複製データ２７、３７が一定時間以内にそれぞれ更新実行（ステップ１８０、１８１）を受信できた場合、更新要求（ステップ１７３、１７４）で通知されたデータにしたがって更新処理を行うとともに、通知された有効期間を記憶する（ステップ１８５、１８６）。更新要求を受信した複製データ４７も、通知されたデータにしたがって更新処理を行う（ステップ１８７）。
【００４８】
もし確認応答ステップ１７６と１７７のどちらかがネットワークの切断など、なんらかの理由により失われた場合、更新操作は失敗する。例えば図８は図７のシーケンスの途中において応答確認（ステップ１７７）が失われた場合について示している。この場合、コアデータ１７は確認応答を受信できなかった複製データ２７、３７のネットワークアドレスを削除したタイマを設定して（ステップ１７５）から一定時間以内に確認応答（ステップ１７６と１７７）を全て受信できなかったので、コアデータ１７は複製データ２７と３７への更新の同期成功を保証できない。このため、コアデータ１７は確認応答を受信できなかった複製データ２７、３７のネットワークアドレスを削除して更新を破棄し（ステップ１９０）、更新の失敗を要求元クライアント２５に更新応答として返送する（ステップ１９１）。その後、複製データ２７へ更新取消を送信する（ステップ１９２）。更新取消を受信した複製データ２７は更新を破棄し、タイマを解除する（ステップ１９４）。
【００４９】
複製データ３７は更新取消を受信しないが、ステップ１８９で設定されたタイマがタイムアウトすると同時に複製データ自体が破棄される（ステップ１９５）。もし更新取消（ステップ１９２）がなんらかの理由で失われた場合、一定期間内に更新の実行を依頼されなかった場合も、タイムアウトにより複製データ２７は破棄される。
【００５０】
このように、本複製データ管理方法では、複製レベルが「強整合同期」あるいは「強整合通知」の有効期限内の複製データに関しては更新メッセージが確実に受信されることを保証することができる。これによって、複製レベルが「強整合同期」あるいは「強整合通知」の有効期限内の複製データに関して厳密なデータの一貫性保証が可能になっている。
【００５１】
図９は図１のネットワークにおいてノード２０上のデータデータ複製２７の期限延長要求があった場合の動作のシーケンスを示している。
【００５２】
ノード２０上の複製データ２７は有効期限が切れる前に複製データの有効期間の延長要求をコアデータ１７に送信し、現在時刻＋規定値で計算される仮の有効期限を一時記憶する（ステップ２４０）と同時にタイマを設定する（ステップ２９１）。延長要求を受信したコアデータ１７は複製データ２７の新たな有効期限（現在時刻＋規定値）を計算し、これをもって管理する複製データ表を更新し（ステップ２９２）、延長応答を送信する（ステップ２９３）。延長要求を送信してから一定時間内に延長応答を受信した複製データ２７は延長応答に含まれる新たな有効期限を自身に設定する（ステップ２９４）。
【００５３】
もし一定時間内に延長応答が受信されなかった場合（ステップ２９８）、複製データ２７はタイムアウトによって複製データ自身を破棄する（ステップ２９９）。これによって、コアデータが把握する複製データの有効期限は、複製データが把握する有効期限より常に長くなることが保証される。
【００５４】
図１０は図１のネットワークにおいてノード２０上のクライアント２５から更新要求があり、コア移動を伴う更新を行う場合の動作シーケンスを示している。
【００５５】
ノード２０上のクライアント２５はデータ更新要求を複製データ２７へ送信する（ステップ３００）。複製データ２７はコアデータ１７へコア移動を送信する（ステップ３０２）。受信したコアデータ１７は複製データに降格し（ステップ３０３）、データ内容及びテーブルの情報を含むコア移動応答を複製データ２７に返送し、これと同期をとった後、移動前に把握していた全ての複製データに対して移動後のアドレスを通知する（ステップ３０５）。コア移動応答を受信した複製データ２７はコアデータへと昇格する（ステップ３０４）。その後は、データ更新要求（ステップ３００）に含まれる更新内容データを用いて、図７で説明したと同様の方法で更新処理を行う（ステップ３０６〜３１８）。
【００５６】
図１１は図１のネットワークにおいてアクセスポイント０１とアクセスポイント０２の間のネットワークが切断し、ノード１０とノード２０からなるネットワークと、ノード３０とノード４０からなるネットワークに分断された状態において、ノード４０上の複製データ４７をコアデータとして再生するときの動作のシーケンスを示している。
【００５７】
ノード４０上のクライアント４５がデータ参照要求を送信する（ステップ３２０）。受信した複製データ４７は、複製レベルと参照ポリシの関係からコアデータへアクセスする必要があったとする。このとき、複製データ４７はコアデータ１７へデータ参照要求を送信し（ステップ３２２）、同時にタイマを設定し（ステップ３２３）、コアデータ１７からの参照応答を待つ。しかし、データ参照要求はネットワーク切断のため失われるため、タイムアウトが起こり（ステップ３２４）、複製データ４７はコアデータ１７とネットワーク接続が失われたことを認識する。
【００５８】
その後、複製データ４７はコア探索をネットワークブロードキャストによって送信し（ステップ３２５）、コアデータを探索する。同時にタイマを設定する（ステップ３２６）。コア探索メッセージを受信したそれぞれの複製データは、自身のリビジョン番号と自身がコアデータであるか否かの情報を含めてコア探索応答を返送する（ステップ３２８）。本実施形態においては複製データ３７のみがコア探索を受信し、リビジョン番号と複製データであるという情報を含めてコア探索応答を返送する（ステップ３２８）。
【００５９】
複製データ４７はタイムアウトまでの一定時間を待機してコア探索応答の受信を待ち、タイムアウト（ステップ３３０）の後、コア探索応答のあった複製データと自分自身の中から、最も新しいリビジョン番号を持つ複製データを選択する。そして、選んだ複製データ（本実施形態では複製データ３７とする）に対してコア生成要求を送信する（ステップ３３２）。コア生成要求を受信した複製データ３７は自身をコアデータへと昇格させ（ステップ３３３）、コア生成応答を返送する（ステップ３３４）。
【００６０】
この時点で複製データ３７はコアデータ３７となり、ノード３０とノード４０によって構成されるネットワーク内における単一のコアデータとなる。コア生成応答（ステップ３３４）を受信した複製データ４７はコアデータが再生されたことを認識し、新しいコアデータ３７に対して改めてデータ参照要求を送信し（ステップ３３５）、データの参照を行う（ステップ３３６）。
【００６１】
図１２は図１のネットワークにおいてアクセスポイント０１とアクセスポイント０２の間のネットワークが切断し、ノード１０とノード２０からなるネットワークと、ノード３０とノード４０からなるネットワークに分断されていて、ノード１０上にコアデータ１７、ノード３０上にコアデータ３７が、ノード２０上に複製データ２７、ノード４０上に複製データ４７がそれぞれ存在している状態において、アクセスポイント０１とアクセスポイント０２の間のネットワーク接続が回復した後に二つのコアデータを一つに統合する動作のシーケンスを示している。
【００６２】
各ノード上のデータマネージャは、直接通信可能な全ての隣接ノード上のデータマネージャに向けて定期的に接続性調査メッセージを送信している（ステップ４４０、４４１、４４５、４４６）。接続性調査メッセージを受信した各データマネージャは接続応答メッセージを返送する（ステップ４４２、４４７、４４８）。このため各データマネージャは定期的に受信する接続応答の送信元のリストを比較して、新たにネットワークに接続した隣接ノードの存在や、ネットワーク接続を失った隣接ノードの存在を検知することができる。
【００６３】
初めの状態ではノード２０とノード３０は通信が不可能であるため、データマネージャ３３の送信する接続性調査メッセージはノード２０上のデータマネージャ２７に到達せず、ノード３０が受信する接続応答はノード４０上のデータマネージャ４３から送信されるものだけとなる。しかしノード２０とノード３０の間のネットワーク接続が回復した後には、新たにノード３０上のデータマネージャ３３からの接続応答（ステップ４４７）を受信する。
【００６４】
ここで、データマネージャ３３は新たにノード２０の接続を検知し（ステップ４５０）、自ノード上のコアデータ（ここではコアデータ３７）に対して新規接続を通知する（ステップ４３１）。
【００６５】
接続通知（ステップ４５１）を受けたコアデータ３７は、該データの識別子を含んだコア存在確認メッセージをネットワークブロードキャストによって全てのノード上のデータマネージャに対して送信する（ステップ４５２―４５４）。コア存在確認を受信したデータマネージャはデータ対応表を参照して、該識別子で識別されるコアデータが自ノード１０上に存在するかどうかを検索し、もし存在した場合はコア存在応答を返送する。本実施形態ではノード１０上のデータマネージャ１３がコア存在応答（ステップ４５５）を返送する。コア存在応答を受信したコアデータ３７は、新しく発見したノード１０上のコアデータ１７に対して、自身のデータ内容を含めてコア統合を送信する（ステップ４５６）。コア統合を受信したコアデータ１７は通知されたデータと自身のデータを比較してＣＶＳなどの既存のアルゴリズムによってコアデータの変更点を組合せることによりデータの統合を試みる（ステップ４５８）。統合が成功した場合はコア統合応答によって成功を返送し（ステップ４５９）、成功の応答を受信したコアデータ３７は自身を複製データに降格する（ステップ４６０）。これによってコアデータ３７は、接続されたネットワーク内において再び一意となり、ネットワーク内の複製データの整合性は保たれる。
【００６６】
統合が失敗した場合は、コア統合応答によって失敗を返送し（ステップ４５９）、失敗の応答を受信したコアデータ３７は、次にデータにアクセスがあったタイミングでユーザに通知し、ユーザの人手によって統合操作を行う。
【００６７】
なお、本発明は専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フロッピーディスク、光磁気ディスクひかりおじきでぃすく、ＣＤ―ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間の間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合はサーバとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含む。
【００６８】
【発明の効果】
以上説明したように、本発明は下記の効果がある。
【００６９】
１）任意のノードに存在し得るデータごとにネットワーク内で単一のコアデータが更新の権利を持つことにより、接続されたネットワーク内でのデータの一貫性を保つことが可能となる。
【００７０】
２）データの更新はコアデータに対して行い、最新のデータ読み出しはコアデータから行うため、データ更新後のデータの不整合は発生しない。本発明はデータ更新後に更新発生ノードでさらにデータ参照要求が発生し易い場合、コアデータを更新発生ノードに移動してから更新を行うようにすることによって、ノード間通信が不要なデータ更新・参照が可能となり効率的である。特に、トポロジが変化し易くその変化が予測不能なネットワークにおいては、マスタとなるデータの位置を自由に変更できることおよびノード間通信なしにデータの参照が可能であることはデータの可用性を高める。
【００７１】
３）また、本発明では、単一のネットワークがいくつかのサブネットワークに分割された場合においても、それぞれの接続されているネットワーク内で複製データ間の一貫性保持が可能であり、また、これらの分割されたネットワークが再び融合する際にもデータの自動的な統合が可能である。このため、ネットワークがどのような状態にあってもデータの更新・参照が可能で、データの可用性が高い。
【００７２】
４）さらに、本発明では複製データはそれぞれのノード上で必要となる同期のレベルを選択できるため、厳密な一貫性制御が必要な複製データ数を小さく抑えることが可能であり、データ更新の同期遅延を抑制することが可能である。ここで、厳密な一貫性保持を要求する複製データに関しては、実施形態でも示したとおり、データ更新に関するメッセージが紛失した場合においてもデータの一貫性を保つことが可能である。
【００７３】
５）したがって、本発明は、トポロジが動的に変化するネットワーク内に分散配置されたデータの複製間の整合を、ノードの要求する同期ポリシにしたがって保持しつつ、データの可用性の低下を抑えたい場合に効果がある。
【図面の簡単な説明】
【図１】本発明が適用されたネットワークの構成図である。
【図２】データマネージャによるデータの実現方法を示す図である。
【図３】データマネージャの動作を示すフローチャートである。
【図４】図１のネットワークにおいてノード１０でデータ生成要求が発生し、その後続けてデータの参照要求と更新要求が発生した場合のデータ生成動作のシーケンス図である。
【図５】図１のネットワークにおいて複製データの存在しないノード２０でデータの参照要求が発生した場合の動作のシーケンス図である。
【図６】図１のネットワークにおいて複製データの存在するノード２０でデータの参照要求が発生した場合の動作のシーケンス図である。
【図７】図１のネットワークにおいてノード２０でデータの参照要求が発生した場合の動作のシーケンス図である。
【図８】図７のシーケンスの途中において応答確認１７７が失われた場合のシーケンス図である。
【図９】図１のネットワークにおいてノード２０上のデータ複製２７の期間延長要求があった場合の動作のシーケンス図である。
【図１０】図１のネットワークにおいてノード２０上のクライアント２５から更新要求があり、コア移動を伴う更新を行う場合の動作のシーケンス図である。
【図１１】図１のネットワークにおいてアクセスポイント０１とアクセスポイント０２間のネットワークが切断し、ノード１０とノード２０からなるネットワークとノード３０とノード４０からなるネットワークに分断された状態において、ノード４０上の複製データ４７をコアデータとして再生するときの動作のシーケンス図である。
【図１２】
図１のネットワークにおいてアクセスポイント０１とアクセスポイント０２の間のネットワークが切断し、ノード１０とノード２０からなるネットワークと、ノード３０とノード４０からなるネットワークに分断されていて、ノード１０上にコアデータ１７、ノード３０上にコアデータ３７が、ノード２９上に複製データ２７、ノード４９上に複製データ４７がそれぞれ存在している状態において、アクセスポイント０１とアクセスポイント０２の間のネットワーク接続が回復した後に二つのコアデータを一つに統合する動作のシーケンス図である。
【符号の説明】
０１、０２    無線アクセスポイント
１０、２０、３０、４０    ノード
１３、２３、３３、４３    データマネージャ
１５、２５、３５、４５    クライアント
１７    コアデータ
２７、３７、４７    複製データ
６０    ノード
６１    データマネージャ
６２    データ対応表
６３    作成済データ表
６４    データオブジェクト
６５    ローカルデータ
１０１〜１２０、１２１〜１３３、１４０〜１５６、１６０〜１６７    ステップ
１７０〜１９５、２９０〜２９９、３００〜３３７、４４０〜４６０    ステップ
【図１】
2004171278.tif 000003
【図２】
2004171278.tif 000004
【図３】
2004171278.tif 000005
【図４】
2004171278.tif 000006
【図５】
2004171278.tif 000007
【図６】
2004171278.tif 000008
【図７】
2004171278.tif 000009
【図８】
2004171278.tif 000010
【図９】
2004171278.tif 000011
【図１０】
2004171278.tif 000012
【図１１】
2004171278.tif 000013
【図１２】
2004171278.tif 000014