Paxos算法(http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf)中有一点我不明白关于如何处理差距,本文描述了两种方法,如下所示:
leader,以及任何学习leader知道的所有命令的其他服务器,现在都可以执行命令1-135。但是,它不能执行命令138-140,它也知道,因为命令136和137还没有被选择。leader可以接受客户机请求的下两个命令,即命令136和137。相反,我们让它立即填补空白,提出了一个特殊的“禁止操作”命令,作为命令136和137,保持状态不变。(它通过执行一致算法实例136和137的第2阶段来实现这一点。)一旦选择了这些no op命令,就可以执行命令138–140。
接受客户端请求的下两个命令
特殊的“禁止操作”命令
已经提到了第二个选项Why is it legit to use no-op to fill gaps between paxos events。
我的问题是关于第一个。在我看来,接下两个命令会破坏一致性,因为后面发生的实例可能序号较小。为什么它仍然合法?
最佳答案
由于所有客户机都看到相同的一致性结果,因此不会违反一致性所以不违反算法不变量。
如果考虑所有命令都来自一个客户机的场景,那么与客户机发送值的顺序相比,这将是一个重新排序如果单个客户机是多线程的,并且它流式处理多个并发请求,那么重新排序可能是无害的(取决于应用程序语义)。如果您认为leader使用noops,那么它只会有效地删除一些可能对客户机无害的消息,这取决于它流的值的顺序。这取决于应用程序。
如果考虑到所有价值都来自不同客户的情况,那么情况就自然得多。在相反的条件下,会发生一些重新排序。但在正常情况下,这种情况不会发生。重新排序它只是看起来有些值“比正常值花了更长的时间”才被领导者修复,而其他客户机发布的值“运行得更快”。