Lamport Clock

In Datenbanken für Total Ordering. Manchmal willst du einfach irgendeine Reihenfolge, die fair ist. Lamport Clocks + Process ID = Eindeutige Reihenfolge. Timestamp.ProcessID. 10.A kommt vor 10.B (weil A < B). So kann man Transaktionen in einer Datenbank global sortieren, ohne Synchronisation.

1. Happens-Before Relation ($\to$)

Der wichtigste Begriff in verteilten Systemen. $a \to b$ gilt, wenn:

1. $a, b$ im selben Prozess sind und $a$ vor $b$ kommt.
2. $a$ ist Senden, $b$ ist Empfangen der selben Nachricht.
3. Transitivität: $a \to x$ und $x \to b$, dann $a \to b$. Lamport Clocks erfüllen die "Clock Condition": $a \to b \implies C(a) < C(b)$.

2. Schwäche

Lamport Clocks können Nebenläufigkeit (Concurrency) nicht erkennen. Wenn $C(a) < C(b)$, könnte $a$ parallel zu $b$ passiert sein oder $a$ vor $b$. Vector Clocks lösen genau das.

1. Transitive Kausalitätslücken

Die mathematische Schwachstelle der Lamport-Uhr ist der fehlende Rückschluss. Wenn $C(a) < C(b)$ ("Prozess A hat Log 10, Prozess B hat Log 20"), bedeutet das nicht, dass $a \to b$ ursächlich gilt. B könnte das Log 20 völlig asynchron am anderen Ende der Welt auf Basis von anderen Modulen erreicht haben. Eine reine Lamport-Uhr verliert also die globale Parallelitäts-Analyse beim Zusammenführen von Logfiles. Die Topologische Sortierung, die durch Lamport-Werte im Data Warehouse entsteht, ist lediglich eine mögliche chronologische Realität, nicht die unumstößlich-historische. Verteilte Tracing-Systeme (Jaeger/Zipkin) benötigen zwingend Vektor-Uhren, um "Spans liefen parallel!" von "Span B wartete auf Span A!" zu trennen.

2. State Machine Replication und Total Ordering

Warum nutzt man sie dann? In verteilten Datenbanken ist Total Ordering (strikt deterministische Anordnung von Updates auf Leader/Followern) existenziell. Wenn 5 Datenbank-Nodes gleichzeitig Mutationen erhalten, müssen sie sich einigen, wer wen überschreibt. Die Erweiterte Lamport-Uhr nutzt das Prozess-ID-Tie-Breaking Protocol. Update A hat Zeitstempel $(45, \text{Node}_1)$. Update B hat $(45, \text{Node}_2)$. Jeder Knoten wendet die Regel an: Sortiere primär nach Lamport-Wert, sekundär nach MAC-Addresse/Node-ID). Da $\text{Node}_1 < \text{Node}_2$ mathematisch global gleich bewertet wird, wird das Array bei allen 5 Nodes zu [Update A, Update B]. Alle State Machines mutieren atomar in identische Zwischenzustände (Basis von Paxos und Raft Loggings).

3. Spanner und das Ende von Lamport (TrueTime)

Lamport löste 1978 das Problem fehlender Atomuhren. Aber Lamport-Clocks erzwingen enormen Message-Overhead, da die Clocks Piggybacked durchs Netzwerk schwimmen müssen. Google's Cloud Spanner beerdigte teilweise Lamports Software-Ansatz durch Hardware: Die TrueTime API. Jedes Google-Datacenter besitzt GPS- und Atomuhren. TrueTime liefert keine einfache Unix-Zeit, sondern ein Zeit-Intervall $[time - \epsilon, time + \epsilon]$, wobei der Fehler $\epsilon$ physikalisch garantiert unter 4ms liegt. Bei einer globalen Transaktion wartet Spanner die Unsicherheit ($\epsilon$) extrem dediziert hard-blocked ab, bevor der Commit durchgewinkt wird. So garantiert Google globale Kausalität (Linearisierbarkeit) nur aus physikalischer Messung der C-Geschwindigkeit heraus, völlig ohne, dass Tokio und New York Lamport-Ticks aushandeln müssen.