作业要求¶

作业要求分为三部分：

40 分的基础要求，这一部分的目的在于考察上课学习的内容，有少量需要自习的内容
40 分的提高要求，这一部分难度较大，需要自己学习课上不会讲到的内容
20 分的非功能要求，即代码规范和报告

本文提供两个版本：简洁版本和详细版本，可以使用下面的按钮进行切换：

切换版本

简洁版本去掉了提示，只保留作业要求
详细版本包括所有内容

建议在刚开始做大作业的时候，选择详细版本；在对内容比较熟悉后，切换到简洁版本，方便检查自己的实现是否满足要求。

当前版本：简洁版本

当前版本：详细版本

自动化测试¶

作业的基础要求部分将使用 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 状态码，对于定义好的错误，必须按照 API 文档给出的要求实现。

基础要求（40’）¶

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

（15’）基础评测：运行 Web 服务器，实现 POST /jobs API。
- 从命令行参数获得配置文件路径，解析配置文件内容
- 接受到 POST /jobs 请求时，从请求中获取 source_code 字段，根据配置文件中 Rust 语言的配置，使用 rustc 命令编译为可执行文件。
- 根据题目 ID 找到题目的各个数据点，对题目的各个数据点进行评测，衡量测量程序运行的真实时间（wall time），在超过设定的时间限制一段时间（如 500ms）后强制终止程序；
- 比对程序输出的结果与答案，需要支持两种模式：standard（忽略文末空行和行末空格）和 strict（严格比较）
- 实现阻塞评测，在评测后才返回响应，因此只会出现 Finished 状态，数据点结果仅会出现 Waiting（前序数据点尚未评测完成或编译错误）、Accepted（答案正确）、Wrong Answer（答案错误）、 Time Limit Exceeded（超时）和 Runtime Error（运行时错误，程序异常退出）
- 不需要保存评测历史，所有评测 ID 都可返回 0
提示
- 不要忘记在前一个大作业里学到的知识。
- Rust 标准库的 std::process::Command 不支持超时后强制终止程序，可以用 wait_timeout 库来实现。
- 测量运行时间可以用 std::time::Instant 来实现：运行前获取当前时间，运行结束再获取一次，然后求差。
- 如果想不明白如何忽略文末空行和行末空格进行比较，可以先用比较熟悉的 C/C++ 写一遍，再想想 Rust 怎么写
- 运行时错误要根据程序退出时的状态码判断，只有 0 才表示程序正常退出，其他都是异常。
- 不要忘记编译器也可能异常退出。
（5‘）多语言支持：支持配置文件中提供的其他语言（保证使用的编译命令存在于系统中）
- 请保证你的系统内安装了 gcc 和 g++
- 如果你在 Windows 中开发（但没有使用 WSL），可以本地修改测例的配置为其他编译器（如 MSVC，MinGW 等），但不要提交到 Tsinghua GitLab 代码仓库上
提示

如果在之前实现 Rust 语言支持的时候，就是从配置文件读取编译命令，那么这一步就会很简单。
（10’）评测列表：保存启动以来的评测列表，实现下列 /jobs 开头的 API，实现对任务的搜索，详情查询和重新评测。
- GET /jobs：筛选并获取评测任务列表；
- GET /jobs/{jobId}：获取指定评测任务信息；
- PUT /jobs/{jobId}：重新评测指定评测任务。
提示

这里需要维护当前的评测任务列表，如果没有实现数据库支持，可以采用全局变量来保存评测任务列表。但是，全局变量引入了新的问题，在多线程的场景下，如何保证它同时只有一个可变借用呢？解决方法是使用 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 结束生命周期时，锁会自动释放。编写代码的时候，需要小心出现死锁的情况。

将来如果实现了数据库持久化支持，可以把数据保存到数据库中。如果你想提早实现数据库持久化，也可以一步到位。
（5‘）用户支持：实现所有 /users 开头的 API，支持简单的用户功能。此时创建任务时应该进一步检查用户 ID，并且支持通过 ID 和名称搜索相应用户的评测任务。
- GET /users：获取用户列表；
- POST /users：新建或更新用户；
- 系统启动时自动创建用户：ID 为 0，用户名为 root。
提示

和评测任务列表一样，可以用全局变量来保存用户列表。
（5’）排行榜支持：
- 实现简单的排行榜：按用户所有问题的得分之和进行排序（排序方式详见参数）；
- 暂不考虑比赛，传入的比赛 id 恒为 0，即只要实现 GET /contests/0/ranklist 获取全局排行榜即可。此时用户的分数按题目 ID 从小到大顺序对应。
提示

实现前，请先仔细理解 API 文档中关于 tie_breaker 的部分，先思考如何实现排序算法，可以满足 API 文档的需求，再开始编写。不然很大概率会写到一半，发现要大改逻辑。

提高要求（40’）¶

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

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

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

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

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

允许用其他语言实现前端，是因为这符合很多现代网站的开发方式：前端用一个语言，后端用一个语言。在这里后端语言就是 Rust。

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

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

提示

