Design an online code judge

A judge has to run untrusted code safely, and it must survive a contest spike that is about 24 times a normal day. The Submit API validates the request, saves the source with a queued status, puts a small job holding only the submission ID on a durable queue, and returns at once. Judge workers, one job per dedicated core, take jobs, use test data cached locally by problem and version, and run the compile and every test in a fresh sandbox.

The sandbox has no network, a seccomp filter, cgroup limits for memory, processes and output, and both a CPU limit and a wall-clock limit. The worker compares output outside the sandbox and writes the verdict, keyed by submission ID, so redelivery is harmless. Sizing is the arrival rate times the time per job: 83 per second times 8 core-seconds is about 667 cores, so with headroom I would plan 55 machines of 16 cores, started on schedule before the contest, with a queue-age rule as backup.

A per-user cap and separate lanes keep it fair. Pinned toolchain images and re-runs of borderline timings keep verdicts repeatable. For a bad test case, I would publish a new data version and rejudge in a low-priority lane.

These numbers are assumptions for the exercise, not facts about a real system:

• A normal day brings 300,000 submissions.
• A contest has 20,000 participants who send 120,000 submissions in 2 hours. The busiest moments run at 5 times that average.
• Judging one submission takes 2 seconds to compile and 20 tests of 0.3 seconds each, on one dedicated CPU core.
• There are 2,000 problems, and the test data for one problem averages 20 MB.

The arithmetic:

Submissions per second, normal day

300,000 ÷ 86,400 s ≈ 3.5

≈ 3.5/s

Submissions per second, contest

120,000 ÷ 7,200 s ≈ 16.7; × 5 for the peak

≈ 17/s on average, ≈ 83/s at the peak

Core-seconds per submission

2 s compile + 20 × 0.3 s

8 core-seconds

Cores busy at the contest peak

83/s × 8 core-seconds

≈ 667 cores; with 30% headroom ≈ 870, or 55 machines of 16 cores

Cores busy on a normal day

3.5/s × 8 core-seconds

≈ 28 cores, so the contest needs about 24 times more

All test data

2,000 problems × 20 MB

40 GB, which fits on a worker's local disk

Assume every submission is hostile. It can fork until the machine is full, fill the disk, read other files, open the network, or look for a kernel bug. The compiler is also at risk, since a tricky source file can make it use huge memory or read files it should not. Layer the defences.

• Isolation. Run each job in a container built from Linux namespaces: its own process list, mounts and an empty network, so there is no network at all. Add a seccomp filter that allows only the system calls a normal program needs, drop all privileges, and use an unprivileged user and a read-only root file system. A small writable scratch area is thrown away afterwards.
• Resource limits. Use cgroups. Cap memory at, say, 256 MB with no swap, so an overrun is killed and reported as Memory Limit Exceeded. Pin the run to one core. Cap the number of processes at 64 to stop fork bombs, and cap output size so a loop that prints forever cannot fill the disk.
• Two clocks. Enforce a CPU time limit, say 1 second, measured by the cgroup. Enforce a wall-clock limit of about 3 times that, to catch programs that sleep or wait for input. Either one gives Time Limit Exceeded.
• A fresh sandbox every time. Never reuse one between users, so nothing is left behind to read.

Keep the hidden answers out of the sandbox. The program receives each input on standard input and nothing else. The expected output stays outside, where the worker compares it.

Containers share the host's kernel, so a kernel bug could let code escape. If the contest is public and the stakes are high, run each job in a micro-VM, which has its own kernel and a stronger wall, at the price of a slower start. A cheaper middle path: run the containers inside disposable worker VMs that hold no secrets and no credentials. Then an escape reaches nothing valuable.

The Submit API does as little as possible. It checks the source size and the language, applies a per-user limit, saves the source and puts a job on a durable queue that holds only the submission ID. It replies in milliseconds with the ID. The queue turns a sharp spike into a line the workers drain at their own pace.

Delivery is at least once. A worker hides a job while it works, and if it does not finish within a timeout, the job reappears for another worker. Judging takes tens of seconds, so the worker sends a heartbeat that extends the timeout. Because the same code and tests always give the same verdict, a duplicate run is harmless: the verdict is written once, keyed by the submission ID. A job that crashes its worker three times goes to a dead-letter queue for a person to review, and the user sees 'System error' rather than a hang.

Sizing. By Little's law, the cores busy are the arrival rate times the time per job. At the contest peak that is 83 per second × 8 core-seconds, about 667 cores. Add 30% headroom and you need about 870 cores, which is 55 machines of 16 cores. Judge one job per core, so tests do not compete for CPU and distort the timings.

Autoscaling that reacts to queue depth is too slow on its own, because a new machine takes minutes to start. For a known contest, scale on the schedule: bring machines up 15 minutes early, and warm their test-data caches. Keep the reactive rule as a backup, based on the age of the oldest job. If the queue's oldest job passes 30 seconds, add capacity.

Fairness. Cap how many of one user's jobs run at once, say 3, so a script that submits 200 times cannot starve everyone else. Use separate lanes for contest, practice and rejudge jobs, with the contest lane first. Show the user their place in line, and the progress, such as 'judging test 7 of 20'.

Most verdicts are stable by nature. The trouble is borderline timing and moving tools, so remove the sources of drift.

• Pin the toolchain. Each language runs from an immutable image, identified by a digest, with fixed compiler flags. Record the image on the submission. An upgrade is a new image, never an in-place change.
• Measure CPU time, on a dedicated core. One job per core, no neighbours. Compare the time to a limit that was set from a reference solution, say 2 to 5 times its time, with a larger factor for slower languages.
• Re-run the borderline. If a run lands within about 10% of the limit, repeat it up to three times and keep the best. A noisy machine then cannot turn a pass into a fail.
• Special checkers. When a problem has many valid answers, run a checker program in its own sandbox. It reads the input, the jury's answer and the user's output.

Test data. Keep it in object storage with a version number per problem. A worker caches it on local disk by problem and version, and checks a checksum. The whole 40 GB fits on one disk, and a least-recently-used rule drops the oldest problems if space runs short. A new version means a new cache key, so there is no stale-data bug.

Rejudging. A test case is found to be wrong. Publish the corrected data as the next version, such as 5 in place of 4. Then a rejudge job finds the affected submissions, perhaps 30,000 of them, and puts them in the low-priority lane so live users are not delayed. Each new verdict is stored as a new row that names the test-data version. The old one stays in the history. Where the result changes in a contest, recompute the standings and announce it.