背景

存在多个服务实例

某个实例数据修改，数据一致性问题
某个实例宕机恢复，数据一致性问题
跨分区网络异常（脑裂），数据一致性问题

Paxos

是基于消息传递的一致性算法
有 Basic Paxos, Multi Paxos, Fast Paxos 版本

Basic Paxos

角色	介绍
client	发起请求1
proposer	接收client请求，发起提案2，请求提交提案4
acceptor	接收proposer提案，投票proposer提案3，执行proposer提案5
learner	执行proposer提案

Client   Proposer      Acceptor     Learner|          |           |  |  |       |  | --- First Request ---X----1---->|           |  |  |       |  |  Request|          X-----2---->|->|->|       |  |  Prepare(N)|          |<----3-----X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})|          X-----4---->|->|->|       |  |  Accept!(N,I,V)|          |<----5-----X--X--X------>|->|  Accepted(N,I,V)|<-----------------------------------X--X  Response|          |           |  |  |       |  |

提案编号自增
最新提案才会发起提案 proposer->acceptor
最新提案才会投接受票 acceptor->proposer
获得多数票才会请求提交提案 proposer->acceptor
落地提案最新才会执行提案 acceptor->proposer

问题：多个proposer固执己见，始终出现最新的落地提案，导致活锁
解决：等待随机时间才能发起提案

缺点：效率低（多个老大proposer），活锁问题

Multi-Paxos

第1阶段：

选leader。同于Basi-Paxos
提案被执行的proposer=leader

角色	介绍
client	发起请求1
proposer	接收client请求，发起提案2，请求提交提案4
acceptor	接受proposer提案，投票proposer提案3，执行proposer提案5
learner	执行proposer提案

Client   Proposer      Acceptor     Learner|          |           |  |  |       |  | --- First Request ---X----1---->|           |  |  |       |  |  Request|          X-----2---->|->|->|       |  |  Prepare(N)|          |<----3-----X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})|          X-----4---->|->|->|       |  |  Accept!(N,I,V)|          |<----5-----X--X--X------>|->|  Accepted(N,I,V)|<-----------------------------------X--X  Response|          |           |  |  |       |  |

第2阶段

角色	介绍
client	发起请求1
leader	接收client请求，请求提交提案2
acceptor	接收leader提案，投票proposer提案3，执行proposer提案4
learner	执行proposer提案

Client     Proposer      Acceptor        Learner|          |           |  |  |        |  |  --- Following Requests ---X----1---->|           |  |  |        |  |  Request|          X----2----->|->|->|        |  |  Accept!(N,I+1,W)|          |<---3------X--X--X---4--->|->|  Accepted(N,I+1,W)|<------------------------------------X--X  Response|          |           |  |  |        |  |

优点：效率高

Raft

分布式共识协议

第1阶段：选leader

角色	介绍
follower	所有结点初始都是follower
candidate	随机时钟到点成为candidate
leader	候选者获得多数票成为leader

第2阶段

角色	介绍
client	发起请求1
leader	接收client请求，记录日志，请求提交提案2
follower	接收leader提案，记录日志，投票proposer提案3，执行proposer提案4

Client     Proposer      Acceptor        Learner|          |           |  |  |        |  |  --- Following Requests ---X----1---->|           |  |  |        |  |  |          X----2----->|->|->|        |  |  |          |<---3------X--X--X        |  |  |          |<---4------X--X--X------->|->|  |<------------------------------------X--X  |          |           |  |  |        |  |