论文地址： Viewstamped复制：支持高可用分布式系统的新主复制方法-Oki&Liskov’88。

    给定一组组成组的协作节点，我们如何将信息复制到组成员，并在组成员来来往往时保持一致的“一个副本可序列化”属性？Oki和Liskov介绍了两个相互关联的协议：一个描述成员和领导稳定时的团队行为，另一个描述团队如何过渡到新的成员和/或领导安排。一组给定的成员（本文中称为队列）和一个指定为领导者（称为主要成员）的组合称为视图。每个视图都有一个唯一的id，在视图中发生的每个事件都有一个唯一的（逻辑）时间戳。视图id和事件时间戳的组合称为viewstamp，纸张从这里派生其名称。

    “会员制”的概念值得澄清。这个概念是在组中有一组固定的成员，当所有成员都正常工作时，所有成员都可以相互通信。其中一个将是主要的。如果存在网络分区或节点出现故障，则会发生视图更改-基本假设是这是临时的，最终将恢复网络连接或重新启动出现故障的节点。添加全新的成员，或者永久性地停用现有的成员，这超出了本文的讨论范围（但我们将在本周晚些时候讨论“重新访问带视图标记的复制”，展示如何适应这一点）。

    80年代后期，人们对分布式系统的希望似乎不大：

    分布式系统的一个潜在好处是它们可以提供高可用性的服务，即在需要时可以启动和访问的服务。
    你会发现很多关于对象和rpc（当时的）的引用，但这篇论文真正让我印象深刻的一点是，整个作品都是在没有完全实现这些想法的情况下完成的！“我们相信我们的方法会比非复制系统表现更好…”，“目前我们正在实施我们的方法，当我们的实现完成后，我们将能够运行关于系统性能的实验。”如此多看似伟大的想法落入了理论和实践之间的鸿沟，以至于我的本能是在一个被证明的实现可用之前暂停信念。当然，这项工作并不仅仅是“空中楼阁”

    网络和进程模型是常见的非拜占庭式故障停止进程，具有丢失、延迟、重复和无序的消息传递。

    我们的复制方法假设一个计算模型，其中一个分布式程序由模块组成，每个模块都驻留在网络的单个节点上。每个模块都包含数据对象和操作对象的代码；模块可以在某些状态完好的情况下从崩溃中恢复。其他模块不能直接访问其他模块的数据对象。相反，每个模块提供可用于访问其对象的过程；模块通过远程过程调用进行通信。进行调用的模块称为客户机；被调用的模块是服务器。

    每个模块都有许多副本实例，通常是3到5个，称为队列。其中一个被指定为主服务器，它处理来自客户端的请求并参与两阶段提交协议。其他的是被动备份，只是从主服务器接收状态信息。

    随着时间的推移，随着队列或通信链路的失败和恢复，组内的通信能力可能会发生变化。为了反映这种不断变化的情况，每个队列都在一个视图中运行。视图是一组能够（或曾经）相互通信的队列，以及哪个队列是主要队列的指示；它是配置的子集，必须包含大多数组成员…因为时间戳仅在视图中有意义，所以我们引入了viewstamp。viewstamp只是一个时间戳，它与生成时间戳的视图的viewid连接在一起。我们保证，对于其历史中的每个viewstamp v，队列的状态从view v反映事件e。id如果e的时间戳小于或等于v的时间戳。

    事务处理保证序列化，并且事务只能在大多数队列知道其事件时提交。视图更改算法保证大多数队列已知的事件在后续视图中继续存在。

    假设事务处理模型是一个带有2PC的分布式事务模型，本文讨论了作为协调器的客户机（不是我要做的设计选择），但也可以将协调移到服务器端组件，而不影响基本算法：

    如果客户端没有被复制，协调器仍然需要高可用性，因为这可以减少两阶段提交中的“漏洞窗口”。这可以通过提供一个复制的“协调服务器”来实现。当客户机启动一个事务，并且当t提交或中止该事务时，它与这样的服务器进行通信。协调服务器代表客户机执行如上所述的两阶段提交。

    与常规事务协议有两个关键区别：viewstamp用于确定事务是否可以提交，而不是在2PC期间将信息写入稳定存储，主服务器通过通信缓冲区将其发送到备份，该缓冲区“向主服务器视图中的所有备份提供事件记录的可靠传递。”

    我们如何将这种“按时间戳顺序将事件记录可靠地传递给所有备份”与关于有损、延迟和无序消息传递的开场假设相协调？答案是，这些保证是在视图中做出的——如果通信缓冲区无法传递消息，那么假设发生了崩溃或通信故障，这将导致视图更改。

    2PC协调器首先向事务中的所有参与者发送一个prepare消息（这个集合在pset中维护，因为远程过程调用是在事务范围内进行的）。当参与者（模块组的主要参与者）收到prepare消息时，它首先检查是否知道在其自身历史记录中的事务期间进行的所有调用。如果没有，就拒绝准备。如果它这样做了，它会强制其缓冲区确保在大多数模块实例（即，它的备份的一小部分）中已知所有已完成的调用事件，然后用accept进行响应。

    如果所有参与者都同意提交，协调器将提交事务。当然，如果任何参与者投票赞成中止，事务将被中止。如果协调器在重复尝试后没有收到参与者的反馈，它首先刷新其缓存的组成员身份知识，然后在有更新视图的情况下重试准备阶段。如果没有，它就会中止。文中给出了处理规则的全部细节，包括如何处理远程过程调用。

    更改视图
    尽管事务处理协议是对以前的内容稍加修改的形式，但视图更改的想法是新的。

    事务处理依赖于强制备份信息，以便大多数队列知道特定事件。视图更改算法的工作是确保大多数队列知道的事件能够存活到后续视图中。它通过确保每个视图至少包含大多数队列并在最新的可能状态下启动新视图来实现这一点。

    这取决于Paxos所依赖的观察结果——如果多数人知道某条信息x，那么任何随后的多数人也必须包括至少一个知道x的成员。

    如果每个视图至少有大多数队列，那么它包含至少一个队列，该队列知道强迫大多数队列执行的任何事件。因此，我们只需要确保新观点的状态包括该群体所知道的。这是使用viewstamp完成的：前一个视图的viewstamp最高的队列的状态用于在新视图中初始化状态。此方案之所以有效，是因为事件记录按时间戳顺序发送到备份，因此对于某个视图，具有较新viewstamp的队列知道对于该视图，具有较早viewstamp的队列所知道的一切。

    队列交换保持活动的消息。任何队列检测到更改（成员返回通信、与现有成员的通信丢失或队列本身正在从崩溃中恢复）时，都会以manager角色启动视图更改协议，其他队列作为下属。

    新的视图管理器创建一个新的视图id，向所有其他队列发送加入视图的邀请，并等待他们的响应。如果视图管理器同时收到具有更高视图id的邀请，则它将接受该邀请并成为下划线。当队列收到视图管理器的邀请时，如果视图id比他们以前看到的任何视图id都高，他们就会接受它，并成为下属。接受可以采取两种形式之一：如果队列是最新的，则发送包含其当前视图戳的正常接受，并指示它是否是当前视图中的主视图；如果队列不是最新的，则发送崩溃接受响应。

    一旦所有队列都响应，或者超时过期，新视图管理器将检查响应，以查看是否可以形成新视图。

    只有满足两个条件，才能成功地形成观点：至少大多数队列必须接受邀请，并且至少其中一个队列必须知道所有来自先前观点的强制信息。后一个条件可能不是真的，如果一些接受是“崩溃”的品种…。如果可以形成视图，则返回最大可视图章（在“正常”接受中）的队列将被选为新的主视图；如果可能，将选择该视图的旧主视图，因为这将在系统中造成最小的中断。

    下属的队列调用await-view以找出决定。如果在指定的超时内没有响应，队列将成为视图管理器并尝试形成新视图。

    即使有多个有效的初选，系统也能正常运行。当它们是一个分区并且旧的主节点很慢地注意到视图更改的需要，并且即使在新视图形成之后也继续响应客户机请求时，可能会出现这种情况。但是，旧的主服务器将无法准备和提交用户事务，因为它无法将它们的影响强加于备份。如果同一群组是视图更改前后的主要群组，则在更改中不会丢失任何用户工作。否则，我们保证以下内容：在旧视图中准备的事务将能够提交，而提交的事务仍将提交。

    作者指出，该算法不能容忍丢失的消息和缓慢的响应。建议“相当长的超时”来缓解这种情况。核心算法还假设将最小信息写入稳定的存储（在崩溃后依靠复制来保存信息）。因此，在一个“灾难”中，导致几个队列全部崩溃的模拟信息丢失是可能的。

    请注意，灾难不会导致组输入缺少某些所需信息的新视图。相反，它使算法不再形成新的视图。

    例如，可以通过在主服务器上使用稳定的存储来增加灾难保护。

    我介绍了这篇文章，因为它先于Paxos（Paxos和Viewstamped复制是在大约80年代后期独立开发的）并且经常被引用。本周晚些时候，我们将看到2012年的论文《重新审视带图章的复制品》（Viewstamped Replication reviewed）（至少对本读者而言）更清楚地阐述了这些想法，其中包括了24年来的进展。如果你只想读一篇关于虚拟现实的论文，我建议你读一篇。