Hajautetut järjestelmät

Kevät 2021

Yleiskatsaus

15-440 on hajautettujen järjestelmien johdantokurssi. Pääpaino on tekniikoissa, joilla luodaan toimivia, käyttökelpoisia ja skaalautuvia hajautettuja järjestelmiä. Asioiden konkretisoimiseksi kurssiin sisältyy useita moniviikkoisia projekteja, jotka vaativat merkittävää suunnittelua ja toteutusta

Kurssin tavoitteet ovat kaksijakoiset. Opiskelijoiden on ensinnäkin opittava ymmärtämään hajautettujen järjestelmien suunnittelun taustalla olevat periaatteet ja tekniikat, kuten lukitus, samanaikaisuus, välimuistitallennus, esihaku, aikataulutus ja viestintä verkon yli. Toiseksi opiskelijat saavat käytännön kokemusta todellisten hajautettujen järjestelmien suunnittelusta, toteutuksesta ja virheenkorjauksesta.

Tämän kurssin pääteemoja ovat muun muassa:

• Resurssien niukkuus, aikataulutus, ja samanaikaisuus
• Kommunikaation viive ja kaistanleveys
• Nimeäminen
• Abstraktio ja modulaarisuus
• Täydellinen kommunikaatio ja muuntyyppiset vikatilanteet
• Suojaaminen tahattomilta ja ilkivaltaisilta vahingoittumisilta
• Optimismi
• Konsensus
• Instrumentoinnin käyttö, seuranta- ja virheenkorjaustyökaluja ongelmanratkaisussa.
• Suunnittelu, toteutus ja virheenkorjaus merkittävissä ohjelmointiprojekteissa, jotka kattavat edellä mainitut teemat

Pisteytys

Kaikki kurssityöt tehdään yksilöllisesti. Tiimejä tai projektikumppaneita ei ole. Tämän kurssin henkilökohtaisessa tarjonnassa (ennen COVIDia ja toivottavasti myös sen jälkeen) arviointi perustui projekteihin (45 %), ongelmakokonaisuuksiin (20 %), välikokeeseen (15 %) ja loppukokeeseen (20 %). Kevään 2021 kurssitarjonnassa kokeet korvataan COVID-rajoitusten vuoksi kumulatiivisilla ongelmakokonaisuuksilla. Ne ovat kuin avoimen kirjan tentit, mutta ilman aikapaineita. Kuten nimikin kertoo, ne sisältävät kaiken siihen mennessä tunnilla käsitellyn materiaalin. Muita tehtäväkokonaisuuksia kutsutaan ajankohtaisiksi tehtäväkokonaisuuksiksi, koska niissä keskitytään aiheisiin. Kevään 2021 arviointi on siis seuraava (kaikki painotukset ovat likimääräisiä, 5 %:n vaihteluväli):

• 45 % neljästä projektista, tasapuolisesti painotettu
• 20 % neljästä ajankohtaisesta ongelmakokonaisuudesta, tasapuolisesti painotettu
• 15 % lukukauden puolivälissä olevasta kumulatiivisesta ongelmakokonaisuudesta
• 20 % lopullisesta kumulatiivisesta ongelmakokonaisuudesta.

Oppimistulokset

Odotamme opiskelijoiden saavan syvällisen ymmärryksen, sujuvan päättelykyvyn ja käytännön toteutustaidot seuraavista hajautettujen järjestelmien ydinkäsitteistä:

1. • Kommunikaatio ja etäproseduurikutsut
   • Valvontasemantiikka ja kielirajoitukset
   • Tarkasti vain kerran, enintään kerran, at-least-once
   • Serialisointi ja deserialisointi
   • End-to-end-argumentti ja sen soveltaminen todellisiin järjestelmiin
   • Integrointi säikeistykseen
   • Operaatioiden rinnakkaisuus
2. • Datan välimuistitallennus ja yksi- ja-copy semantiikka
   • Välimuistin johdonmukaisuusprotokollat ja toteutuksen kompromissit
   • Origins of temporaland spatial locality
   • Välimuistin laatumittarit
   • Sovelluskohtaiset johdonmukaisuusprotokollat
   • Prefetching:
