Elosztott rendszerek

Tavaszi 2021

Áttekintés

15-440 az elosztott rendszerek bevezető kurzusa. A hangsúly a funkcionális, használható és skálázható elosztott rendszerek létrehozásának technikáin lesz. A témák konkretizálása érdekében az óra több többhetes, jelentős tervezést és megvalósítást igénylő projektet tartalmaz

A kurzus céljai kettősek. Először is, hogy a hallgatók megismerjék az elosztott rendszerek tervezésének alapelveit és technikáit, például a zárolást, az egyidejűséget, a gyorsítótárazást, az előhívást, az ütemezést és a hálózaton keresztüli kommunikációt. Másodszor, a hallgatók gyakorlati tapasztalatot szereznek valós elosztott rendszerek tervezésében, megvalósításában és hibakeresésében.

A főbb témák, amelyeket ez a kurzus tanítani fog, a következők:

• Az erőforrások szűkössége, ütemezés, és párhuzamosság
• Kommunikációs késleltetés és sávszélesség
• Nevezés
• Absztrakció és modularitás
• Tökéletlen kommunikáció és más típusú hibák
• Védelem a véletlen és rosszindulatú károktól
• Optimizmus
• Konszenzus
• A műszerek használata, Megfigyelési és hibakeresési eszközök a problémamegoldásban.
• A fenti témákat átfogó, jelentős programozási projektek tervezése, megvalósítása és hibakeresése

Besorolás

Minden tantárgyi munka egyénileg történik. Nincsenek csapatok vagy projektpartnerek. A kurzus (a COVID előtti és remélhetőleg a COVID utáni) személyes felajánlásainál az értékelés a projektek (45%), a feladatsorok (20%), a félévközi vizsga (15%) és a záróvizsga (20%) alapján történt. A kurzus 2021. tavaszi kínálatában a COVID megszorításai miatt a vizsgákat kumulatív feladatsorok váltják fel. Ezek olyanok, mint a nyitott könyvből írt vizsgák, de időnyomás nélkül. Ahogy a nevük is jelzi, az órán addig tárgyalt összes anyagot tartalmazzák. A többi feladatsort tematikus feladatsornak nevezzük, mivel ezek témákra összpontosítanak. A 2021 tavaszi értékelés tehát a következőképpen alakul (minden súlyozás hozzávetőleges, 5%-os súllyal):

• 45% a 4 projektre, egyenlő súlyozású
• 20% a 4 tematikus feladatsorra, egyenlő súlyozású
• 15% a félévközi összesített feladatsorra
• 20% a végső összesített feladatsorra.

Learning Outcomes

Elvárjuk, hogy a hallgatók mély megértést, folyékony érvelést és gyakorlati megvalósítási készségeket szerezzenek az elosztott rendszerek alábbi alapvető rendszerkoncepcióiban:

1. • Kommunikáció és távoli eljáráshívás
   • Vezérlési szemantika és nyelvi korlátok
   • Pontosan egyszer, legfeljebb egyszer, at-least-once
   • Serializáció és dezerializáció
   • End-to-end érvelés és annak alkalmazása valós rendszerekben
   • Integráció a szálkezeléssel
   • Műveletek párhuzamossága
2. • Adatok gyorsítótárazása és egy-másolat szemantika
   • Cache konzisztencia protokollok és megvalósítási kompromisszumok
   • A temporális és térbeli lokalitás eredete
   • Cache minőség mérőszámok
   • Alkalmazás-specifikus konzisztencia protokollok
   • Prefetching:
3. • Hibák az elosztott rendszerekben: eredete és empirikus vizsgálatok
   • Fail fast and Byzantine failures
   • Fundamental limits of failure resilience
4. • Fault tolerance:
   • A megvalósítás kihívásai
   • Shadowing, szándéklisták és write-ahead naplózás
   • A fizikai naplózás és a műveletnaplózás ellentétei
   • Beépített tranzakciók
   • Disztributált tranzakciók
5. • Consensus és blokklánc: Egyhangúság (kétfázisú commit)
   • Többségi (vezető választás, Paxos)
   • Byzantine (single-shot és Dolev-Strong)
   • State machine replikáció és Streamlet
   • Bitcoin

6. Közös programozási paradigmák, mint a Map-Reduce, MPI és GraphLab

7. (Csak ha az idő engedi):
   • Nagyfokú rendelkezésre állás elérése: az egy példányos szemantika szavazáson alapuló megőrzése
   • A replikációs stratégiák taxonómiája: Pesszimista és optimista megközelítések
   • Read-write és write-write konfliktusok
   • Server-kliens és peer-to-peer stratégiák
   • Caching és leválasztott működés; konfliktusok feloldása
   • A kis sávszélesség kihasználása a rendelkezésre állás javítása érdekében

