分布式理论

CAP原则的理解与解析

CAP原则又称为CAP定理，表示在一个分布式系统中，Consistency（一致性）、Availability（可用性）和Partition tolerance（分区容错性）这三项基本需求中，最多只能同时满足其中的两项。

CAP原则详解

选项	描述
Consistency（一致性）	数据在多个副本之间保持一致的特性（严格的一致性）。
Availability（可用性）	系统能始终提供服务，每次请求都能得到非错误的响应（不保证获取数据的时效性）。
Partition tolerance（分区容错性）	在网络分区故障的情况下，分布式系统仍能提供一致性和可用性的服务，除非整个网络都出现故障。

CAP原则为什么不可兼得？

在分布式系统中，分区是不可避免的，所谓的分区是指分布式系统中可能出现的网络隔离情况。

分区的概念

因此，分区容错性（P）必须得以满足。如果牺牲分区容错性，意味着将服务和资源集中在一个节点或同一集群，这样会违背分布式系统的初衷。

在满足分区容错性的前提下，能否同时保障一致性和可用性呢？

设想有两个分区N1和N2，各自存储不同的数据D1和D2并提供服务S1和S2。

在保证一致性的情况下，N1和N2的数据需保持相同，即D1=D2。
在保证可用性的情况下，无论请求N1还是N2，都需及时响应。

分区的服务

假设用户访问了N1并对D1进行了修改，随后再次请求时落在了N2，此时D1和D2的数据不匹配。

接下来的情况是：

若要保证一致性，则D1和D2务必保持一致，不能返回不一致的数据，因此可用性将无法保障。
若要保证可用性，系统需迅速响应，但此时返回的数据将与D1不一致，因此一致性无法得到保障。

由此可见，在满足分区容错的前提下，一致性和可用性之间是存在矛盾的。

CAP原则的模型及应用场景

CA without P

理论上放弃P（分区容错性），可以保证C（强一致性）和A（可用性）。实际应用中，分区是不可避免的，因此严格的CA指的是在允许分区的情况下，子系统依然维持CA特性。

CA模型的常见应用包含：

集群数据库
xFS文件系统

CP without A

放弃A（可用性），意味着每个请求需在服务器间保持强一致，而P（分区）可能导致同步时间无限延长，这样CP也是可以保障的。许多传统的数据库分布式事务属于这种模式。

CP模型的常见应用包括：

分布式数据库
分布式锁

AP without C

为了实现高可用且允许分区，则必须放弃一致性。当分区发生时，节点间可能失去联系，为了高可用，每个节点只能使用本地数据提供服务，从而导致全局数据不一致。当前许多NoSQL解决方案均属于此类。

AP模型的常见应用包括：

Web缓存
DNS

在我们熟悉的注册中心如ZooKeeper、Eureka、Nacos中：

ZooKeeper保障的是CP模型
Eureka则是AP模型
Nacos同时支持CP和AP模型

BASE理论的概述

BASE（Basically Available、Soft state、Eventual consistency）是基于CAP理论演变而来的，其核心思想是在不能实现强一致性（Strong consistency）的情况下，依据应用特性采用适当方式实现最终一致性（Eventual consistency）。

BASE的主要含义包含：

Basically Available（基本可用）

即使系统发生不可预见的故障，仍应能保持可用性，只是响应时间可能变慢，或功能可能降低。

Soft State（软状态）

与硬状态的要求不同，软状态允许系统中的数据处于中间状态，而不影响系统的整体可用性，允许多个节点的数据副本存在延迟。

Eventually Consistent（最终一致性）

虽然允许存在软状态，但在一定时间内，系统应达到最终状态以确保所有副本数据一致，所需时间取决于网络延迟、系统负载及数据复制方案等因素。

分布式锁

在单体应用时代，通常可以直接使用本地锁来管理竞争资源，而在分布式环境中就需要使用分布式锁。

常见的分布式锁实现方案

分布式锁的实现方案主要有三种：MySQL分布式锁、ZooKeeper分布式锁、Redis分布式锁。

分布式锁概述

1. MySQL分布式锁的实现方式

使用数据库实现分布式锁相对简单，只需创建一张锁表，对字段进行唯一性约束。

