[go: up one dir, main page]

JP2017016576A - Node, rebalancing cancellation method, and program - Google Patents

Node, rebalancing cancellation method, and program Download PDF

Info

Publication number
JP2017016576A
JP2017016576A JP2015135527A JP2015135527A JP2017016576A JP 2017016576 A JP2017016576 A JP 2017016576A JP 2015135527 A JP2015135527 A JP 2015135527A JP 2015135527 A JP2015135527 A JP 2015135527A JP 2017016576 A JP2017016576 A JP 2017016576A
Authority
JP
Japan
Prior art keywords
rebalancing
node
load
design
information
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2015135527A
Other languages
Japanese (ja)
Other versions
JP6326011B2 (en
Inventor
篤史 外山
Atsushi Toyama
篤史 外山
啓介 小西
Keisuke Konishi
啓介 小西
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to JP2015135527A priority Critical patent/JP6326011B2/en
Publication of JP2017016576A publication Critical patent/JP2017016576A/en
Application granted granted Critical
Publication of JP6326011B2 publication Critical patent/JP6326011B2/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

【課題】時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制する、ノード、リバランシングキャンセル方法、および、プログラムを提供する。【解決手段】ノード１は、分散処理システムを構成する各ノード１から負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノード１がある場合に、当該ノード１の負荷を許容範囲に収めるようにリバランシング設計を行うリバランシング部１５と、リバランシング設計時間の経過後に、再度各ノード１から負荷情報を受信し、リバランシングキャンセルの所定の判定基準を満たす場合に、リバランシングキャンセル指示情報をリバランシング部１５に出力するリバランシングキャンセル処理部１６とを備える。【選択図】図４Provided are a node, a rebalancing cancellation method, and a program that determine whether or not rebalancing is appropriate in view of the passage of time and suppress unnecessary rebalancing. A node 1 obtains load information from each node 1 constituting a distributed processing system, and if there is a node 1 that measures load information that does not fall within a predetermined allowable range, the node 1 allows the load on the node 1 The rebalancing unit 15 that performs the rebalancing design so as to fall within the range, and when the load balancing information is received again from each node 1 after the elapse of the rebalancing design time and the predetermined determination criterion for rebalancing cancellation is satisfied, A rebalancing cancel processing unit 16 that outputs cancel instruction information to the rebalancing unit 15. [Selection] Figure 4

Description

本発明は、ネットワーク上に分散配置されるノードをクラスタ化してデータを格納する分散処理システムにおいて、ノードの負荷の偏りを適正に是正する、ノード、リバランシングキャンセル方法、および、プログラムに関する。   The present invention relates to a node, a rebalancing cancellation method, and a program that appropriately correct a load deviation of nodes in a distributed processing system that stores data by clustering nodes that are distributed on a network.

近年、クラウドコンピューティングの隆盛に伴い、多量のデータの処理や保持を効率的に行うことが求められている。そこで、複数のサーバを協調動作させることにより効率的な処理を実現する分散処理技術が発展している。   In recent years, with the rise of cloud computing, it has been required to efficiently process and retain a large amount of data. Thus, distributed processing technology has been developed that realizes efficient processing by operating a plurality of servers in a coordinated manner.

分散処理を行う際には、クラスタ構成からなる分散処理システムを構成する各サーバ（以下、「ノード」と称する。）が担当するデータを決定する必要がある。このとき、分散処理システム全体での処理能力を高めるためには、各ノードが担当するデータ数は平均化されていることが望ましい。   When performing distributed processing, it is necessary to determine data to be handled by each server (hereinafter referred to as “node”) constituting a distributed processing system having a cluster configuration. At this time, in order to increase the processing capability of the entire distributed processing system, it is desirable that the number of data handled by each node is averaged.

代表的なデータの管理手法として、各データのｋｅｙをハッシュ関数にかけた値（以下、「ｈａｓｈ（ｋｅｙ）」と称する。）をノード数Ｎで割った余り、即ち「ｈａｓｈ（ｋｅｙ） ｍｏｄ Ｎ」を番号として持つノードがデータを管理する手法がある。この場合、各ノードに事前に「０」から「Ｎ−１」までの番号を割り当てていることが前提となる。このような管理手法を用いた場合、ノードを追加・離脱すると、Ｎの値が変化して、多くのデータについて、そのデータの保存を担当するノードが変更になるため、担当するデータを再配置することが必要になる。   As a representative data management method, a remainder obtained by dividing a value obtained by multiplying the key of each data by a hash function (hereinafter referred to as “hash (key)”) by the number of nodes N, that is, “hash (key) mod N”. There is a method in which a node having a number as a number manages data. In this case, it is assumed that numbers “0” to “N−1” are assigned to each node in advance. When such a management method is used, when a node is added or removed, the value of N changes and the node responsible for storing that data changes for many data. It becomes necessary to do.

そこで、ノードの追加・離脱に伴い担当するノードが変更になるデータ数を約１／Ｎに抑える方法として、コンシステント・ハッシュ（Consistent Hashing）法（非特許文献１参照）を用いたデータ管理手法がある。このコンシステント・ハッシュ法は、Amazon Dynamo（非特許文献２参照）等において用いられている。   Therefore, as a method for suppressing the number of data that the node in charge changes with the addition / detachment of a node to about 1 / N, a data management method using a consistent hashing method (see Non-Patent Document 1). There is. This consistent hash method is used in Amazon Dynamo (see Non-Patent Document 2) and the like.

このコンシステント・ハッシュ法を用いたデータ管理手法では、ノードとデータの双方にＩＤ（IDentifier）を割り当てる。そして、データのＩＤから閉じたＩＤ空間を時計回りに辿った場合に最初に当たったノードをそのデータの担当とする。ノードに対するＩＤの与え方の例としては、ＩＰアドレスをハッシュ関数にかけた値（ｈａｓｈ（ＩＰアドレス））が挙げられる。   In this data management method using the consistent hash method, IDs (IDentifiers) are assigned to both nodes and data. Then, when the closed ID space is traced clockwise from the ID of the data, the node that hits first is assumed to be in charge of the data. An example of how to give an ID to a node is a value (hash (IP address)) obtained by multiplying an IP address by a hash function.

クラスタ構成の分散処理システムでは、各ノードの処理性能が等しい場合には、各ノードが担当するデータ量を等しくする、即ち、コンシステント・ハッシュ法のＩＤ空間（以下、単に「ＩＤ空間」と称する場合がある。）における、ノード間の距離（以下、「ノードの担当領域」と称する。）を等しくすることが望ましい。この点を実現するため、各ノードに仮想的に複数のＩＤを持たせる手法が用いられている（非特許文献３参照）。各ノードが複数の仮想ＩＤを持つことで、仮想ＩＤ毎の担当領域は異なっていても、大数の法則に従いノードの担当領域は平均化される。   In a clustered distributed processing system, when the processing performance of each node is equal, the amount of data handled by each node is made equal, that is, a consistent hash method ID space (hereinafter, simply referred to as “ID space”). In some cases, it is desirable to make the distances between nodes (hereinafter referred to as “node assigned areas”) equal. In order to realize this point, a method of virtually giving a plurality of IDs to each node is used (see Non-Patent Document 3). By having each node have a plurality of virtual IDs, even if the assigned areas for each virtual ID are different, the assigned areas of the nodes are averaged according to the law of large numbers.

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>David karger, et al., “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”, [online], 1997, ACM, [June 23, 2015 search], Internet <URL : 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>Giuseppe DeCandia, et al., “Dynamo: Amazon's Highly Available Key-value Store”, SOSP'07, October 14-17, 2007, Stevenson, Washington, USA, [online], [June 23, 2015 search] , Internet <URL: http: //www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf> 入江 道生、他４名、「コンシステント・ハッシュ法におけるデータの複製を意識した負荷分散手法」、社団法人電子情報通信学会、2010年10月、信学技報、IN2010-77、P.69-74Michio Irie and 4 others, "Load distribution method that is conscious of data replication in consistent hash method", The Institute of Electronics, Information and Communication Engineers, October 2010, IEICE Technical Report, IN2010-77, P.69- 74

これらのコンシステント・ハッシュ法や仮想ＩＤ等の従来技術により、ノード間で担当するデータを均一化し負荷を分散させることが可能である。しかしながら、特定ノードにおいて、アクセス頻度の高い、処理時間が長い等でノードに高い負荷を与えるデータ（以下、「高負荷データ」と称する。）が偏って発生するために、各ノードが担当するデータ数自体は均等であっても、ノード間で負荷の偏りが発生する。   With these conventional techniques such as the consistent hash method and virtual ID, it is possible to uniformize the data in charge among the nodes and distribute the load. However, since data that gives a high load to the node due to high access frequency, long processing time, etc. (hereinafter referred to as “high load data”) is generated in a specific node, the data that each node is in charge of. Even if the numbers themselves are equal, load imbalance occurs between nodes.

従来、このようなコンシステント・ハッシュ法の分散処理システムにおける負荷増大に対する対策としては、新たなノードを増設し、システムをスケールアウトさせて、高負荷となったノードの担当するデータ数を縮小させ負荷を低減する手法がとられている。一方、各ノードのコンシステント・ハッシュのＩＤ空間上での配置変更（以下、「リバランシング」と称する。）を行い、適切に負荷を分散させることにより、増設を行うことなく現行のノード台数で対応可能なケースもある。この場合、コンシステント・ハッシュのＩＤ空間上の隣接ノード間でリバランシングを実行してノード間の負荷の偏りを是正する手法が用いられる。   Conventionally, as a countermeasure against the load increase in such a distributed processing system of the consistent hash method, a new node is added, the system is scaled out, and the number of data assigned to the high load node is reduced. A technique for reducing the load is taken. On the other hand, by changing the placement of each node's consistent hash in the ID space (hereinafter referred to as “rebalancing”) and distributing the load appropriately, the number of nodes can be increased without increasing the number of nodes. There are cases that can be handled. In this case, a technique is used in which rebalancing is performed between adjacent nodes on the ID space of the consistent hash to correct the load imbalance between the nodes.

しかしながら、既存のリバランシング手法では、各ノードの負荷情報を取得し、その負荷情報に基づきリバランシング設計を行い、その設計した結果を用いて実際にリバランシングが実行されるため、リバランシング設計の計算に係る時間（以下、「リバランシング設計時間」と称する場合がある。）によっては、実負荷が適正値に変動したにもかかわらず、リバランシングが実行されてしまう問題があった。このリバランシング設計に係る時間は、ノード数に依存するものであり、数秒から数分におよぶ場合も想定される。つまり、既存のリバランシング手法では、リバランシング設計にかかる時間経過を考慮していないため、リバランシングを実行する時点において、実負荷が適正値に変動しているにもかかわらず、不要なリバランシングを実行してしまう問題があった。   However, in the existing rebalancing method, load information of each node is obtained, rebalancing design is performed based on the load information, and rebalancing is actually executed using the designed result. Depending on the calculation time (hereinafter sometimes referred to as “rebalancing design time”), there is a problem in that rebalancing is executed even though the actual load has changed to an appropriate value. The time required for this rebalancing design depends on the number of nodes, and it may be several seconds to several minutes. In other words, the existing rebalancing method does not take into account the time elapsed for rebalancing design, so unnecessary rebalancing is performed even though the actual load has changed to an appropriate value at the time of rebalancing. There was a problem of running.

このような背景を鑑みて本発明がなされたのであり、本発明は、時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制することができる、ノード、リバランシングキャンセル方法、および、プログラムを提供することを課題とする。   The present invention has been made in view of such a background, and the present invention can determine whether rebalancing is appropriate, including the viewpoint of the passage of time, and can suppress unnecessary rebalancing. It is an object to provide a node, a rebalancing cancellation method, and a program.

前記した課題を解決するため、請求項１に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準（１）は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、前記判定基準（２）は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、前記判定基準（３）は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。   In order to solve the above-described problem, the invention according to claim 1 is the node of the distributed processing system that distributes and processes data to each of a plurality of nodes constituting the cluster, and loads the load information of the node itself. The load information is acquired from each of the node load measurement unit to be measured and each of the other nodes other than itself, and it is determined whether or not each of the acquired load information falls within a predetermined allowable range, and the allowable range If there is a node that measured load information that does not fit in the node, perform a rebalancing design that changes the data distribution destination so that the load of the node falls within the allowable range, and execute rebalancing based on the rebalancing design Negative load from itself and other nodes other than itself after the rebalancing design time elapses. Rebalancing cancel instruction information for instructing to stop execution of rebalancing based on the rebalancing design when the information is acquired and any of the predetermined criteria (1), (2), and (3) for rebalancing cancellation is satisfied A rebalancing cancellation processing unit that outputs the rebalancing unit to the rebalancing unit, and the determination criterion (1) is that the load information of each node acquired after the rebalancing design time elapses is within the allowable range. In the determination criterion (2), a node average load obtained by averaging the load information of each node is calculated, and the calculated node average load is decreased by a predetermined reference value before and after the rebalancing design calculation. The criterion (3) is obtained by referring to the load information of each node and sorting the nodes based on the magnitude relation of the load. The rank information is created before and after the calculation of the rebalancing design, and the rank of the node where the load does not fall within the allowable range is varied in the node rank information before and after the calculation, and the rebalancing unit When the rebalancing cancel instruction information is received, execution of the rebalancing is stopped.

また、請求項５に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムが有する前記ノードのリバランシングキャンセル方法であって、前記ノードが、自身のノードの負荷情報を計測するステップと、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行うステップと、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、当該リバランシング設計に基づくリバランシングの実行を中止させるステップと、を実行し、前記判定基準（１）は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、前記判定基準（２）は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、前記判定基準（３）は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であることを特徴とするリバランシングキャンセル方法とした。   The invention according to claim 5 is the node rebalancing cancellation method of the distributed processing system that distributes and processes data to each of a plurality of nodes constituting the cluster, wherein the node is its own node. Measuring the load information, acquiring the load information from each of itself and other nodes other than itself, determining whether each of the acquired load information falls within a predetermined allowable range, and When there is a node that has measured load information that does not fall within the range, a step of performing a rebalancing design for changing the data distribution destination so that the load of the node falls within the allowable range, and after a lapse of the rebalancing design time Obtain load information from each of the nodes and other nodes other than itself again, and perform rebalancing cancellation. When the determination criterion (1), (2), or (3) is satisfied, the execution of the rebalancing based on the rebalancing design is performed, and the determination criterion (1) The load information of each node acquired after the lapse of the balancing design time is within the allowable range, and the criterion (2) calculates a node average load obtained by averaging the load information of each node, and the rebalancing design Before and after the calculation, the calculated node average load is reduced by a predetermined reference value or more, and the determination criterion (3) refers to the load information of each node, and determines each node based on the load magnitude relationship. The sorted node order information is created before and after the calculation of the rebalancing design, and the nodes before and after the calculation are assigned to the ranks of the nodes where the load does not fall within the allowable range. That the position information is change, and rebalancing canceling method which is a.

このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、リバランシングを中止する。
よって、時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制することができる。 In this way, when a node acquires load information from each node constituting the distributed processing system, and there is a node that measures load information that does not fall within a predetermined allowable range, the load of the node is within the allowable range. Rebalancing design is performed so that Then, after the elapse of the rebalancing design time, the node receives load information from each node again, and rebalancing is performed when any of the predetermined determination criteria (1), (2), and (3) for rebalancing cancellation is satisfied. Cancel.
Therefore, it is possible to determine whether or not rebalancing is appropriate, including the viewpoint of the passage of time, and to suppress unnecessary rebalancing.

請求項２に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。   The invention according to claim 2 is a node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster, and measures a load information of its own node; The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design that changes the data distribution destination so that the load on the node falls within the allowable range, and a rebalancing unit that performs rebalancing based on the rebalancing design, and rebalancing After the design time elapses, load information is acquired again from each node other than itself and other nodes, and rebalancing A rebalancing cancel processing unit that outputs rebalancing cancel instruction information for instructing to stop execution of rebalancing based on the rebalancing design when a predetermined determination criterion for cancellation is satisfied, and The criterion is that the load information of each node acquired after the rebalancing design time elapses is within the allowable range, and the rebalancing unit receives the rebalancing cancel instruction information. The node is characterized by stopping the execution of balancing.

このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準である、「リバランシング設計時間の経過後に取得した各ノードの負荷情報が許容範囲に収まっていること」を満たす場合に、リバランシングを中止する。
よって、時間の経過により各ノードの負荷が変動し、許容範囲に収まっている場合に、不要なリバランシングを抑制することができる。 In this way, when a node acquires load information from each node constituting the distributed processing system, and there is a node that measures load information that does not fall within a predetermined allowable range, the load of the node is within the allowable range. Rebalancing design is performed so that The node receives load information from each node again after the elapse of the rebalancing design time, and is a predetermined criterion for rebalancing cancellation, which is “the load information of each node acquired after the elapse of the rebalancing design time. If the value is within the allowable range, the rebalancing is stopped.
Therefore, unnecessary rebalancing can be suppressed when the load of each node fluctuates with time and falls within the allowable range.

請求項３に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。   The invention according to claim 3 is a node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster, and measures a load information of its own node, The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design that changes the data distribution destination so that the load on the node falls within the allowable range, and a rebalancing unit that performs rebalancing based on the rebalancing design, and rebalancing After the design time elapses, load information is acquired again from each node other than itself and other nodes, and rebalancing A rebalancing cancel processing unit that outputs rebalancing cancel instruction information for instructing to stop execution of rebalancing based on the rebalancing design when a predetermined determination criterion for cancellation is satisfied, and The criterion is to calculate a node average load obtained by averaging the load information of each node, and before and after the rebalancing design calculation, the calculated node average load is decreased by a predetermined reference value or more, When the rebalancing unit receives the rebalancing cancel instruction information, the rebalancing unit stops the execution of the rebalancing.

このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準である、「各ノードの負荷情報を平均したノード平均負荷を算出し、リバランシング設計の計算前後において、算出したノード平均負荷が所定の基準値以上減少していること」を満たす場合に、リバランシングを中止する。
よって、時間の経過によりノード平均負荷が、所定の基準値以上減少した場合には、システム全体としての負荷が下がっているため、リバランシングの実行を不要と判断し、不要なリバランシングを抑制することができる。 In this way, when a node acquires load information from each node constituting the distributed processing system, and there is a node that measures load information that does not fall within a predetermined allowable range, the load of the node is within the allowable range. Rebalancing design is performed so that Then, after the elapse of the rebalancing design time, the node receives load information from each node again, and is a predetermined criterion for rebalancing cancellation, “calculates a node average load obtained by averaging the load information of each node, If the calculated node average load is reduced by a predetermined reference value before or after the rebalancing design calculation, the rebalancing is stopped.
Therefore, when the node average load decreases by more than a predetermined reference value with the passage of time, the load on the entire system is reduced. Therefore, it is determined that rebalancing is unnecessary, and unnecessary rebalancing is suppressed. be able to.

請求項４に記載の発明は、クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、自身のノードの負荷情報を計測するノード負荷計測部と、自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、前記判定基準は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であり、前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止することを特徴とするノードとした。   The invention according to claim 4 is a node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster, and measures a load information of its own node, The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design that changes the data distribution destination so that the load on the node falls within the allowable range, and a rebalancing unit that performs rebalancing based on the rebalancing design, and rebalancing After the design time elapses, load information is acquired again from each node other than itself and other nodes, and rebalancing A rebalancing cancel processing unit that outputs rebalancing cancel instruction information for instructing to stop execution of rebalancing based on the rebalancing design when a predetermined determination criterion for cancellation is satisfied, and Judgment criteria refer to the load information of each node, and node order information obtained by sorting each node based on the magnitude relationship of the load is created before and after the rebalancing design calculation, and the load does not fall within the allowable range. There is a change in the node order information before and after the calculation in the node order, and the rebalancing unit stops executing the rebalancing when receiving the rebalancing cancel instruction information. Node.

このようにすることで、ノードは、分散処理システムを構成する各ノードから負荷情報を取得し、所定の許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を許容範囲に収めるようにリバランシング設計を行う。そして、ノードは、リバランシング設計時間の経過後に、再度各ノードから負荷情報を受信し、リバランシングキャンセルの所定の判定基準である、「各ノードの負荷情報に基づき、負荷が大きい順に各ノードをソートしたノード順位情報を、リバランシング設計の計算前後において作成し、負荷が許容範囲に収まらないノードの順位が、計算前後のノード順位情報において変動があること」を満たす場合に、リバランシングを中止する。
よって、リバランシング設計の計算前後において、負荷が許容範囲に収まらないノードの順位に変動がある場合には、各ノードの負荷状態が安定しておらず、リバランシングを実行しても再度リバランシングを実行すべき状態になる可能性が高くなるため、その時点でのリバランシングの実行を不要と判断する。したがって、不要なリバランシングを抑制することができる。 In this way, when a node acquires load information from each node constituting the distributed processing system, and there is a node that measures load information that does not fall within a predetermined allowable range, the load of the node is within the allowable range. Rebalancing design is performed so that Then, after the rebalancing design time elapses, the node receives the load information from each node again, and is a predetermined criterion for rebalancing cancellation, “Based on the load information of each node, the nodes are listed in descending order of load. If the sorted node order information is created before and after the rebalancing design calculation and the load of the node whose load is not within the allowable range satisfies the fact that there is a change in the node order information before and after the calculation, the rebalancing is canceled. To do.
Therefore, before and after the rebalancing design calculation, if there is a change in the order of nodes whose load does not fall within the allowable range, the load status of each node is not stable and rebalancing is performed even if rebalancing is performed. Therefore, it is determined that execution of rebalancing at that time is unnecessary. Therefore, unnecessary rebalancing can be suppressed.

請求項６に記載の発明は、請求項５に記載のリバランシングキャンセル方法を、コンピュータに実行させるためのプログラムとした。   The invention described in claim 6 is a program for causing a computer to execute the rebalancing canceling method described in claim 5.

このようなプログラムによれば、請求項５に記載のリバランシングキャンセル方法を、一般的なコンピュータで実現することができる。   According to such a program, the rebalancing cancellation method according to claim 5 can be realized by a general computer.

本発明によれば、時間経過の観点を含めてリバランシングの実行が適切か否かを判断し、不要なリバランシングを抑制する、ノード、リバランシングキャンセル方法、および、プログラムを提供することができる。   According to the present invention, it is possible to provide a node, a rebalancing cancellation method, and a program that determine whether or not rebalancing is appropriate, including the passage of time, and suppress unnecessary rebalancing. .

既存のリバランシング手法の問題点を説明するための図である。It is a figure for demonstrating the problem of the existing rebalancing method. 既存のリバランシング手法の問題点を説明するための図である。It is a figure for demonstrating the problem of the existing rebalancing method. 本実施形態に係る分散処理システムの全体構成を示す図である。It is a figure which shows the whole structure of the distributed processing system which concerns on this embodiment. 本実施形態に係る分散処理システムを構成するノードの機能ブロック図である。It is a functional block diagram of the node which comprises the distributed processing system which concerns on this embodiment. 本実施形態に係るノード識別子管理テーブルのデータ構成例を示す図である。It is a figure which shows the data structural example of the node identifier management table which concerns on this embodiment. 本実施形態に係る振り分けＩＤテーブルのデータ構成例を示す図である。It is a figure which shows the data structural example of the distribution ID table which concerns on this embodiment. 本実施形態に係るノードが実行するリバランシング設計を説明するための図である。It is a figure for demonstrating the rebalancing design which the node which concerns on this embodiment performs. 本実施形態に係るリバランシングキャンセルの判定基準（３）を満たさない場合のノード順位テーブルの例を示す図である。It is a figure which shows the example of a node order | rank table | surface when not satisfy | filling the criteria (3) of the rebalancing cancellation which concern on this embodiment. 本実施形態に係るリバランシングキャンセルの判定基準（３）を満たす場合のノード順位テーブルの例を示す図である。It is a figure which shows the example of a node order | rank table | surface when satisfy | filling the determination criterion (3) of the rebalancing cancellation which concerns on this embodiment. 本実施形態に係るノードが実行するリバランシングキャンセル処理の流れを示すフローチャートである。It is a flowchart which shows the flow of the rebalancing cancellation process which the node concerning this embodiment performs.

（課題の詳細な説明）
まず、本実施形態に係るノード１を含む分散処理システム１０００が解決する課題について詳細に説明する。
図１および図２は、既存のリバランシング手法の問題点を説明するための図である。図１は、リバランシング設計前後において、分散処理システム１０００を構成するノードの負荷の例を示すである。
図１（ａ）は、コンシステント・ハッシュのＩＤ空間に配置された各ノード（仮想ノード）の時刻ｔにおける負荷を示している。図１（ａ）の上図に示すように、ノード「Ｂ」の負荷は許容範囲より低く、ノード「Ｅ」の負荷は許容範囲を超えている。ここで、例えば、ノード「Ｂ」の負荷は、下図のコンシステント・ハッシュのＩＤ空間に配置された仮想ノード「Ｂ１」と「Ｂ２」の負荷の合計値となる。また、ノード「Ｅ」の負荷は、下図のコンシステント・ハッシュのＩＤ空間に配置された仮想ノード「Ｅ１」と「Ｅ２」の負荷の合計値となる。なお、例えば、仮想ノード「Ｂ１」の負荷は、仮想ノード「Ａ１」〜「Ｂ１」にはさまれた担当領域の「〇」で示す低負荷のデータの１つを処理する負荷である。仮想ノード「Ｅ２」の負荷は、仮想ノード「Ｄ２」〜「Ｅ２」にはさまれた担当領域の「●」で示す高負荷のデータの２つを処理する負荷である。 (Detailed description of the issue)
First, a problem to be solved by the distributed processing system 1000 including the node 1 according to the present embodiment will be described in detail.
1 and 2 are diagrams for explaining problems of the existing rebalancing method. FIG. 1 shows an example of the load on the nodes constituting the distributed processing system 1000 before and after the rebalancing design.
FIG. 1A shows the load at time t of each node (virtual node) arranged in the consistent hash ID space. As shown in the upper diagram of FIG. 1A, the load of the node “B” is lower than the allowable range, and the load of the node “E” exceeds the allowable range. Here, for example, the load of the node “B” is the total value of the loads of the virtual nodes “B 1 ” and “B 2 ” arranged in the ID space of the consistent hash shown in the figure below. Further, the load of the node “E” is the total value of the loads of the virtual nodes “E 1 ” and “E 2 ” arranged in the ID space of the consistent hash shown in the figure below. Incidentally, for example, the load of the virtual node "B 1" is the load of processing one of the low load of the data indicated by "〇" in charge region between the virtual node "A 1" - "B 1" is there. Load of the virtual node "E 2" is a load of processing two high load data indicated by "●" in charge region between the virtual node "D 2" - "E 2".

時刻ｔにおいて、図１（ａ）に示すように、負荷が許容範囲に収まらないノードがある場合に、既存技術では、コンシステント・ハッシュのＩＤ空間上での配置変更（リバランシング）が実行される。具体的には、このリバランシングを実行するために、負荷が許容範囲に収まらないノードの負荷を許容範囲に収めるようにするための配置変更を設計する処理（リバランシング設計）が時刻ｔに開始され、そのリバランシング設計の計算に係る時間（リバランシング設計時間：Δｔ）後に、実際のコンシステント・ハッシュのＩＤ空間上での配置変更（リバランシング）が実行される。   At time t, as shown in FIG. 1A, when there is a node whose load does not fall within the allowable range, the existing technology performs a relocation of the consistent hash on the ID space (rebalancing). The Specifically, in order to execute this rebalancing, a process (rebalancing design) for designing a placement change for keeping the load of a node whose load is not within the allowable range within the allowable range starts at time t. Then, after the time related to the calculation of the rebalancing design (rebalancing design time: Δt), the arrangement change (rebalancing) of the actual consistent hash on the ID space is executed.

しかしながら、このリバランシング設計時間は、ノード数に依存して通常数秒から数分かかるため、実際に配置変更しようとする時刻（ｔ＋Δｔ）では、各ノードの負荷が変動し、図１（ｂ）に示すように、各ノードがすべて許容範囲に収まっていることもある（上図参照）。
図１（ｂ）では、リバランシング設計時間（Δｔ）内に、仮想ノード「Ｂ１」に高負荷のデータの処理が発生したため負荷が増加し、ノード「Ｂ」が許容範囲に収まるように変動し、仮想ノード「Ｅ２」の高負荷のデータの処理が終了したため負荷が消失し、ノード「Ｅ」が許容範囲に収まるように変動したことを示している。 However, since this rebalancing design time usually takes several seconds to several minutes depending on the number of nodes, the load of each node fluctuates at the time (t + Δt) at which the actual relocation is attempted, as shown in FIG. As shown, each node may be within an acceptable range (see above).
In FIG. 1B, within the rebalancing design time (Δt), processing of high load data has occurred in the virtual node “B 1 ”, so that the load increases and fluctuates so that the node “B” falls within the allowable range. In addition, since the processing of the high load data of the virtual node “E 2 ” is completed, the load disappears and the node “E” fluctuates so as to be within the allowable range.

このように各ノードの負荷が、リバランシング設計時間（Δｔ）内に変動した後、ｔ＋Δｔの時刻において、リバランシングが実際に実行されてしまうと、図２に示すように、ノードの負荷のバランスが崩れ、そのリバランシングの処理の結果として負荷が許容範囲から外れてしまい、再度のリバランシングが必要となる。図２においては、時刻ｔにおいてリバランシング設計が開始され、リバランシング設計が完了した時刻ｔ＋Δｔでは、自然に負荷が許容範囲に収まっていたにもかかわらず、時刻ｔでの負荷情報に基づいてリバランシングを実行してしまう。このため、ノードの負荷が許容範囲を下回る結果となる。よって、時刻ｔ１において、再度リバランシング設計が開始され、リバランシング設計時間（Δｔ）の経過後（時刻ｔ１＋Δｔ）に、実際のリバランシングを実行し、負荷が許容範囲に収まったことを示している。つまり、リバランシングをせずに、許容範囲に収まっていた負荷に対して、２回不要なリバランシング（ＩＤ空間上での配置変更）が発生することになる。 Thus, after the load of each node fluctuates within the rebalancing design time (Δt), when the rebalancing is actually executed at the time t + Δt, as shown in FIG. As a result of the rebalancing process, the load falls outside the allowable range, and rebalancing is necessary. In FIG. 2, the rebalancing design is started at time t, and at time t + Δt when the rebalancing design is completed, the load is naturally within the allowable range, but the rebalancing design is based on the load information at time t. Balancing is executed. For this reason, the load on the node falls below the allowable range. Therefore, the rebalancing design is started again at time t 1 , and after the rebalancing design time (Δt) has elapsed (time t 1 + Δt), the actual rebalancing is executed, and the load is within the allowable range. Show. That is, unnecessary rebalancing (placement change in the ID space) occurs twice for a load that is within the allowable range without performing rebalancing.

本実施形態に係るノード１を含む分散処理システム１０００は、上記のような不要なリバランシングの発生を抑制するため、リバランシング設計時間の経過後に、再度各ノード１の負荷を計測し、後記する所定の判定基準を満たした場合には、リバランシングをキャンセルする。このように、時間経過の観点を含めてリバランシングの実行が適切か否かを判断することにより、不要なリバランシングを抑制するものである。   The distributed processing system 1000 including the node 1 according to the present embodiment measures the load of each node 1 again after the elapse of the rebalancing design time in order to suppress the occurrence of unnecessary rebalancing as described above, which will be described later. If the predetermined criterion is satisfied, the rebalancing is canceled. In this way, unnecessary rebalancing is suppressed by determining whether or not rebalancing is appropriate, including the viewpoint of the passage of time.

＜本実施形態の説明＞
次に、本発明を実施するための形態（以下、「本実施形態」と称する。）における分散処理システム１０００について説明する。
図３は、本実施形態に係る分散処理システム１０００の全体構成を示す図である。 <Description of this embodiment>
Next, a distributed processing system 1000 in a mode for carrying out the present invention (hereinafter referred to as “the present embodiment”) will be described.
FIG. 3 is a diagram showing an overall configuration of the distributed processing system 1000 according to the present embodiment.

この分散処理システム１０００は、複数のノード１から構成される。各ノード１は、コンピュータなどの物理装置や仮想マシンなどの論理装置である。ロードバランサ３は、クライアント２からのメッセージを受信し、単純なラウンドロビン等により振り分けて各ノード１に送信する。そして、ノード１の振り分け部１２は、クライアント２からのメッセージを、例えば、コンシステント・ハッシュ法等に基づき、メッセージを担当するノード１に振り分ける。メッセージを担当するノード１では、信号処理部１３において、信号処理を行い、クライアント２にサービスを提供する。   This distributed processing system 1000 includes a plurality of nodes 1. Each node 1 is a physical device such as a computer or a logical device such as a virtual machine. The load balancer 3 receives a message from the client 2, distributes it by simple round robin or the like, and transmits it to each node 1. Then, the distribution unit 12 of the node 1 distributes the message from the client 2 to the node 1 in charge of the message based on, for example, a consistent hash method. In the node 1 in charge of the message, the signal processing unit 13 performs signal processing and provides a service to the client 2.

なお、ロードバランサ３が存在せず、クライアント２から任意のノード１（振り分け部１２）にメッセージを送信することも可能である。また、振り分け部１２と信号処理部１３とは、同じノード１上に同時に存在してもよいし、別々のノード１上に存在してもよい。
本実施形態の以下の説明では、分散処理システム１０００のデータ管理手法として、ノード１の増減時の影響が少ない、コンシステント・ハッシュ法によるデータ管理手法を例として説明する。ただし、コンシステント・ハッシュ法に限定されるものではない。 Note that the load balancer 3 does not exist, and a message can be transmitted from the client 2 to an arbitrary node 1 (distribution unit 12). Further, the distribution unit 12 and the signal processing unit 13 may exist on the same node 1 at the same time, or may exist on different nodes 1.
In the following description of the present embodiment, as a data management method of the distributed processing system 1000, a data management method based on the consistent hash method that is less affected when the number of nodes 1 is increased or decreased will be described as an example. However, it is not limited to the consistent hash method.

＜ノード＞
次に、本実施形態に係る分散処理システム１０００を構成するノード１について、具体的に説明する。なお、本実施形態に係るノード１は、分散処理システム１０００の複数のノード１のうち、後記するノード識別子管理テーブル１００および振り分けＩＤテーブル２００を管理する特権ノードとなる場合と、特権ノードからノード識別子管理テーブル１００および振り分けＩＤテーブル２００の情報を受け取り自身のノード識別子管理テーブル１００および振り分けＩＤテーブル２００を更新する特権ノードではない場合とが存在する。なお、特権ノードが行う処理等については、後記する。 <Node>
Next, the node 1 constituting the distributed processing system 1000 according to the present embodiment will be specifically described. Note that the node 1 according to the present embodiment is a privileged node that manages the node identifier management table 100 and the distribution ID table 200 described later among the plurality of nodes 1 of the distributed processing system 1000, and the node identifier from the privileged node. There are cases where the node is not a privileged node that receives the information of the management table 100 and the distribution ID table 200 and updates the node identifier management table 100 and the distribution ID table 200 of its own. The processing performed by the privileged node will be described later.

ノード１は、図３に示したように、ロードバランサ３と通信可能に接続されるともに、クラスタを構成する自身以外の他のノード１と通信可能に接続される。また、このノード１は、ロードバランサ３を介してクライアント２からメッセージを受け取ると、そのメッセージを、担当するノード１（自身を含む）に振り分け、そのメッセージの信号処理を実行する。また、特権ノードとなるノード１は、各ノード１から負荷情報を受信し、所定の許容範囲に収まらない負荷であるノード１について、コンシステント・ハッシュのＩＤ空間上の配置変更（リバランシング）を実行する。その際、特権ノードとなるノード１は、リバランシング設計時間（Δｔ）の経過後に再度各ノード１から負荷情報を受信し、所定の判定基準を満たした場合には、リバランシングをキャンセルする。
このノード１は、図４に示すように、制御部１０と、入出力部２０と、記憶部３０とを含んで構成される。 As shown in FIG. 3, the node 1 is communicably connected to the load balancer 3 and is communicably connected to other nodes 1 other than itself constituting the cluster. Further, when the node 1 receives a message from the client 2 via the load balancer 3, the node 1 distributes the message to the responsible node 1 (including itself), and executes signal processing of the message. Further, the node 1 serving as the privileged node receives the load information from each node 1, and changes the arrangement (rebalancing) in the ID space of the consistent hash for the node 1 that is a load that does not fall within the predetermined allowable range. Run. At that time, the node 1 serving as a privileged node receives the load information from each node 1 again after the elapse of the rebalancing design time (Δt), and cancels the rebalancing when a predetermined determination criterion is satisfied.
As illustrated in FIG. 4, the node 1 includes a control unit 10, an input / output unit 20, and a storage unit 30.

入出力部２０は、ロードバランサ３や、自身以外の他のノード１との間の情報の入出力を行う。また、この入出力部２０は、通信回線を介して情報の送受信を行う不図示の通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。   The input / output unit 20 inputs / outputs information to / from the load balancer 3 and other nodes 1 other than itself. The input / output unit 20 performs input / output between a communication interface (not shown) that transmits and receives information via a communication line and an input means such as a keyboard (not shown) and an output means such as a monitor. And an output interface.

記憶部３０は、ハードディスクやフラッシュメモリ、ＲＡＭ（Random Access Memory）等の記憶手段からなり、処理の対象となるデータ３００や、ノード識別子管理テーブル１００（図５参照）、振り分けＩＤテーブル２００（図６参照）、ノード１自身のノード負荷を計測した情報であるノード負荷計測情報４００が記憶される。さらに、ノード１が特権ノードである場合には、各ノード１のノード負荷情報をまとめた情報であるシステム負荷情報５００、各ノード１のリバランシング設計に用いる負荷量（負荷情報）を降順に並べた情報であるノード順位テーブル６００α（ノード順位情報）（図８、図９参照）、各ノードのリバランシング設計直後の負荷量（負荷情報）を降順に並べた情報であるノード順位テーブル６００β（ノード順位情報）（図８、図９参照）が記憶される。また、許容範囲を示す閾値（上限閾値や下限閾値）や後記する所定の基準値等の各パラメータに関する情報が格納される。なお、この記憶部３０に記憶される各情報についての詳細は後記する。   The storage unit 30 includes storage means such as a hard disk, flash memory, and RAM (Random Access Memory). The storage unit 30 includes data 300 to be processed, a node identifier management table 100 (see FIG. 5), and a distribution ID table 200 (FIG. 6). Reference), node load measurement information 400, which is information obtained by measuring the node load of node 1 itself, is stored. Further, when the node 1 is a privileged node, the system load information 500, which is information that summarizes the node load information of each node 1, and the load amount (load information) used for the rebalancing design of each node 1 are arranged in descending order. Node ranking table 600α (node ranking information) (see FIGS. 8 and 9), and node ranking table 600β (node information) in which the load amount (load information) immediately after rebalancing design of each node is arranged in descending order. Order information) (see FIGS. 8 and 9) is stored. In addition, information regarding each parameter such as a threshold indicating an allowable range (upper limit threshold or lower limit threshold) and a predetermined reference value described later is stored. Details of each piece of information stored in the storage unit 30 will be described later.

