Asynchronität, Queues und Backpressure

Queues verwandeln Lastspitzen in Rückstände

Last kommt nie gleichmäßig an. Mittagsbestellungen ballen sich um 12:30, Ticketkäufer drücken alle um 10:00:00 auf den Knopf, und ein Batch-Job kippt um Mitternacht eine Million Events ab. Ein synchroner Service muss entweder Kapazität für die höchste Spitze haben oder während dieser Spitze ausfallen. Eine Queue zwischen dem Producer der Arbeit und dem Service, der sie erledigt, ändert die Rechnung: Während einer Spitze wartet die zusätzliche Arbeit in der Queue, und die Consumer verarbeiten sie in ihrem eigenen gleichmäßigen Tempo und holen auf, wenn die Spitze vorbei ist. Microsofts Katalog von Cloud-Mustern nennt das Queue-Based Load Leveling. Abschnitt 2.4 hat gezeigt, warum sich Warteschlangen bilden, sobald Ankünfte sich ballen; in diesem Abschnitt geht es darum, sie gezielt einzusetzen.

Der Nutzen ist real: Consumer können für den Durchschnitt statt für die Spitze dimensioniert werden, ein langsamer oder neu startender Consumer verliert keine Arbeit, und der Producer ist nicht mehr zeitlich an den Consumer gekoppelt (Abschnitt 6.5). Der Preis ist, dass die Arbeit nun später erledigt wird. Eine Queue verwandelt eine Spitze in einen Rückstand, und ein Rückstand ist schlicht eine Verzögerung, die jedes Element dahinter erfährt. Für den Versand von Bestätigungs-E-Mails oder die Aktualisierung eines Suchindex ist das in Ordnung, für die Zuweisung eines Kuriers zu einer Bestellung fragwürdig und für eine Zahlung, deren Bestätigung die Kundin oder der Kunde erwartet, inakzeptabel. Die erste Entwurfsfrage für jede Queue lautet daher: Wie lange darf ein Element warten, und was geschieht mit Elementen, die länger warten würden?

Work Queues und Competing Consumers

Am häufigsten ist eine Work Queue mit Competing Consumers: Mehrere identische Worker lesen aus einer Queue, jede Nachricht geht an genau einen von ihnen, und der Durchsatz wächst, indem man Worker hinzufügt. Das ist die X-Achse des Scale Cube, angewandt auf Hintergrundarbeit, und sie skaliert natürlich anhand des richtigen Signals: Rückstand pro Worker oder Alter der ältesten Nachricht.

Für die Korrektheit kommt es auf die Mechanik an. Ein Worker nimmt eine Nachricht, verarbeitet sie und bestätigt sie dann; stürzt der Worker vorher ab, macht der Broker die Nachricht nach einem Timeout wieder sichtbar (SQS nennt das den Visibility Timeout), und ein anderer Worker verarbeitet sie. Die Zustellung erfolgt daher at least once, also müssen Consumer idempotent sein (Abschnitt 6.4). Ein Visibility Timeout, der kürzer als die tatsächliche Verarbeitungszeit ist, führt dazu, dass dieselbe Nachricht zweimal parallel verarbeitet wird. Die Reihenfolge geht verloren, sobald es mehr als einen Consumer gibt, es sei denn, die Nachrichten werden nach Schlüssel partitioniert; dann begrenzt die Zahl der Partitionen die Zahl sinnvoller Consumer. Und Prefetching (ein Worker nimmt mehrere Nachrichten auf einmal, um Roundtrips zu sparen) sollte bei langsamen Aufgaben niedrig bleiben, sonst hortet ein Worker Nachrichten, die untätige Worker hätten verarbeiten können.

Eine Queue schafft keine Kapazität

