この記事はCompetitive Programming Advent Calendar 2014の14日目の記事です。

今回はCodeRunnerについて書こうと思います。例年はなにか新しいことに挑戦してそれについて書くみたいなことをやっていましたが、毎回消化不良になるのと今回は特に時間がないので…

CodeRunnerができた経緯

もともと弊社ではCodeVSの開発を毎年行っていましたが、今年は諸事情によりこれとは別のプログラミングコンテストを行うプロジェクトができました。
とにかくCodeVSと差別化を図るため、いろいろアイデアが出されました。こうして生まれたのが、短時間で1個の問題を解く、しかも問題によっては相互作用しあう形式です。これはちゃんと元ネタがあって弊社で一度行われた大会形式をオープンにして大掛かりにしたものになります(第五回ラボ天下一)。

題材ぎめ

感覚的にこれが一番時間がかかったと思います。CodeVS同様、参加者が集まらなければいけません。作問にあたって次の条件が課されました。番号が大きいほど優先順位が低いです。

ルールが単純であること
初心者勢でも楽しめること (簡単に試せること＆正の点を簡単に取れること)
ガチ勢でも工夫する余地があること
相互作用すること
ビジュアライズしやすいこと
最終的に人力よりプログラムのほうが強くなること

本当に都合がいいですね。こんな条件をすべてみたす都合の良い問題はそうそう考えつきません。これについてミーティングを始めると2時間の予定のはずが必ず5,6時間程度にはなってしまうぐらいには議論しました。
たとえば、運要素の強いゲームを出すと初心者勢でも簡単にスコアを稼げますが、戦略要素がなさすぎてガチ勢が飽きてしまいます。また、ラボ天下一のゲームでは、カウントの増加速度を掴みきれない初心者はかすることすらできず0点続出になってしまいます。
またたとえば、ある2人対戦用ゲームをランダムマッチするのを繰り返すというアイデアもありますが、これは他方の手がきたら通知するみたいな処理が必要になり、複雑になってしまいよくありません。

AtCoderさんにも軽くみてもらい、2ヶ月ほどかけてようやく題材が決まりました。社内コンペも軽く行い、他の題材は、「これ運ゲーじゃね？」とか「やってみたらつまらなかった」とかで落とされました。来年~~あれば~~使うかもしれませんね。
あとは、残り1ヶ月で予選ゲームをコンペ用から高負荷対応用にもっていき、予選を行い、さらにその後1ヶ月で決勝ゲームを作成する感じになります。みんなこれだけに情熱をそそげればよいですが、他にも案件を掛け持ちしての作業になりました。

予選1

いわゆる辞書ゲーです。ルールは簡単、50文字以下の[ABCD]からなる文字列を投げ、特定の連続部分文字列を含んでいればスコアが入る。できるだけスコアが高くなる文字列を見つけてね、というやつです。
これは相互作用もなく、ビジュアライズ要素も何一つないですが、社内で試してみたら好評だったのでわりと悶着なく採用されました。あまりに相互作用がなかったため、投げたクエリを一部マスクをつけて共有履歴化しようかとも提案しましたが、却下されました。
解法としては局所最適化・焼きなましがありますが、1秒制限があるため、最大10800回しか試行できないのでうまくやる必要があります。辞書の高得点単語をいくつかの試行で当ててそれをつないで稼ぐという方法もあります。
最終的に焼きなましのほうが強かったようで、若干運ゲーだったようにも見受けられました。

これはPlay Framework2(Java:EBean)+MySQL(Amazon RDS)で実装しました。本番ではAPIを受け付けるのがc3.4xlargeのEC2-3台でバックにc3.4xlargeのRDSが1台という構成でした。処理的にも特に複雑なことはなく、前もってつくっておいた辞書ファイルをひとつずつindexOfで存在性チェックしているだけです。この手の問題だったらtrieだろ！って感じですが、愚直でも速度面で問題なかったため、trieの出番はありませんでした。
MySQLにアクセスがいくのは、スコア更新時とトークンチェック・1秒制限チェックのときです。本当はトークンチェック・1秒制限チェックで毎回MySQLに通信しにいくのは良くないのですが、~~間に合わなかった~~負荷をかけても特になんともなかったのでこのままやっちゃいました。

