Stackrig

Startseite Blog

erklärt die Rechnung aus dem Paper von Dean und Barroso und das Live-Modell veröffentlicht

Warum macht Fan-out schnelle Dienste langsam?

Eine Anfrage, die auf 100 parallele Aufrufe wartet, ist so langsam wie der langsamste davon: die Rechnung aus dem Paper von Dean und Barroso und derselbe Effekt in einem Design, das du ausführen kannst.

Kurze Antwort: Eine Anfrage, die parallel auf viele Aufrufe wartet, ist so langsam wie der langsamste davon. Wenn einer von hundert Aufrufen langsam ist, trifft eine Anfrage mit 100 Aufrufen in 63 % der Fälle auf einen langsamen. Der seltene Fall des einzelnen Aufrufs ist der Normalfall der Anfrage.

Im Live-Modell hat ein Aufruf an einen Dienst mit 10 ms Arbeit einen Median von etwa 9 ms und ein p99 von etwa 50 ms. Eine Anfrage, die 100 solche Aufrufe parallel macht, hat einen Median von etwa 55 ms: Ihr typischer Fall ist langsamer als das langsamste 1 % der einzelnen Aufrufe. Was hilft, sind weniger Aufrufe pro Anfrage und eine geringere Streuung jedes Aufrufs, lange bevor mehr Server helfen.

Eine Suchseite fragt hundert Index-Shards ab. Eine Produktseite fragt nach dem Preis, dem Lagerbestand, den Bewertungen und zwanzig Empfehlungen. Ein Feed fragt nach den Beiträgen von fünfzig Konten. Jeder dieser Dienste sieht auf seinem eigenen Dashboard gesund aus: Median 7 ms, p99 50 ms. Die Seite ist trotzdem langsam. Jeffrey Dean und Luiz André Barroso haben in „The Tail at Scale“ (2013) beschrieben, warum, mit Zahlen aus Googles Diensten. Diese Seite geht die Rechnung durch und zeigt dann denselben Effekt in einem Design, das du öffnen kannst.

Die Rechnung: Ein langsamer Aufruf genügt

Nenn eine Antwort „langsam“, wenn sie zum langsamsten Anteil p der Antworten eines Dienstes gehört. Eine Anfrage, die N Antworten braucht und auf alle wartet, ist langsam, wenn mindestens eine Antwort es ist:

slow share = 1 − (1 − p)^N
Berechnet: der Anteil der Anfragen, die auf mindestens einen langsamen Aufruf treffen, wenn die Aufrufe unabhängig voneinander langsam sind. Das Paper nennt zwei dieser Zellen: 63 % für 100 Server bei einer langsamen Antwort von 100 und „almost one in five“ für 2.000 Server bei einer von 10.000.
Parallele Aufrufe1 von 100 Aufrufen ist langsam1 von 1.0001 von 10.000
11 %0,1 %0,01 %
109,6 %1 %0,1 %
10063 %9,5 %1 %
1.000100 %63 %9,5 %
2.000100 %86 %18 %

Andersherum gelesen sagt die Tabelle, in welchem Teil der Latenzkurve eines Dienstes seine Aufrufer leben. Der Median einer Anfrage mit 100 parallelen Aufrufen ist das 99,3. Perzentil des einzelnen Aufrufs, und ihr p99 ist das 99,99. Perzentil des einzelnen Aufrufs. Ein Team, das das p99 seines Dienstes beobachtet, beobachtet eine Zahl, die ein Aufrufer mit breitem Fan-out längst hinter sich gelassen hat: Für diesen Aufrufer zählt das p99.99 des Dienstes.

Was Google gemessen hat

Das Paper berichtet von einem echten Dienst, der eine Anfrage durch einen Baum von Servern an eine sehr große Zahl von Blättern schickt. An der Wurzel gemessen antwortet ein einzelnes Blatt im 99. Perzentil innerhalb von 10 ms. Wartet man auf alle Blätter, liegt das 99. Perzentil bei 140 ms. Wartet man auf 95 % davon, liegt es bei 70 ms: Die Hälfte des ganzen Tails geht auf das Konto des langsamsten Zwanzigstels der Antworten.

Aus Tabelle 1 von Dean und Barroso, The Tail at Scale (2013): Fertigstellungszeiten von Blatt-Anfragen in einem von Googles Fan-out-Diensten, an der Wurzel gemessen.
An der Wurzel gemessenMedian95. Perzentil99. Perzentil
Ein zufälliges Blatt ist fertig1 ms5 ms10 ms
95 % aller Blätter sind fertig12 ms32 ms70 ms
Alle Blätter sind fertig40 ms87 ms140 ms

Derselbe Effekt im Live-Modell

