あいつの日誌β

働きながら旅しています。

ISUCON6 予選を復習: とりあえず Perl で 5万点とれました

ISUCON6

あらすじ

ISUCON6 の予選を復習しました。ベンチマークツールを localhost で実行しているので予選時とはまたちがった数値になっていると思いますので参考程度に考えて頂ければと思います。

ちなみに今回の予選では VM が SSD になっていて、そのため redis やプロセス内にデータを全部を保存する戦術がやや陳腐化しています。

予選敗退だったけど

ISUCON 楽しかったなあ。来年もやってくれるといいなあ...

記事の概要

準備する

ソースコードはここにあります。 https://github.com/okamuuu/isucon6q

VM を作成する

https://portal.azure.com/#create/Microsoft.Template/uri/https%3a%2f%2fgist%2egithub%2ecom%2ftatsuru%2fc9813892b9c4eb99c7f661a880d8b4fe%2fraw%2fdeploy%2ejson

Deploy したからといってすぐ動くわけではないので10分ほど待ってみましょう。 top コマンドを見ていると ansible などが動いている事が確認できると思います。

待っている間に各自で dotfiles などの設定をしておくと良いでしょう。

ベンチマークツールを同一ホスト上に設置する

以下のようにすればいいと思います。私はあまり golang の経験ないので正しい作法かわかりませんがこれでベンチの実行はできました。

https://gist.github.com/okamuuu/dbdc299fe9a37516de64c9bcdafcbf0d

初期状態で localhost にめがけてベンチツールを実行するとだいたいこのような数値が表示されると思います。

{"pass":true,"score":3369,"success":1758,"fail":5,"messages":["リクエストがタイムアウトしました (POST /login)","リクエストがタイムアウトしました (POST /stars)"]}

Perl で実装を開始する

初期ベンチ結果

{"pass":true,"score":3245,"success":1610,"fail":4,"messages":["リクエストがタイムアウトしました (POST /keyword)","リクエストがタ イムアウトしました (POST /stars)"]}

とりあえず話をシンプルにするために isuda, isutar を統合する

以下の作業を行います。真っ先に対処するべきなのは htmlify の箇所だと思いますが記事をコンパクトにしたいので真っ先にここの改修をした事にして話をすすめます。

  • isutar.star を isuda.entry_star へ移植する
  • isutar の機能を isuda へ移動
  • nginx から isutar へのリクエストを辞める
{"pass":true,"score":3953,"success":1790,"fail":3,"messages":["リクエストがタイムアウトしました (POST /keyword)"]}

isutar は sudo systemctl disable isutar.perl.service　して disable しておきます。

worker の調整

そもそもベンチが通り切っていないのですがどうやら nginx が仕事を渡す相手が足りてないので返事をするのが遅くなっているようです。worker を 5 -> 15 に増やします。

{"pass":true,"score":11122,"success":2392,"fail":0,"messages":[]}

無事ベンチが走りきったようです。ちなみに公開されたベンチマークツールをみたところわざと負荷をかけるリクエストも存在していたようです。

htmlify 関数

というわけで htmlify の処理時間を計測してみます。

とあるプロセスでは htmlify で使った49秒のうち36秒が MySQL から keyword を取得しているに使われているようです。

$VAR1 = {
'sub htmlify -> create regex' => '1.87830519676208',
'sub htmlify -> replace br' => '0.00245761871337891',
'sub htmlify' => '49.4288206100464',
'sub htmlify -> replace content' => '10.9845297336578',
'sub htmlify -> select keywords' => '36.3201262950897',
'sub htmlify -> link escape' => '0.235542058944702',
'sub htmlify -> html_escape' => '0.00136899948120117'
};

keyword だけ取得するようにします。

{"pass":true,"score":18138,"success":5578,"fail":0,"messages":[]}

とあるプロセスではどうやら正規表現を使って content を置換する箇所が重かったようです。9.9秒中6.8秒がそのために使われています。

