前言

• 本篇是对于 2022-MIT 6.828 的对于 Fault-tolerant Key/Value Service 的试验记录；
• 如果发现内容上的纰漏，请不要悭吝您的键盘。

一点点的背景常识

In this lab you will build a fault-tolerant key/value storage service using your Raft library from lab 2. Your key/value service will be a replicated state machine, consisting of several key/value servers that use Raft for replication. Your key/value service should continue to process client requests as long as a majority of the servers are alive and can communicate, in spite of other failures or network partitions. After Lab3, you will have implemented all parts (Clerk, Service, and Raft) shown in the diagram of Raft interactions.

The service supports three operations: Put(key, value), Append(key, arg), and Get(key). It maintains a simple database of key/value pairs. Keys and values are strings. Each client talks to the service through a Clerk with Put/Append/Get methods. A Clerk manages RPC interactions with the servers.

Your service must provide strong consistency to application calls to the Clerk Get/Put/Append methods. Here’s what we mean by strong consistency. If called one at a time, the Get/Put/Append methods should act as if the system had only one copy of its state, and each call should observe the modifications to the state implied by the preceding sequence of calls. For concurrent calls, the return values and final state must be the same as if the operations had executed one at a time in some order. Calls are concurrent if they overlap in time, for example if client X calls Clerk.Put(), then client Y calls Clerk.Append(), and then client X’s call returns. Furthermore, a call must observe the effects of all calls that have completed before the call starts (so we are technically asking for linearizability). Strong consistency is convenient for applications because it means that, informally, all clients see the same state and they all see the latest state.

Lab 3 是要实现通过 Clerk 对象去代理用户 Client 来实现与 KV Server 的交互的三个接口，别离是 Put(), Append() 和 Get()。而这些接口的 KV Server 端的实现就是要依赖咱们先前在 Lab 2 实现的 Raft 库提供的 Replication 来实现 fault-tolerance 的。而 Client 和 KV Server 的接口通信是利用两种 RPC Request 来实现的，别离是 PutAppend() 和 Get()。接口 Put() 和 Append() 将会复用同一个 PutAppend() RPC。

最初说一下我本人对线性一致性的了解。比方 KV Server 的状态机当初有 (K: x, V: 0)。此时有客户端 C1 发送 Put(x, 7)，客户端 C2 发送 Get(x), Put(x, 42)。线性一致性就认为这三个申请别离都是在某个霎时实现的，当然理论不可能霎时实现，只是从后果上看像是霎时实现的而已。不同客户端之间因为是齐全并行的，申请的霎时能够随便，但同一个客户端的申请是串行的，前一个申请霎时必须在后一个申请霎时之前。如果零碎未满足线性一致性，客户端 C2 可能会拿到 (K: x, V: 7)，并且状态机是 (K: x,V: 7) 的后果。在线性一致性的状况下，这个后果无论怎么排列组合这三个申请都是无奈呈现的（注：Get(x) 肯定会在 Put(x, 42) 之前实现）。这个后果只能是 KV Server 1 响应了 Put(x, 7) 提交并利用到状态机之后在返回给客户端之前挂掉了，之后 RPC 超时之后客户端 C1 向 KV Server 2 重试发送该申请，但这个申请是在 KV Server 2 解决完 Put(x, 42) 之后响应的，因而这个谬误的后果就产生了。

理解完了根本状况之后，如果你是刚刚实现了 Lab 2，就能够趁热看测试代码和实现局部开始上手写了。Lab 3 的难度绝对于 Lab 2 要简略很多。

试验伪代码

1. 本人的实现没有用到 Raft.Start() 返回的 Index，因为将客户端申请和 ApplyCh 进去的 Command 对应起来的是 ClientID 和 SequenceNumber。这是为了保障线性一致性须要去除反复响应的申请，而 (ClientID, SequenceNumber) 二元组能惟一确定一个申请。ClientID 由客户端本人抛一个 64 位的随机数决定，这个实现曾经足够好来通过测试了，因为两个 ClientID 撞车的概率为 1/10^64 根本能够认为不可能，但实在的生产环境必定不会用这种毫无健壮性的实现。SequenceNumber 是同一个 Client 的申请的序列号，以后申请胜利响应后 Client 的序列号自增一，否则还是用原来的序列号发送同一个申请。
2. 同一个 Client 同一时间只会发动一个申请，不同申请间是严格串行执行的，如果这个申请失败 Client 还会一直重试，所以 KV Server 端用一个从 ClientID 映射到“申请后果”的 HashMap 来进行后果的返回和查重。
3. 模拟 Lab 2 测试中 config.go 中 appliersnap() go routine 去接管来自 applyCh 的 ApplyMsg，并利用到状态机，最初写到对应 ClientID 的申请后果中去。
4. 伪代码将省略获取和开释锁的机会。

构造体及常量定义

/* client.go */

