KE 5

• erreicht skalierbarkeit

• reliablität erhöhen

  • wenn eine Replik abstürtzt

  • kann man mit der anderen weiterarbeiten

  • Schutz vor "corrupted" data durch Kopien

• Performanz verbessern

  • bei Größe

    • Server replizieren

    • Arbeitslast aufteilen

  • oder geographischer Verteilung

    • Kopie der Daten nah zu den Clients setzen

  • hier der Fokus (Reliabilität in Kapitel 8)

• Speichersystem

  • Menge von Prozessen

  • jeder hat Replikat auf lokalem Speicher

  • "konsistentes Speichersystem"

    • .= Speichersystem mit einem Konsistenzmodell

1) Monotonic Writes

2) Read your Writes

3) Monotonic Reads

4) Read your Writes

5) Write follows Reads

• in DB:

  • Grundlage ist ACID-Eigeschaft der Transaktionen

    • Atomicity = all-or-nothing

    • Consistency = only valid data written to database

    • Isolation = Transaktionen beeinflussen einander nicht

    • Durability = übermittelte Transaktionen gehen nicht verloren

• in VS:

  • schwächere Konsistenz

Modelle liefern Garantieren für Ergebnis von Zugriffen

1. Datenzentriert

   1. sequentielle Konsistenz

   2. kausale Konsistenz

   3. eventual consistency

      
      

      
      

2. Clientzentriert

   1. Monotonic Reads

   2. Monotonic Writes

   3. Read your Writes

   4. Write follow Read

      
      

… einer Menge von Operationen

= Reihenfolge der Operationen (Permutation)

• jede Leseoperation auf einem Element gibt genau den Wert,

  den die letzte Schreiboperation dort hineingeschrieben hat

Folge von Operationen die ein Prozess ausführt

geg.: Ausführungsgeschichte G = (F1, …, Fn) von n Prozessen

die ist linearisierbar, wenn

1. es eine Serialisierung aller Operationen aus G gibt

2. bei der Operation o1 als Paar (invocation, response) vor Operation o2 (invocation, response)

   auftreten muss, wenn die response von o1 vor der invocation von o2 vorkommt.

respektiert globale Zeitordnung aller Ereignisse

= Serversicht

• spezifiziert Einschränkungen auf Reihenfolge von Operationen, die von individuellen Servern ausgeführt werden müssen

• fokussiert Synchronisation zwischen Prozessen im Speichersystem und der Reihenfolge der Operationen

= viele Prozesse greifen simultan auf geteilte Daten zu (read und write)

• geht darum, was Prozesse erwarten können

  = Vertrag zwischen Prozess und Data store

  • wenn Prozess Regeln befolgt, arbeitet Store korrekt

1. Linearisierbarkeit

2. Sequentielle Konsistenz

3. Kausale Konsistenz

4. Eventual consistency

   = bleiben Updates aus, konvergieren alle Kopien gegen identische Kopie

= Sicht eines einzelnen Clients

• spezifiziert Anforderungen an Datenkonsistenz, die nur auf Interaktion einzelner Clienten und dem System basiert

• garantiert, was ein Client während einer Sitzung sieht

• einfacher zu implementieren

• Speichersystem ist Blackbox - geben einfach die Daten mit gewünschten Eigenschaften

• hier:

  • Data stores, die nicht simultane Updates brauchen

  • meist lesender Zugriff

• garantiert einzelnem Client

  • konsistenten Zugriff auf Data store

  • auch wenn er verschiedene Repliken verwendet

  • (bei eventual Konsistenz nicht gegeben)

• keine Garantie für gleichzeitigen Zugriff unterschiedlicher Clients

  • write-write Konflikte können entstehen

  • und lange dauern, bevor sie bemerkt werden

• Client verbindet sich zu nähester Replik

• updates werden eventuell zu anderen Kopien verbreitet

geg.: Ausführungsgeschichte G = (F_1, ..., F_n)

