raft 协议简述

raft 官方博客

背景

分布式存储系统通常要有多个副本来提高整个系统的容错性(fault-tolarence)和可用性。要实现这个目标，就必须要保证多个副本的一致性。

数据一致性

数据一致性是指多个 server 对存储数据的达成一致的状态。典型的一致性算法当多于一半的 server 可用时进行。以包含 5 个 server 的集群举例，如果有两个 server 宕机，那么一致性算法仍然可以正常工作，但是宕机，如果有超过一半的 server 宕机，则一致性算法则无法工作。

注: 一个合理的分布式系统，不应该包含偶数个节点，当系统恰好分裂为一半时， majority-vote 会无法收敛。

每个 server 包含一个状态机和命令日志。状态机是我们用来达成高容错性的组件，与其的交互应该是输出唯一结果，可靠的，即使当少部分 server 发生宕机，仍能正常工作。每个状态机从日志中读取命令。
一致性算法的目的在于使各个 server 上的命令日志达成一致。以 set x 3 这个命令为例，一致性算法必须保证所有的状态机都将 set x 3 作为第 n 个操作，不能出现状态机第 n 个操作不一致的情况。由此达成的结论是，所有的状态机都执行相同的命令序列，产生相同的数据，并达到相同的状态。

Raft 协议

Raft 协议从多副本状态机出发，解决多副本一致性的问题。

多副本状态机

多副本状态机用于解决各种各样的分布式系统的容错问题。例如，大规模分布式系统都有一个 leader,(GFS, HDFS 和 RAMCloud), 通常使用单独的多副本状态机来管理 leader election 和 保存配置信息(以防 leader 宕机)。多副本状态机的是先有 Chubby 和 ZooKeeper.

多副本状态机典型的实现有使用多副本日志。如下图

每个 server 保留一份按照时序记录的命令日志。每份日志保留维护相同的命令序列，状态机从命令日志获取命令序列进行处理，由于状态机的算法是确定的，所以每个 server 上的状态机的应到相同的状态，并有相同的输出。
一致性算法的目的在于保持多个日志副本的一致性。server 上的一致性模块接受从 client 端发来的命令填追加到日志，与其他 server 上的一致性模块进行通信确保即使当部分 server 宕机，其他副本最终保存的是相同时序的命令日志。一旦命令被正确复制，其他 server 将按照顺序执行日志中的命令，并将输出返回到 client 端。最终的结果时，整个集群对外表现为一个单一，高度可靠的状态机。

在实际生产中使用一致性算法时，有如下要求

安全性

在任何复杂的情况都从不返回错误的结果，包括不限于网络延迟，集群隔离，丢包，重写，拓扑重排。

高可用性

一致性组件要保证当集群中的任意大多数 server 正常运行并互相之间能够通讯时保障可用。例如，一个有 5 个 server 的集群可以接受任意 2 个 server 的宕机。这里宕机的 server 可在之后恢复正常后再重新加入集群中。

不依赖计时

一致性算法不依赖计时来保证多个副本的最终一致性。但是错误的时钟和极端的消息延迟会影响，这两个因素也会导致可用性问题。

多数投票

少数 server 执行命令较慢时不影响整个集群的性能。

Raft 一致性算法

Raft 协议首先要在分布式系统中选举出一个 leader 节点, leader 从 client 接受请求并添加到 log 中，并将 log 复制到其它节点，并当 log 可以安全地添加到状态机时告知其余节点。有一个 leader 简化了多副本日志的管理，当一个 leader 正常运行时，数据流是单向从 leader 流向其余的节点。
当 leader 节点宕机或者从集群中断开连接时，其余节点就开始新的 leader 节点选举过程。

Raft 一致性算法在存在 Leader 的背景下，将一致性问题分解为如下三个相对独立的子问题。

• Leader 节点选举
  当已存在的 leader 宕机或不可连时，必须选举出一个新的 leader
• 多副本日志
  leader 从 client 端取得 log，并复制到其余节点并强迫其余节点在 log 与 leader 保持一致
• 安全性
  如果任何一个在 log 索引中的命令已经添加到了状态机中，那么其余任何节点都必须在相同 log 索引与其保持一致

Raft 基本概念

一个 raft cluster 通常包含若干节点。在任意给定的时间，cluster 中的节点只会处于三个状态

leader, follower, candidate

在 cluster 处于正常的状态中时，只会存在一个正常的 leader, 其余所有节点都为 follower. follower 只会被动地从 leader 或者 candidate 接受信息并做相应。leader 为所有 client 请求的入口(如果 client 向一个 follower 发送请求，则会被 follower 重定向至 leader). candidate 仅当 leader 不存在时才出现，用于选举一个新的 leader.

整天摸鱼，我要被开了━((′д｀)爻(′д｀))━!!!!