Questions sur la mise en œuvre Paxos

StackOverflow https://stackoverflow.com/questions/5850487

  •  27-10-2019
  •  | 
  •  

Question

Je suis en œuvre Paxos dans une application de simulation de cluster, en utilisant la documentation disponible dans Wikipedia . Malheureusement, il laisse plusieurs portes ouvertes à l'interprétation et ne fournit pas beaucoup d'informations sur les questions clés de mise en œuvre. On ne sait pas et incomplète.

  • En supposant un cluster divisé en 3 régions, chacune contenant 3 noeuds (total = 9 noeuds). Qu'advient-il si la communication est rompue entre les régions? Il n'y a aucun moyen tout dirigeant peut atteindre le quorum (qui est 5).

est-ce pas Paxos va entrer dans une boucle infinie? Je suppose qu'il ne faut pas lancer Paxos si l'on ne peut pas communiquer avec au moins un quorum de nœuds.

  • Dans la phase 1b: « Si le numéro de la proposition N est plus grand que toute proposition précédente, chaque promesse accepteurs ne pas accepter des propositions moins de N, et envoie la valeur qu'elle dernière a accepté cette instance pour le soumissionnaire .

Qu'est-ce que la dernière valeur, il a accepté? Est-il un numéro de proposition antérieure de l'auteur? Que signifie « exemple » se réfèrent exactement dans ce cas?

  • Dans la phase 1a: Doit-on inclure la valeur d'accord avec le message Préparer ou est-ce reporté à l'accepter! message? Ou cela importe?

  • Dans la phase 2a: « Si l'un des accepteurs ont déjà accepté une valeur, le moût leader Choisir une valeur avec le numéro de la proposition maximale N .

Quelle est la valeur ici? Est-ce le numéro de proposition? Je crois pas, mais cette phrase est peu claire.

  • Dans la phase 2a: «Dans le cas contraire, le soumissionnaire est libre de choisir toute valeur. Qu'est-ce que ça veut dire? Une valeur pour quoi? Pour le numéro de proposition?

  • Paxos semble se fonder sur une valeur croissante de N (numéro de la proposition) au travail? Est-ce exact?

  • L'entrée de wikipedia ne discute pas les valeurs initiales d'un nœud doit paramétrées avant le lancement de participer à Paxos. Quelles sont ces?

P.S .: Je n'ai pas assez réputation pour créer une étiquette 'Paxos' (tout bénévole?)

Était-ce utile?

La solution

Qu'est-ce qu'un exemple?

La nomenclature Paxos est un peu unintuitive.

  • instance est l'algorithme pour choisir un valeur.
  • round fait référence à une seule tentative de proposeur d'une phase 1 + phase 2. Un nœud peut avoir plusieurs tours dans un par exemple de Paxos. Une carte d'identité est ronde globaly unique par exemple sur tous les nœuds. Cela est parfois appelé numéro de proposition .
  • Un nœud peut prendre plusieurs rôles; notamment et accepteurs proposant. Dans mes réponses, je suppose que chaque nœud prend les deux rôles.
  • Phase 1 est également connu comme la phase Préparer.
    • Dans la phase 1a, un envoie un message proposant Préparer! (RoundId) aux accepteurs
    • Dans la phase 1b, les accepteurs répondre soit avec promesse! (RoundId, valeur) ou PrepareNack! ()
    • est également connu
  • Phase 2 comme phase Accepter.
    • Dans la phase 2a, un envoie un message proposant au accepteurs Encaisser! (RoundId, valeur)
    • Dans la phase 2b, les accepteurs réponse soit acceptée! (...) ou AcceptNack! ()

En supposant un cluster divisé en 3 régions, chacune contenant 3 noeuds (total = 9 noeuds). Qu'advient-il si la communication est rompue entre les régions? Il n'y a aucun moyen tout dirigeant peut atteindre le quorum (qui est 5).

Paxos exige que vous pouvez obtenir au moins le quorum (5 noeuds dans votre cas). Allez avec votre solution de trois régions; ayant deux partitions de réseau entre les trois régions est très mauvaises nouvelles. Je l'utilise aussi une version de Paxos qui peut modifier l'appartenance de noeud d'une instance à l'autre. Ceci est utile pour les partitions et défaillance d'un nœud.

est-ce pas Paxos va entrer dans une boucle infinie?

Une mise en œuvre naïve de Paxos n'est pas garanti de mettre fin, car plusieurs nœuds peuvent sauter-grenouille Préparer les phases. Il y a deux façons de contourner cela. L'un est d'avoir un backoff aléatoire avant de commencer une nouvelle phase Préparer. La seconde est d'acheminer toutes les demandes à un chef de file désigné, qui agit comme proposeur (Le chef est choisi par une instance Paxos. Voir aussi Multi-Paxos)

Dans la phase 1b: « Si le numéro de la proposition N est plus grand que toute proposition précédente, chaque >> Acceptor promet de ne pas accepter des propositions moins de N, et envoie la valeur acceptée pour ce dernier >> cette instance de la motion » .

Qu'est-ce que la dernière valeur, il a accepté? Est-il un numéro de proposition antérieure du proposeur?

