NaroZeol

Student

该lab是2024年的课程新增加的一个，但是难度定位不高，只有两道easy的任务。

但是个人实现起来还是相当头疼的，期间踩了很多的坑

Key/Value Server

要求

该lab要求实现一个具有良好语义的Key/Value服务器

要实现的操作是Get, Put, Append。

具体如下

  • Get

    该操作给予一个Key字符串，要求服务器返回该字符串对应的Value，如果不存在该Key则返回空字符串

  • Put

    该操作给予一个Key-Value对，如果Key不存在则新增该键值，如果Key存在则覆盖原Value。不要求返回原字符串

  • Append

    该操作给予一个Key和一个Arg。要求将Arg附加到该Key对应的Value上，如果Key不存在则认为附加到空字符串上。要求返回该Key对应的原字符串

Key/value server with no network failures

如果假设没有网络错误，则所有的RPC都不会失效，所有的请求都会被处理且只处理一次，生活会变得非常美好，但可惜事情总是不如人意。。。

不过在这里我们先假设不会出现错误，先构建一个简单的雏形

该部分主要是熟练使用RPC包，用一把大锁保护map即可。

Key/value server with dropped messages

现在不开心的事出现了，所有的网络请求都会发生故障

故障分为两种

一种是client的请求丢失，一种是server的返回消息丢失

两者的区别在于，第一种不会对服务器上的数据产生任何影响。但是对于后者，服务器已经完成了任务，但是用户没有收到完成的信息

client端的修改

实验框架中的RPC在指定时间内没收到响应则认为失败，此时RPC的Call函数就会返回false

对client端要做的处理比较简单，只需简单地重试即可

使用类似如下的代码即可实现：

for {
    ok := ck.server.Call("KVServer.***", &args, &reply)

    if !ok {
        DPrintf("[Client] Call ***(%v) failed, retrying...", args)
        continue
    } else {
        DPrintf("[Client] Call ***(%v) successed", args)
        break
    }
}

server端的修改

对要求的解读可以得知可以假定单一客户端在同一时刻只会调用三种操作中的一种，这给我们的实现带来很多便利

server端要处理的问题是如果网络中发生的故障是第二种故障，那么server端会在完成一次操作后收到相同的操作请求时，如何处理这些相同的请求

无需修改的Get和Put

通过对要求的分析可以发现，三种操作中，因为服务器支持并发访问，Get和Put在语义上其实并是允许重复执行的

Get不影响任何服务器的任何数据，只需要返回当前的数据即可。就算客户端发起任意次访问，只需要照做即可，服务器的状态都维持一致。而Put操作也是如此，因为Put不要求返回之前的数据，所以Put重做多少次对服务器的影响都是一致的

因此真正不能多次执行的操作只有Append，因为其的多次执行会对服务器造成不同的影响

等停结构

在处理Append的多次执行问题，我借鉴了计网中提到的等停协议

首先要保证每个客户端具有一个可供唯一标识的ID，框架中提供了一个生成随机数的函数，就直接用这个了

在我设计的等停协议中，客户端维护一个bool变量，称之为opstate。对于每个客户端，服务器也都维护一个对应的opstate。初始时所有的opstate都为false

同时服务器也存有每个ID对应的上次成功的Append调用的返回值

工作流程如下：

  1. 客户端设置RPC调用参数，将ID,opstate包括其中
  2. 客户端翻转opstate
  3. 客户端发起RPC调用，服务器收到含有ID和opstate的RPC调用请求

  4. 服务器检查RPC调用参数中opstate是否和自己维护的该ID对应的opstate是否相同

  5. 如果相同则执行Append操作，完成后将返回结果存储一份，同时翻转该ID对应的opstate

    如果不相同则说明是一个重复调用，直接返回存储着的上次成功的Append的返回值

通过这样的结构就能保证客户端发起的一次Append调用只会被执行一次

内存开销的优化

这样的结构当然能完成任务，也很成功地通过了所有的测试。但这样的结构存在一些潜在的问题

  1. 服务器存储着上次Append的结果，如果这个字符串很大，相当于在服务器上会存着前缀几乎一致的两个大字符串。

    一个可能的优化方式是每次收到重复的调用，就将当前对应的字符串取出，对结尾做一些处理，删除Append的内容。这样也能做到返回Append之前的结果，但是问题在于在并发下会导致一些不一致的问题。而且要倒过来匹配字符串也不是一件容易的事

  2. 没有设计客户端退出机制，一个客户端一旦发起过Append,在服务器上就会有与该客户端相关的数据产生。因为没有退出机制，长期运行的服务器爆内存是必然事件。但既然lab没有要求我也就不做了

You May Also Enjoy