{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Le chat de Schr\u00f6dinger sans bo\u00eete : le probl\u00e8me du consensus dans les syst\u00e8mes r\u00e9partis","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Imaginons. Cinq chats sont enferm\u00e9s dans une pi\u00e8ce, et pour aller r\u00e9veiller leur ma\u00eetre, ils doivent tous s'accorder ensemble pour cela, car ils ne peuvent ouvrir la porte qu'en se poussant mutuellement. Si l'un des chats est le chat de Schr\u00f6dinger, et que les autres ne connaissent pas sa d\u00e9cision, la question se pose : \u00ab Comment peuvent-ils faire cela ? \u00bb <\/p>\n

Dans cet article, je vais vous expliquer simplement la composante th\u00e9orique du monde des syst\u00e8mes distribu\u00e9s et le principe de leur fonctionnement. Je vais \u00e9galement aborder bri\u00e8vement l'id\u00e9e principale qui sous-tend Paxos. <\/p>\n

\"Le
\n<\/a><\/noindex>
\nLorsque les d\u00e9veloppeurs utilisent des infrastructures cloud, divers syst\u00e8mes de gestion de bases de donn\u00e9es, et qu'ils travaillent dans des clusters avec un grand nombre de n\u0153uds, ils sont convaincus que les donn\u00e9es seront int\u00e9grales, s\u00e9curis\u00e9es et toujours accessibles. Mais d'o\u00f9 viennent ces garanties ?<\/p>\n

En fait, les garanties que nous avons viennent du fournisseur. Elles sont d\u00e9crites dans la documentation \u00e0 peu pr\u00e8s comme suit : \u00ab Ce service est suffisamment fiable, il a un SLA d\u00e9fini, ne vous inqui\u00e9tez pas, tout fonctionnera de mani\u00e8re distribu\u00e9e comme vous l'attendez. \u00bb <\/p>\n

Nous avons tendance \u00e0 croire au meilleur, car des personnes intelligentes de grandes entreprises nous ont assur\u00e9 que tout ira bien. Nous ne nous posons pas la question : pourquoi cela peut-il fonctionner ? Existe-t-il une justification formelle pour la validit\u00e9 de ces syst\u00e8mes ?<\/p>\n

R\u00e9cemment, je suis all\u00e9 \u00e0 une \u00e9cole de calculs distribu\u00e9s<\/a><\/noindex> et j'ai \u00e9t\u00e9 tr\u00e8s inspir\u00e9 par ce sujet. Les cours dans l'\u00e9cole ressemblaient plus \u00e0 des s\u00e9minaires d'analyse math\u00e9matique qu'\u00e0 autre chose li\u00e9 aux syst\u00e8mes informatiques. Mais c'est ainsi que, par le pass\u00e9, les algorithmes les plus importants que nous utilisons chaque jour ont \u00e9t\u00e9 prouv\u00e9s, sans m\u00eame que nous en ayons conscience. <\/p>\n

La plupart des syst\u00e8mes distribu\u00e9s modernes utilisent l'algorithme de consensus Paxos et ses diverses modifications. Le plus \u00e9tonnant, c'est que la justification et, en principe, la possibilit\u00e9 m\u00eame d'existence de cet algorithme peuvent \u00eatre prouv\u00e9es simplement avec un stylo et du papier. En pratique, cet algorithme est appliqu\u00e9 dans de grands syst\u00e8mes fonctionnant sur un nombre \u00e9norme de n\u0153uds dans le cloud. <\/p>\n

Une illustration l\u00e9g\u00e8re de ce dont nous allons parler ensuite : le probl\u00e8me des deux g\u00e9n\u00e9raux<\/b>Pour commencer, examinons le probl\u00e8me des deux g\u00e9n\u00e9raux<\/a><\/noindex>. <\/p>\n

Nous avons deux arm\u00e9es \u2013 l'arm\u00e9e rousse et l'arm\u00e9e blanche. Les troupes blanches sont bas\u00e9es dans la ville assi\u00e9g\u00e9e. Les troupes rousses, dirig\u00e9es par les g\u00e9n\u00e9raux A1 et A2, se situent de chaque c\u00f4t\u00e9 de la ville. La t\u00e2che des rousses est d'attaquer la ville blanche et de vaincre. Cependant, l'arm\u00e9e de chaque g\u00e9n\u00e9ral rousse est plus petite que celle des blancs.<\/p>\n

\"Le
\n
\nLes conditions de victoire pour les rousses : les deux g\u00e9n\u00e9raux doivent attaquer en m\u00eame temps pour avoir un avantage num\u00e9rique sur les blancs. Pour cela, les g\u00e9n\u00e9raux A1 et A2 doivent s'accorder entre eux. S'ils attaquent s\u00e9par\u00e9ment, les rousses perdront. <\/p>\n

Pour s'accorder, les g\u00e9n\u00e9raux A1 et A2 peuvent s'envoyer des messagers \u00e0 travers le territoire de la ville blanche. Un messager peut atteindre le g\u00e9n\u00e9ral alli\u00e9 avec succ\u00e8s ou \u00eatre intercept\u00e9 par l'ennemi. La question est : existe-t-il une s\u00e9quence de communications entre les g\u00e9n\u00e9raux rousses (s\u00e9quence d'envoi de messagers d'A1 \u00e0 A2 et inversement d'A2 \u00e0 A1), o\u00f9 ils vont s'accorder de mani\u00e8re certaine pour attaquer \u00e0 l'heure X. Ici, par garanties, on entend que les deux g\u00e9n\u00e9raux auront une confirmation claire que leur alli\u00e9 (l'autre g\u00e9n\u00e9ral) attaquera \u00e0 l'heure pr\u00e9vue X.<\/p>\n

Supposons qu'A1 envoie un messager \u00e0 A2 avec le message : \u00ab Attaquons aujourd'hui \u00e0 minuit ! \u00bb. Le g\u00e9n\u00e9ral A1 ne peut pas attaquer sans confirmation du g\u00e9n\u00e9ral A2. Si le messager d'A1 est arriv\u00e9, alors le g\u00e9n\u00e9ral A2 envoie une confirmation avec le message : \u00ab Oui, attaquons aujourd'hui les blancs \u00bb. Mais maintenant, le g\u00e9n\u00e9ral A2 ne sait pas si son messager est arriv\u00e9 ou non, il n'a pas de garanties que l'attaque sera synchronis\u00e9e. Maintenant, le g\u00e9n\u00e9ral A2 a de nouveau besoin de confirmation.<\/p>\n

Si l'on prolonge leur communication, on d\u00e9couvrira que peu importe le nombre de cycles d'\u00e9change de messages, il n'est pas possible de garantir que les deux g\u00e9n\u00e9raux soient inform\u00e9s que leurs messages ont \u00e9t\u00e9 re\u00e7us (\u00e0 condition que l'un des messagers puisse \u00eatre intercept\u00e9).<\/p>\n

