Das Problem

• Daten werden auf mehrere Knoten repliziert
• Schreibvorgänge müssen auf alle Replicas übertragen werden
• Netzwerklatenz und Ausfälle verhindern sofortige Synchronisation
• Zwei Clients lesen denselben Schlüssel – und erhalten unterschiedliche Werte

Warum nicht einfach stark konsistent?

• Starke Konsistenz erfordert Koordination aller Replicas
• Koordination kostet Latenz und Verfügbarkeit
• Tradeoff: Konsistenz ↔ Verfügbarkeit ↔ Leistung

Beispiel: Banküberweisung

Node A (EU):  Konto = 100 €
Node B (US):  Konto = 100 €  (Replik)

Client schreibt auf Node A:
  Konto = Konto - 50 €  →  50 €

Client liest sofort von Node B:
  Konto = 100 €  ← veralteter Wert!

Frage: Wann ist Node B synchron?
→ Sofort?  (starke Konsistenz)
→ Irgendwann?  (Eventual Consistency)
→ Nur bei Quorum?  (Tunable Consistency)

Drei Garantien – nur zwei gleichzeitig möglich

• C – Consistency: jeder Read liefert den aktuellsten Write oder einen Fehler
• A – Availability: jede Anfrage erhält eine Antwort (kein Fehler, ggf. veraltet)
• P – Partition Tolerance: System funktioniert trotz Netzwerkpartition

Konsequenz

• Netzwerkpartitionen sind in verteilten Systemen unvermeidlich
• → P muss gewählt werden
• → Wahl zwischen C und A bei Partition
• CP-Systeme: Konsistenz bevorzugt (z.B. HBase, Zookeeper)
• AP-Systeme: Verfügbarkeit bevorzugt (z.B. Cassandra, DynamoDB)

Netzwerkpartition tritt auf

Node A ──✗── Node B
   ↑               ↑
Client 1       Client 2

CP: Node B lehnt Reads ab
    bis Partition geheilt
    → Fehler, aber konsistent

AP: Node B antwortet mit
    möglicherweise veraltetem Wert
    → verfügbar, aber inkonsistent

Kritik am CAP-Theorem

• Binäres Modell – Praxis ist ein Spektrum
• PACELC-Modell erweitert CAP um Latenz-Tradeoff

• Erweiterung von CAP durch Daniel Abadi (2012)
• Partition → Availability vs. Consistency
• Else (kein Partition) → Latency vs. Consistency
• Auch im Normalbetrieb gibt es einen Tradeoff: schnelle Antwort vs. Koordinationsaufwand

Kategorien

• PA/EL: Verfügbarkeit + niedrige Latenz (DynamoDB, Cassandra)
• PC/EC: Konsistenz auch im Normalbetrieb (Spanner, HBase)
• PA/EC: Verfügbarkeit bei Partition, Konsistenz sonst (MongoDB)

ACID – relationale Datenbanken

• Atomicity: Transaktion ganz oder gar nicht
• Consistency: DB bleibt in gültigem Zustand
• Isolation: parallele Transaktionen sehen sich nicht
• Durability: nach Commit dauerhaft gespeichert

• Starke Garantien, aber schwer skalierbar
• Koordination zwischen Knoten kostet Latenz

BASE – NoSQL-Systeme

• BAsically Available: System antwortet immer
• Soft State: Zustand kann sich ohne Schreibvorgang ändern (Replikation)
• Eventually Consistent: irgendwann konsistent

• Schwächere Garantien, hohe Verfügbarkeit und Skalierbarkeit
• Applikation muss Konflikte tolerieren oder auflösen

Fazit

• ACID und BASE sind kein Widerspruch – sie sind Designziele
• Viele Systeme bieten Tuning: von ACID bis BASE

• Stärkstes Konsistenzmodell für einzelne Operationen
• Jede Operation erscheint atomar und sofort an einem einzigen Zeitpunkt
• Reads sehen stets den aktuellsten abgeschlossenen Write
• Globale, totale Ordnung aller Operationen
• Entspricht dem Verhalten eines einzelnen Servers

Umsetzung

