学生枠、今までありがとう #ISUCON9
ISUCON9予選突破できたのでブログ書いてます
３年連続ISUCON本戦出場！！！ https://t.co/2wzmSTVMiS
— nakario (@nakario_jp) 2019年9月8日
今年から学生枠が無くなって、去年の予選の順位的に本戦出場はぶっちゃけ無理だと思ってました
盛大に砕け散って学生枠の再開を声高に主張するつもりだったのに……
本題ですが、僕はチーム（百万円ドリブン）の中では一番Goに慣れているということもあってアプリのコードの変更をメインで担当しています
やったことを時系列順で簡単に書くと
- pprofを仕込む(10:20)
- getCategoryByID のDBアクセスをなくす(12:40)
- getNewItems, getNewCategoryItems のN+1を解消する(14:30)
- なんか不要そうな FOR UPDATE を postBuy から消す(17:20)
- 上手くいくか怪しかったけど getItem からDBアクセスをなくす(17:40)
- もっと FOR UPDATE を大胆に消してみる→エラーが出たので大急ぎで戻す(18:05)
という感じです
最後ので戻せなかったら予選敗退してたのでマジ危なかった
つらつらと書きましたが、今回の最大の勝因はbcryptの計算専用に２台のサーバを使うという大胆な戦略を提案・実装してくれたチームメンバーのaokabi & murataにあると思ってます。感謝。
その他良かった点
- キャンペーン還元率に早い段階で気付けた（ISUCON8本戦でSNSシェア率による負荷コントロールの仕組みに気付けなかったので気をつけてた）
- pprof、pt-query-digest、netdata、alpなど複数のソースからボトルネックを判断した（過去問練習で見えてるボトルネックと原因が別の場所でハマった）
- 定期的に声掛けして方針を立てた（ISUCON7本戦で何時間も一人で悩み続けた反省）
- 大きいホワイトボードを用意した
- カレーを食べた
こうして見ると、学生枠で本戦に出場させてもらえた経験がとても活きているので、これからISUCONを始めようという人たちのためにも学生枠が廃止されたのは残念です
学生枠、今までありがとう
KMCとボードゲーム「超人ロック」 —— KMC Advent Calendar 2018
この記事はKMC Advent Calendar 2018 - Adventarの10日目の記事です。昨日はtetsutalow先生の担当でした。
KMCとボードゲーム
こんにちはこんにちは。KMC5回生のnakario(kmc-id: gnu)です。KMCでは昔はお絵かきなどをやっていましたが、最近はISUCONなど不定期イベントを除けばSlackとボードゲームしかしていないです。はて、コンピュータサークルである京大マイコンクラブでボードゲーム……？
実は、KMCは京大のサークルの中でもRPG研やシミュ研に次いで(？)ボードゲーム活動が盛んです。新歓コンパ、NF、春合宿などの大きなイベントで人が集まる時は必ずと言っていいほどボドゲで遊んでいます。サークルに置いてあるボドゲの数は正確には誰も把握していませんが100以上はあると思います。
超人ロック
単に「超人ロック」とだけ言えば聖悠紀先生による漫画のことを指します。今年で生誕50周年を迎えてなお続いている超長寿漫画です。人類が宇宙に進出した未来、作中屈指の超能力と永遠の命を持つ主人公ロックが色々な時代・惑星で事件に巻き込まれたり他のエスパー達と戦ったりという感じの王道スペースオペラです。
ボードゲームの超人ロックは、この漫画を原作としてエポック社が30年以上も前に発売したもので、各プレイヤーが作中のキャラクターになりきり、自分の正体を隠しつつ、各々の勝利条件を満たすためにESP能力や兵器を駆使して戦闘したり、惑星や秘密基地を探索したりというゲームです。ゲームシステムが秀逸で、ルールの修正や大胆なキャラクターの追加などの変化を経てKMCロック、RPG研ロック、名大ロックなどの独自の進化を遂げて今でも遊ばれ続けています。
このゲームの面白いところは、なんと言っても正体の騙し合いです。原作ではESP能力により外見上は完全に他人になりすますことが出来るのですが、ボードゲームのシステム上では最初から公開の「シルエットカード」と自分だけが確認して伏せておく「正体カード」として再現されています。あまり強力なESP能力やキャラ固有能力を使ってしまうと敵陣営のエースに各個撃破されてしまうので能力を隠したり、味方のふりをして団体行動しつつ肝心なところで裏切ったりといった駆け引きがコミュニケーションを生み、皆でワイワイ盛り上がれるのがサイコーに楽しいです。
また、強力なキャラクターで強力なアイテムを引いた時の俺TUEEE感、かといって多対一に持ち込まれたりダイスの出目次第で窮地に追い込まれるゲームバランス、死んだはずのキャラクターが突然生き返ったりエース級のキャラクターが地形効果で死にかけたりといったハプニングなど、何度遊んでも異なった展開になるところも他のゲームにはなかなかない良い点だと思います。
ただ、なにせ発売が30年以上前なので、当然絶版となっていたのですが、なんと来る12月21日に国際通信社よりリメイクされて発売されます！！めでたい！！！一家に一台是非買いましょう！！！！
超人ロック【CHARACTER BOARD GAME】 国際通信社
KMCでは11/24、25に開催されたゲームマーケット2018秋の先行販売で入手できたので既に何回か遊んでいます。普段はKMCロックのルールで遊んでいるのですが、これを機にオリジナルルールで遊んでみたところ、ゲームから除外されたり、無限に*1攻撃を反射可能といった強烈なカードがいくつかあったり、陣営ごとの人数比がかなり違ったりして新鮮でした。RPG研や名大のルールと比べるとオリジナルからの変更がだいぶ少ないとは言え、こういったあまりに苛烈な部分はしっかり修正さているのだと実感しました。なお、リメイク版ではこういった独自に発展してきたマイナールールを尊重するため、あえてルールに修正を加えていないとのことです。ルールの曖昧性で困ったり、このカード壊れ性能すぎる！と思った場合はぜひKMCロックのページをご覧ください。
プレイログ
実際のプレイの様子を軽く紹介します。今回のメンバーはgnu、drafear、yuma、jacker、siotouto、base64です。
すべてのキャラクターはロックと敵対し悪事をなそうとするEvil、ロックと共にEvilの秘密基地を破壊せんとするGood、それぞれ別々の勝利条件のもとに動くSpecialの3陣営に分類されます。KMCロックのルールではロック：その他Good：Evil：Specialの陣営ごとに1:0:2:2とランダム*2に1人正体カードを選びます。僕が引いたのは追加キャラクターであるリュカーンでした。リュカーンは高い能力値に加えて強力なアイテムを最初から所持しているEvil陣営のエースとも言えるキャラクターです。
まずゲームの前編はEvilたちが悪巧みをしている秘密基地を探す惑星探索編です。僕はGoodキャラクターのシルエットカードを選択したのでGoodのフリをして惑星を探索します。惑星を探索するとエスパーを取り締まる警官と戦闘になったりトラップを踏んだりするのですが、たまにゲームを有利に進められるアイテムを拾えるので、歩いているだけで死ぬような虚弱な能力値キャラクターでない場合はGoodかSpecialのフリをすることが多いです。
探索していると「自分の正体露見」カードを引いてしまいました。これで自分がリュカーンであることは皆にバレてしまいました。せっかく高い能力地を持っているのでいろんなキャラのフリができたのですが、こうなっては仕方ありません。Evil陣営のエースとして仲間を集める役を果たします。
今度は「他人の正体判明」カードを引きました。これを使うと他人の正体を一人だけこっそり覗き見ることができます。これでdrafearの正体を見てみるとなんとロックのうちの一人である「テオ」でした。こんなに早く敵の親玉を発見できるとはついていますね。捨てる神あれば拾う神あり。
さらにさらに超強力なアイテムである「ニケ」を入手しました。これは能力値が高いほど有効活用できるカードなので、リュカーンとの相性は抜群です。もう怖いものなしです。
jackerさんが秘密基地の場所が書かれた「情報入手」カードを規定枚数入手したため後半の秘密基地編に突入します。秘密基地ではEvilシルエットを選択した人が重要拠点を裏向きに伏せて設置します。今回のEvilシルエットはsiotoutoさん一人のみなので、彼の好きなように配置できます。もしも彼の正体がGoodだった場合は破壊しやすいように隣接して設置することができるので、まだ正体を確認していない僕は少々不安です(まぁニケがあるので大抵なんとかなると思っていますが……)。
秘密基地では敵の親玉がdrafearだと僕は知っているので、ドシドシ戦闘を仕掛けていきますが、そこはさすが主人公らしく高い能力値を活かしてのらりくらりと逃げられ続け、４つある重要拠点のうち３つを破壊されてしまいました。最後の重要拠点を破壊されると負けてしまうため、重要拠点の上に陣取ってdrafearが来るのを待ちます。
いよいよ最終戦闘。僕とdrafearの他には僕の味方っぽい動きをしているyumaが戦闘に参加します。更にここで秘密基地編に突入してすぐ罠にハマって死んでいたbase64が「実は生きていた」のダイスロールに成功して復活してきました。何もせずにあっさり死んでいったので敵か味方かわかりませんが放置します。
yumaと協力しdrafearを殴ったところものの数ターンで倒せてしまいました。やはりもともとの能力値が高い上にニケを持っていたら怖いものなしですね。その間base64は静観を決め込んでいましたが、yumaが攻撃したところ固有能力「分解消去」を発動したのでbase64は「ジェシカ」というキャラクターに確定しました。彼女は能力値が全キャラ中最低で、勝利条件が「ゲーム終了時に独身男性キャラとパーティを組んでいる」というなかなか厳しい条件のため、かわいそうな子扱いされている不憫なキャラクターです。そんなわけで彼女を引いてしまった場合はゲーム終了直前まで息を潜めて、最後に独身男性に媚を売って勝たせてもらうのがセオリーなのですが、今回のbase64のムーブは実に素晴らしいと言わざるを得ません。
リュカーンは独身男性なのであとはジェシカとパーティを組めばみんなハッピーエンドだったのですが、僕の手札には相手の正体を見ることが出来る「接触テレパス」のカードが……。そしてKMCロックでは相手の正体を見ている場合勝利宣言を拒否されません。魔が差した僕はbase64に対し接触テレパスを発動、見事(？)ダイスロールに成功して僕とyumaは正体を見てしまいました。これにはbase64もブチ切れ。殆ど無いESP能力を駆使してyumaに殴りかかりますがあっさりいなされてゲーム終了。僕とyuma、あとは死んでいたsiotoutoさんがEvil陣営だったので勝利しました。可愛そうなジェシカ……。
と、超人ロックはこんな感じのゲームです。文章力と時間とスペースの問題でここでは語りきれないので、ぜひ一度プレイしてみてください。
KMCM
明日のアドベントカレンダーは同期のnonyleneさんの担当です。お楽しみに！
KMCは年齢・所属・所在地など問わず誰でも入部できます。ボードゲームを遊びたい人、ついでにプログラミングしたりお絵かきしたり作曲したりゲーム開発したりしたい人はぜひ例会にお越しいただくかメールでご連絡ください！
isucon8本戦に参加してきた
昨年に引き続きISUCON予選を突破した。去年はたまたま出場できた感が強かったけど、今回は結果的に学生枠２位で通ったのでちょっと自信は芽生えた。
ISUCONでの自分の役割はアプリケーション(Go)。去年は本当にコード書くしかできなかったけど、過去問を解きまくったのでデータベースも基本的な知識はついて全面的にロジックの改修はできるようになった。
競技開始まで
前日の新幹線の運行停止に巻き込まれたりしたものの、無事東京に到着して起床も成功。
開場前に会場に到着していい席を確保したあとは、Wi-Fiの設定したりリポジトリ作成したりKMCから同じく参加した別チームと談笑するなどして時間を潰した。
isuconやっていき pic.twitter.com/2DXbXTs8tE
— nakario (@nakario_jp) 2018年10月20日
準備も万端で時間の余裕もあり緊張がほぐれてきたくらいで競技開始時間。
去年も思ったけどISUCONはオープニングがすごく凝っててモチベめっちゃあがった。
問題の詳細は公式参照。
競技中のログ
開始〜11時：Dockerの操作に慣れておらずアクセスログやスロークエリログ、フレームグラフの生成にとまどる。
チームメイトのmurataがコンテナに入って無理やりフレームグラフを取ってくれたのでそれを確認。
GET /infoが処理時間の大半を占めているため、ここを調査。
よく読まなくても無駄にtradeを取ってきているのがわかったので、LIMIT 1を追加したら一気に5000点を突破して一位に躍り出た(数百点差で別の学生チームがいたので単にガチャに勝ったっぽい)。ここが当日のハイライト。
11時〜13時：Dockerに阻まれて色々データが取れないのでどこがネックになっているのか把握できず、とりあえずフレームグラフからログイン処理内の暗号化が重いようなのでTODOに書かれているBAN機能を実装することに。
(たぶんこの時点でCPU使用率が90%切ってたはずで、アプリケーションがネックでないので判断ミス)
実装できたもののスコア改善せず。
13時〜16時：この頃にはmurataとaokabiがDocker全排除に成功していたのでスロークエリログを確認すると、ローソク足の生成のための集計に時間がかかってるようだったので、別テーブルに予め計算結果を保存しておくことに。ここもCPUネック処理なので判断ミス。
明らかに遅そうなSQLだったのと解決策をサクッと思いついてしまったので食いついてしまった(その割に実装に時間がかかったのはcreated_atとSTR_TO_DATE(DATE_FORMAT(created_at, '%Y-%m-%d %H:%i:%s'), '%Y-%m-%d %H:%i:%s')の違いで一秒ズレたりズレなかったりするバグの解決に時間がかかったから)。
16時〜18時：htopを見てCPUネックじゃないことに気づく。過去の経験からデータベースのロックだと決めつけてしまった(判断ミス)。スロークエリログにも総ロック時間がとても長いクエリがあったため競技終了まで勘違いに気づけなかった。
その問題のロックが長いクエリというのが椅子のトレード関連のもので、トレードのロジックがめちゃ難しかったので途方に暮れている間に競技終了。雑にN+1を解消しようともしたけどバグが治りきらなかった。
反省点
- もろもろの計測環境が整う前に方針を決めてしまってるのでかなり時間を無駄にしている。特別賞に目が眩んだというのはある。
- 計測環境が整ってからも全体の情報を見ていないため、一つのソースから間違った判断をし続けてしまった。
- レギュレーション(仕様書)の読み込みが甘い。バルク送信は完全に気づいてなかった。ログの欠損のエラーが出たときもトレードに時間がかかりすぎているのが原因と(何故か)思い込んでた。
- チームメンバーが詰まってたり非効率的なことをしてそうな時の声かけが(去年よりはできてたものの)足りなかった。
SNSシェア機能には気づいていたものの、ALL or NOTHINGだと思ってたので10%だけ有効化するみたいなのはどっちみち思いつかなかったと思う。これは反省というよりも普段からABテストみたいな経験を積んでるかどうかの違いかと。
感想
去年に比べて成長しているものの、まだまだできることがあるなぁというのが大きい。ISUCONは奥が深い……。
学生なので交通費＋宿泊費もでるし昼夜のご飯も食べられるし、マジで最高のイベント。
運営＆協賛の皆様、お疲れ様でした＆ありがとうございました！
ISUCON7本戦に学生枠で参加してきた & こうしていれば優勝できたかもしれない方法
経緯
なんとなくで参加を決め、なんとなくでメンバー(@aokabit, @murata)を組み、なんとなく過去の予選問題を解いたりしていったところ、予選直前に解いたPixiv社内ISUCONにおける経験を活かし*1Cache-Control: publicをつけたところ、マシンを１台しか使用していないにも関わらず学生枠で予選突破できたので非常にラッキーでした。
isucon本戦出場決定したの嬉しすぎてサイゼで「やったーーー！！！」って叫んでしまった
— nakario (@nakario_jp) 2017年10月22日
本戦でやったこと
とりあえずNewRelicを入れたりgo-torchからFlameGraphを生成したりしてgetStatusがネックなのはひと目でわかりました。
中でもBigIntの掛け算が大きな割合を占めているので、雑にそれらを眺めてみたところ、new(big.Int).Mul(str2big(hoge), big.NewInt(1000))しているところが目立ったので、big.NewInt(1000)を使い回したり文字列の最後に+"000"した後str2bigで代用したりしたものの、あまり効果が出ず。他の掛け算は色々な場所に散らばっていて共通部分を見いだせず、なかなか取っ掛かりが見いだせないでいました。
@murata が同じくgetStatusで大きな時間を消費しているbig2expをやっつけてくれるらしいので、賭けに出てgetStatus全体をキャッシュしてみることに。
キャッシュにはgolang.org/x/sync/singleflightを使用しました。何も考えずにroomNameをキーにしてgroup.Doでラップしたところ、ドカンと並列数が上がってこれはいけるか！！？と期待したもののベンチマーク後の検証に失敗。流石にこうも簡単ではないかと思いつつもこの方針ですすめることに。
コードを眺めていると検証に失敗しているのはaddIsu、buyItemしているにも関わらずキャッシュを利用しているせいであることはすぐに判明しました。そこでそれらの直後にgroup.Forgetを仕込みキャッシュをクリアしたところ、スコアはもとに戻ってしまいました。ログを吐かせて確認したところgetStatusの呼び出しはほとんどがaddIsu、buyItemの後に行われているもので、serveGameConnの始めや500ミリ秒周期で現在のゲーム状況を送信する箇所での呼び出しは割合として低いものだったようです。
同期地獄
こういった状況を踏まえてsingleflightによるキャッシュを効かせるためにはaddIsu、buyItemの変更が加わった状態で複数GoルーチンでgetStatusの呼び出しを同時に行う必要があります。しかし、恥ずかしいことに、チーム内で１番Goに詳しいことを自負していながら、数が減ったり増えたりする複数のGoルーチンを同期させる方法を知りませんでした。今考えてみると知らないなりに色々やり方はあったと思いますが、競技中は焦りやらプレッシャーやら*2で全くアイデアが浮かんでこず、思いついた！と思っても負荷走行後のバリデーションに失敗し*3、適当にネットで検索してライブラリを見つけたものの本番で使ったことのないライブラリに手を出す恐怖から試しもせず*4、最終的に辿り着いたのがこのコードです*5。
for {
if time.Now().UnixNano() / int64(100 * time.Millisecond) / int64(time.Nanosecond) % 5 == 1 {
break
}
time.Sleep(100 * time.Millisecond)
}
何をしているのかというと、現在時刻を100ミリ秒単位で数えて、その数字を5で割った余りが1の場合ループを脱出し、そうでない場合100ミリ秒スリープしてループする、という超原始的な同期を行っています。何時間もかけて最終的に出てきたのがこれって……。
しかしこの変更により3000近く*6だったスコアが初めて一万点を超え、競技終了時間も迫っていたので最終的にこれをベースに複数台に分散した実装で提出。ちなみに最終スコアは7248で一台のほうがスコアが良いという残念な結果に。書きながら思い至ったのですが3台のアプリサーバと1台のDBサーバでこれを行うとDBのロックタイミングまでもが同期されてスコアが悪くなるのは当然ですね……。
複数Goルーチンを同期させる方法の正解(?)
syncパッケージのCondに生えているBroadcastを使用します。
詳細はこちらにあります。
簡単に説明すると、各roomごとにGoルーチンを起動して、time.NewTickerによって定期的にcond.Broadcastを呼び出し、cond.Waitで待機していたgetStatusWithGroupを複数同時に起動します。この関数はsingleflightのgroup.DoでgetStatus関数をラップしただけのもので、複数同時の呼び出しを一回の計算のみで処理できます。
この変更を再現環境*7にて検証したところ、初期実装の4000~6000点から14000~16000点まで跳ね上がりました。本番環境で一台で動かしたときの初期実装が4000点前後だったことを考えると、4台全て使えば優勝も狙えたので非常に悔しいです。
まとめ
標準パッケージの型ひとつ知っているだけで出来ることが大きく変わるので、普段から色々なコードを書くことで勉強することが大事だと思いました。あと本番はめっちゃ緊張するので精神力も大事ですね。お寺とかで修行を積んで出直します。