Amdahl's Law und die Grenzen des Wachstums

Ein Suchdienst verarbeitet 350 Anfragen pro Sekunde. Der Server hat 16 Kerne, die CPU-Auslastung liegt bei 40 %. Der Traffic wächst – da müsste doch noch mehr gehen, denkt das Team.

Sie verdoppeln den Thread-Pool auf 400, damit mehr Requests gleichzeitig verarbeitet werden. Der Durchsatz steigt von 350 auf 410. Bei 800 Threads: 425. Bei 1.600: 430. Mehr Threads, fast kein Gewinn. Es ist zum Haareraufen.

Warum flacht die Kurve ab? Ein Thread-Dump – oder ein Blick auf das Wall-Clock-Profil im Profiler – liefert die Antwort: Hunderte Threads sind blockiert. Sie warten auf Connections, auf Locks, auf GC-Safepoints.

Nicht alles lässt sich bei der Verarbeitung von Requests vollständig parallelisieren. Jeder Thread braucht eine Connection aus dem Pool, und am anderen Ende serialisiert die Datenbank konkurrierende Zugriffe über Locks. Der In-Memory-Cache synchronisiert sich über einen Mutex. Und mehr Threads bedeuten mehr Objektallokation, also häufigere Garbage-Collection-Pausen – Stop-the-World-Phasen, in denen alle Threads stehen, egal wie viele Kerne verfügbar sind. Auch moderne Collectors wie ZGC oder Shenandoah eliminieren das nicht vollständig: Sie verkürzen die Pausen, aber serielle Phasen bleiben.

Der Suchdienst ist in unserem Szenario noch ein Monolith mit einer Datenbank. In verteilten Systemen kommen synchrone Calls zu Downstream-Services hinzu – dazu kommen wir noch in einem späteren Teil der Serie.

All das sind serielle Abschnitte – Teile des Systems, durch die jeder Thread einzeln hindurch muss. Und es gibt eine Formel, die exakt beschreibt, wie hart diese Abschnitte die Skalierung begrenzen.

Die Obergrenze

Ein Maler streicht eine Wohnung. Zwei Stunden klebt er Kanten und Steckdosen ab – das geht nur allein, weil jede Kante von der vorherigen abhängt. Theoretisch jetzt. Dann streicht er acht Stunden Wände. Für das Streichen kann er Hilfe holen: Zwei Maler schaffen es in vier Stunden, vier in zwei. Aber die zwei Stunden Abkleben bleiben. Selbst mit hundert Malern dauert der Job mindestens zwei Stunden – der serielle Anteil setzt die Untergrenze.

Gene Amdahl hat das 1967 in eine Formel gefasst. Er betrachtete ein Programm, das zum Teil sequenziell und zum Teil parallel ausgeführt werden konnte, und fragte: Wenn ich $n$ Prozessoren einsetze, wie viel schneller wird das Programm?

Die Antwort lässt sich in einem Satz zusammenfassen. Der maximale Speedup ist der Kehrwert des seriellen Anteils. Ist ein Zehntel des Programms seriell, sind es höchstens Faktor zehn. Ist ein Viertel seriell, höchstens Faktor vier. Egal, wie viele Prozessoren man einsetzt. Formal sieht das so aus:

\[S(n) = \frac{1}{s + \frac{1-s}{n}}\]

• $s$ ist der Anteil des Programms, der seriell ausgeführt werden muss – also nicht parallelisierbar ist.
• $n$ ist die Anzahl der parallelen Einheiten (Kerne, Threads, Instanzen, Maler,…).
• $S(n)$ ist der resultierende Speedup.

Was passiert, wenn $n$ gegen unendlich geht? Der Term $\frac{1-s}{n}$ geht gegen null, und es bleibt:

\[S(\infty) = \frac{1}{s}\]

Die Zahlen dazu:

Serieller Anteil $s$	Maximaler Speedup
50 %	2×
25 %	4×
10 %	10×
5 %	20×
1 %	100×

