Viewstamped Replication：视图、主副本与盖章请求，不是又一份 Paxos

破除误解#

误解二：主副本复制 1976 年就已经有了，这篇只是给 Alsberg 与 Day 换了个名字。 论文把灵感写给那份主副本技术。原先的方法要求能把节点故障和网络故障分开；一般网络里这两件事观察起来一样，论文因此不要求这份区分。视图是配置的子集，标出谁是主副本，且必须含组成员的多数。通信能力变了就换视图，而不是先判决“宕机还是分区”。备份在后台收事件，提交前才把相关事件强制到足以构成多数的副本。丢失的是未被多数派知道的计算，不是“主副本一死，已提交的事务也死”。

误解三：视图戳就是墙上的钟，或就是 Lamport 时钟 里那种跨进程的先后。 时间戳只在一个视图里有全序，由主副本递增本地计数器产生，每次要把信息告诉备份时发一个。事件包括远程调用做完、准备、提交。换了视图之后旧计数器没有意义，于是把时间戳与产生它的视图标识拼成视图戳。每个副本维护一段历史：按不同视图标识排列的视图戳序列。对其中每一个戳，副本状态里来自该视图的事件，恰好是时间戳不超过它的那些。比较的是“我在这一届里看见了哪一号事件”，不是全球时钟，也不是任意两机之间的因果箭头。

误解四：视图变更就是故障切换脚本；主副本一换，正在跑的事要么全丢，要么全留下。 事务能够提交，仅当它的全部事件已为至少多数派所知。视图变更保证多数派已经知道的事件进入后续视图。两边合在一起，已提交效果跨视图仍在。未被强制到多数派的调用，准备阶段用历史与戳集做兼容检查，对不上就拒绝，事务必须中止。客户端若得不到应答，1988 年的文本选择中止整笔事务，因为无法分辨“还没做”与“做过但视图已换、重做会重复”。嵌套子动作把中止范围收小，这是 Argus 里的检查点，不是切换作业，更不是打断视图变更的说明书。FLP 标明完全异步里慢与死没有可检验的分界；论文假定崩溃终将恢复、分区终将修好，并不声称推翻那条不可能性。

视图、主副本与视图戳#

方法复制的是模块：数据和代码住在一起，外界只能经远程调用进来。若干副本叫做同组伙伴，构成模块组，对外是一个逻辑实体。论文预期每组大约三到五个伙伴。一个被指定为主副本，执行调用并参加两阶段提交；其余是备份，只从主副本接收状态。程序员按不复制的模型写，语言实现再把模块自动复制成组——这是写给 Argus 一类原子事务语言的目标，不是集群配方。正确性口径是单副本可串行化。同步按严格两阶段锁；对象有基版本，事务改试探版本。故障模型明确不是 拜占庭：节点按故障停止崩溃，网络可丢失、延迟、重复或乱序，链路可造成分区。

视图把“此刻谁跟谁还能说话”写成状态：一组当时能够通信的伙伴，外加谁是主副本；它是配置的子集，且必须含组成员的多数。每个视图有唯一且全序的视图标识。1988 年把发起者的成员名与一个更大的计数配成一对，以免并发换届撞号。2012 年的重述把视图收成整数编号，并用编号对副本下标取模来命名主副本——那是后一份对象里的简化，不要读回这十页。事务只在活跃视图里处理。换届协议被写成对 El Abbadi 与 Toueg 虚拟分区的简化。组的可用性上界被地点服务钉住：组名映射到配置，模块组不能比这份目录更可用。

主副本不在每次调用时把备份拉进关键路径。它维护一个通信缓冲，写入事件记录（调用动过哪些对象、持了什么锁、试探版本是什么），按时间戳顺序可靠投递给当前视图里的备份；投递失败则将引起视图变更。写入与强制被分开，类比写稳定存储与强制稳定存储。加入缓冲会原子分配时间戳、推进历史，并返回该事件的视图戳。强制则等到论文所称的次多数——配置里少一票即多数的那批备份——已经知道当前视图中时间戳不超过给定戳的全部事件。次多数知道了，配置的多数也就知道了；多数派知道的信息，换届后仍在。

每做完一次远程调用，服务器主副本盖一个视图戳，放进应答里的戳集。戳集是“组名加视图戳”的对，嵌套调用的戳沿应答向上合并。客户端主副本当地点协调者，把戳集放进准备消息。服务器用历史做兼容检查：对本组每一条戳，必须有同一视图标识且时间戳不小于它的记录。对不上就拒绝准备；对得上，就把缓冲强制到该组最晚那条调用戳，再答应准备。只持读锁的参与者也要强制：否则旧主可能在不知道已经换届时答应准备，而新视图里读锁并未留下。协调者在全体答应后，把“正在提交”记录强制进缓冲，再发提交。用户代码在这条记录被强制之后就可以继续。准备不再单独落一条准备记录，改用历史与戳集判断。

