分布式

分布式系统的一致性算法(2PC到Paxos)

分布式系统的一致性算法(2PC到Paxos) 在分布式系统中，一个事务可能涉及到集群中的多个节点。单个节点很容易知道自己执行的事务成功还是失败，但因为网络不可靠难以了解其它节点的执行状态(可能事务执行成功但网络访问超时)。 若部分节点事务执行失败进行回滚，而其它节点完成事务提交，则事务会处于部分完成

分布式系统的一致性算法(2PC到Paxos)

在分布式系统中，一个事务可能涉及到集群中的多个节点。单个节点很容易知道自己执行的事务成功还是失败，但因为网络不可靠难以了解其它节点的执行状态(可能事务执行成功但网络访问超时)。

若部分节点事务执行失败进行回滚，而其它节点完成事务提交，则事务会处于部分完成的不一致状态。为了避免错误，分布式系统需要使用分布式一致性协议来保证分布式事务的执行。

2PC

两阶段提交(2-Phase Commit, 2PC)是一种比较简单的分布式一致性协议。

2PC协议中，每个事务需要一个协调者来协调各个参与者。每个事务分为两步执行。

  1. 阶段一: 事务请求
    1. 协调者向所有参与者发送事务内容，询问是否可以执行事务操作。
    2. 各参与者执行事务，写事务日志但不进行提交。 各参与者锁定事务相关的资源，保证事务可以正常提交。
    3. 各参与者向协调者返回响应，YES表示可以提交，NO表示不可以提交。若协调者收到所有参与者的YES回复，则准备进行事务提交。若有参与者回复NO或者超时，则准备回滚事务。
  2. 阶段二: 提交事务
    1. 协调者向所有参与者发送提交请求
    2. 参与者正式提交事务，并在完成后释放相关资源。
    3. 参与者协调者回复ACK，协调者收到所有参与者的ACK后认为事务提交成功。
  3. 回滚事务
    1. 在事务请求阶段若有参与者回复NO或者超时，协调者向所有参与者发出回滚请求
    2. 各参与者执行事务回滚，并在完成后释放相关资源。
    3. 参与者协调者回复ACK，协调者收到所有参与者的ACK后认为事务回滚成功。

2PC是一种简单的一致性协议，它存在一些问题:

  • 单点服务: 若协调者突然崩溃则事务流程无法继续进行或者造成状态不一致
  • 无法保证一致性: 若协调者第二阶段发送提交请求时崩溃，可能部分参与者受到COMMIT请求提交了事务，而另一部分参与者未受到请求而放弃事务造成不一致现象。
  • 阻塞: 为了保证事务完成提交，各参与者在完成第一阶段事务执行后必须锁定相关资源直到正式提交，影响系统的吞吐量。

参与者在完成阶段一的事务执行后等待协调者的下一个请求，若协调者超时则可以自行放弃事务。

这种方案仍然有无法保证一致性的缺点，但并不会出现某些资料所述一直锁定资源，无法继续的情况。

3PC

三阶段提交协议(3-Phase Commit, 3PC)进一步将事务请求分为两个阶段，可以解决2PC协议阻塞的问题但无法解决单点服务和不一致的问题。

3PC协议下事务分三步提交:

  1. CanCommit
    1. 协调者向所有参与者发送CanCommit请求
    2. 各参与者判断是否可以完成事务提交，但不执行事务也不锁定资源
    3. 各参与者根据是否可以完成事务向协调者回复YES或NO
  2. PreCommit
    1. 协调者向所有参与者发送PreCommit请求，执行事务预提交
    2. 各参与者执行事务，写事务日志但不进行提交。 各参与者锁定事务相关的资源，保证事务可以正常提交。
    3. 各参与者向协调者返回响应。若协调者收到所有参与者的YES回复，则准备进行事务提交。若有参与者回复NO或者超时，则放弃事务。
  3. DoCommit
    1. 协调者向所有参与者发送提交请求
    2. 参与者正式提交事务，并在完成后释放相关资源。
    3. 参与者协调者回复ACK，协调者收到所有参与者的ACK后认为事务提交成功。若有参与者回复NO或者超时，则回滚事务。
    4. 参与者进入 PreCommit 状态后，若始终未收到协调者的 DoCommit 请求则会超时后自动执行提交。

