Sperrverfahren

Sperrverfahren werden in Datenbanksystemen eingesetzt, um die Forderung der Isolation des ACID-Prinzips bei Transaktionen zu erfüllen. Alle Sperrverfahren, auch Sperrprotokolle genannt, fallen in die Kategorie der pessimistischen Synchronisationsverfahren („Pessimistisches Locking“), d. h., es wird bei dem Start einer Transaktion davon ausgegangen, dass es mit hoher Wahrscheinlichkeit zu einem Konflikt mit einer parallel ablaufenden Transaktion kommt. Deren Gegenteil bilden optimistische Verfahren, die Schedules auf Konflikte untersuchen und ggf. eine der beteiligten Transaktionen zurücksetzen („Rollback“).

Einführung

Um eine Transaktion formal darstellen zu können, wird der Vereinfachung halber angenommen, dass auf einem Datenbankobjekt $a$ entweder eine Lese- oder eine Schreiboperation stattfinden kann. Beim Lesen wird das Objekt, im Gegensatz zum Schreiben, nicht verändert.

Um mehrere Transaktionen, welche gleichzeitig auf das gleiche Datenbankobjekt zugreifen wollen, miteinander zu synchronisieren, kann jede Transaktion eine Lesesperre (shared lock) oder eine Schreibsperre (exclusive lock) auf ein Objekt anfordern.

Bevor eine Transaktion $T$ das Objekt $a$ nutzen darf, muss sie eine Sperre für $a$ anfordern ($R(a)$). Wenn eine andere Transaktion $P$ das gewünschte Objekt allerdings exklusiv gesperrt hat, muss $T$ solange warten, bis $P$ das Objekt wieder freigegeben hat und $T$ die Lesesperre erhält. Während dieser Wartezeit spricht man davon, dass $T$ blockiert ist. Eine Blockade kann immer dann auftreten, wenn eine andere Transaktion bereits eine Sperre auf das gewünschte Objekt $a$ gesetzt hat.

In dem Fall, dass mehrere Transaktionen gegenseitig auf die Freigabe von Sperren warten, das heißt, sie sich gegenseitig blockieren, spricht man von einem „Deadlock“.

In welchen Situationen eine Blockade erfolgt, hängt von dem jeweils eingesetzten Sperrverfahren ab und kann aus der dazugehörenden Kompatibilitätsmatrix (s. u.) abgelesen werden.

Formale Schreibweisen

Transaktion $T_{i}$ liest Objekt $a$: $r_{i}(a)$

Transaktion $T_{i}$ schreibt Objekt $a$: $w_{i}(a)$

Transaktion $T_{i}$ fordert eine Lesesperre auf dem Objekt $a$ an: $R_{i}(a)$

Transaktion $T_{i}$ fordert eine Schreibsperre auf dem Objekt $a$ an: $X_{i}(a)$

Kompatibilitätsmatrix

Die Kompatibilitätsmatrix gibt an, ob eine Transaktion eine bestimmte Sperre auf ein Objekt erhalten kann, wenn eine andere Transaktion bereits eine Sperre auf demselben Objekt erhalten hat.

	R	X
R	+	−
X	−	−

Leseart:

• In der obersten Zeile ist die Art der bereits gesetzten Sperre angegeben.
• In der ersten Spalte ist die Art der von einer anderen Transaktion angeforderten Sperre angegeben.
• Das „+“ sagt aus, dass die angeforderte Sperre zu der bereits gesetzten kompatibel ist und die Sperre somit gesetzt werden kann. Demzufolge wird die anfordernde Transaktion nicht blockiert
• Das „−“ sagt aus, dass die Sperren nicht kompatibel sind und die anfordernde Transaktion blockiert wird.

Fundamentalsatz des Sperrens

Jede Transaktion, welche Sperren nutzt, muss die folgenden Sperrbedingungen einhalten:

1. Für jedes Objekt, welches von der Transaktion benutzt werden soll, muss vor der Nutzung eine Sperre angefordert werden.
2. Eine Transaktion darf eine von ihr bereits gesetzte Sperre auf demselben Objekt nicht nochmals anfordern.
3. Spätestens am Ende der Transaktion (end-of-transmission, EOT) müssen wieder alle von der Transaktion gesetzten Sperren freigegeben werden.
4. Jede Transaktion muss die durch andere Transaktionen gesetzten Sperren beachten.
5. Jede Transaktion durchläuft die Phasen des Wachstums der Sperren und deren Schrumpfung (siehe unten).

