分布式互斥与同步

学习极客时间《分布式技术原理与算法解析》

1. 分布式概览#

1.1 分布式知识体系图#

1.2 分布式发展历程#

	单机模式	数据并行模式	任务并行模式
简介	所有业务和数据都在一台服务器上	让多台服务器放同样的代码逻辑，把要执行的数据拆分后分别放到这些服务器同时执行，用空间换时间	把单个任务拆分成多个子任务并行执行
优点	便于集中管理、维护、执行	缩短所有任务的总体执行时间	能缩短单个任务的执行时间
缺点	单台服务器有性能瓶颈，有单点失效问题	对提升单个任务的执行性能及降低时延无效	任务拆分的复杂性增加

1.3 分布式系统指标#

性能指标：

吞吐量
- QPS：每秒的查询数，常用于读操作；
- TPS：每秒处理的事务数，常用于写操作；
- BPS：每秒处理的比特数，常用于衡量数据量；
响应时间：系统响应一个请求所花费的时间，直接影响到用户体验
完成时间：系统真正完成一个请求所花费的时间

资源占用：

空载资源占用：系统在没有任何负载时，本身所自带的资源占用
满载资源占用：系统满额负载时的资源占用

可用性：

可用性：系统面对各种异常情况时依然可以正确提供服务的能力，体现了系统的鲁棒性，可用（正常运行时间/总运行时间）的比值来判断可用性高低，表示可以允许系统出现部分故障的情况下，仍能对外提供服务的能力。
可靠性：通常表示一个系统完全不出故障。

可扩展性：有横向的集群数量扩展，也有纵向的单机性能扩展。

不同场景下的指标要求：

2. 分布式互斥与同步#

2.1 分布式互斥#

在分布式系统里，访问临界资源，就叫分布式互斥；临界资源就是被互斥访问的共享资源。

分布式互斥方法：

	集中式方法	分布式方法	令牌环方法
描述	通过协调者，把所有请求放入队列，按FIFO的方式请求临界资源	每个请求者使用临界资源时，都要征求其他参与者的同意	所有参与者组成环，令牌顺/逆时针流动，拿到令牌的参与者则可访问临界资源
优点	简单、通信高效、易实现	可用性高	单个参与者通信效率高，因为不用请求其他参与者同意
缺点	瓶颈在协调者，可用性低	通信成本高、复杂度高	容易造成无用通信，例如一轮下来，只有几个参与者需要访问令牌
场景	在协调者稳定性高的情况下适合使用	系统规模小或使用频度低的情况下	系统规模小、每个参与者使用临界资源的频率高的情况下

2.2 分布式选举#

分布式选举主要是选出主节点，该主节点在分布式集群中对其他子节点进行协调和管理，保证集群有序运行和节点间数据的一致性。

	Bully算法	Raft算法	ZAB算法
