Sequential Consistency (deutsch: sequentielle Konsistenz) ist ein Konsistenzmodell für nebenläufige und verteilte Systeme. Leslie Lamport definierte es 1979 in dem Aufsatz „How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs“; bis heute ist es der wichtigste Referenzpunkt zwischen starken und schwachen Konsistenzmodellen.
Zwei Bedingungen
Ein System ist sequentiell konsistent, wenn das Ergebnis jeder Ausführung dasselbe ist, als wären alle Operationen in einer einzigen gemeinsamen Reihenfolge nacheinander ausgeführt worden und jede Operation dabei in der Reihenfolge erscheint, die ihr Programm vorgibt. Daraus folgen zwei Bedingungen:
- Programmreihenfolge: Die Operationen eines einzelnen Prozesses erscheinen in genau der Reihenfolge, in der das Programm sie ausführt. Schreibt ein Prozess erst A und dann B, sieht jeder andere Prozess A vor B.
- Eine gemeinsame Gesamtordnung: Es gibt genau eine globale Reihenfolge, in der alle Prozesse die Operationen sehen. Nimmt Prozess 1 an, dass der Write von Prozess 2 vor dem Write von Prozess 3 geschah, gilt diese Sicht für alle Prozesse.
Der zweite Punkt trennt die Sequential Consistency von schwächeren Modellen: Kausale Konsistenz und PRAM-Konsistenz erlauben verschiedenen Prozessen unterschiedliche Gesamtordnungen, solange die kausalen beziehungsweise pro-Prozess-FIFO-Beziehungen gewahrt bleiben.
Einordnung im Spektrum
- Schwächer als Linearisierbarkeit: Die sequentielle Ordnung muss nicht der Echtzeit entsprechen. Eine Leseoperation darf einen bereits abgeschlossenen Write verpassen, solange alle Prozesse dieselbe Reihenfolge sehen. Den formalen Vergleich lieferten Hagit Attiya und Jennifer Welch 1994 mit „Sequential Consistency versus Linearizability“ (ACM TOCS).
- Stärker als Kausale Konsistenz: Es existiert ein gemeinsamer, globaler Konsistenzpunkt; kausale Konsistenz kennt nur eine partielle Ordnung.
- Stärker als Weak Consistency und Eventual Consistency: Diese Modelle garantieren keine sofortige, für alle gleiche Sicht.
Praxis
Sequential Consistency ist einfach zu verstehen, aber in verteilten Systemen teuer: Jede Operation müsste über einen globalen Ordnungspunkt laufen, ähnlich wie bei Quorum-basiertem Konsens. Hardware-Multiprozessoren setzen aus Performancegründen oft schwächere Speichermodelle um (z. B. Total Store Order). In Datenbanken entspricht die stärkste Isolationsebene (Serializable) dem Wunsch nach einer sequentiellen Ausführung; die praktische Snapshot Isolation liegt darunter und erlaubt je Transaktion unterschiedliche Sichten.
Das CAP-Theorem beschreibt das Spannungsfeld: Sequential Consistency steht auf der Konsistenzseite und ist nur mit Einschränkungen bei Verfügbarkeit und Hochverfügbarkeit erreichbar. Die Grundlagen zu Modellen und Herausforderungen liefert der Artikel Verteilte Systeme.