Analysez une file d'attente M/M/1

Votre API de prédiction tourne sur un seul serveur, capable de traiter 10 requêtes par seconde. Elle en reçoit 8 par seconde : le serveur est occupé à 80 %, il lui reste de la marge… Et pourtant, les utilisateurs se plaignent de temps de réponse cinq fois plus longs que le temps de calcul d’une requête. Pourquoi ? Et que se passerait-il si le trafic montait à 9,5 requêtes par seconde ?

Les files d’attente répondent exactement à ce genre de questions. Dans ce chapitre, vous allez apprendre à décrire une file avec la notation de Kendall, puis à analyser la plus simple et la plus importante d’entre elles, la file M/M/1. Nous suivrons cette API mono-serveur tout au long du chapitre.

L’anatomie d’une file d’attente

Une file d’attente « isolée » se compose de clients qui arrivent, attendent éventuellement dans une salle d’attente (le tampon, ou buffer), sont servis par un ou plusieurs serveurs, puis repartent. Ici, les clients sont des requêtes et le serveur est une instance du modèle. Pour la décrire, il faut préciser cinq caractéristiques :

• le processus d’arrivée : la loi des durées entre deux arrivées ;
• le service : la loi de la durée de service d’un client ;
• le nombre de serveurs qui travaillent en parallèle ;
• la capacité du système : le nombre maximal de clients présents (en attente et en service). Par défaut, on la suppose infinie. Une salle d’attente de cabinet médical, ou le tampon d’un routeur réseau, ont une capacité finie : un client qui arrive quand tout est plein est perdu ;
• la discipline de service : l’ordre dans lequel on sert les clients en attente.

Les cinq ingrédients d'une file : la loi des arrivées, le tampon (sa capacité et sa discipline), le nombre de serveurs et la loi du service. Si la capacité est finie, un client qui trouve le système plein est perdu.

Les disciplines les plus courantes sont FIFO (premier arrivé, premier servi, la discipline par défaut), LIFO (dernier arrivé, premier servi, comme une pile), RR (tourniquet, ou round robin : chaque client reçoit à tour de rôle un petit quantum de service, comme les processus d’un système d’exploitation) et PS (partage du serveur, processor sharing : la limite du tourniquet quand le quantum tend vers zéro, tous les clients présents sont servis simultanément à vitesse réduite).

On peut aussi introduire des priorités. Avec une priorité non préemptive, un client prioritaire passe devant la file mais attend la fin du service en cours. Avec une priorité préemptive, il interrompt le client en service, qui reprendra ensuite de trois façons possibles : là où il s’était arrêté (preemptive resume), en recommençant un service de même durée (repeat identical) ou en recommençant avec une nouvelle durée tirée au hasard (repeat different). Aux urgences, un blessé grave interrompt la consultation en cours : c’est une priorité préemptive.

La notation de Kendall

Pour nommer une file en quelques caractères, on utilise la notation de Kendall :

$$F_T \,/\, F_S \,/\, s \,/\, N$$

• $F_T$ est la loi des temps inter-arrivées ;
• $F_S$ est la loi des durées de service ;
• $s$ est le nombre de serveurs ;
• $N$ est la capacité du système, omise quand elle est infinie.

Les lois se notent par une lettre :

Lettre	Loi	Exemple
M	exponentielle (markovienne, sans mémoire)	arrivées de Poisson
D	déterministe (durée constante)	un robot qui traite chaque pièce en 30 s exactement
$E_k$	Erlang d’ordre $k$ : somme de $k$ phases exponentielles successives	une inscription en $k$ guichets successifs
$H_k$	hyper-exponentielle : une exponentielle choisie au hasard parmi $k$	des requêtes simples ou lourdes
G	générale, quelconque	un service mesuré, sans loi connue
GI	générale, avec des durées indépendantes	des arrivées renouvelées quelconques

Ainsi, M/M/1 désigne une file à arrivées de Poisson, service exponentiel, un serveur et capacité infinie ; M/D/1 la même avec un service de durée fixe ; M/M/3/10 une file à trois serveurs qui accepte au plus 10 clients.

À retenir

Une file se décrit par ses arrivées, son service, son nombre de serveurs, sa capacité et sa discipline. La notation de Kendall $F_T/F_S/s/N$ résume les quatre premiers ; « M » signifie exponentiel, donc markovien.

La file M/M/1 : un processus de naissance et de mort

Dans une file M/M/1, les requêtes arrivent selon un processus de Poisson de taux $\lambda$ et chaque service dure un temps exponentiel de taux $\mu$. Grâce à l’absence de mémoire, le nombre $X_t$ de requêtes présentes (en attente ou en service) est une chaîne de Markov, et plus précisément un processus de naissance et de mort (chapitre 6) :

