Raft 算法分析

2021-01-26 14:56:04 浏览数 (1)
  • 为什么需要 Raft？
  • Raft 是什么？
  • Raft 的目标
  • 前置条件：复制状态机
  • Raft 基础
  • Leader 选举（选举安全特性）
  • 日志复制（Leader只附加、日志匹配）
  • 安全
  • 学习资料
  • 使用 Raft 的应用？
  • 扩展：ZooKeeper ZAB 协议
  • 扩展：ZooKeeper 是什么？

为什么需要 Raft？

  • 要提高系统的容错率，需要分布式系统
  • 分布式系统有多个实例，对于给定的一组操作，需要协议让所有实例达成一致（分布式一致性）
  • Paxos 是分布式一致性协议的标准，但难以理解、实现
  • Raft 提供了和 Paxos 算法相同的功能，但更好理解、构建实际的系统

Raft 是什么？

  • Replicated And Fault Tolerant，复制和容错
  • 管理复制日志的一致性算法

Raft 的目标

  • 简单易理解
  • 提供完整的实现系统，减少开发者的工作量
  • 保证所有条件下都是安全的，在大部分情况下是可用的
  • 常用操作是高效的

前置条件：复制状态机

  • Raft 相当于复制状态机中的“一致性模块”
  • 一致性模块（Consensus Module）：管理来自客户端的指令，接入 log
  • 日志（Log）
  • 状态机（State Machine）：执行日志的指令，得到 Server 状态

Raft 基础

  • 节点状态：
    • Leader（领导者）：系统只有一个节点处是 Leader，处理所有客户端的请求并同步给 Follower
    • Follower（跟随者）：只响应其他服务器（Leader、Candidate）的请求
    • Candidate（候选者）：在选举领导的时候出现
  • term（任期）：
    • 一段选举的任期（选举开始 正常工作）
    • term 号自动 1
    • 如果选票均分，则该 term 直接结束，进入下一个 term
    • Raft 中的「逻辑时钟」，可发现过期信息，规则：
      • 每个节点会存储当前 term 号，term 编号单调递增
      • 节点间通信，交换 term 号
      • （1）节点当前 term 号 < 他人 term 号，更新 term 号
      • （2）节点当前 term 号 > 他人 term 号，拒绝请求
      • （3）Candidate、Leader 发现自己的 term < 他人 term，立即变成 Follower
  • 节点通信：使用 RPC
    • 请求投票（RequestVote） RPCs：选举阶段，Candidate 节点发送给他人
    • 附加条目（AppendEntries）RPCs：非选举阶段，Leader 发给所有节点，复制日志 心跳
  • 特性（Raft 保证在任何时候都成立）
    • 选举安全：对一个给定的 term 号，最多选举出一个 Leader
    • Leader 只附加原则：Leader 不会删除、覆盖自己的日志，只会增加
    • 日志匹配：若两个日志在相同索引位置的日志的 term 号相同，则日志从头到该索引位置全部相同
    • Leader 完整特性：选举出的 Leader，会包含所有已提交的日志
    • 状态机安全特性：Leader 已经将给定的索引值位置的日志条目应用到状态机，其他任何服务器都已执行

Leader 选举（选举安全特性）

  • Raft 使用心跳机制触发 Leader 选举
    • 集群存在 Leader，Leader 节点周期性发心跳包
    • 一个 Follower 没有收到任何消息（固定区间随机的时间），发起选举
  • 集群启动时，所有节点都处于 Follower 状态
  • 节点到达超时时间后，会进入 Candidate 状态，增加自己的 term 号，发送请求投票给自己
  • Candidate 状态机
    • 节点得票最多的，变成 Leader
    • 收到来自其他节点的“声明自己是 Leader”的请求
    • 一段时间后，没有获得多数票，也没有收到其他节点的 Leader 通知（平分选票）
  • 避免选举的平分选票：随机选举超时时间
    • 每个节点随机选择选举超时时间，到达时间后成为 Candidate
    • 大多数情况下，只有一个节点率先进入 Candidate

日志复制（Leader只附加、日志匹配）

  • Leader 会接收客户端的请求，请求指令作为一个“日志条目”添加到日志中
  • 向所有 Follower 发送附加条目 RPC，让他们复制这个日志条目
  • 得到大多数节点回复后，Leader 会把日志写入复制状态机，持久化，把执行结果返回给客户端
  • 日志非安全的；进入状态机中是安全的（已提交），最终会被所有可用的状态机执行。

index = 7 的日志已经被大多数节点复制，状态为已提交。

安全

  • 选举限制（Leader 完整性）：每次选举出来的 Leader，必须包含所有已提交的日志
    • 只有已经被大部分节点复制的日志，才会变成“已提交”
    • 一个 Candidate 必须得到大部分节点投票，才能变成 Leader
    • 投票时，节点不会把票投给没有自己的日志新的 Candidate
  • Follower 或 Candidate 崩溃：无限重试
  • 超时和可用性：broadcastTime（广播时间）<< electionTimeout（选举超时时间）<< MTBF（平均故障间隔时间)

学习资料

  • 生动形象的网站：http://thesecretlivesofdata.com/raft/
  • 论文：https://raft.github.io/raft.pdf

使用 Raft 的应用？

  • 服务发现框架：consul、etcd
  • 日志：RocketMQ
  • 数据存储：Tidb、k8s

扩展：ZooKeeper ZAB 协议

  • 支持崩溃恢复的原子广播协议：ZooKeeper Atomic Broadcast protocol
  • ZooKeeper 适合读多写少的场景，客户端随机连到 ZK 集群的一个节点
    • 从当前节点读
    • 写入到 leader，leader 广播事务，半数节点成功才会被提交
  • 整体流程类似于 Raft，只是细节和实现的区别

扩展：ZooKeeper 是什么？

官方定义: A Distributed Coordination Service for Distributed Applications。本质：基于内存的 KV 系统，以 path 为 key。

raft zookeeper rpc

0 人点赞