Key/Value Server

本次试验中，将为一台机器构建一个键值服务器，该服务器确保即使网络故障，每个操作也只执行一次，且操作是线性化的。后面的实验将会复制这样的服务器来处理服务器崩溃。

• 线性一致性：最强的数据一致性保证，所有操作看起来像是按照某种全局顺序执行的，与真实的时间顺序一致，系统表现的像是一个单机系统，所有操作都是原子的。（分布式锁、金融系统）

• 顺序一致性：操作按照某种顺序执行，但不一定与真实时间一致。（多线程编程模型）

• 最终一致性：系统最终会达到一致状态，但中间可能存在不一致。（DNS 系统、分布式缓存）

• 因果一致性：保证因果关系的操作顺序，但不保证无关操作的顺序。（社交网络中的消息传递）

执行概述

Clients可以向KVServer发送三种不同的RPC请求：Put(key, value), Append(key, arg), Get(key)。KVServer维护键值对的内存映射map。每个Client通过一个带有Put/Append/Get方法的Clerk与服务器进行对话。Clerk管理RPC与服务器的交互。

• Put(key, value)：设置或者替换一个特定键在map中的值。
• Append(key, arg)：将arg附加到键对应的值后面，并返回旧值。
• Get(key)：返回键对应的值，如果键不存在则返回空字符串。

提供线性一致性会使应用程序更方便，因为它是你在服务器上看到的行为，该服务器一次处理一个请求。当一个客户从服务器成功响应更新请求，则随后从其他客户端启动的读取就可以保证看到更新的效果。对于单个服务器来说，提供线性一致性也相对容易。

结构体定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// client.go
type Clerk struct {
	server *labrpc.ClientEnd
	requestId int64
}

// server.go
type KVServer struct {
	mu              sync.Mutex

	// Your definitions here.
	kvMap           map[string]string
	pushAppendCache map[int64]PutAppendReply
}

// Put or Append
type PutAppendArgs struct {
	Key       string
	Value     string
	RequestId int64
}

type PutAppendReply struct {
	Value   string
	ReplyId int64
}

type GetArgs struct {
	Key string
}

type GetReply struct {
	Value string
}

client.go

MakeClerk

1. 初始化Clerk，赋值server，用nrand()创建一个requestId

Get

1. 创建GetArgs{Key: key}和GetReply{}，用来发送RPC请求
2. 循环发送RPC请求处理Get，直到响应成功时，返回reply.Value。

PutAppend

put和append操作的公共部分。

1. 创建PutAppendArgs{Key: key, Value: value, RequestId: ck.requestId}和PutAppendReply{}，用来发送RPC请求。
2. 根据传入的参数op，循环发送RPC请求处理Put/Append，直到响应成功时，返回reply.Value，且requestId自增1。

server.go

Get

1. 获取锁，避免脏读到中间状态。
2. 读取kvMap对应key的值，若存在，则把值返回给reply，否则返回空字符串。

Put

1. 获取锁。
2. 查看pushAppendCache，若存在该requesID，则把对应的值返回给reply，然后return。
3. 否则，设置kvMap对应key的值，然后把该requestId和reply添加到pushAppendCache中。
4. 清理上一个请求的缓存。

1

delete(kv.pushAppendCache, args.RequestId-1)

这里的pushAppendCache的作用是，如果客户端发送了Put/Append请求，但服务器崩溃了，那么客户端会重新发送请求，这里就可以检查requestID是否存在于缓存，保证每个操作只执行一次。

Append

处理过程与Put相同，区别在于Put是直接修改对应key的值，而Appen的是把值附加到对应key的值后面。

StartKVServer

初始化服务器的kvMap和pushAppendCache。

1
2

kv.kvMap = make(map[string]string)
kv.pushAppendCache = make(map[int64]PutAppendReply)