Théorie des files d'attente : ce qu'elle dit de la latence

1 novembre 2026 8 min de lecture

La théorie des files d’attente (en anglais queueing theory) est la mathématique de l’attente : à partir du rythme d’arrivée du travail, de la durée de chaque tâche et du nombre de serveurs, elle prédit combien de temps les tâches attendent et quelle longueur atteint la file. Pour le logiciel, son résultat le plus utile est que le temps de réponse augmente lentement sous charge modérée, puis brusquement quand un serveur approche 100 % d’occupation. Dans le modèle le plus simple, un serveur occupé 90 % du temps répond en moyenne dix fois plus lentement qu’un serveur inactif.

Les chiffres ci-dessous sont des calculs tirés de formules classiques, vérifiés par un script, sans test derrière. Les sources ont été vérifiées le 1er novembre 2026.

Taux d’utilisation ρ	Temps dans le système W ÷ temps de service S	Si S = 20 ms
0,5	2	40 ms
0,7	3,3	67 ms
0,8	5	100 ms
0,9	10	200 ms
0,95	20	400 ms
0,99	100	2 000 ms

Ce sont des moyennes pour la file M/M/1 : un serveur, des arrivées de Poisson et des temps de service exponentiels.

Qu’est-ce que la théorie des files d’attente ?

C’est la branche des probabilités qui modélise un travail qui arrive, attend puis est servi. Une file se décrit par ses arrivées, ses temps de service, son nombre de serveurs et sa discipline de service, c’est-à-dire l’ordre dans lequel les tâches en attente sont prises.

Urban Operations Research de Larson et Odoni, un texte du MIT en libre accès, cite les guichets de banque, les caisses de supermarché et les péages comme cas classiques. Un serveur web entre dans le même cadre : les requêtes arrivent, des threads ou des cœurs les traitent, et les autres attendent dans une file.

D’où vient la théorie des files d’attente ?

Du central téléphonique, où A. K. Erlang a obtenu les premiers résultats pour la compagnie des téléphones de Copenhague.

Selon sa biographie MacTutor, l’article d’Erlang de 1909 montrait que des appels passés au hasard suivent la loi de Poisson, et sa formule de 1917 sur les pertes et le temps d’attente a vite été adoptée par des compagnies de téléphone de nombreux pays. L’article de David Kendall de 1953, Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain, a introduit la notation encore en usage, comme le rappelle le récit de son œuvre par Geoffrey Grimmett. La démonstration de L = λW par Little et les résultats de Kingman en trafic dense ont suivi en 1961.

Que signifie la notation de Kendall, comme M/M/1 ?

Elle nomme une file en trois parties, A/S/c : la loi des intervalles entre arrivées, celle des temps de service et le nombre de serveurs. M/M/1 signifie des arrivées aléatoires, des temps de service exponentiels et un seul serveur.

M signifie memoryless, sans mémoire (arrivées de Poisson ou temps exponentiels), D déterministe et G general, c’est-à-dire n’importe quelle loi : M/D/1 est un serveur dont le temps de service est constant.

Comment le temps de réponse augmente-t-il avec le taux d’utilisation ?

Dans une file M/M/1, le temps moyen passé dans le système est W = 1/(μ − λ), soit S/(1 − ρ). Quand le taux d’utilisation ρ approche 1, W croît sans limite.

lambda = arrival rate        mu = service rate (1 / S)
rho    = lambda / mu         (utilization, must stay below 1)
W      = 1 / (mu - lambda)   = S / (1 - rho)

Larson et Odoni le démontrent pour un centre d’appels à une seule opératrice et montrent qu’il n’existe pas de régime stationnaire pour ρ ≥ 1 : la file ne cesse de s’allonger. La même source montre que le temps dans le système suit une loi exponentielle. Chaque percentile augmente donc du même facteur 1/(1 − ρ), et le p95 vaut environ trois fois la moyenne : 600 ms sur la ligne 0,9 ci-dessus.

Pourquoi la latence fait-elle un coude avant que le CPU atteigne 100 % ?

Parce qu’une requête attend chaque fois qu’elle trouve le serveur occupé, ce qui arrive de plus en plus souvent quand le taux d’utilisation monte. Sous les hypothèses M/M/1, le temps de réponse a déjà doublé à 50 % d’utilisation.

La ressource qui sature peut aussi être un pool de connexions, un verrou de base de données ou une boucle d’événements à un seul thread, et la plus chargée dicte la courbe. C’est ce coude précoce qui explique pourquoi le taux d’utilisation visé reste bien en dessous de 100 %. Partez de votre budget de latence : avec S = 20 ms et une moyenne cible de 100 ms, le tableau autorise environ 80 %, et une cible de 60 ms environ 67 %, avant que les pics de trafic ne prennent leur part.

