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 J04.

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

Horaires

2 tests écrits (67%)
4 labos notés (33%)

Notation

Matériel du cours

Centralisé sur sdr-classroom.github.io.

Labos

Données et rendus sur GitHub.

Discussions

Feedback, questions, suggestions sur Teams.

Labos

4 semaines par labo, par groupe de deux.

Quiz individuel en fin de chaque labo

Prouvez-nous que vous comprenez votre solution et ses choix.

1. Reliable Broadcast et Mutex

Sans pannes

2. Élection

3. Synchronisation

4. Consensus

Avec pannes

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é, diffusion et pannes

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é

Reliable Broadcast (Diffusion Fiable)

Si le temps le permet :

Définition des pannes

Cours

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 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

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 à tendance 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

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

On pourrait donc dire qu'un système réparti est

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