Verteilte Systeme - Exam

Aufgabe 1)

Ein Unternehmen plant den Einsatz eines neuen verteilten Systems, um seine Datenverarbeitung effizienter zu gestalten. Das System soll mehrere unabhängige Computer verwenden, die miteinander kommunizieren und kooperieren, um komplexe Analyseaufgaben durchzuführen. Das Unternehmen hat spezifische Anforderungen an Skalierbarkeit, Transparenz, Zuverlässigkeit, Heterogenität, Parallelität und verteilte Kontrolle gestellt. Du wirst gebeten, die Machbarkeit dieses Projekts und die potenziellen Herausforderungen zu bewerten.

a)

Aufgabe 1: Erkläre, wie ein verteiltes System die Anforderung an Skalierbarkeit erfüllen kann und diskutiere mögliche Herausforderungen im Zusammenhang mit Skalierbarkeit. Beziehe dich auf konkrete Architekturen und Technologien, die zur Lösung dieser Probleme beitragen könnten.

Lösung:

Aufgabe 1:

Um die Anforderung an Skalierbarkeit in einem verteilten System zu erfüllen, sollten mehrere Aspekte berücksichtigt werden. Ein verteiltes System kann skalierbar sein, wenn es in der Lage ist, durch die Hinzufügung zusätzlicher Ressourcen (wie z.B. weitere Computer) linear oder nahezu linear seine Leistung zu steigern. Hier sind einige Möglichkeiten, wie Skalierbarkeit erreicht werden kann:

• Horizontale Skalierung: Dies bedeutet, dass die Leistung des Systems durch Hinzufügen weiterer Einheiten (z.B. Server oder Knoten) erhöht wird. Technologien wie Apache Hadoop, Apache Kafka und Docker-Container unterstützen diese Skalierungsstrategie.
• Verwendung von Load Balancern: Load Balancer verteilen die eingehenden Anfragen gleichmäßig auf unterschiedliche Server, um Überlastungen zu vermeiden und die Effizienz zu maximieren. Systeme wie NGINX und HAProxy sind häufig verwendete Lösungen.
• Microservices-Architektur: Durch die Aufteilung der gesamten Anwendung in unabhängige, aber kommunizierende Microservices kann jede Einheit individuell skaliert und aktualisiert werden. Technologien wie Spring Boot und Kubernetes ermöglichen diese Architektur.

Herausforderungen im Zusammenhang mit der Skalierbarkeit:

• Netzwerküberlastung: Bei der horizontalen Skalierung kann es zu Überlastungen im Netzwerk kommen, insbesondere wenn viele Knoten gleichzeitig kommunizieren. Technologien wie Content Delivery Networks (CDNs) und Cache-Strategien (z.B. Redis) können helfen, die Last zu verteilen.
• Datenkonsistenz: In einem verteilten System kann es schwierig sein, eine konsistente Informationsbasis sicherzustellen. CAP-Theorem gibt Aufschluss über die Balance zwischen Konsistenz, Verfügbarkeit und Partitionstoleranz. Systeme wie Apache Cassandra oder Amazon DynamoDB bieten konfigurierbare Konsistenzmodelle an.
• Fehlerisolierung und Handhabung: In einem großen, verteilten System sind einzelne Komponenten fehleranfällig. Circuit Breaker-Muster, z.B. mit Hilfe von Netflix Hystrix, können verhindern, dass Fehler in einem Teil des Systems das gesamte System beeinträchtigen.
• Synchronisation und Koordination: In einem verteilten System müssen häufig komplexe Koordinationsaufgaben gelöst werden. Technologien wie Zookeeper können dabei unterstützen, synchronisierte Zustände zwischen Knoten zu verwalten.

Durch den Einsatz dieser Architekturen und Technologien kann ein Unternehmen ein skalierbares und effizientes verteiltes System aufbauen, das den Anforderungen gerecht wird. Dennoch sollte stets eine sorgfältige Planung erfolgen und potenzielle Probleme proaktiv angegangen werden.

b)

Aufgabe 2: Beschreibe umfassend, wie Transparenz in einem verteilten System gewährleistet werden kann. Zeige auf, welche Arten von Transparenz (z.B. Ortstransparenz, Zugriffstransparenz, Fehlertoleranztransparenz) erforderlich sind und welche Mechanismen oder Protokolle zur Implementierung dieser Transparenz beitragen könnten.

Lösung:

Aufgabe 2:

Um Transparenz in einem verteilten System zu gewährleisten, muss das System so gestaltet sein, dass die Komplexität der verteilten Natur vor den Benutzern und Entwicklern verborgen bleibt. Dies umfasst mehrere Arten von Transparenz, die sicherstellen, dass Benutzer und Anwendungen keine Unterschiede zwischen einem zentralisierten und einem verteilten System wahrnehmen. Hier sind die wichtigsten Arten von Transparenz und die Mechanismen oder Protokolle, die zu deren Umsetzung beitragen können:

• Ortstransparenz: Die Benutzer und Anwendungen sollten nicht wissen (oder sich darum kümmern müssen), wo sich die Ressourcen physisch befinden. Mechanismen, die diese Art von Transparenz unterstützen, umfassen verteilte Verzeichnisse und Namensdienste wie DNS oder Apache Zookeeper. Diese Dienste ermöglichen es, Ressourcen durch logische Namen anstelle physischer Adressen zu identifizieren.
• Zugriffstransparenz: Die Art und Weise des Zugriffs auf die Ressourcen sollte unabhängig davon sein, ob die Ressourcen lokal oder entfernt sind. Mechanismen zur Unterstützung dieser Transparenz umfassen Protokolle wie Remote Procedure Call (RPC) und RESTful APIs. Technologien wie XML, JSON und gRPC können ebenfalls dabei helfen.
• Fehlertoleranztransparenz: Das System sollte Fehler so behandeln können, dass sie für die Benutzer und Anwendungen unsichtbar sind. Dies kann durch Replikation, automatische Fehlererkennung und -korrektur erreicht werden. Technologien wie Raft und Paxos für Konsensbildung sowie Mechanismen zur automatischen Fehlertoleranz, wie sie z.B. in Apache Kafka oder Hadoop implementiert sind, können hilfreich sein.
• Replikationstransparenz: Die Benutzer sollten nicht wissen müssen, dass ein Objekt oder Dienst repliziert ist, um die Verfügbarkeit und Zuverlässigkeit zu erhöhen. Das System sollte alle Replikate konsistent halten. Apache Cassandra oder Amazon DynamoDB sind Beispiele für Datenbanken, die diese Transparenz bieten.
• Leistungstransparenz: Das System sollte so gestaltet sein, dass die Nutzer keine signifikanten Leistungseinbußen bemerken, selbst wenn Ressourcen an verschiedenen geografischen Standorten vorhanden sind. Lastverteilungsmechanismen und geografisch verteilte Inhaltsbereitstellungsnetzwerke (CDNs) wie CloudFlare oder Amazon CloudFront können zur Gewährleistung der Leistungstransparenz beitragen.
• Skalierungstransparenz: Das System sollte seine Größe ändern können, ohne dass die Nutzer oder Anwendungen dies wahrnehmen. Die Vertikalisierung und Horizontalisierung von Ressourcen durch den Einsatz von Container-Orchestrierungssystemen wie Kubernetes oder Docker Swarm können dies unterstützen.

Zur Implementierung dieser Transparenzarten sind verschiedene Mechanismen und Protokolle erforderlich:

• Mittels Software-Middleware: Middleware wie Apache Kafka, RabbitMQ oder gRPC kann dabei helfen, verschiedene Arten von Transparenz umzusetzen, indem sie eine einheitliche Kommunikationsschicht bieten.
• Service-Discovery-Protokolle: Diese Protokolle, wie z.B. Consul oder etcd, helfen Systemen dabei, die Verfügbarkeit und Position von Diensten dynamisch zu ermitteln und sie für transparente Zugriffe bereitzustellen.
• Verteilte Transaktionsprotokolle: Protokolle wie Two-Phase Commit (2PC) und Three-Phase Commit (3PC) können zur Sicherstellung der Transaktionsintegrität in einem verteilten System beitragen.

Durch den strategischen Einsatz dieser Mechanismen und Technologien können Unternehmen die erforderliche Transparenz in ihrem verteilten System sicherstellen und so eine nahtlose und benutzerfreundliche Datenverarbeitung ermöglichen.

Aufgabe 2)

Protokolle der Transportschicht: Die Protokolle der Transportschicht, insbesondere TCP und UDP, spielen eine entscheidende Rolle für den Datentransfer zwischen Hosts. TCP (Transmission Control Protocol) ist für eine zuverlässige und verbindungsorientierte Datenübertragung verantwortlich und garantiert die Reihenfolge und Integrität der Datenübermittlung, was sich für Anwendungen wie HTTP und FTP eignet. TCP verwendet Mechanismen wie Flow-Control, Segmentierung, Sequenznummern und ACKs (Acknowledgements) für die Fehlerkorrektur. Andererseits bietet UDP (User Datagram Protocol) eine unzuverlässige und verbindungslose Datenübertragung, ist jedoch schneller und ressourcenschonender, was ideal für Echtzeitanwendungen wie VoIP und DNS ist. UDP verzichtet auf Verbindungsaufbau- und Abbauprozesse und hat daher weniger Overhead. Besonders wichtig ist die Wahl des geeigneten Protokolls abhängig von den jeweiligen Anwendungsanforderungen in Bezug auf Zuverlässigkeit und Geschwindigkeit.

a)

Anwendungsfallanalyse: Ein Unternehmen plant, eine neue Anwendung zu implementieren, die eine Echtzeitübertragung großer Datenmengen (z.B. Videostreaming) erfordert. Erläutere, welches Transportschicht-Protokoll (TCP oder UDP) in diesem Szenario besser geeignet ist, indem Du die spezifischen Anforderungen und die Eigenschaften beider Protokolle analysierst. Begründe Deine Wahl ausführlich.

Lösung:

Anwendungsfallanalyse:

Ein Unternehmen plant, eine neue Anwendung zu implementieren, die eine Echtzeitübertragung großer Datenmengen, wie zum Beispiel Videostreaming, erfordert. Um das geeignete Transportschicht-Protokoll (TCP oder UDP) auszuwählen, müssen wir die spezifischen Anforderungen des Anwendungsfalls sowie die Eigenschaften beider Protokolle analysieren.

• Eigenschaften von TCP: - Zuverlässige und verbindungsorientierte Datenübertragung - Garantiert die Reihenfolge und Integrität der Datenübermittlung - Eignet sich gut für Anwendungen, die eine exakte Datenübertragung benötigen (z.B. HTTP, FTP) - Mechanismen wie Flow-Control, Segmentierung, Sequenznummern und ACKs für die Fehlerkorrektur - Höherer Overhead aufgrund der Verbindungsverwaltung und Fehlerkorrektur, was zu einer geringeren Geschwindigkeit führt
• Eigenschaften von UDP: - Unzuverlässige und verbindungslose Datenübertragung - Keine Garantie für die Reihenfolge oder Integrität der Daten - Schneller und ressourcenschonender im Vergleich zu TCP - Ideal für Echtzeitanwendungen, die eine schnelle Datenübertragung benötigen und bei denen der Verlust einzelner Datenpakete unkritisch ist (z.B. VoIP, DNS) - Weniger Overhead, da keine Verbindungsaufbau- und Abbauprozesse notwendig sind

