Datenbanksysteme Technische Grundlagen Transaktions-Konzept, Mehrbenutzer-Synchronisation, Fehlerbehandlung Prof. Dr. Manfred Gruber FH München

DatenbanksystemeTechnische Grundlagen

Transaktions-Konzept, Mehrbenutzer-Synchronisation,

Fehlerbehandlung

Prof. Dr. Manfred Gruber FH München

Transaktions-Konzept (1)

• Beispiel:op1 BOT

op2 read(K1) aus KONTO1

op3 write(K1 := K1 - 8000) in KONTO1

op4 read(K2) aus KONTO2

op5 write(K2 := K2 + 8000) in KONTO2

op6 commit

• Konsistenz: T ganz oder gar nicht ausführen!

T

Transaktions-Konzept (2)

• Transaktion (TA): Folge von DB-Operationen– atomar– konsistenzerhaltend

• DB-Operationen– allgemein: read, write– speziell: BOT, commit, abort

„gleichzeitige" Ausführung von TAs

bessere Ressourcen-Nutzung (Optimierung)– einige TAs lesen oder schreiben Daten– andere lasten die CPU aus

höherer Durchsatz kürzere Antwortzeiten

• Gleichzeitigkeit (Nebenläufigkeit) birgt Gefahren!

typische Synchronisations-Probleme (1)

Beispiel. [w/r-Konflikt (dirty read)]Zeit T1 T2

t1 read(K1)

t2 write(K1 := K1 - 8000)

t3 read(K1)

t4 write(K1 := K1*1,04)

t5 read(K2)

t6 write(K2 := K2*1,04)

t7 read(K2)

t8 write(K2 := K2 + 8000)


Beispiel. [r/w-Konflikt (unrepeatable read)]

Zeit T1 T2

t1 S := read(K1)

t2 read(K1)

t3 write(K1 := K1 - 8000)

t4 read(K2)

t5 write(K2 := K2 + 8000)

t6 S := S+ read(K2)

(„Phantomproblem“)


Beispiel. [w/w-Konflikt (lost update)]

Zeit T1 T2

t1 read(K1)

t2 read(K1)

t3 write(K1 := K1 - 8000)

t4 write(K1 := K1+8000)

ACID-Paradigma

• Atomicity TAs werden ganz oder gar nicht durchgeführt

• Consistency TAs sind konsistentTAs hinterlassen konsistente DB-Zustände

• Isolation TAs „sehen“ einander nicht

• Durabilityerfolgreiche (commit) TAs werden durchgesetzt

Aufgabenverteilung

• Konsistenz und Isolation:– Concurrency Control

(Mehrbenutzer-Synchronisation)

• Atomarität und Dauerhaftigkeit:– Logging & Recovery

(Protokoll- und Wiederanlauf-Komponente)

Schedules• Schedule: Zeitliche „Verzahnung“ der Operationen

mehrerer TAs, interne Operationen-Reihenfolge jeder TA wird beibehalten.

• Beispiel: T1 : (r1(A), r1(C), w1(C)),T2 : (r2(A), r2(B), w2(B)),S : (r1(A), r2(A), r2(B), w2(B), r1(C), w1(C))

• DB-Anfangszustand DB-EndzustandSchedule

„vernünftige“ Schedules ?

• seriell: eine TA nach der anderen– idealtypisch („isoliert“,“konsistent“), aber langsam

• serialisierbar: Wirkung wie serieller Schedule– nicht praktikabel (exponentieller Nachprüfungs-

Aufwand)

• konfliktserialisierbar: azyklischer Konflikt-Graph– praktikabel (polynomialer Nachprüfungs-Aufwand)

Konflikt-Serialisierbarkeit (1)

• Konfliktgraph G(S) von S– Knoten: alle TAs Ti von S

– (gerichtete) Kanten: Pfeile von Ti nach Tj, falls

• A, op1(A) Ti, op2(A) Tj existieren

• wobei op1(A) zeitlich vor op2(A) liegt

• und (op1 = w oder op2 = w) ist

• G(S) azyklisch S (konflikt)serialisierbar

Konflikt-Serialisierbarkeit (2)Beispiel.

T1 : (r1(A), w1(B)),

T2 : (w2(A)),

T3 : (r3(A), r3(B)),

S : (r1(A), w2(A), r3(A), r3(B), w1(B))

T1 T2

G(S): (zyklisch,S nicht konfliktserialisierbar)

T3

Konflikt-Serialisierbarkeit (3)• Beispiel.

T1 : (r1(A), w1(B)),

T2 : (w2(A)),

T3 : (r3(A), r3(B)),

S´: (r1(A), w2(A), r3(A), w1(B), r3(B))

T1 T2

G(S´): (azyklisch, S´ serialisierbar)

T3

Sperrbasierte Synchronisation (1)

• Scheduler setzt temporäre DB-Obj-Sperren– 2 Sperrmodi: S (shared), X (exclusive)

