My Raft Log

Posted on | Edited on | In , | Comments:

参考

Overview

  • 共识是多个参与者针对某一件事达成完全一致。已达成一致的结论，不可推翻（领导人绝不删除或覆盖自己的日志，only append，并且领导人的日志绝对正确）
  • 复制状态机通常基于复制日志实现。因为每个状态机都是确定的，所以每一次执行操作都产生相同的状态和相同的序列。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成一个高可靠的状态机。保持日志的相同就是共识算法的工作了
  • Raft可以提供以下特性
    • 安全：在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确
    • 可用：大多数机器work那么该集群就work，宕机的节点当有稳定的存储的时候可以从状态中恢复回来并重新加入集群
    • 不依赖时序来保证一致性: 物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题
    • 集群的响应速度取决于最快的大部分机器
  • 作用
    • 在低可靠的普通x86服务器上构建一个高可靠的整体，使得即使有少部分机器宕机，集群依然可用（当然选举的过程中集群是不可用的）

      普通服务器具有良好的性价比，因此在互联网等行业得到了广泛的应用。但普通服务器也不得不面对2%-4%的年故障率([1])，于是必须高可用的传统数据库只得很悲催地使用性价比低得可怜的高可靠服务器。分布式一致性协议（distributed consensus protocol）是迄今为止最有效的解决服务器不可靠问题的途径，因为它使得一组服务器形成一个相互协同的系统，从而当其中部分服务器故障后，整个系统也能够继续工作(Ref from)

    • 通过支持follower read使得对于读请求可以负载均衡

任期

  • 任期在 Raft 算法中充当逻辑时钟的作用，这会允许服务器节点查明一些过期的信息比如陈旧的领导者
  • 任期号是单调递增的： 新leader的任期号一定比旧的任期号大。旧leader得到有大部分server的支持，所以大部分server上持久化的leader任期号必然等于旧leader的，所以一个跟旧leader任期号相同或更小的server必然不可能当选
  • 如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值
  • 如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求

选举

  • 最开始启动时，server以follower的身份启动
  • 如果超时没有收到心跳（选举超时，通常是100ms~500ms，每台服务器都会随机的计算下次超时的间隔时间，这个时间间隔在[T, 2T]之间。T代表着选举超时的时间，即服务器可能出现超时的最短时间）。那么进入选举过程
  • 通过以下手段使得不会无限分票
    • 广播时间（广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间）必须比选举超时时间小一个量级,这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态
    • 随机化超时时间
  • 拉票RPC包括：候选人的任期号、候选人的id、候选人的最后日志条目的索引值、候选人最后日志条目的任期号
    • 一个问题，索引值和任期号相同，那么日志内容就一定相同吗？
    • 我认为
      • 因为数据都从领导人流向其他服务器，所以某服务器在该位置上有这样一条这个任期号的日志，必然是因为有这个任期号的leader传给它的，而领导人绝不删除或覆盖自己的日志，所以日志内容是确定的
      • 如果出现该leader还没有comment该日志就下台，也不会出问题，因为新的leader的任期号必然比旧leader的大
  • 投票过程
    • 每一个服务器最多会对一个任期号投出一张选票，按照先来先服务的原则
    • RPC 中包含了候选人的日志信息,然后投票人会拒绝掉那些日志没有自己新的投票请求。（“新的”定义：(lastterm_me < lastterm_ca || (lastterm_me == lastterm_ca && lastindex_me <= lastindex_ca))）
    • 拉票时，通过日志的完整、新旧程度来判断是否投票给某候选人，所以即使某服务器已收到term-4的leader发来的term-2的log，其还是会将票投给term-3的候选人（这样导致了“新leader复制旧日志使之分布到大多数node上时依然不能提交”）
  • 安全：保证某任期一定有一个leader，方法是保证某次投票只投给一人，所以需要server持久化自己的投票信息，保证不重复投票
  • 可用：保证一定会选出leader。通过随机化超时时间来保证
  • Raft使用投票的方式来阻止一个候选人赢得选举除非这个候选人包含了所有已经提交的日志条目。候选人为了赢得选举必须联系集群中的大部分节点,这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果候选人的日志至少和大多数的服务器节点一样新, 那么他一定持有了所有已经提交的日志条目

可用性

  • 选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行
  • 当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用