制御部１０は、ノード１全体の制御を司り、ノード識別子管理部１１、振り分け部１２、信号処理部１３、ノード負荷計測部１４、リバランシング部１５およびリバランシングキャンセル処理部１６を含んで構成される。なお、この制御部１０は、例えば、記憶部３０に格納されたプログラムをＣＰＵ（Central Processing Unit）（図示省略）がＲＡＭ（図示省略）に展開し実行することで実現される。   The control unit 10 controls the entire node 1, and includes a node identifier management unit 11, a distribution unit 12, a signal processing unit 13, a node load measurement unit 14, a rebalancing unit 15, and a rebalancing cancellation processing unit 16. The The control unit 10 is realized, for example, by a CPU (Central Processing Unit) (not shown) developing and executing a program stored in the storage unit 30 on a RAM (not shown).

ノード識別子管理部１１は、分散処理システム１０００においてクラスタを構成する各ノード１のノード情報（ＩＰアドレス等）および各ノード１が担当するＩＤ空間を管理する。
具体的には、ノード識別子管理部１１は、自身が属する分散処理システム１０００へのノードの追加や離脱が発生した場合に、その分散処理システム１０００を構成するノード１の識別情報等を更新し、ノード識別子管理テーブル１００として管理する。 The node identifier management unit 11 manages the node information (IP address and the like) of each node 1 configuring the cluster in the distributed processing system 1000 and the ID space handled by each node 1.
Specifically, the node identifier management unit 11 updates the identification information and the like of the node 1 constituting the distributed processing system 1000 when a node is added or removed from the distributed processing system 1000 to which the node identifier belongs. The node identifier management table 100 is managed.

