State machine replication for highly available service networks

Abstract

Service networks of arbitrary network topology are known from stream and complex event processing systems. As service networks are often required to be highly available, this raises the question, whether replication mechanism known from traditional database or client/server systems can be transferred to generic service networks. State machine replication is well-known to provide both, availability and strong consistency, even in the presence of node failures. When nodes crash and recover, it is, however, not clear, whether, and in what way, these consistency guarantees can be transferred to the service network as a whole. To solve this, we propose a protocol that enables the interconnection of replicated services to a consistent, semi-dynamic service network. Our protocol is built upon a persistent enumeration system for messages produced by the state machine and upon a replicated log, which provides “intelligent” guarantees on the entries that are committed. A formal proof verifies the correctness of the protocol for normal operation as well as during recovery. We finally conduct a quantitative evaluation to give an impression of the possible performance of the protocol.

Hohe Verfügbarkeitsanforderungen an vernetzte Dienste mit beliebiger Netzwerktopologie, wie sie aus dem Bereich der Verarbeitung komplexer Ereignisse als Operatorgraphen bekannt sind, werfen die Frage auf, ob die von klassischen Datenbank- und Client/Server-Anwendungen bekannten Replikationsmechanismen auch auf allgemeine vernetzte Dienste angewendet werden können. Hierbei bietet die Replikation von Zustandsmaschinen bekanntermaßen sowohl hohe Verfügbarkeit als auch starke Konsistenzgarantien, selbst wenn einer oder mehrere Knoten eines Dienstes ausfallen. Insbesondere durch den Ausfall von Knoten, die nach einem Neustart ihren Zustand wiederherstellen, ist allerdings nicht klar, ob oder wie diese Konsistenzgarantien auf den vernetzten Dienst als Ganzes übertragen werden können. Hierfür beschreiben wir ein Protokoll, das die Verknüpfung replizierter Dienste zu einem konsistenten, semidynamischen Gesamtsystem ermöglicht. Das Protokoll baut dabei vor allem auf eine eineindeutige Nummerierung der durch die Zustandsmaschine erzeugten Nachrichten sowie ein um “intelligente” Garantien erweitertes repliziertes Log auf. Ein formeller Beweis verifiziert die Korrektheit des Protokolls sowohl unter normalen Betriebsbedingungen als auch während der Wiederherstellung des Zustands. Schließlich gibt eine quantitative Evaluierung einen ersten Eindruck der möglichen Leistung des Protokolls.