Kapitel 11: Mehrbenutzersynchronisation und Serialisierbarkeit

Question 1

Arten von Mehrbenutzersynchronisation?

Answer 1

• Im Einzelbetrieb
  
  • laufen sequenziell
• Im verzahnten Mehrbenutzerbetrieb
  
  • Laufen parallel
  • Bei warten auf Nutzer von TA1 läuft beispieslweise zwischenzeitlich TA2 an

Question 2

Beispiel für Fehler bei unkontrolliertem Mehrbenutzerbetrieb?

Answer 2

Lost update: write(A,a2) geht verloren, da überschrieben

Question 3

Fehler zwei bei Mehrbenutzerbetrieb

Answer 3

Dirty read: liest Wert, der später zurückgesetzt wird

Question 4

Fehler drei bei Mehrbenutzerbetrieb?

Answer 4

Phantomproblem: T1: SElect, T2: dann daten hinzugefügt, T1dann erst mit select arbeiten

Question 5

Was ist Serialisierbarkeit?

Answer 5

• Historie ist aquivalent zu einer seriellen Historie
• Dennoch parallele (verzahnte) Ausführung möglich

Es wird immer gewartet, bis verwendeter Wert festgeschrieben wurde. Wird er zeitlich verwendet, kann gegebenenfalls ein Konflikt auftreten (siehe Beispiele). Serialisierungsgraphen zeichnen, wer kommt nach wem? Muss azyklisch sein

Question 6

Beispielaufgabe Aquivalenz verschiedener Historien I

Answer 6

lösen:

Question 7

Beispielaufgabe Äquivalenz einer Historie II

Answer 7

Lösen:

Question 8

Wann ist ein Serialisierungsgraph serialisierbar

Answer 8

WEnn er azyklisch ist (aufzeichnen)

Question 9

Erkläre Rücksetzbarkeit (RC)

Answer 9

• Eine Transaktion darf erst dann ihr commit durchführen, wenn alle Transaktionen, von denen sie gelesen hat, beendet sind.

TA kann zurückgesetzt werden, ohne dadurch Änderungen einer anderen TA plötzlich inkonsistent werden zu lassen.

Question 10

Erkläre kasskadierendes Rücksetziten (ACA)

Answer 10

TA kann zurückgesetzt werden, ohne dadurch Änderungen einer anderne TA inkonsistenz werden zu lassen.

Question 11

Erkläre strikte Historien (ST)

Answer 11

Historien in dieser Klasse haben die Eigenschaft, dass Transaktionen zurückgesetzt werden können, ohne dadurch das Zurücksetzen einer anderen TA notwendig zu machen.

Question 12

Wie sehen die verschiedenen Arten in Beziehung aus?

Answer 12

Question 13

Was ist der DB Scheduler?

Answer 13

Question 14

Nennen Sie die Modi der sperrbasierten Synchronisation

Answer 14

• S (shared, read lock) - Lesesperre
• X (exclusive, write lock) - Schreibsperre

Verträglichkeit:

S Sperre: geht bei NL und S

X Sperre: geht bei NL

Question 15

Definition: Zwei-Phasen Sperrprotokoll (2PA)

Answer 15

1. Jedes Objekt, das von TA genutzt wird muss gesperrt werden.
2. TA fordert Sperre, die sie schon besitzt nicht erneut an
3. Verträglichkeitstabelle muss eingehalten werden
4. Zwei Phasen
   
   1. Wachstumsphase: Sperre wird angefordert, aber keine freigegeben
   2. Bisher erworbene Sperre wird freigegeben, keine weitere darf angefordert werden
5. EOT muss TA alle Sperren zurückgeben

Question 16

Beispiel für Zwei-Phasen Sperrprotokoll

Answer 16

Question 17

Unterschied zwischen 2PL und strengem 2PL

Answer 17

• 2PL schließt kasskadierendes Rücksetzen nicht aus
• strenges 2PL:
  
  • alle Sperren werden bis EOT gehalten
  • kaskadierendes Rücksetzten ist somit ausgeschlossen

Question 18

Wie können in 2PL Deadlocks auftreten?

Answer 18

Question 19

Wie können Deadlocks erkannt werden?

Answer 19

• Wartegraph erstellen um zyklen zu finden

Question 20

Wie ist die Beziehung zwischen Wartegraph und Serialisierungsgraph?

Answer 20

Wartegraph ist teilmenge des seralisierungsgraphen.

Kann sein, dass man nie warten muss aber trotzdem kanten im seralisierungsgraph hat. Anders herum hat man eine kante im wartegraph, hat man diese auch garantiert im SG

Question 21

Wie können Deadlocks vermieden werden? und wie sehen die Verfahren aus?

Answer 21

• Preclaiming:
  
  • Beginn der Transaktion alle benötigten Sperren auf einmal setzen
  • ist eine Illusion. geh nicht, da man nicht weiß worauf der user zugreifen wird.
