Concurrency-Probleme

Locking zur Lösung der Probleme

Die Grundidee des Locking ist es, alle Objekte, welche von einer Transaktion benötigt werden, mit einer entsprechenden Marke (diese wird als Lock bzw. Sperre bezeichnet) zu versehen, welche anderen Transaktionen anzeigt, daß dieses Objekt derzeit nicht verfügbar ist.

2 Arten von Locks werden unterschieden:

X‑Lock (exclusive Locks): Wird durch eine Transaktion A ein Datensatz verändert, so wird dieser für alle anderen Transaktionen gesperrt, bis die Transaktion den Datensatz wieder freigibt. Diese Sperre verhindert, daß andere Transaktionen den Datensatz lesen oder verändern.

S‑Lock: (share Locks): Wird durch eine Transaktion ein Datensatz abgefragt, so wird dieser Datensatz für X-Locks gesperrt d.h. daß andere Transaktionen den Datensatz nicht ändern dürfen, Lesezugriffe sind jedoch ohne weiteres erlaubt.

Aus diesen zwei Aussagen ergibt sich folgende Wertetabelle

Bsp.: Angenommen Transaktion A hat einen Datensatz R für ein Anderung (X‑Lock) gesperrt, so wird eine Anfrage von Transaktion B für einen Lock auf denselben Datensatz (egal welchen Typs) diese in einen Wartezustand führen.

Bsp.: Hat aber die Transaktion A ein S‑Lock auf den Datensatz R, so muß man bei einer Anfrage eines Locks von Transaktion B auf R zwei Fälle unterscheiden:

a)   bei Anfrage von Transaktion B für ein X‑Lock auf R gelangt diese in einen Wartezustand bis der Datensatz wieder freigegeben wird.

b)   eine Anfrage von Transaktion B für ein S‑Lock auf R wird erlaubt.

Das lost update Problem

Das Problem besteht darin, daß "ältere" Anderungen durch zeitlich verschobene Zugriffe verloren gehen können:

Lösung mittels Locking:

Mit dem Einlesen des Satzes R zum Zeitpunkt t1 wird dieser mit einem X‑Lock gesperrt. Dadurch werden alle weiteren Zugriffe (z.B. Leseanforderung zum Zeitpunkt t2) gesperrt. Erst nach Freigabe der Sperren (Zeitpunkt t4) kann der Datensatz weiter verwendet werden.

Verwendet man allerdings an Stelle der X‑Locks in obigem Beispiel S‑Locks so treten neue Probleme auf:

Da Transaktion A beim Lesen seine Anderungsabsicht noch nicht bekanntgibt, wird Transaktion B zum Zeitpunkt t2 der Lesezugriff nicht verwehrt. Die in der Folge angeforderten X‑Locks versetzen beide Transaktionen in den Wartezustand, da das von der gegnerischen Transaktion gesetzte S‑Lock kein X‑Lock zuläßt. Diese Situation bezeichnet man als Deadlock. Die Lösung dieses neuen Problems wird später erklärt.

Das uncommited dependency Problem

Dieses Problem basiert auf der Verwendung von unbestätigten, veränderten Daten und diese müssen Anderungen zurückgenommen werden.

Lösung mittels Locking:

Dadurch, daß die Transaktion A auf die Freigabe des von der Transaktion B gesperrten Datensatzes R wartet, kann sie zu keinem Zeitpunkt (sowohl bei einem Lesen als auch beim Verändern von Datensätzen) mit falschen Daten rechnen.

Das inconsistent analysis Problem

Bei diesem Problem arbeitet ein Programm mit Daten, die aus einer kurzfristig inkonsistenten Datenbank kommen.

Lösungsversuch mittels Locking:

Auch hier tritt wieder das Problem des Deadlocks auf.

Problem Deadlock

An den zwei vorherigen Beispielen kann man ersehen, daß das Locking nicht alle Probleme löst. Durch das gegenseitige Locking, warten zwei Transaktionen auf die gegenseitige Freigabe eines Datensatzes, was sich dadurch bemerkbar macht, daß keine Transaktion weiter arbeitet.

Dieses Problem kann nur dann gelöst werden, wenn eine der beiden Transaktionen zurückgenommen wird. Dadurch kann die andere Transaktion ihre Arbeit beenden, worauf die abgebrochene Transaktion neu gestartet wird.

Techniken zur Vermeidung/Lösung von Deadlocks

Erforderliche Eigenschaften von Transaktionen:

