CAP-Theorem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Das CAP-Theorem oder Brewers Theorem besagt, dass es in einem verteilten System unmöglich ist, gleichzeitig die drei Eigenschaften Konsistenz, Verfügbarkeit und Partitionstoleranz zu garantieren.[1][2]

Eigenschaften[Bearbeiten]

Veranschaulichung des CAP-Theorems

Laut dem CAP-Theorem kann ein verteiltes System zwei der folgenden Eigenschaften gleichzeitig erfüllen, jedoch nicht alle drei[3].

Konsistenz (C)
Alle Knoten sehen zur selben Zeit dieselben Daten. Diese Konsistenz sollte nicht verwechselt werden mit der Konsistenz aus der ACID-Transaktionen, die nur die innere Konsistenz eines Datenbestandes betrifft.
Verfügbarkeit (A)
Alle Anfragen an das System werden stets beantwortet.
Partitionstoleranz (P)
Das System arbeitet auch bei Verlust von Nachrichten, einzelner Netzknoten oder Partition des Netzes weiter.

Da nur zwei dieser drei Anforderungen in verteilten Systemen gleichzeitig vollständig erfüllt sein können, wird das CAP-Theorem oft als Dreieck visualisiert, bei dem eine konkrete Anwendung sich auf eine der Kanten einordnen lässt.

Die System-Eigenschaften C, A und P können dabei als graduelle Größen gesehen werden, d.h. die Verfügbarkeit ist hoch, wenn das System schnell antwortet, und gering, wenn das System langsam antwortet. In Hinblick auf die Konsistenz bedeutet das, dass diese entweder sofort sichergestellt ist (bei strikter Konsistenz) oder erst nach einem gewissen Zeitfenster der Inkonsistenz („BASE“-Prinzip (= Basically Available, Soft state, Eventual consistency) vieler NoSQL-Datenbanken).[4]

Geschichte[Bearbeiten]

Das Theorem entstand im Jahr 2000 als eine Vermutung des Informatikers Eric Brewer an der University of California, Berkeley beim "Symposium on Principles of Distributed Computing" (PODC).[5] Im Jahr 2002 veröffentlichten Seth Gilbert und Nancy Lynch vom MIT einen axiomatischen Beweis von Brewers Vermutung, und etablierten diese somit als Theorem.[1]

Beispiele[Bearbeiten]

AP – Domain Name System (DNS) oder Cloud Computing[Bearbeiten]

Das Domain Name System ist der Internet-Dienst, mit dem symbolische Hostnamen wie de.wikipedia.org zu numerischen IP-Adressen zur TCP/IP-Kommunikation aufgelöst werden.

Das DNS fällt in die Kategorie AP. Die Verfügbarkeit ist extrem hoch, ebenso Toleranz gegenüber dem Ausfall einzelner DNS-Server. Allerdings ist die Konsistenz nicht immer sofort gegeben: es kann mitunter Tage dauern, bis ein geänderter DNS-Eintrag an die gesamte DNS-Hierarchie propagiert ist und damit von allen Clients gesehen wird.

Cloud-Plattformen setzen auf eine horizontale Skalierung, das heißt die Last wird auf viele Knoten verteilt, die aus billiger, nicht unbedingt ausfallsicherer Hardware bestehen (können). Daher muss eine Cloud-Anwendung zwingend Toleranz gegenüber dem Ausfall einzelner Knoten zeigen können. Eine hohe Verfügbarkeit wird auch gefordert. Daraus folgt, dass eine Cloud-Anwendung (zumindest in großen Teilen) auch in die Kategorie AP fällt. Beispiele für Web-Anwendungen, die nicht auf strenge Konsistenz angewiesen sind, wären Social-Media-Sites wie Twitter oder Facebook; wenn einzelne Nachrichten nicht bei allen Nutzern gleichzeitig eintreffen, ist dadurch die prinzipielle Funktion des Dienstes nicht beeinträchtigt.

Da eine strenge Konsistenz wegen des CAP-Theorems hier nicht mehr gewährleistet werden kann, eine völlig inkonsistente Datenhaltung aber auch nicht gewünscht ist, muss man sich mit schwächeren Konsistenzbedingungen abfinden. Als Gegenstück zum ACID-Prinzip der relationalen Datenbanken setzen viele NoSQL-Datenbanken auf das BASE-Prinzip: Basically Available, Soft State, Eventual consistency. Eventual consistency lässt sich sinngemäß gut mit „schlussendlicher Konsistenz“ übersetzen, das heißt: das System ist nach Ablauf einer gewissen (möglichst kurzen) Zeitspanne der Inkonsistenz wieder in einem konsistenten Zustand.

CA – Relationales Datenbank Management System (RDBMS)[Bearbeiten]

Die klassischen Relationalen Datenbanken wie DB2 oder Oracle streben vor allem Konsistenz an.

Ein RDBMS-Cluster fällt meistens in die Kategorie CA. Sie streben vor allem Verfügbarkeit und Konsistenz aller Knoten an. Da sie meistens mit hochverfügbaren Netzwerken und Servern betrieben werden, müssen sie nicht unbedingt gut mit einer Partitionierung umgehen können. Wie schon erwähnt, sind C, A und P eben graduelle Größen.

CP – Banking-Anwendungen[Bearbeiten]

Für verteilte Finanzanwendung wie z. B. Geldautomaten ist die Konsistenz der Daten oberstes Gebot: Ein abgehobener Geldbetrag muss zuverlässig auch auf der Kontenseite abgebucht werden, eingezahltes Geld muss auf dem Konto erscheinen. Diese Anforderung muss auch bei Störungen im Datenverkehr sichergestellt werden (Partitionstoleranz).

Gegenüber der Konsistenz und der Partitionstoleranz ist die Verfügbarkeit zweitrangig (CP): bei Netzwerkstörungen soll ein Geldautomat oder ein anderer Service eher nicht verfügbar sein als nicht korrekte Transaktionen abwickeln. Eine Alternative könnte es auch sein, bei einer Partitionierung den maximal abhebbaren Geldbetrag zu reduzieren, um den möglichen Schaden zu reduzieren. Diese Lösung ist dann jedoch fachlich und hat mit dem CAP-Theorem selber nicht mehr so viel zu tun.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. a b Gilbert, Seth and Lynch, Nancy. “Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services.” ACM SIGACT News, v. 33 issue 2, 2002, p. 51–59.
  2. julianbrowne.com: Brewer's CAP Theorem. Retrieved 02-Mar-2010.
  3. royans.net: Brewers CAP theorem on distributed systems
  4. 12 years later - the rules have changed
  5. Brewer, Eric. Towards Robust Distributed Systems (PDF, 229 kB)