Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to achieve load balancing algorithm in Java". The content in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to achieve load balancing algorithm in Java".

What is load balancing (Load balancing)?

In the early days of the website, we generally used a single machine to provide centralized services, but with the increasing volume of business, there are greater challenges in terms of performance and stability. At this time, we will think of expanding capacity to provide better services. We usually form a cluster of multiple machines to provide services. However, our website provides the same access point, such as www.taobao.com. So how do users distribute their requests to different machines in the cluster when they enter www.taobao.com in the browser? this is what load balancer is doing.

At present, most Internet systems use server cluster technology, which means that the same services will be deployed on multiple servers to provide services as a whole. These clusters can be Web application server clusters, database server clusters, distributed cache server clusters and so on.

In practical applications, there will always be a load balancer server before the Web server cluster. The task of the load balancer device is to act as the entrance of Web server traffic, select the most suitable Web server, forward the client's request to it for processing, and achieve transparent forwarding from the client to the real server. In recent years, "cloud computing" and distributed architecture are very popular, in essence, the back-end servers are used as computing resources and storage resources, which are encapsulated by a management server into a service for external provision. the client does not need to care about which machine really provides the service, as if it is facing a server with almost unlimited capabilities, while in essence, it is the back-end cluster that really provides services.

The two core problems solved by software load are: who to choose and forward, the most famous of which is LVS (Linux Virtual Server).

The topology of a typical Internet application is as follows:

Load balancing classification

We now know that load balancing is a computer network technology that is used to distribute load among multiple computers (computer clusters), network connections, CPU, disk drives, or other resources to optimize resource usage, maximize throughput, minimize response time, and avoid overload. Then, there are many ways to realize this computer technology. It can be divided into the following categories, of which the most commonly used are layer-4 and layer-7 load balancers:

Layer 2 load balancing

The cloud load balancer server still provides a VIP (virtual IP). Different machines in the cluster use the same IP address, but the MAC address of the machine is different. When the load balancing server receives the request, it rewrites the destination MAC address of the message and forwards the request to the target machine to achieve load balancing.

Three-tier load balancing

Similar to layer 2 load balancer, the load balancer server still provides a VIP (virtual IP), but different machines in the cluster use different IP addresses. When the load balancing server receives the request, it forwards the request to different real servers through IP according to different load balancing algorithms.

Four-tier load balancing

Layer 4 load balancing works in the transport layer of the OSI model. Because there is only TCP/UDP protocol in the transport layer, these two protocols include not only the source IP and the destination IP, but also the source port number and the destination port number. After receiving the request from the client, the layer-4 load balancer server forwards the traffic to the application server by modifying the address information (IP+ port number) of the packet.

Seven-tier load balancing

Layer 7 load balancer works in the application layer of the OSI model. There are many application layer protocols, such as http, radius, DNS and so on. Seven layers of load can be loaded based on these protocols. There will be a lot of meaningful content in these application layer protocols. For example, for the load balancer of the same Web server, in addition to load balancing based on IP plus port, you can also decide whether to load balancer based on URL, browser category and language at layer 7.

Figure: layer 4 and layer 7 load balancing

For general applications, Nginx is enough. Nginx can be used for layer 7 load balancer. However, for some large websites, DNS+ four-layer load + seven-layer load is generally used for multi-level load balancing.

Common load balancing tools

Hardware load balancing has superior performance and comprehensive functions, but it is expensive, so it is generally suitable for early or long-term use by Tuhao companies. Therefore, software load balancing is widely used in the Internet field. The commonly used software load balancing software includes Nginx, LVS, HaProxy and so on.

Nginx/LVS/HAProxy is the three most widely used load balancing software at present.

1 、 LVS

LVS (Linux Virtual Server), also known as Linux virtual server, is a free software project initiated by Dr. Zhang Wensong. The goal of using LVS technology is to achieve a high-performance, high-availability server cluster through the load balancing technology provided by LVS and the Linux operating system, which has good reliability, scalability and maneuverability. In order to achieve the optimal service performance at a low cost.

LVS is mainly used for layer 4 load balancing.

LVS architecture

The server cluster system set up by LVS consists of three parts: the front-end load balancing layer (Loader Balancer), the middle server group layer, represented by Server Array, and the lowest data sharing storage layer represented by Shared Storage. In the eyes of users, all applications are transparent, and users are just using the high-performance services provided by a virtual server.

A detailed description of the various levels of LVS:

Load Balancer layer: it is located at the front end of the whole cluster system and is composed of one or more load schedulers (Director Server). The LVS module is installed on Director Server, while the main function of Director is similar to a router. It contains routing tables set for completing the LVS function, through which users' requests are distributed to the application server (Real Server) in the Server Array layer. At the same time, the monitoring module Ldirectord for Real Server services should be installed on Director Server, which is used to monitor the health status of each Real Server service. Remove Real Server from the LVS routing table when it is not available and rejoin it when it is restored.

