Sistemi distribuiti

Primavera 2021

Panoramica

15-440 è un corso introduttivo ai sistemi distribuiti. L’enfasi sarà posta sulle tecniche per creare sistemi distribuiti funzionali, usabili e scalabili. Per rendere le questioni più concrete, la classe include diversi progetti di più settimane che richiedono una significativa progettazione e implementazione

Gli obiettivi di questo corso sono due. In primo luogo, gli studenti devono acquisire una comprensione dei principi e delle tecniche che stanno alla base della progettazione dei sistemi distribuiti, come il locking, la concorrenza, il caching, il prefetching, lo scheduling e la comunicazione attraverso la rete. In secondo luogo, per gli studenti di acquisire esperienza pratica nella progettazione, implementazione e debugging di sistemi distribuiti reali.

I temi principali di questo corso includono:

• Scarsità di risorse, programmazione, e concorrenza
• Latenza di comunicazione e larghezza di banda
• Nominazione
• Astrazione e modularità
• Comunicazione imperfetta e altri tipi di fallimento
• Protezione da danni accidentali e dolosi
• Optimismo
• Consenso
• Uso di strumentazione, strumenti di monitoraggio e debug nella risoluzione dei problemi.
• Progettazione, implementazione e debugging di progetti di programmazione sostanziali che abbracciano i temi di cui sopra

Grading

Tutto il lavoro del corso è fatto individualmente. Non ci sono squadre o partner di progetto. Per le offerte in presenza di questo corso (pre-COVID e, si spera, post-COVID) la valutazione era basata su progetti (45%), serie di problemi (20%), esame intermedio (15%), ed esame finale (20%). Per l’offerta della primavera 2021 del corso, a causa dei vincoli COVID, gli esami sono sostituiti da serie di problemi cumulativi. Questi sono come esami a libro aperto, ma senza la pressione del tempo. Come suggerisce il nome, includono tutto il materiale trattato in classe fino a quel momento. Ci riferiamo agli altri set di problemi come set di problemi topici poiché si concentrano su argomenti. Quindi la valutazione della primavera 2021 sarà la seguente (tutti i pesi sono approssimativi, entro un intervallo del 5%):

• 45% per 4 progetti, ugualmente ponderati
• 20% per 4 serie di problemi topici, ugualmente ponderati
• 15% per la serie di problemi cumulativa di metà semestre
• 20% per la serie di problemi cumulativa finale.

Risultati dell’apprendimento

Ci aspettiamo che gli studenti acquisiscano una profonda comprensione, scioltezza nel ragionamento e capacità di implementazione pratica dei seguenti concetti fondamentali dei sistemi distribuiti:

1. • Comunicazione e chiamata di procedura remota
   • Semantica del controllo e limiti del linguaggio
   • Esattamente una volta, al massimo una volta, at-least-once
   • Serializzazione e de-serializzazione
   • Argomento end-to-end e sua applicazione a sistemi reali
   • Integrazione con il threading
   • Concorrenza delle operazioni
2. • Caching dei dati e semantica one-copia
   • Protocolli di coerenza della cache e compromessi di implementazione
   • Indicazioni della localizzazione temporale e spaziale
   • Metriche di qualità della cache
   • Protocolli di coerenza specifici per le applicazioni
   • Prefetching: benefici e rischi
   • Estrazione di suggerimenti
   • Buffer bloat
3. • Fallimenti nei sistemi distribuiti: origini e studi empirici
   • Fallimenti veloci e bizantini
   • Limiti fondamentali della resilienza ai fallimenti
4. • Tolleranza ai fallimenti: transazioni atomiche; proprietà ACID
   • Sfide implementative
   • Shadowing, liste di intenzioni e write-ahead logging
   • Tradeoffs in physical logging e operation logging
   • Transazioni annidate
   • Transazioni distribuite
5. • Consenso e blockchain: unanimità (commit a due fasi)
   • Maggioranza (elezione del leader, Paxos)
   • Bizantina (single-shot e Dolev-Strong)
   • Replicazione della macchina di stato e Streamlet
   • Bitcoin

6. Paradigmi di programmazione comuni come Map-Reduce, MPI e GraphLab

7. (Solo se il tempo lo permette):
   • Raggiungere l’alta disponibilità: conservazione basata sul voto della semantica di una copia
   • Tassonomia delle strategie di replica: approcci pessimistici e ottimistici
   • Conflitti di lettura-scrittura e scrittura-scrittura
   • Strategie server-client e peer-to-peer
   • Caching e funzionamento disconnesso; risolvere i conflitti
   • Sfruttare la bassa larghezza di banda per migliorare la disponibilità

