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):

  1. 暂停 Primary

  2. 将 Primary 的所有内存,寄存器,硬盘数据传输到 Backup 中

  3. 恢复 Primary

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

图 1 - Remus Primary/Backup 结构示意图

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 同步过程示意图

针对 Q2:Remus 有两种改进手段

  • 每次同步只做增量更新

  • 在同步的时候,可以超前执行新的请求

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

  • 如果 Primary 在于 Backup 同步数据之后,发送响应给 Client 之前崩溃,怎么办?

  • 网络分区可能引起 Remus 误将 Backup 激活

  • 如果区域性断电导致 Primary 和 Backup 都故障了怎么办

  • 当 Primary 回复,Remus 如何让 Primary 的状态更新到最新

  • epoch 的时间长短如何决定

参考

6.824-2015-Lecture 3: Primary/Backup Replication, notes, video