(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年6月23日検索］，インターネット<ＵＲＬ: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年6月23日検索］，インターネット<ＵＲＬ:http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【非特許文献３】入江  道生、他４名、「コンシステント・ハッシュ法におけるデータの複製を意識した負荷分散手法」、社団法人電子情報通信学会、2010年10月、信学技報、IN2010-77、P.69-74
【発明の概要】
【発明が解決しようとする課題】
【０００９】
これらのコンシステント・ハッシュ法や仮想ＩＤ等の従来技術により、ノード間で担当するデータを均一化し負荷を分散させることが可能である。しかしながら、特定ノードにおいて、アクセス頻度の高い、処理時間が長い等でノードに高い負荷を与えるデータ（以下、「高負荷データ」と称する。）が偏って発生するために、各ノードが担当するデータ数自体は均等であっても、ノード間で負荷の偏りが発生する。
【００１０】
従来、このようなコンシステント・ハッシュ法の分散処理システムにおける負荷増大に対する対策としては、新たなノードを増設し、システムをスケールアウトさせて、高負荷となったノードの担当するデータ数を縮小させ負荷を低減する手法がとられている。一方、各ノードのコンシステント・ハッシュのＩＤ空間上での配置変更（以下、「リバランシング」と称する。）を行い、適切に負荷を分散させることにより、増設を行うことなく現行のノード台数で対応可能なケースもある。この場合、コンシステント・ハッシュのＩＤ空間上の隣接ノード間でリバランシングを実行してノード間の負荷の偏りを是正する手法が用いられる。
【００１１】
しかしながら、既存のリバランシング手法では、各ノードの負荷情報を取得し、その負荷情報に基づきリバランシング設計を行い、その設計した結果を用いて実際にリバランシングが実行されるため、リバランシング設計の計算に係る時間（以下、「リバランシング設計時間」と称する場合がある。）によっては、実負荷が適正値に変動したにもかかわらず、リバランシングが実行されてしまう問題があった。このリバランシング設計に係る時間は、ノード数に依存するものであり、数秒から数分におよぶ場合も想定される。つまり、既存のリバランシング手法では、リバランシング設計にかかる時間経過を考慮していないため、リバランシングを実行する時点において、実負荷が適正値に変動しているにもかかわらず、不要なリバランシングを実行してしまう問題があった。
【００１２】
このような背景を鑑みて本発明がなされたのであり、本発明は、時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制することができる、ノード、リバランシングキャンセル方法、および、プログラムを提供することを課題とする。
【課題を解決するための手段】
【００１３】
前記した課題を解決するため、請求項１に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準（１）は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、前記判定基準（２）は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、前記判定基準（３）は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。
【００１４】
また、請求項５に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムが有する前記ノードのリバランシングキャンセル方法であって、前記ノードが、自身のノードの負荷情報を計測するステップと、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行うステップと、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、当該リバランシング設計に基づくリバランシングの実行を中止させるステップと、を実行し、前記判定基準（１）は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、前記判定基準（２）は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、前記判定基準（３）は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であることを特徴とするリバランシングキャンセル方法とした。
【００１５】
このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、リバランシングを中止する。
よって、時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制することができる。
【００１６】
請求項２に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。
【００１７】
このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準である、「リバランシング設計時間の経過後に取得した各ノードの負荷情報が許容範囲に収まっていること」を満たす場合に、リバランシングを中止する。
よって、時間の経過により各ノードの負荷が変動し、許容範囲に収まっている場合に、不要なリバランシングを抑制することができる。
【００１８】
請求項３に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。
【００１９】
このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準である、「各ノードの負荷情報を平均したノード平均負荷を算出し、リバランシング設計の計算前後において、算出したノード平均負荷が所定の基準値以上減少していること」を満たす場合に、リバランシングを中止する。
よって、時間の経過によりノード平均負荷が、所定の基準値以上減少した場合には、システム全体としての負荷が下がっているため、リバランシングの実行を不要と判断し、不要なリバランシングを抑制することができる。
【００２０】
請求項４に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。
【００２１】
このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準である、「各ノードの負荷情報に基づき、負荷が大きい順に各ノードをソートしたノード順位情報を、リバランシング設計の計算前後において作成し、負荷が許容範囲に収まらないノードの順位が、計算前後のノード順位情報において変動があること」を満たす場合に、リバランシングを中止する。
よって、リバランシング設計の計算前後において、負荷が許容範囲に収まらないノードの順位に変動がある場合には、各ノードの負荷状態が安定しておらず、リバランシングを実行しても再度リバランシングを実行すべき状態になる可能性が高くなるため、その時点でのリバランシングの実行を不要と判断する。したがって、不要なリバランシングを抑制することができる。
【００２２】
請求項６に記載の発明は、請求項５に記載のリバランシングキャンセル方法を、コンピュータに実行させるためのプログラムとした。
【００２３】
このようなプログラムによれば、請求項５に記載のリバランシングキャンセル方法を、一般的なコンピュータで実現することができる。
【発明の効果】
【００２４】
本発明によれば、時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制する、ノード、リバランシングキャンセル方法、および、プログラムを提供することができる。
【図面の簡単な説明】
【００２５】
【図１】既存のリバランシング手法の問題点を説明するための図である。
【図２】既存のリバランシング手法の問題点を説明するための図である。
【図３】本実施形態に係る分散処理システムの全体構成を示す図である。
【図４】本実施形態に係る分散処理システムを構成するノードの機能ブロック図である。
【図５】本実施形態に係るノード識別子管理テーブルのデータ構成例を示す図である。
【図６】本実施形態に係る振り分けＩＤテーブルのデータ構成例を示す図である。
【図７】本実施形態に係るノードが実行するリバランシング設計を説明するための図である。
【図８】本実施形態に係るリバランシングキャンセルの判定基準（３）を満たさない場合のノード順位テーブルの例を示す図である。
【図９】本実施形態に係るリバランシングキャンセルの判定基準（３）を満たす場合のノード順位テーブルの例を示す図である。
【図１０】本実施形態に係るノードが実行するリバランシングキャンセル処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２６】
（課題の詳細な説明）
まず、本実施形態に係るノード１を含む分散処理システム１０００が解決する課題について詳細に説明する。
図１および図２は、既存のリバランシング手法の問題点を説明するための図である。図１は、リバランシング設計前後において、分散処理システム１０００を構成するノードの負荷の例を示すである。
図１（ａ）は、コンシステント・ハッシュのＩＤ空間に配置された各ノード（仮想ノード）の時刻ｔにおける負荷を示している。図１（ａ）の上図に示すように、ノード「Ｂ」の負荷は許容範囲より低く、ノード「Ｅ」の負荷は許容範囲を超えている。ここで、例えば、ノード「Ｂ」の負荷は、下図のコンシステント・ハッシュのＩＤ空間に配置された仮想ノード「Ｂ１」と「Ｂ２」の負荷の合計値となる。また、ノード「Ｅ」の負荷は、下図のコンシステント・ハッシュのＩＤ空間に配置された仮想ノード「Ｅ１」と「Ｅ２」の負荷の合計値となる。なお、例えば、仮想ノード「Ｂ１」の負荷は、仮想ノード「Ａ１」〜「Ｂ１」にはさまれた担当領域の「〇」で示す低負荷のデータの１つを処理する負荷である。仮想ノード「Ｅ２」の負荷は、仮想ノード「Ｄ２」〜「Ｅ２」にはさまれた担当領域の「●」で示す高負荷のデータの２つを処理する負荷である。
【００２７】
時刻ｔにおいて、図１（ａ）に示すように、負荷が許容範囲に収まらないノードがある場合に、既存技術では、コンシステント・ハッシュのＩＤ空間上での配置変更（リバランシング）が実行される。具体的には、このリバランシングを実行するために、負荷が許容範囲に収まらないノードの負荷を許容範囲に収めるようにするための配置変更を設計する処理（リバランシング設計）が時刻ｔに開始され、そのリバランシング設計の計算に係る時間（リバランシング設計時間：Δｔ）後に、実際のコンシステント・ハッシュのＩＤ空間上での配置変更（リバランシング）が実行される。
【００２８】
しかしながら、このリバランシング設計時間は、ノード数に依存して通常数秒から数分かかるため、実際に配置変更しようとする時刻（ｔ＋Δｔ）では、各ノードの負荷が変動し、図１（ｂ）に示すように、各ノードがすべて許容範囲に収まっていることもある（上図参照）。
図１（ｂ）では、リバランシング設計時間（Δｔ）内に、仮想ノード「Ｂ１」に高負荷のデータの処理が発生したため負荷が増加し、ノード「Ｂ」が許容範囲に収まるように変動し、仮想ノード「Ｅ２」の高負荷のデータの処理が終了したため負荷が消失し、ノード「Ｅ」が許容範囲に収まるように変動したことを示している。
【００２９】
このように各ノードの負荷が、リバランシング設計時間（Δｔ）内に変動した後、ｔ＋Δｔの時刻において、リバランシングが実際に実行されてしまうと、図２に示すように、ノードの負荷のバランスが崩れ、そのリバランシングの処理の結果として負荷が許容範囲から外れてしまい、再度のリバランシングが必要となる。図２においては、時刻ｔにおいてリバランシング設計が開始され、リバランシング設計が完了した時刻ｔ＋Δｔでは、自然に負荷が許容範囲に収まっていたにもかかわらず、時刻ｔでの負荷情報に基づいてリバランシングを実行してしまう。このため、ノードの負荷が許容範囲を下回る結果となる。よって、時刻ｔ１において、再度リバランシング設計が開始され、リバランシング設計時間（Δｔ）の経過後（時刻ｔ１＋Δｔ）に、実際のリバランシングを実行し、負荷が許容範囲に収まったことを示している。つまり、リバランシングをせずに、許容範囲に収まっていた負荷に対して、２回不要なリバランシング（ＩＤ空間上での配置変更）が発生することになる。
【００３０】
本実施形態に係るノード１を含む分散処理システム１０００は、上記のような不要なリバランシングの発生を抑制するため、リバランシング設計時間の経過後に、再度各ノード１の負荷を計測し、後記する所定の判定基準を満たした場合には、リバランシングをキャンセルする。このように、時間経過の観点を含めてリバランシングの実行が適切か否かを判断することにより、不要なリバランシングを抑制するものである。
【００３１】
＜本実施形態の説明＞
次に、本発明を実施するための形態（以下、「本実施形態」と称する。）における分散処理システム１０００について説明する。
図３は、本実施形態に係る分散処理システム１０００の全体構成を示す図である。
【００３２】
この分散処理システム１０００は、複数のノード１から構成される。各ノード１は、コンピュータなどの物理装置や仮想マシンなどの論理装置である。ロードバランサ３は、クライアント２からのメッセージを受信し、単純なラウンドロビン等により振り分けて各ノード１に送信する。そして、ノード１の振り分け部１２は、クライアント２からのメッセージを、例えば、コンシステント・ハッシュ法等に基づき、メッセージを担当するノード１に振り分ける。メッセージを担当するノード１では、信号処理部１３において、信号処理を行い、クライアント２にサービスを提供する。
【００３３】
なお、ロードバランサ３が存在せず、クライアント２から任意のノード１（振り分け部１２）にメッセージを送信することも可能である。また、振り分け部１２と信号処理部１３とは、同じノード１上に同時に存在してもよいし、別々のノード１上に存在してもよい。
本実施形態の以下の説明では、分散処理システム１０００のデータ管理手法として、ノード１の増減時の影響が少ない、コンシステント・ハッシュ法によるデータ管理手法を例として説明する。ただし、コンシステント・ハッシュ法に限定されるものではない。
【００３４】
＜ノード＞
次に、本実施形態に係る分散処理システム１０００を構成するノード１について、具体的に説明する。なお、本実施形態に係るノード１は、分散処理システム１０００の複数のノード１のうち、後記するノード識別子管理テーブル１００および振り分けＩＤテーブル２００を管理する特権ノードとなる場合と、特権ノードからノード識別子管理テーブル１００および振り分けＩＤテーブル２００の情報を受け取り自身のノード識別子管理テーブル１００および振り分けＩＤテーブル２００を更新する特権ノードではない場合とが存在する。なお、特権ノードが行う処理等については、後記する。
【００３５】
ノード１は、図３に示したように、ロードバランサ３と通信可能に接続されるともに、クラスタを構成する自身以外の他のノード１と通信可能に接続される。また、このノード１は、ロードバランサ３を介してクライアント２からメッセージを受け取ると、そのメッセージを、担当するノード１（自身を含む）に振り分け、そのメッセージの信号処理を実行する。また、特権ノードとなるノード１は、各ノード１から負荷情報を受信し、所定の許容範囲に収まらない負荷であるノード１について、コンシステント・ハッシュのＩＤ空間上の配置変更（リバランシング）を実行する。その際、特権ノードとなるノード１は、リバランシング設計時間（Δｔ）の経過後に再度各ノード１から負荷情報を受信し、所定の判定基準を満たした場合には、リバランシングをキャンセルする。
このノード１は、図４に示すように、制御部１０と、入出力部２０と、記憶部３０とを含んで構成される。
【００３６】
入出力部２０は、ロードバランサ３や、自身以外の他のノード１との間の情報の入出力を行う。また、この入出力部２０は、通信回線を介して情報の送受信を行う不図示の通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００３７】
記憶部３０は、ハードディスクやフラッシュメモリ、ＲＡＭ（Random Access Memory）等の記憶手段からなり、処理の対象となるデータ３００や、ノード識別子管理テーブル１００（図５参照）、振り分けＩＤテーブル２００（図６参照）、ノード１自身のノード負荷を計測した情報であるノード負荷計測情報４００が記憶される。さらに、ノード１が特権ノードである場合には、各ノード１のノード負荷情報をまとめた情報であるシステム負荷情報５００、各ノード１のリバランシング設計に用いる負荷量（負荷情報）を降順に並べた情報であるノード順位テーブル６００α（ノード順位情報）（図８、図９参照）、各ノードのリバランシング設計直後の負荷量（負荷情報）を降順に並べた情報であるノード順位テーブル６００β（ノード順位情報）（図８、図９参照）が記憶される。また、許容範囲を示す閾値（上限閾値や下限閾値）や後記する所定の基準値等の各パラメータに関する情報が格納される。なお、この記憶部３０に記憶される各情報についての詳細は後記する。
【００３８】
制御部１０は、ノード１全体の制御を司り、ノード識別子管理部１１、振り分け部１２、信号処理部１３、ノード負荷計測部１４、リバランシング部１５およびリバランシングキャンセル処理部１６を含んで構成される。なお、この制御部１０は、例えば、記憶部３０に格納されたプログラムをＣＰＵ（Central Processing Unit）（図示省略）がＲＡＭ（図示省略）に展開し実行することで実現される。
【００３９】
ノード識別子管理部１１は、分散処理システム１０００においてクラスタを構成する各ノード１のノード情報（ＩＰアドレス等）および各ノード１が担当するＩＤ空間を管理する。
具体的には、ノード識別子管理部１１は、自身が属する分散処理システム１０００へのノードの追加や離脱が発生した場合に、その分散処理システム１０００を構成するノード１の識別情報等を更新し、ノード識別子管理テーブル１００として管理する。
【００４０】
図５は、本実施形態に係るノード識別子管理テーブル１００のデータ構成例を示す図である。
図５に示すように、ノード識別子管理テーブル１００には、分散処理システム１０００を構成する各ノード１のノード識別子１０１とアドレス１０２（例えば、ＩＰアドレス）とが対応付けられて格納される。
【００４１】
このノード識別子１０１は、例えば、当該分散処理システム１０００内において予め設定される特定のノード（例えば、ノード識別子１０１の昇順に設定）のノード識別子管理部１１で付与され、当該分散処理システム１０００内の各ノード１に配信される。なお、このノード識別子１０１は、コンシステント・ハッシュのＩＤ空間において仮想ＩＤを用いる場合、仮想ＩＤ毎に付与される。
【００４２】
また、ノード識別子管理部１１は、ノード識別子管理テーブル１００の更新（ノード１の増減設）に合わせて、ノード１の担当するＩＤ空間情報を更新し、振り分けＩＤテーブル２００として管理する。
【００４３】
図６は、本実施形態に係る振り分けＩＤテーブル２００のデータ構成例を示す図である。
図６に示すように、振り分けＩＤテーブル２００には、ノード識別子２０１に対応付けて、そのノード１が担当するＩＤ空間２０２が格納される。このノード識別子２０１は、図５のノード識別子１０１と同様の情報である。図６に示す例では、ＩＤ空間の全ＩＤ数が「０」〜「９９９」の「１０００」であり、例えば、ノード識別子２０１が「Ａ」のノード１が、担当するＩＤ空間２０２として「０〜１９９」について担当することを示している。
【００４４】
分散処理システム１０００内の特権ノードは、各ノード１に対して、最新のノード識別子管理テーブル１００および振り分けＩＤテーブル２００を送信する。これにより、各ノード１のノード識別子管理部１１は、ノード識別子管理テーブル１００および振り分けＩＤテーブル２００を常に最新の状態に更新して保持する。このようにすることにより、分散処理システム１０００内の各ノード１には、同一のノード識別子管理テーブル１００および振り分けＩＤテーブル２００が保持される。
【００４５】
また、特権ノードは、例えば、このノード識別子管理テーブル１００の一番上の行のノード１から順に、特権ノードとなるように設定される。ノード１が新たに特権ノードになった場合、自身が特権ノードであることを示す情報を、各ノード１等に送信する。そして、特権ノードは、クラスタ内のノード１についてリバランシング（ＩＤ空間上での配置変更）があった場合に、自身の振り分けＩＤテーブル２００を更新し、その更新情報を、各ノード１に配信する。
【００４６】
図４に戻り、振り分け部１２は、ロードバランサ３等を介してクライアント２から発呼されるメッセージ内の情報（「振り分けキー」）をもとに「ｈａｓｈ（ｋｅｙ）」を算出し、振り分けＩＤテーブル２００を参照して、そのメッセージの処理を担当するノード１を特定する。そして、振り分け部１２は、特定したノード１のアドレスの情報を、ノード識別子管理テーブル１００を参照して取得し、特定したノード１へメッセージの振り分け（送信）を行う。
また、信号処理部１３は、自身のノード１が担当するデータに関するメッセージの信号処理を実行する。
【００４７】
ノード負荷計測部１４は、所定の周期や、後記する特権ノードによるリバランシング設計時間（Δｔ）の経過直後においてノード負荷計測要求等を特権ノードから受信した場合に、自身のノード１のノード負荷（負荷情報）を計測し、自身の記憶部３０内にノード負荷計測情報４００として記憶する。そして、ノード負荷計測部１４は、その計測したノード負荷（負荷情報）を、特権ノードに送信する。
ノード負荷計測部１４が計測するノード負荷は、例えば、メモリ使用量、ＣＰＵ使用率、アクセス頻度等である。
【００４８】
以下説明する、リバランシング部１５およびリバランシングキャンセル処理部１６は、各ノード１が備えるが、ノード１自身が特権ノードの場合に動作する。
リバランシング部１５は、各ノード１の負荷情報に基づき、リバランシングの実行判定を行う。そして、リバランシング部１５は、リバランシングを実行すると判定した場合には、コンシステント・ハッシュのＩＤ空間上でのノードの配置変更の計算（リバランシング設計）を行い、リバランシングを実行する。なお、リバランシング部１５は、リバランシングキャンセル処理部１６から、リバランシングキャンセル指示情報を受け付けた場合には、当該リバランシングの実行を中止する。以下、リバランシング部１５の処理を具体的に説明する。
【００４９】
リバランシング部１５は、各ノード１から負荷情報を取得し、記憶部３０内のシステム負荷情報５００に格納する。
そして、リバランシング部１５は、各ノード１の負荷情報を参照し、その負荷情報が許容範囲に収まっているか否かを判定する。具体的には、リバランシング部１５は、その負荷情報（例えば、メモリ使用量、ＣＰＵ使用率、アクセス頻度等）について予め設定した、上限閾値を超えているか、下限閾値未満であるか、を判定する。このどちらかの条件を満たす場合に、リバランシング部１５は、リバランシングが必要であると判定し、リバランシング設計を開始する。
【００５０】
リバランシング部１５は、リバランシング設計（ＩＤ空間上でのノードの配置変更）を以下のようにして行う。なお、ここでは、負荷が上限閾値を超えたノード１（ここでは、ノード「Ｄ」とする。）について、負荷を低減させるリバランシングを行うものとして説明する。
【００５１】
図７は、リバランシング部１５が実行するリバランシング設計を説明するための図である。リバランシング部１５は、リバランシングが必要と判定したノード１を特定した上で、その特定したノード１からみて、ＩＤ空間において両隣のノードを抽出する。図７においては、リバランシングが必要と判定したノード「Ｄ」の両隣のノード「Ｃ」とノード「Ｅ」とが抽出される。
次に、リバランシング部１５は、抽出した両隣のノードのうち、負荷が少ないノードを選択する。図７（ａ）は、負荷が少ないノードとしてノード「Ｃ」が選択された例を示し、図７（ｂ）は、負荷が少ないノードとしてノード「Ｅ」が選択された例を示している。
【００５２】
リバランシング部１５は、負荷が少ないノードとしてノード「Ｃ」が選択された場合、図７（ａ）に示すように、ノード「Ｃ」のＩＤ空間における担当領域が増えるように（つまり、ノード「Ｄ」の担当領域が減るように）、ノード「Ｃ」のＩＤ空間上の位置を移動する。
一方、リバランシング部１５は、負荷が少ないノードとしてノード「Ｅ」が選択された場合、図７（ｂ）に示すように、ノード「Ｅ」のＩＤ空間における担当領域が増えるように（つまり、ノード「Ｄ」の担当領域が減るように）、ノード「Ｄ」のＩＤ空間上の位置を移動する。
【００５３】
リバランシング部１５は、このように、リバランシング設計を実行した後に、リバランシングキャンセル処理部１６から、リバランシングキャンセル指示情報を受け付けたか否かを判定し、リバランシングキャンセル指示情報を受け付けていない場合には、リバランシング設計に基づき、実際のリバランシング（ＩＤ空間上での配置変更）を実行する。なお、リバランシング部１５は、図６に示した振り分けＩＤテーブル２００のＩＤ空間２０２の値を変更することにより、リバランシング（ＩＤ空間上での配置変更）を行う。
【００５４】
図４に戻り、リバランシングキャンセル処理部１６は、リバランシング部１５によるリバランシング設計時間（Δｔ）の経過後、つまり、リバランシング部１５によりリバランシング設計が終わると、例えば、各ノード１に対し、ノード負荷計測要求を送信することにより、再度各ノード１から負荷情報を受信し、以下に示す判定基準を満たす場合には、リバランシングキャンセルすることを示すリバランシングキャンセル指示情報をリバランシング部１５に出力する。
【００５５】
≪リバランシングキャンセルの判定基準≫
リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）の経過後の各ノード１の負荷情報に基づき、以下の判定基準（１）〜（３）のいずれかに該当する場合には、リバランシングの実行をキャンセルする。
【００５６】
〔判定基準（１）〕各ノード１の負荷が許容範囲内に収まっている。
例えば、リバランシング設計時間（Δｔ）経過後の各ノード１の負荷が、分散処理システム１０００を構成するすべてのノード１の平均負荷（以下、「ノード平均負荷」と称する。）の±５％以内（許容範囲）に収まっている。このような場合に、リバランシングキャンセル処理部１６は、すでに、各ノード１の負荷が許容範囲に収まっているため、リバランシングは中止と判定し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
【００５７】
〔判定基準（２）〕ノード平均負荷が、リバランシング設計の計算の前後で、所定の基準値以上に減少している。
この場合、リバランシングキャンセル処理部１６は、リバランシング部１５が、負荷情報が許容範囲に収まっていないノード１が存在する、つまり、リバランシングが必要であると判定したときに、その時点のノード平均負荷を計算しておく。また、リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）経過後の各ノード１の負荷に基づき、ノード平均負荷を計算する。そして、リバランシングキャンセル処理部１６は、リバランシング設計の計算前後のノード平均負荷を比較し、所定の基準値（例えば、計算前のノード平均負荷の２０％）以上、計算後のノード平均負荷が減少している場合に、リバランシングは中止と判定し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
この判定基準（２）は、ノード平均負荷が所定の基準値（例えば、２０％）以上、減少している場合には、全体としてノード１の負荷がかなり下がった状態となっており、この状態のときにさらに、リバランシングを実行すると、よりバランスを崩す（許容範囲から外れる）結果になる可能性が高いことに基づく。
【００５８】
〔判定基準（３）〕負荷が許容範囲外であるノード１のノード順位に変動がある。
判定基準（３）において、リバランシングキャンセル処理部１６は、リバランシング部１５が、負荷情報が許容範囲に収まっていないノード１が存在する、つまり、リバランシングが必要であると判定したときに、その時点の各ノード１のノード負荷に基づき、その負荷の大きさを降順でソートした情報であるノード順位テーブルを作成する。このとき作成されたノード順位テーブルを「ノード順位テーブル６００α」と称する。また、リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）経過後の各ノード１の負荷に基づき、同じく負荷の大きさを降順でソートしたノード順位テーブルを作成する。このとき作成されたノード順位テーブルを「ノード順位テーブル６００β」と称する。
なお、ここでは、リバランシングキャンセル処理部１６が、負荷の大きさを降順でソートしノード順位テーブルを作成するものとして説明するが、負荷の大きさを昇順でソートしノード順位テーブルを作成してもよい。つまり、リバランシングキャンセル処理部１６は、負荷の大小関係に基づいてソートし、ノード順位テーブルを作成する。
リバランシングキャンセル処理部１６は、リバランシング設計の計算前後のノード順位テーブルにおいて、負荷が許容範囲外であるノード１のノード順位に変動があるかを判定し、変動がある場合には、リバランシングは中止と判定し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
【００５９】
図８は、リバランシングキャンセルの判定基準（３）を満たさない場合のノード順位テーブル（ノード順位情報）の例を示す図である。また、図９は、リバランシングキャンセルの判定基準（３）を満たす場合のノード順位テーブル（ノード順位情報）の例を示す図である。
【００６０】
図８は、例えば、ノード１の負荷情報としてメモリ使用量が採用された場合において、許容範囲が５０〜９０（ＭＢ）に設定された例を示す。図８（ａ）に示すように、リバランシング設計前のノード順位テーブル６００αにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ａ」「Ｄ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。
これに対し、図８（ｂ）に示すように、リバランシング設計時間（Δｔ）経過後のノード順位テーブル６００βにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ａ」「Ｄ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。つまり、負荷が許容範囲外にあるノード１の順に変動はない。よって、リバランシングキャンセル処理部１６は、判定基準（３）を満たさないと判断する。これにより、リバランシング部１５によるリバランシングが実行される。
【００６１】
一方、図９においては、図８（ａ）と同様、図９（ａ）に示すように、リバランシング設計前のノード順位テーブル６００αにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ａ」「Ｄ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。
これに対し、図９（ｂ）に示すように、リバランシング設計時間（Δｔ）経過後のノード順位テーブル６００βにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ｄ」「Ａ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。よって、ノード順位がノード「Ａ」と「Ｄ］とで変動している。従って、リバランシングキャンセル処理部１６は、判定基準（３）を満たすと判断し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
【００６２】
判定基準（３）は、負荷が許容範囲外であるノードの順位に変動のある場合には、リバランシングを実行した後においても、負荷が許容範囲に収まらないノード１が発生する可能性が高いことに基づく。つまり、負荷の変動の激しいときには、リバランシングを行わず、変動が落ち着いた後に、リバランシングを実行するという考えに基づく。
よって、判定基準（３）において、「ノード順位に変動がある」場合とは、リバランシング設計の計算前のノード順位テーブル６００αにおいては、許容範囲に収まっていたノードが、許容範囲外に変動した場合や、許容範囲外であったノードが、許容範囲に収まった場合も「ノードの順位に変動がある」とし、判定基準（３）を満たすと判断して、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
【００６３】
リバランシングキャンセル処理部１６は、上記のリバランシングキャンセルの判定基準（１）（２）（３）のいずれかに該当する場合には、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
ただし、リバランシングキャンセル処理部１６において、この判定基準（１）（２）（３）のすべてを用いず、判定基準（１）（２）（３）のうちのいずれか１つや、いずれか２つの組み合わせを設定し、リバランシングをキャンセルするか否かを判定するようにしてもよい。このようにすることによっても、不要なリバランシングを抑制することができる。
【００６４】
リバランシングキャンセル処理部１６からリバランシングキャンセル指示情報を受け取ったリバランシング部１５は、リバランシングの実行を行わない。このようにすることにより、不要なリバランシングを抑制することができる。
【００６５】
＜処理の流れ＞
次に、本実施形態に係るノード１が実行する、リバランシングキャンセル処理について、図１０を参照して説明する。図１０は、本実施形態に係るノード１が実行するリバランシングキャンセル処理の流れを示すフローチャートである。なお、このリバランシングキャンセル処理は、分散処理システム１０００を構成するノード１のうち、特権ノードが行う処理である。
【００６６】
まず、ノード１（特権ノード）のリバランシング部１５は、例えば、所定の時間間隔で、各ノード１から負荷情報を受信する（ステップＳ１）。そして、リバランシング部１５は、受信した各ノード１の負荷情報を記憶部３０のシステム負荷情報５００に記憶する。
【００６７】
続いて、リバランシング部１５は、各ノード１の負荷情報を参照し、その負荷情報が許容範囲に収まっているか否かを判定する。つまり、リバランシング部１５は、リバランシングが必要か否かを判定する（ステップＳ２）。具体的には、リバランシング部１５は、各ノード１の負荷が、予め設定した、上限閾値を超えているか、下限閾値未満であるか、を判定する。即ち、各ノード１の負荷が許容範囲外であるか否かを判定する。
【００６８】
ここで、リバランシングが不要であると判定された場合には（ステップＳ２→Ｎｏ）、処理を終了する。一方、リバランシングが必要であると判定された場合には（ステップＳ２→Ｙｅｓ）、次にステップＳ３に進む。
【００６９】
ステップＳ３において、リバランシングキャンセル処理部１６は、後記するステップＳ８における判定に備えて、リバランシング設計の計算前における、ノード平均負荷を算出し、記憶部３０に記憶しておく。また、リバランシングキャンセル処理部１６は、後記するステップＳ１０における判定に備えて、各ノード１の負荷情報に基づき、その負荷の大きさを降順でソートした情報であるノード順位テーブル６００αを作成し、記憶部３０に記憶しておく。なお、ノード平均負荷は、リバランシングキャンセルの判定基準（２）を満たすか否かの判定に用いられる。また、ノード順位テーブル６００αは、リバランシングキャンセルの判定基準（３）を満たすか否かの判定に用いられる。
【００７０】
続いて、リバランシング部１５は、リバランシング設計を実行する（ステップＳ４）。具体的には、リバランシング部１５は、リバランシングが必要と判定した（許容範囲外であるとした）ノード１を特定した上で、その特定したノード１からみて、ＩＤ空間において両隣のノードを抽出し、その抽出した両隣のノードのうち、負荷が少ないノードを選択する。そして、その選択した負荷が少ないノードの負荷が増えるように、ＩＤ空間上の位置を移動するように設計する。
【００７１】
次に、リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）の経過後、例えば、各ノード１に対し、ノード負荷計測要求を送信することにより、各ノード１から再度、負荷情報を受信する（ステップＳ５）。そして、リバランシングキャンセル処理部１６は、受信した各ノード１の負荷情報を記憶部３０のシステム負荷情報５００に記憶する。
【００７２】
続いて、リバランシングキャンセル処理部１６は、上記したリバランシングキャンセルの判定基準（１）、判定基準（２）、判定基準（３）のうち、いずれか１つでも満たすか否かを判定する。具体的には、次のステップＳ６〜Ｓ１０を実行する。
【００７３】
まず、リバランシングキャンセル処理部１６は、判定基準（１）を満たすか否かを判定する（ステップＳ６）。例えば、リバランシングキャンセル処理部１６は、リバランシング設計の計算後（リバランシング設計時間（Δｔ）経過後）における各ノード１の負荷が、許容範囲である、ノード平均負荷の±５％以内に収まっているか否かを判定する。
ここで、判定基準（１）を満たす場合には（ステップＳ６→Ｙｅｓ）、ステップＳ１１に進む。一方、判定基準（１）を満たさない場合には（ステップＳ６→Ｎｏ）、次のステップＳ７に進む。
【００７４】
ステップＳ７において、リバランシングキャンセル処理部１６は、ステップＳ５において受信した各ノード１の負荷情報に基づき、リバランシング設計の計算後（リバランシング設計時間（Δｔ）経過後）における、ノード平均負荷を算出する。
【００７５】
続いて、リバランシングキャンセル処理部１６は、判定基準（２）を満たすか否かを判定する（ステップＳ８）。具体的には、リバランシングキャンセル処理部１６は、ノード平均負荷が、リバランシング設計の計算の前後で、所定の基準値（例えば、計算前のノード平均負荷の２０％）以上に減少しているか否かを判定する。
ここで、判定基準（２）を満たす場合には（ステップＳ８→Ｙｅｓ）、ステップＳ１１に進む。一方、判定基準（２）を満たさない場合には（ステップＳ８→Ｎｏ）、次のステップＳ９に進む。
【００７６】
ステップＳ９において、リバランシングキャンセル処理部１６は、ステップＳ５において受信した各ノード１の負荷情報に基づき、その負荷の大きさを降順でソートした情報であるノード順位テーブル６００βを作成する。
【００７７】
次に、リバランシングキャンセル処理部１６は、判定基準（３）を満たすか否かを判定する（ステップＳ１０）。具体的には、リバランシングキャンセル処理部１６は、ステップＳ３において作成したノード順位テーブルαと、ステップＳ９において作成したノード順位テーブルβとを比較し、負荷が許容範囲外であるノード１のノード順位に変動があるか否かを判定する。
ここで、負荷が許容範囲外であるノード１のノード順位に変動がある場合には、判定基準（３）を満たすとして（ステップＳ１０→Ｙｅｓ）、ステップＳ１１に進む。一方、負荷が許容範囲外であるノード１のノード順位に変動がない場合には、判定基準（３）を満たさないとして（ステップＳ１０→Ｎｏ）、ステップＳ１２に進む。
【００７８】
そして、リバランシングキャンセル処理部１６は、リバランシングキャンセルの判定基準（１）、判定基準（２）、判定基準（３）のうち、いずれか１つでも満たす場合には（ステップＳ６→Ｙｅｓ、ステップＳ８→Ｙｅｓ、ステップＳ１０→Ｙｅｓ）、リバランシングキャンセル指示情報をリバランシング部１５に出力し、これにより、リバランシング部１５は、設計したリバランシングの実行を中止する（ステップＳ１１）。そして、ステップＳ１に戻る。
【００７９】
一方、リバランシングキャンセル処理部１６は、リバランシングキャンセルの判定基準（１）、判定基準（２）、判定基準（３）のすべてについて満たさなかった場合には（ステップＳ１０→Ｎｏ）、ステップＳ１２に進み、リバランシング部１５が、設計したリバランシングを実行し、処理を終了する。
【００８０】
以上説明したように、本実施形態に係るノード、リバランシングキャンセル方法、および、プログラムによれば、リバランシング設計時間の経過後に、再度各ノード１の負荷を計測し、リバランシングキャンセルの判定基準を満たした場合には、リバランシングを中止する。このように、時間経過の観点を含めてリバランシングの実行が適切か否かを判断することにより、不要なリバランシングを抑制することができる。
【符号の説明】
【００８１】
１      ノード
２      クライアント
３      ロードバランサ
１０    制御部
１１    ノード識別子管理部
１２    振り分け部
１３    信号処理部
１４    ノード負荷計測部
１５    リバランシング部
１６    リバランシングキャンセル処理部
２０    入出力部
３０    記憶部
１００  ノード識別子管理テーブル
２００  振り分けＩＤテーブル
３００  データ
４００  ノード負荷計測情報
５００  システム負荷情報
６００α，６００β  ノード順位テーブル（ノード順位情報）
１０００  分散処理システム
【図１】
0006326011.tif 000002
【図２】
0006326011.tif 000003
【図３】
0006326011.tif 000004
【図４】
0006326011.tif 000005
【図５】
0006326011.tif 000006
【図６】
0006326011.tif 000007
【図７】
0006326011.tif 000008
【図８】
0006326011.tif 000009
【図９】
0006326011.tif 000010
【図１０】
0006326011.tif 000011