# Primary/Backup Replication

## 复制 （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）：

1. 暂停 Primary
2. 将 Primary 的所有内存，寄存器，硬盘数据传输到 Backup 中
3. 恢复 Primary

当 Primary 发生故障时，启动 Backup 运行软件。

![图 1 - Remus Primary/Backup 结构示意图](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LOrj08HakMZ9DVNK3fS%2F-LOrt41AgmAh45BbUumc%2FScreen%20Shot%202018-10-15%20at%209.21.26%20PM.jpg?alt=media\&token=98168763-8021-4cc5-a860-18cc8a90d518)

Q1：思路一正确吗？

不正确。例如 Client 向 Primary 发送一个 DB 写请求，Primary 将数据写入 DB 后，告诉 Client 已经完成，但在 Primary 尚未向 Backup 同步最新状态时，Primary 发生故障，这时候启动 Backup，Backup 中的 DB 尚未写入数据，而 Client 认为数据已经写入。

Q2：思路二高效吗？

不高效。光硬盘数据就不可能在 1 秒内写完，更不用说每秒同步多次了。

### 让思路一可行

针对 Q1：我们可以在 Primary 与 Backup 完成当前写操作的状态同步后，才允许 Primary 将请求结果返回给 Client，如下图所示：

![图 2 - Remus Primary/Backup 同步过程示意图](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LOrj08HakMZ9DVNK3fS%2F-LOrwROsjiQFiZk2uFB2%2FScreen%20Shot%202018-10-15%20at%209.36.46%20PM.jpg?alt=media\&token=1224c62f-1b3a-4455-8416-77f0f547ad8e)

\
针对 Q2：Remus 有两种改进手段

* 每次同步只做增量更新
* 在同步的时候，可以超前执行新的请求

其它实现过程中可能遇到的问题：

* 如果 Primary 在于 Backup 同步数据之后，发送响应给 Client 之前崩溃，怎么办？
* 网络分区可能引起 Remus 误将 Backup 激活
* 如果区域性断电导致 Primary 和 Backup 都故障了怎么办
* 当 Primary 回复，Remus 如何让 Primary 的状态更新到最新
* epoch 的时间长短如何决定

## 参考

6.824-2015-Lecture 3: Primary/Backup Replication, [notes](http://nil.csail.mit.edu/6.824/2015/notes/l-remus.txt), [video](https://www.youtube.com/watch?v=OUJ24CPQljs)