微服务/分布式 基础面试题

算法/协议

说下paxos算法

Paxos 有点类似 2PC，3PC，但比这两种算法更加完善。在很多多大厂都得到了工程实践，比如阿里的 OceanBase 的 分布式数据库， Google 的 chubby 分布式锁 。

Paxos算法是什么？ Paxos 算法是 基于消息传递 且具有 高效容错特性 的一致性算法，目前公认的解决 分布式一致性问题 最有效的算法之一。

Paxos算法的工作流程？

在Paxos中有这么几个角色：

• Proposer（提议者） : 提议者提出提案，用于投票表决。
• Accecptor（接受者） : 对提案进行投票，并接受达成共识的提案。
• Learner（学习者） : 被告知投票的结果，接受达成共识的提案。
  在实际中，一个节点可以同时充当不同角色。

详细可以看这篇文章：Paxos 算法详解

描述一下 ZAB 协议

详情请看ZAB协议

ZAB协议（Zookeeper Atomic Broadcast）是Zookeeper中用于实现分布式一致性的协议。该协议旨在确保分布式系统中的数据一致性和可靠性，并具有以下特点：

• 支持崩溃恢复：当Leader节点崩溃或因其他原因导致Leader缺失时，ZAB协议能够自动进入崩溃恢复模式。在崩溃恢复模式中，系统会重新选举一个新的Leader节点，并确保所有Follower节点的状态与新Leader保持一致，之后继续进行消息广播。
• 原子性保证：ZAB协议确保每个事务请求的原子性，即每个事务要么被所有节点成功执行，要么在所有节点上失败回滚，不会出现部分成功的情况。这是通过两阶段提交过程来实现的。
• 一致性保证：ZAB协议通过多副本同步和消息广播机制，确保集群中所有节点的数据副本在最终状态下是一致的。即使在Leader崩溃或网络分区等异常情况下，也能通过崩溃恢复机制来恢复一致性。

ZAB协议的执行过程包括三个阶段：

1. 准备阶段（Prepare）：Leader节点准备数据（即一个事务提案），并为其分配一个唯一的事务ID（zxid），然后通知所有Follower节点。
2. 提议阶段（Proposal，有时也称为确认阶段，但这里用提议阶段更准确）：Follower节点接收Leader发送的提案和zxid，将其写入本地日志，并准备自己所在的服务（如更新内存状态等）。然后，Follower节点回复一个确认消息（或称为Ack消息）给Leader节点，表示已经接收到并处理了该提案。注意，这里的“确认”是指Follower节点已经准备好处理该提案，而不是指提案已经被提交。
3. 提交阶段（Commit，有时也称为广播阶段，但这里用提交阶段更准确，因为广播通常发生在准备和确认之后）：在收到足够数量的Follower节点的确认消息后（通常是超过半数的Follower节点），Leader节点会广播一个提交消息（Commit消息）给所有的Follower节点。这表示该提案已经被大多数节点接受，并被正式提交到各自的内存树中执行。

如果在确认阶段（或提议阶段），Follower节点没有收到Leader节点的任何消息（包括提案和可能的超时通知），并且无法与Leader节点建立通信，那么这些Follower节点可能会认为Leader已经失效，并可能触发崩溃恢复模式。

然而，崩溃恢复模式通常不是由单个Follower节点单独触发的。实际上，ZooKeeper集群中的节点会通过一种称为“选举算法”的机制来共同决定何时进入崩溃恢复模式，并选举出一个新的Leader节点。

ZAB 和 Paxos 算法的联系与区别

ZAB（ZooKeeper Atomic Broadcast）算法和Paxos算法都是分布式系统中用于实现数据一致性的算法。

两者的主要联系在于它们都采用了类似领导者的选举机制，通过多数派的投票来保证系统的稳定性。在ZAB中，这体现在它使用了一种类似于Paxos的领导者选举过程，其中有一个领导者（leader）来协调多个跟随者（follower）的操作。而在Paxos中，一个提案需要被大多数的进程接受并返回结果，才能被确定。

两者的区别在于它们的目标和实现方式不同：

• 目标：ZAB算法是为了构建一个高可用的分布式数据主备系统（如ZooKeeper），而Paxos算法则是为了构建一个分布式一致性状态机系统。
• 实现方式：ZAB算法使用了消息广播的方式来实现分布式系统的协调，它要求每个消息都必须得到大多数节点的反馈才能确认，从而确保消息的一致性。同时，ZAB算法还引入了一个重要的概念，即消息的epoch，用来保证在领导者出现故障时，能够正确地选择新的领导者。Paxos算法则更加通用，它可以处理更广泛的一致性问题，而不仅仅是消息广播。然而，Paxos算法的实现较为复杂，因为它需要处理多种可能的情况，包括领导者故障、消息丢失等。

