分布式基础

Raft算法 选举制 心跳机制 日志同步

分布式系统 Raft协议 选举制 心跳机制 日志同步

分布式本质上需要多台物理隔离的计算机。

如果可以在一台计算机上解决问题，那么不应当使用分布式系统，因为这会让问题变得复杂。

我们使用分布式系统的主要意愿

  • 高性能计算

  • 高可用 —— 高容错，既是一台服务器不可用，也不会导致服务瘫痪

  • 更加安全 —— 因不信任某些代码，故分散运行以限制出错域。

  • 在一些情景中，服务器之间天然就是物理隔离的

分布式系统面临的挑战主要包括：

  1. 并发编程与复杂交互：系统中众多部分并发执行，引发并发编程问题，以及时间依赖的复杂性（如同步与异步），使得系统难以管理。

  2. 意想不到的故障：由于分布式系统涉及多台计算机和网络，相比单一计算机，更容易遭遇局部错误，如部分组件运行而其他停止，或网络中断，增加了系统的复杂性和不稳定性。

  3. 性能优化难题：设计分布式系统的初衷常是为了提升性能，如利用大量计算机或磁盘。然而，实现预期性能并非易事，存在诸多挑战，需要精心设计以确保系统能达到预期效能。

Raft协议

Raft是一种用于管理复制日志的共识算法，专为分布式系统设计。旨在多个节点之间达成一致性。它提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。

  1. 在非拜占庭条件下保证共识的一致性：
  • 非拜占庭条件：这是指在一个可信的网络环境中，所有与您通信的节点提供的信息都是真实且可靠的，不存在欺骗行为。这种条件下，共识算法能够确保所有节点对某个状态或操作达成完全一致。
  • 一致性：在分布式系统中，一致性指的是所有节点对某个数据的值或某个操作的结果具有相同的认知。
  1. 在多数节点存活时，保持可用性：
  • 多数节点存活：这里的“多数”指的是配置文件中列出的所有节点中的超过半数。这是确保系统能够继续运行并达成共识的最小节点数量。
  • 可用性：在分布式系统中，可用性指的是系统能够在需要时提供服务。当多数节点存活时，共识算法能够确保系统继续运行并处理请求，从而保持可用性。
  1. 不依赖于绝对时间：
  • 绝对时间问题：在分布式系统中，由于节点可能位于不同的地理位置，且网络延迟和报文丢失是常见现象，因此依赖绝对时间可能会导致问题。例如，如果两个节点的时间不同步，它们可能会对同一个操作的时间戳产生分歧。
  • 逻辑时钟：为了避免这个问题，共识算法通常不依赖绝对时间，而是使用逻辑时钟来替代。在Raft算法中，这个逻辑时钟被称为“任期”（Term），它用于确保节点在选举和日志复制过程中保持同步。
  1. 在多数节点一致后就返回结果，而不会受到个别慢节点的影响：
  • 多数节点一致：当超过半数的节点对某个操作或状态达成一致时，共识算法就认为整个集群已经同意了该操作或状态。这是因为在多数节点存活且可信的条件下，任何尝试篡改或破坏共识的行为都会被多数节点的正确行为所抵消。
  • 不受慢节点影响：在分布式系统中，个别节点可能会因为网络延迟、硬件故障或其他原因而变慢或停止响应。共识算法通过确保在多数节点一致后就返回结果，从而避免了因个别慢节点而导致的系统性能下降或僵局情况。对于Raft算法来说，这意味着一旦多数节点将某个操作记录到它们的日志中（即形成一个日志条目），该操作就被认为是已被整个集群所接受。

Raft共识算法组成

一、状态机

  • Raft的上层应用，可以是键值数据库等。
  • 状态机根据日志中的命令进行操作，以保持节点间的一致性。

二、日志相关概念

  1. 日志（log）与条目（entry）
  • Raft将外部命令以日志形式保存。
  • 日志可以看作一个连续的数组，其中的每一个元素称为一个条目（entry）。
  1. 提交日志（commit）
  • Raft保存日志后，需要经过复制同步过程，才能将日志“应用”到上层状态机。
  • 这个“应用”日志到状态机的过程称为提交。

三、节点身份

  • Follower：集群中的普通节点，响应来自Leader的请求，并投票给Candidate。

  • Candidate（临时角色）：在选举过程中，节点可能从Follower转变为Candidate，尝试成为Leader。

    • 为了防止在同一时间有太多的follower转变为candidate导致一直无法选出leader， Raft 采用了随机选举超时（randomized election timeouts）的机制， 每一个candidate 在发起选举后，都会随机化一个新的选举超时时间（times out），这意味着不同的节点会在不同的时间点发起选举，从而减少了多个节点同时发起选举的可能性。

      • 当一个节点转变为candidate并发起选举时，它会发送RequestVoteRPC请求给其他节点。
      • 在这个请求中，candidate会带上它最后一个日志entry的信息。
      • 其他节点收到请求后，会将自己的日志与candidate的日志进行比较。
      • 如果发现自己的日志比candidate的日志更新（即“不旧于”candidate的日志），则会拒绝投票给该candidate。

  • Leader：负责处理客户端请求、管理日志复制以及向Follower发送心跳的节点，是Raft集群中的核心节点，负责协调和管理集群的运作。

    • 成为leader的条件：它的日志必须不旧于集群中其他节点的日志，即它的日志要么与其他节点的日志一样新，要么比其他节点的日志更新。这样，当该节点成为leader后，它能够确保包含所有已committed的日志，从而维护集群的一致性和安全性。

    • 判断日志老旧的方法：

      • 判断日志老旧需要比较两个节点最新日志entry的term和对应的index。
      • 如果两个节点最新日志entry的term不同，那么term大的日志更新。
      • 如果term相同，那么index大的日志更新。

