(57)【特許請求の範囲】
【請求項１】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、
自身のノードの負荷情報を計測するノード負荷計測部と、
前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、
前記スロット最適化処理部は、
特定のノードが減設される際に、前記ＩＤ空間上において減設されるノードの時計回りで次に位置する次ノードのノードＩＤを、前記減設されるノードから時計回りで次の次に位置する次々ノードのノードＩＤと、前記減設されるノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、前記算出した次ノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新すること
を特徴とするノード。
【請求項２】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、
自身のノードの負荷情報を計測するノード負荷計測部と、
前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、
前記スロット最適化処理部は、
特定のノードが減設される際に、前記ＩＤ空間上において減設されるノードの反時計回りで１つ前に位置する前ノードのノードＩＤを、前記減設されるノードから時計回りで次に位置する次ノードのノードＩＤと、前記減設されるノードから反時計回りで２つ前に位置する前々ノードのノードＩＤとの合計を等分割して算出し、前記算出した前ノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新すること
を特徴とするノード。
【請求項３】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、
自身のノードの負荷情報を計測するノード負荷計測部と、
前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、
前記スロット最適化処理部は、
特定のノードが増設される際に、前記振り分けＩＤ情報を参照し、複数の前記ノードのうち、前記スロットの大きさが最も大きいノードを抽出し、前記抽出したノードのスロットを分割する位置に、増設するノードを配置するように割り当て、
前記増設するノードのノードＩＤを、前記増設するノードによりスロットが分割される前記抽出したノードのノードＩＤと、当該抽出したノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、算出した前記増設するノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新すること
を特徴とするノード。
【請求項４】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、
自身のノードの負荷情報を計測するノード負荷計測部と、
前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、
前記スロット最適化処理部は、
特定のノードの減設時または増設時において、減設後または増設後の各ノードの平均負荷を示すノード平均負荷を算出し、各ノードの負荷から前記ノード平均負荷を減算した値の絶対値の合計であるユークリッド距離合計をノード毎に算出し、算出したユークリッド距離合計が最も小さいノードを、各ノードのデータの移動量が最も少ない起点となるノードとして選択し、前記起点となるノードを基準として、各ノードの前記スロットの大きさが等しくなるように、各ノードのノードＩＤを決定し、前記決定した各ノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新すること
を特徴とするノード。
【請求項５】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、
前記ノードは、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、
前記クラスタを構成する複数のノードに減設が生じた場合、前記ＩＤ空間上において減設されるノードの時計回りで次に位置する次ノードを、前記ノードＩＤを変更するノードとして決定し、前記次ノードのノードＩＤを、前記減設されるノードから時計回りで次の次に位置する次々ノードのノードＩＤと、前記減設されるノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、前記算出した次ノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップ
を実行することを特徴とするスロット最適化方法。
【請求項６】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、
前記ノードは、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、
前記クラスタを構成する複数のノードに減設が生じた場合、前記ＩＤ空間上において減設されるノードの反時計回りで１つ前に位置する前ノードを、前記ノードＩＤを変更するノードとして決定し、前記前ノードのノードＩＤを、前記減設されるノードから時計回りで次に位置する次ノードのノードＩＤと、前記減設されるノードから反時計回りで２つ前に位置する前々ノードのノードＩＤとの合計を等分割して算出し、前記算出した前ノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップ
を実行することを特徴とするスロット最適化方法。
【請求項７】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、
前記ノードは、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、
前記クラスタを構成する複数のノードに増設が生じた場合、前記振り分けＩＤ情報を参照し、複数の前記ノードのうち、前記スロットの大きさが最も大きいノードを抽出し、前記抽出したノードのスロットを分割する位置に、増設するノードを配置するように割り当て、
前記増設するノードのノードＩＤを、前記増設するノードによりスロットが分割される前記抽出したノードのノードＩＤと、当該抽出したノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、算出した前記増設するノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップ
を実行することを特徴とするスロット最適化方法。
【請求項８】
クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、
前記ノードは、
複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、
自身のノードの負荷情報を計測するステップと、
前記クラスタを構成する複数のノードに減設または増設が生じた場合、減設後または増設後の各ノードの平均負荷を示すノード平均負荷を自身以外のノードから負荷情報を取得することにより算出し、各ノードの負荷から前記ノード平均負荷を減算した値の絶対値の合計であるユークリッド距離合計をノード毎に算出し、算出したユークリッド距離合計が最も小さいノードを、各ノードのデータの移動量が最も少ない起点となるノードとして選択し、前記起点となるノードを基準として、各ノードの前記スロットの大きさが等しくなるように、各ノードのノードＩＤを決定し、前記決定した各ノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップと
を実行することを特徴とするスロット最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に分散配置されるノードをクラスタ化してデータを格納する分散処理システムにおいて、各ノードの負荷の偏りを低減する、ノードおよびスロット最適化方法に関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングの隆盛に伴い、多量のデータの処理や保持を効率的に行うことが求められている。そこで、複数のサーバを協調動作させることにより効率的な処理を実現する分散処理技術が発展している。
【０００３】
分散処理を行う際には、クラスタ構成からなる分散処理システムを構成する各サーバ（以下、「ノード」と称する。）が担当するデータを決定する必要がある。このとき、分散処理システム全体での処理能力を高めるためには、各ノードが担当するデータ数は平均化されていることが望ましい。
【０００４】
代表的なデータの管理手法として、各データのｋｅｙをハッシュ関数にかけた値（以下、「ｈａｓｈ（ｋｅｙ）」と称する。）をノード数Ｎで割った余り、即ち「ｈａｓｈ（ｋｅｙ） ｍｏｄ Ｎ」を番号として持つノードがデータを管理する手法がある。この場合、各ノードに事前に「０」から「Ｎ−１」までの番号を割り当てていることが前提となる。このような管理手法を用いた場合、ノードの追加・離脱が発生すると、Ｎの値が変化して、多くのデータについて、そのデータの保存を担当するノードが変更になるため、担当するデータを再配置することが必要になる。
【０００５】
そこで、ノードの追加・離脱に伴い担当するノードが変更になるデータ数を約１／Ｎに抑える方法として、コンシステント・ハッシュ（Consistent Hashing）法（非特許文献１参照）を用いたデータ管理手法がある。このコンシステント・ハッシュ法は、Amazon Dynamo（非特許文献２参照）等において用いられている。
【０００６】
このコンシステント・ハッシュ法を用いたデータ管理手法では、ノードとデータの双方にＩＤ（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，［平成27年8月25日検索］，インターネット<ＵＲＬ:http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf>
【非特許文献２】Giuseppe DeCandia，et al.，“Dynamo: Amazon’s Highly Available Key-value Store”， SOSP’07, October 14-17, 2007, Stevenson, Washington, USA，［online］，［平成27年8月25日検索］，インターネット<ＵＲＬ:http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【非特許文献３】入江  道生、他４名、「コンシステント・ハッシュ法におけるデータの複製を意識した負荷分散手法」、社団法人電子情報通信学会、2010年10月、信学技報、IN2010-77、P.69-74
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献３に記載の各ノードに仮想的に複数のＩＤを持たせる手法（仮想ノードを用いる手法）では、１つのノードに対し複数の仮想ノードが設定されるため、チェックすべきノード数が増加し、検索性能や処理性能が劣化するという欠点がある。そのため、例えば、映像サービスの提供においては、仮想ノードの利用が見送られるケースがある。
【００１０】
また、コンシステント・ハッシュ法の分散システムにおいては、コンシステント・ハッシュのＩＤ空間上での時計回り探索により、各ノードの担当領域が決定される。よって、何らかの事由で特定のノードが減設された場合には、減設されたノードの時計回りに次に位置するノードに担当領域の移譲が行われる。その結果、特定ノードへ極端に負荷が集中する事象が発生し、ノード毎の負荷バランスが崩れるという問題がある。この点について、図１２を参照して説明する。
【００１１】
図１２（ａ）は、コンシステント・ハッシュのＩＤ空間に配置された各ノードおよびデータと、各ノードの負荷を示している。コンシステント・ハッシュ法では、図１２（ａ）の下図に示すように、ＩＤ空間上に位置するデータ（各図において丸「〇」で示す。）から、ＩＤ空間を時計回りに辿り最初に当たったノード（各図において、四角「□」で示す。）を、そのデータを担当するノードとする。図１２（ａ）においては、ノード「Ａ」，「Ｂ」，「Ｃ」それぞれは３つのデータの処理を担当し、ノード「Ｄ」は、２つのデータの処理を担当している。この場合の、各ノードの負荷を図１２（ａ）の上図に示している。
【００１２】
図１２（ａ）の状態において、ノード「Ｃ」が減設された場合を考える。この場合、図１２（ｂ）に示すように、減設されたノード「Ｃ」が担当していたデータは、ＩＤ空間上で時計回りに次のノードであるノード「Ｄ」が担当することになる。その結果、ノード「Ｄ」の負荷が、他のノードと比べ大きくなってしまうことになる（図１２（ｂ）の上図参照）。つまり、各ノードの負荷バランスが崩れてしまう。
【００１３】
また、ノードを増設することにより、負荷バランスを解消しようとしても、既存技術では、例えば、増加するノードの位置がランダムに決定されるため、ノードの最適な配置とならず、負荷バランスが解消されない場合が想定される。
【００１４】
このような背景を鑑みて本発明がなされたのであり、本発明は、分散処理システムを構成するノードの減設・増設動作時において、特定ノードへの負荷の偏りを低減することができる、ノードおよびスロット最適化方法を提供することを課題とする。
【課題を解決するための手段】
【００１８】
前記した課題を解決するため、請求項１に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、自身のノードの負荷情報を計測するノード負荷計測部と、前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、前記スロット最適化処理部が、特定のノードが減設される際に、前記ＩＤ空間上において減設されるノードの時計回りで次に位置する次ノードのノードＩＤを、前記減設されるノードから時計回りで次の次に位置する次々ノードのノードＩＤと、前記減設されるノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、前記算出した次ノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新することを特徴とするノードとした。
また、請求項５に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、前記ノードが、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、前記クラスタを構成する複数のノードに減設が生じた場合、前記ＩＤ空間上において減設されるノードの時計回りで次に位置する次ノードを、前記ノードＩＤを変更するノードとして決定し、前記次ノードのノードＩＤを、前記減設されるノードから時計回りで次の次に位置する次々ノードのノードＩＤと、前記減設されるノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、前記算出した次ノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップを実行することを特徴とするスロット最適化方法とした。
【００１９】
これにより、特定のノードが減設される際に、ＩＤ空間上において減設されるノードの時計回りで次に位置する次ノードのノードＩＤを、隣接ノード間で負荷が偏らないように適切に変更することができる。
【００２０】
請求項２に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、自身のノードの負荷情報を計測するノード負荷計測部と、前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、前記スロット最適化処理部が、特定のノードが減設される際に、前記ＩＤ空間上において減設されるノードの反時計回りで１つ前に位置する前ノードのノードＩＤを、前記減設されるノードから時計回りで次に位置する次ノードのノードＩＤと、前記減設されるノードから反時計回りで２つ前に位置する前々ノードのノードＩＤとの合計を等分割して算出し、前記算出した前ノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新することを特徴とするノードとした。
また、請求項６に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、前記ノードが、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、前記クラスタを構成する複数のノードに減設が生じた場合、前記ＩＤ空間上において減設されるノードの反時計回りで１つ前に位置する前ノードを、前記ノードＩＤを変更するノードとして決定し、前記前ノードのノードＩＤを、前記減設されるノードから時計回りで次に位置する次ノードのノードＩＤと、前記減設されるノードから反時計回りで２つ前に位置する前々ノードのノードＩＤとの合計を等分割して算出し、前記算出した前ノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップを実行することを特徴とするスロット最適化方法とした。
【００２１】
これにより、特定のノードが減設される際に、ＩＤ空間上において減設されるノードの反時計回りで１つ前に位置する前ノードのノードＩＤを、隣接ノード間で負荷が偏らないように適切に変更することができる。
【００２２】
請求項３に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、自身のノードの負荷情報を計測するノード負荷計測部と、前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、前記スロット最適化処理部が、特定のノードが増設される際に、前記振り分けＩＤ情報を参照し、複数の前記ノードのうち、前記スロットの大きさが最も大きいノードを抽出し、前記抽出したノードのスロットを分割する位置に、増設するノードを配置するように割り当て、前記増設するノードのノードＩＤを、前記増設するノードによりスロットが分割される前記抽出したノードのノードＩＤと、当該抽出したノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、算出した前記増設するノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新することを特徴とするノードとした。
また、請求項７に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、前記ノードが、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、前記クラスタを構成する複数のノードに増設が生じた場合、前記振り分けＩＤ情報を参照し、複数の前記ノードのうち、前記スロットの大きさが最も大きいノードを抽出し、前記抽出したノードのスロットを分割する位置に、増設するノードを配置するように割り当て、前記増設するノードのノードＩＤを、前記増設するノードによりスロットが分割される前記抽出したノードのノードＩＤと、当該抽出したノードから反時計回りで１つ前に位置する前ノードのノードＩＤとの合計を等分割して算出し、算出した前記増設するノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップを実行することを特徴とするスロット最適化方法とした。
【００２３】
これにより、特定のノードが増設される際に、増設されるノードのＩＤ空間上でのノードＩＤを、隣接ノード間で負荷が偏らないように適切に設定することができる。
【００２４】
請求項４に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードであって、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部と、自身のノードの負荷情報を計測するノード負荷計測部と、前記クラスタを構成する複数のノードに減設または増設が生じた場合、複数の前記ノードの中から、前記ノードＩＤを変更するノードを決定し、複数の前記ノードの前記負荷情報を用いて、前記減設または増設後の複数の前記ノードについての負荷の偏りを低減する前記ＩＤ空間上の位置に、前記決定したノードのノードＩＤを変更し、前記変更したノードＩＤを前記振り分けＩＤ情報に記憶するスロット最適化処理部と、を備え、前記スロット最適化処理部が、特定のノードの減設時または増設時において、減設後または増設後の各ノードの平均負荷を示すノード平均負荷を算出し、各ノードの負荷から前記ノード平均負荷を減算した値の絶対値の合計であるユークリッド距離合計をノード毎に算出し、算出したユークリッド距離合計が最も小さいノードを、各ノードのデータの移動量が最も少ない起点となるノードとして選択し、前記起点となるノードを基準として、各ノードの前記スロットの大きさが等しくなるように、各ノードのノードＩＤを決定し、前記決定した各ノードのノードＩＤを用いて、前記振り分けＩＤ情報を更新することを特徴とするノードとした。
また、請求項８に記載の発明は、クラスタを構成する複数のノードそれぞれに、コンシステント・ハッシュ法によりデータを振り分けて処理させる分散処理システムの前記ノードのスロット最適化方法であって、前記ノードが、複数の前記ノードのノードＩＤそれぞれに対応付けて、ＩＤ空間上での担当領域を示すスロットが記憶される振り分けＩＤ情報を格納する記憶部を備えており、自身のノードの負荷情報を計測するステップと、前記クラスタを構成する複数のノードに減設または増設が生じた場合、減設後または増設後の各ノードの平均負荷を示すノード平均負荷を自身以外のノードから負荷情報を取得することにより算出し、各ノードの負荷から前記ノード平均負荷を減算した値の絶対値の合計であるユークリッド距離合計をノード毎に算出し、算出したユークリッド距離合計が最も小さいノードを、各ノードのデータの移動量が最も少ない起点となるノードとして選択し、前記起点となるノードを基準として、各ノードの前記スロットの大きさが等しくなるように、各ノードのノードＩＤを決定し、前記決定した各ノードのノードＩＤを前記振り分けＩＤ情報に記憶するステップとを実行することを特徴とするスロット最適化方法とした。
【００２５】
これにより、特定のノードの減設時または増設時において、各ノードの負荷が最も低くなるような起点となるノードを選択し、その起点となるノードを基準として、各ノードのスロットの大きさが等しくなるように、各ノードのノードＩＤを決定することができる。
よって、ノードの減設または増設時において、各ノードの負荷に偏りがないようにすることができる。
【発明の効果】
【００２６】
本発明によれば、分散処理システムを構成するノードの減設・増設動作時において、特定ノードへの負荷の偏りを低減する、ノードおよびスロット最適化方法を提供することができる。
【図面の簡単な説明】
【００２７】
【図１】本実施形態に係るノードを含む分散処理システムの全体構成を示す図である。
【図２】本実施形態に係るノードが実行する負荷分散処理の概要を説明するための図である。
【図３】本実施形態に係るノードの機能ブロック図である。
【図４】本実施形態に係るノード識別子管理テーブルのデータ構成例を示す図である。
【図５】本実施形態に係る振り分けＩＤテーブルのデータ構成例を示す図である。
【図６】手法（１）Minimum Adjustment法の減設時における負荷分散処理を説明するための図である。
【図７】手法（１）Minimum Adjustment法の増設時における負荷分散処理を説明するための図である。
【図８】手法（２）Full Justification法の減設時における起点ノード選択処理を説明するための図である。
【図９】手法（２）Full Justification法の増設時における起点ノード選択処理を説明するための図である。
【図１０】本実施形態に係るノードが、手法（１）Minimum Adjustment法を実行する場合の処理の流れを示すフローチャートである。
【図１１】本実施形態に係るノードが、手法（２）Full Justification法を実行する場合の処理の流れを示すフローチャートである。
【図１２】従来技術における問題を説明するための図である。
【発明を実施するための形態】
【００２８】
＜全体構成＞
まず、本発明を実施するための形態（以下、「本実施形態」と称する。）に係るノード１を含む分散処理システム１０００について説明する。
図１は、本実施形態に係るノード１を含む分散処理システム１０００の全体構成を示す図である。
【００２９】
この分散処理システム１０００は、複数のノード１から構成される。各ノード１は、コンピュータなどの物理装置や仮想マシンなどの論理装置である。ロードバランサ３は、クライアント２から受信したメッセージを、単純なラウンドロビン等により振り分けて各ノード１に送信する。そして、ノード１の振り分け部１２は、クライアント２からのメッセージを、例えば、コンシステント・ハッシュ法等に基づき、メッセージを担当するノード１に振り分ける。メッセージを担当するノード１では、信号処理部１３において、信号処理を行い、クライアント２にサービスを提供する。
【００３０】
なお、ロードバランサ３が存在せず、クライアント２から任意のノード１（振り分け部１２）にメッセージを送信することも可能である。また、振り分け部１２と信号処理部１３とは、同じノード１上に同時に存在してもよいし、別々のノード１上に存在してもよい。
【００３１】
＜ノード＞
次に、分散処理システム１０００を構成するノード１について、具体的に説明する。
【００３２】
≪概要≫
まず、本実施形態に係るノード１の処理の概要を説明する。
ノード１は、負荷分散処理（負荷の偏りを低減する処理）の手法として、手法（１）Minimum Adjustment法、手法（２）Full Justification法のいずれかを実行する。
【００３３】
手法（１）Minimum Adjustment法は、分散処理システム１０００を構成するノード１に減設や増設が発生した場合に、その減設するノード（以下、「減設ノード」と称する場合がある。）や増設するノード（以下、「増設ノード」と称する場合がある。）に隣接するノード（以下、「隣接ノード」と称する場合がある。）間で、担当領域を等分割するようにしてノードＩＤを変更する。
【００３４】
具体的には、図２（ａ）に示すように、コンシステント・ハッシュのＩＤ空間上に、ノード「Ａ」〜「Ｄ」が配置され、各データの処理を実行している場合において、例えば、ノード「Ｃ」が減設したものとする。このとき、手法（１）Minimum Adjustment法では、ノード「Ｃ」に隣接するノードであるノード「Ｄ」またはノード「Ｂ」のいずれかのノードＩＤを変更することにより、負荷の偏りの低減を実現する。ここでは、減設ノード（ノード「Ｃ」）のＩＤ空間上での次のノードであるノード「Ｄ」のノードＩＤを変更するものとして説明する。手法（１）Minimum Adjustment法では、図２（ｂ）に示すように、減設ノードであるノード「Ｃ」のＩＤ空間上において次のノードであるノード「Ｄ」と、さらにその次のノード（次々ノード）であるノード「Ａ」とを対象として、ノード「Ｄ」とノード「Ａ」の担当領域を等分割するようにノード「Ｄ」のノードＩＤを変更する（ここでは、ノード「Ｄ」を反時計回りに移動する。）。
これにより、ＩＤ空間上において、減設ノード（ノード「Ｃ」）の時計回りに次のノード（ノード「Ｄ」）の負荷が、極端に高くなることを抑制することができる。また、担当データを移動する必要のあるノードが、全ノードのうち、減設ノード（ノード「Ｃ」）に隣接するノード「Ｄ」のみとなるため、データの移動量を少なくすることができ、高速に減設に対応することができる。
【００３５】
手法（２）Full Justification法は、分散処理システム１０００に属するノード１の減設が発生した場合、または、ノード１を増設する場合に、各ノード１の担当領域が等分割されるように、特定ノード（後記する「起点ノード」）を基準として、起点ノード以外の他の全てのノード１のノードＩＤを変更する。
【００３６】
具体的には、図２（ａ）に示すように、コンシステント・ハッシュのＩＤ空間上に、ノード「Ａ」〜「Ｄ」が配置され、各データを処理している場合において、例えば、ノード「Ｃ」が減設したものとする。このとき、手法（２）Full Justification法では、図２（ｃ）に示すように、特定ノード（図２（ｃ）においては、ノード「Ｂ」）を起点ノードとして、各ノード１の担当領域（スロット）が等分割されるように、起点ノード以外のノード１のノードＩＤを変更（再設定）する。ここでは、ノード「Ａ」とノード「Ｄ］のノードＩＤを変更する。
これにより、各ノード１の負荷が偏らず、均等に保つことができる。
【００３７】
本実施形態に係るノード１は、手法（１）Minimum Adjustment法、手法（２）Full Justification法のいずれかの負荷分散処理を実行することにより、分散処理システム１０００を構成するノード１の減設・増設動作時において、特定ノードへの負荷の偏りを低減ることができる。
【００３８】
≪ノードの構成≫
次に、本実施形態に係る分散処理システム１０００を構成するノード１について、具体的に説明する。なお、本実施形態に係るノード１は、分散処理システム１０００の複数のノード１のうち、後記するノード識別子管理テーブル１００（図４参照）および振り分けＩＤテーブル２００（図５参照）を管理する特権ノードとなる場合と、特権ノードからノード識別子管理テーブル１００および振り分けＩＤテーブル２００の情報を受け取り自身のノード識別子管理テーブル１００および振り分けＩＤテーブル２００を更新する非特権ノードとなる場合とが存在する。なお、特権ノードが行う処理等については、後記する。
【００３９】
ノード１は、図１に示したように、ロードバランサ３と通信可能に接続されるともに、クラスタを構成する自身以外の他のノード１と通信可能に接続される。また、このノード１は、ロードバランサ３を介してクライアント２からメッセージを受け取ると、そのメッセージを、担当するノード１（自身を含む）に振り分け、そのメッセージの信号処理を実行する。また、特権ノードとなるノード１は、分散処理システム１０００に属するノード１の減設・増設に関する情報を受信し、前記した、手法（１）Minimum Adjustment法、手法（２）Full Justification法のいずれかを実行することにより、ＩＤ空間上において対象となるノード１のノードＩＤを変更（具体的には、後記する振り分けＩＤテーブル２００を更新）して、負荷の偏りの低減を実現する。
このノード１は、図３に示すように、制御部１０と、入出力部２０と、記憶部３０とを含んで構成される。
【００４０】
入出力部２０は、ロードバランサ３や、自身以外の他のノード１との間の情報の入出力を行う。また、この入出力部２０は、通信回線を介して情報の送受信を行う通信インタフェース（図示省略）と、キーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェース（図示省略）とから構成される。
【００４１】
記憶部３０は、ハードディスクやフラッシュメモリ、ＲＡＭ（Random Access Memory）等の記憶手段からなり、処理の対象となるデータ３００や、ノード識別子管理テーブル１００（図４参照）、振り分けＩＤテーブル（振り分けＩＤ情報）２００（図５参照）、ノード１自身のノード負荷を計測した情報であるノード負荷計測情報４００が記憶される。さらに、ノード１が特権ノードである場合には、各ノード１のノード負荷情報をまとめた（収集した）情報であるシステム負荷情報５００が記憶される。なお、この記憶部３０に記憶される各情報についての詳細は後記する。
【００４２】
制御部１０は、ノード１全体の制御を司り、ノード識別子管理部１１、振り分け部１２、信号処理部１３、ノード負荷計測部１４およびスロット最適化処理部１５を含んで構成される。なお、この制御部１０は、例えば、記憶部３０に格納されたプログラムをＣＰＵ（Central Processing Unit）（図示省略）がＲＡＭ（図示省略）に展開し実行することで実現される。
【００４３】
ノード識別子管理部１１は、分散処理システム１０００においてクラスタを構成する各ノード１のノード情報（ＩＰアドレス等）および各ノード１が担当するＩＤ空間を管理する。
具体的には、ノード識別子管理部１１は、自身が属する分散処理システム１０００へのノードの離脱（減設）や追加（増設）が発生した場合に、その情報を外部から受信し、分散処理システム１０００を構成するノード１の識別情報等が記憶されたノード識別子管理テーブル１００を更新する。
【００４４】
図４は、本実施形態に係るノード識別子管理テーブル１００のデータ構成例を示す図である。
図４に示すように、ノード識別子管理テーブル１００には、分散処理システム１０００を構成する各ノード１のノード識別子１０１とアドレス１０２（例えば、ＩＰアドレス）とが対応付けられて格納される。
【００４５】
このノード識別子１０１は、例えば、当該分散処理システム１０００内において予め設定される特定のノード（例えば、ノード識別子１０１の昇順に設定）のノード識別子管理部１１で付与され、当該分散処理システム１０００内の各ノード１に配信される。なお、このノード識別子１０１は、コンシステント・ハッシュのＩＤ空間において仮想ＩＤを用いる場合、仮想ＩＤ毎に付与される。
【００４６】
また、ノード識別子管理部１１は、ノード１の減設・増設について受信した情報を、スロット最適化処理部１５に出力するとともに、そのスロット最適化処理部１５の処理結果(ノードＩＤの変更情報等）に基づき、ノード識別子管理テーブル１００を更新（ノード１の減設・増設を反映）し、さらに、ノード１の担当するＩＤ空間（担当領域：スロット）を変更するため、振り分けＩＤテーブル２００を更新する。
【００４７】
図５は、本実施形態に係る振り分けＩＤテーブル（振り分けＩＤ情報）２００のデータ構成例を示す図である。
図５に示すように、振り分けＩＤテーブル２００には、ノード識別子２０１に対応付けて、そのノード１が担当するＩＤ空間２０２（担当領域：スロット）が格納される。このノード識別子２０１は、図４のノード識別子１０１と同様の情報である。図５に示す例では、ＩＤ空間の全ＩＤ数が「０」〜「７９９」の「８００」であり、例えば、ノード識別子２０１が「Ａ」のノード１が、担当するＩＤ空間２０２として「０〜１９９」について担当することを示している。また、この振り分けＩＤテーブル２００において、ノード識別子２０１が「Ａ」のノード１（ノード「Ａ」）のＩＤ空間上のノードＩＤは、「１９９」であり、以下同様に、ノード「Ｂ」のＩＤ空間上でのノードＩＤは「３９９」であり、ノード「Ｃ］のＩＤ空間上でのノードＩＤは「５９９」であり、ノード「Ｄ］のＩＤ空間上でのノードＩＤは「７９９」である。そして、ノード識別子管理部１１は、振り分けＩＤテーブル２００において、各ノード１のノードＩＤを昇順にソートし、連続したＩＤ空間２０２として管理する。
なお、本実施形態においては、閉じたＩＤ空間上において各ＩＤを時計回りに配置し、データのＩＤから時計回りに辿った場合に最初に当たったノードをそのデータの担当として説明する。しかしながら、ＩＤ空間上において各ＩＤを反時計回りに配置し、データのＩＤから反時計回りに辿った場合に最初に当たったノードをそのデータの担当とするように構成してもよい。つまり、所定の方向回りにＩＤ空間上におけるＩＤを設定することができる。
【００４８】
分散処理システム１０００内の特権ノードのノード識別子管理部１１は、各ノード１に対して、最新のノード識別子管理テーブル１００および振り分けＩＤテーブル２００を送信する。これにより、各ノード１のノード識別子管理部１１は、ノード識別子管理テーブル１００および振り分けＩＤテーブル２００を常に最新の状態に更新して保持する。このようにすることにより、分散処理システム１０００内の各ノード１には、同一のノード識別子管理テーブル１００および振り分けＩＤテーブル２００が保持される。
【００４９】
また、特権ノードは、例えば、このノード識別子管理テーブル１００（図４）の一番上の行のノード１から順に、特権ノードとなるように設定される。ノード１が新たに特権ノードになった場合、自身が特権ノードであることを示す情報を、各ノード１等に送信する。そして、特権ノードは、クラスタ内のノード１について、ＩＤ空間上での配置変更（ノードＩＤの変更等）があった場合に、自身の振り分けＩＤテーブル２００を更新し、その更新情報を、各ノード１に配信する。
【００５０】
図３に戻り、振り分け部１２は、ロードバランサ３等を介してクライアント２から受信したメッセージ内の情報（「振り分けキー」）をもとに「ｈａｓｈ（ｋｅｙ）」を算出し、振り分けＩＤテーブル２００を参照して、そのメッセージの処理を担当するノード１を特定する。そして、振り分け部１２は、特定したノード１のアドレスの情報を、ノード識別子管理テーブル１００を参照して取得し、特定したノード１へメッセージの振り分け（送信）を行う。
また、信号処理部１３は、自身のノード１が担当するデータに関するメッセージの信号処理を実行する。
【００５１】
ノード負荷計測部１４は、例えば、所定の周期において、ノード負荷計測要求等を特権ノードから受信した場合に、自身のノード１のノード負荷（負荷情報）を計測し、自身の記憶部３０内にノード負荷計測情報４００として記憶する。そして、ノード負荷計測部１４は、その計測したノード負荷（負荷情報）を、特権ノードに送信する。
ノード負荷計測部１４が計測するノード負荷は、例えば、メモリ使用量、ＣＰＵ使用率、データ個数等である。
【００５２】
以下説明する、スロット最適化処理部１５は、各ノード１が備えるが、ノード１自身が特権ノードの場合に動作する。
ノード１のスロット最適化処理部１５は、手法（１）Minimum Adjustment法、手法（２）Full Justification法のいずれかを実行することにより、ＩＤ空間上のノードＩＤを変更し、負荷の偏りの低減を実現する。なお、スロット最適化処理部１５が、手法（１）Minimum Adjustment法、手法（２）Full Justification法のどちらを実行するかは、予め分散処理システム１０００の管理者等により設定される。
【００５３】
（手法（１）Minimum Adjustment法）
手法（１）Minimum Adjustment法は、分散処理システム１０００を構成するノード１に減設や増設が発生した場合に、減設ノードや増設ノードに隣接するノード（隣接ノード）間で、担当領域を等分割するようにしてノードＩＤを変更する。
【００５４】
〔減設時の処理〕
スロット最適化処理部１５が、手法（１）Minimum Adjustment法により、ノード減設時において実行する処理について説明する。
スロット最適化処理部１５は、まず、ノードＩＤを変更するノード１として、減設ノードの時計回り側に位置するノード１（以下、「次ノード」と称する場合がある。）、若しくは、減設ノードの反時計回り側に位置するノード１（以下、「前ノード」と称する場合がある。）を決定する。ここで、スロット最適化処理部１５は、減設ノードの時計回り側で２つ目に位置するノード１（以下、「次々ノード」と称する場合がある。）と、前ノードとについて、担当領域の大きさ（スロットのサイズ）、負荷の大きさ、データ個数の多さのいずれかを比較する。そして、スロット最適化処理部１５は、次々ノードの値の方が小さければ、次ノードをノードＩＤを変更するノード１として決定し、前ノードの値の方が小さければ、前ノードをノードＩＤを変更するノード１として決定する。
【００５５】
具体的には、スロット最適化処理部１５は、担当領域の大きさ（スロットのサイズ）を基準とする場合には、減設ノードについての、次々ノードと前ノードのスロットのサイズを比較し、スロットのサイズが小さい側のノード１を選択する。スロット最適化処理部１５は、負荷の大きさを基準とする場合には、減設ノードについての、次々ノードと前ノードの負荷を比較し、負荷が少ない側のノード１を選択する。また、スロット最適化処理部１５は、データ個数の多さを基準とする場合には、減設ノードについての、次々ノードと前ノードのデータ個数を比較し、データ個数の少ない側のノード１を選択する。このようにすることで、ノード１間の負荷の偏りの増大をできるだけ回避するようにして、ノードＩＤを変更するノード１を決定することができる。
【００５６】
スロット最適化処理部１５は、ノードＩＤを変更するノード１として、減設ノードの時計回り側に位置するノード１（次ノード）、若しくは、減設ノードの反時計回り側に位置するノード１（前ノード）のいずれかを決定すると、以下の式に基づき、ノードＩＤを算出する。
【００５７】
［次ノードに決定した場合］
スロット最適化処理部１５は、ノードＩＤを変更するノード１を次ノードに決定した場合、以下の式（１）により、変更するノードＩＤを算出する。
【００５８】
減設ノードの時計回り側に位置するノード（次ノード）のＩＤ＝
（減設ノードの反時計回り側に位置するノード（前ノード）のＩＤ ＋
時計回り側で２つ目に位置するノード（次々ノード）のＩＤ）÷２    ・・・式（１）
【００５９】
前記した図２（ｂ）に示す例では、減設ノード（ノード「Ｃ」）の反時計回り側に位置するノード（前ノード：ノード「Ｂ」）のＩＤと、減設ノード（ノード「Ｃ」）の時計回り側で２つ目に位置するノード（次々ノード：ノード「Ａ」）のＩＤとを足して、２で割る（等分割する）ことにより、減設ノードの時計回り側に位置するノード（次ノード：ノード「Ｄ」）のＩＤが算出される。
なお、等分割したＩＤの値が割り切れない場合は、例えば、小数点以下を切り捨てる等を予め設定しておく（以下同様）。また、コンシステント・ハッシュのＩＤ空間は、閉じたＩＤ空間（つまり環状）であるため、設定されたＩＤの最大値の次のＩＤは「０」に戻る。よって、ＩＤが「０」をまたぐ場合は、それを考慮した上で式（１）を用いる。なお、後記する式（２）、式（３），式（５）の場合も同様である。
【００６０】
このようにして、スロット最適化処理部１５は、減設ノードの次ノードの新たなＩＤを算出する。そして、スロット最適化処理部１５は、算出した次ノードのＩＤを、ノード識別子管理部１１に出力して、振り分けＩＤテーブル２００を更新させる。これにより、減設ノードの時計回り側に位置するノード（次ノード）への負荷の偏りを低減することができる。
【００６１】
［前ノードに決定した場合］
スロット最適化処理部１５は、ノードＩＤを変更するノード１を前ノードに決定した場合、以下の式（２）により、変更するノードＩＤを算出する。
【００６２】
減設ノードの反時計回り側に位置するノード（前ノード）のＩＤ＝
（減設ノードの反時計回り側で２つ目に位置するノード（前々ノード）のＩＤ ＋
時計回り側に位置するノード（次ノード）のＩＤ）÷２    ・・・式（２）
【００６３】
図６に示す例では、図６（ａ）に示すＩＤ空間上で、ノード「Ｃ」が減設した場合に、図６（ｂ）に示すように、減設ノード（ノード「Ｃ」）の反時計回り側で２つ目に位置するノード（前々ノード：ノード「Ａ」）のＩＤと、減設ノード（ノード「Ｃ」）の時計回り側に位置するノード（次ノード：ノード「Ｄ」）のＩＤとを足して、２で割る（等分割）することにより、減設ノードの反時計回り側に位置するノード（前ノード：ノード「Ｂ」）のＩＤが算出される。
【００６４】
このようにして、スロット最適化処理部１５は、減設ノードの反時計回り側に位置するノード（前ノード）の新たなＩＤを算出する。そして、スロット最適化処理部１５は、算出した前ノードのＩＤを、ノード識別子管理部１１に出力して、振り分けＩＤテーブル２００を更新させる。これにより、前ノードのＩＤが、ＩＤ空間上で時計回り側に移動する。よって、減設ノードの時計回り側に位置するノード（次ノード）への負荷の偏りを低減することができる。
【００６５】
なお、上記においては、スロット最適化処理部１５は、まず、ノードＩＤを変更するノード１として、減設ノードの時計回り側に位置するノード１（次ノード）、若しくは、減設ノードの反時計回り側に位置するノード１（前ノード）のいずれかを決定するものとして説明した。しかしながら、スロット最適化処理部１５に、ノードＩＤを変更するノード１として、減設ノードの次ノード、減設ノードの前ノードのいずれかを予め設定しておき、式（１）または式（２）のいずれかを用いて、変更後のノードＩＤを算出するようにしてもよい。
【００６６】
〔増設時の処理〕
スロット最適化処理部１５が、手法（１）Minimum Adjustment法において、ノード増設時において実行する処理について説明する。スロット最適化処理部１５は、各ノード１のスロットの大きさを比較し、最も大きいスロットを等分割する位置に、増設するノードを配置する。以下、具体的に説明する。
【００６７】
まず、スロット最適化処理部１５は、振り分けＩＤテーブル２００（図５）を参照し、増設前の各ノード１の担当領域の大きさ（スロットのサイズ）が、最も大きいノード１を抽出し、その抽出したノード１の担当領域を分割する位置に、新たに増設するノード１（増設ノード）を配置するように割り当てる。なお、この担当領域が分割されるノード１を、以下、「分割ノード」と称する場合がある。
【００６８】
続いて、スロット最適化処理部１５は、以下の式（３）により、増設ノードのノードＩＤを算出する。
【００６９】
増設ノードのＩＤ＝
（増設ノードによりスロットを分割されるノード（分割ノード）のＩＤ ＋
分割ノードの反時計回り側に位置するノード（前ノード）のＩＤ ）÷２  
・・・式（３）
【００７０】
具体的には、図７（ａ）に示すように、ＩＤ空間上にノード「Ａ」「Ｂ」「Ｄ」が配置され、各データを処理している場合において、ノード「Ｃ」を増設する指示をノード１が受けたものとする。ここで、スロット最適化処理部１５は、振り分けＩＤテーブル２００を参照し、担当領域の大きさ（スロットのサイズ）が最も大きいノード１として、ノード「Ｄ」を抽出する。この場合、スロット最適化処理部１５は、式（３）を用いて、ノード「Ｄ」のノードＩＤと、ノード「Ｂ」のノードＩＤとを、足して２で割る（等分割する）ことにより、増設ノードであるノード「Ｃ」のノードＩＤを算出する（図７（ｂ）参照）。
【００７１】
このようにして、スロット最適化処理部１５は、増設ノードのノードＩＤを算出する。そして、スロット最適化処理部１５は、算出した増設ノードのノードＩＤを、ノード識別子管理部１１に出力して、振り分けＩＤテーブル２００を更新させる。これにより、ノード１の増設時において、分割ノードと増設ノードの間の負荷の偏りを回避することができる。
【００７２】
（手法（２）Full Justification法）
次に、手法（２）Full Justification法について説明する。
手法（２）Full Justification法は、分散処理システム１０００に属するノード１の減設が発生した場合、または、ノード１を増設する場合に、各ノード１の担当領域が等分割されるように、特定のノード（後記する「起点ノード」）以外の他の全てのノード１のノードＩＤを変更する。
【００７３】
〔減設時の処理〕
スロット最適化処理部１５が、手法（２）Full Justification法により、ノード減設時において実行する処理について説明する。
スロット最適化処理部１５は、まず、データの移動量が最も少ないノードを起点ノードとして選択し（起点ノード選択処理）、その後、選択した起点ノードを基準として、各ノード１の担当領域の大きさ（スロットのサイズ）が等分割されるように、起点ノード以外の各ノード１のノードＩＤを決定する（ノードＩＤの更新処理）。
【００７４】
図８は、手法（２）Full Justification法の減設時における起点ノード選択処理を説明するための図である。スロット最適化処理部１５は、各ノード１のデータの移動量が最も少なくなるように起点ノードを選択する。
そのため、スロット最適化処理部１５は、減設後の各ノード１の平均負荷（ノード平均負荷μ）を算出する。そして、式（４）に示すように、そのノード平均負荷μからのユークリッド距離合計ｄＮが最も小さいノード「Ｎ」を選択する。
【００７５】
【数１】
0006387333.tif 000002
【００７６】
図８（ａ）に示すように、４つのノード１（ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」）がＩＤ空間上に配置されている場合において、ノード「Ｃ」が減設した場合を考える。図８においては、説明を分かりやすくするため、各ノードの負荷をデータ（図の丸「〇」）で示し、各データ「〇」の負荷はすべて同じ「１」であるものとして説明する。
まず、スロット最適化処理部１５は、ノード「Ｃ］が減設した後の、ノード平均負荷μを、μ＝１２／３＝４として算出する。ここで、Ｎ（ノード数）が「３」であり、データ数が、「１２」である。
【００７７】
このとき、図８（ｂ）に示すように、ノード「Ａ」を起点とし、各ノード１（ノード「Ａ」「Ｂ」「Ｄ」）の担当領域の大きさ（スロットのサイズ）を等分割した場合において、ユークリッド距離合計ｄＡは、ノード「Ａ」、ノード「Ｂ」、ノード「Ｄ」の順に合計し、
ｄＡ＝｜３−４｜＋｜５−４｜＋｜４−４｜＝１＋１＋０＝２
となる。
【００７８】
また、図８（ｃ）に示すように、ノード「Ｂ」を起点とし、各ノード１（ノード「Ａ」「Ｂ」「Ｄ」）の担当領域の大きさ（スロットのサイズ）を等分割した場合において、ユークリッド距離合計ｄＢは、ノード「Ａ」、ノード「Ｂ」、ノード「Ｄ」の順に合計し、
ｄＢ＝｜３−４｜＋｜５−４｜＋｜４−４｜＝１＋１＋０＝２
となる。
【００７９】
また、図８（ｄ）に示すように、ノード「Ｄ」を起点とし、各ノード１（ノード「Ａ」「Ｂ」「Ｄ」）の担当領域の大きさ（スロットのサイズ）を等分割した場合において、ユークリッド距離合計ｄＤは、ノード「Ａ」、ノード「Ｂ」、ノード「Ｄ」の順に合計し、
ｄＤ＝｜４−４｜＋｜４−４｜＋｜４−４｜＝０＋０＋０＝０
となる。
【００８０】
以上より、スロット最適化処理部１５は、図８に示す場合においては、ノード平均負荷μ（＝４）からのユークリッド距離合計ｄＮが最も小さいノード「Ｄ」（ｄＤ＝０）を起点ノードとして選択する。
【００８１】
そして、スロット最適化処理部１５は、選択した起点ノードを基準として、担当領域の大きさ（スロットのサイズ）が等分割となるように、各ノード１のノードＩＤを、次の式（５）を用いて算出する。
【００８２】
ノードＩＤ＝ＩＤ空間全体の大きさ÷Ｎ×ｋ＋起点ノードのノードＩＤ  ・・・式（５）
ここで、Ｎ＝（減設後の）ノード数、０≦ｋ＜Ｎ（ｋは正の整数）である。
【００８３】
このようにして、スロット最適化処理部１５は、ノード１を減設する場合において、最もデータの移動量が少ない起点ノードを選択し、その起点ノードを基準として、各ノード１の担当領域の大きさ（スロットのサイズ）が等分割されるように、起点ノード以外のノード１それぞれのノードＩＤを算出する。そして、スロット最適化処理部１５は、算出した起点ノード以外のノード１それぞれのノードＩＤをノード識別子管理部１１に出力して、振り分けＩＤテーブル２００を更新させる。これにより、各ノードの負荷に偏りがないようにすることができる。
【００８４】
〔増設時の処理〕
スロット最適化処理部１５が、手法（２）Full Justification法において、ノード増設時において実行する処理について説明する。
スロット最適化処理部１５は、減設時の処理と同様に、まず、データの移動量が最も少ないノードを起点ノードとして選択し（起点ノード選択処理）、その後、選択した起点ノードを基準として、各ノード１の担当領域の大きさ（スロットのサイズ）が等分割されるように、起点ノード以外の各ノード１のノードＩＤを決定する（ノードＩＤの更新処理）。
【００８５】
図９は、手法（２）Full Justification法の増設時における起点ノード選択処理を説明するための図である。スロット最適化処理部１５は、各ノード１のデータの移動量が最も少なくなるように起点ノードを選択する。
そのため、スロット最適化処理部１５は、増設後の各ノードの平均負荷（ノード平均負荷μ）を算出する。そして、前記した式（４）に示すように、そのノード平均負荷μからのユークリッド距離合計ｄＮが最も小さいノード「Ｎ」を選択する。
【００８６】
図９（ａ）に示すように、３つのノード１（ノード「Ａ」「Ｂ」「Ｄ」）がＩＤ空間上に配置されている場合において、ノード「Ｃ」を増設する場合を考える。図９においては、説明を分かりやすくするため、各ノードの負荷をデータ（図の丸「〇」）で示し、各データ「〇」の負荷はすべて同じ「１」であるものとして説明する。
【００８７】
まず、スロット最適化処理部１５は、振り分けＩＤテーブル２００（図５）を参照し、増設前の各ノード１の担当領域の大きさ（スロットのサイズ）が最も大きいノード１を抽出し、その抽出したノード１の担当領域を分割する位置に、新たに増設するノード１を配置するように割り当てる。なお、各ノード１の担当領域の大きさ（スロットのサイズ）が同じ場合には、ランダムに新たに増設するノード１の位置を割り当てる。
図９（ａ）においては、ノード「Ｄ」の担当領域に、新たなノード「Ｃ」を増設するものとして説明する。
【００８８】
次に、スロット最適化処理部１５は、ノード「Ｃ」を増設した後の、ノード平均負荷μを計算する。ここでは、ノード平均負荷μ＝１２／４＝３となる。ここで、Ｎ（ノード数）が「４」であり、データ数が、「１２」である。
【００８９】
このとき、図９（ｂ）に示すように、ノード「Ａ」を起点として、各ノード１（ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」）の担当領域の大きさ（スロットのサイズ）を等分割した場合において、ユークリッド距離合計ｄＡは、ノード「Ａ」、ノード「Ｂ」、ノード「Ｃ」、ノード「Ｄ」の順に合計し、
ｄＡ＝｜３−３｜＋｜４−３｜＋｜２−３｜＋｜３−３｜＝０＋１＋１＋０＝２
となる。
【００９０】
また、図９（ｃ）に示すように、ノード「Ｂ」を起点とし、各ノード１（ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」）の担当領域の大きさ（スロットのサイズ）を等分割した場合において、ユークリッド距離合計ｄＢは、ノード「Ａ」、ノード「Ｂ」、ノード「Ｃ」、ノード「Ｄ」の順に合計し、
ｄＢ＝｜３−３｜＋｜３−３｜＋｜３−３｜＋｜３−３｜＝０＋０＋０＋０＝０
となる。
【００９１】
また、図９（ｄ）に示すように、ノード「Ｄ」を起点とし、各ノード１（ノード「Ａ」「Ｂ」「Ｃ」「Ｄ」）の担当領域の大きさ（スロットのサイズ）を等分割した場合において、ユークリッド距離合計ｄＤは、ノード「Ａ」、ノード「Ｂ」、ノード「Ｃ」、ノード「Ｄ」の順に合計し、
ｄＤ＝｜３−３｜＋｜４−３｜＋｜３−３｜＋｜２−３｜＝０＋１＋０＋１＝２
となる。
【００９２】
以上より、スロット最適化処理部１５は、図９に示す場合においては、ノード平均負荷μ（＝３）からのユークリッド距離合計ｄＮが最も小さいノード「Ｂ」（ｄＢ＝０）を起点ノードとして選択する。
【００９３】
そして、スロット最適化処理部１５は、選択した起点ノードを基準として、担当領域の大きさ（スロットのサイズ）が等分割となるように、各ノード１のノードＩＤを、前記した式（５）を用いて算出する。ただし、ここで、Ｎ＝（増設後の）ノード数である。
【００９４】
このようにして、スロット最適化処理部１５は、ノード１を増設する場合において、最もデータの移動量が少ない起点ノードを選択し、その起点ノードを基準として、各ノード１の担当領域の大きさ（スロットのサイズ）が等分割されるように、起点ノード以外のノード１それぞれのノードＩＤを算出する。そして、スロット最適化処理部１５は、算出した起点ノード以外のノード１それぞれのノードＩＤをノード識別子管理部１１に出力して、振り分けＩＤテーブル２００を更新させる。これにより、各ノードの負荷に偏りがないようにすることができる。
なお、上記の説明では、各ノード１の平均負荷（ノード平均負荷）を「μ」として、式（４）により、ユークリッド距離合計ｄＮを算出した。しかしながら、これに限定されず、スロット最適化処理部１５は、各ノード１の平均スロットサイズや、各ノードの平均データ個数を用いて、ユークリッド距離合計ｄＮを算出し、起点ノードを選択してもよい。
【００９５】
＜処理の流れ＞
次に、本実施形態に係るノード１が実行する、負荷分散処理(負荷の偏りを低減する処理）の流れについて、スロット最適化処理部１５が実行する、手法（１）Minimum Adjustment法、手法（２）Full Justification法のそれぞれについて説明する。なお、以下に説明する負荷分散処理は、分散処理システム１０００を構成するノード１のうち、特権ノードが行う処理である。
【００９６】
≪手法（１）Minimum Adjustment法≫
図１０は、本実施形態に係るノード１が、負荷分散処理として、手法（１）Minimum Adjustment法を実行する場合の処理の流れを示すフローチャートである。
【００９７】
まず、ノード１のスロット最適化処理部１５は、分散処理システム１０００を構成する各ノード１から、各ノードそれぞれの負荷情報（例えば、メモリ使用量、ＣＰＵ使用率、データ個数等）を、所定の時間間隔で受信する（ステップＳ１）。
【００９８】
続いて、スロット最適化処理部１５は、分散処理システム１０００を構成するノード１が減設されたか否かを判定する（ステップＳ２）。ここで、スロット最適化処理部１５は、ノード１のノード識別子管理部１１が、分散処理システム１０００の管理装置から特定ノードの減設指示を受信したり、各ノード１の死活監視を行い特定のノード１が減設したことを検知したりすることにより、ノード１の減設（減設ノード）を認識することができる。スロット最適化処理部１５は、ノード１が減設されていない場合には（ステップＳ２→Ｎｏ）、ステップＳ７に進む。一方、ノード１が減設された場合には（ステップＳ２→Ｙｅｓ）、次のステップＳ３に進む。
【００９９】
ステップＳ３において、スロット最適化処理部１５は、減設ノードに隣接するノード１のうち、ノードＩＤを変更するノード１を決定する。
具体的には、スロット最適化処理部１５は、減設ノードの時計回り側で２つ目に位置するノード１（次々ノード）と、減設ノードの反時計回り側に位置するノード１（前ノード）についての、担当領域の大きさ（スロットのサイズ）、負荷の大きさ、データ個数の多さのいずれかを比較する。そして、スロット最適化処理部１５は、次々ノードの値の方が小さければ、次ノードをノードＩＤを変更するノード１として決定し、前ノードの値の方が小さければ、前ノードをノードＩＤを変更するノード１として決定する。
【０１００】
そして、スロット最適化処理部１５は、ノードＩＤを変更するノード１を次ノードに決定した場合には（ステップＳ４→Ｙｅｓ）、次のステップＳ５に進む。一方、スロット最適化処理部１５は、ノードＩＤを変更するノード１を前ノードに決定した場合には（ステップＳ４→Ｎｏ）、次のステップＳ６に進む。
【０１０１】
ノードＩＤを変更するノード１を次ノードに決定した場合（ステップＳ４→Ｙｅｓ）、ステップＳ５において、スロット最適化処理部１５は、前記した式（１）を用いて、次ノードのノードＩＤを算出する。そして、ステップＳ１０に進む。
【０１０２】
一方、ノードＩＤを変更するノード１を前ノードに決定した場合（ステップＳ４→Ｎｏ）、ステップＳ６において、スロット最適化処理部１５は、前記した式（２）を用いて、前ノードのＩＤを算出する。そして、ステップＳ１０に進む。
【０１０３】
また、ステップＳ２においてノード１が減設されていないと判定された場合（ステップＳ２→Ｎｏ）、スロット最適化処理部１５は、分散処理システム１０００を構成するノード１を増設するか否かを判定する（ステップＳ７）。ここで、スロット最適化処理部１５は、ノード１のノード識別子管理部１１が、分散処理システム１０００の管理装置から、ノード１の増設指示を受信したこと等により、ノード１を増設するか否かを判定することができる。スロット最適化処理部１５は、ノード１を増設しない（増設指示を受けていない）と判定した場合には（ステップＳ７→Ｎｏ）、ステップＳ１に戻り、所定の時間間隔で各ノードそれぞれから新たな負荷情報を受信して、処理を続ける。一方、スロット最適化処理部１５は、ノード１を増設すると判定した場合には（ステップＳ７→Ｙｅｓ）、次のステップＳ８に進む。
【０１０４】
ステップＳ８において、スロット最適化処理部１５は、振り分けＩＤテーブル２００を参照して、増設前の各ノード１の担当領域の大きさ（スロットのサイズ）を比較し、担当領域が最も大きいノード１を抽出して、その抽出したノード１の担当領域を分割する位置に、新たに増設するノード１を割り当てる。なお、各ノード１の担当領域の大きさ（スロットのサイズ）が同じ場合には、ランダムに新たに増設するノード１の位置を割り当てる。そして、次のステップＳ９に進む。
【０１０５】
ステップＳ９において、スロット最適化処理部１５は、前記した式（３）を用いて、増設ノードのノードＩＤを算出する。そして、ステップＳ１０に進む。
【０１０６】
ステップＳ１０において、ノード識別子管理部１１は、ステップＳ５、ステップＳ６、または、ステップＳ９において算出した変更後のノードＩＤまたは増設ノードのノードＩＤを、スロット最適化処理部１５から取得し、振り分けＩＤテーブル２００およびノード識別子管理テーブル１００を更新する。
具体的には、ノード識別子管理部１１は、ノード１を減設する場合には、振り分けＩＤテーブル２００において、減設ノードのノード識別子２０１を削除するとともに、減設ノードの次ノードまたは前ノードのノードＩＤを変更する（ＩＤ空間２０２の担当領域を変更する）。また、ノード識別子管理部１１は、減設ノードのレコード（ノード識別子１０１およびアドレス１０２）をノード識別子管理テーブル１００から削除する。
一方、ノード識別子管理部１１は、ノード１を増設する場合には、増設ノードのノードＩＤに基づき、振り分けＩＤテーブル２００において、増設するノード１のレコードを追加する。さらに、ノード識別子管理部１１は、ノード識別子管理テーブル１００において、増設するノード１のレコードを追加する。
【０１０７】
続いて、ノード識別子管理部１１は、更新した振り分けＩＤテーブル２００およびノード識別子管理テーブル１００を、分散処理システム１０００を構成する各ノード１に送信する（ステップＳ１１）。これにより、各ノード１において、振り分けＩＤテーブル２００およびノード識別子管理テーブル１００が更新され、システム全体として同期をとることができる。そして、ノード１は、負荷分散処理を終了する。
【０１０８】
≪手法（２）Full Justification法≫
図１１は、本実施形態に係るノード１が、負荷分散処理(負荷の偏りを低減する処理）として、手法（２）Full Justification法を実行する場合の処理の流れを示すフローチャートである。
【０１０９】
まず、ノード１のスロット最適化処理部１５は、分散処理システム１０００を構成する各ノード１から、各ノードそれぞれの負荷情報（例えば、メモリ使用量、ＣＰＵ使用率、データ個数等）を、所定の時間間隔で受信する（ステップＳ２０）。
【０１１０】
続いて、スロット最適化処理部１５は、分散処理システム１０００を構成するノード１が減設されたか否かを判定する（ステップＳ２１）。ここで、スロット最適化処理部１５は、分散処理システム１０００を構成するノード１が減設されたと判定した場合には（ステップＳ２１→Ｙｅｓ）、ステップＳ２４に進む。一方、スロット最適化処理部１５は、減設されたと判定しなかった場合には（ステップＳ２１→Ｎｏ）、次のステップＳ２２に進む。
【０１１１】
ステップＳ２２において、スロット最適化処理部１５は、分散処理システム１０００を構成するノード１を増設するか否かを判定する。ここで、スロット最適化処理部１５は、ノード１のノード識別子管理部１１が、分散処理システム１０００の管理装置から、ノード１の増設指示を受信したこと等により、ノード１を増設するか否かを判定することができる。スロット最適化処理部１５は、ノード１を増設しない（増設指示を受けていない）と判定した場合には（ステップＳ２２→Ｎｏ）、ステップＳ２０に戻り、所定の時間間隔で各ノードそれぞれから新たな負荷情報を受信して、処理を続ける。一方、スロット最適化処理部１５は、ノード１を増設すると判定した場合には（ステップＳ２２→Ｙｅｓ）、次のステップＳ２３に進む。
【０１１２】
ステップＳ２３において、スロット最適化処理部１５は、振り分けＩＤテーブル２００を参照して、増設前の各ノード１の担当領域の大きさ（スロットのサイズ）を比較し、担当領域が最も大きいノード１を抽出して、その抽出したノード１の担当領域を分割する位置に、新たに増設するノード１を割り当てる。なお、各ノード１の担当領域の大きさ（スロットのサイズ）が同じ場合には、ランダムに新たに増設するノード１の位置を割り当てる。そして、次のステップＳ２４に進む。
【０１１３】
ステップＳ２４において、スロット最適化処理部１５は、減設（または増設）後のノード数と、各ノード１の負荷情報を用いて、ノード平均負荷μを算出する。
【０１１４】
続いて、スロット最適化処理部１５は、前記した式（４）を用いて、各ノード１を起点として場合のユークリッド距離合計ｄＮを算出する（ステップＳ２５）。
そして、スロット最適化処理部１５は、算出した各ノード１についてのユークリッド距離合計ｄＮのうち、そのユークリッド距離合計ｄＮが最も小さいノード１を、起点ノードとして選択する（ステップＳ２６）。
【０１１５】
次に、スロット最適化処理部１５は、選択した起点ノードを基準として、担当領域の大きさ（スロットのサイズ）が等分割となるように、各ノード１のノードＩＤを、前記した式（５）を用いて算出する（ステップＳ２７）。
【０１１６】
続いて、ノード識別子管理部１１は、ステップＳ２７において算出した変更後のノードＩＤを、スロット最適化処理部１５から取得し、振り分けＩＤテーブル２００およびノード識別子管理テーブル１００を更新する（ステップＳ２８）。
具体的には、ノード識別子管理部１１は、振り分けＩＤテーブル２００において、ノード１を減設する場合は、減設ノードのレコード（ノード識別子１０１およびアドレス１０２）を削除するとともに、ノードＩＤを変更したノード１について、ＩＤ空間２０２の担当領域を変更する。また、ノード識別子管理部１１は、振り分けＩＤテーブル２００において、ノード１を増設する場合は、増設するノードのレコードを追加する。さらに、ノード識別子管理部１１は、ノード識別子管理テーブル１００において、減設の場合は、減設ノードのレコードを削除し、増設の場合は、増設ノードのレコードを追加する。
【０１１７】
続いて、ノード識別子管理部１１は、更新した振り分けＩＤテーブル２００およびノード識別子管理テーブル１００を、分散処理システム１０００を構成する各ノード１に送信する（ステップＳ２９）。これにより、各ノード１において、振り分けＩＤテーブル２００およびノード識別子管理テーブル１００が更新され、システム全体として同期をとることができる。そして、ノード１は、負荷分散処理を終了する。
【０１１８】
以上説明したように、本実施形態に係るノード１およびスロット最適化方法によれば、分散処理システム１０００の特権ノードとなるノード１が、負荷分散の手法として、手法（１）Minimum Adjustment法、手法（２）Full Justification法のいずれかを実行する。これにより、分散処理システム１０００を構成するノード１の減設・増設動作時において、特定ノードへの負荷の偏りを低減することができる。
【０１１９】
なお、手法（１）Minimum Adjustment法は、手法（２）Full Justification法に比べ、データの移動量が少ないため、処理が高速であるという特徴がある。よって、分散処理システム１０００を構成するノード１の減設・増設の頻度が高い場合に特に有効である。一方、手法（２）Full Justification法は、手法（１）Minimum Adjustment法に比べ、データの移動量が多いため処理が低速になるが、特定ノードへ負荷が偏らずに均等とすることができる。よって、分散処理システム１０００を構成するノード１の減設・増設の頻度が低い場合に特に有効である。
【符号の説明】
【０１２０】
１      ノード
２      クライアント
３      ロードバランサ
１０    制御部
１１    ノード識別子管理部
１２    振り分け部
１３    信号処理部
１４    ノード負荷計測部
１５    スロット最適化処理部
２０    入出力部
３０    記憶部
１００  ノード識別子管理テーブル
２００  振り分けＩＤテーブル（振り分けＩＤ情報）
３００  データ
４００  ノード負荷計測情報
５００  システム負荷情報
１０００  分散処理システム
【図１】
0006387333.tif 000003
【図２】
0006387333.tif 000004
【図３】
0006387333.tif 000005
【図４】
0006387333.tif 000006
【図５】
0006387333.tif 000007
【図６】
0006387333.tif 000008
【図７】
0006387333.tif 000009
【図８】
0006387333.tif 000010
【図９】
0006387333.tif 000011
【図１０】
0006387333.tif 000012
【図１１】
0006387333.tif 000013
【図１２】
0006387333.tif 000014