Kingmans Formel

Kingmans Formel

Foto: Denys Nevozhai @ Unsplash - Unsplash-Lizenz

Der Suchdienst eines Online-Shops, vor kurzem noch ein Sorgenkind: Unter Last brach er zusammen, weil der Connection-Pool zur Datenbank viel zu klein dimensioniert war. Das Team hatte den Fehler gefunden, den Pool von zehn auf fünfzig Verbindungen hochgezogen, Lasttests bestanden. Problem gelöst.

Zwei Monate später.

Der Shop wächst. Mehr Produkte im Katalog, mehr Kunden, der Traffic hat sich auf 350 Anfragen pro Sekunde mehr als verdreifacht und die wachsende Datenmenge macht jeden Datenbankzugriff etwas langsamer. DB-Zugriffe, die vor zwei Monaten 70 Millisekunden dauerten, brauchen jetzt 100. Der Connection-Pool läuft bei rund 70% Auslastung.

Newsletter versendet das Team vorerst keine mehr: Die Reserve wäre zu dünn. Das Dashboard zeigt eine mittlere Antwortzeit von 120 Millisekunden. Leicht gestiegen, aber eine Query-Optimierung steht auf der Roadmap. Die nächsten Maßnahmen sind auch bereits eingeplant, aber vorher muss noch ein wichtiges Feature umgesetzt werden.

Dann melden sich die ersten Kunden: Die Suche sei „ewig langsam”. Das Team schaut aufs Dashboard: 120 Millisekunden, wie erwartet. Also: Problem des Kunden, nicht des Service. Bis sich die Beschwerden häufen und jemand auf die Idee kommt, genauer in die Logs zu schauen.

Warum der Mittelwert lügt

Die Verwendung von Mittelwerten im Monitoring ist irreführend. Er nimmt eine breite Verteilung und macht eine harmlose Zahl daraus. 120 Millisekunden – das klingt nach einem Service, der halt etwas langsamer geworden ist. Aber der Mittelwert glättet alles: die schnellen Cache-Hits bei 30 Millisekunden genauso wie die teuren Queries bei 400. Repräsentativ ist er für keinen der beiden Fälle.

Perzentile

Ein Perzentil beschreibt die Grenze, unter der ein bestimmter Anteil aller Messwerte liegt. p95 = 350 ms heißt: 95% der Anfragen sind schneller – aber jede zwanzigste braucht länger.

Während der Mittelwert Ausreißer glättet, machen Perzentile sie sichtbar. p95 und p99 sind deshalb die wichtigeren Werte im Monitoring: Sie zeigen, was die langsamsten Nutzer erleben.

Erst das Histogramm der Antwortzeiten zeigt, was passiert: Die meisten Anfragen sind schnell: 30 bis 50 Millisekunden, Cache-Hits, die nie die Datenbank berühren. Aber ein langer Schwanz zieht sich bis 500 Millisekunden und darüber hinaus, verursacht durch Wildcard-Suchen und Facettenberechnungen auf einem Datenbestand, der in zwei Monaten deutlich gewachsen ist. Der Median liegt bei 80 Millisekunden, der Mittelwert bei 120 – und das p95 bei 350. Jede zwanzigste Anfrage ist fast dreimal so langsam wie der Mittelwert suggeriert.

Wer nur den Mittelwert beobachtet, bemerkt das Problem erst, wenn die Kunden anrufen.

5% klingt nach wenig. Aber ein Nutzer stellt nicht eine einzige Anfrage – er durchsucht, filtert, blättert. Bei zehn Seitenaufrufen pro Session liegt die Wahrscheinlichkeit, mindestens einen langsamen Request zu erleben, bei:

\[1 - 0{,}95^{10} \approx 40\%\]

Aus „jede zwanzigste Anfrage” wird „fast jeder zweite Nutzer”. Kein Wunder, dass sich die Beschwerden häufen.

Und es kommt schlimmer. Die langsamen Anfragen sind nicht nur ein Problem für die Nutzer, die sie auslösen – sie sind ein Problem für alle. Der Suchdienst hat einen Pool mit fünfzig Datenbankverbindungen. Bei niedriger Auslastung sind die meisten davon frei. Ein langsamer Request – 400 Millisekunden statt 30 – belegt seine Verbindung dreizehnmal länger, aber es sind genug andere verfügbar. Die Schwankung wird absorbiert.

