Distributed Systems

Spring 2021

Overview

15-440 is een inleidende cursus in gedistribueerde systemen. De nadruk zal liggen op de technieken om functionele, bruikbare en schaalbare gedistribueerde systemen te maken. Om de onderwerpen concreter te maken, omvat de cursus een aantal meerweekse projecten die een significant ontwerp en implementatie vereisen

De doelen van deze cursus zijn tweeledig. Ten eerste, studenten inzicht geven in de principes en technieken achter het ontwerp van gedistribueerde systemen, zoals locking, concurrency, caching, prefetching, scheduling, en communicatie over het netwerk. Ten tweede, om studenten praktische ervaring te laten opdoen met het ontwerpen, implementeren en debuggen van echte gedistribueerde systemen.

De belangrijkste thema’s die in deze cursus worden behandeld zijn:

• Resource schaarste, scheduling, en concurrency
• Communicatielatentie en bandbreedte
• Naming
• Abstraction en modulariteit
• Imperfecte communicatie en andere types van falen
• Bescherming tegen accidentele en kwaadwillige schade
• Optimisme
• Consensus
• Gebruik van instrumentatie, monitoring, en debugging tools bij het oplossen van problemen.
• Ontwerpen, implementeren en debuggen van substantiële programmeerprojecten die de bovenstaande thema’s omvatten

Beoordeling

Al het cursuswerk wordt individueel gedaan. Er zijn geen teams of projectpartners. Voor de in-persoon aanbiedingen van deze cursus (pre-COVID en, hopelijk, post-COVID) was de evaluatie gebaseerd op projecten (45%), probleem sets (20%), mid-term examen (15%), en eindexamen (20%). In het voorjaar van 2021 worden de examens, vanwege de beperkingen van COVID, vervangen door cumulatieve probleemopgaven. Dit zijn net openboektentamens, maar zonder de tijdsdruk. Zoals de naam al aangeeft, bevatten ze alle stof die tot dan toe in de klas is behandeld. De andere probleemreeksen noemen we thematische probleemreeksen, omdat ze op onderwerpen gericht zijn. De evaluatie in het voorjaar van 2021 ziet er dus als volgt uit (alle gewichten bij benadering, binnen een marge van 5%):

• 45% voor 4 projecten, gelijk gewogen
• 20% voor 4 thematische probleemverzamelingen, gelijk gewogen
• 15% voor cumulatieve probleemverzameling halverwege het semester
• 20% voor cumulatieve probleemverzameling voor het einde van het semester.

Leerresultaten

We verwachten van studenten een diepgaand begrip, vloeiend redeneren, en hands-on implementatievaardigheden van de volgende kernconcepten van gedistribueerde systemen:

1. • Communicatie en remote procedure call
   • Control semantiek en taal beperkingen
   • Exactly-once, at-most-once, at-least-once
   • Serialisatie en de-serialisatie
   • End-to-end argument en de toepassing ervan op echte systemen
   • Integratie met threading
   • Concurrency van operaties
2. • Data caching en een-copy semantics
   • Cache consistency protocols and implementation tradeoffs
   • Origins of temporaland spatial locality
   • Cache quality metrics
   • Application-specific consistency protocols
   • Prefetching: voordelen en risico’s
   • Extractie van hints
   • Buffer bloat
3. • Failures in distributed systems: origins and empirical studies
   • Fail fast and Byzantine failures
   • Fundamental limits of failure resilience
4. • Fault tolerance: atomaire transacties; ACID-eigenschap
   • Uitdagingen bij de implementatie
   • Shadowing, intentielijsten en write-ahead logging
   • Tradeoffs in physical logging en operation logging
   • Nested transactions
   • Distributed transactions
5. • Consensus en blockchain: unanimiteit (commit in twee fasen)
   • Meerderheid (verkiezing leider, Paxos)
   • Byzantine (single-shot en Dolev-Strong)
   • State machine replicatie en Streamlet
   • Bitcoin

6. Gemeenschappelijke programmeerparadigma’s zoals Map-Reduce, MPI en GraphLab