综上所述，ZAB和Paxos的联系在于采用了领导者的选举机制和多数派的投票原则，而区别在于它们的目标和实现方式不同。

CAP原则怎么理解

CAP原则是由Eric Brewer提出的分布式系统设计的基本定理。它指出在一个分布式系统中，以下三个特性最多只能同时满足其中两个：

• Consistency（一致性）：所有节点在同一时间具有相同的数据。
• Availability（可用性）：保证每个请求都会收到一个响应，无论响应成功或失败。
• Partition Tolerance（分区容错性）：分区容错性表明系统能够容忍网络中的任意分区或节点失效。当网络节点之间无法通信时，系统仍然必须正常运作。
  在实际应用中，由于网络分区是不可避免的，所以在CAP中通常只能在C和A之间做出选择。

为什么CAP原则最多只能同时满足其中两个？
假设有一个分布式数据库，分布在两个数据中心A和B。如果A和B之间的网络连接断开：

• 如果我们选择保证一致性（C）和分区容错性（P），那么我们必须让至少一个数据中心停止接受写操作，以避免数据不一致，这就牺牲了可用性（A）。
• 如果我们选择保证可用性（A）和分区容错性（P），那么两个数据中心都可以继续独立工作，但可能会导致数据不一致，因此牺牲了一致性（C）。

怎么理解BASE原则

BASE是对CAP中一致性和可用性权衡的结果，它的全称是：

• Basically Available（基本可用）
• Soft state（软状态）
• Eventually consistent（最终一致性）

BASE原则是对CAP中AP的一个延伸，它的主要思想是：

• 基本可用：系统在出现故障时，保证核心可用，允许损失部分可用性。
• 软状态：允许系统中的数据存在中间状态，并认为该状态不会影响系统整体可用性。
• 最终一致性：系统中所有的数据副本，在经过一段时间后，最终能够达到一致的状态。

举一个符合BASE原则场景例子：
在一个大型社交媒体平台上，用户可以在线更新他们的个人状态（例如，发布心情、描述活动等）。该平台有多个数据中心，分布在不同的地理位置，以支持全球用户的低延迟访问。为了能够快速响应用户请求并保持高可用性，该平台选择遵循BASE原则。

符合BASE原则的特征：

1. 基本可用（Basically Available）： 在这个系统中，即使有部分数据中心出现故障，其他数据中心依然可以处理用户的状态更新和查看请求。 用户可以不间断地继续发布状态，而不需要等待所有数据中心同步完成。
2. 软状态（Soft state）： 用户发布的状态信息在传播过程中，允许在短时间内不同数据中心的数据有所不同。 不一致被认为是暂时的，并且在最终一致性（eventual consistency）下会得到解决。
3. 最终一致性（Eventually Consistent）： 虽然在某个时间点，不同的数据中心可能会显示出不同的用户状态，但是随着时间的推移，通过后台的同步和合并机制，所有数据中心最终会达到一致的状态。 系统可能使用异步复制来慢慢将所有数据中心的数据同步一致。

BASE原则是对CAP中一致性和可用性权衡的结果，它通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。

在Java分布式系统开发中，我们经常需要根据具体业务需求来选择适合的原则。例如：

• 对于需要强一致性的场景（如引航交易），可能更倾向于选择CP（一致性和分区容错性）。
• 对于可以容忍短期不一致，但需要高可用的场景（如社交网络的点赞功能），可能更适合选择AP（可用性和分区容错性）并遵循BASE原则。

在实际应用中，我们可能会使用各种技术和框架来实现这些原则，如分布式事务、最终一致性等。理解这些原则对于设计可靠的分布式系统至关重要。

说下Raft算法

Raft 也是一个 一致性算法，和 Paxos 目标相同。但它还有另一个名字 - 易于理解的一致性算法。Paxos 和 Raft 都是为了实现 一致性 产生的。这个过程如同选举一样，参选者 需要说服 大多数选民 (Server) 投票给他，一旦选定后就跟随其操作。Paxos 和 Raft 的区别在于选举的 具体过程 不同。

Raft算法的工作流程？

Raft 协议将 Server 进程分为三种角色：

• Leader（领导者）
• Follower（跟随者）
• Candidate（候选人）

就像一个民主社会，领导者由跟随者投票选出。刚开始没有 领导者，所有集群中的 参与者 都是 跟随者。

那么首先开启一轮大选。在大选期间 所有跟随者 都能参与竞选，这时所有跟随者的角色就变成了 候选人，民主投票选出领袖后就开始了这届领袖的任期，然后选举结束，所有除 领导者 的 候选人 又变回 跟随者 服从领导者领导。

