TU Wien:Verteilte Systeme VO (Göschka)/Prüfung 2010-06-10

Aus VoWi
Wechseln zu: Navigation, Suche

« Prüfung 2010-04-29 | Prüfung 2010-10-11 »

Modus[Bearbeiten]

5 Fragen, nur 4 davon sind zu beantworten. zeit: 45 Minuten. Letzte Frage war neu.

Prüfungsfragen[Bearbeiten]

Frage 1[Bearbeiten]

Frage: Wie kann man die Flexibilität der Middleware erhöhen sowie die Zusammenarbeit von Middleware und Anwendung effizienter gestalten? Erläutern Sie dabei die Grundprinzipien von Interceptoren, Adaptivität und Self-Management.

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Flexibilität\s*/si}}

Flexibilität der MW erhöhen:

  • Interceptors
  • Separation of concern (Modularisierung)
  • Reflection (Anpassen der Parameter zur Laufzeit)
  • Component-based design
  • Middleware-Application interaction (Plug-ins, ...)
  • Autonomic computing, self-* (Selbstregulierung, Selbstwiederherstellung, ...)


Ein wichtiger Zweck von Middleware (Schicht zwischen Applikationen und verteilten Plattformen) ist es, einen gewissen Grad an Verteilungstransparenz zu bieten. Auch Middleware-Systeme folgen bestimmtem Architekturstil (z.B. Object-based (CORBA, Event-based (TIB/Rendezvous)) Middleware-Systeme sollen einfach konfigurierbar, adaptierbar und individuell anpasspar sein, je nach Applikation daher wird Trennung zwischen Policy und Mechanismus vorgenommen!

TODO /* bzg. effizientere Gestaltung würde ich meinen, dass hier eine bessere Anpassbarkeit (eventuell automatisch) Bezug genommen werden kann (seite 58 / 59 Discussion bietet da glaub ich eine gute Richtlinie für die Beantwortung)


Interceptors

Software-Konstrukte, die den normalen Kontrollfluss unterbrechen und es erlauben, anderen (Applikations-spezifischen) Code auszuführen = Mittel um die Middleware anzupassen Objekt A ruft eine Methode auf, die zu Objekt B gehört, welches sich auf einer anderen Maschine als Obj. A befindet. Das ist ein Remote Object Call, dieser erfolgt in drei Schritten:

  1. A und B bieten beide das gleiche Interface an. A ruft die Methode auf, die in diesem Interface verfügbar ist auf.
  2. Der Aufruf von A wird in eine "generic object invocation" transformiert, möglich gemacht durch ein "object-invocation interface" der Middleware der Maschine, auf der sich A befindet.
  3. Am Schluss wird die "gen. obj. invoc." in eine message transformiert und wird über das transport-level network interface geschickt, das A's local operating system anbietet.
Generelle Ansätze zu Adaptiver Software

Middleware soll sich an Veränderungen in der Umgebung eines DS anpassen –> Konstruktion adaptiver Software. Drei Basistechniken, um zu Software-Adaptierung zu kommen:

  1. Separation of concerns: Traditionelle Art, Systeme zu modularisieren (d.h. Trennen der Teile eines Systems, die Funktionalität implementieren, von denen, die für Extrafunktionalitäten wie Reliability, Performance, Security etc. zuständig sind.) – ist in DS nicht einfach (Thema für aspect-oriented software development)
  2. Computational reflection: Fähigkeit eines Programms, sich selbst zu überprüfen und, wenn notwendig, sein Verhalten anzupassen
  3. Component-based design: unterstützt Anpassung durch Komposition (dynamisch zur Laufzeit)
Self-Management in Verteilten Systemen

Selbstmanagement ist in großen, verteilten Systemen von entscheidender Bedeutung. Für viele Systeme stellen eine zentrale Verwaltung und Organisation keine optimale Lösung dar. Die meisten selbstverwaltenden Systeme haben gemeinsam, dass Anpassungen mithilfe einer oder mehrerer Rückkopplungsschleifen (feedback-control-loops) erfolgen. Diese Schleife besteht neben den Komponenten, die das eigentliche VS ausmachen, aus 3 Teilen:

  • Die metric estimation component quantifiziert die Aspekte eines Systems, die Rückschlüsse auf seine Effizienz zulassen, z.B. Latenzzeiten.
  • Die feedback analysis component wertet diese Messungen aus und bestimmt, welche Veränderungen am System vorgenommen werden.
  • Schließlich beeinflussen verschiedene Anpassungsmechanismen das System direkt und verändern z.B. die Platzierung von Repliken, Scheduling Strategien oder Lastverteilung


Frage 2[Bearbeiten]

Frage: Was ist ein "Name Space"? Erläutern Sie das Grundprinzip des "Closure Mechanismus" anhand eines Beispieles (zB Unix File System).

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Name Spaces\s*/si}}

TU Wien-Verteilte Systeme VO (Göschka) - distsys tanenbaum S196.gif

