Raft协议详解

共识算法（Consensus Algorithm）就是用来做这个事情的，它保证即使在小部分（≤ (N-1)/2）节点故障的情况下，系统仍然能正常对外提供服务。共识算法通常基于状态复制机（Replicated State Machine）模型，也就是所有节点从同一个 state 出发，经过同样的操作 log，最终达到一致的 state。

etcd分布式存储

consul服务中心

TiKV 同样在底层使用了 Raft 算法

TiKV 同样在底层使用了 Raft 算法。虽然都自称是“分布式 kv 存储”，但 TiKV 的使用场景与 etcd 存在区别。其目标是支持 100TB+ 的数据，类似 etcd 的单 Raft 集群肯定无法支撑这个数据量。因此 TiKV 底层使用 Multi Raft，将数据划分为多个 region，每个 region 其实还是一个标准的 Raft 集群，对每个分区的数据实现了多副本高可用。

使用方

Raft 使用 Quorum 机制来实现共识和容错，我们将对 Raft 集群的操作称为提案，每当发起一个提案，必须得到大多数（> N/2）节点的同意才能提交。

所以 Raft 核心算法中的第一部分就是选主（Leader election）——没有主节点集群就无法工作

日志复制

主节点职责

Raft 集群必须存在一个主节点（leader）

基本概念

Leader: 所有请求的处理者，接收客户端发起的操作请求，写入本地日志后同步至集群其它节点

Follower: 请求的被动更新者，从 leader 接收更新请求，写入本地文件。如果客户端的操作请求发送给了 follower，会首先由 follower 重定向给 leader

Candidate: 如果 follower 在一定时间内没有收到 leader 的心跳，则判断 leader 可能已经故障，此时启动 leader election 过程，本节点切换为 candidate 直到选主结束。

角色

每开始一次新的选举，称为一个任期（term），每个 term 都有一个严格递增的整数与之关联。

每当 candidate 触发 leader election 时都会增加 term，如果一个 candidate 赢得选举，他将在本 term 中担任 leader 的角色。但并不是每个 term 都一定对应一个 leader，有时候某个 term 内会由于选举超时导致选不出 leader，这时 candicate 会递增 term 号并开始新一轮选举。

RequestVote RPCs: 用于 candidate 拉票选举。AppendEntries RPCs: 用于 leader 向其它节点复制日志以及同步心跳。

节点间通过RPC来通信

过程

选主(leader election)

负责接收客户端发过来的操作请求，将操作包装为日志同步给其它节点，在保证大部分节点都同步了本次操作后，就可以安全地给客户端回应响应了

Leader 为客户端提供服务，客户端的每个请求都包含一条即将被状态复制机执行的指令。

Leader 把该指令作为一条新的日志附加到自身的日志集合，然后向其它节点发起附加条目请求（AppendEntries RPC），来要求它们将这条日志附加到各自本地的日志集合。

当这条日志已经确保被安全的复制，即大多数（N/2+1）节点都已经复制后，leader 会将该日志 apply 到它本地的状态机中，然后把操作成功的结果返回给客户端。

流程

每条日志除了存储状态机的操作指令外，还会拥有一个唯一的整数索引值（log index）来表明它在日志集合中的位置。此外，每条日志还会存储一个 term 号（日志条目方块最上方的数字，相同颜色 term 号相同），该 term 表示 leader 收到这条指令时的当前任期，term 相同的 log 是由同一个 leader 在其任期内发送的。

因为主节点的责任是如此之大，所以节点们在选主的时候一定要谨慎，只有符合条件的节点才可以当选主节点。此外主节点在处理操作日志的时候也一定要谨慎，为了保证集群对外展现的一致性，不可以覆盖或删除前任主节点已经处理成功的操作日志。

对选举的限制

Leader 只允许 commit 包含当前 term 的日志

对提交的限制

安全性

谨慎处理

三大核心

为什么 etcd 不适合大数据量的存储？

为什么集群节点数不是越多越好？

为什么集群适合部署奇数个节点？

Raft 将操作包装成为了日志，集群每个节点都维护了一个不断增长的日志序列，状态机只有通过重放日志序列来得到。但由于这个日志序列可能会随着时间流逝不断增长，因此我们必须有一些办法来避免无休止的磁盘占用和过久的日志重放。

