ISUCON6予選のメイン出題担当のSongmuです。今回はISUCON6の予選問題がどういう問題だったのか、振り返ってみましょう!

アプリケーションについて

はてなキーワード、
(?:匿名)?
ダイアリーを模したブログとWikiの中間の様なアプリケーションです。キーワード自動リンク機能がついています。また、はてなスターのようなお気に入りを付けられる様な機能もついていました。記事の投稿時にはスパムチェックをおこなっており、一部の禁止ワードや、アダルトサイトへのリンクが含まれている場合には投稿できないようになっています。

構成

初期状態で以下の3種類のアプリケーションが起動しており、それぞれが通信を行なっていました。
  • isuda (はてなキーワード・はてな
    (?:匿名)?
    ダイアリーを模したアプリケーション)
  • isutar (はてなスターを模したサブアプリケーション)
  • isupam (スパムチェッカー/Go製のバイナリのみ提供)

  • ISUCONの歴史の中で、最初から複数のプロセスが起動している問題は初めてです。お気づきかと思いますが、今回の問題のテーマは「マイクロサービスアンチパターン」でした。

    また、僕のISUCON参加哲学として「結局いつもの仕事と同じことしかできないし、それが一番うまくいく」というのがあるのですが、それは出題側も一緒なのではないかということで、問題もかなり「はてなっぽい」問題になっています。

    「はてなっぽい」問題にしてしまうと、はてな社員が有利なのでは?と思う向きもあるかもしれませんが、キーワードリンクなどは、はてな社内でもロストテクノロジーと化しているため、問題なかろうという判断でした。実際、はてな社員のチームは何チームか予選に参加していたのですが、決勝進出できたチームはありませんでした…。個人的に非常に残念ですが、それだけ今回の激戦ぶりが伺えます。

    閑話休題。

    isudaとisutarは相互に依存しあっているというアンチパターンで、isupamはソースコードが紛失してしまっているという設定でした。

    ベンチマーカーと採点について

    今回、予選問題を作るにあたって以下の様な狙いがありました。

  • 余りキャッシュが有効にならない問題にしたかった
  • 多くの予選参加者が無条件失格にはならずにスコアが残せるような作りにしたかった

  • ですので、一発失格となるのは初期チェックのみで、その後のメインのベンチマークについては、誤ったレスポンスを返しても減点するのみで失格になるようにはしませんでした。その代わり、減点時には厳し目に減点するという仕組みです。

    実際、一定確率(90%)以上正しいレスポンスを返せない場合にはスコアが上がらないようになっていました。このあたりの減点幅は問題作成当初はもっと厳しかったのですが、一部の言語であまりにも初期スコアが出なかったため、減点幅を緩めることになりました。

    その為、結果として、失敗レスポンスを大幅に許容してもキャッシュで押し切れる様になってしまったことは、出題者として悔いが残るところです。

    初期スコア

    今回は初期スコアのばらつきが大きく、Perl, Python, Ruby以外は初期スコアが0点になってしまうような状況でした。ゆらぎはありますが、初期状態の得点とリクエスト成功数は大体以下のようになっています。(括弧内がリクエスト成功数)

  • Perl 3500(1500)
  • Python 1800(1000)
  • Ruby 300(800)
  • Node/PHP 0(500)
  • Go/Scala 0(200)

  • この初期スコアのばらつきは、各言語の正規表現エンジンの性質によるところが大きいです。問題を作成していて特に困ったのがGoとPHPで、Goの正規表現は想像を絶する遅さであり、PHPに関しては正規表現文字列の長さ上限に引っかかってしまったため、初期実装が他の言語と少し異なっています。

    ベンチマーカーの挙動

    ベンチマーカーには以下の様なシナリオが設定されていました。

  • 正しくログインが行えるか/不正なログインを弾けるか
  • スパムコンテンツを適切に弾いているか
  • スターを正しく付けられるか/不正なスターが付けられないようになっているか
  • トップページから深いページに遡っても適切なレスポンスが返せているか
  • ランダムなキーワードにアクセスして正しくレスポンスを返せるか
  • キーワードを新たに追加できるか。その場合トップページに反映されるとともに新たなキーワードリンクが適切に設定されるか
  • 既存のキーワードを更新できるか。その場合トップページに正しく反映されるか

  • 新規キーワードに対して、他のページからのキーワードリンクの即時反映が求められる点が特にシビアな点と言えるでしょう。

    以下に想定解答を解説していきます。

    最初にやること

    今回の問題を解くに当たって最初にやるべきことは「明らかな無駄を削る」ということです。

    今回のケースだと、isudaとisutarが相互に依存しており無駄な通信も多いため、この2つを結合してモノリシックにしてしまうのが良いでしょう。マイクロサービスを捨ててモノリシックにするのが正解と言うのは皮肉が効いていて面白いのではないでしょうか。

    あとは、キーワードリンクを作る際に毎回テーブルを全件走査して正規表現を組み立てているのは無駄なので、
    SELECT *
    をやめて、
    keyword
    のみの取得にしつつ、そこの処理は1リクエストに付き高々1回にしてしまうこともやると良いでしょう。

    あとは細かいこととして、キーワードリンクが最前最長マッチを期待している関係上、CHARACTER_LENGTH 順でソートしていますが、そこをvirtual columnなり別カラムなりにindexを張るのも良いでしょう。折角MySQL5.7なので、virtural columnを使うのがオシャレです。

    それと、キーワードは更新順で並んでいますが、
    entry.updated_at
    にindexが張られていないので、ここにも張ると良いでしょう。ただ、今回の問題のデータ量だとあまり意味が無いかもしれません。

    キーワードリンク(htmlify)

    今回の問題の本丸は、キーワードリンク作成の高速化です。ここに関しては、正直に言うと余り模範解答を考えていませんでした。想定解答としては、キーワード更新時に正規表現を作り直して、memcachedなりオンメモリにキャッシュしてしまうというものです。そこまでできれば得点は10万点前後で予選突破はできるだろうという想定でした。それ以上を狙う場合は正規表現を捨てて頑張る感じになりますが、そこは各チームがどんな解法を編み出してくるか問題作成者として楽しみにしていました。

    結果としては、思っていたよりも参加者のレベルが高く、正攻法だけではなかなか予選突破が難しいレベルの高い戦いになりました。結果として競プロ勢の躍進があったところも面白かったところです。

    Goでオンメモリに正規表現をキャッシュしてしまえばかなり強いのではないかと思っていたのですが、 Go の正規表現エンジンが想定以上に遅く、その戦略は有効になりませんでした。ただ、
    strings.Replacer
    が有効だったことは盲点でした。

    また、キーワード投稿時にLIKE検索を使ってキャッシュのpurgeをおこなう戦略も有効でこれも盲点でした。初期データのデータ量を絞らざるを得なかったからこそ有効だった手段ですが、想定外の解法であり脱帽です。

    スパムチェッカーisupam

    スパムチェッカーのisupamに関しては、これは狙いとしては完全に目眩ましであり、ボトルネックにはならないところなので手をいれるところではなく、気にしたら負け、くらいの感覚でした。ただ、予選上位チームに関しては、isupamがボトルネックになりつつあったところもあったようで、流石だなという印象です。

    問題作成

    今回最初の初期実装はPerlで作りました。結果として、Perl以外の正規表現が想定以上に遅く、バランスを取るのに苦労しました。本当は初期データ量はもっと増やしたかったのですが思ったよりも少量になりました。Perlの正規表現の速度には改めて驚かされました。

    今回はWikipediaのデータから初期データを作りましたが、初期データの作り込みが肝で、データ量の調整のたびに作り直しが発生するのでその点が一番大変でした。

    新規投稿データに関しては、他のページにキーワードリンクが発生するようなものを優先的に選びつつ、逆に既存のリンクを壊さない様にするデータを抽出しています。このあたりは自動化して選んだ部分もありますが、最終的には温かみのある手動チェックでカバーしています。カバーしきれていない点もあるかも知れませんがご容赦ください。

    ボツ案

    今回の出題でやろうと思っていたけどできなかったことの一つに、検索bot避けがあります。
    /robots.txt
    のエンドポイントがあるのに使われていないのはそのためです。botからのアクセスは低得点にしつつ、
    robots.txt
    に適切な記述があれば加点するようなことを考えていました。実際の世界でも、はてなのようなサービスで、検索ボットをどのように扱うかは結構大事な問題です。

    小ネタ

    今回、各言語実装で、DB接続時に
    SET SESSION sql_mode='TRADITIONAL,NO_AUTO_VALUE_ON_ZERO,ONLY_FULL_GROUP_BY'
    というクエリを発行していますが、これは kamipo TRADITIONALです。皆さん、kamipo TRADITIONALを使いましょう。

    今回の問題のログインユーザーは、PerlのCPANモジュールの
    Acme::CPANAuthors::Japanese
    からリストを作成しています。

    総括

    ということで、予選を実施しました。競プロ勢の躍進もあった予選でしたが、本選はサーバー複数台構成になり、より本来の意味でのWebアプリケーションチューニングコンテストになるため、一筋縄ではいかない問題になるでしょう。

    本選会場で皆様にお会い出来るのを楽しみにしています!


    ■関連リンク
    ISUCON6 予選問題 参照実装ならびにベンチマーカー等の公開