Verteilte Systeme

Frühjahr 2021

Überblick

15-440 ist ein Einführungskurs in verteilte Systeme. Der Schwerpunkt liegt auf den Techniken zur Erstellung funktionaler, benutzbarer und skalierbarer verteilter Systeme. Um die Themen konkreter zu machen, umfasst der Kurs mehrere mehrwöchige Projekte, die einen umfangreichen Entwurf und eine Implementierung erfordern

Die Ziele dieses Kurses sind zweierlei. Erstens sollen die Studierenden die Prinzipien und Techniken verstehen, die dem Entwurf verteilter Systeme zugrunde liegen, wie Sperren, Gleichzeitigkeit, Caching, Prefetching, Scheduling und Kommunikation über das Netz. Zweitens sollen die Studierenden praktische Erfahrungen mit dem Entwurf, der Implementierung und der Fehlersuche in echten verteilten Systemen sammeln.

Die wichtigsten Themen, die in diesem Kurs vermittelt werden, sind:

• Ressourcenknappheit, Scheduling, und Nebenläufigkeit
• Kommunikationslatenz und Bandbreite
• Benennung
• Abstraktion und Modularität
• Unvollkommene Kommunikation und andere Arten von Fehlern
• Schutz vor versehentlichem und böswilligem Schaden
• Optimismus
• Konsens
• Verwendung von Instrumentierung, Überwachungs- und Fehlerbehebungsinstrumenten bei der Problemlösung.
• Entwurf, Implementierung und Fehlersuche von umfangreichen Programmierprojekten, die die oben genannten Themen umfassen

Benotung

Alle Kursarbeiten werden individuell durchgeführt. Es gibt keine Teams oder Projektpartner. Bei den Präsenzveranstaltungen dieses Kurses (vor dem COVID und hoffentlich auch nach dem COVID) basierte die Bewertung auf Projekten (45 %), Problemstellungen (20 %), einer Zwischenprüfung (15 %) und einer Abschlussprüfung (20 %). Für den Kurs im Frühjahr 2021 werden die Prüfungen aufgrund der COVID-Zwänge durch kumulative Problemstellungen ersetzt. Diese sind wie Klausuren mit offenem Buch, aber ohne Zeitdruck. Wie der Name schon sagt, umfassen sie den gesamten bis dahin im Unterricht behandelten Stoff. Die anderen Aufgabenstellungen bezeichnen wir als thematische Aufgabenstellungen, da sie sich auf Themen konzentrieren. Die Bewertung für das Frühjahr 2021 sieht also wie folgt aus (alle Gewichtungen sind ungefähre Angaben, innerhalb einer 5%-Spanne):

• 45% für 4 Projekte, gleich gewichtet
• 20% für 4 thematische Problemstellungen, gleich gewichtet
• 15% für die kumulative Problemstellung zur Semestermitte
• 20% für die abschließende kumulative Problemstellung.

Lernergebnisse

Wir erwarten, dass die Studenten ein tiefes Verständnis, eine flüssige Argumentation und praktische Implementierungsfähigkeiten für die folgenden Kernkonzepte verteilter Systeme erwerben:

1. • Kommunikation und Remote Procedure Call
   • Steuersemantik und Sprachbeschränkungen
   • Exactly-once, at-most-once, at-least-once
   • Serialisierung und De-Serialisierung
   • End-to-End-Argumente und ihre Anwendung auf reale Systeme
   • Integration mit Threading
   • Gleichzeitigkeit von Operationen
2. • Daten-Caching und One-copy semantics
   • Cache consistency protocols and implementation tradeoffs
   • Origins of temporaland spatial locality
   • Cache quality metrics
   • Application-specific consistency protocols
   • Prefetching: Vorteile und Risiken
   • Extraktion von Hints
   • Buffer Bloat
3. • Fehler in verteilten Systemen: Ursprünge und empirische Studien
   • Fail fast und Byzantine Failures
   • Grundlegende Grenzen der Fehlertoleranz
4. • Fehlertoleranz: Atomare Transaktionen; ACID-Eigenschaft
   • Herausforderungen bei der Implementierung
   • Shadowing, Intentionslisten und Write-Ahead-Logging
   • Gegensätze bei physischem Logging und Operationslogging
   • Schachtelungen von Transaktionen
   • Verteilte Transaktionen
