大作业二：在线评测系统（2021-2022 学年夏季学期）

作业简介

OJ（Online Judge，在线评测系统）是在课程教学、算法竞赛等场合中用于测试程序正确性的线上系统。用户可以通过友好的界面提交自己的源代码，评测系统在指定的环境中编译代码，使用特定的输入运行程序，并将输出与答案进行比对。

随着需求的不断演化，各类开源的 OJ 系统不断涌现（如 Vijos、UOJ、NOJ、HUSTOJ、Hydro、DMOJ、CMS）。它们各具特色，均有广泛的用户群。本课程使用的 TUOJ 也在校内的多门课程中获得了广泛应用。

作业要求

在本课程中，你需要使用 Rust 语言，基于给出的项目模板实现一个 OJ 系统。如果没有特殊说明，它应该在各个平台下都能正常工作。

自动化测试

作业的基础要求部分将使用 Rust 的测试框架进行自动化集成测试。运行测试的方式详见项目模板。每个测试的名称类似 test_01_15_pts_basic_judging，名称中即标记了对应的分数。

关于测试的注意事项

提高要求的测试结果不影响 CI 结果，即只要通过所有基本要求的测试点，CI 结果就是成功。
通过某个测试点只代表在你的程序在给定输入下的表现是符合预期的，并不代表一定能获得该点的分数。
每个请求均有响应时间限制，超时将会直接认为失败。
你的程序在 debug 与 release 模式下的测试结果通常应该相同。如果不同，则取较差的结果。

API 定义

见 API 定义页面。

请仔细阅读定义的内容。并非所有字段都是必须的，尚未实现的功能涉及的字段都可以忽略，测试时也不会关注。

其他配置

详细描述见配置页面。

语言支持、问题配置通过本地 JSON 配置文件给出。你的 OJ 应该接受以下的命令行参数：

-c/--config config.json：读取配置文档中描述的配置。如果没有指定配置文件路径，则报错退出。
-f/--flush-data：启动时清除所有持久化的状态（如果实现了持久化）

异常处理

除配置文件格式或内容不正确（如无法绑定到要求的地址或端口）外，你的程序不应该因为其他任何问题异常退出。任何响应 API 请求时产生的问题都应该以 API 错误的形式返回给调用者。API 定义文档中已经预定义了一些错误和对应的错误代码、HTTP 状态码，请尽量使用；你也可以增加自己的错误代码，但请注意语义清晰。

基础要求（40’）

此部分功能按点给分，并且必须按顺序实现（也就是说，某个功能点得分的必要条件是它与之前的所有功能均正确实现）。除特殊说明外，最终结果以程序在助教环境中测试的结果为准。

（15’）基础评测：运行 Web 服务器，实现 POST /jobs API。
- 从命令行参数获得配置文件路径，解析配置文件内容
- 接受到 POST /jobs 请求时，从请求中获取 source_code 字段，根据配置文件中 Rust 语言的配置，使用 rustc 命令编译为可执行文件；运行 rustc 可以用 std::process::Command。
- 根据题目 ID 找到题目的各个数据点，对题目的各个数据点进行评测，衡量测量程序运行的真实时间（wall time），在超过设定的时间限制一段时间（如 500ms）后强制终止程序；测量运行时间可以用 std::time::Instant
- 比对程序输出的结果与答案，需要支持两种模式：standard（忽略文末空行和行末空格）和 strict（严格比较）
- 实现阻塞评测，在评测后才返回响应，因此只会出现 Finished 状态，数据点结果仅会出现 Waiting（前序数据点尚未评测完成或编译错误）、Accepted（答案正确）、Wrong Answer（答案错误）、 Time Limit Exceeded（超时）和 Runtime Error（运行时错误，程序异常退出）
- 不需要保存评测历史，所有评测 ID 都可返回 0
（5‘）多语言支持：支持配置文件中提供的其他语言（保证使用的编译命令存在于系统中）
- 请保证你的系统内安装了 gcc 和 g++
- 如果你在 Windows 中开发（但没有使用 WSL），可以本地修改测例的配置为其他编译器（如 MSVC，MinGW 等），但不要提交到 Tsinghua GitLab 代码仓库上
（10’）评测列表：保存启动以来的评测列表（例如使用全局变量，Arc<Mutex<Vec<Job>>>），实现下列 /jobs 开头的 API，实现对任务的搜索，详情查询和重新评测。
- GET /jobs：筛选并获取评测任务列表；
- GET /jobs/{jobId}：获取指定评测任务信息；
- PUT /jobs/{jobId}：重新评测指定评测任务。
（5‘）用户支持：实现所有 /users 开头的 API，支持简单的用户功能。此时创建任务时应该进一步检查用户 ID，并且支持通过 ID 和名称搜索相应用户的评测任务。
- GET /users：获取用户列表；
- POST /users：新建或更新用户；
- 系统启动时自动创建用户：ID 为 0，用户名为 root。
（5’）排行榜支持：
- 实现简单的排行榜：按用户所有问题的得分之和进行排序（排序方式详见参数）；
- 暂不考虑比赛，传入的比赛 id 恒为 0，即只要实现 GET /contests/0/ranklist 获取全局排行榜即可。此时用户的分数按题目 ID 从小到大顺序对应。

