Multimaster-Replikation

Arno SchmidhauserLetzte Revision: März 2010Email: arno.schmidhauser@bfh.chWebseite: http://www.sws.bfh.ch/db

Replikation ist allgegenwärtig

• Durch die Verfügbarkeit von Daten auf verschiedensten Endgeräten mitunterschiedlicher Connectivity sindheute viele Datenbestände in mehreren Replikaten vorhanden:

– Filesysteme– Emails– Kalender– SQL-Datenbanken– Applikationsobjekte

Ausgangslage für Multimaster-Replikation

• Replizierte Daten sollen in einer beliebigen Topologie abgleichbar sein, insbesondere sternförmig (Server mit Clients) oder N:N (Clients unter sich, oder Server unter sich).

• Der Abgleich zwischen den Knoten findet zeitlich zufällig zu nicht vorhersehbaren Zeitpunkten statt.

• Das Schlussresultat aller Abgleiche in einem Replikatsnetz soll unabhängig von der Abgleichreihenfolge sein.

→ Verfahren mit Zeitstempeln→ Verfahren mit Versionenvektoren→ Verfahren mit Versionenvektoren für Knoten

Verfahren mit Zeitstempeln

X = 1 (t1)

T1: x = 2

X = 2 (t2)

X = 3 (t3) gewinnt

X = 3 (t3)

X = 1 (t1)

X = 2 (t2) gewinnt

X = 3 (t3) gewinnt

X = 3 (t3)

X = 1 (t1)

T3: x = 3

X = 3 (t3)

X = 3 (t3) gewinnt

X = 3 (t3)

send X = 2

send X = 3

send X = 3

send X = 2

Der Zeitstempel-Vergleich kann nicht unterscheiden zwischen einer neueren Version eines Datensatzes und einem Konflikt zwischen zwei Datensätzen !

Knoten R1 Knoten R2 Knoten R3

Version xi eines Datenelementes

Verfahren mit Versionenvektoren

• Ein Versionenvektor ermöglicht die Steuerung des Datenabgleichs und die Erkennung von Konflikten in einer beliebigen Topologie. Jedes Datenelement (Datensatz, File etc) wird dazu um folgende Informationen ergänzt:

– Eine VersionenID, bestehend aus KnotenID und fortlaufender Versionennummer für den Knoten, der die letzte Änderung vorgenommen hat.

– Ein Vektor von Versionennummern, welche die letzte bekannte Änderung an diesem Datensatz für jeden Knoten im Replikationsnetz wiedergeben.

Daten VersionenID Versionenvektor

100 R1, 5 5, 3, 1

Versionenvektor, einfacher Ablauf

x=0, [R1,1], [1,0,0]

x=1, [R1,2], [2,0,0] x=1, [R1,2], [2,0,0]

x=2, [R2,1], [2,1,0] x=2, [R2,1], [2,1,0]

x=3, [R3,1], [2,1,1]

T

T

T

send

send

Knoten R1 Knoten R2 Knoten R3

x=3, [R3,1], [2,1,1]x=3, [R3,1], [2,1,1]sendsend

Versionenvektor, KonflikterkennungAnhand der zwei Versionenvektoren wird festgestellt, ob beim Abgleich zweier Versionen eines Datensatzes ein Konflikt vorliegt, oder eine erlaubte Update-Operation durchgeführt werden kann.

Xi = 100, [R1,1], [1,0,0]

Xk = 101, [R1,2], [2,0,0]

Xi = 100, [R1,1], [1,0,0]

Xk = 104, [R3,2], [2,0,2]

Xi = 102, [R1,2], [2,1,0]

Xk = 104, [R3,3], [2,0,3]

Beispiel 1 Beispiel 2 Beispiel 3

Kein Konflikt, nur Update Konflikt, unabhängige ÄnderungenKein Konflikt, nur Update

Versionenvektoren, Vergleichsoperatoren

• Ein Versionenvektor V dominiert den Versionenvektor W, wenn beide die gleiche Anzahl Einträge (Dimension) haben und gilt: V[i] ≥ W[i] für jedes i.

Beispiel: [3,0,2] dominiert [2,0,1]

• Zwei Versionenvektoren sind inkompatibel, wenn keiner den anderen dominiert.

Beispiel: [3,0,2] und [2,1,0] sind inkompatibel.

Abgleichregeln für Datensätze

AusgangslageDie Datensatzversion Xi werde vom Knoten R1 an den Knoten R2 zum Abgleich geschickt. Auf R2 existiert bereits die Datensatzversion Xk. Vi sei der Versionenvektor von Xi und Vk sei der Versionenvektor von Xk.

Abgleichsregeln1. Wenn Vk dominiert Vi : keine Aktion

2. Wenn Vi dominiert Vk : Xi ersetzt Xk

3. Wenn Vi und Vk inkompatibel : Konfliktauflösung notwendig.

Versionenvektor, Ablauf mit Konflikten

x=3, [R3,1], [2,1,1]

Knoten R1 Knoten R2 Knoten R3

x=3, [R3,1], [2,1,1]x=3, [R3,1], [2,1,1]

