Trouvez le goulot d'étranglement

L’an dernier, 152 personnes naviguaient en même temps sur la billetterie au pic d’ouverture. Cette année, l’équipe marketing en annonce 400. Le site tiendra-t-il ? Et s’il ne tient pas, faut-il acheter un processeur plus rapide, un meilleur disque, ou un deuxième serveur web ?

Vous allez voir qu’avec les trois demandes de service calculées au chapitre précédent, et rien d’autre, on peut déjà répondre à ces questions à la main. C’est toute la puissance des bornes asymptotiques.

Le goulot : la ressource qui sature la première

Reprenons la loi de la demande de service, écrite à l’envers : $U_i = X_0 \, D_i$. Quand le débit du système $X_0$ augmente, l’utilisation de toutes les ressources augmente, chacune proportionnellement à sa demande. Or une utilisation ne peut pas dépasser 1 : une ressource ne peut pas être occupée plus de 100 % du temps. Donc, pour chaque ressource, $X_0 D_i \leq 1$, et la contrainte la plus forte vient de la ressource de plus grande demande :

$$X_0 \leq \frac{1}{D_{\max}}$$

où $D_{\max} = \max_i D_i$ est la plus grande demande de service. Cette ressource s’appelle le goulot d’étranglement (bottleneck) : c’est elle qui atteint 100 % d’utilisation la première, et elle fixe le débit maximal du système entier.

Exemple

Pour la billetterie, les demandes sont $D_{\text{web}} = 20$ ms, $D_{\text{CPU}} = 30$ ms et $D_{\text{disque}} = 60$ ms. Le goulot est le disque, et le débit maximal vaut $X_{\max} = 1/0{,}06 \approx 16{,}7$ commandes/s. Au chapitre 2, on mesurait 10 commandes/s avec un disque occupé à 60 % : cohérent, puisque $0{,}6 = 10 \times 0{,}06$.

Remarquez que le goulot n’est pas forcément la ressource la plus lente par visite. Le processeur fait 5 visites de 6 ms, le disque 4 visites de 15 ms : c’est le produit $V_i S_i$ qui compte.

Chaque utilisation croît en ligne droite, de pente Dᵢ. Le disque, de plus grande demande, touche 100 % le premier, à 16,7 commandes/s : c'est lui qui plafonne tout le système.

À retenir

Le goulot est la ressource de plus grande demande de service $D_i$ (pas de plus grand temps de service $S_i$). Le débit du système ne peut jamais dépasser $1/D_{\max}$, quel que soit le nombre d’utilisateurs.

Les bornes asymptotiques

Considérons un système fermé : $N$ utilisateurs, chacun avec un temps de réflexion $Z$, et $K$ ressources de demandes $D_1, \dots, D_K$. Notons $D = \sum_i D_i$ la demande totale, c’est-à-dire le temps de réponse d’une requête qui ne rencontrerait aucune file d’attente.

Borne sur le débit

Deux contraintes limitent le débit :

• Peu d’utilisateurs : même sans aucune attente, un utilisateur ne peut pas envoyer plus d’une requête toutes les $D + Z$ secondes. Avec $N$ utilisateurs, $X_0 \leq N / (D + Z)$.
• Beaucoup d’utilisateurs : le goulot impose $X_0 \leq 1 / D_{\max}$.

$$X_0(N) \leq \min\left( \frac{N}{D + Z}, \; \frac{1}{D_{\max}} \right)$$

Borne sur le temps de réponse

De même, le temps de réponse est minoré de deux façons :

• une requête doit au minimum recevoir son service : $R \geq D$ ;
• avec la loi du temps de réponse interactif, $R = N / X_0 - Z$, et comme $X_0 \leq 1/D_{\max}$, on obtient $R \geq N D_{\max} - Z$.

$$R(N) \geq \max\left( D, \; N D_{\max} - Z \right)$$

Le point de saturation

Les deux droites de la borne sur le débit se croisent en :

$$N^* = \frac{D + Z}{D_{\max}}$$

C’est le point de saturation. En dessous de $N^*$, le système peut en théorie servir tout le monde sans attente, et le débit croît avec $N$. Au-delà, le goulot est saturé : ajouter des utilisateurs n’augmente plus le débit, mais seulement le temps de réponse, qui croît alors de $D_{\max}$ par utilisateur supplémentaire.

Attention

Certains formulaires écrivent la borne sous la forme $X_0 \leq \min(1/D_{\max}, \, N/D)$, sans $Z$. C’est le cas particulier d’un système sans temps de réflexion ($Z = 0$), par exemple un traitement par lots où une tâche en remplace immédiatement une autre. Pour un site web, oublier $Z$ sous-estime énormément le nombre d’utilisateurs supportés.

