在分布式存储中实现线性化是否需要复制日志
Is a replication log necessary to achieve linearizability in distributed store
etcd使用的Raft算法和Zookeeper的ZAB算法都是使用复制日志更新状态机
我想知道是否可以通过简单地使用领导者选举和版本化值来设计一个类似的系统。以及为什么这些系统决定使用复制日志。
如果我们有以下设置，我就是我的例子
- 机器 A（领导者），包含版本 1
- 机器 B（跟随者），包含版本 1
- 机器 C（跟随者），包含版本 1
写入过程如下：
- 机器A接收写入请求并存储挂起写入V2
- 机器A向机器B和机器C发送准备请求
- 跟随者（机器 B 和机器 C）向领导者（机器 A）发送确认
- Leader（机器A）收到来自机器法定人数的Acknowledge后，它知道V2现在已经提交并向客户端发送成功响应
- Leader（机器a）向Follower（机器A和机器B）发送finalize请求，通知他们V2已经提交，V1可以被丢弃。
为了使该系统正常工作，在获取领导者租用后领导者发生变化时，领导者机器必须在接受请求之前通过从节点的仲裁中读取来获取最新的数据版本。
你的例子很有道理。但是，您是否考虑过每一种可能的故障情况？在步骤 2 中，由于网络分区或路由器故障，机器 B 可能会在机器 C 之前或之后几分钟（反之亦然）收到消息。在第 3 步中，确认可能会丢失、延迟或重传多次。领导者也可能失败并在同一轮共识中重新出现一次、两次或可能多次。在第 5 步中，消息可能会丢失、重复，或者机器 A 和 C 可能会收到通知，而 B 却没有收到通知....
概念简单性，也称为 "reducing the potential points of failure"，是分布式系统的关键。任何事情都有可能发生，在现实环境中会发生。原语，例如基于被证明在任何环境中都是正确的共识协议的复制日志，是构建更高级别抽象的坚实基础。更好的性能或延迟或您的 "metric of interest" 确实可以通过定制算法实现，但确保此类算法的正确性是 主要 的时间投资。
复制日志简单、易于理解、可预测，并且完全属于已建立的共识协议（paxos、paxos-variants 和 raft）的领域。这就是它们受欢迎的原因。这并不是因为它们是任何特定应用程序的最佳选择，而是因为它们易于理解且可靠。
相关参考，您可能感兴趣Understanding Paxos and Consensus in the Cloud: Paxos Systems Demystified
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.
是的，可以在没有日志复制的情况下实现 consensus/linearizability。最初，Leslie Lamport (1998) 在 Paxos Made Simple 论文中解决了共识问题。他描述了两种算法：Single Decree Paxos 用于构建分布式可线性化的一次写入寄存器和 Multi-Paxos 用于在仅追加日志（一次写入寄存器的有序数组）之上创建分布式状态机。
仅附加日志是比一次写入寄存器更强大的抽象，因此人们选择日志而不是寄存器也就不足为奇了。此外，在 Vertical Paxos (2009) 发表之前，日志复制是唯一能够更改集群成员资格的共识协议；对于多项任务至关重要的是：如果您不能更换故障节点，那么您的集群最终将变得不可用。
然而 Vertical Paxos 是一篇很好的论文，通过联合共识，我更容易理解 Raft 的 集群成员的想法，所以我写了 a post 关于如何将 Raft 的方式适配到 Single Decree Paxos。
随着时间的推移，Single Decree Paxos 的 "write-once" 性质也得到了解决，将一次写入寄存器变成分布式可线性化变量，这是一个非常强大的抽象，适用于许多用例。在野外，我在 Treode database. If you got interested I blogged about this improved SDP in the How Paxos Works post.
中看到了这种方法
所以现在当我们有日志的替代方案时，考虑它是有意义的，因为基于日志的复制很复杂并且有内在的局限性：
- 对于日志，您需要关心日志压缩和垃圾收集
- 日志的大小受限于一个节点的大小
- 用于拆分日志和迁移到新集群的协议并不为人所知
And why those system decided to use a replication log.
基于日志的方法比替代方法更早，因此它有更多时间获得流行。
关于你的例子
很难评价，因为你没有描述领导者选举是如何发生的，领导者之间的冲突是如何解决的，处理失败的策略是什么，如何改变集群的成员。
我相信如果你仔细描述它们你会得到a variant of Paxos。
etcd使用的Raft算法和Zookeeper的ZAB算法都是使用复制日志更新状态机
我想知道是否可以通过简单地使用领导者选举和版本化值来设计一个类似的系统。以及为什么这些系统决定使用复制日志。
如果我们有以下设置，我就是我的例子
- 机器 A（领导者），包含版本 1
- 机器 B（跟随者），包含版本 1
- 机器 C（跟随者），包含版本 1
写入过程如下：
- 机器A接收写入请求并存储挂起写入V2
- 机器A向机器B和机器C发送准备请求
- 跟随者（机器 B 和机器 C）向领导者（机器 A）发送确认
- Leader（机器A）收到来自机器法定人数的Acknowledge后，它知道V2现在已经提交并向客户端发送成功响应
- Leader（机器a）向Follower（机器A和机器B）发送finalize请求，通知他们V2已经提交，V1可以被丢弃。
为了使该系统正常工作，在获取领导者租用后领导者发生变化时，领导者机器必须在接受请求之前通过从节点的仲裁中读取来获取最新的数据版本。
你的例子很有道理。但是，您是否考虑过每一种可能的故障情况？在步骤 2 中，由于网络分区或路由器故障，机器 B 可能会在机器 C 之前或之后几分钟（反之亦然）收到消息。在第 3 步中，确认可能会丢失、延迟或重传多次。领导者也可能失败并在同一轮共识中重新出现一次、两次或可能多次。在第 5 步中，消息可能会丢失、重复，或者机器 A 和 C 可能会收到通知，而 B 却没有收到通知....
概念简单性，也称为 "reducing the potential points of failure"，是分布式系统的关键。任何事情都有可能发生，在现实环境中会发生。原语，例如基于被证明在任何环境中都是正确的共识协议的复制日志，是构建更高级别抽象的坚实基础。更好的性能或延迟或您的 "metric of interest" 确实可以通过定制算法实现，但确保此类算法的正确性是 主要 的时间投资。
复制日志简单、易于理解、可预测，并且完全属于已建立的共识协议（paxos、paxos-variants 和 raft）的领域。这就是它们受欢迎的原因。这并不是因为它们是任何特定应用程序的最佳选择，而是因为它们易于理解且可靠。
相关参考，您可能感兴趣Understanding Paxos and Consensus in the Cloud: Paxos Systems Demystified
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.
是的，可以在没有日志复制的情况下实现 consensus/linearizability。最初，Leslie Lamport (1998) 在 Paxos Made Simple 论文中解决了共识问题。他描述了两种算法：Single Decree Paxos 用于构建分布式可线性化的一次写入寄存器和 Multi-Paxos 用于在仅追加日志（一次写入寄存器的有序数组）之上创建分布式状态机。
仅附加日志是比一次写入寄存器更强大的抽象，因此人们选择日志而不是寄存器也就不足为奇了。此外，在 Vertical Paxos (2009) 发表之前，日志复制是唯一能够更改集群成员资格的共识协议；对于多项任务至关重要的是：如果您不能更换故障节点，那么您的集群最终将变得不可用。
然而 Vertical Paxos 是一篇很好的论文，通过联合共识，我更容易理解 Raft 的 集群成员的想法，所以我写了 a post 关于如何将 Raft 的方式适配到 Single Decree Paxos。
随着时间的推移，Single Decree Paxos 的 "write-once" 性质也得到了解决，将一次写入寄存器变成分布式可线性化变量，这是一个非常强大的抽象，适用于许多用例。在野外，我在 Treode database. If you got interested I blogged about this improved SDP in the How Paxos Works post.
中看到了这种方法所以现在当我们有日志的替代方案时，考虑它是有意义的，因为基于日志的复制很复杂并且有内在的局限性：
- 对于日志，您需要关心日志压缩和垃圾收集
- 日志的大小受限于一个节点的大小
- 用于拆分日志和迁移到新集群的协议并不为人所知
And why those system decided to use a replication log.
基于日志的方法比替代方法更早，因此它有更多时间获得流行。
关于你的例子
很难评价，因为你没有描述领导者选举是如何发生的，领导者之间的冲突是如何解决的，处理失败的策略是什么，如何改变集群的成员。
我相信如果你仔细描述它们你会得到a variant of Paxos。