• TA darf– lesen nach Erhalt einer S-Sperre– schreiben nach Erhalt einer X-Sperre

- S X

• Verträglichkeits-Matrix: S ja ja neinX ja nein nein


• Strenges 2-Phasen-Sperrprotokoll (Strict 2PL)– TA darf nur lesen nach Erhalt einer S-Sperre– TA darf nur schreiben nach Erhalt einer X-Sperre– „streng“: TA behält alle Sperren bis commit/abort

• TAs, die keine Sperre erhalten Warteschlange

• Strict 2PL Serialisierbarkeit + weitere Vorzüge (u.a. Rücksetzbarkeit)


• Beispiel. [Deadlock (Verklemmung)]

T1 : (X1(A), w1(A), S1(B), r1(B)),

T2 : (X2(B), w2(B), S2(A), r2(A)),

S : (X1(A), w1(A), X2(B), w2(B), S1(B), S2(A), ...) warten !

warten!

• 2 Strategien möglich– 1. pessimistisch: Deadlock-Vermeidung– 2. optimistisch: Deadlock-Erkennung und -Beseitigung

Deadlock-Erkennung und -Beseitigung

• Wartegraph W(S) von S– Knoten: alle TAs Ti von S

– (gerichtete) Kanten: Pfeile von Ti nach Tj, falls

• Tj das DB-Obj A sperrt

• und Ti auf Gewährung einer Sperre auf A wartet

• periodische Untersuchung von W(S) auf Zyklen

• Zyklus entdeckt eine TA „abschießen“

Fehlerklassifikation

• lokale „Fehler“ (relativ häufig)– Anwendungsprogramm-Fehler, expliziter Abbruch (abort),

systemgesteuerter Abbruch (z.B. Deadlock-Beseitigung)

• Fehler mit Hauptspeicherverlust (selten)– z.B. Betriebssystem-Fehler, Hardwareausfall, Stromausfall

• Fehler mit Hintergrundspeicherverlust (sehr selten)– z.B. bei „head crash“, Feuer/Erdbeben, Systemprogramm-

Fehler (fehlerhafter Plattentreiber)

Seiten-Ersetzungs-Strategien

• „force“: am Ende einer TA (nach commit) geänderte Seiten sofort zurückschreiben– garantiert Dauerhaftigkeit– aber lange Antwortzeiten

• „no steal“: Seite nicht zurückschreiben, solange eine der schreibenden TAs aktiv (vor commit) ist– gut für Atomarität– aber schlechter Durchsatz

steal & no force !

• steal: Seite P zurückschreiben, obwohl T noch ein DB-Obj auf P sperrt!– . . . und wenn dann T abgebrochen wird (abort)?– undo-Information (alter Wert von P) in die Log-Datei!

• no force: Von T geänderte Seite P (noch) nicht zurückschreiben, trotz T´s commit!– . . . und wenn nun das System „abstürzt“?– redo-Information für T beim commit in die Log-Datei!

Logging

• für jede DB- Änderung ein Eintrag in die Log-Datei– sequentiell– minimale Info (nur 's), viele Log-Sätze auf eine Log-Seite– separater, sicherer Speicherort (Log-Puffer, Log-Archiv)

• Log-Datei: Liste von redo- und undo-Information– <TAID,pageID,offset,length,beforeImage,afterImage>– und weitere Kontroll-Information

Write-Ahead-Logging

WAL-Protokoll• alle Log-Sätze zu einer DB-Seite permanent

speichern, bevor die DB-Seite zurückgeschrieben wird!– ermöglicht undo nichtabgeschlossener TAs Atomarität

• alle Log-Sätze zu einer TA vor deren commit schreiben!– ermöglicht redo abgeschlossener TAs

Dauerhaftigkeit

Recovery Manager

• Einsatz– bei laufendem Betrieb: local undo bei lokalen Fehlern– bei Wiederanlauf:

• global undo/redo nach Hauptspeicherverlust• Rekonstruktion des jüngsten konsistenten DB-

Zustands nach Hintergrundspeicherverlust

• local undo, global undo/redo:– TAs ohne commit: zurücksetzen Atomarität– TAs mit commit: durchsetzen Dauerhaftigkeit

Literatur[1] A. Hald, W. Nevermann: Datenbank-

Engineering für Wirtschaftsinformatiker. Vieweg-Verlag

[2] A. Kemper, A. Eickler: Datenbanksysteme. Oldenbourg

[3] R. Ramakrishnan, J. Gehrke: Database Management Systems. McGraw-Hillhttp://www.cs.wisc.edu/~dbbook/

[4] G. Vossen: Datenmodelle, Datenbanksprachen und Datenbank-Management-Systeme. Oldenbourg

Documents

Datenbanksysteme Technische Grundlagen Transaktions-Konzept, Mehrbenutzer-Synchronisation, Fehlerbehandlung Prof. Dr. Manfred Gruber FH München