Raft和Paxos

背景介绍

分布式事务

分布式事务指事务的操作位于不同的分布式系统节点上，需要保证事务的ACID特性。

解决这种分布式一致性问题的办法有：

• 二阶提交协议（Two Phase Commitment Ptotocol）也叫2PC
• 三阶提交协议（Three Phase Commitment Protocol）
• Paxos算法

二阶段提交

简而言之就是将操作结果通知给协调者，再由协调者根据所在参与者的反馈情况决定各参与者是否要提交操作还是中止操作

二阶段的大题思路

• 投票阶段：参与者将操作结果通知协调者
• 提交阶段：收到参与者的通知后，协调者再向参与者发出通知，根据反馈情况决定参与
• 者是否要提交还是回滚

Paxos协议

Paxos可以用来解决分布式环境下设置某一个值的问题，保证在系统中进程间基于消息传递就某个值达成一致

paxos将节点分为三种类型

• 倡议者proposer：提交一个提案，等待大家批准为结案，往往是客户端担任，提案的信息包括提案的编号和提议的value
• 接受者acceptor：负责对提案进行投票，往往服务器担任。若提案获得多数Acceptors的接受，则称该提案被批准（chosen）
• 学习者learner：被告知天结果，只能学习被批准的提案，不参与投票过程，客户端和服务端都可担任。

Raft协议

raft算法是paxos算法的一种简化实现，包括三种角色

• follow：所有节点都以follower的状态开始，如果没有收到leader消息则会变成candidate状态。
• candidate：会向其他节点拉选票，如果得到大部分的票则为leader，整个过程是leader选举
• leader：所有对系统的修改都会经过leader

动画演示

raft算法的执行过程如下所示：

（源自网站http://thesecretlivesofdata.com/raft/）

概要

• Understandable Distributed Consensus

  可理解的分布式共识

• Let’s say we have a single node system

  假设我们有一个单节点系统

• For this example, you can think of our node as a database server that stores a single value.

  在此示例中，您可以将节点视为存储单个值的数据库服务器。

• We also have a client that can send a value to the server.

  我们还有一个可以将值发送到服务器的客户端。

  只有一个节点就可以很容易地达成一致或共识。

  但是，如果我们有多个节点，我们如何达成共识呢？像下面这样

这就是分布式共识的问题。

Raft是一种实现分布式共识的协议。

让我们从更高的层次来了解它的工作原理。

节点可以处于3种状态之一：

• follower（追随者）

• candidate（候选者）

• leader（领导）

所有的节点以follower开始

如果追随者没有收到领导者的消息，那么他们就可以成为候选人。

然后候选人请求其他节点的投票。

其他节点将会回复

候选者如果收到了多数的投票，这个候选者就会变成leader

上面的这个过程叫做领导人选举

对系统的所有更改现在都要经过领导。

日志复制

每个更改都作为一个条目添加到节点的日志中。

此日志项当前未提交，因此不会更新节点的值。

要提交条目，节点首先将其复制到follower节点。。。

然后领导者等待，直到大多数节点都写了该条目。

现在，该条目已提交到引导者节点上，并且节点状态为“ 5”。

领导者然后通知关注者该条目已提交。

然后其他的也变成5了

现在，集群已就系统状态达成共识。

此过程称为日志复制。

leader选举机制

在Raft中，有两个超时设置可控制选举。

• 首先是选举超时。

  选举超时是指追随者成为候选人之前要等待的时间。

  选举超时一般是随机在150ms和300ms之间

选举超时后，关注者将成为候选人并开始新的选举任期。并且给自己投票，然后把投票请求发给其他的节点

如果接收节点在本任期内尚未投票，则它将投票给候选人。。。

在投票之后，节点的选举过期时间要被重置

一旦候选节点获得了多数表，那么他将会bianchengleader

领导者开始向追随者发送附加条目消息。

这些消息以心跳超时指定的间隔发送。然后跟随者响应每个附加条目消息。

此选举任期将持续到追随者停止接收心跳并成为候选人为止。

这个过程就是leader给所有的node发，然后node再给leader发，直到追随者停止接受心跳并且成为候选人为止

如果这个时候A停止了，那么B和C谁的时间先过期，谁就是新的leader

如果两个节点同时成为候选节点，则可能会发生拆分表决。

像下面这种情况，b和d的票数一样

这个时候就会重新开始计时，然后重新投票（肯定不可能每次都有两个同时到期）

一旦有了新的leader，需要将系统所有的更改复制到所有的节点

这个的实现也是用的和心跳检测一样的

下面是具体的实现

外界发来的消息先被存放到leader

然后再下一次心跳检测的时候把消息发给其他的节点（follower）

一旦大多数的follower认同了这个条目，就会提交该条目

然后leader就会把响应发送给客户端

下面再尝试一个例子，将值增加2

流程就是leader把加2的消息发给follower，然后大多数follower都加了2之后，leader这边也会加2，然后相应给client

Raft算法很强，在复杂的集群环境下也同样适用

让我们添加一个分区，将a&B与C、D&E分开。

让我们添加另一个客户端，并尝试更新两个领导者。

一个客户端将尝试将节点B的值设置为“ 3”。

节点B无法复制为多数，因此其日志条目保持未提交状态。

另一个客户端将尝试将节点C的值设置为“ 8”。

这将成功，因为它可以复制到大多数。

现在让我们修复网络分区。

节点A和B都将回滚其未提交的条目并匹配新领导者的日志。

现在，我们的日志在整个集群中是一致的。