Lab 2：Primary/Backup Key/Value Service

Overview of lab 2

在本次实验中，我们将使用primary/backup replication 来提供能够容错的key/value service。为了让所有的clients和severs都认同哪个server是primary，哪个server是backup，我们将引入一个master service，叫viewservice。viewservice将监控那些可获取的server中哪些是死的，哪些是活的。如果当前的primary或者backup死了的话，viewservice将选择一个server去替代它。client通过检查viewservice来获取当前的primary。servers通过和viewservice合作来确保在任意时间至多只有一个primary。

我们的key/value service要能够对failed servers进行替换。当一个primary故障的时候，viewservice会从backup中选择一个作为新的primary。当一个backup故障或者被选为primary之后，如果有可用的空闲的server，viewservice就会将它变成backup。primary会将整个数据库都传送给新的backup，也会将之后的Puts操作的内容传送给backup，从而保证backup的key/value数据库和primary相同。

事实上，primary必须将Gets和Puts操作传送给backup（如果存在的话），并且直到收到backup的回应之后，才回复client。这能防止两个server同时扮演primary的角色（a "split brain"）。例如：S1是primary，S2是backup。viewservice（错误地）认为S1死了并且将S2提升为新的primary。但是client仍然认为S1是primary，并且向它发送了一个operation。S1会将该operation传送给S2，S2将回复一个错误，告诉S1它不再是backup了（假设S2从viewservice中获得了新的view）。于是S1将返回给client一个错误，表明S1可能不再是primary了（因为S2拒绝了operation，因此肯定是一个新的view已经形成了）。之后，client将询问viewservice获取正确的primary（S2）并且向它发送operation。

发生故障的key/value server需要进行重启，但是此时我们不需要对replicated data（那些key和value）进行拷贝。这说明，我们的key/value server是将数据保存在内存而不是磁盘上的。只将数据保存在内存中的一个后果是，如果没有backup，primary发生故障了并且进行了重启操作，那么它将不能再扮演primary。

在clients和servers之间，不同的servers之间，以及不同的clients之间，RPC是唯一的交互方式。例如，不同的server实例之间是不允许共享Go变量或者文件的。

上文描述的设计存在一些容错和性能方面的限制，使它很难在现实世界中应用：

（1）、viewservice是非常脆弱的，因为它没有进行备份

（2）、primary和backup必须一次执行一个operation，限制了它们的性能

（3）、recovering server必须从primary中拷贝整个key/value对的数据库，即使它已经拥有了几乎是最新的数据，这是非常慢的（例如，可能因为网络的问题从而少了几分钟的更新）。

（4）、因为servers不将key/value数据库存放在磁盘中，因此不能忍受server的同时崩溃（例如，整个site范围内的断电）

（5）、如果因为一个临时的问题妨碍了primary和backup之间的通信，系统只有两种补救措施：改变view，从而消除通信障碍的backup，或者不断地尝试，不管是哪种方式，如果这样的问题老是发生的话，性能都不会很好

（6）、如果primary在确认它自己是primary的view之前发生故障了，那么viewservice将不能继续执行-----它将不断自旋并且不会改变view

在之后的实验中，我们将通过更好的设计和协议来解决这些限制。而本实验会让你明白在接下来的实验中将要解决哪些问题。

本实验中的primary/backup 方案并没有基于任何已知的协议。事实上，本实验并没有指定一个完整的协议，我们必须要自己对细节进行处理。本实验其实和Flat Datacenter Storage有些类似（viewservice就像FDS的metadata center，primary/backup server就像FDS中的tractserver），不过FDS花了更多的功夫在性能优化上。本实验的设计还和MongoDB中的replica set有些类似，虽然MongoDB是通过Paxos-like的选举来选择leader的。对于primary-backup-like protocal的细节描述，可以参见Chain Replication的实现。Chain Replication比本实验的设计有更好的性能，虽然它的viewservice并不会宣布一个server的死亡，如果它仅仅只是参与的话。参见Harp and Viewstamped Replication，可以发现它对高性能primary/backup 的细节处理以及在各种各样的故障之后对系统状态的重构操作。

Part A: The Viewservice

viewservice会经过一系列标号的view，每一个view都有一个primary和一个backup（如果有的话）。一个view由一个view number和view的primary和backup severs的identity（network port number）组成。一个view的primary必须是前一个view的primary或者backup。这确保了key/value的状态能够保存下来。当然有一个例外：当viewservice刚刚启动的时候，它要能够接受任何server作为第一个primary。view中的backup可以是除了primary之外的任何一个server，如果没有可用的server的话，也可以没有backup。（通过空字符串表示，“”）

每一个key/value server都会在每隔一个PingInterval发送一个Ping RPC给viewservice，viewservice则会回复当前view的描述。Ping让viewservice知道key/value server仍然活着，同时通知了key/value server当前的view，还让viewservice了解key/value server知道的最新的view。如果viewservice经过DeadPings PingIntervals还没有从server收到一个Ping，那么viewservice认为该server已经死了。当一个server在崩溃重启之后，它需要向viewservice发送一个或多个带有参数0的Ping来告知viewservice它崩溃过了。

