close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kapitel 7: Transaktionsverwaltung Was ist eine - Informatik

EinbettenHerunterladen
Frühjahrsemester 2014
CS243 Datenbanken
Kapitel 7: Transaktionsverwaltung
H. Schuldt
Was ist eine Transaktion?
•
Eine Transaktion ist eine Menge von logisch zusammengehörenden Operationen
(zumeist in ein Programm eingebunden, aber auch interaktiv möglich)
– Im Fall von klassischen Datenbanktransaktionen beziehen sich alle
Operationen (Lesen bzw. Schreiben von Datenobjekten) auf dasselbe
Datenbanksystem
– Verteilte Transaktionen erlauben Operationen in verschiedenen
Datenbanksystemen
•
Transaktionen basieren auf einem generischen Abstraktionskonzept zum Kapseln
der enthaltenen Operationen, um für diese bestimmte Ausführungsgarantien
durchzusetzen
– Ausführungsgarantien abgeleitet von ACID-Eigenschaften
– Diese Garantien werden vom System transparent für den
Anwendungsentwickler/ Benutzer bereitgestellt
– Anwendungsentwickler/Benutzer muss lediglich die Transaktionsgrenzen
festlegen (BOT = Begin-of-Transaction bzw. EOT = End-of-Transaction),
wird aber von allen anderen Aspekten zur Realisierung der Garantien befreit
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-2
1
Transaktionseigenschaften: ACID
.
Atomicity (Atomarität)
– Eine Transaktion wird entweder komplett ausgeführt (“commit”) oder
erscheint so, als wäre sie nie gestartet worden, d.h. sie hinterlässt keine
Effekte (“rollback”). Die Semantik einer Transaktion entspricht also einem
“Alles-oder-Nichts”.
Consistency (Konsistenz)
– Eine Transaktion führt die Datenbank von einem konsistenten Zustand in
einen anderen konsistenten Zustand über
Isolation
– Transaktionen, auch wenn parallel ausgeführt, erscheinen so als ob sie
isoliert voneinander (d.h. sequentiell) ausgeführt werden
Durability (Dauerhaftigkeit/Persistenz)
– Nach dem Commit einer Transaktion sind ihre Effekte dauerhaft, d.h.
überleben auch Systemabstürze
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-3
Durchsetzen von Transaktionseigenschaften
•
Transaktionen sind eine Art Vertrag zwischen einem Anwendungsprogramm und dem Laufzeitsystem der Datenbank
– Die ACID-Eigenschaften können dabei als Vertragsinhalt angesehen werden,
durch welche die Aufgaben der Laufzeitumgebung festgeschrieben sind
•
Die wichtigsten Aufgaben einer Infrastruktur zur Transaktionsverwaltung
bestehen aus der
– korrekten Synchronisation paralleler, konkurrierender Transaktionen
(Concurrency Control Æ Isolation) sowie der
– korrekten Behandlung von System- und Anwendungsfehlern
(Recovery Ø Atomarität, Persistenz).
– Diese Unterscheidung spiegelt sich auch in den Komponenten der
Infrastruktur zur Transaktionsverwaltung wieder
•
Für beide Bereiche (Concurrency Control und Recovery) bedarf es zunächst einer
eingehenden Untersuchung, was jeweils “korrekt” bedeutet
T Korrektheitskriterien
• Concurrency Control: Serialisierbarkeitstheorie
• Recovery: Fehlererholung / Crash-Recovery
Auf der Basis dieser Korrektheitskriterien müssen dann Systeme entwickelt
werden, welche die verlangten Garantien durchsetzen
T Concurrency Control- bzw. Recovery-Protokolle
•
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-4
2
Transaktionsverwaltung – Beispiel …
•
Szenario: Banküberweisung
– Klassischer Vertreter von Datenbanktransaktionen
– Kurzlebige Transaktionen, operieren auf wenigen Datenobjekten
– Parallele Zugriffe auf Konto-Relationen (bzw. Objekte)
Konto (KontoNr, KundenNr, FilialNr, Kontostand)
– Typische Operationen (z.B. reslisiert durch Embedded SQL-Programme)
Debit (KontoNr, Betrag) bucht Betrag von Konto KontoNr ab
Credit (KontoNr, Betrag) bucht Betrag auf Konto KontoNr
sowie Transfer (KontoNrA, KontoNrB, Betrag), das aus einem
Debit(KontoNrA, Betrag) und einem Credit(KontoNrB, Betrag)
besteht.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-5
… Transaktionsverwaltung – Beispiel …
„Ich möchte 50.SFr von meinem
Konto abheben“
.
„Ich möchte meiner
Enkelin 200.- SFr
überweisen“
Client
Client
Debit (4711, 50.- SFr)
Transfer (0815, 4711,
200.- SFr)
=
Debit (0815, 200.- SFr)
Credit (4711, 200.- SFr)
DBMS
DB
Bank
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-6
3
… Transaktionsverwaltung – Beispiel: Atomarität …
„Ich möchte 50.SFr von meinem
Konto abheben“
KontoNr
„Ich möchte
meiner Enkelin
200.- SFr
überweisen“
Kontostand
0815
2770.-
4711
120.-
SELECT kontostand INTO :balanceTransA
FROM Konto WHERE kontoNr = 0815;
2570.-
balanceTransA := balanceTransA - 200;
...
Update Konto
SET kontostand = :balanceTransA
Where kontoNr = 0815;
SELECT kontostand INTO :balanceTransB
FROM Konto WHERE kontoNr = 4711;
KontoNr
t
FS 2014
Kontostand
0815
2570.-
4711
120.-
*** Programmabbruch ***
Datenbanken (CS243) – Transaktionsverwaltung
7-7
… Transaktionsverwaltung – Beispiel: Atomarität …
•
Im vorigen Ablauf ist die Alles-oder-Nichts-Semantik der Atomarität verletzt
– Ein inkonsistenter Zwischenzustand bleibt erhalten
(bei der fehlgeschlagenen Überweisung ging Geld verloren!)
– Abhilfe: für die durch den Systemabsturz abgebrochene
Überweisungstransaktion sollte das bereits erfolgte Debit automatisch
durch das Datenbanksystem rückgängig gemacht werden
T Gefragt sind also geeignete Recovery-Protokolle, die beispielsweise den
Zustand einspielen, der direkt vor Beginn der Überweisungstransaktion
vorlag
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-8
4
… Transaktionsverwaltung – Beispiel: Isolation …
„Ich möchte 50.SFr von meinem
Konto abheben“
„Ich möchte
meiner Enkelin
200.- SFr
überweisen“
KontoNr
Kontostand
0815
2770.-
4711
120.-
...
SELECT Kontostand INTO :balanceATM
FROM Konto WHERE KontoNr = 4711;
320.-
balanceTransB := balanceTransB + 200;
balanceATM := balanceATM – 50;
Update Konto
SET Kontostand = :balanceTransB
WHERE KontoNr = 4711;
70.-
Update Konto
SET Kontostand = :balanceATM
WHERE KontoNr = 4711;
KontoNr
0815
2570.-
t
4711
70.-
FS 2014
SELECT Kontostand INTO :balanceTransB
FROM Konto WHERE KontoNr = 4711;
Kontostand
Datenbanken (CS243) – Transaktionsverwaltung
7-9
… Transaktionsverwaltung – Beispiel: Isolation …
•
Im vorigen Ablauf überschneiden sich die beiden Transaktionen in inkorrekter
Weise
– Die Änderungsoperation der Überweisungstransaktion geht komplett verloren
(und damit auch das überwiesene Geld). Das Phänomen wird auch als
„lost update“ bezeichnet
– Der korrekte Endzustand nach kompletter Ausführung beider Transaktionen
wäre:
KontoNr
Kontostand
0815
2570.-
4711
270.-
T Das System muss daher die beiden Transaktionen durch geeignete
Concurrency Control-Protokolle voneinander isolieren, indem z.B. die
Überweisungstransaktion den Kontostand von 4711 erst lesen und
verändern kann, nachdem die ATM-Transaktion beendet ist.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-10
5
… Transaktionsverwaltung – Beispiel: Isolation …
•
Problemtyp „Inkonsistentes Lesen“
KontoNr
Kontostand
0815
2770.-
4711
120.-
Transfer von 4711 nach 0815
...
/* 0815.Kontostand = 2770.00 SFr. */
Update Konto
SET Kontostand = Kontostand - 200
WHERE KontoNr = 0815;
/* 0815.Kontostand = 2570.00 SFr. */
/* 4711.Kontostand = 120.00 SFr. */
UPDATE Konto
SET Kontostand = Kontostand + 200
WHERE Kontonr = 4711
/* 4711.Kontostand = 320.00 SFr. */
FS 2014
Prüfen der Summe von 4711 und 0815
...
t
KontoNr
SELECT Kontostand INTO :A FROM Konto
WHERE KontoNr = 4711;
/* A = 2570.00 SFr. */
SELECT Kontostand INTO :B FROM Konto
WHERE KontoNr = 0815;
/* B = 120.00 SFr. ; A+B = 2690.- SFR */
Kontostand
0815
2570.-
4711
320.-
Datenbanken (CS243) – Transaktionsverwaltung
7-11
… Transaktionsverwaltung – Beispiel: Isolation …
Problemtyp "Phantomproblem" (Spezialfall des inkonsistenten Lesens)
Schema:
Abteilungen (AbtNr, AbtName, Budget, ...)
Angestellte (AngNr, Name, Adresse, Gehalt, ..., AbtNr)
Integritätsbedingung:
Abteilungen.Budget = 200000 * (SELECT COUNT(*) FROM
Angestellte WHERE Angestellte.AbtNr =
Abteilungen.AbtNr )
Finanzprüfung
Einstellung eines Mitarbeiters
...
SELECT COUNT(*) FROM Angestellte
WHERE AbtNr = 1
/* Resultat: 10 Angestellte */
...
SELECT Budget FROM Abteilungen
WHERE AbtNr = 1
/* Resultat: 2'200'000 SFr */
FS 2014
INSERT INTO Angestellte
VALUES (111, 'Hans Meier', ..., 1)
UPDATE Abteilungen
SET Budget = Budget + 200'000
WHERE AbtNr = 1
t
Datenbanken (CS243) – Transaktionsverwaltung
7-12
6
… Transaktionsverwaltung – Beispiel
Weitere Anforderungen der Beispielanwendung
• Konsistenz
– z.B. Einschränkung, dass der Kontostand niemals negativ werden kann
– Dies wird, wie bereits bekannt, in der Regel durch Integritätsbedingungen
zugesichert
•
•
CREATE ASSERTION positiverKontostand
CHECK (NOT EXISTS (
SELECT * FROM Konto
WHERE Kontostand < 0 ))
T Auch die Konsistenz wird vom System garantiert und muss nicht vom
Anwendungsentwickler berücksichtigt werden
Dauerhaftigkeit
– Änderungen am Kontostand durch korrekt (mit Commit) beendete
Transaktionen müssen dauerhaft sein, also z.B. auch Systemabstürze
überstehen
Performanz
– Natürlich muss das System mehr als zwei Benutzer parallel unterstützen, ohne
dass dabei die Synchronisation konkurrierender Transaktionen zu
signifikanten Performance-Einbussen führt
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7.1
•
7-13
Read/Write-Modell
Die wesentlichen Aspekte von Concurrency Control und Recovery werden
auf der Basis des Read/Write-Modells (R/W-Modell) betrachtet
Grundlegende Begriffe
•
Datenbank (DB)
Menge von Objekten: DB = {o1, o2, … }
Diese Menge ist statisch, Objekte sind in der Regel
einzelne Datenseiten
•
Operation (OP)
Menge von Operationen: OP = {read, write}
•
Aktion
Aktion a œ (OP  DB), also entweder read(oi) oder write(oi).
– read(oi) liefert das Datenobjekt oi zurück
– write(oi) schreibt Datenobjekt oi
Im Folgenden werden wir die Aktionen in abgekürzter
Schreibweise verwenden:
– r(oi) für read(oi)
– w(oi) für write(oi)
SQL-Operationen müssen also auf Operationen im R/W-Modell abgebildet werden
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-14
7
Transaktion
Transaktion (T) Eine Transaktion T ist ein Tupel mit T = ( ACT , < ) bestehend
aus einer Menge von Aktionen ACT, zwischen denen eine
(partielle) Ordnungsrelation < vorhanden ist
Dabei ist: ACT = { a1, a2, …, ak} » term
a1, …, ak sind Aktionen
term œ {C, A} ist Terminierungsaktion
<  (ACT  ACT) ist Präzedenzrelation
•
•
Jede Transaktion T ist entweder durch C (commit) oder A (abort) abgeschlossen.
C bzw. A ist hinter allen Aktionen der jeweiligen Transaktion geordnet
(bezüglich <), also ai < term für alle 1 § i § k.
Die Präzedenzrelation < legt die Ausführungsreihenfolge der Aktionen einer
Transaktion fest
< partiell: Parallelität innerhalb einer Transaktion
(intra-transaktionale Parallelität) erlaubt
< total:
FS 2014
sequentieller Ablauf (dies ist der Normalfall)
T = ( a1 < a2 < … < ak < C )
Datenbanken (CS243) – Transaktionsverwaltung
7-15
Commit bzw. Abort
•
Transaktionen werden dynamisch durch entsprechende DBS-Aufrufe des
Anwendungsprogramms (bzw. durch Eingabe von SQL-Befehlen über die Konsole)
erzeugt. In SQL gibt es dafür drei Anweisungen:
CONNECT ... (BOT = Begin-of-Transaction):
kennzeichnet den Beginn einer Transaktion.
COMMIT WORK bzw. COMMIT (EOT = End-of-Transaction):
kennzeichnet das ("erfolgreiche") Ende einer Transaktion und
erklärt alle Änderungen der Transaktion für gültig.
ROLLBACK WORK bzw. ROLLBACK (RBT = Rollback-Transaction):
kennzeichnet das ("erfolglose") Ende einer Transaktion (Abort)
und erklärt alle Änderungen der Transaktion für ungültig.
•
Implizit kennzeichnen EOT und RBT ausserdem den Beginn einer neuen
Transaktion, die bis zum nächsten EOT, RBT oder DISCONNECT dauert.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-16
8
Wiederholung: DB-System-Modell
•
Der TM leitet eingehende
Operationen an den Scheduler
weiter. Im Falle von verteilten
DBMSen beinhaltet dies die
Kommunikation sowie die
Koordination verteilter
Transaktionen.
•
Der Scheduler entscheidet, ob
Operationen ausgeführt, zurückgewiesen oder verzögert werden.
•
Aufgabe des RM ist, die DB vor
Systemfehlern zu schützen (z.B.
wenn der transiente Speicher
verloren geht) und zu garantieren,
dass die Effekte abgeschlossener
Transaktionen dauerhaft sind bzw.
dass abgebrochene TA keine
Effekte hinterlassen.
•
Der CM (Pufferverwaltung) sorgt
für einen effizienten Zugriff auf
Daten.
FS 2014
Transaktionen
read / write / commit / abort
DBMS
TransaktionsManager (TM)
read / write / commit / abort
Scheduler
read / write / commit / abort
DataManager
Recovery-Manager (RM)
read /
write
fetch / flush
Cache-Manager (CM)
Cache
transienter Speicher
read /
write
flush
Datenbank
fetch
Log
persistenter Speicher
Datenbanken (CS243) – Transaktionsverwaltung
7-17
7.2 Serialisierbarkeitstheorie
Die Serialisierbarkeitstheorie befasst sich mit den Korrektheitskriterien für die
korrekte parallele Ausführung von Transaktionen
Gegeben:
 = { T1, T2, … , Tn} Menge von Transaktionen, die
