JP6433926B2 - Rebalancing device, rebalancing method, and program - Google Patents

Description

  The present invention relates to a technique for correcting a load imbalance among a plurality of nodes in a distributed system.

  In recent years, with the rise of cloud computing, it has been required to efficiently process and hold 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 for each server (hereinafter also referred to as a node) that configures a cluster and constructs a distributed system. At this time, in order to increase the data processing capacity of the entire distributed system, the number of data handled by each node is preferably averaged.

  By the way, as a representative data management method, a remainder obtained by dividing a value obtained by multiplying the key (key) of each data by a hash function (hereinafter also referred to as hash (key): hash key) by the number of nodes N, that is, hash. There is a method in which a node having (key) mod N as a number manages data. At this time, however, numbers from 0 to N-1 are assigned to the nodes in advance. When such a management method is used, when a node is added or removed, the value of N changes, and the node in charge is changed for a lot of data, so that the node in charge needs to be rearranged.

  Therefore, there is a data management method using a consistent hash [Consistent Hashing] (Non-patent Document 1) as a method of suppressing the number of data that the node in charge changes with the addition / detachment of the node to about 1 / N. , Amazon Dynamo, etc. (Non-Patent Document 2). In the data management method using the consistent hash method, for example, in the circular ID space indicated by reference numeral 5 in FIG. 15, the loads indicated by the nodes A, B, C, D, and E, and the marks indicated by ◯ and ● are different. An ID (identification) is assigned to both data and data. The ID space 5 is traced clockwise from the ID of the data, and the first node encountered becomes the responsible node for the data. As an example of how IDs are given to the nodes A to E, a value obtained by applying an IP (Internet Protocol) address to a hash function {this is also referred to as a hash (IP address)} can be given.

  In a distributed system having a cluster configuration, for example, when the performance of each node is equal, the amount of data handled by each node A to E is equal, that is, the distance between nodes in the ID space 5 of the consistent hash method (hereinafter, It is desirable that the nodes are in charge of each other.

  In order to solve this point, a method of virtually giving a plurality of IDs to each of the nodes A to E is used (Non-Patent Document 3). Since each node A to E has a plurality of virtual IDs, even if the assigned area for each virtual ID is different, the assigned areas of the nodes A to E are averaged according to the law of large numbers. Conventional techniques such as the consistent hash method and virtual ID make it possible to equalize the number of data handled between nodes and distribute the load.

  However, since data with a high access frequency and data with a long processing time (high load data) are unevenly generated at specific nodes among the nodes A to E, the number of data handled by the nodes A to E itself Even if they are equal, load imbalance occurs between nodes.

  As a countermeasure against such a load increase in the distributed system of the consistent hash method, for example, a new node F shown in FIG. 15 is added to the distributed system, and the distributed system is scaled out. High load node), for example, a method of reducing the load by reducing the number of data handled by the high load node C.

  In addition, there is a case where the current number of nodes can be dealt with without additional installation if the load is distributed appropriately by changing the spatial arrangement on the consistent hash of the node (this is called rebalancing). . Non-Patent Document 4 identifies the situation to be dealt with by scale-out / rebalance, and in the situation to be dealt with by rebalance, between adjacent nodes on the consistent hash space (ID space 5) (for example, In the case of E, a method has been proposed in which rebalancing is performed in the adjacent A or D) indicated by two arrows to correct the load imbalance between nodes. In addition to the non-patent document 4, various techniques for rebalancing have been studied.

David Karger (Author), "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" Giuseppe DeCandia (Author), "Dynamo: Amazon's Highly Available Key-value Store" Michio Irie et al., "Load Balancing Method Aware of Data Replication in the Consistent Hash Method", IEICE Technical Report, IEICE Technical Report, IN2010-77 (2010-10) Y. Tsuruta et al., “Node Load Balancing Optimization Method in Distributed Server System”, Proceedings of the IEICE General Conference, Mar. 2014, B-7-84

  Since the existing rebalancing method does not consider the passage of time, there is a problem that depending on the time for calculation for rebalancing design, the rebalancing is executed even though the actual load is an appropriate value. is there.

  For example, in the ID space shown in FIG. 16A, the load on the node B (the load in the area in charge of B and B ′ in FIG. 16) and the load on the node E (the load in the area in charge of E and E ′ in FIG. 16). ) Is outside the allowable range. Therefore, it is determined to perform rebalancing.

  Then, assume that the state shown in FIG. 16B is reached after the time (Δt) related to the calculation for the rebalance design has elapsed from the state shown in FIG. The state shown in FIG. 16B indicates that the load at node E (E ′) having a high load has decreased and the load at node B having a low load has increased. Thereby, the load imbalance is within an allowable range.

  However, in the prior art, if it is decided to perform rebalancing at the time of FIG. 16A, the rebalancing is executed regardless of whether or not the state shown in FIG. Therefore, for example, since the rebalance is executed from the state shown in FIG. 16B, an unbalance may occur and the rebalance must be executed again.

  The present invention has been made in view of the above points. In a technique for performing rebalancing to correct a load imbalance among a plurality of nodes in a distributed system, the rebalancing is performed based on the load state with time. It is an object of the present invention to provide a technique that makes it possible to determine whether or not to execute the above.

According to an embodiment of the present invention, there is provided a rebalancing apparatus used in a distributed system having a plurality of nodes to which information from a plurality of client machines using a communication service is distributed via a network,
Rebalancing processing means for determining whether or not rebalancing is necessary to suppress the uneven load amount between the plurality of nodes based on the load amounts of the plurality of nodes;
When the rebalancing processing unit determines that rebalancing is necessary, based on the predicted load state of the plurality of nodes after the rebalancing, canceling whether to cancel the rebalancing or not Processing means ,
The cancellation processing means
At a first time point when the rebalance processing unit determines that rebalancing is necessary, a difference from an average value of load amounts of the plurality of nodes at the first time point is calculated for each node, By subtracting the difference from the load amount of the node at the second time point for each node at the second time point when the time required for the rebalance design by the rebalance processing unit has elapsed from the time point 1, the prediction is performed. A rebalancing device is provided that calculates a load state .

In addition, according to the embodiment of the present invention, the rebalancing method executed by the rebalancing apparatus used in the distributed system having a plurality of nodes to which information from a plurality of client machines using the communication service is distributed via the network Because
A rebalance determination step for determining whether or not rebalancing is required to suppress the uneven load amount between the plurality of nodes based on the load amounts of the plurality of nodes;
Cancellation for determining whether or not to cancel the rebalancing based on the predicted load state of the plurality of nodes after the rebalancing when the rebalancing determination step determines that rebalancing is necessary A determination step ,
In the cancellation determination step, the rebalance device
At a first time point when rebalancing is determined by the rebalance determining step, a difference from an average value of load amounts of the plurality of nodes at the first time point is calculated for each node, The predicted load state is calculated by subtracting the difference from the load amount of the node at the second time point for each node at the second time point when the time required for rebalance design has elapsed from the time point 1. A rebalancing method is provided.

  According to an embodiment of the present invention, in a technique for rebalancing to correct a load imbalance among a plurality of nodes in a distributed system, whether or not rebalancing can be performed is determined based on a load state over time. Techniques are provided that enable this to be done.

