nakarioのほぼISUCONブログ

ISUCON出るたびブログ書く

ISUCON12予選突破できず無念

予選突破出来なかったけどせっかくなのでやったことを書きます。

僕はチーム「百万円ドリブン」では主にアプリケーションの修正をメインに担当していて、メンバーのaokabiとmurataはそれぞれnginxやmysqlなどのミドルウェア、なんか色々をメインに担当してもらってます。

スコアから書くと14205点でスコア再現性テストで失敗して失格でした。失格については再起動テスト含めて再現性の検証をやっている余裕がなかったので仕方ないとは思ってますが何がだめだったのかは謎のままです。

当日やったこととしては、いつもどおり一通りの計測手法を仕込んだあと、mysqlへの負荷が低すぎるということでsqliteの存在に気づいて、主にaokabiとmurataにsqliteのまま分散 or mysqlへの移行で水平スケーラビリティを確保してもらう方向で動いてもらいつつ、アプリケーションを改善していく方向でやっていました。

ただ、sqliteが通信のオーバヘッドがない分N+1が負荷になりにくいこととかが頭からすっぽ抜けていて、N+1を直したのにスコア変わらないなぁといった感じに空回りしていたなと後になって思います。また、sqlite3で動いていたwindow関数を使ったクエリをmysqlで動かしてみると「ONLY_FULL_GROUP_BYモードが有効だと非集計カラムを参照できない」といったエラーで動かないことが判明して、非効率的なサブクエリとのJOINでなんとか動かすみたいなことをしていたので、こういった情報をちゃんと予習できてなかったなと反省したり(むしろ何で今までのISUCONでこのエラーに遭遇しなかったのかが不思議)。

15:30ごろにaokabiとmurataがmysqlへの移行(/var/lib/mysqlの全置換によるinitialize時間の短縮)を完了してくれて、そこからは各々いつも以上のパフォーマンスを出せたのではないかと思いますが、さすがに時間が足りずスコアが伸び切りませんでした。mysqlサーバを3台用意しておいてinitializeのたびに向き先を変えて、今まで使っていたサーバの初期化を走らせておくっていう副案も抱えていたのでそれをやっても良かったかもですね。競技中はもっとまともな方法で解決できるはずと思っていましたが、たとえ異常な作戦でも有効ならばチャレンジしていく勇気がなければ百万円には届かないのかもしれません。

ISUCON11-priorやってみた

予選が近いので練習戦として isucon11-prior をチームでやってみました。解説記事は出ていないようだったので、答え合わせはできてませんが8割くらいは対処できたのではないでしょうか。

構成は以下のようにして、最終的に30,000点を超えるくらいのスコアで終了しました。

  • appサーバ x 2
    • AWS c5.large (2 CPU, 4GB Mem)
  • benchサーバ x 1
    • AWS c5.xlarge (4 CPU, 8GB Mem)