备份按时间戳顺序应用事件，也可以先把“调用完成”存着、等到提交或中止再处理。中止消息不保证到达，任一已经见过对应记录的伙伴都可以回答查询。未复制的客户端可另用复制的协调者服务跑两阶段提交。嵌套事务把“主副本失联就整笔中止”收成只中止该子动作再重做；在调用前强制“开始调用”或先探测主副本都会拖慢正常路径，子动作更便宜。细节在学位论文与 Argus 里，不在这十页。

视图变更要让多数派已经知道的事件进入新视图，并把状态接到尽可能新的地方。每个视图仍含多数，其中至少有一个伙伴知道任何曾被强制到多数派的事件；同一视图里较新的戳包含较旧戳的全部事件，于是取上一视图中视图戳最高的那份状态来初始化即可。伙伴察觉与视图内某人不通、与先前不通的人又通了、或自己刚恢复，就发起换届。崩溃恢复的伙伴标明组状态不可用，只交出视图标识，不交出一份假装完整的记忆。新标识必须高于任何人见过的标识。这些是正确性声明：多数、全序的届次、戳上的前缀知识。不是超时配方，也不是把视图变更当成可攻击接口来拆的说明。

2012 年的重述把思想从 Argus 事务里抽出，改写成复制状态机：请求带编号，主副本把操作编号与视图编号交给备份，收够准备应答后再答复客户端。视图变更、节点重新加入、以及可改组成员与可容忍故障数的重配置，被写成另外的子协议。本页把它当作已发表的对照：方便把 1988 年的视图与戳对上请求日志，并不把缓冲模型作废，更不把它读成部署手册。

论文表明了什么，以及它没有表明的东西#

它表明主副本方法不必先判决“宕机还是分区”。一般网络里这两件事分不开；用多数派视图加上视图戳，提交过的效果在换届后仍在，未进入多数派的计算被中止，单副本可串行化仍然成立。远程调用可以只在主副本上跑，备份走后台缓冲，正常路径延迟可以接近未复制系统。准备往往不必再等，因为“调用完成”记录通常已经在次多数上；提交则强制协调者的“正在提交”记录。若通信比写稳定存储更快、且备份很少，准备与提交可以快于未复制的磁盘路径。这是和磁盘对照的延迟论证，不是吞吐发票。

视图戳足以判断换届后是否还知道这笔事务的事件，而不必每次调用都把备份拉进前台。兼容检查加强制，替代了传统准备记录在崩溃后回答“你能否提交”。嵌套子动作只丢掉失联的那一截，不必在正常路径上为尚未发生的换届付探测代价。地点服务是可用性的天花板。崩溃终将恢复、分区终将修好，是模型假设，不是现场统计。

它没有后来工程报告里那种生产曲线，没有每秒事务数，也没有选举毫秒分布。它不处理拜占庭故障。它没有证明自己与后来刊出的 Paxos 形式等价——那是更晚对照文献的事。HARP 把视图戳复制用进文件服务，是 1991 年 SOSP 的另一份对象。2012 年重述补了恢复与重配置，并声称处理请求与换届可以不写磁盘，同样不是集群配方。

分布式系统 里高可用常被听成“多放几台就行”。这篇对象更窄：能继续处理事务的，是含多数派并把状态接到最高视图戳上的那一届；能提交的，是事件已经写进多数派记忆的请求。数据库与事务 的两阶段提交几乎原样留下，只是稳定存储换成对备份缓冲的强制。把它读成可采购的选主组件，或读成 Raft、ZooKeeper 的操作说明，都离开了纸上的装置。

跨域连接#

