CN104104611A - Method and device for achieving cluster load balancing dispatching - Google Patents

Abstract

The invention discloses a method and device for realizing cluster load balancing scheduling, comprising: when the computing cluster receives a request packet, setting the hash level to 0; according to the request packet and the hash level, determining the server corresponding to the hash level; judging Whether the obtained server meets the scheduling conditions. When the server meets the scheduling conditions, the request will be distributed to the server; when the server does not meet the scheduling conditions, the hash level will increase by 1, and continue to determine the server corresponding to the hash level. If the maximum value is set, the request is rejected; the value range of the hash level is [0, N-1], and N is the total number of servers. The technical solution of the present application reduces the probability of rejecting requests and greatly improves the utilization rate of cluster resources.

Description

A method and device for implementing cluster load balancing scheduling

technical field

The invention relates to the field of computer clusters, in particular to a method and device for realizing cluster load balance scheduling.

Background technique

Various load balancing methods are often used in cluster computing to solve the scalability and transparency problems of the system, that is, the load balancing scheduler efficiently distributes requests to different servers for execution, making a cluster system composed of multiple independent computers Become a virtual server; client applications interact with the cluster system as if interacting with a high-performance server.

At present, common load balancing scheduling methods include round-robin scheduling, weighted round-robin scheduling, minimum connection scheduling, weighted minimum connection scheduling, locality-based least connection, locality-based least connection with replication, target address hash scheduling, source Address hash scheduling, etc. Among them, destination address hash scheduling and source address hash scheduling are relatively common static scheduling methods. In practical applications, these two scheduling methods are used in firewall clusters to ensure that the entire system has a unique entrance and exit.

The basic principle of the source address hash scheduling algorithm is to find out the corresponding server from the statically allocated hash table according to the source IP address of the request as a hash key. This algorithm can quickly and efficiently schedule servers, and at the same time, it can ensure that requests with the same address are scheduled to the same server. However, the problem with this method is that if the server hashed by a source address is overloaded, it will return empty, that is, it will refuse to process subsequent requests, so when a single server is heavily loaded, frequent requests to the server cannot be hashed. be processed, which reduces the utilization of cluster resources.

Contents of the invention

In order to solve the above technical problems, the present invention provides a method and device for implementing cluster load balancing scheduling, which can greatly reduce the probability of rejecting requests and greatly improve the utilization rate of cluster resources.

In order to achieve the purpose of the above invention, the present invention discloses a method for realizing cluster load balancing scheduling, including:

When the computing cluster receives the request packet, set the hash level to 0;

According to the request package and the hash level, determine the server corresponding to the hash level;

Determine whether the obtained server meets the scheduling conditions. When the server meets the scheduling conditions, distribute the request to the server; If the maximum value is exceeded, the request is rejected;

Wherein, the value range of the hash level is [0, N-1], and N is the total number of servers.

Further, before the hash level is set to 0 when the computing cluster receives the request packet, the above method further includes: establishing a ServerNode table for storing the one-to-one correspondence between each server information and the index value in the computing cluster.

Further, the request packet includes: the IP address of the external user.

Further, determine the server corresponding to the hash level, including:

The index value of the server is obtained by the following formula:

(ip_addr*2654435761UL)% (N—hash level); wherein, ip_addr is an integer corresponding to the IP address, and % is a modulo operation.

According to the index value of the server, find the server corresponding to the hash level in the ServerNode table.

Further, the scheduling condition is: the server is alive, the weight is not 0, and the number of connections of the server is less than twice the weight.

The invention also discloses a device for realizing cluster load balance scheduling, including: a setting module, a mapping module, a judging module and a distribution module; wherein,

The setting module is used to set the hash level to 0 when an external user sends a request packet to the computing cluster;

The mapping module is connected with the setting module, and is used to determine the server corresponding to the hash level according to the request packet and the hash level;

A judging module, configured to judge whether the obtained server satisfies the scheduling condition;

