Consider the scenario, an API gateway that distributes requests to multiple upstream nodes, as in the upstream configuration of nginx.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

upstream backend {
    server a1.com weight=5;
    server a2.com;
    server a3.com backup;
    server a4.com backup;
}

server {
    location / {
        proxy_pass http://backend;
    }
}

There are many common practices on how to distribute the routes / equally to the four services, in general, such as randomized algorithms, etc.

Random

Treat each node as an element of an array, and for each request calculate a random number, e.g. calculate a random number from 1-4 and take the modulus, e.g.

1
2
3

hosts := []string{"a1.com","a2.com","a3.com","a4.com"}
x := random(1,4) % len(hosts)
proxyPass(x)

Then we directly take hosts[x] as the object of the distribution request. Therefore, we only need to ensure that this random algorithm is random enough to achieve balanced distribution.

Polling

In addition to random, polling can be used to achieve random assignment, e.g.

1
2
3
4
5
6
7

hosts :=  []string{"a1.com","a2.com","a3.com","a4.com"}
cursor := 0

for {
    cursor ++ 
    proxyPass(hosts[cursor % len(hosts)])
}

This approach maintains a cursor that points to which node was last hit, and then sequentially polls the next node in the array.

Directed Distribution

Some scenarios, requests for the same IP (or other fields) need to be forwarded to the same node, this way an IP needs to be transformed into a number and mapped to an array subscript, like this scenario, a crc32 algorithm can be used to map a string to a number and then modulo that number.

1
2
3

hosts :=  []string{"a1.com","a2.com","a3.com","a4.com"}
x := crc32(ip) % len(hosts)
proxyPass(hosts[x])

If we consider that each IP access is random in terms of data distribution, then this approach can be used to implement the LB function.

All of these methods above are relatively common and easy to think of solutions. Based on these balancing strategies, some more business-friendly variants, such as weighting, can also be implemented. In ordinary business scenarios, these methods should be sufficient to meet business needs. The only problem that may arise is that if a node goes down during a process, this situation will cause a portion of the requests to still be forwarded to the failed node. To solve this problem, the mechanism of live detection has emerged.

Heartbeat Detection

To ensure service availability, a heartbeat detection mechanism from LB to node can be maintained, with each node providing an interface. For example:

1
2
3

func Alive(ctx *gin.Context) {
    ctx.String(http.StatusOK, "ok")
}

Then LB accesses this interface every time, say 10ms, and the service is considered normal only if it returns normally, and when the service is abnormal, it needs to be removed from the hosts list. In this way, combined with the several load balancing strategies mentioned above, it greatly increases the service availability when the node hangs. All of the above, however, are solutions for stateless services.

For a stateful service, such as ws long connection service, data storage service, etc., then such node downtime will lead to data loss. Therefore, it is necessary to do data synchronization when the node of a stateful service has a problem. And if we use the above random algorithm approach, we have to recalculate the original data and land on the remaining nodes, this kind of performance may not be guaranteed for a large distributed system, so another strategy of data synchronization needs to be improved, such as consistent hashing.

Consistent Hashing

First, first define as a ring data structure, such as an array or LinkedList, and here assume a ring array with 16 elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

type VNode struct {
    idx int
    server string
}

// arr
var nodes = make([]*Vnode, 0)
for i:=0;i<16;1++ {
    nodes = append(nodes,&VNode{idx:i,server:""})
}

Next, bind specific Host and Vnode nodes, such as binding the following nodes.

1
2
3
4
5
6

func initVNode() {
    nodes[0].server = "a1.com"
    nodes[4].server = "a2.com"
    nodes[8].server = "a3.com"
    nodes[12].server = "a4.com"
}

When a request comes through, we get a number based on a random number, or IP, or other field that can be identified. For example.

1

(Assumptions ) vNodeId = crc32(request_id) % 16 = 3

At this point, find the first node with binding from the ring array according to clockwise (counterclockwise is also possible) and use it as the node for load balancing.

1
2
3
4
5
6
7
8

func FindService(vNodeId int) string {
    for i:=vNodeId;i<vNodeId + 16;i++ {
        if nodes[i % 16].server != "" {
            return nodes[i % 16].server
        }
    }
    return ""
}

When a node in the system hangs, it is necessary to do data migration, at this time, assuming that a3.com is down, it is only necessary to transfer all the data of the original a3.com to a4.com, which means that all the data of the original a3.com is transferred to a4.com. This process only involves moving from a3.com to a4.com, other nodes are not affected. However, if this is a simple forward transfer, it is found that the data is not evenly distributed and a4.com directly carries 50% of the data, so to improve it, the distribution of physical nodes to multiple nodes on the ring can be used.

1
2
3
4
5
6
7
8
9

func initVNode() {
    nodes[0].server = "a1.com"
    nodes[1].server = "a2.com"
    nodes[4].server = "a2.com"
    nodes[5].server = "a3.com"
    nodes[8].server = "a3.com"
    nodes[12].server = "a4.com"
    nodes[14].server = "a4.com"
}

This way, when nodes are migrated, they can be spread more evenly to the remaining nodes. Of course, consistent hashing is designed to minimize the cost of data synchronization and recovery when a node hangs in a distributed environment, thus improving overall high availability.

Nginx’s Load Balancing Strategy

Nginx implements several load balancing strategies, such as polling, which polls each node according to request time and automatically listens to keep it alive.

1
2
3
4

upstream backserver {
    server 10.0.2.16;
    server 10.0.2.17;
}

Weighted assignments can also be specified to request the corresponding nodes in proportion to their weights.

1
2
3
4

upstream backserver {
    server 10.0.2.16 weight=3;
    server 10.0.2.17 weight=7;
}

It can also be distributed in a targeted manner, such as ip_hash.

1
2
3
4
5

upstream backserver {
    ip_hash;
    server 10.0.2.16;
    server 10.0.2.17;
}

SRV records

SRV is a type of DNS record that supports load balancing on DNS resolution. SRV supports specifying IP, port, and weight information on the record, so it can also be used for cluster load balancing.

The DNS “service” (SRV) record specifies a host and port for specific services such as voice over IP (VoIP), instant messaging, and so on. Most other DNS record only specify a server or an IP address, but SRV records include a port at that IP address as well. Some Internet protocols require the use of SRV records in order to function.

An SRV record has the following format.

1
2
3
4
5
6

format: Service type. Transport protocol. Host/Domain TTL IN/OUT SRV Priority Weight Target Port Target Host/Target Domain

example:

_xmpp._tcp.example.com. 86400 IN SRV 10 5 5223 server0.example.com.
_xmpp._tcp.example.com. 86400 IN SRV 10 4 5224 server1.example.com.

That is, if you visit example.com, it will resolve to the target port of the target domain by weight and priority.