|
概览分布式一致性协议和算法 2PC 3PC 拜占庭将军问题 Paxos ZAB Raft
拜占庭将军问题
byzantine https://www.jianshu.com/p/8bcef0ca676c
拜占庭问题，假设节点总数是N，叛徒节点数为F。如果需要达成一致性的认识，则当 N 》= 3F+1 时，问题才有解，共识才能达成，这就是Byzantine Fault Tolerant（BFT）算法。
Quorum NRW系统一致性策略
N: 分布式系统的副本总数
R: 读操作需要参与确认的最少副本数
W: 写操作需要参与确认的最少副本数
若 R+W>N，那么系统可以保证强一致性；
若 R=1, W=N，适用于频繁读、对读性能要求低，对写性能要求高的系统；
若 R=N, W=1，适用于频繁写、对读性能要求低，对写性能要求高的系统；
R=W=ceil(N/2), 读写性能平衡。
分布式事务协议 2PC 3PC
2pc 3pc https://blog.csdn.net/skyie53101517/article/details/80741868
2PC(2 Phase Commit)
- 角色：coordinator协调者, participants参与者
- 事务请求阶段（commit-request stage)
c–request–>p
p: lock resource, undo redo
p – ack / no–> c
- 提交阶段
c --commit / abort --> p
p – ack ->c
- 问题：
- c单点故障
- 各节点事务性阻塞
- 数据不一致
- 脑裂：协调者在发出commit消息之后宕机，如果只有部分参与者接收并执行了Commit请求,会导致节点数据不一致。如果这些接受到Commit消息的部分参与者也都宕机，那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
3PC
- 角色：coordinator协调者, participants参与者
1.CanCommit Stage
c–CanCommit–>p
p – ack / reject --> c
- PreCommit
c–PreCommit–>p
p: lock resource, undo redo
p – ack / no–> c (if timeout, c sends abort request in 3rd stage)
- DoCommit
c --commit / abort --> p (if timeout, p commit)
p – ack ->c
- 相比2PC特点：
- c, p端都引入超时机制, 解决单点故障， 各节点事务性阻塞
- 数据不一致
- 由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
So, here is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. --Mike Burrows
状态机副本集和分布式主备系统
state machine replication vs primary-backup https://www.jianshu.com/p/4dcf3325269d
State Machine
- 状态机：一组状态之间的转换关系。带状态的，（用函数式编程的说法是非函数式的）
- InitialState – Commandx --> StateA – Commandy --> StateB…
- 状态机的输出依赖于当前的输入（命令）和历史的输入
- 状态机是确定性的，在给定两次运行的情况下，它接收到相同的请求序列，它总是进行相同的内部状态转换并产生相同的回复。
分布式系统模型
分布式系统模型：
- 在一个由一组进程 {P1, P2, …, Pn}组成的分布式系统中，其每个进程都有各自的存储设备，进程间通过相互通信来实现消息的传递。
- 每个进程随时有可能崩溃退出(进入DOWN状态)，在退出后还有可能再次加入(重新进入UP状态)。
- 每个进程持有的上下文即为进程的状态，这样的进程可以视为一个状态机，分布式系统可视为分布式的状态机。
分布式系统间的同步方式
- 同步操作
操作必须是确定性的，如跟时间、随机数相关的的操作就会导致各节点操作的结果不一致。
- 同步操作后的值
操作先作用到Primary节点上，即使操作本身是不确定的，但结果的值是确定的。其他节点同步操作后的值，数据具有一致性。
进阶：如果数据值本身比较大，同步值的做法IO代价较高。可以在primary节点将非确定的操作的确定实现同步，譬如，同步操作ADD Random()，随机值为ADD 2
Primary-backup
Paxos
https://www.jianshu.com/p/06a477a576bf
- 角色： Proposer, Acceptor, Learner
- 原则：
1.prepare | promise stage
- Acceptor 回复（promise)收到的第一个proposal或大于当前接受proposal编号的proposal
- Accept stage
- Proposer 获得大多数（过半数）Acceptor 的promise则向回复promise的Acceptor发送accept请求
- 其他Learner学习 Acceptor的结果
ZAB(Zookeeper Atomic Broadcast)协议
zab https://www.cnblogs.com/wttttt/p/7500663.html
zookeeper 分布式协调服务，是一种分布式主备系统。Primary Order.
-
Broadcast stage
- 消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交过程。
- leader server会为每个follower分配一个单独的队列(基于具有FIFO特性的TCP协议)，事务的有序性质（Int64 ZXID,high32 for epoch/term, low 32 increment id)
- 过半数的follower反馈Ack之后就可以提交事务Proposal
-
Recovery
- Discover
- 【大家公示信息、投票】leader选举: 各个节点广播自己事务proposal的最大ZXID, 同时接受其他节点的广播。若发现更大的ZXID广播（比自己或其他节点），则向广播发出节点ack，否则。 选举出来的leader服务器拥有集群中所有机器最高编号(即ZXID最大)的事务proposal
- Sync
Raft
raft https://www.jianshu.com/p/8e4bbe7e276c
动画演示： http:///raft/
- 角色： Follower，Candidate，Leader
- 过程
- 选主 Leader Election
- 【自荐、拉票阶段】各个节点Vote：Follower timer timeout --> candidate --> self vote —> request other nodes to vote
- 收到过半数的ack的Candidate成为leader, 若同时有多个Candidate相同票数，进行下一轮投票，直到分出高下
- leader 与各个follower 建立heartbeat
- 复制日志 Log Replication
- follower 同步leader的日志，丢弃无效的，接受并提交错过的等。
|