三阶段提交协议在CanCommit阶段不锁定资源，解决了阻塞降低吞吐量的问题。

若某个参与者进入 PreCommit 后始终未收到协调者的进一步指令则会自动提交，该策略一定程度上避免协调者单点服务问题。

但是 3PC 仍然无法解决数据不一致问题。

Paxos

Paxos 算法的目的在于使分布式系统对于某个值达成一致，比如 Master 选举过程中保证最终所有节点对 Master 身份达成共识。

作者认为 Paxos 解决的分布式共识问题与分布式事务有着较大不同。

Paxos 认为信道可能丢失数据但是不会篡改数据(即不存在拜占庭将军问题)，实际上我们也很容易通过校验检查数据是否被篡改。

在介绍Paxos算法之前，我们先来分析2PC(3PC)协议在分布式共识问题上的不足。

2PC(3PC)协议要求收到所有参与者的 ACK 消息后才认为提交成功，而在Master选举这类分布式共识问题上只需要过半参与者达成一致即可。

而最难以解决的问题在于协调者的单点服务问题，若协调者在过程中崩溃则集群很难继续达成共识。

因此，关键在于设计在有多个协调者的情况下仍然可以达成共识的协议。

Basic Paxos

Paxos算法中有3个角色:

  • Proposer: 负责发起提案，类似于2PC中的协调者
  • Acceptor: 负责批准提案，类似于2PC中的参与者
  • Learner: 不参与提案过程，只从其它Acceptor那里学习已通过的提案。

我们重点介绍 Proposer 和 Acceptor 参与的流程，暂时不介绍 Learner。

在集群中每个进程(节点)可能会扮演其中多个角色。

提案由编号N和值V组成记作(N, V), 每个提案都的编号N是唯一的。保证编号唯一非常简单，若集群中有k个 Proposer， 那么第i个Proposer提出的第n个提案编号为 i + k * n。

我们希望集群最终可以选中一个V，且所有节点知道集群最终选定的V值。

算法做出几个规定:

  • 只要集群中有超过半数的Accpetor批准了提案，Proposer 就可以认为集群对接受了提案
  • 在一轮投票中，Acceptor总是批准它收到的第一个提案
  • 在一轮投票中，Acceptor可以批准多个提案，但是批准提案的值V必须相同

算法分为两个阶段:

  1. prepare 阶段
    1. Proposer 选择提案N，向半数以上Acceptor发送请求Prepare(N)
    2. Acceptor 保存自己受到过的最大请求的编号 maxN 和已接受的编号最大提案 (acceptedN, acceptedV)。
      • 若 maxN > N, 那么 Acceptor 返回拒绝响应
      • 若 maxN < N, 那么 Acceptor 返回已接受的编号最大提案(acceptN, acceptV)，若尚未接受过提案则返回空的成功响应。同时，Acceptor 更新 maxN, 即不会在接受编号小于N的请求
  2. accept 阶段
    1. 若 Proposer 收到过半 Acceptor 对 Prepare(N) 返回的ACK响应，那么它会从响应的提案中选出编号最大的一个(acceptN, acceptV)， 若响应中不包含提案则由 Proposer 决定提案。决定提案后 Proposer 会向过半 Acceptor 发送 Accept(N, V)请求。
    2. Acceptor 收到 Accept(N, V) 请求后
      • 若 maxN > N, 那么 Acceptor 返回拒绝响应
      • 若 maxN < N, 那么 Acceptor 返回成功响应，并更新已接受的编号最大提案 (acceptedN, acceptedV)
    3. 若 Proposer 未收到过半 Acceptor 对 Accept(N, V) 请求的成功响应，则认为提案被拒绝。

若集群中存在两个 Proposer 依次提出编号递增的提案可能会使 Paxos 算法陷入死循环:

  1. Proposer1 提出提案 N1， 并收到过半Prepare(N1)响应
  2. Proposer2 提出提案 N2 (N2 > N1)， 并收到过半Prepare(N2)响应
  3. Proposer1 进入第二阶段, 过半Accept(N1)请求被拒绝 (过半Acceptor 的 maxN = N2)。 Proposer1 提出提案 N3 (N3 > N2) ...

