Dustin 是 Mozilla 的开源软件开发人员和发布工程师。他曾参与过各种项目，例如 Puppet 中的主机配置系统、基于 Flask 的 Web 框架、防火墙配置的单元测试以及 Twisted Python 中的持续集成框架。在 GitHub 上找到他，用户名为 @djmitche.
在本章中，我们将探讨旨在支持可靠分布式计算的网络协议的实现。网络协议可能难以正确实现，因此我们将研究一些最小化错误以及捕获和修复剩余错误的技术。构建可靠的软件也需要一些特殊的开发和调试技术。
本章的重点是协议实现，但作为激励示例，让我们考虑一个简单的银行账户管理服务。在此服务中，每个账户都有一个当前余额，并使用账户编号标识。用户通过请求“存款”、“转账”或“获取余额”等操作来访问账户。“转账”操作同时对两个账户进行操作——源账户和目标账户——如果源账户的余额过低，则必须拒绝。
如果服务托管在单个服务器上，则这很容易实现：使用锁确保转账操作不会并行运行，并在该方法中验证源账户的余额。但是，银行无法依靠单个服务器来管理其重要的账户余额。相反，服务分布在多个服务器上，每个服务器运行完全相同的代码的单独实例。用户然后可以联系任何服务器来执行操作。
在分布式处理的幼稚实现中，每个服务器都会保留每个账户余额的本地副本。它将处理收到的任何操作，并将账户余额的更新发送到其他服务器。但这种方法会引入一种严重的故障模式：如果两个服务器同时处理同一个账户的操作，哪个新的账户余额是正确的？即使服务器相互共享操作而不是余额，两个对同一账户的同步转账也可能会透支账户。
从根本上说，当服务器使用其本地状态来执行操作时，就会发生这些错误，而没有首先确保本地状态与其他服务器上的状态匹配。例如，假设服务器 A 从账户 101 接收了一个转账操作到账户 202，而服务器 B 已经处理了将账户 101 的全部余额转账到账户 202 的另一个转账，但尚未通知服务器 A。服务器 A 上的本地状态与服务器 B 上的本地状态不同，因此服务器 A 错误地允许转账完成，即使结果是账户 101 透支。
避免此类问题的技术称为“分布式状态机”。其思想是，每个服务器在完全相同的输入上执行完全相同的确定性状态机。那么，根据状态机的性质，每个服务器都会看到完全相同的输出。“转账”或“获取余额”等操作以及它们的参数（账户编号和金额）表示状态机的输入。
此应用程序的状态机很简单
def execute_operation(state, operation):
if operation.name == 'deposit':
if not verify_signature(operation.deposit_signature):
return state, False
state.accounts[operation.destination_account] += operation.amount
return state, True
elif operation.name == 'transfer':
if state.accounts[operation.source_account] < operation.amount:
return state, False
state.accounts[operation.source_account] -= operation.amount
state.accounts[operation.destination_account] += operation.amount
return state, True
elif operation.name == 'get-balance':
return state, state.accounts[operation.account]请注意，执行“获取余额”操作不会修改状态，但仍被实现为状态转换。这保证了返回的余额是服务器集群中的最新信息，而不是基于单个服务器上的（可能是陈旧的）本地状态。
这可能与您在计算机科学课程中学习到的典型状态机有所不同。这个机器的状态不是一组有限的命名状态和带标签的转换，而是账户余额的集合，因此存在无限个可能的状态。尽管如此，确定性状态机的通常规则仍然适用：从相同的状态开始处理相同的操作将始终产生相同的输出。
因此，分布式状态机技术确保了在每个主机上执行相同的操作。但问题仍然是如何确保每个服务器都同意状态机的输入。这是一个关于 *共识* 的问题，我们将使用 Paxos 算法的衍生形式来解决它。
Paxos 由 Leslie Lamport 在一篇奇特的论文中描述，该论文于 1990 年首次提交，最终在 1998 年发表，题为“兼职议会”1。Lamport 的论文比我们这里要详细得多，并且是一篇有趣的读物。本章结尾处的参考文献描述了我们在这种实现中所采用的算法的一些扩展。
Paxos 的最简单形式提供了一种方法，让一组服务器始终同意一个值。Multi-Paxos 在此基础上构建，一次同意一个编号的事件序列。为了实现分布式状态机，我们使用 Multi-Paxos 来同意每个状态机输入，并按顺序执行它们。
那么让我们从“简单 Paxos”开始，它也被称为 Synod 协议，它提供了一种方法来达成一致，该方法只能达成一次，而且永远不会改变。Paxos 这个名字来自“兼职议会”中的传说中的岛屿，立法者在那里通过 Lamport 称为 Synod 协议的过程对立法进行投票。
该算法是更复杂算法的基础，我们将在下面看到。我们将在本示例中达成一致的单个值是我们假设的银行处理的第一个交易。虽然银行每天都会处理交易，但第一个交易只会发生一次并且永远不会改变，因此我们可以使用简单 Paxos 来达成一致。
该协议在一系列选票中运行，每个选票由集群中的单个成员（称为提议者）领导。每个选票都有一个基于整数和提议者身份的唯一选票编号。提议者的目标是获得大多数集群成员（充当接受者）对其价值的接受，但前提是尚未决定其他价值。
图 3.1 - 选票
选票从提议者向接受者发送带有选票编号 *N* 的 Prepare 消息开始，并等待从大多数接受者那里收到回复（图 3.1）。
Prepare 消息是请求带有小于 *N* 的最高选票编号的已接受值（如果有）。接受者将回复包含他们已经接受的任何值的 Promise，并承诺将来不会接受任何编号小于 *N* 的选票。如果接受者已经针对更大的选票编号做出承诺，则它会将该编号包含在 Promise 中，表明提议者已被抢占。在这种情况下，选票结束，但提议者可以自由地在另一个选票中（以及使用更大的选票编号）再次尝试。
当提议者从大多数接受者那里收到回复时，它会向所有接受者发送一个 Accept 消息，其中包括选票编号和值。如果提议者没有从任何接受者那里收到任何现有值，则它会发送它自己的期望值。否则，它会发送来自最高编号承诺的值。
除非违反承诺，否则每个接受者都会记录来自 Accept 消息的值作为已接受，并回复一个 Accepted 消息。当提议者从大多数接受者那里收到其选票编号时，选票就完成，并且该值已决定。
回到示例，最初没有其他值被接受，因此所有接受者都发送回一个不包含值的 Promise，并且提议者发送一个包含其值的 Accept，例如
operation(name='deposit', amount=100.00, destination_account='Mike DiBernardo')如果另一个提议者后来启动了一个选票编号较低且操作不同的选票（例如，将资金转账到账户 'Dustin J. Mitchell'），接受者将简单地不接受它。如果该选票的选票编号更大，则来自接受者的 Promise 会告知提议者关于 Michael 的 100.00 美元存款操作，并且提议者将在 Accept 消息中发送该值，而不是发送到 Dustin 的转账。新的选票将被接受，但支持与第一个选票相同的价值。
实际上，即使选票重叠、消息延迟或少数接受者出现故障，该协议也不会允许两个不同的值被决定。
当多个提议者同时进行投票时，很容易出现没有一个投票被接受的情况。然后两个提议者都会重新提议，并且希望其中一个会获胜，但如果时间安排恰到好处，僵局可能会无限期地持续下去。
考虑以下事件序列
Prepare/Promise 阶段。Prepare/Promise 阶段。Accept 时，接受者会拒绝它，因为他们已经承诺了选票编号 2。Prepare 来做出反应，早于提议者 B 发送其 Accept 消息。Accept 被拒绝，并且该过程重复。如果时间安排不佳——在长距离连接中更为常见，在长距离连接中，发送消息和获得响应之间的时间很长——这种僵局可能会持续许多轮。
仅仅达成一致单一静态值本身并没有什么用处。像银行账户服务这样的集群系统希望达成一致的特定状态（账户余额）会随着时间的推移而改变。我们使用 Paxos 来达成一致每个操作，将其视为状态机转换。
Multi-Paxos 实际上是一系列简单的 Paxos 实例（槽），每个实例按顺序编号。每个状态转换都会被赋予一个“槽号”，并且集群的每个成员都会严格按照数字顺序执行转换。为了改变集群的状态（例如，处理转账操作），我们尝试在下一个槽中达成一致该操作。具体来说，这意味着在每条消息中添加一个槽号，并且所有协议状态都在每个槽的基础上进行跟踪。
为每个槽运行 Paxos，至少需要两次往返，这将太慢。Multi-Paxos 通过对所有槽使用相同的选票编号集，并且对所有槽同时执行 Prepare/Promise 阶段来进行优化。
在实际软件中实现 Multi-Paxos 非常困难，导致发表了许多论文来嘲笑 Lamport 的“Paxos Made Simple”，这些论文的标题类似于“Paxos Made Practical”。
首先，上面描述的多提议者问题在繁忙的环境中可能会成为问题，因为每个集群成员都会尝试在每个槽中使其状态机操作达成一致。解决办法是选举一个“领导者”，该领导者负责提交每个槽的选票。然后，所有其他集群节点将新操作发送到领导者以执行。因此，在正常操作中，只有一个领导者，选票冲突不会发生。
Prepare/Promise 阶段可以充当一种领导者选举：拥有最近承诺选票编号的集群成员被认为是领导者。然后，领导者可以自由地直接执行 Accept/Accepted 阶段，而无需重复第一阶段。正如我们将在下面看到的那样，领导者选举实际上非常复杂。
虽然简单的 Paxos 保证集群不会做出冲突的决定，但它无法保证任何决定会被做出。例如，如果最初的 `Prepare` 消息丢失并且没有到达接受者，那么提案者将等待一个永远不会到达的 `Promise` 消息。修复这个问题需要精心编排的重传：足够多以最终取得进展，但不要太多以至于集群淹没在数据包风暴中。
另一个问题是决定的传播。一个简单的 `Decision` 消息广播可以处理正常情况下的传播。但是，如果消息丢失，则一个节点可能会永久地对决定一无所知，并且无法对后续时隙应用状态机转换。因此，实现需要某种机制来共享有关已决定的提议的信息。
我们使用分布式状态机提出了另一个有趣的挑战：启动。当一个新节点启动时，它需要赶上集群的现有状态。虽然它可以通过赶上从第一个时隙开始的所有时隙的决定来做到这一点，但在成熟的集群中，这可能涉及数百万个时隙。此外，我们需要某种方法来初始化一个新的集群。
但理论和算法的讨论就到此为止了——让我们看看代码吧。
本章中的 `Cluster` 库实现了 Multi-Paxos 的一种简单形式。它被设计为一个库，为更大的应用程序提供共识服务。
此库的用户将依赖于其正确性，因此对代码进行结构化以便我们可以看到——并测试——它与规范的对应关系非常重要。复杂的协议可能会表现出复杂的故障，因此我们将构建支持重现和调试罕见故障。
本章中的实现是概念验证代码：足以证明核心概念是可行的，但没有用于生产中使用所需的所有普通设备。代码的结构使得这些设备可以在以后添加，而对核心实现的更改最少。
让我们开始吧。
Cluster 的协议使用十五种不同的消息类型，每种类型都定义为一个 Python namedtuple。
Accepted = namedtuple('Accepted', ['slot', 'ballot_num'])
Accept = namedtuple('Accept', ['slot', 'ballot_num', 'proposal'])
Decision = namedtuple('Decision', ['slot', 'proposal'])
Invoked = namedtuple('Invoked', ['client_id', 'output'])
Invoke = namedtuple('Invoke', ['caller', 'client_id', 'input_value'])
Join = namedtuple('Join', [])
Active = namedtuple('Active', [])
Prepare = namedtuple('Prepare', ['ballot_num'])
Promise = namedtuple('Promise', ['ballot_num', 'accepted_proposals'])
Propose = namedtuple('Propose', ['slot', 'proposal'])
Welcome = namedtuple('Welcome', ['state', 'slot', 'decisions'])
Decided = namedtuple('Decided', ['slot'])
Preempted = namedtuple('Preempted', ['slot', 'preempted_by'])
Adopted = namedtuple('Adopted', ['ballot_num', 'accepted_proposals'])
Accepting = namedtuple('Accepting', ['leader'])使用命名元组描述每个消息类型使代码保持整洁，并有助于避免一些简单的错误。如果命名元组构造函数没有给出完全正确的属性，它将引发异常，使拼写错误变得明显。元组在日志消息中格式化得很好，而且作为一个额外的好处，它们不像字典那样占用那么多内存。
创建一个消息读起来很自然
msg = Accepted(slot=10, ballot_num=30)并且该消息的字段可以通过最少的额外输入进行访问
got_ballot_num = msg.ballot_num在接下来的部分中，我们将看到这些消息的含义。代码还引入了一些常量，大多数常量定义了各种消息的超时时间
JOIN_RETRANSMIT = 0.7
CATCHUP_INTERVAL = 0.6
ACCEPT_RETRANSMIT = 1.0
PREPARE_RETRANSMIT = 1.0
INVOKE_RETRANSMIT = 0.5
LEADER_TIMEOUT = 1.0
NULL_BALLOT = Ballot(-1, -1) # sorts before all real ballots
NOOP_PROPOSAL = Proposal(None, None, None) # no-op to fill otherwise empty slots最后，Cluster 使用两种数据类型命名，对应于协议描述
Proposal = namedtuple('Proposal', ['caller', 'client_id', 'input'])
Ballot = namedtuple('Ballot', ['n', 'leader'])人类受到我们可以在活动内存中保留多少内容的限制。我们无法同时推断整个 Cluster 实现——它太多了，因此很容易遗漏细节。出于类似的原因，大型单体代码库难以测试：测试用例必须操作许多活动部件，并且很脆弱，在对代码进行几乎任何更改时都会失败。
为了鼓励可测试性并保持代码可读性，我们将 Cluster 分解成几个类，对应于协议中描述的角色。每个类都是 `Role` 的子类。
class Role(object):
def __init__(self, node):
self.node = node
self.node.register(self)
self.running = True
self.logger = node.logger.getChild(type(self).__name__)
def set_timer(self, seconds, callback):
return self.node.network.set_timer(self.node.address, seconds,
lambda: self.running and callback())
def stop(self):
self.running = False
self.node.unregister(self)集群节点拥有的角色通过 `Node` 类粘合在一起，该类代表网络上的单个节点。随着执行的进行，角色会被添加到节点中并从节点中移除。到达节点的消息被转发到所有活动角色，调用一个以消息类型命名的具有 `do_` 前缀的方法。这些 `do_` 方法以关键字参数的形式接收消息的属性，以便于访问。`Node` 类还提供了一个 `send` 方法作为便利，使用 `functools.partial` 为 `Network` 类的相同方法提供一些参数。
class Node(object):
unique_ids = itertools.count()
def __init__(self, network, address):
self.network = network
self.address = address or 'N%d' % self.unique_ids.next()
self.logger = SimTimeLogger(
logging.getLogger(self.address), {'network': self.network})
self.logger.info('starting')
self.roles = []
self.send = functools.partial(self.network.send, self)
def register(self, roles):
self.roles.append(roles)
def unregister(self, roles):
self.roles.remove(roles)
def receive(self, sender, message):
handler_name = 'do_%s' % type(message).__name__
for comp in self.roles[:]:
if not hasattr(comp, handler_name):
continue
comp.logger.debug("received %s from %s", message, sender)
fn = getattr(comp, handler_name)
fn(sender=sender, **message._asdict())
应用程序在每个集群成员上创建并启动一个 `Member` 对象，提供一个特定于应用程序的状态机和一个对等列表。成员对象如果加入的是现有集群，则向节点添加一个引导角色；如果创建的是新的集群，则添加一个种子角色。然后，它在一个单独的线程中运行协议（通过 `Network.run`）。
应用程序通过 `invoke` 方法与集群交互，该方法启动一个用于状态转换的提案。一旦该提案被决定并且状态机运行，`invoke` 将返回机器的输出。该方法使用一个简单的同步 `Queue` 来等待协议线程的结果。
class Member(object):
def __init__(self, state_machine, network, peers, seed=None,
seed_cls=Seed, bootstrap_cls=Bootstrap):
self.network = network
self.node = network.new_node()
if seed is not None:
self.startup_role = seed_cls(self.node, initial_state=seed, peers=peers,
execute_fn=state_machine)
else:
self.startup_role = bootstrap_cls(self.node,
execute_fn=state_machine, peers=peers)
self.requester = None
def start(self):
self.startup_role.start()
self.thread = threading.Thread(target=self.network.run)
self.thread.start()
def invoke(self, input_value, request_cls=Requester):
assert self.requester is None
q = Queue.Queue()
self.requester = request_cls(self.node, input_value, q.put)
self.requester.start()
output = q.get()
self.requester = None
return output让我们逐个看一下库中的每个角色类。
`Acceptor` 类实现了协议中的接受者角色，因此它必须存储代表其最新承诺的选票号码，以及每个时隙接受的提议集。然后，它根据协议响应 `Prepare` 和 `Accept` 消息。结果是一个简短的类，很容易与协议进行比较。
对于接受者来说，Multi-Paxos 看起来非常像 Simple Paxos，只是在消息中添加了时隙号码。
class Acceptor(Role):
def __init__(self, node):
super(Acceptor, self).__init__(node)
self.ballot_num = NULL_BALLOT
self.accepted_proposals = {} # {slot: (ballot_num, proposal)}
def do_Prepare(self, sender, ballot_num):
if ballot_num > self.ballot_num:
self.ballot_num = ballot_num
# we've heard from a scout, so it might be the next leader
self.node.send([self.node.address], Accepting(leader=sender))
self.node.send([sender], Promise(
ballot_num=self.ballot_num,
accepted_proposals=self.accepted_proposals
))
def do_Accept(self, sender, ballot_num, slot, proposal):
if ballot_num >= self.ballot_num:
self.ballot_num = ballot_num
acc = self.accepted_proposals
if slot not in acc or acc[slot][0] < ballot_num:
acc[slot] = (ballot_num, proposal)
self.node.send([sender], Accepted(
slot=slot, ballot_num=self.ballot_num))`Replica` 类是最复杂的角色类，因为它有一些紧密相关的职责
副本响应来自客户端的 `Invoke` 消息创建新的提案，选择它认为未使用的时隙，并将 `Propose` 消息发送到当前领导者（图 3.2。）此外，如果所选时隙的共识是针对不同的提案，则副本必须使用新的时隙重新提出提案。
图 3.2 - 副本角色控制流程
`Decision` 消息代表集群已达成共识的时隙。在这里，副本存储新决定，然后运行状态机，直到它到达未决定的时隙。副本区分集群已同意的 *已决定* 时隙，与本地状态机已处理的 *已提交* 时隙。当时隙按顺序决定时，已提交的提案可能会滞后，等待下一个时隙被决定。当一个时隙被提交时，每个副本向请求者发送一个 `Invoked` 消息，其中包含操作的结果。
在某些情况下，一个时隙可能没有活动提案，也没有决定。状态机需要逐个执行时隙，因此集群必须就某些东西达成共识来填充该时隙。为了防止这种情况，副本在赶上一个时隙时会进行一个“无操作”提案。如果这样的提案最终被决定，那么状态机对该时隙不做任何操作。
同样，同一个提案也可能被决定两次。副本跳过对任何此类重复提案调用状态机，对该时隙不执行任何转换。
副本需要知道哪个节点是活动领导者，以便向其发送 `Propose` 消息。正如我们将在后面看到的那样，要做到这一点需要惊人的细致。每个副本使用三个信息来源跟踪活动领导者。
当领导者角色变为活动状态时，它会向同一个节点上的副本发送 `Adopted` 消息（图 3.3）。
图 3.3 - Adopted
当接受者角色向新领导者发送 `Promise` 时，它会向其本地副本发送 `Accepting` 消息（图 3.4）。
图 3.4 - Accepting
活动领导者会发送 `Active` 消息作为心跳（图 3.5）。如果在 `LEADER_TIMEOUT` 超时之前没有收到此类消息，副本将假设领导者已死，并继续进行到下一个领导者。在这种情况下，重要的是所有副本选择同一个新领导者，我们通过对成员进行排序并选择列表中的下一个成员来实现这一点。
图 3.5 - Active
最后，当一个节点加入网络时，引导角色会发送一个 `Join` 消息（图 3.6）。副本会响应一个 `Welcome` 消息，其中包含其最新的状态，允许新节点快速赶上进度。
图 3.6 - Bootstrap
class Replica(Role):
def __init__(self, node, execute_fn, state, slot, decisions, peers):
super(Replica, self).__init__(node)
self.execute_fn = execute_fn
self.state = state
self.slot = slot
self.decisions = decisions
self.peers = peers
self.proposals = {}
# next slot num for a proposal (may lead slot)
self.next_slot = slot
self.latest_leader = None
self.latest_leader_timeout = None
# making proposals
def do_Invoke(self, sender, caller, client_id, input_value):
proposal = Proposal(caller, client_id, input_value)
slot = next((s for s, p in self.proposals.iteritems() if p == proposal), None)
# propose, or re-propose if this proposal already has a slot
self.propose(proposal, slot)
def propose(self, proposal, slot=None):
"""Send (or resend, if slot is specified) a proposal to the leader"""
if not slot:
slot, self.next_slot = self.next_slot, self.next_slot + 1
self.proposals[slot] = proposal
# find a leader we think is working - either the latest we know of, or
# ourselves (which may trigger a scout to make us the leader)
leader = self.latest_leader or self.node.address
self.logger.info(
"proposing %s at slot %d to leader %s" % (proposal, slot, leader))
self.node.send([leader], Propose(slot=slot, proposal=proposal))
# handling decided proposals
def do_Decision(self, sender, slot, proposal):
assert not self.decisions.get(self.slot, None), \
"next slot to commit is already decided"
if slot in self.decisions:
assert self.decisions[slot] == proposal, \
"slot %d already decided with %r!" % (slot, self.decisions[slot])
return
self.decisions[slot] = proposal
self.next_slot = max(self.next_slot, slot + 1)
# re-propose our proposal in a new slot if it lost its slot and wasn't a no-op
our_proposal = self.proposals.get(slot)
if (our_proposal is not None and
our_proposal != proposal and our_proposal.caller):
self.propose(our_proposal)
# execute any pending, decided proposals
while True:
commit_proposal = self.decisions.get(self.slot)
if not commit_proposal:
break # not decided yet
commit_slot, self.slot = self.slot, self.slot + 1
self.commit(commit_slot, commit_proposal)
def commit(self, slot, proposal):
"""Actually commit a proposal that is decided and in sequence"""
decided_proposals = [p for s, p in self.decisions.iteritems() if s < slot]
if proposal in decided_proposals:
self.logger.info(
"not committing duplicate proposal %r, slot %d", proposal, slot)
return # duplicate
self.logger.info("committing %r at slot %d" % (proposal, slot))
if proposal.caller is not None:
# perform a client operation
self.state, output = self.execute_fn(self.state, proposal.input)
self.node.send([proposal.caller],
Invoked(client_id=proposal.client_id, output=output))
# tracking the leader
def do_Adopted(self, sender, ballot_num, accepted_proposals):
self.latest_leader = self.node.address
self.leader_alive()
def do_Accepting(self, sender, leader):
self.latest_leader = leader
self.leader_alive()
def do_Active(self, sender):
if sender != self.latest_leader:
return
self.leader_alive()
def leader_alive(self):
if self.latest_leader_timeout:
self.latest_leader_timeout.cancel()
def reset_leader():
idx = self.peers.index(self.latest_leader)
self.latest_leader = self.peers[(idx + 1) % len(self.peers)]
self.logger.debug("leader timed out; tring the next one, %s",
self.latest_leader)
self.latest_leader_timeout = self.set_timer(LEADER_TIMEOUT, reset_leader)
# adding new cluster members
def do_Join(self, sender):
if sender in self.peers:
self.node.send([sender], Welcome(
state=self.state, slot=self.slot, decisions=self.decisions))领导者的主要任务是接收请求新选票的 `Propose` 消息并做出决定。领导者在成功执行了协议的 `Prepare` / `Promise` 部分时处于“活动”状态。活动领导者可以立即发送 `Accept` 消息来响应 `Propose`。
为了符合每个角色一个类的模型，领导者委托给侦察员和指挥官角色来执行协议的每个部分。
class Leader(Role):
def __init__(self, node, peers, commander_cls=Commander, scout_cls=Scout):
super(Leader, self).__init__(node)
self.ballot_num = Ballot(0, node.address)
self.active = False
self.proposals = {}
self.commander_cls = commander_cls
self.scout_cls = scout_cls
self.scouting = False
self.peers = peers
def start(self):
# reminder others we're active before LEADER_TIMEOUT expires
def active():
if self.active:
self.node.send(self.peers, Active())
self.set_timer(LEADER_TIMEOUT / 2.0, active)
active()
def spawn_scout(self):
assert not self.scouting
self.scouting = True
self.scout_cls(self.node, self.ballot_num, self.peers).start()
def do_Adopted(self, sender, ballot_num, accepted_proposals):
self.scouting = False
self.proposals.update(accepted_proposals)
# note that we don't re-spawn commanders here; if there are undecided
# proposals, the replicas will re-propose
self.logger.info("leader becoming active")
self.active = True
def spawn_commander(self, ballot_num, slot):
proposal = self.proposals[slot]
self.commander_cls(self.node, ballot_num, slot, proposal, self.peers).start()
def do_Preempted(self, sender, slot, preempted_by):
if not slot: # from the scout
self.scouting = False
self.logger.info("leader preempted by %s", preempted_by.leader)
self.active = False
self.ballot_num = Ballot((preempted_by or self.ballot_num).n + 1,
self.ballot_num.leader)
def do_Propose(self, sender, slot, proposal):
if slot not in self.proposals:
if self.active:
self.proposals[slot] = proposal
self.logger.info("spawning commander for slot %d" % (slot,))
self.spawn_commander(self.ballot_num, slot)
else:
if not self.scouting:
self.logger.info("got PROPOSE when not active - scouting")
self.spawn_scout()
else:
self.logger.info("got PROPOSE while scouting; ignored")
else:
self.logger.info("got PROPOSE for a slot already being proposed")当领导者想要变为活动状态时，它会创建侦察员角色，响应在它处于非活动状态时接收到的 `Propose`（图 3.7）。侦察员发送（并在必要时重新发送）`Prepare` 消息，并收集 `Promise` 响应，直到它从大多数对等节点处收到响应，或者直到它被抢占。它分别通过 `Adopted` 或 `Preempted` 向领导者进行回传。
图 3.7 - Scout
class Scout(Role):
def __init__(self, node, ballot_num, peers):
super(Scout, self).__init__(node)
self.ballot_num = ballot_num
self.accepted_proposals = {}
self.acceptors = set([])
self.peers = peers
self.quorum = len(peers) / 2 + 1
self.retransmit_timer = None
def start(self):
self.logger.info("scout starting")
self.send_prepare()
def send_prepare(self):
self.node.send(self.peers, Prepare(ballot_num=self.ballot_num))
self.retransmit_timer = self.set_timer(PREPARE_RETRANSMIT, self.send_prepare)
def update_accepted(self, accepted_proposals):
acc = self.accepted_proposals
for slot, (ballot_num, proposal) in accepted_proposals.iteritems():
if slot not in acc or acc[slot][0] < ballot_num:
acc[slot] = (ballot_num, proposal)
def do_Promise(self, sender, ballot_num, accepted_proposals):
if ballot_num == self.ballot_num:
self.logger.info("got matching promise; need %d" % self.quorum)
self.update_accepted(accepted_proposals)
self.acceptors.add(sender)
if len(self.acceptors) >= self.quorum:
# strip the ballot numbers from self.accepted_proposals, now that it
# represents a majority
accepted_proposals = \
dict((s, p) for s, (b, p) in self.accepted_proposals.iteritems())
# We're adopted; note that this does *not* mean that no other
# leader is active. # Any such conflicts will be handled by the
# commanders.
self.node.send([self.node.address],
Adopted(ballot_num=ballot_num,
accepted_proposals=accepted_proposals))
self.stop()
else:
# this acceptor has promised another leader a higher ballot number,
# so we've lost
self.node.send([self.node.address],
Preempted(slot=None, preempted_by=ballot_num))
self.stop()领导者为每个它拥有活动提案的时隙创建一个指挥官角色（图 3.8）。与侦察员一样，指挥官发送并重新发送 `Accept` 消息，并等待大多数接受者回复 `Accepted`，或者等待有关其抢占的消息。当一个提案被接受时，指挥官会向所有节点广播 `Decision` 消息。它通过 `Decided` 或 `Preempted` 向领导者进行响应。
图 3.8 - Commander
class Commander(Role):
def __init__(self, node, ballot_num, slot, proposal, peers):
super(Commander, self).__init__(node)
self.ballot_num = ballot_num
self.slot = slot
self.proposal = proposal
self.acceptors = set([])
self.peers = peers
self.quorum = len(peers) / 2 + 1
def start(self):
self.node.send(set(self.peers) - self.acceptors, Accept(
slot=self.slot, ballot_num=self.ballot_num, proposal=self.proposal))
self.set_timer(ACCEPT_RETRANSMIT, self.start)
def finished(self, ballot_num, preempted):
if preempted:
self.node.send([self.node.address],
Preempted(slot=self.slot, preempted_by=ballot_num))
else:
self.node.send([self.node.address],
Decided(slot=self.slot))
self.stop()
def do_Accepted(self, sender, slot, ballot_num):
if slot != self.slot:
return
if ballot_num == self.ballot_num:
self.acceptors.add(sender)
if len(self.acceptors) < self.quorum:
return
self.node.send(self.peers, Decision(
slot=self.slot, proposal=self.proposal))
self.finished(ballot_num, False)
else:
self.finished(ballot_num, True)顺便说一句，在开发过程中，这里出现了一个非常微妙的错误。当时，网络模拟器即使在节点内的消息中也引入了数据包丢失。当所有 `Decision` 消息都丢失时，协议就无法继续进行。副本继续重新传输 `Propose` 消息，但领导者忽略了它们，因为它已经对该时隙有了提案。副本的赶上进程无法找到结果，因为没有副本听说过这个决定。解决方案是确保本地消息始终被传递，就像真实网络堆栈的情况一样。
当一个节点加入集群时，它必须在参与之前确定当前集群状态。引导角色通过依次向每个对等节点发送 `Join` 消息，直到收到 `Welcome` 消息，来处理这种情况。引导的通信图如上面 副本 中所示。
早期版本的实现让每个节点都有一组完整的角色（副本、领导者和接受者），每个角色都从“启动”阶段开始，等待来自 `Welcome` 消息的信息。这将初始化逻辑分散到每个角色中，需要对每个角色进行单独的测试。最终的设计让引导角色在启动完成后将每个其他角色添加到节点中，并将初始状态传递给它们的构造函数。
class Bootstrap(Role):
def __init__(self, node, peers, execute_fn,
replica_cls=Replica, acceptor_cls=Acceptor, leader_cls=Leader,
commander_cls=Commander, scout_cls=Scout):
super(Bootstrap, self).__init__(node)
self.execute_fn = execute_fn
self.peers = peers
self.peers_cycle = itertools.cycle(peers)
self.replica_cls = replica_cls
self.acceptor_cls = acceptor_cls
self.leader_cls = leader_cls
self.commander_cls = commander_cls
self.scout_cls = scout_cls
def start(self):
self.join()
def join(self):
self.node.send([next(self.peers_cycle)], Join())
self.set_timer(JOIN_RETRANSMIT, self.join)
def do_Welcome(self, sender, state, slot, decisions):
self.acceptor_cls(self.node)
self.replica_cls(self.node, execute_fn=self.execute_fn, peers=self.peers,
state=state, slot=slot, decisions=decisions)
self.leader_cls(self.node, peers=self.peers, commander_cls=self.commander_cls,
scout_cls=self.scout_cls).start()
self.stop()在正常操作中，当一个节点加入集群时，它期望找到一个正在运行的集群，并且至少有一个节点愿意响应 `Join` 消息。但是集群是如何启动的呢？一种选择是让引导角色在尝试联系所有其他节点后，确定它是集群中的第一个。但这样做有两个问题。首先，对于大型集群来说，这意味着在每个 `Join` 超时时要等待很长时间。更重要的是，在网络分区的情况下，一个新节点可能无法联系到任何其他节点，从而启动一个新的集群。
网络分区是集群应用中最具挑战性的故障情况。在网络分区中，所有集群成员都保持存活，但某些成员之间的通信失败。例如，如果连接柏林和台北节点的集群的网络链路发生故障，则网络将被分区。如果集群的两个部分在分区期间继续运行，则在网络链路恢复后重新加入这两个部分可能具有挑战性。在 Multi-Paxos 的情况下，修复后的网络将托管两个具有相同时隙号的不同决策的集群。
为了避免这种结果，创建新的集群是用户指定的操作。集群中的恰好一个节点运行 seed 角色，其他节点像往常一样运行 bootstrap。seed 等待收到来自其大多数对等体的 Join 消息，然后发送包含状态机初始状态和空决策集的 Welcome。然后，seed 角色停止自身并启动 bootstrap 角色以加入新播种的集群。
seed 模拟了 bootstrap/副本交互的 Join/Welcome 部分，因此其通信图与副本角色相同。
class Seed(Role):
def __init__(self, node, initial_state, execute_fn, peers,
bootstrap_cls=Bootstrap):
super(Seed, self).__init__(node)
self.initial_state = initial_state
self.execute_fn = execute_fn
self.peers = peers
self.bootstrap_cls = bootstrap_cls
self.seen_peers = set([])
self.exit_timer = None
def do_Join(self, sender):
self.seen_peers.add(sender)
if len(self.seen_peers) <= len(self.peers) / 2:
return
# cluster is ready - welcome everyone
self.node.send(list(self.seen_peers), Welcome(
state=self.initial_state, slot=1, decisions={}))
# stick around for long enough that we don't hear any new JOINs from
# the newly formed cluster
if self.exit_timer:
self.exit_timer.cancel()
self.exit_timer = self.set_timer(JOIN_RETRANSMIT * 2, self.finish)
def finish(self):
# bootstrap this node into the cluster we just seeded
bs = self.bootstrap_cls(self.node,
peers=self.peers, execute_fn=self.execute_fn)
bs.start()
self.stop()请求者角色管理对分布式状态机的请求。角色类只是将 Invoke 消息发送到本地副本，直到收到相应的 Invoked。有关此角色的通信图，请参见上面的“副本”部分。
class Requester(Role):
client_ids = itertools.count(start=100000)
def __init__(self, node, n, callback):
super(Requester, self).__init__(node)
self.client_id = self.client_ids.next()
self.n = n
self.output = None
self.callback = callback
def start(self):
self.node.send([self.node.address],
Invoke(caller=self.node.address,
client_id=self.client_id, input_value=self.n))
self.invoke_timer = self.set_timer(INVOKE_RETRANSMIT, self.start)
def do_Invoked(self, sender, client_id, output):
if client_id != self.client_id:
return
self.logger.debug("received output %r" % (output,))
self.invoke_timer.cancel()
self.callback(output)
self.stop()回顾一下，集群的角色是
Prepare/Promise 部分Accept/Accepted 部分要使集群运行，只需要再添加一件设备：所有节点通信的网络。
任何网络协议都需要发送和接收消息的能力以及在未来某个时间调用函数的方法。
Network 类提供了一个具有这些功能的简单模拟网络，还模拟了数据包丢失和消息传播延迟。
计时器使用 Python 的 heapq 模块处理，允许高效地选择下一个事件。设置计时器涉及将 Timer 对象推入堆中。由于从堆中删除项目效率低下，因此已取消的计时器将保留在原位，但标记为已取消。
消息传输使用计时器功能在每个节点上调度稍后发送消息，使用随机模拟的延迟。我们再次使用 functools.partial 来设置对目标节点的 receive 方法的未来调用，并带有适当的参数。
运行模拟只需从堆中弹出计时器并在它们没有被取消且目标节点仍然活动的情况下执行它们。
class Timer(object):
def __init__(self, expires, address, callback):
self.expires = expires
self.address = address
self.callback = callback
self.cancelled = False
def __cmp__(self, other):
return cmp(self.expires, other.expires)
def cancel(self):
self.cancelled = True
class Network(object):
PROP_DELAY = 0.03
PROP_JITTER = 0.02
DROP_PROB = 0.05
def __init__(self, seed):
self.nodes = {}
self.rnd = random.Random(seed)
self.timers = []
self.now = 1000.0
def new_node(self, address=None):
node = Node(self, address=address)
self.nodes[node.address] = node
return node
def run(self):
while self.timers:
next_timer = self.timers[0]
if next_timer.expires > self.now:
self.now = next_timer.expires
heapq.heappop(self.timers)
if next_timer.cancelled:
continue
if not next_timer.address or next_timer.address in self.nodes:
next_timer.callback()
def stop(self):
self.timers = []
def set_timer(self, address, seconds, callback):
timer = Timer(self.now + seconds, address, callback)
heapq.heappush(self.timers, timer)
return timer
def send(self, sender, destinations, message):
sender.logger.debug("sending %s to %s", message, destinations)
# avoid aliasing by making a closure containing distinct deep copy of
# message for each dest
def sendto(dest, message):
if dest == sender.address:
# reliably deliver local messages with no delay
self.set_timer(sender.address, 0,
lambda: sender.receive(sender.address, message))
elif self.rnd.uniform(0, 1.0) > self.DROP_PROB:
delay = self.PROP_DELAY + self.rnd.uniform(-self.PROP_JITTER,
self.PROP_JITTER)
self.set_timer(dest, delay,
functools.partial(self.nodes[dest].receive,
sender.address, message))
for dest in (d for d in destinations if d in self.nodes):
sendto(dest, copy.deepcopy(message))虽然本实现中没有包含，但组件模型允许我们替换真实世界的网络实现，在真实网络上的实际服务器之间进行通信，而无需对其他组件进行任何更改。测试和调试可以使用模拟网络进行，库的生产使用在真实网络硬件上运行。
在开发这样一个复杂的系统时，错误很快就会从微不足道的错误（如简单的 NameError）转变为只有在几分钟（模拟）协议操作后才会出现的模糊错误。追查此类错误涉及从错误变得明显的点开始回溯。交互式调试器在这里毫无用处，因为它们只能向前逐步执行。
集群中最重要的调试功能是确定性模拟器。与真实网络不同，它在每次运行时都会以完全相同的方式运行，前提是随机数生成器的种子相同。这意味着我们可以将其他调试检查或输出添加到代码中，并重新运行模拟以更详细地查看相同的错误。
当然，其中大部分细节都在集群中节点交换的消息中，因此这些消息会自动完整地记录下来。该日志记录包括发送或接收消息的角色类，以及通过 SimTimeLogger 类注入的模拟时间戳。
class SimTimeLogger(logging.LoggerAdapter):
def process(self, msg, kwargs):
return "T=%.3f %s" % (self.extra['network'].now, msg), kwargs
def getChild(self, name):
return self.__class__(self.logger.getChild(name),
{'network': self.extra['network']})像这样的弹性协议通常可以在错误触发后长时间运行。例如，在开发过程中，数据别名错误导致所有副本共享相同的 decisions 字典。这意味着一旦在一个节点上处理了决策，所有其他节点都会将其视为已经决定。即使存在这个严重错误，集群在死锁之前也为几个事务生成了正确的结果。
断言是及早捕获此类错误的重要工具。断言应包含算法设计中的任何不变式，但当代码的行为不符合我们的预期时，断言我们的预期是查看事物偏离轨道的绝佳方法。
assert not self.decisions.get(self.slot, None), \
"next slot to commit is already decided"
if slot in self.decisions:
assert self.decisions[slot] == proposal, \
"slot %d already decided with %r!" % (slot, self.decisions[slot])在阅读代码时识别我们做出的正确假设是调试艺术的一部分。在此来自 Replica.do_Decision 的代码中，问题在于 Decision 正在被忽略，因为下一个要提交的时隙已经在 self.decisions 中。被违反的潜在假设是下一个要提交的时隙尚未决定。在 do_Decision 的开头断言这一点可以识别缺陷并快速修复。类似地，其他错误会导致在同一个时隙中决定不同的提案——一个严重的错误。
在协议开发过程中添加了许多其他断言，但为了节省空间，只保留了一些。
在过去十年中的某个时间，没有测试的编码终于变得和没有安全带驾驶一样疯狂。没有测试的代码可能不正确，修改代码在没有方法查看其行为是否已更改的情况下很危险。
当代码组织得便于测试时，测试最为有效。在该领域有几个活跃的思想流派，但我们采用的方法是将代码分解成小的、最小连接的单元，可以单独进行测试。这与角色模型很好地一致，在角色模型中，每个角色都有特定的目的，并且可以独立于其他角色运行，从而产生一个紧凑、自包含的类。
集群被编写为最大程度地实现这种隔离：角色之间的所有通信都通过消息进行，除了创建新角色之外。因此，在大多数情况下，可以通过向角色发送消息并观察它们的响应来测试角色。
集群的单元测试简单而短小
class Tests(utils.ComponentTestCase):
def test_propose_active(self):
"""A PROPOSE received while active spawns a commander."""
self.activate_leader()
self.node.fake_message(Propose(slot=10, proposal=PROPOSAL1))
self.assertCommanderStarted(Ballot(0, 'F999'), 10, PROPOSAL1)此方法测试单个单元（Leader 类）的单个行为（指挥官生成）。它遵循众所周知的“安排、行动、断言”模式：设置一个活动的领导者，向它发送一条消息，并检查结果。
我们使用一种称为“依赖注入”的技术来处理新角色的创建。每个向网络添加其他角色的角色类都将一组类对象作为构造函数参数，默认为实际类。例如，Leader 的构造函数如下所示
class Leader(Role):
def __init__(self, node, peers, commander_cls=Commander, scout_cls=Scout):
super(Leader, self).__init__(node)
self.ballot_num = Ballot(0, node.address)
self.active = False
self.proposals = {}
self.commander_cls = commander_cls
self.scout_cls = scout_cls
self.scouting = False
self.peers = peersspawn_scout 方法（以及类似的 spawn_commander）使用 self.scout_cls 创建新的角色对象
class Leader(Role):
def spawn_scout(self):
assert not self.scouting
self.scouting = True
self.scout_cls(self.node, self.ballot_num, self.peers).start()此技术的魔力在于，在测试中，Leader 可以使用假类，从而可以单独测试，与 Scout 和 Commander 分开。
关注小型单元的一个弊端是它不会测试单元之间的接口。例如，验收者角色的单元测试验证了 Promise 消息的 accepted 属性的格式，而侦察者角色的单元测试为该属性提供了格式良好的值。这两个测试都没有检查这些格式是否匹配。
解决此问题的一种方法是使接口自我强制。在集群中，使用命名元组和关键字参数可以避免对消息属性的任何分歧。由于角色类之间唯一的交互是通过消息，因此这涵盖了接口的很大一部分。
对于 accepted_proposals 格式等特定问题，可以使用相同的函数验证真实数据和测试数据，在本例中为 verifyPromiseAccepted。验收者的测试使用此方法来验证每个返回的 Promise，而侦察者的测试使用它来验证每个假的 Promise。
防止接口问题和设计错误的最后一道防线是集成测试。集成测试将多个单元组合在一起并测试其组合效果。在我们的例子中，这意味着构建一个由多个节点组成的网络，向其中注入一些请求，并验证结果。如果单元测试中没有发现任何接口问题，那么它们应该会导致集成测试快速失败。
由于该协议旨在优雅地处理节点故障，因此我们还测试了一些故障场景，包括活动领导者的意外故障。
集成测试比单元测试更难编写，因为它们的隔离程度较低。对于集群来说，这在测试失败的领导者时最为明显，因为任何节点都可能是活动领导者。即使使用确定性网络，一条消息的更改也会改变随机数生成器的状态，从而不可预测地改变后续事件。测试代码不必硬编码预期的领导者，而是必须深入研究每个领导者的内部状态以找到认为自己处于活动状态的领导者。
测试弹性代码非常困难：它很可能对自身的错误具有弹性，因此集成测试可能无法检测到非常严重的错误。也很难想象和构建测试以应对所有可能的故障模式。
解决此类问题的常用方法是“模糊测试”：使用随机变化的输入重复运行代码，直到出现故障。当出现故障时，所有调试支持都变得至关重要：如果故障无法重现，日志记录信息不足以找到错误，那么就无法修复！
我在开发过程中对集群进行了一些手动模糊测试，但完整的模糊测试基础设施超出了本项目的范围。
具有许多活动领导者的集群是一个非常嘈杂的地方，侦察员向验收者发送不断增加的投票数，但没有投票被决定。没有活动领导者的集群很安静，但同样不起作用。平衡实现，以便集群几乎总是就一个领导者达成一致，这非常困难。
避免领导者争斗很容易：当被抢先时，领导者只接受其新的非活动状态。但是，这很容易导致没有活动领导者的案例，因此非活动领导者将在每次收到 Propose 消息时尝试变为活动状态。
如果整个集群不同意哪个成员是活动领导者，就会出现问题：不同的副本向不同的领导者发送 Propose 消息，导致侦察员发生冲突。因此，重要的是领导者选举要快速决定，并且所有集群成员都要尽快了解结果。
集群通过尽快检测到领导者变更来处理这个问题：当一个接受者发送一个Promise时，很有可能被承诺的成员将成为下一个领导者。故障通过心跳协议检测到。
当然，有很多方法可以扩展和改进这个实现。
在“纯粹”的多Paxos中，未能接收消息的节点可能比集群中的其他节点落后许多槽位。只要分布式状态机的状态从未被访问，除非通过状态机转换，这种设计是可行的。为了从状态中读取，客户端请求一个实际上不改变状态的状态机转换，但返回所需的值。这个转换在整个集群中执行，确保它根据提案所在的槽位返回相同的值，无论在哪里。
即使在最佳情况下，这也是很慢的，需要多次往返才能读取一个值。如果一个分布式对象存储为每个对象访问发出这样的请求，它的性能将非常糟糕。但是，当接收请求的节点落后时，请求延迟会更大，因为该节点必须赶上集群中的其他节点才能成功提出提案。
一个简单的解决方案是实现一个类似八卦的协议，其中每个副本定期联系其他副本，以共享它所知道的最高槽位，并请求未知槽位的信息。这样，即使Decision消息丢失了，副本也能很快从其对等节点之一处获知该决定。
一个集群管理库在不可靠的组件存在的情况下提供可靠性。它不应该添加自己的不可靠性。不幸的是，集群在内存使用和消息大小不断增长的情况下，不会运行很长时间而不出现故障。
在协议定义中，接受者和副本构成了协议的“内存”，因此它们需要记住所有内容。这些类永远不知道它们什么时候会收到对旧槽位的请求，可能是来自落后的副本或领导者。为了保持正确性，它们会保存从集群启动以来的所有决定的列表。更糟糕的是，这些决定在副本之间以Welcome消息的形式传输，这使得这些消息在长期运行的集群中变得非常庞大。
解决此问题的一种技术是定期对每个节点的状态进行“检查点”，保留有关一些有限数量的决策的信息。那些已经过时到没有提交所有检查点前的槽位的节点必须通过离开并重新加入集群来“重置”自己。
虽然集群成员中少数成员发生故障是可以接受的，但接受者“忘记”它接受的任何值或做出的任何承诺是不可接受的。
不幸的是，这正是集群成员发生故障并重新启动时发生的情况：新初始化的 Acceptor 实例没有记录其前任做出的承诺。问题是，新启动的实例取代了旧的实例。
解决这个问题有两种方法。更简单的解决方案是将接受者状态写入磁盘，并在启动时重新读取该状态。更复杂的解决方案是从集群中删除失败的集群成员，并要求将新成员添加到集群中。这种对集群成员资格的动态调整称为“视图变更”。
运维人员需要能够调整集群的大小以满足负载和可用性要求。一个简单的测试项目可能从一个最小的三节点集群开始，其中任何一个节点都可以发生故障而不会影响。但是，当该项目“上线”时，额外的负载将需要一个更大的集群。
集群，正如所写，无法在不重启整个集群的情况下更改集群中的对等节点集。理想情况下，集群能够就其成员资格达成共识，就像它对状态机转换达成共识一样。这意味着，集群成员集（视图）可以通过特殊的视图变更提案进行更改。但是 Paxos 算法依赖于对集群中成员的普遍一致，因此我们必须为每个槽位定义视图。
Lamport 在“Paxos Made Simple”的最后一段中解决了这一挑战
我们可以允许领导者提前获得\(\alpha\)个命令，方法是让执行共识算法的第\(i+\alpha\)个实例的服务器集由执行第\(i\)个状态机命令后的状态指定。（Lamport，2001）
这个想法是，Paxos（槽位）的每个实例都使用\(\alpha\)个槽位之前的视图。这允许集群在任何时候最多处理\(\alpha\)个槽位，因此\(\alpha\)的值非常小会限制并发性，而\(\alpha\)的值非常大则会导致视图变更生效速度变慢。
在这个实现的早期草稿中（忠实地保存在 git 历史记录中！），我实现了对视图变更的支持（使用\(\alpha\)代替 3）。这个看似简单的改变引入了很多复杂性
结果对于这本书来说太大了！
除了最初的 Paxos 论文和 Lamport 的后续文章 “Paxos Made Simple”2 之外，我们的实现还添加了受其他一些资源启发的扩展。角色名称取自“Paxos Made Moderately Complex”3。“Paxos Made Live”4 对快照特别有帮助，而 "Paxos Made Practical" 描述了视图变更（尽管不是这里描述的那种类型）。Liskov 的“From Viewstamped Replication to Byzantine Fault Tolerance”5 从另一个角度提供了对视图变更的看法。最后，一个 Stack Overflow 讨论 有助于了解成员如何添加到系统中以及如何从系统中删除。
L. Lamport，“The Part-Time Parliament”，ACM Transactions on Computer Systems，16(2):133–169，1998 年 5 月。↩
L. Lamport，“Paxos Made Simple”，ACM SIGACT News（分布式计算专栏）32，4（第 121 号，2001 年 12 月）51-58。↩
R. Van Renesse 和 D. Altinbuken，“Paxos Made Moderately Complex”，ACM Comp. Survey 47，3，第 42 篇文章（2015 年 2 月）↩
T. Chandra，R. Griesemer 和 J. Redstone，“Paxos Made Live - An Engineering Perspective”，第二十六届 ACM 分布式计算原理研讨会论文集（PODC '07）。ACM，纽约，纽约，美国，398-407。↩
B. Liskov，“From Viewstamped Replication to Byzantine Fault Tolerance”，在 *Replication* 中，Springer-Verlag，柏林，海德堡，121-149（2010）↩