The distribution module is used for distributing the request to the server when the server meets the scheduling condition;

The mapping module is also used to increase the hash level by 1 when the server does not meet the scheduling conditions, continue to determine the server corresponding to the hash level, and reject the request when the hash level exceeds the maximum value;

Wherein, the value range of the hash level is [0, N-1], and N is the total number of servers.

Further, the above-mentioned device also includes a storage module, which is connected to the setting module, and is used for: when the computing cluster receives the request packet, before setting the hash level to 0, establish a server information and index value for storing each server in the computing cluster ServerNode table of one-to-one correspondence.

Further, the request packet includes: the IP address of the external user.

Further, the mapping module is specifically used for:

The index value of the server is obtained by the following formula:

(ip_addr*2654435761UL)%(N—hash level); wherein, ip_addr is an integer corresponding to the IP address, and % is a modulo operation.

Find the server corresponding to the hash level in the ServerNode table according to the index value of the server.

Further, the scheduling condition is: the server is alive, the weight is not 0, and the number of connections of the server is less than twice the weight.

The technical solution of the present application includes: when an external user sends a request packet to the computing cluster, set the hash level to 0; determine the server corresponding to the hash level according to the request packet and the hash level; determine whether the obtained server meets the scheduling conditions, and when When the server meets the scheduling conditions, the request is distributed to the server; when the server does not meet the scheduling conditions, the hash level is increased by 1, and the server corresponding to the hash level is continued to be determined. When the hash level exceeds the maximum value, the request is rejected; wherein, The value range of the hash level is [0, N-1], and N is the total number of servers. The technical solution of the present application reduces the probability of rejecting requests and greatly improves the utilization rate of cluster resources.

Description of drawings

The accompanying drawings described here are used to provide a further understanding of the present invention and constitute a part of the application. The schematic embodiments of the present invention and their descriptions are used to explain the present invention and do not constitute improper limitations to the present invention. In the attached picture:

Fig. 1 is the flow chart of the method for realizing cluster load balance scheduling of the present invention;

Fig. 2 is the flow chart of the embodiment of the method for realizing cluster load balance scheduling of the present invention;

FIG. 3 is a schematic structural diagram of a device for implementing cluster load balancing scheduling according to the present invention.

Detailed ways

The invention improves the existing source address hash scheduling algorithm, and introduces a level parameter hash level (level) for specifying the hash level. When the level is 0, it is the hash function used by the source address hash scheduling. If no server meeting the requirements is found when level=0, then add a level to continue searching, and increase the level in a waterfall manner until a server meeting the requirements is found. This method Only when the level reaches the number of servers N will it announce that no server that meets the requirements can be found, and when the level reaches the N value, it indicates that all servers have been traversed, that is, all servers are servers that do not meet the requirements.

The present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments.

Fig. 1 is the flow chart of the method for realizing cluster load balancing scheduling of the present invention, as shown in Fig. 1, comprising:

Step 101, when the computing cluster receives the request packet, set the hash level to 0.

The request packet in this step is sent from a user on the external network to the computing cluster, and the request packet includes the source address IP, which is the IP address used by the external user.

Before this step, the method of the present invention further includes: establishing a ServerNode table for storing a one-to-one correspondence between each server information and an index value in the computing cluster.

The server information includes: server IP, name, memory, hard disk. How to establish the ServerNode table belongs to the common knowledge well known by those skilled in the art, and details are not repeated here.

It should be noted that the ServerNode table contains all servers and their information, and each index value in the ServerNode table corresponds to a server in the ServerNode table, that is, if you find the index value, you can obtain the corresponding server and the server's information.

The above request packet includes: the IP address of the external user.

Step 102, according to the request packet and the hash level, determine the server corresponding to the hash level.

Specifically include:

First, get the index value of the server corresponding to the hash level through the following formula:

(ip_addr*2654435761UL)%(N—hash level); wherein, ip_addr is an integer corresponding to the IP address, and % is a modulo operation.

