Verteiltes DBMS - Steuern der Parallelität

Parallelitätssteuerungstechniken stellen sicher, dass mehrere Transaktionen gleichzeitig ausgeführt werden, während die ACID-Eigenschaften der Transaktionen und die Serialisierbarkeit in den Zeitplänen beibehalten werden.

In diesem Kapitel werden die verschiedenen Ansätze zur Parallelitätskontrolle untersucht.

Sperrbasierte Parallelitätssteuerungsprotokolle

Sperrbasierte Parallelitätssteuerungsprotokolle verwenden das Konzept des Sperrens von Datenelementen. EINlockist eine einem Datenelement zugeordnete Variable, die bestimmt, ob Lese- / Schreibvorgänge für dieses Datenelement ausgeführt werden können. Im Allgemeinen wird eine Sperrkompatibilitätsmatrix verwendet, die angibt, ob ein Datenelement durch zwei Transaktionen gleichzeitig gesperrt werden kann.

Auf Sperren basierende Parallelitätskontrollsysteme können entweder einphasige oder zweiphasige Sperrprotokolle verwenden.

Einphasen-Sperrprotokoll

Bei dieser Methode sperrt jede Transaktion ein Element vor der Verwendung und gibt die Sperre frei, sobald die Verwendung beendet ist. Diese Sperrmethode sorgt für maximale Parallelität, erzwingt jedoch nicht immer die Serialisierbarkeit.

Zweiphasen-Sperrprotokoll

Bei dieser Methode gehen alle Sperrvorgänge dem ersten Sperr- oder Entsperrvorgang voraus. Die Transaktion besteht aus zwei Phasen. In der ersten Phase erhält eine Transaktion nur alle erforderlichen Sperren und gibt keine Sperre frei. Dies nennt man das Erweitern oder dasgrowing phase. In der zweiten Phase gibt die Transaktion die Sperren frei und kann keine neuen Sperren anfordern. Dies nennt man dasshrinking phase.

Jede Transaktion, die dem Zwei-Phasen-Sperrprotokoll folgt, ist garantiert serialisierbar. Dieser Ansatz bietet jedoch eine geringe Parallelität zwischen zwei widersprüchlichen Transaktionen.

Algorithmen zur Steuerung der Parallelität von Zeitstempeln

Auf Zeitstempeln basierende Algorithmen zur Steuerung der Parallelität verwenden den Zeitstempel einer Transaktion, um den gleichzeitigen Zugriff auf ein Datenelement zu koordinieren und die Serialisierbarkeit sicherzustellen. Ein Zeitstempel ist eine eindeutige Kennung, die DBMS einer Transaktion gibt, die die Startzeit der Transaktion darstellt.

Diese Algorithmen stellen sicher, dass Transaktionen in der durch ihre Zeitstempel vorgegebenen Reihenfolge festgeschrieben werden. Eine ältere Transaktion sollte vor einer jüngeren Transaktion festgeschrieben werden, da die ältere Transaktion vor der jüngeren in das System eingeht.

Zeitstempel-basierte Parallelitätssteuerungstechniken generieren serialisierbare Zeitpläne, sodass der entsprechende serielle Zeitplan in der Reihenfolge des Alters der teilnehmenden Transaktionen angeordnet ist.

Einige der auf Zeitstempeln basierenden Algorithmen zur Steuerung der Parallelität sind:

Grundlegender Algorithmus für die Reihenfolge von Zeitstempeln.
Konservativer Algorithmus für die Reihenfolge von Zeitstempeln.
Multiversionsalgorithmus basierend auf der Reihenfolge der Zeitstempel.

Die zeitstempelbasierte Bestellung folgt drei Regeln, um die Serialisierbarkeit zu erzwingen:

Access Rule- Wenn zwei Transaktionen gleichzeitig versuchen, auf dasselbe Datenelement zuzugreifen, wird bei widersprüchlichen Vorgängen der älteren Transaktion Vorrang eingeräumt. Dies führt dazu, dass die jüngere Transaktion darauf wartet, dass die ältere Transaktion zuerst festgeschrieben wird.
Late Transaction Rule- Wenn eine jüngere Transaktion ein Datenelement geschrieben hat, darf eine ältere Transaktion dieses Datenelement nicht lesen oder schreiben. Diese Regel verhindert, dass die ältere Transaktion festgeschrieben wird, nachdem die jüngere Transaktion bereits festgeschrieben wurde.
Younger Transaction Rule - Eine jüngere Transaktion kann ein Datenelement lesen oder schreiben, das bereits von einer älteren Transaktion geschrieben wurde.

