CAP-Theorem

CAP-Theorem

Das CAP-Theorem oder Brewer's Theorem besagt, dass es für ein System zum verteilten Rechnen unmöglich ist, gleichzeitig die drei Eigenschaften Konsistenz, Verfügbarkeit und Partitionstoleranz zu garantieren.[1][2]

Inhaltsverzeichnis

Eigenschaften

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 die selben Daten.
  • Verfügbarkeit (A): Alle Anfragen an das System werden stets beantwortet.
  • Partitionstoleranz (P): Das System arbeitet trotz willkürlicher Verluste von Nachrichten weiter.

Das CAP-Theorem läßt sich anschaulich mit der folgenden Abbildung darstellen[4]:

Veranschaulichung des CAP-Theorems

Die System-Eigenschaften C, A und P sind dabei als graduelle Größen zu sehen, 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 (etwa ACID-Prinzip relationaler Datenbanksysteme) oder erst nach einem gewissen Zeitfenster der Inkonsistenz (BASE-Prinzip vieler NoSQL-Datenbanken).

Ein konkretes verteiltes System liegt immer auf einem der Schenkel (CA), (CP) oder (AP) dieses Dreiecks. Da man eigentlich immer an hoher Verfügbarkeit interessiert ist, kann man diskutieren, ob ein CP-System wirklich Sinn macht und man im realen Leben nur die Wahl zwischen (CA) und (AP) hat. Weiterhin steht man bei verteilten Systemen bei der Eigenschaft der Partitionstoleranz nicht wirklich vor einer Wahl – will man ein ausfallsicheres verteiltes System haben, ist P stets Voraussetzung.

Geschichte

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 Brewer's Vermutung, und etablierten diese somit als Theorem.[1]

Beispiele[4]

DNS – Domain Name System

Das DNS ist der 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.

RDBMS – Relationales Datenbank Management System

Die klassischen RDBMSe wie DB2 oder Oracle garantieren vor allem eins: Konsistenz. Grundlagen dieser System ist das ACID-Prinzip: Zugriffe sind stets atomar, konsistent, isoliert und dauerhaft.

Ein RDBMS fällt in die Kategorie (CA). Verfügbarkeit und Konsistenz sind bei einem Einzelsystem in der Regel sehr hoch. Setzt man ein Datenbank-Cluster mit Replikation zwischen mehreren Knoten ein, sinkt die Verfügbarkeit, da eine konsistente Transaktion nun länger dauert. Mit steigender der Anzahl der Knoten verlängert sich die Dauer einer Transaktion.

Cloud Computing

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) in die Kategorie (AP) fällt.

Da eine Konsistenz im Sinne des ACID-Prinzips wegen des CAP-Theorems nun nicht mehr gewährleistet werden kann, eine völlig inkonsiste 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. BASE steht für: 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.

Einzelnachweise

  1. a b Lynch, Nancy, and Seth Gilbert. “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. a b Grundlagen Cloud Computing: CAP-Theorem
  5. Brewer, Eric. Towards Robust Distributed Systems

Wikimedia Foundation.

Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • CAP — als Abkürzung steht für: CAP (Automobilhersteller), ehemaliger belgischer Automobilhersteller CAP (Markt), eine Supermarktkette betrieben von behinderten/benachteiligten Menschen CAP Customer Advantage Program GmbH, verantwortlich für HappyDigits …   Deutsch Wikipedia

  • Theorem von Bayes — Das Bayestheorem (auch Satz von Bayes) ist ein Ergebnis der Wahrscheinlichkeitstheorie, benannt nach dem Mathematiker Thomas Bayes. Es gibt an, wie man mit bedingten Wahrscheinlichkeiten rechnet. Inhaltsverzeichnis 1 Formel 2 Interpretation 3… …   Deutsch Wikipedia

  • Cap & Trade — Der Emissionsrechtehandel oder auch Handel mit Emissionszertifikaten ist ein Instrument der Umweltpolitik mit dem Ziel, Schadstoffemissionen mit möglichst geringen volkswirtschaftlichen Kosten zu verringern. In der Europäischen Union wurde der EU …   Deutsch Wikipedia

  • Cap and Trade — Der Emissionsrechtehandel oder auch Handel mit Emissionszertifikaten ist ein Instrument der Umweltpolitik mit dem Ziel, Schadstoffemissionen mit möglichst geringen volkswirtschaftlichen Kosten zu verringern. In der Europäischen Union wurde der EU …   Deutsch Wikipedia

  • Теорема CAP — (известная также как теорема Брюера), в информатике  эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств: согласованность данных… …   Википедия

  • Théorème CAP — Le théorème CAP ou CDP, aussi connu sous le nom de théorème de Brewer dit qu il est impossible sur un système informatique de calcul distribué de garantir en même temps les trois contraintes suivantes[1],[2] : Cohérence : tous les nœuds …   Wikipédia en Français

  • Teorema CAP — El Teorema CAP, también llamado Teorema de Brewer, establece que es imposible para un sistema de computo distribuido dar simultaneamente las siguientes tres garantías:[1] [2] Consistencia (Consistency): todos los nodos ven la misma información al …   Wikipedia Español

  • Bayes' theorem — In probability theory, Bayes theorem (often called Bayes law after Thomas Bayes) relates the conditional and marginal probabilities of two random events. It is often used to compute posterior probabilities given observations. For example, a… …   Wikipedia

  • Chinese remainder theorem — The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra. In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers.… …   Wikipedia

  • Lasker–Noether theorem — In mathematics, the Lasker–Noether theorem states that every Noetherian ring is a Lasker ring, which means that every ideal can be written as an intersection of finitely many primary ideals (which are related to, but not quite the same as, powers …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”