7. (Alleen als de tijd het toelaat):
   • Hoge beschikbaarheid bereiken: stemgebaseerd behoud van één-kopie semantiek
   • Taxonomie van replicatiestrategieën: pessimistische en optimistische benaderingen
   • Lees-schrijf- en schrijf-schrijfconflicten
   • Server-client en peer-to-peer strategieën
   • Caching en ontkoppelde werking; conflicten oplossen
   • lage bandbreedte benutten om beschikbaarheid te verbeteren

Cursuslogistiek

Professoren

Ondersteunende docenten

Lectures

• Dinsdag en donderdag, 10:40 – 12:00 uur
• Zoom links en video opnames: Op Canvas pagina voor deze cursus
• Geen les: Dinsdag 23 februari (rustdag), donderdag 15 april (carnaval)
• Laatste les: Donderdag 6 mei

Recitaties

• Tijd: woensdag 19:00 – 19:50 uur (sectie A), 20:00 – 20:50 uur (sectie B)
• Zoomlinks en video-opnamen: Op Canvas pagina voor deze cursus

Course Notes

Wordt geplaatst in de cursus AFS gebied op: /afs/andrew/course/15/440/classnotes na elke les. Deze aantekeningen zijn alleen voor persoonlijk gebruik. Gelieve ze niet te verspreiden.

Textbooks and Optional Readings

Er zijn geen verplichte tekstboeken. Hier zijn drie goede referenties om als optionele lectuur te gebruiken:

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

Daarnaast heeft de “Readings” link bovenaan deze webpagina een aantal specifieke optionele lezingen die we op verschillende punten in de colleges zullen noemen. De pdf’s van deze optionele lezingen zijn beschikbaar op deze cursus website.

Cursus Beleid

Voorwaarden

Omdat deze cursus een grote project component heeft, moet u vaardig zijn in C en Java programmeren op UNIX systemen. Het is vereist dat u 15-213 hebt gevolgd en een “C” of hoger hebt gehaald, aangezien veel van de programmeervaardigheden die u nodig zult hebben, in die cursus worden onderwezen. Als je een C hebt gehaald in 15-213, moet je een afspraak maken met je academisch adviseur om je achtergrond te bespreken voordat je aan 15-440 begint, en misschien een extra cursus volgen om je systeemvaardigheden aan te scherpen.

Beleid inzake academische integriteit

Het beleid van de Carnegie Mellon University inzake academische integriteit is van toepassing op deze cursus. Van alle studenten wordt verwacht dat zij dit beleid zorgvuldig doornemen en zich eraan houden voor alle aspecten van deze cursus.

Richtlijnen voor samenwerking:

• Studenten worden aangemoedigd om met elkaar, met de TA’s, met de instructeurs, of met iemand anders te praten over een van de opdrachten. Elke hulp moet echter beperkt blijven tot het bespreken van het probleem en het schetsen van algemene benaderingen van een oplossing.
• Elke student moet zijn of haar eigen oplossingen voor probleemstellingen uitschrijven. Alle projecten moeten individueel worden gedaan.
• Het raadplegen van de oplossing van een andere student is verboden, en ingeleverde oplossingen mogen niet worden gekopieerd van welke bron dan ook. Deze handelingen worden beschouwd als spieken.
• Als je je afvraagt of een bepaalde activiteit spieken is, vraag het dan gerust aan de docenten.

Richtlijnen over delen: U mag werk dat u tijdens 15-440 voltooit, niet leveren aan andere studenten in toekomstige instanties van deze cursus of voor gebruik in toekomstige instanties van deze cursus (net zoals u geen werk mag gebruiken dat is voltooid door studenten die de cursus eerder hebben gevolgd).

Recordings

Voorjaar 2021 zullen Zoom-sessies van elke lezing en recitatie worden opgenomen door CMU Computing Services en op de Canvas-pagina voor deze cursus worden geplaatst. Alle andere opnames zijn verboden.

Limiet op het gebruik van TA-tijd

Om eerlijk te zijn voor iedereen, vooral wanneer er een lange rij studenten staat te wachten op de aandacht van een TA, zal er een limiet zijn van 10 minuten op alle consulten. Als een student aan het eind van de 10 minuten nog niet klaar is, gaat hij/zij terug naar het eind van de rij voordat hij/zij meer tijd met de TA krijgt. Wees voorbereid voor je een TA ontmoet. Als je hulp nodig hebt bij het vinden van een fout, verklein en vereenvoudig het probleem voordat je de TA ontmoet.