1 is a block diagram illustrating a configuration of a distributed system according to a first embodiment of the present invention. The configuration of the node in the distributed system of this embodiment is shown, (a) is a block diagram showing the configuration of the control unit, (b) is a block diagram showing the information in the storage unit. It is a figure which shows the hash space divided | segmented by several nodes AE. (A) A figure showing an example of a node identifier management table, (b) A figure showing an example of a distribution ID table. (A) A diagram showing an example of node load measurement data (node unit), (b) a diagram showing an example of node load measurement data (virtual node unit), and (c) an example of node load measurement data (data unit). FIG. It is a figure which shows an example of distributed system load total data. (A) The figure which shows an example of the distribution ID table before rebalance, (b) The figure which shows an example of the distribution ID table after rebalance, (c) The other example of the distribution ID table after rebalance is shown FIG. (A) A figure showing an example of a distribution ID table before rebalancing, (b) A figure showing an example of a distribution ID table after rebalancing. It is a figure for demonstrating operation | movement of a rebalancing cancellation function part. It is a figure for demonstrating operation | movement of a rebalancing cancellation function part. It is a figure for demonstrating the effect of operation | movement of a rebalancing cancellation function part. It is a flowchart for demonstrating the operation | movement at the time of performing the rebalance of each node of the distributed system of this embodiment. It is a flowchart for demonstrating the operation | movement at the time of performing the rebalance of each node of the distributed system of this embodiment. It is a flowchart for demonstrating operation | movement of a rebalancing cancellation function part. It is a figure which shows the hash space for demonstrating a prior art. It is a figure for demonstrating a subject.

  Hereinafter, an embodiment (this embodiment) of the present invention will be described with reference to the drawings. The embodiment described below is only an example, and the embodiment to which the present invention is applied is not limited to the following embodiment.

  For example, in the example described below, the nodes constituting the cluster themselves perform rebalancing necessity determination, rebalancing design, and rebalancing cancellation determination. However, rebalancing necessity determination, rebalancing design and execution are performed. The rebalancing cancellation determination may be executed by a device other than the nodes constituting the cluster. In this case, the device collects load information of each node and performs rebalancing necessity determination, rebalancing design, rebalancing cancellation determination, distribution ID table distribution, and the like.

  In addition, when the main body that performs the rebalancing process / rebalancing cancellation determination process is the node itself or an apparatus other than the node, the main body can be referred to as a rebalancing apparatus.

  The rebalancing method described below is an example. The rebalancing cancellation determination method according to the present invention is not limited to the rebalancing method described below, but can be applied to other rebalancing methods (eg, Non-Patent Document 4).

  However, the rebalancing method described below is not limited to changing the spatial arrangement between adjacent nodes as in Non-Patent Document 4, and is an excellent rebalancing method that can efficiently correct the load imbalance.

(Overall system configuration, node configuration)
FIG. 1 is a block diagram illustrating a configuration example of a distributed system according to the present embodiment.

  A distributed system 10 shown in FIG. 1 is a system that performs data management using a plurality of nodes 15 using a consistent hash method. In the distributed system 10, when a load bias occurs between the nodes 15 constituting the distributed system 10, the load balance of the current node 15 is efficiently rebalanced to correct the load bias. . However, if it is determined that rebalancing is necessary, it is determined whether or not rebalancing is to be executed (whether or not to cancel) based on the load state after a predetermined time has elapsed. To do.

  The distributed system 10 includes a load balancer 13 connected to a plurality of client machines (also simply referred to as clients) 11 via a network 12 such as the Internet, and a plurality of nodes 15 constituting a cluster 14. Yes.

  Each node 15 is a physical device such as a computer or a logical device such as a virtual machine, in other words, a physical or virtual server. A message from the client 11 is distributed to each node 15 by the load balancer 13. This distribution is performed by a simple round robin method or the like.

  The node 15 includes a control unit 18 and a storage unit 19. However, the control part 18 and the memory | storage part 19 are implement | achieved when software (program) is run by the said apparatus (computer). The program may be distributed via a network, or may be stored and distributed in a storage medium such as a memory. Note that the control unit 18 and the storage unit 19 may each be configured by hardware (for example, an integrated circuit incorporating processing logic).

  As shown in FIG. 2A, the control unit 18 includes a node identifier management unit 18a, a distribution unit 18b, a signal processing unit 18c, a node load measurement unit 18d, a distributed system load rebalancing unit (simply, 18e and a rebalancing cancel function unit 18f.

  As shown in FIG. 2B, the storage unit 19 includes a node identifier management table 19a, a distribution ID table 19b, data 19c, node load measurement data 19d, distributed system load summary data 19e, and call control. A state flag 19f, a node-by-node load difference table / node-by-node predicted load comparison table 19g, and previous measurement data 19h are stored. The node identifier management table 19a is also called a management table 19a, the distributed system load summary data 19e is also called summary data 19e, and the call control status flag 19f is also called flag 19f.

  The distribution unit 18b distributes the message (information) from the client 11 to the node 15 in charge of the message based on, for example, a consistent hash method.

  The signal processing unit 18 c performs predetermined signal processing in response to a message from the client 11 and provides a service to the client 11. That is, the node 15 in charge of the message provides a service to the client 11 by performing predetermined signal processing in the signal processing unit 18c. The processing operations of the distribution unit 18b and the signal processing unit 18c will be described in detail later.

  However, in the distributed system 10, the load balancer 13 does not exist, and a message can be transmitted from the client 11 to an arbitrary node 15 (distribution unit 18b). Further, the allocating unit 18b and the signal processing unit 18c may be simultaneously present on the same node 15 as illustrated in FIG.

  In the control unit 18, the node identifier management unit 18a (or rebalancing unit 18e) manages the ID space handled by each node 15 by accumulating node information on the distributed system 10 in the node identifier management table 19a. This ID space is a space (hash space) on the consistent hash in the consistent hash method.

  For example, as shown in FIG. 3, the hash space is divided by a plurality of nodes A to E, and assigned areas of the nodes A to E are determined and managed. At this time, the hash space handled by the node A is an area from the node E to the node A in the clockwise direction, and the responsible node A holds (or processes) data existing in the hash space. The same applies to the other nodes B to E. In addition, as the size of the hash space (area in charge) is larger, more data can be held (processed).

  Returning to FIG. 2A, the distribution unit 18b performs processing related to determination of a distribution destination of data such as a message based on the distribution ID table 19b.

  The signal processing unit 18 c performs signal processing at the node 15. Data 19c to be accessed at the time of this signal processing is stored in the storage unit 19.

  The node load measurement unit 18d measures the load of the node 15 and records the measurement result as the node load measurement data 19d in the storage unit 19, and the privileged node 15 (for example, the node shown in FIG. 3) determined as necessary. Send to B).

  The distributed system load rebalancing unit 18e calculates the average value and standard deviation of the load based on the node load of the entire distributed system 10, and stores the distributed system load aggregate data 19e as the calculation result in the storage unit 19. Remember. Further, the rebalancing unit 18e performs the rebalancing necessity determination and the rebalancing design based on the stored total data 19e, and the rebalancing cancellation function unit 18f determines that the rebalancing is not canceled. If so, perform a rebalance. The rebalancing cancel function unit 18f will be described later.

  The call control state flag 19f stored in the storage unit 19 is information for determining whether or not the state is a state for controlling a new call.

