Scheduler (Datenbank) - LinkFang.de





Scheduler (Datenbank)


Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Ein (Datenbank-)Scheduler dient der Verwaltung von Schreib- und Lesezugriffen (sog. Operationen) auf Datenbankobjekten. Er sorgt dafür, dass keine Konflikte während der parallelen Ausführung nebenläufiger Transaktionen auftreten. Transaktionen werden nach Möglichkeit parallel ausgeführt, um die Systemressourcen optimal ausnutzen zu können bzw. sie in kürzerer Zeit abzuschließen als wenn man sie nacheinander (seriell) ausführt. Dies kommt besonders bei Mehrbenutzerdatenbanken zum Tragen, da in solchen System viele Datenbankzugriffe in sehr kurzer Zeit stattfinden können beispielsweise im zentralen Server einer Bank, der die Konten aller Filialen verwaltet.

Mit anderen Worten, der Scheduler ist die Komponente eines DBMS, welche die Ablaufreihenfolge (auch Schedule oder Historie genannt) der Datenzugriffe auf der Datenbank (Datenbankoperation) so konstruiert, dass sie einem bestimmten Protokoll gehorchen. Außerdem übernimmt ein Scheduler die Ablaufkontrolle. Dabei hat er die Möglichkeit eine Operation sofort auszuführen (d.h. an den Datenverwalter weitergeben), sie zu verzögern (meist realisiert über eine Warteschlange) um den Operationen andere Transaktionen den Vorzug zu geben oder sie zurückzuweisen (durch Abbruch / abort der zugehörigen Transaktion).

Ein Scheduler muss folgende Eigenschaften eines Schedules sicherstellen:

Serialisierbarkeit

In einem seriellen Schedule werden die enthaltenen Transaktionen strikt nacheinander ausgeführt. Ein serieller Schedule ist damit immer korrekt, weil keine Überschneidungen der Transaktionen auftreten können. Allerdings ist ein serieller Schedule auch verhältnismäßig ineffizient, weil eine Transaktion immer die Beendigung der anderen Transaktion abwarten muss und damit keine Parallelisierung ausgenutzt werden kann.

Ein Schedule wird als serialisierbar bezeichnet, wenn er äquivalent zu einem seriellen Schedule ist. Es gibt dabei folgende Äquivalenzklassen:

Schedules sind final-state-äquivalent, wenn ihre Operationen ausgehend von einem gleichen Anfangszustand den gleichen Endzustand erzeugen. Dabei wird die globale Konsistenz nach Ausführung aller beteiligter Transaktionen betrachtet.
FSR (final state serializability) ist die Klasse aller final-state-serialisierbaren Historien.
Schedules sind sichten-äquivalent, wenn alle Transaktionen den gleichen Datenbank-Zustand 'sehen', d.h. wenn gilt: Transaktionen lesen gleiche Werte [math]\Rightarrow[/math] sie produzieren das gleiche Ergebnis. Es wird also sowohl die globale Konsistenz nach Ausführung aller beteiligten Transaktionen als auch die lokale Konsistenz nach Ausführung jeder einzelnen Transaktion betrachtet.
VSR (view serializability) ist die Klasse aller sichten-serialisierbaren Historien.
Schedules sind konflikt-äquivalent, wenn unverträgliche Operationen in der gleichen Reihenfolge angeordnet sind.
CSR (conflict serializability) ist die Klasse aller konflikt-serialisierbaren Historien.
CMFSR (commit final state serializability) ist die Klasse aller commit-final-state-serialisierbaren Historien.

CMVSR (commit view serializability) ist die Klasse aller commit-view-serialisierbaren Historien.


CMCSR (commit conflict serializability) ist die Klasse aller commit-conflict-serialisierbaren Historien.

Fehlersicherheit

Fehlersicherheit eines Schedules ist die Eigenschaft, dass dieser Schedule sich bei Abbruch einer oder mehreren Transaktionen genauso verhält wie ein ähnlicher Schedule, der ausschließlich die nicht abgebrochenen Transaktionen enthält.

Es gibt folgende Klassen von Schedules bzgl. der Fehlersicherheit:

  • RC - recoverable. Es ist möglich nach einer abgebrochenen Transaktion die Verarbeitung der restlichen Schedules weiterzuführen ohne Inkonsistenzen zu erhalten.
  • ACA - avoids cascading abort. Geschachtelte Abbrüche werden vermieden indem Transaktionen nur von abgeschlossenen Transaktionen lesen dürfen.
  • ST - strict schedules.
  • RG - rigorous schedules.

