分布式《各种分布式算法学习》笔记

分布式笔记

发布时间 : 2022-09-17 00:00

字数:13.5k

CAP理论
BASE理论：
一致性Hash算法
Raft共识算法
Paxos 共识算法
MySQL分布式锁
ZooKeeper分布式锁
Redis分布式锁
分布式事务
雪花算法分布式ID

CAP理论

CAP：一个分布式系统不可能同时满足一致性（Consistency)，可用性（Availability）和分区容错性（Partition tolerance）这三个基本需求，最多只能同时满足其中的2个。

分区容错性（Partition tolerance）：分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。
一致性（Consistence）：指数据在多个副本之间能够保持一致的特性（严格的一致性）。
可用性（Availability）：指系统提供的服务必须一直处于可用的状态，每次请求都能获取到正确的响应，但是不保证获取的数据为最新数据。

进一步理解：“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系。

由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲C或A。
C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生
这三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。

BASE理论：

，是对AP的扩展：

Basically Available(基本可用)：可用性：出现故障时，允许损失部分可用功能，保证核心功能可用。
Soft state(软状态)：中间状态：允许系统中存在中间状态，这个状态不影响系统可用性，这里指的是CAP中的不一致。
Eventually consistent (最终一致性)：一致性：经过一段时间后，所有节点数据都将会达到一致。

一致性Hash算法

作用，目标是为了解决因特网中的热点(Hot spot)问题：

资源均匀分布：负载均衡中要求资源均匀的分布到所有节点上
单个节点变化影响小：某个节点变更时（挂掉或插入1个新节点），最大限度的减少Hash取余后的变化，不用全部重写Hash，减少数据丢失。

原理：

整个Hash范围是一个环。
节点均匀的分布到环上。
Hash时，计算位点。取位点处顺时针遇到的第一个节点为存储节点。
虚拟节点：为防止数据倾斜，每个节点对应n个虚拟节点。所以计算位点后会做两次映射，一次映射到虚拟节点，再一次映射到具体节点。

好处：

down掉一个节点时，只影响Hash环上该节点逆时针到前一个节点处之间的数据。
新增一个节点时，同样的只影响该结点处逆时针到前一个节点处的数据。

示例：

1.范围映射到环。假设范围为0 ~ 2^32-1：

2.实际节点映射到环。

3.数据hash到具体节点。从hash环上顺时针找第一个节点：

4.新增或删除一个节点时，只影响Hash环上该节点逆时针到前一个节点之间的数据。

5.为防止数据倾斜，每个实际节点再次分散为hash环上的多个虚拟节点。此时数据映射到具体的节点就需要做两次映射：

Raft共识算法

场景举例，分布式系统的两种同步方法：

主从同步，主从断开连接时有同步风险：如MySQL。Redis主从。
Raft同步，可允许小部分机器挂掉，机器挂掉、重启前后，数据依然能保持一致：如newSQL(TiDB)。RedLock。

共识算法：在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。共识算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值（广义的数据，可以是一条日志，也可以是一条命令等）达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

基本概念

目的：在保证CP（强一致性）的前提下，只要求大多数节点可以正常互联，系统便能达到A。即系统便可以一直处于可用状态。这样就在一致性和可用性之间做到良好的平衡。大白话就是，系统某个节点出故障了，我既要保证保证系统对外可用，还要保证整个系统数据的一致性。

场景：保持整个集群间的节点数据同步。如Consul集群

状态机：说白了，一般就是指一张状态转换图。状态机的全称是有限状态自动机。自动的意思是，给定一个状态机，同时给定它的当前状态以及输入，那么输出状态时可以明确的运算出来的。

共识：共识就是多个服务器就某个值而言，最终达成一致的决策过程。一般情况下，共识算法只要满足“多数存活”的原则即可。

共识算法通常依赖于状态机复制。

状态机复制：理论基础是，如果集群里的每一个节点上都运行着相同的确定性状态机S，并且所有的状态机刚开始都处于同样的初始状态s0，那么给予这些状态机相同的输入序列，这些状态机必然会经过相同的状态转换路径，最终达到相同的状态sn，同时生成相同的输出序列。

状态机复制在实际应用中的一个例子：就是MySQL集群。从节点按主节点的binlog跑一次，就达到了和主节点相同的状态。

Raft算法核心组件

核心设计包括两大部分：状态机与日志：

状态机：见上文。
日志：Raft语境下，我们所说的“日志”并不是系统运行的警告，错误等信息等，而是指操作记录。例如，set x to 3等。

客户机看来，即使集群中的少数服务器出现故障，它们也会与单个可靠的状态机进行交互。每个状态机处理相同的命令序列，从而产生相同的结果序列并到达相同的状态序列。

Raft算法概念

算法实现过程主要包括选举和日志同步两部分：

第一阶段：选举。从集群中选出一个合适的节点作为Leader。
第二阶段：日志同步。选举出的Leader接收客户端请求，将其转为Raft日志。Leader将日志同步到其他节点，当大多数节点写入成功后，日志变为Committed，一经Committed日志便不会再被篡改。Leader故障时，切换到第一阶段，重新选举。

节点角色：

Leader: 为主节点，同一时刻只有一个Leader节点，负责整个集群的节点间的协调和管理。
Candidate: 候选节点，只有角色为候选者的节点才可以被选为新的Leader，每个节点都有可以成为候选者。
Follower: Leader的跟随者，这个角色的时候不可以发起选主。

任期（Term）：

将时间切分为一个个的Term（同时每个节点自身也会本地维护currentTerm），可以认为是逻辑上的时间。避免分布式系统中，“时间同步”的难题，因为大家会时钟不一致。

心跳（heartbeats）和超时机制（timeout）：在Raft算法中，有两个timeout机制来控制领导人选举：

选举定时器（eletion timeout）：即Follower等待成为Candidate状态的等待时间，这个时间被随机设定为150ms~300ms之间。
心跳定时器（heartbeat timeout）：在某个节点成为Leader以后，它会发送Append Entries消息给其他节点，这些消息就是通过heartbeat timeout来传送，Follower接收到Leader的心跳包的同时也重置选举定时器。

