Forscherinnen und Forscher der EPFL haben einen neuen verteilten Algorithmus entwickelt, der zum ersten Mal eines der größten Leistungs- und Zuverlässigkeitsprobleme bei vielen der derzeit eingesetzten Konsensprotokolle löst.
Der Konsens gehört zu den grundlegenden Problemen verteilter Systeme. Er ermöglicht es einer Gruppe von Maschinen, mehrere Kopien von Daten zu behalten und diese auf einheitliche Weise zu aktualisieren, selbst wenn ein Teil der Maschinen ausfällt.
Nehmen wir als Beispiel drei Server, die drei Kopien von Daten speichern und die Aktualisierungen der Informationen verfolgen müssen, um konsistent zu bleiben. Wenn ein Server ausfällt, müssen die beiden anderen die Datenkonsistenz aufrechterhalten und die Aktualisierungen normal weiterlaufen lassen, so als hätte es keinen Ausfall gegeben.
Die heutigen Konsensprotokolle beruhen darauf, dass jederzeit ein Computerknoten zum Anführer ernannt wird, der die Datenaktualisierungen ständig überwacht und verwaltet. Wenn der Anführer ausfällt, wird ein anderer Knoten aktiv und übernimmt die Aufgabe, doch dabei tritt ein Problem auf. Wie lange muss ein anderer Knoten warten, bevor er einen nicht reagierenden Warteschlangenleiter ablöst?
"Wenn der Anführer ausfällt oder das Netzwerk schlecht ist, besteht das Problem bei herkömmlichen Konsensprotokollen darin, dass es sehr schwierig ist, die Wartezeit festzulegen", erklärt Prof. Bryan Ford, Leiter des Labors für dezentrale und verteilte Systeme (DEDIS) an der Fakultät für Informatik und Kommunikation der EPFL (IC). "Wenn Sie eine zu lange Vorlaufzeit festlegen und ein Anführer ausfällt, kann es zu langen Wartezeiten kommen und das System ist einfach nicht mehr funktionsfähig. Umgekehrt laufen Sie bei einer zu kurzen Frist Gefahr, eine echte Katastrophe auszulösen".
"Angenommen, der alte Anführer ist nicht ausgefallen, das Netzwerk ist nur ein bisschen langsamer als Sie dachten, der nächste Anführer kommt und versucht, die Arbeit zu übernehmen, aber gemäß der Funktionsweise aller bestehenden Protokolle. Die Aktionen des neuen Anführers werden die des alten Anführers aufheben, sodass dieser nicht mehr in der Lage ist, das zu beenden, was er gerade getan hat. Seine gesamte Arbeit ist dann verloren. Eine solche Situation kann zu ernsthaften Zuverlässigkeitsproblemen führen. Diese auf Anführern basierenden Protokolle können bei einem absichtlichen Denial-of-Service-Angriff völlig ausfallen", fährt er fort.
Um diese Schwierigkeiten zu umgehen, haben die DEDIS-Forscherinnen und -Forscher eine selten verwendete Kategorie von Konsensalgorithmen untersucht, die als "asynchrone Konsensprotokolle" bezeichnet werden. Im Gegensatz zu den heutigen Protokollen, die auf Anführern basieren, sind ihre asynchronen Gegenstücke nicht anfällig für Anführerausfälle oder Denial-of-Service-Angriffe. Es gibt jedoch einen wichtigen Nachteil: Die bisherigen asynchronen Protokolle sind unter normalen Bedingungen viel weniger effizient.
Laut Bryan Ford ändert ihr QuePaxa-Protokoll zum ersten Mal diese Dynamik. "Wir haben eine vorteilhafte Lösung gefunden. Das Neue und Einzigartige an QuePaxa ist, dass es sich um ein asynchrones Konsensprotokoll handelt, das unter normalen Netzwerkbedingungen endlich eine Effizienz erreicht, die der der weit verbreiteten, auf Anführern basierenden Protokolle gleichkommt. QuePaxa ist unter normalen Bedingungen ebenso schnell, effizient, mit geringer Latenz und geringen Kosten für die Netzwerkbandbreite".
Der neue Algorithmus ist so konzipiert, dass jeweils nur ein Anführer die Fortschrittsaufgabe leitet, aber ein zweiter Anführer kann eingreifen und im selben Zyklus Hilfe leisten, ohne den ersten Anführer zu stören. Ein dritter kann sich sogar den beiden anderen anschließen, um ihnen zu helfen, die Aufgabe schneller abzuschließen. Es gibt eine gewisse Redundanz der Bemühungen, aber die Knoten, die nicht Anführer sind, greifen nicht destruktiv ein. Kurze Fristen führen nicht dazu, dass die Aufgaben eines Anführers von anderen Anführern abgebrochen werden, wie es bei den aktuellen Protokollen der Fall ist.
Ein weiterer Vorteil von QuePaxa ist, dass es unter schwierigen Bedingungen wie lauten Netzwerken, langen Kommunikationsverzögerungen, unvorhersehbar variierenden Netzwerkverzögerungen oder absichtlichen Denial-of-Service-Angriffen äußerst robust ist.
"Unter diesen Bedingungen werden die bestehenden Konsensprotokolle vollständig verschwinden. QuePaxa wird weiterhin funktionieren, da es viel robuster ist", fährt er fort. "In allen Fällen, in denen die Leistung, die Zuverlässigkeit oder die Anfälligkeit für diese Art von Angriffen Anlass zu großer Sorge geben, halte ich es aufgrund seiner Robustheit für eine revolutionäre Lösung. QuePaxa ist dazu bestimmt, das neue Standard-Konsensusprotokoll zu werden".
Das DEDIS-Team hat bereits einen Open-Source-Prototypen von QuePaxa erstellt, der auf dem bekannten GitHub-Repository verfügbar ist. Das neue Protokoll wurde bereits auf der SOSP einem Artefaktbewertungsprozess unterzogen, bei dem Peer Reviewer seine Fähigkeiten testeten.
Der Artikel mit dem Titel QuePaxa: Escaping the tyranny of timeouts in consensus wird diese Woche auf dem alle zwei Jahre stattfindenden Symposium über Betriebssystemprinzipien ( SOSP) vorgestellt , das von der Association for Computing Machinary (ACM) organisiert wird, dem weltweit führenden Forum für Forscher, Entwickler, Programmierer und Lehrkräfte für Computersystemtechnik.
Eine Innovation für die Schaffung robuster verteilter Systeme
Links
Übersetzung durch myScience
Anzeige