(About processing in the distribution unit 18b and the signal processing unit 18c)
Here, message distribution processing and signal processing by the distribution unit 18b and the signal processing unit 18c of the node 15 shown in FIG. 2 will be described in more detail.

  The distribution unit 18b identifies the node 15 in charge of signal processing based on the information in the message called from the client 11, and distributes the message to the node 15. The message is divided into a new call (for example, Initial-INVITE or the like in SIP (Session Initiation Protocol)) and a subsequent call (for example, BYE in SIP).

  Whether the call is a new call or a subsequent call can be determined based on whether or not a distribution key described later is embedded in the call message. For example, in SIP, it can be determined by Tag of To / From header or the like.

  The distribution key is configured by “data identifier (call-id in SIP) + hash value”. The hash value is a value derived from the data identifier by applying a hash function.

  On the other hand, in the case of a subsequent call as a result of the above-described determination of whether the call is a new call or a subsequent call, the distribution unit 18b allocates a distribution ID space that is an assigned region for each node 15 on the distribution ID table 19b { 4 (b) and will be described later} is compared with the hash value in the distribution key to identify the node 15 in charge. Further, the address of the node 15 in charge is specified from the node identifier management table 19a shown in FIG. 4A described later, and transferred to the specified node 15.

  On the other hand, as a result of the determination described above, since a distribution key does not exist in the case of a new call, a Call-id (data identifier) is extracted from the message and introduced into a hash function to derive a hash value. Further, the distribution unit 18b compares the distribution ID space {shown in FIG. 4B and described later}, which is the assigned area for each node 15 on the distribution ID table 19b, with the derived hash value. The node 15 in charge is specified. Further, the address of the node 15 in charge is specified from the node identifier management table 19a shown in FIG. 4A described later, and transferred to the specified node 15.

  Even when a new call is received by the signal processing unit 18c, a Call-id (data identifier) is extracted from the message, and this is introduced into a hash function to derive a hash value, thereby generating a distribution key. Further, after the signal processing by the signal processing unit 18c, a distribution key is embedded in a message to be sent to the client 11 (UAC, UAS, etc. in SIP) (To / From header Tag in SIP) and sent.

  Thereafter, a message is sent after embedding the real distribution key in the subsequent call from the client 11, and the distribution unit 18b distributes the call based on the hash value of the main distribution key. Subsequent calls can reach the processed node 15.

(About the node identifier management unit 18a)
Next, the node identifier management unit 18a described above will be described in more detail.

  The node identifier management unit 18a updates the identifier information (node identifier) of the node 15 constituting the distributed system 10 when the node 15 is added to or removed from the distributed system 10, and this is updated as shown in FIG. The node identifier management table 19a shown in FIG. In the example of FIG. 4A, an address (for example, “10.45.0.1”) is associated with a node identifier (or node ID) (for example, “Node 1”). The node identifier is assigned by the node identifier management unit 18a of the privileged node and distributed to all the nodes 15.

  In the consistent hash method, the virtual node identifier (or virtual node ID) shown in FIG. 4B is subordinate to the node identifier. This virtual node ID is an arbitrary ID (by hash value) in the distribution ID space. For example, the node identifier “Node1” shown in FIG. 4A is subordinate to at least one or more virtual node IDs “Node1-1” and “Node1-2” shown in the distribution ID table 19b of FIG. 4B. doing. In other words, one or more virtual nodes are subordinate to the node 15. However, this is a basic configuration, and the virtual node may not be subordinate to the node 15 in some cases.

  Thus, in conjunction with the update of the node identifier management table 19a described above, the assigned area of the distribution ID space handled by the node 15 is updated and managed as the distribution ID table 19b. In the distribution ID table 19b, for example, the virtual node ID “Node1-1” is associated with the data size of “0 to 199 (D = 200)” as the assigned area of the assigned ID space, and the virtual node The data size of “600 to 999 (D = 400)” is associated with the ID “Node1-2” as the assigned area of the assigned ID space. That is, D = 200 indicates that the data size of the assigned area is 200. The same applies to other D = 400 and the like.

(Regarding the processing of the node load measuring unit 18d)
Next, information collection of the load measured by the node load measurement unit 18d described above and sending of the collected load to the privileged node will be described.

  The node load measurement unit 18d measures the load on the node 15 at a predetermined cycle, and records and accumulates the load on the storage unit 19 as node load measurement data 19d. Further, the node load measurement unit 18d sends the node load measurement data 19d accumulated in the privileged node (for example, the node B shown in FIG. 3) at a predetermined cycle.

  Further, the privileged node distributes the load data of all nodes collected from each node 15 to all the nodes 15. Each node 15 can record this load data in the storage unit 19 as node load measurement data 19d.

  As the load of the node 15 measured at a predetermined period in the node load measuring unit 18d described above, all parameters that can be acquired by the node 15 such as a CPU (Central Processing Unit) usage rate, a memory usage rate, and an access frequency are used. be able to. Also, which numerical value is the bottleneck, and what value is the threshold to be rebalanced depends on the system characteristics of the distributed system, and there are cases where it is determined by a combination of multiple parameters. is there. Therefore, it can be used without being limited to a specific parameter type.

  Further, the unit of load measurement by the node load measuring unit 18d is measured in any one of (a) node unit by node ID, (b) virtual node ID unit by virtual node ID, and (c) data unit in FIG. It doesn't matter. In addition, when the load is measured in the virtual node unit of FIG. 5B, it is possible to calculate the node unit of (a) by summing up the load, and when measuring the load in the data unit of (c), It is possible to calculate the load in units of virtual nodes in (b) and in units of nodes in (a) by summing up. In FIG. 5, the load measured by the node load measuring unit 18 d shows an access frequency (number of accesses) as an example.

  Such tables in FIGS. 5A to 5C are for the distributed system 10 including two nodes 15 and have the following configuration.

  In one node 15 (for example, node ID = Node1) shown in FIG. 5A, two virtual nodes with two virtual node IDs (Node1_1, Node1_2) shown in FIG. 5B are held. Furthermore, it is assumed that two data (data1, data2) per virtual node with one virtual node ID (for example, Node1_1) shown in FIG. The same applies to the other nodes.

  In this case, the load measurement unit is a virtual node unit as shown in FIG. 5B, and the access frequency (number of times) as a load to be collected is a 10 second period (10: 15: 00 → 10: 15: 10). → 10:15:20) The case of collecting and accumulating is assumed.