5. • Konsens und Blockchain: Einstimmigkeit (Zwei-Phasen-Commit)
   • Mehrheit (Leaderwahl, Paxos)
   • Byzantinisch (single-shot und Dolev-Strong)
   • State-Machine-Replikation und Streamlet
   • Bitcoin

6. Gemeinsame Programmierparadigmen wie Map-Reduce, MPI und GraphLab

7. (Nur wenn es die Zeit erlaubt):
   • Hochverfügbarkeit erreichen: abstimmungsbasierte Erhaltung der One-Copy-Semantik
   • Taxonomie der Replikationsstrategien: Pessimistische und optimistische Ansätze
   • Lese-Schreib- und Schreib-Schreib-Konflikte
   • Server-Client- und Peer-to-Peer-Strategien
   • Caching und disconnected operation; Lösung von Konflikten
   • Ausnutzung geringer Bandbreite zur Verbesserung der Verfügbarkeit

Kurslogistik

Professoren

Name	Bürozeiten	Büro	Telefon	Andrew email
Mahadev Satyanarayanan (Satya)	Do 1:00 – 3:00 pm	GHC-9123	x8-3743	satya
Padmanabhan Pillai (Babu)	Wed 11:00 – 13:00 Uhr	GHC-9232		pspillai
Runting Shi (Elaine)	Mon 4:00 – 6:00 pm	CIC-2217		Kontakt über Canvas

Lehrende Assistenten

Name	Bürozeiten	Andrew email
Nathan Ang	Do 2:00-16:00 Uhr	Nathanan
Junwon Chang (Joseph)	Sat 9:00-11:00 Uhr	junwonc
Wenxin Ding (Freda)	Fr 10:00-12:00 Uhr	wenxind
Timothy Ganger	Sat 4:00-6:00 pm	tganger
Ziying He	Fri 5:00-7:00 pm	ziyingh
Roger Iyengar	Wed 1:00-3:00 pm	raiyenga
Ishaan Jaffer	Thu 4:00-6:00 pm	ijaffer
Ibnul Jahan	Tue 4:00-18:00 pm	iej
Chen Jin (Crystal)	Fri 8:00-10:00	chenj
Yajin Li	Mon 10:00-12:00 pm	yajinl
Diego San Miguel	Fri 14:00-4:00 pm	dsanmigu
Riccardo Santoni	Mon 8:00-10:00 pm	rsantoni
Yiwen Song (Victor)	Thu 9:00-11:00 pm	yiwenson
Haithem Turki	Wed 15:00-5:00 pm	hturki
Clarissa Xu	Tue 6:30-8:30 pm	csxu

Vorlesungen

• Dienstags und donnerstags, 10:40 – 12:00 Uhr
• Zoom-Links und Videoaufnahmen: Auf der Canvas-Seite für diesen Kurs
• Kein Unterricht: Dienstag, 23. Februar (Ferien), Donnerstag, 15. April (Frühlingskarneval)
• Letzte Vorlesung: Donnerstag, 6. Mai

Vorlesungen

• Zeit: Mittwochs 19:00 – 19:50 Uhr (Sektion A), 20:00 – 20:50 Uhr (Sektion B)
• Zoom-Links und Videoaufzeichnungen: Auf der Canvas-Seite für diesen Kurs

Kursnotizen

Werden im AFS-Bereich des Kurses eingestellt unter: /afs/andrew/course/15/440/classnotes Diese Notizen sind nur für Ihren persönlichen Gebrauch bestimmt. Bitte geben Sie sie nicht weiter.

Lehrbücher und optionale Lektüre

Es gibt keine Pflichtlehrbücher. Hier sind drei gute Referenzen für die optionale Lektüre:

• „Distributed Systems: Principles and Paradigms“ von Andrew S. Tanenbaum und Maarten Van Steen, Third (2017) Edition, Prentice Hall
• „Guide to Reliable Distributed Systems“ von Kenneth P. Birman, Springer
• „Foundations of Distributed Consensus and Blockchains“ von Elaine Shi (2020, Buchmanuskript)

Außerdem finden Sie unter dem Link „Readings“ oben auf dieser Webseite einige fakultative Lektüren, die wir an verschiedenen Stellen in den Vorlesungen erwähnen werden. Die pdf-Dateien dieser optionalen Lektüre sind auf der Kurswebseite verfügbar.

Kursrichtlinien

Voraussetzungen

