一致性算法

一致性算法是分布式计算领域中用于确保多个节点能够就某个提议或状态达成一致的技术。在分布式系统中，由于网络延迟、节点故障等问题的存在，使得不同节点之间保持数据的一致性变得非常具有挑战性。一致性算法通过一系列规则来保证即使在网络分区或者部分节点失效的情况下，整个系统仍然可以正常运作，并且所有正确工作的节点最终能够对某些值达成共识。

Raft 和 Paxos 都是用于在分布式系统中实现一致性（consensus）的算法。

Paxos

在深入了解Paxos算法之前，我们先来认识一下该算法中的三个关键角色：

• Proposer（提议者）：负责发起提案，试图让系统中的节点就某个值达成共识。
• Acceptor（接受者）：负责接收提议者的提案，并在满足条件的情况下承诺接受这些提案。
• Learner（学习者）：从接受者那里获取已达成共识的值，并将其应用于系统的状态更新。

Paxos算法的主要流程

阶段一：准备（Prepare）

1. Proposer选定一个独一无二的提案编号$n$，并向所有Acceptor广播一个prepare请求，附带该编号。此阶段请求中无需包含具体的提案值。
   • 提案编号用于确保提案的顺序性和唯一性，避免冲突。
   • 通常，Proposer会选择一个比之前所有提案编号都大的值。
2. 当Acceptor接收到prepare请求后，会执行以下操作：
   • 如果Acceptor之前没有承诺过编号大于或等于$n$的提案，则它会回应Proposer，包含它最后一次承诺的提案编号及其值（如果有）。
   • 如果Acceptor已经承诺过编号大于$n$的提案，则它会忽略这个prepare请求。
3. Proposer等待，直到收到来自多数Acceptor的响应，然后进入第二阶段。

阶段二：接受（Accept）

4. Proposer根据收到的响应来确定要提议的值$v$：
   • 如果所有响应中都没有包含提案值，Proposer可以自由选择一个值。
   • 如果有响应包含了提案值，Proposer必须选择编号最大的提案对应的值。
5. Proposer向多数Acceptor发送一个包含提案编号$n$和提案值$v$的accept请求。
6. 当Acceptor接收到accept请求后，会有以下两种处理方式：
   • 如果Acceptor尚未承诺过编号大于$n$的提案，它会接受这个提案，并记录下提案编号$n$和值$v$。
   • 如果Acceptor已经承诺过编号大于$n$的提案，它会忽略这个accept请求。
7. Proposer等待，直到收到多数Acceptor的确认，此时提案$n,v$被视为已被接受。

阶段三：学习（Learn）

8. 当提案$n,v$被多数Acceptor接受后，Learner可以认为这个值已经达成共识，并将其应用于系统状态。
   • Learner可以通过监听Acceptor的接受消息或者通过专门的通信渠道来获知这一信息。
   • 一旦提案被接受，它就成为了系统的一致性决策。

Paxos算法的优势

• 安全性保障：一旦某个值被接受，就不会再被更改，确保了系统状态的一致性。
• 活性保障：只要大多数节点保持活跃，Paxos算法就能持续运行，不会陷入僵局。
• 容错能力：即使部分节点失效或网络出现延迟，只要超过一半的节点能够正常通信，系统仍能正确执行Paxos算法。

Raft

Raft算法是一种实现分布式系统的领导者选举和日志复制的一致性算法，由Diego Ongaro和John Ousterhout在2013年提出。

与Paxos算法相比，Raft算法更易于理解和实现。

Raft算法将一致性问题分解为几个主要的子问题：领导选举、日志复制、安全性和变更配置。

节点角色

• Follower：被动角色，响应来自领导者或候选者的消息。
• Candidate：当 Follower 在一定时间内没有收到领导者的消息时，它会转变为 Candidate 并开始选举过程。
• Leader：负责处理所有客户端请求，并向其他服务器发送心跳信息以保持其领导地位。每次成功的选举后都会有一个新的 Leader。

任期

在Raft中，任期的概念类似于逻辑时间戳，它是一个连续递增的整数。每当发生领导选举时，任期就会增加。每个任期开始时，都会尝试选举出一个新的领导者。任期的作用：

