Olivier Lemer
1.
Types de pannes
2.
Protocoles de fiabilité
3.
Broadcast
4.
Détection de pannes
Panne dont on ne reviendra jamais
A
∞
B
∞
On dit qu'un processus est correct en terme de panne permanente
quand il ne tombera jamais en panne permanente.
L'aspect "correct" est une caractéristique théorique.
Elle servira à analyser les algorithmes du cours.
(e.g. "cet algorithme fonctionne ssi tous les processus sont corrects en terme de panne permanente",
équivalent à dire "cet algorithme fonctionne ssi aucun processus ne tombe en panne.")
Elle n'a aucun sens dans la vraie vie.
(Impossible de savoir si un processus tombera un jour en panne ou non)
Panne dont on peut revenir, parfois en ayant perdu des informations ("amnésie").
On dit qu'un processus est correct en terme de panne récupérable
quand il existe un instant T après lequel il ne tombera plus en panne.
A
∞
Donc, un processus qui tombe constamment en panne, ou qui ne revient jamais d'une panne n'est pas correct.
Un processus qui revient d'une panne en est conscient.
B
∞
T
a.k.a. byzantine
Panne suite à laquelle tout est possible...
Peut être due à un bug, ou bien à une corruption par un agent malicieux.
A
∞
On dit qu'un processus est correct en terme de panne arbitraire
quand il suivra toujours l'algorithme attendu.
B
∞
Évidemment, le type de panne le plus couteux à supporter.
Panne d'omission
Lorsqu'un message devant être envoyé ne l'est pas.
Panne d'eavesdropping
Lorsqu'un message peut être lu par une entité extérieure au système.
Pas de
perte
Pas de
duplication
Pas de
changement d'ordre
Un message envoyé est reçu.
Un message envoyé n'est reçu qu'une fois.
L'ordre de réception est celui d'envoi.
Tolérer les pannes
fair-lossypertes de message autorisées,
mais après assez de renvois, le message finit par arriver.
En cas de panne,
maintenir le progrès (l'algorithme avance)
maintenir la validité (l'algorithme reste correcte)
Supposées, à ne pas casser.
Remote Procedure Call
Interface identique à un appel de fonction classique,
mais exécuté sur une autre machine.
Problème : L'autre machine peut tomber en panne.
Résolu par 4 protocoles de fiabilité.
Protocoles de fiabilité
"peut-être" (a.k.a. maybe)
(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é
"au moins une fois" (a.k.a. at-least-once)
Client
Serveur
Time
Réponse envoyée en fin de traitement.
Envoi
Réception
req
Envoi
Réception
rep
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 ?
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é
"au plus une fois" (a.k.a. at-most-once)
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.
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 !
!
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.
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.
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.
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 "Au plus une fois")
trop d'identificateurs à gérer.
déclenche un renvoi.
est annulé à la réception.
Protocoles de fiabilité
(a.k.a. at-most-once, avec libération de l'état serveur)
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
Start timer
Timeout !
!
Stop timer
id:1
déclenche un renvoi.
est annulé à la réception.
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
Renvoi
!
Start timer
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.
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
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 ?
Solution 1
Absence traitement
Duplication traitement
Absence confirmation
Duplication confirmation
R
RR
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é
ignoré
!
!
ignoré
ignoré
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.
Solution 2
En cas de traitement long :
Client
Serveur
Envoi
Réception
Réception
req:1
Timeout !
!
Envoi
rep:1
req:1
Start timer
Renvoi
Start timer
Stop timer
Traitement
Réception
doublon : ignoré
id:1
Solution 3
En cas de panne du client :
Client
Serveur
Envoi
Réception
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é
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
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
R maybe
"peut-être"
RR at-least-once
"au moins une fois"
RR + id at-most-once
"exactement une fois"
RRA at-most-once
"au moins une fois" + libère l'état serveur
On pourra supposer à partir de maintenant un envoi fiable, type RRA.
Une diffusion fiable
Le plus simple : Best effort
A
B
C
D
Broadcast
Envoyer à tous les processus.
Le plus simple : Best effort
A
B
C
D
Broadcast
Envoyer à tous les processus.
Tolérance aux pannes : Reliable Broadcast
A
B
C
D
Broadcast
Envoyer à tous les processus.
Lorsqu'on reçoit un message,
le renvoyer à tous,
A
B
C
D
Broadcast
Envoyer à tous les processus.
Lorsqu'on reçoit un message,
le renvoyer à tous,
peu importe d'où il vient,
Tolérance aux pannes : Reliable Broadcast
A
B
C
D
Broadcast
Envoyer à tous les processus.
Lorsqu'on reçoit un message,
le renvoyer à tous,
peu importe d'où il vient,
sauf si déjà reçu.
Tolérance aux pannes : Reliable Broadcast
Propriétés garanties
Validité
Si un processus correct envoie m,
alors il finit par délivrer m
Accord
Si un processus correct délivre m,
alors tous les processus corrects délivrent m
Non-création
Un processus ne délivre m que si m a été envoyé
Non-duplication
Un processus délivre m au plus une fois
"Surveille <id>"
"Panne de <id> détectée"
"Arrête de surveiller <id>"
Propriétés
p est détecté par un quelconque processus, alors p est en panne.Supposons pour l'instant des pannes permanentes uniquement.
Détecteur de pannes parfait
T sur la durée de transit de tout message.On parle de système distribué "synchrone".
B
A
"Surveille B"
PING
PONG
PING
PONG
PONG
PING
Périodiquement, le surveillant
envoie un ping, et
lance un timer de 2T.
Le surveillé
répond à ping par pong.
À la fin du timer,
Si le pong a été reçu,
Un nouveau ping est envoyé
Un nouveau timer est lancé
B
A
"Surveille B"
PING
Périodiquement, le surveillant
envoie un ping, et
lance un timer de 2T.
"Panne de B détectée"
Le surveillé
répond à ping par pong.
À la fin du timer,
Si le pong a été reçu,
Un nouveau ping est envoyé
Un nouveau timer est lancé
Sinon,
Une panne est signalée
Est-ce que ça vérifie
Complétude ?
Précision ?
Oui, un processus en panne permanente ne répondra plus aux pings, et après 2T, cette panne sera découverte.
Oui, puisqu'un message ne prend jamais plus de T unités de temps pour transiter, je dois avoir reçu un pong après 2T si le processus est correct.
Problème ?
La supposition d'un système synchrone est irréaliste. Les vrais réseaux ne nous donnent pas de garantie sur la durée de transit d'un message.
"Un jour, tout processus en panne sera détecté par tout processus correct."
"Si un processus p est détecté par un quelconque processus, alors p est en panne."
surveillés
ensemble d'entiers
processus que je surveille
pongs_reçus
ensemble d'entiers
ont répondu au dernier ping
T
constante
borne sur la durée de transit
Initialisation
Écouter infiniment les événements suivants :
Demande de surveillance de i
Demande d'arrêt de surveillance de i
Réception d'un ping de i
Réception d'un pong de i
Fin du timer de i
Demande de surveillance de i
Ajouter i à surveillés
Envoyer un ping à i
Lancer un timer de 2T pour i
Demande d'arrêt de surveillance de i
Enlever i de surveillés
Réception d'un ping de i
Envoyer un pong à i
Réception d'un pong de i
Ajouter i à pongs_reçus
Fin du timer de i
Si i est dans pongs_reçus
Enlever i de pongs_reçus
Envoyer un ping à i
Lancer un timer de 2T pour i
Sinon
Signaler « Panne de i détectée »
Enlever i de surveillés
"Surveille <id>"
"Panne de <id> suspectée"
"Arrête de surveiller <id>"
Propriétés
"Suspicion de <id> annulée"
Détecteur de pannes parfait un jour
On parlera ici de système distribué "partiellement synchrone".
T inconnue sur la durée de transit de tout message.B
A
"Surveille B"
PING
"Panne de B suspectée"
PONG
"Suspicion de B annulée"
Initialement,
envoie un ping, et
lance un timer de durée 𝚫
Le surveillé
répond à ping par pong.
À la fin du timer,
Si le pong n'a pas été reçu,
𝚫 est incrémenté d'une constante
lance un timer de durée 𝚫
Envoie un ping, et
Une panne est suspectée
Si un pong est reçu d'un suspecté
La suspicion est annulée.
PING
PING
PONG
PONG
Est-ce que ça vérifie
Complétude ?
Précision un jour ?
Oui, un processus en panne permanente ne répondra plus aux pings, et après 𝚫, cette panne sera découverte.
Oui, un processus correct (en terme de panne permanente comme récupérable) répondra aux pings en un temps fini ; quand 𝚫 sera assez grand, plus de panne ne sera suspectée : tout processus sera soit "en panne" et suspecté pour toujours, ou "correct" et plus jamais suspecté.
Était-il nécessaire d'avoir un timeout dynamique ?
Oui, sinon on risquerait de constamment suspecter un processus qui est simplement lent mais bien correct.
"Un jour, tout processus en panne permanente sera suspecté par tout processus correct."
"Un jour, aucun processus correct ne sera suspecté par un processus correct."
𝚫 ne décroît jamais.
Un réseau redevenu rapide garde un détecteur arbitrairement lent.
surveillés
ensemble d'entiers
processus que je surveille
suspectés
ensemble d'entiers
ceux que je suspecte
pongs_reçus
ensemble d'entiers
ont répondu au dernier ping
𝚫
entier, init 𝚫₀
timeout courant, commun à tous
Demande de surveillance de i
Ajouter i à surveillés
Envoyer un ping à i
Lancer un timer de 𝚫 pour i
Réception d'un pong de i
Ajouter i à pongs_reçus
Si i est dans suspectés
Enlever i de suspectés
Signaler « Suspicion de i annulée »
Fin du timer de i
Si i n'est pas dans pongs_reçus
𝚫 est incrémenté d'une constante
Ajouter i à suspectés
Signaler « Panne de i suspectée »
Enlever i de pongs_reçus
Envoyer un ping à i
Lancer un timer de 𝚫 pour i
Les deux autres événements sont ceux du détecteur parfait.
Le détecteur parfait suppose une borne T connue et des pannes permanentes.
Que se passe-t-il si un processus surveillé tombe en panne puis récupère ?
Reprenez le pseudocode du détecteur parfait et dites, pour chacune des deux propriétés, si elle tient encore, et pourquoi.
Précision : perdue.
Le processus est signalé en panne alors qu'il répondra de nouveau. Le détecteur l'a même retiré de surveillés, donc il ne se corrigera jamais.
Complétude : conservée.
Elle ne parle que des pannes permanentes, et celles-là sont toujours détectées.
→ C'est exactement ce que le détecteur parfait un jour vient corriger, en annulant ses suspicions.