(Regarding rebalancing determination processing by the distributed system load rebalancing unit 18e)
Next, a description will be given of the process of calculating the load deviation of the node 15 and the rebalancing necessity determination by the distributed system load rebalancing unit 18e. Any node 15 may perform the rebalancing necessity determination, rebalancing design, and execution (distribution ID table distribution) processing in the distributed system load rebalancing unit 18e described below. Assumes to do.

  Based on the node load data (node load measurement data 19d) collected from each node 15 at a predetermined period, the rebalance unit 18e loads the average value, standard deviation, deviation, and deviation / The standard deviation (value obtained by dividing the deviation by the standard deviation) is calculated. Further, the rebalance unit 18e records the calculation results as aggregated data 19e as shown in FIG. 6, and based on the recorded aggregated data 19e, the following three conditions (1) to (3) are recorded. If any one of the above is satisfied, it is determined that rebalancing is necessary to correct the load imbalance among the nodes 15. If neither is satisfied, it is determined that rebalancing is unnecessary.

  The total data 19e shown in FIG. 6 includes a collection time, a node ID (node identifier), an average value (access frequency), a standard deviation, an actual measurement value (access frequency), a deviation (difference from the average value), and a deviation. / Standard deviation is recorded. The average value and the actual measurement value are the average value and the actual measurement value of the access frequency.

  Condition (1), the rebalance unit 18e, based on the total data 19e, whether or not the load on any of the nodes 15 exceeds the upper limit value (predetermined upper limit value) that the node 15 allows. If there is a node exceeding the upper limit value, it is determined that rebalancing is necessary.

  Condition (2), the rebalance unit 18e checks whether or not the standard deviation of the load of the entire node 15 is equal to or less than a predetermined threshold (first threshold) based on the total data 19e, and exceeds the threshold Therefore, it is determined that rebalancing is necessary.

  Condition (3), the rebalance unit 18e checks whether or not the load deviation / standard deviation for each node 15 is equal to or less than a predetermined threshold (second threshold) based on the aggregated data 19e. When there is a node 15 that is present, it is determined that rebalancing is necessary.

  However, in the aggregated data 19e shown in FIG. 6, the load measurement unit is the node unit shown in FIG. 5A (there may be a virtual node unit), and the load average value and the actual measurement value are the access frequency. Furthermore, the time interval for calculating the average value and the standard deviation is set to 20 seconds (for example, 10:14:40 to 10:15:00). The example of FIG. 6 is the calculated value and the like at the time of 10:15:00. In addition, the upper limit value of the load allowed by each node 15 is set as the upper limit value for the actually measured access frequency, which is “90” {condition (1)}, and the standard deviation threshold is “15” {condition (2). }, This is an example when the deviation / standard deviation threshold (also referred to as the deviation threshold) is “1.2” {condition (3)}. Note that the time interval for calculating the average value and the standard deviation may be a time interval for determining the necessity of rebalancing.

  In this example, the conditions (1) and (2) are not satisfied. However, in FIG. 6, the deviation / standard deviation of the node identifiers “Node 1”, “Node 3”, and “Node 4” is “1.5”, which exceeds the threshold value “1.2” and satisfies the condition (3) Therefore, it is determined that rebalancing is necessary. However, if the rebalancing cancel function unit 18f described later determines that the rebalancing is canceled, the rebalancing at this timing is not executed.