Einem System, das zu 25 % seriell ist, kann man beliebig viele Kerne oder Threads hinzufügen – schneller als Faktor 4 wird es nie. Das ist keine Frage der Implementierung, sondern eine harte Grenze. Wenn uns das nicht bewusst ist, werfen wir den Cloudanbietern das Geld hinterher. Ohne Sinn.

Eine häufige Falle ist dabei übrigens, $s$ aus dem Profiler der bereits parallelisierten Anwendung abzulesen statt an der ursprünglichen Ausführungszeit auf einem einzelnen Kern zu messen. Zeigt der Profiler bei 16 Kernen „5 % serielle Zeit”, heißt das nicht, dass $s = 0{,}05$ ist – die anderen 95 % sind ja bereits auf 16 Kerne verteilt. Der tatsächliche serielle Anteil liegt deutlich höher.

Amdahl’s Law beschreibt also eine Obergrenze für den Speedup – den besten Fall. In der Praxis kommt es oft schlimmer, weil Koordinationsaufwand zwischen parallelen Einheiten den Durchsatz nicht nur stagnieren lässt, sondern aktiv senken kann. Das Team beim Suchdienst hat Glück gehabt: Der Durchsatz stagnierte nur. In anderen Systemen – etwa wenn viele Threads um dieselben Datenbank-Rows konkurrieren oder Retry-Stürme das Netz fluten – bricht er sogar dramatisch ein.

Ursprünglich beschreibt das Gesetz den Speedup eines fixen Jobs. Derselbe Mechanismus greift aber auch dort, wo viele Requests pro Sekunde durch ein System laufen: Jeder Request ist ein fixer Job, der durch denselben Serialisierungspunkt muss – deshalb gilt Amdahl sowohl für die Latenz des einzelnen Requests als auch – via Little’s Law, das Parallelität, Durchsatz und Antwortzeit verknüpft – für den Gesamtdurchsatz. Genau das hat der Suchdienst bei 430 req/s erlebt, obwohl noch Kapazität auf den Kernen frei war.

Vertiefung: Das Universal Scalability Law – Amdahl ist ein hoffnungsloser Optimist

„The purpose of models is not to fit the data but to sharpen the questions.” – Sam Karlin, zitiert von Neil Gunther

Neil Gunther hat 1993 Amdahl’s Modell um einen zweiten Term erweitert: das Universal Scalability Law (USL). Neben dem seriellen Anteil $\sigma$ (Contention, entspricht Amdahls $s$) fügt Gunther einen Kohärenz-Parameter $\kappa$ (Crosstalk) hinzu:

\[C(n) = \frac{n}{1 + \sigma(n-1) + \kappa \times n \times (n-1)}\]

Der entscheidende Unterschied steckt im letzten Term: $\kappa \times n \times (n-1)$ wächst quadratisch mit der Anzahl der Einheiten. Wenn $\kappa = 0$ ist (kein Koordinationsaufwand), reduziert sich die Formel auf Amdahl’s Law. Sobald $\kappa > 0$, gibt es einen Punkt, ab dem der Koordinationsaufwand den Gewinn durch Parallelisierung übersteigt. Der Durchsatz sinkt.

Man kann sich das vorstellen wie einen übereifrigen Abteilungsleiter, der sich in alle Details einmischt. Amdahl’s Law sagt: Egal wie viele Mitarbeiter in der Abteilung sitzen, der Abteilungsleiter bleibt der Flaschenhals – mehr Leute helfen irgendwann nicht mehr. Gunther ergänzt: Die Mitarbeiter müssen sich auch noch untereinander abstimmen, wann wer mit welchem Anliegen zu ihm geht. Ab einer bestimmten Teamgröße verbringen sie mehr Zeit mit Koordination als mit Arbeit.

Beim Suchdienst ist der Effekt mild: Cache-Line-Bouncing, Context-Switching-Overhead und gelegentliche Lock Convoys kosten ein paar Prozent. Bei 1.600 Threads erreicht der Durchsatz sein Maximum von 435 req/s und fällt dann auf 415 – statt der 430, die reine Amdahl-Rechnung vorhersagt. Ärgerlich, aber kein Drama. Das liegt daran, dass die Threads hier die meiste Zeit auf I/O warten und sich dabei kaum in die Quere kommen. Das $\kappa$ des Suchdienstes ist klein.

