分布式共识算法—

本文为阶段学习成果记录，如有错误，欢迎指正

Paxos算法由 Leslie Lamport 于1990年提出，主要为了解决分布式系统中的共识问题。

什么是共识？

分布式系统就像一个人类群体一样，其中每个节点相当于一个独立的个体，个体之间相互沟通交流彼此的信息。
假设某天椰虂想和好友一起吃饭，几人通过聊天软件商量了半天，最后决定去吃火锅。这一过程便是达成共识的过程。在分布式系统中，“吃什么”是多个节点要达成一致的一个值，这个值的结果就是“火锅”。

怎么达成共识？

显然，决定吃什么是一个过程，而这一过程要怎样完成，才能让所有人一致同意去吃火锅呢？

Paxos中的角色

当大家有这个想法之后，有人提议去吃烧烤，有人则想去吃火锅，还有人想吃KFC… 这些想法，在Paxos中被称为提议(Proposal)，当想法被某个人接受，则转变为Chosen状态。此时，每个提出想法的人称为Proposer，听取他人提议的人称为Acceptor，要了解被接受的提议的人称为Learner。显然，同一个人可以拥有多个角色。

Proposal的特点

在开始讨论的时候，每个人七嘴八舌，搞得大家晕头转向的。因此，大家决定列张表格，每个人在自己的提议前面加上编号(例如：1.烧烤，2.火锅…)。现在，Proposal的结构变得十分清楚，即Proposal = Number + Value。

达成共识

在介绍达成共识的方法前，首先要明确，每个节点之间可以互相通信，但是并没有一个消息总线。拿上面的例子来讲，椰虂和各个好友都是私聊，不存在什么群组聊天。
接下来，椰虂遇到了一些问题：

几人最初决定，将所有想法发给一个人，那个人只接受他最先收到的想法。
现在问题来了，我们选出的“组长”断网了，导致整个过程没有办法推进下去，即master节点出现问题后，整个系统都会崩溃。
所以我们决定，每个人可以把自己的想法发给多个人，当提议被多数人(一边而言为半数以上)接受，则被全体接受(人话：少数服从多数)
现在可以保证一个”组长“断网不会影响整个过程。但是新问题接踵而至：如果A发给B，C发给D，几个人之间达成了一个“没有多数”的巧合，那岂不是永远商量不出结果？
那如果每个人接受所有收到的想法呢？
这种方式的结果就是，可能有多个想法同时符合“少数服从多数”的条件，依然没有办法做出选择。
最后，我们决定，每个人可以收到多个想法，然后选取编号最大的一个想法接受，并且后续不会接受编号更小的想法。
比如，椰虂收到了“4.火锅”这一消息，并且接受了，那么如果另一个好友发来“3.KFC”，椰虂 是不会接受这个想法的。另外，需要保证相同编号的提议的值一致。若此时有好友发来“4.烧烤”，虽然椰虂不会拒绝，但是会告诉好友，我这里收到了你的消息，但是已经决定了去吃火锅，你那里自己改一下吧。

现在，我们基本上明确了Paxos达成共识的大致方法，接下来详细分析一下。

Paxos过程

Paxos主要分为两个阶段，Prepare和Accept。

Prepare阶段

作为Proposer，我们需要将自己的想法按照Proposal的形式发送给部分好友(注意，不一定是全部好友)。
作为Acceptor，我们要判断，新接到的Proposal的序号是否比所有已经接到的Proposal的序号大。

i)如果新接到的序号小，则忽略这个Proposal，告诉发送的好友，你的这个想法我不会接受。 ii)如果新接到的序号大，则告诉发送的好友，我会考虑接受你这个想法，且会忽略一切序号比当前想法小的想法 iii)如果已经接受了一个想法，则会告诉对方，我现在已经有接受的想法了，你那里同步一下

伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func promise(proposal) msg{
  if proposal.id > maxPromisedId{
    maxPromisedId = proposal.id
    if (already accept a proposal){
      return msg{id:maxPromisedId,chosenValue}
    }
    return msg{id:maxPromisedid,nil}
  }
  return refuse msg
}

Accept阶段

作为Proposer，我们接收到了Acceptor的回复，如果向我们保证会考虑自己想法的回复占了半数以上，则会向部分好友**(这里的部分好友不一定与Prepare阶段的完全相同)**发送Accept请求：“我的想法已经被多数人考虑了，你要不接受一下？”请求中包含了统一值以后的Propsal
伪代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func handlePromise(promisedMsg){
  if promisedMsg.value != nil{
    proposal.value = promisedMsg.value
  }

  if promisedMsg.ok{
    count++
  }  
  if count > len(acceptors)/2 + 1{
    requestAccept(proposal)
  }
}

作为Acceptor，当我们收到了Accept请求后，要判断，在收到这个请求之前，有没有对更大编号的想法做出承诺。如果没有，则接受这个想法，否则告诉对方：”我这里对比这个想法编号更大的想法做出了保证，因此没法接受你的想法“
伪代码：

1
2
3
4
5
6
7


handleAccept(proposal) msg{
  if maxPromisedId > proposal.id{
    return refuseMsg
  }
  promisedProposal = proposal
  return OKMsg
}

活锁

上述方案感觉确实可行，但是仍然有一个小bug。比如A给我发了一个“2.火锅”，我做出了考虑承诺，但是在他给我发送accept请求之前，我又收到了B的”3.烧烤“，我就没法接受”2.火锅“这个想法。同样的，A不服输，在我接收到B的accept请求前又给我发了一个”4.KFC”，以此类推，我就永远无法接受一个最终的想法了。
不过，通过引入随机时间，错开每个Proposer发送Proposal的时间，保证其发送accept请求之前Proposal被抢占的可能性没有那么大，就能解决这一问题。

结语

本文主要简述了Paxos算法的基本概念与流程。不难发现，Paxos算法带来的开销还是比较大的，而且并不是特别容易理解。因此，后续也诞生了Raft等一系列分布式一致性算法。

参考资料

[1] 《Paxos Made Simple》(https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf) [2] 《Paxos算法与Raft算法》(https://yeasy.gitbook.io/blockchain_guide/04_distributed_system/paxos) [3] 《Golang实现Paxos分布式共识算法》(https://zhuanlan.zhihu.com/p/335857136) [4] 《理解Paxos》(https://mp.weixin.qq.com/s/lbauCATMesqTEeIQuCsz9A)