CAP Theorem

CAP - Consistency, Availability, Partition Tolerance

Konsistenz (Consistency)

• Konsistenter Zustand im verteilten System
• Änderung auf einem Knoten
• Lesezugriff auf replizierten Knoten liefert geänderten Wert

Verfügbarkeit (Availability)

• System bietet akzeptable Reaktionszeit
• Auch bei Ausfall von Knoten und Netzwerkverbindungen

Partitionierungstoleranz (Partition Tolerance)

• Bei Netzwerk-Split: Teilnetze können weiter arbeiten

Zusammenspiel von C, A und P

In einem verteilten System kann P nicht ausgeschlossen werden
Daher macht nur die Diskussion von A und C Sinn

Knoten nicht verfügbar (Ausfall oder nicht erreichbar)

• Entscheidung für C
• Operationen ablehnen
• Keine Verfügbarkeit
• Entscheidung für A
• Operationen auf verfügbaren Knoten zulassen
• Erzeugt möglicherweise inkonstistenten Zustand im Gesamsystem
• Knoten können verschiedene Zustände für gleiches Objekt haben
• Konstistenz später herstellen
• (Eingeschränkte) Verfügbarkeit
• Keine absolute Entscheidung zwischen C und A
• Verschiedene Strategien möglich

BASE

BASE - Basic Available, Soft State, Eventually Consistent

Basic Available

• (Eingeschränkte) Verfügbarkeit als oberstes Ziel

Soft State

• Fenster der Inkonsistenz

Eventually Consistent

• Irgendwann wird ein konsistenter Zustand erreicht

Konsistenz aus Nutzersicht

Beteiligte

• Verteiltes Speichersystem
• Prozesse A und B schreiben und lesen

Starke Konsistenz

• Nach Änderung: A und B sehen immer den neuen Wert
• Alle Replikate müssen aktualisiert sein

Schwache Konsistenz

• A oder B sehen den alten Wert
• z.B. beim Lesen eines Replikats
• Eventual Consistency ist eine Form schwacher Konsistenz

Quoren

Mechanismus zur Konsistenzsteuerung

• Replikationsfaktor n
• Anzahl der Kopien von Datenelementen: n
• Read Quorum r
• Lies r Replikate
• Write Quorum w
• Schreibe r Replikate, melde erst dann erfolgreiches Schreiben
• r + w > n: starke Konsistenz
• r + w <= n: schwache Konsistenz

Read your own writes

Problem

• Ändern auf dem Leader
• Lesen von einem Follower
• z.B. Lesen von unterschiedlichen Geräten

Lösungsansätze

• Daten, die nur vom Nutzer geändert werden können (z.B. Profil) - Lesen immer vom Leader
• Zeitpunkt der letzten Änderung merken - innerhalb einer Minute immer vom Leader lesen, danach beliebig
• Zeitpunkt der letzten Änderung merken - nur dann von einem Follower lesen, wenn dieser aktueller ist

Monotonic Reads

Problem

• Lesen von unterschiedlichen Follower
• Erstes Lesen liefert aktuellere Version als zweites Lesen

Lösungsansatz

• Gleicher Nutzer muss immer vom gleichen Replikat lesen

Consistent Prefix Read 1

Consistent Prefix Read 2

Problem

• Lesen entgegen der Schreibreihenfolge
• Kann bei Sharding auftreten
• Nuzter 1 und 2 schreiben in unterschiedlichen Shards
• Replikate werden entgegen der Schreibreihenfolge aktualisiert
• Shards operieren unabhängig, deshalbe keine globale Ordnung auf den Schreibvorgängen

Lösungsansatz

• Kausale Abhängigkeiten erkennen und berücksichtigen
• Im Beispiel liest Nutzer 2 einen von Nutzer 1 geschriebenen Wert
• Das begründet eine kausale Abhängigkeit

Schreiben bei Knotenausfall

Quorum beim Schreiben (z.B. 2 von 3)

• Fehler beim Schreiben wird ignoriert, wenn Quorum erreicht

Quorum beim Lesen (z.B. 2 von 3)

• Lesen ok, wenn Quorum erreicht
• Schreiben des neuen Wertes auf Replikat mit altem Wert (Read Repair)

Konsistenz

• Replikationsfaktor: n
• Anzahl gelesener Replikate: r
• Anzahl geschriebener Replikate: w
• r + w > n stellt Überlappung von Lesern und Schreibern sicher
• wenigstens ein Leser liefert die neuste Version

Paralleles Schreiben

• userA erhält Rückmeldung, dass x=100 geschrieben wurde (Quorum erfüllt)
• userB erhält Rückmeldung, dass x=200 geschrieben wurde (Quorum erfüllt)
• node3: x=200 wird durch x=100 überschrieben
• node2: x=100 wird durch x=200 überschrieben
• reader liest x per Quorum
• Quorum liefert x=100
• das Schreiben von x=200 geht verloren, obwohl für user2 der Wert x=200 per Quorum bestätigt wurde

Aspekte von Quorum-Konsistenz 1

Konsistenz versus Verfügbarkeit

• r + w < n stellt Konsistenz nicht sicher
• liefert aber eine gewisse Wahrscheinlichkeit für das Lesen der aktuellen Version
• erhöht die Verfügbarkeit des Systems, wenn mehrere Knoten ausfallen

Probleme aus praktischer Sicht bei r + w > n

• Paralles Schreiben und Überschreiben von Werten (z.B bei "first writer wins)"
• Paralleles Lesen und Schreiben, welche Version wird geliefert
• Wiederherstellung von Knoten durch möglicherweise alte Versionen

Aspekte von Quorum-Konsistenz 2

Sloppy Quorums und Hinted Handoff

• Große Cluster: echte Anzahl Knoten N > n (Replikationsfaktor)
• Explizite (feste) Knotenzuordnung für Replikate
• Beispiel
• Datensatz d auf Knoten k3, k10, k15
• Ausfall von k10 und k15, danach Änderung von d
• Kein echtes Quorum erreichbar, aber Schreiben auf k3, k8 und k17 möglich
• Denkbares Vorgehen
• Schreiben auf k3, k8 und k17 (Sloppy Quorum)
• k8 und k17 vermerken "echte" Replikatsknoten (Hinted Handoff)
• Übertragung auf k10 und k15 bei Verfügbarkeit

Schreiben mit Versionen

• Versionen dienen zum Auflösen von Schreibkonflikten