MIT 6.824 Distributed Systems 分布式系统课程系列2 Lab2-Raft#

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

  • 任务:读raft论文。实现其算法。

  • 论文写的非常直白。可以大致看一遍就开始写代码。
    下面的顺序是先翻译一些重点内容,就开始写代码,发现问题,再看论文思考,这样相互推进。


1.介绍#

raft的大致背景#

  • 一致性算法,跑在一批机器上,同时维护多个副本,保证所有副本数据一致。
    可承受一部分机器失效。是大型网络软件的基石。
    著名的前辈paxos,最近十年基本统治了这一领域。但是比较难懂、难实现。大家深受其苦,所以发明了raft。

  • raft的一个主要目的就是易懂。算法有效很重要,能理解它为什么有效也同样重要。 与众不同之处:

    1. Strong leader 强化的leader。比如log只从leader发往其他节点。

    2. leader选举 用随机timer选leader。只在常用的心跳机制上稍作改变即可实现。 可简单快速地选出leader。

    3. 归属变更 用joint consensus机制进行归属变更。使得配置的更改不影响集群的运行。

  • raft的发明者认为raft比paxos等算法更好,更适合教学,更易于实现,更有效。已被各界广泛应用。


2.Replicated state machines 状态机副本#

  • 集群中有多个状态机副本,每个机器一个,核心是log副本。
    对于同一个log序列,执行的结果一定是相同的,那么如果能保证所有log副本是一致的,即使某个节点出错了,也能通过log副本恢复到一致的状态。
    比如一个节点运行某个子模块出了异常丢了数据,而这时它的log副本是好的,那么可以重新处理log副本来还原到正确的状态。

  • Byzantine fault拜占庭错误
    简单说,出现了错误,错误有可能是伪造的。比如有恶意程序发了恶意数据。

  • 非拜占庭错误:
    出现了错误,错误不是伪造的。比如网络暂时不通,消息丢失、乱序,死机等。


一致性算法的主要性质#

  1. 在非拜占庭状态下(只包含网络延迟、数据包丢失、数据包重复、数据包乱序之类)(不包含恶意数据、攻击操作)是安全的。

  2. 只要多数(超过半数)server能互联并能接入(从客户端),整个系统就能正常运转。 比如5个server的集群可以最多失效2个还能工作。 主动停止server也算作失效,失效的server之后可以再次加入集群并恢复到正常状态

  3. 不依赖时序(或者说时间戳之类的东西)来保证log的一致性。坏的系统时钟和非常严重的消息延迟可能导致系统失效。

  4. 通常情况,一旦多于半数server回应了一个rpc,那这个rpc就算是完成了。少于半数的慢的server不应影响整体系统的响应速度。


3.Paxos的问题#

  • 十年来Paxos基本成为了一致性算法的标准。地位不需多说。

  • 缺点

    1. 非常难懂。raft作者说自己团队费劲搞了一年才懂。

    2. 并没有提供一个好的开发平台,很难在其基础上进一步开发。 很多基于paxos的系统会慢慢发现有坑,然后逐渐发展出一套自己的架构。 Chubby(一个paxos的实现)就有一段描述(大意):paxos算法与现实情况有相当的出入。最终的系统可能是基于一个未被证明的协议。


4.为了易于理解的设计#

raft的一些目标:#

  • 提供一个完整、实用、通用的基础,便于二次开发和教学。

  • 安全(在所有情况下)

  • 可用(在典型的环境下)

  • 高效(通常操作下)

最难的目标:#

  • 易懂

raft的一些哲学:#

  • 以易懂的标准来做一些技术选型

  • 区分功能块

  • 减少状态,减少不确定性。


5 Raft一致性算法#

请打开论文 Raft论文链接

  • 图2以紧凑的格式描述了raft算法。

  • 图3列出了算法的重点性质