Name Space: Namen werden in einem Verteilten System mithilfe eines Namespace organisiert. Ein Name identifiziert ein Objekt. Namen sind dabei immer relativ zu einem Verzeichnisknoten. Zur eindeutigen Zuordnung ist jedoch der entsprechende Kontext – eben der Namensraum zu beachten. Hierarchische Namen können als beschriftete gerichtete Graphen dargestellt werden:

  • Blattknoten = benannte Entität
  • Verzeichnisknoten (hat ausgehende Kanten): speichert eine Verzeichnistabelle: jede ausgehende Kante wird als Paar der Form (Kantenbeschriftung, Knotenbezeichner) gespeichert, (siehe obige Skizze)


Durch 'Aliases können mehrere Namen auf die gleiche Entität zeigen.

  • Hardlinks: absolute Pfade verweisen auf den selben Knoten im Graphen (siehe Fig. 5-9.)


  • Symbolic Links: speichern Pfad zu einer Entität

Symboliclink.png


Durch Mounting können Namensräume miteinander kombiniert werden. (benötigt: access protocol, server, mounting point).


Closure Mechanismus: zu wissen, wie und wo die Namensauflösung beginnen soll ? Auswahl des ersten Knotens.

Bsp. Unix: um absoluten Verzeichnispfad (/users/home) aufzulösen, muss dem Dateisystem der Root-Knoten „/“ bekannt sein. Der tatsächliche Offset des Root-Knotens ist im Superblock des logischen Laufwerks kodiert.

Bsp. DNS: Der Closure Mechanismus bei DNS sind die IP-Adressen der 13 DNS-Root-Server


Frage 3[Bearbeiten]

Frage: Welche Probleme gibt es bei der Ermittlung des "Global State" und wie können diese überwunden werden? Geben Sie zumindest einen Algorithmus an. Hinweis: Dies wird nur in den Folien und im PDF (weiter unten und im Fragenkatalog und auf der Homepage im Fragenkatalog) erwähnt.

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Global State\s*/si}}

Global State
Der Globale State eines verteilten Systems besteht aus

  • dem localen Zustand eines jeden Prozesses
  • zusammen mit den Nachrichten die gerade unterwegs sind (gesendet aber noch nicht empfangen)


Probleme:

  • Es könnte ein inkonsistener "Schnitt" durch das System gemacht werden. (Ergebnisse ohne Ursache. z.B.: Empfangen einer Nachricht ohne Senden dieser Nachricht)
  • Keiner hat eine globale Sicht auf das System.
  • Es gibt keine gemeinsame Zeit für die Aufzeichnung ("Stichtag")

Lösung der Probleme durch Ermittlung des Globale State durch Chandy und Lamport-Algorithmus.

Bitte die Probleme überarbeiten, mir ist nicht mehr eingefallen


Algorithmus von Chandy und Lamport (Snapshot vom Global State):

Chandy Lamport.png

Ein Initiator beginnt seinen eigenen Status aufzuzeichnen und schickt einen Marker aus. Beim Empfang des 1. Markers zeichnet jeder Rechner seinen lokalen Status auf und schickt den Marker weiter. Bis zum Empfang des Markers zum zweiten Mal zeichnet queued jeder Prozess alle eingehenden Nachrichten. Beim Empfang des Markers zum zweiten Mal ist die Aufzeichnung abgeschlossen: der lokale Status und die aufgezeichneten Nachrichten können an den ursprünglichen Initiator gesendet werden, wo dann die Auswertung passiert.

Der aufgezeichnete Status ist garantiert konsistent, kann aber Kombinationen von lokalen Zuständen enthalten, die so nie aufgetreten sind.

EDIT: Ich verstehe den Algorithmus (lt. wikipedia) anders: Der Initiator schickt einen Aufzeichnungs-Marker an alle anderen Rechner. Wenn ein Rechner den Marker zum ersten Mal erhält, schickt er seinen momentanen Status an den Initiator und hängt den Marker an alle anderen seiner ausgehenden Pakete (um den Marker weiter zu verbreiten). Erhält er jetzt eine Message an der kein Marker hängt, so war dieses Message offensichtlich gerade "im Äther" als die Aufzeichnung begann. Da sie natürlich auch zum Global State gehört, wird die Message ebenfalls an den Initiator geschickt. Dieser hat dadurch den Überblick über den Status aller Rechner und aller Nachrichten die zu diesem Zeitpunkt im Netz unterwegs waren.

weitere Infos GlobalState.pdf,Chandy-Lamport-Algorithmus auf Wikipedia (de),Chandy-Lamport auf Wikipedia (en)

ausführliche Erklärung des Algorithmus: https://web.archive.org/web/*/https://users.informatik.haw-hamburg.de/~schmidt/vs/05_ZeituGlobalerZustand.pdf

EDIT2: Ich verstehs eigentlich nach dem Artikel in der deutschen Wikipedia und dem PDF auch so wie in der ersten Erklärung (nicht dem EDIT).

