Das Datenbanktheorem

Gut, machen wir mal ein bisschen theoretische Informatik.

Ein Leser schreibt zum Twittersausen:

Twitter/x-Probleme: eventual consistency ?

Hallo Hadmut,
viele verteilte Datenbanken (meist No-SQL) werden heute nicht mehr strikt “consistent” gehalten.
Dauert zu lange….
Hier hat das Konzept der “eventual consistency” einzug gehalten.
https://en.wikipedia.org/wiki/Eventual_consistency

Könnte deine Erfahrungen erklären…

Ich wollte eigentlich nicht so tief gehen, aber wenn wir schon dabei sind, tun wir mal was für die digitale Allgemeinbildung und lernen etwas, was selbst viele Informatikprofessoren nicht wissen: Das Datenbanktheorem. Oder, besser gesagt, das CAP theorem. Der deutsche Begriff ist kaum gebräuchlich und ungenau.

In database theory, the CAP theorem, also named Brewer’s theorem after computer scientist Eric Brewer, states that any distributed data store can provide only two of the following three guarantees:

Consistency

Every read receives the most recent write or an error. Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.

Availability

Every request received by a non-failing node in the system must result in a response. This is the definition of availability in CAP theorem as defined by Gilbert and Lynch. Note that availability as defined in CAP theorem is different from high availability in software architecture.

Partition tolerance

The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

(Deshalb CAP-Theorem, die drei Anfangsbuchstaben.)

Eine Datenbank kann von drei wichtigen Eigenschaften immer nur höchstens zwei voll erfüllen: Konsistenz, Verfügbarkeit und Ausfalltoleranz.

Davon merkt man in vielen Fällen gar nichts (weshalb das auch nicht sehr bekannt ist), weil viele Datenbanken auf einem einzelnen Server laufen, und das Theorem erst bei verteilten Datenbanken zur Wirkung kommt – klar, ein einzelner Server kann ja nicht inkonsistent in dem Sinne zu sich selbst sein, dass er unterschiedliche Daten speichert und nicht alle auf dem neuesten Stand sind (nicht gemeint die Inkonsistenz zwischen Tables, die geht natürlich, hat aber mit dem Theorem nichts zu tun, es geht um serverübergreifende Inkonsistenz.) Und die Ausfalltoleranz ist bei einem einzelnen Rechner auch nicht relevant, denn er kann ja nur an oder aus sein, aber nicht teilweise. Das kommt alles erst zum Tragen, wenn man große, verteilte Datenbanken verwendet, die auf vielen Servern laufen – wie etwa Twitter, Google und solche Anwendungen.

Es ist übrigens ein wichtiger Punkt bei der Auswahl von Datenbanken für ein Projekt, denn es muss vorher geklärt werden, welche der Eigenschaften erforderlich sind und auf welche man verzichten kann. Eine Pflichtenheftsache. Das wird oft unterlassen und dann wundert man sich, wenn es nicht gut läuft. Ich müsste nochmal nachlesen, aber wenn ich mich aus dem Stand recht erinnere, unterscheiden sich zwei beliebte, konkurrierende NoSQL-Datenbanksysteme, CouchDB und MongoDB, darin, welche zwei der drei Eigenschaften sie abbilden. Ich glaube, CouchDB ist hochverfügbar und partitionstolerant, aber nicht konsistent, während MongoDB hochverfügbar und konsistent, aber nicht partitionstolerant ist, bin mir jetzt aber nicht ganz sicher.

In der Praxis ist das dann so, dass man sich um die dritte Eigenschaft dann irgendwie kümmern muss, um die zumindest möglichst gut anzunähern, weil sich das „haben will“ natürlich gerne auf alle drei Eigenschaften bezieht. Man bastelt sich dann halt irgendwas, um das Fehlen der dritten Eigenschaft möglichst moderat zu halten.

Und es ist wohl so, dass die bei Twitter/X die Schwerpunkte auf Verfügbarkeit und Partitionstoleranz (Ausfalltoleranz) gelegt und die Konsistenz (ein bisschen zu stark) geopfert haben.

Nun wisst Ihr was aus der Informatik, was viele Informatikprofessoren nicht wissen.