Secondly, according to the index value of the server, find the server corresponding to the hash level in the ServerNode table.

It should be noted that finding the index value of the server through the above formula is similar to the hash function of prime number multiplication in the prior art. The difference is also the core of the present invention: the first difference is that the hash mask, that is, N-hash The level is not fixed, but changes according to the hash level; the second difference is that the server index value corresponding to the hash level is not obtained by AND operation but by modulo operation, which makes the operation more convenient and greatly saves calculation time. In addition, 2654435761UL is a globally fixed value, which is a prime number close to the golden section between 2 and 2^32 (4294967296), 2654435761/4294967296=0.618033987, which ensures that different source addresses will be allocated to different servers as much as possible.

The corresponding ip_addr can be obtained by the following method: field less than three digits plus 0 to make up three digits.

For example, when the IP address is 192.168.0.1, because the first two fields are three digits, it is only necessary to fill in the last two fields, that is, add two 0s to the third field to become 000, and the fourth field Two 0s are added to become 001, and the above IP address is converted to ip_addr=192168000001. If there are 1000 servers in total, N=1000, and the IP address is 192.168.0.1, ip_addr=192168000001, when the hash level=0, N—hash level=1000–0=1000, then (ip_addr*2654435761UL)%(N— hash level)=192168000001*2654435761%1000=761, that is, hash to the 761st server, when the hash level is 1, N—hash level=1000–1=999, then (ip_addr*2654435761UL)%(N—hash level )=192168000001*2654435761%999=763, that is, hash to the 763rd server.

Step 103, judging whether the obtained server meets the scheduling condition, when the server meets the scheduling condition, then distribute the request to the server; when the server does not meet the scheduling condition, then the hash level increases by 1, and returns to step 102, when the hash level exceeds maximum value, the request is rejected.

In this step, the scheduling condition is: the server is alive, the weight is not 0, and the number of connections of the server is less than twice the weight.

If the number of server connections is greater than or equal to 2 times the weight, it indicates that the server is overloaded.

What needs to be explained in this step is that the heartbeat detection technology in the prior art can be used to determine whether the current server is alive, which will not be repeated here. The weight and connection number of the server are stored in the scheduler. The weight refers to the rated connection number of each server saved in the scheduler and can be manually edited. It can be manually set, and the connection number of each server can be updated in real time during scheduling. The number refers to the number of external users connected to the server, which can be modified in real time. The method in the source address hash scheduling algorithm in the prior art is used to obtain and update the weight and connection number of each server.

In the above method, the value range of the hash level is [0, N-1], and N is the total number of servers.

Only when the level reaches the server quantity N, the method of the present invention will announce that no server meeting the requirements can be found, and when the level reaches the value of N (the total number of servers), it indicates that all servers have been traversed, that is, all servers are unavailable. Therefore, this method is an optimal scheduling algorithm. At the same time, this algorithm can inherit the advantages of the source address hash scheduling algorithm, that is, it has scheduling locality. When the load of the server is basically balanced, the same IP address Requests are dispatched to the same server, which improves the access locality and main memory hit rate of each server, thereby improving the processing capacity of the entire cluster system.

Fig. 2 is the flow chart of the embodiment of the method for realizing the cluster load balancing scheduling of the present invention, as shown in Fig. 2, comprises the following steps:

Step 201, when the computing cluster receives the request packet, set the hash level to 0.

Step 202, according to the request packet and the hash level, determine the server corresponding to the hash level.

This step is the same as step 102 and will not be repeated here.

Step 203, judging whether the server satisfies the scheduling condition, if the scheduling condition is met, go to step 204, if the server does not meet the scheduling condition, go to step 205.

The scheduling condition in this step is the same as the requirement in step 103 .

Step 204, distribute the request to the server. At this point, the distribution task is completed and ends.

In step 205, the hash level is increased by 1. Go to step 206.

Step 206, judge whether the hash level exceeds the maximum value, if it exceeds the maximum value, then go to step 207; if it does not exceed the maximum value, then return to step 202.

