Sisteme distribuite

Primăvara anului 2021

Vizualitate generală

15-440 este un curs introductiv în domeniul sistemelor distribuite. Se va pune accentul pe tehnicile de creare a unor sisteme distribuite funcționale, utilizabile și scalabile. Pentru a face problemele mai concrete, cursul include mai multe proiecte de mai multe săptămâni care necesită o proiectare și implementare semnificativă

Obiectivele acestui curs sunt duble. În primul rând, ca studenții să dobândească o înțelegere a principiilor și tehnicilor care stau la baza proiectării sistemelor distribuite, cum ar fi blocarea, concurența, memoria cache, prefetching, programarea și comunicarea în rețea. În al doilea rând, pentru ca studenții să dobândească experiență practică în proiectarea, implementarea și depanarea sistemelor distribuite reale.

Telemele majore pe care le va preda acest curs includ:

• Riscuitatea resurselor, programarea, și concurența
• Letența de latență și lățimea de bandă a comunicațiilor
• Denumirea
• Abstracția și modularitatea
• Comunicarea imperfectă și alte tipuri de eșecuri
• Protecția împotriva daunelor accidentale și rău intenționate
• Optimism
• Consensus
• Utilizarea instrumentarului, monitorizare și a instrumentelor de depanare în rezolvarea problemelor.
• Proiectarea, implementarea și depanarea unor proiecte de programare substanțiale care acoperă temele de mai sus

Notarea

Toate lucrările de curs se fac individual. Nu există echipe sau parteneri de proiect. Pentru ofertele în persoană ale acestui curs (pre-COVID și, sperăm, post-COVID), evaluarea s-a bazat pe proiecte (45%), seturi de probleme (20%), examen intermediar (15%) și examen final (20%). Pentru oferta de primăvară 2021 a cursului, din cauza constrângerilor COVID, examenele sunt înlocuite de seturi de probleme cumulative. Acestea sunt ca niște examene cu caiet deschis, dar fără presiunea timpului. După cum sugerează și numele lor, acestea includ tot materialul abordat în clasă până la acel moment. Ne referim la celelalte seturi de probleme ca fiind seturi de probleme tematice, deoarece acestea se concentrează pe subiecte. Așadar, evaluarea din primăvara anului 2021 va fi următoarea (toate ponderile sunt aproximative, într-un interval de 5%):

• 45% pentru 4 proiecte, cu pondere egală
• 20% pentru 4 seturi de probleme topice, cu pondere egală
• 15% pentru setul de probleme cumulative de la jumătatea semestrului
• 20% pentru setul final de probleme cumulative.

Rezultatele învățării

Ne așteptăm ca studenții să dobândească o înțelegere profundă, fluență în raționament și abilități de implementare practică a următoarelor concepte de bază ale sistemelor distribuite:

1. • Comunicare și apel de procedură la distanță
   • Semantica de control și limitările limbajului
   • Exact o dată, cel mult o dată, at-least-once
   • Serializare și de-serializare
   • Argumentul end-to-end și aplicarea sa la sisteme reale
   • Integrarea cu threading
   • Concurența operațiilor
2. • Caching de date și unu-copie
   • Protocoale de consistență a cache-ului și compromisuri de implementare
   • Origini ale localității temporale și spațiale
   • Metrice de calitate a cache-ului
   • Protocoale de consistență specifice aplicației
   • Prefetching: Beneficii și riscuri
   • Extracția de indicii
   • Buffer bloat
3. • Eșecuri în sistemele distribuite: origini și studii empirice
   • Eșecuri rapide și eșecuri bizantine
   • Limitele fundamentale ale rezilienței la eșecuri
4. • Toleranța la eșecuri: Tranzacții atomice; proprietatea ACID
   • Provocări de implementare
   • Shadowing, liste de intenții și write-ahead logging
   • Tradeoffs in physical logging and operation logging
   • Tranzacții înglobate
   • Tranzacții distribuite
