Dimensionnez un système à plusieurs serveurs

Le trafic de votre API a triplé : elle reçoit maintenant 24 requêtes par seconde. Un serveur ne suffit plus, il en faut plusieurs. Mais combien ? Et vaut-il mieux trois serveurs indépendants avec chacun sa file, trois serveurs qui partagent une file commune, ou une seule machine trois fois plus puissante ?

Ce chapitre étend la file M/M/1 à plusieurs serveurs. Vous y trouverez les deux formules que tout ingénieur réseau connaît, Erlang C pour les systèmes où l’on attend et Erlang B pour ceux où l’on refuse les clients, et vous apprendrez à choisir un nombre de serveurs. Nous suivrons l’API à trois répliques, puis un cluster de GPU qui refuse les tâches quand il est plein.

La file M/M/s : plusieurs serveurs, une file commune

Dans une file M/M/s, les clients arrivent selon un Poisson de taux $\lambda$ et patientent dans une file unique ; dès qu’un des $s$ serveurs se libère, il prend le premier client en attente. Chaque service dure un temps exponentiel de taux $\mu$.

Le nombre de clients présents est encore un processus de naissance et de mort. Les arrivées ont toujours lieu au taux $\lambda_n = \lambda$. Pour les départs, tout dépend du nombre de serveurs occupés : avec $n$ clients présents, $\min(n, s)$ serveurs travaillent, et le premier service se termine au taux

$$\mu_n = \min(n, s)\,\mu.$$

Le graphe de la M/M/3 de l'API : les arrivées se font toujours au taux 24, mais le taux de départ croît avec le nombre de serveurs occupés (10, 20, 30) puis plafonne à 30 dès que les trois serveurs sont pris.

Deux notations reviennent sans cesse :

• $u = \lambda/\mu$ est le trafic offert, exprimé en erlangs : le nombre moyen de serveurs qu’il faudrait occuper en permanence pour absorber la demande ;
• $\rho = u/s = \lambda/(s\mu)$ est l’intensité de trafic par serveur, c’est-à-dire le taux d’occupation moyen de chaque serveur.

Piège

Dans une M/M/s, la charge qui compte pour la stabilité est $\rho = \lambda/(s\mu)$, et non $\lambda/\mu$. Pour notre API, $\lambda/\mu = 2{,}4$ : ce nombre supérieur à 1 ne signifie pas que le système est instable, mais qu’il faut au moins 3 serveurs.

La formule du chapitre 6 donne les $\gamma_n$ :

$$\Pi_n = \frac{u^n}{n!}\,\Pi_0 \quad (n < s), \qquad \Pi_n = \frac{u^n}{s!\, s^{n-s}}\,\Pi_0 \quad (n \geq s).$$

Tant que $n < s$, chaque nouveau client trouve un serveur libre ; au-delà, on retombe sur une géométrique de raison $\rho$. La série converge si et seulement si $\rho < 1$, et la normalisation donne

$$\Pi_0 = \left(\sum_{n=0}^{s-1} \frac{u^n}{n!} + \frac{u^s}{s!\,(1 - \rho)}\right)^{-1}.$$

Erlang C : la probabilité d’attendre

La question pratique est : quelle proportion de clients doit attendre ? Un client attend s’il trouve les $s$ serveurs occupés, c’est-à-dire au moins $s$ clients présents. En sommant la géométrique, on obtient la formule d’Erlang C :

$$C(s, u) = P(\text{attendre}) = \sum_{n \geq s} \Pi_n = \frac{u^s}{s!\,(1 - \rho)}\,\Pi_0.$$

On en déduit tous les indicateurs :

• nombre moyen de clients en attente : $\bar N_q = \dfrac{\rho\, C(s, u)}{1 - \rho}$ ;
• nombre moyen de clients en service : $u = s\rho$ (autant de serveurs occupés, en moyenne, que le trafic offert) ;
• temps moyen d’attente, par la loi de Little : $\bar W_q = \bar N_q/\lambda$ ;
• temps moyen de séjour : $\bar W = \bar W_q + 1/\mu$.

Exemple

