问题标签 [paxos]

我已经阅读了 Lamport关于 Paxos的论文。我还听说，出于性能原因，它在实践中的使用并不多。分布式系统中共识常用的算法有哪些？

我正在研究 Paxos，我对算法在这个人为的例子中应该如何表现感到困惑。我希望下图能解释这个场景。

几点：

• 每个代理都充当提议者/接受者/学习者
• 准备消息有形式(instance, proposal_num)
• 提议消息有形式(instance, proposal_num, proposal_val)
• Server1 和 Server2 都决定同时启动提案流程
• 在开始时，消息 M1、M2 和 M3 同时出现

这里似乎虽然协议是“正确的”，即只S2选择了一个值，但 Server1 和 Server2 认为选择它是因为不同的提案编号。

Decide(...)Paxos 算法是否仅在消息发送给学习者时才终止？我一定是误解了Paxos Made Simple，但我认为选择是在提议者达到他们的Propose(...)消息的法定人数的那一刻做出的。

Decide(...)如果仅在将消息发送给代理后才做出选择，那么 Server2 是否应该Decide(1, 5, S2)在它恢复时终止其发送，因为它看到了较晚的消息Prepare(1, 7)？

我正在使用Wikipedia中提供的文档在集群模拟器应用程序中实现 Paxos 。不幸的是，它为解释留下了几扇大门，并且没有提供关于关键实施问题的太多信息。它不清楚和不完整。

• 假设一个集群分为 3 个区域，每个区域包含 3 个节点（总共 = 9 个节点）。如果区域之间的通信中断会发生什么？任何领导者都无法达到法定人数（即 5）。

Paxos不是要进入死循环了吗？如果一个人不能与至少一个法定人数的节点通信，我想一个人不应该启动 Paxos。

• 在阶段 1b：'如果提案编号 N 大于任何先前的提案，则每个 Acceptor 承诺不接受小于 N 的提案，并将它最后接受的值发送给Proposer。

“它接受的最后一个值”是什么？提案人之前是否有任何提案编号？在这种情况下，“实例”到底指的是什么？

• 在阶段 1a：是否包含与 Prepare 消息达成一致的值，还是推迟到 Accept！信息？或者这很重要？

• 在阶段 2a：'如果任何 Acceptor 已经接受了一个值，领导者必须选择一个具有最大提案编号 N的值'。

这里的价值是什么？是提案号吗？我不相信，但这句话不清楚。

• 在阶段 2a：“否则，Proposer 可以自由选择任何值”。这是什么意思？有什么价值？对于提案编号？

• Paxos 似乎依赖于不断增加的 N（提案编号）值来工作？这个对吗？

• 维基百科条目没有讨论节点在开始参与 Paxos 之前应该设置的初始值。这些是什么？

PS：我没有足够的声誉来创建“Paxos”标签（任何志愿者？）

在 Multi-Paxos 算法中，从接受者的角度考虑这个消息流：

接收：准备（N）

回复：承诺（N，空）

接收：接受！（N，V1）

回复：接受（N，V1）

接收：接受！（N+1，V2）

回复： ？

根据协议，在这种情况下，接受者的反应应该是什么？它应该回复 Accepted(N+1, V2)，还是应该忽略第二个 Accept！？

我相信当第二个提议者上线并相信他是（并且一直是）领导者时，这种情况可能会发生在 Multi-Paxos 中，因此他在没有准备的情况下发送了他的接受。或者，如果他的 Prepare 根本没有到达接受者。如果这种情况可能不会发生，你能解释一下原因吗？

有人能给我一份 Paxos 的真实用例列表吗？这是真正的问题，需要将共识作为更大问题的一部分。

以下是 Paxos 的用例吗？

假设有两个客户端在扑克服务器上互相玩扑克。扑克服务器被复制。我对 Paxos 的理解是，它可以用来保持代表当前扑克牌的内存数据结构的一致性。也就是说，确保所有副本都具有完全相同的内存状态。

但是为什么需要 Paxos？假设需要发一张新牌。如果一切正常，运行相同代码的每个副本都会生成相同的卡。为什么客户端不能只从所有复制的服务器请求最新状态并选择出现最多的卡。因此，如果一台服务器出现错误，客户端仍然可以通过选择大多数来获得正确的状态。

基本上，我想实现以下算法并分析使用这些算法构建的系统在不同条件下的行为。

• 八卦协议
• 多个 paxos
• 一致的哈希

我的兴趣在于这些算法。我基本上是在寻找一种可以让我快速编写这些算法并深入理解这些算法的编程语言。

我应该选择哪种语言？Java、Scala、Erlang 或其他任何东西。

目前，我知道 Java 和 C++。

Paxos 算法在使用 2F + 1 个处理器时最多可以容忍 F 次失败。据我了解，该算法仅适用于固定数量的处理器。是否可以在动态环境中使用该算法，可以动态添加和删除节点？

我在下面粘贴了 paxos 算法的伪代码，想知道是否有人能指出我正确的方向。我正在尝试实现下面的算法，但我对下面的“视图”到底代表什么感到困惑。我知道评论说它是“过去视图数字到值的映射”，但是如果有人可以向我解释这些“值”到底是什么以及“视图数字”是什么。

有人可以给我一个真实的例子，说明 Paxos 算法是如何在分布式数据库中使用的吗？我已经阅读了很多关于 Paxos 的论文来解释该算法，但没有一篇真正用一个实际的例子来解释。

一个简单的例子可以是一个银行应用程序，其中一个帐户正在通过多个会话进行修改（即在柜员处存款、借记操作等）。Paxos 是用来决定哪个操作先发生的吗？另外，Paxos 协议的多个实例是什么意思？这个什么时候用？基本上，我试图通过一个具体的例子而不是抽象的术语来理解这一切。

I have pasted pseudocode for a paxos algorithm here:

What is a "view" in the Paxos consensus algorithm?

and was wondering if someone could point me in the right direction.

The algorithm says that each node has a "state" which contains a bunch of information the node should keep track of.

Suppose we have two nodes: Node #1 and Node #2. In the simplest case Node #2 joins Node #1 and they both play paxos. What exactly happens to the states of Node #1 and Node #2 after 2 joins 1? When does the "views" data structure change and what does it contain? If someone can explain to me this simple case of two nodes playing paxos, then I think I can figure out multiple node case.

My current understanding (which I'm pretty sure is not correct) is as follows:

1. Node #2 sends a message to join Node #1.
2. Node #1 receives message from Node #2 asking to join.
3. Node #1 assumes leadership and kicks into phase 1, computes my_num = max(0,0) + 1 = 1
4. Node #1 sends all nodes in views[0] (which is empty) prepare(1,1)
5. Node #1 sends initial contact node (Node #2) prepare(1,1)
6. Node #1 sends Node #1 (itself) prepare(1,1)
7. Node #2 receives prepare(1,1). It sets its num_h=1 and returns to leader PROMISE(0,{empty list})
8. Node #1 receives prepare(1,1) and sets its num_h=1 and returns itself PROMISE(0,{empty list}).

now we get to phase 2

This is where I am quite confused.

Node #1 is the leader and it receives two PROMISE(0,{empty list}) messages. According to the algorithm, if the leader gets a majority of promises in views[0] then it can set a value for "v" and send the ACCEPT message to all responders.

What I am confused about is currently the views[0] for the leader is empty so how can you compute the majority of an empty list?

Also, let's assume the leader has received a majority of promises and proceeds to set v = set of pingable nodes (including self). What exactly are pingable nodes? Is it just Node #1 and Node #2?

Would appreciate all / any help and will definitely award points to those that help.