Server Array layer: consists of a group of machines that actually run application services. Real Server can be one or more of Web servers, Mail servers, FTP servers, DNS servers, and video servers. Each Real Server is connected by high-speed LAN or distributed WAN. In practical applications, Director Server can also act as Real Server at the same time.

Shared Storage layer: a storage area that provides shared storage space and content consistency for all Real Server. Physically, it is generally composed of disk array devices. In order to provide content consistency, data can be shared through the NFS network file system. However, the performance of NFS is not very good in busy business systems, so you can use cluster file systems, such as Red hat's GFS file system, OCFS2 file system provided by Oracle, and so on.

From the whole LVS structure, we can see that Director Server is the core of the whole LVS. At present, the operating system for Director Server can only be Linux and the FreeBSD,Linux2.6 kernel can support LVS functions without any settings, while there are not many applications of FreeBSD as Director Server, and the performance is not very good. For Real Server, it can be almost all system platforms, Linux, windows, Solaris, AIX, BSD series can well support.

2 、 Nginx

Nginx (pronounced engine x) is a web server that can reverse proxy protocol links for HTTP, HTTPS, SMTP, POP3, IMAP, as well as a load balancer and a HTTP cache.

Nginx is mainly used for layer 7 load balancing.

Concurrent performance: official support for 50, 000 concurrency per second, the actual domestic generally to 20, 000 concurrency per second, there are optimized to 100000 concurrency per second. The specific performance depends on the application scenario.

Features:

Modular design: good expansibility, can be expanded through the module way.

High reliability: the master process and worker are implemented synchronously. If there is a problem with one worker, another worker will be started immediately.

Low memory consumption: ten thousand long connections (keep-alive), consuming only 2.5MB memory.

Support hot deployment: do not stop the server, update the configuration file, change the log file, update the server program version.

Strong concurrency: official data support 50,000 concurrency per second

Feature-rich: excellent reverse proxy function and flexible load balancing strategy

The basic working mode of Nginx

A master process that generates one or more worker processes. But here master is started using the root identity, because nginx works on port 80. Only the administrator has permission to start ports less than 1023. Master is mainly responsible for starting worker, loading configuration files, and being responsible for the smooth upgrade of the system. The rest of the work is given to worker. When worker is started, it is only responsible for some of the simplest tasks of web, while the rest of the work is carried out by modules called in worker.

The function is realized by pipelining between modules. Pipeline, which refers to a user request, is completed by multiple modules combining their respective functions in turn. For example, the first module is only responsible for analyzing the first part of the request, the second module is only responsible for finding data, and the third module is only responsible for compressing data and completing their respective work in turn. To achieve the completion of the whole job.

How do they achieve hot deployment? Well, we said earlier that master is not responsible for the specific work, but calls the worker work, which is only responsible for reading the configuration file, so when a module is modified or the configuration file changes, it is read by master, so it will not affect the worker work at this time. After master reads the configuration file, worker is not immediately informed of the modified configuration file. Instead, let the modified worker continue to work with the old configuration file, and when the worker is finished, pawn the child process directly, replace the new child process, and use the new rules.

3 、 HAProxy

HAProxy is also a widely used load balancing software. HAProxy provides high availability, load balancing and agents based on TCP and HTTP applications, supports virtual hosts, and is a free, fast and reliable solution. It is especially suitable for those web sites with heavy load. The operating mode allows it to be easily and securely integrated into the current architecture while protecting your web server from being exposed to the network.

HAProxy is a free and open source software written in C language that provides high availability, load balancing, and TCP and HTTP-based application proxies.

Haproxy is mainly used for layer 7 load balancing.

Common load balancing algorithms

When introducing the load balancing technology above, it is mentioned that when the load balancing server decides which real server to forward the request to, it is realized through the load balancing algorithm. Load balancing algorithms can be divided into two categories: static load balancing algorithm and dynamic load balancing algorithm.

Static load balancing algorithms include: polling, ratio, priority.

Dynamic load balancing algorithms include: minimum number of connections, fastest response speed, observation method, prediction method, dynamic performance allocation, dynamic server supplement, quality of service, service type, rule pattern.

Polling (Round Robin): a sequential loop will request a sequential loop to connect to each server. When one of the servers fails from layer 2 to layer 7, BIG-IP takes it out of the sequential loop queue and does not participate in the next poll until it returns to normal.

Request to schedule different servers in turn by polling; when implemented, the server is generally weighted; this has two advantages:

Different loads can be distributed according to the differences in server performance.

When you need to weed out a node, you only need to set its weight to 0

Advantages: simple and efficient implementation; easy to scale horizontally

Disadvantages: the uncertainty of the request to the destination node makes it inapplicable to scenarios with writes (caching, database writes)

Application scenario: a read-only scenario in the database or application service layer

Random mode: requests are randomly distributed to each node; a balanced distribution can be achieved in scenarios where the data is large enough

Advantages: easy to implement and easy to scale horizontally