Eine Queue fängt einen vorübergehenden Überschuss auf, aber keinen dauerhaften. Kommt Arbeit lange genug schneller an, als sie erledigt wird, wächst der Rückstand ohne Grenze, und Littles Gesetz (L = λ × W) besagt, dass die Wartezeit mit ihm wächst. Eine unbegrenzte In-Memory-Queue erschöpft irgendwann den Speicher und bringt den Prozess zum Absturz, wobei alles darin verloren geht; eine unbegrenzte persistente Queue füllt ihre Festplatte oder hält Arbeit noch Stunden, nachdem sich niemand mehr dafür interessiert. Schlimmer noch: Die Queue verbirgt das Problem. Producer erhalten schnelle Bestätigungen, die Fehlerraten bleiben bei null, und das einzige Symptom ist, dass Ergebnisse immer später eintreffen. Fachleute bei Amazon beschreiben solche Rückstände als potenziell unüberwindbar, weil ein Service, der weit genug zurückfällt, seine gesamte Kapazität für Arbeit aufwenden kann, die seine Clients längst aufgegeben haben.

Daraus folgen zwei Praktiken. Erstens: Messen Sie neben der Queue-Länge auch das Alter der ältesten Nachricht; das Alter ist das, was Benutzer erleben, und es reagiert sofort, wenn Consumer ins Stocken geraten. Zweitens: Geben Sie jeder Queue eine Grenze, die Sie mit Littles Gesetz aus der akzeptablen Wartezeit ableiten, und legen Sie im Voraus fest, was passiert, wenn die Grenze erreicht ist. Um diese Entscheidung geht es in den nächsten drei Teilen dieses Abschnitts.

Backpressure: Producer zum Verlangsamen bringen

Backpressure ist jeder Mechanismus, mit dem eine langsamere nachgelagerte Stufe eine schnellere vorgelagerte Stufe zum Verlangsamen bringt, statt Arbeit dazwischen auflaufen zu lassen. Der Begriff stammt von Flüssigkeiten in Rohren, und die Idee ist uns bei Pipes and Filters (Abschnitt 5.4) begegnet. Sie ist in viele Schichten des Stacks eingebaut, den Sie bereits nutzen. Die Flusskontrolle von TCP stoppt einen Sender, wenn der Puffer des Empfängers voll ist. Eine begrenzte blockierende Queue lässt das put des Producers auf freien Platz warten. Pull-basierte Consumer wie bei Kafka holen Arbeit erst, wenn sie bereit sind, sodass das Log des Brokers statt des Speichers des Consumers den Rückstand hält, und ein Kafka-Producer blockiert oder schlägt fehl, wenn sein eigener Sendepuffer voll ist. Die Reactive-Streams-Spezifikation lässt einen Subscriber eine bestimmte Anzahl von Elementen anfordern, sodass ein Stream nie mehr liefert, als der Subscriber verlangt hat.

Backpressure funktioniert gut innerhalb eines Prozesses oder entlang einer Pipeline. Über eine Request-Response-Grenze mit menschlichen Benutzern wird daraus meist Ablehnung: Ein überlasteter HTTP-Service kann ein Smartphone nicht höflich warten lassen, also antwortet er mit 429 Too Many Requests oder 503 Service Unavailable, idealerweise mit einem Retry-After-Header, und verlässt sich darauf, dass der Client zurückweicht. Ist eine begrenzte Queue voll, gibt es nur drei Möglichkeiten: den Producer blockieren, die neue Arbeit ablehnen oder etwas bereits Angenommenes verwerfen. Jede ist irgendwo richtig; der Fehler ist, keine Wahl zu treffen.

Load Shedding und Priorisierung

Ein Server unter mehr Last, als er bewältigen kann, schneidet schlechter ab, als wenn er seine Kapazität bedienen und den Rest ablehnen würde. Er nimmt alles an, jede Anfrage wartet in seinen internen Queues, die Antwortzeiten steigen über die Timeouts der Clients, und am Ende verwendet er seine gesamte Kapazität auf Anfragen, deren Clients bereits aufgegeben haben. Der Durchsatz bleibt hoch, während der Goodput, die Rate der Anfragen, die rechtzeitig genug abgeschlossen werden, um nützlich zu sein, gegen null einbricht. Load Shedding verhindert das, indem es einige Anfragen bewusst ablehnt, damit die übrigen erfolgreich sind.