算法大致流程#

  • 从server中选出一个唯一的leader。这个leader全权负责log副本的管理。

  • leader从应用层client接收log项,复制到其他server。择机(某个安全的情况下)通知其他server们处理这个log项。

  • 最终使得log项在多数server中得到复制和执行,达成一致。

  • leader可能会挂或从集群断开,这时会选出新的leader。

  • 只要大于半数server正常运转,数据就能保证安全。

从leader这个模式生出几个子问题:

  1. leader选举

  2. log复制

  3. 安全性。如果某个server处理一个log项,那么绝不可能有其他server在同个index(可理解为log项的流水号)上处理了一个不同的log项。

重要性质#

  1. Election Safety 一个term里最多只能选出一个leader。

  2. Leader Append-Only leader绝不会删除或改写自己的log。leader只会追加自己的log。

  3. Log Matching 如果两份log有两个log项,他们的index和term都相等,那么这两份log在这个index之前的内容完全相同。

  4. Leader Completeness 如果一个log项在某个term里是已提交状态,那么以后如果有了更加新的term,这个log项在新term的leader的log中必然存在。

  5. State Machine Safety 如果一个server在某个index执行了一个log项,那么不可能有其他server在同一个index上执行一个不同的log项。

5.1 raft基础#

  • raft集群包括数个server。典型是五个,可容忍其中两个失效。
    同一时刻,server的身份可能是[leader follower candidate](L F C)。
    正常操作下只有一个leader,其他所有都是follower。
    follower是被动的:不能发请求。只能响应leader或candidate的请求。
    leader接收所有应用端的请求(如果应用端连的是follower,那么follower把请求转发给leader)。
    candidate在5.2选举中再讲。
    论文图4描述了三种身份之间的转换过程

  • raft把时间分为不定时长的term(session),所有term依次编号。
    每个term都以一个选举开始,一个或多个candidate开始竞选。成功以后得到一个leader,其他都成为follower。
    有时会出现平局,那么会重新开始选举,

  • 不同的server可能在不同的时间点观察到term的转换。有的情况下更是可能错过整个选举或term。
    比如其他人一个term都结束了,新起了一个term了,我这边才迟迟收到消息。
    term只是一个”逻辑时钟”,可用来判断一个leader是否仍然合法等等。
    必须要能确认当前实际的term。判断是否过期。
    每个server会存一个currentTerm值。server间通信时会更新currentTerm。
    如果发现自己的currentTerm小于其他server,会更新成大的值。
    如果一个leader或candidate发现自己的term过期,会变成follwer身份。
    如果一个server收到一个过期的term,拒收。

server间用rpc通信。只有两个:

  1. RequestVote rpc(RV)
    由candidate在选举时发起(5.2)

  2. AppendEntries rpc(AE)
    leader用来发起log项的复制,同时作为一个心跳(5.3)。

发rpc是异步的,阻塞的话碰到网络故障等情况效率会很差。

5.2 leader选举#

  • leader选举由心跳触发。
    server初始身份为follower。只要它不断收到来自leader和candidate的有效rpc,就一直是follower。
    leader定时发送心跳(没有log数据的AppendEntries rpc)给follower来宣示自己的leader身份。
    如果一个follower在一定时间内(election timeout)没收到这个心跳,它会认为已经没有一个有效的leader了,会发起一个选举。

  • follower增加自己的currentTerm计数,并转变为candidate。发RequestVote rpc给其他所有server请求选举,要求给自己投票,并且先投自己一票。
    这个candidate会持续发这个请求直到以下3种情况之一发生:

  1. 自己赢得选举

  2. 其他某个server赢得选举。

  3. 一直没选出来,直到超时。

  • 如果票数过半,赢得选举。
    一个server只能给最多一个candidate投票。
    成为leader后server就开始不断给follower发心跳。(阻止别人发起新的选举)

  • 选举期间,一个candidate可能收到AE(宣示leader)。
    如果收到的term大于等于自己的currentTerm,认为发送者是合法的leader,自己转变为follower。
    如果收到的term小于自己的currentTerm,拒绝之,维持自己的candidate身份。

  • 可能会出现连续选举失败。例如几个server几乎同时发起投票,这样他们各自都投了自己的票,结果就是平局。
    raft把election timeout做成随机来解决(150-300ms)。因为这样的话发起投票大概率会错开。

  • 作者还考虑过另一种ranking的方法来选举,没有这种简单而放弃。