提高要求（40’）

此部分功能没有具体的要求，助教将视完成情况酌情给分。其中有些项目存在依赖关系，无法单独完成。所有项目得到的分数综合不超过 40 分。标记有“⚠️”的功能是助教认为复杂度较高的功能，请谨慎上手。

实现提高要求部分不应该影响已有的自动化测试。如要实现任何未提及的功能，请先与助教确认可行性，并评估应得分数，如未经确认直接实现则不得分。

OJ 前端用户管理评测技术评测方式

只可选择一个方向完成，可以选择子项目完成。

CLI 前端（10‘）：使用 Rust 编写 CLI 客户端，实现以下功能：
- （3’）提交单个程序（提交的程序支持使用不同编程语言编写，如 Rust，C++），并等待结果
- （4’）根据一定的配置批量提交不同用户的程序，并以机器可读格式（如 JSON）输出评测结果
- （3’）查询排行榜并以表格形式渲染到终端
Web 前端（10‘）：不要求使用 Rust，建议使用现代前端框架（如 React、Vue、Angular 等），实现以下功能（效果参考 TUOJ）：
- （5’）提交单个程序，并渲染评测状态和每个数据点结果
- （5’）渲染比赛排行榜

此部分内容需要在报告中详细描述。

（10’）实现用户的注册、登录和鉴权，需要向 OJ 系统添加新的 API，并且由后端实现用户的权限管理，所有 API 均需进行鉴权（如使用 Bearer token），并合理设计权限机制；为了不影响自动测试，默认情况下不应当拒绝自动测试发送的请求，可以使用一个命令行参数或在配置文件中加入自定义的配置来打开 API 鉴权
（10’）多角色支持（依赖上一条）：支持不同的用户角色，如管理员、出题人、普通用户等，不同角色拥有不同的 API 权限

