• 欢迎大家分享资料!前往留言板评论即可!

MIT 6.824 Distributed Systems 分布式系统课程系列3 Lab3-Fault-tolerant Key/Value Service

合宙 模组资料网 5个月前 (05-15) 82次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

MIT 6.824 Distributed Systems 分布式系统课程系列3 Lab3-Fault-tolerant Key/Value Service

  • 实验主页:https://pdos.csail.mit.edu/6.824/labs/lab-kvraft.html

* 任务:在raft基础上实现一个分布式可容灾的kv服务。

1.介绍

  • 在Lab2中我们学习并实现了raft算法。有了raft,我们其实已经实现了数据的一致性存储和容灾。
    比如起3个raft节点,把一批数据存进某个节点,数据在三个节点上都会保持强一致性。
    整个系统可以承受在某个时间点有1个节点出现故障。
    如果配置大量节点,比如9台服务器,可靠性会非常有保障。可承受4台机器同时出故障

  • 这次任务是在raft的基础上实现一个key/value服务。
    虽然是一个相对简单的kv服务,但是掌握基本技术之后可扩展为更复杂的应用,比如分布式数据库或分布式文件系统等等。

  • 任务分为AB两部分。A部分是基础的kv服务。B部分引入log压缩(log快照)。


2. kv服务

架构

  • 有数个raft节点。实现数据一致性。

  • 有数个kvserver实体。存储实际的kv数据。可看作数据库实体。
    一个kvserver绑定一个raft节点。

  • 可有任意多个client实体,即客户端。可以看作连接数据库的客户端工具。

  • 比如有3台机器,每个机器上跑一个kvserver,每个kvserver里包含一个raft节点。
    raft节点之间可互通。kvserver可与自己的raft节点交互。
    client为任意多个,可与任意kvserver交互。

数据

  • 数据就是简单的key和value键值对。都是string类型。

操作

  • 实现3个操作:Put(key, value)赋值,Append(key, arg)追加,Get(key)取值。

实现

一些要点

  • 只要多数server能互通,client发命令必须要能返回,不能无限卡死。否则允许卡死。
  • client发一个命令必须等到server回复才能返回。这里肯定是简化了,现实应用肯定得有个超时提示。
  • 没有commit的log可能被清掉(别的命令覆盖)。一旦commit,就不能被清掉,如果发生,那数据就坏了,就是实现有问题。
  • 看一下论文第8章,少走弯路。

