Parallelitätskontrolle in Datenbankmanagementsystemen: Sperr- und zeitstempelbasierte Protokolle

Was ist Parallelitätskontrolle?

Gleichzeitigkeitskontrolle In einem Datenbankmanagementsystem ist dies ein Verfahren zur Verwaltung gleichzeitiger Operationen ohne Konflikte. Es stellt sicher, dass Datenbanktransaktionen gleichzeitig und präzise ausgeführt werden, um korrekte Ergebnisse zu erzielen, ohne die Datenintegrität der jeweiligen Datenbank zu beeinträchtigen.

Gleichzeitiger Zugriff ist recht einfach, wenn alle Benutzer lediglich Daten lesen, da sie sich nicht gegenseitig beeinträchtigen können. In der Praxis führt eine Datenbank jedoch sowohl Lese- als auch Schreibvorgänge durch, wodurch die gleichzeitige Zugriffskontrolle zu einer Herausforderung wird.

Die Parallelitätskontrolle von Datenbankmanagementsystemen (DBMS) dient der Behebung solcher Konflikte, die hauptsächlich in Mehrbenutzersystemen auftreten. Sie ist daher eines der wichtigsten Elemente für das ordnungsgemäße Funktionieren einer Datenbank, in der zwei oder mehr Transaktionen gleichzeitig ausgeführt werden und auf dieselben Daten zugreifen müssen. Sie arbeitet eng mit der Parallelitätskontrolle zusammen. Transaktionsmanagement, welche die Arbeitseinheiten definiert, die die Parallelitätskontrolle sicher miteinander verschachteln muss.

Mögliche Probleme der Gleichzeitigkeit

Hier sind einige Probleme, mit denen Sie wahrscheinlich konfrontiert werden, wenn Sie keine ordnungsgemäße DBMS-Parallelitätskontrolle implementieren:

• Verlorene Updates tritt auf, wenn mehrere Transaktionen dieselbe Zeile auswählen und sie basierend auf dem ausgewählten Wert aktualisieren.
• Nicht festgelegte Abhängigkeit Ein Dirty Read tritt auf, wenn eine zweite Transaktion eine Zeile auswählt, die bereits von einer anderen, noch nicht abgeschlossenen Transaktion aktualisiert wurde.
• Nicht wiederholbares Lesen tritt auf, wenn eine zweite Transaktion mehrmals auf dieselbe Zeile zugreift und jedes Mal unterschiedliche Daten liest.
• Falsche Zusammenfassung Dies tritt auf, wenn eine Transaktion die Werte aller Instanzen eines wiederholten Datenelements summiert, während eine zweite Transaktion nur einige dieser Instanzen aktualisiert. Die resultierende Summe spiegelt kein korrektes Ergebnis wider.

Warum sollte man eine Parallelitätsmethode verwenden?

Gründe für die Verwendung einer Methode zur Steuerung der Parallelverarbeitung in DBMS:

• Um die Isolation durch gegenseitigen Ausschluss zwischen widersprüchlichen Transaktionen anzuwenden.
• Zur Behebung von Lese-/Schreibkonflikten.
• Um die Konsistenz der Datenbank durch die ständige Durchsetzung von Ausführungsbeschränkungen zu gewährleisten.
• Die Interaktion zwischen gleichzeitig ablaufenden Transaktionen wird mithilfe von Parallelitätssteuerungsmechanismen kontrolliert.
• Um die Serialisierbarkeit zu gewährleisten.

Beispiel

Angenommen, zwei Personen gehen gleichzeitig zu einem elektronischen Kiosk, um eine Kinokarte für denselben Film und dieselbe Vorstellungszeit zu kaufen.

Für diese Vorstellung ist jedoch nur noch ein Platz im Kino frei. Ohne Zugriffskontrolle könnten beide Kinobesucher eine Karte kaufen. Die Zugriffskontrolle verhindert dies. Beide Besucher können weiterhin auf die Informationen in der Sitzplatzdatenbank zugreifen, aber die Zugriffskontrolle stellt die Karte nur demjenigen zur Verfügung, der den Kaufvorgang zuerst abschließt.

Parallelitätskontrollprotokolle

Verschiedene Protokolle zur Steuerung des gleichzeitigen Zugriffs bieten unterschiedliche Kompromisse zwischen dem Grad der zulässigen Parallelität und dem damit verbundenen Mehraufwand. Die wichtigsten Techniken zur Steuerung des gleichzeitigen Zugriffs in Datenbankmanagementsystemen (DBMS) sind:

• Sperrbasierte Protokolle
• Zweiphasen-Verriegelungsprotokoll
• Zeitstempelbasierte Protokolle
• Validierungsbasierte Protokolle

Im Folgenden werden die einzelnen Protokolle nacheinander untersucht, beginnend mit den am weitesten verbreiteten, sperrbasierten Protokollen.

Sperrbasierte Protokolle