(Rebalancing design and execution processing by the distributed system load rebalancing unit 18e)
Here, the rebalancing design and execution processing executed by the rebalancing unit 18e when the rebalancing is not canceled by the rebalancing cancellation function unit 18f will be described.

  The rebalance corrects the load bias by transferring a transfer area (described later) in the assigned area (responsible ID space) of the node 15 having a high load to the node 15 having a low load. At this time, in order to correct the load divergence, the size of the necessary transfer area of the assigned area is estimated, and only the transfer area is transferred. However, the transfer area may be all of the assigned areas or an area with a ratio of less than 100% of the assigned areas.

  In the present embodiment, this transfer method is as follows (T1) to (T4).

  (T1) It is assumed that the transfer area in the assigned area of the node 15 having the highest load among all the nodes 15 is transferred to the lowest node 15.

  (T2) The transfer of the transfer area ends in the following case. That is, when all of the deviations that cause any of the above conditions (1) to (3) no longer exist (T2-1), or a part of the deviation (previously designated deviation cancellation ratio) The process ends when the transfer of the transfer area that resolves (deviation satisfying) is determined (T2-2), or when there is no transfer destination node 15 that can transfer the transfer area (T2-3). And

  (T3) The transfer unit of the transfer area may be a node unit or a virtual node unit, not a virtual node unit, but a unit for transferring half of the area in charge of the virtual node, or a transfer unit of only data using one hash value I do not care.

  (T4) The rebalancing design executed in advance when the rebalancing unit 18e performs rebalancing determines in which unit the load measurement unit is executed from among the node unit, the virtual node unit, and the data unit described above. The granularity of possible rebalance designs varies as described below.

  That is, in the case of load measurement in node units, the method is only used when the rebalance granularity described later is coarse.

  In the case of load measurement in units of virtual nodes, it is possible to use a method in which the rebalance granularity described later is coarse and the rebalance granularity is intermediate (intermediate between coarse and fine).

  In the case of load measurement in units of data, all three methods can be employed when the rebalance granularity described later is coarse, intermediate, and fine.

  First, the case where the rebalance particle size is coarse will be described.

  An average load amount “Lv_ave” per virtual node obtained by dividing the total load amount of the entire node 15 by the number of virtual node IDs of all the nodes 15 is calculated. Next, paying attention to the node 15 with the highest load among the nodes 15, calculate the deviation of the load amount to be eliminated for this node 15 (because the sign of this deviation is +, it is also called a plus deviation) “Ltarget” To do. This deviation is, for example, the positive deviation (difference from the average value of the actual measurement values) shown in FIG.

  Next, a value obtained by dividing “Ltarget” by “Lv_ave” is considered as the number of virtual node IDs “Vtarget_num” necessary for eliminating the load to be eliminated.

  The virtual node ID of “Vtarget_num” is randomly extracted from the virtual nodes of the node 15 having the highest load. At this time, when “Vtarget_num” includes a decimal number, as described in the outline in (T3) above, the area in charge of the virtual node having a predetermined virtual node ID may be assigned based on the decimal number, for example. For example, in the case of “1.5”, the assigned area of one virtual node is assigned and the assigned area of the second virtual node is divided in half. Further, an integer number of virtual node IDs may be extracted by rounding down, rounding up, or rounding off the decimal part.

  As described above, when the transfer area in the assigned area of the virtual node with the virtual node ID “Vtarget_num” extracted at random is transferred, the transfer is performed in order from the node 15 having the lowest load among all the nodes 15. I will do it. At this time, it is necessary to determine an allowable transfer size of the assigned area so that the load on the transfer destination node 15 does not increase too much due to the transfer.

  Specifically, the node 15 as the transfer destination can accept the load amount deviation (the sign of the deviation is −, so it is also referred to as a minus deviation). For this reason, the number of virtual node IDs “Vget_num1” required to eliminate the load amount, which is a value obtained by dividing the minus deviation of the load amount by the average load amount “Lv_ave”, is the allowable number of virtual node IDs.

  Here, when the assigned area of the transfer destination node 15 exceeds the allowable amount, an allowable virtual node ID number “Vget_num2” is obtained for the node 15 having the next lowest load in the same procedure, and Vtarget_num <Vget_num1 + Vget_num2 + When the transfer of the transfer area in all the necessary assigned areas is completed, the process ends.

  Thereafter, the same processing is executed for the next highest load node, and the transfer of the transfer area in the assigned area that corrects the load divergence is completed in all the nodes 15 that need to eliminate the load divergence. Or, it is executed until there is no node that can be transferred to the transfer area.

  Next, a case where the rebalance granularity is intermediate will be described.

  Since it is basically the same as the case where the rebalance granularity described above is coarse, only the difference from the coarse case will be described.

  As described above, instead of randomly extracting virtual nodes from the virtual nodes of the transfer source node 15, the virtual nodes that cause a positive deviation of the load amount to be eliminated are selectively extracted. It is assumed that the transfer area in the area in charge of the extracted virtual node is transferred. In this case, since the load amount is measured in units of virtual nodes, the measured load is higher than when the granularity is coarse, but the transfer area can be transferred more accurately to correct the load divergence. It becomes.

  Next, the case where the rebalance granularity is fine will be described.

  Since it is basically the same as the case where the rebalance granularity described above is coarse, only the difference from the coarse case will be described.

  As described above, instead of randomly extracting virtual nodes from the virtual nodes of the transfer source node 15, a hash value of data that causes a plus deviation of the load to be eliminated is selectively extracted. Only the hash value is transferred. In this case, the load is measured in units of data, so the measured load is higher than when the rebalance granularity is intermediate, but the transfer of the transfer area to correct the load divergence should be performed more accurately. Is possible. Also, the unit of transfer can be minimized.

  When it is determined that rebalancing is necessary, the rebalancing unit 18e executes the rebalancing design for correcting the load bias in the above-described procedure, and reflects the rebalancing design in the distribution ID table 19b. However, the transmission to all the nodes 15 in the distribution ID table 19b is executed when the rebalance is not canceled.

  For example, as shown in FIG. 7A, the distribution ID table 19b before rebalancing is assigned to the virtual node ID “Node1-1” as “0-199 (D = 200) ”,“ Node 2-1 ”is“ 200 to 399 (D = 200) ”,“ Node 3-1 ”is“ 400 to 599 (D = 200) ”, and“ Node 1-2 ”. Are associated with a data size of “600 to 999 (D = 400)”.

  Here, for example, all the assigned areas “600 to 999 (D = 400)” of the virtual node “Node 1-2” illustrated in FIG. 7A are transferred to the virtual node having the other virtual node ID “Node3_2”. And In this case, as shown in FIG. 7B, the area in charge of the virtual node with the virtual node ID “Node3_2” has a size of “600 to 999 (D = 400)”.

  Also, half of the assigned area “600 to 999 (D = 400)” of the virtual node “Node 1-2” illustrated in FIG. 7A is transferred to the virtual node having the other virtual node ID “Node3_2”. To do. In this case, as shown in FIG. 7C, the virtual node with the virtual node ID “Node1_2” has a size of “600 to 799 (D = 200)”, and the virtual node with the virtual node ID “Node3_2” The area in charge is “800 to 999 (D = 200)”.

<Other examples of rebalancing design>
The rebalance unit 18e may perform rebalance design by the process described below.

  Here, although the total amount of resources (total load) of each node 15 of the distributed system 10 is sufficient with respect to the used resource amount (used load amount), the used resource amount is biased. To do. At this time, the rebalancing unit 18e does not specify the target node to which the transfer area in the assigned area is transferred as in the above-described process, or the virtual node of each node 15 without specifying the appropriate transfer size of the corresponding node 15. The number is rebalanced according to the current load status of each node 15 to the number of virtual nodes that is required for each node 15.

  At this time, the rebalancing unit 18e calculates the number of virtual nodes of each node 15 according to the following equation (1) according to the load condition, and rebalances based on the calculated number of virtual nodes of each node 15.

  In this rebalancing, the virtual node ID and the distribution ID space are remapped from the top of the distribution ID space of each virtual node based on the calculated number of virtual nodes. In the remapping, the total extension (total size) of the assigned area is divided by the calculated number of virtual nodes to obtain a distribution ID space size per virtual node, and a new distribution ID space size from the top of the distribution ID space. Each time, the number of virtual nodes for each virtual node ID is reset.

