Raft 论文读书笔记
Raft
In Search of an Understandable Consensus Algorithm (Extended Version)
1. Introduction
一致性算法。一个机器集合如何对外提供一致性，并具有容错性(容忍某些节点失效).
Raft把一致性分为三个关键元素：leader election, log replication, safety
Raft 关键的特性：
- Strong leader
- Leader election
- Membership changes
2. Replicated state machines
在 replicated state machines 的场景下讨论一致性算法。在server集合上的状态机，在一样的状态上进行相同的计算 ，并且在少数server挂掉后，仍能对外提供服务。用于在分布式系统中提供容错性。
replicated state machines 一般使用 replicated log来实现。每个server存储状态机按照顺序执行的一系列命令的日志。每个日志都按照相同的顺序存储命令。一致性算法的职责就是保持 replicated log 的一致性。
典型的一致性算法具有以下属性
- 在所有非拜占庭(non-Byzantine)条件下都是保证安全的，包括：网络延迟，分区，丢包，重复，乱序
- 在大多数server在运作，并可以相互通讯，与客户端通讯的情况下，能够对外提供服务。
- 不依赖于时间来保证logs的一致性：因为不一致的时钟，计算情况下的网络延迟会导致
- 一般情况下，一条命了在集群中大多数响应后即完成。即少数慢的服务器不会影响整体系统性能。
3. What's wrong with Paxos?
- Paxos 难以理解
- 没有为实现提供好的基础
4. Designing for understandability
5. The Raft consensus algorithm
一致性算法的关键属性(Figure 3)：
- Election safety：(5.2节)在一个term期间最多只会选出一个leader
- Leader Append-Only：(5.3节)leader只会新增(append)entries，而永远不会覆盖或删除entries。
- Log Matching：(5.3节)如果两个logs包含一个具有相同index及term的entry，那么这两者，在该index项及之前的所有entries都是一致的
- Leader Completeness：(5.4节)if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-number terms？
- State Machine Safety：(5.4.3节)如果一个server 在某一index上对状态机applied 了 log entry，不会有其它server 用同样的index，apply一个不一致的log entry
Raft的做法是首先选出leader，全权负责管理replicated log。包括接收客户端的log entries，复制log entries至其他server，告知他们何时可以 apply log entries to their state machines. 在 leader 挂掉或者与其他server失去链接的情况下，选举出新的leader。
Raft把一致性问题拆分为三个子问题：
- Leader election：在当前 leader 挂掉后选出一个新的 leader
- Log replication：leader 从客户端接收 log entries 并在集群内进行复制，让其他 logs 与leader的log保持一致
- Safety：关键需要保证 Figure 3 中的 State Machine Safety. 5.4节描述 Raft 如何保证这一点。为了保证这一点，在 5.2 节选举的方式中也会额外添加了一些限制。
5.1 Raft basics
Figure 4. Server states
server 有三个状态：leader，follower，candidate。一般情况下有且仅有一个leader，其它server都是follower。
Leader 负责处理对外所有客户端的请求(如果client向follwer发起请求，follower把client重定向给leader)。
Follower被动地接收leader及candidates的请求。
Candidate用于选举出新的leader
Raft把时间划分为任意长度的term。每个term以选举开始，如果有candidate赢得选举，其在term内当选leader；在某些情况下发生了split vote，该term以没有leader结束，并在较短时间内发起新的选举。term在Raft中扮演着逻辑始终的角色(logical clock)。
基本的一致性算法，Raft server 之间只需要两类型的RPC调用。而在第7节为在server间转移snapshots添加了第三种RPC。
- RequestVote：在选举期间由candidates发起
- AppendEntries：由leader发起的复制log entries以及heartbeat。
