Algorithmes de load balancing : chacun repare le defaut du precedent

Repartir des requetes sur une poignee de serveurs sonne comme le probleme le plus trivial des systemes distribues. Vous avez trois backends et une requete ; en choisir un, l'envoyer, fini. Un seul appel a rand.Intn(3) et vous avez un load balancer. En production.

Ca marche jusqu'a ce que la realite se pointe. Un backend tourne sur une machine plus grosse que les autres. Une requete prend cinq secondes quand les autres prennent cinq millisecondes. Un client doit atterrir sur le meme serveur a chaque fois parce que c'est la que vit sa session. Un backend meurt discretement et votre balancer parfaitement aleatoire continue joyeusement de lui envoyer un tiers du trafic. Chacun de ces cas est une facon differente dont la reponse naive casse, et chaque algorithme classique de load balancing est une reponse a une casse precise.

Ceci n'est donc pas une liste de six algorithmes. C'est une chaine. On part de la chose la plus simple qui marche, on la regarde echouer, et on saisit l'algorithme suivant precisement parce qu'il repare ce que le precedent ne pouvait pas. Le Go pour le code, mais la progression est le sujet. Tout pend a une seule interface :

// Un Balancer choisit le backend qui doit servir la prochaine requete.
type Balancer interface {
    Next(r *Request) *Backend
}

type Backend struct {
    URL         string
    Weight      int          // capacite relative, pour les schemas ponderes
    ActiveConns int64        // requetes en cours, pour least-connections
    Healthy     bool
}

Round robin : le point de depart honnete

Le premier vrai algorithme apres "choisir au hasard" est le round robin : donner chaque requete au backend suivant dans l'ordre, en repartant du debut a la fin. Chaque serveur a un tour egal, dans une rotation previsible.

type RoundRobin struct {
    backends []*Backend
    counter  uint64
}

func (rr *RoundRobin) Next(_ *Request) *Backend {
    // increment atomique pour que des appelants concurrents aient chacun un slot distinct
    n := atomic.AddUint64(&rr.counter, 1)
    return rr.backends[n%uint64(len(rr.backends))]
}

Ce atomic.AddUint64 compte : un load balancer est martele par de nombreuses goroutines a la fois, et un simple counter++ ferait une race et donnerait le meme index a deux appelants. Avec l'atomique, le round robin est correct, sans verrou, et a peu pres aussi bon marche qu'un dispatch peut l'etre.

Le round robin fait une promesse et la tient : au fil du temps, chaque backend recoit le meme nombre de requetes. L'ennui est qu'egal n'est pas la meme chose qu'equitable. Le round robin suppose que chaque serveur est identique et que chaque requete coute pareil, et les deux hypotheses sont d'habitude fausses. Envoyez le meme nombre de requetes a une machine 16 coeurs et a une 2 coeurs et vous en avez surcharge une pendant que l'autre tourne au ralenti. Cet ecart entre egal et equitable est le defaut que l'algorithme suivant existe pour reparer.

Round robin pondere : quand les serveurs ne sont pas egaux

Si un backend peut encaisser trois fois la charge d'un autre, il devrait recevoir trois fois le trafic. Attachez un poids a chaque serveur et repartissez en proportion.

L'implementation evidente est d'etendre la liste, en repetant chaque backend autant de fois que son poids, et de faire du round robin dessus. Ca marche, mais ca cluster : un serveur de poids 3 recoit trois requetes en rafale, puis rien, ce qui pique la charge au lieu de la lisser. La version qu'utilisent les vrais proxies est le smooth weighted round robin (c'est l'algorithme de Nginx), qui entrelace les choix pour qu'un serveur de poids 3 soit reparti uniformement dans la rotation plutot qu'entasse.

type SmoothWRR struct {
    backends []*Backend
    current  []int // "credit" courant par backend
    mu       sync.Mutex
}

func (w *SmoothWRR) Next(_ *Request) *Backend {
    w.mu.Lock()
    defer w.mu.Unlock()

    total := 0
    best := -1
    for i, b := range w.backends {
        w.current[i] += b.Weight // chaque backend gagne son poids en credit
        total += b.Weight
        if best == -1 || w.current[i] > w.current[best] {
            best = i // le backend le plus credite gagne ce tour
        }
    }
    w.current[best] -= total // et rembourse
    return w.backends[best]
}

Chaque backend accumule un credit egal a son poids a chaque tour ; celui qui a le plus de credit est choisi puis se voit facturer le poids total en retour. Sur un cycle complet un serveur de poids 3 gagne trois fois plus souvent, mais les gains sont repartis, pas entasses. Les pics ont disparu.

Le round robin pondere repare les differences de capacite statiques. Ce qu'il ne peut pas voir, c'est la charge dynamique. Les poids sont configures a l'avance et ne changent jamais, donc si un "petit" serveur attrape par hasard une rafale de requetes lentes, le round robin pondere continue de le nourrir a son rythme configure, aveugle au fait qu'il se noie a l'instant present. Les poids decrivent la capacite en theorie, pas la charge dans l'instant.

