(57)【特許請求の範囲】
【請求項１】
通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製方法において、
前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有し、
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬し、
（ｂ）前記フロントエンド・ノードは、
前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、
前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、
この読み出し複製ノードに対して読み出し要求を行い、
前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答し、
前記フロントエンド・ノードは、
前記クライアント・ノードが要求する新しさと等しい時間以内に更新を伝搬することのできる複製ノードの集合を、前記複製ノードの範囲内発信ノード集合と定義し、
この範囲内発信ノード集合が他の複製ノードの範囲内発信ノード集合の部分集合でない複製ノードを既約複製ノードと定義し、
この既約複製ノードのうち、他の既約複製ノードの範囲内発信ノード集合に含まれていない複製ノードを範囲内発信ノード集合に含むものを必須複製ノードと定義し、
木構造の中から、必須複製ノードを、読み出し複製ノードとして選択し、
選択された必須複製ノードの範囲内発信ノード集合に含まれていない複製ノードを削除して最小の部分木を構成し、
同様にして必須複製ノードを算出して読み出し複製ノードに加える操作を繰り返し、
前記部分木のうちの少なくとも一つの複製ノードの範囲内発信ノード集合が、前記部分木の全てのノードを含むまで上述の操作を繰り返すことにより読み出し複製ノードを算出する手段である
ことを特徴とするデータ複製方法。
【請求項２】
請求項１において、
前記フロントエンド・ノードは、
木構造上で隣接する複製ノード間において、それぞれの範囲内発信ノード集合を交換し、自ノードの範囲内発信ノードの集合と隣接ノードから受け取った範囲内発信ノードの集合を用いて、前記既約複製ノードおよび前記必須複製ノードを算出する手段である
ことを特徴とするデータ複製方法。
【請求項３】
通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製方法において、
前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有し、
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬し、
（ｂ）前記フロントエンド・ノードは、
前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、
前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、
この読み出し複製ノードに対して読み出し要求を行い、
前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答し、
前記クライアント・ノードが要求する新しさは、最新度として定義され、
所定の確率ｐで、現在から時間Ｔ前までの更新を反映しているときに、確率ｐの最新度はＴである
と定義されていることを特徴とするデータ複製方法。
【請求項４】
通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製プログラムを記録した記録媒体において、
前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有し、
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬し、
（ｂ）前記フロントエンド・ノードは、
前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、
前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、
この読み出し複製ノードに対して読み出し要求を行い、
前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答し、
前記フロントエンド・ノードは、
前記クライアント・ノードが要求する新しさと等しい時間以内に更新を伝搬することのできる複製ノードの集合を、前記複製ノードの範囲内発信ノード集合と定義し、
この範囲内発信ノード集合が他の複製ノードの範囲内発信ノード集合の部分集合でない複製ノードを既約複製ノードと定義し、
この既約複製ノードのうち、他の既約複製ノードの範囲内発信ノード集合に含まれていない複製ノードを範囲内発信ノード集合に含むものを必須複製ノードと定義し、
木構造の中から、必須複製ノードを、読み出し複製ノードとして選択し、
選択された必須複製ノードの範囲内発信ノード集合に含まれていない複製ノードを削除して最小の部分木を構成し、
同様にして必須複製ノードを算出して読み出し複製ノードに加える操作を繰り返し、
前記部分木のうちの少なくとも一つの複製ノードの範囲内発信ノード集合が、前記部分木の全てのノードを含むまで上述の操作を繰り返すことにより読み出し複製ノードを算出する手段である
ことを特徴とするデータ複製プログラムを記録した記録媒体。
【請求項５】
請求項４において、
前記フロントエンド・ノードは、
木構造上で隣接する複製ノード間において、それぞれの範囲内発信ノード集合を交換し、自ノードの範囲内発信ノードの集合と隣接ノードから受け取った範囲内発信ノードの集合を用いて、前記既約複製ノードおよび前記必須複製ノードを算出する手段である
ことを特徴とするデータ複製プログラムを記録した記録媒体。
【請求項６】
通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製プログラムを記録した記録媒体において、
前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有し、
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬し、
（ｂ）前記フロントエンド・ノードは、
前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、
前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、
この読み出し複製ノードに対して読み出し要求を行い、
前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答し、
前記クライアント・ノードが要求する新しさは、最新度として定義され、
所定の確率ｐで、現在から時間Ｔ前までの更新を反映しているときに、確率ｐの最新度はＴである
と定義されていることを特徴とするデータ複製プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ複製方法およびデータ複製プログラムを記録した記録媒体に関し、特にネットワーク上で使用される判断支援システム、および、判断支援システムと協調して動作するディレクトリ・サービス等に適用されるデータ複製方法およびデータ複製プログラムを記録した記録媒体に関するものである。
【０００２】
【従来の技術】
近年のネットワークの発展に伴う分散環境の拡大およびノード数の増大によって、ディレクトリ・サービス、移動端末情報、ネットワーク管理情報、判断支援システム等のデータ管理が重要となってきている。これらでは、銀行のオンライン処理のように、トランザクションおよびその構成要素であるオペレーションの厳密な一貫性制御の重要性が低い反面、各トランザクションに対する応答時間やスループットの重要性が高くなっている。
【０００３】
このような特性を持つデータでは、（１）トランザクションを発行するアプリケーションが一貫性を維持するために必要な処理順序や依存関係を把握している場合、（２）トランザクションの応答および応答結果を用いたアプリケーションの動作結果によってデータの異常が検知できる場合、（３）ほとんどのトランザクション間に衝突が無く、衝突があった場合でもアンドゥ（ｕｎｄｏ）によって取り消しを行うことが可能である場合が多い。
【０００４】
そこで、このような特性を利用して、文献（Ｊ．Ｇｒａｙ，Ｐ．Ｈｅｌｌａｎｄ，Ｐ．Ｏ’Ｎｅｉｌ，ａｎｄ  Ｄ．Ｓｈａｓｈａ著，“Ｔｈｅ  ｄａｎｇｅｒｓ  ｏｆ  ｒｅｐｌｉｃａｔｉｏｎ  ａｎｄ  ａ  ｓｏｌｕｔｉｏｎ，”Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆＡＣＭ  ＳＩＧ−ＭＯＤ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｄａｔａ，ｐｐ．１７３−１８２）に述べられているレイジー・グループ・レプリケーション（Ｌａｚｙ  ｇｒｏｕｐ  ｒｅｐｌｉｃａｔｉｏｎ）や現在の多くのデータベース・システムに実装されている非同期更新によるデータ・レプリケーション機能によって応答時間やスループットの改善と弱一貫性の制御を行うことが行われている。
【０００５】
レイジー・グループ・レプリケーションや多くの市販データベース・システムに実装されている非同期更新では、ネットワークに接続された複数の計算機で同じデータ・オブジェクトを管理し、更新および読み出し要求を処理することによって応答時間やスループットを改善している。しかし、同じデータ・オブジェクトを管理している計算機の数が増加するにつれて、更新が全てのデータを管理する計算機に反映されるための時間が増大するためにクライアントが取得したデータの新しさが重要となってくる。
【０００６】
例えば、このような技術の応用例としては、ある商品の販売個数を提供し、この情報に基づいて商品の生産個数の決定を支援する判断支援システム等がある。この場合、十分に新しい情報に基づいて生産個数を決めなければ、大量の在庫を抱えることになる。
【０００７】
また、別の応用例としては、計算機ネットワーク上での移動端末の位置情報管理等がある。計算機ネットワーク上で、移動端末に対して通信を行うときには、その移動端末の接続されているネットワーク上での位置を把握する必要がある。この位置情報は、通常分散されて管理されている。すなわち、接続を行った移動端末は、その接続を行った位置の位置管理システムやそれ以外の位置の位置管理システムに自分の位置の登録を行う。このような環境下において、移動端末と通信を行う計算機とが古い位置情報を取得すると、実際の位置との差が大きくなり、現在の位置を正確に把握することが困難となる。したがって、従来より、ある時間内のデータを提供するシステムが求められていた。
【０００８】
以上の観点から、従来においては以下のような技術がある。
（１）レイジー・レプリケーション（ｌａｚｙ  ｒｅｐｌｉｃａｔｉｏｎ）（文献：Ｒ．Ｌａｄｉｎ，“Ｌａｚｙ  ｒｅｐｌｉｃａｔｉｏｎ：Ｅｘｐｌｏｉｔｉｎｇ  ｔｈｅ  ｓｅｍａｎｔｉｃｓ  ｏｆ  ｄｉｓｔｒｉｂｕｔｅｄ  ｓｅｒｖｉｃｅｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｒｅｐｌｉｃａｔｅｄ  Ｄａｔａ，ｐｐ．３１−３４，１９９０、文献：Ｒ．Ｌａｄｉｎ，“Ｐｒｏｖｉｄｉｎｇ  ｈｉｇｈ  ａｖａｉｌａｂｉｌｉｔｙ  ｕｓｉｎｇ  ｌａｚｙ  ｒｅｐｌｉｃａｔｉｏｎ”，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ，Ｖｏｌ．１０，ｐｐ．３６０−３９１，Ｎｏｖｅｍｂｅｒ  １９９２）
【０００９】
このレイジー・レプリケーションは、オペレーションの一貫性として、カジュアル・オペレーション（ｃａｓｕａｌ  ｏｐｅｒａｔｉｏｎ）、フォースト・オペレーション（ｆｏｒｃｅｄ  ｏｐｅｒａｔｉｏｎ）およびイミディエイト・オペレーション（ｉｍｍｅｄｉａｔｅ  ｏｐｅｒａｔｉｏｎ）を提供するデータ複製方式である。更新要求は非同期に複製ノードに伝搬される。
【００１０】
（２）ピービー・キャスト（ｐｂｃａｓｔ）（文献：Ｋ．Ｂｉｒｍａｎ，“ＢＵＩＬＤＩＮＧ  ＳＥＣＵＲＥ  ＡＮＤ  ＲＥＬＩＡＢＬＥ  ＮＥＴＷＯＲＫ  ＡＰＰＬＩＣＡＴＩ０ＮＳ”，ＭＡＮＮＩＮＧ  Ｐｕｂｌｉｓｈｅｒ，１９９６）
【００１１】
このピービー・キャストは、メッセージの伝搬方式であり、更新要求の伝搬に用いた場合の伝搬方法は以下のようになる。まず、更新要求を受け取ったノードは、「ｆｕｎｏｕｔ」と呼ばれる定数で決まる個数だけ、複製ノードをランダムに選択し、更新要求を送信する。すでに同じ更新要求を受信したノードは、他の複製ノードには、更新要求を伝搬しない。
【００１２】
【発明が解決しようとする課題】
しかしながら、従来技術を用いた場合、複製ノードから提供されるデータの新しさは、システム的に決っているため、
・負荷が高くなる等して、システムの状態が変化するとクライアントの要求する新しさのデータを提供することができなくなる、
・新しさの要求がアプリケーションの種類によって異なる場合やアプリケーションのおかれた状態に依存する場合、全ての要求を満たすようにするためには、最も高い新しさの要求に応じたシステム設計をしなければならず、システム全体のコストを高めてしまう、
といった問題が発生する。
【００１３】
本発明は、このような課題を解決するためのものであり、クライアントの要求する新しさのデータを容易に提供することができ、かつ、低コストで実現可能なデータ複製方法およびデータ複製プログラムを記録した記録媒体を提供することを目的とする。
【００１４】
【課題を解決するための手段】
このような目的を達成するために、本発明に係るデータ複製方法は、通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製方法において、前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有す。
【００１５】
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬する。
【００１６】
（ｂ）前記フロントエンド・ノードは、前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、この読み出し複製ノードに対して読み出し要求を行い、前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答するものである。
【００１７】
また、本発明に係るデータ複製方法は、その他の態様として以下に示す構成も含む。
【００１８】
すなわち、前記フロントエンド・ノードは、前記クライアント・ノードが要求する新しさと等しい時間以内に更新を伝搬することのできる複製ノードの集合を、前記複製ノードの範囲内発信ノード集合と定義し、この範囲内発信ノード集合が他の複製ノードの範囲内発信ノード集合の部分集合でない複製ノードを既約複製ノードと定義し、この既約複製ノードのうち、他の既約複製ノードの範囲内発信ノード集合に含まれていない複製ノードを範囲内発信ノード集合に含むものを必須複製ノードと定義し、木構造の中から、必須複製ノードを、読み出し複製ノードとして選択し、選択された必須複製ノードの範囲内発信ノード集合に含まれていない複製ノードを削除して最小の部分木を構成し、同様にして必須複製ノードを算出して読み出し複製ノードに加える操作を繰り返し、前記部分木のうちの少なくとも一つの複製ノードの範囲内発信ノード集合が、前記部分木の全てのノードを含むまで上述の操作を繰り返すことにより読み出し複製ノードを算出する手段であってもよい。
【００１９】
また、前記フロントエンド・ノードは、木構造上で隣接する複製ノード間において、それぞれの範囲内発信ノード集合を交換し、自ノードの範囲内発信ノードの集合と隣接ノードから受け取った範囲内発信ノードの集合を用いて、前記既約複製ノードおよび前記必須複製ノードを算出する手段であってもよい。
【００２０】
さらに、前記クライアント・ノードが要求する新しさは、最新度として定義され、所定の確率ｐで、現在から時間Ｔ前までの更新を反映しているときに、確率ｐの最新度はＴであると定義されていてもよい。
【００２１】
一方、本発明に係るデータ複製プログラムを記録した記録媒体は、通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製プログラムを記録した記録媒体において、前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有す。
【００２２】
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬する。
【００２３】
（ｂ）前記フロントエンド・ノードは、前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、この読み出し複製ノードに対して読み出し要求を行い、前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答するものである。
【００２４】
また、本発明に係るデータ複製プログラムを記録した記録媒体は、その他の態様として以下に示す構成も含む。
【００２５】
すなわち、前記フロントエンド・ノードは、前記クライアント・ノードが要求する新しさと等しい時間以内に更新を伝搬することのできる複製ノードの集合を、前記複製ノードの範囲内発信ノード集合と定義し、この範囲内発信ノード集合が他の複製ノードの範囲内発信ノード集合の部分集合でない複製ノードを既約複製ノードと定義し、この既約複製ノードのうち、他の既約複製ノードの範囲内発信ノード集合に含まれていない複製ノードを範囲内発信ノード集合に含むものを必須複製ノードと定義し、木構造の中から、必須複製ノードを、読み出し複製ノードとして選択し、選択された必須複製ノードの範囲内発信ノード集合に含まれていない複製ノードを削除して最小の部分木を構成し、同様にして必須複製ノードを算出して読み出し複製ノードに加える操作を繰り返し、前記部分木のうちの少なくとも一つの複製ノードの範囲内発信ノード集合が、前記部分木の全てのノードを含むまで上述の操作を繰り返すことにより読み出し複製ノードを算出する手段であってもよい。
【００２６】
また、前記フロントエンド・ノードは、木構造上で隣接する複製ノード間において、それぞれの範囲内発信ノード集合を交換し、自ノードの範囲内発信ノードの集合と隣接ノードから受け取った範囲内発信ノードの集合を用いて、前記既約複製ノードおよび前記必須複製ノードを算出する手段であってもよい。
【００２７】
さらに、前記クライアント・ノードが要求する新しさは、最新度として定義され、所定の確率ｐで、現在から時間Ｔ前までの更新を反映しているときに、確率ｐの最新度はＴであると定義されていてもよい。
【００２８】
【発明の実施の形態】
次に、本発明の一つの実施の形態について図を用いて説明する。
図１は、本発明に係るネットワークおよびネットワークに接続された計算機を示す。同図に示すように、計算機１は、インターフェースを介してネットワーク２に接続され、データの複製等の種々の制御を行う中央処理装置（ＣＰＵ）、データおよび本発明に係る通信制御プログラムおよびアプリケーション・プログラム等を記憶保持するランダム・アクセス・メモリ（ＲＡＭ）およびハードディスク・ドライブ（ＨＤＤ）を有する。データ等は複数の計算機１に分散して記憶保持され、各計算機１には後述の種々のプロセスが働いている。
したがって、本発明はネットワーク・システムとして提供できるとともに、記録媒体に記録した状態で提供することもできる。
【００２９】
図２は、ネットワーク上に分散する複数のプロセスを模式的に示したものである。同図に示すように、各プロセスはその働きに応じて３種類に分類される。データを管理するプロセスである複製ノードと、データの更新およびデータの読み出し要求を行うプロセスであるクライアント・ノードと、クライアント・ノードからの要求を仲介して複数の複製ノードに対して要求（更新要求、読み出し要求等）を出すプロセスであるフロントエンド・ノードとである。各複製ノードは、同一のデータ・オブジェクトを管理している。
【００３０】
（１）クライアントノードは、読み出し要求と更新要求を行う。読み出し要求は、フロントエンド・ノードに対して、読み出しを行いたいデータ・オブジェクトと、必要とするデータの新しさである最新度とを指定することにより行われる。更新要求は、フロントエンド・ノードに対して、更新したいデータ・オブジェクトと更新後の値を指定することにより行われる。
【００３１】
（２）複製ノードは、複数が集まって一つのグループを構成し、ネットワーク上には一以上のグループが存在する。各グループに含まれる複製ノードは、更新経路を示す論理的な木構造によって接続され、データ更新操作と読み出し操作と読み出し複製ノード計算とを行う。データ更新操作は、フロントエンド・ノードまたは他の複製ノードからの更新要求を受信し、自ノードのデータを更新して、隣接する複製ノードのうち、更新要求を送信した複製ノード以外に対して更新要求を伝搬することにより行われる。読み出し操作は、フロントエンド・ノードからの読み出し操作に対して、自ノードが管理するデータやトランザクション・ログと、それらに付与されたタイムスタンプと、をフロントエンド・ノードに返答することにより行われる。
【００３２】
（３）フロントエンド・ノードは、データ更新操作と読み出し操作と読み出し複製ノード計算とを行う。データ更新操作は、クライアント・ノードからの更新要求を、グループ分けした複製ノードの各グループに含まれる１つの複製ノードに対して、更新要求を送信することにより行われる。読み出し操作は、クライアント・ノードからの読み出し要求で指定された最新度を満す読み出しノード集合を選択し、この集合に含まれる各読み出しノードに読み出し要求を送信し、結果として受信したデータやトランザクション・ログとそれらに付与されたタイムスタンプに基づいて、読み出し要求を行った複製ノードのデータに反映されている全ての更新を反映したデータを生成し、クライアント・ノードに返答することにより行われる。読み出し複製ノード計算は、複製ノードと協調して読み出し複製ノードを算出することにより行われる。詳細は後述する。
【００３３】
なお、フロントエンド・ノードの読み出し動作は、アプリケーションによって異なる。例えば、従来例での述べた移動端末の位置情報の場合について説明すると次のようになる。移動端末の位置情報の場合、複数の位置から更新が行われた場合に最も新しい情報が正しい情報となるため、各複製ノードにおける通常の更新では、データに割り当てられた更新時のタイムスタンプを基にして、最も新しいタイムスタンプを持ったデータを現在の値として用いる。フロントエンド・ノードは、各複製ノードにおける更新処理と同じ処理を行う。よって、移動端末の例では、複数の複製ノードからデータと、そのデータに割り当てられたタイムスタンプとを取得して、最も新しいタイムスタンプを持つデータを現在のデータとしてクライアント・ノードに送信する。
【００３４】
ここで読み出し複製ノードの算出方法について述べる。
【００３５】
まず、クライアント・ノードが要求する取得データの新しさの定義として、最新度を定義する。次に、ある複製ノードから他の複製ノードヘの更新遅れを推測する方法について述べる。最後に、推測された更新遅れに基づいてクライアント・ノードの要求する最新度を満たす読み出し複製ノードの算出方法について述べる。
【００３６】
（１）最新度の定義
持願平１１−０４７０７６号「データ複製システムおよびデータ複製プログラムを記録した記録媒体」に定義されている最新度と同様に、取得したデータがどの程度の最近のデータであるかをあらわすパラメータである最新度を、確率ｐで現在から時間Ｔｐ  前までの更新を反映している時、確率ｐの最新度がＴｐ  であると定義する。
【００３７】
（２）更新遅れの推測
ここでは、ある複製ノードから他の複製ノードヘの更新遅れを推定する方法について述べる。文献「統計的方法ＩＩ推測」（渡辺洋、芝祐順著、新曜社発行）に述べられているように、今ｎ個の旧標本の順序統計をＸ（１），Ｘ（２），Ｘ（３），…，Ｘ（ｎ）とする。ｍ個の新標本Ｙ（１），Ｙ（２），Ｙ（３），…，Ｙ（ｍ）をとり、両標本の全てに順序づけを行うと、新標本の取り方として可能な組合わせは、ｎ＋ｍＣｎである。したがって、それぞれの生じる確率は、１／ｎ＋ｍＣｎである。
ある一つの更新の伝搬の遅れについて考えると、ｍ＝１であるため、今、確率ｐでの２つの複製ノード間の遅れｄｐ  は、ｄｐ  ＝Ｘｉ  である。ただし、Ｘｉ＜ｄｐ≦Ｘｉ＋１であり、ｉはｉ／（ｎ＋１）＜ｐ≦（ｉ＋１）／（ｎ＋１）を満たす整数である。
【００３８】
（３）用語の定義
ここでは、後述の「読み出し複製ノードの算出方法」の説明の際に用いられる用語について定義を行う。
【００３９】
「読み出し複製ノード」…フロントエンド・ノードがクライアント・ノードの要求する最新度を満たすようなデータを提供するために、読み出し要求を発行する複製ノードのことである。また、この読み出し複製ノードの集合を読み出し複製ノード集合と呼ぶ。
【００４０】
「範囲内発信ノード」…複製ノードｉから、複製ノードｊに対して、クライアント・ノードが要求する範囲内の最新度で更新が伝搬するとき、ｉをｊの範囲内発信ノードと呼ぶ。また、範囲内発信ノードの集合を範囲内発信ノード集合と呼ぶ。この範囲内発信ノードであるか否かの判断は、上記の更新遅れの推測によって行うものとする。
【００４１】
「既約複製ノード」…各複製ノードｉの範囲内発信ノードの集合をＯｉ  としたとき、任意のｊ（ｉ≠ｊ）について
【００４２】
【数１】
0003545267.tif 000002
【００４３】
であるとき、ｉを既約複製ノードと呼ぶ。
「必須複製ノード」…既約複製ノードの中で、ｒ∈Ｏｉ  であり、かつ、任意のｊ（ｊ≠ｉ）について、
【００４４】
【数２】
0003545267.tif 000003
【００４５】
であるｒが存在するとき、ｉを必須複製ノードと呼ぶ。
【００４６】
【実施例】
［読み出し複製ノードの算出方法の実施例１］
本読み出し複製ノードの算出方法の実施例では、
・各ノードは、識別子を持つ、
・各フロントエンド・ノードは、フラッディング（送信ノード以外の隣接ノードにデータを送出する）等の技術によって、トポロジー情報および各複製ノードの範囲内発信ノード集合の情報を持つ、
・フロントエンド・ノードが、読み出し複製ノード集合を算出する、
ものとする。
【００４７】
本実施例では、最初の木構造Ｔから、ノードおよび枝を削除しながら、木構造を再構築していき、読み出し複製ノードを算出していく。このとき、再構築された木構造をＴＳ  とし、初期値はＴＳ  ＝Ｔである。また、本実施例では、以下の１．〜４．の手続きをＴＳ  内のノードのうち、ＴＳ  に含まれる全てのノードを範囲内発信ノード集合とするものが存在しない間繰り返し、最後に５．の手続きを実行する。
【００４８】
１．ＴＳ  について既約複製ノード集合を算出する。
２．既約複製ノードの中から同一の範囲内発信ノード集合を持つものがあれば、一つを残して他を削除する。
３．必須複製ノードを算出する。
４．必須複製ノードの範囲内発信ノードではない複製ノードで構成される最小の木ＴＳ  を構成する。
５．ＴＳ  内のノードのうち、ＴＳ  に含まれる全てのノードを範囲内発信ノード集合とするものを読み出し複製ノードに加える。
【００４９】
図３に、本実施例のアルゴリズムを示す。同図において、各変数は以下の通りである。
【００５０】
Ａ：全複製ノードの集合である。
Ｒ：読み出し複製ノード集合である。初期値はＲ＝｛φ｝であり、φは空集合を意味する。
Ｖ：Ｒに含まれる読み出し複製ノードの範囲内発信ノードの集合である。初期値はＶ＝｛φ｝である。
【００５１】
Ｓ：木構造ＴＳ  に含まれる複製ノードの集合である。初期値はＳ＝Ａである。
Ｃ：ＴＳ  に含まれる既約複製ノードの集合である。
Ｍ：必須複製ノードの集合である。
Ｏｉ  ：複製ノードｉの範囲内発信ノード集合である。
また、関数ｃｏｎｓｔｒｕｃｔＭｉｎｉｍｕｍＴｒｅｅ（ｎｏｄｅｓ）は、ノード集合ｎｏｄｅｓを含む最小の部分木を作成する関数である。
【００５２】
アルゴリズムの詳細について説明する。
【００５３】
まず、同図に示すように、全複製ノード集合Ａ，読み出し複製ノード集合Ｒ，集合Ｒに含まれる読み出し複製ノードの範囲内発信ノード集合Ｖ，木構造ＴＳ  に含まれる複製ノード集合Ｓを設定する。
次いで、（１）に示すように、集合Ａから集合Ｖを除いた集合（以下、集合Ａ＼Ｖという）内における全ての複製ノードｉについて、（２）〜（９）に示す演算を繰り返す。ここで、複製ノードｉの範囲内発信ノード集合Ｏｉ  は、集合Ａ＼Ｖと等しくない。
【００５４】
（２）集合Ｓ中の全ての複製ノードｉについて、範囲内発信ノード集合Ｏｉ  に集合Ｏｉ  ＼Ｖを代入する。
（３）既約複製ノード集合Ｃに、複製ノードｉからなる集合を代入する。ここで、複製ノードｉは集合Ｓの要素であり、かつ、集合Ｓに含まれる全ての複製ノードｊに関して範囲内発信ノード集合Ｏｊ  は範囲内発信ノード集合Ｏｉ  を部分集合として持たない。
【００５５】
（４）集合Ｃの要素である全ての複製ノードｉ，ｊ（ただし、ｉ≠ｊ）について、範囲内発信ノード集合Ｏｉ＝Ｏｊであれば、既約複製ノード集合Ｃに集合Ｃ＼｛ｊ｝を代入する。
（５）集合Ｍに、複製ノードｉからなる集合を代入する。ここで、集合Ａ＼Ｖに存在する複製ノードｊと、集合Ｃに含まれる全ての複製ノードｋ（ただし、ｋ≠ｉ）とに関して、複製ノードｊが範囲内発信ノード集合Ｏｉ  に含まれかつ範囲内発信ノード集合Ｏｋ  に含まれないという条件を満たす。
【００５６】
（６）読み出し複製ノード集合Ｒに、読み出し複製ノード集合Ｒと必須複製ノード集合Ｍとの和集合を代入する。
（７）集合Ｖに、集合Ｖと複製ノードｉからなる集合との和集合を代入する。ここで、複製ノードｉは範囲内発信ノード集合Ｏｊ  の要素であり、かつ、複製ノードｊは必須複製ノード集合Ｍの要素である。
【００５７】
（８）集合ＴＳ  に、集合Ａ＼Ｖに関数ｃｏｎｓｔｒｕｃｔＭｉｎｉｍｕｍＴｒｅｅを施した結果を代入する。
（９）集合Ｓに、集合ＴＳ  中の複製ノードの集合を代入する。
【００５８】
以上のように（１）〜（９）の演算を繰り返した後、（１０）に示す演算を行う。
（１０）読み出し複製ノード集合Ｒに、読み出し複製ノード集合Ｒと複製ノードｉの集合との和集合を代入する。ここで、範囲内発信ノード集合Ｏｉ  は集合Ａ＼Ｖに等しい。
【００５９】
次に、実施例１に係るアルゴリズムを用いた具体例について説明する。
図４（ａ）は、この例で用いられる更新伝搬のための木構造Ｔ０  を示す。また、クライアントが要求する最新度を確率ｐでＴｐとし、各リンクにおける遅延時間は等しく、１リンクの遅延はクライアントの要求を満たすが、２リンク以上の遅延はクライアントの要求を満たさないものとする。最初の繰り返しでは、黒色および梨地の丸印のノードが既約複製ノードとなる。すなわち、ノード２，３，４，５，６，７，１０，１２，１３，１４，１６，１７，２０，２１および２２は既約複製ノードである。
【００６０】
このうち、黒色の丸印は必須複製ノードである。すなわち、ノード２，７，１０，１４，１７および２２は必須複製ノードである。ノード２はノード１を唯一含むため必須複製ノードである。同様にノード７はノード８および９を唯一含み、ノード１０はノード１１を唯一含み、ノード１４はノード１５を唯一含み、ノード１７はノード１８および１９を含み、ノード２２はノード２３および２４を唯一含むため、何れも必須複製ノードである。また、同図中のＲＯｎ  は、複製ノードｎの範囲内発信ノード集合である。
【００６１】
次に、本アルゴリズムは、必須複製ノードに含まれていないノードで構成される最小の部分木を構成する。この段階において、必須複製ノードに含まれていないノードは、４，５，１２および２０である。よって、最小の部分木は図４（ｂ）に示されるように、ノード４，５，１２，１３および２０で構成される部分木となる。
【００６２】
ここでさらに、部分木を用いて同様の操作で既約複製ノードを算出すると、ノード４，１２および１３となる。このうちノード４はノード５を唯一含み、ノード１３はノード２０を唯一含むため、ノード４および１３が必須複製ノードとなる。この段階で全てのノードが必須複製ノードによってカバーされたことになり、本アルゴリズムは必須複製ノードであるノード２，４，７，１０，１３，１４，１７および２２を、クライアントの要求する最新度を満たすための読み出し複製ノード集合として、アルゴリズムは終了する。
【００６３】
［読み出し複製ノードの算出方法の実施例２］
本実施例においても、各複製ノードは識別子をもち、各ノードがＴＳ  に含まれるか否かを示すフラグ変数としてｉｎ＿ｔｒｅｅ＿ｆｌａｇを管理し、以下の操作を繰り返す。ｉｎ＿ｔｒｅｅ＿ｆｌａｇの初期値は、ｉｎ＿ｔｒｅｅ＿ｆｌａｇ＝ＯＮである。
【００６４】
１．ツリー上の各ノードは、自ノードの識別子をフラッディングによって、ほかの全てのノードに通知する。
２．ツリー上のノードヘの経路のなかに、２つ以上の隣接ノードが含まれているときには、ｉｎ＿ｔｒｅｅ＿ｆｌａｇ＝ＯＮとする。
３．自ノードｉの範囲内発信ノード集合Ｏｉ  が、ツリー上の全てのノードを含んでいる時、フラッディングによって全てのツリー上のノードに計算終了を通知する。
４．自ノードｉのＯｉ  を自ノード識別子とともに隣接複製ノードに送信する。
５．既約複製ノードの判別
・全ての隣接複製ノードｊについて
【００６５】
【数３】
0003545267.tif 000004
【００６６】
ならば、既約複製ノードである。
・受信したＯｊ  にＯｉ⊂Ｏｊを満たすものが一つでも存在すれば、既約複製ノードではない。
・いくつかについてＯｉ＝Ｏｊ、それ以外は
【００６７】
【数４】
0003545267.tif 000005
【００６８】
ならば、判断待ち状態となる。
６．自ノードが既約複製ノードか否かの判断がつき、かつ、隣接ノードｊにＯｉ＝Ｏｊなるものが存在すれば、複製ノードは、同じＯｉ  を持つ隣接複製ノードに判断結果を送信する。
７．複数の既約複製ノードの範囲内発信ノード集合が同一であるとき、最も大きな識別子を持つ複製ノードが代表で既約複製ノードとなる。
【００６９】
８．必須複製ノードの判別
・既約複製ノードでない複製ノードは、既約複製ノードからのメッセージを伝達することによって、既約複製ノードでない複製ノードを縮退させた木構造上での隣接する既約複製ノード間で範囲内発信ノード集合を交換する。
・複製ノードｉが、既約複製ノードであり、全ての隣接ノードのＯｊ  の和集合に含まれない要素をＯｉ  がもっているとき、複製ノードｉは、必須複製ノードである。必須複製ノードは、識別子を全てのフロントエンドノードに通知する。
【００７０】
９．必須複製ノードは、Ｏｉ  をフラッディングする。それ以外は、空集合をフラッディングする。受信した範囲内発信ノード集合に含まれているノードは、ｉｎ＿ｔｒｅｅ＿ｆｌａｇ＝ＯＦＦとする。含まれていないノードは、ｉｎ＿ｔｒｅｅ＿ｆｌａｇ＝ＯＮとする。
【００７１】
【発明の効果】
以上説明したように本発明は、通信ネットワークに計算機が複数接続されており、計算機上には、データを管理するプロセスが一つまたは複数動作しており、前記プロセスの管理するデータは全て同一であり、全てのデータを管理するプロセスがマスタ、すなわち管理するデータの更新を受付け、自プロセスのデータを変更して、他のプロセスに更新を伝搬していくプロセスであり、各プロセスが管理するデータの更新は、非同期に行われることによって、前記データがしだいに複製ノードに更新されていくデータ複製方法において、前記データを管理する複数の複製ノードと、前記データの更新と読み出しとを要求するクライアント・ノードと、このクライアント・ノードからの要求を仲介し前記複製ノードに対して要求を行うフロントエンド・ノードとを有し、複製ノードおよびフロントエンド・ノードが以下のような構成をしている。
【００７２】
（ａ）前記複数の複製ノードは、一つまたは複数のグループに分割され、前記各グループに含まれる複製ノードは、更新経路を表す論理的な木構造で接続されており、ある複製ノードに更新要求が伝搬されたとき、この複製ノードは、前記木構造上で隣接する複製ノードのうち、前記更新要求を伝搬してきたノード以外の全てのノードに対して更新要求を伝搬する。
【００７３】
（ｂ）前記フロントエンド・ノードは、前記クライアント・ノードからの更新要求に対して、前記複製ノードの各グループにおける一つの複製ノードに更新要求を行うとともに、前記クライアント・ノードからの読み出し要求に対して、前記クライアント・ノードが要求する新しさのデータを取得するために必要な複製ノード（以下、読み出し複製ノードという）を一つまたは複数選択し、この読み出し複製ノードに対して読み出し要求を行い、前記読み出し複製ノードから読み出したデータ、または、前記読み出し複製ノードにおけるトランザクション・ログに基づいて、前記各複製ノードが更新を処理する方法と同じ方法により、全ての読み出し複製ノードに施されている更新内容を反映したデータを生成し、このデータを前記クライアント・ノードに応答する。
【００７４】
したがって、本発明は、負荷が高くなる等して、システムの状態が変化しても、クライアントの要求する新しさのデータを提供することができる。また、新しさの要求がアプリケーションの種類によって異なる場合やアプリケーションのおかれた状態に依存する場合においても、低コストでシステムを構成することができる。
【図面の簡単な説明】
【図１】本発明に係るネットワークおよび計算機を示す構成図である。
【図２】更新要求および読み出し要求を受けた際の各ノードの関係を示す説明図である
【図３】実施例１のアルゴリズムを示す説明図である。
【図４】実施例１のアルゴリズムを用いた場合の具体例を示す説明図である。
【符号の説明】
１…計算機、２…ネットワーク、３…更新開始ノード、４…読み出し複製ノード。
【図１】
0003545267.tif 000006
【図２】
0003545267.tif 000007
【図３】
0003545267.tif 000008
【図４】
0003545267.tif 000009