Distribuerede systemer

Forår 2021

Overblik

15-440 er et introduktionskursus i distribuerede systemer. Der vil blive lagt vægt på teknikker til at skabe funktionelle, anvendelige og skalerbare distribuerede systemer. For at gøre emnerne mere konkrete omfatter kurset flere flerugersprojekter, der kræver omfattende design og implementering

Målene med dette kursus er todelt. For det første skal de studerende få en forståelse af de principper og teknikker, der ligger bag designet af distribuerede systemer, såsom låsning, samtidighed, caching, prefetching, planlægning og kommunikation på tværs af netværket. For det andet skal de studerende få praktisk erfaring med at designe, implementere og fejlfinde reelle distribuerede systemer.

De vigtigste temaer, som dette kursus vil undervise i, omfatter:

• Ressourceknaphed, skemalægning, og samtidighed
• Kommunikationslatenstid og båndbredde
• Navngivning
• Abstraktion og modularitet
• Imperfekt kommunikation og andre typer af fejl
• Beskyttelse mod utilsigtet og ondsindet skade
• Optimisme
• Konsensus
• Brug af instrumentering, overvågnings- og fejlfindingsværktøjer i forbindelse med problemløsning.
• Design, implementering og fejlfinding af omfattende programmeringsprojekter, der spænder over ovennævnte temaer

Bedømmelse

Alt kursusarbejde udføres individuelt. Der er ingen hold eller projektpartnere. I forbindelse med de personlige tilbud af dette kursus (før-COVID og forhåbentlig også efter-COVID) var evalueringen baseret på projekter (45%), problemstillinger (20%), midtvejsprøve (15%) og afsluttende eksamen (20%). I foråret 2021, hvor kurset udbydes på grund af COVID-krav, erstattes eksamenerne af kumulative problemsæt. Disse er som åbne eksamener, men uden tidspres. Som navnet antyder, omfatter de alt det materiale, der er blevet behandlet i klassen indtil da. Vi kalder de andre problemsæt for aktuelle problemsæt, da de fokuserer på emner. Så evalueringen i foråret 2021 vil være som følger (alle vægte er omtrentlige, inden for et interval på 5 %):

• 45 % for 4 projekter, ligeligt vægtet
• 20 % for 4 aktuelle problemsæt, ligeligt vægtet
• 15 % for det kumulative problemsæt midt på semestret
• 20 % for det endelige kumulative problemsæt.

Læringsresultater

Vi forventer, at de studerende opnår en dyb forståelse, en flydende ræsonnementsevne og praktiske implementeringsfærdigheder inden for følgende centrale systemkoncepter i distribuerede systemer:

1. • Kommunikation og remote procedure call
   • Kontrolsemantik og sproglige begrænsninger
   • Exactly-once, at-most-once, at-least-once
   • Serialisering og de-serialisering
   • End-to-end-argument og dets anvendelse på reelle systemer
   • Integration med threading
   • Samtidighed i operationer
2. • Data caching og one-kopi-semantik
   • Cache-konsistensprotokoller og kompromiser i forbindelse med implementering
   • Originerne til tidsmæssig og rumlig lokalitet
   • Cache-kvalitetsmålinger
   • Applikationsspecifikke konsistensprotokoller
   • Prefetching: Fordele og risici
   • Udtrækning af hints
   • Buffer bloat
3. • Fejl i distribuerede systemer: oprindelse og empiriske undersøgelser
   • Fail fast and Byzantine failures
   • Fundamental limits of failure resilience
4. • Fault tolerance: atomiske transaktioner; ACID-egenskab
   • Udfordringer i forbindelse med implementering
   • Shadowing, intentionslister og write-ahead logging
   • Tradeoffs i fysisk logging og operation logging
   • Nested transactions
   • Distributed transactions
5. • Consensus og blockchain: enstemmighed (to-fase commit)
   • Majoritet (ledervalg, Paxos)
   • Byzantine (single-shot og Dolev-Strong)
   • State machine replication and Streamlet
   • Bitcoin

6. Gængse programmeringsparadigmer som Map-Reduce, MPI og GraphLab

