2

etcd 使用的 Raft 算法和 Zookeeper 使用的 ZAB 算法都是使用复制日志来更新状态机。

我想知道是否可以通过简单地使用领导者选举和版本化值来设计一个类似的系统。以及为什么这些系统决定使用复制日志。

如果我们有以下设置，我就是我的例子

  • 机器 A（Leader），包含版本 1
  • 机器 B（跟随者），包含版本 1
  • 机器 C（跟随者），包含版本 1

写入将是这样的：

  1. 机器 A 接收写入请求并存储待处理的写入 V2
  2. 机器 A 向机器 B 和机器 C 发送准备请求
  3. 追随者（机器 B 和机器 C）向领导者（机器 A）发送确认
  4. 领导者（机器 A）从机器的 quorum 收到确认后，它知道 V2 现在已提交，并向客户端发送成功响应
  5. Leader（机器 a）向 Follower（机器 A 和机器 B）发送 finalize 请求，通知他们 V2 已提交，V1 可以被丢弃。

为了使该系统正常工作，在获得领导者租赁后领导者发生变化时，领导者机器必须通过在接受请求之前从节点的法定人数中读取来获取最新的数据版本。

4

2 回答 2

4

ETCD 中的 raft 算法和 Zookeeper 中的 ZAB 算法都是使用复制日志来更新状态机。我想知道是否可以通过简单地使用领导者选举和版本化值来设计一个类似的系统。

是的，无需日志复制就可以实现共识/线性化。最初，共识问题在Leslie Lamport (1998)的Paxos Made Simple论文中得到解决。他描述了两种算法：Single Decree Paxos 用于构建分布式线性化一次性写入寄存器，Multi-Paxos 用于在仅附加日志（一次性写入寄存器的有序数组）之上构建分布式状态机。

仅附加日志比一次写入寄存器更强大的抽象，因此人们选择日志而不是寄存器也就不足为奇了。此外，在Vertical Paxos (2009) 发布之前，日志复制是唯一能够更改集群成员的共识协议；对于多项任务来说至关重要的是：如果您无法替换故障节点，那么最终您的集群将变得不可用。

然而Vertical Paxos是一篇好论文，通过联合共识对我来说更容易理解Raft集群成员的想法，所以我写了一篇关于如何将 Raft 的方式改编为 Single Decree Paxos 的帖子。

随着时间的推移，Single Decree Paxos 的“一次写入”性质也得到解决，将一次性写入寄存器转换为分布式线性化变量，这是一种适用于许多用例的非常强大的抽象。在野外，我在Treode 数据库中看到了这种方法。如果你有兴趣，我会在Paxos的工作原理博文中写下这个改进的 SDP 。

所以现在当我们有日志的替代品时，考虑它是有意义的，因为基于日志的复制很复杂并且有内在的限制：

  • 对于日志，您需要关心日志压缩和垃圾收集
  • 日志的大小受一个节点大小的限制
  • 用于拆分日志和迁移到新集群的协议并不为人所知

以及为什么这些系统决定使用复制日志。

基于日志的方法比替代方法更老，因此它有更多的时间来获得普及。

关于你的例子

很难评估，因为你没有描述领导者选举是如何发生的，领导者之间的冲突是如何解决的，处理失败的策略是什么以及如何更改集群的成员资格。

我相信如果你仔细描述它们，你会得到Paxos 的一个变体。

于 2016-04-15T07:23:54.570 回答
3

你的例子很有意义。但是，您是否考虑过所有可能的故障情况？在步骤 2 中，由于网络分区或路由器故障，机器 B 可以在机器 C 之前或之后（反之亦然）收到消息。在步骤 3 中，确认可能会丢失、延迟或多次重新传输。领导者也可能在同一轮共识中失败并重新出现一次、两次或可能多次。在第 5 步中，消息可能会丢失、重复，或者机器 A 和 C 可能会在 B 错过通知时收到通知......

概念简单，也称为“减少潜在故障点”，是分布式系统的关键。任何事情都可能发生，并且会在现实环境中发生。原语，例如基于在任何环境中被证明是正确的共识协议的复制日志，是构建更高级别抽象的坚实基础。确实可以通过定制算法实现更好的性能或延迟或您的“感兴趣的指标”，但确保此类算法的正确性是一项重大的时间投资。

复制的日志简单、易于理解、可预测，并且完全属于已建立的共识协议（paxos、paxos-variants 和 raft）的领域。这就是他们受欢迎的原因。这并不是因为它们最适合任何特定的应用程序，而是因为它们易于理解且可靠。

有关相关参考资料，您可能对了解 Paxos和云中的共识感兴趣：Paxos Systems Demystified

于 2016-04-13T05:56:41.263 回答