チームRedCompでISUCON6に参加しました

いい感じにスピードアップコンテスト(ISUCON)の第6回にチーム「RedComp」で参加しました!

isucon.net

RedComp

今回は一緒に仕事をしているtakyoshi & mizkeiとチームを組んで参加しました。
Redは赤でCompは粉です。
役割分担は

  • takyoshi : 下回り
  • mizkei : アプリ
  • rg_gs(私) : なんか色々

な感じでした。

やったこと

  1. azure VMs、repo準備
  2. index張る
  3. アプリ、DB統合
  4. htmlify対策
  5. さらばgolang

azure VMs、repo準備

マニュアル記載のテンプレートボタンをぽちっとして競技用のVMを用意。この機能すごい。
が、VMの起動中に焦って計測ツールのインストールやpub key配置用のスクリプトを動かしてしまい、プロビジョニングが中途半端に…
アプリが配置されなかったのでやり直し… 今度は焦らず再起動を待ち、初期状態でベンチ実行。初期はperl実装にベンチがかかり1800点前後。

アプリケーションをrepoに上げ、patchを当て… とこのくらいで大体11:00
アプリ担当のmizkeiはperl < goな人なので言語はgoを選択。
goはマニュアルに記載されていた初期実装ベンチが0点な言語でしたが、とにかくアプリ読んでから考えようということに。

index張る

mizkeiがアプリを読んでいる傍ら、データのバックアップをとったりついでにindexを張ったり。
とはいえDBは非常に小さく、最終的には

alter table entry add index updated_at(updated_at);
alter table star add index keyword(keyword);

くらいだった気がする。
ベンチは //keyword/:keywordタイムアウトしてしまいこの時点でも0〜200点くらい。不穏。

アプリ、DB統合

今回の問題で特徴的だったのはアプリケーションが複数存在し、httpによるデータ交換を行っている点でした。
作りは面白いのですが、特に別アプリになっているメリットがなく(笑)、ひとつのアプリに統合することに。

  • isuda側に /star を移動
  • star tableもisudaのDBに作成
  • nginxの設定からstarの分岐を削除
  • isutarのアプリ停止

等をやりました。
こういった変更はbranchを切って行い、ベンチマークの結果次第でmasterに取り込むかどうかを決める、というルールでやっていたのですが、この時点でもタイムアウトによる減点のためかスコアは0〜200点くらい…
この変更はとりあえず保留に…

htmlify対策

とりあえずスコアが出ないことには効いてるのかどうかもわからん!
ということで一番のボトルネックであるhtmlifyに着手。

  • keywordの長さでsortするクエリ対策のためにcolumnを追加
  • keywordの長さをscoreにしたsorted setを作成し、DBからentryを全取りしないように
  • regexp.MustCompile やばい!となってstrings.Replace

ここまでやってやっと1800点くらい。時刻は16:00くらい。つらい。
普段業務でgoを書けない鬱憤を晴らすかの如く、喜び勇んで手を動かしてたmizkeiもだいぶ意気消沈して来てたw

さらばgolang

結局のところperlの初期実装を超えられておらず、ボトルネックは文字列処理。
じゃあperl使えばいいじゃない
ということでmizkeiがgo書いてる裏でそれを私がperlでも実装。(私はperlのほうが得意)
結構諦め気味で最悪perlの初期実装を提出しようか〜www などと言っていましたが、sorted setからkeywordを取得するようにしたところでスコアが40000点くらいまで伸びISUCON始まった!(でももう17:00)
そこからisutarの統合やらnginxの調整やら大急ぎでやって、最終的には70000点位のスコアは見ることが出来ました。

結果・振り返り

スコア的に期待はしてなかったけどやっぱり結果は予選落ち、残念。
振り返るともっと早い段階でgo捨ててperlにしとけばよかったのでは?となりそうですが、そうでもない。
みんgo第一章にある通りgoの正規表現はパフォーマンスが悪いし、perlはそういうの得意だけど、問題のキモは正規表現の生成速度ではなく、その頻度を減らすことだったり更新後の参照可能性の担保。なので文字列比較やリンクとしての置き換えの回数自体を減らす方向でアプローチしていけばgoでもスコアは出せたんじゃないかなぁと思います。
とは言え初期実装がベンチ0点で、最大のボトルネックを取り去るまで進捗が見えないのはつらかった…

