Concurrency Control

Historie muss mindestens konfliktserialisierbar sein - meistens auch strikt.

Sperrbasierte Synchronisation

Verträglichkeits- / Kompatibilitäts-Matrix

$NL$ no lock

$S$ shared - read lock

$X$ exclusive - write lock

Bei MGL

$IS$ intention shared lock - tiefer in Hierarchie

$IX$ intention exclusive lock - tiefer in Hierarchie

2PLs

Zwei-Phasen-Sperrprotokoll 2PL

Jedes Objekt muss vor der Verwendung locked werden

Es darf nicht ein lock angefordert werden, wenn man sie bereits besitzt

locks werden nach Kompatibilitätsmatrix gewährt wenn man nicht blockiert ist

Nach einem unlock, ist kein Anfordern von locks erlaubt (2 Phasen)
Wachstumsphase → Schrumpfungsphase

Bei $\small \tt EOT$ müssen alle Sperren freigegeben werden

erzeugt konfliktserialisierbare Historien (ohne $\small \tt abort$ seriell)

Strict 2PL

Alle unlocks müssen bis $\small \tt EOT$ blockiert und dann aufeinmal ausgeführt werden.

erzeugt strikte Historien

Conservative 2PL (= Preclaiming)

Alle unlocks müssen bis $\small \tt EOT$ blockiert und dann aufeinmal ausgeführt werden.

Alle locks müssen bei $\small \tt BOT$ aufeinmal ausgeführt werden.

Variante von strict 2PL

Transaktionen nur gestartet wenn sie alle ihre locks von Anfang an bekommen

Vermeidet deadlocks

Deadlocks

Bei 2PLs sind deadlocks möglich.

Sie lassen sich mit conservative 2PL oder Zeitstempelverfahren vermeiden.

Beispiel

Erkennung

Time-out Strategie

Einfache Methode

$\small \tt abort$ innerhalb einer Zeitspanne keine Fortschritte gemacht werden

timeout zu klein - unnötige $\small \tt abort$ s

timeout zu groß - deadlocks zu spät erkannt

Wartegraph

Exakte Methode

gerichtete Kante $\small T_{i} \rightarrow T_{j}$ falls $\small T_{i}$ auf $\small T_{j}$ wartet.

Deadlock = Zyklus um Graph

Knoten entfernen um Zyklus aufzulösen

Zeitstempelverfahren

Jede Transaktion hat Zeitstempel $\small TS(T_i)$ zB vergangene Sekunden oder counter

Jüngere Transaktionen = größere Zeitstempel

$\small T S\left(T_{i}\right)<T S\left(T_{j}\right)$ $\small T_i$ älter als $\small T_j$

Zeitstempel entscheidet ob Transaktion auf lock wartet oder $\small \tt abort$ ed wird.

Angenommen $\small T_1$ will lock den $\small T_2$ besitzt.

wound-wait Strategie: ältere Transaktion (kleinere Zahl) setzt sich durch

Wenn $\small T_1$ älter $\small T_2$ wird $\small \tt abort$ ed

Wenn $\small T_2$ älter $\small T_1$ wartet bis Freigabe

wait-die Strategie: jüngere Transaktion (größere Zahl) setzt sich durch

Wenn $\small T_1$ älter $\small T_2$ wartet bis Freigabe

Wenn $\small T_2$ älter $\small T_1$ wird $\small \tt abort$ ed

Granularität von Sperren

Multiple Granularity Locking (MGL)

kleinere Sperrgranulate → verbesserte Effizienz:

Datensatz $\sube$ Tabelle $\sube$ Seite $\sube$ Segment / area (logisch zusammengehörende pages) $\sube$ Datenbasis

Anforderung: bei lock müssen Kinder auch gelocked werden

Freigabe: nur möglich wenn Kinder auch freigegeben wurden

Delete - $\small X$ -lock

Andere Transaktionen die ein lock für das Objekt wollen, werden es nach dem $\small \tt commit$ der Transaktion nicht mehr erhalten.

Insert - $\small X$ -lock

Sollte vermieden werden:

Phantomproblem (Indexbereich sperren).

Konfliktserialisierbar $\not \Rarr$ serialisierbar bei Inserts.

Zeitstempel-basierende Synchronisation

keine Deadlocks

erzeugt konfliktserialisierbare Historie (deshalb kein $\small \tt abort$ erlaubt)

