MIT 6.824: Distributed Systems- 实现Raft Lab3A

接上文《MIT 6.824: Distributed Systems- 实现Raft Lab2C》,Lab3A要求基于Raft实现分布式kv server,支持Put/Get操作,并且要求设计满足线性一致性。

线性一致性,站在客户端视角应该满足以下特性:

  • 对于单个client来说,发起OP1必须等待其结果返回,才能执行OP2,必须是顺序的(上锁或者排队提交)。
  • 多个client可以并发请求。
  • 一旦有1个client读取到新值,那么后续任意client的读操作都应该返回新值。

我们需要自己实现kv server和kv client来满足线性一致性要求,底层依赖我们在Lab2B实现的raft。

已通过MIT单元测试:

Lab2A实现

Clerk客户端

每个客户端启动后随机分配clientId,确保全世界唯一,此后每个请求由单调递增的seqId标识。

seqId用于实现写请求的幂等性,避免重试的RPC导致KV存储写入多次数据,这块幂等性逻辑最终体现在Raft log提交那块。

leaderId缓存最近通讯的leader节点。

PutAppend调用

请求与应答。

该请求被唯一ID标识用于幂等处理,与当前认为的leader通讯,如果返回失败则可能因为超时或者Leader切换导致提交失败,需要重试。

Get调用

请求与应答。

类似PutAppend逻辑,只是会多一个ErrNoKey的特殊错误,除此之外的错误是因为leader切换或者超时而导致失败,需要继续重试来得到最终结果。

启动KV Server

利用kvStore存储应用层状态(纯内存,宕机重启基于raft log回放复原),reqMap存储正在进行中的RPC调用,seqMap记录每个clientId已提交的最大请求ID以便做写入幂等性判定。

Op日志

这是写入raft层的日志,需要有客户端的ClientId,SeqId做提交幂等处理,需要有操作类型与值,需要有写入Leader时的log index和term以便raft提交日志时判定是否发生了leader切换。

OpCtx请求上下文

当raft log提交时,需要找到正在阻塞的RPC调用,唤醒它并返回客户端,因此用OpCtx来做请求上下文。

PutAppend处理

先把Op写入Raft,保存请求上下文到对应index,然后就是等待index位置的log被raft集群提交了。

如果index位置提交的log,其term与写入leader时的不一样,那么说明期间leader已经切换,需要让客户端重试。

还有一种情况是leader切换导致当前node写入的日志被截断,index位置持续没有提交,那么超时返回客户端,让客户端重试来确认。

Get处理

与PutAppend类似,为了线性一致性,把读操作也作为一条log写入raft等待提交后再响应RPC。

applyLoop日志提交

不断监听raft层的已提交日志,如果是写操作则判定Op的sequence id是否过期,过期则跳过,否则生效到kvStore。读操作则将kvStore此时的k=v保存到opCtx,并唤起阻塞的RPC。

总结Lab3A

  • 线性一致性要求,客户端必须串行发起OP,并行发起OP服务端无法保证前1个OP生效,实际工程里我认为应该客户端对请求排队编号seqId,串行提交给KV server。
  • 只要保证每个client的ID能够唯一,那么seqId无需持久化,保证clientId唯一还是比较简单的,比如用:ip+pid+timestamp就可以。
  • 写入幂等性通过比较clientId最后一次提交日志的seqId,来确定是否可以执行当前OP。
  • 读取的一致性则是通过向raft写入一条read log实现的,当read log被提交时再把此时此刻kvStore的数据返回给RPC,那么RPC看到的数据一定是符合线性一致性的,即后续的读操作一定可以继续读到这个值。
  • RPC服务端要做超时处理,因为很有可能leader写入本地log后发生了选主,那么新leader会截断掉老leader写入的log,导致对应index位置持续得不到提交,所以要通过超时让客户端重新写入log来达成提交,得到最终结果。

如果文章帮助您解决了工作难题,您可以帮我点击屏幕上的任意广告,或者赞助少量费用来支持我的持续创作,谢谢~

MIT 6.824: Distributed Systems- 实现Raft Lab3A》有7个想法

  1. 王祺

    博主, 我在LAB4B时有个样例有时过不了,回头重新审视了代码,发现LAB3A可能有个BUG,如下,
    函数func (kv *KVServer) PutAppend(args *PutAppendArgs, reply *PutAppendReply) 中
    如果发生了如下情况,对于serverRPC的清理上下文,如果在清理上下文之前, select { case <- opCtx.committed: 超时之后,如果applyLoop处理掉了提交的日志,那么服务器依然会返回wrongleader,此时客户端认为请求没有被处理,实际上请求已经在服务器落地了,造成客户端之后的重复请求都不会再返回OK了(seqId已经被记录了)。应该需要在func()清理上下文闭包拿到锁以后中进行一次double check 检查管道opCtx.committed吧?

    话说不知道有没有啥好的DEBUG建议= =求教

    回复
    1. yuer 文章作者

      对,rpc前后是需要考虑如何做活锁的,因为没法死锁住rpc过程,所以如何check是不是当时的上下文是关键。

      具体debug的话就是打印log证明才猜想吧,需要磨一磨,坚持下去!

      回复
    2. 匿名

      Put和Append有seqId说明已经执行过了,Get的话具有幂等性这里不会特殊判断,超时重发获得新的index即可。只要RPC请求还在就会获得返回值。如果跟博主实现方式相近的话,你问题应该不在这里感觉。你最后发现问题在哪里了吗?

      回复
  2. 匿名

    写入指针是对的吗?不应该写入Op吗,因为其他的follower节点在这个地址上不会是同一个值,求解.

    回复

发表评论

您的电子邮箱地址不会被公开。