Quand un nœud reçoit un (message en raison d'un Préparez! (HigherRoundId)) Accepter! (RoundId, valeur) message d'un proposant et il n'a pas promis de ne pas accepter la valeur, il stocke la valeur et la roundId (je vais les appeler acceptedValue et acceptedRoundId). Il peut écrire sur ces messages en raison de la suite Accepter! (...).

Quand un nœud reçoit un message d'un Préparez proposant! (RoundId), il stocke roundId comme promiseRoundId = max(roundId, promiseRoundId). Il envoie ensuite un retour de Promise!(acceptedRoundId, acceptedValue) au proposantes. NB:. Si un nœud n'a pas reçu un message Accepter (...), il répond avec Promise!(null, null)

Dans la phase 1a: Doit-on inclure la valeur d'accord avec le message Préparer ou est-ce reporté à l'accepter! message? Ou cela importe?

Il n'y a pas besoin de l'envoyer. Je ne sais pas.

Dans la phase 2a:. « Si l'un des accepteurs ont déjà accepté une valeur, le leader doit choisir une valeur avec le numéro de la proposition maximale N »

Quelle est la valeur ici? Est-ce le numéro de proposition? Je crois pas, mais cette phrase est peu claire.

La valeur est les données réelles de l'algorithme atteint un consensus sur. Je vais reformuler cela

Pour commencer la phase Accept, le proposant doit choisir une valeur à être acceptée en fonction des résultats de la phase Préparer. Si seulementAccepteurs a répondu avec la promesse (roundId, valeur), la doit utiliser la proposant valeur associée à la plus haute roundId. Dans le cas contraire, la seule promesse reçue proposant (null, null), et peut choisir une valeur d'envoyer aux accepteurs.

NB:. Le numéro de proposition ici est la même chose que roundId

Dans la phase 2a: «Dans le cas contraire, le soumissionnaire est libre de choisir toute valeur. Qu'est-ce que ça veut dire? Une valeur pour quoi? Pour le numéro de proposition?

Ceci est la valeur que vous voulez avoir un consensus sur. Cela est généralement un changement d'état à travers le système distribué, peut-être déclenchée par une demande du client.

Paxos semble se fonder sur une valeur croissante de N (numéro proposition) au travail? Est-ce exact?

L'entrée de wikipedia ne discute pas les valeurs initiales d'un nœud doit paramétrées avant le lancement de participer à Paxos. Quelles sont ces?

ids ronde (alias numéros proposition) devrait augmenterons et doivent être unique par exemple sur tous les nœuds. Le document Paxos suppose que vous pouvez le faire, car il est trivial d'atteindre. Voici un schéma qui produit les mêmes résultats sur tous les nœuds:

  1. Say il y a des nœuds M qui participent à une instance de Paxos.
  2. Trier tous les nœuds lexicographique. index [noeud] est l'indice d'un nœud dans cette liste triée.
  3. roundId = i*M + index[node] où i est le i-ième tour ce noeud commence (à savoir i est unique pour chaque noeud par paxos exemple, et est de façon monotone croissante).

Ou en pseudo-code (qui manque clairement quelques optimisations majeures): 

define runPaxos( allNodesThisPaxosInstance, myValue ) {
    allNodesThisPaxosInstance.sort()
    offset = allNodesThisPaxosInstance.indexOf( thisNode )
    for (i = 0; true; i++) {
        roundId = offset + i * allNodesThisPaxosInstance.size()
        prepareResult = doPreparePhase( roundId )

        if (!prepareResult.shouldContinue?)
            return

        if (prepareResult.hasAnyValue?)
           chosenValue = prepareResult.valueWithHighestRoundId
        else
            chosenValue = myValue

        acceptResult = doAcceptPhase( roundId, chosenValue )

        if (!acceptResult.shouldContinue?)
            return
    }
}

Autres conseils

J'ai trouvé le document suivant expliquer Paxos dans plus de détails. Je l'ai mis à jour l'entrée de wikipedia en conséquence.

Les réponses à ma question que je pourrais trouver sont:

est-ce pas Paxos va entrer dans un infini boucle?

Paxos ne fonctionne que si au moins un quorum de noeuds peuvent communiquer entre eux (dans notre cas 5). Par conséquent, si un noeud ne peut pas communiquer avec au moins un quorum de nœuds, il ne faut pas essayer de Paxos.

Quelle est la dernière valeur qu'il accepte?

Il est le dernier numéro de proposition acceptée et la valeur correspondante.

Qu'est-ce que « par exemple » se réfèrent exactement dans ce cas?

Il se réfère à l'accepteur.

Doit-on inclure la valeur d'accord sur avec PREPARE message ou est ce reporté à l'accepter! message? ou qui importe?

La valeur ne figure pas dans le message Préparer, il est laissé à l'accepter les messages.

Quelle est la valeur ici? Est-ce la proposition nombre? Je crois pas, mais cette phrase ne sait pas.

«Dans le cas contraire, le libre initiateur est choisissez une valeur. Qu'est-ce que cela signifier? Une valeur pour quoi? Pour le numéro de proposition?

Si accepteurs ont déjà accepté une proposition de l'auteur, ils peuvent retourner le numéro de la proposition correspondante et la valeur, rien d'autre.

La deuxième question tombe, depuis l'entrée Wikipedia était trompeuse. On peut choisir une valeur arbitraire pour une proposition donnée ou dériver des valeurs correspondant aux propositions acceptées précédemment.

Paxos semble se fonder sur une valeur croissante de N (numéro proposition) au travail? Est-ce exact?

Oui. A p besoins proposeur à nombre de ses propositions de plus en plus.

L'entrée de wikipedia ne discute pas les valeurs initiales d'un nœud doit paramétrées avant le lancement de participer à Paxos. Quelles sont ces?

Les nœuds devraient conserver leur dernier numéro de proposition acceptée et éventuellement, la valeur correspondante aussi. Ils devraient persister il. Lors de la connexion pour la première fois, le numéro de proposition initiale pour un auteur donné doit être nul (ou tout équivalent). 

Paxos seems to rely on an increasing value of N (proposal number) to work? Is this correct?

Chaque proposeur a un stockage stable. Chaque auteur se souvient (dans le stockage stable) la proposition numéro le plus élevé, il a essayé de problème, et commence la phase 1 avec un certain nombre de propositions plus élevé que tout a déjà utilisé.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top