Systèmes distribués

Printemps 2021

Overview

15-440 est un cours d’introduction aux systèmes distribués. L’accent sera mis sur les techniques de création de systèmes distribués fonctionnels, utilisables et évolutifs. Pour rendre les questions plus concrètes, la classe comprend plusieurs projets de plusieurs semaines nécessitant une conception et une mise en œuvre importantes

Les objectifs de ce cours sont doubles. Premièrement, pour les étudiants d’acquérir une compréhension des principes et des techniques derrière la conception de systèmes distribués, tels que le verrouillage, la concurrence, la mise en cache, la préextraction, l’ordonnancement et la communication à travers le réseau. Deuxièmement, pour les étudiants d’acquérir une expérience pratique de conception, de mise en œuvre et de débogage de systèmes distribués réels.

Les principaux thèmes que ce cours enseignera comprennent :

• La rareté des ressources, l’ordonnancement, et la concurrence
• Latence de communication et largeur de bande
• Nomination
• Abstraction et modularité
• Communication imparfaite et autres types de défaillance
• Protection contre les dommages accidentels et malveillants
• Optimisme
• Consensus
• Utilisation de l’instrumentation, de surveillance, et d’outils de débogage dans la résolution de problèmes.
• Conception, mise en œuvre et débogage de projets de programmation substantiels qui couvrent les thèmes ci-dessus

Notation

Tous les travaux de cours sont effectués individuellement. Il n’y a pas d’équipes ou de partenaires de projet. Pour les offres en personne de ce cours (avant COVID et, espérons-le, après COVID), l’évaluation était basée sur les projets (45%), les ensembles de problèmes (20%), l’examen de mi-session (15%) et l’examen final (20%). Pour l’offre du cours du printemps 2021, en raison des contraintes du COVID, les examens sont remplacés par des ensembles de problèmes cumulatifs. Ces derniers sont comme des examens à livre ouvert, mais sans la pression du temps. Comme leur nom l’indique, ils comprennent tout le matériel couvert en classe jusqu’à ce moment-là. Nous appelons les autres séries de problèmes des séries de problèmes topiques puisqu’elles se concentrent sur des sujets. Ainsi, l’évaluation du printemps 2021 sera la suivante (toutes les pondérations sont approximatives, dans une fourchette de 5%):

• 45% pour 4 projets, pondération égale
• 20% pour 4 ensembles de problèmes topiques, pondération égale
• 15% pour l’ensemble de problèmes cumulatifs du milieu du semestre
• 20% pour l’ensemble de problèmes cumulatifs final.

Résultats d’apprentissage

Nous attendons des étudiants qu’ils acquièrent une compréhension approfondie, une aisance dans le raisonnement et des compétences pratiques de mise en œuvre des concepts de systèmes fondamentaux suivants dans les systèmes distribués :

1. • Communication et appel de procédure à distance
   • Sémantique de contrôle et limitations de langage
   • Exactly-once, at-most-once, au moins une fois
   • Sérialisation et dé-sérialisation
   • Argument de bout en bout et son application aux systèmes réels
   • Intégration avec le threading
   • Concurrence des opérations
2. • Mise en cache des données et sémantique de la copie unique
   • .copie
   • Protocoles de cohérence de cache et compromis d’implémentation
   • Origines de la localité temporelle et spatiale
   • Métriques de qualité de cache
   • Protocoles de cohérence spécifiques aux applications
   • Prefetching : avantages et risques
   • Extraction d’indices
   • Buffer bloat
3. • Défaillances dans les systèmes distribués : origines et études empiriques
   • Défaillances rapides et byzantines
   • Limites fondamentales de la résilience aux défaillances
4. • Tolérance aux défaillances : Transactions atomiques ; propriété ACID
   • Défis de mise en œuvre
   • L’ombre, les listes d’intentions et la journalisation write-ahead
   • Tradeoffs dans la journalisation physique et la journalisation des opérations
   • Transactions imbriquées
   • Transactions distribuées
5. • Consensus et blockchain : unanimité (commit à deux phases)
   • Majorité (élection du leader, Paxos)
   • Byzantine (single-shot et Dolev-Strong)
   • Réplication de machine d’état et Streamlet
   • Bitcoin

6. Paradigmes de programmation communs tels que Map-Reduce, MPI et GraphLab

7. (Seulement si le temps le permet) :
   • Achèvement de la haute disponibilité : préservation basée sur le vote de la sémantique d’une copie
   • Taxonomie des stratégies de réplication : Approches pessimistes et optimistes
   • Conflits de lecture-écriture et d’écriture-écriture
   • Stratégies serveur-client et pair-à-pair
   • Mise en cache et fonctionnement déconnecté ; Résolution des conflits
   • Exploitation de la faible bande passante pour améliorer la disponibilité