図５は、本実施形態に係るノード識別子管理テーブル１００のデータ構成例を示す図である。
図５に示すように、ノード識別子管理テーブル１００には、分散処理システム１０００を構成する各ノード１のノード識別子１０１とアドレス１０２（例えば、ＩＰアドレス）とが対応付けられて格納される。 FIG. 5 is a diagram illustrating a data configuration example of the node identifier management table 100 according to the present embodiment.
As shown in FIG. 5, the node identifier management table 100 stores the node identifier 101 and the address 102 (for example, IP address) of each node 1 constituting the distributed processing system 1000 in association with each other.

このノード識別子１０１は、例えば、当該分散処理システム１０００内において予め設定される特定のノード（例えば、ノード識別子１０１の昇順に設定）のノード識別子管理部１１で付与され、当該分散処理システム１０００内の各ノード１に配信される。なお、このノード識別子１０１は、コンシステント・ハッシュのＩＤ空間において仮想ＩＤを用いる場合、仮想ＩＤ毎に付与される。   The node identifier 101 is given by, for example, the node identifier management unit 11 of a specific node (for example, set in ascending order of the node identifier 101) set in advance in the distributed processing system 1000. Distributed to each node 1. The node identifier 101 is assigned to each virtual ID when a virtual ID is used in the consistent hash ID space.

