74
SS 2004 B. König-Ries: Datenbanksysteme 5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann, IPD, Uni Karlsruhe

SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

Embed Size (px)

Citation preview

Page 1: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

SS 2004 B. König-Ries: Datenbanksysteme 5-1

Kapitel 5: Transaktionsverwaltung

TransaktionsmodellIsolationAtomizitätDauerhaftigkeit

Folien: © Prof. Lockemann, IPD, Uni Karlsruhe

Page 2: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

SS 2004 B. König-Ries: Datenbanksysteme 5-2

Kapitel 5: Transaktionsverwaltung

Transaktionsmodell

Isolation

Atomizität

Dauerhaftigkeit

Page 3: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 4: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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).

Page 5: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 6: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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!

Page 7: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 8: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 9: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 10: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 11: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 12: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.)

Page 13: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 14: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 15: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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 .

Page 16: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 17: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 18: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 19: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 20: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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?

Page 21: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

SS 2004 B. König-Ries: Datenbanksysteme 5-21

Kapitel 5: Transaktionsverwaltung

Transaktionsmodell

Isolation

Atomizität

Dauerhaftigkeit

Page 22: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 23: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 24: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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)

Page 25: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 26: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 27: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 28: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 29: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 30: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 31: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 32: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 33: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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].

Page 34: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 35: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 36: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 37: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 38: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 39: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 40: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 41: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 42: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 43: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 44: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 45: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 46: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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:

Page 47: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 48: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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)

Page 49: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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!

Page 50: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 51: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 52: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 53: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 54: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 55: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 56: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 57: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 58: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 59: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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 ---

Page 60: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 61: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 62: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 63: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

SS 2004 B. König-Ries: Datenbanksysteme 5-63

Behandlung von Verklemmungen (2)

T2 T4

T3 T1

T2 T4

T1

Page 64: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

SS 2004 B. König-Ries: Datenbanksysteme 5-64

Kapitel 5: Transaktionsverwaltung

Transaktionsmodell

Isolation

Atomizität

Dauerhaftigkeit

Page 65: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 66: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 67: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 68: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 69: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 70: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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.

Page 71: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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

Page 72: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

SS 2004 B. König-Ries: Datenbanksysteme 5-72

Kapitel 5: Transaktionsverwaltung

Transaktionsmodell

Isolation

Atomizität

Dauerhaftigkeit

Page 73: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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!

Page 74: SS 2004B. König-Ries: Datenbanksysteme5-1 Kapitel 5: Transaktionsverwaltung Transaktionsmodell Isolation Atomizität Dauerhaftigkeit Folien: © Prof. Lockemann,

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