面试官军训分布式一致性机制
- 基本原则与理论 -
- 2PC -
-
提交事务请求(投票阶段) -
协调者向参与者发送事务内容,询问是否可以执行事务提交操作,等待响应 -
参与者执行事务操作,并将undo和redo日志记录 -
参与者回复协调者,执行成功则回Yes否则No -
执行事务提交(执行阶段) -
如果都是参与者都回复Yes,则协调者向参与者发送提交请求,否则发送回滚请求 -
参与者根据协调者的请求执行事务提交或回滚,并向协调者发送Ack消息 -
协调者收到所有的Ack消息过后判断事务的完成或者中断
- 3PC -
-
事务询问(canCommit) -
协调者向参与者发送一个包含事务内容的询问请求,询问是否可以执行事务并等待 -
参与者根据自己状态判断并回复yes、no -
执行事务预提交(preCommit) -
若协调者收到全是yes,就发送preCommit请求否则发布abort请求 -
参与者若收到preCommit则执行事务操作并记录undo和redo然后发送Ack,若收到abort或者超时则中断事务 -
执行事务提交(doCommit) -
协调者收到所有的Ack则发送doCommit请求,若收到了No或者超时则发送abort请求 -
参与者收到doCommit就执行提交并发送ACk,否则执行回滚并发送Ack -
协调者收到Ack判断是完成事务还是中断事务
- Paxos -
-
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
- Raft -
-
它赢得选举; -
另一个节点成为Leader; -
一段时间没有节点成为Leader。
如果出现两个Candidate得票一样多,则它们都无法获取超过半数投票,这种情况会持续到超时,然后进行新一轮的选举,这时同时的概率就很低了,那么首先发出投票请求的的Candidate就会得到大多数同意,成为Leader。
Raft协议目前被用于 cockrouchDB,TiKV等项目中,据我听的一些报告来看,一些大厂自己造的分布式数据库也在使用Raft协议。
- Gossip -
事实上现代互联网架构只要把单点做得足够强大,再加上若干个强一致的热备,一般问题都不大。
- NWR 机制 -
N:有多少份数据副本;
W:一次成功的写操作至少有w份数据写入成功;
R:一次成功的读操作至少有R份数据读取成功。
版本的新旧需要版本控制算法来判别,比如向量时钟。
当然R或者W不能太大,因为越大需要操作的副本越多,耗时越长。
- Quorum 机制 -
分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)才能读或者写。如果一个系统有V票(意味着一个数据对象有V份冗余拷贝),那么这最小读写票必须满足:
-
Vr + Vw > V -
Vw > V/2
第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。
- Lease 机制 -
租约机制也可以解决主备之间网络不通导致的双主脑裂问题,亦即:主备之间本来心跳连线的,但是突然之间网络不通或者暂停又恢复了或者太繁忙无法回复,这时备机开始接管服务,但是主机依然存活能对外服务,这是就发生争夺与分区,但是引入lease的话,老主机颁发给具体server的lease必然较旧,请求就失效了,老主机自动退出对外服务,备机完全接管服务。
参考:
https://en.wikipedia.org/wiki/Three-phase_commit_protocol
https://en.wikipedia.org/wiki/Paxos_(computer_science)
https://raft.github.io/
https://en.wikipedia.org/wiki/Raft_(computer_science)
https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
http://www.infoq.com/cn/articles/raft-paper
https://en.wikipedia.org/wiki/Gossip_protocol
从Paxos到ZooKeeper
分布式java应用
大数据日知录
http://m635674608.iteye.com/blog/2343038
来源:网络
程序员面试
聚焦程序员,Java,Spring boot,Spring cloud,Linux,Docker,Sql,kafka,Elasticsearch等面试,涵盖阿里,头条,百度,美团面试经验和题目分享!
Official Account