Piazza Policy

Deze cursus gebruikt de Piazza website voor het beantwoorden van vragen: hier is de Piazza pagina voor deze cursus.

Denk aan Piazza als je hand opsteken in de klas en een vraag stellen. Geen vraag is te dom om te stellen, dus wees niet bang. Voor elke persoon die een vraag stelt, zijn er waarschijnlijk vele anderen aan wie dezelfde vraag al is gesteld of binnenkort zal worden gesteld. Het antwoord op uw vraag kan ook voor hen van nut zijn. Bovendien zijn er misschien mensen bij wie uw vraag niet is opgekomen. Door de vraag te stellen, helpt u hen een subtiliteit te zien die zij misschien nog niet eerder hebben gezien. Rechtstreekse e-mails aan de docenten worden niet beantwoord.

Te allen tijde verwachten wij van u dat u uw gezond verstand gebruikt in uw Piazza posts (zowel vragen als antwoorden op de vragen van medestudenten). Een deel van het leerproces is worstelen met de stof totdat je tot het juiste inzicht komt om het te begrijpen. Te veel details posten in antwoord op een vraag om hulp kan het leren belemmeren. Aan de andere kant is het soms fijn om een duwtje in de goede richting te krijgen als je niet uit een sleur kunt komen. En natuurlijk moeten misverstanden over de opdracht of de beschikbare hulpmiddelen snel worden verholpen. Gelieve uw beste oordeel te gebruiken bij het posten op de Piazza site, alsof u persoonlijk samenwerkt met uw vrienden. Een paar ruwe richtlijnen:

Voorbeelden van goede dingen om te posten en te beantwoorden:

• Misverstanden over de opdracht
• Verklaringen over de eisen
• Bugs in de opdracht spec of referentie-implementatie of tests
• Kleine, gedetailleerde vragen over de werking van system calls, functies, enz.
• Dingen die eruit zien alsof ze in een FAQ voor de opdracht thuishoren

Voorbeelden van slechte dingen om te posten of te beantwoorden:

• Meer dan een paar regels code
• Diepgaande uitleg over hoe je systeem werkt
• Vragen over de beste aanpak voor de architectuur van het systeem op een hoog niveau
• Vragen over je cijfer

We verwachten dat je redelijke moeite hebt gedaan om zelf na te denken voordat je een piazza vraag plaatst. Dit is vooral waar met betrekking tot het debuggen van uw code. Hebt u de man pagina’s geprobeerd? Hebt u een Google-zoekopdracht gedaan voor mogelijk relevante bronnen? Hebt u gekeken naar de vorige vragen die mensen reeds hebben gesteld, en naar de antwoorden die werden gegeven? Hebt u printf’s ingevoegd en geprobeerd te begrijpen wat er met uw code gebeurt?

Gebruik autolab niet als een debugging tool. We verwachten dat u een redelijke inspanning hebt geleverd om uw code te debuggen voordat u het aan autolab voorlegt. Het maken van test cases en stress testen van uw code is onderdeel van waar een project om draait. Als je die inspanning niet levert, mis je een belangrijk deel van de leermogelijkheden in de cursus. Indienen bij autolab zou de laatste stap moeten zijn van een proces waarin je je code getest, gedebugged en verbeterd hebt tot het uiterste van je kunnen. Het sturen van een autolab dump in een piazza bericht en zeggen “alsjeblieft help” is een flagrante schending van de piazza etiquette.

Privé berichten op Piazza worden niet ondersteund. Dit is een beleidsbeslissing voor deze klas. Denk eraan, posten op piazza is hetzelfde als je hand opsteken en een vraag stellen. Andere studenten hebben er baat bij dat jij de vraag stelt en het antwoord van de docent ziet. We staan toe dat uw berichten anoniem zijn voor medestudenten, als u dat wenst. Dat is al een mate van privacy die verder gaat dan wat mogelijk is wanneer je een vraag stelt in de klas. Voor de echt zeldzame gevallen waarin je een privéverzoek moet doen dat geen verband houdt met de cursusinhoud, werd een speciale privé-mailinglijst gecreëerd.

