PAXOS/RAFT理解

PAXOS学习记录

前提: 信息准确无篡改,通信环境可信

目的: 解决多结点间一致性问题(集群中一个修改或者申请成为主结点的提议)

主要角色

Proposer :提出议案(同时存在一个或者多个,他们各自发出提案)

Acceptor: 收到议案后选择是否接受

Learner: 酱油

提案: Value{编号,决议}

过程描述

A 准备 Proposer首先选择一个提议序号n给其他的Acceptor结点发出prepare消息。Acceptor收到prepare消息后,如果提议的序号大于他已经回复的所有prepare消息,则Acceptor将自己上次接受的提议回复给Proposer,并且承诺不再回复小于n的提议

B 批准 Proposers收到Acceptor中的多数派对prepare的回复后,进入准备阶段。如果在之前的prepare阶段Acceptor回复了上次接受的提议,那么Proposers选择其中序号最大的提议发送给Acceptor批准,否则,Proposers生成一个新的提议值发送给Acceptor批准,Acceptor在不违背之前在Prepare的承诺的前提下,接受这个请求。

C 确认 如果超过一半的Acceptor接受,提议值生效。Proposers发送acknowledge消息通知所有的Acceptor提议生效

每个*包含

LastTried[p]:由p试图发起的最后一个议案的编号,没有为负无穷

PreviousVote[p]:由P投票的所有表决中,编号最大的表决对应的投票,没有为负无穷

NextBallot[p]:由p发出的所有LastVote(b,v)消息中,表决编号b的最大值

流程

A. *p选择一个比LastTried[p]大的表决编号b,设置LastTried[p]=b,然后将NextBallot[p]消息发送给某些*

B. q从P收到一个b大于NextBallot[q]的nextBallot(b)消息后,q将NextBallot[q]=b,然后发送LastVote(b,v)给p,其中v=PreviousVote[q](b<=NextBallot[q]的NextBallot[b]消息被忽略)

C. 在某个多数集合Q中的每个成员都收到一个LastVote(b,v)消息后,p发起一个编号为b,法定人数为Q,议案为d的新表决。给Q中每一个牧师发送一个BeginBallot(b,d)消息

D. 在收到b=NextBallot[q]的BeginBallot(b,d)消息后,q在编号为b的表决中投出他的一票,设置PreviousVote[p]为这一票,然后向p发送Voted(b,q)消息

E. p收到Q中每个q的Voted(b,q)消息中,将d(这轮表决的法令)记下,然后发送一条Success(d)消息给每个q

F. 一个*在接受到Success(d)后,将决议d记录

原则:少数服从多数原则 如果同时有人提出议案,出现碰撞,双方都需要增加议案的编号再提交,活锁正确,可终止

http://www.cnblogs.com/endsock/p/3480093.html 这边文章例子非常好。

Raft

http://thesecretlivesofdata.com/raft/

leader election:

发出投票提议选自己,得到大多数投票则成功

Log replicaition:

master/slave系统中,客户端请求到master,写log entry uncommited,复制分发给slave,slave自己写log,告诉master,master commit,通知slave commit

https://www.cnblogs.com/mindwind/p/5231986.html

Raft 协议强依赖 Leader 节点的可用性来确保集群数据的一致性。数据的流向只能从 Leader 节点向 Follower 节点转移。当 Client 向集群 Leader 节点提交数据后,Leader 节点接收到的数据处于未提交状态(Uncommitted),接着 Leader 节点会并发向所有 Follower 节点复制数据并等待接收响应,确保至少集群中超过半数节点已接收到数据后再向 Client 确认数据已接收。一旦向 Client 发出数据接收 Ack 响应后,表明此时数据状态进入已提交(Committed),Leader 节点再向 Follower 节点发通知告知该数据状态已提交。

上一篇:底层算法系列:Paxos算法


下一篇:C++ ABI之名字改编(以Qt为例)