Verteilte Systeme - Eine Einführung

Mittlerweile gibt es einige verteile Systeme. Die Blockchain-Technologien sind nur die Neusten. Es gibt zum Beispiel noch:

  • Verteiltes Filesystem (z.B. Hadoop, NFS, CIFS, AFP)
  • Peer to Peer Video-Plattform (z.B. PeerTube)
  • Federated Kurznachrichtendienst (z.B. Mastodon)
  • Email
  • Internet (Webserver)
  • DNS
  • Distributed Hash Tables (z.B. Kademlia, Chord, TomP2P, Paxos, Raft)
  • BitTorrent
  • Software Updates in Windows 10 und einigen Spielen
  • Browser Peer to Peer über WebRTC (Videotelefonie, Chat u.v.m.)
  • Remote Procedure Call (RPC) (z.B. gRPC, Apache Avro)
  • Peer to Peer Internet (z.B. Tor)
  • Message Queue (z.B. RabbitMQ, ActiveMQ, Qpid, ZeroMQ, Kafka)
  • Hierarchical key-value-store (z.B. Apache ZooKeeper)

Ich werde einige als Prüfungsvorbereitung beschreiben. Viel Material kann man auf der Website von Maarten van Steen finden.

Distributed Hash Table

Ist ähnlich einer normalen HashMap, die jedoch verteilt auf mehrere Nodes ist. Man könnte damit versuchen einen verteilten Cloud-Storage zu bauen. Ein Produkt dafür ist DynamoDB. Wenn ein neuer Node dazu kommt, sollte nur ein kleiner Teil der Daten verschoben werden und nicht alle. Stichword dazu ist consistent hashing. Man könnte aber auch einen verteilten Cache bauen. Ein Produkt dafür heisst Memcached.

Das ganze System baut auf einem gemeinsamen Adressraum auf. Alle Objekte und alle Nodes benutzen den gleichen Addressraum und werden logisch in einem Ring angeordnet. Der Node mit dem kleinsten Key k, der grösser oder gleich dem Key des Objektes ist, ist für das Objekt verantwortlich. Das nennt man auch (consistent hashing). Im untenstehenden Diagramm wäre der Knoten 4 für alle Objekte von 2 bis inklusive 4 verantwortlich.

Chord Diagramm von https://www.distributed-systems.net

Die Tabelle neben dem Ring ist die Finger-Tabelle, die eine logarithmische Zugriffszeit auf alle Nodes sicherstellt.

Diese Hash Tabelle hat aber einige Probleme. Wenn die Nodes, also in der Regel Computer, den Key selber wählen können, kann man Objekte aus der Hash Tabelle löschen. Man muss nur einen Key wählen, der einem zum Verantwortlichen für diese Objekte macht, wodurch der alte Verantwortliche seine Daten auf den neuen Node überträgt. Ein anderer Angriff führt zur Störung eines Nodes, indem man sich direkt davor platziert, sodass der alte Verantwortliche für keine Objekte mehr zuständig ist. In beiden Fällen kann man falsche Informationen zurückliefern.

Die Daten des “successor” und des “predecessor” müssen immer aktuell sein. Ob der “successor” noch aktuell ist, kann man mit dem Trick herausfinden. Man fragt nach dem “predecessor” des “successor” und wenn dieser grösser als man selber aber kleiner als der jetzige “successor” ist, kann man ihn als “successor” übernehmen.

Der “predecessor” kann man über regelmässige Notifikationen vom Vorgänger an den Nachfolger aktuell halten und übernehmen, sofern er grösser als der jetzige “predecessor” aber kleiner als man selber ist.

Wenn Nodes ungeplant verschwinden, stimmen vielleicht einmal der eigene “successor” nicht mehr. Man muss dann einfach zum nächsten “successor” wechseln indem man nach dem zuständigen Node für das Objekt mit “Node-Key + 1” sucht.