CAP- und Konsistenzmodelle

Konsistenzmodelle definieren, welche Garantien ein repliziertes System hinsichtlich der von Lesezugriffen zurückgegebenen Werte bietet, und das CAP-Theorem begrenzt, welche dieser Garantien unter Netzwerkpartitionen mit Verfügbarkeit koexistieren können.

Definition

Ein Konsistenzmodell ist ein Vertrag zwischen einem replizierten Datenspeicher und seinen Clients, der die zulässigen Ergebnisse gleichzeitiger Lese- und Schreibvorgänge spezifiziert; das CAP-Theorem besagt, dass ein verteiltes Datenspeichersystem bei Vorhandensein einer Netzwerkpartition nicht gleichzeitig linearisierbare Konsistenz und Verfügbarkeit bieten kann.

Scope

Dieses Thema behandelt die formalen Konsistenzmodelle – Linearisierbarkeit, sequentielle Konsistenz, kausale Konsistenz und Eventual Consistency – und deren Stärkeordnung; das CAP-Theorem sowie dessen präzise Formulierung und Beweis; und Verfeinerungen wie PACELC, die auch den Latenz-Konsistenz-Kompromiss bei fehlenden Partitionen berücksichtigen. Es liefert das Vokabular zur Spezifikation und zum Vergleich von Garantien replizierter Systeme.

Core questions

• Wie unterscheiden sich Linearisierbarkeit, sequentielle, kausale und Eventual Consistency in ihrer Stärke?
• Was genau verbietet das CAP-Theorem und was erlaubt es?
• Wie verfeinern Latenzüberlegungen den Konsistenz-Kompromiss, wenn keine Partition vorliegt?

Key theories

Linearisierbarkeit und sequentielle Konsistenz

Linearisierbarkeit erfordert, dass jede Operation atomar zu einem Zeitpunkt zwischen ihrer Aufrufung und Antwort wirksam wird, konsistent mit der Echtzeit; sequentielle Konsistenz verzichtet auf die Echtzeitanforderung und verlangt lediglich eine einzige gültige Interleaving, die die Reihenfolge jedes Prozesses respektiert.

Das CAP-Theorem

Gilbert und Lynch bewiesen, dass kein repliziertes Datenspeichersystem sowohl linearisierbare Konsistenz als auch Verfügbarkeit garantieren kann, wenn das Netzwerk Nachrichten zwischen Replikaten verlieren kann, was während Partitionen eine Wahl erzwingt.

PACELC-Verfeinerung

PACELC erweitert CAP, indem es feststellt, dass ein System auch ohne Partition Latenz gegen Konsistenz eintauscht, sodass Designs durch ihr Verhalten sowohl während Partitionen als auch im Normalbetrieb charakterisiert werden.

Clinical relevance

Jede verteilte Datenbank und jeder Speicherdienst muss ein Konsistenzmodell deklarieren, und die CAP- und PACELC-Kompromisse erklären, warum einige Systeme die Verfügbarkeit priorisieren, während andere die Konsistenz priorisieren; deren Verständnis ist für die Auswahl und den Betrieb von Dateninfrastrukturen unerlässlich.

History

Lamport definierte die sequentielle Konsistenz 1979, und Herlihy und Wing formalisierten die Linearisierbarkeit 1990; Brewer vermutete den CAP-Kompromiss im Jahr 2000, Gilbert und Lynch bewiesen ihn 2002, und Abadis Neufassung von PACELC im Jahr 2012 verdeutlichte, dass Latenz, nicht nur Partitionen, die Konsistenzentscheidungen beeinflusst.

Debates

Wird CAP oft falsch interpretiert?

CAP wird häufig als „wähle zwei von drei“ zusammengefasst, aber das präzise Ergebnis erzwingt eine Konsistenz-Verfügbarkeits-Wahl nur während einer Partition; Kritiker argumentieren, dass diese Vereinfachung den relevanteren alltäglichen Latenz-Konsistenz-Kompromiss, der von PACELC erfasst wird, verschleiert.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

Bedeutet CAP, dass ein System immer nur zwei von Konsistenz, Verfügbarkeit und Partitionstoleranz haben kann?

Nicht ganz. Partitionen sind eine Tatsache von Netzwerken, keine Designentscheidung, daher ist die eigentliche Entscheidung, was während einer Partition zu tun ist: starke Konsistenz opfern, um verfügbar zu bleiben, oder Verfügbarkeit opfern, um konsistent zu bleiben. Wenn keine Partition vorliegt, kann ein System sowohl konsistent als auch verfügbar sein.