• Konsensprotokoll: Paxos, Raft
• Alle Replicas stimmen vor Rückantwort ab
• Kostet: hohe Latenz, eingeschränkte Verfügbarkeit bei Partition

Beispiel

Zeit →

Client A:  Write(x=1) ────────────────▶ OK
Client B:             Read(x) ────────▶ 1  ✓

Linearisierbar:
  Read nach abgeschlossenem Write
  muss neuen Wert liefern

Nicht linearisierbar:
Client A:  Write(x=1) ──────────────▶ OK
Client B:      Read(x) ──────▶ 0  ✗
  (Write abgeschlossen, aber 0 gelesen)

Systeme

• Google Spanner (TrueTime)
• etcd, ZooKeeper (Linearizable reads)
• Cassandra: CONSISTENCY ALL

• Alle Prozesse sehen Operationen in derselben globalen Reihenfolge
• Die Reihenfolge muss mit der lokalen Programmreihenfolge eines jeden Prozesses verträglich sein
• Keine Echtzeit-Garantie: Reihenfolge muss nicht der Wanduhr entsprechen
• Schwächer als Linearisierbarkeit, aber stärker als Kausalkonsistenz

Unterschied zur Linearisierbarkeit

• Linearisierbarkeit: Echtzeitordnung der Operationen
• Sequentielle Konsistenz: nur Programm-Reihenfolge innerhalb eines Prozesses
• → Nicht-überlappende Ops können in beliebiger Reihenfolge erscheinen

Beispiel: sequentiell konsistent, aber nicht linearisierbar

Prozess P1:  Write(x=1)
Prozess P2:  Write(x=2)

Prozess P3 sieht:  x=1, dann x=2  ✓
Prozess P4 sieht:  x=1, dann x=2  ✓
→ alle sehen gleiche Reihenfolge ✓

Aber: P2 schrieb x=2 vor P1 (Wanduhr)
→ Reihenfolge entspricht nicht Realzeit
→ nicht linearisierbar, aber
  sequentiell konsistent ✓

• Operationen, die kausal voneinander abhängen, werden von allen Prozessen in der richtigen Reihenfolge gesehen
• Kausalität: A → B, wenn B A „gesehen" hat (Happens-Before-Relation)
• Nebenläufige (nicht-kausale) Ops dürfen in beliebiger Reihenfolge sichtbar werden
• Schwächer als sequentielle Konsistenz, besser skalierbar

Happens-Before (→)

• Innerhalb eines Prozesses: alle Ops in Programmreihenfolge
• Nachricht: Senden → Empfangen
• Transitiv: wenn A→B und B→C, dann A→C

Beispiel

P1:  Post("Frage?")          Write(x=1)
P2:  Read(x=1) → Reply("Antwort!")
P3:  ?

Kausal konsistent:
  P3 sieht erst "Frage?", dann "Antwort!"
  (weil Reply kausal von Post abhängt) ✓

Nicht kausal konsistent:
  P3 sieht erst "Antwort!", dann "Frage?"
  → Ursache kommt nach Wirkung ✗

Implementierung

• Vektoruhren oder logische Zeitstempel
• MongoDB Causal Consistency Sessions

• Schwächstes praktisch relevantes Konsistenzmodell
• Wenn keine neuen Writes erfolgen, konvergieren irgendwann alle Replicas
• Keine Garantie über Zeitpunkt oder Reihenfolge der Konvergenz
• Liest können veraltete Werte liefern

Vorteile

• Maximale Verfügbarkeit: kein Warten auf Koordination
• Minimale Latenz: sofortige lokale Antwort
• Geeignet für: Shopping-Carts, DNS, Social Feeds, Sensor-Daten

Herausforderungen

• Anwendung muss mit veralteten Daten umgehen können
• Konfliktauflösung bei konkurrierenden Writes notwendig

Beispiel: DNS

DNS-Eintrag geändert:
  example.com → neue IP

Nameserver A:  kennt neue IP sofort
Nameserver B:  liefert noch alte IP
Nameserver C:  liefert noch alte IP

Nach TTL (z.B. 300 s):
  alle Nameserver: neue IP ✓

