C’était censé être une journée de travail parfaitement tranquille lorsque vous avez rencontré pour la première fois le Calcul Distribué. Vous étiez détendu comme Bilbo (enfin, pas tout à fait), mais ce jour-là, vous avez dû affronter ce nouveau problème de classe…
“VEUX-TU ME SOUHAITER UN BON MATIN, OU VEUX-TU DIRE QUE C'EST UN BON MATIN PEU IMPORTE CE QUE JE VEUX?”
Le calcul distribué est une discipline spécialisée au sein de l’informatique, dédiée à l’examen des systèmes distribués. Un système distribué comprend de nombreux composants logiciels, répartis sur plusieurs ordinateurs, tout en fonctionnant de manière transparente comme une entité unifiée. Ce paradigme offre une méthodologie décentralisée afin d’aborder des problèmes complexes, offrant la flexibilité de mettre à l’échelle horizontalement notre système, localement ou sur plusieurs machines, pour améliorer les performances globales.
Pour y parvenir, il faut un changement fondamental dans notre approche de résolution de problèmes. Nous devons passer d’une perspective généralisée et d’un contrôle presque complet de l’exécution des algorithmes à l’adoption d’un point de vue localisé. Dans ce contexte, chaque élément du système collabore localement, contribuant à une résolution complète et harmonieuse du problème d’une manière similaire à une performance chorale.
Notre voyage dans le Calcul Distribué commencera par aborder l’un de ses défis fondamentaux. Nous commencerons par une définition mathématique et progresserons progressivement vers des aspects plus pratiques, en voyant quelques exemples de code utilisant l’un des frameworks les plus célèbres.
Vous pouvez essayer de le résoudre avec les outils que vous connaissez déjà. Mais si vous ne voulez pas quitter La Comté Bag End, restez où vous êtes. Je vous apporte l’aventure.
TL;DR
Je vais vous donner une explication initiale de toute la mathématique derrière ce sujet. Il est nécessaire d’avoir une base et un point de référence pour évaluer la qualité du système que nous utilisons. Je vais au moins effleurer la surface, ou vous pouvez passer à la section du code.
Entités
Pour que notre hypothèse prenne forme, définissons d’abord l’environnement dans lequel nous devons opérer dans un univers soumis à certaines restrictions. Un univers vide est un peu terne. Nous devons le peupler avec quelques petites créatures : les entités. Cette collection finie se compose d’éléments informatiques qui peuvent interagir en échangeant des messages.
Les capacités de notre entité x comprennent :
- accès (stockage et récupération) à la mémoire locale Mx privée et non partagée
- traitement local
- communication (préparation, transmission et réception de messages)
La mémoire locale comprend un ensemble de registres dont les valeurs doivent toujours être initialement définies : le registre d’état status(x) et le registre de valeur d’entrée value(x).
Le registre status(x) prend ses valeurs dans un ensemble fini d’états système S précédemment définis tels que “Inactif”, “En traitement”, “En attente”, etc. De plus, chaque entité dispose d’un réveil cx qui peut être activé et désactivé.
Une entité ne peut effectuer que quatre opérations :
- stockage et traitement local
- transmission de message
- réglage du réveil
- mise à jour du registre d’état
Événements
Il y a trois événements possibles:
- L’arrivée d’un message:
- sonnerie du réveil
- impulsion spontanée
L’arrivée d’un message et la sonnerie du réveil sont des événements externes à l’entité mais qui proviennent de l’intérieur du système : le message est envoyé par une autre entité, l’entité elle-même règle le réveil, tandis qu’une impulsion spontanée est déclenchée par des forces externes au système et donc en dehors des perceptions des entités.
Le comportement de l’entité x est réactif en ce sens qu’elle ne répond qu’aux stimuli externes appelés événements externes (ou simplement événements). En l’absence de stimuli, l’entité x est inerte et ne fait rien.
Actions
Comment l’entité x réagit-elle lorsque survient un événement externe e ? L’entité x réagit à l’événement e en exécutant une action, une séquence finie et indivisible d’opérations avec une terminaison.
Une action est atomique : les opérations composantes sont exécutées sans interruption. En d’autres termes, une fois que l’action commence, elle ne s’arrêtera pas tant qu’elle n’est pas terminée dans un laps de temps donné. Il y aura certains événements qui ne déclenchent aucune réaction sur l’entité cible. Plus précisément, l’entité réagit avec une action unique “nil” dans ces cas-là.
Comportement
Comment se comporte une entité lorsqu’elle est en action ? La nature de l’action qui sera effectuée est définie par la correspondance entre l’événement et la valeur dans l’état(x). Ainsi, la spécification forme la règle:
Status × Event → Action
L’ensemble des règles que l’entité x respecte est le comportement B(x), dans lequel chaque événement possible e et état(x) doit être complet et non ambigu. Ensuite, un ensemble de B(x) provenant de chaque entité dans le système forme un comportement collectif suivant le problème qui doit être résolu.
JE PARS À L’AVENTURE!
Communications
Messages. Maintenant que vous êtes familier avec le calibre de nos citoyens étoiles (aucune arnaque impliquée). Comment interagissent-ils entre eux ? Une chose à retenir est que notre contexte se compose d’un environnement distribué. Nous ne savons pas à l’avance comment nos entités sont disposées dans l’espace de contexte et quelles entités communiquent potentiellement entre elles. Par conséquent, tout comme les humains savent comment communiquer par la voix ou par le texte, la méthode de communication des entités, qui implique la transmission et la réception de messages, doit être définie.
Topologie. Comme vous pouvez le constater, les entités qui peuvent communiquer directement ne sont pas nécessairement l’ensemble complet des entités. En d’autres termes, une entité peut souvent communiquer directement seulement avec un sous-ensemble d’autres entités. Le sous-ensemble Nout(x) est les voisins sortants de x, et il indique l’ensemble des entités auxquelles l’entité x peut transmettre un message directement. De manière similaire, Nin(x) est le voisin entrant de x, qui indique les entités auxquelles l’entité x peut recevoir un message directement.
Cette relation de voisinage définit un graphe dirigé G = (V, E) qui décrit la topologie de communication de l’environnement. C’est la définition générale. Selon le problème donné, des hypothèses peuvent être faites pour simplifier les deux arêtes d’une entité A à B et vice versa en une seule connexion bidirectionnelle.
Exemple de Diffusion
Permettez-moi de vous donner un exemple concret du concept ci-dessus. Dans notre univers, les petites créatures essaient de comprendre où elles se trouvent pour s’organiser. Lorsqu’une entité fait une nouvelle découverte importante, comment peut-elle partager cette information avec toutes les autres entités ? Ainsi, ici, l’entité est confrontée à un problème de diffusion, un problème général de diffusion d’informations.
Dans le cadre de la solution, nous devons simplifier notre tâche en faisant certaines hypothèses et restrictions (qui seront discutées plus en détail dans un autre article de blog):
- Hypothèse 1 : Les liens entre les entités sont bidirectionnels.
Hypothèse 2 : Fiabilité totale. Il n’y a ni défaillances ni n’en arrivera.
- Restriction 1 : La topologie est limitée à avoir seulement le graphe G connecté (pas entièrement connecté, mais il existe au moins un chemin qui connecte chaque entité appartenant à notre ensemble)
Restriction 2 : Initiateur unique. Tel que défini dans le problème, seule une entité découvre à chaque exécution et lance l’algorithme.
La première étape pour résoudre le problème de diffusion est de rendre explicite l’ensemble des états S:
initiateur, inactif, terminé;
Le processus peut être démarré uniquement par l’initiateur ; laissons I dénoter l’information à être
diffusée et impulse l’arrivée de l’impulsion spontanée qui lance l’algorithme.
Voici l’ensemble de règles B(x) (le même pour toutes les entités):
- initiateur × impulse → {envoyer(I) à N(x); devenir terminé}
- inactif × Réception(I) → {Traiter(I); devenir terminé ; envoyer(I) à N(x)}
- initiateur × Réception(I) → néant
- inactif × impulse → néant
- terminé × Réception(I) → néant
- terminé × impulse → néant
Cet ensemble de règles a déjà été optimisé par rapport à la résolution classique du problème de diffusion et est appelé “Protocole de Flood”. Ce protocole introduit un état supplémentaire, terminé, sans lequel le protocole serait formellement incorrect, ne parvenant jamais à un état de repos car les entités continueraient à échanger des messages.
Montre-moi le code
LE MONDE N’EST PAS DANS VOS LIVRES ET CARTES. IL EST LA’-BAS.
Voyons comment nous pouvons rendre cet exemple plus concret.
Pour faire cela, nous utiliserons le framework Akka (https://akka.io/). Mais qu’est-ce qu’Akka ? C’est exactement ce dont nous avons besoin !
Akka est une boîte à outils pour construire des applications hautement concurrentes, distribuées et résilientes, pilotées par messages, pour Java et Scala.
Akka implémente le modèle d’acteur sur la machine virtuelle Java. Sans entrer dans les détails, le modèle d’acteur est proche des concepts que nous avons discutés précédemment.
Pour notre exemple, nous utiliserons la classe FSM fournie par l’API classique du framework (au moment de la rédaction, Akka propose une nouvelle API qui permet de réaliser les mêmes choses, mais pour cet exemple, l’utilisation de la classe FSM offre une corrélation plus explicite avec le pseudo-code vu précédemment).
Laissons de côté la modalité de la définition du graphe d’entités.
- Passons maintenant à définir explicitement les deux types de messages que nos entités peuvent recevoir :
final case class SpontaneousImpulse(info: String)
final case class Receiving(info: String)
- Définissons l’ensemble S des états possibles pour nos entités:
sealed trait State
case object Initiator extends State
case object Idle extends State
case object Done extends State
- Nous devons définir comment l’entité enveloppe l’information dans son magasin de mémoire:
sealed trait Data
case object Uninitialized extends Data
final case class Info(info: String) extends Data
- Et voici globalement la structure et la forme de notre classe:
class Entity(name: String, initialState: State) extends FSM[State, Data] {
startWith(initialState, Uninitialized)
...
// idle × Receiving(I) → {Process(I); become done}
when(Idle) {
case Event(Receiving(ref), Uninitialized) =>
goto(Done).using(Info(ref))
}
// initiator × impulse → {become done}
when(Initiator) {
case Event(SpontaneousImpulse(ref), Uninitialized) =>
goto(Done).using(Info(ref))
}
// done × Receiving(I) → nil
when(Done) {
case Event(e, s) =>
log.warning("I'm {} already know this info {} i'm in {} state", name, e, stateName)
stay()
}
onTransition {
case Initiator -> Done =>
stateData match {
case Info(info) => sendToNeighbours(info)
case _ => // nothing to do
}
case Idle -> Done =>
stateData match {
case Info(info) => sendToNeighbours(info)
case _ => // nothing to do
}
}
...
whenUnhandled {
case Event(e, s) =>
log.warning("received unhandled request {} in state {}/{}", e, stateName, s)
stay()
}
}
Conclusion
J’espère que ce premier article a éveillé votre curiosité à propos de l’informatique distribuée. Le chemin hors de la Comté est dificile, mais une grande satisfaction accompagnera un soupçon d’esprit d’aventure.
Restez à l’écoute pour l’article suivant, dans lequel nous explorerons des sujets tels que le coût du temps ou le nombre de messages, ainsi que quelques exemples pratiques avec Akka.
Quelles questions avez-vous sur l’informatique distribuée ? Laissez-nous un commentaire. Ou faites-nous savoir quels sujets vous souhaitez approfondir.
References
- akka.io
- Design and Analysis of distributed algorithms – Nicola Santoro – Published by John Wiley & Sons, Inc., Hoboken, New Jersey 2007
- Bing Ai
