2017/12/04

ISUCON7 決勝に出ていろいろキャッシュ作戦を立てたけどダメでした

10月11月は大忙しプロジェクトで過ごしておりましてすっかりブログ書くのが遅くなってしまいました。ということでISUCON7決勝のお話です。

過去のfujiwara組最弱の座を返上するべくfujiwara組として出場してきましたが、結果としてはFAILということで、さらに最弱になってしまいアァ〜という感じです。まぁやったことのうち無事マージされた分については組長のところにかいてありますのでそちらを見ていただくとして、私がやっていったキャッシュ作戦について書いておきます。

だいたい「ここ重いからキャッシュしていこう」って言ったのは私なので、ざくざく書いていきます。

mItemsは変わらないからキャッシュ

みんな初手でやるヤーツですね。handlenameがサクッとやってくれました。

getStatusの結果をキャッシュする

goだと、serveGameConnという関数がコネクションごとのループになっており、こいつがWebSocketでやってくるコマンドメッセージを処理しつつ500ミリ秒ごとに現在のステータスを送っていくという感じになっています。

3台で分散してるとはいえ、来てるコネクションは結構多く、しかも部屋の数は(序盤ということもあり)全然多くない、ってことで、クソ重いcalcStatusがムダに呼ばれまくってる対策としてまず最初にこのtickerで返してるやつをキャッシュして同じ部屋にいるやつらには各コネクションに500ミリ秒ごとに更新されるキャッシュを返しましょう、というのをやりました。

ちなみにここでキャッシュを返す対象はtickerで回ってくるやつだけです。それ以外のはコマンドの結果が反映されてないものを返しちゃうとFailになるはず。

GetPowerとGetPriceをキャッシュする

getStatusをキャッシュしてもあんまりスコア上がらなくて、まぁcalcStatusが破滅的に重いししかたないよな〜ということで、gopsでプロファイリングしたところ、runtimeとbigが重いということがわかり、あーはい…みたいな感じになったので、bigの計算を削減していく方向でキャッシュをしていきます。

じゃあとりあえず商品の各レベルの値段とかパワーは変わらないのでこれ起動時にキャッシュしましょうかってことでhandlenameにおねがいしてやってもらいました。最初「とりあえずスコアアップしたあとのことを考えたら1000段階くらいまでキャッシュしとけばいいんじゃね」って言ってやってもらったんですが、13品目を1000回ループ回すとCPU張り付いていつまで経っても起動がおわらないという大ウケ状態になってしまったので、とりあえず50段階までキャッシュしました。

GetPriceとかの1000倍もキャッシュする

個人的に今回の問題でなんだこのクソ仕様(※クソ問題、ではありません)とおもったのが「1ミリ秒に生産できる単位を1ミリ椅子とする」ってやつで、これのせいでいろんなところにPowerを1000倍したりPriceを1000倍する処理が差し込まれておりました。とりあえずPriceとPowerをキャッシュできるんだからじゃあその1000倍の値もオンメモリにキャッシュねってことでそれもhandlenameにやってもらいましたが、中盤以降負荷走行後に謎の事後検証エラーが出ており結局これは最終版に入りませんでした。

ただとにかくMulは減らしたいと言うことで、文字列化した巨大数に+"000"してそれをBigIntにしましょうっていうアイディアを組長がだしてくれたのでとりあえずそれは入っています。

calcStatusの途中計算を全部キャッシュする

ぼくが2時間ぐらいかけてバグを潰しきれなくて結局マージできなかったやつがこれです。

当日の講評で @methane さんが言ってたキャッシュ戦略にも入ってましたが、私はとりあえず以下のような感じでキャッシュ戦略を考えました。

「Schedule[0]で返しているデータは未来のデータじゃなくて現在の確定したデータなので、このデータはキャッシュできる。このSchedule[0]を作るのに使ったデータを全部キャッシュすれば、それ以降はaddingとbuyingの差分だけ計算すれば次の時間のSchedule[0]を計算できるので、大幅に計算量が減ってブレイクスルーするはず」

ということで、totalMilliIsu, totalPower, itemBought, itemPower, itemBuiltおよびタイムスタンプで計算ステートのキャッシュを作る実装をやりました。

やりましたって言いつつ結局メインブランチにはマージできなかったんですが、その理由は最後までバグ潰しきったつもりだったけど事後検証エラーが出てたからでした。売れた個数とかが合わなかったりとかしてて、目を皿にしてももうわからーんみたいな感じで16時半くらいにギブアップしてブランチを放棄しました。

このキャッシュは実装難易度がだいぶ高くて、その理由はaddingやbuyingは未来のぶんもメソッドに渡ってきているので「キャッシュしていいadding」「キャッシュしてはいけないadding(未来のぶん)」「キャッシュしていいbuying」「キャッシュしてはいけないbuying(未来のぶん)」というのがあります。しかも、// buying は 即座に isu を消費し buying.time からアイテムの効果を発揮するっていうキャッシュ泣かせの仕様があってだいぶ苦労しました。