Raft算法工作机制

Raft算法可分为3部分：

领导人选举
日志复制
安全性

领导人选举（Leader Election）

1.一开始，所有节点都是以Follower角色启动，同时启动选举定时器（时间随机，降低冲突概率）

2.如果一个节点发现在超过选举定时器的时间以后一直没有收到Leader发送的心跳请求，则该节点就会成为候选人，并且一直处于该状态，直到下列三种情况之一发生：

该节点（Candidate）赢得选举
其他节点赢得选举
一段时间后没有任何一台服务器赢得选举（进入下一轮Term的选举，并随机设置选举定时器时间）

3.然后这个候选人就会向其他节点发送投票请求（Request Vote），如果得到半数以上节点的同意，就成为Leader（Leader）。如果选举超时，还没有Leader选出，则进入下一任期，重新选举。

4.完成Leader选举后，Leader就会定时给其他节点发送心跳包（Heartbeat），告诉其他节点Leader还在运行，同时重置这些节点的选举定时器。

日志复制（Log Replication）

1.客户端提交命令，Leader 节点置为 uncommitted：Client向Leader提交指令（如：SET 5），Leader收到命令后，将命令追加到本地日志中。此时，这个命令处于“uncomitted”状态，复制状态机不会执行该命令。

2.Leader通知复制命令，其他所有节点置为 uncommitted，完成后 Leader置为committed，并返回：Leader将命令（SET 5）并发复制给其他节点，并等待其他其他节点将命令写入到日志中，如果此时有些节点失败或者比较慢，Leader节点会一直重试，直到所有节点都保存了命令到日志中。之后Leader节点就提交命令（即被状态机执行命令，这里是：SET 5），并将结果返回给Client节点。

3.Leader用通知提交命令，其他所有节点置为committed：Leader节点在提交命令后，下一次的心跳包中就带有通知其他节点提交命令的消息，其他节点收到Leader的消息后，就将命令应用到状态机中（State Machine），最终每个节点的日志都保持了一致性。

Leader节点会记录已经提交的最大日志index，之后后续的heartbeat和日志复制请求（Append Entries）都会带上这个值，这样其他节点就知道哪些命令已经提交了，就可以让状态机（State Machine）执行日志中的命令，使得所有节点的状态机数据都保持一致。

Raft算法如何处理日志内容不一致的情况？

如下图，如果在一个分布式网络中，各个节点的日志状态如下。当Leader节点发送日志复制请求的时，会带上上一次的日志记录的 index和 term。

此时Leader节点发送日志复制请求*<nextIndex：8，命令：x←4，,已提交的日志index为7，term为3>*。

此时，A节点收到Leader的请求后，对比Leader节点记录的上一个日志记录的index和term，发现自己的日志中不存在这个命令，于是拒绝这个请求：

index（leader）> index（A）
term（leader）> currentTerm（A）

此时，Leader节点知道发生了不一致，于是递减nextIndex，并重新给A节点发送日志复制请求，直到找到日志一致的地方为止。然后把Follower节点的日志覆盖为Leader节点的日志内容。

也就是说，Raft算法对于日志内容不一致的请求，会采取Leader节点的日志内容覆盖Follower节点的日志内容的做法，先找到两者日志记录第一次不一致的地方，然后一直覆盖到最新提交的命令位置。

安全性

Leader宕机时可能导致不一致：上述日志复制的机制，并不能保证每一个状态机能按照相同的顺序执行同样的指令。例如，当领导人提交了若干日志条目的同时，一个追随者可能宕机了，之后该追随者又被选为了领导人然后用新的日志条目覆盖掉了旧的那些，最后，不同的状态机可能执行不同的命令序列。

解决方法：Raft算法通过在领导人选举阶段增加一个限制来完善了Raft算法。RequestVote RPC：一个Candidate节点参加竞选时，如果它自己的日志比候选人的日志要新，那么它会拒绝候选人的投票请求。

如何判断两个节点日志内容新旧：通过比较日志中最后一个命令的索引（index）和任期号（term）来判定：

如果两个日志的任期号不同，任期号大的日志内容更新
如果任期号相同，日志长的日志内容更新

注意到，最开始的Leader是所有节点的日志都 uncommitted之后，才会给客户端答复。所以它挂掉之后，剩余的节点里是有最新日志的。

实例分析

下面我们来考虑一个比较极端的情况，出现网络分区的时候，Raft如何保持一致性。

省流总结：

出现分区后，虽然有两个Leader节点。但是小分区的Leader会由于支持节点不足，无法写入。
分区结束后，大分区的Leader由于选票多，会成为新的Leader。之后它就把数据覆盖之前的小分区。

如下图，我们将分布式网络分割为两个子网，分别是子网络AB和子网络CDE，此时节点B是Leader节点。

然而由于网络分区导致子网1不存在Leader节点，此时，C、D和E节点由于没有收到Leader节点的心跳，导致选举定时器超时从而进入Candidate状态，开始进行领导人选举。

这时，我们假设C节点赢得选举，成为子网1的Leader节点。

此时，如果两个子网有Client节点分别向各个子网的Leader节点提交数据（如：X←3），由于子网2中Leader节点B不可能复制到大部分节点，所以其X←3命令会一直处于“uncomitted”状态。而子网1由于成功复制给大部分节点，所以X←3最终在子网1达成共识，如下图所示。

我们假设，子网1经过多次选举和数据交互，最终子网1的日志状态如下图所示：

而此时，分区隔离状态消失。Leader C和 Leader B分别会发送心跳请求，最终Leader B发现Leader C选票比自己更多，从而转换为Follower状态。而通过日志复制（Log Replication），最终所有节点日志达成一直，如下图。

其他共识算法

简单提一下：Bully、ZAB算法。

其他详细略。本节Raft共识算法参考资料：

Paxos 共识算法

暂略。参考 https://www.cnblogs.com/linbingdong/p/6253479.html

