为什么不使用操作来填补两次paxos事件之间的间隔是合法的？ [英] Why is it legit to use no-op to fill gaps between paxos events?

问题描述

我正在学习Paxos算法（ http： //research.microsoft.com/zh-CN/um/people/lamport/pubs/paxos-simple.pdf ），有一点我不理解。

I am learning Paxos algorithm (http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf) and there is one point I do not understand.

我们知道事件遵循及时的顺序，例如，当事件1-5和10确定后，但事件6-9和11尚未确定时，就会发生。在上面的论文中，它说我们只是用无操作值填充6-9之间的间隙，并简单地记录11点及以后的新事件。

We know that events follow a timely order, and it happens when, say, events 1-5 and 10 are decided, but 6-9 and 11 thereafter are not yet. In the paper above, it says we simply fill in the gap between 6-9 with no-op values, and simply record new events from 11 and on.

在这种情况下，由于已经记录了事件10，因此我们知道某些事件必须在5到10之间发生，但是由于某些故障Paxos并未记录。如果我们仅填写无操作值，这些事件将在我们的记录中丢失。

So in this case, since event 10 is already recorded, we know some kinds of events must have happened between 5 and 10 but are not recorded by Paxos due to some failures. If we simply fill in no-op values, these events will lost in our recording.

更糟糕的是，如果正如我上面链接的文章所述，事件实际上是来自客户端的命令，那么中间缺少一些命令可能会使整个集合操作非法（如果没有一个命令可以跳过或它们的顺序很重要）。

Even worse, if, as the paper I linked above says, events are in fact commands from the client, then missing a few commands in the middle might make the entire set of operations illegal (if none of the commands can be skipped or the order of them matters).

为什么Paxos仍然可以合法地为事件之间的间隔填充无操作值？ （如果整个记录集由于如上所述的无操作值而可能是无效的。）而且，是否有更好的方法可以从这种差距中恢复，而不是使用无操作？

So why is it still legit for Paxos to fill no-op values for gaps between events? (If the entire set of records might be invalid because of no-op values as I concerned above.) Also, is there a better way to recover from such gaps instead of using no-op?

推荐答案

这是一个包含多个部分的答案。

This is a multi-part answer.

建议无操作值是发现尚未到达节点的命令的方法。我们不只是使用无操作命令来填充间隙中的每个插槽：我们建议每个插槽都使用无操作来填充。如果任何对等方已经接受了命令，它将在 Prepare-ack 消息中返回该命令，并且提议者将使用接受回合中的命令，而不是无操作。

Proposing no-op values is the way to discover commands that haven't got to the node yet. We don't simply fill each slot in the gap with a no-op command: we propose each slot is filled with a no-op. If any of the peers have accepted a command already, it will return that command in the Prepare-ack message and the proposer will use that command in the Accept round instead of the no-op.

例如，假设一个节点位于临时网络分区后面，并且无法与其他节点一起使用6-9插槽。它知道在学习了插槽10中的命令后就错过了它。于是建议不操作来了解那些插槽中的决定。

For example, assume a node was behind a temporary network partition and was unable to play with the others for slots 6-9. It knows it missed out upon learning the command in slot 10. It then proposes no-ops to learn what was decided in those slots.

实际的实现也有一个带状学习协议，可大量学习大量过渡。

Practical implementations also have an out-of-band learning protocol to learn lots of transitions in bulk.

命令直到完全确定后，才是命令。 ; ，直到那时它只是一个建议命令。 Paxos是关于在来自多个客户端的竞争命令之间进行选择。客户必须准备好拒绝他们的命令，因为选择了另一个客户。

A command isn't a command until it is fully decided; until then it is just a proposed command. Paxos is about choosing between contending commands from multiple clients. Clients must be prepared to have their commands rejected because another client's was chosen instead.

实际的实现都是关于选择客户端命令的 order 。他们的世界观是预写日志，他们正在将命令放在该日志中。如果未选择命令，它们将在下一个插槽中重试。 （有很多方法可以减少争用； Lamport提到了将请求转发给领导者，例如在Multi-Paxos中所做的。）

Practical implementations are all about choosing the order of client commands. Their world view is that of a write-ahead log, and they are placing the commands in that log. They retry in the next slot if they're command wasn't chosen. (There are many ways to reduce the contention; Lamport mentions forwarding requests to a leader, such as is done in Multi-Paxos.)

实际系统也有一些方法可以在提出建议之前先知道该命令是否无效；例如了解一组读取和一组写入。这很重要，有两个原因。首先，它是一个异步的多客户端系统，当客户端的命令到达服务器时，一切都可能会发生变化。其次，如果两个并发命令没有冲突，那么两个命令都应该能够成功。

Practical systems also have some means to know if the command is invalid before proposing it; such as knowing a set of reads and a set of writes. This is important for two reasons. First, it's an asynchronous, multi-client system and anything could have changed by the time the client's command has reached the server. Second, if two concurrent commands do not conflict then both should be able to succeed.

这篇关于为什么不使用操作来填补两次paxos事件之间的间隔是合法的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！