Optimistischer Parallelitätskontrollalgorithmus

In Systemen mit niedrigen Konfliktraten kann die Aufgabe, jede Transaktion auf Serialisierbarkeit zu überprüfen, die Leistung beeinträchtigen. In diesen Fällen wird der Test auf Serialisierbarkeit auf kurz vor dem Festschreiben verschoben. Da die Konfliktrate niedrig ist, ist auch die Wahrscheinlichkeit gering, Transaktionen abzubrechen, die nicht serialisierbar sind. Dieser Ansatz wird als optimistische Parallelitätssteuerungstechnik bezeichnet.

Bei diesem Ansatz ist der Lebenszyklus einer Transaktion in die folgenden drei Phasen unterteilt:

Execution Phase - Eine Transaktion ruft Datenelemente in den Speicher ab und führt Operationen an ihnen aus.
Validation Phase - Eine Transaktion führt Überprüfungen durch, um sicherzustellen, dass das Festschreiben ihrer Änderungen an der Datenbank den Serialisierbarkeitstest besteht.
Commit Phase - Eine Transaktion schreibt ein geändertes Datenelement im Speicher auf die Festplatte zurück.

Dieser Algorithmus verwendet drei Regeln, um die Serialisierbarkeit in der Validierungsphase zu erzwingen:

Rule 1- zwei Transaktionen T Da _i und T _j , wenn T _i wird das Datenelement zu lesen , die T _j , dann T schreibt _i ‚s Ausführungsphase nicht überlappen kann mit T _j ‚s Festschreibungsphase. T _j kann erst _{festgeschrieben} werden, nachdem T _i die Ausführung beendet hat.

Rule 2- zwei Transaktionen T Da _i und T _j , wenn T _i wird das Datenelement zu schreiben , dass T _j liest, dann T _i ‚s Phasen - Commit nicht überlappen kann mit T _j ‚Ausführungsphase s. T _j kann erst ausgeführt werden, nachdem T _i bereits festgeschrieben hat.

Rule 3- Wenn bei zwei Transaktionen T _i und T _j T _i das Datenelement schreibt, das T _j auch schreibt, kann sich die Festschreibungsphase von T _i nicht mit der Festschreibungsphase von T _j überschneiden . T _j kann erst mit dem Festschreiben beginnen, nachdem T _i bereits festgeschrieben hat.

Parallelitätskontrolle in verteilten Systemen

In diesem Abschnitt werden wir sehen, wie die oben genannten Techniken in einem verteilten Datenbanksystem implementiert werden.

Verteilter Zwei-Phasen-Verriegelungsalgorithmus

Das Grundprinzip der verteilten Zweiphasenverriegelung entspricht dem Grundprotokoll der Zweiphasenverriegelung. In einem verteilten System gibt es jedoch Sites, die als Sperrmanager bezeichnet werden. Ein Sperrmanager steuert Sperrerfassungsanforderungen von Transaktionsmonitoren. Um die Koordination zwischen den Sperrmanagern an verschiedenen Standorten zu erzwingen, erhält mindestens ein Standort die Berechtigung, alle Transaktionen anzuzeigen und Sperrenkonflikte zu erkennen.

Abhängig von der Anzahl der Standorte, die Sperrkonflikte erkennen können, gibt es drei Arten von verteilten Zweiphasen-Sperransätzen:

Centralized two-phase locking- Bei diesem Ansatz wird ein Standort als zentraler Sperrmanager festgelegt. Alle Standorte in der Umgebung kennen den Standort des Zentralschlosermanagers und erhalten bei Transaktionen eine Sperre von diesem.
Primary copy two-phase locking- Bei diesem Ansatz werden mehrere Standorte als Schleusenkontrollzentren ausgewiesen. Jeder dieser Standorte ist für die Verwaltung eines definierten Satzes von Sperren verantwortlich. Alle Standorte wissen, welches Sperrkontrollzentrum für die Verwaltung der Sperrung welcher Datentabelle / welchen Fragmentelements verantwortlich ist.
Distributed two-phase locking- Bei diesem Ansatz gibt es eine Reihe von Sperrmanagern, bei denen jeder Sperrmanager Sperren von Datenelementen steuert, die an seinem lokalen Standort gespeichert sind. Der Speicherort des Sperrmanagers basiert auf der Datenverteilung und -replikation.