加锁时，向锁表插入一条记录；释放锁时，删除对应记录。

对于并发请求，数据库会确保只有一个请求能获得锁。这种方式的效率不高，且频繁操作会增加数据库负担，因此在高并发场景中不常用。

2. ZooKeeper的分布式锁实现

ZooKeeper也是常见的分布式锁实现方法。ZooKeeper的数据节点和文件目录相似，例如创建一个锁节点，子节点可确保先后顺序，即使两个进程同时请求创建节点，也会按顺序生成节点。

ZooKeeper的分布式锁实现

通过这种特性，可以实现分布式锁。一个资源作为目录，目录下的节点为需要获取锁的客户端。每个服务在该目录下创建节点，若其节点序号最小则获取锁，否则等待。释放锁的方式为删除服务创建的节点。

ZooKeeper是一个相对较重的分布式组件，因此用ZooKeeper实现分布式锁的实际应用较少。

3. Redis的分布式锁实现

Redis是当前应用最广泛的分布式锁实现方式。Redis的单线程特性使得其能够高效实现分布式锁，最简单的实现命令为：setNx（若不存在则设置）：

setNx resourceName value

为了避免机器宕机导致锁无法释放，需要设置过期时间，并将过期时间和setNx操作合并为原子操作。在Redis 2.8之前，需要使用Lua脚本，而在Redis 2.8之后，支持将nx和ex操作合并为一个原子操作：

set resourceName value ex 5 nx

Redisson

在实际生产中，通常使用Redisson客户端，它良好地封装了分布式锁的API，并支持RedLock机制。

分布式事务

分布式事务的定义

分布式事务是与本地事务相对的概念。本地事务利用数据库的内建事务机制即可保证事务的ACID特性。

ACID特性

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

多数据库场景

分布式事务就是将对同一数据库的事务概念扩展至多个数据库，目的是确保分布式系统中的数据一致性。

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

记录事务在任何节点执行的所有操作；
所有操作要么完全提交，要么完全回滚。

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

分布式事务的常见实现方案包括 2PC、3PC、TCC、本地消息表、MQ消息事务、最大努力通知、SAGA事务等。

1. 2PC（两阶段提交）

提到2PC，必须先介绍分布式事务中的XA协议。该协议涉及三个角色：

AP（Application）：应用系统（服务）
TM（Transaction Manager）：事务管理器（全局事务管理）
RM（Resource Manager）：资源管理器（数据库）

XA协议详解

XA协议采用两阶段提交方式管理分布式事务。XA接口提供资源管理器与事务管理器之间的标准通信接口。

两阶段提交思路概括为：参与者将操作成功与否反馈给协调者，由协调者决定各参与者是否提交或回滚操作。

2PC流程

准备阶段：事务管理器要求每个参与事务的数据库进行预提交并反馈是否可以提交。
提交阶段：事务协调器要求每个数据库提交数据或执行回滚操作。

优点：尽可能确保数据强一致性，且实现成本低，主流数据库均支持。

缺点:

单点故障：事务管理器在整个流程中至关重要，一旦其宕机，比如在第一阶段完成而第二阶段准备提交时宕机，资源管理器将一直阻塞，导致数据库不可用。
同步阻塞：在准备完成后，资源管理器中的资源将处于阻塞状态，直到提交完成释放资源。
数据不一致性：尽管两阶段提交协议旨在实现强一致性，但仍可能出现数据不一致性，比如在第二阶段中，若协调者发出提交通知，但网络问题导致部分参与者未接收到通知，造成数据不一致性。

2. 3PC（三阶段提交）

三阶段提交（3PC）是二阶段提交（2PC）的改进版本，旨在解决两阶段提交中的单点故障和同步阻塞问题。

三阶段提交包含三个阶段：CanCommit、PreCommit、DoCommit。

3PC流程

CanCommit：准备阶段。协调者向参与者发送提交请求，参与者如能提交则返回“Yes”，否则返回“No”。
PreCommit：预提交阶段。协调者依据参与者在准备阶段的响应判断是否执行事务或中断，参与者执行完操作后返回ACK响应，等待最终指令。
DoCommit：提交阶段。协调者依据参与者的反馈决定是否提交或中断事务：
- 当所有参与者都返回正确的ACK响应时，则提交事务；
- 若有一个或多个参与者返回错误的ACK响应或超时，则中断事务；
- 若参与者未能及时接收到协调者的请求，则在等待超时后继续提交事务。

