(57)【特許請求の範囲】
【請求項１】
環状のＩＤ（IDentifier）空間に、管理対象の複数のデータ、および、前記データを管理しクラスタを構成する複数のサーバ、が割り振られ、それぞれの前記サーバが、前記ＩＤ空間において自身から所定方向回りに次の前記サーバまでの間に位置する前記データを管理するとともに、当該次の前記サーバから前記所定方向回りにさらに次の前記サーバまでの間に位置する前記データの複製を記憶する分散処理システムにおいて、クライアントマシンからのリクエストを前記複数のサーバのいずれに振り分けるかを決定する管理装置であって、
前記ＩＤ空間における前記データの管理を担当するサーバを管理するＩＤ空間管理情報、
前記複数のサーバおよび待機中のサーバを含むサーバそれぞれは所定の３以上の複数の物理的な地域のいずれかに属しており、前記地域ごとに、当該地域に物理的に存在するすべての前記サーバとの対応付けを管理するサーバ管理情報、を記憶する記憶部と、
前記クラスタに対して前記待機中のサーバを増設する場合、当該増設するサーバについての前記ＩＤ空間における挿入位置に基づき、前記ＩＤ空間管理情報を参照して前記ＩＤ空間における当該挿入位置の両側の前記サーバを特定し、前記サーバ管理情報を参照して当該特定した前記両隣のサーバが属さない地域に物理的に存在するサーバを選択し、当該選択したサーバと当該挿入位置の情報を用いて前記ＩＤ空間管理情報を更新する処理部と、
を有することを特徴とする管理装置。
【請求項２】
環状のＩＤ（IDentifier）空間に、管理対象の複数のデータ、および、前記データを管理しクラスタを構成する複数のサーバ、が割り振られ、それぞれの前記サーバが、前記ＩＤ空間において自身から所定方向回りに次の前記サーバまでの間に位置する前記データを管理するとともに、当該次の前記サーバから前記所定方向回りにさらに次の前記サーバまでの間に位置する前記データの複製を記憶する分散処理システムにおいて、クライアントマシンからのリクエストを前記複数のサーバのいずれに振り分けるかを決定する管理装置であって、
前記ＩＤ空間における前記データの管理を担当するサーバを管理するＩＤ空間管理情報、
前記複数のサーバおよび待機中のサーバを含むサーバそれぞれは所定の３以上の複数の物理的な地域のいずれかに属しており、前記地域ごとに、当該地域に物理的に存在するすべての前記サーバとの対応付けを管理するサーバ管理情報、を記憶する記憶部と、
前記クラスタに対して前記待機中のサーバを増設する場合、当該増設するサーバについての前記ＩＤ空間における挿入位置に基づき、
前記地域の数をＫ（≧３）とした場合、
Ｋが奇数のとき、前記ＩＤ空間管理情報を参照して前記ＩＤ空間における当該挿入位置の両側それぞれについて｛（Ｋ−１）／２｝台の前記サーバを特定し、
Ｋが偶数のとき、前記ＩＤ空間管理情報を参照して前記ＩＤ空間における当該挿入位置の両側の一方について（Ｋ／２）台、他方について｛（Ｋ−２）／２｝台の前記サーバを特定し、
前記サーバ管理情報を参照して当該特定したすべてのサーバがいずれも属さない地域に物理的に存在するサーバを選択し、当該選択したサーバと当該挿入位置の情報を用いて前記ＩＤ空間管理情報を更新する処理部と、
を有することを特徴とする管理装置。
【請求項３】
前記処理部は、
前記クラスタに対して前記待機中のサーバを増設する場合、
前記ＩＤ空間管理情報を参照して前記ＩＤ空間において前記サーバ同士の間が最も広い箇所の中央の位置を前記挿入位置として特定する
ことを特徴とする請求項１または請求項２に記載の管理装置。
【請求項４】
コンピュータを請求項１から請求項３までのいずれか一項に記載の管理装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、協調してデータ処理を行うクラスタを構成する複数のサーバを管理する管理装置に関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングの隆盛に伴い、多量のデータの処理や保持を効率的に行うことが求められている。そこで、複数のサーバを協調動作させることにより効率的な処理を実現する分散処理技術が発展している。
【０００３】
分散処理を行う際には、処理対象（管理対象）のデータを、クラスタを構成する各サーバ（以下、「クラスタメンバ」または「メンバ」とも称する。）に振り分けておく必要がある。このとき、クラスタ全体での処理能力を高めるためには、各クラスタメンバが担当するデータ数（データ量）は平均化されていることが望ましい。
【０００４】
代表的なデータの振り分け手法として、各データのｋｅｙをハッシュ関数にかけた値（以下、「ｈａｓｈ（ｋｅｙ）」と称する。）をクラスタメンバ数Ｎで割った余り、すなわち「ｈａｓｈ（ｋｅｙ）  ｍｏｄ  Ｎ」を番号として持つクラスタメンバにデータを振り分ける手法がある。この場合、各クラスタメンバに事前に「０」から「Ｎ−１」までの番号を割り当てていることが前提となる。このような振り分け手法を用いた場合、クラスタメンバを追加すると、Ｎの値が変化して、多くのデータについて、担当するクラスタメンバが変更になるため、担当するデータの再配置が必要になる。
【０００５】
そこで、クラスタメンバの追加に伴い担当するクラスタメンバが変更になるデータ数を約１／Ｎに抑える方法として、コンシステント・ハッシュ法［Consistent Hashing］（非特許文献１参照）を用いた振り分け手法がある。
【０００６】
このコンシステント・ハッシュ法を用いたデータ振り分け手法では、クラスタメンバとデータの双方にＩＤ（IDentifier）を割り当て、データのＩＤからＩＤ空間を時計回りに辿った場合に最初に出合ったクラスタメンバをそのデータの担当とする。
【０００７】
また、多量のデータの管理をクラスタ構成の分散処理システムで行う場合、あるクラスタメンバに障害が発生した場合でも他のクラスタメンバで処理を継続できるように、データの複製を保持することでデータ冗長化を実現する必要がある。これは、コンシステント・ハッシュ法によるデータ管理手法を用いた分散処理システムにおいても同様である。
【０００８】
図７に示すように、コンシステント・ハッシュ法では、クラスタメンバ（メンバ１〜４）とデータ（データＡ〜Ｄ。黒丸で表示）の双方にＩＤを割り当て、データのＩＤからＩＤ空間を時計回りに辿り最初に出合ったクラスタメンバをそのデータの担当として決定する。そして、担当するクラスタメンバのさらに右隣（時計回りに次）のクラスタメンバに複製データを担当させる。
【０００９】
例えば、図７においては、データＡはＩＤ空間上を時計回りに辿り最初に出合ったメンバ１が担当となり、その複製データはＩＤ空間上でメンバ１の右隣にあたるメンバ２に担当させる。このように原本データ・複製データを担当するクラスタメンバを決定することで、クラスタメンバに離脱があった場合でもその複製データを所持しているクラスタメンバが新しくデータを担当するクラスタメンバとなることで対応できるという利点がある。なお、複製データを複数個とる場合には、さらに右隣のクラスタメンバに２個目の複製データを担当させるようにすることもできる。
【００１０】
なお、このような手法に使用できるデータベースサーバとしては、例えば、Ｃａｓｓａｎｄｒａ（非特許文献２）等に記載されている、複数サーバが動的にクラスタに参加・離脱可能できる分散データベースサーバがある。非特許文献２の技術では、コンシステント・ハッシュ法を用いたデータの均等な分散と、Ｏ（１）の高速アクセスを実現している。また、複製情報を複数のサーバに対して持たせることで、耐故障性を高めている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】David Karger et al., “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”, [online], 1997, ACM, [平成24年2月20日検索], インターネット<ＵＲＬ：http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf>
【非特許文献２】Avinash Lakshman et al., “Cassandra - A Decentralized Structured Storage System”, [online], [平成24年2月20日検索], インターネット<ＵＲＬ：http://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、前記した従来の手法では、激甚災害等が発生し、複数のサーバが同時にダウン（故障）した場合、原本データおよび複製データの両方を消失してしまう可能性がある。そうなると、復旧には、別途のバックアップデータ等による処理が必要になる。この処理は、通常、ディスクからの吸出し作業になるため低速であり、サービスの一時停止等の弊害は免れない。
【００１３】
よって、汎用サーバを複数台用いた分散処理システムにおいて、激甚災害等で大規模故障が発生した場合でも、データを消失することなく処理を継続できる可能性を高めるためのデータ複製方式について検討する。
【００１４】
例えば、関東をエリアとするデータセンタエリア（サーバを管理するデータセンタが管轄するエリア）のみに複数のサーバを配置した場合、関東全域に激甚災害等が発生すると、すべてのサーバがダウンし、すべてのデータが消失してしまう可能性がある。したがって、広域なエリアに複数のサーバを分散させておくことが、まず必要になる。
【００１５】
ここで、図８に示すように、複数のサーバが全国に跨ってＫ種類（ここでは５種類）のデータセンタエリアのいずれかに属している場合について考える。なお、図８のＩＤ空間では、記号（黒丸、白丸、黒三角、白三角、白四角）が同じサーバは、同じデータセンタエリアに属しているものとする。
【００１６】
この場合、関東全域に激甚災害等が発生しても、関東のデータセンタエリアに属するサーバはダウンするが、その他のデータセンタエリアに属するサーバはダウンしない。つまり、コンシステント・ハッシュ法のＩＤ空間では、関東のデータセンタエリアのサーバは離脱するが、他のデータセンタエリアのサーバは離脱しない。
【００１７】
なお、通常、コンシステント・ハッシュ法のＩＤ空間では、サーバの物理位置を考慮せずにサーバを分散（配置）させている。そのため、図８において、ＩＤ空間における上部に破線で囲った２つのサーバのように、同じデータセンタエリアに属するサーバが隣り合っていると、そのデータセンタエリア全域に激甚災害等が発生した場合、原本データと複製データの両方を同時に消失してしまう可能性がある。
【００１８】
そこで、本発明は、前記した事情に鑑みてなされたものであり、分散処理システムにおける管理装置が、サーバ（クラスタメンバ）を増設する際に、サーバの物理位置を考慮したサーバ選択を行うことで、３つ以上の地域のうちの１つの地域に存在するすべてのサーバがダウンしても、データが消失する事態を回避することを課題とする。
【課題を解決するための手段】
【００１９】
前記課題を解決するために、本発明は、環状のＩＤ空間に、管理対象の複数のデータ、および、前記データを管理しクラスタを構成する複数のサーバ、が割り振られ、それぞれの前記サーバが、前記ＩＤ空間において自身から所定方向回りに次の前記サーバまでの間に位置する前記データを管理するとともに、当該次の前記サーバから前記所定方向回りにさらに次の前記サーバまでの間に位置する前記データの複製を記憶する分散処理システムにおいて、クライアントマシンからのリクエストを前記複数のサーバのいずれに振り分けるかを決定する管理装置であって、前記ＩＤ空間における前記データの管理を担当するサーバを管理するＩＤ空間管理情報、前記複数のサーバおよび待機中のサーバを含むサーバそれぞれは所定の３以上の複数の物理的な地域のいずれかに属しており、前記地域ごとに、当該地域に物理的に存在するすべての前記サーバとの対応付けを管理するサーバ管理情報、を記憶する記憶部と、前記クラスタに対して前記待機中のサーバを増設する場合、当該増設するサーバについての前記ＩＤ空間における挿入位置に基づき、前記ＩＤ空間管理情報を参照して前記ＩＤ空間における当該挿入位置の両側の前記サーバを特定し、前記サーバ管理情報を参照して当該特定した前記両隣のサーバが属さない地域に物理的に存在するサーバを選択し、当該選択したサーバと当該挿入位置の情報を用いて前記ＩＤ空間管理情報を更新する処理部と、を有することを特徴とする。
【００２０】
これによれば、クラスタに対して待機中のサーバを増設する場合、ＩＤ空間におけるそのサーバの挿入位置の両隣のサーバが属さない地域に物理的に存在するサーバを選択することで、ＩＤ空間において同じ地域のサーバが隣り合うことがないので、３つ以上の地域のうちの１つの地域に存在するすべてのサーバがダウンしても、データが消失する事態を回避することができる。
【００２１】
また、本発明は、環状のＩＤ空間に、管理対象の複数のデータ、および、前記データを管理しクラスタを構成する複数のサーバ、が割り振られ、それぞれの前記サーバが、前記ＩＤ空間において自身から所定方向回りに次の前記サーバまでの間に位置する前記データを管理するとともに、当該次の前記サーバから前記所定方向回りにさらに次の前記サーバまでの間に位置する前記データの複製を記憶する分散処理システムにおいて、クライアントマシンからのリクエストを前記複数のサーバのいずれに振り分けるかを決定する管理装置であって、前記ＩＤ空間における前記データの管理を担当するサーバを管理するＩＤ空間管理情報、前記複数のサーバおよび待機中のサーバを含むサーバそれぞれは所定の３以上の複数の物理的な地域のいずれかに属しており、前記地域ごとに、当該地域に物理的に存在するすべての前記サーバとの対応付けを管理するサーバ管理情報、を記憶する記憶部と、前記クラスタに対して前記待機中のサーバを増設する場合、当該増設するサーバについての前記ＩＤ空間における挿入位置に基づき、前記地域の数をＫ（≧３）とした場合、Ｋが奇数のとき、前記ＩＤ空間管理情報を参照して前記ＩＤ空間における当該挿入位置の両側それぞれについて｛（Ｋ−１）／２｝台の前記サーバを特定し、Ｋが偶数のとき、前記ＩＤ空間管理情報を参照して前記ＩＤ空間における当該挿入位置の両側の一方について（Ｋ／２）台、他方について｛（Ｋ−２）／２｝台の前記サーバを特定し、前記サーバ管理情報を参照して当該特定したすべてのサーバがいずれも属さない地域に物理的に存在するサーバを選択し、当該選択したサーバと当該挿入位置の情報を用いて前記ＩＤ空間管理情報を更新する処理部と、を有することを特徴とする。
【００２２】
これによれば、クラスタに対して待機中のサーバを増設する場合、地域の数を３以上の自然数Ｋとした場合、Ｋが奇数のとき、ＩＤ空間におけるそのサーバの挿入位置の両側それぞれについて｛（Ｋ−１）／２｝台のサーバを特定し、Ｋが偶数のとき、ＩＤ空間におけるそのサーバの挿入位置の両側の一方について（Ｋ／２）台、他方について｛（Ｋ−２）／２｝台のサーバを特定する。そして、特定したすべてのサーバがいずれも属さない地域に物理的に存在するサーバを選択する。これによって、Ｋが奇数のときは、ＩＤ空間において任意の連続する｛（Ｋ＋１）／２｝台のサーバはすべて異なる地域に属していることになる。また、Ｋが偶数のときは、ＩＤ空間において任意の連続する（Ｋ／２）台のサーバはすべて異なる地域に属していることになる。したがって、冗長数（原本データと複製データの合計数）を３以上とした場合、１つの地域のサーバがすべてダウンしても、ダウンしたサーバが保持していた原本データの複製データを保持しているサーバの数の期待値をより大きくすることができる。
【００２３】
また、本発明は、前記処理部が、前記クラスタに対して前記待機中のサーバを増設する場合、前記ＩＤ空間管理情報を参照して前記ＩＤ空間において前記サーバ同士の間が最も広い箇所の中央の位置を前記挿入位置として特定することを特徴とする。
【００２４】
これによれば、クラスタに対して待機中のサーバを増設する場合、ＩＤ空間においてサーバ同士の間が最も広い箇所の中央の位置に対応する地域に物理的に存在するサーバを選択することで、３つ以上の地域のうちの１つの地域に存在するすべてのサーバがダウンしても、データが消失する事態を回避するとともに、各サーバにおける処理負荷をより平均化することができる。なお、本明細書および特許請求の範囲において、「中央の位置」とは、厳密な中央の位置だけでなく、中央付近の位置も含む。
【００２５】
また、本発明は、コンピュータを前記管理装置として機能させるためのプログラムである。
【００２６】
これによれば、このようなプログラムを実装したコンピュータを管理装置として機能させることができる。
【発明の効果】
【００２７】
本発明によれば、分散処理システムにおける管理装置が、サーバ（クラスタメンバ）を増設する際に、サーバの物理位置を考慮したサーバ選択を行うことで、３つ以上の地域のうちの１つの地域に存在するすべてのサーバがダウンしても、データが消失する事態を回避することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の概要の説明図である。
【図２】本実施形態の管理装置等の構成図である。
【図３】本実施形態のＩＤ空間管理情報の構成を示す図である。
【図４】本実施形態の地域名情報の構成を示す図である。
【図５】本実施形態のサーバ管理情報を示す図である。
【図６】本実施形態の管理装置による処理の流れを示すフローチャートである。
【図７】従来のコンシステント・ハッシュ法の説明図である。
【図８】従来のコンシステント・ハッシュ法におけるＩＤ空間およびクラスタメンバの物理位置の説明図である。
【発明を実施するための形態】
【００２９】
以下、本発明を実施するための形態（以下、実施形態と称する。）について、図面を参照（言及図以外の図も適宜参照）しながら説明する。なお、理解を容易にするために、まず、図１を参照して本実施形態の概要について説明し、その後、実施形態について説明する。
【００３０】
（本実施形態の概要）
図１に示すように、Ｋ種類（３種類以上。ここでは５種類）のデータセンタエリア（以下、「地域」とも称する。）にサーバを配置する場合を考える。コンシステント・ハッシュ法のＩＤ空間では、まず、同じ地域のサーバが隣り合わないように、サーバを図示のように分散させて（地域ごとに順番に）並べる。
【００３１】
そして、サーバの増設時は、ＩＤ空間における新たなクラスタメンバの挿入先（「挿入位置」と同義。ＩＤ）を決定する（図１の（１））。
【００３２】
ＩＤ空間における新たなクラスタメンバの挿入先を決定した（図１の（１））後に、その挿入先の周囲Ｋ−１個（最低限、両隣だけでもよい。）のサーバの地域を調査する（図１の（２）。詳細は後記）。そして、そのＫ−１個（最低限、両隣）のサーバのいずれも属さない地域のサーバを選択し（図１の（３））、そのサーバを増設する。
【００３３】
このようなアルゴリズムにより、ＩＤ空間において同じ地域のサーバが隣り合うことがないので、３つ以上の地域のうちの１つの地域に存在するすべてのサーバがダウンしても、データが消失する事態を回避することができる。また、各サーバにおける処理負荷をより平均化することもできる。
【００３４】
改めて説明すると、コンシステント・ハッシュ法の特性上、「どれか１つでもデータが（複製ともども）失われる確率」は、「連続してＭ（冗長数（原本データと複製データの合計数））個同じ地域のサーバが配置される確率」と等しい。前記したアルゴリズムによれば、Ｍ≧２の場合に常に上記確率を０％にできる。つまり、１つの地域が全壊（その地域に存在するすべてのサーバがダウン）したとしても、Ｍが２以上であればいずれのデータも失われない（複製データは必ず残る）。
【００３５】
また、挿入先の「両隣」だけでなく周囲Ｋ−１個のサーバの地域を調査する手法の場合、Ｋが奇数のときは、ＩＤ空間において任意の連続する｛（Ｋ＋１）／２｝台のサーバはすべて異なる地域に属していることになる。また、Ｋが偶数のときは、ＩＤ空間において任意の連続する（Ｋ／２）台のサーバはすべて異なる地域に属していることになる。これによって、冗長数を３以上とした場合、１つの地域のサーバがすべてダウンしても、ダウンしたサーバが保持していた原本データの複製データを保持しているサーバの数の期待値をより大きくすることができる。
【００３６】
例えば、Ｋ＝５で、Ｍ＝３の場合、１つの地域が全壊しても、その地域のサーバが保持していた原本データの複製データを保持しているサーバは、いずれもその地域以外の別々の地域に属しており、複製データを保持し続けている。つまり、その場合、２つの地域が全壊したとしても、１つのサーバが複製データを必ず保持していることになる。
【００３７】
データの冗長数Ｍをもっと増加させれば、さらに多くの地域が全壊した場合でも、複製データが消失していない可能性を高くすることができる。例えば、Ｋ＝７の場合、Ｍ＝４としておけば、３つの地域が全壊しても、１つのサーバが複製データを必ず保持していることになる。
【００３８】
なお、クラスタにサーバを追加する場合に、ＩＤ空間の中で、クラスタメンバ間の距離が最も広い個所の中央の位置を選んだが、これは一例に過ぎない。つまり、クラスタにサーバを追加する場合に、ＩＤ空間において選択する位置（挿入位置）は任意でよく、必須事項は、そのＩＤ空間において選択した位置の両隣のサーバのいずれも属さない地域のサーバを選択することである。これにより、サーバの物理位置を考慮したサーバ選択を行うことができ、３つ以上の地域のうちの１つの地域に存在するすべてのサーバがダウンしても、データが消失する事態を回避することができる。
【００３９】
（実施形態）
次に、本実施形態について説明する。図２に示すように、本実施形態の分散処理システム１０００は、負荷分散装置３、管理装置４、クラスタ１００を構成する複数のサーバ５を備えている。負荷分散装置３は、インターネット等のネットワーク２を介して、複数のクライアントマシン１と接続されている。
【００４０】
全体の主な動作について説明すると、クライアントマシン１からのデータ処理リクエストを、ネットワーク２経由で負荷分散装置３が受け取る。負荷分散装置３は、データのＩＤ空間上のサーバ割当表（ＩＤ空間管理情報）に基づいて、そのリクエストを、データ処理を行う複数のサーバ５のいずれかに振り分ける。振り分けられたサーバ５は、そのリクエストの処理を行う。管理装置４は、ＩＤ空間管理情報を管理する。
【００４１】
次に、負荷分散装置３と管理装置４の構成について説明する。
負荷分散装置３は、記憶部３１、処理部３２、通信部３３を備える。
記憶部３１は、情報を記憶する手段であり、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）などのメモリ、ＨＤＤ（Hard Disk Drive）などによって構成される。記憶部３１には、管理装置４から受信したＩＤ空間管理情報４１１が、ＩＤ空間管理情報３１１として格納されている。なお、記憶部３１には、処理部３２の動作プログラムなども格納されている（図示を省略）。
【００４２】
処理部３２は、記憶部３１に格納された情報に基づいて演算処理を行う手段であり、例えばＣＰＵ（Central Processing Unit）によって構成される。
【００４３】
通信部３３は、外部装置との通信に用いられる通信インタフェースである。
なお、負荷分散装置３は、ほかに、負荷分散装置３のユーザが情報を入力する入力部や、情報を表示する表示部などを備えていてもよい。
【００４４】
管理装置４は、コンシステント・ハッシュ法に基づいて、クライアントマシン１からのリクエストを複数のサーバ５（クラスタメンバ）のいずれに振り分けるかを決定するコンピュータ装置である。なお、前記したように、このコンシステント・ハッシュ法では、環状のＩＤ空間に、管理対象の複数のデータ、および、データを管理しクラスタ１００を構成する複数のサーバ５、が割り振られ、それぞれのサーバ５が、ＩＤ空間において自身から時計回り（所定方向回り）に次のサーバ５までの間に位置するデータを管理（担当）するとともに、当該次のサーバ５から時計回りにさらに次のサーバ５までの間に位置するデータの複製を記憶することを前提とする。
【００４５】
管理装置４は、記憶部４１、処理部４２、入力部４３、表示部４４、通信部４５を備える。
記憶部４１は、情報を記憶する手段であり、ＲＡＭやＲＯＭなどのメモリ、ＨＤＤなどによって構成される。記憶部４１には、ＩＤ空間管理情報４１１、地域名情報４１２、サーバ管理情報４１３、地域数４１４、冗長数４１５が格納されている。なお、記憶部４１には、処理部４２の動作プログラムなども格納されている（図示を省略）。
【００４６】
ＩＤ空間管理情報４１１は、管理対象のデータについて所定のハッシュ値変換を行って算出されたＩＤを用いて、そのデータを担当するサーバ５を管理する情報である（図３で後記）。
【００４７】
地域名情報４１２は、地域ＩＤと、その地域ＩＤに対応する地域名との対応付けを管理する情報である（図４で後記）。
【００４８】
サーバ管理情報４１３は、地域（地域ＩＤ）ごとに、当該地域に物理的に存在するすべてのサーバ５との対応付けを管理する情報である（図５で後記）。なお、本実施形態では、すべてのサーバ５（クラスタ１００をすでに構成している複数のサーバ、および、待機中のサーバ）は、所定の３以上の複数の物理的な地域のいずれかに属していることを前提としている。
【００４９】
地域数４１４は、管理装置４のユーザによって予め設定された地域数（Ｋ）の情報である。
冗長数４１５は、管理装置４のユーザによって予め設定された冗長数（Ｍ）の情報である。
【００５０】
処理部４２は、記憶部４１に格納された情報に基づいて演算処理を行う手段であり、例えばＣＰＵによって構成される。処理部４２は、クラスタ１００に対して待機中のサーバ５を増設する場合、まず、当該増設するサーバ５についてＩＤ空間における挿入位置を決定する。次に、処理部４２は、ＩＤ空間管理情報４１１を参照してＩＤ空間における当該挿入位置の両側のサーバ５を特定する。次に、処理部４２は、サーバ管理情報４１３を参照して当該特定した両隣のサーバ５が属さない地域に物理的に存在するサーバ５を選択し、当該選択したサーバ５と当該挿入位置の情報を用いてＩＤ空間管理情報４１１を更新する。詳細は図６の説明で後記する。
【００５１】
また、処理部４２は、クラスタ１００に対して待機中のサーバ５を増設する場合、次のような処理を行ってもよい。まず、地域の数をＫ（≧３）とした場合、Ｋが奇数のとき、ＩＤ空間管理情報４１１を参照してＩＤ空間における当該挿入位置の両側それぞれについて｛（Ｋ−１）／２｝台のサーバ５を特定する。また、処理部４２は、Ｋが偶数のとき、ＩＤ空間管理情報４１１を参照してＩＤ空間における当該挿入位置の両側の一方について（Ｋ／２）台、他方について｛（Ｋ−２）／２｝台のサーバ５を特定する。次に、処理部４２は、サーバ管理情報４１３を参照して当該特定したすべてのサーバ５がいずれも属さない地域に物理的に存在するサーバ５を選択し、当該選択したサーバと当該挿入位置の情報を用いてＩＤ空間管理情報４１１を更新する。詳細は図６の説明で後記する。
【００５２】
入力部４３は、管理装置４のユーザが情報を入力する手段であり、例えば、キーボードやマウスによって実現される。
表示部４４は、情報を表示する手段であり、例えば、ＬＣＤ（Liquid Crystal Display）によって実現される。
通信部４５は、外部装置との通信に用いられる通信インタフェースである。
【００５３】
次に、ＩＤ空間管理情報４１１について説明する。図３に示すように、ＩＤ空間管理情報４１１は、ＩＤ、サーバの各カラムから構成され、ＩＤの値の大きさでソートされている。
ＩＤは、ＩＤ空間におけるＩＤであり、サーバ５が管理を担当するデータの領域を特定するために格納される。
【００５４】
サーバは、クラスタ１００を構成するサーバ５の識別子を表す。例えば、図３に示す、第１行目のＩＤの値が「００５６」の場合は、識別子が「００００」〜「００５６」の領域に属するデータを「サーバＡ」が担当することを示す。また、第２行目のＩＤの値が「０１７２」の場合は、１つ前の行のＩＤの値に１をプラスした「００５７」〜「０１７２」の識別子に属するデータを「サーバＧ」が担当することを示す。
【００５５】
次に、地域名情報４１２について説明する。図４に示すように、地域名情報４１２は、地域ＩＤ、地域名の各カラムから構成される。
地域ＩＤは、所定の複数の物理的な地域の識別子を表す。
地域名は、その行の地域ＩＤに対応する地域の名称を表す。
【００５６】
次に、サーバ管理情報４１３について説明する。図５に示すように、サーバ管理情報４１３は、地域ＩＤ、サーバの各カラムから構成される。
地域ＩＤは、所定の複数の物理的な地域の識別子を表す。
サーバは、対応する地域ＩＤの地域に物理的に存在するサーバ５の識別子を表す。なお、このサーバ５には、まだクラスタ１００として使用されていないものも含まれている。
【００５７】
次に、管理装置４による処理について説明する。
図６に示すように、ステップＳ１において、管理装置４の処理部４２は、クラスタ構成変更要求があるか否かを判定し、Ｙｅｓの場合はステップＳ２に進み、Ｎｏの場合はステップＳ１に戻る。なお、ここでのクラスタ構成変更要求は、例えば、管理装置４のユーザによるその旨の入力や、他の装置からのその旨のリクエストの受信などが考えられる。
【００５８】
ステップＳ２において、処理部４２は、そのクラスタ構成変更要求がクラスタメンバの追加か否かを判定し、Ｙｅｓの場合はステップＳ３に進み、Ｎｏの場合はステップＳ７に進む。
【００５９】
ステップＳ３において、処理部４２は、ＩＤ空間において、追加するクラスタメンバの挿入先（ＩＤ）を決定する。
【００６０】
どこに挿入するかは、入力部４３を通じて保守者から指定を受けてもよいし、処理部４２が任意の方法で算出することもできる。ＩＤ空間において選択する位置は任意でよく、必須事項は、そのＩＤ空間において選択した位置の両隣のサーバ５のいずれも属さない地域のサーバ５を選択することである。これにより、サーバ５の物理位置を考慮したサーバ選択を行うことができ、３つ以上の地域のうちの１つの地域に存在するすべてのサーバ５がダウンしても、データが消失する事態を回避することができる。
【００６１】
例えば、処理部４２が、記憶部４１のＩＤ空間管理情報４１１を参照して、ＩＤ空間の中でクラスタメンバ間の距離（ＩＤ空間上の距離）が最も広い個所を検索（特定）し、そのクラスタメンバ間の中央の位置を新たなクラスタメンバのＩＤの挿入先として決定する。なお、このような位置を選択する理由は、クラスタ構成の分散処理システム１０００では、クラスタメンバ間で負荷がなるべく平均化されていることが望ましく、統計的に、データ数がクラスタメンバ数よりも格段に多い場合には、各クラスタメンバが担当するデータ数はＩＤ空間上のクラスタメンバ間の距離にほぼ比例するためである。
【００６２】
続いて、ステップＳ４において、処理部４２は、記憶部４１のＩＤ空間管理情報４１１および地域数４１４を参照して、前記中央点の周囲Ｋ−１個のサーバ５の属するデータセンタエリアを調査し、使用されていないデータセンタエリア（地域ＩＤ）を特定する。
【００６３】
ステップＳ４では、具体的には、処理部４２は、Ｋが奇数のとき、ＩＤ空間管理情報４１１と地域数４１４を参照してＩＤ空間における当該位置の両側それぞれについて｛（Ｋ−１）／２｝台のサーバ５を特定する。また、Ｋが偶数のとき、ＩＤ空間管理情報４１１と地域数４１４を参照してＩＤ空間における当該位置の両側の一方について（Ｋ／２）台、他方について｛（Ｋ−２）／２｝台のサーバ５を特定する。次に、サーバ管理情報４１３を参照して当該特定したすべてのサーバ５がいずれも属さないデータセンタエリアを特定する。なお、「いずれも属さないデータセンタエリア」が複数ある場合は、例えば、使用されているサーバ５の総数の最も少ないデータセンタエリアを選ぶなどすればよいが、これに限定されない。
【００６４】
続いて、ステップＳ５において、処理部４２は、記憶部４１のサーバ管理情報４１３を参照して、そのデータセンタエリアに物理的に存在する（つまり、ステップＳで特定した地域ＩＤに対応する）サーバ５を選択する。
【００６５】
ステップＳ６において、処理部４２は、ＩＤ空間管理情報４１１を更新して、処理を終了する。ステップＳ７では、具体的には、ステップＳ３〜Ｓ５を経由した場合は、ＩＤ空間管理情報４１１において、新たな行を挿入し、該当するＩＤおよび追加するサーバ５の識別子を書き込む等の処理を行う（追加されたサーバ５は周知の手段でアクティベートされる）。また、例えば、ステップＳ３〜Ｓ５を経由せず、障害等によりクラスタメンバの一部を削除する場合は、ＩＤ空間管理情報４１１において、該当する行を削除する等の処理を行う。
【００６６】
なお、この後、負荷分散装置３は、管理装置４から最新のＩＤ空間管理情報４１１を受信して記憶部３１にＩＤ空間管理情報３１１として保存する。そして、負荷分散装置３は、そのＩＤ空間管理情報３１１に基づいて、コンシステント・ハッシュ法によって、クライアントマシン１から受け取ったリクエストを、複数のサーバ５のいずれかに振り分ける。振り分けられたサーバ５は、そのリクエストの処理を行う。
【００６７】
また、複数のサーバ５は、管理装置４から最新のＩＤ空間管理情報４１１と冗長数４１５を受信して記憶部（不図示）に保存し、コンシステント・ハッシュ法に基づく前記したデータの複製を行う。
【００６８】
このようにして、本実施形態の管理装置４によれば、クラスタ１００に対して待機中のサーバ５を増設する場合、ＩＤ空間におけるそのサーバ５の位置の周囲Ｋ−１個のサーバ５の属するデータセンタエリアを調査し、使用されていないデータセンタエリアに物理的に存在するサーバ５を選択することで、ＩＤ空間において同じ地域のサーバが隣り合うことがないので、３つ以上（本実施形態では５つ）のデータセンタエリアのうちの１つのデータセンタエリアに存在するすべてのサーバ５がダウンしても、複製データが消失する事態を回避することができる。また、ＩＤ空間における挿入先の「両隣」だけでなく「周囲Ｋ−１個」のサーバの属するデータセンタエリアを調査することで、ダウンしたサーバ５が保持していた原本データの複製データを保持しているサーバ５の数の期待値をより大きくすることができる（前記「本実施形態の概要」参照）。
【００６９】
また、クラスタ１００に対して待機中のサーバ５を増設する場合、ＩＤ空間においてサーバ５同士の間が最も広い箇所の中央の位置に対応する地域に物理的に存在するサーバ５を選択することで、各サーバ５における処理負荷をより平均化することができる。
【００７０】
なお、前記したように、「周囲Ｋ−１個」の代わりに「両隣」としても、ＩＤ空間において同じデータセンタエリアのサーバ５が隣り合うことがないので、３つ以上のデータセンタエリアのうちの１つのデータセンタエリアに存在するすべてのサーバ５がダウンしても、データが消失する事態を回避することができるという最低限の効果を奏する。
【００７１】
以上で本実施形態の説明を終えるが、本発明の態様はこれらに限定されるものではない。
例えば、管理装置４と負荷分散装置３を同一のハードウエアに並存させる構成としてもよい。
【００７２】
また、負荷分散装置３を使用せず、それぞれのクライアントマシン１が管理装置４から受信したＩＤ空間管理情報４１１を保持して、ネットワーク２経由で複数のサーバ５のいずれかに直接アクセスするようにしてもよい。
【００７３】
また、地域として、データセンタエリアを単位とする場合を例にとって説明したが、データセンタエリアをさらに分割したものや都道府県等の別の単位を採用してもよい。
【００７４】
また、本実施形態ではコンシステント・ハッシュ法を前提としたが、他の手法を前提としてもよい。
また、本発明は、コンピュータを管理装置４として機能させるためのプログラムとしても具現化可能である。
その他、具体的な構成について、本発明の主旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００７５】
１      クライアントマシン
２      ネットワーク
３      負荷分散装置
４      管理装置
５      サーバ
３１    記憶部
３２    処理部
３３    通信部
４１    記憶部
４２    処理部
４３    入力部
４４    表示部
４５    通信部
１００  クラスタ
３１１  ＩＤ空間管理情報
４１１  ＩＤ空間管理情報
４１２  地域名情報
４１３  サーバ管理情報
４１４  地域数
４１５  冗長数
１０００  分散処理システム
【図１】
0005629281.tif 000002
【図２】
0005629281.tif 000003
【図３】
0005629281.tif 000004
【図４】
0005629281.tif 000005
【図５】
0005629281.tif 000006
【図６】
0005629281.tif 000007
【図７】
0005629281.tif 000008
【図８】
0005629281.tif 000009