Le panneau de capacité de LoadFocus regroupe un test terminé par nombre d’utilisateurs virtuels actifs et indique le dernier palier qui a tenu avant que le taux d’erreur dépasse 1 % ou que le p95 dépasse le double du meilleur palier, à condition qu’aucun palier supérieur ne se soit rétabli. Il lui faut un test sur un seul générateur de charge qui monte sur au moins trois paliers, le plus haut valant au moins le double du plus bas. D’après le calcul ci-dessus, si le palier le plus léger a laissé le goulot d’étranglement presque inactif, le doublement se déclenche juste au-delà de 50 % d’utilisation ; s’il le chargeait déjà à ρ0, le doublement se déclenche plus tard, au-delà de (1 + ρ0)/2 sous M/M/1.

Pourquoi la variabilité compte-t-elle autant que le taux d’utilisation ?

Les files naissent du hasard : des arrivées en rafales et des tâches parfois lentes. En trafic dense, le temps d’attente croît avec la variabilité des deux, multipliée par un terme ρ/(1 − ρ).

L’article de Kingman de 1961, The single server queue in heavy traffic, montre que lorsque l’intensité de trafic d’un serveur unique est proche de 1, la file est longue et le temps d’attente suit à peu près une loi exponentielle. Des notes de cours de la TU Eindhoven et du Technion en donnent une approximation de la moyenne (le Technion l’appelle approximation d’Allen-Cunneen ; elle est aussi largement connue sous le nom de formule de Kingman) :

Wq ≈ rho / (1 - rho) × (ca² + cs²) / 2 × S
ca, cs = coefficient of variation (std dev / mean)
         of arrival gaps and of service times

Wq est l’attente avant le début du service, et ca, cs sont les coefficients de variation. Des temps exponentiels ont c² = 1, ce qui redonne l’attente M/M/1 de 9S à 90 % d’utilisation. Un temps de service constant la divise par deux, à 4,5S ; cs² = 4, ce que peut produire un mélange de succès de cache et d’appels lents à la base de données, la porte à 22,5S. Un trafic synthétique régulier varie moins que la production, donc un test montre en général moins d’attente que les vrais pics.

Comment plusieurs serveurs (M/M/c) aident-ils ?

Plusieurs serveurs qui partagent une file absorbent bien mieux les rafales aléatoires que les mêmes serveurs avec une file chacun, si bien que chaque serveur peut être plus occupé pour la même attente.

D’après les formules M/M/m de Larson et Odoni, avec chaque serveur occupé à 90 %, W vaut 10S pour un serveur, 5,3S pour deux partageant une file et 3,0S pour quatre. Quatre instances derrière un répartiteur de charge qui choisit une instance libre se comportent comme le dernier cas ; quatre qui reçoivent chacune un quart aléatoire du trafic, comme des files M/M/1 séparées à 10S.

Quel lien avec la loi de Little ?

La loi de Little, L = λW, relie le nombre moyen de requêtes dans un système à leur taux d’arrivée et à leur temps de séjour, quelles que soient les lois. La théorie des files d’attente donne W, et la loi de Little en tire L.

Sur la ligne 0,9, 45 requêtes par seconde avec W = 200 ms donnent en moyenne 9 requêtes dans le système. Notre article sur la loi de Little utilise la même loi pour dimensionner et vérifier des tests de charge.

Où ces modèles cessent-ils de s’appliquer en test de charge ?

Ils supposent un flux ouvert d’arrivées indépendantes et un régime stationnaire. Un test avec un nombre fixe d’utilisateurs virtuels est un système fermé, où les arrivées ralentissent quand les réponses ralentissent.

Tests fermés. Avec N utilisateurs virtuels, il y a au plus N requêtes dans le système, donc la cadence de requêtes baisse là où une file ouverte s’allongerait, et le temps de réflexion la réduit encore. Notre article sur le modèle de charge ouvert ou fermé explique pourquoi cela masque la saturation.
LoadFocus exécute des scripts k6, mais les scénarios arrival-rate y tournent avec un nombre fixe d’utilisateurs, comme le signale son validateur de scripts. Lisez ces tests comme des tests fermés : après le coude, attendez-vous à une cadence de requêtes plate et à des temps de réponse qui montent.
Régime stationnaire. La phase de chauffe, les caches et l’autoscaling changent le taux de service pendant le test, donc comparez des paliers tenus assez longtemps pour se stabiliser.

FAQ

Faut-il écrire queueing theory ou queuing theory ? Les deux orthographes anglaises sont correctes et désignent le même domaine. L’article de Kingman de 1961 écrit « queueing time », tandis que la démonstration de Little, la même année, porte « Queuing Formula » dans son titre.

La théorie des files d’attente exige-t-elle des arrivées de Poisson ? Seulement pour les résultats exacts du modèle M/M/1. Les approximations G/G/1 comme la formule de Kingman utilisent la moyenne et la variabilité des intervalles entre arrivées et des temps de service, et la loi de Little ne suppose rien sur les lois.