Zwei-Phasen-Sperrung

Zwei-Phasen-SperrungBearbeiten

Nach dem Zwei-Phasen-Sperrungsprotokoll behandelt eine Transaktion ihre Sperren in zwei verschiedenen, aufeinanderfolgenden Phasen während der Ausführung der Transaktion:

1. Expandierende Phase (auch als Wachsende Phase bezeichnet): Sperren werden erworben und keine Sperren werden freigegeben (die Anzahl der Sperren kann nur zunehmen).
2. Schrumpfungsphase (auch Contracting-Phase genannt): Sperren werden freigegeben und es werden keine Sperren erworben.

Die Regeln für das Sperren in zwei Phasen lassen sich wie folgt zusammenfassen: niemals eine Sperre erwerben, nachdem eine Sperre freigegeben wurde. Die Serialisierbarkeitseigenschaft ist für einen Zeitplan mit Transaktionen, die diese Regel befolgen, garantiert.

Typischerweise wird ohne explizites Wissen in einer Transaktion über das Ende von Phase 1 erst dann sicher festgestellt, wenn eine Transaktion die Verarbeitung abgeschlossen und die Übergabe angefordert hat. In diesem Fall können alle Sperren auf einmal freigegeben werden (Phase 2).

Conservative two-phase lockingEdit

Der Unterschied zwischen 2PL und C2PL besteht darin, dass die Transaktionen von C2PL alle benötigten Sperren erhalten, bevor die Transaktionen beginnen. Damit soll sichergestellt werden, dass eine Transaktion, die bereits einige Sperren hält, nicht blockiert, während sie auf andere Sperren wartet. Conservative 2PL verhindert Deadlocks.

Strict two-phase lockingEdit

Um dem S2PL-Protokoll zu entsprechen, muss eine Transaktion 2PL einhalten und ihre (exklusiven) Schreibsperren erst freigeben, wenn sie beendet ist, d.h. entweder committed oder abgebrochen wurde. Andererseits werden Lesesperren (Shared Locks) während Phase 2 regelmäßig freigegeben. Dieses Protokoll ist für B-Bäume nicht geeignet, da es zu Engpässen führt (während B-Bäume immer von der übergeordneten Wurzel aus mit der Suche beginnen).

Strong strict two-phase lockingEdit

or Rigorousness, or Rigorous scheduling, or Rigorous two-phase locking

Um dem Strong strict two-phase locking (SS2PL) zu entsprechen, gibt das Sperrprotokoll die von einer Transaktion angelegten Schreib- (exclusive) und Lesesperren (shared) erst frei, wenn die Transaktion beendet ist, d.h., erst, nachdem die Ausführung abgeschlossen (bereit) und entweder bestätigt oder abgebrochen wurde. Dieses Protokoll entspricht auch den S2PL-Regeln. Eine Transaktion, die SS2PL gehorcht, hat eine Phase 1, die die gesamte Ausführungsdauer der Transaktion dauert, und keine Phase 2 (oder eine degenerierte Phase 2). Somit bleibt eigentlich nur eine Phase übrig, und die Bezeichnung „zweiphasig“ scheint aufgrund der historischen Entwicklung des Konzepts aus 2PL und der Tatsache, dass 2PL eine Superklasse ist, immer noch verwendet zu werden. Die SS2PL-Eigenschaft eines Zeitplans wird auch als Rigorosität bezeichnet. Es ist auch der Name der Klasse von Zeitplänen mit dieser Eigenschaft, und ein SS2PL-Zeitplan wird auch als „rigoroser Zeitplan“ bezeichnet. Der Begriff „Rigorosität“ ist frei von dem unnötigen Vermächtnis der „Zweiphasigkeit“ und unabhängig von einem (Sperr-)Mechanismus (im Prinzip können auch andere Sperrmechanismen verwendet werden). Der entsprechende Sperrmechanismus der Eigenschaft wird manchmal als Rigorous 2PL bezeichnet.

