Primary/Backup Replication
6.824 2015 Lecture 3/2018 Lecture 4
复制 （Replication）
容错（Fault Tolerance）
我们都希望一个服务能够在发生故障后还能正常提供服务，这要求系统：
可用（Available）：即使出现（某些）故障还能够使用
正确（Correct）：服务的正确性不受影响，如同在单机上运行
这特别有用，却也特别困难。而这正复制技术尝试解决的一个问题。但再强大的复制技术，也不可能解决所有故障，因此我们需要定义一个故障模型（Failure Model）：
故障模型 （Failure Model）
一个故障模型可以从以下方面来分析：
不同计算节点的宕机相关性
区域性断电（最终重启）
网络分区（断网）
复制
使用 2 台或多台服务器，构成一个复制集合（Replica Set），每个复制单元（Replica）都保持服务的所有状态，如果其中一个复制单元发生故障，其它复制单元可以继续提供服务。
举例：Fault-tolerant MapReduce Master
在实验 1 中，MapReduce Workers 已经具备容错能力，然而 Master 是单点故障（single point of failure）。如果引入复制技术，比如两个 Master 节点，当其中一个发生故障，另一个能顶上去。
每个 MapReduce Master 的状态可能包含：
当前 Worker 列表
Jobs 进度信息
空闲 Worker 列表
TCP 连接状态
程序计数器
...
主要问题
哪些状态需要复制？
复制节点如何获取状态？
如何切换到备用节点？
在切换过程中会出现问题吗？
如何接入新节点或故障恢复的节点？
两种保持节点状态一致的思路
状态转移：Primary 执行服务，把实时状态发送给 Backups
更简单
需要转移的状态较大
复制状态机：所有节点，不论 Primary 还是 Backups 都执行所有请求操作，并保证操作一致、顺序一致且操作结果是完全可确定的
更复杂，保证执行顺序的逻辑复杂
需要转移的状态较小
论文研读：Remus
基本思想
Remus 的想法非常大胆，它尝试在系统级别上通过复制技术来实现系统的高可用性，从而基于此系统开发的所有软件都自动获得了高可用性。
故障模型
可以容忍单个节点发生故障
当主从节点都发生故障时，系统处于崩溃一致（crash-consistent）状态，即数据是一致的，重启以后系统能正常工作
在所有系统状态被确认提交到备用节点后，当前的系统输出才会对外部可见
思路一
Primary/Backup 复制集，Primary 上运行 Remus 代码及其它应用程序，Backup 上只运行 Remus 代码，负责同步系统状态，每秒按以下步骤执行多次（每次成为一个 epoch）：
暂停 Primary
将 Primary 的所有内存，寄存器，硬盘数据传输到 Backup 中
恢复 Primary
当 Primary 发生故障时，启动 Backup 运行软件。
Q1：思路一正确吗？
不正确。例如 Client 向 Primary 发送一个 DB 写请求，Primary 将数据写入 DB 后，告诉 Client 已经完成，但在 Primary 尚未向 Backup 同步最新状态时，Primary 发生故障，这时候启动 Backup，Backup 中的 DB 尚未写入数据，而 Client 认为数据已经写入。
Q2：思路二高效吗？
不高效。光硬盘数据就不可能在 1 秒内写完，更不用说每秒同步多次了。
让思路一可行
针对 Q1：我们可以在 Primary 与 Backup 完成当前写操作的状态同步后，才允许 Primary 将请求结果返回给 Client，如下图所示：
针对 Q2：Remus 有两种改进手段
每次同步只做增量更新
在同步的时候，可以超前执行新的请求
其它实现过程中可能遇到的问题：
如果 Primary 在于 Backup 同步数据之后，发送响应给 Client 之前崩溃，怎么办？
网络分区可能引起 Remus 误将 Backup 激活
如果区域性断电导致 Primary 和 Backup 都故障了怎么办
当 Primary 回复，Remus 如何让 Primary 的状态更新到最新
epoch 的时间长短如何决定
参考
Last updated
