Eine vereinfachte klassische Datenbanktransaktion kann wie folgt angesehen werden:
- M Elemente lesen
- Durchführen einiger Berechnungen basierend auf diesen Lesevorgängen
- Schreiben einiger N-Ergebnisse basierend auf diesen Berechnungen, die die ursprünglich gelesenen Elemente enthalten können.
Bei der Ausführung dieser Transaktionen (gleichzeitig) müssen die ACID- Eigenschaften beibehalten werden.
Genau die gleichen Anforderungen (N Aktualisierungen basierend auf M Lesevorgängen auf Transaktionsebene) bestehen auch in anderen Nicht-DBMS-Systemen.
Ich bin daran interessiert herauszufinden, welche Algorithmen zum Ausführen / Auflösen dieser Transaktionen existieren und welche relativen Stärken und Schwächen diese Algorithmen haben. Könnten Sie etwas zum Lesen empfehlen? Dies können Bücher oder Online-Referenzen / Tutorials sein.
Klärung:
Ein naiver Algorithmus könnte beispielsweise sein, dass jede Transaktion eine einzelne globale Sperre durchführt, wodurch ein einzelnes Threading erzwungen und die Parallelität entfernt wird. Ein etwas komplizierterer Algorithmus wären Lese- / Schreibsperren für einzelne Elemente mit einer Reihenfolge, um einen Deadlock zu vermeiden. Usw. Gibt es eine gute Quelle, die verschiedene Algorithmen zur Lösung dieses Problems dokumentiert? Sogar eine Antwort, die nur auf einen einzigen Algorithmus mit seinen Stärken und Schwächen hinwies, wäre nützlich.
quelle
Antworten:
Das Buch Transactional Information Systems von Weikum und Vossen deckt einen großen Teil des theoretischen und praktischen Bereichs aus verschiedenen Perspektiven ab, nicht nur aus Transaktionen. Es ist ungefähr 1000 Seiten lang und wird Sie ein oder zwei Wochen lang beschäftigen. Auf der anderen Seite ist es fast 10 Jahre alt, so dass möglicherweise etwas aktuelleres verfügbar ist. Andere Bücher in der Reihe umfassen Parallelitätskontrolle und -wiederherstellung in Datenbanksystemen von Bernstein, P., Hadzilacos, V. und Goodman, N., Addison-Wesley, 1987, Transaktionsverarbeitung: Konzepte und Techniken von Jim Gray und Andreas Reuter sowie Prinzipien der Transaktionsverarbeitungvon Philip A. Bernstein und Eric Newcomer, 2009. Letzteres habe ich nicht gesehen, aber als jüngstes könnte es ein guter Anfang sein, obwohl Ihre Lösung möglicherweise in älteren Texten zu finden ist. Ein Ausflug in die Bibliothek kann sich lohnen.
Ein monumentaler Text in diesem Bereich ist Atomic Transactions von Nancy Lynch et al. Es enthält einen formalen Bericht und Beweise für eine Reihe von Algorithmen, an denen Sie interessiert sind. Es ist eher formal und langwierig und entspricht möglicherweise nicht Ihrem Geschmack.
Viele neuere Arbeiten widmen sich dem Software-Transaktionsspeicher , der die Transaktionsideen auf Multithread-Anwendungen anwendet. Zu diesem Thema gibt es jedes Jahr Dutzende von Veröffentlichungen: Die Wikipedia-Seite bietet zahlreiche Referenzen.
quelle