I. Design and Implementation of Scalable Network Services

1.         Requirements for Network Services

With the rapid development of the Internet and its deep impact on our lives, the number of Internet users and network traffic are growing geometrically, which places high demands on the scalability of network services. In addition, as critical applications such as e-commerce run on the Internet, any exceptional service interruption will cause incalculable losses, and the high availability of services is becoming increasingly important. Therefore, the demand for implementing highly scalable and highly available network services through hardware and software methods continues to grow. This demand can be summarized as follows:

• Scalability: when the service load grows, the system can be expanded to meet the demand without degrading service quality.

• Availability: even if some hardware and software fail, the service of the entire system must be available 24 hours a day, 7 days a week.

• Manageability: the entire system may be physically large, but it should be easy to manage.

• Cost-effectiveness: the implementation of the entire system is economical and affordable.

A single server obviously cannot handle continuously growing loads. This server upgrade method has the following disadvantages:

First, the upgrade process is cumbersome; machine switching will temporarily interrupt services and cause waste of existing computing resources;

Second, the higher-end the server, the greater the cost;

Third, once the server or application software fails, it will cause interruption of the entire service.

In response to the above requirements, we present load balancing scheduling solutions based on the IP layer and on content-based request distribution, and have implemented these methods in the Linux kernel, forming a group of servers into a server cluster that realizes scalable, highly available network services. We call it the Linux Virtual Server (LVS). In an LVS cluster, the structure of the server cluster is transparent to clients; clients access the network services provided by the cluster just as they would access a single high-performance, highly available server. Client programs are not affected by the server cluster and do not need any modification. The scalability of the system is achieved by transparently adding and removing a node in the server cluster, and high availability is achieved by detecting node or service process failures and correctly resetting the system.

   2.     LVS Cluster's General Architecture

LVS cluster adopts IP load balancing technology and content-based request distribution technology. The scheduler has good throughput, evenly transfers requests to different servers for execution, and automatically shields server failures, thereby forming a group of servers into a high-performance, highly available virtual server.

Figure 1.1: Architecture of LVS Cluster

To this end, the design must consider the transparency, scalability, high availability, and manageability of the system. The architecture of the LVS cluster is shown in Figure 1.1, and it has three main components:

• Load balancer: it is the front-end machine of the entire cluster facing the outside, responsible for sending client requests to a group of servers for execution, while clients believe the service comes from one IP address. It can be a load balancer using IP load balancing technology, a load balancer based on content-based request distribution, or a combination of both.

• Server pool: a group of servers that actually execute client requests; the services they run include WEB, MAIL, FTP, DNS, etc.

• Backend storage: it provides a shared storage area for the server pool, making it easy for the server pool to have the same content and provide the same services.

The scheduler adopts IP load balancing technology, content-based request distribution technology, or a combination of both. In IP load balancing technology, the server pool is required to have the same content and provide the same services. When a client request arrives, the scheduler selects a server from the server pool based only on the load situation, forwards the request to the selected server, and records this scheduling; when other packets of this request arrive, they are also forwarded to the previously selected server. In content-based request distribution technology, servers can provide different services. When a client request arrives, the scheduler can select a server to execute the request based on the request content and the server situation. Because all operations are completed in the operating system kernel space, its scheduling overhead is very small, so it has very high throughput.

The number of nodes in the server pool is variable. When the load received by the entire system exceeds the processing capacity of all current nodes, servers can be added to the server pool to meet the continuously growing request load. For most network services, there is no strong correlation between nodes, so the performance of the entire system can grow linearly with the increase in the number of nodes in the server pool.

Backend storage usually uses fault-tolerant distributed file systems, such as AFS, GFS, Coda, Intermezzo, etc. Distributed file systems provide a shared storage area for each server; they access the distributed file system just like accessing a local file system. At the same time, distributed file systems provide good scalability and availability.

II. IP Load Balancing Technology

This chapter will describe the working principles of three IP load balancing technologies: VS/NAT, VS/TUN, and VS/DR, as well as their advantages and disadvantages. In the following description, we refer to the data communication between a client socket and a server socket as a connection, regardless of whether they use the TCP or UDP protocol.

1.         Virtual Server via NAT (VS/NAT)

Due to the increasing scarcity of IPv4 address space and security reasons, many networks use reserved IP addresses (10.0.0.0/255.0.0.0, 172.16.0.0/255.128.0.0, and 192.168.0.0/255.255.0.0) [64, 65, 66]. These addresses are not used on the Internet, but are reserved specifically for internal networks. When hosts in an internal network need to access the Internet or be accessed from the Internet, Network Address Translation (NAT) must be used to translate internal addresses into external addresses usable on the Internet. The working principle of NAT is that after the packet header (destination address, source address, port, etc.) is correctly rewritten, clients believe they are connected to one IP address, and the server group with different IP addresses also believes it is directly connected to the clients. Thus, the NAT method can turn parallel network services at different IP addresses into a virtual service at one IP address.

