C.A.P.-Theorem

4.1 Konsistenz über Brewera

Erstens ist Eric Brewer kein Datenbankexperte und hat auch nie behauptet, einer zu sein. Er gehört zur Gemeinschaft der verteilten Systeme und sein berühmter Vortrag, in dem das CAP-Theorem auftauchte, wurde auf der Konferenz „Principles of Distributed Computing“ gehalten. (Übrigens hielt er zehn Jahre später, im Jahr 2010, erneut einen eingeladenen Vortrag auf derselben Konferenz und nannte in diesem Vortrag insbesondere eine Reihe von Beispielen verteilter Systeme, deren Entwicklung die „ Der Satz von CAP.) In diesem Bereich gibt es eine eigene Interpretation der im Bereich der Datenbanken verwendeten Begriffe.

Der Begriff „sofortige Konsistenz“ bedeutet insbesondere, dass, nachdem der Benutzer vom System eine Benachrichtigung über den erfolgreichen Abschluss eines Datenaktualisierungsvorgangs erhält, das Ergebnis dieses Vorgangs sofort für alle Beobachter sichtbar wird.

Eventuelle Konsistenz bedeutet, dass, wenn über einen ausreichend langen Zeitraum keine neuen Datenaktualisierungsvorgänge in das System gelangen, damit zu rechnen ist, dass sich die Ergebnisse aller vorherigen Datenaktualisierungsvorgänge schließlich auf alle Knoten des Systems ausbreiten und alle Replikatdaten erhalten bleiben konsistent (anscheinend sollte dies so verstanden werden, dass „alle Replikate den gleichen Status haben“.

Unter Berücksichtigung dieses Konsistenzgefühls kann Brewers „Theorem“ als durchaus verständlich und offensichtlich angesehen werden: In jedem verteilten System mit gemeinsam genutzten Daten können nur zwei beliebige Eigenschaften des Netzwerks gleichzeitig gewährleistet werden: Konsistenz, Verfügbarkeit und Partitionstoleranz. In dieser Hinsicht stellt Brewer sogar den Satz von ACID-Eigenschaften dem von ihm vorgeschlagenen Satz von BASE-Eigenschaften gegenüber (Grundsätzlich verfügbar, weicher Zustand, eventuelle Konsistenz – Verfügbarkeit in den meisten Fällen; instabiler Zustand; endgültige Konsistenz). Aber dieser Widerspruch ist meiner Meinung nach ungerechtfertigt, da es im ersten Fall um die logischen Eigenschaften von Transaktionen und im zweiten Fall um die physikalischen Eigenschaften verteilter Systeme geht.

4.2 Beweis des „Theorems“

Viele glauben, dass Brewers „Theorem“ formal bewiesen wurde. Tatsächlich führt der Aufsatz von Seth Gilbert und Nancy Lynch einige (fast) formale Definitionen ein, in deren Kontext der „Satz“ tatsächlich zu einem Satz wird und bewiesen wird. Sehen wir uns jedoch an, wie diese drei Eigenschaften eines verteilten Systems bestimmt werden, von denen nach dem „Theorem“ von Brewer nur zwei Eigenschaften gleichzeitig unterstützt werden können.

Konsistenz wird als atomare oder linearisierbare Konsistenz (atomare oder linearisierbare Konsistenz) bezeichnet und ist eine Eigenschaft des Systems, von dem alle einzelnen Datenobjekte atomar (linearisierbar) sind. Ein atomares Objekt wiederum ist ein Objekt mit mehreren Operationen, sodass der Aufruf der Operation und der Empfang von Antwortdaten sozusagen sofort erfolgen, d. h. Das Objekt akzeptiert den Aufruf der nächsten Operation erst, wenn die vorherige Operation vollständig abgeschlossen ist. Die Reihenfolge, in der Operationen empfangen werden, muss so sein, dass, wenn eine Leseoperation eintrifft, nachdem eine Schreiboperation ausgeführt wurde, die Leseoperation den von dieser oder einer späteren Schreiboperation geschriebenen Wert zurückgeben muss.

Ein verteiltes System ist immer verfügbar, wenn jede von einem nicht ausgefallenen Knoten empfangene Anfrage beantwortet werden muss. Die Widerstandsfähigkeit des Systems gegenüber Netzwerkpartitionen wird als die Aufrechterhaltung der Lebensfähigkeit des Systems im Falle des Verlusts einer beliebigen Anzahl von Nachrichten, die von einem Knoten an einen anderen gesendet werden, modelliert.

Basierend auf diesen Definitionen formulieren Hilbert und Lynch den folgenden Satz (im asynchronen Netzwerkmodell gibt es keine Uhr und Knoten sollten Entscheidungen nur auf der Grundlage empfangener Nachrichten und lokaler Berechnungen treffen):

In einem asynchronen Netzwerkmodell ist es nicht möglich, ein Lese-/Schreibdatenobjekt zu implementieren, das Verfügbarkeit und atomare Konsistenzeigenschaften für alle gültigen Ausführungen (einschließlich derjenigen, bei denen Nachrichten verloren gehen) garantiert.

Dieser Satz wird eigentlich ganz einfach formal mit der Methode „durch Widerspruch“ bewiesen. Der Artikel kommt zu dem Schluss, dass:

In einem asynchronen Netzwerkmodell ist es nicht möglich, ein Lese-/Schreibdatenobjekt zu implementieren, das Zugänglichkeitseigenschaften für alle gültigen Ausführungen und atomare Konsistenz für gültige Ausführungen garantiert, bei denen Nachrichten nicht verloren gehen.

Darüber hinaus wird die Wahrheit des Hauptsatzes für ein teilweise synchrones Netzwerkmodell bewiesen, bei dem jeder Knoten über eine Uhr verfügt, deren angezeigte Zeit mit der gleichen Geschwindigkeit zunimmt, die jedoch nicht synchronisiert sind, d. h. kann verschiedene Zeiten zum gleichen realen Zeitpunkt anzeigen. Es wird gezeigt, dass für diesen Fall keine ähnliche Konsequenz abgeleitet werden kann und es daher für teilweise synchrone Netzwerke mehr Möglichkeiten gibt, verteilte Systeme mit „guten“ Eigenschaften zu organisieren.

Ja, in gewisser Weise (nicht unbedingt im Sinne von Brewers Absicht) können Gilbert und Lynch als Beweis dafür angesehen werden, dass es unmöglich ist, gleichzeitig die Eigenschaften atomarer Konsistenz, Verfügbarkeit und Partitionstoleranz eines Netzwerks in einem einzelnen verteilten System sicherzustellen. Aber was hat das mit Datenbanktransaktionen im Allgemeinen und ACID-Transaktionen im Besonderen zu tun?

4.3 ACID-Transaktionen

Hier ist, was Julian Browne dazu in seiner Notiz zur Diskussion des „Theorems“ von CAP schreibt:

Hilbert und Lynch verwenden in ihrem Beweis den Begriff Atomizität anstelle des Begriffs Konsistenz, was aus technischer Sicht sinnvoller ist, da sich Konsistenz im Sinne von ACID streng genommen auf die idealen Eigenschaften von Datenbanktransaktionen bezieht und bedeutet, dass keine Daten werden dauerhaft, wenn sie gegen bestimmte vorab festgelegte Einschränkungen verstoßen. Wenn wir jedoch davon ausgehen, dass eine vorab festgelegte Einschränkung verteilter Systeme das Verbot des Vorhandenseins mehrerer unterschiedlicher Werte für dasselbe Datenelement ist, dann kann meiner Meinung nach dieser Fehler in der Abstraktion der Konsistenz berücksichtigt werden unbedeutend (außerdem würde, wenn Brewer den Begriff Atomizität verwenden würde, das AAP-Theorem auftauchen, dessen Namen äußerst unpraktisch auszusprechen wäre).

Das ist nicht sehr ernst, aber ehrlich geschrieben. Und tatsächlich sollte die Anforderung der atomaren Konsistenz nicht mit den Anforderungen der Transaktionskonsistenz im Sinne von ACID vermischt werden. Einschränkungen der Datenbankintegrität sind sozusagen logische Geschäftsanforderungen. Sie stammen aus der Anwendungsdomänenlogik. Das Erfordernis der atomaren Konsistenz ist von ganz anderer Art. Hierbei handelt es sich um eine Implementierungsanforderung, die in die Kategorie fällt, die in der Datenbankbranche traditionell als physische Konsistenz bezeichnet wird (z. B. müssen bei der Durchführung einer Indexänderungsoperation alle Blöcke des entsprechenden B+-Baums gültige Werte enthalten und durch gültige Referenzen verknüpft sein). ).

