Go to Qiita Advent Calendar 2024 Top
LoginSignup
41
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@keymoon

ac-predictor を支える技術

Last updated at Posted at 2020-11-30

この記事は、Competitive Programming (1) Advent Calendar 2020 1 日目の記事です。

ac-predictor とは?

コンテスト中やコンテスト後にパフォーマンスの計算をローカルで行い、レートの更新を待たずとも更新後のレートやパフォーマンスを確認することができるサービスです。UserScript（拡張機能）と Web ページにて提供されています。
なお、このサービスは Codeforces における同様のサービスである cf-predictor に着想を得たものです。

処理

このサービスを提供するにおいてのコアの部分である、パフォーマンスを計算する部分とレート遷移を計算する部分について必要な処理を考えます。ここでは概要だけを説明するので、詳しく知りたい方はAtCoderのレート計算式等の資料を参照してください。
まず、レート遷移を計算するにあたって必要な情報についてです。レート遷移については全パフォーマンスの履歴があればもちろん計算できますが、参加回数と現レート、パフォーマンスだけでも計算できることが知られています。
次に、パフォーマンスについてです。パフォーマンスは、全コンテスト参加者について aperf と呼ばれる値が分かれば求めることができます。この aperf は、これまでのパフォーマンス履歴から得られるレートのような値です。
なので、パフォーマンスとレート遷移を計算するには以下の情報が分かれば良いことになります:

  • 順位表データ（順位/ユーザー名/レート/参加回数）
  • rated 参加者の aperf データ

順位表データは AtCoder に API が用意されているのでそこから取得すれば良いですが、問題は rated 参加者の aperf データの取得です。
もし、各クライアントから全 rated ユーザーの aperf データを取得したとしましょう。現状のサービスを利用しているユーザー数は 1000 人 ほど、有効 rated 人数は 10000 人ほどで、一人の aperf データの取得には 1 リクエストかかります。なので、このままでは AtCoder のサーバーに 1e9 回ほどのリクエストが飛んでいってしまうことになります。これでは立派な DDoS 攻撃です。
そこで、開発者が代表して全 rated 参加者のデータを取得し、それを配信することで対処することにします。
すると、その処理を実現するために必要な要素は以下のようになります:

  • aperf データ配信サーバー
  • データをアップデートするクローラ
  • クローラを動かすためのスケジューラ

これらが主に行われている処理と、それに必要な要素となります。

構成

2020 年 12 月現在の ac-predictor がどのような構成で動いているのかを紹介します。

構成要素

  • フロントエンド
  • UserScript: AtCoder ページ上で利用できる拡張機能
  • Web ページ: UserScript をインストールすることなく予測を利用可能な Web ページ
  • バックエンド
  • API: クロールした aperf を配信するための API と、Web ページ用に順位表を取得して返すための API
  • クローラ: 参加者のレートを計算するためのクローラ
  • データベース: クロールしたデータを保存しておくためのデータベース
  • スケジューラ: クロールを定期的に実行するためのスケジューラ

UserScript

ac-predictor/ac-predictor-extension at master · key-moon/ac-predictor
TypeScript で開発をし、Rollup にて UserScript として発行可能な形にバンドルを行っています。テストは Jest を用いています。
バンドルのフレームワークとしてスタンダードな WebPack を用いていない理由としては、RollUp を用いるとバンドルファイルがコンパクトに収まるためです。UserScript はスクリプトの安全性を担保するために可読的であることが望ましいため、バンドル後にボイラープレートのコードが多くなる WebPack はこの用途には不向きだと考えました。
また、他スクリプトによる上書き等の問題が多発したため、外部ライブラリは jquery 等も含めて一切用いていません。

Web ページ

ac-predictor/ac-predictor-frontend at master · key-moon/ac-predictor
Jekyll + TypeScript にて開発をし、GitHub Pages にてホストしています。
デプロイは、リポジトリが変更された際に CI が走り、gh-pages ブランチに上記ディレクトリをコピーした後に Rollup を用いて TypeScript をバンドルすることで実現しています1。

