Warteschlangentheorie: was sie ist und warum Latenz steigt

Die Warteschlangentheorie (englisch queueing theory) ist die Mathematik der Warteschlangen: Aus der Rate, mit der Arbeit eintrifft, der Dauer jedes Auftrags und der Zahl der Server sagt sie voraus, wie lange Aufträge warten und wie lang die Schlange wird. Für Software ist ihr nützlichstes Ergebnis, dass die Antwortzeit bei mittlerer Last langsam und dann steil wächst, wenn ein Server sich 100 % Auslastung nähert. Im einfachsten Modell antwortet ein Server, der 90 % der Zeit beschäftigt ist, im Schnitt zehnmal langsamer als ein Server im Leerlauf.

Die Zahlen unten sind Arithmetik aus Standardformeln, mit einem Skript nachgerechnet, ohne Testlauf dahinter. Die Quellen wurden am 1. November 2026 geprüft.

Das sind Mittelwerte für die M/M/1-Warteschlange: ein Server, Poisson-Ankünfte und exponentialverteilte Bedienzeiten.

Was ist Warteschlangentheorie?

Sie ist das Teilgebiet der Wahrscheinlichkeitsrechnung, das Arbeit modelliert, die eintrifft, wartet und bedient wird. Eine Warteschlange wird durch ihre Ankünfte, ihre Bedienzeiten, ihre Zahl der Server und ihre Warteschlangendisziplin beschrieben, also die Reihenfolge, in der wartende Aufträge drankommen.

Larson und Odonis Urban Operations Research, ein frei zugänglicher MIT-Text, nennt Bankschalter, Supermarktkassen und Mautstellen als klassische Fälle. Ein Webserver passt in denselben Rahmen: Anfragen treffen ein, Threads oder Kerne bedienen sie, und der Rest wartet in einer Schlange.

Woher kommt die Warteschlangentheorie?

Aus der Telefonvermittlung, wo A. K. Erlang die ersten Ergebnisse für die Kopenhagener Telefongesellschaft erarbeitete.

Erlangs Aufsatz von 1909 zeigte, dass zufällig eingehende Anrufe der Poisson-Verteilung folgen, und seine Formel für Verluste und Wartezeiten von 1917 nutzten bald Telefongesellschaften in vielen Ländern, so die MacTutor-Biografie. David Kendalls Aufsatz von 1953, Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain, führte die bis heute gebräuchliche Notation ein, wie Geoffrey Grimmetts Darstellung seines Werks festhält. Littles Beweis von L = λW und Kingmans Ergebnisse zu hoher Last folgten 1961.

Was bedeutet die Kendall-Notation wie M/M/1?

Sie benennt eine Warteschlange in drei Teilen, A/S/c: die Verteilung der Abstände zwischen Ankünften, die der Bedienzeiten und die Zahl der Server. M/M/1 heißt zufällige Ankünfte, exponentielle Bedienzeiten und ein Server.

M steht für memoryless, also gedächtnislos (Poisson-Ankünfte oder exponentielle Zeiten), D für deterministisch und G für general, also eine beliebige Verteilung: M/D/1 ist ein Server mit konstanter Bedienzeit.

Wie wächst die Antwortzeit mit der Auslastung?

In einer M/M/1-Warteschlange ist die mittlere Zeit im System W = 1/(μ − λ), also S/(1 − ρ). Nähert sich die Auslastung ρ dem Wert 1, wächst W unbegrenzt.

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

Larson und Odoni leiten das für eine Telefonzentrale mit einer Vermittlungskraft her und zeigen, dass es bei ρ ≥ 1 keinen stationären Zustand gibt: Die Schlange wächst immer weiter. Dieselbe Quelle zeigt, dass die Zeit im System exponentialverteilt ist. Jedes Perzentil wächst also mit demselben Faktor 1/(1 − ρ), und das p95 liegt bei etwa dem Dreifachen des Mittelwerts: 600 ms in der Zeile 0,9 oben.

Warum zeigt die Latenz einen Knick, bevor die CPU 100 % erreicht?

Weil eine Anfrage immer dann wartet, wenn sie den Server beschäftigt vorfindet, und das geschieht mit steigender Auslastung öfter. Unter M/M/1-Annahmen hat sich die Antwortzeit bei 50 % Auslastung schon verdoppelt.

Die Ressource, die sättigt, kann auch ein Connection-Pool, ein Datenbank-Lock oder eine Event-Loop mit nur einem Thread sein, und die am stärksten ausgelastete bestimmt die Kurve. Wegen des frühen Knicks liegt die Zielauslastung deutlich unter 100 %. Rechnen Sie vom Latenzbudget zurück: Mit S = 20 ms und einem Mittelwertziel von 100 ms erlaubt die Tabelle etwa 80 %, ein Ziel von 60 ms etwa 67 %, bevor Lastspitzen ihren Teil verlangen.

Die Kapazitätsanzeige von LoadFocus gruppiert einen abgeschlossenen Lauf nach der Zahl aktiver virtueller Benutzer und nennt die letzte Stufe, die hielt, bevor die Fehlerrate 1 % überschritt oder das p95 über das Doppelte der besten Stufe stieg, sofern sich keine höhere Stufe wieder erholte. Dafür braucht sie einen Lauf mit einem einzigen Lastgenerator, der mindestens drei Laststufen hochfährt, wobei die höchste mindestens doppelt so hoch ist wie die niedrigste. Nach der Rechnung oben greift die Verdopplung knapp oberhalb von 50 % Auslastung, wenn die leichteste Stufe den Engpass fast im Leerlauf ließ; hatte die leichteste Stufe ihn schon auf ρ0 ausgelastet, greift sie später, unter M/M/1 oberhalb von (1 + ρ0)/2.

