ISUCON7で優勝しました

まずは、素晴らしい問題と素晴らしい会場、素晴らしいインフラを提供してくれた運営に関わる皆様、本当にありがとうございました。
また、腰の重い僕を引っ張ってくれた会社の同僚の皆さんありがとう。

ISUCON7に同僚のmizkei とsuzukiとMSAで参加して優勝してきました。

勝因はこれです。


というのは冗談ですが、初参加のため過去の大会のことはわかりませんが、今回の問題は僕たちのチーム編成にとってとにかく相性が良かったというのが大きかったです。
チーム編成や基本的な作戦については下記の予選のブログに書いていますが、今回の問題はインフラはほとんど関係なく、膨大かつ複雑なアプリをどうするかみたいな感じで、手数を打てる僕らに有利だったと思います。

 

ken39arg.hatenablog.com

問題概要

決勝の問題はクッキークリッカーのソーシャル版で複数のユーザーでルームを共有できるというもの。
ポイントは以下

  • 扱う数字が64bitintの桁数を遥かに超える巨大な正数を扱うこと
  • サーバーは４台構成
  • 通信の殆どがWebSocketでルーム毎にサーバーを固定することが可能
  • 更新系アクションaddIsuとbuyItemの成功数がスコアに直結する
  • 参照系getStatusが重く1秒以内に結果を返せないとwsクライアントは切断する
  • websocket以外がアクセスするサーバーは予選同様チェックボックスで選べる

より詳しいことは本戦の問題が公開されたら見てください

事前準備

予選での反省を生かして本線ではモニタリングにmackerelを入れるだとか、静的型付け言語であるGoでも検知できないような文字列のタイポをしづらくするだとか、Redisを迷いなく使うための準備だとか、そういうのをするつもりでしたが、予選後に突然仕事が忙しくなってしまい何一つ準備することはできませんでした。

結局予選と同じchefを準備する程度のことはsuzukiがやってくれたようですが、予選とは異なり事前に集まったり、issueにメモしたりだとかは一切できませんでした。

あと、ノートとかホワイトボードを用意しようと思っていましたが、それすらも忘れてしまい、かろうじてsuzukiのカバンに入っていた病院の明細の裏が僕達のホワイトボードの代わりでした。

結果論ですが、そうしてノープランで挑んだことが、いつもどおりやるという結果につながり、そのいつもどおりがこの結果に繋がったと思っています。

やったこと

mizkei が既に書いているし、suzukiも書くだろうけど、何をやったのかをいろんな視点で見るのは興味深いと思うので僕も書いておきます。

ドキュメントをよむ
  • redisのincrby使うと良さそうだ！
  • 1ルーム1サーバーにしてスタンドアロンで完結できそうだ！
  • addIsuとbuyItemがスコアになる！
サーバーログイン〜環境準備

やること

  • まずサーバーに入って準備
  • mizkeiはコードリーディング

ログ

  • 自分のPCの.ssh/configを設定し `ssh isu{1..4}` でログインできるようにした
  • 10:30 用意したchefなどをgit pull (suzuki)
  • 10:30 webapp/go db以下をgit push (suzuki)
  • 10:42 isu1〜4の/etc/{nginx,mysql} を集めてgit push それぞれシンボリックリンクにする(ken39arg) → 一応shellコマンド
初期実行

やること

  • alpなltsvとslowlogを出し、golangでアプリを動かし最初のスコアを見る

ログ

  • 11:00 nginxのログフォーマットをltsvに変更(ken39arg)
  • 11:05 MySQLのスローログ設定(mizkei)
  • 11:08 初期設定のままisu1,isu2,isu3に向けてベンチ実行 Score:7211

感想

  • slowlog特になさそう
  • websocketのせいででaccesslog意味ねーみたいな感じでさらっと流す。
  • suzuki曰くdbがボトルネック

アプリ修正 その1

戦略

  • Redisのincrbyとか使え無さそうという初見であるが一応Redisを入れておこう
  • キャッシュ戦略を取りやすくするため1ルーム1サーバーにしよう
  • roomnameからの逆引きは、普段DBやredisをシャーディングする時の用にincrementな採番をして永続化できるようにroomnameをuniqにしてAUTO_INCREMENTなidを持つテーブルで行く
  • とりあえず明らかに無駄なクエリを削ろう