Exemple

Pour la billetterie : $D = 20 + 30 + 60 = 110$ ms, $D_{\max} = 60$ ms, $Z = 15$ s.

$$N^* = \frac{0{,}11 + 15}{0{,}06} \approx 252 \text{ utilisateurs}$$

• Avec 152 utilisateurs (l’an dernier) : $X_0 \leq \min(152/15{,}11 \, ; \, 16{,}7) \approx 10{,}1$ req/s, et $R \geq 0{,}11$ s. On est sous la saturation.
• Avec 400 utilisateurs (cette année) : $X_0 \leq 16{,}7$ req/s, et $R \geq 400 \times 0{,}06 - 15 = 9$ s. Même dans le meilleur des cas, chaque clic prendra au moins 9 secondes. Le site ne tiendra pas.

Le graphique ci-dessous montre les deux bornes du débit (en pointillés) et, en trait plein, le débit exact que calculera l’algorithme MVA au chapitre 5. La vraie courbe reste sous les bornes et s’en éloigne surtout autour de $N^*$, là où les files d’attente se forment.

Les bornes (pointillés) encadrent la courbe exacte de MVA (trait plein). L'écart est le plus grand autour de N* ≈ 252, là où les files se forment ; au-delà, chaque utilisateur ajouté coûte 60 ms de temps de réponse.

Quelle amélioration vaut la peine ?

Les bornes donnent une règle de décision très simple. Seule la réduction de $D_{\max}$ relève le plafond de débit. Améliorer une autre ressource réduit un peu $D$ (donc le temps de réponse à faible charge) mais ne change rien au débit maximal.

Comparons trois investissements pour la billetterie :

Amélioration	Nouvelles demandes (web, CPU, disque)	$X_{\max}$	$N^*$
Aucune	20, 30, 60 ms	16,7 req/s	252
Serveur web deux fois plus rapide	10, 30, 60 ms	16,7 req/s	252
Processeur deux fois plus rapide	20, 15, 60 ms	16,7 req/s	252
Disque SSD deux fois plus rapide	20, 30, 30 ms	33,3 req/s	503

Seul le disque fait bouger les choses, et il double le débit maximal. Mais attention : avec un disque à 30 ms, le processeur (30 ms aussi) devient co-goulot. Pour aller plus loin, il faudra améliorer les deux. C’est le phénomène du goulot qui se déplace : on n’en a jamais fini, on repousse simplement la limite jusqu’à la ressource suivante.

Et avec le SSD, les 400 utilisateurs de cette année passent-ils ? $N^* \approx 503 > 400$ : oui, en théorie on reste sous la saturation. La borne $R \geq \max(0{,}08 \, ; \, 400 \times 0{,}03 - 15)$ vaut 0,08 s, ce qui est encourageant, mais une borne reste optimiste : le chapitre 5 donnera le vrai temps de réponse.

Diviser par deux la demande du goulot double le plafond et repousse N* au-delà des 400 utilisateurs attendus ; améliorer le web ou le processeur ne déplacerait aucune de ces courbes.

Piège

Optimiser ce qui est facile à optimiser plutôt que le goulot. Diviser par deux le temps du serveur web est satisfaisant techniquement, mais inutile si le disque sature : le débit maximal ne bouge pas d’un iota.

def bornes(D, Z, N):
    """Bornes asymptotiques d'un système fermé : N utilisateurs, temps de réflexion Z."""
    D_tot, D_max = sum(D.values()), max(D.values())
    goulot = max(D, key=D.get)
    X_max = min(N / (D_tot + Z), 1 / D_max)
    R_min = max(D_tot, N * D_max - Z)
    N_sat = (D_tot + Z) / D_max
    return goulot, X_max, R_min, N_sat

D = {"web": 0.020, "cpu": 0.030, "disque": 0.060}      # demandes de service (s)
for N in (152, 400):
    goulot, X, R, N_sat = bornes(D, Z=15, N=N)
    print(f"N={N}: goulot={goulot}, X <= {X:.1f} req/s, R >= {R:.2f} s, N* = {N_sat:.0f}")

En entretien

« Pour trouver le goulot, je mesure l’utilisation de chaque ressource et le débit, j’en déduis les demandes de service $D_i = U_i / X$ : le goulot est la ressource de plus grande demande, et le débit ne peut pas dépasser $1/D_{\max}$. Améliorer autre chose ne sert à rien pour le débit, et après amélioration le goulot se déplace. »

