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

Was ist Middleware[Bearbeiten | Quelltext bearbeiten]

{{#lsth:TU Wien:Verteilte Systeme VO (Göschka)/Fragenkatalog Wiki|Was ist Middleware}}

Frage: Was ist Middleware? Welche Anforderungen stellt man an Middleware? Welche Services soll Middleware bieten? Erläutern Sie den Zusammenhang zwischen Middleware und Architectural styles.

Middleware ist eine Softwarekomponente die viele oft von Verteilten Systemen benötigte Services zusammenfasst und in parametrisierbarer Form anbietet. Man muss daher gleiche Funktionalitäten nicht immer neu implementieren. Die Schicht ist logisch zwischen Application- und Transportlayer einzuordnen. Services von Middleware sind z.B. Verschlüsselung, Authentifizierung, Security, Replikation, Access-Transparenz, Naming etc. Man kann annehmen, dass sich die Entwicklung von Middleware für Verteilte Systeme weitgehend mit der Behandlung zusätzlicher Funktionalität unabhängig von Anwendungen beschäftigt. Die Middleware bildet eine Schicht zwischen Anwendungen und verteilten Plattformen. Ein wichtiger Zweck besteht darin einen Grad von Verteilungstransparenz zu bieten, der in einem gewissen Maß die Verteilung von Daten, die Verarbeitung und die Steuerung vor den Anwendungen verbirgt. Wenn Middleware nach einem bestimmten Architekturstil geformt ist, hat das den Vorteil, dass der Entwurf von Anwendungen einfacher werden kann, eventuell ist die Middleware dann jedoch nicht mehr optimal für das geeignet was der Anwendungsentwickler im Sinn hat.

Important styles of architecture for distributed systems (Folien)

Layered architectures (OSI)
Object-based architectures (and components)
Data-centered architectures (file based, database, resourceful WS, ...)
Event-based architectures
.... and combinations thereof

Anforderungen: (ich glaube das ist eher gefragt als die Anforderungen unten)

Unterstützt Transparenz
Unterstützt Offenheit
Gibt die Möglichkeit Skalierbarkeit hinein zu bringen
Unterstützt Wartbarkeit
Life-cycle Management für die Komponenten (aktivieren/deaktivieren)
Unterstützt Interface Definition
Liefert Kommunikationsgrundlagen
Liefert Unterstützung für Concurrency (Thread library)

Services:

Kommunikationsservice für Zugriffstransparenz
Naming
Persistence Service für die Persistence Transparenz
Verteilte Transaktionen
Replikationen um Failure Transparenz zu unterstützen
Securitymechanismen: Authentication, Authorisation

Anforderungen an Middleware: Middleware ist nicht immer ideal für die Anwendungen, die Applikationsentwickler im Sinn hatten: CORBA hat z.B. nur Objekte bereitgestellt, die von remote clients aufgerufen werden konnten. Es hat sich herausgestellt, dass nur diese Form der Interaktion zu einschränkend ist. Also wurde Messaging hinzugefügt. Das hinzufügen von Features kann aber zu einer aufgeblasenen Middleware führen. Und obwohl Middleware Verteilungstransparenz bereitstellen sollte, sollten bestimmte Lösungen auch an die Applikationsanforderungen anpassbar sein. Eine Lösung wäre, unterschiedliche Middleware-Versionen zu entwerfen. Eine andere Möglichkeit ist Middlewaresysteme leicht konfigurierbar und adaptierbar zu gestalten.

Replicated-write Protokolle[Bearbeiten | Quelltext bearbeiten]

{{#lsth:TU Wien:Verteilte Systeme VO (Göschka)/Fragenkatalog Wiki|Replicated-write Protokolle}}

Frage: Erläutern Sie die Funktionsweise der "replicated-write" Protokolle. Bewerten und vergleichen Sie die verschiedenen Arten. Welche Probleme können bei "Active Replication" auftreten? Erklären Sie "quorum-based" Replikationsprotokolle und geben Sie die Bedingungen an, um Read-Write und Write-Write Konflikte zu verhindern.

Im Gegensatz zu Primary-Based Protokollen erlauben Replicated-Write-Protokolle den Zugriff auf beliebigen Replikate. Die Änderungen werden dann an alle anderen Replikate propagiert, entweder über Active Replication (die Operationen werden ausgeschickt und überall nachvollzogen – nur bei deterministischen Operationen möglich; gleiche Reihenfolge wird durch totally-ordered Multicast und deterministisches Thread Scheduling erreicht) oder über quorumbasierte Ansätze (es wird immer eine bestimmte Anzahl von Replikaten gelesen bzw. geschrieben, so dass es keine Schreib/Schreib- oder Lese/Lese-Konflikte geben kann ).

lese/schreib Zugriff verhinden Qr+Qw>n
schreib/schreib Zugriff verhindern Qw>n/2

Eine Spezialform von Replicated-Write-Protokollen ist Coordinator-Cohort-Replication. Dabei wird die Anfrage an ein (beliebiges) Replikat gesendet, das die Updates synchron an alle anderen propagiert. Dazu ist ein distributed-Locking-Mechanismus erforderlich.

Alternative Antwort (die ich persönlich verständlicher finde):

Schreib-operationen werden im Gegensatz zu primary-based Protokollen an vielen replicas ausgeführt.

active replication: Die Operation wird an jedes Replica gesendet. Das Problem ist, dass Operationen überall in der selben Reihenfolge geliefert werden müssen. Was es daher braucht ist einen "totaly-ordered multicast- Mechanismus". Hier gibt es aber in groß skalierten Systemen Probleme. Als Alternative kann ein zentraler Koordinator (Sequencer) verwendet werden. Meistens ist eine Mischung aus beiden nötig.

quorum-based protocolls: Hier wird ein Voting verwendet. Bsp.: Um ein File zu aktualisieren, muss der Client zuerst mindestens die Hälfte der Server plus 1 dazu bringen dem Update zuzustimmen. Um das File zu lesen muss der Client wiederum mindestens die Hälfte der Server plus eins dazu bringen ihre Versionsnummern des Files zu schicken. Wenn alle Versionsnummer gleich sind, muss es sich um die aktuelle Version handeln.

Eine Verallgemeinerung hierfür ist das Gifford's scheme, das folgenden Regeln folgt: Der Client muss eine Mehrheit der Server mit den Update versorgen. Beim Lesezugriff muss auch wieder von zumindest der Anzahl der nicht upgedaten Server +1 gelesen werden. Dabei gewinnt die Dateneinheit mit der höchsten Versionsnummer.

1. Nr + Nw > N (verhindert read-write Konflikte) 2. Nw > N/2 (verhindert write-write Konflikte)

Location Service[Bearbeiten | Quelltext bearbeiten]

{{#lsth:TU Wien:Verteilte Systeme VO (Göschka)/Fragenkatalog Wiki|Location Service}}

Frage: Wie funktioniert in flachen Namensräumen das Location Service? Geben Sie das Grundprinzip möglicher Lösungen an und gehen Sie dabei auch auf die Begriffe Mobility und Discovery ein. Erläutern Sie Vor- und Nachteile bei der Verwendung von "Forwarding Pointers". Wie funktionieren "Home-based approaches" für mobile Geräte?

Ein Location Service bezeichnet ein Two-Level mapping zum Übersetzen von Namen in Adressen über sog. Identities.

In einem Ad hoc Netzwerk, wie z.B. P2P, müssen Rechner Services und Resourcen ankündigen bzw. auffinden können (discovery). Ein Location Service kann dazu benutzt werden, Services zu registrieren und aufzufinden. Dadurch wird ein hoher Grad an Mobility erreicht, da ein Host nicht mehr über eine fixe Adresse (IP) angesprochen wird. Location Services unterscheiden sich von NS und Directory Services durch die Anforderung, dass sie sich oft/schnell ändern.

Lösungen:

Broadcast und Multicast:

Wird nach einer Entität gesucht, sendet man per Broadcast Anfragen an alle Geräte im Netzwerk ob sie diese Entität haben. Wenn ja wird die Adresse des Eintrittspunkts zurückgeliefert, ansonsten die Anfrage einfach ignoriert. Bsp.: ARP Dies sorgt jedoch für jede Menge unnötigen Traffic und die Hosts werden ständig mit Anfragen nach Entitäten belästigt. Eine Lösung wäre der Wechsel auf Multicast, durch die nur eine begrenzte Anzahl an Hosts die Anfrage erhält.

Forwarding Pointers:

Ein Ansatz um Mobility zu erreichen ist die Verwendung von Forwarding Pointers. Wenn eine Entität seinen Ort ändert, lässt sie eine Referenz zurück, welche auf ihren neuen Ort zeigt.

Vorteil: sehr einfach. Sobald eine Entität lokalisiert wurde, kann ein Client die aktuelle Adresse nachschlagen, indem er der Kette der Referenzen folgt.

Nachteil: Lange Ketten, möglicherweise viele Zwischenschritte notwendig, eine falsche Referenz unterbricht die gesamte Kommunikation (broken link). Zwischenstandorte müssen ihren Teil der Kette so lange wie möglich halten.

Daher müssen die Ketten so kurz wie möglich gehalten werden.

Homebased Aproach:

Ein Ansatz um Mobility in großen Netzwerken zu erreichen ist die Verwendung von Homebased Approaches. Die Homelocation speichert dabei immer den aktuellen Standort einer Entität. Ändert die mobile Entität ihren Standort registriert sie eine Care-Of-Address beim Home-Agent.

Ein Client, der den aktuellen Standort nicht kennt, kann ihn also immer bei der HL erfragen und anschließend direkt kommunizieren.

Logical Clocks[Bearbeiten | Quelltext bearbeiten]

{{#lsth:TU Wien:Verteilte Systeme VO (Göschka)/Fragenkatalog Wiki|Logical Clocks}}

Frage: Was sind die Gründe für die Verwendung von Logical Clocks? Erklären Sie die Unterschiede zu den Physical Clocks. Was ist die "happened-before" Beziehung und wie funktionieren die "Lamport-Timestamps"?

Verwendung von Logical Clocks: Es ist meist ausreichend, wenn alle die selbe Zeit haben, auch wenn diese nicht mit der realen Zeit zusammenpasst. Es ist oft nur die Reihenfolge der Operationen wichtig.

Unterschiede: Die physikale Uhr ist die "reale" Uhr (Kristall-Oszillator, mittlere Sonnensekunde, Atomuhr (TAI, International Atomic Time), UTC (Universal Coordinated Time), wobei eine Logische Uhr eine Reihung der Ereignisse darstellt.

"happend-before"-Beziehung: a -> b wird gelesen als "a passiert vor b". Dies bedeutet, dass alle Prozesse wissen, dass a vor b eingetreten ist. Zwei Situationen:

wenn a und b im selben Prozess sind, und a tritt vor b ein dann ist "a->b" = true
wenn a das Ereignis darstellt, dass eine Nachricht von einem Prozess gesendet wird, und b ist das Ereignis, dass die Nachrricht von einem anderen Prozess empfangen wird. Eine Nachricht kann nicht empfangen werden, bevor sie gesendet wird (und auch nicht gleichzeitig).

Dies ist eine transitive Relation: a -> b und b -> c, dann a -> c

Lamport-Timestamps: Ereignisse werden nur durchnummeriert. Potentiell kausal abhängige Ereignisse (im Sinne der "happend-before"-Beziehung) bekommen dabei Nummern so zugewiesen, dass das abhängige Ereignis eine größere Nummer hat als die Ursache, und dass diese Nummern bei allen Prozessen gleich sind. Jeder Prozess hat seinen eigenen Counter (logische Uhr). Bei jedem Ereignis (Berechnung, Senden, Empfangen) wird er um 1 erhöht und hängt diese Zahl der Nachricht an. Empfänger setzt seinen Counter auf das Maximum aus seinem aktuellen Counter und der mitgeschickten Zahl, anschließend erhöht er seinen Counter um 1. Es muss immer gelten:

T(b) > T(a), falls a und b in dieser Reihenfolge im gleichen Prozess stattfinden

Eigenschaften:

2 aufeinanderfolgende Ereignisse a und b im gleichen Prozess: T(a) < T(b)
Der Empfang einer Nachricht hat immer höhere Zahl als das Senden
Die Relation ist transitiv abgeschlossen

Es kann jedoch nicht auf kausale Abhängigkeiten geschlossen werden, d.h. T(a) < T(b) bedeutet nicht unbedingt dass a->b gilt (nur in die andere Richtung).

Key Distribution Centre (KDC)[Bearbeiten | Quelltext bearbeiten]

{{#lsth:TU Wien:Verteilte Systeme VO (Göschka)/Fragenkatalog Wiki|Key Distribution Centre}}

Frage: Was ist ein Key Distribution Centre (KDC), wozu wird es eingesetzt und welchen Vorteil bietet es? Geben Sie ein konkretes Verfahren zur gegenseitigen Authentifizierung von Kommunikationsteilnehmern mit Hilfe eines KDC an und beschreiben Sie für jeden Schritt, wer sich wem gegenüber bereits authentifiziert hat.

Eines der größten Probleme bei Shared Secret Key Authentications ist die Skalierbarkeit der Systeme. Es müssen einfach zu viele Schlüssel gewartet werden. Bei N Hosts im System muss jeder der Hosts mit N-1 anderen einen Secret Key teilen. Im System gibt es dann N(N-1)/2 Schlüssel und jeder Host muss N-1 warten.

Eine Alternative dazu (zur "Schlüsselwartung") stellt das KDC dar (Key Distribution Center). Es teilt einen Secret Key mit jedem Host aber die Hosts untereinander müssen keine Secret Keys mehr teilen. Es müssen also nur noch N Keys gewartet werden.

Authentifizierung mit KDC:

Die Grundidee ist folgende: das KDC händigt jedem der Teilnehmer einen Key aus, mit dem diese dann untereinander kommunizieren können.

Ablauf:

Alice sendet eine Message an das KDC wo sie bekannt gibt, mit wem sie sprechen will
das KDC retouniert einen Shared Secret Key Ka,b an Alice und Bob, welcher mit dem Secret Key des jeweiligen Empfängers verschlüsselt wurde

Hierbei gibt es nur ein Problem: Alice könnte den Schlüssel schon bekommen haben und eine Kanal zu Bob aufmachen, obwohl dieser den Schlüssel noch nicht hat (oder noch nicht dazu bereit ist). Abhilfe schafft folgendes angepasste Protokoll.

Hierbei erhält Bob nicht vom KDC sondern von Alice seinen Schlüssel übermittelt. Dieser Ansatz wird als Ticketing bezeichnet (die Message Kb,kdc(Ka,b) ist das Ticket). Auch hier kann nur Bob etwas mit dem Ticket anfangen, da nur er den Private Key zum Entschlüsseln hat.

Ein konkretes Protokoll für die Authentifizierung, welches nun diesen Ansatz verwendet, ist das Needham-Schroeder-authentication protocol.