• F_i = Folgen von Operationen des Prozesses P.i

Sequentielle Konsistenz, wenn

1. es gibt eine Serialisierung aller Operationen aus G

2. bei der jede Folge F_i in genau ihrer Reihenfolge vorkommt

   • müssen nicht am Stück vorkommen

   
   

Zwei Operationen o1 und o2 einer Ausführungsgeschichte von n Prozessen erfüllen die kausale Relation o1 ⇒ o2 , dann und genau dann, wenn eine der drei folgenden

Bedingungen erfüllt ist:

1. Lokale Ordnung

   = o1, o2 Operationen desselben Prozesses

   • o1 wird in Ausführungsgeschichte von P vor o2 ausgeführt

2. Interprozess-Ordnung

   • o1 ist write-Operation auf Datenelelement: W_i(x)a

   • o2 ist read-Operation eines anderen Prozesses auf gleichem Datenelement mit selben Ergebnis, wie was vorher geschrieben wurde: R_j(x)a

3. Transitivität

   • es gibt eine Operation o, sodass o1 => o und o => o2 gilt

• schwächer als sequentielle Konsistenz

  • enthält nur das Notwendige

• aus Sicht jedes einzelnen Prozesses definiert

  • wichtig ist nur eigene Geschichte

  • und Schreiben anderer Prozesse auf gemeinsame Datenelemente

  • serialisiert müssen nur diese Operationen werden

geg.: Ausführungsgeschichte G = (F1, ..., Fn ) von n Prozessen

• Ai sei Menge aller Operationen in Fi , i = 1, . . . , n und aller Schreiboperationen in G

  = die Menge aller für P.i relevanten Operationen

Ausführungsgeschichte G = (F1, ..., Fn) heißt kausal konsistent, wenn es für jeden Prozess P.i eine Serialisierung der Menge A.i gibt, die die kausale Relation erfüllt.

kausale Konsistenz ist gegeben, wenn vier klientenzentrierten Konsistenzmodelle erfüllt sind:

• Monotonic Reads

• Monotonic Writes

• Read Your Writes

• Writes Follow Reads

1. womöglich kausal verkettet

2. nicht kausal verkettet

   concurrent

   = Operationen, die nicht kausal verbunden sind

   
   

wenn Ereigniss a ein Ereignis b kausal beeinflusst,

• dann muss a vor b geschehen sein

  
  

1. möglicherweise kausale Writes müssen von allen Maschinen gleich gesehen werden

2. concurrent Writes können in unterschiedlicher Reihenfolge von verschiedenen Maschinen gesehen werden

• dt.: schließliche Konsistenz

• irgendwann ensteht Konsistenz

• in Datenbanken kaum Updates

• kaum write-write-Konflikte

  • dann wird ein Prozess global als Gewinner deklariert

• nur read-write-Konflikte

• Updates lazy verbreiten

• Inkonsistenz wird toleriert

Bedingungen:

• liest Prozess den Wert eines Daten-Item x

• dann gibt jeder spätere Read-Zugriff

• entweder den gleichen Wert x

• oder einen aktuelleren

  • der muss aber aus dem vorherigen folgen

  • liest er Version n, dann später nur noch Version >= n lesen

Implementierung

• Client schickt bei Leseoperationen immer Read-Set Read-Set(C) mit

• Server weiß dann, ob er Schreiboperationen schon ausgeführt hat, die C gesehen hat

Bsp. Email

• Mail-Programm ruft E-Mails ab

• neue Mails muss Obermenge der bisher abgerufenen Emails sein

Bedingungen

• Schreibender Zugriff eines Prozesses auf Daten-Item x ist beendet

• vor einem folgenden Schreibzugriff auf x durch denselben Prozess

• -> Schreibende Operationen werden in korrekter Reihenfolge an alle Kopien der Daten weitervermittelt

• anders:

  • Schreiben auf Kopie der Daten, nur wenn die Kopie geupdatet wurde

