06 Concurrency Control

Das Testen auf Sicht-Serialisierbarkeit ist ein NP-Vollständiges Problem. Aus Effizienzgründen kann daher nicht jede Transaktion auf Serialisierbarkeit geprüft werden.
In der Praxis werden Protokolle verwendet die serialiserbare Schedules sicherstellen.

Synchronisationsmethoden werden in die beiden Kategorien ‘pessimistisch’ und ‘optimistisch’ eingeteilt.
Dabei gehen Optimistische Techniken von Konfliktfreiheit aus und überprüfen diese Annahme vor dem Abschluss einer Transaktion.
In echten Systemen sind die pessimistischen Verfahren, bei denen im Fall von möglichen Konflikten gesperrt wird, häufiger eingesetzt.

Synchronisationsmechanismen

Pessimistisch

Diese Verfahren blockieren Transaktionen allgemein, falls Konflikte drohen.

Preclaiming

Alle benötigten Datenobjekte werden zu Beginn einer Transaktion gesperrt.
So wird eine große Menge Resets vermieden, auch Deadlocks sind nicht möglich.
Sperrzeiten sind insgesamt unnötig lang, außerdem ist es nicht immer bekannt welche Objekte im Verlauf der Transaktion verwendet werden.
Daher wird diese Strategie kaum verwendet.

Sperrverfahren

Verwendet zwei Arten von Sperren.
Read-Write Locks erlauben das gleichzeitige Lesen durch mehrere Transaktionen, jedoch nur eine Schreiboperation.

Die Sperren können auf verschiedenen Objekten gesetzt werden.

• Gesamte Datenbank
• Dateien
• Blöcke
• Tabellen
• Zeilen
• Felder

Feinere Granularität erlauben einen höheren Durchsatz an Transaktionen, verursachen allerdings auch mehr Verwaltungsaufwand da mehr Sperren gesetzt, geprüft und zurückgenommen werden müssen.

Dabei gilt der Fundamentalsatz des Sperrens

Two Phase Locking

Mit dem ‘Two phase locking’ (2PL) Protokoll werden alle lock Operationen vor allen unlock Operationen durchgeführt. Somit genügt das Protokoll auch Regel 4 des Fundamentalsatzes.

Durch Verwendung von Locks können die Mehrbenutzerprobleme vermieden werden.
Weiterhin auftreten können Kaskadierende Rollbacks, wenn der Rollback einer Transaktion auch eine auf ihrem Zwischenergebnis basierende nächste Transaktion zum Rollback zwingt. Dabei existiert kein Limit, es kann eine beliebig lange Kette vorkommen.

Beim Anfordern von Sperren muss die Möglichkeit von Deadlocks vermieden werden, bei denen zwei Transaktionen aufeinander warten.

Kaskadierende Rollbacks

Der Fehlschlag einer Transaktion kann auch einen Rollback einer weiteren Transaktion erzwingen, wenn die Sperre auf ein Objekt vor dem finalen Commit freigegeben wurde und bereits von einer anderen Transaktion verwendet wird.

Dieses Problem kann vermieden werden, indem alle Sperren gleichzeitig am Transaktionsende freigegeben werden.

Es gibt noch eine Strikte Variante, bei der im Gegensatz zur eben gezeigten Rigorosen Version die lesenden Sperren auch früher freigegeben werden können.

Deadlock Vermeidung

Um Deadlocks zu vermeiden ist es notwendig alle benötigten Sperren direkt zur Beginn zu erlangen. Die Ermittlung dieser Menge ist allerdings eventuell aufwändig.

Eine andere Strategie verwendet Zeitstempel. So wird sichergestellt dass nur in ‘eine Richtung’ gewartet wird und keine Zyklen entstehen.

Wait-Die

Ältere Transaktionen warten auf jüngere.

1. T1 hält eine Sperre
2. T2 fordert die Sperre an
3. Entscheidung
   • Falls T1 jünger ist, so wartet T2 bis die Sperre frei ist
   • Falls T1 älter ist, bricht T2 ab und startet nach ‘gewisser Zeit’ mit altem Zeitstempel neu

if ts(Ti) < ts(Tj) then
	WAIT(Ti)
else
	ROLLBACK(Ti) // Die

Unter Anwendung des Wait-Die Algorithmus entsteht folgender Ablauf

Wound-Wait

Funktioniert umgekehrt zu Wait-Die. Jüngere Transaktionen warten auf ältere.