Tanfolyami logisztika

Professzorok

Tanársegédek

Előadások

• kedden és csütörtökön 10:40-12:00
• Zoom linkek és videofelvételek: A kurzus Canvas oldalán
• Nincs óra: Február 23. kedd (szünnap), április 15. csütörtök (tavaszi farsang)
• Az utolsó óra:

Recitations

• Time: Wednesdaydays 7:00 – 7:50pm (Section A), 8:00 – 8:50pm (Section B)
• Zoom linkek és videofelvételek: Canvas oldalon ehhez a kurzushoz

Tanfolyami jegyzetek

A kurzus AFS területén lesz elhelyezve az alábbi címen: /afs/andrew/course/15/440/classnotes minden óra után. ezek a jegyzetek csak az Ön személyes használatára szolgálnak. Kérjük, ne terjessze őket.

Tankönyvek és választható olvasmányok

Nincsenek kötelező tankönyvek. Itt van három jó hivatkozás, amit választható olvasmányként használhat:

• “Elosztott rendszerek: Tanenbaum és Maarten Van Steen, harmadik (2017) kiadás, Prentice Hall
• “Guide to Reliable Distributed Systems” Kenneth P. Birman, Springer
• Foundations of Distributed Consensus and Blockchains by Elaine Shi (2020, Book manuscript)

Mellett a weboldal tetején található “Readings” link alatt található néhány konkrét, választható olvasmány, amelyeket az előadások különböző pontjain meg fogunk említeni. Ezeknek a választható olvasmányoknak a pdf-jei elérhetőek ezen a kurzus weboldalán.

Tanfolyami irányelvek

Előfeltételek

Miatt, hogy ennek a kurzusnak nagy projektkomponense van, jártasnak kell lennie a C és Java programozásban UNIX rendszereken. Feltétel, hogy a 15-213-as tantárgyat már elvégezte, és legalább “C”-t kapott, mivel a szükséges programozási ismeretek nagy részét abban a tantárgyban tanítják. Ha a 15-213-ban “C”-t kapott, akkor a 15-440 felvétele előtt találkoznia kell a tanulmányi tanácsadójával, hogy megbeszéljék a hátterét, esetleg egy további kurzus elvégzésével a rendszerismereteinek csiszolása érdekében.

A tanulmányi integritás szabályzata

A Carnegie Mellon Egyetem tanulmányi integritásról szóló szabályzata vonatkozik erre a kurzusra. Minden hallgatótól elvárjuk, hogy gondosan áttanulmányozza ezt a szabályzatot, és a kurzus minden vonatkozásában tartsa be.

Az együttműködésre vonatkozó irányelvek:

• A hallgatókat arra bátorítjuk, hogy beszéljenek egymással, a tanársegédekkel, az oktatókkal vagy bárki mással a feladatokról. Bármilyen segítségnek azonban a probléma megbeszélésére és a megoldás általános megközelítéseinek felvázolására kell korlátozódnia.
• Minden hallgatónak ki kell írnia a feladatsorok saját megoldásait. Minden feladatot egyénileg kell elkészíteni.
• Másik hallgató megoldását tilos átnézni, és a benyújtott megoldásokat semmilyen forrásból nem szabad lemásolni. Ezek a tevékenységek csalásnak minősülnek.
• Ha bármilyen kérdése van azzal kapcsolatban, hogy valamely tevékenység csalásnak minősül-e, kérdezze meg bátran az oktatókat.

A megosztásra vonatkozó útmutatás:

Felvételek

2021 tavaszán a CMU Computing Services minden egyes előadásról és előadásról felvételt készít, és azt a kurzus Canvas-oldalán közzéteszi. Minden más felvétel tilos.

A TA-idő felhasználásának korlátozása

Azért, hogy mindenkivel szemben méltányosak legyünk, különösen akkor, amikor hosszú sorban állnak a hallgatók, akik a TA figyelmére várnak, minden konzultációra 10 perc lesz a limit. Ha egy diák nem végez a 10 perc végére, akkor visszamegy a sor végére, mielőtt újabb időt kapna a TA-val. Készüljön fel, mielőtt találkozik a tanársegéddel. Ha segítségre van szüksége egy hiba megtalálásához, szűkítse és egyszerűsítse le a problémát a TA-val való találkozás előtt.

Piazza-szabályzat

Ez a kurzus a Piazza weboldalt használja a kérdések megválaszolására: itt van a kurzus Piazza oldala.