Raft状态转换

四、任期（term）

  • 也称逻辑时钟，用于标识不同的选举周期。
  • 每个任期都有一个唯一的编号，用于区分不同的任期。

五、选举

  • Follower节点在特定条件下会转变为Candidate，并发起选举以成为Leader。
  • 选举过程中，节点会投票给拥有最新日志的Candidate。

六、日志的任期

  • 在日志提交时，会记录该日志是在哪个任期（term）内记录的。
  • 这有助于后续进行日志的新旧比较和一致性维护。

七、心跳与日志同步

  • Leader会定期向Follower发送心跳（AppendEntryRPC）。
  • 心跳（AppendEntry）不仅用于告诉Follower自己的存在，还携带日志信息以进行同步。
    • 如果follower在一段时间内没有接收leader发送的AppendEntry，那么follower就会认为当前的leader 出现故障，从而发起选举。携带的日志信息携带了leader的index和term等关键信息以便follower对比确认follower自己或者leader是否过期。

Raft是一个强Leader 模型，可以粗暴理解成Leader负责统领follower，如果Leader出现故障，那么整个集群都会对外停止服务，直到选举出下一个Leader。如果follower出现故障（数量占少部分），整个集群依然可以运行。

选举制

一、Term（任期）的定义

  • Raft使用Term作为内部逻辑时钟，用于比较日志、身份、心跳的新旧，而非依赖绝对时间。
  • Term与Leader身份紧密相关，即某个节点是Leader更准确的说法是它是某个Term的Leader。
  • Term以连续数字表示，每次follower发起选举时，Term会加1。

二、选举过程与Term的变化

  1. 胜利当选：
  • 当超过半数的节点认为某个Candidate有资格成为Leader时，该Candidate胜利当选。
  1. 选举失败：
  • 如果没有任何Candidate获得超半数的选票，选举超时后会开始新的Term（Term递增）的选举。
    • 这是因为一个Term内只能有一位Leader，但多个节点可能同时发起选举，导致存在多位Candidate。

三、Raft如何保证一个Term只有一个Leader

  • Candidate变成Leader的条件是获得超过半数的选票。
  • 一个节点在一个Term内只能投一次票，因此不可能有两个节点同时获得超过半数的选票。
  • 这确保了每个Term内只有一个Leader。

四、故障恢复与Term的更新

  • 发生故障时，节点可能无法知道当前最新的Term。
  • 故障恢复后，节点可以通过其他节点发送的心跳中的Term信息来查明过期信息。

五、节点如何处理Term不一致的情况

  • 当发现自己的Term小于其他节点的Term时：
    • Leader和Candidate会退回follower身份，并更新Term到较大的那个Term。
    • Follower会更新Term信息到较大的那个Term。
    • 这是因为较小的Term意味着，整个Raft集群可能已经有了新的leader、提交了新的日志，当前自己可能发生了网络隔离等故障，并且日志缺失。退回follower身份并更新Term可以确保节点与集群保持一致。
  • 当发现自己的Term大于其他节点的Term时：
    • 节点会忽略该消息中携带的其他信息。
    • 这是因为较大的Term意味着节点的信息是最新的，无需更新或改变。

安全性

  1. Election Safety（选举安全性）：
  • 每个 term 最多只会有一个 leader：这意味着在Raft算法中，任何给定的时间点上，一个集群中只能有一个节点被选为leader。这是通过选举过程确保的，其中节点会投票给拥有最新日志条目的候选人。
  • 集群同时最多只会有一个可以读写的 leader：即使网络发生分区，导致多个子集群尝试进行选举，Raft的设计也确保了只有一个分区能够成功选举出leader，并且这个leader拥有集群中的大多数节点支持，从而保证了写操作的一致性和安全性。
  1. Leader Append-Only（领导者日志只增）：
  • 这意味着leader节点上的日志只能以追加的方式进行更新，即新的日志条目总是被添加到现有日志的末尾。这种设计防止了日志条目被篡改或删除，从而保证了日志的完整性和一致性。
  1. Log Matching（日志匹配）：
  • 如果两个节点的日志中有两个 entry 有相同的 index 和 term，那么它们就是相同的 entry：这是Raft算法中的一个重要性质，它确保了在不同节点上的日志条目在相同位置和相同任期内是一致的。
  • 在运行过程中，leader会定期检查follower的日志，以确保它们与leader的日志匹配。如果发现不匹配，leader会发送自己的日志条目去覆盖follower上对应的条目，以恢复日志的一致性。
  1. Leader Completeness（领导者日志完整性）：
  • 一旦一个操作被提交了（即被大多数节点写入到日志中），那么在之后的任期内，该操作都会存在于日志中。这保证了已提交的操作不会被遗忘或丢失，从而确保了数据的持久性和可靠性。
  1. State Machine Safety（状态机一致性）：
  • 一旦一个节点应用了某个 index 的 entry 到状态机（即执行了该操作），那么其他所有节点在应用到相同 index 的操作时，必须保证这些操作是一致的。这是通过确保所有节点的日志在相同位置上包含相同的条目来实现的。

