View
108
Download
1
Category
Preview:
Citation preview
SS 2004 B. König-Ries: Datenbanksysteme 5-1
Kapitel 5: Transaktionsverwaltung
TransaktionsmodellIsolationAtomizitätDauerhaftigkeit
Folien: © Prof. Lockemann, IPD, Uni Karlsruhe
SS 2004 B. König-Ries: Datenbanksysteme 5-2
Kapitel 5: Transaktionsverwaltung
Transaktionsmodell
Isolation
Atomizität
Dauerhaftigkeit
SS 2004 B. König-Ries: Datenbanksysteme 5-3
Zur Erinnerung
Transaktionsprozedur: Folge primitiver Operationen als Einheit der Konsistenz und der Robustheit.
Transaktion (TA): Ausführung einer Transaktionsprozedur mit gewissen Garantien für Konsistenz und Robustheit.
Transaktionsverwaltung (TAV): Steuerung einer Menge auch überlappender Transaktionen unter Wahrung von Konsistenz und Robustheit unter Berücksichtigung weiterer Merkmale wie Performanz.
SS 2004 B. König-Ries: Datenbanksysteme 5-4
Verantwortlichkeiten (1)
Ausgangspunkt: Transaktion ist Konsistenzeinheit: Konsistenz (engl. consistency): Eine Transaktion bewirkt einen
konsistenten Zustandsübergang, d.h. sie führt auf einen konsistenten Datenbasiszustand, sofern sie zu Beginn auf einem konsistenten Datenbasiszustand aufsetzte.
Dies ist eine Forderung der Transaktionsverwaltung (TAV) an die Transaktion. Nur wenn sie erfüllt ist, kann die TAV die Konsistenz und Robustheit des Gesamtsystems zusichern.
Wegen der Veranwortlichkeit der Transaktion spricht man daher von der lokalen Konsistenz (der Transaktion).
SS 2004 B. König-Ries: Datenbanksysteme 5-5
Verantwortlichkeiten (2)
Recovery: Durchsetzen von Persistenz und Fehler-Resistenz in der folgenden Form: Atomizität (engl. atomicity): Die Transaktion hat nur als Einheit eine
Wirkung nach außen. Bis zu ihrem erfolgreichen Abschluss hinterlässt sie überhaupt keine Wirkung nach außen (Transienz), nach ihrem erfolgreichen Abschluss ist ihre Wirkung allgemein sichtbar (Persistenz).
Transienz (als Teil der Resistenz) und Persistenz sind also rein lokal auf die von der Transaktion betroffenen Zustände bezogen. Transienz bezieht sich auf den Zustand unmittelbar vor, Persistenz auf den unmittelbar nach der Transaktion.
Die Verantwortung liegt (vorrangig) beim Recovery-Verwalter als Teil der Segmentverwaltung.
SS 2004 B. König-Ries: Datenbanksysteme 5-6
Verantwortlichkeiten (3)
Dauerhaftigkeit (engl. durability): Ergänzung der Persistenz auf lange Dauer: Die Wirkung einer erfolgreich ausgeführten Transaktion geht nicht
mehr verloren, es sei denn, sie wird durch eine weitere Transaktion ausdrücklich widerrufen.
Da die Transaktion nicht mehr existiert, kann die Verantwortung nur einer eigenen Komponente (Archiv-Verwaltung) übertragen werden. Mit der Atomizität schafft sie aber die Voraussetzungen!
SS 2004 B. König-Ries: Datenbanksysteme 5-7
Verantwortlichkeiten (4)
Durchsetzen der Konsistenz einer Datenbasis für eine Menge in Konflikt stehender Transaktionen (globale Konsistenz) durch eine strenge Form der Konflikt-Resistenz: Isolation (engl. isolation): Nebenläufige Transaktionen laufen jede
für sich so ab, als ob sie alleine ausgeführt würden (keine „Vermischung“ von Zustandsübergängen).
Gleichlaufende Transaktionen sind also nicht sichtbar, jede Transaktion läuft „außer Konkurrenz“. Jegliche Wechselwirkung ist unerwünscht.
Die Verantwortung liegt beim Scheduler als Teil der Segmentverwaltung.
SS 2004 B. König-Ries: Datenbanksysteme 5-8
ACID-Eigenschaften (1)
Gut geeignet für kommerzielle Anwendungen mit: kurzlaufenden, unabhängigen Transaktionen (z.B. Buchungen), hohen Korrektheitsanforderungen.
A atomicity
C consistency
I isolation
D durability
SS 2004 B. König-Ries: Datenbanksysteme 5-9
ACID-Eigenschaften (2)
Weniger gut geeignet für: kooperative Anwendungen (z.B. CAD): Kooperatives Arbeiten (z.B.
gemeinsamer Entwurf eines Automotors) ist bei strikter Isolation nicht möglich, da Zwischenergebnisse einer Transaktion für andere nicht sichtbar sind.
langlaufende Vorgänge (z.B. interaktive Bestellung über das WWW): Bei langlaufenden, ressourcenintensiven Transaktionen ist komplettes Zurücksetzen im Fehlerfall gemäß Atomizität oft nicht akzeptabel.
statistische Analyseverfahren mit geringen Korrektheitsanforderungen, aber hohem Datendurchsatz: Vollständige Konsistenz der gelesenen Daten ist nicht erforderlich, daher ist Zusatzaufwand für ACID-Garantien nicht gerechtfertigt.
SS 2004 B. König-Ries: Datenbanksysteme 5-10
Modellierung von Transaktionen
Zur Formalisierung der ACID-Garantien muss Verhalten von Transaktionen modelliert werden.
Folge aus der Forderung nach lokaler Konsistenz: Die Transaktionsverwaltung soll nichts über die Semantik der TA wissen müssen.
Annahme: Die TA teilt der TAV auch nichts darüber mit. Folge: Die TAV ist auf das beobachtbare Verhalten der TA
angewiesen: Dies sind die Bekanntgabe der Transaktionsgrenzen sowie die Transportvorgänge zwischen Arbeitsspeicher der TA und dem Hintergrundspeicher, also die individuellen Lese- und Schreibzugriffe.
SS 2004 B. König-Ries: Datenbanksysteme 5-11
Lese-Schreib-Modell
Transaktionsverwaltung eines DBMS arbeitet daher mit einfachem Lese-Schreib-Modell von Transaktionen: Bearbeitung der Daten erfolgt in einem privaten
Arbeitsspeicherbereich der Transaktion. Transaktionen können durch Operationen read(x) und write(x)
Transfer eines Datenelements x (z.B. Block, Tupel oder Relation) vom Hintergrund- in den Arbeitsspeicher und umgekehrt anfordern.
Transaktionen können durch Operationen commit und abort erfolgreichen bzw. nicht erfolgreichen Abschluss mitteilen. Im ersten Fall müssen alle durchgeführten write-Operationen dauerhaft, im zweiten rückgängig gemacht werden.
Interaktion von Transaktionen mit der Datenbasis beschränkt sich auf die Operationen read, write, commit und abort. Nur diese werden von der Transaktionsverwaltung bearbeitet.
SS 2004 B. König-Ries: Datenbanksysteme 5-12
Formale Beschreibung von Transaktionen (1)
Eine Operation o hat eine der folgenden vier Formen: ri(x) Lesen von Datenelement x durch Transaktion i
wi(x) Schreiben von Datenelement x durch Transaktion i
ci Abschluss von Transaktion i
ai Abbruch von Transaktion i
(Wenn es auf Details nicht ankommt, werden Operationen kurz als oi bzw. oi(x) notiert.)
SS 2004 B. König-Ries: Datenbanksysteme 5-13
Formale Beschreibung von Transaktionen (2)
Eine Transaktion ist eine total geordnete Menge Ti von Operationen mit: Ti {ri(x), wi(x) | x Datenelement} {ai, ci}.
Ti kann höchstens eine der Operationen ai oder ci enthalten.
Falls Ti ai oder ci enthält, so ist dies die letzte Operation in Ti.
Falls es o,o' Ti gibt mit o = ri(x), o' = wi(x), so folgt o < o'.
Konsequenzen aus Definition: Transaktion kann, muss aber nicht abgeschlossen sein. Mehrfaches Lesen oder Schreiben desselben Datums nicht
zulässig. Schreiben und anschließendes Lesen eines Datums nicht zulässig.
SS 2004 B. König-Ries: Datenbanksysteme 5-14
Lese-Schreib-Modell: Beispiele
Relationen TICKET (ticketNr, name) T BUCHUNG (flugNr, ticketNr, platzCode, datum) B
Transaktionen: T1: Prüfen der Konsistenz von Passagierlisten und Buchungen,
T2: Umbuchung einer Gruppe von Passagieren,
T3: Stornieren einer Buchung. Vereinfachende Annahmen:
Bei Lese- und Schreib-Operationen werden stets die gesamten Relationen zwischen Hintergrund- und Arbeitsspeicher übertragen.
SS 2004 B. König-Ries: Datenbanksysteme 5-15
Beispiel-Transaktion T1
Transaktion T1 druckt Anzahl der für den 12. August 2000 verkauften Tickets sowie Liste der Inhaber aus:
select count (distinct ticketNr)from BUCHUNGwhere datum = 12-AUG-00;drucke Anzahl der verkauften Tickets;select namefrom TICKETwhere ticketNr in
(select ticketNr from BUCHUNG where datum = 12-AUG-00);
drucke Passagierliste;commit;
Lesen von BUCHUNG
Lesen von TICKET
BUCHUNG schon gelesen
Transaktionsbeschreibung von T1 : r1(B) r1(T) c1 .
SS 2004 B. König-Ries: Datenbanksysteme 5-16
Beispiel-Transaktion T2
Transaktion T2 bucht Passagiere in Reihe 19 (Bender, Kuhn und Weinand) auf LH500 vom 12. August 2000 auf 11. August 2000 um und versieht Ticketnummer mit Änderungsvermerk :update TICKET set ticketNr = ticketNr + 100000where ticketNr in
(select ticketNr from BUCHUNG where datum = 12-AUG-00 and flugNr = "LH500" and (platzCode = "19D" or platzCode = "19E"
or platzCode = "19G" ));update BUCHUNGset datum = 11-AUG-00, ticketNr = ticketNr + 100000where datum = 12-AUG-00 and flugNr = "LH500"and (platzCode = "19D" or platzCode = "19E" or platzCode = "19G");commit;
Lesen von BUCHUNG
Lesen von TICKET
BUCHUNG schon gelesen
Schreiben von TICKET
Schreiben von BUCHUNG
SS 2004 B. König-Ries: Datenbanksysteme 5-17
Beispiel-Transaktion T2
Transaktion T2 bucht Passagiere in Reihe 19 (Bender, Kuhn und Weinand) auf LH500 vom 12. August 2000 auf 11. August 2000 um und versieht Ticketnummer mit Änderungsvermerk :update TICKET set ticketNr = ticketNr + 100000where ticketNr in
(select ticketNr from BUCHUNG where datum = 12-AUG-00 and flugNr = "LH500" and (platzCode = "19D" or platzCode = "19E"
or platzCode = "19G" ));update BUCHUNGset datum = 11-AUG-00, ticketNr = ticketNr + 100000where datum = 12-AUG-00 and flugNr = "LH500"and (platzCode = "19D" or platzCode = "19E" or platzCode = "19G");commit;
Lesen von BUCHUNG
Lesen von TICKET
BUCHUNG schon gelesen
Transaktionsbeschreibung von T2 : r2(B) r2(T) w2(T) w2(B) c2 .
Schreiben von TICKET
Schreiben von BUCHUNG
Nicht anzusehen, dass die geschriebenen Werte von beiden gelesenen Werten abhängen
SS 2004 B. König-Ries: Datenbanksysteme 5-18
Beispiel-Transaktion T3
Transaktion T3 storniert Ticket Nr. 7216087338:
delete from TICKET where ticketNr = 7216087338;
delete from BUCHUNGwhere ticketNr = 7216087338;
commit;
Transaktionsbeschreibung von T3 : r3(T) w3(T) r3(B) w3(B) c3 .
Lesen von BUCHUNG
Lesen von TICKET
Schreiben von TICKET
Schreiben von BUCHUNG
SS 2004 B. König-Ries: Datenbanksysteme 5-19
Schedules
Bei nebenläufiger Bearbeitung von Transaktionen müssen die Operationen der einzelnen Transaktionen (sog. lokale Schedules) in eine globale Reihenfolge gebracht werden. Dadurch entsteht ein globaler Schedule.
Aufgabe des Schedulers: Herbeiführung eines globalen Schedules, der den ACID-Anforderungen genügt.
Transaktion 1 Transaktion 2 ... Transaktion n
Scheduler
Datenbasis-Manager
Schedule 1 Schedule n
Globaler robuster Schedule
SS 2004 B. König-Ries: Datenbanksysteme 5-20
Schedules: Beispiele
Betrachte:T1 : r1(B) r1(T) c1
T2 : r2(B) r2(T) w2(T) w2(B) c2
Ein globaler Schedule:S1: r1(B) r2(B) r2(T) w2(T) w2(B) c2 r1(T) c1
Ein weiterer globaler Schedule:S2: r2(B) r2(T) r1(B) r1(T) w2(T) w2(B) c2 c1
Sind sie robust, genügen sie also den ACID-Anforderungen?
SS 2004 B. König-Ries: Datenbanksysteme 5-21
Kapitel 5: Transaktionsverwaltung
Transaktionsmodell
Isolation
Atomizität
Dauerhaftigkeit
SS 2004 B. König-Ries: Datenbanksysteme 5-22
Aufgabe
1. Teilaufgabe des Schedulers: Verzahnung der einzelnen Operationsfolgen muss so erfolgen, dass unerwünschte Wechselwirkungen vermieden werden.
Im Folgenden Illustration der Probleme, die bei inkorrekter Verzahnung nebenläufiger Transaktionen entstehen können.
SS 2004 B. König-Ries: Datenbanksysteme 5-23
Beispiel
Wir betrachten die Relationen Weißweine und Verkäufe aus der Datenbasis eines Weinhändlers:
Auf diese Datenbasis werde gleichzeitig von verschiedenen Verkäufern zugegriffen
WeißweineArtikel BestandGutedel 12Riesling 34Silvaner 2Weißburgunder 11Müller Thurgau 100
VerkäufeArtikel Kunde MengeGutedel Adam 2Riesling Adam 4Gutedel Breit 6Silvaner Breit 4
SS 2004 B. König-Ries: Datenbanksysteme 5-24
R/W-Modell (Beispiel)
Verkaufs-Transaktion (R: Riesling)
wird vereinfacht zu: r[R] w[R]
(Berechnung innerhalb der Transaktion wird nicht berücksichtigt!)
Schritt 1 read(R) 2 update(R) 3 write(R)
SS 2004 B. König-Ries: Datenbanksysteme 5-25
Beispiel 1 für Lost Update
Die Verkäufer Müller und Schmidt sind beide gerade dabei Riesling zu verkaufen. Dazu lesen sie zunächst die aktuellen Bestände aus der Relation Weißweine aus, ändern diese dann und schreiben sie schließlich zurück.
Herr Müller habe eine Kiste Riesling (R) verkauft, Herr Schmidt zwei.
Es werde jeweils auf ein Tupel zugegriffen. Angenommen die Prozesse laufen zeitlich wie folgt verzahnt ab:
Zeit Müller Schmidt Wert in DB Kommentar 1 read(R) 34 2 read(R) 34 3 update(R) 34 Müller verkauft eine Kiste 4 update(R) 34 Schmidt verkauft zwei Kisten 5 write(R) 33 34-1 6 write(R) 32 34-2
WeißweineArtikel BestandGutedel 12Riesling 34Silvaner 2Weißburgunder 11Müller Thurgau 100
SS 2004 B. König-Ries: Datenbanksysteme 5-26
Beispiel 1 für Lost Update
Analyse:
Der in der Datenbasis erfasste Endbestand an Riesling ist nicht, wie es korrekt wäre, 31 Kisten, sondern 32.
Die durch Hr. Müller eingebrachte Änderung ist verloren gegangen (lost update). Also Verstoß gegen lokale Konsistenz von Prozess „Müller“.
Schema:
r1[R] r2[R] w1[R] w2[R]
w1[R] geht verloren.
SS 2004 B. König-Ries: Datenbanksysteme 5-27
Beispiel 2 für Dirty Read
Dirty read: Lesen eines durch eine andere Transaktion geänderten Wertes, dessen Gültigkeit zum Zeitpunkt des Lesens noch nicht feststeht.
SS 2004 B. König-Ries: Datenbanksysteme 5-28
Beispiel 2 für Dirty Read
Gegeben sei wieder die obige Situation. Wieder verkaufen die Herren Müller und Schmidt Riesling. Diesmal überlegt es sich allerdings der Käufer von Hr. Müller im letzten Moment anders und Hr. Müller ist gezwungen, die Verkaufstransaktion abzubrechen:
Zeit Müller Schmidt Wert in DB Kommentar 1 read(R) 34 2 update(R) 34 Hr.M. verkauft eine Kiste 3 write(R) 33 34-1 4 read(R) 33 Hr.S. liest den geänderten Wert 5 update(R) 33 Hr.S. verkauft zwei Kisten 6 abort 34 Hr.M. storniert 7 write(R) 31 33-2
WeißweineArtikel BestandGutedel 12Riesling 34Silvaner 2Weißburgunder 11Müller Thurgau 100
SS 2004 B. König-Ries: Datenbanksysteme 5-29
Beispiel 2 für Dirty Read
Analyse: Hr. Schmidt hat einen im Nachhinein gesehen falschen Wert
gelesen.Schema:
r1[R] w1[R] r2[R] a1
r2[R] liest illegitimen Wert R.Anmerkungen: Dirty read kann immer dann vorkommen, wenn eine Transaktion
einen Wert einer anderen Transaktion vor deren commit liest.
SS 2004 B. König-Ries: Datenbanksysteme 5-30
Beispiel 3 für inconsistent read
inconsistent read: Lesen von Zuständen, die aus Sicht der Transaktion zu unterschiedlichen Zeitpunkten gültig sind. Im einfachsten Fall möglich, wenn eine Transaktion von einer zweiten nebenläufigen Transaktion liest.
Jetzt sieht nämlich die betrachtete Transaktion keinen konsistenten Zustand.
Bei einer rein lesenden Transaktion mag dies gelegentlich tolerierbar sein.
SS 2004 B. König-Ries: Datenbanksysteme 5-31
Beispiel 3 für inconsistent read
Die Herren Müller und Schmidt führen zum Jahresabschluss eine Inventur ihrer Bestände durch. Hr. Müller fragt die Bestände der einzelnen Sorten bei der Relation Weißweine ab und errechnet den Gesamtbestand. Hr. Schmidt stellt unterdessen fest, dass 10 Kisten Gutedel irrtümlich als Müller-Thurgau erfasst wurden. Er korrigiert die entsprechenden Bestände in der Relation.
Zeit Müller Schmidt1 sum:=02 read(Gutedel)3 sum:=124 read(Riesling) read(Müller-Th.)5 sum:=12+34 Müller-Th.:= Müller-Th.-106 read(Silvaner) write(Müller-Th.)7 sum:= 46+2 read(Gutedel)8 read(Weißb.) Gutedel:=Gutedel+109 sum:= 48+11 write(Gutedel)10 read(Müller-Th.)11 sum:= 59+90
SS 2004 B. König-Ries: Datenbanksysteme 5-32
Beispiel 3 für inconsistent read
WeißweineArtikel BestandGutedel 12Riesling 34Silvaner 2Weißburgunder 11Müller Thurgau 100
Zeit Müller Schmidt1 sum:=02 read(Gutedel)3 sum:=124 read(Riesling) read(Müller-Th.)5 sum:=12+34 Müller-Th.:= Müller-Th.-106 read(Silvaner) write(Müller-Th.)7 sum:= 46+2 read(Gutedel)8 read(Weißb.) Gutedel:=Gutedel+109 sum:= 48+11 write(Gutedel)10 read(Müller-Th.)11 sum:= 59+90Gutedel: gültig zu
Beginn von T1
Müller-Thurgau: gültig mitten in T1
SS 2004 B. König-Ries: Datenbanksysteme 5-33
Beispiel 3 für inconsistent read
Analyse:
Hr. Müller hat einen um 10 Flaschen zu geringen Bestand ermittelt.
Schema:
r1[G]r1[R]r2[M]r1[S]w2[M]r2[G]r1[W]w2[G]c2r1[M]c1
r1[G] vor w2[G], aber r1[M] nach w2[M].
SS 2004 B. König-Ries: Datenbanksysteme 5-34
Serialisierbarkeitsprinzip
Isolationsprinzip scheint zunächst streng serielle Abwicklung der Transaktionen zu fordern:
r1(x) r1(y) ... w1(z) c1 r2(u) r2(v) ... w2(w) c2 r3(r) r3(s) ... w3(t) c3 ...
(sogenannter serieller Schedule). Serielle Schedules sind aber viel zu ineffizient, da keinerlei
Nebenläufigkeit möglich. Da Isolation nur besagt: „Jede Transaktion muss ablaufen, als ob sie
alleine abliefe“, muss von korrekten Schedules nur Äquivalenz zu seriellen Schedules verlangt werden.
Daher Betrachtung von serialisierbaren Schedules, wobei je nach Äquivalenzbegriff unterschiedliche Definitionen möglich sind.
SS 2004 B. König-Ries: Datenbanksysteme 5-35
Veranschaulichung von Schedules (1)
Beispiel: Scheduler1(h) r2(a) r1(f) r2(e) w2(h) r3(a) r1(i) r1(d) w1(d) w1(f) r1(b) r2(g) w1(h) r2(d) w1(c) w2(c) r1(e) w1(i) c1 w3(h) c2 c3.
Schreibzugriff durch T2
Schreibzugriff durch T3
Lesezugriff durch T2
Lesezugriff durch T3
Legende:
Schreibzugriff durch T1Lesezugriff durch T1
Zeit
Daten-elemente
a
b
c
d
e
f
g
h
i
SS 2004 B. König-Ries: Datenbanksysteme 5-36
Veranschaulichung von Schedules (2)
Beispiel: serieller Scheduler1(h) r1(f) r1(i) r1(d) w1(d) w1(f) r1(b) w1(h) w1(c) r1(e) w1(i) c1 r2(a) r2(e) w2(h) r2(g) r2(d) w2(c) c2 r3(a) w3(h) c3.
Zeit
Daten-elemente
a
b
c
d
e
f
g
h
i
Schreibzugriff durch T2
Schreibzugriff durch T3
Lesezugriff durch T2
Lesezugriff durch T3
Legende:
Schreibzugriff durch T1Lesezugriff durch T1
SS 2004 B. König-Ries: Datenbanksysteme 5-37
Veranschaulichung von Schedules (3)
Vereinfachte Darstellung desselben seriellen Schedules durch Annahme unendlich kurzer Ausführungszeiten für Operationen möglich.
Jede Transaktion läuft damit konzeptuell zu einem bestimmten Zeitpunkt, dem Äquivalenzzeitpunkt.
Schreibzugriff durch T2
Schreibzugriff durch T3
Lesezugriff durch T2
Lesezugriff durch T3
Legende:
Schreibzugriff durch T1Lesezugriff durch T1
Zeit
Daten-elemente
a
b
c
de
f
g
h
i
Zeit
Daten-elemente
a
b
c
d
e
f
g
h
iT1 T2 T3
SS 2004 B. König-Ries: Datenbanksysteme 5-38
Serialisierbarkeit: Hilfsdefinitionen (1)
Sei S globaler Schedule, der durch Verzahnung von Transaktionen T1, T2, ..., Tk entstanden ist.
Eine Umordnung von S ist ein Schedule S', der dieselben Operationen wie S enthält und die Ordnung der Operationen innerhalb einer Transaktion erhält (d.h., beim Übergang von S zu S' wurden nur Operationen verschiedener Transaktionen vertauscht).
Eine serielle Umordnung von S ist eine Umordnung von S, die zugleich ein serieller Schedule ist.
SS 2004 B. König-Ries: Datenbanksysteme 5-39
Serialisierbarkeit: Hilfsdefinitionen (2)
Tj liest x von Ti in S, falls es Operationen wi(x) und rj(x) in S gibt mit:
wi(x) erfolgt vor rj(x).
ai und aj nicht in S.
Es gibt keine Operation wk(x) zwischen wi(x) und rj(x), es sei denn ak ist in S.
Ti finalisiert x in S, wenn Ti den Endzustand von x in S schreibt, d.h.:
S enthält eine Schreiboperation wi(x).
Nach wi(x) erfolgt kein Aufruf von ai.
Es gibt keine Operation wk(x) nach wi(x), es sei denn, nach wk(x) erfolgt Aufruf von ak.
SS 2004 B. König-Ries: Datenbanksysteme 5-40
Serialisierbarkeit: Hilfsdefinitionen (3)
Zwei Operationen o und o' in S sind unverträglich, wenn gilt: o und o' sind Lese- oder Schreiboperationen auf demselben
Datenelement. o und o' werden von verschiedenen Transaktionen ausgeführt. Mindestens eine der beiden Operationen ist eine Schreiboperation.
SS 2004 B. König-Ries: Datenbanksysteme 5-41
Konfliktserialisierbarkeit
Definition: Schedule S ist konfliktserialisierbar, wenn es serielle Umordnung
S' von S gibt, sodass für alle unverträglichen Operationen o und o' gilt:o liegt vor o' in S o liegt vor o' in S'.
S' heißt konfliktäquivalenter serieller Schedule zu S.
Intuition: Alle Operationen, die potenziell Wechselwirkungen verursachen
könnten, haben im realen Schedule und im äquivalenten seriellen Schedule dieselbe Reihenfolge.
SS 2004 B. König-Ries: Datenbanksysteme 5-42
Konfliktserialisierbarkeit: Veranschaulichung
Existenz eines konfliktäquivalenten seriellen Schedules bedeutet: Operationen einer jeden Transaktion lassen sich auf Äquivalenzzeitpunkt zusammenziehen, ohne unverträgliche Operationen zu vertauschen.
Durchführung für Schedule von vorhin zeigt:(für beliebige Wahl der Äquivalenzzeitpunkte)
Zeit
Daten-elemente
a
b
c
de
f
g
h
iT1 T2 T3
unmöglich
Schreibzugriff durch T2
Schreibzugriff durch T3
Lesezugriff durch T2
Lesezugriff durch T3
Legende:
Schreibzugriff durch T1Lesezugriff durch T1
SS 2004 B. König-Ries: Datenbanksysteme 5-43
Prüfung auf Serialisierbarkeit (1)
Serialisierbarkeit bezieht sich grundsätzlich auf (erfolgreich) abgeschlossene Transaktionen, da abgebrochene Transaktionen aufgrund von Atomizität keine sichtbaren Auswirkungen haben dürfen und der Ausgang noch laufender Transaktionen offen ist.
Bei Prüfung eines Schedule S auf Serialisierbarkeit daher zunächst Bildung der abgeschlossenen Projektion CP(S) durch Eliminieren der Operationen aller (noch) nicht mit commit abgeschlossenen Transaktionen.
SS 2004 B. König-Ries: Datenbanksysteme 5-44
Prüfung auf Serialisierbarkeit (2)
Konfliktserialisierbarkeit ist relativ effizient zu entscheiden. Einfaches Kriterium: Zyklusfreiheit des Serialisierbarkeitsgraphen
SG(S), der wie folgt konstruiert wird: SG(S) enthält einen Knoten Ki für jede in CP(S) vorkommende
Transaktion Ti.
Für jedes in CP(S) vorkommender Paar unverträglicher Operationen oi(x), oj(x) mit oi(x) vor oj(x) füge in SG(S) Kante von Ki nach Kj ein. (Bedeutung: In jedem zu CP(S) konfliktäquivalenten seriellen Schedule muss Ti vor Tj stattfinden.)
Wenn SG(S) einen Zyklus enthält, ist CP(S) nicht konfliktserialisierbar, ansonsten liefert jede topologische Sortierung von SG(S) einen konfliktäquivalenten seriellen Schedule.
SS 2004 B. König-Ries: Datenbanksysteme 5-45
Prüfung auf Serialisierbarkeit (3)
Aufbau des Serialisierbarkeitsgraphen für Beispiel-Schedule:
T1
T2
T3
Schreibzugriff durch T2
Schreibzugriff durch T3
Lesezugriff durch T2
Lesezugriff durch T3
Legende:
Schreibzugriff durch T1Lesezugriff durch T1
Zeit
Daten-elemente
a
b
c
de
f
g
h
i
SS 2004 B. König-Ries: Datenbanksysteme 5-46
Prüfung auf Serialisierbarkeit (4)
Frühere Schedules:S1: r1(B) r2(B) r2(T) w2(T) w2(B) c2 r1(T) c1 S2: r2(B) r2(T) r1(B) r1(T) c1 w2(T) w2(B) c2
S3: r2(B) r2(T) w2(T) r1(B) r1(T) c1 w2(B) c2
S4: r2(B) r2(T) w2(T) w2(B) r1(B) r1(T) a2 c1 nur T1 in CP!
S5: r3(T) w3(T) r2(B) r2(T) w2(T) w2(B) c2 r3(B) w3(B) c3
S6: r2(B) r2(T) r3(T) w3(T) r3(B) w3(B) c3 w2(T) w2(B) c2
T1 T2S1: T1 T2S3:T1 T2S2: T2 T3S5: T2 T3S6:
SS 2004 B. König-Ries: Datenbanksysteme 5-47
Prüfung auf Serialisierbarkeit (5)
Neuer Schedule:
S7:
r1(B) r2(B) r2(T) r1(T) w2(T) r3(T) w3(T) w2(B) r3(B) w3(B) c1 c2 c3
T1 T2S7: T3
Äquivalenter serieller Schedule: T1 T2 T3Betrachte:
S8: r2(B) r3(T) w2(B) r1(B) w3(T) r1(T) c1 c2 c3
T1T2
S8:T3
Äquivalenter serieller Schedule: T2 T3 T1 und T3 T2 T1
SS 2004 B. König-Ries: Datenbanksysteme 5-48
Transaktion 1 Transaktion 2 ... Transaktion n
Synchronisation durch Scheduler
Datenbasis-Verwalter
lokaler Schedule 1 lokaler Schedule n
konfliktserialisierbarer globaler Schedule
Synchronisation (1)
SS 2004 B. König-Ries: Datenbanksysteme 5-49
Scheduler muss spätestens bei Ausführung von ci entscheiden, wann Ti im äquivalenten seriellen Schedule stattgefunden haben soll (Festlegung des Äquivalenzzeitpunkts von Ti).
Ferner muss real durchgeführter Schedule zum gedachten seriellen Schedule sichten- bzw.konfliktäquivalent sein.
Für noch laufende Transaktionen kann Scheduler sich Entscheidung offen halten, da für Serialisierbarkeit nur abgeschlossene Projektion des Schedules relevant ist.
Transaktion 1 Transaktion 2 ... Transaktion n
Synchronisation durch Scheduler
Datenbasis-Verwalter
lokaler Schedule 1 lokaler Schedule n
konfliktserialisierbarer globaler Schedule
Synchronisation (2)
c1
Spielräume!
SS 2004 B. König-Ries: Datenbanksysteme 5-50
Transaktion 1 Transaktion 2 ... Transaktion n
Synchronisation durch Scheduler
Datenbasis-Verwalter
lokaler Schedule 1 lokaler Schedule n
konfliktserialisierbarer globaler Schedule
Synchronisation (3)
o1(x)
Mögliche Scheduler-Entscheidungen: Sofortige Ausführung der Operation durch Übermittlung an
Datenbasis-Verwalter. Zurückstellung (durch Blockierung der zugehörigen Transaktion). Abbruch der zugehörigen Transaktion (und Rücksetzen aller bisher
von ihr ausgeführten Operationen durch den Datenbasis-Verwalter).
Ausführung einer bisher zurückgestellten Operation.
SS 2004 B. König-Ries: Datenbanksysteme 5-51
Synchronisation (4)
Synchronisationsverfahren wird somit spezifiziert durch: Algorithmus zur Zuordnung von Äquivalenzzeitpunkten zu
Transaktionen.
Zeitpunkt, zu dem diese Zuordnung festgelegt, d.h. Transaktion in gedachten seriellen Schedule eingeordnet wird.
Verfahren, mit dem Äquivalenz des realen zum gedachten seriellen Schedule garantiert wird.
begin TA vs. commit
vor vs. während vs. bei commit der TA
Pessimistische Verfahren Optimistische Verfahren
SS 2004 B. König-Ries: Datenbanksysteme 5-52
Synchronisation (4)
Synchronisationsverfahren wird somit spezifiziert durch: Algorithmus zur Zuordnung von Äquivalenzzeitpunkten zu
Transaktionen. Zeitpunkt, zu dem diese Zuordnung festgelegt, d.h. Transaktion in
gedachten seriellen Schedule eingeordnet wird.
Verfahren, mit dem Äquivalenz des realen zum gedachten seriellen Schedule garantiert wird.
begin TA vs. commit
vor vs. während vs. bei commit der TA
Pessimistische Verfahren
Synchronisation mit SperrenSynchronisation mit Zeitstempeln
SS 2004 B. König-Ries: Datenbanksysteme 5-53
Synchronisation mit Sperren
Sperrenbasierte Synchronisation = Gewinnung konfliktserialisierbarer Schedules ohne explizite Verwaltung des Serialisierbarkeitsgraphen (wäre viel zu aufwändig).
Intuition: Für jede Transaktion wird als Äquivalenzzeitpunkt Zeitpunkt des
commits gewählt. Äquivalenz des realen und seriellen Schedules wird gesichert,
indem jede Operation oi(x), o{r,w}, das Datenelement x im Zeitintervall zwischen oi(x) und ci für unverträgliche Operationen anderer Transaktionen sperrt.
Falls benötigte Sperre nicht sofort verfügbar ist, muss Transaktion bis zur Freigabe warten.
SS 2004 B. König-Ries: Datenbanksysteme 5-54
Sperren
Transaktionen stehen drei Sperr-Operationen zur Verfügung: s(x) setzt share-Sperre auf Datenelement x, die fremde Schreib-
Operationen ausschließt; x(x) setzt exclusive-Sperre auf Datenelement x, die fremde Schreib-
und Lese-Operationen ausschließt; u(x) löst Sperre auf Datenelement x.
Entwurfsspielräume für Sperren: Sperrgranulat: Feinheit der Unterteilung der Datenbasis für
Sperrzwecke: Relation, Tupel, Tupelkomponente. Sperrart: Art der Festlegung der zu sperrenden Elemente.
Objektsperre: Datenelemente werden explizit angegeben. Prädikatsperre: Datenelemente werden implizit durch logisches
Prädikat spezifiziert.
SS 2004 B. König-Ries: Datenbanksysteme 5-55
Sperrverträglichkeit
Sperren derselben Transaktion sind stets miteinander verträglich. Für Sperren verschiedener Transaktionen gilt folgende
Verträglichkeitstabelle:
– S X
S –
X – –
Belegung
Anforderung
SS 2004 B. König-Ries: Datenbanksysteme 5-56
Strenges Zwei-Phasen-Sperrprotokoll
Umsetzung: Strenges Zwei-Phasen-Sperrprotokoll (S2PL). Regeln:
Jede Transaktion muss vor Ausführung einer Operation ri(x) oder wi(x) eine s-Sperre bzw. eine x-Sperre auf x anfordern, dabei darf eine s-Sperre zu einer x-Sperre verschärft werden.
Alle Sperren müssen bis zum commit oder abort gehalten werden. Datenelemente dürfen nicht mit unverträglichen Sperren belegt
werden; ggf. muss eine Transaktion, die eine Sperre benötigt, warten.
Resultat: Realer Schedule S ist konfliktäquivalent zu seriellem Schedule, der entsteht, wenn alle Transaktionen komplett zum Zeitpunkt ihres commits in S ausgeführt werden.
SS 2004 B. König-Ries: Datenbanksysteme 5-57
S2PL: Graphische Darstellung
Platzierung der Sperren:
Anzahl der gehaltenen Sperren:
Zeit
AnzahlSperren Anforderungsphase Freigabephase
Zeit
Daten-elemente
a
b
c
de
f
g
h
iCommitT1
Legende:
Schreibzugriff durch T1Lesezugriff durch T1
shared-Sperre von T1exclusive-Sperre von T1
SS 2004 B. König-Ries: Datenbanksysteme 5-58
S2PL: Beispiel
Beispiel-Transaktionen:
T1 : s1(B) r1(B) s1(T) r1(T) u1(B) u1(T) c1
T2 : s2(B) r2(B) s2(T) r2(T) x2(T) w2(T) x2(B) w2(B) u2(T) u2(B) c2
Sperrenverschärfung
Vereinfachung - keine Sperrenverschärfung:
T1 : s1(B) r1(B) s1(T) r1(T) u1(B) u1(T) c1
T2 : x2(B) r2(B) x2(T) r2(T) w2(T) w2(B) u2(T) u2(B) c2
Schedule S1: r1(B) r2(B) r2(T) w2(T) w2(B) c2 r1(T) c1 lässt sich nicht mehr konstruieren:s1(B) r1(B) x2(B) Fehlschlag, T2 blockiert, T1 fortgesetzt, z.B.
s1(T) r1(T) u1(B) u1(T) c1 x2(B) r2(B) r2(T) x2(T) w2(T) w2(B) u2(T) u2(B) c2.
Sperranweisungen herausprojiziert:r1(B) r1(T) c1 r2(B) r2(T) w2(T) w2(B) c2. rein seriell
SS 2004 B. König-Ries: Datenbanksysteme 5-59
Verklemmung: Beispiel
Beispiel-Transaktionen:
T1 : s1(B) r1(B) s1(T) r1(T) u1(B) u1(T) c1
T2 : s2(B) r2(B) s2(T) r2(T) x2(T) w2(T) x2(B) w2(B) u2(T) u2(B) c2
Schedule S1: r1(B) r2(B) r2(T) w2(T) w2(B) c2 r1(T) c1 lässt sich nicht mehr konstruieren:
s1(B) r1(B) s2(B) r2(B) s2(T) r2(T) x2(T) w2(T) x2(B) Fehlschlag, T2 blockiert
T1 fortgesetzt, s1(T) Fehlschlag, T1 blockiert
--- keine Fortsetzung möglich ---
SS 2004 B. König-Ries: Datenbanksysteme 5-60
Verklemmungen
Bei sperrenbasierter Synchronisation können sogenannte Verklemmungen (engl. deadlocks) auftreten, in denen Transaktionen sich gegenseitig durch ihre Sperren blockieren.
Folgerung: Sperrenbasiertes Scheduling ist zwar pessimistisch, kann aber trotzdem in Situationen geraten, in denen keine serialisierbare Fortsetzung mehr möglich und Transaktionsabbruch erforderlich ist.
SS 2004 B. König-Ries: Datenbanksysteme 5-61
Erkennen von Verklemmungen
Durch Timeout: Jede Sperrenanforderung wird mit maximaler Wartezeit versehen. Nach Ablauf wird Verklemmung angenommen. Einfach zu implementieren, kann aber zu irrtümlichen Abbrüchen
oder verspäteter Entdeckung von Verklemmungen führen. Durch Wartegraph:
Wartegraph enthält Knoten Ki für jede aktive Transaktion Ti sowie Kante von Ki nach Kj, falls Transaktion Ti auf Transaktion Tj wartet.
Verklemmung wird durch Existenz eines Zyklus angezeigt. Verwaltung aufwendiger als Timeouts, liefert aber präzise
Ergebnisse.
SS 2004 B. König-Ries: Datenbanksysteme 5-62
Behandlung von Verklemmungen (1)
Auflösung (durch Transaktionsabbruch): Erfordert Erkennung der Verklemmung und Auswahl der
abzubrechenden Transaktion. Bei mehreren Kandidaten Auswahl der abzubrechenden
Transaktion über Kostenfunktion (z.B. bereits investierter Aufwand, Priorität, verbleibender Aufwand bis Abschluss).
Ausgewählte Transaktion wird rückgesetzt und Sperren werden freigegeben.
SS 2004 B. König-Ries: Datenbanksysteme 5-63
Behandlung von Verklemmungen (2)
T2 T4
T3 T1
T2 T4
T1
SS 2004 B. König-Ries: Datenbanksysteme 5-64
Kapitel 5: Transaktionsverwaltung
Transaktionsmodell
Isolation
Atomizität
Dauerhaftigkeit
SS 2004 B. König-Ries: Datenbanksysteme 5-65
Rücksetzen
Bisher betrachtetes Scheduling gewährleistet Isolation, d.h. Serialisierbarkeit, setzt jedoch voraus, dass Transaktionen abgebrochen und rückgesetzt werden können.
Jetzt zu betrachten: Rücksetzmechanismen, die gewährleisten, dass nicht erfolgreiche Transaktionen keinerlei Effekte bewirken (Atomizität).
Mögliche Gründe für Transaktionsabbruch: Selbstaufgabe (Ausführung von abort-Operation), Systembedingter Abbruch (z.B. wegen Verklemmung,
Ressourcenmangel, I/O-Fehler), Systemzusammenbruch mit Verlust des Hauptspeicherinhalts.
SS 2004 B. König-Ries: Datenbanksysteme 5-66
Rücksetzbarkeit von Schedules (1)
Rücksetzen einer Transaktion Ti kann andere Transaktion Tj beeinflussen, die bereits von Ti gelesen hat und deshalb nun ebenfalls rückgesetzt werden muss.
Zur Erinnerung: Konfliktserialisierbarer (fast serieller) Schedule
S4: r2(B) r2(T) w2(T) w2(B) r1(B) r1(T) a2 c1.
CP(S4): Nur T1! Da aber T1 Wert B (und T) von T2 gelesen hat (dirty read), kann Atomizität von T1 nur durch Rücksetzen von T1 erreicht werden.
Vorgang ist als kaskadierendes Rücksetzen bekannt — unerwünscht, da Arbeit von T1 verloren geht.
SS 2004 B. König-Ries: Datenbanksysteme 5-67
Rücksetzbarkeit von Schedules (2)
Betrachte konfliktserialisierbaren (fast seriellen) Schedule S10: r3(T) w3(T) r3(B) w3(B) r2(B) r2(T) w2(T) w2(B) c2 c3.
Rücksetzen von T3 fatal, da wegen dirty read auch T2 rückzusetzen wäre, dies aber die Persistenz von T2 verletzen würde.
Folgerung: Für Zwecke der Rücksetzbarkeit muss Menge der zulässigen Schedules über Serialisierbarkeit hinaus eingeschränkt werden.
a3
Zum Vergleich: Kaskadierendes Rücksetzen S10: r3(T) w3(T) r3(B) w3(B) r2(B) r2(T) w2(T) w2(B) c3 c2.a3
SS 2004 B. König-Ries: Datenbanksysteme 5-68
Rücksetzbarkeit von Schedules (3)
Definition: Sei S Schedule. S heißt rücksetzbar (wiederanlaufbar), wenn für alle
Transaktionen Ti, Tj mit i j gilt: wenn Tj irgendein Datenelement x von Ti liest und S den Aufruf cj enthält, dann enthält S auch ci, und ci erfolgt vor cj.
S vermeidet kaskadierendes Rücksetzen, wenn für alle Transaktionen Ti, Tj mit i j gilt: wenn Tj irgendein Datenelement x von Ti liest, dann erfolgt zwischen wi(x) und rj(x) ein Aufruf von ci.
S heißt rigoros, wenn für alle Transaktionen Ti, Tj in CP(S) mit i j gilt: wenn oi(x) vor oj(x) in S und oi(x) unverträglich mit oj(x), dann erfolgt ci vor oj(x).
Rigorose Schedules vermeiden kaskadierendes Rücksetzen und sind konfliktserialisierbar.
S2PL erzeugt rigorose Schedules S2PL löst Isolation und Atomizität.
SS 2004 B. König-Ries: Datenbanksysteme 5-69
Transaktion 1 Transaktion 2 ... Transaktion n
Synchronisation durch Scheduler
Segment-Verwalter
Atomizität, Dauerhaftigkeit
lokaler Schedule 1 lokaler Schedule n
konfliktserialisierbarer, wiederanlaufbarer globaler Schedule
Zusammenspiel mit Segment-Verwalter (1)
Abstimmung bei commit und rollback
Konflikt-Resistenz
Fehler-Resistenz
SS 2004 B. König-Ries: Datenbanksysteme 5-70
Zusammenspiel mit Segment-Verwalter (2)
Lokales Zwei-Phasen-Festschreibe-Protokoll:
1. Sichern der Persistenz oder Fehler-Resistenz: Der Segment-Verwalter schreibt den Anfangszustand (bei rollback
aufgrund von abort) oder den Endzustand (bei commit) der Transaktion fest.
Nach Abschluss dieser Phase wird die erfolgreiche Transaktion als wiederholbar bezeichnet, die abgebrochene Transaktion als wiederanlaufbar, sofern sie ihren Abbruch nicht selbst verschuldet hat.
2. Freigabe der Betriebsmittel: Anschließend können alle von der Transaktion benutzten
Betriebsmittel freigegeben werden. Insbesondere löst der Scheduler alle von der Transaktion
gehaltenen Sperren.
SS 2004 B. König-Ries: Datenbanksysteme 5-71
Transaktionszustände
potenziell aktiv blockiert
geschei-tert
abge-schlossen
wieder-holbar
auf-gegeben
wieder-anlaufbar
inkarnieren
neustarten
undo undo
abbrechen
abbrechen abbrechen
einbringen
verdrängen
beenden
festschreiben
SS 2004 B. König-Ries: Datenbanksysteme 5-72
Kapitel 5: Transaktionsverwaltung
Transaktionsmodell
Isolation
Atomizität
Dauerhaftigkeit
SS 2004 B. König-Ries: Datenbanksysteme 5-73
Robustheitsgarantien
Dauerhaftigkeit kann nur in die Zuständigkeit des Segment-Verwalters fallen.
Gefährdungen: Kurzer Zeithorizont: Systemabsturz. Längerer Zeithorizont: Plattenspeicherfehler, Feuer, Wasser,
Sabotage, alle resultierend im Medienverlust. Garantien: Nach restart
Abbrechen (undo) aller zum Katastrophenzeitpunkt noch aktiven Transaktionen.
Wiederholen (redo) aller zum Katastrophenzeitpunkt erfolgreich abgeschlossenen Transaktionen.
Wegen unterschiedlicher Zeithorizonte unterschiedliche technische Lösungen!
SS 2004 B. König-Ries: Datenbanksysteme 5-74
Undo/Redo-Prinzip
Zeit
dauerhaft
gesichert
T1
T4
T5
Katastrophe
T2
ignoriert
ignoriert
redoT3
undo
undo
Recommended