• ist daten-zentrierte FIFO-Konsistenz

Implementierung

• Client muss bei Schreiboperationen immer Write-Set(C) mitsenden

• Server weiß dann, ob er bisherige Schreiboperationen von S ausgeführt hat

Beispiel:

• Editieren von Texten

Bedingungen:

• liest ein Prozess x sieht immer alle seine vorhergehenden Schreiboperationen auf x

• anders:

  • Server kann lesenden Zugriff erst ausführen, wenn er alle schreibenden Zugriffe des Clienten vorher ausgeführt hat

    
    

Implementierung:

• Client sendet bei Leseoperationen sein Schreibset Write-Set(C) mit

• Server weiß, ob er Cs Schreiboperationen schon ausgeführt hat

Bsp.:

• Passwort ändern

• Löschen von E-Mail

Bedingungen:

• Schreiben von Prozess P auf Daten Item x

• nach einem Lesen von P auf x

• garantiert, dass auf dem zuletzt gelesenen oder einem aktuelleren Wert von x geschrieben wird

• jedes Schreiben von P auf einem x, das wenigstens so aktuell wie das letzte Lesen von x ist

Implementierung

• Client schickt bei Schreiboperationen sein Read-Set(C) mit

• Server weiß, ob er Schreiboperationen ausgeführt hat, die C gelesen hat

Bsp.

• Antwort auf Newsgruppeneintrag

Wenn VS immer verfügbar sein soll

Wenn alle vier klientenzentrierten Konsistenzmodelle erfüllt sind

(MR, MW, RYW, WFR)

1. Platzierung von Servern

2. Platzierung von Inhalt

Bild 7_21_Replika_Arten

1. Permanent

   • kleine Anzahl

   • statisch organisiert

   2 Arten:

   • a) Verteilung über Server an einem einzelnen Ort

     • Request geht zu einem der Server

     • z.B. mit Round-robin

   • b) mirror sites

     • über Internet verteilt

     • Clienten wählen einen mirror

2. Server-initiiert

3. Client-initiiert

4. Clients

• Kopien der Daten

• um Performanz zu verbessern

• vom Bestzer des Datenstores geschaffen

• dynmisch geschaffen - bei z.B. vielen Anfragen aus einer Region

• auch abhängig von Datei

  • Anfragen unter einer Schranke -> lösche Datei

  • sichergestellt, dass immer irgendwo eine Kopie der Datei bleibt

• ebenso Replikationsschranke

  • Anfragenanzahl darüber?

  • neue Replikation erstellen

• gebräuchlicherer Name: "client caches"

• Client verwaltet cache

  • manchmal kann er Hilfe vom Server nutzen

• verbessern nur Zugriffszeit

• cache hit

  = Daten konnten vom lokalen Cache geholt werden

• geteilte Caches sind auch möglich

• pull vs. push operations

• unicasting vs. multicasting

  • multicasting:

    • Netzwerk versendet Nachrichten effizient

  • unicasting:

    • N Nachrichten für N Server

      • eine zu jedem Server

consistency protocol beschreibt implementierung eines Konsistenz-Modells

state vs operations

1. Benachrichtigungen über Update

   • machen invalidation protocols

   • braucht wenig Bandbreite

   • am besten bei kleiner read-to-write ratio

     
     

2. Daten von einer Kopie zur anderen

   • bei hoher read-to-write ratio

     
     

3. Update-Operation zu anderen Kopien

   • auch "active replication"

a) Push-Protokolle

b) Pull-Protokolle

c) hybrid: leases

• auch "server-based protocols"

• Repliken fragen nicht nach Update

• meist zwischen permanent und server based Repliken

• meist wenn starke Konsistenz verlangt wird

• Server muss alle Client-Caches kennen

• server oder client fragt Server nach Update

• auch "client-based protocols"

• meist bei client caches

• client fragt server, ob Daten nach letztem cache modifiziert wurden

• bei niedriger read-to-update-ratio