Da dieser Kurs eine große Projektkomponente hat, müssen Sie die C- und Java-Programmierung auf UNIX-Systemen beherrschen. Es wird vorausgesetzt, dass Sie den Kurs 15-213 mit der Note „C“ oder besser abgeschlossen haben, da viele der benötigten Programmierkenntnisse in diesem Kurs vermittelt werden. Wenn Sie in 15-213 eine „C“ erhalten haben, müssen Sie sich mit Ihrem Studienberater treffen, um Ihren Hintergrund zu besprechen, bevor Sie 15-440 belegen, und vielleicht einen zusätzlichen Kurs belegen, um Ihre Systemkenntnisse zu verbessern.

Policy on Academic Integrity

Die Carnegie Mellon University Policy on Academic Integrity gilt für diesen Kurs. Von allen Studenten wird erwartet, dass sie diese Richtlinie sorgfältig durchlesen und in allen Aspekten dieses Kurses einhalten.

Hinweise zur Zusammenarbeit:

• Die Studenten werden ermutigt, miteinander, mit den Assistenten, mit den Dozenten oder mit anderen Personen über die Aufgaben zu sprechen. Jegliche Hilfe muss sich jedoch auf die Diskussion des Problems und die Skizzierung allgemeiner Lösungsansätze beschränken.
• Jeder Student muss seine eigenen Lösungen zu den Aufgabenstellungen aufschreiben. Alle Arbeiten müssen individuell angefertigt werden.
• Es ist verboten, die Lösung eines anderen Schülers zu konsultieren, und die eingereichten Lösungen dürfen nicht aus irgendeiner Quelle kopiert werden. Diese Handlungen gelten als Täuschung.
• Wenn Sie eine Frage dazu haben, ob eine bestimmte Aktivität eine Täuschung darstellt, wenden Sie sich bitte an die Dozenten.

Hinweise zum Teilen: Sie dürfen Arbeiten, die Sie im Rahmen des Kurses 15-440 anfertigen, nicht an andere Studierende weitergeben oder in zukünftigen Kursen verwenden (ebenso wenig dürfen Sie Arbeiten verwenden, die von Studierenden angefertigt wurden, die den Kurs zuvor belegt haben).

Aufzeichnungen

Im Frühjahr 2021 werden Zoom-Sitzungen jeder Vorlesung und jedes Vortrags von CMU Computing Services aufgezeichnet und auf der Canvas-Seite für diesen Kurs veröffentlicht. Alle anderen Aufzeichnungen sind verboten.

Limit für die Nutzung der TA-Zeit

Um allen gerecht zu werden, besonders wenn eine lange Schlange von Studenten auf die Aufmerksamkeit eines TAs wartet, wird es ein Limit von 10 Minuten für alle Konsultationen geben. Wenn ein Student nach 10 Minuten noch nicht fertig ist, geht er/sie zurück zum Ende der Schlange, bevor er/sie mehr Zeit mit dem TA bekommt. Bereiten Sie sich vor, bevor Sie sich mit einem TA treffen. Wenn Sie Hilfe brauchen, um einen Fehler zu finden, grenzen Sie das Problem ein und vereinfachen Sie es, bevor Sie sich mit dem Assistenten treffen.

Piazza-Politik

Dieser Kurs benutzt die Piazza-Website, um Fragen zu beantworten: hier ist die Piazza-Seite für diesen Kurs.

Stellen Sie sich Piazza so vor, als ob Sie in der Klasse die Hand heben und eine Frage stellen. Keine Frage ist zu dumm, um sie zu stellen, also haben Sie keine Angst. Für jede Person, die eine Frage stellt, gibt es wahrscheinlich viele andere, denen die gleiche Frage bereits gestellt wurde oder bald gestellt werden wird. Die Antwort auf Ihre Frage kann auch für sie von Nutzen sein. Darüber hinaus gibt es vielleicht auch Menschen, denen Ihre Frage nicht gestellt wurde. Indem Sie die Frage stellen, helfen Sie ihnen, eine Feinheit zu erkennen, die sie vorher vielleicht nicht gesehen haben. Direkte E-Mails an die Dozenten werden nicht beantwortet.