描述	遵循长者为大的原则，即在所有活着的节点中，选取 ID 最大的节点作为主节点	少数服从多数原则，获得投票最多的节点成为主节点(超过半数即可为leader)	ZAB协议是专门为zookeeper实现分布式协调功能而设，遵循少数服从多数，ID 大的节点优先为主的原则，可以看成对Raft算法的改进
选举过程	Election消息：用于发起选举，如p1->p2发送选举消息，表示p1支持选举p2当Leader。Alive消息：若本节点收到比自己 ID 小的节点发送的 Election 消息，则回复一个 Alive 消息，告知其他节点，我比你大，重新选举。Victory消息：若在给定的时间范围内，本节点没有收到其他节点回复的 Alive 消息，则认为自己成为主节点，并向其他节点发送 Victory 消息，宣誓自己成为主节点。	Follower状态：开始时所有节点都是Follower状态，Follower 节点会定期发送心跳包给Leader节点，以检测主节点是否活着。Candidate状态：开始选主时所有Follower转为Candidate状态，发送选举请求，每个节点只有一次投票权。Leader状态：发起选举请求的节点获得超过一半的投票，变为Leader状态。Leader任期到了，会降为Follower状态，参与新一轮选举。	Looking 状态，即选举状态。当节点处于该状态时，它会认为当前集群中没有 Leader，因此自己进入选举状态。Leading 状态，即领导者状态，表示已经选出主，且当前节点为 Leader。Following 状态，即跟随者状态，集群中已经选出主后，其他非主节点状态更新为Following，表示对 Leader 的追随。Observing 状态，即观察者状态，表示当前节点为 Observer，持观望态度，没有投票权和选举权。
优点	简单、快速、复杂度低、易实现	快速、复杂度低、易实现更稳定，当有新节点加入时会触发选主，但不一定能拿到超过一般的票数而切主。	稳定性好，当有新节点加入时会触发选主，但不一定能拿到超过一般的票数而切主。算法性能高
缺点	因为需要每个节点有全局信息，所以额外信息存储较多。只要随便新进来一个ID比当前leader的ID大的，就会易主，所以导致容易频繁易主。不适合大规模分布式系统。	因为要求所有节点都可以互相通信且要参与投票，所以导致通信量大、连接数多，不适合大规模集群	因为采用广播方式发送消息，当节点多的时候容易发生广播风暴。选举时间长复杂度高
场景	适用于小规模分布式系统	适合中小规模场景	适合大规模分布式系统

为什么选举算法常采用奇数个节点？

因为偶数个节点容易出现两个主的情况，造成重新选主，而且第二次选主依然有概率出现两个主的情况。

2.3 分布式共识#

分布式共识：分布式共识就是在多个节点均可独自操作或记录的情况下，使得所有节点针对某个状态达成一致的过程。比如通过分布式共识，使得分布式系统中不同节点的数据达成一致。

分布式共识比较常用与区块链技术中。比如有5台服务器，其中一台进行了金钱转账，那么如何让另外4台服务器也达到一样的状态呢？这就是分布式共识要解决的问题。在分布式在线记账问题中，针对同一笔交易，有且仅有一个节点或服务器可以获得记账权，然后其他节点或服务器同意该节点或服务器的记账结果，达成一致。也就是说，分布式共识包括两个关键点，获得记账权和所有节点或服务器达成一致

分布式共识方法：

	PoW	PoS	DPoS
全称	Proof-of-Work工作量证明	Proof-of-Stake权益证明	Delegated Proof of Stake委托权益证明
过程	每个节点都去解同一道题目，哪个节点先得出正确答案，就获得记账权，简单来说：谁的计算能力强，获得记账权的可能性就越大	由系统权益代替算力来决定区块记账权，拥有的权益越大获得记账权的概率就越大	相比于 PoS 算法，DPoS 引入了受托人，由投票选举出的若干信誉度更高的受托人记账，解决了所有节点均参与竞争导致消息量大、达成一致的周期长的问题。
优点	去中心化、安全性高	解决了Pow算法的问题，效率高	解决了 PoS 算法的垄断问题，能耗更低，速度更快
缺点	如果题目过难，则计算时间过长，导致资源浪费；如果题目过于简单，会导致大量节点获取记账权，导致冲突。总结来说就是达成共识的时间长，效率偏低。	去中心化程度和安全性不如PoW，易造成垄断	去中心化程度不如前面的两种算法，投票积极性不高
场景	比特币	以太坊	以太股

2.4 分布式事务#

分布式事务就是在分布式系统中运行的事务，由多个本地事务组合而成，都要遵循ACID原则。

2.4.1 二阶段提交法#

准确来说是基于XA协议的二阶段提交法

XA协议：分为两部分，即事务管理器和本地资源管理器。事务管理器作为协调者负责各个本地资源的提交和回滚；资源管理器就是分布式事务的参与者，通常由数据库实现。

为了保证事务的一致性，需要引入一个协调者来管理所有节点，分为投票阶段和提交阶段。