{
'sub htmlify -> select keywords' => '1.97450876235962',
'sub htmlify -> create regex' => '0.733687400817871',
'sub htmlify -> replace content' => '6.80711960792542',
'sub htmlify -> replace br' => '0.0530831813812256',
'sub htmlify -> link escape' => '0.338440179824829',
'sub htmlify -> html_escape' => '0.000801801681518555',
'sub htmlify' => '9.92848801612854'
};

Regexp::Trie

正規表現での置換が遅いという事がわかったのでその処理を高速化したいと思います。 というわけで Regexp::Trie を使います。

残念ながら遅くなってしまいました。

{"pass":true,"score":13091,"success":2501,"fail":0,"messages":[]}

とあるプロセスの処理時間

$VAR1 = {
'sub htmlify -> output regexp' => '22.6670215129852',
'sub htmlify -> create trie tree' => '11.0876638889313',
'sub htmlify -> replace content' => '2.06930303573608',
'sub htmlify -> select keywords' => '1.38240551948547',
'sub htmlify -> replace br' => '0.0216348171234131',
'sub htmlify' => '37.4570116996765',
'sub htmlify -> link escape' => '0.166108369827271',
'sub htmlify -> html_escape' => '0.0616908073425293'
};

目論見通り正規表現での置換は高速になりましたが Trie 木を構築するのとそこから regexp を生成するのに時間がかかっているようです。ちなみに Trie なので ORDER BY CHARACTER_LENGTH(keyword) DESC の箇所が不要になります。

という事で Regexp::trie を使って都度正規表現を生成すると逆に時間がかかってします。というわけで keyord の更新が行われた時だけ　Regexp::trie　を生成する方法を考えてみます(結局うまくいきませんでした)

redis に正規表現を保存してみる