7. (Kun hvis tiden tillader det):
   • Høj tilgængelighed: afstemningsbaseret bevarelse af én-kopi-semantik
   • Taxonomi af replikationsstrategier: pessimistiske og optimistiske tilgange
   • Læse-skrive- og skrive-skrive-konflikter
   • Server-klient- og peer-to-peer-strategier
   • Caching og afbrudt drift; løsning af konflikter
   • Udnyttelse af lav båndbredde for at forbedre tilgængeligheden

Kursuslogistik

Professorer

Undervisningsassistenter

Foredrag

• Tirsdage og torsdage, kl. 10:40 – 12:00
• Zoom links og videooptagelser: På Canvas-siden for dette kursus
• Ingen undervisning: Tirsdag d. 23. februar (feriedag), torsdag d. 15. april (forårskarneval)
• Sidste undervisningsgang:
• Torsdag den 6. maj

Recitationer

• Tidspunkt: Onsdage kl. 19:00-19:50 (afdeling A), kl. 20:00-20:50 (afdeling B)
• Zoom-links og videooptagelser: På Canvas-siden for dette kursus

Kursusnoter

Vil blive placeret i kursets AFS-område på: /afs/andrew/course/15/440/classnotes efter hver lektion.Disse noter er kun til personlig brug. De må ikke distribueres.

Tekstbøger og valgfri læsning

Der er ingen obligatoriske tekstbøger. Her er tre gode referencer, der kan bruges som valgfri læsning:

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

Dertil kommer, at linket “Readings” øverst på denne webside har nogle specifikke valgfrie læsninger, som vi vil nævne på forskellige tidspunkter i forelæsningerne. PDF’erne af disse valgfrie læsninger er tilgængelige på dette kursuswebsted.

Kursusregler

Forudsætninger

Da dette kursus har en stor projektkomponent, skal du være god til at programmere i C og Java på UNIX-systemer. Det er et krav, at du har taget 15-213 og fået et “C” eller højere, da mange af de programmeringsfærdigheder, du får brug for, undervises i dette kursus. Hvis du fik et C i 15-213, skal du mødes med din akademiske vejleder for at drøfte din baggrund, inden du tager 15-440. Du kan eventuelt tage et ekstra kursus for at skærpe dine systemfærdigheder.

Politik om akademisk integritet

Carnegie Mellon University Policy on Academic Integrity gælder for dette kursus. Det forventes, at alle studerende omhyggeligt gennemgår denne politik og overholder den for alle aspekter af dette kursus.

Rådgivning om samarbejde:

• De studerende opfordres til at tale med hinanden, med TA’erne, med instruktørerne eller med andre om opgaverne. Enhver hjælp skal dog begrænses til diskussion af problemet og skitsering af generelle tilgange til en løsning.
• Den enkelte studerende skal skrive sine egne løsninger på opgavesættene ud. Alle opgaver skal udføres individuelt.
• Det er forbudt at konsultere en anden studerendes løsning, og de indsendte løsninger må ikke kopieres fra nogen kilde. Disse handlinger udgør snyd.
• Hvis du har spørgsmål om, hvorvidt en bestemt aktivitet udgør snyd, er du velkommen til at spørge instruktørerne.

Vejledning om deling: Du må ikke udlevere arbejde, som du laver i 15-440, til andre studerende i fremtidige tilfælde af dette kursus eller til brug i fremtidige tilfælde af dette kursus (ligesom du ikke må bruge arbejde, der er lavet af studerende, som har taget kurset tidligere).

Optagelser

I foråret 2021 vil Zoom-sessioner af hver forelæsning og oplæsning blive optaget af CMU Computing Services og lagt ud på Canvas-siden for dette kursus. Alle andre optagelser er forbudt.

Begrænsning på brugen af TA-tid

For at være fair over for alle, især når der er en lang kø af studerende, der venter på en TA’s opmærksomhed, vil der være en begrænsning på 10 minutter på alle konsultationer. Hvis en studerende ikke er færdig efter de 10 minutter, skal han/hun gå tilbage til enden af køen, før han/hun kan få mere tid med en assistent. Vær forberedt, inden du mødes med en assistent. Hvis du har brug for hjælp til at finde en fejl, skal du indsnævre og forenkle problemet inden mødet med TA’en.