Least connections : reagir a la charge reelle

Pour repondre a ce qui se passe vraiment, cessez de compter les tours et commencez a compter le travail en cours. Least connections route chaque requete vers le backend qui a le moins de connexions actives, donc un serveur englue par des requetes lentes cesse naturellement d'en recevoir de nouvelles le temps de rattraper.

func (lc *LeastConn) Next(_ *Request) *Backend {
    var best *Backend
    min := int64(math.MaxInt64)
    for _, b := range lc.backends {
        c := atomic.LoadInt64(&b.ActiveConns)
        if c < min {
            min, best = c, b
        }
    }
    return best // l'appelant incremente ActiveConns, decremente a la fin de la requete
}

Cela s'adapte a la realite d'une facon que le round robin ne pourra jamais. Des durees de requete inegales, un backend qui passe une mauvaise minute, un downstream lent : least connections contourne tout cela automatiquement, car un serveur en difficulte accumule des connexions et tombe en fin de file. C'est le premier algorithme ici qui reagit a la charge au lieu de la supposer.

Le cout est dans cette boucle. Pour choisir le minimum, least connections scanne chaque backend a chaque requete, ce qui va pour une poignee de serveurs et fait mal pour des centaines. Pire, sous forte concurrence, le lire-puis-router fait une race : de nombreuses goroutines observent toutes le meme backend le moins charge au meme instant et le stampedent ensemble, precisement le desequilibre que l'algorithme devait empecher. Lire un etat global pour prendre une decision locale ne passe pas a l'echelle.

Power of two choices : l'astuce que personne n'enseigne

Voici l'algorithme qui devrait etre bien plus celebre qu'il ne l'est. Au lieu de scanner tous les backends pour le vrai minimum, choisissez deux backends au hasard et routez vers le moins charge des deux. C'est toute l'idee.

func (p *P2C) Next(_ *Request) *Backend {
    a := p.backends[rand.Intn(len(p.backends))]
    b := p.backends[rand.Intn(len(p.backends))]
    // comparer seulement ces deux-la, pas toute la flotte
    if atomic.LoadInt64(&a.ActiveConns) <= atomic.LoadInt64(&b.ActiveConns) {
        return a
    }
    return b
}

Ca a l'air trop simple pour etre bon, et le resultat est vraiment surprenant : n'echantillonner que deux et prendre le meilleur donne une repartition de charge presque aussi egale que scanner toute la flotte, a un cout O(1) au lieu de O(N). Le resultat mathematique derriere (le theoreme "power of two choices") montre que la charge maximale entre serveurs chute exponentiellement par rapport au pur aleatoire, et qu'un seul echantillon de plus achete presque tout ce benefice. Et comme deux goroutines echantillonnent rarement la meme paire, le probleme de troupeau qui plombait least connections s'evapore en grande partie.

Ce n'est pas un jouet. Power of two choices est ce vers quoi les systemes de production se tournent vraiment : c'est le defaut dans les versions recentes de HAProxy, dans le Finagle de Twitter, dans le load balancing d'Envoy. C'est le point d'equilibre de toute la progression, une qualite quasi globale a cout local, et la plupart des tutos passent droit devant. Si vous retenez un algorithme de cet article, retenez celui-la.

IP hash : quand le client doit rester colle

Tout ce qui precede suppose que n'importe quel backend peut servir n'importe quelle requete. Parfois c'est faux : un client a une session, un cache, ou un upload en cours lie a un serveur precis, et il doit y revenir. La reponse classique est de hasher l'IP du client et de l'utiliser pour choisir un backend de facon deterministe.

func (h *IPHash) Next(r *Request) *Backend {
    sum := fnv.New32a()
    sum.Write([]byte(r.ClientIP))
    return h.backends[sum.Sum32()%uint32(len(h.backends))]
}

Meme IP, meme hash, meme backend, a chaque fois. Les sessions restent epinglees. C'est propre et ca marche, et ca cache un piege qui ne se declenche que lorsque vous changez le pool. Ce % len(backends) est tout le probleme : des l'instant ou vous ajoutez ou retirez un seul serveur, N change, et presque tous les clients hashent soudain vers un backend different. Chaque session casse, chaque cache devient froid, d'un coup, pour un changement d'un seul serveur. Le hachage naif est stable seulement tant que le pool ne change jamais, ce qui n'est pas une propriete des vrais systemes.

Consistent hashing : la stabilite dans le changement

La solution est de hasher serveurs et clients sur un meme anneau abstrait, un espace de, disons, 0 a 2^32, et de marcher dans le sens horaire depuis la position du client jusqu'au premier serveur sur l'anneau. Ajoutez ou retirez un serveur et seules les cles dans l'arc de ce serveur bougent ; tous les autres restent en place.

type Ring struct {
    sorted []uint32          // positions de hash, triees
    owner  map[uint32]*Backend
}

