Kapitel 16: Verteilte Datenbanken Flashcards

1
Q

Terminologie verteilter Datenbanken

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Aufbau und Entwurf eines verteilten Datenbanksystems

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Fragmentierung und Allokation einer Relation

A
  • Fragmentierung: Fragmente enthalten Daten mit gleichem Zugriffsverhalten
  • Allokation: Fragmente werden den Stationen zugeordnet
    • mit Replikation (redundanzfrei)
    • ohne Replikation
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Arten der Fragmentierung + Korrektheitsanforderung

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Erkläre Horizontale Fragmentierung

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Behebung Fragmentierungsproblem bei Horizontaler Fragmentierung

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Erkäre vertikale Fragmentierung und deren Probleme

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Welche Formen der kombinierten Fragmentierung gibt es?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Erkläre Allokation

A
  • Dasselbe Fragment kann mehreren Stationen zugeordnet werden
  • Allokation für unser Beispiel ohne Replikationen ⇒ redundanzfreie Zuordnung

SVerw –> Verwaltungsrechner –> {ProfVerw}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Erkläre Transparenz und deren Arten in verteilten DB

A
  • Grad der Unabhängigkeit den ein VDBMS dem Benutzer beim Zugriff auf verteilte Daten vermittelt
  • Verschiedene Stufen der Transparenz:
  1. 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)

  1. 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‘;

  1. 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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Anfragebearbeitung bei horizontaler Fragmentierung

A

Ü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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Wie könnte eine Optimierung der horizontalen Fragmentierung aussehen?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Anfrageoptimierung bei vertikaler Fragmentierung:

Beispiel:

select Name, Gehalt from Professoren where Gehalt > 80000;

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Rolle von JOIN Auswertung bei VDBMS und Möglichkeiten?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Wie sieht Transaktionskontrolle in VDBMS aus?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Warum ist die EOT-Behandlung ein Problem?

A

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

17
Q

Wie kann das EOT-Problem gelöst werden?

A

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
18
Q

Wie sieht der Ablauf der EOT-Behandlung beim beim 2PC Protokoll aus?

A
  • 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
19
Q

Zustandsübergang beim 2PC-Protokoll für Koordinator:

A
20
Q

Zustandsübergang beim 2PC-Protokoll für Agenten:

A
21
Q

Fehlersituationen des 2PC-Protokolls + Beschreibung

A

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)
22
Q

Mehrbenutzersynchronisation in VDBMS

A
  • 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
23
Q

Wie können Deadlocks in VDBMS erkannt werden?

A

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
24
Q

Deadlockvermeidung in VDBMS

A

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

25
Q

Was ist das Quorum Consensus Verfahren?

A
  • 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 zugeordnet werden
    • Lesequorum Qr(A)
    • Schreibquorum Qw(A)
    • Folgende Bedingungen müssen gelten:
      1. Qw(A) + Qw(A) > W(A)
      2. Qr(A) + Qw(A) > W(A)
26
Q

NO-SQL Datenbanken?

A
  • Internet-scale Skalierbarkeit
  • CAP-Theorem: nur 2 von 3 Wünschen erfüllbar
    • Konsistenz (Consistency)  Zuverläassigkeit/Verfügbarkeit (Availability)
  • Partitionierungs-Toleranz
  • No-SQL Datenbanksysteme verteilen die Last innerhalb eines Clusters/Netzwerks
  • Dabei kommen oft DHT-Techniken zum Einsatz
  •  MongoDB  Cassandra  Dynamo  BigTable  Hstore  SimpleDB  S3
27
Q

Was ist das CAP Modell?

A

Relaxiertes Konsistenzmodell

  • Replizierte Daten haben nicht alle den neuesten Zustand
    • Vermeidung des (teuren) Zwei-Phasen-Commit-Protokolls
  • Transaktionen könnten veraltete Daten zu lesen bekommen
  • Eventual Consistency
    • Würde man das System anhalten, würden alle Kopien irgendwann (also eventually) in denselben Zustand übergehen
  • Read your Writes-Garantie
    • Tx leist auf jeden Fall ihre eigenen Änderungen
  • Monotonic Read-Garantie
    • Tx würde beim wiederholten Lesen keinen älteren Zustand als den vorher mal sichtbaren lesen
28
Q

Bei einer abgeleiteten horizontalen Zerlegung kann es vorkommen, dass die erzeugten Frag- mente nicht disjunkt sind. Charakterisieren Sie, unter welchen Umständen Disjunktheit gewährleistet ist, und unter welchen Umständen dies nicht der Fall ist. Hinweis: Charakte- risieren Sie die Beziehung zwischen der primär zerlegten Relation und der davon abhängig fragmentierten Relation.

Welche Voraussetzungen müssen erfüllt sein, so dass eine abgeleitete Fragmentierung voll- ständig ist?

A

Ob Disjunktheit bei einer abgeleiteten Zerlegung gewährleistet ist, hängt von den Multiplizitäten (m1 und m2) in der Beziehung stehenden Relation ab.

  • N:1 Hier ist disjunkte Zerlegung von R gewährlesitet, da zu jedem Tupel r element R kann es höchstens s Element S geben. Beispiel Aufteilung Vorlesung und Dozenten.
  • 1:N Hier ist Zuordnung der Tupel r Element R zu Tupeln s Element S durch die Beziehung Rel nicht mehr eindeutig. Damit kann auch Disjunktheit der ablegeiteten horizontalen Zerlegung von R nicht mehr sichergestellt werden. Z.b. Relation Vorlesung S und Professor R. Partitioniert man nach SWS ist auch bei kleinen Größen wird Disjunktheit schnell verletzt.
  • N:M: Verallgemeinerung von 1:N. Disjunktheit kann nicht gewährleistet werden.