korrekt parallel ausgeführt werden sollen.
Grundannahme G1:
Jede Transaktion Ti für sich genommen (einzeln, in
Isolation ausgeführt) ist korrekt.
Grundannahme G2:
Jede serielle (sequentielle) Ausführung aller n Transaktionen
(in irgend einer Reihenfolge) ist korrekt. Es wird angenommen,
dass alle Transaktionen von verschiedenen, unabhängigen
Benutzern stammen und dass für diese Benutzer jede beliebige
sequentielle Ausführung der Transaktionen akzeptabel ist.
Wir benötigen also Kriterien die überprüfen, ob eine gegebene parallele
Ausführung mehrerer Transaktionen mit einer solchen seriellen Ausführung
übereinstimmt!
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-18
9
Schedule …
Die parallele Ausführung der Transaktionen in  wird durch einen Schedule
reflektiert:
Vollständiger Schedule S
Dabei ist:
Ein vollständiger Schedule S ist ein Tripel
S = (, ¿, <). S enthält die Ausführungsfolge
aller Aktionen sämtlicher Transaktionen aus 
unter Wahrung der Präzedenzrelationen.
 = { T1, T2, … , Tn } Menge von Transaktionen
¿ = » ACTi
Vereinigung der Aktionen aller
Transaktionen in  (*)
<  (¿  ¿)
partielle Ordnung, wobei gilt:
<i  < für alle Ti  , d.h. die
Ausführungsfolge der Aktionen in S
beachtet die vorgeschriebene Folge
innerhalb jeder Transaktion.
(*) Ein vollständiger Schedule enthält genau ein C oder ein A für jede Transaktion.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-19
… Schedule …
T2
…
a31
a21
a11
a2
a12
2
Tn
…
…
T1
…
Schedule:

a2
a1n
n
Scheduler
t
…
t
a11
a2n
a1n
a12
FS 2014
Schedule S
Ein Schedule ist ein Präfix
eines vollständigen Schedules
Ein Schedule S enthält
– abgeschlossene
(C in S)
– abgebrochene
(A in S)
– aktive
(weder C noch A in S)
Transaktionen.
In einem vollständigen Schedule
existieren keine aktiven Transaktionen.
Für die Ordnung < eines Schedules gilt:
< total:
sequentielle Bearbeitung
< nicht total:
parallele Bearbeitung,
z.B. in verteilten
Datenbanken
Datenbanken (CS243) – Transaktionsverwaltung
7-20
10
… Schedule
Serieller Schedule:
In einem seriellen Schedule ist < total und für
beliebige i, k œ {1, .., n} gilt:
alle Aktionen von Ti werden vor allen Aktionen
von Tk ausgeführt
Sser = a12 a22 … C2 a1n a2n … Cn a11 a21 … Cn
T2
Tn
T1
Zwei serielle Schedules werden jeweils als korrekt angesehen, liefern i.a.
aber verschiedene Datenbank-(Zwischen- oder/und End-) Zustände.
Committed Projection:
Die committed projection C(S) eines Schedules S
erhält man, wenn man aus S alle Aktionen von
Transaktionen streicht, die nicht mit commit
beendet sind, d.h.  einschränkt auf: « Ti: Ci in S
C(S) enthält also weder aktive noch abgebrochene Transaktionen.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-21
Semantik von Aktionen
Die Semantik der Aktionen einer Transaktion in einem Schedule ist wie folgt:
Leser:
ri(x) liest x von wk(x), wobei wk(x) die letzte
Schreibaktion in S vor ri(x) ist.
Dabei ist i  k und Tk ist nicht abgebrochen.
Schreiber:
wi(x) schreibt x neu. Dieses Schreiben hängt
von allen Leseaktionen von Ti vor wi(x) ab.
Diese Leser (wie oben) lesen von nicht abgebrochenen
Transaktionen.
Ø Das Ergebnis einer Schreibaktion hängt
(in unbekannter Weise; dies ist Sache des Anwendungsprogramms) von allen vorhergehenden Leseaktionen
innerhalb der betrachteten Transaktion ab.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-22
11
Konflikt-Serialisierbarkeit
Konflikt-Serialisierbarkeit basiert auf der grundlegenden Beobachtung,
dass manche Aktionen eines Schedules vertauscht werden können, ohne dass sich
dabei etwas ändert (sowohl aus der Sicht dieser Aktionen als auch aus der Sicht der
jeweiligen Objekte). Dies ist nicht nur im einfachen read/write-Modell der Fall
sondern kann auch auf beliebige (semantisch reiche) Aktionen verallgemeinert
werden.
Beispiel:
r1(x) < r2(x)
w1(x) < w2(y)
~
~
r2(x) < r1(x)
w2(y) < w1(x)
Umgekehrt gibt es jedoch auch Paare von Aktionen, die nicht vertauscht werden
können (da diese Vertauschung Auswirkungen auf die Aktionen bzw. die
jeweiligen Objekte hat). In solchen Fällen bestehen Abhängigkeiten zwischen
diesen Aktionen (bzw. müssen wir Abhängigkeiten annehmen).
Beispiel:
r1(x) < w2(x)
w1(x) < w2(x)
FS 2014


