9.3 Voting-Verfahren
9.3.2 Gewichtetes Votieren (Quorum Consensus)
Diese Nachteile können durch verallgemeinerte Voting-Verfahren abgeschwächt werden [Gi79]. Dabei wird jedem Replikat eines Objektes ein bestimmtes Gewicht (Stimmenanzahl) zugeordnet. Zum Lesen eines Objektes muß nun eine Transaktion erst eine bestimmte Anzahl von Stimmen sammeln (Lese-Quorum), ebenso zum Schreiben (Schreib-Quorum). Wenn v die Gesamtanzahl der für ein Objekt vergebenen Stimmen (votes) ist, und r bzw. w das Lese-Quorum (read quorum) bzw. Schreib-Quorum (write quorum), dann müssen folgende beiden Bedingungen erfüllt sein:
-
a) w > v/2
b) r + w > v
Die erste Bedingung garantiert, daß ein Objekt nicht gleichzeitig von mehr als einer Transaktion geändert wird. Weiterhin kann bei einer Netzwerk-Partitionierung die Bedingung in höchstens einer der Partitionen erfüllt werden, so daß parallele Änderungen eines Objekts in mehreren Partitionen ausgeschlossen sind. Die zweite Bedingung verhindert, daß ein Objekt zur gleichen Zeit gelesen und geändert wird. Weiterhin ist damit sichergestellt, daß jedes Lese-Quorum mindestens ein Replikat enthält, das zum Schreib-Quorum des letzten Änderungszugriffs gehörte und damit auf dem aktuellsten Stand ist.
Das anfangs beschriebene Mehrheits-Votieren ergibt sich offenbar als Spezialfall, wenn man jedem Replikat das gleiche Gewicht zuordnet (z.B. 1 Stimme) und r und w eine einfache Mehrheit darstellen. Durch unterschiedliche Gewichtung der Replikate und Festlegung von r und w kann man aber nun in flexibler Weise sowohl die Kosten eines Lese- bzw. Schreibzugriffs als auch die Verfügbarkeit im Fehlerfall bestimmen. So kann man z.B. an einem Rechner einen besonders schnellen Zugriff auf ein Objekt ermöglichen, indem man dem dort gespeicherten Replikat eine hohe Anzahl von Stimmen zuordnet. Je kleiner r (w) gewählt wird, desto schneller sind Lesezugriffe (Schreibzugriffe) auszuführen, da dann weniger Stimmen gesammelt werden müssen. Entsprechend erhöht sich dadurch auch die Verfügbarkeit der Leseoperation (Schreiboperation), da dann die notwendigen Stimmen oft noch eingeholt werden können, selbst wenn ein(ige) Rechner nicht erreichbar ist (sind). Allerdings geht wegen obiger Bedingung b) die Bevorzugung von Leseoperationen immer auf Kosten der Schreibzugriffe und umgekehrt.
Beispiel 9-5
- Objekt A sei an vier Rechnern R1 bis R4 repliziert; die Stimmenverteilung sei <2, 1, 1, 1>, d.h., R1 hält 2 Stimmen, die anderen Rechner jeweils eine (v=5). Wählt man r=3, w=3 sind zwei bis drei Rechner involviert, um einen Lese- oder Schreibzugriff abzuwickeln. Durch die Bevorzugung von R1 genügen zwei Rechner, sobald R1 an dem Quorum beteiligt ist. Der Objektzugriff ist auch noch nach Ausfall jedes der Rechners möglich. Solange R1 verfügbar bleibt, ist der Zugriff auch noch nach Ausfall von zwei der drei anderen Rechner möglich.
Will man Lese- gegenüber Schreibzugriffen bevorzugen, kann man z.B. r=2, w=4 wählen. Damit können Lesezugriffe in R1 lokal abgewickelt werden; dafür sind mindestens drei Rechner (darunter stets R1) an einem Schreibzugriff zu beteiligen. Nach Ausfall von R1 ist das Objekt nicht mehr änderbar.
Die Flexibilität des Voting-Ansatzes wird daran deutlich, daß sich durch spezielle Wahl der Parameter nicht nur das Mehrheits-Votieren, sondern auch das ROWA- Verfahren sowie eines der Primary-Copy-Protokolle als Spezialfälle ergeben:
- Ein ROWA-Verfahren erhält man, indem man jedem Replikat eine Stimme zuordnet und r=1 und w=v (= Anzahl der Replikate) wählt. Dieser Fall unterstützt lokale Lesezugriffe, was beim Mehrheits-Votieren nicht möglich ist.
- Ein Primary-Copy-Verfahren ergibt sich, wenn man der Primärkopie eine Stimme zuweist und allen anderen Replikaten keine Stimme und r=w=1 wählt. Dieses Verfahren verlangt, daß Lesevorgänge an die Primärkopie gerichtet werden. Lokale Kopien ohne Stimmen können wiederum für Lesezugriffe ohne Konsistenzzusicherung genutzt werden.
Auch der Fall von nur zwei Kopien kann mit dem verallgemeinerten Voting-Verfahren besser als beim Mehrheits-Votieren behandelt werden. Wählt man etwa die Stimmenverteilung <2, 1> und r=w=2, dann kann das Lese- bzw. Schreib-Quorum lokal am ersten Knoten erreicht werden. Ein Objektzugriff am zweiten Rechner erfordert stets Kommunikation, um ein ausreichendes Quorum zu bilden. Die zweite Kopie kann dennoch sinnvoll sein, um den Objektzugriff selbst lokal durchzuführen (sofern die Aktualität der Kopie festgestellt wurde). In unserer Bankanwendung (Beispiel 9-1) könnten so in jeder Filiale lokale Konten ohne Kommunikation gelesen und geändert werden. In der Zentralen wird zwar für jeden Kontozugriff Kommunikation zur Sperrbehandlung notwendig, dafür kann die Verarbeitung selbst auf den lokalen Kopien erfolgen.
Ein Hauptproblem bei Voting-Verfahren liegt in der geeigneten Wahl der Stimmenvergabe sowie der Lese- und Schreib-Quoren. Obwohl es zu dieser Thematik eine Reihe von Arbeiten gibt (z.B. [GB85]), erscheint eine für den Praxiseinsatz geeignete Lösung, die keine oder nur eine geringe Involvierung der Systemverwalter erfordert, nicht in Sicht. In der Literatur wurden daneben verschiedene Erweiterungen wie dynamische, mehrdimensionale oder hierarchische Voting-Verfahren vorgeschlagen, die in [Bo91] überblicksartig diskutiert werden.