Atomicity: Eine Transaktion ist eine elementarer Prozeß. Er wird entweder vollständig oder gar nicht durchgeführt.

Konsistenzkriterium: Eine korrekte Durchführung einer Transaktion muß die Datenbank wieder in einen konsistenten Zustand versetzt

Dauerhaftigkeit: Wurden von einer Transaktion Anderungen durchgeführt und bestätigt, so gehen diese auch durch einen späteren Fehler nicht mehr verloren.

Isolation: Alle Anderungen während einer Transaktion dürfen für andere Transaktionen erst nach der Bestätigung sichtbar werden.

Serialisierbarkeit: Man spricht von serialisierbaren Transaktionen, wenn ein Datenbankzustand, der durch parallel arbeitende Transaktionen erreicht wurde, auch durch die serielle Abarbeitung der gleichen Transaktionen erreicht würde.

Es wird vorausgesetzt, daß die einzelnen Transaktionen voneinander unabhängig sind. Eine Abhängigkeit wäre gegeben, wenn z.B. eine Transaktion A vor einer Transaktion B unbedingt laufen müßte. Damit ist zwar keine beliebige Hintereinanderausführung mehr möglich, aber es ist ein bestimmter, zeitlicher Ablauf gegeben.

Punkt 1 und 2 sind in der Definition der Transaktion enthalten. Punkt 3 wird durch Recovery‑Techniken im Falle eines Fehlers gewährleistet.

Zur Einhalten der im Punkt 4 und 5 geforderten Serialisierbarkeit wird das Two-Phase-Locking Protokoll eingesetzt

Two Phase Locking

Wenn eine Transaktion einen gesperrten Datensatz wieder frei gibt, aber ihn danach noch einmal benötigt und ihn somit wieder sperren muß, muß erwartet werden das die Daten schon von einer anderen Transaktion geändert wurden. Um die daraus resultierenden Probleme (uncommitted dependency) zu vermeiden, werden folgende Forderungen aufgestellt:

Vor jeder Bearbeitung eines Datensatzes wird dieser gesperrt

Dieser Datensatz wird erst wieder freigegeben, wenn er für die restliche Transaktion nicht mehr benötigt wird.

Eine Transaktion, die beiden Regeln entspricht, arbeitet nach dem 'two Phase Locking Protocol (2PL)', und erfüllt die Forderung der Serialisierbarkeit.

Zeitmarkenverfahren (Timestamp technique)

Jede Transaktion erhält bei ihrem Start einen Zeitstempel. Die Abarbeitung erfolgt streng noch dem Prinzip First in - First out (FIFO), d.h. streng nach der Startreihenfolge. Tritt ein Konflikt auf, so wird jene Transaktion neu gestartet die den Konflikt auslöste. Ein Konflikt entsteht z.B. wenn eine "ältere" Transaktion eine Leseanforderung für einen bestimmten Datensatz absetzt, der durch eine "jüngere" verändert werden soll. Dadurch erhält der Benutzer immer die aktuellen und geänderten Daten. Dieses Verfahren dient unter anderem zur Vermeidung von Deadlocks.

Transaktion Retry

Nach Erkennung eines Deadlocks muß eine der Transaktionen abgebrochen und zu einem späteren Zeitpunkt neu gestartet werden. Für die Entscheidung welche der Transaktionen abzubrechen ist gibt es verschiedene Verfahren:

Wait‑Die Protokoll

Wound‑Wait Protokoll

Bei beiden Verfahren wird jeweils die 'jüngere' Transaktion zurückgenommen und zu einem späteren Zeitpunkt ausgeführt. Dazu ist erforderlich, daß jede Transaktion einen eindeutigen Zeitstempel, am Beginn erhält.

Wenn die Transaktion A einen von der Transaktion B bereits gesperrten Datensatz sperren will, passiert folgendes:

Wait‑Die: falls A älter ist als B wartet A, sonst wird A zurückgenommen

Wound‑Wait: falls A jünger ist als B wartet A, sonst wird B zurückgenommen

Es ergibt sich folgende Wertetabelle:

B hat Satz gesperrt, A fordert Satz an

-: arbeitet

Bei diesem System ist sichergestellt, daß kein Deadlock entstehen kann, da jede Transaktion in einer endlichen Zeit und nach endlich vielen Wiederholungen ausgeführt wird. Das Schlimmste was passieren kann, ist daß der Rechner zu langsam ist und jede neu ankommende Transaktion länger abläuft als ihr Vorgänger.

