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来达成提交,得到最终结果。

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