Nebenläufigkeitskontrollprotokolle

Nebenläufigkeitskontrollprotokolle sind die Methoden – Sperren, Zeitstempelreihenfolge, optimistische Validierung und Multiversionierung –, die nebenläufige Transaktionen so planen, dass das Ergebnis einer seriellen Ausführung entspricht.

Definition

Ein Nebenläufigkeitskontrollprotokoll ist ein Regelsatz, der festlegt, wie nebenläufige Transaktionen auf Daten zugreifen, sodass jeder zulässige Zeitplan serialisierbar ist (oder ein gewähltes schwächeres Isolationsniveau erfüllt), wodurch die Isolation erhalten bleibt, ohne Transaktionen zu zwingen, einzeln ausgeführt zu werden.

Scope

Dieses Thema behandelt die Protokolle, die die Serialisierbarkeit unter Nebenläufigkeit erzwingen: Zwei-Phasen-Sperren und ihre strikte Variante, mit Deadlock-Erkennung und -Vermeidung; Zeitstempel-Ordnungsprotokolle; optimistische Nebenläufigkeitskontrolle mit Lese-Validierungs-Schreib-Phasen; und Multiversions-Nebenläufigkeitskontrolle, einschließlich Snapshot Isolation. Es wird behandelt, wie jedes Protokoll korrekte Zeitpläne garantiert und welche Kompromisse zwischen Blockierung, Abbrüchen und Durchsatz bestehen. Die Definition der Serialisierbarkeit selbst und die Wiederherstellungsmechanismen, die die Nebenläufigkeitskontrolle ergänzen, sind ausgeschlossen.

Core questions

• Wie garantieren Zwei-Phasen-Sperren serialisierbare Zeitpläne?
• Wie werden Deadlocks erkannt, verhindert oder gelöst?
• Wie unterscheiden sich Zeitstempel-Ordnungs- und optimistische Protokolle von Sperren?
• Wie ermöglicht die Multiversions-Nebenläufigkeitskontrolle Lesern, das Blockieren von Schreibvorgängen zu vermeiden?
• Welche Durchsatz-Kompromisse gibt es zwischen pessimistischen und optimistischen Methoden?

Key concepts

• Zwei-Phasen-Sperren
• strikte und rigorose 2PL
• gemeinsame und exklusive Sperren
• Deadlock-Erkennung und -Vermeidung
• Zeitstempel-Ordnung
• optimistische Nebenläufigkeitskontrolle
• Multiversions-Nebenläufigkeitskontrolle
• Snapshot Isolation

Key theories

Zwei-Phasen-Sperren

Wenn jede Transaktion alle ihre Sperren erwirbt, bevor sie eine freigibt (eine Wachstumsphase, gefolgt von einer Schrumpfphase), sind alle resultierenden Zeitpläne konfliktserialisierbar; strikte Zwei-Phasen-Sperren halten Schreibsperren zusätzlich bis zum Commit, um die Wiederherstellbarkeit zu gewährleisten.

Optimistische Nebenläufigkeitskontrolle

Transaktionen werden ohne Sperren ausgeführt und zum Commit-Zeitpunkt gegen nebenläufige Transaktionen validiert; widersprüchliche Transaktionen werden abgebrochen und wiederholt, was bei geringer Konfliktdichte gut funktioniert.

Multiversions-Nebenläufigkeitskontrolle

Durch das Beibehalten mehrerer Versionen jedes Datenelements ermöglicht das System Lesevorgängen den Zugriff auf einen konsistenten Snapshot, ohne Schreibvorgänge zu blockieren; Snapshot Isolation ist ein weit verbreitetes Multiversionsschema, obwohl es bestimmte nicht-serialisierbare Anomalien zulassen kann.

Clinical relevance

Nebenläufigkeitskontrollprotokolle bestimmen, wie sich eine Datenbank unter Last verhält: Sperren sind robust, können aber Deadlocks und Konflikte verursachen; optimistische und Multiversionsmethoden ermöglichen eine hohe Lesekonkurrenz; und die Wahl des Protokolls beeinflusst direkt den Durchsatz und die Latenz von transaktionsintensiven Systemen.

History

Zwei-Phasen-Sperren und Prädikatssperren wurden 1976 von Eswaran und Kollegen bei System R formalisiert; Kung und Robinson führten 1981 die optimistische Nebenläufigkeitskontrolle ein; und die Monographie von Bernstein, Hadzilacos und Goodman aus dem Jahr 1987 vereinte die Theorie. Multiversionsmethoden und Snapshot Isolation wurden später in weit verbreiteten Datenbanksystemen aufgrund ihres lesefreundlichen Verhaltens dominant.

Debates

Snapshot Isolation versus Serialisierbarkeit

Snapshot Isolation bietet eine hohe Nebenläufigkeit, indem sie Lesern einen konsistenten Snapshot ermöglicht, aber sie erlaubt Anomalien wie Write Skew, die eine vollständige Serialisierbarkeit verbietet; Praktiker diskutieren, wann ihre schwächere Garantie akzeptabel ist und wann serialisierbare Varianten erforderlich sind.

Key figures

• Jim Gray
• Philip Bernstein
• H. T. Kung

Seminal works

• eswaran1976
• kung1981
• bernstein1987

Frequently asked questions

Was verursacht einen Deadlock und wie wird er behandelt?

Ein Deadlock tritt auf, wenn zwei oder mehr Transaktionen jeweils eine Sperre halten, die die andere benötigt, sodass keine fortfahren kann. Systeme behandeln dies entweder durch Erkennung – Erstellen eines Warte-auf-Graphen, Finden eines Zyklus und Abbrechen einer Opfertransaktion – oder durch Präventionsschemata, die die Sperrakquisition ordnen oder Zeitstempel verwenden, um zu entscheiden, welche Transaktion wartet oder abbricht.

Wann ist optimistische Nebenläufigkeitskontrolle eine gute Wahl?

Optimistische Methoden glänzen, wenn Konflikte selten sind, da Transaktionen ohne Sperr-Overhead ausgeführt werden und nur gelegentlich die Validierung fehlschlägt und wiederholt werden muss. Bei hoher Konfliktdichte verschwenden sie Arbeit durch Abbrüche und Wiederholungen, daher werden für schreibintensive, konfliktträchtige Workloads in der Regel pessimistische Sperren oder Multiversionsmethoden bevorzugt.