6.5840 - LAB2

LAB2 任务地址 源码地址 实现思路 任务描述 此 LAB 比较适合使用增量模型一步一步来,所以实现思路也根据任务的不同要求一步一步递进。 当你看到这里时默认你已经看过了任务描述,这里再简单复述一下。我们需要构建一个 KVServer,以及一个 Clerk,Clerk 可以放松两个请求,Get 和 Put,前者试图获取一个key 的 value,后者通过 version 的值来尝试进行 kv 的创建或者更新。 构建一个基本的 KVServer 像前一个 LAB 一样,为了方便起见我们自定义一个结构体来存储 kv 和 version。如下: type Item struct { K,V string Version rpc.Tversion } 那对于我们的 server 来讲,我们自然是需要一个变量来存放item,并且最好能够快速的获取和更新结果,那根据这种需求,我们自然可以想到使用 map,并且在 map 中存放指针而不是值对象,就可以方便快速的获取以及更新对象。此外,我们还需要一个锁,以此来避免可能会有的数据竞争问题,避免一个 rpc 在操作某一个 key,另一个 rpc 在读取这个 key,导致冲突。 所以我们的 Server 可以定义如下: type KVServer struct { kvs map[string]*Item mu sync.Mutex } 接下来只需要处理逻辑上的问题就好了,没有难点。 你直接去看源代码可能会看到有sync.Map,这是我在假设读多写少的场景下做的优化,相信你可以理解其中的逻辑。 使用键值存储实现锁 对于这个需求一开始我不太理解,看了好一会儿才看懂。大致的意思就是很多个 clerk 共享同一个 key,我们要做的就是基于这个 key 实现一个 clerk(lock)对这个 kv 对的掌控权限,相当于所有权。 那大致的思路就很简单了,我们可以给每一个 lock 一个独一无二的 secret,让他给这个共享的 key 赋值为自己的这个密钥,那对于其他的 lock 而言,通过 get 请求获取到的 value 不是自己的密钥也不为空,那就说明这个 key 此时正在被别的 lock 拥有,那就不断循环尝试判断这个 value 就行了,等到 value 为空的那一刻,也就说明这个 key 被别人释放了,那就可以赋值为自己的 secret,让别人也无法获取。 ...

February 21, 2025

6.5840 - LAB1

LAB1 任务地址 源码地址 实现思路 Lab1主要有两个角色:coordinator 与 worker,worker 主动的向 coordinator 请求任务。总共两个任务: map 与 reduce,并且 reduce 依赖于 map 的结果。所以我们可以自然的让 coordinator 将整个流程分为两个模块来进行处理:一个是处理 map 任务,一个是处理 reduce 任务。 在有了大致的思路之后,下一步显然是具体的去处理任务。那处理任务又分为两个步骤,分配任务与校验任务是否完成。在这个lab 中,分配任务与校验任务都是被动的,只能依靠 worker 的请求来进行处理。所以对于 map 阶段来说,我们显然可以设计两个 RPC 请求,一个是请求分配 map 任务,一个是告知任务已完成。 有了分配任务和校验的思路之后,下一步就是如何分配与校验。根据任务要求,coordinator 主要校验的是任务是否超时,那显然我们在分配任务的时候要有一个 record 来记录某个任务被分配出去的时间,然后等到 worker 主动报备任务完成时,coordinator 来校验这个时候任务是否已经超时。但显然还有另一种情况存在,那就是 worker 接收到任务之后宕机或者因为某些原因拖延完成时间,没有办法给 coordinator 及时的反馈,那 coordinator 就需要一个主动的机制去校验一个任务何时失败,让一个任务没有反馈或者超时的时候,coordinator 可以自行的控制这个 task 接下来的行为。需要注意一点:既然我们要具体的判断某一个任务,那我们就需要对这个任务进行唯一标识,这样才能更好的存储与判断任务的状态。 说完了 coordinator 的要做的事情,worker 的工作流程就相对简单,不管是正常完成,超时完成,接收到了但是不完成。coordinator 都已经有对应的机制了,那需要做的就是在请求到任务之后去做然后给 coordinator 反馈就可以了。唯一需要注意的就是,worker 是需要转变的,比如现在请求 map 任务,过一会儿请求 reduce 任务,最后如果没有任务可做的话,还需要能够退出进程。那这里我们再结合前面的不同阶段引入一个 period(时期)的概念,为了避免混乱,我们规定时期的轮转由 coordinator 来控制,那我们可以简单的让每一次 rpc请求的 response 都带上 coordinator 的period,让 worker 改变自己的 period,当 period 是退出(全部任务完成)的时候,worker 也跟着退出就好了。 ...

February 20, 2025