多节点状态一致

在数据在多个节点存储的情况,数据的修改会首先提交到其中的一个节点上,之后在同步到所有节点中。

这里有两种同步方法,两种方式传递状态的方式不同:

  • 状态转移:在第一个修改的节点状态(包括其中存储的数据),将节点的所有数据(作为一个状态)同步给其他节点
  • 操作转移:将第一个修改的节点的操作发送到其余的节点上,所有的节点执行相同的操作(在确定状态机上,状态机的初态和顺序一致的输入即可达到相同的状态)

在执行操作的期间,允许节点的状态不同(一部分节点已经完成操作,而另一部分未完成),这种不一致的状态需要对外部来说不可见,而最终所有的节点状态一致。

考虑到节点可能出现错误,一般来说只要集群中的半数以上的节点完成了状态的转移,那么就认为这个集群完成了状态的转移。

让集群在外部看来保持一个一致性的即是协商共识,依赖于分布式的共识算法完成。

Paxos

令多个节点对一个(单个)变量的值的一次更新(或者置初值)达成共识。

将分布式中的节点角色分为 3 类:

  • 提案节点
  • 决策节点,决定一个提案是否通过
  • 记录节点(不参与提案和决策),仅执行一个已经通过的提案

假设在系统初始化时,每个节点都已经获取到节点的数量,以及地址。

对于一个变量的值到底是什么存在分歧是因为:

  1. 节点之间的通信存在延迟,错误和丢失
  2. 外部对这个值的存取(读写)是并发的

抢占锁:一个节点获取锁之后,可能在释放锁之前崩溃,那么分布式中的锁需要是可抢占的。

paxos 分为两个阶段,准备和批准

准备阶段(Prepare)

提案节点对其余节点发出 prepare 请求,请求中包含一个全局唯一的数 n 作为提案 ID

决策节点在接受这个请求后(先执行承诺,再返回响应):

(两个承诺)

  • 不会接受提案 ID $\le$ n 的 prepare 请求
  • 不会接受提案 ID < n 的 Accept 请求

(一个响应)

以当前接受(Accept)过的最大的提案 ID 和提案中单变量的值作为响应。如果没有接受过任何提案,响应中变量值为空。

接受阶段(Accept)

分为两种情况:

  • 所有 prepare 响应中,单变量的值都为空
    那么说明这个 prepare 请求是集群中最新的,提案节点可以对单变量设置值,发出一个包含提案 ID(之前发出的 Prepare 请求中的提案 ID) 和变量值的 Accept 请求。
  • prepare 响应中,存在单变量的值不为空的情况,那么找出不为空的,提案 ID 最大的响应,以这个提案 ID 和响应的变量值发出 Accept 请求。

超时

Paxos 不总是成功或失败,也可能形成一个活锁,需要在某个提案在一段时间后主动失败。

Multi Paxos

paxos 中存在活锁和一系列复杂的场景很大原因是因为每个节点都可以发起提案,Multi Paxos 与 Paxos 相比,增加了对主节点的选举。只有主节点可以发起提案。

选主

在 Multi Paxos 中,节点会通过心跳包轮询集群中存在主节点,如果发现当前集群中没有主节点的话,通过 Paxos 的准备和接受两个阶段进行选主(可以视为将集群中的变量:主节点编号,设置为自己)。

选主之后的提案就不需要进行准备阶段了(已经没有节点能与其竞争了)。

接受阶段

与 Paxos 不同的是,发起的提案中除了提案 Id 和值 value 之外,还需要一个任期编号 i 字段,这是为了当旧主节点掉线,集群重新选主,然后主节点由上线了,这时候就需要区分提案是新或旧的主节点发出的,也通知旧的主节点它的任期已经结束。

Gossip

Gossip 可以看作一直循环执行下面两件事:

  • 如果有某一项信息需要在整个网络中所有节点中传播,那从信息源开始,选择一个固定的传播周期(譬如 1 秒),随机选择它相连接的 k 个节点(称为 Fan-Out)来传播消息。
  • 每一个节点收到消息后,如果这个消息是它之前没有收到过的,将在下一个周期内,选择除了发送消息给它的那个节点外的其他相邻 k 个节点发送相同的消息,直到最终网络中所有节点都收到了消息,尽管这个过程需要一定时间,但是理论上最终网络的所有节点都会拥有相同的消息。

Gossip 对节点状态的传播同样由最上面的两种方式(状态转移和操作转移),称为反熵和传谣。

raft

raft 作为一个非常重要的分布式共识算法,单独作为一篇博客:

raft 分布式共识算法
work and life with some dreams