Logistica dei corsi

Professori

Nome	Ore di ufficio	Ufficio	Telefono	Andrew email
Mahadev Satyanarayanan (Satya)	Tue 1:00 – 3:00 pm	GHC-9123	x8-3743	satya
Padmanabhan Pillai (Babu)	Wed 11:00 am – 1:00 pm	GHC-9232		pspillai
Runting Shi (Elaine)	Mon 4:00 – 6:00 pm	CIC-2217		Contatto tramite Canvas

Assistenti all’insegnamento

Nome	Ore di ufficio	Andrew email
Nathan Ang	Thu 2:00-4:00 pm	nathanan
Junwon Chang (Joseph)	Sab 9:00-11:00	junwonc
Wenxin Ding (Freda)	Venerdì 10:00-12:00	wenxind
Timothy Ganger	Sab 4:00-6:00 pm	tganger
Ziying He	Fri 5:00-7:00 pm	ziyingh
Roger Iyengar	Wed 1:00-3:00 pm	raiyenga
Ishaan Jaffer	Tu 4:00-6:00 pm	ijaffer
Ibnul Jahan	Tue 4:00-18:00 pm	iej
Chen Jin (Crystal)	Fri 8:00-10:00	chenj
Yajin Li	Mon 10:00-12:00 pm	yajinl
Diego San Miguel	Venerdì 14:00-16:00 pm	dsanmigu
Riccardo Santoni	Mon 8:00-10:00 pm	rsantoni
Yiwen Song (Victor)	Tu 9:00-11:00 pm	yiwenson
Haithem Turki	Wed 3:00-5:00 pm	hturki
Clarissa Xu	Tue 6:30-8:30 pm	csxu

Lezioni

• Martedì e giovedì, dalle 10:40 alle 12:00
• Link zoom e registrazioni video: Sulla pagina Canvas di questo corso
• Nessuna lezione: Martedì 23 febbraio (giorno di riposo), giovedì 15 aprile (carnevale di primavera)
• ultima lezione: Giovedì 6 maggio

Recitazioni

• Orario: mercoledì 19:00 – 19:50 (sezione A), 20:00 – 20:50 (sezione B)
• Link zoom e registrazioni video: Sulla pagina Canvas di questo corso

Appunti del corso

Saranno inseriti nell’area AFS del corso a: /afs/andrew/course/15/440/classnotes dopo ogni lezione. Queste note sono solo per uso personale. Si prega di non distribuirli.

Libri di testo e letture opzionali

Non ci sono libri di testo obbligatori. Qui ci sono tre buoni riferimenti da usare come letture opzionali:

• “Sistemi distribuiti: Principles and Paradigms” di Andrew S. Tanenbaum e Maarten Van Steen, terza edizione (2017), Prentice Hall
• “Guide to Reliable Distributed Systems” di Kenneth P. Birman, Springer
• Foundations of Distributed Consensus and Blockchains di Elaine Shi (2020, Book manuscript)

Inoltre, il link “Readings” in cima a questa pagina web ha alcune letture opzionali specifiche che menzioneremo in diversi punti delle lezioni. I pdf di queste letture opzionali sono disponibili sul sito web del corso.

Politiche del corso

Prequisiti

Perché questo corso ha una grande componente di progetto, è necessario essere abili nella programmazione C e Java su sistemi UNIX. È richiesto che tu abbia preso 15-213 e ottenuto una “C” o superiore, poiché molte delle abilità di programmazione di cui avrai bisogno sono insegnate in quel corso. Se hai ricevuto una C nel 15-213, devi incontrare il tuo consulente accademico per discutere il tuo background prima di frequentare il 15-440, magari frequentando un corso aggiuntivo per affinare le tue abilità nei sistemi.

Policy on Academic Integrity

La Carnegie Mellon University Policy on Academic Integrity si applica a questo corso. Tutti gli studenti sono tenuti a rivedere attentamente questa politica e ad aderirvi per tutti gli aspetti di questo corso.

Guida sulla collaborazione:

• Gli studenti sono incoraggiati a parlare tra loro, con gli assistenti, con gli istruttori, o con chiunque altro di qualsiasi compito. Qualsiasi assistenza, tuttavia, deve essere limitata alla discussione del problema e all’abbozzo di approcci generali ad una soluzione.
• Ogni studente deve scrivere le proprie soluzioni ai gruppi di problemi. Tutti i progetti devono essere fatti individualmente.
• Consultare la soluzione di un altro studente è proibito, e le soluzioni presentate non possono essere copiate da nessuna fonte. Queste azioni costituiscono un imbroglio.
• Se avete qualche domanda sul fatto che qualche attività possa costituire un imbroglio, non esitate a chiedere agli istruttori.