API

aperfs API

key-moon/ac-predictor-data
GitHub のリポジトリをデータベースとし、GitHub Pages で直接配信しています。GitHub Pages にはクロスドメイン制約2がないため、AtCoder ページ上からでも取得することができます。
ただし、GitHub Pages には

  • サイトのサイズについての 1GB の制限
  • 月当たり 100GB のソフトな帯域幅制限
  • 時間あたり 10 ビルドのソフトな制限

という利用制限があります3。
帯域幅については、2020 年 6 月時点でのピーク時の転送量が 2.1GB でした。この転送量が変わっていないとすれば、月に 40 コンテスト程度ならば転送可能であるという見積もりが立てられます4。
また、クロールは後述の通り基本的に 15 分おきに行っているため、時間あたりのビルド数は高々 6 ビルドです。
これらを鑑みると、これらの制限の元でも当分の間ホストはできそうです。

standings API

ac-predictor/ac-predictor-backend at master · key-moon/ac-predictor
C#, ASP.NET Core にて実装されています。後述のクローラの実装時に作成した内部用の AtCoder ライブラリを使用しています。
AtCoder の順位表データは DoS 攻撃防止の観点からログインユーザーしかアクセスできなくなっているため、専用アカウントの認証情報を環境変数で持たせています。また、純粋に AtCoder 側の順位表を返すのではなく、不要なデータ（各問題の所要時間等）を除いた後、圧縮して送信するといったことをして帯域幅を節約しています。

クローラ

ac-predictor/UpdateAPerfs.cs at master · key-moon/ac-predictor
C# を用いて書かれ、Azure Functions 上でサーバレス関数として実行されています。後述のスケジューラからの呼び出しで起動します。GitHub リポジトリをデータベースとして用いているため、GitHub 関連のライブラリである OctoKit を使用しています。また、他のプロジェクトからも再利用したいため、AtCoder のためのライブラリは別途実装し、それを利用する形としました。
クロールは以下のような手順で行われます:

  1. 最初に既にクロール済みのファイルが存在するか確認した後、存在するならばそれを取得する
  2. その後、参加者のうち Rated で未クロールなユーザーについてそれぞれクロールを行う
  3. 全てのユーザーについてクロールが終わったら、結果をリポジトリに保存することでクロール終了とする

データベース

前述の通り、GitHub のリポジトリをデータベースとしています。

スケジューラ

ac-predictor/CrawlScheduler.cs at master · key-moon/ac-predictor
前述のクローラと同一のアプリケーションとして動いています。また、後述の要件を満たすために Azure Durable Functions という長時間実行する Azure Functions 用のライブラリを使用しています。

このスケジューラは「コンテスト開始2時間前からコンテスト終了まで、15分おきにクローラを叩く」という動作をしています。
もちろんスケジューラを 15 分おきに cron ジョブで実行し、その度にコンテストリストを取得してクロールが必要なコンテストをクロールする、としても良かったですが、今回は別のアプローチで実装をしました5。

  1. クローラを叩く
  2. コンテストが終わっていたら return する
  3. 15 分待機する
  4. 再帰する

といった動作をします。
前述した Azure Durable Functions というライブラリは、例えば「1日連続して関数を動かす必要があるが、関数の殆どは待機時間」といった空白の時間が多い長時間関数のためのライブラリです。これを用いることで、空白の時間は関数を停止させて実行時間を節約することができます。今回であれば、15 分待機するためにこれを使用しています。
以下のコードはその関数の簡易版です。実コードでは input がコンテスト名のリストでしたが、このコードでは input をコンテスト名としています。

[FunctionName("PeriodicCrawlExecuter")]
public static async Task PeriodicCrawlExecuter(
    [OrchestrationTrigger] IDurableOrchestrationContext context, ILogger logger)
{
    var dueTime = context.CurrentUtcDateTime.AddMinutes(15); // 関数の開始から15分後を取得

    var contest = context.GetInput<string>(); // 関数の入力受け取り
    var result = await context.CallActivityAsync<bool>("UpdateAPerfs", contest); // クローラを叩く
    
    if (!result) return;

    await context.CreateTimer(dueTime, CancellationToken.None); // 15分待機（待機中は課金が発生しない）
    context.ContinueAsNew(needCrawlContests); // 自身を同じ引数で呼び出す（再帰）
}

