Leader-Auswahl in verteilten Systemen

Leader-Auswahl ist die einfache Idee, einer Sache (einem Prozess, einem Host, einem Thread, einem Objekt oder einem Menschen) in einem verteilten System besondere Befugnisse zu verleihen. Zu diesen besonderen Befugnissen könnten die Möglichkeit gehören, Arbeit zuzuweisen, Daten zu ändern oder sogar alle Anforderungen im System zu bearbeiten.

Die Leader-Auswahl ist ein leistungsfähiges Instrument zur Verbesserung der Effizienz, zur Reduzierung der Koordination, zur Vereinfachung der Architekturen und zur Reduzierung der Operationen. Auf der anderen Seite können durch die Wahl von Leadern neue Fehlermodi und Skalierungsengpässe entstehen. Darüber hinaus kann es für Sie durch die Leader-Auswahl schwieriger werden, die Korrektheit eines Systems zu beurteilen.

Aufgrund dieser Komplikationen prüfen wir andere Optionen sorgfältig, bevor wir die Leader-Auswahl durchführen. Bei der Datenverarbeitung und bei Workflows können Workflow-Services wie AWS Step Functions viele der gleichen Vorteile erzielen wie die Wahl von Führungskräften und viele ihrer Risiken vermeiden. Für andere Systeme implementieren wir oft idempotente APIs, optimistische Sperren und anderer Muster, die einen einzelnen Leader überflüssig machen.

In diesem Artikel werde ich einige der Vor- und Nachteile der Leader-Auswahl im Allgemeinen erläutern und erläutern, wie Amazon die Leader-Auswahl in unseren verteilten Systemen angeht, einschließlich Einsichten in das Versagen von Leadern.

Es gibt viele Möglichkeiten, einen Leader zu wählen, von Algorithmen wie Paxos über Software wie Apache ZooKeeper bis hin zu kundenspezifischer Hardware und Leasing. Leases sind der bei Amazon am häufigsten verwendete Mechanismus zur Wahl von Leadern. Leases sind relativ einfach zu verstehen und zu implementieren und bieten integrierte Fehlertoleranz. Leases funktionieren mit einer einzigen Datenbank, in der der aktuelle Leader gespeichert ist. In diesem Fall muss der Leader in regelmäßigen Abständen Herzschlag aufweisen, um zu zeigen, dass er immer noch der Leader ist. Wenn der bestehende Leader nach einiger Zeit keinen Herzschlag verspürt, können andere Leader versuchen, die Führung zu übernehmen.

Wir vermeiden Zeitabhängigkeit in verteilten Systemen, selbst mit der großartigen Zeitsynchronisierungsfunktion in Amazon Elastic Compute Cloud (Amazon EC2). Es ist schwierig sicherzustellen, dass die Systemuhren in einem Cluster synchron genug sind, um von dieser Synchronisation abhängig zu sein, um verteilte Vorgänge zu ordnen oder zu koordinieren. In Amazon verwenden verteilte Systeme nur Zeit für den menschlichen Konsum. Leases sind zeitabhängig. Sie hängen jedoch nur von der lokalen Dauer der abgelaufenen Zeit ab und nicht von einer Wanduhrzeit, die synchronisiert ist und von mehreren Servern vereinbart werden muss.

Der Quellcode des DynamoDB-Sperrclients enthält Beispiele und Details zur Wahl des Leiters. Wir haben jedoch festgestellt, dass die korrekte Implementierung, obwohl Leases und Sperren konzeptionell einfach sind, subtil sein kann. Für die Implementierung muss bekannt sein, wie ein Server die lokale Zeitdauer misst. Wenn beispielsweise ein Server oder eine Bibliothek, die die Zeit misst, der Meinung ist, dass die Zeit gelegentlich rückwärts springt, würde dies die Annahmen über die in Leases integrierte Zeitdauer sprengen. Probleme mit der globalen Zeitsynchronisierung treten über längere Zeiträume hinweg auf, sodass Server sich nicht mehr auf die aktuelle Uhrzeit einigen können, von Schaltsekunden bis hin zur lokalen Zeitverschiebung aufgrund einer anhaltend hohen CPU-Auslastung.

