https://www.zhihu.com/question/390424213/answer/1179758442

今天是WeJudge3.0项目2018年立项开发以来,举办过的最大型比赛了!

本次网赛迎来了广东省各大高校的诸多高手同台竞技,充分展示了各位选手的实力。早上8时开始,不到10分钟,就有6题被拿了一血,不到3小时,排行榜首过15题了!(吐槽一下出题人,怎么出的这么简单;-)截止至晚上8时整,共1196名同学至少过题一道,有19道题被拿一血(总共20题,其中E题无人过题),排行榜上第一名是来自华南理工大学的郑炜城同学,恭喜!

凡事没有一帆风顺,作为WeBug系统(不是),此前花了大量时间在服务端优化上,结果比赛开始的时候,服务端看上去还挺顺的哦。于是顺手点了一下排行榜…嗯?我浏览器怎么卡爆了?经过一个多小时的排查,最终问题定位在了react-virtualized组件的CellMeasurerCache上,因为没有设置fixWidth属性,导致在渲染大量Cell的时候,每个Cell都去渲染并计算了Width,2300 * 20 == BOOM,紧急修复后恢复正常。

考虑到是2000多人的比赛,我们手上也就只有一台双路E5 2603 v2,学校借给我们一台单路E5-1620 v4作为主服务器,以及三台E5 2603 v2的单路服务器作为判题机服务器。根据百度统计的数据估算,短时间内大概在800 – 900 PV的时候我们服务器的承受量达到了峰值,接口访问出现也拥塞的情况。但总体来说,除了比赛结束那一瞬间可能有大批人访问排行榜,导致服务器压力过大,接口拥塞2-3分钟左右以外,整个比赛期间没有出现大面积崩溃、拥塞的情况,我悬着的一颗心终于放了下来,长舒了一口气。

再来看看咱们的各个数据库服务的工作情况。咱们的系统在设计上采用了MySQL作为主数据库、Redis和MongoDB作为副数据库和缓存服务,RabbitMQ作为队列数据库,虽然设计上支持分布式部署,奈何我们没有那么多服务器_(:з」∠)_于是主服务器基本上都是用来承担这个他们的工作了。

这次最佳凉快奖颁给了我们的MariaDB同学(也就是MySQL的好兄弟),平均不到20%的CPU占用率,您搁这儿树下泡茶喝咖啡呐?

劳动光荣奖,颁给Redis和MongoDB同学吧。账号数据、题目数据、排行榜的数据计算和缓存是Redis同学负责输出的,MongoDB同学则负责储存判题任务、判题结果和日志、题目配置信息等。

最惨996加班奖,就颁给我们最惨的RabbitMQ同学吧!从头到尾忙不停,内存都不够用了。判题队列、判题结果处理和查重队列,都是他在负责处理,可谓是“多人运动”…咳咳…鞠躬尽瘁!下次一定给你安排上16G内存,别再告警了求你了_(:з」∠)_

接下来是判题机。之前我们拿java压测了一波,python也压测了一波,也就是想看看这些高负载的评测对整个队列有啥影响。结果实际情况,确实没有压测时设想的那么恐怖。通过压力测试,也成功的怼出了判题机的一些问题,比如WA、PE没判对,以及测试文件太大的时候判题机出现访问文件失败的问题,这才使得我们在比赛前能够尽可能解决存在的问题。感觉下图判题机的CPU都没完全吃满,绰绰有余咯~(吃满你们就全TLE了哈哈)

再来看看比赛一个月来的访问量统计,PV达到了100W+!今日UV达到3000+!

Wow! Awesome! 这是OJ独享的moment…. 😉

可能对于那些商业OJ来说,这不算什么,但是对于我们来说,这是一次前所未有的经历。感谢主办方对我们的信任,也感谢北京师范大学珠海分校信息技术学院的领导、老师对我们整个系统的人力、物力、财力上的大力支持,感谢来自五湖四海的参赛者同学们对我们的理解和支持!

最后,来感谢一下为WeJudge作出贡献的大家!

