ISUCON7本選の出題を担当した @methane です。参加者の皆様、お疲れ様でした。
すでに Twitter でアナウンスされているとおり、本選の問題を Github で公開しています。
▼isucon/isucon7-final
すでに一週間以上経ってしまいましたが、この記事では本選の問題設計や攻略ポイントについて解説していきます。
一方本選では、そういった気遣いを一切無視して自分たちの得意な分野の問題を出そうということで、MOゲームをお題に選びました。
「協力してレイドボスを殴るゲームにしようか。」
「ボスのヒットポイントは無限にして総与ダメージをスコアにできないかな。」
「攻撃スキル、バフ／デバフスキルみたいなのはコード量を大幅に増やす割にISUCONとして面白くないから、もっとシンプルなルールが良いよね」
「あれ、クッキークリッカーってレイドボスになるんじゃない！？」
という流れで Chair Constructor Online にすることになりました。
自分たちの得意分野をやるということで、WebSocketを使ってマルチプレイ対応することまでは考えていましたが、ボトルネックをどう作り込むかなどはアイデア時点では考えていませんでした。
アイデア段階では存在しなかったタイムスタンプや未来に反映されるコマンドを使った同期といった難しい部分は、予選期間中にお題のゲームのプロトタイプを作ってくれていた @hasi_t が作り込んでくれました。
オンメモリ戦略: RDB上のデータを正としてプロセスメモリ上のデータをキャッシュとしてのみ利用するのではなく、プロセスメモリ上のデータを正として、RDBは永続化のためだけに使う（もしくはRDBを捨てて別の永続化手段を取る）
ISUCON参加者の中にはオンメモリ戦略を嫌う方もいます。
その理由は次の2点が大きいと思います。
RDB 以外の永続化手段は実際のWebの現場では安全性のために利用しにくいので、ISUCONでしか使えない戦略である（現場でも活かせる方法で勝てるようにしたい） シングルプロセスでマルチコアを活用できるGoが、ISUCONでよく使われる他の言語と比べてかなり有利になる
しかし今回の問題は明確にオンメモリ戦略が有効な問題でした。それで問題ないと判断したのは次の理由です。
FPS等の短時間のMOゲームならサーバーや回線のトラブル時に無効試合になるのは一般的で、信頼できる永続化は必須ではない 部屋毎に接続するプロセスを固定することで、Go以外の言語でもオンメモリ戦略を効率的に実装できる
今回のクライアント（Webアプリ、ベンチマーカー共に）は、APIが返したホストとポートに対して接続するように実装されており、例えば部屋名のハッシュ値などをもとに接続先を指定してやることで、動的なリバースプロキシなどを作ることなく簡単に部屋毎に接続するプロセスを固定することができました。
そうなると、むしろシングルスレッドで動いている言語の方が、排他制御などを考えなくて良い分Goより楽な部分も出てきます。
本選では言語間の公平性はあまり重視していなかったものの、ここだけはGoが圧倒的に有利にならないように配慮しました。
Goやnode.js (本選では async/awaitを利用) にとってはこれは得意分野ですし、Pythonもスレッドプールを利用することで比較的上手く解決していますが、 php は deferred/promise 地獄になっていますし、 Ruby と Perl はMySQLアクセス中にWebSocketの処理がブロックしてしまう状態になっていました。
ただし、想定解法ではMySQLのアクセスは序盤で排除する前提でした。なので、この部分が苦手な言語ほど早い段階でMySQLを捨てる決断ができたのではないかと思います。
この関数は前半で現時刻までの addings と buyings から現在の椅子の数と生産力を計算し、後半ではこれから先1秒間のスケジュールを計算します。前半部分もあとでチューニングしますが、せっかくユニットテストが用意されているので、関数のAPIを壊さずにチューニングできる部分を優先します。また、この最適化はオンメモリ化の判断の前に可能な部分でもあります。
この中でチューニングが簡単かつ効果が大きいのは、アイテムの価格と生産能力のキャッシュと、 on_sale の計算部分です。
価格と生産能力はマスターデータから同じ形の計算式を使って計算しています。アイテムのIDと生産個数をキーにキャッシュするとシンプルですが、ユニットテストは別のマスターデータを使っているので、最初は計算部分だけをキャッシュするとユニットテストを壊すのを遅らせることができます。例えば Python だと次のようになるでしょう。
on_sale の計算は、1000回ループの中で、さらにアイテムの種類数 (13) のループで実装されています。まだ買えないアイテムを安い方からチェックすれば、13000回のループを約1000回に抑えることができます。
他にも、言語ごとに異なる重い部分があるかもしれません。多倍長整数演算が入っているためにどの部分が重いのかが見た目からの直感と反する事が多いはずなので、ちゃんと大きめのテストデータを用意して、（自作でも、ベンチマーク終盤の入力を保存＆リプレイでも可）プロファイルを取りながら最適化しましょう。
例えば1000回ループは buyItem や addIsu が発生した時間の回数分のループに書き換えることができますが、それをバグなしに一気に書き換えることは難しいでしょう。アプリに強いメンバーが複数人居るのでなければここで時間を溶かすべきではありません。プロファイルしながらなら、一部の特に重い部分だけをチューニングして先に進むという判断もしやすいはずです。
例えば AddIsu の椅子の数は、DBに保存するときは文字列、合計を計算するときは bigint になるので、毎回変換が必要になります。メモリ上にこれらを bigint のまま載せるだけで高速化が期待できます。
DBへの書き込みを無くす必要はありません。ただし Python や php だとスレッドプールや Deferred 地獄を削って Ruby, Perl と同じにした方が、並行処理が無くなるので部屋ごとのロックの必要がなくなって楽になります。
もしDBの書き込み待ちでCPUが使い切れなくなってくるようであれば、プロセス数をCPUコア数と同じ2から3に増やすとか、MySQLを各サーバーで動かすなどの対策が取れるはずです。
もちろん、MySQLを使わず部屋の状態をシリアライズして保存しても構いません。
ステータス計算は addIsu や buyItem の結果として実行することが多いのですが、その処理が反映された状態のステータスを返さないといけないので、古い状態を返してしまうと fail するのです。
ここで予選を思い出してみましょう。少し sleep を入れることで、同じ部屋の複数のメッセージをまとめてから一気にクライアントに送ることができました。
今回も addIsu や buyItem の後に非同期な (他の WebSocket 経由のリクエストを実行できる) sleep を入れてやります。その後、キャッシュされたステータスが sleep 前の時刻より新しければそのキャッシュを返すことができます。キャッシュされたステータスが古い場合は計算しないといけないのですが、その計算結果は sleep 中の他のリクエストの結果もまとめたものにすることができているはずです。
試しに 0.2 秒の非同期 sleep を入れた所、先ほどと同じ構成で 100199点になりました。ここまでくれば優勝ラインです。
なお sleep 以外にも calcStatus を別スレッドや別プロセスに逃がして結果を待つようにするなどの方法があります。 複数の addIsu や buyItem 後の calcStatus をまとめて計算するのが本質なので、それを実現できるなら方法は問いません。
ただし sleep を使う方法はベンチマーカー側の攻撃ループを待たせて全体の負荷を下げる副作用もあるので、タイムアウトを発生させることなくCPU使用率があまるくらいにチューニングが進んでから sleep 時間を減らしていくという調整ができます。 sleep を使った方法は純粋にシンプルでバグを埋め込みにくいのと、この負荷調整の効果も期待できるので、個人的には一番おすすめです。
初期実装ではそのまま10進数文字列にしてから先頭15文字を切り出し、残りの文字列長を計算しています。これは、例えば椅子の数が10の10万乗になると、10万桁程度の文字列を作ってから先頭だけ取って残りを捨てているようなもので、とてももったいないです。
これは例えば、2の10乗が10の3乗より少し大きいことを利用して、次のような高速化ができます。
この方法ではわざわざ10のn乗を作って除算していますが、チームメイトに数学に強いメンバーがいればもっと上手い計算方法があるかもしれません。
この高速化を思いつかなかった場合も、 JSON の構造をよく見てみると指数表記が椅子の数と総生産力だけでなく、各アイテムの価格と生産力にも使われていることがわかるはずです。これはアイテムの個数で決まった値になるので、指数表記に変換した結果をキャッシュすることもできたかもしれません。
なお、 addings の合計までを実装した Python 実装（ただし手抜きで永続化はしていない）を python-optimized ブランチで公開しておきました。参考スコアとして、本選と同じ環境で、4台で各2プロセスに分散すると18万点台を出しました。
もっとアグレッシブに、永続化をルールから外し、初期実装からオンメモリにするくらいにしてしまったほうがちょうどよいバランスになっていたと思います。そうすれば競技後の検証プロセスも減らせましたし、参照実装の各言語移植者の負担も大幅に減らせたはずです。
また、非常に重い計算処理があるにもかかわらず、想定通りにキャッシュしてくれるチームがなかったのも残念でした。キャッシュ自体は簡単なはずですが、ロジックが複雑だったためにそこで一度 fail にハマると、キャッシュするのに臆病になってしまうチームが多かったのだと思います。初期実装でも buyItem や addIsu とそのあとの getStatus は別トランザクションになっていて、キャッシュすることで何か整合性が損なわれることはないことが明らかになっていたのですが、もっと分かりやすいヒントが必要だったかもしれません。
この辺の難易度調整は、出題側は「こんなに重いんだから複数の有力チームはキャッシュ試してくるだろう」という思い込みがあるうえ、スケジュールが厳しいと優勝候補レベルの協力者に難易度調整済みの問題でリハーサルしてもらうのが難しいので、予選と本選の出題が１チームで間が１ヶ月しか無いとなかなか難しいものがあります。
出題メンバーでは、中心になって動いてくれた一番の功労者である @mecha_g3 さん、消される前提で deferred 地獄な php コードを書いてくれた @___Johniel さん、エッジの効いた問題を作ってくれた @hasi_t さん、楽しいゲーム画面を用意してくれた @halt さんと @hnw さん。
WebSocket + MySQL + 多倍長整数という難題を、厳しいスケジュールで各言語で実装、レビューしていただいた、 @L_e_k_o 様、@mix3様、@ykzts様、@kamipo様。
大量のサーバーをセットアップしてくれたインフラ担当の @kizkoh 様、 yokogawa-k さん。
運営していただいたLINE株式会社の櫛井様と三木様。
インフラを提供していただいたさくらインターネット株式会社と、サポートしていただいた横田様。
そして度重なるトラブルを辛抱して参加して下さった競技者の皆様。
皆様のお陰でISUCON7を成功させることができたことを感謝します。
すでに Twitter でアナウンスされているとおり、本選の問題を Github で公開しています。
▼isucon/isucon7-final
すでに一週間以上経ってしまいましたが、この記事では本選の問題設計や攻略ポイントについて解説していきます。
お題について
予選では、夏期講習参加者や過去問を練習してきてくれた学生チームにいじわるな問題設計にならないようにと考えていました。（残念ながら失敗していた部分も多かったですが）一方本選では、そういった気遣いを一切無視して自分たちの得意な分野の問題を出そうということで、MOゲームをお題に選びました。
「協力してレイドボスを殴るゲームにしようか。」
「ボスのヒットポイントは無限にして総与ダメージをスコアにできないかな。」
「攻撃スキル、バフ／デバフスキルみたいなのはコード量を大幅に増やす割にISUCONとして面白くないから、もっとシンプルなルールが良いよね」
「あれ、クッキークリッカーってレイドボスになるんじゃない！？」
という流れで Chair Constructor Online にすることになりました。
自分たちの得意分野をやるということで、WebSocketを使ってマルチプレイ対応することまでは考えていましたが、ボトルネックをどう作り込むかなどはアイデア時点では考えていませんでした。
アイデア段階では存在しなかったタイムスタンプや未来に反映されるコマンドを使った同期といった難しい部分は、予選期間中にお題のゲームのプロトタイプを作ってくれていた @hasi_t が作り込んでくれました。
オンメモリ戦略と分散構成
ISUCON を攻略するテクニックの1つとしてオンメモリ戦略があります。この名称は自然発生したものできちんとした定義は無いものの、私の理解では次のような方法です。ISUCON参加者の中にはオンメモリ戦略を嫌う方もいます。
その理由は次の2点が大きいと思います。
しかし今回の問題は明確にオンメモリ戦略が有効な問題でした。それで問題ないと判断したのは次の理由です。
今回のクライアント（Webアプリ、ベンチマーカー共に）は、APIが返したホストとポートに対して接続するように実装されており、例えば部屋名のハッシュ値などをもとに接続先を指定してやることで、動的なリバースプロキシなどを作ることなく簡単に部屋毎に接続するプロセスを固定することができました。
そうなると、むしろシングルスレッドで動いている言語の方が、排他制御などを考えなくて良い分Goより楽な部分も出てきます。
本選では言語間の公平性はあまり重視していなかったものの、ここだけはGoが圧倒的に有利にならないように配慮しました。
WebSocketと非同期I/Oについて
WebSocketを利用するお題でなおかつオンメモリ戦略が有効ということで、通常の prefork 型のWebサーバーは利用できません。さらに（少なくとも初期実装では） MySQL へアクセスもする必要があります。Goやnode.js (本選では async/awaitを利用) にとってはこれは得意分野ですし、Pythonもスレッドプールを利用することで比較的上手く解決していますが、 php は deferred/promise 地獄になっていますし、 Ruby と Perl はMySQLアクセス中にWebSocketの処理がブロックしてしまう状態になっていました。
ただし、想定解法ではMySQLのアクセスは序盤で排除する前提でした。なので、この部分が苦手な言語ほど早い段階でMySQLを捨てる決断ができたのではないかと思います。
攻略ポイント
Python 版実装をベースにチューニングポイントを解説していきます。calcStatus() の後半部分の高速化
最初の状態で遅いのは calcStatus() 関数です。この関数は前半で現時刻までの addings と buyings から現在の椅子の数と生産力を計算し、後半ではこれから先1秒間のスケジュールを計算します。前半部分もあとでチューニングしますが、せっかくユニットテストが用意されているので、関数のAPIを壊さずにチューニングできる部分を優先します。また、この最適化はオンメモリ化の判断の前に可能な部分でもあります。
この中でチューニングが簡単かつ効果が大きいのは、アイテムの価格と生産能力のキャッシュと、 on_sale の計算部分です。
価格と生産能力はマスターデータから同じ形の計算式を使って計算しています。アイテムのIDと生産個数をキーにキャッシュするとシンプルですが、ユニットテストは別のマスターデータを使っているので、最初は計算部分だけをキャッシュするとユニットテストを壊すのを遅らせることができます。例えば Python だと次のようになるでしょう。
+from functools import lru_cache
+
+@lru_cache(100000)
+def _calc_item_status(a, b, c, d, count):
+ return (c * count + 1) * (d ** (a * count + b))
+
+
def calc_item_power(m: dict, count : int) -> int:
"""アイテムマスタ m から count 個目のそのアイテムの生産力を計算する"""
a = m['power1']
b = m['power2']
c = m['power3']
d = m['power4']
- return (c * count + 1) * (d ** (a * count + b))
+ return _calc_item_status(a, b, c, d, count)
@@ -68,7 +75,7 @@ def calc_item_price(m: dict, count : int) -> int:
b = m['price2']
c = m['price3']
d = m['price4']
- return (c * count + 1) * (d ** (a * count + b))
+ return _calc_item_status(a, b, c, d, count)
on_sale の計算は、1000回ループの中で、さらにアイテムの種類数 (13) のループで実装されています。まだ買えないアイテムを安い方からチェックすれば、13000回のループを約1000回に抑えることができます。
他にも、言語ごとに異なる重い部分があるかもしれません。多倍長整数演算が入っているためにどの部分が重いのかが見た目からの直感と反する事が多いはずなので、ちゃんと大きめのテストデータを用意して、（自作でも、ベンチマーク終盤の入力を保存＆リプレイでも可）プロファイルを取りながら最適化しましょう。
例えば1000回ループは buyItem や addIsu が発生した時間の回数分のループに書き換えることができますが、それをバグなしに一気に書き換えることは難しいでしょう。アプリに強いメンバーが複数人居るのでなければここで時間を溶かすべきではありません。プロファイルしながらなら、一部の特に重い部分だけをチューニングして先に進むという判断もしやすいはずです。
部屋ごとの分散
Pythonの場合はマルチコアを利用できないので、 5000, 5001 番ポートで1つずつプロセスを立ち上げるように設定します。/room/{room_name} のハンドラで、部屋名から一意に決まる方法で分散します。最適化が進むと部屋数が増えるので綺麗に分散する必要はないと思います。オンメモリ化
部屋ごとに接続先プロセスを固定する分散方式を実装すれば、どの言語でも部屋の状態を簡単にオンメモリ化できます。例えば AddIsu の椅子の数は、DBに保存するときは文字列、合計を計算するときは bigint になるので、毎回変換が必要になります。メモリ上にこれらを bigint のまま載せるだけで高速化が期待できます。
DBへの書き込みを無くす必要はありません。ただし Python や php だとスレッドプールや Deferred 地獄を削って Ruby, Perl と同じにした方が、並行処理が無くなるので部屋ごとのロックの必要がなくなって楽になります。
もしDBの書き込み待ちでCPUが使い切れなくなってくるようであれば、プロセス数をCPUコア数と同じ2から3に増やすとか、MySQLを各サーバーで動かすなどの対策が取れるはずです。
もちろん、MySQLを使わず部屋の状態をシリアライズして保存しても構いません。
ステータスのキャッシュ
まだまだ calcStatus が遅いので結果をキャッシュしたいところですが、問題があります。ステータス計算は addIsu や buyItem の結果として実行することが多いのですが、その処理が反映された状態のステータスを返さないといけないので、古い状態を返してしまうと fail するのです。
ここで予選を思い出してみましょう。少し sleep を入れることで、同じ部屋の複数のメッセージをまとめてから一気にクライアントに送ることができました。
今回も addIsu や buyItem の後に非同期な (他の WebSocket 経由のリクエストを実行できる) sleep を入れてやります。その後、キャッシュされたステータスが sleep 前の時刻より新しければそのキャッシュを返すことができます。キャッシュされたステータスが古い場合は計算しないといけないのですが、その計算結果は sleep 中の他のリクエストの結果もまとめたものにすることができているはずです。
試しに 0.2 秒の非同期 sleep を入れた所、先ほどと同じ構成で 100199点になりました。ここまでくれば優勝ラインです。
なお sleep 以外にも calcStatus を別スレッドや別プロセスに逃がして結果を待つようにするなどの方法があります。 複数の addIsu や buyItem 後の calcStatus をまとめて計算するのが本質なので、それを実現できるなら方法は問いません。
ただし sleep を使う方法はベンチマーカー側の攻撃ループを待たせて全体の負荷を下げる副作用もあるので、タイムアウトを発生させることなくCPU使用率があまるくらいにチューニングが進んでから sleep 時間を減らしていくという調整ができます。 sleep を使った方法は純粋にシンプルでバグを埋め込みにくいのと、この負荷調整の効果も期待できるので、個人的には一番おすすめです。
指数表記変換の高速化
calcStatus の回数は大幅に減りましたが、まだまだ重いのがここです。特に多倍長整数を10進数の指数表記に変換する計算が重いです。初期実装ではそのまま10進数文字列にしてから先頭15文字を切り出し、残りの文字列長を計算しています。これは、例えば椅子の数が10の10万乗になると、10万桁程度の文字列を作ってから先頭だけ取って残りを捨てているようなもので、とてももったいないです。
これは例えば、2の10乗が10の3乗より少し大きいことを利用して、次のような高速化ができます。
+@lru_cache(100000)
+def exp10n(n):
+ return 10**n
+
+
# JSON中で利用する10進指数表記
# [x, y] = x * 10^y
def int2exp(x: int) -> (int, int):
- s = str(x)
- if not s:
+ if not x:
return (0, 0)
+
+ b = x.bit_length()
+ d = b // 10 * 3
+ e = d - 17
+ k = 0
+ if e > 0:
+ k = e
+ x //= exp10n(e)
+
+ s = str(x)
if len(s) <= 15:
- return (x, 0)
- return (int(s[:15]), len(s)-15)
+ return (x, k)
+ return (int(s[:15]), len(s)-15+k)
この方法ではわざわざ10のn乗を作って除算していますが、チームメイトに数学に強いメンバーがいればもっと上手い計算方法があるかもしれません。
この高速化を思いつかなかった場合も、 JSON の構造をよく見てみると指数表記が椅子の数と総生産力だけでなく、各アイテムの価格と生産力にも使われていることがわかるはずです。これはアイテムの個数で決まった値になるので、指数表記に変換した結果をキャッシュすることもできたかもしれません。
その他
現在時刻までの addings を合計しておくというのも簡単で効果があります。buying も adding のように現在時刻までの処理をまとめることができますが、そちらは影響範囲が大きいので競技時間中に実装するのは難しかったと思います。なお、 addings の合計までを実装した Python 実装（ただし手抜きで永続化はしていない）を python-optimized ブランチで公開しておきました。参考スコアとして、本選と同じ環境で、4台で各2プロセスに分散すると18万点台を出しました。
反省点
オンメモリ戦略を早めに取ったほうがいい問題だったのですが、その判断に時間がかかってしまうチームが多かったのが残念でした。もっとアグレッシブに、永続化をルールから外し、初期実装からオンメモリにするくらいにしてしまったほうがちょうどよいバランスになっていたと思います。そうすれば競技後の検証プロセスも減らせましたし、参照実装の各言語移植者の負担も大幅に減らせたはずです。
また、非常に重い計算処理があるにもかかわらず、想定通りにキャッシュしてくれるチームがなかったのも残念でした。キャッシュ自体は簡単なはずですが、ロジックが複雑だったためにそこで一度 fail にハマると、キャッシュするのに臆病になってしまうチームが多かったのだと思います。初期実装でも buyItem や addIsu とそのあとの getStatus は別トランザクションになっていて、キャッシュすることで何か整合性が損なわれることはないことが明らかになっていたのですが、もっと分かりやすいヒントが必要だったかもしれません。
この辺の難易度調整は、出題側は「こんなに重いんだから複数の有力チームはキャッシュ試してくるだろう」という思い込みがあるうえ、スケジュールが厳しいと優勝候補レベルの協力者に難易度調整済みの問題でリハーサルしてもらうのが難しいので、予選と本選の出題が１チームで間が１ヶ月しか無いとなかなか難しいものがあります。
終わりに
トラブルも多く、参加者、関係者に多大な迷惑をかけてしまいましたが、なんとか出題担当という大役を果たすことができました。出題メンバーでは、中心になって動いてくれた一番の功労者である @mecha_g3 さん、消される前提で deferred 地獄な php コードを書いてくれた @___Johniel さん、エッジの効いた問題を作ってくれた @hasi_t さん、楽しいゲーム画面を用意してくれた @halt さんと @hnw さん。
WebSocket + MySQL + 多倍長整数という難題を、厳しいスケジュールで各言語で実装、レビューしていただいた、 @L_e_k_o 様、@mix3様、@ykzts様、@kamipo様。
大量のサーバーをセットアップしてくれたインフラ担当の @kizkoh 様、 yokogawa-k さん。
運営していただいたLINE株式会社の櫛井様と三木様。
インフラを提供していただいたさくらインターネット株式会社と、サポートしていただいた横田様。
そして度重なるトラブルを辛抱して参加して下さった競技者の皆様。
皆様のお陰でISUCON7を成功させることができたことを感謝します。
