Cloud Spanner: TrueTime und externe Konsistenz

Vorteile von TrueTime für Cloud Spanner

TrueTime ist ein hochverfügbarer verteilter Zeitgeber, der für Anwendungen auf allen Google-Servern bereitgestellt 1 wird. TrueTime ermöglicht es Anwendungen, monoton steigende Zeitstempel zu generieren: Eine Anwendung kann einen Zeitstempel T berechnen, der garantiert größer als jeder Zeitstempel T' ist, wenn T' vor dem Erzeugen von T beendet wurde. Diese Garantie gilt für alle Server und Zeitstempel.

Diese Funktion von TrueTime wird von Cloud Spanner verwendet, um Transaktionen Zeitstempel zuzuweisen. Insbesondere wird jeder Transaktion ein Zeitstempel zugewiesen, der den Zeitpunkt widerspiegelt, ab dem Cloud Spanner das Ereignis als eingetreten einstuft. Da Cloud Spanner die versionsübergreifende Gleichzeitigkeitserkennung verwendet, können Cloud Spanner-Clients dank der Reihenfolgegarantie für Zeitstempel konsistente Lesevorgänge über eine ganze Datenbank hinweg ausführen (sogar über mehrere Cloud-Regionen hinweg), ohne Schreibvorgänge zu blockieren.

Externe Konsistenz

Cloud Spanner bietet Kunden die besten Garantien der Gleichzeitigkeitserkennung für Transaktionen. Dies wird als externe Konsistenz2 bezeichnet. Unter der externen Konsistenz verhält sich das System so, als ob alle Transaktionen sequenziell ausgeführt wurden, obwohl Cloud Spanner sie tatsächlich über mehrere Server hinweg (womöglich sogar in mehreren Rechenzentren) ausführt, um höhere Leistung und Verfügbarkeit zu erzielen. Wenn eine Transaktion abgeschlossen ist, bevor der Commit einer anderen Transaktion beginnt, garantiert das System, dass Kunden nie einen Zustand sehen, der die Auswirkung der zweiten Transaktion enthält, aber nicht die der ersten. Cloud Spanner ist semantisch nicht von einer Datenbank mit einem einzigen Rechner zu unterscheiden. Obwohl es so starke Garantien bietet, ermöglicht Cloud Spanner es Anwendungen, Leistungen zu erzielen, die mit Datenbanken mit schwächeren Garantien (und im Gegenzug besseren Leistungen) zu vergleichen sind. Beispielsweise lässt Cloud Spanner, genauso wie Datenbanken, die Snapshot-Isolation unterstützen, zu, dass Schreibvorgänge fortfahren, ohne von schreibgeschützten Transaktionen blockiert zu werden. Dabei zeigen sie allerdings nicht die Anomalien auf, die bei der Snapshot-Isolation erlaubt sind.

Externe Konsistenz vereinfacht die Anwendungsentwicklung erheblich. Angenommen, Sie haben eine Banking-Anwendung auf Cloud Spanner erstellt und einer Ihrer Kunden beginnt mit 50 € im Bankkonto und 50 $ auf dem Sparkonto. Ihre Anwendung startet dann einen Workflow, in dem zuerst eine Transaktion T1 übergeben wird, um 200 € auf das Sparkonto zu überweisen, und anschließend eine zweite Transaktion T2 ausgeführt wird, um eine Lastschrift über 150 € von dem Bankkonto abzubuchen. Nehmen wir weiter an, dass am Ende des Tages negative Salden auf einem Konto automatisch von anderen Konten gedeckt werden und ein Kunde eine Strafe erhält, wenn der Gesamtbetrag aller Konten zu einem Zeitpunkt an diesem Tages negativ ist. Externe Konsistenz garantiert, dass alle Leser der Datenbank erkennen, dass die Zahlung T2 vor der Abbuchung T1 stattgefunden hat, weil der Commit von T1 nach dem von T2 anfängt. Anders ausgedrückt garantiert externe Konsistenz, dass niemand jemals einen Zustand sehen wird, bei dem T2 vor T1 auftritt. Das heißt, die Abbuchung wird nie eine Strafe aufgrund unzureichender Mittel nach sich ziehen.

Eine traditionelle Datenbank, die eine strikte Zweiphasensperrung verwendet, sorgt für externe Konsistenz. Leider erhält ein solches System jedes Mal, wenn Ihre Anwendung die aktuellen Daten lesen möchte (auch "starker Lesevorgang" genannt), eine Lesesperre auf den Daten, wodurch Schreibvorgänge an den gelesenen Daten blockiert werden.