図

以上の構成を図にすると、以下のようになります。（Web 版や、それにまつわる standings API は省略）

pic.png

おまけ

おまけ1: ac-predictor を支えられなかった技術

ac-predictor は 2018 年の 7 月にリリースされました。2 年間そのシステムをベースとしたものを運用していましたが、その 2 年後である今年（2020 年）の 6 月に大規模な改修を行いました。ここでは、その改修を行う前のレガシーなシステムについて紹介します。

改修理由

概要の前に、このシステムを改修するに至った経緯について説明したいと思います。
大きな理由としては、ユーザー数の増加に伴い増加したトラフィックに継続して対処することが難しくなったことが挙げられます。これについては後に詳述しますが、今年 3 月頃から AtCoder Beginner Contest の参加者が急増し、4 月には 10000 人の大台を突破しました。これに伴って ac-predictor の利用者も増加し、結果として以前より問題視していた配信基盤の貧弱さの問題が顕在化してしまいました。
また、人為的な操作に依存した設計になっていたことが原因の障害が何度か起きていたことも改修を行う動機となりました。

構成

構成要素

構成要素は改修後と大きく変わりませんが、再掲しておきます。

  • フロントエンド
  • UserScript: AtCoder ページ上で利用できる拡張機能
  • Web ページ: UserScript をインストールすることなく予測を利用可能な Web ページ
  • バックエンド
  • API: クロールした aperf を配信するための API と、Web ページ用に順位表を取得して返すための API
  • クローラ: 参加者のレートを計算するためのクローラ
  • データベース: クロールしたデータを保存しておくためのデータベース
  • スケジューラ: クロールを定期的に実行するためのスケジューラ

UserScript

WebPack を用いて、バンドルの後リリースするようにしていました。AtCoder に配置されている jquery と Moment.js を外部ライブラリとして用いています。また、コードの透明性を確保する目的で

の 2 つのライブラリを別途ファイルに分離して require で参照していますが、かえって透明性を阻害する結果となっていました。

Web ページ

後述の配信 API が置かれているサーバーに、静的コンテンツとして配置しました。ロジックは JavaScript で書かれており、これには WebPack 等は導入していません。

API

C#, ASP.NET を用いています。ホストは Azure Web Service の Free プランです。データベースから取得してデータを返すのが主ですが、特にリクエスト数が多い aperfs API では以下のような通信量上の工夫を行っていました。

  • できる限りキャッシュをする
  • データベースへのアクセスは起動直後の取得のみとし、それ以外はキャッシュから配信する
  • last-modified ヘッダを追加することで無駄な送信を抑える
  • 返すデータの精度は小数点以下 2 桁に抑える
  • 未参加者は全員同じレートとして計算されるため、それらを含めないことで未参加とする
  • データは圧縮して送信する

また、standings API でも不要なデータ（各問題の所要時間等）を除いて送信するといった工夫は行っていました。

クローラ

上述の配信 API が置かれているサーバーと同じサーバーに、REST API として外部から実行可能な形でクローラを配置しました。これも ASP.NET を用いて実装されています。

データベース

Free プラン6が存在する MongoDB Atlas を使用しました。

スケジューラ

それぞれのコンテストの前毎に、自 PC にて上述の API を 15 分おきに叩く C# プログラムを手動で走らせていました。コンテスト名も自動で取得せず、手動で入力していました。

図

以上の構成を図にすると、以下のようになります。（Web 版や、それにまつわる standings API は省略）
pic2.png

おまけ2: ac-predictor 障害集

いつも利用して頂いている皆様、本当にご迷惑をお掛けしています。上述したように改善を行うことでリリース当初よりも強固な設計になってきていますが、未だに障害は発生しています。
そこで、より安心して利用していただくためにも今まで発生した障害の詳細と対策を以下に挙げました。読み物としても面白くなっていると思います。