L’API reçoit $\lambda = 24$ requêtes par seconde, servies par $s = 3$ répliques de taux $\mu = 10$. Alors $u = 2{,}4$ et $\rho = 0{,}8$.

• $\sum_{n=0}^{2} u^n/n! = 1 + 2{,}4 + 2{,}88 = 6{,}28$ et $\dfrac{u^3}{3!\,(1 - 0{,}8)} = \dfrac{13{,}824}{1{,}2} = 11{,}52$, donc $\Pi_0 = 1/17{,}8 \approx 0{,}056$.
• Erlang C : $C = 11{,}52 \times 0{,}056 \approx 0{,}647$. Près de deux requêtes sur trois doivent attendre.
• $\bar N_q = 0{,}8 \times 0{,}647/0{,}2 \approx 2{,}59$ requêtes en attente, donc $\bar W_q = 2{,}59/24 \approx 0{,}108$ s.
• Temps de séjour moyen : $\bar W \approx 0{,}108 + 0{,}1 = 0{,}208$ s.

Avec une quatrième réplique ($\rho = 0{,}6$), la probabilité d’attendre tombe à 0,287 et le séjour moyen à 0,118 s.

La loi du nombre de requêtes présentes dans la M/M/3 : tant qu'un serveur est libre (en vert), personne n'attend. Les barres violettes, où les trois serveurs sont occupés, totalisent la probabilité d'attendre C ≈ 0,647.

Mutualiser ou grossir ? Trois architectures comparées

Revenons à la question de l’introduction. Pour le même trafic ($\lambda = 24$) et la même capacité totale (30 requêtes par seconde), comparons trois architectures, toutes chargées à 80 % :

Architecture	Modèle	Attente moyenne	Séjour moyen
3 serveurs, chacun sa file (trafic réparti au hasard)	3 × M/M/1 ($\lambda = 8$, $\mu = 10$)	0,400 s	0,500 s
3 serveurs, une file commune	M/M/3 ($\lambda = 24$, $\mu = 10$)	0,108 s	0,208 s
1 serveur trois fois plus rapide	M/M/1 ($\lambda = 24$, $\mu = 30$)	0,133 s	0,167 s

Pour la première ligne, la décomposition d’un Poisson (chapitre 7) donne à chaque serveur un Poisson de taux 8, et on retrouve l’API du chapitre 8.

Même trafic, même capacité totale. Avec des files séparées, un serveur peut rester inoccupé pendant qu'on attend devant son voisin (séjour 0,500 s) ; la file commune évite ce gâchis (0,208 s) ; le serveur unique rapide fait encore mieux en séjour (0,167 s), mais une panne arrête tout.

Deux leçons en ressortent :

• Mutualiser la file est un gain énorme : le temps de séjour est divisé par plus de deux. Avec des files séparées, un serveur peut rester inoccupé pendant qu’une requête attend devant son voisin ; avec une file commune, jamais. C’est pour cela que les bureaux de poste et les répartiteurs de charge (load balancers) utilisent une file unique, ou au moins envoient la requête au serveur le moins chargé.
• Un serveur rapide bat plusieurs serveurs lents en temps de séjour, parce que chaque service est trois fois plus court. En revanche, on y attend un peu plus, et une panne arrête tout. Le choix final dépend donc aussi de la tolérance aux pannes.

À retenir

Dans une M/M/s, le nombre de serveurs occupés suit $\mu_n = \min(n, s)\mu$ ; le système est stable si $\rho = \lambda/(s\mu) < 1$. La formule d’Erlang C donne la probabilité d’attendre, puis la loi de Little donne les temps moyens. À capacité égale, une file commune est bien meilleure que des files séparées.

M/M/∞ : chacun son serveur

À la limite $s \to \infty$, il y a toujours un serveur libre : personne n’attend jamais. On a $\lambda_n = \lambda$ et $\mu_n = n\mu$, et le chapitre 6 nous a déjà donné la réponse :

$$\Pi_n = e^{-u}\,\frac{u^n}{n!}, \qquad n = 0, 1, 2, \dots$$

