(57)【特許請求の範囲】
【請求項１】
環状のＩＤ（IDentifier）空間に、管理対象の複数のデータ、および、前記データを管理する複数のノード、が割り振られ、前記データのオリジナルであるオーナデータが、前記ＩＤ空間において前記オーナデータから所定方向回りに移動して最初に当たった前記ノードによって記憶される分散処理システムにおいて、クライアントマシンからのリクエストを前記複数のノードのいずれに振り分けるかを決定する管理装置であって、
物理的な地域の同一障害範囲であるＡＧ（Availability Group）の数をＮとした場合、
前記ＩＤ空間における前記ノードの位置を管理するＩＤ空間管理情報、および、前記ノードとそのノードが所属する前記ＡＧとの対応を管理するノード管理情報、を記憶する記憶部と、
前記ＩＤ空間をＮ×（Ｎ−１）個に均等分割し、当該ＩＤ空間に、複数のＡＧそれぞれを（Ｎ−１）個ずつ、隣り合う２つのＡＧの組み合わせおよび順番がすべて異なるように、配置し、
前記ＩＤ空間管理情報、および、前記ノード管理情報を用いて、前記オーナデータの複製であるバディデータを、前記ＩＤ空間において前記オーナデータから前記所定方向回りの次のＡＧに所属するノードのいずれかに記憶させる処理部と、
を有することを特徴とする管理装置。
【請求項２】
前記処理部は、
前記クライアントマシンからのリクエストがあった場合、所定のハッシュ関数に基いて算出したハッシュ値を用いて、前記オーナデータの前記ＩＤ空間における位置を決定し、前記ＩＤ空間において当該位置から所定方向回りに移動して最初に当たった前記ノードを、前記オーナデータを記憶するノードと決定するとともに、
前記ＩＤ空間において、
（１）前記ハッシュ値を前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノード、または、
（２）前記オーナデータを記憶するノードを前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノード、
のいずれかを、前記バディデータを記憶するノードと決定する
ことを特徴とする請求項１に記載の管理装置。
【請求項３】
前記処理部は、
前記オーナデータを記憶するノードが故障した場合、
前記記憶部に、前記ＩＤ空間における当該ノードに対応するＩＤに故障状態である旨を対応付けて記憶させ、
前記クライアントマシンからのリクエストがあって、前記所定のハッシュ関数に基いて算出したハッシュ値を用いて、前記ＩＤ空間において所定方向回りに移動して最初に当たった前記ノードが前記故障状態のノードであった場合、
当該オーナデータに対応するバディデータを記憶するノードに、当該リクエストへの対応を指示する
ことを特徴とする請求項２に記載の管理装置。
【請求項４】
前記処理部は、
前記クライアントマシンからのリクエストがあって、前記所定のハッシュ関数に基いて算出したハッシュ値を用いて、前記ＩＤ空間において所定方向回りに移動して最初に当たった前記ノードが前記故障状態のノードであった場合、
（１ａ）  前記（１）のときは、当該ハッシュ値を前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノードを、
（２ａ）  前記（２）のときは、当該故障状態のノードを前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノードを、
前記バディデータを記憶するノードとして特定し、
当該ノードに、当該リクエストへの対応を指示する
ことを特徴とする請求項３に記載の管理装置。
【請求項５】
前記処理部は、
前記故障状態のノードに代わって新たに他のノードを導入する復旧を行う場合、
（１ｂ）  前記（１ａ）のときは、前記ＩＤ空間における復旧対象のハッシュ値の範囲を前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して当たったすべてのノードに、前記他のノードへのデータ移行を指示し、
（２ｂ）  前記（２ａ）のときは、前記ＩＤ空間における前記他のノードの位置から前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノードに、前記他のノードへのデータ移行を指示する
ことを特徴とする請求項４に記載の管理装置。
【請求項６】
コンピュータを請求項１から請求項５までのいずれか一項に記載の管理装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、協調してデータ処理を行うクラスタを構成する複数のノードを管理する管理装置に関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングの隆盛に伴い、多量のデータの処理や保持を効率的に行うことが求められている。そこで、複数のノードを協調動作させることにより効率的な処理を実現する分散処理技術が発展している。ここで、ノードとは、例えば、物理サーバや、物理サーバに仮想的に割り当てられる仮想ノード（論理サーバ）を指す。
【０００３】
分散処理を行う際には、管理対象のデータを、クラスタを構成する各ノードに振り分けておく必要がある。このとき、クラスタ全体での処理能力を高めるためには、各ノードが担当するデータ数（データ量）は平均化されていることが望ましい。
【０００４】
代表的なデータの振り分け手法として、各データのｋｅｙを所定のハッシュ関数にかけた値（以下、「ｈａｓｈ（ｋｅｙ）」または「ハッシュ値」と称する。）をノード数Ｎで割った余り、すなわち「ｈａｓｈ（ｋｅｙ）  ｍｏｄ  Ｎ」を番号として持つノードにデータを振り分ける手法がある。この場合、各ノードに事前に「０」から「Ｎ−１」までの番号を割り当てていることが前提となる。このような振り分け手法を用いた場合、ノードを追加すると、Ｎの値が変化して、多くのデータについて、担当するノードが変更になるため、担当するデータの再配置が必要になる。
【０００５】
そこで、ノードの追加に伴い担当するノードが変更になるデータ数を約１／Ｎに抑える方法として、コンシステント・ハッシュ法（Consistent Hashing）を用いた振り分け手法がある。
【０００６】
このコンシステント・ハッシュ法を用いたデータ振り分け手法では、ノードとデータの双方にＩＤ（IDentifier）を割り当て、データのＩＤからＩＤ空間を時計回りに移動して最初に当たったノードをそのデータの担当とする。
【０００７】
また、多量のデータの管理をクラスタ構成の分散処理システムで行う場合、あるノードに障害が発生した場合でも他のノードで処理を継続できるように、データの複製を保持することでデータ冗長化を実現する必要がある。これは、コンシステント・ハッシュ法によるデータ管理手法を用いた分散処理システムにおいても同様である。
【０００８】
図１０に示すように、コンシステント・ハッシュ法では、ノード（ノード１〜４）とデータ（データＡ〜Ｄ。黒丸で表示）の双方にＩＤを割り当て、データのＩＤからＩＤ空間を時計回りに移動して最初に当たったノードをそのデータの担当として決定する。
【０００９】
そして、例えば、担当するノードのさらに右隣（時計回りに次）のノードに複製データを担当させる。図１０の例では、データＡはＩＤ空間上を時計回りに移動して最初に当たったノード１が担当となり、その複製データはＩＤ空間上でノード１の右隣にあたるノード２に担当させる。このように原本データ・複製データを担当するノードを決定することで、ノードに離脱があった場合でもその複製データを所持しているノードが新しくデータを担当するノードとなることで対応できるという利点がある。なお、複製データを複数作る場合には、さらに右隣のノードに２個目の複製データを担当させるようにすることもできる。
【００１０】
また、激甚災害（大地震等）が発生し、複数のノードが同時にダウン（故障）した場合でも、原本データおよび複製データの両方が消失してしまわないようにしておくことが重要である。ここで、激甚災害対策で、物理的な地域の同一障害範囲であるＡＧ（Availability Group）を考慮した従来の複製先決定方式（特許文献１）について、図１１を参照して説明する。
【００１１】
図１１（ａ）では、複数のノードが全国に跨ってＫ箇所（ここでは５箇所）のＡＧ（拠点）のいずれかに属している場合について考える。なお、図１１のＩＤ空間では、記号（黒丸、白丸、黒四角、白四角、白三角）が同じノードは、同じＡＧに属しているものとする。
【００１２】
図１１（ａ）に示すように、複製データは、原本データを保持するノードのＡＧと異なるＡＧのノードに配置されるように、その配置先（挿入先）を決定する。
具体的には、まず、Ｓ１１１において、最も振り分けＩＤ（担当ノードのＩＤ）数の合計値の小さいＡＧからノードを選択する。
次に、Ｓ１１２において、所定のＩＤ割り当て方法に基いて、そのノードの挿入先を選択する。
【００１３】
そして、Ｓ１１３において、冗長数（原本データと複製データの合計数）をＭ（例えばＭ＝３）とした場合、その挿入先の左右（Ｍ−１）個のノードの属するＡＧを確認し、条件を満たすか（挿入しようとしているノードのＡＧと異なるか）をチェックし、条件を満たせば、その挿入先にそのノードを挿入する。
【００１４】
このようにすれば、激甚災害が発生したときでも、原本データおよび複製データの両方が消失してしまう可能性をある程度低減できる。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２０１３−１８２５４６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかし、前記した従来の手法では、個別のノードの離脱があると、同じＡＧの２つのノードが隣り合う場面が生じ、その場合、左側のノードの複製データは、時計回りに次のノードではなく、さらにその次以降の他のＡＧのノードに記憶させる必要が生じ、処理コストが増えるという問題がある。また、ノードの配置状態によっては、複製データの偏りが発生するという問題もある。例えば、図１１（ｂ）に示すように、ノードＡ、Ｂ、ＣのＡＧが同一である場合、ノードＡ、Ｂ、Ｃのいずれの複製データも、ノードＣの右側のノード（白三角のノード）に記憶させる必要がある。
【００１７】
また、図１１（ｂ）の例でノードＡの通常（激甚災害以外）の故障減設が起きたときは、図１１（ｃ）に示すように、本来、ノードＡが対応すべきＸに関連するリクエストがノードＢに来ることになるが、ノードＢは、複製データを保持していないため、ノードＣの右側のノード（白三角のノード）から複製データを送信してもらうこと（グラビテーション）が必要になるなど、データ複製に関する処理コストが増えてしまうという問題もある。
【００１８】
そこで、本発明は、前記した事情に鑑みてなされたものであり、分散処理システムにおいて、激甚災害対策にＡＧを考慮しつつ、処理コストが低く、かつ、複製データの偏りが少ない手法を提供することを課題とする。
【課題を解決するための手段】
【００１９】
前記課題を解決するために、本発明は、環状のＩＤ空間に、管理対象の複数のデータ、および、前記データを管理する複数のノード、が割り振られ、前記データのオリジナルであるオーナデータが、前記ＩＤ空間において前記オーナデータから所定方向回りに移動して最初に当たった前記ノードによって記憶される分散処理システムにおいて、クライアントマシンからのリクエストを前記複数のノードのいずれに振り分けるかを決定する管理装置であって、物理的な地域の同一障害範囲であるＡＧの数をＮとした場合、前記ＩＤ空間における前記ノードの位置を管理するＩＤ空間管理情報、および、前記ノードとそのノードが所属する前記ＡＧとの対応を管理するノード管理情報、を記憶する記憶部と、前記ＩＤ空間をＮ×（Ｎ−１）個に均等分割し、当該ＩＤ空間に、複数のＡＧそれぞれを（Ｎ−１）個ずつ、隣り合う２つのＡＧの組み合わせおよび順番がすべて異なるように、配置し、前記ＩＤ空間管理情報、および、前記ノード管理情報を用いて、前記オーナデータの複製であるバディデータを、前記ＩＤ空間において前記オーナデータから前記所定方向回りの次のＡＧに所属するノードのいずれかに記憶させる処理部と、を有する。
【００２０】
これによれば、ＩＤ空間をＮ×（Ｎ−１）個に均等分割し、当該ＩＤ空間に、複数のＡＧそれぞれを（Ｎ−１）個ずつ、隣り合う２つのＡＧの組み合わせおよび順番がすべて異なるように、配置することで、激甚災害対策にＡＧを考慮しつつ、処理コストが低く、かつ、複製データの偏りが少ない分散処理システムを実現できる。
【００２１】
また、本発明は、前記処理部が、前記クライアントマシンからのリクエストがあった場合、所定のハッシュ関数に基いて算出したハッシュ値を用いて、前記オーナデータの前記ＩＤ空間における位置を決定し、前記ＩＤ空間において当該位置から所定方向回りに移動して最初に当たった前記ノードを、前記オーナデータを記憶するノードと決定するとともに、前記ＩＤ空間において、（１）前記ハッシュ値を前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノード、または、（２）前記オーナデータを記憶するノードを前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノード、のいずれかを、前記バディデータを記憶するノードと決定することが好ましい。
【００２２】
これによれば、ＩＤ空間における各ＡＧ領域（３６０度／｛Ｎ×（Ｎ−１）｝分の領域）のバディデータを、所定方向回りに隣のＡＧに均等に配置できる。
【００２３】
また、本発明は、前記処理部が、前記オーナデータを記憶するノードが故障した場合、前記記憶部に、前記ＩＤ空間における当該ノードに対応するＩＤに故障状態である旨を対応付けて記憶させ、前記クライアントマシンからのリクエストがあって、前記所定のハッシュ関数に基いて算出したハッシュ値を用いて、前記ＩＤ空間において所定方向回りに移動して最初に当たった前記ノードが前記故障状態のノードであった場合、当該オーナデータに対応するバディデータを記憶するノードに、当該リクエストへの対応を指示することが好ましい。
【００２４】
これによれば、ノードの故障減設時に、グラビテーション不要で対応できる。
【００２５】
また、本発明は、前記処理部が、前記クライアントマシンからのリクエストがあって、前記所定のハッシュ関数に基いて算出したハッシュ値を用いて、前記ＩＤ空間において所定方向回りに移動して最初に当たった前記ノードが前記故障状態のノードであった場合、（１ａ）前記（１）のときは、当該ハッシュ値を前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノードを、（２ａ）前記（２）のときは、当該故障状態のノードを前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノードを、前記バディデータを記憶するノードとして特定し、当該ノードに、当該リクエストへの対応を指示することが好ましい。
【００２６】
これによれば、ノードの故障時に、シンプルな処理で、バディデータを記憶するノードを特定し、対応できる。
【００２７】
また、本発明は、前記処理部が、前記故障状態のノードに代わって新たに他のノードを導入する復旧を行う場合、（１ｂ）前記（１ａ）のときは、前記ＩＤ空間における復旧対象のハッシュ値の範囲を前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して当たったすべてのノードに、前記他のノードへのデータ移行を指示し、（２ｂ）前記（２ａ）のときは、前記ＩＤ空間における前記他のノードの位置から前記所定方向回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした位置から前記所定方向回りに移動して最初に当たったノードに、前記他のノードへのデータ移行を指示することが、好ましい。
【００２８】
これによれば、ノードの復旧時に、シンプルな処理で、バディデータを新ノードに移行できる。
【００２９】
また、本発明は、コンピュータを前記管理装置として機能させるためのプログラムである。
【００３０】
これによれば、このようなプログラムを実装したコンピュータを前記管理装置として機能させることができる。
【発明の効果】
【００３１】
本発明によれば、分散処理システムにおいて、激甚災害対策にＡＧを考慮しつつ、処理コストが低く、かつ、複製データの偏りが少ない手法を提供することができる。
【図面の簡単な説明】
【００３２】
【図１】本実施形態の分散処理システムの構成図である。
【図２】本実施形態のＩＤ空間管理情報の構成図である。
【図３】本実施形態のＡＧ情報の構成図である。
【図４】本実施形態のノード管理情報の構成図である。
【図５】本実施形態のＩＤ空間におけるＡＧの配置などを示す図である。
【図６】本実施形態のＩＤ空間を用いた第１のデータ配置方法の説明図である。
【図７】本実施形態のＩＤ空間を用いた第２のデータ配置方法の説明図である。
【図８】本実施形態のＩＤ空間を用いた故障処理の説明図である。
【図９】本実施形態のＩＤ空間を用いた復旧処理の説明図である。
【図１０】従来のコンシステント・ハッシュ法の説明図である。
【図１１】従来のコンシステント・ハッシュ法における問題の説明図である。
【発明を実施するための形態】
【００３３】
以下、本発明を実施するための形態（以下、実施形態と称する。）について、図面を参照（言及図以外の図も適宜参照）しながら説明する。図１に示すように、本実施形態の分散処理システム１０００は、負荷分散装置３、管理装置４、クラスタ１００を構成する複数のノード５を備えている。負荷分散装置３は、インターネット等のネットワーク２を介して、複数のクライアントマシン１と接続されている。
【００３４】
分散処理システム１０００の全体の主な動作について説明すると、まず、クライアントマシン１からのデータ処理リクエストを、ネットワーク２経由で負荷分散装置３が受け取る。負荷分散装置３は、ＩＤ空間管理情報４１１（図２参照）に基いて、そのリクエストを、データ処理を行う複数のノード５のいずれかに振り分ける。振り分けられたノード５は、そのリクエストの処理を行う。
【００３５】
なお、ノード５は、本実施形態では、物理サーバに仮想的に割り当てられる仮想ノード（論理サーバ）である。１つの物理サーバにより、１つ以上のノード５が実現され、ノード５は仮想ＩＤを用いて管理される。
【００３６】
次に、負荷分散装置３と管理装置４の構成について説明する。
負荷分散装置３は、記憶部３１、処理部３２、通信部３３を備える。
記憶部３１は、情報を記憶する手段であり、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）などのメモリ、ＨＤＤ（Hard Disk Drive）などによって構成される。記憶部３１には、管理装置４から受信したＩＤ空間管理情報４１１が、ＩＤ空間管理情報３１１として格納されている。なお、記憶部３１には、処理部３２の動作プログラムなども格納されている（図示を省略）。
【００３７】
処理部３２は、記憶部３１に格納された情報に基いて演算処理を行う手段であり、例えばＣＰＵ（Central Processing Unit）によって構成される。
【００３８】
通信部３３は、外部装置との通信に用いられる通信インタフェースである。
なお、負荷分散装置３は、ほかに、負荷分散装置３のユーザが情報を入力する入力部や、情報を表示する表示部などを備えていてもよい。
【００３９】
管理装置４は、コンシステント・ハッシュ法に基いて、クライアントマシン１からのリクエストを複数のノード５（以下、符号を省略して単に「ノード」と称する場合もある。）のいずれに振り分けるかを決定するコンピュータ装置である。なお、前記したように、このコンシステント・ハッシュ法では、環状のＩＤ空間に、管理対象の複数のデータ、および、データを管理しクラスタ１００を構成する複数のノード５、が割り振られ、データは、ＩＤ空間を自身から時計回り（所定方向回り）に移動して最初に当たったノード５に担当（記憶、管理）される。また、以下では、データのオリジナルをオーナデータと称する場合があり、また、オーナデータの複製をバディデータと称する場合がある。
【００４０】
管理装置４は、記憶部４１、処理部４２、入力部４３、表示部４４、通信部４５を備える。
記憶部４１は、情報を記憶する手段であり、ＲＡＭやＲＯＭなどのメモリ、ＨＤＤなどによって構成される。記憶部４１には、ＩＤ空間管理情報４１１、ＡＧ情報４１２、ノード管理情報４１３が格納されている。なお、記憶部４１には、処理部４２の動作プログラムなども格納されている（図示を省略）。
【００４１】
ＩＤ空間管理情報４１１は、管理対象のデータについて所定のハッシュ関数を用いて算出されたハッシュ値（ＩＤ）を用いて、そのデータを担当するノード５を管理する情報である（図２で後記）。
【００４２】
ＡＧ情報４１２は、ＡＧと、そのＡＧに対応する地域名との対応付けを管理する情報である（図３で後記）。
【００４３】
ノード管理情報４１３は、ＡＧごとに、当該地域に存在する物理サーバにより実現されるすべてのノード５との対応付けを管理する情報である（図４で後記）。
【００４４】
処理部４２は、記憶部４１に格納された情報に基いて演算処理を行う手段であり、例えばＣＰＵによって構成される（処理内容の詳細は後記）。
入力部４３は、管理装置４のユーザが情報を入力する手段であり、例えば、キーボードやマウスによって実現される。
表示部４４は、情報を表示する手段であり、例えば、ＬＣＤ（Liquid Crystal Display）によって実現される。
通信部４５は、外部装置との通信に用いられる通信インタフェースである。
【００４５】
次に、ＩＤ空間管理情報４１１について説明する。図２に示すように、ＩＤ空間管理情報４１１は、「ＩＤ」、「ノード」の各カラムから構成され、ＩＤの値の大きさでソートされている。
「ＩＤ」は、ＩＤ空間におけるＩＤであり、各ノード５が管理を担当するデータの領域を特定するために格納される。
【００４６】
「ノード」は、クラスタ１００を構成するノード５の識別子を表す。例えば、図２に示す、第１行目のＩＤの値が「００５６」の場合は、識別子が「００００」〜「００５６」の領域に属するデータを「ノード＃」が担当することを示す。また、第２行目のＩＤの値が「０１７２」の場合は、１つ前の行のＩＤの値に１をプラスした「００５７」〜「０１７２」の識別子に属するデータを「ノード※」が担当することを示す。
【００４７】
次に、ＡＧ情報４１２について説明する。図３に示すように、ＡＧ情報４１２は、「ＡＧ」、「地域名」の各カラムから構成される。
「ＡＧ」は、所定の複数の物理的な地域（ＡＧ）の識別子を表す。
「地域名」は、その行のＡＧに対応する地域の名称を表す。
【００４８】
次に、ノード管理情報４１３について説明する。図４に示すように、ノード管理情報４１３は、「ＡＧ」、「ノード」の各カラムから構成される。
「ＡＧ」は、所定の複数の物理的な地域（ＡＧ）の識別子を表す。
「ノード」は、対応するＡＧの地域に存在する物理サーバによって実現されるノード５の識別子を表す。
【００４９】
次に、管理装置４による処理内容について説明する。なお、以下の処理は、管理装置４の処理部４２が記憶部４１の各情報を参照しながら行う。図５（ａ）に示すように、まず、ＡＧの数をＮとした場合、ＩＤ空間をＮ×（Ｎ−１）個に均等分割する。以下では、Ｎ＝４の場合を例にとって説明するが、その場合、分割数は４×（４−１）＝１２である。
【００５０】
そして、その分割したＩＤ空間に、複数のＡＧ（「１」、「２」、「３」、「４」）それぞれを３個（（Ｎ−１）個）ずつ、隣り合う２つのＡＧの組み合わせおよび順番がすべて異なるように、配置する。ここで、「Ａ」〜「Ｌ」は各ＡＧ領域（ＡＧのサブ領域）を表す。ＡＧ領域「Ａ」、「Ｅ」、「Ｊ」は、ＡＧが「１」である。ＡＧ領域「Ｂ」、「Ｇ」、「Ｉ」は、ＡＧが「２」である。ＡＧ領域「Ｃ」、「Ｆ」、「Ｌ」は、ＡＧが「３」である。ＡＧ領域「Ｄ」、「Ｈ」、「Ｋ」は、ＡＧが「４」である。
【００５１】
ＡＧ領域「Ａ」〜「Ｌ」のＡＧは、順に「１」、「２」、「３」、「４」、「１」、「３」、「２」、「４」、「２」、「１」、「４」、「３」である。したがって、隣り合う２つのＡＧの組み合わせおよび順番は、ＡＧ領域「Ａ」と「Ｂ」から順に、「１」と「２」、「２」と「３」、「３」と「４」、「４」と「１」、「１」と「３」、「３」と「２」、「２」と「４」、「４」と「２」、「２」と「１」、「１」と「４」、「４」と「３」、「３」と「１」となっており、すべて異なっている。これによって、オーナ（オーナデータを記憶するノード）とバディ（バディデータを記憶するノード）の組み合わせを均等に分散し、ＡＧごとやノードごとの扱うデータ量の均等化を図ることができる。
【００５２】
次に、図５（ｂ）に示すように、ＡＧ「１」を例にとると、ＡＧ「１」の各ＡＧ領域「Ａ」、「Ｅ」、「Ｊ」に、物理サーバの数（ここでは「３」とする。サーバ＃１〜＃３）の分、振り分けＩＤ（担当ノードのＩＤ）を付与する。つまり、ＡＧ「１」への振り分けＩＤの総数は、（Ｎ−１）×物理サーバ数であり、この例では（４−１）×３＝９である。その際、ＡＧ領域「Ａ」、「Ｅ」、「Ｊ」のそれぞれに、３つずつの振り分けＩＤを付与することで、ノードごとの扱うデータ量の均等化を図ることができる。また、各ＡＧ領域の右端には、必ず振り分けＩＤを配置するものとする。オーナとバディが隣り合うＡＧに所属することを保証するためである（詳細は後記）。
【００５３】
また、各ＡＧ領域における振り分けＩＤの担当領域が均等になるように配置する。これにより、ノードごとの扱うデータ量の均等化を図ることができる。
【００５４】
次に、図５（ｃ）に示すように、ＡＧ「２」を例にとると、ＡＧ「２」の各ＡＧ領域「Ｂ」、「Ｇ」、「Ｉ」に、物理サーバの数（ここでは「２」とする）の分、振り分けＩＤを付与する。つまり、振り分けＩＤの総数は、（４−１）×２＝６である。その際、ＡＧ領域「Ｂ」、「Ｇ」、「Ｉ」のそれぞれに、２つずつの振り分けＩＤを付与することで、ノードごとの扱うデータ量の均等化を図ることができる。また、各ＡＧ領域の右端には、必ず振り分けＩＤを配置する。また、各ＡＧ領域における振り分けＩＤの担当領域が均等になるように配置する。
【００５５】
次に、第１のデータ配置方法について説明する。図６（ａ）に示すように、オーナデータは、ハッシュ関数に基いて算出されたハッシュ値（Ｓ６０１）を元に、ＩＤ空間を時計回りに移動して最初に当たった（右方向探索により特定した）振り分けＩＤ（のノード）に担当させる（Ｓ６０２）。
【００５６】
また、図６（ｂ）に示すように、バディデータは、ハッシュ関数に基いて算出されたハッシュ値（Ｓ６１１）を元に、ＩＤ空間を時計回りに３６０度／｛Ｎ×（Ｎ−１）｝（＝３０度）ずらした（Ｓ６１２）位置から右方向探索により特定した振り分けＩＤに担当させる（Ｓ６１３）。
【００５７】
これにより、各ＡＧ領域のバディデータを右隣のＡＧの振り分けＩＤに均等に配置することができる。また、一律的でシンプルな処理により、バディとして、オーナのＡＧと異なるＡＧのノードを特定できる。また、ＡＧごとのバディの選定頻度を均等にすることができる。
【００５８】
次に、第２のデータ配置方法について説明する。図７（ａ）に示すように、オーナデータは、ハッシュ関数に基いて算出されたハッシュ値（Ｓ７０１）を元に、右方向探索により特定した振り分けＩＤに担当させる（Ｓ７０２）。
【００５９】
また、図７（ｂ）に示すように、バディデータは、ハッシュ関数に基いて算出されたハッシュ値（Ｓ７１１）を元に、まず、右方向探索により振り分けＩＤ（オーナデータの振り分けＩＤ）を特定し（Ｓ７１２）、その後、バディデータは、その特定した振り分けＩＤから時計回りに３６０度／｛Ｎ×（Ｎ−１）｝（＝３０度）ずらした位置（Ｓ７１３）から右方向探索により特定した振り分けＩＤに担当させる（Ｓ７１４）。
【００６０】
これにより、一律的でシンプルな処理により、バディとして、オーナのＡＧと異なるＡＧのノードを特定できる。また、ＡＧごとのバディの選定頻度を均等にすることができる。また、オーナとバディを１対１で対応させることができ、バディごとの扱うデータ量をさらに均等化させることができる。
【００６１】
次に、第１のデータ配置方法を採用した場合の故障処理について説明する。図８（ａ）に示すように、ここでは、ＡＧ領域「Ａ」の左端の振り分けＩＤに対応するノードが故障したものとする。また、故障減設は行わず、ＩＤ空間における当該ノードに対応する振り分けＩＤに故障状態である旨を対応付ける。
【００６２】
まず、ハッシュ関数に基いて算出されたハッシュ値（Ｓ８０１）を元に、右方向探索により振り分けＩＤを特定するも故障を検出する（Ｓ８０２）。その場合、そのハッシュ値を時計回りに３６０度／｛Ｎ×（Ｎ−１）｝（＝３０度）ずらした（Ｓ８０３）位置から右方向探索により振り分けＩＤ（バディの振り分けＩＤ）を特定し（Ｓ８０４）、そのバディを切替え先に決定する。
【００６３】
これにより、ノードの故障に、一律的でシンプルな処理によりバディを特定でき、グラビテーションなどの余計な処理コストの発生を抑止できる。
なお、図８（ａ）のＡＧ領域「Ｅ」、「Ｆ」に示すように、ＡＧ領域ごとのノード数が異なる場合（ＡＧ領域「Ｅ」のノード数は「３」、ＡＧ領域「Ｆ」のノード数は「２」）、ＡＧ領域「Ｅ」の振り分けＩＤ「２」の故障が検出されたとき、ＡＧ領域「Ｆ」の振り分けＩＤ「４」と振り分けＩＤ「５」に分割して切り替えられる。
【００６４】
次に、第２のデータ配置方法を採用した場合の故障処理について説明する。図８（ｂ）に示すように、図８（ａ）と同様、ＡＧ領域「Ａ」の左端の振り分けＩＤに対応するノードが故障したものとする。また、故障減設は行わず、ＩＤ空間における当該ノードに対応する振り分けＩＤに故障状態である旨を対応付ける。
【００６５】
まず、ハッシュ関数に基いて算出されたハッシュ値（Ｓ８１１）を元に、右方向探索により振り分けＩＤを特定するも故障を検出する（Ｓ８１２）。その場合、その振り分けＩＤから時計回りに３６０度／｛Ｎ×（Ｎ−１）｝（＝３０度）ずらした（Ｓ８１３）位置から右方向探索により振り分けＩＤ（バディ）を特定し（Ｓ８１４）、そのバディを切替え先に決定する。
【００６６】
これにより、ノードの故障に、一律的でシンプルな処理によりバディを特定でき、グラビテーションなどの余計な処理コストの発生を抑止できる。
なお、図８（ｂ）のＡＧ領域「Ｅ」、「Ｆ」に示すように、ＡＧ領域ごとのノード数が異なる場合（ＡＧ領域「Ｅ」のノード数は「３」、ＡＧ領域「Ｆ」のノード数は「２」）、ＡＧ領域「Ｅ」の振り分けＩＤ「２」の故障が検出されたとき、ＡＧ領域「Ｆ」の振り分けＩＤ「５」に切り替えられる。
【００６７】
次に、第１のデータ配置方法を採用した場合の復旧処理について説明する。ここでは、故障ノードの代替ノード（ＡＧが故障ノードと同じノード）の準備ができたものとする。図９（ａ）に示すように、復旧対象ハッシュ値の範囲（Ｓ９０１）を時計回りに３６０度／｛Ｎ×（Ｎ−１）｝ずらした（Ｓ９０２）位置から右方向探索したところにあるすべての振り分けＩＤを特定し（Ｓ９０３）、その特定した振り分けＩＤのノード（バディ）に、代替ノードへのデータ移行を指示する。そのバディは、データ移行するデータをリストアップし、代替ノードへのデータ移行を実施する。また、データ移行の完了後、代替ノードを新オーナとして、その新オーナへのリクエストの振り分けを開始し、復旧を完了する。
【００６８】
これにより、ノードの復旧時に、シンプルな処理で、バディデータを新オーナに移行できる。
なお、図９（ａ）のＡＧ領域「Ｅ」、「Ｆ」に示すように、ＡＧ領域ごとのノード数が異なる場合（ＡＧ領域「Ｅ」のノード数は「３」、ＡＧ領域「Ｆ」のノード数は「２」）、ＡＧ領域「Ｅ」の振り分けＩＤ「２」のノードの復旧時、ＡＧ領域「Ｆ」の振り分けＩＤ「４」と振り分けＩＤ「５」のノードにデータ移行を指示する。その振り分けＩＤ「４」と振り分けＩＤ「５」のノードは、データ移行するデータをリストアップし、振り分けＩＤ「２」のノードへのデータ移行を実施する。
【００６９】
次に、第２のデータ配置方法を採用した場合の復旧処理について説明する。図９（ａ）と同様、故障ノードの代替ノード（ＡＧが故障ノードと同じノード）の準備ができたものとする。図９（ｂ）に示すように、代替ノードが保持する予定の振り分けＩＤ（Ｓ９０１）を時計回りに３６０度／｛Ｎ×（Ｎ−１）｝（＝３０度）ずらした（Ｓ９１２）位置から右方向探索して振り分けＩＤを特定し（Ｓ９１３）、その特定した振り分けＩＤのノード（バディ）に、代替ノードへのデータ移行を指示する。そのバディは、データ移行するデータをリストアップし、代替ノードへのデータ移行を実施する。また、データ移行の完了後、代替ノードを新オーナとして、その新オーナへのリクエストの振り分けを開始し、復旧を完了する。
【００７０】
これにより、ノードの復旧時に、シンプルな処理で、バディデータを新オーナに移行できる。
なお、図９（ｂ）のＡＧ領域「Ｅ」、「Ｆ」に示すように、ＡＧ領域ごとのノード数が異なる場合（ＡＧ領域「Ｅ」のノード数は「３」、ＡＧ領域「Ｆ」のノード数は「２」）、ＡＧ領域「Ｅ」の振り分けＩＤ「２」のノードの復旧時、ＡＧ領域「Ｆ」の振り分けＩＤ「５」のノードにデータ移行を指示する。その振り分けＩＤ「５」のノードは、データ移行するデータをリストアップし、振り分けＩＤ「２」のノードへのデータ移行を実施する。
【００７１】
このようにして、本実施形態の管理装置４によれば、ＩＤ空間をＮ×（Ｎ−１）個に均等分割し、当該ＩＤ空間に、複数のＡＧそれぞれを（Ｎ−１）個ずつ、隣り合う２つのＡＧの組み合わせおよび順番がすべて異なるように、配置することで、激甚災害対策にＡＧを考慮しつつ、処理コストが低く、かつ、複製データの偏りが少ない分散処理システム１０００を実現できる。
【００７２】
また、各ＡＧ領域（３６０度／｛Ｎ×（Ｎ−１）｝分の領域）のバディデータを、時計回り回りに隣のＡＧに均等に配置できる。
また、ノードの故障時に、グラビテーション不要で、シンプルな処理で、バディデータを記憶するノードを特定し、対応できる。
また、ノードの復旧時に、シンプルな処理で、バディデータを新ノードに移行できる。
【００７３】
以上で本実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
例えば、管理装置４と負荷分散装置３を同一のハードウエアに並存させる構成としてもよい。
【００７４】
また、図５（ｂ）の変形例として、ＡＧ領域「Ａ」、「Ｅ」、「Ｊ」に３つの物理サーバをそれぞれ１対１で対応させて、各ＡＧ領域に、対応する１つの物理サーバの３つの振り分けＩＤを付与するようにしてもよい。
また、ＩＤ空間を、Ｎ×（Ｎ−１）個に均等分割したが、（Ｎ×（Ｎ−１）の整数倍）個に均等分割して同様の処理を行うようにしてもよい。
【００７５】
また、本実施形態ではコンシステント・ハッシュ法を前提としたが、他の手法を前提としてもよい。
また、本発明は、コンピュータを管理装置４として機能させるためのプログラムとしても具現化可能である。
その他、具体的な構成や処理内容について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００７６】
１      クライアントマシン
２      ネットワーク
３      負荷分散装置
４      管理装置
５      ノード
３１    記憶部
３２    処理部
３３    通信部
４１    記憶部
４２    処理部
４３    入力部
４４    表示部
４５    通信部
１００  クラスタ
３１１  ＩＤ空間管理情報
４１１  ＩＤ空間管理情報
４１２  ＡＧ情報
４１３  ノード管理情報
１０００  分散処理システム
【図１】
0006053712.tif 000002
【図２】
0006053712.tif 000003
【図３】
0006053712.tif 000004
【図４】
0006053712.tif 000005
【図５】
0006053712.tif 000006
【図６】
0006053712.tif 000007
【図７】
0006053712.tif 000008
【図８】
0006053712.tif 000009
【図９】
0006053712.tif 000010
【図１０】
0006053712.tif 000011
【図１１】
0006053712.tif 000012