5. • Consensus și blockchain: unanimitate (comitere în două faze)
   • Majoritate (alegerea liderului, Paxos)
   • Byzantine (single-shot și Dolev-Strong)
   • Replicarea mașinilor de stat și Streamlet
   • Bitcoin

6. Paradigme comune de programare, cum ar fi Map-Reduce, MPI și GraphLab

7. (Numai dacă timpul permite):
   • Obținerea unei disponibilități ridicate: conservarea pe bază de vot a semanticii unei singure copii
   • Taxonomie a strategiilor de replicare: abordări pesimiste și optimiste
   • Conflicte de citire-scriere și scriere-scriere
   • Servere-client și strategii peer-to-peer
   • Caching și funcționare deconectată; rezolvarea conflictelor
   • Exploatarea lățimii de bandă reduse pentru a îmbunătăți disponibilitatea

Logistica cursurilor

Profesori

.

Nume	Ora de lucru	Oficiu	Telefon	Andrew email
Mahadev Satyanarayanan (Satya)	Marți 1:00 – 3:00 pm	GHC-9123	x8-3743	satya
Padmanabhan Pillai (Babu)	Miercuri 11:00 am – 1:00 pm	GHC-9232			pspillai
Runting Shi (Elaine)		Luni 4:00 – 6:00 pm		CIC-2217		Contact prin Canvas

Asistenți de predare

.

Nume	Ora de lucru	Andrew email
Nathan Ang		Thu 2:00-4:00 pm	nathanan
Junwon Chang (Joseph)	Sâmbătă 9:00-11:00 am	junwonc
Wenxin Ding (Freda)	Vin 10:00-12:00	wenxind
Timothy Ganger	Sat 4:00-18:00 pm	tganger
Ziying He	Vin 5:00-19:00 pm	ziyingh
Roger Iyengar	Miercuri 1:00-15:00 pm	raiyenga
Ishaan Jaffer	Joi 4:00-18:00 pm	ijaffer
Ibnul Jahan	Miercuri 4:00-18:00 pm	iej
Chen Jin (Crystal)	Vin 8:00-10:00	chenj
Yajin Li	Luni 10:00-12:00 pm	yajinl
Diego San Miguel	Vin 2:00-16:00 pm	dsanmigu
Riccardo Santoni	Luni 8:00-22:00 pm	rsantoni
Yiwen Song (Victor)	Joi 9:00-11:00 pm	yiwenson
Haithem Turki	Miercuri 3:00-5:00 pm	hturki
Clarissa Xu	Marți 6:30-8:30 pm	csxu

Lecții

• Marți și joi, 10:40 – 12:00 pm
• Legături de zoom și înregistrări video: Pe pagina Canvas pentru acest curs
• Niciun curs: Marți 23 februarie (zi de pauză), Joi 15 aprilie (Carnavalul de primăvară)
• Ultimul curs: Joi, 6 mai

Repetiții

• Ora: Miercuri 19:00-19:50 (Secțiunea A), 20:00-20:50 (Secțiunea B)
• Legături de zoom și înregistrări video: Pe pagina Canvas pentru acest curs

Anotații de curs

Vor fi plasate în zona AFS a cursului la adresa:

Anotații de curs

: /afs/andrew/course/15/440/classnotes după fiecare curs.Aceste notițe sunt doar pentru uz personal. Vă rugăm să nu le distribuiți.

Cărți de curs și lecturi opționale

Nu există manuale obligatorii. Iată trei referințe bune de folosit pentru lecturi opționale:

• „Distributed Systems: Principles and Paradigms” de Andrew S. Tanenbaum și Maarten Van Steen, ediția a treia (2017), Prentice Hall
• „Guide to Reliable Distributed Systems” de Kenneth P. Birman, Springer
• Foundations of Distributed Consensus and Blockchains de Elaine Shi (2020, manuscrisul cărții)

În plus, link-ul „Lecturi” din partea de sus a acestei pagini web are câteva lecturi opționale specifce pe care le vom menționa în diferite momente ale cursurilor. PDF-urile acestor lecturi opționale sunt disponibile pe site-ul acestui curs.