日志同步

日志同步与心跳

在Raft共识算法中，日志同步和心跳是两个关键的操作，它们被巧妙地结合在一个RPC函数（AppendEntryRPC）中实现。这种设计的原因在于，心跳RPC可以被视为一种特殊的日志同步RPC，它不携带具体的日志内容。

1. 日志同步

  • 目的：确保所有follower节点的日志与leader节点的日志保持一致。

  • 过程：

    1. Leader会向follower发送AppendEntryRPC请求，该请求中可能包含日志条目（entry）。
    2. Follower接收到请求后，会根据自己的日志情况与leader的日志进行比较。
    3. 如果follower的日志与leader的日志完全匹配，那么后续的AppendEntryRPC请求中就不需要再携带日志条目了，只发送心跳信息以维持leader与follower之间的联系。
    4. 如果follower的日志与leader的日志不匹配，leader会逐步发送之前的日志条目，从最后一个开始，直到找到一个匹配的日志条目为止。

2. 为什么不让follower直接拷贝leader的日志？

  • 如果让follower直接拷贝leader的全部日志，会携带大量的无效日志，因为follower可能已经拥有部分与leader相同的日志条目。
  • Raft算法采用了一种更高效的方法，即只同步不匹配的日志条目，从而减少了数据传输量和同步时间。

3. Leader如何知道follower的日志是否与自己完全匹配？

  • Leader在发送AppendEntryRPC请求时，会携带上日志条目的index和term信息。
  • Follower接收到请求后，会根据自己的日志情况与leader发送的日志条目进行比较。
  • 通过比较最后一个日志条目的index和term，follower可以判断自己的日志是否与leader匹配。
    •     Raft日志具有两个特点：
      1. 如果两个节点的日志中有两个entry拥有相同的index和term，那么它们一定记录了相同的内容/操作。
      2. 如果两个节点的日志中有两个entry拥有相同的index和term，那么它们前面的日志entry也相同。
      3. 基于这两个特点，follower可以通过比较接收到的日志条目的index和term来判断自己的日志是否与leader匹配。

5. 如何处理不匹配的日志？

  • 如果follower的日志与leader的日志不匹配，follower会拒绝leader的AppendEntryRPC请求。
  • Leader发现follower拒绝请求后，就知道存在不匹配的日志条目。
  • Leader会逐步发送之前的日志条目，从最后一个开始，直到找到一个匹配的日志条目为止。
  • 在这个过程中，leader会覆盖follower上不匹配的日志条目，从而确保所有节点的日志最终保持一致。

6. 逐个匹配太慢？

  • 可以设计匹配时候的越过日志条目的数量来进行优化。

快照（Snapshot）

快照是什么？

快照是系统状态在某个特定时间点的完整记录，它以紧凑的形式存储了恢复系统到该状态所需的所有必要信息。

  • 在分布式系统中，如使用Raft协议的系统，日志是记录系统状态变更历史的关键组件。
  • 然而，随着系统的运行，日志可能会变得非常庞大，影响系统性能和存储效率。此时，引入快照机制可以有效压缩日志。

何时创建快照？

  1. 日志大小限制：当日志增长到一定大小时，为了避免其无限增长，系统会触发快照的创建。这样可以有效限制日志的存储空间占用。

  2. 系统空闲时间：在系统相对空闲，即没有新的日志条目被频繁追加时，也是创建快照的好时机。这可以减少对系统正常操作的影响。

快照的传输

快照的传输主要涉及两个层面：

  1. Raft上层（假设为kv数据库）与Raft节点之间：

  • 当需要创建快照时，kv数据库会首先生成当前状态的快照，并将其打包成适合传输的格式。

  • 打包好的快照随后被传递给Raft节点。Raft节点在接收到快照后，会根据快照内容更新其内部状态，并删除或截断与快照内容重复的日志条目，以避免数据冗余。

  1. 不同Raft节点之间：

  • 在Raft集群中，leader节点负责日志的复制和同步。当leader节点已经将某个日志及其之前的内容转化为快照时，对于后续需要同步这些内容的follower节点，leader将直接发送快照而不是逐个发送日志条目。

  • 通过快照同步，follower节点可以快速达到与leader节点一致的状态，从而提高集群的一致性和恢复速度。

分布式基础
https://weihehe.top/2024/09/13/MapReduce/
作者
weihehe
发布于
2024年9月13日
许可协议