In früheren Artikeln haben wir erklärt, was Konsistenz ist, den Unterschied zwischen "starker" und "eventueller" Konsistenz und warum diese Unterscheidung für moderne Anwendungsentwickler wichtiger denn je ist. Wir haben auch den Begriff 'Konsistenzsteuer': die zusätzliche Zeit und Mühe, die ein Entwicklungsteam investieren muss, wenn es sich für ein System mit nur eventueller Konsistenz oder begrenzten Konsistenzgarantien entscheidet.
Mehrere moderne Datenbanken verwenden hochmoderne Algorithmen, um den Kompromiss zwischen Konsistenz und Leistung zu eliminieren. Natürlich möchten wir nicht, dass Sie uns das einfach glauben, ohne eine angemessene Erklärung. Daher tauchen wir in diesem letzten Artikel in die technischen Details hinter einigen dieser Datenbanken ein. Typischerweise sind Forschungspapiere die einzige Informationsquelle für diese technischen Details, daher ist der Sinn dieses Artikels, diese Systeme in einfacheren Worten zu erklären. Da diese Systeme in Wirklichkeit weitaus komplexer sind, stellen wir die Links im Text zur Verfügung, falls Sie mehr erfahren möchten und gerne Forschungspapiere lesen.
Einführung
In den Teilen 1 und 2 dieser Artikelreihe haben wir erklärt, wie verteilte Datenbanken verschiedene Replikate verwenden, um die Last zu verteilen und/oder Benutzer in verschiedenen Regionen zu bedienen. Um es hier für neue Leser zusammenzufassen: Ein Replikat ist lediglich eine Duplizierung Ihrer Daten. Und diese Duplizierung kann entweder am selben Ort zur Redundanz oder an einem anderen Ort leben, um Benutzern in diesen Orten geringere Latenzen zu bieten. Mehrere Replikate zu haben, die sowohl Lese- als auch Schreibvorgänge verarbeiten können, ist ein großer Vorteil, da die Datenbank skalierbar wird und allen Ihren Benutzern geringere Latenzen bieten kann, egal wo sie sich befinden. Sie möchten jedoch nicht, dass jedes der Replikate seine eigene Interpretation der Daten hat. Anstatt kleiner Datenunterschiede zwischen jedem Replikat, wünschen Sie sich eine einzige Interpretation der Daten, die oft als "Single Source of Truth" bezeichnet wird. Um dies zu erreichen, benötigen Sie eine Art Übereinkunft über Datenänderungen. Wir brauchen einen Konsens.
Warten auf Konsens
Jede verteilte Datenbank, die konsistent sein soll, hat mehrere Replikate, die sich über die Ergebnisse von Transaktionen einig sein müssen. Wenn widersprüchliche Datenaktualisierungen auftreten, müssen sich diese Replikate einigen, welche Aktualisierung durchgeführt wird und welche nicht. Dies nennt man "Konsens".
Kehren wir zu unserem Spiel zurück, um zu veranschaulichen, warum wir Konsens brauchen. Stellen Sie sich vor, der Spieler unseres Spiels hat nur noch 3 Goldstücke übrig, versucht aber gleichzeitig, zwei verschiedene Gegenstände in zwei verschiedenen Geschäften für ein Gesamtbudget zu kaufen, das größer ist als die verbleibenden 3 Goldstücke. Dies beinhaltet zwei Transaktionen, eine für jeden Gegenstand/Geschäft, die wir als t1 und t2 bezeichnen. Und nehmen wir an, die Besitzer der Geschäfte befinden sich auf verschiedenen Kontinenten, sodass die Transaktionen auf zwei verschiedenen Replikaten stattfinden. Wenn beide Transaktionen akzeptiert werden, könnte der Benutzer mehr kaufen, als er sich leisten kann. Wie verhindern wir, dass der Benutzer zu viel ausgibt?
Wir wissen, dass diese Replikate kommunizieren müssen, um sich über das Endergebnis der beiden Transaktionen zu einigen. Was wir nicht wissen, ist, wie viel Kommunikation sie benötigen. Wie viele Nachrichten müssen zwischen Replikat 1 und Replikat 2 hin und her gesendet werden, um sich darauf zu einigen, welche Transaktion Vorrang hat und welche storniert wird?
Da Replikate in einer verteilten Datenbank dazu dienen, Benutzer aus verschiedenen Regionen der Welt mit geringer Latenz zu bedienen, sind sie naturgemäß weit voneinander entfernt. Indem Duplikate der Daten näher an den Endbenutzern platziert werden, können diese Benutzer mit geringeren Latenzen lesen. Wenn jedoch Schreibvorgänge stattfinden, müssen die Replikate Nachrichten aneinander senden, um alle duplizierten Daten einheitlich zu aktualisieren – und diese Nachrichten können mehrere 10 Millisekunden dauern, da sie durch die Lichtgeschwindigkeit begrenzt sind, während sie um die Welt reisen. Es ist klar, dass wir die Anzahl der Cross-Datacenter-Nachrichten so gering wie möglich halten müssen, damit der Endbenutzer nicht darauf warten muss, dass diese Replikate auf der ganzen Welt zu einem Konsens gelangen.
Lange Zeit wurde dies für unmöglich oder unpraktisch gehalten. Aber heute existieren mehrere Technologien, um die Anzahl der Round-Trips niedrig zu halten und die Latenz innerhalb normaler Grenzen zu halten.
Die Entfernung zwischen New York und Paris beträgt 5.839 km. Damit Licht von New York nach Paris und zurück reisen kann, dauert es 40 Millisekunden.
— Theoretische vs. reale Geschwindigkeit
Die wichtigste verbleibende Frage ist: "Wie viele Round-Trips benötigen wir, um Transaktionen auszuführen?" Die Antwort auf diese Frage hängt stark von den verwendeten Algorithmen ab.
Wie erreicht man eine Einigung?
Es scheint, dass man mindestens vier Hops (oder zwei Kommunikationsrunden) benötigt, um einen Konsens über etwas zu erzielen: eine Runde, um jedes Replikat wissen zu lassen, dass man etwas tun wird, dann eine zweite Runde, um die Aktion tatsächlich auszuführen, sobald sich alle einig sind, dass diese Aktion ausgeführt werden kann. Dies ist etwas, das als verteilter Two-Phase Commit bezeichnet wird und von fast jeder verteilten Datenbank verwendet wird. Betrachten wir eine Analogie. Stellen Sie sich vor, Sie müssen sich mit einer Gruppe von Leuten auf ein gutes Datum für eine Party einigen. Es könnte so ablaufen:
Zuerst fragt Polly alle, ob sie an einer Party am Montag teilnehmen können; sie weiß jetzt, dass tatsächlich alle zur Party kommen können. Als Nächstes muss sie alle wissen lassen, dass die Party tatsächlich am Montag stattfindet, und die Leute bestätigen, dass sie dabei sein werden.
Dies ist dem Zweiphasen-Commit sehr ähnlich. Natürlich feiern Datenbanken keine Partys, daher haben die Phasen unterschiedliche Funktionen. Im Fall eines verteilten Systems werden die Phasen wie folgt genannt:
- Vorbereiten oder Commit anfordern: Sicherstellen, dass jeder von der Transaktion weiß. In dieser Phase speichern Replikate in einer verteilten Datenbank die Abfrage in einer Art To-do-Liste (ein Transaktionsprotokoll) auf der Festplatte, um sicherzustellen, dass sie immer noch wissen, was zu tun ist, wenn der Server ausfällt.
- Commit: Tatsächlich die Ergebnisse berechnen und speichern
Natürlich ist es, wie immer, nie so einfach. Es gibt viele Varianten solcher Algorithmen. Zum Beispiel gibt es Verbesserungen des Two-Phase Commits namens Paxos und Raft und sogar viele Varianten davon (Multi-Paxos/Fast Paxos/...). Diese Alternativen zielen darauf ab, Verfügbarkeits- oder Leistungsprobleme zu verbessern. Um die Verfügbarkeitsprobleme zu verstehen, stellen Sie sich einfach vor, Polly wird krank oder Ambers Handy geht kaputt. Im ersten Fall könnte sie ihre Arbeit als Partykoordinatorin nicht fortsetzen, und im letzteren Fall wäre es für Polly vorübergehend unmöglich zu wissen, ob Amber dem Partydatum zustimmt. Raft und Paxos verbessern dies, indem sie nur die Mehrheit zur Antwort auffordern und/oder automatisch einen neuen Koordinator auswählen, wenn der Leiter oder Koordinator ausfällt. Eine gute Animation, die zeigt, wie Raft funktioniert, finden Sie hier.
Worüber einigen?
Können wir schlussfolgern, dass jede verteilte Datenbank dann 2 Round-Trips zum Schreiben/Lesen von Daten benötigt? Nein, die Realität ist komplexer als das. Einerseits gibt es viele mögliche Optimierungen, und andererseits gibt es möglicherweise mehrere Dinge, über die wir uns einigen müssen.
- Vereinbarung über den Zeitpunkt einer Transaktion
- Vereinbarung, ob Lesezugriffe ausgeführt werden können
Das einfachste Beispiel mit mehreren Two-Phase-Commit-Runden sind wahrscheinlich die leichtgewichtigen Transaktionen von Cassandra. Sie erfordern zuerst Konsensvereinbarungen über Lesevorgänge und dann Konsens über Schreibvorgänge. Wenn jede Nachricht 40 ms zur Übertragung benötigt, bedeutet dies, dass die gesamte Transaktion 320 ms oder länger dauert – abhängig von den erforderlichen "Sperren", wie wir später erläutern werden.
Das ist recht einfach zu verstehen, aber es gibt einige Probleme mit der Implementierung, da Cassandra nie als stark konsistent konzipiert wurde. Bedeutet das, dass stark konsistente Datenbanken noch langsamer sind? Keineswegs! Moderne verteilte Datenbanken verwenden eine Mischung aus interessanten Funktionen, um eine bessere Leistung zu erzielen.
Warten auf Sperren
Nicht nur müssen wir auf Nachrichten warten, um zu einer Einigung zu gelangen, sondern fast jede verteilte Datenbank verwendet auch "Sperren". Sperren garantieren, dass die von einer Transaktion zu ändernden Daten nicht gleichzeitig von einer anderen Transaktion geändert werden. Wenn Daten gesperrt sind, können sie von anderen Transaktionen nicht geändert werden, was bedeutet, dass diese Transaktionen warten müssen. Die Dauer einer solchen Sperre hat daher einen großen Einfluss auf die Leistung. Auch hier hängt dieser Leistungseffekt vom Algorithmus und den vom Datenbankhersteller implementierten Optimierungen ab. Einige Datenbanken halten Sperren länger als andere, und einige Datenbanken verwenden überhaupt keine Sperren.
Nachdem wir nun die Grundlagen kennen, tauchen wir in die Algorithmen ein.
Moderne Algorithmen für Konsens
Wir wissen jetzt, dass Konsens und Sperren die Hauptengpässe sind, die wir optimieren müssen. Kehren wir also zur Hauptfrage dieses Artikels zurück: "Wie senkt neue Technologie diese Latenzen auf akzeptable Werte?" Beginnen wir mit dem ersten dieser modernen Algorithmen, der interessante Ideen für den Rest der Datenbankwelt anregte.
2010 – Percolator
Percolator ist ein internes System, das auf BigTable (einer der ersten von Google entwickelten NoSQL-Datenbanken) basiert und von Google verwendet wurde, um inkrementelle Aktualisierungen der Seiten-Crawling-Geschwindigkeit seines Suchindexes zu beschleunigen. Das erste Paper über Percolator wurde 2010 veröffentlicht und inspirierte 2013 die erste davon abgeleitete verteilte Datenbank: FoundationDB. FoundationDB wurde dann von Apple übernommen, um schließlich 2019 eine stabile Version zu veröffentlichen, zusammen mit der Veröffentlichung eines FoundationDB Papers.
Obwohl Percolator es Google ermöglichte, das Crawling von Seiten erheblich zu beschleunigen, wurde es ursprünglich nicht als Allzweckdatenbank entwickelt. Es war vielmehr als schnelles und skalierbares inkrementelles Verarbeitungsmodul gedacht, um den Suchindex von Google zu unterstützen. Da der Suchindex skalierbar sein musste, mussten viele Berechnungen gleichzeitig auf vielen Maschinen erfolgen, was eine verteilte Datenbank erforderte. Wie wir in den vorherigen Artikeln gelernt haben, ist die Programmierung gegen verteilte Systeme, die Daten speichern, sehr komplex und erforderte traditionell, dass Entwickler eine "Konsistenzsteuer" zahlen, um unvorhersehbares Datenbankverhalten zu umgehen. Um eine so hohe Konsistenzsteuer zu vermeiden, hat Google ein starkes Konsistenzmodell übernommen, als sie Percolator entwickelten.
Das Konsistenzmodell von Percolator konnte ohne zwei Schlüsselkomponenten nicht existieren: Versionierung und der Timestamp Oracle
Zutat 1: Versionierung
Wie wir in früheren Artikeln erwähnt haben, erfordert starke Konsistenz, dass wir uns auf eine globale Reihenfolge für unsere Transaktionen einigen. Versionierung ist eines der Elemente, die für viele dieser Algorithmen entscheidend sein werden, da sie zur Wiederherstellung nach Fehlern, zur Replikation von Daten und zur Unterstützung eines Konsistenzmodells namens "Snapshot Isolation" verwendet werden kann.
Die Versionierung hilft bei der Wiederherstellung nach Fehlern, wenn ein Knoten ausfällt oder die Verbindung trennt. Wenn der Knoten wieder online geht, kann er dank der Versionen seinen Zustand leicht wiederherstellen, indem er mit dem letzten Snapshot beginnt, den er speichern konnte, und dann die Transaktionen basierend auf den Versionen in einem anderen Knoten wiedergibt. Alles, was er tun muss, ist, einen anderen Knoten zu fragen: "Hey, was hat sich geändert, seit ich weg war?" Ohne Versionierung müsste er alle Daten kopieren, was das System stark belasten würde.
Die Wiederherstellung nach Fehlern ist großartig, aber der größte Vorteil liegt darin, dass ein solches Versionierungssystem zur Implementierung eines starken Konsistenzmodells verwendet werden kann. Wenn das Versionierungssystem Versionen für jede Datenänderung speichert, können wir tatsächlich in der Zeit zurückgehen und Abfragen gegen eine frühere Version unserer Daten durchführen.
Einige kluge Köpfe haben herausgefunden, dass diese Fähigkeit zur Abfrage der Historie verwendet werden kann, um ein Konsistenzmodell namens "Snapshot Consistency" bereitzustellen. Die Idee der Snapshot Consistency besteht darin, zu Beginn der Abfrage eine Version der Daten auszuwählen, mit dieser Datenversion während des Rests der Abfrage zu arbeiten und am Ende der Abfrage eine neue Version zu schreiben.
Hier gibt es einen möglichen Fallstrick: Während der Ausführung einer solchen Abfrage könnte eine andere Abfrage Daten schreiben, die mit der ersten Abfrage in Konflikt stehen. Wenn beispielsweise zwei Schreibabfragen mit demselben Snapshot eines Bankkontos mit 1000 US-Dollar beginnen, könnten sie beide das Geld ausgeben, da sie die Schreibvorgänge der anderen Abfrage nicht sehen. Um dies zu verhindern, findet eine zusätzliche Transaktion statt, um zu prüfen, ob sich die Werte des Snapshots geändert haben, bevor eine der Abfragen ein Ergebnis schreibt. Wenn etwas Konfliktträchtiges den Wert des Snapshots geändert hat, wird die Transaktion zurückgerollt und muss neu gestartet werden.
Es gibt jedoch immer noch ein Problem, das Percolator lösen muss. Uhren auf verschiedenen Maschinen können leicht um einige 100 Millisekunden auseinanderdriften. Wenn Daten für eine Abfrage auf mehrere Maschinen aufgeteilt sind, wie in unserem ursprünglichen Beispiel, können Sie nicht einfach beide Maschinen bitten, Ihnen Daten zu einem bestimmten Zeitstempel zu geben, da sie eine leicht unterschiedliche Vorstellung von der aktuellen Zeit haben. Es sind nur Millisekunden, aber wenn viele Transaktionen verarbeitet werden müssen, reichen ein paar Millisekunden aus, um von korrekten zu fehlerhaften Daten zu gelangen.
Zeitsynchronisation bringt uns zur zweiten Percolator-Zutat.
Zutat 2: Der Timestamp Oracle
Percolators Lösung für das Problem der Zeitsynchronisation ist etwas, das Timestamp Oracle genannt wird. Anstatt jedem Knoten seine eigene Zeit diktieren zu lassen (was nicht genau genug war), verwendet Percolator ein zentrales System, das eine API bereitstellt, die Ihnen einen Zeitstempel liefert. Der Knoten, auf dem dieses System läuft, ist das Timestamp Oracle. Wenn wir mehrere Versionen unserer Daten behalten, benötigen wir mindestens zwei Zeitstempel für jede Abfrage. Erstens benötigen wir einen Zeitstempel, um einen Snapshot abzufragen, den wir zum Lesen der Daten verwenden werden. Dann, am Ende der Transaktion, wenn wir bereit sind zu schreiben, benötigen wir einen zweiten Zeitstempel, um die neue Datenversion zu kennzeichnen. Infolgedessen hat Percolator den Nachteil, dass es mindestens zwei Aufrufe an das Timestamp Oracle benötigt, was zu noch mehr Latenz führt, wenn sich das Oracle in einer anderen Region befindet als die Knoten, von denen die Aufrufe stammen. Als Google sich ihre Distributed Database Spanner ausdachten, lösten sie dieses Problem.
2012 – Spanner
Spanner war die erste global verteilte Datenbank, die starke Konsistenz bot, was im Wesentlichen bedeutet, dass Sie schnelle Lesezugriffe erhalten, ohne sich mehr um potenzielle Datenbankfehler sorgen zu müssen. Entwickler müssen keine zusätzliche Arbeit mehr investieren, um potenzielle Fehler aufgrund von eventueller Konsistenz zu umgehen. Das Paper wurde 2012 veröffentlicht und 2017 als Spanner Cloud der Öffentlichkeit zugänglich gemacht.
Zutat 1: Versionierung
Google baute Spanner nach seinen Erfahrungen mit Percolator. Da sich das Versionierungssystem von Percolator bewährte, behielten sie dies im Design von Spanner bei. Dieses Versionierungssystem ermöglichte sehr schnelle Lesezugriffe (Snapshot-Lesen), wenn man bereit war, auf Konsistenz zu verzichten. In diesem Fall konnten Abfragen ausgeführt und Spanner ein maximales Alter der Ergebnisse angegeben werden. Zum Beispiel: "Bitte geben Sie mir so schnell wie möglich meinen aktuellen Lagerbestand zurück, aber die Daten dürfen nur 15 Sekunden alt sein". Anstatt die Konsistenz aufzugeben, konnten Sie nun für jede Abfrage wählen, welches Konsistenzniveau für Ihren Anwendungsfall geeignet ist.
Zutat 2: TrueTime
Um den zusätzlichen Overhead für die Zeitsynchronisation zwischen Maschinen zu eliminieren, verzichtete Spanner auf das Timestamp Oracle zugunsten eines neuen Konzepts namens TrueTime. Anstatt eines zentralen Systems, das eine einheitliche Zeitansicht bereitstellt, versucht TrueTime, die Uhrenabweichung zwischen den Maschinen selbst zu reduzieren. Ingenieure bei Google gelang es, die lokale Uhrenabweichung durch die Implementierung eines Zeitsynchronisationsprotokolls auf Basis von GPS und Atomuhren zu begrenzen. Dieser Synchronisationsalgorithmus ermöglichte es ihnen, die Uhrenabweichung auf eine Grenze von 7 ms zu beschränken, erforderte jedoch spezifische Hardware, die aus einer Kombination von GPS- und Atomuhrtechnologie bestand.
Natürlich gibt es immer noch eine potenzielle Uhrenabweichung von 7 ms, was bedeutet, dass zwei Server einen Zeitstempel immer noch als zwei verschiedene Snapshots interpretieren könnten. Dies wird durch die dritte Zutat für Spanner gelöst: Commit-Wait.
Zutat 3: Commit-Wait
Tatsächlich gibt die TrueTime-API nicht einen Zeitstempel zurück, sondern ein Intervall, in dem sie sicher ist, dass der aktuelle Zeitstempel liegen sollte. Sobald sie bereit ist, zu committen, wartet sie einfach ein paar Millisekunden, um die potenzielle Abweichung zu berücksichtigen, was als "Commit-Wait" bezeichnet wird. Dies stellt sicher, dass der Zeitstempel, der der Schreiboperation zugewiesen wird, ein Zeitstempel ist, der auf allen Knoten vergangen ist. Es ist auch der Grund, warum Spanner auf handelsüblicher Hardware nicht die gleichen Garantien liefern kann, da die Wartezeit mehrere 100 Millisekunden betragen würde.
2012 – Calvin
Das erste Paper über den Calvin-Algorithmus wurde 2012 von Forschern der Yale University veröffentlicht. Ähnlich wie die vorherigen Ansätze besteht Calvin aus mehreren Komponenten. Obwohl Versionierung ebenfalls Teil davon ist, ist der Rest des Ansatzes radikal anders und erfordert einige zusätzliche Komponenten: deterministische Berechnungen und die Trennung von Reihenfolge und Sperrung. Dies sind Komponenten, die in Datenbanken mit traditioneller Architektur typischerweise nicht zu finden sind. Durch die Änderung der Architektur und die Akzeptanz, dass Abfragen deterministisch sein müssen, kann Calvin die Worst-Case-Anzahl von Cross-Datacenter-Nachrichten auf zwei reduzieren. Dies senkt die Worst-Case-Latenz globaler Transaktionen erheblich und bringt sie unter 200 ms oder theoretisch sogar unter 100 ms. Um dies glauben zu können, möchten Sie wahrscheinlich zuerst wissen, wie es funktioniert, also werfen wir einen Blick auf den Algorithmus.
Zutat 1: Versionierung
Ähnlich wie Percolator und Spanner setzt Calvin auf versionierte Daten. Diese Snapshots in Calvin werden hauptsächlich zur Gewährleistung der Fehlertoleranz verwendet. Jeder Knoten speichert unterschiedliche Snapshots, die als Checkpoints betrachtet werden können. Ein getrennter Knoten, der wieder online geht, muss nur den Zeitstempel des letzten Checkpoints erfassen, den er gesehen hat, und dann einen anderen Knoten bitten, ihn über alle Transaktionen zu informieren, die nach diesem Checkpoint stattgefunden haben.
Zutat 2: Deterministische Berechnungen
Viele Frontend-Entwickler haben vielleicht vom Elm-Frontend-Framework gehört, das einen Workflow ähnlich wie React Redux implementiert. Elm hat eine steilere Lernkurve als ähnliche JavaScript-basierte Frameworks, da Sie eine neue Sprache lernen müssen. Da die Sprache jedoch funktional ist (keine Nebeneffekte), ermöglicht Elm einige beeindruckende Optimierungen. Der Schlüssel ist, dass Funktionen in Elm destruktive Manipulationen aufgeben, um deterministisch zu sein. Sie können dieselbe Funktion mit demselben Eingabewert zweimal ausführen und erhalten immer dasselbe Ergebnis. Da sie deterministisch sind, können Elm-Abfragen nun effizienter entscheiden, wie Ansichten aktualisiert werden.
Ähnlich wie Elm hat Calvin etwas aufgegeben, um die Berechnungen zu beschleunigen. Im Fall von Calvin können wir im Grunde sagen, dass das Ergebnis einer Transaktion dasselbe ist, egal ob es auf Maschine A oder Maschine B ausgeführt wird. Das mag offensichtlich erscheinen, aber normalerweise garantieren Datenbanken dies nicht. Denken Sie daran, dass SQL Ihnen erlaubt, die aktuelle Zeit zu verwenden oder sogenannte interaktive Transaktionen zu nutzen, bei denen Benutzereingaben mitten in einer Transaktion eingefügt werden können, was beides die von Calvin bereitgestellten Garantien verletzen könnte.
Um deterministische Berechnungen zu erreichen, muss Calvin (1) Berechnungen wie die aktuelle Uhrzeit herausnehmen und im Voraus berechnen und (2) keine interaktiven Transaktionen zulassen. Interaktive Transaktionen sind Transaktionen, bei denen ein Benutzer eine Transaktion startet, einige Daten liest, mitten in der Transaktion zusätzliche Benutzereingaben bereitstellt und dann einige zusätzliche Berechnungen und möglicherweise einige Schreibvorgänge durchführt. Da der Benutzer nicht vorhersehbar ist, ist eine solche Transaktion nicht deterministisch. Im Wesentlichen tauscht Calvin eine geringfügige Bequemlichkeit (interaktive Transaktionen) gegen hohe Leistung.
Zutat 3: Trennung des Problems der Reihenfolge.
Datenbanken verbringen viel Zeit mit der Aushandlung von Sperren, um den Eindruck zu erwecken, dass das System in einer bestimmten Reihenfolge ausgeführt wird. Wenn eine Reihenfolge alles ist, was Sie brauchen, können wir vielleicht das Problem der Sperrung vom Problem der Reihenfolge trennen. Das bedeutet jedoch, dass Ihre Transaktionen rein sein müssen.
— Kyle Kingsbury
Die Trennung der Verantwortung für die Reihenfolge von Transaktionen von der eigentlichen Ausführung wurde in der Datenbankwelt schon oft in Betracht gezogen, aber ohne großen Erfolg. Wenn Ihre Transaktionen jedoch deterministisch sind, wird die Trennung der Reihenfolge von den Berechnungen tatsächlich machbar. Tatsächlich ist die Kombination aus deterministischen Berechnungen und der Trennung der Reihenfolge vom Rest des Algorithmus äußerst wirkungsvoll, da sie dazu beiträgt, die Sperrdauer zu verkürzen und die langsamere Kommunikation zwischen entfernten Knoten (Cross-Datacenter-Kommunikation) erheblich zu reduzieren.
Kürzere Sperrdauer
Immer wenn Daten gesperrt sind, bedeutet dies, dass andere Abfragen, die diese Daten verwenden, warten müssen. Daher führt eine kürzere Sperrung zu einer besseren Leistung. Unten ist eine Abbildung, die einen Überblick über das Sperrverfahren in Calvin im Vergleich zu einer traditionellen verteilten Datenbank zeigt. Die meisten Datenbanken würden eine Sperre auf Daten halten, bis ein Konsens darüber besteht, was geschrieben werden soll, während Calvin die Sperre nur so lange halten würde, bis sich alle Knoten über die Reihenfolge einig sind. Da die Berechnungen deterministisch sind und sie sich alle auf die Reihenfolge geeinigt haben, berechnet jeder Knoten separat und kommt zum selben Endergebnis.
Weniger Kommunikation zwischen entfernten Knoten
Neben den Vorteilen bei der Sperrdauer erfordert die Trennung der Reihenfolge vom Rest des Algorithmus auch weniger Kommunikation. Wie bereits am Beispiel von Cassandra erläutert, erfordert eine verteilte Datenbank typischerweise in vielen Phasen ihres Algorithmus eine Cross-Datacenter-Kommunikation. Im Fall von Calvin ist der einzige Moment, in dem wir uns über etwas einigen müssen, der Zeitpunkt, an dem wir die Reihenfolge bestimmen. Mit dem Raft-Protokoll könnte dies in zwei Hops erfolgen, was Latenzen von unter 100 ms für Lese-Schreib-Abfragen ermöglicht.
Zusammen mit der reduzierten Sperrzeit führt dies auch zu einem hervorragenden Durchsatz. Das ursprüngliche Calvin Paper hat auch Experimente durchgeführt, die zeigen, dass dieser Ansatz verteilte Datenbankdesigns traditioneller Bauart unter Workloads mit hoher Konkurrenz deutlich übertrifft. Ihre Ergebnisse von einer halben Million Transaktionen pro Sekunde auf einem Cluster von Standardmaschinen sind wettbewerbsfähig mit den aktuellen Weltrekordergebnissen, die auf viel höherwertiger Hardware erzielt wurden.
Läuft auf jeder Hardware
Darüber hinaus hat Calvin einen weiteren Vorteil: Es benötigt keine spezielle Hardware mehr, um solche Ergebnisse zu erzielen. Da Calvin auf Standard-Hardware laufen kann, kann es auf jedem Cloud-Provider laufen.
2014 – Der FaunaDB-Ansatz des Konsens
Zutat 1: Versionierung
FaunaDB verfügt über ein eigenes verteiltes Transaktionsprotokoll mit einigen Ähnlichkeiten zu Calvin. Wie die früheren Ansätze sind auch die Daten von FaunaDB versioniert. Da Versionierung nicht nur für das Konsistenzmodell nützlich ist, sondern auch geschäftlichen Wert haben kann, hat FaunaDB diesen Mechanismus zu einem erstklassigen Bürger aufgewertet, der von Endbenutzern verwendet werden kann. Diese Funktion ermöglicht im Wesentlichen Zeitreiseabfragen. Endbenutzer können eine Abfrage auf historischen Daten ausführen, um Fragen zu beantworten wie: „Wie wäre das Ergebnis dieser Abfrage vor 20 Tagen gewesen?“. Dies ist nützlich, um versehentlich überschriebene Daten wiederherzustellen, Datenänderungen zu überprüfen oder einfach Zeitreisen in die Funktionen Ihrer Anwendung zu integrieren.
Zutat 2 und 3: Deterministische Berechnungen und Trennung
Wie Calvin verfügt auch FaunaDB über deterministische Berechnungen und trennt das Problem der Reihenfolge vom Rest des Algorithmus. Obwohl es Ähnlichkeiten gibt, findet die Berechnung von Transaktionen in FaunaDB in einer anderen Phase als bei Calvin statt. Während Calvin die deterministische Natur nutzt, um dieselbe Transaktion mehrmals auszuführen, sobald die Reihenfolge festgelegt ist, berechnet FaunaDB nur einmal vor dem Konsens über die Reihenfolge der Transaktionen. Was uns zur vierten Zutat bringt.
Zutat 4: Optimistische Berechnung
FaunaDB fügt eine vierte Zutat hinzu, die wir bereits gesehen haben, als wir über Snapshot Isolation sprachen: **Optimistische Berechnungen** anstelle von Sperren.
FaunaDB sperrt nicht, sondern berechnet optimistisch das Ergebnis der Transaktion **einmal** auf dem Knoten, auf dem die Transaktion empfangen wurde, und fügt dann das Ergebnis und die ursprünglichen Eingabewerte zum Protokoll hinzu. Während Calvin die auszuführende Abfrage im Transaktionsprotokoll gespeichert hätte, speichert FaunaDB sowohl das Ergebnis der Berechnung als auch die ursprünglichen Eingabewerte im Protokoll. Sobald ein Konsens über die Reihenfolge besteht, in der die Ergebnisse angewendet werden müssen, überprüft FaunaDB, ob sich die Eingabedaten für diese Berechnung geändert haben oder nicht (dank Versionierung). Wenn sich die Eingabewerte geändert haben, wird die Transaktion abgebrochen und neu gestartet. Wenn sie gleich geblieben sind, werden die Ergebnisse ohne zusätzliche Berechnung auf allen Knoten angewendet.
Der Algorithmus von FaunaDB hat ähnliche Vorteile wie Calvin, reduziert aber die Menge der erforderlichen Berechnungen im Cluster.
Fazit
In dieser Reihe haben wir erklärt, wie starke Konsistenz Ihnen helfen kann, fehlerfreie Anwendungen effizienter zu erstellen. In diesem letzten Artikel haben wir weiter erklärt, wie revolutionäre Ideen eine neue Generation verteilter Datenbanken antreiben können, die sowohl konsistent als auch performant sind. Die Quintessenz der vorherigen Artikel war: „Konsistenz ist wichtig“. In diesem abschließenden Artikel ist die Quintessenz in Folgendem zusammengefasst:
In naher Zukunft, wenn Sie einen Satz wie lesen:
„Viele NoSQL-Datenbanken bieten keine atomaren Schreibvorgänge für mehrere Dokumente und bieten dafür eine bessere Leistung. Und während Konsistenz ein weiteres großartiges Merkmal von SQL-Datenbanken ist, behindert sie die Skalierbarkeit einer Datenbank über mehrere Knoten hinweg, sodass viele NoSQL-Datenbanken auf Konsistenz verzichten.“ – Die größten Herausforderungen beim Umzug zu NoSQL
Erkennen Sie, dass moderne Algorithmen es Datenbanken ermöglichen, Konsistenz ohne Zentralisierung zu liefern. In diesem Artikel haben wir einige Beispiele für Algorithmen und Datenbanken gesehen, die dies tun. Datenbanken, die auf diesen Algorithmen aufbauen, sind eine nächste Generation von Datenbanken, die nicht mehr durch einfache Kategorien wie NoSQL, SQL oder sogar NewSQL beschrieben werden können.
Mit verteilten Cloud-Datenbanken, die auf Percolator, Spanner, Calvin und dem Transaktionsprotokoll von FaunaDB basieren, können Sie hochperformante verteilte Datenbanken erhalten, die stärkere Konsistenzmodelle bieten. Das bedeutet, dass Sie datenintensive Anwendungen erstellen können, die geringe Latenz bieten, ohne sich Gedanken über Datenfehler, Leistung oder Servicebereitstellung machen zu müssen. In solchen Systemen ist Konsistenz transparent, und Sie müssen als Entwickler nicht darüber nachdenken. Wählen Sie bei der nächsten Datenbankauswahl eine, die standardmäßig konsistent ist.