Bei 70% Auslastung sieht das anders aus: Rund 35 der 50 Verbindungen sind ständig belegt. Wenn jetzt mehrere langsame Requests gleichzeitig eintreffen – und bei 350 Anfragen pro Sekunde ist das keine Frage des Ob, sondern des Wann – halten sie ihre Verbindungen dreizehn­mal länger als ein Cache-Hit. Die fünfzehn freien Verbindungen schmelzen schnell zusammen. Neue Anfragen finden keine freie Verbindung mehr und stauen sich auf. Unter den aufgestauten Requests ist mit hoher Wahrscheinlichkeit wieder ein langsamer – und die Schlange wächst weiter. Die Schwankungen können sich nicht mehr auflösen, sie akkumulieren.

Jede Häufung langsamer Requests erzeugt eine Welle, die alle nachfolgenden Anfragen trifft.

Das Ergebnis ist eine Kurve, die im letzten Post schon aufgetaucht ist: lange flach, dann steil – der Hockeyschläger. Die Frage ist: Lässt sich dieser Effekt quantifizieren?

Die Formel hinter dem Hockeyschläger

1961 – im selben Jahr, in dem John Little seine Warteschlangenformel bewies – formulierte der britische Mathematiker John Kingman eine Näherung für genau dieses Phänomen. Kingman fragte: Wie lang ist die Wartezeit in einer Warteschlange, wenn die Bedienzeiten nicht konstant sind?

Exkurs: Wenn man es genau nimmt - und Mathematiker neigen dazu - ist Kingmans Formel auf unseren Fall nicht anwendbar, denn Kingman beschreibt eine einzelne Bedienstelle, während wir durch den Pool mehrere Bedienstellen haben. Warum die Formel trotzdem für Pools mit vielen Verbindungen taugt, erklärt der Exkurs G/G/1 vs. G/G/c – Kingman und mehrere Bedienstellen.

Seine Antwort zerlegt die Wartezeit in drei Faktoren:

\[\text{Wartezeit} \approx V \times \frac{\rho}{1 - \rho} \times S\]

1. S: die mittlere Servicezeit. In unserem Suchdienst: 120 Millisekunden, 100 davon in der Datenbank, der Rest CPU-Arbeit.

2. ρ/(1−ρ): der Auslastungsfaktor (ρ, „Rho”, steht für den Anteil der genutzten Kapazität). Bei 50% Auslastung ergibt das 1. Bei 80% schon 4. Bei 90% sind es 9. Bei 95%: 19. Dieser Faktor ist der Grund für die Kurve: er wächst nicht linear, sondern explodiert.

3. V: die Variabilität der Servicezeiten, ein Maß dafür, wie stark die Servicezeiten um ihren Mittelwert streuen. V = 0 bedeutet: alle Anfragen dauern exakt gleich lang, keine Schwankungen, keine Warteschlange (abgesehen von der Servicezeit selbst). V = 1 wäre exponentiell verteilte Zeiten, der klassische Worst Case. Für den Suchdienst mit seiner Mischung aus Cache-Hits und Wildcard-Suchen liegt V bei etwa 0,5.

Die gesamte Antwortzeit – von der Anfrage bis zur Antwort – ergibt sich aus Servicezeit plus Wartezeit:

\[\begin{align}Antwortzeit &= S + \text{Wartezeit} \\ &= S \times \left(1 + V \times \frac{\rho}{1 - \rho}\right)\end{align}\]

Oder als Vielfaches der Servicezeit:

\[\frac{Antwortzeit}{S} = 1 + V \times \frac{\rho}{1 - \rho}\]

Der Faktor 1 ist die reine Servicezeit: die Zeit, die jede Anfrage braucht, selbst wenn die Warteschlange leer ist. Alles darüber kommt vom Warten.

Rechnen wir das für den Suchdienst durch, mit Variabilität V = 0,5 und Servicezeit S = 120 ms:

Auslastung	ρ/(1−ρ)	Wartezeit	Antwortzeit
50%	1	60 ms	180 ms
80%	4	240 ms	360 ms
90%	9	540 ms	660 ms
95%	19	1.140 ms	1.260 ms