Le nombre de clients présents suit une loi de Poisson de paramètre $u = \lambda/\mu$, et le régime stationnaire existe toujours. Ce modèle décrit les situations où chacun « se sert lui-même » : les sessions ouvertes sur un site web, les voitures sur une portion d’autoroute fluide, les utilisateurs connectés à un service de visioconférence. Si 2 utilisateurs se connectent par minute et restent en moyenne 15 minutes, le nombre de sessions simultanées suit une loi de Poisson de moyenne 30 et d’écart-type $\sqrt{30} \approx 5{,}5$ ; la probabilité de dépasser 40 sessions simultanées vaut environ 3 %.

Dans une M/M/∞, le nombre de sessions suit une loi de Poisson de moyenne 30 : la plupart du temps entre 25 et 35, mais plus de 40 environ 3 % du temps (en rose).

M/M/s/s : le système à perte et la formule d’Erlang B

Changeons de décor. Un cluster de calcul possède $s$ GPU. Chaque tâche en occupe un ; si tous sont occupés, la tâche est refusée (l’utilisateur devra la resoumettre plus tard). Il n’y a aucune file d’attente : la capacité totale est égale au nombre de serveurs. C’est la file M/M/s/s, dite système à perte. C’est aussi le modèle historique des centraux téléphoniques : quand toutes les lignes sont prises, l’appel est rejeté.

Le nombre de tâches en cours est un processus de naissance et de mort sur $\lbrace 0, \dots, s \rbrace$, avec $\lambda_n = \lambda$ pour $n < s$ et $\mu_n = n\mu$. C’est la M/M/∞ tronquée à $s$ :

$$\Pi_n = \frac{u^n/n!}{\sum_{i=0}^{s} u^i/i!}, \qquad 0 \leq n \leq s.$$

L’espace étant fini, le régime stationnaire existe toujours, même si $u > s$. La grandeur clé est la probabilité de perte, la probabilité qu’une tâche arrive quand les $s$ GPU sont occupés. C’est la formule d’Erlang B :

$$B(s, u) = \Pi_s = \frac{u^s/s!}{\sum_{i=0}^{s} u^i/i!}.$$

Attention

Dans la notation M/M/s/s, le dernier $s$ est la capacité totale (en service et en attente), pas la taille de la salle d’attente. Capacité $s$ avec $s$ serveurs signifie donc zéro place d’attente. Ne confondez pas Erlang B (système à perte, on refuse) et Erlang C (système à attente, on patiente).

Exemple

Le cluster reçoit en moyenne 24 tâches par heure, d’une durée moyenne de 6 minutes ($\mu = 10$ par heure), soit $u = 2{,}4$ erlangs. Voici la probabilité de refus selon le nombre de GPU :

GPU $s$	3	4	5	6	7
Probabilité de refus $B(s; 2{,}4)$	26,8 %	13,9 %	6,2 %	2,4 %	0,8 %

Il faut 7 GPU pour refuser moins de 1 % des tâches, alors que le trafic moyen n’en occupe que 2,4. Là encore, la marge sert à absorber les fluctuations.

La probabilité de refus (Erlang B) chute vite avec le nombre de GPU, mais il faut en aligner 7, presque trois fois le trafic offert de 2,4 erlangs, pour passer sous l'objectif de 1 %.

En pratique, on calcule Erlang B par une récurrence numériquement stable, qui évite les grandes factorielles :

$$B(0, u) = 1, \qquad B(s, u) = \frac{u\,B(s-1, u)}{s + u\,B(s-1, u)}.$$

import math

def erlang_b(s, u):
    """Probabilité de perte d'une M/M/s/s de trafic offert u (récurrence stable)."""
    b = 1.0
    for k in range(1, s + 1):
        b = u * b / (k + u * b)
    return b

def erlang_c(s, u):
    """Probabilité d'attendre dans une M/M/s (exige u < s)."""
    rho = u / s
    b = erlang_b(s, u)
    return b / (1 - rho + rho * b)          # lien classique entre Erlang B et C

def mms(lam, mu, s):
    """Indicateurs d'une M/M/s : P(attendre), attente et séjour moyens."""
    u = lam / mu
    c = erlang_c(s, u)
    nq = (u / s) * c / (1 - u / s)
    wq = nq / lam                            # loi de Little sur la salle d'attente
    return c, wq, wq + 1 / mu