• 可靠性工程：故障单元不是“这一台还能不能 ping 通”，而是“当前视图是否仍含配置的多数、以及事件是否已为多数派所知”。Alsberg 与 Day 要求先把节点故障和网络故障分开；一般网络里两者观察起来一样，论文用换届而不是用一次正确分类来继续服务。地点服务把组名映射到配置，模块组不能比这份目录更可用。崩溃恢复的伙伴必须承认组状态作废，不能带着空白内存冒充上一届的记忆。这是把失效模式写进复制手续，不是把五台机器摆进三个机架的作业。
• 信息不对称：主副本先看见调用的效果，备份按缓冲落后。强制是付费把私有观察变成多数派的共同记忆；未强制的事件在换届后可以消失，于是准备消息携带戳集，让对方用历史核对“你以为我知道的，我是否还知道”。客户端在失联时选择中止，是承认无法分辨“那边没做”与“做过但记忆已换届”，不肯用猜测填平不对称。查询允许任一知情的伙伴回答结局，因为中止通知本身也不保证到达。2012 年把请求编号交给客户端，是后一份对象里处理这同一不对称的另一种写法。
• 立法机构：视图像必须凑够法定人数才能开会的届次，视图标识像全序的会期编号，主副本像这一届被点名主持的人。纪要不是全球日历，而是“本届第几号事件已经写入”的戳；新一届要拿到上一届里最完整的那一份来开场，以免已通过的决议消失。准备阶段核对戳集，像表决前宣读各委员会的记录是否还在。比喻能讲清出缺、届次和纪要，不能把这份方法读成《兼职议会》里的提案与选票，也不能读成可采购的议事规则。法定人数保护的是“已被多数听见的事件不丢”，不是保证每一届都会在有限时间内开成。
• 认识论：组状态里的对象是世界里的事实；视图戳是一份关于知识的声明——“在这一届里，我的状态已包含时间戳不超过它的事件”。历史把多届声明串起来。兼容检查问的是：协调者带来的“哪些调用已经发生”的证词，能否被本地知识支撑。支撑得了才可提交；支撑不了就必须拒绝，而不能把缺失说成已知。强制把“我知道”变成“多数派也知道”，换届后这份知识仍能被新主继承。未被强制的计算可以从公共知识里消失，对应事务必须中止。工程事故常发生在把主副本内存里尚未盖章的效果，当成已经可向全组引用的知识。
• 概率论：组的规模写在大约三到五个伙伴，多数派与次多数按这份固定配置来数，而不是按随机图上的渗流阈值来数。可用性论证依赖崩溃与分区最终结束，以及相关故障不会把多数派同时拿走——这是模型假设，不是独立故障乘积公式里的年可用性。视图标识用成员名配对计数来避免相撞，处理的是并发换届的唯一性，不是散列碰撞概率。正常路径上“准备往往不必再等”，是因为调用完成记录被预期已经送到次多数；文中没有到达过程的拟合，也没有把三台与五台画成可外推的可靠度曲线。

参考文献#

• Oki, B. M. & Liskov, B. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. Proc. 7th ACM PODC, 1988, pp. 8–17. doi:10.1145/62546.62549（本文对象）
• Oki, B. M. Viewstamped Replication for Highly Available Distributed Systems. Ph.D. thesis, MIT Laboratory for Computer Science, MIT-LCS-TR-423, 1988.（同年学位论文，嵌套事务与完整论证）
• Liskov, B. & Cowling, J. Viewstamped Replication Revisited. MIT-CSAIL-TR-2012-021, July 2012.（状态机重述：请求、视图变更与恢复；已发表对象，非操作单）
• Alsberg, P. A. & Day, J. D. A Principle for Resilient Sharing of Distributed Resources. Proc. 2nd International Conference on Software Engineering, 1976, pp. 562–570.（论文所本的主副本技术；要求区分节点故障与网络故障）
• El Abbadi, A. & Toueg, S. Availability in Partitioned Replicated Databases. Proc. 5th ACM PODS, 1986, pp. 240–251.（论文所称视图变更的前身：虚拟分区）
• Bernstein, P. A. & Goodman, N. An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases. ACM TODS 9(4), 1984, pp. 596–615.（单副本可串行化口径）
• Lamport, L. The Part-Time Parliament. ACM TOCS 16(2), 1998, pp. 133–169.（后来常被拿来对读的选定值协议，非本文对象）
• Fischer, M. J., Lynch, N. A. & Paterson, M. S. Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32(2), 1985, pp. 374–382.（完全异步下慢与死不可分；论文不声称推翻）

延伸阅读#

• Liskov, B., Ghemawat, S., Gruber, R., Johnson, P., Shrira, L. & Williams, M. Replication in the Harp File System. Proc. ACM SOSP, 1991, pp. 226–238.（把视图戳复制用进文件服务；非本文对象）
• Schneider 1990：Fred B. Schneider, Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys 22(4), 1990, pp. 299–319。（2012 年重述所依的状态机复制框架）
• van Renesse, R., Schiper, N. & Schneider, F. B. Vive la Différence: Paxos vs. Viewstamped Replication vs. Zab. IEEE Transactions on Dependable and Secure Computing 12(4), 2015, pp. 472–484.（后来的形式对照，不是把三份兑成一份操作单）
• 与 兼职议会与 Paxos 对读：TOCS 的对象是选定值；本文是主副本、视图与盖章请求。
• 与 共识算法、etcd、ZooKeeper 对读：那些页讲复制日志和协调内核；本文停在 1988 年的视图戳与 2012 年重述。
• 与 FLP 对读：不可能性标定完全异步的全称承诺；本文在崩溃与分区终将结束的模型里谈换届，不把超时写成攻击步骤。