SS2PL ist ein Spezialfall von S2PL, d. h. die SS2PL-Klasse von Zeitplänen ist eine echte Unterklasse von S2PL (jeder SS2PL-Zeitplan ist auch ein S2PL-Zeitplan, aber es gibt S2PL-Zeitpläne, die nicht SS2PL sind).

SS2PL ist das Gleichzeitigkeitskontrollprotokoll der Wahl für die meisten Datenbanksysteme und wird seit ihren Anfängen in den 1970er Jahren verwendet. Es hat sich in vielen Situationen als wirksamer Mechanismus erwiesen und bietet neben Serialisierbarkeit auch Strenge (ein Spezialfall der kaskadenlosen Wiederherstellbarkeit), die für eine effiziente Datenbankwiederherstellung von entscheidender Bedeutung ist, sowie Commitment-Ordering (CO) für die Teilnahme an verteilten Umgebungen, in denen eine CO-basierte verteilte Serialisierbarkeit und globale Serialisierbarkeitslösungen eingesetzt werden. Da es sich um eine Teilmenge von CO handelt, ist eine effiziente Implementierung von verteiltem SS2PL ohne einen verteilten Sperrmanager (DLM) möglich, während verteilte Deadlocks (siehe unten) automatisch aufgelöst werden. Die Tatsache, dass SS2PL in Multi-Datenbank-Systemen die globale Serialisierbarkeit sicherstellt, war schon seit Jahren vor der Entdeckung von CO bekannt, aber erst mit CO wurde die Rolle eines atomaren Commitment-Protokolls bei der Aufrechterhaltung der globalen Serialisierbarkeit erkannt und die automatische Auflösung verteilter Deadlocks beobachtet (siehe ein detailliertes Beispiel für Distributed SS2PL). Tatsächlich ist die Tatsache, dass SS2PL die Eigenschaften von Recoverability und CO geerbt hat, bedeutsamer als die Tatsache, dass es eine Untermenge von 2PL ist, das in seiner allgemeinen Form nicht nur einen einfachen Serialisierungsmechanismus enthält (Serialisierbarkeit wird jedoch auch durch CO impliziert), sondern auch keine anderen wichtigen Eigenschaften von SS2PL aufweist. Es ist nicht bekannt, dass 2PL in seiner allgemeinen Form oder in Kombination mit Strictness, d. h. Strict 2PL (S2PL), in der Praxis verwendet wird. Das populäre SS2PL erfordert keine Markierung des „Endes von Phase 1“ wie 2PL und S2PL und ist daher einfacher zu implementieren. Außerdem bietet SS2PL im Gegensatz zum allgemeinen 2PL, wie oben erwähnt, die nützlichen Eigenschaften Strictness und Commitment Ordering.

Es gibt viele Varianten von SS2PL, die verschiedene Sperrtypen mit unterschiedlicher Semantik in verschiedenen Situationen verwenden, einschließlich Fällen von Sperrtypwechsel während einer Transaktion. Besonders erwähnenswert sind Varianten, die Multiple granularity locking verwenden.