阶段	过程
投票阶段	① 协调者发送请求给参与者，询问是否可以执行提交(commit)操作。② 参与者收到请求后，会执行请求中的事务操作，并将undo信息和redo信息写入事务日志，但不提交(commit)。若执行成功，会返回yes；若执行失败，会返回no。③ 协调者等待所有参与者返回操作结果后进入提交阶段。
提交阶段	情况一，协调者收到的都是yes：① 协调者向所有参与者发送正式 commit 的请求② 参与者完成操作后释放占用的资源③ 参与者向协调者返回“ack完成”消息④ 协调者收到所有参与者的回复后意味着这个事务结束了情况二，协调者收到的信息中存在no：① 协调者向所有参与者发送 rollback 请求② 参与者收到 rollback 消息后利用之前的undo日志执行回滚③ 参与者回滚完后释放占用的资源④ 参与者向协调者恢复 ack回滚完成信息⑤ 协调者收到所有参与者的回复后，取消事务

阶段

过程

投票阶段

① 协调者发送请求给参与者，询问是否可以执行提交(commit)操作。② 参与者收到请求后，会执行请求中的事务操作，并将undo信息和redo信息写入事务日志，但不提交(commit)。若执行成功，会返回yes；若执行失败，会返回no。③ 协调者等待所有参与者返回操作结果后进入提交阶段。

提交阶段

情况一，协调者收到的都是yes：① 协调者向所有参与者发送正式 commit 的请求② 参与者完成操作后释放占用的资源③ 参与者向协调者返回“ack完成”消息④ 协调者收到所有参与者的回复后意味着这个事务结束了情况二，协调者收到的信息中存在no：① 协调者向所有参与者发送 rollback 请求② 参与者收到 rollback 消息后利用之前的undo日志执行回滚③ 参与者回滚完后释放占用的资源④ 参与者向协调者恢复 ack回滚完成信息⑤ 协调者收到所有参与者的回复后，取消事务

存在的问题：

① 同步阻塞问题。因为所有节点都是事务阻塞型，所有只要有一个节点在访问临界资源时，其他节点只能等待

② 单点故障问题。一旦某个节点发生故障，则会锁定事务资源，其他节点也会处于等待状态，导致整个系统阻塞

③ 数据不一致问题。在提交阶段，在协调者向参与者发送提交请求后，若因为网络或其他原因导致只有部分参与者接收到了请求并执行，于是就会出现数据不一致的问题

2.4.2 三阶段提交法#

三阶段提交是在二阶段提交的基础上，中间加了一个预提交阶段，改善了同步阻塞问题和数据不一致问题

阶段	过程
投票阶段	协调者向参与者发送请求，询问是否可以执行事务操作，参与者回复yes或no
预提交阶段	情况一，协调者收到的都是yes：① 协调者向参与者发送预提交请求，进入预提交阶段② 参与者接收到请求后执行事务操作，并记录undo日志和redo日志③ 若参与者成功执行了事务，则返回 ack成功信息情况二，协调者收到的信息中存在no：① 协调者向所有参与者发送中中断请求② 参与者接收到中断请求后，或超时仍未接收到协调者的信息，执行事务的中断操作
提交阶段	情况一：正式提交阶段：① 协调者接收到所有参与者的 ack成功响应后，向参与者发送正式提交消息② 参与者收到协调者的正式提交消息后，正式提交事务，完成后释放锁住的资源③ 参与者提交完事务后，向协调者回复 ack 响应④ 协调者收到所有参与者的响应后，表示完成事务情况二：事务中断阶段：① 协调者向所有参与者发送回滚请求② 参与者收到回滚消息后，利用预提交阶段记录的undo日志进行事务的回滚，并释放事务资源③ 参与者回滚完成想协调者回复ack消息④ 协调者收到参与者回滚完成的消息后结束事务

2.4.3 最终一致性方案#

二阶段提交和三阶段提交都存在两个问题：① 处理事务时都需要锁定资源。② 仍然存在数据不一致的问题。

所以提出了最终一致性的方案，准确来说是基于消息队列的最终一致性方案。这个消息队列用于在多个节点之间传递消息，因为消息队列本身具有存储功能，所以可以用来存储消息和日志。