Number of virtual nodes after rebalancing = current number of virtual nodes × (average value of loads of all nodes / actual value of loads of relevant nodes) (Equation 1)
However, the “actually measured load value of the corresponding node” in the equation (1) is an actually measured value of the load of the node having the current virtual node. In addition, Expression (1) is held in a storage unit (not shown) of the rebalance unit 18e.

  Hereinafter, the rebalancing process here will be specifically described.

  First, the rebalancing unit 18e resets the number of virtual nodes that each node 15 has. The resetting process will be described with reference to FIGS. 8 (a) and 8 (b). However, the virtual node IDs “Node 1-1” and “Node 1-2” illustrated in FIGS. 8A and 8B are assigned to the virtual nodes 1-1 and 1-2 subordinate to the node 1 having the node ID “Node 1”. It shall correspond. The same applies to other virtual node IDs. For example, the virtual node IDs “Node5-1”, “Node5-2”, and “Node5-3” are virtual nodes 5 to 5 subordinate to the node 5 of the node ID “Node5”. It shall correspond to 1,5-2,5-3.

  In the distribution ID table 19b shown in FIG. 8A, the virtual node ID “Node1-1” corresponds to the data size “0 to 199 (D = 200)” as the assigned area of the assigned ID space. A data size of “200 to 399 (D = 200)” is associated with “Node 1-2”. The same applies to other virtual node IDs.

  Further, the number of virtual nodes of each of the nodes 1 to 5 is that the number of virtual nodes of node 1 is 2, the number of virtual nodes of node 2 is 1, the number of virtual nodes of node 3 is 1, and the number of virtual nodes of node 4 is Two and the number of virtual nodes of the node 5 is two.

  Under such conditions, the rebalance unit 18e resets the number of virtual nodes held by the nodes 1 to 5 to a necessary load amount according to the current load state. Hereinafter, the resetting process will be described.

  First, the rebalance unit 18e changes the number of virtual nodes of each of the nodes 1-5. For example, as shown in FIG. 8A, the current number of virtual nodes in each of the nodes 1 to 5 is two for node 1, one for node 2, one for node 3, two for node 4, 5 is a total of 8 pieces. As shown in FIG. 8 (b), this corresponds to one node 1, two nodes 2, two nodes 3, two nodes 4, according to the current state of loads of the nodes 1 to 5. Node 5 changes to a total of 10 nodes.

  The above formula (1) is used when changing the number of virtual nodes. For example, the number of virtual nodes is changed as shown in FIG. 8B in which the number of nodes 1 to 5 shown in FIG. 8A is “2, 1, 1, 2, 2” = 8. The number of nodes 1 to 5 is changed to “1, 2, 2, 2, 3” = 10.

  In the current state of FIG. 8A, the hash space size (size of the assigned area) of all the nodes 1 to 5 is 1600 of “0 to 1599” and the number of virtual nodes is 8, so the assigned area per virtual node is The size is 1600 ÷ 8 = 200. Of the size of the assigned area of D = 200, the actual measured value of the load of the corresponding node 1 is, for example, “80” or “150”. Since the average value of the loads of all the nodes 1 to 5 is obtained from the actually measured values of all the nodes 1 to 5, the average value and the actually measured value are substituted into the above formula (1).

  For example, in the assigned area (size D = 200) of the distribution ID space of virtual node ID = “Node 1-1”, the actual load value is “140”, and in “Node 1-2”, the actual load value is “160”. If there is, the measured value of the load of the node 1 is “300”. At this time, the average value of the loads of all the nodes 1 to 5 is “150”. In this case, the number of virtual nodes after the rebalancing of node 1 is 2 × (150/300) = 1. Similarly, the number of virtual nodes after rebalancing is obtained in the other nodes 2 to 5, and the number of virtual nodes of each node 1 to 5 is changed to the obtained number of virtual nodes. However, when the calculation result fitted to the formula (1) includes a decimal point such as 1.6, it is determined in advance that rounding up, rounding down, and rounding off are performed.

  Next, the rebalance unit 18e changes the hash space size per virtual node. In the current state shown in FIG. 8A, as described above, the hash space size D per virtual node is 1600/8 = 200.

  If the number of virtual nodes after change = 10 is used, the hash space size per virtual node is 1600/10 = 160. Using this hash space size, as shown in FIG. 8B, the hash space size D of each virtual node is set to “160”.

  Next, the rebalance unit 18e allocates the virtual nodes having the changed hash space size D = “160” by the number of virtual nodes of the respective nodes 1 to 5 after the above change. That is, since there is one changed virtual node in the node 1, as shown in FIG. 8B, in the node 1, the changed virtual node {has the virtual node ID “Node1-” having the hash space size D = “160”. 1 "} is allocated.

  Similarly, since there are two virtual nodes after the change in node 2, two virtual nodes {virtual node IDs “Node2-1, Node2-2”} of size D = “160” are allocated. Thereafter, as shown in the figure, two to three virtual nodes after the change are allocated to the nodes 3 to 5.

  As a result of the rebalance design as described above, a post-rebalance distribution ID table as shown in FIG. 8B is obtained, and this is distributed to each node 15 when there is no cancellation. Each node 15 executes a distribution process according to the distribution ID table.

(Regarding the processing of the rebalancing cancel function unit 18f)
Hereinafter, the processing of the rebalancing cancel function unit 18f will be described. The processing of the rebalancing cancellation function unit 18f may be performed by any node 15, but here, as described above, it is performed by a privileged node that performs rebalancing design and distribution of the distribution ID table after rebalancing. Is assumed.

  When the rebalancing cancel function unit 18f determines that rebalancing is necessary by the rebalancing unit 18e, the rebalancing cancellation function unit 18f first loads each node based on the load data of all the nodes 15 obtained by the node load measuring unit 18d. A difference table 19g is created and stored in the storage unit 19.

  On the left side of FIG. 9, an example of a node-by-node load difference table 19g is shown. As shown in the example of FIG. 9, the node-by-node load difference table 19g includes an actually measured load for each node 15 and a difference (deviation) from an average value (total load of all nodes / number of nodes, here 70). In this example, a calculation example in units of nodes is shown, but the node here may be a “virtual node”.

  Then, the node load measuring unit 18d loads the load data (only the difference only) of each node at the time when the node-by-node load difference table 19g is created (= the time when it is determined that rebalancing is necessary, and this is t). May be stored in the storage unit 19 as the previous measurement data 19h. When the previous measurement data 19h is already stored, the previously stored “previous measurement data 19h” is deleted, and the current “previous measurement data 19h” is stored.

  Next, the rebalancing cancel function unit 18f performs the current node load measurement data 19d (actual measurement data of the load of each node 15) after the time (Δt) required for the rebalance design from t (that is, at the time t + Δt). ) From the current node load measurement data 19d and the previous measurement data 19h, the node-specific predicted load comparison table 19g (19g same as the node load difference table in the meaning of the table related to the cancellation determination) is attached. Create). Δt may be a predetermined time, or the rebalancing unit 18e estimates Δt from the number of nodes involved in the calculation, and the rebalancing unit 18e notifies Δt to the rebalancing cancellation function unit 18f. It is good to do. Note that the update time interval of the node load measurement data 19d is shorter than Δt.

  An example of the predicted load comparison table 19g for each node is shown on the right side of FIG. As shown in the per-node predicted load comparison table 19g, the per-node predicted load comparison table 19g is a load per node at the current time (t + Δt) and a difference at time t (referred to as “previous difference”). ) And a predicted load. The predicted load is the load on each node when it is assumed that rebalancing has been executed. Since it is assumed that the difference is eliminated by the rebalancing, the predicted load here is obtained by “current load-previous difference”. For example, in the example of FIG. 9, the load at the current time (t + Δt) in the node A is 125 and the front difference is +68, so the predicted load is 125−68 = 57.

  Then, the rebalancing cancellation function unit 18f determines whether or not any of the following criteria (1) and (2) is satisfied, and is required at the timing t when either is satisfied. Cancel the rebalance determined to be present. If neither is satisfied, it is decided to perform rebalancing.

  Determination criterion (1): There is an increase or decrease in the number of nodes.

  Criteria (2): There is a node whose predicted load value is outside the allowable range.

  The increase / decrease in the number of nodes in the determination criterion (1) can be determined by, for example, the rebalancing cancellation function unit 18f acquiring the rebalance design result (distribution ID table) from the rebalancing unit 18e. Here, the case where the number of nodes increases is, for example, a case where the increase in load is large, the current number of nodes is insufficient, and it is necessary to add nodes. Also, the case where the number of nodes decreases is, for example, a case where the number of nodes is reduced because the decrease in load is large, the current number of nodes is too large and inefficient.

  In addition, regarding the criterion (2), the allowable range is a predetermined value. In the example of FIG. 9, the allowable range is ± 20% from the average value. In the example of FIG. 9, since the node G is out of the allowable range, it is determined to cancel the rebalance.

  On the other hand, in the example shown in FIG. 10, since all nodes are within the allowable range, it is determined that rebalancing is to be executed.

  Further, regarding the criterion (2), the criterion (2) may be satisfied when the number of nodes outside the allowable range exceeds a predetermined threshold. As an example, the criterion (2) is “the number of nodes outside the allowable range> 20% of the total number of nodes”, and if this is satisfied, the determination is canceled. In this case, in the examples of FIGS. 9 and 10, when three or more predicted values are outside the allowable range, the cancellation is performed.

  Here, canceling the rebalance means, for example, that the rebalancing cancellation function unit 18f discards the new distribution ID table obtained by the rebalancing design to the rebalance unit 18e without distributing it to each node 15. It is to instruct to do. Further, when it is determined to execute the rebalance, the rebalancing cancel function unit 18f distributes the new distribution ID table obtained by the rebalance design to each node 15 to the rebalance unit 18e. Instruct.

  With reference to FIG. 11, the effect of the processing of the rebalancing cancel function unit 18f will be described. FIG. 11 shows, for example, the transition of load for a certain node. It is determined that rebalancing is necessary at time t. After that, the load on the node decreases, and at the time of t + Δt, it is within an allowable range (a range in which rebalancing is not required). However, the prior art does not consider such a change in load over time, so rebalancing is performed, the load falls outside the allowable range, and rebalancing is executed again.

  On the other hand, the determination function of the rebalancing cancellation function unit 18f determines that rebalancing is canceled at the time point t + Δt, and thus it is possible to maintain an allowable load without executing unnecessary rebalancing.