試合中のアクセス推移はこんな感じです。

予選2

いわゆるRPGゲーです。部屋に最大3人になるように割り振られ、そこにいるボスを倒して次の部屋に行く…与ダメージの合計が得点になるというものです。隠れた属性相性みたいなのがあって、相性が良い属性以外はかなり低いダメージになります。
技が100個あり、そこそこ大きいダメージは10種類程度でしか出ません。100個の技を頂点にしたものに、関係性の辺を付与します。関係性は10x10個ずつで小さい10個の間で密度が高くなるように、その後に全体でいくつか辺で結んで、最後にWarshall-Floydで技同士の距離を出してからnax(5,1000/(距離^2))で与ダメージを計算しています。この計算の都合上、ダメージの値の種類はかなり少ないので、ヒントになってくれたらよかったのになーと思っていたんですが、そもそもこの構造自体に気づいた人が1,2人程度しかいなかったみたいで、現実厳しいという感想でした。スケーリングがちょくちょくあったせいでダメージがずんずん変わっていってしまったのもありますね。
ちなみにそこそこ大きいダメージが出たらそればかりで殴ると平均60秒でボスを倒せ、属性相性を完全に把握していると平均15秒でボスを倒すことができます。
このゲームについては相当議論を重ねました。最初部屋を自由に選べるようにしていたのですが、部屋を選ぶためにプレーヤーに渡す部屋の情報で有効なものがほとんどなかったので自動割り振りになりました。また、自分で有効な技をひたすら探す「正直者」と、自分で有効な技を探さず、攻撃履歴から最大効果の攻撃を取り出してひたすら殴る「横殴り」について、「正直者」が最終的に勝てるような仕組みにしないといけませんでした。「横殴り」が優位に立てるのは他に「正直者」がいる部屋の場合だけなので、適当な確率で「横殴り」を孤立させればなんとかなるみたいな結論でした。マックスアタックボーナスも「正直者」にボーナスを与える仕組みです。
また、このゲームは恒常的に敵を殴るため、後のほうで属性相性に気づいても、最初から何も考えずに殴っていたほうがスコアが上になってしまう懸念をchokudaiからもらいました。部屋が一定数たまるとスケールが上がり、敵HPとダメージすべてが同じだけ倍化するようにしました。

これも予選1と同じくPlay Framework2(Java:JPA)+MySQL(Amazon RDS)で実装しました。本番の構成は予選1と同様のものを4台-1台です。ただ処理としてはMySQLにかなり依存することになってしまいました。
テーブルはプレーヤー・部屋・履歴の3個からなっていて、

プレーヤーテーブルは、名前・プロフィール・トークン・スコア・現在いる部屋・最終攻撃時刻、
部屋テーブルは、ボスのHP・属性・マックスアタックボーナスの情報、
履歴テーブルは、プレーヤー・部屋・スキルID・スキルによるダメージ値
を主に持っています。1度/attackが走ると、必ず、プレーヤーは更新、履歴は追加がされます。マックスアタックあるいは部屋の振り分けのときに部屋テーブルが更新されます。
部屋振り分けの処理をできるだけ軽くするために、部屋テーブルに乱数を格納するpriorityカラムを設けて、プレイヤーを現存するpriority最大の部屋に振り分け、そのあとその部屋のpriorityを再設定するみたいなことをしています。

このテーブル構成で本番を迎えたところ、デッドロックが40秒に1回程度の割合で起こってしまっていました。予選1と違い、あちこちのテーブルを更新するので多少はしょうがないかと思って重篤にならない限りは大丈夫と踏んでいました。
しかし2時間20分すぎに最悪の事態が起こってしまいました。トランザクションがタイムアウトしはじめて、ほとんどのリクエストを受け付けなくなってしまいました。いそいで中断して原因調査しましたが、全くわからず無能感に苛まれたまま時間がすぎていきました。中断してアクセスが減ると普通にリクエストが通るので、アクセス過多でどこかが詰まっているんだろうとは想像できたのですが、それ以上のことはわからず、解決策も当然見つかりませんでした。
アクセスが少ない時にリクエストが通ったので、Playのプロセスを再起動、RDSも再起動してゲームを再開しましたが、現象はすぐに再発してしまいました。原因がわからない状態で再開させちゃいけなかったですね。