Und das schreiben die Vertreter der Datenbank-Community Daniel Abadi und Alexander Thomson ganz ernst in ihrer Notiz:

... die Anforderung an die Verfügbarkeit skalierbarer Transaktionssysteme wird immer kritischer und wird in der Regel durch Replikation und automatische Umleitung von Anfragen im Falle eines Ausfalls eines der Knoten erfüllt. Daher erwarten Anwendungsentwickler, dass die Konsistenzgarantien von ACID-Systemen (die ursprünglich aus der lokalen Unterstützung für benutzerdefinierte Invarianten bestanden) erweitert werden, um eine starke Konsistenz sicherzustellen (dass alle Replikate derselben Daten zu einem bestimmten Zeitpunkt identische Kopien sind, d. h. in diese Fallkonsistenz ist im Sinne von CAP/PACELC impliziert.

Mit anderen Worten: Die Brewer-Konsistenz hat nichts mit der ACID-Konsistenz zu tun, aber in Systemen, die auf die Bereitstellung hoher Verfügbarkeit durch Datenreplikation ausgerichtet sind, ist es wünschenswert, eine starke Replikatkonsistenz aufrechtzuerhalten. Dabei handelt es sich nicht um eine ACID-Eigenschaft, sondern um eine technische (physische) Funktion eines massiv parallelen DBMS, die die Anwendungsentwicklung erleichtert.

Laut Michael Stonebreaker liegt der Schlüssel zum Aufbau eines hochwertigen modernen DBMS in der richtigen Wahl technischer Kompromisse. Bei der Auswahl einer konkreten technischen Lösung muss man viele Faktoren berücksichtigen – die Anforderungen zukünftiger Nutzer, die Wahrscheinlichkeit verschiedener Fehlersituationen etc. und darf sich nicht dogmatisch von allgemeinen theoretischen Leitlinien (einschließlich des CAP-„Theorems“) leiten lassen.

Stonebreaker glaubt, dass im Bereich transaktionaler paralleler Datenbanksysteme der Verzicht auf die Brewer-Konsistenz zugunsten der Unterstützung von Hochverfügbarkeit und Netzwerkpartitionstoleranz ein schlechter Kompromiss ist, weil (a) Replikatkonsistenz ein sehr nützliches Merkmal des Systems ist; (b) transaktionale massiv-parallele DBMS benötigen keine Cluster mit einer sehr großen Anzahl von Knoten, sodass Netzwerkaufteilungssituationen unwahrscheinlich sind; (c) Das System kann leicht nicht mehr verfügbar sein, nicht aufgrund einer Netzwerkpartition, sondern beispielsweise aufgrund regelmäßig auftretender Softwarefehler.

Die hohe Aktivität von Vertretern des NoSQL-Lagers (sprich NoACID), die sich oft auf Brewers „Theorem“ beziehen, hängt also nicht mit der theoretischen Unmöglichkeit zusammen, massiv parallele Transaktions-DBMS aufzubauen, die ACID-Transaktionen unterstützen, sondern mit der Tatsache, dass vereinfachte Systeme die nicht nur ACID-Transaktionen, sondern auch Replikatkonsistenz unterstützen, lassen sich einfacher und schneller erstellen. Aufgrund ihrer einfachen Organisation sind sie in der Lage, Daten sehr schnell zu verarbeiten, und für manche Anwendungen ist dies wichtiger als alle Annehmlichkeiten der Datenbanktechnologie.

Mal sehen, wie die Datenbank-Community auf diese Herausforderung reagiert.