3. • Häiriöt hajautetuissa järjestelmissä: alkuperä ja empiiriset tutkimukset
   • Fail fast and Byzantine failures
   • Fundamental limits of failure resilience
4. • Vikasietoisuuden perimmäiset rajat: Atomiset transaktiot; ACID-ominaisuus
   • Toteutuksen haasteet
   • Shadowing, intentiolistat ja write-ahead-loggaaminen
   • Fyysisen loggaamisen ja operaatioiden loggaamisen eroavaisuudet
   • Sisäkkäiset transaktiot
   • Hajautetut transaktiot
5. • konsensus ja lohkoketju:
   • Monimielisyys (johtajan valinta, Paxos)
   • Byzantine (single-shot ja Dolev-Strong)
   • State machine replication and Streamlet
   • Bitcoin

6. Yleisiä ohjelmointiparadigmoja, kuten Map-Reduce, MPI ja GraphLab

7. (Vain jos aika sallii):
   • Suuren saatavuuden saavuttaminen: äänestyspohjainen yhden kopion semantiikan säilyttäminen
   • Replikointistrategioiden taksonomia: Pessimistiset ja optimistiset lähestymistavat
   • Lue-kirjoita- ja kirjoita-kirjoita -konfliktit
   • Palvelin-client- ja peer-to-peer-strategiat
   • Välimuistitiedostojen tallentaminen (caching) ja irrotettu toiminta; konfliktien ratkaiseminen
   • Heikon kaistanleveyden hyödyntäminen käytettävyyden parantamiseksi

Kurssilogistiikka

Professorit

Opetusavustajat

Luennot

• Tiistaisin ja torstaisin klo 10:40-12:00
• Zoom-linkit ja videotallenteet: Canvas-sivulla tätä kurssia varten
• Ei opetusta: Tiistai 23.2. (taukopäivä), torstai 15.4. (kevätkarnevaalit)
• Viimeinen tunti: Torstai 6. toukokuuta

Kertaukset

• Aika: Keskiviikkoisin klo 19:00-19:50 (osasto A), 20:00-20:50 (osasto B)
• Zoom-linkit ja videotallenteet: Tämän kurssin Canvas-sivulla

Kurssin muistiinpanot

Sijoitetaan kurssin AFS-alueelle osoitteessa: /afs/andrew/course/15/440/classnotes jokaisen oppitunnin jälkeen.Nämä muistiinpanot on tarkoitettu vain henkilökohtaiseen käyttöön. Älkää jakako niitä.

Lukukirjat ja valinnaiset lukemistot

Pakollisia oppikirjoja ei ole. Seuraavassa on kolme hyvää valinnaislukemistoa:

• ”Distributed Systems: Principles and Paradigms”, Andrew S. Tanenbaum ja Maarten Van Steen, kolmas (2017) painos, Prentice Hall
• ”Guide to Reliable Distributed Systems”, Kenneth P. Birman, Springer
• Foundations of Distributed Consensus and Blockchains by Elaine Shi (2020, Kirjan käsikirjoitus)

Lisäksi tämän sivun ylälaidassa olevasta ”Readings”-linkistä löytyy joitakin erityisiä valinnaisia lukemistoja, jotka mainitsemme luentojen eri kohdissa. Näiden valinnaisten lukemistojen pdf-tiedostot löytyvät tältä kurssin verkkosivulta.

Kurssin käytännöt

Edellytykset

Koska tällä kurssilla on suuri projektikomponentti, sinun on hallittava C- ja Java-ohjelmointi UNIX-järjestelmissä. Kurssin 15-213 suorittamisen edellytyksenä on, että olet suorittanut kurssin 15-213 ja saanut vähintään arvosanan ”C”, koska monet tarvitsemistasi ohjelmointitaidoista opetetaan kyseisellä kurssilla. Jos olet saanut C:n kurssista 15-213, sinun on tavattava opinto-ohjaajasi kanssa keskustellaksesi taustastasi ennen kurssin 15-440 suorittamista ja mahdollisesti suoritettava lisäkurssi järjestelmätaitojesi terävöittämiseksi.

Policy on Academic Integrity

