ISUCON6予選で悲しくも負けてしまいました
Created at Sat, Sep 10, 2016ISUCON6予選で悲しくも負けてしまいました
こんにちは. ISUCON6に3人チーム「ウルド」として出場したのですが, 悲しくも予選落ちをしてしまいました.
ベストスコアは99,000点, 最終スコアは76,000点で, ベストスコアなら予選を突破できていただけに非常に悔しく思っています.
今回は, 予選で何をしたかと反省を書きたいと思います. 反省ブログです.
基本的なメンバーのスペック
Golangで勝負しました. 最初の実装では正規表現をバリバリに使っていて, スコアが0の状態だったのでPythonにしようか悩んだのですが, 最終的には言語の差はほぼ出ないだろうとの予測でGolangで勝負することにしました.
メンバーの簡単な役割分担は以下の感じです.
- 僕(アプリ: Golang)
- メンバーその1(インフラ+アプリ)
- メンバーその2(インフラ+アプリ)
僕がアプリを中心に直して, 2人にはボトルネックの検出や, 全体的な流れを見てもらう感じになっています. とはいえ, かっちりこの役割というわけではなく, 時間に応じて役割を切り分けながらという感じで柔軟にいけたかなと思ってます.
最初の2時間くらい
とにかくGoの初期実装がスコア0なので, そこから脱却するためにいろいろと細かいところをチューニングしたのですが効果が出ず.
プロファイリングしてみると, アプリプロセスがCPUを使い果たしていてパフォーマンスが出ていない模様.
そしてなんやかんやと, メンバーが正規表現をバリバリ使っている「htmlify」の部分が遅いことを突き止めてくれたのでそこを中心に勝負することに.
12時くらいの段階
テキストに対してキーワードリンクを挿入する箇所で, 正規表現のorを使っている箇所を発見.
re := regexp.MustCompile("(" + strings.Join(keywords, "|") + ")")
keywordsは7,000以上なのでここが明らかにボトルネック.
そういえば, 昔naoyaさんのブログではてなのキーワードリンクがスケールしなくなったときに, 何かアルゴリズムを使って解決したみたいな記事があったことを思い出して死ぬ気でググる.
その結果 Aho Corasick というアルゴリズムを発見. これ使えばいけるんじゃね? ということでGolangで Aho Corasick のライブラリがないかを死ぬ気でググる.
その結果, https://github.com/anknown/ahocorasick を発見. よく分かんないけどこれを死ぬ気でアプリに適応させる.
13:30くらい
何かよく分かんないけど動いた! そしてスコアは15,000くらいになる!
これでhtmlifyは大丈夫だと思い, keywordをredisでリストで保持して, MySQLのクエリを減らす作業に入る.
これがミスでした. htmlifyのコストがまだ高く, ここをもう少し重点的にやるべきだった.
15:30くらい
keywordをリストで持つようにしたもののスコアは15,000のまま動かず.
ここで, メンバーがhtmlifyがまだ遅いことを突き止めてTrie木をキャッシュすることを考える
16:30くらい
Trie木をキャッシュする. keywordが更新, 削除されるタイミングでTrie木を作り直す(invalidate)のを実装.
結果, 75,000点くらいを叩き出す. この時点ではいい感じの順位に入っており, 予選突破いけるんじゃないかとそわそわし始める.
これがミスでした. ここでそわそわして, 残りの時間適切な実装が出来ずスコアがここで止まってしまった.
17:30くらい
MySQLのstarを取ってくる部分のクエリ効率化などの実装をしたものの, 間に合わず. このあたりで再起動テストに入る.
運良く? このあたりのベンチで99,000を出したものの, 最後は76,000で着地しました.
まとめ/反省
個人的にやりたかったのは
- トップページのキャッシュ
- UnixSocket化(最後時間がなかった)
- MySQLのstarを取ってくる部分のクエリ効率化
これらが時間内に実装出来れば100,000以上いけたと思います.
練習だったら多分ここまでいけたと思うんですけど, 本番の重圧か, ここまでいけませんでした.
あと, 心構えとしては
- 予選突破できそうだからと慌ててはいけない
- 最初スコアが出なくも慌ててはいけない
慌てないことが大切だなと思いました.
最後に
最後に出題して頂いたはてなさん, ピクシブさん本当にありがとうございました.
非常に楽しい時間を過ごせました(^o^)
あと, 何かここが知りたいみたいなことがあったら, twitterとかコメントどしどし下さい.
ISUCON6予選で悲しくも負けてしまいました
こんにちは. ISUCON6に3人チーム「ウルド」として出場したのですが, 悲しくも予選落ちをしてしまいました.
ベストスコアは99,000点, 最終スコアは76,000点で, ベストスコアなら予選を突破できていただけに非常に悔しく思っています.
今回は, 予選で何をしたかと反省を書きたいと思います. 反省ブログです.
基本的なメンバーのスペック
Golangで勝負しました. 最初の実装では正規表現をバリバリに使っていて, スコアが0の状態だったのでPythonにしようか悩んだのですが, 最終的には言語の差はほぼ出ないだろうとの予測でGolangで勝負することにしました.
メンバーの簡単な役割分担は以下の感じです.
- 僕(アプリ: Golang)
- メンバーその1(インフラ+アプリ)
- メンバーその2(インフラ+アプリ)
僕がアプリを中心に直して, 2人にはボトルネックの検出や, 全体的な流れを見てもらう感じになっています. とはいえ, かっちりこの役割というわけではなく, 時間に応じて役割を切り分けながらという感じで柔軟にいけたかなと思ってます.
最初の2時間くらい
とにかくGoの初期実装がスコア0なので, そこから脱却するためにいろいろと細かいところをチューニングしたのですが効果が出ず.
プロファイリングしてみると, アプリプロセスがCPUを使い果たしていてパフォーマンスが出ていない模様.
そしてなんやかんやと, メンバーが正規表現をバリバリ使っている「htmlify」の部分が遅いことを突き止めてくれたのでそこを中心に勝負することに.
12時くらいの段階
テキストに対してキーワードリンクを挿入する箇所で, 正規表現のorを使っている箇所を発見.
re := regexp.MustCompile("(" + strings.Join(keywords, "|") + ")")
keywordsは7,000以上なのでここが明らかにボトルネック.
そういえば, 昔naoyaさんのブログではてなのキーワードリンクがスケールしなくなったときに, 何かアルゴリズムを使って解決したみたいな記事があったことを思い出して死ぬ気でググる.
その結果 Aho Corasick というアルゴリズムを発見. これ使えばいけるんじゃね? ということでGolangで Aho Corasick のライブラリがないかを死ぬ気でググる.
その結果, https://github.com/anknown/ahocorasick を発見. よく分かんないけどこれを死ぬ気でアプリに適応させる.
13:30くらい
何かよく分かんないけど動いた! そしてスコアは15,000くらいになる!
これでhtmlifyは大丈夫だと思い, keywordをredisでリストで保持して, MySQLのクエリを減らす作業に入る.
これがミスでした. htmlifyのコストがまだ高く, ここをもう少し重点的にやるべきだった.
15:30くらい
keywordをリストで持つようにしたもののスコアは15,000のまま動かず.
ここで, メンバーがhtmlifyがまだ遅いことを突き止めてTrie木をキャッシュすることを考える
16:30くらい
Trie木をキャッシュする. keywordが更新, 削除されるタイミングでTrie木を作り直す(invalidate)のを実装.
結果, 75,000点くらいを叩き出す. この時点ではいい感じの順位に入っており, 予選突破いけるんじゃないかとそわそわし始める.
これがミスでした. ここでそわそわして, 残りの時間適切な実装が出来ずスコアがここで止まってしまった.
17:30くらい
MySQLのstarを取ってくる部分のクエリ効率化などの実装をしたものの, 間に合わず. このあたりで再起動テストに入る.
運良く? このあたりのベンチで99,000を出したものの, 最後は76,000で着地しました.
まとめ/反省
個人的にやりたかったのは
- トップページのキャッシュ
- UnixSocket化(最後時間がなかった)
- MySQLのstarを取ってくる部分のクエリ効率化
これらが時間内に実装出来れば100,000以上いけたと思います.
練習だったら多分ここまでいけたと思うんですけど, 本番の重圧か, ここまでいけませんでした.
あと, 心構えとしては
- 予選突破できそうだからと慌ててはいけない
- 最初スコアが出なくも慌ててはいけない
慌てないことが大切だなと思いました.
最後に
最後に出題して頂いたはてなさん, ピクシブさん本当にありがとうございました.
非常に楽しい時間を過ごせました(^o^)
あと, 何かここが知りたいみたいなことがあったら, twitterとかコメントどしどし下さい.