# Lab: Primary/Backup Key/Value Service

## Part A

### Viewservice 的职责

![图1 - Viewservice 的职责](/files/-LOBMRrJ5mP-bti2UOOq)

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](/files/-LO6fgE-PoQ-086eBe3o)

![图3 - 状态变化测试 4-5](/files/-LO6fxOegOY--y92PKSJ)

![图4 - 状态变化测试 6-8](/files/-LO6g248z9h-Ak43PamA)

![图5 - 状态变化测试 9](/files/-LO6g9s7jnOZMz7hpXRR)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.824/shi-yan-2primarybackup-keyvalue-service.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.