Tälle kurssille sovelletaan Carnegie Mellon Universityn politiikkaa akateemisesta rehellisyydestä. Kaikkien opiskelijoiden odotetaan tutustuvan huolellisesti tähän käytäntöön ja noudattavan sitä kaikilta osin tällä kurssilla.

Ohjeita yhteistyöstä:

• Opiskelijoita rohkaistaan keskustelemaan keskenään, opinto-ohjaajien kanssa, ohjaajien kanssa tai kenenkään muun kanssa mistä tahansa tehtävästä. Mahdollinen apu on kuitenkin rajoitettava keskusteluun ongelmasta ja yleisten ratkaisukeinojen hahmotteluun.
• Kunkin opiskelijan on kirjoitettava omat ratkaisunsa tehtäväkokonaisuuksiin. Kaikki tehtävät on tehtävä yksilöllisesti.
• Konsultointi toisen opiskelijan ratkaisusta on kielletty, eikä toimitettuja ratkaisuja saa kopioida mistään lähteestä. Nämä toimet ovat huijaamista.
• Jos sinulla on kysyttävää siitä, onko jokin toiminta huijaamista, kysy rohkeasti opettajilta.

Ohjeita jakamisesta: Et saa antaa kurssin 15-440 aikana tekemiäsi töitä muille opiskelijoille tämän kurssin myöhemmissä opintojaksoissa tai käytettäväksi tämän kurssin myöhemmissä opintojaksoissa (samoin kuin et saa käyttää kurssin aiemmin suorittaneiden opiskelijoiden tekemiä töitä).

Tallenteet

Kevätkaudella 2021 CMU:n tietotekniikkapalvelut nauhoittavat jokaisen luennon ja luentokertauksen Zoom-istunnot CMU:n tietotekniikkapalveluiden toimesta, ja ne tallennetaan tämän kurssin Canvas-sivulle. Kaikki muut nauhoitukset ovat kiellettyjä.

Taitotukihenkilöiden ajankäytön rajoitus

Ollaksemme reiluja kaikkia kohtaan, erityisesti silloin, kun on pitkä jono opiskelijoita odottamassa taitotukihenkilön huomiota, kaikille konsultaatioille asetetaan 10 minuutin rajoitus. Jos opiskelija ei ole valmis 10 minuutin kuluessa, hän palaa takaisin jonon päähän ennen kuin hän saa lisäaikaa TA:n kanssa. Ole valmistautunut ennen kuin tapaat opinto-ohjaajan. Jos tarvitset apua vian löytämisessä, rajoita ja yksinkertaista ongelmaa ennen tapaamista TA:n kanssa.

Piazza-käytännöt

Tällä kurssilla käytetään Piazza-sivustoa kysymyksiin vastaamiseen: tässä on tämän kurssin Piazza-sivu.

Ajattele, että piazza on kuin nostaisit käden ylös luokassa ja kysyisit kysymyksen. Mikään kysymys ei ole liian tyhmä kysyttäväksi, joten älä pelkää. Jokaista kysymyksen esittäjää kohden on luultavasti monia muita, joille sama kysymys on jo noussut tai nousee pian esiin. Vastaus kysymykseesi voi hyödyttää myös heitä. Lisäksi saattaa olla ihmisiä, joille kysymyksesi ei ole tullut mieleen. Kysymällä kysymyksen autat heitä näkemään hienovaraisuuden, jota he eivät ehkä ole aiemmin nähneet. Suoraan sähköpostiin ohjaajille ei vastata.

Odotamme aina, että käytät hyvää harkintakykyäsi Piazza-postauksissasi (kysymykset sekä vastaukset opiskelutovereiden kysymyksiin). Osa oppimisprosessia on kamppaileminen materiaalin kanssa, kunnes pääset oikeaan oivallukseen sen ymmärtämiseksi. Liian yksityiskohtainen postaus vastauksena avunpyyntöön voi haitata oppimista. Toisaalta joskus on hyvä, että sinua tuupataan oikeaan suuntaan, kun et pääse irti rutiineista. Ja tietysti väärinymmärryksiin tehtävästä tai käytettävissä olevista työkaluista on autettava nopeasti. Käytäthän parasta harkintakykyäsi kirjoittaessasi Piazza-sivustolle, aivan kuin tekisit yhteistyötä ystäviesi kanssa henkilökohtaisesti. Muutama karkea ohje:

