Forschungsbericht 2014 - Max-Planck-Institut für Softwaresysteme, Standort Kaiserslautern

Robuste Systeme durch Replikation

Autoren
Clement, Allen
Abteilungen
Abteilung: Robust Systems / Max-Planck-Institut für Softwaresysteme, Saarbrücken / Max-Planck-Institut für Softwaresysteme, Kaiserslautern
Zusammenfassung
Computersysteme sind das Bindeglied vieler Bereiche des modernen Lebens: von den Smartphones für den Zugriff auf Websites über die von diesen Websites gehosteten Dienste bis zu den Computersystemen, mit denen wichtige Infrastrukturen verwaltet werden. Diese Systeme setzen sich aus tausenden von Computern zusammen, auf die wir uns tagtäglich verlassen. Die Zuverlässigkeit der von ihnen bereitgestellten Dienste sicherzustellen, ist eine fundamentale Herausforderung für die Forschung im Bereich der Verteilten Systeme. Hier ist ein wirksames Werkzeug das der Replikation.

Einleitung

Computer haben mittlerweile in allen Bereichen des modernen Lebens Einzug gehalten. Von den Smartphones, mit denen wir auf Internet-Websites zugreifen, über die Server zum Hosting von Online-Diensten bis zu den Computersystemen zur Lenkung zentraler Infrastrukturen (z. B. Flugsicherungssysteme, Stromnetze, Börsen und sonstige Dienste im Finanzwesen) bis hin zur Bordelektronik unserer PKW: Es wird immer schwieriger, Lebensbereiche zu finden, die nicht durch Computersysteme vernetzt sind.

Man ist versucht, sich jeden dieser Dienste als einzelnen großen Computer vorzustellen, der sich irgendwo weit weg oder unter der Motorhaube des Fahrzeugs befindet. Die Realität sieht jedoch weitaus interessanter – und komplizierter – aus. Denn bei diesen Diensten handelt es sich tatsächlich um sogenannte „Verteilte Systeme“, die sich aus mehreren hundert, zuweilen sogar mehreren tausend oder zehntausend Einzelcomputern zusammensetzen, deren Zusammenwirken die ordnungsgemäße Funktionsfähigkeit des Dienstes als Ganzes erst möglich macht.

Damit liegt eine der zentralen Herausforderungen für jeden durch ein Verteiltes System gestützten Dienst darin, dessen Zuverlässigkeit sicherzustellen. Während ein Verbund aus vielen Computern mehr leisten kann als jeder einzelne isolierte Computer, steht die Beschaffenheit Verteilter Systeme einem ordnungsgemäßen und zuverlässigen Verhalten zunächst prinzipbedingt entgegen. Wie Leslie Lamport einst so treffend beobachtet hat, ist „ein Verteiltes System eines, in dem der Ausfall eines einzigen Computers, von dessen Existenz Sie noch nicht einmal wussten, Ihren eigenen Computer unbrauchbar machen kann.“

Sicherzustellen, dass Verteilte Systeme sowie die darauf aufsetzenden Dienste zuverlässig funktionieren, ist eine zentrale Herausforderung der Forschung zu Verteilten Systemen. Erschwert wird diese Herausforderung zum Teil durch die vielfältigen Ursachen für einen Computerausfall – Stromausfälle, Hardware-Defekte, Software-Fehler, Fehlkonfigurationen, böswillige oder egoistische Benutzer, Unterbrechungen der Kommunikation und Zugangskonflikte, um nur einige zu nennen. Erschwerend kommt der Umstand hinzu, dass „zuverlässig“ für jeden Dienst eine völlig andere Bedeutung haben kann. In einem Dienst kann sich die Zuverlässigkeit auf korrekte und konsistente Rückantworten beziehen, während bei einem anderen die Schnelligkeit der Antworten höchste Priorität hat.

Forschungsaufgabe: Replikation von Diensten zur Maskierung von Ausfällen

