Systèmes Distribués et Répartis

Olivier Lemer

Reveal.js slides

Hide les notes

Liste des raccourcis clavier

Naviguer dans les slides

Voir toutes les slides

Esc

Logistique

Cours - mardi, 14h45-16h15, en C23.

Labos - mercredi, 13h00-14h30, en G04.

Horaires

3 tests écrits (67%)
4 labos notés (33%) + 1 d'échauffement

Notation

Matériel du cours

Centralisé sur sdr-classroom.github.io.

Labos

Données et rendus sur GitHub Classroom.

Discussions

Feedback, questions, suggestions sur Teams.

Labos

Généralement 4 semaines par labo, par groupes de 2.

Semaine 1

Semaine 2

Semaine 3

Semaine 4

Rendu 1 minute avant le début du labo suivant.

Planning

Implémentation

Dès validation, le développement peut commencer.

Conceptualisation

Définir et valider les abstractions, leur API, leur intégration.

Échangez avec nous pour créer une confiance en votre approche.

Labos

Intro à Go

Échauffement

Labo 2

Labo 3

Labo 4

Labo 1

Protocoles de fiabilité

Exclusion Mutuelle

Élection

Sondes et échos

Labos

Phase de conception

Généralement 4 semaines par labo, par groupes de 2.

Séance 1

Séance 2

Séance 3

Séance 4

Rédaction d'un document d'architecture logicielle.

Phase de mise en oeuvre

Sur la base d'une proposition d'achitecture fournie.

Mise en oeuvre de la solution.

Rédaction d'un document d'architecture logicielle descriptif.

Rendu 1min avant début du labo suivant.

(25%)

(75%)

Les IAs

Ma vision

Utiliser la bonne syntaxe

(dépend du langage, peu de réflexion)

Utiliser des if et des boucles

(code linéaire simple, niveau introductif)

Réaliser une logique

(i.e. implémenter un algorithme donné)

Réaliser une abstraction

(i.e. comment la boite noire fonctionne pour satisfaire sa spécification)

Transformer un besoin en abstractions et leurs interactions

(i.e. définir les boites noires, et comment elles intéragissent)

Compétences des LLM

Ce qui fera de vous de bon.ne.s ingénieur.e.s

Ça tombe bien

Ce qui vous fera sortir du lot, c'est ce que vous ne pourrez pas déléguer aux IAs.

Les IAs

Votre objectif

Cherchez à sortir du lot.

Construisez-vous une valeur ajoutée aux vibe-coders.

Être capable de dire

"Non, cette abstraction a trop de responsabilités, il faut..."

"Non, cet import est superflu, utilisons plutôt..."

"Attention, on commence à dépendre de détails d'implémentation..."

"Attention, ce module fait une supposition sur celui-ci qui..."

"Non, cette fonction devrait retourner une promesse, parce que..."

...

Programme

Introduction - Définitions, Fiabilité et pannes

Golang

Estampilles - Horloges logiques, exclusion mutuelle

Jetons - Exclusion mutuelle

Diffusion - Élection de leader

Sondes et échos - Exemples et synchroniseurs

Synchronisation et battements - Exemples

Consensus (!)

Aujourd'hui

Définition d'un système distribué et réparti

Classes de fiabilité

Exercices théoriques

Si le temps le permet :

Définition des pannes

Découverte du Go.

Cours

Labo

Système distribué ?

Définition(s)

Réparti

Distribué

Décentralisé

Système s'executant sur

un ensemble de processus (process, machine, etc),
sans mémoire partagée,
vu par l'utilisateur.rice comme une seule entité.

Système

S'emploie plus quand on parle des taches et leur répartition.

S'emploie plus quand on parle de l'architecture du système.

Système distribué dans lequel il n'existe pas d'autorité centrale responsable du contrôle du système.

Relativement interchangeables.

Enjeux

Logiciel

Problèmes simples deviennent compliqués
Tous langages ne sont pas adaptés
Niveau de transparence sur l'aspect réparti

Fiabilité

Délai du réseau
Perte de messages
Crash de machines

Résilience à

Partage de données

Synchronisation des données entre machines
Protection et sécurité des données

Parallèle vs. concurrent

Parallélisme

Définition

Lorsque deux taches sont en cours d'execution au même instant.

Question : Quelles unités de traitement executent ces taches ?

Threads

→ Système multi-threaded

Machines