Esimerkkejä hyvistä asioista, joita kannattaa postata ja joihin kannattaa vastata:

• Tehtävän väärinymmärrykset
• Tarkennuksia vaatimuksiin
• Virheitä tehtävän spekseissä tai referenssitoteutuksessa tai testeissä
• Pieniä, yksityiskohtaisia kysymyksiä systeemikutsujen, funktioiden yms. toiminnasta.
• Juttuja, jotka näyttävät siltä, että ne kuuluisivat tehtävän FAQ:iin

Esimerkkejä huonoista asioista, joita pitäisi kirjoittaa tai joihin pitäisi vastata:

• Enemmän kuin muutama rivi koodia
• Syvälliset selitykset siitä, miten järjestelmäsi toimii
• Kysymykset parhaasta lähestymistavasta järjestelmän arkkitehtuuriin korkealla tasolla
• Kysymykset arvosanastasi

Odotamme, että olet kohtuullisessa määrin pyrkinyt ajattelemaan itse, ennen kuin lähetät piazza-kysymyksen. Tämä pätee erityisesti koodisi debuggaamiseen. Oletko kokeillut man-sivuja? Teitkö Google-haun mahdollisesti asiaankuuluvien resurssien löytämiseksi? Katsoitko aiempia kysymyksiä, joita ihmiset ovat jo esittäneet, ja niihin annettuja vastauksia? Lisäsitkö printf:iä ja yrititkö ymmärtää, mitä koodissasi tapahtuu?

Älä käytä autolabia virheenkorjaustyökaluna. Odotamme, että olet nähnyt kohtuullisesti vaivaa saadaksesi koodisi debuggattua ennen kuin lähetät sen autolabiin. Testitapausten luominen ja koodisi stressitestaus on osa sitä, mistä projektissa on kyse. Ilman näitä ponnisteluja menetät tärkeän osan kurssin oppimismahdollisuuksista. Autolabiin lähettämisen pitäisi olla viimeinen vaihe prosessissa, jossa olet testannut, debugannut ja parantanut koodiasi niin pitkälle kuin pystyt. Autolab-dumppien lähettäminen piazza-postissa ja sanomalla ”please help” on räikeä piazza-etikettien rikkominen.

Privaatit postit piazzassa eivät ole tuettuja. Tämä on tätä luokkaa koskeva poliittinen päätös. Muista, että piazzalla kirjoittaminen on samanlaista kuin käden nostaminen ja kysyminen. Muut opiskelijat hyötyvät siitä, että kysyt kysymyksen ja näet opettajan vastauksen. Voit halutessasi jättää viestisi nimettömänä muiden opiskelijoiden nähtäväksi. Tämä on jo enemmän yksityisyyden suojaa kuin se, mikä on mahdollista, kun kysyt kysymyksen luokassa. Niitä todella harvinaisia tapauksia varten, joissa sinun on esitettävä yksityinen pyyntö, joka ei liity kurssin sisältöön, on luotu erityinen yksityinen sähköpostilista.

Pyyntöjä varten, jotka on todella pidettävä yksityisinä, lähetä sähköpostia osoitteeseen[email protected], niin joku opettajista vastaa. Tälle listalle lähetetyt sähköpostiviestit, jotka liittyvät kurssin sisältöön (esim. selvennykset kurssimateriaaliin), jätetään huomiotta; sinun tulisi lähettää tällaiset kysymykset Piazza-palveluun.

Policy on Late Submissions

For projects:

• Kullakin opiskelijalla on viisi myöhästymispäivää käytettävissään koko lukukauden ajan. Nämä myöhästymispäivät on tarkoitettu lomien, matkojen, haastattelujen, flunssan ja muiden vastaavien tilanteiden huomioon ottamiseen. Voit käyttää niitä vapaasti mihin tahansa syyhyn kysymättä lupaa ohjaajilta. Voit käyttää enintään kahta myöhästymispäivää tiettynä eräpäivänä (eli jos projektissa on useita tarkistuspisteitä, voit käyttää enintään kahta myöhästymispäivää kutakin tarkistuspistettä kohti). Myöhästymispäiviä käytetään automaattisesti aikajärjestyksessä, joten et voi lykätä myöhästymispäivän käyttöä korkeamman painoarvon omaavaan tulevaan tehtävään.