w2(x) < r1(x)
w2(x) < w1(x)
Datenbanken (CS243) – Transaktionsverwaltung
7-23
Konfliktrelation
Aktionen, die nicht vertauscht werden können, sind in Konflikt.
Die Konfliktrelation con gibt an, wann dies für Paare von Aktionen a und a’ der Fall
ist (solche Paare werden auch Konfliktpaare genannt)
Konfliktrelation con:
con(a, a’) ñ (1)
(2)


a
a
a
a
und a’ werden auf dasselbe DB-Objekt x angewandt
= read(x)  a’ = write(x)
r/w-Konflikt
= write(x)  a’ = read(x)
w/r-Konflikt
= write(x)  a’ = write(x)
w/w-Konflikt
Im Read/Write-Modell sind also zwei Aktionen in Konflikt, wenn sie auf dasselbe
Objekt zugreifen und mindestens eine Aktion ein Schreiben ist.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-24
12
Abhängigkeitsrelation
Die Abhängigkeitsrelation eines Schedules S enthält sämtliche Konfliktpaare aller
Transaktionen aus S.
Abhängigkeit & Abhängigkeitsrelation:
Sei S ein Schedule. Aktion ak ist abhängig von Aktion ai in S, kurz ai Ø ak ñ
(1) i  k
Ti und Tk sind verschiedene Transaktionen,
ai kommt vor ak in S,
(2) ai < ak
i
k
(3) con(a , a )
ai und ak sind in Konflikt,
i
k
(4) C , C in S
beide Transaktionen sind abgeschlossen.
Die Abhängigkeitsrelation dep(S) ist die Menge aller abhängigen Paare in S:
dep(S) = {(ai, ak) œ S | ai Ø ak }
Beispiele:
S1 = · w1(a) r2(a) r1(b) w2(b) C1 C2 Ò
S’1 = · w1(a) r1(b) C1 r2(a) w2(b) C2 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-25
Konflikt-Äquivalenz
Die Abhängigkeitsrelation ist ein Mittel, um die Semantik eines Schedules zu erfassen
(und daher, um zwei Schedules zu vergleichen).
Konflikt-Äquivalenz:
Zwei Schedules S und S’ sind konflikt-äquivalent, wenn beide Schedules
– dieselben Aktionen beinhalten und wenn die
– Abhängigkeitsrelation identisch ist, also dep(S) = dep(S’) ist.
Wenn zwischen zwei Transaktionen Ti und Tk ein Informationsfluss besteht, so
kommt er ausschliesslich über die Konfliktpaare von Ti und Tk zustande. Es gibt keine
weitere Informationsübermittlung über Nachrichten oder über weitere (lokale)
gemeinsame Variable. Daher ist nur die Reihenfolge der Aktionen in den
Konfliktpaaren von Bedeutung.
Beispiel:
S1 = · w1(a) r2(a) r1(b) w2(b) C1 C2 Ò
S’1 = · w1(a) r1(b) C1 r2(a) w2(b) C2 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-26
13
CPSR
Konflikt-Serialisierbarkeit (CPSR):
Ein Schedule S ist konflikt-serialisierbar, wenn seine Committed Projection C(S)
konflikt-äquivalent zu einem seriellen Schedule Sser ist.
Die Klasse der konflikt-serialisierbaren Schedules wird
CPSR (Conflict Preserving Serializable) genannt.
Konflikt-äquivalente Schedules sind also erzeugbar durch das Kommutieren von
Aktionen, die nicht abhängig sind.
Beobachtung: Durch die Betrachtung der Committed Projection wird der Einfluss
abgebrochener Transaktionen nicht berücksichtigt.
Beispiel:
S1 = · w1(a) r2(a) r1(b) w2(b) C1 C2 Ò
S’1 = · w1(a) r1(b) C1 r2(a) w2(b) C2 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-27
Vertauschen von Aktionen
•
Beobachtung: Bei serieller Ausführung werden alle Aktionen einer Transaktion Ti
vor/nach allen Aktionen einer Transaktion Tk ausgeführt.
Beispiel:
S = · a1 1 a2 1 a3 1 a1 2 a1 3 a4 1 Ò
falls kein Konflikt
ª · a1 1 a2 1 a3 1 a1 2 a4 1 a1 3 Ò
falls kein Konflikt
ª · a1 1 a2 1 a3 1 a4 1 a1 2 a1 3 Ò
… seriell !
Wir benötigen daher ein Verfahren zum Nachweis der Existenz eines seriellen
Schedules, der durch Vertauschung von Aktionen, die nicht in Konflikt sind,
entsteht.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-28
14
Serialisierungsgraph
Serialisierungsgraph (Abhängigkeitsgraph)
Der Serialisierungsgraph (Abhängigkeitsgraph) SG(S) eines Schedules S ist ein
Graph dessen
– Knoten alle mit Commit beendeten Transaktionen in S und dessen
– Kanten alle Paare (Ti, Tk) sind für die gilt: es gibt Aktionen ai  Ti und
ak in Tk mit (ai, ak)  dep(S).
Beispiel:
FS 2014
S1 = · r11(a) r12(a) w21(a) r13(a) w22(b) w23(b) C1 C2 C3 Ò
Datenbanken (CS243) – Transaktionsverwaltung
7-29
Serialisierbarkeitstheorem
Ein Schedule S ist genau dann konflikt-serialisierbar (S œ CPSR), wenn sein
Serialisierungsgraph SG(S) zyklenfrei ist.
Man erhält einen zum Schedule äquivalenten seriellen Schedule (eine Serialisierung)
durch topologische Sortierung des Abhängigkeitsgraphen:
– Man wähle eine beliebige Quelle des Graphen
(d.h. einen Knoten ohne eingehende Kanten) und entferne diese
sowie alle davon ausgehenden Kanten.
– Falls der Graph noch Knoten hat, wiederholt man diese Prozedur für
den verbleibenden Graphen.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-30
15
Topologische Sortierung von SG(S)
Vorüberlegung: Wenn SG(S) zyklenfrei ist, dann gibt es mindestens
eine Quelle/Senke
Quelle
sonst
Topologische Sortierung:
Eine topologische Sortierung von SG(S) ist die Folge aller Knoten
‚ i1 i2 … in Ú wobei gilt: ir < is fl es gibt keinen Pfad von is nach ir
in SG(S).
Beispiel:
T2
T1
FS 2014
1
T3
T6
2
T4
T2 Ø T3 Ø
T5
Datenbanken (CS243) – Transaktionsverwaltung
T4 T5 T6 T1
T1 T4 T6 T5
T4 T5 T1 T6
… mit T4 Ø T6
7-31
Beispiele: CPSR
S1 = · r11(a) r12(a) w21(a) r13(a) w22(b) w23(b) C1 C2 C3 Ò
S2 = · r11(a) r12(a) w22(a) r13(a) w21(a) w23(a) C1 C2 C3 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-32
16
Ordnungserhaltende Serialisierbarkeit
•
CPSR ist ein sehr intuitives Korrektheitskriterium. Allerdings gibt es auch hier
noch unerwartete (?) Effekte.
Beispiel:
FS 2014
S = · r1(x) r2(y) w2(y) r1(y) C1 r3(z) C3 r2(z) w2(z) C2 Ò
Datenbanken (CS243) – Transaktionsverwaltung
7-33
OPSR
Ordnungserhaltende Serialisierbarkeit:
Ein Schedule S ist (transaktions-) ordnungserhaltend serialisierbar,
wenn S œ CPSR und wenn es mindestens einen seriellen äquivalenten Schedule S’
gibt, in dem die in S vollständig geordneten Transaktionen auch in S’ die gleiche
Reihenfolge haben.
Die Klasse der ordnungserhaltend serialisierbaren Schedules wird
OPSR (Order Preserving Serializable) genannt.
Satz:
OPSR Õ CPSR
Beweis:
– OPSR Teilmenge von CPSR: Klar, nach obiger Definition
(jeder OPSR-Schedule ist auch CPSR)
– OPSR ist echte Teilmenge von CPSR: Beispiel hierfür (Schedule aus
CPSR, aber nicht aus OPSR): siehe vorige Folie.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-34
17
Commit-Ordnungserhaltung
•
•
OPSR betrachtet nur die Erhaltung der Reihenfolge von Transaktionen, die in
einem Schedule vollständig geordnet sind, aber nicht die Reihenfolge, in der die
Commits erfolgen. Die Commit-Ordnungserhaltung ist ein weiteres
Korrektheitskriterium, das genau diese Ordnung zusätzlich betrachtet.
Grundlegende Idee:
Man will nicht nur sicherstellen, dass parallele Transaktionen garantiert
korrekt ausgeführt werden, sondern möchte auch noch die (interne)
Serialisierungsreihenfolge kennen (bzw. vorgeben). Dies ist über die
Commit-Reihenfolge, die nach aussen hin bekannt ist, möglich.
Commit-ordnungserhaltende Serialisierbarkeit:
Ein Schedule S ist commit-ordnungserhaltend serialisierbar
wenn für jedes Paar mit Commit abgeschlossener Transaktionen
Ti, Tk aus S gilt:
falls (ai, ak) in dep(S), dann ist Ci < Ck.
Die Klasse der commit-ordnungserhaltend serialisierbaren Schedules wird COPSR
(Commit Order Preserving Serializable) genannt. Es gilt: COPSR Õ OPSR
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-35
Vergleich von Korrektheitskriterien
Alle Schedules
CPSR
OPSR
COPSR
Serielle Schedules
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-36
18
7.3 Concurrency Control-Protokolle …
Tn
…
a2
a12
…
a31
a21
a11
T2
…
T1
…
a2
a1n
2
n
Eingabeschedule
Scheduler
(Sch)
t
…
t
a11
a2n
a1n
a12
FS 2014

