计算机系统工程之：Paxos

Replicated State Machines

备份状态机，每个机器单独为一个状态机，他们具有相同的初始状态，转换规则，以及输入的顺序也是一致的，对于特定的输入的转换也是确定而非模糊的（Determined State Machine）；问题在于，如果请求是分别由客户端发往不同的备份机器上的，那么顺序根本无法保证
primary-backup model 首先使用primary机器来为每个输入确定好排序后发给每个备份机器，而primary本身也需要一个备份机器来进行备份自身排好的输入顺序，这样在主机器挂了之后还有个backup顶住

这里其实关键的问题就是，如何控制每个机器接收到的请求的顺序是完全一模一样的，此处使用了primary-backup的机制，也就是每个记录数据的节点还需要一些备份节点同步更改
在一个分布式体系中，有不止一个coordinator，一个coordinator负责不同的客户们的请求，而且还决定了体系中哪一个数据节点是priamry；请求会被coordinator转发到primary node中，而backup node则负责接收primary的指令并且返回ACK；但是这里会有个问题，即决定primary的coordinator不止一个，很可能会同时出现两个primary；一个primary会直接拒绝另一个primary发来的复制请求，因为primary不会去复制别人
所以出现了一个叫做view server的东西，coordinator会从vs中获取谁是primary，而vs用于监控每个数据节点的心跳以及调控谁是primary
Paxos1
一些问题：

  • vs在更改primary节点的时候，在现有体系下的步骤是同时给将来的primary节点发送一个“你是将来的primary”的指令，同时更新自己存储的primary节点id；如果有coordinator在新primary仍然未正式成为primary的时候，从vs中获取到了新primary的id，然后给其发送客户端的数据请求，那么将来的primary（当时还是backup）会在这个阶段拒绝，因为backup不会接受这种请求 （但是其实可以选择去优化它，这样可以让请求不会被错误地拒绝）
  • vs并非是向S1发送“取消其primary资格”的指令，在S2确定自己为primary节点的时候，假设仍然有未来得及询问vs的coordinator向S1发送了数据请求，那么S1会发送备份请求给S2（在这个体系中其记录了S2为其备份），然而S2表示了拒绝，说明自己已经被vs给辞退了，于是他会拒绝这个数据请求，并且退出primary状态
  • 理论上应该立即给S2分配一个备份节点，但是这个体系没有这么做
  • 如果vs挂了，难道还要再来一个backup，然后一层套一层形成套娃递归？

Paxos

Paxos是一个具有非常多进程的一个用于备份的集群，他的结构比较复杂，介绍一下每个部分的作用：
Paxos2

  • Proposer是用来进行“提交议案”的进程，他会向每个Proposer（包括自身）和Acceptor去发送自己的Proposal Number，并且在这个number被半数接受后将这个number和对应的value广播给每个Proposal/Acceptor/Listener
  • Acceptor用于接受proposal，根据自身所见过的最大number $N_h$来判断要不要赞成这个接收到的number，如果大于$N_h$则赞成并发给该proposer，反之表示反对
  • Learner用于接受Proposer发送的<number, value>

每个proposer发送proposal并没有什么规定，想什么时候发就什么时候发，acceptor只会认可超过自身见过的number的proposal number的请求

Paxos in Action

  1. 客户端向某个proposer发送一个请求
  2. 这个proposer会成为广播number的leader，创建一个$N$作为要发送的number，$N$必须是大于自身记录的$N_h$
  3. 作为接收者acceptor，赞成这个proposal的条件如下，即这个$N$大于自身的$N_h$，如果是则会发送$N_a$和$V_a$给proposer leaderPaxos3
  4. 如果proposer收到了超过半数票的赞成，则会将这个提案视为成功，并且将$N,V$发送到每个acceptor/proposer；而$V$则由发送来的$N_a$最大的$V_a$决定
  5. 如果acceptor接收到了proposer的<accept-request>则会修改自身的$N_a,N_h,V_a$，并且将ACK发送给leader/learner
  6. 由learner来进行对client的回复
    Paxos4Paxos5Paxos6

  • 由于proposer本身也作为acceptor，故可能出现不同的proposer提出number一致的提案；同时也因为如此，proposer不会陷入一个较低的number而被废掉Paxos7

    若半数以上的acceptor已径accept-ok一个value，那么即使accept-ok没被proposal收到，下一个proposal也会收到这个accept-ok的value，该value是Na最高的value

当时针对这个问题做了思考，有兴趣的人可以深入交流讨论，未验证过是否属于“想当然”证明
Interesting Question