Konsistenzerhaltung

Die Konsistenzerhaltung (engl. consistency control) dient in der Informatik der Erhaltung der Konsistenz bei der Ausführung von Operationen in verteilten Systemen. Die Konsistenzerhaltung ist Teil der Synchronisation, im Fachbereich Computer Supported Cooperative Work wird sie durch Late-Join ergänzt.

Das Problem

Zwei Teilsysteme A und B eines verteilten Systems besitzen identische Anfangszustände, d. h. ihre Zustände sind konsistent. Nun ändert A ein Datum x seines Zustands – man nennt dies Operation – und schickt die Änderung an B. Fast gleichzeitig ändert auch B das Datum x seines Zustandes und schickt eine Mitteilung an A. Da die beiden Änderungen dasselbe Datum x betreffen – man sagt, sie seien konfliktär – haben A und B nach Empfang der Mitteilungen des jeweils anderen am Ende verschiedene Zustände. Ein Beispiel:

Das Beispiel zeigt, dass sowohl die Reihenfolge der Ausführung von Operationen als auch der Ausführungszeitpunkt einer Operation kritisch ist.

Formalisierung

Für eine Operation ist nicht nur wichtig, wann sie erzeugt wurde, sondern auch, wann sie ausgeführt wird. Man nennt eine Operation abhängig von einer anderen Operation, wenn sie logisch gesehen nach dieser ausgeführt werden muss. Operationen, die nicht abhängig voneinander sind, sind nebenläufig. Mit diesen Begriffen lassen sich nun die folgenden Kriterien definieren, deren Erfüllung zur Konsistenzerhaltung beiträgt:

• Kausalität: Wird eine abhängige Operation bei allen Instanzen des verteilten Systems nach der Operation ausgeführt, von der sie abhängt, so spricht man von Kausalität. Kausalität alleine garantiert noch keine Konsistenzerhaltung, denn über nebenläufige Operationen ist hiermit noch nichts ausgesagt.
• Konvergenz: Führen alle Instanzen des verteilten Systems dieselbe Menge von Operationen aus und haben am Ende alle denselben Zustand, so spricht man von Konvergenz. Konvergenz ist ein stärkeres Kriterium als Kausalität, garantiert aber lediglich, dass der Endzustand der Instanzen gleich ist; übergangsweise eingenommene Zwischenzustände können durchaus voneinander abweichen.
• Korrektheit: Angenommen, es gebe eine „perfekte Instanz“ innerhalb des verteilten Systems, die alle Operationen zum Zeitpunkt ihrer Erzeugung ausführt. Haben nach dem Ausführen einer Menge von Operationen alle Instanzen denselben Endzustand wie diese perfekte Instanz, so spricht man von Korrektheit. Absolut gleichzeitig erzeugte Operationen werden mit Hilfe eines „Tie-Break“-Kriteriums zeitlich hintereinander angeordnet. Korrektheit ist das stärkste Kriterium; es erfüllt gleichzeitig auch das Kriterium Konvergenz.

Realisierung

Zur Einhaltung der Kriterien der Konsistenzerhaltung werden Zustandsvektoren verwendet. Wird eine Operation erzeugt, so wird ihr ein Zustandsvektor zugewiesen. Dieser enthält für alle Instanzen je eine Sequenznummer. Die Sequenznummer einer Instanz gibt an, welche Operationen diese Instanz bis zu diesem Zeitpunkt bereits ausgeführt hat. Der Zustandsvektor einer Operation gibt also die Zustände aller Instanzen zu dem Zeitpunkt an, als die Operation erzeugt wurde. Gemeinsam mit der Operation wird nun auch deren Zustandsvektor verschickt. Zusätzlich zu den Operationen führt auch jede Instanz einen Zustandsvektor mit sich.

Der Empfänger kann das Kriterium Kausalität auf einfache Weise überprüfen, indem er den empfangenen Zustandsvektor mit seinem eigenen Zustandsvektor vergleicht. Ist die Sequenznummer der Instanz, die die Operation erzeugt hat, genau um 1 größer als die Sequenznummer dieser Instanz im eigenen Vektor und sind alle anderen Sequenznummern des Zustandsvektors der Operation kleiner oder gleich der entsprechenden Sequenznummern im eigenen Vektor, so ist die Operation kausal ausführbar, d. h. die Kausalität bleibt bei ihrer Ausführung gewahrt.