• Die Aufgabe eines Schedulers ist die
Transformation eines wohlgeformten
Eingabeschedules in einen serialisierbaren
Schedule.
• Ein Scheduler kann also als Abbildung
Sch: ES # AS angesehen werden, wobei ES
die Menge aller Eingabeschedules und AS die
Menge aller serialisierbaren Ausgabeschedules ist, d.h. AS ΠCPSR
• Die Güte eines Schedulers bestimmt sich aus
der “Grösse” der Ausgabeschedule-Menge
AS, d.h. je mehr korrekte Schedules ein
Scheduler zulässt, umso besser ist er.
• Ein weiteres Gütekriterium eines Schedulers
ist dessen Fixpunktmenge: je grösser diese
ist, umso besser ist der Scheduler.
(die Fixpunktmenge eines Schedulers ist die
Serialisierbarer Menge der korrekten Eingabeschedules, die
nicht verändert werden, also
Schedule
Fixpunkt: S’ = Sch(S) = S )
Datenbanken (CS243) – Transaktionsverwaltung
7-37
… Concurrency Control-Protokolle
• Die Spielregeln des Schedulers, d.h. sein Algorithmus, werden als Concurrency
Control Protokoll bezeichnet.
• Für die Praxis relevant sind nur dynamische (“on-line”) Scheduler.
– Das bedeutet, dass Concurrency Control-Protokolle die Entscheidung,
ob Aktion aik der Transaktion Tk ausgeführt werden kann oder verzögert
werden muss, oder ob Tk zurückgesetzt werden muss ausschliesslich mit
dem vor aik liegenden Präfix des Schedules fällen können.
– Je nach Art der Protokolle wird dabei diese Entscheidung zumeist entweder
nur für die Aktionen auf Datenobjekten (im r/W-Modell: r(x) bzw. w(x)),
oder nur für die Terminierungsaktionen (Commit bzw. Abort) durchgeführt.
(einige wenige Protokolle verlangen eine Entscheidung für beide Arten
von Aktionen)
• Ausgeschlossen ist auf jeden Fall die Analyse aller Aktionen der Transaktionen
vor deren Ausführung.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung

