STP027: Verteilte Systeme

Schlüsseltechnologie

In dieser Episode bringt Xyrill uns versprengte Systeme näher. Dabei erfahren wir auch, dass Dinge, die wir als Grundvoraussetzung ansehen würden, bei genauerer Betrachtung gar nicht so selbstverständlich sind.

Shownotes

Laut Wikipedia eine überraschend breite Definition:

Ein verteiltes System ist [...] ein Zusammenschluss unabhängiger Computer, die sich für den Benutzer als ein einziges System präsentieren.

• Motivationen für verteilte Systeme

  • Kommunikation zwischen Computern mit verschiedenen Eigentümern (z.B. Chatnetzwerk, Banküberweisung)
  • Teilen von Ressourcen (z.B. Druckerfreigabe)
  • Hochverfügbarkeit
  • Lastverteilung

• Grundlage des Problems: CAP-Theorem

  • Es gibt drei extrem wünschenswerte Eigenschaften. Wähle zwei.
  • Konsistenz (Consistency): Lesevorgänge liefern immer die Daten, die zuletzt geschrieben wurden.
  • Verfügbarkeit (Availability): Alle Anfragen an das System werden stets beantwortet.
  • Partitionstoleranz: Das System kann bei Störungen des Netzwerkes oder einzelner Computer weiterarbeiten.

• Beispiele bekannter Systeme gemäß CAP-Klassifikation

  • CP: Banküberweisung, Geldautomat
  • CA: Datenbanksysteme (siehe Folge 12)
  • AP: DNS (siehe Folge 18)

• Komplexbeispiel: Verteilte Datenbank mit Raft-Konsensalgorithmus

  • Computernetzwerk aus N gleichartigen Teilnehmern (N meist ungerade, um Pattsituationen zu vermeiden)
  • pro Wahlperiode ein Anführer, alle anderen folgen dem Anführer
  • Schreibvorgänge gehen an den Anführer, werden von ihm an die Folger verteilt, und erst quittiert, wenn eine Mehrzahl der Folger Vollzug meldet
  • Anführer sagt regelmäßig (Größenordnung 150-300 ms) allen Folgern Bescheid, dass er noch anführt
  • bei Ausbleiben der Meldung vom Anführer startet jeder Folger eine neue Wahlperiode und stimmt für sich selbst als neuen Anführer
  • pro Wahlperiode:
    • wer jemand anderen abstimmen sieht, bevor er selbst abstimmt, folgt sofort der gesehenen Stimme
    • wer die Mehrheit der Stimmen auf sich vereinigt, ist der neue Anführer
  • bei Pattsituationen beginnt nach einer Wartefrist die nächste Wahlperiode (Wartefrist ist pro Teilnehmer randomisiert, um Kettenpatt zu vermeiden)
  • CAP-Bewertung: CA (nicht partitionstolerant, weil eine Mehrheit der Teilnehmer erforderlich ist)

• hier nicht betrachtet: Byzantinische Fehler

  • Paper: The Saddest Moment
  • Analogie zu Wahlcomputern

• zum Nachlesen: Irrtümer der verteilten Datenverarbeitung

• Sidebar: Volunteer Computing (BOINC, SETI@Home, Folding@Home, etc.)

  • siehe Pentacast 56

• Nachtrag: geführte Visualisierung des Raft-Algorithmus (englisch): https://thesecretlivesofdata.com/raft/