分布式综合面试
分布式综合面试
逻辑时钟
扩展：
- Time, Clocks, and the Ordering of Events in a Distributed System，译文，解读 - Lamport 介绍 happened before、偏序关系（partial ordering）、逻辑时钟（Logical Clocks）概念，提出解决分布式系统中区分事件发生的时序问题的方法。
- Virtual Time and Global States of Distributed Systems，解读 - 逻辑时钟无法描述事件的因果关系。本文提出了向量时钟，这种算法利用了向量这种数据结构将全局各个进程的逻辑时间戳广播给各个进程，通过向量时间戳就能够比较任意两个事件的因果关系。
- 逻辑时钟 - 如何刻画分布式中的事件顺序
【初级】为什么需要逻辑时钟？
要点
经典问题
- 为什么需要逻辑时钟？
- 分布式系统中以系统时间来确定事件顺序有什么问题？
知识点
不同节点的物理时钟无法完全保持一致。即使引入一个全局时钟（例如：NTP）来进行校准，由于网络通信延迟的不确定性，以及时钟计时的偏差，无法保证每个节点的时间完全一致。
在分布式系统中，由于网络通信延迟的不确定性， 仅仅以接收顺序作为整个分布式系统中事件的发生顺序是不可取的。
【中级】什么是偏序？什么是全序？
要点
全序和偏序是数学上的术语，按照数学内容阐述比较晦涩，简单来说：
- 偏序是部分可比较的有序关系。
- 全序是在偏序基础上，要求全部元素必须可比较的有序关系。
【高级】什么是逻辑时钟？
要点
经典问题
- 什么是逻辑时钟？
- 逻辑时钟是如何工作的？
知识点
1978 年，Lamport 在 Time, Clocks, and the Ordering of Events in a Distributed System 中提出了逻辑时钟的概念，来解决分布式系统中区分事件发生的时序问题。
逻辑时钟并不度量时间本身，仅区分事件发生的前后顺序。
分布式系统中按是否存在节点交互可分为三类事件，一类发生于节点内部，二是发送事件，三是接收事件。Lamport 时间戳原理如下：
- 每个事件对应一个 Lamport 计数器，初始值为 0
- 如果事件在节点内发生，计数器加 1
- 如果事件属于发送事件，计数器加 1 并在消息中带上该计数器
- 如果事件属于接收事件，计数器 = Max(本地计数器，消息中的计数器) + 1
综上，Lamport 逻辑时钟构建了一个全序时钟来描述事件顺序。
Lamport 逻辑时钟的缺陷是无法描述同时发生的事件。
扩展：
Time, Clocks, and the Ordering of Events in a Distributed System
【高级】什么是向量时钟？
要点
向量时钟其实是在逻辑时钟的基础上进行了演进，算法逻辑类似，只是不仅记录了本节点的时间戳，还记录了其他节点的时间戳。其本质在于将逻辑时钟的全序计数器改造为向量时钟的偏序大小关系：向量有序，则事件有序；向量平行，则事件并发。
向量时钟可以发现数据冲突，但不能解决数据冲突。
【高级】什么是版本向量时钟？
要点
在向量时钟算法中， 消息传播后，发送方的向量一定会小于接收者的向量， 是因为接收者对齐了发送者的原因。
版本向量在此基础上，做了一点加强：消息传播后，发送方也对齐接收者的向量，也就是双向对齐，在版本向量中，叫做同步。
发送消息和接收消息的时候不再自增向量中的自己的计数器，而是只做双方的向量对齐操作。 也就是，只有在更新数据的时候做向量自增。
一致性
【初级】什么是强一致性？什么是弱一致性？什么是最终一致性？
要点
一致性（Consistency）指的是多个数据副本是否能保持一致的特性。
数据一致性又可以分为以下几点：
- 强一致性 - 数据更新操作结果和操作响应总是一致的，即操作响应通知更新失败，那么数据一定没有被更新，而不是处于不确定状态。通俗的说，分布式系统在执行写操作成功后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。
- 弱一致性 - 系统在写入数据成功后，不承诺立即能读到最新的值，也不承诺什么时候能读到，但是过一段时间之后用户可以看到更新后的值。那么用户读不到最新数据的这段时间被称为“不一致窗口时间”。
- 最终一致性 - 最终一致性作为弱一致性中的特例，强调的是所有数据副本，在经过一段时间的同步后，最终能够到达一致的状态，不需要实时保证系统数据的强一致性。
【初级】什么是 ACID？
要点
ACID 是数据库事务正确执行的四个基本要素的单词缩写：
- 原子性（Atomicity）
- 原子是指不可分解为更小粒度的东西。事务的原子性意味着：事务中的所有操作要么全部成功，要么全部失败。
- 回滚可以用日志来实现，日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。
- 一致性（Consistency）
- 数据库在事务执行前后都保持一致性状态。
- 在一致性状态下，所有事务对一个数据的读取结果都是相同的。
- 隔离性（Isolation）
- 同时运行的事务互不干扰。换句话说，一个事务所做的修改在最终提交以前，对其它事务是不可见的。
- 持久性（Durability）
- 一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。
- 可以通过数据库备份和恢复来实现，在系统发生奔溃时，使用备份的数据库进行数据恢复。
一个支持事务（Transaction）的数据库系统，必需要具有这四种特性，否则在事务过程（Transaction processing）当中无法保证数据的正确性。
- 只有满足一致性，事务的执行结果才是正确的。
- 在无并发的情况下，事务串行执行，隔离性一定能够满足。此时只要能满足原子性，就一定能满足一致性。
- 在并发的情况下，多个事务并行执行，事务不仅要满足原子性，还需要满足隔离性，才能满足一致性。
- 事务满足持久化是为了能应对系统崩溃的情况。
CAP & BASE
扩展：
- Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services，解读 - 经典的 CAP 定理，即：在一个分布式系统中，当发生网络分区时，那么强一致性和可用性只能二选一。
- CAP Twelve Years Later: How the “Rules” Have Changed, 解读 - CAP 定理的新解读，并阐述 CAP 定理的一些常见误区。
- BASE: An Acid Alternative，译文 - BASE 定理是对 CAP 中一致性和可用性的权衡，提出采用适当的方式来使系统达到最终一致性。
【中级】什么是 CAP 定理？
要点
CAP 定理提出：分布式系统有三个指标，这三个指标不能同时做到：
- 一致性（Consistency） - 在任何给定时间，网络中的所有节点都具有完全相同（最近）的值。
- 可用性（Availability） - 对网络的每个请求都会返回响应，但不能保证返回的数据是最新的。
- 分区容错性（Partition Tolerance） - 即使任意数量的节点出现故障，网络仍会继续运行。
CAP 就是取 Consistency、Availability、Partition Tolerance 的首字母而命名。
在分布式系统中，分区容错性是一个既定的事实：因为分布式系统总会出现各种各样的问题，如由于网络原因而导致节点失联；发生机器故障；机器重启或升级等等。因此，CAP 定理实际上是要在可用性（A）和一致性（C）之间做权衡。
扩展：Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services，解读 - 经典的 CAP 定理，即：在一个分布式系统中，当发生网络分区时，那么强一致性和可用性只能二选一。
【中级】选择 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 定理真的正确吗？
要点
CAP 定理在分布式系统领域大名鼎鼎，以至于被很多人视为了真理。然而，CAP 定理真的正确吗？
网络分区是一种故障，不管喜欢还是不喜欢，它都可能发生，所以无法选择或逃避分区的问题。在网络正常的时候，系统可以同时保证一致性（线性化）和可用性。而一旦发生了网络故障，必须要么选择一致性，要么选择可用性。因此，对 CAP 更准确的理解应该是：当发生网络分区（P）的情况下，可用性（A）和一致性（C）二者只能选其一。
CAP 定理所描述的模型实际上局限性很大，它只考虑了一种一致性模型和一种故障（网络分区故障），而没有考虑网络延迟、节点失效等情况。因此，它对于指导一个具体的分布式系统设计来说，没有太大的实际价值。
值得一提的是，在 CAP 定理提出十二年之后，其提出者也发表了一篇文章 CAP Twelve Years Later: How the “Rules” Have Changed，来阐述 CAP 定理的局限性。
扩展：- CAP Twelve Years Later: How the “Rules” Have Changed, 解读 - CAP 定理的新解读，并阐述 CAP 定理的一些常见误区。
【中级】什么是 BASE 定理？
要点
BASE 是 基本可用（Basically Available）、软状态（Soft State） 和 最终一致性（Eventually Consistent） 三个短语的缩写。BASE 定理是对 CAP 定理中可用性（A）和一致性（C）权衡的结果。
BASE 定理的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。
ACID 要求强一致性，通常运用在传统的数据库系统上。而 BASE 要求最终一致性，通过牺牲强一致性来达到可用性，通常运用在大型分布式系统中。
在实际的分布式场景中，不同业务单元和组件对一致性的要求是不同的，因此 ACID 和 BASE 往往会结合在一起使用。
扩展：- BASE: An Acid Alternative，译文 - BASE 定理是对 CAP 中一致性和可用性的权衡，提出采用适当的方式来使系统达到最终一致性。
Paxos
扩展：
【高级】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 个阶段负责协商并达成共识：
- 准备（Prepare）阶段：Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。
- 接受（Accept）阶段：Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的 Propose 请求进行 Accept 处理。
- 学习（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
扩展：
【高级】Raft 是怎样工作的？
要点
Raft 是一种为了管理日志复制的分布式共识性算法。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。
Raft 出现之前，Paxos 一直是分布式共识性算法的标准。Paxos 难以理解，更难以实现。Raft 的设计目标是简化 Paxos，使得算法既容易理解，也容易实现。
Raft 将一致性问题分解成了三个子问题：
- 选举 Leader
- 日志复制
- 安全性
Raft 概念
（1）服务器角色
在 Raft 中，任何时刻，每个服务器都处于这三个角色之一 ：
Leader- 领导者，通常一个系统中是一主（Leader）多从（Follower）。Leader 负责处理所有的客户端请求。Follower- 跟随者，不会发送任何请求，只是简单的 响应来自 Leader 或者 Candidate 的请求。Candidate- 参选者，选举新 Leader 时的临时角色。
（2）任期
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 算法通过：领导者心跳消息、随机选举超时时间、得到大多数选票才通过原则、任期最新者优先、先来先服务等投票原则，保证了一个任期只有一位领导，也极大地减少了选举失败的情况。
日志复制
- Leader 负责处理所有客户端的请求。
- Leader 把请求作为日志条目加入到它的日志中，然后并行的向其他服务器发送
AppendEntries RPC请求，要求 Follower 复制日志条目。 - Follower 复制成功后，返回确认消息。
- 当这个日志条目被半数以上的服务器复制后，Leader 提交这个日志条目到它的复制状态机，并向客户端返回执行结果。
安全性
- 选举限制：拥有最新的已提交的日志条目的 Follower 才有资格成为 Leader。
- 提交旧任期的日志条目：Raft 永远不会通过计算副本数目的方式去提交一个之前 Term 内的日志条目。
- 日志压缩：Raft 采用对整个系统进行快照来解决，快照之前的日志都可以丢弃。以此，避免日志无限膨胀，导致故障恢复过久。
ZAB
扩展：
【高级】ZAB 是怎样工作的？
要点
ZAB 协议是 Zookeeper 专门设计的一种支持故障恢复的原子广播协议。
ZAB 协议是 ZooKeeper 的数据一致性和高可用解决方案。
ZAB 协议定义了两个可以无限循环的流程：
选举 Leader- 用于故障恢复，从而保证高可用。原子广播- 用于主从同步，从而保证数据一致性。
选举 Leader
ZooKeeper 集群采用一主（称为 Leader）多从（称为 Follower）模式，主从节点通过副本机制保证数据一致。
- 如果 Follower 节点挂了 - ZooKeeper 集群中的每个节点都会单独在内存中维护自身的状态，并且各节点之间都保持着通讯，只要集群中有半数机器能够正常工作，那么整个集群就可以正常提供服务。
- 如果 Leader 节点挂了 - 如果 Leader 节点挂了，系统就不能正常工作了。此时，需要通过 ZAB 协议的选举 Leader 机制来进行故障恢复。
ZAB 协议的选举 Leader 机制简单来说，就是：基于过半选举机制产生新的 Leader，之后其他机器将从新的 Leader 上同步状态，当有过半机器完成状态同步后，就退出选举 Leader 模式，进入原子广播模式。
原子广播
ZooKeeper 通过副本机制来实现高可用。
那么，ZooKeeper 是如何实现副本机制的呢？答案是：ZAB 协议的原子广播。
ZAB 协议的原子广播要求：
所有的写请求都会被转发给 Leader，Leader 会以原子广播的方式通知 Follow。当半数以上的 Follow 已经更新状态持久化后，Leader 才会提交这个更新，然后客户端才会收到一个更新成功的响应。这有些类似数据库中的两阶段提交协议。
在整个消息的广播过程中，Leader 服务器会每个事务请求生成对应的 Proposal，并为其分配一个全局唯一的递增的事务 ID(ZXID)，之后再对其进行广播。
Gossip
【高级】Gossip 是怎样工作的？
扩展：
要点
Gossip 也叫 Epidemic Protocol （流行病协议），这个协议基于最终一致性以及去中心化设计思想。主要用于分布式节点之间进行信息交换和数据同步，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络（去中心化）。
Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。
Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。异步是它的优点，而消息冗余则是它的缺点。
Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。
Gossip 有两种类型：
- Anti-Entropy(反熵)：以固定的概率传播所有的数据。反熵时通讯成本会很高，可以通过引入校验和等机制，降低需要对比的数据量和通讯消息等。反熵不适合动态变化或节点数比较多的分布式环境。
- Rumor-Mongering(谣言传播)：仅传播新到达的数据。谣言传播模型指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。在谣言传播模型下，消息可以发送得更频繁，因为消息只包含最新 update，体积更小。而且，一个谣言消息在某个时间点之后会被标记为 removed，并且不再被传播，因此，谣言传播模型下，系统有一定的概率会不一致。而由于，谣言传播模型下某个时间点之后消息不再传播，因此消息是有限的，系统开销小。