また、ノード識別子管理部１１は、ノード識別子管理テーブル１００の更新（ノード１の増減設）に合わせて、ノード１の担当するＩＤ空間情報を更新し、振り分けＩＤテーブル２００として管理する。   Further, the node identifier management unit 11 updates the ID space information in charge of the node 1 in accordance with the update of the node identifier management table 100 (increase / decrease of the node 1), and manages it as the distribution ID table 200.

図６は、本実施形態に係る振り分けＩＤテーブル２００のデータ構成例を示す図である。
図６に示すように、振り分けＩＤテーブル２００には、ノード識別子２０１に対応付けて、そのノード１が担当するＩＤ空間２０２が格納される。このノード識別子２０１は、図５のノード識別子１０１と同様の情報である。図６に示す例では、ＩＤ空間の全ＩＤ数が「０」〜「９９９」の「１０００」であり、例えば、ノード識別子２０１が「Ａ」のノード１が、担当するＩＤ空間２０２として「０〜１９９」について担当することを示している。 FIG. 6 is a diagram illustrating a data configuration example of the distribution ID table 200 according to the present embodiment.
As shown in FIG. 6, the distribution ID table 200 stores an ID space 202 that the node 1 is responsible for in association with the node identifier 201. This node identifier 201 is the same information as the node identifier 101 of FIG. In the example illustrated in FIG. 6, the total number of IDs in the ID space is “1000” from “0” to “999”. For example, the node 1 whose node identifier 201 is “A” is “0” as the ID space 202 in charge. To 199 ”.

分散処理システム１０００内の特権ノードは、各ノード１に対して、最新のノード識別子管理テーブル１００および振り分けＩＤテーブル２００を送信する。これにより、各ノード１のノード識別子管理部１１は、ノード識別子管理テーブル１００および振り分けＩＤテーブル２００を常に最新の状態に更新して保持する。このようにすることにより、分散処理システム１０００内の各ノード１には、同一のノード識別子管理テーブル１００および振り分けＩＤテーブル２００が保持される。   The privileged node in the distributed processing system 1000 transmits the latest node identifier management table 100 and the distribution ID table 200 to each node 1. Accordingly, the node identifier management unit 11 of each node 1 always updates and holds the node identifier management table 100 and the distribution ID table 200 in the latest state. By doing so, each node 1 in the distributed processing system 1000 holds the same node identifier management table 100 and distribution ID table 200.

また、特権ノードは、例えば、このノード識別子管理テーブル１００の一番上の行のノード１から順に、特権ノードとなるように設定される。ノード１が新たに特権ノードになった場合、自身が特権ノードであることを示す情報を、各ノード１等に送信する。そして、特権ノードは、クラスタ内のノード１についてリバランシング（ＩＤ空間上での配置変更）があった場合に、自身の振り分けＩＤテーブル２００を更新し、その更新情報を、各ノード１に配信する。   Further, the privileged nodes are set so as to become privileged nodes in order from the node 1 in the top row of the node identifier management table 100, for example. When node 1 newly becomes a privileged node, information indicating that it is a privileged node is transmitted to each node 1 or the like. Then, when there is rebalancing (placement change in the ID space) for node 1 in the cluster, the privileged node updates its own distribution ID table 200 and distributes the update information to each node 1. .

図４に戻り、振り分け部１２は、ロードバランサ３等を介してクライアント２から発呼されるメッセージ内の情報（「振り分けキー」）をもとに「ｈａｓｈ（ｋｅｙ）」を算出し、振り分けＩＤテーブル２００を参照して、そのメッセージの処理を担当するノード１を特定する。そして、振り分け部１２は、特定したノード１のアドレスの情報を、ノード識別子管理テーブル１００を参照して取得し、特定したノード１へメッセージの振り分け（送信）を行う。
また、信号処理部１３は、自身のノード１が担当するデータに関するメッセージの信号処理を実行する。 Returning to FIG. 4, the distribution unit 12 calculates “hash (key)” based on the information (“distribution key”) in the message called from the client 2 via the load balancer 3 or the like, and determines the distribution ID. With reference to the table 200, the node 1 in charge of processing the message is specified. Then, the distribution unit 12 acquires information on the address of the identified node 1 with reference to the node identifier management table 100, and distributes (transmits) the message to the identified node 1.
In addition, the signal processing unit 13 performs signal processing of messages related to data handled by the node 1 itself.