Guida sulla condivisione: Non potete fornire il lavoro che completate durante il 15-440 ad altri studenti in istanze future di questo corso o per usarlo in istanze future di questo corso (così come non potete usare il lavoro completato da studenti che hanno seguito il corso in precedenza).

Registrazioni

Per la primavera 2021, le sessioni Zoom di ogni lezione e recita saranno registrate dal CMU Computing Services e pubblicate sulla pagina Canvas di questo corso. Tutte le altre registrazioni sono proibite.

Limite sull’uso del tempo dell’assistente

Per essere giusti con tutti, specialmente quando c’è una lunga fila di studenti in attesa dell’attenzione dell’assistente, ci sarà un limite di 10 minuti per tutte le consultazioni. Se uno studente non ha finito alla fine dei 10 minuti, torna alla fine della fila prima di ottenere altro tempo con l’assistente. Sii preparato prima di incontrare un assistente tecnico. Se hai bisogno di aiuto per trovare un bug, restringi e semplifica il problema prima di incontrare l’assistente.

Politica di Piazza

Questo corso usa il sito di Piazza per rispondere alle domande: ecco la pagina di Piazza per questo corso.

Pensa a Piazza come alzare la mano in classe e fare una domanda. Nessuna domanda è troppo stupida da fare, quindi non abbiate paura. Per ogni persona che fa una domanda, ci sono probabilmente molti altri a cui la stessa domanda è già sorta o sorgerà presto. La risposta alla tua domanda potrebbe essere utile anche a loro. Inoltre, ci possono essere alcune persone a cui la vostra domanda non è stata posta. Ponendo la domanda, li aiuti a vedere una sottigliezza che potrebbero non aver visto prima. Le e-mail dirette agli istruttori non riceveranno risposta.

In ogni momento, ci aspettiamo che tu usi il tuo buon giudizio nei tuoi post su Piazza (domande e risposte alle domande dei compagni). Parte del processo di apprendimento è lottare con il materiale finché non si arriva alla giusta comprensione. Postare troppi dettagli in risposta ad una richiesta di assistenza può compromettere l’apprendimento. D’altra parte, a volte è bello essere spinti nella giusta direzione quando non si è in grado di uscire da una routine. E, naturalmente, le incomprensioni del compito o degli strumenti disponibili dovrebbero essere aiutati rapidamente. Per favore usa il tuo miglior giudizio quando scrivi sul sito di Piazza, come se stessi collaborando con i tuoi amici di persona. Alcune linee guida approssimative:

Esempi di cose buone da postare e a cui rispondere:

• Misunderstanding del compito
• Chiarimenti sui requisiti
• Bugs nelle specifiche del compito o nell’implementazione di riferimento o nei test
• Piccole, dettagliate domande sul funzionamento delle chiamate di sistema, funzioni, ecc.
• Cose che sembrano andare in una FAQ per il compito

Esempi di cose brutte da postare o a cui rispondere:

• Più di qualche riga di codice
• Spiegazioni approfondite su come funziona il tuo sistema
• Domande sul miglior approccio per architettare il sistema ad alto livello
• Domande sul tuo voto

Ci aspettiamo che tu abbia fatto uno sforzo ragionevole per pensare da solo prima di postare una domanda su piazza. Questo è particolarmente vero per quanto riguarda il debug del tuo codice. Hai provato le pagine man? Hai fatto una ricerca su Google per risorse possibilmente rilevanti? Hai guardato le domande precedenti che le persone hanno già posto, e le risposte fornite? Hai inserito le printf e cercato di capire cosa sta succedendo nel tuo codice?

Non usare autolab come strumento di debug. Ci aspettiamo che tu abbia fatto uno sforzo ragionevole per fare il debug del tuo codice prima di inviarlo ad autolab. Creare casi di test e stressare il vostro codice è parte di ciò che è un progetto. Senza fare questo sforzo, state perdendo una parte importante dell’opportunità di apprendimento del corso. L’invio all’autolab dovrebbe essere l’ultimo passo di un processo in cui avete testato, debuggato e migliorato il vostro codice al massimo delle vostre capacità. Inviare un dump di autolab in un post su Piazza e dire “per favore aiutatemi” è un’egregia violazione del galateo di Piazza.

