Historie (Transaktionsverarbeitung)

Als Historie (der einem vollständigen Schedule entspricht, siehe Abschnitt Schedule und Schuffleprodukt) bezeichnet man in der Informatik im Bereich der Datenbanktheorie einen Ausführungsplan für die parallele Ausführung mehrerer Transaktionen (siehe auch Transaktionssystem), welcher angibt, in welcher Reihenfolge die Transaktionsoperationen ausgeführt werden. Zu den möglichen Arten von Transaktionsoperationen gehören Lese- und Schreiboperationen, und die Terminierungsoperationen Commit (erfolgreicher Abschluss der Transaktion) und Abort (Abbruch der Transaktion). Die Historie ist also eine Bezeichnung für die Ausführungsreihenfolge aller Operationen der parallel ausgeführten Transaktionen.

Schedule und Shuffleprodukt

Im Zusammenhang mit Historie sollte auch der Begriff Schedule genannt werden. Ein Schedule ist ein sogenanntes Präfix einer Historie. Präfix heißt in diesem Zusammenhang: das erste bis n-te Element der Historie. Ein vollständiger Schedule entspricht demnach einer Historie. Ein (formales) Beispiel für einen Schedule wäre:

Gegeben seien folgende Elemente:

$x,y,z$: Datenobjekte in einer Datenbank

$T_{i}$: eine von $n$ parallel ausgeführten Transaktion

$R_{i}(x)$: Leseoperation der Transaktion $i$ auf dem Objekt $x$

$W_{i}(x)$: Schreiboperation der Transaktion $i$ auf dem Objekt $x$

$C_{i}$: Commit-Operation der Transaktion $i$ (erfolgreicher Abschluss der Transaktion)

$A_{i}$: Abort-Operation der Transaktion $i$ (Abbruch der Transaktion)

$H_{i}$: eine von i möglichen Historien für $T_{1}$ bis $T_{n}$

$S_{i}(H_{i})$: ein Schedule der Historie $H_{i}$

Für die parallele Ausführung von 3 Transaktionen ($T_{1},T_{2},T_{3}$) sieht eine der möglichen Historien ($H_{1}$), mit ihren Schreiboperationen ($W_{i}()$) und Leseoperationen ($R_{i}()$) auf den Objekten ($x,y,z$) sowie den dazugehörigen Commitoperationen ($C_{i}$) und Abbruchoperationen ($A_{i}$), wie folgt aus:

Historie $H_{1}=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3},W_{2}(y),C_{2},W_{1}(x),C_{1}$

Ein möglicher Schedule ($S_{1}$), in diesem Fall der vollständige Schedule, für diese Historie wäre dann:

Schedule $S_{1}(H_{1})=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3},W_{2}(y),C_{2},W_{1}(x),C_{1}$

Ein weiterer möglicher Schedule ($S_{2}$) (unvollständig) für diese Historie wäre:

Schedule $S_{2}(H_{1})=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3},W_{2}(y),C_{2}$

Noch ein weiterer möglicher Schedule ($S_{3}$) (unvollständig) für diese Historie wäre:

Schedule $S_{3}(H_{1})=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),R_{3}(y),A_{3}$

Für die parallele Ausführung der drei Transaktionen gibt es natürlich noch weitere Historien, z. B. wenn wir die beiden Operationen der dritten Transaktion einfach nach hinten stellen:

Historie $H_{2}=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),W_{2}(y),C_{2},W_{1}(x),C_{1},R_{3}(y),A_{3}$

Die Menge aller möglichen Kombinationen der Lese- und Schreiboperationen, allerdings ohne die Commit- und Abbruchoperationen, nennt man Shuffleprodukt. Nehmen wir unsere zweite Historie ($H_{2}$) als Grundlage, dann würde das Element ($S_{2}$) aus der Menge der Shuffleprodukte ($S$) lauten:

$S_{2}=R_{1}(x),R_{1}(y),R_{2}(x),R_{2}(y),W_{2}(x),W_{2}(y),W_{1}(x),R_{3}(y)$

Bei genauer Betrachtung erkennt man, dass die Kombination der Lese- und Schreiboperationen gleich bleibt, aber die Commit- und Abbruchoperationen entfernt wurden.

Serielle und nicht/serialisierbare Historien, Korrektheitskriterium "Serialisierbarkeit"

Neben der Darstellung von bestimmten Ausführungsreihenfolgen der Operationen, dienen Historien zur Definition (und sind Grundlage zur Prüfung) der Serialisierbarkeit dieser Ausführungsfolgen.