Analyse der Anwendungsanforderungen:

• Die Anwendung erfordert eine Echtzeitübertragung großer Datenmengen (Videostreaming), weshalb Geschwindigkeit und eine geringe Verzögerung (Latenz) von entscheidender Bedeutung sind.
• Beim Videostreaming ist es oft tolerierbar, wenn einzelne Datenpakete verloren gehen oder nicht in der richtigen Reihenfolge ankommen, solange dies nicht zu häufig passiert und das Gesamtstreaming-Erlebnis nicht beeinträchtigt wird.

Begründung der Protokollwahl:

Aufgrund der oben genannten Eigenschaften und Anwendungsanforderungen ist UDP in diesem Szenario besser geeignet als TCP. Folgende Gründe unterstützen diese Wahl:

• UDP bietet eine schnellere Datenübertragung und geringere Latenzzeiten, was für Echtzeitanwendungen wie Videostreaming essentiell ist.
• Die fehlende Garantie für die Reihenfolge und Integrität der Daten ist beim Videostreaming weniger kritisch, da kurze Datenverluste vom Benutzer meist nicht bemerkt werden.
• Weniger Overhead durch den Verzicht auf Verbindungsaufbau- und Abbauprozesse sowie aufwendige Fehlerkorrekturmechanismen, was die Effizienz und Geschwindigkeit erhöht.

Daher sollte das Unternehmen für die neue Anwendung, die eine Echtzeitübertragung großer Datenmengen erfordert, UDP als Transportschicht-Protokoll wählen.

b)

Fehlertoleranz und Datenintegrität: Angenommen, Du entwickelst eine File Transfer Anwendung bei der Datenintegrität und Zuverlässigkeit oberste Priorität haben. Beschreibe, wie TCP genutzt wird, um eine zuverlässige Übertragung zu gewährleisten. Erkläre dabei im Detail die Funktion von Sequenznummern und ACKs (Acknowledgements). Simuliere außerdem ein einfaches Szenario, in dem ein Datenpaket verloren geht und erkläre, wie TCP dieses Problem löst.

Lösung:

Fehlertoleranz und Datenintegrität:

Wenn Du eine File Transfer Anwendung entwickelst, bei der Datenintegrität und Zuverlässigkeit oberste Priorität haben, ist TCP (Transmission Control Protocol) das geeignete Protokoll. TCP bietet Mechanismen, um eine zuverlässige und verbindungsorientierte Datenübertragung sicherzustellen. Im Folgenden wird beschrieben, wie TCP genutzt wird, um eine zuverlässige Übertragung zu gewährleisten, und welche Funktion Sequenznummern und ACKs (Acknowledgements) dabei spielen.

• Sequenznummern: TCP teilt die Daten in Segmente und nummeriert jedes Segment mit einer Sequenznummer. Diese Sequenznummern ermöglichen es dem Empfänger, die Segmente in der richtigen Reihenfolge wieder zusammenzusetzen, selbst wenn diese in einer anderen Reihenfolge ankommen. Die Sequenznummer für ein Segment stellt den Byte-Offset des ersten Bytes dieses Segments im Datenstrom dar.
• ACKs (Acknowledgements): Der Empfänger sendet eine Bestätigung (ACK) zurück, sobald er ein Segment fehlerfrei empfangen hat. Das ACK enthält die nächste erwartete Sequenznummer, was dem Sender signalisiert, dass alle vorherigen Daten erfolgreich angekommen sind. Wenn der Sender ein ACK nicht innerhalb einer bestimmten Zeit erhält, nimmt er an, dass das entsprechende Segment verloren gegangen ist oder fehlerhaft übertragen wurde, und sendet es erneut.

Simuliertes Szenario: Verlust eines Datenpakets

Angenommen, Du versendest eine Datei und der Übertragungsprozess läuft folgendermaßen ab:

• Der Sender teilt die Datei in mehrere Segmente auf, z.B.:
• Segment 1 (Sequenznummer 1)
• Segment 2 (Sequenznummer 101)
• Segment 3 (Sequenznummer 201)
• ...
• Der Sender überträgt die Segmente nacheinander an den Empfänger.
• Der Empfänger erhält Segment 1 und sendet ein ACK zurück mit der Sequenznummer 101 (d.h. das nächste erwartete Byte ist das erste Byte des nächsten Segments).
• Der Empfänger erhält auch Segment 2 und sendet ein ACK mit der Sequenznummer 201.
• Angenommen, Segment 3 geht auf dem Weg zum Empfänger verloren.
• Der Empfänger wartet auf Segment 3, aber es kommt nicht an. Stattdessen erhält er Segment 4 (Sequenznummer 301).
• Da Segment 3 fehlt, sendet der Empfänger weiterhin ACKs mit der Sequenznummer 201 (zeigt dem Sender an, dass Segment 3 fehlt und er auf Byte 201 wartet).
• Der Sender erkennt das wiederholte ACK und sendet Segment 3 erneut.
• Der Empfänger erhält Segment 3 und sendet ein ACK mit der Sequenznummer 301 (nun ist Segment 4 ebenfalls bestätigt, da es bereits angekommen ist).

Durch die Verwendung von Sequenznummern und ACKs stellt TCP sicher, dass keine Segmente fehlen und alle in der richtigen Reihenfolge ankommen. Dies gewährleistet eine zuverlässige und fehlerfreie Datenübertragung, was für eine File Transfer Anwendung unerlässlich ist.

Aufgabe 3)

