Raft算法的原理与实现

前言

在摘要当中我们提到，Raft算法多用于多副本状态机的日志管理。在此之前，我们需要明白 日志管理 意味着什么。

日志管理

考虑一个类似于数据库的存储服务器。

• 服务器存储了若干键值对，可以进行Put, Get, Delete等操作。
• 客户端可以向服务器发送Put, Get, Delete等操作，服务器接收请求之后进行操作，操作完成后把结果返回给客户端。

而 日志 就顺序地记录了这个服务器接收到的所有的操作。可以参考MySQL里面的redo log和undo log，有了日志之后，KV存储服务器可以通过日志返回、或者恢复到先前的任何一个状态。也正因此，日志管理是KV存储器的核心。

单个节点Server的情况，可以参考下图：

多副本状态机

我们通过日志管理保证了存储服务器的一致性，但是从整个服务过程来看，我们只使用了单个服务器节点。这意味着一旦单个节点出现问题（如机械故障、网络不通）等原因而无法动作，整个服务将被迫停止。

基于分布式的思想，我们很自然地提出了一个问题：能不能用多台服务器构成一个集群，即使服务器集群当中的其中一些节点崩了，服务端依然可以为客户端提供服务？

答案是可以的，我们建构一个服务器集群，然后保证每个服务器之间都存储了相同的数据即可（这是通过日志管理实现的）。也就是说，集群当中有多个相同备份/副本服务器（replica），保证服务的正常运行，这就是多副本状态机。

尽管多副本状态机与MapReduce都运用了分布式的思想，但是不同的是，MapReduce是计算框架，使用分布式提高效率。而多副本状态机则更关注于分布式的另一个方面：容错。

新的问题是：客户端只向单个服务器节点发送命令(Command)，我们如何保证其他的副本也能有与主服务器相同的日志，进而有相同的数据？

在论文当中，主服务器称为Leader, 其余的副本服务器称为Follower。

Raft算法解决了这个问题，多副本状态机的日志管理。

概述 - Raft算法干了什么？

Leader选举

日志管理

持久化与日志快照

三个状态：

1. follower
2. candidate
3. leader

一些主动指令：

• 成为cand : candidate发送投票请求
• 计时到达 : leader发送心跳
• 收到新log：leader同步log
• 定时：leader更新commitIdx
• commit提交：all states 应用状态
• 状态转换：
  • 超时：follower -> candidate
  • 胜利：candidate -> leader
  • 很多条件：candidate -> follower
  • 很多条件：leader -> follower