= Ausarbeitung Prüfungsfragen Verteilte Systeme VO (Göschka) WS10 = Dies ist eine stichwortartige Ausarbeitung der Prüfungsfragen, die ich für mich selbst verfasst habe. Die hier skizzierten Antworten sollten ausformuliert bei der Prüfung für eine relative gute Note reichen. Ohne Vorwissen ist diese Zusammenfassung wahrscheinlich eher nicht geeignet. === Grundlagen, Konzepte === 1) verteiltes sys: unabhängige computer kommunizieren über netzwerk und formen ein einheitliches system aus sicht des benutzers design ziele: openness transparency reliability, fault tolerance extensibility concurrency res sharing fallstricke: bandwidth is infinite network is reliable one admin 0 latency network homogenous network secure static topology transport cost 0 2) transparenz: abstraktes service benutzen kann, ohne konkrete maschinen/implementierung/verteilung zu kennen standardisierete arten: access: hides data representation, type of access location: migration: hide that a res may move relocation: migration while in use replication: hide several copies concurrency: hide that other users access res failure: hide failure & recovery persistence: hide whether in mem or disk nachteil: es kann zu viel info versteckt werden. es kann günstig/notwendig sein, auf aspekte der verteilung direkt zuzugreifen, was transparenz verhindern würde. vollständige transparenz ist extrem schwer zu implementieren (viele schichten der indirektion) -> performance-- 3) openness offenheit der services (interfaces, protokolle). interoperabilität erreicht durch standards diese müssen _vollständig_ und _implementierungsneutral_ sein trennung policy - mechanismus 4) probleme & lösungsansätze für scalability scalability: - size (number users, resources) -> zentrale services/daten/algos überlastet - geographisch -> latenz - administration -> kollaboration von verschied. orgas schwierig (resourcen, billing, management, security) lösungen: - dezentralisierung: - kein system hat vollständige info, lokale entscheidungen - no single point of failure - replikation: last verteilen - latenz: - asynchronität - weniger kommunikation - hierarchische strukturen: administration klar verteilen 5) vertikale verteilung (N-schichten-system): separation of concerns. eine schicht pro aspekt (bsp: präsentation, programmlogik, resourcen) jede schicht kommuniziert mit der darunterliegenden und bietet der darüberliegenden ein interface. die einzelnen schichten können beliebig verteilt sein. grundvarianten client/server: thin client (1-tier): alle schichten beim server. skaliert schlecht. 2-tier: client macht nur präsentation, server den rest thick client: server stellt nur resourcen bereit , client macht die arbeit 3-tier: präsentation, logik und res separat java applet: thick/thin client? thick. (logik und präsentation beim client) 6) horizontale verteilung: mehrere maschinen erledigen die gleiche arbeit. meistens zur lastverteilung/ausfallsicherheit. design-fragen: konsistenz physische einschränkungen (bsp: es muss auf zentralen daten gearbeitet werden) größe der komponenten: kleiner: flexibler, bessere wiederverwendbarkeit, mehr traffic zusammenhang vertikal: kein direkter zusammenhang; vertikal & horizontal können kombiniert werden, sind aber prinzipiell unabhängig === kommunikation: middleware, rpc === 1) grundprinzip iso-osi: klassisches schichtenmodell (separation of concerns, ..) physical - link - network - transport - session - presentation - application bezug zu tcp/ip: ip ~ network tcp ~ transport warum transport layer protokolle für VS nicht ausreichend? eingeschränkte steuerungsmöglichkeit nicht ausreichend abstraktion/transparenz keine session, authentifizierung, datenrepräsentation, verschlüsselung 2) middleware: runtime infrastructure above transport layer programming abstraction anforderungen: transparency openness flexibility scalability maintainability interface definition concurrency control services: communication facilities naming (for location transparency) persistency distributed transactions replication security (encryption, authentication) middleware - architectural styles: je nach architekturstil (schicht-, objekt-, daten-, event-basiert, ...) gibt es verschiedene middlewares (kann auch in einer kombiniert sein). middleware muss architekturstil unterstützen. 3) wie flexibilität der middleware, zusammenarbeit (middleware, applikation) erhöhen? interceptoren: hook in middleware, an dem die app eigenen code platzieren kann. adaptivität: anpassbare middleware austauschbare komponenten reflektion self-management: middleware passt sich selbst an bsp: parameter dynamisch je nach situation automatisch setzen rückkopplung (feedback control loop) 4) rpc = funktionsaufruf in einem entfernten programm middleware fängt aufruf im client stub auf dieser sendet ihn über netzwerk an server stub (inkl opt parameter konvertierung) dort wird die funktion aufgerufen resultat nimmt selben weg zurück. aus der sicht der apps ist alles lokal. 5) wie variablen übergeben. handhabung, probleme: by value: trivial bei rpc by reference: nicht direkt möglich bei rpc. by copy/restore: kann by reference bei rpc teilweise simulieren problem: copy/restore != by reference: - nicht mögl bei großen daten - concurrency (wenn während copy/restore-call daten lokal verändert werden) parameter marshalling: verpacken der parameter in netzwerkpacket-taugliche daten. durch heterogenität ev. verschiedene datenformate notwendig (zeichensätze, endianness) 6) client/server rpc implementierung. idl? in einer idl wird das interface der funktion sprachunabhängig definiert. davon kann automatisch der server- bzw. client-stub in beliebigen programmiersprachen generiert werden. ziele einer idl: flexibilität einfachheit interoperabilität (idl-compiler gleicht plattformunterschiede aus) binding: der client-stub muss für einen rpc mit einem server-stub verbunden sein finden des servers-endpunkt (ev. directory server) und verbindung zu server-endpoint = binding server muss vorher bekannt/registriert sein. 7) arten asynchroner rpcs. typen der kommunikation (persistent/transient, sychron/asynchron) - auf ergebnis warten (=synchron) - auf empfangsbestätigung warten - gar nicht warten bei zweiwegigen asynchronen rpc wird client bei empfang des resultates unterbrochen transient: nachricht wird nicht übermittelt, wenn empfänger nicht online persistent: middleware speichert nachricht, wenn empfänger nicht online, und übermittelt später synchron: sender wartet auf ergebnis asynchron: !synchron === kommunikation: RMI, messaging === 1) grundprinzipien verteilter objekte, rmi objekte können sich auf verschiedenen maschinen befinden, werden aber aus sicht des programmierers gleich behandelt interface des objektes steht durch obj-proxies an clients zur verfügung, obwohl das objekt am server lebt. rmi: wie rpc, nur dass methoden auf objekte aufgerufen werden, die remote sind. client bindet nicht an server, sondern an ein objekt am server. proxy, skeleton: proxy: "client stub". verweist auf ein remote obj. läuft lokal auf client, hat selbes interface wie remote obj. aufrufe werden an skeleton weitergeleitet. skeleton: "server stub". ruft methoden an serverobjekten lokal auf, nach requests von proxies. compile-, run-time objekte: compile: instanz einer bestimmten klasse (typ und interface). language dependent. bestimmt zur compile-zeit. client- & server-stub automatisch generierbar runtime: unabhängig von progsprache. obj dynamisch beliebig konstruiert. kann object adapter (wrapper) verwenden, um implementierung an interface zu binden (insb., wenn implementierung nicht oop). persistente, transiente objs: persistent: lebt unabhängig von prozessen. wird serialisiert, wenn der prozess nicht läuft. transient: der managende prozess bestimmt die lebenszeit 2) binding bei rmi: wie bei rpc muss der server auffindbar sein. implizit: aufrufe auf globale referenz; binding transparent durch middleware. explizit: lokale referenz wird explizit durch einen funktionsaufruf an eine entfernte referenz gebunden zusammenhang zwischen verschiedenen obj reference arten: obj muss eindeutig identifizerbar sein. prinzipieller aufbau: netzwerkadresse + obj identifier netzwerkadresse kann auch ein directory sein, in dem die echte adresse nachgeschlagen wird. obj identifier: port, obj name, service name vgl corba/java bzgl objreferenzen: corba: plattformunabhängig; spezielle interoperable object reference (ior); java: plattformspezifisch (java-vm) 3) static/dynamic invocation: static: zur compile-zeit steht fest, welche methode aufgerufen wird. bsp: obj.foo()) interface change => recompile dynamic: methode zum aufruf wird zur laufzeit bestimmt. bsp: invoke(obj, "foo") braucht lookup. anwendungen: inspection (reflection), frameworks. 4) parameter passing. inwiefern rmi durch oop besser als rpc: serialisieren: wie by value. oder objreferenz statt obj schicken. wird dieses obj verwendet, werden die aufrufe auf die ursprüngliche maschine weitergeleitet. da die objektreferenz alle daten zur lokalisierung eines objektes beinhalten, können diese objekte auch weitergeschickt werden. 5) grundprinzipien (kategorien) message-orientierter kommunikation inkl corba basiert auf nachrichten (keine transparenten aufrufe) transistent/persistent; synchron/asynchron; 2 unterschiedliche methoden für asynchrone rmi in corba messaging: 1: client schickt request; bei response wird callback der application aufgerufen 2: client schickt request; response vom server wird gespeichert; client kann pollen, ob eine antwort da ist. 6) message-oriented middleware: modell & architektur message queuing system persistent, asynchron. nachrichten werden nur in queue gestellt, keine info über abholung. sender und receiver haben queuing layer, auf den die app zugreift. dieser layer übernimmt zustellung, wenn beide knoten online sind. message relay stations auch mögl (wie postamt, nachrichten werden gespeichert, bis sie weitergeleitet werden können) put: nachricht in queue einfügen get: nachricht blockierend abholen poll: nachricht nicht blockierend abholen notify: callback für nachrichteneingang installieren einsatzzwecke, vor-/nachteile, message broker, eai bsp: mail, groupware message broker kann nachrichten in beliebigen formaten bereitstellen und so interoperabilität schaffen (besonders legacy systems) für eai interessant: loose kopplung (große systeme). nachteile: langsam 7) stream-oriented communication: keine einzelnen pakete, sondern fortlaufender strom an daten (z.b. TV) probleme: muss oft auf paketbasierte verbindungen gemapt werden, wo reihenfolge, timeliness und regelmäßigkeit nicht garantiert ist. simple vs complex streams: mehrere zusammengehörige, oder 1 stream (z.b. audio + video) 3 arten: - asynchron: zeit egal (filedownload) - synchron: hat maximale verzögerung (überholen egal) (sensordaten) - isochron: min und max verzögerung QoS: qualitative anforderungen soc hat zeitliche anforderungen an das netzwerk, z.b.: - max verzögerung - max jitter (verzögerungsvarianz) - min bit rate - max verzögerung bei sessionaufbau - max round-trip delay gegen jitter kann ein buffer verwendet werden. einzelne dateneinheiten des stroms können auch auf verschiedene pakete aufgeteilt werden (interleaved transmission). wenn dann ein paket nicht rechtzeitig ankommt, kann der codec das vllt interpolieren (was nicht gehen würde, wenn ein ganzer abschnitt verloren geht) === Operating System Support === 1) prozess: wird vom kernel verwaltet. eigener speicherbereich und resourcen. eher aufwendig zu erstellen und verwalten. thread: mehrere threads befinden sich in einem prozess, der kernel sieht sie nicht. alle resourcen werden geteilt. kann einfach erzeugt und verwaltet werden. schneller context switch. probleme beim scheduling, da der kernel die threads nicht sieht (z.b. blockierung bei syscalls) multithreading: safety: durch resourcensharing können konflikte und race conditions auftreten. threads können speicher anderer threads überschreiben. liveness: deadlocks vermeiden performance: nicht zu viel context switchen und locken threads in verteilten systemen: verteilungstransparenz (verbergen von netzwerklatenzen) eigener thread für jede remote verbindung load balancing 2) verteilung auf clientseite? mehrere threads können die verschiedenen kommunikationspartner lokal widerspiegeln. interaktion mit user und remote servern gleichzeitig. UI in VS? am besten in eigenen thread, sonst blockierung bei rpc. bei thin clients kann auch der server die UI darstellen. wie verschiedene arten von transparenz? access: stub (hat interface vom server, versteckt konkrete details und eigentliche kommunikation) location: naming & (re)-binding replication: proxy nimmt anfragen entgegen und verteilt auf replikas failure: retry, redirect, cache concurrency: transaction monitors (intermediate servers) 3) design decisions am server: iterative/concurrent: hängt von performanceanforderung ab server interrupt/out-of-band: client unterbricht server oder hat extra-kanal stateful/stateless naming/binding stateful - stateless inkl bsps stateless: jede anfrage wird immer gleich behandelt, es ist egal, was vorher war. keine client info speicherung. bsp: http stateful: ältere kommunikation beeinflusst aktuelles verhalten; server speichert client-daten (z.b. login). bsp: fileserver mit zugriffsberechtigungen skizze: architektur und funktionsweise eines multithreaded servers. requests gehen an einen dispatcher thread, der worker threads erzeugt. diese kommunizieren mit den clients. was ist bei multithreading vom entwickler zu beachten: nebenläufigkeit: synchronisierung. 4) objekt-server: ermöglicht zugriff auf objekte. diese können auch nach verschiedenen strategien und policies erzeugt werden. invocation-arten: erzeugung: lazy/eager eigener thread für jedes objekt pool von worker-objekt-threads code sharing: objekte nur einmal laden eigener speicherbereich oder shared objekt-adapter: implementiert activation/invocation policy gruppiert objekte nach policy generisch (kennt interface der objekte nicht) 5) code migration: ausführbaren code im netzwerk verschicken eine andere sichtweise auf verteilung früher: rechenleistung balancieren heute: kommunikation vermindern (e.g. code zum client schicken und dort ausführen) problem: lokale resourcen vorteil: flexibilität (fehlende softwareteile am client einfach nachliefern) nachteile: security, heterogene systeme strong mobility: code wird während ausführung übergeben. inkludiert laufzeitdaten (stack, programmzähler, ...). weak mobility: code wird "kalt" übergeben. bsp: js 6) virtualisierung inkl bedeutung für code migration heterogene umgebungen: interface erweitern oder ersetzen, um anderes system zu imitieren vorteile: - legacy systems portieren - security durch isolation - virtualisierte OS leichter handhabbar als echte maschinen heterogenität ist ein großes problem für VS. durch virtualisierung kann auf verschiedenen maschinen eine einheitliche plattform geschaffen werden. hier kann beliebiger code migriert werden, da die plattformen ident sind. 2 architekturarten von virtual machines: process virtual machine: runtimesystem in einem prozess eines betriebssystems (bsp: JVM) virtual machine monitor: schicht zur hardwareabstrahierung, auf der betriebsysteme aufsetzen (bsp: VMware) === Naming & Discovery === 1) name: string referring to an entity (meistens human readable) entität kann verschiedene und wechselnde access points haben, der name verweist aber immer auf die selbe entität location independent: unabhängig von adresse identifier: ungefähr: "eindeutiger name" refers to at most 1 entity (meistens maschinenlesbar) jede entität hat höchstens einen identifier identifier bezieht sich immer auf eine entität (kein reuse) address: name eines access points access point: ein zugriffspunkt (handle) auf eine entität (bsp: telefon ist zugriffspunkt auf mensch) direkte verwendung der adresse verhindert location transparency addresse kann nicht weiter aufgelöst werden, es weist eben auf eine "konkrete" entität 2) namespace: räume, innerhalb deren namen eine bestimmte bedeutung haben räume können hierarchisch organisiert sein (vgl. baumdarstellung) closure mechanismus anhand eines bsps: um in namensräumen navigieren zu können, muss ein startpunkt bekannt sein dieser muss außerhalb des namenraums zugänglich sein (den startpunkt kann man nicht durch den auflösemechanismus bestimmen, da die auflösung den startpunkt benötigt) bsp: unix filesystem: startpunk: / adresse dieses punktes ist im superblock des logischen laufwerks kodiert. 3) schichten der verteilung von namespaces: flache namen ungeeignet bei vielen knoten => hierarchische einteilung eine schicht teilt den namensraum in kleinere teile, welche von unteren schichten gehandhabt werden typische aufteilung: - global: (vgl. top level domain) erste, grobe unterteilung daten eher konstant (ändert sich nur bei großen änderungen der unterteilung) => gut replizierbar, auch cachebar durch clients - administrativ (vgl. second level domain) caching durch clients mögl, eher weniger replikate - management (vgl. pfad am webserver bei urls) sehr viele einträge relativ wenige zugriffe pro eintrag, verglichen mit höheren schichten im normalfall kaum replikation/caching iterative namensauflösung: 1. client fragt ns 2. ns gibt einen anderen ns zurück, der näher bei der entität liegt 3. goto 1 bis der ns die gesuchte entität zurückgibt rekursive auflösung: 1. client fragt ns_1 2. ns_i fragt ns_(i+1) 3. goto 2 bis entität gefunden 4) dns erklären inkl ablauf anhand dns database (resource records): mapping domainname -> ip baumartig organisiert domain: subbaum domain name sind pfadangaben im baum knoten speichern daten in resource records rr besteht aus aus name, record type und record value record type können u.a. sein: host (ip) nameserver, die mehr informationen zu diesem namen haben ptr für reverse lookup reverse lookup: ip -> domainname zone-transfer: übertragung von rr auf andere ns zur ausfallsicherheit & performancesteigerung 5) directory service bzw attribute-based naming: keine auflösung von namen, sondern von attributen ("yellow pages") prinzipieller aufbau von X.500 inkl ldap-implementierung: hierarchisches directory service basiert auf osi soll effektives suchen auf basis von beschreibungen ermöglichen 1 riesiger baum, jede schicht für daten darunter verantwortlich einteilung: country -> organisation -> organisational unit -> common name jeder knoten hat mehrere attribut-wert paare beinhaltet informationen über organisationen ldap: einfache, effiziente implementierung eines directory services abgeleitet von X.500 baut auf tcp anstatt osi auf 6) location service in flachen namensräumen, grundprinzip möglicher lösungen. bsp: p2p namen beziehen sich auf entitäten. location service: name auf adressen mappen hosts müssen announce & discovery von services und resourcen unterstützen oft wichtig: ttl (leases) mobility: lokalisierung von knoten, deren adresse sich ändert discovery: finden von resourcen vor-/nachteile von forwarding pointers: einfaches prinzip probleme wenn ketten länger werden (1 ausfall zersört ganze kette) home-based apporaches für mobile geräte: es gibt einen fixen ort, der die adresse eines mobilen gerätes kennt das gerät hält dort sine adresse aktuell jeder kann es durch diesen fixen ort finden === clocks, agreement === 1) wozu uhrensynchronisation: systeme mit bezug zur zeit brauchen uhrzeit synchronisation mit real-world (external) synchronisation miteinander (internal) festlegung von reihenfolge von operationen ntp: externer zeitgeber mehrere anfragen, die mit geringster abweichung wird verwendet korrektur erfolgt durch verlangsamen oder beschleunigen der uhr, kein hard set 1. client sendet request, merkt sich zeitpunkt 2. server antwortet mit seiner aktuellen zeit, schickt dauer der beantwortung des requests mit 3. client: muss zeit berechnen, die das letzte pakete gebraucht hat. d = ((antwort erhalten) - (anfrage abgeschickt) - (dauer beim server)) / 2 implizite annahme, dass hinweg genauso lang wie rückweg dauert aktuelle zeit = (zeit, die server geschickt hat) + d berkeley algo: mehrere uhren einigen sich auf eine gemeinsame zeit 1. time daemon fragt alle maschinen nach zeit 2. alle maschinen antworten 3. time daemon errechnet mittelwert, und schickt differenz der zeit der maschine zur errechneten zeit aus ad 1, 2: implizite annahme, dass alle pakete gleich lang brauchen ad 3: nur differenz wird geschickt, da bei absoluter zeit nicht klar ist, wie lange das paket mit dieser zeit gebraucht hat problematik bei synchronisation von physical clocks: natürliche phänomäne nicht konstant (erdumlauf der sonne ) 2) warum logical clocks inkl unterschiede zu physical clocks: oft ist es nicht wichtig, wann etwas passiert ist, sondern nur die reihenfolge. dazu braucht man keine schwer zu synchronisierende physical clock. happened-before: wenn eine happened-before beziehung (a -> b) vorliegt, ist a definitiv vor b passiert. der umkehrschluss ist nicht gültig. partielle ordnung (nicht geordnete events sind logisch concurrent) hat ähnlichkeit zu möglicher physischer kausalität. transitiv konkret: - wenn a in einem prozess vor b, dann a -> b - wenn a eine nachricht an einen anderen prozess schickt, und dort später c passiert, dann a -> c - ansonsten: concurrent lamport-timestamps: implementiert happened-before (a -> b) => L(a) < L(b) umkehrschluss gilt wieder nicht jeder knoten (prozess) hat einen counter vor jedem event (berechnung, senden, empfangen) wird dieser erhöht der aktuelle wert wird bei jeder nachricht mitgeschickt beim erhalt einer nachricht: LC = max( local LC, received LC ) 3) nachteil der lamport-timestamps: aus (L(a) < L(b)) kann _nicht_ (a -> b) geschlossen werden sondern nur ((a -> b) oder a, b concurrent) (die timestamps können von unabhängigen events stammen) überwindung durch vector-timestamps: jeder prozess hat einen vektor mit einträgen für jeden prozess mit annahme multicast: bei lokalen events wird der eintrag für den eigenen prozess erhöht beim senden wird der vektor mitgeschickt beim empfang wird die nachricht solange verzögert, wie ein eintrag des empfangenen vektors (nicht der eintrag vom sender) größer ist als einer der einträge des lokalen vektors (das würde bedeuten, dass eine nachricht von diesem prozess fehlt). für den eintrag des senders muss gelten, dass dieser um 1 größer ist als der lokale eintrag, ansonsten würden nachrichten von diesem prozess fehlen. dann: v_i = max ( lokaler v_i, empfangener v_i ) jetzt gilt: (V(a) < V(b)) => (a -> b) (kausale ordnung) 4) distributed mutual exclusion: nur ein prozess darf einen kritischen codeabschnitt ausführen (safety); jeder prozess muss irgendwann drankommen (liveness); eine ordnung soll fairness garantieren. zentraler algo: clients fragen beim koordinater nach einer berechtigung ist die queue leer, erhält der client eine antwort und kann fortfahren andernfalls wird er in die queue eingereiht wenn ein prozess fertig ist, benachrichtigt dieser den koordinator, der anschließend dem nächsten prozess die berechtigung gibt fehlertoleranz: fail bei coordinator crash skalierbarkeit: gut (O(1) nachrichten) verteilter algo: clients multicasten die anfrage inkl timestamp der kleinste timestamp gewinnt, alle schicken diesem ein OK ist dieser fertig, gibt er dem nächsthöheren timestamp das OK fehlertoleranz: fail bei einem crash skalierbarkeit: schlecht (O(n) nachrichten) token ring algo: ein token wird im kreis weitergereicht hat ein prozess den token, kann er den kritischen abschnitt ausführen fehlertoleranz: fail bei einem crash skalierbarkeit: akzeptabel; lineare steigerung der tokenumlaufzeit bei neuen clients 5) locking bei einem fileserver mit mehreren clients sinnvoll: zentraler algo - beschreibung: s.o. - daten sind zentral, daher auch zentrale verwaltung - zentrale steuerung i.A. am einfachsten (immer vollständige info, effizente auswahlstrategien möglich) lesen & schreiben blockieren, während einer schreibt, ist sinnvoll wegen R-W und W-W konflikten 6) election: auswahl eines koordinators unter gleichberechtigten prozessen bully: jeder prozess hat eine eindeutige id wahl: 1. ein prozess schickt anfragen an prozesse mit höherer id 2. alle davon, die noch laufen, antworten an diesen prozess und unterdrücken ihn 3. höhere prozesse: goto 1 bis bei 2 keine antwort kommt (dieser prozess ist der höchste) Ring: jeder prozess hat eine eindeutige id wahl: ein prozess schickt eine liste durch den ring. jeder fügt sich selbst hinzu und gibt die liste weiter. ist ein nachfolger gecrasht, wird die nachricht an den nächsten nachfolger weitergeleitet. ist die liste beim ausgangsknoten angelangt, findet dieser den höchsten eintrag heraus. dieser wird neuer koordinator. der prozess informiert alle anderen darüber. wird die wahl gleichzeitig von verschiedenen prozessen gestartet, kommt trotzdem immer dasselbe ergebnis heraus. beide sehr fehlertolerant, solange noch ein knoten lebt, kann ein koordinator bestimmt werden. ad-hoc netzwerke: ungeeignet, da alle knoten bekannt sein müssen, und eine eindeutige id zugewiesen haben müssen weiters sollten hier günstige knoten gewählt werden (bandbreite) large-scale: hier sind mehrere koordinatoren (superpeers) notwendig diese sollten gute anbindung (latency, throughput) haben und gut verteilt sein anzahl der superpeers sollte von anzahl der knoten abhängen bei ring würde die abstimmung sehr lange dauern bei bully müssten zu viele nachrichten geschickt werden 7) probleme bei global state ermittlung: global state: zustand der prozesse und nachrichten, die gerade unterwegs sind probleme: - es gibt keine einheitliche, globale sicht - es gibt keinen einheitlichen zeitpunkt der aufzeichnung - inkonsistente cuts: wirkungen ohne ursache snapshot algo (chandy & lamport): ein prozess schickt eine markierung an allen kanälen aus und startet lokale aufzeichnung von system und eingehenden nachrichten wenn eine prozess die markierung zum ersten mal bekommt, wird die aufzeichnung gestartet beim 2. erhalt wird die aufzeichnung gestoppt. alle aufzeichnungen zusammen ergeben einen konsistenten cut. (bedingung: fifo nachrichtenabarbeitung) (diesen zustand muss es trotzdem so nicht gegeben haben) === consistency, replication === 1) gründe für replikation: ausfallsicherheit performance replikation - skalierbarkeit: je nach konsitenzanforderungen lässt sich replikation unterschiedlich gut einsetzen bei hohen konsistenzanforderungen bedeutet replikation einen hohen mehraufwand (skaliert schlecht) varianten content replication/content placement: permanente replikas: - cluster: mehrere server an einem ort, lastverteilung - mirroring: gespiegelte server an verschiedenen orten server-initiierte replikas: bei vielen anfragen client-initiierte replikas: cache. muss durch client aktuell gehalten werden. replikas oft zeitlich beschränkt 2) möglichkeiten zur update propagation: - notification: replikas wird mitgeteilt, dass daten outdated sind. diese updaten ihre daten beim nächsten read auf diese. sinnvoll, wenn mehr geschrieben als gelesen wird - state transfer: neue daten werden transferiert sinnvoll, wenn mehr gelesen als geschrieben wird - operation transfer: updateoperation wird transferiert mehr rechenaufwand, möglicherweise weniger datentransfer - push: replikas bekommen updates automatisch eher bei server-initiierten und permanenten replikas gute konsistenz sinnvoll, wenn viel gelesen wird (alle updates müssen sowieso zu den replikas) - pull: replikas müssen updates nachfragen eher bei client-initiierten replikas response time kann steigen, wenn viel gepullt werden muss sinnvoll, wenn seltener gelesen wird - lease: push auf zeit, dann wieder pull - synchron: blocking, eager (alle kopien auf einmal updaten) - asynchron: lazy (erst eine kopie updaten, die anderen später) - unicast: server sendet direkt an n server; gut bei pull - multicast: server sendet, netzwerk übernimmt verteilung; gut bei push 3) primary-based: master server (koordinator) = primary, der immer am aktuellsten stand ist synchron: daten werden gleich auf alle replikas verteilt keine inkonsistenzen, daten immer überall up2date atomic changes aber langsam, halten keinen crash aus asynchron: daten werden nur auf primary kopiert, dieser verteilt später an replikas bewertung: genaues gegenteil von synchron local-write: der server, mit dem ein client gerade verbunden ist, wird zum primary holt daten bei write vom alten primary; verteilt updates davon an andere vorteil: es gibt keine schreib-bottleneck macht nur asynchron sinn 4) replicated-write: schreiboperationen können nicht nur an einem primary, sondern an jeder replika stattfinden active replication: alle replikas führen die operationen gesendet probleme: wenn diese bei der operation mit weiteren servern kommunizieren müssen, geschieht dies n mal. eine replication-aware layer kann das abfangen. determinismus: die gleiche operation kann verschiedenes bewirken, wenn die umgebung nicht ident ist. nachrichten müssen in gleicher reihenfolge eintreffen -> ordnung notwenig vorteile: einfach kein bottleneck kein spof quorum-based: schreib- und leseoperationen müssen auf einer gewissen anzahl von servern stattfinden N_r + N_w > N (R-W konflikte) N_w > N/2 (W-W konflikte) braucht versionsnummern jedes write erzeugt eine neue version, beim read wird die höchste version zurückgegeben vorteile: kann an das spezielle lese-schreib-verhältnis angepasst werden übersteht je nach konfiguration einige ausfälle 5) besonderheiten an replikation von objekten: zugriffe auf objekte müssen konsistent gehalten werden. kann mit koordinator oder totally ordered multicasts auf basis von lamport timestamp gemacht werden replication transparency inkl skizze (replicated invocation): skizze: a schickt nachricht repliziert an b_1, b_2, b_3; alle b_i würden nachricht an c_1 und c_2 schicken. eine transparenzschicht fängt das ab. das koordinatorobjekt leitet nur eine nachricht an c_1 und c_2 weiter. bei den c_i gibt es auch einen koordinator, der die 2 gleichen anfragen erkennt, und nur einmal auf alle b_i antwortet 6) epidemic protocols: einzige garantie: update erreicht replika irgendwann updates werden lokal an nachbarn weitergereicht gute skalierbarkeit schwieriges löschen (death certificates) gossiping im zusammenhang mit replica update: nachrichten werden an neue nachbarn verteilt, bis sie mehrere nachbarn sie schon bekommen haben schnelle verbreitung in großen netzwerken; keine garantie anti-entropy modell: nachbarn, mit denen updates ausgetauscht werden, werden zufällig ausgewählt. === dependability, fault tolerance === 1) dependability. deliver a system, that can justifiably trusted 5 attribute: availability reliability safety confidentiality integrity maintainability availability - reliability: availability: readiness for service (uptime) reliability: continuity of service (mean time between failures) dependability threats: failure, error, fault failure: service, das ein system anbietet, verhält sich falsch. ausgelöst durch error. error: der teil des zustands eines systems, der zu einem failure führen kann fault: ursache eines fehlers permanent: tritt dauerhaft auf, bis zur reperatur: bsp: hardwaredefekt transient: tritt einmal auf. bsp: vogelschwarm stört funkverbindung intermittent: tritt manchmal auf. bsp: netzwerk 2) wozu fehlermodelle: kategorisierung überblick bei systemanalyse (checklist) einschätzung der auswirkungen (unterschiedlich je nach kategorie) fehlermodelle für fail-controlled systems; maskierungsaufwand: fail-halt leicht festellbar; k+1 server insgesamt für maskierung fail-passive (=fail-silent) 2k+1 (man braucht mehrheit zum überstimmen des fehlverhaltens) fail-consistent: immer gleich ausgefallen 2k+1 (w.o.) fail-inconsistent: byzantinisch; ohne distributed agreement: 2k+1 mit: 3k+1 k-fault-tolerant: k komponenten können ausfallen, ohne dass das system beeinträchtigt wird. je nach fehlerklasse braucht man verschieden viele korrekt funktionierende systeme, die richtig funktionieren, um den betrieb aufrecht zu erhalten. k schwer einzuschätzen weiteres problem: ausfall muss als solcher erkannt werden. 3) wieso redundanz zur fehlermaskierung: ein ausfall muss kompensiert werden; dies ist nur durch zusätzliche resourcen möglich. keine redundanz = nur notwendige komponenten. (=> fällt eine notwendige komponente aus, funktioniert das system nicht mehr) redundanzarten: information zeit: bsp: nachrichten mehrmals mit zeitlicher differenz senden physisch (technisch): mehrfacher hard-/software 4) two-army problem: konsens ist bei unzuverlässiger kommunikation nicht möglich (die letzte bestätigung kann immer verloren gehen; damit weiß der ein prozess nicht, ob der andere zustimmt) bedingungen: synchrones system, perfekte prozesse, unzuverlässige kommunikation 5) byzantinische generäle: bedingungen: synchrone, zuverlässige kommunikation, prozesse können beliebig ausfallen (insb. falsche nachrichten verschicken) bei 3 prozessen ist kein konsens möglich (man braucht 3k+1), da jeder prozess nur mit 2 anderen kommuniziert. wenn diese beiden verschiedenes sagen, kann der prozess nicht entscheiden, was korrekt ist. 6) fehlerklassen in rpc-client/server-umbebungen: - client kann server nicht finden - lost request: - server crash: client kann nie wissen, ob die anfrage bearbeitet wurde -> man kann nicht richtig reagieren - lost reply - client crash lost-reply: client bekommt keine antwort => weiß nicht, was passiert ist (antwort verloren, server crash, anfrage bereits verloren (wenn kein ACK)) idempotente nachrichten können erneut gesendet werden, nachrichten sind aber oft nicht idempotent lösungsmöglichkeit: sequenznummern: client schickt nummer für anfrage mit server erkennt, ob das eine retransmission ist server kann antworten speichern und bei retransmission nur antwort abrufen (stateful) 7) reliable bzw. ordered multicast (group communication) in statischen prozessgruppen: eine nachricht erreicht eine gruppe von prozessen garantiert. bei ordered: garantiert in einer bestimmten reihenfolge ordnungen: - fifo: sendet ein prozess n_1 vor n_2, erhalten alle n_1 vor n_2 - causal: happened-before - total: alle nachrichten bei allen prozessen in selber reihenfolge erhalten bei dynamischen gruppen: es braucht konsens, wer in der gruppe ist atomic multicast (virtual synchrony): multicast, der entweder alle nicht fehlerhaften oder keinen prozess erreicht, und das in der selben reihenfolge. unterschied zu reliable multicast: nachrichten sind total geordnet problem: einigkeit über gruppenzugehörigkeit. group view: geteilte sicht auf gruppenzugehörigkeit bei join/leave/fail: view-change nachricht alle prozesse schicken allen anderen alle gepufferten nachrichten (feststellen, ob eine bei einem fehlt. in diesem fall: verwerfen) === security === 1) definition von security mit attributen availability, confidentiality, integrity anhand von beispielen. availability: service muss verfügbar sein confidentiality: nur berechtigte entitäten dürfen bestimmte daten lesen integrity: daten drüfen nur von berechtigten erstellt, verändert und gelöscht werden. 4 threats und 4 security mechanisms: interception: angreifer liest mit fabrication: nachrichten einschleusen modification: nachrichten verändern interruption: service unterbrechen encryption: daten nur mit passwort lesbar machen (integrity, confidentiality) authentication: sicherstellen, dass eine entität ist, was sie vorgibt zu sein. authorization: zugriff nur für bestimmte entitäten gewähren auditing: überprüfen, wer was gemacht hat 2) SSL/TLS: verschlüsselung über public-key kryptographie wird ein schlüssel ausgetauscht alle nachrichten werden dann mit diesem symmetrisch verschlüsselt im inet protkoll stack: über TCP (transport layer) 3) cryptography: die transformation von plaintext in ciphertext und zurück. beide transformationen benötigen spezielle verfahren und einen schlüssel. ohne schlüssel kann vom ciphertext nicht auf den plaintext geschlossen werden. verfahren soll gewährleisten: confidentiality, authentication, integrity, non-repudiation symmetrisch: ein schlüssel, den sender und empfänger haben und nicht preisgeben dürfen schwierige schlüsselverteilung schnell DES, AES asymmetrisch: 2 schlüssel (privater und öffentlicher) einfache schlüsselverteilung langsam RSA, elliptic curve 4) eigenschaften von secure channel: authentication: es kann festgestellt werden, mit wem man kommuniziert integrity: nachrichten können nicht verändert werden confidentiality authentifizierung bei public key crypto: ein von A zufällig generierter challenge wird mit dem public key von B verschlüsselt, und an B geschickt. B entschlüsselt diesen und generierte auch einen challenge. beides wird mit dem public key von A verschlüsselt und an A geschickt. A schickt den challenge von B zurück. (das genügt zur authentifizierung, ein shared key kann bei diesem verfahren auch noch ausgetauscht werden) 5) authentifizierung bei symmetrischer verschl: A: A B: R_B A: K_A,B ( R_B ) A: R_A B: K_A,B ( R_A ) problematische optimierung: B darf den challenge von A erst verschlüsselt an A senden, wenn A sich authentifiziert hat. ansonsten kann sich A von B jede challenge in einer anderen session verschlüsseln lassen. (reflection attack) 6) digitale signatur, garantieren, funktionsprinzip: mechanismus zum sicherstellen des ursprungs einer nachricht. funktionsweise: nachricht wird auf eine weise verändert, die dem sender möglich ist bsp: ganze nachricht oder hash der nachricht mit private key oder shared key verschlüsseln hash, notwendige eigenschaften für digitale signatur: funktion, die eine bitfolge fixer länge aus einer verschieden langen nachricht errechnet eigenschaften: vom hash kann nicht auf die nachricht geschlossen werden weak collision resistance: für einen gegebenen wert ist es schwer, einen nachricht zu finden, die diesen hash-wert hat strong collision resistance: es ist schwer, 2 beliebige nachrichten mit gleichem hashwert zu finden 7) key distribution centre: bei symmetrischer verschlüsselung braucht jeder host ein eigenes passwort für jeden host, mit dem er kommunizieren will (skaliert schlecht). kdc: fixer server, mit dem alle hosts verschlüsselt kommunizieren können. dieser verteilt bei bedarf temporäre passwörter an 2 parteien, die kommunizieren wollen => N schlüssel statt N*(N-1)/2 authentifizierung: A->K: A,B K->A: K_A,KDC (K_A,B), K_B,KDC (K_A,B) K schickt hier 2 schlüssel; einen, den nur A lesen kann, und einen, den nur B lesen kann A authentifiziert sich dadurch, dass es den ersten entschlüsseln kann A->B: A, K_B,KDC (K_A,B) hier authentifiziert sich B, indem es den schlüssel entschlüsseln kann. B weiß auch, dass es A vertrauen kann, weil die info vom KDC stammt (erwiesen durch verschlüsseltes passwort), und das KDC gibt die info nur aus, wenn A sich schon authentifiziert hat. === technology === 1) 2 techniken, bsps oder systeme zu: temporal coupled, referential coupled; direct: telefon, rpc temporal uncoupled referential coupled:; mailbox: e-mail, sms, persistent message passing temporal coupled, referential uncoupled; meeting oriented: publish/subscribe, information bus temporal uncoupled, referential uncoupled; generative communication: distributed shared memory, JavaSpaces, tuple spaces 2) publish/subscribe; möglichkeiten, probleme: subscribe: prozesse registrieren sich für den empfang von nachrichten bestimmter typen publish: prozesse übergeben nachrichten bestimmter typen an das system. dieses verteilt es an alle registrierten prozesse beide prozesse müssen aktive sein skaliert gut (loose kopplung) jini: generative communication; unterstützt referentielle und zeitliche entkopplung durch JavaSpaces JavaSpaces: basiert auf tupel (liste von objektreferenzen) jeder prozess kann tupel hineinstellen lesen durch angabe eines template-tupel (alle matches werden zurückgegeben) operationen: write, read, take, notify 3) webserver: allgemeine bedeutung: programm, das dienste über das internet anbietet spezielle bedeutung: programm, dass via http dokumente an clients senden kann. http: austausch von dokumenten übers internet 2 operationen: get, post cgi-programm: erhält vom webserver eine anfrage nach einem bestimmten dokument sowie optional zusätzliche parameter. generiert daraus u.U. mithilfe einer datenbank oder anderer resourcen ein dokument. dies wird dem server übergeben, welcher es dem client weiterreicht.