func (r *Ring) Next(req *Request) *Backend {
    h := hash(req.ClientIP)
    // recherche binaire de la premiere position >= h, avec wrap
    i := sort.Search(len(r.sorted), func(i int) bool { return r.sorted[i] >= h })
    if i == len(r.sorted) {
        i = 0 // au-dela de la fin de l'anneau, on repart au debut
    }
    return r.owner[r.sorted[i]]
}

Avec le hachage naif, retirer un serveur sur N remappe a peu pres toutes les cles. Avec le consistent hashing, il en remappe seulement environ K/N, celles qui vivaient dans l'arc du serveur parti. En pratique on ajoute aussi des noeuds virtuels, en hashant chaque backend vers de nombreuses positions sur l'anneau au lieu d'une seule, pour que la charge se repartisse uniformement et qu'aucun serveur ne possede un arc geant par accident. C'est la meme structure derriere les caches distribues et le sharding par hash : le consistent hashing est moins une astuce de load balancing qu'une reponse generale a "assigner des cles a des noeuds pour qu'ajouter un noeud ne derange presque rien".

La panne qu'aucun algorithme ne repare : les serveurs morts

Prenez du recul et remarquez ce que chaque algorithme ci-dessus suppose discretement : que le backend qu'il choisit est vivant. Le round robin routera consciencieusement un tiers de votre trafic vers un serveur mort il y a trente secondes. Power of two choices echantillonnera un cadavre. Le consistent hashing epinglera un client a un backend qui a cesse de repondre. Un algorithme de selection impeccable pointe vers un serveur mort renvoie des erreurs aussi fidelement qu'il renverrait des succes.

Un vrai load balancer a donc besoin d'une couche qu'aucun de ces algorithmes ne fournit : savoir quels backends sont reellement debout. Deux approches, d'habitude combinees :

• Health checks actifs. Sonder periodiquement chaque backend (un GET /healthz sur un timer). Le marquer malsain en cas d'echec, le retirer du pool, et continuer a le sonder pour qu'il puisse revenir en se retablissant.
• Health checks passifs. Observer le trafic reel. Si un backend commence a renvoyer des erreurs ou a timeouter, l'ejecter sans attendre la prochaine sonde. C'est la version load balancer d'un circuit breaker.

func (rr *RoundRobin) Next(_ *Request) *Backend {
    for i := 0; i < len(rr.backends); i++ {
        n := atomic.AddUint64(&rr.counter, 1)
        b := rr.backends[n%uint64(len(rr.backends))]
        if b.Healthy { // sauter les backends ejectes, essayer le slot suivant
            return b
        }
    }
    return nil // tout le pool est down ; l'appelant doit shed ou echouer vite
}

Cela boucle avec le reste de la boite a outils de resilience. L'ejection par health check est le cousin cote selection-de-serveur du circuit breaker qu'un client utilise pour cesser d'appeler une dependance morte, et il se tient a cote du rate limiting qui deleste la charge qu'un service ne peut servir. Le load balancing est la troisieme face de la meme piece : le rate limiting decide combien un serveur prend, les retries decident quand un client envoie, et le load balancing decide quel serveur le recoit. Rendez la selection parfaite et sautez les health checks, et vous avez construit une facon tres equitable de repartir la panne.

La chaine, en un coup d'oeil

Aucun n'est "le meilleur". Chacun est la bonne reponse a une pression precise, et chacun a ete saisi parce que le precedent a heurte un mur.

A retenir

• Commencez plus simple que vous ne le croyez necessaire. Pour une petite flotte de serveurs similaires avec des requetes similaires, le round robin ou meme le pur aleatoire va vraiment bien. N'allez plus loin que lorsqu'un vrai defaut mord.
• Egal n'est pas equitable. Utilisez des poids quand les serveurs different en capacite, et des comptes de connexions quand les requetes different en cout. Le round robin melange les deux et est aveugle aux deux.
• Power of two choices est le point d'equilibre sous-estime. Une qualite de charge quasi globale a cout O(1), sans le scan ni le troupeau de least-connections. C'est ce qu'utilisent les vrais proxies, et c'est a un appel rand de distance.
• Le hachage naif casse des que le pool change. Si vous avez besoin d'un routage colle, utilisez le consistent hashing avec noeuds virtuels, ou acceptez qu'ajouter un serveur refroidira le cache de tous.
• Le meilleur algorithme de selection route quand meme vers des serveurs morts. Les health checks et l'ejection ne sont pas du vernis optionnel ; ils sont la couche qui fait reellement marcher chaque algorithme ci-dessus en production.

La lecon de toute la chaine est que le "load balancing" n'est pas un probleme avec une reponse. C'est une suite de pressions de plus en plus precises, capacite, charge en direct, cout, stickiness, churn, panne, et chaque algorithme classique est l'outil qui repond a exactement l'une d'elles. Savoir quelle pression vous avez reellement, c'est l'essentiel de savoir quel algorithme choisir.