Piazza-politik

Dette kursus bruger webstedet Piazza til at besvare spørgsmål: her er siden om Piazza for dette kursus.

Tænk på piazza som at række hånden op i klassen og stille et spørgsmål. Intet spørgsmål er for dumt at stille, så du skal ikke være bange. For hver person, der stiller et spørgsmål, er der sikkert mange andre, for hvem det samme spørgsmål allerede er opstået eller snart vil opstå. Svaret på dit spørgsmål kan også være til gavn for dem. Desuden kan der være nogle mennesker, som dit spørgsmål ikke er opstået for. Ved at stille spørgsmålet hjælper du dem med at se en finesse, som de måske ikke har set før. Direkte e-mails til instruktørerne vil ikke blive besvaret.

Vi forventer til enhver tid, at du bruger din gode dømmekraft i dine indlæg på Piazza (spørgsmål såvel som svar på spørgsmål fra medstuderende). En del af læringsprocessen er at kæmpe med stoffet, indtil du når frem til den rette indsigt, så du forstår det. Hvis du skriver for mange detaljer som svar på en anmodning om hjælp, kan det skade din indlæring. På den anden side er det nogle gange godt at blive skubbet i den rigtige retning, når man ikke er i stand til at komme ud af en rutine. Og selvfølgelig skal misforståelser af opgaven eller de tilgængelige værktøjer hjælpes hurtigt. Brug venligst din bedste dømmekraft, når du skriver på Piazza-webstedet, som om du samarbejdede med dine venner personligt. Et par grove retningslinjer:

Eksempler på gode ting at skrive og besvare:

• Misforståelser af opgaven
• Klargørelser om kravene
• Bugs i opgavespecifikationen eller referenceimplementationen eller testene
• Små, detaljerede spørgsmål om driften af systemkald, funktioner osv.
• Ting, der ser ud til at høre hjemme i en FAQ til opgaven

Eksempler på dårlige ting at skrive eller besvare:

• Mere end et par linjer kode
• Dybdegående forklaringer på, hvordan dit system fungerer
• Spørgsmål om den bedste tilgang til arkitektur af systemet på et højt niveau
• Spørgsmål om din karakter

Vi forventer, at du har gjort en rimelig indsats for at tænke selv, inden du stiller et piazza-spørgsmål. Dette gælder især med hensyn til fejlfinding af din kode. Har du prøvet man-siderne? Har du foretaget en Google-søgning efter eventuelt relevante ressourcer? Har du kigget på de tidligere spørgsmål, som folk allerede har stillet, og på de svar, der er givet? Har du indsat printf’er og forsøgt at forstå, hvad der sker med din kode?

Brug ikke autolab som fejlfindingsværktøj. Vi forventer, at du har gjort en rimelig indsats for at få debugget din kode, inden du indsender den til autolab. Oprettelse af testcases og stresstest af din kode er en del af det, som et projekt handler om. Hvis du ikke gør denne indsats, går du glip af en vigtig del af læringsmuligheden i kurset. Indsendelse til autolab bør være det sidste skridt i en proces, hvor du har testet, fejlsøgt og forbedret din kode i videst muligt omfang. At sende et autolab-dump i et piazza-indlæg og sige “please help” er en grov overtrædelse af piazza-etikette.

Private indlæg på Piazza understøttes ikke. Dette er en politisk beslutning for denne klasse. Husk, at indlæg på piazza svarer til at række hånden op og stille et spørgsmål. Andre studerende har gavn af, at du stiller spørgsmålet og ser instruktørens svar. Vi tillader dog, at dine indlæg kan være anonyme for dine medstuderende, hvis du ønsker det. Det er allerede en højere grad af privatlivets fred end det, der er muligt, når man stiller et spørgsmål i klassen. For de virkelig sjældne tilfælde, hvor du har brug for at fremsætte en privat forespørgsel, der ikke er relateret til kursusindholdet, er der oprettet en særlig privat postliste.