7-38
19
Einteilung: konservativ vs. optimistisch
Konservative Protokolle
Ein konservativer Scheduler setzt voraus, dass vor jeder Aktion überprüft wird,
ob diese Aktion ausgeführt werden darf oder nicht. Ein Commit einer Transaktion
hingegen ist in konservativen Protokollen immer erlaubt.
Konservative Scheduler arbeiten häufig mit Sperrprotokollen. Da solche Verfahren
mit Konflikten rechnen und vorsorglich Sperren setzen, werden sie auch als
“pessimistische” Verfahren bezeichnet. Eine Besonderheit dieser sperrbasierten
Verfahren ist die Möglichkeit, die Ausführung von Aktionen zu verzögern um damit
Aktionen umzuordnen.
Optimistische Protokolle
Ein optimistischer Scheduler erlaubt die Ausführung von Aktionen, ohne dass zuvor
überprüft werden muss, ob diese Aktion zulässig ist (solche Verfahren werden
teilweise auch als “aggressive” Verfahren bezeichnet). Allerdings müssen
optimistische Scheduler vor dem Commit eine Validierung bzw. Konfliktanalyse
durchführen, um Korrektheit zu garantieren.
In der Praxis haben sich die konservativen Protokolle durchgesetzt, die wir im
Folgenden auch weiter betrachten werden.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-39
Zwei-Phasen-Sperrprotokoll (2PL)
Idee:
Vor dem Zugriff (sowohl lesend als auch schreibend) auf ein Datenobjekt
muss eine Sperre erworben werden.
Dabei werden die Sperren so gewählt, dass keine Konfliktaktionen auf
demselben Objekt möglich sind.
Diese Sperren müssen transparent für die Transaktionen
(und damit für den Benutzer bzw. das Anwendungsprogramm)
vom System gesetzt werden.
Beispiel:
Transaktion T1 = · a11 a12 … a1k Ò
wird automatisch transformiert in
T1* = · L(a11) a11 L(a12) a12 … L(a1k) a1k U(a11) U(a12) … U(a1k) Ò
wobei L(aik) eine Sperre auf das Objekt der Aktion aik erwirbt (Lock)
U(aik) die gehaltene Sperre wieder freigibt (Unlock)
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-40
20
Sperrmodi und -verträglichkeit
Das Ziel des 2PL-Verfahrens ist, keine Konfliktaktionen auf demselben Objekt
zuzulassen, aber zugleich Aktionen, die nicht in Konflikt stehen, zu erlauben.
Zwei parallele Transaktionen dürfen also dasselbe Objekt lesen, wenn aber auch auf
das Objekt geschrieben wird, darf dies nur eine Transaktion (und keine andere darf
das Objekt lesen).
Um dies zu realisieren, benötigen wir unterschiedliche Sperrmodi:
• S-lock (= Shared Lock) für lesenden Zugriff, also für r(x)
• X-lock (= Exclusive Lock) für schreibenden Zugriff, also für w(x)
Sperren sind im Prinzip Semaphore, die durch das DBS implementiert werden. Der
Sperrmodus für einen Zugriff wird jeweils vom DBS automatisch gewählt. Für die
Sperrmodi gilt folgende Verträglichkeit (die aus der Konfliktrelation abgeleitet ist):
Transaktion fordert
Objekt Shared
belegt
eXclusive
mit
FS 2014
Shared
eXclusive
+
—
—
—
+ angeforderte Sperre kann vergeben werden
(Reihenfolge von Lesern vertauschbar. Kein
Konflikt im r/r-Fall)
— angeforderte Sperre kann NICHT vergeben
werden (da sonst w/r, r/w, w/w-Konflikt),
die anfordernde Transaktion muss warten
(dazu verwaltet das DBS verschiedene
Queues).
Datenbanken (CS243) – Transaktionsverwaltung
7-41
Zwei-Phasen-Sperrprotokoll
Zwei-Phasen-Sperrprotokoll (2PL)
Ein Scheduler hält das Zwei-Phasen-Sperrprotokoll (2PL) ein, wenn:
(1) Vor der Ausführung jeder Aktion aik Sperren L(aik)
erworben werden (S-Sperre für Leseaktionen, X-Sperre für
Schreibaktionen)
(2) Eine Sperre L(aik) mindestens solange gehalten wird, bis die
Aktion aik ausgeführt wurde
(3) Nach dem Freigeben einer Sperre keine weitere für dieselbe Transaktion
angefordert wird.
Erklärungen
Zu (1): Hiermit werden Konfliktaktionen in die Reihenfolge der Sperranforderung
gebracht. Falls eine Sperranforderung für Aktion aik von Ti nicht gewährt
werden kann, muss Ti warten!
Zu (2): Die Aktionen müssen auch wirklich in der vom Scheduler
vorgeschriebenen Reihenfolge ausgeführt werden.
Ein 2PL-Scheduler erzeugt nur konflikt-serialisierbare (CPSR) Schedules; die
entstehenden Schedules sind sogar ordnungserhaltend (OPSR).
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-42
21
Zweiphasigkeit
Zu (3): Sperranforderungen und –freigaben sind also in zwei Phasen aufgeteilt.
Zunächst erwirbt eine Transaktion in der Wachstumsphase Sperren für
alle Aktionen. Mit der ersten Sperrfreigabe tritt die Schrumpfungsphase ein,
es dürfen dann keine neuen Sperren mehr angefordert werden.
Anzahl
Sperren
BOT
Wachstumsphase
FS 2014
t
EOT
Schrumpfungsphase
Datenbanken (CS243) – Transaktionsverwaltung
7-43
Beispiel für einen 2PL-Ablauf
Ausführung des Eingabeschedules
· r1(a) w2(a) w1(b) C1 w2(b) C2 Ò
Locktabelle des 2PL-Schedulers zu folgenden Zeitpunkten:
Zeit
Objekt
t0
a
—
b
—
Sperranforderungen/
-freigaben des
Schedulers
t0
t1
t2
t3
t4
t5
t6
t7
t1
t2
t3
t4
t5
t6
t7
t
Ausgabeschedule
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-44
22
Striktes Zwei-Phasen-Sperrprotokoll
Das 2PL-Protokoll erlaubt das frühe Freigeben von Sperren (vor dem Commit).
Da aber ein (on-line) Scheduler in der Regel nur den Präfix eines Schedules zur
Verfügung hat, ist dieses frühzeitige Freigeben risikoreich!
Abhilfe: Sperren müssen immer bis zum Ende der jeweiligen Transaktion
gehalten werden.
Striktes Zwei-Phasen-Sperrprotokoll (S2PL)
Ein Scheduler hält das strikte Zwei-Phasen-Sperrprotokoll (S2PL) ein, wenn:
(1)
Vor der Ausführung jeder Aktion aik Sperren L(aik)
erworben werden (S-Sperre für Leseaktionen, X-Sperre für
Schreibaktionen)
(2)
Alle Sperren L(aik) bis zum Ende der jeweiligen Transaktion
gehalten werden (werden also beim Commit wieder freigegeben).
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-45
Korrektheit von S2PL
Offensichtlich ist das S2PL-Protokoll strenger als das 2PL-Protokoll. Also garantiert
auch S2PL, dass jeder erzeugte Schedule OPSR und damit auch CPSR ist.
Zusätzlich gilt: Ein S2PL-Scheduler erzeugt nur commit-ordnungserhaltende
(COPSR) Schedules
Anzahl
Sperren
Die Schrumpfungsphase
fällt also im S2PL mit dem
Commit bzw. dem Abort
zusammen.
BOT
FS 2014
EOT
t
Datenbanken (CS243) – Transaktionsverwaltung
7-46
23
2PL in der Praxis
•
Das strikte 2PL ist als Concurrency-Control-Protokoll in einigen
kommerziellen DBS implementiert, wird aber immer mehr durch die Snapshot
Isolation (dazu später mehr) „verdrängt“
•
Das 2PL kann auf verschiedenen Sperrgranulaten implementiert werden:
– Seitensperren (einfach zu realisieren, aber nicht sehr performant)
– Relationssperren oder Tablespace-Sperren (sehr grob und damit restriktiv)
– Tupelsperren und Sperren auf Indexeinträgen (sehr feines Granulat und
daher bezüglich der Mehrbenutzerleistung am besten, aber auch komplexer
zu realisieren; wird in den meisten kommerziellen DBS verwendet)
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-47
Deadlocks
Ein entscheidender Nachteil des 2PL-Protokolls (und des S2PL-Protokolls) ist die
Tatsache, dass zyklische Wartebeziehungen entstehen können.
Das bedeutet, Transaktionen warten (prinzipiell unendlich lange) auf Sperren, die
von anderen Transaktionen gehalten werden, dort aber nicht freigegeben werden
können (weil auch diese Transaktionen auf weitere Sperren warten).
Solche zyklischen Wartebeziehungen werden auch als Deadlocks bezeichnet.
Beispiel: Gegeben sei folgender Eingabeschedule ES
ES = · r1(x) w2(y) w2(x) C2 w1(y) C1 Ò
Ein S2PL-Scheduler produziert folgenden Ausgabeschedule S:
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-48
24
Deadlock-Erkennung: Wait-For-Graph
Eine wesentliche Voraussetzung zur Behebung von Deadlocks ist zunächst ein
Mechanismus, um zyklisches Warten überhaupt zu erkennen.
Dies geschieht zumeist mit Hilfe eines Wartegraphen (Wait-For-Graph, WFG).
Knoten dieses Graphen sind Transaktionen, Kanten Ti Ø Tk werden genau dann
eingefügt, wenn Ti auf eine Sperre wartet, die von Tk gehalten wird
(Ti wartet auf Unlock von Tk)
Beispiel: Gegeben sei folgender Eingabeschedule ES
ES = · r3(a) w1(b) w1(c) w1(a) r2(d) w2(e) r4(b) w2(c) r3(e) r5(e) C2 C3 C5 C1 C4 Ò
Die Erzeugung des Ausgabeschedules S zu ES durch einen 2PL-Scheduler
führt dann zu folgenden Wartebeziehungen:
WFG(S):
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-49
Deadlock-Auflösung …
Deadlocks entsprechen einem Zyklus im Wartegraphen. Es werden also Graphenalgorithmen zur effizienten Zyklenerkennung in gerichteten Graphen benötigt.
Wann sollte diese Zyklenerkennung vorgenommen werden? Mögliche Strategien:
– Regelmässig, nach bestimmter Zeit (periodisch)
– Nach jedem Einfügen einer Kante in den WFG, also bei jeder nicht gewährten
Sperranforderung (kontinuierlich)
Deadlocks können nur aufgelöst werden, indem Transaktionen aus dem WFG-Zyklus
zurückgesetzt werden (schliesslich wartet jede dieser Transaktionen und kann nicht
fortfahren). Allerdings entstehen dadurch “Kosten” (Transaktionen, die abgebrochen
werden, haben bereits Ressourcen verbraucht).
Das Anwendungsprogramm erhält in diesem Fall einen speziellen Fehlercode
(SQLCODE) für die SQL-Anweisung, bei der der Deadlock entstand. Das Programm
sollte in einem solchen Fall selbst den erneuten Start der Transaktion veranlassen
(ggf. nach erneuten Initialisierungen), damit der Deadlock und seine Behandlung
gegenüber dem Endbenutzer transparent ist.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-50
25
… Deadlock-Auflösung
Welche Transaktion(en) soll(en) zurückgesetzt werden (Auswahl des “DeadlockOpfers”)?
Mögliche Strategien sind:
– Letzte Transaktion, die eine Kante in den WFG eingefügt hat (last blocked)
– Transaktion, die am wenigsten Sperren hält (minimum locks)
– Transaktion, die am wenigsten Rücksetzkosten verursacht, z.B. diejenige,
die am wenigsten Update-Aktionen durchgeführt hat (minimum work)
– Transaktion, welche die meisten Zyklen auflöst (most cycles); dies ist vor
allem beim periodischen Check des WFG relevant
– Transaktion, deren Rücksetzen am meisten Kanten aus dem WFG entfernt
(most edges)
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-51
Sperrkonversion
•
•
Deadlocks können auch aufgrund von Sperrkonversionen (Verschärfung einer
Shared-Sperre in eine Exclusive-Sperre) auftreten – dies tritt in der Praxis
potentiell häufig auf.
Solche Deadlocks können durch zusätzliche Sperrmodi weitgehend vermieden
werden bzw. durch Einflussnahme des Benutzers / Anwendungsprogrammierers
auf die Sperrverwaltung. Aus diesem Grund hat SQL spezielle Anweisungszusätze
wie z.B.
SELECT * FROM … WHERE … FOR UPDATE
(setzt automatisch Schreibsperren für gelesene Daten)
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-52
26
Serialisierungsgraph-Test (SGT)
Grundlage des Serialisierungsgraph-Test-Verfahrens (SGT) ist die naheliegende Idee,
dass der Scheduler einen Serialisierungsgraphen pflegt und sicherstellt,
dass dieser azyklisch bleibt.
Dadurch ist dann sofort garantiert, dass jeder SGT-Schedule CPSR ist!
SGT-Algorithmus:
Voraussetzung: zu jedem Zeitpunkt wird benötigt
– Ak: die Menge der Aktionen aller aktiven und korrekt abgeschlossenen
Transaktionen Tk
– SG: der bislang aufgebaute Serialisierungsgraph
Aktion pi von Ti steht zur Ausführung an
– Falls Ti noch nicht in SG
• Füge Ti in SG ein
– Für alle Tk, also für alle aktiven und committeten Transaktionen
• Füge Kante Tk Ø Ti in SG ein, wenn ein Ak eine Aktion qk enthält,
die mit pi in Konflikt ist.
– Prüfe, ob SG azyklisch ist
– Falls ja, führe pi aus und füge pi in Ai ein, sonst: setze Ti zurück
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-53
Grösse des SG bei SGT
•
•
Ein Problem beim SGT-Verfahren ist, dass der Serialisierungsgraph
immer grösser wird
– Wann können Knoten sicher eliminiert werden?
Naive Lösungsvermutung: Eine Transaktion Tk kann nach dem Commit
entfernt werden
– Diese Annahme ist allerdings falsch (wie das folgende Beispiel zeigt)
Beispiel:
S = · rk+1(x) w1(x) w1(y1) C1 w2(y1) w2(y2) C2… wk(yk-1) wk(yk) Ck wk+1(yk) Ck+1Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-54
27
Entfernen von Transaktionen aus SGT
Das Beispiel zeigt, dass im Prinzip beliebig viele abgeschlossene Transaktionen im
Serialisierungsgraph behalten werden müssen.
Richtiges und korrektes Entfernen von Transaktionen aus SG:
Tk kann entfernt werden, wenn
1)
2)
Tk abgeschlossen ist und
Tk Quelle in SG ist
Wenn Tk abgeschlossen ist, dann können keine Kanten nach Tk gerichtet
hinzukommen. Wenn Tk zudem noch Quelle ist, dann kann Tk nicht mehr in einen
Zyklus verwickelt werden, darf also aus SG entfernt werden.
SGT wird heute in Datenbanken praktisch nicht verwendet. Das Problem des
Verfahrens ist, dass bei kurzen r/w-Transaktionen der Aufwand recht gross ist,
die Ak-Mengen zu verwalten (zudem ist für r/w-Transaktionen die Verwendung
von Sperren einfacher und auch intuitiver). Allerdings besitzt SGT den Vorteil,
sehr generisch zu sein (im Gegensatz zu den Sperrverfahren, da S- bzw. X-Sperren
sehr stark auf der Semantik von Lese- und Schreibaktionen basieren).
Daher ist das SGT-Verfahren für semantisch reiche Aktionen in komplexeren
Umgebungen durchaus sinnvoll.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-55
Isolationsstufen
•
Striktes 2PL garantiert Serialisierbarkeit. Für bestimmte Transaktionen können
jedoch auch geringere Anforderungen an die Korrektheit ausreichen. In SQL-92
kann deshalb mit einer SET TRANSACTION-Anweisung unmittelbar vor der
ersten Anweisung einer Transaktion auch eine niedrigere Isolationsstufe als volle
Serialisierbarkeit spezifiziert werden.
•
Spezifikation von Transaktionsmodi
TransactionSpec =
SET TRANSACTION
[ READ ONLY | READ WRITE ]
[ ISOLATION LEVEL Isolation ]
Isolation =
READ UNCOMMITTED | READ COMMITTED | REPEATABLE READ |
SERIALIZABLE
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-56
28
SQL-92 Isolationsstufen
READ UNCOMMITTED („level 0“) bedeutet, dass die entsprechende Transaktion
Daten, die von einer anderen noch im Gang befindlichen Transaktion geschrieben
wurden, lesen kann (“dirty read”). Die Transaktion hält keine Sperren.
Diese Isolationsstufe ist nur für READ ONLY Transaktionen gestattet.
READ COMMITTED („level 1“) bedeutet, dass die entsprechende Transaktion nur
„definitive“ Daten lesen kann. Dies kann erreicht werden, wenn die Transaktion
keine Sperren für Tupel hält, die von ihr gelesen wurden, wohl aber für solche,
die von ihr modifiziert wurden. Da keine Sperren für gelesene Tupel gehalten
werden, ist es möglich, dass bei wiederholtem Lesen eines bestimmten Tupels
dieses zwischenzeitlich verändert wurde. Auch das Phänomen des inkonsistenten
Lesens sowie das Phantom-Problem kann auftreten.
REPEATABLE READ („level 2“) bedeutet ebenfalls, dass die entsprechende
Transaktion nur „definitive“ Daten lesen kann, z.B. indem die Transaktion Sperren
für alle Tupel hält, die von ihr gelesen und/oder geschrieben wurden (bzw. wenn
sie auf einem privatem Snapshot operiert). Da jedoch keine so genannten
Prädikatsperren gehalten werden kann u.U. noch das Phantomproblem auftreten.
SERIALIZABLE („level 3“) schliesst auch noch das Phantomproblem aus .
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-57
Snapshot Isolation (SSI)
Bisher haben wir für jede Transaktion Tk nur die Aktionen rk(x) bzw. wk(x) sowie
die Beendigung von Tk betrachtet (entweder durch Commit Ck oder Abort Ak)
Für die Formalisierung der Snapshot Isolation benötigen wir jetzt zusätzlich noch
folgende Informationen für jede Transaktion Tk
– Read-Set RS(Tk): Menge der Datenobjekte, welche von Tk gelesen werden
– Write-Set WS(Tk): Menge der Datenobjekte, welche von Tk geschrieben werden
– Start von Tk: BOTk (Begin-of-Transaction)
In den folgenden Beispielschedules werden wir den Beginn BOTk einer Transaktion Tk
nicht explizit einfügen. Die erste Aktion von Tk soll gleichzeitig auch der Start der
Transaktion sein. Später (im praktischen Beispiel) werden wir dann noch eine andere
Alternative für BOT kennen lernen.
Zusätzlich kann jedes Datenbank-Objekt x in mehreren Versionen existieren. Diese
Versionen werden unterschieden durch die Angabe, welche Transaktion diese Version
erstellt hat; z.B. wurde xi von Transaktion Ti mittels wi(xi) geschrieben.
Dementsprechend bezeichnet rk(xi) das Lesen von Version xi durch Transaktion Tk.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-58
29
Definition der Snapshot-Isolation
Idee: Jede Transaktion Tk erhält eine eigene Version (Snapshot) der Datenbank
beim Transaktionsbeginn zugewiesen. Dieser Snapshot ist für die komplette
Lebensdauer von Tk gültig.
Snapshot Isolation (SSI):
Ein Mehrversionen-Schedule über einer Menge  von Transaktionen
erfüllt das Kriterium der Snapshot-Isolation (SSI), wenn die folgenden
Bedingungen eingehalten werden:
(SSI-V)
 rk(xi) gilt: wi(xi) < Ci < BOTk < rk(xi) und