Computer oder Software-Systeme so zu entwickeln, dass sie niemals ausfallen, ist ein seit jeher angestrebtes und ehrenwertes Ziel, dessen Erreichen jedoch noch aussteht. Daher müssen Verteilte Systeme auf die Möglichkeit hin gestaltet werden, dass (einige) einzelne Komponenten ausfallen können. Diese Ausfälle müssen maskiert werden, um sicherzustellen, dass die Rückantworten, die der Anwender durch den Gesamtdienst erhält, korrekt und konsistent sind.

Die Replikation von Zustandsautomaten (State Machine Replication) ist eine gängige Methode, um den Ausfall eines von einem einzelnen Computer bereitgestellten Dienstes zu maskieren. Die Grundidee hinter dieser Methode ist einfach: Implementierung des Dienstes als deterministischer Zustandautomat, Erstellung mehrerer Kopien dieses deterministischen Zustandautomaten, Sicherstellung, dass jede Kopie des Zustandautomaten Benutzerabfragen in derselben Reihenfolge verarbeitet, und schließlich Auswahl der Antwort anhand eines Votings (Quorums) unter allen Zustandsautomaten. Damit stellt die Replikation der Zustandsautomaten prinzipbedingt sicher, dass der Dienst auch dann verfügbar bleibt, wenn einige Computer aufgrund eines Ausfalls nicht reagieren. Darüber hinaus sorgt die Replikation der Zustandsautomaten durch die Voting-Stufe dafür, dass der Dienst korrekt arbeitet und den Benutzern konsistente Antworten liefert, selbst wenn einige Computer fehlerhaft arbeiten und ungültige Ergebnisse liefern.

Selbstverständlich verursacht die Replikation mehr Kosten als singulär laufende Dienste. Diese Mehrkosten sind jedoch für alle Dienste unumgänglich, die zwingend verfügbar und konsistent sein müssen. Größter Kostenfaktor der Replikation ist die Koordination der Replikate, die sicherstellt, dass sie die Benutzeranfragen in derselben Reihenfolge verarbeiten. Einen Konsens zur Reihenfolge der Benutzeranfragen zu erhalten, ist kompliziert. Zum einen ist nicht sichergestellt, dass die Benutzer die Anfragen an die Replikate in derselben Reihenfolge stellen. Das heißt, die Replikate müssen sich selbst untereinander koordinieren. Zum anderen leitet ein fehlerbehafteter Computer eine Anfrage möglicherweise nicht an alle Replikate weiter oder – noch schlimmer – verhält sich äquivok. Von Äquivokation sprechen wir dann, wenn ein Computer an verschiedene Kommunikationspartner unterschiedliche Informationen ausgibt. Im Zusammenhang mit der Replikation von Zustandsautomaten meldet ein sich äquivok verhaltendes Replikat unterschiedliche Reihenfolgen der Benutzeranfragen. Damit säht es Verwirrung und verhindert einen Konsens zur Reihenfolge der Benutzeranfragen.

Neueste Fortschritte in der Hardware-Technik haben zur Entwicklung besonders verlässlicher Computer-Komponenten geführt (Trusted Components), die fehlerbehaftete Computer präventiv daran hindern können, sich äquivok zu verhalten. Also ging die landläufige Meinung davon aus, dass man diese Komponenten nutzen könnte, um die Kosten der Zustandsautomaten-Replikation zu senken. In vorangehenden Arbeiten konnte jedoch nachgewiesen werden, dass diese Annahme falsch ist [1]. Wie sich zeigte, hindert die Nicht-Äquivokation einen fehlerbehafteten Computer lediglich daran, zwei verschiedenen Kommunikationspartnern unterschiedliche Informationen zu liefern – verhindert jedoch nicht, dass er dem einen Partner falsche und dem anderen gar keine Informationen liefert. Dieses selektive Schweigen ist letztlich genauso gefährlich wie eine aktive Falschaussage.