这种情况称为算法陷入活锁，在工程实践中我们通常选择一个 Proposer 作为 leader。

Paxos 算法实现难度和运行开销非常大，因此开发出 Raft、ZAB等协议用于生产实践。

Raft

动画详解Raft: https://thesecretlivesofdata.com/raft/

这个动画配合文章看，动画非常形象

Raft是一个用于管理日志一致性的协议。它将分布式一致性分解为多个子问题：Leader选举（Leader election）、日志复制（Log replication）、安全性（Safety）、日志压缩（Log compaction）等。同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选者（Candidate）：

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
  • Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
  • Candidate：Leader选举过程中的临时角色。

image-vgal.png

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

2、Term

Raft 算法将时间划分成为任意不同长度的任期（term）。任期用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，它就会在该任期的剩余时间担任领导人。在某些情况下，选票会被瓜分，有可能没有选出领导人，那么，将会开始另一个任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

3、RPC

Raft 算法中服务器节点之间通信使用远程过程调用（RPC），并且基本的一致性算法只需要两种类型的 RPC，为了在服务器之间传输快照增加了第三种 RPC。

【RPC有三种】：

  • RequestVote RPC：候选人在选举期间发起。
  • AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成。
  • InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。

二、Leader选举

1、Leader选举的过程

Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

每一个follower都有一个时钟，是一个随机的值，表示的是follower等待成为leader的时间，谁的时钟先跑完，则发起leader选举。

Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。结果有以下三种情况：

  • 赢得了多数的选票，成功选举为Leader；
  • 收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；
  • 没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

image-txzm.png

2、Leader选举的限制

在Raft协议中，所有的日志条目都只会从Leader节点往Follower节点写入，且Leader节点上的日志只会增加，绝对不会删除或者覆盖。

这意味着Leader节点必须包含所有已经提交的日志，即能被选举为Leader的节点一定需要包含所有的已经提交的日志。因为日志只会从Leader向Follower传输，所以如果被选举出的Leader缺少已经Commit的日志，那么这些已经提交的日志就会丢失，显然这是不符合要求的。

这就是Leader选举的限制：能被选举成为Leader的节点，一定包含了所有已经提交的日志条目。

三、日志复制（保证数据一致性）

1、日志复制的过程

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

  • 客户端的每一个请求都包含被复制状态机执行的指令。
  • leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让他们复制这条信息。
  • 假如这条日志被安全的复制，领导人就应用这条日志到自己的状态机中，并返回给客户端。
  • 如果 follower 宕机或者运行缓慢或者丢包，leader会不断的重试，直到所有的 follower 最终都复制了所有的日志条目。

image-jjnf.png

简而言之，leader选举的过程是：1、增加term号；2、给自己投票；3、重置选举超时计时器；4、发送请求投票的RPC给其它节点。

2、日志的组成

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

image-bymt.png

上图显示，共有 8 条日志，提交了 7 条。提交的日志都将通过状态机持久化到磁盘中，防止宕机。

3、日志的一致性

image-yshm.png

（1）日志复制的两条保证

  • 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的（原因：leader 最多在一个任期里的一个日志索引位置创建一条日志条目，日志条目在日志的位置从来不会改变）。
  • 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的（原因：每次 RPC 发送附加日志时，leader 会把这条日志条目的前面的日志的下标和任期号一起发送给 follower，如果 follower 发现和自己的日志不匹配，那么就拒绝接受这条日志，这个称之为一致性检查）。

（2）日志的不正常情况

image-jqub.png

一般情况下，Leader和Followers的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。

下图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

（3）如何保证日志的正常复制

Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。

具体的操作是：Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位置点（基于上述的两条保证），然后向后逐条覆盖Followers在该位置之后的条目。

总结一下就是：当 leader 和 follower 日志冲突的时候，leader 将校验 follower 最后一条日志是否和 leader 匹配，如果不匹配，将递减查询，直到匹配，匹配后，删除冲突的日志。这样就实现了主从日志的一致性。

四、安全性

Raft增加了如下两条限制以保证安全性：

  • 拥有最新的已提交的log entry的Follower才有资格成为leader。
  • Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