± wm(xm) mit: wm(xm) < BOTk und Ci < Cm < BOTk
(SSI-W)
 Ti, Tk mit
gilt:
WS(Ti)
(BOTi < BOTk < Ci) ¤
(BOTk < BOTi < Ck)
… WS(Tk) = 
Ordnet einem Leser rk immer den jüngsten, zum Startzeitpunkt von Tk
committeten Wert zu (= Versionenzuordung)
SSI-W: Je zwei parallele Transaktionen müssen paarweise disjunkte Write-Sets
besitzen
SSI-V:
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-59
SSI – Beispiele …
Beispiel 1:
S1 = · r11(x) r21(y) w12(x) r22(x) C2 w13(y) C1 Ò
Mehrversionenschedule: S‘1 = · r11(x0) r21(y0) w12(x1) r22(x0) C2 w13(y1) C1 Ò
Beispiel 2:
S2 = · r11(x) r21(y) w22(y) C2 r12(y) w13(y) C1 Ò
Mehrversionenschedule: S‘2 = · r11(x0) r21(y0) w22(y2) C2 r12(y2) w13(y1) C1 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-60
30
… SSI – Beispiele
Beispiel 3:
S3 = · r11(x) r21(y) r22(x) r12(y) w23(x) w13(y) C1 C2 Ò
Mehrversionenschedule (einzige mögliche Versionenordnung) :
S‘3 = · r11(x0) r21(y0) r22(x0) r12(y0) w23(x2) w13(y1) C1 C2 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-61
Praktisches Beispiel …
Relationen
Konto
Zins
(KontoNr, Saldo, KontoInhaber),
(KontoNr, Zinssatz)
Transaktion T1 (Zinsbestimmung):
– Lese Kontostand
– Falls 5000 < Kontostand < 10000 erhöhe Zins um 1%,
falls Kontostand > 10000 erhöhe Zins um 2%
Transaktion T2 (Zinsauszahlung):
– Lese kontospezifischen Zinssatz
– Buche Zins auf Konto
Initialwert für KontoNr 4711:
– Kontostand = 9999
– Zins = 3%
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-62
31
… Praktisches Beispiel …
Transaktion T1:
> Select Saldo from Konto
where KontoNr = 4711;
Transaktion T2:
> Select Zinssatz from Zins
where KontoNr = 4711;
> Select Saldo from Konto
where KontoNr = 4711;
> Select Zinssatz from
Zins where KontoNr=4711;
> Update Konto set Saldo =
Saldo*Zinssatz where
KontoNr = 4711;
> Update Zins Set Zinssatz =
Zinssatz+1 where KontoNr =
4711;
> commit;
> commit;
t
S3 = · r11 (x) r21 (y) r22 (x) r12 (y) w23 (x) w13 (y) C1 C2 Ò
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-63
… Praktisches Beispiel
•
S3 ist nicht serialisierbar!
 Allerdings ist S3 “korrekt” bezüglich SSI da sowohl (SSI-V) als auch
(SSI-W) erfüllt sind!
 Beide möglichen seriellen (und damit korrekten) Abläufe liefern jedoch andere
Ergebnisse (entweder höheren Zinssatz oder höheren Kontostand)
– T1 Ø T2: Saldo = 10399 und Zinssatz = 4%
– T2 Ø T1: Saldo = 10299 und Zinssatz = 5%
– Hier jedoch: Saldo = 10299 und Zinssatz = 4%
•
SSI wird in der Isolationsstufe serializable von mehreren
Datenbanksystemen (z.B. Oracle, mySQL) verwendet!
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-64
32
Vergleich: SSI vs. CPSR
CPSR vs. SSI:
Begründung siehe Beispiele 1-3
SSI
CPSR
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-65
7.4 Atomarität und Persistenz in Datenbanken
Die Eigenschaften der Atomarität und Persistenz bedeuten, dass DatenbankAnwendungsprogramme grösstenteils so geschrieben werden können,
als gäbe es keine Fehler der Hardware oder Systemsoftware.
Die Transaktionsverwaltung eines DBS stellt mit der Recovery-Komponente weit
reichende Fehlertoleranzmassnahmen zur Verfügung, und zwar transparent für
die Anwendungsentwicklung.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-66
33
Übersicht über Fehlerklassen
Folgende Fehler können die Atomarität oder die Persistenz von Transaktionen
(A bzw. D von ACID) gefährden:
1. Fehler im Anwendungsprogramm
2. Fehler in der Systemsoftware (OS oder DBS), die zum “Systemabsturz”
(engl.: system failure, [soft] crash) führen
– “Bohrbugs”: deterministisch und reproduzierbar; sind in gut ausgetesteter
Systemsoftware so gut wie eliminiert
– “Heisenbugs”: schwer einzugrenzen und praktisch nicht reproduzierbar;
treten vor allem in Überlastsituationen im Mehrbenutzerbetrieb auf
3. Stromausfall
4. Transienter Hardwarefehler (CPU, Speicher)
5. Fehlbedienung (Systemadministrator, Operator, Techniker)
6. Plattenfehler (Media-Fehler), der zum Verlust von permanent gespeicherten
Daten führt (engl.: disk failure, hard crash)
7. Katastrophe (Feuer, Erdbeben, etc.)
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-67
Fehlerbehandlung
1. Unvollendete Transaktionen von fehlerhaft beendeten Programmen werden
zurückgesetzt.
2. – 5.
– Das DBMS wird im Warmstart neu gestartet und führt dabei eine
Crash-Recovery durch. Dabei werden alle vor dem Absturz unvollendeten
Transaktionen zurückgesetzt (Undo von Transaktionen).
– Änderungen von beendeten Transaktionen werden nötigenfalls
DBMS-intern wiederholt (Redo von Transaktionen).
• Transaktionen, für die die Recovery-Komponente ein Undo durchgeführt
hat, müssen vom Anwendungsprogramm oder sogar vom Endbenutzer
neu gestartet werden.
• Die Fehlerkategorie 3 kann durch ununterbrechbare Stromversorgung
eliminiert werden.
6. Wiederherstellung der verlorenen Daten durch Aufsetzen auf einer Archivkopie der
Datenbank und Wiederholung der Änderungen abgeschlossener Transaktionen
(Media-Recovery, Archiv-Recovery).
7. Änderungen abgeschlossener Transaktionen müssen auf einem zweiten,
genügend weit entfernten Rechner doppelt erfasst werden;
im Katastrophenfall übernimmt der zweite Rechner dann die Verarbeitung.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-68
34
7.5 Transaktions-Recovery
In der bisherigen Betrachtung der Concurrency Control wurden Fehler nicht
berücksichtigt, d.h. der Einfluss abgebrochener Transaktionen auf die Korrektheit
eines Schedules wurde ignoriert:
– bei CPSR wird nur die Committed Projection eines Schedules betrachtet.
– Bisher sind wir also implizit so verfahren, als ob wir die Aktionen
abgebrochener Transaktionen einfach streichen könnten
– Dies ist jedoch nicht ohne weiteres möglich, da natürlich Schreib-Aktionen
abgebrochener Transaktionen sehr wohl den Datenbankzustand ändern
können (und dieser geänderte Zustand dann von weiteren Transaktionen
gelesen werden kann).
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-69
Transaktions-Recovery
Die Atomarität von Transaktionen eine wichtige Eigenschaft, denn jederzeit
während der Ausführung einer Transaktion können Fehler auftreten
(Systemfehler oder vom Benutzer bzw. Anwendungsprogramm initiierte Fehler)
– Es muss garantiert werden, dass die Änderungen abgebrochener
Transaktionen ohne Seiteneffekte entfernt werden können
– Recovery, dt.: Fehlererholung
Dies wird mit den folgenden Korrektheitskriterien präzisiert, die angeben, wann
Transaktionen in einem Schedule korrekt abgebrochen werden können (also wie
Fehler der Kategorie 1 behoben werden können)
– Diese Kriterien folgen dabei der “klassischen” Vorgehensweise, in der
Concurrency Control und Recovery getrennt voneinander betrachtet
werden
– in der Praxis sind jedoch Protokolle gefragt, die beide Probleme integriert
behandeln
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-70
35
Transaktionsverwaltung – Beispiel: Recovery
„Ich möchte 250.SFr von meinem
Konto abheben“
„Ich möchte meiner
Enkelin 200.- SFr
überweisen“
Kontostand
0815
2770.-
4711
120.-
320.-
...
KontoNr
SELECT Kontostand INTO :balanceTransB
FROM Konto WHERE KontoNr = 4711;
balanceTransB := balanceTransB + 200;
320.-
SELECT Kontostand INTO :balanceATM
FROM Konto WHERE KontoNr = 4711;
balanceATM := balanceATM – 250;
Update Konto
SET Kontostand = :balanceATM
WHERE KontoNr = 4711;
70.-
COMMIT WORK;
FS 2014
Update Konto
SET Kontostand = :balanceTransB
WHERE KontoNr = 4711;
ROLLBACK WORK;
Datenbanken (CS243) – Transaktionsverwaltung
7-71
Rücksetzbarkeit (Recoverability)
•
•
Die Atomaritäts-Eigenschaft des Transaktionskonzepts verlangt, dass die Effekte
einer abgebrochenen Transaktion vollständig rückgängig gemacht werden.
Dies betrifft sowohl eventuell schon durchgeführte Änderungen in der Datenbank
als auch Auswirkungen auf andere Transaktionen.
Allerdings kann der Abbruch einer Transaktion und das Rückgängigmachen
ihrer Änderungen in bestimmten Situationen unmöglich sein, weil andere,
bereits abgeschlossene Transaktionen, davon betroffen sind:
Beispiel:
FS 2014
S1 = · w1(x) r2(x) w2(y) C2 A1 Ò
Datenbanken (CS243) – Transaktionsverwaltung
7-72
36
Recoverability (RC)
Die Minimalanforderung an Schedules, um korrekte Abbrüche von Transaktionen
zu ermöglichen ist daher, dass jede Transaktion Ti nach allen Transaktionen Tk,
von denen sie liest, beendet wird. Hierzu benötigen wir zunächst Information über
die Frage, welche Transaktion von welcher anderen Transaktion Daten liest.
Liest-von-Beziehung:
(a)
(b)
(c)
Reads-From-Relation:
(Liest-von-Relation)
Sei S ein Schedule. ri(x) liest-von wk(x), i  k, falls:
wk(x) < ri(x)
 wm(x) mit wk(x) < wm(x) < ri (x)