VS/NAT architecture is shown in Figure 3.1. There is a scheduler in front of a group of servers, which are connected through a Switch/HUB. These servers provide the same network services and the same content, that is, regardless of which server the request is sent to, the execution result is the same. The service content can be copied to the local hard disk of each server, shared through a network file system (such as NFS), or provided through a distributed file system.

Figure 3.1: Architecture of VS/NAT

When a client accesses a network service through the Virtual IP Address (the IP address of the virtual service), the request packet arrives at the scheduler. The scheduler selects a server from a group of real servers according to the connection scheduling algorithm, rewrites the packet's destination address Virtual IP Address to the address of the selected server, rewrites the packet's destination port to the corresponding port of the selected server, and finally sends the modified packet to the selected server. At the same time, the scheduler records this connection in a connection hash table. When the next packet of this connection arrives, the address and port of the originally selected server can be obtained from the connection hash table, the same rewriting operation is performed, and the packet is passed to the originally selected server. When a response packet from a real server passes through the scheduler, the scheduler changes the packet's source address and source port to the Virtual IP Address and corresponding port, and then sends the packet to the user. We introduce a state machine on the connection. Different packets will cause the connection to be in different states, and different states have different timeout values. In a TCP connection, state transitions are performed according to the standard TCP finite state machine; in UDP, we set only one UDP state. The timeout values for different states are configurable. By default, the timeout of the SYN state is 1 minute, the timeout of the ESTABLISHED state is 15 minutes, and the timeout of the FIN state is 1 minute; the timeout of the UDP state is 5 minutes. When the connection terminates or times out, the scheduler deletes this connection from the connection hash table.

In this way, what the client sees is only the service provided on the Virtual IP Address, and the structure of the server cluster is transparent to the user. For rewritten packets, an incremental checksum adjustment algorithm is applied to adjust the TCP Checksum value, avoiding the overhead of scanning the entire packet to calculate the Checksum.

In some network services, they transmit IP addresses or port numbers in the packet data. If we only translate the IP address and port number in the packet header, inconsistency will occur and the service will be interrupted. Therefore, for these services, corresponding application modules need to be written to translate the IP address or port number in the packet data. The network services we know with this problem include FTP, IRC, H.323, CUSeeMe, Real Audio, Real Video, Vxtreme / Vosiac, VDOLive, VIVOActive, True Speech, RSTP, PPTP, StreamWorks, NTT AudioLink, NTT SoftwareVision, Yamaha MIDPlug, iChat Pager, Quake, and Diablo.

2.         Virtual Server via IP Tunneling (VS/TUN)

In the VS/NAT cluster system, both request and response data packets need to pass through the load balancer. When the number of real servers is between 10 and 20, the load balancer will become a new bottleneck for the entire cluster system. Most Internet services have the following characteristic: request packets are relatively short, while response packets often contain a large amount of data. If requests and responses can be processed separately, that is, the load balancer is only responsible for scheduling requests while responses are returned directly to clients, the throughput of the entire cluster system will be greatly improved.

IP tunneling is a technology that encapsulates one IP packet in another IP packet, which allows a data packet destined for one IP address to be encapsulated and forwarded to another IP address. IP tunneling technology is also called IP encapsulation. IP tunneling is mainly used for mobile hosts and virtual private networks (Virtual Private Network), in which tunnels are statically established, with one IP address at one end of the tunnel and a unique IP address at the other end.

We use IP tunneling technology to encapsulate and forward request packets to backend servers, and response packets can be returned directly from the backend servers to clients. However, here there is a group of backend servers rather than one, so it is impossible to statically establish one-to-one tunnels; instead, a server is dynamically selected, and the request packet is encapsulated and forwarded to the selected server. In this way, we can use the principle of IP tunneling to combine network services on a group of servers into a virtual network service at one IP address. The architecture of VS/TUN is shown in Figure 3.3, and each server configures the VIP address on its own IP tunnel device.

Figure 3.3: Architecture of VS/TUN

3.         Virtual Server via Direct Routing (VS/DR)

Like the VS/TUN method, VS/DR utilizes the asymmetric characteristics of most Internet services. The load balancer is only responsible for scheduling requests, while servers return responses directly to clients, which can greatly improve the throughput of the entire cluster system. This method is similar to the method used in IBM's NetDispatcher product, but IBM's NetDispatcher is a very expensive commercial product, and we do not know the mechanism used internally; some of it is patented by IBM.

VS/DR architecture is shown in Figure 3.6: both the scheduler and the server group must physically have a network card connected through a non-segmented local area network, that is, connected through a switch or a high-speed HUB, with no router in between. The VIP address is shared by the scheduler and the server group. The VIP address configured on the scheduler is externally visible and is used to receive request packets for the virtual service; all servers configure the VIP address on their respective non-ARP network devices, which are invisible to the outside and are only used to process network requests whose destination address is the VIP.

