Raft算法
Raft 把这个一致性的算法分解成了几个部分，一个是领导选举（Leader Selection），一个是日志复制（Log Replication），一个是安全性（Safety），还有一个是成员变化（Membership Changes）。
Raft 协议中有一个状态机，每个结点会有三个状态，分别是 Leader、Candidate 和 Follower。Follower 只响应其他服务器的请求，如果没有收到任何信息，它就会成为一个 Candidate，并开始进行选举。收到大多数人同意选票的人会成为新的 Leader。
一旦选举出了一个 Leader，它就开始负责服务客户端的请求。每个客户端的请求都包含一个要被复制状态机执行的指令。Leader 首先要把这个指令追加到 log 中形成一个新的 entry，然后通过 AppendEntries RPC 并行地把该 entry 发给其他服务器（server）。如果其他服务器没发现问题，复制成功后会给 Leader 一个表示成功的 ACK。Leader 收到大多数 ACK 后应用该日志，返回客户端执行结果。如果 Follower 崩溃 （crash）或者丢包，Leader 会不断重试 AppendEntries RPC。
Raft的日志
指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
任期编号：创建这条日志项的领导者的任期编号。
首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上。接着，如果领导者接收到大多数的“复制成功”响应后，它将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端。
接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项应用到它的状态机中。
领导者将执行的结果返回给客户端。
当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中。
如何实现日志的一致？
在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。具体有 2 个步骤。首先，领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。也就是先向前找到一样的日志的点位，然后覆盖掉后面不一样的地方。如果日志是不连续的，这一点就不能保证。
日志完整性最高的节点才能当选领导者
这是为了防止之前的领导者突然挂掉，保证一旦相应客户端请求，保证服务端至少有一台机器和客户端理解的一样。复制和应用日志是两个步骤，只有复制到大多数机器上，领导者才能把结果返回给客户端，然后应用日志。所以这时其他跟随者节点就有这个已复制，但是未应用的揭露。
Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），
在领导者选举中，需要用到这样两类的 RPC：
1. 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
2. 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。我想强调的是，日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键之一（就像猴王像后代传递基因一样）
利用“一次变更一个节点，不会同时存在旧配置和新配置 2 个‘大多数’”的特性，实现成员变更。
在 Raft 中，不是所有节点都能当选领导者，只有日志最完整的节点，才能当选领导者；其次，在 Raft 中，日志必须是连续的。Raft 算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导，也极大地减少了选举失败的情况。本质上，Raft 算法以领导者为中心，选举出的领导者，以“一切以我为准”的方式，达成值的共识，和实现各节点日志的一致。
Raft这种"一切以我为主"的强领导模型和上一讲中的chubby有点类似，chubby是只能从主节点读取，相当于单机，性能和吞吐量有限
Raft的强领导模型是写要以主为主，也相当于单机了。性能和吞吐量也会受到限制
我们通过 Raft 算法实现了 KV 存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接入性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系统过载和服务不可用，这时该怎么办呢？其实这是一个非常常见的问题。在我看来，这时我们就要通过分集群，突破单集群的性能限制了。答案就是一致哈希
类似的算法还有Bully算法，ZAB算法，主要是选举机制和选举过程不同，需要关注的是选举所需时间的长短。
Lamport算法
算法中提到了逻辑时间戳的概念，解决了分布式系统中没有统一时间戳的问题。由于分布式系统没有统一的时钟，因此无法知道各个进程申请访问临界资源的先后顺序。在集中互斥算法中是通过协调者记录先后顺序的，而在 Lamport 算法中，每个节点进程都会维护一个逻辑时钟，当系统启动时，所有节点上的进程都会对这个时钟进行初始化，每当节点进程向其他节点进程发起临界资源访问申请的时候，就会将这个逻辑时间戳加 1。同样，每个节点进程在接收到来自其他节点进程的申请请求时，也会更新自己的逻辑时钟，具体地，对自己逻辑时钟与发出请求的节点的逻辑时钟进行比较，选出最大值后加 1。
在 Lamport 算法中，根据逻辑时钟的大小来选择由哪个节点进程获取临界资源的访问权限：逻辑时钟最小的节点将首先获得临界资源的使用权；如果逻辑时钟相同，就让节点编号较小的进程使用资源。同时每个节点进程都会维护一个请求队列，这个队列按照时间戳的优先级对各节点进程的请求进行排序，时间戳越小的节点进程排在越前面。
每个节点进程在初始化时，时间戳为 0；
当节点进程发起资源使用申请时，将其自带的时间戳加 1；
发起申请的节点进程将节点编号和时间戳一起发送给分布式系统中的其他节点；
其他节点接收到申请消息以后，更新本地的时间戳，更新公式是 Max（本地时间戳，消息中的时间戳）＋ 1。
(1) 节点进程 1 完成对时间戳的初始化以后，需要访问临界资源，于是通过 REQUEST 消息将节点 ID 和时间戳发送给节点进程 2 和节点进程 3。（会发送给其他所有的节点）
(2) 节点进程 2 和节点进程 3 接收到请求以后，根据 Lamport 算法更新本地的时间戳，同时将节点进程 1 的请求添加到本地的资源访问链表中。这样做的目的是如果此时还有其他节点也在申请访问资源，那么根据时间戳算法，其他节点的时间戳比节点进程 1 大，因此在链表中排在节点进程 1 后面。排队以后，节点进程 2 和节点进程 3 会发送 REPLY 消息给节点进程 1，也就是许可节点进程 1 对临界资源的访问。
(3) 节点进程 1 接到许可信息以后，对临界资源进行访问。
(4) 节点进程 1 访问完资源以后，会向节点进程 2 和节点进程 3 发出 RELEASE 消息，这两个进程接收到消息以后，会把节点进程 1 从链表中删除，此时如果链表中还排列着其他节点进程的请求，则会重复第 (2) 步。
按照 Lamport 算法的思路，在一个含 n 节点的分布式系统中，访问一次临界资源需要发送 3 (n－1) 次消息，其中 REQUEST、REPLY 和 RELEASE 消息各发送 n－1 条。发送过多的消息容易导致网络堵塞，因此 Richard&Agrawal 算法对 Lamport 算法进行了改进，将 Lamport 算法中的 RELEASE 消息和 REPLY 消息合并为一个，这样消息的发送次数就从 3(n－1) 降到了 2(n－1)。在 Richard&Agrawal 算法中，节点进程访问临界资源时，发送 REQUEST 消息到其他节点进程，其他节点进程接收到请求后做以下动作：如果自己没有访问临界资源，就直接返回 REPLY 消息，允许发送请求的节点进程访问；如果自己正在访问临界资源，就对自己和发送请求的节点的时间戳进行排序，若后者的时间戳排在前面，则不回复任何消息，否则返回 REPLY 消息，允许其访问临界资源。请求节点接收到 REPLY 消息以后对临界资源进行访问，访问完成后向请求访问链表中的请求节点发送 REPLY 消息，链表中的节点根据优先级发送下一轮的资源访问请求。
由上面两个算法的原理可以看出，基于许可的互斥算法是一个会征求每个进程意见的公平算法，但随着系统中访问资源的进程增加，其他通信成本也会变多。因此，这种算法可以用在临界资源使用频率较低且系统规模较小的场景。
一致性级别
数据的一致性模型定义了，一个数据对象在多个节点上有多个副本时，对外部读写表现出来的现象。数据一致性模型从强至弱分别为：线性一致性、顺序一致性、因果一致性和最终一致性。其中线性一致性是我们目前可以实现的一致性最强的模型，对于线性一致性的数据复制模型，我们可以认为它和操作单副本是一样的结果，基于它搭建的数据系统一般都是 CP 系统。
而一致性级别最弱的最终一致性，它只能确保数据最终会一致，并不能明确这个时间有多长。最终一致性牺牲了数据一定程度上的正确性，换取了高性能和高可用，在高并发的互联网场景中经常被使用，基于它搭建的数据系统一般都是 AP 系统。
其次，共识是指多个节点（进程）对某一个事情达成一致的结果，一个完备的共识算法需要满足四个要求：一致同意、诚实性、合法性和可终止性。共识算法主要用于解决 Leader 选举和分布式锁服务等分布式场景中，最底层、最基础的问题，所以基于 Leader 的线性一致性算法，通常都需要依赖共识算法来实现选举。
