Vector Clock

In Datenbanken wie DynamoDB, Riak oder Cassandra. Wenn du ein Objekt speicherst, bekommt es eine Vector Clock. Wenn zwei User offline editieren und dann syncen: Die Datenbank vergleicht die Vektoren.

• Wenn V1 < V2: Alles gut, V2 ist neuer. Überschreibe V1.
• Wenn V1 und V2 unvergleichbar sind (Konflikt!): Die Datenbank wirft einen Fehler ("Sibling") und du (die App) musst entscheiden, wie gemerged wird.

1. Der Algorithmus

Jeder Prozess $P_i$ hat einen Vektor $V$.

1. Internes Event: $V[i] = V[i] + 1$.
2. Sende Nachricht: Schicke $V$ mit. $V[i] = V[i] + 1$.
3. Empfange Nachricht mit $V_{msg}$: $V[j] = \max(V[j], V_{msg}[j])$ für alle $j$. Dann $V[i] = V[i] + 1$. Das garantiert: Wenn $V(a) < V(b)$, dann ist $a$ kausal vor $b$ passiert (Happens-Before Relation $\to$).

2. Version Vectors vs Vector Clocks

Oft verwechselt.

• Vector Clocks: Für Events (Prozess-Zustände).
• Version Vectors: Für Replica-Zustände (Daten-Updates). Sie funktionieren mathematisch fast gleich, haben aber andere Regeln für die Update-Logik bei Sync.

1. Partielle Ordnung & Vergleiche

Mathematisch gesehen definieren Vector Clocks eine partielle Ordnung. Man vergleicht zwei Vektoren $V_a$ und $V_b$:

• $V_a < V_b \iff (\forall i: V_a[i] \leq V_b[i]) \land (\exists j: V_a[j] < V_b[j])$. Das bedeutet: Alle Zähler in $a$ sind kleiner oder gleich $b$, und mindestens einer ist echt kleiner. $a$ ist die Ursache von $b$.
• Falls weder $V_a < V_b$ noch $V_b < V_a$ gilt, sind die Ereignisse nebenläufig (concurrent). Das ist die Information, die Lamport-Clocks (eine einzelne Zahl) nicht liefern können. Vector Clocks sind also "Isomorph" zur Kausalität: Sie spiegeln den Informationsfluss im System perfekt wider.

2. Dotted Version Vectors (DVV)

Ein Problem in Systemen mit dem "LWW" (Last-Write-Wins)-Ansatz ist, dass Updates verloren gehen können, wenn ein Node abstürzt und seine Vector Clock vergisst. Dotted Version Vectors erweitern das Konzept um einen "Punkt" (Dot), der ein spezifisches Event eindeutig identifiziert. Dies wird in modernen Datenbanken wie Riak genutzt. Ein Dot (A, 5) bedeutet: "Dies ist das 5. Update von Node A." Dadurch wird verhindert, dass Versionen fälschlicherweise als "gleich" angesehen werden, nur weil die Vektor-Summe zufällig gleich aussieht. Es macht die Konflikterkennung präziser und robuster gegen Nachrichtenverluste.

3. Größe und Pruning

Das größte operative Risiko ist die Unbegrenztheit. Wenn jeder Browser-Tab eines Users als eigener "Prozess" zählt, wird die Liste [P1, P2, ..., Pn] astronomisch groß. In der Produktion (z.B. DynamoDB) nutzt man Logical Pruning. Wenn ein Eintrag im Vektor sehr alt ist (lange nicht inkrementiert), wird er gelöscht. Gefahr: Wenn zwei sehr alte Updates nach langer Zeit wieder auftauchen, könnte das System die Kausalität falsch einschätzen ("False Positives" bei Konflikten). Man muss daher die "Pruning Threshold" so hoch ansetzen, dass sie weit über der maximal erwarteten Synchronisationszeit des Systems liegt.