In Systemen mit hohem Koordinationsaufwand sieht das anders aus. Ein Datenbankserver, der bei steigender Verbindungszahl mehr Zeit mit Lock-Management als mit Queries verbringt. Ein Message Broker, der bei wachsender Consumer-Zahl mehr mit Rebalancing als mit Auslieferung beschäftigt ist. Verteilte Caches, in denen jeder Schreibvorgang an alle Knoten propagiert werden muss. Dort ist $\kappa$ groß, und der Durchsatz bricht ein – nicht um Prozente, sondern auf einen Bruchteil des Maximums.

Die durchgezogene rote Kurve zeigt den Suchdienst: ein leichter Rückgang, der vor allem Geld kostet. Die gestrichelte rote Kurve zeigt, was bei starker Koordination passiert – der retrograde Bereich, in dem jede zusätzliche Einheit das System aktiv verschlechtert. Amdahl ist der Optimist unter den Skalierungsgesetzen. Das USL zeigt, wie weit die Realität davon abweichen kann.

Gunther fasst die drei Bremsen der Skalierung als 3 Cs zusammen: Concurrency (ideale Parallelität), Contention ($\sigma$ – Wartezeit auf geteilte Ressourcen) und Coherency ($\kappa$ – Aufwand, um einen konsistenten Zustand zwischen parallelen Einheiten herzustellen). Das ist ein nützlicher Diagnoserahmen: Wenn ein System nicht skaliert, liegt es entweder an zu wenig Parallelität, an Ressourcen-Kämpfen oder an Abstimmungsaufwand. $\sigma$ und $\kappa$ lassen sich aus Lasttest-Daten empirisch bestimmen – Kopplung wird damit vom Designprinzip zur messbaren Systemeigenschaft.

Was ist „seriell”?

Amdahl hatte Parallelrechner im Sinn: mehrere Prozessoren, ein Programm. Aber das Modell ist allgemeiner. Überall, wo parallele Einheiten auf geteilte Ressourcen treffen, gilt dasselbe Prinzip. Der serielle Anteil ist jede geteilte Ressource und jeder zentrale Koordinationspunkt:

• Ein Mutex, der eine geteilte Datenstruktur schützt, ist ein serieller Anteil. Mehrere Threads kämpfen um denselben Lock; der Durchsatz skaliert nicht mit der Thread-Zahl.
• Eine Datenbank, auf die alle Anfragen schreiben, ist ein serieller Anteil. Thread-Pool und Connection-Pool wachsen lassen ändert nichts – der Engpass liegt am anderen Ende der Connection, genau wie in der Einleitung beobachtet.
• Ein synchroner HTTP- oder gRPC-Call zu einem anderen Service ist ein serieller Anteil. Der Thread wartet blockierend auf die Antwort, egal wie viele Kerne lokal zur Verfügung stehen. Virtuelle Threads (Java 21) entschärfen das lokale Symptom – der Thread wartet, ohne den Pool zu blockieren – aber der serielle Anteil bleibt: Der Downstream-Service kann pro Zeiteinheit nur eine begrenzte Zahl von Anfragen verarbeiten. Der Anteil wächst linear mit der Anzahl der Downstream-Abhängigkeiten: Wer einen Monolithen in fünf synchron gekoppelte Services zerlegt, hat den seriellen Anteil pro Request verfünffacht, nicht reduziert – und gleichzeitig Verfügbarkeit und Antwortzeit verschlechtert.
• Selbst harmlos wirkende (Standard-)bibliotheken können serielle Anteile verstecken. Javas Math.random() nutzt intern einen geteilten Seed: Jeder Aufruf konkurriert in einer Schleife um denselben Wert – wer verliert, versucht es erneut, bis er drankommt. System.out.println() hält einen globalen Monitor. In .NET war Random vor Version 6 nicht einmal thread-safe. Die Lösung ist immer dieselbe: thread-lokale Alternativen wie ThreadLocalRandom oder Random.Shared. Aber der geteilte Default ist oft die Falle, in die man zuerst tappt. Man sieht es den Bibliotheken nicht an – nur ein Profiler hilft. Ein Tool, das aus mir unerfindlichen Gründen heute kaum noch in Gebrauch ist.