基本流程 TestBasic3A

  • GenericTest是通用的测试流程。包含起kvserver,起client,发命令,设置网络故障、网络分组,重启节点等各种测试流程。

  • 最简单的测试。5个server

  • make_config
    对每个server调StartServer(我们实现)进行我们kv服务的初始化:起一个KVServer,KVServer包含一个raft节点。

  • makeClient
    用MakeClerk(我们实现)创建客户端(他所谓的clerk)。

  • 一些初始化后进入测试循环。

  • spawn_clients_and_wait
    起一个channel
    用run_client起一个client并调用循环里的闭包
    等待channel的数据

  • 闭包函数主要做一顿kv操作。先put一个值。
    再进入一个循环(会持续5秒(见done_clients)),每次随机选一个操作:
    1.append。key是server id,value是根据循环造的一个值。并记下append后的值。
    2.get。用key获取获取value,跟记下的值对比。不一样就是测试失败。

  • 5秒过后
    做一些模拟(断网、重启等),现在是最简测试,所以跳过。
    对每个server的kv进行检查(checkClntAppends)。因为存入的值是定了规则的,所以可检查正确性。
    最后对log的大小做一些检查

  • 代码可总体分为3层:client,server,raft。
    client可看作各种数据库连接工具。处理人类或测试程序发来的请求,与server交互,获取结果。client可以自己选择连哪个server
    server实现kv存储,与raft系统交互,根据raft的指示来执行实际的kv操作。
    raft负责每个kv操作在整个系统中的一致性。
    例如一个命令来了以后,raft得把它安全复制到多数server后才通知server这个命令已经完成复制了,可以执行。然后各个server才能执行这个命令。然后client才能看到这个命令执行的最终结果。

  • client.go里。Get和PutAppend,直接给server发Get和PutAppend的rpc。
    client把命令发给谁?
    应该找leader发,并记录每一次的leader。如果leader改变,rpc应该返回相应的错误,client就找新的leader。

  • PutAppend怎样算成功?
    命令提交给raft,按说要等raft把这个命令复制到多数server,再发apply消息后,kv服务才真正执行PutAppend,再返回成功。
    看测试代码是Append之后必须Get到正确的值,也就是应用层面是不考虑任何超时的。
    所以为了迎合测试,每次发命令一定要等到正确执行才返回。
    在server里rf.Start()之后,要死等apply消息,等到才返回。
    这里可以思考一些异常,如果leader apply这个之后马上挂了。下次这个client发命令时会连一个新的leader。这时会不会造成重发?各server的命令数据是否正确?

  • rpc的reliable问题
    发rpc如果能收到正常回复,无论成功还是失败,都是好的。
    如果rpc无响应,就麻烦,无法确定是什么情况。
    测试程序可以模拟rpc不稳定,可能
    1.对端收不到rpc(不执行)。
    2.对端收到rpc,执行以后,回复结果时网络不通。
    这两种情况rpc都会失败,得重发,但是2的情况可能造成一条命令重复执行。
    想到序列号的方法,给每一个命令做一个唯一的sn,收到命令后每次判断一下sn是否已经执行过,就可能避免重复执行了。也保证了操作的幂等性。怎么做唯一sn?现实中应该也是很有讲究,这里直接用随机数简化。

  • ApplyMsg的接收
    在每个kvserver里起一个ApplyTask的goroutine专门收ApplyMsg(在lab2里是测试程序收的这个消息),收到就实际执行命令。
    对于不是收命令的server,不做其他事情。
    如果是该server接收的命令,那么得通知client命令已经执行完,让client返回。前面说过现在的模式是client发命令必须死等一个确切的结果。
    我加了另一个channel来传这个消息。

TestOnePartition3A

  • 这个测试把server分割成两个群体,把当前leader放在少数群体。

  • Put(cfg, ckp2a, “1”, “15”)发到少数群体,是无法commit的,也就无法apply,client也就阻塞无法返回。
    直到走到”Test: completion after heal (3A)”,恢复所有网络,p2的leader发的ae可以传到p1了,p1的leader发的ae也可以传到p2了,这时p1的leader的term一定是领先p2的,因为分割后p1没有leader,一定会选一个新的,term变大。
    那么p2的leader一定会变成follwer。p2接收的Put命令会被p1的命令冲掉。kvserver应该返回wrongleader给client,client重新找leader发这个命令。
    重点是kvserver执行命令等结果期间要能识别自己的命令被冲掉(因为自己的leader身份失效)。

  • Get()必须从多数群体中获取,否则可能获得失效的数据。
    课程提示一个简单的方法。可以把Get也看作PutAppend,也走一遍一致性流程,这样肯定是从多数群体取值了。

  • 一个死锁问题
    LeaderSendAE里发ApplyMsg时我是先锁住rf然后进循环挨个检测index是否可以apply,有时会出现一次可以apply多个index的情况。
    那么问题来了,循环里会往channel发消息,这样就带着锁到了一个kvserver的线程,这个线程里又会走到一个rf.GetState()的检测,GetState是要锁的。如果LeaderSendAE的第二个消息没发出去,就走到GetState()的话,就死锁了。
    把ApplyMsg消息的发送挪到一个单独的goroutine,结构更好,耦合低,循环检测,每次循环加锁就行,解决问题。
    其实lab2也是这么推荐的。

  • 后话,挪到单独goroutine后,后来偶尔发现lab2的TestFigure8Unreliable2C居然过不了,能达成一致,但是很慢,耗了三分钟,测试程序最多给2分钟。而不挪出来只用40秒。
    因为挪出来后,循环里要每次加锁,这样死循环争锁影响了性能。
    还是改为最开始的方式,循环外面加锁,里面发消息。而接受消息的代码之前刚好做了优化,不连续发消息,而是设置kv的全局变量,另起goroutine来监控。所以不会死锁了。
    注意死循环里看情况要加个sleep,否则会很卡。
    最终形态就是死循环里每轮sleep10毫秒,争锁,然后循环发一波apply。
    但是有个问题,在最坏的情况下,每一波只能apply一个命令的话,还是很耗时。当然如果每次来一个命令也说明命令不是很多。
    一个很好的优化就是把多个apply打包一次发走。暂时跳过。

  • go test -race的问题
    可以检测可能的race condition。比如有个变量某一处加了锁,另外一处没加,运行时如果出现篡改的可能,它就会检测出来报错。
    是否有必要?比如有的地方我绝对有把握不会死锁。
    如果统一加上锁肯定能避免一些难查的死锁。在lab2里试过,感觉有的地方略显啰嗦。特别是打印变量时,比较繁琐。