ノード負荷計測部１４は、所定の周期や、後記する特権ノードによるリバランシング設計時間（Δｔ）の経過直後においてノード負荷計測要求等を特権ノードから受信した場合に、自身のノード１のノード負荷（負荷情報）を計測し、自身の記憶部３０内にノード負荷計測情報４００として記憶する。そして、ノード負荷計測部１４は、その計測したノード負荷（負荷情報）を、特権ノードに送信する。
ノード負荷計測部１４が計測するノード負荷は、例えば、メモリ使用量、ＣＰＵ使用率、アクセス頻度等である。 The node load measurement unit 14 receives a node load measurement request or the like from a privileged node immediately after a predetermined period or a rebalancing design time (Δt) by a privileged node to be described later has elapsed. Load information) is measured and stored as node load measurement information 400 in its own storage unit 30. Then, the node load measurement unit 14 transmits the measured node load (load information) to the privileged node.
The node load measured by the node load measuring unit 14 is, for example, a memory usage amount, a CPU usage rate, an access frequency, or the like.

以下説明する、リバランシング部１５およびリバランシングキャンセル処理部１６は、各ノード１が備えるが、ノード１自身が特権ノードの場合に動作する。
リバランシング部１５は、各ノード１の負荷情報に基づき、リバランシングの実行判定を行う。そして、リバランシング部１５は、リバランシングを実行すると判定した場合には、コンシステント・ハッシュのＩＤ空間上でのノードの配置変更の計算（リバランシング設計）を行い、リバランシングを実行する。なお、リバランシング部１５は、リバランシングキャンセル処理部１６から、リバランシングキャンセル指示情報を受け付けた場合には、当該リバランシングの実行を中止する。以下、リバランシング部１５の処理を具体的に説明する。 The rebalancing unit 15 and the rebalancing cancel processing unit 16 described below are provided in each node 1, but operate when the node 1 itself is a privileged node.
The rebalancing unit 15 performs rebalancing execution determination based on the load information of each node 1. If the rebalancing unit 15 determines that rebalancing is to be performed, the rebalancing unit 15 calculates the relocation of the node on the consistent hash ID space (rebalancing design) and executes rebalancing. When the rebalancing unit 15 receives rebalancing cancellation instruction information from the rebalancing cancellation processing unit 16, the rebalancing unit 15 stops the rebalancing. Hereinafter, the process of the rebalancing part 15 is demonstrated concretely.

リバランシング部１５は、各ノード１から負荷情報を取得し、記憶部３０内のシステム負荷情報５００に格納する。
そして、リバランシング部１５は、各ノード１の負荷情報を参照し、その負荷情報が許容範囲に収まっているか否かを判定する。具体的には、リバランシング部１５は、その負荷情報（例えば、メモリ使用量、ＣＰＵ使用率、アクセス頻度等）について予め設定した、上限閾値を超えているか、下限閾値未満であるか、を判定する。このどちらかの条件を満たす場合に、リバランシング部１５は、リバランシングが必要であると判定し、リバランシング設計を開始する。 The rebalancing unit 15 acquires load information from each node 1 and stores it in the system load information 500 in the storage unit 30.
Then, the rebalancing unit 15 refers to the load information of each node 1 and determines whether or not the load information is within an allowable range. Specifically, the rebalancing unit 15 determines whether the load information (for example, memory usage, CPU usage rate, access frequency, etc.) exceeds the upper limit threshold or less than the lower limit threshold set in advance. To do. When either of these conditions is satisfied, the rebalancing unit 15 determines that rebalancing is necessary and starts rebalancing design.

リバランシング部１５は、リバランシング設計（ＩＤ空間上でのノードの配置変更）を以下のようにして行う。なお、ここでは、負荷が上限閾値を超えたノード１（ここでは、ノード「Ｄ」とする。）について、負荷を低減させるリバランシングを行うものとして説明する。   The rebalancing unit 15 performs rebalancing design (node placement change in the ID space) as follows. Here, description will be made assuming that rebalancing for reducing the load is performed on the node 1 (here, node “D”) whose load exceeds the upper limit threshold.

図７は、リバランシング部１５が実行するリバランシング設計を説明するための図である。リバランシング部１５は、リバランシングが必要と判定したノード１を特定した上で、その特定したノード１からみて、ＩＤ空間において両隣のノードを抽出する。図７においては、リバランシングが必要と判定したノード「Ｄ」の両隣のノード「Ｃ」とノード「Ｅ」とが抽出される。
次に、リバランシング部１５は、抽出した両隣のノードのうち、負荷が少ないノードを選択する。図７（ａ）は、負荷が少ないノードとしてノード「Ｃ」が選択された例を示し、図７（ｂ）は、負荷が少ないノードとしてノード「Ｅ」が選択された例を示している。 FIG. 7 is a diagram for explaining the rebalancing design performed by the rebalancing unit 15. The rebalancing unit 15 identifies the node 1 determined to require rebalancing, and then extracts both adjacent nodes in the ID space as seen from the identified node 1. In FIG. 7, the nodes “C” and “E” on both sides of the node “D” determined to require rebalancing are extracted.
Next, the rebalancing unit 15 selects a node with a low load among the extracted adjacent nodes. FIG. 7A shows an example in which the node “C” is selected as a node having a low load, and FIG. 7B shows an example in which the node “E” is selected as a node having a low load.

リバランシング部１５は、負荷が少ないノードとしてノード「Ｃ」が選択された場合、図７（ａ）に示すように、ノード「Ｃ」のＩＤ空間における担当領域が増えるように（つまり、ノード「Ｄ」の担当領域が減るように）、ノード「Ｃ」のＩＤ空間上の位置を移動する。
一方、リバランシング部１５は、負荷が少ないノードとしてノード「Ｅ」が選択された場合、図７（ｂ）に示すように、ノード「Ｅ」のＩＤ空間における担当領域が増えるように（つまり、ノード「Ｄ」の担当領域が減るように）、ノード「Ｄ」のＩＤ空間上の位置を移動する。 When the node “C” is selected as a node with a low load, the rebalancing unit 15 increases the assigned area in the ID space of the node “C” as shown in FIG. The position in the ID space of the node “C” is moved so that the area in charge of “D” is reduced).
On the other hand, when the node “E” is selected as a node with a low load, the rebalancing unit 15 increases the assigned area in the ID space of the node “E” as shown in FIG. The position of the node “D” in the ID space is moved so that the area in charge of the node “D” decreases.

リバランシング部１５は、このように、リバランシング設計を実行した後に、リバランシングキャンセル処理部１６から、リバランシングキャンセル指示情報を受け付けたか否かを判定し、リバランシングキャンセル指示情報を受け付けていない場合には、リバランシング設計に基づき、実際のリバランシング（ＩＤ空間上での配置変更）を実行する。なお、リバランシング部１５は、図６に示した振り分けＩＤテーブル２００のＩＤ空間２０２の値を変更することにより、リバランシング（ＩＤ空間上での配置変更）を行う。   The rebalancing unit 15 thus determines whether or not rebalancing cancel instruction information has been received from the rebalancing cancel processing unit 16 after executing the rebalancing design, and has not received rebalancing cancel instruction information. The actual rebalancing (placement change in the ID space) is executed based on the rebalancing design. The rebalancing unit 15 performs rebalancing (placement change in the ID space) by changing the value of the ID space 202 of the distribution ID table 200 shown in FIG.

図４に戻り、リバランシングキャンセル処理部１６は、リバランシング部１５によるリバランシング設計時間（Δｔ）の経過後、つまり、リバランシング部１５によりリバランシング設計が終わると、例えば、各ノード１に対し、ノード負荷計測要求を送信することにより、再度各ノード１から負荷情報を受信し、以下に示す判定基準を満たす場合には、リバランシングキャンセルすることを示すリバランシングキャンセル指示情報をリバランシング部１５に出力する。   Returning to FIG. 4, after the rebalancing design time (Δt) by the rebalancing unit 15 has elapsed, that is, when the rebalancing design is completed by the rebalancing unit 15, the rebalancing cancellation processing unit 16 When the load information is received from each node 1 again by transmitting a node load measurement request and the following criteria are satisfied, rebalancing cancel instruction information indicating that rebalancing cancellation is to be performed is sent to the rebalancing unit 15. Output to.

≪リバランシングキャンセルの判定基準≫
リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）の経過後の各ノード１の負荷情報に基づき、以下の判定基準（１）〜（３）のいずれかに該当する場合には、リバランシングの実行をキャンセルする。 ≪Criteria for rebalancing cancellation≫
Based on the load information of each node 1 after the elapse of the rebalancing design time (Δt), the rebalancing cancellation processing unit 16 performs the rebalancing cancellation processing unit 16 when any of the following criteria (1) to (3) is met. Cancel the execution of balancing.

〔判定基準（１）〕各ノード１の負荷が許容範囲内に収まっている。
例えば、リバランシング設計時間（Δｔ）経過後の各ノード１の負荷が、分散処理システム１０００を構成するすべてのノード１の平均負荷（以下、「ノード平均負荷」と称する。）の±５％以内（許容範囲）に収まっている。このような場合に、リバランシングキャンセル処理部１６は、すでに、各ノード１の負荷が許容範囲に収まっているため、リバランシングは中止と判定し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。 [Criteria (1)] The load of each node 1 is within the allowable range.
For example, the load of each node 1 after the elapse of the rebalancing design time (Δt) is within ± 5% of the average load of all the nodes 1 constituting the distributed processing system 1000 (hereinafter referred to as “node average load”). (Tolerable range). In such a case, the rebalancing cancel processing unit 16 has already determined that the rebalancing is to be stopped because the load of each node 1 is within the allowable range, and outputs the rebalancing cancel instruction information to the rebalancing unit 15. To do.

〔判定基準（２）〕ノード平均負荷が、リバランシング設計の計算の前後で、所定の基準値以上に減少している。
この場合、リバランシングキャンセル処理部１６は、リバランシング部１５が、負荷情報が許容範囲に収まっていないノード１が存在する、つまり、リバランシングが必要であると判定したときに、その時点のノード平均負荷を計算しておく。また、リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）経過後の各ノード１の負荷に基づき、ノード平均負荷を計算する。そして、リバランシングキャンセル処理部１６は、リバランシング設計の計算前後のノード平均負荷を比較し、所定の基準値（例えば、計算前のノード平均負荷の２０％）以上、計算後のノード平均負荷が減少している場合に、リバランシングは中止と判定し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
この判定基準（２）は、ノード平均負荷が所定の基準値（例えば、２０％）以上、減少している場合には、全体としてノード１の負荷がかなり下がった状態となっており、この状態のときにさらに、リバランシングを実行すると、よりバランスを崩す（許容範囲から外れる）結果になる可能性が高いことに基づく。 [Decision Criteria (2)] The node average load has decreased to a predetermined reference value or more before and after the rebalancing design calculation.
In this case, when the rebalancing unit 15 determines that there is a node 1 whose load information is not within the allowable range, that is, the rebalancing unit 15 determines that rebalancing is necessary, Calculate the average load. Further, the rebalancing cancel processing unit 16 calculates the node average load based on the load of each node 1 after the rebalancing design time (Δt) has elapsed. Then, the rebalancing cancellation processing unit 16 compares the node average loads before and after the calculation of the rebalancing design, and the node average load after the calculation is greater than a predetermined reference value (for example, 20% of the node average load before the calculation). If it is decreased, it is determined that the rebalancing is stopped, and the rebalancing cancel instruction information is output to the rebalancing unit 15.
In this criterion (2), when the node average load is decreased by a predetermined reference value (for example, 20%) or more, the load on the node 1 as a whole is considerably reduced. Further, if rebalancing is performed at this time, it is more likely to result in a more unbalanced (out of tolerance) result.

