オンラインジャッジの作り方/実装
オンラインジャッジを作ってみた、作ってみてる、作ってみようかなという人は結構多いのに、調べても何も出てこない不思議。
全体的な仕様
色々と、違いうる点がある。
今回はできるだけ必要最低限とおもわれる機能を追加していくことにする。
また、実装の方針として、できるだけ楽に、バグりにくくすることにする。
- 問題作成
- 問題にテストケースを追加
- 解答のサブミット
- 自動ジャッジ
- これらの一覧や検索等
コンテスト機能やログイン機能は後回しにすることにする。
何を作る必要がある?
多分この2つ。データベースは、1つのものを共有する。
- webサーバ
ユーザーからのhttpリクエストを処理してwebページを表示したり、投げてこられたソースコードをジャッジサーバに投げたりする。
- ジャッジサーバ
ソースコードをジャッジしてデータベースを更新する。
Webフレームワーク
何らかのWebフレームワークを使う事にはなると思う。が、これといって良いのが無いような?
結局自分はRailsを使ってますが、、rubyなのが修行だし、割とrails自体がバグってたりして修行。
でもユーザー数の少ないフレームワークはもっと修行になりそう。
おすすめ教えてください...
何が難しい?
大きく分けて、この3点だと思う。
- Webの作り方
- Webサーバとジャッジサーバの連携
- ジャッジサーバのセキュリティ
webの作り方
手っ取り早くそれっぽいデザインのものを作るには、twitter-bootstrapというCSSフレームワークが便利。最近、「適当に作ったよー」なwebサービスはほぼこれが使われている気がする。*1
railsでは、twitterboostrap-railsというのがあるのでそれを使えばいい。
あとは適当に実装すればいい。
webサーバとジャッジサーバの連携
一番シンプルに実装するなら、全部ブロッキングというか同期処理でというか、やればいい。
ジャッジサーバがジャッジ終了するまで、webサーバもレスポンスを返さない。これならまあやるだけ。
でも、ノンブロッキングにしたいですよね。ここは割と譲れない。
webサーバの概要としては、次のようにすればよさそう。
- webサーバはソースコードを受け取ったら、ひとまず状態=pending systemtestingにして、データベースに保存する。
- ジャッジサーバにリクエスト(サブミットidだけ投げればいいはず)を投げる。*2
- webサーバはレスポンスを返す(サブミッション一覧にでもリダイレクトすればいい)
ジャッジサーバの概要としては、次のようにすればよさそう。
- httpサーバなら、適当にレスポンスを返しておく。
- ジャッジしてデータベースを更新する。
あとどうでもいいけど(?)、そのあとF5連打するのがストレスフルなので、Codeforcesのコンテスト中のサブミット画面みたいにしたい。
サーバ側からのpush通知が必要そうで、一見面倒そうだけど、ここは手を抜いてポーリング。
サブミット画面で、自分のサブミットをjavascriptでポーリングする。状態がpending systemtestingから別の何かに変わってれば、F5する。これでいけるはず。
ジャッジサーバのセキュリティ
これが一番頭痛い。正直良くわからないのでググってたら、
http://imoz.jp/note/onlinejudge.html
こんなページがある。システムプログラミングしなきゃいけない?だるい。
と思ったらこんなものが。
libsandbox
システムコールの監視、TLE,MLEの監視などしてくれる。
ただドキュメント皆無なので(多分)、結構辛い。sample.pyを見れば基本的な使い方は分かるのだが、それ以上は未だにわかってない。
ので、自分の実装は、rails製のジャッジサーバからpythonを呼び出すという非常にアレなものになっております。。
まとめ
これでおそらく、一番簡単なオンラインジャッジは作れるはず。
ここに書いたことに加えて、twitterログインを追加したものが
https://github.com/wistery-k/oj
にあるので参考になるかも?(v0.1タグです)
これを書いてたら考えが整理されたせいで、上に書いてあることと実装が違ったりします、そこはよしなに...
この記事に足りないこと、書いてないことを誰か教えてください。個人的には、テストケースの生成やジャッジ形式の充実のさせ方が知りたい。