ReZero's Utopia.

distributed algorithm

Word count: 2.6kReading time: 10 min
2021/11/13 Share

Paxos

basic paxos

proposer: 发起请求的人,提议一个值,用于投票表决

acceptor:对每个提议的值进行投票

learner:被告知投票结果,接受达成共识的值。一般来说,学习者是数据备份节点,比如【Master-Slave】模型中的 Slave,被动地接受数据,容灾备份。

stage

prepare

客户端发送准备请求,节点接受提案号,并作出响应【尚无提案】,承诺不接受比当前节点获得提案号小的提案号。如果接收到了小于当前节点提案号的提案,那么节点将不接受并且不做响应。

Accept

客户端收到大多数节点的准备响应后发送接收请求,这时会提交提案号和提案值,如果客户端接收的准备响应为【尚无提案】,那么会将自己的提案值提交给节点。节点接收时,按准备阶段接收的小提案号的提案请求会被拒绝,大于等于的会被接受达成共识。

如果集群中有学习者,当接受者通过提案就会通知所有学习者。学习者发现大多数接收者通过了某个提案就会学习(接受)该提案的值。

Acceptor 保证三个承诺,具体来说:如果准备请求的提案编号,小于等于接受者已经响应的准备请求的提案编号,那么接受者将承诺不响应这个准备请求;
如果接受请求中的提案的提案编号,小于接受者已经响应的准备请求的提案编号,那么接受者将承诺不通过这个提案;
如果接受者之前有通过提案,那么接受者将承诺,会在准备请求的响应中,包含已经通过的最大编号的提案信息。

basic paxos 能容忍一半以内的节点过账

multi-paxos

review

basic paxos 只能就单个值达成共识,一旦遇到为一系列值实现共识时就不管用了。

Multi-Paxos 是一种思想,不是算法。而Multi-Paxos 算法是一个统称,它是指基于 Multi-Paxos 思想,通过多个 Basic Paxos实例实现一系列值的共识的算法(比如 Chubby Multi-Paxos 实现、Raft 算法等)。

problem

如果多个提议者同时提交提案,可能出现因为提案冲突,在准备阶段没有提议者接收到大多数准备响应,协商失败,需要重新协商。你想象一下,一个 5 节点的集群,如果 3个节点作为提议者同时提案,就可能发生因为没有提议者接收大多数响应(比如 1 个提议者接收到 1 个准备响应,另外 2 个提议者分别接收到 2 个准备响应)而准备失败,需要重新协商。

2轮的 rpc 消耗较大,延迟高,不建议

leader

引入领导者,让领导者作为唯一的提议者,这样不存在多个提议者提议自然也就没有冲突了。

客户端【A,B,C】 <-> 【single leader】 <-> 节点【I, II】

optimize

当领导者处于稳定状态时,省掉准备阶段,直接进入接受阶段。

Chubby 的 Multi-Paxos 实现
  1. 引入了 leader

  2. leader 是通过执行 basic paxos 投票选举产生的,并且运行过程中主节点通过续租来延长 租期(Lease)。实际场景中可能几天内都是同一个节点作为leader,leader故障后其他节点会选举新的leader,即leader一直存在且唯一。

  3. 实现了优化:稳定态省掉准备阶段

    1. 稳定态:领导者节点上,序列中的命令是最新的,不再需要通过准备请求来发现之前被大多数节点通过的 提案,领导者可以独立指定提案中的值。
    2. 准备阶段的意义,是发现接受者节点上,已经通过的提案的值。如果在所有接受者节点上,都没有已经通过的提案了,这时,领导者就可以自己指定提案的值了,那么,准备阶 段就没有意义了,也就是可以省掉了。
  4. 实现了成员变更,保证节点变更时集群平稳运行。

  5. 为了实现强一致性,读操作也只能在主节点上执行。

Raft

从本质上说,Raft 算法是通过 [一切以领导者为准] 的方式,实现 [一系列值] 的共识和各节点日志的一致

role which also called server state

  • Follower: accept and process message from leader, and election itself as candidate when the heartbeat to leader timeout.
  • Candidate: send request vote(rpc message) to other nodes. It will be promoted to leader if only it won majority votes.
  • Leader:1. process write request 2. manage log copy 3. restrict them from initiating new elections by sending heartbeats

tips: Raft use strong leader model, only one leader can be existed.

跟随者:就相当于普通群众,默默地接收和处理来自领导者的消息,当等待领导者心跳 信息超时的时候,就主动站出来,推荐自己当候选人
候选人:候选人将向其他节点发送请求投票(RequestVote)RPC 消息,通知其他节点来投票,如果赢得了大多数选票,就晋升当领导者
领导者:蛮不讲理的霸道总裁,一切以我为准,平常的主要工作内容就是 3 部分,处理写请求、管理日志复制和不断地发送心跳信息,通知其他节点“我是领导者,我还活着,你们现在不要发起新的选举,找个新领导者来替代我。”

