Design and implementation of online judge system
My previous blog posts were describing how to safely compile and run an untrusted user code. They also showed that the user process will only read from standard input and write to standard output. Pair of official input and output data is called test case. Test case also has a checker program associated with it, which compares user output with official test case, and decides if the output is correct. This is also the smallest processing unit of this judge system.
Central part of this judge system is the dispatcher. It is responsible for:
- receiving new tasks for evaluation from web
- notifying the workers about these new tasks
- receiving the results from workers
- notifying the web about the results of evaluation
Dispatcher is implemented as postgresql database. It has only one table, named queue, which stores tasks that need to be evaluated. Basic design of this table is as below:
| Column | Type |
|---|---|
| queue_id | integer |
| queue_status | integer |
| text_in | text |
| bin_in | bytea |
| text_out | text |
| bin_out | bytea |
Field queue_status indicates what is the status with this task, it can be:
- 0 - the worker hasnt fetched this task yet
- 1 - worker is evaluating this task
- 2 - task is completed
Notifying workers about new tasks
Postgresql database supports LISTEN and NOTIFY commands. Clients that issue LISTEN commands, will be notified when the database issues NOTIFY command. Each worker issues LISTEN for channel new_queue_row, and the database is configured to issue NOTIFY new_queue_row when new row is inserted into queue table. When workers fetch this newly inserted row they fetch it inside a transaction, which prevents multiple workers from fetching the same row, this function is called queue_fetch_front().To make this functionality easier to use, it was separated in a service called waiter. It is a thrift service, which has only one funcition.
bool wait(string channel, int timeout_ms);
This function waits for a notification on the given channel, and returns true when notification is received. If after timeout_ms notification wasnt received, false is returned. After the worker receives true from the wait() function, it executes queue_fetch_front() function in database to retrieve the new row.
Permdata service
Permdata service is also a thrift service, which runs with every worker. It is used by the worker to retrieve test cases, or any other blob of data from the database. Permdata has its own database with one table that has only three columns.| Column | Type |
|---|---|
| data_hash | text |
| blob | bytea |
| t_added | timestamp |
Primary key of this table is data_hash, which is md5(blob). Calculating hash was chosen over incrementing ids, because this way cache cant get invalidated at any time.
Primary reason for making the permdata service is to avoid storing large blobs of data in the queue table. Instead of storing the whole test case, which can be several megabytes of size, we now need to store only its hash, which is 32 characters. Permdata service is also a good place to cache all of the test cases, to avoid multiple transfers of large data over network.
Permdata thrift service has only one function.
struct getDataResult {
1: bool found;
2: binary data;
}
getDataResult getData(1:string hash)
This also means that the worker only has read permissions on the permdata database.
download file now