En résumé

• Comme $U_i = X_0 D_i \leq 1$, le débit est plafonné par la ressource de plus grande demande : $X_0 \leq 1/D_{\max}$. C’est le goulot.
• Borne sur le débit d’un système fermé : $X_0(N) \leq \min(N/(D + Z), \, 1/D_{\max})$.
• Borne sur le temps de réponse : $R(N) \geq \max(D, \, N D_{\max} - Z)$.
• Le point de saturation $N^* = (D + Z)/D_{\max}$ sépare le régime où le débit croît de celui où seul le temps de réponse augmente.
• Seule la réduction de $D_{\max}$ relève le plafond ; après amélioration, le goulot se déplace.
• Les bornes sont optimistes : elles ignorent les files d’attente, que les chapitres 4 et 5 prennent en compte.

Exercices

Exercice · Trouver le goulot

facile

Un serveur d’analyse de données traite 20 tâches par seconde. On mesure les utilisations suivantes : processeur 0,5, disque A 0,7, disque B 0,3, réseau 0,2.

1. Calculez la demande de service de chaque ressource.
2. Quel est le goulot, et quel est le débit maximal ?

Voir la solution

1. Par la loi de la demande de service, $D_i = U_i / X_0$ : processeur $0{,}5/20 = 25$ ms, disque A $0{,}7/20 = 35$ ms, disque B $0{,}3/20 = 15$ ms, réseau $0{,}2/20 = 10$ ms.
2. Le goulot est le disque A (35 ms). Le débit maximal vaut $1/0{,}035 \approx 28{,}6$ tâches/s. On pouvait le voir directement : c’est la ressource la plus utilisée, et elle atteindra 100 % quand le débit sera multiplié par $1/0{,}7 \approx 1{,}43$.

En code

Python

X0 = 20                                             # tâches/s
U = {"processeur": 0.5, "disque A": 0.7, "disque B": 0.3, "réseau": 0.2}

D = {nom: u / X0 for nom, u in U.items()}           # loi de la demande de service
for nom, d in D.items():
    print(f"{nom:<10} D = {d * 1000:.0f} ms")       # 25, 35, 15, 10 ms
goulot = max(D, key=D.get)
print(goulot, round(1 / D[goulot], 1))              # disque A 28.6 tâches/s

R

X0 <- 20                                            # tâches/s
U <- c(processeur = 0.5, disque_A = 0.7, disque_B = 0.3, reseau = 0.2)

D <- U / X0                                         # loi de la demande de service
D * 1000                                            # 25  35  15  10 ms
goulot <- names(which.max(D))
c(goulot, round(1 / max(D), 1))                     # "disque_A"  "28.6"

Exercice · Bornes d'un système interactif

moyen

Un intranet a trois ressources de demandes $D_{\text{CPU}} = 40$ ms, $D_{\text{disque}} = 100$ ms et $D_{\text{réseau}} = 20$ ms. Les employés réfléchissent en moyenne $Z = 10$ s entre deux requêtes.

1. Calculez le point de saturation $N^*$.
2. Donnez les bornes sur le débit et sur le temps de réponse pour 50 puis 200 employés.

Voir la solution

$D = 0{,}16$ s et $D_{\max} = 0{,}1$ s (le disque).

1. $N^* = (0{,}16 + 10)/0{,}1 = 101{,}6$, soit environ 102 employés.
2. Pour $N = 50$ : $X_0 \leq \min(50/10{,}16 \, ; \, 10) \approx 4{,}92$ req/s et $R \geq \max(0{,}16 \, ; \, 5 - 10) = 0{,}16$ s. Pour $N = 200$ : $X_0 \leq \min(19{,}7 \, ; \, 10) = 10$ req/s et $R \geq \max(0{,}16 \, ; \, 200 \times 0{,}1 - 10) = 10$ s. Avec 200 employés, le système est largement saturé : au moins 10 s par requête.

En code

Python

D = {"cpu": 0.040, "disque": 0.100, "réseau": 0.020}   # demandes de service (s)
Z = 10                                                 # temps de réflexion (s)
D_tot, D_max = sum(D.values()), max(D.values())

N_sat = (D_tot + Z) / D_max                            # point de saturation
print(f"N* = {N_sat:.1f}")                             # N* = 101.6
for N in (50, 200):
    X_borne = min(N / (D_tot + Z), 1 / D_max)          # borne sur le débit
    R_borne = max(D_tot, N * D_max - Z)                # borne sur le temps de réponse
    print(f"N = {N}: X <= {X_borne:.2f} req/s, R >= {R_borne:.2f} s")