(Operation example)
Next, in the distributed system 10 according to the present embodiment, examples of operations when performing determination of the necessity of rebalancing to correct the load imbalance between the nodes 15, cancellation determination, and the like are illustrated in FIGS. This will be described with reference to the flowchart of FIG. This operation example is based on the hash space shown in FIG. 3, for example. The following operation example corresponds to the rebalance design method described first.

  First, in step S1 shown in FIG. 12, the distributed system load rebalancing unit 18e of a predetermined node (example: node B of FIG. 3) uses the node load measurement data 19d collected from each node A to E at a predetermined cycle. Based on the load average values, standard deviation, deviation, and deviation / standard deviation of each node A to E are calculated.

  Next, in step S2, the rebalance unit 18e records the calculation result in step S1 in the storage unit 19 as the aggregate data 19e (example: FIG. 6).

  In step S3, the rebalance unit 18e determines whether any one of the three conditions (1) to (3) described above is satisfied based on the data 19e recorded in step S2. As a result, if not satisfied (No), the rebalancing process is terminated.

  On the other hand, if any one of them is satisfied as a result of the determination, the rebalancing cancel function unit 18f performs the rebalancing cancel determination in step S3.

  Refer to FIG. 14 for rebalancing cancellation determination. The rebalancing cancellation function unit 18f creates a node-by-node load difference table 19g at the time (t) when it is determined that rebalancing is necessary, and then, at time t + Δt, the node-by-node load difference table 19g and its Based on the node load measurement data 19d at the time, the node-by-node predicted load comparison table 19g is created (step S41). In step S42, the rebalancing cancel function unit 18f determines whether any of the above-described determination criterion (1) and determination criterion (2) is satisfied, and cancels the rebalance if satisfied (step S42). S43) If not satisfied, no cancellation is made (step S44).

  Returning to FIG. 12, when canceling the rebalance, the process returns to step S <b> 1, and the necessity for rebalancing is determined at the next timing in the same manner as described above.

  When the rebalance is not canceled, the load amount of each node A to E is detected in step S5. For example, by transferring the transfer area in the assigned area of the high load node A to the other nodes B and C, the load bias To make corrections.

  In step S6, the rebalancing unit 18e calculates the size (= load amount) of the transfer area in the transfer area of the transfer source node, and in step S7, determines the allowable size of the transfer area of the transfer destination node.

  Next, in step S8 shown in FIG. 13, the rebalancing unit 18e determines whether or not there is a transfer destination node that can transfer the assigned area of the transfer source node. This determination is made by detecting whether or not the allowable size of the area in charge of the transfer destination node can transfer the transfer area in the area in charge of the transfer source node. As a result, if there is no transferable transfer destination no (No), the rebalancing process is terminated.

  On the other hand, if there is a transfer destination node that can be transferred (Yes), in step S9, the rebalance unit 18e transfers the transfer area in the assigned area of the transfer source node to the transfer destination node.

  Thereafter, in step S10 shown in FIG. 13, the rebalancing unit 18e determines whether or not there is a remaining transfer area in the assigned area of the transfer source node. As a result, if there is no remaining (No), in other words, if all of the transfer target areas have been transferred, the rebalancing process ends.

  On the other hand, if there is a remaining in the determination in step S10 (Yes), in step S11, the rebalance unit 18e determines whether there is a transfer destination node to which the remaining transfer area of the transfer source node can be transferred. To do. As a result, if there is no transfer destination node (No), the rebalancing process is terminated.

  As a result of the determination in step S11, if there is a transfer destination node to which the remaining transfer area can be transferred (Yes), in step S12, the rebalancing unit 18e determines the remaining transfer area of the transfer source node in step S10. It is transferred to the transfer destination node whose existence is recognized in.

  Thereafter, returning to step S10, the rebalance unit 18e repeats steps S10 to S12 until the processing is completed. Further, as described above, the processing after step S6 is repeated for each transfer source node.

  By the above processing, the distribution ID table 19b after rebalancing is created and distributed to each node, whereby the distribution processing after rebalancing is executed, and the load bias is eliminated.