（10’）多比赛支持
- 实现 /contests 开头的其余 API，支持新建或更新比赛，获取比赛信息和获取比赛排行榜。
- 比赛 ID 为 0 时特殊处理，认为比赛 0 包括所有用户和所有题目，没有开始和结束时间，没有提交次数限制，比赛 0 的配置不可修改
- 比赛 ID 不为 0 时为正常的比赛，需要通过 API 新建或更新
（10’）持久化存储：将所有的评测任务、用户信息和比赛信息实时保存到文件系统，启动时读取（以下两种方式二选一）
- （5’）简单文件持久化：将所有状态保存到 JSON 等结构化文件中，启动时读取，并定时/实时保存
- （10’）数据库持久化存储：选择一个数据库后端（如 SQLite），设计合理的表结构
（10’）非阻塞评测，以下两种方式二选一
- （5‘）评测依旧在单个请求中处理，但不阻塞其他的 HTTP 请求处理。此功能可使用 Web 框架提供的机制将评测工作移动到其他线程执行，如 actix_web::web::block，但依旧在请求处理中等待其返回的 future。
- （10‘）将评测与 API 请求处理分离，即创建任务的请求应该立刻返回（返回 Queueing 状态），使用额外的线程运行评测；评测开始后更新状态为 Running（可选实时更新数据点结果）；评测结束后更新状态为 Finished，并更新相应的完整结果。你应该启动一个 async 函数，然后立即返回，在 async 函数中继续完成评测，完成评测后更新状态；如果依旧使用框架提供的机制，则需要小心处理生命周期问题。
（10’）独立评测进程：此要求依赖于非阻塞评测。将评测进程与 OJ 服务端分离（但可以共享题目配置文件）。服务端收到请求时，将评测任务推入队列。独立的评测进程轮询队列，并运行评测、更新结果。不要求评测进程和服务端是分布式运行的，但建议使用消息队列（如 RabbitMQ）来实现解耦合，以自动获得错误处理、负载均衡等高级功能。此外，还需要实现 DELETE /jobs/{job_id} API，用于取消某个正在排队的评测任务。
（10‘）资源限制进阶：此功能要求在 Linux 上实现，并建议在独立评测进程的基础上完成。具体要求如下：
- （3’）测量内存占用：使用 wait4 等方式测量程序在每个数据点上的最大内存占用（指工作集大小）并报告
- （7’）初步限制内存占用：使用 ulimit 等方式限制程序在每个数据点上的内存占用，并在程序因此退出时报告 Memory Limit Exceeded
（20’ ⚠️）评测安全性（包含资源限制进阶的内容，不重复得分）：此功能要求在 Linux 上实现，并建议在独立评测进程的基础上完成。考虑到用户程序可能执行危险操作，真实的 OJ 必须将用户程序在与真实系统隔离的沙盒（sandbox）环境中运行，并阻止其除 IO 读写外的大部分行为（如访问网络）。你需要自行调研并设计一定的安全机制，做到：
- 将用户程序隔离在单独的环境中
- 限制用户程序的资源占用：包括只允许使用单个 CPU 核心、指定的内存、指定的运行时间
- 限制程序的行为：尤其是不能读写除输入和输出外的任何文件、不能连接外部网络、不能随意使用系统调用

你可以用多种技术（以及它们的组合）来实现这些功能，例如：

容器化：Docker、LXC
资源限制：chroot、ulimit、cgroups
系统调用限制：libseccomp

如果实现了此要求，则需要在实验报告中详细说明你的设计。助教将会构造一系列恶意代码对你的设计进行充分的测试，不要求完全通过这些测试。

（5’）打包测试：支持将测试点分为若干个组（每一组称为一个子任务，子任务的集合构成对测试点集合的一个划分），每一组必须所有测试点均正确才能获得所有分数，否则该组整体不得分（此时某个评测任务的 score 可能不再等于所有测试点得分之和）。一旦某个点错误，则该组剩余的测试点不再进行评测，结果标记为 Skipped。此选项在题目配置的 misc 字段中增加以下配置：

"misc": {
  "packing": [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9, 10]
  ]
}

（10’）Special Judge：支持通过外部程序将用户程序输出与标准答案进行对比，并给出得分。此选项即对应题目配置的 type 为 spj，并在 misc 字段中增加以下配置：

"misc": {
  "special_judge": ["./judge.py", "%OUTPUT%", "%ANSWER%"]
}

此选项指定了 judger 的调用方式，其中的 %OUTPUT% 和 %ANSWER% 需要替换为真实的文件名。SPJ 程序输出两行：第一行表示评测结果（与 API 中 result 定义一致），仅有 Accepted 能得到分数；第二行表示要告知用户的其他信息，需要在评测任务中每个数据点的 info 字段中返回。如果 SPJ 程序异常退出，或者输出信息不符合上面的要求，则数据点的结果为 SPJ Error。

（10’）竞争得分：在一类任务中，每个用户的得分受到其他用户的提交影响（考虑需要评价程序的性能，每个用户提交的得分为 性能总分 * 个人性能 / 最高性能）。此选项即对应题目的 type 为 dynamic_ranking，并在 misc 字段中增加以下配置：

"misc": {
  "dynamic_ranking_ratio": 0.5
}

