Sperrverfahren
aus Wikipedia, der freien Enzyklopädie
Sperrverfahren (Datenbanken) 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, 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.
Inhaltsverzeichnis |
[Bearbeiten] Einführung
Um eine Transaktion formal darstellen zu können, wird zur Vereinfachung 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 das mehrere Transaktionen gegenseitig auf die Freigabe von Sperren warten, d.h. sie sich gegenseitig blockieren, spricht man von Verklemmung.
In welchen Situationen eine Blockade erfolgt, hängt von dem jeweils eingesetzten Sperrverfahren ab und kann aus der dazu gehörenden Kompatibilitätsmatrix (s.u.) abgelesen werden.
[Bearbeiten] formale Schreibweisen
Transaktion Ti liest Objekt a: ri(a)
Transaktion Ti schreibt Objekt a: wi(a)
Transaktion Ti fordert eine Lesesperre auf dem Objekt a an: Ri(a)
Transaktion Ti fordert eine Schreibsperre auf dem Objekt a an: Xi(a)
[Bearbeiten] 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 | - | - |
Lesart:
- in der obersten Zeile ist die Art der bereits gesetzten Sperre angegeben
- in der ersten Spalte ist die Art der von einen 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.
[Bearbeiten] Fundamentalsatz des Sperrens
Jede Transaktion, welche Sperren nutzt, muss die folgenden Sperrbedingungen einhalten:
- Für jedes Objekt welches von der Transaktion benutzt werden soll, muss vor der Nutzung eine Sperre angefordert werden.
- Eine Transaktion darf auf demselben Objekt, eine von ihr bereits gesetzte Sperre nicht nochmals anfordern.
- Spätestens am Ende der Transaktion müssen wieder alle von der Transaktion gesetzten Sperren freigegeben werden.
- Jede Transaktion muss die durch andere Transaktionen gesetzten Sperren beachten.
- Eine Transaktion durchläuft während ihrer Ausführung immer zwei Phasen. Zuerst die Wachstumsphase, in welcher neue Sperren angefordert werden können, aber keine Sperren freigeben werden dürfen. Danach die Schrumpfungsphase, in welcher zwar bestehende Sperren freigegeben werden können, aber es verboten ist, neue Sperren anzufordern.
[Bearbeiten] Zwei Phasen Sperrprotokoll
Das 2PL Verfahren (2 Phases Locking) geht davon aus, dass jede Transaktion zwei Phasen durchläuft:
- Die Wachstumsphase, in welcher Sperren nur gesetzt, aber nicht freigegeben werden dürfen.
- Die Schrumpfungsphase, in welcher Sperren nur freigegeben, aber nicht angefordert werden dürfen.
Es gibt zwei Spezialfälle von 2PL:
- 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 Verklemmungen, 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 einem bedingten (if ... then) Ablauf nicht trivial zu lösen ist. Aus diesem Grund wird diese Variante in der Praxis kaum eingesetzt.
- Das strikte 2 Phasen Sperrprotokoll, bei welchem alle gesetzten Sperren 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.
Falls beide Verfahren in Kombination eingesetzt werden, führt dies automatisch dazu, dass alle Transaktionen, welche auf das gleiche Objekt zugreifen, sequentiell nacheinander ausgeführt werden. Dies widerspricht der Idee des Transaktionskonzeptes.
Im Folgenden werden 3 Sperrprotokolle vorgestellt welche auf dem 2PL Verfahren basieren und somit dem Fundamentalsatz des Sperrens gehorchen.
[Bearbeiten] RX - Sperrverfahren
Das RX Protokoll kennt nur die beiden klassischen Sperren R (Lesesperre) und X (Schreibsperre). Mehrere Transaktionen können gleichzeitig auf einem Objekt lesen. Eine Transaktion, die eine Schreibsperre anfordert, um das Objekt zu ändern, muss jedoch so lange warten bis alle Lesesperren 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 anderen Transaktionen, die das selbe Objekt benötigen.
[Bearbeiten] RX Kompatibilitätsmatrix
| R | X | |
| R | + | - |
| X | - | - |
[Bearbeiten] RAC - Sperrverfahen
[Bearbeiten] RAX - Sperrverfahren
[Bearbeiten] Multiversion Concurrency Control
[Bearbeiten] Siehe auch
[Bearbeiten] Literatur
- R. Elmasri et al: Grundlagen von Datenbanksystemen, Pearson Studium, 2002, 3ed, ISBN 3-8273-7021-3, S. 714 ff
