Gestion du temps et des états dans les systèmes distribués
Gestion du temps et des états dans les systèmes distribués
Distributed Systems · notes
Voir tous les documents en gestion et économie
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
Cette conférence traite de la gestion du temps et des états dans les systèmes distribués, un sujet fondamental pour comprendre comment coordonner des processus répartis sans accès à un temps global unique. Elle s'inscrit dans un cours sur les systèmes distribués et aborde les concepts de causalité, d'horloges logiques et vectorielles, ainsi que la construction d'états globaux cohérents.
Les systèmes distribués sont caractérisés par une latence importante due aux délais de communication, qui sont à la fois significatifs et variables. Ces variations peuvent entraîner des exécutions différentes d’un même protocole, avec des résultats divergents. Par exemple, un chef peut envoyer un message pour ouvrir une vanne, puis un autre pour la fermer quelques minutes plus tard. Selon les délais de transfert, la quantité de liquide peut varier. De plus, la duplication de messages dans le canal de transmission peut compliquer davantage la gestion.
Dans un système distribué, les événements correspondent à tout changement d’état. L’ordre de ces événements est crucial, notamment pour assurer des mécanismes comme l’exclusion mutuelle. Deux événements ne peuvent pas avoir lieu exactement au même instant, et un observateur externe suffisamment précis peut toujours déterminer lequel précède l’autre. Cependant, les processus n’ont accès qu’à des horloges locales, souvent mal synchronisées, ce qui rend difficile la définition d’un ordre global précis. De plus, deux processus différents peuvent percevoir des ordres d’événements différents, posant des problèmes de décisions cohérentes.
Le principe de causalité stipule qu’un effet ne peut précéder sa cause. Dans les systèmes distribués, il est essentiel de respecter ce principe pour éviter des incohérences graves. Par exemple, l’envoi d’un message précède toujours sa réception.
La relation d’ordre causal, notée “→”, est définie par trois règles :
Cette relation est un ordre partiel, car certains événements sont concurrents, c’est-à-dire impossibles à classer causalement.
On distingue la concurrence physique (événements se produisant simultanément) de la concurrence logique (absence de relation causale). Deux événements peuvent être logiquement concurrents même s’ils ne sont pas physiquement simultanés. L’ordre d’exécution des événements concurrents logiques n’affecte pas le résultat des interactions entre processus.
Pour que tous les processus partagent le même ordre sur les événements qui les concernent, on leur associe des dates via des horloges. Ces horloges doivent respecter :
Les horloges logiques permettent aux processus de distinguer les événements concurrents des événements ordonnés. L’objectif est d’établir un ordre total compatible avec la causalité.
Chaque site Si maintient une variable Hi initialisée à 0. Les règles sont :
1. À chaque événement local sur Si : Hi ← Hi + 1;
2. Lors de l’émission d’un message, Hi est incrémenté et le message est estampillé par H(m) ← Hi;
3. À la réception d’un message m : Hi ← max(Hi, H(m)) + 1;
Cet algorithme garantit un ordre total sur les événements, noté “<<”, défini par :
a << b si H(a) < H(b) ou si H(a) = H(b) et le site de a est inférieur à celui de b.
Par exemple, un ordre total sur des événements répartis sur trois sites peut être :
e11 << e21 << e31 << e12 << e13 << e22 << e14 << e23 << e15 << e24 << e32 << e25 << e33 << e34
Cette méthode est utilisée pour l’exclusion mutuelle, le multicast totalement ordonné et la réplication. Ses limites sont que la comparaison des dates ne permet pas toujours de déduire la causalité exacte, et que les horloges ne sont pas bornées.
Les horloges vectorielles améliorent la représentation de la dépendance causale. Chaque site Si maintient un vecteur Vi de taille n (nombre de sites), initialisé à zéro. Les règles sont :
1. À chaque événement local sur Si : Vi[i] ← Vi[i] + 1;
2. Lors de l’émission d’un message : Vi[i] ← Vi[i] + 1, le message est estampillé par V(m) ← Vi;
3. À la réception d’un message m :
Vi[i] ← Vi[i] + 1;
Pour tout j ≠ i : Vi[j] ← max(V(m)[j], Vi[j]);
La relation d’ordre sur les vecteurs est définie par :
Les horloges vectorielles représentent exactement la dépendance causale :
Contrairement aux horloges logiques, elles ne définissent pas un ordre total.
Chaque composante Vi[i] compte le nombre d’événements précédant un événement donné sur le site Si.
Chaque processus Si possède un état local eli, résultant de son état initial et de la séquence des événements sur ce site. Chaque canal de communication cij entre Si et Sj a pour état ecij l’ensemble des messages en transit (émis par Si et non encore reçus par Sj).
Les actions modifiant l’état global sont :
L’état global du système est la somme des états locaux et des états des canaux :
État global = Σ eli + Σ ecij
Un jeton circule entre trois sites S1, S2 et S3. À tout instant, le jeton est soit sur un site, soit en transit dans un canal. Si S3 interroge le système sur le nombre de jetons, il peut recevoir une réponse erronée indiquant deux jetons en circulation, ce qui est incohérent avec la réalité. Cela illustre la difficulté de construire une vision cohérente de l’état global à partir de vues locales prises à des instants différents.
Une coupure est un ensemble d’événements contenant au moins un événement par site. Elle est dite cohérente si elle est fermée par la relation de dépendance causale. Formellement, une coupure C est cohérente si :
(a ∈ C et a → b) ⇒ b ∈ C
Autrement dit, si un événement appartient à la coupure, alors tous les événements qui en dépendent causalement doivent aussi y appartenir.
La date d’une coupure C = (c1, ..., cn) est définie par le vecteur :
V(C) = sup(V(c1), ..., V(cn))
où V(ci) est l’horloge vectorielle associée à l’événement ci.
Une coupure est cohérente si :
V(C) = (Vc1[1], ..., Vci[i], ..., Vcn[n])
Un exemple montre que certaines coupures ne sont pas cohérentes car la composante d’un vecteur ne respecte pas la fermeture causale.
Pour construire un état global cohérent, l’algorithme de Chandy-Lamport utilise un marqueur envoyé par un processus Si :
À la réception d’un marqueur par Sj via le canal cxj :
Dans l’exemple, le jeton est capturé dans l’état du canal ec12. Ensuite, les processus échangent leurs états locaux et les états des canaux enregistrés pour construire l’état global cohérent.