Library Checkerを支える技術

あけましておめでとうございます。これは Competitive Programming (2) Advent Calendar 2019 - Adventar の 14日目の記事です。あけましておめでとうございます。

この記事では、Library Checker の宣伝をします

Library Checkerって?

競プロのライブラリを整備するために爆誕したサイトです。特徴としては、問題が全部ライブラリを整備する目的に特化していること、ケースジェネレーター、チェッカーなどが全て公開されていることが大きな特徴です

中身を全て公開することにより

  • 誰でも問題の追加が出来る
  • 誰でもケースの修正などが出来る
  • CIに組み込める*1

などの、様々な利点を得ることが出来ます。理論上はO(使用人数)でケースが強くなっていくので、最強のテストケースが出来ると言う目論見です。

概要

こんな感じです

f:id:yosupo:20200101233401p:plain
こういう図をブログに貼りたかった

見ての通り、GCP(Google Compute Platform)で動いています。

一つ一つ紹介していきます

Problems

library-checker-problems で問題の情報を管理しています。

ジェネレーターとかは全部C++で、それをpythonから叩く仕組みになっています。 目的上どの環境でも同じテストケースを吐き出すようにしないといけないので、とても苦労しています。(uniform_int_distributionは環境依存なんですよ、知っていましたか?)

Cloudbuild

図にやたら出てくるやつです。yamlファイルにコマンドを書き並べるだけで、githubにpushするたびに実行とかをやってくれるので乱用しています。今5種類ぐらい使っています。

ジャッジサーバー

dockerなどの既存のコンテナは時間計測 / メモリ計測がむずかったので、いっそのことと思い、unshare / cgroups / overlayfs などの(dockerの中で使われてる技術たち)を直接叩き、コンテナを作っています

  • unshare: プロセスからネットワークのアクセスを禁止したり、mountを分離したりしてくれるすごいやつ
  • cgroups: これがないと何も出来ない。プロセスのCPU、メモリ消費量とか諸々を制限してくれるすごいやつ
  • overlayfs: プロセスから/tmpとか変な場所にファイルを書き込んでも、パッとやるとそれらを一瞬でなかったことにしてくれるすごいやつ

ずっとサーバー借りてると高いので、preemptible(AWSのスポットインスタンスみたいなもの)を借り続けるという雑なことをしています。24時間(or もっと短い)で勝手に停止してしまうので、停止を検出したらCloud Functions(≒ AWS Lambda)で自動再起動、うまくいくのかと思いましたが、今のところうまくいっています。

SQL

Cloud SQLと言うフルマネージドのサービスでPostgre SQLを立てています。バックアップなども取ってくれているようなので慢心しています。

このサービスのコアで、全てが入っています。問題のテストケースもbytea型でそのまま入っています ええんかこれ?

APIサーバー

(最近正式サービスとなった)Cloud Runで動いています。理由はApp engineだとgRPCが動かなかったからです。 apiv1.yosupo.jp:443 で動いていて、API一覧は library-checker-judge/library_checker.proto at master · yosupo06/library-checker-judge · GitHub です。(RESTではないので、GitHub - ktr0731/evans: Evans: more expressive universal gRPC client のようなgRPCクライアントを使わないと何も見れないです)

フロントエンド

言ってしまえばAPIサーバーを叩いて結果を出力するだけです。

APIサーバーを作る前はgoでSQL直接叩いてやっていたのを、API化と共にtypescriptとかそう言うのに置き換えようと思ったんですが、断念して今はgoでAPIを叩いてやっていっています。

おわりに

このプロジェクトは、いつでもみなさんの協力をお待ちしております。最近めちゃくちゃコントリビューターが増えて、嬉しい。 普通のOSSよりは競プロ勢の人にとってとっつきやすいと思うので、pull requestsとかに興味があるけど、難しそうだし〜と言う人は、ぜひ!

明日(概念崩壊)はsaka_ponさんの競技プログラミングでも C# で簡潔に書きたい です。ありがとうございました。

*1:ざっくり言うと、自動で「ライブラリをちょっと修正するたびに全部の問題に投げ直す」ことが出来ます