从2015年立项以来,WeJudge前前后后更新了三个大版本。当初做这个是为了给同学们提供一个教学用的评测平台,所以,在肖红玉老师(咱们团队的指导老师)的帮助下,从2015年9月就开始使用到她的C语言课程中,逐步推广到整个学院在使用,也因此积累下来很多质量较高的题目,因此,也很感谢肖老师和信院的各位老师、我的同学 Wolf Zheng (@草原狼)、 @QuanQqqqq 和Tosh Qiu等大佬,以及北师珠ACM协协会各届的大佬,为OJ提供了许多优秀的题目资源和测试数据。

然后是咱们团队~在初期我单枪匹马独干了2年多的时间里,系统存在一些自身的不足和偏见,3.0版本以前的WeJudge在现在看来是一个大作业水平的作品。在经历了一个很棒的科技公司实习后(很感谢那位老板给我的实习机会~),让我清楚的意识到,如果我想把它做好,就需要重头开始。在即将毕业的那一年,我很幸运遇到了两位大佬121和ztr( @三好少年R某 ),在我们共同的努力下,把3.0系统做出来了。我负责架构多一些,业务代码大多数是他们在整,大家都是在同一个起跑线上成长,也见证了整个系统从0到1的过程。很感谢你们两年多来为WeJudge的付出!无论WeJudge的未来如何,我相信它带给你们的都是技术上成长和收获!

再然后,是关于这次比赛的。比赛筹备大概是3月份开始的,一开始接到的是说比赛我们来搞,报名也我们来搞,不仅要支付,还要小程序(??)。于是乎我们在两个星期左右的时间里,内把支付接好了,并把小程序搞了出来。期间感谢ztr大佬搭建微信小程序的项目(我一窍不通哈哈哈),以及我们可爱的xj小姐姐在开发上的帮助~考虑到比赛需要消耗较大的服务器资源,申请到的备用服务器需要做相应的配置才有用。由于疫情期间,学校没开学,我本人也毕业两年了不在学校,所以只好请实验室管理员郑义老师帮忙新服务器的安装操作系统工作,以及原有主机的内存扩容、故障硬盘更换等。郑老师辛苦啦,周末都还在帮我们装系统啥的,我有点儿过意不去,总之非常感谢啦!

最后最后,当然要感谢我们的大老板小红鱼老师了!肖老师从15年立项到现在一直在支持这个项目,幕后的运营、推广都是她在负责搞。可以说,如果没有她帮忙,OJ也许就真是一个大作业玩具了,基本上是没人会用的。这次比赛的顺利进行,相信是对她辛劳和努力的一个最好的回礼!

老板的鸡腿已加,请查收

大家见证了WeJudge的成长,WeJudge也见证了你们的成就和荣耀!

衷心感谢大家,我们明年再见!哦不,别急,这才网络资格赛呢,还有现场赛呢!到时会有更好玩的功能出现在现场哦,也许还会在B站有直播?

不骄不躁,脚踏实地,继续前行!

一些私货

WeJudge官方网站:https://oj.bnuz.edu.cn
判题机核心模块开源:https://github.com/LanceLRQ/deer-executor
WeJudge团队:https://github.com/wejudge


不过是去便利店买了个泡面,居然穿越到了异世界。一次意外的去世,发现自己拥有了死亡后读档的技能…原来,世界线分支交错复杂,不同的世界线里发生着不同的故事…

0x00 进程

进程(Process)是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础。在早期面向进程设计的计算机结构中,进程是程序的基本执行实体;在当代面向线程设计的计算机结构中,进程是线程的容器。程序是指令、数据及其组织形式的描述,进程是程序的实体。

来自百度百科词条

进程就像是一个个世界线的分支,各自发生着不同的故事,但又是相互关联的。

我们运行的每一个程序,系统都会为它创建一个进程,然后分配内存和堆栈,装入程序的指令,并执行它们。如果我们要在自己的程序里调用其他的程序,就需要向系统申请创建子进程,重复执行上述的初始化操作。那么进程应该如何创建呢?

0x01 创建进程

在Linux的世界里,我们可以利用fork()函数或者vfork()函数来创建新的子进程。代码如下所示:

pid_t child = fork();
if (child == 0) {
    // 子进程
} else {
    // 父进程继续执行
}