Logistique des cours

Professeurs

.

Nom	Heures de bureau	Bureau	Téléphone	Andrew email
Mahadev Satyanarayanan (Satya)	Tue 1 :00 – 15:00 pm	GHC-9123	x8-3743	satya
Padmanabhan Pillai (Babu)	Mercredi 11 :00 h – 13 h	GHC-9232		pspillai
Runting Shi (Elaine)	Mon 16 h – 18 :00 pm	CIC-2217		Contact via Canvas

Assistants d’enseignement

Nom	Heures de bureau	Andrew email
Nathan Ang	Thu 2 :00-16:00 pm	nathanan
Junwon Chang (Joseph)	Sam 9 :00-11h00	junwonc
Wenxin Ding (Freda)	Fri 10:00-12:00	wenxind
Timothy Ganger	Sam 4 :00-18h00	tganger
Ziying He	Ven 5:00-19:00	ziyingh
Roger Iyengar	Merc 1 :00-15h00	raiyenga
Ishaan Jaffer	Jeu 4:00-6:00	ijaffer
Ibnul Jahan	Mar 4 :00-18h00	iej
Chen Jin (Crystal)	Ven 8:00-10:00	chenj
Yajin Li	Mon 10 :00-12:00	yajinl
Diego San Miguel	Ven 14:00-4:00	dsanmigu
Riccardo Santoni	Mon 8 :00-10:00	rsantoni
Yiwen Song (Victor)	Jeu 9:00-11 :00	yiwenson
Haithem Turki	Mercredi 15h-17h	hturki
Clarissa Xu	Mardi 18h30-20h :30 pm	csxu

Lectures

• Mardi et jeudi, 10:40 am – 12:00 noon
• Liens zoom et enregistrements vidéo : Sur la page Canvas de ce cours
• Pas de cours : Mardi 23 février (jour de relâche), jeudi 15 avril (Carnaval de printemps)
• Dernier cours : Jeudi 6 mai

Récitations

• Horaire : mercredis de 19h00 à 19h50 (section A), de 20h00 à 20h50 (section B)
• Liens zoom et enregistrements vidéo : Sur la page Canvas de ce cours

Notes de cours

Sera placé dans la zone AFS du cours à : /afs/andrew/course/15/440/classnotes après chaque cours.Ces notes sont destinées à votre usage personnel uniquement. Veuillez ne pas les distribuer.

Les manuels et les lectures facultatives

Il n’y a pas de manuels obligatoires. Voici trois bonnes références à utiliser pour les lectures facultatives:

• « Distributed Systems : Principles and Paradigms » par Andrew S. Tanenbaum et Maarten Van Steen, troisième édition (2017), Prentice Hall
• « Guide to Reliable Distributed Systems » par Kenneth P. Birman, Springer
• Fondations du consensus distribué et des blockchains par Elaine Shi (2020, manuscrit du livre)

En outre, le lien « Lectures » en haut de cette page web a quelques lectures optionnelles spécifiques que nous mentionnerons à différents moments dans les conférences. Les pdf de ces lectures optionnelles sont disponibles sur le site web de ce cours.

Politiques du cours

Prérequis

Comme ce cours a une grande composante de projet, vous devez être compétent en programmation C et Java sur les systèmes UNIX. Il est nécessaire que vous ayez suivi le cours 15-213 et que vous ayez obtenu un « C » ou plus, puisque plusieurs des compétences en programmation dont vous aurez besoin sont enseignées dans ce cours. Si vous avez obtenu un C dans le 15-213, vous devez rencontrer votre conseiller pédagogique pour discuter de votre parcours avant de prendre le 15-440, en prenant peut-être un cours supplémentaire pour affiner vos compétences en matière de systèmes.

Politique d’intégrité académique

La politique d’intégrité académique de l’Université Carnegie Mellon s’applique à ce cours. Tous les étudiants sont tenus d’examiner attentivement cette politique et d’y adhérer pour tous les aspects de ce cours.

Guidance sur la collaboration:

• Les étudiants sont encouragés à parler entre eux, aux TA, aux instructeurs ou à toute autre personne au sujet de l’un des devoirs. Toute aide, cependant, doit être limitée à la discussion du problème et à l’esquisse d’approches générales pour une solution.
• Chaque étudiant doit écrire ses propres solutions aux ensembles de problèmes. Tous les projets doivent être faits individuellement.
• Consulter la solution d’un autre étudiant est interdit, et les solutions soumises ne peuvent être copiées d’aucune source. Ces actions constituent une tricherie.
• Si vous avez des questions pour savoir si une activité constitue une tricherie, n’hésitez pas à demander aux instructeurs.