大致思想如下：

① 生产者可以向消息队列发送具体的消息

② 消息队列把消息存起来，然后异步发送给消费者

③ 消费者收到消息后可以异步执行各自的具体事务，不管是执行成功还是失败都要给消息队列返回响应

④ 若消息队列收到了某个消费者返回执行成功的消息，表示这个消费者完成了任务

⑤ 若消息队列收到了某个消费者返回执行失败的消息，则消息队列会继续给这个消费者发送消息，即失败重试

⑥ 当所有消费者都完成事务后，才会删除消息队列里的消息，即最终一致性

2.4.4 总结#

刚性事务	柔性事务
如二阶段提交和三阶段提交	如最终一致性方案
遵循ACID原则	遵循BASE理论，BASE 理论包括：① 基本可用（Basically Available）② 柔性状态（Soft State）③ 最终一致性（Eventual Consistency）
缺点：① 数据不一致问题② 性能低③ 吞吐量一般优点：① 强一致性② 同步执行③ 算法实现简单④ 三阶段提交解决了二阶段提交同步阻塞问题和单点故障问题	缺点：① 算法复杂度高优点：① 最终一致性② 异步执行③ 性能高④ 吞吐量高⑤ 无同步阻塞问题⑥无单点故障问题

2.5 分布式锁#

锁是实现多线程访问同一共享资源，保证同一时刻只有一个线程可访问共享资源所做的一种标记。分布式锁处于分布式环境中，具有多个服务器，实现分布式互斥。为了保证多个进程可以看到锁，一般把锁存放在公共存储中（如redis、数据库等）。

分布式锁应该具有这些特征：

互斥性：只能有一个客户端持有锁
超时释放：防止死锁
可重入：一个线程获取锁后，可以再次加请求加锁，更新过期时间等
高性能、高可用：使开销尽可能低，可用性高
安全性：锁只能被持有的客户端删除，不能被其他客户端删除

2.5.1 基于数据库#

关于mysql锁的介绍，我写过一篇文章： Title MySQL锁的总结

基于数据库的增删
- 这是最简单的一种方式，即在数据库创建一张专门用于存放锁标记的锁表。当某个请求(A)对数据库的某个共享资源操作时，就往锁表增加一条记录，表示锁住了该资源，当操作完成后，就删除这条记录，表示释放锁。其他请求(B)想要操作该资源时都要先查询锁表，看是否有请求在操作该共享资源，如果有，就要等待，否则往锁表插入记录，表示请求(B)锁定了该资源。
- 优点：容易理解、复杂性低
- 缺点：单点故障，容易导致整体系统崩溃；死锁问题，锁没有限定失效时间；数据存放在磁盘，有IO读写开销，操作数据库开销大
基于数据库的排它锁
- 即在执行语句的时候添加for update，如：select ... from ... for update，当加上排它锁的时候，其他事务不能加锁

基于数据库的分布式锁适合于并发量低的场景

2.5.2 基于Redis#

redis是基于内存的，所以数据都存放在内存中，不需要写入磁盘，减少了IO操作。

如下是几种Redis实现分布式锁的方案：

SETNX EXPIRE

SETNX是（set if not exists）的缩写，如果 key不存在，则SETNX成功返回1，如果这个key已经存在了，则返回0。EXPIRE则是设置过期时间，防止死锁。

代码语言：javascript复制

if nx := redis.SetNX("lock_key", "lock_value", 0); nx.Val() == true {	// 加锁
	redis.Expire("lock_key", 100)	// 设置过期时间

    // todo 执行业务逻辑

	redis.Del("lock_key")	// 释放锁
}

缺点：setnx和expire两个操作是分开的，不是原子性操作，如果执行完setnx后出现了故障，那么就没法设置过期时间，锁就得不到释放，导致死锁。

SET扩展参数

为了解决不是原子性执行的问题，Redis 作者加入了 set 指令的扩展参数，使得 setnx 和 expire 指令可以一起执行，解决了上述问题。SET key value[EX seconds][PX milliseconds][NX|XX]