以下走进了死路

TestManyPartitionsOneClient3A
  • 一个client。随机分组。
    发现一个问题。如果client发了一个命令cmd1,leader1短暂变成follower,client返回准备重发cmd1,leader1这时又变成leader.
    那么记过就是client认为只发了一个cmd1,但实际leader1上存了两个cmd1。
    问题在于client被返回wrongleader时,第一个cmd1没有被删除。一般情况如果有leader2取代leader1,那么会把cmd1擦掉,没问题。
    但如果leader1又做回leader,那么老的cmd1就会保留,出现重复。
    可能的解法:
    start会生成一个index,跟踪这个index,如果能apply,没问题。如果被擦除,返回wrongleader。其他情况都死等。期间不要自行检查leader。

  • 这又会引出一个问题,一个命令可能会单纯被清掉而不是被覆盖(比如一个高term的leader1复活,发ae给leader2,leader2变成follower并且被清掉不同的命令)。
    考虑上面说的情况:(ca为commit和apply。t1为term1。)

123456
2 Leader1put”0 cax 0 0 y cax 0 1 y ca t1x 0 2 y t1
1 Leader2put”0 cax 0 0 y cax 0 1 y t1t2
3
4
5
  • 2先当leader,给2发一个命令,未复制成功时,被独立分割,1再当leader。
    这时把1和2联通。1和2的身份都是leader。
    2给1发AE会失败,因为term小。
    1给2发AE会成功。因为1、2两点都通过。

  • 问题是到底需不要把2的index4上的log删掉?
    论文图2收AE的第3点。字面上是如果出现冲突要删掉冲突和之后的log。目前的实现是删掉。
    如果把index4删掉,然后白等,就会导致index4没法apply。导致client卡死。因为按上面的等待index的实现,没考虑直接删除index4的情况。

  • 如果不删,这时2会变成Follower,1继续做leader,虽然2比1多一个命令。
    如果这时给1发命令。1会发ae把2的index4冲掉。
    如果一直不发,那么2的index4的命令永远得不到返回,造成cleint卡死。那么这个情况按理要给这个client返回wrongleader吧。

  • 想个办法,还是按删掉的实现来。
    raft做个接口查询某个index上的命令。kvserver定时把正在等待的index查一遍,如果发现被删除,那么返回wrongleader。

按这个思路来,感觉问题越来越多,越来越复杂。是不是钻了牛角尖?

  • 再从头理一遍client的交互。
    client发命令,每个kvserver里起一个map判断重复,记录每个client的最高sn。
    防止的是:实际commit但没有返回给client,比如rpc故障,client又把命令提交一遍。
    这里有个问题,如果这时出了新的leader,client重新提交给新的leader,是否能防住?
    如果是的话,那么是可以在kvserver里给等待命令设一个超时的,不死等index,而是返回让client重发命令。直接从源头解决了问题,不会造成client卡死了。
    为什么重发命令给新leader可以判断重复?
12345index
—–>0 Leadercmd1
1cmd1
2cmd1
3
4
  • client先连0,成功复制到012,commit,这意味着cmd1在系统里是确定的,一定会执行,不会被清除。
    当raft返回apply消息到kvserver时(这里简化为一定能成功返回apply消息),kvserver会记录cmd1的client和sn,这样后续就能判断重复了。
    注意,发到0,但是012收apply消息时都会记录。这样后续再发到012时都能判断重复了。
    下一个命令有没有可能发到3或4,不可能,因为34是少数,不管网络怎么分割,新leader一定是在012中产生。
    也就是说只要命令得到成功复制,新的leader一定存了这个命令的唯一标识,一定可以判断出重复。
    一个不爽的地方是重复的命令也会存到raft的log里,如果要做恢复数据等操作,还需要判断重复。

  • 因为开始没有完全想清楚判断重复命令的细节,所以绕了弯路。
    最后在kvserver等待index那加上超时返回wrongleader,让client重发。解决了重发问题。
    过了partitions, one client和partitions, many clients这两个测试。

