In Spanner ist TrueTime & Das CAP-Theorem , schreibt Eric Brewer:
Eine subtile Sache bei Spanner ist, dass es Serialisierbarkeit durch Sperren erhält, aber externe Konsistenz (ähnlich wie Linearisierbarkeit ) aus TrueTime [ Hervorhebung hinzugefügt ].
Was ist die Definition von externer Konsistenz ? und wie unterscheidet es sich von Linearisierbarkeit ?
Kommentare
- Dies ist eine großartige Frage, und ich wünschte, Eric hätte sie hier etwas ausgearbeitet. Ist es linearisierbar oder nicht? 🙂
Antwort
Externe Konsistenz hat keine feste Bedeutung. In diesem Zusammenhang hat sie die Dies bedeutet, dass dies im nächsten Satz des Dokuments erscheint:
Für zwei beliebige Transaktionen $ T_1 $ und $ T_2 $ (auch wenn sie sich auf gegenüberliegenden Seiten des Dokuments befinden Globus): Wenn $ T_2 $ mit dem Festschreiben beginnt, nachdem $ T_1 $ das Festschreiben beendet hat, ist der Zeitstempel für $ T_2 $ größer als der Zeitstempel für $ T_1 $.
Kommentare
- Je mehr ich darüber nachdenke, desto mehr klingt dies für mich nach Linearisierbarkeit, da alle Transaktionen geordnet sind. Leider sind diese Begriffe manchmal subtil. Ich meine, die Transaktionen sind serialisierbar und werden basierend auf der Festschreibungszeit vollständig geordnet. Vielleicht liegt die Subtilität darin, wie 2PC in Spanner implementiert wird?
- @Bminer Linearisability ist ein Konsistenzmodell, das gilt nur für einzelne Objekte, bei denen Transaktionen mehrere o umfassen können Objekte.
- @LorinHochstein – Ha! Das riecht nach zerkleinerten Worten. Der springende Punkt der Terminologie ist es, echten Menschen dabei zu helfen, sich vorzustellen, welche Garantien sie erhalten, insbesondere im Hinblick auf Transaktionen. Linearisierbarkeit + Serialisierbarkeit ist die stärkste Garantie, und ich denke, dass ' das ist, worauf sich die Spanner-Dokumente mit dem Begriff " externe Konsistenz beziehen. " Aber es stellt sich die Frage: Weiß jemand wirklich, was " externe Konsistenz " meint? 🙂
Antwort
Sie können über die externe Konsistenz aus Sicht der Transaktionsisolation (Tx) und der Reihenfolge nachdenken . In der Tx-Isolation entspricht die externe Konsistenz der strengen serialisierbaren Isolation, wobei „strict“ der Echtzeit-Einschränkungsteil ist (wie bei der Linearisierbarkeit).
Das alles bedeutet wiederum, dass ein Systemclient Tx beobachten kann Nebenwirkungen sind gleichbedeutend mit einem System, bei dem alle Sendungen isoliert und ohne Parallelität stattfinden und deren Echtzeitreihenfolge aus Sicht des Kunden erhalten bleibt. Noch wichtiger ist, dass dieselbe Reihenfolge von jedem anderen unabhängigen Kunden gesehen wird.
Weitere Informationen zur Unterscheidung finden Sie unter in diesem Blog .
Antwort
Wenn " externe Konsistenz erwähnt wird " , Brewer verweist auf B. Liskov. Praktische Verwendung synchronisierter Uhren in verteilten Systemen . ACM-Prinzipien des verteilten Rechnens (PODC). Montreal, Kanada, August 1991.
Liskov bezieht sich in Bezug auf Gifford D.K. Informationsspeicherung in einem dezentralen Computersystem . Technischer Bericht CSL-81-8, Xerox Corporation, März 1983
So definiert Gifford die externe Konsistenz:
Extern Konsistenz garantiert, dass eine Transaktion immer aktuelle Informationen erhält. Mit den soeben eingeführten Konzepten können wir eine formale Definition der externen Konsistenz bereitstellen. Die tatsächliche Zeitreihenfolge, in der Transaktionen abgeschlossen werden, definiert einen eindeutigen seriellen Zeitplan. Dieser serielle Zeitplan wird als
externer Zeitplan Ein System soll externe Konsistenz bieten, wenn es garantiert, dass der Zeitplan, den es zur Verarbeitung einer Reihe von Transaktionen verwendet, seinem externen Zeitplan entspricht.
Wie @Oleg erwähnt, klingt dies wie strikte Serialisierbarkeit .