Gutes Load Shedding hat drei Eigenschaften. Es ist früh und kostengünstig: Eine Anfrage abzulehnen muss weit weniger kosten, als sie zu bedienen; es geschieht daher an der Eingangstür, vor aufwendiger Authentifizierung oder Datenbankarbeit, anhand eines billigen Signals wie laufender Anfragen oder des Queue-Alters. Es ist priorisiert: Googles SRE-Buch beschreibt, jede Anfrage mit einer Kritikalität zu kennzeichnen (von CRITICAL_PLUS bis hinunter zu SHEDDABLE), damit Batch- und Prefetch-Verkehr vor nutzerseitigem Verkehr verworfen wird. In der Essenslieferplattform haben Checkouts und Standortupdates der Kuriere Vorrang vor Empfehlungen, die wiederum Vorrang vor Analytics-Events haben. Und es ist zeitbewusst: Eine Anfrage, die bereits länger gewartet hat als der Timeout ihres Aufrufers, sollte verworfen statt verarbeitet werden. Fachleute bei Facebook haben zwei Verfeinerungen beschrieben: eine Controlled-Delay-Queue, die nur eine kurze Wartezeit zulässt, wenn eine Queue in letzter Zeit nicht leer war, und den Wechsel zu Last-in-first-out unter Last, sodass die frischesten Anfragen, deren Benutzer noch warten, zuerst bedient werden.

Ein weiterer Schritt besteht darin, das Limit selbst anzupassen. Feste Nebenläufigkeitslimits sind an einem guten Tag entweder zu niedrig oder an einem schlechten zu hoch; adaptive Nebenläufigkeitsbegrenzer erhöhen die erlaubte Zahl laufender Anfragen, solange die Latenz niedrig bleibt, und senken sie, wenn die Latenz steigt – eine Idee, die der TCP-Überlastkontrolle entlehnt ist. Ganz am Eingang eines Systems kann Zugangskontrolle die Form eines virtuellen Warteraums annehmen, wie beim Ticketverkaufsstart oben: Benutzer werden am Rand in einer Warteschlange gehalten und in dem Tempo eingelassen, das der Kern bedienen kann – Load Shedding, präsentiert als Fairness.

Algorithmen für Rate Limiting

Rate Limiting beschränkt, wie viel Arbeit ein bestimmter Client, API-Schlüssel, Mandant oder eine IP-Adresse in einem Zeitraum einreichen darf. Es unterscheidet sich im Zweck von Load Shedding: Load Shedding schützt den Server vor völliger Überlast, egal wer sie verursacht, während Rate Limiting Kapazität fair verteilt und vor jedem einzelnen Client schützt, ob fehlerhaft oder böswillig. Beide antworten auf dieselbe Weise, meist mit HTTP 429. Vier Algorithmen dominieren.

Der Token Bucket verdient einen genaueren Blick, weil er der übliche Standard ist. Der Eimer fasst bis zu b Tokens und erhält r Tokens pro Sekunde. Jede Anfrage nimmt ein Token; ist keines übrig, wird sie abgelehnt (oder in der Shaping-Variante verzögert). Ein Client, der ruhig war, kann daher einen Burst von b Anfragen auf einmal senden, was zu echten Clients passt, etwa einer mobilen App, die einen Bildschirm öffnet, während er über jeden längeren Zeitraum im Mittel r nicht überschreiten kann. Der Leaky Bucket ist das Spiegelbild: Er glättet die Ausgabe auf eine konstante Rate, was nützlich ist, um ein nachgelagertes System zu schützen, das überhaupt keine Bursts verkraftet.

import math, time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate              # tokens added per second
        self.capacity = capacity      # largest burst allowed
        self.tokens = capacity        # start full
        self.updated = time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        elapsed = now - self.updated
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, 0
        wait = (cost - self.tokens) / self.rate   # seconds until enough tokens
        return False, max(1, math.ceil(wait))      # for the Retry-After header

bucket = TokenBucket(rate=5, capacity=20)        # one bucket per API key
allowed, retry_after = bucket.allow()

