终于把lab4写到过test稳如狗了. 回顾这段时间, 看日志看得头疼. 写这个lab可比打只狼硬核多了. 能写完完全靠坚持. 当跑通test的时候, 我感觉我要high到天上去了.
剧透警告
下面涉及剧透
lab4a
4A这里有点坑的地方是要求每次rebalance的移动操作最小, 并且rebalance之后尽可能平均. 这里尽可能平均的意思是所有shard server包含的shard数 |min - max| <=1. 我之前还写了半天一致性hash, 结果test挂了, 推倒重写naive的方法.
另外一个坑是我这个rebalance的算法用到了golang map. 做到lab4b的时候发现replica的状态不一样? 这个很坑了, 我rebalance没有用io, 没有用rand, 相同程序跑下来结果不同? 后来是发现golang map iteration的顺序是随机的, 每次运行都不一样! 让我这个推崇函数式的人浑身难受. 我花了3个小时在这里.
分配算法没啥好说的
lab4b
lab3给了我们一些自己发挥的空间, 但是最终解决的方法大同小异. lab4 就很大自由了, 我还没看别人怎么实现的. lab4b的对系统有如下要求
- put/append操作的linearizability
- 在任何一个时间点, 至多一个group对某个key服务
第二点要求我们在做shard migration的时候, shard的新拥有者开始服务的时间点, 旧shard的拥有者必须在这个时间点停止服务. lab4有一个很大的挑战是, 不同group servers之间需要通信, 一旦这些通信会改变state machine的状态, 那问题就很大了:
不能让state machine自己参与通信, 因为通信这个不是确定的操作, server挂掉重新reply指令的时候, 外部世界已经变化, 通信的结果无法保证. 对某个server来说, 假设所有的通信操作都是幂等的, 那就要求外部世界能“记住并且重现”所有历史的通信请求和对应结果, 这个不大现实.
所以我的设计的时候, 设计成所有的通信都不会改变shard server的内部状态:
- 收到rpc请求时候, 只读取内部状态
- 收到rpc回复的时候, 只读取内部状态, 并且向raft提交接下来要做的操作
这样的话, 系统就变成, 有一个神秘的外部的力量, 不断地对这个系统的状态作出“最高指示”, 作为系统的唯一输入. 这样的话这个系统的状态就变成可控的了. 相信独立完成lab3的同学对此表示是常规操作.
Shard migration的算法
Setting:
- 首先, 全局而言, 有一个config的序列(其实就是shardmaster存的config序列). 一个group某时刻只处于这个序列中的某个config, 它的下标是i, 我这里写作$C_i$
- 每个shard group有两种关于migration的状态
- $S$ , serving, 表示正常运行, 处于某个固定的config
- $U$, updating, 表示正在做migration
- 状态变化为 $(S, C_i) \rightarrow(U, C_{i}) \rightarrow(S, C_{i+1})$
对于所有的shard group:
- 所有的shardserver的经历的config变化序列都是相同的, 都是严格按照全局config序列的顺序, 没有跳过任何config
- 独立线程定期查看是否有新的config, 如果有, 向raft提交: 把state machine状态设为$U$的命令$Command(Do: (S, C_i) \rightarrow(U, C_{i}) )$
- state machine收到这个命令, 告诉某个工作线程, 让他向需要的group发起migration请求, 获取所需的shard
- 只回复如下的migration请求, 并返回对方所需Shard:
- 对方config比自己旧: 对方$(U, C_k)$ 自己$(S, C_i)$, 其中$k<i$
- 对方config等于自己且自己处于更新状态: 对方$(U, C_k)$ 自己$(U, C_i)$, 其中$k=i$
- 工作线程发现所有migration请求都完成后, 向raft提交更新完成的命令, 连带着需要的shard和各种其他信息(shard带着去重的信息) $Command(Do: (U, C_{i}) \rightarrow(S, C_{i+1}), Shard)$
对于1. 不同shardserver可以在全局config序列中的不同位置, 有些server变得快, 有些变得慢. 如下图所示, 4个groups, 圈圈表示Config, 虚线表示正在更新并且尝试进入下一个config, 箭头表示正在向对方请求migration.
如何处理client的请求?
最简单做法就是
在状态$U$的时候拒绝一切请求 (#1)
而且算法第4步保证了
在任何一个时间点, 至多一个group对某个key服务
的要求. 因为一旦某个server开始服务某个新的shard, 这说明migration已经完成(第五部的command), 这就说明原先shard的拥有者已经同意migration请求, 这就说明:
- 要么server已经在新的config, 所以不会服务这个旧的shard
- 要么server在相同config, 但是在状态$U$, 按照(#1), 不会服务这个旧的shard
这里其实可以只拒绝掉那些这一轮config有, 但是下一轮要丢掉的keys就行, 这就直接过了Challenge 2.
为什么不会死锁?
上述情况 server都会处于一个等待, 请求shard, 更新config的过程. 假设有一个循环依赖的环:
- 这个环里所有server都在同一个阶段的config, 此时所有server都是$U$状态, 所有migration请求都不会被拒绝
- 这个环里存在不同阶段config的server. 那么必然存在新config的server向旧config的请求, 此时最旧的那个config的请求一定会被满足, 循环依赖被打破.
Challenges
按照上述讨论challenge 2很容易达到. 我们讨论下challenge 1, 即shard回收 这里我的方法是基于以下观察
当某个group在$C_{i}$失去某个$shard_k$的所有权后, 需要这个$shard_k$的group处于$C_{j}$, 其中$j \geq i$, 并且从$C_{i}$到现在$C_{current}$, $shard_k$都没有再次回到这个group, 那么在进入到下一个 $C_{current+1}$前, 都不会在有人喊自己要这个$shard_k$ (#2)
为什么? 因为只有一个group在进入$C_{i}$时候需要$shard_k$, 并且在$C_{i}$之后, $C_{current+1}$之前的任意一个$C_{m}(i<m\leq current)$, $shard_k$都不属于这个group. 所以, 大胆地丢弃这个shard把!
GC 算法:
- 每个group阶段性向其他group, 广播当前自己的$C_{i}$
- 每当知道有新的group进入到新的Config, 按照规则(#2), 丢弃不用的shard
关于实现的一个坑. 官方的测试用例里 TestChallenge1Delete, 会在插入大量数据和做完大量config变更之后检查raft statesize(就是你要persist的那些) + shardserver snapshot的大小. 蛋疼的是, 他插入了30KB数据, 只允许你的每个replica的raft和shardserver有2KB的额外空间…直接导致我每个shard server把所有不需要的shard都丢光光之后还是过不了. 为此我还修改了snapshot算法(之前是lazy的, 现在改成是aggressive的)和疯狂精简内部状态, 还用上了zlib(这不算作弊, 毕竟测试数据完全随机, 几乎无法压缩) 才通过. 截图留念:
按照规定, 不放代码, 有兴趣联系我蛤
最后
终于mit 6.824的lab告一段落了. 感觉自己真的在实现的过程中学到了好多. 以后估计很难有这种看日志看到眼瞎来捕捉极低概率的并发bug的经验了. 反而对自己未来可能的挑战充满了信心. 跑通test, 被虐到心态崩溃后的成功喜悦真的会让人手舞足蹈. 最开心的事情莫过于发现了官方testcase里的一个bug, 发邮件也得到了Prof. Robert Morris的肯定. 希望自己未来的工作能多和大佬们有交集把.