Verteilte Zeitstempel-Parallelitätskontrolle

In einem zentralisierten System wird der Zeitstempel einer Transaktion durch das Lesen der physischen Uhr bestimmt. In einem verteilten System können die lokalen physischen / logischen Taktwerte eines Standorts jedoch nicht als globale Zeitstempel verwendet werden, da sie nicht global eindeutig sind. Ein Zeitstempel besteht also aus einer Kombination der Site-ID und dem Uhrwert dieser Site.

Für die Implementierung von Zeitstempel-Bestellalgorithmen verfügt jeder Standort über einen Scheduler, der für jeden Transaktionsmanager eine separate Warteschlange verwaltet. Während der Transaktion sendet ein Transaktionsmanager eine Sperranforderung an den Scheduler der Site. Der Scheduler stellt die Anforderung in aufsteigender Zeitstempelreihenfolge in die entsprechende Warteschlange. Anfragen werden von der Vorderseite der Warteschlangen in der Reihenfolge ihrer Zeitstempel verarbeitet, dh der ältesten zuerst.

Konfliktdiagramme

Eine andere Methode besteht darin, Konfliktdiagramme zu erstellen. Hierzu werden Transaktionsklassen definiert. Eine Transaktionsklasse enthält zwei Datenelemente, die als Lesesatz und Schreibsatz bezeichnet werden. Eine Transaktion gehört zu einer bestimmten Klasse, wenn die Lesemenge der Transaktion eine Teilmenge der Lesemenge der Klasse und die Schreibmenge der Transaktion eine Teilmenge der Schreibmenge der Klasse ist. In der Lesephase gibt jede Transaktion ihre Leseanforderungen für die Datenelemente in ihrem Lesesatz aus. In der Schreibphase gibt jede Transaktion ihre Schreibanforderungen aus.

Für die Klassen, zu denen aktive Transaktionen gehören, wird ein Konfliktdiagramm erstellt. Diese enthält eine Reihe vertikaler, horizontaler und diagonaler Kanten. Eine vertikale Kante verbindet zwei Knoten innerhalb einer Klasse und kennzeichnet Konflikte innerhalb der Klasse. Eine horizontale Kante verbindet zwei Knoten über zwei Klassen und kennzeichnet einen Schreib-Schreib-Konflikt zwischen verschiedenen Klassen. Eine diagonale Kante verbindet zwei Knoten über zwei Klassen und bezeichnet einen Schreib-Lese- oder einen Lese-Schreib-Konflikt zwischen zwei Klassen.

Die Konfliktdiagramme werden analysiert, um festzustellen, ob zwei Transaktionen innerhalb derselben Klasse oder über zwei verschiedene Klassen hinweg parallel ausgeführt werden können.

Verteilter optimistischer Algorithmus zur Steuerung der Parallelität

Der verteilte optimistische Parallelitätskontrollalgorithmus erweitert den optimistischen Parallelitätskontrollalgorithmus. Für diese Erweiterung werden zwei Regeln angewendet -

Rule 1- Nach dieser Regel muss eine Transaktion bei ihrer Ausführung an allen Standorten lokal validiert werden. Wenn festgestellt wird, dass eine Transaktion an einem Standort ungültig ist, wird sie abgebrochen. Die lokale Validierung garantiert, dass die Transaktion an den Standorten, an denen sie ausgeführt wurde, seriell bleibt. Nachdem eine Transaktion den lokalen Validierungstest bestanden hat, wird sie global validiert.

Rule 2- Nach dieser Regel sollte eine Transaktion, nachdem sie den lokalen Validierungstest bestanden hat, global validiert werden. Durch die globale Validierung wird sichergestellt, dass zwei widersprüchliche Transaktionen, die an mehr als einem Standort zusammen ausgeführt werden, an allen Standorten, an denen sie zusammen ausgeführt werden, in derselben relativen Reihenfolge festgeschrieben werden. Dies kann erfordern, dass eine Transaktion nach der Validierung vor dem Festschreiben auf die andere widersprüchliche Transaktion wartet. Diese Anforderung macht den Algorithmus weniger optimistisch, da eine Transaktion möglicherweise nicht festgeschrieben werden kann, sobald sie an einem Standort validiert wird.