Home

Impressum

kreissl.info[rmation science]

best practices

Concurrency Control

Kapitel 8 - Concurrency Control

Einführung in das Read-Write-Modell für Transaktionen
Was sind Schedules
Was heißt Serialisierbarkeit von Schedules?
Welche Synchronisationsprobleme gibt es?
Welche Synchronisationsverfahren gibt es für Scheduler?
Wie arbeitet die Concurrency Controll und wie ist sie aufgebaut?

Weshalb Zugriffe auf Datenbankobjekte synchronisieren?

Ziel ist eine verzahnte Ausführung aller Transaktionen, um Antwortzeit und Performance hoch zu halten. Dafür müssen serialisierbare Schedules erstellt werden. Ein Schedule ist dann serialisierbar, wenn er im Ergebnis äquivalent zu der möglichen seriellen Ausführung der Transaktionen ist. Auftretende Synchronisationsprobleme, wie Dirty Read, Lost Update und Inkonsistent Read müssen ausgeschlossen werden.

Schedule (verzahnt): T1:read(a) -> T2:read(a) -> T1:read(b)
seriell: T1->T2->T3, also hier T1:read(a) -> T1:read(b) -> T2:read(a)

Desweiteren muss sichergestellt werden, daß die Transaktionen dem ACID-Prinzip genügen:

Atomicity / Atomarität
Eine Transaktion wird entweder vollständig oder gar nicht ausgeführt.

Consistency / Konsistenz
Eine Transaktion überführt einen konsistenten Zustand der Datenbank in einen anderen konsistenten Zustand.

Isolation
Die Zwischenergebnisse gleichzeitig ablaufender Transaktionen dürfen jeweils für die anderen Transaktionen nicht sichtbar sein. D.h. keine Transaktion merkt, daß andere Transaktionen parallel zu ihr laufen. Dies impliziert, das eine Transaktion rücksetzbar ist.

Durability / Dauerhaftigkeit
Die Ergebnisse einer erfolgreichen Transaktion werden gegen Versagen der Hard- und Software gesichert und können nur durch eine weitere Transaktion wieder geändert werden.

Im klassischen Fall werden die Punkte Consistency und Isolation dadurch erreicht, daß man verlangt, daß die Transaktionen serialisierbar ablaufen. Verletzungen der Serialisierbarkeit müssen erkannt und verhindert werden. Hierfür gibt es prinzipiell zwei Kategorien von Verfahren, pessimistische und optimistische. Sperren gewährleisten Konfliktserialisierbarkeit (Reihenfolge von Konfliktbeteiligten bleibt in beiden Schedules gleich) und sind pessimistische Verfahren. Sie definieren sich durch zwei Phasen:

Eine Wachstumsphase, in der Sperren angefordert, aber nicht freigegeben werden dürfen.
Eine Schrumpfungsphase, in der Sperren freigegeben, aber nicht mehr angefordert werden dürfen.

Deadlocks können auch beim strikten 2-PL entstehen. Nur Preclaiming kann Deadlocks ausschließen, da hier alle Sperren auf einmal und atomar gesetzt werden und keine Sperren nachträglich angefordert werden können. Deadlocks werden normalerweise nach Timeouts auf Zyklen im Wartegraphen geprüft und erkannt.

Welche drei Definitionen gibt es für die Äquivalenz von Schedules?

Zustands-Serialisierbarkeit (ZSR)

Dies ist die intuitivste Definiton. Zwei Abfolgen der gleichen Transaktionen sind äquivalent, wenn für alle möglichen Anfangszustände und Semantiken der Transaktionen die Endzustände jeweils gleich sind.

Sichten-Serialisierbarkeit (SSR)

ist eine Verschärfung der Zustands-Serialisierbarkeit. Es wird zusätzlich verlangt, daß jede Leseoperation in den beiden 'Schedules' jeweils den Wert von derselben Schreiboperation erhält.

Konflikt-Serialisierbarkeit (KSR)

verlangt, daß die Reihenfolge jeweils zweier in Konflikt stehenden Operationen in beiden 'Schedules' gleich bleibt.

Erkäutern Sie das Read-Write Modell für Transaktionen!

Eine Transaktion ist eine endliche Folge von Schritten oder Aktionen der Form read(x) oder write(x). Somit ist eine Transaktion ein Straight-line Programm von Lese und Schreiboperationen. Es wird die Annahme gemacht, das eine Transaktion keine internen Redundanzen aufweisst. D.h. jedes Datenobjekt wird nur einmal gelesen bzw. geschrieben. Read bzw. Write aktionen sind atomar und dürfen nicht unterbrochen werden.

