《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 mageek.cn/archives/88/ 「mageek」欢迎转载,保留摘要,谢谢!


🙂🙂🙂关注微信公众号:【芋道源码】有福利:

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言将得到认真回复。甚至不知道如何读源码也可以请教噢
  4. 新的源码解析文章实时收到通知。每周更新一篇左右
  5. 认真的源码交流微信群。

前言

分布式中一致性是非常重要的,分为弱一致性和强一致性。现在主流的一致性协议一般都选择的是弱一致性的特殊版本:最终一致性。下面就从分布式系统的基本原则讲起,再整理一些遵循这些原则的协议或者机制,争取通俗易懂。但是要真正实施起来把这些协议落地,可不是一篇文章能说清楚的,有太多的细节,要自己去看论文呐(顺着维基百科找就行了)。

基本原则与理论

CAP(Consistency一致性,Availability可用性,Partition tolerance分区容错性)理论是当前分布式系统公认的理论,亦即一个分布式系统不可能同时满足这三个特性,只能三求其二。对于分布式系统,P是基本要求,如果没有P就不是分布式系统了,所以一般都是在满足P的情况下,在C和A之间寻求平衡。

ACID(Atomicity原子性,Consistency一致性,Isolation隔离性,Durability持久性)是事务的特点,具有强一致性,一般用于单机事务,分布式事务若采用这个原则会丧失一定的可用性,属于CP系统。

BASE(Basically Availabe基本可用,Soft state软状态,Eventually consistency最终一致性)理论是对大规模的互联网分布式系统实践的总结,用弱一致性来换取可用性,不同于ACID,属于AP系统。

2PC

2 Phase Commit,两阶段提交,系统有两个角色协调者和参与者,事务提交过程分为两阶段:

  1. 提交事务请求(投票阶段)

  2. 协调者向参与者发送事务内容,询问是否可以执行事务提交操作,等待响应

  • 参与者执行事务操作,并将undo和redo日志记录
  • 参与者回复协调者,执行成功则回Yes否则No
  1. 执行事务提交(执行阶段)

  2. 如果都是参与者都回复Yes,则协调者向参与者发送提交请求,否则发送回滚请求

  • 参与者根据协调者的请求执行事务提交或回滚,并向协调者发送Ack消息
  • 协调者收到所有的Ack消息过后判断事务的完成或者中断

该协议可以视为强一致的算法,通常用来保证多份数据操作的原子性,也可以实现数据副本之间的一致性,实现简单,但是缺点也很多,比如单点故障(协调者挂了整个系统就没法对外服务,任一节点挂了事务就没法执行,没有容错机制)、阻塞(两个阶段都涉及同步等待阻塞,极大降低了吞吐量)、数据不一致(参与者回复Yes/No后如果因为网络原因没有收到提交/中断请求,此时它就不知道该如何操作了,导致集群数据不一致)……

2PC有些优化手段:超时判断机制,比如协调者发出事务请求后等待所有参与者反馈,若超过时间没有搜集完毕所有回复则可以多播消息取消本次事务;互询机制,参与者P回复yes后,等待协调者发起最终的commitabort,如果没收到那么可以询问其他参与者Q来决定自身下一步操作,避免一直阻塞(如果其他参与者全都是等待状态,那么P也只能一直阻塞了)。所以2PC的阻塞问题是没办法彻底解决的。

当然,如果网络环境较好,该协议一般还是能很好的工作的,2PC广泛应用于关系数据库的分布式事务处理,如mysql的内部与外部XA都是基于2PC的,一般想要把多个操作打包未原子操作也可以用2PC。

3PC

3 Phase Commit,三阶段提交,是二阶段提交的改进,系统也有两个角色协调者和参与者,事务提交过程分为三阶段:

  1. 事务询问(canCommit)

  2. 协调者向参与者发送一个包含事务内容的询问请求,询问是否可以执行事务并等待

  • 参与者根据自己状态判断并回复yes、no
  1. 执行事务预提交(preCommit)

  2. 若协调者收到全是yes,就发送preCommit请求否则发布abort请求

  • 参与者若收到preCommit则执行事务操作并记录undo和redo然后发送Ack,若收到abort或者超时则中断事务
  1. 执行事务提交(doCommit)

  2. 协调者收到所有的Ack则发送doCommit请求,若收到了No或者超时则发送abort请求

  • 参与者收到doCommit就执行提交并发送ACk,否则执行回滚并发送Ack
  • 协调者收到Ack判断是完成事务还是中断事务

