SS's Trace

Sirius's Blog

在线评测系统(OJ)架构优化案例分析与经验心得

序言

大学中计算机专业的学习、高中生和大学生程序设计竞赛都经常要用到在线评测系统,我们通常称之为 OJ。在2014年,当时网络上比较有名的 OJ 有 CodeVS、Vijos等。6 年过去,现在的 OJ 系统变得更加开放和进步。感谢开源项目 QingdaoU/OnlineJudge ,和参与NUISTOJv4开发的学长学姐。

以此文总结在我参与学校 OJ 开发中,升级架构的心得。有点遗憾的是,我现在的项目当前尚未做好开源准备。开源后还请大家多多批评指正。

OJ 的核心要求主要有以下几点:

  • 实现对用户提交代码的编译运行,并做好安全防护
  • 实现易用方便的用户界面

非必须的需求:

  • 便利的题目导入导出功能
  • 竞赛系统
  • 课程系统
  • 小组
  • 多评测机
  • SPJ / 交互评测
  • ……

部分 OJ 的架构设计特点

撰文时,我还没有对部分项目完成代码层面的理解,所以仅简要概括一下。

QingdaoU/OnlineJudge

【待完善】

基于 Vue, Django and Docker 开发。

很稳定的开源 OJ,使用 Python 开发。

部署可以使用 docker,简化(?)了部署过程。– 因为文档问题,有可能出现预料外的部署问题

支持多评测机,题目导入与导出。

仅支持 C/C++、Python、Java

现在已经基本不再更新。

zhblue/hustoj

【待完善】

基于 PHP/C++/MySQL/Linux 开发。

syzoj/syzoj

【待完善】

使用 JavaScript 开发。

TSOJ (NuistOJv4)

闭源项目 已终止维护更新

因为在学校必修课课程中使用,且本身并不完善,此项目并没有开源。

基于 tornado/C/Mysql/Linux 开发。

内核部分借鉴了青岛大学 OJ。

内核部分(评测机)完全使用 C 开发。

Leverage Online Judge (NuistOJv5)

闭源项目

基于 Vue/Nest/C/C++/Rust/Mysql 开发。

借鉴了 NuistOJv4中的很多设计。

NuistOJv4 到 NuistOJv5 的架构升级

v4

《在线评测系统(OJ)架构优化案例分析与经验心得》

 

评测机(Judger)使用C语言实现,包含两个部分(Executer 和 Updater)。Web端和评测内核之间使用 Redis 来进行通讯。最终的评测结果会放在 Redis 和 MySQL 里,供 Web 端使用。

所有组成元素均为守护进程。

蓝色标记为 Push,橙色标记为 Pull。意为消息传送行为的发起方是发送方还是接收方。

  1. PUSH WEB 将 源码、来源(练习/课程/竞赛)、题号、用户等 信息保存至 Redis,并将评测ID push 至 Redis 列表A。
  2. PULL Executer 阻塞监听列表 A,获取评测信息
  3. PUSH Executer 保存用户代码
  4. PULL Executer 打开保存在本地硬盘中的测试文件,并重定向至用户程序
  5. PULL Executer 在运行后更新redis中的数据(时间、内存等),并将评测ID push 至 Redis 列表B。
  6. PUSH Updater 阻塞监听列表 B……
  7. PULL ……并将数据插入至 MySQL

这是南信大第一版“比较好用”的 OJ。它的设计在当时已经是巨大进步。Redis 阻塞监听取代了死循环 MySQL 轮询,C 语言写的内核效率上也满足要求。但是因为过于抠性能,也造成了很多难以修复的问题。这导致后来最终决定推翻重写。

问题有:

  1. 可持久化保存的数据的只在中进行保存,这导致前面任何一个环节出错都可能导致数据丢失。并且Web、Updater 均要建立与数据库的连接(池),均要处理数据库逻辑,完全耦合了起来。
  2. 过度依赖 Redis 中的数据且没有 tts,MySQL 与 Redis 可能出现不同步的情况。
  3. 因为能力有限,使用 C/C++ 难以处理更复杂的逻辑

评测机(Judger)部分有使用其他语言重写的版本,改善了部分问题,但没有根本解决问题,不再展开。

v5 初代

《在线评测系统(OJ)架构优化案例分析与经验心得》

这是 v5 早期版本的架构。Web 担任了原先 Updater 的任务,数据逻辑和评测机解耦,架构设计更加合理。如果不新增语言(仅支持C/C++、Java、Python)的话,实际上是可以满足需求的。

评测机 Judger 现在是一个确实存在的实体,用 TypeScript 写成,ts-node 运行,是对运行内核的一层包装。内核处理更少的逻辑,专注于安全和隔离;Judger 负责处理其余的逻辑,如数据的传输、文件的保存等。

在当前架构中,文件仍然是由内核 Core 打开。

v5 中期

这是一个比较失败的改动,在后期架构中也再也没有出现。当时测试数据一共也就 200MB,所以想到把数据直接放在 Redis 中,Judger 取出来直接 pipe 到 core 的 stdin,stdout 通过内存获得,全程不走硬盘。但是这仅在评测机性能足够好且单个和全部评测文件大小不大时才适用,规模一大直接扑街。

v5 当前

《在线评测系统(OJ)架构优化案例分析与经验心得》

此架构应对的需求为:实现更优的安全隔离和更多的编程语言支持

这时上一个架构就有局限性了:由于能力和学习资料限制,用 C 编写的内核很难做到非常完善的隔离,即使做出来,也会使内核变得极为臃肿。经过选择,我最终使用了 Sandbox + Core 双层结构作为评测内核。外层 Sandbox 使用 google/nsjail做硬限制,如运行时间和空间,保证沙盒内一定不会影响到沙盒外,且规定时间和内存耗尽后可以退出。内层 Core 则专注于资源计算和更精细的权限控制,如设置用户组、Seccomp规则等。

这样一来,引出一个问题:Core 在 Sandbox 内运行,则 Core 必须使用尽量少的外部依赖。外部依赖包括文件、系统权限。

所以此版本,文件从评测机 Judger 打开,而不是 Core 或 Sandbox。

v5 未来

《在线评测系统(OJ)架构优化案例分析与经验心得》

此架构尚未实现,但可行性不存在问题,是大量题目和大量提交的低成本解决方案

改动主要有:

  1. Redis 不再负责信息传送,仅负责 Web 端的缓存且必定为可持久化存储的局部。数据传输使用 WebSocket。
  2. 评测数据保存在OSS,评测机仅缓存必要的评测文件
  3. 文件比对使用单独的程序,使用 Rust 编写,用户程序的 stdout 直接 pipe 到其 stdin 上。
  4. 由于不再使用 Redis,失去了自然的负载均衡,所以 Web 端需要手动实现 LBS。
  5. 由第四条,因为反正要手动调度,所以还可以加入支持仅评测部分语言的评测机。

因为大硬盘存储的服务器不仅少而且贵,所以当评测文件特别多的时候(>40GB),使用OSS更为合算。每个评测机仅需要保存一部分测试数据即可(s3fs自带lru缓存)。

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

点赞
  1. 大叉烧说道:

    没搞明白为啥judger和web之前的通信用redis。。。。为啥不直接用socket

    1. Symbiotic Star说道:

      版本初期沿用了上版本的Redis设计,用在此处可以解决问题,写起来也比较简单,不用考虑负载均衡的问题。
      后面是准备使用WebSocket的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注