约Paxos的一些问题

Question

我被弄得价值选择通过提案人。用 来举例说明。如果现在要保人要锁定文件，那么它会发送L1是processer_number，且v1的“锁定文件”的价值，受体接受它。 比提议者想要解锁文件，并且发送（l2> l1）v2是“解锁文件”的值，之后，接受者返回最后的值并且提议者选择它并且再次发送。

in这个例子中，V2失去了什么？或者这个例子中的真实过程是什么？ 还有，这些是两轮还是一轮呢？如何处理这一轮？

Answer 1

Paxos不是原子寄存器;一旦值为通过选择的Paxos，它不能改变

首先，注意到你的锁是有限状态机：

  on_lock 
     .-----------. 
     |   | 
+------+---+ +--v-----+ 
| UNLOCKED | | LOCKED |<--- start 
+------^---+ +--+-----+ 
     |   | 
     `-----------' 
     on_unlock 

Paxos可以用来决定一个转换序列;但每个新的转换都必须在新的Paxos实例中决定。

我建议考虑看看一些周围StackOverflow上的其它的Paxos问题：

• paxos value choice
• implementation of Paxos algorithm
• Questions about Paxos implementation

Answer 2

我们需要描述锁定协议，我们可以使用Paoxs运行以了解何时有多个值可用并查看选择值的结果。

的锁处于格式L={T,P}，其中P是进程持有锁和T是过程花费锁的时间保持锁定令牌值的小区。获取客户端发送V={Lc,Ln}其中Lc是它认为是当前锁定令牌和Ln={T',P'}是它要设定新的锁定令牌锁。可以发送特殊标记Nil来解锁该锁。如果消息未指出与当前令牌匹配的正确Lc，则新令牌未设置。此比较和交换（CAS）可防止错误应用延迟解锁消息。当客户端可以窃取它时它也可以超时锁定;如果两个进程发送两个赛车的消息{L1,L2}和{L1,L3}只有一个能够成功。进程通过检查作为锁定值L的返回值来了解其操作是否成功。一个进程可以查询通过发送{Nil,Nil}这是解锁一个打开的锁是“什么都不做” CAS锁值;但是如果锁关闭，则返回谁拥有锁。

写操作必须经过领导者。如果一个节点知道它不是领导者，它应该将客户端重定向到领导者。如果节点不知道谁是领导者，它应该抛出一个错误，客户端应该随机选择另一个节点。如果节点认为它是领导者，那么只有在确定大多数节点已接受新值时才能对客户端做出响应。这是因为Paxos确保多数人接受的价值已被集群持久化。如果节点处于领先地位，则不会听到大多数接受，它无法响应客户端。它可能与其他节点隔离。其他节点可能有新当选的领导。这也适用于{Nil,Nil}需要大部分接受的查询，以确认领导者仍然是领导者，以告诉客户当前的锁定值。最终，节点应该听到一个新的领导是否存在，否则超时试图获得大多数人接受的价值。然后，它应该将客户端重定向到新的领导者，否则向客户端返回错误。

现在我们可以在领导故障转移期间考虑多个值。客户端A发送一个有效的CAS更新V1，该更新应该连接到三节点群集的领导者节点X。节点X自己发送accept(N1,V1)，节点Y和Z。它接受自己的价值，并从Y获得承诺，但网络将该消息丢弃到Z。然后节点X变黑，并停止发送任何消息一段时间。它可能已经死亡或停滞，但我们还不知道。它已经看到了大部分X,Y，但现在是一个神秘的薛定谔的猫，要么死或活，直到我们看到另一个消息来知道它的命运。无论接下来发生什么，Paxos都选择使用协作来获得一致和正确的结果。

经过一段时间后，节点Z超时，因为它没有听到领导者太长时间。它向自身和其他节点发出propose(N2)。它从节点Y和promise(N2,empty)自身获取promise(N2,V1)。它拥有大多数Y,Z并且可以领先。只有节点X知道值V1已被大多数人接受，并且客户是否已被告知其CAS成功;但它是沉默的。节点Z必须做出保守的选择。如果假设X已经死亡，则可能是错误的：节点X可能处于活动状态，并且可能已告知客户端操作成功。节点Z必须协作并以V1作为其第一值完成最后领导者的部分工作。所以它将accept(N2,V1)发送给所有三个节点。现在，如果节点X已经死了或者已经告诉客户端操作成功了，那么这并不重要。在任何情况下，锁定协议都不会被违反，并且如果错误重试，客户端将最终发现它有锁定;它没有看到也不在意哪个提案和哪个节点实施了这项工作。