Ein größeres Problem bei Leases und allen Arten von verteilten Sperren besteht darin, sicherzustellen, dass der Leader nur funktioniert, während er die Sperre hält. Es ist ziemlich schwierig, sicherzustellen, dass der Leader die Sperre hält. Wir haben es als wichtig erachtet, sicherzustellen, dass ein Leader in einem langsamen oder verlustbehafteten Netzwerk nicht glaubt, dass es Sperren länger hält als es tatsächlich ist. In ähnlicher Weise kann die Garbage Collection-Pause zwischen der Überprüfung einer Sperre und der Ausführung von Arbeiten zu einem falschen Verhalten führen. In der Praxis ist das Härten gegen diese Probleme oft die größte Herausforderung.

DynamoDB und ZooKeeper bieten einfache Lease-basierte Locking-Clients, die eine fehlertolerante Leader-Wahl ermöglichen. Sofern keine besonderen Bedürfnisse bestehen, bevorzugen wir diese Kunden, da sie unserer Meinung nach die einfachste und am besten getestete Möglichkeit zur Durchführung von Leader-Auswahlen bieten. Amazon-Teams vermeiden es lieber, eine benutzerdefinierte Implementierung für die Leader-Auswahl zu erstellen. Stattdessen bevorzugen wir bestehende Clients, die gut getestet und kampferprobt sind.

Leader-Auswahl ist ein weit verbreitetes Muster in Amazon. Beispiel:

• Nahezu alle Systeme, die herkömmliche relationale Datenbankverwaltungssysteme (RDBMS) verwenden, verlassen sich auf die Wahl des Leiters, um eine Leader-Datenbank auszuwählen, die alle Schreibvorgänge und manchmal alle Lesevorgänge verarbeitet. In diesen Systemen kann die Wahl automatisiert werden, wird jedoch häufig manuell von einem menschlichen Bediener durchgeführt.
• Amazon EBS verteilt Lese- und Schreibzugriffe auf ein Volume über viele Speicherserver. Um die Konsistenz zu gewährleisten, wählt es für jeden Bereich des Volumes Leader, um eine Vorauswahl zu treffen, die die Lese- und Schreibzugriffe anordnen. Wenn diese Vorauswahl fehlschlägt, kopiert der Nachfolger Schritte zur Verwendung desselben Auswahlmechanismus. In Amazon EBS stellt die Wahl des Leaders die Konsistenz sicher und verbessert gleichzeitig die Leistung, indem die Koordination auf der Datenebene vermieden wird. DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB) und Amazon Kinesis (Kinesis) verwenden aus demselben Grund ähnliche Ansätze.
• Die Kinesis Client Library (KCL) verwendet Leases, um sicherzustellen, dass jeder Kinesis-Shard von einem Eigentümer verarbeitet wird, sodass die Verarbeitung von Kinesis-Streams einfach skaliert werden kann.

Eine andere Sache, über die Sie sorgfältig nachdenken sollten, ist, was mit der Arbeit eines Leaders geschieht, wenn sie fehlschlägt. Wenn ein Leader während einer Aufgabe versagt, wie beendet der neue Leader die Aufgabe? Wenn ein Leader ausfällt, bevor er seine Arbeit dauerhaft macht, ist das System dann noch korrekt? Bei vielen Arten von Systemen gibt es separate Schritte zum Festlegen der „Dauerhaftigkeit“ und zum Feststellen der „Vollständigkeit“. Bei Amazon machen unsere Systeme immer die ersteren vor den letzteren (oder tolerieren Datenverlust). Auch hier ist Idempotenz nützlich. Auf diese Weise kann der neue Leader Arbeiten, die der scheidende Leader möglicherweise teilweise abgeschlossen oder abgeschlossen hat, von denen er anderen jedoch nichts erzählt hat, vertrauensvoll weiterleiten.

Um Ausfälle zu tolerieren, verfügen verteilte Amazon-Systeme nicht über einen einzigen Leader. Stattdessen ist Leadership eine Eigenschaft, die von Server zu Server oder von Prozess zu Prozess weitergegeben wird. In verteilten Systemen kann nicht garantiert werden, dass genau ein Leader im System vorhanden ist. Stattdessen kann es meistens einen Leader geben, und bei Ausfällen kann es entweder null oder zwei Leader geben.

Wie wir das Verhalten des Systems bei einem Leader-Ausfall festlegen, hängt davon ab, was in einem System bei zwei Leadern geschieht. Systeme, die idempotente Arbeit leisten, tolerieren häufig zwei Leader mit minimalem Effizienzverlust. Mit zwei Leadern können Systeme eine höhere Verfügbarkeit erzielen und schwächere Ansätze für die Leader-Auswahl wählen.