Zwei-Phasen-Sperrprotokoll

Varianten von 2PL

Das 2PL-Verfahren (two-phase locking) geht davon aus, dass jede Transaktion zwei Phasen durchläuft:

1. Die Wachstumsphase, in welcher Sperren nur gesetzt, aber nicht freigegeben werden dürfen.
2. Die Schrumpfungsphase, in welcher Sperren nur freigegeben, aber nicht angefordert werden dürfen.

Dabei wird zwischen zwei Sperren unterschieden:

1. Read-Lock (auch shared): mehrere Prozesse können lesend auf das gesperrte Objekt zugreifen.
2. Write-Lock (auch exclusive): nur der sperrende Prozess kann auf das Objekt zugreifen und dieses auch schreiben.

Es gibt zwei Spezialfälle von 2PL:

1. Das konservative 2-Phasen-Sperrprotokoll (Preclaiming), bei welchem zu Beginn der Transaktion alle benötigten Sperren auf einmal gesetzt werden. Dies verhindert in jedem Fall Deadlocks, führt aber auch zu einem hohen Verlust an Parallelität, da eine Transaktion ihre erste Operation erst dann ausführen kann, wenn sie alle Sperren erhalten hat. Weiterhin muss im Voraus bekannt sein, welche Sperren von der Transaktion benötigt werden, was zumindest bei einer bedingten if-then-else-Anweisung nicht trivial zu lösen ist. Aus diesem Grund wird diese Variante in der Praxis kaum eingesetzt. Es kann bei dieser Variante bereits vor Ende der Transaktion mit der Freigabe gesperrter Objekte begonnen werden.
2. Das strikte 2-Phasen-Sperrprotokoll, bei welchem alle gesetzten Write-Locks erst am Ende der Transaktion (nach der letzten Operation) freigegeben werden. Dieses Vorgehen verhindert den Schneeballeffekt, also das kaskadierende Zurücksetzen von sich gegenseitig beeinflussenden Transaktionen. Der Nachteil ist, dass Sperren häufig viel länger gehalten werden als nötig und sich somit die Wartezeit von blockierten Transaktionen verlängert. Die Read-Locks werden entsprechend dem Standard-2PL-Verfahren freigegeben.

Falls beide Verfahren in Kombination eingesetzt werden, führt dies automatisch dazu, dass alle Transaktionen, die auf das gleiche Objekt zugreifen, sequentiell nacheinander ausgeführt werden (sofern nicht beide Transaktionen das Datenelement nur lesen). Dies widerspricht der Idee des Transaktionskonzeptes.

Weitere Sperren

Grundsätzlich existieren zwei Arten von klassischen Sperren: X (von englisch eXclusive = ausschließlich) als Sperre bei Modifikationen, meist Schreiben, und die S-Sperre (von englisch share = teilen, gemeinsam benutzen), bei der das Objekt unverändert bleibt und die den gleichzeitigen Zugriff zulässt. Da dies für das Lesen zutrifft, wird die S-Sperre häufig auch als R-Sperre (von englisch read = lesen) bezeichnet. Eine Transaktion, die eine Schreibsperre anfordert, muss so lange warten, bis alle Sperren anderer Transaktionen freigegeben wurden.

Während die Schreibsperre gesetzt ist, kann keine andere Transaktion eine weitere Lese- oder Schreibsperre für das Objekt erhalten. Das heißt, eine schreibende Transaktion blockiert sämtliche andere Transaktionen, die dasselbe Objekt benötigen.

SX-Kompatibilitätsmatrix

	S	X
S	+	−
X	−	−

SAX-Kompatibilitätsmatrix

Erweiterung für Lesen mit Absicht zu schreiben (A). Diese Sperrenform bietet viel Durchsatz, wobei die Schreiber verhungern können, wenn immer neue Leser kommen.

	S	A	X
S	+	+	−
A	+	−	−
X	−	−	−

SUX-Kompatibilitätsmatrix

Erweiterung für Lesen mit exklusiver Änderungsabsicht (U). Bei Schreibabsicht wird U in X geändert, nachdem S-Sperren aufgehoben sind. Wird doch nicht geändert, wird die U-Sperre in eine S-Sperre geändert. Es kann nur eine Transaktion eine U-Sperre halten. Schreiber können nicht mehr verhungern. Weniger Durchsatz als bei SAX.

	S	U	X
