Was sind die wichtigsten Forschungsfragen bei verteilten Transaktionen?

10

Hintergrund: Die Transaktionsverarbeitung ist ein traditionelles Forschungsthema in der Datenbanktheorie. Heutzutage werden verteilte Transaktionen von großen verteilten Speichersystemen populär gemacht, die typischerweise Datenpartition (auch Sharding genannt) und Datenreplikation umfassen .

Was sind die wichtigsten Forschungsfragen bei verteilten Transaktionen?

Gibt es bekannte Theorien und Lösungen, die (theoretisch) verbessert werden müssen?

Alle Referenzen werden geschätzt.

Hengxin
quelle

Antworten:

9

Sowohl in der Theorie als auch in der Praxis verteilter Datenbanken gibt es viele Forschungsbereiche.

Eine der wichtigsten praktischen Herausforderungen besteht darin, effiziente Mechanismen zur Kontrolle der Parallelität für verteilte und georeplizierte Datenbanken zu implementieren. Um Transaktionen effizient auszuführen, können solche Mechanismen schwächere Garantien als die Serialisierbarkeit bieten, was erfordert, dass Transaktionen scheinbar nacheinander ausgeführt werden. Eine Alternative zur Serialisierbarkeit besteht darin, sich für die Snapshot-Isolation zu entscheiden [1]. Es wurde jedoch nachgewiesen, dass dies für georeplizierte und verteilte Systeme schlecht skalierbar ist. Nach dem aktuellen Stand der Technik wurden zwei verschiedene Varianten der Snapshot-Isolation (SI) definiert, um die Parallelitätskontrolle in georeplizierten Systemen zu behandeln: die parallele Snapshot-Isolation (PSI) [2] und die nicht monotone Snapshot-Isolation (NMSI) [ 3,4]. Was verteilte Datenbanken betrifft (dh wo Daten zwischen verschiedenen Standorten aufgeteilt werden),

Eine andere wichtige Frage, die unterschiedliche Vorstellungen von Isolationsstufen hat, die schwächere Garantien als die Serialisierbarkeit bieten, besteht darin, Programme so zu schreiben, dass Ausführungen immer noch serialisierbar erscheinen. Ein solides Kriterium für die Snapshot-Isolierung wurde in [1] entwickelt. Einige Leute in meiner Gruppe arbeiten derzeit daran, ein vernünftiges Kriterium für PSI zu entwickeln.

Eine weitere relevante Frage, sowohl aus theoretischer als auch aus praktischer Sicht, ist die des Transaktionshackens. Grundsätzlich ist das Hacken eine statische Analysetechnik, bei der grobkörnige Transaktionen in kleinere, feinkörnige Transaktionen zerlegt werden. Aus Gründen der Serialisierbarkeit wurde diese Frage in [6] behandelt, und die daraus resultierende Theorie wurde angewendet, um eine praktische Implementierung in [7] zu ermöglichen.

Unter dem Gesichtspunkt der theoretischen Grundlagen verteilter Datenbanken wurde vorgeschlagen, Techniken aus der Community der schwachen Speichermodelle [8] zu verwenden, um das Verhalten von Transaktionen formal zu definieren. In [9] geben die Autoren einen formalen Begriff des Verhaltens für Transaktionen; Der gleiche Ansatz wurde in [10] verwendet, um das Verhalten replizierter Datentypen zu spezifizieren.

Kürzlich haben ich und einige meiner Kollegen (Alexey Gotsman und Hongseok Yang) ausgehend von den in [8,9,10] entwickelten Techniken einen theoretischen Rahmen für die Spezifizierung des beobachtbaren Verhaltens von Konsistenzstufen für georeplizierte Datenbanken erstellt. Wir haben das Framework erfolgreich eingesetzt, um eine Axiomatisierung von SI, PSI und NMSI zu erzielen, von denen wir uns in Bezug auf eine einfache Implementierung als richtig erwiesen haben. Wir haben die resultierende Theorie auch genutzt, um ein Zerhackungskriterium für PSI zu entwickeln. Diese Ergebnisse werden wir hoffentlich in absehbarer Zeit veröffentlichen.

Bitte zögern Sie nicht, mir zu schreiben, wenn Sie weitere Fragen haben. Hoffe das hilft,

Andrea Cerone.

Verweise:

[1] Fekete et al., Making Snapshot Isolation Serializable (2005)

[2] Sovran et al., Transaktionsspeicher für georeplizierte Systeme (2011)

[3] Arkedani et al., Nicht-monotone Snapshot-Isolierung: Skalierbare und starke Konsistenz für georeplizierte Transaktionssysteme (2013)

[4] Arkedani et al., Zur Skalierbarkeit der Schnappschussisolierung (2013)

[5] Binnig et al., Distributed Snapshot Isolation: Globale Transaktionen zahlen global, lokale Transaktionen zahlen lokal

[6] Shasha et al., Transaction Chopping: Algorithmen und Leistungsstudien (1995)

[7] Zhang et al., Transaktionsketten: Erreichen der Serialisierbarkeit mit geringer Latenz in geoverteilten Speichersystemen (2013)

[8] Alglave, Eine formale Hierarchie schwacher Speichermodelle (2012)

[9] Buckhardt et al., Understanding Eventual Consistency (2013)

[10] Buckhardt et al., Replizierte Datentypen: Spezifikation, Verifikation, Optimalität (2014)

Andrea Cerone
quelle
Vielen Dank für Ihre umfassende Antwort. Gibt es für SI verteilte, sperrfreie Protokolle in replizierten Einstellungen in der Literatur? Oder ist dieser Versuch bedeutungslos, weil SI nicht gut skaliert? Für PSI habe ich ein Papier gelesen (Tim Kraska @ Eurosys'13), in dem die Umsetzung in zukünftigen Arbeiten erwähnt wurde. Ist Generalized Paxos dafür geeignet? Was sind die möglichen Vor- / Nachteile / Herausforderungen im Vergleich zum ursprünglichen von Sovran et al. [2]? Danke noch einmal.
Hengxin
2
Tatsächlich lässt sich SI nicht gut auf georeplizierte Systeme skalieren. In [4] oben beweisen die Autoren, dass es Eigenschaften wie die echte partielle Replikation gibt, die von georeplizierten DBMS, die auf der SI-Konsistenzstufe ausgeführt werden, nicht erreicht werden können. In [5] zeigen die Autoren Beispiele für Ausführungen, die sich gemäß SI lokal (bei einzelnen Shards), aber nicht global verhalten, und schlagen eine Variante von SI mit dem Namen DSI vor. Was MDCC betrifft, ist mir dieses Papier nicht bekannt, und ich muss zugeben, dass ich die Implementierungsdetails von generalisiertem Paxos nicht kenne. Aber ich werde gerne einen Blick darauf werfen und so schnell wie möglich antworten.
Andrea Cerone