The value range of the above hash level is [0, N-1], and N is the total number of servers.

Step 207, rejecting the request.

FIG. 3 is a schematic structural diagram of a device for implementing cluster load balancing scheduling according to the present invention, as shown in FIG. 3 , including: a setting module, a mapping module, a judging module and a distribution module. in,

The setting module is used to set the hash level to 0 when the computing cluster receives the request packet.

The setting module receives a request packet sent from a user on the external network to the computing cluster. The request packet includes the source address IP, which is the IP address used by the external user, and the setting module sends the IP address and hash level to the mapping module.

The mapping module is connected with the setting module, and is used to determine the server corresponding to the hash level according to the request packet and the hash level.

Further, the above mapping module is specifically used for:

The index value of the above server is obtained by the following formula:

(ip_addr*2654435761UL)%(N—hash level); wherein, ip_addr is an integer corresponding to the IP address, and % is a modulo operation.

According to the index value of the server, the server corresponding to the above hash level is found in the ServerNode table.

It should be noted that finding the index value of the server through the above formula is similar to the hash function of prime number multiplication in the prior art. The difference is also the core of the present invention: the first difference is that the hash mask, that is, N-hash The level is not fixed, but changes according to the hash level; the second difference is that obtaining the server index value corresponding to the hash level does not use the AND operation but the modulo operation, which makes the operation more gradual, which greatly saves the operation time. In addition, 2654435761UL is a globally fixed value, which is a prime number close to the golden section between 2 and 2^32 (4294967296), 2654435761/4294967296=0.618033987, which ensures that different source addresses will be allocated to different servers as much as possible.

The corresponding ip_addr can be obtained by the following method: field less than three digits plus 0 to make up three digits.

For example, when the IP address is 192.168.0.1, because the first two fields are three digits, it is only necessary to fill in the last two fields, that is, the third field is supplemented with two 0s to become 000, and the fourth field Two 0s are added to become 001, and the above IP address is converted to ip_addr=192168000001. If there are 1000 servers in total, that is N=1000, when the IP address is 192.168.0.1, ip_addr=192168000001, when the hash level=0, N—hash level=1000–0=1000, then (ip_addr*2654435761UL)%(N— hash level)=192168000001*2654435761%1000=761, that is, hash to the 761st server, when the hash level is 1, N—hash level=1000–1=999, then (ip_addr*2654435761UL)%(N—hash level )=192168000001*2654435761%999=763, that is, hash to the 763th server.

A judging module, configured to judge whether the obtained server satisfies the scheduling condition.

The above scheduling conditions include: the server is alive, the weight is not 0, and the number of connections of the server is less than twice the weight.

If the number of server connections is greater than or equal to 2 times the weight, it indicates that the server is overloaded.

It should be noted that the heartbeat detection technology in the prior art can be used to determine whether the current server is alive, which will not be repeated here. The server's weight and connection number are stored in the scheduler. The weight refers to the rated connection number of each server that can be manually edited in the scheduler, and the connection number of each server can be updated in real time during scheduling. The connection number refers to the The number of external users connected to the server. The method in the source address hash scheduling algorithm in the prior art is used to obtain and update the weight and connection number of each server.

The distribution module is configured to distribute the request to the server when the server meets the scheduling condition.

The above mapping module is also used to increase the hash level by 1 when the server does not meet the scheduling conditions, and continue to determine the server corresponding to the hash level, and reject the request when the hash level exceeds the maximum value.

In the above device, the value range of the hash level is [0, N-1], and N is the total number of servers.

The above-mentioned device also includes: a storage module, connected to the setting module, used for: when the computing cluster receives the request packet, before setting the hash level to 0, establish a server information and index value for storing each server information and index value in the computing cluster ServerNode table of one-to-one correspondence.

The server information includes: server IP, name, memory, hard disk. How to establish the ServerNode table belongs to the common knowledge well known by those skilled in the art, and details are not repeated here.