S	+	−	−
U	+	−	−
X	−	−	−

SAC-Kompatibilitätsmatrix

Erweiterung der Parallelität, indem Lesevorgänge besser unterstützt werden. Eine A-Sperre, wenn das Objekt geändert werden soll. Mit Hilfe der C-Sperre werden die beiden Versionen der Kopie konsistent gemacht. Bei gesetzter C-Sperre gibt es zwei Objektversionen, eine vor der beendeten Transaktion mit A-Sperre und eine nach der Transaktion. Je nach Start des Lesevorgangs wird die passende Version ausgewählt.

	S	A	C
S	+	+	+
A	+	−	−
C	+	−	−

Hierarchische Sperrgranulate

Die bisherigen Sperren betrachteten nur solche derselben Granularität, die zu sperrenden Objekte standen hierarchisch auf der gleichen Höhe. Dies kann auf folgende hierarchische Sperrgranulate (engl. Multiple granularity locking genannt) verfeinert werden (in absteigender Hierarchie, je weiter unten desto feiner):

1. Datenbasis
2. Segmente
3. Seiten
4. Datensätze

IX-Kompatibilitätsmatrix

Bei diesem Verfahren werden verschiedene Granulate unterschieden. Grobe Granulate definieren ganze Relationen als gesperrtes Objekt, während feine Granulate nur einzelne Sätze einer Relation betreffen. Intention Share (IS) setzt eine Sperre auf einer gröberen Granularitätsstufe. Intention eXclusive (IX) ist die passende Sperre auf gröberer Granularitätsstufe für das Schreiben auf feinerer Granularitätsstufe.

	IS	IX	S	X
IS	+	+	+	−
IX	+	+	−	−
S	+	−	+	−
X	−	−	−	−

SIX-Kompatibilitätsmatrix

Dieses Verfahren ist eine weitere Verfeinerung der IX-Sperre. SIX setzt sich zusammen aus S (Shared) + IX (Intention eXclusive). SIX kann verwendet werden für den Fall, dass alle Sätze eines Satztyps gelesen, aber nur einige geändert werden sollen. In diesem Fall wäre eine X-Sperre auf den Satztyp zu restriktiv und eine IX-Sperre würde das Sperren jedes Satzes verlangen. SIX sperrt das Objekt im S-Modus und verlangt X-Sperren auf tieferen Hierarchieebenen nur für zu ändernde Objekte.

	IS	IX	S	SIX	U	X
IS	+	+	+	+	−	−
IX	+	+	−	−	−	−
S	+	−	+	−	−	−
SIX	+	−	−	−	−	−
U	−	−	+	−	−	−
X	−	−	−	−	−	−

Sperrung von Knoten

Soll ein Datenobjekt mit einer Sperre versehen werden, so müssen die übergeordneten Knoten überprüft werden, die Sperrung beginnend ab dem obersten Knoten (der Datenbasis, top-down), die Freigabe von unten (bottom-up):

1. Sperrung eines Knotens mit S oder IS: Sperrung alle über ihm in IS oder halten in IX
2. Sperrung eines Knotens mit X oder IX: Sperrung aller über ihm in IX
3. Freigabe von unten nach oben

Multiversion Concurrency Control (MVCC)

→ Hauptartikel: Multiversion Concurrency Control

Siehe auch

• Lock
• Sperreskalation
• Optimistisches Locking

Literatur

• R. Elmasri et al.: Grundlagen von Datenbanksystemen. 3. Auflage. Pearson Studium, 2002, ISBN 3-8273-7021-3, S. 714 ff.
• Alfons Kemper, André Eickler: Datenbanksysteme – Eine Einführung. 11 Auflage. Oldenbourg, München 2011, ISBN 978-3-486-59834-6, S. 329 ff.
• J. Gray, R. Lorie, G.F. Putzolu, I.L. Traiger: Granularity of Locks and Degrees of Consistency in a Shared Database. In: G.M. Nijssen (Hrsg.): Modeling in Data Base Management Systems. North Holland Pub., 1976, S. 364–394.
• Skript zur Vorlesung Datenbanksysteme II (PDF; 435 kB) LMU München
• inst.eecs.berkeley.edu (PDF; 1,3 MB) University of Berkeley

Weblinks

• Skripte zum automatischen Lösen von Schedules mittels 2PL