Paxos算法

Paxos算法是一种基于消息传递的协商共识的算法，Paxos已经成了分布式系统最重要的理论基础，几乎是共识的代名词

共识，让各个系统节点不受局部网络分区、机器奔溃、执行性能或者其他因素影响，最终表现出整体一致的过程，就是各个节点的协商共识

共识（Consensus）与一致性（Consistency）是有区别的，一致性指的是数据不同副本之间的差异，而共识是指达到一致性方法与过程

Paxos算法的工作流程

Paxos解决的是，一个分布式系统如何就某个值(决议)达成一致的问题，比如如何让三个不同城市的人在纸上画出同样的图形，并不是统一先画圆后画方的问题（就是想强调Paxos只是要来解决一件事，不然理解起来会有问题），下面提到的并发指的是为了来确定画哪个图形提出的决策，可以在Paxos基础上去实现复制状态机

拜占庭问题是表示一类如何保证分布式节点中可能发出恶意错误信息让分布式系统达成共识的问题，Paxos不考虑这种情况

提案节点：称为Proposer，对某个值进行设置操作的节点，设置值这个行为就是提案，值一旦设置成功，就是不会丢失也不可改变的

决策节点：称为Acceptor，是应答提案节点，决定该提案是否可以被投票、是否可以被接受，提案一旦得倒过半数决策节点的接受就意味着提案被批准

记录节点：称为Learner，不参与提案，也不参与决策，只是单纯从其他节点中学习已经达成共识的提案，比如，少数节点从网络中恢复时就会进入这种状态

在使用Paxos算法里，所有节点都是平等的，他们可以承担一种或多种角色，为了确保多数派，决策节点应该被设置为奇数个

Paxos算法包括准备（Prepare）和批准（Accept）两个阶段（Accept多数决策节点应答后才会将数据节点发往记录节点及设置值成功）

• 第一阶段准备就相当于抢占锁的过程，发起提案节点必须向所有决策节点广播一个许可申请，请求会带一个全局唯一的数字n作为提案ID，决策节点收到后，会有两个承诺和一个应答
  承诺不在接受提案ID小于等于n的Prepare请求，承诺不会再接受提案ID小于n的Accept请求，一个应答是在不违背做出的承诺前提下回复已经批准过的提案ID中最大的那个值以及那个提案设定的值，如果没有设定过则返回空，如果违背了承若（收到的提案ID不是最大的）那么就可以不理会Prepare请求（批准过是指已经收到Accept请求并且确认的提案）

• 当提案节点收到多数派决策应答（称为Promise应答）后，可以开始第二阶段的批准过程（Accept）会有两种结果，
  Promise应答返回的值是空，则可以随意修改，构成一个二元组（id，value）发送Accept请求来设置值
  如果提案几点发现响应中已经至少一个节点应答中包含有了值，那它就不能随意取值了，必须无条件从应答中找出ID最大的那个值并接受，构成一个二元组（id，maxAcceptValue）然后发送Accpet请求来设置值

Paxos算法会有活锁问题，两个提案节点交替使用更大的提案ID来使得准备阶段成功，但是批准阶段失败

解决方式就是固定一个Proposer，同时为了高可用，Proposer同时和各个节点保持心跳

情况1.png 情况2.png image.png image.png

MultiPaxos算法

Paxos算法在决定一个值的时候需要执行两个阶段，涉及大量的消息交换，MultiPaxos算法提出可以解决这个问题，MultiPaxos保持一个长期的Leader这样决定一个值只需要执行第二阶段（Accepted多数节点）

Raft协议

Raft协议不像Paxos，Raft有一整套复制状态机的实现方式，Paxos只是提供了一致性共识的协议，需要在其基础上实现复制状态机（只实现了状态机的共识模块）

Raft正常工作流程（消息被多半数节点确认就确认接收）：

image.png

