Vakuum开发笔记01 开天辟地

1.缘起

先驱——COGS

早在2008年,我自学PHP后开发了COGS,并成功用于学校内部的OJ,ruvtex。也曾经对外开放过,但是由于学校网络不稳定,后来一直连不上了。我还把COGS推荐给了OOJ,只是直到现在都过于冷清。随着COGS功能不断完善,体系越来越庞大,Bug也非常多。限于当时水平,架构非常混乱,以至于到无法继续维护的地步,于是我遗憾的宣布了COGS的死亡。随后我又萌生了一个重新设计的念头,只是高二时期忙于NOI和文化课的学习,这一计划就一直被搁置到NOI2009结束。

知识准备

NOI2009结束以后,我终于有了时间,可以进行我新的OJ的开发了。之前的COGS不敢开源,因为写的太烂,开源的话肯定会黑得万劫不复。不过新的OJ不同,为了提高对自己要求,我决定对其开源。

我在暑假时期阅读了有关PHP高级开发、MVC架构、Javascript、CSS、Linux系统编程等大量书籍。受到经典的架构Zend Framework的启发,起初决定用它开发,但是学习不久就发现Zend Framework过于庞大,学习难度太大,并且难以找到比较好的资料。在Zend Framework的官方网站上阅读纯英文的文档实在太费力了,而且效果不好,始终没有弄明白其本质。开源界有一个箴言,叫做“不要重新发明轮子”。什么意思呢?就是说很多开发人员总是在做一些前人已经做过,而且做得很好的工作。比如libxml2已经是一个非常优秀的C语言XML库了,你再自己写一个XML解析库,就是在浪费时间,尽管也许你做的不错,但也最多算的上是“重新发明了轮子”。起初我非常笃信这句“箴言”,拼死也要学Zend Framework,做了大量的无用功。但后来细细一想,我们最初学算法、数据结构的时候,不是都是要自己实现每一个细节吗?尽管库函数可能已经做得很好了,如qsort,平衡树。而我现在也是MVC架构的初学者,在对其理解不是很深刻的情况下,直接学习某个库、某个架构,是非常不明智的行为。因此我决定要“发明轮子”——自己开发一个合适的架构,就叫——BYVoid Framework Library(BFL)。

恰好当时父亲的公司准备建一个产品介绍性网站,为节约成本就把开发的任务交给了我。我想这是一个难得的练手的机会,决定用我的BFL开发。果然在开发的时候遇到了前所未有的问题,但是都一个个迎刃而解了,而且获得了不少经验,其中包括Apache2 .htaccess的设置。两个星期以后,公司的网站制作完成,我的"MVC架构轻量级内容管理系统"也发布了。

2.Vakuum诞生之初与架构设计

命名

2009年9月,我正式开始开发新的OJ。在开发先我想先起个名字——就像“没有名字的船不会带来好运”。起初准备叫vacuum,英语意思是“真空”,算是Beyond the Void的衍生。但是我不幸地发现这个名字已经在sourceforge上被占用了,后来决定改名为vakuum,即vacuum的德语拼写方法。

基础结构

Vakuum作为一个OJ,我把它剖分为了三个部分,vakuum-web,vakuum-judge和judger。vakuum-web是一个网站,用于和用户交互,处理各种请求,它是一个PHP网站,应该能够跨平台vakuum-judge则是评测机终端,用于接收来自vakuum-web的评测任务,评测以后返回结果。而judger是评测的核心,其中包含编译器compiler、执行器executor和检查器checker三部分,分别用于编译用户程序、执行用户程序和比对用户输出与测试数据。简而言之,vakuum-web是一个用户与核心的中介,而vakuum-judge则是judger的通信接口。我的目标是网站和评测分离,并允许多评测机协同工作,因此vakuum-web和vakuum-judge之间少不了通信。

通信设计

参考很多成熟OJ的结构,发现几乎都是把vakuum-judge模块实现为一个常驻进程daemon,不断检查数据库是否有新的任务出现,对其评测,但后写回数据库。多数设计都没有分离vakuum-web和judger,即限定了只能有一个评测机,少数可以实现分离,但是实际上是多写了一个通信程序。我的想法是vakuum-judge也用PHP实现,这样就避免了自己写一个socket通信程序,而且不需要额外获得底层权限以常驻进程。这样只需要接收来自vakuum-web的HTTP请求,对其处理,然后将结果写回。可是这样的一个同步传输方案有很大的问题,即vakuum-web发送请求以后需要长时间被阻塞在通信上,等待vakuum-judge评测的结束。如此一来加大了传输的风险,二来加重vakuum-web的服务器负载,三来还无法让用户看到评测的进度。因此我想出了一个异步传输方案,即vakuum-web只发送请求,完毕后就断开连接,之后等待vakuum-judge的回传即可。然而PHP有一个特性,就是用户浏览器断开连接以后,PHP脚本也会停止执行,vakuum-web是在模拟用户浏览器发送请求,断开链接以后就相当于浏览器按下了“停止”键,vakuum-judge正在执行的脚本不管到了哪里都会停止。查资料以后才知道PHP有这样的一个函数,ignore_user_abort(),忽略用户中止,就是用来对付这种情况的。

队列处理

通信方式设计很成功了,还有一个问题就是如何处理评测队列。这是一个棘手的问题,要么为什么有那么多大型OJ经常卡在评测队列上,出现Waiting长龙呢?几乎所有的OJ都是写了一个常驻进程的daemon处理队列。我想为了实现多评测机调度,这个daemon必须是现在vakuum-web端,但是这样就违背了我当初vakuum-web能够“跨平台”的设想,而且vakuum-web必须获得系统底层权限——不仅维护不便,还有安全隐患。

绞尽脑汁以后,我想出了“链式反应”的想法,其实也是受了通信设计方式的启发。这种方法不需要获得底层权限,不用额外写一个daemon,能够跨平台,不用为安全性额外操心,还可以充分利用先前写好的代码,究竟是什么方法呢?其实就是用一个PHP进程来充当队列处理器,这个队列处理器不需要常驻内存,仅仅在用时才会出现。就是当用户提交一个评测任务以后,如果有空闲评测机的话,立即对任务进行处理,然后当vakuum-judge返回评测完毕的信号时,vakuum-web端再对评测任务队列进行检查,看看有没有新的任务出现,如果有的话,立刻执行即可。这种方法很简洁,而且支持多评测机协同工作,因为每次结果返回时都要检查队列,就好像链式反应,或者多米诺骨牌一样,只要处理了第一个,后面的就都会接着被处理。

这种队列处理方法的唯一缺陷在于依赖评测机的返回信号,如果评测机那边出了什么问题,或者因为通信原因vakuum-web没有正常接收到信号,队列就会被卡住。因此首先需要保证的是vakuum-judge需要绝对的安全和稳定,除非无可抗拒理由(如网线被拔),不会因为任何原因而不正常返回信号。此外还要增加人工干预手段(如强制继续处理队列),避免真的不可抗拒原因的到来。

——————————————————————————————————

先到此为止,欢迎继续关注Vakuum开发笔记,下次将要写的是评测机核心(judger)的设计。目前的开发进度停滞在后台管理各种繁杂的细枝末节的处理上,下图的是目前的后台管理界面截图。

点击看全图

相关日志