需要注意的是，无论是2PC还是3PC都无法保证分布式系统中数据的100%一致性。

3. TCC（Try Confirm Cancel）

TCC是两阶段提交的一种变种，为每个操作设置对应的确认和取消操作，操作成功时调用确认，失败时调用取消。可以视为对业务的补偿机制。

TCC下单与减库存

Try：执行待处理的业务。订单系统将当前订单状态设为支付中，库存系统检查剩余库存。
Confirm：确认执行业务。若Try阶段成功，接着执行Confirm，将订单状态改为支付成功，库存剩余量更新。
Cancel：取消待执行的业务。若Try阶段失败，执行Cancel，将订单状态设为支付失败，库存数量恢复。

TCC致力于实现业务层面的分布式事务，确保最终一致性，且不会长时间持有资源锁。

优点：将数据库层的二阶段提交转移至应用层，降低2PC的性能瓶颈问题。
缺点：TCC的Try、Confirm和Cancel操作需由业务提供，开发成本高，且与业务逻辑紧密耦合。

4. 本地消息表

本地消息表的核心思想是将分布式事务拆分为本地事务处理。

例如，在订单库中新增一个消息表，将新增订单与新增消息放入同一事务中，通过轮询查询消息表，将消息推送至MQ，由库存服务消费。

本地消息表的流程

执行流程：

订单服务在本地消息表中添加订单和消息，执行一个事务。
订单服务定时查询未同步的消息，将其发送至MQ，失败则重试。
库存服务接收MQ消息并更新库存表，确保幂等操作。
修改成功后，调用接口更新消息状态为已完成或删除消息。
若修改失败，则可不做处理，等待重试。

此方案实现了最终一致性，但需在业务系统中添加消息表，导致性能损耗。

5. MQ消息事务

MQ消息事务的原理在于通过消息中间件异步解耦两个事务。

订单服务执行本地事务并发送MQ消息，库存服务接收并执行本地事务。表面上与本地消息表类似，省去了本地消息表的操作和MQ的轮询发送，但实现机制不同。

消息事务必须确保业务操作与消息发送的一致性，若业务成功，消息也需成功投递。

MQ消息事务的执行流程

执行流程：

向消息中间件发送prepare消息。
发送成功后，执行本地事务。
若事务成功，则commit，消息中间件将消息发送至消费端；
若事务失败，则回滚，消息中间件删除prepare消息。
消费端接收到消息后进行处理，处理失败则重试。

消息事务依赖于支持事务消息的消息中间件，例如RocketMQ。

此方案实现了最终一致性，相较本地消息表，性能损耗和业务入侵更小。

6. 最大努力通知

最大努力通知的实现相对简单，适用于对最终一致性实时性要求不高的业务，如支付通知和短信通知。

以支付通知为例，业务系统调用支付平台进行支付，支付平台完成支付后，异步通知业务系统支付结果，如通知失败则重试，但设定最大通知次数，超出后不再通知，业务系统需自行查询支付结果。

最大努力通知的执行流程

执行流程：

业务系统调用支付接口，并记录状态为支付中；
支付平台完成支付后，无论成功与否，向业务系统同步结果；
若通知失败，则根据重试规则异步重试，达到最大通知次数后不再通知；
支付平台提供查询接口，供业务系统查询支付结果；
业务系统依据业务规则查询支付结果。

7. Seata的使用

Seata是一个流行的分布式事务调度工具，实现分布式事务调度较为复杂。

Seata的设计目标是对业务无侵入，因此它基于无侵入的两阶段提交（全局事务）。Seata理解分布式事务为包含多个分支事务的全局事务，旨在协调分支事务达成一致性，实现成功提交或回滚。

全局事务与分支事务

Seata中的重要角色包括：

TC（Transaction Coordinator）：负责管理全局分支事务的状态，协调全局事务的提交和回滚。
TM（Transaction Manager）：用于开启、提交或回滚事务。
RM（Resource Manager）：对分支事务的资源进行管理，注册分支事务并反馈状态。