→ Eventual Consistency

Cassandra Beispiel

-- Konsistenzlevel ONE:
-- antwortet nach 1 Replica
-- möglicherweise veraltet
CONSISTENCY ONE;
SELECT * FROM sensor_data
WHERE id = 's-001';

Vier Session-Guarantees (Terry et al. 1994)

• Read-your-writes (RYW): ein Client sieht immer seine eigenen Writes
• Monotonic Reads (MR): Reads werden nie „zurückgedreht" – kein älterer Wert nach neuerem
• Writes Follow Reads (WFR): ein Write nach einem Read wird hinter dem gelesenen Wert eingeordnet
• Monotonic Writes (MW): Writes eines Clients erscheinen in Reihenfolge

Read-your-writes (häufigste Anforderung)

Client schreibt: Profil-Update
Client liest sofort: eigenes Profil

Ohne RYW:
  → Client sieht altes Profil ✗
  → frustrierend!

Mit RYW:
  → Client wird immer zu Replica
     geleitet, die seinen Write kennt ✓

Implementierung:
  - Sticky Session (immer gleicher Node)
  - Session Token mit Versions-Info

Monotonic Reads

Read 1:  Konto = 150 €
Read 2:  Konto = 100 €  ✗ (älter!)

Mit MR:  nie rückwärts in der Zeit

• N: Replikationsfaktor (Anzahl Kopien)
• W: Anzahl Bestätigungen beim Schreiben
• R: Anzahl Antworten beim Lesen

Starke Konsistenz: W + R > N

• Lese- und Schreib-Quorum überlappen sich → mindestens eine Replica ist aktuell
• Typisch: N=3, W=2, R=2 → QUORUM

Schwache Konsistenz: W + R ≤ N

• Keine Überlappung garantiert → Reads können veraltet sein
• Typisch: N=3, W=1, R=1 → ONE (Eventual Consistency)

Konfigurationen (N = 3)

Tradeoff

• Hohe W → schreiblastige Systeme langsamer
• Hohe R → leselastige Systeme langsamer

• Mechanismus zur Erfassung von Kausalität ohne globale Uhr
• Jeder Knoten hält einen Zähler pro Knoten im System
• Bei Ereignis: eigener Zähler wird inkrementiert
• Bei Nachricht: Vektoren werden komponentenweise per Max gemergt

Vergleich

• V(A) < V(B) → A happened-before B (kausal abhängig)
• V(A) und V(B) unvergleichbar → nebenläufig (Konflikt möglich)

Beispiel (3 Knoten: A, B, C)

Initial:  A=[0,0,0]  B=[0,0,0]  C=[0,0,0]

A schreibt x=1:
  A=[1,0,0]  → sendet an B

B empfängt, schreibt x=2:
  B=max([0,0,0],[1,0,0])+1B
  B=[1,1,0]  → sendet an C

C empfängt, schreibt x=3:
  C=[1,1,1]

Nebenläufig (Konflikt):
A schreibt x=4:  A=[2,0,0]
B schreibt x=5:  B=[1,2,0]
→ [2,0,0] und [1,2,0] unvergleichbar
  → Konflikt! Auflösung notwendig

Wann entstehen Konflikte?

• Zwei Clients schreiben denselben Schlüssel nebenläufig auf verschiedene Replicas
• Netzwerkpartition: Writes auf isolierten Partitionen
• Eventual-Consistency-Systeme akzeptieren solche Writes

Auflösungsstrategien

• Last-Write-Wins (LWW): Timestamp entscheidet – einfach, aber Writes können verloren gehen
• Multi-Version: alle Versionen aufbewahren, Client löst auf (Amazon Dynamo)
• Merge-Funktion: domänenspezifische Zusammenführung (z.B. Sets vereinigen)
• CRDT: konfliktfreie Datenstrukturen (automatische Auflösung)

Last-Write-Wins (LWW)

Node A:  x = "Alice"  ts=1000
Node B:  x = "Bob"    ts=1001

Sync: ts=1001 gewinnt → x = "Bob"
"Alice" geht verloren!