Forschungsaufgabe: Replikation von Diensten zur Reduzierung der Latenzzeiten

Viele Internetdienste verfügen über umfangreiche Nutzergruppen, die über die ganze Welt verteilt sind. Um die Nutzer an diese Dienste zu binden, sind kurze Reaktionszeiten auf Nutzeranfragen unverzichtbar. Diese Forderung steht jedoch im Widerspruch zur von der Zustandsautomaten-Replikation benötigten Koordination sowie zu den Netzwerk-Latenzen, die auftreten, wenn eine Kommunikation mit einem Zentralserver auf der anderen Seite des Globus erfolgen muss. Als Lösung für diese Szenarios bietet sich die Replikation des Dienstes an mehreren Standorten in der Nähe der Nutzer-Cluster an. Damit entfallen die netzwerkbedingten Latenzen – zumindest solange die Nutzeranfragen verarbeitet werden können, ohne dass die Replikate sich untereinander koordinieren müssen. Ist eine sofortige Koordination unter den geo-replizierten Replikaten erforderlich, entfallen jedoch die Latenz- und Verfügbarkeitsvorteile der Geo-Replikation. Bei der Argumentation im Zusammenhang mit dieser Art geo-replizierter Dienste hat sich das Konsistenzkonzept der Eventual Consistency als vorherrschendes Paradigma herausgebildet.

Eventual Consistency beinhaltet eine einfache Idee: „Irgendwann (eventually) sehen alle Replikate gleich aus.“ Das heißt, bei Eventually-Consistent-Systemen können die einzelnen Replikate die Benutzeranfragen lokal verarbeiten und diese dann mit der Zeit an weitere Replikate weiterleiten (propagieren). Die beiden Forderungen der Eventual Consistency lauten: Irgendwann haben die Nutzeranfragen alle Replikate erreicht, und jedes Replikat-Paar, das dieselben Nutzeranfragen verarbeitet hat, muss in denselben Zustand konvergieren. Während die Forderung der Propagierung nicht weiter kompliziert ist und durch einfachen Informationsaustausch realisiert werden kann, stellt sich die Konvergierung der Replikate deutlich schwieriger dar.

Systeme der Eventual Consistency erreichen die Konvergenz der Replikate in der Regel dadurch, dass alle Nutzeranfragen kommutieren müssen, das heißt, die Reihenfolge, in der die Nutzeranfragen auf ein Replikat angewandt werden, darf nicht den endgültigen Zustand dieses Replikats beeinflussen. Es konnte nachgewiesen werden, dass kommutative Nutzeranfragen eine notwendige Bedingung sind, um letztendlich eine Konvergenz der Replikate zu erreichen, dass jedoch eine sofortige Koordination notwendig sein kann, wenn die Semantik der Anwendung durch Invarianten im Dienstezustand begrenzt ist [2].

Fazit

Verteilte Systeme bilden die Infrastruktur für viele Dienste, die unseren Alltag bestimmen. Die Replikation ist eine leistungsfähige Methode zum Aufbau zuverlässiger Dienste und kann zur Sicherstellung der Korrektheit und Verfügbarkeit dieser Dienste genutzt werden. Die Ausgestaltung effizienter Replikationsmethoden stellt dabei eine genauso wichtige wie fundamentale Hausforderung in der Forschung zu Verteilten Systemen dar.

Literaturhinweise

1.
Clement, A.; Junqueira, F.; Kate, A.; Rodrigues, R.
On the (limited) power of non-equivocation
In: Proceedings of the 2012 ACM symposium on Principles of distributed computing (PODC '12). ACM, New York 2012, pp. 301-308
2.
Li, C.; Porto, D.; Clement, A.; Gehrke, J.; Preguica, N.; Rodrigues, R.
Making geo-replicated systems fast as possible, consistent when necessary
In: Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation (OSDI '12). USENIX Association, Berkeley 2012, pp. 265-278
Zur Redakteursansicht