Alors imaginons. Il y a 5 chats enfermés dans la pièce, et pour aller réveiller le propriétaire, il faut qu'ils se mettent tous d'accord là-dessus entre eux, car ils ne peuvent ouvrir la porte qu'à cinq d'entre eux appuyés dessus. Si l'un des chats est le chat de Schrödinger et que les autres chats ne connaissent pas sa décision, la question se pose : « Comment peuvent-ils faire cela ?
Dans cet article, je vais vous parler en termes simples de la composante théorique du monde des systèmes distribués et des principes de leur fonctionnement. J’examinerai également superficiellement l’idée principale qui sous-tend Paxos.
Lorsque les développeurs utilisent des infrastructures cloud, diverses bases de données et travaillent dans des clusters constitués d'un grand nombre de nœuds, ils sont sûrs que les données seront complètes, sécurisées et toujours disponibles. Mais où sont les garanties ?
Pour l’essentiel, les garanties dont nous disposons sont des garanties fournisseurs. Ils sont décrits dans la documentation comme suit : "Ce service est assez fiable, il a un SLA donné, ne vous inquiétez pas, tout fonctionnera de manière distribuée comme prévu."
Nous avons tendance à croire au meilleur, car les hommes intelligents des grandes entreprises nous ont assuré que tout irait bien. Nous ne posons pas la question : pourquoi, en fait, cela peut-il fonctionner ? Existe-t-il une justification formelle au bon fonctionnement de tels systèmes ?
Je suis récemment allé à et j'ai été très inspiré par ce sujet. Les cours à l’école ressemblaient plus à des cours de calcul qu’à quelque chose lié aux systèmes informatiques. Mais c’est exactement ainsi qu’ont été éprouvés à un moment donné les algorithmes les plus importants que nous utilisons quotidiennement, sans même le savoir.
La plupart des systèmes distribués modernes utilisent l'algorithme de consensus Paxos et ses diverses modifications. Le plus cool, c'est que la validité et, en principe, la possibilité même de l'existence de cet algorithme peuvent être prouvées simplement avec un stylo et du papier. En pratique, l’algorithme est utilisé dans de grands systèmes fonctionnant sur un grand nombre de nœuds dans les nuages.
Une légère illustration de ce qui sera discuté ensuite : la tâche de deux générauxJetons un coup d'oeil pour un échauffement .
Nous avons deux armées : rouge et blanche. Les troupes blanches sont basées dans la ville assiégée. Les troupes rouges dirigées par les généraux A1 et A2 sont implantées des deux côtés de la ville. La tâche des rousses est d'attaquer la ville blanche et de gagner. Cependant, l’armée de chaque général rouge est plus petite que l’armée blanche.
Conditions de victoire pour les rouges : les deux généraux doivent attaquer en même temps afin d'avoir un avantage numérique sur les blancs. Pour ce faire, les généraux A1 et A2 doivent se mettre d’accord. Si tout le monde attaque séparément, les rousses perdront.
Pour parvenir à un accord, les généraux A1 et A2 peuvent s'envoyer des messagers à travers le territoire de la ville blanche. Le messager peut réussir à atteindre un général allié ou être intercepté par l'ennemi. Question : existe-t-il une telle séquence de communications entre les généraux aux cheveux roux (la séquence d'envoi de messagers de A1 à A2 et vice versa de A2 à A1), dans laquelle ils sont assurés de se mettre d'accord sur une attaque à l'heure X. Ici, les garanties signifient que les deux généraux auront la confirmation sans ambiguïté qu'un allié (un autre général) attaquera définitivement au moment fixé X.
Supposons que A1 envoie un messager à A2 avec le message : « Attaquons aujourd'hui à minuit ! » Le général A1 ne peut pas attaquer sans confirmation du général A2. Si le messager de A1 est arrivé, alors le général A2 envoie une confirmation avec le message : « Oui, tuons les blancs aujourd'hui ». Mais désormais le général A2 ne sait pas si son messager est arrivé ou non, il n'a aucune garantie si l'attaque sera simultanée. Maintenant, le général A2 a encore besoin de confirmation.
Si nous décrivons plus en détail leur communication, il devient clair que quel que soit le nombre de cycles d'échange de messages, il n'y a aucun moyen de garantir que les deux généraux ont reçu leurs messages (en supposant que l'un ou l'autre des messagers puisse être intercepté).
Le problème des deux généraux est une excellente illustration d’un système distribué très simple où se trouvent deux nœuds dont la communication n’est pas fiable. Cela signifie que nous n'avons pas une garantie à 100 % qu'ils soient synchronisés. Des problèmes similaires ne sont abordés qu’à une plus grande échelle plus loin dans l’article.
Nous introduisons le concept de systèmes distribués
Un système distribué est un groupe d'ordinateurs (ci-après nous les appellerons nœuds) qui peuvent échanger des messages. Chaque nœud individuel est une sorte d’entité autonome. Un nœud peut traiter des tâches seul, mais pour communiquer avec d'autres nœuds, il doit envoyer et recevoir des messages.
Comment exactement les messages sont implémentés, quels protocoles sont utilisés - cela ne nous intéresse pas dans ce contexte. Il est important que les nœuds d'un système distribué puissent échanger des données entre eux en envoyant des messages.
La définition elle-même n'a pas l'air très compliquée, mais nous devons tenir compte du fait qu'un système distribué possède un certain nombre d'attributs qui seront importants pour nous.
Attributs des systèmes distribués
- Concurrency – la possibilité que des événements simultanés ou concurrents se produisent dans le système. De plus, nous considérerons que les événements qui se produisent sur deux nœuds différents sont potentiellement concurrents tant que nous n’avons pas un ordre clair d’apparition de ces événements. Mais en règle générale, nous ne l’avons pas.
- Pas d'horloge globale. Nous n’avons pas d’ordre clair des événements en raison de l’absence d’horloge mondiale. Dans le monde ordinaire des gens, nous sommes habitués au fait que nous disposons d’horloges et d’heures absolues. Tout change lorsqu'il s'agit de systèmes distribués. Même les horloges atomiques ultra-précises dérivent, et il peut y avoir des situations dans lesquelles nous ne pouvons pas dire lequel des deux événements s'est produit en premier. Nous ne pouvons donc pas non plus compter sur le temps.
- Panne indépendante des nœuds du système. Il existe un autre problème : quelque chose peut mal tourner simplement parce que nos nœuds ne durent pas éternellement. Le disque dur peut tomber en panne, la machine virtuelle dans le cloud peut redémarrer, le réseau peut clignoter et les messages seront perdus. De plus, il peut y avoir des situations dans lesquelles les nœuds fonctionnent, mais en même temps vont à l'encontre du système. La dernière classe de problèmes a même reçu un nom distinct : problème . L’exemple le plus populaire de système distribué présentant ce problème est la Blockchain. Mais aujourd’hui, nous n’examinerons pas cette classe particulière de problèmes. Nous nous intéresserons aux situations dans lesquelles simplement un ou plusieurs nœuds peuvent échouer.
- Modèles de communication (modèles de messagerie) entre les nœuds. Nous avons déjà établi que les nœuds communiquent en échangeant des messages. Il existe deux modèles de messagerie bien connus : synchrone et asynchrone.
Modèles de communication entre nœuds dans les systèmes distribués
Modèle synchrone – nous savons avec certitude qu’il existe un delta de temps connu et fini pendant lequel un message est assuré de passer d’un nœud à un autre. Si ce délai est écoulé et que le message n'est pas arrivé, nous pouvons affirmer en toute sécurité que le nœud est en panne. Dans ce modèle, nous avons des temps d'attente prévisibles.
Modèle asynchrone – dans les modèles asynchrones, nous considérons que le temps d'attente est fini, mais il n'existe pas de delta de temps au-delà duquel nous pouvons garantir que le nœud est tombé en panne. Ceux. Le temps d'attente d'un message provenant d'un nœud peut être arbitrairement long. C'est une définition importante, et nous en reparlerons plus loin.
Le concept de consensus dans les systèmes distribués
Avant de définir formellement la notion de consensus, considérons un exemple de situation où nous en avons besoin, à savoir - Réplication de machine d'état.
Nous avons un journal distribué. Nous aimerions qu'il soit cohérent et contienne des données identiques sur tous les nœuds du système distribué. Lorsqu'un des nœuds apprend une nouvelle valeur qu'il va écrire dans le journal, sa tâche consiste à proposer cette valeur à tous les autres nœuds afin que le journal soit mis à jour sur tous les nœuds et que le système passe à un nouvel état cohérent. Dans ce cas, il est important que les nœuds soient d'accord entre eux : tous les nœuds conviennent que la nouvelle valeur proposée est correcte, tous les nœuds acceptent cette valeur, et ce n'est que dans ce cas que tout le monde peut écrire la nouvelle valeur dans le journal.
En d’autres termes : aucun des nœuds n’a objecté qu’il disposait d’informations plus pertinentes et la valeur proposée était incorrecte. L'accord entre les nœuds et l'accord sur une seule valeur acceptée correcte constituent un consensus dans un système distribué. Nous parlerons ensuite des algorithmes qui permettent de garantir qu'un système distribué parvienne à un consensus.
Plus formellement, nous pouvons définir un algorithme de consensus (ou simplement un algorithme de consensus) comme une certaine fonction qui transfère un système distribué de l'état A à l'état B. De plus, cet état est accepté par tous les nœuds, et tous les nœuds peuvent le confirmer. Il s’avère que cette tâche n’est pas du tout aussi anodine qu’il y paraît à première vue.
Propriétés de l'algorithme de consensus
L'algorithme de consensus doit avoir trois propriétés pour que le système continue d'exister et progresse dans son passage d'un état à l'autre :
- contrat – tous les nœuds fonctionnant correctement doivent prendre la même valeur (dans les articles, cette propriété est également appelée propriété de sécurité). Tous les nœuds qui fonctionnent actuellement (n’ont pas échoué ou n’ont pas perdu le contact avec les autres) doivent parvenir à un accord et accepter une valeur commune finale.
Il est important de comprendre ici que les nœuds du système distribué que nous envisageons veulent être d’accord. Autrement dit, nous parlons maintenant de systèmes dans lesquels quelque chose peut simplement échouer (par exemple, certains nœuds échouent), mais dans ce système, il n'y a certainement aucun nœud qui travaille délibérément contre les autres (la tâche des généraux byzantins). Grâce à cette propriété, le système reste cohérent.
- Intégrité — si tous les nœuds fonctionnant correctement offrent la même valeur v, ce qui signifie que chaque nœud fonctionnant correctement doit accepter cette valeur v.
- Termination – tous les nœuds fonctionnant correctement finiront par prendre une certaine valeur (propriété de vivacité), ce qui permet à l'algorithme de progresser dans le système. Chaque nœud qui fonctionne correctement doit tôt ou tard accepter la valeur finale et la confirmer : « Pour moi, cette valeur est vraie, je suis d'accord avec l'ensemble du système. »
Un exemple du fonctionnement de l'algorithme de consensus
Bien que les propriétés de l'algorithme ne soient pas tout à fait claires. Par conséquent, nous illustrerons par un exemple les étapes par lesquelles passe l'algorithme de consensus le plus simple dans un système avec un modèle de messagerie synchrone, dans lequel tous les nœuds fonctionnent comme prévu, les messages ne sont pas perdus et rien ne se casse (est-ce que cela arrive vraiment ?).
- Tout commence par une demande en mariage (Propose). Supposons qu'un client se connecte à un nœud appelé "Nœud 1" et démarre une transaction en transmettant une nouvelle valeur au nœud - O. Désormais, nous appellerons "Nœud 1" proposant. En tant que proposant, le « nœud 1 » doit désormais informer l'ensemble du système qu'il dispose de nouvelles données, et il envoie des messages à tous les autres nœuds : « Regardez ! Le sens « O » m’est venu et j’ai envie de l’écrire ! Veuillez confirmer que vous enregistrerez également « O » dans votre journal.
- L'étape suivante consiste à voter pour la valeur proposée (Vote). Pourquoi est-ce? Il peut arriver que d'autres nœuds aient reçu des informations plus récentes et disposent de données sur la même transaction.
Lorsque le nœud « Nœud 1 » envoie sa proposition, les autres nœuds vérifient dans leurs journaux les données sur cet événement. S'il n'y a pas de contradictions, les nœuds annoncent : « Oui, je n'ai pas d'autres données pour cet événement. La valeur « O » est la dernière information que nous méritons.Dans tous les autres cas, les nœuds peuvent répondre au « Nœud 1 » : « Écoutez ! J'ai des données plus récentes sur cette transaction. Pas 'O', mais quelque chose de mieux."
Lors de l'étape de vote, les nœuds prennent une décision : soit ils acceptent tous la même valeur, soit l'un d'eux vote contre, indiquant qu'il dispose de données plus récentes.
- Si le tour de vote est réussi et que tout le monde est en faveur, alors le système passe à une nouvelle étape : l'acceptation de la valeur. Le « Nœud 1 » collecte toutes les réponses des autres nœuds et rapporte : « Tout le monde était d'accord sur la valeur « O » ! Maintenant, je déclare officiellement que « O » est notre nouveau sens, le même pour tout le monde ! Notez-le dans votre petit livre, n’oubliez pas. Notez-le dans votre journal !
- Les nœuds restants envoient une confirmation (Accepté) qu'ils ont noté la valeur « O » ; rien de nouveau n'est arrivé pendant ce temps (une sorte de commit en deux phases). Après cet événement marquant, nous considérons que la transaction distribuée est terminée.
Ainsi, l'algorithme de consensus dans un cas simple se compose de quatre étapes : proposer, voter (voter), accepter (accepter), confirmer l'acceptation (accepté).
Si, à un moment donné, nous ne parvenons pas à un accord, l'algorithme recommence en tenant compte des informations fournies par les nœuds qui ont refusé de confirmer la valeur proposée.
Algorithme de consensus dans un système asynchrone
Avant cela, tout se passait bien, car nous parlions d'un modèle de messagerie synchrone. Mais nous savons que dans le monde moderne, nous sommes habitués à tout faire de manière asynchrone. Comment fonctionne un algorithme similaire dans un système avec un modèle de messagerie asynchrone, où nous pensons que le temps d'attente pour une réponse d'un nœud peut être arbitrairement long (d'ailleurs, la défaillance d'un nœud peut également être considérée comme un exemple lorsque un nœud peut répondre pendant une durée arbitrairement longue).
Maintenant que nous savons comment fonctionne en principe l'algorithme de consensus, une question pour les lecteurs curieux qui sont arrivés jusqu'ici : combien de nœuds dans un système de N nœuds avec un modèle de message asynchrone peuvent échouer pour que le système puisse toujours atteindre un consensus ?
La bonne réponse et la justification se trouvent derrière le spoiler.La bonne réponse est: 0. Si même un nœud d’un système asynchrone tombe en panne, le système ne pourra pas parvenir à un consensus. Cette affirmation est prouvée dans le théorème FLP, bien connu dans certains milieux (1985, Fischer, Lynch, Paterson, lien vers l'original en fin d'article) : « L'impossibilité d'atteindre un consensus distribué si au moins un nœud échoue .»
Les gars, alors nous avons un problème, nous sommes habitués à ce que tout soit asynchrone. Et le voici. Comment continuer à vivre ?
Nous parlions justement de théorie, de mathématiques. Que signifie « un consensus ne peut pas être atteint », traduit du langage mathématique dans le nôtre - celui de l'ingénierie ? Cela signifie que « cela ne peut pas toujours être réalisé », c'est-à-dire Il existe un cas dans lequel le consensus n’est pas réalisable. De quel genre de cas s'agit-il ?
C'est exactement la violation de la propriété de vivacité décrite ci-dessus. Nous n'avons pas d'accord commun et le système ne peut pas progresser (ne peut pas se terminer dans un temps fini) dans le cas où nous n'avons pas de réponse de tous les nœuds. Parce que dans un système asynchrone, nous n'avons pas de temps de réponse prévisible et nous ne pouvons pas savoir si un nœud est tombé en panne ou s'il met simplement beaucoup de temps à répondre.
Mais dans la pratique, nous pouvons trouver une solution. Que notre algorithme puisse fonctionner longtemps en cas de panne (il peut potentiellement fonctionner indéfiniment). Mais dans la plupart des situations, lorsque la plupart des nœuds fonctionnent correctement, nous progresserons dans le système.
En pratique, nous avons affaire à des modèles de communication partiellement synchrones. La synchronie partielle s'entend comme suit : dans le cas général, nous avons un modèle asynchrone, mais une certaine notion de « temps de stabilisation global » d'un certain instant est formellement introduite.
Ce moment ne se produira peut-être pas avant un certain temps, mais il devra arriver un jour. Le réveil virtuel sonnera et à partir de ce moment nous pourrons prédire le delta de temps pour lequel les messages arriveront. A partir de ce moment, le système passe d'asynchrone à synchrone. En pratique, nous avons précisément affaire à de tels systèmes.
L'algorithme Paxos résout les problèmes de consensus
est une famille d'algorithmes qui résolvent le problème du consensus pour les systèmes partiellement synchrones, sous réserve de la possibilité que certains nœuds échouent. L'auteur de Paxos est . Il a proposé une preuve formelle de l’existence et de l’exactitude de l’algorithme en 1989.
Mais la preuve s’est avérée loin d’être anodine. La première publication n'a été publiée qu'en 1998 (33 pages) décrivant l'algorithme. Il s'est avéré qu'il était extrêmement difficile à comprendre et, en 2001, une explication de l'article a été publiée, qui occupait 14 pages. Le volume des publications est donné afin de montrer qu'en réalité le problème du consensus n'est pas du tout simple et que derrière de tels algorithmes se cache une énorme quantité de travail de la part des personnes les plus intelligentes.
Il est intéressant de noter que Leslie Lamport lui-même a noté dans sa conférence que dans le deuxième article explicatif il y a une déclaration, une ligne (il n'a pas précisé laquelle), qui peut être interprétée de différentes manières. Et pour cette raison, un grand nombre d’implémentations Paxos modernes ne fonctionnent pas entièrement correctement.
Une analyse détaillée du travail de Paxos nécessiterait plus d’un article, je vais donc essayer de transmettre très brièvement l’idée principale de l’algorithme. Dans les liens à la fin de mon article, vous trouverez du matériel pour approfondir ce sujet.
Rôles chez Paxos
L'algorithme Paxos a un concept de rôles. Considérons trois principaux (il existe des modifications avec des rôles supplémentaires) :
- Proposants (les termes peuvent également être utilisés : leaders ou coordinateurs). Ce sont ces gars-là qui découvrent une nouvelle valeur auprès de l’utilisateur et assument le rôle de leader. Leur tâche est de lancer une série de propositions pour une nouvelle valeur et de coordonner les actions ultérieures des nœuds. De plus, Paxos permet la présence de plusieurs dirigeants dans certaines situations.
- Accepteurs (électeurs). Ce sont des nœuds qui votent pour accepter ou rejeter une valeur particulière. Leur rôle est très important, car la décision dépend d'eux : dans quel état le système ira (ou non) après la prochaine étape de l'algorithme de consensus.
- Apprenants. Des nœuds qui acceptent et écrivent simplement la nouvelle valeur acceptée lorsque l'état du système a changé. Ils ne prennent pas de décisions, ils reçoivent simplement les données et peuvent les transmettre à l'utilisateur final.
Un nœud peut combiner plusieurs rôles dans différentes situations.
La notion de quorum
Nous supposons que nous disposons d'un système de N nœuds Et parmi eux le maximum F les nœuds peuvent échouer. Si les nœuds F échouent, alors nous devons avoir au moins 2F+1 nœuds accepteurs.
Cela est nécessaire pour que nous ayons toujours la majorité, même dans la pire des situations, de « bons » nœuds qui fonctionnent correctement. C'est F+1 les "bons" nœuds qui ont accepté, et la valeur finale sera acceptée. Autrement, il pourrait y avoir une situation dans laquelle nos différents groupes locaux prendraient des significations différentes et ne parviendraient pas à s'entendre entre eux. Il nous faut donc une majorité absolue pour remporter le vote.
L'idée générale du fonctionnement de l'algorithme de consensus Paxos
L’algorithme Paxos implique deux grandes phases, elles-mêmes divisées en deux étapes chacune :
- Phase 1a : Préparer. Lors de la phase de préparation, le leader (proposant) informe tous les nœuds : « Nous commençons une nouvelle phase de vote. Nous avons un nouveau tour. Le numéro de ce tour est n. Maintenant, nous allons commencer à voter. » Pour l’instant, il signale simplement le début d’un nouveau cycle, mais ne signale pas de nouvelle valeur. La tâche de cette étape est de lancer un nouveau cycle et d'informer chacun de son numéro unique. Le nombre rond est important, il doit avoir une valeur supérieure à tous les nombres de votes précédents de tous les dirigeants précédents. Car c’est grâce au nombre rond que les autres nœuds du système comprendront à quel point les données du leader sont récentes. Il est probable que d'autres nœuds disposent déjà des résultats des votes de tours beaucoup plus ultérieurs et diront simplement au leader qu'il est en retard.
- Phase 1b : Promesse. Lorsque les nœuds accepteurs reçoivent le numéro de la nouvelle étape de vote, deux résultats sont possibles :
- Le nombre n du nouveau vote est supérieur au nombre de tout vote précédent auquel l'accepteur a participé. Ensuite, l'accepteur envoie une promesse au leader qu'il ne participera plus à aucun vote avec un nombre inférieur à n. Si l'accepteur a déjà voté pour quelque chose (c'est-à-dire qu'il a déjà accepté une certaine valeur dans la deuxième phase), alors il attache à sa promesse la valeur acceptée et le numéro du vote auquel il a participé.
- Sinon, si l’accepteur connaît déjà le vote portant le numéro le plus élevé, il peut simplement ignorer l’étape de préparation et ne pas répondre au leader.
- Phase 2a : Accepter. Le leader doit attendre une réponse du quorum (la majorité des nœuds du système) et, si le nombre requis de réponses est reçu, il a alors deux options pour le développement des événements :
- Certains accepteurs ont envoyé des valeurs pour lesquelles ils avaient déjà voté. Dans ce cas, le leader sélectionne la valeur du vote avec le nombre maximum. Appelons cette valeur x, et elle envoie un message à tous les nœuds comme : "Accepter (n, x)", où la première valeur est le numéro de vote de sa propre étape de proposition, et la deuxième valeur est ce pour quoi tout le monde s'est rassemblé, c'est à dire. la valeur pour laquelle nous votons réellement.
- Si aucun des acceptants n'a envoyé de valeurs, mais qu'ils ont simplement promis de voter à ce tour, le leader peut les inviter à voter pour leur valeur, la valeur pour laquelle il est devenu leader en premier lieu. Appelons-le y. Il envoie un message à tous les nœuds comme : « Accept (n, y) », similaire au résultat précédent.
- Phase 2b : Acceptée. De plus, les nœuds accepteurs, dès réception du message « Accepter(...) » du leader, sont d'accord avec celui-ci (envoient une confirmation à tous les nœuds qu'ils sont d'accord avec la nouvelle valeur) uniquement s'ils n'en ont pas promis (autres) ) leader pour participer au vote avec le numéro du tour n' > n, sinon ils ignorent la demande de confirmation.
Si la majorité des nœuds ont répondu au leader et que tous ont confirmé la nouvelle valeur, alors la nouvelle valeur est considérée comme acceptée. Hourra! Si la majorité n’est pas atteinte ou si certains nœuds refusent d’accepter la nouvelle valeur, alors tout recommence.
C'est ainsi que fonctionne l'algorithme Paxos. Chacune de ces étapes comporte de nombreuses subtilités, nous n'avons pratiquement pas pris en compte les différents types de pannes, les problèmes de plusieurs dirigeants et bien plus encore, mais le but de cet article est uniquement de présenter au lecteur le monde de l'informatique distribuée à un niveau élevé.
Il convient également de noter que Paxos n'est pas le seul du genre, il existe d'autres algorithmes, par exemple : , mais c'est un sujet pour un autre article.
Liens vers des documents pour une étude plus approfondie
Niveau DEBUTANT:
- , Preethi Kasireddy, article de blog sur Medium
- , Adi Kancherla, article de blog sur Medium
- , Ittaï Abraham, blog
- , Ittai Abraham, article de blog
Niveau de Leslie Lamport :
- , Fischer, Lynch et Paterson, document de recherche, 1985
- , Leslie Lamport, document de recherche, 1998
- , Leslie Lamport, document de recherche, 2001
Source: habr.com