TestPersistOneClient3A

  • 从这开始,会重启kvserver。raft的log已经实现了持久化没问题,但kvserver也是有很多状态和数据的。
    课程里好像没有直接提怎么恢复kvserver的数据。只在Part B开始时带了一句,As things stand now with your code, a rebooting server replays the complete Raft log in order to restore its state.
    那么就从raft的log里恢复数据试试。
    replay比想象的要容易,把rf的log跑一遍,同时更新命令sn信息,判断一下重复命令不要执行就行了。

  • 到这里3A都通过了测试。跑一遍耗时4分钟。

go相关

  • 发AE时rpc传的arg参数在接收的地方变成了nil。
    导致panic: runtime error: invalid memory address or nil pointer dereference
    最后定位到labrpc.go的dispatch函数和value.go里的Elem()。
    估计是新的命令类型造成。之前的命令是一个int没有问题。
    我直接传的PutAppendArgs类型报错。后来用了server.go里他定义好的Op类型就不报错。搞不懂,用不同文件的类型会出这种错。
    一堆reflect、value、type比较底层的东西,看不懂放弃。有恶心到。

  • 简单情况下,channel如果没有人接收消息,发消息就会一直阻塞?

  • 消息里放int64好像有时发不出去。不确定。

  • 居然不能直接给map里的某个元素赋值


3. log压缩

论文解读

  • log不能任其增长。如果量巨大,即占空间,replay也很耗时。
    需要一个机制来把老的的log信息给挪走。

  • “快照”是一种最简单的压缩方式:
    在某个时间点,当前系统的整个状态会存为一个快照并持久化备用,然后把这个时间点之前的log删除。

  • chubby和zookeeper都用到了快照。

  • 作者又比较了一下其他的log压缩方法。结论是快照更简洁。

  • 图12描述了raft的快照。
    一个快照包含了最后的term和index,以及每个key的当前值(只保留最新的值,过程(log)丢弃)。

  • 图13描述了具体算法。即“安装快照(IS)”rpc。
    IS一定是leader发出。可分次发送(我们实际不实现),可作为一次心跳。

流程

  1. kvserver每次收到正常apply的命令后需要检测一下raft的log大小,超出一定值就要发起存快照的操作。
    把本地kv数据发给raft,raft删除被快照覆盖的log,再把快照和log持久化。
    重要的原则是保持所有数据不丢,要么在快照里要么在log里,并已经持久化。

  2. 每个节点只保存一份快照。保存快照后,要记录快照最末log的index和term。

  3. leader发AE时如果对端需要的index落在自己的快照里,给对端发自己的快照,即InstallSnapshot RPC。
    否则正常发AE。

  4. raft收到快照后判断有效性,再把快照发给自己的kvserver,kvserver拿到后直接覆盖本地kv数据。log和快照都要做好持久化。

实现

  • 引入快照后,log的一些边界上的操作可能需要大范围改造,改得更通用、清晰,是一种进步。
    改动后一定要保持lab2能通过测试。
    可能需要折腾一番才能稳定下来。

一个错误场景

  • TestSnapshotRecoverManyClients3B报错。get出来的值是值比预期要短,是个旧的值。

  • 原因:raft收到有效的快照后,把本地log清空,发给kvserver安装,但是没有持久化。
    如果这时服务重启,这个raft节点选为leader,数据就丢失了,因为log删了,log持久化了,但快照却没持久化。违反了上述数据不能丢失的原则。

go相关

  • go test -race的问题
    出现一个经典的ab/ba死锁的情况。检测不出来。具体没懂。

  • channel的问题
    循环阻塞读消息进行处理,里面加锁,容易死锁。可改成读出消息后进队列,再另起goroutine循环处理。


喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址