EDIT3: Ich verstehe es nach den Folien und dem PDF ebenfalls so wie ganz oben (und nicht im EDIT) beschrieben. -- emptyvi

EDIT4: Tatsächlich stimmt die erste Version mit der deutschen Wikipedia, und die zweite mit der englischen überein. Es handelt sich wohl um zwei verschiedene Varianten des Algorithmus. Bei der einen wird der Status nur aufgezeichnet, bei der anderen auch an den Initiator gesendet. Und dann muss die empfangene Nachricht auch weitergeleitet werden.


Frage 4[Bearbeiten]

Frage: Was sind Epidemic Protocols. Welche Vor- und Nachteile haben diese? Erklären Sie "gossiping" ("rumor spreading") im Zusammenhang mit Replica update propagation. Erläutern Sie Vor- und Nachteile. Erklären Sie das Anti-Entropy Modell im Zusammenhang mit Replica update propagation. Erläutern Sie Vor- und Nachteile.

{{#dpl:resultsheader=Diese Frage wurde bereits in folgenden Prüfungen gestellt: |oneresultheader=Diese Frage wurde bereits in der folgenden Prüfung gestellt: |noresultsheader=* Diese Frage wurde noch nie gestellt! |skipthispage=no |shownamespace=false |uses=Vorlage:Kapitel |replaceintitle=/Verteilte Systeme VO \(Göschka\)\/Prüfung/, |include={Kapitel}.dpl |includematch=/\|\s*TU Wien:Verteilte Systeme VO \(Göschka\)\/Fragenkatalog Wiki\s*\|\s*Epidemic Protocols\s*/si}}


Epidemic Protocols sind für Datenspeicher gedacht, welche nur eine schlußendliche (en eventual = de schlußendlich!) Konsistenz aufweisen müssen. Das heißt: Wenn es keine Aktualisierung gibt, muss nur sichergestellt sein, dass alle Repliken irgendwann identisch sind.

Das Hauptziel dieser Protokolle ist es, schnell Information an viele Knoten zu verbreiten während man nur lokale Informationen verwendet.

  • Vorteile: Gute Skalierbarkeit, Aktualisierung an alle Repliken erfolgt in so wenigen Nachrichten wie möglich -> geringe Netzwerkbelastung.
  • Nachteile: Weitergabe des Löschens eines Datenelements ist schwierig, löst keine Aktualisierungskonflikte, nur -e-v-e-n-t-u-e-l-l-e- schlußendliche Konsistenz (sehr schwache Konsistenz? -- nicht schwach, aber erst später).


Das Anti-Entropy Modell ist ein Weitergabemodell für Epidemische Protokolle welches per Zufall einen anderen Server auswählt, und mit diesem dann Aktualisierungen austauscht. Es kann pull- oder pushed basiert arbeiten (Ein Server schickt seine Updates zu einem anderen oder holt sie von einem anderen). Wenn viele Knoten infiziert sind, ist die Chance relativ gering über den push-Ansatz weitere Knoten für ein Update zu finden. Der pull-Ansatz funktioniert viel besser wenn viele Knoten infiziert sind.

EDIT1: Es ann gezeigt werden , dass Akutalisierungen irgenwann über alle Server verteilt werden wenn nur ein einziger Server infektiös ist (bei pull-Ansatz)

Gossiping ist eine spezielle Form des Anti-Entropy Modells und ein effizientes Weitergabemodell für Epidemische Protokolle. Die Funktionsweise ist einfach: Wenn ein Datenelement aktualisiert wurde, wendet sich der Server an einen beliebigen anderen Server um ihm die "Neuigkeit" mitzuteilen. Dieser wiederum macht dasselbe und kontaktiert den nächsten Server um die Aktualisierung vorzunehmen usw. Wenn ein Server erreicht wird, der schon "infiziert" wurde, ist die "Neuigkeit" nicht mehr so interessant und macht nur mehr mit einer gewissen Wahrscheinlichkeit weiter mit "gossiping".

  • Vorteil: Aktualisierung wird schnell weitergereicht
  • Nachteil: Es kann nicht garantiert werden das alle Server "infiziert" werden, sprich mit Aktualisierungen versorgt werden.

Daten löschen ist leider in den vorgestellten Ansätzen nicht so leicht. Epidemische Protokolle sind gut, um Daten zu verbreiten, aber ein Nachteil ist, dass das Löschen schwierig ist. Wenn man einen Datensatz von einem Knoten komplett löscht, ist der Knoten ja wieder susceptible (ansteckbar) und wird die "Krankheit" bald wieder bekommen. Daher muss man data removal per "death certificates" verbreiten, die eigentlich selbst nur Updates sind, die Datensätze ungültig machen. Leider wird es mit der Zeit sehr viele "death certificates" auf jedem Knoten geben, was Performanzmäßig nicht gerade ideal ist.


Frage 5[Bearbeiten]

Frage 5 hab ich auch so in Errinerung wie in diesem Beitrag im Informatikforum