Illustration:
FROM What Is Load Balancing? How Load Balancers Work
Before the introduction:
Originally intended Dragon Boat Festival hair. But a few days ago is really eager to rest empty brain, drag down. One more thing is that the class library itself doesn’t have time to evaluate what it forgot to do.
But all of a sudden it doesn’t matter, and now it’s done.
primers
Load balancing is widely used in various orchestration systems, microservice gateways, Nginx/HAProxy as the front site cluster and so on. Load balancing takes on a different look in more areas that you can’t see, and even in places that you can’t imagine and have never noticed, such as mechanical hard disks, read and write access to hard disk groups, pipeline allocation of multi-core cpus, and so on.
Therefore, load balancing technology, aiming at optimizing resource utilization, maximizing throughput, minimizing access delay and preventing overload, has various manifestations.
The basic feature of load balancing is to schedule input to different computing units. Therefore, when a computing unit fails, the load balancer can select the working unit and avoid the failed unit. When the unit recovers, the load balancer can also correctly schedule requests to this unit. This transparent and unperceived failover feature is often mentioned in conjunction with load balancing. For example, the company has three private lines. It doesn’t matter which one is broken. There are always good lines for us to export to the cloud for maintenance.
On the Internet, the most basic service, the DNS service, has automatic load balancing capability. As long as your domain name has multiple A records to indicate the servers of A particular IP, these server farms can evenly receive input requests and provide service.
The DNS service, however, has little advantage in the failover feature, limiting its possible advanced use. Because of this, we do a large site cluster, the front part must be several nginx made of the front proxy, after the DNS load balancing, still need a redundant layer of load balancer, because this can effectively mask the changes in the business server farm (up and down).
In addition to using legacy software load balancers such as Nginx /HAProxy, companies with money can also use dedicated hardware load balancers.
Orchestration software such as K8s proactively provides multiple forms of load balancing to expose nodes and services in its private network as the view shrinks to business server farms.
In fact, THE overall cost of K8s may be too high (extra server and computing resource requirements, extra operation and maintenance management requirements, etc.), you may be naked on the cloud server, whether it is self-developed service governance or using well-known frameworks such as Micro or Kong, they also provide load balancing scheduling capabilities.
Regardless of these microservice architectures, this small comprehensive DNS cluster can also provide enhanced load balancing capabilities when you use consul converged with a private DNS server, but may require some architectural design and encoding adaptation.
All this should not obscure the conclusion that there will always be value in using software to implement load balancing algorithms. Because when you have a system architecture of a certain size and complexity that requires scheduling capabilities, that requires amortization of request latency, that requires dial-and-conquer map-reduce, you will often need to hand out a little load balancing scheduler, whatever it may look like.
Hence, this set of articles.
There are countless articles, papers, or source code on load balancing, but this set of articles exists because none of them are mine. Mine, mine. So,
Basic load balancing algorithm
From a comprehensive perspective, there are at least the most basic load balancing algorithms:
- random
- polling
- Minimum number of connections
- hash
- Polling with weights
Below do a brief introduction in turn, finally to review again.
Pre-introduction
I’ve always loved coding, pure coding. So let’s start with some basic interface Settings:
type Peer interface {
String() string
}
type Factor interface {
Factor() string
}
type BalancerLite interface {
Next(factor Factor) (next Peer, c Constrainable)
}
type Balancer interface {
BalancerLite
/ /... more
}
type FactorComparable interface {
Factor
ConstrainedBy(constraints interface{}) (peer Peer, c Constrainable, satisfied bool)}type FactorString string
func (s FactorString) Factor(a) string { return string(s) }
const DummyFactor FactorString = ""
type Constrainable interface {
CanConstrain(o interface{}) (yes bool)
Check(o interface{}) (satisfied bool)
Peer
}
Copy the codeIn order not to get bogged down in design details, I have outlined the highlights:
PeerIt’s a rear node.- Load balancer
BalancerHolds a set of Peers. Factor是BalancerIn the selection,Next(factor)) a reference object provided by the dispatcher when Peer,BalancerMay be used as a factor in how the selection algorithm works.- When you’re a scheduler and you want to call Next, but there’s no proper “factor” to provide, just provide it
DummyFactorAll right. ConstrainableThere may be another introduction at the end of this series, but ignore it for now.
Random algorithm
As the name suggests, picking any one from a list of back ends is a random algorithm. It is the simplest, combined with our pre-prompts, please understand the following example:
package main
import (
"fmt"
"github.com/hedzr/lb/lbapi"
mrand "math/rand"
"sync"
"sync/atomic"
"time"
)
type randomS struct {
peers []lbapi.Peer
count int64
}
func (s *randomS) Next(factor lbapi.Factor) (next lbapi.Peer, c lbapi.Constraintenable) {
l := int64(len(s.peers))
ni := atomic.AddInt64(&s.count, inRange(0, l)) % l
next = s.peers[ni]
return
}
func main(a) {
lb := &randomS{
peers: []lbapi.Peer{
exP("172.16.0.7:3500"), exP("172.16.0.8:3500"), exP("172.16.0.9:3500"),
},
count: 0,
}
sum := make(map[lbapi.Peer]int)
for i := 0; i < 300; i++ {
p, _ := lb.Next(lbapi.DummyFactor)
sum[p]++
}
for k, v := range sum {
fmt.Printf("%v: %v\n", k, v)
}
}
var seededRand = mrand.New(mrand.NewSource(time.Now().UnixNano()))
var seedmu sync.Mutex
func inRange(min, max int64) int64 {
seedmu.Lock()
defer seedmu.Unlock()
return seededRand.Int63n(max-min) + min
}
type exP string
func (s exP) String(a) string { return string(s) }
Copy the codeRandomS implements a miniature, simple LB of random algorithms.
Although I could have simplified it to just a few lines of code snippets, the example is a bit long and somewhat irrelevant in order to be able to make it live & runnable or a slightly added salt.
The result might be:
$go run./_examples/simple/random/ 172.16.0.8:35:116 172.16.0.7:35:94 172.16.0.9:35:90Copy the codeWell, the random number generator should be uniform, the order of magnitude should be 5K, or even 100K to make sense. So it’s not evenly divided here, it’s pretty much ok.
regularization
Note that the formal Random LB code is a little more complex than the core above. The reason is that there are two other design goals we need to achieve:
- Thread safety
- Can be nested
Because random LB’s key algorithm is no more than three lines:
l := int64(len(s.peers))
ni := atomic.AddInt64(&s.count, inRange(0, l)) % l
next = s.peers[ni]
Copy the codeThat’s why I have a little space to simply provide the official version of the code, which looks almost like this:
package random
import (
"github.com/hedzr/lb/lbapi"
mrand "math/rand"
"sync"
"sync/atomic"
"time"
)
var seededRand = mrand.New(mrand.NewSource(time.Now().UnixNano()))
var seedmu sync.Mutex
func inRange(min, max int64) int64 {
seedmu.Lock()
defer seedmu.Unlock()
return seededRand.Int63n(max-min) + min
}
// New make a new load-balancer instance with Round-Robin
func New(opts ... lbapi.Opt) lbapi.Balancer {
return (&randomS{}).init(opts...)
}
type randomS struct {
peers []lbapi.Peer
count int64
rw sync.RWMutex
}
func (s *randomS) init(opts ... lbapi.Opt) *randomS {
for _, opt := range opts {
opt(s)
}
return s
}
func (s *randomS) Next(factor lbapi.Factor) (next lbapi.Peer, c lbapi.Constraintenable) {
next = s.miniNext()
if fc, ok := factor.(lbapi.FactorComparable); ok {
next, c, ok = fc.ConstraintBy(next)
} else if nested, ok := next.(lbapi.BalancerLite); ok {
next, c = nested.Next(factor)
}
return
}
func (s *randomS) miniNext(a) (next lbapi.Peer) {
s.rw.RLock()
defer s.rw.RUnlock()
l := int64(len(s.peers))
ni := atomic.AddInt64(&s.count, inRange(0, l)) % l
next = s.peers[ni]
return
}
func (s *randomS) Count(a) int {
s.rw.RLock()
defer s.rw.RUnlock()
return len(s.peers)
}
func (s *randomS) Add(peers ... lbapi.Peer) {
for _, p := range peers {
s.AddOne(p)
}
}
func (s *randomS) AddOne(peer lbapi.Peer) {
if s.find(peer) {
return
}
s.rw.Lock()
defer s.rw.Unlock()
s.peers = append(s.peers, peer)
}
func (s *randomS) find(peer lbapi.Peer) (found bool) {
s.rw.RLock()
defer s.rw.RUnlock()
for _, p := range s.peers {
if lbapi.DeepEqual(p, peer) {
return true}}return
}
func (s *randomS) Remove(peer lbapi.Peer) {
s.rw.Lock()
defer s.rw.Unlock()
for i, p := range s.peers {
if lbapi.DeepEqual(p, peer) {
s.peers = append(s.peers[0:i], s.peers[i+1:]...).return}}}func (s *randomS) Clear(a) {
s.rw.Lock()
defer s.rw.Unlock()
s.peers = nil
}
Copy the codeThis should show how hot the #%$&#%@ code is
For once, there won’t be any down there.
The polling algorithm is round-robin
You probably don’t really know who Robin is.
It’s really nobody. Originally it was a French word ruban, which means Ribbon Ribbon. But time washed everything away, and somehow, it became Robin.
The term round-robin is derived from the French term ruban, meaning “ribbon”. Over a long period of time, the term was corrupted and idiomized to robin.
– Round – robin tournament
Round and ruban comes from the round and ruban system, which is also known as round robin. As for the round robin letter mentioned in the Chinese version of Wiki, you may also want to take a look. Of course, as far as Robin is concerned, that’s pure leisure time.
Well, none of that matters. The important thing is that the polling algorithm is to select a peer one by one. That’s it.
So the core of the algorithm looks something like this:
func (s *rrS) miniNext(a) (next lbapi.Peer) {
ni := atomic.AddInt64(&s.count, 1)
ni %= int64(len(s.peers))
next = s.peers[ni]
return
}
Copy the codeS. mount increments continuously without modulo. This is intended to make the final selection more ambiguous if the array of peers is added or subdivided by a small amount.
For Golang, s. ount comes to int64.maxValue and continues to loop to 0. This feature, like most major compiled languages, is a basic feature provided by the CPU.
Minimum number of Connections Least Connections
If the activity on a back-end service has the fewest connections of all the back-end services, then it is selected.
This algorithm is not instantiated, because many times managing the number of active connections is an unusual chore, a hassle, and consumes extra resources – this resource is not a fact-add or mod – so it’s not really used much outside of professional proxy servers like Nginx.
As long as your system manages its back-end connection count properly, implementing a Least Connections LB is no algorithmic problem.
Hashing and Consistent Hashing
review
In the early years, when microservices were not distinguished from individual applications, load balancing with Hash algorithms was often treated as a magic trick, because session retention was often the key factor that prevented horizontal growth of a service. When scheduling Hash values for users’ session-IDS, This ensures that the session of the source user of the same session-ID always falls on a certain backend server, thus ensuring that its session is always valid.
After the Hash algorithm has been extended, it’s obvious that you can use client IP values, host names, urls, or whatever you want to Hash, as long as you get hashCode, you can apply the Hash algorithm. Since identifiers such as client IP and client host name have the same hashCode, the corresponding back-end peer can also be consistent, which is why the Hash algorithm in session years is important.
Next year, the government will not use the Browser session mode, but instead will use the stateless model, so the hash algorithm is actually a bit lonely.
The essence of the stateless model is to include a token in the header, which can be expanded into an identity for user login, equivalent to the Browser session. After all, the original intent of stateless models, such as JWT, is to scale server farms horizontally.
Later, in 1997, Karger of MIT published an algorithm paper called consistent Hashing, which differs from the traditional hashCode calculation in that, on the one hand, hashCode is constrained to a positive integer (INT32 /uint32/ INT64, etc.). On the one hand, positive integer space [0, int.MaxValue] is regarded as a loopable Ring, namely the so-called Hash Ring, and peers to be selected are evenly distributed on this Ring, thus ensuring that each peer can be selected smoothly every time.
There is no limit to the subscript calculation at the time of selection, so you can add an alternative strategy to the subscript calculation scheme.
In the consistent Hash algorithm in the field of load balancing, Replica factor is added, which actually adds an index number suffix to the host name of the Peer when calculating the Hash value of the Peer, and adds the Replica number to the index number. Then a replica of the peer is obtained. This expands the scale of peers from N to N x Replica, which helps to further improve the smoothness of selection.
Code implementation
So with all that said, the core of the algorithm looks something like this:
type Hasher func(data []byte) uint32
// hashS is a impl with ketama consist hash algor
type hashS struct {
hasher Hasher // default is crc32.ChecksumIEEE
replica int // default is 32
hashRing []uint32
keys map[uint32]lbapi.Peer
peers map[lbapi.Peer]bool
rw sync.RWMutex
}
func (s *hashS) Next(factor lbapi.Factor) (next lbapi.Peer, c lbapi.Constraintenable) {
var hash uint32
hash = s.hasher([]byte(factor.Factor()))
ix := sort.Search(len(s.hashRing), func(i int) bool {
return s.hashRing[i] >= hash
})
if ix == len(s.hashRing) {
ix = 0
}
hashValue := s.hashRing[ix]
if p, ok := s.keys[hashValue]; ok {
if _, ok = s.peers[p]; ok {
next = p
}
}
return
}
func (s *hashS) Add(peers ... lbapi.Peer) {
for _, p := range peers {
s.peers[p] = true
for i := 0; i < s.replica; i++ {
hash := s.hasher(s.peerToBinaryID(p, i))
s.hashRing = append(s.hashRing, hash)
s.keys[hash] = p
}
}
sort.Slice(s.hashRing, func(i, j int) bool {
return s.hashRing[i] < s.hashRing[j]
})
}
func (s *hashS) peerToBinaryID(p lbapi.Peer, replica int) []byte {
str := fmt.Sprintf("%v-%05d", p, replica)
return []byte(str)
}
Copy the codeThe Add implementation establishes a hashRing structure, which is a ring, but in the form of an array and subscript modulo. In addition, the keys map resolves the mapping from the hash value of a peer to a peer, and in the future (in Next) it will be possible to pick a point from a hashRing and get the corresponding peer immediately.
In Next, we mainly calculate the hash value of factor. The result of calculation is mapped to a point pt on hashRing. If there is not exactly a peer hit, the peer closest to PT is scanned backwards.
The algorithm idea is summarized
In fact, I’m not going to write this paragraph, because other people’s pictures are really nice ah, speak thoroughly.
Take this picture for example:
FROM Wayne’s Blog – System Design 101 – Consistent Hashing
Keynote, drool. I’m really going to learn it.
If you’re interested in every detail of the algorithm, check out these two videos:
- Consistent Hashing – Georgia Tech – Network Congestion
- A Brief Introduction to Consistent Hashing
Previously, we mentioned Replica, which is a method to create virtual nodes of peers on hashRing. This idea is to maximize the problem of uneven and smooth selection results caused by changes of peers. It basically came from libketama, a memcached library, so in most cases the same idea is called the Ketama Hashing algorithm. You can refer to it here.
Weighted round-robin
Adding weights is a very important feature. So in the basic LB algorithm section we need to use weighted Polling (WRR) as an example.
The weighted polling algorithm adds a weight to each peer and adds this weight on the basis of average polling as adjustment.
The most famous implementation of the weighted polling algorithm is Nginx and LVS.
Nginx smooth weighted polling
Nginx uses a balancing method based on the difference between total and each weight: For each selection, add currentWeight to each node, select the node with the highest currentWeight, and restore the node’s currentWeight to the increment before subtracting its weight. With this repeated selection, heavier nodes are selected more often due to faster increments.
The idea of this algorithm can be mathematically proved rigorously, but I won’t go into that, but the core implementation:
func (s *wrrS) Next(a) (best lbapi.Peer) {
total := 0
for _, node := range s.peers {
if node == nil {
continue
}
total += s.mUpdate(node, 0.false)
if s.mTest(best, node) {
best = node
}
}
ifbest ! =nil {
s.mUpdate(best, -total, true)}return
}
func (s *wrrS) mUpdate(node lbapi.Peer, delta int, success bool) (total int) {
if delta == 0 {
delta = s.m[node].weight
}
s.m[node].current += delta
return s.m[node].weight
}
func (s *wrrS) mTest(best, node lbapi.Peer) bool {
return best == nil || s.m[node].current > s.m[best].current
}
Copy the codeThe above code has been refined, but the actual code is a little more complicated because we also need to do the lock operation.
LVS smooth weighted polling
As for the weighted polling method of LVS, the core idea is to adopt GCD (greatest common divisor).
/* Supposing that there is a server set S = {S0, S1,... , Sn-1}; W(Si) indicates the weight of Si; i indicates the server selected last time, and i is initialized with -1; cw is the current weight in scheduling, and cw is initialized with zero; max(S) is the maximum weight of all the servers in S; gcd(S) is the greatest common divisor of all server weights in S; * /
while (true) {
i = (i + 1) mod n;
if (i == 0) {
cw = cw - gcd(S);
if (cw <= 0) {
cw = max(S);
if (cw == 0)
return NULL; }}if (W(Si) >= cw)
return Si;
}
Copy the codeYou can think of it this way: For three nodes A, B, and C, weighted x,y, and z, imagine an array filled x times A,y times B, and z times C, and then polling the array. Is the final ratio of selections sufficient for the weight assignment?
In fact, I did this with my first WRR implementation many years ago, and was annoyed by the weight, until I saw the introduction of the LVS algorithm one day and said, “This is Ben.”
summary
The main basic LB algorithms have been explained above.
These basic algorithms can be further combined and evolved, for example
- Weighted stochastic algorithm
- (Request) Source Hash
- Destination Hash
- Weighted minimum number of connections algorithm
- , etc.
We want to do this in the new class library, so further code design and reorganization will be required. For reasons of space, we’ll talk about what kind of thinking goes into making a library next time.
:end: