Grundlagen Cloud Computing: CAP-Theorem

Ein wesentlicher Aspekt des Cloud Computing ist die nahezu unbegrenzte Skalierbarkeit wie sie etwa von der Google App Engine oder CloudFoundry angeboten werden. Durch die Zusicherung dieser Eigenschaft muss man aber auf andere aus dem Enterprise Computing gewohnte nicht-funktionale Aspekte wie Konsistenz der Daten verzichten. Warum ist das so? Die Antwort auf diese Frage liefert das CAP-Theorem, das ich im Folgenden näher erläutern möchte.

Das CAP-Theorem

Bereits im Jahr 2000, also lange bevor der Begriff Cloud Computing entstand, formulierte Prof. Eric A. Brewer im Rahmen einer Keynote auf dem ACM Symposium über die Prinzipien verteilten Computings das sog. CAP-Theorem. Dieses Theorem ist daher auch als Brewers Theorem bekannt. Zwei Jahre später wurde das Theorem von Seth Gilbert und Nancy Lynch vom MIT formal bewiesen.

Was sagt das Theorem nun aus? Das Akronym CAP steht für die Begriffe Consistency, Availability und Partition Tolerance.

  • Consistency bedeutet, dass alle Clients jederzeit die gleichen Daten sehen.
  • Availability bedeutet, dass alle Clients stets Lese- und Schreibzugriffe durchführen können.
  • Partition Tolerance bedeutet, dass das System auch bei Ausfall einzelner Knoten als Ganzes weiter arbeiten kann.


Brewer hat erkannt, dass in einem verteilten System nur zwei der drei vorgenannten Eigenschaften gleichzeitig gelten können. Diese Tatsache läßt sich anschaulich an der folgenden Abbildung darstellen:

CAP Theorem

Die System-Eigenschaften C, A und P sind dabei als graduelle Größen zu sehen, d.h. die Availability ist hoch, wenn das System schnell antwortet, und gering, wenn das System langsam antwortet. In Hinblick auf die Consistency 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 Partition Tolerance nicht wirklich vor einer Wahl – will man ein ausfallsicheres verteiltes System haben, ist P stets Voraussetzung.

Bevor ich auf die Auswirkungen des CAP-Theorems auf Cloud Computing eingehe, möchte ich kurz noch Beispiele für einige verteilte System nennen.

DNS – Domain Name System

Das DNS, das wir praktisch täglich nutzen ohne es bewusst wahrzunehmen, ist der Dienst, mit dem symbolische Hostnamen wie www.codecentric.de 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. Jeder, der schon mal einen DNS-Server administrieren durfte, weiss aber, dass die Konsistenz nicht immer sofort gegeben ist: es kann mitunter Tage dauern, bis ein geänderter DNS-Eintrag an die gesamte DNS-Hierarchie propagiert ist und damit von allen Clients (den Internet-Nutzern) gesehen wird.

RDBMS – Relationale Datenbank Management Systeme

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 (falls man atomic, consistent, isolated und durable so übersetzen mag).

Ein RDBMS fällt in die Kategorie (CA). Verfügbarkeit und Konsistenz sind bei einem Einzelsystem i.d.R. 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 immer weiter.

CAP-Theorem und Cloud Computing

Cloud-Plattformen setzen auf eine horizontale Skalierung, d.h. die Last wird auf viele Knoten verteilt, die aus billiger Commodity-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, da der Endanwender heutzutage nur noch ein begrenztes Verständnis für lange Antwortzeiten zeigt und im Zweifelsfalls schnell zur Konkurrenz wechselt. 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 wg. des CAP-Theorems nun nicht mehr gewährleistet werden kann, eine völlig inkonsiste Datenhaltung aber auch nicht zielführend ist, muss man sich mit schwächeren Konsistenzbedingungen abfinden. Das ist in vielen Fällen aber auch vollkommen ausreichend.

Das BASE-Prinzip

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. Eventually consistency lässt sich sinngemäß gut mit schlussendlicher Konsistenz übersetzen, d.h. das System ist nach Ablauf einer gewissen (möglichst kurzen) Zeitspanne der Inkonsistenz wieder in einem konsistenten Zustand, so dass alle Clients die gleichen Daten sehen.

Als Beispiel sei hier der Dienst Twitter angeführt. Vielleicht ist Ihnen schon aufgefallen, dass Updates des Profils oder an Follower-Listen nicht immer sofort für andere (oder auch für Sie selbst auf anderen Kanälen, z.B. Web vs. Mobile) sichtbar sind. Ohne zu tief in die Architektur von Twitter vorzudringen, kann man annehmen, dass solche Updates asynchron ausgeführt werden. An dieser Stelle kann man die meist nur kurzzeitige Inkonsistenz aber durchaus tolerieren.

  • Facebook
  • Delicious
  • Digg
  • StumbleUpon
  • Reddit
  • Blogger
  • LinkedIn
Tobias Trelle

3 Antworten auf Grundlagen Cloud Computing: CAP-Theorem

  1. Konstantin sagt:

    Schöner Grundlagen-Beitrag Tobias! Der greift einige Begriffe auf mit denen ich vorher nichts anfangen konnte. RDBMS und DNS sollte jeder Webentwickler kennen. Das BASE-Prinzip kannte ich allerdings noch nicht.

    Schöne Grüße

  2. Sasa sagt:

    Nice summary.

  3. Frisian sagt:

    Gelungene Übersicht. Aber wenn schon auf englisch, dann sollte in der zweiten Grafik besser “state 1″ und “state 2″ statt “Zustand 1″ und “Zustand 2″ stehen, oder?

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>