常用的分布式系统理论_基于etcd 实现令牌桶

CAP定理

CAP指的是Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）

C、A、P这三个需求中，网络分区的发生是不可避免的，因此分区容错性是分布式系统必须满足的需求。因此，CAP定理实际上是在告诉我们，当发生网络分区时，我们需要在一致性和可用性之间做出权衡，只能选择其中的一个。这是因为，在网络分区的情况下，要么保持一致性，但会牺牲可用性，即请求可能会得到错误的响应或者超时；要么保持可用性，但会牺牲一致性，即不同节点上的数据可能是不一致的。因此，CAP定理提醒我们在设计分布式系统时要根据具体的需求和场景做出适当的取舍。

CA模型的常见应用：

• 集群数据库
• xFS文件系统
• CP without A

放弃A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

CP模型的常见应用：

• 分布式数据库
• 分布式锁
• AP wihtout C

要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

AP模型常见应用：

• Web缓存

• DNS
  举个大家更熟悉的例子，像我们熟悉的注册中心ZooKeeper、Eureka、Nacos中：

• ZooKeeper 保证的是 CP

• Eureka 保证的则是 AP

• Nacos 不仅支持 CP 也支持 AP

分布式锁

基于redis单实例分布式锁

Redis的分布式锁是非常的经典的，它的使用遍布在各个业务系统中。
redis单实例中实现分布式锁的正确方式（原子性非常重要）:

1. 设置锁时，使用set命令，因为其包含了setnx,expire的功能，起到了原子操作的效果，给key设置随机值，并且只有在key不存在时才设置成功返回True,并且设置key的过期时间（最好用毫秒）

SET key_name my_random_value NX PX 30000 # NX 表示if not exist 就设置并返回True，否则不设置并返回False PX 表示过期时间用毫秒级， 30000 表示这些毫秒时间后此key过期

2. 在获取锁后，并完成相关业务后，需要删除自己设置的锁（必须是只能删除自己设置的锁，不能删除他人设置的锁）；

删除原因：保证服务器资源的高利用效率，不用等到锁自动过期才删除；

删除方法：最好使用Lua脚本删除（redis保证执行此脚本时不执行其他操作，保证操作的原子性），代码如下；逻辑是 先获取key，如果存在并且值是自己设置的就删除此key;否则就跳过；

if redis.call(“get”,KEYS[1]) == ARGV[1] then return redis.call(“del”,KEYS[1]) else return 0 end

基于etcd的分布式锁

Etcd是一个高可用、分布式、一致性的键值存储系统，因其高效、可靠的特点，被广泛应用于分布式系统中。Etcd中的分布式锁实现，可以实现多个进程之间的互斥访问，避免出现并发访问的问题。基于Etcd的分布式锁实现过程中，主要涉及到以下几个步骤：

• 创建Etcd客户端连接：在分布式系统中，各个进程都需要连接到Etcd服务，获取分布式锁的信息。

• 创建租约：在Etcd中，租约是指某个键值对的生存时间，在租约时间内，Etcd会保证该键值对一直存在。如果租约时间到期，那么Etcd会自动将该键值对删除。

• 创建分布式锁：在Etcd中，分布式锁的实现需要使用到租约。分布式锁的创建过程主要分为两个步骤：

• 创建一个带有租约的临时节点；

• 通过比较Etcd中当前节点的序列号和前一个节点的序列号，来判断当前节点是否获取到了分布式锁。

• 释放锁：在获取到锁之后，进程需要使用相同的Etcd客户端连接释放锁。释放锁的过程主要分为两个步骤：

• 删除当前节点；

• 关闭租约。

基于Etcd的分布式锁实现，能够保证分布式系统中各个进程的互斥访问。但是，它也存在一些问题：

网络通信开销：在分布式系统中，各个进程需要频繁地连接Etcd服务，获取分布式锁的信息。这会增加网络通信的开销，影响系统的性能。

锁竞争：在高并发的情况下，分布式锁的竞争会变得非常激烈，容易造成锁竞争的问题，影响系统的稳定性。

因此，在实际应用中，需要根据实际情况选择合适的分布式锁实现方案，保证系统的可用性和稳定性。

分布式事务

分布式事务是指在分布式系统中的多个事务并发执行时，为了保证数据的一致性和完整性，需要采取一些协调机制，确保这些事务的执行结果和单机事务一样具有原子性、一致性、隔离性和持久性。

以下是常见的分布式事务实现方案：