Tk ist nicht abgebrochen
RF(S) = { (Tk, x, Ti) | ri(x) liest-von wk(x) in S}
Rücksetzbarkeit (Recoverability, RC)
Ein Schedule S ist rücksetzbar (recoverable), wenn für alle
Transaktionen Ti, Tk in S gilt:
Falls (Tk, x, Ti) œ RF(S) und i ∫ k und Ci in S, dann
müssen die Commits wie folgt geordnet sein: Ck < Ci.
Alle Transaktionen Tk, von denen Ti liest, müssen also vor Ti beendet sein.
Die Klasse der rücksetzbaren (recoverable) Schedules wird mit RC bezeichnet.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-73
Transaktionsverwaltung – Beispiel: „Dominoeffekt“
„Ich möchte 250.SFr von meinem
Konto abheben“
„Ich möchte meiner
Enkelin 200.- SFr
überweisen“
Kontostand
0815
2770.-
4711
120.-
320.-
...
KontoNr
SELECT Kontostand INTO :balanceTransB
FROM Konto WHERE KontoNr = 4711;
balanceTransB := balanceTransB + 200;
320.-
SELECT Kontostand INTO :balanceATM
FROM Konto WHERE KontoNr = 4711;
balanceATM := balanceATM – 250;
Update Konto
SET Kontostand = :balanceATM
WHERE KontoNr = 4711;
Transaktion am Geldautomat muss
ebenfalls abgebrochen werden!
FS 2014
Update Konto
SET Kontostand = :balanceTransB
WHERE KontoNr = 4711;
70.-
ROLLBACK WORK;
Datenbanken (CS243) – Transaktionsverwaltung
7-74
37
Kaskadenfreiheit (ACA)
Selbst bei rücksetzbaren Schedules können, wie im vorigen Beispiel gezeigt, noch
unangenehme Effekte auftreten (in abstrakter Formulierung):
Beispiel:
S2 = · w1(x) r2(x) w2(y) A1 Ò
Es kann also vorkommen, dass das Rücksetzen einzelner Transaktionen in einem
RC-Schedule kaskadierend das Rücksetzen weiterer Transaktionen erfordert.
Kaskadenfreiheit (Avoiding Cascading Aborts, ACA)
Ein Schedule S ist kaskadenfrei, wenn gilt:
falls (Tk, x, Ti) œ RF(S) und i  k, dann muss Ck < ri(x) sein.
Transaktionen dürfen also nur “comittete” Werte lesen.
Die Klasse der kaskadenfreien Schedules wird auch als ACA (avoiding cascading
aborts) bezeichnet.
ACA Õ RC: ACA ist eine echte Teilmenge von RC.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-75
Striktheit
•
Für die praktische Durchführung eines Aborts müssen die einzelnen Aktionen
einer abgebrochenen Transaktion rückgängig gemacht werden.
•
In der Regel schreibt man dazu das “before image” des betroffenen
Datenobjektes (den letzten Wert, den es vor Ausführung der Aktion der
abzubrechenden Transaktion hatte). Dies kann jedoch inkorrekt sein,
wenn “nur” Kaskadenfreiheit existiert:
Beispiel:
FS 2014
S3 = ‚ w1(x) w2(x) C2 A1 Ò
Datenbanken (CS243) – Transaktionsverwaltung
7-76
38
Striktheit (ST)
Striktheit (ST)
Ein Schedule S ist strikt, wenn gilt:
Falls wk(x) < ai(x) und i  k in S, dann müssen die TerminierungsAktionen wie folgt geordnet sein:
Ak < ai(x) oder Ck < ai(x) (für ai œ {ri, wi}).
Ein Objekt darf weder gelesen noch geschrieben bzw. überschrieben
werden, bevor es “commited” oder “aborted” ist.
Die Klasse der strikten Schedules wird mit ST bezeichnet.
ST Õ ACA: ST ist eine echte Teilmenge von ACA.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-77
Rigorosität (RG)
Eine noch weitere Einschränkung der Striktheit eines Schedules führt zur
Rigorosität:
Rigorosität (RG)
Ein Schedule S ist rigoros, wenn zwischen je zwei
Konflikt-Aktionen ai < ak stets ein Ci oder Ai kommt.
Die Klasse der rigorosen Schedules wird mit RG bezeichnet.
RG Õ ST: RG ist eine echte Teilmenge von ST.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-78
39
Einordnung der Rigorosität
RG verhindert also r/w, w/r und w/w-Konflikte zwischen aktiven Transaktionen,
während ST dies nur für w/r und w/w-Konflikte tut.
Dieser Unterschied hat grosse praktische Konsequenzen:
RG Õ CPSR:
•
•
RG ist eine echte Teilmenge der Klasse CPSR aller
konflikt-serialisierbaren Schedules.
RG garantiert also als einziges der bisher eingeführten Korrektheitskriterien
Concurrency Control und Recovery gleichzeitig (jedoch sehr restriktiv):
RG Õ (CPSR … RC)
Da RG die Platzierung von Commits zwischen Konflikt-Aktionen verlangt,
gilt bezüglich COPSR (der Klasse der commit-ordnungserhaltend serialisierbaren
Schedules):
RG Õ COPSR:
RG ist eine echte Teilmenge der Klasse COPSR.
Im Gegensatz zu RG sind jedoch jeweils ST, ACA und RC nicht mit CPSR
vergleichbar, garantieren also nicht gleichzeitig auch Serialisierbarkeit!
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-79
Zusammenfassung der Klassen von Schedules
Es gilt also: RG Õ ST Õ ACA Õ RC und RG Õ COPSR
Alle Schedules
CPSR
COPSR
RC
ACA
ST
Serielle
Schedules
RG
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-80
40
7.6 Crash Recovery
Im Gegensatz zur Transaktions-Recovery, in der (nur) die Atomarität von
Transaktionen garantiert wird, ist das Ziel der Crash-Recovery, Atomarität und
Persistenz zu garantieren.
Bei einem Systemabsturz muss der Datenbank-Server wieder gestartet und vor der
Aufnahme des “normalen” Betriebes wieder in einen konsistenten Zustand gebracht
werden. Dies beinhaltet das ...
• Rückgängigmachen der Änderungen abgebrochener Transaktionen,
die bereits auf persistentem Speicher sind
• Nachfahren der Änderungen von Transaktionen, die bereits vor dem Crash
mit Commit beendet wurden, aber noch nicht auf den persistenten Speicher
geschrieben wurden
... jeweils unter Einhaltung der Serialisierungsordnung der ursprünglichen Ausführung
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-81
Recovery-Komponente: Zielsetzungen
Vordringliches Ziel ist eine hohe Verfügbarkeit, also eine möglichst hohe
Wahrscheinlichkeit, dass ein Benutzer zu einem beliebigen Zeitpunkt ein laufendes
System antrifft.
Start des
Systems
Systemausfall
Systemausfall
Recovery
beendet
MTTR
Recovery
beendet
Zeit
MTTF
MTBF
Für die Verfügbarkeit v gilt:
mit: – MTTF = Mean Time To Failure
– MTTR = Mean Time To Repair
– MTBF = Mean Time Between Failures
: System nicht verfügbar
v :
MTTF
MTTF