# N = 50: X <= 4.92 req/s, R >= 0.16 s
# N = 200: X <= 10.00 req/s, R >= 10.00 s

R

D <- c(cpu = 0.040, disque = 0.100, reseau = 0.020)   # demandes de service (s)
Z <- 10                                                # temps de réflexion (s)
D_tot <- sum(D); D_max <- max(D)

(D_tot + Z) / D_max                                    # N* = 101.6
for (N in c(50, 200)) {
  X_borne <- min(N / (D_tot + Z), 1 / D_max)           # borne sur le débit
  R_borne <- max(D_tot, N * D_max - Z)                 # borne sur le temps de réponse
  cat(sprintf("N = %d : X <= %.2f req/s, R >= %.2f s\n", N, X_borne, R_borne))
}
# N = 50 : X <= 4.92 req/s, R >= 0.16 s
# N = 200 : X <= 10.00 req/s, R >= 10.00 s

Exercice · Dimensionner un achat

difficile

Reprenez l’intranet de l’exercice précédent. L’entreprise veut que 200 employés aient un temps de réponse borné inférieurement par moins de 1 s (c’est une condition nécessaire, pas suffisante). Deux options : un disque deux fois plus rapide, ou deux disques identiques à l’actuel entre lesquels on répartit équitablement les données.

1. Calculez $N^*$ et la borne sur $R$ pour 200 employés dans chaque cas.
2. Laquelle choisir ?

Voir la solution

1. Disque deux fois plus rapide : $D_{\text{disque}} = 50$ ms. Le nouveau goulot est le disque à 50 ms (le processeur est à 40 ms). $D = 0{,}11$ s, $N^* = 10{,}11/0{,}05 \approx 202$. Pour 200 employés, $R \geq \max(0{,}11 \, ; \, 200 \times 0{,}05 - 10) = \max(0{,}11 \, ; \, 0) = 0{,}11$ s. Deux disques : chacun reçoit la moitié des accès, donc $D = 50$ ms par disque. Les demandes sont 40, 50, 50 et 20 ms, $D = 0{,}16$ s, $D_{\max} = 0{,}05$ s, $N^* = 10{,}16/0{,}05 \approx 203$. Pour 200 employés, $R \geq \max(0{,}16 \, ; \, 0) = 0{,}16$ s.
2. Les deux options donnent le même plafond de débit (20 req/s) et une borne sur $R$ bien inférieure à 1 s. Mais dans les deux cas, 200 employés sont juste sous le point de saturation : les files d’attente seront importantes et le vrai temps de réponse bien supérieur à la borne. Il faudrait aussi traiter le processeur, qui devient presque un co-goulot, ou vérifier avec MVA (chapitre 5). La leçon : la borne est une condition nécessaire, et un système dimensionné pile à $N^*$ est un système qui souffrira.

En code

Python

Z, N = 10, 200
options = {
    "disque x2":    [0.040, 0.050, 0.020],          # CPU, disque, réseau (s)
    "deux disques": [0.040, 0.050, 0.050, 0.020],   # CPU, disque 1, disque 2, réseau
}
for nom, D in options.items():
    D_tot, D_max = sum(D), max(D)
    N_sat = (D_tot + Z) / D_max
    R_borne = max(D_tot, N * D_max - Z)
    print(f"{nom:<13} N* = {N_sat:.0f}, X_max = {1 / D_max:.0f} req/s, R >= {R_borne:.2f} s")
# disque x2     N* = 202, X_max = 20 req/s, R >= 0.11 s
# deux disques  N* = 203, X_max = 20 req/s, R >= 0.16 s

R

Z <- 10; N <- 200
options <- list(
  "disque x2"    = c(0.040, 0.050, 0.020),          # CPU, disque, réseau (s)
  "deux disques" = c(0.040, 0.050, 0.050, 0.020)    # CPU, disque 1, disque 2, réseau
)
for (nom in names(options)) {
  D <- options[[nom]]
  N_sat <- (sum(D) + Z) / max(D)
  R_borne <- max(sum(D), N * max(D) - Z)
  cat(sprintf("%-13s N* = %.0f, X_max = %.0f req/s, R >= %.2f s\n",
              nom, N_sat, 1 / max(D), R_borne))
}
# disque x2     N* = 202, X_max = 20 req/s, R >= 0.11 s
# deux disques  N* = 203, X_max = 20 req/s, R >= 0.16 s