有个错误要更正：在第二阶段acceptor判断是否接受提案的条件应该是 N >= ResN。

MySQL分布式锁

用MySQL也可以实现一个分布式锁。其实用其他方式实现时，要考虑的点也差不多是一样的。

存锁：可直接建立一张表来存锁：

id
resource_name：资源名
node_info：机器信息。机器或线程id。
count：加锁次数。用于可重入锁。
desc：其他备注描述
create_time：创建时间
update_time：更新时间

加锁：可实现以下方法：

*lock()*：阻塞不断尝试，直到获取到锁。
*tryLock()*：非阻塞获取。获取不到立即返回。
*tryLock(long timeout)*：非阻塞获取。不断尝试，直到超时或获取成功。

解锁：

unlock()：count为1则直接删除记录以解锁，否则count减一。

锁超时：防止机器挂掉或连接中断时导致锁无法释放：

锁自动释放：启动一个定时任务，如果锁超过XX时间没有被释放，我们就认为是节点挂了然后将其直接释放。（有隐患）

锁延期：

看门狗延期锁：加锁端启动一个看门狗，一直给锁延期。（机器挂掉时还是有隐患）

乐观锁：

正常操作时，需要加行锁，开销较大：select * for update
类似CAS，直接给锁加一个版本号，加解锁时带上版本号：update/delete lock_table t …..where t.version = oldVersion。

总结：MySQL要考虑的问题如下：

存锁、加锁（可重入）、解锁、锁超时、锁延期。

其他分布式锁要考虑的问题是类似的。

ZooKeeper分布式锁

关键思路：插入临时有序节点，自己是第一个则获得锁，否则用watcher监控前一节点。

ZK特点：

ZK基于Paxos 算法，不是主从，没有宕机时数据不一致问题。
底层的数据节点结构和文件目录类似。可以利用这一点来实现分布式锁。

加锁思路

以某个资源为目录，该目录下的节点就是我们需要获取锁的客户端，未获取到锁的客户端注册时需要注册 Watcher 到上一个客户端。

如下图所示：

/lock 是用于加锁的目录，/resource_name 是锁定的资源，其下面的节点按照我们加锁的顺序排列：

Curator框架

类似Redission框架。封装了操作ZK的API，也封装了分布式锁的方法。

Curator分布式锁实现内容：

实现了可重入锁：InterProcessMutex。
- 可重入锁中还实现了读写锁。
实现了不可重入锁：InterProcessSemaphoreMutex

InterProcessMutex可重入锁

使用示例：acuire 加锁，release 解锁：

实现流程如下：

加锁流程：

可重入锁判定：判断是不是可重入锁。是否可重入、已重入次数是记录在客户端本地。

可重入锁记录在 ConcurrentMap <Thread, LockData> threadData 这个 Map 里。如果 threadData.get(currentThread)有值，则证明就是可重入锁，然后记录会加 1。

之前的 MySQL 也可以通过这种方法去优化，可以不需要 count 字段的值，将这个维护在本地可以提高性能。
创建临时有序节点：在资源目录下创建一个节点：比如这里创建一个 /0000000002 节点，该节点需要设置为EPHEMERAL_SEQUENTIAL ，即临时节点并且有序。
判断是否是目录下第一个节点：获取当前目录下所有子节点，判断自己的节点是否位于子节点第一个。
获取锁成功，直接返回：如果是第一个节点，则获取锁成功，直接返回。
获取锁失败，注册监控器到前一个节点：如果不是第一个节点，则获取锁失败。获取自己节点的前一个节点，并在前一个节点上注册 Watcher(这里的 Watcher 其实调用的是 object.notifyAll()，用来解除阻塞)。
阻塞等待：object.wait(timeout) 或 object.wait()，进行阻塞等待。直到watcher调用object.notifyAll()。ZK的节点监听机制，可以反向通知客户端重新获取锁。

为什么不全部监听第一个节点，而是监听前一个节点：因为如果都监听第一个节点，该节点一旦释放锁，则会全部通知监听该节点的客户端，引起不必要大量的网络开销，也就是羊群效应。

解锁流程：

可重入锁判定：是可重入锁则次数减 1 即可。减 1 之后，若加锁次数不为 0 直接返回。为 0 则继续下面步骤进行解锁。
删除当前节点。
删除 threadDataMap 里面的可重入锁的数据。

读写锁

Curator 提供了读写锁，实现类是 InterProcessReadWriteLock。此时每个节点都会加上前缀：

private static final String READ_LOCK_NAME  = "__READ__";
private static final String WRITE_LOCK_NAME = "__WRIT__";

加锁规则：

加读锁：若发现前面有写锁，则将 Watcher 注册到和自己最近的写锁。
加写锁：逻辑和前文一样，保持不变。

锁超时

ZK无需配置锁超时。临时节点通过检测Session状态来管理生命周期，我们的每个客户端机器都维护着一个 ZK 的 Session，通过这个 Session，ZK 可以判断机器是否宕机。宕机时，对应的临时节点就会被删除。

ZK小结：

优点：无需关心锁超时时间。支持读写锁。ZK 的锁是公平锁，因为获取锁会按照加锁的顺序。对于高可用利用 ZK 集群进行保证。
缺点：ZK 需要额外维护，增加维护成本。性能比较差，和 MySQL 相差不大。且需要开发人员了解 ZK 原理。

ZK VS Redis：

超时机制：ZK基于session维护，底层时hearbeat。Redis则需要设置超时时间。
性能消耗：ZK获取不到锁，只需要添加一个监听器就可以了。ZK的监听机制可以反向通知客户端重写获取锁，不用一直轮询，性能消耗较小。redis则需要不断轮询加锁。
公平锁：ZK是有序节点，公平锁。Redis是抢占式。
读写锁：ZK支持读写锁。

Redis分布式锁

分布式锁的设计目标

就是实现3点，基本上和其他锁一致：

互斥：不用解释，锁的基本要求。只能被一个客户端的一个线程独占。
不死锁：即使拿锁的客户端挂掉了，锁也可以释放。
容错性：只要Redis集群中大部分节点正常运行，就可以执行加减锁。

