0

为了让自己相信 Paxos 和 Raft 等标准算法的复杂性是必要的，必须理解为什么更简单的解决方案不能令人满意。假设，为了对 N 台机器集群中的事件流达成共识（即实现复制的时间增长日志），提出以下算法：

  1. 每当一台机器想要将一条消息附加到日志时，它就会广播元组(msg, rnd, prev)，其中msg是消息，rnd是一个随机数，prev是日志中最后一条消息的 ID。

  2. 当机器接收到一个元组时，它msg作为 的一个子插入prev，形成一棵树。

  3. 如果一个节点有多个孩子，只有最高的一个rnd被认为是有效的；有效消息通过树的路径是主链。

  4. 如果一条消息是主链的一部分，并且它足够老，则它被认为是决定/最终的。

  5. 如果一台机器尝试提交一条消息，但过了一段时间，它不在主链上，这意味着另一台机器大致同时广播了一条消息，所以你重新广播它直到它在那里。

看起来简单、高效且对崩溃具有弹性。这个算法会起作用吗？

4

1 回答 1

1

如果机器按顺序发送两个元组并且第一个丢失（包丢失/损坏或其他），我认为你有问题

在这种情况下，假设机器 1 的 prev elemtent id 为 10，然后再发送两个 (msg,rnd,10)=11 和 (msg,rnd,11)=12 到机器 2。

机器 2 只接收 (msg,rnd,11) 但在其树中没有 prev id 11。机器 3 接收两者，因此将其插入主树。

此时，分布式树之间会出现不同步。

在机器 x 将包插入树中后，我建议对包进行 ack 发送给发件人，他等待它发送下一个。

这样，发件人需要将先前的消息重新发送到在给定时间范围内未能确认的机器。

于 2017-03-11T15:25:59.837 回答