为什么会产生这个问题？

快照（Snapshot）是一种常用的、简单的日志压缩方式，ZooKeeper、Chubby 等系统都在用。

简单来说，就是将某一时刻系统的状态 dump 下来并落地存储，这样该时刻之前的所有日志就都可以丢弃了。

在 Raft 中我们只能为 committed 日志做 snapshot

1、日志的元数据：最后一条被该快照 apply 的日志 term 及 index2、状态机：前边全部日志 apply 后最终得到的状态机

快照包含

解决方案：日志压缩

Raft如何解决日志无限增长的问题？

一个 Raft 集群不太可能永远是固定几个节点，总有扩缩容的需求，或是节点宕机需要替换的时候。直接更换集群成员可能会导致严重的脑裂问题。Raft 给出了一种安全变更集群成员的方式。

Raft 使用一种两阶段方法平滑切换集群成员配置来避免脑裂。

解决方案：集群成员变更（Cluster membership change）

Raft如何解决成员变更的问题？

Raft 巧妙的使用了一个随机化的定时器，让每个节点的“超时时间”在一定范围内随机生成

“选举超时时间”该如何制定？如果所有节点在同一时刻启动，经过同样的超时时间后同时发起选举，整个集群会变得低效不堪，极端情况下甚至会一直选不出一个主节点。

Raft 强制要求 follower 必须复制 leader 的日志集合来解决不一致问题。leader 从来不会覆盖或者删除自己的日志，而是强制 follower 与它保持一致。

follower 节点上任何与 leader 不一致的日志，都会被 leader 节点上的日志所覆盖。

要使得 follower 的日志集合跟自己保持完全一致，leader 必须先找到二者间最后一次达成一致的地方。因为一旦这条日志达成一致，在这之前的日志一定也都一致

Leader 针对每个 follower 都维护一个 next index，表示下一条需要发送给该follower 的日志索引。当一个 leader 刚刚上任时，它初始化所有 next index 值为自己最后一条日志的 index+1。但凡某个 follower 的日志跟 leader 不一致，那么下次 AppendEntries RPC 的一致性检查就会失败。在被 follower 拒绝这次 Append Entries RPC 后，leader 会减少 next index 的值并进行重试。

针对每个 follower，一旦确定了 next index 的值，leader 便开始从该 index 同步日志，follower 会删除掉现存的不一致的日志，保留 leader 最新同步过来的。

Raft如何处理日志不至的情况？

问题

第一步：所有节点都是follower

第二步：当follower节点超时没有收到leader的心跳，切换candidate身份并对term+1，并向其他集群节点发送发送“请给自己投票”的消息（RequestVote RPC）

当candicate从整个集群的大多数（N/2+1）节点获得了针对同一 term 的选票时，它就赢得了这次选举，立刻将自己的身份转变为 leader 并开始向其它节点发送心跳来维持自己的权威。

第三步：如果上一步candidate选举成功，则切换身份leader，并发送心跳维持权威

Candidate 在等待投票回复的时候，可能会突然收到其它自称是 leader 的节点发送的心跳包，如果这个心跳包里携带的 term 不小于 candidate 当前的 term，那么 candidate 会承认这个 leader，并将身份切回 follower。

如果心跳包中的 term 比自己小，candidate 会拒绝这次请求并保持选举状态。

第三步：如果上一步candidate选举失败

此时 candidate 需要增加自己的 term，然后发起新一轮选举。

如果有多个 follower 同时成为 candidate，选票是可能被瓜分的，如果没有任何一个 candidate 能得到大多数节点的支持，那么每一个 candidate 都会超时

第三步：如果上一步candidate选举超时

想象一个场景：当 leader 节点发生了宕机或网络断连，此时其它 follower 会收不到 leader 心跳，首个触发超时的节点会变为 candidate 并开始拉票（由于随机化各个 follower 超时时间不同），由于该 candidate 的 term 大于原 leader 的 term，因此所有 follower 都会投票给它，这名 candidate 会变为新的 leader。一段时间后原 leader 恢复了，收到了来自新leader 的心跳包，发现心跳中的 term 大于自己的 term，此时该节点会立刻切换为 follower 并跟随的新 leader。

leader只可能转换为follower

leader状态转换

Raft协议