为什么采用下两个命令来填补paxos事件之间的空白是合法的? [英] Why is it legit to take the next two commands to fill gaps between paxos events?
问题描述
Paxos算法中有一个要点( http://research.microsoft.com/zh-cn/um/people/lamport/pubs/paxos-simple.pdf ).关于如何处理差距，本文描述了以下两种方法:
There is a point in Paxos algorithm (http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf) that I do not understand. It's about how to deal with the gaps, the paper describe two ways as below:
领导者以及学习领导者知道的所有命令的任何其他服务器，现在可以执行命令1–135.但是，它无法执行它也知道的命令138-140，因为尚未选择命令136和137.领导者可以将客户要求的下两个命令作为命令136和137.相反，我们通过建议一条特殊的"no-op"命令作为命令136和137，来立即填补空白.状态保持不变.(它是通过执行共识算法实例136和137的阶段2来完成的.)一旦选择了这些无操作命令，就可以执行命令138-140.
The leader, as well as any other server that learns all the commands the leader knows, can now execute commands 1–135. However, it can’t execute commands 138–140, which it also knows, because commands 136 and 137 have yet to be chosen. The leader could take the next two commands requested by clients to be commands 136 and 137. Instead, we let it fill the gap immediately by proposing, as commands 136 and 137, a special "no- op" command that leaves the state unchanged. (It does this by executing phase 2 of instances 136 and 137 of the consensus algorithm.) Once these no-op commands have been chosen, commands 138–140 can be executed.
- 接受客户要求的接下来的两个命令
- 特殊的"no-op"命令
提到了第二个选项我的问题是关于第一个的.我认为，接下两个命令将违反一致性，因为事后发生的实例可能具有较小的序列号.那么为什么它仍然是合法的?
And My question is about the first one. In my opinion, take the next two commands will violate the consistency, since the instance happened later may be have a smaller sequence number. So why it is still legit?
推荐答案
由于所有客户端都看到相同的一致结果，因此不会违反一致性.因此，没有违反算法不变式.
Since all clients see the same consistent outcome there isn't a violation of consistency. So there isn't a violation of the algorithms invariants.
如果考虑所有命令都来自单个客户端的情况，那么与客户端发送值的顺序相比，这将是重新排序.如果单个客户端是多线程的，并且如果它流式传输多个并发请求，则重新排序可能是无害的(取决于应用程序的语义).如果您认为领导者使用noops，那么它实际上只是丢弃一些消息，这对于客户端来说可能是无害的，这取决于客户端流式传输的值的顺序.这取决于应用程序.
If you consider the scenario where all the commands come from a single client then it would be a reordering compared to the order the client sent the values. If a single client is multi-threaded and if it streams multiple concurrent requests the reordering may be harmless (or not, depending on the application semantics). If you consider that the leader uses noops then it effectively just drops some messages which may not be harmless to a client that depends on the ordering of values it streams. It depends on the application.
如果您考虑所有值都来自不同客户的情况，那么情况就自然而然了.在不利条件下，会发生一些重新排序.但是在正常运行下不会发生这种情况.重新排序它看起来就像某些值花费比正常时间更长"要由领导者修复，而其他客户端发布的后来的值运行得更快".
If you consider the scenario where all the values come from different clients then the situation is far more natural. Under averse conditions some reordering occurs. Yet under normal running that doesn't happen. The reordering it just looks like some values "took longer than normal" to be fixed by a leader while later values issued by other clients "ran faster".
这篇关于为什么采用下两个命令来填补paxos事件之间的空白是合法的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