(Summary of embodiment)
As described above, according to the present embodiment, a rebalancing apparatus used in a distributed system having a plurality of nodes to which information from a plurality of client machines using a communication service is distributed via a network, Based on the load amounts of a plurality of nodes, the rebalance processing means for determining whether or not the rebalance that suppresses the uneven load amount among the plurality of nodes is necessary, and the rebalance processing means And a cancel processing means for determining whether or not to cancel the rebalance based on the predicted load state of the plurality of nodes after the rebalance. Provided. The rebalancing device may be any node in the plurality of nodes, or may be a device other than the plurality of nodes.

  The cancel processing means is, for example, at a second time when a time required for rebalance design by the rebalance processing means has elapsed from a first time when the rebalance processing means determines that rebalancing is necessary. The predicted load state is calculated based on the load amounts of the plurality of nodes and the load amounts of the plurality of nodes at the first time point.

  Further, for example, when the predicted load state is a load state that requires an increase or decrease in the number of nodes, or the predicted load state is a load state in which a predetermined number of nodes having a load amount outside an allowable range exists. In addition, the cancel processing means determines to cancel the rebalance.

  In addition, for example, at the first time point, the cancel processing unit calculates a difference from an average value of load amounts of the plurality of nodes at the first time point for each node, and at the second time point, For each node, the predicted load state is calculated by subtracting the difference from the load amount of the node at the second time point.

  The distributed system load rebalancing unit 18e is an example of a rebalance processing unit. The rebalancing cancel function unit 18f is an example of a cancel processing unit.

  According to the technique according to the present embodiment, in a distributed system, it is possible to determine at high speed whether rebalancing is appropriate, including the viewpoint of the passage of time, and to specify a situation that should not be performed. Therefore, execution of useless rebalancing can be suppressed.

(Section 1)
A rebalancing device used in a distributed system having a plurality of nodes to which information from a plurality of client machines using a communication service is distributed via a network,
Rebalancing processing means for determining whether or not rebalancing is necessary to suppress the uneven load amount between the plurality of nodes based on the load amounts of the plurality of nodes;
When the rebalancing processing unit determines that rebalancing is necessary, based on the predicted load state of the plurality of nodes after the rebalancing, canceling whether to cancel the rebalancing or not Processing means and
A rebalancing device comprising:
(Section 2)
The cancellation processing means
The load amounts of the plurality of nodes at the second time point when the time required for the rebalance design by the rebalance processing unit has elapsed from the first time point when the rebalance processing unit determines that rebalancing is necessary. And calculating the predicted load state based on load amounts of the plurality of nodes at the first time point.
The rebalancing device according to item 1, characterized in that:
(Section 3)
If the predicted load state is a load state that requires an increase or decrease in the number of nodes, or the predicted load state is a load state in which a predetermined number of nodes having a load amount outside the allowable range exists, the cancellation is performed. The processing means determines to cancel the rebalance
The rebalancing apparatus according to item 1 or 2, characterized in that:
(Section 4)
The cancellation processing means
At the first time point, a difference from the average load amount of the plurality of nodes at the first time point is calculated for each node, and at the second time point, for each node, at the second time point The predicted load state is calculated by subtracting the difference from the load amount of the node.
The rebalancing device according to item 2, characterized in that:
(Section 5)
A rebalancing method executed by a rebalancing device used in a distributed system having a plurality of nodes to which information from a plurality of client machines using a communication service is distributed via a network,
A rebalance determination step for determining whether or not rebalancing is required to suppress the uneven load amount between the plurality of nodes based on the load amounts of the plurality of nodes;
Cancellation for determining whether or not to cancel the rebalancing based on the predicted load state of the plurality of nodes after the rebalancing when the rebalancing determination step determines that rebalancing is necessary Judgment step and
A rebalancing method comprising:
(Section 6)
In the cancellation determination step, the rebalance device
Load amounts of the plurality of nodes at the second time point when the time required for rebalance design has elapsed from the first time point when the rebalance determination step determines that rebalancing is necessary, and the first time point The predicted load state is calculated based on the load amounts of the plurality of nodes at
6. The rebalancing method according to item 5, wherein
(Section 7)
In the cancellation determination step, the predicted load state is a load state that requires an increase or decrease in the number of nodes, or the predicted load state is a load state in which a predetermined number of nodes having a load amount outside an allowable range exists. In some cases, the rebalancing device determines to cancel the rebalancing.
7. The rebalancing method according to item 5 or 6, wherein
(Section 8)
The program for functioning a computer as each means in the rebalancing apparatus of any one of Claim 1 thru | or 4.
As mentioned above, although the Example of this invention was explained in full detail, this invention is not limited to such specific embodiment, In the range of the summary of this invention described in the claim, various deformation | transformation・ Change is possible.

DESCRIPTION OF SYMBOLS 10 Distributed system 11 Client machine 12 Network 13 Load balancer 14 Cluster 15 Node 18 Control part 18a Node identifier management part 18b Distribution part 18c Signal processing part 18d Node load measurement part 18e Distributed system load rebalancing part 18f Rebalancing cancellation function part 19 Storage unit 19a Node identifier management table 19b Distribution ID table 19c Data 19d Node load measurement data 19e Distributed system load summary data 19f Call control status flag 19g Load difference table for each node, predicted load comparison table for each node 19h Previous measurement data

Claims (5)

A rebalancing device used in a distributed system having a plurality of nodes to which information from a plurality of client machines using a communication service is distributed via a network,
Rebalancing processing means for determining whether or not rebalancing is necessary to suppress the uneven load amount between the plurality of nodes based on the load amounts of the plurality of nodes;
When the rebalancing processing unit determines that rebalancing is necessary, based on the predicted load state of the plurality of nodes after the rebalancing, canceling whether to cancel the rebalancing or not Processing means ,
The cancellation processing means
At a first time point when the rebalance processing unit determines that rebalancing is necessary, a difference from an average value of load amounts of the plurality of nodes at the first time point is calculated for each node, By subtracting the difference from the load amount of the node at the second time point for each node at the second time point when the time required for the rebalance design by the rebalance processing unit has elapsed from the time point 1, the prediction is performed. A rebalancing device that calculates a load state . If the predicted load state is a load state that requires an increase or decrease in the number of nodes, or the predicted load state is a load state in which a predetermined number of nodes having a load amount outside the allowable range exists, the cancellation is performed. The rebalancing apparatus according to claim 1, wherein the processing unit determines to cancel the rebalancing. A rebalancing method executed by a rebalancing device used in a distributed system having a plurality of nodes to which information from a plurality of client machines using a communication service is distributed via a network,
A rebalance determination step for determining whether or not rebalancing is required to suppress the uneven load amount between the plurality of nodes based on the load amounts of the plurality of nodes;
Cancellation for determining whether or not to cancel the rebalancing based on the predicted load state of the plurality of nodes after the rebalancing when the rebalancing determination step determines that rebalancing is necessary A determination step ,
In the cancellation determination step, the rebalance device
At a first time point when rebalancing is determined by the rebalance determining step, a difference from an average value of load amounts of the plurality of nodes at the first time point is calculated for each node, The predicted load state is calculated by subtracting the difference from the load amount of the node at the second time point for each node at the second time point when the time required for rebalance design has elapsed from the time point 1. A rebalancing method characterized by In the cancellation determination step, the rebalancing device is configured such that the predicted load state is a load state that requires an increase or decrease in the number of nodes, or the predicted load state has a predetermined number of nodes having a load amount outside an allowable range. The rebalancing method according to claim 3 , wherein the rebalancing device determines that the rebalancing is canceled when a load state exists. The program for functioning a computer as each means in the rebalancing apparatus of Claim 1 or 2 .

Images