Hollis的个人博客
Hollis的个人博客

面试：Raft 共识算法

Hollis Hollis 收录于 Raft 和 面试
  约 4200 字 预计阅读 9 分钟  - 次阅读   - 条评论  

简介

Raft 共识算法是一种用于分布式系统的共识算法，是 Paxos 算法的一种改进，通过逻辑分离和明确的角色（领导者、跟随者和候选者）简化了对分布式一致性的理解，确保集群中的每个节点都同意一系列相同的状态转换，并通过领导选举和日志复制机制保证数据的安全性和一致性。

领导选举

1. 成员身份与角色

领导者（Leader）：负责处理客户端请求，维护日志一致性，并向跟随者发送心跳信息。

跟随者（Follower）：在正常情况下不接收客户端请求，仅从领导者接收日志条目和心跳信息。

候选者（Candidate）：在领导者失效时，跟随者会转变为候选者并发起选举。

角色的变化顺序只能是：跟随者 —> 候选者 —> 领导者，然后循环。

跟随者不能直接变成领导者，领导者也不能直接变成候选者。

如果自己是领导者，现在又要参与任期的投票，决策的任期比自己的任期大，那么自己就会从领导者变成别人的跟随者。

2. 选举触发条件

当跟随者在一段时间内（选举超时时间）没有收到领导者的心跳信息时，会转变为候选者并发起选举。

3. 选举过程

  1. 请求投票（RequestVote RPC）

    • 候选者增加自己的任期编号（如从 0 增加到 1），并向集群中的其他节点发送 RequestVote RPC 请求，请求它们投票给自己。

      如果在对 Peer 请求投票时，发现有 Peer 的任期高于自己（候选者）的任期，则将自己的任期更新为较大值，重置自己的投票权利，并直接返回。

    • 每个候选者自荐时会获得自己的一票。

  2. 投票规则

    • 跟随者收到 RequestVote RPC 请求后，会检查以下条件：

      • 请求者的任期编号是否大于或等于自己的任期编号。
      • 自己是否已经在这一任期内投过票（每个任期只能投一票）。
      • 请求者的日志是否至少和自己一样新（通过比较最后一条日志的索引和任期编号）。

    • 如果以上条件都满足，跟随者会投票给请求者，并更新自己的任期编号。

      Peer 对候选者投票之后，会重置选举时钟。

  3. 收集选票

    • 候选者等待来自集群中其他节点的投票响应。
    • 如果候选者获得了超过半数的选票（N/2 + 1，其中 N 为集群中节点的总数），则成为新的领导者。

  4. 选票计数

    • 如果有多个候选者同时请求投票，选票可能会被拆分。
    • 如果在某个任期内没有候选者获得超过半数的选票，那么选举将失败，任期编号会增加，进入下一轮选举。

  5. 选举超时

    • 如果跟随者在一段时间内没有收到领导者的心跳信息，也没有收到任何候选者的 RequestVote RPC 请求，它将再次增加自己的任期编号并进入候选者状态，发起新的选举。

4. 领导者与跟随者交互

  • 一旦选举出新的领导者，领导者会开始发送心跳信息给跟随者，以维持其领导地位并防止新的选举发生。

    跟随者接收到领导者的心跳信息后，会重置自己的选举时钟。

    如果领导者向跟随者发送心跳信息时，发现有跟随者的 Term 大于自己的 Term，则将领导者变成候选者，并更新其 Term。

  • 跟随者会响应领导者的心跳信息，确认领导者的存在，并在需要时从领导者那里接收新的日志条目。

    系统是如何保证一定存在一个领导者的？领导者挂了怎么办？

    如果领导者失效了，则跟随者会因为收不到心跳信息而超时，然后自己发起新的选举，这样就会产生新的领导者。

5. 安全性与效率

  • Raft 算法通过确保每个任期只有一个领导者、任期编号的递增性、以及日志一致性的检查来维护系统的安全性。
  • 通过随机化的选举超时时间和限制每个任期只能投一票来确保选举的效率。

日志复制

Raft 算法的日志同步是确保分布式系统中数据一致性的关键部分。以下是 Raft 算法日志同步的详细说明：

1. 日志复制的背景

  • 目标：Raft 算法的目标是将日志完整地复制到集群内的所有服务器，这些复制的日志会被状态机所使用。
  • 作用：日志可以保证状态机执行相同的命令，从而实现数据的一致性。

2. 日志同步过程

2.1 角色定义

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

2.2 同步流程

  1. 日志追加（Append）：
    • 当 Leader 收到客户端的请求后，它会将这个请求作为一个 entry 记录到日志中。
    • Leader 会将新 entry 追加到日志的末尾，并为这个 entry 分配一个递增的索引（index）。
  2. 并行复制：
    • Leader 在完成日志追加后，会并行向所有的 Follower 发起 AppendEntries RPC（远程过程调用）。
    • AppendEntries RPC 中包含了要追加的日志条目（entries）以及前一个日志条目的索引（prevLogIndex）和任期（prevLogTerm）。
  3. Follower 响应：
    • Follower 在收到 AppendEntries RPC 后，会检查日志的一致性。
    • 如果 Follower 的日志与 Leader 的日志在 prevLogIndex 位置之前的部分相同，那么 Follower 就会接受新的日志条目并追加到自己的日志中。
    • 如果 Follower 的日志与 Leader 的不一致（例如丢失了某些条目），那么 Follower 会请求 Leader 重新发送缺失的日志条目。
  4. 提交日志：
    • 当 Leader 收到大多数 Follower 对某个日志条目的确认后，它会将这个日志条目标记为已提交（committed）。
    • Leader 随后会通知所有 Follower 该日志条目已提交，并允许它们将已提交的日志应用到状态机中。