Politica cursului

Precondiții

Pentru că acest curs are o componentă mare de proiect, trebuie să aveți cunoștințe de programare C și Java pe sisteme UNIX. Este necesar să fi urmat cursul 15-213 și să fi obținut un „C” sau o notă mai mare, deoarece multe dintre abilitățile de programare de care veți avea nevoie sunt predate în acel curs. Dacă ați primit un „C” la 15-213, trebuie să vă întâlniți cu consilierul dvs. academic pentru a discuta despre pregătirea dvs. înainte de a urma 15-440, poate urmând un curs suplimentar pentru a vă perfecționa abilitățile în domeniul sistemelor.

Politica privind integritatea academică

Politica privind integritatea academică a Universității Carnegie Mellon se aplică acestui curs. Se așteaptă ca toți studenții să analizeze cu atenție această politică și să o respecte pentru toate aspectele acestui curs.

Guidance on Collaboration:

• Studenții sunt încurajați să vorbească între ei, cu asistenții tehnici, cu instructorii sau cu oricine altcineva despre oricare dintre sarcini. Cu toate acestea, orice asistență trebuie să se limiteze la discutarea problemei și la schițarea unor abordări generale pentru o soluție.
• Care student trebuie să-și scrie propriile soluții la seturile de probleme. Toate proiectele trebuie să fie realizate individual.
• Consultarea soluției unui alt student este interzisă, iar soluțiile prezentate nu pot fi copiate din nicio sursă. Aceste acțiuni constituie înșelăciune.
• Dacă aveți întrebări cu privire la faptul că o anumită activitate ar constitui înșelăciune, nu ezitați să întrebați instructorii.

Ghiduri privind partajarea: Nu aveți voie să furnizați lucrările pe care le finalizați în timpul cursului 15-440 altor studenți în instanțe viitoare ale acestui curs sau pentru a fi utilizate în instanțe viitoare ale acestui curs (la fel cum nu puteți utiliza lucrările finalizate de studenții care au urmat cursul anterior).

Înregistrări

Pentru primăvara anului 2021, sesiunile Zoom ale fiecărei prelegeri și recitări vor fi înregistrate de CMU Computing Services și postate pe pagina Canvas pentru acest curs. Toate celelalte înregistrări sunt interzise.

Limită de utilizare a timpului TA

Pentru a fi corect față de toată lumea, mai ales atunci când există o coadă lungă de studenți care așteaptă atenția unui TA, va exista o limită de 10 minute pentru toate consultațiile. Dacă un student nu a terminat la sfârșitul celor 10 minute, acesta se întoarce la capătul rândului înainte de a primi mai mult timp cu AT. Fiți pregătit înainte de a vă întâlni cu un TA. Dacă aveți nevoie de ajutor pentru a găsi o eroare, restrângeți și simplificați problema înainte de întâlnirea cu TA.

Politica Piazza

Acest curs folosește site-ul Piazza pentru a răspunde la întrebări: aici este pagina Piazza pentru acest curs.

Gândiți-vă la piazza ca și cum ați ridica mâna în clasă și ați pune o întrebare. Nicio întrebare nu este prea stupidă pentru a o pune, așa că nu vă fie teamă. Pentru fiecare persoană care pune o întrebare, există probabil multe altele cărora le-a apărut deja aceeași întrebare sau le va apărea în curând. Răspunsul la întrebarea dvs. le poate fi de folos și lor. În plus, este posibil să existe unele persoane cărora întrebarea dumneavoastră nu le-a apărut. Punând întrebarea, îi ajutați să vadă o subtilitate pe care poate că nu au văzut-o până acum. Nu se va răspunde la e-mailurile adresate direct instructorilor.