Figure 3.6: Architecture of VS/DR

VS/DR load balancer is also only in the half-connection from the client to the server, and performs state transitions according to the TCP finite state machine of the half-connection.

4.         Comparison of Advantages and Disadvantages of the Three Methods

The advantages and disadvantages of the three IP load balancing technologies are summarized in the following table:

VS/NAT-----When the number of servers rises to a certain level, the load balancer is prone to becoming a bottleneck; throughput is low.

    VS/TUN-------relatively large throughput.

    VS/DR---------relatively large throughput.

Note: The estimates of the maximum number of servers supported by the above three methods assume that the scheduler uses a 100M network card, the hardware configuration of the scheduler is the same as that of the backend servers, and the service is general Web service. If a higher hardware configuration (such as a gigabit network card and a faster processor) is used as the scheduler, the number of servers that the scheduler can schedule will increase accordingly. When applications differ, the number of servers will also change accordingly. Therefore, the above data estimates are mainly for a quantitative comparison of the scalability of the three methods.

a)  Virtual Server via NAT

VS/NAT advantage is that the servers can run any operating system that supports TCP/IP. It requires only one IP address configured on the scheduler, and the server group can use private IP addresses. The disadvantage is that its scalability is limited. When the number of server nodes rises to 20, the scheduler itself may become a new bottleneck for the system, because in VS/NAT both request and response packets need to pass through the load balancer.

b)  Virtual Server via IP Tunneling

In the VS/TUN cluster system, the load balancer only schedules requests to different backend servers, and the backend servers return the response data directly to users. In this way, the load balancer can handle a large number of requests; it can even schedule more than a hundred servers (of comparable scale), and it will not become a bottleneck for the system. Even if the load balancer has only a 100Mbps full-duplex network card, the maximum throughput of the entire system can exceed 1Gbps. Therefore, VS/TUN can greatly increase the number of servers scheduled by the load balancer. The VS/TUN scheduler can schedule hundreds of servers without itself becoming a bottleneck, and can be used to build high-performance super servers.

VS/TUN technology has requirements for servers, namely, all servers must support the "IP Tunneling" or "IP Encapsulation" protocol. Currently, the backend servers of VS/TUN mainly run the Linux operating system, and we have not tested other operating systems. Because "IP Tunneling" is becoming a standard protocol for various operating systems, VS/TUN should also be applicable to backend servers running other operating systems.

c)  Virtual Server via Direct Routing

Like the VS/TUN method, the VS/DR scheduler only handles connections from clients to servers, and response data can be returned directly to clients through an independent network route. This can greatly improve the scalability of the LVS cluster system. Compared with VS/TUN, this method has no IP tunneling overhead, but it requires that both the load balancer and the actual servers have a network card connected to the same physical network segment, and the server network device (or device alias) does not respond to ARP, or can redirect packets to a local Socket port.

III. Load Scheduling Algorithms

How to efficiently distribute requests through the load balancer to different servers for execution, so that a cluster system composed of multiple independent computers becomes one virtual server; when a client application interacts with the cluster system, it is like interacting with one high-performance server.

How to schedule request flows to each server so that each server maintains load balance as much as possible. Various connection scheduling algorithms implemented by IPVS in the kernel;

In the following description, we refer to the data communication between a client socket and a server socket as a connection, regardless of whether they use the TCP or UDP protocol. For scheduling UDP datagrams, the IPVS scheduler will also establish a scheduling record and set a timeout value (such as 5 minutes); within the set time, UDP packets from the same address (IP address and port) will be scheduled to the same server.

Eight scheduling algorithms (rr, wrr, lc, wlc, lblc, lblcr, dh, sh)

V. Content-Based Request Distribution in the Kernel KTCPVS

Because the overhead of a user-space TCP Gateway is too large, its scalability is limited. To this end, we propose implementing a Layer-7 switching method in the operating system kernel to avoid the overhead of switching between user space and kernel space and the overhead of memory copying. In the Linux operating system kernel, we implemented Layer-7 switching, called KTCPVS (Kernel TCP Virtual Server). The following subsections will introduce the architecture, implementation methods, load balancing, and high-availability features of KTCPVS.

1.         KTCPVS Architecture

KTCPVS cluster architecture is shown in Figure 6.3: it mainly consists of two components. One is the KTCPVS switch, which sends requests to different servers according to different content; the other is the backend servers, which can run different network services. The KTCPVS switch and backend servers are interconnected through LAN/WAN.

Figure 6.3: Architecture of KTCPVS Cluster

KTCPVS switch can perform content-based scheduling, sending different types of requests to different backend servers, and then returning the results to clients. The backend servers are invisible to clients. Therefore, the structure of the KTCPVS cluster is transparent to clients; clients access the network services provided by the cluster just as they would access a single high-performance, highly available server, so we also call it a virtual server. Client programs are not affected by the server cluster and do not need any modification.