Disadvantages: same as Round Robin, cannot be used in scenarios with writing

Application scenario: database load balancing is also a read-only scenario

Hash method: calculate the nodes that need to fall according to key, which can guarantee that the same key must fall on the same server.

Pros: the same key must fall on the same node, so it can be used in cache scenarios with write and read

Disadvantages: after a node failure, it will lead to the redistribution of hash keys, resulting in a significant reduction in the hit rate.

Solution: consistent hash or uses keepalived to ensure the high availability of any node, and other nodes will come up after failure

Application scenarios: cache, read and write

Consistent hash: when a server node fails, only the key on that node is affected to maximize the hit rate, such as the ketama scheme in twemproxy. The specified sub-key hash can also be planned in the production implementation, so as to ensure that the keys with local similar features can be distributed on the same server.

Advantages: the drop of hit rate after node failure is limited.

Application scenarios: cach

Load according to the range of keys: according to the range of keys to load, the first 100 million keys are stored in the first server, 100 million to 200 million in the second node.

Advantages: it is easy to scale horizontally, and when there is not enough storage, add a server to store the new data.

Disadvantages: uneven load; uneven distribution of databases

(there is a distinction between hot and cold data, and recently registered users are generally more active, resulting in a very busy server and a lot of idle nodes in the previous period.)

Applicable scenario: database sharding load balancing

Load according to the number of key-pair server nodes: load according to the number of key-pair server nodes; for example, there are four servers, key module 0 falls on the first node, 1 falls on the second node.

Advantages: data hot and cold distribution balanced, database node load balanced distribution

Disadvantages: difficult to scale horizontally

Applicable scenario: database sharding load balancing

Pure dynamic node load balancing: decide how to schedule the next request according to the processing capacity of CPU, IO and network.

Advantages: make full use of the resources of the server to ensure load balance on each node

Disadvantages: complex to implement, less real use

No active load balancer: use the message queue to switch to an asynchronous model to eliminate the problem of load balancing; load balancing is a push model that sends data to you all the time, then all user requests are sent to the message queue, and all downstream nodes who are idle and who come up for data processing; after switching to the pull model, the problem of load on downlink nodes is eliminated.

Advantages: protect the back-end system through the buffering of the message queue, do not destroy the back-end server when the number of requests increases sharply; it is easy to scale horizontally, and after adding a new node, you can directly take queue.

Disadvantages: no real-time performance

Application scenarios: scenarios that do not need to be returned in real time

For example, after placing an order in 12036, immediately return the prompt message: your order is waiting in line. Notify asynchronously after the processing is finished.

Ratio (Ratio): each server is assigned a weighting value as a proportion, according to which user requests are assigned to each server. When one of the servers fails at layers 2 to 7, BIG-IP takes it out of the server queue and does not participate in the allocation of the next user request until it returns to normal.

Priority (Priority): all servers are grouped, priority is defined for each group, and requests from BIG-IP users are assigned to the highest priority server group (within the same group, polling or ratio algorithm is used to assign users' requests); when all servers in the highest priority fail, BIG-IP sends the request to the server group with lower priority. In this way, it actually provides a way of hot backup for users.

Minimum connection method (Least Connection): pass new connections to servers that do the least connection processing. When one of the servers fails at layers 2 to 7, BIG-IP takes it out of the server queue and does not participate in the allocation of the next user request until it returns to normal.

Fastest mode (Fastest): passes the connection to the server that responds most quickly. When one of the servers fails from layer 2 to layer 7, BIG-IP takes it out of the server queue and does not participate in the allocation of the next user request until it returns to normal.

Observation mode (Observed): the number of connections and response time are based on the best balance between the two items to select a server for new requests. When one of the servers fails from layer 2 to layer 7, BIG-IP takes it out of the server queue and does not participate in the allocation of the next user request until it returns to normal.

Prediction mode (Predictive): BIG-IP uses the current performance indicators of the collected server to carry out prediction analysis, and selects a server in the next time slot, its performance will reach the best server corresponding to the user's request. (detected by BIG-IP)

Dynamic performance allocation (Dynamic Ratio-APM): BIG-IP collects performance parameters of applications and application servers to dynamically adjust traffic allocation.

Dynamic server supplement (Dynamic Server Act.): dynamically replenish the backup server to the primary server farm when the number in the primary server farm decreases due to a failure.

Quality of service (QoS): data streams are assigned according to different priorities.

Type of service (ToS): data flows are allocated by load balancing according to different types of service (identified in Type of Field).

Rule mode: set guiding rules for different data streams, users can do so on their own.

Java implementation Code of several algorithms for load balancing

Polling

Weighted random load balancing algorithm

Random load balancing algorithm

Load balancing ip_hash algorithm.

Thank you for reading, the above is the content of "how to achieve load balancing algorithm in Java". After the study of this article, I believe you have a deeper understanding of how to achieve load balancing algorithm in Java, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.