In verteilten Systemen beschreibt die strenge Konsistenz (strong consistency) eine Methode, bei der alle Knoten stets denselben Datenzustand anzeigen. Im Gegensatz dazu erlaubt die Eventual Consistency (schwache Konsistenz), dass die Daten auf verschiedenen Knoten nicht synchron sind, solange irgendwann Konsistenz erreicht wird.

• Strenge Konsistenz: Jede Leseoperation gibt den zuletzt geschriebenen Wert zurück.
• Eventual Consistency: Garantiert nur, dass alle Kopien der Daten schließlich konsistent werden.
• Trade-off: Strenge Konsistenz bietet höhere Verlässlichkeit, aber geringere Verfügbarkeit und Leistung.
• CAP-Theorem: Ein verteiltes System kann maximal zwei der drei Eigenschaften Konsistenz (Consistency), Verfügbarkeit (Availability) und Partitionstoleranz (Partition Tolerance) gleichzeitig erreichen.

a)

Erkläre das CAP-Theorem und beschreibe, wie es sich auf die Wahl zwischen strenger Konsistenz und eventual consistency in einem verteilten System auswirkt. Diskutiere auch die möglichen Konsequenzen für die Systemleistung und -verfügbarkeit.

Lösung:

Das CAP-Theorem: Das CAP-Theorem wurde von Eric Brewer formuliert und beschreibt die Einschränkungen, die ein verteiltes System bei der Auswahl bestimmter Eigenschaften hat. Das Theorem besagt, dass ein verteiltes System maximal zwei der drei folgenden Eigenschaften gleichzeitig erreichen kann:

• Konsistenz (Consistency): Alle Knoten im System zeigen nach einem bestimmten Zeitpunkt denselben Datenzustand an. Jede Leseoperation liefert den zuletzt geschriebenen Wert zurück.
• Verfügbarkeit (Availability): Jede Anforderung erhält eine Antwort, unabhängig davon, ob die Antwort den aktuellen Datenstand wiedergibt.
• Partitionstoleranz (Partition Tolerance): Das System funktioniert weiterhin, auch wenn Teile des Netzwerks partitioniert (d.h. getrennt) sind.

Wahl zwischen strenger Konsistenz und Eventual Consistency: Angesichts des CAP-Theorems müssen Entwickler von verteilten Systemen oft Entscheidungen darüber treffen, welche Eigenschaften sie priorisieren möchten. Dies hat direkte Auswirkungen auf die Wahl zwischen strenger Konsistenz (strong consistency) und eventual consistency:

• Strenge Konsistenz: Wenn Konsistenz und Verfügbarkeit priorisiert werden, kann das System im Falle einer Partitionierung des Netzwerks nicht garantiert funktionieren. Dies bedeutet, dass das System möglicherweise Ausfälle oder Verzögerungen in Kauf nehmen muss, um konsistente Daten sicherzustellen. Hierdurch könnte die Systemleistung vermindert werden, da jede Operation sicherstellen muss, dass alle Knoten denselben Datenzustand anzeigen.
• Eventual Consistency: Wird Verfügbarkeit und Partitionstoleranz bevorzugt, so erlaubt dies die eventual consistency. In diesem Fall wird nicht garantiert, dass sofort alle Knoten denselben Datenzustand anzeigen. Stattdessen wird nur garantiert, dass die Daten irgendwann konsistent werden. Dies kann die Verfügbarkeit und Leistung des Systems erhöhen, da Schreib- und Leseoperationen schneller durchgeführt werden können, selbst wenn das Netzwerk partitioniert ist.

Konsequenzen für die Systemleistung und -verfügbarkeit: Die Entscheidung zwischen strenger Konsistenz und eventual consistency hat verschiedene Auswirkungen auf die Systemleistung und -verfügbarkeit:

• Leistung: Ein System, das strenge Konsistenz erfordert, kann langsamer sein, da jede Änderung im gesamten System synchronisiert werden muss. Eventual consistency kann die Leistung verbessern, indem sie weniger strenge Synchronisationsanforderungen stellt.
• Verfügbarkeit: Systeme mit strenger Konsistenz sind möglicherweise weniger verfügbar, insbesondere bei Netzwerkpartitionierungen, da sie möglicherweise aufhören, Anfragen zu bedienen, um die Konsistenz zu wahren. Systeme mit eventual consistency bieten höhere Verfügbarkeit, da sie weiterhin Anfragen bearbeiten, auch wenn einige Knoten oder Netzwerkverbindungen ausgefallen sind.
• Fehlertoleranz: Systeme mit höherer Partitionstoleranz können Netzwerkfehler besser verkraften und bleiben verfügbar, während strenge Konsistenzsysteme möglicherweise bei Netzwerkpartitionierungen nicht mehr vollständig funktionsfähig sind.

Zusammenfassend lässt sich sagen, dass das CAP-Theorem eine wichtige Rolle bei der Architektur von verteilten Systemen spielt. Die Wahl zwischen strenger Konsistenz und eventual consistency hängt von den spezifischen Anforderungen an Konsistenz, Verfügbarkeit und Partitionstoleranz ab. Jede Wahl hat ihre eigenen Vor- und Nachteile bezüglich Leistung und Verfügbarkeit, und Entwickler müssen diese sorgfältig abwägen, um die beste Lösung für ihre Anwendung zu finden.

b)

Betrachte ein verteiltes Datenbanksystem, das Eventual Consistency verwendet und eine Partitionstoleranz erleidet. Was sind die möglichen Auswirkungen auf die Datenintegrität während der Partitionierung? Beschreibe Szenarien, in denen Daten entweder inkonsistent oder inkorrekt werden könnten.

Lösung:

