共识算法分分类
- 拜占庭问题解决方案：PBFT POW DBFT
- 非拜占庭问题解决方案：RAFT PAXOS
Raft
Raft 是一套通过选举主节点来实现分布式系统一致性的算法，简易版Paxos
结构：
- follower（跟随者）：最初大家都是follower，任务就是听leader的安排，和投票。如果timeout使劲内，没有收到leader消息，进入candidate状态。
- candidate（候选人）：竞选leader，向其余节点“拉票“
- leader（领导）：客户端的更新，最先到达Leader，由Leader分发。
主要解决了一致性的问题。Raft主要是选出一个leader来简化副本的管理；具体要求是日志（log ）只允许从Leader流向follower
理解成三个独立的问题：
领导人选举（Leade election）：统一管理数据的人，一旦宕机，重新选举
日志复制（Log replication）：领导人从客户端接收到日志，随后复制到其他服务器
安全性（Safety）：得益于状态机安全原则，一旦状态机在指定索引
算法的整个流程如下：
任期（Term）
时间被分为一个个的任期（term），每一个任期的开始都是领导人选举。在成功选举之后，一个领导人会在任期内管理整个集群。如果选举失败，该任期就会因为没有领带人而结束。这个转变会在不同的时间的不同服务器上观察到。4
很多情况会让导致选举失败，此时会放弃this term 的选举，直接开始下一届。如：票数不够；同时刻竞选者
服务器之间会相互通信，如果发现自己任期过时，会放弃一切扫操作，先保持一致性。任期号过时。如果一台服务器收到过时的任期号，是会拒绝投票的，意味着总会会选出自己认为最新的服务器。
RPC
Raft 中的服务器通过远程过程调用（RPC）来通信，基本的 Raft 一致性算法仅需要 2 种 RPC。
- RequestVote RPC 是候选人在选举过程中触发的
- AppendEntries RPC 是领导人触发的，为的是复制日志条目和提供一种心跳（heartbeat）机制
1.领导人选举
通过心跳机制（heartb信号）触发领导人选举。所有服务器启动时，都是初始化为追随者（follower）。只有当timeout时间内，没有收到heartbeat，就会跳转到candidate（候选人）状态。
一旦开始开始选举，伴随着候选者将自己的当前任期更新。然后给自己投上一票，并且去其他服务器发送RequestVote
RPC。一个候选人会一直处于该状态，直到下列三种情形之一发生：
- 它赢得了选举；
- 另一台服务器赢得了选举；
- 一段时间后没有任何一台服务器赢得了选举
在同一个任期内，每个人只有一次投票权。当候选人遇到其他服务器的投票请求时，要分情况讨论，若请求的任期晚于自身，拒绝投票；若请求的任期相同，继续保持候选人状态，相当于拒绝投票，应为那一票已经投给自己了；若投票请求任期早于自身，则放弃选举，转为follower状态。
既没有输掉选举，也没有胜选，是什么情况。发生在同一时刻，多个竞选者都成为候选人，导致选票分散。不能产生大多数人支持的选票。所有人都将自增日期，进入下一轮选举。
投票的机制：只会投给日志比自己日志更加新的候选人，以此来保证Leader数据是最新的状态机。日志和状态机不完整或过时的候选人不可能当选。
2.日志复制
服务器：共识通信模型，状态机，日志库
状态机：理解为提供展示和跟踪所有历史状态的内存区域 ，每一个服务器都有一个，让过时服务器恢复到最新版本，就是通过查询过时服务器的历史位置，从历史位置依次恢复。
日志库：包含了客户端数据，当前任期
日志条目：状态机命令，客户端数据，接收数据时领导人任期号
一条客户端命令，除了数据，还包括状态机命令，首先将日志条目复制给其他服务器，若被大多数服务器接受，则Leader立马将状态机命令执行，并且向客户端返回执行结果。一旦追随者知道一条日志被提交，他也会将该条目提交到状态机。
一旦状态机命令被Leader状态机执行，则认为该条日志条目被提交（commited）
我们设计了 Raft 日志机制来保证不同服务器上日志的一致性。这样做不仅简化了系统的行为使得它更可预测，并且也是保证安全性不可或缺的一部分。Raft 保证以下特性，并且也保证了 表-3 中的日志匹配原则（Log Matching Property）:
- 如果在不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
- 如果在不同日志中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全一样的。
第一条特性源于领导人在一个任期里在给定的一个日志索引位置最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，领导人会把新日志条目紧接着之前的条目的索引位置和任期号都包含在里面。如果追随者没有在它的日志中找到相同索引和任期号的日志，它就会拒绝新的日志条目。这个一致性检查就像一个归纳步骤：一开始空的日志的状态一定是满足日志匹配原则的，一致性检查保证了当日志添加时的日志匹配原则。因此，只要 AppendEntries 返回成功的时候，领导人就知道追随者们的日志和它的是一致的了。
3.安全性的性质
3.1 选举限制
在所有的以领导人为基础的一致性算法中，领导人最终必须要存储全部已经提交的日志条目。在一些一致性算法中，例如：Viewstamped Replication，即使一开始没有包含全部已提交的条目也可以被选为领导人。这些算法都有一些另外的机制来保证找到丢失的条目并将它们传输给新的领导人，这个过程要么在选举过程中完成，要么在选举之后立即开始。不幸的是，这种方式大大增加了复杂性。Raft 使用了一种更简单的方式来保证在新的领导人开始选举的时候在之前任期的所有已提交的日志条目都会出现在上边，而不需要将这些条目传送给领导人。这就意味着日志条目只有一个流向：从领导人流向追随者。领导人永远不会覆盖已经存在的日志条目。
Raft 通过比较日志中最后一个条目的索引和任期号来决定两个日志哪一个更新。如果两个日志的任期号不同，任期号大的更新；如果任期号相同，更长的日志更新。
3.2提交之前的任期条目
3.3追溯者姐就选人崩溃
3.3 时序和可用性
动画演示
http://thesecretlivesofdata.com/raft/
中文论文
http://www.infoq.com/cn/articles/raft-paper
说点什么：这篇文章本该三天前就要完成，因为中间又遇到网络编程的临时补充，导致中断。后又因为一拖再拖，不知道如何动笔
的确这种文章不好写，范围太大。总结了一点有助于写作的理论指导，先把大纲弄出来，构成一个个标题。当往标题中添加内容时，最为一个真正理解了的概念，能回答1.是什么 2. 这其中有什么问题 3. 怎么解决