MTBF MTTF  MTTR
(Eine Verfügbarkeit von 99 % impliziert beispielsweise eine “Auszeit” von
ca. 5000 Minuten pro Jahr, während der das System nicht verfügbar ist; eine
Verfügbarkeit von 99.9 % impliziert eine “Auszeit” von ca. 500 Minuten pro Jahr.)
Das führt zu folgenden Anforderungen:
• Schnelle Recovery beim Warmstart: kurze MTTR
• Geringer Overhead im laufenden Normalbetrieb
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-82
41
Logging für (Crash-)Recovery
Arbeitsprinzipien der Recovery-Komponente:
• Um im Fehlerfall Undo und Redo durchführen zu können, müssen Änderungen
auf einem hinreichend stabilen Speichermedium protokolliert werden.
Für jede Änderung gibt es eine Undo-Information, um die Änderung rückgängig
machen zu können, und eine Redo-Information, um die Änderung wiederholen zu
können.
Atomaritätsprinzip:
• Vor einer Veränderung der permanenten Datenbank (durch Zurückschreiben
geänderter Seiten aus dem Puffer auf die Platte) muss die entsprechende
Undo-Information auf stabilen Speicher geschrieben werden.
Persistenzprinzip:
• Vor dem Commit einer Transaktion muss die entsprechende Redo-Information
auf stabilen Speicher geschrieben werden.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-83
Recovery-Komponente: Arbeitsprinzipien
Idempotenzprinzip:
• Da es während eines Warmstarts zu einem erneuten Ausfall kommen kann,
müssen Recovery-Massnahmen beliebig oft wiederholbar sein:
– zweimaliges Undo derselben Änderung hat gleichen Effekt wie
einmaliges Undo
– zweimaliges Redo derselben Änderung hat gleichen Effekt wie
einmaliges Redo
– Ein Undo einer Änderung, die durch den Systemabsturz bereits verloren
gegangen ist, hat keinen Effekt; ein Redo einer Änderung, die durch den
Systemabsturz gar nicht verloren gegangen ist, hat keinen Effekt.
•
Änderungen werden in Form von Log-Sätzen in einer Log-Datei protokolliert.
Um nicht für alle Änderung einen Plattenzugriff durchführen zu müssen,
werden Log-Sätze zunächst in einen Log-Puffer im Hauptspeicher geschrieben
und nur bei Bedarf (später mehr hierzu) sequentiell in die Log-Datei auf Platte
geschrieben.
•
Um sicherzustellen, dass für die Log-Datei tatsächlich immer sequentielle I/Os
stattfinden, sollte die Log-Datei auf einer separaten Platte liegen.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-84
42
DB-System-Modell: Verfeinerung
Transaktionen
DBMS
read / write / begin / commit / abort
TM
read / write / begin / commit / abort
Scheduler
read / write / begin / commit / abort
DataManager
Recovery-Manager (RM)
read / write
begin / commit / abort
Cache-Manager (CM)
Cache
flush (steal)
write
Log-Puffer
fetch
Datenbankseite
force
Log-Satz
Datenbank
FS 2014
transienter
Speicher
persistenter
Speicher
Log-Datei
Datenbanken (CS243) – Transaktionsverwaltung
7-85
Logging: Implementierung …
•
Ein Log-Satz enthält in der Regel sowohl die Undo-Information als auch die
Redo-Information einer Änderung. Im einfachsten Fall bezieht sich ein Log-Satz
bzw. die darin protokollierte Änderung auf genau eine Seite der Datenbank.
•
Der Log-Satz beschreibt entweder
– den Zustand der Seite bzw. der geänderten Bytes vor oder nach der
Änderung (zustandsorientiertes, physisches Logging) oder
– die auszuführende Operation selbst (operationsorientiertes, logisches
Logging).
•
Ein Spezialfall des zustandsorientierten Logging ist das Protokollieren ganzer
Seiten jeweils vor und nach einer Änderung (“Before-Images” und “AfterImages”).
•
Zusätzlich werden Log-Sätze für die Beendigung von Transaktionen
(EOT und RBT) geschrieben, sowie optional auch für den Beginn von
Transaktionen (BOT).
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-86
43
... Implementierung von Logging
•
Log-Sätze sind (über Log-Puffer und Log-Datei hinweg) transaktionsweise
rückwärts verkettet. Dadurch können einzelne Transaktionen auch im laufenden
Normalbetrieb einfach zurückgesetzt werden.
•
Log-Sätze sind fortlaufend nummeriert. Die Nummer eines Logsatzes
(genannt Log Sequence Number, LSN) gibt den relativen Zeitpunkt einer
Änderung an. Sie kann auch zur Adressierung der Log-Sätze in der Log-Datei
dienen. Die LSN der jüngsten Änderung einer Seite wird in einem speziellen
Feld im Header der Seite gespeichert.
•
Der Log-Puffer muss in den folgenden Fällen in die Log-Datei auf Platte
geschrieben werden:
– Vor dem Zurückschreiben einer geänderten Seite aus dem Cache in die
Datenbank auf der Platte, sofern die Seite Änderungen von noch nicht
abgeschlossenen Transaktionen enthält: Write Ahead Logging (WAL-Prinzip)
– Unmittelbar vor dem Commit einer Transaktion, die Änderungen durchgeführt
hat: Redo-Log vor Commit
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-87
Logging im Normalbetrieb: Übersicht
DB-Cache
Log-Puffer
Page
6789
Page
4321
LSN 72:
LSN 72
LSN 44
LSN 71:
Page
1234
Page
7890
LSN 60
LSN 71
...
...
DBMS
Page
6789
LSN 47
Datenbank
FS 2014
...
Page
1234
LSN 70:
LSN 60
LSN 69:
...
Datenbanken (CS243) – Transaktionsverwaltung
...
...
Log-Datei
7-88
44
Warmstart nach einem Crash: Vorgehen
1. Analysephase: Die Log-Datei wird sequentiell gelesen (in aufsteigender LSNReihenfolge). Dabei wird bestimmt, welche Transaktionen vor dem Crash
beendet wurden (“Gewinner”; Commit-Logsatz ist vorhanden) und welche
unvollendet waren (“Verlierer”; kein Commit-Logsatz).
2. Redo-Phase: Die Log-Datei wird nochmals sequentiell gelesen
(in aufsteigender LSN-Reihenfolge). Dabei werden die Änderungen der Gewinner
wiederholt, sofern die Änderungen noch nicht in der Datenbank enthalten sind.
Dazu wird getestet, ob die LSN des Log-Satzes grösser ist als die LSN im Header
der betreffenden Seite (d.h. ob die Seite in der Log-Datei jünger ist als die in der
DB). Wenn dies der Fall ist, wird die Änderung wiederholt. Dieser Test stellt die
Idempotenz von Redo sicher.
3. Undo-Phase: Die Log-Datei wird nochmals sequentiell gelesen
(in absteigender LSN-Reihenfolge). Dabei werden die Änderungen der Verlierer
rückgängig gemacht, sofern die Änderungen in der Datenbank enthalten sind.
Dazu wird getestet, ob die LSN des Log-Satzes kleiner oder gleich der LSN im
Header der betreffenden Seite ist. Wenn dies der Fall ist, wird die Änderung
rückgängig gemacht. Dieser Test stellt die Idempotenz von Undo sicher.
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-89
Einbring-Strategien
Recovery-Algorithmen unterscheiden sich ja nach Art (und Zeitpunkt), zu dem
geänderte Daten in die DB eingebracht werden (Einbring-Strategien)
Update-in-Place (steal):
• Das Einbringen von Änderungen in die DB ist jederzeit, also auch vor dem
Commit der entsprechenden Transaktion, möglich. Die DB kann daher solche
“dirty pages” dem Cache stehlen (steal-Strategie).
• Konsequenzen für Recovery:
– Undo-Logsätze (“Before Images”) müssen vorher geschrieben werden
– Durch erforderliches Undo wird der Warmstart sehr aufwändig
Schattenspeicher bzw. Deferred-Update (no-steal):
• Änderungen werden verzögert eingebracht, z.B. am Ende einer Transaktion
• Konsequenzen für Recovery:
– Kein Undo erforderlich (transaktionsorientierter Schattenspeicher)
– Nachteil: Zerstörung des Clustering; Umrechnungstabellen werden benötigt
FS 2014
Datenbanken (CS243) – Transaktionsverwaltung
7-90
45
Zusammenfassung: Recovery-Strategien
Neben den Einbring-Strategien ist auch noch relevant, wann Änderungen
abgeschlossener Transaktionen in die DB ausgelagert werden
(Auslagerungsstrategien):
– force: erzwingt die Auslagerung der Änderungen zum Commit-Zeitpunkt
– no-force: erlaubt die Auslagerung nach dem Commit
Durch die Kombination von Auslagerungs- und Einbringstrategien lassen sich vier
Recovery-Varianten unterscheiden:
– steal/no-force:
verlangt sowohl Undo als auch Redo in der
Warmstart-Phase
– steal/force:
verlangt Undo, benötigt aber kein Redo
– no-steal/no-force: da keine dirty pages in die DB geschrieben werden ist
kein Undo nötig, durch no-force eventuell aber Redo
– no-steal/force:
FS 2014
erfordert weder Undo noch Redo. Dieser Gewinn wird
jedoch erkauft durch den deutlich grösseren Aufwand
im regulären Betrieb
Datenbanken (CS243) – Transaktionsverwaltung
7-91
46
Document
Kategorie
Technik
Seitenansichten
3
Dateigröße
495 KB
Tags
1/--Seiten
melden