Eventual Consistency in einem partitionierten verteilten Datenbanksystem: Wenn ein verteiltes Datenbanksystem eventual consistency verwendet und eine Netzwerkpartitionierung erleidet, können vielfältige Auswirkungen auf die Datenintegrität auftreten. Während der Partitionierung können Knoten, die getrennt sind, unterschiedliche Datenstände aufweisen. Die eventual consistency garantiert, dass diese Knoten nach einer Weile wieder konsistent werden, jedoch könnten während der Partitionierung Daten inkonsistent oder inkorrekt sein.

Hier sind einige Szenarien, in denen Daten inkonsistent oder inkorrekt werden könnten:

• Parallel durchgeführte Schreiboperationen: Angenommen, während der Partitionierung führen zwei Benutzer gleichzeitig Schreiboperationen auf unterschiedlichen Partitionen des Systems durch. Wenn Benutzer A den Wert eines Datensatzes auf Knoten 1 ändert und Benutzer B dieselbe Änderung auf Knoten 2 durchführt, ohne voneinander zu wissen, kann dies zu Inkonsistenzen führen. Beide Änderungen könnten widersprüchlich sein, und wenn die Partitionierung endet, muss das System eine Methode finden, diese Konflikte zu lösen. Es könnte zum Beispiel eine Änderung bevorzugen oder durch einen Mergebefehl beides zusammenführen.
• Sichteffekte: Während der Partitionierung könnten verschiedene Knoten des Systems alte oder unvollständige Daten anzeigen. Benutzer könnten basierend auf diesen veralteten Daten handeln, was zu inkorrekten oder unerwarteten Ergebnissen führen kann. Zum Beispiel könnte ein Benutzer, der auf Knoten 1 liest, eine veraltete Version eines Datensatzes sehen, während auf Knoten 2 die neueste Version vorhanden ist. Diese verschiedenen Sichteffekte führen zu Unsicherheit und möglichen Fehlern bei der Datenverarbeitung.
• Transaktionsinkonistenz: In einem System mit eventual consistency könnte eine Transaktion, die mehrere Schreibvorgänge umfasst und während der Partitionierung erfolgt, zu einem inkonsistenten Zustand führen, wenn nicht alle Schreibvorgänge erfolgreich synchronisiert werden. Hierdurch könnte nur ein Teil der Änderungen gültig sein, während ein anderer Teil verloren geht oder unvollständig bleibt.

Beispiele für inkonsistente oder inkorrekte Daten:

• Finanztransaktionen: Stelle Dir eine Anwendung vor, die Geldüberweisungen zwischen verschiedenen Konten handhabt. Während einer Partitionierung könnte eine Überweisung auf einem Knoten als erfolgreich verbucht werden, während auf einem anderen Knoten dieselbe Überweisung als fehlerhaft markiert wird. Dies könnte zu Salden führen, die nicht übereinstimmen, und wenn die Knoten wieder synchronisiert werden, müssen Konflikte aufgelöst werden, um den tatsächlichen Betrag zu bestimmen.
• Bestellverwaltung: In einem E-Commerce-System könnte ein Benutzer während einer Partitionierung eine Bestellung aufgeben. Die Bestellinformationen könnten auf einem Knoten aktualisiert werden, der Benutzer erhält eine Bestellbestätigung, jedoch könnten Lagerbestände und Logistiksysteme auf einem anderen Knoten nicht aktualisiert werden. Dies könnte zu Fehlern in der Bestellabwicklung und zur Falschlieferung von Artikeln führen.

Zusammenfassend lässt sich sagen, dass die Verwendung von eventual consistency in einem partitionierten verteilten System zu temporären Dateninkonsistenzen und -fehlern führen kann. Um diese Probleme zu mildern, verwenden verteilte Systeme häufig Mechanismen wie Versionierung, Konfliktlösung und Replikationsprotokolle, die die Konsistenz der Daten gewährleisten, sobald die Partitionierung beendet ist und die Knoten wieder synchronisiert sind.

c)

Implementiere einen Algorithmus in Python, der sicherstellt, dass ein System eventual consistency erreicht. Beschreibe dabei die wichtigsten Schritte und Synchronisationsmethoden, die Du verwendest.

Lösung:

Um einen Algorithmus zu implementieren, der eventual consistency in einem verteilten System sicherstellt, können wir auf das Prinzip der 'Replikation' zurückgreifen, bei dem Daten auf mehreren Knoten dupliziert werden. Einer der gängigsten Ansätze ist das Verwenden eines Protokolls wie dem 'Gossip Protocol'. Dies basiert auf der Idee, dass Knoten Informationen untereinander austauschen, bis alle Knoten schließlich einen konsistenten Zustand erreichen.

Hier ist ein einfacher Algorithmus in Python, der das Gossip Protocol zur Synchronisation verwendet:

import threading, time, random, copyclass Node:    def __init__(self, id):        self.id = id        self.data = {}        self.neighbors = []    def update(self, key, value):        self.data[key] = value        print(f'Node {self.id} updated {key} to {value}')        self.gossip(key, value)    def gossip(self, key, value):        print(f'Node {self.id} gossips {key} = {value}')        for neighbor in self.neighbors:            neighbor.receive_gossip(key, value)            time.sleep(random.random())    def receive_gossip(self, key, value):        self.data[key] = value        print(f'Node {self.id} received gossip {key} = {value}')# Create nodesnodes = [Node(i) for i in range(5)]# Establish neighbors (for simplicity, all nodes are neighbors of each other)for node in nodes:    node.neighbors = [n for n in nodes if n != node]# Update data in one of the nodesnodes[0].update('x', 42)# Wait for a while to let gossip propagate# In practice, you should use more sophisticated synchronization mechanisms# to ensure that all nodes will eventually receive and apply the gossiped updates# Display final state of each nodetime.sleep(3)  # Adjust timing for demonstration purposesprint('Final states:')for node in nodes:    print(f'Node {node.id} data: {node.data}')