→ Système distribué

Threads

(e.g. CPU multi-coeur)

(e.g. Réseau de PC interconnectés)

Difficulté : Coordonner les unités de traitement.

Execution parallèle

Time

Parallélisme vs. Concurrence

Définition Parallélisme

Lorsque deux taches sont en cours d'execution au même instant.

Parallélisme

Time

→ T1, T2 et T3 s'exécutent de manière concurrente, mais pas toujours parallèle.

Concurrence

Définition Concurrence

Lorsque deux taches ont progressé dans un interval commun.

Classification de Flynn

Catégorisation des machines selon 2 axes : flots de données, et

(i.e. contrôle)

flots d'instructions.

Flot d'Instructions (Contrôle)

Flot de Données

Single

Multiple

Single

Multiple

SISD	MISD
SIMD	MIMD

Classification de Flynn

SISD

Banque d'instructions

Banque de données

(a.k.a. Architecture Von Neumann (1945))

un seul flot séquentiel d'instructions

un seul flot de données

une seule unité de traitement

Classification de Flynn

SIMD

Banque d'instructions

Banque de données

Un seul flot séquentiel d'instructions,

partagé par tous les PU.

Plusieurs flots de données, un par PU.

Plusieurs unités de traitement

Par exemple pour calcul scientifique (vecteurs et matrices)

Classification de Flynn

MISD

Banque d'instructions

Banque de données

Plusieurs flots d'instructions, un par PU.

Un seul flot de données,

partagé par tous les PUs.

Plusieurs unités de traitement.

Architecture théorique...

Classification de Flynn

MIMD

Banque d'instructions

Banque de données

Plusieurs flots de données, un par PU.

Plusieurs unités de traitement

L'exécution peut ici être asynchrone. L'enjeu est la synchronisation des PUs.

Plusieurs flots d'instructions,

parfois partagés par plusieurs PUs.

Classification de Flynn

Catégorisation des machines selon 2 axes : flots de données, et

(i.e. contrôle)

flots d'instructions.

Flot d'Instructions (Contrôle)

Flot de Données

Single

Multiple

Single

Multiple

SISD	MISD
SIMD	MIMD

Distributed memory

Shared memory

Classification de Flynn

MIMD (Shared Memory)

Banque d'instructions

Communication inter-processeurs via la mémoire commune.

Banque de données

Classification de Flynn

MIMD (Shared Memory)

Banque d'instructions

Main memory

Cache

Bus Arbiter

System Bus

I/O

Communication inter-processeurs via la mémoire commune.

Classification de Flynn

MIMD (Distributed Memory)

Banque d'instructions

Communication inter-processeurs via le réseau.

Banque de données

Banque d'instructions

Banque de données

Classification de Flynn

MIMD (Distributed Memory)

(e.g. Massively Parallel Processing (MPP))

Ordinateur

Plusieurs ordinateurs distincts.

Interconnection par réseau.

Par exemple

Computer clusters
Grid Computing
BOINC

Couplage

Matériel vs. logiciel

Couplage matériel

Le couplage matériel

"Quantité et qualité des liens entre éléments."

Couplage faible

Couplage fort

Beaucoup de liens, rapides.

Peu de liens, lents.

Shared Memory MIMD

Distributed Memory MIMD

Débit élevé
Délai faible

Peut partager beaucoup, rapidement.

Débit faible
Délai élevé

Peut partager peu, avec delai.

En fonction du couplage de l'architecture matérielle ciblée,

une même application devra être conçue très différemment.

Ôyez, concepteur.rices !

Couplage logiciel

Le couplage logiciel

Couplage faible

Couplage fort

Beaucoup de liens, rapides.

Peu de liens, lents.

"Quantité et qualité des liens entre éléments."

Module A

Module B

getX

setX

incX

setY

Module A

Module B

buy

Couplage : 4

Couplage : 1

Généralement, on vise un couplage logiciel faible :

interfaces plus claires

risque de bugs moindre

Couplage logiciel

Execution réseau :

et Execution réseau

couplage matériel faible,

donc coût de communication élevé,

donc couplage logiciel fort "couteux".

Ordinateur

Execution réseau

Logiciel réseau simple

vs Programme réparti

Serveur simple

Logiciel réseau faiblement couplé

Logiciel réseau réparti

Serveur implicitement distribué
Couplage logiciel naturellement faible

Serveur implicitement distribué
Couplage logiciel à tendence forte

