(译文)通过一个例子理解paxos算法

paxos算法号称是"世界上唯一的分布式一致性算法",其他任何一致性算法都是它的变体.

最近在看paxos算法, 看了不少博客, 都感觉总结得不够到位,甚至有理解偏差的地方,倒是在博客的引用文章里面找到了一篇英文文献,看完后豁然开朗茅塞顿开.

于是把那篇英文原文翻译了一下, 加深一下理解

英文文献虽是2012年的了, 但是短小精悍,值得一看,原文地址是:

angus.nyc/2012/paxos-by-example/

文章中不全是直译, 有些地方改成了我自己的理解, 所以有可能有理解错的地方, 还望指出.

另外在理解的过程中参考到了以下这篇文章, 也是一篇paxos算法相关的译文

www.iteblog.com/archives/23…

译文开始

本文通过一个实例描述了一个叫Paxos的分布式一致性算法

分布式一致性算法通常是用于让多个计算机节点就某个单值的修改达成一致, 例如事务的提交commit或回滚rollback, 典型的思想就是二阶段提交或三阶段提交.

算法并不关心这个单值是什么,只关心最后只有唯一一个值被所有的节点选中, 对该值的修改达成一致

在一个分布式系统中这非常的难, 因为不同机器之前的消息可能会丢失, 或是被无限延迟, 甚至机器本身也会挂掉

Paxos算法可以保证最终只会有一个值会被选中, 但是不能保证如果集群中的大多数节点挂掉后,还能选中一个值

概述

Paxos的节点可以是proposer, acceptor,learner中的任何一种角色.proposer会提议一个它想被采纳的值, 一般是通过发送一个包含该提议值的提案给集群中的每个acceptor. 然后acceptor会独立的决定是否接受这个提案--它可能会接收到多个proposer的不同提案, 决定好后会把它的决定发给learner. learner的作用是判断一个值是否已经被接受.在Paxos算法中, 只有一个值被大多数的acceptor选中, 才算被Paxos算法选中.在实际项目中, 一个节点可能担任多种角色, 但是在这个例子里面, 每一种角色都是一个独立的节点.

图1 Paxos的基本架构. 几个proposer向acceptor提交提案. 当一个acceptor接受了一个值后, 它把它的决定发给learner

Paxos算法例子

在标准的Paxos算法中, 一个proposer会发送两种类型的消息给acceptors: prepare request 和accept request. 在算法的第一阶段, proposer会发送一个prepare request给每一个acceptor, 这个prepare request包含一个提议值value和一个提案号number.每一个proposer的提案号number必须是正数, 单调递增的,独一无二的自然数.

在下面图2的例子中, 有两个proposer, 都在发送prepare request. proposer A的请求([n=2,v=8])比proposer B的请求([n=4,v=5])先到达acceptor X和acceptor Y, 而proposer B的请求先到达acceptor Z

图2: Paxos. proposer A和B各发送了一个prepare request 给每一个accetor. 在这个例子中, proposer A的请求先到达acceptor X和Y, 而proposer B的请求先到达了acceptor Z.

如果一个acceptor接收到了一个prepare request而又没接收过其他的提案, 这个acceptor会回应一个prepare response, 并保证不会接受其他比当前提案号number更小的提案. 下面图3展示了每个acceptor是如何响应它们接收到的prepare request的

图3: 每个acceptor都对它接收到的第一个prepare request 进行prepare response.

最终, acceptor Z接收到了proposer A的请求, acceptor X和Y收到了proposer B的请求.

如果一个acceptor之前已经接收了一个提案号更高的prepare request的话, 那么后面收到的prepare request就会被忽略, 这个例子中就是acceptor Z会忽略掉proposer A的请求(Z已经接收了B的提案n=4).

如果acceptor之前没有接收过更高提案号的提案, 它会保证忽略其他提案号比这个更低的请求(注意是包括prepare request和accept request),然后在prepare response中把它已经选中的提案号最高的提议(包括这个提议的值)发送给proposer.在这个例子就是acceptor X和Y给proposer B的响应(X和Y已经接受了一个B的[n=2,v=8]的提案,当再收到[n=4, v=5]的提案时, 它保证会忽略任何n<4的prepare request和accept request, 然后把[n=2, v=8]的prepare response回去给B)

图4: acceptor Z 忽略了proposer A的请求, 因为它已经接收到了更高的提议号(4 > 2). acceptor X和Y给proposer B响应了它见过最高的提议号的提案, 并承诺会忽略提案号更小的提案

一旦proposer 收到了大多数acceptor的prepare response, 它就可以开始给所有的acceptor发送accept request了. 因为proposer A接收到prepare response中表明在它之前没有更早的提案. 所以它的accept request中的提案号和提议值都是跟prepare request中的一样.然而,这个accept request被所有的acceptor都拒绝了,因为它们都承诺了不会接收提议号比4更新的提案(因为都见过proposer B的提案了)

Proposer B的accept request情况就跟proposer A的有所不同了. 首先它的提案号还是它之前的提案号(n=4), 但是提议值却不是它之前的提议值了(它之前提议的是v=5), 而是它在prepare response中接收到的提议值(v=8)

图5: proposer B也发送了一个accept request给每一个acceptor.acceptor request中的提案号是它之前的提案号(4), 而提议值是它在prepare response中收到的值(8, 来自proposer A的提案[n=2, v=8])

如果acceptor收到了一个提案号不小于它见过的accept request, 它会接受这个accept request并且发送一个通知给到learner节点. 当learner节点发现大多数acceptor都已经接受了一个值的时候,Paxos算法就认为这个值已经被选中.

当一个值被paxos选中后,后续的流程中将不能改变这个值.例如,当另一个proposer C发送一个提案号更高的prepare request(例如, [n=6, v=7])过来时,所有的acceptor都会响应它之前已经选中的提议(n=4,v=8).这会要求proposer C在后续的acceptor request中也只能发送[n=6, v=8]的提议, 即只能确认一遍已经选中的这个值. 再后面, 如果有少量的acceptor还没选中一个值的话, 这个流程会保证最终所有的节点都会一致地选中同一个值.