Aber was genau passiert am p99, wenn diese seriellen Abschnitte unter Last geraten?

Tail Latency

Neben der Deckelung des maximalen Durchsatzes hat der serielle Anteil noch eine weitere Auswirkung: Er treibt die Antwortzeit am Rand der Verteilung nach oben. Genau dort, wo die SLAs hängen.

Die Erklärung kommt aus Kingmans Formel – dem Zusammenspiel von Auslastung und Variabilität: Warteschlangen wachsen bei hoher Auslastung nicht gleichmäßig, sondern explosionsartig. Der Effekt steckt im Term $\frac{\rho}{1 - \rho}$, wobei $\rho$ die Auslastung des seriellen Abschnitts ist. Bei 80 % Auslastung hat dieser Term den Wert 4, bei 90 % bereits 9, bei 95 % liegt er bei 19. Steigt die Auslastung von 80 % auf 90 %, verdoppelt sich die mittlere Wartezeit etwa, der p99 vervierfacht sich.

Je mehr Threads um denselben Lock kämpfen, desto häufiger landet ein einzelner Request hinter einer langen Schlange – und genau dieser Request taucht im p99 auf. Ein weiteres Argument dafür, Monitoring nicht nur auf den Mittelwert auszurichten, sondern auf die Verteilung der Antwortzeiten.

Für Service-Landschaften verschärft sich der Effekt. Ein Request, der fünf Downstream-Services aufruft – ob parallel oder nacheinander –, trifft mit hoher Wahrscheinlichkeit mindestens einen davon in einem schlechten Moment. Mit jedem zusätzlichen synchronen Hop steigt die Wahrscheinlichkeit, in mindestens einer der Schlangen zu stecken. Formal: Bei $N$ Services, die jeweils in 1 % der Fälle langsam antworten, liegt die Wahrscheinlichkeit, mindestens einen langsamen Hop zu erwischen, bei $1 - 0{,}99^N$ – bei fünf Services also knapp 5 %, bei zehn Services fast 10 %.

Das p99 der Gesamtantwort wird damit vom p99 der einzelnen Services dominiert, nicht vom Mittelwert. Delimitrou und Kozyrakis haben das 2018 als Amdahl’s Law for Tail Latency formalisiert: Der serielle Anteil bestimmt nicht nur ob der Durchsatz wächst, sondern wie vorhersagbar das System bei Last antwortet.

Bei der Tail Latency fallen beide Gesetze zusammen: Zusätzliche Parallelität stößt an die Amdahl-Grenze, und gleichzeitig lässt die steigende Auslastung die Wartezeiten nach Kingman überproportional wachsen.

Das kann man auch praktisch nutzen: Wenn der Spread zwischen P50 und P99 bei steigender Last auseinanderläuft, ist das ein empirischer Hinweis darauf, dass serielle Abschnitte unter Contention geraten. Bei rein paralleler Verarbeitung wären die Antwortzeiten konsistent – manche Requests schnell, andere vom gleichen Typ zehnmal langsamer bedeutet: Manche landen vor einer leeren Queue, andere müssen warten. Der wachsende P99/P50-Quotient zeigt, dass Serialisierung langsam problematisch wird – noch bevor man den Profiler anwirft.

Vom Thread zum Team

Das alles betrifft eine einzelne Instanz – aber der Effekt wiederholt sich auf jeder Ebene. Innerhalb einer Instanz teilen sich Threads Caches, Connection-Pools und Lock-geschützte Datenstrukturen. Eine Ebene tiefer parallelisiert die Datenbank zwar über Kerne, serialisiert Schreibzugriffe aber über Locks; ACID erzwingt das. Und sobald mehrere Instanzen desselben Service auf dieselbe Datenbank zugreifen, wandert der serielle Anteil nur eine Ebene tiefer – worauf wir in den nächsten beiden Teilen näher eingehen werden .

Das Prinzip endet auch nicht bei Technik. Gemeinsame Codebases und zentrale Entscheidungsträger bremsen Teams genauso wie Locks die Threads. Die theoretischen Grundlagen der Skalierbarkeit gelten für alle möglichen Arten von Parallelität – von der Hardware über die Software bis zur Organisation.