(telnet, wget, ssh)

(NFS, iCloud Drive)

(calcul distribué)

Conception logicielle combat ce couplage

Couche logicielle de répartition

Pour le client, une API simple, inconsciente de la répartition.

Client

Serveur

Système réparti

Les serveurs offrent un service indépendant de la répartition.

Une couche logicielle gère l'aspect réparti.

Système réparti

Définition :

Le challenge est d'optimiser le couplage logiciel effectif pour assurer une performance élevée.

Un système réparti est donc

l'execution d'une logique nécessitant un couplage logiciel fort,

sur du matériel limité à un couplage matériel faible.

Propriétés

Un bon système réparti

Système réparti

Qu'est-ce qu'un bon système réparti ?

1. Abstraction

2. Fiabilité

3. Performance

4. Dimensionnement

Système réparti

Qu'est-ce qu'un bon système réparti ?

1. Abstraction

Emplacement des processus et données

Pas d'adresses physiques des machines ou des données.

Migration des processus et données

Déplacement de ressource (processus, données) invisible.

Duplication des données

Gestion implicite des copies éventuelles.

Cohérence des données

Gestion implicite de la concurrence.

Système réparti

Qu'est-ce qu'un bon système réparti ?

1. Abstraction

2. Fiabilité

3. Performance

4. Dimensionnement

(Emplacement, Migration, Duplication, Cohérence)

Système réparti

Qu'est-ce qu'un bon système réparti ?

2. Fiabilité

Disponibilité

Résilience aux pannes de machines et de réseau

Cohérence

État toujours correct (récupération après panne, résistance aux attaques)

Système réparti

Qu'est-ce qu'un bon système réparti ?

1. Abstraction

2. Fiabilité

3. Performance

4. Dimensionnement

(Emplacement, Migration, Duplication, Cohérence)

(Disponibilité, Cohérence)

Système réparti

Qu'est-ce qu'un bon système réparti ?

3. Performance

Parallélisme maximal

Tirer profit du parallélisme, éviter qu'une machine soit en attente de travail.

Communication minimale

Diminuer le nombre d'échange de messages.

Tradeoff Performance-Fiabilité :

Garantir la fiabilité nécessite des protocoles limitant les performances.

Système réparti

Qu'est-ce qu'un bon système réparti ?

1. Abstraction

2. Fiabilité

3. Performance

4. Dimensionnement

(Emplacement, Migration, Duplication, Cohérence)

(Disponibilité, Cohérence)

(Parallélisme, Communication)

Système réparti

Qu'est-ce qu'un bon système réparti ?

4. Dimensionnement

Extensibilité

Ajouter une machine doit être possible et peu couteux.

Complexité algorithmique faible

Avoir plus de machines ne doit pas rendre le service notablement plus lent.

(scalability)

Ceci implique d'éviter les goulots d'étranglement, par exemple

Élément centralisé
Nécessité de connaissance d'un état global

Les algorithmes n'ont donc accès qu'à des informations partielles du système

Système réparti

Qu'est-ce qu'un bon système réparti ?

1. Abstraction

2. Fiabilité

3. Performance

4. Dimensionnement

(Emplacement, Migration, Duplication, Cohérence)

(Disponibilité, Cohérence)

(Parallélisme, Communication)

(Extensibilité, Complexité)

Erreurs réseau

Synchronicité

Copie du message

Dans les cas non-bloquants, le message est mis de coté (buffered) le temps de pouvoir être envoyé au destinataire, ou traité par le client.

Envoi bloquant

Client

Gestion réseau

Copie et envoi du message

Client

Gestion réseau

Copie du message

Envoi du message

Envoi non-bloquant

Client

Gestion réseau

Attente de réception et copie du message

Réception bloquante

Client

"Pas de message"

Attente de réception

Gestion réseau

Message reçu !

Réception non-bloquante

Traitement des erreurs

Garanties du réseau

Pas de

perte

Pas de

duplication

Pas de

changement d'ordre

Un message envoyé est reçu.

Un message envoyé n'est reçu q'une fois.

L'ordre de réception est celui d'envoi.

→ Différents protocoles de fiabilité

Responsabilités du Système Réparti

Le système réparti doit

assurer la résilience aux pannes (de serveur et du client)

maintenir les garanties du réseau, et

Ce que nous supposerons dans ce cours.

Protocoles de fiabilité

