ISUCON11 予選参加記(最終スコア 117585)
チーム「四年ぶり二度目」で @brook_bach と @mayoko_ で参加しました。4年前に ISUCON7 に参加したときと同じチームです。
「興味ある言語でやってみたいよね~」ということで Rust で参加しました。私は本を積んでいる状態だったので、2週間くらいで急いで「実践 Rust プログラミング入門」の5章までを読んで間に合わせました。
事前準備は過去の ISUCON で使った便利スクリプトをかき集めてきたことと、MySQL を AWS 向けにチューニングしたことくらいです。
以下はやったことの概要です。典型的なものしか直せていないので、作問者の意図した「この課題特有のおもしろいところ」まではたどり着けていない感があります。
MariaDB から MySQL に差し替えた(担当 @shora_kujira16)
最近の MariaDB の進化に付いていけていないので MySQL 8.0.26 に差し替えて、事前に用意しておいた設定を適用しました。
これだけだと failed to connect db: Tls(InvalidDNSNameError)
というエラーが出て MySQL に接続できない状態になってしまったので少し焦りました。以下の記事を参考にして Rust から MySQL に接続するときの TLS の実装を runtime-actix-rustls から runtime-actix-native-tls に変更しました。
あとから気づいたのですが、TLS の CPU 負荷も少し気になるので、MySQL への接続に TLS を利用しないことを検討してもよかったのかもしれません。
あとは GROUP BY による暗黙のソートの仕様が MySQL 8.0 で変更されたことも今思えば少し危なかったかもしれません。SELECT `character` FROM `isu` GROUP BY `character`
というステートメントが使われているのですが、MySQL 5.7 以前では GROUP BY `character` ORDER BY `character`
と書かれたのと同じになる仕様でした。MySQL 8.0 ではその仕様がなくなったため、同じ挙動にするためには ORDER BY `character`
を付けてやる必要があります。
Ruby に関するファイルを削除
rust と ruby はプレフィックスが ru まで一緒のため、ディレクトリの移動や isucondition.rust.service の再起動などあらゆるところで補完が止まります。コマンド入力の生産性の低下につながってくるので消しました。
ログイン状態の確認を簡略化(担当 @brook_bach)
アプリケーションのあらゆる個所で require_signed_in によって user テーブルにセッションの値を問い合わせて正式なユーザーであることの確認をしていますが、ユーザーを削除するような処理は存在しないのでセッションの値を信用するということで user テーブルへの問い合わせをやめました。
GET /api/isu の N+1 を少し改善(担当 @shora_kujira16)
isu テーブルのレコードそれぞれについて isu_condition の最新の値をとってくるというクエリがあったので、この部分の改善を試みました。こういうパターンでは MySQL 8.0 で使えるようになったウィンドウ関数が使えたはずだという記憶があったので使い方をググったのですが、微妙にシンタックスエラーになるため以下のようなサブクエリで妥協しました。
SELECT isu.id AS id, isu.character AS `character`, isu.jia_isu_uuid AS jia_isu_uuid, isu.name AS name, (SELECT isu_condition.timestamp FROM isu_condition WHERE isu_condition.jia_isu_uuid = isu.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS timestamp, (SELECT isu_condition.is_sitting FROM isu_condition WHERE isu_condition.jia_isu_uuid = isu.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS is_sitting, (SELECT isu_condition.condition FROM isu_condition WHERE isu_condition.jia_isu_uuid = isu.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS `condition`, (SELECT isu_condition.message FROM isu_condition WHERE isu_condition.jia_isu_uuid = isu.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS message FROM isu WHERE isu.jia_user_id = ? ORDER BY isu.id DESC
他の人の参加記を読んで分かったのですが、こういった処理では MySQL 8.0.14 で追加された LATERAL 句も便利なようです。LATERAL 句では LIMIT 1 に限らず LIMIT N が必要になる場合でも対応できるようです。
インデックスを付ける(担当 @shora_kujira16)
N+1 の改善で全く速くならなかったのでなんだこれと思ってよく見直すとインデックスがまともについていなかったので付けました。MySQL 8.0 で使えるようになった降順インデックスがどれくらい寄与しているのかは分からないです。
-- WHERE isu.jia_user_id = ? ORDER BY isu.id DESC の高速化狙い ALTER TABLE isu ADD INDEX ia_user_id_and_id (jia_user_id, id DESC); -- WHERE isu_condition.jia_isu_uuid = ? ORDER BY isu_condition.timestamp DESC の高速化狙い ALTER TABLE isu_condition ADD INDEX jia_isu_uuid_and_timestamp (jia_isu_uuid, timestamp DESC);
この改善でスコアが 13000 程度になりました。
画像を nginx から配信する(担当 @brook_bach, @mayoko_)
/api/isu/*/icon
に10秒くらいかかっているものがあったので nginx から配信することにしました。今よく考えると、もしかすると Conditional GET のためのヘッダを適切に付与していれば省略できたのかもしれません。
画像ファイルが MySQL に保存されているのを静的ファイルとして保存するように変更するという課題は私たちのチームが前回参加した ISUCON 7 でまさに出題されたものです。今回の課題で違ったのは認証が含まれているということです。アプリケーション側でなにか処理をした結果に応じて静的ファイルを返すかどうか決めるというのはよく必要になる処理であり、多くの Web サーバーがそれに適した機能を提供しています。nginx ではアプリケーションから返すレスポンスヘッダに X-Accel-Redirect を付けると指定個所にリクエストを rewrite してくれるため、これを利用しました。
最新の isu_condition を取ってくる処理の高速化のため、最新の isu_condition を別テーブルに保存する(担当 @shora_kujira16)
GET /api/isu がまだ遅かった(1秒以上かかっていた)ため、N+1 を解消するためにサブクエリではなく JOIN が使えるように ORDER BY isu_condition.timestamp DESC LIMIT 1 の部分を別のテーブルに保存することにしました。
以下のようなテーブルを作り、
CREATE TABLE `last_condition` ( `jia_isu_uuid` char(36) NOT NULL, `timestamp` datetime NOT NULL, `is_sitting` tinyint(1) NOT NULL, `condition` varchar(255) NOT NULL, `message` varchar(255) NOT NULL, PRIMARY KEY (`jia_isu_uuid`) ) ENGINE=InnoDB DEFAULT CHARACTER SET=utf8mb4;
/initialize では以下のようなクエリで初期化し、
INSERT INTO last_condition SELECT a.jia_isu_uuid AS jia_isu_uuid, (SELECT isu_condition.timestamp FROM isu_condition WHERE isu_condition.jia_isu_uuid = a.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS timestamp, (SELECT isu_condition.is_sitting FROM isu_condition WHERE isu_condition.jia_isu_uuid = a.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS is_sitting, (SELECT isu_condition.condition FROM isu_condition WHERE isu_condition.jia_isu_uuid = a.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS `condition`, (SELECT isu_condition.message FROM isu_condition WHERE isu_condition.jia_isu_uuid = a.jia_isu_uuid ORDER BY isu_condition.timestamp DESC LIMIT 1) AS message FROM isu_condition a GROUP BY a.jia_isu_uuid;
POST /api/condition/*
では以下のようなクエリで最新の isu_condition を保存することで
INSERT INTO last_condition (jia_isu_uuid, timestamp, is_sitting, `condition`, message) VALUES (?, ?, ?, ?, ?) ON DUPLICATE KEY UPDATE is_sitting=IF(timestamp<VALUES(timestamp), VALUES(is_sitting), is_sitting), `condition`=IF(timestamp<VALUES(timestamp), VALUES(`condition`), `condition`), message=IF(timestamp<VALUES(timestamp), VALUES(message), message), timestamp=IF(timestamp<VALUES(timestamp), VALUES(timestamp), timestamp)
GET /api/isu
では以下のようなクエリを使えるようになりました。
SELECT isu.id AS id, isu.character AS `character`, isu.jia_isu_uuid AS jia_isu_uuid, isu.name AS name, last_condition.timestamp AS timestamp, last_condition.is_sitting AS is_sitting, last_condition.condition AS `condition`, last_condition.message AS message FROM isu LEFT OUTER JOIN last_condition ON isu.jia_isu_uuid = last_condition.jia_isu_uuid WHERE isu.jia_user_id = ? ORDER BY isu.id DESC;
この改善によりスコアが 18000 程度になりました。
私が知らなかった SQL の仕様として、ON DUPLICATE KEY UPDATE に書いた代入リストは前から順に適用されるということがあります。以下のような順番で書くと3行目の is_sitting=...
以降を実行する際にはすでに timestamp=...
による代入が行われているため、意図しない結果となります。
ON DUPLICATE KEY UPDATE timestamp=IF(timestamp<VALUES(timestamp), VALUES(timestamp), timestamp), is_sitting=IF(timestamp<VALUES(timestamp), VALUES(is_sitting), is_sitting), `condition`=IF(timestamp<VALUES(timestamp), VALUES(`condition`), `condition`), message=IF(timestamp<VALUES(timestamp), VALUES(message), message)
GET /api/trend の N+1 を改善(担当 mayoko_)
GET /api/isu の改善と並行して /api/trend の改善も進めました。last_condition が用意されていれば以下のようなクエリで N+1 を解消することができ、レスポンスの組み立てをアプリケーション側で処理することができます。
SELECT isu.id AS id, isu.character AS `character`, last_condition.condition AS `condition`, last_condition.timestamp AS timestamp FROM isu INNER JOIN last_condition ON isu.jia_isu_uuid = last_condition.jia_isu_uuid WHERE isu.character IS NOT NULL
この改善によりスコアが 35000 程度になりました。
この改善ではベンチマーカーの採点基準に起因すると思われる不思議な現象に悩まされました。当初の実装ではレスポンスに含まれるデータの順序を考慮しておらず減点が発生していました。順序を考慮するような実装に修正して再度負荷走行を行ったところ「サービスの評判が上がりユーザーが増加しました」という旨のメッセージともに負荷レベルが上昇しました。これによりこれまで問題となっていなかったエンドポイントで1秒以上の時間がかかるようになってしまいタイムアウトが頻発し、ほとんどスコアが出なくなってしまいました。おそらく正攻法ではないのではないかと考えています。
分散構成に移行(担当 @brook_bach)
当初は以下のような構成を想定していました。
- 192.168.0.11 は nginx, MySQL の処理と画像ファイルに関連するエンドポイントを処理
- 192.168.0.12, 192.168.0.13 はその他のエンドポイントを処理
しかし謎のエラーが出てしまい、時間も迫っていたので以下のような構成で妥協しました。
結果発表後に調査したところ、エラーの原因は非常に単純で location /api/isu { }
としなければならないところを location /api/isu/ { }
と余計なスラッシュを付けてしまっていたことでした。
負荷走行中に htop を眺めていると 192.168.0.13 の CPU 使用率が100%だったためこの間違いがなければスコアの改善が見込めたと考えられますが、192.168.0.11 と 192.168.0.12 の CPU 使用率もそれなりに高かったため、たかだか 1.x 倍程度の改善だったと考えられます。
そのほかカーネルのチューニングやログの無効化などにより最終スコアが得られました。
感想
- 毎度のことですが、作問者の意図した「この課題特有のおもしろいところ」まではたどり着けていないのは悔しいです。一方、以前と比べて理詰めで改善が行えている点は進歩と言えそうです
- Rust を使ったことに関しては今回の課題はアプリケーション側の負荷が高めだったため、速度面での恩恵が受けられたと言えそうです。私にとってはあまりスムーズに開発できたとはいえない状況でしたが、それは本を買って積んでいた私がわるいのです
運営さんありがとう
今回の運営はこれまでと比べて格段にルールやレギュレーションの示し方が明確になっており、clar の受付や選手向けページの障害発生時の対応などについても違和感を感じることがなく、高いレベルで運営されていると感じました。とても有意義な時間になりました。ありがとうございました。
「Stack Overflow の機械翻訳サイトの除外用フィルタ」の管理をしていてわかったこと
こんにちは。ublacklist-stackoverflow-translation を管理している @shora_kujira16 です。
このリポジトリはよく目につく Stack Overflow の機械翻訳サイトがまだ両手で数えられるほどしかなかった2019年10月に公開を始めたものです。利用者数を計測することはできていないのですが、GitHub のスターの数などから推測するに今年の1月ごろから多くの方にご利用いただいているようです。
リポジトリを公開してから1年半ほど経ち、今では多くの方から継続的にプルリクエストをいただくようになりました。この記事ではこのリポジトリを管理していてわかったことや今後の展望についてまとめます。
対象ドメインの数
「Stack Overflow 機械翻訳」のようなキーワードで Twitter を検索してみることがあるのですが、リポジトリの公開を始めた2019年10月ごろと比較すると「機械翻訳サイトを見かけることが増えてきた」という旨のツイートの件数が増えているように思われます。
以下のグラフはフィルタのエントリである uBlacklist.txt の月ごとの件数*1を表したものです。
2020年10月からの比較で約3倍に増えているということがわかります。フィルタのメンテナンスはあくまで利用者が機械翻訳サイトの存在に気づいた時点で行われるため、このグラフをもって機械翻訳サイトの立ち上げが増えていると結論付けることは難しいですが、目につく件数が増えているとみなすことはできるかもしれません。
最近追加されているサイトの傾向
プルリクエストの内容は毎回確認してから取り込むようにしています。その作業の中で気づいたことを紹介します。
既存サイトのドメイン変更やリダイレクト専用サイトの追加
SEO のテクニックなのか何なのか詳細はわかりませんが、似たようなドメインを大量に取得して同じ内容を配信したり、ひとつのドメインにリダイレクトして集約するような構成にしているサイト群がいくつか見つかります。
例としては以下のようなサイト群です。
stackovernet.com stackoverrun.com stackovernet.xyz
www.it-swarm-ja.tech www.it-swarm.jp.net www.it-mure.jp.net www.it-swarm-ja.com www.it-swarm.com.ru
www.generacodice.blog www.generacodice.it www.generacodice.com
このようなサイトは油断した隙にドメインが増えていることがよくあります。利用者の方でフィルタに引っ掛からないドメインが増えていることに気づいた方はお気軽にプルリクエストでご連絡ください。
CMS を利用して構築されたサイトの登場
evidence.md というファイルの Page という列に書かれている URL を上から順番に開いてみてください。内容は別として、上のほうに掲載されている老舗のサイトはデザインも悪くなく出来のいいものが多いと感じる方も多いのではないでしょうか。
一方、下のほうに掲載されている最近追加されたサイトについてもいくつか開いてみてください。最近は CMS として WordPress を利用して機械翻訳サイトを量産することが流行しているらしく、デザインが破綻しているものもいくつか見つかります。
このようなサイトの存在は #45, #46 で知りました。今後の傾向にも注視していきたいと考えています。
今後の展望
Stack Exchange 以外のサイトへの対応
#50 で GitHub の、#57 で teratail の機械翻訳サイトの存在を指摘されました。
このフィルタのほとんどの利用者にとってはこのようなサイトも除外リストに加えることが有益であると想像していますが、このリポジトリでは Stack Exchange の翻訳サイトのみを対象とすることとして今のところは採用しない方針にしています。これは悩ましいグレーゾーンの判断のために時間を要するものが増えてくると管理の負担が増えてくることを危惧しているためです。
一方、このようなサイトが増えてきた場合には私自身が利用するためにもフィルタを開発する必要があると考えており、目安として4つ以上のサイトが発見された場合には新しいリポジトリの運営を始めたいと考えています。
メンテナンスにおける工夫
リポジトリを公開した時点ではフィルタの本体である uBlacklist.txt と README しか無いリポジトリでしたが、エントリが増えてくるにつれて以下のような改善がありました。
フィルタへの収録根拠の明示
フィルタへの収録の根拠として元となった Stack Overflow のページと、そのページの機械翻訳ページの URL を evidence.md に記載しています。「このドメインって本当に機械翻訳サイトだったっけ?」と不安になることが増えてきたのでエントリが20件を超えたあたりで作成しました。
このファイルのメンテナンスには手間がかかりますが、フィルタを安心して利用してもらうためには根拠を明示することが重要であり必要なコストであると考えています。
CI によるメンテナンス作業の補助
上記の evidence.md と uBlacklist.txt の整合性を保つのが面倒になってきたため #33 で協力を募って #48 で開発していただいたものです。domain-list.yml という YAML を編集してコミットすると GitHub Actions により evidence.md と uBlacklist.txt を更新したコミットが自動的に作られるようになっています。
このような改善によりメンテナンス作業の負担が軽減されました。一方、エントリ数が数百に達してきた場合にはさらに別の課題が出てくるのではないかと感じており、今後の対策について検討しています。
まとめ
この記事では ublacklist-stackoverflow-translation を管理していてわかったことと今後の展望についてまとめました。私の生活に余裕がある間はメンテナンスを続けたいと考えているため今後も安心してご利用ください。
*1:正確には毎月の最終コミット時のファイルの行数
ICPC 模擬国内予選 2020 スタッフ参加記
問題
あなたは ICPC OB/OG の会が開催する ICPC 模擬国内予選 2020 のスタッフとして、選手に詳細案内を送付する仕事を任されている。
詳細案内は、模擬国内予選で使われるジャッジシステムの URL とログインに必要なチーム番号、パスワード、そしてチーム名と所属を含む文字列であり、与えられたテンプレートにチームごとに異なる文字列を埋め込むことによって表される。
あなたは詳細案内を「すごく難しい天才以外お断りプロトコル」(SMTP) を使って送付しなければならない。 プログラマーであるあなたは SMTP を使って詳細案内を送信するプログラムを作成することにした。
入力
入力は以下の形式で表される
N A_1 T_1 S_1 I_1 P_1 A_2 T_2 S_2 I_2 P_2 ... A_N T_N S_N I_N P_N L M_1 M_2 ... M_L
最初の行は送付先のメールアドレスの数 N (1 ≦ N ≦ 103) を表す整数からなる。
2行目から続く N 行はそれぞれ i 番目の詳細案内の送付に必要な情報としてメールアドレス A_i、チーム名 T_i、所属 S_i、チーム番号 I_i、パスワード P_i を表す文字列からなる。
N + 2 行目は詳細案内のテンプレートの行数 L (1 ≦ L ≦ 103) を表す整数からなる。続く L 行は詳細案内のテンプレートを表す文字列を表す。このテンプレートのいずれかの行は、チーム名を埋め込むべき箇所を表す $team
、所属を埋め込むべき箇所を表す $affiliation
、チーム番号を埋め込むべき箇所を表す $login
、パスワードを埋め込むべき箇所を表す $password
を含む。テンプレートの文字列は 100 KiB を超えない。
出力
出力はない。
得点
模擬国内予選の終了までに「詳細案内のメールが届いていない」という旨の連絡を受け取った数を X とする。N - X があなたの得点となる。
入力例
6 king-1@example.com ___KING___ The_University_of_Tokyo 1 aaaaaaaa king-2@example.com ___KING___ The_University_of_Tokyo 1 aaaaaaaa good-yamikin-1@example.net good_yamikin Tokyo_Institute_of_Technology 2 bbbbbbbb good-yamikin-2@example.net good_yamikin Tokyo_Institute_of_Technology 2 bbbbbbbb good-yamikin-3@example.net good_yamikin Tokyo_Institute_of_Technology 2 bbbbbbbb gazeru-1@example.org gazeru Kyoto_University 3 cccccccc 11 ICPC 国際大学対抗プログラミングコンテスト模擬国内予選 2020 チーム $team ($affiliation) の皆様 模擬国内予選への参加登録ありがとうございます. このメールでは自動審判システムの情報についてお知らせします. 今年も自動審判システムとして国内予選本番で使われるものと同様の Web ベースの審判システムを利用します. 自動審判システムへのログインには,チーム番号とパスワードが必要です. チーム番号: $login パスワード: $password 審判システムの URL はこちらです. http://icpc2020.jag-icpc.org/icpc2020/common/login_ja.php 参加者は事前にチュートリアルにもよく目を通しておいてください.
部分点解法
JAG で運用しているサーバーで動いている Postfix を使ってメールを送信する方法が愚直解として考えられます。事実として、数年前まではこの方法でも問題なくメールを配信できていました。しかし昨年の模擬国内予選では「メールが届いていない。迷惑メールフォルダにも入っていない」という問い合わせが殺到してしまいました。さらに、去年までは1チーム1メールアドレスまでの登録としていたところ、利便性のため今年は1チーム3メールアドレスまで登録できるように変更したため、問い合わせがさらに増えることが予想されました。そのため今年は別の方法を探すことを余儀なくされました。
部分点解法の問題点
Gmail や Outlook.com をはじめとする多くのメールサービスプロバイダーでは、以前にも増して悪意あるメールへの対策が厳しくなってきています。悪意あるメールを判定する方法としてはメールの内容を調べることも重要ですが、「怪しい IP アドレス」から送信されているかどうか、という特徴量も強い影響を持っています。「怪しい IP アドレス」からメールが大量に送信されている場合、受信側のメールサーバーではそのメールを迷惑メールフォルダに隔離することさえなく捨ててしまう場合もあるようです。
この IP アドレスの怪しさは「レピュテーション」(評判)と呼ばれています。レピュテーションの算出方法はメールサービスプロバイダーの実装に依存し、悪用を防ぐため通常は公開されていませんが、一般論として以下のような要素が考慮されていると言われています*1。
- 存在しないメールアドレスにメールを送ってくる IP アドレスはレピュテーションを低くする(無差別にスパムメールを送信している疑いがあるため)
- ユーザーがよく「迷惑メールを報告」ボタンを押すようなメールを送ってくる IP アドレスはレピュテーションを低くする
- スパムメール業者がよく利用しているホスティングサービス(レンタルサーバーや IaaS)の IP アドレス帯はレピュテーションを低くする
- これまであまりメールを送ってこなかった IP アドレスから急にたくさんのメールが送られてきたら警戒する
JAG で運用しているサーバーからメールを送信する方法は 3. と 4. の観点で大きく不利でした。3. については現在利用しているホスティングサービスのレピュテーションがどうなのか私は知りませんが、一般論としてレンタルサーバーに付与される IP アドレスは基礎的なレピュテーションにあまり期待できません。4. についてはかなり致命的で、平常時は1週間のうちにせいぜいに10通程度のメールしか送信していない IP アドレスから数時間のうちに何百通もメールが届くようなことがあれば、ブロックするように実装するのは妥当な考えでしょう。
満点解法
地道にメールの送信数を増やして JAG のサーバーの IP アドレスのレピュテーションを高くするというのが正攻法ですが、模擬国内予選は1年に1回の開催のためこの方法をとることはできません。
代わりに SendGrid や Amazon SES といったメール配信サービスを使います。これらのサービスを使ってメールを送信すると、高いレピュテーションを持った IP アドレスからメールが送信されるため、メールの到達率が格段に上昇します。
悪意のある利用者がメール配信サービスを使ってしまえばレピュテーションの意味がなくなってしまうのではと思われるかもしれませんが、メール配信サービス側では以下のような対策が行われています。
- 利用に事前審査が必要
- 送信元(メール配信サービス側)でも独自のレピュテーションを計算
- 送信先のメールアドレスからバウンスメール(いわゆる MAILER-DAEMON)が返ってきたり、迷惑メールとしての通報があるとレピュテーションが低下
- レピュテーションが一定のしきい値を下回ると送信をブロック。再審査が通るまで利用を制限
今回は SendGrid を利用しました。SendGrid は月に12,000通までの送信は無料で利用できるというのが大きな利点です。また、これは ICPC 特有の事情ですが、SendGrid の日本の販売代理店である構造計画研究所は以前に ICPC のスポンサーを数年間していたことがあり、もし審査で渋い反応をされたときでもアピールしやすいのではないかということもありました。
結果的に、この方法は功を奏し、数百通のメールを配信することができました。今年も「メールが届いていない」という問い合わせは何件かありましたが、申し込みに使っていたメールアドレスを勘違いしていたというような原因によるものであり、SendGrid 側でなにか問題が起きていたという事例はありませんでした。さすが大手のメール配信サービスだなという感想です。
おわりに
最近はコンテストにはあまり参加できておらず問題を作るのも解くのも現役のときと比べると難しさを感じており作問作業ではほとんど貢献できていなかったのですが、本業の知見を活かしてインフラ面での貢献できたのはよかったです。