简单实现

加锁：

setNx resourceName value

锁超时：考虑锁超时问题，可再加入过期时间。Redis 2.8后，支持 加锁nx 和超时ex 合并为同一个原子操作。

set resourceName value ex 5 nx

Redisson实现

实现思路：

继承了 java.util.concurrent.locks.Lock，用起来比较直观。
底层是调用eval来使用 Lua 脚本实现，而不是使用前文的 ex + nx。原因时为了兼容老版本Redis。
Redission 通过 Netty 支持非阻塞 I/O，比起Jedis 简单使用阻塞的 I/O 和 Redis 交互，性能高一些。

使用示例：

Lua脚本源码：

加锁逻辑：

尝试加锁：锁定资源的节点信息是 Key，锁定次数是 Value。可重入锁。
加锁失败，且判断已经超时，则返回 false。
加锁失败，且判断没有超时，则订阅解锁消息，然后一直阻塞，直到超时或有解锁消息。订阅的channel是redisson_lock__channel + lockName。
重复1，2，3，直到获取锁，或获取锁超时。

加锁成功后添加看门狗：为避免业务还没执行完锁就过期了，Redisson会用一个守护线程看门狗去给锁延时。每10s看下锁有没有被释放，没有就延长锁的过期时间（使用set key uniq_id ex timeout，没有使用NX）。

Redisson也提供公平锁实现，简单原理是：

用 list 结构和 hashset 结构分别保存排队的节点，以及节点的过期时间。用这两个数据结构来实现公平锁。

解锁逻辑：分两步执行：

获取锁的id并判断是否是当前客户端设置的id
删除锁

两步要具有原子性。使用lua脚本即可，Get、判断、Del操作在一个lua脚本中执行：

$script = '
if redis.call("get",KEYS[1]) == ARGV[1]
    then
    return redis.call("del",KEYS[1])
else
    return 0
end
';
$token = uniqid(mt_rand(), true);
if ($redis->set('my:lock', $token, ['NX', 'EX' => 10])) {
        # todo

        $redis->eval($script, ["my:lock", $token], 1);
    } else {
        echo 'get lock failed!';
    }

RedLock解决主从宕机问题

上述解决了单节点的加解锁问题，但未考虑集群时锁信息同步的问题。下面来看下：

业务场景：

机器 A 申请到锁A，Redis主机宕机，锁记录未同步到从机，从机升为主机，机器 B 再次从当前主机上申请锁A，机器 B 也获得了锁A。

本质上是主从同步宕机时的数据同步问题。

解决思路：

用 Raft 集群算法解决宕机时数据同步问题，以取代主从同步算法。
此时需要使用Raft算法同时给多个锁节点加锁，协调各节点数据状态。

Reddison用RedLock实现了Raft算法。

使用示例：使用时需要搭建多个 Redis 集群，然后进行红锁的加锁，解锁：

算法步骤：

构建多个集群：生成多个 Redis 集群的 Rlock，并将其构造成 RedLock。
依次循环加锁：依次循环对三个集群进行加锁，加锁的过程和前文的实现一致。
判断失败次数：依次循环加锁时失败，则需要判断失败次数是否超过允许失败节点数：如果循环加锁的过程中加锁失败，那么则需要判断加锁失败的次数是否超出允许失败最大值。该最大值是根据集群的个数，比如三个那么只允许失败一个，五个的话只允许失败两个，要保证多数成功。
判断是否超时：依次循环加锁时，需要判断加锁是否已超时：如设置加锁只能用 3ms，若第一个集群加锁已经消耗了 3ms ，那么就算加锁失败。
失败则全部解锁：若3，4 步加锁失败，则进行解锁操作，解锁会对所有的集群再请求一次解锁。

详细算法步骤参考：

获取当前时间（毫秒数）
单个节点解锁：单个节点加锁时间是否超时 + 唯一ID：按顺序依次向N个Redis节点执行加锁操作。这个加锁操作跟前面单节点Redis的加锁操作一样，包含整体超时时间和唯一的字符串id。

这里为了保证在某个Redis节点不可用的时候算法能够正常运行，这个单个节点的加锁操作还有一个超时时间，它要远小于锁的超时时间（几十毫秒）。客户端在向某个Redis节点获取锁失败后，就立即开始尝试下一个Redis节点。这里的失败包括Redis节点不可用，也包括该Redis节点上的锁已经被其他客户端持有等等情况。
整个集群加锁：所有节点加锁时间是否超时 + 成功获取锁节点数：计算整个加锁过程总共消耗的时间，计算方法是用当前时间减去第1步记录的时间。如果客户端从大多数Redis节点（*>= N/2+1*）成功获取到锁，并且获取锁总共消耗的时间没有超过锁的超时时间，那么这时才认为客户端最终加锁成功；否则，认为最终加锁失败。
最终加锁成功：计算剩余锁超时时间：如果最终加锁成功，那么这个锁的超时时间应该重新计算，它等于最初的锁的超时时间减去上一步计算出来的加锁消耗的时间。即锁总的超时时间 - 加锁过程消耗总时间
最终加锁失败：发起解锁：如果最终加锁失败（可能由于获取到锁的Redis节点个数小于N/2+1，也可能是整个获取锁的过程消耗的时间超过了锁最初的超时时间），那么客户端应该立即想所有Redis节点发起解锁操作（见下面）。

即加锁的时候考虑：1.当前节点加锁操作是否超时。2.已消耗的所有加锁时间是否已超过锁总的超时时间。3.已加锁成功的节点个数是否已满足要求。4.加锁成功则剩余的锁可用时间 = 总的锁超时时间 - 加锁过程消耗的总时间。

Redisson RedLock已标注为弃用，使用RLock即可，RLock使用了wait命令，但wait只能提高数据安全性不保证一致性。

Redis小结：

优点：
- 性能好，比 ZK 和 MySQL 都好。
- 实现简单，自己用 set resourceName value ex 5 nx 就可以做。复杂业务则可用 Redisson，高可用则还可用 RedLock。
缺点：
- 需要维护 Redis 集群。
- 如果要实现 RedLock 需要维护更多的集群。
- 超时机制有点不太优雅。