Seata的工作流程

Seata的整体执行流程如下：

服务A中的TM向TC申请开启一个全局事务，TC创建该全局事务并返回唯一的XID。
服务A中的RM向TC注册分支事务，将该分支事务纳入XID对应的全局事务。
服务A开始执行分支事务。
服务A开始远程调用B服务，此时XID传播至下游。
服务B中的RM向TC注册分支事务，纳入XID对应的全局事务。
服务B开始执行分支事务。
全局事务结束后，TM依据异常情况，向TC提交或回滚全局事务。
TC协调所有分支事务，决定提交或回滚。

分布式一致性算法

Paxos算法的理解与应用

Paxos算法与2PC、3PC类似，但更为完备，被许多大型公司应用于工程实践中，如阿里的OceanBase分布式数据库、Google的Chubby分布式锁。

Paxos算法概述

Paxos算法是基于消息传递并具备高效容错特性的一致性算法，被广泛认为是解决分布式一致性问题的有效方案。

Paxos算法的角色

在Paxos中，涉及以下角色：

Proposer（提议者）：负责提出提案并进行投票表决。
Acceptor（接受者）：对提案进行投票，并接受达成共识的提案。
Learner（学习者）：接受和学习投票结果。

在实际应用中，一个节点可以兼任多种角色。

Paxos的角色分配

提议者提出提案，提案由编号和值构成，可以表示为[M,V]，每个提案均具有唯一编号且其编号遵循递增规律。

Paxos算法的流程

Paxos算法分为两个阶段：Prepare（准备）与Accept（接受）。

Paxos算法流程

Prepare（准备）阶段

提议者提出新的提案P[Mn，?]，向超过半数的接受者发送编号为Mn的准备请求。
若接受者收到编号为Mn的请求且其编号大于之前所有响应的编号，则其将反馈最大已批准提案的编号及值，并承诺不再批准小于Mn的任何提案。

总结来说，接受者在接收到提案后，会做出两个承诺和一个应答：

两个承诺：
- 不再接受编号小于或等于Mn的Prepare请求；
- 不再批准编号小于Mn的Accept请求。
一个应答：
- 在不违背约定的前提下，回复已通过的提案中编号最大者的值和提案号Mmax。若无则返回空值。

Accept（接受）阶段

若提议者收到了超过半数的接受者对其准备请求的响应，则其发送针对提案[Mn,Vn]的接受请求，注意Vn的值是响应中编号最大的提案值，若响应中无提案则可自选值。
若接受者收到此接受请求且尚未对编号大于Mn的请求做出响应，则可通过该提案。

当提议者获得多数接受者的接受响应后，协商结束，形成共识，结果将发送至所有学习节点进行学习。

因此，Paxos算法的整体流程具体如下：

Paxos详细流程

关于算法的模拟流程，可参考相关资料。

Paxos算法的不足与优化

上述描述称为Basic Paxos算法，在单提议者的情况下并无问题，然而在多个提议者互相争夺的情况下，可能导致提案循环死锁。

为此，Lamport提出了Multi Paxos算法。其核心思想是在多个提议者中选举出一个Leader，由领导者作为唯一提议者，从而避免提议者间的冲突。

Raft算法的解析

Raft算法简介

Raft同样是一个一致性算法，其目标与Paxos相同，因而也被称为“易于理解的一致性算法”。Paxos与Raft均为实现一致性而产生，但选举的具体过程有所不同。

Raft算法的工作流程

Raft算法的角色划分

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

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

在初始状态下，没有Leader，所有参与者均为Follower。

选举过程如下：在选举期间，所有Follower均可参与竞选，成为Candidate。选举结束后，选出的Leader开始任期，非Leader的Candidates恢复为Follower。

引入“任期”概念，用Term表示。

三类角色的变迁图如下：

Raft三种角色变化

Leader选举过程

Raft使用心跳（heartbeat）机制触发Leader选举。Server启动后初始化为Follower。Leader定期向所有Follower发送心跳。如果Follower在选举超时时间内未收到Leader的心跳，则等待一段随机时间后发起Leader选举。