まとめ

今回もとても楽しく参加させていただきました。
問題も今までにない感じで面白かった!(はてなってすごいサービスなんだなぁと思ったり…)

誘ってくれたtakyoshi & mizkeiありがとうございました!
そして運営の皆さん、お疲れ様でした!本選も応援しています。

P.S.
みんなのGo言語買いました!まだちょっとしか読んでませんがとても良さげ。

ISUCON5本選に参加しました!

いい感じにスピードアップコンテスト(ISUCON)の第5回本選にチーム「chatzmers」で参加しました!

isucon.net

with @Maco_Tasu and @m0t0k1ch1

予選を無事に突破し、本選に参加してきました。

やったこと

問題の形式は

  • 各チーム3台のマシンが与えられ、その全てで同じアプリケーションが起動している
  • benchmarkは実行時に指定した1台に対して実行される
  • 3台すべてを使う必要はない

という感じです。
アプリの内容は予選よりも軽めで、幾つかの外部サービスAPIをユーザー指定のクエリで定期取得するというもの。
データ表示用の画面の他に、クエリ設定画面、ログイン/signup画面などが実装されていました。
初期ベンチは1000点前後。

とりあえず1台でkey-pairを作り共有。
全台にsshできるようになったところでnsshを利用してtool類を整備していきました。

postgresql -> mysql

この辺でアプリを眺めてた@MacoTasuが「mysql繋げない」と。
どうやらmysql-serverも動いてる気配がない…ってpostgre?! psqlわかんねーぞ…となりました。
slowクエリ見たりindex張ったり、my.cnf的なものはどれぞ?といろいろ不安を感じ、DBをpostgreからmysqlにしてしまおうと大きくかじを切りました。

「初期化されたpostgreからcsvを吐いてmysqlに流す。」と書くとまあ行けそうな感じがしたの。

結果としてはそんなにうまくいくはずもなく、csvの一部になったjson部分をシングルクオートで囲んだりしてた。(Vimのマクロは直感的で便利!!!)
データにはマルチバイトもあったので、csv吐くところか取り込むところあたりで文字化けにも悩まされてスコアを落とすことに…。これは結局どこで起きてたのかわからないまま終わってしまった。
initializeがpostgreの方にかかっていたり細かなミスもあって、一部文字化けしてるけどとりあえずmysqlでアプリが動いたのが15時くらい。

speedup

時間もない中tryしたこととしては

  • 外部APIのendpointのリストをキャッシュ
  • 認証の方式を変更
  • リクエストを1台のnginxで受けてアプリを2台に
  • etc.

初期実装ではsignup時に決定されるsaltとpasswordからsha-512で生成したhash値をDBに保存し、取得時には毎回postgreのdigest()で再計算していました。
ここの計算コストをカットするために単純にmailアドレスのドメイン部分をpasswordとして置き換えてしまい簡略化しました。(レギュレーション的にokなのか?)

あとは外部APIにリクエストするところが一番のネックになっていたので、ここを並列にしようとParallel::ForkManagerでざっくり書いて見るも結局うまく動かせず…。

そうこうしているうちに決定打を打てないままタイムアップとなってしまいました。

振り返り

migrate?

結果から振り返るとDBの入れ替えは良い選択ではありませんでした。
「migrationが思ったより詰まったなぁ」とか「いやそもそもpostgreももうちょいいじれないと…」というのもありましたが、本質的には今回の出題、DBはほとんどネックになっていなかったのです。

推測するな、計測せよ

ですね。

切り戻し

  • 変更は基本的に各自のbranchで
  • 多種の変更を同時に(同じbranchで)行わない
  • push前にbenchが実行中かどうかを確認
  • benchにfailしたもの、スコアが上がらなかったものはmasterに取り込まない

予選では割りとできてたことが全然できてなかったなぁ。
benchのfail率も予選に比べてかなり高くて、心やすまる時がありませんでした。殆どの時間fail見てた。
慌てていろいろやってたらいつの間にか外暗くなっててさらに焦ったり。

使用言語

chatzmersは予選と同様使い慣れたperlを選択しましたが、今回の出題ならgolangとかのほうがスコア上げやすいかなと思ったり。
なんにせよ問題見てからいろいろ選べるようだと強いですね。勉強しよう。
けど

