本文更接近复习笔记，侧重Basic Paxos的整体把握和实现（Go语言）。系统学习建议继续阅读相关论文[1]和wiki[2]。
解决的问题
假设server group中有N个server，每个都可以处理client发来的请求，但要求这个group对外表现一致——即在所有client看来都像是只有一个server。因此，任何一个server只有在确定知晓自己的状态与其他（大部分）server相同时才会处理client的请求。一致性算法（consensus algorithm）是server用来在互相之间针对某个问题达成一致所用的方法，Paxos就是其中的一种。
总体认识
Paxos算法可以理解成一群server来针对某个议题（比如变量x的取值）开会讨论，至少有一个server带来了自己的提案，最多也可以每个server都带来了自己的提案。servers会按一定的规则进行投票。会议在大多数的server对议题成一致之后结束。
一些概念
提案（proposal）：server对“议题”的“想法”（比如“x=2”），每个提案还会包含一个唯一的proposal number；
proposer：提出提案的server；
acceptor：接收提案并选择是否接受的server
quorum：acceptors的一个子集，简言之就是其中的大多数；
- proposer和acceptor是Paxos算法中为了结构清晰而抽象出来的概念，一般来说代码实现的时候一个server会同时扮演proposer和acceptor的角色
原则
重要的是让server中的大多数尽快达成一致，最终选谁的提案不重要。
过程
算法的介绍和详细分析已经有很多[3]，本文直接从伪代码开始进行分析。
-- Paxos Proposer --
# v为该proposer准备提出的值
proposer(v):
# 选择一个大于当前所有n_p的proposal number
choose n > n_p
# 将proposal发送给所有server（包括自己）
broadcast prepare(n) to all servers
# 若收到了大多数的prepare_ok回复
if prepare_ok(n, n_a, v_a) from majority:
# 选择其中最大的n_a对应的v_a来更新v的值，如果还没有这样的值则选择自己之前准备的v
# 注意这里处理的目的是：如果存在已被accept（但还未decide）的值，则选择其中最新的作为自己的提案值，从而便于尽快达成一致
v' = v_a with highest n_a; choose own v otherwise
# 向所有server发送accept请求
send accept(n, v') to all
# 如果收到了大多数的accept_ok回复
if accept_ok(n) from majority:
# 对所有server发送decided请求
send decided(v') to all
-- Paxos Acceptor --
每个acceptor需要维护的状态（需持久存储以应对机器故障）:
n_p: 最小proposal number，小于该数的proposal直接reject；同时也是当前见过的最高的prepare(n)中的n
n_a: 已接受的proposal的对应number
v_a: 已接受的v值
acceptor's prepare(n) handler:
if n > n_p:
n_p = n
reply prepare_ok(n, n_a, v_a)
else:
reply prepare_reject
acceptor's accept(n, v) handler:
if n >= n_p:
n_p = n
n_a = n
v_a = v
reply accept_ok(n)
else:
reply accept_reject
- 实现代码中使用RPC进行不同server间的通讯，比如prepare请求的发送实际上是server1中的prepare()进行对server2中的prepareHandler()的远程调用
func (px *Paxos) prepare(peerIndex int, seq int, proposeNum int) (PrepareReply, error) {
var reply PrepareReply
// 准备参数
...
// RPC
ok := call(px.peers[peerIndex], "Paxos.PrepareHandler", args, &reply)
// 根据RPC结果进行处理
if !ok {
return reply, fmt.Errorf("prepare RPC failed: index: %d, number: %d, seq: %d", peerIndex, proposeNum, seq)
}
return reply, nil
}
func (px *Paxos) PrepareHandler(args *PrepareArgs, reply *PrepareReply) error {
// 根据args（传来的参数）进行处理
...
// 根据处理结果生成结果值并存入reply
...
return nil
}
- 几种情况的流程图（图片来源网络）
以下图为例，其中左侧的X和Y分别为server S1和S5准备提出的提案中的值（即伪码中的v）；方框中的表示相应Handler操作，比如S2时间线上的P3.1即表示S2的prepareHandler()被远程调用，传入的proposal number是3.1，图中proposal number的构成是number + '.' + 'serverId'的形式，即P3.1是由S1的prepare()调用的；同理，A3.1X表示acceptHandler()被远程调用，同时传入的参数是proposal number3.1和proposal valueX。
例1：S5发起提案时大多数server已接受了同样的值，S5得知后便将自己提案的值改成同样的值
例2：S5发起提案时大多数还未达成一致，但S5看到S3已接受了一个值，也会将自己的提案值改成相同的值以便尽快达成一致
例3：S3在处理P4.5的时候还没有accept S1提出的X，之后再处理A3.1X的时候因为已经见过S5 prepare的更大的proposal number (3.1 < 4.5)，所以会拒绝S1的A3.1X而接受S5的A4.5Y
代码实现
上学期Distributed System课上的一个lab，类似MIT-6.824的这个lab。
源码地址：Github
03/09/18
