复制日志

形式陈述 ​

复制日志在每个副本 $p_i$ 上维护一条带连续索引的有限序列公理库序列Sequence以自然数为定义域的函数。

$$L_i=⟨e_{i,1},e_{i,2},\dots ,e_{i,n_i}⟩,$$

其中条目通常包含命令、唯一请求标识和协议需要的元数据。日志接口区分三个状态：条目可以先被某副本本地追加，随后被协议判定为 chosen/committed，最后才由副本按索引顺序 applied 到状态机公理库状态机State machine · Transition system用状态集合、初始状态和转移关系描述系统可能执行轨迹的模型。。一次本地写入或磁盘落盘不自动跨越这三层。

抽象安全规格至少包括：有效性要求日志条目来自合法提议；完整性要求同一命令标识不会被无故伪造或重复交付；已提交前缀一致性要求任意两个正确副本的 committed 序列彼此为前缀，等价地，若索引 $k$ 在两边都已提交，则对应条目相同；只追加要求已经提交的前缀不被修改或删除。未提交本地尾部可以因恢复或领导者变化被截断、覆盖，因此只追加承诺必须明确限定 committed 部分。

进展规格则要说明合法提议在何种故障、网络与公平条件下最终获得索引并提交，以及正确副本是否最终应用每个 committed 条目。复制日志本身不指定 leader、任期、投票、法定人数或超时；这些是 Raft、Paxos、Viewstamped Replication 等实现安全与活性的机制。抽象接口只保留客户端和状态机真正依赖的共同序列合同。

日志与原子广播公理库原子广播Atomic broadcast · Total-order broadcast所有正确进程以同一总序交付广播消息。有直接对应。把每次全序交付的消息追加到下一个索引，所有正确副本便得到同一已交付前缀；反过来，按索引交付复制日志新提交的条目可实现全序广播。两者表达同一排序能力的不同接口面，但日志通常显式暴露索引、提交位置、应用位置、恢复和截断中的本地尾部状态。

直觉 ​

复制日志不是把每台机器的文件复制到同样长，而是让它们对一条不可反悔的命令前缀达成共同承诺。副本可以快慢不同：一个已经应用到索引 200，另一个只到 190；只要短日志是长日志已提交部分的前缀，它们就在沿同一条历史前进。

“出现过”和“承诺过”的分界最重要。领导者可以先把候选条目写到本地，网络分区后却无法获得协议所需证据。若客户端把这一暂存事实当成全局完成，新领导者合法覆盖尾部时就会看到已经确认的结果消失。

例子与边界 ​

复制银行状态机从余额映射 $s_0$ 出发，日志依次提交 deposit(A, 50)、transfer(A, B, 20) 与 withdraw(B, 10)。只要各副本从同一初态按相同索引调用确定性转移函数，即使实际应用时间不同，它们应用到同一前缀后也得到相同余额与响应。客户请求 ID 还需参与去重，否则网络重试可能把同一存款作为两个合法条目追加，日志完全一致却破坏端到端“恰好一次效果”。

旧领导者本地日志尾部有索引 41 的命令 $x$，但只复制到少数副本便失去连接。新领导者在同一位置提交 $y$，恢复后旧副本必须丢弃未提交的 $x$ 并接受共同前缀中的 $y$。这个覆盖不违反只追加，因为 $x$ 从未进入 committed 前缀；若只检查“条目已经 fsync”，就会把本地持久性误当成分布式承诺。

复制日志也不等同数据库 WAL。WAL 首要目标是让单机或数据库恢复重做/撤销更新，可以包含物理页记录、补偿记录和未提交事务；复制日志首要目标是让副本认同命令顺序。一个系统可以把两者组合或共用存储格式，但恢复语义、提交判据和消费方不同，不能靠“都是 append-only 文件”直接等同。

推论与应用 ​

状态机复制公理库状态机复制State machine replication · SMR让多个副本按同一确定顺序执行命令，从而实现容错服务。消费 committed 日志，把共同命令序列变为共同状态；读路径、响应时机、快照和成员变更仍需额外协议。快照可以压缩已应用前缀，却必须保留与后续日志衔接所需的最后索引和状态摘要，不能把压缩误写成改写历史。

实现选择应分别验证日志安全与活性。多数相交、任期和领导者完整性可以维护前缀不变，部分同步或最终领导者常为持续提交提供时序条件；这些机制都不进入本页的接口定义。如此一来，不同共识协议才能共享同一个可复用的日志消费者模型。

参考资料

• Diego Ongaro and John Ousterhout, “In Search of an Understandable Consensus Algorithm,” USENIX ATC 2014, pp. 305–319。
• Brian M. Oki and Barbara H. Liskov, “Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems,” PODC 1988, pp. 8–17。
• Leslie Lamport, “The Part-Time Parliament,” ACM TOCS 16(2), 1998, pp. 133–169。
• Xavier Défago, André Schiper, and Péter Urbán, “Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey,” ACM Computing Surveys 36(4), 2004, pp. 372–421。