(57)【特許請求の範囲】
【請求項１】
複数のサーバがデータを分散して管理する分散データ管理システムであって、
前記サーバは、
データと当該データの識別子とが関連付けて記憶される第一の記憶部と、
前記複数のサーバの識別子及びアドレスとが関連付けられたアドレス表が記憶される第二の記憶部と、
前記複数のサーバの増減時に、前記アドレス表を新たに生成して当該アドレス表の生成時刻とともに前記第二の記憶部に記憶させるアドレス表生成部と、
クライアントから送信された、データの識別子と当該データの生成時刻とを含み、前記データの送信又は保管を要求する要求信号を取得する要求信号取得部と、
取得された前記要求信号に含まれる前記データの識別子と、前記第二の記憶部に記憶された最新の前記アドレス表の前記複数のサーバの識別子と、に基づいて、前記データの担当サーバを特定する担当サーバ特定部と、
前記第二の記憶部に記憶された最新の前記アドレス表のアドレスを用いて、特定された前記担当サーバに前記要求信号を転送する要求信号転送部と、
前記データの送信を要求する前記要求信号に含まれる前記データの識別子に基づいて第一の記憶部を参照し、対応する前記データを読み出して前記クライアントへ送信する、又は、前記データの保管を要求する前記要求信号に含まれる前記データの識別子に基づいて前記第一の記憶部を参照し、対応する前記データの保管の成否を判定して判定結果を示す保管成否信号を前記クライアントへ送信する応答部と、
前記要求信号に含まれる前記データの識別子に対応するデータが前記第一の記憶部に記憶されていない場合に、前記第二の記憶部に記憶されたアドレス表のうち、当該アドレス表の生成時刻が前記要求信号に含まれる前記データの生成時刻よりも古くかつ最新のアドレス表を用いて、前記データの前の担当サーバを特定する前担当サーバ特定部と、
特定された前記前の担当サーバとの間で前記データ及び当該データの識別子の転送を行うデータ転送部と、
転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させるデータ更新部と、
を備えることを特徴とする分散データ管理システム。
【請求項２】
前記第一の記憶部には、前記データ及び当該データの識別子と当該データの生成時刻とが関連付けて記憶されており、
前記データ更新部は、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させる際に、転送された前記データ及び当該データの識別子を当該データ更新部が取得した時刻、又は、転送された前記データ及び当該データの識別子を当該データ更新部が前記第一の記憶部に記憶させた時刻を当該データの生成時刻として前記第一の記憶部に記憶させ、
前記応答部は、前記データ又は前記保管成否信号に前記データの生成時刻を付与して前記クライアントへ送信する
ことを特徴とする請求項１に記載の分散データ管理システム。
【請求項３】
複数のサーバがデータを分散して管理する分散データ管理方法であって、
前記サーバは、データと当該データの識別子とが関連付けて記憶される第一の記憶部と、前記複数のサーバの識別子及びアドレスとが関連付けられたアドレス表が記憶される第二の記憶部と、を備え、前記複数のサーバの増減時に、前記アドレス表を新たに生成して当該アドレス表の生成時刻とともに前記第二の記憶部に記憶させており、
一の前記サーバが、クライアントから送信された、データの識別子と当該データの生成時刻とを含み、前記データの送信又は保管を要求する要求信号を取得するステップと、
一の前記サーバが、取得された前記要求信号に含まれる前記データの識別子と、前記第二の記憶部に記憶された最新の前記アドレス表の前記複数のサーバの識別子と、に基づいて、前記データの担当サーバを特定するステップと、
一の前記サーバが、前記第二の記憶部に記憶された最新の前記アドレス表のアドレスを用いて、特定された前記担当サーバに前記要求信号を転送するステップと、
前記担当サーバが、前記データの送信を要求する前記要求信号に含まれる前記データの識別子に基づいて第一の記憶部を参照し、対応する前記データを読み出して前記クライアントへ送信する、又は、前記データの保管を要求する前記要求信号に含まれる前記データの識別子に基づいて前記第一の記憶部を参照し、対応する前記データの保管の成否を判定して判定結果を示す保管成否信号を前記クライアントへ送信するステップと、
を含むとともに、
前記要求信号に含まれる前記データの識別子に対応するデータが前記第一の記憶部に記憶されていない場合に、前記担当サーバが、前記第二の記憶部に記憶されたアドレス表のうち、当該アドレス表の生成時刻が前記要求信号に含まれる前記データの生成時刻よりも古くかつ最新のアドレス表を用いて、前記データの前の担当サーバを特定するステップと、
前記担当サーバが、前記前の担当サーバとの間で前記データ及び当該データの識別子の転送を行うステップと、
前記担当サーバが、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させるステップと、
を含むことを特徴とする分散データ管理方法。
【請求項４】
前記第一の記憶部には、前記データ及び当該データの識別子と当該データの生成時刻とが関連付けて記憶されており、
前記担当サーバは、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させる際に、転送された前記データ及び当該データの識別子を当該担当サーバが取得した時刻、又は、転送された前記データ及び当該データの識別子を当該担当サーバが前記第一の記憶部に記憶させた時刻を当該データの生成時刻として前記第一の記憶部に記憶させ、
前記担当サーバは、前記データ又は前記保管成否信号に前記データの生成時刻を付与して前記クライアントへ送信する
ことを特徴とする請求項３に記載の分散データ管理方法。
【請求項５】
複数のコンピュータがデータを分散して管理するときに用いられる分散データ管理プログラムであって、
データと当該データの識別子とが関連付けて記憶される第一の記憶部と、前記複数のサーバの識別子及びアドレスとが関連付けられたアドレス表が記憶される第二の記憶部と、を備えるコンピュータを、
前記複数のサーバの増減時に、前記アドレス表を新たに生成して当該アドレス表の生成時刻とともに前記第二の記憶部に記憶させるアドレス表生成部、
クライアントから送信された、データの識別子と当該データの生成時刻とを含み、前記データの送信又は保管を要求する要求信号を取得する要求信号取得部、
取得された前記要求信号に含まれる前記データの識別子と、前記第二の記憶部に記憶された最新の前記アドレス表の前記複数のサーバの識別子と、に基づいて、前記データの担当サーバを特定する担当サーバ特定部、
前記第二の記憶部に記憶された最新の前記アドレス表のアドレスを用いて、特定された前記担当サーバに前記要求信号を転送する要求信号転送部、
前記データの送信を要求する前記要求信号に含まれる前記データの識別子に基づいて第一の記憶部を参照し、対応する前記データを読み出して前記クライアントへ送信する、又は、前記データの保管を要求する前記要求信号に含まれる前記データの識別子に基づいて前記第一の記憶部を参照し、対応する前記データの保管の成否を判定して判定結果を示す保管成否信号を前記クライアントへ送信する応答部、
前記要求信号に含まれる前記データの識別子に対応するデータが前記第一の記憶部に記憶されていない場合に、前記第二の記憶部に記憶されたアドレス表のうち、当該アドレス表の生成時刻が前記要求信号に含まれる前記データの生成時刻よりも古くかつ最新のアドレス表を用いて、前記データの前の担当サーバを特定する前担当サーバ特定部、
特定された前記前の担当サーバとの間で前記データ及び当該データの識別子の転送を行うデータ転送部、及び、
転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させるデータ更新部、
として機能させるための分散データ管理プログラム。
【請求項６】
前記第一の記憶部には、前記データ及び当該データの識別子と当該データの生成時刻とが関連付けて記憶されており、
前記データ更新部は、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させる際に、転送された前記データ及び当該データの識別子を当該データ更新部が取得した時刻、又は、転送された前記データ及び当該データの識別子を当該データ更新部が前記第一の記憶部に記憶させた時刻を当該データの生成時刻として前記第一の記憶部に記憶させ、
前記応答部は、前記データ又は前記保管成否信号に前記データの生成時刻を付与して前記クライアントへ送信する
ことを特徴とする請求項５に記載の分散データ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを複数のサーバに分散して管理する分散データ管理システム、分散データ管理方法及び分散データ管理プログラムに関する。
【背景技術】
【０００２】
データベースのように大規模なデータ管理を行う際に、複数のサーバを接続して高い処理性能を獲得するために、分散データ管理システムが用いられる。分散データ管理システムは、複数のサーバが協調して動作する分散システムであり、当該システム全体で管理されるデータを、個々のサーバが分担して管理するものである。かかる分散データ管理システムは、医療、通信等といった高いリアルタイム性が求められる分野において用いられており、分散データ管理システムを利用するクライアントからのデータ取得要求に対し、当該クライアントのアプリケーションごとに定められた一定時間内にデータを返信することが望まれる。
【０００３】
データを複数のサーバに分散して管理する手法として、コンシステント・ハッシングが挙げられる（非特許文献１参照）。図７に示すように、コンシステント・ハッシングは、分散データ管理プログラムを実装するサーバである複数のノード１３０（１３０Ａ〜１３０Ｆ）と、ノード１３０によって管理されるデータのそれぞれに識別子を割り当て、あるノード１３０が管理するデータの識別子の範囲を、当該ノード１３０の識別子と、当該ノード１３０よりも値の小さい識別子を持つノード１３０の中では最も大きい値の識別子を持つノード１３０の識別子との間に定める技術である。なお、図７のように、ノード１３０及びデータを識別子の値の順に並べたものは、コンシステント・ハッシングにおいてＩＤ空間と呼ばれる。ここで、ノード１３０及びデータの識別子は、ハッシュ関数等の無作為な値を算出する手法によって決定されるので、個々のノード１３０が担当するデータの量は、確率的に等しくなり、分散データ管理システムにおいて、各ノード１３０に対して平等に近い負荷分散を行うことが可能になる。
【０００４】
各ノード１３０は、他の全てのノード１３０の識別子と当該ノード１３０のアドレス（ＩＰアドレス等）が関連付けられたアドレス表を保持する。コンシステント・ハッシングを用いた分散データ管理システムでは、当該システムを構成するノード１３０の数が増減した場合であっても、複数のノード１３０間で分担していたデータの担当替えがごく一部で済み、分散データ管理システム全体から見ればノード１３０の数によらず一定のデータ移動しか発生しない。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web,” in Proceedings of the 29th ACM Symposium on Theory of Computing (STOC'97), pp.654-663, May 1997.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ここで、非特許文献１には、ノード１３０の数を動的に変更した際のデータ移管の具体的手法については、開示されていない。データの移管に関する最も単純な手法としては、ノード１３０の数の変更時に、全てのデータ送信（データを必要とするクライアントへの送信）・保管（データを担当するノード１３０での保管）要求の処理を停止し、データを前の担当ノード１３０から新たな担当ノード１３０へと全て移管し、その後でデータ送信・保管要求の処理を再開するという手法が考えられる。
【０００７】
しかし、医療、通信等といった高リアルタイム性を必要とする分野においては、このようにデータ送信・保管要求を停止して全てのデータを移管するという手法は、データの移管にかかる時間が長くなり、データ送信・保管要求の処理の再開が遅れてしまうため、適用が困難である。
【０００８】
そこで、新たなノード１３０上で実際にデータが必要になった際に、前の担当ノード１３０からこのデータを新たなノード１３０へ移管し処理を行う手法が考えられる。かかる手法では、予め全てのデータを移管する手法と比べて、データの移管が散発的に発生するため、データ送信・保管要求を受け付けながらデータの移管を行うことができ、リアルタイム性への影響が少ない。一方で、データの移管が完了するまでの時間は長くなり、全てのデータに対してデータ送信・保管要求等の「実際にデータが必要になる」契機が発生するまで、データの移管は完了しない。
【０００９】
このようなデータ移管の手法においては、分散データ管理システムに新たに追加されたノード１３０にデータ送信・保管要求が届き、ノード１３０上に処理対象のデータがないことを確認したことを契機に、どのノード１３０が前の担当ノード１３０であるかの探索を行うことが考えられる。
【００１０】
一般的には、図８（ａ）に示すように、前の担当ノード１３０Ａは、新規に追加されたノード１３０Ｇよりも大きい識別子で、かつ最も識別子の値の近いノード１３０である可能性が高いため、新たな担当ノード１３０Ｇは、ノード１３０Ａへデータの有無の問い合わせを行うことが考えられる。このように、ＩＤ空間において隣接するノード１３０からのデータ移管は、一度に追加されるノード１３０の数が小さい（例えば、１つのみ）場合には成立する。
【００１１】
一方、一度に追加されるノード１３０の数が多い場合には、図８（ｂ）に示すように、新たな担当ノード１３０Ｇと前の担当ノード１３０Ａとの間に、1つ以上の他の新規ノード１３０（１３０Ｈ，１３０Ｉ，１３０Ｊ）が存在する可能性がある。このような場合、単純にデータ送信・保管要求を受けた新たな担当ノード１３０Ｇが、隣接するノード１３０Ｈにデータの問い合わせを行っても、問い合わせ先のノード１３０Ｈも追加されたばかりで何のデータも持たないため、新たな担当ノード１３０Ｇは、所望のデータを取得することができない。
【００１２】
ここで、隣接するノード１３０へ問い合わせた結果、所望のデータを取得できない場合、順繰りに更に隣のノード１３０（１３０Ｉ，１３０Ｊ，…）へと問い合わせを行う手法が考えられる。かかる手法では、新たな担当ノード１３０Ｇと前の担当ノード１３０Ａとの間に隣接して追加されたノード１３０の台数Ｎに比例して、実際のデータが発見されるまでに複数ホップ（Ｎホップ）がかかるため、Ｎの値に比例してリアルタイム性が損なわれる。
【００１３】
前記したように、ノード１３０の識別子はハッシュ関数等により無作為に与えられるため、Ｎの値は一定ではないが、追加前の全てのノード１３０の数に対する追加されたノード１３０の数の比に比例して大きくなる。
【００１４】
リアルタイム性を損ねない手法としては、データ送信・保管要求を受けた新たな担当ノード１３０Ｇが所望のデータを持たない場合に、他の全てのノード１３０へと問い合わせを行うものがある。かかる手法では、データの探索に複数ホップを要しないものの、システム全体への問い合わせを行うため、全ノード１３０の数に比例して処理負荷が増大し、スケーラビリティを著しく損ねる。
【００１５】
本発明は、前記した事情に鑑みて創作されたものであり、複数のサーバが追加された場合であっても、リアルタイムに、かつスケーラビリティを損なわずにデータを移管することが可能な分散データ管理システム、分散データ管理方法及び分散データ管理プログラムを提供することを課題とする。
【課題を解決するための手段】
【００１６】
前記課題を解決するため、本発明の分散データ管理システムは、複数のサーバがデータを分散して管理する分散データ管理システムであって、前記サーバは、データと当該データの識別子とが関連付けて記憶される第一の記憶部と、前記複数のサーバの識別子及びアドレスとが関連付けられたアドレス表が記憶される第二の記憶部と、前記複数のサーバの増減時に、前記アドレス表を新たに生成して当該アドレス表の生成時刻とともに前記第二の記憶部に記憶させるアドレス表生成部と、クライアントから送信された、データの識別子と当該データの生成時刻とを含み、前記データの送信又は保管を要求する要求信号を取得する要求信号取得部と、取得された前記要求信号に含まれる前記データの識別子と、前記第二の記憶部に記憶された最新の前記アドレス表の前記複数のサーバの識別子と、に基づいて、前記データの担当サーバを特定する担当サーバ特定部と、前記第二の記憶部に記憶された最新の前記アドレス表のアドレスを用いて、特定された前記担当サーバに前記要求信号を転送する要求信号転送部と、前記データの送信を要求する前記要求信号に含まれる前記データの識別子に基づいて第一の記憶部を参照し、対応する前記データを読み出して前記クライアントへ送信する、又は、前記データの保管を要求する前記要求信号に含まれる前記データの識別子に基づいて前記第一の記憶部を参照し、対応する前記データの保管の成否を判定して判定結果を示す保管成否信号を前記クライアントへ送信する応答部と、前記要求信号に含まれる前記データの識別子に対応するデータが前記第一の記憶部に記憶されていない場合に、前記第二の記憶部に記憶されたアドレス表のうち、当該アドレス表の生成時刻が前記要求信号に含まれる前記データの生成時刻よりも古くかつ最新のアドレス表を用いて、前記データの前の担当サーバを特定する前担当サーバ特定部と、特定された前記前の担当サーバとの間で前記データ及び当該データの識別子の転送を行うデータ転送部と、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させるデータ更新部と、を備えることを特徴とする。
【００１７】
かかる構成によると、サーバの増減ごとにアドレス表生成時刻を有するアドレス表を生成して第二の記憶部に記憶させ、担当サーバの第一の記憶部のデータ表に所望のデータが記憶されていない場合には、データ生成時刻とアドレス表生成時刻とに基づいて選択した過去のアドレス表に基づいて前の担当サーバを特定し、特定された前の担当サーバから担当サーバへデータを移管するので、複数のサーバが追加された場合であっても、リアルタイムに、かつスケーラビリティを損なわずにデータを移管することができる。
【００１８】
前記した分散データ管理システムにおいて、前記第一の記憶部には、前記データ及び当該データの識別子と当該データの生成時刻とが関連付けて記憶されており、前記データ更新部は、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させる際に、転送された前記データ及び当該データの識別子を当該データ更新部が取得した時刻、又は、転送された前記データ及び当該データの識別子を当該データ更新部が前記第一の記憶部に記憶させた時刻を当該データの生成時刻として前記第一の記憶部に記憶させ、前記応答部は、前記データ又は前記保管成否信号に前記データの生成時刻を付与して前記クライアントへ送信することが望ましい。
【００１９】
かかる構成によると、前の担当サーバから担当サーバへデータを移管した際に、担当サーバがデータを取得した時刻又は担当サーバの第一の記憶部のデータ表にデータを記憶させた時刻をデータ生成時刻として第一の記憶部に記憶させるとともにクライアントへ送信するので、データ移管後において、クライアントに新たなデータ生成時刻に基づいて要求信号を生成させることができる。
【００２０】
また、本発明の分散データ管理方法は、複数のサーバがデータを分散して管理する分散データ管理方法であって、前記サーバは、データと当該データの識別子とが関連付けて記憶される第一の記憶部と、前記複数のサーバの識別子及びアドレスとが関連付けられたアドレス表が記憶される第二の記憶部と、を備え、前記複数のサーバの増減時に、前記アドレス表を新たに生成して当該アドレス表の生成時刻とともに前記第二の記憶部に記憶させており、一の前記サーバが、クライアントから送信された、データの識別子と当該データの生成時刻とを含み、前記データの送信又は保管を要求する要求信号を取得するステップと、一の前記サーバが、取得された前記要求信号に含まれる前記データの識別子と、前記第二の記憶部に記憶された最新の前記アドレス表の前記複数のサーバの識別子と、に基づいて、前記データの担当サーバを特定するステップと、一の前記サーバが、前記第二の記憶部に記憶された最新の前記アドレス表のアドレスを用いて、特定された前記担当サーバに前記要求信号を転送するステップと、前記担当サーバが、前記データの送信を要求する前記要求信号に含まれる前記データの識別子に基づいて第一の記憶部を参照し、対応する前記データを読み出して前記クライアントへ送信する、又は、前記データの保管を要求する前記要求信号に含まれる前記データの識別子に基づいて前記第一の記憶部を参照し、対応する前記データの保管の成否を判定して判定結果を示す保管成否信号を前記クライアントへ送信するステップと、を含むとともに、前記要求信号に含まれる前記データの識別子に対応するデータが前記第一の記憶部に記憶されていない場合に、前記担当サーバが、前記第二の記憶部に記憶されたアドレス表のうち、当該アドレス表の生成時刻が前記要求信号に含まれる前記データの生成時刻よりも古くかつ最新のアドレス表を用いて、前記データの前の担当サーバを特定するステップと、前記担当サーバが、前記前の担当サーバとの間で前記データ及び当該データの識別子の転送を行うステップと、前記担当サーバが、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させるステップと、を含むことを特徴とする。
【００２１】
前記した分散データ管理方法において、前記第一の記憶部には、前記データ及び当該データの識別子と当該データの生成時刻とが関連付けて記憶されており、前記担当サーバは、転送された前記データ及び当該データの識別子を前記第一の記憶部に記憶させる際に、転送された前記データ及び当該データの識別子を当該担当サーバが取得した時刻、又は、転送された前記データ及び当該データの識別子を当該担当サーバが前記第一の記憶部に記憶させた時刻を当該データの生成時刻として前記第一の記憶部に記憶させ、前記担当サーバは、前記データ又は前記保管成否信号に前記データの生成時刻を付与して前記クライアントへ送信することが望ましい。
【００２２】
なお、本発明は、コンピュータを前記した分散データ管理システムのサーバの各機能部として機能させるための分散データ管理プログラムとしても具現化可能である。
【発明の効果】
【００２３】
本発明によれば、複数のサーバが追加された場合であっても、リアルタイムに、かつスケーラビリティを損ねずにデータを移管することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施形態に係る分散データ管理システムを模式的に示す図である。
【図２】図１のサーバの構成を示すブロック図である。
【図３】データ表の一例を示す図である。
【図４】アドレス表の一例を示す図である。
【図５】本発明の実施形態に係る分散データ管理システムの動作例を説明するための図であって、ＩＤ空間を示す図である。
【図６】本発明の実施形態に係る分散データ管理システムの動作例を説明するためのフローチャートである。
【図７】従来技術におけるＩＤ空間を示す図である。
【図８】従来技術におけるＩＤ空間において、ノード（サーバ）が追加された場合を説明するための図であって、（ａ）は１つのノードが追加されたＩＤ空間を示す図、（ｂ）は複数のノードが追加されたＩＤ空間を示す図である。
【発明を実施するための形態】
【００２５】
以下、本発明の実施形態について、適宜図面を参照しながら説明する。図１に示すように、本発明の実施形態に係る分散データ管理システム１は、クライアント１０からの要求信号をロードバランサ２０を介して取得して応答するシステムであって、複数のサーバ３０（３０Ａ，３０Ｂ，…，３０Ｎ）を備える。複数のサーバ３０は、データを分散して管理しており、図示しないネットワークを介して互いに通信可能に接続されている。
【００２６】
＜クライアント及びロードバランサ＞
クライアント１０には、データの識別子と当該データの生成時刻とが関連付けて記憶されている。クライアント１０は、利用者による入力装置（キーボード、マウス等）の操作に応じて、分散データ管理システム１に記憶されたデータのクライアント１０への送信又は分散データ管理システム１での保管を要求する要求信号を生成し、生成された要求信号を分散データ管理システム１へ送信する。ここで、要求信号には、送信又は保管を要求すべきデータの識別子（データ識別子）と生成時刻（データ生成時刻）とが含まれる。ロードバランサ２０は、任意のサーバ３０を無作為に選択し、クライアント１０から送信された要求信号を選択されたサーバ３０へ転送する。なお、クライアント１０は、最初に、データ生成時刻を含まない、データの保管を要求する要求信号を生成して分散データ管理システム１へ送信し、後記するようにサーバ３０から応答信号に付与されて送信されたデータ生成時刻を取得し、取得されたデータ生成時刻を記憶し、以降はデータ識別子及びデータ生成時刻を引数として要求信号を生成することができる。
【００２７】
＜サーバ＞
複数のサーバ３０は、分散データ管理システム１全体で管理すべきデータのうち、当該サーバ３０が担当するデータをそれぞれ管理する。サーバ３０は、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read-Only Memory）、入出力回路等から構成されており、図２に示すように、機能部として、第一の記憶部３１−１と、第二の記憶部３１−２と、アドレス表生成部３２と、要求信号取得部３３と、担当サーバ特定部３４と、要求信号転送部３５と、応答部３６と、前担当サーバ特定部３７と、データ転送部３８と、データ更新部３９と、を備える。
【００２８】
＜第一の記憶部＞
第一の記憶部３１−１には、図３に示すデータ表３１ａが記憶されている。データ表３１ａは、サーバ３０が担当するデータと、当該データの識別子（データ識別子）と、当該データの生成時刻（データ生成時刻）とを関連付けた表である。
【００２９】
＜第二の記憶部＞
第二の記憶部３１−２には、図４に示すアドレス表３１ｂが記憶されている。アドレス表３１ｂは、分散データ管理システム１を構成する全てのサーバ３０の識別子（サーバ識別子）と、当該サーバ３０のアドレス（ＩＰアドレス等）とを関連付けた表であり、当該アドレス表３１ｂの生成時刻（アドレス表生成時刻）ごとに記憶されている。
【００３０】
＜アドレス表生成部＞
アドレス表生成部３２は、分散データ管理システム１を構成するサーバ３０の増減時に、アドレス表３１ｂを新たに生成し、新たなアドレス表３１ｂのアドレス表生成時刻とともに第二の記憶部３１−２に記憶させる。すなわち、第二の記憶部３１−２に記憶されたアドレス表３１ｂは、サーバ３０が増減して新たなアドレス表３１ｂが生成されても削除されずに履歴として保存され、サーバ３０の増減ごとに増える。なお、サーバ３０の増減時に、例えば追加（増設）されたサーバ３０にアドレスを付与したり、サーバ３０の増減及び新たに付与されたアドレスを他のサーバ３０と共有したりする技術としては、公知の技術を採用することが可能であり、ここでは詳しい説明を省略する。
【００３１】
＜要求信号取得部＞
要求信号取得部３３は、クライアント１０から送信された要求信号をロードバランサ２０を介して取得し、担当サーバ特定部３４へ出力する。
【００３２】
＜担当サーバ特定部＞
担当サーバ特定部３４は、要求信号取得部３３から出力された要求信号を取得し、取得された要求信号に含まれるデータ識別子と、第二の記憶部３１−２に記憶された最新のアドレス表３１ｂのサーバ識別子と、に基づいて、データの担当サーバを特定する。ここで、担当サーバ特定部３４は、既存のコンシステント・ハッシング等の技術を用いて担当サーバを特定することができる。自サーバ３０が担当サーバであると特定された場合には、担当サーバ特定部３４は、要求信号を応答部３６へ出力し、他サーバ３０が担当サーバであると特定された場合には、担当サーバ特定部３４は、担当サーバのアドレスを第二の記憶部３１−２に記憶されたアドレス表３１ｂから読み出し、要求信号及び読み出されたアドレスを要求信号転送部３５へ出力する。
【００３３】
＜要求信号転送部＞
要求信号転送部３５は、担当サーバ特定部３４から出力された要求信号及びアドレスを取得し、かかるアドレスを用いて要求信号を担当サーバの応答部３６へ転送する。
【００３４】
＜応答部＞
応答部３６は、自サーバ３０が担当サーバである場合に、自サーバ３０の担当サーバ特定部３４から出力された要求信号、又は、非担当サーバである他サーバ３０の要求信号転送部３５によって転送された要求信号を取得する。要求信号がデータの送信を要求するものである場合には、応答部３６は、取得された要求信号に含まれるデータ識別子に基づいて第一の記憶部３１−１に記憶されたデータ表３１ａを参照し、データ識別子に対応するデータを読み出してクライアント１０へ送信する。また、要求信号がデータの保管を要求するものである場合には、応答部３６は、取得された要求信号に含まれるデータ識別子に基づいて第一の記憶部３１−１に記憶されたデータ表３１ａを参照し、データ識別子に対応するデータがデータ表３１ａに記憶（保管）されているか否かを判定し、判定結果を示す保管成否信号を生成してクライアント１０へ送信する。
【００３５】
なお、担当サーバである自サーバ３０が分散データ管理システム１に追加されたばかりで、データ表３１ａに所望のデータが記憶されていない場合がある。この場合には、応答部３６は、要求信号を前担当サーバ特定部３７へ出力する。
【００３６】
＜前担当サーバ特定部＞
前担当サーバ特定部３７は、応答部３６から出力された要求信号を取得し、取得された要求信号に含まれるデータ生成時刻に基づいて第二の記憶部３１−２に記憶されたアドレス表３１ｂを参照し、データ生成時刻よりも古くかつ最新のアドレス表生成時刻を有するアドレス表３１ｂを特定する。前担当サーバ特定部３７は、取得された要求信号に含まれるデータ識別子と、特定されたアドレス表３１ｂのサーバ識別子と、に基づいて、データの直前の担当サーバ（前担当サーバ）を特定する。ここで、前担当サーバ特定部３７は、担当サーバ特定部３４と同様に、既存のコンシステント・ハッシング等の技術を用いて前担当サーバを特定することができる。データ生成時刻よりも古くかつ最新のアドレス表生成時刻を有するアドレス表３１ｂは、所望のデータの担当ノードの更新前のアドレス表に相当するため、かかるアドレス表３１ｂを用いると、担当ノード更新前（担当ノードの更新が行われていない場合は、データの分散データ管理システム１への最初の格納時）の担当ノード、すなわち前担当ノードを特定することができる。前担当サーバ特定部３７は、自サーバ３０のアドレス及び前担当サーバのアドレスを第二の記憶部３１−２に記憶されたアドレス表３１ｂから読み出し、要求信号及び読み出されたアドレスをデータ転送部３８へ出力する。
【００３７】
＜データ転送部＞
自サーバ３０が担当サーバであってデータを保管していないデータ転送部３８は、前担当サーバ特定部３７から出力された要求信号及びアドレスを取得し、取得された要求信号及びアドレスに基づいて、前担当サーバのデータ転送部３８との間でデータの転送を行い、前担当サーバからデータ及び当該データのデータ識別子を取得し、データ更新部３９へ出力する。
【００３８】
＜データ更新部＞
データ更新部３９は、データ転送部３８から出力されたデータ及びデータ識別子を取得し、取得されたデータを第一の記憶部３１−１のデータ表３１ａに記憶させる。
【００３９】
≪データ移管≫
ここで、自サーバ３０の第一の記憶部３１−１のデータ表３１ａに所望のデータが記憶されていない場合の、自サーバ３０及び前担当サーバのデータ転送部３８、データ更新部３９及び応答部３６のデータ移管に関する機能について詳細に説明する。
【００４０】
自サーバ３０が現在の担当サーバ（新担当サーバ）であってデータを保管していないデータ転送部３８は、要求信号及び自サーバ３０のアドレスを含むデータ転送依頼信号を、前担当サーバのアドレスを用いて前担当サーバのデータ転送部３８へ送信する。
【００４１】
前担当サーバのデータ転送部３８は、新担当サーバのデータ転送部３８によって送信されたデータ転送依頼信号を取得し、取得されたデータ転送依頼信号に含まれる要求信号のデータ識別子をデータ更新部３９へ出力する。
【００４２】
前担当サーバのデータ更新部３９は、データ転送部３８から出力されたデータ識別子を取得し、取得されたデータ識別子に基づいて第一の記憶部３１−１に記憶されたデータ表３１ａを参照し、データ識別子に対応するデータを読み出し、データ識別子及び読み出されたデータをデータ転送部３８へ出力する。ここで、データ更新部３９は、読み出したデータ及び当該データのデータ識別子（並びに当該データのデータ生成時刻）をデータ表３１ａから削除する。
【００４３】
前担当サーバのデータ転送部３８は、データ更新部３９から出力されたデータ及びデータ識別子を取得し、取得されたデータ及びデータ識別子を、新担当サーバのアドレスを用いて新担当サーバのデータ転送部３８へ送信する。
【００４４】
新担当サーバのデータ転送部３８は、前担当サーバのデータ転送部３８によって送信されたデータ及びデータ識別子を取得し、取得されたデータ及びデータ識別子をデータ更新部３９へ出力する。
【００４５】
新担当サーバのデータ更新部３９は、データ転送部３８から出力されたデータ及びデータ識別子を取得し、取得されたデータ及びデータ識別子を第一の記憶部３１−１のデータ表３１ａに記憶させるとともに、更新通知信号を応答部３６へ出力する。ここで、新担当サーバのデータ更新部３９は、前担当サーバから転送されてきたデータ及びデータ識別子を第一の記憶部３１−１のデータ表３１ａに記憶させる際に、前担当サーバから転送されてきたデータ及びデータ識別子を当該データ更新部３９が取得した時刻、又は、前担当サーバから転送されてきたデータ及びデータ識別子を当該データ更新部３９がデータ表３１ａに記憶させた時刻を当該データのデータ生成時刻としてデータ表３１ａに記憶させる。
【００４６】
新担当サーバの応答部３６は、データ更新部３９から出力された更新通知信号を取得し、取得された更新通知信号に応じて、データ又は保管成否信号をクライアント１０へ送信する。この際、新担当サーバの応答部３６は、要求信号に含まれるデータ識別信号に基づいて第一の記憶部３１−１のデータ表３１ａに記憶されたデータ生成時刻を読み出し、データ又は保管成否信号にデータ生成時刻を付与してクライアント１０へ送信することができる。
【００４７】
クライアント１０は、応答部３６によって送信されたデータ又は保管成否信号とデータ生成時刻とを取得すると、取得されたデータ生成時刻に基づいて、データ識別子と関連付けて記憶されたデータ生成時刻を更新する。
【００４８】
なお、前担当サーバのデータ更新部３９が所望のデータを読み出すことができなかった場合（前担当サーバのデータ表３１ａに所望のデータが無い場合）には、前担当サーバのデータ更新部３９は、データが無い旨を示す信号をデータ転送部３８へ出力し、前担当サーバのデータ転送部３８は、データが無い旨を示す信号を新担当サーバのデータ転送部３８へ送信する。新担当サーバのデータ転送部３８は、データが無い旨を示す信号を取得し、取得された信号をデータ更新部３９を介して応答部３６へ出力する（データ更新部３９を介さずに応答部３６へ直接出力する構成でも可）。新担当サーバの応答部３６は、データが無い旨を示す保管成否信号を生成し、クライアント１０へ送信する。
【００４９】
＜動作例＞
続いて、本発明の実施形態に係る分散データ管理システム１の動作例について、図５及び図６を参照して説明する（適宜図１〜図４参照）。かかる動作例では、図５に示すように、サーバ３０Ａ〜３０Ｆによって構成された分散データ管理システム１に対して、新たなサーバ３０Ｇ，３０Ｈ，３０Ｉ，３０Ｊがサーバ３０Ｆ，３０Ａ間に追加され、あるデータの担当サーバが、サーバ３０Ｇ〜３０Ｊの追加によって、サーバ３０Ａからサーバ３０Ｈに変更されているものとする。
【００５０】
まず、クライアント１０が、あるデータの要求信号をロードバランサ２０を介してサーバ３０Ｆへ送信する。サーバ３０Ｆの要求信号取得部３３が、要求信号を取得すると（ステップＳ１）、サーバ３０Ｆの担当サーバ特定部３４が、要求信号に含まれるデータ識別子と、最新のアドレス表３１ｂに記憶された全サーバ３０のサーバ識別子と、に基づいて、データの担当サーバを特定する。
【００５１】
本動作例では、担当サーバはサーバ３０Ｆではなくサーバ３０Ｈであるため（ステップＳ２でＮｏ）、サーバ３０Ｆの要求信号転送部３５が、要求信号を担当サーバであるサーバ３０Ｈの応答部３６へ送信する（ステップＳ３）。なお、サーバ３０Ｆが担当サーバである場合には（ステップＳ２でＹｅｓ）、サーバ３０Ｆの担当サーバ特定部３４が、要求信号をサーバ３０Ｆの応答部３６へ出力し、本フローはステップＳ４へ移行する。
【００５２】
ステップＳ３の実行後、担当サーバであるサーバ３０Ｈの応答部３６が、要求信号を取得し、取得された要求信号に含まれるデータ識別子に基づいて、第一の記憶部３１−１のデータ表３１ａからデータを探索する。本動作例では、サーバ３０Ｈのデータ表３１ａには所望のデータが記憶されていないため（ステップＳ４でＮｏ）、前担当サーバ特定部３７が、要求信号に含まれるデータ生成時刻よりも古くかつ最新のアドレス表生成時刻を有するアドレス表３１ｂに記憶されたサーバ識別子と、要求信号に含まれるデータ識別子と、に基づいて、データの前担当サーバを特定する（ステップＳ５）。なお、サーバ３０Ｈのデータ表３１ａに所望のデータが記憶されている場合には（ステップＳ４でＹｅｓ）、本フローはステップＳ７へ移行する。
【００５３】
ステップＳ５の実行後、担当サーバであるサーバ３０Ｈのデータ転送部３８及びデータ更新部３９と、前担当サーバであるサーバ３０Ａのデータ転送部３８及びデータ更新部３９とが、データの移管を行うとともに、担当サーバであるサーバ３０Ｈのデータ更新部３９が、データ生成時刻を更新する（ステップＳ６）。ステップＳ６によって、第一の記憶部３１−１のデータ表３１ａに、データ及びデータ識別子が記憶され、また、データ及びデータ識別子を取得した時刻又は記憶させた時刻がデータ生成時刻として記憶される。
【００５４】
続いて、担当サーバであるサーバ３０Ｈの応答部３６が、クライアントへ応答する（ステップＳ７）。要求信号がデータの送信を要求するものである場合には、応答部３６は、データ及びデータ生成時刻をクライアント１０へ送信し、要求信号がデータの保管を要求するものである場合には、応答部３６は、保管成否信号及びデータ生成時刻をクライアント１０へ送信する。
【００５５】
本発明の実施形態に係る分散データ管理システム１は、サーバ３０の増減ごとにアドレス表生成時刻を有するアドレス表３１ｂを生成して第二の記憶部３１−２に記憶させ、担当サーバの第一の記憶部３１−１のデータ表に所望のデータが記憶されていない場合には、データ生成時刻とアドレス表生成時刻とに基づいて選択した過去のアドレス表３１ｂに基づいて前担当サーバを特定し、特定された前担当サーバから新担当サーバへデータを移管するので、複数のサーバ３０が追加された場合であっても、隣接するサーバ３０に順にデータの有無を問い合わせたり、全てのサーバ３０にデータの有無を問い合わせたりする必要が無く、前担当サーバにのみ１ホップでデータの有無を確認することができ、リアルタイムに、かつスケーラビリティを損なわずにデータを移管することができる。
【００５６】
また、本発明の実施形態に係る分散データ管理システム１は、前担当サーバから新担当サーバへデータを移管した際に、新担当サーバがデータを取得した時刻又は新担当サーバの第一の記憶部３１−１のデータ表３１ａにデータを記憶させた時刻をデータ生成時刻としてデータ表３１ａに記憶させるとともにクライアント１０へ送信するので、データ移管後において、クライアント１０に新たなデータ生成時刻に基づいて要求信号を生成させることができる。
【００５７】
以上、本発明の実施形態について図面を参照して説明したが、本発明は前記実施形態に限定されず、本発明の要旨を逸脱しない範囲で適宜変更可能である。例えば、本発明は、コンピュータを前記サーバ３０として機能させるための分散データ管理プログラムとしても具現化可能である。また、サーバ３０及びデータの識別子の決定手法は、ハッシュ関数によるものに限定されず、サーバ３０のアドレスは、ＩＰアドレスに限定されない。また、クライアント１０及びサーバ３０は、それぞれ、一のコンピュータによって具現化されてもよく、複数のコンピュータによって具現化されてもよい。
【符号の説明】
【００５８】
１      分散データ管理システム
３０    サーバ（ノード）
３１−１  第一の記憶部
３１−２  第二の記憶部
３２    アドレス表生成部
３３    要求信号取得部
３４    担当サーバ特定部
３５    要求信号転送部
３６    応答部
３７    前担当サーバ特定部
３８    データ転送部
３９    データ更新部
【図１】
0005508346.tif 000002
【図２】
0005508346.tif 000003
【図３】
0005508346.tif 000004
【図４】
0005508346.tif 000005
【図５】
0005508346.tif 000006
【図６】
0005508346.tif 000007
【図７】
0005508346.tif 000008
【図８】
0005508346.tif 000009