Problem: Clock Skew (Uhren laufen unterschiedlich)
→ ts=1000 auf A könnte real später sein
→ NTP hilft, garantiert aber nichts

Multi-Version (Dynamo-Stil)

Shopping Cart:
  v1: ["Buch"]            VC=[1,0]
  v2: ["Buch","Stift"]    VC=[1,1]
  v3: ["Buch","Heft"]     VC=[2,0]

v2 und v3 nebenläufig → beide behalten
Client sieht beide → wählt Vereinigung:
  ["Buch","Stift","Heft"]

• Datenstrukturen, bei denen nebenläufige Updates automatisch und deterministisch zusammengeführt werden
• Merge-Funktion ist kommutativ, assoziativ und idempotent
• Keine Koordination notwendig – immer verfügbar
• Zwei Varianten: State-based (CvRDT) und Op-based (CmRDT)

Beispiele

• G-Counter: wächst nur (verteilter Zähler, nur Inkrement)
• PN-Counter: Inkrement + Dekrement
• G-Set: Set, nur Hinzufügen (kein Löschen)
• LWW-Register: Last-Write-Wins Register
• OR-Set: Observed-Remove Set (Löschen möglich)

G-Counter (Grow-only Counter)

Node A zählt: +2  →  A=[2, 0, 0]
Node B zählt: +3  →  B=[0, 3, 0]
Node C zählt: +1  →  C=[0, 0, 1]

Merge (komponentenweises Maximum):
  Max([2,0,0],[0,3,0],[0,0,1])
  = [2, 3, 1]

Gesamtwert = Summe = 6
→ kein Konflikt, kein Koordinationsbedarf

Einsatz

• Riak: CRDT-basierte Datentypen
• Redis: CRDT-Erweiterungen
• Figma, SoundCloud: kollaborative Echtzeit-Anwendungen

Synchrone Replikation

• Alle Replicas müssen Write bestätigen, bevor Client Antwort erhält
• Starke Konsistenz: alle Replicas immer aktuell
• Hohe Schreiblatenz (= Latenz des langsamsten Replica)
• Verfügbarkeit leidet bei Replica-Ausfall

Asynchrone Replikation

• Client erhält sofort Antwort; Replikation im Hintergrund
• Niedrige Schreiblatenz
• Replica kann zeitweise veraltet sein (Replikationsverzögerung)
• Bei Primärausfall: Datenverlust möglich

Konsensbasierte Replikation (Raft/Paxos)

• Mehrheitsbeschluss: Write gilt, wenn Mehrheit (Quorum) bestätigt
• Starke Konsistenz + Fehlertoleranz
• Höhere Latenz als async, besser als sync zu allen Replicas
• Leader koordiniert alle Writes

Vergleich

Cassandra – Tunable Consistency

• Konsistenzlevel pro Anfrage konfigurierbar
• ONE → Eventual Consistency
• QUORUM + QUORUM (W+R > N) → starke Konsistenz
• LOCAL_QUORUM für Multi-Datacenter

Google Spanner – Externe Konsistenz

• Linearisierbarkeit global, über Datacenter hinweg
• TrueTime-API: GPS + Atomuhren, bekanntes Zeitfenster
• Commits warten auf Ablauf des Unsicherheitsintervalls
• Stärkstes Konsistenzmodell in einem verteilten System

ZooKeeper – Sequentielle Konsistenz

• Alle Writes werden linear über Leader abgewickelt (ZAB-Protokoll)
• Clients sehen Writes in derselben Reihenfolge
• Reads können von Follower-Nodes beantwortet werden (veraltet möglich)
• sync() erzwingt Aktualität vor Read

DynamoDB

• Standard: Eventually Consistent Reads (niedriger Preis)
• Option: Strongly Consistent Reads (2× RCU)
• Transaktionen: ACID über mehrere Items/Tabellen

Fazit

• Kein Modell ist universell besser – Wahl hängt vom Anwendungsfall ab
• Kritische Daten (Finanzen, Reservierungen) → starke Konsistenz
• Skalierung, Verfügbarkeit priorisiert → Eventual Consistency