Datenreplikation und Konsistenz

Datenreplikation hält mehrere Kopien von Daten für Verfügbarkeit und Performance vor, und Konsistenzprotokolle regeln, wie Lese- und Schreibvorgänge über diese Kopien hinweg abgeglichen werden.

Definition

Datenreplikation pflegt Kopien eines Datenelements auf mehreren Knoten; ein Konsistenzmodell spezifiziert die Garantien bezüglich der Werte, die Lesezugriffe zurückgeben können, gegeben die Historie der Schreibzugriffe, reichend von stark (jeder Lesezugriff sieht den neuesten Schreibzugriff) bis eventuell (Repliken konvergieren, wenn Aktualisierungen aufhören).

Scope

Dieses Thema behandelt Replikationsstrategien (Primary-Backup, Multi-Master, Quorum), Quorum-basierte Lese-/Schreibprotokolle und deren Schnittmengenanforderungen, Anti-Entropie und Gossip für die eventuelle Konvergenz, Konflikterkennung mit Versionsvektoren und konfliktfreien replizierten Datentypen (CRDTs) sowie das Spektrum der Konsistenz von linearisierbar bis eventuell. Es behandelt das Gegenstück der Zustandsmaschinenreplikation auf Datenebene.

Core questions

• Wie garantieren Quorum-Größen für Lese- und Schreibvorgänge, dass Lesezugriffe den neuesten Schreibzugriff beobachten?
• Wie konvergieren Repliken unter Eventual Consistency, und wie werden Konflikte gelöst?
• Welches Konsistenzniveau sollte eine Anwendung angesichts ihrer Latenz- und Verfügbarkeitsanforderungen wählen?

Key theories

Quorum-Konsens für replizierte Daten

Indem Repliken Stimmen zugewiesen werden und Lese- und Schreibquoren erforderlich sind, deren Größen sich zu mehr als der Gesamtanzahl addieren, schneidet jedes Lesequorum das neueste Schreibquorum, wodurch garantiert wird, dass Lesezugriffe aktuelle Daten beobachten.

Eventual Consistency und Anti-Entropie

Hochverfügbare Stores akzeptieren Schreibvorgänge an jeder Replik und gleichen diese asynchron über Gossip und Versionsvektoren ab, wobei nur garantiert wird, dass Repliken konvergieren, wenn Aktualisierungen aufhören, wie am Dynamo-Design exemplarisch gezeigt wird.

Konfliktfreie replizierte Datentypen

CRDTs sind Datentypen, deren Operationen so konzipiert sind, dass sie kommutieren oder deren Zustände ein Join-Halbgitter bilden, sodass gleichzeitige Aktualisierungen deterministisch ohne Koordination zusammengeführt werden, was eine starke Eventual Consistency bietet.

Clinical relevance

Diese Techniken definieren die Garantien realer Speichersysteme: Quorum-Protokolle sind die Grundlage stark konsistenter Key-Value-Stores, während Eventual Consistency und CRDTs hochverfügbare Stores, Warenkörbe und kollaborative Editoren antreiben, bei denen Verfügbarkeit Vorrang vor sofortiger Übereinstimmung hat.

History

Giffords gewichtetes Abstimmungsschema von 1979 etablierte die Quorum-Replikation; Amazons Dynamo-Paper von 2007 popularisierte die hochverfügbare Eventual Consistency; und die Formalisierung von CRDTs im Jahr 2011 lieferte eine prinzipielle Grundlage für die koordinationsfreie Konvergenz, die das Design moderner replizierter Daten prägt.

Debates

Wie viel Konsistenz sollten replizierte Daten standardmäßig bieten?

Starke Konsistenz erleichtert die Anwendungsentwicklung, begrenzt jedoch die Verfügbarkeit und erhöht die Latenz, während Eventual Consistency die Verfügbarkeit maximiert, auf Kosten der Exposition temporärer Divergenz; abstimmbare Quoren und CRDTs sind Versuche, Anwendungen die Wahl pro Operation zu ermöglichen.

Key figures

• David Gifford
• Werner Vogels
• Marc Shapiro
• Andrew S. Tanenbaum

Seminal works

• gifford1979
• decandia2007
• shapiro2011

Frequently asked questions

Wie garantieren Lese- und Schreibquoren aktuelle Lesezugriffe?

Wenn ein Schreibvorgang W Repliken erreichen muss und ein Lesevorgang R Repliken konsultieren muss, und R plus W die Gesamtzahl der Repliken übersteigt, dann überlappt jedes Lesequorum das jüngste Schreibquorum in mindestens einer Replik, sodass der Lesevorgang den neuesten Wert beobachten kann.