Wir erwarten von Ihnen, dass Sie bei Ihren Beiträgen auf Piazza (Fragen und Antworten auf die Fragen Ihrer Kommilitonen) stets Ihr gutes Urteilsvermögen einsetzen. Ein Teil des Lernprozesses besteht darin, sich so lange mit dem Stoff auseinanderzusetzen, bis Sie die richtige Einsicht gewonnen haben, um ihn zu verstehen. Wenn Sie zu viele Details als Antwort auf eine Bitte um Unterstützung posten, kann das den Lernprozess beeinträchtigen. Andererseits ist es manchmal gut, einen Anstoß in die richtige Richtung zu bekommen, wenn man nicht in der Lage ist, aus einem Trott herauszukommen. Und natürlich sollte bei Missverständnissen in Bezug auf die Aufgabe oder die zur Verfügung stehenden Hilfsmittel schnell geholfen werden. Bitte verwenden Sie Ihr bestes Urteilsvermögen, wenn Sie auf der Piazza-Website Beiträge verfassen, als ob Sie persönlich mit Ihren Freunden zusammenarbeiten würden. Ein paar grobe Richtlinien:

Beispiele für gute Beiträge und Antworten:

• Missverständnisse der Aufgabe
• Klarstellungen zu den Anforderungen
• Fehler in der Aufgabenspezifikation oder der Referenzimplementierung oder den Tests
• Kleine, detaillierte Fragen zur Funktionsweise von Systemaufrufen, Funktionen usw.
• Dinge, die in eine FAQ für die Aufgabe passen

Beispiele für schlechte Dinge, die man posten oder beantworten sollte:

• Mehr als ein paar Zeilen Code
• Gründliche Erklärungen, wie Ihr System funktioniert
• Fragen über den besten Ansatz für die Architektur des Systems auf hohem Niveau
• Fragen über Ihre Note

Wir erwarten, dass Sie sich angemessene Mühe gegeben haben, selbst zu denken, bevor Sie eine Piazza-Frage stellen. Dies gilt insbesondere für die Fehlersuche in deinem Code. Haben Sie es mit den Man Pages versucht? Haben Sie eine Google-Suche nach möglicherweise relevanten Ressourcen durchgeführt? Haben Sie sich die früheren Fragen angesehen, die bereits gestellt wurden, und die Antworten darauf? Haben Sie printf’s eingefügt und versucht zu verstehen, was in Ihrem Code vor sich geht?

Benutzen Sie autolab nicht als Debugging-Tool. Wir erwarten von Ihnen, dass Sie angemessene Anstrengungen unternommen haben, um Ihren Code zu debuggen, bevor Sie ihn an autolab senden. Das Erstellen von Testfällen und das Testen Ihres Codes unter Stressbedingungen ist Teil eines jeden Projekts. Wenn Sie diese Anstrengungen nicht unternehmen, verpassen Sie einen wichtigen Teil der Lernmöglichkeiten in diesem Kurs. Die Übermittlung an autolab sollte der letzte Schritt eines Prozesses sein, in dem Sie Ihren Code bis zum Äußersten getestet, debuggt und verbessert haben. Das Senden eines Autolab-Dumps in einem Piazza-Posting mit der Bitte um Hilfe ist ein eklatanter Verstoß gegen die Piazza-Etikette.

Private Posts auf Piazza werden nicht unterstützt. Dies ist eine Grundsatzentscheidung für diese Klasse. Denken Sie daran, dass ein Beitrag auf Piazza so ähnlich ist, wie wenn Sie Ihre Hand heben und eine Frage stellen. Andere Studenten profitieren davon, dass Sie die Frage stellen und die Antwort des Dozenten sehen. Wir erlauben es, dass Ihre Beiträge für Ihre Kommilitonen anonym bleiben, wenn Sie dies wünschen. Das ist bereits ein Grad an Privatsphäre, der über das hinausgeht, was beim Stellen einer Frage im Unterricht möglich ist. Für die wirklich seltenen Fälle, in denen Sie eine private Anfrage stellen müssen, die sich nicht auf den Kursinhalt bezieht, wurde eine spezielle private Mailingliste eingerichtet.

Für Anfragen, die wirklich privat sein müssen, senden Sie eine E-Mail an

[email protected]und einer der Dozenten wird Ihnen antworten. E-Mails an diese Liste, die Kursinhalte betreffen (z. B. Erklärungen zum Unterrichtsmaterial), werden ignoriert; solche Fragen sollten Sie auf Piazza stellen.

Politik zu verspäteten Einsendungen

Für Projekte:

• Jeder Student hat während des Semesters fünf Nachschreibetage zur Verfügung. Diese späten Tage sind für Urlaub, Reisen, Vorstellungsgespräche, Erkältungen und ähnliche Situationen gedacht. Es steht Ihnen frei, diese Tage zu nutzen, ohne die Dozenten um Erlaubnis zu fragen. Sie können maximal zwei Verspätungstage für ein Fälligkeitsdatum verwenden (d. h. bei Projekten mit mehreren Kontrollpunkten können Sie bis zu zwei Verspätungstage für jeden Kontrollpunkt verwenden). Verspätungstage werden automatisch in chronologischer Reihenfolge angerechnet. Sie können also nicht wählen, ob Sie einen Verspätungstag für eine spätere Aufgabe mit höherem Gewicht verwenden möchten.

• Ein Verspätungstag = (0,24] Stunden nach dem Fälligkeitsdatum; zwei Verspätungstage = (24, 48] Stunden nach dem Fälligkeitsdatum; usw.

• Wenn Sie alle Verspätungstage verwenden, können Sie bis zu zwei Tage lang gegen einen Aufschlag von 15% pro Tag verspätet einreichen. Mit anderen Worten: Wenn Sie alle Nachschreibetage ausgeschöpft haben, können Sie die nächsten zwei Tage noch einreichen, wobei Sie für jeden dieser Tage eine Strafe von 15 % zahlen müssen (Kulanztage).

• Sie können Nachschreibetage und Kulanztage nicht kombinieren, um mehr als zwei Tage zu spät einzureichen.

Für Problemstellungen: Verspätete Einsendungen werden nicht akzeptiert, weder mit noch ohne Strafe. Stellen Sie sicher, dass Sie pünktlich einreichen.

Style Guide for Projects

Neben der Prüfung der Funktionalität Ihres Codes werden wir auch einen Teil der Punkte jedes Projekts für seinen Stil und seine Lesbarkeit reservieren. Das Wichtigste ist ein konsistenter und lesbarer Stil. Wir achten vor allem darauf, dass Sie einen Stil gewählt haben, der lesbar und vernünftig ist, und dass Sie denselben Stil im gesamten Projekt durchgängig verwenden. Benutzen Sie den gesunden Menschenverstand: haben Sie keine 500-Zeichen-Zeilen im Code, nennen Sie Ihre Variablen nicht foo (es sei denn, das macht in ihrem Kontext Sinn), und vermeiden Sie es, Groß- und Kleinschreibung wahllos zu vermischen.

Wir werden auf die folgenden Dinge achten:

Dokumentation Eine gute Dokumentation ist wichtig: für Sie selbst in der Zukunft, für andere Betreuer des Codes und in diesem Zusammenhang für die Prüfer, die sich Ihren Code ansehen werden. Sie müssen nicht jede Zeile des Codes dokumentieren (da guter Code in gewissem Sinne auch selbstdokumentierend sein sollte), aber es ist in der Regel gut, die allgemeine Verwendung und den Zweck jeder Funktion sowie großer oder komplexer Codeblöcke hervorzuheben. Es ist auch eine gute Praxis, einen Dateikopf in jede Datei einzufügen, der detailliert beschreibt, wie die Datei in die Struktur des Projekts als Ganzes passt. Leerzeichen Bitte seien Sie konsequent. Bitte verwenden Sie nicht an manchen Stellen 2 Leerzeichen und an anderen 4. Seien Sie vernünftig und verwenden Sie Leerzeichen, um sicherzustellen, dass Ihr Code lesbar ist. Zeilenlänge Bei der Zeilenlänge sind wir nachsichtig, solange Sie konsistent sind und Ihre Zeilengrenzen vernünftig sind (500 Zeichen sind nicht… 80 oder 120 Zeichen sind üblich und werden akzeptiert). Variablennamen Ihre Variablennamen sollten einen klaren Hinweis darauf geben, wofür sie stehen oder wofür sie verwendet werden. Dead/Test Code Versuchen Sie, keinen Code einzureichen, der mit Debug-Druckanweisungen oder großen kommentierten Code-Blöcken übersät ist. Dies beeinträchtigt die Lesbarkeit und lenkt von dem Code ab, der tatsächlich in der Produktion laufen wird. Design Versuchen Sie, Ihren Code und Ihre Projekte so zu gestalten, dass sie einigermaßen modular sind. 5000-zeilige Funktionen sind im Allgemeinen ein Zeichen für schlechtes Design und werden Ihnen später Kopfschmerzen bereiten.

Hier ist ein Google Style Guide, der hilfreich sein kann.

Wohlbefinden

Hier sind einige Tipps für das Wohlbefinden.