• Server verspricht Client für bestimmte Zeit updates zu schicken

• nach der Zeit muss Client lease verlängern

• oder dynamischer Wechsel zwischen push und pull

3 Arten

1. age-based lease

   • je nachdem wann Daten zuletzt geändert wurden

   • lange nicht geändert - wahrscheinlich auch in Zukunft nicht so schnell

2. renewal-frequency-based leases

   • je nach Häufigkeit, die der Cache geupdatet werden muss

   • für Clients die often refresh benötigen einen langen lease

   • kurzer lease für Client, der Daten nur selten benötigt

3. state-based lease

   • je nach server overhead

   • wird Server zu sehr ausgelastet, verkürzt er lease

   • ggf. muss er dann aber auch mehr arbeiten, wenn read-to-update ratio hoch ist

1. aktiv

   • Operation wird an alle Repliken weitergeleitet

   • jede Replik hat Prozess, der Updates ausführt

   • Updates als Write-Operationen verbreitet

   Problem:

   • Operationen müssen überall in gleicher Reihenfolge ausgeführt werden

   • braucht total-ordered multicast mechanism

   nutzt zentralen Koodinator:

   • heißt "sequencer"

   • Operation geht zu ihm

   • er gibt jeder eine einzigartige Sequenznummer

   • und schickt sie zu anderen Repliken

     
     

2. passiv

   • die Daten werden wieder verschickt?

• für sequentielle Konsistenz

• jedes Data-Item had “primary”

  = zentrale Maschine, die Schreiboperationen ausführt

  • propagiert Schreiboperationen zu anderen Servern

  • gibt Operation frei, wenn alle Server mit ok geantwortet haben

Zwei arten

1. Remote-write protocols

• primary ist fest auf remote server

• lesen geht auch lokal, schreiben nur dort

• auch "primary-backup protocol"

• schreiben geht an zentralen primary - der updated alle repliken -> die geben ok -> ok geht zurück an ursprünglichen Client

• Problem: Update dauert zu lange

  • implementiert als Blockierung

• b) local-write protocols

  • lokale Repliken werden geschrieben

  • variante des primary-backup protocols

  • primary-Kopie wandert zwischen Prozessen, die schreiben wollen

• nutzt Wahlen - Clients fragen um Erlaub

• es gibt N Replikate einer Datei auf ebensovielen Servern

• Clients wollen DateienLesen oder Schreiben

Varianten:

1. Clients fragen immer N/2 + 1 Server

• zum Schreiben - dann ist ok zu schreiben und neue Versionsnummer für updated file

• zum Lesen: schauen, ob alle Server die gleiche Versionsnummer haben - dann ist es die aktuellste Version

1. read-quorum : N_R und write-quorum: N_W

2 Regeln:

• 1) N_R + N_W > N

  • vermeidet read-write-Konflikte

  • immer aktuellste Version, weil ein Server beim Schreiben dabei gewesen sein muss

• 2) N_W > N/2

  • vermeidet write-write-Konflikte

  • kein zwei disjunkte Teilmengen zum Schreiben

1. ROWA (Read-one, Write-all)

   • gute Leseperformanz (man braucht nur eine Kopie finden)

   • schlechte Schreibperformanz

   • kein Schreiben mehr möglich, wenn ein Server ausfälle

• erkennt Inkonsistenzen

• bei statischen Lösugnen:

  • Compiler macht Analyse vor Ausführung

• bei dynamischen Lösungen:

  • in VS - wie im Buch

  • Inkonsistenzen bei Runtime erkannt

  • z.B. bei Server schauen, ob Daten im Cache geändert wurden

3 Arten:

• 1) Vor Transaktion

• 2) Während Transaktion

• 3) Nach Transaktion bei Commit

b)

• entscheidet, wie Caches konsistent gehalten werden

• einfachste Lösung: geteilte Daten darf man nicht cachen

  
  