具体的には、buyingのtotalMilliIsuを差っ引いて返すというゲーム側の仕様は未来の時間に関係なく行われるので、Schedule[0]を計算しおわった時点のtotalMilliIsuをそのままキャッシュすると未来の支出の分まで減った状態の額がキャッシュされてお金が減りまくってしまうため、totalMilliIsuのうち未来のbuyingだけ別口でカウントしてキャッシュに入れるときだけ戻してあげるみたいな感じのキャッシュを作る必要があります。

あと、実際に動かしてみると15個しか売れてないはずなのにキャッシュ的には45個も売れたみたいなバグが出てきて、あーこれ同時並列系だなーってことでとりあえずルーム毎にmutex作ってcalcStatusがシリアルに動くようにする必要がありました。

とまぁそんなかんじでして、講評で @methane さんが「まずaddingをキャッシュして、それでだいぶブレイクスルーするのでそれで5万点はいくはず。さらなる高みを目指すならbuyingもキャッシュします」みたいな話をしてたので「オレいきなりさらなる高みを目指しすぎたか〜〜〜」みたいな感じでした。

で、最終的にはこのブランチを放棄したあとどうしたかというと、addingだけキャッシュしますね…ということでそういうブランチも作ったんですが、結局最終的にどうなったんだっけな。repoみるとマージされてないけど、組長にブランチ切り替えて動かしてもらってテスト通ってたのでそれだけ採用されてたような気もします。

ずっと「calcを軽く」ってダジャレ言ってたんですが成就しなくて残念です。

感想

アンケートにも書いた気がしますが、インフラの仕事がほぼなかった問題なので、組長をだいぶヒマさせてしまったな〜という感じです。組長は組長で全然別のアプローチで、Floatに丸めてもうまいこと通るんじゃねみたいなのをいろいろ試してたみたいでしたが、こちらも事後検証エラーでダメだったので結局投入できず。

結局の所問題の方向性というのは出題者のISUCON観が出るって感じなのかなと思うので今回はそういうISUCON観の人が作ったからこういう感じだったと思っています。ただ、そらはー氏とかが「つまらなかったな」みたいなことを言ってたのは理解できて、それを自分のISUCON観で言語化すると「ISUCONの醍醐味とか面白さって、高速化を進めていくとボトルネックがMySQLだったりネットワークだったりWebAppだったりメモリ容量だったりディスクIOだったりと色々なところに移り変わりまくって各メンバーの強みが各所で発揮されることだと思っていて、その点今回は終始ずっとWebAppのCPUチューニングしかやることがなかったので面白くなかったかな」ってことなのかなーと思っています。

全部キャッシュしきれば他の所がサチったりするらしいけどこの複雑怪奇プログラムを初見でそこまでもってくのはテストがあっても無理だ〜、というか、テストあってもキャッシュしたらどうせテストもメンテしないとテストが使い物にならなくなるのでどうしようもないっていう…。

ちなみに、私はこれまでプロトタイプ含めてGoやC#(.NET Core)でスマホ向けのリアルタイムゲームのサーバサイドを作った経験のある人間なので本当はこれ勝てないとダメなやつだったんだよな〜。ただ、このゲーム性にあの永続化ルールは本当に気が重かったです。インゲームが数分で終わって結果を集計して永続化しておわりっていう普通のソーシャルゲームだったら確実に最初から初手オンメモリでよかったんですが、クッキークリッカーのように終わりの無いゲームはインゲームの生存期間が無限なのでそれを既に永続化処理を実装済みのところからオンメモリにもっていって乗っけるか? って言われると私ははっきりNoという感じですね。

ちなみにPC向けオンラインゲームを作ってる人に話聞いてDBのコミットとかどういうタイミングでやってるの? みたいな話を教えてもらったりしたこともありますが、まぁその辺の知識を勘案してもちょっと今回の問題をいきなりオンメモリには持って行けないかなぁ…といった感じでした。まぁ今回の問題の高速化を業務でやるならオンメモリに持ちつつ同期になってるaddingとbuyingのDB書き込みをchanに投げて行って別goroutineでオフロードして書き込みしていくとかでしょうかね。いずれにせよそれだけだと行溜まりすぎ、計算量多すぎ問題の解決にはなってないのでそれだけでは勝てないのです。

ということで、みなさまお疲れさまでした〜。とりあえず弊社の初出場勢の別チームのMSAがいきなり優勝してビビってますが、これは来年出題側に回るフラグなのかな…? それでは来年もまたお会いしましょう。よいお年を〜

---

あ、そうそう、前回予選の記事でPOST /profileで投げこまれる画像のSHA1を全体で取るんじゃなくて先頭数KBで取るようにしてもなんかベンチがFailした! おかしい! みたいなことを書いておりましたが、後日予選のベンチマークにそういうの落とすためにPNGの後ろのメタデータのところにランダムな文字列が入るようになってるみたいな話を聞きまして、確認したところたしかにそうなってました。

講評でseedがランダムになってないのでちょっとミスったみたいなことは書かれていましたが、画像セット作るところで表パターンとメタデータを入れ替えた裏パターンを作っててそれを順番に回してたので、たしかに負荷走行はじまってしばらくして表データを使い切った後のタイミングでベンチが落ちるので、なるほど起きてた現象と一致しています。いや〜やられたな〜、IDATの後ろのメタデータでキャッシュできるように後ろ側もSHA1の対象に入れれば出し抜けたのにな〜みたいな感じです。