La t\u00e2che des deux g\u00e9n\u00e9raux est une excellente illustration d'un syst\u00e8me distribu\u00e9 tr\u00e8s simple, o\u00f9 il y a deux n\u0153uds avec une communication peu fiable. Cela signifie que nous n'avons aucune garantie \u00e0 100 % qu'ils vont se synchroniser. Des probl\u00e8mes similaires \u00e0 une \u00e9chelle plus grande seront abord\u00e9s plus loin dans l'article.<\/p>\n

Introduisons le concept de syst\u00e8mes distribu\u00e9s.<\/h2>\n

\nUn syst\u00e8me distribu\u00e9 est un ensemble d'ordinateurs (que nous appellerons n\u0153uds) capables d'\u00e9changer des messages. Chaque n\u0153ud est une entit\u00e9 autonome. Un n\u0153ud peut traiter des t\u00e2ches de mani\u00e8re ind\u00e9pendante, mais pour interagir avec d'autres n\u0153uds, il doit envoyer et recevoir des messages. <\/p>\n

La fa\u00e7on dont les messages sont pr\u00e9cis\u00e9ment mis en \u0153uvre, quels protocoles sont utilis\u00e9s, ne nous int\u00e9resse pas dans ce contexte. Ce qui importe, c'est que les n\u0153uds d'un syst\u00e8me distribu\u00e9 peuvent \u00e9changer des donn\u00e9es entre eux par l'envoi de messages.<\/p>\n