HTTP 429, Retry-After und wo Limits durchgesetzt werden

HTTP hat Standardsignale für beide Situationen. 429 Too Many Requests, definiert in RFC 6585 (2012), teilt einem Client mit, dass er in einem bestimmten Zeitraum zu viele Anfragen gesendet hat. 503 Service Unavailable besagt, dass der Server als Ganzes vorübergehend überlastet ist oder gewartet wird. Beide können einen Retry-After-Header (RFC 9110) tragen, der eine Anzahl von Sekunden oder ein Datum angibt, nach dem ein erneuter Versuch sinnvoll ist. Viele APIs geben außerdem Header zurück, die das Limit, das verbleibende Kontingent und den Rücksetzzeitpunkt ankündigen, traditionell X-RateLimit-*; ein IETF-Entwurf standardisiert die Felder RateLimit und RateLimit-Policy. Wohlerzogene Clients beachten Retry-After, fügen Jitter hinzu, damit abgelehnte Clients nicht alle im selben Augenblick zurückkommen, und behandeln wiederholte 429er als Grund, langsamer zu werden, statt es heftiger zu versuchen (Abschnitt 9.4).

Limits lassen sich auf mehreren Schichten durchsetzen, und ausgereifte Systeme nutzen mehr als eine: am Edge oder API-Gateway pro IP-Adresse und API-Schlüssel, um Missbrauch und außer Kontrolle geratene Clients zu stoppen, bevor sie etwas kosten; pro Mandant, damit ein großer Kunde die anderen nicht aushungern kann; und innerhalb jedes Service, um die eigene Kapazität und die eigenen Abhängigkeiten zu schützen. Ein globales Limit über viele Gateway-Instanzen braucht gemeinsamen Zustand, meist atomare Zähler in Redis, was einen Netzwerkaufruf pro Anfrage hinzufügt; ein gängiger Kompromiss ist, jeder von N Instanzen ein lokales Limit von etwa 1 ÷ N des Gesamtwerts zu geben und eine gewisse Ungenauigkeit hinzunehmen. Limits sollten anhand gemessener Kapazität festgelegt und veröffentlicht werden, damit Partner darauf hin entwerfen können, und die Zahl der Ablehnungen sollte überwacht werden, denn ein plötzlicher Anstieg ist entweder ein Angriff, ein Fehler in einem Client oder ein Limit, das nicht mehr zur Realität passt.

Dead Letter Queues

Manche Nachrichten scheitern jedes Mal: eine fehlerhafte Nutzlast, eine Bestellung für ein Restaurant, das es nicht mehr gibt, ein Bug, den eine bestimmte Eingabe auslöst. Endlos wiederholt, blockiert eine solche Poison Message eine Partition oder verschwendet für immer einen Worker. Eine Dead Letter Queue (eingeführt in Abschnitt 6.4) nimmt Nachrichten auf, die eine festgelegte Anzahl von Malen gescheitert sind (SQS nennt das den Maximum Receive Count in einer Redrive Policy), damit die übrige Arbeit weiterlaufen kann.

Eine Dead Letter Queue ist ein Werkzeug für Defekte, nicht für Überlast: Landen Nachrichten dort, weil Consumer zu langsam sind, liegt die Lösung in Kapazität oder Backpressure, nicht in einer zweiten Queue. Jede Nachricht in einer DLQ bedeutet, dass etwas, das das Geschäft erwartet hat, nicht passiert ist. Die DLQ braucht daher einen Verantwortlichen, einen Alarm auf ihre Tiefe oder ihr Alter, Werkzeuge, um Nachrichten mit ihrem Fehler und ihrer Versuchszahl zu untersuchen, und einen Weg, sie erneut abzuspielen, sobald die Ursache behoben ist. Legen Sie im Voraus fest, was ein verspätetes Replay für die Reihenfolge bedeutet und für Nachrichten, deren geschäftlicher Moment vorbei ist: Eine Erstattung kann einen Tag später nachgeholt werden, eine Kurierzuweisung nicht.