TU Wien:Verteilte Systeme VO (Göschka)/Prüfung 2013-03-16

Aus VoWi
Zur Navigation springen Zur Suche springen

1.Scalability[Bearbeiten]

Frage: Erläutern Sie Probleme und Lösungsansätze für "Scalability".

{{#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*Scalability\s*/si}}


Scalability ist die Fähigkeit des Systems bei wachsenden Anforderungen noch einsatzfähig zu sein. Die Skalierbarkeit eines Systems kann dabei in mindestens drei unterschiedlichen Dimensionen gemessen werden:

  • Größe/Ausmaß: noch mehr Benutzer oder Ressourcen können einfach hinzugefügt werden
  • Geographisch: die Benutzer und Ressourcen dürfen weit auseinander liegen (topologisch)
  • Administrativ: noch immer einfach verwaltbar, auch wenn es sich über viele unabhängige administrative Organisationen (domains) erstreckt.


Probleme bei der Skalierbarkeit (meist Performance-Probleme)

  • Größe:
    Werden mehrere Benutzer oder Ressourcen unterstützt, werden wir häufig mit den Einschränkungen zentralisierter Dienste, Daten und Algorithmen konfrontiert:
    • Zentrale Services, z.B. ein einziger Server für alle Benutzer (ist aber oft für die Sicherheit erforderlich!)
    • Zentral verwaltete Daten, z.B. ein einziges Online-Telefonbuch
    • Zentral ablaufende Algorithmen, z.B. Routing durchzuführen, das auf vollständiger Information basiert
Nur dezentrale Algorithmen sollten verwendet werden! Charakteristika dezentraler Algorithmen:
  • Keine Maschine hat vollständige Information über den Systemstatus.
  • Computer entscheiden nur auf Grund von lokalen Informationen.
  • Der Ausfall eines Computers schädigt nicht den Algorithmus.
  • Die Existenz einer globalen Uhr wird nicht implizit vorausgesetzt.
  • Geographisch:
    • Verteilte Systeme die für LANs entwickelt wurden, basieren auf synchroner Kommunikation: Client blockiert bis Antwort zurück gesendet wird – problematisch in WANs (zu langsam)
    • Kommunikation in WANs ist inhärent unzuverlässig und so gut wie immer Point-to-Point, LANs hingegen bieten hoch zuverlässige Kommunikation und unterstützen Broadcasting
    • Geographische Skalierbarkeit hängt stark mit den Problemen zentralisierter Lösungen zusammen, die auch die Größenskalierbarkeit behindern.
  • Administrativ:
    Schwierige Frage wie ein verteiltes System über mehrere voneinander unabhängige administrative Domänen skaliert werden kann. Ein Problem sind die widersprüchliche Strategien zur
    • Benutzung (und Bezahlung) von Ressourcen
    • Verwaltung
    • Sicherheit


Skalierungstechniken:

  • Verbergen der Latenzzeiten (wichtig für geographische Skalierbarkeit)
    • asynchrone Kommunikation -> Abarbeiten von anderen Aufgaben, während man auf eine Antwort wartet.
    • Gesamte Kommunikation reduzieren (z.B. Teile der Berechnung zum Client-Prozess verschieben, wie z.B. Überprüfen von Formulareinträgen schon beim Client)
  • Verteilung -> Komponenten in kleinere Teile zerlegen und über gesamtes System verteilen. Bsp.: DNS (hierarchisch in Domains organisiert -> dieser wiederum in sich nicht überschneidende Zonen aufgeteilt -> Namen in jeder Zone werden von einem einzigen Name-Server behandelt)
  • Replikation
    • Erhöht Verfügbarkeit
    • Balanciert die Last zwischen Komponenten aus -> bessere Performance
    • In WANs kann eine nahe gelegene Kopie Kommunikations-Latenz-Probleme verbergen
    • Caching = spezielle Form der Replikation (vom Client ausgelöst)
      • Nachteil: Caching und Replikation führt zu Konsistenzproblemen!


Probleme bei Scalable Size:

  • Controlling the cost of physical resources: The quantity required should be O(n)
  • Controlling the performance loss: In hierarchical system should be no worse than O(log n)
  • Preventing software resources running out, but over-compensation may be even worse: Internet Addresses or Oracle7 2TB restriction
  • Avoiding performance bottlenecks (centralized services, data, or algorithms)


2. Serverdesign[Bearbeiten]

Frage: Geben Sie grundlegende Design-Entscheidungen für Server an und bewerten Sie diese. Gehen Sie auf den Unterschied zwischen stateful und stateless Servern genauer ein und geben Sie Beispiele an. Erläutern Sie anhand einer Skizze Architektur und Funktionsweise eines multi-threaded Servers (zB File- oder Web-Server). Was ist beim Einsatz von Multi-Threading vom Entwickler besonders zu beachten?

{{#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*Serverdesign\s*/si}}

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

Grundlegende Design-Entscheidungen sind zB:

  • benötigt man einen iterativen Server (Server handled alles selbst)
  • oder einen concurrent server (nebenläufig, gibt alle Aufgaben an eigene Worker-Threads oder andere Prozesse weiter)
  • wie werden Interrupts behandelt(zB. wenn man ein File via FTP auf den Server lädt und währenddessen bemerkt, dass es das falsche ist )
    • Server Interrupt: Eine Möglichkeit für den User ist es den Client zu beenden und neu zu starten -> Server wird Verbindung aufgeben und das File verwerfen, da er denkt der Client ist abgestürzt.
    • out of band control: Client und Server so entwickeln dass sie in der Lage sind out of band daten zu senden. Der Server behandelt diese Daten mit höchster Priorität vor allen Anderen. Eine Möglichkeit: Server hört auf einem getrennten Control End Point, ob out of band Daten vom Client kommen.
  • ist der Server / besitzt der Server
    • stateless Server hat keine Information über den Status des Clients und kann eigenen Status ändern ohne den Client darüber zu informieren. (z.b. Webserver). Zustandslose Server enthalten in Wirklichkeit zwar dennoch Informationen über die Clients, aber entscheidend ist dass der Verlust dieser Informationen zu keinen Unterbrechungen führt.
    • stateful Server enthält beständige Information über Clients. Diese werden so lange behalten bis sie ausdrücklich gelöscht werden. (z.B. Fileserver: Tabelle mit Clients und Berechtigungen). Sind aus Clientsicht schneller als stateless Server. Nachteil: Stürzt der Server ab, muss der Status vor dem Absturz wieder hergestellt werden. Gelingt das nicht kommt es zu Problemen.
    • soft state (der Server kennt den Client nur für eine bestimmte Zeit und verwirft danach alles wieder)
    • session state (hier werden Aktionen immer in einer Session ausgeführt, in der sich ein Client authentifiziert hat - zB WebServer mit Session à la Cookies)
  • wie/wo kann man den Server finden?
    • Name oder Directory Server
    • Well known Port addresses(0-1023)

Arten von Servern:

  • multithreaded server: bestehend aus einem dispatcher und mehreren worker threads. Der dispatcher thread wartet auf eingehende anfragen, und startet pro anfrage einen worker thread, an welchen die anfrage weitergereicht wird. Somit ist es möglich, dass während eine Anfrage bearbeitet wird, der dispachter thread wieder auf neue Anfragen warten kann.
  • single-threaded server: Bestehend aus nur einem einzigen Thread, welcher die Anfragen entgegennimmt, bearbeitet und das Ergebnis an den Client sendet. Die Implementierung ist recht einfach, jedoch kann immer nur ein Client zur selben Zeit bearbeitet werden.
  • finite-state machine: Ebenfalls nur ein Thread. Die finite state machine hält eine Tabelle mit Ergebnissen bereit, sodass eine Anfrage, wo das Ergebnis bekannt ist, sofort beantwortet werden kann. Falls das Ergebnis nicht in der Tabelle enthalten ist, wird eine Anfrage an die Festplatte geschickt, jedoch sofort weitergearbeitet. Wenn das Ergebnis dieser Anfrage eintrifft, wird es in die Tabelle eingetragen und an den Client geschickt.

Beim Einsatz von Multi-Threaded Servern ist zu beachten:

  • Wer erzeugt den Thread?
  • Wann wird der Thread erzeugt?
  • Fixe Anzahl an Threads?
  • Verschiedene Architekturen sind möglich(Thread-per-request, Thread-per-connection, Thread-per-object)
  • Synchronisation

Die Thread-Erzeugung ist sehr teuer. Die Kosten der Thread-Erzeugung können verringert werden, wenn man einen Thread für mehrere Anfragen verwendet. Eine fixe Anzahl an Threads können schon beim Starten erzeugt and und den einkommenden Anfragen zugewiesen werden.


3.Fehlermodelle und k-fault-tolerance[Bearbeiten]

Frage: Wozu benötigt man Fehlermodelle ganz allgemein? Geben Sie verschiedene Fehlermodelle für "fail-controlled systems" an und diskutieren Sie diese v.a. hinsichtlich des benötigten Aufwandes für die Maskierung. Inwiefern ist es u.U. heikel zu spezifizieren, daß ein System "k-fault-tolerant" sein soll?

{{#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*Fehlermodelle und k-fault-tolerance\s*/si}}

Achtung: Diese Fehlermodelle sind falsch, wie wir in der Prüfung vom 17.01.2011 leider feststellen mussten. Siehe http://www.informatik-forum.at/showthread.php?85245-After-test-17.01.2011&p=690539&viewfull=1#post690539


Fehler werden in Klassen unterteilt, um die Auswirkungen besser einschätzen zu können.

  • crash failure: ein server stürtzt ab und gibt keine Rückmeldungen mehr, bis er neugestartet wird. Bis der crash eingetroffen ist, arbeitet der Server korrekt
  • omission failure: Ein Server antwortet nicht auf Anfragen. Das kann verschiedene Gründe haben, beispielsweise, dass er nie die Anfrage erhalten hat (receive omission). Oder der Server hat die Anfrage erhalten, beantwortet, ist aber nicht in der Lage die Antwort zu versenden (send omission)
  • timing failure: Wenn eine Antwort länger als eine definierte Response-Time benötigt, spricht man von einem Timing failure
  • response failure: wenn die Antwort eines Servers inkorrekt ist. Es gibt 2 Arten von response Fehlern: value failure der Server liefert eine falsche Antwort (Suchmaschine liefert webseiten, nach welchen nicht gesucht wurde); state transition failure: passieren, wenn der Server unerwartet auf eine Anfrage reagiert (z.B: ein Server erhält eine Anfrage, welche er nicht erkennen kann und daraus Aktionen startet, welche niemals passieren dürften)
  • arbitrary failure/bizantine failure: ist eine sehr schwerwiegende klasse von fehlern, wenn z.b. ein Server eine Antwort liefert, welche niemals erstellt werden dürfte (die aber nicht als fehlerhaft erkannt werden kann)


Richtige Antworten für Fehlermodelle:


  • fail-halt (fail-stop) system: Halting failures only. Often: halting can be detected; d.h. der Server stürzt ab und teilt das entweder vorher mit oder es ist für andere, von ihm abhängige Prozesse ersichtlich, dass er abgestürzt ist.
  • fail-passive (fail-silent) system: Stuck output instead of erratic output (Silence as opposed to babbling). Often crash failures. Other processes may incorrectly conclude that a server has halted whereby the server is only unexpectedly slow!; Server crashed, aber teilt dies nicht mit (häufig!), hier ist es schwierig festzustellen, ob der Server tatsächlich down oder nur langsam ist (oder das Problem ganz woanders liegt, etwa in der Netzwerkverbindung).
  • fail-consistent system: No byzantine failures.
  • fail-inconsistent system: Any type of failure.
  • fail-safe system: All minor failures, no catastrophic consequences expected.; Output des Systems ist falsch, kann aber von anderen Prozessen als solcher erkannt werden.

Ein System ist k-Fehler-tolerant, wenn es k Fehler verkraften, aushalten kann. Zum Beispiel ist ein Server mit 3 Netzteilen in Bezug auf diese 2-fault tolerant: 2 Netzeile können ausfallen, aber die Stromversorgung ist immer noch gewährleistet!

Hauptproblem in der Spezifikation von k-fault-tolerant liegt v.a. darin, dass man nicht ohne weiteres sagen kann, was k tatsächlich für eine Zahl ist. Kann man zB über Erfahrungswerte festlegen, aber auch das ist natürlich keine Garantie.

Aufwand für die Maskierung:

  • fail-stop or fail-silent: k+1: Wenn man 3 Systeme hat und 1 fällt aus, braucht man genau 1 weiteres um es zu ersetzen, wenn man weiß, dass es down ist.
  • fail-passive (fail-consistent) with or w/o distributed agreement: 2k+1: Wenn man 3 Systeme hat, eines abstürzt dies aber nicht mitteilt, braucht man 2 Systeme, die eine Mehrheit liefern.
  • arbitrary (malicious, two-faced, byzantine) without distributed agreement: 2k+1: Wie fail-passive - wenn man 3 Systeme hat, eines davon lügt, und man schaut sich die Ergebnisse der drei nachher an, braucht man mindestens 2 um zu sagen, was das korrekte Ergebnis ist
  • byzantine (arbitrary failures, malicious, two-faced) with distributed agreement: 3k+1: Hat man 3 Systeme, bei denen das Ergebnis von einem oder mehreren Systemen davon abhängt, wie die anderen entscheiden, kann man mit 3 kein garantiert korrektes Ergebnis finden -> man braucht min. 4 (siehe hierzu #"Byzantinische Generäle" )
  • It is therefore wise to provide enough errordetection logic inside a component to guarantee failsilent behaviour at the system level!


4.Publish/Subscribe[Bearbeiten]

Frage: Erläutern Sie das Grundprinzip von publish/subscribe als Kommunikations-/Koordinationsmechanismus. Worin bestehen die Möglichkeiten aber auch die Probleme dieses Mechanismus (v.a. dessen Implementierung). Erläutern Sie weiters JINI und JavaSpaces als konkrete Technologien.

{{#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*Publish\/Subscribe\s*/si}}

Publish/Subscribe-Systeme, bei denen Nachrichten mit einem gewissen Typ versehen werden. Diese werden an alle Prozesse zugestellt, die sich dafür interessieren (indem sie sich vorher dafür registriert haben). Funktioniert nur wenn beide Prozesse aktive sind. Dieser Ansatz wird als Meeting-based bezeichnet. Publish/Subscribe systeme sind referentiell ungekoppelt, und können temporal ungekoppelt (Message wird gespeichert und zugestellt, sobald Subscriber online) oder gekoppelt (Subscriber muss online sein um Message zu empfangen)

Vorteile: Der Publisher muss sich keine Gedanken um die Systemtopologie machen und um die Zustellung, sondern kann einfach eine Nachricht in das System schicken. Besser Skalierbar als ein traditionelles Client-Server Modell.

Nachteile: Der Publisher weiß nicht, wer die Nachrichten empfangen soll und kann nicht feststellen, ob alle, die die Nachricht erhalten sollen sie auch erhalten haben. Wenn es viele Publisher, aber nur einen Subscriber gibt, und der Subscriber crasht, gehen die Nachrichten verloren.

(Anm. koDiacc: Hab jetzt kein Buch zur Hand, aber müsste es nicht heißen: Wenn es viele Subscriber (=Abbonnementen) gibt, aber nur einen Publisher (Veröffentlicher), und der Publisher "baden" geht, stehen die Subscriber mit leeren händen da?)


Anm.: ich glaube, dass hier außerdem ("v.a. dessen Implementierung") das Broker-Konzept erklärt werden soll. Hier ein Versuch (hauptsächlich aus dem deutschen Buch (2008, S.176) kopiert):

Ein Broker verwaltet einen Vorrat aus Regeln und Programmen, die eine Nachricht des Typs T1 in eine Nachricht des Typs T2 umwandeln können. Das Problem besteht in der Regeldefinition und Programmentwicklung. Als kommerzielles Produkt werden Broker oftmals irreführend als "intelligent" bezeichnet. Broker werden jedoch mit umfangreichen Entwicklungswerkzeugen mitgeliefert, und der Vorrat an Regeln und Programmen muss weiterhin von Experten gefüllt werden. Die "Intelligenz" des Systems liegt also in Wirklichkeit in den Köpfen von Experten/Entwicklern.


Jini setzt Generative Communication um. Es speichert Tupel von Java-Objekten in einem Shared Dataspace (JavaSpace), aus dem sie von interessierten Prozessen durch Matching mit einem Template (ebenfalls ein Tupel aus Objekten, das aber nicht vollständig ausgefüllt sein muss) wieder abgefragt werden können. Das Abfragen kann dabei auch das gelesene Tupel auch gleich aus dem Datastore entfernen (take-Operation). Neben dem Zugriff auf JavaSpaces unterstützt Jini auch noch Naming und Security (Authentification, so dass nur berechtigte Prozesse auf den Datastore zugreifen können).. [ausreichend??]


5. NTP[Bearbeiten]

Es war eine Kommunikation zwischen NTP Server und Client gegeben. Also die 4 Punkte T1 am Client (00:15, Server steht zum gleichen Zeitpunkt auf 00:00!), T2 am Server (00:01), T3 am Server (00:05) und T4 am Client (00:51). Frage 1 war dabei was für ein Offset/neue Zeit bei dieser einzelnen Berechnung (anstatt 8 mal) dann rauskommt. Frage 2 war, wieviel die Abweichung tatsächlich beträgt und wieso der Unterschied so groß ist. Frage 3 war, ob der Client die tatsächliche Zeit in einem Intervall abschätzen kann und falls ja, wie.