〔判定基準（３）〕負荷が許容範囲外であるノード１のノード順位に変動がある。
判定基準（３）において、リバランシングキャンセル処理部１６は、リバランシング部１５が、負荷情報が許容範囲に収まっていないノード１が存在する、つまり、リバランシングが必要であると判定したときに、その時点の各ノード１のノード負荷に基づき、その負荷の大きさを降順でソートした情報であるノード順位テーブルを作成する。このとき作成されたノード順位テーブルを「ノード順位テーブル６００α」と称する。また、リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）経過後の各ノード１の負荷に基づき、同じく負荷の大きさを降順でソートしたノード順位テーブルを作成する。このとき作成されたノード順位テーブルを「ノード順位テーブル６００β」と称する。
なお、ここでは、リバランシングキャンセル処理部１６が、負荷の大きさを降順でソートしノード順位テーブルを作成するものとして説明するが、負荷の大きさを昇順でソートしノード順位テーブルを作成してもよい。つまり、リバランシングキャンセル処理部１６は、負荷の大小関係に基づいてソートし、ノード順位テーブルを作成する。
リバランシングキャンセル処理部１６は、リバランシング設計の計算前後のノード順位テーブルにおいて、負荷が許容範囲外であるノード１のノード順位に変動があるかを判定し、変動がある場合には、リバランシングは中止と判定し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。 [Criteria (3)] There is a change in the node order of the node 1 whose load is outside the allowable range.
In the criterion (3), when the rebalancing cancel processing unit 16 determines that the node 1 whose load information is not within the allowable range exists, that is, the rebalancing unit 15 determines that rebalancing is necessary, Based on the node load of each node 1 at that time, a node ranking table that is information obtained by sorting the magnitudes of the loads in descending order is created. The node order table created at this time is referred to as a “node order table 600α”. Further, the rebalancing cancel processing unit 16 creates a node ranking table in which the magnitudes of the loads are similarly sorted in descending order based on the loads of the respective nodes 1 after the elapse of the rebalancing design time (Δt). The node ranking table created at this time is referred to as a “node ranking table 600β”.
In this example, the rebalancing cancel processing unit 16 is described as creating a node order table by sorting the load magnitudes in descending order. However, the node order table is created by sorting the load magnitudes in ascending order. Also good. That is, the rebalancing cancel processing unit 16 sorts based on the magnitude relation of the load, and creates a node order table.
The rebalancing cancellation processing unit 16 determines whether or not there is a change in the node order of the node 1 whose load is out of the allowable range in the node order table before and after the rebalancing design calculation. Is determined to be canceled, and rebalancing cancel instruction information is output to the rebalancing unit 15.

図８は、リバランシングキャンセルの判定基準（３）を満たさない場合のノード順位テーブル（ノード順位情報）の例を示す図である。また、図９は、リバランシングキャンセルの判定基準（３）を満たす場合のノード順位テーブル（ノード順位情報）の例を示す図である。   FIG. 8 is a diagram illustrating an example of the node order table (node order information) when the rebalancing cancellation determination criterion (3) is not satisfied. FIG. 9 is a diagram illustrating an example of a node order table (node order information) when the determination criterion (3) for rebalancing cancellation is satisfied.

図８は、例えば、ノード１の負荷情報としてメモリ使用量が採用された場合において、許容範囲が５０〜９０（ＭＢ）に設定された例を示す。図８（ａ）に示すように、リバランシング設計前のノード順位テーブル６００αにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ａ」「Ｄ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。
これに対し、図８（ｂ）に示すように、リバランシング設計時間（Δｔ）経過後のノード順位テーブル６００βにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ａ」「Ｄ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。つまり、負荷が許容範囲外にあるノード１の順に変動はない。よって、リバランシングキャンセル処理部１６は、判定基準（３）を満たさないと判断する。これにより、リバランシング部１５によるリバランシングが実行される。 FIG. 8 shows an example in which the allowable range is set to 50 to 90 (MB) when the memory usage is adopted as the load information of the node 1, for example. As shown in FIG. 8A, in the node order table 600α before rebalancing design, the nodes 1 with node orders “1”, “2”, and “3” whose loads are outside the allowable range (exceeding the upper limit threshold) In order, nodes “A”, “D”, and “F”. In addition, the nodes 1 with node ranks “10”, “11”, and “12” whose loads are outside the allowable range (less than the lower threshold) are nodes “C”, “E”, and “G” in order.
On the other hand, as shown in FIG. 8B, in the node order table 600β after the rebalancing design time (Δt) has elapsed, the node orders “1” and “2” where the load is outside the allowable range (exceeds the upper limit threshold value). The nodes 1 of “3” are nodes “A”, “D”, and “F” in this order. In addition, the nodes 1 with node ranks “10”, “11”, and “12” whose loads are outside the allowable range (less than the lower threshold) are nodes “C”, “E”, and “G” in order. That is, there is no change in the order of the node 1 whose load is outside the allowable range. Therefore, the rebalancing cancellation processing unit 16 determines that the determination criterion (3) is not satisfied. Thereby, the rebalancing by the rebalancing unit 15 is executed.

一方、図９においては、図８（ａ）と同様、図９（ａ）に示すように、リバランシング設計前のノード順位テーブル６００αにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ａ」「Ｄ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。
これに対し、図９（ｂ）に示すように、リバランシング設計時間（Δｔ）経過後のノード順位テーブル６００βにおいて、負荷が許容範囲外（上限閾値を超える）であるノード順位「１」「２」「３」のノード１は、順に、ノード「Ｄ」「Ａ」「Ｆ」である。また、負荷が許容範囲外（下限閾値未満）であるノード順位「１０」「１１」「１２」のノード１は、順に、ノード「Ｃ」「Ｅ」「Ｇ」である。よって、ノード順位がノード「Ａ」と「Ｄ］とで変動している。従って、リバランシングキャンセル処理部１６は、判定基準（３）を満たすと判断し、リバランシングキャンセル指示情報をリバランシング部１５に出力する。 On the other hand, in FIG. 9, similarly to FIG. 8A, as shown in FIG. 9A, in the node order table 600α before rebalancing design, the node whose load is outside the allowable range (exceeds the upper limit threshold value). The nodes 1 of the ranks “1”, “2”, and “3” are nodes “A”, “D”, and “F” in order. In addition, the nodes 1 with node ranks “10”, “11”, and “12” whose loads are outside the allowable range (less than the lower threshold) are nodes “C”, “E”, and “G” in order.
On the other hand, as shown in FIG. 9B, in the node order table 600β after the rebalancing design time (Δt) has elapsed, the node orders “1” and “2” whose load is outside the allowable range (exceeding the upper limit threshold value). The nodes 1 of “3” are nodes “D”, “A”, and “F” in this order. In addition, the nodes 1 with node ranks “10”, “11”, and “12” whose loads are outside the allowable range (less than the lower threshold) are nodes “C”, “E”, and “G” in order. Therefore, the node order varies between the nodes “A” and “D.” Therefore, the rebalancing cancellation processing unit 16 determines that the determination criterion (3) is satisfied, and sends the rebalancing cancellation instruction information to the rebalancing unit. 15 is output.

判定基準（３）は、負荷が許容範囲外であるノードの順位に変動のある場合には、リバランシングを実行した後においても、負荷が許容範囲に収まらないノード１が発生する可能性が高いことに基づく。つまり、負荷の変動の激しいときには、リバランシングを行わず、変動が落ち着いた後に、リバランシングを実行するという考えに基づく。
よって、判定基準（３）において、「ノード順位に変動がある」場合とは、リバランシング設計の計算前のノード順位テーブル６００αにおいては、許容範囲に収まっていたノードが、許容範囲外に変動した場合や、許容範囲外であったノードが、許容範囲に収まった場合も「ノードの順位に変動がある」とし、判定基準（３）を満たすと判断して、リバランシングキャンセル指示情報をリバランシング部１５に出力する。 In the criterion (3), when there is a change in the order of nodes whose load is outside the allowable range, there is a high possibility that a node 1 whose load does not fall within the allowable range will occur even after rebalancing is performed. Based on that. In other words, it is based on the idea that rebalancing is not performed when the load fluctuates heavily, and rebalancing is performed after the fluctuation has settled.
Therefore, in the criterion (3), the case where “the node order varies” means that in the node order table 600α before the rebalancing design calculation, the nodes that were within the allowable range changed outside the allowable range. If a node that is outside the allowable range falls within the allowable range, it is determined that the order of the nodes is changed, and the determination criterion (3) is satisfied, and the rebalancing cancellation instruction information is rebalanced. To the unit 15.

リバランシングキャンセル処理部１６は、上記のリバランシングキャンセルの判定基準（１）（２）（３）のいずれかに該当する場合には、リバランシングキャンセル指示情報をリバランシング部１５に出力する。
ただし、リバランシングキャンセル処理部１６において、この判定基準（１）（２）（３）のすべてを用いず、判定基準（１）（２）（３）のうちのいずれか１つや、いずれか２つの組み合わせを設定し、リバランシングをキャンセルするか否かを判定するようにしてもよい。このようにすることによっても、不要なリバランシングを抑制することができる。 The rebalancing cancel processing unit 16 outputs rebalancing cancel instruction information to the rebalancing unit 15 when any of the above rebalancing cancellation determination criteria (1), (2), and (3) is satisfied.
However, the rebalancing cancel processing unit 16 does not use all of the determination criteria (1), (2), and (3), and any one of the determination criteria (1), (2), and (3), or any two One combination may be set to determine whether or not to cancel the rebalancing. In this way, unnecessary rebalancing can be suppressed.

リバランシングキャンセル処理部１６からリバランシングキャンセル指示情報を受け取ったリバランシング部１５は、リバランシングの実行を行わない。このようにすることにより、不要なリバランシングを抑制することができる。   The rebalancing unit 15 that has received the rebalancing cancel instruction information from the rebalancing cancel processing unit 16 does not execute rebalancing. By doing so, unnecessary rebalancing can be suppressed.

＜処理の流れ＞
次に、本実施形態に係るノード１が実行する、リバランシングキャンセル処理について、図１０を参照して説明する。図１０は、本実施形態に係るノード１が実行するリバランシングキャンセル処理の流れを示すフローチャートである。なお、このリバランシングキャンセル処理は、分散処理システム１０００を構成するノード１のうち、特権ノードが行う処理である。 <Process flow>
Next, rebalancing cancel processing executed by the node 1 according to the present embodiment will be described with reference to FIG. FIG. 10 is a flowchart showing the flow of rebalancing cancellation processing executed by the node 1 according to this embodiment. This rebalancing cancellation process is a process performed by a privileged node among the nodes 1 constituting the distributed processing system 1000.

まず、ノード１（特権ノード）のリバランシング部１５は、例えば、所定の時間間隔で、各ノード１から負荷情報を受信する（ステップＳ１）。そして、リバランシング部１５は、受信した各ノード１の負荷情報を記憶部３０のシステム負荷情報５００に記憶する。   First, the rebalancing unit 15 of the node 1 (privileged node) receives load information from each node 1 at a predetermined time interval, for example (step S1). Then, the rebalancing unit 15 stores the received load information of each node 1 in the system load information 500 of the storage unit 30.

続いて、リバランシング部１５は、各ノード１の負荷情報を参照し、その負荷情報が許容範囲に収まっているか否かを判定する。つまり、リバランシング部１５は、リバランシングが必要か否かを判定する（ステップＳ２）。具体的には、リバランシング部１５は、各ノード１の負荷が、予め設定した、上限閾値を超えているか、下限閾値未満であるか、を判定する。即ち、各ノード１の負荷が許容範囲外であるか否かを判定する。   Subsequently, the rebalancing unit 15 refers to the load information of each node 1 and determines whether or not the load information is within the allowable range. That is, the rebalancing unit 15 determines whether or not rebalancing is necessary (step S2). Specifically, the rebalancing unit 15 determines whether the load of each node 1 exceeds a preset upper limit threshold or less than a lower limit threshold. That is, it is determined whether or not the load on each node 1 is outside the allowable range.

