# Lab: Primary/Backup Key/Value Service

## Part A

### Viewservice 的职责

![图1 - Viewservice 的职责](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LOBJGyNhjAlQzQcFl7X%2F-LOBMRrJ5mP-bti2UOOq%2Fview-service.png?alt=media\&token=b72b9184-a2ec-4b8d-bbdf-daab145d8239)

Viewservice (以下简称 VS) 是服务集群的状态管理者，也是唯一的信息来源 (single source of truth)，它负责在任何时刻告诉集群中的每台机器以及所有的客户端，谁是 Primary，谁是 Backup，谁在 Idle Servers 队列中。为此 VS 支持两种请求，Ping 和 Get：

* 计算节点向 VS 发送 Ping 请求，表示它已经准备好加入集群中
* 计算节点向 VS 发送 Get 请求，获取当前集群状态

由于 VS、计算节点、网络传输都可能出现问题，因此 Viewservice 需要规定不同情形下的处理协议：

* VS 同时接收到多个 Ping 请求
* VS 接收第一个、第二个、...、第 N 个 Ping 请求
* Primary、Backup、Idle Server 如果失去心跳 （不再持续向 VS 发送 Ping 请求)
* VS 什么时候能够确认从View X 进入View X+1（在 View X 被 Primary 确认后），注意这里的 View 指代码中规定的数据结构，包含 Viewnum、Primary 和 Backup
* VS 自身崩溃（在本实验中未解决）

### 实验测试过程中的状态变化

**状态变化图的说明：**

* 每个测试内部的状态变化使用横着的虚线隔离开
* Viewservice 的状态在左边表示
  * \#ack：最后得到确认的 view 编号
  * \#view: 当前 Viewservice 内部未公开的最新 view 编号
  * p、b、idles: 当前公开的 view 的 Primary、Backup 和 Idle Servers
* 图中的从上到下表示时间演进，每个 Ping 请求为引发状态变化的 Ping 请求，未引发状态变化的未画出。可参考测试代码阅读本图

![图2 - 状态变化测试 1-3](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LO6fFNgT_MFzLktGkCG%2F-LO6fgE-PoQ-086eBe3o%2FScreen%20Shot%202018-10-06%20at%2012.40.47%20PM.jpg?alt=media\&token=997e5daf-a445-41c6-bbc7-9fd78858f648)

![图3 - 状态变化测试 4-5](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LO6fFNgT_MFzLktGkCG%2F-LO6fxOegOY--y92PKSJ%2FScreen%20Shot%202018-10-06%20at%2012.41.13%20PM.jpg?alt=media\&token=813c5a5e-8d55-47e6-ad5a-f1fba7abd0fc)

![图4 - 状态变化测试 6-8](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LO6fFNgT_MFzLktGkCG%2F-LO6g248z9h-Ak43PamA%2FScreen%20Shot%202018-10-06%20at%2012.41.33%20PM.jpg?alt=media\&token=fd46965a-0e84-4556-9a8c-396573eed08e)

![图5 - 状态变化测试 9](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LO6fFNgT_MFzLktGkCG%2F-LO6g9s7jnOZMz7hpXRR%2FScreen%20Shot%202018-10-06%20at%2012.41.46%20PM.jpg?alt=media\&token=7eb8623b-2074-42e2-aacc-359ef636940c)

## Part B

### 目标

在 Part B 中，我们需要利用 Part A 中的 VS，构建一个分布式主从 （Primary/Backup，简称 P/B）键值 （Key/Value，简称 K/V） 数据库，这个数据库满足：

* 只要任何时刻在 VS 上还有注册的服务器，这个 K/V 数据库服务就能够正常运作
* 当存在网络分区（Network Partition) 时，这个 K/V 数据库服务依然能够正常运作
* 当 K/V 数据库只有一台服务器在运行，且有可用的服务器（新注册的或者在 Idle 列表中的），本服务能够自动初始化 Backup 服务来帮助容忍服务器故障问题
* K/V 数据库正常运作时，Clerk.Get(k) 应该返回上一次 Clerk.Put(k, v) 或 Clerk.Append(k, v) 的结果，如果 k 不在数据库中，则返回空字符串，并且所有的操作需要保证最多执行一次（at-most-once）的语义。

### 难点及解决方案

#### P/B 数据同步

P/B 的数据需要保持一致，有两种方法：

* 每隔一段时间 Primary 将这段时间内的增量更新同步给 Backup：操作逻辑简单，传输数据量大
* 每隔一段时间 Primary 将这段时间内的增量操作同步给 Backup，后者按照相同的顺序执行一遍操作：操作逻辑复杂，传输数据量小

本实验将采用第二种方法，在增量操作同步时，需要做到：

***操作的顺序不变***

思路一：利用时间戳，在每个从 Primary 转发到 Backup 的写操作中加上 Primary 上操作执行的时间戳信息，Backup 通过时间戳信息来决定执行顺序。但本思路在实现过程中存在一个致命问题：

> 由于 Primary 转发的不同操作到达 Backup 的时间不同，因此 Backup 需要对这些操作进行重排序，但实际上这个重排序是不可能完成的任务，如 Backup 在接收到 T1，T3 的操作后，无法知道 T2 是否存在操作，T2 时刻可能压根不存在操作或 T2 时刻的操作由于网络原因可能无限期延迟。

除此之外，软件的正确性依赖于时间戳是很危险的一件事情。在多主环境下，时间信息可能不一致，虽然本实验中无需考虑该情况，但利用时间戳的思路隐患颇多。在发现缺陷后，我果断放弃了思路一。

