面试官：谈谈分布式一致性机制
前言
分布式中一致性是非常重要的，分为弱一致性和强一致性。
现在主流的一致性协议一般都选择的是弱一致性的特殊版本：最终一致性。下面就从分布式系统的基本原则讲起，再整理一些遵循这些原则的协议或者机制，争取通俗易懂。
但是要真正实施起来把这些协议落地，可不是一篇文章能说清楚的，有太多的细节，要自己去看论文呐（顺着维基百科找就行了）。
基本原则与理论
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，两阶段提交，系统有两个角色协调者和参与者，事务提交过程分为两阶段：
提交事务请求（投票阶段）
协调者向参与者发送事务内容，询问是否可以执行事务提交操作，等待响应
参与者执行事务操作，并将 undo 和 redo 日志记录
参与者回复协调者，执行成功则回 Yes 否则 No
执行事务提交（执行阶段）
如果都是参与者都回复 Yes，则协调者向参与者发送提交请求，否则发送回滚请求
参与者根据协调者的请求执行事务提交或回滚，并向协调者发送 Ack 消息
协调者收到所有的 Ack 消息过后判断事务的完成或者中断
该协议可以视为强一致的算法，通常用来保证多份数据操作的原子性，也可以实现数据副本之间的一致性，实现简单，但是缺点也很多，比如单点故障（协调者挂了整个系统就没法对外服务，任一节点挂了事务就没法执行，没有容错机制）、阻塞（两个阶段都涉及同步等待阻塞，极大降低了吞吐量）、数据不一致（参与者回复 Yes/No 后如果因为网络原因没有收到提交/中断请求，此时它就不知道该如何操作了，导致集群数据不一致）……
2PC 有些优化手段：超时判断机制，比如协调者发出事务请求后等待所有参与者反馈，若超过时间没有搜集完毕所有回复则可以多播消息取消本次事务；互询机制，参与者 P 回复 yes 后，等待协调者发起最终的 commitabort，如果没收到那么可以询问其他参与者 Q 来决定自身下一步操作，避免一直阻塞（如果其他参与者全都是等待状态，那么 P 也只能一直阻塞了）。所以 2PC 的阻塞问题是没办法彻底解决的。
当然，如果网络环境较好，该协议一般还是能很好的工作的，2PC 广泛应用于关系数据库的分布式事务处理，如 mysql 的内部与外部 XA 都是基于 2PC 的，一般想要把多个操作打包未原子操作也可以用 2PC。
3PC
3 Phase Commit，三阶段提交，是二阶段提交的改进，系统也有两个角色协调者和参与者，事务提交过程分为三阶段。另外，如果你近期准备面试跳槽，建议在 Java 面试库小程序在线刷题，涵盖 2000+ 道 Java 面试题，几乎覆盖了所有主流技术面试题。
事务询问（canCommit）
协调者向参与者发送一个包含事务内容的询问请求，询问是否可以执行事务并等待
参与者根据自己状态判断并回复 yes、no
执行事务预提交（preCommit）
若协调者收到全是 yes，就发送 preCommit 请求否则发布 abort 请求
参与者若收到 preCommit 则执行事务操作并记录 undo 和 redo 然后发送 Ack，若收到 abort 或者超时则中断事务
执行事务提交（doCommit）
协调者收到所有的 Ack 则发送 doCommit 请求，若收到了 No 或者超时则发送 abort 请求
参与者收到 doCommit 就执行提交并发送 ACk，否则执行回滚并发送 Ack
协调者收到 Ack 判断是完成事务还是中断事务
三阶段相对于两阶段的改善就是把准备阶段一分为二，亦即多了一个 canCommit 阶段，按我理解这样就类似于 TCP 的三步握手，多了一次确认，增大了事务执行成功的概率。而且 3PC 的协调者即使出了故障，参与者也能继续执行事务所以解决了 2PC 的阻塞问题，但是也可能因此导致集群数据不一致。
另外，如果你近期准备面试跳槽，建议在 Java 面试库小程序在线刷题，涵盖 2000+ 道 Java 面试题，几乎覆盖了所有主流技术面试题。
Paxos
上面两个协议的协调者都需要人为设置而无法自动生成，是不完整的分布式协议，而 Paxos 就是一个真正的完整的分布式算法。系统一共有几个角色：Proposer（提出提案）、Acceptor（参与决策）、Learner（不参与提案，只负责接收已确定的提案，一般用于提高集群对外提供读服务的能力），实践中一个节点可以同时充当多个角色。提案选定过程也大概分为 2 阶段：
Prepare 阶段
Proposer 选择一个提案编号 M，向 Acceptor 某个超过半数的子集成员发送该编号的 Prepare 请求
Acceptor 收到 M 编号的请求时，若 M 大于该 Acceptor 已经响应的所有 Prepare 请求的编号中的最大编号 N，那么他就将 N 反馈给 Proposer，同时承诺不会再批准任何编号小于 M 的提案
Accept 阶段
如果 Proposer 收到超过半数的 Acceptor 对于 M 的 prepare 请求的响应，就发送一个针对[M,V]提案的 Accept 请求给 Acceptor，其中 V 是收到的响应编号中编号的最大的提案值，如果响应中不包括任何提案值，那么他就是任意值
Acceptor 收到这个针对[M,V]的 Accept 请求只要改 Acceptor 尚未对大于 M 编号的提案做出过响应，他就通过这个提案
Learn 阶段（本阶段不属于选定提案的过程）
Proposer 将通过的提案同步到所有的 Learner
Paxos 协议的容错性很好，只要有超过半数的节点可用，整个集群就可以自己进行 Leader 选举，也可以对外服务，通常用来保证一份数据的多个副本之间的一致性，适用于构建一个分布式的一致性状态机。
Google 的分布式锁服务 Chubby 就是用了 Paxos 协议，而开源的 ZooKeeper 使用的是 Paxos 的变种 ZAB 协议。另外，如果你近期准备面试跳槽，建议在 Java 面试库小程序在线刷题，涵盖 2000+ 道 Java 面试题，几乎覆盖了所有主流技术面试题。
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 必然较旧，请求就失效了，老主机自动退出对外服务，备机完全接管服务。
原文：http://mageek.cn/archives/88/
如果感觉本文对你有帮助，点赞关注支持一下，想要了解更多 Java 后端，大数据，算法领域最新资讯可以关注我公众号【架构师老毕】私信 666 还可获取更多 Java 后端，大数据，算法 PDF+大厂最新面试题整理+视频精讲
需要资料添加小助理vx：bjmsb2020 2021-10-19 加入
爱生活爱编程
评论