图片

三阶段相对于两阶段的改善就是把准备阶段一分为二,亦即多了一个canCommit阶段,按我理解这样就类似于TCP的三步握手,多了一次确认,增大了事务执行成功的概率。而且3PC的协调者即使出了故障,参与者也能继续执行事务所以解决了2PC的阻塞问题,但是也可能因此导致集群数据不一致。

Paxos

上面两个协议的协调者都需要人为设置而无法自动生成,是不完整的分布式协议,而Paxos 就是一个真正的完整的分布式算法。系统一共有几个角色:Proposer(提出提案)、Acceptor(参与决策)、Learner(不参与提案,只负责接收已确定的提案,一般用于提高集群对外提供读服务的能力),实践中一个节点可以同时充当多个角色。提案选定过程也大概分为2阶段:

  1. Prepare阶段

  2. Proposer选择一个提案编号M,向Acceptor某个超过半数的子集成员发送该编号的Prepare请求

  • Acceptor收到M编号的请求时,若M大于该Acceptor已经响应的所有Prepare请求的编号中的最大编号N,那么他就将N反馈给Proposer,同时承诺不会再批准任何编号小于M的提案
  1. Accept阶段

  2. 如果Proposer收到超过半数的Acceptor对于M的prepare请求的响应,就发送一个针对[M,V]提案的Accept请求给Acceptor,其中V是收到的响应编号中编号的最大的提案值,如果响应中不包括任何提案值,那么他就是任意值

  • Acceptor收到这个针对[M,V]的Accept请求只要改Acceptor尚未对大于M编号的提案做出过响应,他就通过这个提案
  1. Learn阶段(本阶段不属于选定提案的过程)

  2. Proposer将通过的提案同步到所有的Learner

图片

Paxos协议的容错性很好,只要有超过半数的节点可用,整个集群就可以自己进行Leader选举,也可以对外服务,通常用来保证一份数据的多个副本之间的一致性,适用于构建一个分布式的一致性状态机。

Google的分布式锁服务Chubby就是用了Paxos协议,而开源的ZooKeeper使用的是Paxos的变种ZAB协议。

Raft

Raft协议对标Paxos,容错性和性能都是一致的,但是Raft比Paxos更易理解和实施。系统分为几种角色:Leader(发出提案)、Follower(参与决策)、Candidate(Leader选举中的临时角色)。

刚开始所有节点都是Follower状态,然后进行Leader选举。成功后Leader接受所有客户端的请求,然后把日志entry发送给所有Follower,当收到过半的节点的回复(而不是全部节点)时就给客户端返回成功并把commitIndex设置为该entry的index,所以是满足最终一致性的。

Leader同时还会周期性地发送心跳给所有的Follower(会通过心跳同步提交的序号commitIndex),Follower收到后就保持Follower状态(并应用commitIndex及其之前对应的日志entry),如果Follower等待心跳超时了,则开始新的Leader选举:首先把当前term计数加1,自己成为Candidate,然后给自己投票并向其它结点发投票请求。直到以下三种情况:

  • 它赢得选举;
  • 另一个节点成为Leader;
  • 一段时间没有节点成为Leader。

在选举期间,Candidate可能收到来自其它自称为Leader的写请求,如果该Leader的term不小于Candidate的当前term,那么Candidate承认它是一个合法的Leader并回到Follower状态,否则拒绝请求。

如果出现两个Candidate得票一样多,则它们都无法获取超过半数投票,这种情况会持续到超时,然后进行新一轮的选举,这时同时的概率就很低了,那么首先发出投票请求的的Candidate就会得到大多数同意,成为Leader。

图片

在Raft协议出来之前,Paxos是分布式领域的事实标准,但是Raft的出现打破了这一个现状(raft作者也是这么想的,请看论文),Raft协议把Leader选举、日志复制、安全性等功能分离并模块化,使其更易理解和工程实现,将来发展怎样我们拭目以待(挺看好)。