Systeme, die unbedingt höchstens einen Leader benötigen, sind schwerer zu bauen als Systeme mit mehreren Leadern. Das Leader-Auswahl muss immer korrekt und konsistent sein. Und es muss sicherstellen, dass der scheidende Leader abgesetzt wird, bevor ein neuer Leader ausgewählt wird, was schwieriger ist, als es scheint. In verteilten Systemen ist es oft schwierig festzustellen, ob ein System ausgefallen ist oder ob es in einer anderen Netzwerkpartition weiterhin funktioniert. Bei Amazon stellen wir sicher, dass jedes vom Leader gewählte System diese Grenzbedingung erfüllt.

Bei Amazon befolgen wir die folgenden Best Practices für die Leader-Auswahl:

• Überprüfen Sie die verbleibende Lease-Zeit (oder den Sperrstatus im Allgemeinen) häufig und insbesondere, bevor Sie eine Operation einleiten, die Nebenwirkungen hat, die über den Leader hinausgehen.
• Bedenken Sie, dass langsame Netzwerkverbindungen, Zeitüberschreitungen, Wiederholungsversuche und Pausen bei der Garbage Collection dazu führen können, dass die verbleibende Lease-Zeit abläuft, bevor der Code dies erwartet.
• Vermeiden Sie Heartbeat-Leases in einem Hintergrund-Thread. Dies kann zu Korrektheitsproblemen führen, wenn der Thread den Code nicht unterbrechen kann, wenn das Lease abläuft oder der Heartbeat-Thread abbricht. Verfügbarkeitsprobleme können auftreten, wenn der Arbeitsthread abstirbt oder stoppt, während der Heartbeat-Thread an der Lease festhält.
• Haben Sie zuverlässige Metriken, die zeigen, wie viel Arbeit ein Leader leisten kann im Vergleich zu dem, was er gerade tut. Überprüfen Sie diese Metriken häufig und stellen Sie sicher, dass eine Skalierung geplant ist, bevor die Kapazität aufgebraucht ist.
• Machen Sie es sich leicht, herauszufinden, welcher Host der aktuelle Leader ist und welcher Host zu einem bestimmten Zeitpunkt der Leader war. Führen Sie einen Audit-Trail oder ein Protokoll über Leadership-Wechsel.
• Modellieren und überprüfen Sie formal die Korrektheit verteilter Algorithmen mit Tools wie TLA+. Hierdurch werden subtile, schwer zu beobachtende und seltene Fehler aufgedeckt, die auftreten können, wenn eine Bewerbung zu viel von den Garantien des Auswahlprotokolls für Leader verlangt.

Leader-Auswahl ist ein leistungsstarkes Tool, das in Systemen von Amazon eingesetzt wird, um die Fehlertoleranz und die Benutzerfreundlichkeit unserer Systeme zu verbessern. Wenn wir jedoch die Leader-Auswahl verwenden, achten wir darauf, die Garantien zu berücksichtigen, die jedes Leader-Auswahlprotokoll bietet, und was noch wichtiger ist, dass dies nicht der Fall ist.

Amazon-Systeme verwenden häufig die Leader-Auswahl, um sicherzustellen, dass Fehlertoleranz eingebaut ist. Wenn Systeme mithilfe der Leader-Auswahl sicherstellen, dass mindestens ein Server eine Aufgabe verarbeitet, verwenden sie separate Mechanismen, um die Korrektheit gegenüber mehreren gleichzeitigen Leadern aufrechtzuerhalten. Sie könnten beispielsweise eine zugrunde liegende Datenbank verwenden, um sicherzustellen, dass sich zwei Leader nicht gegenseitig stören, wenn sie ein Lease abschließen. Anstatt Annahmen über die Garantien einer Leasing-Implementierung zu treffen, konzentrieren wir uns auf die Korrektheit dieser Systeme, häufig mit der Modellierung mit Techniken wie TLA +.

Trotz seiner Nuancen bleibt die Leader-Auswahl neben Mustern wie Idempotenz und optimistischem Locking ein nützliches Werkzeug in unserem Toolkit für verteilte Systeme bei Amazon.

Weitere Informationen zur Funktionsweise von Leases finden Sie unter:

• So verteilen Sie Sperren
• Burrows, The Chubby Lock Service für lose gekoppelte verteilte Systeme
• Gray und Cheriton, Leases: Ein effizienter fehlertoleranter Mechanismus für die Konsistenz des verteilten Datei-Cache