Gondoljon a piazza-ra úgy, mintha felemelné a kezét az órán és feltenne egy kérdést. Egyetlen kérdés sem túl hülye ahhoz, hogy feltegye, úgyhogy ne féljen. Minden egyes személyre, aki feltesz egy kérdést, valószínűleg sokan mások is vannak, akiknek ugyanez a kérdés már felmerült, vagy hamarosan felmerül. A kérdésedre adott válasz nekik is hasznára válhat. Ezenkívül lehetnek olyanok is, akiknek a kérdésed nem merült fel. Azzal, hogy felteszed a kérdést, segítesz nekik meglátni egy olyan finomságot, amelyet korábban talán nem láttak. Az oktatóknak küldött közvetlen e-mailekre nem válaszolunk.

Minden alkalommal elvárjuk, hogy józan ítélőképességeddel járj el a Piazza hozzászólásaidban (kérdések, valamint a diáktársak kérdéseire adott válaszok). A tanulási folyamat része, hogy addig küzdesz az anyaggal, amíg el nem jutsz a megfelelő felismeréshez, hogy megértsd azt. Ha túl sok részletet posztolsz egy segítségkérésre válaszul, az ronthatja a tanulást. Másrészt, néha jó, ha a helyes irányba löknek, amikor nem tudsz kilépni egy rögös útból. És természetesen a feladattal vagy a rendelkezésre álló eszközökkel kapcsolatos félreértéseken is gyorsan segíteni kell. Kérjük, hogy a legjobb belátásod szerint járj el, amikor a Piazza oldalra posztolsz, mintha személyesen dolgoznál együtt a barátaiddal. Néhány durva irányelv:

Példák arra, hogy milyen dolgokat érdemes posztolni és megválaszolni:

• A feladat félreértései
• A követelményekkel kapcsolatos pontosítások
• Hibák a feladat specifikációjában vagy a referencia implementációban vagy a tesztekben
• Kisebb, részletes kérdések a rendszerhívások, függvények stb. működésével kapcsolatban.
• Azok, amik úgy néznek ki, mintha a feladathoz tartozó GYIK-be tartoznának

Példák rossz dolgokra, amiket ki kellene írni vagy megválaszolni:

• Pár sor kódnál több
• Mélyreható magyarázatok a rendszered működéséről
• Kérdések a rendszer architektúrájának legjobb megközelítéséről magas szinten
• Kérdések a jegyedről

Elvárjuk, hogy ésszerű erőfeszítéseket tegyél a saját gondolkodásodra, mielőtt piazza kérdést teszel fel. Ez különösen igaz a kódod hibakeresésére. Kipróbáltad a man oldalakat? Csináltál egy Google keresést az esetlegesen releváns forrásokra? Megnézted a már feltett korábbi kérdéseket és az azokra adott válaszokat? Beillesztettél printf-eket, és megpróbáltad megérteni, hogy mi történik a kódoddal?

Ne használd az autolabot hibakeresési eszközként. Elvárjuk, hogy ésszerű erőfeszítéseket tegyen a kódja hibakeresésére, mielőtt beküldi az autolabba. A tesztesetek létrehozása és a kódod stressztesztelése része annak, amiről egy projekt szól. Ezen erőfeszítések megtétele nélkül a tanfolyam tanulási lehetőségének egy fontos részét hagyja ki. Az autolaborba való beküldésnek az utolsó lépésének kell lennie annak a folyamatnak, amelynek során tesztelte, hibakeresést végzett és a képességeihez mérten a lehető legteljesebb mértékben javította a kódját. Az autolab dump elküldése egy piazza-posztban azzal, hogy “kérem, segítsen”, a piazza etikett durva megsértése.

A Piazza magánposztjai nem támogatottak. Ez egy irányelvi döntés erre az osztályra vonatkozóan. Ne feledd, a piazzán való hozzászólás hasonló ahhoz, mintha felemelnéd a kezed és feltennél egy kérdést. A többi hallgatónak hasznára válik, ha felteszi a kérdést, és látja az oktató válaszát. Lehetővé tesszük, hogy a hozzászólásaid névtelenek legyenek a diáktársaid számára, ha úgy döntesz. Ez már egy olyan fokú magánéletet jelent, ami túlmutat azon, ami az órán történő kérdésfeltevés esetén lehetséges. Azokra a valóban ritka esetekre, amikor magánjellegű, a kurzus tartalmához nem kapcsolódó kérdéseket kell feltenned, létrehoztunk egy külön privát levelezőlistát.