Zwei-Phasen-Commit (Two Phase Commit)

Das 2‑Phasen‑Commit wird eingesetzt, wenn mehrere Systeme (z.B.: hierarchisches und relationales DB‑System) gemeinsam synchronisiert werden müssen. Hier tritt das Problem auf, daß zwischen dem Commit für System1 und dem Commit für System2 ein Fehler auftritt. Beim automatischen Recovery würde in diesem Fall System2 zurückgesetzt werden, die Daten für System1 bleiben bestätigt. Dadurch stimmen die beiden Systeme nicht mehr überein.

System befindet sich in einem konsistenten Zustand

Eine Applikation beginnt mit Anderungsanforderungen. Diese Anderungen werden an den Koordinator geschickt. Dieser leitet sie zeitverzögert an die jeweilige Datenbank.

Applikation hat Anderungen abgeschlossen und setzt einen Synchpoint.

Darauf leitet der Koordinator Phase 1 von Commit ein. Dazu schickt er eine entsprechende Anforderung an alle Datenbanksysteme.

Die einzelnen Datenbanksysteme markieren die Commit‑Anforderung in ihrem Logfile und bestätigen anschließend dem Koordinator das Commit.

Nach Eintreffen aller Commit‑Bestätigungen protokolliert der Koordinator dies in seinem Logfile und leitet anschließend Commit Phase 2 ein.

Auch Phase 2 muß von den einzelnen Datenbanksystemen bestätigt werden.

Nach Erhalt aller Bestätigungen und einem entsprechenden Protokolleintrag meldet der Koordinator einen neuen konsistenten Zustand der Datenbank.

Treten bis zum Zeitpunkt des ersten Logeintrags des Koordinators Fehler auf oder meldet ein Datenbanksystem einen nicht erfolgreichen Abschluß, so fordert der Koordinator alle Datenbanksysteme zu einem Rollback auf. Tritt hingegen nach diesem Zeitpunkt ein Fehler auf, so werden automatisch alle noch ausständigen Phase 2 Commits durchgeführt.

Fragen

Wie lauten die zwei Locks, und welche gleichzeitigen Transaktionen sind erlaubt?

X‑Lock (exclusive Locks): Wird durch eine Transaktion A ein Datensatz verändert, so wird dieser für alle anderen Transaktionen gesperrt, bis die Transaktion den Datensatz wieder freigibt. Diese Sperre verhindert, daß andere Transaktionen den Datensatz lesen oder verändern.

S‑Lock: (share Locks): Wird durch eine Transaktion ein Datensatz abgefragt, so wird dieser Datensatz für X-Locks gesperrt d.h. daß andere Transaktionen den Datensatz nicht ändern dürfen, Lesezugriffe sind jedoch ohne weiteres erlaubt.

Was ist ein Deadlock, und wie kann er gelöst werden?

Durch das gegenseitige Locking, warten zwei Transaktionen auf die gegenseitige Freigabe eines Datensatzes, was sich dadurch bemerkbar macht, daß keine Transaktion weiter arbeitet.

Dieses Problem kann nur dann gelöst werden, wenn eine der beiden Transaktionen zurückgenommen wird. Dadurch kann die andere Transaktion ihre Arbeit beenden, worauf die abgebrochene Transaktion neu gestartet wird.

Concurrency-Probleme

Locking zur Lösung der Probleme

Zwei Arten von Locks:

X-Lock (Exclusive Lock)

S-Lock (Share Lock)

Wertetabelle:

Das lost update Problem

Problem:

Lösung mittels Locking:

Zweiter Lösungsweg:

Das uncommited dependency Problem

Problem:

Lösung mittels Locking:

Das incosistent analysis Problem

Problem:

Lösungsversuch mittels Locking:

Deadlock

Techniken zur Vermeidung/Lösung von Deadlocks

Erforderliche Eigenschaften von Transaktionen:

Atomicity

Konsistenzkriterium

Dauerhaftigkeit

Isolation

Serialisierbarkeit

Two Phase Locking

Zeitmarkenverfahren

Transaktion Retry

Zwei Protokolle:

Wait-Die Protokoll

Wound-Wait Protokoll

Es ergibt sich folgende Wertetabelle:

B hat Satz gesperrt, A fordert Satz an

-: arbeitet

Zwei-Phasen-Commit

Anwendung wenn mehrere verschiedene Datenbanksysteme synchronisiert werden müssen.