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“ eingeführt: die zusätzliche Zeit und Mühe, die ein Entwicklungsteam investieren muss, wenn es sich für ein System mit nur eventueller oder eingeschränkter Konsistenzgarantie 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 ohne eine angemessene Erklärung glauben. Daher tauchen wir in diesem abschließenden Artikel in die technischen Details hinter einigen dieser Datenbanken ein. Typischerweise sind Forschungspapiere die einzige Informationsquelle für diese technischen Details, daher ist der Zweck 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 hier für neue Leser zusammenzufassen: Ein Replikat ist lediglich eine Duplizierung Ihrer Daten. Und diese Duplizierung kann entweder am selben Standort zur Redundanz oder an einem anderen Standort leben, um Benutzern an diesen Standorten eine geringere Latenz zu bieten. Das Vorhandensein mehrerer Replikate, die sowohl Lese- als auch Schreibvorgänge verarbeiten können, hat einen großen Vorteil, da die Datenbank skalierbar ist und allen Benutzern, unabhängig von ihrem Standort, eine geringere Latenz bieten kann. Sie möchten jedoch nicht, dass jedes Replikat seine eigene Interpretation der Daten hat. Anstatt kleiner Datenunterschiede zwischen den einzelnen Replikaten möchten Sie eine einzige Interpretation der Daten, die oft als einzige Quelle der Wahrheit bezeichnet wird. Um dies zu erreichen, benötigen Sie eine gewisse Einigkeit über Datenänderungen. Wir brauchen einen Konsens.
Auf Konsens warten
Jede verteilte Datenbank, die auf Konsistenz abzielt, hat mehrere Replikate, die sich über das Ergebnis von Transaktionen einig sein müssen. Wenn widersprüchliche Datenaktualisierungen auftreten, müssen sich diese Replikate darauf einigen, welche Aktualisierung durchgeht und welche nicht. Dies nennt man „Konsens“.
Kehren wir zu unserem Spiel zurück, um zu veranschaulichen, warum wir einen Konsens brauchen. Stellen Sie sich vor, der Spieler unseres Spiels hat nur noch 3 Goldstücke übrig, versucht aber gleichzeitig, zwei verschiedene Gegenstände aus 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 sind auf der ganzen Welt voneinander getrennt, 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 Priorität hat und welche abgesagt 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. Durch die Platzierung von Datenduplikaten näher an den Endbenutzern können diese Benutzer mit geringerer Latenz 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 zehn Millisekunden dauern, da sie durch die Lichtgeschwindigkeit gebremst werden, wenn sie um die Welt reisen. Es ist klar, dass wir die Anzahl der Cross-Data-Center-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 kommen.
Lange Zeit glaubte man, dass dies unmöglich oder unpraktisch sei. Aber heute gibt es 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 wieder zurückreisen kann, würden 40 Millisekunden vergehen.
— 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 man Einigkeit erzielt?
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, und 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 als verteilter Two-Phase Commit bekannt, der von fast jeder verteilten Datenbank verwendet wird. Betrachten wir eine Analogie. Stellen Sie sich vor, Sie müssten sich mit einer Gruppe von Leuten auf ein gutes Datum für eine Party einigen. Es könnte so ablaufen:
Zuerst fragt Polly jeden, ob er am Montag zur Party kommen kann; sie weiß jetzt, dass tatsächlich jeder zur Party kommen kann. Als Nächstes muss sie alle darüber informieren, dass die Party tatsächlich am Montag stattfindet, und die Leute bestätigen, dass sie da sein werden.
Dies ähnelt sehr den beiden Phasen des Two-Phase Commit. Natürlich veranstalten Datenbanken keine Partys, sodass die Phasen unterschiedliche Funktionen haben. Im Falle eines verteilten Systems werden die Phasen als bezeichnet:
- Vorbereiten oder Commit anfordern: Sicherstellen, dass jeder über die Transaktion informiert ist. 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 Commit 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 Telefon stirbt. Im ersten Fall wäre sie nicht in der Lage, ihre Arbeit als Partykoordinatorin fortzusetzen, 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 benötigen und/oder automatisch einen neuen Koordinator auswählen, wenn der Leader oder Koordinator ausfällt. Eine gute Animation, die zeigt, wie Raft funktioniert, finden Sie hier.
Worüber Einigkeit erzielen?
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, auf die wir uns einigen müssen.
- Einigung über die Zeit einer Transaktion
- Einigung darüber, ob Lesevorgänge ausgeführt werden können
Das einfachste Beispiel mit mehreren Two-Phase Commit-Runden sind wahrscheinlich Cassandras leichtgewichtige Transaktionen. Sie erfordern zuerst Konsensvereinbarungen über Lesevorgänge und dann Konsens über Schreibvorgänge. Wenn jede Nachricht 40 ms für die Übertragung benötigt, bedeutet dies, dass die gesamte Transaktion 320 ms oder länger dauert – abhängig von den erforderlichen „Locks“, wie wir später erklären werden.
Das ist ziemlich einfach zu verstehen, aber es gibt einige Probleme mit der Implementierung, da Cassandra nie dafür konzipiert war, stark konsistent zu sein. Bedeutet das, dass stark konsistente Datenbanken noch langsamer sind? Keineswegs! Moderne verteilte Datenbanken nutzen eine Mischung aus interessanten Funktionen, um eine bessere Leistung zu erzielen.
Auf Sperren warten
Wir müssen nicht nur auf Nachrichten warten, um eine Einigung zu erzielen, sondern fast jede verteilte Datenbank verwendet auch „Locks“ (Sperren). Locks 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 die Auswirkung auf die Leistung vom Algorithmus und den Optimierungen ab, die von der Datenbank implementiert wurden. Einige Datenbanken halten Sperren länger als andere, und einige Datenbanken verwenden überhaupt keine Sperren.
Jetzt, da wir 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. Gehen wir also zurück zur Hauptfrage dieses Artikels: „Wie senkt neue Technologie diese Latenzen auf akzeptable Grenzen?“ Beginnen wir mit dem ersten dieser modernen Algorithmen, der interessante Ideen für den Rest der Datenbankwelt inspirierte.
2010 – Percolator
Percolator ist ein internes System, das auf BigTable (einer der frühen von Google entwickelten NoSQL-Datenbanken) basiert und den Google zur inkrementellen Aktualisierung der Seiten-Crawling-Geschwindigkeit seines Suchindex nutzte. Das erste Paper zu 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 Seiten-Crawling 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 durchgeführt werden, was eine verteilte Datenbank erforderte. Wie wir in den vorherigen Artikeln gelernt haben, kann die Programmierung gegen verteilte Systeme, die Daten speichern, sehr komplex sein 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 das Timestamp-Orakel.
Zutat 1: Versionierung
Wie wir in früheren Artikeln erwähnt haben, erfordert starke Konsistenz, dass wir uns auf eine globale Reihenfolge unserer Transaktionen einigen. Die Versionierung ist eines der Elemente, das für viele dieser Algorithmen entscheidend sein wird, da sie für die Wiederherstellung nach Fehlern, die Replikation von Daten und die 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 verliert. Wenn der Knoten wieder online ist, kann er dank der Versionen seinen Zustand leicht wiederherstellen, indem er mit dem letzten Schnappschuss beginnt, den er speichern konnte, und dann die Transaktionen basierend auf den Versionen auf einem anderen Knoten erneut abspielt. 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 stärkste Vorteil liegt in der Tatsache, 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 die Vergangenheit zurückgehen und Abfragen gegen eine frühere Version unserer Daten durchführen.
Einige brillante Köpfe haben herausgefunden, dass diese Fähigkeit zur Abfrage historischer Daten 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 Version der Daten während des Rests der Abfrage zu arbeiten und dann 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 Schnappschuss eines Bankkontos mit 1000 US-Dollar beginnen, könnten 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 Schnappschusses geändert haben, bevor eine der Abfragen ein Ergebnis schreibt. Wenn etwas Konfliktträchtiges passiert ist und der Wert des Schnappschusses geändert wurde, 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 hundert Millisekunden auseinanderdriften. Wenn Daten für eine Abfrage über mehrere Maschinen verteilt sind, wie in unserem ursprünglichen Beispiel, können Sie nicht einfach beide Maschinen bitten, Ihnen Daten zu einem bestimmten Zeitpunkt zu liefern, da sie eine leicht unterschiedliche Vorstellung von der aktuellen Zeit haben. Es sind Millisekunden, aber wenn viele Transaktionen verarbeitet werden müssen, reichen ein paar Millisekunden aus, um von korrekten Daten zu fehlerhaften Daten zu gelangen.
Zeitsynchronisation bringt uns zur zweiten Percolator-Zutat.
Zutat 2: Das Timestamp-Orakel
Percolators Lösung für das Zeitsynchronisationsproblem ist das sogenannte Timestamp-Orakel. 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 sich dieses System befindet, ist das Timestamp-Orakel. Wenn wir mehrere Versionen unserer Daten aufbewahren, benötigen wir mindestens zwei Zeitstempel für jede Abfrage. Erstens benötigen wir einen Zeitstempel, um einen Schnappschuss abzufragen, den wir zum Lesen von 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-Orakel benötigt, was zu noch mehr Latenz führt, wenn sich das Orakel in einer anderen Region befindet als die Knoten, von denen die Aufrufe stammen. Als Google seine verteilte Datenbank Spanner entwickelte, hat es dieses Problem gelöst.
2012 – Spanner
Spanner war die erste global verteilte Datenbank, die starke Konsistenz bot, was im Wesentlichen bedeutet, dass Sie Lesezugriffe mit geringer Latenz erhalten, ohne sich mehr um potenzielle Datenbankfehler sorgen zu müssen. Entwickler müssen keine zusätzliche Arbeit mehr investieren, um potenzielle Fehler zu umgehen, die durch die eventuelle Konsistenz verursacht werden. Das Paper wurde 2012 veröffentlicht und 2017 als Spanner Cloud für die breite Öffentlichkeit zugänglich gemacht.
Zutat 1: Versionierung
Google entwickelte Spanner nach ihren Erfahrungen mit Percolator. Da sich das Versionierungssystem von Percolator als funktionierend erwiesen hatte, behielten sie dies im Design von Spanner bei. Dieses Versionierungssystem bot die Möglichkeit, sehr schnelle Lesezugriffe (Snapshot-Reads) durchzuführen, wenn man bereit war, auf Konsistenz zu verzichten. In diesem Fall konnten Sie Abfragen ausführen und Spanner eine maximale Alter des Ergebnisses vorgeben. 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 Aufwand für die Zeitsynchronisation zwischen Maschinen zu eliminieren, verzichtete Spanner auf das Timestamp-Orakel und setzte stattdessen auf ein neues Konzept namens TrueTime. Anstatt eines zentralen Systems, das eine einheitliche Sicht auf die Zeit bietet, versucht TrueTime, die Zeitabweichung zwischen den Maschinen selbst zu reduzieren. Ingenieure bei Google gelang es, die lokale Zeitabweichung durch die Implementierung eines Zeitsynchronisationsprotokolls, das auf GPS und Atomuhren basiert, zu begrenzen. Dieser Synchronisationsalgorithmus ermöglichte es ihnen, die Zeitabweichung auf eine Grenze von 7 ms zu begrenzen, erforderte jedoch spezielle Hardware, die eine Kombination aus GPS- und Atomuhrtechnologie darstellte.
Natürlich gibt es immer noch eine potenzielle Zeitabweichung von 7 ms, was bedeutet, dass zwei Server einen Zeitstempel immer noch als zwei verschiedene Schnappschüsse 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 n, in dem sicher ist, dass der aktuelle Zeitstempel liegen sollte. Sobald der Commit bereit ist, wartet er nur wenige 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. Dies ist auch der Grund, warum die Ausführung von Spanner auf Standardhardware keine gleichen Garantien liefern kann, da die Wartezeit einige hundert Millisekunden betragen würde.
2012 – Calvin
Das erste Paper zum Calvin-Algorithmus wurde 2012 im Rahmen von Forschungsarbeiten an der Yale University veröffentlicht. Ähnlich wie die früheren Ansätze besteht Calvin aus mehreren Zutaten. Obwohl auch die Versionierung Teil davon ist, ist der Rest des Ansatzes radikal anders, was einige zusätzliche Zutaten erfordert: deterministische Berechnungen und die Trennung von Reihenfolge und Sperren. Dies sind Zutaten, 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 Anzahl der Cross-Data-Center-Nachrichten im schlimmsten Fall auf **zwei** reduzieren. Dies senkt die Latenz im schlimmsten Fall von globalen Transaktionen erheblich und bringt sie unter 200 ms oder theoretisch sogar unter 100 ms. Um dies glauben zu können, möchten Sie vielleicht zuerst wissen, wie es funktioniert, also werfen wir einen Blick auf den Algorithmus.
Zutat 1: Versionierung
Ähnlich wie Percolator und Spanner stützt sich Calvin auf versionierte Daten. Diese Schnappschüsse in Calvin werden hauptsächlich verwendet, um die Fehlertoleranz zu gewährleisten. Jeder Knoten speichert verschiedene Schnappschüsse, die als Checkpoints betrachtet werden können. Ein getrennter Knoten, der wieder online geht, muss nur den Zeitstempel des letzten Checkpoints abrufen, 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 wahrscheinlich vom Elm-Frontend-Framework gehört, das einen React Redux-ähnlichen Workflow 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 Seiteneffekte), 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 sie liefert 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, unabhängig davon, ob sie auf Maschine A oder Maschine B ausgeführt wird. Das mag offensichtlich erscheinen, aber typischerweise garantieren Datenbanken dies nicht. Denken Sie daran, dass SQL Ihnen erlaubt, die aktuelle Uhrzeit zu verwenden oder sogenannte interaktive Transaktionen zuzulassen, bei denen Benutzereingaben in die Mitte einer Transaktion eingefügt werden können, beides könnte die von Calvin bereitgestellten Garantien verletzen.
Um deterministische Berechnungen zu erreichen, muss Calvin (1) Berechnungen wie die aktuelle Uhrzeit herausnehmen und sie vorab berechnen und (2) keine interaktiven Transaktionen zulassen. Interaktive Transaktionen sind Transaktionen, bei denen ein Benutzer eine Transaktion startet, einige Daten liest, zwischendurch zusätzliche Benutzereingaben liefert 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 geringe Bequemlichkeit (interaktive Transaktionen) gegen große Leistung.
Zutat 3: Trennen Sie das Problem der Reihenfolge.
Datenbanken verbringen viel Zeit mit der Verhandlung 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 Sperren vom Problem der Reihenfolge trennen. Das bedeutet jedoch, dass Ihre Transaktionen rein sein müssen.
— Kyle Kingsbury
Die Trennung des Anliegens der Reihenfolge von Transaktionen von der eigentlichen Ausführung wurde in der Datenbankwelt schon viele Male in Betracht gezogen, jedoch ohne viel 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 leistungsfähig, da sie die Sperrdauer reduziert und die langsamere Kommunikation zwischen entfernten Knoten (Cross-Datacenter-Kommunikation) erheblich verringert.
Kürzere Sperrdauer
Wenn Sperren auf einem Datensatz gehalten werden, bedeutet dies, dass andere Abfragen, die diese Daten verwenden, warten müssen. Kürzere Sperren führen daher zu einer besseren Leistung. Unten sehen Sie ein Bild, das einen Überblick über den Sperrprozess in Calvin im Vergleich dazu zeigt, wie eine traditionelle verteilte Datenbank dies tun könnte. Die meisten Datenbanken würden eine Sperre auf Daten beibehalten, bis es zumindest einen Konsens darüber gibt, was geschrieben werden soll, während Calvin die Sperre nur so lange aufrechterhalten würde, bis sich alle Knoten auf die Reihenfolge geeinigt haben. Da die Berechnungen deterministisch sind und sie sich alle auf die Reihenfolge geeinigt haben, wird jeder Knoten separat berechnen und zum selben Endergebnis gelangen.
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 domänenübergreifende Kommunikation in vielen Phasen ihres Algorithmus. Im Fall von Calvin ist der einzige Moment, in dem wir uns über etwas einigen müssen, der Moment, in dem wir die Reihenfolge bestimmen. Mit dem Raft-Protokoll könnte dies in zwei Hops erfolgen, was es ermöglicht, Latenzen von unter 100 ms für Lese-/Schreibabfragen zu erreichen.
Zusammen mit der reduzierten Sperrzeit führt dies auch zu einem hervorragenden Durchsatz. Das ursprüngliche Paper zu Calvin hat auch Experimente durchgeführt, die zeigen, dass dieser Ansatz traditionelle verteilte Datenbankdesigns unter hohen Konfliktlasten erheblich ü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 leistungsfähigerer Hardware erzielt wurden.
Auf beliebiger Hardware ausführen
Darüber hinaus hat Calvin einen weiteren Vorteil: Es benötigt keine spezielle Hardware mehr, um solche Ergebnisse zu erzielen. Da Calvin auf Standardmaschinen laufen kann, kann es auf jedem Cloud-Anbieter ausgeführt werden.
2014 – Der FaunaDB-Geschmack von Konsens
Zutat 1: Versionierung
FaunaDB hat sein eigenes verteiltes Transaktionsprotokoll mit einigen Ähnlichkeiten zu Calvin. Genau wie bei den früheren Ansätzen werden die Daten von FaunaDB ebenfalls versioniert. Da die 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 genutzt 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 prüfen oder einfach Zeitreisen in die Funktionen Ihrer Anwendung zu integrieren.
Zutat 2 und 3: Deterministische Berechnungen und Trennung
Ähnlich wie Calvin verfügt FaunaDB über deterministische Berechnungen und trennt das Problem der Reihenfolge vom Rest des Algorithmus. Obwohl es Ähnlichkeiten gibt, erfolgt die Berechnung von Transaktionen in FaunaDB in einer anderen Phase als bei Calvin. Wo Calvin die deterministische Natur nutzt, um dieselbe Transaktion mehrmals auszuführen, sobald die Reihenfolge festgelegt ist, wird FaunaDB nur einmal vor dem Konsens über die Reihenfolge der Transaktionen berechnen. Was uns zur vierten Zutat führt.
Zutat 4: Optimistische Berechnung
FaunaDB fügt eine vierte Zutat hinzu, die wir bereits bei der Erwähnung von Snapshot Isolation gesehen haben: **Optimistische Berechnungen** anstelle von Sperren.
FaunaDB sperrt nicht, sondern berechnet den Transaktionsergebnis **einmal** optimistisch im Knoten, der die Transaktion empfangen hat, und fügt dann das Ergebnis und die ursprünglichen Eingabewerte dem Log 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 Log. Sobald ein Konsens über die Reihenfolge erzielt ist, in der die Ergebnisse angewendet werden sollen, überprüft FaunaDB, ob sich die Eingabedaten für diese Berechnung geändert haben oder nicht (dank der Versionierung). Wenn sich die Eingabewerte geändert haben, wird die Transaktion abgebrochen und neu gestartet. Wenn sie gleich geblieben sind, werden die Ergebnisse auf allen Knoten ohne zusätzliche Berechnung angewendet.
Der Algorithmus von FaunaDB hat ähnliche Vorteile wie Calvin, reduziert jedoch die Anzahl der erforderlichen Berechnungen im Cluster.
Fazit
In dieser Serie haben wir erläutert, wie starke Konsistenz Ihnen helfen kann, fehlerfreie Anwendungen effizienter zu erstellen. In diesem letzten Artikel haben wir weiter erläutert, 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 fasst die folgende Aussage die Quintessenz zusammen.
In naher Zukunft, wenn Sie eine Phrase lesen wie:
„Viele NoSQL-Datenbanken bieten keine atomaren Schreibvorgänge für mehrere Dokumente und bieten im Gegenzug 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, daher verzichten viele NoSQL-Datenbanken auf Konsistenz.“ – die größten Herausforderungen beim Umstieg auf 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 mit stärkeren Konsistenzmodellen erhalten. Das bedeutet, dass Sie datenintensive Anwendungen erstellen können, die geringe Latenzzeiten bieten, ohne sich um Datenfehler, Leistung oder Servicebereitstellung kümmern zu müssen. In solchen Systemen ist Konsistenz transparent, und Sie müssen sich als Entwickler nicht darum kümmern. Wählen Sie beim nächsten Mal, wenn Sie eine Datenbank auswählen, eine, die standardmäßig konsistent ist.