Une innovation pour la création de systèmes distribués robustes
Abstract background of wires and glowing particles © iStock 2023
Des chercheuses et chercheurs de l’EPFL ont mis au point un nouvel algorithme distribué qui résout, pour la première fois, l’un des problèmes majeurs de performance et de fiabilité concernant bon nombre de protocoles de consensus actuellement déployés.
Le consensus fait partie des problèmes fondamentaux des systèmes distribués. Il permet à un ensemble de machines de conserver plusieurs copies de données et de les mettre à jour de manière cohérente, même en cas de défaillance d’une partie des machines.
Prenons l’exemple de trois serveurs qui doivent stocker trois copies de données et suivre les mises à jour des informations pour rester cohérents. Si un serveur tombe en panne, les deux autres doivent maintenir la cohérence des données et permettre aux mises à jour de se poursuivre normalement, comme s’il n’y avait pas eu de défaillance.
Les protocoles de consensus actuels reposent sur la désignation, à tout moment, d’un nœud informatique comme chef de file, qui supervise et gère en permanence les mises à jour des données. Si le chef de file est défaillant, un autre nœud s’active et prend le relais, mais un problème se pose. Combien de temps un autre nœud doit-il attendre avant de prendre le relais d’un chef de file qui ne répond pas?
«Si le chef de file est défaillant ou si le réseau est mauvais, le problème avec les protocoles de consensus classiques est qu’il est très difficile de fixer le délai d’attente», explique le professeur Bryan Ford, directeur du Laboratoire de systèmes décentralisés et distribués (DEDIS) de la Faculté informatique et communications de l’EPFL (IC). «Si vous fixez un délai trop long, lorsqu’un chef de file tombe en panne, vous risquez d’attendre longtemps et le système est tout simplement inopérant. À l’inverse, avec un délai trop court, vous risquez de provoquer un véritable désastre.»
«Supposons que l’ancien chef de file ne soit pas tombé en panne, que le réseau soit juste un peu plus lent que ce que vous pensiez, que le prochain chef de file arrive et essaie de prendre le relais, mais selon le fonctionnement de tous les protocoles existants. Les actions du nouveau chef de file annuleront celles de l’ancien chef de file, de sorte que ce dernier ne pourra plus terminer ce qu’il était en train de faire. Tout son travail sera alors perdu. Ce type de situation peut entraîner de graves problèmes de fiabilité. Ces protocoles basés sur des chefs de file peuvent devenir totalement défaillants en cas d’attaque délibérée par déni de service», poursuit-il.
Pour contourner ces difficultés, les chercheuses et chercheurs du DEDIS ont étudié une catégorie d’algorithmes de consensus rarement utilisée, que l’on appelle «protocoles de consensus asynchrones». Contrairement aux protocoles actuels basés sur des chefs de file, leurs homologues asynchrones ne sont pas vulnérables aux défaillances de chef de file ni aux attaques par déni de service. Mais il y a une contrepartie importante: les protocoles asynchrones antérieurs sont beaucoup moins efficaces dans des conditions normales, et c’est l’une des raisons pour lesquelles ils ne sont pratiquement jamais déployés.
Selon Bryan Ford, leur protocole QuePaxa change pour la première fois cette dynamique. «Nous avons trouvé une solution avantageuse. La nouveauté et l’originalité de QuePaxa résident dans le fait qu’il s’agit d’un protocole de consensus asynchrone qui atteint enfin, dans des conditions de réseau normales, une efficacité équivalente à celle des protocoles basés sur des chefs de file, largement déployés. QuePaxa est aussi rapide, efficace, à faible latence et à faible coût en termes de bande passante du réseau, dans des conditions normales.»
Le nouvel algorithme est conçu de manière à ce qu’un seul chef de file à la fois mène la tâche de progression, mais un deuxième chef de file peut intervenir pour apporter son aide dans le même cycle sans interférer avec le premier chef de file. Un troisième peut même se joindre aux deux autres pour les aider à terminer le travail plus rapidement. Il y a une certaine redondance des efforts, mais les nœuds qui ne sont pas chefs de file n’interfèrent pas de manière destructive. Les délais courts n’entraînent pas l’annulation des tâches d’un chef de file par d’autres chefs de file, comme c’est le cas avec les protocoles actuels.
Un autre avantage de QuePaxa est qu’il est extrêmement robuste dans des conditions difficiles telles que des réseaux bruyants, des délais de communication importants, des délais de réseau variant de manière imprévisible ou des attaques délibérées par déni de service.
«Dans ces conditions, les protocoles de consensus existants disparaîtront complètement. QuePaxa continuera à fonctionner car il est beaucoup plus robuste», poursuit-il. «Dans tous les cas où les performances, la fiabilité ou la vulnérabilité à ce type d’attaque suscitent de vives inquiétudes, je pense qu’il s’agit d’une solution révolutionnaire en raison de sa robustesse. QuePaxa est appelé à devenir le nouveau protocole de consensus standard.»
L’équipe DEDIS a déjà créé un prototype open source de QuePaxa, qui est disponible sur le célèbre dépôt GitHub. Le nouveau protocole a déjà fait l’objet d’un processus d’évaluation des artefacts lors du SOSP, où des pairs examinateurs ont testé ses capacités.
L’article, intitulé QuePaxa: Escaping the tyranny of timeouts in consensus, sera présenté cette semaine à l’occasion du Symposium bisannuel sur les principes des systèmes d’exploitation (SOSP) organisé par l’Association for Computing Machinary (ACM), le premier forum mondial pour les chercheuses et chercheurs, les développeurs, les programmeurs et les enseignantes et enseignants de la technologie des systèmes informatiques.