• une arrivée fait passer de $n$ à $n + 1$, au taux $\lambda_n = \lambda$ ;
• une fin de service fait passer de $n$ à $n - 1$, au taux $\mu_n = \mu$ dès que $n \geq 1$.

On définit l’intensité de trafic (ou charge) du serveur :

$$\rho = \frac{\lambda}{\mu}$$

C’est le rapport entre le rythme des arrivées et le rythme de service. Pour notre API, $\rho = 8/10 = 0{,}8$.

Le chapitre 6 nous donne directement $\gamma_n = \rho^n$. La série géométrique converge si et seulement si $\rho < 1$ : c’est la condition de stabilité. Il faut, en moyenne, servir plus vite qu’on ne reçoit. Sous cette condition,

$$\Pi_n = (1 - \rho)\,\rho^n, \qquad n = 0, 1, 2, \dots$$

Le nombre de clients suit une loi géométrique. En particulier, $\Pi_0 = 1 - \rho$ est la probabilité que le serveur soit inoccupé, et la probabilité d’avoir au moins $k$ clients vaut $P(X \geq k) = \rho^k$.

Exemple

Pour l’API ($\rho = 0{,}8$) : le serveur est inoccupé 20 % du temps, ce qui est cohérent avec une charge de 80 %. La probabilité qu’au moins 5 requêtes soient présentes vaut $0{,}8^5 \approx 0{,}33$ : une fois sur trois, une requête qui arrive trouve déjà 5 requêtes devant elle ou plus. Voilà l’origine des plaintes.

Pour ρ = 0,8, l'état le plus probable est la file vide (20 % du temps), mais la queue est longue : les barres roses, 5 requêtes ou plus, pèsent ensemble 0,33, et la moyenne atteint 4.

Piège

Si $\rho \geq 1$, il n’y a pas de régime stationnaire. La chaîne est irréductible, mais elle n’est pas récurrente positive : la file grossit sans limite (pour $\rho > 1$) ou fait des excursions de plus en plus longues (pour $\rho = 1$). Appliquer les formules avec $\rho = 1{,}2$ donne des probabilités négatives, signe que la question n’a pas de sens.

En haut (ρ = 0,8), la file fait des excursions mais revient toujours à 0 : il existe un régime stationnaire. En bas (ρ = 1,2), elle grossit d'environ 2 requêtes par seconde : aucune loi stationnaire n'existe.

Temps de séjour et loi de Little

Le nombre moyen de clients dans le système est l’espérance de la loi géométrique :

$$\bar N = \sum_{n \geq 0} n\,\Pi_n = \frac{\rho}{1 - \rho}.$$

Mais l’utilisateur se moque du nombre de requêtes présentes : ce qui l’intéresse, c’est le temps de séjour $\bar W$, le temps moyen entre l’arrivée de sa requête et la réponse. Le lien entre les deux est l’un des résultats les plus utiles de toute la théorie, la loi de Little :

$$\bar N = \lambda\, \bar W$$

• $\bar N$ est le nombre moyen de clients présents dans le système ;
• $\lambda$ est le débit moyen des clients qui entrent (et, en régime stationnaire, qui sortent) ;
• $\bar W$ est le temps moyen passé dans le système.

Son intuition est simple : si 8 clients entrent chaque seconde et que chacun reste en moyenne 0,5 seconde, il y a en permanence $8 \times 0{,}5 = 4$ clients dans le système. La loi de Little est remarquablement générale : elle ne suppose ni arrivées de Poisson, ni service exponentiel, ni discipline FIFO, seulement un régime stationnaire. Elle s’applique aussi à une partie du système, par exemple à la seule salle d’attente.

L'écart vertical entre arrivées et départs cumulés est le nombre de requêtes présentes, l'écart horizontal le séjour d'une requête. L'aire ombrée se calcule dans les deux sens : c'est l'idée de la loi de Little, N̄ = λ W̄.

Pour la M/M/1, on en tire :

Grandeur	Formule	API ($\lambda = 8$, $\mu = 10$)
Nombre moyen dans le système $\bar N$	$\rho/(1-\rho)$	4 requêtes
Temps moyen de séjour $\bar W = \bar N/\lambda$	$1/(\mu - \lambda)$	0,5 s
Temps moyen de service	$1/\mu$	0,1 s
Temps moyen d’attente $\bar W_q = \bar W - 1/\mu$	$\rho/(\mu - \lambda)$	0,4 s
Nombre moyen en attente $\bar N_q = \lambda \bar W_q$	$\rho^2/(1-\rho)$	3,2 requêtes

Nous tenons notre explication : une requête passe en moyenne 0,4 seconde à attendre pour 0,1 seconde de calcul. Le temps de réponse est cinq fois le temps de service, alors que le serveur n’est chargé qu’à 80 %.