Klassifikation und Protokolle

Scheduler können in folgende Klassen eingeteilt werden:

  • Pessimistische / konservative Scheduler. Diese Scheduler versuchen Konflikte zwischen Operationen nebenläufiger Transaktionen während ihrer Ausführung zu erkennen bzw. zu beheben. Sie bevorzugen die Verzögerung von Operationen bei Konflikten.
    • Sperrende Scheduler (Locking Scheduler) - Die o.g. Kriterien werden durch Locks (Sperren) erreicht.
      • 2PL - Two-Phase-Locking. Jede Transaktion teilt sich in zwei Phasen. In der ersten dürfen Locks nur angefordert werden und in der zweiten Phase dürfen diese nur freigegeben werden. Es ist also einer Transaktion nicht erlaubt nach der Freigabe eines Datenelements einen neuen Lock darauf anzufordern. Die ausgegebenen Schedules sind CSR.
        • C2PL - conservative 2PL. Hier werden grundsätzlich beim Start jeder Transaktion alle Locks angefordert.
        • S2PL - strict 2PL. Sämtliche angeforderten Write Locks werden erst beim Abschluss der Transaktion freigegeben. Es kann bewiesen werden, dass solche Schedules zusätzlich zu CSR auch ST sind.
        • SS2PL - strong 2PL. Alle Locks werden erst beim Abschluss der Transaktion freigegeben. Es kann bewiesen werden, dass solche Schedules der Klasse RG entsprechen.
      • Baum-Sperrprotokolle. Wie 2PL, nur speziell für Bäume unter Ausnutzung deren besonderer Eigenarten.
        • WTL - write only tree locking
        • RWTL - read write tree locking
        • MGL - multiple granularity locking. Die Datenbankobjekte werden in einem Baum hierarchisch organisiert. An oberster Stelle steht z.B. die Datenbank, darunter Tabellen und weiter unten Tupel. Um an unterer Stelle ein Lock zu erhalten muss an den darüber liegenden Knoten mindestens ein ebensolches Lock bereits existieren. Beim Freigeben ist dies genau umgekehrt. MGL-produzierte Schedules sind CSR.
    • Nicht-sperrende Scheduler (non-locking)
      • TO - Zeitstempel-Verfahren (time ordering). Um Synchronisationsprobleme zu vermeiden, werden Zeitstempel für jede Transaktion vergeben sobald ihre jeweils erste Operation beim Scheduler eingeht. Zwei Strategien sind zu unterscheiden: wait-die und wound-wait
        • BTO - Basis-TO. Einfache und aggressive Implementierung von TO. Operationen werden hier direkt an den Datenverwalter weitergeleitet und Transaktionen zu spät kommender Operationen abgebrochen.
      • SGT - Serialisierungsgraph-Tester
      • Generische Prüfung
  • Optimistische / aggressive Scheduler. Diese Scheduler verschieben die Konfliktprüfung durch einen sog. Certifier auf den Commit-Zeitpunkt einer Transaktion. Sie führen eine Transaktion in drei Phasen aus: Read Phase (Operationen werden ausgeführt, Schreibzugriffe erfolgen ausschließlich im transienten lokalen Arbeitsbereich), Validation Phase (beim Commit wird die Transaktion durch Certifier validiert), Write Phase (Inhalt des transienten lokalen Arbeitsbereiches wird in die persistente Datenbasis übertragen). Validation Phase und Write Phase sind ununterbrechbar, werden also immer ohne Unterbrechung ausgeführt.
  • Hybride Scheduler. Sie verteilen die Konfliktprüfung auf mehrere Komponenten, die unterschiedliche Protokolle verwenden können.
    • Unterscheidung nach Konfliktart (read-write- / write-write-Konflikt)
    • Unterteilung der Datenelemente in disjunkte Teilmengen
    • Unterteilung der Datenelemente nach ihrem Zugriffsmuster

Darüber hinaus gibt es noch Mehrversionen-Scheduler, welche zu jedem geschriebenen Datenelement mehrere Versionen speichern können, um Inconsistent Reads zu vermeiden. Ein Mehrversionen-Scheduler muss zusätzlich zum und abhängig vom umgesetzten Protokoll einer Lese-Operationen eine bestimmte Version des gelesenen Datenelementes zuweisen. Eine Schreib-Operation erzeugt normalerweise eine neue Version des jeweiligen Datenelements. Mehrversionen-Protokolle sind MVTO, MV2PL, MVSGT, ROMV (read only mulitiversion protocol).


Kategorien: Datenbanktheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Scheduler (Datenbank) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.