Tdo- - lösungswege zu den concurrency-problemen
1 Concurrency-Probleme 1
1.1 Locking zur Lösung der Probleme 1
1.2 Das lost update Problem 2
1.3 Das uncommited dependency Problem 3
1.4 Das inconsistent analysis Problem 4
1.5 Problem Deadlock 5
1.
6 Techniken zur Vermeidung/Lösung von Deadlocks 5
1.6.1 Two Phase Locking 6
1.6.2 Zeitmarkenverfahren (Timestamp technique) 6
1.6.
3 Transaktion Retry 6
2 Zwei-Phasen-Commit (Two Phase Commit) 7
3 Fragen 8
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
gefordertes Lock
gesetztes Lock von Transaktion A
von Transaktion B
X
S
kein
X
wait B
wait B
OK
S
wait B
OK
OK
Bsp.: Angenommen Transaktion A hat einen Datensatz R für ein Änderung (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:
bei Anfrage von Transaktion B für ein X-Lock auf R gelangt diese in einen Wartezustand bis der Datensatz wieder freigegeben wird.
eine Anfrage von Transaktion B für ein S-Lock auf R wird erlaubt.
Das lost update Problem
Das Problem besteht darin, daß „ältere“ Änderungen durch zeitlich verschobene Zugriffe verloren gehen können:
Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
t1
-
|
-
t2
lese Satz R
|
ändere Satz R
t3
-
|
-
t4
ändere Satz R
-
¯
-
Lösung mittels Locking:
Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R zum Ändern
(meldet X-Lock auf Satz R an)
t1
|
-
|
-
t2
|
lese Satz R zum Ändern
(möchte X-Lock auf Satz R)
|
ändere Satz R
t3
wartet auf Freigabe von Satz R durch A
|
Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)
t4
|
wartet auf Freigabe von Satz R durch A
|
-
t5
|
lese Satz R zum Ändern
(meldet X-Lock auf Satz R an)
-
¯
-
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:
Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
(meldet S-Lock auf Satz R an)
t1
|
-
|
-
t2
|
lese Satz R
(meldet S-Lock auf Satz R an)
|
ändere Satz R
(möchte X-Lock auf Satz R)
t3
|
-
|
wartet auf Freigabe von Satz R durch B
t4
|
ändere Satz R
(möchte X-Lock auf Satz R)
|
wartet auf Freigabe von Satz R durch B
t5
wartet auf Freigabe von Satz R durch A
|
wartet auf Freigabe von Satz R durch B
¯
wartet auf Freigabe von Satz R durch A
Da Transaktion A beim Lesen seine Änderungsabsicht 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 Änderungen zurückgenommen werden.
Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
ändere Satz R
|
lese Satz R
t2
-
|
-
t3
Rollback
-
¯
-
Lösung mittels Locking:
Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
|
ändere Satz R
(meldet X-Lock auf Satz an)
|
lese Satz R
(möchte S-Lock auf Satz R)
t2
|
-
|
wartet auf Freigabe von Satz R durch B
t3
|
Rollback; Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)
|
lese Satz R
(meldet S-Lock auf Satz R an)
t4
|
-
-
¯
-
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.
Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1
Kontostand = 40
t1
|
-
|
-
t2
|
ändere Konto2
Kontostand = 50 + 30 = 80
|
-
t3
|
ändere Konto1
Kontostand = 40 - 30 = 10
|
lies Konto2
Kontostand = 80
t4
|
-
-
¯
-
Lösungsversuch mittels Locking:
Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1
(meldet S-Lock auf Konto1 an)
t1
|
-
|
-
t2
|
ändere Konto2
(meldet X-Lock auf Konto2 an)
|
-
t3
|
ändere Konto1
(meldet X-Lock auf Konto1 an)
|
lies Konto2
(möchte S-Lock auf Konto2)
t4
|
wartet auf Freigabe von Konto1 durch A
|
wartet auf Freigabe von Konto2 durch B
t5
wartet auf Freigabe von Konto1 durch A
-
¯
-
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 Änderungen durchgeführt und bestätigt, so gehen diese auch durch einen späteren Fehler nicht mehr verloren.
Isolation: Alle Änderungen 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
Wait-Die
Wound-Wait
A
B
A
B
A älter als B
wartet
-
-
zurückgenommen
B älter als A
zurückgenommen
-
wartet
-
-: 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 Änderungsanforderungen.
Diese Änderungen werden an den Koordinator geschickt. Dieser leitet sie zeitverzögert an die jeweilige Datenbank.
Applikation hat Änderungen 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:
gefordertes Lock
gesetztes Lock von Transaktion A
von Transaktion B
X
S
kein
X
wait B
wait B
OK
S
wait B
OK
OK
Das lost update Problem
Problem:
Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
t1
-
|
-
t2
lese Satz R
|
ändere Satz R
t3
-
|
-
t4
ändere Satz R
-
¯
-
Lösung mittels Locking:
Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R zum Ändern
(meldet X-Lock auf Satz R an)
t1
|
-
|
-
t2
|
lese Satz R zum Ändern
(möchte X-Lock auf Satz R)
|
ändere Satz R
t3
wartet auf Freigabe von Satz R durch A
|
Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)
t4
|
wartet auf Freigabe von Satz R durch A
|
-
t5
|
lese Satz R zum Ändern
(meldet X-Lock auf Satz R an)
-
¯
-
Zweiter Lösungsweg:
Transaktion A
Zeit
Transaktion B
-
|
-
lese Satz R
(meldet S-Lock auf Satz R an)
t1
|
-
|
-
t2
|
lese Satz R
(meldet S-Lock auf Satz R an)
|
ändere Satz R
(möchte X-Lock auf Satz R)
t3
|
-
|
wartet auf Freigabe von Satz R durch B
t4
|
ändere Satz R
(möchte X-Lock auf Satz R)
|
wartet auf Freigabe von Satz R durch B
t5
wartet auf Freigabe von Satz R durch A
|
wartet auf Freigabe von Satz R durch B
¯
wartet auf Freigabe von Satz R durch A
Þ Deadlock
Das uncommited dependency Problem
Problem:
Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
ändere Satz R
|
lese Satz R
t2
-
|
-
t3
Rollback
-
¯
-
Lösung mittels Locking:
Transaktion A
Zeit
Transaktion B
-
|
-
-
t1
|
ändere Satz R
(meldet X-Lock auf Satz an)
|
lese Satz R
(möchte S-Lock auf Satz R)
t2
|
-
|
wartet auf Freigabe von Satz R durch B
t3
|
Rollback; Synchpoint; Ende Transaktion
(gibt Satz R wieder frei)
|
lese Satz R
(meldet S-Lock auf Satz R an)
t4
|
-
-
¯
-
Das incosistent analysis Problem
Problem:
Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1; Kontostand = 40
t1
-
|
-
t2
ändere Konto2; Kontostand = 50 + 30 = 80
|
-
t3
ändere Konto1; Kontostand = 40 - 30 = 10
|
lies Konto2; Kontostand = 80
t4
-
-
¯
-
Lösungsversuch mittels Locking:
Transaktion A
Zeit
Transaktion B
-
|
-
lies Konto1
(meldet S-Lock auf Konto1 an)
t1
|
-
|
-
t2
|
ändere Konto2
(meldet X-Lock auf Konto2 an)
|
-
t3
|
ändere Konto1
(meldet X-Lock auf Konto1 an)
|
lies Konto2
(möchte S-Lock auf Konto2)
t4
|
wartet auf Freigabe von Konto1 durch A
|
wartet auf Freigabe von Konto2 durch B
t5
wartet auf Freigabe von Konto1 durch A
-
¯
-
Þ Deadlock
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
Wait-Die
Wound-Wait
A
B
A
B
A älter als B
wartet
-
-
zurückgenommen
B älter als A
zurückgenommen
-
wartet
-
-: arbeitet
Zwei-Phasen-Commit
Anwendung wenn mehrere verschiedene Datenbanksysteme synchronisiert werden müssen.
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