• Yksi myöhästymispäivä = (0,24] tuntia myöhässä eräpäivästä; kaksi myöhästymispäivää = (24, 48] tuntia myöhässä eräpäivästä; jne.

• Jos käytät kaikki myöhästymispäivät, voit lähettää myöhästymispäiviä 15 %:lla rangaistuksella per päivä, enintään kahden päivän ajan. Toisin sanoen, jos olet käyttänyt kaikki myöhästymispäiviäsi, voit silti jättää kaksi seuraavaa päivää, jolloin saat 15 %:n sakon jokaiselta näistä päivistä (vapaapäivät).

• Et voi yhdistää myöhästymispäiviä ja vapaapäiviä antaaksesi yli kaksi päivää myöhässä.

Tehtäväsarjoja varten: Myöhästyneitä lähetyksiä ei hyväksytä, ei rangaistuksella eikä ilman. Varmista, että lähetät sen ajoissa.

Projektien tyyliopas

Koodisi toimivuuden testaamisen lisäksi varaamme osan kunkin projektin pisteistä myös sen tyylistä ja luettavuudesta. Tärkeintä on yhtenäinen ja luettava tyyli. Haluamme lähinnä nähdä, että olet valinnut tyylin, joka on luettava ja järkevä, ja että käytät samaa tyyliä johdonmukaisesti koko projektin ajan.Käytä tervettä järkeä: älä käytä 500-merkkisiä koodirivejä, älä nimeä muuttujia foo (paitsi jos se on järkevää asiayhteydessään), ja vältä sekoittamasta case-käytäntöjä sattumanvaraisesti.

Etsimme seuraavia asioita:

Dokumentaatio Hyvä dokumentaatio on tärkeää: itsellesi tulevaisuudessa, muille koodin ylläpitäjille ja tässä yhteydessä myös graduntekijöille, jotka tarkastelevat koodiasi. Älä koe tarvetta dokumentoida jokaista koodiriviä (koska hyvän koodin pitäisi tavallaan olla myös itsestään dokumentoituvaa), mutta yleensä on hyvä tuoda esiin kunkin funktion yleinen käyttö ja tarkoitus sekä suuret tai monimutkaiset koodilohkot. Hyvänä käytäntönä on myös sisällyttää jokaiseen tiedostoon otsikko, jossa kerrotaan yksityiskohtaisesti, miten kyseinen tiedosto sopii koko projektin rakenteeseen. Valkoinen tila Ole johdonmukainen. Älä käytä tabulaattoria 2 välilyöntiä joissakin paikoissa ja 4 välilyöntiä toisissa paikoissa. Ole järkevä ja käytä välilyöntejä, jotta koodisi on luettavissa. Rivin pituus Suhtaudumme kohtuullisesti rivien pituuteen, kunhan olet johdonmukainen ja rivien rajat ovat kohtuulliset (500 merkkiä ei ole… 80 tai 120 merkkiä on yleisesti käytetty ja hyväksytty). Muuttujien nimet Muuttujien nimien tulisi antaa selkeä osoitus siitä, mitä muuttujat edustavat, tai niiden käyttötapauksesta. Kuollut/testikoodi Yritä olla lähettämättä koodia, joka on täynnä debug-tulostuslauseita tai suuria kommentoituja koodinpätkiä. Ne heikentävät luettavuutta ja vievät huomion siitä koodista, joka todella toimii tuotannossa. Suunnittelu Yritä suunnitella koodisi ja projektisi siten, että ne ovat kohtuullisen modulaarisia. 5000-riviset funktiot ovat yleensä merkki huonosta suunnittelusta ja aiheuttavat myöhemmin päänvaivaa.

Tässä on Googlen tyyliopas, josta voi olla apua.

Hyvinvointi

Tässä on vinkkejä hyvinvointiin.