思路二：利用编号，在每个从 Primary 转发到 Backup 的写操作中加上 Primary 写操作执行的编号，编号从1 开始递增，Backup 只需记录上一个写操作的编号 N，等待编号为 N+1的写操作，同时缓存所有编号大于 N+1 的写操作，忽略编号小于或等于 N 的写操作。本思路解决了实现思路一过程中遇到的问题。

***操作去重***

操作去重的思路其实实验代码已经为我们提供了解决方案：为客户端发送的每个写请求加上唯一的**识别码**。在测试代码（pbservice/server）中，我们可以看到如下代码：

```go
for pb.isdead() == false {
	conn, err := pb.l.Accept()
	if err == nil && pb.isdead() == false {
		if pb.isunreliable() && (rand.Int63()%1000) < 100 {
			// discard the request.
			conn.Close()
		} else if pb.isunreliable() && (rand.Int63()%1000) < 200 {
			// process the request but force discard of reply.
			c1 := conn.(*net.UnixConn)
			f, _ := c1.File()
			err := syscall.Shutdown(int(f.Fd()), syscall.SHUT_WR)
			if err != nil {
				fmt.Printf("shutdown: %v\n", err)
			}
			go rpcs.ServeConn(conn)
		} else {
			go rpcs.ServeConn(conn)
		}
	} else if err == nil {
		conn.Close()
	}
	if err != nil && pb.isdead() == false {
		fmt.Printf("PBServer(%v) accept: %v\n", me, err.Error())
		pb.kill()
	}
}
```

为了模拟网络的不可靠性，服务器在接到 RPC 请求后，可能存在三种情况：

* 直接丢弃请求（模拟请求未被顺利发到服务器）
* 处理请求同时丢弃响应（模拟响应未被顺利发送到客户端）
* 处理请求并正确响应

在前两种情况下，客户端可能重复发送写请求，但只要保证这些写请求的**识别码**不变，服务端就能够实现操作去重。

#### Backup 初始化

Backup 初始化要分成三个阶段：（假设该服务器为 S）

1. VS 将 S 提升为 Backup，此时 S 尚不知道自己的身份，Primary 已经知道 S 的身份（若 Primary 不知道，View 不会跳转），就会转发请求到 S，此时 S 可以大胆丢弃这些请求。
2. S 已经知道自己的身份，但尚未从 Primary 完成 K/V 数据库的同步，此时 S 同样可能接到 Primary 转发的请求，如何处理这些请求是保证 Backup 顺利初始化的关键。仔细推敲后不难想到，在 Primary 读取 K/V 数据库的时刻之后的所有请求 S 都应该执行；之前的所有请求 S 都必须丢弃。因此我们可以让 Primary 在读取数据库后的响应中加入当前 Primary 已经顺利执行的写操作编号，S 只需要根据这个编号来判断在此期间收到的请求的处理方法。
3. S 完成同步数据过程，成为一个合格的备胎。

#### 网络分区

假设在某个时刻，S1 是 Primary。但由于网络分区，VS 认为 S1 发生故障，将 S2 提升为 Primary，这时候有两个服务器都认为自己是 Primary，这时候可能出现不同的客户端向不同的服务器发请求，为了保证 K/V 服务的正常运作，返回最新的键值，S1 不能处理失联后收到的请求。解决网络分区的思路在实验的提示信息中已经给出：

> S1 在转发请求给 S2 之后（S1 失联之前，S2 是 Backup），S2 如果发现自己实际上是 Primary ，S2 就应该拒绝该请求

根据该思路，我在转发的请求中加上两个字段：

1. Viewnum: 请求转发者的 View 版本
2. Isfp: 即 is from primary，表示请求是否来自于 Primary

### 实验过程

**Part A**

Part A 的完成使用了大约 4 个小时，难点在于真正理解 “VS 什么时候应该从 View X 跳转到 View X+1”，只有遵从 “在 Primay 确定了 View X 之后才能进入 View X+1” 的协议才能通过所有请求。

**Part B**

Part B 的完成使用了大约 15 个小时，历尽艰辛，在解决 P/B 数据的同步问题过程中，浪费较多时间在思路一上，没能够跳出思路重新思考。在大约 10 个小时的时候才开始重新评估思路一的可行性，终于解决问题。实验过程中也发现一套服务端代码要同时完成多个角色（P/B）的工作对编程者来说是挺大的考验，许多地方为了增加代码可读性，会让代码变得更啰嗦一些，避免一些小聪明反被聪明误。

比如以下代码，在服务器每次 tick 时，我会记录下 pb.isp 和 pb.isb，之后的所有逻辑在书写之前都先判断服务器的角色。

```go
// inside tick()
pb.mu.Lock()
defer pb.mu.UnLock()
pb.isp = pb.me == view.Primary
pb.isb = pb.me == view.Backup

// inside any server logic
pb.mu.Lock()
defer pb.mu.UnLock()
if pb.isp {
    // do something when it is primary
}

if pb.isb {
    // do something when it is backup
}
```

**其它**

由于本实验目的在于了解一个 P/B 服务的构建方法及过程体验，因此本次的解决方案在并发上没有优化，直接暴力使用 Mutex，存在进一步优化空间。

## 参考

6.824 - Spring 2015 - Lab 2: Primary/Backup Key/Value Service [instructions](http://nil.csail.mit.edu/6.824/2015/labs/lab-2.html), [raw source code](git://g.csail.mit.edu/6.824-golabs-2015), [my solution](https://github.com/ZhengHe-MD/distributed-system-lab-codes-2015)