RedLock仍然不够安全？

Martin Kleppmann 认为RedLock仍然不够安全。其实前面的算法也都有这些问题。

问题如下：

STW问题

长时间GC时，会有长时间的STW。相当于服务器未响应了。

业务场景：服务器未响应一段时间，又恢复响应。此时会有问题。

client1 获取了锁A并且设置了锁的超时时间。
client1 STW未响应，锁A到期后自动释放。
client2 获取到锁A。
client1 STW结束，此时以为自己还在占有锁。此时client1 和 client2 发生了冲突。

ZK、MySQL也会有这样的问题，因为是用户端服务器未响应导致的。

需要解决的问题：

超时时间的设置：
- 方法一：将过期时间设置的足够长，确保代码逻辑在锁释放之前能够执行完成。具体时长看业务。
- 方法二：为获取锁的线程增加一个守护线程，为将要过期但是未释放的锁增加有效时间。
如何保证加锁和解锁是同一个客户端
- setnx命令：加锁时给锁配一个唯一的id，解锁时只有用这个id才能解锁。

Martin 给出了一个解决方法：版本序列号：后面谷歌的Chubby也是参照这种做法。

Martin 给出了解决方法：加版本号：对于 ZK 这种他会生成一个自增的序列，那么我们真正进行对资源操作的时候，需要判断当前序列是否是最新，有点类似于乐观锁。
Redis 作者进行了反驳：你既然都能生成一个自增的序列了那么你完全不需要加锁了，也就是可以按照类似于 MySQL 乐观锁的解法去做。

个人认为，其实这个问题可以用最新的垃圾回收器解决，他们提供符合预期的垃圾回收时间。

时钟跳跃问题

Redis 锁服务器时间发生跳跃，影响了锁的过期时间。此时：

MySQL有问题，因为基于过期时间。
Redis 有问题，因为基于过期时间。
ZK没问题，因为没有设置过期时间。ZK 不需要依赖时间，依赖每个节点的 Session。

Redis 作者也给出了解决方法

人为调整时间导致跳转：人为调整影响的完全可以人为不调整，这个是处于可控的。
NTP 自动调整导致跳转：可以通过一定的优化，把跳跃时间控制在可控范围内，虽然会跳跃，但是是完全可以接受的。

长时间的网络 I/O

和STW类似，导致获取了锁之后，网络调用超时了 ，且其网络调用时间可能比锁的过期时间都还长，从而出现安全性问题。

MySQL有问题。
Redis有问题。
ZK没问题，因为没有设置过期时间

Martin么有重点讨论。个人解决思路：

调整网络调用超时时间：控制网络调用的超时时间，把所有网络调用的超时时间相加。
调整锁过期时间：锁过期时间其实应该大于这个时间。
优化网络：当然也可以通过优化网络调用比如串行改成并行，异步化

ZooKeeper是怎么检测出某个客户端已经崩溃了呢？实际上，每个客户端都与ZooKeeper的某台服务器维护着一个Session，这个Session依赖定期的心跳(heartbeat)来维持。如果ZooKeeper长时间收不到客户端的心跳（这个时间称为Sesion的过期时间），那么它就认为Session过期了，通过这个Session所创建的所有的ephemeral类型的znode节点都会被自动删除。

Chubby 的一些优化

大家搜索 ZK 的时候，ZK 是 Chubby 的开源实现，Chubby 内部工作原理和 ZK 类似。但是 Chubby 的定位是分布式锁和 ZK 有点不同。

Chubby 也是使用上面自增序列的方案用来解决分布式不安全的问题，但是它提供了多种校验方法：

CheckSequencer()：调用 Chubby 的 API 检查此时这个序列号是否有效。
访问资源服务器检查，判断当前资源服务器最新的序列号和我们的序列号的大小。
lock-delay：为了防止我们校验的逻辑入侵我们的资源服务器，其提供了一种方法当客户端失联的时候，并不会立即释放锁，而是在一定的时间内(默认 1min)阻止其他客户端拿去这个锁。那么也就是给予了一定的 buffer 等待 STW 恢复，而我们的 GC 的 STW 时间如果比 1min 还长那么你应该检查你的程序，而不是怀疑你的分布式锁了。

分布式锁安全性的详细讨论（暂略）

详细的分布式锁安全性的讨论，可参照以下两篇文章：

Redisson源码实现（暂略）

Redission源码实现，可参考：

Redisson分布式锁实现：原文作者

Redis分布式锁小节参考文章：

分布式事务

事务理论

事务的类型，共5种：

扁平事务：普通事务，带begin、end。
带保存点的扁平事务：增加了SavePoint机制，内存保存，如果数据库宕机，savepoint将会丢失。
链式事务：提交事务后，相当于执行了 COMMIT AND CHAIN，也就是开启一个链式事务，即当我们提交事务之后会开启一个相同隔离级别的事务。如果回滚只会回滚当前事务节点。
嵌套事务：
- 嵌套事务可以是一棵树，其中的叶节点可以使扁平事务，也可以是嵌套事务，但是都叫做子事务。
- 某个节点回滚只影响当前节点下面所有的事务。
- 父节点提交后子节点的提交才会最后提交，也就说，所有事务的保存只能再最顶层提交，才会生效。
- mysql不支持嵌套事务,Oracle支持
分布式事务：一个在分布式环境下运行的扁平事务。

以上，前4种是单机事务，由DB底层保证实现。单机事务的ACID，具体到MySQL，主要通过以下方式实现：

A，原子性：undolog。
D，持久性：redolog。
I，隔离性：数据库锁。
C，一致性：以上三个共同实现。

分布式事务理论

CAP：

C：一致性。能读到最新数据。
A：可用性。访问有数据，不是超时等。
P：分区容错。出现网络分区时，可正常使用。即一刀分成大小几个区，或者某台机器断网。

BASE：对AP的扩展：