Ein Design, das du in Stackrig öffnen kannst: Nutzer schicken 50 Anfragen pro Sekunde an einen Root-Dienst, und der Root fragt einen Leaf-Dienst N-mal parallel und wartet auf alle Antworten. Ein Leaf-Aufruf braucht im Mittel 10 ms Arbeit, mit der Streuung, die Request-Handler meist haben: Die meisten Aufrufe sind schneller als der Mittelwert, und einige wenige dauern ein Mehrfaches davon. Der Leaf hat weit mehr Server, als er braucht (seine CPUs bleiben unter 20 %), also steckt in der Tabelle keine Wartezeit in einer Warteschlange: Es ist nur die Streuung der Arbeit selbst.

Aus Stackrigs Live-Modell, nicht von echten Maschinen: Latenz der ganzen Anfrage über zwei Minuten, gerundet. In der App wird p99 für die letzte Sekunde angezeigt und schwankt um diese Werte.
Parallele Aufrufe pro AnfrageMedian95. Perzentil99. Perzentil
19 ms30 ms50 ms
1027 ms62 ms100 ms
5045 ms95 ms135 ms
10055 ms110 ms160 ms

Drei Dinge lassen sich daraus ablesen:

  1. Der Median bewegt sich am stärksten. Von einem Aufruf zu hundert wächst der Median etwa auf das Sechsfache und das p99 etwa auf das Dreifache. Fan-out fügt nicht nur einen schlechten Tail hinzu: Es macht die gewöhnliche Anfrage langsam.
  2. Die ersten zehn Aufrufe kosten am meisten. Von 1 auf 10 Aufrufe verdreifacht sich der Median; von 10 auf 100 verdoppelt er sich. Eine Seite, die „nur“ zehn parallele Aufrufe macht, hat schon den größten Teil des Weges hinter sich.
  3. Die eigenen Zahlen des Leafs haben sich nie geändert. In allen vier Zeilen meldet der Leaf-Dienst denselben Median und dasselbe p99. Sein Dashboard kann das Problem nicht zeigen.

Die Streuung der Arbeit ist der Hebel

Dasselbe Design mit 100 parallelen Aufrufen und einer geänderten Einstellung am Leaf: Seine „Service time variation“ ist 0,3 statt 1, sodass 98 von 100 Aufrufen zwischen etwa 5 und 20 ms dauern statt zwischen 1 und 50. Der Mittelwert bleibt 10 ms.

Aus Stackrigs Live-Modell: 100 parallele Aufrufe pro Anfrage, die mittlere Arbeit des Leafs 10 ms in beiden Zeilen; gerundet.
Service time variation des LeafsMedian der Anfrage99. Perzentil der Anfrage
1 (die Voreinstellung)55 ms160 ms
0,322 ms30 ms

Kein Server kam hinzu, und kein Aufruf fiel weg. Dass jeder Aufruf etwa gleich lange dauert, hat das p99 der Anfrage auf etwa ein Fünftel gesenkt. In einem echten Dienst heißt das: dieselbe Abfrage für jeden Aufruf statt einer billigen und einer teuren hinter demselben Endpunkt, keine Stop-the-World-Pausen, kein Hintergrund-Job auf den Maschinen, die antworten.

Zum Vergleich: Dieselben 100 Aufrufe nacheinander dauern etwa eine Sekunde (100 × 10 ms). Erst das parallele Aufrufen macht eine breite Anfrage überhaupt möglich, und der Tail ist der Preis dafür.

Öffne die Designs in der App:

Wähl jeweils die Verbindung von Root zu Leaf, um die Aufrufe pro Anfrage zu ändern, und den Leaf, um seine Service time variation zu ändern.

Was das Paper empfiehlt