It should be noted that the ServerNode table contains all servers and their information, and each index value in the ServerNode table corresponds to a server in the ServerNode table, that is, if you find the index value, you can obtain the corresponding server and the server's information.

Those skilled in the art can understand that all or part of the steps in the above method can be completed by instructing relevant hardware through a program, and the program can be stored in a computer-readable storage medium, such as a read-only memory, a magnetic disk or an optical disk, and the like. Optionally, all or part of the steps in the foregoing embodiments may also be implemented using one or more integrated circuits. Correspondingly, each module/unit in the foregoing embodiments may be implemented in the form of hardware, or may be implemented in the form of software function modules. This application is not limited to any specific form of combination of hardware and software.

The above descriptions are only preferred examples of the present invention, and are not intended to limit the protection scope of the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

Claims (10)

1. A method for realizing cluster load balancing scheduling is characterized by comprising the following steps:

when the computing cluster receives the request packet, setting the hash hierarchy to be 0;

determining a server corresponding to the hash hierarchy according to the request packet and the hash hierarchy;

judging whether the obtained server meets a scheduling condition, and when the server meets the scheduling condition, distributing the request to the server; when the server does not meet the scheduling condition, increasing the hash level by 1, continuously determining the server corresponding to the hash level, and when the hash level exceeds the maximum value, rejecting the request;

wherein, the value range of the hash hierarchy is [0, N-1], and N is the total number of the servers.

2. The method of claim 1, wherein before setting a hash level to 0 when the compute cluster receives the request packet, the method further comprises: and establishing a ServerNode table for storing the one-to-one corresponding relation between the information of each server in the computing cluster and the index value.

3. The method according to claim 1 or 2, wherein the request packet comprises: the IP address of the external user.

4. The method according to claim 3, wherein the determining the server corresponding to the hash hierarchy comprises:

the index value of the server is obtained by the following formula:

(ip _ addr 2654435761 UL)% (N-hash level); wherein IP _ addr is an integer corresponding to the IP address,% is modulo operation;

and finding the server corresponding to the hash level in a ServerNode table according to the index value of the server.

5. The method according to claim 1 or 2, wherein the scheduling condition is: the server is alive, the weight is not 0, and the number of the server connections is less than 2 times of the weight.

6. An apparatus for implementing cluster load balancing scheduling, comprising: the system comprises a setting module, a mapping module, a judging module and a distributing module; wherein

The system comprises a setting module, a hash module and a sending module, wherein the setting module is used for setting the hash hierarchy to 0 when an external user sends a request packet to a computing cluster;

the mapping module is connected with the setting module and used for determining a server corresponding to the hash hierarchy according to the request packet and the hash hierarchy;

the judging module is used for judging whether the obtained server meets the scheduling condition;

the distribution module is used for distributing the request to the server when the server meets the scheduling condition;

the mapping module is further used for increasing the hash hierarchy by 1 when the server does not meet the scheduling condition, continuously determining the server corresponding to the hash hierarchy, and rejecting the request when the hash hierarchy exceeds the maximum value;

wherein, the value range of the hash hierarchy is [0, N-1], and N is the total number of the servers.

7. The apparatus of claim 6, further comprising a storage module, coupled to the setup module, for: and when the computing cluster receives the request packet, before setting the hash level to be 0, establishing a ServerNode table for storing the one-to-one corresponding relation between the information of each server in the computing cluster and the index value.

8. The apparatus of claim 6 or 7, wherein the request packet comprises: the IP address of the external user.

9. The apparatus of claim 8, wherein the mapping module is specifically configured to:

the index value of the server is obtained by the following formula:

(ip _ addr 2654435761 UL)% (N-hash level); wherein IP _ addr is an integer corresponding to the IP address,% is modulo operation;

and finding the server corresponding to the hash level in a ServerNode table according to the index value of the server.

10. The apparatus according to claim 6 or 7, wherein the scheduling condition is: the server is alive, the weight is not 0, and the number of the server connections is less than 2 times of the weight.