type Clerk struct {servers []*labrpc.ClientEnd
    // You will have to modify this struct.
    serverHint  int
    clientID    int64
    sequenceNum int // log sequence number
}

/* server.go */

const (
    PUT    = 1
    APPEND = 2
    GET    = 3
    //CheckTime = 1 // best result
    CheckTime = 2 // better enough
    // CheckTime = 3 // a little bit slow
)


type Op struct {
    // Your definitions here.
    // Field names must start with capital letters,
    // otherwise RPC will break.
    T           int
    K           string
    V           string
    ClientID    int64
    SequenceNum int
}

type ApplyResult struct {
    E           Err
    V           string
    SequenceNum int
}

type KVServer struct {
    mu      sync.Mutex
    me      int
    rf      *raft.Raft
    applyCh chan raft.ApplyMsg
    dead    int32 // set by Kill()

    maxraftstate int // snapshot if log grows this big

    // Your definitions here.
    StateMachine map[string]string
    resultMap    map[int64]ApplyResult
    persister    *raft.Persister
}

// Put or Append
type PutAppendArgs struct {
    Key   string
    Value string
    Op    string // "Put" or "Append"
    // You'll have to add definitions here.
    // Field names must start with capital letters,
    // otherwise RPC will break.
    ClientID    int64
    SequenceNum int
}

/* common.go */

type PutAppendReply struct {E Err}

type GetArgs struct {
    Key string
    // You'll have to add definitions here.
    ClientID    int64
    SequenceNum int
}

type GetReply struct {
    E     Err
    Value string
}

• KV Server 端被 Client 申请拉起的 RPC 线程是通过相似在 Lab 2 的定时器一样去用半轮询的形式来查看申请音讯有没有被解决好的，轮询距离设为 2 毫秒曾经足够好了，因为我的 Raft 库通常同步一个日志从 Start() 下传开始到 applyCh 进去均匀 3 毫秒左右，性能也能够。当然你也能够应用 channel 来实现成果一样。

客户端

/* Client end pseudo code */

func (ck *Clerk) Get(key string) string {
    // You will have to modify this function.
    Create & config argument and reply

    Send 'Get' RPC request

    for reply.E != OK && reply.E != ErrNoKey {
        // try again
        Redirect to other server
        Send 'Get' RPC request
    }

    ck.sequenceNum += 1
    return reply.Value
}


func (ck *Clerk) PutAppend(key string, value string, op string) {
    // You will have to modify this function.
    Create & config argument and reply
    
    Send 'PutAppend' PRC request

    for reply.E != OK {
        // try again
        Redirect to other server
        Send 'PutAppend' RPC request
    }

    ck.sequenceNum += 1
}

服务端

/* Server end pseudo code */

func (kv *KVServer) applier() {for kv.killed() == false {
        m := <-kv.applyCh
        if m.SnapshotValid {Decode StateMachine & ResultMap from the Snapshot} else if m.CommandValid {kv.applyMsg(&m)
        } else {Do nothing}
    }
}

func (kv *KVServer) applyMsg(m *raft.ApplyMsg) {op := m.Command.(Op)

    if kv.resultMap[op.ClientID].SequenceNum == op.SequenceNum {return}

    Result := Apply op into StateMachine
    Record the Result into corresponding ResultMap
    
    if kv.maxraftstate != -1 && kv.maxraftstate <= kv.persister.RaftStateSize() {
        Encode StateMachine & ResultMap into Snapshot
        Call Raft Snapshot
    }
}

func (kv *KVServer) Get(args *GetArgs, reply *GetReply) {if args.SequenceNum != kv.resultMap[args.ClientID].SequenceNum {
        Create & config Op
        
        kv.rf.Start(op)

        _, term, isLeader := kv.rf.Start(op)
        if !isLeader {return}

        for args.SequenceNum != kv.resultMap[args.ClientID].SequenceNum {time.Sleep(CheckTime * time.Millisecond)

            currentTerm, _ := kv.rf.GetState()
            if currentTerm != term {return}
        }
    }
}

/* PutAppend 和 Get 简直统一 */

后记

我本人 Lab 3 的测试卡住的起因全是因为 Raft 库里的问题，但让我诧异的居然这些问题并没有在 Lab 2 的测试中裸露进去，因为我过后是每个局部的重要的测试都测了 3000 遍以上。一个是 Snapshot 中的一个 typo，但就这个 typo 找了一下午，属于是毕生之敌了……。另一个是 Leader 计算 CommitIndex 的代码 out of Log range 了。简略 Debug 了之后都没问题了。

Lab 3 要求整个测试的 real time 不超过 400 秒，CPU time 不超过 700 秒，TestSnapshotSize 的 real time 不超过 20 秒。能够看到均达到了要求，并且最初一个测试跑了 3000 遍没有一个挂掉，Lab 3 完结，应该是目前来说最简略的试验吧（

心田 OS：

听群友说 Lab 4 会比 Lab 2 还难，我间接？？？

（咕，鲨了我罢）