Dean und Barroso halten fest, dass ein großer Dienst nicht jede Quelle von Langsamkeit beseitigen kann (geteilte Maschinen, Hintergrund-Daemons, Garbage Collection, Warteschlangen, Wartungsarbeit). Er muss also so gebaut sein, dass er langsame Teile verkraftet, so wie er ausgefallene verkraftet. Ihre Techniken, in unseren Worten:

  • Hedged Requests. Schick denselben Aufruf an ein zweites Replikat, wenn das erste nach einer kurzen Verzögerung nicht geantwortet hat, und nimm die Antwort, die zuerst kommt. Wer bis zum 95. Perzentil der erwarteten Latenz wartet, hält die Zusatzlast bei etwa 5 %. Ihr Beispiel: ein Benchmark, der 1.000 Schlüssel aus einer Tabelle liest, die über 100 Server verteilt ist; eine zweite Anfrage nach 10 ms brachte das 99,9. Perzentil von 1.800 ms auf 74 ms, mit 2 % mehr Anfragen.
  • Tied Requests. Stell den Aufruf auf zwei Servern zugleich in die Warteschlange und lass jeden die Kopie des anderen abbrechen, sobald er mit der Arbeit beginnt, sodass die Wartezeit eines Servers nicht mehr entscheidet.
  • Antworten, die gut genug sind. Antworte, wenn die meisten Blätter geantwortet haben, sofern das Ergebnis auch ohne den Rest noch nützlich ist. Ihre eigene Tabelle zeigt, was das bringt: 70 statt 140 ms.
  • Nimm langsame Server eine Weile heraus, und schick ihnen weiter Schatten-Anfragen, um zu sehen, wann sie sich erholt haben.
  • Viele kleine Partitionen pro Maschine, damit sich Last in kleinen Schritten verschieben lässt und stark gefragte Einträge zusätzliche Replikate bekommen können.
  • Canary Requests. Probier eine neue Art von Anfrage an einem oder zwei Blättern aus, bevor du sie an Tausende schickst, damit eine schlechte Anfrage nicht alle lahmlegen kann.

Ein Hedged Request ist ein früh geschickter Retry. Er braucht Aufrufe, die sich gefahrlos wiederholen lassen, und eine Grenze dafür, wie viele geschickt werden, sonst macht er aus einer langsamen Minute eine Überlast: Retry-Stürme: warum Retries deinen Dienst lahmlegen.

Was du in einem kleineren System tun kannst

  1. Zähl die Aufrufe pro Anfrage. Auf wie viele Backend-Aufrufe wartet jede Seite und jeder API-Aufruf? Zehn sind schon ein Fan-out.
  2. Mach einen Aufruf statt vieler. Eine Abfrage für hundert Zeilen, ein Batch-Aufruf für hundert Schlüssel: ein Zug aus der Latenzkurve statt hundert.
  3. Beobachte das Perzentil, das deine Aufrufer spüren. Ein Dienst, der 100-mal pro Anfrage aufgerufen wird, braucht sein p99.9 und p99.99 auf dem Dashboard, nicht sein p99.
  4. Verringere die Streuung, bevor du Server hinzufügst: Trenn billige und teure Arbeit, beseitige Pausen. Warum Warteschlangen die Streuung vergrößern, wenn sich Maschinen füllen, steht in Warum explodiert die p99-Latenz lange vor 100 % CPU?
  5. Leg fest, was die Seite ohne die langsamste Antwort tut: ein Zeitlimit pro Aufruf und eine Seite, die auch ohne die Empfehlungen angezeigt wird.

Was diese Seite dir nicht sagt

  • Die Rechnung setzt unabhängige Aufrufe voraus. Echte Langsamkeit ist oft geteilt: Eine Pause auf einer Maschine verlangsamt jeden Aufruf, den sie bedient, ein langsames Netz verlangsamt alle. Dann trifft es weniger Anfragen, als die Tabelle sagt, und die getroffenen trifft es härter.
  • Die Form der Streuung ist eine Annahme. Das Modell gibt den Arbeitszeiten eine schiefe Streuung, die eine einzige Zahl beschreibt, die Service time variation; mit der Voreinstellung 1 ist der äußerste Tail länger als im einfachsten Lehrbuchfall. Dein Dienst hat seine eigene Kurve: Miss sein p99.9 und p99.99, bevor du irgendeiner Tabelle traust.
  • Das Modell hat keine Hedged oder Tied Requests. Es zeigt das Problem und was die Zahl der Aufrufe und die Streuung damit machen, nicht die Gegenmittel aus dem Paper.
  • Googles Zahlen sind Googles Zahlen. Ein Dienst, vor 2013 gemessen, mit weit mehr Blättern, als die meisten Systeme haben.
  • Das Live-Modell ist keine Messung. Wie es sich zu einer echten Maschine verhält, beantwortet für ein System der Artikel über den 12-Dollar-Server. Woran das Live-Modell geprüft wird, nämlich an einer exakten Simulation, steht auf Wie genau ist Stackrig?

Quellen

  • Jeffrey Dean und Luiz André Barroso, The Tail at Scale, Communications of the ACM 56(2), Februar 2013, Seiten 74–80: das Beispiel mit 63 % und das Beispiel mit 2.000 Servern (Seite 76), Tabelle 1 (Seite 77), Hedged und Tied Requests (Seiten 77–78), die übrigen Techniken (Seiten 78–79).

„Web app with database“ im Playground öffnen

Die App kannst du kostenlos im Browser ausprobieren, ohne Konto. Um zu erfahren, wann Pro fertig ist, trag dich in die Warteliste ein.

Stackrig