Verteilte Systeme - HTWG Konstanz - AIN 5
Karteikarten für das Fach Verteilte Systeme von Prof. Dr. Haase
Karteikarten für das Fach Verteilte Systeme von Prof. Dr. Haase
-
- 1 / 104
-
Lernkarten
-Daten im System = Sammlung von Objekten
-jjedes logische objekt wird durch reihe physischer objekte realisiert(Replikate)
-Replikate müssen nicht jederzeit absolut identisch sein
-replikationsintelligenz kann in objekten platzirt sein oder auüerhalb(middleware)
-->anwendungsprogrammierer können frei von überlegungen zur replikation sein
-legt fest in weclher Reihenfolge die verteilten Schreiboperationen von lesenden Prozessen gesehen werden
-Ideal: Prozess der REadausführt liest wert des letzten write
-Aber: was wenn keine globale Uhr?
-Lösung: verschiedene Konsistenzmodelle(nicht nur strikt)
-Datenzentrierte: Sicht des Datenspeichers, geegnet für parallele Schreibzugriffe
-Clientzentriere:sicht des client,weniger starke annahmen,keine gleichzeitigen updates
-Strikte Konsistenz
-sequentielle Konsistenz
-Kausale Konsistenz
-Fifokonsistenz
-Jedes Read liefert als Ergebnis den wErt der global letzten writeoperation
-->konsequentestes Konsistenzmodell
-->benötigt absolute globale Zeit
-->nicht implementierbar!
-Jede gültige Kobination(Reihenfolge der Operationen pro Prozess bleibt erhalten) von Read- und Write-Operationen ist akzeptabel,solange alle Prozesse dieselbe Folge sehen
-schwächeres modell, implementierbar
-zeit spielt keine rolle
-->Gummibandmetahper(Zeit spielt keine Rolle solange interne Reihenfolgen erhalten bleiben)
-Nur writeoperationen die potentiell in einem kausalen Verhältnis stehen müssen bei allen Prozessen in der selben Reihenfolge gesehen werden. Für nicht in dieser Beziehung stehende Operationen ist die Reihenfolge auf unterschiedlichen Rechner gleichgültig
-->schwächer als sequentielle
--"happened before Relation
-Schreibzugriffe einzerlner Prozesse werden von allen Prozessen in korrekter Reihenfolge gesehen, Schreibzugriffe verschiedener Prozesse können in unterschiedlicher Reihenfolge gesehen werden
-->abschwächung der kausalen Konsistenz
-Implementierung muss Reihenfolge nur pro Prozess sichersteleln
Vorteil: einfach, vollständig nebenläufiges lesen/schreiben,lokaler proz nicht aufgehalten
Nachteil: schwach konsistentes Verhalten
-verteilter datenspeicher der nur von wenigern prozessen geschrieben aber vielen gelsenen wird
-->keine schreib schreib konflikte, nur lese /schreib konflikte
-Häufig einsatz von Leserepllikas(Caches)
bei clientzentrierten Konsistenzmodellen
-Wenn lange Zeit kein Update durchgeführt wird werden alle Replikas(Caches) nach und nach konsistent
Probleme:
-kann auftreten wen client replika wechselt
-->mobiler client updatet replika,wechselt ort, liest veraltete daten von anderer
-benutzer stellt inkonsistenz fest!
Lösung:
clientzentrierte Modelle bei denen für jeden Clent Konsistenz garantiwert wird, jedoch nicht für nebenläufigen Zugriff durch mehere Clients
-Konsistenz für monotones Lesen: wenn prozess den Wert einer Variable x liest wird jede weitere readoperation desselben prozesses denselben oder einenen neuerern WErt von x liefern
-->schreiboperationen müüssen auf anderen replikas vor dem nächsten lesen durch prozess wiederholte werden
Konsistenz für monotones Schreiben: Eine Schreiboperation eines Prozesses in eine Variable x wird abgeschlossen bevor der selbe Prozess X erneut schreiben kann
-->gilt über verschiedene lokale kopien hinweg!
-Schreiboperation von P auf x1 muss auf S2 vor dem nächsten Schreiben von x durch P wiederholt werden
-Ergebnis einer Schreiboperation von x wird für eine anschließende Leseoperation von x desselben Prozesses stets sichtbar ein
-ohne: pw für onlieshop geändert, zugang erst nach gewisser zeit möglich
-Eine schreiboperation eines Prozesses von x, die auf eine Leseoperation von x desselben Prozesses folgt, findet auf demselben oder einem aktuelleren WErt von x statt
->schreiboperationen diefür das Lesen von x1 relevant waren, müssen auf S2 vor dem nächsten Schreiben von x durch P wiederholt werden
-Optimierungsproblem:finde k beste von n möglichen standorten
--Qiu et al
--Radoslavov et al
--Szymaniakt et al
-berücksichtigt Cleintstandorte
-bestimmt entfernung von clients zu standorten(latenzzeit,bandbreite)
-platziert nach und nach server auf denjenigen verbliebenen standort der im durchschnitt allen clients am nächsten
-Aufwand: O(N²)
-->ungeeignet für Serverplatzierung im Fall von Flash Crowds, d.h. plötzlich gehäufte anfragen nach bestimmten Webseiten
-ignoriert Clientstandorte
-berücksichtigt staddessen Topologie des internets
-internet aus Autonomen Systemen(AS) d.h. Systeme die dasselbe Routingprotokoll verwenden, von einer Organisation verwaltet werden
-platziert 1.server in größtem AS,auf Router mit den meisten Verknüpfungen, 2.Serverin zweitgrößtem As,..
-fpr gleichmäßig verteilte Clients genauso gut wie qiu et al
-Aufwand O(N²) -->ungeeignet für schnlelle Platzierungsberechnung
-berücksichtigt Clentstandorte
-teilt Netz in Zellen auf
-sucht ClientCluster(Zellen mit vielen Clients)
-platziert Replikatserver in K größten Clustern
-Qualität hängt von Zellengröße bei Clustersuche ab
-ideale Zellengröße lässt sich aus druschn. Entfernung zwischen zwei knoten und k berechnen
-->geeignet für schnelle Platzierung bei Flash Crowds
-Permanente Replikate
-Server initiierte Replikate
-Client initiierte Replikate
-Grundlegende Menge von REpliakten, meist beim Deesing eines Datenspeichers schon angelegt
-entweder transparent repliziert(client merkt nix von)
oder mirroring (client scuht bewusst replikation aus)
-meist geringe Anzahl
-kurzfristing initiiert bei hohem Bedarf, meist in der Netzregion wo bedarf auftritt
-schwierig: wann und wo sollen replikate erzeugt werden?
-Algorithmen verwenden dazu: name gesuchter dateien, anzahl/Herkunft Requests
-kann permanente Replikas ersetzen wenn garantiert, dass jedes Datum immer von mindestens einem Server vorrätig gehalten
-meist als (Client)cache bezeichnet
-management des chaches dem client überlasse,server kümmert sich nicht um Konsistenzerhaltung
-Zweck: Verbesserung Datenzugriffszeiten
-daten meist für begrenzte Zeit gespeichert
-Cache meist auf Clientmaschine üplaziert oder in näche vieler Clients(z.b. im LAN)
-Client führt Update generell auf einer Replika durch
-das update muss an alle anderen Replikas weitergegeben werden
-verschiedene design gesichtspunkte für entsprechende Protokolle:
-was wird zu den anderen Replikaten propagiert?
-pull,push oder leases eingesetzt?
-unicast oder multicast?
-Benachrichtigung das Update vorliegt
-->invalidation Protocols
-->wenig Bandbreite
-->gut wenn viele SChreib vs wenig lese operationen
-Transferiere Änderungsoperation zu anderen Servern
-->geringe Bandbreite
-->mehr rechenleistung auf Servern
Terminologie: Server= änderung vorgenommen, client: server der weiteres replikat beherrbergt oder Client
-Updates werden auf Initaitive des Servers verteilt
-Clients schicken keine Requests nach Daten
-Server muss Liste aller Clientcaches für jedes Datum aktuell halten
-Gut wenn hoher grad an konsistenz notwendig oder viele lese vs wenig schreiboperationen
Terminologie: Server= änderung vorgenommen, client: server der weiteres replikat beherrbergt oder Client
-Server/clients fragen nach neuen Updates für Daten
-oft von Clientchaches verwendet
-gut bei wenig lese vs viele schreiboperatioen oder wenn geringe Kohärenz erfoderlich
-längere Antwortzeiten bei Cache Miss
Terminologie: Server= änderung vorgenommen, client: server der weiteres replikat beherrbergt oder Client
-Hybrid aus Push and Pull
-lease hat bestimmte Laufzeit
-während Laufzweit überträgt Server Änderung per Push
-danach muss client änderungen per pull abholen
-client kann neuen lease beantragen
-erlaubt dynamisches umschalten zwischen pull und push
-kriterien für lease-laufzeit:
-->änderungshäufigkeit: änderung selten: langes lease
-->Nachfragehäufigkeit: client fragt oft nach -->langes lease
-->serverlast: serverlast gering -->lange Leases
-sende Nachricht mit demselben Inhalt an jeden Replikaserver
-->besser zu pull, wo immer nur ein Server nach einer neuen Version eines Datums fragt
-sende nur eine Nachricht, überlasse dem Netz die verteilung
-->effizienter als unicast (insofern implementiert=
-->meist mit pushprotokollen verbunden, server als multicastgruppe organisiert
-datenzentrierte Konsistenzprotokolle
-Clientzentrierte Konsistenzprotokolle
-wei Ansätze:
urbildbasierte Protokolle
-->remote-write-protokolle
-->local-write-protokolle
protokolle für relizierte schreibvorgänge
-aktive replikation
-quorum basiert
-wenn alle writeoperationen immer nur an eine Kopie gehen, kann man unterscheinen ob die Primärkopie
-immer am selben entfernten Platz bleibt: Remote Write Protokolle
-zu de schreibenden Client verlagert: Local Write Protokolle
-alle Updates auf einem entfernten Urbildserver
-Leseoperationen auf lokalen Kopien
-Wenn client Datum x ändern möchte:
-->lokaler Server S leitet Änderung an Urbildserver U weiter
-->U macht änderung, informiert alle Kopien
-->Jede Kopie macht Änderung, sendet ACK an U
-->Nachdem alle ACKs eingetroffen: U sendet ACK an S
Problem: Performance(darum non-blocking Update -->achtung: fehlertoleranz!)
-beste umsetzung für sequentielle Konsistenz
-Jeder Prozess, der ein Update ausführen will, lokalisiert das urbild und bwegt dieses an seinen eigenen platz
-gutes Modell auch fpr mobile benutzer:
-->hole urbild ab, breche verbindung ab, arbeite, baue später veindung wieder auf, keine zwischenzeitliche änderung durch andere prozesse,andere prozesse können weiterhin lesen
-writeoperationen können auf belibeigen Replikaten ausgeführt werden
-muss entschieden werden welches richtiger wert eines datums
Zwei Ansätze:
-aktive replikation: operation an alle Replikas weitergeben
-Quorumbasiert: abgestimmt, mehrheit gewinnt
-Jede Replika besitzt Prozess der Updates durchführt
-Updates meist als Operation propagiert
-wichtigestes Problem: alle updates auf allen Replikas in selber Reihenfolge!
-->multicast mit toater Ordnung benötigt(z.b. LamportUhr)
- skaliert schlecht
-alternativ: zentraler Prozess, übernimmt Sequentalisierung
-Clients müssen vor Lese/Schreiboperation Erlaubnis meherer Server einholen
-Jeder schreibvorgang W bekommt global eindietuge id
-pro clientc zwei Reihen von schreibvorgängen überwachen
-->Lesevorgangsreihe: Schreibvorgänge(aller)die für Lesevorgänge von C relevant
-->Schreibvorgangsreihe: Schreibvorgänge von C
(konsistenzerhaltungsprotokolle fr konsistenz für monotones lesen, monotones schreiben,readyourwrites,wiritesfollowreads) nach diesem SChema
: Lese- oder Schreiboperation
Lese oder Schreibvorgangsreihe
-Sobald client c lokale Operation auf Server S durchfprt bekommt S Cs
-S prüft ob alle relevanten Operationen aus lokal durchgeführt wurden
-Falls nein: kontaktiert S die Server die fehlende Pperationen aus durchgefphrt haben und hold diese nach oder die Operation wird an einen solchen Server delegiert
-Nach erfolgter Operation wird diese ggf. in Reihe aufgenommen
-Vertraulichkeit(Confidentially) : System gibt Infos nur an autorisierte Parteien (lesender Zugriff)
-Integrität(Integrity): System lässt Änderungen nur durch autorisierte Parteien zu (schreibender Zugriff)