if ts(Ti) < ts(Tj) then
	ROLLBACK(Tj) // Wound
else
	WAIT(Ti)

Rollback

Mit ‘Rollback’ in Wait-Die und Wound-Wait ist kein vollständiger Rollback gemeint, sondern ein zurücksetzen auf den letzten vergangenen Checkpoint. (Siehe Abschnitt ‘Recovery’)

Beim selben Beispiel ist die Ausführung mit dem Wound-Wait Algorithmus bereits nach $33$ Zeitschritten beendet.

Klausuraufgabe

Bestimmung der Ausführungsreihenfolge bei mehreren Transaktionen mit Wound-Wait und Wait-Die algorithmus.

Waiting-For-Graph

Siehe auch Deadlocks.
In einem Graph wird jede Transaktion als Knoten dargestellt.
Beim Anfragen einer Sperre wird eine gerichtete Kante vom Anfragenden zum Besitzer der Sperre gezogen. Falls ein Zyklus entsteht, sind Deadlocks möglich.

Zeit	1	2	3	4
5	hat A
6		hat B
7			hat C
8	Wartet auf B (2)
9				hat D
10			Wartet auf A (1)
11		wartet auf C (3)

A wartet auf B wartet auf C wartet auf A; D ist separat

Deadlock mit ABC

Klausuraufgabe

Deadlocks erkennen mit Waiting-For-Graph

Sperrprotokolle

Die Kompatibilitätsmatrix eines Objekts zeigt welche Übergänge des Sperrmodus möglich sind.

Ein + bedeutet dass die Sperre vergeben werden kann, ein - verbietet es.

Die folgenden Beispiele basieren auf dieser Anfragereihenfolge:

RX Verfahren

	R	X
R	+	-
X	-	-
Es wird gleichzeitiges Lesen erlaubt, eine Änderungstransaktion schließt den Zugriff durch alle anderen Transaktionen aus.

Zu $t_4$ könnte $T_3$ schreiben, nur der Leser muss auf der alten Version weiter arbeiten.
Auch $T_4$ könnte zu $t_6$ mit dem alten Wert arbeiten, nur die neue Änderung von $T_3$ darf hier nicht sichtbar sein.

RAX Verfahren

Es wird neben read (R) und exclusive-write (X) noch eine analyse (A) Sperre eingeführt.

	R	A	X
R	+	+	-
A	+	-	-
X	-	-	-

• Zulassen von Lesetransaktionen, auch wenn Änderungstransaktion läuft
• Für Änderungstransaktion wird Objekt kopiert, Änderungen folgen auf Kopie, Objekt mit Kopie besitzt A-Sperre (Analyse)
• Lesetransaktionen arbeiten auf Originalversion
• Sind alle Lesetransaktionen beendet, werden alle A-Sperren in X-Sperren verwandelt, Kopie wird zum Original (Sperrkonversion)

RAC Verfahren

Lange Lesetransaktionen beim RAX Verfahren implizieren lange Wartezeiten für schreibende Transaktionen.
Beim Ende einer Transaktion werden A-Sperren hier in C-Sperren verwandelt. Dabei wird eine zusätzliche Kopie des ursprünglichen Objekts erstellt die durch die C-Sperre angezeigt wird. Lesende Aktionen versuchen erst auf Kopie 1 zuzugreifen, greifen bei Problemen auf Kopie 2 zu.

	R	A	C
R	+	+	+
A	+	-	-
C	+	-	-

In $t_7$ kann hier gleichzeitig die neue, zweite Kopie gelesen werden und das Ergebnis in der ersten Kopie an die Stelle des Originals kopiert werden.

Fundamentalsatz des Sperrens

1. Vor dem Zugriff muss eine Sperre gesetzt werden
2. Transaktionen fordern eine von ihr gesetzte Sperre nicht erneut an
3. Sperren durch andere Transaktionen müssen beachtet werden.
4. Es gibt eine Wachstumsphase in der Sperren gesammelt werden, und eine Schrumpfphase in der sie wieder freigegeben werden.
5. Spätestens zum Transaktionsende müssen alle Sperren wieder freigegeben werden.

Begründung

Während die Regeln 1-3 und 5 offensichtlich sind, scheint 4. nicht direkt sinnvoll.
Diese Vorgabe ist allerdings notwendig, um Serialisierbarkeit herzustellen.