このときのルームが40000レコード程度、履歴は1.6Mレコード程度だったと思います。この多さが悪さしているのかなと思っていたのですが、インフラの人いわく、プレーヤーのテーブルに大量のトランザクションが貼ってあったようです。
予選2では負荷テストを長く回すことをしていなかったのではじまるまではこのダウンには気づけませんでした(気づけても直せる時間があったかどうか微妙)。

アクセス状況はこんな感じです。ゲームの性質上、アクセス数は他のゲームの2倍ちかくになっていますが、問題は、この大量のアクセスがフロントをほぼ素通りしてRDSで全部処理していたような構図になっていたことです。

正直なところ、現在でもまだダウンした原因についてはわかっていません。ただ決勝に向けて、プレーヤーテーブルへのロックをできるだけ避けるようにしないといけないなというのはうすうす感じていました。

決勝

決勝は召喚+交易ゲーです。召喚のみでもある程度稼げますが、うまく交易するともっと稼げるよ、というものです。ただそれだけのはずなのにやはりルールが複雑っぽくなってしまいました。むずかしい。
個人的にこれが一番やりたかったゲームです。CedecAIの懇親会で、そのときの同じ題材Java Challengeで交易があったけど誰も使ってくれなかったみたいなことを聞いたので、機会があったら試してみたいなーと思っていました。
ゲームとしては、プレイヤーが得る召喚石の個数はどうあがいても一定、そして0.9997というバイアスは100体召喚されても3%程度しかスコアが下がらないことを見抜き、市場を支配して石を適切に貯め召喚するのが良い戦術になっています。このバイアスは本来貯める戦術を落とすためにつくられたものですが、先手必勝で他の人達が召喚していくなか、自分の戦術が正しいと信じて待つのは割と辛いのではないかという独断に基いて1に必要以上に近づけてあります。
予選2の大失態をうけて、「本番絶対落ちないようにする」というのがかなり意識されました。負荷テスト(長回し)も相当数やりましたし、以降に書くように構成も若干変えました。

決勝はPlay Framework2(Java:Jedis)+Redisで実装しました。実はこの開発までRedisはほとんど触ったことがなかったのですが、予選2で大量にアクセスされたプレーヤーテーブルの各プロパティは、複数が同時に更新されることがないため、ハッシュマップ的なもので良いのではないかという考えからNoSQL使ってみようという結論になりました。
PlayでMySQLにアクセスするときは主にhibernate経由でSQLの戻り値をクラスにO/Rマッピングして取り出します。チューニングするときは、クラスで必要なプロパティだけ値をセットさせたり、そもそもクラスにマッピングさせなかったりみたいなことをしますが、これは可読性を損ねるものなので、普通の開発だと一番最後にやります。予選は一杯一杯で残念ながらそこまで手が回りませんでした。それから、アノテーションによりパラメータの振る舞い(ID, カラム長, ユニーク性, 外部参照 etc.)を定義しますが、これの習得にえらく時間がかかった記憶があります。
RedisだとそもそもO/Rマッピングの仕組みすらありません。トランザクションも自力で管理しなければいけません。でもRedisのドキュメントを読むとすごくワクワクします。各関数には時間計算量が書いてあるし、こういうときはこっちの関数を使えば高速になるよ的な関数がたくさんあって、コーディングの工夫がはかどりました。
この選択は正しかったようで、再三の負荷テストに対してもRedisサーバーは一度も例外を吐きませんでした。それどころか、メモリ上に展開しているはずなのに、どんなにぶんまわしても1.5GB程度までしか行かないのには驚きでした。

