Author 2022-04-25
PDF
Paxos共识算法1分布式一致性(1)：Paxos真的很简单！刨根问底算法ContentsPaxos共识算法 ........................................................................................ 1共识问题确定选取的提议老爷子说，很简单，简单的不能再简单我敢说，简单到全世界搞计算机起码有的人都得怀疑自己的智商。为了让自己保持在自己的之内，最近几天又重新来学习一下。回头来看，Paxos made simple的确很简单地描述了算法。本文即记录理解此文的一些思考。Paxos共识算法共识问题共识问题就是一组程序需要能够为选择某个值达成共识。首先来说，需要有至少一个提议，然后各程序通过类似投票的方式进行选举，达成共识后，这个提议的值被称为选中。为了保证这个过程是完备的，需要遵循几个安全性要求只有被提议的值才可能被选中，也就是说不能平白无故随便选一个值出来有且仅有一个值会被选中只有一个值真正被选中之后，程序才能获悉选中了此值。这个条件稍微有点奇怪，换句话表述就显得自然一些：程序必须要获悉真正被选中的值不可能原理已经证明，在异步的网络模型（即无超时边界）下，不存在一种共识算法能够完全满足下面三个条件：可终止所有的节点（只要没有挂掉）最后必须要决定一个值达成一致即上述的安全性要求容错性：当存在节点失败的情况下依然能够奏效但是如果牺牲掉一些特性（比如选）或者使用同步的情况下，是可以实现一致性算法的。中假定遵循异步、非拜占庭容错的网络模型：节点可以奔溃、失败、重启，可以以任意的速度响应消息可以经过任意长的时间投递；可以重复；可以丢失；但不会被篡改（如果是拜占庭容错，那么可以假定节点可能发出一些篡改的消息，例如被恶意攻击）中，将参与者区分为提议者、接受者、学习者。简单来说，提议者可以提出待选择的提议；接受者决定选择哪一个提议；学习者能够获悉被选中的值。 Paxos共识算法2一般情况下为了简化这个过程，通常让一个分布式节点即是提议者、又是接受者。学习者不是必须的。确定选取的提议在Paxos made simple文中，作者通过一步一步从简单到复杂的推理过程，来得出一个最终的算法，让人印象深刻。从最简单的情况开始。最简单的情况是，只有一个接受者，并且选择接受到的第一个提议。这样肯定可以达成一致，但是一旦这个接受者挂掉，那么就不可能会选取一个值。因此，在分布式共识算法中，需要有多个接受者，只有其中的大多数接受者都选取了一个值，才认为其被选中。为了达成大多数的情况，节点总数必须为奇数。这种方式下，接受者如果最多只能接受一个值，那么可以形成一个多数派，从而达成共识。考虑到消息可能丢失或者节点失败，节点是无法预测是否会有第二个消息到来，那么假设只有一个提议者，提交了一个提议，这个提议一定需要被接受。否则这种情况下，无法达成共识。这种方式被归纳为：接受者必须接受其第一次接收到的提议。这种方式存在的问题是，有可能会有多个提议者几乎同时发起了提议，而接受者分别接受到了不同的提议，假定有个接受者、三个提议：，首先接受到，按照接受了，首先收到，接受了首先收到，接受了这种情况下，提议、、没有一个形成多数派（至少个接受者接受），因此无法达成一致。即便只有个提议者、，一旦挂掉，提议、也无法达成一致。因此，可以推论出，接受者必须要允许接受多个提议。为了方便表示，将提议进行编号（以自然数正序），以代表编号为的提议值为。没一个不同的提议其编号是不一样的（即便是两个提议值相同，也是不同的提议，其编号一定不相同）。在这种方式表示的情况下，一个值被选中的条件是，有一个值为的提议被多数派接受。为了满足，同时又能够支持接受者多次接受，那么推导出如果一个值为的提议被选中，那么其他被选中的更高序号的提议值必然为。这个推论看起来没什么问题，但却困扰了我一段时间：既然已经选中，又何来再选中之说呢？我们这可是阿！选中一个值，不就结束了么？应该这么来看待：选中首先是要站在事实的角度来看（即以上帝视角来审视），如果超过半数的接受者接受了某个提议，那么它事实上已经被选中。这是从所有接 Paxos共识算法3受者的角度来看的，但对于观察者（提议者）而言，是不能保证他们一定能够获悉这个结论的。提议者通过将自己的提议发送给所有的接受者，并从结果中判断是否有超过半数的接受者接受，来判断自己的提议是否被接受。 比如两个提议者（A，B）分别提议了1,2，acceptor一定只能接受一个， 比如1被多数接受者接受，那么<1, v1>就被选中了。 但是假设返回给提议者的消息丢失了，对于提议者A无法确定自己的提议是否被接受； 从而需要再发起一次投票 但是此时，B已经获悉自己的提议被接受。 (Acceptor 1) (Acceptor 2) (Acceptor 3) ________ ___________ ____________ _______________ <1, v1> | accept | accept | reject <2, v2> | reject | reject | accept因为消息可能丢失，或者节点挂掉重启。因此，当这样的情况发生时，观察者需要重新发起提议，向所有的接受者重新发起提议，然后再判断是否选中。因此，选中这个事件，不论是在观察者角度、还是接受者角度，都可能发生多次；只有保证他们全部是一致的，才能满足安全性需求。所以说，即使有多个提议被事实上选中，那么他们的值必然要一致，才能保证对于所有的观察者而言，选中了一个唯一的值。那么如何才能保证呢？说，如果被选中，那么更高编号的提议被选中必然值为；本来选中只需要超过半数的接受者接受即可，但是我们可以用一个更严格的条件来满足它：如果被选中，后续所有接受者接受的更高编号的提议必然值为。这个约束比更加严格，也能够保证被选中，因此得到：如果一个值为的提议被选中，那么其他被任意接受者接受的的更高序号的提议值都为。必须跟一起才能保证正确，因为无法适用只有一次提议的场景。而因为是异步模型，可能存在一种场景是，某个接受者接受到的第一次提议，对于其他接受者而言不是第一次了（比如一个接受者挂掉，进行第二轮投票的时候才恢复）。对于其他接受者，可以只接受自己曾经接受过的值；但是对于这个接受者，按照，它必需要接受这个提议，无论其值是什么。这样就可能出现与冲突的情况。解决的办法也很简单，既然值是由提议者决定的，那么我们要求一旦值被选中后，提议者提出的更高序号的提议的值必须为：如果一个值为的提议被选中，那么任意提议者提出的任意更高序号的提议值都为。是比更严格的条件，因此可以满足，当然也满足。那么如何做才能满足这个条件呢？通过数学归纳法，可以证明：假设提议被选中，那么对于任意提议必定有。数学归纳法分为两步： Paxos共识算法4基础步骤：验证在时成立归纳步骤：假设为真，证明为真那么，如果应用到上述的条件，可以有：基础步骤为的时候，被选中是预设的前提，无需证明归纳假设：假设提议的值都为。证明目标：现在要证明对于提议，其值也为。为了完成这一目标，还需要先增加一个提议的条件：对于任意的提议被提出的条件是，存在一个多数派集合要么满足：这个集合中没有一个接受者接受过任意小于的提议（也就是说第一次接受提议）；要么满足：所有接受者中，其接受的小于的最大编号提议的值为。因为已经选中，所以一定存在一个多数派，其中所有的接受者都接受了提议。从而推断出：中的所有接受者都接受了一个的提议（至少接受了），且其中所有提议的值均为（从假设可以得出）。对于任意一个多数派集合，一定与至少有一个交集，因此条件不可能成立；而根据上面的推论，条件是满足的。从而，一个新的提议（）的值必然也为。从而，证明了。要满足，提议者在提议之前，必须要获悉当前小于的最高提议的值，为了能够得到确定的结果，要求接受者不能再接受任何小于的提议，并得到如下的一个算法：提议者准备提交，首先发送一个准备请求给接受者，要求其：承诺不再接受任何小于的提议返回其接受的小于的最大提议（如果有的话）如果提议者从多数接受者获得的提议值为，那么提议者可以提议；或者没有从接受者获悉已经接受的提议，那么提议者可以提议任意的值。这个过程被称为接受请求对于接受者而言，可以响应任意的请求，而对于请求，必须要保证：接受者当且仅当在没有响应大于的请求的时候，才可以接受。很明显，是包含的。最后，加入了一个小的优化。如果接受者已经响应了的请求且大于，那么接受者无论如何也不会再接受提议了，因此不需要响应和；同样对于已经接受的提议的请求也不需要响应。最终，完整的算法如下： Paxos共识算法5准备阶段提议者向多数派接受者发送请求。如果接受者收到请求时大于其响应过的任意请求序号，那么它返回给提议者一个不再接受任何小于的提议的承诺，以及其已经接受的最大的提议（如果存在的话）提交阶段：如果从多数派接受者收到的响应是不是真的很简单？算法分布式理论：深入浅出算法区块链共识算法的发展现状与展望

HTML view coming soon.

Download PDF for the full formatted version.