Voor verzoeken die echt privé moeten zijn, stuur een e-mail naar[email protected]en een van de docenten zal antwoorden. E-mail naar deze lijst met betrekking tot de inhoud van de cursus (bijvoorbeeld verduidelijkingen van de lesstof) zal worden genegeerd; u moet dergelijke vragen op Piazza plaatsen.

Beleid voor te laat inleveren

Voor projecten:

• Elke student krijgt gedurende het semester vijf dagen de tijd om zijn werk te laat in te leveren. Deze vrije dagen zijn bedoeld om rekening te houden met vakanties, reizen, interviews, verkoudheid en andere soortgelijke situaties. U bent vrij om ze te gebruiken voor welke reden dan ook, zonder toestemming te vragen aan de docenten. U kunt maximaal twee extra dagen te laat gebruiken op elke vervaldatum (d.w.z. voor projecten met meerdere controlepunten kunt u maximaal twee extra dagen te laat gebruiken voor elk controlepunt). Late dagen worden automatisch toegepast in chronologische volgorde, dus u kunt er niet voor kiezen om het gebruik van een late dag uit te stellen voor een toekomstige opdracht met een hoger gewicht.

• Eén late dag = (0,24] uur na de vervaldatum; twee late dagen = (24, 48] uur na de vervaldatum; enz.

• Als u al uw late dagen gebruikt, kunt u maximaal twee dagen te laat inleveren tegen een boete van 15% per dag. Met andere woorden, als u al uw extra dagen te laat hebt opgebruikt, kunt u de volgende twee dagen nog inzenden met een boete van 15% voor elk van die dagen (extra dagen).

• U kunt extra dagen te laat en extra dagen te laat niet combineren om meer dan twee dagen te laat in te dienen.

Voor probleemreeksen: Te laat inleveren wordt niet geaccepteerd, met of zonder boete. Zorg ervoor dat u op tijd inlevert.

Stijlgids voor projecten

Naast het testen van de functionaliteit van uw code, zullen we ook een deel van de punten van elk project reserveren voor de stijl en leesbaarheid ervan. Het belangrijkste is een consistente en leesbare stijl. We kijken vooral of je een stijl hebt gekozen die leesbaar en redelijk is, en of je dezelfde stijl consequent gebruikt doorheen een project.Gebruik je gezond verstand: gebruik geen code van 500 karakters, noem je variabelen geen foo (tenzij dat logisch is in zijn context), en vermijd het willekeurig mixen van hoofdletterconventies.

We kijken naar de volgende dingen:

Documentatie Goede documentatie is belangrijk: voor jezelf in de toekomst, voor andere beheerders van de code, en in deze context, voor de beoordelaars die naar je code zullen kijken. Voel niet de noodzaak om elke regel code te documenteren (goede code zou in zekere zin ook zelf-documenterend moeten zijn), maar het is meestal goed om het algemene gebruik en doel van elke functie te belichten, evenals grote of complexe blokken code. Het is ook een goede gewoonte om in elk bestand een header op te nemen, waarin gedetailleerd wordt aangegeven hoe dat bestand past in de structuur van het project als geheel. Witruimte Wees consistent. Gebruik geen tab 2 spaties op sommige plaatsen en 4 op andere. Wees redelijk en gebruik witruimte om ervoor te zorgen dat uw code leesbaar is. Regellengte We zullen redelijk zijn over regellengte, zolang je maar consistent bent en je regellengte redelijk is (500 karakters is niet… 80 of 120 karakters is algemeen gebruikt en geaccepteerd). Namen van variabelen Uw namen van variabelen moeten een duidelijke indicatie geven van wat ze voorstellen of van hun gebruik. Dode/Test code Probeer geen code in te dienen die bezaaid is met debug print statements of grote stukken code die van commentaar zijn voorzien. Dit vermindert de leesbaarheid en leidt af van de code die daadwerkelijk in productie zal draaien. Ontwerp Probeer je code en projecten zo te ontwerpen dat ze redelijk modulair zijn. 5000-regelige functies zijn over het algemeen een teken van slecht ontwerp en zullen u later hoofdpijn bezorgen.

Hier is een Google stijlgids die nuttig kan zijn.

Welzijn

Hier zijn enkele tips voor welzijn.