5.3 log复制#

  • 选出leader后。leader开始接收client的请求。
    client请求包含replicated state machines(副本化状态机)可执行的命令。
    leader把命令插到log末尾形成一个新的log项,通过并发的AE发送给所有其他server。
    当log项被安全复制(怎么算安全,后续会讲),leader执行这个命令,并返回结果给client。
    如果follower卡了或挂了等等,leader仍会不断尝试发送。即使已经把结果返回给client,也会不断发AE,直到follower收到为止。

  • 图6描述了log的结构。
    每个格子存一个命令。可以想象成一个sql命令。
    term会用来检测可能的冲突状态,保证图3的一些性质。
    index是全局log的index。

  • leader会决定一个安全的时间点来执行log项。多数server复制到了这个log项的时候,就变成committed(已提交)。
    这时可能也会commit之前积压的log项,包括老的leader的log项。
    5.4会讨论因leader切换而产生的刁钻问题,并证明算法的正确性。
    leader会保存commit状态的最高的index,并通过AE发给其他server。
    当一个follower知道某个log项是commit状态后,就会把这个log项给本地的状态机执行。

  • raft保持server之间log的高度一致性,使系统更简洁、好预测、更安全。

  • 加上保证以下2点,实现了图3的Log Matching属性。

  1. 如果两个不同的log中的log项有同样的index和term,那么他们存的是同样的命令。

  2. 如果两个不同的log中的log项有同样的index和term,那么此index之前的log项完全一致。
    。。。。

  • 正常情况下L和F的log是一致的。
    如果L崩了,那么log的状态就会不一致(新leader的log可能不是完整的),并且可能历经多次L和F的崩溃,变得异常混乱。
    图7举例了不一致情况

  • raft用暴力的办法。L会强制F复制自己的log(5.4会进一步说明安全性)。
    F首先找到两个log的相同点,再把后面不一致的log删掉,再用L后面的log续上。
    这个是在F收到AE时执行。

  • L会维护一个nextIndex数组,包含下一个要发给每个server的index。
    当一个leader新上任时,会把这个数组初始化成它本身最后一个index+1。
    当F收到AE发现不一致,会通知L不一致,L会把对应F的nextIndex-1再发AE。
    持续这样操作直到得到一个一致的index。再把F不一致的log删了,再把L的后续log续到F后面。
    这里面会有一些优化空间,不用每次index-1。作者觉得实际情况下不是必要,因为一般不会出现大片的不一致。

  • 这样L不用做太多操作就能完成log统一。
    L绝不会删除或修改自己的log(图3 Leader Append-Only性质)

5.4 安全性#

  • 之前几节讲了选举和log复制流程。但并没有保证各个操作成功,没有容错机制。
    这一章引入“选举限制”,更严格地选出leader,保证Leader Completeness(图3性质4)。
    然后补全commit规则。最后证明和讨论Leader Completeness。

5.4.1 选举限制#

  • 所有基于leader的一致性算法中,leader最终必须存有已提交的log项。
    有些算法,可能会出现leader开始并没有完整的已提交log项数据,但也被选上。
    这类算法需要额外的开销来确认leader所缺失的log项,并把缺失的数据给他补上。这些算法提高了不少复杂性。
    raft采用简单的办法来保证所有之前term的log项都会在新的leader上存在。省去了“转移”的操作。
    这意味着log项只会从L传到F。即Leader Append-Only性质。

  • raft用投票机制来阻止C赢得选举,除非C包含所有已提交的log项。
    一个C必须与多数的server通信才可能赢。这个意味着每一个已提交的log项会存在与这多数server中的至少一个server上。
    如果一个C自己的log比多数的server新或持平,说明这个C拥有所有的log项。
    RequesVote rpc负责实现这个功能:
    C发起RV时会带上自己的log信息,其他server收到时会跟各自的log比对,如果自己的log比发起者的还新,就会反对。
    对比的方法,先看term,term越大越新。term相同看log,log越长越新。