此选项指定了竞争得分的比例，即 0.5 表示用户每个测试点得分有 50% 为竞争得分，剩余为正确性得分。只有用户获得了所有测试点的正确性分数后，才可以计算并获得竞争得分。每个测试点的竞争得分为 总分 * 得分比例 * 最短时间 / 有效时间。最短时间是在同一比赛内所有用户能够计算竞争得分的有效提交的该测试点的运行时间集合中，取最小的一个。输出和答案的比较方式与 standard 相同。计算排行榜时，如果用户有正确的提交，则忽略 scoring_rule，按照用户最后一次正确的提交算分。在响应中出现评测任务信息的 API 中，不计算竞争得分，仅显示正确性分数（即最高为 总分 * (1 - 竞争得分比例)）。

非功能要求（20’）

（10'）代码规范
- （3'）正确使用 Git 管理代码、使用 Cargo 管理项目
- （7'）代码风格良好、模块化合理、有清晰的注释
（10'）提交 PDF 格式的大作业报告到网络学堂，包含：
- 简单的程序结构和说明（不必过长，尤其不要逐句解释代码）
- OJ 主要功能说明和截图（不必面面俱到）
- 提高要求的实现方式（如有）
- 完成此作业感想（可选）

提示

文件操作

Rust 标准库中提供了很多文件操作，大多都在 std::fs 模块下，如

std::fs::File::create：以写模式打开或新建一个文件
std::fs::File::open：以读模式打开一个文件
std::fs::write：跳过打开文件的步骤，直接向文件写入数据
std::fs::read：跳过打开文件的步骤，直接从文件读取数据
std::fs::read_to_string：跳过打开文件的步骤，直接从文件读取数据为 String
std::fs::create_dir 和 std::fs::create_dir_all：创建文件夹
std::fs::remove_file：删除文件
std::fs::remove_dir_all：删除目录以及目录下的所有内容

HTTP 基本知识

当你在阅读本文档的时候，你的浏览器向文档服务器发起了 HTTP 请求，并且从 HTTP 响应中得到了文档的内容，最后呈现给你。在这个过程中，你的浏览器实现了 HTTP 客户端，文档服务器充当了 HTTP 服务端，当客户端向服务端发起请求的时候，服务端回复相应的响应。

于是，我们需要了解一下 HTTP 的请求和响应分别都有什么内容。

一个 HTTP 请求，有如下几个部分（其中所有的换行均为 CRLF，即 \r\n）：

方法：如 GET、POST、PUT、DELETE 等
地址：如 http://www.baidu.com/s?wd=%E9%82%B1%E5%8B%87，这里域名是 www.baidu.com，路径是 /s，参数是 wd=%E9%82%B1%E5%8B%87
头部：一些键值对
正文：用于传输额外的数据

下面是一些实际的例子：

GET /s?wd=%E9%82%B1%E5%8B%87
Host: www.baidu.com
Accept: text/html

上面的请求向 http://www.baidu.com/s?wd=%E9%82%B1%E5%8B%87 发送了一个 GET 请求，没有请求的正文。

POST /users
Host: www.example.com
Content-Type: application/json
Content-Length: 16

{"name": "user"}

上面的请求向 http://www.example.com/users 发送了一个 POST 请求，请求的正文是一个 JSON。

服务器收到请求以后，经过一些处理，会发送响应给客户端。一个 HTTP 响应有如下几个部分：

状态码：常见的有 200 OK，404 Not Found，500 Internal Server Error 等
头部：一些键值对
正文：用于传输额外的数据

例子如下：

HTTP 200 OK
Content-Type: application/json
Content-Length: 25

{"id": 0, "name": "user"}

上面的响应的状态码是 200 OK，正文是一个 JSON。

简单总结一下，HTTP 实际上就是客户端向服务端发送一个请求，服务端向客户端返回一个响应；请求包括方法、地址、头部和正文；响应包括状态码、头部和正文。

你要实现的 OJ 系统会运行一个 HTTP 服务端，监听在本机的一个端口上。它会处理来自客户端的 HTTP 请求，并提供响应。

本次的 OJ 系统不涉及跨主机访问，因此所有的监听地址都只需要设置为 127.0.0.1。同一时间，通常只能有一个进程监听在同一个地址的同一个端口上。因此，如果你运行程序的时候出现 Address already in use 的报错，那就说明之前运行的程序还没有退出。