Sperrbasierte Protokolle In Datenbankmanagementsystemen (DBMS) gibt es einen Mechanismus, der verhindert, dass eine Transaktion ein Datenelement lesen oder schreiben kann, bevor sie eine entsprechende Sperre erhalten hat. Sperrbasierte Protokolle tragen zur Beseitigung des Problems der Parallelität bei, indem sie ein bestimmtes Datenelement für eine einzelne Transaktion sperren oder isolieren.

Eine Sperre ist eine Datenvariable, die einem Datenelement zugeordnet ist und angibt, welche Operationen darauf ausgeführt werden dürfen. Sperren tragen zur Synchronisierung des Zugriffs auf Datenbankelemente durch gleichzeitige Transaktionen bei. Alle Sperranforderungen werden an den Zugriffskontrollmanager gestellt, und Transaktionen werden erst ausgeführt, wenn die Sperranforderung erteilt wurde.

Binäre Schlösser: Eine binäre Sperre für ein Datenelement kann sich entweder im gesperrten oder im entsperrten Zustand befinden.

Gemeinsam/Exklusiv: Dieser Sperrmechanismus unterscheidet Sperren anhand ihres Verwendungszwecks. Wird eine Sperre für einen Schreibvorgang benötigt, spricht man von einer exklusiven Sperre.

1. Gemeinsame Sperre (S): Eine gemeinsame Sperre wird auch als schreibgeschützte Sperre bezeichnet. Bei einer gemeinsamen Sperre kann ein Datenelement von mehreren Transaktionen gemeinsam genutzt werden, da keine der Transaktionen die Berechtigung hat, das Element zu aktualisieren. Wenn beispielsweise zwei Transaktionen den Kontostand einer Person lesen, Datenbank Durch das Setzen einer gemeinsamen Sperre können sie lesen. Wenn eine andere Transaktion diesen Kontostand aktualisieren möchte, verhindert die gemeinsame Sperre dies, bis der Lesevorgang abgeschlossen ist.

2. Exklusive Sperre (X): Mit einer exklusiven Sperre können Daten sowohl gelesen als auch geschrieben werden. Sie ist exklusiv und kann nicht gleichzeitig für dasselbe Datenelement gehalten werden. Eine X-Sperre wird mit dem Befehl `lock-x` angefordert. Wenn beispielsweise eine Transaktion einen Kontostand aktualisieren muss, wird dies durch das Setzen einer X-Sperre ermöglicht; eine zweite Transaktion, die lesen oder schreiben möchte, wird dadurch verhindert.

3. Simplistisches Sperrprotokoll: Dies ermöglicht es Transaktionen, vor Beginn einer Operation eine Sperre für jedes Objekt zu erhalten. Transaktionen können die Daten nach Abschluss des Schreibvorgangs wieder freigeben.

4. Vorab-Sperrung: Dieses Protokoll wertet Operationen aus und erstellt eine Liste der für die Ausführung benötigten Datenelemente. Sobald alle Sperren erteilt wurden, wird die Transaktion ausgeführt, und alle Sperren werden nach Abschluss der Operationen wieder freigegeben.

Hunger: Von „Starvation“ spricht man, wenn eine Transaktion unbestimmte Zeit auf eine Sperre warten muss. Gründe hierfür können ein schlecht verwaltetes Warteschema für gesperrte Elemente, ein Ressourcenleck oder die wiederholte Auswahl derselben Transaktion als Opfer sein.

Deadlock: Ein Deadlock ist eine Situation, in der zwei oder mehr Prozesse aufeinander warten, bis ein anderer eine Ressource freigibt, wodurch eine kreisförmige Kette entsteht.

Zweiphasen-Verriegelungsprotokoll (2PL)

Das Zweiphasen-Verriegelungsprotokoll, auch bekannt als 2PL, ist eine Methode der Parallelitätskontrolle, die die Serialisierbarkeit durch Anwenden einer Sperre auf Transaktionsdaten sicherstellt, wodurch andere Transaktionen daran gehindert werden, gleichzeitig auf dieselben Daten zuzugreifen.

Das Zwei-Phasen-Sperrprotokoll ermöglicht es jeder Transaktion, eine Sperr- oder Entsperranforderung in zwei Schritten zu stellen:

• Wachstumsphase: In dieser Phase kann eine Transaktion Sperren erhalten, aber keine Sperren freigeben.
• Schrumpfphase: In dieser Phase kann eine Transaktion Sperren freigeben, aber keine neuen Sperren erhalten.

Es stimmt, dass 2PL Serialisierbarkeit bietet. Allerdings garantiert es nicht, dass keine Deadlocks auftreten. Im obigen Diagramm suchen lokale und globale Deadlock-Detektoren nach Deadlocks und beheben diese, indem sie Transaktionen in ihren Ausgangszustand zurücksetzen.

Strenge Zweiphasen-Verriegelungsmethode

Strict 2PL ist fast identisch mit 2PL. Der einzige Unterschied besteht darin, dass Strict 2PL eine Sperre nach ihrer Verwendung nie wieder freigibt. Es hält alle Sperren bis zum Commit-Punkt und gibt sie alle gleichzeitig frei, wenn der Prozess beendet ist.

Zentralisiertes 2PL