5.4.2 前一个term的log项的提交情况#

  • 5.3节提到,当一个log被复制到多数server后,leader就会把这个log项设为已提交状态。
    考虑一个情况:如果leader设置commit状态之前挂了,怎么办。
    图8描述了这个情况。
    这个log项已经复制到多数server但不是commit状态,新来的leader不知道这个情况,收到新命令后会发ae把它覆盖。

  • 对于老的term,raft不会通过统计它的复制数来commit。只有当前的term,才这么做。
    一旦一个当前的log项commit后,根据Log Matching性质,前边的log都是commit状态。??????
    第一次看到这里时我理解错了,以为需要保住之前的log,其实是不能去之前term的log。
    这里先不管,在后面实际问题里会讨论。

5.4.3 安全性讨论#

Leader Completeness相关。我没看。。。

5.5 follower和candidate崩溃#

  • 之前讨论的都是leader奔溃。F和C的崩溃相对简单,而且处理方式相同。
    如果F或C崩溃,之后发给他们RVAE都会失败。
    发送者会继续不断发。如果他们恢复了,rpc会成功。
    如果收到rpc并处理完毕,但是在返回结果之前崩溃,那么也会给他重发。
    这样不会造成错误,因为raft的rpc操作是幂等的,多次收到相同的命令,结果跟执行一次完整的命令一致,并不会毁掉数据。
    这里说一句后话,实际写代码时很多时候就是在实现这个幂等性,保证乱序的、重复的操作不会把数据搞乱。

5.6 时序和可用性#

  • raft的一个原则是安全性不受时序影响,也就是说某些操作或者响应的快慢、先后不会造成错误。
    但是时序一定是影响可用性的。
    例如一个消息交互严重延迟可能导致一个C选举失败。如果没有一个稳定的leader,raft没法工作。

  • 时序对于leader选举十分重要。只有系统满足下面的要求,raft才能维持一个稳定的leader。

  • broadcastTime << electionTimeout << MTBF

  • broadcastTime是一个server并行发rpc给其他所有server并得到回复的平均时间。
    electionTimeout是5.2节讨论的选举超时时间
    MTBF是server两次失效之间的平均时长

  • 也就是说rpc的平均耗时得小于electionTimeout几个数量级,否则leader维持不了自己的地位。(5.2节讲过如果F在这个超时时间范围内没收到AE心跳,就会认为leader没了,就会发起选举)

  • electionTimeout需要比MTBF小几个数量级。

  • 当leader崩溃,可认为系统失效时间大致与electionTimeout相同。

  • broadcastTime和MTBF依赖于底层系统。electionTimeout是需要我们指定的。
    raft的rpc一般需要接收者做一些数据的持久化,根据存储条件,可能耗时0.5-20ms。
    electionTimeout大概会在10-500ms。
    MTBF可能是几个月这个级别。

  • 我通过测试的的代码发AE的间隔是100ms。electionTimeout是300ms-1000ms随机。

6 Cluster membership changes 集群成员变更#

本课程不做要求

7 log compaction(log 压缩)#

本次实验用不到这部分内容。放到下一次实验详细分析。

8 客户端交互#

下一次实验讨论

9 实现和评估#

讨论一些raft的现实表现

10 相关工作#

介绍一些一致性算法的相关研究和对比。

11 结论#

raft好。一顿吹。

12 鸣谢#

开始看代码#