I post privati su Piazza non sono supportati. Questa è una decisione politica per questa classe. Ricordate, postare su Piazza è simile ad alzare la mano e fare una domanda. Gli altri studenti beneficiano della tua domanda e vedono la risposta dell’istruttore. Permettiamo che i tuoi post siano anonimi per gli altri studenti, se lo scegli. Questo è già un grado di privacy superiore a quello che è possibile quando si fa una domanda in classe. Per le rarissime occasioni in cui hai bisogno di fare una richiesta privata che non è legata al contenuto del corso, è stata creata una speciale mailing list privata.

Per richieste che hanno veramente bisogno di essere private Invia un’email a[email protected]e uno degli istruttori ti risponderà. Le e-mail a questa lista che riguardano il contenuto del corso (per esempio, chiarimenti sul materiale del corso) saranno ignorate; tali domande dovrebbero essere poste su Piazza.

Policy on Late Submissions

Per i progetti:

• Ogni studente avrà cinque giorni di ritardo da utilizzare durante il semestre. Questi giorni di ritardo sono destinati a tenere conto di vacanze, viaggi, interviste, un raffreddore e altre situazioni simili. Siete liberi di usarli per qualsiasi motivo, senza chiedere il permesso agli istruttori. Puoi usare al massimo due giorni di ritardo per ogni data di scadenza (cioè, per progetti con più punti di controllo, puoi usare fino a due giorni di ritardo per ogni punto di controllo). I giorni di ritardo saranno automaticamente applicati in ordine cronologico, quindi non puoi scegliere di rinviare l’uso di un giorno di ritardo per un incarico futuro di peso maggiore.

• Un giorno di ritardo = (0,24] ore dopo la data di scadenza; due giorni di ritardo = (24, 48] ore dopo la data di scadenza; ecc.

• Se usi tutti i tuoi giorni di ritardo, puoi inviare in ritardo con una penalità del 15% al giorno, fino a due giorni. In altre parole, se hai usato tutti i tuoi giorni di ritardo, puoi ancora presentare per i prossimi due giorni, incorrendo in una penalità del 15% per ciascuno di quei giorni (giorni di grazia).

• Non puoi combinare i giorni di ritardo e i giorni di grazia per presentare più di due giorni di ritardo.

Per le serie di problemi: Non si accettano invii in ritardo, con o senza penalità. Assicurati di presentare in tempo.

Guida allo stile per i progetti

Oltre a testare la funzionalità del tuo codice, riserveremo anche una parte dei punti di ogni progetto per il suo stile e leggibilità. La cosa più importante è uno stile coerente e leggibile. Cerchiamo soprattutto di vedere che avete scelto uno stile che sia leggibile e ragionevole, e che usate lo stesso stile in modo coerente in tutto il progetto.Usate il buon senso: non avete linee di codice di 500 caratteri, non chiamate le vostre variabili foo (a meno che non abbiano senso nel loro contesto), ed evitate di mescolare le convenzioni sui casi a caso.

Cercheremo le seguenti cose:

Documentazione Una buona documentazione è importante: per voi stessi in futuro, per gli altri manutentori del codice, e in questo contesto, per i classificatori che guarderanno il vostro codice. Non sentite il bisogno di documentare ogni linea di codice (poiché un buon codice dovrebbe anche essere auto-documentante in un certo senso), ma di solito è bene evidenziare l’uso generale e lo scopo di ogni funzione, così come i grandi o complessi blocchi di codice. E’ anche buona pratica includere un’intestazione in ogni file, dettagliando come quel file si inserisce nella struttura del progetto nel suo complesso. Spazio bianco Si prega di essere coerenti. Per favore non usate tab 2 spazi in alcuni punti e 4 in altri. Sii ragionevole e usa lo spazio bianco per assicurare che il tuo codice sia leggibile. Lunghezza delle linee Saremo ragionevoli sulla lunghezza delle linee, a patto che siate coerenti e che i vostri limiti di linea siano ragionevoli (500 caratteri non lo sono… 80 o 120 caratteri sono comunemente usati e accettati). Nomi delle variabili I vostri nomi delle variabili dovrebbero dare una chiara indicazione di ciò che rappresentano o del loro caso d’uso. Codice morto/di test Cercate di non presentare codice che sia disseminato di istruzioni di stampa di debug o grandi pezzi di codice commentato. Questo diminuisce la leggibilità e distrae dal codice che verrà effettivamente eseguito in produzione. Design Cercate di progettare il vostro codice e i vostri progetti in modo che siano ragionevolmente modulari. Le funzioni di 5000 linee sono generalmente un segno di cattiva progettazione e vi daranno mal di testa in seguito.

Qui c’è una guida di stile di Google che può essere utile.

Benessere

Qui ci sono alcuni consigli per il benessere.