Basically Available(基本可用)
Soft state(软状态)
Eventually consistent (最终一致性)三个短语的缩写。

解决方案：2PC

两阶段提交，属于刚性事务。典型的就是XA。MySQL是从5.5开始支持XA。

XA协议中分为两阶段提交过程：

第一阶段：事务管理器要求每个涉及到事务的数据库预提交（precommit）此操作，并反映是否可以提交.
第二阶段：事务协调器要求每个数据库提交数据，或者回滚数据。

缺点：

数据锁定：数据在整个事务处理过程结束前，都被锁定，读写都按隔离级别的定义约束起来。
协议阻塞：XA prepare 后，分支事务进入阻塞阶段，收到 XA commit 或 XA rollback 前必须阻塞等待。
性能差：性能损耗主要来自两个方面：
- 事务协调过程，增加单个事务的 RT。
- 并发事务数据的锁冲突，降低吞吐。

唯一的优点就是实现简单。

原理图示：

AP：应用程序：业务服务。
RM：资源管理器：数据库
TM：事务管理器：可以是单独的服务。也可以是业务服务。

时序图：

MySQL使用示例：

XA BEGIN '123';
insert into xxx;
XA END '123'; // 链接断开会失去这次事务
XA PREPARE '123'; // 二阶段准备会持久化
XA COMMIT '123'; //prepare全部成功/或者有一个失败就回滚

解决方案：消息最终一致：本地消息表

核心思路是：把分布式事务拆分为本地事务来处理。

最初是ebay提出的。ebay的完整方案https://queue.acm.org/detail.cfm?id=1394128。

解决思路：

用一张本地消息表保存消息状态，和本地业务放到同一事务执行。
发消息前先存表。
收到消息反馈后删除本地消息。
定时任务：需要定时任务扫描。
幂等性：需要保证消息执行的幂等性。

解决步骤：

微服务：
1. 开启事务。
2. 执行业务。
3. 插入消息到本地消息表。
4. 结束事务。
5. 发送消息至MQ，从而发送到其他微服务。
6. 接收其他微服务执行成功反馈。
7. 删除本地消息表对应消息。
定时任务：该过程需要保证消息幂等性。
1. 扫描本地消息表未完成状态消息。
2. 发送消息至MQ。
3. 接收执行成功反馈后，删除本地消息表对应消息。

示意图：

解决方案：消息最终一致：可靠MQ

由RocketMQ实现。本质上是对本地消息表方式的内部封装。先发一个prepare，再发一个commit最终确认发送消息。

实现步骤：

第一阶段：先发送一个prepare消息，会获取到一个prepare的消息id。拿到消息地址。
第二阶段：执行本地事务。执行成功，则发送commit。执行失败，则rollback。
第三阶段：rocketmq-server根据第二阶段消息结果，如果成功就投递给consumer，不成功则把消息删除掉。
第四阶段：未上报是否发送。如果第二阶段没有上报消息结果，那就需要进行回查。RocketMq Broker中提供了定时扫描没有更新状态的消息，如果有消息没有得到确认，会向消息发送者发送消息询问，来判断是否提交。在rocketmq中是以listener的形式给发送者，用来处理。
消费超时：RocketMQ会不断重试，此时需要保证消息幂等。
消费失败：概率较低，没有专门设计处理流程。人工处理。

示意图：

解决方案：最大努力通知

适合于开放平台，外部的第三方系统的场景。此时想要保证最终一致。

关键是要保证两点：

有限次数的重试，一般重试策略采用指数退避。
需要提供查询接口，来防止通知失败。

解决方案：TCC

最早是由Pat Helland于2007年发表的一篇名为《Life beyond Distributed Transactions:an Apostate’s Opinion》的论文提出。

适用场景：适用于有强隔离性、严格一致性要求，执行时间较短的场景。做支付的同学比较常用的。

例如：如果用户一次订单想同时扣减积分服务，券服务，余额服务。此时用消息最终一致、最大努力通知都不行，没法防止用户重复使用资产。用XA则性能太差。

执行步骤：

try：锁定，通常用一个字段或者记录。尝试执行，完成所有业务检查（一致性），预留必须业务资源（准隔离性）。(演化成saga直接try commit合并)
confirm：提交资源。确认执行真正执行业务，不作任何业务检查，只使用Try阶段预留的业务资源，Confirm操作满足幂等性。要求具备幂等设计，Confirm失败后需要进行重试。
cancel：释放资源。取消执行，释放Try阶段预留的业务资源。Cancel操作满足幂等性。Cancel阶段的异常和Confirm阶段异常处理方案基本上一致。

举例：

100元买一瓶水：

try阶段：检查钱包是否够100元并锁住这100元，检查有没有一瓶水并锁住这瓶水。
confirm阶段：如果都成功，则进行confirm，确认这100元扣减，这一瓶水卖出。confirm操作则不断重试，并保持幂等。
cancel阶段：如果有一个资源检查失败，则进行cancel，释放这100元和这一瓶水。cancel操作则不断重试，并保持幂等。

实现参考：ByteTCC:https://github.com/liuyangming/ByteTCC/

示意图：

解决方案：SEGA

Saga是30年前一篇数据库论文提到的一个概念。

核心思想：

是将长事务拆分为多个本地短事务。
由Saga事务协调器协调。
如果正常结束那就正常完成。
如果某个步骤失败，则根据相反顺序依次调用补偿操作。

示意图：

在saga模式中不能保证隔离性，因为没有锁住资源，其他事务依然可以覆盖或者影响当前事务。

举例，100元买一瓶水：

执行：T1=扣100元 T2=给用户加一瓶水 T3=减库存一瓶水。
回滚：C1=加100元 C2=给用户减一瓶水 C3=给库存加一瓶水。

此时如果用户把水喝了，或者没有100元了，就出问题了。

华为的解决方案：从业务层面入手，加入一个 Session 以及锁的机制来保证能够串行化操作资源。也可以在业务层面通过预先冻结资金的方式隔离这部分资源，最后在业务操作的过程中可以通过及时读取当前状态的方式获取到最新的更新。具体实例：可以参考华为的servicecomb。