Auch die Korrektheit kann mit Hilfe der Zustandsvektoren überprüft werden. Dazu wird eine Relation kleiner als eingeführt, die die Summe aller Sequenznummern zweier Zustandsvektoren miteinander vergleicht. Ist diese Summe einer Operation kleiner als die einer anderen, so ist die Operation kleiner als die andere. Ist die Summe gleich, so wird wiederum ein Tie-Break-Kriterium angewandt, um die Operationen künstlich voneinander zu unterscheiden; es könnten z. B. Identifikationsnummern der beteiligten Instanzen verglichen werden. Die Kleiner-als-Relation umfasst automatisch auch die kausale Abhängigkeit; ist also eine Operation kleiner als eine andere, so ist letztere auch von ersterer abhängig.

Die Kleiner-als-Relation ordnet eine Menge von Operationen so an, wie sie von einer perfekten Instanz ausgeführt werden würde. Um die Korrektheit zu wahren, muss eine Instanz also alle bisherigen Operationen so ausführen, dass sie den Endzustand einnimmt, den sie hätte, wenn sie alle Operationen in der Reihenfolge der Kleiner-als-Relation ausgeführt hätte.

Erweiterung auf kontinuierliche Vorgänge

Die bisher beschriebene Realisierung ist auf diskrete Anwendungen zugeschnitten, also solche, die keine zeitlichen Vorgänge beinhalten. Liegen jedoch kontinuierliche Vorgänge vor, d. h. ist auch der zeitliche Ablauf von Bedeutung, so werden die folgenden Kriterien der Konsistenzerhaltung verwendet:

• Konsistenz: Haben alle Instanzen eines verteilten Systems zu einem Zeitpunkt den gleichen Endzustand – nachdem sie alle Operationen empfangen haben, deren Ausführungszeitpunkt vor diesem Zeitpunkt liegt – so spricht man von Konsistenz. Konsistenz ist ein schwaches Kriterium, denn es erlaubt vorübergehend unterschiedliche Zwischenzustände und macht keine Angaben dazu, in welcher Reihenfolge oder zu welchem Zeitpunkt die Operationen nun tatsächlich ausgeführt werden müssen.
• Korrektheit: Angenommen, es gebe eine perfekte Instanz innerhalb des verteilten Systems, die alle Operationen zu ihrem Ausführungszeitpunkt ausführte. Haben zu einem Zeitpunkt – nach dem Empfang aller Operationen mit früherem Ausführungszeitpunkt – alle Instanzen denselben Endzustand wie diese perfekte Instanz, so spricht man von Korrektheit. Korrektheit ist das stärkste Kriterium; es erfüllt auch hier gleichzeitig das Kriterium Konvergenz.

Absolut gleichzeitig erzeugte Operationen sollten bei guten Uhren nicht auftreten, können aber auch hier mit Hilfe eines Tie-Break-Kriteriums zeitlich hintereinander angeordnet werden. Die Kausalität spielt hier eine deutlich untergeordnete Rolle und wird nur zusätzlich eingesetzt, um grobe Fehler zu vermeiden (etwa das Verändern eines Objektes, bevor es erzeugt wurde).

Sinnlose Zustände

Die bisher beschriebenen formalisierten Verfahren der Konsistenzerhaltung scheitern jedoch alle an einer Hürde: Sie können den Sinn von Operationen nicht erkennen. Dementsprechend führt auch die sorgfältige Einhaltung aller Konsistenzerhaltungs-Kriterien noch zu unangenehmen Effekten:

• Eine Instanz kann zeitweise einen Zustand aufweisen, der inkonsistent ist; man nennt dies temporäre Inkonsistenz. Wird diese temporäre Inkonsistenz vom Benutzer wahrgenommen, so spricht man von Artefakten. Artefakte äußern sich z. B. in „springenden“ Spielfiguren in Computerspielen, wenn zu spät eingetroffene Operationen nachträglich in den Spielablauf eingepflegt werden.
• Weist eine Instanz Artefakte auf, so kann der Benutzer aufgrund der fehlerhaften Informationen Entscheidungen fällen, die er sonst nicht gefällt hätte; man spricht hier von sekundären Inkonsistenzen. Sie äußern sich z. B. darin, dass der Spieler eines Computerspiels anders reagiert hätte, wenn er gewusst hätte, dass sein Gegner bereits vor ihm steht.