Avec des milliards d’ordinateurs qui se parlent quotidiennement, comment décident-ils quoi que ce soit ? Même dans un déploiement de base de données ou de serveur, comment les différents ordinateurs qui composent la base de données décident-ils des valeurs qui ont été validées ? Comment se mettent-ils d’accord sur l’heure qu’il est ? Comment parviennent-ils à un consensus ?
Mais d’abord, qu’est-ce que le concept de consensus dans le contexte des ordinateurs ? En résumé, il appartient à tous les agents concernés de s’accorder sur une valeur unique. Cependant, les allocations pour les agents dissidents, incorrects ou fautifs sont conçues dans le protocole. Chaque agent correct doit répondre, et tous les agents appropriés doivent avoir la même réponse. Ceci est particulièrement important pour les centres de données ou les réseaux maillés. Que se passe-t-il si le réseau est partitionné, si certains nœuds se déconnectent ou si le logiciel plante bizarrement, envoyant d’étranges données brouillées ? L’un des algorithmes de consensus les plus courants est Raft.
Radeau
The Secret Lives Of Data a une grande démonstration animée de la façon dont les données circulent à l’intérieur de l’algorithme Raft entre les agents. La page Raft GitHub contient également des diagrammes utiles. Le Raft a des garanties prouvables qui offrent une tolérance aux pannes par un dirigeant élu. Surtout, ce chef élu conduit à une faiblesse dans les échecs byzantins, mais nous en parlerons plus tard. Des bases de données telles que Cockroach DB, Splunk et MongoDB utilisent souvent Raft, qui est particulièrement adapté pour permettre aux agents de s’entendre sur un ensemble de transitions d’état, comme les transactions vers une base de données. Pour résumer l’algorithme Raft, il y a deux parties : l’élection du leader et la réplication du journal.
Imaginez un ensemble de serveurs communiquant entre eux et un client produisant des messages. Ces messages peuvent être n’importe quoi, comme « définir le registre Y sur 6 » ou « supprimer la ligne avec l’id = 1230231 ». Lorsque les serveurs apparaissent pour la première fois, ils sont dans un état de suiveur et cherchent à entendre un leader via un battement de cœur. Ils essaient de devenir candidats à une élection s’ils ne reçoivent pas de battement de cœur dans les 150 à 300 ms. Les serveurs votent ensuite sur les candidats, et dans le cas d’un vote partagé, le mandat électoral se termine et le cycle recommence. Les délais d’attente sont randomisés pour tenter d’éviter les votes divisés.
Le client envoie des messages au leader actuel, puis le leader réplique le message à tous les suiveurs. Une fois qu’il a reçu une réponse d’une majorité d’abonnés, le message est considéré comme engagé. Les messages sont ajoutés à un journal pour être cohérents sur tous les serveurs. En cas de défaillance d’un leader, les journaux du leader nouvellement élu sont utilisés et les entrées incohérentes sont supprimées. Étant donné que tout abonné doit disposer du journal engagé le plus à jour pour être pris en compte pour l’élection, cela garantit que les données engagées pour la majorité ne peuvent pas être perdues.
Échecs byzantins
Comme mentionné, Raft/Paxos protège contre les pannes de serveur, pas les pannes byzantines. Le nom vient du célèbre problème des généraux byzantins, où certains généraux ne sont pas fiables. Ils disent une chose mais en font une autre. Raft suppose que lorsqu’un système tombe en panne, il tombe en panne et redémarre. Ce n’est pas le cas au sens matériel, car l’appareil pourrait continuer à produire des données incohérentes, agir de manière incorrecte ou même être pris en charge par une entité hostile.
Néanmoins, de nombreux systèmes en temps réel, tels que ceux d’un avion ou d’un vaisseau spatial, doivent garder à l’esprit les échecs byzantins. Un composant peut générer des données erronées, et le reste des systèmes doit contourner cela. Cela peut être fait par des messages supplémentaires pour vérifier les actions d’autres serveurs, signer les données, ou même se débarrasser complètement de l’idée d’un leader.
Protocole Lockstep
Si vous avez joué à un jeu de stratégie en temps réel, vous vous demandez peut-être comment le jeu peut être cohérent entre des dizaines de joueurs avec des connexions incroyablement lentes. Malheureusement, la mise en réseau d’Age of Empires a été développée en 1996, alors qu’un modem 28.8 était relativement standard. Alors, comment pouvez-vous sérialiser la position et les mises à jour de chaque objet à l’écran lorsque vous avez quelques bits par seconde à perdre avec des sautes de latence réseau sauvages ? La réponse est que non.
Il y a un article fantastique sur le fait que 1500 archers courent en temps réel à partir de [Paul Bettner], qui a travaillé sur Age of Empires (entre autres). La réponse est uniquement d’envoyer les actions des joueurs plutôt que l’état de chaque objet dans le jeu. Chaque jeu exécute exactement la même simulation et les commandes de chaque joueur sont simulées sur l’ordinateur de chaque joueur. À bien des égards, cela ressemble au protocole Raft : les messages sont transmis et ajoutés à un journal en lecture seule, et le journal doit toujours être cohérent sur tous les ordinateurs. Mais contrairement à Raft, il n’y a pas de leader, et chaque serveur est aussi un client. Il y a un hôte, mais il n’y a pas une seule véritable autorité sur l’état du jeu.
Il existe un numéro de virage monotone qui est cohérent pour tous les clients. Chaque commande est prévue pour être exécutée en deux tours. Cela permet à la commande d’être envoyée, reconnue et traitée pendant la simulation du jeu. Cela signifie que la simulation ne peut fonctionner qu’à la vitesse de la machine la plus lente, et il existe un contrôleur de vitesse pour modifier la durée d’un tour afin de garder le jeu jouable. En séparant le temps de rendu du temps de rotation, le gameplay reste fluide pour le joueur, même si le taux de rotation est relativement faible.
Étant donné que chaque client exécute la même simulation, il est difficile de tricher (encore le problème byzantin). Tout client envoyant des messages déroutants ou dépourvus de sens a été désynchronisé et expulsé du jeu. Cependant, comme vous le pensez peut-être, obtenir une simulation avec un caractère aléatoire et des probabilités cohérentes sur des dizaines de machines avec des processeurs différents et potentiellement même des architectures différentes est pour le moins difficile.
Crypto
Chez Hackaday, nous avons tendance à nous concentrer sur le véritable côté minier de Bitcoin, mais comment le réseau s’accorde-t-il sur le prochain hachage ? C’est le véritable pouvoir de la preuve de travail. Il s’agit d’un algorithme de consensus distribué à grande échelle qui peut accueillir un grand pourcentage de mauvais acteurs. Nous n’entrerons pas dans les détails (peut-être un article pour une autre fois). En fin de compte, c’est le seul pouvoir de la blockchain et tout le battage médiatique qui va avec. C’est juste un journal d’entrées sur lequel nous pouvons tous nous mettre d’accord de manière décentralisée. Chia est une autre crypto-monnaie qui fonctionne sur un principe similaire mais utilise une preuve d’enjeu au lieu d’une preuve de travail mais a le même concept à la base.
Le consensus est partout
Le consensus est partout, des avions aux services Web en passant par les crypto-monnaies. En conséquence, il existe des centaines d’algorithmes de consensus, chacun avec des compromis et des profils de performances différents. Peut-être que la prochaine fois que vous implémenterez un projet IOT à l’échelle du maillage avec de nombreux nœuds qui doivent s’accorder sur des valeurs partagées, vous pourrez trouver certaines des idées ici.