安全性

  • 如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令
  • 覆盖日志的风险
    • 如果一个领导人在提交日志条目之前崩溃了，未来后续的领导人会继续尝试复制这条日志记录
    • 当领导人复制之前任期里的日志时,Raft会为所有日志保留原始的任期号
    • 所以如果某条前任的日志被当前leader复制到大多数机器上，另外的机器（没有这条日志）依然有可能被选为leader，因为该server的日志可以被老日志新（虽然比当前leader老）（论文中的图8）
    • 解决方法：一个领导人不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交了。一旦当前任期的日志条目以这种方式被提交,那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，领导人可以安全的知道一个老的日志条目是否已经被提交(例如，该条目是否存储到所有服务器上）

Raft读取

  • Ref from
  • 方法一：就像写入一样，走一遍raft log，这个log commit、apply后就可能拿到最新的值了
  • 方法二：ReadIndex Read
    • 将当前⾃⼰的 commit index 记录到⼀个 local 变量 ReadIndex ⾥⾯
      • 我的想法：对于用户来说，只能期待写入后的读取读到“刚刚写入的值”，而不能期待读到“读取时写入的值”。所以即使保存该commit index后有新的写入到来，commit index增大，依然没有问题（TODO，待求证）
    • 向其他节点发起⼀次 heartbeat，如果⼤多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在⾃⼰仍然是 leader
    • Leader 等待⾃⼰的状态机执⾏，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了
    • Leader 执⾏ read 请求，将结果返回给 client
    • corner case
      • leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index
      • Raft要求当 leader 选举成功之后，⾸先提交⼀个 no-op 的 entry，保证leader 的 commit index 成为最新的
      • 因为 leader 在选举成功之后，term ⼀定会增加，在处理 ReadIndex 的时候，如果当前最新的 commit log 的 term 还没到新的 term，就会⼀直等待跟新的 term ⼀致，也就是 no-op entry 提交之后，才可以对外处理ReadIndex（幸好有一个no-op的写入，不然这个读就得等到有新的写入完成才能读取成功）
  • 方法三：Lease Read
    • leader 发送 heartbeat 的时候，会⾸先记录⼀个时间点 start，当系统⼤部分节点都回复了 heartbeat response，那么我们就可以认为 leader 的 lease 有效期可以到 start + election timeout / clock drift bound 这个时间点
    • 主要是在于 Raft 的选举机制，因为 follower 会在⾄少election timeout 的时间之后，才会重新发⽣选举，所以下⼀个 leader 选出来的时间⼀定可以保证⼤于 start + election timeout / clock drift bound
    • 面临风险：CPU时间不准从而出错

需要可靠硬盘

  • 需要可靠保存任期号
  • 保证某次选举时只将票投给一个server（如果没有可靠保存任期号，则有可能在选举过程中宕机又恢复的server会两次投票——一次宕机前，一次恢复后）
  • 需要可靠保存日志
  • 我认为，“需要可靠硬盘”与“硬盘可以损坏”并不冲突，因为我们在硬盘下线后上线时，可以使用checksum等工具，来判定硬盘是否损坏，如果损坏，那么不让其上线即可

优化

  • 当附加日志RPC的请求被拒绝的时候（因为一致性检查失败），跟随者可以包含冲突的条目的任期号和自己存储的那个任期的最早的索引地址。借助这些信息,领导人可以减小 nextIndex越过所有那个任期冲突的所有日志条目;这样就变成每个任期需要一次附加条目 RPC 而不是每个条目一次
  • follower read （TODO）

具体情况分析

  • 某server一直收不到回复，从而假定出现分票，从而新开一个任期来选举，而他刚开始选举时，就收到上一次投票时的获胜者的心跳，会发生什么？
    • 因为对于心跳RPC，如果term < currentTerm就返回 false，并且心跳RPC的返回值有这个follower的当前任期号，所以leader会成为follower

      如果接收到的RPC请求或响应中，任期号T>currentTerm，那么就令currentTerm等于T，并切换状态为跟随者

    • 只是这里有一个问题，候选人收到心跳RPC也是按照follower那样回复吗，论文上的表述是“接收者实现:”，而不是“follower实现”（第5节开头时关于附加日志RPC的介绍那里）
  • 如何获得全局有效的任期号？这是个坏的问题。

问题

  • 如果心跳收不到响应怎么办？论文中没有提到