Schedule-Prinzip

Schwerpunkte:

Zeitlich verzahnte Ausführungsreihenfolgen von Schritten (read oder write) werden durch Schedules modelliert. (dynamischer Aspekt)
Unter welchen Bedingungen ist ein Schedule korrekt?
Entwurf und Verifizierung von Scheduling-Verfahren oder kurz Schedulern.

Was sind Schedules?

Durch Hinzunahme von zwei Pseudoschritten zu den Schritten read und write, lassen sich Schedules modellieren:

Commit - Transaktion erfolgreich beendet. Ergebnisse können für andere Prozesse freigegeben werden.

Abort - Transaktion aufgrund eines Fehlers vorzeitig abgebrochen.

Vollständige Schedules sind Schedules, bei denen alle geöffneten Schritte terminiert werden und auch die Schritte a und c enthalten sind. Normale Schedules beinhalten dies normalerweise nicht, da aus Effizienzgründen bei Begin einer Transaktionsverarbeitung noch gar nicht alle Transaktionen vorhanden sind. Diese Treffen beim Scheduler ja eh Schrittweise ein...

Zwei Daten-Operationen stehen im Konflikt, falls sie auf demselben Objekt operieren und eine von ihnen schreibt.

Was heißt Serialisierbarkeit?

Ein Schedule heißt seriell, wenn alle Schritte einer Transaktion unmittelbar hintereinander ablaufen. Zwei Schedules sind äquivalent, wenn sie die gleichen Transaktionen beherbergen und die gleiche Abhängigkeitsrelation besitzen. Ein Schedule heißt Konflikt-serialisierbar, wenn es für den Schedule einen äquivalenten seriellen Schedule gibt. D.h. wenn ein zeitlich verzahnter Schedule die gleichen Konflikte wie irgend eine serielle Abarbeitung aufweist, so kann dieser als Konsistenz bewahrend eingestuft werden.

Prüfen lässt sich dies mit einem Präzedenzgraph, welcher als Knoten die Transaktionen und die Kanten nach der zeitlichen Abarbeitung beinhaltet. Tritt in diesem Graph ein Zyklus auf, so ist der Schedule nicht Konflikt-serialisierbar. Die topologische Sortierung eines DAG's würde einen korrekten Schedule ergeben.

Erklären Sie wie Serialisierbarkeitsbedinung und Logs arbeiten!

Ein Log ist eine Folge von Read bzw. Write Operationen auf ein bestimmtes Objekt x mit der dazugehörigen Transaktionsnummer als Index. Gibt es zwei Transaktionsfolgen T1 und T2, so könnte im Log für das Objekt a (log(a)) folgende Folge von Operationen stehen:

r1 w1 r2 w2

Dies heißt nichts anderes als:

Objekt a wird von Transaktionsfolge 1 gelesen
Objekt a wird von Transaktionsfolge 1 geschrieben
Objekt a wird von Transaktionsfolge 2 gelesen
Objekt a wird von Transaktionsfolge 2 geschrieben

In den einzelnen Logs muss eine eindeutige serielle Ausführung der Operationen möglich sein. Treten in zwei oder mehr verschiedenen Logs unterschiedliche Reihenfolgen auf wie z.B. r2 < r1, so ist das system nicht serialisierbar.

Überprüfen kann man die Deadlocks über den Wartegraphen, welcher sich leicht aus den Logs herstellen läßt.

Wie prüft man einen Schedule auf Deadlocks?

Man stellt die einzelnen Logs auf und prüft den Wartegraphen. Ein Log ist eine Folge von Transaktionen auf ein bestimmtes Objekt. Folgendes Beispiel soll das Vorgehen erläutern.

Folgender Schedule ist gegeben:

S[r1(b),r2(b),w2(b),r2(c),r2(d),r3(b),r4(d),w3(a),w4(d),r5(a),r5(c),w2(c)]

1. Aufstellen der Logs für die beteiligten Objekte a,b,c und d

log(A)	log(b)	log(c)	log(d)
w3 r5	r1 r2 w2 r3	r2 r5 w2	r2 r4 w4

2. Den Wartegraphen nach dem extrahierten Log aufstellen

1. Zeichne für jede Transaktion einen Knoten.
2. Wiederhole für jeden Log in welchem mindestens eine Transaktion schreibt und zwei lesend zugreifen:

Verbinde jede Leseoperation r vor dem Write mit dem Knoten der Schreibertransaktion
Verbinde jede Schreibertransaktion mit jedem danach folgenden Readbefehl
Schlingen sind zwecklos und können dabei ignoriert werden

3. Wartegraph auf Zyklus prüfen, denn mit ist der Schedule nicht serialisierbar

Wie wir sehen enthält der Graph einen Zyklus. Dies bedeutet, daß die genannten Bedingungen in den Logs nicht gelten. Und zwar das die Reihenfolgen der Zugriffe in allen Logs gleich ist. Dies ist hier nicht der Fall. Denn was nicht sein darf, ist

T2 vor T3 kommt, T3 vor T5 komt und T5 vor T2 kommt

Deshalb erzeugen T2, T3 und T5 einen Deadlock.

Was ist die Serialisierbarkeitsbedinung in Schedules?

Die oben erkläre Bedingung lässt sich auf Schedules übertragen. Ein Schedule ist ja nichts weiter als eine Folge von Read / Write Operationen, welche als Zusammenfassung aller Logs aufgefasst werden kann. Somit gilt in einer Schedule die Serialisierbarkeitsbedinung ebenso. Desweiteren kann man aus einer Schedule die einzelnen Logs herleiten.

Ein Schedule ist nicht serialisierbar, wenn sein Graph bestehend aus den Transaktionen und den gerichteten Kanten, welche den Ablauf beschreiben, einen zyklus enthält.

Wann stehen zwei Operationen bzw. Transaktionen in Konflikt?

Wenn beide auf das selbe Objekt zugreifen und eine von beiden eine Schreiboperation ist.

Warum wird nicht ein Prinzip wie "Shortest Transaction Next" angewandt?

Weil solche Prinzipien nicht die Reihenfolge der Transaktionen beibehalten!

Welche Synchronisationsprobleme gibt es?

Lost Update

read1(x)  >  read2(x)  >  update1(x)  >  update2(x)

Das Update von Prozess 1 geht somit verloren.

Dirty Read

Read1(x)  >  Update1(x)  >  Write1(x)

>  Read2(x)  >  Update2(x)  >  ABORT1 > Write2(x)

Inconsistent Read

Prozess eins ließt ein Datum und speichert es zwischen. Prozess 2 dagegen, ändert das Datum erst danach und somit hat Prozess 1 den falschen alten Wert des Datums gelesen.

Was passiert alles bei einem Commit?

After-Images müssen zu diesem Zeitpunkt im Log stehen
Before-Images können verworfen werden
Datenbank kann muß aber nicht geschrieben sein (Daten können sich auch noch im Systempuffer befinden)
Daten werden für die Außenwelt sichtbar

Welche Sychronisationsverfahren für Schedules gibt es?

verifizierend (optimistisch, validierend):

Vor dem Commit wird geprüft, ob eine Transaktion an einer nichtserialisierbaren Schedule beteiligt ist. Falls ja, dann wird die Transaktion abgebrochen. (abort) Die Prüfung auf Serialisierbarkeit wird auch certification bzw. validation genannt.

präventiv (pessimistisch): nicht-serialisierbare Schedules werden verhindert, v.a. durch Sperrverfahren, welche durch Sperren gemeinsamer Objekte gemeinsamen Zugriff verhindern (selten durch Zeitstempelverfahren).

Wie sehen optimistische Verfahren aus?

In der Arbeitsphase sind nur lesende Zugriffe auf die Datenbank möglich (kein Rollback nötig). Die Zwischenspeicherung erfolgt in einen privaten Arbeitsbereich.

In der Validationsphase erfolgt die Prüfung auf Nicht-Serialisierbarkeit der entstandenen Schedule (Abhängigkeitsgraph hat Zyklen).

Definition der Abhängigkeit:

- S: Schedule (Folge von Lese- und Schreiboperationen)
- T:Transaktionen in S

Konflikt zwischen zwei Operationen besteht wenn:

Zugriff auf dasselbe Objekt erfolgt, davon mindestens ein Schreibzugriff.
Ty ist abhängig von Tx, gdw. es Operationen ax und by gibt die in Konflikt miteinander stehen und ax vor by in S ausgeführt werden soll.

Schreibphase: veränderte Objekte werden in die Datenbank geschrieben (Commit).

Was genau passiert in der Validationsphase, welche Operationen werden hier betrachtet?