实现之前，可以了解一些目前比较成熟的 API 鉴权的方法，并且学习如何安全地使用它们。安全并不容易，如果没有预先的学习，很难设计出安全的方法来。
（10’）多角色支持（依赖上一条）：支持不同的用户角色，如管理员、出题人、普通用户等，不同角色拥有不同的 API 权限
- 绘制一个权限表格，记录每个角色可以或者不可以访问哪些 API

（10’）多比赛支持
- 实现 /contests 开头的其余 API，支持新建或更新比赛，获取比赛信息和获取比赛排行榜。
- 比赛 ID 为 0 时特殊处理，认为比赛 0 包括所有用户和所有题目，用户和题目都按 id 升序，没有开始和结束时间，没有提交次数限制，比赛 0 的配置不可修改
- 比赛 ID 不为 0 时为正常的比赛，需要通过 API 新建或更新
（10’）持久化存储：将所有的评测任务、用户信息和比赛信息实时保存到文件系统，启动时读取（以下两种方式二选一）
- （5’）简单文件持久化：将所有状态保存到 JSON 等结构化文件中，启动时读取，并定时/实时保存
- （10’）数据库持久化存储：选择一个数据库后端（如 SQLite），设计合理的表结构
（10’）非阻塞评测，以下两种方式二选一
- （5’）评测依旧在单个请求中处理，但不阻塞其他的 HTTP 请求处理。
- （10’）将评测与 API 请求处理分离，即创建任务的请求应该立刻返回（返回 Queueing 状态），使用额外的线程运行评测；评测开始后更新状态为 Running（可选实时更新数据点结果）；评测结束后更新状态为 Finished，并更新相应的完整结果。如果评测过程中出现内部错误，更新结果为 System Error。
提示

非阻塞评测的核心在于，当 OJ 在处理评测任务的时候，依然可以继续处理来自用户的请求。

Web 框架会按照处理器的核心个数起若干个线程，每个线程都可以处理用户请求。如果使用阻塞评测，那么正在处理评测任务的那一个线程将无法处理其他来自用户的请求。随着同时进行的评测任务越来越多，OJ 将会进入所有线程都被阻塞的情况，此时就无法继续处理来自用户的请求。

因此核心思想就是要把阻塞的任务放到单独的线程池里去执行，这样就不会阻挡新的用户请求。Web 框架提供了 actix_web::web::block 函数来把阻塞的代码放在线程池中执行。这个函数也返回了一个 future，可以用 .await 来等待阻塞代码执行完成，但由于使用了 async/await 机制，实际上不会阻塞当前线程。

此外，如果希望启动一个 async 函数，但是又不想等待它执行完成，可以用 actix_web::rt::spawn 在 当前线程 启动一个单独的 async 函数。

下面是非阻塞评测的流程图：
（10’ ⚠）独立评测进程：此要求依赖于非阻塞评测。将评测进程与 OJ 服务端分离（但可以共享题目配置文件）。服务端收到请求时，将评测任务推入队列。独立的评测进程轮询队列，并运行评测、更新结果。不要求评测进程和服务端是分布式运行的，但建议使用消息队列（如 RabbitMQ）来实现解耦合，以自动获得错误处理、负载均衡等高级功能。此外，还需要实现 DELETE /jobs/{job_id} API，用于取消某个正在排队的评测任务。
（10’ ⚠）资源限制进阶：此功能要求在 Linux 上实现，并建议在独立评测进程的基础上完成。具体要求如下：
- （3’ ⚠️️）测量内存占用：测量程序在每个数据点上的最大内存占用（指工作集大小）并报告
- （7’ ⚠️）初步限制内存占用：限制程序在每个数据点上的内存占用，并在程序因此退出时报告 Memory Limit Exceeded
提示

可以使用 wait4 等方式测量程序在每个数据点上的最大内存占用（指工作集大小）。

可以使用 ulimit 等方式限制程序在每个数据点上的内存占用。

这一部分会涉及到较多 Linux 底层调用，可能需要编写 unsafe 代码。
（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：支持不使用内置的 standard 和 strict 答案比对算法，而是通过外部程序将用户程序输出与标准答案进行对比，并给出得分。此选项即对应题目配置的 type 为 spj，并在 misc 字段中增加以下配置：

"misc": {
  "special_judge": ["python3", "./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 主要功能说明和截图（不必面面俱到）
- 提高要求的实现方式（如有）
- 完成此作业感想（可选）

提示¶

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

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

运行 OJ 服务端的时候，如果出现报错信息 Address already in use，意味着还有 OJ 服务端在后台运行，请先结束正在运行的 OJ 服务端，再重新运行。

由于 OJ 系统评测时会运行子程序，如果 OJ 系统实现出现问题，可能导致子程序一直在后台运行，占用 CPU，导致自动测试超时。此时可以用 ps aux 命令列出系统里的所有进程，如果发现有一些之前的遗留进程，可以用 killall 进程名 来结束。

注意事项¶

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

最后更新: 2023年7月18日

作者：Jiajie Chen (99.35%), lionmjump (0.65%)