适用场景：

无法提供TCC接口(遗留系统，外部系统)，一般来说提供提交和回滚接口即可，这里的可以看做业务上的接口，生成订单对应的删除订单就是回滚，不需要单独命名回滚接口。
不看隔离性，一阶段就生效。（？）
想异步执行。（？）
想支持正向重试（tcc 的 try 为什么不能正向重试？因为资源一直被业务隔离，需要释放隔离性)

各解决方案对比

2PC：优点是刚性事务，具有强一致性。但是性能太差，很少用。
消息最终一致：可使用的场景较多。但没法解决强一致性要求和隔离性需求（大家都来扣款，钱不够了怎么办？）。
最大努力通知：和消息最终一致相似。
TCC：可以提前锁定资源，所以可以保证强一致性。不过实现起来比较复杂。需要专门提供接口。
SEGA：

解决中间件：seata

seata 提供了 AT、TCC、SAGA 和 XA 事务模式。seata官网：https://seata.io/zh-cn 。

Seata实现了以下分布式模式：

AT：自动模式，通过我们记录运行sql的undolog，来完成事务失败时的自动重做。
TCC：TCC模式，这种模式弥补我们AT模式只能支持ACID数据库的场景。
XA
SAGA

Seata这类TCC框架的局限性：

改造困难：目前Seata支持的通信框架不多只有Dubbo和Spring-Cloud-Alibaba，如果使用的是其他框架，或者直接是简单的HTTP，甚至有些公司可能目前系统中都没有支持Trace。
维护成本高：Seata需要维护一个单独的集群，一般在公司都需要分配一定的资源（人员资源，机器资源）去管理维护Seata，很多时候不可能为了几个分布式事务去花费这么大的成本，当然这一块的话未来可以上云解决。

实战示例（本地消息表方式）

分布式事务框架关键的三点：

重做记录
重试机制
幂等

重做记录

重做记录保存到表里。回滚时用响应的记录回滚即可。

关键点：

重做记录
全局事务ID：可以用业务相关的，如 order_id。

本地消息表示例：

全局事务ID
操作用户
操作资源Id
资源数量
是否成功