print(mms(24, 10, 3))                        # ≈ (0.647, 0.108, 0.208)
print([round(erlang_b(s, 2.4), 3) for s in range(3, 8)])
# [0.268, 0.139, 0.062, 0.024, 0.008]

# Plus petit nombre de GPU pour moins de 1 % de refus
s = 1
while erlang_b(s, 2.4) > 0.01:
    s += 1
print(s)                                     # 7

En entretien

« Pour dimensionner un pool de serveurs, je calcule le trafic offert $u = \lambda/\mu$ en erlangs. Si les clients attendent, j’utilise Erlang C pour la probabilité d’attente et Little pour les temps ; s’ils sont rejetés, Erlang B pour la probabilité de perte. Dans les deux cas, il faut sensiblement plus de serveurs que $u$. »

En résumé

• M/M/s : $\lambda_n = \lambda$, $\mu_n = \min(n, s)\mu$ ; trafic offert $u = \lambda/\mu$, intensité $\rho = u/s$ ; stable si $\rho < 1$.
• Erlang C : $C(s, u) = \dfrac{u^s}{s!(1-\rho)}\Pi_0$ est la probabilité d’attendre ; $\bar N_q = \rho C/(1-\rho)$, $u$ serveurs occupés en moyenne, puis Little pour $\bar W_q$ et $\bar W$.
• À capacité égale, une file commune à $s$ serveurs est bien meilleure que $s$ files séparées ; un serveur unique plus rapide donne un séjour plus court mais concentre le risque de panne.
• M/M/∞ : personne n’attend, le nombre de clients suit une loi de Poisson de paramètre $u$.
• M/M/s/s (système à perte, sans attente) : la probabilité de refus est donnée par Erlang B, $B(s, u) = \dfrac{u^s/s!}{\sum_{i \leq s} u^i/i!}$, qu’on calcule par récurrence.

Exercices

Exercice · Un standard téléphonique

facile

Un petit standard dispose de 3 lignes. Les appels arrivent au rythme de 4 par heure et durent en moyenne 30 minutes. Un appel qui arrive quand les trois lignes sont occupées est perdu. Quelle proportion d’appels est perdue ? Combien de lignes sont occupées en moyenne ?

Voir la solution

C’est une M/M/3/3 de trafic offert $u = \lambda/\mu = 4 \times 0{,}5 = 2$ erlangs. Par la formule d’Erlang B :

$$B(3, 2) = \frac{2^3/3!}{1 + 2 + 2^2/2 + 2^3/3!} = \frac{4/3}{1 + 2 + 2 + 4/3} = \frac{4/3}{19/3} = \frac{4}{19} \approx 0{,}21.$$

Environ 21 % des appels sont perdus. Les appels acceptés arrivent au taux $\lambda(1 - B) = 4 \times 15/19$ par heure et durent 0,5 h : par Little, le nombre moyen de lignes occupées vaut $4 \times \tfrac{15}{19} \times 0{,}5 = \tfrac{30}{19} \approx 1{,}58$.

En code

Python

def erlang_b(s, u):
    b = 1.0
    for k in range(1, s + 1):
        b = u * b / (k + u * b)
    return b

lam, duree = 4, 0.5                       # appels par heure, durée moyenne (h)
u = lam * duree
B = erlang_b(3, u)
print(B, 4 / 19)                          # 0.2105 0.2105 : appels perdus
print(lam * (1 - B) * duree)              # 1.579 lignes occupées (loi de Little)

R

erlang_b <- function(s, u) {
  b <- 1
  for (k in seq_len(s)) b <- u * b / (k + u * b)
  b
}
lam <- 4; duree <- 0.5                  # appels par heure, durée moyenne (h)
u <- lam * duree
B <- erlang_b(3, u)
c(B, 4 / 19)                            # 0.2105 0.2105 : appels perdus
lam * (1 - B) * duree                   # 1.579 lignes occupées (loi de Little)

Exercice · Deux serveurs lents ou un rapide ?

moyen

Un service reçoit $\lambda = 8$ requêtes par seconde. On hésite entre deux serveurs de taux $\mu = 5$ partageant une file commune (M/M/2) et un seul serveur de taux $\mu = 10$ (M/M/1).