Conseils sur le partage : Vous ne pouvez pas fournir le travail que vous complétez pendant 15-440 à d’autres étudiants dans des instances futures de ce cours ou pour une utilisation dans des instances futures de ce cours (tout comme vous ne pouvez pas utiliser le travail complété par des étudiants qui ont suivi le cours précédemment).

Enregistrements

Pour le printemps 2021, les sessions Zoom de chaque conférence et récitation seront enregistrées par les services informatiques de la CMU et affichées sur la page Canvas de ce cours. Tous les autres enregistrements sont interdits.

Limite de l’utilisation du temps de l’AT

Pour être juste envers tout le monde, surtout lorsqu’il y a une longue file d’étudiants qui attendent l’attention d’un AT, il y aura une limite de 10 minutes sur toutes les consultations. Si un étudiant n’a pas terminé au bout de 10 minutes, il retourne au bout de la file avant d’obtenir plus de temps avec le TA. Soyez préparé avant de rencontrer un TA. Si vous avez besoin d’aide pour trouver un bogue, réduisez et simplifiez le problème avant de rencontrer le TA.

Politique Piazza

Ce cours utilise le site web Piazza pour répondre aux questions : voici la page Piazza pour ce cours.

Pensez à piazza comme lever votre main en classe et poser une question. Aucune question n’est trop stupide pour être posée, alors n’ayez pas peur. Pour chaque personne qui pose une question, il y en a probablement beaucoup d’autres à qui la même question s’est déjà posée ou se posera bientôt. La réponse à votre question peut leur être utile à eux aussi. En outre, il y a peut-être des personnes à qui votre question ne s’est pas posée. En posant la question, vous les aidez à voir une subtilité qu’ils n’avaient peut-être pas vue auparavant. Les courriels adressés directement aux instructeurs ne recevront pas de réponse.

En tout temps, nous nous attendons à ce que vous utilisiez votre bon jugement dans vos messages sur Piazza (questions ainsi que réponses aux questions des autres étudiants). Une partie du processus d’apprentissage consiste à se débattre avec la matière jusqu’à ce que vous arriviez au bon aperçu pour la comprendre. Publier trop de détails en réponse à une demande d’aide peut nuire à l’apprentissage. D’un autre côté, il est parfois agréable de recevoir un coup de pouce dans la bonne direction lorsque l’on ne parvient pas à sortir d’une ornière. Et, bien sûr, les malentendus concernant le travail ou les outils disponibles doivent être résolus rapidement. Veuillez faire preuve de discernement lorsque vous postez des messages sur le site Piazza, comme si vous collaboriez avec vos amis en personne. Quelques lignes directrices approximatives :

Exemples de bonnes choses à poster et à répondre :

• Mauvaise compréhension du devoir
• Clarifications sur les exigences
• Bugs dans la spécification du devoir ou l’implémentation de référence ou les tests
• Petites questions détaillées sur le fonctionnement des appels système, des fonctions, etc.
• Des choses qui semblent aller dans une FAQ pour l’affectation

Des exemples de mauvaises choses à poster ou à répondre :

• Plus que quelques lignes de code
• Des explications approfondies sur le fonctionnement de votre système
• Des questions sur la meilleure approche pour l’architecture du système à un haut niveau
• Des questions sur votre note

Nous attendons de vous que vous ayez fait un effort raisonnable pour penser par vous-même avant de poster une question piazza. Cela est particulièrement vrai en ce qui concerne le débogage de votre code. Avez-vous essayé les pages de manuel ? Avez-vous effectué une recherche sur Google pour trouver des ressources pertinentes ? Avez-vous consulté les questions déjà posées par les utilisateurs et les réponses fournies ? Avez-vous inséré des printf et essayé de comprendre ce qui se passe avec votre code ?

N’utilisez pas autolab comme outil de débogage. Nous attendons de vous que vous ayez fait des efforts raisonnables pour que votre code soit débogué avant de le soumettre à autolab. Créer des cas de test et tester votre code sous contrainte fait partie de ce qu’est un projet. Si vous ne faites pas cet effort, vous manquez une partie importante de l’opportunité d’apprentissage dans ce cours. La soumission à autolab devrait être la dernière étape d’un processus dans lequel vous avez testé, débogué et amélioré votre code dans toute la mesure de vos capacités. Envoyer un dump d’autolab dans un post piazza en disant « please help » est une violation flagrante de l’étiquette piazza.