1. 两阶段提交（Two-Phase Commit，2PC）：是一种同步协议，通过协调器来实现事务的一致性。该协议由两个阶段组成，第一阶段是投票阶段，协调器向所有参与者发起请求，询问它们是否可以提交事务；第二阶段是执行阶段，如果所有参与者都同意提交，协调器会向它们发送提交请求，否则会发送回滚请求。

2. 三阶段提交（Three-Phase Commit，3PC）：是对两阶段提交的改进，通过引入超时机制和优化提交流程来解决2PC中存在的问题。3PC主要包含三个阶段：CanCommit，PreCommit和DoCommit。

3. TCC（Try-Confirm-Cancel）：是一种基于补偿的分布式事务处理方案。将分布式事务拆分成三个操作：Try、Confirm和Cancel。当分布式事务发生时，先进行Try操作，检查分布式事务操作是否可以成功，如果Try操作成功，则执行Confirm操作提交分布式事务操作；如果Try操作失败，则执行Cancel操作回滚分布式事务。

4. 本地消息表（Local Message Table，LMT）：是一种轻量级的分布式事务解决方案，它通过将分布式事务操作转化为本地操作和消息发送，然后通过本地消息表来实现事务的最终一致性。

5. Saga：是一种基于流程的事务处理机制，将分布式事务拆分成一系列互相协作的子事务（Step），并通过Saga协调器来确保每个子事务的执行顺序和一致性。

6. 最大努力通知： 最大努力通知相比实现会简单一些，适用于一些对最终一致性实时性要求没那么高的业务，比如支付通知，短信通知。对通知失败的操作不断的进行重试，直到达到最大通知次数。

7. Seata（Simple Extensible Autonomous Transaction Architecture）是一个开源的分布式事务解决方案，提供了高性能和易用性的分布式事务服务。它能够保证事务的ACID属性，同时提供了简单易用的编程模型，使得开发人员可以方便地开发分布式事务应用。

Seata是非常常见的分布式事物的使用方案，Seata支持两种事务模型：AT（自动事务）和TCC（尝试、确认、取消事务）。AT模型是一种自动的事务模型，适用于大多数的业务场景，它不需要应用开发人员显式地编写事务提交和回滚的代码。TCC模型则需要应用开发人员显示地编写事务提交和回滚的代码，适用于一些特定的场景，如金融领域、电商领域等。

Seata的核心组件包括：

Transaction Coordinator（TC）：事务协调器，负责协调全局事务的提交和回滚。
Transaction Manager（TM）：事务管理器，负责管理分支事务的状态，以及向TC报告全局事务的状态。
Resource Manager（RM）：资源管理器，负责管理本地事务的提交和回滚，以及向TM报告分支事务的状态。
Seata的工作流程如下：

1. 客户端向TC发起全局事务请求。
2. TC创建全局事务，并向TM发起分支事务请求。
3. TM在本地创建分支事务，并向RM注册分支事务。
4. 客户端在分支事务中执行业务逻辑。
5. 客户端向TM发送分支事务的提交请求。
6. TM向TC报告分支事务的状态。
7. TC根据分支事务的状态决定全局事务的提交或回滚。
8. 如果全局事务提交，TC向所有RM发送分支事务的提交请求。
9. RM接收到分支事务的提交请求后，提交本地事务。
10. 如果全局事务回滚，TC向所有RM发送分支事务的回滚请求。
11. RM接收到分支事务的回滚请求后，回滚本地事务。
12. 基于Seata的分布式事务实现方案可以保证事务的ACID属性，同时提供了简单易用的编程模型，使得开发人员可以方便地开发分布式事务应用。

分布式一致性算法

Paxos算法

在Paxos中有这么几个角色：

1. Proposer（提议者） : 提议者提出提案，用于投票表决。
   2 .Accecptor（接受者） : 对提案进行投票，并接受达成共识的提案。
2. Learner（学习者） : 被告知投票的结果，接受达成共识的提案。
   在实际中，一个节点可以同时充当不同角色。
   Paxos算法包含两个阶段，第一阶段Prepare(准备)、第二阶段Accept(接受)。
   Prepare(准备)阶段
   提议者提议一个新的提案 P[Mn,?]，然后向接受者的某个超过半数的子集成员发送编号为Mn的准备请求
   如果一个接受者收到一个编号为Mn的准备请求，并且编号Mn大于它已经响应的所有准备请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给提议者，同时该接受者会承诺不会再批准任何编号小于Mn的提案。
   总结一下，接受者在收到提案后，会给与提议者两个承诺与一个应答：