やったこと

  • 計測環境構築
    • 兎にも角にも計測しないことにはやることを決められないので、MySQLとnginxのログ設定を行い、golang実装にpprofからflamegraphを出力させます
    • 初期スコアはparallel=4で1,600点くらいだった気がします
  • デプロイスクリプトの用意
    • ローカルで作業したコードの変更をサーバに反映させて再起動するスクリプトを用意します
    • 実は去年まではサーバで直接作業したり一旦GitHubにpushしてサーバでpullしたりしてたのですが、他のチームに倣ってウチも導入しました
    • お手軽だし事故が減る一方、コードを一緒に見ながら議論するには一工夫必要だなと感じています
  • N+1の解消
    • MySQLのCPU負荷がネックなので、スロークエリログをもとにgetReservations、schedulesHandlerに仕込まれているN+1を解消します
    • この時点でbenchサーバの移行が完了した上で4,000かな?
  • nginxでstatic fileの配信
    • aokabiがやってくれました
    • スコアは大きくは変化しなかった(はず)
  • indexの追加
    • タイミングが分からないけど多分このあたり?
  • overbookingの解消
    • 負荷が増えてくるとcapacity以上に参加者の予約ができてしまうバグによってエラー減点が目立ってきます
    • 根本原因はcreateReservationHandler内でのtransactionにおける他のtransactionのcommit後の値の変化を考慮しないreadです
    • 取り組んでいる際にはトランザクション分離レベルをデフォルトのREPEATABLE READからREAD COMMITTEDに変更することでファジーリードを引き起こす方法で対処しましたが、後々でロックの取得後にtransactionを使わずに値をreadするだけで良かったのではと言われて「それやん!」となりました
  • schedulesHandlerの挙動をドキュメント通りに変更
    • ここらで、原因は最後までわからなかったのですがスコアが4000点付近に張り付いて動かなくなる現象が発生
    • GETリクエストばかりでPOSTが来なくなっており、得点計算かユーザの挙動に原因があると考えてドキュメントを読み漁る
    • 実装とドキュメントの齟齬を発見し、一般ユーザには空きのあるスケジュールのみを表示するように変更
    • 実装したものの点数に変化がなかったが、いつの間にか8,000点くらいになっていたので実は効果があったのかも
  • DBのmax connectionを設定
    • 点数が伸びないので場当たり的にやった
  • reservedカウントの管理オンメモリに移行
    • indexの追加とかもあったかも
    • 12,000点くらい
  • interpolateParams=true
    • 14,000点くらい
  • 2台構成に移行
    • アプリとDBで分割
    • parallel=20に変更したのもここ付近?
    • 24,000点くらい?
  • reservedのオンメモリ化をすすめる
    • 30,000点ちょい
  • (失敗)reservationのbulk insert
    • 一定間隔おきにためておいたreservationを一括でinsertする実装を追加しましたが、ベンチとの相性が悪かったのか点数は変わりありませんでした
  • (失敗?)json Encoderの置き換え
    • 公式のencoderとほぼ変わらなかった

感想

練習用に作られたものとして基本を抑えつつ、ボリュームもしっかりあってとても楽しめました!UIやパスワードまわりは大胆に手を抜きつつ、ISUCON要素をぎゅぎゅっと濃縮したような感じでした。

あたかも私がボトルネックなので変更してください!と言っているかのようにドキュメントに書いてあるID生成の部分は触ってないですし、ベンチサーバー側のメモリが溢れそうで負荷が増やせない感じだったのでまだまだ上は目指せそうです。こんなにやりがいのある問題を提供していただいて、本当に作問者の方々には感謝してもしたりないくらいです。

さて、まずは予選を突破できるよう、早寝早起きを頑張ろうと思います!

ISUCON10本戦5位でした&感想戦88000点

百万円ならず!悔しい〜〜〜!

チーム「百万円ドリブン」としてISUCON10に出場し、良いところまではいけたもののどの賞にも引っかからない5位でした。それでも過去最高の成績だったのでそこは嬉しかったですね。

本戦でやったことと、今回は感想戦の機会が公式から提供されたのでそこで最高約88000点を取れたときにやったことを書いていきます。

続きを読む

実力を発揮できたと感じるISUCON10予選(百万円ドリブン:21位)

ISUCONを始めてから4連続での本戦出場になる。前回までの予選では、意図せず難所を攻略できたおかげで通過できたという感覚が強かった。しかし今回は「ここが今最大のボトルネックだから、これを改善すれば大きく点数があがるはずだ」という認識を持ち、それを時間内に実行することが出来たために21位という成績を残せたと思う。今までの知識と経験が結実したという感覚は予選通過にもまして喜ばしい。
そんなISUCON10予選での判断と施策を振り返る。

続きを読む

学生枠、今までありがとう #ISUCON9

ISUCON9予選突破できたのでブログ書いてます

今年から学生枠が無くなって、去年の予選の順位的に本戦出場はぶっちゃけ無理だと思ってました
盛大に砕け散って学生枠の再開を声高に主張するつもりだったのに……