Die Konsequenz ist stets dieselbe: Loose Coupling – minimale geteilte Ressourcen, maximale Autonomie. Die extreme Variante, Shared-Nothing, eliminiert geteilte Ressourcen vollständig: kein gemeinsamer Speicher, keine gemeinsame Datenbank, keine gemeinsamen Locks. In der Praxis ist das ein Ideal, selten vollständig erreicht. Jeder Schritt dorthin verschiebt die Amdahl-Grenze nach oben, weil die seriellen Anteile reduziert werden.

Architektur schlägt Hardware

Zurück zum Suchdienst. Das Team kennt die Serialisierungspunkte – Connection-Pool, Cache-Mutex, DB-Locks – aber wie groß ist der serielle Anteil tatsächlich? Um das herauszufinden, deployt es den Service auf verschiedenen Instanzgrößen der AWS-c7g-Familie und fährt jeweils denselben Lasttest bis zur Sättigung:

Instanz	vCPUs	Durchsatz (Sättigung)	Speedup vs. 2 Kerne	Preis/Stunde
c7g.large	2	175 req/s	1,0×	1×
c7g.xlarge	4	260 req/s	1,5×	2×
c7g.2xlarge	8	345 req/s	2,0×	4×
c7g.4xlarge	16	430 req/s	2,5×	8×

Das Muster ist eindeutig: Jede Verdopplung der Kerne bringt weniger als die vorherige. Das Team fittet die Amdahl-Kurve an die Messdaten und landet bei $s \approx 0{,}20$ – rund ein Fünftel der Verarbeitungszeit ist seriell. Damit liegt die theoretische Obergrenze für den Speedup bei fünf, egal wie viele Kerne man einsetzt. Auf den aktuellen 16 Kernen ergibt die Formel $S(16) = \frac{1}{0{,}20 + 0{,}80/16} = 4{,}0\times$ – das passt zu den gemessenen 430 req/s.

Die naheliegende Frage: Was passiert, wenn man einfach eine größere Maschine kauft? Die Tabelle zeigt es bereits: Jede Verdopplung der Kerne verdoppelt den Preis, aber der Durchsatz wächst immer langsamer. Von 16 auf 32 vCPUs – $S(32) = 4{,}4\times$ – wären das 11 % mehr Leistung für 100 % mehr Geld. Bei 64 Kernen: noch einmal 7 % obendrauf. Das muss man mögen. Und irgendwann endet die Auswahl – bei AWS bei 64 vCPUs, bei GCP bei 176. Dann gibt es schlicht keine größere Maschine mehr.

Die lohnendere Investition: den seriellen Anteil senken. Bessere Indizes, asynchrone Verarbeitung, Lock-freie Datenstrukturen – wer $s$ von 20 % auf 10 % drückt, verdoppelt die Speedup-Obergrenze von fünf auf zehn. Auf denselben 16 Kernen steigt der rechnerische Speedup von 4,0× auf 6,4×. Architektur schlägt Hardware.

Für den Suchdienst heißt das: Die Instanz ist am Ende. Mehr Kerne bringen wenig, mehr Threads nichts. Der naheliegende nächste Schritt wäre, einfach mehr Instanzen danebenzustellen. Aber der serielle Anteil verschwindet nicht – er wandert.

---

Quellen

• Amdahl (1967) – Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Spring Joint Computer Conference Proceedings, Vol. 30, 483–485.
• Gustafson (1988) – Reevaluating Amdahl’s Law. Communications of the ACM, 31(5), 532–533.
• Gunther (1993) – Practical Performance Analyst. McGraw-Hill. → Universal Scalability Law
• Gunther (2007) – Guerrilla Capacity Planning. Springer. → USL formalisiert und angewendet
• Delimitrou & Kozyrakis (2018) – Amdahl’s Law for Tail Latency. Communications of the ACM, 61(8), 65–72.
• Abbott & Fisher (2015a) – The Art of Scalability. 2nd ed., Chapter 22. Addison-Wesley.

Kommentare