Skip to content

Latest commit

 

History

History
51 lines (37 loc) · 6.31 KB

raft.md

File metadata and controls

51 lines (37 loc) · 6.31 KB

强一致性的共识算法Raft

Raft 是一种通过日志复制来实现的一致性算法。Raft 有几个关键模块:领导人选举、日志复制和安全性,同时它通过更强的一致性来减少算法状态的数量。Raft 算法还允许集群成员的动态变更,它利用大多数原则来保证安全性。

Raft特性

复制状态机与一致性算法

一致性算法是从复制状态机的背景下提出的。在这种方法中,一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。 复制状态机通常都是基于复制日志实现的,每一个日志都按照相同的顺序包含相同的指令,所以每一个状态机都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列。

  • 一致性算法通常含有以下特性:
    • 安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
    • 可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信,就可以保证可用。因此,一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
    • 不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟在可能只有在最坏情况下才会导致可用性问题。
    • 通常情况下,一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

领导人选举

  • leader通过心跳来保证自己仍然是集群的领导者, follower也可以通过心跳来判断leader提交的日志点
  • 在等待投票的时候,可能会收到了新leader的心跳或者append请求。
  • 选票被瓜分导致没有人获得绝大多数投票时,通过随机超时等待来使得其中一个人先发起投票
  • 预选举
    • 假设某个节点因为网路抖动而与leader失去了联系,那么如果他这个时候发起选举,那么leader会转变为follower, 但是如果他并没有包含最新的日志,那么这个节点并不会赢得选举,只是干扰了leader的正常服务。
    • 在每次选举正式开始前,先进行预投票。发起投票的人以更大的term发起选举,但是所有接受投票的人都不会更改自己的任期。并且倘若接受者仍然和leader保持心跳,他就会拒绝掉这次预选举。
    • leader不会接受其他节点发起的预选举投票。除非他已经失去了和大多数节点的连接。

日志复制

  • 为了保证日志连续性,leader每次发送entries时, 会把该次日志数据的前一条日志的index与term也一并发过去,follower会校验自己日志相同index处的term是否一致,倘若不一致,则拒绝掉这次请求。
  • leader在发送日志时会附带自己已经提交的最大日志Index,如果follower接受此次Append请求(接受条件见上一条),那么follower会将leader提交了的日志(并且本节点也拥有)全部提交。
  • follower在每次接受leader的Append请求时,会返回自己和leader匹配上的最长日志地址。leader以此来判断自己的每一条日志是否被成功Append到了绝大多数节点,并决定该条日志是否应该被提交。
  • figure 8:
    • 假设集群有5个节点,在任期2,如果leader S1已经复制了日志到S2,然后在时间点1崩溃,时间点2时,S5凭借S3、S4、S5的投票成为了leader,并且给自己添加了一条任期3的日志,然后时间点3时,S5崩溃并且S1重新成为leader(任期4),如果S1继续尝试发送自己上一个任期的日志条目到S3的话,那么S3接受了S1的任期2的日志后,S1就会提交这条日志,之后S1再次崩溃,由于S5此时有一条任期3的日志,那么S5会赢得选举,并且将S2、S3的任期2的日志覆盖掉。注意!此时任期2的这条日志已经被S1提交过了,覆盖已提交的日志是违反线性一致性原则的。
    • 解决办法: Raft不会让leader直接提交上一个任期的日志,而是让leader在选举成功后立刻给自己添加一条空的条目,那么之后leader向其他follower同步日志时,上一个任期的日志一定会和这条空的日志一起提交。因此S2获得的最新日志不是任期2的条目,而是任期4的这条空条目,所以S2和S3都会阻止S5获得选举。

日志压缩

  • 对于增长过块的日志, 可以通过对状态机进行快照,然后把快照对应的日志位置之前的日志全部清空。(对rocksdb这样自带WAL的状态机而言,快照就是他的索引文件与日志文件)
  • 记录快照对应的日志索引index与该位置的任期term
  • 所有的节点都可以自由创建快照,而不必保持一致。因为快照中的数据必定是已经被提交的日志,所以其对应的日志条目也不会被覆盖。
  • 对于落后太多的follower, 领导人先发送自己的快照数据,再同步数据。

客户端交互

  • 客户端与服务端交互时,由于网络故障或者重传,有可能导致客户端向服务端发送的一条命令已经被Raft提交了,但是客户端认为这次请求超时或者意外中断了,于是尝试重新发送,同一条命令因此被提交了两次,所以Raft需要客户端对与每一条指令都赋予唯一的序列号, 并且在状态机中持久化,状态机通过该序列号来保证每一条命令被执行一次。
  • 只读请求如果直接处理的话,会有返回脏数据的风险,即当只读请求提交时,该Leader已被废除,并且新leader已经提交了新的日志。
    • 最简单的办法是将只读请求也当作一条Raft日志做提交,当应用该条日志时,读取数据并返回给客户端。
    • leader在处理每个读请求前,向所有follower发送一条心跳日志以确认自己仍然没有被废除。