x=4, [R1,3], [3,1,1]

T

x=5, [R2,2], [2,2,1]

T

sendx=5, [R2,2], [2,2,1]send

x=4, [R1,4], [4,2,1]

x=5, [R2,2], [2,2,1]

x=4, [R1,4], [4,2,1]send

Konfliktauflösung

sendx=4, [R1,4], [4,2,1]

Update

x=4, [R1,4], [4,2,1]

Versionenvektor für Knoten• Um Datensätze in Paketen mit anderen Knoten abzugleichen, wird für

jeden Knoten als Ganzes ein Versionenvektor mitgeführt.

• Der Versionenvektor gibt den Stand des Knotens bezüglich abgeglichenen Versionen an. Beispiel: Versionenvektor [10,5,3] auf dem Knoten R1 bedeutet, dass R1 selber als Letztes die Versionen-nummer 10 vergeben hat, dass R1 alle Versionen von Knoten R2 bis und mit 5 erhalten hat, und dass R1 von Knoten R3 alle Versionen bis und mit 3 erhalten hat.

• Nach jedem Abgleich wird der Versionenvektor des Knotens, der den Abgleich angefordert hat, aktualisert.

• Der Eintrag im Versionenvektor, der dem eigenen Knoten entspricht, enthält die Versionennummer des letzten auf dem eigenen Knoten geänderten Datensatzes.

Knoten R1

x[R1,1],[1,0,0]

[1,0,0]

Knoten R2

[0,1,0]

Knoten R3

(0,0,1]

y[R2,1],[0,1,0] z[R3,1],[0,0,1]

[0,1,0]

[1,1,0]

x[R1,1],[1,0,0]

[0,0,1] y[R2,1],[0,1,0]

x[R1,1],[1,0,0]

(1,1,1] [1,1,0]

z[R3,1],[0,0,1]

[1,1,1] [1,0,0]

y[R2,1],[0,1,0]

z[R3,1],[0,0,1]

[1,1,1)

Anfrage

Anfrage

Anfrage

Anfrage

Knoten R1

x[R1,1],[1,0,0]

[1,1,1]

Knoten R2 Knoten R3

x[R1,1],[1,0,0]

[1,1,1]

x[R1,1],[1,0,0]

[1,1,1]

[1,1,1]

x[R3,2],[1,0,2]

T

[1,1,2]

x[R3,2],[1,0,2]

[1,1,2]

T

[2,1,1]

x[R1,2],[2,0,0]

[2,1,1]

x[R3,2],[1,0,2]

[3,1,2]

x[R1,3],[3,0,2]

Anfrage

Anfrage

Konfliktauflösung

usw. usw.

Abgleichprozesse

• Da der Aufbau der Replikationsfähigkeit die Struktur der Nutzdaten einer Datenbank nicht beeinflussen sollte, werden folgende Zusatzinformation meist in eigenen Datenbank-Tabellen abgelegt:– Angaben zur VersionenID und zum Versionenvektor alter oder

aktueller Datensätze – VersionenID und Versionenvektor von gelöschten Datensätzen

(tombstone table)

– Versionenvektor des Knotens als Ganzes

• Da alle für die Replikation benötigten Daten selber persistent sind, kann die gesamte Replikation transaktionsorientiert durchgeführt werden und ist damit selbst fehlersicher und concurrent.

Microsoft Sync Framework

• Universales Replikationsframework für Datenelemente (Datensätze, relationale Tabellen, Emails, News)

Microsoft Sync Framework

• Die Metadaten zur Kontrolle des Abgleichs zwischen den Replikaten basiert auf Versionenvektoren, mit folgenden Vereinfachungen:– Ein vollständiger Versionenvektor wird nur auf

Knotenebene, nicht auf Datenelement-Ebene mitgeführt.

– Datenelemente besitzen eine VersionenID (KnotenID und Versionennummer).

Knoten A

x[A,cA=2]

VA[AA=2,AB=0]

Knoten B

VB[BA=0,BB=3]

y[B,cB=3]

Abgleich

III CAP

CAP - Prinzip

Eine nützliche Betrachtung von replizierten und verteilten System geht von drei Hauptanforderungen aus:

• ConsistencyDie Daten aller Knoten eines replizierten Datenbestandes müssen zu jeder Zeit vollständig übereinstimmen.

• AvailabilityJede mögliche Anfrage an das System muss von mindestens einem Knoten sofort beantwortet werden können.

• Partition ToleranceEin Knoten der eine Anfrage bearbeitet muss dies auch dann tun können, wenn andere Knoten ausfallen oder nicht verfügbar sind.

Ein verteiltes System kann leider nie alle drei Bedingungen gleichzeitig erfüllen, sondern höchstens zwei davon!

CAP, Replikationsarten

Replikationsarten

Synchronität Symmetrie

Asynchron Synchron

Asymmetrisch

Symmetrisch C jaA nein P ja

C neinA ja P ja

C neinA ja P ja

C jaA neinP Ja

C jaA jaP nein

C jaA jaP nein