Es genügt schreibende Zugriffe parallel ablaufender Transaktionen zu betrachten und mit den Lese- und Schreiboperationen der Transaktion für die die Validation durchgeführt wird zu vergleichen. Die Prüfung auf Zyklen erfolgt auch hier im Abhängigkeitsgraph.

Knoten: Transaktionen, gerichtete Kanten zu jeweils abhängigen Transaktion

Abhängigkeit:

mindestens eine Operation steht im Konflikt mit einer vorher in der Schedule stehenden Operation einer anderen Transaktion.

Wie kann man Transaktionen synchronisieren?

Durch den Einsatz von Synchronisationsverfahren:

verifizierende Verfahren (optimistisch)
präventive Verfahren (pessimistisch)
z.B. Sperrverfahren, Zeitstempelverfahren

Welche Sperrverfahren gibt es?

Zwei-Phasen-Sperrprotokolle werden am häufigsten benutzt - vor allem Sperren bis EOT. Premclaiming wird dagegen kaum verwendet. Folgende weitere klassifikation ist möglich...

RX-Sperrverfahren:

Alle Transaktionen können gleichzeitig das Datenobjekt lesen. Falls eine Transaktion ein Datenobjekt ändert, müssen die Anderen warten.

RAX-Sperrverfahren:

Die Änderung des Datenobjektes erfolgt erst auf einer Kopie, so dass andere Transaktionen das Datenelement trotzdem weiterhin lesen können. Erst bei Transaktionsende wird das Datenobjekt durch die Kopie überschrieben.

RAC-Sperrverfahren:

Das Überschreiben des Datenelements durch die Kopie kann beim RAX-Sperrverfahren erst erfolgen, wenn keine lesenden Transaktionen mehr auf das Datenobjekt zugreifen. Das RAC-Sperrverfahren läßt demgegenüber weiterhin das Lesen zu, da beim Transaktionsende eine Kopie des ursprünglichen Datenobjekts geschrieben wird, auf die im Bedarfsfall zugegriffen werden kann.

Erläutern Sie die Concurrency Control!

Dynamische Erzeugung serialisierbarer Schedules, um Mehrbenutzerbetrieb zu überwachen und zu regulieren.

Schedule-Prinzip

Sendet der Scheduler ein Commit an den Recovery-Manager, so ist die Transaktion erfolgreich beendet worden. Dies bedeutet auch, daß alle Transaktionen im Scheduler initiiert werden. Wird ein Abort an den Recovery-Manager übermittelt, so weiß dieser, daß der Effekt nicht in der Datenbank sichtbar werden soll.

Was macht der Lock-Manager?

Der Lock-Manager ist Teil des Transaktionsmanagers, welcher die Lock- und Unlock-Prozeduren verwaltet und ausführt. Seine Aufgaben sind

das Setzen und Freigeben von Sperren nach 2-PL
die Verhinderung von Dauerhaften Blockaden
die Deadlockerkennung, -auflösung und -verhinderung

Der Lock-Manager verwaltet seine Sperren in einer Tabelle, welche Einträge in der Form Objekt-ID, Transaction-ID und Modus (read,write,intentieren) enthält. Falls weitere Transaktionen einen weiteren Lock erfordern, werden diese an eine Warteschlange an die entsprechende Zeile angehängt.

Was ist Preclaiming?

Alle von einer Transaktionen benötigten Objekte werden vor Ausführung zusammen gesperrt. Notwendig dafür ist, dass alle notwendigen Betriebsmittel (hier read bzw write auf Objekte) vorher bekannt sein müssen. Eine andere weniger elegante Möglichkeit ist die des Timeouts. Nach einer definierten Wartezeit wird die Transaktion abgebrochen.

Inhalt

Anfang

zurück

vor

Kapitel 1	DBMS Konzept
Eigenschaften, Bestandteile, Ebenen...
Kapitel 2	DB Entwurf
Qualitätsmerkmale, funktionale Abhängigkeiten, ER...
Kapitel 3	Normalformen
Übersicht Normalformen, Anomalien...
Kapitel 4	Relationalität
Regeln und Vorgehensweisen...
Kapitel 5	Sprachen
relationale Sprachen, SQL, Query...
Kapitel 6	Datenorganisation
Tertiärspeicher, Adressierung, Indexe, ISAM...
Kapitel 7	Transaktionskonzept
Datenintegrität, Serialisierbarkeit, ACID...
Kapitel 8	Concurrency Control
Read-Write Modell, Schedules, Prinzip...
Kapitel 9	Scheduler & Recovery
2-Phasen-Sperren,Deadlocks,Recovery...