CREATE TABLE `transaction_record` (
  `orderId` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `op_total` int(11) NOT NULL COMMENT '本次操作资源操作数量',
  `status` int(11) NOT NULL COMMENT '1:代表支付成功 2:代表支付取消',
  `resource_id` int(11) NOT NULL COMMENT '本次操作资源的Id',
  `user_id` int(11) NOT NULL COMMENT '本次操作资源的用户Id',
  PRIMARY KEY (`orderId`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

提交/回滚代码示例：

int orderId = createInitOrder();
checkResourceEnough();
try {
    accountService.payAccount(orderId, userId, opTotal);
    coinService.payCoin(orderId, userId, opTotal);
    couponService.payCoupon(orderId, userId, couponId);
    updateOrderStatus(orderId, PAID);
}catch (Exception e){
    //这里进行回滚
    accountService.rollback(orderId, userId);
    coinService.rollback(orderId, userId);
    couponService.rollback(orderId, userId);
    updateOrderStatus(orderId, FAILED);
}
// ------------ 手动提交/回滚代码示例
@Transactional
void payAccount(int orderId, int userId, int opTotal){
    account.payAccount(userId, opTotal); // 实际的去我们account表扣减
    transactionRecordStorage.save(orderId, userId, opTotal, account.getId()); //保存事务记录表
}
@Transactional
void rollback(int orderId, int userId){
    TransactionRecord tr = transactionRecordStorage.get(orderId); //从记录表中查询
    account.rollbackBytr(tr); // 根据记录回滚
}

上述可满足，在机器不出问题的情况下，能手动回滚。

重试机制

例如，上述4步，执行到第2步服务器宕机了，怎么办？这个时候没法手动回滚了。

使用重试机制。有两种思路：

定时任务重试：需要单机任务 + 分布式锁。或者xxl-job等分布式框架。定制轮询状态不对的记录，并重试。如，处于未支付状态，但创建时间已经超过15分钟的订单，此时对其进行回滚，回滚完成之后将订单状态置为FAILED。
消息队列重试：通过发消息到MQ进行下单操作。消费失败的消息丢到私信队列，不断重试。业务上需要处理，比如创建订单时，如果订单已存在，且已超时，那么需要回滚它。

幂等

由于消息可能会被多次消费，所以业务上要考虑幂等性。有两个坑：

多次回滚。
空回滚。

第一个坑，多线程同时回滚：回滚操作未响应，多一次回滚。

幂等处理需要考虑多线程同时执行操作的情况。此时查询和更新要加锁。

举例：两个线程同时判断事务未取消，同时进行了回滚操作。

 @Transactional
    void rollback(int orderId, int userId){
        TransactionRecord tr = transactionRecordStorage.get(orderId);
        if(tr.isCanceled()){
            return; //如果已经被取消了那么直接返回
        }
        //从记录表中查询
        account.rollbackBytr(tr); // 根据记录回滚
    }

第二个坑，事务记录不存在时，若直接返回空，会产生事务悬挂。

当查询TransactionRecord不存在时（因为即使try未成功，我们也会重试），还需要保证没有空指针。可以有两个策略

空回滚：如果为空我们直接返回即可。
保持一条事务回滚记录：如果为空，我们保存一条Status为已执行空回滚状态的TransactionRecord。那么多余的prepare操作过来是，就可以判断到事务已经回滚，从而停止操作。

使用第一个策略，即没发现可回滚的事务时，回滚操作如果是直接返回，会有“事务悬挂”的坑，：

空回滚：

事务悬挂：

优化之后的代码：

 @Transactional
    void payAccount(int orderId, int userId, int opTotal){
        TransactionRecord tr = transactionRecordStorage.getForUpdate(orderId);	// 重点：加了锁
        if(tr != null){
            return;  // 重点：如果已经有数据了，这里直接返回。提交幂等性。
        }
        account.payAccount(userId, opTotal); // 实际的去我们account表扣减
        transactionRecordStorage.save(orderId, userId, opTotal, account.getId()); //保存事务记录表
    }
    @Transactional
    void rollback(int orderId, int userId){
         TransactionRecord tr = transactionRecordStorage.getForUpdate(orderId);
        if(tr == null){
            saveNullCancelTr(orderId, userId); // 重点：保存空回滚的记录
        }
        if(tr.isCanceled() || tr.isNullCancel()){
            return; //如果已经被取消了那么直接返回
        }
        //从记录表中查询
        account.rollbackBytr(tr); // 根据记录回滚

实战实例可详细参考：https://mp.weixin.qq.com/s?__biz=MzA5Mjg2MDQ5NQ==&mid=2452509457&idx=1&sn=edafa119519f6fa577f9f53ac9bd5287&scene=21#wechat_redirect

分布式事务小结参考文章：

雪花算法分布式ID

SnowFlake的结构如下（每部分用-分开），共64位:

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

1位正负标识。由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
41位差值时间戳(毫秒级)：存储差值（当前时间戳 - 开始时间戳) 。注意，41位时间截不是存储当前时间的时间戳，而是存储时间戳的差值（当前时间戳 - 开始时间戳) 得到的值）。这里的的开始时间戳，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下面程序IdWorker类的startTime属性）。

41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
10位的数据机器位。可以部署在1024个节点，包括5位datacenterId和5位workerId。
12位毫秒内的计数。12位的计数顺序号支持每个节点每毫秒（同一机器，同一时间截）产生4096个ID序号。12位不够用时强制得到新的时间前缀。

以上加起来刚好64位。特点：

性能综述：最多支持1024台机器，每毫秒产生4096个ID（每秒400w），持续69年。
优点：整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高。且可根据需要灵活调整各位数。
缺点：对系统时间的依赖性非常强，需关闭ntp的时间同步功能。

注意事项：

生成雪花算法的类，需要使用单例模式。
getNextId()等需要加锁保证线程安全。
超过当前毫秒容量问题：当前毫秒数获取不到时，可以空转一下到下一毫秒获取。
时钟回拨问题：当前时间戳小于上次记录的时间戳时，说明发生了时钟回拨，拒绝提供ID。

代码实现：

// 做了一点改造，机器ID从Redis获取。
// 或者也可以改成，直接当前时间 % 1024 来获取。这样可以做到无状态。
public final class SnowFlakeIdUtil {
    /** 起始的时间戳 */
    private final static long START_STAMP = 1567267200000L; // 2019年9月1日

    /** 每一部分占用的位数 */
    private final static long SEQUENCE_BIT = 12; // 序列号占用的位数
    private final static long DATE_MACHINE_BIT = 10; // 数据机器位

    /** 每一部分的最大值 */
    private final static long MAX_DATE_MACHINE_NUM = -1L ^ (-1L << DATE_MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /** 每一部分向左的位移 */
    private final static long DATE_MACHINE_LEFT = SEQUENCE_BIT;
    private final static long TIMESTAMP_LEFT = DATE_MACHINE_LEFT + DATE_MACHINE_BIT;

    /** 数据机器标识（通过分布式配置中心配置，默认为0）  */
    private long dataMachineId;
    /** 序列号 */
    private long sequence = 0L;
    /** 上一次时间戳 */
    private volatile long lastStamp = -1L;

    private static volatile SnowFlakeIdUtil idWorker = null;

    public static SnowFlakeIdUtil getInstance() {
        if (ObjectUtil.isNull(idWorker)) {
            synchronized (SnowFlakeIdUtil.class) {
                if (ObjectUtil.isNull(idWorker)) {
                    idWorker = new SnowFlakeIdUtil();
                }
            }
        }

        return idWorker;
    }

    public Long getdataMachineId() {return this.dataMachineId;}

    private SnowFlakeIdUtil() {
//    Long dataMachineIdL = SpringContextUtil.getBean(WindProperties.class).getDataMachineId();
        DataMachineIdListener dlisten = SpringContextUtil.getBean(DataMachineIdListener.class);
        if (ObjectUtil.isNull(dlisten)) {
            throw new IllegalArgumentException("DataMachineIdListener未注入！");
        }

        dataMachineId = dlisten.getRegistedDataMachineId();
        log.info("++++++++++++++++++++++++++++++ Id生成器所使用的dataMachineId:" + dataMachineId);
        if (dataMachineId > MAX_DATE_MACHINE_NUM || dataMachineId <= 0) {
            throw new IllegalArgumentException("dataMachineId 取值范围(0, " + MAX_DATE_MACHINE_NUM + "]");
        }
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStamp = getNewStamp();
        if (currStamp < lastStamp) {
            throw new RuntimeException("发生时钟回拨，拒绝生产id");
        }

        if (currStamp == lastStamp) {
            // 相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            // 同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currStamp = getNextMill();
            }
        } else {
            // 不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastStamp = currStamp;

        return (currStamp - START_STAMP) << TIMESTAMP_LEFT // 时间戳部分
                | dataMachineId << DATE_MACHINE_LEFT // 数据机器标识部分
                | sequence; // 序列号部分
    }

    private long getNextMill() {
        long mill = getNewStamp();
        while (mill <= lastStamp) {
            mill = getNewStamp();
        }
        return mill;
    }

    private long getNewStamp() {
        return System.currentTimeMillis();
    }
}

newSQL可分为三种：

新架构型：如Spanner、TiDB、OB。新架构NewSQL数据库存储设计即为基于paxos（或Raft）协议的多副本，相比于传统数据库主从模式（半同步转异步后也存在丢数问题），在实现了真正的高可用、高可靠（RTO<30s，RPO=0）。
中间件方案：如Sharding-Sphere、Mycat、DRDS等。
云数据库

newSQL数据量小的时候，性能可能还不如MySQL，因为有协调开销。现在有一些公司在用，如知乎、微众银行。

利弊分析可参考：https://www.jianshu.com/p/9131edd8fd2c

转载请注明来源