ログ

  • 11:40 deploy するためのmakefile作成(suzuki) ※ミスがあり12:35にfix
  • 12:02 getCurrentTimeはdb見ずに`time.Now().UnixNano() / time.Millisecond`に (ken39arg) Score:5103
  • 12:30 mitemは初期化時にmapにキャッシュ(ken39arg) Score:10401 ※ ただしこのスコアに再現性はなかった
  • 13:07 ルーム:サーバーの1:1対応 (mizkei) Score:9784 ※ Scoreは変化無いが後の戦略のためmerge
アプリ修正 その2

戦略

  • additem buyitem getscore で呼ばれるupdateroomtimeはオンメモリ管理に変更しforupdateのlockを削る
  • addIsuの確定スコアをdbに保存し過去分のスコア計算を削る
  • gzipとか基本的なnginxの設定見直しをしておこう

ログ

  • 13:25 nginxの設定変更 (suzuki) ※ スコア落ち不採用
  • 13:40 addIsuの確定スコアをDBで管理するのは難しいので諦めることにする(ken39arg)
  • 13:55 updateroomtimeのオンメモリ化 (mizkei) Score:4836 ※スコアが減ったのでmerge見送り

アプリ修正 その3

戦略

  • その2は全滅だったので冷静にpprofを取ろう
  • オンメモリ前提でキャッシュしDBはメモリ復元に使うことにする

ログ

  • 14:17 pprof (mizkei)
    → big.Int 周りをなんとかすべしな感じ
  • 14:36 ルーム毎の共有メモリと管理方法を確定(ken39arg)
  • 14:42 GetPower GetPriceをcount毎にcache(mizkei) Score:8654 ※スコアが減ったのでmerge見送り
  • 15:05 addingsをキャッシュし`INSERT ON DUPLICATE`,`SELECT FOR UPDATE`,`UPDATE`の3クエリをINSERT or UPDATE 1回で済むようにした (ken39arg) Score:7746 ※スコアが減ったのでmerge見送り
  • 15:29 nginx.conf のgzipstaticなどを間違いないのを修正(ken39arg) Score:9259
アプリ修正 その4

戦略

  • その3やその2で入れたキャッシュ関連の修正はどう考えても効かないわけが無いのに、なぜスコアが全く伸びないのかということに思い悩む
  • mizkeiがレギュレーションを読み直し、そもそもgetScoreを1秒間隔で返せなくなるとベンチが上がっていかないという記述に気づく。
  • これまでの変更は効果を発揮する前に足切りにあっていた可能性が高いということで、ダメ元でお互いのレビューでOKなものはmergeしつつ、getStatusを最適化していこうという話をする。
  • インフラ担当のsuzukiは暇させてしまっていたのでhttp2試しますみたいなことで、よろしくみたいなノリ

ログ

  • 15:47 14:42に見送ったGetPower GetPriceのキャッシュ化PRをmerge(mizkei) Score:7012
  • 15:57 13:55に見送ったupdateroomtimeのオンメモリ化PRをmerge(mizkei) Score:7921
  • 16:07 15:05に見送ったaddingsのキャッシュPRに確定addingsを纏めて総量を減らす変更を加えてmerge (ken39arg) Score:6404
  • 16:27 buyingsもオンメモリ化(ken39arg) Score: 8744
  • 16:31 getStatusでDBへの参照がきえたのでtxなどDBを触っているところをすべてなくす(ken39arg) Score:5773
  • 16:36 1000回loop内の`totalMilliIsu.Cmp`で使っている`new(big.Int).Mul(itemPrice[itemID], big.NewInt(1000))` をloopの外にだしloop内で初期化させないようにする(mizkei) Score:48745
アプリ修正 その5

戦略

  • isu1〜3のCPUが圧倒的に支配的になりDB担当のisu4がスカスカになったので、isu4にもwebsocketを向ければ多分特別賞超えられるからやろう
  • 再起動時にキャッシュを復元するのを据え置いていたが、50000を超えたらとりあえず復元に取り掛かろう
  • getScoreまだイケるところ無いか探ろう

ログ

  • 16:45 isu4にもwebsocketを2:2:2:1で向ける(ken39arg) Score:57103

  • 17:00 再起動時にキャッシュを復元 (ken39arg) Score:61750
  • 17:30 big.NewInt(1000)を、グローバルにもつ (mizkei) Score:63404