有趣的事情来了,父子进程居然通过一个if条件区分了!因为子进程拥有和父进程的一样的数据空间、堆和栈等,并以副本的形式存在。代码从fork()开始,被一分为二,分别在不同的进程继续执行。其中,fork()的返回值child变量,在子进程中获取到的是0,而在父进程获取到的是子进程PID。

与fork()不同的是,vfork()创建的子进程会和父进程共享数据段,另外,vfork()会保证在_exit()和exec()类函数执行前,子进程先运行。

0x02 进程调度

为了更好的理解进程的工作原理,先来简单的了解一下系统调度进程的方式。

现代操作系统可以同时运行多个程序,但从操作系统的视角来看,CPU是个菜鸡,一次只能执行一个程序(如单核CPU)。那如果要同时运行程序怎么办?没错,换多核处理器!EPYC 7742了解一下?64核128线程…

你的钱包还好吗?

显然,简单的堆硬件是不合理的。操作系统需要解决的问题便是,如何让多个程序同时有序的执行,但又要让用户觉得他们是同时执行。于是操作系统引入了一个调度概念:

操作系统将进程的分成三种状态:

  • 就绪 :程序等待系统唤醒 。(你在这待着别动,我去给你买橘子。)
  • 执行:程序正常执行。(动,自己动,使劲儿动!)
  • 阻塞:程序由于自身I/O需要,将控制权交出给I/O设备,等待返回。

就绪状态时,进程都是不会占用CPU的,处于休眠状态,等待操作系统唤醒。操作系统会对时间进行划分成一个个区间,称作时间片。当某个进程获得时间片后,操作系统就会唤醒它,进入执行状态;时间片用完了,系统就会令其休眠,进入就绪状态;如此往复,不同的进程均在某段时间获取了时间片并执行,于是均达到了运行的目的。由于这个过程非常的快,用户直观上几乎无法察觉它的存在,即所有的进程的“同时”运行的。

0x03 输入输出

当你在Terminal使用键盘输入文字的时候,你的输入将被送入程序的基本输入流(STDIN)缓冲区,再经由程序处理,并将结果输出到基本输出流(STDOUT)。操作系统默认为你的程序分配了三个标准的流:STDIN、STDOUT和STDERR,它们的文件描述符(File Descriptor)是0、1和2。

判题机内核要想接管程序的输入输出,就需要将这几个默认的流重定向。Linux系统为我们提供了dup2函数:

#include <unistd.h>

int dup2(int oldfd, int newfd);

通过参数名,很容易知道这个函数传入两个文件描述符,oldfd将会替换newfd。因此,判题机内核要做的工作就是打开一个测试数据的输入文件,和一个临时文件,并将它们分别重定向到子进程的STDIN和STDOUT中。

int fd_in = open("./testcase.in", O_RDONLY);
int fd_out = open("/tmp/user.out", O_RDWR);

dup2(fd_in, STDIN_FILENO);    // STDIN_FILENO  == 2
dup2(fd_out, STDOUT_FILENO);  // STDOUT_FILENO == 1

此时,程序的输入将从testcase.in文件读入,输出内容将可以在user.out文件获取。你还可以将STDERR_FILENO重定向到一个文件,以便接收程序在STDERR流输出的内容。注意,由于open方法是一个非常底层的文件操作,user.out文件在反复写入的时候,只会从头覆盖特定长度的内容,而不是清空整个文件后再写入。例如程序A输出了10个字节,程序B输出了4个字节,覆盖操作下,程序B运行结束后,user.out文件依然是10个字节,只是前4个字节被覆盖。因此,在每次执行判题前,需要先将user.out文件删除,确保输出结果是正常的。

0x04 等待进程退出

判题内核的一个关键目标就是,必须能够监控被测程序的开始和结束。

通过第一节我们了解到,父进程可以创建子进程并在子进程运行外部程序。但不知道你有没有注意到,如果我们要实现一个判题内核,在启动新的进程后,父进程就必须停下来,等待子进程结束后,才能继续工作,收集被测程序的运行信息等。这时候就要用到wait()系列的函数了。

