Kapitel 16: Verteilte Datenbanken Flashcards
(34 cards)
Terminologie verteilter Datenbanken
- Sammlung von Informationseinheiten, verteilt auf mehreren Rechnern, verbunden mittels Kommunikationsnetz
- Kooperation zwischen autonom arbeitenden Stationen, zur Durchführung einer globalen Aufgabe
- z.B. über LAN oder WAN
Aufbau und Entwurf eines verteilten Datenbanksystems
Fragmentierung und Allokation einer Relation
- Fragmentierung: Fragmente enthalten Daten mit gleichem Zugriffsverhalten
- Allokation: Fragmente werden den Stationen zugeordnet
- mit Replikation (redundanzfrei)
- ohne Replikation
Arten der Fragmentierung + Korrektheitsanforderung
- horizontale Fragmentierung: Zerlegung der Relation in disjunkteTupelmengen
- vertikale Fragmentierung: Zusammenfassung von Attributen mit gleichem Zugriffsmuster
- kombinierte Fragmentierung: Anwendung horizontaler und vertikaler Fragmentierung auf dieselbe Relation
- Korrektheitsanforderungen:
- Rekonstruierbarkeit
- Vollständigkeit
- Disjunktheit
Erkläre Horizontale Fragmentierung
sinnvolle Gruppierung der Professoren nach Fakultätszugehörigkeit - 3 Zerlegungsprädikate:
- p1 ≡ Fakultät = ‚Theologie‘
- p2 ≡ Fakultät = ‚Physik‘
- p3 ≡ Fakultät = ‚Philosophie‘
TheolProfs ́ := σp1∧¬p2 ∧¬ p3(Professoren) = σp1(Professoren)
PhysikProfs ́ := σ¬p1∧p2 ∧¬ p3(Professoren) = σp2(Professoren)
PhiloProfs ́ := σ¬p1∧¬p2 ∧p3(Professoren) = σp3(Professoren)
AndereProfs ́:= σ¬p1∧¬p2 ∧¬ p3(Professoren)
Beispiel Vorlesungen aus dem Universitätsschema: Zerlegung in Gruppen mit gleicher SWS-Zahl
2SWSVorls := σSWS=2 (Vorlesungen)
3SWSVorls := σSWS=3 (Vorlesungen)
4SWSVorls := σSWS=4 (Vorlesungen)
Behebung Fragmentierungsproblem bei Horizontaler Fragmentierung
Erkäre vertikale Fragmentierung und deren Probleme
Beliebige vertikale Fragmentierung gewährleistet keine Rekonstruierbarkeit 2 mögliche Ansätze, um Rekonstruierbarkeit zu garantieren:
- jedes Fragment enthält den Primärschlüssel der Originalrelation. Aber: Verletzung der Disjunktheit
- jedem Tupel der Originalrelation wird ein eindeutiges Surrogat (= künstlich erzeugter Objektindikator) zugeordnet, welches in jedes vertikale Fragment des Tupels mit aufgenommen wird
für die Universitätsverwaltung sind PersNr, Name, Gehalt und Steuerklasse interessant:
ProfVerw := Π PersNr, Name, Gehalt, Steuerklasse (Professoren)
für Lehre und Forschung sind dagegen PersNr, Name, Rang,
Raum und Fakultät von Bedeutung:
Profs := Π PersNr, Name, Rang, Raum, Fakultät (Professoren)
Rekonstruktion der Originalrelation Professoren: Professoren = ProfVerw JOIN ProfVerw.PersNr = Profs.PersNr Profs
Welche Formen der kombinierten Fragmentierung gibt es?
Kombinierte Fragmentierung
a ) horizontale Fragmentierung nach vertikaler Fragmentierung
b ) vertikale Fragmentierung nach horizontale
Fall a)
R = R1 JOIN p (R21 ∪ R22 ∪ R23)
Fall b)
R = R1 ∪ R2 ∪ (R31 JOIN R31. κ = R32. κ R32)
Erkläre Allokation
- Dasselbe Fragment kann mehreren Stationen zugeordnet werden
- Allokation für unser Beispiel ohne Replikationen ⇒ redundanzfreie Zuordnung
SVerw –> Verwaltungsrechner –> {ProfVerw}
Erkläre Transparenz und deren Arten in verteilten DB
- Grad der Unabhängigkeit den ein VDBMS dem Benutzer beim Zugriff auf verteilte Daten vermittelt
- Verschiedene Stufen der Transparenz:
- Fragmentierungstransparenz
- Beispielanfrage, die Fragmentierungstransparenz voraussetzt:
select Titel, Name
from Vorlesungen, Professoren where gelesenVon = PersNr;
Beispiel für eine Änderungsoperation, die Fragmentierungs- transparenz voraussetzt:
update Professoren
set Fakultät = ‚Theologie‘
where Name = ‚Sokrates‘;
* Ändern des Attributwertes von Fakultät
Transferieren des Sokrates-Tupels aus Fragment PhiloProfs in das Fragment TheolProfs (= Löschen aus PhiloProfs, Einfügen in TheolProfs)
Ändern der abgeleiteten Fragmentierung von Vorlesungen (= Einfügen der von Sokrates gehaltenen Vorlesungen in
TheolVorls, Löschen der von ihm gehaltenen Vorlesungen aus PhiloVorls)
- Allokationstransparenz
- Benutzer müssen Fragmentierung kennen, aber nicht den „Aufenthaltsort“ eines Fragments
Beispielanfrage:
select Gehalt
from ProfVerw
where Name = ‚Sokrates‘;
* unter Umständen muss Originalrelation rekonstruiert werden
Beispiel:
Verwaltung möchte wissen, wieviel die C4-Professoren der Theologie insgesamt verdienen
da Fragmentierungstransparenz fehlt muss die Anfrage folgendermaßen formuliert werden:
select sum (Gehalt) from ProfVerw, TheolProfs where ProfVerw.PersNr = TheolProfs.PersNr and
Rang = ‚C4‘;
- Lokale Schema-Transparenz
- Der Benutzer muss auch noch den Rechner kennen, auf dem ein Fragment liegt.
Beispielanfrage:
select Name
from TheolProfs at STheol where Rang = ‚C3‘;
* Ist überhaupt Transparenz gegeben?
Lokale Schema-Transparenz setzt voraus, dass alle Rechner dasselbe Datenmodell und dieselbe Anfragesprache verwenden.
⇒ vorherige Anfrage kann somit analog auch an Station SPhilo ausgeführt werden
Dies ist nicht möglich bei Kopplung unterschiedlicher DBMS.
Verwendung grundsätzlich verschiedener Datenmodelle auf lokalen DBMS nennt man „Multi-Database-Systems“ (oft unumgänglich in „realer“ Welt).
Anfragebearbeitung bei horizontaler Fragmentierung
Übersetzung einer SQL-Anfrage auf dem globalen Schema in eine äquivalente Anfrage auf den Fragmenten benötigt 2 Schritte:
- Rekonstruktion aller in der Anfrage vorkommenden globalen Relationen aus den Fragmenten, in die sie während der Fragmentierungsphase zerlegt wurden. Hierfür erhält man einen algebraischen Ausdruck.
- Kombination des Rekonstruktionsausdrucks mit dem algebraischen Anfrageausdruck, der sich aus der Übersetzung der SQL-Anfrage ergibt
Wie könnte eine Optimierung der horizontalen Fragmentierung aussehen?
Anfrageoptimierung bei vertikaler Fragmentierung:
Beispiel:
select Name, Gehalt from Professoren where Gehalt > 80000;
Rolle von JOIN Auswertung bei VDBMS und Möglichkeiten?
- spielt kritischere Rolle als in zentralisierten Datenbanken Problem: Argumente eines Joins zweier Relationen können auf
- unterschiedlichen Stationen des VDBMS liegen
- Betrachtung des allgemeinsten Falles:
- äußere Argumentrelation R ist auf Station StR gespeichert
innere Argumentrelation S ist dem Knoten StS zugeordnet
Ergebnis der Joinberechnung wird auf einem dritten Knoten StResult benötigt
* Mit Filter z.B. Bloom Filter und Hash-Filter
* Ohne Filterung:
* Nested-Loops
* Transfer einer Argumentrelation
* Transfer beider Argumentrelationen
Wie sieht Transaktionskontrolle in VDBMS aus?
- Transaktionen können sich bei VDBMS über mehrere Rechnerknoten erstrecken
- ⇒ Recovery:
- Redo: Wenn eine Station nach einem Fehler wieder anläuft, müssen alle Änderungen einmal abgeschlossener Transaktionen - seien sie lokal auf dieser Station oder global über mehrere Stationen ausgeführt worden - auf den an dieser Station abgelegten Daten wiederhergestellt werden.
- Undo: Die Änderungen noch nicht abgeschlossener lokaler und globaler Transaktionen müssen auf den an der abgestürzten Station vorliegenden Daten rückgängig gemacht werden.
Warum ist die EOT-Behandlung ein Problem?
Die EOT (End-of-Transaction)-Behandlung von globalen Transaktionen stellt in VDBMS ein Problem dar.
Eine globale Transaktion muss atomar beendet werden, d.h. entweder
Ø commit: globaleTransaktionwirdanallen
(relevanten) lokalen Stationen festgeschrieben
oder
Ø abort: globale Transaktion wird gar nicht festgeschrieben
⇒ Problem in verteilter Umgebung, da die Stationen eines VDBMS unabhängig voneinander „abstürzen“ können
Wie kann das EOT-Problem gelöst werden?
2 Phaen Commit Protokoll:
→ gewährleistet die Atomarität der EOT-Behandlung
- das 2PC-Verfahren wird von sog. Koordinator K
- überwacht
- gewährleistet, dass die n Agenten (=Stationen im VDBMS) A1,…An, die an einer Transaktion beteiligt waren, entweder alle von Transaktion T geänderten Daten festschreiben oder alle Änderungen von T rückgängig machen
Wie sieht der Ablauf der EOT-Behandlung beim beim 2PC Protokoll aus?
- K schickt allen Agenten eine PREPARE-Nachricht, um herauszufinden, ob sie Transaktionen festschreiben können
- jeder Agent Ai empfängt PREPARE-Nachricht und schickt eine von zwei möglichen Nachrichten an K:
- READY, falls Ai in der Lage ist, die Transaktion T lokal festzuschreiben
- FAILED, falls Ai kein commit durchführen kann (wegen Fehler, Inkonsistenz etc.)
- hat K von allen n Agenten A1,…,An ein READY erhalten, kann K ein COMMIT an alle Agenten schicken mit der Aufforderung, die Änderungen von T lokal festzuschreiben; antwortet einer der Agenten mit FAILED od. gar nicht innerhalb einer bestimmten Zeit (timeout), schickt K ein ABORT an alle Agenten und diese machen die Änderungen der Transaktion rückgängig
- haben die Agenten ihre lokale EOT-Behandlung abgeschlossen, schicken sie eine ACK-Nachricht (=acknowledgement, dt. Bestätigung) an den Koordinator
Zustandsübergang beim 2PC-Protokoll für Koordinator:
Zustandsübergang beim 2PC-Protokoll für Agenten:
Fehlersituationen des 2PC-Protokolls + Beschreibung
Absturz Koordinator:
- Absturz vor dem Senden einer COMMIT-Nachricht → Rückgängigmachen der Transaktion durch Versenden einer ABORT-Nachricht
- Absturz nachdem Agenten ein READY mitgeteilt haben → Blockierung der Agenten
⇒ Hauptproblem des 2PC-Protokolls beim Absturz des Koordinators, da dadurch die Verfügbarkeit des Agenten bezüglich andere globaler und lokaler Transaktionen drastisch eingeschränkt ist
Absturz des Agenten:
- antwortet ein Agent innerhalb eines Timeout-Intervalls nicht auf die PREPARE-Nachricht, gilt der Agent als abgestürzt; der Koordinator bricht die Transaktion ab und schickt eine ABORT-Nachricht an alle Agenten
- „abgestürzter“ Agent schaut beim Wiederanlauf in seine Log-Datei:
- kein ready-Eintrag bzgl. Transaktion T → Agent führt ein abort durch und teilt dies dem Koordinator mit (FAILED- Nachricht)
- ready-Eintrag aber kein commit-Eintrag → Agent fragt Koordinator, was aus Transaktion T geworden ist; Koordinator teilt COMMIT oder ABORT mit, was beim Agenten zu einem Redo oder Undo der Transaktion führt
- commit-Eintrag vorhanden → Agent weiß ohne Nach- fragen, dass ein (lokales) Redo der Transaktion nötig ist
Verlorengegangene Nachrichten:
- PREPARE-Nachricht des Koordinators an einen Agenten geht verloren oder
- READY-(oder FAILED-)Nachricht eines Agenten geht verloren
→ nach Timeout-Intervall geht Koordinator davon aus, dass betreffender Agent nicht funktionsfähig ist und sendet ABORT-Nachricht an alle Agenten (Transaktion gescheitert)
- Agent erhält im Zustand Bereit keine Nachricht vom Koordinator → Agent ist blockiert, bis COMMIT- oder ABORT-Nachricht vom Koordinator kommt, da Agent nicht selbst entscheiden kann (deshalb schickt Agent eine „Erinnerung“ an den Koordinator)
Mehrbenutzersynchronisation in VDBMS
- Serialisierbarkeit
- Zwei-Phasen-Sperrprotokoll in VDBMS
- lokale Sperrverwaltung an jeder Station
- globale Sperrverwaltun
- Serialisierbarkeit:
- Lokale Serialisierbarkeit an jeder der an den Transaktionen beteiligten Stationen reicht nicht aus.
Deshalb muß man bei der Mehrbenutzersynchronisatin auf globaler Serialisierbarkeit bestehen
- Lokale Sperrverwaltung:
- globale Transaktion muß vor Zugriff/Modifikation eines Datums A, das auf Station S liegt, eine Sperre vom Sperrverwalter der Station S erwerben
- Verträglichkeit der angeforderten Sperre mit bereits existierenden Sperren kann lokal entschieden werden → favorisiert lokale Transaktionen, da diese nur mit ihrem lokalen Sperrverwalter kommunizieren müssen
- Globale Sperrverwaltung:
- alle Transaktionen fordern alle Sperren an einer einzigen, ausgezeichneten Station an.
- Nachteile:
- zentraler Sperrverwalter kann zum Engpass des VDBMS werden, besonders bei einem Absturz der Sperrverwalter- Station („rien ne vas plus“)
- Verletzung der lokalen Autonomie der Stationen, da auch lokale Transaktionen ihre Sperren bei der zentralisierten Sperrverwaltung anfordern müssen zentrale Sperrverwaltung i.a. nicht akzeptabel
- Deadlocks:
- Erkennung von Deadlocks (Verklemmungen) • zentralisierte Deadlock-Erkennung
- dezentrale (verteilte) Deadlock-Erkennung
- Vermeidung von Deadlocks
- Timeout:
- betreffende Transaktion wird zurückgesetzt und erneut gestartet → einfach zu realisieren
- Problem: richtige Wahl des Timeout-Intervalls:
- zu lang → schlechte Ausnutzung der Systemressourcen
- zu kurz → Deadlock-Erkennung, wo gar keine Verklemmung vorliegt
Wie können Deadlocks in VDBMS erkannt werden?
Zentralisierte Erkennung:
- Stationen melden lokal vorliegende Wartebeziehungen an neutralen Knoten, der daraus globalen Wartegraphen aufbaut (Zyklus im Graphen → Deadlock)
→ sichere Lösung - Nachteile:
- hoher Aufwand (viele Nachrichten)
- Entstehung von Phantom-Deadlocks (=nicht- existierende Deadlocks) durch „Überholen“ von Nachrichten im Kommunikationssystem
Dezentrale Erkennung:
- lokale Wartegraphen an den einzelnen Stationen → Erkennen von lokalen Deadlocks
- Erkennung globaler Deadlocks:
- jeder lokale Wartegraph hat einen Knoten External, der stationenübergreifenden Wartebeziehungen zu externen Subtransaktionen modelliert
- Zuordnung jeder Transition zu einem Heimatknoten, von wo aus externe Subtransaktionen auf anderen Stationen initiiert werden
Deadlockvermeidung in VDBMS
Vermeidung:
- optimistische Mehrbenutzersynchronisation:
nach Abschluss der Transaktionsbearbeitung wird Validierung durchgeführt - Zeitstempel-basierende Synchronisation:
Zuordnung eines Lese-/Schreib-Stempels zu jedem Datum
→ entscheidet, ob beabsichtigte Operation durchgeführt werden kann ohne Serialisierbarkeit zu verletzen oder ob Transaktion abgebrochen wird (abort)
Sperrbasierte Synchronisation:
- wound/wait:
nur jüngere Transaktionen warten auf ältere;
fordert ältere Transaktion Sperre an, die mit der von der jüngeren Transaktion gehaltenen nicht verträglich ist, wird jüngere Transaktion abgebrochen
- wait/die:
nur ältere Transaktionen warten auf jüngere;
fordert jüngere Transaktion Sperre an, die mit der von der älteren Transaktion gehaltenen nicht kompatibel ist, wird jüngere Transaktion abgebrochen