Bei zentralisiertem 2PL ist ein einziger Standort für die Sperrverwaltung zuständig. Es gibt nur einen Sperrmanager für das gesamte DBMS.

Primärkopie 2PL

Im Primary Copy 2PL-Mechanismus sind viele Sperrmanager auf verschiedene Standorte verteilt, wobei ein bestimmter Sperrmanager für die Sperre einer Gruppe von Datenelementen zuständig ist. Wird die primäre Kopie aktualisiert, wird die Änderung an die Slaves weitergegeben.

Verteiltes 2PL

Bei diesem Mechanismus werden Sperrverwalter auf alle Standorte verteilt und sind für die Verwaltung der Datensperren am jeweiligen Standort zuständig. Werden keine Daten repliziert, entspricht dies der Zwei-Faktor-Authentifizierung (2PL) mit primärer Kopie. Die Kommunikationskosten der verteilten 2PL sind deutlich höher als die der Zwei-Faktor-Authentifizierung mit primärer Kopie.

Zeitstempelbasierte Protokolle

Das Zeitstempelbasiertes Protokoll In Datenbankmanagementsystemen (DBMS) ist dies ein Algorithmus, der die Systemzeit oder einen logischen Zähler als Zeitstempel verwendet, um die Ausführung gleichzeitiger Transaktionen zu serialisieren. Er stellt sicher, dass jeder in Konflikt stehende Lese- und Schreibvorgang in der Reihenfolge des Zeitstempels ausgeführt wird.

Bei dieser Methode hat die ältere Transaktion stets Vorrang. Sie verwendet die Systemzeit, um den Zeitstempel der Transaktion zu bestimmen, und ist das am häufigsten verwendete Protokoll für parallele Transaktionen. Sperrbasierte Protokolle regeln die Ausführungsreihenfolge von Transaktionen, die in Konflikt stehen; zeitstempelbasierte Protokolle lösen Konflikte, sobald eine Operation erstellt wird.

Ejemplo:

Suppose there are three transactions T1, T2, and T3.
T1 has entered the system at time 0010
T2 has entered the system at 0020
T3 has entered the system at 0030
Priority will be given to transaction T1, then T2 and lastly T3.

Vorteile:

• Zeitpläne sind serialisierbar, genau wie 2PL-Protokolle.
• Kein Warten auf die Transaktion, wodurch die Möglichkeit von Deadlocks ausgeschlossen wird.

Nachteile: Eine Verhungern der Ressourcen ist möglich, wenn dieselbe Transaktion immer wieder neu gestartet und abgebrochen wird.

Validierungsbasiertes Protokoll

Das Validierungsbasiertes Protokoll In Datenbankmanagementsystemen (DBMS) ist dies, auch bekannt als optimistische Parallelitätssteuerung, eine Methode zur Vermeidung von Parallelitätskonflikten bei Transaktionen. Bei diesem Protokoll werden lokale Kopien der Transaktionsdaten aktualisiert, anstatt die Daten selbst, was zu weniger Störungen während der Ausführung führt.

Das Validierungsprotokoll wird in drei Phasen durchgeführt:

1. Lesephase
2. Validierungsphase
3. Schreibphase

Lesephase

In der Lesephase können Datenwerte von einer Transaktion gelesen werden, Schreibvorgänge oder Aktualisierungen werden jedoch nur auf die lokalen Datenkopien und nicht auf die eigentliche Datenbank angewendet.

Validierungsphase

In der Validierungsphase werden die Daten überprüft, um sicherzustellen, dass die Anwendung der Aktualisierungen die Serialisierbarkeit nicht verletzt.

Schreibphase

In der Schreibphase werden die Aktualisierungen in die Datenbank übernommen, wenn die Validierung erfolgreich ist; andernfalls werden die Aktualisierungen verworfen und die Transaktion wird zurückgesetzt.

Vergleich von Protokollen zur Steuerung gleichzeitiger Operationen

Die vier Protokollfamilien gehen unterschiedlich davon aus, wie häufig Transaktionen tatsächlich in Konflikt geraten. Die folgende Tabelle fasst zusammen, wo jede Familie einzuordnen ist.

Kurz gesagt, gehen sperrbasierte Protokolle und 2PL-Protokolle davon aus, dass Konflikte häufig auftreten und verhindern diese von vornherein, während Zeitstempel- und Validierungsprotokolle davon ausgehen, dass Konflikte selten sind und diese erst dann lösen, wenn sie auftreten.

Merkmale eines guten Parallelverarbeitungsprotokolls

Ein idealer Mechanismus zur Steuerung von Parallelität hat folgende Ziele:

• Es muss gegenüber Standort- und Kommunikationsausfällen robust sein.
• Es ermöglicht die parallele Ausführung von Transaktionen, um maximale Parallelität zu erreichen.
• Seine Speichermechanismen und Rechenmethoden sollten bescheiden sein, um den Overhead zu minimieren.
• Es muss bestimmte Einschränkungen für die Struktur der atomaren Aktionen von Transaktionen durchsetzen.

Häufig gestellte Fragen