Raft协议目前被用于 cockrouchDB,TiKV等项目中,据我听的一些报告来看,一些大厂自己造的分布式数据库也在使用Raft协议。

Gossip

Gossip协议与上述所有协议最大的区别就是它是去中心化的,上面所有的协议都有一个类似于Leader的角色来统筹安排事务的响应、提交与中断,但是Gossip协议中就没有Leader,每个节点都是平等的。

图片

每个节点存放了一个key,value,version构成的列表,每隔一定的时间,节点都会主动挑选一个在线节点进行上图的过程(不在线的也会挑一个尝试),两个节点各自修改自己较为落后的数据,最终数据达成一致并且都较新。节点加入或退出都很容易。

去中心化的Gossip看起来很美好:没有单点故障,看似无上限的对外服务能力……本来随着Cassandra火了一把,但是现在Cassandra也被抛弃了,去中心化的架构貌似难以真正应用起来。归根到底我觉得还是因为去中心化本身管理太复杂,节点之间沟通成本高,最终一致等待时间较长……往更高处看,一个企业(甚至整个社会)不也是需要中心化的领导(或者制度)来管理吗,如果没有领导(或者制度)管理,大家就是一盘散沙,难成大事啊。

事实上现代互联网架构只要把单点做得足够强大,再加上若干个强一致的热备,一般问题都不大。

NWR 机制

首先看看这三个字母在分布式系统中的含义:

N:有多少份数据副本;
W:一次成功的写操作至少有w份数据写入成功;
R:一次成功的读操作至少有R份数据读取成功。

NWR值的不同组合会产生不同的一致性效果,当W+R>N的时候,读取操作和写入操作成功的数据一定会有交集,这样就可以保证一定能够读取到最新版本的更新数据,数据的强一致性得到了保证,如果R+W<=N,则无法保证数据的强一致性,因为成功写和成功读集合可能不存在交集,这样读操作无法读取到最新的更新数值,也就无法保证数据的强一致性。

版本的新旧需要版本控制算法来判别,比如向量时钟。

当然R或者W不能太大,因为越大需要操作的副本越多,耗时越长。

Quorum 机制

Quorom机制,是一种分布式系统中常用的,用来保证数据冗余和最终一致性的投票算法,主要思想来源于鸽巢原理。在有冗余数据的分布式存储系统当中,冗余数据对象会在不同的机器之间存放多份拷贝。但是同一时刻一个数据对象的多份拷贝只能用于读或者用于写。

分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)才能读或者写。如果一个系统有V票(意味着一个数据对象有V份冗余拷贝),那么这最小读写票必须满足:

  • Vr + Vw > V
  • Vw > V/2

第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候,它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr,因此不能再有读请求过来了。同理,当读请求已经获得了Vr个冗余拷贝的许可时,写请求就无法获得许可了。

第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。

Quorum机制其实就是NWR机制。

Lease 机制

master给各个slave分配不同的数据,每个节点的数据都具有有效时间比如1小时,在lease时间内,客户端可以直接向slave请求数据,如果超过时间客户端就去master请求数据。一般而言,slave可以定时主动向master要求续租并更新数据,master在数据发生变化时也可以主动通知slave,不同方式的选择也在于可用性与一致性之间进行权衡。

租约机制也可以解决主备之间网络不通导致的双主脑裂问题,亦即:主备之间本来心跳连线的,但是突然之间网络不通或者暂停又恢复了或者太繁忙无法回复,这时备机开始接管服务,但是主机依然存活能对外服务,这是就发生争夺与分区,但是引入lease的话,老主机颁发给具体server的lease必然较旧,请求就失效了,老主机自动退出对外服务,备机完全接管服务。

文章目录
  1. 1. 前言
  2. 2. 基本原则与理论
  3. 3. 2PC
  4. 4. 3PC
  5. 5. Paxos
  6. 6. Raft
  7. 7. Gossip
  8. 8. NWR 机制
  9. 9. Quorum 机制
  10. 10. Lease 机制