29
Q

Gehen Sie von folgender kombinierter Fragmentierung der in Abbildung 1 dargestellten Relation Professoren aus:

  1. Zuerst erfolgt eine vertikale Fragmentierung in

ProfVerw := ΠPersNr, Name, Gehalt, Steuerklasse(Professoren)

Profs := ΠPersNr, Name, Rang, Raum, Fakultät(Professoren)

  1. Das Fragment Profs wird weiter horizontal fragmentiert in

TheolProfs := σ Fakultät = ’Theologie’(Profs)

PhysikProfs := σ Fakultät = ’Physik’(Profs)

PhiloProfs := σ Fakultät = ’Philosophie’(Profs)

Übersetzen Sie aufbauend auf dieser Fragmentierung die folgende SQL-Anfrage in die kanonische Form.

select Name , Gehalt Rang from Professoren
where Gehalt > 80000;

Optimieren Sie diesen kanonischen Auswertungsplan durch Anwendung algebraischer Trans- formationsregeln (Äquivalenzen).

A
30
Q

Überlegen Sie sich, welche Tupel bei der Anwendung des bloomfilterbasierten Joins in Abbildung 1 übertragen werden. Markieren Sie insbesondere, welche Tupel übertragen werden, obwohl sie keinen Joinpartner finden (sog. false drops). Wie kann die Anzahl dieser false drops verringert werden? Welche Eigenschaften sollte die Hashfunktion h(c) die bei dieser Joinbearbeitung verwendet wird erfüllen?

A
  • False Drops sind c7 und c8 die übertragen werden, obwohl sie keinen Joinpartner finden.
  • Bei sinnvoller Hashfunktion weniger False Drops je größer der Vektor ist. Gute Hashfunktion! Mehrere Hashfunktionen zu benutzen verbessert auch die Effizienz des Bloomfilters
  • Hashfunktion sollte möglichst gleichmäßig verteilen.
31
Q

Zweiphasen-Commit-Protokoll

Ein schwerwiegendes Problem des Zweiphasen-Commit-Protokolls (2PC) besteht darin, dass Agenten beim Absturz des Koordinators blockiert sind. Eine gewisse Abhilfe des Pro- blems la ̈sst sich dadurch erreichen, dass die Agenten sich untereinander beraten und eine Entscheidung herbeifu ̈hren. Entwickeln Sie ein derartiges Protokoll. Insbesondere sollten folgende Fa ̈lle abgedeckt sein:

(a) Einer der Agenten hat noch keine READY-Meldung an den Koordinator abgeschickt.
(b) Einer der Agenten hat ein ABORT empfangen.
(c) Ein Agent hat ein FAILED an den Koordinator gemeldet.
(d) Alle erreichbaren Agenten haben ein READY an den Koordinator gemeldet, aber keiner der erreichbaren Agenten hat eine Entscheidung (COMMIT oder ABORT) vom Koordinator empfangen.

In welchen Fa ̈llen ko ̈nnen die sich beratenden Agenten eine Entscheidung herbeifu ̈hren; in welchen Fa ̈llen ist dies nicht mo ̈glich (und deshalb eine Blockierung der Agenten nicht zu vermeiden)?

A

a) abort oder warten
b) Alle anderen sagen abort –> abort an alle
c) Abbruch
d) Noch mal senden. Warten

32
Q

Quorum-Consensus Verfahren

Zeigen Sie, dass die write-all/read-any Methode zur Synchronisation replizierter Daten einen Spezialfall der Quorum-Consensus-Methode darstellt.

  • Für welche Art von Workloads eignet sich dieses Verfahren besonders gut?
  • Wie werden Stimmen zugeordnet um write-all / read-any zu simulieren?
  • Wie müssen die Quoren Qw und Qr vergeben werden?
A

Dieses Verfahren fordert einen sehr großen Aufwand beim Schreiben, aber nur minimalen Aufwand beim Lesen. Daher eignet es sich besonders gut für Workloads in denen wesentlich mehr Daten gelesen als geschrieben werden. Dies entspricht z.B. analytischen Anfragen.

Berechnung es Gesamtgewicht W (A) zu W(A) bei n Kopien: Summe Wi(A)

Vergeben von Lesequorum Qr und Schreibquorum Qw:

  1. Qw(A) + Qw(A) > W(A)
  2. Qr(A) + Qw(A) > W(A)

Station / Kopie / Gewicht

S1/A1/1

S2/A2/1

S3/A3/1

S4/A4/1

33
Q

Zeigen Sie, dass bei der write-all / read-any Methode zur Synchronisation bei replizierten Daten nur serialisierbare Schedules erzeugt werden – unter der Voraussetzung, dass das strenge 2PL-Protokoll angewendet wird.

A

Write all: Gehe auf jede Station. Kann nicht lesen wenn ich schreibe. Siehe 4.2

34
Q

Zeigen Sie, dass die Suche in einem Chord-Overlaynetzwerk durch die Nutzung der Fin- gerTabellen in maximal logarithmisch vielen Schritten zur Gro ̈ße des Zahlenrings (bzw. der Anzahl der Stationen) durchgefu ̈hrt werden kann. Verwenden Sie die Suche nach K57 beginnend an Station P11 (siehe Abbildung 1) zur Illustration.

A

FingerTAbellen P3, P14, P26.

Log: Anhand Abbildung Größe 2^n. Nach log |P| sprüngen ist man wegen der Halbierung der Distanz bei jedem Sprung in einem Abstand von 2^n / |P| zum Peer p. P = Anzahl an Peers