Lab: Primary/Backup Key/Value Service

2015 Lab2

Part A

Viewservice 的职责

图1 - Viewservice 的职责

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
图3 - 状态变化测试 4-5
图4 - 状态变化测试 6-8
图5 - 状态变化测试 9

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)中,我们可以看到如下代码:

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,之后的所有逻辑在书写之前都先判断服务器的角色。

// 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, raw source code, my solution