image-mubl.png

五、日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃（以前的数据已经落盘了）。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

【Snapshot中包含以下内容】：

  • 日志元数据，最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
  • 系统当前状态。

当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。

做snapshot既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。

做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。

image-whgf.png

六、成员变更

1、常规处理成员变更存在的问题

我们先将成员变更请求当成普通的写请求，由领导者得到多数节点响应后，每个节点提交成员变更日志，将从旧成员配置（Cold）切换到新成员配置（Cnew）。但每个节点提交成员变更日志的时刻可能不同，这将造成各个服务器切换配置的时刻也不同，这就有可能选出两个领导者，破坏安全性。

考虑以下这种情况：集群配额从 3 台机器变成了 5 台，可能存在这样的一个时间点，两个不同的领导者在同一个任期里都可以被选举成功（双主问题），一个是通过旧的配置，一个通过新的配置。

简而言之，成员变更存在的问题是增加或者减少的成员太多了，导致旧成员组和新成员组没有交集，因此出现了双主。

image-pjbk.png

2、解决方案之一阶段成员变更

Raft解决方法是每次成员变更只允许增加或删除一个成员（如果要变更多个成员，连续变更多次）。

image-pghb.png

七、关于Raft的一些面试题

1、Raft分为哪几个部分？

主要是分为leader选举、日志复制、日志压缩、成员变更等。

2、Raft中任何节点都可以发起选举吗？

Raft发起选举的情况有如下几种：

  • 刚启动时，所有节点都是follower，这个时候发起选举，选出一个leader；
  • 当leader挂掉后，时钟最先跑完的follower发起重新选举操作，选出一个新的leader。
  • 成员变更的时候会发起选举操作。

3、Raft中选举中给候选人投票的前提？

Raft确保新当选的Leader包含所有已提交（集群中大多数成员中已提交）的日志条目。这个保证是在RequestVoteRPC阶段做的，candidate在发送RequestVoteRPC时，会带上自己的last log entry的term_id和index，follower在接收到RequestVoteRPC消息时，如果发现自己的日志比RPC中的更新，就拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。

4、Raft网络分区下的数据一致性怎么解决？

发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follwer了，那么Leader只能正常更新它能访问的那些Follower，而大多数的Follower因为没有了Leader，他们重新选出一个Leader，然后这个 Leader来接受客户端的请求，如果客户端要求其添加新的日志，这个新的Leader会通知大多数Follower。如果这时网络故障修复 了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算commit，都回滚，接受新的Leader的新的更新（递减查询匹配日志）。

5、Raft数据一致性如何实现？

主要是通过日志复制实现数据一致性，leader将请求指令作为一条新的日志条目添加到日志中，然后发起RPC 给所有的follower，进行日志复制，进而同步数据。

6、Raft的日志有什么特点？

日志由有序编号（log index）的日志条目组成，每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。

7、Raft和Paxos的区别和优缺点？

  • Raft的leader有限制，拥有最新日志的节点才能成为leader，multi-paxos中对成为Leader的限制比较低，任何节点都可以成为leader。
  • Raft中Leader在每一个任期都有Term号。

8、Raft prevote机制？

Prevote（预投票）是一个类似于两阶段提交的协议，第一阶段先征求其他节点是否同意选举，如果同意选举则发起真正的选举操作，否则降为Follower角色。这样就避免了网络分区节点重新加入集群，触发不必要的选举操作。

9、Raft里面怎么保证数据被commit，leader宕机了会怎样，之前的没提交的数据会怎样？

leader会通过RPC向follower发出日志复制，等待所有的follower复制完成，这个过程是阻塞的。

老的leader里面没提交的数据会回滚，然后同步新leader的数据。

10、Raft日志压缩是怎么实现的？增加或删除节点呢？？

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃（以前的数据已经落盘了）。

snapshot里面主要记录的是日志元数据，即最后一条已提交的 log entry的 log index和term。

11、Raft里面的lease机制是什么，有什么作用？

租约机制确保了一个时刻最多只有一个leader，避免只使用心跳机制产生双主的问题。中心思想是每次租约时长内只有一个节点获得租约、到期后必须重新颁发租约。

Comment