Hier sind die wichtigsten Schritte und Synchronisationsmethoden:

• Initialisierung von Knoten: Jeder Knoten hat eine individuelle ID, Daten (als Dictionary) und eine Liste von Nachbarn.
• Update-Methode: Die Methode aktualisiert die Daten eines Knotens und erzeugt eine Gossip-Nachricht, um die Aktualisierung an die Nachbarn zu senden.
• Gossip-Methode: Diese Methode sendet das Update an jeden Nachbarn, und dies wird asynchron durchgeführt, indem eine zufällige Pause (sleep) hinzugefügt wird.
• Receive Gossip-Methode: Diese Methode empfängt die Gossip-Nachricht und aktualisiert die Daten des Knotens entsprechend.
• Nachbarschaftsverbindungen: Um die Gossip-Nachrichten zwischen den Knoten zu propagieren, müssen Verbindungen zwischen den Knoten erstellt werden. Im obigen Beispiel sind alle Knoten Nachbarn voneinander.

Dieser Algorithmus ist einfach und veranschaulicht die grundlegenden Prinzipien der Gossip-Protokolle, aber in echten verteilten Systemen könnten weitere Mechanismen wie Versionskontrolle, Konfliktlösung und fortgeschrittene Synchronisationsstrategien verwendet werden, um die eventual consistency effizient und zuverlässig zu gewährleisten.

d)

Angenommen, ein Unternehmen verwendet ein verteiltes System mit strenger Konsistenz. Berechne die theoretische maximale Verfügbarkeit des Systems, wenn Du die Latenz zwischen den Knoten mit \texttt{L} Sekunden und die Wahrscheinlichkeit eines Knotenausfalls mit \texttt{p} pro Stunde annimmst. Stelle die Formel her und errechne die Verfügbarkeit für \texttt{L = 0.1} Sekunden und \texttt{p = 0.01}.

Lösung:

Theoretische maximale Verfügbarkeit in einem System mit strenger Konsistenz: In einem verteilten System mit strenger Konsistenz müssen alle Knoten stets denselben Datenzustand anzeigen. Jede Änderung muss daher sofort über alle Knoten hinweg propagiert werden, was eine gewisse Latenz (L) erfordert. Gleichzeitig gibt es eine gewisse Wahrscheinlichkeit (p) für den Ausfall eines Knotens pro Stunde. Beide Faktoren beeinflussen die Verfügbarkeit des Systems (A).

Formel zur Berechnung der Verfügbarkeit: Die Verfügbarkeit eines Systems kann durch folgende Formel dargestellt werden:

A = \frac{MTBF}{MTBF + MTTR}

Hierbei sind: • MTBF (Mean Time Between Failures): Die durchschnittliche Zeit zwischen Ausfällen • MTTR (Mean Time To Repair): Die durchschnittliche Reparaturzeit

In unserem Fall berechnen wir MTBF und MTTR wie folgt:

• MTBF: Dies ist die umgekehrte Wahrscheinlichkeit eines Knotenausfalls pro Stunde.MTBF = \frac{1}{p}
• MTTR: Dies ist die Latenzzeit zwischen den Knoten konvertiert in Stunden.MTTR = \frac{L}{3600}

Daraus ergibt sich die Verfügbarkeitsformel:

A = \frac{\frac{1}{p}}{\frac{1}{p} + \frac{L}{3600}}

Einsetzen von L = 0.1 Sekunden und p = 0.01:

Wir setzen die gegebenen Werte in die Formel ein:

• L = 0.1 Sekunden
• p = 0.01 Ausfälle pro Stunde

Das ergibt:

A = \frac{\frac{1}{0.01}}{\frac{1}{0.01} + \frac{0.1}{3600}}

Dies vereinfacht sich zu:

A = \frac{100}{100 + \frac{0.1}{3600}}

Um den Nenner zu vereinfachen, berechnen wir \frac{0.1}{3600}:

\frac{0.1}{3600} = 0.00002778

Setzen wir dies zurück ein, ergibt sich:

A = \frac{100}{100 + 0.00002778}

Schließlich vereinfacht sich das zu:

A \approx 0.99999972

Ergebnis:Die theoretische maximale Verfügbarkeit des Systems beträgt etwa 0.99999972, was etwa 99.999972% entspricht. Dies zeigt eine extrem hohe Verfügbarkeit bei der gegebenen Latenzzeit von 0.1 Sekunden und der Wahrscheinlichkeit eines Knotenausfalls von 0.01 pro Stunde.

Aufgabe 4)

Kontext: Stellen Sie sich vor, Sie entwickeln ein verteiltes System, das gleichzeitig Dienste in verschiedenen geografischen Regionen bereitstellen muss. Ihr Ziel ist es, die Prinzipien des CAP-Theorems (Konsistenz, Verfügbarkeit und Partitionstoleranz) zu nutzen, um sicherzustellen, dass Ihr System eine geeignete Balance zwischen diesen drei Eigenschaften findet. Dazu benötigen Sie ein tiefes Verständnis des CAP-Theorems, um fundierte designtechnische Entscheidungen zu treffen.

• Konsistenz (Consistency): Jeder Lesevorgang erhält die zuletzt geschriebene Version der Daten.
• Verfügbarkeit (Availability): Jedes Anfragen erhält eine (nicht notwendigerweise die neueste) Antwort.
• Partitionstoleranz (Partition Tolerance): Das System funktioniert weiter trotz Ausfällen oder Nachrichtenverlusten zwischen den Knoten.
• Formel: Es gilt \(C + A \leq 2\).
• Typische Systeme: CA (relationale DBs), AP (NoSQL-Datenbanken wie Cassandra), CP (verteilte Dateisysteme wie HDFS).