go相关:#

  • defer
    可把一个代码延迟到之后执行(目前理解是return时或者函数块结束时)
    例如:
    rn.mu.Lock()
    defer rn.mu.Unlock()
    加锁解锁,一开始就写好延迟解锁。以后就不用管了。
    循环中有坑

  • waitgroup
    可能待一批任务的执行

  • closure
    闭包
    可比较方便地起goroutine。比如在一个循环中。

  • sync.Once
    可以让某个函数只执行一次

  • runtime包
    可对go的runtime进行操作,比如设置同时利用的cpu数量。

  • make(chan XXX)
    定义一个channel,可收发XXX类型的数据。

  • for m := range XXX
    遍历channel收到的数据

  • timer的问题
    time.timer有些难用。有时候stop不了。好像跟channel还有牵连。
    老师也建议用sleep,说timer很难用对。
    用sleep的话就只能隔段时间查看标志位来处理消息的接收。而且时间管理不如timer来的准确。

  • labgob warning: Decoding into a non-default variable/field XXXXX may not work
    貌似是因为在循环里调rpc,重复使用了参数。起了临时变量好了。一头雾水。


代码文件:#

  • config.go到底什么角色?辅助测试。包含大量系统信息,包括raft的数据、rpc基础设施、一堆测试函数。
    类似一个raft之上的应用程序。
    入侵感很强。

  • labrpc.go
    基于channel的rpc。

  • raft.go
    raft协议。协议都在这个文件实现。其他文件里可加打印帮助调试。

  • test_test.go
    测试代码


测试流程#

2a#

  • make_config
    设置cpu数。初始化rpc网络。初始化各种raft的数据。所有server调start1。所有server调connect。
    设置了cfg.net.LongDelays(true)。这个会导致labrpc里走一处ms = (rand.Int() % 7000)。
    这个会导致给断开的peer发rpc最高耗时6秒多然后返回失败。

  • start1
    启动或重启一个server
    先调crash1关掉server。
    初始化server的各种数据。
    起一个channel applyCh,传给raft节点,当节点执行一个命令后发消息回channel通知测试程序。
    调raft.go的Make返回一个Raft对象。存到config里。
    最后把raft对象注册到rpc服务里。

  • disconnect
    把server断开网络。rpc进出都不通。

  • connect
    把server连上网络。恢复rpc调用。

  • checkOneLeader
    检查每个term的leader是否一致

  • checkNoLeader
    确认所有server都不是leader。

发RV的架构问题#

  1. 最开始是for循环里每次等ElectionTimeout,然后依次给其他人发rv。这样阻塞肯定是不好的。

  2. 再改为并发发rv,给所有人同时发出一组rv,阻塞等结果。
    如果能快速得到超过半数的票,那么没问题。如果有半数以上的人卡了,怎么办?还是会等很长时间比如上面的6秒,才能发下次rv。

  3. 如果改成每组rv之间不阻塞(每次超时都起一个goroutine发一组rv),能不能解决。
    至少对于目前的测试程序是可以解决的。
    假设第一组rv卡了,如果阻塞等一组的结果,如果超过半数的人卡了,比如6秒,那么下一次发rv至少就要6秒。
    如果不阻塞,那么过几百ms就能再发一组rv,能加速投票。
    这里跟测试程序有关,因为它的rn.longDelays事先就决定了rpc的返回时间,而不是一旦联通就能迅速把积压的rpc返回,它一旦积压就注定要积压,所以短时间内再发一组rv是可能显著提高投票速度的。

  4. 最终形态就是每ElectionTimeout时间强制发一组rv。
    因为每次发rv时term都会+1,可以很方便做成忽略老的rv结果,只看最新一组rv。

那么就是完全异步了,那么同一时刻可能有多个发给同个server的rpc在飘,而且先后不一定。需要处理一系列相关问题。

改成异步后选举速度明显加快,测试也ok。之前时不时会有错,只有通过改它的测试代码才能过。

https://pdos.csail.mit.edu/6.824/labs/raft-structure.txt
有讨论


2b#

  • cfg.logs是怎么更新的?
    config侧,对每个server在start1里起一个channel applyCh,并传给server。
    起一个goroutine,里面不断收applyCh的数据,并更新对应的log。
    server侧,每个server自己负责发消息到applyCh。