wait函数有很多个兄弟姐妹,常用的如wait()、waitpid()、wait3()和wait4()等。它们共同的作用就是阻塞父进程,等待子进程的结束。

wait()函数会阻塞原程序并等待任意一个子进程退出,而waitpid()可以指定等待的子进程PID。不过,这两个我们都不用,因为他们都不能取到程序的运行信息。

pid_t wait4(pid_t pid, int *status, int options, struct rusage *rusage);

wait4解决了这个问题,它为我们带来了四个参数:

  • pid_t pid:等待的进程
  • int *status:接收进程退出的状态信息
  • int options:设置等待方式
    • WUNTRACED:除了返回终止子进程的信息外,还返回因信号而停止的子进程信息。
    • WCONTINUED:返回那些因收到SIGCONT信号而恢复执行的已停止子进程的状态信息。
    • WNOHANG:如果参数pid所指定的子进程并未发生状态变化,则立即返回不会阻塞。这种情况下waitpid返回0
  • struct rusage *rusage:获取运行的资源信息。

要获取进程的运行资源信息,我们可以rusage返回的数据来获取。要获取进程的退出状态,可以用WIFEXITED(status)和WIFSIGNALED(status)来判断,前者判定进程是正常退出的,可以使用WEXITSTATUS(status)获取退出代码[1],后者判定进程是以信号方式终止[2],可以通过WTERMSIG(status)获取退出时的信号。通过对这些数据的分析,我们可以得知进程是以什么方式退出的,从而作出正确的判定。这些会在后续的文章中进行介绍。

0x05 小结

本文从进程的概念着手,对判题机核心中最重要的功能的实现进行简述,为后续开发完整的判题机核心奠定理论基础。下一节,我会就判题机如何判断TLE、MLE和OLE等判定进行分析。

一些备注

[1] 在你学C语言的课上,老师肯定建议你main函数结尾加上return 0; 当你产生了很多的问号,老师会跟你说不用管这个0是什么意思,写就是了。这个main函数的返回值0就是退出代码,表示正常退出,如果是负数,则说明程序异常退出了。显然,你可以自定义这个退出代码。
[2] Linux系统中通过信号(signal)机制来传递消息,在软件层模拟了一个中断(软中断)。当进程收到信号的时候,默认是会终止运行。你可以在程序中编写相关函数来捕获信号,并选择终止程序或者忽略信号。

文章引用

https://www.dazhuanlan.com/2019/12/26/5e0426c13920a
https://man7.org/linux/man-pages/man2/dup2.2.html

姐姐大人,姐姐大人,你用过在线代码评测工具吗?
蕾姆,蕾姆,用过呢,真好用,给我也整一个……

0x00 我为什么要开发OJ?

在线判题系统(Online Judge)是一种在编程竞赛中用来测试参赛程序的在线系统,也可以用于平时练习。

相信参加过ACM-ICPC、IO的童鞋们都对它不陌生吧,那个偶尔让你产生许许多多的小问号,想AC却又不停的WA,做题做到停不下来的系统。

五年前,作为前ACM校队队员,在深感自己太菜的技术后,一次突发奇想和老师讨论起了怎么把OJ用到教学中去,让学弟学妹们也被折腾一下(这句划掉),从此给自己挖了一个巨大的坑。

0x01 OJ是怎么工作的?

小学二年级的知识告诉我们,你输入的代码,会被OJ的判题机编译、运行。判题机将通过控制程序的标准输入流,模拟你的输入操作。当程序运行结束后,从标准输出流获取到的数据,即是你程序的答案,然后将它与标准答案进行比较。

当然,如果程序在一开始就错了,或者在运行过程中出现了错误,又或者超出了题目设定的资源限制,那么你也会得到相对于的错误提示,供你排查问题。

通常意义上,OJ的判断非常严格,错一个字都是错,少个空格也是错。所以很多时候,折腾了半天,结果跑完第一组数据过了,第二组数据又超时…

0x02 这就是我要整学弟学妹的理由?

没错,人要经历挫折,有挫折才会有成长,才会明白做啥都好不要做程序员啊

