Raft算法原理，看这篇就够了
Raft算法原理，看这篇就够了
Raft算法是一种用于管理和维护分布式系统一致性的协议，它通过在节点间复制数据来保证分布式系统中的一致性。本文将详细介绍Raft算法的基本概念、选主过程、任期机制以及消息复制机制。
什么是Raft？
Raft是一种用于管理和维护分布式系统一致性的协议，它是一种共识算法，在实现高可用性和数据的持久性。Raft通过在节点间复制数据来保证分布式系统中的一致性，即使在节点故障的情况下也能保证数据不会丢失。
在分布式系统中，为了消除单点提高系统可用性，通常会使用副本来进行容错，但这会带来另一个问题，即如何保证多个副本之间的一致性？共识算法（Consensus Algorithm）就是做这个事情的，它允许多个分布式节点就某个值或一系列值达成一致性协议。即使在一些节点发生故障，网络分区或其他问题的情况下，共识算法也能保证系统的一致性和数据的可靠性。
常见的共识算法有：Paxos，Raft，Zab等
- Paxos：一种经典的共识算法，用于解决分布式系统中的一致性问题
- Raft：一种较新的共识算法，Paxos不易实现，raft是对Paxos算法的简化和改进，在易于理解现
- Zab：Zookeeper使用的共识算法，基于Paxos算法。大部分和Raft相同，主要区别是对于Leader的任期，Raft叫做term，Zab叫做epoch，状态复制的过程中，raft的心跳从Leader向Follower发送，而ZAB则相反
- Gossip:Gossip算法每个节点都是对等的，即没有角色之分。Gossip算法中的每个节点都会将数据改动告诉其他节点（类似传八卦）
Raft基本概念
Raft 使用Quorum 机制来实现共识和容错，我们将对Raft集群的操作必须得到大多数（>N/2）节点的同意才能提交。
节点指的是分布式系统中的一个独立成员
当我们向Raft集群发起一系列读写操作时，集群内部究竟发生了什么呢？我们先来简单了解一下。Raft集群必须存在一个主节点（Leader），客户端向集群发起的所有操作都必须经由主节点处理。所以Raft核心算法中的第一部分就是选主（Leader election）。没有主节点集群就无法工作，先选出一个主节点，再考虑其它事情。
主节点会负责接收客户端发过来的操作请求，将操作包装为日志同步给其它节点，在保证大部分节点都同步了本次操作后，就可以安全地给客户端回应响应了。这一部分工作在Raft核心算法中叫日志复制(Log replication)。
因为主节点的责任非常大，所以只有符合条件的节点才可以当选主节点。为了保证集群对外展现的一致性，主节点在处理操作日志时，也一定要谨慎，这部分在Raft核心算法中叫安全性（Safety）。
Raft算法将一致性问题分解为三个子问题：Leader选举，日志复制和安全性。下面我们详细介绍下Raft的选主过程。
选主(Leader Election)
选主（Leader election）就是在集群中抉择出一个主节点来负责一些特定的工作。在执行了选主过程后，集群中每个节点都会识别出一个特定的，唯一的节点作为leader。
节点角色
在Raft算法中，每个节点都处于以下三种角色之一
- Leader（领导者）：负责处理所有客户请求，并将这些请求作为日志项复制到所有Follower。 Leader定期向所有Follower发送心跳消息，以维持其领导者地位，防止Follower 进入选举过程。
- Follower（跟随者）：接收来自Leader的日志条目，并在本地应用这些条目。跟随者不直接处理客户请求。
- Candidate（候选者）：当跟随者在一段时间内没有收到来自Leader的心跳消息时，它会变得不确定Leader是否仍然可用。在这种情况下，跟随者会转变角色成为Candidate，并开始尝试通过投票过程成为新的Leader。
在正常情况下，集群中只有一个Leader，剩下的节点都是follower，下图展示了这些状态和它们之间的转换关系
可以看出所有节点在启动时，都是follow状态，在一段时间内如果没有收到来自leader的心跳，从
follower切换到candidate，发起选举。如果收到多数派（majority）的投票（含自己的一票）则切换到leader状态.Leader一般会一直工作直到它发生异常为止
任期(term)
Raft将时间划分成任意长度的任期（term）。每一段任期从一次选举开始，在这个时候会有一个或者多个
candidate尝试去成为leader。在成功完成一次leaderelection之后，一个leader就会一直节管理集群直
到任期结束。在某些情况下，一次选举无法选出leader，这个时候这个任期会以没有leader而结束（如下图t3）。同时一个新的任期（包含一次新的选举）会很快重新开始
Term更像是一个逻辑时钟（logicclock）的作用，有了它，就可以发现哪些节点的状态已经过期。每一个节点都保存一个currentterm，在通信时带上这个term的值
每一个节点都存储着一个当前任期号（currenttermnumber）。该任期号会随着时间单调递增。节点之间通信的时候会交换当前任期号，如果一个节点的当前任期号比其他节点小，那么它就将自己的任期号更新为较大的那个值。如果一个candidate或者leader发现自己的任期号过期了，它就会立刻回到follower状态。如果一个节点接收了一个带着过期的任期号的请求，那么它会拒绝这次请求
Raft算法中服务器节点之间采用RPC进行通信，主要有两类RPC请求
- RequestVoteRPCS：请求投票，由candidate在选举过程中发出
- AppendEntriesRPCS: 追加条目，由leader发出，用来做日志复制和提供心跳机制
选举过程
Raft采用一种心跳机制来触发leader选举，当服务器启动的时候，都是follow状态。如果follower在electiontimeout内没有收到来自leader的心跳（可能没有选出leader，也可能leader挂了，或者leader与follower之间网络故障），则会主动发起选举
步骤如下：
- 率先超时的节点，自增当前任期号然后切换为candidate状态，并投自己一票
- 以并行的方式发送一个RequestVoteRPCS给集群中的其他服务器节点（企图得到它们的投票)
- 等待其他节点的回复
在这个过程中，可能出现三种结果
- 赢得选举，成为Leader（包括自己的一票）
- 其他节点赢得了选举，它自行切换到follower
- 一段时间内没有收到majority投票，保持candidate状态，重新发出选举
投票要求
- 每一个服务器节点会按照先来先服务原则（first-come-first-served）只投给一个candidate.
- 候选人知道的信息不能比自己的少
接下来对这三种情况进行说明
第一种情况：赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举
第二种情况：比如有三个节点ABCAB同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，这时候A就胜出了.A胜出之后，会给3C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是把自己转换成follower.
第三种情况：没有任何节点获得majority投票.比如所有的follower同时变成candidate，然后它们都将
票投给自己，那这样就没有candidate能得到超过半数的投票了.当这种情况发生的时候，每个
candidate都会进行一次超时响应，然后通过自增任期号来开启一轮新的选举，并启动另一轮的
RequestVoteRPCS.如果没有额外的措施，这种无结果的投票可能会无限重复下去
为了解决上述问题，Raft采用随机选举超时时间（randomizedelectiontimeouts）来确保很少产生无结果的投票，并且就算发生了也能很快地解决。为了防止选票一开始就被瓜分，选举超时时间是从一个固定的区间（比如，150-300ms）中随机选择。这样可以把服务器分散开来以确保在大多数情况下会只有一个服务器率先结束超时，那么这个时候，它就可以赢得选举并在其他服务器结束超时之前发送心跳。
通过动画我们也能更直观的感受到：https://raft.github.io/
Raft协议下的消息复制
每个仲裁队列都有多个副本，它包含一个主和多个从副本.replicationfactor为5的仲裁队列将会有1个主副本和4个从副本，每个副本都在不同的节点上
客户端（生产者和消费者）只会与主副本进行交互，主副本再将这些命令复制到从副本.当主副本所在的节点下线，其中一个从副本会被选举成为主副本，继续提供服务
消息复制和主副本选举的操作，需要超过半数的副本同意，当生产者发送一条消息，需要超过半数的队列副本都将消息写入磁盘以后才会向生产者进行确认，这意味着少部分比较慢的副本不会影响整个队列的性能