• preface
  • Load balancer
  • Load balancing algorithm
    • Random algorithm
      • Random
      • WeightRandom
    • Polling and weighted polling
      • Round Robbin
      • Weighted Round Robbin
    • Minimum link and weighted minimum link
      • Least Connections
      • Weighted Least Connection
    • The hash algorithm
      • Common hash
      • Consistency hashing
    • IP address hash
    • The URL hash
  • The method of load uniformity algorithm
    • DNS Domain name Resolution Load Balancing (delay)
    • Data Link Layer Load Balancing (LVS)
    • IP Load Balancing (SNAT)
    • HTTP Redirected load balancing (rare)
    • Reverse Proxy Load Balancing (NGINx)

preface

Load balancing learning record ~

Load balancer

This can be a dedicated device or an application running on a common server. Distribute requests to servers that have the same content or provide the same services. Dedicated devices generally only have Ethernet interfaces, which can be said to be a kind of multi-layer switch. Virtual IP addresses are assigned to load balancers. All requests from clients are processed based on virtual IP addresses. The load balancer uses a load balancing algorithm to forward requests from clients to the actual IP address of the server

Load balancing algorithm

Const serverMap = new Map ([[' 192.168.1.100, 1], [' 192.168.1.101, 3], [' 192.168.1.102, 1], [' 192.168.1.103 ', 1), [' 192.168.1.104,, 4], [' 192.168.1.105, 1], [' 192.168.1.106, 2], [' 192.168.1.107, 1], [' 192.168.1.108 ', 1), ['192.168.1.109', 2], ['192.168.1.110', 1],])Copy the code

Random algorithm

Random

Random, according to the weight of the random probability, the probability of collision in a section is high, but the greater the amount of adjustment is more uniform distribution, and according to the probability of weight is also more uniform, conducive to dynamic adjustment of weight.

function random() {
    const servers = [];
    for (let [address, weight] of serverMap) {
        servers.push(address)
    }
    const index = Math.floor(Math.random() * servers.length);
    const address = address[index];
    console.log(address);
}
Copy the code

WeightRandom

According to the weight

function weightRandom() {
    const servers = [];
    for (let [address, weight] of serverMap) {
        for (let i = 0; i < weight; i += 1) {
            servers.push(address)
        }
    }
    const index = Math.floor(Math.random() * servers.length);
    const address = address[index];
    console.log(address);
}
Copy the code

Polling and weighted polling

Round Robbin

This algorithm is best used when all servers in a server farm have the same processing capacity and there is little difference in the processing capacity of each service.

Polling, according to the convention after the weight set polling ratio, there is a slow server cumulative request problem, such as: the second machine is slow, but not hung, when the request is transferred to the second machine stuck, over time, all the requests stuck on the second machine.

const index = 0; const servers = []; for (let [address, Function roundRobin() {if (index >= servers.length) index = 0; console.log(servers[index]); }Copy the code

Weighted Round Robbin

Add some weight algorithm to the dummy server in polling, for example:

[server 1, weight], [server 2, weight 2], [server 3, weight 3]

Order: 1 – > 2 – > 2 – > 3 – > 3 – > 3 – > 1 – > 2 – > 2 – > 3 – > 3 – >…

const servers = []; for (let [address, weight] of serverMap) { for (let i = 0; i < weight; I += 1) {servers.push(address)}} function weightRoundRobin() {// loop if (index >= servers.length) index = 0; console.log(servers[index]); }Copy the code

Minimum link and weighted minimum link

Least Connections

In multiple servers, the algorithm that communicates with the server that handles the least number of connections (sessions) can reduce the load on the server to some extent, even if the processing capacity of each server is different and the volume of each transaction is different.

Weighted Least Connection

An algorithm that attaches weight to each server in the least number of connections algorithm, which preassigns each server the number of connections to process and directs customer requests to the server with the least number of connections.

The hash algorithm

Common hash

/** * remoteIp = visitor */ function hash(remoteIp = '192.168.2.215') {const Servers = []; for (let [address, weight] of serverMap) { servers.push(address) } const hashCode = remoteIp.hashCode(); Const index = hashCode % Servers.length; // Render console.log(Servers [index]); }Copy the code

Consistency hashing

Consistent Hash: Requests with the same parameters are always sent to the same server for processing. When a server is down, the requests originally sent to this server are distributed to other servers based on virtual nodes without drastic changes.

IP address hash

By managing the sender IP and destination IP address hash, unified will come from the sender’s group united (or sent to the destination of the packet) unified to the same server algorithm, when a customer comprised a series of business need to deal with and must repeatedly and a server communication, the algorithm is able to flow (session) as the unit, Ensure that traffic from the same client can always be processed in a unified server.

The URL hash

An algorithm that forwards requests to the same URL to the same server by managing the hash of URL information requested by clients.

The method of load uniformity algorithm

Methods:

DNS -> Data link layer -> IP -> Http layer

DNS Domain name Resolution Load Balancing (delay)

It is A common solution to use DNS to process domain name resolution requests and perform load balancing. Multiple A records are configured on the DNS server.

Such as:

  • www.mysite.com IN A 114.100.80.1
  • www.mysite.com IN A 114.100.80.2
  • www.mysite.com IN A 114.100.80.3

Each domain name resolution request is returned with A different IP address based on the load balancing algorithm. In this way, multiple servers configured in record A form A cluster and load balancing is implemented.

The advantage of DNS domain name resolution load balancing is that the LOAD balancing work is handed over to DNS and the network management trouble is omitted. The disadvantage is that DNS may cache A records and is not controlled by websites.

In fact, large sites always partially use DNS resolution as a first-level load balancing tool, and then do second-level load balancing internally.

Data Link Layer Load Balancing (LVS)

Data link layer load balancing refers to load balancing by changing MAC addresses on the data link layer of communication protocols.

This data transfer mode is also called triangular transfer mode. During load balancing, IP addresses are not changed during data distribution, but MAC addresses of the destination are changed. The virtual IP addresses of all the servers in the real physical server cluster are the same as those of the load balancing server to achieve load balancing. In this way, the load balancing mode is also called direct routing (DR).

In the figure above, after the user request reaches the load balancing server, the load balancing server changes the destination MAC address of the request data to the MAC address of the real WEB server without changing the destination IP address of the data packet. Therefore, the data can normally reach the destination WEB server. After processing the data, the server can go through the network management server instead of the load balancing server to reach the user browser directly.

LVS (Linux Vitual Server) is the best open source product for data link layer load balancing on Linux platform.

IP Load Balancing (SNAT)

IP load balancing: Load balancing is performed at the network layer by modifying the destination IP address of the request.

User request packet arriving at the load balancing server, the load balancing server access to network packets in the operating system kernel, according to the calculation of load balancing algorithm is a real WEB server address, and then amend the packet’s IP address to the real WEB server address, don’t need to deal with, through the user process After the real WEB server finishes processing, the response packet goes back to the load balancing server, and the load balancing server changes the source address of the packet to its OWN IP address and sends it to the user visitor.

The key here is how the real WEB server responds to the packet back to the load balancer:

  • A load balancing server changes the source IP address of a packet to its own IP address when changing the destination IP address. This is called Original Address translation (SNAT).
  • Another option is to use the load balancer server as a gateway server to the real physical server, so that all data will reach the load balancer server.

IP load balancing completes data distribution in the kernel process and has better processing performance than reverse proxy balancing. However, all data packets requesting data need to pass through the load balancing server, so the network card loan of load balancing becomes the bottleneck of the system.

HTTP Redirected load balancing (rare)

HTTP redirect server is an ordinary application server, its only function is to calculate a real server address according to the user’s HTTP request, and write the real server address in the HTTP redirect response (response status code) back to the tour, and then the tour in the automatic request real server.

The advantage of this load balancing scheme is that it is relatively simple to determine whether the tourist needs to request two service periods each time to complete a visit, which has poor performance. Redirection using HTTP 302 response code may be judged as SE0 cheating by the search engine and reduce the search ranking. The redirection server’s own processing power can be a bottleneck, so this solution is not very common in practice.

Reverse Proxy Load Balancing (NGINx)

A traditional proxy server sits on one side of the browser, which delivers HTTP requests to the Internet. On the other hand, the reverse proxy server is located in the equipment room of the website. The web server of the proxy website receives HTTP requests.

The purpose of the directional proxy is to protect the website. All Internet requests go through the proxy server, but it creates a barrier between the Web server and possible network attacks.

In addition, the proxy server can also configure caching to speed up Web requests. When users access static content for the first time, static memory is cached on the proxy server in the direction. In this way, when other users access the static content, they can directly return it from the server in the direction, speeding up the response speed of Web requests. Reduce the load on the Web server.

In addition, the reverse proxy server can also implement load balancing.

Because the reverse proxy server forwards requests at the HTTP protocol level, it is also called application-layer load balancing. It is easy to deploy and may become a system bottleneck.

reference

  • Load balancing algorithm and means