这里提到一个概念 「任期」，用术语 Term 表达。

Leader选举过程

Raft 使用心跳（heartbeat）触发Leader选举。当Server启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC 。结果有以下三种情况：

• 赢得了多数（超过1/2）的选票，成功选举为Leader；
• 收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；
• 没有Server赢得多数的选票，Leader选举失败，等待选举时间超时（Election Timeout）后发起下一次选举。

选出 Leader 后，Leader 通过 定期 向所有 Follower 发送 心跳信息 维持其统治。若 Follower 一段时间未收到 Leader 的 心跳，则认为 Leader 可能已经挂了，然后再次发起 选举 过程。

什么是分布式系统

一个系统 各组件分别部署在不同服务器。彼此通过网络通信和协调的系统。

• 可以指多个不同组件分布在网络上互相协作，比如说电商网站
• 也可以一个组件的多个副本组成集群，互相协作如同一个组件，比如数据存储服务中为了数据不丢失而采取的多个服务备份冗余，当数据修改时也需要通信来复制数据

分布式最早出现的目地首先是解决单点问题，避免单点故障，然后解决了性能问题。

什么是分布式事务

分布式事务是相对本地事务而言的，对于本地事务，利用数据库本身的事务机制，就可以保证事务的ACID特性。

而在分布式环境下，会涉及到多个数据库。

分布式事务其实就是将对同一库事务的概念扩大到了对多个库的事务。目的是为了保证分布式系统中的数据一致性。

分布式事务处理的关键是：

• 需要记录事务在任何节点所做的所有动作；
• 事务进行的所有操作要么全部提交，要么全部回滚。

分布式事务有哪些常见的实现方案

详情可以看分布式事务实现方案

有哪些分布式锁的实现方案

一般需要使用分布式锁的场景如下：

• 效率：使用分布式锁可以避免不同节点重复相同的工作，比如避免重复执行定时任务等；
• 正确性：使用分布式锁同样可以避免破坏数据正确性，如果两个节点在同一条数据上面操作，可能会出现并发问题。

分布式锁特点

一个完善的分布式锁需要满足以下特点：

• 互斥性：互斥是所得基本特性，分布式锁需要按需求保证线程或节点级别的互斥。；
• 可重入性：同一个节点或同一个线程获取锁，可以再次重入获取这个锁；
• 锁超时：支持锁超时释放，防止某个节点不可用后，持有的锁无法释放；
• 高效性：加锁和解锁的效率高，可以支持高并发；
• 高可用：需要有高可用机制预防锁服务不可用的情况，如增加降级；
• 阻塞性：支持阻塞获取锁和非阻塞获取锁两种方式；
• 公平性：支持公平锁和非公平锁两种类型的锁，公平锁可以保证安装请求锁的顺序获取锁，而非公平锁不可以。

分布式锁常见的实现有三种实现：

• 基于数据库的分布式锁；
• 基于Redis的分布式锁；
• 基于Zookeeper的分布式锁。

基于数据库的分布式锁

用数据库实现分布式锁比较简单，就是创建一张锁表，数据库对字段作唯一性约束。

加锁的时候，在锁表中增加一条记录即可；释放锁的时候删除记录就行。

如果有并发请求同时提交到数据库，数据库会保证只有一个请求能够得到锁。

这种属于数据库 IO 操作，效率不高，而且频繁操作会增大数据库的开销，因此这种方式在高并发、高性能的场景中用的不多。

上面列举出了分布式锁需要满足的特点，使用数据库实现分布式锁也需要满足这些特点，下面我们来一一介绍实现方法：

• 互斥性：通过数据库update的原子性达到两次获取锁之间的互斥性；
• 可重入性：在数据库中保留一个字段存储当前锁的持有者；
• 锁超时：在数据库中存储锁的获取时间点和超时时长；
• 高效性：数据库本身可以支持比较高的并发；
• 高可用：可以增加主从数据库逻辑，提升数据库的可用性；
• 阻塞性：可以通过看门狗轮询的方式实现线程的阻塞；
• 公平性：可以添加锁队列，不过不建议，实现起来比较复杂。

数据库的表名为lock，各个字段的定义如下所示：

获取锁的SQL语句 ：获取锁的SQL语句分不同的情况，如果锁不存在，那么首先需要创建锁，并且创建锁的线程可以获取锁：

insert into lock(lock_key,lock_time,lock_duration,lock_owner,locked) values ('xxx',now(),1000,'ownerxxx',true)

如果锁已经存在，那么就尝试更新锁的信息，如果更新成功则表示获取锁成功，更新失败则表示获取锁失败。