Zeitstempel und versionsübergreifende Gleichzeitigkeitserkennung (Multi-Version Concurrency Control, MVCC)

Um Lesevorgänge ohne Blockierung von Schreibvorgängen durchzuführen, speichern Cloud Spanner und viele andere Datenbanksysteme mehrere unveränderliche Versionen der Daten (oft als versionsübergreifende Gleichzeitigkeitserkennung bezeichnet). Ein Schreibvorgang erstellt eine neue unveränderliche Version, deren Zeitstempel dem Zeitstempel der Schreibtransaktion entspricht. Ein "Snapshot-Lesevorgang" bei einem Zeitstempel gibt den Wert der neuesten Version vor diesem Zeitstempel zurück und muss Schreibvorgänge nicht blockieren. Daher ist es wichtig, dass die den Versionen zugewiesenen Zeitstempel die Reihenfolge einhalten, in der Transaktionen übergeben werden können. Wir nennen diese Eigenschaft "ordnungsgemäße Zeitstempel". Beachten Sie, dass die Existenz eines ordnungsgemäßen Zeitstempels äquivalent zur externen Konsistenz ist.

Warum ordnungsgemäße Zeitstempel wichtig sind, sehen Sie am Online-Banking-Beispiel aus dem vorherigen Abschnitt. Ohne ordnungsgemäße Zeitstempel könnte T2 ein Zeitstempel zugewiesen werden, der früher als der Zeitstempel ist, der T1 zugewiesen ist (wenn beispielsweise ein hypothetisches System lokale Uhren anstelle von TrueTime verwendet und die Uhr des Servers, der T2 verarbeitet, etwas langsamer geht). Ein Snapshot-Lesevorgang könnte die Abbuchung von T2 widerspiegeln, aber nicht die Zahlung T1, obwohl der Kunde gesehen hat, dass die Zahlung beendet war, bevor die Abbuchung gestartet wurde.

Es ist einfach, richtige Zeitstempel für eine Datenbank mit einem einzelnen Gerät zuzuweisen (zum Beispiel können Sie Zeitstempel einfach von einem globalen, monoton ansteigenden Zähler zuweisen lassen). Die gleiche Genauigkeit in einem weit verteilten System wie Cloud Spanner zu erreichen, bei dem Server auf der ganzen Welt Zeitstempel zuweisen müssen, ist viel schwieriger und weniger effizient.

Cloud Spanner hängt beim Generieren monoton steigender Zeitstempel von TrueTime ab. Cloud Spanner verwendet diese Zeitstempel auf zwei Arten. Erstens werden diese als ordnungsgemäße Zeitstempel für Schreibtransaktionen verwendet, ohne dass eine globale Kommunikation erforderlich ist. Zweitens werden sie als Zeitstempel für starke Lesevorgänge verwendet, was ermöglicht, dass starke Lesevorgänge in einer Kommunikationsrunde ausgeführt werden können, selbst bei starken Lesevorgängen, die sich über mehrere Server erstrecken.

FAQ

Welche Konsistenzgarantien bietet Cloud Spanner?

Cloud Spanner bietet externe Konsistenz, die die strengste Konsistenzeigenschaft für Transaktionsverarbeitungssysteme ist. Diese Konsistenzeigenschaft wird von allen Transaktionen in Cloud Spanner erfüllt, nicht nur von den Transaktionen innerhalb einer Partition. Externe Konsistenz gibt an, dass Cloud Spanner Transaktionen auf eine Art und Weise ausführt, die von einem System, in dem die Transaktionen seriell ausgeführt werden, nicht zu unterscheiden ist. Außerdem stimmt die serielle Reihenfolge mit der Reihenfolge überein, in der Transaktionen festgeschrieben werden können. Da die für Transaktionen erzeugten Zeitstempel der seriellen Reihenfolge entsprechen, gilt Folgendes: Wenn ein Client den Start des Festschreibungsvorgangs für eine Transaktion T2 erkennt, nachdem eine andere Transaktion T1 abgeschlossen ist, ordnet das System einen Zeitstempel für T2 zu, der höher als der Zeitstempel für T1 ist.

Bietet Cloud Spanner Linearisierbarkeit?