Les posts privés sur Piazza ne sont pas supportés. Il s’agit d’une décision de politique pour cette classe. Rappelez-vous, poster sur piazza est similaire à lever votre main et poser une question. Les autres étudiants bénéficient du fait que vous posez la question et que vous voyez la réponse de l’instructeur. Si vous le souhaitez, vos messages peuvent être anonymes pour les autres étudiants. Cela représente déjà un degré de confidentialité supérieur à ce qui est possible lorsque vous posez une question en classe. Pour les occasions vraiment rares où vous devez faire une demande privée qui n’est pas liée au contenu du cours, une liste de diffusion privée spéciale a été créée.

Pour les demandes qui doivent vraiment être privées Envoyez un courriel à[email protected]et l’un des instructeurs vous répondra. Les courriels à cette liste impliquant le contenu du cours (par exemple, des clarifications au matériel de classe) seront ignorés ; vous devriez poster de telles questions sur Piazza.

Politique sur les soumissions tardives

Pour les projets:

• Chaque étudiant aura cinq jours de retard à utiliser tout au long du semestre. Ces jours de retard sont destinés à tenir compte des vacances, des voyages, des entretiens, d’un rhume et d’autres situations similaires. Vous êtes libre de les utiliser pour n’importe quelle raison, sans demander la permission aux instructeurs. Vous pouvez utiliser au maximum deux jours de retard pour une même date d’échéance (c’est-à-dire que pour les projets comportant plusieurs points de contrôle, vous pouvez utiliser jusqu’à deux jours de retard pour chaque point de contrôle). Les jours de retard seront automatiquement appliqués dans l’ordre chronologique, vous ne pouvez donc pas choisir de reporter l’utilisation d’un jour de retard pour un devoir futur de poids plus élevé.

• Un jour de retard = (0,24] heures après la date d’échéance ; deux jours de retard = (24, 48] heures après la date d’échéance ; etc.

• Si vous utilisez tous vos jours de retard, vous pouvez soumettre en retard moyennant une pénalité de 15% par jour, jusqu’à deux jours. En d’autres termes, si vous avez utilisé tous vos jours de retard, vous pouvez encore soumettre pendant les deux jours suivants, en encourant une pénalité de 15% pour chacun de ces jours (jours de grâce).

• Vous ne pouvez pas combiner les jours de retard et les jours de grâce pour soumettre plus de deux jours de retard.

Pour les ensembles de problèmes : Aucune soumission tardive n’est acceptée, avec ou sans pénalité. Assurez-vous de soumettre à temps.

Guide de style pour les projets

En plus de tester la fonctionnalité de votre code, nous réserverons également une partie des points de chaque projet pour son style et sa lisibilité. Le plus important est un style cohérent et lisible. Nous cherchons surtout à voir que vous avez choisi un style lisible et raisonnable, et que vous utilisez le même style de manière cohérente tout au long du projet.Faites preuve de bon sens : n’ayez pas de lignes de code de 500 caractères, ne nommez pas vos variables foo (sauf si cela a un sens dans son contexte), et évitez de mélanger les conventions de casse de manière aléatoire.

Nous rechercherons les choses suivantes :

Documentation Une bonne documentation est importante : pour vous-même dans le futur, pour les autres mainteneurs du code, et dans ce contexte, pour les correcteurs qui examineront votre code. Ne ressentez pas le besoin de documenter chaque ligne de code (car un bon code devrait également s’auto-documenter dans un sens), mais il est généralement bon de mettre en évidence l’utilisation générale et le but de chaque fonction, ainsi que les blocs de code importants ou complexes. Une bonne pratique consiste également à inclure un en-tête de fichier dans chaque fichier, détaillant comment ce fichier s’intègre dans la structure du projet dans son ensemble. Espace blanc Veuillez être cohérent. N’utilisez pas la tabulation à 2 espaces à certains endroits et à 4 à d’autres. Soyez raisonnable et utilisez les espaces blancs pour assurer la lisibilité de votre code. Longueur de ligne Nous serons raisonnables quant à la longueur des lignes, tant que vous êtes cohérent et que vos limites de ligne sont raisonnables (500 caractères ne le sont pas… 80 ou 120 caractères sont couramment utilisés et acceptés). Noms de variables Vos noms de variables doivent donner une indication claire de ce qu’ils représentent ou de leur cas d’utilisation. Code mort/de test Essayez de ne pas soumettre un code qui est jonché de déclarations d’impression de débogage ou de gros morceaux de code commentés. Cela réduit la lisibilité et détourne l’attention du code qui sera réellement exécuté en production. Conception Essayez de concevoir votre code et vos projets de manière à ce qu’ils soient raisonnablement modulaires. Les fonctions de 5000 lignes sont généralement un signe de mauvaise conception et vous donneront des maux de tête plus tard.

Voici un guide de style Google qui peut être utile.

Bien-être

Voici quelques conseils pour le bien-être.