Wieso ist ein Mehrbenutzerbetrieb bei DBMS notwendig?
Damit das System besser ausgelastet wird, da es oft vorkommt, dass auf langsamere Betriebsmittel (e.g. Hintergrundspeicher) oder Benutzereingaben gewartet werden muss
Was ist das Ziel der Mehrbenutzersynchronisation?
Die einhaltung der Isolation der ACID ziele
-> für jede TA muss es so erscheinen, als wäre sie die einzig aktive!!
Was für fehler können bei unkontrolliertem Mehrnutzerbetrieb entstehen?
Verlorengegangene Änderungen (lost updates)
Abhängigkeit von nicht freigegebenen Änderungen
Phantomproblem
Was sind verlorengegangene Änderungen (lost updates)?
Falls bsp. zwei TA ein datum lesen, ändern und zurückschreiben.
-> Wenn beide lesen bevor die jeweils andere TA zurückgeschrieben hat, wird nur die änderung der als letzte zurückschreibenden TA gespeichert, die änderung der anderen geht verloren!
Was ist die abhöngigkeit von nicht frei gegebenen änderungen?
Auch als dirty read bezeichnet
-> Eine TA greift auf ein datum zu, das von einer anderen TA die dieses bearbeitet nocht nicht freigegeben wurde
-> evtl. ist wert nicht gültig oder TA aborted; dadurch hat andere TA falsche Grundlage für eigene Operation
Bsp.: TA1: bankkonto + 300; TA2: zinsen Bankkonto * 1.03; TA1: abort
-> Es werden zu viel zinsen (9 euro) berechnet!
Was ist das Phantomproblem?
Diese art von Problem tauch auf, falls eine TA auf ein Datum zugreift, das noch nicht vollständig ist (daten fehlen…)
Bsp. ein Fach in der Notenliste wurde noch nicht veröffentlöicht und einen andere TA greift bereits darauf zu und stellt die zeugnisse zusammen
Was bedeutet serialisierbarkeit?
Das vermögen, eine menge von TA so auszuführen dass sie nebenläufig arbeiten aber das Konzept dier Isolation nicht verletzen
Aus welchen elementaren Operationen kann eine Transaktion hinsichtlich der Serialisierbarkeitstheorie bestehen?
read
write
abort
commit
=> abort und commit sind mutually exclusive!!!
Was für eine Ordnung müssen die Operationen von TA einhalten?
Es reicht eine Partielle ordnung
Was für Bedingungen muss die partielle Ordnungen der Operationen von Transaktionen einhalten?
Alle Operationen einer TA i müssen vor einem abort oder commit dieser Transaktion ausgeführt worden sein
(abort oder commit IMMER letzte Operation)
Falls eine TA ein datum liest und schreibt, muss die reihenfolge festgelegt sein
reihenfolge gleicher TA auf gleichem Datum immer geordnet!
Was versteht man unter einer sog. Historie?
Den verzahnten ablauf mehrerer Transaktionen in der form einer Partiellen Ordnung auf elementaren Operaitonen
Für welche Operationen muss in einer Historie eine Ordnung festgelegt sein?
Für die von der serialisierbarkeit vorgeschriebenen Operationen und sog. Konfliktoperationen
Was sind Konfliktoperationen?
Mengen von Operationen, die bei unkontrollierter ausführung zu Inkonsistenzen führen können
Wann liegt eine Konfliktoperation vor und welche Operationspaare gelten als Konfliktoperationen?
Immer wenn ein Datum gelesen und geschrieben wird liegt ein Konflikt vor
ri(A) wj(A) muss immer geordnet sein (lesen und schreiben auf gleichem Datum)
wj(A) wi(A) muss immer geordnet sein (schreiben auf gleichem Datum)
Wann sind zwei Historien Äquivalent?
Falls alle Konfliktoperationen die gleiche Reihenfolge haben
-> anordnung der nicht konflikt operationen irrelevant!
Wie können historien optimiert werden?
In dem man durch schlaues vertauschen der nicht konflikt operationen eine äquivalente historie schafft, die besser verzahnt (performanter) ist
Wann ist eine Historie serialisierbar?
Wenn sie äquivalent zu einer seriellen (hintereinanderausführung der TA als blöcke) äquivalent ist!
Was gibt ein serialisiserbarkeitsgraph an ?
Ob es eine serialisierbare Historie zu einer gegebenen gibt, und wie diese geordnet sein muss
-> “ordnung” der Transaktionen
Wie stellt man einen Serialisierbarkeitsgraphen auf?
Man schaut sich alle erfolgreich abgeschlossenen (commit) Transaktionen einer Historie an
für jede Konfliktoperation zweier Transaktionen Ti und Tj zeichnet man eine gerichtete Kante zwischen Ti und Tj an in richtung der später ausgeführten operation (bsp. ri(A) < rj(A) => Ti -> Tj)
Wann ist laut Serialisierbarkeitsgraph eine Historie Serialisierbar?
Falls der Serialisierbarkeitsgraph azyklisch ist
Wann sind zwei Historien laut serialisierbarkeitsgraph äquivalent?
Falls die anordnung der Transaktionen einer Topologischen Sortierung des Resialisierbarkeitsgraphen entspricht
-> Keine Transaktion Ti steht vor einer anderen Tj, falls es eine (auch transitive) gerichtete Kante von Tj nach Ti gibt!
Was ist eine Anforderung die man an Historien bezüglich der Recovery stellen kann?
Die Historie soll so geordnet sein, dass zu jedem Zeitpunk vor einem commit die entsprechende TA lokal zurückgesetzt werden kann ohne dass andere TA davon beeinträchtigt werden
Wann nennt man eine Historie rücksetzbar?
Falls bei lokalem zurücksetzen einer TA bereits commitete TA nicht in mitleidenschaft gezogen werden
=> es gilt immer, dass die schreibende TA vor der lesenden commited
Wann liest eine Transaktion Ti von einer anderen Transaktion Tj?
Falls folgendes gilt:
wj(A) < ri(A) -> i liest ein Datum dass j zuvor geschrieben hat
Tj wird nicht vor dem Lesevorgang zurückgesetzt (falls zurückgesetzt wäre die änderung ja verworfen…)
Alle anderen Schreibvorgänge anderer Transaktionen auf A werden zwischen schreiben von j und lesen von i zurückgesetzt (letztes datum ist das das j geschrieben hat…)
=> i liest von j, falls es ein Datum liest das j zuletzt geschrieben hat
Was kann ein problem bei rücksetzbaren historien sein?
Es entsteht ein kaskadierendes zurücksetzen, indem eine schreibende TA aborted, dann die lesende auch aborten muss was wiederum zu einem abort von lesenden TA der lesenden TA zufolge hat……
Wann vermeidet eine Historie kaskadierendes Rücksetzen?
Falls Ti von Tj liest, muss Tj erst commiten
-> änderungen dürfen erst gelesen werden, wenn die TA die die änderung ausgeführt hat commited hat
Was ist eine strikte Historie?
Ohne kaskadierendes zurücksetzen
plus:
es dürfen keine geschriebenen daten nicht abgeschlossener (commit oder abort) Transaktionen überschrieben werden
-> Also falls eine TA ein datum liest oder überschreibt das zuvor von der anderen geschrieben wurde muss die erste TA bereits ihr abort oder commit ausgeführt haben
Wie ist die beziehung der verschidenen Klassen von Historien?
serielle historien TM Strikten Historien TM ohne kaskadierendes Rücksetzen TM alle historien
und serialisierbare historien können jede klasse davon sein! (wobei serielle historien immer serialisierbar sind!)
Was macht ein Datenbank scheduler?
Er ordnet Operaitonen so, dass sie serialisierbarkeit und kein kaskadierendes Rücksetzen erfüllen
In welchen Modi können scheduler operieren?
Sperrbasierte Synchronisation
Zeitstempelbasierte-Synchronisation (pessimistische synchronisation)
Optimistische Synchronisation
Was stellt die sperrbasierte Synchronisation sicher?
Sie stellt sicher, dass die resultierende Historie serialisierbar bleibt
Wie arbeitet die sperrbasierte Synchronisierung grob?
TA dürfen erst nach erhalt einer Sperre auf ein Datum zugreifen
Welche sperrmodi unterscheidet die sperrbasierte Synchronisation?
S (Shared, Read Lock, Lesesperre) -> Transaktion kann read ausführen auf datum von dem sie die S-Sperre erhalten hat
Mehrere TA können diese Sperre für gleiches datum haben
X(exclusive, write lock, schreibsperre) -> TA kann auf datu mder Soerre write operation ausführen
Diese sperre kann je datum nur eine TA haben
Wie verträglich sind die verschiedenen Sperren untereinander?
S kann mit S; aber X kann nur alleine (kein S oder X darf bereits auf Datum liegen)
Welches Protokoll stellt die serialisierbarkeit bei sperrbasierter Synchronisation sicher?
Das Zwei Phasen Sperrprotokoll (2PL)
Was verlangt das 2PL von einer TA?
jedes Objekt das eine TA benutzen möchte muss vorher gesperrt werden
Eine TA die eine sperre besitzt fordert diese nicht noch einmal an
Eine TA muss die sperre anderer TA auf die von ihr angeforderte beachten
-> falls nicht verträglich, wird sie in eine warteschlange eingereiht
Jede TA durchläuft 2 phasen
Wachstumsphase (sperren werden angefordert aber keine greigegeben)
Schrumfungsphase (berworbene sperren werden freigegeben, keine neuen angefordert)
Bei EOT (Transaktionsende) muss die TA alle erworbenen sperren freigeben
Was ist ein nachteil des 2PL?
Es garabtiert nicht das vermeiden von kaskadierendem rücksetzen
Wie kann das 2PL erweitert werden um kaskadierendes rücksetzen zu vermeiden?
Strenges 2PL
erweiterung:
Keine schrumpfungsphase, sondern alle Sperren werden erst bei EOT freigegeben!!
Was ist ein inherentes Problem der Sperrbasierten Synchronisationsmethoden?
Es können Deadlocks auftreten
Was für methoden zur deadlockerkennung existieren?
Time Out methode
Wartegraphen
Was sind vorteile und nachteile der Time Out methode?
vorteil: günstige methode
nachteil:
falls zeitmaß zu klein kann es sein dass TA abgebrochen werden, die eigentlich gar nicht verklemmt sind (sondern TA wartet nur auf ressourcen wie z.b. CPU)
falls zeitmaß zu groß: deadlocks können zu lange geduldet werden bevor sie abgebrochen werden
Wie funktioniert die time out methode?
TA werden überwacht
-> falls eine TA innerhalb eines definierten Zeitmaßes (bsp. 1 sec) keinen fortschritt erzielt, geht das system von einem deadlock aus und setzt die TA zurück
Wie funktionieren Wartegraphen?
Ein graph bei dem
knoten: derzeit aktive Transaktionen
gerichtete kanten: TA wartet auf sperre die andere TA besitzt (will sperre -> besitzt sperre)
Wann liegt ein Deadlock im Wartegraphen vor?
Falls der Wartegraph einen Zyklus aufweist
Was ist der Nachteil von Wartegraphen ggü. der Time Out strategie?
Präziser aber auch teurer
Wie werden Deadlocks im Wartegraphen gelöst?
Rücksetzen einer TA im Zyklus
Wie wird im Wartegraphen ausgewählt, welche TA zurückgesetzt wird?
Mehrere Strategien:
Minimierung rücksetzaufwand -> jüngste TA rücksetzen
Maximierung der freigegebenen Ressourcven -> TA mit meisten Sperren rücksetzen
Vermeidung von Starvation -> verhinderung dass immer die gleiche TA zurückgesetzt wird -> merken wie oft eine TA bereits rückgesetzt wurde und ihr ggf. einen Freifahrtschein geben der eine erneute rücksetzung verhindert
Mehrfache Zyklen: Falls eine TA in mehreren Zyklen vorkommt, macht es sinn diese rückzusetzen um mehrere Deadlocks auf einmal aufzulösen
Welche Methoden zum Vermeiden von Deadlocks existieren?
Preclaiming
Zeitstempel
Wie funktioniert preclaiming zur DL vermeidung?
Transaktionen werden erst begonnen, wenn alle Sperrforderungen zur BOT erfüllt werden können
-> anfordern aller benötigter sperren vor beginn der Transaktion!
Was ist ein nachteil der Preclaiming methode?
Die TA muss bereits zu beginn wissen, welche Sperren sie benötigt
-> schwierig bei z.b. if…else anweisungen da mehr sperren angefordert als tatsächlich benötigt…
Wie funktioniert deadlockvermeidung mit Zeitstempeln?
Jede TA enthält einen Zeitstempel in monoton wachsender Reihenfolge (ältere TA hat kleineren Zeitstempel)
-> TA warten nicht mehr auf freigabe einer sperre sondern es wird nach einer von zwei strategien verfahren
Welche strategien werden in Deadlockvermeidung mit Zeitstempeln unterschieden?
T1 fordert Sperre an, die T2 hat (T1 wartet auf T2)
wound wait:
T1 älter als T2 -> T2 wird abgebrochen und rückgesetzt, T1 erhält sperre
T1 jünger als T2 -> T1 wartet auf T2
wait-die:
T1 älter als T2 -> T1 wartet auf Freigabe durch T2
T1 jünger als T2 -> T1 wird abgebrochen und zurückgesetzt
Was ist ein nachteil der DL vermeidung mit Zeitstempeln?
i.A. werden zu viele TA zurückgesetzt, da nicht immer ein DL auftreten würde
Was für sperrgranulate existieren für Sperren?
Datensätze: einzelne Tupel sind kleinste Sperreinheit; falls viele Datensätze benötigt -> viele sperren
Seiten
Segmente: logische einheit mehrerer Seiten -> starke einschränkung der parallelität!
Datenbasis: extremfall, aus der die serielle abarbeitung der Transaktionen folgt!
Welches problem entsteht bei gleichzeitigem benutzen mehrerer Sperrgranulate?
Falls z.B. eine TA eine Sperre auf eine Seite anfordern möchte, müssen alle Datensätze der Seite auf evtl. vorhandene Sperren überprüft werden. Dieses problem verschlimmer sich, je größer das sperrgranulat ist!
Was ist ein problem zu großer und zu kleiner sperrgranulate?
zu groß: parallelität zu stark eingeschränkt
zu klein: es müssen sehr viele sperren angefordert werden
Wie kann man die proleme die aus den verschiedenen Sperrgranulaten entstehen beheben?
Durch Einführen weiterer Sperrmodi (nicht mehr nur S und X)
Wie wird das verfahren der flexiblen wahl von sperrgranulaten genannt?
multiple-granularity locking (MGL)
Wie werden die zusätzlichen sperrmodi als gesamtes bezeichnet?
intentionssperren
Um was erweitern die Intentionssperren die ursprünglichen sperrmodi?
Ursprünglich:
NL: No Lock
S: Lesesperre
X: Schreibsperre
Intentinssperren:
IS: weiter unten in hierarchie (auf kleinerem sperrgranulat) ist eine Lesesperre
IX: weiter unten ist eine Schreibsperre
Wie ist die kompatibilität der erweiterten sperrmodi?
S kann man bei S und IS anfordern
X kann man nur bei NL anfordern
IS kann man bei NL, S, IS und IX anfordern
IX kann man bei NL, IS und IX anfordern
Wie verlaufen sperranforderungen und sperrfreigaben bei erweiterten sperrmodi?
anforderung: top down
Falls Knoten mit S oder IS gesperrt wird, müssen alle vorgänger in der Hierarchie mit IS oder IX gesperrt sein
Falls Knoten mit X oder IX gesperrt wird, müssen alle vorgänger mit IX gesperrt sein
freigabe: bottom up
sperren werden nur freigegeben, falls TA nicht weiter unten noch gesperrt hat
Was versteht man unter einem Gruppenmodus hinsichtlich sperrungen?
Falls mehrere intentionale sperrungen auf einem Objekt liegen, wird immer die Höchste als Gruppenmodus angenommen. Dadurch muss man bei Sperranforderungen immer nur gegen den Gruppenmodus vergleichen
es gilt:
S > IS
IX > IS
Was ist lock escalation?
Automatisches umschalten von einer niedrigeren Sperrgranularität auf eine höhere sobald eine bestimmte anzahl von sperren der kleineren Granularität angefordert wurden
Was kann bei MGL sperrverfahren auftreten?
Deadlocks
Last changeda year ago