当（1）viewservice没有从primary和backup中获取最新的Ping，（2）primary或者backup崩溃并且重启了，（3）如果当前没有backup并且有空闲的server出现的时候（一个server ping过了，但是它既不是primary也不是backup），viewservice 都会进入一个新的view。但是在当前view的primary确认它正在当前的view进行操作之前（通过发送一个带有当前view number的Ping），viewservice是一定不能改变view的。当viewservice仍然未收到当前view的primary对于当前view的acknowledgment之前，它不能改变view，即使它认为primary或者backup已经死了。简单地说就是，viewservice不能从view X进入view X+1，如果它还没有从view X的primary接收到Ping（X）。

这个acknowledge规则防止了viewservice的view超过key/value server一个以上。如果viewservice能领先任意个view，那么我们需要更加复杂的设计，从而保证在viewservice中保存view的历史，从而能让key/value server能够获得之前老的view，并且要在合适的时候对老的view进行回收。这种acknowledgment规则的缺陷是，如果primary在它确认自己是primary的view之前出现故障了，那么viewservice就不能再改变view了。

源码分析之ViewService部分

ViewServer结构如下所示：

type ViewServer struct {

　　mu　　　　　  sync.Mutex
　　l　　　　　　 net.Listener
　　dead　　　　　int32　　// for testing
　　rpccount　　 int32　  // for testing
　　me　　　　　　string


　　// Your declaration here.

}

// src/viewservice/server.go

func StartServer(me string) *ViewServer

（1）、首先填充一个*ViewServer的数据结构

（2）、调用rpcs := rpc.NewServer()和rpcs.Register(vs)，注册一个rpc server

（3）、调用l, e := net.Listen("unix", vs.me)，vs.l = l建立网络连接

（4）、生成两个goroutine，一个用于接收来自client的RPC请求并生成goroutine处理，另一个goroutine每隔PingInterval调用一次tick()

源码分析之Clerk部分

Clerk结构如下所示：

// the viewservice Clerk lives in the client and maintains a little state

type Clerk struct {
　　me　　　　  string　　// client‘s name (host:port)
　　server　　　string　　// viewservice‘s host:port
}

// src/viewservice/client.go

func MakeClerk(me string, server string) *Clerk

该函数只是简单地填充一个*Clerk结构并返回而已

// src/viewservice/client.go

func (ck *Clerk) Ping(viewnum int) (View, error)

创建变量args := &PingArgs{}，并进行填充，接着调用ok := call(ck.server, "ViewServer.Ping", args, &reply)且返回reply.View

源码分析之view部分

View结构如下所示：

type View struct {

　　Viewnum　　  int
　　Primary　　  string
　　Backup　　   string
}

Ping相关的结构如下所示：

// If Viewnum is zero, the caller is signalling that it is alive and could become backup if needed

type PingArgs struct {

　　Me　　　　 string　　// "host:port"
　　Viewnum　 uint　　　// caller‘s notion of current view #
}

type PingReply struct {
　　View　　View
}

Get相关的结构如下：

// Get(): fetch the current view, without volunteering to be a server.mostly for clients of p/b service, and for testing

type GetArgs struct {

}

type GetReply struct {

　　View　　View
}

// the viewserver will declare a client dead if it misses this many Ping RPCs in a row

const DeadPings = 5

------------------------------------------------------------------------------------------------ 测试框架分析 -----------------------------------------------------------------------------------------------

1、src/viewservice/test_test.go

func check(t *testing.T, ck *Clerk, p string, b string, n uint)

该函数首先调用view, _ := ck.Get()获取当前的view，并比较view的Primary，Backup和p, b是否相等，并且在n不为0的时候，比较n和view.Viewnum是否相等。

最后调用ck.Primary()比较和p是否相等。

2、src/viewservice/test_test.go

func Test1(t *testing.T)

（1）、首先调用runtime.GOMAXPROCS(4)，再指定viewservice的port，vshost := port("v")，格式为“/var/tmp/824-${uid}/viewserver-${pid}-v”

（2）、调用vs := StartServer(vshost)启动viewservice

（3）、调用cki := MakeClerk(port("i"), vshost)，i = 1, 2, 3,启动3个server

（4）、当ck1.Primary() 不为空时，则报错，因为此时不应该有primary。

Test： First primary ...

每隔一个PingInterval ck1都调用一次ck1.Ping(0)操作，直到返回的view.Primary 为ck1.me退出，最多循环DeadPings * 2次

Test：First backup...

首先调用vx, _ := ck1.Get获取当前的view，每隔PingInterval ck1都调用一次ck1.Ping(1)，之后ck2调用view, _ := ck2.Ping(0)操作，直到返回的view.Backup为ck2.me时退出，最多循环DeadPings * 2次。

Test：Backup takes over if primary fails...

首先通过调用ck1.Ping(2)确认以下view 2。再调用vx, _ := ck2.Ping(2)获取viewservice当前的view，再每隔PingInterval 调用一次v, _ := ck2.Ping(vx.Viewnum)，直到v.Primary == ck2.me并且v.Backup == ""为止，最多循环DeadPings * 2次。

MIT 6.824 : Spring 2015 lab2 训练笔记