Bei 50% Auslastung: unauffällig. Bei 80%: Die Antwortzeit hat sich verdreifacht. Bei 95%: über eine Sekunde – für einen Service, der einzelne Anfragen in 120 Millisekunden bearbeiten kann. Die Wartezeit ist fast zehnmal so hoch wie die Servicezeit.

Hätte jemand das Team vor zwei Monaten gefragt, ob es ein Variabilitätsproblem hat, hätte die Antwort gelautet: Ein was?

Nicht ein plötzlicher Zusammenbruch, sondern ein schleichender Anstieg, der ab 80% spürbar wird und ab 90% unkontrollierbar.

Und jetzt der Punkt, den die Tabelle allein nicht zeigt: Die Variabilität bestimmt, wie steil die Kurve wird. Bei V = 0,1 – einem Service mit sehr gleichförmigen Servicezeiten – steigt die Antwortzeit bei 95% Auslastung auf knapp das Dreifache der Servicezeit. Unangenehm, aber beherrschbar. Bei V = 0,5 sind es über zehn. Der Unterschied zwischen einem homogenen und einem heterogenen Workload ist nicht graduell – er ist der Unterschied zwischen einem stabilen Service und einem, der unter Last zusammenbricht.

Phantomstaus

Wer jemals auf einer Autobahn im Stau gestanden hat, obwohl es weder eine Baustelle noch einen Unfall gab, hat Kingman erlebt – ohne es zu wissen.

Der Verkehrsforscher Martin Treiber beschreibt das Phänomen in Traffic Flow Dynamics: Auf einer vollen Autobahn reicht eine kleine Störung – ein Fahrer, der kurz bremst, weil er sein Handy fallen lässt – für eine Kettenreaktion. Der Hintermann bremst stärker, der nächste noch stärker. Die Bremswelle pflanzt sich nach hinten fort, und Kilometer weiter stehen Autos, die nie erfahren werden, was der Auslöser war. Phantomstaus.

Die Parallele ist kein Zufall. Sowohl Verkehrsfluss als auch Warteschlangen unterliegen derselben Mathematik: Hohe Auslastung plus Schwankungen gleich überproportionale Verzögerungen.

Auf Autobahnen mit Tempolimit sind Phantomstaus daher auch seltener als auf Autobahnen ohne. Nicht weil das Tempolimit den Durchsatz erhöht, sondern weil es die Geschwindigkeitsvarianz senkt. Wenn alle ähnlich schnell fahren, werden die Schwankungen kleiner, die Bremswellen schwächer. Ein Tempolimit ist, in der Sprache von Kingman, eine Reduktion von V. In der Sprache vieler Autofahrer ist es eine Einschränkung der Freiheit, aber das ist ein anderes Thema.

Aber zurück zum Suchdienst. Nicht der Durchsatz ist das Problem – der reicht laut Little’s Law. Das Problem ist die Streuung der Servicezeiten. Die Mischung aus 30-Millisekunden-Cache-Hits und 400-Millisekunden-Wildcard-Suchen erzeugt Phantomstaus in der Warteschlange.

Was tun?

Kingmans Formel hat drei Faktoren. Jeder lässt sich angreifen.

Variabilität senken (V reduzieren)

Der wirksamste Hebel – und der am häufigsten übersehene. Wenn die Servicezeiten weniger streuen, sinkt die Wartezeit überproportional. Für den Suchdienst gibt es mehrere Ansätze:

• Workloads aufteilen. Cache-gestützte Standardsuchen und aufwendige Facetten-Queries auf verschiedene Service-Instanzen oder sogar verschiedene Services verteilen. Jeder einzelne Service hat dann eine homogenere Lastverteilung: niedrigeres V, stabilere Antwortzeiten. In der Sprache der Skalierbarkeit ist das die Y-Achse, funktionale Dekomposition. .

• Timeouts als Variabilitätsbegrenzer. Ein Timeout bei 500 Millisekunden kappt den Schwanz der Verteilung. Nicht jede Anfrage wird beantwortet – aber die, die beantwortet werden, stehen nicht mehr minutenlang in der Warteschlange hinter einem Monster-Query. Kombiniert mit einem Circuit Breaker schützt das den Service vor kaskadierenden Verzögerungen. Leider ist das nicht immer eine Option.