Azokra a kérdésekre, amelyeknek valóban privátnak kell lenniük, küldj e-mailt a[email protected]címre, és az egyik oktató válaszolni fog. Az erre a listára küldött, a kurzus tartalmával kapcsolatos e-maileket (pl. az órai anyaggal kapcsolatos felvilágosítások) figyelmen kívül hagyjuk; az ilyen kérdéseket a Piazza oldalon kell feltennie.

Késedelmes beadványok szabályzata

Projektek esetében:

• Minden hallgatónak öt késedelmes nap áll rendelkezésére a félév során. Ezek a késedelmes napok az ünnepek, utazások, interjúk, megfázás és más hasonló helyzetek figyelembe vételére szolgálnak. Ezeket bármilyen okból szabadon felhasználhatja, anélkül, hogy engedélyt kérne az oktatóktól. Egy esedékességi napon legfeljebb két késedelmes napot használhat fel (azaz több ellenőrzési pontot tartalmazó projektek esetén ellenőrzési pontonként legfeljebb két késedelmes napot használhat fel). A késedelmes napok automatikusan időrendi sorrendben kerülnek alkalmazásra, így nem dönthet úgy, hogy egy késedelmes nap használatát egy nagyobb súlyú jövőbeli feladatra halasztja.

• Egy késedelmes nap = (0,24] órával az esedékesség után; két késedelmes nap = (24, 48] órával az esedékesség után; stb.

• Ha az összes késedelmes napját felhasználja, legfeljebb két napra 15%-os büntetés ellenében adhatja be késedelmesen. Más szóval, ha az összes késedelmes napját kimerítette, a következő két napban még benyújthatja a beadandóját, de ezekre a napokra (türelmi napok) 15%-os büntetést kell fizetnie.

• A késedelmes napokat és a türelmi napokat nem kombinálhatja, hogy két napnál többet késve nyújtson be.

A feladatsorok esetében: Nem fogadunk el késedelmes beadványokat, sem büntetéssel, sem büntetés nélkül. Győződjön meg róla, hogy időben benyújtja.

Stílus útmutató a projektekhez

A kódja funkcionalitásának tesztelése mellett minden projekt pontjainak egy részét a stílusra és az olvashatóságra is fenntartjuk. A legfontosabb a következetes és olvasható stílus. Leginkább azt nézzük, hogy olyan stílust választottál-e, amely olvasható és ésszerű, és hogy ugyanazt a stílust következetesen használod-e a projekt során. használd a józan észt: ne legyenek 500 karakteres kódsorok, ne nevezd a változókat foo-nak (hacsak annak nincs értelme a szövegkörnyezetben), és kerüld az esetkonvenciók véletlenszerű keverését.

A következő dolgokra fogunk figyelni:

Dokumentáció A jó dokumentáció fontos: saját magad számára a jövőben, a kód más karbantartói számára, és ebben az összefüggésben az osztályozók számára, akik meg fogják nézni a kódodat. Ne érezd szükségét, hogy minden egyes kódsort dokumentálj (hiszen a jó kódnak bizonyos értelemben öndokumentálónak is kell lennie), de általában jó, ha kiemeled az egyes függvények általános használatát és célját, valamint a nagy vagy összetett kódblokkokat. Az is jó gyakorlat, ha minden fájlban szerepel egy fájlfejléc, amely részletezi, hogy az adott fájl hogyan illeszkedik a projekt egészének szerkezetébe. Fehér tér Kérjük, legyen következetes. Kérjük, ne használjon egyes helyeken 2, máshol 4 szóközt. Legyen ésszerű és használja a white-space-t, hogy a kód olvasható legyen. Sorhossz A sorhosszúsággal kapcsolatban ésszerűek leszünk, amennyiben következetesek vagyunk, és a sorhatárok ésszerűek (500 karakter nem… 80 vagy 120 karakter az általánosan használt és elfogadott). Változónevek A változók nevének egyértelműen jeleznie kell, hogy mit képviselnek, illetve hogy milyen esetben használják őket. Holt/tesztkód Próbáljon meg nem olyan kódot beküldeni, amely tele van hibakeresési nyomtatási utasításokkal vagy nagy kommentált kódrészletekkel. Ez csökkenti az olvashatóságot, és elvonja a figyelmet arról a kódról, amely ténylegesen futni fog a gyártásban. Tervezés Próbálja meg úgy megtervezni a kódot és a projekteket, hogy azok ésszerűen modulárisak legyenek. Az 5000 soros függvények általában a rossz tervezés jelei, és később fejfájást okoznak.

Itt van egy Google stílus útmutató, ami hasznos lehet.

Jólét

Itt van néhány tipp a jóléthez.