• 区分领导者的有效性：任期用于区分不同领导者的任期，确保系统的状态不会因为旧的领导者而变得混乱。如果一个节点收到了来自一个任期较低的领导者的消息，它会忽略这个消息，因为它知道有更高任期的领导者存在。
• 选举的唯一性：每个任期只能选举出一个领导者。如果一个领导者因为网络分区或故障而失去了与集群的联系，新的任期将会开始，并选举出新的领导者。
• 日志条目的版本控制：任期还被用来保证日志的一致性。每个日志条目都关联着一个任期号，这有助于确定哪些日志条目已经被提交，并且帮助解决不同服务器之间日志不一致的问题。

超时设置

Leader 通过定期向所有 Follower 发送心跳消息来维持其领导地位。心跳消息包含 Leader 当前的任期号，这样可以防止 Follower 因超时而转变为 Candidate 并触发新的选举。

超时设置有助于检测 Leader 的失败，并且能够触发新的选举过程。主要的超时设置包括选举超时和心跳间隔。

1. 选举超时：

   选举超时是指 Follower 在没有收到 Leader 发送的心跳或 AppendEntries RPC 消息后等待的时间长度。如果在这个时间内没有收到任何消息，Follower 将认为当前 Leader 已经失效，并转换为 Candidate 开始新一轮的选举。为了避免多个节点同时成为 Candidate 并引发分裂投票（Split Vote），每个 Follower 在启动时都会设置一个随机的选举超时时间。通常这个时间范围设定在 150ms 到 300ms 之间。

2. 心跳间隔：

   心跳间隔是指 Leader 向所有 Follower 发送心跳消息的频率。Leader 会定期发送空的日志条目或心跳消息给 Follower，以表明自己仍然活跃并且是合法的 Leader。

   心跳间隔通常比选举超时要短得多，一般情况下可能设置为几十毫秒到几百毫秒不等。这样做的目的是确保即使在网络条件不佳的情况下，也能频繁地向 Follower 发送心跳消息。

领导选举

选举触发

当Follower在选举超时时间内没有收到来自Leader的心跳消息时，它会认为Leader已经宕机或网络出现了问题，因此会触发选举过程。

每个Follower都有自己的选举超时计时器，超时时间通常是随机化的，以减少多个节点同时成为Candidate并触发选举的可能性。

选举过程

1. 转换为Candidate：
   • Follower在选举超时后，会将自己的状态转换为Candidate，并开始一轮新的选举任期（Term）。
2. 增加任期号：
   • Candidate会增加自己的当前任期号，并在发起选举时使用这个新的任期号。
3. 请求投票（RequestVote RPC）：
   • Candidate会向集群中的其他节点发送RequestVote RPC消息，请求它们投票给自己成为新的Leader。
   • RequestVote RPC 包含候选人的任期号、候选人最后一条日志条目的索引位置及其任期号、要求投票的请求等信息。
4. 投票规则：
   • 每个节点在一个任期内只能投票一次，通常会投票给第一个请求投票的Candidate，这个规则有助于减少选举冲突。
   • 节点只有在以下情况下才会投票给Candidate：如果Candidate的日志至少和自己一样新（即Candidate的日志至少和自己的一样完整）。
   • 如果Candidate的任期号大于接收者节点当前的任期号，那么接收者会更新自己的任期号，并且如果在这个任期内还没有投票给其他的 Candidate，它会投票给这个 Candidate。
5. 选举结果：
   • 如果一个Candidate从集群中的大多数节点获得了投票，它就会成为新的Leader。
   • 成为Leader后，它会立即向所有其他节点发送心跳消息（通常是空的日志条目形式的 AppendEntries RPC），以确立其领导地位并阻止新的选举。
6. 处理多个Candidate：
   • 如果有多个节点同时成为Candidate，可能会发生分裂投票（Split Vote），此时没有任何Candidate能够获得多数票。
   • 在这种情况下，每个Candidate的选举超时后会再次尝试发起选举，直到有一个Candidate能够获得多数票。

选举后的操作

1. Leader确认：
   • 新选举出的Leader会开始发送心跳消息，以维护其领导地位，并处理来自客户端的请求。
2. 日志复制：
   • Leader会开始复制其日志条目到所有Follower，以确保集群状态的一致性。
3. 处理遗留的Candidate：
   • 在选举过程中，可能会有一些Candidate没有赢得选举。当它们收到来自新Leader的心跳消息时，会自动降级为Follower。

日志复制

一旦选举出领导者，它就开始处理来自客户端的操作请求。