两个承诺：
承诺不会再接受提案号小于或等于 Mn 的 Prepare 请求
承诺不会再接受提案号小于Mn 的 Accept 请求
一个应答：
不违背以前作出的承诺的前提下，回复已经通过的提案中提案号最大的那个提案所设定的值和提案号Mmax，如果这个值从来没有被任何提案设定过，则返回空值。如果不满足已经做出的承诺，即收到的提案号并不是决策节点收到过的最大的，那允许直接对此 Prepare 请求不予理会。
Accept(接受)阶段
如果提议者收到来自半数以上的接受者对于它发出的编号为Mn的准备请求的响应，那么它就会发送一个针对[Mn,Vn]的接受请求给接受者，注意Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它可以随意选定一个值。
如果接受者收到这个针对[Mn,Vn]提案的接受请求，只要该接受者尚未对编号大于Mn的准备请求做出响应，它就可以通过这个提案。
当提议者收到了多数接受者的接受应答后，协商结束，共识决议形成，将形成的决议发送给所有学习节点进行学习。

Raft算法

Raft算法是一种用于分布式一致性的算法，其目的是让多个节点在分布式环境下达成一致的状态。Raft算法的设计者认为，相比其他分布式一致性算法（如Paxos），Raft算法更容易理解、实现和调试。

Raft算法的核心是Leader选举、日志复制和安全性。在Raft算法中，节点可以处于三种状态：Leader、Follower和Candidate。Leader负责处理客户端的请求，并将结果复制到Follower节点。Follower和Candidate节点等待Leader的指令。如果Leader宕机，Follower和Candidate节点会通过选举产生新的Leader。

Raft算法通过日志复制来保证多个节点之间的一致性。当客户端发出请求时，Leader会将请求转化为一条日志记录，并将其复制到Follower节点。一旦大多数节点复制了该日志记录，Leader将会将该请求应用于状态机，然后将结果返回给客户端。

为了保证安全性，Raft算法还引入了一些额外的约束条件，例如限制Follower节点只能接收来自Leader的指令、确保每个日志记录都有唯一的索引、以及限制只有新的Leader才能进行新的日志复制等。

总的来说，Raft算法通过Leader选举、日志复制和安全性保证了分布式一致性。与Paxos相比，Raft算法更加容易理解、实现和调试，因此在实际应用中得到了广泛的应用。

分布式设计

1. insert前先select

在保存数据的接口中，在insert前，先根据requestId等字段先select一下数据。如果该数据已存在，则直接返回，如果不存在，才执行 insert操作。

2. 加唯一索引

加唯一索引是个非常简单但很有效的办法，如果重复插入数据的话，就会抛出异常，为了保证幂等性，一般需要捕获这个异常。

如果是java程序需要捕获：DuplicateKeyException异常，如果使用了spring框架还需要捕获：MySQLIntegrityConstraintViolationException异常。

3. 加悲观锁

更新逻辑，比如更新用户账户余额，可以加悲观锁，把对应用户的哪一行数据锁住。同一时刻只允许一个请求获得锁，其他请求则等待。

select * from user id=123 for update;
这种方式有一个缺点，获取不到锁的请求一般只能报失败，比较难保证接口返回相同值。

4. 加乐观锁

更新逻辑，也可以用乐观锁，性能更好。可以在表中增加一个timestamp或者version字段，例如version:

在更新前，先查询一下数据，将version也作为更新的条件，同时也更新version：

update user set amount=amount+100,version=version+1 where id=123 and version=1;
更新成功后，version增加，重复更新请求进来就无法更新了。

5. 建防重表

有时候表中并非所有的场景都不允许产生重复的数据，只有某些特定场景才不允许。这时候，就可以使用防重表的方式。

例如消息消费中，创建防重表，存储消息的唯一ID，消费时先去查询是否已经消费，已经消费直接返回成功。

6. 状态机

有些业务表是有状态的，比如订单表中有：1-下单、2-已支付、3-完成、4-撤销等状态，可以通过限制状态的流动来完成幂等。

7. 分布式锁

直接在数据库上加锁的做法性能不够友好，可以使用分布式锁的方式，目前最流行的分布式锁实现是通过Redis，具体实现一般都是使用Redission框架。

8. token机制

请求接口之前，需要先获取一个唯一的token，再带着这个token去完成业务操作，服务端根据这个token是否存在，来判断是否是重复的请求。

分布式限流

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

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

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

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

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