CAP定理与Raft算法

CAP

概念

CAP 定理指的是在一个分布式系统中，一致性 Consistency、可用性 Availability、分区容 错性 Partition tolerance，三者不可兼得。

• 一致性（C）：分布式系统中多个主机之间是否能够保持数据一致的特性。即，当系统数据发生更新操作后，各个主机中的数据仍然处于一致的状态。
• 可用性（A）：系统提供的服务必须一直处于可用的状态，即对于用户的每一个请求，系统总是可以在有限的时间内对用户做出响应。
• 分区容错性（P）：分布式系统在遇到任何网络分区故障时，仍能够保证对外提供满足一致性和可用性的服务。

CAP 定理的内容是：对于分布式系统，网络环境相对是不可控的，出现网络分区是不可
避免的，因此系统必须具备分区容错性。但系统不能同时保证一致性与可用性。即要么 CP，要么 AP。

BASE 理论

BASE 是 Basically Available（基本可用）、Soft state（软状态）和 Eventually consistent（最终一致性）三个短语的简写，BASE 是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于 CAP 定理逐步演化而来的。

BASE 理论的核心思想是：即使无法做到强一致性，但每个系统都可以根据自身的业务
特点，采用适当的方式来使系统达到最终一致性。
（1 ） 基本可用
基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。
（2 ） 软状态
软状态，是指允许系统数据存在的中间状态，并认为该中间状态的存在不会影响系统的
整体可用性，即允许系统主机间进行数据同步的过程存在一定延时。软状态，其实就是一种灰度状态，过渡状态。
（3 ） 最终一致性
最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到
一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要保证系统数据的实时一致性。

Raft

基础

Raft 算法是一种通过对日志复制管理来达到集群节点一致性的算法。这个日志复制管理
发生在集群节点中的 Leader 与 Followers 之间。Raft 通过选举出的 Leader 节点负责管理日志复制过程，以实现各个节点间数据的一致性。

角色、任期及角色转变

Leader：唯一负责处理客户端写请求的节点；也可以处理客户端读请求；同时负责日志
复制工作
Candidate：Leader 选举的候选人，其可能会成为 Leader。是一个选举中的过程角色
Follower：可以处理客户端读请求；负责同步来自于 Leader 的日志；当接收到其它
Cadidate 的投票请求后可以进行投票；当发现 Leader 挂了，其会转变为 Candidate 发起Leader 选举

leader 选举

通过 Raft 算法首先要实现集群中 Leader 的选举。

1. 我要选举
   若 follower 在心跳超时范围内没有接收到来自于 leader 的心跳，则认为 leader 挂了。此时其首先会使其本地 term 增一。然后 follower 会完成以下步骤：

   • 此时若接收到了其它 candidate 的投票请求，则会将选票投给这个 candidate
   • 由 follower 转变为 candidate
   • 若之前尚未投票，则向自己投一票
   • 向其它节点发出投票请求，然后等待响应

2. 我要投票
   follower 在接收到投票请求后，其会根据以下情况来判断是否投票：

   • 发来投票请求的 candidate 的 term 不能小于我的 term
   • 在我当前 term 内，我的选票还没有投出去
   • 若接收到多个 candidate 的请求，我将采取 first-come-first-served 方式投票

3. 等待响应
   当一个 Candidate 发出投票请求后会等待其它节点的响应结果。这个响应结果可能有三种情况：

   • 收到过半选票，成为新的 leader。然后会将消息广播给所有其它节点，以告诉大家我是新的 Leader 了
   • 接收到别的 candidate 发来的新 leader 通知，比较了新 leader 的 term 并不比自己的 term小，则自己转变为 follower
   • 经过一段时间后，没有收到过半选票，也没有收到新 leader 通知，则重新发出选举

4. 选举时机
   在很多时候，当 Leader 真的挂了，Follower 几乎同时会感知到，所以它们几乎同时会变为 candidate 发起新的选举。此时就可能会出现较多 candidate 票数相同的情况，即无法选举出 Leader。
   为了防止这种情况的发生，Raft 算法其采用了 randomized election timeouts 策略来解决这个问题。其会为这些 Follower 随机分配一个选举发起时间 election timeout，这个 timeout在 150-300ms 范围内。只有到达了 election timeout 时间的 Follower 才能转变为 candidate，否则等待。那么 election timeout 较小的 Follower 则会转变为 candidate 然后先发起选举，一般情况下其会优先获取到过半选票成为新的 leader。

口述：follower与leader会有一个心跳测试，当follower在心跳范围内没有收到leader的响应时，则认为leader挂了，此时它将吧自己的term＋1，当此时收到了别的candidate的投票请求时，他会比较发来请求的candidate的term，发来的term要大于等于自己的term，并且当自己还有选票时会投给他，当没有candidate向自己发投票请求时，他自己会转变为candidate并且吧票投给自己然后向其他节点发出投票请求（为了避免同一个时间follower同时变为candidate，因为当leader挂了的化follower几乎会同时感知到，所以就会同时变为candidate发起新的选举，Raft采取randomized election timeouts 策略来避免，就是为每一个follower分配一个随机选举发起的时间，到了这个时间才能发起选举，避免了很多follower同时发起选举），然后等待响应。
当收到了一半以上的选票时，这个candidate变为leader并且广播通知其他节点，当等待响应时间内收到了其他candidate的leader通知，他会比较发来的term和自己的term，当发来的>=自己的，则自己会变为follower，当经过一段时间没有收到过半的选票并且也没有其他candidate的leader通知时，他就会重新发起选举。

数据同步

在 Leader 选举出来的情况下，通过日志复制管理实现集群中各节点数据的同步。

• 状态机：Raft 算法一致性的实现，是基于日志复制状态机的。状态机的最大特征是，不同 Server中的状态机若当前状态相同，然后接受了相同的输入，则一定会得到相同的输出。
  

• 处理流程
  
  当 leader 接收到 client 的写操作请求后，大体会经历以下流程：

1. leader 在接收到 client 的写操作请求后，leader 会将数据与 term 封装为一个 box，并随着下一次心跳发送给所有 followers，以征求大家对该 box 的意见。同时在本地将数据封装为日志
2. follower在接收到来自leader的box后首先会比较该box的term与本地记录的曾接受过
   的 box 的最大 term，只要不比自己的小就接受该 box，并向 leader 回复同意。同时会将
   该 box 中的数据封装为日志。
3. 当 leader 接收到过半同意响应后，会将日志 commit 到自己的状态机，状态机会输出一个结果，同时日志状态变为了 committed
4. 同时 leader 还会通知所有 follower 将日志 commit 到它们本地的状态机，日志状态变为了 committed，在 commit 通知发出的同时，leader 也会向 client 发出成功处理的响应。

raft 算法不是强一致性的，而是最终一致的。