sudo apt-get install redis-server して redis を install します。 ちょっと雑ですが正規表現を redis に保存して、post '/keyword' とpost '/keyword/:keyword'` のタイミングで削除してみます。

{"pass":true,"score":17193,"success":5036,"fail":0,"messages":[]}

ただし雑なタイミングでキャッシュしているので場合によってはデータが不整合を起こしてしまいます。keyword が POST されたタイミングと正規表現のキャッシュが完成するまでのタイムラグが大きいので仕方がないといったところです。

{"pass":true,"score":19654,"success":5719,"fail":1,"messages":["keyword: \"福井県道262号武生インター東線\" に \"福井県道40号武生インター 線\" からのリンクがありません (GET /keyword/福井県道40号武生インター線)"]}

とあるプロセスでの処理時間

{
'sub htmlify -> select keywords' => '3.02762842178345',
'sub htmlify -> output regexp' => '12.8065803050995',
'sub htmlify -> create trie tree' => '5.53745675086975',
'sub htmlify -> link escape' => '0.247139453887939',
'sub htmlify -> replace content' => '4.18021178245544',
'sub htmlify -> html_escape' => '0.00234389305114746',
'sub htmlify -> replace br' => '0.00198054313659668',
'sub htmlify' => '28.2025151252747'
};

数字が含まれているキーワードだけ正規表現の構築を分けてみる

パイプで正規表現をつなげると処理が重くなりますが、かといってRegex::Trie を使って、都度正規表現を構築すると時間がかかります。

ということである程度パイプでつなげるのを許容して正規表現のキャッシュを分割します。

数字が含まれているキーワードとそうでないキーワードで正規表現を分けてみます。

{"pass":true,"score":19123,"success":5264,"fail":0,"messages":[]}

とあるプロセスでは数字以外の正規表現の構築に時間がかかっていました。

{                                                                                  
'sub htmlify -> html_escape' => '0.0200762748718262',                            
'sub htmlify -> link escape' => '0.265851497650146',                             
'sub htmlify -> create regex' => '14.5149149894714',                             
'sub htmlify -> create number regex' => '0.267951965332031',                     
'sub htmlify -> replace content' => '6.16770577430725',                          
'sub htmlify -> replace br' => '0.00223565101623535',                            
'sub htmlify -> select keywords' => '5.16128373146057'                           
};

頻出する文字を含むキーワードも正規表現を分けてみるが...

以下のように頻出する単語を調べて追加してみます。

https://gist.github.com/okamuuu/22f894b33021861f4fcf3629768737d9

とりあえずカタカナも分けてみましょう。うーん、ちょっとだめっぽい。

{"pass":true,"score":16826,"success":5203,"fail":1,"messages":["keyword: \"内田修平\" に \"囲碁の記録一覧\" からのリンクがありません (GET /keyword/囲碁の記録一覧)"]}

Trie は高速に変換できるんですがいかんせん keyworod の POST が多すぎてどうにもなりませんでした。プロセスをプリフォークしている関係上整合生を保つのも大変。

他のチームで Trie でうまく行ったチームもあるようなので他の方々が解法を公開するのを待ちたいと思います。

ただ今回削除されたキーワードがリンクをはずれているかどうかをチェックしていない気がする...

気を取り直して別の方法を試す

彼らの手法を真似してみます。

http://yu3mars.hatenablog.com/entry/2016/09/19/190000

{"pass":true,"score":21207,"success":6992,"fail":0,"messages":[]}

速くなりました。なんて賢い学生達なんでしょうか。 とりあえず htmlify はこのあたりにして他の箇所を早くしてみます。

html をキャッシュする手法を試す

http://tagomoris.hatenablog.com/entry/2016/09/20/193730

登録されている7101件のエントリーを事前にレンダリングしておいて保存しておきます。 キーワードが POST された時に影響のある HTML を NULL に置き換えてその場合は正規表現で置換する処理です。

結果は高速化に成功。mysqld が頑張り始めます。

{"pass":true,"score":60072,"success":27025,"fail":1,"messages":["keyword: \"物質文明\" に \"ニューエイジ\" からのリンクがありません (GET /keyword/ニューエイジ)"]}

とりあえず

updated_at にインデックスを貼ってみますが残念ながら誤差の範囲でしかないので set_name の name も session に保存してみますがやはり誤差の範囲でしかないです。

というわけで無事５万点。

ちなみに

今回のお題ではキーワードが更新されたタイミングでキャッシュを削除していますが、実はキーワードが存在しない状態でリンクが貼られていても PASS します。

と、いうことは POST されるキーワードを集めておいて事前に Trie で Regexp 作っておけばいいんじゃないか！という裏技が存在します。

このようなテーブル作ってベンチマークを実行して使用されるキーワードを集めます。

CREATE TABLE `post` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `keyword` varchar(191) COLLATE utf8mb4_bin DEFAULT NULL,
  `created_at` datetime DEFAULT NULL,
  `updated_at` datetime NOT NULL,
  PRIMARY KEY (`id`),
  KEY (`keyword`)
) ENGINE=InnoDB AUTO_INCREMENT=63 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin

entry.keyword と post.keyword を使って GET /initialze の時に Rexgep::Trie で正規表現を組み立てて各プロセスに保存させます。htmlify ではその正規表現を使います。

{"pass":true,"score":80041,"success":35299,"fail":0,"messages":[]}

ついでにこのような table を作って事前にキャッシュを作れば... この解法にそこまで興味ないので私はやりませんが興味がある方はどこまで速くなるのか試してみるのも一興かと。

CREATE TABLE `rendered_entry` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `entry_id` varchar(191) COLLATE utf8mb4_bin DEFAULT NULL,
  `description` mediumtext COLLATE utf8mb4_bin,
  `rendered` mediumtext COLLATE utf8mb4_bin,
  `created_at` datetime DEFAULT NULL,
  `updated_at` datetime NOT NULL,
  PRIMARY KEY (`id`),
  KEY (`entry_id`)
) ENGINE=InnoDB AUTO_INCREMENT=63 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin

あとそれから

ミドルウェアの設定特に何もしていません。