Das CAP-Theorem (auch Brewer’s Theorem) beschreibt den grundlegenden Zielkonflikt verteilter Systeme: Ein verteilter Datenspeicher kann von drei Eigenschaften höchstens zwei gleichzeitig garantieren. Es ist eines der wichtigsten Konzepte hinter Sharding, Cluster und modernen NoSQL-Datenbanken.
Herkunft
Der Informatiker Eric Brewer von der UC Berkeley formulierte die Idee im Jahr 2000 als Vermutung (Conjecture) in seiner Keynote auf der PODC-Konferenz (Principles of Distributed Computing). Zwei Jahre später bewiesen Seth Gilbert und Nancy Lynch vom MIT die Vermutung formal in ihrem einflussreichen Paper „Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services“ – seitdem spricht man vom CAP-Theorem.
Die drei Eigenschaften
- Consistency (Konsistenz): Jede Leseoperation liefert den neuesten geschriebenen Wert – oder einen Fehler. Alle Knoten sehen zu jedem Zeitpunkt denselben Datenstand. Wird ein Wert an einem Knoten geändert, ist die Änderung für alle anderen sofort sichtbar.
- Availability (Verfügbarkeit): Jede Anfrage erhält eine Antwort – nicht notwendigerweise mit den aktuellsten Daten. Das System bleibt auch bei Ausfällen einzelner Komponenten bedienbar. Jeder erreichbare Knoten antwortet garantiert.
- Partition Tolerance (Partitionstoleranz): Das System funktioniert weiter, wenn Nachrichten zwischen Knoten verloren gehen oder ein Netzwerksegment abgeschnitten ist. In verteilten Systemen lassen sich Netzwerkpartitionen nie vollständig ausschließen.
Was das Theorem wirklich besagt
Die populäre Formel „Pick two“ ist irreführend: Bei intaktem Netzwerk kann ein System durchaus alle drei Eigenschaften erfüllen. Erst wenn eine Partition auftritt, muss es sich entscheiden – zwischen Verfügbarkeit und Konsistenz. Ein System ohne Partitionstoleranz funktioniert nur, solange alle Knoten erreichbar sind (praktisch ein einzelner Server, etwa eine klassische relationale Datenbank im Einzelbetrieb).
Die Erweiterung PACELC von Daniel Abadi präzisiert das Bild: If Partition, then Availability or Consistency; Else Latency or Consistency. Also: Bei einer Partition entscheidet sich das System zwischen Verfügbarkeit und Konsistenz – auch ohne Partition gibt es einen Trade-off zwischen Latenz und Konsistenz bei der Datenhaltung, etwa bei synchroner gegenüber asynchroner Replikation.
CP- und AP-Systeme
Aus dem Theorem ergeben sich zwei typische Ausrichtungen:
- CP-Systeme (Consistency + Partition Tolerance) liefern bei einer Partition einen Fehler oder blockieren, bevor sie veraltete Daten zurückgeben. Beispiele: etcd, ZooKeeper, HBase oder MongoDB in der Standardeinstellung. Sie eignen sich für Buchungen, Bestände und Finanztransaktionen, bei denen falsche Antworten schlimmer sind als kurzzeitige Nicht-Erreichbarkeit.
- AP-Systeme (Availability + Partition Tolerance) antworten immer – notfalls mit veralteten Daten, die später durch Eventual Consistency nachgezogen werden. Beispiele: Cassandra, Amazon DynamoDB, CouchDB. Sie eignen sich für stark frequentierte Dienste wie Warenkörbe, Social Feeds oder Metriken.
Das CAP-Theorem erklärt damit den Design-Raum von NoSQL-Systemen und ist die Grundlage für die Abwägung zwischen ACID-Transaktionen und skalierbaren, konsistenzschwächeren Modellen.
Verwandte Grundlagen: Eventual Consistency (die typische AP-Konsistenz), hochverfügbare Systeme in der Praxis – der Begriff Verteilung selbst hat keinen eigenen Artikel, sondern steckt in Cluster und Sharding.