--- title: 分布式综合面试 date: 2021-11-08 08:15:33 categories: - 分布式 - 分布式综合 tags: - 分布式 - 指标 - 挑战 - 超时检测 - NTP - 逻辑时钟 permalink: /pages/5b3ad94d/ --- # 分布式综合面试 ## 逻辑时钟 ::: info 扩展阅读 - [**Time, Clocks, and the Ordering of Events in a Distributed System**](https://lamport.azurewebsites.net/pubs/time-clocks.pdf)，[**译文**](https://cloud.tencent.com/developer/article/1163428)，[**解读**](https://zhuanlan.zhihu.com/p/56146800) - Lamport 介绍 happened before、偏序关系（partial ordering）、逻辑时钟（Logical Clocks）概念，提出解决分布式系统中区分事件发生的时序问题的方法。 - [**Virtual Time and Global States of Distributed Systems**](http://courses.csail.mit.edu/6.852/01/papers/VirtTime_GlobState.pdf)，[**解读**](https://zhuanlan.zhihu.com/p/56886156) - 逻辑时钟无法描述事件的因果关系。本文提出了向量时钟，这种算法利用了向量这种数据结构将全局各个进程的逻辑时间戳广播给各个进程，通过向量时间戳就能够比较任意两个事件的因果关系。 - [逻辑时钟 - 如何刻画分布式中的事件顺序](https://writings.sh/post/logical-clocks) ::: ### 【简单】为什么需要逻辑时钟？ ::: tip 要点 **不同节点的物理时钟即使校准（NTP）也无法完全保持一致**。 ::: 为什么需要逻辑时钟？分布式系统中以系统时间来确定事件顺序有什么问题吗？ **不同节点的物理时钟无法完全保持一致**。即使引入一个全局时钟（例如：NTP）来进行校准，由于网络通信延迟的不确定性，以及时钟计时的偏差，无法保证每个节点的时间完全一致。 在分布式系统中，由于网络通信延迟的不确定性， **仅仅以接收顺序作为整个分布式系统中事件的发生顺序是不可取的**。 ### 【中等】什么是偏序？什么是全序？ 全序和偏序是数学上的术语，按照数学内容阐述比较晦涩，简单来说： - **偏序**是部分可比较的有序关系。 - **全序**是在偏序基础上，要求全部元素必须可比较的有序关系。 ### 【困难】什么是逻辑时钟？ ::: info 扩展阅读 [**Time, Clocks, and the Ordering of Events in a Distributed System**](https://lamport.azurewebsites.net/pubs/time-clocks.pdf) ::: ::: tip 要点 - **Lamport 逻辑时钟构建了一个全序时钟来描述事件顺序**。 - **Lamport 逻辑时钟的缺陷是无法描述同时发生的事件**。 ::: 1978 年，Lamport 在 [**Time, Clocks, and the Ordering of Events in a Distributed System**](https://lamport.azurewebsites.net/pubs/time-clocks.pdf) 中提出了逻辑时钟的概念，来解决分布式系统中区分事件发生的时序问题。 **逻辑时钟并不度量时间本身，仅区分事件发生的前后顺序**。 分布式系统中按是否存在节点交互可分为三类事件，一类发生于节点内部，二是发送事件，三是接收事件。Lamport 时间戳原理如下： ![Lamport timestamps space time (图片来源: wikipedia)_](https://raw.githubusercontent.com/dunwu/images/master/snap/202405170810350.webp) 1. 每个事件对应一个 Lamport 计数器，初始值为 0 2. 如果事件在节点内发生，计数器加 1 3. 如果事件属于发送事件，计数器加 1 并在消息中带上该计数器 4. 如果事件属于接收事件，计数器 = Max(本地计数器，消息中的计数器) + 1 综上，**Lamport 逻辑时钟构建了一个全序时钟来描述事件顺序**。**Lamport 逻辑时钟的缺陷是无法描述同时发生的事件**。 ### 【困难】什么是向量时钟？ ::: tip 要点 - 向量时钟在逻辑时钟基础上改进：**不仅记录了本节点的时间戳，还记录了其他节点的时间戳**。 - 其本质在于**将逻辑时钟的全序计数器改造为向量时钟的偏序大小关系**：向量有序，则事件有序；向量平行，则事件并发。 - **向量时钟可以发现数据冲突，但不能解决数据冲突**。 ::: **向量时钟**其实是在逻辑时钟的基础上进行了演进，算法逻辑类似，只是**不仅记录了本节点的时间戳，还记录了其他节点的时间戳**。其本质在于**将逻辑时钟的全序计数器改造为向量时钟的偏序大小关系**：向量有序，则事件有序；向量平行，则事件并发。 ![Vector clock space time (图片来源: wikipedia)](https://raw.githubusercontent.com/dunwu/images/master/snap/202405170811135.webp) **向量时钟可以发现数据冲突，但不能解决数据冲突**。 ### 【困难】什么是版本向量时钟？ ::: tip 要点 **版本向量时钟只有在更新数据的时候做向量自增**。 ::: 在向量时钟算法中， 消息传播后，发送方的向量一定会小于接收者的向量， 是因为接收者对齐了发送者的原因。 版本向量在此基础上，做了一点加强：消息传播后，发送方也对齐接收者的向量，也就是双向对齐，在版本向量中，叫做**同步**。 发送消息和接收消息的时候不再自增向量中的自己的计数器，而是只做双方的向量对齐操作。 也就是，**只有在更新数据的时候做向量自增**。 ## 一致性 ### 【简单】什么是强一致性？什么是弱一致性？什么是最终一致性？ **一致性（Consistency）**指的是**多个数据副本是否能保持一致**的特性。 数据一致性又可以分为以下几点： - **强一致性** - 数据更新操作结果和操作响应总是一致的，即操作响应通知更新失败，那么数据一定没有被更新，而不是处于不确定状态。通俗的说，分布式系统在执行写操作成功后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。 - **弱一致性** - 系统在写入数据成功后，不承诺立即能读到最新的值，也不承诺什么时候能读到，但是过一段时间之后用户可以看到更新后的值。那么用户读不到最新数据的这段时间被称为“不一致窗口时间”。 - **最终一致性** - 最终一致性作为弱一致性中的特例，强调的是所有数据副本，在经过一段时间的同步后，最终能够到达一致的状态，不需要实时保证系统数据的强一致性。 ### 【简单】什么是 ACID？ 那么，什么是 ACID 特性呢？ACID 是数据库事务正确执行的四个基本要素的单词缩写： - **原子性（Atomicity）** - 原子是指不可分解为更小粒度的东西。事务的原子性意味着：**事务中的所有操作要么全部成功，要么全部失败**。 - 回滚可以用日志来实现，日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。 - ACID 中的原子性并不关乎多个操作的并发性，它并没有描述多个线程试图访问相同的数据会发生什么情况，后者其实是由 ACID 的隔离性所定义。 - **一致性（Consistency）** - 数据库在事务执行前后都保持一致性状态。 - 在一致性状态下，所有事务对一个数据的读取结果都是相同的。 - 一致性本质上要求应用层来维护状态一致（或者恒等），应用程序有责任正确地定义事务来保持一致性。这不是数据库可以保证的事情。 - **隔离性（Isolation）** - **同时运行的事务互不干扰**。换句话说，一个事务所做的修改在最终提交以前，对其它事务是不可见的。 - **持久性（Durability）** - 一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。 - 可以通过数据库备份和恢复来实现，在系统发生奔溃时，使用备份的数据库进行数据恢复。 一个支持事务（Transaction）中的数据库系统，必需要具有这四种特性，否则在事务过程（Transaction processing）当中无法保证数据的正确性。 - 只有满足一致性，事务的执行结果才是正确的。 - 在无并发的情况下，事务串行执行，隔离性一定能够满足。此时只要能满足原子性，就一定能满足一致性。 - 在并发的情况下，多个事务并行执行，事务不仅要满足原子性，还需要满足隔离性，才能满足一致性。 - 事务满足持久化是为了能应对系统崩溃的情况。 ## CAP & BASE ::: info 扩展阅读 - [**Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services**](https://www.comp.nus.edu.sg/~gilbert/pubs/BrewersConjecture-SigAct.pdf)，[**解读**](https://juejin.cn/post/6844903936718012430) - 经典的 CAP 定理，即：在一个分布式系统中，当发生网络分区时，那么强一致性和可用性只能二选一。 - [**CAP Twelve Years Later: How the “Rules” Have Changed**](https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/), [**解读**](https://www.zhihu.com/question/64778723/answer/224266038) - CAP 定理的新解读，并阐述 CAP 定理的一些常见误区。 - [**BASE: An Acid Alternative**](https://www.semanticscholar.org/paper/BASE%3A-An-Acid-Alternative-Pritchett/2e72e6c022dd33115304ecfcb6dad7ea609534a4)，[**译文**](https://www.cnblogs.com/savorboard/p/base-an-acid-alternative.html) - BASE 定理是对 CAP 中一致性和可用性的权衡，提出采用适当的方式来使系统达到最终一致性。 ::: ### 【中等】什么是 CAP 定理？ ::: tip 要点 - CAP 就是取 Consistency、Availability、Partition Tolerance 的首字母而命名。 - CAP 定理提出：Consistency、Availability、Partition Tolerance 三者不可兼得。 - 在分布式系统中，分区容错不可避免，因此，**CAP 定理实际上是要在可用性（A）和一致性（C）之间做权衡**。 ::: CAP 定理提出：分布式系统有三个指标，这三个指标不能同时做到： - **一致性（Consistency）** - 在任何给定时间，网络中的所有节点都具有完全相同（最近）的值。 - **可用性（Availability）** - 对网络的每个请求都会返回响应，但不能保证返回的数据是最新的。 - **分区容错性（Partition Tolerance）** - 即使任意数量的节点出现故障，网络仍会继续运行。 CAP 就是取 Consistency、Availability、Partition Tolerance 的首字母而命名。 ![](https://raw.githubusercontent.com/dunwu/images/master/snap/202405160639643.png) 在分布式系统中，分区容错性是一个既定的事实：因为分布式系统总会出现各种各样的问题，如由于网络原因而导致节点失联；发生机器故障；机器重启或升级等等。因此，**CAP 定理实际上是要在可用性（A）和一致性（C）之间做权衡**。 ### 【中等】选择 CP 还是 AP？ ::: tip 要点 选择 AP 还是 CP，视具体业务场景而定。 以注册中心而论，可用性比一致性更重要，选 AP 更合适。 ::: 在分布式系统中，分区容错性是一个既定的事实：因为分布式系统总会出现各种各样的问题，如由于网络原因而导致节点失联；发生机器故障；机器重启或升级等等。因此，**CAP 定理实际上是要在可用性（A）和一致性（C）之间做权衡**。 - 选择 **AP 模式**，偏向于保证服务的高可用性。用户访问系统的时候，都能得到响应数据，不会出现响应错误；但是，当出现分区故障时，相同的读操作，访问不同的节点，得到响应数据可能不一样。 - 选择 **CP 模式**，一旦因为消息丢失、延迟过高发生了网络分区，就会影响用户的体验和业务的可用性。因为为了防止数据不一致，系统将拒绝新数据的写入。 一个最具代表性的问题是：服务注册中心应该选择 AP 还是 CP？ 在微服务架构下，服务注册和服务发现机制中主要有三种角色： - **服务提供者**（RPC Server / Provider） - **服务消费者**（RPC Client / Consumer） - **服务注册中心**（Registry） **注册中心**负责协调服务注册和服务发现，显然它是核心中的核心。主流的注册中心有很多，如：ZooKeeper、Nacos、Eureka、Consul、etcd 等。在针对注册中心进行技术选型时，其 CAP 设计也是一个比较的维度。 - CP 模型代表：ZooKeeper、etcd。系统强调数据的一致性，当数据一致性无法保证时（如：正在选举主节点），系统拒绝请求。 - AP 模型代表：Nacos、Eureka。系统强调可用性，牺牲一定的一致性（即服务节点上的数据不保证是最新的），来保证整体服务可用。 对于服务注册中心而言，即使不同节点保存的服务注册信息存在差异，也不会造成灾难性的后果，仅仅是信息滞后而已。但是，如果为了追求数据一致性，使得服务发现短时间内不可用，负面影响更严重。所以，对于服务注册中心而言，可用性比一致性更重要，一般应该选择 AP 模型。 ### 【中等】CAP 定理真的正确吗？ ::: tip 要点 CAP 理论模型局限性很大，未考虑网络分区以外的各种故障、异常情况，因此对于复杂的分布式系统场景指导意义不足。 ::: CAP 定理在分布式系统领域大名鼎鼎，以至于被很多人视为了真理。然而，CAP 定理真的正确吗？ 网络分区是一种故障，不管喜欢还是不喜欢，它都可能发生，所以无法选择或逃避分区的问题。在网络正常的时候，系统可以同时保证一致性（线性化）和可用性。而一旦发生了网络故障，必须要么选择一致性，要么选择可用性。因此，对 CAP 更准确的理解应该是：**当发生网络分区（P）的情况下，可用性（A）和一致性（C）二者只能选其一**。 CAP 定理所描述的模型实际上局限性很大，它只考虑了一种一致性模型和一种故障（网络分区故障），而没有考虑网络延迟、节点失效等情况。因此，它对于指导一个具体的分布式系统设计来说，没有太大的实际价值。 值得一提的是，在 CAP 定理提出十二年之后，其提出者也发表了一篇文章 [**CAP Twelve Years Later: How the “Rules” Have Changed**](https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/)，来阐述 CAP 定理的局限性。 ### 【中等】什么是 BASE 定理？ ::: tip 要点 BASE 是 **`基本可用（Basically Available）`**、**`软状态（Soft State）`** 和 **`最终一致性（Eventually Consistent）`** 三个短语的缩写。 BASE 核心思想是：要求最终一致性，通过牺牲强一致性来达到可用性。 ::: BASE 是 **`基本可用（Basically Available）`**、**`软状态（Soft State）`** 和 **`最终一致性（Eventually Consistent）`** 三个短语的缩写。BASE 定理是对 CAP 定理中可用性（A）和一致性（C）权衡的结果。 BASE 定理的**核心思想**是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。 ACID 要求强一致性，通常运用在传统的数据库系统上。而 BASE 要求最终一致性，通过**牺牲强一致性来达到可用性**，通常运用在大型分布式系统中。 在实际的分布式场景中，不同业务单元和组件对一致性的要求是不同的，因此 ACID 和 BASE 往往会结合在一起使用。 ## Paxos ::: info 扩展阅读 - [Part-time Parliament 论文](https://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf) - [Paxos Made Simple 论文](https://lamport.azurewebsites.net/pubs/paxos-simple.pdf) - [Paxos 算法详解](https://zhuanlan.zhihu.com/p/31780743) - [Wiki - Paxos 算法](https://zh.wikipedia.org/w/index.php?title=Paxos%E7%AE%97%E6%B3%95) - [一致性算法（Paxos、Raft、Zab）](https://www.bilibili.com/video/BV1TW411M7Fx?from=search&seid=11524608198747599965) - [Raft 作者讲解 Paxos 视频](https://www.bilibili.com/video/av36556594) - [Paxos 算法讲解视频](https://www.youtube.com/watch?v=d7nAGI_NZPk) - [深入剖析共识性算法 Paxos](https://dunwu.github.io/waterdrop/pages/d287e6b0/) ::: ### 【困难】Paxos 是怎样工作的？ ::: tip 要点 Paxos 是一个分布式系统共识性算法。它的核心思想是**【两阶段提交】**和**【多数派决议】**。 Paxos 将分布式系统中的节点分 Proposer、Acceptor、Learner 三种角色。 Paxos 算法包含 2 个部分： - **Basic Paxos 算法**：描述的是多节点之间如何就某个值达成共识。**Basic Paxos 是通过二阶段提交的方式来达成共识的**。 - **Multi Paxos 思想**：描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。 ::: **Paxos 是一种基于消息传递且具有容错性的共识性（consensus）算法**。 Paxos 算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。 Paxos 利用多数派 (Majority) 机制保证了一定的容错能力，即 `N` 个节点的系统最多允许 `N / 2 - 1` 个节点同时出现故障。 Paxos 算法包含 2 个部分： - **Basic Paxos 算法**：描述的是多节点之间如何就某个值达成共识。 - **Multi Paxos 思想**：描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。 #### Basic Paxos 算法 **Basic Paxos 是通过二阶段提交的方式来达成共识的**。 Paxos 将分布式系统中的节点分 Proposer、Acceptor、Learner 三种角色。 - **提议者（Proposer）**：发出提案（Proposal），用于投票表决。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。在绝大多数场景中，集群中收到客户端请求的节点，才是提议者。这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑。 - **接受者（Acceptor）**：对每个 Proposal 进行投票，若 Proposal 获得多数 Acceptor 的接受，则称该 Proposal 被批准。一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。 - **学习者（Learner）**：不参与接受，从 Proposers/Acceptors 学习、记录最新达成共识的提案（Value）。一般来说，学习者是数据备份节点，比如主从架构中的从节点，被动地接受数据，容灾备份。 Paxos 算法有 3 个阶段，其中，前 2 个阶段负责协商并达成共识： 1. **准备（Prepare）阶段**：Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。 2. **接受（Accept）阶段**：Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的 Propose 请求进行 Accept 处理。 3. **学习（Learn）阶段**：Proposer 在收到多数 Acceptors 的 Accept 之后，标志着本次 Accept 成功，决议形成，将形成的决议发送给所有 Learners。 #### Multi Paxos 思想 Basic Paxos 有以下问题，导致它不能应用于实际： - **Basic Paxos 算法只能对一个值形成决议**。 - **Basic Paxos 算法会消耗大量网络带宽**。Basic Paxos 中，决议的形成至少需要两次网络通信，在高并发情况下可能需要更多的网络通信，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos 搞不定了。 Multi Paxos 基于 Basic Paxos 做了两点改进： - **针对每一个要确定的值，运行一次 Paxos 算法实例（Instance），形成决议**。每一个 Paxos 实例使用唯一的 Instance ID 标识。 - **在所有 Proposer 中选举一个 Leader，由 Leader 唯一地提交 Proposal 给 Acceptor 进行表决**。这样没有 Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。 ## Raft ::: info 扩展阅读 - [Raft 算法论文](https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf) - [Raft 算法论文译文](https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md) - [Raft 作者讲解视频](https://www.youtube.com/watch?v=YbZ3zDzDnrw&feature=youtu.be) - [Raft 作者讲解视频对应的 PPT](http://www2.cs.uh.edu/~paris/6360/PowerPoint/Raft.ppt) - [分布式系统的 Raft 算法](https://www.jdon.com/artichect/raft.html) - [Raft 算法详解](https://zhuanlan.zhihu.com/p/32052223) - [Raft: Understandable Distributed Consensus](http://thesecretlivesofdata.com/raft) - 一个动画教程 - [The Raft Consensus Algorithm](https://raft.github.io/) - 一个交互式动画教程 - [深入剖析共识性算法 Raft](https://dunwu.github.io/waterdrop/pages/3a64eb94/) ::: ### 【困难】Raft 是怎样工作的？ ::: tip 要点 **[Raft](https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf) 是一种管理日志复制的分布式共识性算法**。 Raft 将一致性问题分解成了三个子问题： - **选举 Leader**： - **Leader 心跳**：Leader 定时向 Follower 发心跳以续活；Follower 超时未收到心跳，视其为下线。 - **投票选举**：Follower 判断 Leader 下线后，发起 Leader 选举，成为 Candidate。 - **多数派原则**：得到大多数选票的 Candidate 当选为 Leader。 - **随机的竞选超时时间**： - 每个 Follower 都设置一个随机的竞选超时时间，该时间范围内，未收到 Leader 的心跳，就视为当前 Term 无 Leader，再次 Leader 选举。 - 之所以是随机时间，是为了避免重复出现相同投票结果，导致始终选不出 Leader 的情况（一种典型的活锁）。 - **日志复制**：Leader 负责处理所有客户端读写请求；Follower 只负责同步 Leader 的日志，并更新本地的日志状态机（Offset） - **安全性** - **选举限制**：拥有最新的已提交的日志条目的 Follower 才有资格成为 Leader。 - **提交旧任期的日志条目**：**Raft 永远不会通过计算副本数目的方式去提交一个之前 Term 内的日志条目**。 - **日志压缩**：Raft 采用对整个系统进行快照来解决，快照之前的日志都可以丢弃。以此，避免日志无限膨胀，导致故障恢复过久。 ::: **[Raft](https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf) 是一种管理日志复制的分布式共识性算法**。从本质上说，**Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致**。 [Raft](https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf) 出现之前，Paxos 一直是分布式共识性算法的标准。Paxos **难以理解，更难以实现**。Raft 的设计目标是简化 Paxos，使得算法**既容易理解，也容易实现**。 Raft 将一致性问题分解成了三个子问题： - **选举 Leader** - **日志复制** - **安全性** #### Raft 概念 **（1）服务器角色** 在 Raft 中，任何时刻，每个服务器都处于这三个角色之一 ： - **`Leader`** - 领导者，通常一个系统中是**一主（Leader）多从（Follower）**。Leader **负责处理所有的客户端请求**。 - **`Follower`** - 跟随者，**不会发送任何请求**，只是简单的 **响应来自 Leader 或者 Candidate 的请求**。 - **`Candidate`** - 参选者，选举新 Leader 时的临时角色。 ![](https://raw.githubusercontent.com/dunwu/images/master/snap/20200131215742.png) **（2）任期** ![](https://raw.githubusercontent.com/dunwu/images/master/snap/20200131220742.png) Raft 把时间分割成任意长度的 **_`任期（Term）`_**，任期用连续的整数标记。每一段任期从一次**选举**开始。**Raft 保证了在一个给定的任期内，最多只有一个领导者**。 **任期在 Raft 算法中充当逻辑时钟的作用，使得服务器节点可以查明一些过期的信息（比如过期的 Leader）。每个服务器节点都会存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号。** **（3）选举 Leader** **领导者心跳消息**：Raft 使用一种心跳机制来触发 Leader 选举。**Leader 需要周期性的向所有 Follower 发送心跳消息**，以此维持 Leader 身份。 **随机的竞选超时时间**：每个 Follower 都设置了一个**随机的竞选超时时间**，一般为 `150ms ~ 300ms`，如果在竞选超时时间内没有收到 Leader 的心跳消息，就会认为当前 Term 没有可用的 Leader，并发起选举来选出新的 Leader。开始一次选举过程，Follower 先要增加自己的当前 Term 号，并**转换为 Candidate**。 Candidate 会并行的**向集群中的所有服务器节点发送投票请求（`RequestVote RPC`）**，它会保持当前状态直到以下三件事情之一发生： - **自己成为 Leader** - **其他的服务器成为 Leader** - **没有任何服务器成为 Leader** Raft 算法通过：领导者心跳消息、随机选举超时时间、得到大多数选票才通过原则、任期最新者优先、先来先服务等投票原则，保证了一个任期只有一位领导，也极大地减少了选举失败的情况。 #### 日志复制 ![](https://raw.githubusercontent.com/dunwu/images/master/snap/202405170817072.png) 1. Leader 负责处理所有客户端的请求。 2. Leader 把请求作为日志条目加入到它的日志中，然后并行的向其他服务器发送 `AppendEntries RPC` 请求，要求 Follower 复制日志条目。 3. Follower 复制成功后，返回确认消息。 4. 当这个日志条目被半数以上的服务器复制后，Leader 提交这个日志条目到它的复制状态机，并向客户端返回执行结果。 #### 安全性 - **选举限制**：拥有最新的已提交的日志条目的 Follower 才有资格成为 Leader。 - **提交旧任期的日志条目**：**Raft 永远不会通过计算副本数目的方式去提交一个之前 Term 内的日志条目**。 - **日志压缩**：Raft 采用对整个系统进行快照来解决，快照之前的日志都可以丢弃。以此，避免日志无限膨胀，导致故障恢复过久。 ## ZAB ::: info 扩展阅读 - [**A Simple Totally Ordered Broadcast Protocol**](https://diyhpl.us/~bryan/papers2/distributed/distributed-systems/zab.totally-ordered-broadcast-protocol.2008.pdf) - 概述 ZooKeeper 的全序广播协议（Zab） - [ZooKeeper 简介及核心概念](https://github.com/heibaiying/BigData-Notes/blob/master/notes/Zookeeper%E7%AE%80%E4%BB%8B%E5%8F%8A%E6%A0%B8%E5%BF%83%E6%A6%82%E5%BF%B5.md) - [详解分布式协调服务 ZooKeeper](https://draveness.me/zookeeper-chubby) - [Introduction to Apache ZooKeeper](https://www.slideshare.net/sauravhaloi/introduction-to-apache-zookeeper) - [ZAB 协议](https://dunwu.github.io/waterdrop/pages/da131252/) ::: ### 【困难】ZAB 是怎样工作的？ ::: tip 要点 ZAB 协议是 Zookeeper 专门设计的一种**支持故障恢复的原子广播协议**。 ZAB 协议定义了两个可以**无限循环**的流程： - **`选举 Leader`**：用于故障恢复，从而保证高可用。采用**多数派原则**选举 Leader。 - **`原子广播`**：用于主从同步，从而保证数据一致性。 - Leader 负责所有读写；每次更新事务会有一个唯一标识（**ZXID**） - Leader 会广播同步数据给 Follower，当半数以上 Follower 更新成功，Leader 才会提交数据。 ::: ZAB 协议是 Zookeeper 专门设计的一种**支持故障恢复的原子广播协议**。 ZAB 协议是 ZooKeeper 的数据一致性和高可用解决方案。 ZAB 协议定义了两个可以**无限循环**的流程： - **`选举 Leader`** - 用于故障恢复，从而保证高可用。 - **`原子广播`** - 用于主从同步，从而保证数据一致性。 #### 选举 Leader ZooKeeper 集群采用一主（称为 Leader）多从（称为 Follower）模式，主从节点通过副本机制保证数据一致。 - **如果 Follower 节点挂了** - ZooKeeper 集群中的每个节点都会单独在内存中维护自身的状态，并且各节点之间都保持着通讯，**只要集群中有半数机器能够正常工作，那么整个集群就可以正常提供服务**。 - **如果 Leader 节点挂了** - 如果 Leader 节点挂了，系统就不能正常工作了。此时，需要通过 ZAB 协议的选举 Leader 机制来进行故障恢复。 ZAB 协议的选举 Leader 机制简单来说，就是：基于过半选举机制产生新的 Leader，之后其他机器将从新的 Leader 上同步状态，当有过半机器完成状态同步后，就退出选举 Leader 模式，进入原子广播模式。 #### 原子广播 **ZooKeeper 通过副本机制来实现高可用**。 那么，ZooKeeper 是如何实现副本机制的呢？答案是：ZAB 协议的原子广播。 ![](https://raw.githubusercontent.com/dunwu/images/master/cs/java/javaweb/distributed/rpc/zookeeper/zookeeper_3.png) ZAB 协议的原子广播要求： **_所有的写请求都会被转发给 Leader，Leader 会以原子广播的方式通知 Follow。当半数以上的 Follow 已经更新状态持久化后，Leader 才会提交这个更新，然后客户端才会收到一个更新成功的响应_**。这有些类似数据库中的两阶段提交协议。 在整个消息的广播过程中，Leader 服务器会每个事务请求生成对应的 Proposal，并为其分配一个全局唯一的递增的事务 ID(ZXID)，之后再对其进行广播。 ## Gossip ### 【困难】Gossip 是怎样工作的？ ::: info 扩展阅读 - [Epidemic Algorithms for Replicated Database Maintenance](http://bitsavers.trailing-edge.com/pdf/xerox/parc/techReports/CSL-89-1_Epidemic_Algorithms_for_Replicated_Database_Maintenance.pdf) - [P2P 网络核心技术：Gossip 协议](https://zhuanlan.zhihu.com/p/41228196) - [INTRODUCTION TO GOSSIP](https://managementfromscratch.wordpress.com/2016/04/01/introduction-to-gossip/) - [Goosip 协议仿真动画](https://flopezluis.github.io/gossip-simulator/) ::: ::: tip 要点 Gossip 是一种用于分布式系统节点间信息交换的协议。 Gossip 的设计思想基于**去中心化**和**最终一致性**。 Gossip 协议的工作原理： - **周期性、成对通信**：每个节点每隔一段时间就**随机**选择集群中的另一个节点（这个节点称为“邻居”）。 - **交换信息**：两个节点连接后，会**互相交换**自己拥有的信息（例如，其他节点的状态、存储的数据等）。 - **感染式传播**：接收到新信息的节点，会将这些新信息融入到自己的信息库中。在下一次周期中，它又会成为传染源，将（包含新信息的）所有信息再次传播给其他随机节点。 - **最终一致性**：不需要中央协调，经过一段时间后，通过这种“八卦”式的传播，集群中的所有节点最终都会拥有完全相同的信息。 ::: Gossip 也叫 Epidemic Protocol （流行病协议），这个协议基于**最终一致性**以及**去中心化**设计思想。主要用于**分布式节点之间进行信息交换和数据同步**，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络（去中心化）。 Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。 Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。**异步是它的优点，而消息冗余则是它的缺点**。 Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个**最终一致性**协议。 ![](https://raw.githubusercontent.com/dunwu/images/master/snap/20210708234308.gif) Gossip 有两种类型： - **Anti-Entropy(反熵)**：**以固定的概率传播所有的数据**。反熵时通讯成本会很高，可以通过引入校验和等机制，降低需要对比的数据量和通讯消息等。反熵不适合动态变化或节点数比较多的分布式环境。 - **Rumor-Mongering(谣言传播)**：**仅传播新到达的数据**。谣言传播模型指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。在谣言传播模型下，消息可以发送得更频繁，因为消息只包含最新 update，体积更小。而且，一个谣言消息在某个时间点之后会被标记为 removed，并且不再被传播，因此，谣言传播模型下，系统有一定的概率会不一致。而由于，谣言传播模型下某个时间点之后消息不再传播，因此消息是有限的，系统开销小。