On peut même aller plus loin : en discipline FIFO, le temps de séjour d’une requête dans une M/M/1 suit une loi exponentielle de taux $\mu - \lambda$. La probabilité qu’une requête attende plus d’une seconde sa réponse vaut donc $e^{-2} \approx 0{,}135$ : environ une requête sur sept.

Pourquoi tout explose près de la saturation

Que se passe-t-il quand le trafic augmente ? Gardons $\mu = 10$ et faisons varier $\lambda$ :

Arrivées $\lambda$ (requêtes/s)	Charge $\rho$	Temps moyen de séjour $\bar W = 1/(\mu - \lambda)$
5	50 %	0,2 s
8	80 %	0,5 s
9	90 %	1 s
9,5	95 %	2 s
9,9	99 %	10 s

Le temps de séjour se comporte comme $1/(1 - \rho)$ : il diverge quand la charge s’approche de 100 %. Passer de 80 % à 95 % de charge, soit moins de 20 % de trafic en plus, multiplie le temps de réponse par 4. C’est pour cette raison que les équipes d’exploitation visent des taux d’utilisation de l’ordre de 60 à 70 % sur les services sensibles à la latence : la marge restante n’est pas du gaspillage, c’est ce qui absorbe les fluctuations aléatoires des arrivées.

Le temps de séjour 1/(μ − λ) reste modeste tant que la charge est raisonnable, puis explose à l'approche de 100 % : les points du tableau montrent qu'entre 80 % et 99 % de charge, il est multiplié par 20.

En entretien

« Dans une file M/M/1, le temps de séjour moyen vaut $1/(\mu - \lambda)$ : il explose quand la charge approche 100 %, parce que la moindre rafale d’arrivées crée une file qui met longtemps à se résorber. Et par la loi de Little, $\bar N = \lambda \bar W$, je passe librement du nombre moyen de requêtes en cours au temps de réponse moyen. »

La simulation d’une file FIFO à un serveur tient en quelques lignes : chaque requête commence son service à son arrivée, ou à la fin du service précédent si le serveur est occupé.

import numpy as np

rng = np.random.default_rng(0)
lam, mu, n = 8.0, 10.0, 200_000

arrivees = np.cumsum(rng.exponential(1 / lam, n))   # instants d'arrivée
services = rng.exponential(1 / mu, n)               # durées de service

debut = np.empty(n)
fin = np.empty(n)
fin_precedente = 0.0
for i in range(n):
    debut[i] = max(arrivees[i], fin_precedente)     # attendre que le serveur se libère
    fin[i] = debut[i] + services[i]
    fin_precedente = fin[i]

sejour = fin - arrivees
print(sejour.mean())                    # proche de 0.5 = 1/(mu - lam)
print((debut - arrivees).mean())        # attente, proche de 0.4
print((sejour > 1).mean())              # proche de exp(-2) ≈ 0.135

Avec ces paramètres, on obtient bien un séjour moyen voisin de 0,5 s et une attente moyenne voisine de 0,4 s. Ce petit simulateur vous permet ensuite de tester ce que les formules ne couvrent pas : un service de durée constante, des arrivées en rafales, une discipline LIFO.

En résumé

• Une file d’attente se décrit par ses arrivées, son service, son nombre de serveurs, sa capacité et sa discipline (FIFO par défaut, LIFO, RR, PS), avec d’éventuelles priorités préemptives ou non.
• Kendall : $F_T/F_S/s/N$, avec M (exponentielle), D (déterministe), $E_k$ (Erlang), $H_k$ (hyper-exponentielle), G et GI (générales).
• La M/M/1 est un processus de naissance et de mort de taux constants ; intensité de trafic $\rho = \lambda/\mu$, stable si et seulement si $\rho < 1$.
• Régime stationnaire géométrique : $\Pi_n = (1-\rho)\rho^n$ ; $\bar N = \rho/(1-\rho)$ ; $\bar W = 1/(\mu - \lambda)$ ; $\bar W_q = \rho/(\mu - \lambda)$.
• Loi de Little : $\bar N = \lambda \bar W$, valable pour tout système stable, et même pour une partie du système.
• Le temps de séjour diverge en $1/(1-\rho)$ près de la saturation : il faut garder de la marge.

Exercices

Exercice · Lire la notation de Kendall

facile

Décrivez en une phrase chacune des files suivantes : M/D/1, M/M/3/10, M/M/∞, $E_2$/M/1.

Voir la solution

• M/D/1 : arrivées de Poisson, durée de service constante, un seul serveur, capacité infinie (par exemple, une machine qui emballe chaque colis en un temps fixe).
• M/M/3/10 : arrivées de Poisson, services exponentiels, trois serveurs, au plus 10 clients présents en tout (3 en service et 7 en attente) ; un client qui arrive quand le système est plein est perdu.
• M/M/∞ : arrivées de Poisson, services exponentiels, une infinité de serveurs : chaque client est servi dès son arrivée, sans jamais attendre.
• $E_2$/M/1 : les durées entre arrivées sont des sommes de deux phases exponentielles (arrivées plus régulières que Poisson), service exponentiel, un serveur.