1. Vérifiez que les deux configurations ont la même charge.
2. Pour la M/M/2, calculez $\Pi_0$, la probabilité d’attendre, l’attente moyenne et le séjour moyen.
3. Comparez avec la M/M/1 et concluez.

Voir la solution

1. M/M/2 : $\rho = 8/(2 \times 5) = 0{,}8$. M/M/1 : $\rho = 8/10 = 0{,}8$. Même charge.
2. $u = 8/5 = 1{,}6$. $\Pi_0 = \left(1 + 1{,}6 + \dfrac{1{,}6^2}{2 \times 0{,}2}\right)^{-1} = (1 + 1{,}6 + 6{,}4)^{-1} = 1/9 \approx 0{,}111$. Erlang C : $C = 6{,}4/9 \approx 0{,}711$. $\bar N_q = 0{,}8 \times 0{,}711/0{,}2 \approx 2{,}84$, donc $\bar W_q = 2{,}84/8 \approx 0{,}356$ s et $\bar W = 0{,}356 + 0{,}2 \approx 0{,}556$ s.
3. La M/M/1 donne $\bar W_q = 0{,}4$ s et $\bar W = 0{,}5$ s. On attend un peu moins avec deux serveurs lents, mais le séjour total est plus long, car chaque service dure 0,2 s au lieu de 0,1 s. Si seul le temps de réponse compte, le serveur rapide l’emporte ; si la disponibilité en cas de panne compte, deux serveurs sont plus sûrs.

En code

Python

import math

def mms(lam, mu, s):
    """P0, P(attendre), attente et séjour moyens d'une M/M/s."""
    u, rho = lam / mu, lam / (s * mu)
    queue = u**s / (math.factorial(s) * (1 - rho))
    p0 = 1 / (sum(u**n / math.factorial(n) for n in range(s)) + queue)
    c = queue * p0                        # Erlang C
    wq = rho * c / (1 - rho) / lam        # Little sur la salle d'attente
    return p0, c, wq, wq + 1 / mu

print([round(x, 3) for x in mms(8, 5, 2)])    # [0.111, 0.711, 0.356, 0.556]
print([round(x, 3) for x in mms(8, 10, 1)])   # [0.2, 0.8, 0.4, 0.5]

R

mms <- function(lam, mu, s) {           # P0, P(attendre), attente et séjour moyens
  u <- lam / mu; rho <- lam / (s * mu)
  file <- u^s / (factorial(s) * (1 - rho))
  p0 <- 1 / (sum(u^(0:(s - 1)) / factorial(0:(s - 1))) + file)
  c_attente <- file * p0                # Erlang C
  wq <- rho * c_attente / (1 - rho) / lam   # Little sur la salle d'attente
  round(c(p0 = p0, C = c_attente, Wq = wq, W = wq + 1 / mu), 3)
}
mms(8, 5, 2)                            # p0 0.111  C 0.711  Wq 0.356  W 0.556
mms(8, 10, 1)                           # p0 0.2    C 0.8    Wq 0.4    W 0.5

Exercice · Un tampon vidé d'un seul coup

difficile

Un capteur envoie des paquets vers un tampon de capacité $K = 10$ paquets, selon un Poisson de taux $\lambda = 100$ paquets par seconde. Le tampon est vidé entièrement, d’un seul coup, à des instants qui forment un Poisson de taux $\mu$. Un paquet qui arrive quand le tampon est plein est perdu.

1. Le nombre de paquets dans le tampon est-il un processus de naissance et de mort ? Écrivez les taux de transition.
2. Montrez que $\Pi_n = \dfrac{\mu}{\lambda + \mu}\left(\dfrac{\lambda}{\lambda + \mu}\right)^n$ pour $n < K$ et $\Pi_K = \left(\dfrac{\lambda}{\lambda + \mu}\right)^K$.
3. Quel taux de vidage $\mu$ faut-il pour perdre moins d’un paquet sur mille ?
4. Si le tampon était vidé périodiquement, toutes les $T$ secondes exactement, le modèle resterait-il markovien ?

Voir la solution

