分布式一致性协议算法

分布式协议算法

Paxos

Basic Paxos

角色

提议者

提议一个值用于投票

接受者

对每个提议的值进行投票，并且储存接受的值

学习者

类似于Master-Slave模型中salve，被动学习。容灾备份作用

提案

准备请求

提交一个用于提案编号用于投票

接收请求

接受用于存储的值

Multi-Paxos

Raft

领导者Leader

一个集群只有一个领导者. 负责发送心跳、管理日志复制、处理写请求

跟随者Follower

候选人Candidate

节点间如何通讯？

请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票

日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息

什么是任期？

每个任期由单调递增的数字（任期编号）标识，比如节点 A 的任期编号是 1。任期编号是随着选举的举行而变化的

1.跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。

2.如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票 RPC 消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编号更新为 1。

选举有哪些规则

1.领导者周期性地向所有跟随者发送心跳消息.确保他们不会选举

2.如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举

3.在一次选举中，赢得大多数选票的候选人，将晋升为领导者

4.在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举

5.在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3，先收到了 1 个包含任期编号为 4 的投票请求（来自节点 A），然后又收到了 1 个包含任期编号为 4 的投票请求（来自节点 B）。那么节点 C 将会把唯一一张选票投给节点 A，当再收到节点 B 的投票请求 RPC 消息时，对于编号为 4 的任期，已没有选票可投了

随机超时时间:Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况。

动画演示

http://thesecretlivesofdata.com/raft/

分支主题

BASE理论

Basically Available基本可用

流量削峰

延迟响应

体验降级

过载保护

Eventtually consistent最终一致性

经过一段时间的同步后（MQ.定时任务补偿等机制）使数据达到最终一致性

读时修复：在读取数据时检测数据是否一致，不一致则修复

写时修复：在写入数据时检测数据是否一致，不一致则修复

异步修复：定时任务定时去检测数据是否一致，不一致则修复

Soft state软状态

软状态是实现服务可用性的一种过渡状态，不同节点数据短暂的不一致。就是一种过渡状态/中间状态

ACID理论

原子性（Atomicity）原子性是指事务是一个不可分割的工作单位，事务中的操作要么都发生，要么都不发生。

一致性（Consistency）事务前后数据的完整性必须保持一致。

隔离性（Isolation）事务的隔离性是多个用户并发访问数据库时，数据库为每一个用户开启的事务，不能被其他事务的操作数据所干扰，多个并发事务之间要相互隔离

持久性（Durability） 持久性是指一个事务一旦被提交，它对数据库中数据的改变就是永久性的，接下来即使数据库发生故障也不应该对其有任何影响

二阶段协议提交 

提交请求阶段(投票阶段) 需要预留资源

提交执行阶段(完成阶段) 返回结果

MySQL中innodb两阶段提交的应用案例 更新语句将更新值保存到内中之后 prepare阶段 写入redolog 写入binlog commit阶段提交事务

三阶段提交协议，虽然针对二阶段提交协议的“协调者故障，参与者长期锁定资源”的痛点，通过引入了询问阶段和超时机制，来减少资源被长时间锁定的情况，不过这会导致集群各节点在正常运行的情况下，使用更多的消息进行协商，增加系统负载和响应延迟。也正是因为这些问题，三阶段提交协议很少被使用

TCC

Try预留、Confirm确认、Cancel取消

业务层面的协议，需要在业务中去实现一个操作对应的 确认操作和取消操作。业务入侵性太强

子主题

CAP理论

我们只能在一致性、可用性、分区容错性中选择两个，无法三个都选择。而分布式系统中必须要有分区容错性，也就是说我们只能选择AP/或者CP

Consistency一致性:在分布式系统中每次读取访问任意节点得到的数据都是一致的(读取到最新值或者读取失败)

Partition Tolerance 分区容错性：在分布式系统中，因为某个节点网络故障或者机器故障.整个集群还是可以正常对外使用的