Exercice · L'imprimante du laboratoire

moyen

Une imprimante partagée reçoit en moyenne 12 impressions par heure, selon un processus de Poisson. Une impression dure en moyenne 4 minutes, selon une loi exponentielle.

1. Quelle est la charge de l’imprimante ? La file est-elle stable ?
2. Combien d’impressions sont présentes en moyenne ? Combien de temps attend-on en moyenne sa feuille, depuis l’envoi jusqu’à la fin de l’impression ?
3. Quelle est la probabilité de trouver au moins 4 impressions devant soi en envoyant la sienne ?

Voir la solution

1. $\lambda = 12$ par heure, $\mu = 60/4 = 15$ par heure, donc $\rho = 0{,}8 < 1$ : la file est stable.
2. $\bar N = 0{,}8/0{,}2 = 4$ impressions. Par Little, $\bar W = \bar N/\lambda = 4/12$ h $= 20$ minutes (on retrouve $1/(\mu - \lambda) = 1/3$ h). Sur ces 20 minutes, 16 sont de l’attente et 4 d’impression.
3. Les arrivées de Poisson voient le système dans son régime stationnaire (c’est une propriété des arrivées de Poisson). La probabilité de trouver au moins 4 impressions vaut $\rho^4 = 0{,}8^4 \approx 0{,}41$.

En code

Python

lam = 12                                  # impressions par heure
mu = 60 / 4                               # une impression dure 4 minutes
rho = lam / mu
N = rho / (1 - rho)                       # nombre moyen présent
W = N / lam                               # loi de Little (en heures)
print(rho, N, W * 60, (W - 1 / mu) * 60)  # 0.8 4.0 20.0 16.0 (minutes)
print(rho ** 4)                           # 0.4096 : au moins 4 impressions devant soi

R

lam <- 12                               # impressions par heure
mu <- 60 / 4                            # une impression dure 4 minutes
rho <- lam / mu
N <- rho / (1 - rho)                    # nombre moyen présent
W <- N / lam                            # loi de Little (en heures)
c(rho = rho, N = N, sejour_min = W * 60, attente_min = (W - 1 / mu) * 60)
## rho 0.8   N 4   sejour_min 20   attente_min 16
rho^4                                   # 0.4096 : au moins 4 impressions devant soi

Exercice · Dimensionner pour une latence cible

difficile

L’API reçoit $\lambda = 8$ requêtes par seconde. On peut choisir une machine plus puissante, de taux de service $\mu$ plus élevé.

1. Quel $\mu$ minimal garantit un temps de séjour moyen inférieur à 0,2 s ?
2. L’équipe produit préfère un objectif en pourcentage : moins de 1 % des requêtes doivent attendre leur réponse plus d’une seconde. Quel $\mu$ minimal faut-il ?
3. Avec ce dernier $\mu$, quelle est la charge du serveur ? Commentez.

Voir la solution

1. $\bar W = 1/(\mu - 8) \leq 0{,}2$ équivaut à $\mu - 8 \geq 5$, soit $\mu \geq 13$ requêtes par seconde.
2. Le temps de séjour est exponentiel de taux $\mu - \lambda$, donc $P(W > 1) = e^{-(\mu - 8)}$. On veut $e^{-(\mu - 8)} \leq 0{,}01$, soit $\mu - 8 \geq \ln 100 \approx 4{,}61$, donc $\mu \geq 12{,}61$ requêtes par seconde environ.
3. La charge vaut alors $\rho = 8/12{,}61 \approx 0{,}63$. Pour tenir un objectif de latence exigeant, il faut accepter que le serveur soit inoccupé plus d’un tiers du temps : c’est le prix de l’aléa des arrivées.

En code

Python

import numpy as np

lam = 8
mu_moyenne = lam + 1 / 0.2               # 1/(mu - lam) <= 0.2
mu_quantile = lam + np.log(100)          # exp(-(mu - lam)) <= 0.01
print(mu_moyenne, mu_quantile)           # 13.0 12.605
print(lam / mu_quantile)                 # 0.635 : charge du serveur
print(np.exp(-(mu_quantile - lam)))      # 0.01 : contrôle

R

lam <- 8
mu_moyenne <- lam + 1 / 0.2             # 1/(mu - lam) <= 0.2
mu_quantile <- lam + log(100)           # exp(-(mu - lam)) <= 0.01
c(mu_moyenne, mu_quantile)              # 13.000 12.605
lam / mu_quantile                       # 0.635 : charge du serveur
exp(-(mu_quantile - lam))               # 0.01 : contrôle