Raft总结
Raft个人总结
Raft是一种用于管理复制日志的共识算法。这里面有两个关键：复制日志（Replicated log）和共识算法（Consensus algorithm）。
复制日志可以理解为，任何被确定要执行的操作都要记录在日志当中，同时这些日志要不断地复制到集群中的各个节点，尽可能确保每个节点都有相同的日志。
共识算法主要用于分布式系统，用于解决数据一致性的问题，同时在面临一些会导致节点失效的情况下，仍能提供有效的支持。在Raft算法中也就是要让集群中的节点有相同的日志，保证日志数据的一致。
在阅读论文的过程中，我们可以了解到，Raft是为了解决Paxos一系列的问题近而提出的一种算法。Paxos的结构非常复杂，实现起来也比较困难，本人暂时还没有开始看Paxos，在此立一个Flag，看完做个详解。
Raft有三个主要的特点：
- 强领导人（Strong leader）：例如日志条目只能从领导人流向其他服务器。
- 领导人选举（Leader selection）：领导人失效的时候，可以进行选举，选举机制依靠随机化时间片实现。
- 成员关系变更（Membership Change）：这一部分在于处理变更集群之间的关系，例如两个集群的合并时，两个集群领导人如何选举，旧的配置到新的配置如何转换。
复制状态机
共识算法通常用于复制状态机上，复制状态机可以简单的理解为复制功能，也就是说节点是具有复制功能的，将内容保存到自身的存储单元。
单一集群领导人的大规模系统，例如GFS、HDFS和RAMCloud。通常用单独的复制状态机来管理领导人选举和存储配置信息并且在领导人宕机的情况下也要存活下来。复置状态机的例子一般有：Chubby和Zookeeper。
复制状态机通常是基于复制日志实现的。每个服务器存储一些列指令的日志，并且按照日志的顺序进行执行。每个日志都按照相同的顺序包含相同的指令，所以每一个服务其都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。
一致性算法
一致性算法保证复制日志的一致性：（日志即要执行的指令序列）
服务器上的一致性模块接受客户端发送的指令，然后添加到自己的日志当中，他和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志都以相同的顺序包含相同的请求。一旦指令被正确复制，每一个服务器的状态机按照日志顺序处理，然后输出结果返回给客户端。
一致性算法包含的特性
安全性保证：在非拜占庭错误的情况下，包括网络延迟、分区、丢包、重复和乱序等错误都可以正确保证。
可用性：集群中大部分机器可以运行，并且可以相互通信、和客户端通信。
不依赖时序保证一致性
一条指令可以尽可能快的在集群中的大多数节点响应一轮远程过程调用时完成。
Raft一致性算法
Raft通过选举一个杰出的领导人，然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目，把日志条目复制到其他服务器上，并告诉其他服务器什么时候可以安全地将日志条目应用到他们的状态机当中。
领导人方式，Raft将一致性问题分解为三个独立的子问题：
- 领导人选举：现存领导人故障时，新领导人将被选举出来。
- 日志复制：领导人必须从客户端接收日志条目，然后复制到集群的其他节点，并强制要求其他节点的日志和自己保持一致。
- 安全性：
- 选举安全：一届任期内只有一个领导人
- 领导人唯一增加：领导人不会重新或者删除日志，只会增加新的日志
- 日志匹配：如果两个日志包含具有相同索引和项的条目，那么在给定索引的所有条目中，日志是相同的
- 领导人完整性：如果在给定的项中提交了一个日志条目，那么该条目将出现在所有更高编号项的首项的日志中
- 状态机安全：如果服务器已经将给定索引上的日志条目应用到它的状态机，那么其他服务器将不会为相同的索引应用不同的日志条目，不同服务器上的状态机执行指令的顺序相同。
Raft基础
一个Raft集群包含若干服务器节点，五个服务器节点是典型例子。允许整个系统容忍两个节点失效。任何时刻每个服务器节点都处于三个状态之一：领导人、跟随者和候选人。通常系统中只有一个领导人，其他节点都是跟随者。领导人处理客户端请求，候选人是在选取新领导人时使用的。
Raft把时间分割成任意长度的任期，任期用连续的整数标记。每段任期从一次选举开始。选票瓜分的时候会以没有领导人结束，新的任期很快会重新开始。
Raft算法中服务器节点之间通信使用远程过程调用RPCs，基本的一致性算法只需要两种类型的RPCs。请求投票RPCs由候选人在选举期间发起，然后添加条目（AppendEntries）RPCs由领导人发起，用来复制日志和提供心跳机制。在服务器之间传输快照增加了第三种RPC。
领导人选举：
使用心跳机制触发领导人选举。服务器启动时都是跟随者身份，领导人周期性的向所有跟随者发送心跳包（不包含日志项内容的附加条目（AppendEntries）RPCs）来维持权威。跟随者在一段时间内没有收到消息，则发起选举选出新的领导人。
选举过程：
跟随者增加当前任期号并转换到候选人状态，然后并行的向集群中的其他服务器发送请求投票的RPCs给自己投票。
每个服务器会对一个任期号投出一张选票，按照先来先服务原则。一旦候选人赢得选举，就立刻成为领导人。然后向其他服务器发送心跳消息来建立自己的权威并组织发起新的选举。
候选等待的过程中，候选人接收到其他服务器声明他是领导人的心跳包，如果任期号比当前大的话，则承认领导人合法候选人直接变为跟随者，如果任期号比当前的小则拒绝，并保持候选人装填。
Raft通过随机选举超时时间的方法确保很少发生选票瓜分。选举超时时间从一个固定的区间（150-300ms）随机选择。大多数情况下只有一个服务器会选举超时。每个候选人在开始选举的时候重置选举超时时间。（是否存在更改计时器的漏洞？）
日志复制：
客户端的每一个请求都包含一条被复制状态机执行的指令。这条指令会被加到日志当中。领导人会并行的发送附加条目rpcs给其他服务器，让他们复制这条日志条目，当这条日志被安全地复制，领导人会应用这条日志条目到状态机中，并返回结果给客户端。
领导人来决定什么时候把日志条目应用到状态机中是安全的，这种日志条目被称为已提交。创建的日志条目复制到大多数的服务器上时，日志条目就会被提交。
要使跟随者的日志跟自己一致，领导人必须找到最后两者达成一致的地方，然后删除跟随者那个点之后的所有日志条目，并发送自己在那个点之后的日志给跟随者。所有这些操作都在进行附加日志RPCs的一致性检查时完成。
日志机制的两条性质：
1）如果两个entries在不同的日志中有相同的索引号和任期号，那么它们存储相同的命令。
2）如果两个entries在不同的日志中有相同的索引号和任期号，那么日志的所有之前的部分是相同的。
跟随者日志条目可能存在的情况：某任期的未提交条目（领导人在日志提交之前宕机），一些未被包含的现任领导人的日志。
安全性：
（？不能保证所有的状态机执行指令相同顺序的相同指令）
不同的跟随者不能把保证按照相同的顺序执行相同的指令。
RPC中包含了候选人的日志信息，投票人会拒绝那些日志没有自己新的投票请求。（比较任期号和长度判断谁更新）
应用到服务器状态机中的指令对应的索引，必须与领导人对应位置的索引相同，且被提交。
时间和可用性：
广播时间 <<选举超时时间<<平均故障间隔时间
Raft的RPCs需要接收方将信息持久化的保存到稳定的存储当中去，所以广播时间时0.5ms到20ms，取决于存储的技术。选举时间需要在10ms到500ms之间。大多数服务器的平均故障时间在几个月甚至更长时间，很容易满足需求。
集群成员变化：
集群自动化配置纳入到raft算法当中。（这一部分还需要再看一下）
日志压缩：
快照，Chubby和Zookeeper。
增量压缩，日志清理或者日志结构合并树，这些方法每次只对一小部分数据进行操作，这样就分散了压缩的负载压力。
LSM tree。
快照只包括已提交的日志。快照包含少量的元数据：最后被包含索引和最后被包含任期。还包含最后一次的配置。一旦服务器完成了一次快照，就可以删除最后索引位置之前的所有日志和快照了。
服务器一般独立创建快照，但领导人必须偶尔的发送快照给落后的跟随者（安装快照的新RPC）。