Protocole Request "peut-être"

Protocoles de fiabilité

Protocole R (Request)

(aka "Peut-être")

Client

Serveur

Time

Uniquement une requête,

pas de réponse du serveur.

Panne Serveur ?

Requête perdue, client l'ignore.

Le message sera peut-être traité.

Envoi

Réception

Traitement

Envoi

Protocoles de fiabilité

Protocole Request-Reply "au moins une fois"

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Time

Réponse envoyée en fin de traitement.

Envoi

Réception

req

Envoi

Réception

rep

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

req

Stop timer

Timeout !

Start timer

Réception

req

Renvoi

Réception

Envoi

rep

Start timer

déclenche un renvoi.

est annulé à la réception.

Timeout

Problème ?

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

req

Timeout !

req

Start timer

Renvoi

Problème ?

Renvoi

Risque de reception double.

Doublon !

(version "Au moins une fois")

Réception

Envoi

rep

déclenche un renvoi.

est annulé à la réception.

Timeout

Envoi

Réception

rep

Réception

Start timer

Stop timer

Le message sera traité

au moins une fois

Protocoles de fiabilité

Protocole Request-Reply "exactement une fois"

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

Réception

req:1

Timeout !

Envoi

rep:1

req:1

Start timer

Renvoi

Start timer

Stop timer

Réception

Renvoi

Timeout

Identificateur

Pour détecter les doublons.

id:1

Doublon : ignoré

Stocké indéfiniment ?

déclenche un renvoi.

est annulé à la réception.

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

req:1

Timeout !

Start timer

Renvoi

Start timer

Identificateur

Renvoi

Timeout

Pour détecter les doublons.

Stocké indéfiniment ?

Timeout !

Renvoi

req:1

Réception

Doublon : ignoré

Envoi

rep:1

req:1

Réception

id:1

Doublon : ignoré

déclenche un renvoi.

est annulé à la réception.

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

Réception

req:1

Timeout !

Start timer

Renvoi

Start timer

Identificateur

Renvoi

id:1

Timeout

Pour détecter les doublons.

Stocké jusqu'à nouveau message.

Timeout !

Stop timer

Réception

Nouvel id : remplacement

Envoi

req:2

id:2

Start timer

Envoi

req:1

Réception

Doublon : ignoré

rep:1

Problème ?

déclenche un renvoi.

est annulé à la réception.

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

Réception

req:1

Timeout !

Start timer

Renvoi

Start timer

Identificateur

Renvoi

id:1

Timeout

Pour détecter les doublons.

Stocké jusqu'à nouveau message.

Timeout !

Stop timer

Réception

Envoi

req:1

rep:1

Doublon !

Problème ?

id:1

rep:1

Réception

Risque de reception double.

déclenche un renvoi.

est annulé à la réception.

Protocoles de fiabilité

Protocole RR (Request-Reply)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

Réception

req:1

Timeout !

Start timer

Renvoi

Start timer

Identificateur

id:1

Timeout

Pour détecter les doublons.

Stocké jusqu'à nouveau message

Timeout !

Stop timer

Réception

Envoi

id:1

req:1

rep:1

rep:1

Réception

Doublon : ignoré

id:1

dans serveur et client.

Problème ?

Si requêtes rares mais beaucoup de clients :

(version "Exactement une fois")

trop d'identificateurs à gérer.

déclenche un renvoi.

est annulé à la réception.

Protocoles de fiabilité

Protocole Request-Reply-Acknowledge

Protocoles de fiabilité

Protocole RRA (Request-Reply-Acknowledge)

Client

Serveur

Envoi

Réception

Réponse envoyée en fin de traitement.

Réception

req:1

Renvoi

Identificateur

Renvoi

id:1

Timeout

Pour détecter les doublons.

Stocké jusqu'à nouveau message

Envoi

rep:1

req:1

Réception

Doublon : ignoré

ack:1

Réception

id supprimé

Acknowledgment

ou acknowledge.

Notifie le serveur

de la réception d'une réponse

Start timer

Timeout !

Stop timer

id:1

déclenche un renvoi.

est annulé à la réception.

Protocoles de fiabilité

Protocole RRA (Request-Reply-Acknowledge)

Client

Serveur

Réception

Réponse envoyée en fin de traitement.

req:1

Identificateur

id:1

Timeout

Pour détecter les doublons.

Stocké jusqu'à nouveau message