type ApplyMsg struct {
   CommandValid bool
   Command      interface{}
   CommandIndex int
}

正常情况会这样更新 cfg.logs[server][CommandIndex] = Command

  • cfg.nCommitted(index int)
    检查每个server的log[index],
    也会检查每次处理ApplyMsg消息是否有问题(applyErr)。
    必须按index依次commit,且必须连续。否则报错apply out of order。

  • cfg.one
    对于每个连接着的server调用Start。即处理一个新的命令。
    如果有leader接受了命令,会返回命令分配的index。等待一会再用nCommitted来测试index上命令的一致性。

  • Start
    如果不是leader,不处理,返回false。
    否则把命令存log,持久化。
    等待下次发AE时带上新的log。

  • 其他server收到AE后保存新的log,查看leaderCommit,如有需要commit新的log。
    每次commit后要发ApplyMsg到applyCh告诉测试程序某个index上commit了哪个command。
    nCommitted()就是要检查所有server的某个index上是否commit了同样的command。
    可以看出同个index不能commit两次不同的命令,而且是对于所有server。
    每个server都会有自己的commit记录。

  • 怎样才算commit
    论文5.3有说当leader把一个log项复制到多数server后,这个log项就算commit了。
    我的实现是在一轮ae过后,一个log项如果多数得到复制,leader就更新自己的commit index。
    其他server在收到ae时根据LeaderCommit参数来更新自己的commit index。

  • 复制log的问题
    leader用nextIndex维护每个server下次应接收的log项index。如果leader最新的index大于等于nextIndex了,就要发新log。
    先得找到本地log中对应的index,再把从这个index到最后的log发出去。
    有的server可能不止落后一项,而是多项,比如它断网了一段时间,期间leader收到了很多新命令。
    如果落后太多怎么办,比如几个G的数据。暂不考虑。

  • one()函数失败问题。待确认。
    s0接收命令99。还没来得及发ae,s1变成了leader,而且s1先发出了ae,那么s0变成了follower。造成s0的命令99永远得不到复制。
    总结一下就是,leader收到命令后卡了,这时出了新leader,然后新leader发ae,老leader的命令得不到复制。
    看测试程序的one()函数,有个参数retry。对这个有影响,他一般是false,造成必须由一次收到命令的leader来完成整个复制过程。
    那么如果出现上面的情况,测试就会失败。
    他是为了简化所以传false。如果改成是不是更符合实际?且能通过测试。
    我开始都改成了true暂时通过了测试。(到实验最后代码又改过几轮后,用它原始的测试代码也能通过了。)

TestFailNoAgree2B#

里面起了5个server。测试过后可能导致打印混乱。有点奇怪,我没有仔细研究,在我封装的打印函数里判断一下killed()来解决。

TestFailAgree2B#

输入106命令之前。s1断开后由于收不到ae,会发起rv,同时term+1,这样等他重连以后,leader给s1发ae时term比s1小1。这样造成s1不接受ae。
就是说s1可能比leader落后很多log,但是term却比leader大。然后反而s1要变成leader。
怎么处理。
一个可能的方法:

  1. ae的success问题,其他操作是否要关联。图2AE第4点,s1收ae时不管返回结果,只要有新的log,都存下来。

  2. 图2的RV第2点,只有发rv的人的log至少跟自己持平(5.4.1最后),才可能投它的票。这样就能保证s1至少把缺失的log补上之后才能发起投票成功。
    If votedFor is null or candidateId这句有点耐人寻味,是不是说votedFor同个term最多更新一次?也就是一个term只投一个人的票。

这里后来看到官方说法,要按规则的顺序来,一旦false,就返回,不要进行后续的操作。