• wenn man Daten cachen darf - 2 Möglichkeiten

  • 1) Daten werden modifiziert? -> Server schickt Invalidation zu allen Caches

  • 2) Update verbreiten

• Clienten können ihren Cache direkt modifizieren

• Updates werden zum Server geschickt

• meist in verteilten Datei-Systemen

• wie write through

• nur mehrere Schreib-Zugriffe erlaubt

ergeben sich aus dem Prozess der Zusammenarbeit

1. Isolation

   • Benutzer arbeiten wie alleinige Besitzer an gemeinsamen Daten

2. Integration

   • Änderungen müssen für Gruppe integriert werden können

3. Aktualität

   • leicht alte Daten zu aktualisieren

   • und akutelle Daten zu erhalten

4. Nachvollziehbarkeit

   • alle früheren Zustände sind verfügbar und vergleichbar

   • Veränderungen mit Namen und Datum gespeichert

5. Gruppenwahrnehmung

   • Benutzer über Aktivitäten anderer informieren

= gemeinsamer Datenspeicher

• alte Versionen werden nicht gelöscht

• Veränderungen resultieren in neuer Version eines Repositories

• jede Version hat Vorgänger

• aktuellste Version ist am Ende

• Aufspaltung ist möglich:

  • Branch

    = Version hat mehrere Nachfolger

• mehrere Versionen verbinden:

  • merge

1. Checkout/ Update

   • Benutzer wählt zu bearbeitetende Datei

   • meist komplettes (Teil-)Projekt

   2 Arten:

   • Checkout

     • kopiert neues Projekt in lokalen Arbeitsbereich

   • Update

     • lokale Kopie auf neuesten Stand bringen

2. Bearbeiten = Daten lokal verändern

   • nur Benutzer kann darauf zugreifen (Isolation)

3. Commit

   • (Integration)

   • veränderte Daten ins Repository übertragen

   • neue Versionen der Dateien mit Zeitstempel und Zusatzinformationen speichern

   • Versionen werden mit Vorgängern verknüpft (Nachvollziehbarkeit)

CVS = "Concurrent Version System"

• checkout [projektname]

  • holt aktuelle Version des gesamten Projekts in lokalen Arbeitsbereich

• add [filename]

  • Datei zum Repository hinzufügen

  • erzeugt nur Dateieintrag

• commit [filename] [version comment]

  • erstellt neue Version einer Datei auf CSV-Server

• status [filename]

  • findet Abweichungen lokaler Version von Repository-Version

  • Ergenisse:

    • a) Up-to-Date

    • b) Locally Modified

    • c) Locally Added

      • lokale Version wurde hinzugefügt

    • d) Needs Update

      • Datei wurde von anderem Benutzer auf Server verändert

• diff [filename]

  • listet genaue Unterschiede zwischen zwei Versionen auf

  • z.B. zwischen aktueller und lokaler Kopie

• update [filename]

  • aktuellste Version einer Datei lokal laden

• log [filename]

  • listet für alle bisherigen Versionen der Datei:

    • Versionsnummer

    • Änderungsdaten

    • Speicherungskommentare

• branch [filename]

  • erzeugt Abzweigung aus Versionliste

  • Liste wird zu einem Versionsbaum

  • bei vielen Verzweigungen lieber GIT verwenden

• man kann nur neue Version einchecken, die auf der gerade aktuellen beruht

• prüft lokale Versionnummer mit der im Repository

• wenn unterschiedlich, muss man merge

  • ist Nebeneffekt vom update-Befehl

• kein merge bei commit möglich!

• wenn man bei lokalem Merge Fehler erhält

• geht nur bei Textdateien

• bei Binärdateien kann man nur feststellen, ob sie gleich sind oder nicht

Es überprüft zeilenorientiert

• wenn eine Zeile geändert wurde wird die nächste gleiche gesucht

• alles andere dazwischen ist anders

zwischen:

• lokaler Version

• aktueller Version

• gemeinsamer Vorgängerversion