本題ですが、僕はチーム(百万円ドリブン)の中では一番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の計算専用に2台のサーバを使うという大胆な戦略を提案・実装してくれたチームメンバーのaokabi & murataにあると思ってます。感謝。

f:id:nakario_jp:20190909223307p:plain
複数台化した時点(16:42)で跳ね上がってる

その他良かった点

  • キャンペーン還元率に早い段階で気付けた(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以上はあると思います。

そんなボドゲ大好きKMCですが、数ある中でも根強い人気を集めているボードゲームが「超人ロック」です。

超人ロック

単に「超人ロック」とだけ言えば聖悠紀先生による漫画のことを指します。今年で生誕50周年を迎えてなお続いている超長寿漫画です。人類が宇宙に進出した未来、作中屈指の超能力と永遠の命を持つ主人公ロックが色々な時代・惑星で事件に巻き込まれたり他のエスパー達と戦ったりという感じの王道スペースオペラです。

http://111.89.135.6/app-def/S-102/wp/wp-content/uploads/2014/08/cut_locke06-1.jpg
denkaba | 超人ロックとは

ボードゲーム超人ロックは、この漫画を原作としてエポック社が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のフリをすることが多いです。

f:id:nakario_jp:20181210230707p:plain
惑星探索編

探索していると「自分の正体露見」カードを引いてしまいました。これで自分がリュカーンであることは皆にバレてしまいました。せっかく高い能力地を持っているのでいろんなキャラのフリができたのですが、こうなっては仕方ありません。Evil陣営のエースとして仲間を集める役を果たします。

f:id:nakario_jp:20181210230704p:plain
身バレ

今度は「他人の正体判明」カードを引きました。これを使うと他人の正体を一人だけこっそり覗き見ることができます。これでdrafearの正体を見てみるとなんとロックのうちの一人である「テオ」でした。こんなに早く敵の親玉を発見できるとはついていますね。捨てる神あれば拾う神あり。

さらにさらに超強力なアイテムである「ニケ」を入手しました。これは能力値が高いほど有効活用できるカードなので、リュカーンとの相性は抜群です。もう怖いものなしです。

jackerさんが秘密基地の場所が書かれた「情報入手」カードを規定枚数入手したため後半の秘密基地編に突入します。秘密基地ではEvilシルエットを選択した人が重要拠点を裏向きに伏せて設置します。今回のEvilシルエットはsiotoutoさん一人のみなので、彼の好きなように配置できます。もしも彼の正体がGoodだった場合は破壊しやすいように隣接して設置することができるので、まだ正体を確認していない僕は少々不安です(まぁニケがあるので大抵なんとかなると思っていますが……)。

秘密基地では敵の親玉がdrafearだと僕は知っているので、ドシドシ戦闘を仕掛けていきますが、そこはさすが主人公らしく高い能力値を活かしてのらりくらりと逃げられ続け、4つある重要拠点のうち3つを破壊されてしまいました。最後の重要拠点を破壊されると負けてしまうため、重要拠点の上に陣取ってdrafearが来るのを待ちます。

いよいよ最終戦闘。僕とdrafearの他には僕の味方っぽい動きをしているyumaが戦闘に参加します。更にここで秘密基地編に突入してすぐ罠にハマって死んでいたbase64が「実は生きていた」のダイスロールに成功して復活してきました。何もせずにあっさり死んでいったので敵か味方かわかりませんが放置します。

yumaと協力しdrafearを殴ったところものの数ターンで倒せてしまいました。やはりもともとの能力値が高い上にニケを持っていたら怖いものなしですね。その間base64は静観を決め込んでいましたが、yumaが攻撃したところ固有能力「分解消去」を発動したのでbase64は「ジェシカ」というキャラクターに確定しました。彼女は能力値が全キャラ中最低で、勝利条件が「ゲーム終了時に独身男性キャラとパーティを組んでいる」というなかなか厳しい条件のため、かわいそうな子扱いされている不憫なキャラクターです。そんなわけで彼女を引いてしまった場合はゲーム終了直前まで息を潜めて、最後に独身男性に媚を売って勝たせてもらうのがセオリーなのですが、今回のbase64のムーブは実に素晴らしいと言わざるを得ません。

リュカーンは独身男性なのであとはジェシカとパーティを組めばみんなハッピーエンドだったのですが、僕の手札には相手の正体を見ることが出来る「接触テレパス」のカードが……。そしてKMCロックでは相手の正体を見ている場合勝利宣言を拒否されません。魔が差した僕はbase64に対し接触テレパスを発動、見事(?)ダイスロールに成功して僕とyumaは正体を見てしまいました。これにはbase64もブチ切れ。殆ど無いESP能力を駆使してyumaに殴りかかりますがあっさりいなされてゲーム終了。僕とyuma、あとは死んでいたsiotoutoさんがEvil陣営だったので勝利しました。可愛そうなジェシカ……。

と、超人ロックはこんな感じのゲームです。文章力と時間とスペースの問題でここでは語りきれないので、ぜひ一度プレイしてみてください。

KMCM

明日のアドベントカレンダーは同期のnonyleneさんの担当です。お楽しみに!

KMCは年齢・所属・所在地など問わず誰でも入部できます。ボードゲームを遊びたい人、ついでにプログラミングしたりお絵かきしたり作曲したりゲーム開発したりしたい人はぜひ例会にお越しいただくかメールでご連絡ください!

www.kmc.gr.jp

*1:壊れることがないという意味で

*2:ロック以外から

isucon8本戦に参加してきた

昨年に引き続きISUCON予選を突破した。去年はたまたま出場できた感が強かったけど、今回は結果的に学生枠2位で通ったのでちょっと自信は芽生えた。

ISUCONでの自分の役割はアプリケーション(Go)。去年は本当にコード書くしかできなかったけど、過去問を解きまくったのでデータベースも基本的な知識はついて全面的にロジックの改修はできるようになった。

競技開始まで

前日の新幹線の運行停止に巻き込まれたりしたものの、無事東京に到着して起床も成功。

開場前に会場に到着していい席を確保したあとは、Wi-Fiの設定したりリポジトリ作成したりKMCから同じく参加した別チームと談笑するなどして時間を潰した。

準備も万端で時間の余裕もあり緊張がほぐれてきたくらいで競技開始時間。
去年も思ったけどISUCONはオープニングがすごく凝っててモチベめっちゃあがった。

問題の詳細は公式参照。

競技中のログ

開始〜11時:Dockerの操作に慣れておらずアクセスログやスロークエリログ、フレームグラフの生成にとまどる。
チームメイトのmurataがコンテナに入って無理やりフレームグラフを取ってくれたのでそれを確認。
f:id:nakario_jp:20181027220646p:plain
GET /infoが処理時間の大半を占めているため、ここを調査。
よく読まなくても無駄にtradeを取ってきているのがわかったので、LIMIT 1を追加したら一気に5000点を突破して一位に躍り出た(数百点差で別の学生チームがいたので単にガチャに勝ったっぽい)。ここが当日のハイライト。

11時〜13時:Dockerに阻まれて色々データが取れないのでどこがネックになっているのか把握できず、とりあえずフレームグラフからログイン処理内の暗号化が重いようなのでTODOに書かれているBAN機能を実装することに。
(たぶんこの時点でCPU使用率が90%切ってたはずで、アプリケーションがネックでないので判断ミス)
実装できたもののスコア改善せず。

13時〜16時:この頃にはmurataとaokabiがDocker全排除に成功していたのでスロークエリログを確認すると、ローソク足の生成のための集計に時間がかかってるようだったので、別テーブルに予め計算結果を保存しておくことに。ここもCPUネック処理なので判断ミス。
明らかに遅そうなSQLだったのと解決策をサクッと思いついてしまったので食いついてしまった(その割に実装に時間がかかったのはcreated_atSTR_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は奥が深い……。
学生なので交通費+宿泊費もでるし昼夜のご飯も食べられるし、マジで最高のイベント。
運営&協賛の皆様、お疲れ様でした&ありがとうございました!