a)

Angenommen, Sie entwerfen ein neues verteiltes Finanzsystem, das eine hohe Verfügbarkeit (Availability) und eine starke Konsistenz (Consistency) gewährleisten soll. Erklären Sie, warum gemäß dem CAP-Theorem in dieser Konfiguration keine Partitionstoleranz (Partition Tolerance) sichergestellt werden kann. Welche Konsequenzen hätte dies für Ihr System im Falle eines Netzwerkausfalls?

Lösung:

Erklärung gemäß dem CAP-Theorem

Das CAP-Theorem besagt, dass ein verteiltes System immer nur zwei der drei folgenden Eigenschaften gleichzeitig garantieren kann:

• Konsistenz (Consistency): Jeder Lesevorgang erhält die zuletzt geschriebene Version der Daten.
• Verfügbarkeit (Availability): Jede Anfrage erhält eine (nicht notwendigerweise die neueste) Antwort.
• Partitionstoleranz (Partition Tolerance): Das System funktioniert weiter trotz Ausfällen oder Nachrichtenverlusten zwischen den Knoten.

Die zugrunde liegende Formel lautet:

C + A \leq 2

Wenn du ein neues verteiltes Finanzsystem entwirfst, das sowohl hohe Verfügbarkeit als auch starke Konsistenz gewährleisten soll, ist klar, dass du gemäß dem CAP-Theorem auf Partitionstoleranz verzichten musst.

Warum keine Partitionstoleranz sicherstellen?

Gemäß dem CAP-Theorem können nicht alle drei Eigenschaften gleichzeitig garantiert werden. Wenn du dich entscheidest, starke Konsistenz und hohe Verfügbarkeit zu priorisieren, führt das zu folgenden Herausforderungen:

• Um Konsistenz zu gewährleisten, müssen Daten über alle Knoten hinweg synchronisiert werden. Jede Änderung muss auf alle Knoten propagiert werden, bevor eine Bestätigung erfolgt.
• Um Verfügbarkeit zu gewährleisten, muss jede Anfrage eine Antwort erhalten, auch wenn nicht alle Knoten erreichbar sind.
• Bei einer Netzwerkpartition können einige Knoten nicht miteinander kommunizieren. Um trotzdem Konsistenz zu gewährleisten, müssten Anfragen blockiert oder abgelehnt werden, bis die Partition behoben ist. Dies beeinträchtigt die Verfügbarkeit.

Konsequenzen im Falle eines Netzwerkausfalls

Wenn eine Netzwerkpartitionierung auftritt, hat dies folgende Konsequenzen für dein System:

• Dienstausfälle: Teile des Systems könnten nicht verfügbar sein, da Konsistenzvorgänge blockieren, bis die Netzwerkprobleme behoben sind.
• Verzögerte Antwortzeiten: Die Antwortzeiten könnten steigen, weil das System auf die Synchronisation wartet.
• Fehlende Aktualität: Benutzer könnten veraltete Daten erhalten, insbesondere wenn das System die Synchronisierung erzwingt und Anfragen blockiert.
• Potentieller Datenverlust: Inkonsistenzen oder Datenverluste könnten auftreten, wenn während der Partitionierung Schreibvorgänge stattfinden und die Konsistenz anschließend schwer wiederhergestellt werden kann.

Zusammenfassend lässt sich sagen, dass das Streben nach Konsistenz und Verfügbarkeit in einem verteilten System nach dem CAP-Theorem unweigerlich zu einer Reduzierung der Partitionstoleranz führt. Dies ist eine grundlegende Designentscheidung, die sorgfältig abgewogen werden muss, insbesondere in kritischen Systemen wie einem Finanzsystem.

b)

Nehmen wir an, Sie entscheiden sich stattdessen für ein System, das hohe Verfügbarkeit (Availability) und Partitionstoleranz (Partition Tolerance) bietet. Erläutern Sie, welche Einbußen bezüglich der Konsistenz (Consistency) zu erwarten sind und unter welchen Anwendungsfällen diese Entscheidung gerechtfertigt sein könnte.

Lösung:

Erklärung gemäß dem CAP-Theorem

Das CAP-Theorem besagt, dass ein verteiltes System immer nur zwei der drei folgenden Eigenschaften gleichzeitig garantieren kann:

• Konsistenz (Consistency): Jeder Lesevorgang erhält die zuletzt geschriebene Version der Daten.
• Verfügbarkeit (Availability): Jede Anfrage erhält eine (nicht notwendigerweise die neueste) Antwort.
• Partitionstoleranz (Partition Tolerance): Das System funktioniert weiter trotz Ausfällen oder Nachrichtenverlusten zwischen den Knoten.

Die zugrunde liegende Formel lautet:

C + A \leq 2

Wenn du dich entscheidest, ein System zu entwerfen, das hohe Verfügbarkeit und Partitionstoleranz gewährleistet, besagt das CAP-Theorem, dass du auf eine gewisse Konsistenz verzichten musst.

Einbußen bezüglich der Konsistenz

• Eventual Consistency: In einem AP-System (Availability und Partition Tolerance) erhältst du möglicherweise nur die eventuelle Konsistenz. Das bedeutet, dass Updates zu verschiedenen Zeiten an unterschiedliche Knoten gelangen und es daher zu einem Zeitpunkt Unterschiede zwischen den Daten auf verschiedenen Knoten geben kann. Schließlich werden jedoch alle Knoten konsistent sein.
• Lesen veralteter Daten: Da das System nicht garantiert, dass jede Lesevorgang die neueste Version der Daten erhält, könnten Benutzer veraltete Daten lesen, die noch nicht auf allen Knoten synchronisiert wurden.
• Inkonsequente Sicht der Daten: Verschiedene Benutzer könnten unterschiedliche Versionen derselben Daten sehen, abhängig davon, welcher Knoten ihre Anfragen beantwortet.