クローラの起動忘れによる障害

概要

  • 発生日時: 2019-09-07(abc140) 21:00-21:40, 2019-11-04(agc040) 00:00-03:00, 2020-05-17(abc168) 21:00-23:00
  • 影響範囲: 拡張版/サイト版ユーザー
  • 主な影響: 予測が非常に不正確になる

詳細

旧システムでは、コンテストがある時にクローラを叩くジョブを手動で起動するという運用をしていました。そのため、クローラの起動を忘れるとクロールがなされずに全員が黒コーダー（＝初参加）扱いとなり、全く意味をなさない予測を表示していました。

対策

クローラを Azure Functions にて自動実行するようにしました。

契約サーバーの帯域制約による障害

概要

  • 発生日時: 多数
  • 影響範囲: 拡張版/サイト版ユーザー
  • 主な影響: 予測を表示できない

詳細

ac-predictor 開発当初はユーザー数も少なく、キャッシュやデータ圧縮といったことをせずに無料プランのサーバーを用いてもコンテスト時以外は転送量が問題になることはありませんでした。また、問題となるコンテスト時は帯域制限がなくなる有料プランに切り替えるという運用で無料プランの帯域制限を回避していました。しかし、人力でのプラン切り替えのため、プランの切り替え忘れによる障害が何度か発生していました。

前述の有料プランの利用は、Azure に登録した際に配布される $100 クレジットを用いていました。このクレジットの有効期限は一年であったため、運用開始から一年後の 2019 年 5 月にはこの運用が不可能になりました。有料プランによる帯域制限の回避ができなくなったため、その後の 3 回程のコンテストではコンテスト中に利用ができなくなる障害が発生し、コンテスト後に私がローカルで計算したものを公開することで不完全ながら対応をしました。

ここで、使用している無料プランである Azure App Service F1 プランの帯域制限について詳しく説明します。このプランでは、一日に転送できるデータ量が 165MB、つまり月あたり 5GB です。しかし、この制約には以下のような緩和策が存在します:

月末まで、日当たりの未使用帯域を翌日に繰り越す。月初は、日当たり 165MB よりやり直される。
Azure App Service Free プランのための帯域クオータ変更(英語) より邦訳

これにより、一週間に一度や二度のコンテストであれば、数日分程度のデータ転送量をまとめて使用することができることになります。圧縮やキャッシュを実装してコンテスト一度の転送量を 350MB 程度に抑えられることを考えると、これは十分な量です。
しかし、もし月初の転送量リセットとコンテストが被ってしまった場合は、165MB の転送量でやり過ごさないといけなくなります。そのため、月初付近にコンテストが発生した場合は障害が発生することが分かった上で何も対処ができないといった状況になり、告知をした後に前述のようにローカルで計算したものを公開する対応を取らざるを得ませんでした。

そのような運用を半年程続けましたが、2020 年 3 月から 4 月にかけて状況が変化しました。大学入学シーズンや新型コロナウィルスによる自粛ムードといったものの影響を受け、参加者が急増したのです。

ここで、この増加による転送量の増加を見積もってみましょう。転送量は

キャッシュがある時のレスポンスサイズ(定数)×リクエスト数(参加者数に比例)+キャッシュがない時のレスポンスサイズ(参加者数に比例)×アクティブユーザー(参加者数に比例)×更新回数(定数)

で概算できます。

参加者数の増加はアクティブユーザーと配信するデータ量のどちらにも影響するため、配信量は二乗オーダーで増加します。そのため、参加者数が 2 倍になるとリクエストは 4 倍にも膨れ上がります。5 月のピーク時では毎コンテストで 70000 リクエストものリクエストが発生し、データ転送量は 2.1GB にも膨れ上がっていました。
image.png

3 月時点でも相当なリクエストが発生していたために無料プランで捌き切ることは諦め、コンテストのある日のみ有料プランを使用するといった初期のような運用でカバーすることとしていました7。
しかし、人力での運用ではミスもあり、プランの引き上げを忘れるといったことによる障害を何度か発生させてしまいました。また、プランの引き下げを忘れて少々放置してしまい、5000 円程を飛ばしてしまうといった事故も発生しました8。