如果Leader挂了可能出现的问题（假设有5个节点，A(L),B,C,D,E)：
1.集群只有一个Leader，如果Leader挂了服务就不可用了,所以需要Leader选举来解决
2.A，B，C3个节点已经确认接收消息，回复client成功，此时Leader挂了，如果D，E被选为Leader后就会丢失数据
3.msg1被A,B,C确认接收，msg2被A,D,E接收，都已经回复client成功，如果此时A挂掉后，无论哪个节点当选Leader都会出现消息丢失

Raft解决方式，Raft将一致性问题分解为了三个子问题：

• leader选举：当已有的leader故障时必须选出一个新的leader
• 日志复制：leader接受来自客户端的命令，记录为日志，并复制给集群中的其他- 服务器，并强制其他节点的日志与leader保持一致
• 安全safety措施：通过一些措施确保系统的安全性，如确保所有状态机按照相同顺序执行相同命令的措施

Leader选举

Raft 使用心跳（heartbeat）触发Leader选举，如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举，通过RequestVote RPC来发起

• 如果超过半数节点来投票就会成为新的Leader，每次发起选举都会在当前在当前Term下加一
• 如果票被平分了就等待一会儿重新发起选举
• 如果别的节点已经是Leader就变成Follower

在投票的时候有个规则，只有发起请求当Leader节点的日志的比当前节点的日志要新的时候才会给这个节点投票(可以解决问题2，保证最新的才能当选)
名词解释：
Leader，每个集群里只有一个Leader，客户端的请求都与Leader进行通信
Follower，复制日志同步，在Leader收到请求后会像Follower进行同步，需要返回结果
Candidate，发起想当Leader的节点，当一段时间没有收到Leader的心跳的时候会变成Candidate，发送选举的请求
Term，任期（第几届），每个Leader都有一个任期，当节点挂掉，新的Leader产生后把任期加一
日志：日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了

image.png

日志复制

Raft 保证如果两个日志序列包含具有相同 索引 和 任期 的日志条目，则直到这个日志条目的所有日志条目都是相同的，这个属性被称为 日志一致性。Raft 通过以下两个属性来保证日志一致性（来解决问题3）
1.如果不同的日志序列中的两个日志条目具有相同的 索引 和 任期，那么这两个日志条目包含相同的命令（通过不可变的规则来保证）
2.如果不同的日志序列中的两个日志条目具有相同的 索引 和 任期，那么这两个日志条目 之前 的所有日志条目均一致

当 Leader 在发送 AppendEntries 请求时，会将本地最新日志的前一个日志的索引和任期信息添加到请求中，如果 Follower 在其本地日志中没有匹配上前一个日志，则拒绝本次请求，这就是 AppendEntries 的 日志一致性校验。这个日志一致性校验就保证了第二条属性

最坏的情况下可能出现下图错误：

image.png

（f是由于在任期1的leader挂掉后，当选为leader，收到2和3的请求，还没同步给其他节点就由于网络原因被其他节点单选了）

Raft 算法在处理日志不一致的时候，采取 日志截断 的方式，将 Leader 的日志强制覆盖本地的日志。为了将 Follower 的日志状态与自己同步，Leader 需要找到自己的日志和 Follower 日志的公共祖先，就好比两个分叉的链表，需要找到分叉的那个 LogEntry然后进行日志同步

（可能出现，当client的请求只同步到一个节点，此时Leader挂了，这个时候就可能出现两种情况，同步到数据的那个节点成为了Leader，把请求同步到其他节点及这次命令成功了，还有一种可能就是其他节点当选Leader，把这个请求给覆盖了，都是可以接受的，需要在client保持幂等）

最后

Raft的Leader选举Leader是一个分布式共识的问题吗？
只需要Leader自己知道自己是Leader就行
Kafka保证数据不丢失？
Kafka当设置ack为all时可以保证不丢失，因为所有ISR都以将数据都复制，并且通过ZK来进行Leader选举