For forespørgsler, der virkelig har brug for at være private Send en e-mail til[email protected], og en af underviserne vil svare. E-mails til denne liste, der vedrører kursusindhold (f.eks. afklaring af undervisningsmateriale), vil blive ignoreret; du bør sende sådanne spørgsmål på Piazza.

Politik vedrørende forsinkede indsendelser

For projekter:

• Hver studerende vil have fem forsinkelsesdage til rådighed i løbet af semesteret. Disse forsinkelsesdage er beregnet til at tage højde for helligdage, rejser, interviews, forkølelse og andre lignende situationer. Det står dig frit for at bruge dem af enhver grund, uden at du behøver at bede om tilladelse fra underviserne. Du kan højst bruge to forsinkelsesdage på en given forfaldsdato (dvs. for projekter med flere kontrolpunkter kan du bruge op til to forsinkelsesdage for hvert kontrolpunkt). Forsinkelsesdage vil automatisk blive anvendt i kronologisk rækkefølge, så du kan ikke vælge at udskyde brugen af en forsinkelsesdag til en fremtidig opgave med højere vægt.

• En forsinkelsesdag = (0,24] timer efter forfaldsdatoen; to forsinkelsesdage = (24, 48] timer efter forfaldsdatoen osv.

• Hvis du bruger alle dine forsinkelsesdage, kan du aflevere for sent med en straf på 15 % pr. dag i op til to dage. Med andre ord, hvis du har brugt alle dine forsinkelsesdage, kan du stadig aflevere i de næste to dage med en straf på 15 % for hver af disse dage (fritagelsesdage).

• Du kan ikke kombinere forsinkelsesdage og fritagelsesdage for at aflevere mere end to dage for sent.

For opgavesæt: Der accepteres ingen forsinkede indsendelser, med eller uden straf. Sørg for at aflevere til tiden.

Stilvejledning for projekter

Ud over at teste din kodes funktionalitet vil vi også reservere en del af hvert projekts point til dets stil og læsevenlighed. Det vigtigste er en ensartet og læsbar stil. Vi kigger mest efter at se, at du har valgt en stil, der er læsbar og fornuftig, og at du bruger den samme stil konsekvent i hele projektet. brug sund fornuft: lad være med at have 500-tegns linjer kode, lad være med at navngive dine variabler foo (medmindre det giver mening i sin sammenhæng), og undgå at blande case-konventioner tilfældigt.

Vi vil kigge efter følgende ting:

Dokumentation God dokumentation er vigtig: for dig selv i fremtiden, for andre, der vedligeholder koden, og i denne sammenhæng for de censorer, der skal kigge på din kode. Du skal ikke føle dig nødsaget til at dokumentere hver eneste kodelinje (da god kode på en måde også bør være selvdokumenterende), men det er normalt godt at fremhæve den generelle brug og formålet med hver enkelt funktion, samt store eller komplekse blokke af kode. Det er også god praksis at medtage en filoverskrift i hver fil, der beskriver, hvordan filen passer ind i projektets struktur som helhed. White-space Vær venligst konsekvent. Brug ikke tabulatoren med 2 mellemrum nogle steder og 4 andre steder. Vær fornuftig og brug white-space for at sikre, at din kode er læsbar. Linjelængde Vi vil være rimelige med hensyn til linjelængde, så længe du er konsekvent og dine linjelængder er rimelige (500 tegn er ikke… 80 eller 120 tegn er almindeligt anvendt og accepteret). Variabelnavne Dine variabelnavne skal give en klar indikation af, hvad de repræsenterer, eller hvad de anvendes til. Død/testkode Prøv ikke at indsende kode, der er fyldt med debug-udskrivningsmeddelelser eller store kommenterede kodestykker. Det forringer læsbarheden og distraherer fra den kode, der rent faktisk skal køre i produktionen. Design Forsøg at designe din kode og dine projekter på en sådan måde, at de er rimeligt modulære. 5000-linjers funktioner er generelt et tegn på dårligt design og vil give dig hovedpine senere.

Her er en Google-stilguide, der kan være nyttig.

Velfærd

Her er nogle tips til velfærd.