Upload
anselma-striegel
View
108
Download
0
Embed Size (px)
Citation preview
Verteilte Datenbanken
Geographisch verteilte Organisationsform einer Bank mit ihren Filialen
Filialen sollen Daten lokaler Kunden lokal bearbeiten können
Zentrale soll Zugriff auf alle Daten haben (z.B. für
Kontostandsüberprüfung bei Kreditvergabe)
Szenario:
2
Terminologie
Sammlung von Informationseinheiten (Knoten, Stationen), verteilt auf mehreren Rechnern, verbunden mittels Kommunikationsnetz nach Ceri & Pelagatti (1984)
Kooperation zwischen autonom arbeitenden Stationen, zur Durchführung einer globalen Aufgabe
3
Kommunikationsmedien LAN: local area network, z.B. Ethernet, Token-Ring oder FDDI-Netz
WAN: wide area network, z.B. das Internet
Point-to-Point: z.B. Verbindungen über ISDN oder analoge Modem-Verbindungen
Hier: Kommunikationsmedium für verteiltes DBMS transparent. Jede Station kann mit jeder kommunizieren. Dabei werden u.U. signifikant unterschiedliche Kosten (Zeiten) beobachtet.
4
Verteiltes Datenbanksystem
Kommunikations-netz
Station S1
Station S2 Station S3
5
Client-Server-Architektur VDBMS
Kommunikations-netz
Client C1
Client C2 Server
6
Aufbau und Entwurf eines verteilten Datenbanksystems
globales Schema
Fragmentierungs-schema
Zuordnungsschema
lokalesSchema
lokalesSchema
lokalesDBMS
lokalesDBMS
lokaleDB
lokaleDB
Station S1 Station Sn
...
...
...
...
Ausganspunkt
Zerlegung von Rel.sin (disjunkte) Fragmente Allokation von Rel.sAllokation von Rel.s
zu Stationenzu Stationen
7
Fragmentierung und Allokation einer Relation
Fragmentierung von Relationen: Fragmente enthalten Daten mit gleichem Zugriffsverhalten, um Kommunikationskosten zu minimieren ( Informationen über den zu erwartenden Workload sind notwendig)
Allokation: Fragmente werden den VDBMS-Stationen zugeordnet:
Redundanzfreie Allokation: jedes Fragment ist genau einer Station zugeordnet
Mit Replikation: Ein Fragment wird redundant auf mehreren Stationen verwaltet (N:M-Zuordnung, s. nächste Folie).
8
R2
R3
R1
R3R3
R2R1
R3R2
R1R1
R1R2
R
FragmentierungAllokation
(Zuordnung)
Station S1
Station S3
Station S2
9
Fragmentierung
Horizontale Fragmentierung: Zerlegung der Relation in disjunkte Tupelmengen
Vertikale Fragmentierung: Zusammenfassung von Attributen mit gleichem Zugriffsmuster
Extreme vertikale Fragmentierung: alle Relationen binär (zweispaltig) Vorlesung im WS 06/07
Kombinierte Fragmentierung: Anwendung horizontaler und vertikaler Fragmentierung auf dieselbe Relation
10
Anforderungen an das Fragmentierungsschema
RekonstruierbarkeitJede fragmentierte Relation läßt sich ohne Informationsverlust aus den Fragmenten wiederherstellen.
Vollständigkeit Jedes Datum (Tupel, Attribut) ist einem Fragment zugeordnet.(Voraussetzung für Rekonstruierbarkeit.)
Disjunktheit
Ein Datum ist nicht mehreren Fragmenten zugeordnet.
11
Beispielrelation "Professoren"
Professoren
PersNr Name Rang Raum Fakultät Gehalt Steuerklasse
2125 Sokrates C4 226 Philosophie 85000 1
2126 Russel C4 232 Philosophie 80000 3
2127 Kopernikus C3 310 Physik 65000 5
2133 Popper C3 52 Philosophie 68000 1
2134 Augustinus C3 309 Theologie 55000 5
2136 Curie C4 36 Physik 95000 3
2137 Kant C4 7 Philosophie 98000 1
12
Horizontale Fragmentierung
Abstrakte Darstellung:
Für zwei Prädikate p1 und p2 ergeben sich 4 Fragmente:
n Zerlegungsprädikate p1,...,pn ergeben 2n Fragmente
R
R1
R2
R3
R1 := p1 p2(R)
R2 := p1 p2(R)
R3 := p1 p2 (R)
R4 := p1 p2 (R)
13
Sinnvolle Gruppierung der Professoren nach Fakultät:
3 Zerlegungsprädikate:
p1 (Fakultät = 'Theologie')
p2 (Fakultät = 'Physik')
p3 (Fakultät = 'Philosophie')
TheolProfs´ := σp1p2 p3(Professoren) =
σp1(Professoren)
PhysikProfs´ := σp1p2 p3(Professoren) =
σp2(Professoren)
PhiloProfs´ := σp1p2 p3(Professoren) =
σp3(Professoren)
AndereProfs´ := σp1p2 p3(Professoren) =
14
Abgeleitete horizontale Fragmentierung
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)
Für Anfragebearbeitung u.U. schlechte Zerlegung
Die Fragmentierung verschiedener Relationen ist nicht beliebig und hat Einfluß auf die Anfragebearbeitung.
15
SELECT Titel, NameFROM Vorlesungen, ProfessorenWHERE gelesenVon = PersNr;
resultiert in:
Titel, Name( (TheolProfs´ 2SWSVorls)
(TheolProfs´ 3SWSVorls) … (PhiloProfs´ 4SWSVorls) )
Join-Graph zu dieser Anfrage:
TheolProfs´
PhysikProfs´
PhiloProfs´
2SWSVorls
3SWSVorls
4SWSVorls
16
Einschub: Join-Arten• natürlicher Join
LA B C
a1 b1 c1
a2 b2 c2
RC D E
c1 d1 e1
c3 d2 e2
=
ResultatA B C D E
a1 b1 c1 d1 e1
17
Einschub: Join-Arten (Semi-Joins)
LA B C
a1 b1 c1
a2 b2 c2
RC D E
c1 d1 e1
c3 d2 e2
ResultatC D E
c1 d1 e1
=
• Semi-Join von R mit L (Right Semi-Join)
LA B C
a1 b1 c1
a2 b2 c2
RC D E
c1 d1 e1
c3 d2 e2
=
• Semi-Join von L mit R (Left Semi-Join)
ResultatA B C
a1 b1 c1
18
Lösung: abgeleitete Fragmentierung
TheolProfs´
PhysikProfs´
PhiloProfs´
TheolVorls
PhysikVorls
PhiloVorls
TheolVorls := Vorlesungen gelesenVon=PersNr TheolProfs ´
PhysikVorls := Vorlesungen gelesenVon=PersNr PhysikProfs ´
PhiloVorls := Vorlesungen gelesenVon=PersNr PhiloProfs ´
Titel, Name( (TheolProfs´ p
TheolVorls)
(PhysikProfs´ p
PhysikVorls)
(PhiloProfs´ p PhiloVorls) )
mit p (PersNr = gelesenVon)
19
Vertikale Fragmentierung
Abstrakte: Vertikale Fragmentierung einer Relation R mit Primärschlüssel :
R1 R2
R
κ
20
Vertikale Fragmentierung
Jedes Fragment enthält den Primärschlüssel der Originalrelation. Aber: Verletzung der Disjunktheit.
Jedem Tupel der Originalrelation wird ein eindeutiges SurrogatSurrogat (= künstlich erzeugter Tupelidentifikator) zugeordnet, welches in jedes vertikale Fragment des Tupels mit aufgenommen wird.
Beliebige vertikale Fragmentierung gewährleistet keine Rekonstruierbarkeit.Mögliche Ansätze, um Rekonstruierbarkeit zu garantieren:
21
Vertikale Fragmentierung (Beispiel)
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 ProfVerw.PersNr = Profs.PersNr Profs
22
Kombinierte Fragmentierunga)) Horizontale Fragmentierung nach vertikaler Fragmentierung:
b)) Vertikale Fragmentierung nach horizontaler Fragmentierung:
R1 R2
R21
R
R22
R23
RR1
R2
R3
R32R31
23
Rekonstruktion nach kombinierter Fragmentierung
Fall a)a)
R = R1 R1. = R2.
(R21 R22
R23)
Fall b)b)
R = R1 R2 (R31 R31. = R32.
R32)
24
Baumdarstellung der Fragmentierungen (Beispiel)
v
hh
Profs ProfVerw
PhysikProfsTheolProfsPhiloProfs
Vorlesungen
PhysikVorlsTheolVorlsPhiloVorls
Professoren
abgeleitete Fragmentierung
25
Allokation (Beispiel)
Ein Fragment kann prinzipiell mehreren Stationen zugeordnet werden (Replikation).
Allokation für unser Beispiel jedoch ohne Replikation redundanzfreie Zuordnung.
StationSVerw
SPhysik
SPhilo
STheol
Bemerkung
VerwaltungsrechnerDekanat Physik
Dekanat PhilosophieDekanat Theologie
zugeordnete Fragmente
{ProfVerw}{PhysikVorls, PhysikProfs}{PhiloVorls, PhiloProfs}{TheolVorls, TheolProfs}
26
Transparenz in verteilten Datenbanken
Transparenz:Grad der Unabhängigkeit den ein VDBMS dem Benutzer/Client-Programmen beim Zugriff auf verteilte Daten vermittelt.
Transparenzgrade (abnehmende Transparenz): Fragmentierungstransparenz
Alle Aspekte der Verteilung verborgen, Nutzer arbeiten mit globalem Schema Allokationstransparenz Fragmentierung der Relationen sichtbar, Verteilung auf Stationen verborgen Lokale Schema-Transparenz Operationen adressieren Fragmente und Stationen explizit
27
FragmentierungstransparenzBeispiel (Fragmente/Stationen nicht explizit adressiert):
SELECT Titel, NameFROM Vorlesungen, ProfessorenWHERE gelesenVon = PersNr;
Beispiel für eine Änderungsoperation:
UPDATE ProfessorenSET Fakultät = "Theologie"WHERE Name = "Sokrates";
Welche Operation(en) muß das VDBMS intern ausführen, umdie UPDATE-Anweisung zu realisieren?
28
Fragmentierungstransparenz (cont.)
1. Im betroffenen Fragment: Ändern des Attributwertes von Fakultät.
2. Transferieren des Sokrates-Tupels aus Fragment PhiloProfs in das Fragment TheolProfs (= Löschen aus PhiloProfs, Einfügen in TheolProfs).
3. Ändern der abgeleiteten Fragmentierung von Vorlesungen (= Einfügen der von Sokrates gehaltenen Vorlesungen in TheolVorls, Löschen der von ihm gehaltenen Vorlesungen aus PhiloVorls).
29
Allokationstransparenz
Benutzer müssen Fragmentierung kennen, aber nicht dieStation(en) eines Fragmentes:
Beispiel:
SELECT GehaltFROM ProfVerwWHERE Name = "Sokrates";
Fragmentname!
30
Allokationstransparenz (cont.)Unter Umständen müssen Originalrelationen erst rekonstruiert werden.
Beispiel:Verwaltung möchte wissen, wieviel die C4-Professoren der Theologie insgesamt verdienen?
Da Fragmentierungstransparenz fehlt, muß die Anfrage folgendermaßen formuliert werden:
SELECT SUM (Gehalt)FROM ProfVerw, TheolProfsWHERE ProfVerw.PersNr = TheolProfs.PersNr AND Rang = "C4";
31
Lokale Schema-Transparenz
Der Benutzer muss jetzt auch noch die Station kennen, auf der ein Fragment liegt.
Beispiel:
SELECT NameFROM TheolProfs AT STheol
WHERE Rang = "C3";
32
Lokale Schema-Transparenz (cont.)
Ist hier überhaupt noch 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-SystemsMulti-Database-Systems. Oft unumgänglich in realen (unternehmensweiten) Applikationen.
33
Anfrageübersetzung und Anfrageoptimierung
Annahme: Es liegt Fragmentierungstransparenz vor
Anfragen werden gegen das globale Schema/die globalen Relationen formuliert
Aufgabe des Anfrageübersetzers: Generierung eines Anfrageauswertungsplans auf den Fragmenten
Aufgabe des Anfrageoptimierers: Generierung eines möglichst effizienten Auswertungsplanes
abhängig von der Allokation der Fragmente auf den verschiedenen Stationen des Rechnernetzes
34
Anfragebearbeitung bei horizontaler Fragmentierung
Übersetzung einer SQL-Anfrage auf dem globalen Schema in eine äquivalente Anfrage auf den Fragmenten benötigt 2 Schritte:1. 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.
2. Kombination des Rekonstruktionsausdrucks mit dem algebraischen Anfrageausdruck, der sich aus der Übersetzung der SQL-Anfrage ergibt.
35
Beispiel SELECT TitelFROM Vorlesungen, ProfsWHERE gelesenVon = PersNr AND Rang = "C4";
Der entstandene algebraische Ausdruck heißt kanonische Form der Anfrage:
ΠTitel
σRang="C4"
gelesenVon=PersNr
TheolVorls PhiloVorls PhysikVorls TheolProfs PhiloProfs PhysikProfs
36
Algebraische Äquivalenzen
Für eine effizientere Abarbeitung der Anfrage benutzt der Anfrageoptimierer die folgende Eigenschaft:
(R1 R2) p (S1 S2) =
(R1 p S1) (R1 p S2) (R2 p S1) (R2 p S2)
Die Verallgemeinerung auf n horizontale Fragmente R1,...,Rn von R und m Fragmente S1,...,Sm von S ergibt:
(R1 ... Rn) p (S1 ... Sm) = (Ri p Sj)
1in 1jm
Falls gilt: Si = S p Ri mit S = Si ... Sn ,
dann tragen die Joins Ri p Sj für i j nichts Neues zum Join-Ergebnis bei. (Achtung: Fehler im Buch!)
37
Algebraische Äquivalenzen (Forts.)
Für eine derartig abgeleitete horizontale Fragmentierung von S gilt somit:
(R1 ... Rn) p (S1 ... Sm) =(R1 p S1) (R2 p S2) ... (Rn p Sn)
38
Algebraische Äquivalenzen (Forts.)
Für eine derartig abgeleitete horizontale Fragmentierung von S gilt somit:
(R1 ... Rn) p (S1 ... Sm) =(R1 p S1) (R2 p S2) ... (Rn p Sn)
Noch einmal das konkrete Beispiel:
(TheolVorls PhysikVorls PhiloVorls) (TheolProfs PhysikProfs PhiloProfs)
Um Selektionen und Projektionen über hinweg "nach unten zu drücken" (push down) benötigt man folgende Äquivalenzen:
σp(R1 R2) = σp(R1) σp(R2)L(R1 R2) = L(R1) L(R2)
39
Optimale Form der AnfrageDie Anwendung dieser algebraischen Regeln generiert den folgenden Auswertungsplan:
ΠTitel ΠTitelΠTitel
gelesenVon=PersNr gelesenVon=PersNr gelesenVon=PersNr
σRang=‚C4‘ σRang=‚C4‘σRang=‚C4‘
TheolVorls TheolProfs PhysikVorls PhysikProfs PhiloVorls PhiloProfs
Auswertungen können lokal auf den Stationen STheol,
SPhysik und SPhilo ausgeführt werden Stationen können parallel abarbeiten und lokales Ergebnis voneinander unabhängig an die Station, die die abschliessende Vereinigung durchführt, übermitteln.
Auswertungen können lokal auf den Stationen STheol,
SPhysik und SPhilo ausgeführt werden Stationen können parallel abarbeiten und lokales Ergebnis voneinander unabhängig an die Station, die die abschliessende Vereinigung durchführt, übermitteln.
40
Anfragebearbeitung bei vertikaler Fragmentierung
Beispiel:
SELECT Name, GehaltFROM ProfessorenWHERE Gehalt > 80000;
Kanonischer Auswertungsplan:
ΠName, Gehalt
σGehalt>80000
TheolProfs PhysikProfs PhiloProfs
ProfVerw
41
Optimierung bei vertikaler Fragmentierung
Für unser Beispiel gilt:
Alle notwendigen Informationen sind in ProfVerw enthalten Der Teil mit Vereinigung und Join kann "abgeschnitten" werden. Das ergibt den folgenden optimierten Auswertungsplan:
ΠName, Gehalt
σGehalt>80000
ProfVerw
Beispiel für eine schlecht zu optimierende Anfrage: (Attribut Rang fehlt in ProfVerw)SELECT Name, Gehalt, Rang
FROM ProfessorenWHERE Gehalt > 80000;
42
Der natürliche Verbund zweier Relationen R und S
R
A B Ca1
a2
a3
a4
a5
a6
a7
b1
b2
b3
b4
b5
b6
b7
c1
c2
c1
c2
c3
c2
c6
S
C D Ec1
c3
c4
c5
c7
c8
c5
d1
d2
d3
d4
d5
d6
d7
e1
e2
e3
e4
e5
e6
e7
R S
C D EA Ba1
a3
a5
b1
b3
b5
c1
c1
c3
d1
d1
d2
e1
e1
e2
=
43
Join-Auswertung in VDBMS
Spielt eine kritischere Rolle als in zentralisierten Datenbanken
Problem: Argumente eines Joins zweier Relationen können auf unterschiedlichen Stationen des VDBMS liegen
Zwei Möglichkeiten zur Realisierung: Join-Auswertung mit und ohne Filterung
44
Betrachtung des allgemeinsten Falles:
Join-Auswertung in VDBMS
Äußere Argumentrelation R ist auf Station StR gespeichert
Innere Argumentrelation S ist der Station StS zugeordnet
Ergebnis der Joinberechnung wird auf einer dritten Station StResult benötigt
45
Join-Auswertung ohne Filterung
Nested-Loops
Transfer einer Argumentrelation
Transfer beider Argumentrelationen
Ziel: Einsatz etablierter Join-Verfahren aus zentralisierten DBMS:
46
Nested Loops
Iteration durch die äußere Relation R mittels Laufvariable r und Anforderung (über Kommunikationsnetz bei StS)der zu jedem Tupel r passenden Tupel s S mit r.C = s.C
Diese Vorgehensweise benötigt pro Tupel aus R eine Anforderung und eine passende Tupelmenge aus S (welche bei vielen Anforderungen leer sein könnte)
es werden 2 R Nachrichten benötigt
Hohes Nachrichtenaufkommen, das sich nur in LANs verantworten läßt.
47
Der natürliche Verbund zweier Relationen R und S
R
A B Ca1
a2
a3
a4
a5
a6
a7
b1
b2
b3
b4
b5
b6
b7
c1
c2
c1
c2
c3
c2
c6
S
C D Ec1
c3
c4
c5
c7
c8
c5
d1
d2
d3
d4
d5
d6
d7
e1
e2
e3
e4
e5
e6
e7
48
Alternative 1:Transfer einer Argumentrelation
Vollständiger Transfer einer Argumentrelation (z.B. R) zum Knoten der anderen Argumentrelation
Ausnutzung eines möglicherweise auf S.C existierenden Indexes auf Station StS
1.1.
2.2.
49
Alternative 2: Transfer beider Argumentrelationen
1.1. Transfer beider Argumentrelationen zum Rechner StResult
2.2. Berechnung des Ergebnisses auf dem Knoten StResult mittels
a)a) Merge-Join (bei vorliegender Sortierung)
oderb)b) Hash-Join (bei fehlender Sortierung)
evtl. Verlust der vorliegenden Indexe (auf StR und/oder StS) für die Join- Berechnung
aber kein Verlust der Sortierung der Argumentrelation(en)
50
Join-Auswertung mit Filterung
Verwendung des Semi-Join-Operators zur Vorfilterung
Schlüsselidee: transferiere nur die Tupel, die passenden tatsächlich einen Join-Partner finden werden
Benutzung der folgenden algebraischen Eigenschaften:
R S = R (R S)R S = ΠC(R) S
(Join-Attribut in Relation R ist C)
Bisher: Transfer potentiell großer Datenmengen, auch fallsResultat der Join-Operation selbst sehr klein ist (hohe Selektivität).
Daher:
51
Join-Auswertung mit Filterung (Beispiel, Filterung der Relation S)
Transfer der unterschiedlichen C-Werte von R (= ΠC(R) ) nach StS
Auswertung des Right-Semi-Joins R S = ΠC(R) S auf StS und Transfer des Ergebnisses nach StR
Auswertung des Joins auf StR , der nur diese transferierten Ergebnistupel des Semi-Joins braucht
1.1.
2.2.
3.3.
Transferkosten werden nur reduziert, wenn gilt:
ΠC(R) + R S < S mit = Größe (in Byte) einer Relation
Transferkosten werden nur reduziert, wenn gilt:
ΠC(R) + R S < S mit = Größe (in Byte) einer Relation
52
R (ΠC(R) S)C D EA B
a1
a3
a5
b1
b3
b5
c1
c1
c3
d1
d1
d2
e1
e1
e2
RA B Ca1
a2
a3
a4
a5
a6
a7
b1
b2
b3
b4
b5
b6
b7
c1
c2
c1
c2
c3
c2
c6
Cc1
c2
c3
c6
SC D Ec1
c3
c4
c5
c7
c8
c5
d1
d2
d3
d4
d5
d6
d7
e1
e2
e1
e2
e3
e2
e6
15 Attributwerte...
ΠC(R) SC D Ec1
c3
d1
d2
e1
e2
ΠC
StR
StResult
StS
4 Attributwerte
6 Attributwerte
Auswertung des Joins R
A S
mit Semi-Join-Filterung von
S
53
Alternative Auswertungungspläne
1. Alternative: ...
ΠC
StR
StResult
StS
R S
2. Alternative:
(R ΠC(S)) (ΠC(R) S)
54
Parameter für die Kosten eines VBMDS-Auswertungsplans
Kardinalitäten von Argumentrelationen
Selektivitäten von Joins und Selektionen
Transferkosten für Datenkommunikation: Verbindungsaufbau ++ Datenvolumen
(CPU-)Auslastung der einzelnen VDBMS-Stationen
Effektive Anfrageoptimierung muss auf Basis eines Kosten-modells durchgeführt werden und soll mehrere Alternativen für unterschiedliche Auslastungen des VDBMS erzeugen.
Effektive Anfrageoptimierung muss auf Basis eines Kosten-modells durchgeführt werden und soll mehrere Alternativen für unterschiedliche Auslastungen des VDBMS erzeugen.
55
Transaktionskontrolle in VDBMS
Globale 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.
56
EOT-Behandlung in VDBMS
commit: globale Transaktion wird an allen (relevanten) lokalen Stationen
festgeschrieben
Die EOT (End-of-Transaction)-Behandlung von globalen Transaktionen stellt in VDBMS eine Herausforderung dar.
Eine globale Transaktion muss atomar beendet werden, d.h. entweder
abort: globale Transaktion wird an allen (relevanten) Stationen nicht festgeschrieben
oderoder
Problem in verteilter Umgebung, da die Stationen eines VDBMS unabhängig voneinander "abstürzen" können
Problem in verteilter Umgebung, da die Stationen eines VDBMS unabhängig voneinander "abstürzen" können
57
Problemlösung:Two-Phase-Commit-Protokoll (2PC)
Das 2PC-Verfahren wird von der sog. Koordinator-StationK überwacht.
2PC 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.
Gewährleistet die Atomarität der EOT-Behandlung in VDBMS
58
Nachrichtenaustausch beim 2PC-Protokoll (für 4 Agenten)
KK
A1
A2
A3
A4
K
A1
A2
A3
A4
PREPARE FAILED/READY COMMIT/ABORT ACK
4 Messages?
Phase 1 Phase 2
59
Ablauf der EOT-Behandlung beim 2PC-Protokoll 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:
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, Bestätigung) 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.)
60
Zustandsübergang beim 2PC-Protokoll: Koordinator
Initial
Abgebrochen
Bereit
Fertig
Festschreibend
EOT: Alle an T beteiligen Agenten im Log
protokollieren sende PREPARE an Agenten
READY von allen Agentenempfangen:
(T,commit) ins Log sende COMMIT
Timeout oder 1 x FAILEDempfangen:
(T,abort) ins Log ABORT senden
von allen ACK empfangen: von allen ACK empfangen:
"Bullet" = wichtigste Aktion(en)
(T,terminated) ins Log
61
Zustandsübergang beim 2PC-Protokoll: Agent
Wartend
Bereit
Abgebrochen Festgeschrieben
COMMIT empfangen: (T,commit) ins Log sende ACK
ABORT empfangen: (T,abort) ins Log sende ACK
PREPARE empfangen undlokal alles okay:
Log-Einträge für T schreiben (T,ready) ins Log sende READY
Timeout od. PREPARE empfangenund lokaler Fehler entdeckt:
(T,abort) ins Log sende FAILED
(verspätetes) PREPARE empfangen: sende FAILED
"Bullet" = wichtigste Aktion(en)
Ab hier: Agent verpflichtet sich,T erfolgreich zu beenden
62
Blockierung eines Agenten
2PC birgt die Gefahr der Blockierung der Agenten:
Agent befindet sich im Zustand Bereit (hat sich also verpflichtet, T erfolgreich zu beenden)
Agent wartet vergeblich auf COMMIT/ABORT-Entscheidung durch K Timeout
= Versuche globale COMMIT-Entscheidung bei K nachzufragen (Kommunikationsfehler?)
= Ist 1. erfolglos (K abgestürzt?), erfrage COMMIT-Entscheidung bei weiteren Agenten A oder erfrage, ob A mit FAILED geantwortet hat
= Ist auch 2. erfolglos, wird der Agent blockiert, bis K wieder funktionsfähig ist und die COMMIT-Entscheidung nachholt
63
Crash-Recovery in Agenten-Knoten
Inspiziere den lokalen Log des Agenten, um nach Wiederanlauf die Recovery zu steuern:
Ist auf dem Log ein Eintrag (T, commit) vorhanden, war T bereits erfolgreich beendet. REDO(T) anstossen, um Änderungen, die ausfallbedingt verloren gingen, nachzuholen.
Ist Eintrag (T, abort) vorhanden, war T zur Rücksetzung vorgesehen. Durch UNDO(T) alle Änderungen durch T an der Datenbank zurücknehmen.
Ist Eintrag (T, ready) vorhanden, fehlte zum Absturzzeitpunkt die COMMIT-Entscheidung von K. Entscheidung bei K nachfragen (K hält diese Information noch, da nicht alle ACK-Messages von allen Agenten eingetroffen).
64
Crash-Recovery im Koordinator
Koordinator K untersucht seinen lokalen Log:
Ist (T,terminated) im Log, stoße lediglich lokales UNDO(T)/REDO(T) an, je nachdem ob (T,abort) oder (T,commit) zuvor im Log gefunden wird
Ist (T,abort) im Log, führe lokal ein UNDO(T) aus. Sende ABORT an alle Agenten, die bisher noch kein ACK signalisiert haben.
Ist (T,commit) im Log, führe lokal REDO(T) aus. Sende COMMIT an alle Agenten, die bisher noch kein ACK signalisiert haben.
Setze im jeweils durch den Log signalisierten Zustand fort.
65
Lineare Organisationsform beim 2PC-Protokoll
K A1 A2 A3
FAILED/READY FAILED/READY FAILED/READY
COMMIT/ABORT COMMIT/ABORTCOMMIT/ABORT
COMMIT-Entscheidung wird sequentiell zwischen den AgentenKommuniziert:
• 2PC-Phase 1: Vorwärtskommunikation• 2PC-Phase 2: Komm.sequenz in umgekehrter Reihenfolge
ACK
66
Mehrbenutzersynchronisation in VDBMS
Serialisierbarkeit(kontrollierte und konsistente Verzahnung von DBMS-Operationen: Zyklen im Serialisierbarkeitsgraphen?)
Zwei-Phasen-Sperrprotokoll in VDBMS● lokale Sperrverwaltung an jeder Station ● globale Sperrverwaltung
67
Serialisierbarkeit
Lokale Serialisierbarkeit an jeder der an den Transaktionen beteiligten Stationen reicht nicht aus. Deshalb muß man bei der Mehrbenutzersynchronisation auf globaler Serialisierbarkeit bestehen.
Lokale Serialisierbarkeit an jeder der an den Transaktionen beteiligten Stationen reicht nicht aus. Deshalb muß man bei der Mehrbenutzersynchronisation auf globaler Serialisierbarkeit bestehen.
Beispiel (lokal serialisierbare Historien):
Schritt T1 T2
1.2.
Schritt T1 T2
3. 4.
r(A)w(A)
w(B)r(B)
S1 S2
T1 T2
68
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 (Shared, eXclusive) mit bereits existierenden Sperren kann lokal entschieden werden Favorisiert lokale Transaktionen, da diese nur mit ihrem lokalen Sperrverwalter kommunizieren müssen
69
Globale Sperrverwaltung
Zentraler Sperrverwalter kann zum Engpass des VDBMS werden, besonders bei einem Absturz der Sperrverwalter-Station
Verletzung der lokalen Autonomie der Stationen, da auch lokale Transaktionen ihre Sperren bei der zentralisierten Sperrverwaltung anfordern müssen
Alle Transaktionen fordern alle Sperren an einer einzigen, ausgezeichneten Station (Koordinator) an.
Nachteile:
Zentrale Sperrverwaltung i.a. nicht akzeptabel
70
Deadlocks in VDBMS
Erkennung von Deadlocks (Verklemmungen)
• Zentralisierte Deadlock-Erkennung: • Dezentrale (verteilte) Deadlock-Erkennung: schwierig
Vermeidung von Deadlocks
71
Ein "Verteilter Deadlock"
Schritt T1 T2
0.1.2.
6.
BOTlockS(A)
r(A)
lockX(A)
S1
Schritt T1 T2
3. 4. 5.
7. lockS(B)
BOTlockX(B)
w(B)
S2
• Lokal ist jeweils keine Deadlock-Situation zu erkennen• Der globale Waits-for-Graph ist jedoch zyklisch
72
Erkennung von verteilten Deadlocks : Timeout
Betroffene Transaktion T wird nach Erreichen einer nicht mehr akzeptablen Wartezeit zurückgesetzt und alle Sperren freigegeben. Dann T erneut starten einfach zu realisieren
Problem: Richtige Wahl des Timeout-Intervalls: • zu lang schlechte Ausnutzung der
Systemressourcen, Stationen sind für signifikante Zeit "idle"
• zu kurz Deadlock-Behandlung initiiert, obwohl keine Verklemmung vorliegt
73
Erkennung von verteilten Deadlocks : Zentralisiert
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 durch gegenseitiges "Überholen" von Nachrichten im Kommunikationssystem
74
Erkennung von verteilten Deadlocks : Dezentral
Führe 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 repräsentiert
Zuordnung jeder Transaktion zu einem Heimatknoten (Station, auf der BOT ausgeführt wurde), von wo aus externe Subtransaktionen auf anderen Stationen initiiert werden
75
Dezentrale Deadlock-Erkennung: External
External T2 *) External T1
T1 External T2 External
*) Lies: Externe Transaktionen können potentiell aufgrund von T2 auf S1 gesetzten Locks blockieren.
Schritt T1 T2
0.1.2.
6.
BOTlockS(A)
r(A)
lockX(A)
S1
Schritt T1 T2
3. 4. 5.
7. lockS(B)
BOTlockX(B)
w(B)
S2
76
Beispiel:S1 Heimatknoten von T1, S2 Heimatknoten von T2
Wartegraphen (Zyklus mit External = potentieller Deadlock):
S1: External → T2 → T1 → External
S2
:External → T1 → T2 → External
S2
:External T1 T2 External
T1 → T2 → T1
T2 → T1 → T2
S1 sendet Wartegraphenan die Station, auf der T1
eine Teiltransaktion angestoßenhat (hier: S2).
S2 kann globalen Deadlock (Zyklus ohne External) erkennen.
S2 wählt eine Opfer-Transaktion, setzt diese zurück und löst damit den Deadlock auf.
77
Deadlock-Vermeidung
Optimistische Mehrbenutzersynchronisation:Nach Abschluss der Transaktionsbearbeitung auf lokalen Kopien wird Validierung (alles serialisierbar?) 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)
Deadlock-Erkennung in VDBMS ist aufwendig und Kommunikationsintensiv Versuche, Deadlocks von vornherein zu vemeiden.
78
Sperrbasierte Synchronisation
Wound/wait:Nur jüngere Transaktionen (jedes T bekommt zu BOT einen time stamp) 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 ( strikte Bevorzugung bereits lang laufender Transaktionen)
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 ( ältere Transaktionen bevorzugt, Blockierung mit zunehmender Alter aber immer wahrscheinlicher)
79
Zeitstempel: Voraussetzungen für Deadlockvermeidungsverfahren
Vergabe global eindeutiger Zeitstempel als Transaktionsidentifikatoren. Format:
Vergleich von Zeitstempeln lexikographisch: vergleiche erst bzgl. lokaler Zeit, dann bzgl. Station.
Lokale Uhren müssen hinreichend genau aufeinander abgestimmt sein.
lokale Zeit Stations-ID
80
Synchronisation bei replizierten Daten
Problem:
Im VDBMS gibt es zu einem Datum A mehrere Replikate A1, A2, ..., An, die auf unterschiedlichen Stationen liegen.
Eine Lesetransaktion erfordert nur (irgend)eine Kopie,bei Änderungstransaktionen müssen aber alle bestehenden Kopien geändert werden, inkl. Sperrfanforderung, Kommunikation, etc.
Hohe Laufzeit und Verfügbarkeitsprobleme
(bspw. Heimatstation einer Kopie Ai nicht erreichbar)
Lesetransaktionen eindeutig bevorteilt
81
Quorum-Consensus Verfahren Ausgleich der Leistungsfähigkeit zwischen Lese- und Änderungstransaktionen teilweise Verlagerung des Overheads von den Änderungs- zu den Lesetransaktionen indem den Kopien Ai eines replizierten Datums A individuelle Gewichte (Stimmen) wi zugeordnet werden.
Beispiel:
Gesamtgewicht W(A) = i=1,…,4 wi(Ai) = 8
Station (Si) Kopie (Ai) Gewicht (wi)
S1 A13
S2 A21
S3 A32
S4 A42
82
Quorum-Consensus Verfahren
Weiterhin: Festlegung von Lesequorum Qr(A) und Schreibquorum Qw(A).
Eine Lesetransaktion, die r(A) ausführen will, muß zuvor mindestens Qr(A) Stimmen an den Stationen "einsammeln" und deren Kopien von A mit einem shared lock lockS(A) belegen.
Eine Schreibtransaktion muß vor Operation w(A) Qw(A) Stimmen an den Stationen einsammeln und deren Kopien jeweils mit exclusive locks lockX(A) belegen.
Zusatzbedingungen (Beispiel: Qr(A) = 4, Qw(A) = 5):
Qw(A) + Qw(A) > W(A)
Qr(A) + Qw(A) > W(A)
83
Quorum-Consensus Verfahren Wie werden Updates propagiert?
Eine Schreibtransaktion wird ja nur die Kopien auf den Stationen ändern, deren Stimmen sie eingesammelt hat (und dort lockX-Locks besitzt).
Protokolliere für jedes Datenobjekt eine Versionsnummer.
Eine Schreibtransaktion versieht das geschriebene Objekt mit dem Maximum aller seiner Versionsnummern + 1.
84
Zustände vor (a) und nach (b) Update A := A + 100
Station Kopie Gewicht Wert Versions#
S1 A13 1000 1
S2 A21 1000 1
S3 A32 1000 1
S4 A42 1000 1
a) vor dem Schreiben eines Schreibquorums
b) nach dem Schreiben eines Schreibquorums
Station Kopie Gewicht Wert Versions#
S1 A13 1100 2
S2 A21 1000 1
S3 A32 1100 2
S4 A42 1000 1
85
Quorum-Consensus Verfahren Eine Lesetransaktion liest mehrere Kopien, um mindestens Qr(A) Stimmen "einzusammeln", nutzt aber nur den A-Wert mit der höchsten Versionsnummer.
Beispiel: Lese die Kopien A3 und A4 (Stimmen? w3(A) + w4(A) = 4 Qr(A) ), nutze jedoch nur den Wert der Kopie A3.
Die Bedingunng
Qr(A) + Qw(A) > W(A)
stellt sicher, daß auf mindestens eine Kopie des letzten Schreibquorums zugegriffen wird.