対策

データ配信サーバーを GitHub Pages に移行しました。

2020 年 6 月以前によく発生していた「predictor 落ちた/動かない!」は、殆どが上記の「クローラの起動忘れ」と「帯域制約」の 2 つが原因です。本文やおまけ 1 で述べた通り、新システムに移行することでこの障害を原理的にほぼ防止しています。
なぜ「ほぼ」と言っているかというと、限定的な範囲ではまだ同様の障害が起こりうるからです。Web 版の ac-predictor はクロスドメイン制約回避のために順位表の配信をサーバー経由で行っています。このサーバーも件の無料プランで契約しているため、コンテストが発生する等で月初にウェブ版の利用者が多かった場合にも同じ問題が起きる可能性があります。実際、2020 年 11 月 1 日に行われた abc181 でのウェブ版の障害はこれによるものです。
対策として、配信する順位表データから所属や問題ごとの成績といった無駄な情報を除き、その上で圧縮して転送するといったことをしています。しかし、それでも順位表は 300kB 弱の転送量になってしまうため、月初であれば 500 リクエスト程度で落ちてしまいます。通常の ABC では 700 リクエスト程度が発生するため、現状は「月初にコンテストがある時はバックエンドのプランを上げる」という運用によってカバーしています。

abc178 のリクエストの様子:image.png

管理者による任意コード実行の脆弱性

概要

  • 発生日時: -2019/06/28 02:42
  • 影響範囲: 拡張版/サイト版ユーザー(影響を受けたユーザーは存在せず)
  • 主な影響: データ配信サーバーに配置されたスクリプトを実行してしまう

詳細

AtCoder 側の jquery のバージョンが古かったために脆弱性 CVE-2015-9251 が存在し、これによってデータ配信サーバーに配置された悪意あるスクリプトをクライアント側で実行させることが可能になります。

CVE-2015-9251の概要`jquery 3.0.0` 以前に存在する `XSS` の脆弱性です。 `evilcode.json` に `text/javascript` コンテンツヘッダをつけて配信されるスクリプトが存在した場合、`$.ajax("evilcode.json")` を実行することによってそのスクリプトが実行されてしまいます。 これは、`$.ajax({ url: "evilcode.json", dataType: "json" })` のように明示的に `dataType` を指定することによって回避が可能です。

サーバー管理者は私であり、外部からの攻撃等もなく幸いにも不審なファイルが配信されたことはなかったため、被害はありませんでした。

対策

$.ajax を用いてデータを外部から取得している箇所全てにおいて、dataType 属性を指定しました。また、後方互換性も兼ねて旧データ配信サーバーのドメインを保持しています。

参加者の rated 判定の漏れによる予測ミス

概要

  • 発生日時: 2020/06/07(agc045) 21:00-24:00
  • 影響範囲: 拡張版ユーザー
  • 主な影響: 予測に誤差が生じる

詳細

該当日時に開催された agc045 では、初めて有効な rated 下限制約が追加されました。rated 参加者の判定を上限のみで行う不完全な実装が存在したために rated でない参加者をサンプルに含んだ計算を行ってしまい、誤差のある予測となってしまいました。

対策

rated 判定のロジックを修正しました。

プロパティチェックの実装による障害

概要

  • 発生日時: 2020/08/22(abc176) 21:00-22:25
  • 影響範囲: 拡張版/サイト版ユーザー
  • 主な影響: 予測を表示できない

詳細

パフォーマンスをを計算する部分のコードについて、以下のようなコードがありました。(単純化しています。)

rate = rates[user] ? rates[user] : defaultValue;