Ja. Cloud Spanner verfügt mit der externen Konsistenz über eine Eigenschaft, die die Linearisierbarkeit noch übertrifft, da die Linearisierbarkeit nichts über das Verhalten von Transaktionen aussagt. Die Linearisierbarkeit ist eine Eigenschaft gleichzeitig existierender Objekte, die atomische (kleinstmögliche) Lese- und Schreibvorgänge unterstützen. Ein Objekt wird in einer Datenbank in der Regel durch eine einzelne Zeile oder eine einzelne Zelle repräsentiert. Die externe Konsistenz ist eine Eigenschaft von Transaktionsverarbeitungssystemen, bei denen Transaktionen, die mehrere Lese- und Schreibvorgänge enthalten, von Clients dynamisch synthetisiert werden. Die Linearisierbarkeit kann als Sonderfall der externen Konsistenz betrachtet werden, bei dem eine Transaktion nur einen einzigen Lese- oder Schreibvorgang für ein einziges Objekt enthalten darf.

Bietet Cloud Spanner Serialisierbarkeit?

Ja. Cloud Spanner verfügt mit der externen Konsistenz über eine noch stärkere Eigenschaft als die Serialisierbarkeit. Ein Transaktionsverarbeitungssystem gilt als serialisierbar, wenn es Transaktionen auf eine Weise ausführt, die von einem System mit serieller Transaktionsausführung nicht zu unterscheiden ist. Darüber hinaus bietet Cloud Spanner die Gewähr, dass die serielle Reihenfolge mit der Reihenfolge übereinstimmt, in der die Transaktionen übergeben werden.

Betrachten Sie noch einmal das zuvor verwendete Banking-Beispiel. In einem System, das Serialisierbarkeit ohne externe Konsistenz bietet, könnte das System die Reihenfolge ändern, obwohl der Kunde T1 und dann T2 sequenziell ausführt. Dies könnte dazu führen, dass für die Lastschrift eine Strafgebühr aufgrund von zu geringem Guthaben fällig wird.

Bietet Cloud Spanner hohe Konsistenz?

Ja. Cloud Spanner verfügt mit der externen Konsistenz über eine noch stärkere Eigenschaft als die hohe Konsistenz (strong consistency). Der Standardmodus für Lesevorgänge in Cloud Spanner ist "strong" (stark). Damit wird garantiert, dass die Auswirkungen aller Transaktionen einbezogen werden, die vor dem Start des Vorgangs übergeben wurden, und zwar unabhängig davon, welches Replikat den Lesevorgang empfängt.

Was unterscheidet die "hohe Konsistenz" von der externen Konsistenz?

Ein Replikationsprotokoll weist eine "hohe Konsistenz" auf, wenn die replizierten Objekte linearisierbar sind. Ähnlich wie bei der Linearisierbarkeit ist auch die "hohe Konsistenz" schwächer einzustufen als die "externe Konsistenz", da sie nichts über das Verhalten der Transaktionen aussagt.

Bietet Cloud Spanner Eventual Consistency (verzögerte Konsistenz)?

Cloud Spanner verfügt mit der externen Konsistenz über eine viel stärkere Eigenschaft als "Eventual Consistency" (verzögerte Konsistenz). Bei Eventual Consistency werden schwächere Garantien in Kauf genommen, um eine höhere Leistung zu erzielen. Eventual Consistency ist problematisch, da sie ermöglicht, dass die Leser auf einen Datenbankzustand zugreifen können, der nie real vorhanden war (z. B. könnte ein Lesevorgang einen Zustand abrufen, bei dem Transaktion B festgeschrieben ist, Transaktion A jedoch nicht, obwohl A vor B ausgeführt wurde). Cloud Spanner liefert veraltete Lesevorgänge, die ähnliche Leistungsvorteile wie Eventual Consistency bieten, jedoch mit viel höheren Konsistenzgarantien. Ein veralteter Lesevorgang gibt Daten von einem "früheren" Zeitstempel zurück, bei dem keine Schreibvorgänge blockiert werden können, da alte Datenversionen unveränderlich sind.

Weitere Informationen

Hinweise

  • 1J. C. Corbett, J. Dekan, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's Globally-Distributed Database. In: Tenth USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), S. 261–264, Hollywood, CA, Okt. 2012.
  • 2Gifford, D. K. Information Storage in a Decentralized Computer System. Doktorarbeit, Stanford University, 1981.