(57)【特許請求の範囲】
【請求項１】
クライアントから受信したメッセージ信号を、複数のサーバに振り分ける負荷分散装置と、前記負荷分散装置から受信した前記メッセージ信号に基づき、自身が記憶するデータについて処理を実行する複数の前記サーバと、前記サーバそれぞれが記憶するデータのバックアップとなるデータを記憶する外部バックアップ装置と、を備える分散処理システムであって、
前記負荷分散装置は、リング状の識別子空間上に前記サーバそれぞれに固有な識別子であるサーバ識別子を昇順に配置すると共に、受信した前記メッセージ信号に付されるデータに固有な識別子であるデータ識別子を当該識別子空間上に昇順に配置することにより、受信した前記メッセージ信号の振り分け先となる前記サーバを決定する、コンシステントハッシュによる振り分け手法を採用しており、
前記サーバそれぞれは、自身に振り分けられた前記メッセージ信号に対応するデータを原本データとして記憶しておくと共に、前記識別子空間において隣接する冗長数Ｎ−１個の他のサーバに対し、前記原本データの複製データを生成して送信することにより、当該複製データを前記他のサーバに記憶させておき、
前記負荷分散装置は、
前記識別子空間において前記サーバそれぞれが担当する識別子の領域を示す担当領域を格納する識別子空間管理情報が記憶される記憶部と、
前記識別子空間上に配置された複数の前記サーバのうちから当該分散処理システムを離脱したサーバである離脱サーバを特定し、前記特定した離脱サーバのうちから１つの前記離脱サーバを抽出し、前記識別子空間上において前記抽出した離脱サーバに隣接する前記冗長数Ｎ−１個の他のサーバが全て前記離脱サーバである場合に、前記原本データと当該原本データについての全ての前記複製データとが失われた前記識別子空間上の領域である損失領域が存在すると判定すると共に、
当該損失領域を担当していた離脱サーバの識別子空間上で左回りに直近の残存サーバの前記担当領域の広さと、当該損失領域を担当していた離脱サーバの識別子空間上で右回りに直近の残存サーバの前記担当領域の広さとを比較し、前記担当領域が小さい方のサーバを、当該損失領域の新規担当サーバに決定し、前記決定した新規担当サーバとなる前記サーバに対し、前記損失領域に配置された前記データ識別子のデータである損失データの識別子の領域を示す損失領域の識別子領域情報を付した損失データ復旧指示情報を生成して送信するデータ損失処理部と、を備え、
前記サーバそれぞれは、
前記識別子空間管理情報、前記原本データおよび前記複製データが記憶される記憶部と、
当該記憶部に記憶された前記原本データをバックアップするためのデータを、前記外部バックアップ装置に送信するバックアップ処理部と、
受信した前記損失データ復旧指示情報に付された前記損失領域の識別子領域情報を含む損失データ取得要求を前記外部バックアップ装置に送信し、前記バックアップ装置から前記損失データを受信して、当該損失データを前記原本データとして自身の記憶部に記憶するリストア処理部と、を備え、
前記外部バックアップ装置は、
前記原本データをバックアップするためのデータと、当該データのデータ識別子とを対応付けて格納するバックアップデータ情報が記憶される記憶部と、
前記原本データをバックアップするためのデータを受信し、当該データのデータ識別子に対応付けて自身の記憶部の前記バックアップデータ情報に記憶すると共に、
受信した前記損失データ取得要求に含まれる前記損失領域の識別子領域情報に基づき、前記損失領域の識別子に対応する前記データ識別子のデータを前記バックアップデータ情報から抽出し、当該抽出したデータを前記損失データとして前記損失データ取得要求を送信してきた前記サーバに送信するバックアップデータ管理部と、を備えること
を特徴とする分散処理システム。
【請求項２】
前記負荷分散装置は、さらに、
前記損失領域を、前記新規担当サーバとなるサーバの前記担当領域に追加するように前記識別子空間管理情報を変更し、前記変更した識別子空間管理情報を前記サーバそれぞれに送信する識別子管理部を備え、
前記サーバそれぞれは、さらに、
前記変更した識別子空間管理情報を受信し、自身の記憶部に記憶する前記識別子空間管理情報を更新する識別子空間管理情報登録部と、
前記更新した識別子空間管理情報を参照し、自身の記憶部に記憶する原本データの複製データを生成し、前記識別子空間において隣接する冗長数Ｎ−１個の他のサーバに対し前記生成した複製データを送信する冗長化処理部と、
を備えることを特徴とする請求項１に記載の分散処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のサーバで構成される分散処理システムに関する。
【背景技術】
【０００２】
分散処理システムは、複数の物理的なサーバから構成され、必要に応じてこれらのサーバを仮想化して、目的となるサービスを実現する。また、分散処理システムは、一般的には、１または複数の負荷分散装置を含んで構成される。負荷分散装置は、端末（クライアント）からメッセージ信号を受信すると、所定の手法にしたがってメッセージ信号を分散処理システム内のサーバに振り分ける。各サーバは、振り分けられたメッセージ信号を処理し、端末に対してサービスを提供する。
【０００３】
この負荷分散装置が実行する所定の手法（振り分け手法）としては、例えば、コンシステントハッシュ法がある（非特許文献１参照）。コンシステントハッシュ法は、サーバを識別するサーバ識別子と、サーバに振り分けるメッセージ信号に含まれ、処理の対象となるデータの実体を識別するデータ識別子と、に基づいて、どのサーバにどのメッセージ信号（データ）を振り分けるかを決定する手法である。
【０００４】
コンシステントハッシュ法における、メッセージ信号の振り分け先の決定処理を、図１を参照して説明する。図１は、コンシステントハッシュ法を説明するためのＩＤ（Identifier）空間（識別子空間）の概念図である。サーバ識別子は、例えば、分散処理システムにサーバが参加する際などに、そのサーバに固有の識別子をハッシュ関数にかけた値（ハッシュ値）として決められる。図１においては、分散処理システムを構成するサーバのサーバ識別子を識別子空間に丸（○）で表して配置している。
【０００５】
識別子空間は、図１に示すように、リング状で描写されるハッシュ空間である。サーバ識別子は、例えば、その値（ハッシュ値）に基づいて識別子空間において右回りに昇順に配置される。メッセージ信号があるサーバに振り分けられるとき、データ識別子は、そのメッセージ信号に付されたデータの固有な情報をハッシュ関数にかけることで得られる値（ハッシュ値）に基づいて、識別子空間上に配置される。このデータ識別子も、サーバ識別子と同様に、その値に基づき、識別子空間において右回りに昇順に配置される。図１において、データ識別子は、三角「▲」で表して配置している。
【０００６】
この識別子空間に基づき、サーバは、自身のサーバ識別子の左回りに直近の別のサーバのサーバ識別子（以下、「左隣接サーバ識別子」と称する。）の配置場所から自身のサーバ識別子の配置場所まで右回りに辿る円弧上に配置されるデータ識別子を含むメッセージ信号の処理を担当する。図１において、識別子空間に配置される対象のデータ識別子と、そのデータ識別子を含むメッセージ信号の処理を行うサーバである「担当サーバ」との関係を、破線の矢印で示している。つまり、サーバ「１」は、左回りに直近のサーバであるサーバ「８」から自身のサーバ「１」との間の識別子空間に配置されるデータ識別子について、そのデータ識別子を含むメッセージ信号の処理を担当する。即ち、識別子空間上において、サーバ「８」とサーバ「１」との間の領域がサーバ「１」の担当領域となる。
【０００７】
サーバは、自身が担当するデータ識別子を含むメッセージ信号を処理した結果、そのデータ識別子と紐付くデータを生成し保存することがある。このようなときにおいて、あるサーバに障害が発生した場合でもデータの損失を防ぐため、データの複製（複製データ）を生成することによりデータの冗長化を実現する。複製データは、自身のサーバ識別子の右回りにＮ−１個の別サーバ識別子を持つサーバに配置する。ここで「Ｎ」は、冗長数であり、図１では冗長数Ｎ＝３の例を示している。
【０００８】
このように、データを冗長化していても、大規模災害等により、識別子空間上においてＮ個以上連続して隣接したサーバが同時に離脱すると、原本データと全ての複製データが失われる領域が発生する。図２においては、冗長数Ｎ＝３のときに、隣接するサーバ「１」，「２」，「３」が同時に離脱した場合を示している。この場合、サーバ「１」が担当していた領域のデータについては、サーバ「１」が記憶していた原本データが失われると共に、サーバ「２」，「３」が記憶していた全ての複製データも失われてしまう。このような場合に備えて、外部バックアップ装置にデータをバックアップし、ハードディスク等に半永続的に保存する方法がとられている。これにより、原本データと全ての複製データとが失われた領域が発生したときでも、外部バックアップ装置に保存しておいたデータから復旧することができる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】D. Karger, et al.,“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)、May 1997、pp.654-663、［online］、［平成２５年６月２７日検索］、インターネット<URL:http://thor.cs.ucsb.edu/~ravenben/papers/coreos/KLL+97.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１０】
この外部バックアップ装置にバックアップしておいたデータから復旧する場合、全データを一律に復旧させる手法がある。しかしながら、この手法では、全てのデータをバックアップから復旧するため、リストアに多大な時間がかかる。また、失われていなかったデータが、バックアップ取得後に更新されていた場合、そのデータがバックアップ時のデータに戻ってしまう。つまり、更新された最新の情報が失われてしまう。
そこで、本発明は、バックアップからのデータの復旧時において、原本データと全ての複製データとが失われた識別子空間上の領域（以下、「損失領域」とよぶ。図２参照。）に含まれるデータ（以下、損失領域にデータ識別子が配置されているデータを「損失データ」とよぶ。）のみを復旧対象としてデータ復旧することを課題とする。
【００１１】
また、損失データのみを外部バックアップ装置からの復旧対象とする場合、従来のコンシステントハッシュ法をそのまま適用すると、損失領域を新たに担当するサーバ（以下、「新規担当サーバ」とよぶ。）の担当領域が他のサーバに比べて大きくなる。例えば、図２の場合、サーバ「４」が、サーバ「１」、サーバ「２」、サーバ「３」の領域を全て追加して担当することになる。このとき、分散処理システム全体としては、１つのサーバにのみ負荷が偏り、安定動作が行われなくなる可能性が増加する。
【００１２】
このような背景に鑑みて本発明がなされたのであり、本発明は、原本データと全ての複製データとが失われたデータである損失データのみを復旧対象とした上で、その損失データのデータ復旧時において、サーバ負荷の偏りを低減させることができる分散処理システムを提供することを課題とする。
【課題を解決するための手段】
【００１３】
前記した課題を解決するため、請求項１に記載の発明は、クライアントから受信したメッセージ信号を、複数のサーバに振り分ける負荷分散装置と、前記負荷分散装置から受信した前記メッセージ信号に基づき、自身が記憶するデータについて処理を実行する複数の前記サーバと、前記サーバそれぞれが記憶するデータのバックアップとなるデータを記憶する外部バックアップ装置と、を備える分散処理システムであって、前記負荷分散装置が、リング状の識別子空間上に前記サーバそれぞれに固有な識別子であるサーバ識別子を昇順に配置すると共に、受信した前記メッセージ信号に付されるデータに固有な識別子であるデータ識別子を当該識別子空間上に昇順に配置することにより、受信した前記メッセージ信号の振り分け先となる前記サーバを決定する、コンシステントハッシュによる振り分け手法を採用しており、前記サーバそれぞれが、自身に振り分けられた前記メッセージ信号に対応するデータを原本データとして記憶しておくと共に、前記識別子空間において隣接する冗長数Ｎ−１個の他のサーバに対し、前記原本データの複製データを生成して送信することにより、当該複製データを前記他のサーバに記憶させておき、前記負荷分散装置が、前記識別子空間において前記サーバそれぞれが担当する識別子の領域を示す担当領域を格納する識別子空間管理情報が記憶される記憶部と、前記識別子空間上に配置された複数の前記サーバのうちから当該分散処理システムを離脱したサーバである離脱サーバを特定し、前記特定した離脱サーバのうちから１つの前記離脱サーバを抽出し、前記識別子空間上において前記抽出した離脱サーバに隣接する前記冗長数Ｎ−１個の他のサーバが全て前記離脱サーバである場合に、前記原本データと当該原本データについての全ての前記複製データとが失われた前記識別子空間上の領域である損失領域が存在すると判定すると共に、当該損失領域を担当していた離脱サーバの識別子空間上で左回りに直近の残存サーバの前記担当領域の広さと、当該損失領域を担当していた離脱サーバの識別子空間上で右回りに直近の残存サーバの前記担当領域の広さとを比較し、前記担当領域が小さい方のサーバを、当該損失領域の新規担当サーバに決定し、前記決定した新規担当サーバとなる前記サーバに対し、前記損失領域に配置された前記データ識別子のデータである損失データの識別子の領域を示す損失領域の識別子領域情報を付した損失データ復旧指示情報を生成して送信するデータ損失処理部と、を備え、前記サーバそれぞれが、前記識別子空間管理情報、前記原本データおよび前記複製データが記憶される記憶部と、当該記憶部に記憶された前記原本データをバックアップするためのデータを、前記外部バックアップ装置に送信するバックアップ処理部と、受信した前記損失データ復旧指示情報に付された前記損失領域の識別子領域情報を含む損失データ取得要求を前記外部バックアップ装置に送信し、前記バックアップ装置から前記損失データを受信して、当該損失データを前記原本データとして自身の記憶部に記憶するリストア処理部と、を備え、前記外部バックアップ装置が、前記原本データをバックアップするためのデータと、当該データのデータ識別子とを対応付けて格納するバックアップデータ情報が記憶される記憶部と、前記原本データをバックアップするためのデータを受信し、当該データのデータ識別子に対応付けて自身の記憶部の前記バックアップデータ情報に記憶すると共に、受信した前記損失データ取得要求に含まれる前記損失領域の識別子領域情報に基づき、前記損失領域の識別子に対応する前記データ識別子のデータを前記バックアップデータ情報から抽出し、当該抽出したデータを前記損失データとして前記損失データ取得要求を送信してきた前記サーバに送信するバックアップデータ管理部と、を備えることを特徴とする分散処理システムとした。
【００１４】
このように、分散処理システムは、例えば、大規模災害等が発生した場合に、負荷分散装置が、原本データと全ての複製データとが失われた識別子空間上の領域である損失領域が存在すると判定し、その損失領域を担当していた離脱サーバの左回りに直近の残存サーバ（左隣接サーバ）の識別子空間上での担当領域の広さと、損失領域を担当していた離脱サーバの右回りに直近の残存サーバ（右隣接サーバ）の識別子空間上での担当領域の広さとを比較し、担当領域が小さい方のサーバを、その損失領域を担当する新規担当サーバとして決定する。損失領域を担当する新規担当サーバとなったサーバは、外部バックアップ装置に対して、損失領域にデータ識別子が配置されているデータ（損失データ）の取得要求（損失データ取得要求）を送信し、外部バックアップ装置から、損失データのバックアップのデータを受信することにより、データを復旧する。
このようにすることで、分散処理システムは、原本データと全ての複製データとが失われたデータである損失データのみを復旧対象とした上で、残存するサーバのうち、損失領域を担当していた離脱サーバの左隣接サーバ若しくは右隣接サーバのうち、担当領域が小さい方のサーバを損失領域の新規担当サーバとして決定する。よって、分散処理システムは、損失データのみを復旧させることができると共に、その損失データのデータ復旧時において、サーバ負荷の偏りを低減させることができる。
【００１５】
請求項２に記載の発明は、前記負荷分散装置が、さらに、前記損失領域を、前記新規担当サーバとなるサーバの前記担当領域に追加するように前記識別子空間管理情報を変更し、前記変更した識別子空間管理情報を前記サーバそれぞれに送信する識別子管理部を備え、前記サーバそれぞれが、さらに、前記変更した識別子空間管理情報を受信し、自身の記憶部に記憶する前記識別子空間管理情報を更新する識別子空間管理情報登録部と、前記更新した識別子空間管理情報を参照し、自身の記憶部に記憶する原本データの複製データを生成し、前記識別子空間において隣接する冗長数Ｎ−１個の他のサーバに対し前記生成した複製データを送信する冗長化処理部と、を備えることを特徴とする請求項１に記載の分散処理システムとした。
【００１６】
このようにすることで、分散処理システムは、原本データと全ての複製データとが失われた損失データを、新規担当サーバとなるサーバが復旧した上で、その損失データ（原本データ）の複製データを生成し、冗長数Ｎ−１個の他のサーバに送信して保存させることができる。よって、分散処理システムとしての保存データの冗長数を維持することができる。
【発明の効果】
【００１７】
本発明によれば、原本データと全ての複製データとが失われたデータである損失データのみを復旧対象とした上で、その損失データのデータ復旧時において、サーバ負荷の偏りを低減させる分散処理システムを提供することができる。
【図面の簡単な説明】
【００１８】
【図１】コンシステントハッシュ法を説明するための識別子空間の概念図である。
【図２】識別子空間上における損失領域を説明するための図である。
【図３】本実施形態に係る分散処理システムの全体構成を示す図である。
【図４】本実施形態に係る負荷分散装置の構成例を示す機能ブロック図である。
【図５】本実施形態に係る識別子空間管理情報のデータ構成の一例を示す図である。
【図６】本実施形態に係る損失データ管理情報のデータ構成の一例を示す図である。
【図７】本実施形態に係るサーバの構成例を示す機能ブロック図である。
【図８】本実施形態に係る外部バックアップ装置の構成例を示す機能ブロック図である。
【図９】本実施形態に係る分散処理システムを構成する各装置が実行する全体の処理の流れを示すシーケンス図である。
【図１０】本実施形態に係る負荷分散装置が実行する損失領域の特定処理の流れを示すフローチャートである。
【図１１】本実施形態に係る負荷分散装置が実行する新規担当サーバの決定処理の流れを示すフローチャートである。
【図１２】本実施形態に係る負荷分散装置が実行する新規担当サーバの決定処理の具体例を説明するための図である。
【発明を実施するための形態】
【００１９】
次に、本発明を実施するための形態（以下、「本実施形態」という）における分散処理システム１について説明する。
【００２０】
＜システム構成と処理概要＞
図３は、本実施形態に係る分散処理システム１の全体構成を示す図である。
図３に示すように、分散処理システム１は、複数のクライアント２に接続される１つ以上の負荷分散装置１０と、複数のサーバ２０（２０Ａ，２０Ｂ，…，２０Ｎ）と、外部バックアップ装置３０とを含んで構成される。
【００２１】
負荷分散装置１０は、各クライアント２からのメッセージ信号を受信し、その受信したメッセージ信号の振り分け先となるサーバ２０を、コンシステントハッシュ法に基づき決定し、その決定した振り分け先のサーバ２０に対して、メッセージ信号を送信する。
サーバ２０それぞれは、負荷分散装置１０から受け取ったメッセージ信号を処理し、メッセージ信号に対応するデータを記憶する。また、サーバ２０それぞれは、自身宛のメッセージ信号に関するデータを原本データとして記憶するとともに、他のサーバ２０から受信した複製データを保存する。
外部バックアップ装置３０は、各サーバ２０が記憶するデータを、所定の時間間隔で各サーバ２０から取得することにより、バックアップのデータを記憶する。
【００２２】
本実施形態に係る分散処理システム１は、例えば、大規模災害等が発生した場合に、負荷分散装置１０が、原本データと全ての複製データとが失われた識別子空間上の領域である損失領域が存在するか否かを判定する。そして、負荷分散装置１０は、損失領域が存在する場合に、その損失領域を担当していた離脱サーバの左回りに直近の残存サーバ（左隣接サーバ）の識別子空間上での担当領域の広さと、損失領域を担当していた離脱サーバの右回りに直近の残存サーバ（右隣接サーバ）の識別子空間上での担当領域の広さとを比較し、担当領域が小さい方のサーバを、その損失領域を担当する新規担当サーバとして決定する。損失領域を担当する新規担当サーバとなったサーバ２０は、外部バックアップ装置３０に対して、損失領域にデータ識別子が配置されているデータ（損失データ）の取得要求（後記する「損失データ取得要求」）を送信し、外部バックアップ装置３０から、損失データのバックアップのデータを受信することにより、データを復旧する。
【００２３】
このようにすることにより、本実施形態に係る分散処理システム１は、原本データと全ての複製データとが失われたデータである損失データのみを復旧対象とした上で、残存するサーバのうち、損失領域を担当していた離脱サーバの左隣接サーバ若しくは右隣接サーバのうち、担当領域が小さい方のサーバを損失領域の新規担当サーバとして決定する。これにより、分散処理システム１は、損失データのデータ復旧時において、サーバ負荷の偏りを低減させることができる。
【００２４】
＜各装置の構成＞
以下、本実施形態に係る分散処理システム１を構成する各装置に構成例について、具体的に説明する。
【００２５】
≪負荷分散装置≫
負荷分散装置１０は、各クライアント２（図３参照）から受信したメッセージ信号の振り分け先となるサーバ２０をコンシステントハッシュ法に基づき決定し、その決定したサーバ２０にメッセージ信号を送信する。また、負荷分散装置１０は、各サーバ２０からメッセージ信号に対する処理結果である応答信号を受信し、メッセージ信号を送信してきたクライアント２に送信する。
さらに、負荷分散装置１０は、大規模災害等が発生し複数のサーバ２０が離脱した場合に、識別子空間上に原本データと全ての複製データとが失われた領域である損失領域が存在するか否かを判定して、損失領域が存在する場合に、その損失領域を担当する新規担当サーバを決定する。
【００２６】
図４は、本実施形態に係る負荷分散装置１０の構成例を示す機能ブロック図である。
負荷分散装置１０は、図４に示すように、制御部１１と、入出力部１２と、記憶部１３とを含んで構成される。
【００２７】
入出力部１２は、複数のクライアント２や複数のサーバ２０（２０Ａ，２０Ｂ，…，２０Ｎ）それぞれとの間の情報の入出力を行う。例えば、入出力部１２は、クライアント２からメッセージ信号を受信し、サーバ２０に対しそのメッセージ信号を送信する。
また、この入出力部１２は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００２８】
制御部１１は、負荷分散装置１０全体の制御を司り、情報受信部１１１と、振り分け処理部１１２と、識別子管理部１１３と、データ損失処理部１１４と、情報送信部１１５とを含んで構成される。なお、この制御部１１は、例えば、記憶部１３に格納されたプログラムを、不図示のＣＰＵ（Central Processing Unit）がＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００２９】
情報受信部１１１は、入出力部１２を介して、クライアント２からのメッセージ信号や、各サーバ２０からの応答信号等を取得する。
また、情報受信部１１１は、取得したメッセージ信号を、振り分け処理部１１２に受け渡す。
【００３０】
振り分け処理部１１２は、情報受信部１１１からメッセージ信号を受信すると、そのメッセージ信号に含まれる処理対象となるデータに固有な識別子を抽出しハッシュ関数にかけることで、そのメッセージ信号が対象とするデータのデータ識別子（ハッシュ値）を計算する。そして、振り分け処理部１１２は、計算したデータ識別子（ハッシュ値）に基づき、記憶部１３に記憶された識別子空間管理情報１００（後記する図５）を参照し、振り分け先となるサーバ２０を決定する。振り分け処理部１１２は、決定したサーバ２０に対して、受信したメッセージ信号を、情報送信部１１５を介して送信する。
なお、振り分け処理部１１２は、大規模災害発生等により複数のサーバ２０が離脱し、損失領域が発生する可能性がある場合に、クライアント２から受信するメッセージ信号の振り分けを停止する（詳細は後記）。また、振り分け処理部１１２は、データ損失処理部１１４から、損失データが復旧した旨の情報を受け取った場合に、メッセージ信号の振り分けを再開する。
【００３１】
図５は、本実施形態に係る識別子空間管理情報１００のデータ構成の一例を示す図である。
図５に示すように、識別子空間管理情報１００は、サーバＩＤ１０１、サーバ識別子１０２、および、当該サーバのアドレス１０３のデータ項目を含んで構成される。
ここで、サーバＩＤ１０１は、メッセージ信号の振り分け先となるサーバ２０を、本分散処理システム１内において特定するための固有の番号である。
サーバ識別子１０２は、識別子空間内において、サーバ２０が担当する領域を特定するためのものであり、例えば、「０」から順に「９９９９」までのいずれかの値（ハッシュ値）が各サーバ２０に対応付けられて格納される。
例えば、図５に示す、第１行目のサーバ識別子１０２が「２０」の場合は、サーバＩＤ１０１が「１」のサーバ２０の識別子空間におけるデータの担当領域が「０」〜「２０」であることを示す。また、２行目のサーバ識別子１０２が「８２３」の場合は、サーバＩＤ１０１が「２」のサーバ２０の識別子空間におけるデータの担当領域が、１つ前の行のサーバ識別子１０２の値に「１」をプラスした「２１」〜「８２３」であることを示す。以下、同様である。
アドレス１０３は、サーバＩＤ１０１に示されるサーバ２０についての、例えば、ＩＰ（Internet Protocol）アドレスである。
【００３２】
図４に戻り、識別子管理部１１３は、識別子空間管理情報１００の作成や更新等を行う。具体的には、識別子管理部１１３は、識別子空間上に配置されたサーバ２０が離脱した場合に、その離脱サーバが担当していた領域を隣接サーバの担当領域に追加するようにして、識別子空間管理情報１００を更新する。また、識別子管理部１１３は、後記するデータ損失処理部１１４により、損失領域の新規担当サーバが決定されると、その決定を反映して識別子空間管理情報１００を更新する（詳細は後記）。
識別子管理部１１３は、識別子空間管理情報１００を更新すると、その更新情報を各サーバ２０に送信する。このようにして、分散処理システム１内の負荷分散装置１０と各サーバ２０とが記憶する識別子空間管理情報１００には、同一の情報が格納されるようにする。
【００３３】
データ損失処理部１１４は、離脱サーバを特定することにより、識別子空間上の損失領域を特定し、損失領域を担当する新規担当サーバを決定する処理を行う。
具体的には、データ損失処理部１１４は、例えば、分散処理システム１内の全てのサーバ２０等に生存確認メッセージを送信し、その応答メッセージを各サーバ２０から受信すること等により、離脱サーバを特定する。そして、データ損失処理部１１４は、識別子空間上において、特定した離脱サーバのうちの１つを抽出し、抽出した離脱サーバのサーバ識別子の右回りにＮ−１個（Ｎ：冗長数）の隣接サーバが全て離脱サーバか否かを判定する。データ損失処理部１１４は、Ｎ−１個の隣接サーバが全て離脱サーバである場合に、抽出した離脱サーバが担当していた領域を、損失領域として特定し、記憶部１３内の損失データ管理情報１５０（後記する図６参照）に登録する。
次に、データ損失処理部１１４は、損失領域を担当していた離脱サーバの左回りに直近の残存サーバ（左隣接サーバ）の識別子空間上での担当領域の広さと、損失領域を担当していた離脱サーバの右回りに直近の残存サーバ（右隣接サーバ）の識別子空間上での担当領域の広さとを比較し、担当領域が小さい方のサーバを、その損失領域を担当する新規担当サーバとして決定する。
【００３４】
図６は、本実施形態に係る損失データ管理情報１５０のデータ構成の一例を示す図である。損失データ管理情報１５０は、損失領域ＩＤ１５１、識別子領域１５２、および、新規担当サーバ１５３のデータ項目を含んで構成される。
損失領域ＩＤ１５１は、本分散処理システム１内において、損失領域を特定するための固有の番号である。
識別子領域１５２は、識別子空間上での損失領域の範囲を示す情報であり、損失領域を担当していた離脱サーバ（サーバ２０）の担当領域が格納される。
新規担当サーバ１５３は、データ損失処理部１１４により決定された当該損失領域の新規担当サーバ（損失領域を担当していた離脱サーバの右隣接サーバ若しくは左隣接サーバ）のアドレスが格納される。
【００３５】
データ損失処理部１１４は、損失領域を特定すると、図６（ａ）に示すように、損失データ管理情報１５０に新たなレコードを作成し、新たな損失領域ＩＤ１５１を付して、その特定した損失領域を担当していたサーバ２０の担当領域を、識別子領域１５２に格納する。図６（ａ）においては、図５に示すサーバＩＤ１０１が「１」のサーバの担当領域が損失領域として特定された例として、損失領域ＩＤ１５１を「１」とし、損失領域の範囲を示す識別子領域１５２が「０〜２０」として登録されたことを示している。
また、データ損失処理部１１４は、図６（ｂ）に示すように、損失領域の右隣接サーバ若しくは左隣接サーバを新規担当サーバに決定すると、そのサーバ２０のアドレスを、損失データ管理情報１５０内の新規担当サーバ１５３に格納する。
【００３６】
さらに、データ損失処理部１１４は、損失領域の新規担当サーバを特定すると、識別子領域１５２の情報、つまり、損失領域を担当していたサーバ２０の担当領域についての情報（以下、「損失領域の識別子領域情報」とよぶことがある。）を含む、損失データ復旧指示情報を生成し、その新規担当サーバに対して送信する。
なお、データ損失処理部１１４は、すべての新規担当サーバから、損失データの復旧が完了したことを示す損失データ復旧完了情報を受信すると、振り分け処理部１１２に対し、損失データが復旧した旨の情報を出力し、メッセージ信号の振り分け処理を再開させる。
【００３７】
情報送信部１１５は、データ損失処理部１１４が生成した損失データ復旧指示情報や、識別子管理部１１３が更新した識別子空間管理情報１００等を、各サーバ２０に送信する。
【００３８】
記憶部１３は、ハードディスクやフラッシュメモリ、ＲＡＭ等の記憶装置からなり、前記した、識別子空間管理情報１００（図５参照）や損失データ管理情報（図６参照）を記憶する。
【００３９】
なお、本実施形態においては、図３に示すように、負荷分散装置１０は１つとして説明するが、負荷分散装置１０は複数であってもよい。その場合には、複数の負荷分散装置１０のうちの１つが代表（マスタ）となり、上記において説明した損失データの復旧処理を行なう。
【００４０】
≪サーバ≫
次に、サーバ２０の構成例について説明する。図７は、本実施形態に係るサーバ２０の構成例を示す機能ブロック図である。
サーバ２０は、負荷分散装置１０、自身以外の他のサーバ２０および外部バックアップ装置３０と通信可能に接続され、制御部２１と、入出力部２２と、記憶部２３とを含んで構成される。
【００４１】
入出力部２２は、負荷分散装置１０や外部バックアップ装置３０等との間の情報の入出力を行う。例えば、入出力部２２は、負荷分散装置１０からメッセージ信号を受信し、その処理結果である応答情報を、負荷分散装置１０に送信したりする。
また、この入出力部２２は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００４２】
制御部２１は、サーバ２０全体の制御を司り、情報受信部２１１と、メッセージ処理部２１２と、識別子空間管理情報登録部２１３と、冗長化処理部２１４と、バックアップ処理部２１５と、リストア処理部２１６と、情報送信部２１７とを含んで構成される。なお、この制御部２１は、例えば、記憶部２３に格納されたプログラムを不図示のＣＰＵがＲＡＭに展開し実行することで実現される。
【００４３】
情報受信部２１１は、入出力部２２を介して、負荷分散装置１０からのメッセージ信号や、外部バックアップ装置３０からの損失データ等を受信する。
【００４４】
メッセージ処理部２１２は、クライアント２から負荷分散装置１０を介して受信したメッセージ信号の内容に基づき、記憶部２３内に記憶されたデータ２００について、参照、変更、削除等の処理を実行し、その実行結果を、クライアント２に向けて応答情報として送信する。
【００４５】
識別子空間管理情報登録部２１３は、負荷分散装置１０が作成した識別子空間管理情報１００を受信し、予め記憶部２３に記憶しておく。また、識別子空間管理情報登録部２１３は、負荷分散装置１０から識別子空間管理情報１００の更新情報を受信し、自身の記憶部２３に記憶している識別子空間管理情報１００を更新する。
【００４６】
冗長化処理部２１４は、自身のサーバ２０が記憶部２３に記憶する原本データについての複製データを作成し、識別子空間上において自身のサーバ識別子の右回りにＮ−１個（Ｎ：冗長数）の別サーバ識別子を持つサーバ２０にその複製データを送信することにより保存させる。また、冗長化処理部２１４は、自身のサーバ２０が他のサーバ２０から複製データを受信した場合には、その複製データを記憶部２３に記憶する。
【００４７】
バックアップ処理部２１５は、所定の時間間隔毎に、自身が保存する原本データをバックアップするための情報を、外部バックアップ装置３０に送信する。この原本データをバックアップするための情報は、バックアップ処理部２１５が、原本データの全てを複製して外部バックアップ装置３０に送信するようにしてもよいし、所定の時間間隔において変更された情報（差分情報）のみを外部バックアップ装置３０に送信するようにしてもよい。
【００４８】
リストア処理部２１６は、負荷分散装置１０から、損失領域を担当していたサーバ２０の担当領域の情報（図６の識別子領域１５２を示す「損失領域の識別子領域情報」）を含む損失データ復旧指示情報を受信すると、外部バックアップ装置３０に対し、その損失領域の識別子領域情報を含む損失データ取得要求を生成し、入出力部２２を介して、外部バックアップ装置３０に送信する。
【００４９】
また、リストア処理部２１６は、外部バックアップ装置３０から損失データを取得し、記憶部２３に原本データとして記憶する。さらに、リストア処理部２１６は、損失データを原本データとして記憶したことを契機として、冗長化処理部２１４を起動させることにより、記憶部２３に記憶した原本データの複製データを他のサーバ２０に記憶させる。
さらに、リストア処理部２１６は、損失データ（原本データ）の記憶部２３への記憶と、冗長化処理部２１４による、複製データの送信が完了すると、損失データ復旧完了情報を生成し、負荷分散装置１０に送信する。
【００５０】
情報送信部２１７は、メッセージ処理部２１２が生成したクライアント２に向けて応答情報や、リストア処理部２１６が生成した外部バックアップ装置３０に向けての損失データ取得要求等を送信する。
【００５１】
記憶部２３は、ハードディスクやフラッシュメモリ、ＲＡＭ等の記憶装置からなり、前記した、識別子空間管理情報１００や、データ２００を記憶する。なお、データ２００は、原本データや複製データを含む情報である。
【００５２】
≪外部バックアップ装置≫
次に、外部バックアップ装置３０の構成例について説明する。図８は、本実施形態に係る外部バックアップ装置３０の構成例を示す機能ブロック図である。
外部バックアップ装置３０は、複数のサーバ２０それぞれと通信可能に接続され、制御部３１と、入出力部３２と、記憶部３３とを含んで構成される。
【００５３】
入出力部３２は、各サーバ２０との間の情報の入出力を行う。例えば、入出力部３２は、各サーバ２０からデータ（原本データ）を受信したり、損失データ取得要求を受信し、それに対応するデータ（損失データ）を送信したりする。
また、この入出力部３２は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００５４】
制御部３１は、外部バックアップ装置３０の全体の制御を司り、情報受信部３１１と、バックアップデータ管理部３１２と、情報送信部３１３とを含んで構成される。
【００５５】
情報受信部３１１は、入出力部２２を介して受信した、各サーバ２０からのデータ（原本データ）や、損失データ取得要求等を、バックアップデータ管理部３１２に受け渡す。
【００５６】
バックアップデータ管理部３１２は、各サーバ２０からデータ（原本データ）若しくはその原本データの差分情報を受信すると、記憶部３３内のバックアップデータ情報３００に記憶する。
【００５７】
このバックアップデータ情報３００は、バックアップデータＩＤ３０１、データ識別子３０２およびデータ３０３から構成される。
バックアップデータＩＤ３０１は、外部バックアップ装置３０内において、記憶したデータを特定するための固有の番号である。
データ識別子３０２には、識別子空間上においてそのデータを特定するためのデータ識別子の値（ハッシュ値）が格納される。
また、データ３０３には、バックアップのためのデータ（原本データ）の情報がデータ識別子３０２に対応付けられて格納される。
【００５８】
バックアップデータ管理部３１２は、損失領域の新規担当サーバとなったサーバ２０から、損失領域の識別子領域情報を含む損失データ取得要求を受信すると、記憶部３３内のバックアップデータ情報３００を参照し、その損失領域の識別子領域情報に示される範囲のデータ識別子３０２に対応付けられたデータ３０３を抽出し、その抽出したデータ３０３、つまり、損失データを、損失データ取得要求を送信してきたサーバ２０に対し送信する。
【００５９】
情報送信部３１３は、バックアップデータ管理部３１２が抽出したデータ３０３（損失データ）を、損失データ取得要求を送信してきたサーバ２０に向けて送信する。
【００６０】
記憶部３３は、ハードディスクやフラッシュメモリ、ＲＡＭ等の記憶装置からなり、前記したバックアップデータ情報３００等を記憶する。
【００６１】
＜分散処理システムの処理の流れ＞
次に、本実施形態に係る分散処理システム１が実行する処理の流れについて説明する。
【００６２】
図９は、本実施形態に係る分散処理システム１を構成する各装置が実行する全体の処理の流れを示すシーケンス図である。
【００６３】
ここでは、大規模災害等により分散処理システム１内の複数のサーバ２０に障害が発生し、原本データと全ての複製データとが失われた領域である損失領域の発生が予測される事態になったものとする。このような事態が発生した場合に、負荷分散装置１０は、図示を省略したネットワーク管理装置等から、例えば、損失領域発生の有無の確認指示情報を受信することを契機として、以下に示す、損失領域のデータ（損失データ）のバックアップ処理の実行を開始するようにしてもよい。また、負荷分散装置１０は、各サーバ２０に対し、所定の時間間隔で生存確認情報を送信し、その応答情報を受信することにより、サーバ２０の生存を確認しており、所定数（例えば冗長数Ｎ個）を超えるサーバ２０が一度に離脱した場合に、以下に示す、損失領域のデータ（損失データ）のバックアップ処理の実行を開始するようにしてもよい。
【００６４】
負荷分散装置１０（振り分け処理部１１２）は、上記のようにして、複数のサーバ２０の障害が発生したことにより、識別子空間上において損失領域が発生した可能性がある場合に、まず、クライアント２から受信するメッセージ信号の振り分けを停止する（ステップＳ１）。
【００６５】
次に、負荷分散装置１０のデータ損失処理部１１４は、原本データおよび全ての複製データが失われた識別子空間上の領域である損失領域を特定する（損失領域の特定処理：ステップＳ２）。なお、この損失領域の特定処理は、後記する図１０において詳細に説明する。
【００６６】
続いて、負荷分散装置１０のデータ損失処理部１１４は、特定した損失領域の新規担当サーバを決定し（新規担当サーバの決定処理：ステップＳ３）、識別子管理部１１３が、損失領域を新規担当サーバが担当するように、記憶部１３に記憶する識別子空間管理情報１００を更新（変更）する。この新規担当サーバの決定処理は、後記する図１１において詳細に説明する。
なお、図示は省略しているが、負荷分散装置１０の識別子管理部１１３は、識別子空間管理情報１００の更新（変更）情報を、分散処理システム１内の各サーバ２０に送信し、各サーバ２０の識別子空間管理情報１００を更新させる。そして、各サーバ２０は、更新した識別子空間管理情報１００を参照し、新たに担当領域となったデータについては、そのサーバ２０の冗長化処理部２１４が、自身が記憶する複製データを原本データとし、その原本データの複製データを生成して、識別子空間上において自身のサーバ識別子の右回りにＮ−１個（Ｎ：冗長数）の別サーバ識別子を持つサーバ２０にその複製データを送信し保存させる。このようにすることにより、分散処理システム１内の冗長数を保つようにする。
【００６７】
次に、負荷分散装置１０のデータ損失処理部１１４は、損失領域の識別子領域情報（損失領域を担当していたサーバ２０の担当領域の情報（図６の識別子領域１５２））を含む損失データ復旧指示情報を生成し、ステップＳ３で決定した新規担当サーバに対して送信する（ステップＳ４）。
【００６８】
損失データ復旧指示情報を受信した新規担当サーバ（サーバ２０）のリストア処理部２１６は、損失領域の識別子領域情報を含む損失データ取得要求を生成し、外部バックアップ装置３０に対して送信する（ステップＳ５）。
【００６９】
外部バックアップ装置３０のバックアップデータ管理部３１２は、損失領域の識別子領域情報を含む損失データ取得要求を新規担当サーバ（サーバ２０）から受信すると、自身の記憶部３３内のバックアップデータ情報３００（図８）を参照し、その損失領域の識別子領域情報に示される範囲のデータ識別子３０２のデータ３０３、つまり、損失データを抽出する（損失データ抽出処理：ステップＳ６）。そして、バックアップデータ管理部３１２は、その抽出したデータ３０３（損失データ）を、損失データ取得要求を送信してきた新規担当サーバ（サーバ２０）へ送信する（ステップＳ７）。
なお、このとき、損失領域の識別子領域情報において指定された領域にデータが存在しない場合もあり得るが、その場合、バックアップデータ管理部３１２は、データ存在しない旨を新規担当サーバ（サーバ２０）へ送信する。
【００７０】
損失データを受信した新規担当サーバ（サーバ２０）のリストア処理部２１６は、自身の記憶部２３に、受信した損失データを原本データとして記憶する（損失データリストア処理：ステップＳ８）。
また、新規担当サーバ（サーバ２０）のリストア処理部２１６は、冗長化処理部２１４を起動させ、冗長化処理部２１４が、ステップＳ３において更新された識別子空間管理情報１００を参照し、識別子空間上で自身の右Ｎ−１個の隣接サーバに対し、データ復旧し記憶部２３に記憶した損失データ（原本データ）の複製データを作成して送信する（損失データ複製送信処理：ステップＳ９）。
【００７１】
続いて、新規担当サーバ（サーバ２０）のリストア処理部２１６は、損失データ復旧完了情報を生成して負荷分散装置１０に送信する（ステップＳ１０）。
【００７２】
損失データ復旧完了情報を全ての新規担当サーバ（サーバ２０）から受信した負荷分散装置１０は、振り分け処理部１１２が、クライアント２から受信するメッセージ信号の振り分けを再開する（ステップＳ１１）。
【００７３】
≪損失領域の特定処理≫
次に、図９のステップＳ２において負荷分散装置１０が実行する損失領域の特定処理について詳細に説明する。図１０は、本実施形態に係る負荷分散装置１０が実行する損失領域の特定処理の流れを示すフローチャートである。なお、ここで、冗長数は「Ｎ」であるものとする。
【００７４】
まず、負荷分散装置１０のデータ損失処理部１１４は、大規模災害等により障害が発生し離脱したサーバ２０（離脱サーバ）を特定する（ステップＳ２０）。この離脱サーバの特定は、例えば、不図示のネットワーク管理装置から、離脱サーバに関する情報を取得してもよいし、各サーバ２０に生存確認要求を送信し、それに対する応答情報を所定の時間内に受信できない場合に、そのサーバ２０を離脱サーバと特定するようにしてもよい。
【００７５】
次に、データ損失処理部１１４は、特定した全ての離脱サーバの中から１つを抽出する（ステップＳ２１）。
【００７６】
続いて、データ損失処理部１１４は、ステップＳ２１において抽出した離脱サーバの識別子空間上の右Ｎ−１個の隣接サーバが、全て離脱サーバか否かを判定する（ステップＳ２２）。ここで、右Ｎ−１個の隣接サーバが、全て離脱サーバである場合には（ステップＳ２２→Ｙｅｓ）、ステップＳ２３に進む。一方、右Ｎ−１個の隣接サーバのいずれかが離脱サーバではない場合には（ステップＳ２２→Ｎｏ）、ステップＳ２４に進む。
【００７７】
ステップＳ２３において、データ損失処理部１１４は、右Ｎ−１個の隣接サーバが、全て離脱サーバであることから、抽出した離脱サーバの識別子空間上での担当領域を損失領域として特定し、損失データ管理情報１５０に登録する。具体的には、データ損失処理部１１４は、損失データ管理情報１５０に新たなレコードを作成し、新たな損失領域ＩＤ１５１を付して、その特定した損失領域を担当していた離脱サーバ（サーバ２０）の担当領域を、識別子領域１５２に格納する（図６（ａ）参照）。
【００７８】
一方、ステップＳ２４において、データ損失処理部１１４は、右Ｎ−１個の隣接サーバのうちのいずれかが残存サーバであるため、つまり、複製データを記憶するいずれかのサーバ２０が存在するため、次に示す処理を実行する。データ損失処理部１１４は、残存サーバのうち、抽出した離脱サーバに最も近い右隣接サーバを、当該抽出した離脱サーバの担当領域を新たに担当するサーバ２０として決定する。そして、識別子管理部１１３が、新たに担当するサーバ２０の担当領域に、抽出した離脱サーバの担当領域を追加するようにして、識別子空間管理情報１００を更新する。
【００７９】
ステップＳ２３およびステップＳ２４を終えると、次のステップＳ２５において、データ損失処理部１１４は、ステップＳ２０において特定した全ての離脱サーバについて、処理（ステップＳ２１〜Ｓ２４）を終了したか否かを判定する。ここで、まだ処理を実行していない離脱サーバが残っている場合には（ステップＳ２５→Ｎｏ）、ステップＳ２１に戻り、未処理の離脱サーバのうちから１つを抽出し、その後の処理を続ける。
【００８０】
一方、全ての離脱サーバについて処理を終了している場合には（ステップＳ２５→Ｙｅｓ）、損失領域の特定処理を終了し、図９のステップＳ３（新規担当サーバの決定処理）に進む。
【００８１】
≪新規担当サーバの決定処理≫
次に、図９のステップＳ３において負荷分散装置１０が実行する新規担当サーバの決定処理について、図１１および図１２を参照して、詳細に説明する。図１１は、本実施形態に係る負荷分散装置１０が実行する新規担当サーバの決定処理の流れを示すフローチャートである。また、図１２は、本実施形態に係る負荷分散装置１０が実行する新規担当サーバの決定処理の具体例を説明するための図である。なお、図１２においては、リンク状の識別子空間を、説明を容易にするため直線として表現し、冗長数Ｎ＝２であるものとする。また、図１２（ａ）に示すように、サーバ「４」，「６」，「７」が大規模災害等により離脱したサーバ２０（離脱サーバ）であるものとする。
【００８２】
図１１に示すように、まず、負荷分散装置１０のデータ損失処理部１１４は、損失データ管理情報１５０（図６）に記憶された損失領域の範囲を示す識別子領域１５２を参照し、新規担当サーバ１５３が空欄の領域（識別子領域１５２）のうち、最も大きい領域を特定する（ステップＳ３０）。
【００８３】
次に、データ損失処理部１１４は、特定した領域の左隣接サーバと右隣接サーバの担当領域の広さを比較する（ステップＳ３１）。
具体的には、データ損失処理部１１４は、まず、抽出した領域の開始識別子から左回りに直近のサーバ識別子を持つ残存するサーバ２０（左隣接サーバ）と、その抽出した領域の終了識別子から右回りに直近のサーバ識別子を持つ残存するサーバ２０（右隣接サーバ）とを特定する。そして、データ損失処理部１１４は、特定した左隣接サーバおよび右隣接サーバの両サーバについて、識別子空間管理情報１００（図５）を参照し、担当領域の広さを比較する。
図１２（ｂ）に示す例においては、データ損失処理部１１４は、損失領域の左隣接サーバであるサーバ「５」の担当領域と、損失領域の右隣接サーバであるサーバ「８」の担当領域とを比較する。
【００８４】
そして、左隣接サーバの担当領域の広さが右隣接サーバの担当領域の広さより大きい場合は（ステップＳ３２→Ｙｅｓ）、ステップＳ３３において、データ損失処理部１１４は、より担当領域が小さい右隣接サーバを新規担当サーバとして決定し、損失データ管理情報１５０と識別子空間管理情報１００とを更新する。具体的には、データ損失処理部１１４は、損失データ管理情報１５０の新規担当サーバ１５３に、決定した右隣接サーバのアドレスを格納する（図６（ｂ）参照）。また、識別子管理部１１３は、損失領域を右隣接サーバが担当するように、識別子空間管理情報１００を更新する。
図１２（ｃ）に示す例においては、データ損失処理部１１４は、左隣接サーバであるサーバ「５」の担当領域の広さが、右隣接サーバであるサーバ「８」の担当領域の広さより大きいため、より担当領域が小さい右隣接サーバのサーバ「８」を新規担当サーバとして決定する。また、識別子管理部１１３は、損失領域をサーバ「８」が担当するように、識別子空間管理情報１００を更新する。
【００８５】
一方、右隣接サーバの担当領域の広さが左隣接サーバの担当領域の広さ以上の場合は（ステップＳ３２→Ｎｏ）、ステップＳ３４において、データ損失処理部１１４は、より担当領域が小さい左隣接サーバを新規担当サーバとして決定し、損失データ管理情報１５０と識別子空間管理情報１００とを更新する。具体的には、データ損失処理部１１４は、損失データ管理情報１５０の新規担当サーバ１５３に、決定した左隣接サーバのアドレスを格納する（図６（ｂ）参照）。また、識別子管理部１１３は、損失領域を左隣接サーバが担当するように、識別子空間管理情報１００を更新する。
なお、この識別子空間管理情報１００の更新の際に、識別子管理部１１３は、新規担当サーバとして決定した左隣接サーバのサーバ識別子１０２（図５参照）を、損失領域の終了識別子の値（ハッシュ値）に変更する。図１２（ｃ）の例において、仮に、担当領域が左隣接サーバの方が小さく、損失領域を左隣接サーバのサーバ「５」が担当するとした場合には、サーバ「５」のサーバ識別子１０２は、損失領域の終了識別子の値となる離脱したサーバ「６」のサーバ識別子１０２の値（ハッシュ値）に変更される。
【００８６】
なお、ステップＳ３２においては、左隣接サーバの担当領域の広さが右隣接サーバの担当領域の広さより大きいか否かを判定するものとし、左隣接サーバの担当領域の広さと、右隣接サーバの担当領域の広さが等しい場合には、ステップＳ３４において左隣接サーバが新規担当サーバとして決定されるものとして説明した。しかしながら、データ損失処理部１１４は、左隣接サーバの担当領域の広さと、右隣接サーバの担当領域の広さが等しい場合に、予め左右どちらかの隣接サーバに決めておいた側の隣接サーバを新規担当サーバに決定するようにしてもよいし、ランダムに決定するようにしてもよい。
【００８７】
続いて、データ損失処理部１１４は、損失データ管理情報１５０の新規担当サーバ１５３に空欄があるか否かを判定する（ステップＳ３５）。
そして、データ損失処理部１１４は、新規担当サーバ１５３に空欄がある場合には（ステップＳ３５→Ｙｅｓ）、ステップＳ３０に戻り処理を続ける。一方、データ損失処理部１１４は、新規担当サーバ１５３に空欄がない場合には（ステップＳ３５→Ｎｏ）、新規担当サーバの決定処理を終了し、図９のステップＳ４の処理に進む。
【００８８】
以上説明したように、本実施形態に係る分散処理システム１は、原本データと全ての複製データとが失われたデータである損失データのみを復旧対象とした上で、残存するサーバのうち、損失領域を担当していた離脱サーバの右隣接サーバ若しくは左隣接サーバのうち、担当領域が小さい方のサーバを損失領域の新規担当サーバとして決定する。これにより、分散処理システム１は、損失データのみを復旧させることができると共に、その損失データのデータ復旧時において、サーバ負荷の偏りを低減させることができる。
【符号の説明】
【００８９】
１      分散処理システム
２      クライアント
１０    負荷分散装置
１１，２１，３１  制御部
１２，２２，３２  入出力部
１３，２３，３３  記憶部
２０    サーバ
３０    外部バックアップ装置
１００  識別子空間管理情報
１１１，２１１，３１１  情報受信部
１１２  振り分け処理部
１１３  識別子管理部
１１４  データ損失処理部
１１５，２１７，３１３  情報送信部
１５０  損失データ管理情報
２００  データ
２１２  メッセージ処理部
２１３  識別子空間管理情報登録部
２１４  冗長化処理部
２１５  バックアップ処理部
２１６  リストア処理部
３００  バックアップデータ情報
３１２  バックアップデータ管理部
【図１】
0005945252.tif 000002
【図２】
0005945252.tif 000003
【図３】
0005945252.tif 000004
【図４】
0005945252.tif 000005
【図５】
0005945252.tif 000006
【図６】
0005945252.tif 000007
【図７】
0005945252.tif 000008
【図８】
0005945252.tif 000009
【図９】
0005945252.tif 000010
【図１０】
0005945252.tif 000011
【図１１】
0005945252.tif 000012
【図１２】
0005945252.tif 000013