În orice moment, ne așteptăm să vă folosiți bunul simț în postările dumneavoastră din Piazza (atât întrebările, cât și răspunsurile la întrebările colegilor). O parte a procesului de învățare constă în a te lupta cu materia până când ajungi la percepția potrivită pentru a o înțelege. Postarea de prea multe detalii ca răspuns la o cerere de asistență poate afecta învățarea. Pe de altă parte, uneori este grozav să fii îndrumat în direcția corectă atunci când nu reușești să ieși din impas. Și, bineînțeles, neînțelegerile privind sarcina sau instrumentele disponibile trebuie ajutate rapid. Vă rugăm să vă folosiți cea mai bună judecată atunci când postați pe site-ul Piazza, ca și cum ați colabora cu prietenii dvs. în persoană. Câteva linii directoare aproximative:

Exemple de lucruri bune de postat și la care să răspundeți:

• Înțelegeri greșite ale temei
• Clarificări cu privire la cerințe
• Bugs în specificația temei sau în implementarea de referință sau în teste
• Întrebări mici, detaliate despre funcționarea apelurilor de sistem, a funcțiilor, etc.
• Ceasuri care par să meargă într-un FAQ pentru misiune

Exemple de lucruri proaste de postat sau de răspuns:

• Mai mult decât câteva linii de cod
• Explicații aprofundate despre cum funcționează sistemul dumneavoastră
• Întrebări despre cea mai bună abordare pentru arhitectura sistemului la un nivel înalt
• Întrebări despre nota dumneavoastră

Ne așteptăm să fi făcut un efort rezonabil pentru a gândi singur înainte de a posta o întrebare piazza. Acest lucru este valabil mai ales în ceea ce privește depanarea codului dvs. Ați încercat paginile de manual? Ați făcut o căutare pe Google pentru resurse posibil relevante? V-ați uitat la întrebările anterioare pe care oamenii le-au pus deja și la răspunsurile oferite? Ați inserat printf-uri și ați încercat să înțelegeți ce se întâmplă cu codul dumneavoastră?

Nu folosiți autolab ca instrument de depanare. Ne așteptăm să fi făcut un efort rezonabil pentru a vă depana codul înainte de a-l trimite la autolab. Crearea de cazuri de testare și testarea la stres a codului dvs. face parte din ceea ce înseamnă un proiect. Dacă nu depuneți acest efort, pierdeți o parte importantă a oportunității de învățare din cadrul cursului. Trimiterea la autolab ar trebui să fie ultimul pas al unui proces în care v-ați testat, depanat și îmbunătățit codul în cea mai mare măsură a abilităților dumneavoastră. Trimiterea unui autolab dump într-o postare în piazza și spunând „vă rog să mă ajutați” este o încălcare flagrantă a etichetei piazza.

Postările private în Piazza nu sunt acceptate. Aceasta este o decizie de politică pentru această clasă. Nu uitați, a posta pe piazza este similar cu a ridica mâna și a pune o întrebare. Ceilalți studenți beneficiază de pe urma întrebării dvs. și de faptul că vedeți răspunsul instructorilor. Permitem ca postările dvs. să fie anonime pentru colegii de clasă, dacă doriți. Acesta este deja un grad de confidențialitate care depășește ceea ce este posibil atunci când puneți o întrebare în clasă. Pentru ocaziile cu adevărat rare în care aveți nevoie să faceți o cerere privată care nu are legătură cu conținutul cursului, a fost creată o listă specială de corespondență privată.

Pentru cererile care trebuie cu adevărat să fie private Trimiteți un e-mail la

[email protected]și unul dintre instructori vă va răspunde. E-mailurile către această listă care implică conținutul cursului (de exemplu, clarificări la materialul de curs) vor fi ignorate; ar trebui să postați astfel de întrebări pe Piazza.

Politica privind întârzierile

Pentru proiecte:

• Care student va avea la dispoziție cinci zile de întârziere pe care le va folosi pe parcursul semestrului. Aceste zile de întârziere sunt destinate să țină cont de vacanțe, călătorii, interviuri, o răceală și alte situații similare. Sunteți liberi să le folosiți pentru orice motiv, fără să cereți permisiunea instructorilor. Puteți folosi cel mult două zile de întârziere pentru orice dată de scadență (de exemplu, pentru proiectele cu mai multe puncte de control, puteți folosi până la două zile de întârziere pentru fiecare punct de control). Zilele de întârziere vor fi aplicate automat în ordine cronologică, astfel încât nu puteți alege să amânați utilizarea unei zile de întârziere pentru o lucrare viitoare cu o pondere mai mare.

• O zi de întârziere = (0,24] ore după data scadentă; două zile de întârziere = (24, 48] ore după data scadentă; etc.

• Dacă utilizați toate zilele de întârziere, puteți depune lucrările cu întârziere cu o penalizare de 15% pe zi, timp de maximum două zile. Cu alte cuvinte, dacă v-ați folosit toate zilele de întârziere, puteți depune în continuare pentru următoarele două zile, suportând o penalizare de 15% pentru fiecare dintre aceste zile (zile de grație).

• Nu puteți combina zilele de întârziere și zilele de grație pentru a depune cu mai mult de două zile întârziere.

Pentru seturile de probleme: Nu se acceptă depunerea cu întârziere, cu sau fără penalizare. Asigurați-vă că depuneți la timp.

Ghid de stil pentru proiecte

Pe lângă testarea funcționalității codului dumneavoastră, vom rezerva, de asemenea, o parte din punctele fiecărui proiect pentru stilul și lizibilitatea acestuia. Cel mai important lucru este un stil coerent și lizibil. Ne interesează mai ales să vedem că ați ales un stil care este lizibil și rezonabil și că folosiți același stil în mod consecvent pe parcursul unui proiect.Folosiți bunul simț: nu aveți linii de cod de 500 de caractere, nu vă numiți variabilele foo (decât dacă acest lucru are sens în contextul său) și evitați să amestecați la întâmplare convențiile de majuscule și minuscule.

Vom căuta următoarele lucruri:

Documentație O documentație bună este importantă: pentru dumneavoastră în viitor, pentru alți mentenanți ai codului și, în acest context, pentru evaluatorii care se vor uita la codul dumneavoastră. Nu simțiți nevoia să documentați fiecare linie de cod (deoarece un cod bun ar trebui, de asemenea, să se autodocumenteze într-un anumit sens), dar de obicei este bine să evidențiați utilizarea și scopul general al fiecărei funcții, precum și blocurile mari sau complexe de cod. De asemenea, este o bună practică să includeți un antet de fișier în fiecare fișier, detaliind modul în care fișierul respectiv se încadrează în structura proiectului ca întreg. Spațiul alb Vă rugăm să fiți consecvent. Vă rugăm să nu folosiți tab 2 spații în unele locuri și apoi 4 în altele. Fiți rezonabili și folosiți spațiile albe pentru a vă asigura că codul dvs. este lizibil. Lungimea liniilor Vom fi rezonabili în ceea ce privește lungimea liniilor, atâta timp cât sunteți consecvent și limitele liniilor sunt rezonabile (500 de caractere nu este… 80 sau 120 de caractere sunt utilizate și acceptate în mod obișnuit). Nume de variabile Numele variabilelor Numele variabilelor dvs. trebuie să ofere o indicație clară a ceea ce reprezintă sau a cazului de utilizare a acestora. Dead/Test Code Încercați să nu trimiteți coduri care sunt pline de declarații de depanare (debug print statements) sau bucăți mari de cod comentate. Aceasta diminuează lizibilitatea și distrage atenția de la codul care va rula efectiv în producție. Proiectare Încercați să vă proiectați codul și proiectele în așa fel încât să fie rezonabil de modulare. Funcțiile de 5000 de linii sunt, în general, un semn de proiectare slabă și vă vor da dureri de cap mai târziu.

Iată un ghid de stil Google care vă poate fi de ajutor.

Bunăstare

Iată câteva sfaturi pentru bunăstare.

.