ここで、リバランシングが不要であると判定された場合には（ステップＳ２→Ｎｏ）、処理を終了する。一方、リバランシングが必要であると判定された場合には（ステップＳ２→Ｙｅｓ）、次にステップＳ３に進む。   If it is determined that rebalancing is not necessary (step S2 → No), the process is terminated. On the other hand, if it is determined that rebalancing is necessary (step S2 → Yes), the process proceeds to step S3.

ステップＳ３において、リバランシングキャンセル処理部１６は、後記するステップＳ８における判定に備えて、リバランシング設計の計算前における、ノード平均負荷を算出し、記憶部３０に記憶しておく。また、リバランシングキャンセル処理部１６は、後記するステップＳ１０における判定に備えて、各ノード１の負荷情報に基づき、その負荷の大きさを降順でソートした情報であるノード順位テーブル６００αを作成し、記憶部３０に記憶しておく。なお、ノード平均負荷は、リバランシングキャンセルの判定基準（２）を満たすか否かの判定に用いられる。また、ノード順位テーブル６００αは、リバランシングキャンセルの判定基準（３）を満たすか否かの判定に用いられる。   In step S <b> 3, the rebalancing cancellation processing unit 16 calculates the node average load before the rebalancing design calculation and stores it in the storage unit 30 in preparation for the determination in step S <b> 8 described later. Further, the rebalancing cancellation processing unit 16 creates a node order table 600α that is information obtained by sorting the magnitudes of the loads in descending order based on the load information of each node 1 in preparation for the determination in step S10 described later. Store in the storage unit 30. The node average load is used to determine whether or not the rebalancing cancellation determination criterion (2) is satisfied. The node order table 600α is used to determine whether or not the rebalancing cancellation determination criterion (3) is satisfied.

続いて、リバランシング部１５は、リバランシング設計を実行する（ステップＳ４）。具体的には、リバランシング部１５は、リバランシングが必要と判定した（許容範囲外であるとした）ノード１を特定した上で、その特定したノード１からみて、ＩＤ空間において両隣のノードを抽出し、その抽出した両隣のノードのうち、負荷が少ないノードを選択する。そして、その選択した負荷が少ないノードの負荷が増えるように、ＩＤ空間上の位置を移動するように設計する。   Subsequently, the rebalancing unit 15 executes rebalancing design (step S4). Specifically, the rebalancing unit 15 identifies the node 1 that has been determined to require rebalancing (assuming that it is out of the allowable range), and determines the adjacent nodes in the ID space from the identified node 1. Extraction is performed, and a node with a low load is selected from the extracted adjacent nodes. Then, it is designed to move the position in the ID space so that the load of the selected node with a small load increases.

次に、リバランシングキャンセル処理部１６は、リバランシング設計時間（Δｔ）の経過後、例えば、各ノード１に対し、ノード負荷計測要求を送信することにより、各ノード１から再度、負荷情報を受信する（ステップＳ５）。そして、リバランシングキャンセル処理部１６は、受信した各ノード１の負荷情報を記憶部３０のシステム負荷情報５００に記憶する。   Next, after the rebalancing design time (Δt) has elapsed, the rebalancing cancellation processing unit 16 receives load information from each node 1 again by transmitting a node load measurement request to each node 1, for example. (Step S5). Then, the rebalancing cancellation processing unit 16 stores the received load information of each node 1 in the system load information 500 of the storage unit 30.

続いて、リバランシングキャンセル処理部１６は、上記したリバランシングキャンセルの判定基準（１）、判定基準（２）、判定基準（３）のうち、いずれか１つでも満たすか否かを判定する。具体的には、次のステップＳ６〜Ｓ１０を実行する。   Subsequently, the rebalancing cancel processing unit 16 determines whether any one of the rebalancing cancellation determination criterion (1), determination criterion (2), and determination criterion (3) is satisfied. Specifically, the following steps S6 to S10 are executed.

まず、リバランシングキャンセル処理部１６は、判定基準（１）を満たすか否かを判定する（ステップＳ６）。例えば、リバランシングキャンセル処理部１６は、リバランシング設計の計算後（リバランシング設計時間（Δｔ）経過後）における各ノード１の負荷が、許容範囲である、ノード平均負荷の±５％以内に収まっているか否かを判定する。
ここで、判定基準（１）を満たす場合には（ステップＳ６→Ｙｅｓ）、ステップＳ１１に進む。一方、判定基準（１）を満たさない場合には（ステップＳ６→Ｎｏ）、次のステップＳ７に進む。 First, the rebalancing cancellation processing unit 16 determines whether or not the determination criterion (1) is satisfied (step S6). For example, the rebalancing cancellation processing unit 16 has the load of each node 1 after the rebalancing design calculation (after the rebalancing design time (Δt) elapses) within an allowable range of ± 5% of the average node load. It is determined whether or not.
If the criterion (1) is satisfied (step S6 → Yes), the process proceeds to step S11. On the other hand, when the determination criterion (1) is not satisfied (step S6 → No), the process proceeds to the next step S7.

ステップＳ７において、リバランシングキャンセル処理部１６は、ステップＳ５において受信した各ノード１の負荷情報に基づき、リバランシング設計の計算後（リバランシング設計時間（Δｔ）経過後）における、ノード平均負荷を算出する。   In step S7, the rebalancing cancellation processing unit 16 calculates the node average load after the rebalancing design calculation (after the rebalancing design time (Δt) elapses) based on the load information of each node 1 received in step S5. To do.

続いて、リバランシングキャンセル処理部１６は、判定基準（２）を満たすか否かを判定する（ステップＳ８）。具体的には、リバランシングキャンセル処理部１６は、ノード平均負荷が、リバランシング設計の計算の前後で、所定の基準値（例えば、計算前のノード平均負荷の２０％）以上に減少しているか否かを判定する。
ここで、判定基準（２）を満たす場合には（ステップＳ８→Ｙｅｓ）、ステップＳ１１に進む。一方、判定基準（２）を満たさない場合には（ステップＳ８→Ｎｏ）、次のステップＳ９に進む。 Subsequently, the rebalancing cancellation processing unit 16 determines whether or not the determination criterion (2) is satisfied (step S8). Specifically, the rebalancing cancellation processing unit 16 determines whether the node average load has decreased to a predetermined reference value (for example, 20% of the node average load before calculation) or more before and after the rebalancing design calculation. Determine whether or not.
If the determination criterion (2) is satisfied (step S8 → Yes), the process proceeds to step S11. On the other hand, when the determination criterion (2) is not satisfied (step S8 → No), the process proceeds to the next step S9.

ステップＳ９において、リバランシングキャンセル処理部１６は、ステップＳ５において受信した各ノード１の負荷情報に基づき、その負荷の大きさを降順でソートした情報であるノード順位テーブル６００βを作成する。   In step S9, the rebalancing cancel processing unit 16 creates a node order table 600β which is information obtained by sorting the magnitudes of the loads in descending order based on the load information of each node 1 received in step S5.

次に、リバランシングキャンセル処理部１６は、判定基準（３）を満たすか否かを判定する（ステップＳ１０）。具体的には、リバランシングキャンセル処理部１６は、ステップＳ３において作成したノード順位テーブルαと、ステップＳ９において作成したノード順位テーブルβとを比較し、負荷が許容範囲外であるノード１のノード順位に変動があるか否かを判定する。
ここで、負荷が許容範囲外であるノード１のノード順位に変動がある場合には、判定基準（３）を満たすとして（ステップＳ１０→Ｙｅｓ）、ステップＳ１１に進む。一方、負荷が許容範囲外であるノード１のノード順位に変動がない場合には、判定基準（３）を満たさないとして（ステップＳ１０→Ｎｏ）、ステップＳ１２に進む。 Next, the rebalancing cancellation processing unit 16 determines whether or not the determination criterion (3) is satisfied (step S10). Specifically, the rebalancing cancellation processing unit 16 compares the node order table α created in step S3 with the node order table β created in step S9, and the node order of the node 1 whose load is outside the allowable range. It is determined whether or not there is a fluctuation.
Here, when there is a change in the node order of the node 1 whose load is outside the allowable range, the determination criterion (3) is satisfied (step S10 → Yes), and the process proceeds to step S11. On the other hand, when there is no change in the node order of the node 1 whose load is outside the allowable range, the determination criterion (3) is not satisfied (step S10 → No), and the process proceeds to step S12.