Follower将其当前Term加一，转变为Candidate。Candidate首先投票给自己，并向集群中其他服务器发送RequestVote RPC，结果可能有三种情况：

赢得超过一半的选票，成功当选Leader；
收到Leader的消息，表明其他服务器已选出Leader；
无人赢得多数选票，选举失败，等待选举超时后发起下一次选举。

Leader选举过程

选出Leader后，Leader通过定期向所有Follower发送心跳信息维持领导地位。若Follower一段时间未收到Leader的心跳信息，则认为Leader失效，重新发起选举。

分布式设计

幂等性的概念

什么是幂等性？

幂等性是一个数学概念，应用于接口的上下文中，可以理解为：同一接口多次发出相同请求，其结果始终一致。

简而言之，重复调用的效果与单次调用相同。

幂等性问题的表现

在实际运行中，可能会出现以下问题：

用户在填写表单时，因快速点击保存按钮导致两条重复数据产生，仅ID不同。
开发人员为解决接口超时的问题，通常会引入重试机制。若第一次请求超时，未及时获取结果，可能会造成重复请求。
MQ消费者在读取消息时，有时会遇到重复消息，导致数据重复。

这些都属于常见的幂等性问题。

在分布式系统中，只要下游服务存在写操作（如保存、更新），均可能引发幂等性问题。

注意：幂等与防重不同，前者强调多次调用如同一次，后者则侧重防止数据重复，防重包含了幂等的特性。

如何保证接口幂等性？

接口幂等性保障方法

插入前查询：

在保存数据的接口中，先根据requestId等字段进行查询，若数据已存在则直接返回，若不存在则执行插入操作。

添加唯一索引：

设置唯一索引是简单且有效的办法，若重复插入数据则抛出异常，需捕获该异常以确保幂等性。

使用悲观锁：

更新操作时，可采用悲观锁，锁定对应用户的数据行。此时，只有一个请求能获取锁，其他请求需等待。

select * from user where id=123 for update;

此方法的缺点在于未获得锁的请求只能返回失败，较难保证返回一致。

使用乐观锁：

更新逻辑中，增加timestamp或version字段，例如version:

在更新前查询数据，将version作为条件，更新时同步也更新version：

update user set amount=amount+100, version=version+1 where id=123 and version=1;

更新成功后，version增加，重复请求将无法更新。

建立防重表：

若某些场景允许数据重复，可通过建立防重表存储唯一ID，消费时查询是否已消费，若消费过则直接返回成功。

状态机：

对于有状态的业务表（如订单表），可通过限制状态转移来实现幂等性。

使用分布式锁：

相比在数据库上加锁，分布式锁性能更优。当前流行的实现方式是通过Redis，通常利用Redisson框架。

token机制：

请求接口前，先获取唯一token，带上token完成业务操作，服务端依据token存在性判断请求是否重复。

分布式限流算法的类型

计数器算法

计数器算法简单粗暴，例如限制每秒的请求数。其思路为：从第一个请求开始计时，在接下来的1秒内，每个请求计数+1，超过最大请求数的请求将被拒绝，1秒钟结束后计数清零，重新开始。

这种方式存在一个显著缺陷：如果前10毫秒已经达到了最大请求数，后990毫秒的请求只能被拒绝，造成“突刺现象”。

漏桶算法

漏桶算法设定桶底出水速度固定，进水速度可变，当进水量大于出水量时，水会被装在桶中，不会被丢弃；但桶有容量限制，满桶后溢出的水将被丢弃。

算法实现：准备一个队列保存暂时无法处理的请求，定期从队列中获取请求执行。

漏桶算法概述

令牌桶算法

令牌桶是生成访问令牌的地方，生产速度恒定，用户访问时桶中如有令牌可访问，否则将触发限流。

实现方案：使用Guava RateLimiter进行限流，这是谷歌提供的基于令牌桶算法的限流工具，适用于单实例的系统。

令牌桶算法示意图

本文对分布式系统的面试题进行了详细整理，涵盖了CAP原理、分布式锁、分布式事务等多个方面，虽然内容偏向理论，但分布式领域非常广泛，后续将涉及分布式调用、微服务等相关主题文章，敬请期待。