sub hoge : lvalue {}

とか初見だったしperl力もまだまだ足りない…。

success

それでも予選の反省を活かして競技終了前に再起動試験を行い、結果としてはスコアを残すことができました。
激遅ですが僕らのサーバーはリクエストされたページを返します!
これができないと入社1年目に舞い戻ってしまいますのでsuccessできてよかったです。

まとめ

本選も楽しかった!
みんなで同じ会場に集まるのいいですね。ランキング眺めて一喜一憂したり。

練習も含めてISUCONを通してとても良い経験ができました。
出題/運営の皆様には感謝してもしきれません。

次回も参加して、もっとスコアをあげられるよう精進したいと思います。

ISUCON5 総合4位で予選突破!

いい感じにスピードアップコンテスト(ISUCON)の第5回予選にチーム「chatzmers」で参加し、無事に予選突破しました!

isucon.net

with @Maco_Tasu and @m0t0k1ch1

というわけで当日周辺の出来事、やったことなどを振り返りつつ戦いの記録を残します。

チーム結成〜前日まで

命名

実はあまりよく覚えていないが、いつの間にかメンバーになっていたらしい。
予選当日から一月程前に肉を食いながらチーム名を決めました。チーム名の由来などは@m0t0k1ch1の
ISUCON5 と chatzmers - 予選4位通過編 · m0t0k1ch1st0ry
を参照ください。'z'を付けたのは私です。
肉はうまかった。

この辺りで同時に当日までの各自の分担なども決め、参加申し込み&運営さんとのやり取り、slackのチームを作成、githubのprivate repo作成を行いました。

練習

ぶっつけ本番はまずかろうということで事前に練習を行いました。集まれたのは2回ほど。
練習方法としては、ISUCON4の問題がCloud Storageオブジェクトとして提供されていたためそちらを実際に解いていく形でやりました。ありがたや。
ふんわりと決めた私の分担範囲としてはアプリケーションに対する変更をdeployしたり、同時にbenchmarkを走らせたりという環境整備でした。
アプリケーションと同じホストでbenchmark toolを実行し、scoreを測定する仕組みが提供されていましたので、

  • 手元でブランチを切ってコード変更
  • githubにpush
  • web hookを使って本番でcheckout & pull
  • アプリ再起動
  • benchmark実行
  • 結果をslackに通知

といったあたりをpush以降自動で行えるように整備しました。
あまり触ったことがなかったsupervisorや概念自体は知っていたけど使ったことがなかったgithub web hookを実際に動かせたので良い練習になりました。
(slackのpost.Files APIのchannelsパラメータがchannel nameではなくchannel idを渡すものだというあたりに小一時間ハマったりしていた。)

前日

ほとんど寝ていた。

予選当日

準備

使い慣れた会社の会議スペースを借り、準備しました。
当日朝の #isucon をご覧いただくとわかるように、起床がISUCON参加者たちの最初にして最大の難関であります。幸いchatzmersは開始1時間前には全員が揃っており、無事に競技開始を迎えられました。

やったこと

まずは練習と同じくdeploy環境、benchmark環境を用意するということをやりました。repoは練習と同じものをディレクトリを切って使ったのでツール類はほとんどpathの書き換えくらいでしたが、systemd慣れしていなかったことと、benchmarkが専用のポータルサイトからリクエストする形式でしたので、pushしたらcheckoutするよ、というくらいのところまでになってしまいました。
systemdの設定ファイル見つけるのに手こずった…

この頃他の2人は

  • @m0t0k1ch1 : alp, pt-query-digest等のツールの準備
  • @Maco_Tasu : アプリを読みまくる

というような分担で進めていました。

この辺り、誰かが待ちになってしまうようなことなく、作業に入れたのは非常に良かったと思います。

一通り計測ツール、deploy環境が整ったあたりで@Maco_Tasuがめぼしいボトルネックを挙げ、それを分担して改善していきました。
問題のアプリは少し懐かしい香りのするSNSサイトでISUCON4に比べるとかなり重厚。ユーザー、フレンド、記事、コメント、足あとなどを主な機能とするものでした。