• Caching gezielt erweitern. Nicht die Top 100, sondern die Top 5.000 Suchanfragen cachen. Der Long Tail wird kürzer, die Verteilung schmaler. Allerdings hat Caching seine eigenen Grenzen.

Exkurs: Zipf’s Law und die Grenzen des Cachings Warum selbst ein großer Cache irgendwann nicht mehr hilft – und was Zipf’s Law damit zu tun hat.

Servicezeit senken (S reduzieren)

Little’s Law treibt diesen Hebel: schnellere Queries, bessere Indizes, weniger Datenbankzugriffe pro Anfrage.

Jede Millisekunde, die man hier spart, wirkt doppelt: einmal direkt in der Servicezeit und einmal multiplikativ in der Wartezeit. Senkt das Team in unserem Szenario die mittlere Servicezeit von 120 auf 80 Millisekunden – etwa durch bessere Indizes auf dem gewachsenen Datenbestand – sinkt die Antwortzeit bei 80% Auslastung von 360 auf 240 ms.

Ein Drittel weniger, obwohl die Servicezeit nur um 40ms gesunken ist, denn Kingman verstärkt die Wirkung von Optimierungen.

Auslastung senken (ρ reduzieren)

Der offensichtlichste, aber auch teuerste Hebel ist es, mehr Kapazität bereitzustellen als rechnerisch nötig. Kingman liefert die Begründung dafür, nicht 95% Auslastung als Zielwert zu nehmen, sondern bewusst unter 80% zu bleiben. Der Unterschied zwischen 80% und 95% ist – bei V = 0,5 – ein Faktor 3,5 in der Antwortzeit. Kapazitätspuffer sind kein Luxus, sie sind die billigste Versicherung gegen den Hockeyschläger.

Wer wissen will, wie viel Kapazität „genug“ ist, braucht beide Formeln aus dieser Serie: Little’s Law dimensioniert den Pool – wie viele Verbindungen für diesen Durchsatz? Kingman sagt, wie viel Puffer darüber hinaus nötig ist, damit die Antwortzeiten unter Last nicht explodieren.

Im Monitoring zeigt sich Kingman, bevor es wehtut. Wenn ein System weit genug vom Sättigungspunkt entfernt ist, bleiben die Antwortzeiten bei steigender Last annähernd stabil – oder sinken sogar, weil sich Caches aufwärmen. Steigen die Antwortzeiten im Tagesverlauf dagegen mit der Last, ist das bereits ein Warnsignal: Das System arbeitet in einem Bereich, in dem Kingman zuschlägt. Dafür muss nicht einmal die Auslastung bekannt sein – der Trend der Antwortzeiten unter steigender Last verrät, wie nah man dem Sättigungspunkt bereits ist.

Exkurs: Backpressure – Wenn Systeme Nein sagen lernen Wenn weder V senken noch S senken schnell genug helfen, bleibt: dem System beibringen, Requests abzulehnen. Autobahnauffahrten mit Ampel funktionieren nach demselben Prinzip.

Aber alle drei Hebel – V, S und ρ – beschreiben das Verhalten einer einzelnen Instanz, eines einzelnen Service. Die naheliegende Reaktion auf ein System am Limit ist: mehr Parallelität. Mehr Threads, mehr Kerne, irgendwann mehr Instanzen. Intuitiv erwartet man: doppelt so viele Ressourcen gleich doppelter Durchsatz. Die Realität ist etwas weniger kooperativ. Warum das so ist, welche seriellen Abhängigkeiten den theoretisch möglichen Gewinn auffressen und wo die harte mathematische Grenze liegt, ist das Thema des folgenden Teils dieser Serie über Amdahl’s Law.

---

Quellen

• Kingman (1961) – The single server queue in heavy traffic. Mathematical Proceedings of the Cambridge Philosophical Society, 57(4).
• Hopp & Spearman (2011) – Factory Physics. 3rd ed. Waveland Press. Kap. 8 (Variability, VUT equation).
• Treiber & Kesting (2013) – Traffic Flow Dynamics: Data, Models and Simulation. Springer. Kap. 10–12.
• Little (1961) – A Proof for the Queuing Formula: L = λW. Operations Research, 9(3), 383–387.

Kommentare