そして、リバランシングキャンセル処理部１６は、リバランシングキャンセルの判定基準（１）、判定基準（２）、判定基準（３）のうち、いずれか１つでも満たす場合には（ステップＳ６→Ｙｅｓ、ステップＳ８→Ｙｅｓ、ステップＳ１０→Ｙｅｓ）、リバランシングキャンセル指示情報をリバランシング部１５に出力し、これにより、リバランシング部１５は、設計したリバランシングの実行を中止する（ステップＳ１１）。そして、ステップＳ１に戻る。   Then, the rebalancing cancel processing unit 16 satisfies any one of the rebalancing cancellation determination criterion (1), determination criterion (2), and determination criterion (3) (step S6 → Yes, step (S8 → Yes, Step S10 → Yes), the rebalancing cancel instruction information is output to the rebalancing unit 15, whereby the rebalancing unit 15 stops executing the designed rebalancing (step S11). Then, the process returns to step S1.

一方、リバランシングキャンセル処理部１６は、リバランシングキャンセルの判定基準（１）、判定基準（２）、判定基準（３）のすべてについて満たさなかった場合には（ステップＳ１０→Ｎｏ）、ステップＳ１２に進み、リバランシング部１５が、設計したリバランシングを実行し、処理を終了する。   On the other hand, if the rebalancing cancellation processing unit 16 does not satisfy all of the determination criteria (1), the determination criterion (2), and the determination criterion (3) for rebalancing cancellation (step S10 → No), the rebalancing cancellation processing unit 16 proceeds to step S12. Then, the rebalancing unit 15 executes the designed rebalancing and ends the process.

以上説明したように、本実施形態に係るノード、リバランシングキャンセル方法、および、プログラムによれば、リバランシング設計時間の経過後に、再度各ノード１の負荷を計測し、リバランシングキャンセルの判定基準を満たした場合には、リバランシングを中止する。このように、時間経過の観点を含めてリバランシングの実行が適切か否かを判断することにより、不要なリバランシングを抑制することができる。   As described above, according to the node, the rebalancing cancellation method, and the program according to the present embodiment, after the rebalancing design time has elapsed, the load of each node 1 is measured again, and the rebalancing cancellation determination criterion is set. If satisfied, stop rebalancing. In this way, unnecessary rebalancing can be suppressed by determining whether or not rebalancing is appropriate, including the viewpoint of the passage of time.

１ ノード
２ クライアント
３ ロードバランサ
１０ 制御部
１１ ノード識別子管理部
１２ 振り分け部
１３ 信号処理部
１４ ノード負荷計測部
１５ リバランシング部
１６ リバランシングキャンセル処理部
２０ 入出力部
３０ 記憶部
１００ ノード識別子管理テーブル
２００ 振り分けＩＤテーブル
３００ データ
４００ ノード負荷計測情報
５００ システム負荷情報
６００α，６００β ノード順位テーブル（ノード順位情報）
１０００ 分散処理システム 1 node 2 client 3 load balancer 10 control unit 11 node identifier management unit 12 distribution unit 13 signal processing unit 14 node load measurement unit 15 rebalancing unit 16 rebalancing cancel processing unit 20 input / output unit 30 storage unit 100 node identifier management table 200 Distribution ID table 300 Data 400 Node load measurement information 500 System load information 600α, 600β Node order table (node order information)
1000 Distributed processing system

Claims (6)

クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、
自身のノードの負荷情報を計測するノード負荷計測部と、
自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、
リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、
前記判定基準（１）は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、
前記判定基準（２）は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、
前記判定基準（３）は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であり、
前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止すること
を特徴とするノード。 A node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster,
A node load measurement unit that measures load information of its own node;
The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design for changing the data distribution destination so that the load of the node falls within the allowable range, and a rebalancing unit that executes rebalancing based on the rebalancing design;
When the load information is obtained again from each of the nodes other than itself and after the rebalancing design time has elapsed and either of the predetermined criteria (1), (2), and (3) for rebalancing cancellation is satisfied, A rebalancing cancel processing unit that outputs rebalancing cancel instruction information for instructing to stop execution of rebalancing based on the rebalancing design, to the rebalancing unit,
The determination criterion (1) is that the load information of each node acquired after the elapse of the rebalancing design time is within the allowable range;
The determination criterion (2) is to calculate a node average load obtained by averaging the load information of each node, and the calculated node average load is reduced by a predetermined reference value or more before and after the rebalancing design.
The determination criterion (3) refers to the load information of each node, creates node rank information obtained by sorting the nodes based on the magnitude relation of the load before and after the rebalancing design calculation, and the load is the allowable value There is a variation in node rank information before and after the calculation in the rank of nodes that do not fit in the range,
The rebalancing unit stops the execution of the rebalancing when receiving the rebalancing cancel instruction information. クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、
自身のノードの負荷情報を計測するノード負荷計測部と、
自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、
リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、
前記判定基準は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、であり、
前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止すること
を特徴とするノード。 A node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster,
A node load measurement unit that measures load information of its own node;
The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design for changing the data distribution destination so that the load of the node falls within the allowable range, and a rebalancing unit that executes rebalancing based on the rebalancing design;
After the rebalancing design time elapses, load information is acquired again from itself and other nodes other than itself, and when the predetermined criteria for rebalancing cancellation are satisfied, rebalancing execution based on the rebalancing design is stopped. A rebalancing cancel processing unit that outputs rebalancing cancel instruction information to be instructed to the rebalancing unit,
The determination criterion is that load information of each node acquired after the rebalancing design time has elapsed is within the allowable range,
The rebalancing unit stops the execution of the rebalancing when receiving the rebalancing cancel instruction information. クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、
自身のノードの負荷情報を計測するノード負荷計測部と、
自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、
リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、
前記判定基準は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、であり、
前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止すること
を特徴とするノード。 A node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster,
A node load measurement unit that measures load information of its own node;
The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design for changing the data distribution destination so that the load of the node falls within the allowable range, and a rebalancing unit that executes rebalancing based on the rebalancing design;
After the rebalancing design time elapses, load information is acquired again from itself and other nodes other than itself, and when the predetermined criteria for rebalancing cancellation are satisfied, rebalancing execution based on the rebalancing design is stopped. A rebalancing cancel processing unit that outputs rebalancing cancel instruction information to be instructed to the rebalancing unit,
The determination criterion is to calculate a node average load obtained by averaging the load information of each node, and before and after the rebalancing design calculation, the calculated node average load is reduced by a predetermined reference value or more,
The rebalancing unit stops the execution of the rebalancing when receiving the rebalancing cancel instruction information. クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムの前記ノードであって、
自身のノードの負荷情報を計測するノード負荷計測部と、
自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行い、当該リバランシング設計に基づきリバランシングを実行するリバランシング部と、
リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準を満たす場合に、当該リバランシング設計に基づくリバランシングの実行の中止を指示するリバランシングキャンセル指示情報を前記リバランシング部に出力するリバランシングキャンセル処理部と、を備え、
前記判定基準は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であり、
前記リバランシング部は、前記リバランシングキャンセル指示情報を受け取ると、前記リバランシングの実行を中止すること
を特徴とするノード。 A node of a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster,
A node load measurement unit that measures load information of its own node;
The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, a rebalancing design for changing the data distribution destination so that the load of the node falls within the allowable range, and a rebalancing unit that executes rebalancing based on the rebalancing design;
After the rebalancing design time elapses, load information is acquired again from itself and other nodes other than itself, and when the predetermined criteria for rebalancing cancellation are satisfied, rebalancing execution based on the rebalancing design is stopped. A rebalancing cancel processing unit that outputs rebalancing cancel instruction information to be instructed to the rebalancing unit,
The determination criterion refers to the load information of each node, creates node order information obtained by sorting the nodes based on the magnitude relationship of the load before and after the rebalancing design calculation, and the load falls within the allowable range. There is a variation in node ranking information before and after the calculation in the ranking of no nodes,
The rebalancing unit stops the execution of the rebalancing when receiving the rebalancing cancel instruction information. クラスタを構成する複数のノードそれぞれに、データを振り分けて処理させる分散処理システムが有する前記ノードのリバランシングキャンセル方法であって、
前記ノードは、
自身のノードの負荷情報を計測するステップと、
自身および自身以外の他のノードそれぞれから前記負荷情報を取得し、前記取得した負荷情報のそれぞれが、所定の許容範囲に収まるか否かを判定し、前記許容範囲に収まらない負荷情報を計測したノードがある場合に、当該ノードの負荷を前記許容範囲に収まるように前記データの振り分け先を変更するリバランシング設計を行うステップと、
リバランシング設計時間の経過後に再度自身および自身以外の他のノードそれぞれから負荷情報を取得し、リバランシングキャンセルの所定の判定基準（１）（２）（３）のいずれかを満たす場合に、当該リバランシング設計に基づくリバランシングの実行を中止させるステップと、を実行し、
前記判定基準（１）は、前記リバランシング設計時間の経過後に取得した各ノードの負荷情報が前記許容範囲に収まっていること、
前記判定基準（２）は、各ノードの負荷情報を平均したノード平均負荷を算出し、前記リバランシング設計の計算前後において、前記算出したノード平均負荷が所定の基準値以上減少していること、
前記判定基準（３）は、各ノードの負荷情報を参照し、負荷の大小関係に基づいて各ノードをソートしたノード順位情報を、前記リバランシング設計の計算前後において作成し、前記負荷が前記許容範囲に収まらないノードの順位に、前記計算前後のノード順位情報において変動があること、であること
を特徴とするリバランシングキャンセル方法。 A rebalancing cancellation method for the nodes included in a distributed processing system that distributes and processes data to each of a plurality of nodes constituting a cluster,
The node is
Measuring the load information of its own node;
The load information is acquired from each of itself and other nodes other than itself, whether or not each of the acquired load information falls within a predetermined allowable range, and load information that does not fall within the allowable range is measured. When there is a node, performing a rebalancing design for changing a distribution destination of the data so that a load of the node falls within the allowable range; and
When the load information is obtained again from each of the nodes other than itself and after the rebalancing design time has elapsed and either of the predetermined criteria (1), (2), and (3) for rebalancing cancellation is satisfied, Executing a rebalancing operation based on the rebalancing design, and
The determination criterion (1) is that the load information of each node acquired after the elapse of the rebalancing design time is within the allowable range;
The determination criterion (2) is to calculate a node average load obtained by averaging the load information of each node, and the calculated node average load is reduced by a predetermined reference value or more before and after the rebalancing design.
The determination criterion (3) refers to the load information of each node, creates node rank information obtained by sorting the nodes based on the magnitude relation of the load before and after the rebalancing design calculation, and the load is the allowable value A rebalancing cancellation method characterized in that there is a change in node order information before and after the calculation in the order of nodes that do not fall within the range. 請求項５に記載のリバランシングキャンセル方法を、コンピュータに実行させるためのプログラム。   A program for causing a computer to execute the rebalancing cancellation method according to claim 5.
JP2015135527A 2015-07-06 2015-07-06 Node, rebalancing cancellation method, and program Expired - Fee Related JP6326011B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2015135527A JP6326011B2 (en) 2015-07-06 2015-07-06 Node, rebalancing cancellation method, and program

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2015135527A JP6326011B2 (en) 2015-07-06 2015-07-06 Node, rebalancing cancellation method, and program

Publications (2)

Publication Number Publication Date
JP2017016576A true JP2017016576A (en) 2017-01-19
JP6326011B2 JP6326011B2 (en) 2018-05-16

Family

ID=57828112

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2015135527A Expired - Fee Related JP6326011B2 (en) 2015-07-06 2015-07-06 Node, rebalancing cancellation method, and program

Country Status (1)

Country Link
JP (1) JP6326011B2 (en)

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000163288A (en) * 1998-11-30 2000-06-16 Nec Corp Data storage system, data relocation method and recording medium
JP2009237763A (en) * 2008-03-26 2009-10-15 Hitachi Ltd Server system and control method therefor
JP2012238084A (en) * 2011-05-10 2012-12-06 Nippon Telegr & Teleph Corp <Ntt> Data load distribution arrangement system and data load distribution arrangement method
JP2014041550A (en) * 2012-08-23 2014-03-06 Nippon Telegr & Teleph Corp <Ntt> Data migration processing system and data migration processing method
JP2014186624A (en) * 2013-03-25 2014-10-02 Kddi Corp Migration processing method and processing device

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000163288A (en) * 1998-11-30 2000-06-16 Nec Corp Data storage system, data relocation method and recording medium
JP2009237763A (en) * 2008-03-26 2009-10-15 Hitachi Ltd Server system and control method therefor
JP2012238084A (en) * 2011-05-10 2012-12-06 Nippon Telegr & Teleph Corp <Ntt> Data load distribution arrangement system and data load distribution arrangement method
JP2014041550A (en) * 2012-08-23 2014-03-06 Nippon Telegr & Teleph Corp <Ntt> Data migration processing system and data migration processing method
JP2014186624A (en) * 2013-03-25 2014-10-02 Kddi Corp Migration processing method and processing device

Also Published As

Publication number Publication date
JP6326011B2 (en) 2018-05-16

Similar Documents

Publication Publication Date Title
US20220329651A1 (en) Apparatus for container orchestration in geographically distributed multi-cloud environment and method using the same
JP5664098B2 (en) Composite event distribution apparatus, composite event distribution method, and composite event distribution program
CN107548549B (en) Resource balancing in a distributed computing environment
WO2018076791A1 (en) Resource load balancing control method and cluster scheduler
JP6881575B2 (en) Resource allocation systems, management equipment, methods and programs
US8713125B2 (en) Method and system for scaling usage of a social based application on an online social network
CN101984632A (en) Load distributing method, device and server in distributed cache system
KR20170029263A (en) Apparatus and method for load balancing
JP5531278B2 (en) Server configuration management system
Klems et al. The yahoo! cloud datastore load balancer
JP6116102B2 (en) Cluster system and load balancing method
Sousa et al. Predictive elastic replication for multi‐tenant databases in the cloud
JP5969315B2 (en) Data migration processing system and data migration processing method
US11652892B2 (en) Automatic connection load balancing between instances of a cluster
JP6059558B2 (en) Load balancing judgment system
Tiwari et al. Analysis of public cloud load balancing using partitioning method and game theory
JP6326011B2 (en) Node, rebalancing cancellation method, and program
JP6098167B2 (en) Virtual machine management program and method thereof
JP5723330B2 (en) Distributed processing system and distributed processing method
JP5997659B2 (en) Distributed processing system and distributed processing method
JP2017146848A (en) Rebalancing device, rebalancing method, and program
Oral et al. Supporting performance isolation in software as a service systems with rich clients
JP6259408B2 (en) Distributed processing system
JP6325995B2 (en) Distributed system, load balancing method and program
JP5711771B2 (en) Node leave processing system

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20170630

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20180328

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20180410

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20180413

R150 Certificate of patent or registration of utility model

Ref document number: 6326011

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

LAPS Cancellation because of no payment of annual fees