apache-zookeeper - 在分布式存储中实现线性化是否需要复制日志

Question

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

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

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

• 机器 A(领导者)，包含版本 1
• 机器 B(跟随者)，包含版本 1
• 机器 C(跟随者)，包含版本 1

写入会像这样:

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

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

Answer 1

The raft algorithm in ETCD and ZAB algorithm in Zookeeper are both using replication log to update a state machine. I was wondering if it's possible to design a similar system by simply using leader election and versioned values.

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

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

还Vertical Paxos是一篇好论文，我更容易理解 Raft's通过联合共识的集群成员的想法，所以我写了a post关于如何将 Raft 的方式应用于 Single Decree Paxos。

随着时间的推移，Single Decree Paxos 的“write-once”特性也得到了解决，将 write-once 寄存器转换为分布式可线性化变量，这是一个非常强大的抽象，适用于许多用例。在野外，我在 Treode database 中看到了这种方法.如果您有兴趣，我在 How Paxos Works 中发布了关于这个改进的 SDP 的博客。发布。

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

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

And why those system decided to use a replication log.

基于日志的方法比替代方法更早，因此它有更多时间获得流行。

关于你的例子

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

我相信如果你仔细描述它们，你会得到 a variant of Paxos .