Was ist die Begründung für das GAP-Theorem?

21

http://en.wikipedia.org/wiki/CAP_theorem

http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

Ich denke, es ist nicht ganz einfach, warum nur zwei von

  1. Konsistenz
  2. Verfügbarkeit
  3. Partitionstoleranz

Kann für jedes beliebige verteilte Datenbanksystem gelten. Diese Vermutung wurde bewiesen , aber ist es ein einfacher Weg , um zu sehen , warum wohl diese halten könnte?

Ich suche keinen Beweis, nur einen guten Weg, um zu verstehen, warum dieser Satz Sinn macht. Was ist die Begründung?

Laser
quelle

Antworten:

23

Stellen wir uns vor, Sie haben eine verteilte Datenbank. Angenommen, Sie haben einen Knoten in Oregon und einen in Kalifornien. Die CAP-Theorie besagt, dass Sie beim Einrichten dieses Datenbanktyps auf Probleme stoßen werden.

Wenn Sie beispielsweise Daten aus einer Datenbank abfragen, müssen diese mit den Daten in der anderen Datenbank übereinstimmen. Dies stellt sicher, dass sich der Wert, den Sie in einer Datenbank haben, garantiert in der anderen befindet ( Konsistenz der GAP-Theorie). Auf diese Weise können Sie die Daten in einer Datenbank aktualisieren und von einer anderen abfragen, um die gleichen Ergebnisse zu erzielen.

Ein Computer, der Daten in Oregon aktualisiert, überträgt die Daten nach Kalifornien

Wenn wir die Daten im Oregon-Knoten aktualisieren, werden die Daten an den California-Knoten gesendet, damit die Datenbanken konsistent sind. Um die Konsistenz wirklich aufrechtzuerhalten, müssen wir sicherstellen, dass beide Datenbanken das Update erhalten, bevor beide die Daten wirklich speichern dürfen (zweiphasiges Commit mit verteilten Transaktionen). Mit anderen Worten, wenn die kalifornische Datenbank die Daten aus irgendeinem Grund nicht speichern kann (z. B. Festplattenfehler), speichert die Datenbank in Oregon die Daten nicht und schlägt die Transaktion fehl.

Das Problem mit verteilten Transaktionen wie der obigen tritt auf, wenn wir eine hohe Verfügbarkeit wünschen. In diesem Szenario ist der Versuch, beide Datenbanken synchron zu halten, sehr, sehr langsam. (Stellen Sie sich vor, wir müssen die Daten von Oregon nach Kalifornien senden, sicherstellen, dass sie dort ankommen, dass beide Datenbanken Sperren für die Daten aufweisen usw.) Dies führt zu großen Problemen, wenn wir ein System wünschen, das auch während dieser Zeit schnell und reaktionsfähig ist Zeiten hoher Nachfrage. (Dies ist die Verfügbarkeit des CAP-Theorems.)

Um eine hohe Verfügbarkeit zu gewährleisten, verwenden wir in der Regel die Replikation anstelle verteilter Transaktionen. Anstatt also zu garantieren, dass Kalifornien die Daten akzeptieren kann, speichern wir sie einfach im Oregon-Knoten und senden sie dann nach Kalifornien, wenn wir dort ankommen. Dies garantiert, dass wir die Daten immer speichern können, unabhängig davon, ob California bereit ist, die Daten zu speichern oder nicht.

Der Oregon-Knoten aktualisiert die Daten, während Kalifornien die Daten liest.  Später werden die Daten nach Kalifornien verschoben

Dies verbessert die Verfügbarkeit, jedoch auf Kosten der Konsistenz. Sehen Sie, wenn jemand die Daten in Oregon aktualisiert und dann jemand (zur gleichen Zeit) die Daten in Kalifornien liest, erhält er die neuen Daten nicht - die Datenbanken sind nicht mehr konsistent. In der Tat werden sie nicht konsistent sein, bis Oregon die Daten nach Kalifornien sendet!

Das ist also der Kompromiss zwischen Verfügbarkeit und Konsistenz.

Partitionstoleranz ist der dritte Aspekt der CAP-Theorie. Partitionierung ist in diesem Zusammenhang die Idee, dass eine Datenbank (oder ein anderes verteiltes System) in separate Abschnitte unterteilt werden kann und dennoch ordnungsgemäß funktioniert.

Es stellt sich die Frage, was passiert, wenn beide Datenbanken ordnungsgemäß ausgeführt werden, die Verbindung von Oregon nach Kalifornien jedoch getrennt ist.

Oregon wird aktualisiert, während der California-Knoten gelesen wird.  Das Netzwerk zwischen den Knoten wird getrennt.

Wenn wir die Datenbank in Oregon aktualisieren, müssen wir die Daten auf die eine oder andere Weise nach Kalifornien bringen (verteilte Transaktion oder Replikation). Wenn jedoch die Verbindung zwischen den beiden getrennt wird, ist das System partitioniert und die Datenbanken sind nicht mehr miteinander verbunden.

In diesem Fall haben Sie die Wahl, Aktualisierungen nicht mehr zuzulassen (um die Konsistenz aufrechtzuerhalten) und dies zu Lasten der Verfügbarkeit oder zu Lasten der Konsistenz zuzulassen (um die Verfügbarkeit aufrechtzuerhalten).

Wie Sie sehen, führt die Partitionstoleranz zu direkten Kompromissen zwischen Konsistenz und Verfügbarkeit.


Es steckt offensichtlich mehr dahinter, aber das sind ein paar Beispiele dafür, wie diese drei Hauptaspekte verteilter Systeme für und gegeneinander funktionieren. Julian Brownes Erklärung der CAP-Theorie ist ein ausgezeichneter Ort, um mehr zu lernen.

Richard
quelle
Zugehörige Antwort von Remus Rusanu.
Nick Chammas
Mit einem viel schöneren Bild dabei!
Richard