update lock set
	locked = true,
	lock_owner = 'ownerxxxx',
	lock_time = now(),
	lock_duration = 1000
where
	lock_key='xxx' and(
	lock_owner = 'ownerxxxx' or
	locked = false or
	date_add(lock_time, interval lock_duration second) > now())

释放锁的SQL语句 当用户使用完锁需要释放的时候，可以直接更新locked标识位为false。

update lock set
	locked = false,
where
	lock_key='xxx' and
	lock_owner = 'ownerxxxx' and
	locked = true

看门狗

通过上面的步骤，可以实现获取锁和释放锁，那么看门狗又是做什么的呢？

想象一下，如果用户获取锁到释放锁之间的时间大于锁的超时时间，是不是会有问题？是不是可能会出现多个节点同时获取锁的情况？这个时候就需要看门狗了，看门狗可以通过定时任务不断刷新锁的获取事件，从而在用户获取锁到释放锁期间保持一直持有锁。

基于Redis的分布式锁

Redis的Java客户端Redisson实现了分布式锁，我们可以通过类似ReentrantLock的加锁-释放锁的逻辑来实现分布式锁。

详情可以看redis实现分布式锁

基于Zookeeper的分布式锁

Zookeeper实现的分布式锁适用于引入Zookeeper的服务

详情可以看zk实现分布式锁

三种锁的优缺点

基于数据库的分布式锁：

• 数据库并发性能较差；
• 阻塞式锁实现比较复杂；
• 公平锁实现比较复杂。

基于Redis的分布式锁：

• 主从切换的情况下可能出现多客户端获取锁的情况；
• Lua脚本在单机上具有原子性，主从同步时不具有原子性。

基于Zookeeper的分布式锁：

• 需要引入Zookeeper集群，比较重量级；
• 分布式锁的可重入粒度只能是节点级别；

了解哪些限流算法

详情可以看请求限流算法

• 计数器

计数器比较简单粗暴，比如我们要限制1s能够通过的请求数，实现的思路就是从第一个请求进来开始计时，在接下来的1s内，每个请求进来请求数就+1，超过最大请求数的请求会被拒绝，等到1s结束后计数清零，重新开始计数。

这种方式有个很大的弊端：比如前10ms已经通过了最大的请求数，那么后面的990ms的请求只能拒绝，这种现象叫做“突刺现象”。

• 漏桶算法

就是桶底出水的速度恒定，进水的速度可能快慢不一，但是当进水量大于出水量的时候，水会被装在桶里，不会直接被丢弃；但是桶也是有容量限制的，当桶装满水后溢出的部分还是会被丢弃的。

算法实现：可以准备一个队列来保存暂时处理不了的请求，然后通过一个线程池定期从队列中获取请求来执行。

• 令牌桶算法

令牌桶就是生产访问令牌的一个地方，生产的速度恒定，用户访问的时候当桶中有令牌时就可以访问，否则将触发限流。

实现方案：Guava RateLimiter是一个谷歌提供的限流，其基于令牌桶算法，比较适用于单实例的系统。

说说什么是幂等性

详情可以看幂等性

你了解时间轮(Time Wheel)吗?有哪些应用场景?

时间轮(Time Wheel)是一种用于管理和调度大量定时任务的数据结构。它是一种高效的定时任务调度算法，主要用于优化任务调度的效率，特别是在需要处理大量定时任务时。时间轮是一种环形的数据结构，通过将时间划分为若干个时间片(槽)，每个时间片负责管理一定时间段(如秒、分钟等内 的任务。

工作原理：

• 时间轮的中心是一个环形结构，每个槽表示一个时间段。当时间轮的指针移动到某个槽时，该槽中的任务会被执行。
• 任务被插入到特定的槽中，根据任务的延迟时间确定插入的位置。
• 时间轮以固定的时间步长(如秒)推进，每次推进一个时间单位，执行相应中的任务

应用场景

• 高效的定时任务调度：在需要处理大量定时任务的场景，如高并发的定时任务系统，时间轮可以有效地减少任务调度的开销。
• 网络服务器：在网络服务器中，时间轮常用于实现定时操作，如连接超时、请求超时等。
• 分布式系统：在分布式系统中，时间轮可以用于协调不同节点的定时任务，优化任务调度和超时处理

实际应用示例:

• Netty：Netty 是一个高性能的网络框架，它使用时间轮来管理定时任务，如超时处理和定时操作。
• Guava：Google 的 Guava 库中也有时间轮的实现，用于优化定时任务调度的性能。
• Caffine Cache：这个高性能本地缓存库中也有时间轮的实现，即 TimerWheel。