2

Paxos 算法（http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf）中有一点我不明白。这是关于如何处理差距的，论文描述了两种方法：

领导者以及学习领导者知道的所有命令的任何其他服务器现在可以执行命令 1-135。但是，它不能执行它也知道的命令 138–140，因为尚未选择命令 136 和 137。领导者可以将客户端请求的接下来的两个命令作为命令 136 和 137。相反，我们通过提出作为命令 136 和 137 的特殊“no-op”命令来立即填补空白，使状态保持不变. （它通过执行共识算法实例 136 和 137 的阶段 2 来做到这一点。）一旦选择了这些无操作命令，就可以执行命令 138-140。

  1. 执行客户端请求的下两个命令
  2. 特殊的“no-op”命令

已经提到了第二个选项为什么使用 no-op 来填补 paxos events 之间的空白是合法的。

我的问题是关于第一个问题。在我看来，接下来的两个命令会违反一致性，因为后面发生的实例可能具有较小的序列号。那么为什么它仍然是合法的呢？

4

2 回答 2

1

由于所有客户都看到相同的一致结果，因此不会违反一致性。所以没有违反算法不变量。

如果您考虑所有命令都来自单个客户端的场景，那么与客户端发送值的顺序相比，这将是一种重新排序。如果单个客户端是多线程的并且如果它流式传输多个并发请求，则重新排序可能是无害的（或不是，取决于应用程序语义）。如果您认为领导者使用 noops，那么它实际上只是丢弃了一些可能对客户端无害的消息，这取决于它流式传输的值的顺序。这取决于应用程序。

如果您考虑所有值都来自不同客户端的情况，那么情况会更加自然。在不利的条件下，会发生一些重新排序。然而，在正常运行情况下不会发生这种情况。重新排序它看起来像一些值“比正常时间更长”才能由领导者修复，而后来其他客户端发布的值“运行得更快”。

于 2017-11-14T20:10:58.833 回答
0

第一个选项和第二个选项是一样的。

例如在这个例子中，客户端想要写 4 个命令，

a = 1  
b = 2  
c = 3  
d = 4

在第一个选项中，结果可能是

a = 1  
e = 5  
f = 6  
d = 4

在第二个选项中，结果是

a = 1  
noop  
noop  
d = 4

所以，这两个结果都是非法的。在这个问题中丢失数据和违反顺序没有区别。

然后正如@simbo1905 所说，多Paxos 不承诺FIFO 顺序。

如果136、137、138有顺序关系，比如通过一个TCP连接发送，客户端通过管道发送这三个命令。以先进先出的顺序进行这些操作是客户的责任。如果客户端有很多传出的命令，并且客户端想要先进先出的客户端顺序，客户端需要从第一个失败的命令开始重试该命令。

另一种情况是它们是由不同的连接发送的。由于它们是通过不同的连接发送的，因此服务器不能承诺 FIFO 客户端顺序。136、137操作失败，任何场景都可以接受，这两个操作可以成功也可以失败。如果客户端想知道结果，客户端应该重试操作。

在这两种情况下，承诺订单的责任是客户端，而不是服务器。

所以我认为你误解了一致性的含义，一致性与顺序无关。这是关于安全和活力

于 2017-11-20T17:27:05.117 回答