摘要

raft: 比paxos简单的共识算法, 相比paxos, 有什么特殊的点:

  1. 共识问题简化成三个独立的问题: leader election、log replication、safety[logIndex->log唯一且不可变]
  2. 不允许类似paxos的乱序提交
  3. 使用 Randomization 算法简化leader election问题.
  4. 使用term概念代替原子钟的概念

本身, paxos 就存在一些问题: 1. 难以理解 2. 不具备良好的工程实践能力, multi-paxos 缺乏实现细节. Chubby 实现了类似 paxos 的算法, 但是不公开

细节

1. leader选举

  1. raft中有三个角色: leader、candidate、follower, 只有 candidate可以竞选leader, 竞选leader的时候, 竞选特点如下:

    1. 需要得到包括自己在内一半以上的投票
    2. Candidate的term比voter大, 在相同的情况下, candidate的logEntry的sn比voter大

    这里存在问题: 当一个节点被隔离了, 会出现不断投票给自己的情况, 导致term非常大, 隔离的节点重新加入集群后, 会触发集群多次选举, 直到集群中的节点的term和被隔离的节点一样大

  2. raft在leader当选成功后, 会执行下面几个特点和操作:

    1. leader立即发送一个 no-op entry, 保证leader commit index是最新的, 使整个集群快速进入可读状态.
    2. 当follower 发送自身的commit index 比leader大, 会进行删除操作, 删除本地 leader commit index 之后的内容
    3. leader不能提交之前term的entry, 必须当entry已经得到集群节点半数的响应, 才能将之前的entry提交

  3. leader存活期间, 有下面几个特点

    1. 有心跳租约的概念, 心跳租约时间内, 请求不能被处理
    2. 存活期间, leader 与 follower需要通过心跳维持关系
    3. follower 在指定时间内收不到心跳的情况下, 会重新发起选举

2. 内容复制

  1. 写入的执行流程如下:

    1. client -> leader: 客户端请求leader写入kv
    2. leader append 本地日志(commitlog)
    3. leader 并行发送日志给 follower
    4. follower收到日志, 写入本地 commit log, 并 apply 本地的 FSM, 返回成功给 leader
    5. leader收到follower超过半数以上的成功响应, 本地apply 日志到 FSM.

    写入流程中有几个关键的术语:

    • commit log: 提交的日志, 所有的日志都会先写入 commit log.
    • fsm: 有限状态机, 确认达成一致的内容会写入fsm.

    这两者在 follower层基本上顺序执行的, 在 append commit log后立即 apply fsm. 在leader层, append commit log后, 需要并发发送请求给follower, 需要半数以上follower返回成功响应后, 才能写入 fsm.

  2. 读取的执行流程如下:

    1. client -> leader: 客户端请求leader写入kv
    2. leader 通过 lease 检查自己是否是 leader,
    3. 检查是leader的情况下, 检查本地 apply index 和 客户端的 index, apply index大的话, 读取本地的状态机的数据 + apply index返回
    4. 不是leader的情况下, 就请求leader获取最新的 apply index, 和 客户单的index 比较, apply index 大的话, 读取本地的状态机的数据 + apply index 返回

    通过流程发现, 有client index的概念, 这个是server(leader/follower)返回的apply index. 除此之外, server(leader/follower)都是从本地的fsm中返回数据的, 而不像其他的方式那样，follower从leader中获取数据.

3.异常情况考虑

  1. 写入的数据在半数响应后, 还没来得及响应给客户端, 就挂了 在重新leader选举后, 数据依旧保持在 raft中, 但是客户端因为之前没有收到响应, 会认为操作失败, 所以, 客户端必须得重试内容, 不然会出现 客户单认为失败，但是存储层成功的情况 那么, 客户端重试请求, 会导致重复内容存储吗? 不会, client需要给每一个请求添加一个唯一的编号, 服务端保证幂等, 一个编号的请求值处理一次

  2. 是否存在新选举的leader日志是不全的? 以至于leader切换内容丢失? Leader Completeness Property 保证了 leader是有所有提交的信息的, leader刚当选成功, 会发送 no-op entry来保证自己是新的, 如果不是最新的, 会被拒绝掉.

其他:

  1. 三种时间

    广播时间（broadcastTime） « 选举超时时间（electionTimeout） « 平均故障间隔时间（MTBF）

    广播时间指的是从一个服务器并行的发送 RPC请求 给集群中的其他服务器并接收响应的平均时间, 论文中指出, 关闭时间在 0.5ms 到 20ms的范围, 选举时间在 10ms 到 500ms范围.

  2. 日志压缩

    为了避免日志无限增长的问题, 使用快照方式, 将之前的日志和快照删除, 只保留最新的快照

  3. 群成员管理

    通过引入 joint consensus的概念, 实现了过渡期的概念, 只有 拥有c-old+c-new 的server才有可能被选举成leader, 然后c-old+c-new的日志提交后, leader在使用相同的方式提交 c-new的log entry, 避免 c-old 和 c-new的分裂.

但是, etcd/tikv并没有这么做, 他们通过引入 learner 的概念解决, learner 不能进行投票, 只能够同步日志, 当日志能够跟上follower, 可以指定learner提升到 follower.

优化&实现

  1. pingcap raft: 实现了 batch&pipeline leader append、 append log parallelly、Asynchronous Apply、Asynchronous Lease Read
  2. etcd/tikv 使用learner而不是 joint consensus来保证成员更新的可靠性

参考信息:

  • (官网)[https://raft.github.io/]
  • (论文)[https://raft.github.io/raft.pdf]
  • (可视化动图)[http://thesecretlivesofdata.com/raft/]
  • (raft大规模使用)[https://zhuanlan.zhihu.com/p/23872141]