1. Non : un vidage fait passer de $n$ à 0 d’un coup, pas à $n - 1$. C’est bien une chaîne de Markov à temps continu, mais pas un processus de naissance et de mort. Les taux sont $n \to n+1$ au taux $\lambda$ (pour $n < K$) et $n \to 0$ au taux $\mu$ (pour $n \geq 1$).
2. Balance globale de l’état $n$ avec $1 \leq n < K$ : on en sort au taux $\lambda + \mu$ et on y entre seulement depuis $n - 1$, donc $(\lambda + \mu)\Pi_n = \lambda\,\Pi_{n-1}$, et $\Pi_n = \left(\tfrac{\lambda}{\lambda+\mu}\right)^n \Pi_0$. Pour l’état $K$ : $\mu\,\Pi_K = \lambda\,\Pi_{K-1}$. Pour l’état 0 : $\lambda\,\Pi_0 = \mu\,(1 - \Pi_0)$ (tous les autres états se vident vers 0), donc $\Pi_0 = \tfrac{\mu}{\lambda+\mu}$. On obtient la formule annoncée pour $n < K$, et $\Pi_K = \tfrac{\lambda}{\mu}\,\Pi_{K-1} = \tfrac{\lambda}{\mu} \cdot \tfrac{\mu}{\lambda+\mu}\left(\tfrac{\lambda}{\lambda+\mu}\right)^{K-1} = \left(\tfrac{\lambda}{\lambda+\mu}\right)^K$.
3. Par les arrivées de Poisson, la proportion de paquets perdus est $\Pi_K$. On veut $\left(\tfrac{\lambda}{\lambda+\mu}\right)^{10} \leq 10^{-3}$, soit $\tfrac{\lambda}{\lambda+\mu} \leq 10^{-0{,}3} \approx 0{,}501$, donc $\mu \geq \lambda\,(1 - 0{,}501)/0{,}501 \approx 99{,}5$ vidages par seconde. Avec $\mu = \lambda = 100$, on perd $(1/2)^{10} \approx 0{,}098\,\%$ des paquets.
4. Non : l’instant du prochain vidage dépendrait du temps écoulé depuis le précédent, une information qui ne figure pas dans l’état « nombre de paquets ». Le futur ne dépendrait plus seulement du présent. Pour retrouver un modèle markovien, il faudrait ajouter à l’état le temps écoulé depuis le dernier vidage (on sort alors du cadre de ce cours).

En code

Python

import numpy as np

lam, mu, K = 100.0, 100.0, 10
A = np.zeros((K + 1, K + 1))
for n in range(K + 1):
    if n < K:
        A[n, n + 1] = lam                  # arrivée d'un paquet
    if n >= 1:
        A[n, 0] = mu                       # vidage complet
    A[n, n] = -A[n].sum()

M = A.T.copy(); M[-1, :] = 1
pi = np.linalg.solve(M, np.r_[np.zeros(K), 1])
x = lam / (lam + mu)
formule = np.r_[(1 - x) * x ** np.arange(K), x**K]
print(np.abs(pi - formule).max())          # 1e-19 : la formule est exacte
print(pi[K])                               # 0.000977 de paquets perdus

print(lam * (1 - 10**-0.3) / 10**-0.3)     # 99.53 vidages/s au minimum

R

lam <- 100; mu <- 100; K <- 10
A <- matrix(0, K + 1, K + 1)            # états 0, ..., K en positions 1, ..., K+1
for (n in 0:K) {
  if (n < K)  A[n + 1, n + 2] <- lam    # arrivée d'un paquet
  if (n >= 1) A[n + 1, 1] <- mu         # vidage complet
  A[n + 1, n + 1] <- -sum(A[n + 1, ])
}
M <- t(A); M[K + 1, ] <- 1
pi_ <- solve(M, c(rep(0, K), 1))
x <- lam / (lam + mu)
formule <- c((1 - x) * x^(0:(K - 1)), x^K)
max(abs(pi_ - formule))                 # 2e-19 : la formule est exacte
pi_[K + 1]                              # 0.000977 de paquets perdus

lam * (1 - 10^-0.3) / 10^-0.3           # 99.53 vidages/s au minimum