再起動試験そしてチャレンジ

戦略

  • とりあえず再起動試験をしてScoreを確実にしていこう
  • 他のチームも壁を作ってくる事を想定し優勝スコアは15万くらいと予測、その結果まだあげる必要があるだろう。
  • 予選では「チャレンジしない」と言っていたが決勝は「チャレンジしよう」ということで、最後の最後まで粘ることにする。

ログ

  • 17:45 logとpprofをけす(ken39arg) Score:62871
  • 17:50 最高スコア(たまたま) Score:65218
  • 18:00 getStatusにおいて結果をキャッシュし、最後の取得時間とcurrentTimeと比較し同じならキャッシュを返す(ken39arg) Score:49963 ※不採用
  • 18:18 最終スコア Score:64847
もっとこうしたかった

Schaduleという名前にあるように、addItem,buyItemのタイミングでreqTimeから1秒分のスケジュールを更新するという戦略をゴールにしていたら、getStatusのタイミングでは参照だけで済むようになり、1000回ループの回数を更新アクションの回数と一致させることができ、最低限に抑えることができたはずだと思う。

そこで２回めのブレイクスルーになるのだが、次第にaddItem,buyItemの処理に時間がかかるようになり、そこの改善という一歩先に勧めたと思う。

おそらくそこまで行ったら、今度はbuyItemをaddItem同様にitem毎にmergeするとcalcの計算がまた早くなりじわりとスコアが上がる。

最後はaddItem,buyItemがかなり短い周期で来るようになるのでbuyItem,addItem直後のスケジュール作成を止め、スケジュール更新キューみたいなものにぶち込んでいってその更新キューの間引き調整で最後はねるみたいなストーリーが待っていたと思う。

あくまでも勘であるが、、、

こうやって勝っても悔しさが残って後を引きづられる感じ、ISUCONって初めて参加したけどとっても素晴らしいものだったんですね！！

感想

途中までPRの効果を確認できなくて、マージできてなかったんだけど、アプリ担当の自分とmizkei の関係性から、お互いレビューしあって問題なければ結果が出なくてもマージしていくという決断をしたのは大きかった。

この辺は普段の業務でも同じチームでお互いレビューしあっているということの強みが本当に出た。

あと、予選は1人のミスをみんなで解決するみたいなロスがあったけど、ダメな時はレビューに丸投げして、また別のことに取り組むみたいないい意味の丸投げ体制が取れたのは良かった。

基本的に1回でいい処理は一回しかしないという普段から気をつけていることを黙々とこなした結果ブレイクスルーを踏めたから勝てた。

まあ、正直踏んだ修正が僕じゃ無くてmizkei だったのは悔しいけど、さっさとgamestatusの1000回ループを改善して、個別修正の効果を実感できるような流れだったらもっと楽しかった。

予選もそうだけど、基本的に普段やらないことはやらないで、やってることをガンガンやり、お互い信頼するというのができたのが良かった。

今回のようにpprof以外にすぐできる有効なボトルネック特定手段が無いようなときは、コードリーディングで確信は無いけどほぼ間違いなく効果があるであろうことにアタリを付けて、それを改善するということは業務でもよくある。特に小一時間で終わるような小さな修正に対して、いちいち絶対に効くか確認をするなんてことは大抵しない。影響が無いように小さな単位でPRしmergeしていくことでローリスクな手をたくさん打てる。

僕たちは普段からそういう感じでやっていることが多いので、ハイリスクなcalcStatusのアルゴリズム変更のようなトライをせずに、コツコツと積み重ねて結果を残せたのは今後の自信にもつながって誇らしく思う。

 

さて、これで私の所属するKAYACに４個目のトロフィーが届いたわけであります。

強さの秘密がどの辺にあるのかわかりませんが、受託サービス(主にキャンペーン)とゲーム、チャットサービス、その他自社サービスと多岐に渡るwebサービスを身近に感じられることや、3度優勝している人が身近にいるとか、まだまだ富豪的アプローチでじゃんじゃんお金で解決しますというわけにはいかないこととか、なんだかワチャワチャしているところが強さの要因かもしれません。

 

最後になりますが、取り急ぎ gistに最終的なコードを張っておきますね。