それから、予選で野放しにしていたトークン管理をちゃんと実装しました。
まずトークン変更に対しトークンイベントを発行してRedisのソート済みリスト型に格納します。フロント側は有効なトークンをConcurrentHashMapで管理し、ソート済みリストに対し数秒おきに読みに行って、差分のみ反映します。リクエストが来たらConcurrentHashMap.containsKeyでトークンの有効性をチェックできます。
次に有効なトークンに対し1秒制限をかけることですが、たとえば/summonに対しsummonlock:(token)をキーとしたエントリを、ロック用エントリとします。リクエストがきたら、ロック用エントリに対し、"このエントリが存在するかチェックし、しなかった場合は追加する"処理をし、存在していたら1秒以内なので抜けます。このあと本処理を行い、終了時に、ロック用エントリに"1000ms経ったら消える"という属性をつけます。これならロックチェック前のタイミングで同時にアクセスされても二重に処理することはないですが、本処理中に何らかの例外で想定しない抜け方をした場合永遠にロックが解除されないという問題もあります(負荷テスト・本番通してそういうことはなかったみたいです)。
APIのなかでも、/tradeは実装難度が高かったと思います。dupeしてもlostしてもいけません。概略としては、

既存の自分の取引を強制キャンセルします。
自分の所持している売り石をすべて取り上げます。こうすることにより同時に同じ取引を行っても他の取引を無効にできます。
既存の取引とマッチングさせます。
マッチしきれなかった石を取引として登録し、マッチした取引で得た石と残りの売り石を自分の手元に戻します。

という流れです。1,2それぞれで楽観的ロックをかけています。

負荷テストでボトルネックになったのは、実は/monsters.zipでした。最初zip化していなくて転送量が半端ないことになっていました。/monsters.zipを連打すればもしかしたらサーバーを落とせたかもしれません(多分会場の回線が最初に逝く)。

本番のアクセス状況は次の通りです。負荷テストではこのピーク時のアクセスの37倍のアクセスを3時間かけ続けていました。ちなみにtwitterの最高瞬間風速であるバルス砲は、そのさらに18倍程度になります。(数字は少し適当なのであとでなおすかも)

開始90分後あたりで誰かがDoSを仕掛けたかもしれません。

共通の機能

3問ともゲームを自分で実装するので、割りと共通化している処理がいくつかあります。特にプレイヤーに関係するのは"/"(トップページ)と"/profile"でしょうか。順位表はビジュアライズ側で、ルールのURLもきっとどこかにあるだろうとのことで、トップページは、最初おまけのつもりで作ったのですが(確かルールにトップページのことは記してないはず)、予選1でビジュアライズが2時間ほど沈黙していたようで、なんだかわからないけど役に立った感じでした。予選1を受けて、以後も同様の機能を持つようにしました。決勝でルールリンクがあさっての方向に行っていたのは、完全にこちらのミスです、ありがとうございました。
/profile は、ただ順位表見せるのもいいけど、なんか一言とかtweet的なものがあるといんじゃねということで独断で実装したものです。これはどんなもんだったんですかね・・。予選2だとデフォで空文字列になるので/infoでパースしにくくなるということがありました。決勝ではprofileを適当な文字列にすることと、そもそもprofileを/infoにいれないことで対処しました。

これから

正直なところ、2ヶ月間ずっと余裕なく開発で非常に辛かったでした。競プロ関連のプロジェクトでなければ投げ出していたでしょう。「今年は余裕なかったけど来年はノウハウがたまっているからもっと効率的にできる」とは全然思っていません。来年も同じことをやるなら、テストもしっかり書ける程度にスケジュールに余裕が欲しいし、社内コンペも手軽にできるようにしたいです。
それから、新技術・インフラ関連・チューニング関連にはもう少し詳しくなりたいと思いました。ただこの辺は業務では日常的に登場するものではないのでどうやって身につけたらいいか思案中です。
あと懇親会のごはんおいしかったです。もっとたべたかったけどお腹が許してくれませんでした。

次は愛されるぼっちichyoさんです。愛しましょう。