Envoi

rep:1

req:1

Réception

Acknowledgment

ou acknowledge.

Notifie le serveur

de la réception d'une réponse

Envoi

Réception

Renvoi

Start timer

Timeout !

Stop timer

id:1

ack:1

de messages oubliés.

, et

id:1

Réception

Tache annulée

id supprimé

déclenche un renvoi.

est annulé à la réception.

Exercice

Supposez que le réseau ne nous garantit plus l'absence de perte de message. Quelles sont alors les garanties données par les différentes classes de fiabilité ? Pour répondre, notez pour chacun des 4 protocoles, s'il y a ou non risque de

absence de traitement d'une requête
duplication de traitement d'une requête
absence de confirmation d'une requête
duplication de confirmation de traitement

et si oui, un exemple de scénario qui peut le causer.

Question 1

Question 2

Que se passe-t-il dans RR version "exactement une fois" si le traitement est très long ?

Si de nouveaux problèmes surgissent pour RR avec id et RRA, quelle solution proposez-vous ?

Question 3

Que se passe-t-il dans RR version "exactement une fois" si le client tombe en panne temporairement avant d'avoir reçu une réponse ? Quelle solution proposer ?

Exercice

Solution 1

Absence traitement

Duplication traitement

Absence confirmation

Duplication confirmation

RR avec id

RRA

Impossible :

Le client réessaie après timeout

Impossible :

Le client réessaie après timeout

Impossible :

Le client réessaie après timeout

Impossible :

Le client n'envoie jamais en double.

Inapplicable :

Le client ne reçoit jamais de confirmation.

Inapplicable :

Le client ne reçoit jamais de confirmation.

Impossible :

Le client réessaie après timeout

Impossible :

L'id assure l'absence de doublon coté serveur

Possible, mais pas à cause d'une perte de message.

Impossible :

l'identificateur supprime les doublons

Impossible :

l'identificateur supprime les doublons

Impossible :

L'id assure l'absence de doublon coté serveur

ignoré

Exercice

Solution 1 (continued)

RR avec id et RRA ont un risque d'absence de confirmation en cas de perte de la réponse.

Le problème est que le serveur se reposait sur la garantie du réseau pour ignorer les doublons. Il doit maintenant renvoyer la réponse, même s'il pense être face à un doublon.

Afin d'éviter le cout de recalculer la réponse, celle-ci peut être stockée en cache avec l'id du message. Ceci sera couteux en mémoire pour RR avec id, mais résolu avec le système d'ack de RRA.

Noter aussi le problème de la perte du ACK dans RRA : l'id (et la réponse) ne seront jamais supprimés chez le serveur. La conséquence n'est cependant pas un échec fatal du serveur ou du protocole.

Exercice

Solution 2

En cas de traitement long :

Le client timeout et renvoie la requête.
Le serveur utilise l'id pour détecter le doublon et l'ignore.
La réponse du serveur est perçue comme réponse à la seconde requête du client et stoppe le timer.

Client

Serveur

Envoi

Réception

req:1

Timeout !

Envoi

rep:1

req:1

Start timer

Renvoi

Start timer

Stop timer

Traitement

Réception

doublon : ignoré

id:1

Exercice

Solution 3

En cas de panne du client :

Lorsqu'il revient, s'il veut envoyer un nouveau message (potentiellement indépendant du précédent), celui-ci sera ignoré par le serveur.
Le client réessaiera infiniment, entrant dans une boucle infinie.

Client

Serveur

Envoi

Réception

req:1

rep:1

req:1

Start timer

Nouvel envoi

Start timer

Stop timer

Traitement

Réception

doublon : ignoré

id:1

id:1

id:1

Nouvel envoi

Start timer

req:1

Réception

doublon : ignoré

Exercice

Solution 3 (continued)

Solution

Le client doit envoyer un identifiant unique de l'éxécution en cours.

Ainsi, les ids seront différents lors de la seconde éxécution, et le serveur ne croira pas à un doublon.

Une manière de garantir cette unicité des identifiants peut être d'y accoller l'heure du début de son éxécution.

Client

Serveur

Envoi

Réception

req:T1:1

rep:T1:1

req:T2:1

Start timer

Nouvel envoi

Start timer

Stop timer

Réception

Nouvel id !

id:T1:1

id:T1:1

id:T2:1

id:T2:1

rep:T1:1

rep:T2:1