代码语言：javascript复制

/*
从 Redis 2.6.12 版本开始， SET 命令的行为可以通过一系列参数来修改：
    EX second ：设置键的过期时间为 second 秒。 
    			SET key value EX second 效果等同于 SETEX key second value 。
    PX millisecond ：设置键的过期时间为 millisecond 毫秒。 
    				 SET key value PX millisecond 效果等同于 PSETEX key millisecond value 。
    NX ：只在键不存在时，才对键进行设置操作。 
    	 SET key value NX 效果等同于 SETNX key value 。
    XX ：只在键已经存在时，才对键进行设置操作。
*/

// 根据官方说法
// 因为 SET 命令可以通过参数来实现 SETNX 、 SETEX 和 PSETEX 三个命令的效果，
// 所以将来的 Redis 版本可能会废弃并最终移除 SETNX 、 SETEX 和 PSETEX 这三个命令。

// 根据 go-redis 的源码
//
// Redis `SET key value [expiration] NX` command.
// Zero expiration means the key has no expiration time.
func (c *cmdable) SetNX(key string, value interface{}, expiration time.Duration) *BoolCmd {
	var cmd *BoolCmd
	if expiration == 0 {
		// Use old `SETNX` to support old Redis versions.
		cmd = NewBoolCmd("setnx", key, value)
	} else {
		if usePrecise(expiration) {
			cmd = NewBoolCmd("set", key, value, "px", formatMs(expiration), "nx")
		} else {
			cmd = NewBoolCmd("set", key, value, "ex", formatSec(expiration), "nx")
		}
	}
	c.process(cmd)
	return cmd
}

// 因此用go语言实现该方案的写法为
if nx := redis.SetNX("lock_key", "lock_value", 100); nx.Val() == true {	// 加锁并设置过期时间，为原子操作
	// todo 执行业务逻辑

	redis.Del("lock_key")	// 释放锁
}

上面两种方案都有可能出现超时问题，即业务执行时间超出了锁的超时限制，这个时候锁释放了，但是业务逻辑还在执行，其他线程可以拿到锁，导致数据被修改

还可能导致锁的误删除，如线程a执行完后即将要释放锁时，却提前被线程b占有了锁，此时线程a不知道，就把线程b的锁释放掉了，但此时线程b的业务都还没有执行完。

SET扩展参数校验唯一随机值 Lua脚本

为了解决在释放锁之前容易被其他线程拿到锁并被误删的问题，可以为 value 参数设置为一个随机数，释放锁时先匹配随机数是否一致，然后再删除 key。

代码语言：javascript复制

if nx := redis.SetNX("lock_key", "lock_value", 1000); nx.Val() == true { // 加锁并设置过期时间，为原子操作
    // todo 执行业务逻辑

    if redis.Get("lock_key").Val() == "lock_value" { // 判断是不是当前线程加的锁,是才释放
        redis.Del("lock_key") // 释放锁
    }
}

但是匹配 value 和删除 key 不是一个原子操作，Redis 也没有提供类似于 delifequals 这样的指令，这就需要使用 Lua 脚本来处理了，因为 Lua 脚本可以保证连续多个指令的原子性执行。

代码语言：javascript复制

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

当然还有很多算法和方法用于实现redis分布式锁，如Redlock和Java中的Redisson，本文暂不讨论。

优势：

避免了频繁磁盘IO
可用集群部署，避免了单点故障
适合高并发场景

缺点：

容易时间超时而不正确释放锁

2.5.3 基于ZooKeeper#

暂时不讨论，打算以后专门出一篇文章学习ZooKeeper。

Title ZooKeeper 3.8 文档

Title ZooKeeper 菜鸟教程

3. 参考#

https://juejin.cn/post/6936956908007850014 https://juejin.cn/post/7041375517580689439 https://github.com/go-redis/redis https://blog.csdn.net/m0_67645544/article/details/124768505 极客时间《分布式技术原理与算法解析》

编程算法消息队列CMQ版 kafka 数据库 sql

0 人点赞