La d\u00e9finition elle-m\u00eame semble assez simple, mais il est important de noter qu'un syst\u00e8me distribu\u00e9 poss\u00e8de plusieurs attributs qui seront cruciaux pour nous.<\/p>\n

Attributs des syst\u00e8mes distribu\u00e9s<\/h4>\n

<\/p>\n

    \n
  1. Concurrence<\/b> \u2013 la possibilit\u00e9 d'\u00e9v\u00e9nements simultan\u00e9s ou concurrents dans le syst\u00e8me. De plus, nous consid\u00e9rerons que les \u00e9v\u00e9nements qui se produisent sur deux n\u0153uds diff\u00e9rents sont potentiellement concurrents tant que nous n'avons pas d'ordre clair d'apparition de ces \u00e9v\u00e9nements. Et, en r\u00e8gle g\u00e9n\u00e9rale, nous n'en avons pas.<\/li>\n
  2. Absence d'horloges globales<\/b>. Nous n'avons pas d'ordre clair d'\u00e9v\u00e9nements en raison de l'absence d'horloges globales. Dans le monde ordinaire des humains, nous sommes habitu\u00e9s \u00e0 avoir des horloges et un temps absolu. Tout change quand il s'agit de syst\u00e8mes distribu\u00e9s. M\u00eame les horloges atomiques ultraprecises ont un d\u00e9rive, et il est possible que nous ne puissions pas dire quel \u00e9v\u00e9nement parmi deux s'est produit en premier. Donc, nous ne pouvons pas non plus compter sur le temps.<\/li>\n
  3. D\u00e9faillance ind\u00e9pendante des n\u0153uds du syst\u00e8me<\/b>. Il y a aussi un autre probl\u00e8me : quelque chose peut mal tourner simplement parce que nos n\u0153uds ne sont pas \u00e9ternels. Un disque dur peut tomber en panne, une machine virtuelle dans le cloud peut red\u00e9marrer, le r\u00e9seau peut vaciller et des messages peuvent \u00eatre perdus. De plus, il est possible que les n\u0153uds fonctionnent mais agissent contre le syst\u00e8me. Cette derni\u00e8re classe de probl\u00e8mes a m\u00eame re\u00e7u un nom distinct : le probl\u00e8me des g\u00e9n\u00e9raux byzantins<\/a><\/noindex>. L'exemple le plus populaire de syst\u00e8me distribu\u00e9 avec ce type de probl\u00e8me est la Blockchain. Mais aujourd'hui, nous n'allons pas examiner cette classe particuli\u00e8re de probl\u00e8mes. Nous nous int\u00e9resserons aux situations o\u00f9 un ou plusieurs n\u0153uds peuvent simplement tomber en panne.<\/li>\n
  4. Mod\u00e8les de communication (mod\u00e8les d'\u00e9change de messages) entre les n\u0153uds<\/b>. Nous avons d\u00e9j\u00e0 d\u00e9termin\u00e9 que les n\u0153uds communiquent par \u00e9change de messages. Il existe deux mod\u00e8les de communication par messages : synchrone et asynchrone.<\/li>\n<\/ol>\n

    <\/p>\n

    Mod\u00e8les de communication entre n\u0153uds dans les syst\u00e8mes distribu\u00e9s<\/h4>\n

    \nMod\u00e8le synchrone<\/b> \u2013 nous savons exactement qu'il existe un delta de temps connu au-del\u00e0 duquel un message est garanti de parvenir d'un n\u0153ud \u00e0 un autre. Si ce temps est \u00e9coul\u00e9 et que le message n'est pas arriv\u00e9, nous pouvons affirmer avec certitude que le n\u0153ud est en panne. Dans ce mod\u00e8le, nous avons un temps d'attente pr\u00e9dictible. <\/p>\n

    Mod\u00e8le asynchrone<\/b> \u2013 dans les mod\u00e8les asynchrones, nous consid\u00e9rons que le temps d'attente est fini, mais il n'existe pas de delta de temps apr\u00e8s lequel nous pouvons garantir qu'un n\u0153ud est en panne. C'est-\u00e0-dire que le temps d'attente d'un message d'un n\u0153ud peut \u00eatre ind\u00e9fini. C'est une d\u00e9finition importante, et nous en discuterons plus tard. <\/p>\n

    La notion de consensus dans les syst\u00e8mes distribu\u00e9s<\/h2>\n

    \nAvant de d\u00e9finir formellement la notion de consensus, consid\u00e9rons un exemple de situation o\u00f9 il est n\u00e9cessaire, \u00e0 savoir \u2013 R\u00e9plication de machine d'\u00e9tat<\/b>. <\/p>\n

    Nous avons un certain journal distribu\u00e9. Nous souhaitons qu'il soit coh\u00e9rent et contienne des donn\u00e9es identiques sur tous les n\u0153uds du syst\u00e8me distribu\u00e9. Lorsqu'un des n\u0153uds apprend une nouvelle valeur qu'il s'appr\u00eate \u00e0 enregistrer dans le journal, sa t\u00e2che est de proposer cette valeur \u00e0 tous les autres n\u0153uds afin que le journal soit mis \u00e0 jour sur tous les n\u0153uds et que le syst\u00e8me passe \u00e0 un nouvel \u00e9tat coh\u00e9rent. Dans ce cas, il est important que les n\u0153uds s'accordent entre eux : tous les n\u0153uds conviennent que la nouvelle valeur propos\u00e9e est correcte, tous les n\u0153uds acceptent cette valeur, et seulement dans ce cas, tous peuvent enregistrer la nouvelle valeur dans le journal. <\/p>\n

    En d'autres termes : aucun des n\u0153uds n'a contest\u00e9 le fait qu'il dispose d'informations plus r\u00e9centes, et que la valeur propos\u00e9e est incorrecte. L'accord entre les n\u0153uds et le consensus sur une valeur accept\u00e9e et correcte constitue le consensus dans un syst\u00e8me distribu\u00e9. Nous allons ensuite parler des algorithmes qui permettent \u00e0 un syst\u00e8me distribu\u00e9 d'atteindre le consensus de mani\u00e8re garantie.
    \n\"Le
    \nPlus formellement, nous pouvons d\u00e9finir l'algorithme d'atteinte du consensus (ou tout simplement l'algorithme de consensus) comme une fonction qui transforme un syst\u00e8me distribu\u00e9 d'un \u00e9tat A \u00e0 un \u00e9tat B. Cet \u00e9tat doit \u00eatre accept\u00e9 par tous les n\u0153uds, et tous les n\u0153uds doivent pouvoir le confirmer. Il s'av\u00e8re que cette t\u00e2che n'est pas aussi triviale qu'elle en a l'air au premier abord.<\/p>\n

    Propri\u00e9t\u00e9s de l'algorithme de consensus<\/h4>\n

    \nL'algorithme de consensus doit poss\u00e9der trois propri\u00e9t\u00e9s pour que le syst\u00e8me continue d'exister et progresse dans la transition d'un \u00e9tat \u00e0 un autre :<\/p>\n

      \n
    1. Accord <\/b> \u2013 tous les n\u0153uds fonctionnels doivent accepter la m\u00eame valeur (dans les articles, cette propri\u00e9t\u00e9 est \u00e9galement connue sous le nom de propri\u00e9t\u00e9 de s\u00e9curit\u00e9). Tous les n\u0153uds qui fonctionnent actuellement (qui ne sont pas en panne et qui n'ont pas perdu le contact avec les autres) doivent parvenir \u00e0 un accord et accepter une certaine valeur finale commune.\n

      Il est important de comprendre que les n\u0153uds dans le syst\u00e8me distribu\u00e9 que nous examinons souhaitent parvenir \u00e0 un accord. C'est-\u00e0-dire que nous parlons ici de syst\u00e8mes o\u00f9 quelque chose peut simplement \u00e9chouer (par exemple, un n\u0153ud peut \u00e9chouer), mais dans ce syst\u00e8me, il n'y a certainement pas de n\u0153uds qui travaillent intentionnellement contre les autres (la t\u00e2che des g\u00e9n\u00e9raux byzantins). Gr\u00e2ce \u00e0 cette propri\u00e9t\u00e9, le syst\u00e8me reste coh\u00e9rent.<\/li>\n

    2. Int\u00e9grit\u00e9 <\/b> \u2013 si tous les n\u0153uds fonctionnels proposent la m\u00eame valeur, v<\/b>alors chaque n\u0153ud fonctionnel doit accepter cette valeur. v<\/b>. <\/li>\n
    3. R\u00e9solution <\/b>\u2013 tous les n\u0153uds fonctionnels doivent finalement accepter une certaine valeur (propri\u00e9t\u00e9 de vivacit\u00e9), ce qui permet \u00e0 l\u2019algorithme d'avoir un progr\u00e8s dans le syst\u00e8me. Chaque n\u0153ud fonctionnel individuel doit t\u00f4t ou tard accepter la valeur finale et le confirmer : \u00ab Pour moi, cette valeur est vraie, j'accorde avec l'ensemble du syst\u00e8me \u00bb.<\/li>\n<\/ol>\n

      <\/p>\n

      Exemple de fonctionnement de l'algorithme de consensus<\/h4>\n

      \nBien que les propri\u00e9t\u00e9s de l'algorithme puissent ne pas \u00eatre compl\u00e8tement claires, illustrons par un exemple les \u00e9tapes par lesquelles passe le plus simple algorithme de consensus dans un syst\u00e8me avec un mod\u00e8le de communication synchrone, o\u00f9 tous les n\u0153uds fonctionnent comme pr\u00e9vu, les messages ne sont pas perdus et rien ne se casse (est-ce vraiment possible ?).<\/p>\n

        \n
      1. Tout commence par une demande de main et de c\u0153ur (Propose). Supposons qu'un client se connecte au n\u0153ud appel\u00e9 \u00ab N\u0153ud 1 \u00bb et commence une transaction en transmettant une nouvelle valeur au n\u0153ud \u2013 O. \u00c0 partir de ce moment, nous appellerons \u00ab N\u0153ud 1 \u00bb proposer<\/b>. En tant que proposer, \u00ab N\u0153ud 1 \u00bb doit maintenant informer tout le syst\u00e8me qu'il a de nouvelles donn\u00e9es et il envoie \u00e0 tous les autres n\u0153uds des messages : \u00ab Regardez ! J'ai re\u00e7u la valeur \u00ab O \u00bb, et je veux l'\u00e9crire ! Je demande \u00e0 ce que vous confirmiez que vous \u00e9crirez aussi \u00ab O \u00bb dans votre journal \u00bb.\n

        \"Le<\/li>\n

      2. La prochaine \u00e9tape est le vote pour la valeur propos\u00e9e (Voting). \u00c0 quoi cela sert-il ? Il se peut que d'autres n\u0153uds aient re\u00e7u des informations plus r\u00e9centes et qu'ils disposent de donn\u00e9es concernant cette m\u00eame transaction.\n

        \"Le
        \n
        \nLorsque le n\u0153ud \u00ab N\u0153ud 1 \u00bb envoie sa proposition, les autres n\u0153uds v\u00e9rifient dans leurs journaux les donn\u00e9es concernant cet \u00e9v\u00e9nement. S'il n'y a pas de contradictions, les n\u0153uds d\u00e9clarent : \u00ab Oui, je n'ai pas d'autres donn\u00e9es concernant cet \u00e9v\u00e9nement. La valeur \u00ab O \u00bb est l'information la plus r\u00e9cente que nous avons \u00bb. <\/p>\n

        Dans tous les autres cas, les n\u0153uds peuvent r\u00e9pondre \u00e0 \u00ab N\u0153ud 1 \u00bb : \u00ab \u00c9coute ! J'ai des informations plus r\u00e9centes sur cette transaction. Ce n'est pas \u00ab O \u00bb, mais quelque chose de mieux \u00bb.<\/p>\n

        \u00c0 l'\u00e9tape de vote, les n\u0153uds arrivent \u00e0 une d\u00e9cision : soit tous acceptent une seule valeur, soit l'un d'entre eux vote contre, indiquant qu'il a des donn\u00e9es plus r\u00e9centes. <\/li>\n

      3. Si le tour de vote se passe bien et que tout le monde est \u00ab pour \u00bb, alors le syst\u00e8me passe \u00e0 une nouvelle \u00e9tape \u2013 l'acceptation de la valeur (Accept). \u00ab N\u0153ud 1 \u00bb collecte toutes les r\u00e9ponses des autres n\u0153uds et annonce : \u00ab Tout le monde a accept\u00e9 la valeur \u00ab O \u00bb ! Maintenant, je d\u00e9clare officiellement que \u00ab O \u00bb est notre nouvelle valeur, unique pour tous ! \u00c9crivez-la dans votre petit livre, n'oubliez pas. Notez-la dans votre journal ! \u00bb\n

        \"Le<\/li>\n

      4. Les autres n\u0153uds envoient leur confirmation (Accepted), affirmant qu'ils ont not\u00e9 la valeur \u00ab O \u00bb, rien de nouveau n'\u00e9tant arriv\u00e9 entre-temps (une sorte de commit en deux phases). Apr\u00e8s cet \u00e9v\u00e9nement significatif, nous consid\u00e9rons que la transaction distribu\u00e9e a \u00e9t\u00e9 compl\u00e9t\u00e9e.
        \n \"Le <\/li>\n<\/ol>\n

        \nAinsi, l'algorithme de consensus dans le cas simple se compose de quatre \u00e9tapes : proposer, voter (voting), accepter (accept), confirmation d'acceptation (accepted).<\/p>\n

        Si \u00e0 une \u00e9tape nous n'avons pas pu parvenir \u00e0 un consensus, l'algorithme red\u00e9marre, en tenant compte des informations fournies par les n\u0153uds ayant refus\u00e9 de confirmer la valeur propos\u00e9e.<\/p>\n

        L'algorithme de consensus dans un syst\u00e8me asynchrone<\/h2>\n

        \nTout allait bien jusqu'\u00e0 pr\u00e9sent, car nous parlions d'un mod\u00e8le de communication synchrone. Mais nous savons tous que dans le monde moderne, nous avons pris l'habitude de fonctionner de mani\u00e8re asynchrone. Comment un algorithme similaire fonctionne-t-il dans un syst\u00e8me avec un mod\u00e8le de communication asynchrone, o\u00f9 l'on consid\u00e8re que le temps d'attente pour une r\u00e9ponse d'un n\u0153ud peut \u00eatre ind\u00e9fini (d'ailleurs, une d\u00e9faillance d'un n\u0153ud peut aussi \u00eatre consid\u00e9r\u00e9e comme un exemple o\u00f9 un n\u0153ud peut r\u00e9pondre ind\u00e9finiment). <\/p>\n

        Maintenant que nous savons comment l'algorithme de consensus fonctionne en principe, une question pour les lecteurs curieux qui sont arriv\u00e9s \u00e0 ce point : combien de n\u0153uds dans un syst\u00e8me de N n\u0153uds avec un mod\u00e8le de messages asynchrone peuvent tomber en panne pour que le syst\u00e8me puisse toujours atteindre un consensus ?<\/p><\/blockquote>\n

        \nLa bonne r\u00e9ponse et l'explication se trouvent sous le spoiler.<\/b>Bonne r\u00e9ponse : 0<\/b>. Si au moins un n\u0153ud dans un syst\u00e8me asynchrone tombe en panne, le syst\u00e8me ne pourra pas atteindre le consensus. Cette affirmation est prouv\u00e9e dans le c\u00e9l\u00e8bre th\u00e9or\u00e8me FLP (1985, Fischer, Lynch, Paterson, lien vers l'original \u00e0 la fin de l'article) : \u00ab L'impossibilit\u00e9 d'atteindre un consensus distribu\u00e9 en cas de panne d'au moins un n\u0153ud \u00bb.
        \n\"Le
        \nLes amis, alors nous avons un probl\u00e8me, nous avons l'habitude que tout soit asynchrone. Et l\u00e0, c'est compliqu\u00e9. Comment avancer ? <\/p>\n

        Nous venons de parler de th\u00e9orie, de math\u00e9matiques. Que signifie \u00ab le consensus ne peut pas \u00eatre atteint \u00bb, en traduisant du langage math\u00e9matique au n\u00f4tre \u2013 technique ? Cela signifie que \u00ab le consensus ne peut pas toujours \u00eatre atteint \u00bb, c'est-\u00e0-dire qu'il existe un cas o\u00f9 le consensus est inatteignable. Quel est donc ce cas ? <\/p>\n

        C'est justement la violation de la propri\u00e9t\u00e9 de vivacit\u00e9, d\u00e9crite ci-dessus. Nous n'avons pas de consensus commun, et le syst\u00e8me ne peut pas progresser (ne peut pas se terminer dans un temps fini) s'il n'y a pas de r\u00e9ponse de tous les n\u0153uds. Car dans un syst\u00e8me asynchrone, nous n'avons pas de temps de r\u00e9ponse pr\u00e9visible, et nous ne pouvons pas savoir si un n\u0153ud est tomb\u00e9 en panne ou simplement r\u00e9pond lentement.<\/p>\n

        Mais en pratique, nous pouvons trouver une solution. Supposons que notre algorithme puisse fonctionner longtemps en cas de pannes (peut potentiellement fonctionner ind\u00e9finiment). Mais dans la plupart des situations, lorsque la plupart des n\u0153uds fonctionnent correctement, nous aurons du progr\u00e8s dans le syst\u00e8me. <\/p>\n

        Dans la pratique, nous traitons des mod\u00e8les de communication partiellement synchrones. La partialit\u00e9 de la synchronisation est comprise ainsi : en g\u00e9n\u00e9ral, nous avons un mod\u00e8le asynchrone, mais un concept formel de \u00ab temps de stabilisation global \u00bb est introduit \u00e0 un certain moment. <\/p>\n

        Ce moment peut ne pas arriver pendant une p\u00e9riode ind\u00e9finie, mais un jour, il doit se r\u00e9aliser. Une alarme virtuelle sonnera, et \u00e0 partir de ce moment, nous pouvons pr\u00e9dire le d\u00e9lai pendant lequel les messages arriveront. \u00c0 partir de ce point, le syst\u00e8me passe d'asynchrone \u00e0 synchrone. Dans la pratique, nous avons affaire \u00e0 de tels syst\u00e8mes. <\/p>\n

        L'algorithme Paxos r\u00e9sout les probl\u00e8mes de consensus<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 c'est une famille d'algorithmes qui r\u00e9sout le probl\u00e8me du consensus pour les syst\u00e8mes partiellement synchrones, \u00e0 condition que certains n\u0153uds puissent tomber en panne. L'auteur de Paxos est Leslie Lamport<\/a><\/noindex>. Il a propos\u00e9 une preuve formelle de l'existence et de la validit\u00e9 de l'algorithme en 1989. <\/p>\n

        Mais la preuve s'est av\u00e9r\u00e9e tout sauf triviale. La premi\u00e8re publication a \u00e9t\u00e9 publi\u00e9e seulement en 1998 (33 pages) avec une description de l'algorithme. Comme il s'est av\u00e9r\u00e9, elle \u00e9tait extr\u00eamement difficile \u00e0 comprendre, et en 2001, un document explicatif a \u00e9t\u00e9 publi\u00e9, qui a occup\u00e9 14 pages. Les volumes des publications sont mentionn\u00e9s pour montrer que le probl\u00e8me du consensus n'est pas simple, et qu'un travail \u00e9norme de certaines des plus brillantes personnes est n\u00e9cessaire pour de tels algorithmes.<\/p>\n

        Il est int\u00e9ressant de noter que Leslie Lamport lui-m\u00eame a remarqu\u00e9 dans sa conf\u00e9rence que dans le second article explicatif, il y a une affirmation, une ligne (sans pr\u00e9ciser laquelle), qui peut \u00eatre interpr\u00e9t\u00e9e de diff\u00e9rentes mani\u00e8res. En raison de cela, de nombreuses mises en \u0153uvre modernes de Paxos ne fonctionnent pas tout \u00e0 fait correctement. <\/p><\/blockquote>\n

        \nUne analyse d\u00e9taill\u00e9e du fonctionnement de Paxos n\u00e9cessiterait plusieurs articles, donc je vais essayer de transmettre tr\u00e8s bri\u00e8vement l'id\u00e9e principale de l'algorithme. Dans les liens \u00e0 la fin de mon article, vous trouverez des mat\u00e9riaux pour approfondir ce sujet.<\/p>\n

        R\u00f4les dans Paxos<\/h4>\n

        \nDans l'algorithme Paxos, il existe un concept de r\u00f4les. Consid\u00e9rons trois principaux (il existe des modifications avec des r\u00f4les suppl\u00e9mentaires) :<\/p>\n

          \n
        1. Proposers (d'autres termes peuvent \u00e9galement \u00eatre rencontr\u00e9s : leaders ou coordinateurs)<\/b>. Ce sont des gars qui apprennent une nouvelle valeur d'un utilisateur et prennent le r\u00f4le de leader. Leur t\u00e2che est de lancer un round de proposition d'une nouvelle valeur et de coordonner les actions ult\u00e9rieures des n\u0153uds. De plus, Paxos permet la pr\u00e9sence de plusieurs leaders dans certaines situations.<\/li>\n
        2. Accepteurs (Voteurs)<\/b>. Ce sont des n\u0153uds qui votent pour l'acceptation ou le rejet d'une certaine valeur. Leur r\u00f4le est tr\u00e8s important, car c'est d'eux que d\u00e9pend la d\u00e9cision : dans quel \u00e9tat le syst\u00e8me va basculer (ou ne pas basculer) apr\u00e8s chaque \u00e9tape de l'algorithme de consensus.<\/li>\n
        3. Apprenants<\/b>. Ce sont des n\u0153uds qui acceptent simplement et enregistrent la nouvelle valeur accept\u00e9e lorsque l'\u00e9tat du syst\u00e8me change. Ils ne prennent pas de d\u00e9cisions, ils re\u00e7oivent simplement des donn\u00e9es et peuvent les transmettre \u00e0 l'utilisateur final. <\/li>\n<\/ol>\n

          \nUn n\u0153ud peut combiner plusieurs r\u00f4les dans diff\u00e9rentes situations. <\/p>\n

          La notion de quorum<\/h4>\n

          \nNous supposons que nous avons un syst\u00e8me de N<\/b> n\u0153uds. Et parmi eux, au maximum F<\/b> n\u0153uds peuvent tomber en panne. Si F n\u0153uds tombent en panne, alors nous devons avoir dans le cluster, au minimum, 2F + 1<\/b> des n\u0153uds acceptateurs. <\/p>\n

          C'est n\u00e9cessaire pour que, m\u00eame dans la pire situation, les n\u0153uds \u00abbons\u00bb, fonctionnant correctement, aient la majorit\u00e9. Autrement dit, F + 1<\/b> n\u0153uds \u00abbons\u00bb qui se sont accord\u00e9s, et la valeur finale sera accept\u00e9e. Sinon, il pourrait y avoir une situation o\u00f9 diff\u00e9rents groupes locaux acceptent des valeurs diff\u00e9rentes et ne peuvent pas se mettre d'accord. C'est pourquoi nous avons besoin d'une majorit\u00e9 absolue pour gagner le vote.<\/p>\n

          L'id\u00e9e g\u00e9n\u00e9rale du fonctionnement de l'algorithme de consensus Paxos<\/h4>\n

          \nL'algorithme Paxos se compose de deux grandes phases, qui sont \u00e0 leur tour divis\u00e9es en deux \u00e9tapes chacune :<\/p>\n

            \n
          1. Phase 1a : Pr\u00e9parer<\/b>. Au stade de pr\u00e9paration, le leader (proposeur) informe tous les n\u0153uds : \u00ab Nous commen\u00e7ons une nouvelle phase de vote. Nous avons un nouveau tour. Le num\u00e9ro de ce tour est n. Nous allons maintenant commencer \u00e0 voter \u00bb. Pour l'instant, il se contentera d'annoncer le d\u00e9but d'un nouveau cycle sans communiquer de nouvelle valeur. L'objectif de cette phase est d'initier un nouveau tour et de communiquer \u00e0 tous son num\u00e9ro unique. Le num\u00e9ro du tour est important, il doit \u00eatre sup\u00e9rieur \u00e0 tous les num\u00e9ros de votes pr\u00e9c\u00e9dents de tous les anciens leaders. C'est gr\u00e2ce \u00e0 ce num\u00e9ro que les autres n\u0153uds du syst\u00e8me comprendront combien de donn\u00e9es r\u00e9centes le leader poss\u00e8de. Il est probable que d'autres n\u0153uds ont d\u00e9j\u00e0 des r\u00e9sultats de votes de tours beaucoup plus r\u00e9cents et ils informeront simplement le leader qu'il est \u00e0 la tra\u00eene.<\/li>\n
          2. Phase 1b : Promesse<\/b>. Lorsque les n\u0153uds acceptateurs re\u00e7oivent le num\u00e9ro d'une nouvelle phase de vote, deux issues sont possibles : \n