私は主に足あと周りとコメント周りを担当しました。
足あとはとりあえずuser_idにインデックスを張り、group byの無駄な指定を省きました。timestampをscoreにしてsorted setだなーというアイディアはありましたが、一旦保留に。
コメントは、redisを使って参照の高速化を図りましたが、mysqlから初期データを読み出すところでinitializeの時間制限に関するレギュレーションに違反してしまい、うまく行きませんでした。これと同時に足あとのsorted set案も諦めてしまいました。
答え合わせidobataでfujiwara組(予選総合1位)からaofで〜というのが出ててなるほど流石という感じ。AWSのElasticacheを業務で触ったときに一通り調べて知っていたはずなんですが、なかなかとっさには出てきませんでした…

さて、その他の具体的な実施内容は2人の記事が詳しいのでそちらに譲るとして…
ISUCON5 予選4位通過でした - 眠すぎて明日が見えない
ISUCON5 と chatzmers - 予選4位通過編 · m0t0k1ch1st0ry

方針、暗黙のチームルールっぽいもの

実はこの3人、新卒時に社内で行われたミニISUCONに(それぞれ別のチームで)参加したことがあります。その時は新卒勢は全員fail(記録なし)という散々な結果でした。
というのに加え、自社サービスの保守、運用を主な業務としているメンバーでしたので、不可逆な変更、大きな変更に対しては注意深くすすめる事ができました。

  • 変更は基本的に各自のbranchで
  • 多種の変更を同時に(同じbranchで)行わない
  • push前にbenchが実行中かどうかを確認
  • benchにfailしたもの、スコアが上がらなかったものはmasterに取り込まない

というようなことを違和感なく、スピードを落とすことなく実行できたのはプラスになったと思います。

一方で初期データの破損を恐れて、schemaの変更を避けたり、redisへの置き換えを早々に諦めたりしていたので、snapshotからの復元や別インスタンスを立ててバックアップとするなど、クラウドプラットフォームらしい可逆性の担保も視野に入っていればもう少し大胆な改修もできたかなぁというところです。

まとめ

ISUCON楽しい!
楽しかったです!8時間まるまる集中してて最後は本当にヘトヘトでしたが、ものすごく充実感がありました。
メンバーの2人も同じ会社とは言え一緒のプロダクトで関わったことがなかったので新鮮でした。ありがとう!

最後になりますが、このような素晴らしい場を作り上げて下さった運営の皆さん、本当にありがとうございました!

本選も頑張ります!

Can't save in background: fork: Cannot allocate memory [Redis]

子processがDBをdiskにdumpしようとした時,理論上は親processと同じだけのmemoryを食う.
けど最近のosの実装だとmemory pageを共有してくれる.
ただ,linuxは子processの処理が終わるまでそいつがどれだけmemoryを食うか判断できないから,親processと同じだけ食うものとして使用するmemoryを計算する.
そのためdatasetの容量よりもmemoryの空き容量が小さいとerrorになる.実際には更新部分の分しか食わないから大丈夫なはず.
overcommit_memoryという設定があってコレを1にしておくとこの問題を解決出来る.(「forkの際のmemory割り当ての仕様が緩和される」らしい.)

FAQ - Redis

Background saving is failing with a fork() error under Linux even if I've a lot of free RAM!
Short answer: echo 1 > /proc/sys/vm/overcommit_memory :)
And now the long one:
Redis background saving schema relies on the copy-on-write semantic of fork in modern operating systems: Redis forks (creates a child process) that is an exact copy of the parent. The child process dumps the DB on disk and finally exits. In theory the child should use as much memory as the parent being a copy, but actually thanks to the copy-on-write semantic implemented by most modern operating systems the parent and child process will share the common memory pages. A page will be duplicated only when it changes in the child or in the parent. Since in theory all the pages may change while the child process is saving, Linux can't tell in advance how much memory the child will take, so if the overcommit_memory setting is set to zero fork will fail unless there is as much free RAM as required to really duplicate all the parent memory pages, with the result that if you have a Redis dataset of 3 GB and just 2 GB of free memory it will fail.
Setting overcommit_memory to 1 says Linux to relax and perform the fork in a more optimistic allocation fashion, and this is indeed what you want for Redis.
A good source to understand how Linux Virtual Memory work and other alternatives for overcommit_memory and overcommit_ratio is this classic from Red Hat Magazine, "Understanding Virtual Memory".