rates は内部レートを格納する JSON をパースした Object 型、user は参加者の ID です。rates には「一度以上参加した参加者のレート」が格納されています。そのため、初参加ならば rates[user] は undefined、すなわち偽として評価され、rate には defaultValue が格納されるはずでした。
しかし、JavaScript のオブジェクトはデフォルトで複数のメンバを持っています。例えば、toString や constructor です。ここで、そのような名前を持つユーザーが参加した場合を考えます。
当然 rates["constructor"] は undefined ではないため、真として評価されます。結果として rate に数値でない値が入ってしまい、予期せぬ実行時エラーによって予測が停止してしまっていました。

対策

メンバの存在チェックに hasOwnProperty を使うことにより、同様の問題を防止しました。

AtCoderの仕様変更によって起きたパースエラーによるクローラの停止

概要

  • 発生日時: 2020/11/08(abc182) 19:00-22:50
  • 影響範囲: 拡張版/サイト版ユーザー
  • 主な影響: aperfのデータが提供されず、予測を表示できない

詳細

ac-predictor のクローラを起動するためのスケジューラは、AtCoder の「現在のコンテスト」ページをパースすることで今後にコンテストがあるかや rated であるか等の情報を取得しています。そのページの英語版において、以下のような仕様変更がありました。

Present Contests at 2020/11/01
image.png
Present Contests at 2020/11/15
image.png

これを見て頂ければ分かる通り、英語版ページでの Rated Range の文字列が ~ 1999 から - 1999 に、つまり区切り文字がチルダからハイフンに変化しています。この変更により、パースが出来ずにパーサが停止していました。

対策

原因を特定してパーサを書き直した後、即時の対応としてコンテスト中にクロールを回しました。復旧を最優先で 1000 人程度クロールした時点でデータを追加してしまい、コンテスト終了時にもまだ 5000 人程度しかクロールが完了していませんでした。その結果、コンテスト中の予測が非常に不正確なものとなってしまいました。
また、この障害はサーバーで起きていたエラーを見逃し続けていなければ防げたものです。そのため、エラーを検知したらメールにて通知するアラートを追加しました。

セッションの期限切れによる障害

概要

  • 発生日時: 2020/11/10-2020/11/14(agc049) 20:40(クローラ復旧), -2020/11/15 01:00(サイト復旧)
  • 影響範囲: サイト版ユーザー
  • 主な影響: サイト版 predictor で予測を表示できない

詳細

AtCoder では、DoS 攻撃防止の観点より順位表データの閲覧にログインを必須としています。そのため、順位表を配信する Web 版の API サーバーとクローラには専用アカウントのセッションを保持させています。しかし、セッションは環境変数でサーバーに入れたものを更新せず使っていたために、セッション期限の 6 ヶ月が経過した 11/10 にデータが取得できなくなり、エラーとなりました。

対策

新たなセッションを作成し、サーバーにセットしました。また、セッションではなくパスワードを保持させてログインを行うようにしました。
この問題は、前述の導入したアラートがクローラの異常を検知して通知をしたためにコンテスト前に気がつくことができ、余裕を持って対処を行うことができました。

  1. GitHub Pages では、特定のディレクトリやブランチに置かれたファイル群を Jekyll のページとしてホストできます。 ↩

  2. 他ドメインからのアクセスを制限する制約 ↩

  3. GitHub Pages について - GitHub Docs より ↩

  4. もちろん、今後参加者が増えて転送量が増えるかもしれません。 ↩

  5. 実際の所、複雑性を考えると愚直に実装した方が良かったかもしれません。
    まず、1 時間おきに cron ジョブで関数を実行します。その際にコンテストリストを取得し、開始 2 時間前でかつクロール済リストに入っていないコンテストを列挙します。もしそれらのコンテストがあった場合、スケジューラを叩きます。つまり、1 時間おきに叩くこの関数は「スケジューラのスケジューラ」としての役割を果たしているわけです。
    また、その叩かれたスケジューラは再帰関数になっており、 ↩

  6. 総データ量 512MB, RAM は共用 ↩

  7. この運用を 3 月以前にできなかったのは、学生プランで Azure を契約したために支払手段を登録していなかったからです。個人的な理由でご迷惑をお掛けしてしまい、申し訳ありませんでした。 ↩

  8. つらい ↩

41
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
41
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?