1. SS2PL vs. S2PL: Beide bieten Serialisierbarkeit und Strictness. Da S2PL eine Oberklasse von SS2PL ist, kann es im Prinzip mehr Gleichzeitigkeit bieten. In der Praxis ist jedoch in der Regel kein Vorteil in Bezug auf die Gleichzeitigkeit festzustellen (für beide gibt es genau die gleiche Sperrung, wobei die Freigabe der Sperren bei S2PL praktisch nicht viel früher erfolgt), und der Overhead, der durch einen vom Transaktionsende getrennten Mechanismus für das Ende von Phase 1 in S2PL entsteht, ist nicht gerechtfertigt. Außerdem bietet SS2PL eine Commitment-Reihenfolge, S2PL jedoch nicht. Dies erklärt die Bevorzugung von SS2PL gegenüber S2PL.
2. Vor allem vor 1990, aber auch danach, wurde in vielen Artikeln und Büchern, z.B. (Bernstein et al. 1987, S. 59), der Begriff „Strict 2PL“ (S2PL) häufig durch das Sperrprotokoll „Release all locks only after transaction end“ definiert, das das Protokoll von SS2PL ist. Daher konnte „Strict 2PL“ dort nicht der Name der Schnittmenge von Strictness und 2PL sein, die größer ist als die vom SS2PL-Protokoll erzeugte Klasse. Dies hat zu Verwirrung geführt. Mit einer expliziten Definition von S2PL als Schnittmenge von Strictness und 2PL, einem neuen Namen für SS2PL und einer expliziten Unterscheidung zwischen den Klassen S2PL und SS2PL haben die Artikel (Breitbart et al. 1991) und (Raz 1992) versucht, die Verwirrung zu klären: der erste verwendet den Namen „Rigorosität“, der zweite „SS2PL“.“
3. Es gibt eine allgemeinere Eigenschaft als SS2PL (eine Schedule-Superklasse), Strict Commitment Ordering (Strict CO, oder SCO), die ebenfalls sowohl Serialisierbarkeit, Strenge als auch CO bietet und einen ähnlichen Locking Overhead hat. Im Gegensatz zu SS2PL blockiert SCO nicht bei einem Lese-Schreib-Konflikt (eine Lesesperre blockiert nicht den Erwerb einer Schreibsperre; SCO und SS2PL verhalten sich bei Schreib-Lese- und Schreib-Schreib-Konflikten gleich) auf Kosten eines möglichen verzögerten Commits, und bei einem solchen Konflikttyp hat SCO eine kürzere durchschnittliche Transaktionsabschlusszeit und eine bessere Leistung als SS2PL. Während SS2PL die obige Sperrkompatibilitätstabelle befolgt, hat SCO die folgende Tabelle:

Beachten Sie, dass SCO zwar alle Sperren am Ende der Transaktion freigibt und die 2PL-Sperrregeln einhält, SCO ist aufgrund seiner unterschiedlichen Sperrkompatibilitätstabelle keine Untermenge von 2PL. SCO erlaubt materialisierte Lese-Schreib-Konflikte zwischen zwei Transaktionen in deren Phase 1, was 2PL in Phase 1 nicht zulässt (siehe materialisierte Konflikte in Serialisierbarkeit). Andererseits erlaubt 2PL andere materialisierte Konflikttypen in Phase 2, die SCO überhaupt nicht zulässt. Zusammengenommen bedeutet dies, dass die Zeitplanklassen 2PL und SCO nicht vergleichbar sind (d.h. keine Klasse enthält die andere Klasse).

Zusammenfassung – Beziehungen zwischen KlassenBearbeiten

Schedule classes containment: Ein Pfeil von Klasse A zu Klasse B zeigt an, dass Klasse A B strikt einschließt; das Fehlen eines gerichteten Pfades zwischen den Klassen bedeutet, dass die Klassen nicht vergleichbar sind. Eine Eigenschaft ist inhärent blockierend, wenn sie nur durch Blockieren der Datenzugriffsoperationen einer Transaktion durchgesetzt werden kann, bis bestimmte Ereignisse in anderen Transaktionen eintreten. (Raz 1992)

Zwischen zwei beliebigen Zeitplanklassen (definiert durch die jeweiligen Eigenschaften ihrer Zeitpläne), die gemeinsame Zeitpläne haben, enthält entweder eine die andere (enthält streng, wenn sie nicht gleich sind), oder sie sind unvergleichbar. Die Einschlussbeziehungen zwischen den 2PL-Klassen und anderen wichtigen Zeitplanklassen sind im folgenden Diagramm zusammengefasst. 2PL und seine Unterklassen sind von Natur aus blockierend, was bedeutet, dass es keine optimistischen Implementierungen für sie gibt (und wann immer „Optimistic 2PL“ erwähnt wird, bezieht sich dies auf einen anderen Mechanismus mit einer Klasse, die auch Zeitpläne enthält, die nicht in der 2PL-Klasse enthalten sind).