TestRejoin2B#

  • 这里是一个重要的场景。
    先正常出一个leader1。正常执行101命令。正常复制和commit。
    这时leader1断开,并给他单独发命令102,103,104。(可以理解为leader1正常收到命令,但是要往外发ae的时候网络开始故障)
    再给系统发命令103,这时leader1是断开的,所以其他人会开始选举,选出leader2最终接收这个103命令。
    103得到正常复制和commit。
    这时同时断开leader2,连上老的leader1。
    发命令104。因为leader1还是认为自己是leader,而且leader2已经断了,所以leader1接收104。

情况如下,就有点复杂。

log index->

1

2

3

4

5

0

leader1

重连

term1

101(commit)

102

103

104

104 (new)

1

leader2

断开

term2

101

103(commit)

2

正常

term2

101

103(commit)


  • 这时leader1认为自己还是leader。就要发ae给2。但2的term肯定比leader1高,因为2和1重新选举过,所以ae肯定失败。
    这样过一会2会算作收不到心跳,会开始选举。同时leader1发现2的term更高,会转变成follower,也收不到心跳,也开始选举。
    这种情况按我的理解2必然获胜,因为它的log更新。见图2rv的第二点,log的up-to-date,和5.4.1最后。

  • 5.4.1关于log新旧的比较:
    比较两个server自己的最后一个log项。

    1. 如果term不同。term大的新。

    2. 如果term相同。index大的新。

再看图2收rv的处理

  1. 第一条Reply false if term < currentTerm (§5.1)。这一点因为0和2在选举中会不断升高term,并且如果对方term高的话会更新自己的term,所以是个比较随机的过程,相互攀升,2的term按理一定有机会大于等于0的term。 这里的问题:

    1. 我开始的代码是把每个server的electionTimeout定死,导致有概率走到一个时间模式里,导致长时间2的term小于0,导致选不出leader。后来改成每次发RV都重置一下这个超时时间。仍有概率失败。

    2. 收rv时如果我的log比候选人新,会返回false。这时如果候选人的term比我新,我也应该更新自己的term等状态。否则仍有可能2只能靠自己升term,永远追不上其他人,导致选举出不了结果。

  2. 第二条规定候选人的log必须至少跟我一样新,才可能投它的票。
    0的term永远是101的term,而2是重新选举过的,肯定在101的term基础上变大,然后又执行了103命令,所以103命令的term一定大于101的term,所以2的log一定比0新。

  • 那么这样只可能是2赢得选举。
    然后2发ae给0,发的是103(index=2),这跟0的log是冲突的。0会删掉冲突的log,复制新的log。见图2的AE处理。
    最终0的log变成和2一样。而发给0的104命令一定会失败,得不到复制和commit,除非重发104,让2执行,这也是为什么测试代码发104打开了retry。


matchIndex的问题#

  • 这里有讨论matchIndex
    https://thesquareplanet.com/blog/students-guide-to-raft/#failure-to-follow-the-rules
    粗看matchIndex和nextIndex是相关的,可以从nextIndex推导出来。其实不对。
    matchIndex是一个事实确定的值,一定是准确的。而nextIndex是一个预判的值,只是对下一个要发的index做个引导。


go相关#

  • nCommitted()里
    cmd1, ok := cfg.logs[i][index]
    这是什么意思?其实就是从map里取值,cmd1是值,ok是取值结果,如果key不存在返回nil, false。
    元素的类型是interface{},可以存任意类型。
    https://golang.google.cn/ref/spec#Type_assertions
    https://golang.google.cn/ref/spec#Appending_and_copying_slices
    有个这样的代码
    var t []interface{}
    t = append(t, 42, 3.1415, “foo”) // t == []interface{}{42, 3.1415, “foo”}

  • channel的问题
    感觉有坑。说不清。感觉跟它的生命周期和函数返回时机有关。现象是有时会卡死。没有仔细研究,来回调整尝试几次后没出现了。


2c#

  • 首先需要实现数据持久化。可以简单地实现,不考虑效率。
    当数据发生改变,无脑把所有数据存下来。启动时把数据读出来。
    做一套默认值,如果初次启动,取默认值。

TestFigure82C#