Vor jedem Zugriff timestamp abfragen - sich bei Konflikt $\small \tt abort$ en.

Um $\small \tt abort$ zu ermöglichen

Rücksetzbare Historie

$\small \tt commit$ blockieren bis alle Transaktionen von denen gelesen wurde beendet sind.

Strikte Historie

alle Schreib-Operationen am Ende atomar ausführen.

Dirty-bit
true = Datensatz von aktiver Transaktion geschrieben
kein kaskadierendes Rücksetzen: Schreiben für andere blockieren wenn true .
strikte Historie: Schreiben und Lesen für andere blockieren wenn true .
Nach $\small \tt commit$ die dirty-bits auf false setzen.
Nach $\small \tt abort$ - wenn die Transaktion davor $\small \tt commit$ ed hat - die dirty-bits aktualisieren und $\small \tt writeTS(\text A)$ zurücksetzen.

Definition

Jede Transaktion hat timestamp $\small TS(T_i)$ zB vergangene Sekunden oder counter

Jüngere Transaktionen = größere Zeitstempel

$\small T S\left(T_{i}\right)<T S\left(T_{j}\right)$ $\small T_i$ älter als $\small T_j$

Jedes Datenobjekt $\small A$ hat 2 timestamps zum abfragen:

$\small \tt readTS(\text A)$ TS der jüngsten Transaktion die $\small A$ gelesen hat

$\small \tt writeTS(\text A)$ TS der jüngsten Transaktion die $\small A$ geschrieben hat

Lesezugriff $r_i(A)$

$\small T S\left(T_{i}\right)< \tt writeTS(\text A)$

$\small T_i$ ist älter als anderer der geschrieben hat.

Das bedeutet der ursprünglichen Reihenfolge der Transaktionen zufolge, müsste $\small T_i$ vor der Schreiboperation gelesen haben. - Das trifft nicht zu.

$\small T_i$ wird zurückgesetzt.

$\small T S\left(T_{i}\right) \geq \tt writeTS(\text A)$

$\small T_i$ ist jünger oder gleich alt wie anderer der geschrieben hat.

Das bedeutet der ursprünglichen Reihenfolge der Transaktionen zufolge, müsste $\small T_i$ nach der Schreiboperation gelesen haben. - Das trifft zu.

$\small T_i$ darf lesen.

$\small \tt readTS(\text A) =~$ $\small \textcolor{grey}{ \max(}~TS(T_i),~ \small \tt readTS(\text A)~\textcolor{grey}{ )}$

Schreibzugriff $w_i(A)$

$\small T S\left(T_{i}\right)< \tt writeTS(\text A)$

$\small T_i$ ist älter als anderer der geschrieben hat.

Das bedeutet der ursprünglichen Reihenfolge der Transaktionen zufolge, müsste $\small T_i$ vor der Schreiboperation geschrieben haben. - Das trifft nicht zu.

$\small T_i$ wird zurückgesetzt.

$\small T S\left(T_{i}\right)< \tt readTS(\text A)$

$\small T_i$ ist älter als anderer der gelesen hat.

Das bedeutet der ursprünglichen Reihenfolge der Transaktionen zufolge, müsste $\small T_i$ vor der Leseoperation geschrieben haben, damit die andere Transaktion diesen Wert liest. - Das trifft nicht zu.

$\small T_i$ wird zurückgesetzt.

$\small T S\left(T_{i}\right) \geq \tt writeTS(\text A)$ und $\small T S\left(T_{i}\right) \geq \tt readTS(\text A)$

$\small T_i$ ist jünger oder gleich alt wie anderer der geschrieben oder gelesen hat.

$\small T_i$ darf schreiben.

$\small \tt writeTS(\text A) =~$ $\small TS(T_i)$

Transaktionsverwaltung mit SQL

SET TRANSACTION
[ READ WRITE | READ ONLY ]
[ ISOLATION LEVEL {
READ UNCOMMITED | READ COMMMITED | REPEATABLE READ | SERIALIZABLE
}]

READ UNCOMMITED

Schwächste Stufe.

Nicht festgeschriebene, inkonsistente Änderungen können gelesen werden.

Nur für READ ONLY erlaubt.

READ COMMITED

Nur Daten können gesehen werden die vor der Operation commited waren.

REPEATABLE READ

Nur Daten können gesehen werden die vor der Transaktion commited waren.

SERIALIZABLE

Höchste Stufe.