第三方库

下面是一些推荐的第三方 crate：

时间：chrono
全局变量：lazy_static
HTTP 服务器：actix-web, rocket
HTTP 客户端：reqwest
数据库支持：sqlite, mysql, diesel, sea-orm
命令行参数解析：clap, structopt
JSON 序列化与反序列化： serde_json, json
等待程序运行超时：wait_timeout

HTTP 服务器

在模板仓库中，已经用 actix-web 启动了一个简单的 HTTP 服务器，监听在 127.0.0.1:12345 上，并且实现了两个 API：GET /hello 和 GET /hello/{name}。对代码进行分解：

env_logger::init_from_env(env_logger::Env::new().default_filter_or("info"));

初始化了日志的配置，默认情况下会打印出 HTTP 服务器收到的请求。

HttpServer::new(|| {
    // ...
})
.bind(("127.0.0.1", 12345))?
.run()
.await

启动了一个 HTTP 服务器，监听在 127.0.0.1 地址的 12345 端口上。

App::new()
    .wrap(Logger::default())
    .route("/hello", web::get().to(|| async { "Hello World!" }))
    .service(greet)

启用了请求日志，然后实现了 API GET /hello ，它的行为是直接返回一个 Hello World! 的响应。同时引入了 greet，它的定义在前面：

#[get("/hello/{name}")]
async fn greet(name: web::Path<String>) -> impl Responder {
    log::info!(target: "greet_handler", "Greeting {}", name);
    format!("Hello {name}!")
}

这样表示它实现了一个 GET /hello/{name} 的 API，其中 {name} 部分会解析到 name: web::Path<String> 参数上，也就是说，如果访问了 /hello/abcde，那么这个函数会被调用，并且 name 会等于 abcde。接着，代码打印了日志，然后返回了 format!("Hello {name}") 作为响应的正文。

如果想要实现一个 POST 方法的 API，需要修改 #[get()] 为 #[post()]。经常需要处理 JSON 格式的请求正文，那么，依然可以让框架做解析（实际上底层就是 serde_json），只需要结构体标注了 #[derive(Deserialize)]：

#[derive(Deserialize)]
struct PostJob {
    // ...
}

#[post("/jobs")]
async fn post_jobs(body: web::Json<PostJob>) -> impl Responder {
    // ...
}

fn main() {
    // ...
    App::new()
        .service(post_jobs)
}

类似地，也可以让框架自动帮你把结构体转换为 JSON，只需要结构体标注了 #[derive(Serialize)]：

#[derive(Serialize)]
struct Job {
    // ...
}

#[post("/jobs")]
async fn post_jobs(body: web::Json<PostJob>) -> impl Responder {
    // ...
    web::Json(Job {
        // ...
    })
}

有时候，如果出现了错误，你会希望设置响应的状态码：

#[post("/jobs")]
async fn post_jobs(body: web::Json<PostJob>) -> impl Responder {
    // ...
    HttpResponse::BadRequest().json(Error {
        // ...
    })
}

更进一步，可以进行一些处理，自动把 Result 通过 ? 操作符转换为 API 文档中所需要的格式，可以大大简化错误处理的代码。

有时候，你在实现 API 的时候，可能会想要访问配置，此时可以利用 web::Data 来传递：

#[derive(Clone)]
struct Config {
    // ...
}

#[post("/jobs")]
async fn post_jobs(body: web::Json<PostJob>, config: web::Data<Config>) -> impl Responder {
    // ...
}

fn main() {
    // ...
    App::new()
        .app_data(web::Data::new(config.clone()))
}

这样，API 处理函数就会自动得到一份配置。这个方法也经常用来传递数据库的连接对象。

调试工具

下面是一些工具，能帮助你调试 HTTP 服务器：

下面讲解 VSCode REST Client 插件的基本使用方法。首先在 VSCode 中安装插件，然后新建一个文件 post_jobs.http，填入如下内容：

POST http://127.0.0.1:12345/jobs HTTP/1.1
content-type: application/json