leader election process

  1. all nodes begin as follower state with zero term. 在初始状态下,集群中所有的节点都是跟随者的状态。
  2. raft has implemented random timeout feature. Raft 算法实现了随机超时时间的特性。
  3. the node A has minimum timout will be the first one does not get the leader’s heart beat. 它会最先因为没有等到领导者的心跳信息,发生超时。
  4. At this time, node A will increase its term and elect itself as candidate. It votes itself first and then send voteRequest to other node with asking them elect A as Leader.这个时候,节点 A 就增加自己的任期编号,并推举自己为候选人,先给自己投上一张选票,然后向其他节点发送请求投票 RPC 消息,请它们选举自己为领导者。
  5. When other noe accept A request but does not vote at term 1, it will vote A and increase its term.如果其他节点接收到候选人 A 的请求投票 RPC 消息,在编号为 1 的这届任期内,也还没有进行过投票,那么它将把选票投给节点 A,并增加自己的任期编号
  6. If candidate win majority votes in the ‘elect timeout’. it will be the leader at that term.如果候选人在选举超时时间内赢得了大多数的选票,那么它就会成为本届任期内新的领导者。
  7. When node A as the leader, it will periodically send heart beat to inform other nodes it’s the leader and prevent followers initiating election. 节点 A 当选领导者后,他将周期性地发送心跳消息,通知其他服务器我是领导者,阻止跟随者发起新的选举。
QA
  1. Q: How do nodes communicate ?
    1. RequestVote Rpc, send from candidate at election time, to inform other node send vote.
    2. AppendEntries Rpc, send from leader to copy log and provide heart beat message.
  2. Q: What is the term ?
    1. Follower will increase its term when elect itself as candidate at waiting leader’s heart beat timeout. 跟随者在等待领导者心跳信息超时后,推举自己为候选人时,会增加自己的任期号.
    2. When node get term field at vote request from other nodes, it will update its term to max(its term, vote's term)
    3. candidate or leader will be follower immediately when it receives greater term from other request.
    4. node will reject the request if its term is smaller than node has.
  3. Q: rules in election?
    1. leader send heart beat to all followers.
    2. follower elect itself when leader’s heartbeat timeout.
    3. candidate will be leader if win the majority votes.
    4. leader will be still leader except problem(leader dead or network delay) happened.
    5. At each term every node will send no more than one vote with first come first got rule.
      1. 在一次选举中,每一个服务器节点最多会对一个任期编号投出一张选票,并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3,先收到了 1 个包含任期编号为 4 的投票请求(来自节点 A),然后又收到了 1 个包含任期编号为 4 的投票请求(来 自节点 B)。那么节点 C 将会把唯一一张选票投给节点 A,当再收到节点 B 的投票请求RPC 消息时,对于编号为 4 的任期,已没有选票可投了。
    6. When got the same term, follower with high log integrity will reject send vote to lower log integrity.
      1. 当任期编号相同时,日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。
      2. 比如节点 B、C 的任期编号都是 3,节点 B 的最后一条日志项对应的任期编号为 3,而节点 C 为 2,那么当节点 C请求节点 B 投票给自己时,节点 B 将拒绝投票。
    7. The election is initiated by followers, who elect themselves as candidates; Majority votes refer to more than half of the votes of cluster members; The goal of the majority voting rule is to ensure that there is at most one leader in a given term of office.
      1. 选举是跟随者发起的,推举自己为候选人;大多数选票是指集群成员半数以上的选票;大多数选票规则的目标,是为了保证在一个给定的任期内最多只有一个领导者。
  4. Q: random timeout
    1. follower wait leader’s heartbeat.跟随者等待领导者心跳信息超时的时间间隔,是随机的
    2. Election will be invalid if no candidate win majority vote. 当没有候选人赢得过半票数,选举无效了,这时需要等待一个随机时间间隔,也就是说,等待选举超时的时间间隔,是随机的
  5. Important notes:
    1. node with high log integrity can be the leader, log must be successive.
    2. all methods include –term, leader’s heartbeat, random election timeout, first come will be first served vote rule, majority votes rule and so on are trying to promise only one leader at each term and decrease the possibility of failure situation.

how to copy log

CATALOG
  1. 1. Paxos
    1. 1.1. basic paxos
      1. 1.1.1. stage
        1. 1.1.1.1. prepare
        2. 1.1.1.2. Accept
    2. 1.2. multi-paxos
      1. 1.2.1. review
      2. 1.2.2. problem
        1. 1.2.2.1. leader
        2. 1.2.2.2. optimize
        3. 1.2.2.3. Chubby 的 Multi-Paxos 实现
  2. 2. Raft
    1. 2.1. role which also called server state
    2. 2.2. leader election process
      1. 2.2.0.1. QA
  3. 2.3. how to copy log