Warum zählt Streuung so viel wie Auslastung?

Warteschlangen entstehen durch Zufall: Ankünfte in Schüben und gelegentlich langsame Aufträge. Unter hoher Last wächst die Wartezeit mit der Streuung beider, multipliziert mit einem Term ρ/(1 − ρ).

Kingmans Aufsatz von 1961, The single server queue in heavy traffic, zeigt, dass bei einer Verkehrsintensität eines einzelnen Servers nahe 1 die Schlange lang und die Wartezeit annähernd exponentialverteilt ist. Vorlesungsunterlagen der TU Eindhoven und des Technion geben eine Näherung für ihren Mittelwert an (das Technion nennt sie Allen-Cunneen-Näherung; weithin bekannt ist sie auch als Kingman-Formel):

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

Wq ist die Wartezeit, bevor die Bedienung beginnt, und ca, cs sind die Variationskoeffizienten. Exponentielle Zeiten haben c² = 1, was die M/M/1-Wartezeit von 9S bei 90 % Auslastung ergibt. Eine konstante Bedienzeit halbiert sie auf 4,5S; cs² = 4, wie es eine Mischung aus Cache-Treffern und langsamen Datenbankaufrufen erzeugen kann, hebt sie auf 22,5S. Gleichmäßiger synthetischer Verkehr streut weniger als der Produktivbetrieb, also zeigt ein Test meist weniger Warteschlange, als echte Lastspitzen erzeugen.

Wie helfen mehr Server (M/M/c)?

Mehrere Server mit einer gemeinsamen Warteschlange fangen zufällige Schübe viel besser ab als dieselben Server mit je einer eigenen, sodass jeder Server bei gleicher Wartezeit stärker ausgelastet sein kann.

Nach Larson und Odonis M/M/m-Formeln beträgt W bei 90 % Auslastung jedes Servers 10S für einen Server, 5,3S für zwei mit gemeinsamer Schlange und 3,0S für vier. Vier Instanzen hinter einem Balancer, der eine freie wählt, verhalten sich wie der letzte Fall; vier, die jeweils ein zufälliges Viertel des Verkehrs bekommen, wie getrennte M/M/1-Warteschlangen mit 10S.

Wie passt Little’s Law dazu?

Little’s Law, L = λW, verknüpft die durchschnittliche Zahl der Anfragen in einem System mit ihrer Ankunftsrate und ihrer Verweilzeit, unabhängig von den Verteilungen. Die Warteschlangentheorie liefert W, und Little’s Law macht daraus L.

In der Zeile 0,9 bedeuten 45 Anfragen pro Sekunde bei W = 200 ms im Schnitt 9 Anfragen im System. Unser Artikel zu Little’s Law nutzt dasselbe Gesetz, um Lasttests zu dimensionieren und zu prüfen.

Wo versagen diese Modelle im Lasttest?

Sie setzen einen offenen Strom unabhängiger Ankünfte und einen stationären Zustand voraus. Ein Test mit fester Zahl virtueller Benutzer ist ein geschlossenes System, in dem die Ankünfte langsamer werden, sobald die Antworten es werden.

• Geschlossene Tests. Bei N virtuellen Benutzern sind höchstens N Anfragen im System, also fällt die Anfragerate dort, wo eine offene Schlange wachsen würde, und Think Time senkt sie weiter. Unser Artikel zum offenen vs geschlossenen Lastmodell erklärt, warum das eine Sättigung verbirgt.
• LoadFocus führt k6-Skripte aus, aber Arrival-Rate-Szenarien laufen dort mit einer festen Zahl von Benutzern, worauf der Skript-Validator hinweist. Lesen Sie solche Läufe als geschlossene Tests: Hinter dem Knick sind eine flache Anfragerate und steigende Antwortzeiten zu erwarten.
• Stationärer Zustand. Aufwärmphase, Caches und Autoscaling ändern die Bedienrate während des Laufs, also vergleichen Sie Stufen, die lange genug gehalten wurden.

FAQ

Heißt es queueing theory oder queuing theory? Beide englischen Schreibweisen sind korrekt und bezeichnen dasselbe Gebiet. Kingmans Aufsatz von 1961 schreibt „queueing time“, während Littles Beweis aus demselben Jahr „Queuing Formula“ im Titel trägt.

Braucht die Warteschlangentheorie Poisson-Ankünfte? Nur für exakte M/M/1-Ergebnisse. G/G/1-Näherungen wie die Kingman-Formel arbeiten mit Mittelwert und Streuung der Ankunftsabstände und Bedienzeiten, und Little’s Law braucht keine Annahme über die Verteilungen.

Weiterlesen

• Little’s Law im Lasttest: Tests dimensionieren und prüfen
• Offenes vs geschlossenes Lastmodell: welches passt wann?
• Durchsatz vs. Latenz: wie sie unter Last zusammenhängen
• Tail-Latenz: was sie ist und wie man sie misst
• Think Time im Lasttest: was sie ist und wie man sie wählt

Die technischen Aussagen in diesem Artikel wurden nicht unabhängig geprüft.