这种基于黑盒测试的代码评测模式在ACM-ICPC竞赛中最为常见,具有如下优点:

  1. 判题程序开发难度较低。
  2. 判题程序主要实现进程监控和数据直接比对,运行效率高,占用资源低。
  3. 测试数据易于构造和编辑,可以通过标程(相当于参考答案)生成。
  4. 兼容多语言多平台,扩展性强。

那么,具有以上优点的系统,又是为何被老师和同学边用边骂骂咧咧的呢?究竟是道德的沦丧,还是人性的弱点?不,是系统的缺点:

  1. 测试数据均为静态数据,仅使用“运行结果”来判定代码正误。判题太过于严格了,动不动就WA,同学们的心态都炸了。求A+B问题 数据输入:1 1 答案输出:2 同学:我输出文字『1+1=2』,为什么判我错? 判题机:你哪那么多废话呢,输出『2』不就好了?
  2. 无法进行代码分支预测,无法判定代码是否符合题目要求,无法检测暴力过题的情况。
  3. 系统设计初衷是面对编程初学者用户练习,黑盒测试不能直观反映代码存在一些问题,如:数组或变量未初始化、循环不能跳出和条件语句结构臃肿等等。

上述问题都解决了吗?好吧我承认,并不好解决,于是有了很多很多折中的方案。但这些并不是本系列文章想要讨论的事儿,如果上述问题在技术上有好的建议,非常欢迎你和我一起探讨。

0x03 问题都没解决,写啥系统呀?

问题来了,先有鸡还是先有蛋?系统都没有,解决啥问题?咱也不能老是下半年中美合拍呀就解决问题了呀,啥事都得自己搞搞才能进步嘛

万事开头难,但也最怕是遇到问题不百度直接自己闷声捣鼓的,对,说的就是不才的本人了。我才不会告诉你我当年的OJ整了好几次大版本,每次都是重新来过的(也就是把原来的技术方案否了)。

通过不断的积累,不断的试错,才有了今天的WeJudge系统的技术体系。也许在众多大公司开发的OJ相比起来,它像是一个初来乍到的新同学。我希望通过这篇文章,与你分享关于她的故事。

0x04 关于WeJudge

当年1个月时间开发出来的0.3,到半年后的1.0,再过一年的2.0,再到后面将近三年时间3.0正式发布。我从一个人孤军奋战到2.0,到现在3.0是我带两个学弟一起搞,前前后后经历了太多了。虽然她一分钱都没赚,靠的是学校提供的服务器和网络,基本上用爱发电,但我相信开发她的过程本身就是一种成长。

如果未来有一天,我们确实运营不起她了,也许会在github上看到她完整的样子,在此之前,我们依然在努力。

我在github上开源了判题机相关代码,未来也将会分享更多的东西。

判题机:https://github.com/LanceLRQ/deer-executor (参考dojiong/Lo-runner)

1.0版源程序:https://github.com/LanceLRQ/wejudge

3.0 网站:https://oj.bnuz.edu.cn ,未来计划重新用回 wejudge.net

0x05 未来我会谈谈什么呢?

很久很久以前就一直在想把自己的技术经验、经历写出来分享,也好回顾一下这些年走过的路。因为一些生活、找工作失利等诸多的原因,可能自己在心态有些不太好,感觉技术上停滞不前了。所以打算写一些文章,努力让自己回忆起那些年努力去为梦想奋斗的日子吧。

我将会围绕以判题机为中心,一步步阐述规划、设计和开发一套完整的在线判题系统所涉及到的问题,以及我的想法、看法、解法。新人一个,有说的不足的地方还请大神们多多指教。毕业快两年了,业余时间一直在参与这个项目开发。

如果你有兴趣阅读这个系列的文章,你需要有一些数据结构、算法和操作系统的基础,并了解C语言、Go语言或风格和C语言类似的语言的语法格式。文章主要是阐述思路,不会实际的业务代码,并且我也会尽量把原理说的简单一些。难免会有不专业的词汇或比喻,还请见谅。

0x06 实战回顾

2020年04月,顺利举办“2020年粤澳计算机程序设计大赛网络赛”。回顾参考:

https://www.zhihu.com/question/390424213/answer/1179758442