{
  "source_code": "fn main() { println!(\"Hello, world!\"); }",
  "language": "Rust",
  "user_id": 0,
  "contest_id": 0,
  "problem_id": 0
}

上面的内容表示要向 http://127.0.0.1:12345/jobs 发送一个 POST 请求，正文是一个 JSON。此时 POST 上方会显示 Send Request 提示，按下它，VSCode REST Client 插件就会发送请求，并显示出响应的内容。类似地，你可以用它发送其他类型的请求：

GET http://127.0.0.1:12345/jobs HTTP/1.1

更详细的用法，可以阅读插件的文档。

全局变量

在 OJ 系统，需要维护当前的评测任务列表，如果没有实现数据库支持，可以采用全局变量来保存评测任务列表。但是，全局变量引入了新的问题，在多线程的场景下，如何保证它同时只有一个可变借用呢？课上会讲到这个问题，这里提前预告一下，解决方法是使用 Arc<Mutex<T>>，其中 Mutex 是互斥锁，提供了线程安全的内部可变性，Arc 是线程安全的引用计数器。例如要用 Vec<Job> 保存所有评测任务的话，可以用 Arc<Mutex<Vec<Job>>> 类型来定义一个全局变量，比如：

use std::sync::{Arc, Mutex};

struct Job;
pub static JOB_LIST: Arc<Mutex<Vec<Job>>> = Arc::new(Mutex::new(Vec::new()));

但是，上面的代码不能通过编译，因为 Arc::new() 函数无法用于静态变量的初始化。因此，我们需要引入第三方库 lazy_static 来实现这个事情，比如：

use std::sync::{Arc, Mutex};
use lazy_static::lazy_static;

struct Job;

lazy_static! {
    static ref JOB_LIST: Arc<Mutex<Vec<Job>>> = Arc::new(Mutex::new(Vec::new()));
}

这样就可以通过编译了。那么，在读取或者修改的时候，需要首先获取互斥锁，然后就可以对内部的 Vec<Job> 进行操作了：

let mut lock = JOB_LIST.lock().unwrap();
lock.push(Job);

为了保证多线程安全，互斥锁保证同时只能有一个线程获取，保证了数据在多线程场景下同时只有一个地方拥有可变借用。当 lock 结束生命周期时，锁会自动释放。编写代码的时候，需要小心出现死锁的情况。

运行程序

在 OJ 系统中，编译可执行文件以及评测的时候，都需要运行程序，并且按照需求传递命令行参数，或进行输入输出的重定向。Rust 标准库提供了 std::process::Command 来运行程序。

首先最简单的用法是，直接运行一个程序，等待其运行结束，并获得它的结束状态：

// Taken from rust docs
use std::process::Command;
let status = Command::new("/bin/cat")
                     .arg("file.txt")
                     .status()?;

println!("process finished with: {status}");

上面的代码运行了 /bin/cat file.txt 命令，等待其运行完成并获取它的结束状态。进一步，可以对结束状态调用 ExitStatus::success() 函数来判断程序是否正常退出，这可以用于 Runtime Error，Compilation Error 等结果的判断。

进一步，我们可能想要传递多个参数，或者对标准输入输出进行重定向：

let in_file = File::open("wordle.in")?;
let out_file = File::create("wordle.out")?;
let status = Command::new("wordle")
                     .args(["--random", "-t"])
                     .stdin(Stdio::from(in_file))
                     .stdout(Stdio::from(out_file))
                     .stderr(Stdio::null())
                     .status()?;

上面的代码运行了 wordle --random -t 命令，将标准输入重定向为 wordle.in，标准输出重定向为 wordle.out，丢弃它的标准错误输出，等待其运行完成并获取它的结束状态。

上面的代码会一直等待程序运行完成，如果想要设置超时，可以使用第三方库 wait_timeout。

注意事项

本作业将严格进行查重，任何抄袭同学或网络已有代码的行为均将被视为学术不端。
对于如何判定学术不端，以及应该如何正确地引用已有代码，请阅读 Writing Code Writing Code 中文版

最后更新: 2023年6月2日

作者: Jiajie Chen (80.17%), Harry Chen (19.83%)