Man stelle sich folgende Transaktionen auf einem Konto vor:

1. $T_{1}$: Hebe 100,- € von Konto Nr. 777980 ab.
2. $T_{2}$: Zahle 52,- € auf Konto Nr. 777980 ein.

$T_{1}$ umfasst eine Leseoperation zum Einlesen des Kontostands und eine Schreiboperation zur Modifikation des Kontostands. Das Gleiche gilt für $T_{2}$. Insgesamt sind für diese beiden Transaktionen also vier Operationen auszuführen. Eine Historie legt nun die Reihenfolge fest, in der diese Operationen abgearbeitet werden. Die naheliegendste Lösung wäre die Ausführung der Transaktionen nacheinander („seriell“), also beispielsweise zunächst alle Operationen von $T_{1}$ und danach alle Operationen von $T_{2}$. Eine solche Historie bezeichnet man als serielle Historie.

Ein Problem entsteht, wenn die serielle Ausführung von Transaktionen ineffizient ist. Wenn etwa eine ganze Reihe von Transaktionen warten muss, weil die erste Transaktion gerade auf eine Benutzereingabe wartet. In einigen Fällen ist die strikte Hintereinanderausführung aber gar nicht notwendig, z. B. wenn die Transaktionen auf ganz verschiedenen Datenobjekten arbeiten, oder nur Leseoperationen durchführen. In diesem Fall erhalten wir eine geringe Transaktionsdurchsatzrate (abgeschlossene Transaktionen pro Zeiteinheit). Um den Transaktionsdurchsatz zu erhöhen, werden in Transaktionssystemen auch Historien zugelassen, bei denen gleichzeitig mehrere Transaktionen sogenannt "aktiv" sind. Aktiv bedeutet, dass eine Transaktion $T_{1}$ mit der Ausführung beginnen kann, bevor die laufenden Transaktionen abgeschlossen sind, und es können bereits Operationen nachfolgender Transaktionen durchgeführt werden, bevor $T_{1}$ abgeschlossen ist. Korrekt ist eine solche nebenläufige Historie wenn sie die gleichen Ergebnisse liefert wie eine serielle Historie.

Formal lässt sich so ein Korrektheitskriterium Serialisierbarkeit für die nebenläufige Ausführung von Transaktionen definieren: Eine Historie $H$ ist dann serialisierbar, wenn sie äquivalent zu einer seriellen Historie $H'$ ist. Die Reihenfolge der Transaktionen in $H'$ nennt man dann Serialisierungsreihenfolge. Wichtig ist dabei, dass die relative Reihenfolge konfligierender Operationen (z. B. zwei Schreiboperationen) in der Historie $H$ der Serialisierungsreihenfolge der zugehörigen Transaktionen entspricht. Konfligierende Operation bedeutet, dass zwei Operationen verschiedener Transaktionen auf das gleiche Datenobjekt zugreifen und mindestens eine der beteiligten Operationen eine Schreiboperation ist.

Total und partial geordnete Historien

Da für manche Operationen die Reihenfolge keine Rolle spielt, definieren Historien i. A. keine totale Ordnung auf allen Operationen, sondern nur eine partielle Ordnung, die in erster Linie die relative Reihenfolge konfligierender Operationen festlegt. Solche partiellen Ordnungen können mit Hilfe eines gerichteten Graphen dargestellt werden:

${\begin{matrix}r_{1}[x]&\rightarrow &w_{1}[x]&&r_{1}[x]&\rightarrow &c_{1}&\rightarrow &c_{2}\\&&\downarrow &\nearrow \\r_{2}[y]&\rightarrow &w_{2}[x]\end{matrix}}$

In der hier dargestellten Historie wird eine Leseoperation der Transaktion $T_{1}$ auf einem Objekt $x$ als $r_{1}[x]$ notiert, während eine Schreiboperation von $T_{1}$ auf $x$ als $w_{1}[x]$ notiert wird. Die Pfeile geben die relative Reihenfolge konfligierender Operationen an. Die hier dargestellte Historie ist nicht serialisierbar.

Klassifikation und Protokolle

Scheduler können in folgende Klassen eingeteilt werden:

• Pessimistische / konservative Scheduler. Diese Scheduler versuchen Konflikte zwischen Operationen nebenläufiger Transaktionen während ihrer Ausführung zu erkennen bzw. zu beheben. Sie bevorzugen die Verzögerung von Operationen bei Konflikten.
  • Sperrende Scheduler (Locking Scheduler) - Die o. g. Kriterien werden durch Locks (Sperren) erreicht.
    • 2PL - Two-Phase-Locking. Jede Transaktion teilt sich in zwei Phasen. In der ersten dürfen Locks nur angefordert werden und in der zweiten Phase dürfen diese nur freigegeben werden. Es ist also einer Transaktion nicht erlaubt nach der Freigabe eines Datenelements einen neuen Lock darauf anzufordern. Die ausgegebenen Schedules sind CSR.
      • C2PL - conservative 2PL. Hier werden grundsätzlich beim Start jeder Transaktion alle Locks angefordert.
      • S2PL - strict 2PL. Sämtliche angeforderten Write Locks werden erst beim Abschluss der Transaktion freigegeben. Es kann bewiesen werden, dass solche Schedules zusätzlich zu CSR auch ST sind.
      • SS2PL - strong 2PL. Alle Locks werden erst beim Abschluss der Transaktion freigegeben. Es kann bewiesen werden, dass solche Schedules der Klasse RG entsprechen.
    • Baum-Sperrprotokolle. Wie 2PL, nur speziell für Bäume unter Ausnutzung deren besonderer Eigenarten.
      • WTL - write only tree locking
      • RWTL - read write tree locking
      • MGL - multiple granularity locking. Die Datenbankobjekte werden in einem Baum hierarchisch organisiert. An oberster Stelle steht z. B. die Datenbank, darunter Tabellen und weiter unten Tupel. Um an unterer Stelle ein Lock zu erhalten muss an den darüber liegenden Knoten mindestens ein ebensolches Lock bereits existieren. Beim Freigeben ist dies genau umgekehrt. MGL-produzierte Schedules sind CSR.
  • Nicht-sperrende Scheduler (non-locking)
    • TO - Zeitstempel-Verfahren (time ordering). Um Synchronisationsprobleme zu vermeiden, werden Zeitstempel für jede Transaktion vergeben sobald ihre jeweils erste Operation beim Scheduler eingeht. Zwei Strategien sind zu unterscheiden: wait-die und wound-wait
      • BTO - Basis-TO. Einfache und aggressive Implementierung von TO. Operationen werden hier direkt an den Datenverwalter weitergeleitet und Transaktionen zu spät kommender Operationen abgebrochen.
    • SGT - Serialisierungsgraph-Tester
    • Generische Prüfung
• Optimistische / aggressive Scheduler. Diese Scheduler verschieben die Konfliktprüfung durch einen sog. Certifier auf den Commit-Zeitpunkt einer Transaktion. Sie führen eine Transaktion in drei Phasen aus: Read Phase (Operationen werden ausgeführt, Schreibzugriffe erfolgen ausschließlich im transienten lokalen Arbeitsbereich), Validation Phase (beim Commit wird die Transaktion durch Certifier validiert), Write Phase (Inhalt des transienten lokalen Arbeitsbereiches wird in die persistente Datenbasis übertragen). Validation Phase und Write Phase sind ununterbrechbar, werden also immer ohne Unterbrechung ausgeführt.
  • BOCC - backward oriented optimistic concurrency control.
  • FOCC - forward oriented optimistic concurrency control.
• Hybride Scheduler. Sie verteilen die Konfliktprüfung auf mehrere Komponenten, die unterschiedliche Protokolle verwenden können.
  • Unterscheidung nach Konfliktart (read-write- / write-write-Konflikt)
  • Unterteilung der Datenelemente in disjunkte Teilmengen
  • Unterteilung der Datenelemente nach ihrem Zugriffsmuster

Darüber hinaus gibt es noch Mehrversionen-Scheduler, welche zu jedem geschriebenen Datenelement mehrere Versionen speichern können, um Inconsistent Reads zu vermeiden. Ein Mehrversionen-Scheduler muss zusätzlich zum und abhängig vom umgesetzten Protokoll einer Lese-Operationen eine bestimmte Version des gelesenen Datenelementes zuweisen. Eine Schreib-Operation erzeugt normalerweise eine neue Version des jeweiligen Datenelements. Mehrversionen-Protokolle sind MVTO, MV2PL, MVSGT, ROMV (read only mulitiversion protocol).

Literatur

• Alfons Kemper, André Eickler: Datenbanksysteme. Oldenbourg, 2004, ISBN 3-486-25706-4. 
• Theo Härder, Erhard Rahm: Datenbanksysteme, Konzepte und Techniken der Implementierung. Springer, Berlin 2001, ISBN 3-540-42133-5.