Raft算法
在学术界中分布式一致性算法的基石还是Paxos为代表，Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。
由于Paxos难以理解，而且很难落地到工程实践，所以Paxos在工程中运用的并不多
取而代之的是易理解易实现的Raft算法，号称几乎等同于Paxos，但是性能肯定不及Paxos
分布式一致性算法也称为共识算法，是指在大型分布式系统中，在遇到请求时，各个节点的数据能够保持一致，并且在遇到部分机器宕机时，也能保证整体服务的数据一致性
学习Raft算法最好的方式则是阅读论文：https://raft.github.io/raft.pdf 关于Raft协议步骤动画：Raft
这里我们了解Raft算法中核心逻辑，Raft算法中其实大致分为三个子问题 Leader Election 、Log Replication、Safety，对应的也就是选主，日志复制，安全性（通过安全性原则来处理一些特殊 case，保证 Raft 算法的完备性）
Raft的核心流程归纳：
首先选出 leader，leader 节点负责接收外部的数据更新/删除请求 然后日志复制到其他 follower节点，同时通过安全性的准则来保证整个日志复制的一致性 如果遇到 leader 故障，followers 会重新发起选举出新的 leader Raft节点有三种状态：
Leader（领导者） Follower（跟随者） Candidate（候选人） Leader Election 领导选举 所有节点一开始都是follower状态，一定时间未收到leader的心跳，则进入candidate（候选人）状态，参与选举.选出leader后，leader通过向follower发送心跳来表明存活状态，若leader故障，则整体退回到重新选举状态 每次选举完成后，会产生一个term，term本身是递增的，充当了逻辑时钟的作用 具体的选举过程：领导者与跟随者建立心跳（心跳时间随机，为了避免大多数跟随者在同一时间进行选举）并等待，若超时未等到，准备选举 ----> current term ++，转变为candidate（候选人）状态 ----> 给自己投票，然后给其他节点发送投票请求 ----> 等待选举结果
具体投票过程有三个约束：
在同一任期内，单个节点最多只能投一票 候选人知道的信息不能比自己的少(Log与term) first-come-first-served 先来先得
选举结果有三种情况：
收到大部分（超过半数）的投票（含自己的一票），则赢得选举，成为leader 被告知别人已当选，那么自行切换到follower 一段时间内没有收到超过半数以上的投票，则保持candidate状态，重新发出选举。（ps:如果是遇到平票现象，则会增加系统不可用时间，因此，raft中引入了randomized election timeouts，尽量避免出现平票现象的产生）一旦选举完毕，leader节点会给所有其他节点发消息，避免其他节点触发新的选举
Log Replication 日志复制问题
Replicated state machine 复制状态机
分布式服务中，为了保证流量不会压垮服务器，会将一个server复制成很多副本同时提供相同的服务。多副本服务就会出现副本的一致性问题，比如client1将replica1的X值设置为1，而client2将replica2的X值设置为2，这样如果另一个客户client3从不同的副本获取到的X值可能是1也可能是2，这就导致了副本的一致性问题。
复制状态机就是用来解决副本的一致性问题的，每个副本都是状态机的实现，而且是确定状态机(Deterministic finite-state machine)。使用状态机来实现每个服务器的副本就保证了对相同的输入，每个副本都会产生一致的输出。并且，将每个客户端的请求汇总成一个序列，每个副本都按照这个序列来执行，这就解决了副本的不一致问题。
复制状态机（Replicated State Machine）是指多台机器具有完全相同的状态，运行完全相同的确定性状态机。它让多台机器协同工作犹如一个强化的组合，其中少数机器宕机不影响整体的可用性。复制状态机是实现容错的基本方法，被广泛应用于数据复制和高可用等场景，一直是工业界和学术界的关注热点。越来越多的系统采用复制状态机来实现高可用，如ZooKeeper、ETCD、MySQL Group Replication、TiDB等，各种复制协议和系统架构的研究也层出不穷。如何抽象一个复制状态机系统的架构，使之更加通用和易用呢？本文从复制状态机模型出发，结合一些业界的前沿研究，总结复制状态机系统的架构抽象，在系统架构设计时具有一定参考意义。
复制状态机一般通过复制日志来实现，简单地描述一下：leader将写请求封装成一个个的 log entry，然后将这些 entries复制到 follower（从节点），所有 follower都按照这个这个顺序执行其中的 command（指令），那么所有 server的状态一定是一致的。这就是 raft的做法
复制过程
1.客户端的请求包含了被复制状态机执行的指令，并转发给leader
2.leader把指令作为新的日志，并发送给其他server，让他们复制
3.假如日志被安全的复制（收到超过majority的ack），leader会将日志添加到状态机中，并返回给客户端
4.如果follower丢失，leader会不断重试，直到全部follower都最终存储了所有日志条目
以上都是理想的状态下，若出现崩溃、网络中断等问题，可能会出现日志不正常的现象，则需要考虑数据一致性和安全性问题