Gerechtfertigte Anwendungsfälle

Trotz der Einbußen bei der Konsistenz gibt es viele Anwendungen, bei denen ein System mit hoher Verfügbarkeit und Partitionstoleranz die beste Wahl ist:

• Social Media Plattformen: Auf Plattformen wie Facebook oder Twitter ist unverzügliche Verfügbarkeit wichtiger als sofortige Konsistenz. Benutzer müssen schnell Posts sehen können, auch wenn diese Posts nicht sofort auf allen Servern konsistent sind.
• Web-Content-Delivery-Netzwerke (CDNs): CDNs, die Inhalte an Benutzer weltweit verteilen, priorisieren Verfügbarkeit und Reaktionszeit. Es ist akzeptabel, wenn kurzfristig unterschiedliche Versionen von Inhalten angezeigt werden.
• Online-Handel: Marktplätze wie eBay können hohe Verfügbarkeit und Partitionstoleranz priorisieren, um eine reibungslose Benutzererfahrung zu gewährleisten, auch wenn gelegentlich inkonsistente Produktinformationen auftreten.
• Messaging-Dienste: Bei Diensten wie WhatsApp oder Slack ist es wichtiger, dass Nachrichten sofort zugestellt werden, als dass alle Knoten im Netzwerk die Nachricht sofort sehen.

In solchen Szenarien ist es für Benutzer oft akzeptabel, mit einer vorübergehenden Inkonsistenz zu leben, solange die Daten schließlich konsistent werden und das System immer verfügbar bleibt.

d)

Gegeben sei ein verteiltes Nachrichtensystem, das sich für das CP-Modell (Consistency + Partition Tolerance) entschieden hat. Nutzen Sie die Formel \(C + A \leq 2\) aus dem CAP-Theorem, um zu erklären, wie und warum dieses System nicht immer eine hohe Verfügbarkeit sicherstellen kann. Entwickeln Sie eine rudimentäre mathematische Simulation, die zeigt, wie Netzpartitionen die Verfügbarkeit des Systems beeinflussen.

Lösung:

Erklärung gemäß dem CAP-Theorem

Ein verteiltes Nachrichtensystem, das sich für das CP-Modell (Consistency + Partition Tolerance) entschieden hat, priorisiert Konsistenz und Partitionstoleranz auf Kosten der Verfügbarkeit. Dies bedeutet:

• Konsistenz (Consistency): Jeder Lesevorgang erhält die zuletzt geschriebene Version der Daten.
• Partitionstoleranz (Partition Tolerance): Das System funktioniert weiter trotz Ausfällen oder Nachrichtenverlusten zwischen den Knoten.

Die Formel C + A \leq 2 des CAP-Theorems zeigt, dass ein System, das Konsistenz und Partitionstoleranz gewährleistet, nicht gleichzeitig Verfügbarkeit garantieren kann. Das bedeutet, dass das System in bestimmten Szenarien nicht in der Lage sein wird, Anfragen zu beantworten.

Warum keine hohe Verfügbarkeit sichergestellt werden kann

Wenn eine Netzpartition auftritt, werden einige Knoten vom Netzwerk getrennt und können nicht miteinander kommunizieren. Um Konsistenz sicherzustellen, könnte das System Anfragen blockieren oder ablehnen, bis die Partition behoben ist und alle Knoten wieder synchronisiert sind. Dies führt zu einer verringerten Verfügbarkeit während der Partition.

Im CP-Modell müssen Schreibvorgänge auf Partitionen warten und nicht sofortige Antworten zurückgeben, was in Fällen von Netzpartitionen bedeutet, dass Verfügbarkeit nicht gewährleistet werden kann. Eine rudimentäre mathematische Simulation kann dies verdeutlichen:

Rudimentäre mathematische Simulation

Angenommen, wir haben ein System mit 3 Knoten, und die Wahrscheinlichkeit einer Netzpartition zwischen ihnen beträgt 20%.

# Simulation Parametersknoten = 3  # Anzahl der Knotenpartition_wahrscheinlichkeit = 0.20  # Wahrscheinlichkeit einer Netzpartitionanfragen_pro_tag = 100  # Anzahl der Anfragen pro Tag# Simulation der Auswirkungen einer Partitionierung auf die Verfügbarkeitnetzpartitionen = partition_wahrscheinlichkeit * anfragen_pro_tagverfuegbare_anfragen = anfragen_pro_tag - netzpartitionenprint(f'Gesamtanfragen pro Tag: {anfragen_pro_tag}')print(f'Erwartete Netzpartitionen pro Tag: {netzpartitionen}')print(f'Verfuegbare Anfragen pro Tag: {verfuegbare_anfragen}')

Die Ergebnisse könnten wie folgt aussehen:

Gesamtanfragen pro Tag: 100Erwartete Netzpartitionen pro Tag: 20Verfügbare Anfragen pro Tag: 80

Das bedeutet, dass an einem durchschnittlichen Tag etwa 20 Anfragen aufgrund von Netzpartitionen blockiert oder abgelehnt werden und somit die Verfügbarkeit beeinträchtigt wird.

Zusammenfassung

Ein CP-Modell (Consistency + Partition Tolerance) in einem verteilten Nachrichtensystem priorisiert die Aktualität und die Sicherstellung der Datenintegrität bei Netzpartitionen, was jedoch zu Lasten der Verfügbarkeit geht. Die rudimentäre Simulation zeigt, dass Netzpartitionen zu einer beträchtlichen Anzahl blockierter oder abgelehnter Anfragen führen können, wodurch die Verfügbarkeit des Systems reduziert wird.