• 客户端请求：客户端发送请求给领导者。
• 日志追加：领导者将客户端请求作为新的日志条目追加到自己的日志中。
• 日志复制：领导者并行地将新条目发送给所有跟随者。跟随者将条目追加到自己的日志中，并回应领导者。
• 提交条目：一旦领导者收到多数（比如超过半数）跟随者的确认，它就会将条目标记为已提交，并将结果返回给客户端。
• 跟随者同步：领导者通过后续的心跳消息通知跟随者哪些条目已被提交，跟随者随后将这些条目应用到自己的状态机。

安全性

选举限制

Raft算法通过选举限制来确保只有拥有最新日志信息的节点才能成为领导者。

• 日志条目完整性：在Raft中，一个节点要想成为领导者，它必须拥有所有已提交日志条目的信息。这是通过比较日志条目的最后索引和任期来实现的。如果一个候选人的日志不如其他节点的新，那么它将无法赢得选举。
• 预防旧领导回归：如果一个节点因为网络分区而失去了领导地位，它的日志可能会落后于其他节点。当网络恢复时，这个节点不能立即成为领导者，因为它可能缺少一些已经提交的日志条目。这种机制防止了旧领导者的数据覆盖新领导者的数据。

日志匹配属性

Raft算法保证了日志匹配属性，这意味着如果两个日志条目在相同的日志位置具有相同的任期编号，那么它们之前的所有日志条目都是相同的。

• 日志复制：领导者将日志条目复制到跟随者节点，并且保证日志条目的顺序。如果跟随者与领导者的日志在某些位置不匹配，领导者会强制跟随者的日志与自己的日志一致。
• 冲突解决：在日志复制过程中，如果发现冲突（即不同的日志条目出现在相同的日志位置），领导者会覆盖跟随者的冲突条目。这是因为领导者拥有最新的已提交日志条目。

提交之前的日志条目

Raft算法确保了在领导者提交一个日志条目之前，该条目必须已经被复制到多数服务器上。

• 多数同意：一个日志条目在被领导者认为是已提交之前，必须被多数节点接受。这意味着即使领导者崩溃，这个条目也不会丢失，因为它已经被复制到了其他节点。
• 防止数据丢失：通过要求多数节点复制日志条目，Raft算法确保了即使在发生网络分区或节点故障的情况下，已提交的数据也不会丢失。

变更配置

Raft算法的配置变更机制允许在不中断服务的情况下添加或移除服务器，这对于分布式系统的可伸缩性和容错性至关重要。

单步变更

1. 提交配置变更请求：
   • 客户端发起一个配置变更请求，该请求被Leader作为一条特殊的日志条目追加到自己的日志中。
   • 这条日志条目包含了新的服务器配置信息。
2. 复制日志条目：
   • Leader将包含配置变更的日志条目复制到所有当前配置中的服务器上。
   • 为了确保变更的安全性，这条日志条目必须被复制到多数服务器上，并且被提交。
3. 应用配置变更：
   • 一旦配置变更的日志条目被提交，新的配置立即生效。
   • 所有服务器根据新的配置开始工作，如果配置中添加了新服务器，Leader将开始向它们复制日志条目；如果配置中移除了服务器，Leader将停止向这些服务器发送日志条目。

单步变更的缺点是，如果在配置变更过程中Leader失效，新的Leader可能仍然使用旧的配置，这可能导致数据不一致。因此，更安全的方法是使用两阶段变更。

两阶段变更

1. 提交中间配置：
   • 首先，将当前的配置和新的配置合并成一个中间配置，并将其作为日志条目追加到Leader的日志中。
   • 这个中间配置包含了所有旧的服务器和新的服务器。
2. 复制并提交中间配置：
   • Leader将中间配置的日志条目复制到所有服务器上，并等待它被提交。
   • 一旦中间配置被提交，系统进入一个过渡状态，在这个状态下，新旧配置都有效。
3. 提交最终配置：
   • 接着，Leader创建一个新的日志条目，只包含新的配置，并将其复制到所有服务器上（包括新加入的服务器）。
   • 当这个最终配置的日志条目被提交后，旧的配置被完全替换，新的配置成为唯一有效的配置。

两阶段变更的关键优势在于它减少了在配置变更过程中出现数据不一致的风险。如果在变更过程中Leader失效，由于中间配置包含了所有服务器，新的Leader仍然可以与多数服务器通信，从而保证系统的稳定性。