3. 安全性保证

  • Raft 算法通过确保在大多数服务器上复制日志并仅在大多数服务器确认后提交日志来确保数据的安全性。
  • 如果 Leader 崩溃或失去联系，新的 Leader 选举过程会确保选出的新 Leader 拥有所有已提交的日志条目。

状态机持久化

Raft 算法的状态机持久化主要关注于在服务器重启或故障后能够恢复并继续之前的状态。这主要通过在每次状态更新时，将关键状态信息保存到非易失性存储（如磁盘）中来实现。以下是 Raft 算法状态机持久化的主要步骤和考虑因素：

  1. 需要持久化的状态：
    • currentTerm：服务器观察到的最新任期。
    • votedFor：在最新任期中，此服务器投赞同票的服务器 ID。
    • log：Raft 日志条目，用于记录所有的操作历史。
  2. 持久化方法：
    • 在 Raft 中，通常会实现一个专门的存储接口（如 Storage 接口），该接口提供了设置（Set）和获取（Get）键值对的方法。这些键值对映射到持久化存储中的状态信息。
    • 在每次状态更新时（例如，在投票、日志提交或日志追加等操作时），服务器都会调用存储接口的 Set 方法，将当前状态保存到非易失性存储中。
    • 当服务器重启或恢复时，它会从持久化存储中读取最新的状态信息，通过调用存储接口的 Get 方法来实现。
  3. 编码与解码：
    • 为了将状态信息保存到磁盘或从磁盘读取，通常需要使用编码和解码技术。在参考文章中，提到了使用 labgob 包进行序列化和反序列化。这种方法允许将复杂的数据结构（如 Raft 对象）转换为字节流，然后保存到磁盘中，并在需要时将其恢复为原始数据结构。
  4. 实现细节：
    • 在 Raft 的实现中，通常会定义一些特定的方法来处理持久化操作。例如，persist() 方法用于将当前状态保存到磁盘，而 readPersist() 方法用于从磁盘读取最新状态。
    • 这些方法内部会调用存储接口的 Set 和 Get 方法，并使用编码和解码技术来处理数据的序列化和反序列化。
  5. 注意事项：
    • 持久化操作可能会涉及磁盘 I/O，这可能会增加系统的延迟和复杂性。因此，在设计 Raft 算法的实现时，需要仔细权衡持久化的频率和性能开销。
    • 另外，由于磁盘故障或数据损坏等原因，持久化存储中的数据可能会丢失或损坏。因此，在 Raft 算法的实现中，还需要考虑数据的备份和恢复机制，以确保系统的高可用性和容错性。

日志压缩

Raft 算法的日志压缩是为了解决随着系统运行时间的增长，日志信息不断累积，导致占用过多存储空间的问题。以下是关于 Raft 算法日志压缩的详细说明：

1. 日志压缩的目的

  • 减少存储需求：随着时间的推移，系统中累积的日志信息会越来越多，这可能会占用大量的存储空间。日志压缩通过删除不再需要的日志信息，释放了这些空间。
  • 加速日志同步：对于新加入集群的节点或日志落后的节点，日志压缩可以减少它们与主节点之间的同步时间，从而提高系统效率。

2. 日志压缩的实现方式

Raft 算法通过创建 ** 快照（Snapshot）** 的方式来实现日志压缩。快照是系统当前状态的一个完整副本，包含了状态机的当前状态以及所有已提交的日志的累积效果。

  • 快照结构：
    • lastIncludedIndex：表明快照中最后一条日志的索引值。
    • lastIncludedTerm：表明快照中最后一条日志所在的任期值。
    • state machine state：复制状态机的当前状态。
  • 快照生成：
    • 每个服务器都可以独立地生成快照。这通常是在检测到日志文件大小超过某个阈值或其他预定义条件时触发的。
    • 快照生成时，服务器会保存状态机的当前状态以及 lastIncludedIndex 和 lastIncludedTerm 等信息。
    • 快照生成完成后，服务器可以删除快照之前的所有日志，因为这些日志的信息已经被包含在快照中了。
  • 快照的发送：
    • 当主节点（Leader）发现某个跟随者（Follower）的日志落后太多时，它会发送一个包含最新快照的 InstallSnapshot RPC 消息给该跟随者。
    • 跟随者接收到快照后，会根据快照的 lastIncludedIndex 和 lastIncludedTerm 等信息来决定如何处理自己的日志。如果跟随者的日志落后或冲突，它会使用快照来替换自己的日志；如果跟随者的日志已经包含了快照中的所有信息，它会保留自己的日志并继续工作。

3. 日志压缩的注意事项

  • 一致性检查：在快照发送和接收过程中，需要进行一致性检查以确保数据的正确性。这通常是通过比较 lastIncludedIndex 和 lastIncludedTerm 等信息来实现的。
  • 内存管理：虽然快照可以释放磁盘空间，但它们在生成和传输过程中可能会占用大量的内存资源。因此，在设计和实现日志压缩机制时，需要仔细考虑内存管理的问题。
  • 容错性：由于网络故障或其他原因，可能会导致快照传输失败或丢失。因此，在设计和实现日志压缩机制时，需要考虑容错性，以确保即使在出现故障的情况下，系统也能够正常工作并恢复数据。
收录于 合集・面试 8
更新于 2025-04-08 
CC BY-NC-SA 4.0
面试 Raft
返回 | 主页
0%