论文图8的测试。

  • 图8我绕了半天。开始理解错了,以为它是要求把之前term2的数据给保住。然后越来越想不通。。。。
    5.4.2的标题Committing entries from previous terms,也很容易误导。
    实际它是要求leader不能去commit不是当前term的数据。因为这种情况下去提交term2,之后会被term3的数据给覆盖,造成数据不一致。
    他只是为了说明图2最后log[N].term == currentTerm的必要性!

  • (b)状态下s5添加一个命令后死了,s1重启,被选为leader,term例如为4,这时如果它把2继续复制了到了多数server,也不应该去更新自己的commitIndex为2,而是什么也不干,然后如果:

    1. s5活了,成为leader,因为它log更加新,在term3上。s5会用3覆盖其他server的index2。变成(d)的状态。

    2. s1继续收命令,并在term4上复制成功,那么才可以把commitIndex更新为3(跳过了index2)。这时根据Log Matching性质,之前term2的log一定已经是得到成功复制的。

  • 还是报错。只能看测试代码细调。
    它起了个1000次的循环(可以先改小,比如50,多试几次如果出错,就是比较大的错误)。
    每次找一个活的leader发命令(它用的随机命令,可以先改成顺序的,好看很多!) ,然后随机等待一个时间后马上把这个leader毁了,造成的效果就是图8说的,可能发ae复制到多数server了,但是没commit就死了。
    然后不断这样循环。最后全部连上,再发一个命令。

过了图8的测试后,我代码实际上基本是对的了。但莫名有时超时。

一个超时问题#

  • one只等待10秒。每一轮发命令后等2秒时间达成commit。最后的测试one会小概率失败。如果从头查会非常痛苦,得手动模拟二十多个term,所以先从最后找找线索。

  • 从log里看到的现象就是nextIndex一直在减,从100左右减到6时失败了(后来发现失败的都是减了100次左右)。
    这时想到,因为发ae收到false时nextIndex只是-=1,极端情况下两个超长的log完全不匹配,那么每次-1从尾到头就要等很长时间,造成超时。

  • 我设置的ae间隔是100ms,那么100个log粗算就是10秒左右,正好印证这个想法。

  • nextIndex减1是有优化余地的,可以简单一点,连续失败的话给他翻倍(第二次-2,第三次-4,第三次-8),成功一次归-1。效果还可以,极端情况下快了不少。

另一个超时问题#

  • 我都是同时起5到10个测试程序,还开着直播。。。我cpu是4核。
    那么有时程序会得不到cpu。容易超时。。
    这个非常坑,令人沮丧。程序其实是对的,但因为系统环境问题莫名出错。
    一度怀疑课程的rpc库是不是有问题或者windows上有问题。
    最后因为看log有时几百ms啥也没干,而且经常是一个出现超时,其他也非常容易超时,才明白过来。


测试情况#

  • 按我的理解是不能大量并行测的,cpu会不够用,我cpu4核。

  • 最后我是每次起3个,用原版的测试程序,没事就手动跑一下,跑一遍完整的2a2b2c需要三分钟出头。这样连续成功了一百次以上。分布在两三天时间里。加上之前单项测试大量成功,少量我认为是cpu原因造成的超时,我认为基本ok了。

  • 看别人的讨论,说碰到有的bug1000次才出。这个我暂时无力。后续得做个自动测试,挂着一直跑。go我也还不会,后续再看。

  • 还有说有的bug到lab3才发现。那么马上开始lab3看看!


总结#

  • 需要细心加坚强。
    要看懂它的测试流程。
    有时超时并不是逻辑问题。
    经常需要一步步跟着log推算。
    调并发逻辑需要发挥想象,注意锁和数据更新的逻辑。
    可能多次推翻之前的代码。
    卡住了就看看参考里的两篇blog和课程页面的推荐阅读。
    一定不要看别人代码。


参考#

https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
https://thesquareplanet.com/blog/students-guide-to-raft/
https://thesquareplanet.com/blog/raft-qa/
https://www.zhihu.com/question/29597104