• Zeitstempel:
  
  • eindeutige Zeitstempel (TS) für jede TA
  • ältere TA keleinere TS als jüngere TA
  • wound-to-wait:
    
    • T1 will Sperre erwerben, die von T2 gehalten wird.
    • Wenn T1 älter als T2 ist, wird T2 abgebrochen und zurückgesetzt, so dass T1 weiterlaufen kann
    • Sonst wartet T1 auf die Freigabe der Sperre durch T2
  • wait-die-strategie:
    
    • T1 will Sperre erwerben, die von T2 gehalten wird.
    • Wenn T1 älter als T2 ist, wartet T1 auf die Freigabe der Sperre
    • Sonst wird T1 abgebrochen und zurückgesetzt.

Question 22

Welche Eigenschaften (SR,RC,ACA,ST) haben Historien, welche vom 2PL und vom strengen 2PL zugelassen werden?

Answer 22

2PL garantiert Historien aus SR. Das strenge 2PL garantiert Historien aus SR ∩ ST.

Question 23

Wa ̈re es beim strengen 2PL-Protokoll ausreichend, alle Schreibsperren bis zum EOT (Transaktionsende) zu halten, aber Lesesperren schon fru ̈her wieder freizugeben?

Answer 23

Es ist ausreichend, beim strengen 2PL-Protokoll nur die Schreibsperren bis zum Ende der Transaktion zu halten. Lesesperren ko ̈nnen analog zum normalen 2PL- Protokoll in der Schrumpfungsphase (nach wie vor jedoch nicht in der Wachstums- phase) peu `a peu freigegeben werden. Die generierten Schedules bleiben serialisier- bar und strikt

Question 24

Beim strikten 2PL commit werden die folgende Schritte in angegebener Rei- henfolge ausgeführt:

1. Eintragen des commit in den Logbuffer
2. Persistieren des Logbuffer
3. Freigabe aller Sperren
4. Rückmeldung an den Benutzer

Manche Datenbanksysteme führen Schritt 3 als ersten Schritt aus. Was kann dies für Vorteile bringen? Sind trotzdem noch alle Garantien vom strikten 2PL gewährleistet, wenn ja unter welchen Bedingungen?

Answer 24

In der ursprünglichen Abfolge muss gewartet werden, bis das Log auf die Festplatte geschrieben ist. Dies kann mehrere Millisekunden dauern. Gerade fürr sehr schnelle Transaktionen kann dies ein vielfaches der eigentlich Verarbeitungsdauer sein. In der vorgeschlagenen Abfolge entfällt das Warten auf die Festplatte und die Sperren können viel früher freigegeben werden. Dadurch wird der Durchsatz des Systems erhöht.

Um die Eigenschaften von strikten 2PL zu erhalten, dürfen nur serialisierbare und strikte Historien möglich sein. Da für Serialisierbarkeit von Transaktionen nur die Schreib- und Leseoperationen betrachtet werden und die Änderung erst im commit-Schritt ist, ändert sich in dieser Hinsicht nichts.

Für Striktheit ist es wichtig, dass keine andere Transaktion die veränderten Daten der aktuellen Transaktion an den Benutzer zurückliefert, solange nicht garantiert ist, dass diese nicht mehr zurückgesetzt wird. Zum Zeitpunkt des commit ist die einzig mögliche Ursache für ein Abbruch, dass das Log nicht persistiert werden kann.

Falls mehrere Transaktionen gleichzeitig committen dürfen, kann ein Fehlerzustand gezeigt werden. Dazu T2 schließt alle Schritte des commit ab und das System crasht, bevor T1 das commit in den Logbuffer einträgt. Somit würde beim Wiederanlauf T1 zur Losertransaktion und ihre Änderungen zurückgenommen. Damit hätte T2 Daten gelesen, die nicht mehr in der Datenbank stehen.

Behebung:

• Immer nur eine Transaktion darf gleichzeitig im commit sein.
• Die Freigabe der Sperren wird erst nach Eintragen des commit in den Logbuf- fer durchgeführt.

Question 25

Nennen Sie die Vorteile und Nachteile von Deadlockerkennung / Vermeidung durch:

• Timeouts
• Wartegraphen • Preclaiming
• Zeitstempel
• Sind Kombinationen denkbar/sinnvoll?

Answer 25

Timeouts

• • Verfahren ist einfach und billig
• • Deadlocks werden erst mit Verzögerung erkannt
• • Es gibt false positives

Wartegraphen

• • Es werden echte Deadlocks schnell erkannt
• • Hohe kosten

Preclaiming

• • Deadlocks treten nicht auf
• • Verringert Parallelität

Zeitstempel

• • Deadlocks treten nicht auf
• • Viele Transaktionen müssen zurückgesetzt werden, obwohl nie ein Deadlock auftreten würde – false positives.

Beispielsweise kann Timeout und Wartegraph kombiniert werden. Hierbei wird der Wartegraph erst erzeugt, wenn ein Timeout auftritt. Es treten so im Vergleich zum Timeout-Verfahren keine false positives mehr auf und das Verfahren bleibt im Regelfall billig, da der Wartegraph ”on demand“ erzeugt wird. Das Problem der verzo ̈gerten Erkennung von Deadlocks bleibt allerdings bestehen.

Question 26

Was ist MGL? Beispiel?

Answer 26

Multi-Granularity-Locking:

• NL: keine Sperrung (no lock),
• S: Sperrung durch Leser,
• X: Sperrung durch Schreiber,
• IS (intention share): Weiter unten in der Hierarchie ist eine Lesesperre (S) beabsichtigt,
• IX (intention exclusive): Weiter unten in der Hierarchie ist eine Schreibsperre (X) beabsichtigt.

Vorgehen:

1. Bevor ein Knoten mit S oder IS gesperrt wird, müssen alle Vorgänger in der Hierarchie vom Sperrer (also der Transaktion, die die Sperre anfordert) im IX- oder IS-Modus gehalten werden.
2. Bevor ein Knoten mit X oder IX gesperrt wird, müssen alle Vorgänger vom Sperrer im IX-Modus gehalten werden.
3. Die Sperren werden von unten nach oben (bottom up) freigegeben, so dass bei keinem Knoten die Sperre freigegeben wird, wenn die betreffende Transaktion noch Nachfolger dieses Knotens gesperrt hat.

Question 27

Beim ”multiple-granularity locking“ (MGL) werden Sperren von oben nach un- ten (top-down) in der Datenhierarchie erworben. Zeigen Sie mo ̈gliche Fehlerzusta ̈nde, die eintreten könnten, wenn man die Sperren in umgekehrter Reihenfolge (also bottom-up) setzen wu ̈rde.

Answer 27

Bottom-up sorgt für mehr Konflikte, Beispiel T1 weiter oben T2 weiter unten. Wenn erst T1 kann unter umständen T2 nicht mehr durchgeführt werden. Folge ist eine erhöhte Serialisierung und somit schlechtere Performance

Question 28

Was ist optimistische Synchronisation?

Answer 28

1. Lesephase:

• In dieser Phase werden alle Operationen der Transaktion ausgeführt – also auch die Änderungs operationen.
• Gegenüber der Datenbasis tritt die Transaktion in dieser Phase aber nur als Leser in Erscheinung, da alle gelesenen Daten in lokalen Variablen der Transaktion gespeichert werden.
• alle Schreiboperationen werden zunächst auf diesen lokalen Variablen aufgeführt.

2. Validierungsphase:

• In dieser Phase wird entschieden, ob die Transaktion möglicherweise in Konflikt mit anderen Transaktionen geraten ist.
• Dies wird anhand von Zeitstempeln entschieden, die den Transaktionen in der Reihenfolge zugewiesen werden, in der sie in die Validierungsphase eintreten.

3. Schreibphase:
   * Die Änderungen der Transaktionen, bei denen die Validierung positiv verlaufen ist, werden in dieser Phase in die Datenbank eingebracht.

Question 29

Wie können Synchronisationsverfahren klassifiziert werden?

Answer 29

Question 30

Weisen Sie (halbwegs) formal nach, dass das 2PL-Protokoll nur serialisierbare Historien zulässt.

Answer 30

Question 31

Erläutern Sie Probleme, die bei der naiven Implementierung von SSL auftreten können. Lesen Sie hierzu beispielsweise http://www. ietf.org/mail-archive/web/tls/current/msg07553.html und skizzieren Sie sowohl den traditionellen Angriff mittels eines Botnets sowie den dort neu vorgestellten Angriff mittels Renegotiation. Wie können derartige Angriffe verhindert werden? Können Sie sich a ̈hnliche Angriffe auch im Bezug auf den Einsatz von Datenbanken vorstellen?

Answer 31

Viele DoS Attacken basieren auf der Tatsache, dass durch den Client eine Operation auf dem Server bewirkt werden kann, deren Bearbeitung den Server mehr kostet als es den Client kostet, die Operation auszulo ̈sen.
Im Falle eine DDoS Attacke, d.h. eines verteilten Angriffs ist dies nicht zwingend no ̈tig. Vielmehr muss eine große Zahl von Clients zur Verfu ̈gung stehen, die eine kostspielige aber nicht notwendigerweise unproportional teure Operation auf dem Server auslo ̈sen. Dies la ̈sst sich beispielsweise durch ein Botnetza realisieren, welches eine Webseite gleichzeitig von tausenden verschiedenen Computern ausruft.

Bei SSL bietet es sich an, eine SSL Verbindung von jedem Rechner des Botnets aufzu- bauen. Hierdurch werden auf dem Server tausende Handshake-Berechnungen durch- gefu ̈hrt, auf jedem Client jedoch nur eine. Die Last auf dem Server steigt potentiell, bis dieser keine neuen Verbindungen mehr annehmen kann, wodurch eine Webseite effektiv nicht mehr erreichbar ist.

Die vorgeschlagene Renegotiation Attacke verzichtet auf den Multiplikator mittels Botnets indem hier ein Client den Server anweist, die Verschlu ̈sselung neu auszuhan- deln. Durch die auf Serverseite ho ̈heren Kosten dieser Operationb kann ein einzelner Client mittels Renegotiation-Request sehr hohe Kosten auf Serverseite verursachen und so das gleiche Resultat erzielen, wie beim zuvor genannten Angriff.